蚁群算法研究与应用的新进展

摘要/Abstract

摘要：

蚁群算法是一种源于大自然生物界的仿生进化算法，具有自组织性、正反馈性、较强的鲁棒性和分布式计算等特性，且易于与其它算法相结合，在众多的复杂组合优化领域中有着广阔的应用前景。首先对蚁群算法的理论及其重要参数进行了阐述，继而分析了其在参数优化和智能融合方面的改进与应用；然后对其在车间作业调度问题、车辆路径问题、图像处理、电力系统优化等领域的应用进展进行了综述；最后对其理论研究和应用领域可能存在的问题及对策进行了探讨和展望。

关键词: 蚁群算法, 复杂组合优化, 算法改进, 应用进展

Abstract:

The ant colony algorithm is a bionic evolutionary algorithm derived from the natural biological world. It has the characteristics of selforganization, positive feedback, strong robustness, and distributed computing, and it is easy to combine with other algorithms. it is therefore of great applied value in the complex combinatorial optimization field. We firstly introduce the theory of the ant colony algorithm and its important parameters. Then we analyze the improvement and applications in parameter optimization and intelligent fusion. Thirdly, we summarize the progress of applications in jobshop scheduling problem, vehicle routing problem, image processing and electric power system optimization. Finally, we discuss the potential problems in research work in theory and application domain, as well as some possible countermeasures.

Key words: ant colony algorithm, complex combinatorial optimization, algorithm improvement, application progress

覃远年，梁仲华. 蚁群算法研究与应用的新进展[J]. 计算机工程与科学.

QIN Yuannian，LIANG Zhonghua.

New progress of the ant colony algorithm

in research and applications

#br#

[J]. Computer Engineering & Science.

参考文献［86］

［1］	Bonabeau E,Dorigo M,Theraulaz G.Inspiration for optimization from social insect behaviour［J］.Nature,2000,406(6791):3942.
［2］	Dorigo M,Maniezzo V,Colorni A.Ant system:Optimization by a colony of cooperating agents［J］.IEEE Transactions on Systems Man and Cybernetics, Part B Cybernetics,1996,26(1):113.
［3］	Randall M,Lewis A.A parallel implementation of ant colony optimization［J］.Journal of Parallel & Distributed Computing,2002,62(9):14211432.
［4］	Escario J B,Jimenez J F,GironSierra J M.Ant colony extended:Experiments on the travelling salesman problem［J］.Expert Systems with Applications,2015,42(1):390410.
［5］	Duan Haibin,Wang Daobo,Zhu Jiaqiang,et al.Development on ant colony algorithm theory and its application［J］.Control and Decision,2004,19(12):13211326.(in Chinese)
［6］	Duan Haibin.Ant colony algorithms:Theory and applications［M］.Beijing:Science Press,2005.(in Chinese)
［7］	Dorigo M,Gambardella L M.Ant colony system:A cooperative learning approach to the traveling salesman problem［J］.IEEE Transactions on Evolutionary Computation,1997,1(1):5366.
［8］	Juang C F,Chang P H.Recurrent fuzzy system design using eliteguided continuous ant colony optimization［J］.Applied Soft Computing,2011,11(2):26872697.
［9］	Yousefikhoshbakht M,Didehvar F,Rahmati F.An efficient solution for the VRP by using a hybrid elite ant system［J］.International Journal of Computers Communications & Control,2014,9(3):340347.
［10］	Liu Guobao,Zhang Jie.Dynamic schedule method based on improved rolling time domain optimization strategy［J］.Journal of Mechanical Engineering,2013,49(14):182190.(in Chinese)
［11］	Li M P,Yao M.An optimized ant system for clustering with elitist ant and local search［C］∥Proc of ITM Web of Conferences,2016:Article No.05011.
［12］	Yousefikhoshbakht M,Didehvar F,Rahmati F.A combination of modified tabu search and elite ant system to solve the vehicle routing problem with simultaneous pickup and delivery［J］.Journal of Industrial and Production Engineersing,2014,31(2):6575.
［13］	Stützle T,Hoos H.Improvements on the antsystem:Introducing the MAXMIN Ant System［M］∥Artificial Neural Nets and Genetic Algorithms.Vienna:Springer Vienna,1998.
［14］	Bai J,Yang G K,Chen Y W,et al.A model induced maxmin ant colony optimization for asymmetric traveling salesman problem［J］.Applied Soft Computing,2013,13(3):13651375.
［15］	AIShihabi S. A hybrid of maxmin ant system and linear programming for the kcovering problem［J］.Computers & Operations Research,2016,76:111.
［16］	AIShihabi S T,Aldurgam M M.A maxmin ant system for the financebased scheduling problem［J］.Computers & Industrial Engineering,2017,110:264276.
［17］	Sujaree K,Kitjaruwankul S,Boonamnaj P,et al.Transmembrane helix assembly by maxmin ant system algorithm［J］.Chemical Biology & Drug Design,2015,86(6):13601372.
［18］	Parsa N R,Karimi B,Husseini S M M.Minimizing total flow time on a batch processing machine using a hybrid maxmin ant system［J］.Computers & Industrial Engineering,2016,99(C):372381.
［19］	Gambardella L M,Dorigo M.Solving symmetric and asymmetric TSPs by ant colonies［C］∥Proc of IEEE International Conference on Evolutionary Computation,1996:622627.
［20］	Wang Fang,Li Meian,Duan Weijun.Cloud computing task scheduling based on dynamically adaptive ant colony algorithm［J］.Journal of Computer Applications,2013,33(11):31603162.(in Chinese)
［21］	Zhang C T,Zhao A X.Using adaptive ant colony algorithm optimized BP neural network to identify the DGA fault［C］∥
	Proc of 2013 IEEE International Conference on Region 10(Tencon 2013),2013:14.
