遺傳演算法運算流程

❶ 螞蟻演算法的思想進化公式及遺傳演算法的演算法流程圖

抄的
目前蟻群演算法主要用在組合優化方面，基本蟻群演算法的思路是這樣的：
1. 在初始狀態下，一群螞蟻外出，此時沒有信息素，那麼各自會隨機的選擇一條路徑。
2. 在下一個狀態，每隻螞蟻到達了不同的點，從初始點到這些點之間留下了信息素，螞蟻繼續走，已經到達目標的螞蟻開始返回，與此同時，下一批螞蟻出動，它們都會按照各條路徑上信息素的多少選擇路線(selection)，更傾向於選擇信息素多的路徑走（當然也有隨機性）。
3. 又到了再下一個狀態，剛剛沒有螞蟻經過的路線上的信息素不同程度的揮發掉了(evaporation)，而剛剛經過了螞蟻的路線信息素增強(reinforcement)。然後又出動一批螞蟻，重復第2個步驟。
每個狀態到下一個狀態的變化稱為一次迭代，在迭代多次過後，就會有某一條路徑上的信息素明顯多於其它路徑，這通常就是一條最優路徑。

關鍵的部分在於步驟2和3：
步驟2中，每隻螞蟻都要作出選擇，怎樣選擇呢？
selection過程用一個簡單的函數實現：
螞蟻選擇某條路線的概率＝該路線上的信息素÷所有可選擇路線的信息素之和
假設螞蟻在i點，p(i,j)表示下一次到達j點的概率，而τ(i,j)表示ij兩點間的信息素，則：
p(i,j)＝τ(i,j)/∑τ(i)
（如果所有可選路線的信息素之和∑τ(i)＝0，即前面還沒有螞蟻來過，概率就是一個[0,1]上的隨機值，即隨機選擇一條路線）
步驟3中，揮發和增強是演算法的關鍵所在（也就是如何數學定義信息素的）
evaporation過程和reinforcement過程定義了一個揮發因子，是迭代次數k的一個函數
ρ(k)＝1－lnk/ln(k+1)
最初設定每條路徑的信息素τ(i,j,0)為相同的值
然後，第k+1次迭代時，信息素的多少
對於沒有螞蟻經過的路線：τ(i,j,k+1)＝(1－ρ(k))τ(i,j,k)，顯然信息素減少了
有螞蟻經過的路線：τ(i,j,k+1)＝(1－ρ(k))τ(i,j,k)＋ρ(k)/|W|，W為所有點的集合

為什麼各個函數要如此定義，這個問題很難解釋清楚，這也是演算法的精妙所在。如此定義信息素的揮發和增強，以及路徑選擇，根據馬爾可夫過程（隨機過程之一）能夠推導出，在迭代了足夠多次以後，演算法能夠收斂到最佳路徑。

❷ 遺傳演算法的運算過程

