遺傳算法研究與應用

論文編號:TX259  論文字數:15114,頁數:37 有開題報告，任務書

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

關鍵詞：遺傳算法；TSP問題；適應度函數；交叉；變異

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 國內外研究現狀 3
1.4 論文內容 5
2 遺傳算法簡介 6
2.1 遺傳算法基本概念 6
2.2 遺傳算法基本原理 7
2.3 遺傳算法的步驟 8
3 遺傳算法基本理論 11
3.1 模式定理 11
3.2 積木塊假設與欺騙問題 12
3.3 收斂性分析 13
4 旅行商問題概述 14
4.1 旅行商問題的定義和數學模型 14
4.1.1 定義 14
4.1.2 數學模型 14
4.2 旅行商問題的計算復雜性 15
4.3 研究旅行商問題的意義 16
5 遺傳算法在巡回旅行商問題中的應用 18
5.1 旅行商問題的建模 18
5.1.1 編碼 18
5.1.2 適應度函數 18
5.2 遺傳算法中三個算子的設計 19
5.2.1 選擇算子的設計 20
5.2.2 交叉算子的設計 21
5.2.3 變異算子的設計 25
5.3 遺傳算法求解旅行商問題的步驟 27
5.4 測試結果 27
6 結束語 29
致 謝 30
參考文獻: 31