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

摘要：

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

关键词：最小生成树、遗传算法、模拟退火算法、度约束

所属期刊栏目：29

分类号：TP3(计算技术、计算机技术)

资助基金：国家自然科学基金项目61104004,61170258,U1806201,61671261

在线出版日期：2021-03-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：146-149