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

Memetic Hill Climbing Algorithm for Minimum Linear Arrangement Problem

作　　者：陈雄峰[1,2] 陈振[3] 徐戈[1,2] CHEN Xiongfeng;CHEN Zhen;XU Ge(Department of Computer Science, Minjiang University, Fuzhou 350121, China;Fujian Provincial Key Laboratory of Information Processing and Intelligent Control, Fuzhou 350121, China;Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, Fuzhou 350108, China)

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

出　　处：《计算机科学与探索》2016年第11期1623-1632,共10页Journal of Frontiers of Computer Science and Technology

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

摘　　要：针对图最小线性排序问题优化目标的特性及其可行域总是连通的特点,提出了一个新型的Memetic爬山算法。在Memetic算法框架及其主要算子内部流程中同时结合爬山法,并在主要算子内部采用迂回爬山策略。设计可变型顶点-边-邻接交叉算子,改进使用基于贪心随机自适应搜索过程的初始解生成算法,采用动态更新等保持种群多样性策略。公认测试集的实验结果表明,与最近的两阶段模拟退火算法(two-stage simulated annealing,TSSA)和分散搜索与路径重链接算法(scatter search and path relinking,SSPR)相比,该算法具有更好的整体性能。在相近平均运行时间内,该算法近优解质量分别平均提高1.6%和2.01%,21个测试例子中13个获得当时最好的近优解,比TSSA算法多出4个,比SSPR算法多出2个。According to the properties of optimization objective of the minimum linear arrangement (MinLA) problem,and considering that the feasible region of the problem is always connected, this paper presents a new Memetichill climbing algorithm for solving the MinLA problem. It combines the framework of Memetic algorithm and the internalprocedure of its main operators with hill climbing method simultaneously, and adopts an indirect-climbing strategyin the internal procedure of its main operators. It uses a specific variable- type crossover operator named vertexedge-adjacent crossover, improves the algorithm for generating initial solutions based on greedy randomized adaptivesearch 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 comprehensive performance. In the same average running time, the proposed algorithm improves the quality of the near-optimalsolutions by an average of 1.6% and 2.01% respectively, and obtains the best near-optimal solutions at that time for 13instances from the 21 test instances, which is more 4 than TSSA and more 2 than SSPR.

关 键 词：最小线性排序 MEMETIC算法 爬山法 邻接交叉 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]