遺傳算法及其在機(jī)構(gòu)參數(shù)優(yōu)化中的應(yīng)用

1、11.1 遺傳算法及其在機(jī)構(gòu)參數(shù)優(yōu)化中的應(yīng)用 基于進(jìn)化規(guī)律的遺傳算法（Genetic Algorithm）簡(jiǎn)稱GA，是一種模擬生物進(jìn)化過(guò)程的隨機(jī)全局優(yōu)化搜索方法。GA最早是由提出來(lái)的，自20世紀(jì)80年代中期以來(lái)，由于計(jì)算機(jī)容量的不斷擴(kuò)大和速度的不斷提高，以及GA方法本身的逐步成熟，GA得到了迅速的發(fā)展。它具有很強(qiáng)的魯棒性和通用優(yōu)化能力，優(yōu)化計(jì)算時(shí)只需適應(yīng)度函數(shù)值（適值），不需要導(dǎo)數(shù)信息，可應(yīng)用于科學(xué)研究和工程實(shí)際中的各種搜索過(guò)程和優(yōu)化問(wèn)題，特別是能較有效地求解常規(guī)優(yōu)化方法難以解決的組合優(yōu)化問(wèn)題和大型復(fù)雜非線性系統(tǒng)的全局尋優(yōu)問(wèn)題，因此適用范圍廣。目前，其應(yīng)用遍布于計(jì)算機(jī)科學(xué)、物理學(xué)、社會(huì)學(xué)、圖像

2、處理、生產(chǎn)管理、企業(yè)經(jīng)營(yíng)規(guī)劃、最優(yōu)控制等領(lǐng)域。近年來(lái)，GA在機(jī)構(gòu)參數(shù)優(yōu)化方面的應(yīng)用也越來(lái)越多。11.1.1 遺傳算法原理生物的進(jìn)化是一個(gè)依照群體遺傳與自然選擇機(jī)理進(jìn)行的過(guò)程，優(yōu)勝劣汰，適者生存，有利于生存的基因遺傳給下一代，含不利于生存的基因的個(gè)體產(chǎn)生子代機(jī)會(huì)較小而逐漸消亡?；谶@一原理，GA搜索首先是利用隨機(jī)方法產(chǎn)生一初始群體（祖先），這一點(diǎn)與傳統(tǒng)的搜索方法不同。群體中的每個(gè)個(gè)體稱為染色體，它是一串符號(hào)，比如一個(gè)二進(jìn)制字符串，對(duì)應(yīng)著優(yōu)化問(wèn)題的一個(gè)設(shè)計(jì)向量（即一個(gè)可能解）。染色體的最小組成元素稱為基因，如二進(jìn)制字符串的一位?；蚺c設(shè)計(jì)變量的關(guān)系取決于編碼方法。例如，采用實(shí)數(shù)編碼時(shí)，基因即解空間

3、編碼初始群體 結(jié) 果解碼評(píng)價(jià)后代新種群選 擇 雜 交變 異圖11.13 遺傳算法過(guò)程對(duì)應(yīng)某一設(shè)計(jì)變量（即可能解的某一特征）；采用二進(jìn)制編碼時(shí)，若干個(gè)基因?qū)?yīng)一個(gè)設(shè)計(jì)變量。搜索過(guò)程中，這些染色體不斷遺傳進(jìn)化，產(chǎn)生下一代，即稱為后代。染色體的后代是前一代通過(guò)雜交、變異操作產(chǎn)生的。新一代群體的形成是按照優(yōu)勝劣汰的原則對(duì)染色體進(jìn)行選擇，相對(duì)好的個(gè)體被選中的概率高，得以繁殖，相對(duì)差的個(gè)體將趨于死亡。因此，通過(guò)選擇、雜交、變異等過(guò)程，群體的整體性能趨于改善。經(jīng)過(guò)若干代繁衍進(jìn)化，群體性能趨于最佳。遺傳算法的主要步驟如下：在當(dāng)代群體中，使用解碼后設(shè)計(jì)變量的適應(yīng)度函數(shù)值評(píng)價(jià)該代中的每個(gè)染色體，按照適值的概率分布

4、選擇新群體，然后，通過(guò)變異和雜交算子改變新群體中的染色體。如果在經(jīng)過(guò)若干代后，觀察不到更進(jìn)一步的改進(jìn)，最好染色體就作為一個(gè)可能的全局最優(yōu)解。通常根據(jù)工程實(shí)際問(wèn)題及計(jì)算速度和資源情況確定一固定代數(shù)，在循環(huán)結(jié)束后停止計(jì)算。這一過(guò)程可用圖11.13表示。11.1.2 遺傳算法的一些基本操作1. 編碼和解碼 從設(shè)計(jì)空間向遺傳空間（由染色體個(gè)體組成）的映射稱為編碼，反之稱為解碼。對(duì)于一個(gè)實(shí)際待優(yōu)化問(wèn)題，首先要將根據(jù)具體問(wèn)題確定的一組尋優(yōu)參數(shù)即設(shè)計(jì)向量X表示為適合于遺傳算法操作的二進(jìn)制碼串，即染色體。例如，欲求一個(gè)有n個(gè)設(shè)計(jì)變量的函數(shù)(X)= (x1, ···,xn)的最大值

