【文章內(nèi)容簡(jiǎn)介】 選擇、繁衍和替換過程，直到整個(gè)過程滿足一定的結(jié)束條件為止。通常情況下，進(jìn)化過程的最后一改善或解決實(shí)際問題 實(shí)際問題 參數(shù) 集 編碼成位串 計(jì)算適應(yīng)度值 統(tǒng)計(jì)結(jié)果 遺傳操作 種群 2 種群 1 三種遺傳算子： 選擇算子 交叉算子 變異算子 經(jīng)過優(yōu)化的一個(gè)或多個(gè)參數(shù)集（解碼后） 隨機(jī)算子 種群 1 種 群 2 代群體中的適應(yīng) 度值最高的個(gè)體，就是利用遺傳算法求解的優(yōu)化問題的最終結(jié)果。 遺傳算法的實(shí)現(xiàn)步驟 基本遺傳算法（ Simple Geic Algorithm）可定義為一個(gè) 8 元組： ),,( 0 TMPECS GA ???? （ ） 式中， C—— 個(gè)體編碼方法， SGA 采用二進(jìn)制編碼方法； E—— 個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)； P0—— 初始群體； M—— 群體的大小，通常取 20～ 100； ? —— 選擇算子， SGA 使用比例選擇算子； ? —— 交叉算子， SGA 采用單點(diǎn)交叉算子； ? —— 變異算子， SGA 采用基本位變異算子； ? —— 算法終止條件，一般終止進(jìn)化代數(shù)為 100~500。 1. 參數(shù)編碼與解碼 遺傳算法主要是通過遺傳算子對(duì)群體中具有某種結(jié)構(gòu)形式的個(gè)體施加重組處理，從而不斷地搜索出群體中個(gè)體間的結(jié)構(gòu)相似性，逐代優(yōu)化參數(shù)以趨近最優(yōu)解。遺傳算法不能直接處理問題空間的參數(shù)，必須在目標(biāo)問題的實(shí)際描述與遺傳算法的染色體位串結(jié)構(gòu)之間建立聯(lián)系。由問題空間向遺傳編 碼空間的映射稱作編碼（ Encoding），而由編碼空間向問題空間的映射稱作解碼（ Decoding）。 編碼將問題域知識(shí)轉(zhuǎn)化為遺傳算法空間的碼串描述。理論上，編碼應(yīng)該適合要解決的問題，并非是簡(jiǎn)單的描述問題。因而在具體的應(yīng)用中，編碼設(shè)計(jì)應(yīng)遵循如下原則： （ 1） 完全性 原則上，分布在所有問題域的解都有可能被構(gòu)造出來。 （ 2） 分閉性 每個(gè)基因碼，對(duì)應(yīng)一個(gè)可接受的個(gè)體，封閉性保證系統(tǒng)不會(huì)產(chǎn)生無效的個(gè)體。 （ 3） 緊致性 若兩種基因碼 g1和 g2都被解碼成相同的個(gè)體，若 g1比 g2占的空間少，就認(rèn)為 g1比 g2緊致。 （ 4） 可擴(kuò)展性 對(duì)于具體的問題， 編碼的大小確定了解碼的時(shí)間，兩 者存在一定的函數(shù)關(guān)系，若增加一種表現(xiàn)型，作為基因型的編碼大小也做 出相應(yīng)的增加。 （ 5） 多重性 多個(gè)基因型解碼成一個(gè)表現(xiàn)型，即從基因型到相應(yīng)的表現(xiàn)型空間是多對(duì)一的關(guān)系，這是基因的多重性。若相同的基因型被解碼成不同的表現(xiàn)型，這是表現(xiàn)型的多重性。 （ 6） 個(gè)體可塑性 決定表現(xiàn)型與相應(yīng)給定基因型是受環(huán)境影響的。 （ 7） 模塊性 若表現(xiàn)型的構(gòu)成中有多個(gè)重復(fù)的結(jié)構(gòu)，在基因型編碼中這種重復(fù)是應(yīng)該避免的。 （ 8） 冗余性 冗余性能夠提高可靠性和魯棒性。 （ 9） 復(fù)雜性 包括基因型的結(jié)構(gòu)復(fù)雜性，解碼復(fù)雜性，計(jì)算時(shí)空復(fù)雜性（基因解碼、 適應(yīng)值、再生等） [30]。 編碼方式常用的有二進(jìn)制編碼和浮點(diǎn)數(shù)編碼。 （ 1）二進(jìn)制編碼 二進(jìn)制編碼是遺傳算法中常用的一種編碼方法，即將原問題的解映射為 0， 1 組成的位串，然后在位串空間上進(jìn)行遺傳操作。得到的結(jié)果再通過解碼過程還原為原問題解的解空間，接著進(jìn)行適應(yīng)度值的計(jì)算。 設(shè)種群中的個(gè)體數(shù)目為 n， itx 表示第 t 代的 i 個(gè)個(gè)體， )...,2,1{ ni? 。每個(gè)個(gè)體用 l 位二進(jìn)制表示。這樣每個(gè)個(gè)體 }1,0{,}{ ?? IBIBx mlit ，這樣每個(gè)個(gè)體基 因位數(shù)目 L=ml。個(gè)體 itx 可以表示為 ml 維的行向量，即 ].. ... ... ... .[ )()1)1((2)1()()1( mlitlmitltltlititit xxxxxxx ???? 。第 t 代種群 tX 可以表示為一個(gè) mln? 的矩陣 ]...[ 21 ntttt xxxX ? 。個(gè)體 itx 的第 k 個(gè)長度為 l 的二進(jìn)制碼串轉(zhuǎn)化為實(shí)數(shù)的解碼函數(shù) ? 為 )2(12),( 11)( ??? ??????? jtjjklitl kkkit xuvukx （ ） 式（ ）中 kv 和 ku 分別為第 k 個(gè)實(shí)數(shù)范圍的上限和下限。 很多數(shù)值計(jì)算與非數(shù)值優(yōu)化問題都可以用二進(jìn)制編碼來實(shí)現(xiàn)，該方法具有如下優(yōu)點(diǎn)：編碼方式簡(jiǎn)單且操作方便；符合最小字符集編碼原則，便于用模式定理進(jìn)行分析。但當(dāng)二進(jìn)制編碼在求解連續(xù)優(yōu)化問題存在以下缺點(diǎn)：相鄰整數(shù)的二進(jìn)制可能有較大的 Hamming 距離，例如 15 和 16 的二進(jìn)制表示為 0 1 1 1 1 和 1 0 0 0 0。因此算法要從 15 改進(jìn)到 16 則必須改變所有的位 。這種缺陷將降低遺傳算子的搜索效率 [17,31]。 （ 2）浮點(diǎn)數(shù)編碼 為了克服二進(jìn)制編碼對(duì)于一些多維、高精度要求的連續(xù)函數(shù)優(yōu)化問題弊端可以采用十進(jìn)制或浮點(diǎn)數(shù)進(jìn)行編碼。所謂浮點(diǎn)數(shù)編碼方法，是指?jìng)€(gè)體的每個(gè)基因值用某一范圍內(nèi)的浮點(diǎn)數(shù)來表示，個(gè)體編碼的長度等于其決策變量的個(gè)體。浮點(diǎn)數(shù)編碼必須保證基因值在給定的區(qū)間限制范圍內(nèi)。同時(shí)，遺傳操作中所使用的交叉、變異等也引入了專門的遺傳算子，保證其運(yùn)算結(jié)果所產(chǎn)生的新個(gè)體的基因值也在這個(gè)區(qū)間限制范圍內(nèi) [32]。 浮點(diǎn)數(shù)編碼適用于搜索空間較大、精度要求較高的遺傳方案中，其運(yùn)算簡(jiǎn) 單，提高了遺傳算法的運(yùn)算效率，有利于遺傳算法與經(jīng)典優(yōu)化方法的混合應(yīng)用，便于處理具有約束條件的復(fù)雜決策變量。 2. 適應(yīng)度函數(shù)值計(jì)算 在生物的遺傳和進(jìn)化過程中，對(duì)環(huán)境適應(yīng)度較高的物種將有更多的繁殖機(jī)會(huì)，遺傳算法中也使用類似的概念來度量群體中各個(gè)個(gè)體在優(yōu)化計(jì)算中有可能、或有助于找到最佳解的尋優(yōu)過程。適應(yīng)度值較高的個(gè)體遺傳到下一代的概率就較大，而適應(yīng)度值較低的個(gè)體遺傳到下一代的概率就相對(duì)小些。度量個(gè)體適應(yīng)度值的函數(shù)稱為適應(yīng)度函數(shù)（ Fitness Function）。適應(yīng)度函數(shù)的選取至關(guān)重要，它直接影響遺傳算法的收 斂速度以及能否找到最優(yōu)解。設(shè)計(jì)適應(yīng)度函數(shù)要保證其：①單值、連續(xù)、非負(fù)、最大化；②滿足合理性和一致性③計(jì)算量小、通用性強(qiáng)。 在遺傳算法的實(shí)際應(yīng)用中，適應(yīng)度函數(shù)的確定方法通常有以下三種： （ 1） 直接以待求解的目標(biāo)函數(shù)轉(zhuǎn)化為適應(yīng)度函數(shù)，即 若目標(biāo)函數(shù)為最大化問題則取 )())(( xfxfF it ? （ ） 若目標(biāo)函數(shù)為最小問題則取 )())(( xfxfF i t ?? （ ） 這種適應(yīng)度函數(shù)簡(jiǎn)單直觀，但是存在兩個(gè)問題，其一是可能不滿足常用的輪盤賭選擇中概率非負(fù)的要求；其 二是某些待求解的函數(shù)在函數(shù)值分布上相差很大，由此得到的平均適應(yīng)度可能不利于體現(xiàn)種群的平均性能，影響整個(gè)遺傳算法的性能。 （ 2）界限構(gòu)造法 若目標(biāo)函數(shù)為最大化問題則 ??? ??? 其他,0 )(,)())(( m inm in cxfcxfxfF i t （ ） 式（ ）中， minc 為 )(xf 的最小估計(jì)。 若目標(biāo)函數(shù)為最小問題 ??? ??? 其他,0 )(),())(( m axm ax cxfxfcxfF i t （ ） 這種方法是對(duì)第一種方法的改進(jìn)，在具體的應(yīng)用中優(yōu)勢(shì)會(huì)存在預(yù)先估計(jì)困難、不精 確的問題。 （ 3） 若目標(biāo)函數(shù)為最大問題取 0)(,0,)(1 1))(( ?????? xfccxfcxfF i t （ ） 若目標(biāo)函數(shù)為最小問題取 0)(,0,)(1 1))(( ?????? xfccxfcxfF i t （ ） 該方法與第二種方法類似， c 為目標(biāo)函數(shù)界限的保守估計(jì)值 [17,33,34]。 3 遺傳操作 遺傳算法的操作算子包括選擇、交叉（又稱重組）和變異三種基本形式。三種遺傳算子是遺傳算法具備強(qiáng)大搜索能力的核心，是模擬自然選擇以及遺傳過程中的繁殖惡化突變現(xiàn)象的主要載體。遺傳算法利用交叉和變異算子產(chǎn)生新的群體進(jìn)而實(shí)現(xiàn)種群進(jìn)化，遺 傳算子的設(shè)計(jì)是遺傳策略的主要組成部分，也是調(diào)整和控制進(jìn)化過程的基本工具。 （ 1）選擇算子 選擇是從群體中挑選優(yōu)良的個(gè)體同時(shí)淘汰劣質(zhì)個(gè)體的遺傳操作過程。它建立在適應(yīng)度評(píng)估的基礎(chǔ)上，個(gè)體適應(yīng)度越大，其被選中的可能性就越大，它的子代保留到匹配池（ mating pool）中的個(gè)數(shù)就越多。常用的遺傳方法有 [17,35]： ① 輪盤賭方法（ roulette wheel model） 輪盤賭方法是遺傳算法中最基本也最常用的選擇方法。設(shè)群體為 P，個(gè)體的適應(yīng)度為Fitness，則個(gè)體 i 被選擇的概率為 ?? ?Pj ji FitnessFitnessP1 （ ） 其累計(jì)概率為 ???ij ii Pq 1 （ ） 式（ ）中， ??Pj jFithess1表示該種群在這一代中的總適應(yīng)度值。選擇按旋轉(zhuǎn)輪盤（輪盤上按 Pi 的大小劃分為不等的扇區(qū)），顯然適應(yīng)度大的個(gè)體其選擇概率越大，在輪盤中所占的位置越大，被選中的概率也就越大。 ② 排序選擇法（ rankbased model） 排序選擇法以標(biāo)準(zhǔn)化幾何分布規(guī)律隨機(jī)對(duì)種群中染色體進(jìn)行選擇，以最佳染色體的選擇概率 Ps作為基本參數(shù)，按染色體的 排列序號(hào)確定其選擇概率。排序法的最大優(yōu)點(diǎn)在于排序法忽略實(shí)際染色體的適應(yīng)度值，用染色體的順序來換算出相應(yīng)的生存概率，換算原則為大適應(yīng)度值對(duì)高選擇概率，小適應(yīng)度值對(duì)低選擇概率。這樣既能保證大適應(yīng)度值染色體獲得高選擇概率，同時(shí)又阻止某些超級(jí)染色體過快地控制遺傳過程。 排序選擇法首先需根據(jù)最佳染色體選擇概率計(jì)算標(biāo)準(zhǔn)分布值，表達(dá)式如下 Pss PPt )1(1 ??? （ ） 接著根據(jù)上式計(jì)算染色體選擇概率： PkPtP kNsk ,. ..2,1,)1( 1)( ??? ? （ ） 式（ ）中 )(kN 為第 k 個(gè)染色體的適應(yīng)值在種群中由大到小排列的序號(hào)。 Ps為最佳染色體選擇概率， P 為樣本數(shù)。 最后計(jì)算染色體的累計(jì)選擇概率值 qk Pkpq kj jk ,...2,1,1 ??? ? （ ） ③ 最佳個(gè)體保存法 最佳個(gè)體保存法把群體中適應(yīng)度值最高的個(gè)體不進(jìn)行配對(duì)交叉而直接復(fù)制到下一代。該方法的好處在于保證了進(jìn)化過程中的某一代的最優(yōu)解不被交叉和變異操作所破壞。然而該方法使一些局部?jī)?yōu)化個(gè)體的遺傳基因會(huì)急速增加而達(dá)到局部?jī)?yōu)化解，其全局搜索能力差，不利于多峰值的搜索問題，因而該 方法一般與其他選擇方法相結(jié)合而使用。 （ 2）交叉算子 在遺傳操作中，交叉操作因其全局搜索能力而成為主要算子。交叉操作的作用在于它不僅使原來種群中的優(yōu)良個(gè)體的特性能夠在一定程度上保持，而且其探索新的空間的能力使得種群中的個(gè)體具有多樣性。它是 GA 獲取新的優(yōu)良個(gè)體的最重要手段。交叉是指把兩個(gè)父串個(gè)體的部分結(jié)構(gòu)加以替換重組而成新個(gè)體的操作，交叉算子分為兩類，一類為二進(jìn)制交叉，一類為浮點(diǎn)數(shù)交叉。 ① 二進(jìn)制交叉運(yùn)算 該操作按一定的概率 Pc在匹配池中隨機(jī)地選取兩個(gè)個(gè)體進(jìn)行，交叉的位置也是隨機(jī)確定的。其二進(jìn)制編碼操作又可 分為單點(diǎn)交叉、兩點(diǎn)交叉和多點(diǎn)交叉。 單點(diǎn)交叉：是在個(gè)體中隨機(jī)地選定一個(gè)交叉點(diǎn)，兩個(gè)個(gè)體在該點(diǎn)前后進(jìn)行部分互換以產(chǎn)生新的個(gè)體，如： 父輩個(gè)體 1 AAAAAA|AAAAAA → BBBBBB|AAAAAA 父輩個(gè)體 2 BBBBBB|BBBBBB → AAAAAA|BBBBBB 兩點(diǎn)交叉：與單點(diǎn)交叉類似，只是隨機(jī)設(shè)置兩個(gè)交叉點(diǎn)進(jìn)行部分乎換，以產(chǎn)生新的個(gè)體，如： 父輩個(gè)體 1 AAAA|AAAA|AAAA → AAAA|BBBB|AAAA 父輩個(gè)體 2 BBBB|BBBB|BBBB → BBBB|AAAA|BBBB 多點(diǎn)交叉：該交叉操作即前述兩種交叉操作的推廣，多點(diǎn)交叉有時(shí)又被叫作廣義交叉。當(dāng)用 c 表示交叉參數(shù)時(shí)，則 c=1 或 c=2 時(shí)即為單點(diǎn)交叉和兩點(diǎn)交叉。 ② 浮點(diǎn)數(shù)編碼的交叉運(yùn)算 常用的浮點(diǎn)數(shù)編碼的交叉運(yùn)算為線性交叉又稱算術(shù)交叉。即兩個(gè)父代以線性組合的方式產(chǎn)生子代。對(duì)于凸搜索空間，算術(shù)交叉保證其子代的閉合性。也就是問題空間內(nèi)的任何兩個(gè)染色體的線性組合仍屬于問題空間。該方法在種群中均勻隨機(jī)選取兩條染色體)...2,1(21 nlvv ll ?、 作為交叉雙親；然后在 [0,1]區(qū)間內(nèi)產(chǎn)生隨機(jī)數(shù) lr ；對(duì)染色體按交叉次數(shù)進(jìn)行如式（ ）操作 llllllllll rvrvv rvrvv212211 )1(39。 )1(39。 ??? ??? （ ） 式中 39。39。 21 ll vv 、 為產(chǎn)生的新染色體。 （ 3）變異運(yùn)算 變異運(yùn)算使得遺傳算法具有局部隨機(jī)搜索能力，配合交叉操作以維持種群的多樣性，防止出現(xiàn)過早收斂。變異算子也具有兩類，一類為基本的二進(jìn)制變異操作，另一類為針對(duì)浮點(diǎn)數(shù)而言的浮點(diǎn)數(shù)變異。 ① 二進(jìn)制變異運(yùn)算 變異是以很小的概率 Pm 隨機(jī)地改變個(gè)體串中染色體的某些基因值。在二進(jìn)制編碼方式中，變異操作基本過程是變 異算子隨機(jī)地將某個(gè)基因值取反，即“ 0”變?yōu)椤?1”，“ 1”變?yōu)椤?0”。如： [01000101000101011010] → [01010101000101001010] ② 浮點(diǎn)數(shù)變異運(yùn)算 對(duì)于浮點(diǎn)數(shù)則常用的變異手段有均勻變異、邊界變異和非均勻變異等。浮點(diǎn)數(shù)變異目的在于擴(kuò)大染色體基因的取值范圍。 均勻變異：設(shè)種群中有染色體 ),...,( 21 ml v