［22］	Lei X S,Guo K X.The model identification for small unmanned aerial rotorcraft based on adaptive ant colony algorithm［J］.Journal of Bionic Engineering,2012,9(4):508514.
［23］	Lin Y,Gong Y J,Zhang J.An adaptive ant colony optimization algorithm for constructing cognitive diagnosis tests［J］.Applied Soft Computing,2017,52:113.
［24］	Yang Q,Chen W N,Yu Z,et al.Adaptive multimodal continuous ant colony optimization［J］.IEEE Transactions on Evolutionary Computation,2017,21(2):191205.
［25］	Ding Jianli,Chen Zengqiang,Yuan Zhuzhi.On the combination of genetic algorithm and ant algorithm［J］.Journal of Computer Research and Development,2003,40(9):13511356.(in Chinese)
［26］	Ciornei I,Kyriakides E.Hybrid ant colonygenetic algorithm(GAAPI) for global continuous optimization［J］.IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics,2012,42(1):23445.
［27］	Deng Boyu,Zhao Shanghong,Hou Rui,et al.Research for resources scheduling of relay satellite system with hybrid links based on fusion algorithm of genetic and ant colony［J］.Infrared and Laser Engineering,2015,44(7):22112217.(in Chinese)
［28］	Bamdad K,Cholette M E,Guan L,et al.Ant colony algorithm for building energy optimisation problems and comparison with benchmark algorithms［J］.Energy & Buildings,2017,154：404414.
［29］	Cao Qingkui,Zhao Fei.Port trucks route optimization based on GAACO［J］.Systems EngineeringTheory & Practice,2013,33(7):18201828.(in Chinese)
［30］	Dai Y V,Lou Y S,Lu X.A task scheduling algorithm based on genetic algorithm and ant colony optimization algorithm with multiQoS constraints in cloud computing［C］∥Proc of the 2015 7th International Conference on Intelligent HumanMachine Systems and Cybernetics,2015:428431.
［31］	Wang D,Shao X,Liu S.Assembly sequence planning for reflector panels based on genetic algorithm and ant colony optimization［J］.International Journal of Advanced Manufacturing Technology,2017,91(14):987997.
［32］	Liang H,Ge Y F.GACAVMP:Virtual machine placement scheduling in cloud computing based on genetic ant colony algorithm approach［C］∥Proc of 2015 12th International Conference on Ubiquitous Intelligence and Computing and 2015 IEEE 12th International Conference on Autonomic and Trusted Computing and 2015 IEEE
15	th International Conference on Scalable Computing and Communications and ITS Associated Workshops,2016:10081015.
［33］	Dong G,Fu X,Li H,et al.Cooperative ant colonygenetic algorithm based on spark［J］.Computers & Electrical Engineering,2016,60(C):6675.
［34］	Hu Chunde,Zhu Yanjun,Gao Suixiang.A hybrid algorithm based on artificial immune algorithm and ant colony algorithm for solving traveling salesman problem［J］.Computer Engineering and Applications,2004,40(34):6063.(in Chinese)
［35］	Wan Fang,Qiu Lin,Huang Qiang.Application of ant colony optimization based on immune evolutionary algorithm to optimal reservoir water supply dispatching［J］.Journal of Hydroelectric Engineering,2011,30(5):234239.(in Chinese)
［36］	Zhang L Y,Fei T,Zhang X,et al.Research about immune ant colony optimization in emergency logistics transportation route choice［M］∥Communications and Information Processing.Berlin:Springer Berlin Heidelberg,2012:430437.
［37］	Lin N,Huo Z S,Liu H D.An ant colony dynamic route guidance algorithm of multiroute searching based on immune genetics［C］∥
	Proc of the 2012 8th International Conference on Wireless Communications,Networking and Mobile Computing,2012:14.
