毕业论文（设计）基于蚁群算法的计算机仿真技术.doc
约33页DOC格式手机打开展开
毕业论文（设计）基于蚁群算法的计算机仿真技术,33页共计17591字摘 要自意大利学者m. dorigo于1991年提出蚁群算法后，该算法引起了学者们的极大关注，在短短十多年的时间里，已在组合优化、网络路由、函数优化、数据挖掘、机器人路径规划等领域获得了广泛应用，并取得了较好的效果。本文首先讨论了该算法的基本原理，接着介...
内容介绍
此文档由会员 bfxqt 发布
毕业论文（设计）基于蚁群算法的计算机仿真技术
33页共计17591字
摘 要
自意大利学者M. Dorigo于1991年提出蚁群算法后，该算法引起了学者们的极大关注，在短短十多年的时间里，已在组合优化、网络路由、函数优化、数据挖掘、机器人路径规划等领域获得了广泛应用，并取得了较好的效果。本文首先讨论了该算法的基本原理，接着介绍了旅行商问题，然后对蚁群算法及其二种改进算法进行了分析，并通过计算机仿真来说明蚁群算法基本原理，然后分析了聚类算法原理和蚁群聚类算法的数学模型，通过调整传统的蚁群算法构建了求解聚类问题的蚁群聚类算法。最后，本文还研究了一种依赖信息素解决聚类问题的蚁群聚类算法，并把此蚁群聚类算法应用到对人工数据进行分类，还利用该算法对2005年中国24所高校综合实力进行分类，得到的分类结果与实际情况相符，说明了蚁群算法在聚类分析中能够收到较为理想的结果。
目 录
1 引 言 1
1.1 群智能 1
1.2 蚁群算法 2
1.3 聚类问题 3
1.4 本文研究工作 4
2 蚁群算法原理及算法描述 5
2.1 蚁群算法原理 5
2.2 蚁群优化的原理分析 7
2.3 算法基本流程 9
2.4 蚁群觅食过程计算机动态模拟 10
2.5 人工蚂蚁与真实蚂蚁的对比 12
2.6 本章小结 13
3 基本蚁群优化算法及其改进 14
3.1 旅行商问题 14
3.2 基本蚁群算法及其典型改进 14
3.2.1 蚂蚁系统 14
3.2.2 蚁群系统 15
3.2.3 最大-最小蚂蚁系统 15
3.3 基本蚁群算法仿真实验 15
3.3.1 软硬件环境 15
3.3.2 重要参数设置 15
3.3.3 仿真试验 16
3.4 本章小结 18
4 蚁群聚类算法及其应用 19
4.1 聚类问题 19
4.2 蚁群聚类算法的数学模型 20
4.3 蚁群聚类算法 20
4.3.1 蚁群聚类算法分析 21
4.3.2 蚁群聚类算法流程 24
4.4 蚁群聚类算法在高校分类中的应用 24
4.5 本章小结 26
5 结论与展望 27
参考文献 28
致 谢 30
【关键词】蚁群算法；计算机仿真；聚类；蚁群聚类
参考文献
[1] Bonabeau E., Dorigo M., and Theraulaz G. Swarmn itelligence. http://swis.epfl.ch/teaching/ swarm_intelligence/ay_2006-07/lecture/SI_06-07_W01_lecture.pdf. 2007-04-15
[2]彭喜元, 彭宇, 戴毓丰. 群智能理论及其应用[J]. 电子学报, 2003, 31(12A): 1982-1987
[3]李志伟. 基于群集智能的蚁群优化算法研究[J]. 计算机工程与设计, 2003, 24(8): 27-29
[4]Lee Z. J., Lee C. Y., and Su S.F. An immunity-based ant colony optimization algorithm for solving weapon-target assignment problem [J], Applied Soft Computing, 2002, 2(1): 39-47
[5]Denbya B., and Hlegarat-Mascle. Swarm intelligence in optimization problems [J]. Nuclear Instruments and Methods in Physics Research, 2003, (502): 364-368
[6]Dorigo M., Maniezzo V., and Alberto C. The Ant System: Optimization by a colony of cooperating agents [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 1996, 26(1): 1-13.
[7]吴启迪, 汪镭. 智能蚁群算法及应用[M]. 上海: 上海科技教育出版社, 2004
[8]Bonabeau E., Dorigo M., and Theraulaz G. Swarm Intelligence: From Natural to Artificial System [M]. New York, NY: Oxford University Press, 1999
[9]Deneubourg J. L., Goss S., Franks N., et al.The dynamics of collective sorting: Robot- like ants and ant-like robots[C]. In: Proceedings of the First international Conference on Simulation of Adaptive haviour, From Animals to Animals, Cambridge MA: MIT Press, 1991. 356-365
[10]杨新斌, 孙京诰, 黄道. 一种进化聚类学习新方法[J]. 计算机工程与应用, 2003, 39(15): 60-62
[11]Deneubourg J. L., Pasteels J. M., and Verhaeghe J. C. Probabilistic Behaviour in Ants: a Strategy of Errors [J]. Journal of Theoretical Biology, 1983, (105): 259-271
[12]Deneubourg J. L., and Goss S. Collective patterns and decision-making [J]. Ethology, Ecology & Evolution, 1989, 1: 295-311,
[13]Goss S., Beckers R., Deneubourg J. L., Aron S., and Pasteels J. M. HowTrail Laying and Trail Following Can Solve Foraging Problems for Ant Colonies[C]. In: Behavioural Mechanisms of Food Selection, R.N.Hughesed, NATO-ASI Series, Berlin: Springer-Verlag,1990.
[14]Deneubourg J. L., Aron S., Goss S., and Pasteels J. M. The self-organizing exploratory pattern of the argentine ant [J], Journal of Insect Behavior, 1990, 3: 159-168
[15]Goss S., Aron S., Deneubourg L., and Pasteels J. M. Self-organized shortcuts in the Argentine ant [J]. Naturwissenschaften, 1989, 76: 579-581
[16]Pasteels J. M., Deneubourg J. L., and Goss S. Self-organization mechanisms in ant societies (I): Trail recruitment to newly discovered food sources [J]. Experientia Supplementum, 1987, 54: 155-175.
[17]Watkins C. Learning with delayed rewards [D]. England: Psychology Department, University of Cambridge,1989
[18]Gambardella L. M., and Dorigo M. Ant-Q: A reinforcement learning approach to the traveling salesman problem[C]. In: Proceedings of the Twelfth International Conference on Machine Learning (ML-95). Palo Alto, CA: Morgan Kaufmann Publishers, 1995. 252-260
[19]Dorigo M., and Gianni D. C. Ant Algorithms for Discrete Optimization [J]. Artificial Life, 1999, 5(3): 137-172
[20]Dorigo M., and Maniezzo V. A Colony Ant System: An Autocatalytic Optimizing Process. Politecnico di Milano, Italy, Technical Report: No. 91-016, 1991
[21]Dorigo M., and 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
[22]Stützle T., and Hoos H. The MAX-MIN ant system and local search for the traveling salesman problem [C]. In: Proceedings of IEEE International Conference on Evolutionary Computation and Evolutionary Programming Conference. Indianapolis, USA: IEEE Press, 1997. 309-314
[23]Stützle T., and 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. Wien: Springer Verlag, 1997. 245-249
[24]Stützle T., and Hoos H. MAX-MIN Ant system and local search for combinatorial optimization problems [M]. In: Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization (editors: S. VoB, S. Martello,I.H.O sman,and C. Roucairol). Boston: Kluwer, 1998. 137-154
[25]Stützle T. MAX-MIN Ant System for Quadratic Assignment Problems[R]. Intellectics Group, Department of Computer Science, Darmstadt University of Technology,Germany, Technical Report: AIDA-97-04, 1997
[26]Deneubourg J. L., Goss S., Franks N., et al. The Dynamics of Collective Sorting: Robot-Like Ant and Ant-Like Robot [C]. In: Proceedings First Conference on Simulation of Adaptive Behavior: From Animals to Animate.Cambridge, MA: MIT Press, 1991. 356-365
[27]Lumer E., and Faieta B. Diversity and adaptation in populations of clustering ants [C]. In: Proc. third international conference on simulation of adaptive behavior: from animals to animats. Cambridge, MA: MIT Press, 1994. 499-508.
[28]Wu B., and Shi Z. A clustering algorithm based on swarm intelligence [C]. In: Proceedings IEEE international conferences on info-tech & info-net. Beijing: IEEE Press, 2001. 58 - 66
[29]Ramos V, Merelo J J. Self-organized stigmergic document maps: environment as a mechanismfor context learning [C]. In : Proceedings 21st Spanish conference on evolutionary and bio-inspired algorithms. Mérida, 2002. 284 -293
[30]Yang Y. and Kamel M. Clustering ensemble using swarm intelligence [C]. In: IEEE swarm intelligence symposium[C]. Piscataway, NJ : IEEE service center , 2003. 65 -71
33页共计17591字
摘 要
自意大利学者M. Dorigo于1991年提出蚁群算法后，该算法引起了学者们的极大关注，在短短十多年的时间里，已在组合优化、网络路由、函数优化、数据挖掘、机器人路径规划等领域获得了广泛应用，并取得了较好的效果。本文首先讨论了该算法的基本原理，接着介绍了旅行商问题，然后对蚁群算法及其二种改进算法进行了分析，并通过计算机仿真来说明蚁群算法基本原理，然后分析了聚类算法原理和蚁群聚类算法的数学模型，通过调整传统的蚁群算法构建了求解聚类问题的蚁群聚类算法。最后，本文还研究了一种依赖信息素解决聚类问题的蚁群聚类算法，并把此蚁群聚类算法应用到对人工数据进行分类，还利用该算法对2005年中国24所高校综合实力进行分类，得到的分类结果与实际情况相符，说明了蚁群算法在聚类分析中能够收到较为理想的结果。
目 录
1 引 言 1
1.1 群智能 1
1.2 蚁群算法 2
1.3 聚类问题 3
1.4 本文研究工作 4
2 蚁群算法原理及算法描述 5
2.1 蚁群算法原理 5
2.2 蚁群优化的原理分析 7
2.3 算法基本流程 9
2.4 蚁群觅食过程计算机动态模拟 10
2.5 人工蚂蚁与真实蚂蚁的对比 12
2.6 本章小结 13
3 基本蚁群优化算法及其改进 14
3.1 旅行商问题 14
3.2 基本蚁群算法及其典型改进 14
3.2.1 蚂蚁系统 14
3.2.2 蚁群系统 15
3.2.3 最大-最小蚂蚁系统 15
3.3 基本蚁群算法仿真实验 15
3.3.1 软硬件环境 15
3.3.2 重要参数设置 15
3.3.3 仿真试验 16
3.4 本章小结 18
4 蚁群聚类算法及其应用 19
4.1 聚类问题 19
4.2 蚁群聚类算法的数学模型 20
4.3 蚁群聚类算法 20
4.3.1 蚁群聚类算法分析 21
4.3.2 蚁群聚类算法流程 24
4.4 蚁群聚类算法在高校分类中的应用 24
4.5 本章小结 26
5 结论与展望 27
参考文献 28
致 谢 30
【关键词】蚁群算法；计算机仿真；聚类；蚁群聚类
参考文献
[1] Bonabeau E., Dorigo M., and Theraulaz G. Swarmn itelligence. http://swis.epfl.ch/teaching/ swarm_intelligence/ay_2006-07/lecture/SI_06-07_W01_lecture.pdf. 2007-04-15
[2]彭喜元, 彭宇, 戴毓丰. 群智能理论及其应用[J]. 电子学报, 2003, 31(12A): 1982-1987
[3]李志伟. 基于群集智能的蚁群优化算法研究[J]. 计算机工程与设计, 2003, 24(8): 27-29
[4]Lee Z. J., Lee C. Y., and Su S.F. An immunity-based ant colony optimization algorithm for solving weapon-target assignment problem [J], Applied Soft Computing, 2002, 2(1): 39-47
[5]Denbya B., and Hlegarat-Mascle. Swarm intelligence in optimization problems [J]. Nuclear Instruments and Methods in Physics Research, 2003, (502): 364-368
[6]Dorigo M., Maniezzo V., and Alberto C. The Ant System: Optimization by a colony of cooperating agents [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 1996, 26(1): 1-13.
[7]吴启迪, 汪镭. 智能蚁群算法及应用[M]. 上海: 上海科技教育出版社, 2004
[8]Bonabeau E., Dorigo M., and Theraulaz G. Swarm Intelligence: From Natural to Artificial System [M]. New York, NY: Oxford University Press, 1999
[9]Deneubourg J. L., Goss S., Franks N., et al.The dynamics of collective sorting: Robot- like ants and ant-like robots[C]. In: Proceedings of the First international Conference on Simulation of Adaptive haviour, From Animals to Animals, Cambridge MA: MIT Press, 1991. 356-365
[10]杨新斌, 孙京诰, 黄道. 一种进化聚类学习新方法[J]. 计算机工程与应用, 2003, 39(15): 60-62
[11]Deneubourg J. L., Pasteels J. M., and Verhaeghe J. C. Probabilistic Behaviour in Ants: a Strategy of Errors [J]. Journal of Theoretical Biology, 1983, (105): 259-271
[12]Deneubourg J. L., and Goss S. Collective patterns and decision-making [J]. Ethology, Ecology & Evolution, 1989, 1: 295-311,
[13]Goss S., Beckers R., Deneubourg J. L., Aron S., and Pasteels J. M. HowTrail Laying and Trail Following Can Solve Foraging Problems for Ant Colonies[C]. In: Behavioural Mechanisms of Food Selection, R.N.Hughesed, NATO-ASI Series, Berlin: Springer-Verlag,1990.
[14]Deneubourg J. L., Aron S., Goss S., and Pasteels J. M. The self-organizing exploratory pattern of the argentine ant [J], Journal of Insect Behavior, 1990, 3: 159-168
[15]Goss S., Aron S., Deneubourg L., and Pasteels J. M. Self-organized shortcuts in the Argentine ant [J]. Naturwissenschaften, 1989, 76: 579-581
[16]Pasteels J. M., Deneubourg J. L., and Goss S. Self-organization mechanisms in ant societies (I): Trail recruitment to newly discovered food sources [J]. Experientia Supplementum, 1987, 54: 155-175.
[17]Watkins C. Learning with delayed rewards [D]. England: Psychology Department, University of Cambridge,1989
[18]Gambardella L. M., and Dorigo M. Ant-Q: A reinforcement learning approach to the traveling salesman problem[C]. In: Proceedings of the Twelfth International Conference on Machine Learning (ML-95). Palo Alto, CA: Morgan Kaufmann Publishers, 1995. 252-260
[19]Dorigo M., and Gianni D. C. Ant Algorithms for Discrete Optimization [J]. Artificial Life, 1999, 5(3): 137-172
[20]Dorigo M., and Maniezzo V. A Colony Ant System: An Autocatalytic Optimizing Process. Politecnico di Milano, Italy, Technical Report: No. 91-016, 1991
[21]Dorigo M., and 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
[22]Stützle T., and Hoos H. The MAX-MIN ant system and local search for the traveling salesman problem [C]. In: Proceedings of IEEE International Conference on Evolutionary Computation and Evolutionary Programming Conference. Indianapolis, USA: IEEE Press, 1997. 309-314
[23]Stützle T., and 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. Wien: Springer Verlag, 1997. 245-249
[24]Stützle T., and Hoos H. MAX-MIN Ant system and local search for combinatorial optimization problems [M]. In: Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization (editors: S. VoB, S. Martello,I.H.O sman,and C. Roucairol). Boston: Kluwer, 1998. 137-154
[25]Stützle T. MAX-MIN Ant System for Quadratic Assignment Problems[R]. Intellectics Group, Department of Computer Science, Darmstadt University of Technology,Germany, Technical Report: AIDA-97-04, 1997
[26]Deneubourg J. L., Goss S., Franks N., et al. The Dynamics of Collective Sorting: Robot-Like Ant and Ant-Like Robot [C]. In: Proceedings First Conference on Simulation of Adaptive Behavior: From Animals to Animate.Cambridge, MA: MIT Press, 1991. 356-365
[27]Lumer E., and Faieta B. Diversity and adaptation in populations of clustering ants [C]. In: Proc. third international conference on simulation of adaptive behavior: from animals to animats. Cambridge, MA: MIT Press, 1994. 499-508.
[28]Wu B., and Shi Z. A clustering algorithm based on swarm intelligence [C]. In: Proceedings IEEE international conferences on info-tech & info-net. Beijing: IEEE Press, 2001. 58 - 66
[29]Ramos V, Merelo J J. Self-organized stigmergic document maps: environment as a mechanismfor context learning [C]. In : Proceedings 21st Spanish conference on evolutionary and bio-inspired algorithms. Mérida, 2002. 284 -293
[30]Yang Y. and Kamel M. Clustering ensemble using swarm intelligence [C]. In: IEEE swarm intelligence symposium[C]. Piscataway, NJ : IEEE service center , 2003. 65 -71
