Large Scale Evolution Optimization Algorithm Based On Simplex Multi-Direction Search

Evolutionary algorithms (EAs) often act as optimizers, but they are always pestered by dimensionality curse. This paper aims to solve Large Scale Global Optimization (LSGO) by evolutionary algorithms based on Nelder-Mead simplex multi-direction search (SMDS). Under the generalized neighbor search frame, we try our best to mine search directions implicated in Nelder-Mead simplex method (NMSM) so that we construct Simplex Genetic Algorithm (Simplex GA), Simplex Particle Swarm Optimization (Simplex PSO), and Simplex Cooperative Co evolution Algorithm (Simplex CCEA) based on symbiotic mechanism.The main researches in this paper are summarized as follows.(1) Mine search directions implicated in NMSM and make full use of them. The main drawbacks of NMSM are as follows:(a) NMSM provide neither precise nor abundant gradient information, for example, Jacobi matrix and component gradient information; (b) NMSM easily traps into a local extremum; (c) NMSM is not suitable to be used to optimize high-dimensionality function or to optimize low-dimensionality function in large. From the above, it is the most important for us to mine all search directions implicated in NMSM so as to improve the precise of search direction and to enhance search efficiency. Hence the strategy SMDS is proposed by introducing two elemental concepts of generalized simplex and generalized simplex matrix and three important decomposition method of the generalized simplex matrix, including row decomposition, column decomposition and row-column decomposition. Consequently, three kinds of SMDS are presented further in this paper, which are variable centroid SMDS I (VC-SMDS I), variable centroid SMDS II (VC-SMDS II) and steady centroid SMDS (SC-SMDS). Decomposing the generalized Simplex matrix and mining SMDS are the foundation of improving NMSM and constructing Simplex GA, Simplex PSO and Simplex CCEA.(2) Devise simplex GA.Simplex GA evolves individuals under the synthetic evolution mechanism which integrates greedy mechanism, elitism distribution mechanism, probability acceptation mechanism and the mechanism of selecting the superior and eliminating the inferior, and uses the VC-SMDS I to construct its own reproduce operators, i.e., direction reproduce operators. The direction reproduce operators are composed of dot-search operator, line-search operator, and plane-search operator or solid-search operator. Simplex GA has two implementation approaches: Low Dimension Simplex GA (LD-Simplex GA) and High Dimension Simplex GA (HD-Simplex GA). Many experiments on numerical optimization confirmed that both LD-Simplex GA and HD-Simplex GA have the capacity of LSGO and that LD-Simplex GA is better than HD-Simplex.(3) Devise Simplex PSO.First, a basic Simplex PSO (b-Simplex PSO) is derived from VC-SMDSâ…¡and its convergence is proved by using the consistent asymptotic convergence theory of time-varying linear discrete system. Second, the Simplex PSO is attained by introducing components into b-Simplex PSO. Many experiments on numerical optimization verified that Simplex PSO is convergent and can optimize high-dimension functions, but these results for LSGO do not satisfy us.An extremum turbulence strategy and a two-level communication model are used to improve Simplex PSO, and as a result that the Simplex PSO evolves into three kinds of Simplex PSO with turbulence (Simplex PSO-t), i.e., Global Simplex PSO-t, Local Simplex PSO-t and Synthesis Simplex PSO-t. Many experiments on numerical optimization confirmed that the three kinds of Simplex PSO-t have the capacity of LSGO.(4) Devise Simplex CCEA.An improved cooperative co evolution framework based on symbiotic mechanism is proposed in order to reduce the destruct of interaction between variants, which is caused by the decomposition of vectors, and to strengthen cooperation between components of a vector. The main strategies to improve the original cooperative co evolution framework are random dynamic decomposition of a vector, secondary cooperative optimization of components, and secondary competition of individuals. Under the improved cooperative co evolution framework and the row-collomn decomposition of the generalized simplex matrix, this paper provides Simplex CCEA. Many experiments on numerical optimization confirmed that the Simplex CCEA has the capacity of LSGO.(5) Devise a simplex-based multi-modal hybrid genetic algorithm (Simplex MMHGA).Under the guidance of "decomposition and conquer", Simplex MMHGA is devised. Simplex MMHGA has three features:simple and dynamical cluster based on function peaks, embedding three kinds of NMSM (VC-SMDS I, SC-SMDS, improved NSMS) into three subpopulations (clusters) respectively, and balancing between global search (i.e.,GA) and local search (i.e.,NMSM).In words, this paper presents three kinds of large scale evolution algorithms, i.e., Simplex GA, Simplex PSO, and Simplex CCEA. These algorithms are based on the decomposition of the generalized simplex matrix and SMDS, unified by the generalized neighbor search framework and threaded by the fusion of kernels of NMSM and GA, PSO and Cooperative Co evolution.