遺傳算法研究與應(yīng)用

電子通信論文編號:TX259  論文字數(shù):15114,頁數(shù):37 有開題報告，任務(wù)書

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

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

關(guān)鍵詞：遺傳算法；TSP問題；適應(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;