Matrix-driven preprocessing, search and chromosome polymorphism: A novel genetic algorithm for large-scale satellite mission scheduling

To address the challenges of low time window utilization, poor initial solution quality, and computational intractability in large-scale Earth Observation Satellite Scheduling Problems (EOSSP), a Matrix-driven Preprocessing, Search and Polymorphic Chromosome Algorithm (MPSC) is proposed. First, the concept of a conflict matrix is introduced to drive three key improvements. Specifically, conflict matrix-guided meta-task decomposition and initial solution construction method is employed to optimize the search space and generate high-quality initial solutions. Secondly, conflict matrix-driven dynamic repair search method enhances search capability; Finally, conflict matrix-induced polymorphic chromosome structure significantly improves computational efficiency. Simulation experiments across multiple large-scale scenarios validate the effectiveness of the MPSC algorithm. Compared to baseline algorithms, it achieves a 30.12% improvement in population fitness, a 38.37% boost in computational efficiency, and outperforms in search capability by a factor of 2.8, as the hypervolume value rises from 0.3125 to 0.8774.