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

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