姜禮平 胡偉文 吳向君

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

0 引 言

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

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

1 模式搜索算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 算例測(cè)試

3.1 關(guān)于測(cè)試的相關(guān)說(shuō)明

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

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

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

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

3.2 測(cè)試結(jié)論

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

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

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

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

4 結(jié)束語(yǔ)

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

［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é)報(bào)，2007，29（11）：2 688－2 692.

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

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