| Solving complex optimization problems is a key to many real-world problems.From the Newtonian era,people have focused on developing the optimization methods.However,with the rapid development of society,the optimization problems nowadays have become increasingly complicated,where the traditional optimization methods are often unable to solve them in a reasonable time.In order to solve the optimization prob-lem more efficiently and more effectively,the intelligent computation method came into being.Among them,the population-based search methods,such as evolutionary algo-rithms,have been widely recognized.The so-called population-based search method is a "generate-and-test" framework that generates a set of candidate solutions iteratively over the solution space.These methods have been widely applied into many kinds of en-gineering design,job scheduling,portfolio,automatic control and other major issues re-lated to the people's livelihood,and received remarkable performance.It is particularly worth mentioning that there is also a class of individual-based search methods belonging to the intelligent computation methods,which is a "generate-and-test" framework that iteratively generates only one candidate solution in the solution space.Although such methods,such as simulated annealing and tabu search,have also received great atten-tions and successes,the research focus gradually moved towards the population-based search methods.This is mainly due to a large number of theoretical and experimental results that showing the latter effect is better than the former,especially in the multi?modal optimization problems.Why is the population-based approach better than the individual-based approach?Researchers usually believe that the individuals of a population-based approach work on a cooperative manner.They have also obtained some indirect evidences that a population-based approach with N individuals can be more effective than N indepen-dent individual-based approaches.Researchers have also tried various ways to pro-duce cooperation between individuals,which gives birth to various concrete algorithms.However,in or view,there is still no clear clue of the cooperation mechanisms that can guide the algorithm designers to propose more advanced methods.This paper attempts to explore the cooperation between individuals.We first cat-egorize the existing population-based approach into two broad types:Stochastic Re-combination and Automatic Divide-and-Conquer.Then we briefly review these two methods and discuss the different nature of them.Specifically,the method of Stochas-tic Recombination methods mainly focus on the generation stage of new individuals,which usually depend on the crossover operators to recombine the decision variables contained in the existing individuals.This recombination process can be viewed as a kind of cooperative,the essence of which is to share the potentially better components in between.As the iterations progress,the individuals will "converge" as a result of recom-bination,leading to population convergence.In order to slow down the convergence,such methods also use the mutation operators to stochastically increase the diversity of the population.Crossover and mutation operators together reflect the "stochastic"and "recombination".In turn,the Automatic Divide-and-Conquer methods are mainly about the individual selection and replacement stages,which aim to divide the popula-tion so that different individuals will search for different regions of the solution space.The cooperation is embodied in that the individual communicates with each other with their current state information to avoid the overlapping search.As individuals keep moving away from each other,the individuals in the population will "diverge" with the iterative process.Along the idea of Automatic Divide-and-Conquer,we further divide the related works into two classes,i.e.,the centralized approaches and the decentralized approaches.We also discussed their advantages and disadvantages.Specifically,the centralized methods utilize the global information of the population to divide the whole population from top to bottom.The decentralized methods share the individuals current state in-formation in the local areas and adaptively form multiple sub-populations,which is a bottom-up paradigm.Because the centralized methods involve more global informa-tion,the division of the population should be more precise.That is,the local optimal areas and the sub-populations space are expected to be mapped one-on-one.In this way,each sub-population can search from a better initial position,where the search efficiency of the algorithm can be significantly improved.At the same time,because of the need of dealing with more information,the computational cost will be relatively high.The decentralized approaches only convey the information in local areas,thus the computa-tion cost is much lighter.Besides,as the sub-populations are adaptively formed in the iterative process,the whole divide-and-conquer progress can be more robust.Mean-while,the sub-populations generated by the de-centralized methods will be unable to accurately cover the local optimal areas,but instead increase the diversity of the pop-ulation,while maintaining sufficient population diversity is also a key to a successful search.Along the above clues,we can easily find the inadequacies of the existing work.For the centralized methods,the existing works only use the distribution information of the population,which can hardly produce "accurate" decomposition.For increasing the population diversity,both Stochastic Recombination and the de-centralization methods can be applicable.However,the existing works have not been able to effectively con-nect the two together to form a controllable diversity promotion.In view of these two shortcomings,we propose a solution to each respectively along the above clues.For the centralized approaches,we can increase the accuracy of division by utilizing more information.To this end,we not only consider the distribution of population,but also consider the changes of the distribution.We found that the changes of population dis-tribution,to a certain extent,can reflect the trend of landscape.Through the analysis of population distribution changes,we can more accurately predict the local optimal regions.This constitutes the core of the first work of this thesis.For increasing the diversity of population,we propose a decentralized method that selects individuals in terms of their search behaviors rather than their spatial positions.By modeling the indi-vidual search behaviors,i.e.,the probability distribution of generating new individuals,and selecting individuals with large differences in search behaviors into the next gener-ation,we can combine the generation and selection of the new individuals organically and better control the improvement of diversity.This inspires the second work of this thesis.We teste the proposed algorithm not only on the benchmark set,but also on a spe-cific real-world optimization problem:the UAV path planning problem,which is the third work of this thesis.We focus on the case where the number of obstacles is large.We find that when the number of obstacles increases,the problem is essentially a high-dimensional highly constrained multi-modal optimization problem.We divide these difficulties into two parts:high-dimensional and high-constrained multimodal.For the latter,we use the proposed decentralized approach to solve it.For the former,we fur-ther extend the divide-and-conquer idea from the decomposition of the solution space to the division of decision variables,so as to achieve the purpose of significantly reducing the search space.Experiments show that the proposed method can greatly improve the efficiency and effectiveness of UAV path planning.Inspired by this work,we further generalize the idea of decomposition of decision variables from the UAV path planning to the general high-dimensional optimization problems.This gives birth to the last work of this thesis. |
PDF Full Text Request