【文章內(nèi)容簡介】 提出本文主要用基于操作的編碼方式 .還有提出了幾種主要的遺傳算子。并且以四個工件四個機(jī)器問題進(jìn)行舉例 ,說明了用遺傳算法解決車間調(diào)度問題的可行性 。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 6 頁 2 遺傳算法相關(guān)理論與實現(xiàn)技術(shù) 遺傳算法 (Geic Algorithm, GA)是一種基于自然群體遺傳演化機(jī)制的高效探索算法，它是美國學(xué)者 Holland 于 1975 年首先提出來的 ［ 7］ 。它摒棄了傳統(tǒng)的搜索方式，模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程 ［ 8］ 。它將問題域中的可能解看作是群體的一個個體或染色體，并將每一個體編碼成符號串形式，對群體反復(fù)進(jìn)行基于遺傳學(xué)的操作（遺傳，交叉和變異），根據(jù)預(yù)定的目標(biāo)適應(yīng)度函數(shù)對每個個體進(jìn)行評價，依據(jù)適者生存，優(yōu)勝劣 汰的進(jìn)化規(guī)則，不斷得到更優(yōu)的群體，同時以全局并行搜索方式來搜索優(yōu)化群體中的最優(yōu)個體，求得滿足要求的最優(yōu)解。 自然進(jìn)化與遺傳算法 自從達(dá)爾文的進(jìn)化論得到人們的接受之后，生物學(xué)家們就對進(jìn)化機(jī)制產(chǎn)生了極大的興趣?；涗洷砻魑覀兯^察的復(fù)雜結(jié)構(gòu)的生命是在相對短的時間進(jìn)化而來的，對這一點(diǎn)包括生物學(xué)家在內(nèi)的許多人都感到驚奇。 雖然目前人們對進(jìn)化機(jī)制在一些方面還沒有弄清楚，但它們的一些特征已為人所知。進(jìn)化是發(fā)生在編碼染色體上，通過對染色體的譯碼部分生成生物體，但下面幾個關(guān)于進(jìn)化理論的一般特性已被廣大人們所接受 。 ，而不是發(fā)生在它們所編碼地生物個體上。 ，哪些適應(yīng)性好地個體的染色體經(jīng)常比差的個體的染色體有更多的繁殖機(jī)會。 ，變異可以使生物體子代的染色體不同于它們父代的染色體，通過結(jié)合兩個父代染色體的物質(zhì)，重組過程可以在子代中產(chǎn)生有很大差異的染色體。 。有關(guān)產(chǎn)生個體的信息包含在個體所攜帶的染色體的集合以及染色體編碼的結(jié)構(gòu)之中，這些個體會很好的適應(yīng)它們的環(huán)境。 大多數(shù)生物體是通過自然選擇 和有性生殖這兩種基本過程進(jìn)行演化的。自然選擇的原則是適應(yīng)者生存，不適者淘汰。自然選擇決定了群體中那些個個體能存活并繁殖，有性生殖保證了后代基因中的混合與重組。比起那些僅包 含 單個親本的基因拷貝和依靠偶然變異來改進(jìn)的后代，這種由基因重組產(chǎn)生的后代進(jìn)化要快得多。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 7 頁 基本 遺傳算法 遺傳算法的基本思路 ； 將求解空間中的每一個點(diǎn)進(jìn)行編碼，并從求解空間中任選 N個點(diǎn)組成初始群體； 。運(yùn)用選擇、交叉、變異算子產(chǎn)生新一代群體； ，若找到滿足問題的最優(yōu)解，結(jié)束；否則，轉(zhuǎn)步驟 3。 遺傳算法的 模式定理 選擇操作是遺傳算法中體現(xiàn)“適者生存”的關(guān)鍵一環(huán)，它能控制高適應(yīng)度的模式成指數(shù)級增長。最常用的選擇方式是“輪盤賭”法。其傳統(tǒng)實現(xiàn)建立在逐項比較的基礎(chǔ)上，算法復(fù)雜度為 O（ n＾ 2） 。通過把各碼鏈適應(yīng)值轉(zhuǎn)換為一組具有線性序的區(qū)間，從而可利用二分查找法實現(xiàn)“輪盤賭”選擇操作的遞歸算法，使時間復(fù)雜度下降到 O（ nlog2n）。 交換操作是有規(guī)則的信息交換，它 能創(chuàng)建新的模式結(jié)構(gòu)，但又最低限度地破壞選擇操作過程所選擇的高適應(yīng)度的模式。假設(shè)交換操作是采用的單點(diǎn)隨機(jī)雜交方式，隨機(jī)選取雜交的起始位置，交叉概率為 Pc，兩個具有相同模式 H 的個體發(fā)生交換，即雜交操作，不會改變模式 H。但是如果其中一方個體不具有模式 H，則有可能會引起另一個個體模式的改變。其中一方不具有模式 H 的概率為 1 p(H, t)，當(dāng)兩個個體發(fā)生交換時，如果引起模式 H 的改變，只可能將交換的起始位置選擇在第一個模式位到最后一個模式位之間的任何一個位置上，此時，使模式 H 生存的概率 Ps，為 : ()1 1scHPPl??? ? () 在交換過程中，可能使兩個都不具備模式 H 的個體經(jīng)交換后產(chǎn)生模式 H，故生存概率（ ()1 1c HP l?? ?）只是一個下界，則有： 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 8 頁 ()11scHPPl??? ? () 綜合考慮選擇操作， 模式 H 在下一代中的數(shù)量可以用下式來綜合估計 : _( ) ( )( , 1 ) ( , ) ( 1 )1cf H Hm H t m H t p lf ?? ? ? ?? () 從上式可以看出，模式的平均適應(yīng)度高于群體平均適應(yīng)度，并且具有短定義距的模式，將在下一代中成指數(shù)級的增長。 通過變異操作對個體串中單個位置進(jìn)行代碼替換，替換的概率為變異概率 Pm，則該位置不發(fā)生變異的概率為 1Pm。要使一個模式 H 在變異操作過程中不被破壞，就要保證模式 H 中確定位必須保證不變，因此，模式 H 保持不變的概率為 : ()(1 ) 1 ( )OHs m mp p P o H? ? ? ? ? () 上式中 O(H)為該模式的階數(shù)。 綜合上面所述，考慮到選擇操作、交換操作和變異操作對模式的影響，則第 t 代種群 P(t)經(jīng)過遺傳操作后下一代種群 P(t+1)具有模式 H 的個體總數(shù)為 : _( ) ( )( , 1 ) ( , ) ( 1 ) ( 1 ( ) )1cmf H Hm H t m H t P P o Hlf?? ? ? ??? () 該式表示了下述的模式定理。 模式定理 :在 遺傳算子選擇、交換、變異的作用下，具有低階、短定義距以及平均適應(yīng)度高于群體平均適應(yīng)度的模式，在子代中將得以指數(shù)級增長。 模式定理保證了較優(yōu)的模式 (遺傳算法的較優(yōu)解 )的數(shù)目呈指數(shù)增長，為解釋遺傳算法機(jī)理提供了數(shù)學(xué)基礎(chǔ)。 由模式定理可知，具有低階、短定義距以及平均適應(yīng)度高于群體平均適應(yīng)度的模式在后代中呈指數(shù)級增長。這些模式在遺傳中很重要，稱為基因塊。 基因塊假設(shè) :遺傳算法通過短定義距、低階以及高平均適應(yīng)度的模式 (基因塊 )，在遺傳操作下相互結(jié)合，最終接近全局最優(yōu)解。 模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長，從而 使遺傳算法找到全局最優(yōu)解的可能性存在 。而基因塊假設(shè)則指出了在遺傳算子的作用下，算法具有生成全局最優(yōu)解的能力，即能生成高階、長定義距、高平均適應(yīng)度的模式，最終生成全局最優(yōu)解。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 9 頁 上述結(jié)論并沒有得到證明，因而被稱為假設(shè)。目前已經(jīng)有大量的實踐證據(jù)支持這一假設(shè)，盡管大量的證據(jù)并不等于理論證明，但是至少可以肯定的是對很多經(jīng)常碰到的問題，遺傳算法都是適用的。 遺傳算法的收斂性分析 遺傳算法要實現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都能到達(dá)全局最優(yōu)解，其次算法必須由保優(yōu)操作來防止最優(yōu)解的遺失。與算法收斂性有 關(guān)的因素主要包括種群規(guī)模、選擇操作、交叉概率和變異概率。 通常，種群太小則不能提供足夠的采樣點(diǎn)，以致算法性能很差 。種群太大，盡管可以增加優(yōu)化信息，阻止早熟收斂的發(fā)生，但無疑會增加計算量，造成收斂時間太長，表現(xiàn)為收斂速度緩慢。 選擇操作使高適應(yīng)度個體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。如果在算法中采用最優(yōu)保存策略，即將父代群體中最佳個體保留下來，不參加交叉和變異操作，使之直接進(jìn)入下一代，最終可使遺傳算法以概率 1 收斂于全局最優(yōu)解。 交叉操 作用于個體對，產(chǎn)生新的個體，實質(zhì)上是在解空間中進(jìn)行有效搜索。交叉概率太大時，種群中個體更新很快，會造成高適應(yīng)度值的個體很快被破壞掉 。概率太小時，交叉操作很少進(jìn)行，從而會使搜索停滯不前，造成算法的不收斂。 變異操作是對種群模式的擾動，有利于增加種群的多樣性。但是，變異概率太小則很難產(chǎn)生新模式，變異概率太大則會使遺傳算法成為隨機(jī)搜索算法。 遺傳操作對收斂性的影響，可利用馬爾可夫鏈對遺傳算法進(jìn)行分析，從而論證了遺傳算法在收斂性方面的一些重要性質(zhì)，有力地支持了遺傳算法的理論基礎(chǔ)。由馬爾可 夫鏈推導(dǎo)出來的一些結(jié)論 :基本遺傳算法收斂于最優(yōu)解的概率為 1,使用保留最優(yōu)個體策略的遺傳算法收斂于最優(yōu)解的概率為 1。 隱含并行性定理 :遺傳算法所處理的模式總數(shù)與其群體規(guī)模 N 的立方成正比，即 : m=O(N3) （ ） 由該定理可知，雖然表面上每代處理的個體數(shù)目都是一定的，但是由于每個個體都 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 10 頁 隱含著多種不同的模式，所以每次參與遺傳算子操作的個體卻不僅僅是兩個。從總體上來說， 每代之間所處理的個體要遠(yuǎn)大于其表面的數(shù)目，這就是遺傳算法獨(dú)特的隱含并行性。由隱含并行性定理可知，雖然表面上每代僅對 N 個個體處理操作，而事實上處理了O(N3)個模式，且無需額外存儲。隱含并行性為遺傳算法的高效性提供了理論依據(jù)。 基本遺傳算法參數(shù)說明 對遺傳算法性能有影響的參數(shù)主要有 :種群數(shù)目 N、交換概率 Pc、變異概率 Pm、代溝 G、尺度窗口 W、和選擇策略 S 等。 (population size) 種群數(shù)目的多少直接影響到遺傳算法的優(yōu)化性能和效率，種群選擇太小時，不能提供足夠多的個體，致 使算法性能較差，易產(chǎn)生早熟收斂，甚至不能得到可行解。種群選擇過大時，雖然能避免早熟收斂，但是增加了計算量。 (crossover rate) 交換概率 Pc 用于控制交換操作的頻率。交換概率太大的時，易產(chǎn)生更新過快，從而破壞掉高適應(yīng)度個體的現(xiàn)象。交換概率太小的時候又容易產(chǎn)生搜索停滯不前的現(xiàn)象。 (mutation rate) 變異概率 Pm。增加種群多樣性具有重要意義。通常選取一個較低的變異概率。如果變異概率太大的時，遺傳算法易變成隨機(jī)搜索，如果變異概率太小，則不能產(chǎn)生新個體，不利于種群的 多樣性。 (generation gap) 代溝 G 用于控制每一代群體被替換的比例，每代有 N (1G)個父代個體選中進(jìn)入下一代種群中，該參數(shù)和交換、變異概率以及選擇策略有很大關(guān)系，它并不是一個初始參數(shù)，而是評價遺傳算法的一個參數(shù)。 (scaling window) 該參數(shù)用于作出由目標(biāo)值到適應(yīng)度函數(shù)值的調(diào)整。 (selection strategy) 一般來說有兩種選擇策略，一種為純選擇，種群中每個個體根據(jù)其適應(yīng)度值進(jìn)行比例選擇，即個體被選擇的概率與其適應(yīng)度值成正比。另一種為 保優(yōu)策略，首先進(jìn)行純選擇，把目前最優(yōu)個體直接加入下一代種群中，該策略是為了防止最優(yōu)解的丟失， 但在實際應(yīng)用中往往采取這兩種選擇策略結(jié)合的方法，并做適當(dāng)?shù)淖冃汀? 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 11 頁 遺傳算法的優(yōu)缺點(diǎn) 遺傳算法的優(yōu)點(diǎn) 遺傳算法在解決優(yōu)化問題過程中有如下優(yōu)點(diǎn) : ，而不是從單個解開始。這種機(jī)制意味著搜索過程可以跳出局部最優(yōu)點(diǎn)，能很好地將局部搜索和全局搜索協(xié)調(diào)起來，達(dá)到全局最優(yōu)點(diǎn)。 ，遺傳算法的初始種群本身就帶有大量與最優(yōu)解甚遠(yuǎn)的信息，通過選擇、交換、 變異操作，能迅速排除與最優(yōu)解相差極大的串，這是一個強(qiáng)烈的濾波過程，并且是一個并行濾波機(jī)制。 ，而不是對參數(shù)本身，因此遺傳算法具有靈活性高的特點(diǎn)。 ，而非傳統(tǒng)方法的采用目標(biāo)函數(shù)的導(dǎo)數(shù)信息或者求解問題域內(nèi)知識，因此具有普遍適應(yīng)性和可規(guī)?；奶攸c(diǎn)。 ，容易形成通用算法程序。由于遺傳算法使用適應(yīng)度值這一信息進(jìn)行搜索，并不需要問題導(dǎo)數(shù)等與問題直接相關(guān)的信息。 ，在存在噪聲的 情況下，對同一問題利用遺傳算法求解所得的結(jié)果是相似的。 遺傳算法的缺點(diǎn) ，而不能達(dá)到全局最優(yōu)。 ，用遺傳算法求最優(yōu)解比較困難，因為染色體種群很可能過 早地 斂，而對以后變化了的數(shù)據(jù)不再產(chǎn)生變化。對于這個問題，研究者提出了一些方法增加基因的多樣性，從而防止過早的收斂。其中一種是所謂觸發(fā)式超級突變，就是當(dāng)染色體群體的質(zhì)量下降 (彼此的區(qū)別減少 )時增加突變概率 。另一種叫隨機(jī)外來染色體，是偶爾加入一些全新的隨機(jī)生成的染色體個體，從而 增加染色體多樣性。 ，但交叉和變異的重要性存在爭議。一種觀點(diǎn)認(rèn)為交叉比變異更重要，因為變異僅僅是保證不丟失某些可能的解 。而另一種觀點(diǎn)則認(rèn)為交叉過程的作用只不過是在種群中推廣變異過程所造成的更新，對于初期的種群來說，交叉幾乎等效于