# 遺傳演算法(Genetic Algorithm , GA)

## 遺傳演算法概述
基因演算法是一種受到自然選擇(natural selection)機制所啟發的演算法。
自然選擇解釋生物如何適應環境，基於生物中個體的某種優勢或劣勢，導致生存能力存在差異，進而影響繁殖能力，使得特徵逐漸被保存或者淘汰。

基因演算法便是在模擬自然選擇的機制，將解比擬成一條染色體(chromosome)，模仿生物學中交配(crossover)、突變(mutation)等現象，並根據適應度(fitness)的高低，決定染色體的去留，達到去蕪存菁的效果。

通俗地說，基因演算法就是在特定大小的解集合中，透過增添亂數、兩兩排列組合等操作來改變/產生新的解，並從中挑選較好的解保留到下個世代中，以確保解變異的方向能夠逐漸收斂。

## 基本遺傳演算法
* 解決:==最佳化問題==的工具
　*　旅行推銷員問題（Travelling salesman problem, TSP）
　
　　給定一組城市和每對城市之間的距離，找到每個城市只訪問一次並返回起點的最短路徑。
　　　在以Python實作粒子群演算法一文中提到，最佳化問題分為連續最佳化問題與組合優化，TSP是一個尋求最短路徑的組合優化問題。
　　　TSP情境是給定城市和城市之間的距離，旅人會踏訪每座城市，最終返回到起始城市，期間同一座城市不能踏訪兩次以上，如何決定踏訪城市的順序，使得總路徑距離最短，即是該情境的問題；或是在工廠的生產線上，機器人從起始的位置出發，前往不同的工作站進行特定的操作，最後再返回到起始的位置，要如何規劃出一條最佳路徑。
　　　秉持著物件導向的精神，TSP問題本身亦可成為一個物件。coordinate是城市的經緯度，cities_name如字面上意思，就是城市的名字。get_distance負責計算兩個城市之間的距離，python的Haversine套件可以計算地理距離，但在此只是為了解釋演算法流程，便採用跟論文相同的歐式距離。

## 遺傳演算法的理論分析
* 模式定理
* 遺傳演算法的理論基礎是Holland提出的模式定理。一個模式就是一個描述種群在位串的某些確定位置上具有相似性的位串子集的相似性範本，記為H 。
在模式H中確定位置（基因）的個數稱為該模式的模式階，記為o(H) 。而模式中第一個確定位置和最後一個確定位置之間的確定值，稱為模式H的長度，記為δ (H)。

## 遺傳演算法的應用實例
遺傳演算法提供一種求解複雜系統最佳化問題的通用框架，不依賴於問題具體的領域，對問題的種類有很強的強健性（Robustness），故廣泛被應用於許多學科。近十幾年來，遺傳演算法迅速的發展，目前在生物工程、化學工程、計算機科學、動態處理、人工智慧、建模與模擬、醫學工程、商業與金融等，為求解全域最佳化問題的有利工具。部份應用領域如下所述：
1. 函數最佳化
函數最佳化（Function Optimization）是遺傳演算法的經典應用領域， 亦為遺傳演算法進行性能評估的常用範例。可用各式各樣的函數來驗證遺傳演算法的性能。對於一些非線性、多模型及多目標的函數最佳化問題， 亦可得到較好的結果。
2. 自動控制領域
在自動控制（Automatic Control）領域中有很多與最佳化相關的問題需要求解，遺傳演算法已經在其中得到初步的應用，並顯示出了良好的效果。

例如，基於遺傳演算法的模糊控制器最佳化設計，用遺傳演算法進行航空控制系的最佳化，使用遺傳演算法設計空間交會控制器等。
3. 旅行商問題
旅行商問題（Traveling Salesman Problem，簡稱 TSP）是經典的組合最佳化問題之一，以遠遠超過其本身的含意，成為一種衡量演算法優劣的標準。TSP 問題是採用非標準編碼遺傳演算法求解最成功的一例，用銷售員順序經過的程式名稱表示基因編碼。因使用標準交配產生的後代可能有重複或遺失的機因而成為非可行解，故提出了非標準的交配與突變方法。
4. 資料探勘
資料探勘（Data Mining）是指從大型資料庫中提取隱含的、未知的， 即具有潛在應用價值的訊息或模式，是資料庫研究中一個很有前瞻性的新領域，基於遺傳演算法的特點，可用於資料探勘中的規則開發。