［38］	Wang T,Dong S,Wu S,et al.Numerical simulation of hydrocarbon migration in tight reservoir based on artificial immune ant colony algorithm:A case of the Chang 81,reservoir of the Triassic Yanchang Formation in the Huaqing area,Ordos Basin,China［J］.Marine & Petroleum Geology,2016,78:1729.
［39］	Gao W.Identification of constitutive model for rock materials based on immune continuous ant colony algorithm［J］.Materials Research Innovations,2016,19(sup5):S5311S5315.
［40］	Gao W.Displacement back analysis for underground engineering based on immunized continuous ant colony optimization［J］.Engineering Optimization,2016,48(5):868882.
［41］	Kirkpatrick S,Gelatt C D,Vecchi M P.Optimization by simulated annealing［J］.Science,1983,220(4598):671680.
［42］	Xu Q,Chen S,Li B.Combining the ant system algorithm and simulated annealing for 3D/2D fixedoutline floorplanning［J］.Applied Soft Computing, 2016,40(C):150160.
［43］	Liu Yuxia,Wang Ping,Xiu Chunbo.Converse ant colony algorithm based on simulated annealing［J］.Microcomputer Information,2006,22(34):265267.(in Chinese)
［44］	Zhu Jingwei,Rui Ting,Jiang Xinsheng,et al.Simulated annealing ant colony algorithm for QAP［J］.Computer Engineering and Applications,2011,47(14):3436.(in Chinese)
［45］	Sen S D,Adams J A.sAANT:A hybrid optimization algorithm for multirobot coalition formation［C］∥
	Proc of the 2013 IEEE/WIC/ACM International Joint Conferences on Web Intelligence and Intelligent Agent Technologies,2013:337344.
［46］	Wassila G,Abdelmadjid B.A hybrid intrusion detection approach using ant colony system and simulated annealing(ACSSA)［C］∥
	Proc of the International Conference on Intelligent Information Processing,Security and Advanced Communication,2015:Ariticle No.55.
［47］	Skinderowicz R.An improved ant colony system for the sequential ordering problem［J］.Computers & Operations Research,2017,86:117.
［48］	Zhai D,Zhang F,Gao B,et al.Ant colony algorithm and simulated annealing algorithm based process route optimization［C］∥
	Proc of the 2014 Enterprise Systems Conference,2014:102107.
