回溯搜索算法的研究及改进

发布时间：2018-03-21 02:26

本文选题：数值优化　切入点：回溯搜索算法　出处：《山东大学》2017年硕士论文　论文类型：学位论文

【摘要】：优化是应用数学中的一个重要的研究领域,基于自然仿生的优化算法已经成为人工智能和计算机科学的重要研究方向。回溯搜索算法(BSA)是一种新颖的进化算法,其采用一种独特的变异和交叉策略,能够利用种群的历史信息引导种群进化,保证了全局搜索能力和局部探索能力的平衡。然而,种群历史信息在一定水平上影响算法的收敛速度。因此,本文提出了由最优个体引导的回溯搜索算法以及混合序列二次规划算法的回溯搜索算法。本文的具体工作概括如下:1.提出了一种求解数值优化问题的改进的回溯搜索算法:由最优个体引导的回溯搜索算法。为了提高算法收敛速度和求解精度,本文设计了一种由最优个体引导的算子。种群进化前期,由历史信息引导的种群进化策略能够保证算法的全局搜索能力。种群进化后期,算法采用最优个体引导的进化算子提高局部搜索能力。因此,算法的全局勘探和局部搜索能力达到相对平衡。该方法在CEC-2013测试集上进行测试得到的结果表明,它能够有效求解基准函数并且提高收敛速度。2.提出了一种针对数值优化问题的基于回溯搜索算法的混合算法:结合序列二次规划的回溯搜索算法。该算法将回溯搜索算法作为全局搜索技术,序列二次规划算法作为局部探索工具。为了提高算法的搜索效率和收敛速度,定义了搜索阶段的迭代前期和后期。该算法在迭代前期结合序列二次规划算法并以一定概率调用,尽早引导种群向更优方向进化。该算法在CEC-2005和CEC-2013测试集上进行测试,实验结果表明该方法能够求解基准测试函数,提供更加精确的结果。
[Abstract]:Optimization is an important research field in applied mathematics. Optimization algorithm based on natural bionics has become an important research direction of artificial intelligence and computer science. Backtracking search algorithm (BSAA) is a novel evolutionary algorithm. It adopts a unique mutation and crossover strategy, which can use the historical information of the population to guide the evolution of the population and ensure the balance between the global search ability and the local exploration ability. Population history information affects the convergence rate of the algorithm at a certain level. In this paper, a backtracking search algorithm guided by the optimal individual and a backtracking search algorithm based on mixed sequence quadratic programming are proposed. The specific work of this paper is summarized as follows: 1. An improved backtracking algorithm for solving numerical optimization problems is proposed. Search algorithm: backtracking search algorithm guided by the optimal individual. In order to improve the convergence speed and accuracy of the algorithm, In this paper, an operator guided by the optimal individual is designed. In the early stage of population evolution, the strategy of population evolution guided by historical information can guarantee the global searching ability of the algorithm. The algorithm uses the evolutionary operator guided by the optimal individual to improve the local search ability. Therefore, the global exploration and local search ability of the algorithm reach a relative balance. The results obtained by the method on the CEC-2013 test set show that, It can effectively solve the benchmark function and improve the convergence speed. 2. A hybrid algorithm based on backtracking search algorithm for numerical optimization problems is proposed: a backtracking search algorithm based on sequential quadratic programming. Search algorithm as a global search technology, Sequential quadratic programming (SQP) is used as a local exploration tool. In order to improve the search efficiency and convergence speed of the algorithm, the pre-iteration and late-stage of the search phase are defined. The algorithm combines the sequential quadratic programming algorithm with the sequential quadratic programming algorithm in the early iteration period and is called with a certain probability. The algorithm is tested on CEC-2005 and CEC-2013 test sets. The experimental results show that the method can solve the benchmark function and provide more accurate results.
【学位授予单位】：山东大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18

【相似文献】