利用遺傳算法求解函數(shù)的最大值

1、利用遺傳算法求解函數(shù)的最大值蔣賽 趙玉芹1 遺傳算法的基本原理遺傳算法是模擬生物遺傳學(xué)和自然選擇機理，通過人工方式構(gòu)造的一類優(yōu)化搜索算法，是對生物進(jìn)化過程進(jìn)行的一種數(shù)學(xué)仿真，是進(jìn)化計算的一種重要形式。遺傳算法與傳統(tǒng)數(shù)學(xué)模型截然不同，它為那些難以找到傳統(tǒng)數(shù)學(xué)模型的難題找出了一個解決方法。同時，遺傳算法借鑒了生物科學(xué)中的某些知識，從而體現(xiàn)了人工智能的這一交叉學(xué)科的特點。遺傳算法是一種通用的優(yōu)化算法，其編碼技術(shù)和遺傳操作比較簡單，優(yōu)化不受限制條件的約束，不需要有先驗條件。其搜索過程是從問題解的一個隨機產(chǎn)生的集合開始的，而不是從單個個體開始的，具有隱含并行搜索特性，也就大大減少可陷入局部極小值的可能。

2、在解決可能在求解過程中產(chǎn)生組合爆炸的問題時會產(chǎn)生很好的效果。遺傳算法需選擇一種合適的編碼方式表示解, 并選擇一種評價函數(shù)用來每個解的適應(yīng)值, 適應(yīng)值高的解更容易被選中并進(jìn)行交叉和變異, 然后產(chǎn)生新的子代。選擇、交叉和變異的過程一直循環(huán) , 直到求得滿意解或滿足其他終止條件為止。算法的運行過程具有很強的指向性, 適合眾多復(fù)雜問題的求解。具體操作步驟如下：1）初始化種群；2）計算種群上每個個體的適應(yīng)度值；3）按由個體適應(yīng)度值所決定的某個規(guī)則選擇將進(jìn)入下一代的個體4）按概率PC進(jìn)行交叉操作5）按概率PC進(jìn)行變異操作6）若沒有滿足某種停止條件，則轉(zhuǎn)步驟2），否則進(jìn)入下一步；7）輸入種群中適應(yīng)度值最優(yōu)的

3、染色體作為問題的滿足解或最優(yōu)解本例運用遺傳算法求解函數(shù)優(yōu)化的問題2 遺傳求解舉例（Rosenbrock函數(shù)的全局最大值計算）2.0 求解函數(shù)介紹 函數(shù)f(x1,x2) = 100 (x21-x2)2 + (1-x2)2是非凸函數(shù)，又稱Rosenbrock函數(shù)，是由De Jong提出的，現(xiàn)已成為測試遺傳算法的標(biāo)準(zhǔn)函數(shù)。該函數(shù)在極小值附近沿曲線x2=x12有陡峭的峽谷，很容易陷入局部極小，它的全局最小點是(1，1)，最小值是0.該函數(shù)有兩個局部極大點， 分別是: f(2.048, -2.048)=3897.7342 和 (-2.048,-2.048)=3905.9262其中后者為全局最大值點。如圖

4、所示：21 算法流程圖 下面介紹求解該問題的遺傳算法的構(gòu)造過程：第一步：確定決策變量及其約束條件。 s.t. -2.048 xi 2.048 (xi=1,2)第二步：建立優(yōu)化模型。 max f(x1,x2) = 100 (x21-x2)2 + (1-x1)2第三步；確定編碼方法。 用長度為l0位的二進(jìn)制編碼串來分別表示二個決策變量x1,x2。lO位二進(jìn)制編碼串可以表示從0到1023之間的1024個不同的數(shù)，故將x1,x2的定義域離散化為1023個均等的區(qū)域，包括兩個端點在內(nèi)共有1024個不同的離散點。從離0000000000(0)到1111111111(1023)之間的二進(jìn)制編碼。再將分別表示

5、x1和x2的二個10位長的二進(jìn)制編碼串連接在一起，組成一個20位長的二進(jìn)制編碼串，它就構(gòu)成了這個函數(shù)優(yōu)化問題的染色體編碼方法。例如 X：0000110111 11011 10001 就表示一個個體的基因型。第四步：確定解碼方法。 解碼時先將20位長的二進(jìn)制編碼串切斷為二個10位長的二進(jìn)制編碼串，然后分別將它們轉(zhuǎn)換為對應(yīng)的十進(jìn)制整數(shù)代碼，分別記為y1和y2，依據(jù)前述個體編碼方法相對定義域的離散化方法可知，將代碼yi轉(zhuǎn)換為變量xi的解碼公式為：Xi= 4.096 ´ yi/1023-2.048 (i=1,2)例如，對前述個體 X： 0000110111|11011 10001 它由這樣的

