计算机科学与探索2016，Vol.10Issue(11)：1624-1633,10.DOI:10.3778/j.issn.1673-9418.1601065
图最小线性排序问题的Memetic爬山算法
Memetic Hill Climbing Algorithm for Minimum Linear Arrangement Problem
摘要
Abstract
According to the properties of optimization objective of the minimum linear arrangement (MinLA) prob-lem, and considering that the feasible region of the problem is always connected, this paper presents a new Memetic hill climbing algorithm for solving the MinLA problem. It combines the framework of Memetic algorithm and the in-ternal procedure of its main operators with hill climbing method simultaneously, and adopts an indirect-climbing strate-gy in the internal procedure of its main operators. It uses a specific variable-type crossover operator named vertex-edge-adjacent crossover, improves the algorithm for generating initial solutions based on greedy randomized adaptive search procedure (GRASP), and adopts the strategies including dynamic updating for maintaining population diversity. Compared with two recent algorithms named two-stage simulated annealing (TSSA) and scatter search and path relinking (SSPR), the experimental results on the acknowledged test suite show that the proposed algorithm has better compre-hensive performance. In the same average running time, the proposed algorithm improves the quality of the near-optimal solutions by an average of 1.6%and 2.01%respectively, and obtains the best near-optimal solutions at that time for 13 instances from the 21 test instances, which is more 4 than TSSA and more 2 than SSPR.关键词
最小线性排序/Memetic算法/爬山法/邻接交叉Key words
minimum linear arrangement/Memetic algorithm/hill climbing method/adjacent crossover分类
信息技术与安全科学引用本文复制引用
陈雄峰,陈振,徐戈..图最小线性排序问题的Memetic爬山算法[J].计算机科学与探索,2016,10(11):1624-1633,10.基金项目
The National Natural Science Foundation of China under Grant No.61170308(国家自然科学基金) （国家自然科学基金）
the National Natural Science Foundation for Young Scholars of China under Grant No.61300156(国家自然科学基金青年科学基金) （国家自然科学基金青年科学基金）