5、。事先需確定每個(gè)參數(shù)的變化范圍，設(shè)參數(shù)xi的變化范圍為ximin, ximax，即設(shè)計(jì)變量xi為域Di=ai，biximin， ximaxR內(nèi)的一個(gè)值，也就是對(duì)所有xiDi, (x1, ···,xn)>0。假定以某個(gè)要求的精度來(lái)優(yōu)化函數(shù)：這里取設(shè)計(jì)變量小數(shù)點(diǎn)后第6位。顯然，為達(dá)到這樣的精度，每個(gè)域Di應(yīng)該被分割成 (bi ai)106份等長(zhǎng)度的區(qū)間。令mi表示使 (bi ai)1062mi1成立的最小整數(shù)，則對(duì)每個(gè)變量，由串長(zhǎng)為mi的二進(jìn)制編碼表達(dá)能滿足精度要求。因此，公式xi = ai + decimal (substringi) · （i=1,

6、2,3, ···,n ） （11.5.1）對(duì)應(yīng)于每一二進(jìn)制串substringi的設(shè)計(jì)變量的十進(jìn)制值。式中，decimal (substringi)表示二進(jìn)制串的十進(jìn)制值。設(shè)計(jì)變量的編碼精度為Ai （11.5.2）由上式可見(jiàn)，mi長(zhǎng)則編碼精度高，但是遺傳算法的復(fù)雜性增加。顯然，設(shè)計(jì)變量的碼串長(zhǎng)度mi不僅與計(jì)算精度有關(guān)，還與其變化范圍有關(guān)。各設(shè)計(jì)變量可以根據(jù)實(shí)際工程需要取不同的計(jì)算精度。 最后，將所有表示設(shè)計(jì)變量的二進(jìn)制碼串接起來(lái)組成一個(gè)長(zhǎng)的總二進(jìn)制碼串，構(gòu)成染色體v，它就是遺傳算法可以操作的對(duì)象。這樣，代表一個(gè)潛在解的染色體二進(jìn)制串總長(zhǎng)度為m=，前m1位對(duì)應(yīng)區(qū)間a

7、1，b1中的一個(gè)值x1，隨后的m2位對(duì)應(yīng)區(qū)間a2，b2中的一個(gè)值x2，······ ，最后的mk位對(duì)應(yīng)區(qū)間ak，bk中的一個(gè)值xk。2. 初始群體的產(chǎn)生這里要解決兩個(gè)問(wèn)題，即群體規(guī)模popsize和初始群體的產(chǎn)生。群體規(guī)模越大，GA所處理的模式越多，陷入局部解的可能性越小，即不易陷入未成熟收斂。但規(guī)模過(guò)大會(huì)大大增加計(jì)算量，影響算法效率。實(shí)際應(yīng)用時(shí)需要根據(jù)具體問(wèn)題來(lái)確定。至于初始群體確定方法一種是完全隨機(jī)的方法，如用擲硬幣的方法，正面表示1，反面表示0，不斷擲，直至產(chǎn)生popsize個(gè)染色體。若對(duì)所求解的問(wèn)題具有某些最優(yōu)分布的先驗(yàn)知識(shí)，

8、可首先將這些先驗(yàn)知識(shí)轉(zhuǎn)變?yōu)楸仨殱M足的一組要求，在滿足這些要求的前提下隨機(jī)地選取樣本。例如，若知最優(yōu)解在問(wèn)題空間中的分布范圍，可在此范圍內(nèi)選初始群體。3. 染色體的評(píng)價(jià)染色體的好壞通過(guò)其適值大小來(lái)評(píng)價(jià)，所以，適應(yīng)度函數(shù)是評(píng)價(jià)各群體或個(gè)體是否優(yōu)化、先進(jìn)的準(zhǔn)則，或者說(shuō)適應(yīng)度函數(shù)具有測(cè)定染色體對(duì)目標(biāo)的適應(yīng)性的作用。例如，對(duì)于機(jī)構(gòu)參數(shù)優(yōu)化問(wèn)題，可以直接將目標(biāo)函數(shù)作為適應(yīng)度函數(shù)。因此，簡(jiǎn)單的適應(yīng)度函數(shù)可以用一個(gè)公式來(lái)表示，如誤差平方積分、二次型性能指標(biāo)等。對(duì)于復(fù)雜系統(tǒng)，可能要對(duì)系統(tǒng)仿真，由多個(gè)目標(biāo)值來(lái)判斷；或者要通過(guò)一系列規(guī)則要求，經(jīng)過(guò)多個(gè)步驟才能求得適值，而不能用公式來(lái)表達(dá)。遺傳算法討論的問(wèn)題一般都是適

