一种融合模拟退火和单亲遗传的优化求解算法
来源：计算机测量与控制杂志2021年第1期北京时间：
作者：王海红,李林,刘莉
单位：青岛科技大学 信息科学技术学院
摘要：度约束最小生成树是一个经典的组合优化NP难题，其在网络设计和优化中有广泛的应用。现有求解方法往往不能很好地兼顾求解效率和求解精度。为了在缩短求解时间的同时，更好地获得最优解，提出了一种结合模拟退火算法和单亲遗传算法的改进求解算法。首先，改进遗传算法中变异因子的生成方式，避免不可行解个体的产生，并且设计自适应变异率，以提高算法的求解效率。其次，针对单亲遗传算法仅有变异操作可能导致最优解个体跳跃的问题，结合模拟退火的思想，来保证解的全局最优性。最后，在具体的度约束最小生成树问题中进行了三组实验，从运行时间和最优解的情况等方面与传统单亲遗传算法进行对比，实验表明该算法在求解效率和获得最优解方面都有较好的改进效果。
关键词：最小生成树;遗传算法;模拟退火算法;度约束
基金资助：国家自然科学(61104004,61170258,U1806201和61671261)。
