多群體遺傳算法動態調整區間的參數優化方法

2022-07-07 02:42:48關曉穎謝盛嘉

計算機應用與軟件 2022年5期

關鍵詞：優化

關曉穎謝盛嘉陳果

1(廣東食品藥品職業學院軟件學院廣東廣州 510520)2(廣東女子職業技術學院應用設計學院廣東廣州 511450)3(南京航空航天大學民航學院江蘇南京 210016)

0 引言

參數優化是通過優化方法不斷調整設計變量，使得設計結果不斷接近參數的目標值。參數優化的效果既取決于所采用的優化方法，同時也受給定的參數初始取值區間影響。在實際的應用中，參數的初始取值區間有時會憑經驗給出，就會出現參數解不一定在初始取值區間內，這將影響最終的參數優化效果。因為參數解與給定的初始取值區間之間存在兩種情況：解包含在給定的初始取值區間內和解不包含在給定的初始取值區間內。對于前者，當參數的取值區間在算法的整個運行過程中固定不變時，將會導致最終找到的參數優化結果并不是正確解，因此，希望提高方法的搜索效率和提高解的質量；對于后者，希望能夠動態調整區間，降低對初始區間的準確要求，并能最終高效率找到正確解。

遺傳算法由于其隱含的并行性和全局尋優能力，廣泛應用于參數優化[1-7]。但是，基本都默認參數解包括在初始區間，雖然也有一些學者提出了調整參數取值區間的方法[8-11]，但提出的改進方法主要是縮小搜索區間，并沒有突破原來的參數取值區間，沒有考慮到解不在參數的初始取值區間外的情況。有鑒于此，本文提出多群體遺傳算法動態調整區間的參數優化方法(MGADAI)。該方法能夠在算法的運行過程中動態調整參數取值區間，使得參數初始取值區間不是一直都是固定的，而是根據群體當前的運行情況動態調整，降低了對參數初始取值區間的準確度要求；并且，由于參數取值區間不斷在變化，特別進化后期，調整到更準確的區間，大大提高算法的效率和解的質量。另外，采用多個群體并各自獨立執行遺傳算法操作，定期交流信息相互學習，既有效地改善基本遺傳算法的“早熟”現象，也有利于后代向更好的方向進化。

1 MGADAI的參數優化方法

1.1 算法流程

MGADAI流程如圖1所示，GA流程如圖2所示。

圖1 MGADAI的流程

圖2 GA流程

算法具體實現過程如下：

(1) 給出參數的初始取值區間。

(2) 根據參數的取值區間產生隨機數，完成各群體個體初始化，形成初始種群。

(3) 假設有M群體，則各群體獨立采用GAi(i=1,2,…,M)進行參數優化。

(4) 當各群體獨立迭化到指定代數d，就進行信息交流；即根據各群體的當前優化結果，計算得到新的參數取值區間，實現區間的動態調整。

(5) 得到參數新的取值區間后，各群體根據新的參數取值區間重新進行個體初始化，形成新種群；接著各自繼續執行GA操作。

(6) 直到滿足終止條件結束，輸出結果。

1.2 動態調整參數區間方法

由于先驗知識等原因，對于所要優化的參數初始取值區間不一定能夠準確給出，就會出現如圖3(a)和圖3(b)兩種情況，其中：[a,b]為參數的初始取值區間；c為參數解。參數解與給定的初始取值區間存在兩種情況：解包含在給定的初始取值區間(圖3(a))；解不包含在給定的初始取值區間(圖3(b))。

(a) 解在初始取值區間內

(b) 解在初始取值區間外圖3 參數解與初始取值區間的關系

當出現圖3(b)這種情況，如果算法的設計對于參數的取值區間在整個運行過程中都是固定不變，將會導致參數解無法在給定的取值區間內找到。因此，如果在算法運行過程中，各群體能夠將各自當前搜索情況互相分享和學習，從而挖掘出包含高質量解的區間，并動態調整參數取值區間，這樣就可以避免圖3(b)這種情況所帶來的不足。同時，也降低了對參數初始取值區間的精確度要求；另外，由于參數取值區間不斷在變化，特別是在進化后期，區間不斷收窄，將大大提高算法效率和解的質量。

