一種基于模式搜索的自學(xué)習(xí)遺傳算法研究＊

姜禮平 胡偉文 吳向君

（海軍工程大學(xué)理學(xué)院1） 武漢 430033） （海軍工程大學(xué)船舶與動力學(xué)院2） 武漢 430033）

0 引 言

遺傳算法是一種應(yīng)用廣泛的全局收斂算法，但是傳統(tǒng)的遺傳算法在復(fù)雜優(yōu)化問題求解中常常力不從心.一些理論研究也證明傳統(tǒng)的遺傳算法很難收斂到全局最優(yōu)狀態(tài)［1］.因此，對遺傳算法有眾多的相關(guān)改進(jìn)研究.一方面，為了保證算法的全局收斂性，就要維持種群中個體的多樣性和搜索的有效性，避免有效基因的丟失；另一方面，為了加快收斂速度，就要使種群較快地向最優(yōu)狀態(tài)轉(zhuǎn)移，這又會降低群體的多樣性，容易陷入局部最優(yōu).如何較快地找到最優(yōu)解并防止早熟收斂問題是遺傳算法中一個較難權(quán)衡的問題.

許多研究者提出了各種改進(jìn)方法來提高遺傳算法的性能.其中，針對遺傳算法主要算子進(jìn)行改進(jìn)和將遺傳算法與其他優(yōu)化算法組合的研究較多.如文獻(xiàn)［2］利用選擇操作對優(yōu)良個體的優(yōu)先遺傳作用，通過優(yōu)化選擇策略來提高算法的全局收斂性，這樣雖然加快了算法的收斂速度，但也容易產(chǎn)生早熟的問題；文獻(xiàn)［3］將量子技術(shù)與遺傳算法結(jié)合，利用量子概率編碼的表達(dá)多樣性，提高了遺傳算法解決多目標(biāo)優(yōu)化問題的有效性.本文在通過改變編碼策略來維持群體多樣性的前提下，重點研究了基于模式搜索的學(xué)習(xí)算子，有效的提高了遺傳算法的全局收斂性和收斂速度.

1 模式搜索算法

模式搜索（pattern search）是一種求解優(yōu)化問題的直接搜索方法.與使用梯度或高階導(dǎo)數(shù)信息來搜索優(yōu)化點的傳統(tǒng)優(yōu)化算法不同，模式搜索算法在每次迭代中依據(jù)模式和步長來搜索當(dāng)前點周圍的一系列網(wǎng)格點，尋找使目標(biāo)函數(shù)值得到改善的點.對于求解目標(biāo)函數(shù)不可微、甚至不連續(xù)的問題比較實用［4］.

定義 模式搜索是對當(dāng)前點按固定模式和步長Δk探索移動（exploratory moves），以尋求可行下降方向（非最速下降方向）的直接搜索法.迭代過程只要找到相對于當(dāng)前點的改善點，則步長遞增，并從該點開始進(jìn)入下一次迭代；否則步長遞減，在當(dāng)前點繼續(xù)搜索.以下為模式搜索算法的主要術(shù)語及其實現(xiàn)方式.

1）模式 在模式搜索中，模式是若干向量的集合，向量由算法來使用，以確定在每次迭代中要搜索哪些點.例如，如果在某優(yōu)化問題中存在2個獨立變量，則缺省模式由下面的向量組成

2）網(wǎng)格 在每一次迭代中，模式搜索算法搜索一組點（稱為網(wǎng)格（mesh）），以尋找使目標(biāo)函數(shù)得到改善的點.該算法形成網(wǎng)格的方法是：（1）給模式向量乘以一個標(biāo)量（稱為網(wǎng)格尺寸（mesh size））；（2）把結(jié)果向量與當(dāng)前點相加.當(dāng)前點是在前一步找到的具有最佳目標(biāo)函數(shù)值的點.

需要說明的是，模式搜索中用2個變量來調(diào)整網(wǎng)格的擴(kuò)張和收縮，分別為：擴(kuò)張因子（expansion factor）和收縮因子（contraction factor）.

