基於遺傳演算法的機器學習

⑴ 什麼是遺傳（要詳細的資料和圖片解說）

摘要
遺傳是指經由基因的傳遞，使後代獲得親代的特徵。遺傳學是研究此一現象的學科，目前已知地球上現存的生命主要是以DNA作為遺傳物質。除了遺傳之外，決定生物特徵的因素還有環境，以及環境與遺傳的交互作用。
[編輯本段]特點
遺傳演算法是一類可用於復雜系統優化的具有魯棒性的搜索演算法，與傳統的優化演算法相比，主要有以下特點：[1]
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問題,探討了使用彈性策略來維持群體的多樣性,使得演算法跨過局部收斂的障礙,向全局最優解方向進化。
[編輯本段]一般演算法
遺傳演算法是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型。它的思想源於生物遺傳學和適者生存的自然規律，是具有「生存＋檢測」的迭代過程的搜索演算法。遺傳演算法以一種群體中的所有個體為對象，並利用隨機化技術指導對一個被編碼的參數空間進行高效搜索。其中，選擇、交叉和變異構成了遺傳演算法的遺傳操作；參數編碼、初始群體的設定、適應度函數的設計、遺傳操作設計、控制參數設定五個要素組成了遺傳演算法的核心內容。 作為一種新的全局優化搜索演算法，遺傳演算法以其簡單通用、魯棒性強、適於並行處理以及高效、實用等顯著特點，在各個領域得到了廣泛應用，取得了良好效果，並逐漸成為重要的智能演算法之一。遺傳演算法是基於生物學的，理解或編程都不太難。下面是遺傳演算法的一般演算法：
��
[編輯本段]創建一個隨機的初始狀態
��初始種群是從解中隨機選擇出來的，將這些解比喻為染色體或基因，該種群被稱為第一代，這和符號人工智慧系統的情況不一樣，在那裡問題的初始狀態已經給定了。
��評估適應度
��對每一個解(染色體)指定一個適應度的值，根據問題求解的實際接近程度來指定(以便逼近求解問題的答案)。不要把這些「解」與問題的「答案」混為一談，可以把它理解成為要得到答案，系統可能需要利用的那些特性。
��繁殖(包括子代突變)
��帶有較高適應度值的那些染色體更可能產生後代(後代產生後也將發生突變)。後代是父母的產物，他們由來自父母的基因結合而成，這個過程被稱為「雜交」。
��下一代
��如果新的一代包含一個解，能產生一個充分接近或等於期望答案的輸出，那麼問題就已經解決了。如果情況並非如此，新的一代將重復他們父母所進行的繁衍過程，一代一代演化下去，直到達到期望的解為止。
��並行計算
��非常容易將遺傳演算法用到並行計算和群集環境中。一種方法是直接把每個節點當成一個並行的種群看待。然後有機體根據不同的繁殖方法從一個節點遷移到另一個節點。另一種方法是「農場主/勞工」體系結構，指定一個節點為「農場主」節點，負責選擇有機體和分派適應度的值，另外的節點作為「勞工」節點，負責重新組合、變異和適應度函數的評估。
[編輯本段]遺傳演算法-基本框架
1 GA的流程圖
GA的流程圖如下圖所示
2 編碼
遺傳演算法不能直接處理問題空間的參數，必須把它們轉換成遺傳空間的由基因按一定結構組成的染色體或個體。這一轉換操作就叫做編碼，也可以稱作(問題的)表示(representation)。
評估編碼策略常採用以下3個規范:
a)完備性(completeness):問題空間中的所有點(候選解)都能作為GA空間中的點(染色體)表現。
b)健全性(soundness): GA空間中的染色體能對應所有問題空間中的候選解。
c)非冗餘性(nonrendancy):染色體和候選解一一對應。
目前的幾種常用的編碼技術有二進制編碼，浮點數編碼，字元編碼，變成編碼等。
而二進值編碼是目前遺傳演算法中最常用的編碼方法。即是由二進值字元集{0, 1}產生通常的0, 1字元串來表示問題空間的候選解。它具有以下特點:
a)簡單易行；
b)符合最小字元集編碼原則；
c)便於用模式定理進行分析，因為模式定理就是以基礎的。
3 適應度函數
進化論中的適應度，是表示某一個體對環境的適應能力，也表示該個體繁殖後代的能力。遺傳演算法的適應度函數也叫評價函數，是用來判斷群體中的個體的優劣程度的指標，它是根據所求問題的目標函數來進行評估的。
遺傳演算法在搜索進化過程中一般不需要其他外部信息，僅用評估函數來評估個體或解的優劣，並作為以後遺傳操作的依據。由於遺傳演算法中，適應度函數要比較排序並在此基礎上計算選擇概率，所以適應度函數的值要取正值.由此可見，在不少場合，將目標函數映射成求最大值形式且函數值非負的適應度函數是必要的。
適應度函數的設計主要滿足以下條件：
a）單值、連續、非負、最大化；
b) 合理、一致性；
c）計算量小；
d）通用性強。
在具體應用中，適應度函數的設計要結合求解問題本身的要求而定。適應度函數設計直接影響到遺傳演算法的性能。
4 初始群體的選取
遺傳演算法中初始群體中的個體是隨機產生的。一般來講，初始群體的設定可採取如下的策略:
a)根據問題固有知識，設法把握最優解所佔空間在整個問題空間中的分布范圍，然後，在此分布范圍內設定初始群體。
b)先隨機生成一定數目的個體，然後從中挑出最好的個體加到初始群體中。這種過程不斷迭代，直到初始群體中個體數達到了預先確定的規模。
[編輯本段]遺傳演算法-遺傳操作
遺傳操作是模擬生物基因遺傳的做法。在遺傳演算法中，通過編碼組成初始群體後，遺傳操作的任務就是對群體的個體按照它們對環境適應度(適應度評估)施加一定的操作，從而實現優勝劣汰的進化過程。從優化搜索的角度而言，遺傳操作可使問題的解，一代又一代地優化，並逼進最優解。
遺傳操作包括以下三個基本遺傳運算元(genetic operator):選擇(selection)；交叉(crossover)；變異(mutation)。這三個遺傳運算元有如下特點:
個體遺傳運算元的操作都是在隨機擾動情況下進行的。因此，群體中個體向最優解遷移的規則是隨機的。需要強調的是，這種隨機化操作和傳統的隨機搜索方法是有區別的。遺傳操作進行的高效有向的搜索而不是如一般隨機搜索方法所進行的無向搜索。
遺傳操作的效果和上述三個遺傳運算元所取的操作概率，編碼方法，群體大小，初始群體以及適應度函數的設定密切相關。
1 選擇
從群體中選擇優勝的個體，淘汰劣質個體的操作叫選擇。選擇運算元有時又稱為再生運算元(reproction operator)。選擇的目的是把優化的個體(或解)直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的，目前常用的選擇運算元有以下幾種:適應度比例方法、隨機遍歷抽樣法、局部選擇法、局部選擇法。
其中輪盤賭選擇法 （roulette wheel selection）是最簡單也是最常用的選擇方法。在該方法中，各個個體的選擇概率和其適應度值成比例。設群體大小為n，其中個體i的適應度為，則i 被選擇的概率,為
顯然，概率反映了個體i的適應度在整個群體的個體適應度總和中所佔的比例.個體適應度越大。其被選擇的概率就越高、反之亦然。計算出群體中各個個體的選擇概率後，為了選擇交配個體，需要進行多輪選擇。每一輪產生一個[0，1]之間均勻隨機數，將該隨機數作為選擇指針來確定被選個體。個體被選後，可隨機地組成交配對，以供後面的交叉操作。
2 交叉
在自然界生物進化過程中起核心作用的是生物遺傳基因的重組(加上變異)。同樣，遺傳演算法中起核心作用的是遺傳操作的交叉運算元。所謂交叉是指把兩個父代個體的部分結構加以替換重組而生成新個體的操作。通過交叉，遺傳演算法的搜索能力得以飛躍提高。
交叉運算元根據交叉率將種群中的兩個個體隨機地交換某些基因，能夠產生新的基因組合，期望將有益基因組合在一起。根據編碼表示方法的不同，可以有以下的演算法：
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 新個體
3 變異
變異運算元的基本內容是對群體中的個體串的某些基因座上的基因值作變動。依據個體編碼表示方法的不同，可以有以下的演算法：
a)實值變異；
b)二進制變異。
一般來說，變異運算元操作的基本步驟如下:
a)對群中所有個體以事先設定的編譯概率判斷是否進行變異；
b)對進行變異的個體隨機選擇變異位進行變異。
遺傳演算法導引入變異的目的有兩個:一是使遺傳演算法具有局部的隨機搜索能力。當遺傳演算法通過交叉運算元已接近最優解鄰域時，利用變異運算元的這種局部隨機搜索能力可以加速向最優解收斂。顯然，此種情況下的變異概率應取較小值，否則接近最優解的積木塊會因變異而遭到破壞。二是使遺傳演算法可維持群體多樣性，以防止出現未成熟收斂現象。此時收斂概率應取較大值。
遺傳演算法中，交叉運算元因其全局搜索能力而作為主要運算元，變異運算元因其局部搜索能力而作為輔助運算元。遺傳演算法通過交叉和變異這對相互配合又相互競爭的操作而使其具備兼顧全局和局部的均衡搜索能力。所謂相互配合.是指當群體在進化中陷於搜索空間中某個超平面而僅靠交叉不能擺脫時，通過變異操作可有助於這種擺脫。所謂相互競爭，是指當通過交叉已形成所期望的積木塊時，變異操作有可能破壞這些積木塊。如何有效地配合使用交叉和變異操作，是目前遺傳演算法的一個重要研究內容。
基本變異運算元是指對群體中的個體碼串隨機挑選一個或多個基因座並對這些基因座的基因值做變動(以變異概率P.做變動)，(0，1)二值碼串中的基本變異操作如下:
基因位下方標有*號的基因發生變異。
變異率的選取一般受種群大小、染色體長度等因素的影響，通常選取很小的值，一般取0.001－0.1。
終止條件
當最優個體的適應度達到給定的閥值，或者最優個體的適應度和群體適應度不再上升時，或者迭代次數達到預設的代數時，演算法終止。預設的代數一般設置為100-500代。
[編輯本段]遺傳演算法-求解演算法的特點分析
遺傳演算法作為一種快捷、簡便、容錯性強的演算法，在各類結構對象的優化過程中顯示出明顯的優勢。與傳統的搜索方法相比，遺傳演算法具有如下特點：
a)搜索過程不直接作用在變數上，而是在參數集進行了編碼的個體。此編碼操作，使得遺傳演算法可直接對結構對象（集合、序列、矩陣、樹、圖、鏈和表）進行操作。
b)搜索過程是從一組解迭代到另一組解，採用同時處理群體中多個個體的方法，降低了陷入局部最優解的可能性，並易於並行化。
c)採用概率的變遷規則來指導搜索方向，而不採用確定性搜索規則。
d)對搜索空間沒有任何特殊要求（如連通性、凸性等），只利用適應性信息，不需要導數等其它輔助信息，適應范圍更廣。
[編輯本段]術語說明
由於遺傳演算法是由進化論和遺傳學機理而產生的搜索演算法，所以在這個演算法中會用到很多生物遺傳學知識，下面是我們將會用來的一些術語說明：
一、染色體(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)。為了體現染色體的適應能力，引入了對問題中的每一個染色體都能進行度量的函數，叫適應度函數. 這個函數是計算個體在群體中被使用的概率。
[編輯本段]參考資料
1.《計算機教育》第10期 作者：王利
2.遺傳演算法——理論、應用與軟體實現 王小平、曹立明著
3.同濟大學計算機系 王小平編寫的程序代碼

