遺傳算法在函數優化中的應用研究

王悅

（西安文理學院信息中心，陜西西安710068）

遺傳算法在函數優化中的應用研究

王悅

（西安文理學院信息中心，陜西西安710068）

文中基于對遺傳算法理論進一步完善改進的出發點，選取了遺傳算法在求解函數優化問題這一研究對象，對遺傳算法的基本原理及模式理論進行了探討，并對遺傳算法的不足進行了分析同時也提出了改進方案。在就適應度及遺傳算子的研究之后，提出了改進的遺傳算法。最后，在MATLAB環境下，選取包括改進算法的四種算法進行了測試，完成了遺傳算法求解函數優化問題的應用，并證明了本文提出的改進算法的優越性。

遺傳算法；函數優化；適應度函數；遺傳算子；編碼方式

遺傳算法（GA）是基于達爾文生物進化論和孟德爾遺傳變異理論的一類仿生型優化算法。遺傳算法結構簡單不需要過多的考慮所要處理問題的動力學信息并且兼具有全局搜索能力、信息處理的隱并行性、魯棒性和可規模化等等的優點，非常適合處理利用傳統搜索方法不能很好解決的復雜及非線性問題。因此，現在組合優化、自適應控制、組合優化和規劃設計等領域遺傳算法有著非常廣泛應用前景。基于此國內外現在都非常重視遺傳算法理論及相應應用方面的研究。遺傳算法的處理對象是對參數進行了編碼的個體而不是參數本身，因此可以對矩陣、樹和圖等結構形式的對象進行處理。函數優化是遺傳算法的諸多應用中最顯而易見也是最為經典的。函數優化的本質就是從所有解決問題的可能性中選出最合理最優的方案。而隨著求解維數的增長，求解難度也大幅度的增加，因而傳統的優化方案不能滿足優化需要。遺傳算法就作為仿生物自然進化過程被稱為演化算法的隨機優化技術的代表顯示出了它優于傳統算法的優越性能。

1　遺傳算法的基本理論

1.1基本遺傳算法的描述

遺傳算法不依賴于求解系統的領域及種類，為復雜系統問題的求解提供了一個通用框架。基本遺傳算法（SGA）是由Go1dberg總結的一種最基本的遺傳算法，它以群體中所有的個體為對象，只使用選擇、變異和交叉3種基本遺傳算子，是其他一些遺傳算法的雛形和基礎并為其他的遺傳算法提供了基本的框架。并且基本遺傳算法其自身也有一定的應用價值，圖1給出的就是基本遺傳算法的流程圖。

圖1　基本遺傳算法（SGA）流程圖

首先根據所要處理的系統選擇相應的編碼系統，并隨機產生一組由確定個長度的N個染色體組成的初始群體。然后計算該群體中每個染色體的適應度，判斷算法收斂準則是否滿足，不滿足則繼續執行下面的步驟滿足則輸出搜索結果。接下來進行選擇操作，根據個體適應度計算選擇概率，根據計算得出的概率分布隨機從當前一代群體中選擇一些染色體遺傳到下一代。之后進行交叉操作，以一定改了吧交配可以得到一個由N個染色體組成的群體，最后的變異操作是用一較小概率使染色體進行基因變異，形成新群體，該群體即完成了一次遺傳操作后的子代同時亦是下一次遺傳操作的父代。不過，基本遺傳算法并不收斂于全局最優解，所以在實際應用中要對SGA進行一定的改進使其有更好的收斂性能。

基本遺傳算法的構成要素：1）染色體編碼方法；2）個體適應度評價；3）遺傳算子（選擇、變異和交叉算子）；4）基本遺傳算法的運行參數。

1.2遺傳算法的模式理論

模式，即有用的相似性，表示了一些描述在某位置上有相似結構特征的個體編碼串子集的一些相似模塊。模式定理是最早對遺傳算法的全局收斂性作定性分析的理論基礎，一定程度上對遺傳算法的機理、數學特征及計算能力進行了解釋。引入了模式這一概念之后，我們發現遺傳算法的本質就是一系列基于模式的操作，將當前群體中的優良模式通過選擇操作遺傳到下一代，再通過交叉操作對模式進行重組并通過變異操作實現模式的突變。簡而言之，通過一系列對模式的優勝略汰的操作，得到所求問題的最優解。

遺傳算法為復雜系統問題的求解提供了一種通用架構，其兩大顯著特征是隱并行性和全局搜索特征。不過遺傳基本遺傳算法有著其自身的不足，對于非線性問題、以及欺騙性問題以及多峰函數的優化顯得力不從心，而這些問題是廣泛存在于實際應用操作中的，所以對遺傳算法的進一步研究及改進是十分必要的。

