【摘 要】遺傳算法是模擬自然界生物進化機制的概率性搜索算法，可以處理傳統(tǒng)搜索方法難以解決的非線性問題。但是經(jīng)典遺傳算法存在局部收斂、收斂速度慢等缺點，這使得經(jīng)典遺傳算法有時很難找到全局最優(yōu)解。本文針對經(jīng)典遺傳算法中所存在的缺點，采用階段式的適應(yīng)度函數(shù)、基于競爭機制的交叉方式和仿粒子群變異操作，使遺傳算法的收斂速率、全局收斂概率都得到了較大的提高。

【關(guān)鍵詞】遺傳算法 適應(yīng)度 交叉操作 仿粒子群變異

【中圖分類號】TP18 【文獻標(biāo)識碼】A 【文章編號】1674－4810（2011）11－0012－04

一 遺傳算法

遺傳算法（Genetic Algorithm，簡稱GA）是Holland在研究自然遺傳現(xiàn)象與人工系統(tǒng)的自適應(yīng)行為時，模擬生物進化現(xiàn)象，并采用自然進化機制來表現(xiàn)復(fù)雜現(xiàn)象的一種全局群體搜索算法。遺傳算法的基本思想起源于Darwin進化論和Mendel的遺傳學(xué)說。作為一類智能計算工具和學(xué)習(xí)算法，由于其實現(xiàn)簡單、對目標(biāo)函數(shù)要求不高等特性，遺傳算法已廣泛應(yīng)用于如人工智能、組合優(yōu)化等研究領(lǐng)域。

1．遺傳算法的優(yōu)越性

遺傳算法（Genetic Algorithm）利用某種編碼技術(shù)作用在稱為染色體的二進制串上，模擬由這些串組成的個體的進化過程。通過有組織的、隨機的信息交換來重新結(jié)合那些適應(yīng)性好的串，在每一代中，利用上一代串結(jié)構(gòu)中適應(yīng)性好的位和段來形成一個新的串的群體，同時在串結(jié)構(gòu)中嘗試用新的位和段來代替原來的部分以形成新的個體，以增加種群的多樣性。遺傳算法的最大優(yōu)點是能夠通過群體間的相互作用，保存已經(jīng)搜索到的信息，這是基于單次搜索過程的優(yōu)化方法所無法比擬的。但是，遺傳算法也存在著計算速度較慢，并且容易陷入局部最優(yōu)解的問題中。

遺傳算法的優(yōu)越性歸功于它與傳統(tǒng)搜索方法不同的特定結(jié)構(gòu)。

第一，遺傳算法的操作對象是編碼，對問題的限制極少，對函數(shù)的一些約束條件如連續(xù)性、可導(dǎo)性等不做要求，減少了要解決問題的復(fù)雜性。

第二，遺傳算法同時搜索解空間內(nèi)的許多點，因而可以有效地防止搜索過程中收斂到局部最優(yōu)解，并獲得全局最優(yōu)解，與其他單點搜索的方法相比，在計算時間上也有較大的優(yōu)勢。

第三，遺傳算法使用遺傳操作時是按概率在解空間進行搜索，因而既不同于隨機搜索，也不同于枚舉法那樣盲目地舉例，而是一種有目標(biāo)、有方向的啟發(fā)式搜索。

2．遺傳算法的基本步驟

遺傳算法的實現(xiàn)中包括復(fù)制、交叉、變異三個算子，需要確定關(guān)鍵的幾個參數(shù)與標(biāo)準(zhǔn)包括：種群規(guī)模、基因編碼、適值函數(shù)、選擇概率、遺傳算子以及停機準(zhǔn)則。下面分別對其進行說明：

第一，表示法與適應(yīng)度計算。標(biāo)準(zhǔn)遺傳算法（二進制編碼）作用于確定長度的二進制位串上，即I＝{0，1}l。假設(shè)需要

解決如下函數(shù)優(yōu)化問題 ，一般

是將位串分為n段，每段長度為lx，即l＝n#8226;lx，每段表示分量

xi∈［ui，vi］的二進制代碼。位段譯碼函數(shù) 的常見形式為：

…（1）

其中 … 記為個體 … 的第

i段。把位段譯碼函數(shù) 組合成一個個體的譯碼函數(shù) … ，則適應(yīng)度函數(shù)可設(shè)置為 ，其中δ為比例變換函數(shù)，作用之一是確保適應(yīng)值為正值，并且最好使個體的適應(yīng)度值最大。常見的比例變換有線性比例、冪比例和指數(shù)比例等。