9、值為正且求最大值問(wèn)題。若目標(biāo)函數(shù)可能為負(fù)，則可通過(guò)加法機(jī)制來(lái)調(diào)整，即加入某個(gè)適當(dāng)大的正常數(shù)C(計(jì)算時(shí)取群體中的最大適值或某一足夠大的數(shù))使之為正，也就是問(wèn)題轉(zhuǎn)化為max(X) max(X)+C如果優(yōu)化問(wèn)題是求函數(shù)的最小值，它等同于求函數(shù)g的最大值，其中g(shù) = ，即 min( X) = max g(X) = max (X) （11.5.3）4. 遺傳操作遺傳操作是遺傳算法的核心，其重要特點(diǎn)是有向隨機(jī)的。操作的效果與效率取決于編碼的方式、群體規(guī)模、初始種群、適應(yīng)度函數(shù)及各個(gè)遺傳操作概率。（1）選擇復(fù)制。選擇復(fù)制操作的目的是選出群體中優(yōu)質(zhì)（如適值高）的個(gè)體，淘汰劣質(zhì)個(gè)體，并使優(yōu)質(zhì)個(gè)體直接遺傳或得以配

10、對(duì)雜交。對(duì)基于適值的概率分布選擇新群體的過(guò)程，稱為正比選擇或輪盤(pán)選擇，其基本思想是每個(gè)染色體的選擇概率（即生存概率）正比于它的適值。通常，使用一個(gè)按照如下方法構(gòu)造的一個(gè)輪盤(pán)：l 計(jì)算每個(gè)染色體vi的適應(yīng)值eval(vi) (i=1,2，···, popsize)。l 計(jì)算群體的總適值F = （11.5.4）l 計(jì)算每個(gè)染色體vi的選擇概率（生存概率）pi，pi = eval(vi)/F (i=1, ···, popsize) （11.5.5）l 計(jì)算每個(gè)vi染色體的累積概率qi，（區(qū)間大?。﹒i = (i=1, ··

11、;·, popsize) （11.5.6）對(duì)輪盤(pán)轉(zhuǎn)動(dòng)popsize次，每次按照下面的方法為新群體選擇一個(gè)單個(gè)的染色體：產(chǎn)生一個(gè)在區(qū)間0，1里的隨機(jī)數(shù)r，如果r<q1，選擇第一個(gè)染色體v1加入新群體，否則選擇使qi-1<rqi成立的第i個(gè)染色體vi(2ipopsize) 加入新群體。很明顯，適值高的染色體將被選擇一次以上。這是符合遺傳算法的模式定理的：最好染色體得到多個(gè)拷貝，中等染色體保持平穩(wěn)，最差染色體死亡。復(fù)制操作對(duì)盡快收斂到優(yōu)化解具有很大影響，但它不能產(chǎn)生新的模式結(jié)構(gòu)，而是使高于平均適值的模式數(shù)量增長(zhǎng)很快。(2)雜交操作。雜交操作是兩個(gè)父母代的結(jié)構(gòu)特征結(jié)合生成兩個(gè)子代

12、個(gè)體。雜交過(guò)程在染色體碼串之間是有組織的又是隨機(jī)的（雜交點(diǎn)及誰(shuí)與誰(shuí)配對(duì)等均是隨機(jī)的），它能創(chuàng)建新的結(jié)構(gòu)模式，同時(shí)又是最低限度地破壞復(fù)制過(guò)程所選擇的高適值模式，這樣就會(huì)使群體搜索空間加大，使子代個(gè)體更具多樣性。如在復(fù)制操作中，若群體中有一個(gè)相對(duì)其他個(gè)體適值較好的個(gè)體，復(fù)制將促使它不斷延續(xù)下去，即使該個(gè)體在整個(gè)搜索空間仍是較平庸的，這將導(dǎo)致群體趨向，雜交操作會(huì)打破這樣的局面。雜交操作是產(chǎn)生新個(gè)體的最重要的操作。雜交是遺傳算法的一個(gè)重要的重組算子，雜交概率pc是算法的一個(gè)參數(shù)，此概率給出預(yù)計(jì)要進(jìn)行雜交的個(gè)數(shù)為pc· popsize。雜交操作按下面方法處理，對(duì)新群體中的每個(gè)染色體l 依次產(chǎn)生

13、一個(gè)在區(qū)間0，1里的隨機(jī)數(shù)r。l 如果r < pc，選擇給定的染色體進(jìn)行雜交。在選完進(jìn)行雜交的染色體后，隨機(jī)地對(duì)被選定的染色體進(jìn)行配對(duì)。如選擇的染色體數(shù)是偶數(shù)，可以很容易地配對(duì)。如果選擇的染色體數(shù)為奇數(shù)，可以加入一額外的染色體或者移走一被選出的染色體，這種選擇同樣是隨機(jī)的。對(duì)染色體對(duì)中的每一對(duì)，產(chǎn)生一個(gè)在區(qū)間1，m-1（m為總長(zhǎng)染色體的位數(shù)）里的隨機(jī)整數(shù)pos。數(shù)pos表示雜交點(diǎn)的位置。如兩個(gè)配對(duì)染色體(b1b2···bposbpos+1···bm)和(c1c2···cposcpos+1·

14、··cm)則雜交操作后它們的子代為(b1b2···bposcpos+1···cm)和(c1c2···bposbpos+1···bm)并且被子代所替換。例如，對(duì)于如下兩個(gè)染色體，若隨機(jī)斷點(diǎn)選在第17個(gè)基因之后， 交換雙親上斷點(diǎn)的右端后得到的兩個(gè)后代為 0 0000101001000 (3)變異操作。變異也是一個(gè)重要的遺傳算子，是在一位一位(bit-by-bit)基礎(chǔ)上執(zhí)行的。設(shè)變異率pm，它是遺傳算法另一個(gè)參數(shù)，則可以預(yù)計(jì)的變異位數(shù)為pm· pop

