遺傳算法在優化求最值中的一個應用

【摘要】 在多峰值問題中，為了避免陷入局部最優，結合Matlab作出圖像，利用遺傳算法，調整控制參數，得到全局的最優解.

【關鍵詞】 非線性規劃 多峰值問題 遺傳算法 控制參數

一#65380;遺傳算法介紹

遺傳算法是模擬生物在自然環境中的遺傳和進化過程而形成的一種適應全局優化概率搜索的算法，它能在搜索過程中自動獲取和積累有關搜索空間的知識，并適應地控制搜索過程以求得最優解. Michigan大學Holland教授根據這一規律于1975年首次提出了遺傳算法，其基本思想是力求充分模仿這一自然尋優過程的隨機性#65380;魯棒性和全局性. 這是一種新型的全局優化搜索算法，因為其直接對結構對象進行操作，不存在求導和函數連續性的限定，魯棒性強#65380;隨機性#65380;全局性適于并行處理.

世間的生物從親代繼承特性或性狀，這種生命現象就是遺傳，可以使人民種瓜得瓜，種豆得豆. 構成生物的基本結構和功能單位是細胞，細胞中含有一種微小的絲狀化合物，稱為染色體，生物的所有的信息都在這個染色體中. 遺傳信息是由基因組成的，生物的各種性狀是由其相應的基因所控制的，基因是遺傳的基本單位. 細胞通過本身具有自我復制的能力，在細胞分裂的過程中，其遺傳基因也同時復制到下一代. 從而其性狀也被復制到下一代. 經過生物學家的研究，現在人們已經知道控制并決定生物遺傳性狀的染色體主要由一種叫DNA的物質構成，低等的生物中還含有一種叫RNA的物質，他的作用和DNA有點相似. 基因就是DNA或RNA長鏈結構中占有一定位置的基本遺傳單位. 細胞在分裂的時候，遺傳物質DNA通過復制而轉移到新產生的細胞中，新細胞就繼承了舊細胞的基因. 有性生殖的生物在遺傳到下一代的時候，兩個同源染色體之間相互交叉而重組，也就是在兩個染色體在某一個相同的位置DNA斷裂了，其前后兩竄分別交叉組合而形成兩個新的染色體. 另外，在進行細胞復制時，雖然概率很小，但也有可能產生某些復制差錯，從而使DNA發生某種變異，產生出新的染色體，這些新的染色體表現出的新的性狀，如此這般，遺傳基因或者染色體在遺傳的過程中由于各種各樣的原因而發生變化.

生物在進化過程中主要是通過染色體之間的交叉和染色體的變異來完成的. 與此對應，遺傳算法中最優解的搜索過程也模仿生物進化的過程，使用所謂的遺傳算子作用于群體P(t)中，從而得到新一代群體P(t + 1).

●選擇:根據各個個體的適應度，按照一定的規則或者方法，從第t代群體P(t)中選擇出一些優良的個體遺傳到下一代群體P(t + 1).

