遺傳算法檢視原始碼討論檢視歷史
遺傳算法（Genetic Algorithm，GA）最早是由美國的 John holland於20世紀70年代提出,該算法是根據大自然中生物體進化規律而設計提出的。是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。該算法通過數學的方式,利用計算機仿真運算,將問題的求解過程轉換成類似生物進化中的染色體基因的交叉、變異等過程。在求解較為複雜的組合優化問題時,相對一些常規的優化算法,通常能夠較快地獲得較好的優化結果。遺傳算法已被人們廣泛地應用於組合優化、機器學習、信號處理、自適應控制和人工生命等領域。 [1]
中文名:遺傳算法
基本概念:是一類借鑑生物界的進化規律設計的算法
基本操作:算子選擇、雜交、變異
特 點:模擬自然進化搜索最優解
應 用:組合優化、人工生命等
目錄
簡介
遺傳算法的起源可追溯到20世紀60年代初期。1967年,美國密歇根大學J. Holland教授的學生 Bagley在他的博士論文中首次提出了遺傳算法這一術語,並討論了遺傳算法在博弈中的應用,但早期研究缺乏帶有指導性的理論和計算工具的開拓。1975年, J. Holland等提出了對遺傳算法理論研究極為重要的模式理論,出版了專著《自然系統和人工系統的適配》,在書中系統闡述了遺傳算法的基本理論和方法,推動了遺傳算法的發展。20世紀80年代後,遺傳算法進入興盛發展時期，被廣泛應用於自動控制、生產計劃、圖像處理、機器人等研究領域。
基本框架
編碼
由於遺傳算法不能直接處理問題空間的參數,因此必須通過編碼將要求解的問題表示成遺傳空間的染色體或者個體。這一轉換操作就叫做編碼，也可以稱作（問題的）表示（representation）。
評估編碼策略常採用以下3個規範：
a)完備性(completeness):問題空間中的所有點(候選解)都能作為GA空間中的點(染色體)表現。
b)健全性(soundness): GA空間中的染色體能對應所有問題空間中的候選解。
c)非冗餘性(nonredundancy):染色體和候選解一一對應。
適應度函數
進化論中的適應度，是表示某一個體對環境的適應能力，也表示該個體繁殖後代的能力。遺傳算法的適應度函數也叫評價函數，是用來判斷群體中的個體的優劣程度的指標，它是根據所求問題的目標函數來進行評估的。
遺傳算法在搜索進化過程中一般不需要其他外部信息，僅用評估函數來評估個體或解的優劣，並作為以後遺傳操作的依據。由於遺傳算法中，適應度函數要比較排序並在此基礎上計算選擇概率，所以適應度函數的值要取正值。由此可見，在不少場合，將目標函數映射成求最大值形式且函數值非負的適應度函數是必要的。
適應度函數的設計主要滿足以下條件：
a）單值、連續、非負、最大化
b) 合理、一致性
c）計算量小
d）通用性強。
在具體應用中，適應度函數的設計要結合求解問題本身的要求而定。適應度函數設計直接影響到遺傳算法的性能。
初始群體選取
遺傳算法中初始群體中的個體是隨機產生的。一般來講，初始群體的設定可採取如下的策略:
a)根據問題固有知識，設法把握最優解所占空間在整個問題空間中的分布範圍，然後，在此分布範圍內設定初始群體。
b)先隨機生成一定數目的個體，然後從中挑出最好的個體加到初始群體中。這種過程不斷迭代，直到初始群體中個體數達到了預先確定的規模。
運算過程
遺傳算法的基本運算過程如下：
（1）初始化：設置進化代數計數器t=0，設置最大進化代數T，隨機生成M個個體作為初始群體P(0)。
（2）個體評價：計算群體P(t)中各個個體的適應度。
（3）選擇運算：將選擇算子作用於群體。選擇的目的是把優化的個體直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。
（4）交叉運算：將交叉算子作用於群體。遺傳算法中起核心作用的就是交叉算子。
（5）變異運算：將變異算子作用於群體。即是對群體中的個體串的某些基因座上的基因值作變動。群體P(t)經過選擇、交叉、變異運算之後得到下一代群體P(t+1)。
（6）終止條件判斷：若t=T,則以進化過程中所得到的具有最大適應度個體作為最優解輸出，終止計算。
遺傳操作包括以下三個基本遺傳算子(genetic operator):選擇(selection)；交叉(crossover)；變異(mutation)。
選擇
從群體中選擇優勝的個體，淘汰劣質個體的操作叫選擇。選擇算子有時又稱為再生算子(reproduction operator)。選擇的目的是把優化的個體(或解)直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的，常用的選擇算子有以下幾種：適應度比例方法、隨機遍歷抽樣法、局部選擇法。
交叉
在自然界生物進化過程中起核心作用的是生物遺傳基因的重組(加上變異)。同樣，遺傳算法中起核心作用的是遺傳操作的交叉算子。所謂交叉是指把兩個父代個體的部分結構加以替換重組而生成新個體的操作。通過交叉，遺傳算法的搜索能力得以飛躍提高。
變異
變異算子的基本內容是對群體中的個體串的某些基因座上的基因值作變動。依據個體編碼表示方法的不同，可以有以下的算法：
a)實值變異。
b)二進制變異。
一般來說，變異算子操作的基本步驟如下：
a)對群中所有個體以事先設定的變異概率判斷是否進行變異
b)對進行變異的個體隨機選擇變異位進行變異。
遺傳算法引入變異的目的有兩個:一是使遺傳算法具有局部的隨機搜索能力。當遺傳算法通過交叉算子已接近最優解鄰域時，利用變異算子的這種局部隨機搜索能力可以加速向最優解收斂。顯然，此種情況下的變異概率應取較小值，否則接近最優解的積木塊會因變異而遭到破壞。二是使遺傳算法可維持群體多樣性，以防止出現未成熟收斂現象。此時收斂概率應取較大值。
終止條件
當最優個體的適應度達到給定的閾值，或者最優個體的適應度和群體適應度不再上升時，或者迭代次數達到預設的代數時，算法終止。預設的代數一般設置為100-500代。
特點
遺傳算法是解決搜索問題的一種通用算法，對於各種通用問題都可以使用。搜索算法的共同特徵為： [2]
（1） 首先組成一組候選解
（2）依據某些適應性條件測算這些候選解的適應度
（3）根據適應度保留某些候選解，放棄其他候選解
（4） 對保留的候選解進行某些操作，生成新的候選解。
在遺傳算法中，上述幾個特徵以一種特殊的方式組合在一起：基於染色體群的並行搜索，帶有猜測性質的選擇操作、交換操作和突變操作。這種特殊的組合方式將遺傳算法與其它搜索算法區別開來。
遺傳算法還具有以下幾方面的特點：
（1）算法從問題解的串集開始搜索，而不是從單個解開始。這是遺傳算法與傳統優化算法的極大區別。傳統優化算法是從單個初始值迭代求最優解的；容易誤入局部最優解。遺傳算法從串集開始搜索，覆蓋面大，利於全局擇優。
（2）遺傳算法同時處理群體中的多個個體，即對搜索空間中的多個解進行評估，減少了陷入局部最優解的風險，同時算法本身易於實現並行化。
（3）遺傳算法基本上不用搜索空間的知識或其它輔助信息，而僅用適應度函數值來評估個體，在此基礎上進行遺傳操作。適應度函數不僅不受連續可微的約束，而且其定義域可以任意設定。這一特點使得遺傳算法的應用範圍大大擴展。
（4）遺傳算法不是採用確定性規則，而是採用概率的變遷規則來指導他的搜索方向。
（5）具有自組織、自適應和自學習性。遺傳算法利用進化過程獲得的信息自行組織搜索時，適應度大的個體具有較高的生存概率，並獲得更適應環境的基因結構。
（6）此外，算法本身也可以採用動態自適應技術，在進化過程中自動調整算法控制參數和編碼精度，比如使用模糊自適應法。
不足之處
（1）編碼不規範及編碼存在表示的不準確性。
（2）單一的遺傳算法編碼不能全面地將優化問題的約束表示出來。考慮約束的一個方法就是對不可行解採用閾值，這樣，計算的時間必然增加。
（3）遺傳算法通常的效率比其他傳統的優化方法低。
（4）遺傳算法容易過早收斂。
（5）遺傳算法對算法的精度、可行度、計算複雜性等方面，還沒有有效的定量分析方法。
應用
由於遺傳算法的整體搜索策略和優化搜索方法在計算時不依賴於梯度信息或其它輔助知識，而只需要影響搜索方向的目標函數和相應的適應度函數，所以遺傳算法提供了一種求解複雜系統問題的通用框架，它不依賴於問題的具體領域，對問題的種類有很強的魯棒性，所以廣泛應用於許多科學，下面我們將介紹遺傳算法的一些主要應用領域：[3]
函數優化
函數優化是遺傳算法的經典應用領域，也是遺傳算法進行性能評價的常用算例，許多人構造出了各種各樣複雜形式的測試函數：連續函數和離散函數、凸函數和凹函數、低維函數和高維函數、單峰函數和多峰函數等。對於一些非線性、多模型、多目標的函數優化問題，用其它優化方法較難求解，而遺傳算法可以方便的得到較好的結果。
組合優化
隨着問題規模的增大，組合優化問題的搜索空間也急劇增大，有時在計算上用枚舉法很難求出最優解。對這類複雜的問題，人們已經意識到應把主要精力放在尋求滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。實踐證明，遺傳算法對於組合優化中的NP問題非常有效。例如遺傳算法已經在求解旅行商問題、 背包問題、裝箱問題、圖形劃分問題等方面得到成功的應用。
此外，GA也在生產調度問題、自動控制、機器人學、圖象處理、人工生命、遺傳編碼和機器學習等方面獲得了廣泛的運用。
車間調度
車間調度問題是一個典型的NP-Hard問題，遺傳算法作為一種經典的智能算法廣泛用於車間調度中，很多學者都致力於用遺傳算法解決車間調度問題，現今也取得了十分豐碩的成果。從最初的傳統車間調度（JSP）問題到柔性作業車間調度問題（FJSP），遺傳算法都有優異的表現，在很多算例中都得到了最優或近優解。 [4]
視頻
遺傳算法講解
；