2　遺傳算法的分析及改進

2.1基本遺傳算法存在的問題

衡量一個算法的好壞主要在于能否找到全局最優解、算法優化精度和它的收斂速度等條件，而基于遺傳算法在實際中的應用，人們漸漸發現了遺傳算法存在的一些不足。1）遺傳算法所采用的二進制編碼無法對所求問題的特定知識進行方便快捷的反映，且由于它的隨機性使得遺傳算法的局部搜索能力比較不足，對于多維高精度的連續函數，也存在著在離散化時不能避免的映射誤差；2）算法中應用的選擇策略會使在進化初期時適應度較高的個體被多次選中，影響了群體的多樣性并造成過早收斂。3）算法中使用的變異操作不能收斂于最優解，而遺傳算子的隨機性造成了收斂速度慢；4）控制參數的選擇目前沒有確定的規則，而它對算法的收斂速度和搜索效率也有著相當的影響。

2.2針對存在問題的改進方式

編碼問題是首要解決的問題。針對基本遺傳算法中二進制編碼的不足，在多參數條件下我們可以應用多參數交叉編碼或者多參數級聯編碼這兩種編碼方式，可以將眾多參數中起主要作用的碼位集中起來，避免遺傳算子對它們的破壞。格雷碼與二進制編碼非常相似但是卻有著更高的局部搜索能力；實數碼可以用于大范圍遺傳搜索、高精度多維問題的優化處理。

對于初始種群的設定，則可以利用Leung.Y.W所提出的構造均勻正交數來產生，這樣可以保證初始群體在解空間分布均勻，同時它將遺傳算法視作概率搜索算法從而利用了它的隱含空間特性。也可以利用何大闊等采用的均勻設計產生初始群體和設定操作參數的方法，使算法有更好的收斂性和快速性。

由于不同的選擇操作有著其自身特定的優缺點，無法找到完美的選擇算子，所以結合不同的選擇方法，本文提出了混合選擇法。首先隨機遍歷抽取一定值的個體，依據線性排序得到的適應度進行，對這些個體完成交叉變異操作；將父代中最佳個體保留；最后將之前選中的子代完成交叉變異后按其適應度淘汰原父代中適應度最差的個體。該方法可有效提高原算法的尋優性能。交叉算子是遺傳算法區別于其他算法而言最大的不同，也是在遺傳過程中產生新個體最主要的方法。本文采用的交叉操作依據個體不同的適應度利用逼近方法定位子代群體的交叉策略，利用線性排序法得到個體適應度。對于變異算子的改進，學者們提出了如采用柯西變異算子、高斯變異等其他變異算子的改進方法。本文中選擇實值變異，其中變異概率隨著子代的最優化程度增加而逐漸減小，從而維持進化初期時種群的多樣性。

控制參數的選擇對于遺傳算法的設計也非常重要，不過對于控制參數來說，并不存在適用于所有問題的參數，要具體問題具體分析，根據不同的問題選取最優的參數組合。其中，交叉概率Pc和變異概率Pm是影響算法性能的關鍵所在，需要反復實驗來確定。

3　遺傳算法求解函數最優化問題的實現

3.1函數優化問題的描述

可以說所有的優化都是基于“函數”數學特征的優化，我們可以將目標函數的優化問題描述為：

其中，f（Xi）是目標函數；Rn是目標函數的值域；S為目標函數變量｛Xi=｛x1，x2，L xn｝，i=1，2L popsize｝的定義域，popsize是種群規模；n為變量維數。

式（1）描述的函數最優化問題其實也是目標函數的最大化最小化問題，二者可以相互轉化，也就是尋找在滿足所有約束條件的定義域上，函數f（Xi）的全局最優解及此時對應的n維實向量X*。

3.2本文采用的四種遺傳算法

算法M1：實數遺傳算法，編碼方式采用實數編碼、按比例賭輪選擇、保留最優個體、實值變異、線性雜交算子；算法M2：改進的實數遺傳算法，實數編碼、按比例選擇保留最優個體、無變異算子、逼近方式定位子代群體交叉策略；算法M3：改進二進制編碼遺傳算法，二進制編碼、按比例選擇保留最優個體、離散變異、兩點交叉（二、三維函數）或三點交叉（高維函數）。第四種算法為本文中改進的算法，算法M4：實數編碼、第3章中描述過的由線性排序的適應度分配方法、實值變異、基于適應度的線性筆記的改進交叉策略。

3.3基于MATLAB的函數優化過程分析

