遺傳算法（GeneticAlgorithm）●遺傳算法（GeneticAlgorithm）是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計算模型，是一種通過模擬自然進(jìn)化過程搜尋最優(yōu)解的方法?！褡畛跤擅绹鳰ichigan高校J.Holland教授于1975年首先提出來，并出版了頗有影響的專著《AdaptationinNaturalandArtificialSystems》，GA這個名稱才漸漸為人所知，J.Holland教授所提出的GA通常為簡潔遺傳算法（SGA）。1.1基本概念1.個體與種群●個體就是模擬生物個體而對問題中的對象（一般就是問題的解）的一種稱呼，一個個體也就是搜尋空間中的一個點?！穹N群(population)就是模擬生物種群而由若干個體組成的群體,它一般是整個搜尋空間的一個很小的子集。2.適應(yīng)度與適應(yīng)度函數(shù)●適應(yīng)度(fitness)就是借鑒生物個體對環(huán)境的適應(yīng)程度,而對問題中的個體對象所設(shè)計的表征其優(yōu)劣的一種測度?！襁m應(yīng)度函數(shù)(fitnessfunction)就是問題中的全體個體與其適應(yīng)度之間的一個對應(yīng)關(guān)系。它一般是一個實值函數(shù)。該函數(shù)就是遺傳算法中指導(dǎo)搜尋的評價函數(shù)。

3.染色體與基因

染色體（chromosome）就是問題中個體的某種字符串形式的編碼表示。字符串中的字符也就稱為基因（gene）。例如：個體染色體

9----

1001

（2，5，6）----0101011104.遺傳操作亦稱遺傳算子(geneticoperator)，就是關(guān)于染色體的運算。遺傳算法中有三種遺傳操作:

●

選擇-復(fù)制(selection-reproduction)

●

交叉(crossover，亦稱交換、交配或雜交)

●

變異(mutation，亦稱突變)

選擇-復(fù)制通常做法是：對于一個規(guī)模為N的種群S,按每個染色體xi∈S的選擇概率P(xi)所確定的選中機(jī)會,分N次從S中隨機(jī)選定N個染色體,并進(jìn)行復(fù)制。

這里的選擇概率P(xi)的計算公式為

交叉就是互換兩個染色體某些位上的基因。

s1′=01000101,s2′=10011011可以看做是原染色體s1和s2的子代染色體。

例如,設(shè)染色體s1=01001011,s2=10010101,

交換其后4位基因,即變異就是變更染色體某個(些)位上的基因。例如,設(shè)染色體s=11001101將其第三位上的0變?yōu)?,即s=11001101→11101101=s′。s′也可以看做是原染色體s的子代染色體。1.2基本遺傳算法

遺傳算法基本流程框圖生成初始種群計算適應(yīng)度選擇-復(fù)制交叉變異生成新一代種群終止?結(jié)束算法中的一些限制參數(shù)：■種群規(guī)?！鲎畲髶Q代數(shù)■交叉率(crossoverrate)就是參與交叉運算的染色體個數(shù)占全體染色體總數(shù)的比例，記為Pc,取值范圍一般為0.4～0.99?！鲎儺惵?mutationrate)是指發(fā)生變異的基因位數(shù)所占全體染色體的基因總位數(shù)的比例，記為Pm，取值范圍一般為0.0001～0.1。基本遺傳算法步1在搜尋空間U上定義一個適應(yīng)度函數(shù)f(x)，給定種群規(guī)模N，交叉率Pc和變異率Pm，代數(shù)T；步2隨機(jī)產(chǎn)生U中的N個個體s1,s2,…,sN，組成初始種群S={s1,s2,…,sN}，置代數(shù)計數(shù)器t=1；步3計算S中每個個體的適應(yīng)度f()；步4若終止條件滿足，則取S中適應(yīng)度最大的個體作為所求結(jié)果，算法結(jié)束。步5按選擇概率P(xi)所確定的選中機(jī)會，每次從S中隨機(jī)選定1個個體并將其染色體復(fù)制，共做N次，然后將復(fù)制所得的N個染色體組成群體S1；步6按交叉率Pc所確定的參與交叉的染色體數(shù)c，從S1中隨機(jī)確定c個染色體，配對進(jìn)行交叉操作，并用產(chǎn)生的新染色體代替原染色體，得群體S2；步7按變異率Pm所確定的變異次數(shù)m，從S2中隨機(jī)確定m個染色體，分別進(jìn)行變異操作，并用產(chǎn)生的新染色體代替原染色體，得群體S3；步8將群體S3作為新一代種群，即用S3代替S，t=t+1，轉(zhuǎn)步3；1.3遺傳算法應(yīng)用舉例

例4.1

利用遺傳算法求解區(qū)間［0,31］上的二次函數(shù)y=x2的最大值。

y=x2

31

XY分析原問題可轉(zhuǎn)化為在區(qū)間［0,31］中搜尋能使y取最大值的點a的問題。那么，［0,31］中的點x就是個體,函數(shù)值f(x)恰好就可以作為x的適應(yīng)度，區(qū)間［0,31］就是一個(解)空間。這樣,只要能給出個體x的適當(dāng)染色體編碼,該問題就可以用遺傳算法來解決。

解

(1)

設(shè)定種群規(guī)模,編碼染色體，產(chǎn)生初始種群。將種群規(guī)模設(shè)定為4；用5位二進(jìn)制數(shù)編碼染色體；取下列個體組成初始種群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)

(2)定義適應(yīng)度函數(shù),

取適應(yīng)度函數(shù)：f(x)=x2

(3)計算各代種群中的各個體的適應(yīng)度,并對其染色體進(jìn)行遺傳操作,直到適應(yīng)度最高的個體(即31（11111）)出現(xiàn)為止。

首先計算種群S1中各個體s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)的適應(yīng)度f(si)。簡潔求得f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361再計算種群S1中各個體的選擇概率。選擇概率的計算公式為

由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31

賭輪選擇示意s40.31s20.49s10.14s30.06●賭輪選擇法在算法中賭輪選擇法可用下面的子過程來模擬:①在［0,1］區(qū)間內(nèi)產(chǎn)生一個勻整分布的隨機(jī)數(shù)r。②若r≤q1,則染色體x1被選中。③若qk-1<r≤qk(2≤k≤N),則染色體xk被選中。其中的qi稱為染色體xi(i=1,2,…,n)的積累概率,其計算公式為選擇-復(fù)制

設(shè)從區(qū)間［0,1］中產(chǎn)生4個隨機(jī)數(shù)如下:

r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503

染色體適應(yīng)度選擇概率積累概率選中次數(shù)s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001于是，經(jīng)復(fù)制得群體：s1’

=11000（24）,s2’

=01101（13）s3’

=11000（24）,s4’

=10011（19）交叉設(shè)交叉率pc=100%，即S1中的全體染色體都參與交叉運算。設(shè)s1’與s2’配對，s3’與s4’配對。分別交換后兩位基因，得新染色體：s1’’=11001（25）,s2’’=01100（12）s3’’=11011（27）,s4’’=10000（16）

變異設(shè)變異率pm=0.001。這樣，群體S1中共有5×4×0.001=0.02位基因可以變異。0.02位明顯不足1位，所以本輪遺傳操作不做變異。于是，得到其次代種群S2：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）其次代種群S2中各染色體的狀況染色體適應(yīng)度選擇概率積累概率估計的選中次數(shù)s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.151.001

假設(shè)這一輪選擇-復(fù)制操作中，種群S2中的4個染色體都被選中，則得到群體：

s1’=11001（25）,s2’=01100（12）

s3’=11011（27）,s4’=10000（16）

做交叉運算，讓s1’與s2’，s3’與s4’

分別交換后三位基因，得

s1’’=11100（28）,s2’’=01001（9）

s3’’=11000（24）,s4’’=10011（19）

這一輪仍舊不會發(fā)生變異。于是，得第三代種群S3：

s1=11100（28）,s2=01001（9）

s3=11000（24）,s4=10011（19）

第三代種群S3中各染色體的狀況染色體適應(yīng)度選擇概率積累概率估計的選中次數(shù)s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.001

設(shè)這一輪的選擇-復(fù)制結(jié)果為：

s1’=11100（28）,s2’=11100（28）

s3’=11000（24）,s4’=10011（19）

做交叉運算，讓s1’與s4’，s2’與s3’

分別交換后兩位基因，得

s1’’=11111（31）,s2’’=11100（28）

s3’’=11000（24）,s4’’=10000（16）

這一輪仍舊不會發(fā)生變異。

于是，得第四代種群S4：

s1=11111（31）,s2=11100（28）

s3=11000（24）,s4=10000（16）

明顯，在這一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體s1=11111。于是，遺傳操作終止，將染色體“11111”作為最終結(jié)果輸出。然后，將染色體“11111”解碼為表現(xiàn)型，即得所求的最優(yōu)解：31。將31代入函數(shù)y=x2中，即得原問題的解，即函數(shù)y=x2的最大值為961。YYy=x2

8131924

X第一代種群及其適應(yīng)度y=x2

12162527

XY第二代種群及其適應(yīng)度y=x2

9192428

XY第三代種群及其適應(yīng)度y=x2

16242831

X第四代種群及其適應(yīng)度例1.2用遺傳算法求解TSP。分析由于其任一可能解——一個合法的城市序列，即n個城市的一個排列，都可以事先構(gòu)造出來。于是，我們就可以干脆在解空間（全部合法的城市序列）中搜尋最佳解。這正適合用遺傳算法求解。

（1）定義適應(yīng)度函數(shù)我們將一個合法的城市序列s=（c1,c2,…,cn,cn+1）(cn+1就是c1)作為一個個體。這個序列中相鄰兩城之間的距離之和的倒數(shù)就可作為相應(yīng)個體s的適應(yīng)度，從而適應(yīng)度函數(shù)就是（2）對個體s=（c1,c2,…,cn,cn+1）進(jìn)行編碼。但對于這樣的個體如何編碼卻不是一件直截了當(dāng)?shù)氖虑椤Ｒ驗榧偃缇幋a不當(dāng)，就會在實施交叉或變異操作時出現(xiàn)非法城市序列即無效解。例如，對于5個城市的TSP，我們用符號A、B、C、D、E代表相應(yīng)的城市，用這5個符號的序列表示可能解即染色體。然后進(jìn)行遺傳操作。設(shè)s1=（A,C,B,E,D,A），s2=（A,E,D,C,B,A）實施常規(guī)的交叉或變異操作，如交換后三位，得s1’=（A,C,B,C,B,A），s2’=（A,E,D,E,D,A）或者將染色體s1其次位的C變?yōu)镋，得s1’’=（A,E,B,E,D,A）可以看出，上面得到的s1’，s2’和s1’’都是非法的城市序列。為此，對TSP必需設(shè)計合適的染色體和相應(yīng)的遺傳運算。事實上，人們針對TSP提出了很多編碼方法和相應(yīng)的特殊化了的交叉、變異操作，如依次編碼或整數(shù)編碼、隨機(jī)鍵編碼、部分映射交叉、依次交叉、循環(huán)交叉、位置交叉、反轉(zhuǎn)變異、移位變異、互換變異等等。從而奇妙地用遺傳算法解決了TSP。遺傳算法2.1遺傳算法特點2.2遺傳算法的數(shù)學(xué)基礎(chǔ)2.3

遺傳算法的收斂性分析2.4遺傳算法改進(jìn)2.5遺傳算法的融合

2.1遺傳算法的特點與優(yōu)勢

◆傳統(tǒng)優(yōu)化算法-枚舉法：枚舉出可行解集合內(nèi)的全部可行解，以求出精確最優(yōu)解。 *對于連續(xù)函數(shù)，要求先進(jìn)行離散化處理。枚舉空間比較大時，方法求解效率較低，甚至無法求解。-啟發(fā)式算法：尋求一種能產(chǎn)生可行解的啟發(fā)式規(guī)則，已找到一個最優(yōu)解或近似最優(yōu)解。 *該方法的求解效率比較高，但對每一個需求解的問題必需找出其特有的啟發(fā)式規(guī)則，這個啟發(fā)式規(guī)則一般無通用性，不適合于其他問題。-搜尋算法：尋求一種搜尋算法，該算法在可行解集合的一個子集內(nèi)進(jìn)行搜尋操作，已找到問題的最優(yōu)解或近似最優(yōu)解。 *該方法雖然保證不了能夠獲得問題的最優(yōu)解，但若適當(dāng)?shù)乩靡恍﹩l(fā)式規(guī)則，就可以在近似解的質(zhì)量和效率上達(dá)到一種較好的平衡?！暨z傳算法的主要特點——遺傳算法一般是干脆在解空間搜尋,而不像圖搜尋那樣一般是在問題空間搜尋,最終才找到解，因而可以更加干脆地應(yīng)用?！z傳算法是一種隨機(jī)搜尋算法，搜尋隨機(jī)地始于搜尋空間的一個點集，避開使得算法總是陷入到相同的局部微小點（局部最優(yōu)值）。

——遺傳算法接受適應(yīng)度函數(shù)和遺傳操作，從而設(shè)法盡快找到解,所以遺傳算法又是一種優(yōu)化搜尋算法?！z傳算法的搜尋過程是從空間的一個點集(種群)到另一個點集(種群)的搜尋,而不像圖搜尋那樣一般是從空間的一個點到另一個點地搜尋。因而它實際是一種并行搜尋,適合大規(guī)模并行計算,而且這種種群到種群的搜尋有實力跳出局部最優(yōu)解?！z傳算法的適應(yīng)性強(qiáng),除需知適應(yīng)度函數(shù)外,幾乎不須要其他的先驗學(xué)問?！z傳算法長于全局搜尋,它不受搜尋空間的限制性假設(shè)的約束,不要求連續(xù)性,能以很大的概率從離散的、多極值的、含有噪聲的高維問題中找到全局最優(yōu)解。 ——遺傳算法對應(yīng)給定問題，可產(chǎn)生很多潛在解，并可由運用者來確定最終解。2.2遺傳算法的數(shù)學(xué)基礎(chǔ)模式定理積木塊假設(shè)模式是指種群個體基因串中的相像樣板，它用來描述基因串中某些特征位相同的結(jié)構(gòu)。在二進(jìn)制編碼中，模式是基于三個字符集(0,1,*)的字符串，符號*代表隨意字符，即0或者1。對于二進(jìn)制編碼串，當(dāng)串長為l時，共有3l個不同的模式，遺傳算法中串的運算事實上是模式的運算。模式示例：*1* 表示四元子集{010，011，110，111}與模式0******相比，模式011***1在相像性方面有更明確的表示；模式0*0***與模式0****0相比要跨越整個串長更大的部分。定義1：模式H中確定位置的個數(shù)稱為模式H的階，記作O(H)。例如O(10**1)=3。定義2：模式H中第一個確定位置和最終一個確定位置之間的距離稱為模式H的定義距，記作δ(H)。例如δ(10**1*)=4。模式的階和定義距的含義：模式階用來反映不同模式間確定性的差異，模式階數(shù)越高，模式的確定性就越高，所匹配的樣本數(shù)就越少。在遺傳操作中，即使階數(shù)相同的模式，也會有不同的性質(zhì)，而模式的定義距就反映了這種性質(zhì)的差異。模式定理模式定理：具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式在子代中呈指數(shù)增長。模式定理保證了較優(yōu)的模式（遺傳算法的較優(yōu)解）的數(shù)目呈指數(shù)增長，為說明遺傳算法機(jī)理供應(yīng)了數(shù)學(xué)基礎(chǔ)。從模式定理可看出，有高平均適應(yīng)度、短定義距、低階的模式，在連續(xù)的后代里獲得至少以指數(shù)增長的串?dāng)?shù)目，這主要是因為選擇使最好的模式有更多的復(fù)制，交叉算子不簡潔破壞高頻率出現(xiàn)的、短定義長的模式，而一般突變概率又相當(dāng)小，因而它對這些重要的模式幾乎沒有影響。積木塊假設(shè)：積木塊假設(shè)：遺傳算法通過短定義距、低階以及高平均適應(yīng)度的模式（積木塊），在遺傳操作下相互結(jié)合，最終接近全局最優(yōu)解。模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長，從而使遺傳算法找到全局最優(yōu)解的可能性存在；而積木塊假設(shè)則指出了在遺傳算子的作用下，能生成全局最優(yōu)解。2.3遺傳算法的收斂性分析遺傳算法要實現(xiàn)全局收斂，首先要求隨意初始種群經(jīng)有限步都能到達(dá)全局最優(yōu)解，其次算法必需由保優(yōu)操作來防止最優(yōu)解的遺失。與算法收斂性有關(guān)的因素主要包括種群規(guī)模、選擇操作、交叉概率和變異概率。種群規(guī)模對收斂性的影響通常，種群太小則不能供應(yīng)足夠的采樣點，以致算法性能很差；種群太大，盡管可以增加優(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ī)搜尋算法。遺傳算法的本質(zhì)遺傳算法本質(zhì)上是對染色體模式所進(jìn)行的一系列運算，即通過選擇算子將當(dāng)前種群中的優(yōu)良模式遺傳到下一代種群中，利用交叉算子進(jìn)行模式重組，利用變異算子進(jìn)行模式突變。通過這些遺傳操作，模式逐步向較好的方向進(jìn)化，最終得到問題的最優(yōu)解。2.4遺傳算法的改進(jìn)

自從1975年J.H.Holland系統(tǒng)提出遺傳算法的完整結(jié)構(gòu)和理論以來，眾多學(xué)者始終致力于推動遺傳算法的發(fā)展，對編碼方式、限制參數(shù)的確定、選擇方式和交叉機(jī)理等進(jìn)行了深化探討，引入了動態(tài)策略和自適應(yīng)策略以改善遺傳算法的性能，提出了各種變形的遺傳算法。基本改進(jìn)途徑概括起來包括變更遺傳算法的組成成分或運用技術(shù)，如選用優(yōu)化限制參數(shù)、適合問題特性的編碼技術(shù)等接受混合遺傳算法接受動態(tài)自適應(yīng)技術(shù)，在進(jìn)化過程中調(diào)整算法限制參數(shù)和編碼粒度接受非標(biāo)準(zhǔn)的遺傳操作算子接受并行遺傳算法對編碼方式的改進(jìn)二進(jìn)制編碼優(yōu)點在于編碼、解碼操作簡潔，交叉、變異等操作便于實現(xiàn)，缺點在于精度要求較高時，個體編碼串較長，使算法的搜尋空間急劇擴(kuò)大，遺傳算法的性能降低。格雷編碼克服了二進(jìn)制編碼的不連續(xù)問題，浮點數(shù)編碼改善了遺傳算法的計算困難性。對遺傳算子的改進(jìn)排序選擇勻整交叉逆序變異（1）對群體中的全部個體按其適應(yīng)度大小進(jìn)行降序排序；（2）依據(jù)具體求解問題，設(shè)計一個概率安排表，將各個概率值按上述排列次序安排給各個個體；（3）以各個個體所安排到的概率值作為其遺傳到下一代的概率，基于這些概率用賭盤選擇法來產(chǎn)生下一代群體。對遺傳算子的改進(jìn)排序選擇勻整交叉逆序變異（1）隨機(jī)產(chǎn)生一個與個體編碼長度相同的二進(jìn)制屏蔽字P=W1W2…Wn

；（2）按下列規(guī)則從A、B兩個父代個體中產(chǎn)生兩個新個體X、Y：若Wi=0，則X的第i個基因繼承A的對應(yīng)基因，Y的第i個基因繼承B的對應(yīng)基因；若Wi=1，則A、B的第i個基因相互交換，從而生成X、Y的第i個基因。對遺傳算子的改進(jìn)排序選擇勻整交叉逆序變異變異前：348|7965|21變異前：348|5697|21對限制參數(shù)的改進(jìn)Schaffer建議的最優(yōu)參數(shù)范圍是：M=20-100，T=100-500，Pc=0.4-0.9，Pm=0.001-0.01。

對限制參數(shù)的改進(jìn)Srinvivas等人提出自適應(yīng)遺傳算法，即PC和Pm能夠隨適應(yīng)度自動變更，當(dāng)種群的各個個體適應(yīng)度趨于一樣或趨于局部最優(yōu)時，使二者增加，而當(dāng)種群適應(yīng)度比較分散時，使二者減小，同時對適應(yīng)值高于群體平均適應(yīng)值的個體，接受較低的PC和Pm，使性能優(yōu)良的個體進(jìn)入下一代，而低于平均適應(yīng)值的個體，接受較高的PC和Pm，使性能較差的個體被淘汰。對執(zhí)行策略的改進(jìn)混合遺傳算法免疫遺傳算法小生境遺傳算法單親遺傳算法并行遺傳算法分層遺傳算法

分層遺傳算法基本流程框圖初始化N個子種群N個子種群獨立運行遺傳算法一定代數(shù)N個結(jié)果種群及平均適應(yīng)度值記錄到R[1...N,1...n]及A[i]對R[1...N,1...n]進(jìn)行選擇和交叉對R[1...N,1...n]進(jìn)行變異操作對新的N個子種群重新開始遺傳算法操作性能滿足?結(jié)束并行遺傳算法（parallelGA，PGA）遺傳算法中適應(yīng)度的計算最費時間，再加上須要不斷產(chǎn)生新一代，而每一代又有若干個個體，隨意如何提高遺傳算法的運行速率顯得尤為突出。由于遺傳算法的內(nèi)在并行機(jī)制，其并行處理是很自然的解決途徑。并行遺傳算法的實現(xiàn)方案全局型——主從式模式（master-slavemodel）獨立型——粗粒度模型（coarse-grainedmodel）；孤島模型；分布式遺傳算法分散型——細(xì)粒度模型（fine-grainedmodel）全局型處理方式：并行系統(tǒng)分為一個主處理器和若干個從處理器主處理器監(jiān)控整個染色體種群，并基于全