遺傳操作是模擬生物基因遺傳的做法。在遺傳演算法中，通過編碼組成初始群體後，遺傳操作的任務就是對群體的個體按照它們對環境適應度(適應度評估)施加一定的操作，從而實現優勝劣汰的進化過程。從優化搜索的角度而言，遺傳操作可使問題的解，一代又一代地優化，並逼近最優解。
遺傳操作包括以下三個基本遺傳運算元(genetic operator):選擇(selection)；交叉(crossover)；變異(mutation)。這三個遺傳運算元有如下特點：
個體遺傳運算元的操作都是在隨機擾動情況下進行的。因此，群體中個體向最優解遷移的規則是隨機的。需要強調的是，這種隨機化操作和傳統的隨機搜索方法是有區別的。遺傳操作進行的高效有向的搜索而不是如一般隨機搜索方法所進行的無向搜索。
遺傳操作的效果和上述三個遺傳運算元所取的操作概率，編碼方法，群體大小，初始群體以及適應度函數的設定密切相關。 從群體中選擇優勝的個體，淘汰劣質個體的操作叫選擇。選擇運算元有時又稱為再生運算元(reproction operator)。選擇的目的是把優化的個體(或解)直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的，目前常用的選擇運算元有以下幾種：適應度比例方法、隨機遍歷抽樣法、局部選擇法。
其中輪盤賭選擇法 （roulette wheel selection）是最簡單也是最常用的選擇方法。在該方法中，各個個體的選擇概率和其適應度值成比例。設群體大小為n，其中個體i的適應度為，則i 被選擇的概率，為遺傳演算法
顯然，概率反映了個體i的適應度在整個群體的個體適應度總和中所佔的比例。個體適應度越大。其被選擇的概率就越高、反之亦然。計算出群體中各個個體的選擇概率後，為了選擇交配個體，需要進行多輪選擇。每一輪產生一個[0，1]之間均勻隨機數，將該隨機數作為選擇指針來確定被選個體。個體被選後，可隨機地組成交配對，以供後面的交叉操作。 在自然界生物進化過程中起核心作用的是生物遺傳基因的重組(加上變異)。同樣，遺傳演算法中起核心作用的是遺傳操作的交叉運算元。所謂交叉是指把兩個父代個體的部分結構加以替換重組而生成新個體的操作。通過交叉，遺傳演算法的搜索能力得以飛躍提高。
交叉運算元根據交叉率將種群中的兩個個體隨機地交換某些基因，能夠產生新的基因組合，期望將有益基因組合在一起。根據編碼表示方法的不同，可以有以下的演算法：
a)實值重組（real valued recombination）
1)離散重組（discrete recombination）
2)中間重組（intermediate recombination）
3)線性重組（linear recombination）
4)擴展線性重組（extended linear recombination）。
b)二進制交叉（binary valued crossover）
1)單點交叉（single-point crossover）
2)多點交叉（multiple-point crossover）
3)均勻交叉（uniform crossover）
4)洗牌交叉（shuffle crossover）
5)縮小代理交叉（crossover with reced surrogate）。
最常用的交叉運算元為單點交叉(one-point crossover)。具體操作是:在個體串中隨機設定一個交叉點，實行交叉時，該點前或後的兩個個體的部分結構進行互換，並生成兩個新個體。下面給出了單點交叉的一個例子：
個體A：1 0 0 1 ↑1 1 1 → 1 0 0 1 0 0 0 新個體
個體B：0 0 1 1 ↑0 0 0 → 0 0 1 1 1 1 1 新個體 變異運算元的基本內容是對群體中的個體串的某些基因座上的基因值作變動。依據個體編碼表示方法的不同，可以有以下的演算法：
a)實值變異
b)二進制變異。
一般來說，變異運算元操作的基本步驟如下：
a)對群中所有個體以事先設定的變異概率判斷是否進行變異
b)對進行變異的個體隨機選擇變異位進行變異。
遺傳演算法引入變異的目的有兩個:一是使遺傳演算法具有局部的隨機搜索能力。當遺傳演算法通過交叉運算元已接近最優解鄰域時，利用變異運算元的這種局部隨機搜索能力可以加速向最優解收斂。顯然，此種情況下的變異概率應取較小值，否則接近最優解的積木塊會因變異而遭到破壞。二是使遺傳演算法可維持群體多樣性，以防止出現未成熟收斂現象。此時收斂概率應取較大值。
遺傳演算法中，交叉運算元因其全局搜索能力而作為主要運算元，變異運算元因其局部搜索能力而作為輔助運算元。遺傳演算法通過交叉和變異這對相互配合又相互競爭的操作而使其具備兼顧全局和局部的均衡搜索能力。所謂相互配合.是指當群體在進化中陷於搜索空間中某個超平面而僅靠交叉不能擺脫時，通過變異操作可有助於這種擺脫。所謂相互競爭，是指當通過交叉已形成所期望的積木塊時，變異操作有可能破壞這些積木塊。如何有效地配合使用交叉和變異操作，是目前遺傳演算法的一個重要研究內容。
基本變異運算元是指對群體中的個體碼串隨機挑選一個或多個基因座並對這些基因座的基因值做變動(以變異概率P.做變動)，(0，1)二值碼串中的基本變異操作如下：
基因位下方標有*號的基因發生變異。
變異率的選取一般受種群大小、染色體長度等因素的影響，通常選取很小的值，一般取0.001－0.1。 當最優個體的適應度達到給定的閾值，或者最優個體的適應度和群體適應度不再上升時，或者迭代次數達到預設的代數時，演算法終止。預設的代數一般設置為100-500代。

❸ 關於遺傳演算法選擇概率的和的計算過程——數學達人請進！

首先y=x*x在[0,31]這個函數的極值是取31的時候，用遺傳演算法來解答這樣的問題是內有點多餘容的。遺傳演算法的主要步驟是4步，初始化種群，選擇，交叉，變異。這里說的淘汰函數，很可能就是在選擇選擇運算元，這個運算元是根據最適合最優先的演算法來實現。舉個簡單的例子，你要用數字進行遺傳演算法，肯定得把他轉化為2進制的染色體，【0-31】就是從00000-11111，每條染色體5個基因。對於選擇運算來說，每次要從種群選擇最優的幾個，第一次完全是隨機的。假如隨機選4個染色體，選的4條染色體是1,2,3,4。很明顯他們的值是1,4,9,16，總和是30，那麼選擇4的概率就是30分之16，這樣就可以盡可能的選擇大的數值。這里的淘汰域3，可能是每次淘汰3條染色體，或者每次只選擇3條最優的染色體，視其選擇的條數而定。我看在程序里沒有用到這個東西。遺傳演算法以及進化演算法不限定於特殊的程序，每個人有不同的理解，不必拘泥於概念。

