CMA-ES And Decomposition Strategy For Large Scale Continuous Optimization Problem

Continuous optimization have a wide application both in the engineering problems and academic field. Actually, many problems could be formulated as continuous opti-mization problems. As the system complexity grows, more and more parameters need to be optimized, which results in the increment of the dimensionality for the problem to be optimized. Under the circumstances, large scale continuous optimization appears. Evolutionary algorithm, as an universal optimizer, has many excellent properties such as robustness and capability of global search. Due to the ease implementation and paral-lelism, evolutionary algorithm is well suited for the continuous optimization problems. However, evolutionary algorithm suffers from the curse of dimensionality. Namely, the performance of evolutionary algorithm deteriorates rapidly as the dimensionality of the optimization problems increases. Cooperative coevolution is an evolutionary framework based on divide-and-conquer strategy. Cooperative coevolution firstly de-composes the whole search space into several subspaces with relatively smaller size, and then use appropriate evolutionary algorithm to optimize those sub-problems in a round robin fashion. There have been several algorithms proposed which incorporated evo-lutionary algorithm into cooperative coevolution framework and achieved remarkable performance improvement especially on high dimensional problems compared with the original evolutionary algorithm. The key procedure of cooperative coevolution frame-work is the decomposition strategy. There will be many variables interactive between each other and they should be decomposed into the same sub-problem. Otherwise, the inappropriate decomposition could has serious influence on the performance of the op-timization algorithm. This dissertation has the following main goals:1. Researching decomposition strategy based on the cooperative cpevolution frame-work.2. Reaeraching and designing algorithm to solve large scale continuous problems based on the cooperative coevolution framework.3. Formulating decomposition problem as optimization problem, and giving both theoretical and application analysis.Based on those targets, in this dissertation we conducted research for the decom-position strategy based on CMA-ES and cooperative coevolution framework and used proposed decomposition strategies in CMA-ES to solve large scale continuous opti-mization problems. Also, we gave the theoretical basis for the proposed decomposition strategies and expanded it to universal clustering problems. The main contents and contributions of this dissertation are as follows: 1. Based on normal distribution, we proposed two new decomposition strategies for CMA-ES from the perspective of balance between exploration and exploitation in search.2. Based on the two proposed decomposition strategies and cooperative coevolution framework, we proposed a new algorithm called CC-CMA-ES for large scale continuous optimization problems. We conducted experimental studies of CC-CMA-ES on a suite of large scale continuous optimization problems and verified the effectiveness and efficiency of our decomposition strategies and CC-CMA-ES.3. From the perspective of KL divergence, we formulated the decomposition prob-lem as a discrete optimization problem and gave the theoretical basis for the pro-posed decomposition strategies. We expanded the decomposition problem to uni-versal clustering problems, and proposed a clustering algorithm which is based on KL divergence. Using simulated annealing algorithm, we verified its effec-tiveness on the Iris dataset.Through the research of CMA-ES and cooperative coevolution framework, this dissertation proposed two decomposition strategies and use them into CMA-ES based on cooperative coevolution framework. The new algorithm has remarkable perfor-mance on optimization problems with1000dimensionality. From the perspective of KL divergence, we interpreted the basis for our decomposition strategies and proposed a universal clustering algorithm. The work in this dissertation not only has important theoretical value in scaling up evolutionary algorithm to large scale optimization prob-lems, but also established relationship between decomposition and clustering.