一种融合模拟退火和单亲遗传的优化求解算法

An Optimal Solution Algorithm Combining Simulated Annealingand Single Parent Genetic

摘要:

度约束最小生成树是一个经典的组合优化NP难题，其在网络设计和优化中有广泛的应用。现有求解方法往往不能很好地兼顾求解效率和求解精度。为了在缩短求解时间的同时，更好地获得最优解，提出了一种结合模拟退火算法和单亲遗传算法的改进求解算法。首先，改进遗传算法中变异因子的生成方式，避免不可行解个体的产生，并且设计自适应变异率，以提高算法的求解效率。其次，针对单亲遗传算法仅有变异操作可能导致最优解个体跳跃的问题，结合模拟退火的思想，来保证解的全局最优性。最后，在具体的度约束最小生成树问题中进行了三组实验，从运行时间和最优解的情况等方面与传统单亲遗传算法进行对比，实验表明该算法在求解效率和获得最优解方面都有较好的改进效果。

Abstract:

The degree constrained minimum spanning tree is a classical NP hard problem in combinatorial optimization, which is widely used in network design and optimization. The existing solution methods can't take the efficiency and precision into account. In order to shorten the solution time and get the optimal solution better, an improved algorithm combining simulated annealing algorithm and single parent genetic algorithm is proposed. Firstly, the generation of mutation factor in genetic algorithm is improved to avoid the generation of infeasible solution individuals, and the adaptive mutation rate is designed to improve the efficiency of the algorithm. Secondly, to solve the problem that only mutation operation of single parent genetic algorithm may lead to individual jump of the optimal solution, combined with the idea of simulated annealing, to ensure the global optimization of the solution. Finally, three groups of experiments are carried out in the specific degree constrained minimum spanning tree problem, which are compared with the traditional single parent genetic algorithm in terms of running time and optimal solution. The experiment shows that the algorithm has better improvement effect in solving efficiency and obtaining optimal solution.