Population Topology Structure-based Differential Evolution Algorithm And Its Applications In Clustering

Evolutionary algorithms (EA) are a family of population-based optimization metaheu-ristics designed for searching optimal values in complex spaces. Individuals in the popula-tion represent tentative solutions to the problem at hands, and the algorithm iteratively ap-plies some stochastic variation operators to them in order to make the population evolving toward better solutions in the search space. It is well accepted in the literature that the or-ganization of individuals in the population has a major influence on the search EAs perform. Differential evolution (DE) algorithms compose an efficient type of evolutionary algorithm for the global optimization domain. Differential evolution algorithm is easy to be trapped in local area and avoid finding out the best solution of the problem. There are three common improvement strategies which were proposed to avoid premature. Firstly, differential evolu-tion combined with other evolutionary algorithms to speed up convergence rate. Secondly, differential evolution updates the control parameters for the specific problem. Finally, dif-ferential evolution makes use of evolutionary strategies newly designed. Although it is well known that the population structure has a major influence on the behavior of EAs, there are few works studying its effect in DE algorithms. So, the population topology structure of differential evolution will be discussed in this dissertation.First, we discuss and analyze several DE variants using different panmictic and decen-tralized population schemes. As it happens for other EAs, we demonstrate that the popula-tion scheme has a marked influence on the behavior of DE algorithms too.Secondly three novel self-adaptive population topology DE algorithms are proposed for the unconstrained global optimization problem. The first improved algorithm is adaptive population topology differential evolution with random selection scheme, which is called APTDE. Moreover, the second improved DE, namely SAPTDE, makes use of improvement of the best individual to guide the population topology self-adaptation. The third improve DE try to take the probability of the successful individual into account to discover the most suitable topology, which is called ISAPTDE. These three topologies adaptation methods automatically update the population topology to appropriate topology to avoid premature convergence. These methods utilize the information of the population effectively and im-prove search efficiency. Hence it can enhance the performance of DE. The set of25bench-mark functions provided by CEC2005special session is employed for experimental verifi-cation. Experimental results indicate that all of the three improved DEs are effective and efficient. Results show that all of the adaptive or self-adaptive population topologies based differential evolution algorithms are better than, or at least comparable to, other DE algo-rithms. Moreover, they with an external archive show promising results for high dimension-al problems.Third, two general optimization models gleaned ideas from the coevolution of symbi-otic species in natural ecosystems are presented. The first improve DE, named CoPTDE, is using the coevolutionary affect between different population topologies. Moreover, species extinction and speciation events are also considered in this model to tie it closer to natural evolution, as well as improve the algorithm robustness. This model is instantiated as a novel multi-species optimizer, namely Dynamic CoPTDE, which extends the dynamics of the ca-nonical DE algorithm by adding a significant ingredient that takes into account the symbi-otic coevolution between population topologies. When tested against benchmark functions, the CoPTDE and DCoPTDE are markedly outperforms the canonical DE algorithm in terms of accuracy, robustness and convergence speed.At last, a modified differential evolution (DE) based on population topologies algo-rithm is presented for clustering the pixels of an image in the gray-scale intensity space. The algorithm requires no prior information about the number of naturally occurring clusters in the image. It uses a kernel induced similarity measure instead of the conventional sum-of-squares distance. Use of the kernel function makes it possible to partition data that is linearly non-separable and non-hyper-spherical in the original input space, into homoge-neous groups in a transformed high-dimensional feature space. A novel search-variable rep-resentation scheme is adopted for selecting the optimal number of clusters from several possible choices. Extensive performance comparison over a test-suite of4gray-scale imag-es and objective comparison with manually segmented ground truth indicates that the pro-posed algorithm has an edge over a few state-of-the-art algorithms for automatic multi-class image segmentation.