模拟退火蚁群算法求解二次分配问题

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (14): 34-36.

模拟退火蚁群算法求解二次分配问题

朱经纬，芮挺，蒋新胜，张金林

解放军理工大学工程兵工程学院，南京 210007

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-05-11 发布日期:2011-05-11

Simulated annealing ant colony algorithm for QAP

ZHU Jingwei，RUI Ting，JIANG Xinsheng，ZHANG Jinlin

Engineering Institute of Engineering Corps，PLA University of Science & Technology，Nanjing 210007，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-05-11 Published:2011-05-11

摘要/Abstract

摘要： 提出了一种求解二次分配问题的模拟退火蚁群算法。将模拟退火机制引入蚁群算法，在算法中设定随迭代变化的温度，将蚁群根据信息素矩阵搜索得到的解集作为候选集，根据当前温度按照模拟退火机制由候选集生成更新集，利用更新集更新信息素矩阵，并利用当前最优解对信息素矩阵进行强化。当算法出现停滞对信息素矩阵进行重置。实验表明，该算法有着高的稳定性与收敛速度。

关键词: 二次分配问题, 蚁群算法, 模拟退火, 候选集, 更新集

Abstract: A simulated annealing ant colony algorithm is presented to tackle the Quadratic Assignment Problem（QAP）.The simulated annealing method is introduced to the ant colony algorithm.By setting the temperature which changes with the iterative，after each turn of circuit，the solution set got by the colony is taken as the candidate set，the update set is gotten by accepting the solutions in the candidate set with the probability determined by the temperature.The candidate set is used to update the trail information matrix.In each turn of updating the tail information，the best solution is used to enhance the tail information.The tail information matrix is reset when the algorithm is in stagnation.The computer experiments demonstrate this algorithm has high calculation stability and converging speed.

Key words: quadratic assignment problem, ant colony algorithm, simulated annealing, candidate set, update set

朱经纬，芮挺，蒋新胜，张金林. 模拟退火蚁群算法求解二次分配问题[J]. 计算机工程与应用, 2011, 47(14): 34-36.

ZHU Jingwei，RUI Ting，JIANG Xinsheng，ZHANG Jinlin. Simulated annealing ant colony algorithm for QAP[J]. Computer Engineering and Applications, 2011, 47(14): 34-36.

[1]	史春天，曾艳阳，侯守明. 群体智能算法在图像分割中的应用综述[J]. 计算机工程与应用, 2021, 57(8): 36-47.
[2]	张松灿，普杰信，司彦娜，孙力帆. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
[3]	朱佳莹，高茂庭. 融合粒子群与改进蚁群算法的AUV路径规划算法[J]. 计算机工程与应用, 2021, 57(6): 267-273.
[4]	卜冠南，刘建华，姜磊，张冬阳. 一种自适应分组的蚁群算法[J]. 计算机工程与应用, 2021, 57(6): 67-73.
[5]	马向华，张谦. 改进蚁群算法在机器人路径规划上的研究[J]. 计算机工程与应用, 2021, 57(5): 210-215.
[6]	李壮阔，常凯旋. 合作博弈的连续蚁群算法求解[J]. 计算机工程与应用, 2021, 57(24): 198-204.
[7]	王晓光，杨培蓓. 航运物流企业数字化转型设计与效果分析[J]. 计算机工程与应用, 2021, 57(21): 241-247.
[8]	张子然，黄卫华，陈阳，章政，李梓远. 基于双向搜索的改进蚁群路径规划算法[J]. 计算机工程与应用, 2021, 57(21): 270-277.
[9]	马艳芳，李保玉，杨屹夫，冯翠英. 客户分类下生鲜配送两级路径问题与算法研究[J]. 计算机工程与应用, 2021, 57(20): 287-298.
[10]	李二超，齐款款. 改进双向蚁群算法的移动机器人路径规划[J]. 计算机工程与应用, 2021, 57(18): 281-288.
[11]	童文林，陈德旺，黄允浒，吕宜生. 结合模拟退火与规则约简的模糊系统优化方法[J]. 计算机工程与应用, 2021, 57(16): 142-150.
[12]	何雅颖，范昕炜. 改进蚁群算法在机器人路径规划中的应用[J]. 计算机工程与应用, 2021, 57(16): 276-282.
[13]	付朝晖，刘长石. 多物流中心共同配送的车辆路径问题研究[J]. 计算机工程与应用, 2021, 57(16): 291-298.
[14]	张苏英，郭宝樑，陈灵芝，刘慧贤. 双向蚁群算法的智能消防疏散图路径规划[J]. 计算机工程与应用, 2021, 57(14): 259-266.
[15]	张凯，靳鹏，崔勇. 带时间窗的多车型需求可拆分揽收配送问题[J]. 计算机工程与应用, 2021, 57(14): 281-288.