參考資料
1. 中新網：英13歲少女患家族遺傳怪病 滿臉皺紋像老人，2010年01月27日

http://www.chinanews.com.cn/gj/gj-ywdd2/news/2010/01-27/2094204.shtml

⑵ 遺傳演算法有哪些方向

遺傳演算法研究方向主要有以下幾個方面：
1. 遺傳演算法基礎理論研究
在遺傳演算法中,群體規模和遺傳運算元的控制參數的選取 是必要的試驗參數。
遺傳演算法的收斂也是遺傳演算法基礎理論研究方向之一。

2. 遺傳演算法的分類系統
分類系統屬於基於遺傳演算法的機器學習中的一類,包括一個簡單 的基於串規則的並行生成子系統、規則評價子系統和遺傳演算法子系統 。
分類系統被人們越來越多地應用在科學、工程和經濟領域中,是目 前遺傳演算法研究中一個十分活躍的領域。
3. 分布並行遺傳演算法
分布並行遺傳算 法的研究表明,只要通過保持多個群體和恰當控制群體間的相互作用 來模擬並行執行過程,即使不使用並行計算機,也能提高演算法的執行效 率。
4. 遺傳進化演算法
模擬自然進化過程可以產生魯棒的計算機演算法--進化演算法。其餘兩種演算法是進化規劃和進化策略 。

