Co-Evolutionary Algorithm With Dynamic Population Size Model, Theory And Applications

In recent years, there has been a growing interest in Co-Evolutionary Algorithms (CEAs), which are special Evolutionary Algorithms (EAs) inspired by multispecific coevolutionary phenomena in biology. CEAs have been proven effective in solving complex problems which are difficult for traditional EAs and have become a hot topic in the field of Computational Intelligence. Dynamic population size (DPS) strategy is a key technique for EAs, because appropriate population size will lead to a balance between exploration and exploitation. Unfortunately, due to the difference in evolutionary dynamics, existing DPS strategies designed for traditional EAs are not suit for CEAs. Most of existing works focus on how to design particular CEAs corresponding to variable applications and few of them is about DPS strategies for CEAs.In this paper, we start with the interactions between individuals in the fitness evaluation and designed a DPS strategy which is based on the common properties of CEAs. And then a unified co-evolutionary model is proposed, named as Co-Evolutionary Algorithm with Dynamic population size (CEAD). CEAD model, which covers most existing CEAs including cooperative, competitive, and the mixed ones, uniformly describes the generic evolution mechanisms of various CEAs from their inherent nature. Therefore, CEAD model has great significance for guidance in applications of CEAs.We give out the theoretical analysis for CEAD model and its algorithm system in the aspects of dynamics, stability, convergence and computational complexity. Analytical results show that CEAD model has global asymptotical stability which guarantees appropriate population size to CEAs designed under the guidance of CEAD model. As a result, CEAs with appropriate population size can converge to the global optimal solution stably and efficiently for the reason of the balance between exploration and exploitation, and the rational distribution of computation resources between sub-populations.Finally, the CEAD algorithm system has been applied to two kinds of typical complex optimization problems. First is the problem of Multimodal Function Optimization. Comparative experiment results show that the CEA which is under the guidance of CEAD model has many advantages, such as reasonable modulation of population size, effective utilization of computation resources, strong ability of overall search, high convergence speed and solution quality. The second application of CEAD algorithm is Air Traffic Management Problem which is a kind of typical Multiobjective Optimization problem with many constraints. A CEA with implicit constraint handling mechanism is designed under the guidance of CEAD model, and obtained better solution than those methods before. The complex problem solving ability of CEAD algorithm system is extensively verified.