元胞蚂蚁算法及其应用研究
|
摘要
旅行商问题、度约束最小树问题、二次分配问题、图着色问题等是迄今为止仍悬而未决的NP-难题,具有极大的挑战性。这些问题在实际生活中有着广泛的应用,寻找有效的算法就显得更为重要。近年来,一系列来自自然界的演化型算法,典型的有:遗传算法、模拟退火算法、禁忌搜索法、蚂蚁算法、粒子群算法、免疫算法等,为解决这些问题提供了一种手段。
蚂蚁算法于1991年首次提出的,1996年起正式发表在国际学术期刊上。蚂蚁算法以TSP为测试基准,与其它一些常用启发式方法作了一系列的比较,实验结果体现了其强大的寻优搜索能力,并已在一系列困难的组合优化问题求解中取得了成效。元胞自动机是冯诺伊曼最早提出的“用于模拟生命系统所具有的自复制功能”,沃尔夫勒姆等人将动力系统方法和计算理论及形式语言方法用于元胞自动机的研究中,促进其广泛应用,尤其是其大规模的仿真计算能力为研究复杂系统的行为提供了有效的虚拟实验室。
本文将立足于蚂蚁算法(Ant Algorithm),并结合元胞自动机(Celluar Automata)原理,针对一般连续和离散优化问题,提出一种全新的元胞蚂蚁算法。从理论上探索了算法的收敛性,并从实验角度验证算法的有效性,同时对多目标问题进行了探索。本文为系统科学、人工智能、优化理论以及复杂性科学等一系列跨学科领域的发展提供了新的思想方法,同时为工程技术、社会经济(如城市交通、物流配送)等范畴内的相关问题提供有效的基本解决工具和手段,具有广泛的经济和社会效益。
本文的具体内容包括:第一章给出了论文的研究背景和内容;第二章概述了计算复杂性和演化类算法的几种主流思想及其研究现状;第三章介绍了蚂蚁算法和元胞自动机的原理;第四章介绍元胞蚂蚁算法,首先给出连续元胞蚂蚁算法的数学描述和实例测试,然后给出离散元胞蚂蚁算法的描述,并对TSP库的数据进行实例验证,最后讨论若干扩展TSP的求解方法;第五章介绍随机泛函分析基础,给出连续和离散元胞蚂蚁算法的收敛性的论证;第六章主要讨论多目标的元胞蚂蚁算法;第七章对论文进行总结,并对进一步的研究方向进行展望。
总之,本文的研究从理论上提出了求解组合优化难题的新算法并给出算法收敛性的数学论证,在应用上为复杂困难的系统优化问题提供了新的具有竞争力的求解算法。
This area of research contains many unsolved famous problems that have great challenges, such as those so called NP-hard problems like the traveling salesman problem, degree-constrained minimum spanning tree problem, quadratic assignment problem, graph coloring problem etc. Since these problems have many applications in real situations, it is quite important to find some applicable algorithms. In recent years, there appeared several evolutionary algorithms for solving the NP-hard problems from nature in this field, typically like simulated annealing, genetic algorithm, tabu search, ant algorithm, etc.
Ant colony algorithm was first proposed in 1991 and published at international magazine in 1996. Compared with other bionical algorithms for TSP, the ant algorithms have some good properties as a searching optimization approach in some test experiments and solving different discrete systems optimization problems successfully. The concept of cellular automata were first proposed by Von Neumann in simulating system of living with reproducing. Wolfram et al took the method of dynamic system, computational theory and the method of form language for studying the cellular automata. Cellular automata were applied in many fields and have provided effective virtual laboratory in the field of large-scale simulation computing for studying the behavior of systems.
This dissertation proposes a new algorithm -- cellular ant algorithm-- for function and discrete systems optimization based on ant algorithm and cellular automata.
The dissertation gives convergence analysis for cellular ant algorithm and numerical simulation that show the algorithm is robust and efficient, and extends the application area to the multi-objective optimization.
The dissertation provides a new method for systems science, artificial intelligence, optimization theory and complexity science, and provides effective and basic tools and methods for many fields of engineering technology and social economy with wide effects.
The contents of the dissertation includes:
Chapter 1 gives the background and the contents of the whole dissertation.
Chapter 2 generally introduces computational complexity and surveys some main ideas of evolutionary algorithms and their development.
Chapter 3 describes the basic principles of ant algorithm and Cellular Automata.
Chapter 4 proposes a new optimization algorithm—cellular ant algorithm. Firstly the function optimization, then discusses the discrete systems optimization, like classical TSP, lastly discusses the resolution of some extended TSP. These problems include bottleneck TSP, minimum ratio TSP, time-constrained TSP. Large number of tests and comparisons show the effectiveness of the searching strategy.
Chapter 5 gives convergence analysis for cellular ant algorithm of function and discrete systems based on the theory of random fixed point, and makes the relevant theoretical foundation of the convergence property of the algorithm.
In Chapter 6, a cellular ant algorithm for solving multi-objective function optimization is presented. The algorithm can be used for solving the multi-objective function and discrete systems optimization. The simulation results show that the algorithm can efficiently reach the true Pareto frontier.
In short, the research results of the dissertation theoretically provides a new kind algorithm for NP-hard problems and gives convergence proof of the algorithm. Practically, the dissertation develops a series of strategies for solving different systems optimization problems.
蚂蚁算法于1991年首次提出的,1996年起正式发表在国际学术期刊上。蚂蚁算法以TSP为测试基准,与其它一些常用启发式方法作了一系列的比较,实验结果体现了其强大的寻优搜索能力,并已在一系列困难的组合优化问题求解中取得了成效。元胞自动机是冯诺伊曼最早提出的“用于模拟生命系统所具有的自复制功能”,沃尔夫勒姆等人将动力系统方法和计算理论及形式语言方法用于元胞自动机的研究中,促进其广泛应用,尤其是其大规模的仿真计算能力为研究复杂系统的行为提供了有效的虚拟实验室。
本文将立足于蚂蚁算法(Ant Algorithm),并结合元胞自动机(Celluar Automata)原理,针对一般连续和离散优化问题,提出一种全新的元胞蚂蚁算法。从理论上探索了算法的收敛性,并从实验角度验证算法的有效性,同时对多目标问题进行了探索。本文为系统科学、人工智能、优化理论以及复杂性科学等一系列跨学科领域的发展提供了新的思想方法,同时为工程技术、社会经济(如城市交通、物流配送)等范畴内的相关问题提供有效的基本解决工具和手段,具有广泛的经济和社会效益。
本文的具体内容包括:第一章给出了论文的研究背景和内容;第二章概述了计算复杂性和演化类算法的几种主流思想及其研究现状;第三章介绍了蚂蚁算法和元胞自动机的原理;第四章介绍元胞蚂蚁算法,首先给出连续元胞蚂蚁算法的数学描述和实例测试,然后给出离散元胞蚂蚁算法的描述,并对TSP库的数据进行实例验证,最后讨论若干扩展TSP的求解方法;第五章介绍随机泛函分析基础,给出连续和离散元胞蚂蚁算法的收敛性的论证;第六章主要讨论多目标的元胞蚂蚁算法;第七章对论文进行总结,并对进一步的研究方向进行展望。
总之,本文的研究从理论上提出了求解组合优化难题的新算法并给出算法收敛性的数学论证,在应用上为复杂困难的系统优化问题提供了新的具有竞争力的求解算法。
This area of research contains many unsolved famous problems that have great challenges, such as those so called NP-hard problems like the traveling salesman problem, degree-constrained minimum spanning tree problem, quadratic assignment problem, graph coloring problem etc. Since these problems have many applications in real situations, it is quite important to find some applicable algorithms. In recent years, there appeared several evolutionary algorithms for solving the NP-hard problems from nature in this field, typically like simulated annealing, genetic algorithm, tabu search, ant algorithm, etc.
Ant colony algorithm was first proposed in 1991 and published at international magazine in 1996. Compared with other bionical algorithms for TSP, the ant algorithms have some good properties as a searching optimization approach in some test experiments and solving different discrete systems optimization problems successfully. The concept of cellular automata were first proposed by Von Neumann in simulating system of living with reproducing. Wolfram et al took the method of dynamic system, computational theory and the method of form language for studying the cellular automata. Cellular automata were applied in many fields and have provided effective virtual laboratory in the field of large-scale simulation computing for studying the behavior of systems.
This dissertation proposes a new algorithm -- cellular ant algorithm-- for function and discrete systems optimization based on ant algorithm and cellular automata.
The dissertation gives convergence analysis for cellular ant algorithm and numerical simulation that show the algorithm is robust and efficient, and extends the application area to the multi-objective optimization.
The dissertation provides a new method for systems science, artificial intelligence, optimization theory and complexity science, and provides effective and basic tools and methods for many fields of engineering technology and social economy with wide effects.
The contents of the dissertation includes:
Chapter 1 gives the background and the contents of the whole dissertation.
Chapter 2 generally introduces computational complexity and surveys some main ideas of evolutionary algorithms and their development.
Chapter 3 describes the basic principles of ant algorithm and Cellular Automata.
Chapter 4 proposes a new optimization algorithm—cellular ant algorithm. Firstly the function optimization, then discusses the discrete systems optimization, like classical TSP, lastly discusses the resolution of some extended TSP. These problems include bottleneck TSP, minimum ratio TSP, time-constrained TSP. Large number of tests and comparisons show the effectiveness of the searching strategy.
Chapter 5 gives convergence analysis for cellular ant algorithm of function and discrete systems based on the theory of random fixed point, and makes the relevant theoretical foundation of the convergence property of the algorithm.
In Chapter 6, a cellular ant algorithm for solving multi-objective function optimization is presented. The algorithm can be used for solving the multi-objective function and discrete systems optimization. The simulation results show that the algorithm can efficiently reach the true Pareto frontier.
In short, the research results of the dissertation theoretically provides a new kind algorithm for NP-hard problems and gives convergence proof of the algorithm. Practically, the dissertation develops a series of strategies for solving different systems optimization problems.
引文
[1] Cook, S. A. The complexity of theorem proving procedures. Proceedings of the Third ACM Symposium on the Theory of Computing, 1971. 151-158.
[2] Alsuwaiyel, M.H. Algorithms Design Techniques and Analysis. Singapore: World Scientific Publishing Co.Pte.Ltd.,1999.
[3] Colorni,A, Dorigo M., Maffioli M..et al., Heuristics From Nature for Hard Combinatorial Optimization Problems. International Transactions in Operational Research, 1996, 3(1): 1-21.
[4] Syslo, M.M, Deo N., Kowalik JS. Discrete Optimization Algorithms. Englewood Cliffs, New Jersey: Prentice-Hall,Inc., 1983.
[5] Hochbaum,D.S.(eds.), Approximation Algorithms for NP-hard Problems.Boston, MA: PWS Publishing Company, 1997.
[6]王正志.进化计算.长沙:国防科技大学出版社,2000.
[7] Brualdi,R.A.,Introductory Combinatorics. New Jersey: Prentice-Hall,Inc., 1999.
[8] Kirkpatrick S , Gelatt Jr C D, Vecchi M P. Optimization by stimulated annealing.Science,1983, 220(4598):671-680.
[9] Koulamas,C.et al., A Survey of Simulated Annealing Applications to Operations Research Problems, Omega, 1994, 22(1): 41-56.
[10] Lin,F.T.et al., Applying the Genetic Approach to Simulated Annealing in Solving Some NP-Hard Problems, IEEE Trans. on SMC, 1993, 23 (6): 1752-1767.
[11]邢文训,谢金星.现代优化计算方法.北京:清华大学出版社,1999.
[12] Glover F. Future paths for integer programming and links to artificial intelligence. Computers and Operations Research, 1986,13(5):533-549.
[13] Glover F. Tabu search: part I. ORSA Journal on Computing, 1989,1(3):190-206.
[14] Colorni,A.,Dorigo,M.,Maniezzo,V., Distributed Optimization by Ant Colonies. Proceedings of the First European Conference on Artificial Life, Paris,France: Elsevier Publishing, 1991.134-142.
[15]王小平,曹立明.遗传算法——理论、应用与软件实现.西安:西安交通大学出版社,2002.
[16] Baraglia R , Hidalgo J I , Perego R. A hybrid heuristic for the traveling salesman problem. IEEE Trans on Evolutionary Computation ,2001,5(6):613-622.
[17] Moon Chiung,Kim Jongsoo ,Choi Gyunghyun ,et al . An efficient genetic algorithm for the traveling salesman problem with precedence constraint. European Journal of Operational Research ,2002 ,140(3) :606-617.
[18] Zbigniew Michalewicz David B.Fogel著,曹宏庆,李艳,董红斌,吴志健译.如何求解问题——现代启发式方法.北京:中国水利水电出版社,2003.
[19]马良.离散系统优化的蚂蚁算法研究.上海交通大学博士学位论文,1999.
[20]王陵.智能优化算法及其应用.北京:清华大学出版社,2001
[21]宁爱兵.竞争决策算法及其在组合优化中的应用.上海理工大学博士学位论文,2005
[22]段海滨.蚁群算法原理及其应用.北京:科学出版社,2005
[23]玄光男,程润伟,于歆杰,周根贵译.遗传算法与工程优化.北京:清华大学出版社,2004.
[24]焦李成.神经网络计算.西安:西安电子科技大学出版社, 1995.
[25]马良.来自昆虫世界的寻优策略--蚂蚁算法.自然杂志.1999,21(3):161-163.
[26]马良,项培军.蚂蚁算法在组合优化中的应用.管理科学学报.2004,4(2):32-37.
[27]张铃,程军盛.松散的脑袋——群体智能的数学模型.模式识别与人工智能. 2003, 16 (1): 1-5.
[28] Cotta,C., Aldana J.F., Nebro A.J.et al. Hybridizing Genetic Algorithms with Branch and Bound Techniques for the Resolution of the TSP. In Proceedings of the International Conference on Artificial Neural Nets and Genetic Algorithms,Wien, New York: Sping-Verlag, 1995.277-280.
[29]丁建立,陈增强,袁著祉.基于自适应蚂蚁算法的动态最优路由选择.控制与决策, 2003, 18(6):751-753.
[30] Ryan M G, Richard S B. Dynamic wavelength routing in WDM networks via ant colony optimization .Proc of 3rd Int Workshop ANTS. Brussels, 2002.250-255.
[31]吕勇,赵光宙,苏凡军.基于蚁群算法的自适应动态路由算法.浙江大学学报(工学版),2005,39(10):1537-1540
[32] Li Y J, Wu T J. A nested ant colony algorithm for hybrid production scheduling .Proc of the American Control Conf. Anchorage, 2002. 1123-1128.
[33] Li Y J, Wu T J. A nested hybrid ant colony algorithm for hybrid production scheduling problems. Acta Automatica Sinica, 2003, 29(1):95-101.
[34]梁静,钱省三,马良.基于双层蚂蚁算法的半导体炉管制程批调度研究.系统工程理论与实践,2005,25(12):98-103
[35]王志刚,杨丽徙,陈根永.基于蚁群算法的配电网网架优化规划方法.电力系统及其自动化学报, 2002,14(6):73-76.
[36] Teng J H, Liu Y H. A novel ACS-based optimum switch relocation method. IEEE Trans on Power Systems, 2003, 18(1):113-120.
[37]金飞虎,洪炳熔,高庆吉.基于蚁群算法的自由飞行空间机器人路径规划[J],机器人, 2003, 24(6):526-529.
[38]樊晓平,罗熊,易晟等.复杂环境下基于蚁群优化算法的机器人路径规划.控制与决策, 2004,19(2):166-170.
[39]朱庆保.动态复杂环境下的机器人路径规划蚂蚁预测算法.计算机学报,2005,28(11): 1898—1906
[40]马良,姚俭,范炳全.蚂蚁算法在交通配流中的应用.科技通报, 2003, 19(5):377-380.
[41]崔雪丽,马良,范炳全.车辆路径问题(VRP)的蚂蚁搜索算法. 2004,19(4):418-422
[42]尹晓峰,刘春煌,张惟皎.基于MATLAB的混合型蚁群算法求解车辆路径问题.计算机工程与应用,2005,41(35):207-209
[43]孙焘,王秀坤,刘业欣等,一种简单蚂蚁算法及其收敛性分析[J],小型微型计算机系统,2003,21 (8):1524-1526.
[44]陈棱,沈洁,秦玲.蚁群算法求解连续空间优化问题的一种方法.软件学报, 2002, 13 (12): 2317-2322
[45]丁建立,陈增强,袁著祉,基于动态聚类邻域分区的并行蚁群优化算法,系统工程理论与实践, 2003, 23 (9): 105-110
[46]段海滨,王道波,朱家强等.蚁群算法理论及应用研究的进展,控制与决策,2004,19(12):1321-1340
[47] Von Neumann J, Burks A W. Theory of self-reproducing automata. Urbana: Illinois,University of Illinois Press,1966
[48] Wolfram,S., Universality and Complexty in Cellular Automata, Physica D, 1984, 10 (1): 1-35
[49] Wolfram S. Theory and Application of Cellular Automata. Singapore: The World Scientific Publishing Co Ltd, 1986.
[50] [英]肖帕德,德罗斯著;祝玉学,赵学龙译.物理系统的元胞自动机模拟.北京:清华大学出版社, 2003
[51]周成虎,孙战利,谢一春.地理元胞自动机研究.北京:科学出版社,2000:26-51
[52]谢惠民.复杂性与动力系统.上海:上海科技教育出版社,1994.151-185
[53]顾国庆,范炳全,许伯铭.交通系统的元胞自动机模拟.系统工程理论方法应用,1995, 4(1): 12- 17
[54]应尚军,魏一鸣,范英等.基于元胞自动机的股票市场投资行为模拟.系统工程学报,2001,16(5):382- 388.
[55]陈荣,余亮,何宜柱.元胞自动机模拟在市场营销中的应用.预测,2000,(2):57- 60.
[56]田志友,王浣尘,吴瑞明.区域市场连锁经营选址与布局的元胞自动机模拟.系统工程理论方法应用,2005,14(1):50-54
[57]朱刚,马良.基于元胞自动机的物流系统选址模型.上海理工大学学报,2006,Vol.28(1):19-22
[58]谢政,李建平.网络算法与复杂性理论.长沙:国防科技大学出版社,1995
[59]王晓东.算法设计与分析.北京:清华大学出版社,2003
[60] Lawler,E.L.et al.(eds.). The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization. Chichester, New York: J.Wiley&Sons, 1986.
[61] D Costa and A Hertz, Ants can colour graphs. Journal of Operational Research Society,1997,48(3):295-305.
[62] Applegate D, Cook W. A compuatational study of the job-shop scheduling problem. ORSA Journal on Computing,1991,3(2):149-156.
[63] Maniezzo V.,Colorni A..,The Ant System Applied to the Quadratic Assignment Problem. IEEE Transactions on Knowledge and Data Engineering, 1999, 11(5): 769-778.
[64] Volgenant,A., A Lagrangean approach to the degree-constrained minimum spanning tree problem. European Journal of Operational Research, 1989, 39(3): 325-331.
[65] Kennedy J, Eberhart R., Particle Swarm Optimization. IEEE International Conference on Neural Networks, Perth, Australia, 1995. 1943-1948.
[66]李爱国,覃征,鲍复民,贺升平.粒子群优化算法.计算机工程与应用,2002,38(21):1-3.
[67]袁晓辉.王乘.袁艳斌.张勇传.一种求解机组组合问题的新型改进粒子群方法.电力系统自动化,2005,29(1):34-38.
[68] Lipton R J. DNA solution of hard computational problems. Science, 1995, 268(28):542-545.
[69]李人厚,余文.关于DNA计算的基本原理与探讨.计算机学报,2001,24(9):972-978.
[70]张镇九.张昭理.量子计算机进展.计算机工程,2004,30(8):7-9.
[71]周奇年.量子计算与量子计算机.浙江工程学院学报,2004,19(4):229-235.
[72]殷人昆,陶永雷,谢若阳等.数据结构(用面向对象方法与C++描述).北京:清华大学出版社,1999:23-24
[73]云庆夏.进化算法.北京:冶金工业出版社,2000. 22-30
[74]马良.基于蚂蚁算法的函数优化.控制与决策,2002,17(增刊):719-722
[75]张彤,王宏伟,王子才等.变尺度混沌优化方法及其应用.控制与决策, 1999,14 (3):285-287
[76]姚俊峰,梅炽,彭小奇等.混沌遗传算法及其应用.系统工程,2001,19(1):70-74.
[77]李敏强,寇纪松.遗传算法的一种非单调适应值标度变换方法.自然科学进展,2001, 11 (5):530-536
[78] GambaNella L M, Dorigo M.Solving symmetric and asymmetric TSPs by ant colonies . Proceedings of IEEE International Conference on Evolutionary Computation, IEEE—EC 96, IEEE Preg, 1996.622-627.
[79] Bentley. J.L., Fast Algorithms for Geometric Traveling Salesman Problems. ORSA Journal on Computing, 1992, 4(4):387-411.
[80]陈贤富,庄镇泉.遗传算法的自适应进化策略及TSP问题的遗传优化.电子学报, 1997,25(7):111-114.
[81]马良. TSP及其扩展问题的混合型启发式算法.上海理工大学学报, 1999, 21(1): 25-28.
[82]卢欣,李衍达. TSP问题分层求解算法的复杂度研究.自动化学报, 1999, 25 (2): 279-282.
[83] Dorigo,M.,Gambardella,L.M., Ant Colony System: A Cooperative Learning Approach to the Travelling Salesman Problem, IEEE Trans. on Evolutionary Computation, 1997, 1 (1): 53-66.
[84] Liang Yanchun,Ge Hongwei, Zhou Chunguang. et al.. Solving taveling salesman problems by gnetic algorithms. Progress in natural science, 2003, 13(2):135-141.
[85] Stutzle,T., Hoos,H., The MAX-MIN Ant System and Local Search for the Travelling Salesman Problem, Proc. of ICEC'97─1997 IEEE 4th Int. Conf. on Evolutionary Computation, IEEE Press, 1997: 308-313
[86] Lin S. , Kernighan B.W. . An Effective Heuristic Algorithm for the TravellingSalesman Problem. Operations Research, 1973,21(2):498-516.
[87]孙力娟,王良俊,王汝传.改进的蚁群算法及其在TSP中的应用研究.通信学报, 2004, 25(10):111-116.
[88]杨照选,贺建民,周晓兰.一种改进的遗传算法解决旅行商问题.解放军理工大学学报(自然科学版), 2004,5(5):30-33.
[89] Béla Bollobás. Modern Graph Theory. New York: Springer-Verlag. 1998.
[90]左孝凌,李为监,刘永才.离散数学.上海:上海科学技术文献出版社,1982.
[91]徐俊明.图论及其应用.合肥:中国科学技术出版社,1998.
[92]谢政,戴丽.组合图论.长沙:国防科技大学出版社,2003.
[93]王树禾.图论.北京:科学出版社,2004.
[94]卢开澄,卢华明.图论及其应用.北京:清华大学出版社(第二版),1995.
[95]陈志平,徐宗平.计算机数学.北京:科学出版社,2001.
[96]卢开澄.计算机算法导引.北京:清华大学出版社,1996.
[97] LIANG Yanchun,GE Hongwei,ZHOU Chunguang, et al. Solving travelling salesman problems by genetic algorithms.Progress in Natural Science,2003, 13(2) :135-141.
[98]宁爱兵,马良.基于快速下界估算的瓶颈旅行商问题竞争决策算法.上海理工大学学报, 2005, 27 (3): 223-228
[99]宁爱兵,马良.最小比率旅行商(MRTSP)问题竞争决策算法.计算机工程与应用, 2005, 41 (11): 30-32
[100] Baker, E.K. An Exact Algorithm for the Time-constrained Traveling Salesman Problem. Opns. Res., 1983, 31 (5): 938-945
[101]马良.一类非线性TSP模型及其应用.中国管理科学, 1993, 1 (3): 56-59
[102] Gutjahr W J. A graph-based ant system and its convergence . Future Generation Computer Systems,2000,16(8):873-888
[103] Stuezle T,Dorigo M. A short convergence proof for a class of ant colony optimization algorithms . IEEE Transactions on Evolutionary Computation, 2002,6(4):358-365
[104] Gutjahr W J. ACO algorithms with guaranteed convergence to the optimal solution. Information Processing Letters,2002,82:145-153
[105]段海滨,王道波.蚁群算法的全局收敛性研究及改进.系统工程与电子技术,2004,25(10):1506-1509
[106]丁建立,陈增强,袁著祉.遗传算法与蚂蚁算法融合的马尔可夫收敛性分析.自动化学报,2004,30(4):629-634.
[107] Amr.Badr,Ahmed.Fahmy.A proof of convergence for ant algorithms. Information Sciences,2004,160:267-279.
[108] G.Sebastiani,G.L.Torrisi. An extended ant colony algorithm and its convergence analysis. Methodology and Computing in Applied Probability, 2005, 7: 249–263.
[109]侯云鹤,熊信艮,吴耀武.基于广义蚁群算法的电力系统经济负荷分配.中国电机工程学报, 2003, 23(3):59-64.
[110]夏道行等.实变函数论与泛函分析.北京:人民教育出版社,1979
[111]王宗尧等.应用泛函分析.上海:华东理工大学出版社,2002
[112]卢同善.随机泛函分析及应用.青岛海洋大学出版社,1990:44– 113
[113]张石生,不动点理论及应用[M],重庆出版社,1984:350– 413
[114] C. A. Coello Coello and G. Toscano Pulido. Multiobjective optimization using a micro-genetic algorithm, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO2001). Morgan Kaufmann Publishers: San Francisco, CA, 2001, pp. 274–282.
[115] MU Shengjing,SU Hongye,WANG Yuexuan, et al. ,An efficient evolutionary multi-objective optimization algorithm,Proceedings of the IEEE Congress on Evolutionary Computation (CEC2003).Canberra:IEEE Press,2003,914920
[116]王跃宣,刘连臣,牟盛静等.处理带约束的多目标优化进化算法.清华大学学报(自然科学版),2005,Vol.45(1): 103-106
[117]张勇德,黄莎白.多目标优化问题的蚁群算法研究.控制与决策,2005,Vol.20(2):170-173,178
[118] Tung,C.T. . A Multicriteria Pareto-Optimal Algorithm for the Travelling Salesman Problem. Asia-Pacific J. of Opnl. Res., 1994, 11 (1): 103-115
[119]马良.多目标平面选址问题的模拟退火算法.系统工程理论与实践, 1997, 17 (3): 70-73
[120]马良,蒋馥.多目标旅行商售货员问题的蚂蚁算法求解.系统工程理论方法应用,1999,8(4):23-27
[121]游道明,陈坚.用蚂蚁算法解决多目标TSP问题.小型微型计算机系统,2003,24(10):1808-1811
[122]《运筹学》教材编写组.运筹学.北京:清华大学出版社,2005:440-447
[123]林锉云,董加礼.多目标优化的方法与理论.长春:吉林教育出版社,1992:55-167
[124] Eckart Zitzler, Kalyanmoy Deb,Lothar Thiele. Comparison of multiobjective evolutionary algorithms: Empirical results .Evolutionary Computation, 2000,8(2):173-195
[2] Alsuwaiyel, M.H. Algorithms Design Techniques and Analysis. Singapore: World Scientific Publishing Co.Pte.Ltd.,1999.
[3] Colorni,A, Dorigo M., Maffioli M..et al., Heuristics From Nature for Hard Combinatorial Optimization Problems. International Transactions in Operational Research, 1996, 3(1): 1-21.
[4] Syslo, M.M, Deo N., Kowalik JS. Discrete Optimization Algorithms. Englewood Cliffs, New Jersey: Prentice-Hall,Inc., 1983.
[5] Hochbaum,D.S.(eds.), Approximation Algorithms for NP-hard Problems.Boston, MA: PWS Publishing Company, 1997.
[6]王正志.进化计算.长沙:国防科技大学出版社,2000.
[7] Brualdi,R.A.,Introductory Combinatorics. New Jersey: Prentice-Hall,Inc., 1999.
[8] Kirkpatrick S , Gelatt Jr C D, Vecchi M P. Optimization by stimulated annealing.Science,1983, 220(4598):671-680.
[9] Koulamas,C.et al., A Survey of Simulated Annealing Applications to Operations Research Problems, Omega, 1994, 22(1): 41-56.
[10] Lin,F.T.et al., Applying the Genetic Approach to Simulated Annealing in Solving Some NP-Hard Problems, IEEE Trans. on SMC, 1993, 23 (6): 1752-1767.
[11]邢文训,谢金星.现代优化计算方法.北京:清华大学出版社,1999.
[12] Glover F. Future paths for integer programming and links to artificial intelligence. Computers and Operations Research, 1986,13(5):533-549.
[13] Glover F. Tabu search: part I. ORSA Journal on Computing, 1989,1(3):190-206.
[14] Colorni,A.,Dorigo,M.,Maniezzo,V., Distributed Optimization by Ant Colonies. Proceedings of the First European Conference on Artificial Life, Paris,France: Elsevier Publishing, 1991.134-142.
[15]王小平,曹立明.遗传算法——理论、应用与软件实现.西安:西安交通大学出版社,2002.
[16] Baraglia R , Hidalgo J I , Perego R. A hybrid heuristic for the traveling salesman problem. IEEE Trans on Evolutionary Computation ,2001,5(6):613-622.
[17] Moon Chiung,Kim Jongsoo ,Choi Gyunghyun ,et al . An efficient genetic algorithm for the traveling salesman problem with precedence constraint. European Journal of Operational Research ,2002 ,140(3) :606-617.
[18] Zbigniew Michalewicz David B.Fogel著,曹宏庆,李艳,董红斌,吴志健译.如何求解问题——现代启发式方法.北京:中国水利水电出版社,2003.
[19]马良.离散系统优化的蚂蚁算法研究.上海交通大学博士学位论文,1999.
[20]王陵.智能优化算法及其应用.北京:清华大学出版社,2001
[21]宁爱兵.竞争决策算法及其在组合优化中的应用.上海理工大学博士学位论文,2005
[22]段海滨.蚁群算法原理及其应用.北京:科学出版社,2005
[23]玄光男,程润伟,于歆杰,周根贵译.遗传算法与工程优化.北京:清华大学出版社,2004.
[24]焦李成.神经网络计算.西安:西安电子科技大学出版社, 1995.
[25]马良.来自昆虫世界的寻优策略--蚂蚁算法.自然杂志.1999,21(3):161-163.
[26]马良,项培军.蚂蚁算法在组合优化中的应用.管理科学学报.2004,4(2):32-37.
[27]张铃,程军盛.松散的脑袋——群体智能的数学模型.模式识别与人工智能. 2003, 16 (1): 1-5.
[28] Cotta,C., Aldana J.F., Nebro A.J.et al. Hybridizing Genetic Algorithms with Branch and Bound Techniques for the Resolution of the TSP. In Proceedings of the International Conference on Artificial Neural Nets and Genetic Algorithms,Wien, New York: Sping-Verlag, 1995.277-280.
[29]丁建立,陈增强,袁著祉.基于自适应蚂蚁算法的动态最优路由选择.控制与决策, 2003, 18(6):751-753.
[30] Ryan M G, Richard S B. Dynamic wavelength routing in WDM networks via ant colony optimization .Proc of 3rd Int Workshop ANTS. Brussels, 2002.250-255.
[31]吕勇,赵光宙,苏凡军.基于蚁群算法的自适应动态路由算法.浙江大学学报(工学版),2005,39(10):1537-1540
[32] Li Y J, Wu T J. A nested ant colony algorithm for hybrid production scheduling .Proc of the American Control Conf. Anchorage, 2002. 1123-1128.
[33] Li Y J, Wu T J. A nested hybrid ant colony algorithm for hybrid production scheduling problems. Acta Automatica Sinica, 2003, 29(1):95-101.
[34]梁静,钱省三,马良.基于双层蚂蚁算法的半导体炉管制程批调度研究.系统工程理论与实践,2005,25(12):98-103
[35]王志刚,杨丽徙,陈根永.基于蚁群算法的配电网网架优化规划方法.电力系统及其自动化学报, 2002,14(6):73-76.
[36] Teng J H, Liu Y H. A novel ACS-based optimum switch relocation method. IEEE Trans on Power Systems, 2003, 18(1):113-120.
[37]金飞虎,洪炳熔,高庆吉.基于蚁群算法的自由飞行空间机器人路径规划[J],机器人, 2003, 24(6):526-529.
[38]樊晓平,罗熊,易晟等.复杂环境下基于蚁群优化算法的机器人路径规划.控制与决策, 2004,19(2):166-170.
[39]朱庆保.动态复杂环境下的机器人路径规划蚂蚁预测算法.计算机学报,2005,28(11): 1898—1906
[40]马良,姚俭,范炳全.蚂蚁算法在交通配流中的应用.科技通报, 2003, 19(5):377-380.
[41]崔雪丽,马良,范炳全.车辆路径问题(VRP)的蚂蚁搜索算法. 2004,19(4):418-422
[42]尹晓峰,刘春煌,张惟皎.基于MATLAB的混合型蚁群算法求解车辆路径问题.计算机工程与应用,2005,41(35):207-209
[43]孙焘,王秀坤,刘业欣等,一种简单蚂蚁算法及其收敛性分析[J],小型微型计算机系统,2003,21 (8):1524-1526.
[44]陈棱,沈洁,秦玲.蚁群算法求解连续空间优化问题的一种方法.软件学报, 2002, 13 (12): 2317-2322
[45]丁建立,陈增强,袁著祉,基于动态聚类邻域分区的并行蚁群优化算法,系统工程理论与实践, 2003, 23 (9): 105-110
[46]段海滨,王道波,朱家强等.蚁群算法理论及应用研究的进展,控制与决策,2004,19(12):1321-1340
[47] Von Neumann J, Burks A W. Theory of self-reproducing automata. Urbana: Illinois,University of Illinois Press,1966
[48] Wolfram,S., Universality and Complexty in Cellular Automata, Physica D, 1984, 10 (1): 1-35
[49] Wolfram S. Theory and Application of Cellular Automata. Singapore: The World Scientific Publishing Co Ltd, 1986.
[50] [英]肖帕德,德罗斯著;祝玉学,赵学龙译.物理系统的元胞自动机模拟.北京:清华大学出版社, 2003
[51]周成虎,孙战利,谢一春.地理元胞自动机研究.北京:科学出版社,2000:26-51
[52]谢惠民.复杂性与动力系统.上海:上海科技教育出版社,1994.151-185
[53]顾国庆,范炳全,许伯铭.交通系统的元胞自动机模拟.系统工程理论方法应用,1995, 4(1): 12- 17
[54]应尚军,魏一鸣,范英等.基于元胞自动机的股票市场投资行为模拟.系统工程学报,2001,16(5):382- 388.
[55]陈荣,余亮,何宜柱.元胞自动机模拟在市场营销中的应用.预测,2000,(2):57- 60.
[56]田志友,王浣尘,吴瑞明.区域市场连锁经营选址与布局的元胞自动机模拟.系统工程理论方法应用,2005,14(1):50-54
[57]朱刚,马良.基于元胞自动机的物流系统选址模型.上海理工大学学报,2006,Vol.28(1):19-22
[58]谢政,李建平.网络算法与复杂性理论.长沙:国防科技大学出版社,1995
[59]王晓东.算法设计与分析.北京:清华大学出版社,2003
[60] Lawler,E.L.et al.(eds.). The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization. Chichester, New York: J.Wiley&Sons, 1986.
[61] D Costa and A Hertz, Ants can colour graphs. Journal of Operational Research Society,1997,48(3):295-305.
[62] Applegate D, Cook W. A compuatational study of the job-shop scheduling problem. ORSA Journal on Computing,1991,3(2):149-156.
[63] Maniezzo V.,Colorni A..,The Ant System Applied to the Quadratic Assignment Problem. IEEE Transactions on Knowledge and Data Engineering, 1999, 11(5): 769-778.
[64] Volgenant,A., A Lagrangean approach to the degree-constrained minimum spanning tree problem. European Journal of Operational Research, 1989, 39(3): 325-331.
[65] Kennedy J, Eberhart R., Particle Swarm Optimization. IEEE International Conference on Neural Networks, Perth, Australia, 1995. 1943-1948.
[66]李爱国,覃征,鲍复民,贺升平.粒子群优化算法.计算机工程与应用,2002,38(21):1-3.
[67]袁晓辉.王乘.袁艳斌.张勇传.一种求解机组组合问题的新型改进粒子群方法.电力系统自动化,2005,29(1):34-38.
[68] Lipton R J. DNA solution of hard computational problems. Science, 1995, 268(28):542-545.
[69]李人厚,余文.关于DNA计算的基本原理与探讨.计算机学报,2001,24(9):972-978.
[70]张镇九.张昭理.量子计算机进展.计算机工程,2004,30(8):7-9.
[71]周奇年.量子计算与量子计算机.浙江工程学院学报,2004,19(4):229-235.
[72]殷人昆,陶永雷,谢若阳等.数据结构(用面向对象方法与C++描述).北京:清华大学出版社,1999:23-24
[73]云庆夏.进化算法.北京:冶金工业出版社,2000. 22-30
[74]马良.基于蚂蚁算法的函数优化.控制与决策,2002,17(增刊):719-722
[75]张彤,王宏伟,王子才等.变尺度混沌优化方法及其应用.控制与决策, 1999,14 (3):285-287
[76]姚俊峰,梅炽,彭小奇等.混沌遗传算法及其应用.系统工程,2001,19(1):70-74.
[77]李敏强,寇纪松.遗传算法的一种非单调适应值标度变换方法.自然科学进展,2001, 11 (5):530-536
[78] GambaNella L M, Dorigo M.Solving symmetric and asymmetric TSPs by ant colonies . Proceedings of IEEE International Conference on Evolutionary Computation, IEEE—EC 96, IEEE Preg, 1996.622-627.
[79] Bentley. J.L., Fast Algorithms for Geometric Traveling Salesman Problems. ORSA Journal on Computing, 1992, 4(4):387-411.
[80]陈贤富,庄镇泉.遗传算法的自适应进化策略及TSP问题的遗传优化.电子学报, 1997,25(7):111-114.
[81]马良. TSP及其扩展问题的混合型启发式算法.上海理工大学学报, 1999, 21(1): 25-28.
[82]卢欣,李衍达. TSP问题分层求解算法的复杂度研究.自动化学报, 1999, 25 (2): 279-282.
[83] Dorigo,M.,Gambardella,L.M., Ant Colony System: A Cooperative Learning Approach to the Travelling Salesman Problem, IEEE Trans. on Evolutionary Computation, 1997, 1 (1): 53-66.
[84] Liang Yanchun,Ge Hongwei, Zhou Chunguang. et al.. Solving taveling salesman problems by gnetic algorithms. Progress in natural science, 2003, 13(2):135-141.
[85] Stutzle,T., Hoos,H., The MAX-MIN Ant System and Local Search for the Travelling Salesman Problem, Proc. of ICEC'97─1997 IEEE 4th Int. Conf. on Evolutionary Computation, IEEE Press, 1997: 308-313
[86] Lin S. , Kernighan B.W. . An Effective Heuristic Algorithm for the TravellingSalesman Problem. Operations Research, 1973,21(2):498-516.
[87]孙力娟,王良俊,王汝传.改进的蚁群算法及其在TSP中的应用研究.通信学报, 2004, 25(10):111-116.
[88]杨照选,贺建民,周晓兰.一种改进的遗传算法解决旅行商问题.解放军理工大学学报(自然科学版), 2004,5(5):30-33.
[89] Béla Bollobás. Modern Graph Theory. New York: Springer-Verlag. 1998.
[90]左孝凌,李为监,刘永才.离散数学.上海:上海科学技术文献出版社,1982.
[91]徐俊明.图论及其应用.合肥:中国科学技术出版社,1998.
[92]谢政,戴丽.组合图论.长沙:国防科技大学出版社,2003.
[93]王树禾.图论.北京:科学出版社,2004.
[94]卢开澄,卢华明.图论及其应用.北京:清华大学出版社(第二版),1995.
[95]陈志平,徐宗平.计算机数学.北京:科学出版社,2001.
[96]卢开澄.计算机算法导引.北京:清华大学出版社,1996.
[97] LIANG Yanchun,GE Hongwei,ZHOU Chunguang, et al. Solving travelling salesman problems by genetic algorithms.Progress in Natural Science,2003, 13(2) :135-141.
[98]宁爱兵,马良.基于快速下界估算的瓶颈旅行商问题竞争决策算法.上海理工大学学报, 2005, 27 (3): 223-228
[99]宁爱兵,马良.最小比率旅行商(MRTSP)问题竞争决策算法.计算机工程与应用, 2005, 41 (11): 30-32
[100] Baker, E.K. An Exact Algorithm for the Time-constrained Traveling Salesman Problem. Opns. Res., 1983, 31 (5): 938-945
[101]马良.一类非线性TSP模型及其应用.中国管理科学, 1993, 1 (3): 56-59
[102] Gutjahr W J. A graph-based ant system and its convergence . Future Generation Computer Systems,2000,16(8):873-888
[103] Stuezle T,Dorigo M. A short convergence proof for a class of ant colony optimization algorithms . IEEE Transactions on Evolutionary Computation, 2002,6(4):358-365
[104] Gutjahr W J. ACO algorithms with guaranteed convergence to the optimal solution. Information Processing Letters,2002,82:145-153
[105]段海滨,王道波.蚁群算法的全局收敛性研究及改进.系统工程与电子技术,2004,25(10):1506-1509
[106]丁建立,陈增强,袁著祉.遗传算法与蚂蚁算法融合的马尔可夫收敛性分析.自动化学报,2004,30(4):629-634.
[107] Amr.Badr,Ahmed.Fahmy.A proof of convergence for ant algorithms. Information Sciences,2004,160:267-279.
[108] G.Sebastiani,G.L.Torrisi. An extended ant colony algorithm and its convergence analysis. Methodology and Computing in Applied Probability, 2005, 7: 249–263.
[109]侯云鹤,熊信艮,吴耀武.基于广义蚁群算法的电力系统经济负荷分配.中国电机工程学报, 2003, 23(3):59-64.
[110]夏道行等.实变函数论与泛函分析.北京:人民教育出版社,1979
[111]王宗尧等.应用泛函分析.上海:华东理工大学出版社,2002
[112]卢同善.随机泛函分析及应用.青岛海洋大学出版社,1990:44– 113
[113]张石生,不动点理论及应用[M],重庆出版社,1984:350– 413
[114] C. A. Coello Coello and G. Toscano Pulido. Multiobjective optimization using a micro-genetic algorithm, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO2001). Morgan Kaufmann Publishers: San Francisco, CA, 2001, pp. 274–282.
[115] MU Shengjing,SU Hongye,WANG Yuexuan, et al. ,An efficient evolutionary multi-objective optimization algorithm,Proceedings of the IEEE Congress on Evolutionary Computation (CEC2003).Canberra:IEEE Press,2003,914920
[116]王跃宣,刘连臣,牟盛静等.处理带约束的多目标优化进化算法.清华大学学报(自然科学版),2005,Vol.45(1): 103-106
[117]张勇德,黄莎白.多目标优化问题的蚁群算法研究.控制与决策,2005,Vol.20(2):170-173,178
[118] Tung,C.T. . A Multicriteria Pareto-Optimal Algorithm for the Travelling Salesman Problem. Asia-Pacific J. of Opnl. Res., 1994, 11 (1): 103-115
[119]马良.多目标平面选址问题的模拟退火算法.系统工程理论与实践, 1997, 17 (3): 70-73
[120]马良,蒋馥.多目标旅行商售货员问题的蚂蚁算法求解.系统工程理论方法应用,1999,8(4):23-27
[121]游道明,陈坚.用蚂蚁算法解决多目标TSP问题.小型微型计算机系统,2003,24(10):1808-1811
[122]《运筹学》教材编写组.运筹学.北京:清华大学出版社,2005:440-447
[123]林锉云,董加礼.多目标优化的方法与理论.长春:吉林教育出版社,1992:55-167
[124] Eckart Zitzler, Kalyanmoy Deb,Lothar Thiele. Comparison of multiobjective evolutionary algorithms: Empirical results .Evolutionary Computation, 2000,8(2):173-195
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |