遺傳算法研究與應(yīng)用
1.5萬(wàn)字 37頁(yè)
包括開題報(bào)告和任務(wù)書，正文中附有程序代碼


摘要
遺傳算法（Genetic algorithms, GAs）是借鑒生物界自然選擇和重組機(jī)制的隨機(jī)的搜索算法。由于它簡(jiǎn)單易行、魯棒性強(qiáng)，應(yīng)用范圍極為廣泛，并且已在眾多領(lǐng)域得到了實(shí)際應(yīng)用，引起了廣大學(xué)者和工程人員的關(guān)注。Traveling Salesman Problem（TSP）問(wèn)題是一個(gè)典型NP難題，是衡量近似算法效率的主要標(biāo)準(zhǔn)，因此設(shè)計(jì)TSP問(wèn)題的近似算法具有非常重要的意義。本文討論遺傳算法及其對(duì)于TSP問(wèn)題的解決方法。
論文首先介紹了遺傳算法的基本概念、原理、意義及發(fā)展現(xiàn)狀。通過(guò)對(duì)遺傳算法基本理論的學(xué)習(xí)和研究，提出了解決TSP問(wèn)題的算法，并詳細(xì)給出了算法中的編碼方案、適應(yīng)度函數(shù)、選擇算子、交叉算子、變異算子。最后用C++語(yǔ)言設(shè)計(jì)并實(shí)現(xiàn)了該算法，結(jié)果表明該算法可以在較短的時(shí)間內(nèi)得到TSP問(wèn)題的近似最優(yōu)解。

關(guān)鍵詞：遺傳算法；TSP問(wèn)題；適應(yīng)度函數(shù)；交叉；變異




Research and Application of Genetic Algorithms
Abstract
Genetic algorithms (GAs) are optimization search algorithms based on the mechanics of artificial selection and genetic recombination operators. They are simple, robust and easy to implement. They have been used in many fields. For these reasons now they are the hot research field which has got many scholars’ attention. Traveling Salesman Problem (TSP) is a classic NP problem, which is the main standard of measuring the efficiency of approximative algorithms. So the solution of the problem has has very important significance. The paper discusses the basic genetic algorithms and their application.
The essay first introduces the basic concepts, principle, procedure, significance and characteristics of genetic algorithms. By learning the basic theory of genetic algorithms one solution of TSP is given. The detailed coding scheme, fitness function, selection operator, cross operator and mutation operator of the solution are also given. Finally using C++ implement the solution. The result of the program show that the algorithm can get optimal solution of the problem quickly.

Keywords: Genetic Algorithms(G A); Traveling Salesman Problem( TSP); fitness function; cross operator; mutation operator;



目 錄
1 緒論 1
1.1 課題背景 1
1.2 課題研究意義 2
1.3 國(guó)內(nèi)外研究現(xiàn)狀 3
1.4 論文內(nèi)容 5
2 遺傳算法簡(jiǎn)介 6
2.1 遺傳算法基本概念 6
2.2 遺傳算法基本原理 7
2.3 遺傳算法的步驟 8
3 遺傳算法基本理論 11
3.1 模式定理 11
3.2 積木塊假設(shè)與欺騙問(wèn)題 12
3.3 收斂性分析 13
4 旅行商問(wèn)題概述 14
4.1 旅行商問(wèn)題的定義和數(shù)學(xué)模型 14
4.1.1 定義 14
4.1.2 數(shù)學(xué)模型 14
4.2 旅行商問(wèn)題的計(jì)算復(fù)雜性 15
4.3 研究旅行商問(wèn)題的意義 16
5 遺傳算法在巡回旅行商問(wèn)題中的應(yīng)用 18
5.1 旅行商問(wèn)題的建模 18
5.1.1 編碼 18
5.1.2 適應(yīng)度函數(shù) 18
5.2 遺傳算法中三個(gè)算子的設(shè)計(jì) 19
5.2.1 選擇算子的設(shè)計(jì) 20
5.2.2 交叉算子的設(shè)計(jì) 21
5.2.3 變異算子的設(shè)計(jì) 25
5.3 遺傳算法求解旅行商問(wèn)題的步驟 27
5.4 測(cè)試結(jié)果 27
6 結(jié)束語(yǔ) 29
致 謝 30
參考文獻(xiàn) 31


參考文獻(xiàn)
[4] Hollstien R B. Aritifical Genetic Adaptation in Computer Control Systems[D]. AnnArbor. University of Michigan
[5] 王小平.遺傳算法--理論.應(yīng)用與軟件實(shí)現(xiàn)[M],西安:西安交通大學(xué)出版社
[6] Holland J H. Adaptation in Natural and Artificial Systems[M]. 2nd edition. Ann Arbor. The University of Michigan
[7] 周明,孫樹棟.遺傳算法原理及應(yīng)用[M].北京:國(guó)防工業(yè)出版社
[8] 陳國(guó)良,王煦法,莊鎮(zhèn)泉等.遺傳算法及其應(yīng)用[M].北京:人民郵電出版社
[9]殷人昆,陶永雷等.數(shù)據(jù)結(jié)構(gòu)(用面向?qū)ο蠓椒ㄅcc＋＋描述) .北京:清華大學(xué)出版社
[10] 孫艷豐,王眾托.自然數(shù)編碼遺傳算法的最優(yōu)群體規(guī)模.信息與控制[J]