15、size。因此變異以等于變異率的概率改變一個(gè)或若干個(gè)基因。整個(gè)群體中所有染色體中的每一位都有均等的機(jī)會(huì)經(jīng)歷變異。變異操作是產(chǎn)生新個(gè)體的輔助方法。常用的基于二進(jìn)制編碼的基本變異操作過(guò)程是對(duì)群體中個(gè)體隨機(jī)選定基因位，并按概率pm 將這些基因位上的值取反，即從0變?yōu)?或者相反。若變異概率pm不是固定的，而是隨群體中個(gè)體多樣性程度進(jìn)行調(diào)整，就是自適應(yīng)變異操作。變異操作的目的可使GA保持群體多樣性，防止丟失一些有用的遺傳模式。當(dāng)然它也可能破壞有用的模式，因此pm通常取得很小。為了使群體具有多樣性，同時(shí)又能較快收斂，可以開(kāi)始時(shí)將popsize取得大一些，在一代代遺傳操作過(guò)程中不斷丟掉一些顯然較差的個(gè)體。變

16、異操作按如下方法處理，對(duì)于每個(gè)位l 產(chǎn)生在區(qū)間里0，1的一隨機(jī)數(shù)r。l 如果r < pm，變異此位。例如，假設(shè)染色體v的第18個(gè)基因被選來(lái)變異，該基因?yàn)?，故將其變?yōu)?。于是變異后染色體為 v = 100110110100101101 000000010111001 v= 100110110100101100 000000010111001 11.1.3 遺傳算法計(jì)算步驟在初始群體確定后，隨著選擇、雜交和變異等遺傳操作的完成，新群體就為下一次的評(píng)價(jià)作好了準(zhǔn)備。評(píng)價(jià)的目的是用來(lái)為下一選擇過(guò)程建立概率分布 ，即建立一個(gè)根據(jù)當(dāng)前適值構(gòu)造的輪盤(pán)。算法的其余部分只是上述步驟的循環(huán)重復(fù)。遺傳算法整個(gè)

17、流程框圖如圖11.14所示。 輸入?yún)?shù)：Generation=0，T，Popsize，n，pc，pm 輸入邊界： (ai,bi) i=1,2,n初始群體產(chǎn)生（共Popsize個(gè)染色體）初始群體評(píng)價(jià)，并保存最好的染色體For Generation=1 To T（循環(huán)T代） 選擇操作雜交操作變異操作新群體中各染色體評(píng)價(jià)最優(yōu)個(gè)體保存操作輸出最優(yōu)解圖11.14 遺傳算法框圖下面以參考文獻(xiàn)32中的一例來(lái)說(shuō)明遺傳算法的上述整個(gè)過(guò)程。模擬最優(yōu)化問(wèn)題：無(wú)約束優(yōu)化 max (x1，x2)=21.5 + x1 sin(4 x1) + x2 sin(20 x2) 3.0 x1 12.14.1 x2 5.8目標(biāo)函數(shù)的