動態調整參數區間的方法具體如下。

具體實現步驟如下：

(1) 當前最優個體b1,b2,…,bm的適應度分別為f1,f2,…,fm。

(2) 計算最優個體bi(i=1,2,…,m)的權重：

(1)

(3) 計算每個基因的加權平均aj(1≤j≤n)：

(2)

(4) 計算當前各群體最優個體在第j個基因的散布程度。將wi作為權重，修正第j個基因值與均值的距離，同時也避免異常點帶來的敏感性。

(3)

(5) 計算各基因的新取值區間：

currLowerj=aj-sqrt(dj)

currUpperj=aj+sqrt(dj)

(4)

(6) 為了進一步加強更新后的參數取值區間的可靠性，新的參數取值區間將綜合考慮初始取值區間、至今找到的最優個體的取值區間、各群體迭代d代調整后的取值區間。

假設第j個基因(1≤j≤n)的初始取值區間為(initLowerj,initUpperj)，至今找到的最優個體的取值區間為(gLowerj,gUpperj)，各群體迭代d代調整后的取值區間為(currLowerj,currUpperj)，則調整后的第j個基因的取值區間(lowerj,upperj)為：

lowerj=0.3×initLowerj+0.3×gLowerj+0.4×currLowerj

upperj=0.3×initUpperj+0.3×gUpperj+0.4×currUpperj

(5)

至此，各基因新的取值區間調整完畢。各群體按照新的取值區間重新初始化個體，繼續執行GA進行優化。

1.3 遷移時機

遷移時機反映了各群體在什么時候進行信息的交流和遷移，如果這個時機選擇不當，會降低優化的性能。對于遷移時機，可以采用的方法有：

(1) 各群體每迭代固定的代數后，就進行信息交流和遷移；這種方法的關鍵是選擇合適的固定代數。

(2) 以反映當前種群狀況的某個(些)特性作為遷移依據，當優化達到一定條件時才進行遷移。這種方法的關鍵是評價特性的選擇。

本文采用上述的第1種方法，預先設定一個最大停滯代數d，當各群體都滿足停滯條件時，就暫停優化，進行參數區間的調整。

1.4 改進遺傳算法

由于每個群體都獨立地在相同的參數取值區間進行初始化種群，接著執行遺傳算法的選擇、交叉和變異等操作，當各群體迭代d代后，就暫停進化，進行各群體的交流和更新參數取值區間。

本文算法采用的遺傳算法是對簡單遺傳算法的變異算子進行了改進，采用了差分變異和均勻變異相結合的方法，實現區間外探索和區間內開發。下面介紹改進遺傳算法的主要實現技術。

(1) 編碼。采用實數編碼。設所研究的問題共有n個參數需要優化，則每個參數就作為個體的一個基因，即每個個體由n個基因組成，若干個體就形成了種群。

(2) 選擇算子和交叉算子。選擇算子：由于求解的最小化問題，選用錦標賽選擇算子。錦標賽選擇的核心思想是，一次隨機抽出若干個染色體(個體)，并將這組染色體中適應度最大的個體選入下一代。不斷重復這個過程，直到達到種群規模為止。

交叉算子：采用單點交叉和固定的交叉概率pc，即各個體根據交叉概率pc決定是否參與交配，不參與的個體直接放入下一代；需要參與交配的，則每次選出2個個體交換各自的部分基因，形成2個新的子代個體放入下一代。

(3) 變異算子。變異算子的作用主要是提高種群的多樣性，防止早熟。本文算法采用差分變異和均勻變異相結合的變異算子，除了增加種群的多樣性和提高解的精度外，還提供機會給個體基因向區間外進行不斷探索，這樣有利于解決當解不在初始取值區間時產生的找不到解的問題。對于任一個群體，假設種群規模為popsize，則其中的k個個體的基因采用差分變異，剩下的popsize-k個個體的基因采用均勻變異。