3）判決 在每一步迭代中，算法通過計算當(dāng)前生成的網(wǎng)格點的目標(biāo)函數(shù)值，若找到使目標(biāo)函數(shù)得到改進(jìn)的點（即判決成功），就將網(wǎng)格尺寸擴(kuò)大進(jìn)入下一迭代過程，網(wǎng)格擴(kuò)大的倍數(shù)由擴(kuò)張因子決定，此稱為模式搜索的正向機(jī)制；同樣，若某次迭代中判決不成功，則保留當(dāng)前點不變，將網(wǎng)格尺寸縮小并進(jìn)入下一迭代過程，網(wǎng)格縮小的倍數(shù)由收縮因子決定，此稱為模式搜索的負(fù)向機(jī)制.具體判決過程中有一個完全表決（complete poll，cp）參數(shù)，用來控制判決的完全性.若cp＝1，則判決過程必須搜索、計算并比較每一個當(dāng)前生成的網(wǎng)格點，尋求其中的最優(yōu)點替代當(dāng)前點；若cp＝0，則只要判決過程找到一個相對更優(yōu)的點就停止當(dāng)前代的判決過程，以此點作為新的當(dāng)前點進(jìn)入下一個迭代過程.

2 基于模式搜索的自學(xué)習(xí)遺傳算法

2.1 自學(xué)習(xí)遺傳算法

總體上講，遺傳算法主要存在兩種機(jī)制：遺傳和進(jìn)化，遺傳是必要的，而進(jìn)化才是優(yōu)化的目的所在.絕大多數(shù)遺傳算法的研究集中在對算法自身的改進(jìn)和融合上，只考慮了生物遺傳的客觀性和同代種群個體之間的交流，往往忽略了生物遺傳的主觀能動性和種群進(jìn)化過程中前后代累積的經(jīng)驗信息［5］.所謂自學(xué)習(xí)遺傳是指在不改變遺傳算法主體的前提下，充分利用遺傳過程中的主要遺傳信息來指導(dǎo)遺傳過程下一步的進(jìn)化方向，實現(xiàn)主動的自我學(xué)習(xí)和調(diào)整.如文獻(xiàn)［5］研究了一種通過統(tǒng)計歷代最優(yōu)解的每一個基因位的累積變化情況來確定當(dāng)前優(yōu)化方向的自學(xué)習(xí)遺傳算法.

本文提出了基于模式搜索的自學(xué)習(xí)遺傳算法（active learning genetic algorithm with patern search，ALGA）.即利用每一代遺傳中最優(yōu)個體的變化規(guī)律，通過模式搜索的確定型自調(diào)整機(jī)制，來試探在當(dāng)前代最優(yōu)解的附近是否存在進(jìn)一步優(yōu)化的空間，并將通過模式學(xué)習(xí)調(diào)整而搜索到的更優(yōu)解返回當(dāng)前迭代種群，從而指導(dǎo)遺傳算法改善下一步的進(jìn)化方向，使下一步的個體不斷向更優(yōu)的“先輩”學(xué)習(xí).

2.2 基于模式搜索的學(xué)習(xí)算子

2.2.1 模式搜索作為學(xué)習(xí)算子的可行性

模式搜索是一種直接、有效的主動搜索方式，具有很強(qiáng)的局部搜索能力和一定的全局搜索能力.而遺傳算法具有較好的通用性和全局搜索能力.同時，遺傳算法本身不是確定性的搜索機(jī)制，這既是優(yōu)勢也使其在遺傳過程的優(yōu)化方向上（尤其是部分種群個體）存在一定的隨機(jī)波動；并且在已有的遺傳選擇域內(nèi)，交叉和變異的局部收斂性遠(yuǎn)不及模式搜索；特別是在某些特定情況下（如最優(yōu)域空間相對狹小等），遺傳算法存在后期收斂遲滯的問題.因此，在遺傳過程后引入模式搜索的學(xué)習(xí)機(jī)制具有很強(qiáng)的可行性.

當(dāng)然，模式搜索作為學(xué)習(xí)算子也有相應(yīng)的應(yīng)用范圍.其對具有連續(xù)意義的優(yōu)化問題編碼有較好的應(yīng)用價值，能很好的增強(qiáng)遺傳算法的局部尋優(yōu)能力，提高收斂速度.而對于互不關(guān)聯(lián)的平行編碼或無前后意義的符號編碼類優(yōu)化問題則效果不明顯.

