Abstract:  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 Memetic hill climbing algorithm for solving the MinLA problem. It combines the framework of Memetic algorithm and the internal procedure of its main operators with hill climbing method simultaneously, and adopts an indirect-climbing strategy 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 comprehensive 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.

Key words: minimum linear arrangement, Memetic algorithm, hill climbing method, adjacent crossover

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

关键词: 最小线性排序, Memetic算法, 爬山法, 邻接交叉