18、三維圖形如圖11.15所示。設(shè)定群體規(guī)模popsize=10，遺傳算子的概率pc=0.25和pm=0.01。f(x1,x2)x2x1圖11.15優(yōu)化目標(biāo)函數(shù)1. 編碼和解碼首先，將決策變量編碼為二進(jìn)制串。假設(shè)x1和x2需要的精度都要精確到小數(shù)點(diǎn)后4位，xj的值域是aj，bj ，則xj 所需要的二進(jìn)制編碼子串長(zhǎng)mj 滿足式 并且可按式作解碼計(jì)算。decimal(substringj)表示變量xj的子串 substringj的十進(jìn)制值。因此，兩個(gè)變量需要的總串長(zhǎng)按下述計(jì)算：變量x1的定義域區(qū)間3.0，12.1應(yīng)該至少被分成等距區(qū)間數(shù)為(12.1 ( 3.0) ×10000=151000

19、又因?yàn)?17 <151000 218 ，所以染色體的第一部分需要位數(shù) m1=18。同理，對(duì)于變量x2 ，精度要求自變量域長(zhǎng)度區(qū)間應(yīng)該至少被等分成(5.8 4.1) ×10000=17000因214 <17000 215，即染色體的第二部分需要位數(shù)m2=15。所以，染色體的總長(zhǎng)度（基因數(shù)目）m= m1 +m2=33即前18位表示x1，后15位表示x2。如一染色體v可表示如下：x215位位x118位 v = 對(duì)應(yīng)的變量x1和x2的十進(jìn)制碼為x170352，x231960 而十進(jìn)制值分別為 x1 3.0+70352×(12.1 ( 3.0) / ( 218 1) =1

20、.0524 x2 4.1+31960×(5.8 4.1) / (215 1) =5.7553即對(duì)應(yīng)于X=x1，x2=1.0524，5.7553。該染色體的適值為 (1.0524,5.7553) =20.252640。2. 初始種群每一染色體中的33位都是隨機(jī)初始化的，假定經(jīng)過(guò)初始化過(guò)程后，隨機(jī)產(chǎn)生的初始種群為 v1= v2= 001110101110011000 000010101001000 v30 v4= 100110110100101101 000000010111001 v5= 000010111101100010 001110001101000 v6= 1111101010

21、11011000 000010110011001 v7= 110100010011111000 100110011101101 v8= 001011010100001100 010110011001100 v9= 111110001011101100 011101000111101 v10= 111101001110101010 000010101101010 3. 評(píng)估計(jì)算染色體適值的過(guò)程由以下三步構(gòu)成：步驟1：將染色體vk的基因型轉(zhuǎn)換為表現(xiàn)型，即將二進(jìn)制串解碼轉(zhuǎn)換為十進(jìn)制：Xk = (x,x)，k=1,2,3, ···,popsize。 上述初始種群解碼后對(duì)應(yīng)

22、的十進(jìn)制為 v1= x1，x2 = -2.687969，5.361653 v2= x1，x2= 0.474101，4.170144 v3= x1，x2 = 10.419457，4.661461 v4= x1，x2 = 6.159951，4.109598 v5= x1，x2 = -2.301286，4.477282 v6= x1，x2 = 11.788084，4.174346 v7= x1，x2 = 9.342067，5.121702 v8= x1，x2 = -0.330256，4.694977 v9= x1，x2 = 11.671267，4.873501 v10= x1，x2 = 11.446

23、273，4.171908步驟2：計(jì)算目標(biāo)函數(shù)值(Xk)。步驟3：將目標(biāo)函數(shù)轉(zhuǎn)換為適值。這里，簡(jiǎn)單地取目標(biāo)函數(shù)值為適值：eval(vk) = (Xk)，k=1,2,3,popsize 。對(duì)上述每個(gè)染色體計(jì)算解碼后(x1，x2)的目標(biāo)函數(shù)值，得各染色體的適值為 eval(v1)= (2.687969，5.361653)=19.805119 eval(v2)= (0.474101，4.170144)=17.370896 eval(v3)= (10.419457，4.661461)=9.590546 eval(v4)= (6.159951，4.109598)=29.406122 eval(v5)= (

24、2.301286，4.477282)=15.686091 eval(v6)= (11.788084，4.174346)=11.900541 eval(v7)= (9.342067，5.121702)=17.958717 eval(v8)= (0.330256，4.694977)=19.763190 eval(v9)= (11.671267，4.873501)=26.401669 eval(v10)= (11.446273，4.171908)=10.252480顯然，染色體 v4 是最好的，而染色體v3是最差的。4. 選擇采用轉(zhuǎn)輪法作為選擇方法，根據(jù)與適值成正比的概率選出新的種群。轉(zhuǎn)輪法由以下幾

25、步構(gòu)成:(1) 計(jì)算種群中所有染色體的適值的和， =178.135372(2) 對(duì)各個(gè)染色體vk ，計(jì)算選擇概率pk。p1=0.111180，p2=0.097515， p3=0.053839， p4=0.165077，p5=0.088057p6=0.066806，p7=0.100815， p8=0.110945，p9=0.148211， p10=0.057554(3) 對(duì)各個(gè)染色體vk ，計(jì)算累積概率qk。 q1= 0.111180，q2=0.208695， q3= 0.262534，q4= 0.427611，q5= 0.515668q6= 0.582475，q7= 0.683290，q8=

26、0.794234，q9= 0.942446，q10=1.000000 現(xiàn)在，準(zhǔn)備轉(zhuǎn)動(dòng)輪盤(pán)10次，每次按如下方式選出一個(gè)染色體來(lái)構(gòu)造新的種群:步驟 1：在0，1區(qū)間產(chǎn)生一個(gè)均勻分布的偽隨機(jī)數(shù)r 。步驟2：若r q1 ，則選第一個(gè)染色體v1 ；否則，選擇第k個(gè)染色體vk (2 k 10)，使得qk-1 < r qk成立。設(shè)產(chǎn)生的0，1間的10個(gè)隨機(jī)數(shù)序?yàn)?.301431，0.322062，0.766503，0.881893，0.3508710.583392，0.177618，0.343242，0.032685，0.197577第一個(gè)數(shù)r1=0.301431大于q3 小于q4，這表示染色體v4

27、 被選來(lái)構(gòu)造新種群；第二個(gè)數(shù) r2=0.322062也大于q3 小于q4 ，表示染色體v4 再次被新種群選中，重復(fù)以上操作，最后選出了新的種群 v= 100110110100101101 000000010111001 v4 v= 100110110100101101 000000010111001 v4 v= 001011010100001100 010110011001100 v8 v= 111110001011101100 011101000111101 v9 v= 100110110100101101 000000010111001 v4 v= 110100010011111000 1

