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

• 作者: 徐戈 陈振 陈雄峰
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 最小线性排序 Memetic算法 爬山法 邻接交叉
• 年，卷（期）: 2016,（11）
• 所属期刊栏目: 人工智能与模式识别
• 页码范围: 1624-1633
• 页数: 10页
• 分类号: TP18
• 字数: 9063字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.1601065

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈雄峰	闽江学院计算机科学系	16	32	5.0	5.0
3	徐戈	闽江学院计算机科学系	12	29	3.0	5.0
5	陈振	福州大学离散数学与理论计算机科学研究中心	5	1	1.0	1.0