第二，交叉。交叉操作是將已有個體組合出新個體，使兩個個體的有效信息得以遺傳到下一代，并可能得到新的個體信息。在遺傳算法中，交叉操作是主要的遺傳操作，它把兩個不同個體上的有用段組合在一起，GA的性能在很大的程度上依賴所使用的交叉算子。交叉操作算子r'∶I μ→I也是作用在位串上，以概率pc對兩個個體進行交叉，pc的作用范圍一般為［0.6，1.0］。兩個父輩個體s＝（s1，…，sl），v＝（v1，…，vl）被隨機地從群體中選擇而進行交叉，產(chǎn)生了兩個子代個體：

s'＝（s1，…，sh－1，sh，vh－1，…，vl，） （2）

v'＝（v1，…，vh－1，vh，sh－1，…，sl，） （3）

其中交叉點h為1到l之間的一個隨機整數(shù)。這種交叉即為一點交叉，通過選擇更多的交叉點并交替地變換交叉點之間的位段，就可以把一點交叉擴展到m點交叉算子。另外還有一些其他形式的交叉算子，如一致交叉算子等。不過目前還沒有明確的理論或可靠的實驗證據(jù)來決定哪一種交叉算子是最適合的。

第三，變異。變異操作的目的是通過隨機改變?nèi)旧w的某些基因來引入新個體，增加種群多樣性，并在一定程序上進行局部搜索。相對于交叉操作，變異操作的設(shè)計和實現(xiàn)更為簡單和靈活。在標(biāo)準(zhǔn)遺傳算法中，變異一般被看作為輔助算子，它作用在位串上，以較小的概率pm隨機地改變串上的每一位（即相應(yīng)位上的0變?yōu)?，或者1變?yōu)?）。變異概率pm的值一般為0.001到0.01之間，它不依賴目標(biāo)變量的維數(shù)

和位串的總長。個體（s1，…，sl）經(jīng)變異算子 作用后

變?yōu)椋?… ），其中：

…（4）

這里θi是0與1之間的一致隨機數(shù)，對串上的每一位都要重新采樣。常用的變異操作包括：（1）互換：隨機變換若干不同位置上的不同基因。（2）逆序：將某兩隨機位置間的基因串逆序。（3）插入：即將某一位置上的基因（或某一段位置上的基因串）插入到另一位置之前或之后，若兩位置相鄰，則該操作也稱為漂移。

第四，選擇。標(biāo)準(zhǔn)遺傳算法采用的是一種依據(jù)概率復(fù)制的選擇算子s∶I μ→I μ，個體ai的復(fù)制概率由它的相對適應(yīng)度給出：

…（5）

按照這個概率分布選取μ個個體產(chǎn)生下一代父輩群體。顯然該選擇算子不適于出現(xiàn)負適應(yīng)度值和最小化任務(wù)的情況，此時需采用適應(yīng)度值比例轉(zhuǎn)換。綜上所述，標(biāo)準(zhǔn)遺傳算法的主要步驟可描述如下：

二 遺傳算法的改進

1．一般自適應(yīng)遺傳算法

經(jīng)典遺傳算法（CGA）采用的都是固定參數(shù)，由于遺傳算法從本質(zhì)上說是一種動態(tài)自適應(yīng)的進化過程，因此固定的參數(shù)設(shè)置則是對遺傳算法性能的一種局限和束縛。經(jīng)典遺傳算法在進化過程中，各遺傳算子的參數(shù)保持不變。由于在進化后期，種群內(nèi)個體的多樣性大幅度減小，適應(yīng)值接近，因此選擇操作的選擇壓力可能不夠，致使算法接近隨機搜索狀態(tài)。

針對CGA存在的這些問題，Srinvivas等人提出自適應(yīng)遺傳算法（Adaptive GA，AGA），即交叉概率Pc和變異概率Pm能夠隨適應(yīng)度自動改變，遺傳算法的參數(shù)中交叉概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關(guān)鍵所在，直接影響算法的收斂性，Pc越大，新個體產(chǎn)生的速度就越快。然而，Pc過大時遺傳模式被破壞的可能性也越大，使得具有高適應(yīng)度的個體結(jié)構(gòu)很快就會被破壞；但是如果Pc過小，會使搜索過程緩慢，以至停滯不前。對于變異概率Pm，如果Pm過小，就不易產(chǎn)生新的個體結(jié)構(gòu)；如果Pm取值過大，那么遺傳算法就變成了純粹的隨機搜索算法。

