A Multi-objective Evolutionary Algorithm with Dynamic Topology and its Application to Network-Wide Flight Trajectory Planning

Abstract

Although conventional multi-objective evolutionary optimization algorithms (MOEAs) are proven to be effective in general, they are less superior when applied to solve a large-scale combinational real-world optimization problem with tightly coupled decision variables. For the purpose to enhance the capability of MOEAs in such scenarios, one may consider the importance of interaction topology in information exchange among individuals of MOEAs. From this standpoint, this article proposes a non-dominated sorting genetic algorithm II with dynamic topology (DTNSGAII), which applies a dynamic individual interaction network topology to improve the crossover operation. The dynamic topology and inter-individual interaction are determined by the solution spread criterion in the objective space as well as the solution relationships and similarities in the decision space. The combination of two aspects contributes to the balance of the exploitation and exploration capability of the algorithm. Finally, as an example to real-world applications, the DTNSGAII is used to solve a network-wide flight trajectory planning problem, which demonstrates that the application of dynamic topology can improve the performance of the NSGA-II.

Keywords

• Multi-objective evolutionary algorithm
• complex network
• flight trajectory planning