基于改进蚁群算法的露天矿运输系统优化研究
|
摘要
本文介绍了基本蚁群算法的基本原理、数学模型、实现步骤,分析了参数特性、算法的优缺点,并通过数值试验分析了参数对算法性能的影响。在介绍最大最小蚂蚁系统算法的基础上,提出基于最大最小蚂蚁系统的改进MMAS蚁群算法,给出其算法框架,并通过仿真实验验证了该算法的有效性。
对现实露天矿运输系统进行描述,在此基础上构建露天矿运输系统的网络模型,构建过程包括运输系统网络的组成和描述、节点的选取、权值的确定和运输网络的生成。为将网络模型实现,设计了存储网络数据的数据库,并通过AuotCad的二次开发实现网络数据的操作。确立了改进的MMAS蚁群算法在运输系统网络模型基础上求解任意两点间最优路径的步骤,并通过程序开发实现将改进MMAS蚁群算法应用到最优线路选择中,并通过某一露天矿为实例加以运用。
This article describes the basic principles, the mathematical model and the implementation steps of the basic Ant Colony Algorithm. And it also analyzes the parameter feature and the advantages and disadvantages of the algorithm, and analyzes the impact of parameters on algorithm performance through numerical experiments. By introducing the max-min ant system algorithm, this paper proposes the improved MMAS ant colony algorithm based on the max-min ant system, given the framework of the algorithm and verifies the effectiveness of the algorithm according to the simulation experiment.
In this paper, the author builds a network model of open-pit mine transport system based on describing the real open-pit mine transport systems. The building process includes the following: the composition and description of the transport system network; the node selection; the weights determination and the generation of transport network. To achieve the network model, this paper designs a database to store network data and achieves the operation of the network data through the secondary development of AutoCad. This paper also establishes the steps of the improved MMAS ant colony algorithm based on the transportation system network model in solving the optimal path between any two points and implements the application of the improved MMAS Ant Colony Algorithm in the optimal route selection and uses this model in an open-pit mine as an example.
对现实露天矿运输系统进行描述,在此基础上构建露天矿运输系统的网络模型,构建过程包括运输系统网络的组成和描述、节点的选取、权值的确定和运输网络的生成。为将网络模型实现,设计了存储网络数据的数据库,并通过AuotCad的二次开发实现网络数据的操作。确立了改进的MMAS蚁群算法在运输系统网络模型基础上求解任意两点间最优路径的步骤,并通过程序开发实现将改进MMAS蚁群算法应用到最优线路选择中,并通过某一露天矿为实例加以运用。
This article describes the basic principles, the mathematical model and the implementation steps of the basic Ant Colony Algorithm. And it also analyzes the parameter feature and the advantages and disadvantages of the algorithm, and analyzes the impact of parameters on algorithm performance through numerical experiments. By introducing the max-min ant system algorithm, this paper proposes the improved MMAS ant colony algorithm based on the max-min ant system, given the framework of the algorithm and verifies the effectiveness of the algorithm according to the simulation experiment.
In this paper, the author builds a network model of open-pit mine transport system based on describing the real open-pit mine transport systems. The building process includes the following: the composition and description of the transport system network; the node selection; the weights determination and the generation of transport network. To achieve the network model, this paper designs a database to store network data and achieves the operation of the network data through the secondary development of AutoCad. This paper also establishes the steps of the improved MMAS ant colony algorithm based on the transportation system network model in solving the optimal path between any two points and implements the application of the improved MMAS Ant Colony Algorithm in the optimal route selection and uses this model in an open-pit mine as an example.
引文
[1]骆中洲主编,露天采矿学[M],北京:中国矿业学院出版社,1986年6月
[2]中国矿业学院主编,露天采矿手册(第四册)[M].煤炭工业出版社,1986年.
[3] M Dorigo,G di Caro.Ant Algorithms for Discrete Optimization.Artificial Life,1999
[4] A Colorni,et al.Ant system for Job-shop Scheduling.JORBEL,1994
[5]李士勇,蚁群算法及其应用[M],哈尔滨:哈尔滨工业大学出版社,2004年4月
[6] Dorigo M,Maniezoo V, Colorni A.The Ant System:An autocatalytic optimization process. Techical Report 91-016.Dept.of Electronics,Politecnico di Milano,Italv.1991
[7] Gambardella L M,Dorigo M. Ant-Q: A reinforcement learning approach to the traveling salesman problem. proceedings of the 12th International Conference on Maehine Learning,ML-95,Palo Alto(1995) 252-260
[8] Dorigo M,Gambardella L M. Ant colony system:A cooperative learning approach to the traveling saleman problem. IEEE Transactions on Evolutionary Computation 1(1)(1997) 53-66.
[9] Stutzle T, Hoos H. MAX-MIN Ant system and local search for the traveling saleman problem, Proceedings of the IEEE International Conference on Evolutionary Computation.Indianapolis:Indiana. 1997, 309-314.
[10] Dorigo M,Carp G Di. the Ant Colony Optimization Meta-heuristic, in:D. M.Dorigo, F.Glover, New Ideas in Optimization. McGraw-Hill, UK,11-32.
[11] Dorigo M, Gambardella L M. Ant Colonies for the Traveling Saleman Problem. BioSystem,1997(43):73-81.
[12] Dorigo M,Caro G di.Ant Algorithms for Discrete Optimization.Artifical Life 5(3)(1999) 137-172.
[13]程志刚.连续蚁群优化算法的研究及其化工应用[D].博士学位论文.浙江:浙江大学,2005年.
[14]卢晓筠.福建邮政运输网络系统优化研究[D].博士学位论文.天津:天津大学,2008.
[15]俨蔚敏,昊伟民.数据结构(C语言版)第二版[M].北京.清华大学出版社.1997.
[16]基于蚁群算法的最优路径选择研究[D].硕士学位论文.北京:北京交通大学2007年.
[17] Aho A V Hoperoft J E,Ullman J D.Data Structure and Algorithms.Addison-Wesley Publishing Company,Inc.1983.
[18]王行风,贾凌.GIS支持下的城市交通网络最短路径研究[J].计算机与现代化,2005.9-12.
[19]马良,项培军.蚂蚁算法在组合优化中的应用[J].管理科学学报,2001,1007-9807(2001)02-0032-06.
[20]陈文兰,戴树贵.求解旅行商问题的混合蚂蚁算法[J],计算机技术与发展,2007,07-0110-04
[21]梁震,陈新军.无向完全图的哈密顿贿赂[J].计算机科学,2000,27-11
[22]薛瑞红,李扬.一种改进的蚁群算法及其在TSP问题中的检验[J].2007,12(c)-0211-02
[23]肖进杰,范辉.贪心算法求解K-median问题[J].计算机工程与应用.2006,03-0057-02
[24]孙会君,高自友.考虑路线安排的物流配送中心选址双层规划模型及求解算法[J].中国公路学报,2003,(4):115~119.
[25]肖键梅.蚁群优化算法的改进及应用[D].硕士学位论文.上海:上海海事大学,2006.
[26]唐艺军.基于蚁群算法的数据挖掘应用研究[D].硕士学位论文.辽宁:辽宁工程技术大学,2007.
[27]于芹.基于蚁群算法的物流车辆路径优化问题的研究[D].硕士学位论文.上海:上海交通大学,2007.
[28]程伟.基于费用最小化的进口原油运输网络优化研究[D].硕士学位论文.大连:大连海事大学,2009.
[29]刘超.基于蚁群算法的DTC系统在矿用提升机上的应用研究[D].硕士学位论文.西安:西安建筑科技大学,2008.
[30]段玉波,任伟建,霍凤财,董宏丽.一种新的免疫遗传算法及其应用[J].控制与决策,2005,10-1185-04
[31]黄敏,佟振声.分布式多Agent系统的研究[J].电力情报,2002,01—0065—04
[32]薛俊玲.基于小波变换的鲁棒性水印研究[D].硕士学位论文.南京:南京理工大学,2009.
[33]曹浪财,罗健,李天成.智能蚂蚁算法一蚁群算法的改进[J].计算机应用研究,2003, 10:62-64.
[34] Stutzle T, Hoos H. Improvements on the Ant System: Introducing MAX-MIN Ant System[C]. In Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithms, Springer Verlag, Wien.1997,245-249.
[35]王颖,谢剑英.一种自适应蚁群算法及其仿真研究[J].系统仿真学报,2002,14(1):31-33
[36]覃刚力,杨家本.自适应调整信息素的蚁群算法[J].信息与控制,2002,14(1):31~33.
[37]段海滨,蚁群算法原理及其应用[M].北京:科学出版社,2005.
[38]王小平,曹立明.遗传算法-理论应用于软件实现[M].西安:西安交通大学出版社,2002.
[39]付宇,肖健梅.动态自适应蚁群算法求解TSP问题[J].上海:计算机辅助功能,2006, 04-0010-04.
[40] Dorigo M, Maniezzo V, Colorni A.Ant System : Optimization by a Colony of Cooperating Agents.IEEE Transaction on Systems, Man and Cybernetics-Part B,1996,26(1):29~41.
[41]张军等.蚁群优化[M].北京:清华大学出版社,2007
[42]赵宝江,李士勇,金俊.基于自适应路径选择和信息素更新的蚁群算法[J].计算机工程和应用,2007,43(3):12~15.
[43] Dorigo M, Maniezzo V, Colorni A. The ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 1996,26(1): 29-41
[44]燕忠.基于蚁群优化算法的若干问题的研究[D]. [博士学位论文],东南大学.2005
[45]秦固.基于蚁群优化的多物流配送中心选址算法[J].系统工程理论与实践,2006,4:120~124.
[2]中国矿业学院主编,露天采矿手册(第四册)[M].煤炭工业出版社,1986年.
[3] M Dorigo,G di Caro.Ant Algorithms for Discrete Optimization.Artificial Life,1999
[4] A Colorni,et al.Ant system for Job-shop Scheduling.JORBEL,1994
[5]李士勇,蚁群算法及其应用[M],哈尔滨:哈尔滨工业大学出版社,2004年4月
[6] Dorigo M,Maniezoo V, Colorni A.The Ant System:An autocatalytic optimization process. Techical Report 91-016.Dept.of Electronics,Politecnico di Milano,Italv.1991
[7] Gambardella L M,Dorigo M. Ant-Q: A reinforcement learning approach to the traveling salesman problem. proceedings of the 12th International Conference on Maehine Learning,ML-95,Palo Alto(1995) 252-260
[8] Dorigo M,Gambardella L M. Ant colony system:A cooperative learning approach to the traveling saleman problem. IEEE Transactions on Evolutionary Computation 1(1)(1997) 53-66.
[9] Stutzle T, Hoos H. MAX-MIN Ant system and local search for the traveling saleman problem, Proceedings of the IEEE International Conference on Evolutionary Computation.Indianapolis:Indiana. 1997, 309-314.
[10] Dorigo M,Carp G Di. the Ant Colony Optimization Meta-heuristic, in:D. M.Dorigo, F.Glover, New Ideas in Optimization. McGraw-Hill, UK,11-32.
[11] Dorigo M, Gambardella L M. Ant Colonies for the Traveling Saleman Problem. BioSystem,1997(43):73-81.
[12] Dorigo M,Caro G di.Ant Algorithms for Discrete Optimization.Artifical Life 5(3)(1999) 137-172.
[13]程志刚.连续蚁群优化算法的研究及其化工应用[D].博士学位论文.浙江:浙江大学,2005年.
[14]卢晓筠.福建邮政运输网络系统优化研究[D].博士学位论文.天津:天津大学,2008.
[15]俨蔚敏,昊伟民.数据结构(C语言版)第二版[M].北京.清华大学出版社.1997.
[16]基于蚁群算法的最优路径选择研究[D].硕士学位论文.北京:北京交通大学2007年.
[17] Aho A V Hoperoft J E,Ullman J D.Data Structure and Algorithms.Addison-Wesley Publishing Company,Inc.1983.
[18]王行风,贾凌.GIS支持下的城市交通网络最短路径研究[J].计算机与现代化,2005.9-12.
[19]马良,项培军.蚂蚁算法在组合优化中的应用[J].管理科学学报,2001,1007-9807(2001)02-0032-06.
[20]陈文兰,戴树贵.求解旅行商问题的混合蚂蚁算法[J],计算机技术与发展,2007,07-0110-04
[21]梁震,陈新军.无向完全图的哈密顿贿赂[J].计算机科学,2000,27-11
[22]薛瑞红,李扬.一种改进的蚁群算法及其在TSP问题中的检验[J].2007,12(c)-0211-02
[23]肖进杰,范辉.贪心算法求解K-median问题[J].计算机工程与应用.2006,03-0057-02
[24]孙会君,高自友.考虑路线安排的物流配送中心选址双层规划模型及求解算法[J].中国公路学报,2003,(4):115~119.
[25]肖键梅.蚁群优化算法的改进及应用[D].硕士学位论文.上海:上海海事大学,2006.
[26]唐艺军.基于蚁群算法的数据挖掘应用研究[D].硕士学位论文.辽宁:辽宁工程技术大学,2007.
[27]于芹.基于蚁群算法的物流车辆路径优化问题的研究[D].硕士学位论文.上海:上海交通大学,2007.
[28]程伟.基于费用最小化的进口原油运输网络优化研究[D].硕士学位论文.大连:大连海事大学,2009.
[29]刘超.基于蚁群算法的DTC系统在矿用提升机上的应用研究[D].硕士学位论文.西安:西安建筑科技大学,2008.
[30]段玉波,任伟建,霍凤财,董宏丽.一种新的免疫遗传算法及其应用[J].控制与决策,2005,10-1185-04
[31]黄敏,佟振声.分布式多Agent系统的研究[J].电力情报,2002,01—0065—04
[32]薛俊玲.基于小波变换的鲁棒性水印研究[D].硕士学位论文.南京:南京理工大学,2009.
[33]曹浪财,罗健,李天成.智能蚂蚁算法一蚁群算法的改进[J].计算机应用研究,2003, 10:62-64.
[34] Stutzle T, Hoos H. Improvements on the Ant System: Introducing MAX-MIN Ant System[C]. In Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithms, Springer Verlag, Wien.1997,245-249.
[35]王颖,谢剑英.一种自适应蚁群算法及其仿真研究[J].系统仿真学报,2002,14(1):31-33
[36]覃刚力,杨家本.自适应调整信息素的蚁群算法[J].信息与控制,2002,14(1):31~33.
[37]段海滨,蚁群算法原理及其应用[M].北京:科学出版社,2005.
[38]王小平,曹立明.遗传算法-理论应用于软件实现[M].西安:西安交通大学出版社,2002.
[39]付宇,肖健梅.动态自适应蚁群算法求解TSP问题[J].上海:计算机辅助功能,2006, 04-0010-04.
[40] Dorigo M, Maniezzo V, Colorni A.Ant System : Optimization by a Colony of Cooperating Agents.IEEE Transaction on Systems, Man and Cybernetics-Part B,1996,26(1):29~41.
[41]张军等.蚁群优化[M].北京:清华大学出版社,2007
[42]赵宝江,李士勇,金俊.基于自适应路径选择和信息素更新的蚁群算法[J].计算机工程和应用,2007,43(3):12~15.
[43] Dorigo M, Maniezzo V, Colorni A. The ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 1996,26(1): 29-41
[44]燕忠.基于蚁群优化算法的若干问题的研究[D]. [博士学位论文],东南大学.2005
[45]秦固.基于蚁群优化的多物流配送中心选址算法[J].系统工程理论与实践,2006,4:120~124.