2.2.2 學(xué)習(xí)算子設(shè)計流程

本文中模式搜索僅作為局部輔助搜索，因此在本文算法中僅基于模式搜索的正向機(jī)制（即只采取擴(kuò)張模式）來設(shè)計自學(xué)習(xí)算子，其具體設(shè)計的簡化流程如圖1所示.

圖1 自學(xué)習(xí)算子設(shè)計流程

2.3 基于模式搜索的自學(xué)習(xí)算法流程設(shè)計

綜合上述研究，本文基于模式搜索設(shè)計了獨立的學(xué)習(xí)算子，提出了新的自學(xué)習(xí)遺傳算法.其基本流程如圖2所示.

圖2 自學(xué)習(xí)遺傳算法基本流程

下面將基于模式搜索的自學(xué)習(xí)遺傳算法的流程作簡單介紹.

1）在本文自學(xué)習(xí)遺傳算法中，初始種群采取標(biāo)準(zhǔn)二進(jìn)制編碼，當(dāng)然也可采用格雷編碼、整數(shù)或?qū)崝?shù)（浮點數(shù)）編碼，但是主要針對連續(xù)性數(shù)值優(yōu)化問題.前期對于初始種群的多樣性調(diào)整對算法的全局收斂性至關(guān)重要，對不同的編碼方式和優(yōu)化問題，需要作針對性的調(diào)整.本文中針對標(biāo)準(zhǔn)二進(jìn)制編碼，在考慮種群規(guī)模、編碼位數(shù)、編碼區(qū)間后，取編碼前5位來劃分尋優(yōu)子空間，即可將編碼空間劃分為32個子空間，確保初始個體在每個尋優(yōu)空間均存在.

2）在遺傳算法的主要操作上，本文中種群適應(yīng)度取對優(yōu)化目標(biāo)值的線性標(biāo)定值；選擇操作采取隨機(jī)遍歷抽樣，此方式相對于輪盤賭原則，其選擇的多樣性要優(yōu)于后者；變異操作采取離散變異方式，而交叉操作則采用基本的單點交叉模式；在重插入環(huán)節(jié)，基于適應(yīng)度和精英保留的重插入可以確保各代中的優(yōu)良個體順利的保留下來.

3）主要遺傳過程結(jié)束后，自學(xué)習(xí)算子將依據(jù)模式搜索機(jī)制對當(dāng)代種群的的最優(yōu)個體進(jìn)行趨勢調(diào)整，判斷其下一步優(yōu)化方向并返回調(diào)整結(jié)果，這樣能很好的提高遺傳算法的局部搜索能力.需要說明的是，自學(xué)習(xí)遺傳算法是根據(jù)確定的學(xué)習(xí)機(jī)制，從截止當(dāng)前的種群進(jìn)化過程中判斷種群優(yōu)化的可能方向，進(jìn)而在存在優(yōu)化空間的方向上對目前種群較優(yōu)個體進(jìn)行調(diào)整并返回優(yōu)化結(jié)果，此過程獨立于遺傳操作.這有別于自適應(yīng)遺傳算法中依據(jù)種群進(jìn)化進(jìn)程動態(tài)調(diào)整遺傳參數(shù)的方法.

2.4 對遺傳過程的適當(dāng)改進(jìn)

從上述分析不難看出，自學(xué)習(xí)遺傳算法具有很強(qiáng)的局部搜索能力，能夠確保只要進(jìn)入搜索范圍的最優(yōu)解都能得到體現(xiàn)，但是如何確保在遺傳的最終結(jié)果中得以體現(xiàn)呢？同時，基于模式搜索的自學(xué)習(xí)機(jī)制在提高遺傳算法的局部尋優(yōu)能力的情況下，是否會同樣存在未成熟收斂的風(fēng)險呢？所以，為較好的解決以上兩種隱患，本文在遺傳過程上作了三點改進(jìn)來擴(kuò)大遺傳搜索的全局性和種群的多樣性，確保在歷代中體現(xiàn)的最優(yōu)結(jié)果得以保留.改進(jìn)分別為：（1）對初始種群進(jìn)行分布多樣性調(diào)整（即劃分搜索子空間）；（2）取相對較大的交叉和變異概率，以擴(kuò)大種群的搜索能力；（3）采取精英保留的重插入策略，確保了最終尋優(yōu)結(jié)果的有效收斂.