差分變異：在每一個新個體的生成過程中用到了父代多個個體的線性組合。首先在k個個體中隨機選出3個個體，使用式(6)計算新個體在基因位i的取值。

hi=r1(i)+F×(r2(i)-r3(i))

(6)

式中：rj(i)表示個體rj(j=1,2,3)rj的第i個基因值；1≤i≤n，n為個體的基因數目；F為縮放因子，一般是取值范圍為[0,2]的常量，用于控制差分向量的擾動程度。本文F=0.5。差分變異除了提高種群多樣性外，還可以通過縮放因子，給k個個體的某些基因位提供機會在初始取值區間外取值。當更新基因取值區間時，就有機會擴展初始取值區間，解決當正確解不在初始取值區間所帶來的問題。

均勻變異：對于popsize-k個個體中的每個個體，根據變異概率pm選出要變異的基因，然后在該基因的取值區間內產生一個隨機數來取代該基因的值。

2 算法驗證及分析

采用文獻[12]提供的求最小值的8個標準函數作為算例，如表1所示。這8個標準函數f1-f8都是高維問題，維數n=30，其中：f1-f5是單峰函數；f6-f8是存在很多局部最優解的多峰函數。

表1 標準函數

續表1

由于遺傳算法的定義是適應度越高，個體的生存能力越強，所以遺傳算法的適應度函數定義為：

F(x)=-fabs(f(x)-fmin)

(7)

式中：fmin為表1中的“最小值”，也就是誤差越小，對應的適應度就越高，反之亦然。

為了驗證算法的性能，下面將給出參數在兩種情況下的初始取值區間，分別是函數最小值時，其對應的最小值坐標(稱為“參數解”)包含在初始取值區間內(稱為“區間內”)和最小值坐標不包含在初始取值區間內(稱為“區間外”)，如表2所示。

表2 參數的兩種初始取值區間

本文算法(MGADAI)采用多群體并定期交流信息，信息遷移時機的選擇很關鍵，太早交流不利于分享到當前種群更優的信息，太遲交流容易導致算法進化停滯。所以下面首先在不同的遷移時機對算法的性能進行比較，從而選取合適的遷移時機用于后面的算法測試。

另外，MGADAI以基本遺傳算法(SGA)為基礎，采用均勻變異和差分變異相結合的變異算子，同時采用多群體且每個群體獨立執行遺傳算法操作搜索問題的解，并定期交流分享信息，實現參數取值區間的動態調整。因此，為了分析算法各方面的改進性能，MGADAI與單群體遺傳算法(Single Genetic Algorithm， Single-GA)、差分進化遺傳算法(Different Evolution and Genetic Algorithm，DEGA)、簡單遺傳算法(SGA)進行比較，研究分析差分變異、均勻變異、多群體在兩種不同初始取值區間的參數下，對算法最終優化效果的作用。四種算法主要的區別在于變異算子、是否采用多群體技術、遷移時機與調整參數取值區間這四個方面，具體如表3所示。

表3 四種算法的變異算子及其他參數

為了保證比較的有效性，四種算法的相同參數設定如下：種群規模popsize=100，算法最大迭代次數是10 000代，錦標賽選擇算子，單點交叉算子，交叉概率為0.7，變異概率為0.05；同時，為了減少統計誤差，每種算法各運行50次。

算法驗證將從遷移時機、參數區間動態調整過程、與其他3種算法在最優解、均值、方差和收斂速度等方面的性能進行比較；其中，遷移時機的測試是為了驗證多群體遷移時機太早或太晚對優化結果的影響，從而選出合適的遷移時機用于后續的驗證測試。

2.1 遷移時機

將遷移時機在以下4種情況下的優化結果進化比較及分析，其中“最優解”是指50次測試中找到的最優解，“平均值”是指50次結果的平均。其中表4和表5中的d取值表示各群體獨立迭代d代后才進行遷移或交流。

