基于吸引场的蚁群算法在TSP中的应用
|
摘要
针对传统蚁群算法容易陷入局部最优解等缺陷,提出了一种基于吸引场的改进的蚁群算法.首先,详细分析了基于信息素的吸引场原理,在此基础上建立了基于信息素的吸引场模型.其次,设计了吸引场因子,给出了信息素更新策略,使相距较近的蚂蚁之间能更好地进行协作.最后,针对标准的30个城市的旅行商问题,使用所提出的算法与基本蚁群算法、其他改进的蚁群算法进行优化分析,并进行了结果对比.结果表明:所提出的蚁群算法可以获得TSP问题的最优解423.74,Oliver30问题计算结果最优值为423.74,平均值为423.96,具有较好的搜索全局最优解的能力.
To overcome the default of local optimal solution in the traditional ant colony algorithm,a modified ant colony optimization( AFACO) was proposed based on attractive field. The principle of attraction field based on pheromone was analyzed in detail to establish the attractive field model. The attractive field factor based on pheromone was designed,and the pheromone updating strategy was provided to improve the collaboration among ants nearby. For the standard 30 city traveling salesman problem,the optimization results from the proposed algorithm were compared with those from basic ant colony algorithm and some other improved ant colony. The results show that the optimal solution of TSP problem is 423. 74,while the optimal and the mean solution of Oliver30 are 423. 74 and 423. 96,respectively,which shows the improved ant colony algorithm has good ability for searching the global optimal solution.
To overcome the default of local optimal solution in the traditional ant colony algorithm,a modified ant colony optimization( AFACO) was proposed based on attractive field. The principle of attraction field based on pheromone was analyzed in detail to establish the attractive field model. The attractive field factor based on pheromone was designed,and the pheromone updating strategy was provided to improve the collaboration among ants nearby. For the standard 30 city traveling salesman problem,the optimization results from the proposed algorithm were compared with those from basic ant colony algorithm and some other improved ant colony. The results show that the optimal solution of TSP problem is 423. 74,while the optimal and the mean solution of Oliver30 are 423. 74 and 423. 96,respectively,which shows the improved ant colony algorithm has good ability for searching the global optimal solution.
引文
[1]Liao T J,Stützle T,de Oca M A M,et al.A unified ant colony optimization algorithm for continuous optimization[J].European Journal of Operational Research,2014,234(3):597-609.
[2]Wu W H,Cheng S R,Wu C C,et al.Ant colony algorithms for a two-agent scheduling with sum-of processing times-based learning and deteriorating considerations[J].Journal of Intelligent Manufacturing,2012,23(5):1985-1993.
[3]Wang Lei,Tang Dunbing,Gu Wenbin,et al.Pheromone-based coordination for manufacturing system control[J].Journal of Intelligent Manufacturing,2012,23(3):747-757.
[4]黄晓玮,邹小波,赵杰文,等.近红外光谱结合蚁群算法检测花茶花青素含量[J].江苏大学学报:自然科学版,2014,35(2):165-170,188.Huang Xiaowei,Zou Xiaobo,Zhao Jiewen,et al.Measurement of anthocyanin in flowering tea using near infrared spectroscopy combined with ant colony optimization[J].Journal of Jiangsu University:Natural Science Edition,2014,35(2):165-170,188.(in Chinese)
[5]覃志东,侯颖,肖芳雄.基于蚁群优化算法的同构多核任务分配与调度[J].江苏大学学报:自然科学版,2014,35(6):679-684.Qin Zhidong,Hou Ying,Xiao Fangxiong.Task allocation and scheduling for homogeneous multi-core processors based on ant colony optimization[J].Journal of Jiangsu University:Natural Science Edition,2014,35(6):679-684.(in Chinese)
[6]Xiao Jing,Li Liangping.A hybrid ant colony optimization for continuous domains[J].Expert Systems with Applications,2011,38(9):11072-11077.
[7]Hannaneh Rashidi,Reza Zanjirani Farahani.A hybrid ant colony system for partially dynamic vehicle routing problem[J].American Journal of Operational Research,2012,2(4):31-44.
[8]Mavrovouniotis Michalis,Yang Shengxiang.A memetic ant colony optimization algorithm for the dynamic travelling salesman problem[J].Soft Computing,2011,15(7):1405-1425.
[9]张敬敏,马丽,李媛媛.求解TSP问题的改进混合蛙跳算法[J].计算机工程与应用,2012,48(11):47-50.Zhang Jingmin,Ma Li,Li Yuanyuan.Improved shuffled frog-leaping algorithm for traveling salesman problem[J].Computer Engineering and Applications,2012,48(11):47-50.(in Chinese)
[10]黄国锐,曹先彬,王煦法.基于信息素扩散的蚁群算法[J].电子学报,2004,32(5):865-868.Huang Guorui,Cao Xianbin,Wang Xufa.An ant colony optimization algorithm based on pheromone diffusion[J].ACTA Electronica Sinica,2004,32(5):865-868.(in Chinese)
[11]高世伟,郭雷,杜亚琴,等.一种基于动态加权规则的自适应蚁群算法[J].计算机应用,2007,27(7):1741-1743.Gao Shiwei,Guo Lei,Du Yaqin,et al.Adaptive ant colony algorithm based on dynamic weighted rule[J].Computer Applications,2007,27(7):1741-1743.(in Chinese)
[12]江新姿,汤可宗,高尚.蚁群算法与免疫算法的混合算法[J].科学技术与工程,2008,8(5):1327-1330.Jiang Xinzi,Tang Kezong,Gao Shang.Hybrid algorithm combining ant colony optimization algorithm with immune algorithm[J].Science Technology and Engineering,2008,8(5):1327-1330.(in Chinese)
[13]查凯,曾建潮.求解TSP问题的思维进化算法[J].计算机工程与应用,2002,38(4):102-104.Zha Kai,Zeng Jianchao.Solving TSP with mind evolutionary computation[J].Computer Engineering and Applications,2002,38(4):102-104.(in Chinese)
[2]Wu W H,Cheng S R,Wu C C,et al.Ant colony algorithms for a two-agent scheduling with sum-of processing times-based learning and deteriorating considerations[J].Journal of Intelligent Manufacturing,2012,23(5):1985-1993.
[3]Wang Lei,Tang Dunbing,Gu Wenbin,et al.Pheromone-based coordination for manufacturing system control[J].Journal of Intelligent Manufacturing,2012,23(3):747-757.
[4]黄晓玮,邹小波,赵杰文,等.近红外光谱结合蚁群算法检测花茶花青素含量[J].江苏大学学报:自然科学版,2014,35(2):165-170,188.Huang Xiaowei,Zou Xiaobo,Zhao Jiewen,et al.Measurement of anthocyanin in flowering tea using near infrared spectroscopy combined with ant colony optimization[J].Journal of Jiangsu University:Natural Science Edition,2014,35(2):165-170,188.(in Chinese)
[5]覃志东,侯颖,肖芳雄.基于蚁群优化算法的同构多核任务分配与调度[J].江苏大学学报:自然科学版,2014,35(6):679-684.Qin Zhidong,Hou Ying,Xiao Fangxiong.Task allocation and scheduling for homogeneous multi-core processors based on ant colony optimization[J].Journal of Jiangsu University:Natural Science Edition,2014,35(6):679-684.(in Chinese)
[6]Xiao Jing,Li Liangping.A hybrid ant colony optimization for continuous domains[J].Expert Systems with Applications,2011,38(9):11072-11077.
[7]Hannaneh Rashidi,Reza Zanjirani Farahani.A hybrid ant colony system for partially dynamic vehicle routing problem[J].American Journal of Operational Research,2012,2(4):31-44.
[8]Mavrovouniotis Michalis,Yang Shengxiang.A memetic ant colony optimization algorithm for the dynamic travelling salesman problem[J].Soft Computing,2011,15(7):1405-1425.
[9]张敬敏,马丽,李媛媛.求解TSP问题的改进混合蛙跳算法[J].计算机工程与应用,2012,48(11):47-50.Zhang Jingmin,Ma Li,Li Yuanyuan.Improved shuffled frog-leaping algorithm for traveling salesman problem[J].Computer Engineering and Applications,2012,48(11):47-50.(in Chinese)
[10]黄国锐,曹先彬,王煦法.基于信息素扩散的蚁群算法[J].电子学报,2004,32(5):865-868.Huang Guorui,Cao Xianbin,Wang Xufa.An ant colony optimization algorithm based on pheromone diffusion[J].ACTA Electronica Sinica,2004,32(5):865-868.(in Chinese)
[11]高世伟,郭雷,杜亚琴,等.一种基于动态加权规则的自适应蚁群算法[J].计算机应用,2007,27(7):1741-1743.Gao Shiwei,Guo Lei,Du Yaqin,et al.Adaptive ant colony algorithm based on dynamic weighted rule[J].Computer Applications,2007,27(7):1741-1743.(in Chinese)
[12]江新姿,汤可宗,高尚.蚁群算法与免疫算法的混合算法[J].科学技术与工程,2008,8(5):1327-1330.Jiang Xinzi,Tang Kezong,Gao Shang.Hybrid algorithm combining ant colony optimization algorithm with immune algorithm[J].Science Technology and Engineering,2008,8(5):1327-1330.(in Chinese)
[13]查凯,曾建潮.求解TSP问题的思维进化算法[J].计算机工程与应用,2002,38(4):102-104.Zha Kai,Zeng Jianchao.Solving TSP with mind evolutionary computation[J].Computer Engineering and Applications,2002,38(4):102-104.(in Chinese)