28、00110011101101 v7 v= 001110101110011000 0000101001000 v2 v= 100110110100101101 000000010111001 v4 v= v1 v= 001110101110011000 000010101001000 v25. 雜交因設(shè)雜交率pc=0.25 ，即平均有25%染色體將經(jīng)歷雜交。雜交按照下面的方法進(jìn)行：先對(duì)新群體中的每個(gè)染色體，產(chǎn)生區(qū)間0，1里的一個(gè)隨機(jī)數(shù)r，如果r<0.25，則選擇給定的染色體進(jìn)行雜交。假定隨機(jī)數(shù)序列為0.625721，0.266823，0.288644，0.295114，0.1632740.

29、567461，0.085940，0.392865，0.770714，0.548656于是染色體v5和v7被選入?yún)⒓与s交。再對(duì)配對(duì)的染色體產(chǎn)生一個(gè)隨機(jī)的整數(shù)pos作為斷點(diǎn)，pos1，32 (因?yàn)?3是染色體的長(zhǎng)度)。假設(shè)產(chǎn)生的pop=1，兩染色體自第1位后切斷，并交換斷點(diǎn)右端，得 v5= 100110110100101101 000000010111001 v7= 001110101110011000 0000101001000 v5= 101110101110011000 0000101001000 v7= 000110110100101101 000000010111001 6. 變異因設(shè)變

30、異率pm=0.01，即種群中平均有1%基因發(fā)生變異，而種群中共有m · popsize=33×10=330個(gè)基因，所以，可以預(yù)計(jì)每代平均有3.3個(gè)基因發(fā)生變異。為使每個(gè)基因有均等的機(jī)會(huì)發(fā)生變異，需要對(duì)群體中的每一基因位產(chǎn)生區(qū)間0，1內(nèi)均勻分布的隨機(jī)數(shù)序列rk (k=1,2,3,330)。如果rk<0.01，則變異此位。在運(yùn)行例子中，總共產(chǎn)生4個(gè)小于0.01的數(shù)，變異位關(guān)系和產(chǎn)生的隨機(jī)數(shù)如表11.2所示。這就意味著將有4個(gè)染色體通過(guò)變異而改變。表11.2 變異操作位址染色體號(hào)位號(hào)隨機(jī)數(shù)105164199329457106321320.0098570.0031130.00

31、09460.001282變異后的新種群為 v= 100110110100101101 000000010111001 v= 100110110100101101 000000010111001 v= 001011010100001100 010110011001100 v= 111111001011101100 011101000111101 v= 101110101110011000 000010101001010 v= 110100010011111000 100110011101101 v= 100110110100101101 000000010111001 v= 1001101101

32、00101101 000000010111001 v= v= 001110101110011000 000010101001010 至此，完成了遺傳算法循環(huán)過(guò)程的一次迭代（即一代）。檢查新群體，對(duì)每個(gè)染色體進(jìn)行解碼，并計(jì)算解碼后的適應(yīng)函數(shù)值，得 eval(v)= (6.159951，4.109598)=29.406122 eval(v)= (6.159951，4.109598)= 29.406122 eval(v)= (-0.330256，4.694977)=19.763190 eval(v)= (11.907206，4.873501)=5.702781 eval(v)= (8.024130，

33、4.170248)=19.91025 eval(v)= (9.342067，5.121702)=17.958717 eval(v)= (6.159951，4.109598)=29.406122 eval(v)= (6.159951，4.109598)=29.406122 eval(v)= (-2.687969，5.361653)=19.805119 eval(v)= (0.474101，4.170248)=17.370896注意：新群體的總適值F為218.1354，高于先前群體的總適值178.1353，但在這一輪中，最好染色體的適值還未發(fā)生變化。重復(fù)上述迭代，并跟蹤進(jìn)化過(guò)程中的最好個(gè)體：在遺傳

34、算法的實(shí)現(xiàn)中，通常在一獨(dú)立出來(lái)的位置保存“曾經(jīng)最好”個(gè)體。采用這種方法（稱為精華模型），算法將報(bào)告整個(gè)過(guò)程的最好值，而不只是最終群體的最好值。實(shí)驗(yàn)運(yùn)行在1000代后結(jié)束，在第419代就得到了最佳的染色體 v*對(duì)應(yīng)的設(shè)計(jì)變量 x=11.631407， x=5.724824適值 eval(v*)=(11.631407，5.724824)=38.818208目標(biāo)函數(shù)值 (X*)=38.81820811.1.4 遺傳算法在機(jī)構(gòu)參數(shù)優(yōu)化中的應(yīng)用機(jī)構(gòu)參數(shù)優(yōu)化屬于非線性約束優(yōu)化問(wèn)題，最大特點(diǎn)是問(wèn)題的非線性及多峰性，并且其目標(biāo)函數(shù)復(fù)雜，采用傳統(tǒng)的算法往往搜索不到全局最優(yōu)解。遺傳算法是有效的解決方法之一，它不要

