遺傳算法在函數(shù)優(yōu)化中的應(yīng)用研究

王悅

（西安文理學(xué)院信息中心，陜西西安710068）

遺傳算法在函數(shù)優(yōu)化中的應(yīng)用研究

王悅

（西安文理學(xué)院信息中心，陜西西安710068）

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

遺傳算法；函數(shù)優(yōu)化；適應(yīng)度函數(shù)；遺傳算子；編碼方式

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

1　遺傳算法的基本理論

1.1基本遺傳算法的描述

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

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

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

基本遺傳算法的構(gòu)成要素：1）染色體編碼方法；2）個(gè)體適應(yīng)度評(píng)價(jià)；3）遺傳算子（選擇、變異和交叉算子）；4）基本遺傳算法的運(yùn)行參數(shù)。

1.2遺傳算法的模式理論

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

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

2　遺傳算法的分析及改進(jìn)

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

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

2.2針對存在問題的改進(jìn)方式

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

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

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

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

3　遺傳算法求解函數(shù)最優(yōu)化問題的實(shí)現(xiàn)

3.1函數(shù)優(yōu)化問題的描述

可以說所有的優(yōu)化都是基于“函數(shù)”數(shù)學(xué)特征的優(yōu)化，我們可以將目標(biāo)函數(shù)的優(yōu)化問題描述為：

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

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

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

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

3.3基于MATLAB的函數(shù)優(yōu)化過程分析

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

圖2　4種算法的種群最優(yōu)值與遺傳代數(shù)之間的變化規(guī)律

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

圖3　4種算法的種群平均值與遺傳代數(shù)之間的變化規(guī)律

綜上所述，可以看出本文提出的改進(jìn)算法M4有著相對于其他算法的明顯優(yōu)勢。

4　結(jié)論

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

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

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

［3］李敏強(qiáng)，寇紀(jì)淞.遺傳算法的基本理論及其應(yīng)用［M］.北京：科學(xué)出版社，2002.

［4］王小平，曹立明.遺傳算法—理論、應(yīng)用與軟件實(shí)現(xiàn)［M］.西安：西安交通大學(xué)出版社，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］孫艷豐，王復(fù)托.關(guān)于遺傳算法圖式定理的分析研究［J］.控制與決策，1996（增刊）：221_224.

［9］于欲杰，王贊基.適用于多峰函數(shù)優(yōu)化的改進(jìn)順序生境遺傳算法［J］.清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2001，41（3）：17_20.

［10］陳小平，于盛林.實(shí)數(shù)遺傳算法交又策略的改進(jìn)［J］.電子學(xué)報(bào)，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］李菱，唐朝裕，李笑怡.基于粒子群遺傳算法的電動(dòng)汽車充電站的布局規(guī)劃［J］.陜西電力，2014（4）：65_69.

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

［14］佘小莉.基于遺傳算法的功放預(yù)失真器模型研究與實(shí)現(xiàn)［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稿件編號(hào)：201511116

王悅（1972—），男，陜西西安人，碩士研究生，工程師。研究方向：計(jì)算機(jī)網(wǎng)絡(luò)及應(yīng)用。