求解二次指派问题的最优迭代最大最小蚂蚁算法  

Optimal iterative max-min ant system for solving quadratic assignment problem

作　　者：牟廉明[1,2] 戴锡笠[1] 李坤[1] 贺灵悦[1] 

机构地区：[1]内江师范学院数学与信息科学学院,四川内江641100 [2]四川省高等学校数值仿真重点实验室(内江师范学院),四川内江641100

出　　处：《计算机应用》2014年第1期199-203,共5页journal of Computer Applications

基　　金：国家自然科学基金资助项目(10872085);四川省教育厅自然科学重点项目(13ZA0008);内江师范学院自然科学重点项目(12NJZ03);内江师范学院大学生创新性实验计划项目(X201205)

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]