35、求目標(biāo)函數(shù)和約束是可微的，計(jì)算效率比較高，搜索結(jié)果的最好個(gè)體在概率意義上代表了全局最優(yōu)解。因此，這一算法在機(jī)構(gòu)設(shè)計(jì)領(lǐng)域逐漸得到了應(yīng)用。但由于機(jī)構(gòu)設(shè)計(jì)的特殊性，需對(duì)算法的具體操作作一些適當(dāng)?shù)母倪M(jìn)。1. 編碼 遺傳算法用于機(jī)構(gòu)參數(shù)優(yōu)化數(shù)學(xué)模型的求解時(shí)，算法中的染色體即為設(shè)計(jì)向量X。目前常見(jiàn)的編碼方式有兩種，一是二進(jìn)制方法，前面已經(jīng)提到；二是浮碼（實(shí)數(shù)編碼）方法，即求解過(guò)程直接采用實(shí)數(shù)表達(dá)，每個(gè)染色體編碼為一個(gè)與解向量維數(shù)相同的實(shí)向量，每個(gè)設(shè)計(jì)參數(shù)xi即作為一個(gè)基因。這樣可以避免染色體評(píng)價(jià)過(guò)程中的二進(jìn)制編碼和解碼過(guò)程，提高算法的運(yùn)行效率。所以，機(jī)構(gòu)設(shè)計(jì)中經(jīng)常采用浮碼方法。但此時(shí)算法中的雜交和變異操作

36、與前所說(shuō)的有很大不同。2. 約束條件處理約束條件處理是用GA求解機(jī)構(gòu)約束優(yōu)化設(shè)計(jì)的關(guān)鍵。目前，遺傳算法對(duì)于違反約束的處理主要有四種33。死亡懲罰策略對(duì)于一些很難通過(guò)一般遺傳因子產(chǎn)生可行解的問(wèn)題，算法耗費(fèi)大量的機(jī)時(shí)去評(píng)價(jià)非法個(gè)體；修復(fù)策略用特殊的修補(bǔ)算法來(lái)校正所有產(chǎn)生的不可行解，只對(duì)特定問(wèn)題而言，同樣耗費(fèi)大量的計(jì)算；改進(jìn)遺傳算子策略通過(guò)設(shè)計(jì)專門(mén)的遺傳算子來(lái)維持染色體的可行性。上述三種策略無(wú)法考慮可行域外的點(diǎn)，故有第四種也是常見(jiàn)的懲罰策略。懲罰策略類似于傳統(tǒng)的優(yōu)化方法中的懲罰函數(shù)法。群體中個(gè)體的優(yōu)劣也就是個(gè)體適值一般用目標(biāo)函數(shù)（X）來(lái)評(píng)價(jià)，但對(duì)于有非線性約束條件的數(shù)值優(yōu)化問(wèn)題，考慮采用懲罰策略，所

37、以需把懲罰與目標(biāo)函數(shù)聯(lián)系起來(lái)重新構(gòu)造適值評(píng)價(jià)函數(shù)。目前，這樣的適值函數(shù)有許多種形式，常用的為 （11.5.7） （11.5.8） 式中，p(X)為自適應(yīng)的懲罰函數(shù)；為用來(lái)調(diào)節(jié)懲罰程度的參數(shù)； 為染色體X對(duì)第i個(gè)約束的違反量；為當(dāng)前群體中對(duì)第i個(gè)約束的最大違反量。懲罰函數(shù)的設(shè)計(jì)各有不同。違反程度越大，懲罰越重。這樣，類似于傳統(tǒng)優(yōu)化的懲罰函數(shù)法，通過(guò)懲罰不可行解將約束問(wèn)題轉(zhuǎn)化為無(wú)約束問(wèn)題來(lái)處理。因此，懲罰策略允許在每代的群體中保持部分不可行解，使遺傳搜索可以從可行域和不可行域兩側(cè)達(dá)到最優(yōu)解。其中，合理的懲罰因子取值是非常困難的，與討論的問(wèn)題有關(guān)，一般通過(guò)試驗(yàn)獲得。有時(shí)調(diào)整不好，一些不滿足約束的個(gè)體

38、適值比滿足約束的其他個(gè)體適值還好，以致搜索到可行域外。有特色的是Powell33等提出附加的懲罰項(xiàng)，對(duì)不可行個(gè)體增加懲罰，使它們的適值不好于可行個(gè)體中最差值。對(duì)于機(jī)構(gòu)設(shè)計(jì)，往往在約束界面上取得最優(yōu)點(diǎn)，這樣處理任何不可行個(gè)體會(huì)丟失很多有用信息。參考文獻(xiàn)35、36也針對(duì)這一問(wèn)題給出了一種算法。上述約束處理主要針對(duì)不等式性能約束條件。但是性能約束中有一類特殊的機(jī)構(gòu)存在約束條件，如不滿足表示機(jī)構(gòu)不成立，以致目標(biāo)函數(shù)(X)本身無(wú)法計(jì)算，例如對(duì)于曲柄搖桿機(jī)構(gòu)設(shè)計(jì)，機(jī)構(gòu)成立條件可表示為對(duì)于曲柄任意轉(zhuǎn)角，在機(jī)構(gòu)運(yùn)動(dòng)計(jì)算中有關(guān)式的根號(hào)內(nèi)的值必須大于零。因此，對(duì)于不滿足機(jī)構(gòu)存在約束條件的染色體，因機(jī)構(gòu)不存在，故只

