Abstract: In order to improve the quality of the solution in solving Quadratic Assignment Problem (QAP), an effective Max-Min Ant System (MMAS) was designed. Firstly, by using optimal iteration idea, the location and its corresponding task were selected randomly from the current optimal tour as the initial value of next iteration, so as to enhance the effectiveness of each searching in MMAS. Secondly, in order to increase the purpose of the search in every step, the incremental value of target function after adding new task was used as the heuristic factor to guide effectively the state transition. Then, the pheromone was updated by using the multi-elitist strategy so that it could increase the diversity of the solution. And an effective double-mutation technique was designed to improve the quality of solution and accelerate the algorithm convergence speed. Finally, a large number of data sets from QAPLIB were experimented. The experimental result shows that the proposed algorithm is significantly better than other algorithms in accuracy and stability on solving quadratic assignment problem.

Key words: Quadratic Assignment Problem (QAP), optimal iteration, Max-Min Ant System (MMAS), double-mutation, heuristic factor

摘要： 为提高二次指派问题的求解质量,设计了一个有效的最大最小蚂蚁求解算法。首先,运用最优迭代思想,让每只蚂蚁从当前最优路径中随机地选择位置及其对应的任务作为下一轮迭代的初始值,增强每轮搜索的有效性;其次,采用加入新任务后目标值的增量作为启发式因子来引导状态转移,增加每步搜索的目的性;然后,应用多精英策略来进行信息素更新,增加解的多样性;并设计有效的双重变异技术来提高解的质量,提高算法的收敛速度;最后,应用QAPLIB数据集进行了大量实验,结果表明:该算法在二次指派问题的求解质量和稳定性上显著优于其他算法。

关键词: 二次指派问题, 最优迭代, 最大最小蚂蚁算法, 双重变异, 启发因子