智能优化算法表型空间的动态行为学分析与应用

发布时间：2018-03-08 16:45

本文选题：智能优化算法　切入点：动态行为学分析　出处：《中国科学技术大学》2017年博士论文　论文类型：学位论文

【摘要】：智能优化算法是一类通过模拟自然界生物的进化或集群行为来实现问题求解的元启发式算法(meta-heuristic algorithms),擅长求解研究和工程中遇到的各类复杂优化问题。近二十年来,智能优化领域经历了一个快速发展的时期,涌现了大批新的算法模型,同时在一些复杂应用问题的求解上取得了瞩目的成果。然而,随着算法种类和数量的日益增多,研究和技术人员在求解具体问题时,往往面临算法选择的困难。同时,由于智能优化算法由不同的算子(parameters)组合而成,算子之间的相互作用关系是错综复杂的,即使是同种算法,不同的算子组合也会产生截然不同的优化结果,因此算子调优(parameter tuning)也是该领域研究的热点和难点。本论文主要从智能优化算法的动态行为学分析入手,试图从表型空间研究不同算法在优化过程中表现出的行为差异,以更好地理解不同的算法或算子,为算法选择和算子调优提供指导和帮助。具体而言,本论文的研究工作和成果主要包含如下几个方面:[1]提出了一类新的基于群体可进化性实现表型空间算法行为定量分析的方法。通过将算法的行为与优化问题的特性相结合,提出了三个群体可进化性的度量指标,作为一种新的动态适应度景观分析(Fitness Landscape Analysis,简称FLA)方法,并通过理论和实验相结合的方式,详细分析了各指标的意义和合理性。通过黑盒实值优化问题(black-box numerical optimization problem)上的算法选择任务,对所提指标的有效性进行了实验验证,统计结果表明,本论文的方法取得了较高的准确率,同时显著降低了整个过程的计算代价;[2]提出了一种新的基于统计竞赛(statistical racing)的算子调优方法。通过分析现有算子调优方法的不足,提出了基于Kruskal-Wallis测试的统计竞赛方法KW-Race,随后又合理地融入算法收敛速度的指标,形成了 Fast KW-Race框架,在显著提升算子调优效率的同时,保持了结果在测试问题上较高的准确率,更好地满足了研究和工程人员期望既快又好地解决复杂优化问题上算子调优的需求;[3]研究方法在工程实例中的应用。通过一个工程中遇到的优化设计问题,验证上述两种新方法在NP-hard实数优化场景下的具体表现,结果表明我们的方法无论在算法选择还是算子调优方面,均表现出优于原有方法的性能和稳定性,具有普适的应用价值。本论文定义的基于群体可进化性的指标为设计更加实用的适应度景观分析方法提供了新的方向。本论文提出的KW-Race和Fast KW-Race框架,对定性和定量的算子均适用,是一种通用的算子调优框架。本论文的工作对更加合理有效地应用智能优化算法具有一定的推动作用。
[Abstract]:Intelligent optimization algorithm is a meta-heuristic algorithm that simulates the evolution or cluster behavior of natural organisms. It is good at solving all kinds of complex optimization problems in research and engineering. The field of intelligent optimization has experienced a period of rapid development, a large number of new algorithm models have emerged, and at the same time, great achievements have been made in solving some complex application problems. However, with the increasing number and variety of algorithms, Researchers and technicians often face the difficulty of selecting algorithms when solving specific problems. At the same time, because the intelligent optimization algorithm is composed of different operators, the interaction between operators is complicated, even the same algorithm. Different combinations of operators also produce very different optimization results, so operator tuning parameter is also a hot and difficult point in this field. This paper mainly starts with the dynamic behavior analysis of intelligent optimization algorithms. This paper attempts to study the behavior differences of different algorithms in the optimization process from phenotypic space, in order to better understand different algorithms or operators, and to provide guidance and help for algorithm selection and operator tuning. The research work and achievements of this thesis mainly include the following aspects: [1] A new method for quantitative analysis of phenotypic spatial algorithm based on population evolution is proposed. By combining the behavior of the algorithm with the characteristics of optimization problem, As a new dynamic fitness Landscape analysis (FLA) method, three measures of population evolutionability are proposed, which are combined with theory and experiment. The significance and rationality of each index are analyzed in detail. Through the algorithm selection task on black-box numerical optimization problem (black-box numerical optimization problem), the validity of the proposed index is verified experimentally. The statistical results show that, The method in this paper has achieved high accuracy and significantly reduced the computational cost of the whole process. [2] A new operator tuning method based on statistical statistics is proposed. A statistical competition method based on Kruskal-Wallis test, KW-Race-based, is proposed, and then the index of convergence rate of the algorithm is reasonably incorporated into the framework of Fast KW-Race, which can significantly improve the efficiency of operator tuning and maintain the high accuracy of the test results. It can better meet the needs of the researchers and engineers to solve the optimization problem of complex optimization quickly and well. [3] the application of the research method in engineering example. Through the optimization design problem encountered in a project, The performance of the above two new methods in the NP-hard real number optimization scenario is verified. The results show that our method is superior to the original method in performance and stability both in algorithm selection and operator tuning. The index defined in this paper based on population evolution provides a new direction for the design of more practical landscape fitness analysis methods. In this paper, KW-Race and Fast KW-Race frameworks are proposed. It is suitable for both qualitative and quantitative operators and is a general operator optimization framework. The work of this paper can promote the more rational and effective application of intelligent optimization algorithm.
【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TP18

【相似文献】