5. 遺傳神經網路
包括連接權、網路結構和學習規則的進化。

⑶ 遺傳演算法的優缺點

優點：

1、遺傳演算法是以決策變數的編碼作為運算對象，可以直接對集合、序列、矩陣、樹、圖等結構對象進行操作。這樣的方式一方面有助於模擬生物的基因、染色體和遺傳進化的過程，方便遺傳操作運算元的運用。

另一方面也使得遺傳演算法具有廣泛的應用領域，如函數優化、生產調度、自動控制、圖像處理、機器學習、數據挖掘等領域。

2、遺傳演算法直接以目標函數值作為搜索信息。它僅僅使用適應度函數值來度量個體的優良程度，不涉及目標函數值求導求微分的過程。因為在現實中很多目標函數是很難求導的，甚至是不存在導數的，所以這一點也使得遺傳演算法顯示出高度的優越性。

3、遺傳演算法具有群體搜索的特性。它的搜索過程是從一個具有多個個體的初始群體P(0)開始的，一方面可以有效地避免搜索一些不必搜索的點。

另一方面由於傳統的單點搜索方法在對多峰分布的搜索空間進行搜索時很容易陷入局部某個單峰的極值點，而遺傳演算法的群體搜索特性卻可以避免這樣的問題，因而可以體現出遺傳演算法的並行化和較好的全局搜索性。

4、遺傳演算法基於概率規則，而不是確定性規則。這使得搜索更為靈活，參數對其搜索效果的影響也盡可能的小。

5、遺傳演算法具有可擴展性，易於與其他技術混合使用。以上幾點便是遺傳演算法作為優化演算法所具備的優點。

缺點：

1、遺傳演算法在進行編碼時容易出現不規范不準確的問題。

2、由於單一的遺傳演算法編碼不能全面將優化問題的約束表示出來，因此需要考慮對不可行解採用閾值，進而增加了工作量和求解時間。

3、遺傳演算法效率通常低於其他傳統的優化方法。

4、遺傳演算法容易出現過早收斂的問題。

(3)基於遺傳演算法的機器學習擴展閱讀

遺傳演算法的機理相對復雜，在Matlab中已經由封裝好的工具箱命令，通過調用就能夠十分方便的使用遺傳演算法。

函數ga：[x, fval,reason]= ga(@fitnessfun, nvars, options)x是最優解，fval是最優值，@fitnessness是目標函數，nvars是自變數個數，options是其他屬性設置。系統默認求最小值，所以在求最大值時應在寫函數文檔時加負號。

為了設置options，需要用到下面這個函數：options=gaoptimset('PropertyName1', 'PropertyValue1', 'PropertyName2', 'PropertyValue2','PropertyName3', 'PropertyValue3', ...)通過這個函數就能夠實現對部分遺傳演算法的參數的設置。

