图最小线性排序问题的Memetic爬山算法

作     者：陈雄峰 陈振 徐戈 CHEN Xiongfeng;CHEN Zhen;XU Ge

作者机构：闽江学院计算机科学系福州350121 福建省信息处理与智能控制重点实验室福州350121 福州大学离散数学与理论计算机科学研究中心福州350108 

基　　金：国家自然科学基金No.61170308 国家自然科学基金青年科学基金No.61300156~~ 

出 版 物：《计算机科学与探索》 (Journal of Frontiers of Computer Science and Technology)

年 卷 期：2016年第10卷第11期

页      码：1623-1632页

摘      要：针对图最小线性排序问题优化目标的特性及其可行域总是连通的特点,提出了一个新型的Memetic爬山算法。在Memetic算法框架及其主要算子内部流程中同时结合爬山法,并在主要算子内部采用迂回爬山策略。设计可变型顶点-边-邻接交叉算子,改进使用基于贪心随机自适应搜索过程的初始解生成算法,采用动态更新等保持种群多样性策略。公认测试集的实验结果表明,与最近的两阶段模拟退火算法(two-stage simulated annealing,TSSA)和分散搜索与路径重链接算法(scatter search and path relinking,SSPR)相比,该算法具有更好的整体性能。在相近平均运行时间内,该算法近优解质量分别平均提高1.6%和2.01%,21个测试例子中13个获得当时最好的近优解,比TSSA算法多出4个,比SSPR算法多出2个。

主 题 词：最小线性排序 Memetic算法 爬山法 邻接交叉 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 081104[081104] 08[工学] 0835[0835] 0811[工学-水利类] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3778/j.issn.1673-9418.1601065

馆 藏 号：203195742...