{'fraction_non_alphanumeric': 0.022693635915145536, 'fraction_numerical': 0.0, 'mean_word_length': 5.993103448275862, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Graph-based Genetic Algorithm to Solve the Virtual Constellation Multi-Satellite Collection Scheduling Problem

A variety of near-optimal problem-solving methods inspired from operations research and computational intelligence has been proposed to solve the NP-hard multi-satellite collection scheduling problem (m-SatCSP). In particular, genetic algorithms, well-suited for large-scale problems due to their simplicity and low-cost implementation have been the most pervasive and proven to be very effective. However, most reported contributions mainly promote basic permutation-based genetic principles with limited variants, overlooking prior problem structure exploitation and, widely focus on a single satellite or simple trailing satellites constellation composition. In this paper, a novel graph-based hybrid genetic algorithm is introduced to tackle the static m-SatCSP, involving a mixture of any non-trailing satellites composing a virtual constellation. The proposed Genetic Algorithm-based collecTion scHedulER (GATHER) explicitly exploits problem structure governing feasible imaging opportunity transitions through collection graphs to better handle temporal constraints. Coupled to a low-cost task scheduling heuristic integrated to genetic operators it enhances directed search and speed-up the generation of feasible high-quality solutions. The scheduling approach introduces the notion of mutual satellite orbit compatibility for dissimilar platforms to efficiently explore promising regions of the search space in evolving collection path plans. Taking advantage of those problem domain knowledge instances, the hybrid strategy evolves a mixed population of feasible/infeasible individuals to maximize the expected collection value. A multi-objective implementation named MO-GATHER is finally proposed. Computational experiments confirm that GATHER is cost-effective and competitive in comparison to alternate baseline scheduling heuristics. The benefits of MO-GATHER to decision makers are also discussed.