⑴ [1] 遺傳演算法--附Python代碼
遺傳演算法（Genetic Algorithm, GA）是一種模擬生物在自然界中遺傳和進化的適者生存的搜索演算法。這種演算法是在 1975 年由美國的 Holland 教授首次提出，是一種全局優化概率搜索演算法。生物可以通過遺傳、變異和自然選擇而不斷地進行演化，遺傳演算法就是從達爾文的自然選擇理論中發展而來。就像是不同的基因，不同的染色體會形成不同的物種。
在遺傳演算法中，每一個染色體都是一個解決方案，一系列染色體聚集在一起就是所謂的種群。種群根據「生物間相互競爭，能夠適應者存活」的原則進行個體淘汰。
從初始種群開始，利用適值函數對種群中每一個染色體進行適應度計算，根據個體適應值占總體適應值的比例，設計合適的選擇策略在當前種群中挑選優秀個體，並將這些優秀個體進行交叉和變異產生新的種群。參考物種的演化歷程，這些個體一代又一代的進行進化，直至達到所滿足期望的結束條件後從中挑選出最優秀的個體作為最終解。
編碼是設計遺傳演算法首先需要解決的問題。由於遺傳演算法不能直接處理解空間的解數據，因此必須通過編碼的方式將這些解表示為遺傳空間的基因型串結構數據。遺傳演算法的編碼方式有許多，最典型的是二進制編碼和實數編碼。其中，二進制編碼是人們常選擇的編碼方式。
二進制編碼將待求解問題的解空間用二進制數 0,1 表示，每個個體基因型都是一個二進制編碼符號串，其串長取決於求解的精度。因此，在求解適應度值時需將其解碼後再進行求解。實數編碼則是利用實值來直接表示染色體上的基因，無需進行解碼，可以直接求取個體的適應度值。
隨機產生一定數量的個體，構成初始解的種群，並設置進化代數。產生初始種群的方法通常有兩種：一種是在對問題的解無任何經驗知識的情況下，隨機產生樣本；另一種是在具有某些經驗知識的情況下，將其轉換成需要滿足的要求，在滿足要求的解中隨機的選取樣本。初始群體也要選擇適當的個體數量，如果挑選個體數量的過小則會降低種群的多樣性，而群體的選擇過大就會導致計算復雜、部分高適值的個體有可能被淘汰，影響雜交性能。
適應度函數是對染色體適應能力進行評價的函數，顯示著個體或解的優劣。遺傳演算法評判解的優劣並不在於該解的構造，而是在於該解的適應度值大小。
適應度函數的確立對遺傳演算法計算的收斂速度及最優解的尋找產生極大的影響。這是由於遺傳演算法在進化搜索中基於適應度函數，通過計算種群中每個個體的適應度來搜索尋找。此外，在遺傳演算法中，適應度函數的復雜性佔主導地位，因此在求解過程中要盡量簡化適應度函數，以減少運算的復雜程度。
在遺傳演算法流程的每個循環的開始，利用選擇運算元從當前種群中選出部分個體作為新產生子代的父代。該選擇是基於概率的，並且被選中的個體的概率與其適應度相關聯，從而有較高適應度的個體具有更高優勢。任意的選擇兩個染色體進行雜交。當前常見的選擇運算元主要有輪盤選擇、排序選擇法、精英選擇、隨機遍歷抽樣這幾種。
遺傳演算法的重組運算元里包含交叉運算元等其他重組運算元，由於遺傳演算法中有二進制編碼、實值編碼、排列編碼、樹編碼等編碼方式，因此也必須有與編碼方式相適應的不同的交叉運算元。二進制編碼中常見的有一點交叉、二點交叉等重組運算元。交叉概率通常用 [公式] 來表示，它是指兩個染色體之間發生交叉重組的概率。交叉概率的取值一般選取 0.25 到 1.00 之間。
變異是指種群中的染色體在進行復制時，產生極低的概率使得這一過程中發生了變化，從而產生了變異，即該染色體上的某個基因點或部分基因發生了突變，突變後的基因將會表現出新的特徵。
變異概率通常用 [公式] 來表示，受染色體長度和種群大小的影響。此外， [公式] 的取值也會對演算法的收斂性以及最終的最優解取值產生較大的影響，當變異概率較小時，解的穩定性較高，但容易陷入局部最優，且難以跳出局部最優解的區間，若變異概率較大，則可豐富解的空間，跳出局部最優區間，最終趨向全局最優解，因此在設計程序的時候應多次嘗試確定合適的變異概率。
停止准則的定義方式主要有三種，即最優個體的適應能力達到指定的閾值、最優個體的適應度和群體總適應度保持穩定不變以及達到預設的最大迭代次數。
遺傳演算法解決問題時，對約束條件的處理方法有四種方法：
（1）在開始設計編碼規則時，讓解碼後的染色體就只可能落在可行區域內；
（2）設計合理的交叉運算元和變異運算元，使得在滿足所設計運算元本身特性的前提下，讓運算後的染色體也在可行域內；
（3）採用罰函數的方法，將懲罰值加入適值函數中，降低不滿足約束條件個體的生存概率；
（4）在遺傳操作後加入判斷語句，判斷是否滿足約束條件，如果是則繼續，不滿足可將其超出邊界的放到邊界上或重新初始化操作。
使用遺傳演算法求解 TSP 問題，首先導入基本庫，設置遺傳演算法參數
接著構建遺傳演算法模型
構建 TSP 實驗場景
運行主函數，求解並繪制最優路徑
求解結果如下