［49］	Nancharaiah B,Mohan B C.MANET link performance using ant colony optimization and particle swarm optimization algorithms［C］∥Proc of IEEE International Conference on Communications and Signal Processing,2013:767770.
［50］	Patel M K,Kabat M R,Tripathy C R.A hybrid ACO/PSO based algorithm for QoS multicast routing problem［J］.Ain Shams Engineering Journal,2014,5(1):113120.
［51］	Elloumi W,Abed H E,Abraham A,et al.A comparative study of the improvement of performance using a PSO modified by ACO applied to TSP［J］.Applied Soft Computing,2014,25:234241.
［52］	Mandloi M,Bhatia V.A lowcomplexity hybrid algorithm based on particle swarm and ant colony optimization for largeMIMO detection［J］.Expert Systems with Applications,2016,50(C):6674.
［53］	Santra D,Mondal A,Mukherjee A,et al.Hybrid PSO — ACO technique to solve economic load dispatch problem［C］∥Proc of the 2015 IEEE International Conference on Research in Computational Intelligence and Communication Networks,2016:187191.
［54］	Lazzús J A,Rivera M,Salfate I,et al.Application of particle swarm+ant colony optimization to calculate the interaction parameters on phase equilibria［J］.Journal of Engineering Thermophysics,2016,25(2):216226.
［55］	Kefi S,Rokbani N,Krmer P,et al.Ant supervised by PSO and 2Opt algorithm,ASPSO2Opt,applied to traveling salesman problem［C］∥
	Proc of the 2016 IEEE International Conference on Systems,Man,and Cybernetics,2016:004866004871.
［56］	Bagheri M,Golbraikh A.Rankbased ant system method for nonlinear QSPR analysis:QSPR studies of the solubility parameter［J］.Sar & Qsar in Environmental Research,2012,23(12):5986.
［57］	Jin H,Ran L.A fairrank ant colony algorithm in distributed mass storage system［J］.Canadian Journal of Electrical & Computer Engineering,2015,38(4):338345.
［58］	Peng H,Li L,Kurths J,et al.Topology identification of complex network via chaotic ant swarm algorithm［J］.Mathematical Problems in Engineering,2013,
20	13:Article ID 401983.
［59］	Chatterjee A,Ghoshal S P,Mukherjee V.Chaotic ant swarm optimization for fuzzybased tuning of power system stabilizer［J］.International Journal of Electrical Power & Energy Systems,2011,33(3):657672.
［60］	Fang Xia,Xi Jinju.Ant colony algorithm based on mutation features and selected heuristics［J］.Computer Engineering and Applications,2013,49(24):2427.(in Chinese)
［61］	Liang Yuqing,Zhang Zijun.The robot path planning based on the grid method and ant colony algorithm［C］∥
	Proc of the 2012 3rd International Conference on Mechanic Automation & Control Engineering,2012:236239.
［62］	Korytkowski P,Rymaszewski S,Wisniewski T.Ant colony optimization for job shop scheduling using multiattribute dispatching rules［J］.International Journal of Advanced Manufacturing Technology,2013,67(14):231241.
［63］	Huang R H,Yu T H.An effective ant colony optimization algorithm for multiobjective jobshop scheduling with equalsize lotsplitting［J］.Applied Soft Computing,2017,57:642656.
［64］	Huang R H,Yang C L,Cheng W C.Flexible job shop scheduling with due window—A twopheromone ant colony approach［J］.International Journal of Production Economics,2013,141(2):685697.
［65］	Zhu Rui, Wang Shilong, Zhu Zheqi,et al.An ant colony algorithm for job shop scheduling problem with tool flow［J］.
	Journal of Engineering Manufacture,2014,228(8):959968.