當(dāng)種群中每個個體的適應(yīng)度趨于一致或趨于局部最優(yōu)時，使二者增加，而當(dāng)種群適應(yīng)度比較分散時，使二者減小，同時對適應(yīng)度高于群體平均適應(yīng)度的個體，采用較低的交叉和變異概率，使性能優(yōu)良的個體進入下一代，而低于平均適應(yīng)度的個體，采用較高的交叉和變異概率，使性能較差的個體被淘汰。因此，自適應(yīng)的Pc和Pm能夠提供相對某個解的最佳Pc和Pm。自適應(yīng)遺傳算法在保持群體多樣性的同時，保證遺傳算法的收斂性。自適應(yīng)遺傳算法由于改進了各遺傳算子的參數(shù)，使算法能夠適應(yīng)于種群進化各個階段的特征，使算法的優(yōu)化效率和解的質(zhì)量得到提高。

2．改進的遺傳算法

經(jīng)典遺傳算法的局部搜索能力較差，一般對經(jīng)典遺傳算法進行適當(dāng)?shù)母倪M或?qū)⑦z傳算法與傳統(tǒng)的基于問題的啟發(fā)式搜索技術(shù)相結(jié)合形成混合遺傳算法來解決這個問題。設(shè)計混合遺傳算法有三條指導(dǎo)性原則：（1）采用原有算法中的編碼技術(shù)；（2）吸收原有算法的優(yōu)點；（3）改造遺傳算子。

根據(jù)這三個指導(dǎo)原則本文在保留一般自適應(yīng)算法的編碼方式、變異和交叉概率設(shè)定的基礎(chǔ)上，對一般的自適應(yīng)算法的適應(yīng)度函數(shù)、交叉方式、變異方式做出改進，提出了改進的混合遺傳算法（Hybrid GA， HGA）。最后，通過實驗說明了改進算法的優(yōu)越性。（1）適應(yīng)度函數(shù)的改進。適應(yīng)度函數(shù)是評價個體適應(yīng)環(huán)境的能力，是選擇操作的依據(jù)，它的好壞能直接影響遺傳算法的性能。適應(yīng)度函數(shù)是由目標(biāo)函數(shù)轉(zhuǎn)換而成的。（2）交叉方式的改進。GA交叉算子是模仿自然界有性繁殖的基因重組過程，在該過程中群體的個體品質(zhì)得以提高。直觀來講，選擇算子將原有的優(yōu)良基因遺傳給下一代個體，而交叉算子則可以生成包含更多優(yōu)良基因的新個體。交叉方式的設(shè)計，一般與所求問題的特征有關(guān)。通常需要考慮如下因素：第一，必須保證優(yōu)良基因能夠在下一代中有一定的遺傳和繼承的機會；第二，必須保證通過交叉操作存在一定的生成優(yōu)良基因的機會；第三，交叉方式的設(shè)計與問題編碼緊密相關(guān)，必須結(jié)合編碼的結(jié)構(gòu)來設(shè)計高效的交叉算子。（3）變異方式的改進。變異即對群體中個體的某些基因作出變動。變異的目的有兩個：一個是使遺傳算法具有局部的隨機搜索能力；另一個是保持群體的多樣性。變異在GA中的作用是第二位，與交叉算子相比，當(dāng)變異概率較小時，在進化初期模式存活概率比較高；在進化穩(wěn)定期，與交叉算子下的模式存活概率基本相同；當(dāng)變異概率比較大時，變異算子作用下模式的存活概率比交叉算子下要小得多。

3．算法步驟

Step1采用實數(shù)編碼產(chǎn)生初始種群，在函數(shù)定義域內(nèi)按照均勻分布隨機產(chǎn)生μ個個體{xi}（i＝1，2，…，μ），設(shè)定最大進化代數(shù)設(shè)為T。

Step2計算每個個體的函數(shù)值，之后根據(jù)計算種群函數(shù)的平均值，最后按照本文設(shè)定的適應(yīng)度函數(shù)計算當(dāng)前種群中每個個體的適應(yīng)度。

Step3最優(yōu)保存策略，結(jié)合文獻本文將最優(yōu)保存策略算法做如下修改：第一步計算每個個體的函數(shù)值，然后排序，找出最優(yōu)解，最差解；第二步若上一代最優(yōu)解的函數(shù)值比當(dāng)前最優(yōu)解的函數(shù)值大，則用上一代的最優(yōu)解替換當(dāng)前最優(yōu)解；若上一代的最優(yōu)解函數(shù)值小，則用上一代的最優(yōu)解替換當(dāng)前中的最差解。

Step4根據(jù)每個個體的適應(yīng)度，采用比例選擇法。通過轉(zhuǎn)換，使得在進化前期原本函數(shù)值小的個體將有更大的概率被選擇，保持了種群的多樣性。

Step5計算交叉概率，然后在種群中按照交叉概率隨機選擇父代個體，然后應(yīng)用本文改進的交叉操作進行交叉，最后通過競爭選取兩個最好的個體作為子代個體。

Step6計算變異概率，選定變異個體，將選定的個體依照本文采用的擬粒子群變異方法進行變異操作。

Step7滿足迭代次數(shù)即停止，否則代數(shù)加1，轉(zhuǎn)入Step2。

三 實驗分析

1．實驗參數(shù)設(shè)定

為了驗證改進遺傳算法的效果，選用以下三個典型函數(shù)進行測試：

（1）問題P1

g3是Schaffer函數(shù)，由函數(shù)圖像可以看出當(dāng)（x1，x2）＝（0，0）時有全局最小值0。為方便編程將問題P3轉(zhuǎn)化為求全局最大值，得到問題P3'：

分別用經(jīng)典遺傳算法（CGA）、一般自適應(yīng)遺傳算法（AGA）和改進遺傳算法（HGA）對這些函數(shù)進行優(yōu)化。為了方便編程，函數(shù)均設(shè)定為求其全局最大值，然后將三種算法運行的參數(shù)設(shè)置如下：

問題P1'算法運行的參數(shù)如表1所示：

采用上述參數(shù)用三種算法對每個函數(shù)各自獨立運行 50 次，當(dāng)算法達到最大迭代次數(shù)，或者所得結(jié)果與函數(shù)全局最優(yōu)解的誤差|e|≤10-2時算法終止。表4列出了三種算法的平均收斂代數(shù)，最小收斂代數(shù)和全局收斂概率。

三種算法運行收斂的代數(shù)，見圖1、圖2、圖3。

2．結(jié)果分析

通過表4可以看出，本文的改進算法HGA無論是收斂代數(shù)還是收斂概率都全面優(yōu)于經(jīng)典遺傳算法。與一般自適應(yīng)算法相比，達到最優(yōu)值的收斂代數(shù)減少，得到了令人滿意的效果。

四 小結(jié)

在本節(jié)中詳細介紹了本文改進的遺傳算法（HGA）流程，通過對幾組數(shù)據(jù)的測試結(jié)果分析得出本算法的優(yōu)越性。雖然對個別函數(shù)在全局收斂概率方面略顯不足，但是對于大部分函數(shù)本文改進的算法在減少收斂代數(shù)和提高全局收斂概率方面都是優(yōu)于經(jīng)典遺傳算法（CGA）與一般自適應(yīng)遺傳算法（AGA）的。

參考文獻

［1］馮紅娟.基于遺傳算法的車間作業(yè)調(diào)度問題研究［D］.長春理工大學(xué)，2008.3

［2］趙蕾.遺傳算法在通信網(wǎng)優(yōu)化中的實現(xiàn)［D］.山東大學(xué)，2005.3

［3］Goldberg D E.Genetic Algorithms in Search. Optimization and Machine Learning.Reading， MA: Addison－Wesley， 1989

［4］譚丹丹等.一種基于配對的改進遺傳算法［J］.計算機應(yīng)用，2007（27）：170～171

［5］鄺航宇、金晶、蘇勇.自適應(yīng)遺傳算法交叉變異算子的改進［J］.計算機工程與應(yīng)用，2006（12）：93～99

［6］向佐勇、劉正才.基于完全自適應(yīng)策略的遺傳算法［J］.中南林業(yè)科技大學(xué)學(xué)報，2007（5）：136～139

［7］申元霞、曾傳華、張翠芳.一種自適應(yīng)緊湊遺傳算法及其仿真研究［J］.系統(tǒng)仿真學(xué)報，2008（5）：1167～1169

［8］劉立平、牛熠.遺傳算法綜述［J］.東莞理工學(xué)院學(xué)報，2005（3）：48～52

［9］杜明、王江晴.遺傳算法在車輛路徑問題中的應(yīng)用與實踐［J］.控制理論與應(yīng)用，2007（6）：10～12

〔責(zé)任編輯：李錦雯〕

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文