基于隶属云模型蚁群算法与LK搜索的TSP求解

提出一种求解TSP的算法,采用"问题无关的进化算法与问题相关的局部搜索相结合"的策略。采用基于云模型的蚁群算法来产生足够好的解;改进传统的LK算法,新加入5种搜索删除集与添加集元素的准则,以此细化搜索。将该算法用于求解TSPLIB中不同类型、城市数从48到33810内变化的TSP,比较该学派与其他学派算法的偏离率与运行时间,结果均显示该算法更优,有效求解了TSPLIB中的非对称TSP、哈密尔顿圈问题。

提高链式Lin-Kernighan算法性能的策略

Lin-Kernighan算法作为一种高效的组合优化问题优化算法,普遍应用于各种求解组合优化难题的算法中,尤其是旅行商问题的求解。通过对该类问题的可化简性论述,分析并建立了该类问题初始边集的概率化简模型,经实验分析方式确定了模型中的先验性概率值,并建立旅行商化简初始边集的随机算法。将该算法建立的边集作为链式Lin-Kernighan算法的参照优化边集,大幅度提高了链式Lin-Kernighan算法的求解性能,在与多种智能算法结合中取得了较好的收敛效果。

应用LK算法求解旅行商问题的混合蚂蚁算法

目前求解TSP问题效果最好的混合算法是最大最小蚂蚁算法和局部搜索算法,文章通过对几种局部搜索的灵活运用,并结合改进的接受准则接受局部优化解,提出了一种高效的混合蚂蚁算法。算法前期使用3-opt这种简单高效的局部搜索的解初始化信息素矩阵,加快收敛速度,后期采用改进的Lin-Kernighan算法生成局部优化解然后依Metropolis接受准则概率接受,有效地避免陷入局部最优,理论分析和TSPLIB中部分实例仿真结果表明,此算法能比其他改进蚁群算法具有更多优越性。

三种经典复杂网络社区结构划分算法研究

社团结构是复杂网络的重要特征之一。针对复杂网络中社团划分问题,文章给出了三种经典的社团划分算法,阐述了各种算法的基本原理,并对各算法进行了适当的分析和比较,为实际应用中社团划分算法的选择提供了参考。

Lin-Kernighan算法初始解的启发式构造策略

Lin-Kernighan算法被认为是求解旅行商问题效率最高的启发式算法之一,而初始解构造策略是影响Lin-Kernighan算法路径改进效率重要环节。以往的研究中通常采用某一种启发式策略构造初始解,但目前尚无相关研究对不同启发式构造策略在Lin-Kernighan算法中的性能给出对比。以经典的旅行商问题为对象,分析了8种常用启发式构造策略解的生成情况,得出其中最远插入法,最近插入法,最邻近法和节约算法适用于Lin-Kernighan算法的初始解构造。通过对TSPLIP中6个经典TSP实例仿真,进一步验证了这4种启发式构造策略均可以在保证解具有较高质量的情况下,显著缩小搜索空间和计算时间,提高寻优效率。此外,实验结果表明节约算法由于初始解构造效果较好,较其他启发式构造策略具有更快的收敛速度,而最近插入法在寻优率方面优于其他策略。