●交叉:將群體P(t)內的各個個體隨即搭配成對，對每一個個體以某個概率(稱為交叉概率交換他們之間的部分染色體.

●變異:對群體P(t)中的每一個個體，以某一概率改變某一個或者某一些基因座上的基因值為其他的等位基因.

運算過程如下:

步驟一:初始化. 設置進化代數計數器 T←0;設置最大進化代數T ;隨即生成M個個體作為初始群體P(t).

步驟二:個體評價. 計算群體P(t)中各個個體的適應度.

步驟三:選擇運算. 將選擇算子作用于群體.

步驟四:交叉運算. 將交叉算子作用于群體.

步驟五:變異運算. 將變異算子作用于群體. 群體P(t)經過選擇，交叉，變異運算之后得到下一代群體P(t + 1).

步驟六:終止條件判斷. 若t ≤ T，則:t←t + 1，轉到步驟二;若t > T，則以進化過程中所得到的具有最大適應度的個體作為最優解輸出，終止計算.

遺傳算法中將n維決策向量X = [X1X2…Xn ]T 用n個記號Xi (i = 1，2，…，n)所組成的符號串X 來表示:

X = X1X2 … Xn → X = [x1，x2，…，xn]T .

把每一個Xi看做一個遺傳基因，它的所有可能取值稱為等位基因，這樣，X就可看做是由n個基因所組成的一個染色體. 一般情況下，染色體的長度n 是固定的，對于一些問題n也是可以變化的. 根據不同的情況，這里的等位基因可以是一組整數，也可以是某一范圍內的實數值，或者是純粹的一個記號，最簡單的等位記憶內是0和1這兩個數組成的，相應的染色體就可表示為個二進制符號串. 這種編碼所形成的排列形式X是個體的基因型，與他對應的X值是個體的表現型. 通常個體的表現型和其基因型是一一對應的，但是有時候也允許基因型和表現型的多對一的關系. 染色體X 也稱為個體X，對于每一個個體X，要按照一定的規則確定出其適應度. 個體的適應度與其對應的個體表現型 X的目標函數值相關聯，X越接近于目標函數的最優解，其適應度就越大，反之，其適應度就越小.

二#65380;算法的改進

考慮如下約束優化問題:

minf(x)，s.tx∈Ω.

其中x = (x1，x2，…，xn)T，f ∈c，Ω為有界閉集.

將遺傳算法改進如下:

1. 初始化. 在Ω中隨即選取m個點x1(0)，x2(0)，…，xm(0)，構成初始種群X(0) = {x1(0)，x2(0)，…，xm(0)}，計算初始種群中每個個體xi(0)，i = 1，2，…，m 處的目標函數值f(xi(0))，i = 1，2，…，m，令t = 0，x* = arg {f(xi(0))}.

2. 進行變異.令xi+m(t) = xi(t) + αξ，i = 1，2，…，m，其中ξ~N(0，σ) = (N(0，σ1)，N(0，σ2)，…， N(0，σm))T，N(0，σi)表示均值為0，方差為σi2的正態分布，且ξ的n個分量相互獨立. α∈(0，1]為壓縮因子.

若xi+m(t)∈Ω，則轉第3步;否則重復第2步.

3. 計算新個體xi+m(t)(i = 1，2，…，m) 處的目標函數值f(xi+m(t))，(i = 1，2，…，m).

4. 進行選擇. 從{x1(t)，x2(t)，…，x2m(t)}中選擇m 個函數值最小的個體構成新一代種群X(t + 1) = {x1(t + 1)，…，xm(t + 1)}，令x*(t + 1) =arg {f(xi(t + 1))}.

5. 終止檢驗. 判別X(t + 1)是否滿足終止條件，若滿足，則計算結束，輸出最優解x*(t + 1);否則，令t = t + 1，返回第2步.

三#65380;數值舉例

例1 f(x) = -2πx -sin(2i+1πx)， x∈[0，1]，利用Matlab得到圖1:

該函數在區間[0，1]內有多個局部極值點，其全局最優值為f小(x) = -7.4562，f大(x) = 1.1730.

例2 f(x，y) = (cos(2πx) + cos(2.5πx) - 2.1) × (2.1 - cos(3πy) - cos(3.5πy).

其中(x，y)∈[0，3]×[0，1.5].

利用Matlab作圖如圖2:

該函數在區域[0，3]×[0，1.5]內有多個局部極值點和一個全局最優點. 全局最優值為

f(0.438974，0.305734) = -16.09172 .

例3 f(x，y) = max(f1(x，y)，f2(x，y))，其中f1(x，y) = (x -cos )2 + 0.005(x2 + y2)，f2(x，y) = (x -sin )2 + 0.005(x2 + y2).

該函數雖然是一個單峰函數，卻十分光滑. 其全局最優值為f(0，0) = 0 .

利用Matlab作圖3:

下表是算法A對上述三算例的計算結果.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”