圖2是四種算法的最優值變化曲線圖，描述的是四種算法的種群最優值與遺傳代數之間的變化規律。從圖中可以看出四種算法的最優值曲線隨著進化代數的增加由開始的相對平穩最后趨于收斂，同時可以由運行數據得出全局最優解M4的收斂值，而前三種的算法最終都只趨于收斂于最大峰的脊圈上。

圖2　4種算法的種群最優值與遺傳代數之間的變化規律

圖3是4種算法的均值變化曲線圖，描述種群平均值與遺傳代數之間的變化規律。從圖中可以看出，在進化的初期，4個種群均值曲線都有著較大的波動，不過隨著進化代數增加而趨于平穩。M2、M3和M4的均值都與進化代數保持著相同的增減趨勢，M4的均值始終處于4個種群中的最大值，且有著最為平穩的變化趨勢。

圖3　4種算法的種群平均值與遺傳代數之間的變化規律

綜上所述，可以看出本文提出的改進算法M4有著相對于其他算法的明顯優勢。

4　結論

文中對遺傳算法在函數優化的應用下的編碼方式、適應度函數及遺傳操作方面進行了深入的研究，并得出了相應的改進算法。在編碼方式上采用可應用于多維高精度連續函數的實數編碼方式，采用多種操作方式混合的選擇策略，選擇的適應度函數值由線性排序的分配方法獲得，防止了未成熟收斂。之后又用MATLAB進行實現，對包含文中給出的改進算法的四種算法進行比較，驗證了改進算法的優越性。

［1］Ho11and J H.Adaptation in natura1 and artificia1 systems［M］. Ann Arbor：University of Michigan press，1975

［2］陳國良，王煦法.遺傳算法及其應用［M］.北京：人民郵電出版社，1996.

［3］李敏強，寇紀淞.遺傳算法的基本理論及其應用［M］.北京：科學出版社，2002.

［4］王小平，曹立明.遺傳算法—理論、應用與軟件實現［M］.西安：西安交通大學出版社，2002.

［5］Go1dberg D E.Genetic A1gorithms in search，optimization，and machine 1earning［M］.Addsin_Wes1ey Pub1ishing Company，INC，New York，1989.

［6］Davis L.Handbook of Genetic A1gorithms［M］.New York：Van Nostrand Reinho1d，1991.

［7］Li Maojun，Tong Tiaosheng.A further resu1t on the schema t_ heorem of partheno_genetic a1gorithm［J］.Contro1 Theory and App1ications，2001，18（3）：465_468.

［8］孫艷豐，王復托.關于遺傳算法圖式定理的分析研究［J］.控制與決策，1996（增刊）：221_224.

［9］于欲杰，王贊基.適用于多峰函數優化的改進順序生境遺傳算法［J］.清華大學學報：自然科學版，2001，41（3）：17_20.

［10］陳小平，于盛林.實數遺傳算法交又策略的改進［J］.電子學報，2003，1（31）：71_74.

［11］Anderson K S，YuHung Hsu.Genetic crossover strategy using an approximation concept［C］//Proc.of 1999 Congress on Evo1utionary Computation.Washington D.C：CEC，1999：527_ 533.

［12］李菱，唐朝裕，李笑怡.基于粒子群遺傳算法的電動汽車充電站的布局規劃［J］.陜西電力，2014（4）：65_69.

［13］徐平，聞建中，馬承志，等.基于遺傳算法的輸電線路差異化運維優化方法的研究［J］.陜西電力，2014（5）：6_10.

［14］佘小莉.基于遺傳算法的功放預失真器模型研究與實現［J］.陜西電力，2015（9）：76_79.

APPllcatlon of genetlc algorlthm ln functlon oPtlmlzatlon

WANG Yue
（Xi'an University Information Center，Xi'an 710068，China）

Based on the theory of genetic a1gorithm to further improve and perfect the starting point，this artic1e se1ect the genetic a1gorithm for so1ving function optimization prob1ems in this study，the basic princip1es of genetic a1gorithms and mode1 theory were discussed，and the 1ack of genetic a1gorithms are ana1yzed a1so proposed improvements.Fo11owing on the research of the fitness fuction and genetic operators，the improved genetic a1gorithm was proposed.Fina11y，in the MATLAB environment，inc1uding the improvement of four a1gorithms se1ected a1gorithm has been tested，we comp1eted the genetic a1gorithm function optimization app1ications and proves the superiority of the proposed improved a1gorithm.

genetic a1gorithms；function optimization；fitness function；encoding

TM933.4

A

1674_6236（2016）10_0074_03

2015_11_11稿件編號：201511116

王悅（1972—），男，陜西西安人，碩士研究生，工程師。研究方向：計算機網絡及應用。