Research On Multi-Strategy Evolutionary Algorithm Combined With Neighborhood Search

In the fields of scientific research and engineering projects,many real-world problems can be solved by transforming into optimization problems.As a type of effective optimization methods,evolutionary algorithms(EAs)search the optimal solution of problems by simulating the biological evolution phenomenon in nature.EAs have some advantages,such as simple algorithmic structure,and good performance.Compared with some classic optimization methods,especially with those methods based on gradient information,EAs have little requirements on mathematical properties of the problems,and EAs even can be used in the scenario of black-box optimization.However,with the development of our society,the optimization problems become more complex,and it's harder to solve those problems with EAs accordingly.In such circumstances,the performance of EAs has been greatly challenged,and it's easy for EAs to become premature or get trapped into local optimum.In fact,as far as the algorithm performance is concerned,the factors affecting the performance of EAs can be summarized as two aspects,i.e.,the global explorative capability and the local exploitative capability.How to balance those two capabilities is the key of improving the performance of EAs.Therefore,in this dissertation,based on the purpose of balancing those two capabilities,we focus on designing the multi-strategy mechanism to enhance the performance of EAs,which is an effective way to avoid the limitation of using single strategy.Meanwhile,based on the idea of utilizing elite information of superior individuals,we further study the neighborhood search mechanism in this dissertation.The main research work and innovations of this dissertation are summarized as follows.(1)In the artificial bee colony (ABC) algorithm,the solution search equation(SSE)is used to generate new candidate solutions which has significant impact on the performance of ABC.However,some previous works have pointed out that the original SSE is good at exploration but poor at exploitation.To solve this problem,we propose a new version of SSE based on the idea of utilizing some random superior individuals,which aims to enhance the exploitative capability by using elite information of those superior individuals.Meanwhile,we design a simple but effective multi-strategy mechanism to employ both the new SSE and the original SSE simultaneously.In this mechanism,the frequency of using those two SSE is controlled by the IF-ELSE structure.Experiments are carried out on 22 well-known benchmark functions,and other three well-known improved ABC variants are included in the comparison.The experimental results show that this proposed mechanism can effectively enhance the performance of ABC.(2)In the differential evolution (DE) algorithm,the mutation strategy is an important factor affecting the algorithm performance.Usually,different type of mutation strategies is suitable for solving different type of problems.In the classic DE,however,only one mutation strategy is used to generate new candidate solutions,which highly limit the algorithm performance.To solve this problem,we propose a multi-strategy mechanism based on multiple sub-populations.In the proposed mechanism,the population is divided into three sub-populations according to their fitness values,and then each sub-population employs different type of mutation strategies.After doing these,each sub-population could exhibit different search capabilities,which is helpful to achieve a tradeoff between exploration and exploitation.Extensive experiments are carried out on 34 test functions,and 12 different EAs,including 7 DE algorithms,are involved in the comparison.The experiments show that the improved DE variant based on this mechanism can obtain better results on most of the test functions.(3)In EAs,the superior individuals often contain elite information which can be used to guide search,and the population can be pushed toward better direction to evolve by using these information appropriately.However,how to use these information is a key problem of designing relative learning mechanism.In this dissertation,we introduce a neighborhood search mechanism based on the ring topology structure.In this mechanism,all of the individuals are organized in the form of ring topology according to their indexes,and a neighborhood space of K radius is defined for each individual in which a fine search operator is performed to find better individuals.This mechanism is expected to make full use of superior individuals,and it is applied to improve the performance of ABC and DE,respectively.The experimental results show that the corresponding improved ABC and DE variants have better performance,and this mechanism can be applied to other algorithms with good applicability.(4)To further validate the performance of our proposed algorithms,three real-world optimization problems are used,i.e.,the coverage problem in wireless sensor network (CP),the parameter estimation problem for frequency-modulated sound waves (FM),and the spread spectrum radar Polly phase code design problem (SSR).To solve the CP,the proposed ABC variant in this dissertation is used which can increase the coverage rate with 2.12% in comparison with the classic ABC.For the FM and SSR,the proposed DE variant in this dissertation is used,and the accuracy of final results can be increased by 92.22% and 47.12%,respectively,when compared with the classic DE.