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

doi:10.11772/j.issn.1001-9081.2014.01.0199

计算机应用 ›› 2014, Vol. 34 ›› Issue (1): 199-203.DOI: 10.11772/j.issn.1001-9081.2014.01.0199

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

牟廉明¹,²,戴锡笠¹,李坤¹,贺灵悦¹

1. 内江师范学院数学与信息科学学院,四川内江 641100;
2. 四川省高等学校数值仿真重点实验室(内江师范学院),四川内江 641100

收稿日期:2013-07-22 修回日期:2013-09-08 出版日期:2014-01-01 发布日期:2014-02-14
通讯作者: 牟廉明
作者简介:牟廉明(1971-),男,重庆人,教授,CCF会员,主要研究方向:计算智能、机器学习、数据挖掘;戴锡笠(1990-),男,浙江台州人,主要研究方向:计算智能;李坤(1993-),男,四川巴中人,主要研究方向:计算智能;贺灵悦(1992-),男,四川江油人,主要研究方向:计算智能。〖JP〗
基金资助:
国家自然科学基金资助项目;四川省教育厅自然科学重点项目;内江师范学院自然科学重点项目;内江师范学院大学生创新性实验计划项目

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

MOU Lianming¹,²,DAI Xili¹,LI Kun¹,HE Lingrui¹

1. College of Mathematics and Information Science, Neijiang Normal University, Neijiang Sichuan 641100, China;
2. Key Laboratory of Numerical Simulation of Sichuan Province (Neijiang Normal University), Neijiang Sichuan 641100, China

Received:2013-07-22 Revised:2013-09-08 Online:2014-01-01 Published:2014-02-14
Contact: MOU Lianming

摘要/Abstract

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

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

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

中图分类号:

TP301.6

牟廉明戴锡笠李坤贺灵悦. 求解二次指派问题的最优迭代最大最小蚂蚁算法[J]. 计算机应用, 2014, 34(1): 199-203.

MOU Lianming DAI Xili LI Kun HE Lingrui. Optimal iterative max-min ant system for solving quadratic assignment problem[J]. Journal of Computer Applications, 2014, 34(1): 199-203.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics