1、http:/ - 1 - 遺傳算法在工程優(yōu)化中的幾點(diǎn)改進(jìn)陳玲俐，姚宇瓊，于潔上海大學(xué)土木系，上海（200072）E-mail：摘要：本文面對工程優(yōu)化中的實(shí)際困難，對傳統(tǒng)遺傳算法進(jìn)行了系統(tǒng)改進(jìn)。在遺傳算法中采用動(dòng)態(tài)種群規(guī)模，消除了種群規(guī)模對優(yōu)化效率和優(yōu)化質(zhì)量的影響；在選擇操作中加入記憶功能， 避免了大量重復(fù)計(jì)算工作；針對實(shí)數(shù)編碼導(dǎo)致的雜交操作并行機(jī)制喪失問題，提出了雙重模糊編碼方法；為了提高優(yōu)化效率，提出用啟發(fā)式優(yōu)化準(zhǔn)則減少變異操作中的盲目性。為避免早熟收斂，在優(yōu)化進(jìn)程中逐步增大變異率，減小雜交率。 改進(jìn)的遺傳算法在不破壞自適應(yīng)并行運(yùn)算機(jī)制的同時(shí)，規(guī)避了種群的無效解、消除了優(yōu)化過程中的重復(fù)計(jì)算，

2、提高了優(yōu)化效率。關(guān)鍵詞 ：遺傳算法，動(dòng)態(tài)種群，雙重模糊編碼1. 引言遺傳算法是1975 年美國密西根大學(xué)的Holand 教授借鑒生物進(jìn)化原則，提出的一種自適應(yīng)并行優(yōu)化算法。在自然界中， 生物的染色體決定生物的形態(tài)。千差萬別的染色體都是由相同數(shù)目的基因組成，一個(gè)基因只能是兩種屬性值（X，Y）中的一種 （也可以表示為0 或 1） ，不同屬性值的基因的組合方式構(gòu)成了千差萬別的染色體。生物進(jìn)化過程是染色體中的基因優(yōu)化過程。 在工程和數(shù)學(xué)優(yōu)化問題中，優(yōu)化方案決定優(yōu)化目標(biāo)。千差萬別的優(yōu)化方案都是由相同數(shù)目的優(yōu)化參數(shù)組成，一個(gè)優(yōu)化參數(shù)只能取有限的幾個(gè)值、或在有限區(qū)間L，U中取值，不同取值的優(yōu)化參數(shù)的組合方式

3、構(gòu)成了千差萬別的設(shè)計(jì)方案。可見，優(yōu)化問題與生物進(jìn)化問題從表達(dá)方式到最終目標(biāo)都非常相似。將優(yōu)化問題表述成生物進(jìn)化問題，在優(yōu)化過程中采用生物進(jìn)化原則，實(shí)現(xiàn)優(yōu)化目的的一類算法，稱為遺傳算法。2. 傳統(tǒng)遺傳算法遺傳算法在求解優(yōu)化問題時(shí)一般包括以下幾個(gè)步驟：1、 編碼。 將優(yōu)化參數(shù)表示為基因的過程稱為編碼。由于生物基因?qū)傩灾挥袃煞N，對應(yīng)0-1 二進(jìn)制編碼中的一個(gè)編碼位。如果優(yōu)化參數(shù)的值域也只包括兩個(gè)值，則用一個(gè)編碼位的基因就可以代表一個(gè)優(yōu)化參數(shù)。如果優(yōu)化參數(shù)的值域包括多個(gè)值、或者優(yōu)化參數(shù)為一個(gè)連續(xù)變量，則多個(gè)編碼位的基因才能表示一個(gè)優(yōu)化參數(shù)。例如，優(yōu)化參數(shù)的值域?yàn)椋?7）的8個(gè)整數(shù)，稱值域空間為8，則需

4、要 3 個(gè)編碼位才能表示一個(gè)優(yōu)化參數(shù)。優(yōu)化參數(shù)的值域空間大小決定了編碼位數(shù)的大小。如果編碼位數(shù)為n，則編碼空間為2 n。一般編碼空間不小于優(yōu)化參數(shù)的值域空間。當(dāng)編碼空間大于優(yōu)化參數(shù)的值域空間時(shí)，則基因值可能會(huì)對應(yīng)無意義的或超界的優(yōu)化參數(shù)值。對此，要進(jìn)行修正、淘汰或加以懲罰。這種處理干擾了算法的自然進(jìn)化過程。 為了避免編碼空間與優(yōu)化參數(shù)的值域空間不一致問題，又提出了自然數(shù)編碼、序列編碼和實(shí)數(shù)編碼等編碼形式。如值域空間為8 的優(yōu)化參數(shù)， 可以用變化范圍為18 的一個(gè)自然數(shù)編碼位來表示。后三種編碼方式大大降低了編碼和譯碼的工作量，在工程優(yōu)化中應(yīng)用廣泛，但是這些編碼方式破壞了在生物雜交操作中隱含的并行

5、機(jī)制。2、 遺傳操作。 遺傳操作是通過種群性態(tài)的比較，使好的染色體遺傳到下一代，差的染色體失去繁殖權(quán)利。染色體的好壞通過適應(yīng)函數(shù)值的大小來評價(jià)，適應(yīng)值不小于零。適應(yīng)值http:/ - 2 - 函數(shù)要通過具體的目標(biāo)函數(shù)值和約束情況綜合考慮，構(gòu)建。 適應(yīng)值函數(shù)與目標(biāo)函數(shù)值的關(guān)系通常有以下幾種關(guān)系：線性關(guān)系、指數(shù)關(guān)系、對數(shù)關(guān)系、倒數(shù)關(guān)系等。當(dāng)染色體對應(yīng)的優(yōu)化方案滿足優(yōu)化模型中的約束關(guān)系，約束對染色體的適應(yīng)值不產(chǎn)生影響；當(dāng)約束關(guān)系不滿足時(shí)，要根據(jù)違約量的大小，對目標(biāo)函數(shù)值得到的適應(yīng)值附加一項(xiàng)懲罰。違約量越大， 懲罰量越大。如果一個(gè)優(yōu)化方案違反嚴(yán)格約束，則此方案的適應(yīng)值為零。這種處理方式相當(dāng)于淘汰不滿足

6、約束條件的解， 在窄界約束條件下，很少采用這種處理方式。在種群中挑選遺傳的染色體有多種選擇方法：賭盤選擇、確定性原則、有退還和無退還隨機(jī)選擇、有退還和無退還剩余隨機(jī)選擇。 在后面我們將介紹一種新的遺傳選擇機(jī)制，有繁殖能力的染色體只能在子代中復(fù)制一個(gè)樣本，有效避免降低種群的多樣性。3、 雜交操作。雜交操作通過交換兩對染色體中的部分等位基因，變成兩個(gè)新的染色體。雜交操作分為一點(diǎn)雜交、多點(diǎn)雜交和分段雜交。對于二維編碼，對應(yīng)著二維雜交。在常規(guī)的雜交操作中一般用新解替代舊解。這種做法可能會(huì)破壞遺傳下來的最優(yōu)解。因此， 本文改進(jìn)的遺傳算法采用新解舊解同時(shí)保留策略。這里所說的舊解，已經(jīng)是經(jīng)過遺傳操作篩選后的

7、最優(yōu)種群，保留舊解不會(huì)降低算法優(yōu)化效率，卻可以擴(kuò)大種群多樣性。4、 變異操作。變異操作通過改變?nèi)旧w中的一個(gè)和多個(gè)基因?qū)傩灾?，得到新的染色體。對于二進(jìn)制編碼，變異只需要對待變異基因的屬性按位取反，0、1 互變即可。對于自然數(shù)編碼，可以在取值空間隨機(jī)選取與待變異基因原有屬性不同的值即可。傳統(tǒng)的變異操作與雜交操作一樣，也是采用新解替代舊解策略。本文同時(shí)保留新、舊解，原因同上。如果雜交操作和變異操作產(chǎn)生的新解數(shù)量超過遺傳操作中淘汰解的數(shù)量，則此時(shí)種群規(guī)模大于上一代的種群規(guī)模。雖然本文改進(jìn)的遺傳算法最大特點(diǎn)是在計(jì)算過程中采用動(dòng)態(tài)的種群規(guī)模。但是如果種群規(guī)模一代代擴(kuò)張，不加控制，則計(jì)算效率將很低下，遺傳

8、算法等同于隨機(jī)搜索。 因此在本文的遺傳算法中對種群規(guī)模給定上下限。種群初始規(guī)模在種群規(guī)模的上下限之間。當(dāng)種群規(guī)模大于上限值時(shí)，對種群進(jìn)行多次選擇，優(yōu)中選優(yōu)；當(dāng)種群規(guī)模小于下限值時(shí)，在淘汰解中進(jìn)行二次選擇，次中選優(yōu)。使種群規(guī)模滿足上下限限制。5、 收斂判斷。 遺傳算法有多種收斂判斷方法。方法一： 計(jì)算代數(shù)不超過指定的最大遺傳代數(shù)；方法二：最優(yōu)值與種群均值的差小于指定的小量；方法三：最優(yōu)值連續(xù)多代保持穩(wěn)定。為了保證全局搜索，在方法一中，最大遺傳代數(shù)越大越好。用方法二得到的最優(yōu)解如果不理想， 說明算法在應(yīng)用時(shí)可能出現(xiàn)了早熟收斂問題（種群在沒有搜索到最優(yōu)解時(shí)已經(jīng)喪失多樣性，使優(yōu)化停滯不前）。此時(shí)可以通

9、過擴(kuò)大種群規(guī)模和加大變異率，重新計(jì)算。第三種判斷方法不很可靠。遺傳算法的計(jì)算效率與以下幾個(gè)參數(shù)決定：種群規(guī)模、雜交率、變異率。種群規(guī)模大，計(jì)算時(shí)間長，能保證全局搜索。反之，計(jì)算時(shí)間短，但是可能會(huì)出現(xiàn)早熟收斂問題。在遺傳算法應(yīng)用中通常采用固定種群規(guī)模的做法。本文在計(jì)算中采用動(dòng)態(tài)種群規(guī)模，避免了固定種群規(guī)模對遺傳算法計(jì)算效率的影響。下面我們來詳細(xì)介紹有記憶動(dòng)態(tài)種群遺傳算法的每個(gè)操作步驟。3. 有記憶動(dòng)態(tài)種群遺傳算法3.1 編碼工程優(yōu)化中優(yōu)化參數(shù)多為實(shí)數(shù)，設(shè)優(yōu)化參數(shù)xj的有效取值空間為（，） ，采用實(shí)數(shù)編碼，http:/ - 3 - ( )()()code xrand =-（1）其中 rand()為

10、 01 的隨機(jī)數(shù)。 采用（1）式得到的xj的編碼 code(xj)取值區(qū)間為 ，。用 +， -替換（ 1）式中的和，為一接近零的小正數(shù)；則code(xj)的取值區(qū)間為開區(qū)間（，） ，xj= code( xj)。這種編碼方式顯然無需再譯碼，同時(shí)可以避免優(yōu)化參數(shù)落入無效取值空間形成無意義解，即無效種群。但是，實(shí)數(shù)編碼會(huì)導(dǎo)致雜交操作在很大程度上喪失并行運(yùn)算機(jī)制。為了彌補(bǔ)這個(gè)缺陷，在進(jìn)行雜交操作時(shí)可以對參與雜交操作的染色體采用雙重編碼，即同時(shí)采用實(shí)數(shù)編碼和模糊二進(jìn)制編碼。取值空間為（，）的一個(gè)實(shí)型優(yōu)化參數(shù)xk，如果采用二進(jìn)制編碼需要占用n 個(gè)編碼位， 我們將這 n 個(gè)編碼位分為前、中、后三組（記為 I

11、1I2I3） ；最前一組編碼位非零時(shí)（100，110，111）表示xj取值接近；最前一組為零，而中間一組非零時(shí)（010，011）表示xj取值接近2 +；當(dāng)前兩組編碼為均為零時(shí)（001，000）表示xj取值接近。我們將這種分組二進(jìn)制編碼稱為模糊二進(jìn)制編碼。模糊二進(jìn)制編碼（I1I2I3）映射到實(shí)數(shù)編碼為：123()2)7jxrandIII -+?+(4(2) 實(shí)數(shù)編碼到模糊二進(jìn)制編碼的映射規(guī)則為：當(dāng)23jx+時(shí)賦予其模糊二進(jìn)制編碼記為(100)；2233jx +；存活（4）Int 為取整函數(shù)。存活的染色體的數(shù)量記為pop1，pop1 1，在優(yōu)化過程中pop1 是不定的。 當(dāng)種群的適應(yīng)值都接近max

12、fit() 時(shí)， 存活的染色體就多； 當(dāng)種群的適應(yīng)值都接近minfit()時(shí)，存活的染色體就少。存活的染色體相當(dāng)于在子代中復(fù)制了一個(gè)樣本，這部分樣本的適應(yīng)值顯然已經(jīng)知道，無需重復(fù)計(jì)算。3.4 雜交率和變異率雜交率和變異率取值目前只能采用試算法確定。一般的取值原則是如果種群規(guī)模較小，則雜交率和變異率取值要稍大，目的是增加種群的多樣性。但是雜交率和變異率不能過大，避免雜交和變異產(chǎn)生的新解替換過多的遺傳舊解，使算法的自適應(yīng)特性不突出，變成隨機(jī)搜索。由于本文改進(jìn)的遺傳算法不存在種群規(guī)模對種群多樣性的制約。因此， 雜交率和變異率的取值不受種群規(guī)模大小的影響。另外在雜交和變異操作中采用的新、舊解不替換策略

13、，雜交率和變異率過高不會(huì)破壞算法自適應(yīng)性質(zhì)。因此， 在本文所采用的改進(jìn)遺傳算法中，雜交率和變異率初始取值原則是雜交率高于變異率；其次，初始雜交和變異操作產(chǎn)生的新解數(shù)目略大于遺傳操作中淘汰解的數(shù)目?？紤]到優(yōu)化后期種群逐步趨同，雜交操作往往不能產(chǎn)生新解。為減少無效解，避免種群早熟收斂優(yōu)化過程中通過公式（5） （ 6）逐步降低雜交率，提高變異率。雜交和變異產(chǎn)生的新解的數(shù)目分別為2pop2, pop3 。1,0iterpopNiter?-?cpop1pop2=min int2 (5) 1,0iterpopNiter?+?cpop3=min intpop1 (6) 雜交和變異產(chǎn)生的新解的數(shù)目分別為2po

14、p2, pop3 。 Niter, iter 分別為最大遺傳代數(shù)和遺傳代數(shù)；由于pop1 在優(yōu)化過程中不定，所以在這里我們要規(guī)定最小新解數(shù)量pop0，避免優(yōu)化過程無法進(jìn)行下去。至此，新一代種群規(guī)模變?yōu)閜op=pop1+2 pop2+pop3。由于記憶功能的加入，在新的種群中我們只需要計(jì)算雜交和變異得到的新解的適應(yīng)值。隨著優(yōu)化過程的展開，由于我們沒有用雜交和變異得到的新解替換父代舊解，種群規(guī)?？赡芤淮蛎洝Ｓ捎谟?jì)算機(jī)的存儲(chǔ)和計(jì)算容量是有限的，當(dāng)新一代種群規(guī)模在遺傳操作后存活種群數(shù)量pop1 達(dá)到或超過指定的最大種群規(guī)模pop_max 時(shí)，令 pop=pop1，重新計(jì)算存活種群的相對適應(yīng)值fit

15、，進(jìn)行二次遺傳操作。重復(fù)上面過程直到pop1pop_max。3.5 雜交操作雜交操作的實(shí)質(zhì)是兩個(gè)解xi，xj中一個(gè)或多個(gè)解構(gòu)成信息的互換（如圖1） 。采用二進(jìn)制編碼時(shí)多個(gè)編碼位置的取值決定一個(gè)實(shí)數(shù)參數(shù)的取值大小，信息互換不僅可實(shí)現(xiàn)參數(shù)值的互換，而且可以產(chǎn)生新的數(shù)值。例如8（ 1000）和 3（0011）如果采用二進(jìn)制單點(diǎn)雜交可以得到 0（0000） 、11（1011）和 10（1010） 、1（0001）及 9（1001） 、2（0001）三對新的數(shù)值。采用實(shí)數(shù)編碼時(shí)， 一個(gè)編碼位置對應(yīng)一個(gè)優(yōu)化參數(shù)，雜交操作通常只能實(shí)現(xiàn)優(yōu)化參數(shù)的互換。上例中的8 和 3 雜交后仍然為8 和 3，只是在解向量中

16、發(fā)生了互換，二進(jìn)制編碼時(shí)雜交操作中所蘊(yùn)含的并行運(yùn)算機(jī)制不復(fù)存在。http:/ - 5 - 圖 1 雜交操作Fig.1 Crossover operation 如果各優(yōu)化參數(shù)的靈敏度相近，則所優(yōu)化系統(tǒng)的性能主要表現(xiàn)為優(yōu)化參數(shù)的組合效應(yīng)，這種實(shí)數(shù)雜交操作仍然是有效的，無需采用雙重編碼。但是當(dāng)各優(yōu)化參數(shù)的靈敏度相差較大時(shí)，這種實(shí)數(shù)雜交操作是一種低效的優(yōu)化手段，有時(shí)甚至比隨機(jī)搜索還要差?；谀：M(jìn)制編碼的雜交操作能夠部分恢復(fù)傳統(tǒng)雜交操作所蘊(yùn)含的并行運(yùn)算機(jī)制，同時(shí)充分利用實(shí)數(shù)編碼的優(yōu)點(diǎn)?；谀：M(jìn)制編碼的雜交操作其編碼長度變?yōu)?m，可以采用單點(diǎn)雜交、多點(diǎn)雜交等傳統(tǒng)雜交操作方式。 （100） （ 01

17、1） （001）多點(diǎn)雜交后會(huì)新產(chǎn)生(111)(110)(101)(011)(000) 五種編碼方式。與傳統(tǒng)二進(jìn)制編碼雜交操作唯一不同的地方是譯碼，見公式（2） 。3.6 變異操作采用實(shí)數(shù)編碼的變異操作可以采用單點(diǎn)變異或多點(diǎn)變異，變異方法見公式（1） 。由于多數(shù)工程優(yōu)化問題有明確的物理意義?；诠こ虄?yōu)化的物理意義或者已經(jīng)積累的工程設(shè)計(jì)經(jīng)驗(yàn)， 我們可以建立一些啟發(fā)式優(yōu)化準(zhǔn)則。這些啟發(fā)式優(yōu)化準(zhǔn)則在大型復(fù)雜工程系統(tǒng)優(yōu)化中很難給出全局最優(yōu)解；但是由于這些啟發(fā)式優(yōu)化準(zhǔn)則能夠直觀反映工程優(yōu)化中的部分優(yōu)化規(guī)律，利用啟發(fā)式優(yōu)化準(zhǔn)則給出的優(yōu)化方向作為變異方向通?？梢允棺儺惒僮鞲佑行?。3.7 收斂判斷收斂準(zhǔn)則與傳

18、統(tǒng)遺傳算法相同，這里不再贅述。4工程優(yōu)化實(shí)例一工程系統(tǒng)的組成結(jié)構(gòu)如圖2 所示，節(jié)點(diǎn)間路徑可靠度r 與造價(jià) c、路徑長度l 之間的對應(yīng)關(guān)系為：(10.7 )clr =-。在總造價(jià)約等于35 條件下，求系統(tǒng)各路徑可靠度，要求使系統(tǒng)源點(diǎn)到匯點(diǎn)的連通可靠度最大。路徑長度均為1。圖 2 工程系統(tǒng)組成結(jié)構(gòu)Fig.2 Topology structure of the engineering system 該優(yōu)化問題的優(yōu)化參數(shù)數(shù)量m17，優(yōu)化參數(shù)的取值區(qū)間為0, 1) 。取初始種群規(guī)模為30， 初始雜交率和變異率取為0.4, 0.2； 最小新解數(shù)量pop06， 最大種群規(guī)模pop_max120。1(源點(diǎn) )

19、 4 2 3568710(匯點(diǎn) )9xi1 xi2 xikxi,(k+ 1)xi,(k+ 2) xi,(m-11)ximxj1 xj2 xjk xj,(k+1) x j,(k+2) xj,(m-11)xjmxi1 xi2 xjk xj,(k+1) x j,(k+2) xi,(m-11)ximxj1 xj2 xikxi,(k+ 1)xi,(k+ 2) xj,(m-11)xjm雜交http:/ - 6 - 需要指出的是由于優(yōu)化過程中采用了動(dòng)態(tài)種群規(guī)模，這些初始參數(shù)只在優(yōu)化初期對優(yōu)化進(jìn)程有所影響。根據(jù)單元可靠度越大造價(jià)越高的變化規(guī)律，變異操作時(shí)采用的啟發(fā)式優(yōu)化準(zhǔn)則為：()()(),( )35()()

20、(),( )35ikikikiikikimutute rrrandrc rmutute rrrandc r?=-+?=-+?采用本文的有記憶動(dòng)態(tài)種群遺傳算法得到的優(yōu)化結(jié)果見表1。表 1 優(yōu)化結(jié)果Tab.1 Optimization result 路徑可靠度路徑可靠度路徑可靠度路徑可靠度1-2 0 3-4 0.713735-8 0.248958-10 0.359271-3 0.89871 3-7 0.921056-8 0.379697-6 0.867501-4 0 4-7 0 6-9 0.178287-9 0.168422-5 0 5-6 0 6-10 0.893329-10 0.171943-

21、5 0.21449 系統(tǒng)可靠度：0.67115 系統(tǒng)總造價(jià)：35.189 5結(jié)語遺傳算法經(jīng)過三十多年的研究，借鑒和結(jié)合其它優(yōu)化算法的優(yōu)點(diǎn)，由一種算法發(fā)展為形式極其豐富的一類算法。各種改進(jìn)的遺傳算法或是彌補(bǔ)了算法在應(yīng)用時(shí)存在的潛在缺點(diǎn)，如早熟收斂問題、欺騙解問題等；或者提高了算法的計(jì)算效率。在本文提出的動(dòng)態(tài)種群規(guī)模的遺傳算法中，我們加入了記憶功能。算法對舊解的目標(biāo)函數(shù)值和約束函數(shù)值具有記憶，在子代計(jì)算時(shí)， 不需要再次計(jì)算從遺傳操作得到的舊解的目標(biāo)函數(shù)和約束函數(shù)值，只需對新解進(jìn)行計(jì)算，避免了重復(fù)計(jì)算。對于小雜交率和變異率的遺傳算法， 子代中的大部分解為遺傳得來的舊解，記憶功能的引入，大大降低了子代

22、實(shí)際求解規(guī)模。在工程優(yōu)化問題中，目標(biāo)函數(shù)和約束函數(shù)的計(jì)算通常最為耗時(shí)。避免目標(biāo)函數(shù)和約束函數(shù)的重復(fù)計(jì)算，意義很重大。參考文獻(xiàn)1 米凱利維茲 Z. ， （2000） ，演化程序 遺傳算法和數(shù)據(jù)編碼的結(jié)合，科學(xué)出版社。2 陳玲俐 . 城市供水系統(tǒng)抗震功能分析與優(yōu)化. 上海：同濟(jì)大學(xué)博士學(xué)位論文，2002 年 7 月. 3 Li M, ,Sun X Y, Gong D W. Adaptive hierarchy genetic algorithm .Journal of China University of Mining & Technology, 2002, 31 (6) :622624

23、 . 4 LEE Heow Pueh,LIM Siak Piang,LEE Kwok Hong. Solving traveling salesman problems by genetic algorithmsJ. Progress in Natural Science , 2003,(02) . 5 沈洪遠(yuǎn) ,彭小奇 ,王俊年 ,胡志坤 ,. 基于混沌序列的多峰函數(shù)微粒群尋優(yōu)算法J. 計(jì)算機(jī)工程與應(yīng)用 , 2006,(07) . http:/ - 7 - Some Improvements of Genetic Algorithm for Engineering Optimization

24、Ghen Lingli ，Yao Yuqiong，Yu Jie Department of Civil engineering ，Shanghai Uni.， Shanghai （ 200072）Abstract The classical genetic algorithms are improved to solved the engineering optimization problems. The changeable population is used in Gas in order to eliminate the disturbances of population to optimization efficient and quality. The memory fu