畢業(yè)論文（設(shè)計(jì)）基于蟻群算法的計(jì)算機(jī)仿真技術(shù)

33頁(yè)共計(jì)17591字

摘 要
自意大利學(xué)者M(jìn). Dorigo于1991年提出蟻群算法后，該算法引起了學(xué)者們的極大關(guān)注，在短短十多年的時(shí)間里，已在組合優(yōu)化、網(wǎng)絡(luò)路由、函數(shù)優(yōu)化、數(shù)據(jù)挖掘、機(jī)器人路徑規(guī)劃等領(lǐng)域獲得了廣泛應(yīng)用，并取得了較好的效果。本文首先討論了該算法的基本原理，接著介紹了旅行商問(wèn)題，然后對(duì)蟻群算法及其二種改進(jìn)算法進(jìn)行了分析，并通過(guò)計(jì)算機(jī)仿真來(lái)說(shuō)明蟻群算法基本原理，然后分析了聚類(lèi)算法原理和蟻群聚類(lèi)算法的數(shù)學(xué)模型，通過(guò)調(diào)整傳統(tǒng)的蟻群算法構(gòu)建了求解聚類(lèi)問(wèn)題的蟻群聚類(lèi)算法。最后，本文還研究了一種依賴(lài)信息素解決聚類(lèi)問(wèn)題的蟻群聚類(lèi)算法，并把此蟻群聚類(lèi)算法應(yīng)用到對(duì)人工數(shù)據(jù)進(jìn)行分類(lèi)，還利用該算法對(duì)2005年中國(guó)24所高校綜合實(shí)力進(jìn)行分類(lèi)，得到的分類(lèi)結(jié)果與實(shí)際情況相符，說(shuō)明了蟻群算法在聚類(lèi)分析中能夠收到較為理想的結(jié)果。

目 錄
1 引 言 1
1.1 群智能 1
1.2 蟻群算法 2
1.3 聚類(lèi)問(wèn)題 3
1.4 本文研究工作 4
2 蟻群算法原理及算法描述 5
2.1 蟻群算法原理 5
2.2 蟻群優(yōu)化的原理分析 7
2.3 算法基本流程 9
2.4 蟻群覓食過(guò)程計(jì)算機(jī)動(dòng)態(tài)模擬 10
2.5 人工螞蟻與真實(shí)螞蟻的對(duì)比 12
2.6 本章小結(jié) 13
3 基本蟻群優(yōu)化算法及其改進(jìn) 14
3.1 旅行商問(wèn)題 14
3.2 基本蟻群算法及其典型改進(jìn) 14
3.2.1 螞蟻系統(tǒng) 14
3.2.2 蟻群系統(tǒng) 15
3.2.3 最大-最小螞蟻系統(tǒng) 15
3.3 基本蟻群算法仿真實(shí)驗(yàn) 15
3.3.1 軟硬件環(huán)境 15
3.3.2 重要參數(shù)設(shè)置 15
3.3.3 仿真試驗(yàn) 16
3.4 本章小結(jié) 18
4 蟻群聚類(lèi)算法及其應(yīng)用 19
4.1 聚類(lèi)問(wèn)題 19
4.2 蟻群聚類(lèi)算法的數(shù)學(xué)模型 20
4.3 蟻群聚類(lèi)算法 20
4.3.1 蟻群聚類(lèi)算法分析 21
4.3.2 蟻群聚類(lèi)算法流程 24
4.4 蟻群聚類(lèi)算法在高校分類(lèi)中的應(yīng)用 24
4.5 本章小結(jié) 26
5 結(jié)論與展望 27
參考文獻(xiàn) 28
致 謝 30

【關(guān)鍵詞】蟻群算法；計(jì)算機(jī)仿真；聚類(lèi)；蟻群聚類(lèi)
參考文獻(xiàn)
[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]彭喜元, 彭宇, 戴毓豐. 群智能理論及其應(yīng)用[J]. 電子學(xué)報(bào), 2003, 31(12A): 1982-1987
[3]李志偉. 基于群集智能的蟻群優(yōu)化算法研究[J]. 計(jì)算機(jī)工程與設(shè)計(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]吳啟迪, 汪鐳. 智能蟻群算法及應(yīng)用[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ìn)化聚類(lèi)學(xué)習(xí)新方法[J]. 計(jì)算機(jī)工程與應(yīng)用, 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