⑷ 遺傳演算法研究進展

遺傳演算法^{［56，53］}研究的興起是在20世紀80年代末和90年代初期，但它的歷史起源可追溯到20世紀60年代初期。早期的研究大多以對自然遺傳系統的計算機模擬為主。早期遺傳演算法的研究特點是側重於對一些復雜的操作的研究。雖然其中像自動博弈、生物系統模擬、模式識別和函數優化等給人以深刻的印象，但總的來說這是一個無明確目標的發展時期，缺乏帶有指導性的理論和計算工具的開拓。這種現象直到20世紀70年代中期由於Holland和De Jong的創造性研究成果的發表才得到改觀。當然，早期的研究成果對於遺傳演算法的發展仍然有一定的影響，尤其是其中一些有代表性的技術和方法已為當前的遺傳演算法所吸收和發展。

在遺傳演算法作為搜索方法用於人工智慧系統中之前，已有不少生物學家用計算機來模擬自然遺傳系統。尤其是Fraser的模擬研究，他於1962年提出了和現在的遺傳演算法十分相似的概念和思想。但是，Fraser和其他一些學者並未認識到自然遺傳演算法可以轉化為人工遺傳演算法。Holland教授及其學生不久就認識到這一轉化的重要性，Holland認為比起尋找這種或那種具體的求解問題的方法來說，開拓一種能模擬自然選擇遺傳機制的帶有一般性的理論和方法更有意義。在這一時期，Holland不但發現了基於適應度的人工遺傳選擇的基本作用，而且還對群體操作等進行了認真的研究。1965年，他首次提出了人工遺傳操作的重要性，並把這些應用於自然系統和人工系統中。

1967年，Bagley在他的論文中首次提出了遺傳演算法（genetic algorithm）這一術語，並討論了遺傳演算法在自動博弈中的應用。他所提出的包括選擇、交叉和變異的操作已與目前遺傳演算法中的相應操作十分接近。尤其是他對選擇操作做了十分有意義的研究。他認識到，在遺傳進化過程的前期和後期，選擇概率應合適地變動。為此，他引入了適應度定標（scaling）概念，這是目前遺傳演算法中常用的技術。同時，他也首次提出了遺傳演算法自我調整概念，即把交叉和變異的概率融於染色體本身的編碼中，從而可實現演算法自我調整優化。盡管Bagley沒有對此進行計算機模擬實驗，但這些思想對於後來遺傳演算法的發展所起的作用是十分明顯的。

在同一時期，Rosenberg也對遺傳演算法進行了研究，他的研究依然是以模擬生物進化為主，但他在遺傳操作方面提出了不少獨特的設想。1970年Cavicchio把遺傳演算法應用於模式識別中。實際上他並未直接涉及到模式識別，而僅用遺傳演算法設計一組用於識別的檢測器。Cavicchio對於遺傳操作以及遺傳演算法的自我調整也做了不少有特色的研究。

Weinberg於1971年發表了題為《活細胞的計算機模擬》的論文。由於他和Rosenberg一樣注意於生物遺傳的模擬，所以他對遺傳演算法的貢獻有時被忽略。實際上，他提出的多層次或多級遺傳演算法至今仍給人以深刻的印象。

第一個把遺傳演算法用於函數優化的是Hollstien。1971年他在論文《計算機控制系統中的人工遺傳自適應方法》中闡述了遺傳演算法用於數字反饋控制的方法。實際上，他主要是討論了對於二變數函數的優化問題。其中，對於優勢基因控制、交叉和變異以及各種編碼技術進行了深入的研究。