表4 不同遷移時機8個標準函數的最優解和平均值(區間內)

表5 不同遷移時機8個標準函數的最優解和平均值(區間外)函數

可以看出，參數取值區間無論是區間內還是區間外，總體來說d=20和d=50時8個標準函數的最優解總體比d=5或d=100時的結果更優；而對于d=20和d=50兩種情況，當d=20時，函數f3和f5占有明顯的優勢。因此，下面算法的測試選擇的遷移時機選擇d=20，即各群體獨立迭代20代后就進行交流。

2.2 參數取值區間的動態調整

由于8個標準函數都是高維函數，同一個函數的各參數初始取值區間都是相同的，因此，下面將對每個函數只取一維顯示其取值區間的調整過程。另外，由于算法的最大迭代數是10 000，各群體都是迭代20代后才進行交流并調整取值區間，本文算法MGADAI采用4個群體，因此算法終止時共進行了125次區間調整。由于大部分函數經過45次調整后，取值區間變化不大甚至不變，趨于穩定，所以圖4和圖5的參數取值區間調整過程一般選取前45次，有個別函數則需要進行稍多些的調整才基本穩定(例如函數f5)。在圖4和圖5中，橫坐標表示參數取值區間的調整次數，縱坐標表示區間上、下邊界的取值；fi-xi表示函數fi的第i維參數。

(a) f1-x1 (b) f2-x2

(e) f5-x5 (f) f6-x6

(g) f7-x7 (h) f8-x8圖4 8個標準函數的其中一維參數取值區間的動態調整過程(區間內)

(a) f1-x1 (b) f2-x2

(e) f5-x5 (f) f6-x6

(g) f7-x7 (h) f8-x8圖5 8個標準函數的其中一維參數取值區間的動態調整過程(區間外)

由圖4可以看出，參數取值區間是“區間內”的情況下，參數區間的每次調整都是在不斷地收窄，這表明了各群體當前各自找到的最優個體所對應的參數解都比較集中，說明參數的最優解在該區域的概率很大，這時就可以收窄當前取值區間，使得后續的進化在更窄的區域內搜索，大大加快了求解的速度。

由圖5可以看出，參數取值區間是“區間外”的情況下，參數的取值區間不斷地向參數解的方向靠攏，說明各群體當前找到的最優個體對區間調整具有很好的導向性。圖4和圖5驗證了參數取值區間動態調整方法是可行且有效的。

2.3 與其他算法的比較

2.3.1最優解、平均值和標準差

下面分別對參數的初始取值區間為“區間內”和“區間外”這兩種情況，對4種算法各運行50次，并根據50次測試結果統計出最優解(Best)、平均值(Mean)和標準差(Std.Dev)，結果分別如表6和表7所示。

表6 四種算法8個標準函數在區間內的最優解、平均值和標準差

可以看出：

(1) 函數最小值時各參數解包含在初始取值區間內(即表2的“區間內”列)，4種算法的最優解都接近函數的最小值，但接近的程度還是有明顯的不同。

(2) 4種算法中，DEGA在函數f2找到的最優解的精度最高，達到10-55數量級，但從標準差可看出穩定性不太好；這反映了差分變異有潛力找到精度高的解，但不穩定，需要與其他方法結合，發揮差分變異潛力的同時保證其穩定性。

(3) Single-GA與DEGA、SGA相比，Single-GA的優化結果明顯優于它們，說明均勻變異與差分變異相結合的變異算子，有利于提高求解精度。

(4) MGADAI在Single-GA的基礎上，采用了多群體且實施定期交流信息，并根據各群體最優個體的信息動態調整參數取值區間，使得進化更有導向性。因此，MGADAI在7個標準函數找到的最優解都遠遠優于其他3種算法。特別是函數f1、f3、f7和f8的最優解達到10-11數量級以上。同時，7個標準函數在50次運行結果的平均值都非常接近最優解，標準差也很小，表明算法的穩定性好(f5穩定性稍差些)。