❹ 遺傳演算法的發展過程

遺傳演算法定義遺傳演算法（Genetic Algorithm）是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法，它最初由美國Michigan大學J.Holland教授於1975年首先提出來的，並出版了頗有影響的專著《Adaptation in Natural and Artificial Systems》，GA這個名稱才逐漸為人所知，J.Holland教授所提出的GA通常為簡單遺傳演算法（SGA）。
遺傳演算法是從代表問題可能潛在的解集的一個種群（population）開始的，而一個種群則由經過基因（gene）編碼的一定數目的個體(indivial)組成。每個個體實際上是染色體(chromosome)帶有特徵的實體。染色體作為遺傳物質的主要載體，即多個基因的集合，其內部表現（即基因型）是某種基因組合，它決定了個體的形狀的外部表現，如黑頭發的特徵是由染色體中控制這一特徵的某種基因組合決定的。因此，在一開始需要實現從表現型到基因型的映射即編碼工作。由於仿照基因編碼的工作很復雜，我們往往進行簡化，如二進制編碼，初代種群產生之後，按照適者生存和優勝劣汰的原理，逐代（generation）演化產生出越來越好的近似解，在每一代，根據問題域中個體的適應度（fitness）大小選擇（selection）個體，並藉助於自然遺傳學的遺傳運算元（genetic operators）進行組合交叉（crossover）和變異（mutation），產生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的後生代種群比前代更加適應於環境，末代種群中的最優個體經過解碼（decoding），可以作為問題近似最優解。 [編輯本段]遺傳演算法特點遺傳演算法是一類可用於復雜系統優化的具有魯棒性的搜索演算法，與傳統的優化演算法相比，主要有以下特點：
1、 遺傳演算法以決策變數的編碼作為運算對象。傳統的優化演算法往往直接決策變數的實際值本身，而遺傳演算法處理決策變數的某種編碼形式，使得我們可以借鑒生物學中的染色體和基因的概念，可以模仿自然界生物的遺傳和進化機理，也使得我們能夠方便的應用遺傳操作運算元。
2、 遺傳演算法直接以適應度作為搜索信息，無需導數等其它輔助信息。
3、 遺傳演算法使用多個點的搜索信息，具有隱含並行性。
4、 遺傳演算法使用概率搜索技術，而非確定性規則。 [編輯本段]遺傳演算法的應用由於遺傳演算法的整體搜索策略和優化搜索方法在計算是不依賴於梯度信息或其它輔助知識，而只需要影響搜索方向的目標函數和相應的適應度函數，所以遺傳演算法提供了一種求解復雜系統問題的通用框架，它不依賴於問題的具體領域，對問題的種類有很強的魯棒性，所以廣泛應用於許多科學，下面我們將介紹遺傳演算法的一些主要應用領域：
1、 函數優化。
函數優化是遺傳演算法的經典應用領域，也是遺傳演算法進行性能評價的常用算例，許多人構造出了各種各樣復雜形式的測試函數：連續函數和離散函數、凸函數和凹函數、低維函數和高維函數、單峰函數和多峰函數等。對於一些非線性、多模型、多目標的函數優化問題，用其它優化方法較難求解，而遺傳演算法可以方便的得到較好的結果。
2、 組合優化
隨著問題規模的增大，組合優化問題的搜索空間也急劇增大，有時在目前的計算上用枚舉法很難求出最優解。對這類復雜的問題，人們已經意識到應把主要精力放在尋求滿意解上，而遺傳演算法是尋求這種滿意解的最佳工具之一。實踐證明，遺傳演算法對於組合優化中的NP問題非常有效。例如遺傳演算法已經在求解旅行商問題、 背包問題、裝箱問題、圖形劃分問題等方面得到成功的應用。
此外，GA也在生產調度問題、自動控制、機器人學、圖象處理、人工生命、遺傳編碼和機器學習等方面獲得了廣泛的運用。 [編輯本段]遺傳演算法的現狀進入90年代，遺傳演算法迎來了興盛發展時期，無論是理論研究還是應用研究都成了十分熱門的課題。尤其是遺傳演算法的應用研究顯得格外活躍，不但它的應用領域擴大，而且利用遺傳演算法進行優化和規則學習的能力也顯著提高，同時產業應用方面的研究也在摸索之中。此外一些新的理論和方法在應用研究中亦得到了迅速的發展，這些無疑均給遺傳演算法增添了新的活力。遺傳演算法的應用研究已從初期的組合優化求解擴展到了許多更新、更工程化的應用方面。
隨著應用領域的擴展，遺傳演算法的研究出現了幾個引人注目的新動向：一是基於遺傳演算法的機器學習，這一新的研究課題把遺傳演算法從歷來離散的搜索空間的優化搜索演算法擴展到具有獨特的規則生成功能的嶄新的機器學習演算法。這一新的學習機制對於解決人工智慧中知識獲取和知識優化精煉的瓶頸難題帶來了希望。二是遺傳演算法正日益和神經網路、模糊推理以及混沌理論等其它智能計算方法相互滲透和結合，這對開拓21世紀中新的智能計算技術將具有重要的意義。三是並行處理的遺傳演算法的研究十分活躍。這一研究不僅對遺傳演算法本身的發展，而且對於新一代智能計算機體系結構的研究都是十分重要的。四是遺傳演算法和另一個稱為人工生命的嶄新研究領域正不斷滲透。所謂人工生命即是用計算機模擬自然界豐富多彩的生命現象，其中生物的自適應、進化和免疫等現象是人工生命的重要研究對象，而遺傳演算法在這方面將會發揮一定的作用，五是遺傳演算法和進化規劃（Evolution Programming,EP）以及進化策略（Evolution Strategy,ES）等進化計算理論日益結合。EP和ES幾乎是和遺傳演算法同時獨立發展起來的，同遺傳演算法一樣，它們也是模擬自然界生物進化機制的智能計算方法，即同遺傳演算法具有相同之處，也有各自的特點。目前，這三者之間的比較研究和彼此結合的探討正形成熱點。
1991年D.Whitey在他的論文中提出了基於領域交叉的交叉運算元（Adjacency based crossover），這個運算元是特別針對用序號表示基因的個體的交叉，並將其應用到了TSP問題中，通過實驗對其進行了驗證。
D.H.Ackley等提出了隨即迭代遺傳爬山法（Stochastic Iterated Genetic Hill-climbing，SIGH）採用了一種復雜的概率選舉機制，此機制中由m個「投票者」來共同決定新個體的值（m表示群體的大小）。實驗結果表明，SIGH與單點交叉、均勻交叉的神經遺傳演算法相比，所測試的六個函數中有四個表現出更好的性能，而且總體來講，SIGH比現存的許多演算法在求解速度方面更有競爭力。
H.Bersini和G.Seront將遺傳演算法與單一方法（simplex method）結合起來，形成了一種叫單一操作的多親交叉運算元（simplex crossover），該運算元在根據兩個母體以及一個額外的個體產生新個體，事實上他的交叉結果與對三個個體用選舉交叉產生的結果一致。同時，文獻還將三者交叉運算元與點交叉、均勻交叉做了比較，結果表明，三者交叉運算元比其餘兩個有更好的性能。
國內也有不少的專家和學者對遺傳演算法的交叉運算元進行改進。2002年，戴曉明等應用多種群遺傳並行進化的思想，對不同種群基於不同的遺傳策略，如變異概率，不同的變異運算元等來搜索變數空間，並利用種群間遷移運算元來進行遺傳信息交流，以解決經典遺傳演算法的收斂到局部最優值問題
2004年，趙宏立等針對簡單遺傳演算法在較大規模組合優化問題上搜索效率不高的現象，提出了一種用基因塊編碼的並行遺傳演算法（Building-block Coded Parallel GA，BCPGA）。該方法以粗粒度並行遺傳演算法為基本框架，在染色體群體中識別出可能的基因塊，然後用基因塊作為新的基因單位對染色體重新編碼，產生長度較短的染色體，在用重新編碼的染色體群體作為下一輪以相同方式演化的初始群體。
2005年，江雷等針對並行遺傳演算法求解TSP問題,探討了使用彈性策略來維持群體的多樣性,使得演算法跨過局部收斂的障礙,向全局最優解方向進化。 [編輯本段]遺傳演算法的一般演算法遺傳演算法是基於生物學的，理解或編程都不太難。下面是遺傳演算法的一般演算法：
創建一個隨機的初始狀態
初始種群是從解中隨機選擇出來的，將這些解比喻為染色體或基因，該種群被稱為第一代，這和符號人工智慧系統的情況不一樣，在那裡問題的初始狀態已經給定了。
評估適應度
對每一個解(染色體)指定一個適應度的值，根據問題求解的實際接近程度來指定(以便逼近求解問題的答案)。不要把這些「解」與問題的「答案」混為一談，可以把它理解成為要得到答案，系統可能需要利用的那些特性。
繁殖(包括子代突變)
帶有較高適應度值的那些染色體更可能產生後代(後代產生後也將發生突變)。後代是父母的產物，他們由來自父母的基因結合而成，這個過程被稱為「雜交」。
下一代