6、兩個代碼所組成：y1= 55 y2 = 881經(jīng)上式的解碼處理后，得到： x1= -1.828 x2= 1.476 第五步：確定個體評價方法。由式 f(x1,x2) = 100 (x21-x2)2 + (1-x1)2 可知，Rosenbrock函數(shù)的值域總是非負(fù)的，并且優(yōu)化目標(biāo)是求函數(shù)的最大值，故這里可將個體的適應(yīng)度直接取為對應(yīng)的目標(biāo)函數(shù)值，并且不再對它作其他變換處理，即有： F(x) = f(x1,x2)第六步：設(shè)計遺傳算子。選擇運算使用比例選擇算子;(1) 選擇算子或復(fù)制算子從當(dāng)前代群體中選擇出一些比較優(yōu)良的個體，并將其復(fù)制到下一代群體中。(2) 最常用和最基本的選擇算子： 比例選擇算子。

7、(3) 比例選擇算子：指個體被選中并遺傳到下一代群體中的概率與該個體的適應(yīng)度大小成正比。(4) 執(zhí)行比例選擇的手段是輪盤選擇。輪盤法的基本精神是：個體被選中的概率取決于個體的相對適應(yīng)度： pi = fi / Sfi ( i=1,2,M ) 式中 pi個體i被選中的概率；fi個體i的適應(yīng)度； Sfi群體的累加適應(yīng)度。顯然，個體適應(yīng)度愈高，被選中的概率愈大。但是，適應(yīng)度小的個體也有可能被選中，以便增加下一代群體的多樣性。交叉運算使用單點交叉算子(1) 交叉算子作用 通過交叉，子代的基因值不同于父代。交換是遺傳算法產(chǎn)生新個體的主要手段。正是有了交換操作，群體的性態(tài)才多種多樣。(2) 最常用和最基本單

8、點交叉算子。(3) 單點交叉算子的具體計算過程如下： . 對群體中的個體進(jìn)行兩兩隨機配對。 若群體大小為M，則共有 M/2 對相互 配對的個體組。 . 每一對相互配對的個體，隨機設(shè)置某一基因座之后的位置為交叉點。若染色體的長度為l ，則共有(l-1)個可能的交叉點位置。 . 對每一對相互配對的個體，依設(shè)定的交叉概率pc在其交叉點處相互交換兩個個體的部分染色體，從而產(chǎn)生出兩個新的個體。單點交叉運算的示例如下所示:、A；10110111 00 A：10110111 11B：00011100 11 B：00011100 00交叉概率 Pc=MC/M式中 M群體中個體的數(shù)目； Mc群體中被交換個體的數(shù)

9、目。變異運算使用基本位變異算子。基本位變異算子是最簡單和最基本的變異操作算子。對于基本遺傳算法中用二進(jìn)制編碼符號串所表示的個體，若需要進(jìn)行變異操作的某一基因位上的原有基因值為0，則變異操作將該基因值變?yōu)?，反之，若原有基因值為1，則變異操作將其變?yōu)??；疚蛔儺愐蜃拥木唧w執(zhí)行過程是： . 對個體的每一個基因位，依變異概率pm指定其為變異點。 . 對每一個指定的變異點，對其基因值做取反運算或用其它等位基因值來代替從而產(chǎn)生出一個新的個體。基本位變異運算的示例如下所示：A：1010 1 01010 基本位變異 A1010 0 01010 變異點變異概率變異是針對個體的某一個或某一些基因位上的基因值執(zhí)

10、行的，因此變異概率pm也是針對基因而言，即：Pm=B(M*L)式中 B每代中變異的基因數(shù)目； M每代中群體擁有的個體數(shù)目 l個體中基因串長度。第七步：確定遺傳算法的運行參數(shù)。對于本例，設(shè)定基本遺傳算法的運行參數(shù)如下：群體大小: M80 終止代數(shù): T200交叉概率： pc0.6 變異概率： pm0.001遺傳算法迭代次數(shù)：MAXGA=333 實驗結(jié)果4總結(jié)傳統(tǒng)的搜索方法由于其應(yīng)用的局限性,在某些情況下可能搜索到局部最優(yōu)點，而不能達(dá)到全局最優(yōu)點。利用遺傳算法搜索函數(shù)最優(yōu)點的方法極大地提高了搜索全局最優(yōu)點的準(zhǔn)確性，有效地避免了組合爆炸地產(chǎn)生。因此，遺傳算法在求解復(fù)雜的優(yōu)化問題中具有廣泛的應(yīng)用前景。5 實驗難點和重點 本次實驗的重點在于三個方面，一是