表7 四種算法8個標準函數在區間外的最優解、平均值和標準差

可以看出：(1) 當參數的取值區間為“區間外”時，SGA的最優解與函數最小值相差非常大。

(2) DEGA在函數f2表現非常出色，找到的最優解精度很高，在函數f1和f7找到的最優解也還可以。由于DEGA采用差分變異算子，參數的取值有機會突破當前的取值區間，適當在取值區間外進行探索；但從標準差可以看出，穩定比較差。而SGA采用均勻變異算子，參數的取值一直都是在初始取值區間，這說明了當參數解在初始取值區間外時，如果參數的取值區間一直沒有調整，并且遺傳算子沒有機會適當在取值區間外進行探索，這將嚴重影響算法最終的優化效果。

(3) 由于Single-GA采用了均勻變異與差分變異相結合的變異算子，差分變異通過縮放因子F，給某些個體的基因(參數)提供機會在初始取值區間外取值，實現在取值區間外進行搜索，所以Single-GA即使在區間外情況下得到的最優解也相對比較理想。

(4) MGADAI則在Single-GA的基礎上，采用了多群體且定期交流，并動態調整參數的取值區間，因此，即使在區間外的情況下，也能找到與在區間內相差不大的結果，并明顯優于其他3種算法，從標準差可看出算法總體穩定好。因此，MGADAI能有效降低對參數初始取值區間準確度的要求。

2.3.2收斂速度

對于單峰問題，由于不存在陷入局部最優的問題，因此在算法性能上更加注重收斂速度與求解精度；而對于多峰函數，由于存在多個局部最優解，所以算法很容易陷入局部最優，因此算法更加注重的是全局搜索能力。由于求解精度在表6和表7進行了比較，MGADAI取得了明顯的優勢，下面就主要比較4種算法的收斂速度或全局搜索能力。下面選取表1中的單峰函數f1和多峰函數f8對4種算法分別在單峰和多峰問題上的性能進行比較和分析。

程序迭代的最大代數是10 000，為了更清晰地觀察及比較4種算法的尋優結果，在程序結束前設置20個輸出點，表8為f1在區間內和區間外的20個輸出點及其對應的尋優結果。表9為f8在區間內和區間外的20個輸出點及其對應的尋優結果。另外，由于SGA和DEGA在區間外情況下大部分函數(SGA是全部函數)的最優解與函數的最小值相差太大，因此對于區間外情況，只進行MGADAI與Single-GA這兩種算法的收斂速度或全局搜索能力的比較。

表8 四種算法單峰函數f1在區間內和區間外的測試結果

表9 四種算法多峰函數f8在區間內和區間外的測試結果

可以看出：

(1) 對于單峰函數f1，參數取值區間是區間內和區間外時，MGADAI的收斂速度明顯優于其他算法。

(2) 當參數取值區間是區間內時，MGADAI在4 000代已經收斂到最優解；當參數取值區間是區間外時，則在5 000代收斂到最優解；對于多峰函數f8，也同樣獲得明顯的優勢。這說明了算法在求解問題的過程，采用多群體以及定期交流，各個群體能夠及時共享這些階段性成果，并動態調整參數取值區間，通過參數取值區間的調整，后代能在相對更準確的取值區間內搜索，最終使得在單峰函數的收斂速度、多峰函數的全局搜索能力大大增強。

(3) 同時，結合前面表6和表7解的精度，可以得到MGADAI以更快的速度找到更優的值。

2.3.3算法找到的最優解所對應的參數解

前面對4種算法的求解精度和收斂速度進行了分析比較。下面將對表1的8個標準函數找到最優解時(在“區間內”和“區間外”兩種情況下)，該函數的參數x1-x30優化結果進行比較分析。根據表6和表7的比較分析可知SGA和DEGA找到的8個函數最優解總體相對較差，而Single-GA與MGADAI算法找到的最優解更接近，所以下面就只將MGADAI和Single-GA算法的參數優化結果與參數解(圖中“True value”)進行比較，結果分別如圖6和圖7所示。