一种基于惩罚函数和新信息素更新方式的蚁群算法

J4 ›› 2013, Vol. 35 ›› Issue (3): 103-107.

一种基于惩罚函数和新信息素更新方式的蚁群算法

赵伟1，蔡兴盛1,2，曲慧雁1

(1.吉林农业大学信息技术学院，吉林长春 130118；2.95935部队，黑龙江双城 150100)

收稿日期:2012-05-15 修回日期:2012-09-21 出版日期:2013-03-25 发布日期:2013-03-25
基金资助:
国家自然科学基金资助项目（61106068）；吉林省科技支撑重点资助项目（20100214）；吉林省中青年科技领军人才及优秀创新团队计划项目(20121818)；吉林省自然科学基金资助项目（20101521,201115188,201215182）；吉林省科技发展计划资助项目（20100155，20100149，201101113，201101114，201101115,201201095,201201101）；长春市物联网重大科技专项（11KZ22）;长春市战略性新兴产业重大科技攻关专项项目（12XN14）

An ant colony algorithm based on
penalty function and new pheromone updating

ZHAO Wei1,CAI Xingsheng1,2,QU Huiyan1

(1.College of Information Technology,Jilin Agriculture University,Changchun 130118;
2.Troop 95935,Shuangcheng 150100,China)

Received:2012-05-15 Revised:2012-09-21 Online:2013-03-25 Published:2013-03-25

摘要/Abstract

摘要：

提出一种快速求解旅行商问题的蚁群算法。首先给出了一种新的信息素搜索模型，降低了搜索过程的复杂性，提高了路径搜索的准确性。其次通过设置惩罚函数，排除不相关路径，减小搜索范围。实验结果表明，该算法能较好地得到最优解，提高收敛速度。

关键词: 蚁群算法, 旅行商问题, 信息素更新, 惩罚函数

Abstract:

An fast ant colony algorithm solving traveling salesman problem is presented. Firstly, this paper gives a new pheromone updating model. It reduces the complexity of the search process, improves the accuracy of the route searching. Secondly, by setting penalty function, to exclude irrelevant path so that the narrow scope of the search process. Experiments show that, this algorithm can get better optimal solution, and improve the convergence speed significantly.

Key words: ant colony algorithm;traveling salesman problem;pheromone updating;penalty function

赵伟1，蔡兴盛1,2，曲慧雁1. 一种基于惩罚函数和新信息素更新方式的蚁群算法[J]. J4, 2013, 35(3): 103-107.

ZHAO Wei1,CAI Xingsheng1,2,QU Huiyan1. An ant colony algorithm based on
penalty function and new pheromone updating [J]. J4, 2013, 35(3): 103-107.

[1]	顾楚梅, 曹建军, 王保卫, 徐雨芯, . 基于蚁群参数优化的LightGBM辐射源个体识别[J]. 计算机工程与科学, 2023, 45(01): 85-94.
[2]	申晓宁, 潘红丽, 陈庆洲, 游璇, 黄遥. 引入启发信息的粒子群算法在低碳TSP中的应用[J]. 计算机工程与科学, 2022, 44(06): 1114-1125.
[3]	赵广元, 赵英. 基于改进蚁群优化算法的养殖场机器人路径规划[J]. 计算机工程与科学, 2022, 44(05): 910-915.
[4]	刘雨青, 向军, 曹守启. 基于改进蚁群算法的水下自主航行机器人路径规划[J]. 计算机工程与科学, 2022, 44(03): 536-544.
[5]	胡平志, 李泽滔. 基于改进蚁群算法的四足机器人步态规划[J]. 计算机工程与科学, 2021, 43(12): 2253-2262.
[6]	宋阿妮, 包贤哲. 精英扩散蚁群优化算法求解运输无人机三维路径规划[J]. 计算机工程与科学, 2021, 43(10): 1891-1900.
[7]	马贵平, 潘峰. 基于改进蚁群算法的物流运输路径研究[J]. 计算机工程与科学, 2020, 42(03): 523-528.
[8]	曹新亮, 王智文, 冯晶, 查敏, 王宇航. 基于改进蚁群算法的机器人全局路径规划研究[J]. 计算机工程与科学, 2020, 42(03): 564-570.
[9]	张卫祥，齐玉华，魏波，张敏，窦朝晖. 基于蚁群算法的测试用例优先排序[J]. 计算机工程与科学, 2020, 42(02): 241-249.
[10]	喻小惠1，张晶1,2，陶涛3，龚力波4，黄云明1，傅铁威1. 基于蚁群策略的无线传感器网络能耗均衡分簇算法[J]. 计算机工程与科学, 2019, 41(07): 1197-1202.
[11]	马晗，常安定，陈童，李江杰. 基于文化混合优化算法的旅行商问题求解[J]. 计算机工程与科学, 2019, 41(07): 1273-1278.
[12]	郑延斌1,2，王林林1，席鹏雪1，樊文鑫1，韩梦云1. 动态环境下改进蚁群算法的多Agent路径规划[J]. 计算机工程与科学, 2019, 41(06): 1078-1085.
[13]	吴尚智1，张文超2，佘志用1，张霞1，段超1. 利用蚁群优化算法的粗糙集属性约简方法[J]. 计算机工程与科学, 2019, 41(03): 538-544.
[14]	覃远年，梁仲华. 蚁群算法研究与应用的新进展[J]. 计算机工程与科学, 2019, 41(01): 173-184.
[15]	张立毅1，肖超2，费腾1. 基于细菌觅食的改进蚁群算法[J]. 计算机工程与科学, 2018, 40(10): 1882-1889.