自适应模糊蚁群系统
|
摘要
针对蚁群系统(Ant Colony System,ACS)容易陷入局部最优和收敛速度较慢的不足,提出了自适应模糊蚁群系统(AF-ACS)用于旅行商问题(TSP)。该算法的核心是引入模糊隶属度和信息熵的概念,AF-ACS将以信息熵为概率,自适应地对ACS引入模糊隶属度,以平衡算法的种群多样性与收敛速度之间的关系。算法早期引入模糊隶属度的概率较小,保证算法的多样性;算法后期引入模糊隶属度的概率较大,提高算法的收敛速度。通过与ACS和ECACS(Entropy-based Adaptive Chaotic Ant Colony Algorithm)进行14种不同规模的TSP测试集实验对比,AFACS以较少的迭代次数取得最优解或较优解。从而证明了AF-ACS的可行性与高效性。
Because the Ant Colony System(ACS)is easy to fall into the local optimization and slow convergence, an Adaptive Fuzzy Ant Colony System(AF-ACS)is proposed for Traveling Salesman Problem(TSP). The core of the algorithm is to introduce the concept of fuzzy membership and information entropy. AF-ACS will adaptively introduce fuzzy membership to ACS with information entropy as the probability. This balances the relationship between the population diversity of the algorithm and the rate of convergence. The probability of introducing fuzzy membership degree early in the algorithm is small, which ensures the diversity of the algorithm. The probability of introducing fuzzy membership degree in the later stage of the algorithm is large, which improves the convergence speed of the algorithm. By comparing14 different scale TSP test sets with ACS and ECACS(Entropy-based Adaptive Chaotic Ant Colony Algorithm), AF-ACS obtains the optimal solution or better solution with fewer iterations. This proves the feasibility and efficiency of AF-ACS.
Because the Ant Colony System(ACS)is easy to fall into the local optimization and slow convergence, an Adaptive Fuzzy Ant Colony System(AF-ACS)is proposed for Traveling Salesman Problem(TSP). The core of the algorithm is to introduce the concept of fuzzy membership and information entropy. AF-ACS will adaptively introduce fuzzy membership to ACS with information entropy as the probability. This balances the relationship between the population diversity of the algorithm and the rate of convergence. The probability of introducing fuzzy membership degree early in the algorithm is small, which ensures the diversity of the algorithm. The probability of introducing fuzzy membership degree in the later stage of the algorithm is large, which improves the convergence speed of the algorithm. By comparing14 different scale TSP test sets with ACS and ECACS(Entropy-based Adaptive Chaotic Ant Colony Algorithm), AF-ACS obtains the optimal solution or better solution with fewer iterations. This proves the feasibility and efficiency of AF-ACS.
引文
[1] Dorigo M,Maniezzo V,Colorni A.The ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on System,Man and Cybernetics Society,1996,26:29-41.
[2] Tabakhi S,Moradi P,Akhlaghian F.An unsupervised feature selection algorithm based on ant colony optimization[J].Engineering Applications of Artificial Intelligence,2014,32:112-123.
[3]姜道银,葛洪伟,袁罗.一种动态划分的混合连续域蚁群优化算法[J].计算机工程与应用,2018,54(7):144-151.
[4] Liu X F,Zhan Z H,Deng J D,et al.An energy efficient ant colony system for virtual machine placementin cloud computing[J].IEEE Transactions on Evolutionary Computation,2018,22(1):113-128.
[5] Li J Z,Zheng S Q,Tan Y.Adaptive fireworks algorithm[C]//2014 IEEE CEC.Beijing,China:IEEE,2014:3214-3221.
[6]焦圣喜,王睿,李婉珍.自适应波束形成算法[J].信息与控制,2015,44(2):165-170.
[7] Haario H,Saksman E,Tamminen J.An adaptive metropolis algorithm[J].Bernoulli,2001,7(2):223-242.
[8] Audet C,Dennis J E.Mesh adaptive direct search algorithms for constrained optimization[J].SIAM Journal on Optimization,2006,17(1):188-217.
[9] Toth G,van der Holst B,Sokolov I V.Adaptive numerical algorithms in space weather modeling[J].Journal of Computational Physics,2012,231(3):870-903.
[10] Liang J,Shi Z,Li D,et al.Information entropyrough entropy and knowledge granulation in incomplete information systems[J].International Journal of General Systems,2006,35(6):641-654.
[11] Zhang Xiao,Mei Changlin,Chen Degang.Feature selection in mixed data:a method using a novel fuzzy rough set-based information entropy[J].Pattern Recognition,2016,56:1-15.
[12]蔡自兴.智能控制导论[M].北京:中国水利水电出版社,2013.
[13]李素姝,王士同,李滔.基于双模糊信息的特征选择算法[J].计算机科学与探索,2017,11(12):1993-2003.
[14] Amiri E,Keshavarz H,Alizadeh M,et al.Energy efficient routing in wireless sensor networks based on fuzzy ant colony optimization[J].International Journal of Distributed Sensor Networks,2014:768936.
[15] Porta Garcia M A,Montiel O,Oscar Castillo,et al.Path planning for autonomous mobile robot navigation with ant colony optimization and fuzzy cost function evaluation[J].Elsevier Applied Soft Computing,2009,9:1102-1110.
[16] Mostafa F G,Mohammad S A.Using fuzzy ant colony optimization for diagnosis of diabetes disease[C]//18th Iranian Conference on Electrical Engineering,2010.
[17]王大为,朴在林.基于序优化和模糊蚁群算法的多目标配电网重构[J].电网与清洁能源,2016,32(9):44-49.
[18]唐胜景,陈天悦,李震,等.基于感知模糊自适应蚁群算法的非线性PID控制设计[J].计算机测量与控制,2016,24(11):91-94.
[19] Yan Y,Sohn H,Reyes G.A modified ant system to achieve better balance between intensification and diversification for the traveling salesman problem[J].Applied Soft Computing,2017,60:256-267.
[20]陈卫东,朱奇光.基于模糊算法的移动机器人路径规划[J].电子学报,2011,39(4):971-980.
[21]李娟,游晓明,刘升,等.动态混沌蚁群系统及其在机器人路径规划中的应用[J].计算机应用,2011,39(4):971-974.
[2] Tabakhi S,Moradi P,Akhlaghian F.An unsupervised feature selection algorithm based on ant colony optimization[J].Engineering Applications of Artificial Intelligence,2014,32:112-123.
[3]姜道银,葛洪伟,袁罗.一种动态划分的混合连续域蚁群优化算法[J].计算机工程与应用,2018,54(7):144-151.
[4] Liu X F,Zhan Z H,Deng J D,et al.An energy efficient ant colony system for virtual machine placementin cloud computing[J].IEEE Transactions on Evolutionary Computation,2018,22(1):113-128.
[5] Li J Z,Zheng S Q,Tan Y.Adaptive fireworks algorithm[C]//2014 IEEE CEC.Beijing,China:IEEE,2014:3214-3221.
[6]焦圣喜,王睿,李婉珍.自适应波束形成算法[J].信息与控制,2015,44(2):165-170.
[7] Haario H,Saksman E,Tamminen J.An adaptive metropolis algorithm[J].Bernoulli,2001,7(2):223-242.
[8] Audet C,Dennis J E.Mesh adaptive direct search algorithms for constrained optimization[J].SIAM Journal on Optimization,2006,17(1):188-217.
[9] Toth G,van der Holst B,Sokolov I V.Adaptive numerical algorithms in space weather modeling[J].Journal of Computational Physics,2012,231(3):870-903.
[10] Liang J,Shi Z,Li D,et al.Information entropyrough entropy and knowledge granulation in incomplete information systems[J].International Journal of General Systems,2006,35(6):641-654.
[11] Zhang Xiao,Mei Changlin,Chen Degang.Feature selection in mixed data:a method using a novel fuzzy rough set-based information entropy[J].Pattern Recognition,2016,56:1-15.
[12]蔡自兴.智能控制导论[M].北京:中国水利水电出版社,2013.
[13]李素姝,王士同,李滔.基于双模糊信息的特征选择算法[J].计算机科学与探索,2017,11(12):1993-2003.
[14] Amiri E,Keshavarz H,Alizadeh M,et al.Energy efficient routing in wireless sensor networks based on fuzzy ant colony optimization[J].International Journal of Distributed Sensor Networks,2014:768936.
[15] Porta Garcia M A,Montiel O,Oscar Castillo,et al.Path planning for autonomous mobile robot navigation with ant colony optimization and fuzzy cost function evaluation[J].Elsevier Applied Soft Computing,2009,9:1102-1110.
[16] Mostafa F G,Mohammad S A.Using fuzzy ant colony optimization for diagnosis of diabetes disease[C]//18th Iranian Conference on Electrical Engineering,2010.
[17]王大为,朴在林.基于序优化和模糊蚁群算法的多目标配电网重构[J].电网与清洁能源,2016,32(9):44-49.
[18]唐胜景,陈天悦,李震,等.基于感知模糊自适应蚁群算法的非线性PID控制设计[J].计算机测量与控制,2016,24(11):91-94.
[19] Yan Y,Sohn H,Reyes G.A modified ant system to achieve better balance between intensification and diversification for the traveling salesman problem[J].Applied Soft Computing,2017,60:256-267.
[20]陈卫东,朱奇光.基于模糊算法的移动机器人路径规划[J].电子学报,2011,39(4):971-980.
[21]李娟,游晓明,刘升,等.动态混沌蚁群系统及其在机器人路径规划中的应用[J].计算机应用,2011,39(4):971-974.