［66］	Rossi A.Flexible job shop scheduling with sequencedependent setup and transportation times by ant colony with reinforced pheromone relationships［J］.International Journal of Production Economics,2014,153(4):253267.
［67］	Wang L,Cai J C,Li M,et al.Flexible job shop scheduling problem using an improved ant colony optimization［J］.Scientific Programming,2017,
20	17(3):Article ID 9016303.
［68］	Khoukhi F E,Boukachour J,Alaoui A E. The “DualAnts Colony”:A novel hybrid approach for the flexible job shop scheduling problem with preventive maintenance［J］.Computers & Industrial Engineering,2016,106:236255.
［69］	Reed M,Yiannakou A,Evering R.An ant colony algorithm for the multicompartment vehicle routing problem［J］.Applied Soft Computing,2014,15:169176.
［70］	Abdulkader M M S,Gajpal Y,Elmekkawy T Y.Hybridized ant colony algorithm for the multi compartment vehicle routing problem［J］.Applied Soft Computing,2015,37:196203.
［71］	Yu B,Yang Z Z.An ant colony optimization model:The period vehicle routing problem with time windows［J］.Transportation Research Part E Logistics & Transportation Review,2011,47(2):166181.
［72］	Ding Q,Hu X,Sun L,et al.An improved ant colony optimization and its application to vehicle routing problem with time windows［J］.Neurocomputing,2012,98(98):101107.
［73］	Schyns M.An ant colony system for responsive dynamic vehicle routing［J］.European Journal of Operational Research,2015,245(3):704718.
［74］	Mavrovouniotis M,Yang S X.Ant algorithms with immigrants schemes for the dynamic vehicle routing problem［J］.Information Sciences,2015,294:456477.
［75］	Zhang B,Sun X,Gao L,et al.Endmember extraction of hyperspectral remote sensing images based on the Ant Colony Optimization(ACO) algorithm［J］.IEEE Transactions on Geoscience & Remote Sensing,2011,49(7):26352646.
［76］	Wei W,Lin W,Liu L,et al.2D3D medical image registration based on ant colony algorithm［J］.Applied Mechanics & Materials,2014,462463(5):267273.
［77］	Zhang J Y,Teng J F,Yu B.A new medical image edge detection algorithm based on BCACO［J］.International Journal of Pattern Recognition & Artificial Intelligence,2016,31(3):930937.
［78］	Li L,Liu T,Yong L.An image compression improved algorithm based on the combination of fractal and ant colony algorithm［C］∥Proc of the 2014 5th International Conference on Intelligent Systems Design and Engineering Applications,2014:149152.
［79］	Biniaz A,Abbasi A.Unsupervised ACO:Applying FCM as a supervisor for ACO in medical image segmentation［J］.Journal of Intelligent & Fuzzy Systems,2014,27(1):407417.
［80］	Tang K,Xie L,Li G Y.A multiple classifier system based on antcolony optimization for hyperspectral image classification［J］.
	Journal of Physics, 2017,787(1):Article 012011.
［81］	Jang S H,Roh J H,Kim W,et al.A novel binary ant colony optimization:Application to the unit commitment problem of power systems［J］.Journal of Electrical Engineering & Technology,2011,6(2):174181.
［82］	Abdelaziz A Y, Osama R A, Elkhodary S M.Distribution systems reconfiguration using ant colony optimization and harmony search algorithms［J］.Electric Power Components & Systems,2013,41(5):537554.
［83］	Kaliannan J,Baskaran A,Dey N.Automatic generation control of ThermalThermalHydro power systems with PID controller using ant colony optimization［J］.International Journal of Service Science Management Engineering & Technology,2015,6(2):1834.
［84］	Zhou J,Wang C,Li Y,et al.A multiobjective multipopulation ant colony optimization for economic emission dispatch considering power system security［J］.Applied Mathematical Modelling,2017,45:684704.
［85］	Yin P Y,Chang R I,Chao C C,et al.Niched ant colony optimization with colony guides for QoS multicast routing［J］.Journal of Network & Computer Applications,2014,40(1):6172.
［86］	Han Pan,Chen Mou,Chen Shaodong,et al.Path planning for UAVs based on improved ant colony algorithm［J］.Journal of Jilin University(Information Science Edition),2013,31(1):6672.(in Chinese)
［87］	Kozak J,Boryczka U.Collective data mining in the ant colony decision tree approach［J］.Information Sciences, 2016,372:126147.
	附中文参考文献:
［5］	段海滨, 王道波, 朱家强,等. 蚁群算法理论及应用研究的进展［J］. 控制与决策, 2004, 19(12):13211326.
［6］	段海滨. 蚁群算法原理及其应用［M］. 北京：科学出版社, 2005.
［10］	刘国宝, 张洁. 基于改进滚动时域优化策略的动态调度方法［J］. 机械工程学报, 2013, 49(14):182190.
［20］	王芳, 李美安, 段卫军. 基于动态自适应蚁群算法的云计算任务调度［J］. 计算机应用, 2013, 33(11):31603162.
［25］	丁建立, 陈增强, 袁著祉. 遗传算法与蚂蚁算法的融合［J］. 计算机研究与发展, 2003, 40(9):13511356.
［27］	邓博于, 赵尚弘, 侯睿,等. 基于遗传蚁群融合算法的混合链路中继卫星资源调度研究［J］. 红外与激光工程, 2015, 44(7):22112217.
［29］	曹庆奎, 赵斐. 基于遗传蚁群算法的港口集卡路径优化［J］. 系统工程理论与实践, 2013, 33(7):18201828.
［34］	胡纯德, 祝延军, 高随祥. 基于人工免疫算法和蚁群算法求解旅行商问题［J］. 计算机工程与应用, 2004, 40(34):6063.
［35］	万芳, 邱林, 黄强. 水库群供水优化调度的免疫蚁群算法应用研究［J］. 水力发电学报, 2011, 30(5):234239.
［43］	刘玉霞, 王萍, 修春波. 基于模拟退火策略的逆向蚁群算法［J］. 微计算机信息, 2006, 22(34):265267.
［44］	朱经纬, 芮挺, 蒋新胜,等. 模拟退火蚁群算法求解二次分配问题［J］. 计算机工程与应用, 2011, 47(14):3436.
［60］	方霞, 席金菊. 基于变异和启发式选择的蚁群优化算法［J］. 计算机工程与应用, 2013, 49(24):2427.
［86］	韩攀, 陈谋, 陈哨东,等. 基于改进蚁群算法的无人机航迹规划［J］. 吉林大学学报(信息科学版), 2013, 31(1):6672.

[1]	顾楚梅, 曹建军, 王保卫, 徐雨芯, . 基于蚁群参数优化的LightGBM辐射源个体识别[J]. 计算机工程与科学, 2023, 45(01): 85-94.
[2]	赵广元, 赵英. 基于改进蚁群优化算法的养殖场机器人路径规划[J]. 计算机工程与科学, 2022, 44(05): 910-915.
[3]	刘雨青, 向军, 曹守启. 基于改进蚁群算法的水下自主航行机器人路径规划[J]. 计算机工程与科学, 2022, 44(03): 536-544.
[4]	胡平志, 李泽滔. 基于改进蚁群算法的四足机器人步态规划[J]. 计算机工程与科学, 2021, 43(12): 2253-2262.
[5]	宋阿妮, 包贤哲. 精英扩散蚁群优化算法求解运输无人机三维路径规划[J]. 计算机工程与科学, 2021, 43(10): 1891-1900.
[6]	马贵平, 潘峰. 基于改进蚁群算法的物流运输路径研究[J]. 计算机工程与科学, 2020, 42(03): 523-528.
[7]	曹新亮, 王智文, 冯晶, 查敏, 王宇航. 基于改进蚁群算法的机器人全局路径规划研究[J]. 计算机工程与科学, 2020, 42(03): 564-570.
[8]	张卫祥，齐玉华，魏波，张敏，窦朝晖. 基于蚁群算法的测试用例优先排序[J]. 计算机工程与科学, 2020, 42(02): 241-249.
[9]	喻小惠1，张晶1,2，陶涛3，龚力波4，黄云明1，傅铁威1. 基于蚁群策略的无线传感器网络能耗均衡分簇算法[J]. 计算机工程与科学, 2019, 41(07): 1197-1202.
[10]	郑延斌1,2，王林林1，席鹏雪1，樊文鑫1，韩梦云1. 动态环境下改进蚁群算法的多Agent路径规划[J]. 计算机工程与科学, 2019, 41(06): 1078-1085.
[11]	吴尚智1，张文超2，佘志用1，张霞1，段超1. 利用蚁群优化算法的粗糙集属性约简方法[J]. 计算机工程与科学, 2019, 41(03): 538-544.
[12]	张立毅1，肖超2，费腾1. 基于细菌觅食的改进蚁群算法[J]. 计算机工程与科学, 2018, 40(10): 1882-1889.
[13]	李娟1，汤德佑1，傅娟2，3. 一种基于蚁群算法的生物序列并行比对方法[J]. 计算机工程与科学, 2017, 39(09): 1610-1616.
[14]	张于贤，丁修坤，薛殿春，王晓婷. 求解旅行商问题的改进蚁群算法研究[J]. 计算机工程与科学, 2017, 39(08): 1576-1580.
[15]	卢志刚，申康. 基于粒子群蚁群算法的供应链合作伙伴选择研究[J]. J4, 2016, 38(05): 946-953.