Research On Multimodal Optimization Algorithm With Two-Stage Search

In the field of scientific research and engineering practice,there are many kinds of optimization problems.Multimodal optimization,as one of their branches,has caused wide attention of researchers of home and broad for a long time.The goal of multimodal optimization is not only to search all global optimal solutions in the solution space,but also in some cases need to search local optimal solutions,which presents a challenge to traditional evolutionary algorithms.Because global selection scheme adopted by the traditional evolutionary algorithms leads to a bigger selection pressure to the individuals in the population,resulting in fast convergence of the population and weak ability of keeping population diversity.In order to solve this problem,many techniques combined with the traditional evolutionary algorithms are proposed,such as niching,multiple populations and bi-objectives techniques etc.The common features of these techniques are to furthest maintain the diversity of population and to reduce the probability that they converge to the same optimal solution.This dissertation mainly researches multimodal optimization algorithm based on two-stage search,and focuses on the balance of the ability between keeping population diversity and local search,concrete research contents and innovative works are summarized as following:(1)In multimodal optimization,maintaining population diversity and local search capability is a pair of contradiction.To keep population diversity,this will reduce the convergence rate of the population.Conversely,the increase of population convergence speed will also affect the diversity of population.This dissertation proposes a multimodal optimization algorithm framework based on two-stage search,trying to balance the relationship between them.In the first stage of evolution,keeping population diversity and searching solution space will be more noticed,as many as possible to find approximate locations of potential optimal solutions.However,in order to speed up convergence speed of the second stage,local search ability needs to be paid more attention to.The search results of the first stage will be divided into a number of non-overlapping subpopulations by clustering algorithm,and then local search algorithm is performed independently on each subpopulation,so as to make subpopulations convergence as soon as possible.In the second stage,the method of searching the optimal solutions one by one is adopted,which not only guarantees to preferentially search the preferred locations found in the first stage,but also to seek other locations as many as possible.This method makes algorithm not only having the ability of searching global optima,and with the capability of locating local optima.(2)In the first stage in order to expand search space and maintain stability of population,search point supplementary strategy(SPRS)is proposed.Some of individuals in clusters containing large number of individuals are selectively migrated into other clusters containing small number of individuals,which makes all clusters include the roughly same number of individuals.The selection rule of the individuals migrated is that only those individuals which are the most similar are selected to perform migration,this selection rule can reduce the impact as much as possible to original population structure.SPRS is effective on the low-dimensional problems,but on the high-dimensional problems the effect of SPRS is not obvious.In the early evolution,this strategy has good effect for expanding search space on the low-dimensional problems.However,with the evolution goes on,this effect will be weakened gradually;the migration at this time is beneficial to maintain the stability of the population and reduce the loss of the subpopulations.(3)To perform accurate clustering for the search results of the first stage,the comparative study is carried out among affinity propagation clustering(APC)algorithm,nearest better clustering(NBC)algorithm and detect multimodal clustering(DMC)algorithm.Additionally,this dissertation proposes improved detect multimodal clustering(IDMC)algorithm.DMC is a clustering algorithm based on population topological structure to divide clustering.Its advantages include partitioning clustering of arbitrary shapes,less clustering parameters,excellent clustering effect and easy to be implemented;Its defects contain the requirement of consuming extra fitness evaluations,and algorithm complexity depending on the problem to be solved.Compared with the original clustering method,IDMC has a better performance in the clustering effect and consumes less extra fitness evaluations.Especially on the problem containing a large number of optimal values,the number of fitness evaluations of IDMC method consumed is less a few orders of magnitude than that of DMC method consumed.(4)In order to enhance local exploitation capability of the second stage,this dissertation investigated covariance matrix adaptation evolution strategy algorithm(CMA-ES)in detail.The simple summary of mathematical theory foundations of CMA-ES,and the deep analysis of learning mechanisms of various CMA-ES variants are given.In addition,this dissertation proposes a(??,?)-Cholesky-CMA-ES algorithm,the new algorithm simultaneously implements incremental update of cholesky factors of "rank-1 update" and "rank-u update".The goal of introducing incremental update of cholesky factors is to get rid of eigen decomposition of covariance matrix(the complexity of eigen decomposition of covariance matix is(?)(n3)),so as to convert explicit update of the original covariance matrix into implicit upate,which makes the time complexity of CMA-ES be reduced from(?)(n3)to O((1+?)n2),where ?<<n.(5)In order to verify the performance of our proposed algorithm framework,two test sets(amount to 28 benchmark test functions)are selected,and 9 state-of-the-art algorithms are chosen to do comparative experiments.Test Setl selects 20 test functions of CEC2013 provided,to verify the ability of new algorithm searching all global optima.Test Set2 chooses 8 classical test functions selected from relevant literatures,to determinate the capability of new algorithm searching global and local optima.The experimental results show that the algorithm framework of this dissertation proposed is effective and has better adaptability,which displays a better performance on the majority of test functions.Finally,the proposed algorithm is applied to solving Nash Equilibrium problem,and some of comparative experiments are enforced between it and other state-of-the-art algorithms.