如果新的一代包含一個解，能產生一個充分接近或等於期望答案的輸出，那麼問題就已經解決了。如果情況並非如此，新的一代將重復他們父母所進行的繁衍過程，一代一代演化下去，直到達到期望的解為止。
並行計算

非常容易將遺傳演算法用到並行計算和群集環境中。一種方法是直接把每個節點當成一個並行的種群看待。然後有機體根據不同的繁殖方法從一個節點遷移到另一個節點。另一種方法是「農場主/勞工」體系結構，指定一個節點為「農場主」節點，負責選擇有機體和分派適應度的值，另外的節點作為「勞工」節點，負責重新組合、變異和適應度函數的評估。
術語說明
由於遺傳演算法是由進化論和遺傳學機理而產生的搜索演算法，所以在這個演算法中會用到很多生物遺傳學知識，下面是我們將會用來的一些術語說明：
一、染色體(Chronmosome)
染色體又可以叫做基因型個體(indivials),一定數量的個體組成了群體(population),群體中個體的數量叫做群體大小。
二、基因(Gene)
基因是串中的元素，基因用於表示個體的特徵。例如有一個串S＝1011，則其中的1，0，1，1這4個元素分別稱為基因。它們的值稱為等位基因(Alletes)。
三、基因地點(Locus)
基因地點在演算法中表示一個基因在串中的位置稱為基因位置(Gene Position)，有時也簡稱基因位。基因位置由串的左向右計算，例如在串 S＝1101 中，0的基因位置是3。
四、基因特徵值(Gene Feature)
在用串表示整數時，基因的特徵值與二進制數的權一致；例如在串 S=1011 中，基因位置3中的1，它的基因特徵值為2；基因位置1中的1，它的基因特徵值為8。
五、適應度(Fitness)
各個個體對環境的適應程度叫做適應度(fitness)。為了體現染色體的適應能力，引入了對問題中的每一個染色體都能進行度量的函數，叫適應度函數. 這個函數是計算個體在群體中被使用的概率。 [編輯本段]遺傳演算法的運算過程選擇(復制)：
根據各個個體的適應度，按照一定的規則或方法，從第t代群體P(t)中選擇出一些優良的個體遺傳到下 一代群體P(t+1)中；
交叉：
將群體P(t)內的各個個體隨機搭配成對，對每一對個體，以某個概率(稱為交叉概率）交換它們之間的部分染色體；
變異：
對群體P(t)中的每一個個體，以某一概率(稱為變異概率)改變某一個或某一些基因座上的基因值為其他基因值。

❺ 遺傳演算法的基本原理

遺傳演算法通常的實現方式，就是用程序來模擬生物種群進化的過程。對於一個求專最優解的問題，我屬們可以把一定數量的候選解（稱為個體）抽象地表示為染色體，使種群向更好的解來進化。大家知道，使用演算法解決問題的時候，解通常都是用數據或者字元串等表示的，而這個數據或字元串對應到生物中就是某個個體的「染色體」。進化從完全隨機個體的種群開始，之後一代一代發生。在每一代中評價其在整個種群的適應度，從當前種群中隨機地選擇多個個體（基於它們的適應度），通過自然選擇和突變產生新的種群，該種群在演算法的下一次迭代中成為當前種群。其具體的計算步驟如下：

• 編碼：將問題空間轉換為遺傳空間；

• 生成初始種群：隨機生成P個染色體；

• 種群適應度計算：按照確定的適應度函數，計算各個染色體的適應度；

• 選擇：根據染色體適應度，按照選擇運算元進行染色體的選擇；

• 交叉：按照交叉概率對被選擇的染色體進行交叉操作，形成下一代種群；

• 突變：按照突變概率對下一代種群中的個體進行突變操作；

• 返回第3步繼續迭代，直到滿足終止條件。

❻ 遺傳演算法程序與潮流計算程序怎麼結合

首先要清楚常規潮流計算和最優潮流的不同，尤其是計算過程。
常規潮流計算是給定PV,PQ和平衡節點相應的已知條件，根據網路拓撲計算線路功率和網損等運行指標，所給定的條件不一定使電網的運行達到最優水平；並且在電力市場環境下這些條件是未知的。因此需要尋找最優的已知條件，使調度運行成本、安全性、穩定性等最優，即成為最優潮流。在尋找最優運行條件的過程就需要到如遺傳演算法等智能演算法搜索或者數值方法如內點法等。
遺傳演算法與潮流計算的結合就是用遺傳演算法搜索最優運行條件。
現假定網損是判定最優與否的原則，即網損越小越優，同時定義遺傳演算法的適應度為一大數減去網損(即f=C-PL)將最小化問題轉化為最大化問題；待求運行條件的個數為m；遺傳演算法的種群數為n。
由以上分析不難知道，最優潮流計算過程需要反復調用常規潮流計算，這也是計算耗時的原因。
若將遺傳演算法的收斂判據設定為相鄰兩代的最大適應度值趨於穩定，則結合過程如下：
（1）初始化：用遺傳演算法產生初始種群（n行m列），初始最優適應度為0。轉（2）
（2）計算適應度：將產生的種群（已知條件）分別代入常規潮流程序，計算每個個體下的網損，從而得到每個個體相應的適應度值，保存最優適應度值。判定最優適應值變化情況，若|f2-f1|<ε（ε為一很小的正數），迭代終止，輸出最優個體，否則轉（3）。
（3）進行遺傳運算元的操作：調用遺傳演算法的選擇、交叉和變異操作，從而得到新的種群。轉（2）
根據以上三個基本步即可實現遺傳演算法與潮流計算的結合。

❼ 用遺傳演算法計算最佳路徑的具體方法

1.定義交叉概率，變異概率，終止條件（可以是最小距離限制也可以是代數限制）
2.初始化種群
3.選擇個體，交叉，變異
4.計算適應度函數
5.滿足終止條件否，滿足7，不滿足6
6.更新種群，轉到3
7.輸出結果

❽ 遺傳演算法概念

遺傳演算法是模擬達爾文的生物進化理論，結合進化中優勝劣汰的概念，是一種基於自然選擇和遺傳學原理的搜索演算法。

❾ 遺傳演算法求最優解，及matlab模擬的步驟 要詳細步驟！！！

這么復雜的公式，要有數據才能試驗編程。不是一下能搞定的。

❿ 關於遺傳演算法

遺傳演算法（Genetic Algorithm）是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法，它最初由美國Michigan大學J.Holland教授於1975年首先提出來的，並出版了頗有影響的專著《Adaptation in Natural and Artificial Systems》，GA這個名稱才逐漸為人所知，J.Holland教授所提出的GA通常為簡單遺傳演算法（SGA）。
遺傳演算法定義
遺傳演算法是從代表問題可能潛在的解集的一個種群（population）開始的，而一個種群則由經過基因（gene）編碼的一定數目的個體(indivial)組成。每個個體實際上是染色體(chromosome)帶有特徵的實體。染色體作為遺傳物質的主要載體，即多個基因的集合，其內部表現（即基因型）是某種基因組合，它決定了個體的形狀的外部表現，如黑頭發的特徵是由染色體中控制這一特徵的某種基因組合決定的。因此，在一開始需要實現從表現型到基因型的映射即編碼工作。由於仿照基因編碼的工作很復雜，我們往往進行簡化，如二進制編碼，初代種群產生之後，按照適者生存和優勝劣汰的原理，逐代（generation）演化產生出越來越好的近似解，在每一代，根據問題域中個體的適應度（fitness）大小選擇（selection）個體，並藉助於自然遺傳學的遺傳運算元（genetic operators）進行組合交叉（crossover）和變異（mutation），產生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的後生代種群比前代更加適應於環境，末代種群中的最優個體經過解碼（decoding），可以作為問題近似最優解。
[編輯本段]遺傳演算法特點
遺傳演算法是解決搜索問題的一種通用演算法，對於各種通用問題都可以使用。搜索演算法的共同特徵為：
① 首先組成一組候選解；
② 依據某些適應性條件測算這些候選解的適應度；
③ 根據適應度保留某些候選解，放棄其他候選解；
④ 對保留的候選解進行某些操作，生成新的候選解。
在遺傳演算法中，上述幾個特徵以一種特殊的方式組合在一起：基於染色體群的並行搜索，帶有猜測性質的選擇操作、交換操作和突變操作。這種特殊的組合方式將遺傳演算法與其它搜索演算法區別開來。
遺傳演算法還具有以下幾方面的特點：
(1)遺傳演算法從問題解的串集開始嫂索，而不是從單個解開始。這是遺傳演算法與傳統優化演算法的極大區別。傳統優化演算法是從單個初始值迭代求最優解的；容易誤入局部最優解。遺傳演算法從串集開始搜索，覆蓋面大，利於全局擇優。
(2)許多傳統搜索演算法都是單點搜索演算法，容易陷入局部的最優解。遺傳演算法同時處理群體中的多個個體，即對搜索空間中的多個解進行評估，減少了陷入局部最優解的風險，同時演算法本身易於實現並行化。
(3)遺傳演算法基本上不用搜索空間的知識或其它輔助信息，而僅用適應度函數值來評估個體，在此基礎上進行遺傳操作。適應度函數不僅不受連續可微的約束，而且其定義域可以任意設定。這一特點使得遺傳演算法的應用范圍大大擴展。
(4)遺傳演算法不是採用確定性規則，而是採用概率的變遷規則來指導他的搜索方向。
(5)具有自組織、自適應和自學習性。遺傳演算法利用進化過程獲得的信息自行組織搜索時，硬度大的個體具有較高的生存概率，並獲得更適應環境的基因結構。
[編輯本段]遺傳演算法的應用
由於遺傳演算法的整體搜索策略和優化搜索方法在計算是不依賴於梯度信息或其它輔助知識，而只需要影響搜索方向的目標函數和相應的適應度函數，所以遺傳演算法提供了一種求解復雜系統問題的通用框架，它不依賴於問題的具體領域，對問題的種類有很強的魯棒性，所以廣泛應用於許多科學，下面我們將介紹遺傳演算法的一些主要應用領域：
1、 函數優化。
函數優化是遺傳演算法的經典應用領域，也是遺傳演算法進行性能評價的常用算例，許多人構造出了各種各樣復雜形式的測試函數：連續函數和離散函數、凸函數和凹函數、低維函數和高維函數、單峰函數和多峰函數等。對於一些非線性、多模型、多目標的函數優化問題，用其它優化方法較難求解，而遺傳演算法可以方便的得到較好的結果。
2、 組合優化
隨著問題規模的增大，組合優化問題的搜索空間也急劇增大，有時在目前的計算上用枚舉法很難求出最優解。對這類復雜的問題，人們已經意識到應把主要精力放在尋求滿意解上，而遺傳演算法是尋求這種滿意解的最佳工具之一。實踐證明，遺傳演算法對於組合優化中的NP問題非常有效。例如遺傳演算法已經在求解旅行商問題、 背包問題、裝箱問題、圖形劃分問題等方面得到成功的應用。
此外，GA也在生產調度問題、自動控制、機器人學、圖象處理、人工生命、遺傳編碼和機器學習等方面獲得了廣泛的運用。
[編輯本段]遺傳演算法的現狀
進入90年代，遺傳演算法迎來了興盛發展時期，無論是理論研究還是應用研究都成了十分熱門的課題。尤其是遺傳演算法的應用研究顯得格外活躍，不但它的應用領域擴大，而且利用遺傳演算法進行優化和規則學習的能力也顯著提高，同時產業應用方面的研究也在摸索之中。此外一些新的理論和方法在應用研究中亦得到了迅速的發展，這些無疑均給遺傳演算法增添了新的活力。遺傳演算法的應用研究已從初期的組合優化求解擴展到了許多更新、更工程化的應用方面。
隨著應用領域的擴展，遺傳演算法的研究出現了幾個引人注目的新動向：一是基於遺傳演算法的機器學習，這一新的研究課題把遺傳演算法從歷來離散的搜索空間的優化搜索演算法擴展到具有獨特的規則生成功能的嶄新的機器學習演算法。這一新的學習機制對於解決人工智慧中知識獲取和知識優化精煉的瓶頸難題帶來了希望。二是遺傳演算法正日益和神經網路、模糊推理以及混沌理論等其它智能計算方法相互滲透和結合，這對開拓21世紀中新的智能計算技術將具有重要的意義。三是並行處理的遺傳演算法的研究十分活躍。這一研究不僅對遺傳演算法本身的發展，而且對於新一代智能計算機體系結構的研究都是十分重要的。四是遺傳演算法和另一個稱為人工生命的嶄新研究領域正不斷滲透。所謂人工生命即是用計算機模擬自然界豐富多彩的生命現象，其中生物的自適應、進化和免疫等現象是人工生命的重要研究對象，而遺傳演算法在這方面將會發揮一定的作用，五是遺傳演算法和進化規劃（Evolution Programming,EP）以及進化策略（Evolution Strategy,ES）等進化計算理論日益結合。EP和ES幾乎是和遺傳演算法同時獨立發展起來的，同遺傳演算法一樣，它們也是模擬自然界生物進化機制的智能計算方法，即同遺傳演算法具有相同之處，也有各自的特點。目前，這三者之間的比較研究和彼此結合的探討正形成熱點。
1991年D.Whitey在他的論文中提出了基於領域交叉的交叉運算元（Adjacency based crossover），這個運算元是特別針對用序號表示基因的個體的交叉，並將其應用到了TSP問題中，通過實驗對其進行了驗證。
D.H.Ackley等提出了隨即迭代遺傳爬山法（Stochastic Iterated Genetic Hill-climbing，SIGH）採用了一種復雜的概率選舉機制，此機制中由m個「投票者」來共同決定新個體的值（m表示群體的大小）。實驗結果表明，SIGH與單點交叉、均勻交叉的神經遺傳演算法相比，所測試的六個函數中有四個表現出更好的性能，而且總體來講，SIGH比現存的許多演算法在求解速度方面更有競爭力。
H.Bersini和G.Seront將遺傳演算法與單一方法（simplex method）結合起來，形成了一種叫單一操作的多親交叉運算元（simplex crossover），該運算元在根據兩個母體以及一個額外的個體產生新個體，事實上他的交叉結果與對三個個體用選舉交叉產生的結果一致。同時，文獻還將三者交叉運算元與點交叉、均勻交叉做了比較，結果表明，三者交叉運算元比其餘兩個有更好的性能。
國內也有不少的專家和學者對遺傳演算法的交叉運算元進行改進。2002年，戴曉明等應用多種群遺傳並行進化的思想，對不同種群基於不同的遺傳策略，如變異概率，不同的變異運算元等來搜索變數空間，並利用種群間遷移運算元來進行遺傳信息交流，以解決經典遺傳演算法的收斂到局部最優值問題
2004年，趙宏立等針對簡單遺傳演算法在較大規模組合優化問題上搜索效率不高的現象，提出了一種用基因塊編碼的並行遺傳演算法（Building-block Coded Parallel GA，BCPGA）。該方法以粗粒度並行遺傳演算法為基本框架，在染色體群體中識別出可能的基因塊，然後用基因塊作為新的基因單位對染色體重新編碼，產生長度較短的染色體，在用重新編碼的染色體群體作為下一輪以相同方式演化的初始群體。
2005年，江雷等針對並行遺傳演算法求解TSP問題,探討了使用彈性策略來維持群體的多樣性,使得演算法跨過局部收斂的障礙,向全局最優解方向進化。
[編輯本段]遺傳演算法的一般演算法
遺傳演算法是基於生物學的，理解或編程都不太難。下面是遺傳演算法的一般演算法：
創建一個隨機的初始狀態
初始種群是從解中隨機選擇出來的，將這些解比喻為染色體或基因，該種群被稱為第一代，這和符號人工智慧系統的情況不一樣，在那裡問題的初始狀態已經給定了。
評估適應度
對每一個解(染色體)指定一個適應度的值，根據問題求解的實際接近程度來指定(以便逼近求解問題的答案)。不要把這些「解」與問題的「答案」混為一談，可以把它理解成為要得到答案，系統可能需要利用的那些特性。
繁殖(包括子代突變)
帶有較高適應度值的那些染色體更可能產生後代(後代產生後也將發生突變)。後代是父母的產物，他們由來自父母的基因結合而成，這個過程被稱為「雜交」。
下一代

如果新的一代包含一個解，能產生一個充分接近或等於期望答案的輸出，那麼問題就已經解決了。如果情況並非如此，新的一代將重復他們父母所進行的繁衍過程，一代一代演化下去，直到達到期望的解為止。
並行計算

非常容易將遺傳演算法用到並行計算和群集環境中。一種方法是直接把每個節點當成一個並行的種群看待。然後有機體根據不同的繁殖方法從一個節點遷移到另一個節點。另一種方法是「農場主/勞工」體系結構，指定一個節點為「農場主」節點，負責選擇有機體和分派適應度的值，另外的節點作為「勞工」節點，負責重新組合、變異和適應度函數的評估。
術語說明
由於遺傳演算法是由進化論和遺傳學機理而產生的搜索演算法，所以在這個演算法中會用到很多生物遺傳學知識，下面是我們將會用來的一些術語說明：
一、染色體(Chronmosome)
染色體又可以叫做基因型個體(indivials),一定數量的個體組成了群體(population),群體中個體的數量叫做群體大小。
二、基因(Gene)
基因是串中的元素，基因用於表示個體的特徵。例如有一個串S＝1011，則其中的1，0，1，1這4個元素分別稱為基因。它們的值稱為等位基因(Alletes)。
三、基因地點(Locus)
基因地點在演算法中表示一個基因在串中的位置稱為基因位置(Gene Position)，有時也簡稱基因位。基因位置由串的左向右計算，例如在串 S＝1101 中，0的基因位置是3。
四、基因特徵值(Gene Feature)
在用串表示整數時，基因的特徵值與二進制數的權一致；例如在串 S=1011 中，基因位置3中的1，它的基因特徵值為2；基因位置1中的1，它的基因特徵值為8。
五、適應度(Fitness)
各個個體對環境的適應程度叫做適應度(fitness)。為了體現染色體的適應能力，引入了對問題中的每一個染色體都能進行度量的函數，叫適應度函數. 這個函數是計算個體在群體中被使用的概率。
[編輯本段]遺傳演算法的運算過程
選擇(復制)：
根據各個個體的適應度，按照一定的規則或方法，從第t代群體P(t)中選擇出一些優良的個體遺傳到下 一代群體P(t+1)中；
交叉：
將群體P(t)內的各個個體隨機搭配成對，對每一對個體，以某個概率(稱為交叉概率）交換它們之間的部分染色體；
變異：
對群體P(t)中的每一個個體，以某一概率(稱為變異概率)改變某一個或某一些基因座上的基因值為其他基因值。