1975年在遺傳演算法研究的歷史上是十分重要的一年。這一年，Holland出版了他的著名專著《自然系統和人工系統的適配》。該書系統地闡述了遺傳演算法的基本理論和方法，並提出了對遺傳演算法的理論研究和發展極為重要的模式理論（schemata theory）。該理論首次確認了結構重組遺傳操作對於獲得隱並行性的重要性。直到這時才知道遺傳操作到底在干什麼，為什麼又幹得那麼出色，這對於以後陸續開發出來的遺傳操作具有不可估量的指導作用。

同年，De Jong完成了他的重要論文《遺傳自適應系統的行為分析》。他在該論文中所做的研究工作可看作是遺傳演算法發展進程中的一個里程碑，這是因為他把Holland的模式理論與他的計算實驗結合起來。盡管De Jong和Hollstien一樣主要側重於函數優化的應用研究，但他將選擇、交叉和變異操作進一步完善和系統化，同時又提出了諸如代溝（generation gap）等新的遺傳操作技術。可以認為，De Jong的研究工作為遺傳演算法及其應用打下了堅實的基礎，他所得出的許多結論迄今仍具有普遍的指導意義。

進入20世紀80年代，遺傳演算法迎來了興盛發展時期，無論是理論研究還是應用研究都成了十分熱門的課題。尤其是遺傳演算法的應用研究顯得格外活躍，不但它的應用領域擴大，而且利用遺傳演算法進行優化和規則學習的能力也顯著提高，同時產業應用方面的研究也在摸索之中。此外一些新的理論和方法在應用研究中亦得到了迅速的發展，這些無疑均給遺傳演算法增添了新的活力。

隨著應用領域的擴展，遺傳演算法的研究出現了幾個引人注目的新動向：一是基於遺傳演算法的機器學習（Genetic Base Machine Learning），這一新的研究課題把遺傳演算法從歷來離散的搜索空間的優化搜索演算法擴展到具有獨特的規則生成功能的嶄新的機器學習演算法。這一新的學習機制對於解決人工智慧中知識獲取和知識優化精煉的瓶頸難題帶來了希望。二是遺傳演算法正日益和神經網路、模糊推理以及混沌理論等其他智能計算方法相互滲透和結合，這對開拓21世紀中新的智能計算技術將具有重要的意義。三是並行處理的遺傳演算法的研究十分活躍。這一研究不僅對遺傳演算法本身的發展，而且對於新一代智能計算機體系結構的研究都是十分重要的。四是遺傳演算法和另一個稱為人工生命的嶄新研究領域正不斷滲透。所謂人工生命即是用計算機模擬自然界豐富多彩的生命現象，其中生物的自適應、進化和免疫等現象是人工生命的重要研究對象，而遺傳演算法在這方面將會發揮一定的作用。五是遺傳演算法和進化規劃（Evolution Programming，EP）以及進化策略（Evolution Strategy，ES）等進化計算理論日益結合。EP和ES幾乎是和遺傳演算法同時獨立發展起來的，同遺傳演算法一樣，它們也是模擬自然界生物進化機制的智能計算方法，既同遺傳演算法具有相同之處，也有各自的特點。

隨著遺傳演算法研究和應用的不斷深入和發展，一系列以遺傳演算法為主題的國際會議十分活躍。從1985年開始，國際遺傳演算法會議，即ICGA（International Conference on Genetic Algorithm）每兩年舉行一次。在歐洲，從1990年開始也每隔一年舉辦一次類似的會議，即 PPSN（Parallel Problem Solving from Nature）會議。除了遺傳演算法外，大部分有關ES和EP的學術論文也出現在PPSN中。另外，以遺傳演算法的理論基礎為中心的學術會議有FOGA（Foundation of Genetic Algorithm）。它也是從1990年開始，隔年召開一次。這些國際學術會議論文集中反映了遺傳演算法近些年來的最新發展和動向。

⑸ 遺傳演算法ai影響

