Coevolutionary Numerical Optimization Algorithms And Their Applications

Coevolution is a universal phenomenon in the nature. Coevolution happens when two or more species influence each other's evolution and it is most often invoked to explain coadaptations between species. The biological study shows that coevolution is beneficial to biological evolution. A Coevolutionary Algorithm (CEA), which employs the coevolutionary mechanism within a classical evolutionary algorithm (EA), is an extension to EAs. Solving optimization problems with CEAs has become an important research area of evolutionary computation in recent years. This dissertation is focused on the research of CEA, including the coevolutionary model building, coevolutionary algorithm design and its applications. Firstly, CEAs are categorized based on the induction of the existing CEAs and then the state-of-the-art of CEAs is surveyed. After that, a new coevolutionary model and several new algorithms and strategies are proposed for numerical optimization including unconstrained optimization, constrained optimization and multiobjective optimization. Afterwards, the new algorithms are applied to the detection of communication signals and the equilibrium-constrained circles packing problem with the background of satellite module layout design. The main innovative points of this dissertation can be summarized as follows:(1) The M-elite coevolutionary model and the M-Elite Coevolutionary Algorithm (MECA) are proposed for high-dimensional unconstrained numerical optimization problems based on the concept of coevolutionary algorithm and elitist strategy. In the MECA, the individuals with high fitness, called elite population, are considered to play dominant roles in the evolutionary process. The whole population is divided into two subpopulations which are elite population composed of M elites and common population including other individuals, and team members are selected to form M teams by M elites acting as the cores of the M teams (named as core elites) respectively. If the team member selected is another elite individual, it will exchange information with the core elite by the cooperative operation defined in the paper; If the team member is chosen from the common population, it will be led by the core elite with the leading operation. The cooperative and leading operation above are defined by different combinations of several crossover operators or mutation operators. The algorithm is proved to converge to the global optimization solution with probability one. Tests on 15 benchmark problems show that the algorithm can find the global optimal solution or near-optimal solution for most problems tested. Compared with two classical EAs and three CEAs, MECA achieves an improved accuracy with the same number of function evaluations. Meanwhile, the runtime of MECA is less, even compared with the standard genetic algorithm with the same parameter setting. Moreover, the parameters of the MECA are analyzed in experiments and the results show that MECA is insensitive to parameters and easy to use.(2) The M-Elite Coevolutionary Algorithm (MECA) is improved and extended to solve constrained optimization problems. The orthogonal crossover operator is introduced into MECA to improve the algorithm performance and static penalty functions are used to handle constraints. Tests are made on 13 benchmark problems. The experimental results and the parameter analysis show that the MECA can obtain high solution quality with less runtime and is robust and it obtains better performances than some classical constrained optimization evolutionary algorithms as well as another coevolutionary algorithm, and can solve difficult constrained optimization problem.(3) The Nondominated Neighbor Coevolutionary Algorithm (NNCA) is proposed for multiobjective optimization by introducing the nondominated neighbor selection (NNS) mechanism to the M-elite coevolutionary frame. The whole nondominated population is divided into two subpopulations which are elite population and common population according to the crowding-distance values, where elite population is composed of nE nondominated individuals with higher crowding-distance values. The elite individual located in less-crowded region will have more chances to select more members for its own group and thus this region can be explored more sufficiently. A Size Guarantee Mechanism (SGM) for elite population is proposed so as to avoid the'search stagnation'situation due to the NNS mechanism when the nondominated individuals are too few. The SGM is realized in such a way: as the actual size of elite population is smaller than nE, several dominated individuals, which are selected from the reserved population composed of dominated individuals, will emigrate to the elite population to ensure that the size of elite population is equal to nE. The SGM can prevent the algorithm searching around limited nondominated individuals and trapping into the'search stagnation'situation. The combination of coevolutionary mechanism, NNS mechanism and the idea of emphasizing the role of elite population make the NNCA obtain good search capability and convergence performance. Tests on 13 multiobjective optimization benchmark problems show that NNCA does much better than other excellent multiobjective optimization evolutionary algorithm including NSGA-II, SPEA2 and NNIA in terms of the approximation property and the extent property. Meanwhile, except SPEA2, NNCA does best in terms of diversity maintenance.(4) A new algorithm named as M-elite Evolutionary Algorithm (MEA) is presented with low complexity and high performance to approach the performance of Maximum-Likelihood (ML) detection, for solving the problem of the high complexity of ML detection in real-time Vertical-Bell laboratories LAyered Space-Time (V-BLAST) communication system. The simulation of one knapsack problem validates the effectiveness of MEA to solve combinatorial optimization problems. Furthermore, the simulation of V-BLAST communication system shows that the MEA-based detection algorithm can approach the performance of ML well, and is superior to the detection algorithms based on standard genetic algorithm and that based on clonal selection algorithm as well as some classical ones.(5) The M-Elite Coevolutionary Algorithm (MECA) is extended to the equilibrium-constrained circles packing problem with the background of satellite module layout design, which belongs to NP-hard problem. Static penalty functions are used to transform a constrained packing problem into an unconstrained one. Firstly, four engineering design problems including Welded Beam Design, Spring Design, Speed Reducer Design and Three-Bar Truss Design are used to validate the effectiveness of MECA for practical engineering optimization. Then tests are made on 3 equilibrium-constrained circles packing problems and the experimental results show that the MECA can obtain high quality solution with less runtime, and can solve difficult constrained packing problems.