3 算例測試

3.1 關(guān)于測試的相關(guān)說明

對本文設(shè)計算法的有效性測試采用兩個經(jīng)典函數(shù)，分別為一元多極值函數(shù)f1和多元多峰函數(shù)f2（Shubert函數(shù)）.

式中：函數(shù)f1為周期震蕩函數(shù)，在當(dāng)前限定域中，當(dāng)x＝3.9585時取得極小值－1.9584；函數(shù)f2是一個多峰值多極值函數(shù)，在其定義域內(nèi)它總共有760個局部最小點，其中有18個是全局最小點，全局最小值為13.2691.測試中參與對比的算法為：標(biāo)準(zhǔn)遺傳算法（SGA）和本文的ALGA算法.以下實驗為進(jìn)行最小值尋優(yōu)且所有數(shù)據(jù)和結(jié)果都在同一計算機(jī)環(huán)境上同段時期運算所得，具體見表1、圖3和圖4.遺傳算法均迭代30代，其最終收斂是指優(yōu)化結(jié)果在極值點附近，誤差控制在1%以內(nèi)，超出此誤差控制范圍即認(rèn)為不收斂，且表1的統(tǒng)計結(jié)果為50次連續(xù)操作取得.其中，平均收斂代數(shù)和收斂均值都是依據(jù)在50次遺傳中算法收斂的次數(shù)及其收斂結(jié)果來計算的，平均運行時間為50次遺傳的總體運行時間的均值.

表1 算法優(yōu)化性能統(tǒng)計分析表

圖3 算法在函數(shù)f1時的收斂情況

3.2 測試結(jié)論

從圖3～4的算法收斂性對比以及表1的算法優(yōu)化性能統(tǒng)計結(jié)果可以看出，在算法的初始基本參數(shù)一致和相同運行環(huán)境的情況下，可以得出如下結(jié)論.

圖4 算法在函數(shù)f2時的收斂情況

1）總體而言，ALGA算法的改進(jìn)使其在優(yōu)化性能上較SGA算法有很大的改善，充分體現(xiàn)了ALGA算法的有效性.

2）具體上講，在多極值優(yōu)化問題中，SGA算法容易陷入局部最優(yōu)（見圖3），基本上不具備解決復(fù)雜優(yōu)化問題的有效性.而ALGA算法具有很高的收斂效率和收斂速度，說明算法對于解決此類問題具有較強(qiáng)的可行性.從表1的平均運行時間比較來看，新算法對程序在執(zhí)行效率上的影響很小，這主要得益于新算法更快速、有效的收斂性能提升了程序的遺傳速度.

4 結(jié)束語

本文主要從引入基于模式搜索的獨立學(xué)習(xí)算子對遺傳過程進(jìn)行自我調(diào)整.實驗結(jié)果表明，該算法較好的改善了遺傳算法全局收斂的有效性，對于遺傳算法在復(fù)雜優(yōu)化問題上的應(yīng)用提供了一種新的解決思路，具有一定的參考價值.

［1］Rudolph G.Convergence properties of canonical genetic algorithms［J］.IEEE Trans.Neural Networks，1994，5（1）：96－101.

［2］Thierens D，Goldberg D.Elitist recombination：an integrated selection recombination GA［C］／／The First IEEE Conference o－n Evolutionary Computation，USA，Orlando，F(xiàn)loride，1994.

［3］鄒 誼，魏文龍，李 斌.多目標(biāo)量子編碼遺傳算法［J］.電子與信息學(xué)報，2007，29（11）：2 688－2 692.

［4］雷英杰，張善文，李繼武.MATLAB遺傳算法工具箱及應(yīng)用［M］.西安：西安電子科技大學(xué)出版社，2005.

［5］聶 沖，王維平，趙 雯.基于學(xué)習(xí)算子的自學(xué)習(xí)遺傳算法設(shè)計［J］.計算機(jī)仿真，2006，23（9）：168－171.