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

摘要

遺傳是指經由基因的傳遞，使後代獲得親代的特征。遺傳學是研究此壹現象的學科，目前已知地球上現存的生命主要是以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)非冗余性(nonredundancy):染色體和候選解壹壹對應。

目前的幾種常用的編碼技術有二進制編碼，浮點數編碼，字符編碼，變成編碼等。

而二進值編碼是目前遺傳算法中最常用的編碼方法。即是由二進值字符集{0, 1}產生通常的0, 1字符串來表示問題空間的候選解。它具有以下特點:

a)簡單易行；

b)符合最小字符集編碼原則；

c)便於用模式定理進行分析，因為模式定理就是以基礎的。

3 適應度函數

進化論中的適應度，是表示某壹個體對環境的適應能力，也表示該個體繁殖後代的能力。遺傳算法的適應度函數也叫評價函數，是用來判斷群體中的個體的優劣程度的指標，它是根據所求問題的目標函數來進行評估的。

遺傳算法在搜索進化過程中壹般不需要其他外部信息，僅用評估函數來評估個體或解的優劣，並作為以後遺傳操作的依據。由於遺傳算法中，適應度函數要比較排序並在此基礎上計算選擇概率，所以適應度函數的值要取正值.由此可見，在不少場合，將目標函數映射成求最大值形式且函數值非負的適應度函數是必要的。

適應度函數的設計主要滿足以下條件：

a）單值、連續、非負、最大化；

b) 合理、壹致性；

c）計算量小；

d）通用性強。

在具體應用中，適應度函數的設計要結合求解問題本身的要求而定。適應度函數設計直接影響到遺傳算法的性能。

4 初始群體的選取

遺傳算法中初始群體中的個體是隨機產生的。壹般來講，初始群體的設定可采取如下的策略:

a)根據問題固有知識，設法把握最優解所占空間在整個問題空間中的分布範圍，然後，在此分布範圍內設定初始群體。

b)先隨機生成壹定數目的個體，然後從中挑出最好的個體加到初始群體中。這種過程不斷叠代，直到初始群體中個體數達到了預先確定的規模。

[編輯本段]遺傳算法-遺傳操作

遺傳操作是模擬生物基因遺傳的做法。在遺傳算法中，通過編碼組成初始群體後，遺傳操作的任務就是對群體的個體按照它們對環境適應度(適應度評估)施加壹定的操作，從而實現優勝劣汰的進化過程。從優化搜索的角度而言，遺傳操作可使問題的解，壹代又壹代地優化，並逼進最優解。

遺傳操作包括以下三個基本遺傳算子(genetic operator):選擇(selection)；交叉(crossover)；變異(mutation)。這三個遺傳算子有如下特點:

個體遺傳算子的操作都是在隨機擾動情況下進行的。因此，群體中個體向最優解遷移的規則是隨機的。需要強調的是，這種隨機化操作和傳統的隨機搜索方法是有區別的。遺傳操作進行的高效有向的搜索而不是如壹般隨機搜索方法所進行的無向搜索。

遺傳操作的效果和上述三個遺傳算子所取的操作概率，編碼方法，群體大小，初始群體以及適應度函數的設定密切相關。

1 選擇

從群體中選擇優勝的個體，淘汰劣質個體的操作叫選擇。選擇算子有時又稱為再生算子(reproduction 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 reduced 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)對搜索空間沒有任何特殊要求（如連通性、凸性等），只利用適應性信息，不需要導數等其它輔助信息，適應範圍更廣。

[編輯本段]術語說明