遺傳演算法(GA)是基於自然選擇和遺傳學概念的基於搜索的演算法。遺傳演算法是稱為進化計算的更大分支的一個子集。
GAs 由 John Holland 及其在密歇根大學的學生和同事開發，最著名的是 David E.Goldberg。自那以來，它一直在嘗試各種優化問題並取得了很高的成功。
在 GAs 中，我們為給定問題提供了一系列可能的解決方案。這些解決方案然後經歷重組和突變(如在自然遺傳學中)，產生新的兒童，並且該過程在各代重復。每個個體(或候選解決方案)都被分配一個適應值(基於其目標函數值)，並且適合者個體被賦予更高的配偶並產生更適合個體的機會。這符合達爾文適者生存理論。
因此，它不斷發展更好的個人或解決方案，直到達到停止標准。
遺傳演算法在本質上具有充分的隨機性，但它們比隨機局部搜索(我們只是嘗試隨機解決方案，追蹤迄今為止最好的)的性能好得多，因為它們也在利用歷史信息。

⑹ Python實現基於遺傳演算法的排課優化

排課問題的本質是將課程、教師和學生在合適的時間段內分配到合適的教室中，涉及到的因素較多，是一個多目標的調度問題，在運籌學中被稱為時間表問題（Timetable Problem，TTP）。設一個星期有n個時段可排課，有m位教師需要參與排課，平均每位教師一個星期上k節課，在不考慮其他限制的情況下，能夠推出的可能組合就有 種，如此高的復雜度是目前計算機所無法承受的。因此眾多研究者提出了多種其他排課演算法，如模擬退火，列表尋優搜索和約束滿意等。

Github ： https://github.com/xiaochus/GeneticClassSchele

遺傳演算法（Genetic Algorithm）是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。遺傳演算法的流程如下所示：

遺傳演算法首先針對待解決問題隨機生成一組解，我們稱之為種群（Population）。種群中的每個個體都是問題的解，在優化的過程中，演算法會計算整個種群的成本函數，從而得到一個與種群相關的適應度的序列。如下圖所示：

為了得到新的下一代種群，首先根據適應度對種群進行排序，從中挑選出最優的幾個個體加入下一代種群，這一個過程也被稱為精英選拔。新種群餘下的部分通過對選拔出來的精英個體進行修改得到。

對種群進行修改的方法參考了生物DAN進化的方法，一般使用兩種方法： 變異 和 交叉 。 變異 的做法是對種群做一個微小的、隨機的改變。如果解的編碼方式是二進制，那麼就隨機選取一個位置進行0和1的互相突變；如果解的編碼方式是十進制，那麼就隨機選取一個位置進行隨機加減。 交叉 的做法是隨機從最優種群中選取兩個個體，以某個位置為交叉點合成一個新的個體。

經過突變和交叉後我們得到新的種群（大小與上一代種群一致），對新種群重復重復上述過程，直到達到迭代次數（失敗）或者解的適應性達到我們的要求（成功），GA演算法就結束了。

演算法實現

首先定義一個課程類，這個類包含了課程、班級、教師、教室、星期、時間幾個屬性，其中前三個是我們自定義的，後面三個是需要演算法來優化的。

接下來定義cost函數，這個函數用來計算課表種群的沖突。當被測試課表沖突為0的時候，這個課表就是個符合規定的課表。沖突檢測遵循下面幾條規則：

使用遺傳演算法進行優化的過程如下，與上一節的流程圖過程相同。

init_population ：隨機初始化不同的種群。
mutate ：變異操作，隨機對 Schele 對象中的某個可改變屬性在允許范圍內進行隨機加減。
crossover ：交叉操作，隨機對兩個對象交換不同位置的屬性。
evolution ：啟動GA演算法進行優化。

實驗結果

下面定義了3個班，6種課程、教師和3個教室來對排課效果進行測試。

優化結果如下，迭代到第68次時，課程安排不存在任何沖突。

選擇1203班的課表進行可視化，如下所示，演算法合理的安排了對應的課程。