基于自动分治的智能优化方法及其应用研究

发布时间：2018-05-02 08:52

本文选题：计算智能 + 基于种群的搜索　；参考：《中国科学技术大学》2017年博士论文

【摘要】：求解复杂优化问题是解决许多实际问题的关键步骤。从牛顿时代开始,人们就已经开始关注于优化问题的求解方法。然而,随着社会的飞速发展,当今世界中的优化问题已经越来越复杂,传统的优化方法常常无法在合理时间内进行求解。为了更快更好地求解优化问题,智能优化方法应运而生。其中,基于种群的搜索方法,如演化算法类,已经得到了广泛的认可。所谓基于种群的搜索方法,即是在问题解空间迭代式地"生成-测试"一组候选解。这类方法已经被广泛应用于各类工程设计、作业调度、投资组合和自动控制等关系国计民生的重大项目中,并获得了令人瞩目的成绩。特别值得一提的是,相对于基于种群的搜索方法,在智能优化方法中还存在着一类基于个体的搜索方法,即是在问题解空间迭代式地"生成-测试"一个候选解。诚然这类方法,如模拟退火、禁忌搜索等,曾经也获得了巨大的关注以及成功,但研究的热潮还是逐渐在朝基于种群的搜索方法转移。这主要是大量的理论和实验结果表明后者效果优于前者,特别是在一类叫做多极值优化的问题类上。然而,何以基于种群的方法要比基于个体的方法更好?研究人员普遍认为这是基于种群的方法中多个个体之间的某种合作机制在起作用,并也得到了一些间接的证据,如一个种群大小为N的基于种群的方法可以比N个独立运行的基于个体的方法表现更好。研究者也尝试了各种方式来产生个体间的合作,并得到了许多优秀的算法。然而在我们看来,目前仍然没有一个关于合作机制的清晰路线来引导算法设计者提出更先进的方法。本文试图对个体间的合作机制进行一些探索。我们首先将现有的基于种群的方法梳理为两大类:随机重组和自动分治。然后我们简要回顾以及对比这两类方法,讨论这两类方法在设计思路上的本质不同。具体来说,随机重组类方法主要是关注于新个体的产生阶段,其利用交叉、变异的方式将已有个体中包含的变量进行重新组合。这个重新组合的过程就是一种合作机制,其本质在于共享一些潜在较好的决策变量值。随着迭代的进行、个体会由于不断重组而"趋同"、导致种群收敛。为了延缓收敛,该类方法还利用了变异这一操作来随机地增加种群中的多样性。交叉和变异操作合起来就是其随机、重组的思想体现。反过来,自动分治类方法主要是关于个体的选择、替换阶段,其旨在对种群进行划分,使得不同个体分别搜索解空间不同的区域。其合作机制体现在:个体之间互相传递各自的当前状态信息,避免搜索区域重叠。由于个体互相"排斥",该类方法中种群的成分会随着迭代过程而"趋异"。接着,我们沿着自动分治的思想,进一步将相关工作划分为中心化方法和去中心化方法,并提出各自的优势和劣势。具体来说,中心化自动分治方法旨在利用种群的全局信息,自顶向下地对整个种群进行划分;而去中心化自动分治方法则在局部区域共享个体当前状态信息,自适应地形成多个子种群,这是一种自底向上地划分方式。由于中心化方法利用了更多更全面的信息,其对种群的划分应该更加精准,即子种群和解空间局部极值区域能够一一对应。这样,每个子种群能从一个比较好的初始位置开始搜索,算法总的搜索速率会显著提高。同时,由于其需要处理的信息更多,计算代价也比较高。而去中心化方法只在局部区域传递信息进行合作,计算更加轻便,而且由于子种群是在迭代过程中自适应生成的,可以更佳鲁棒。但同时,去中心化方法生成的子种群无法精确覆盖局部极值区域,而是通过增加种群多样性的方式来逐渐搜索解空间。而维持足够的种群多样性也是搜索成功的关键要素之一。沿着以上思路,我们不难发现现有工作的不足之处。对于中心化方法,已有工作只利用了种群的分布信息来进行划分,无法做到子种群和局部极值区域一一对应。而对于增加种群多样性,随机重组和去中心化方法均可。但现有工作并未能有效地将两者连接起来,形成一种可控地多样性提升方式。针对这两者缺点,我们沿着以上思路分别提出了改进方法。对于中心化方法,我们可以通过增加信息的使用来提升划分的精确性。为此,我们不仅利用了种群的分布信息,还利用了种群分布的变化信息来帮助划分子种群。我们发现种群分布的变化信息在一定程度上实际反应了解空间地形变化的趋势。通过对种群分布变化的分析,我们能更加快速地找到局部极值所在区域。这构成了本文第一个工作的核心贡献。对于增加种群多样性,我们提出了一种按搜索行为而非个体位置距离来进行候选解选择的去中心化方法。通过对搜索行为(可能产生新个体的概率分布)进行直接建模,我们能够将新个体的产生和选择有机地结合在一起,使得种群的多样性更容易控制。这是本文第二个工作的主要想法。我们不仅在基准测试问题集上测试了我们提出的算法,还将其应用于一个具体的现实优化问题:无人机路径规划问题。这是本文的第三个工作。我们重点关注任务场景中具有大量障碍的无人机路径规划问题。我们发现,当障碍数量增加时,该问题本质上是一个高维、高约束的多极值优化问题。我们将这些难点分为两部分:高维度和高约束多极值。对于后者,我们利用提出的去中心化方法进行求解。对于前者,我们进一步将分治思想从候选解划分拓展到了决策变量的划分,从而达到显著降低搜索空间的目的。实验证明,我们提出的该方法可以极大地提升无人机路径规划的求解效率和性能。受到该工作的启发,我们将按决策变量分治的思想进一步从该无人机路径规划问题泛化到了一般性的高维优化问题上。这构成了本文的最后一个工作。
[Abstract]:Solving complex optimization problems is the key step to solve many practical problems. Since the Newton era, people have begun to pay attention to the optimization problem solving methods. However, with the rapid development of society, the optimization problems in the world are becoming more and more complex, and the traditional optimization methods are often unable to be solved in a reasonable time. In order to solve the optimization problem faster and better, intelligent optimization methods emerge as the times require. Among them, the population based search method, such as the evolutionary algorithm class, has been widely recognized. The so-called population based search method is a group of candidate solutions, which are iteratively "generating and testing" in the problem solution space. In the major projects related to the national economy and the people's livelihood, such as engineering design, job scheduling, investment portfolio and automatic control, it has gained remarkable achievements. It is particularly worth mentioning that there is a kind of individual based search method in intelligent optimization method, that is, "birth" in the solution space iteratively relative to the population based search method. It is true that such methods, such as simulated annealing, tabu search and so on, have also gained great attention and success, but the upsurge of research is gradually moving towards a population based search method. This is mainly a large number of theoretical and experimental results that show that the latter is better than the former, especially in a class called multipole. However, why is the population based approach better than the individual based approach? Researchers generally believe that this is a kind of cooperative mechanism among a number of individuals in a population based approach, and some indirect evidence, such as a population based method of a population size of N, can be compared to N The individual based approach performs better. The researchers have also tried various ways to produce inter individual cooperation and have obtained many excellent algorithms. However, in our view, there is still no clear route to the cooperation mechanism to guide the algorithm designers to bring forward more advanced methods. The cooperation mechanism is explored. We first sort out the existing population based methods into two categories: random and automatic division. Then we briefly review and compare the two methods, and discuss the differences in the design ideas of these two methods. In particular, the random reorganization method is mainly concerned with the production of new individuals. In the birth stage, it uses cross and mutation to recombine the variables contained in the existing individual. This regrouping process is a cooperative mechanism whose essence is to share some potential better decision variables. As the iteration proceeds, the experience is "converging" by continuous reorganization, leading to the convergence of the population. Convergence, this kind of method also uses the mutation operation to randomly increase the diversity in the population. The intersection and mutation operation is the idea of random and regrouping. In turn, the method of automatic divide and conquer is mainly about the selection and replacement of the individual, which is designed to divide the group, so that the different individuals search for the solution space respectively. In different regions, the cooperation mechanism is embodied in that the individual transfers their current state information to each other and avoids the overlap of the search areas. As the individual "repels" each other, the composition of the population will "be different" with the iterative process. Then, we further divide the relevant work into a centralization method along the idea of automatic divide and treatment. In particular, the centralization automatic divide and conquer method aims to divide the whole population from the top to the bottom by using the global information of the population, while the centralization automatic divide and conquer method shares the present state information of the individual in the local area and adaptively forms a number of subpopulations. Because the centralization method uses more and more comprehensive information, the division of the population should be more accurate, that is, the subpopulation and the spatial local extremum area can correspond one by one. In this way, each subpopulation can start searching from a better initial position, and the total search rate of the algorithm will be significantly improved. At the same time, the computational cost is higher because of the more information it needs to deal with, and the de centralization method only transfers information in the local area to cooperate, and the calculation is more portable. And because the subpopulation is self-adaptive in the iterative process, it can be better. At the same time, the subpopulation generated by the centralization method can not accurately cover the Bureau. It is one of the key elements of the search success to search the solution space gradually by increasing the diversity of the population, and maintaining sufficient population diversity is also one of the key elements of the search success. It is impossible to make a one-to-one correspondence between the subpopulation and the local extreme value region. But for the increase of population diversity, random recombination and de centralization, but the existing work does not effectively connect the two together to form a controllable diversity promotion method. Method. For the centralization method, we can improve the accuracy of the partition by increasing the use of information. Therefore, we not only use the distribution information of the population, but also use the change information of the population distribution to help divide the subpopulation. We find that the variation information of the population distribution is in a certain degree to understand the spatial terrain to some extent. The trend of change. By analyzing the variation of population distribution, we can find the region of the local extremum more quickly. This constitutes the core contribution of the first work in this paper. For the increase of population diversity, we propose a de centralization method for selecting the candidate solutions according to the search behavior rather than the individual location distance. We can directly model the search behavior (the probability distribution of new individuals). We can combine the generation and selection of new individuals organically to make the diversity of the population more easily controlled. This is the main idea of the second work in this paper. It is applied to a specific realistic optimization problem: the UAV path planning problem. This is the third work of this paper. We focus on the problem of UAV path planning with a large number of obstacles in the task scene. We find that when the number of obstacles is increased, the problem is essentially a high dimension, high constraint multipole optimization problem. These difficulties are divided into two parts: high dimension and high constraint multi extremum. For the latter, we use the proposed de centralization method to solve the problem. For the former, we further extend the divide and conquer idea from the candidate solution division to the decision variable division, so as to achieve the goal of significantly reducing the search space. The method can greatly improve the efficiency and performance of the UAV path planning. Inspired by this work, we will further generalize the problem of the UAV path planning to the general high dimensional optimization problem according to the idea of the decision variables dividing and treatment. This constitutes the last work of this paper.

【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TP301.6

【相似文献】