39、能采用拒絕策略，即重新產(chǎn)生新的染色體取代之。此外，對(duì)于等式約束，解決方案是降維法，使設(shè)計(jì)變量X 的維數(shù)降低，并且消去等式約束，可以簡(jiǎn)化優(yōu)化時(shí)約束條件的處理。對(duì)于不等式邊界約束，采用浮碼時(shí)可通過(guò)選擇雜交和變異方法來(lái)解決。3. 雜交 設(shè)初始群體中各染色體依據(jù)設(shè)計(jì)參數(shù)的邊界約束隨機(jī)產(chǎn)生，即取染色體X的基因?yàn)?（11.5.9）其中，隨機(jī)函數(shù)rand()取區(qū)間0，1內(nèi)的隨機(jī)數(shù)。顯然，這樣產(chǎn)生的染色體均滿足邊界約束條件。那么遺傳進(jìn)化操作時(shí)，可以采用算術(shù)雜交算子，使產(chǎn)生的后代仍滿足邊界約束條件。如采用算術(shù)雜交，設(shè)父代染色體為X1、X2，則雜交后產(chǎn)生的子代染色體為（11.5.10）式中，是（0，1）內(nèi)的隨機(jī)數(shù)

40、。這種雜交是凸雜交，其特點(diǎn)是如父代 X1、X2 均屬于凸集，則子代 也均屬于該凸集。由于邊界約束是凸集，所以雜交結(jié)果仍滿足邊界約束。4. 變異同理，在用上述方法產(chǎn)生初始群體后，若變異采用非均勻變異算子，那么對(duì)于選定的父代X，如其基因x k被選作變異，則生成的后代為 其中 隨機(jī)地按如下兩種可能的機(jī)會(huì)變換 ， 如隨機(jī)數(shù)為 0 ， 如隨機(jī)數(shù)為 1 （11.5.11）式中， 分別為x k的上下界。這種變異的特點(diǎn)是如父代在上下界域內(nèi)，則變異產(chǎn)生的后代也在該域內(nèi)?？梢?jiàn)，只要雜交和變異前父代是滿足邊界約束的，因邊界約束形成的空間是凸集，故通過(guò)上述所采用的雜交和變異算子產(chǎn)生的后代也必然滿足邊界約束。因此，在遺

41、傳算法中，如初始群體在設(shè)計(jì)參數(shù)的上下邊界范圍內(nèi)產(chǎn)生，經(jīng)上述所采用的遺傳算子可保證產(chǎn)生的后代仍滿足邊界約束，這樣處理把邊界約束從約束中分離了出來(lái)，使整個(gè)搜索過(guò)程中可以不考慮邊界約束而只需懲罰不滿足性能約束的染色體即可，從而在懲罰函數(shù)中消去了邊界約束的影響，少去了邊界約束引起的懲罰，使懲罰函數(shù)更為簡(jiǎn)單，并可以提高優(yōu)化計(jì)算效率。11.1.5 應(yīng)用實(shí)例劍桿織機(jī)引緯機(jī)構(gòu)參數(shù)優(yōu)化設(shè)計(jì)圖11.16所示為劍桿織機(jī)的引緯機(jī)構(gòu)簡(jiǎn)圖，它是平面四桿機(jī)構(gòu)、空間RSSR機(jī)構(gòu)和平面定軸內(nèi)嚙合齒輪機(jī)構(gòu)串聯(lián)而成的組合機(jī)構(gòu)。其工作原理是主動(dòng)曲柄AB以角速度順時(shí)針?lè)较蚧剞D(zhuǎn)，通過(guò)六桿組合機(jī)構(gòu)使扇形齒輪r5往復(fù)擺動(dòng)，從而驅(qū)動(dòng)劍輪使劍頭作往復(fù)直線移動(dòng)，實(shí)現(xiàn)引緯運(yùn)動(dòng)。引緯規(guī)律即劍頭運(yùn)動(dòng)規(guī)律對(duì)于引緯機(jī)構(gòu)功能的實(shí)現(xiàn)是至關(guān)重要的，引緯機(jī)構(gòu)的設(shè)計(jì)主要是實(shí)現(xiàn)織造工藝所要求的引緯規(guī)律。該機(jī)構(gòu)的引緯規(guī)律是由兩連桿機(jī)構(gòu)的尺寸所確定的。因連桿機(jī)構(gòu)的特性限制，引緯規(guī)律不能隨意設(shè)計(jì)，但是，改變連桿機(jī)構(gòu)的尺寸設(shè)計(jì)，可以獲得滿足要求的劍頭運(yùn)動(dòng)規(guī)律。但是按常規(guī)的設(shè)計(jì)方法，這是非常困難的，所以，必須采用參數(shù)優(yōu)化的設(shè)計(jì)方法。圖11.16 劍桿織機(jī)引緯機(jī)構(gòu)簡(jiǎn)圖首先確定該機(jī)構(gòu)結(jié)構(gòu)參數(shù)與劍桿頭運(yùn)動(dòng)規(guī)律的關(guān)系，可按如下方法計(jì)算：對(duì)于平面四桿