試驗(yàn)設(shè)計(jì)在遺傳算法參數(shù)配置中的應(yīng)用

范家旭　徐銘潔　孫曉華　陳雪平

摘要：遺傳算法是受生物進(jìn)化論的啟發(fā)而產(chǎn)生的，其是一種高效的隨機(jī)搜索與優(yōu)化算法，具有很好的收斂性，簡(jiǎn)單通用。試驗(yàn)設(shè)計(jì)是使用頻率最高的統(tǒng)計(jì)方法之一，其中正交設(shè)計(jì)是利用標(biāo)準(zhǔn)化正交設(shè)計(jì)表進(jìn)行試驗(yàn)而迅速找到優(yōu)化方案。均勻設(shè)計(jì)是考慮讓試驗(yàn)點(diǎn)在試驗(yàn)范圍盡量均勻地分布，因此試驗(yàn)次數(shù)少。本文將這兩種試驗(yàn)設(shè)計(jì)方法應(yīng)用在遺傳算法的參數(shù)優(yōu)化配置中，模擬結(jié)果表明采用設(shè)計(jì)方案后可以提高遺傳算法的收斂速度及尋優(yōu)性能。

關(guān)鍵詞：遺傳算法；試驗(yàn)設(shè)計(jì)；正交設(shè)計(jì)；均勻設(shè)計(jì)

中圖分類號(hào)：O212.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-7394（2016）02-0005-06

遺傳算法由Bagley J.D于1967年提出，其借鑒生物進(jìn)化過程中優(yōu)勝劣汰、適者生存的機(jī)理來(lái)尋求最優(yōu)解。正交設(shè)計(jì)是利用正交設(shè)計(jì)表進(jìn)行多因素多水平試驗(yàn)的一種高效的試驗(yàn)設(shè)計(jì)方法。均勻設(shè)計(jì)是利用均勻設(shè)計(jì)表進(jìn)行試驗(yàn)的方法，讓試驗(yàn)點(diǎn)完全從均勻性出發(fā)，大大減少試驗(yàn)次數(shù)，縮短試驗(yàn)周期。

在遺傳算法中常常有不同的參數(shù)可以選擇，本文將采用試驗(yàn)設(shè)計(jì)方法來(lái)對(duì)參數(shù)進(jìn)行最優(yōu)搭配。全文共分四部分，第一節(jié)介紹遺傳算法，包括遺傳算法的背景、基本要素和原理、流程等；第二節(jié)介紹試驗(yàn)設(shè)計(jì)，包括正交設(shè)計(jì)和均勻設(shè)計(jì)；第三節(jié)介紹均勻試驗(yàn)設(shè)計(jì)和正交試驗(yàn)設(shè)計(jì)在遺傳算法參數(shù)優(yōu)化中的應(yīng)用；第四節(jié)為總結(jié)。

1 遺傳算法簡(jiǎn)介

1.1 遺傳算法的基本要素

遺傳算法（GA）是受達(dá)爾文的進(jìn)化論的啟發(fā)，其核心思想是“物競(jìng)天擇，適者生存”。在繁殖過程中，生物體會(huì)發(fā)生基因交叉，基因突變等現(xiàn)象，適應(yīng)度低的個(gè)體會(huì)被逐步淘汰，適應(yīng)度高的個(gè)體會(huì)越來(lái)越多。這樣經(jīng)過N代的進(jìn)化后，保存下來(lái)的個(gè)體適應(yīng)度就會(huì)變高。下面先介紹遺傳算法中的幾個(gè)基本概念。

（1）參數(shù)編碼：將解空間的解數(shù)據(jù)轉(zhuǎn)換成基因型串結(jié)構(gòu)數(shù)據(jù)。

（2）初始種群設(shè)定：先隨機(jī)產(chǎn)生N個(gè)初始串結(jié)構(gòu)數(shù)據(jù)，每個(gè)串結(jié)構(gòu)數(shù)據(jù)稱為一個(gè)個(gè)體，Ⅳ個(gè)個(gè)體構(gòu)成一個(gè)群體，以此N個(gè)串結(jié)構(gòu)數(shù)據(jù)作為初始種群開始迭代。

（3）適應(yīng)度函數(shù)設(shè)計(jì)：在遺傳算法中，適應(yīng)度函數(shù)表明了個(gè)體或解的優(yōu)劣性。

（4）遺傳操作設(shè)計(jì)：包括了三個(gè)基本遺傳算子：選擇、交叉和變異。

（ⅰ）選擇：從種群中選出優(yōu)良個(gè)體，使它們的優(yōu)良基因遺傳給下一代；

（ⅱ）交叉：兩條染色體之間通過交叉而重組，形成兩條新的染色體；

（ⅲ）變異：對(duì)在種群中選中的個(gè)體以一定的概率隨機(jī)的改變串結(jié)構(gòu)數(shù)據(jù)中某個(gè)串的值。

1.2 遺傳算法的基本原理

利用遺傳算法求解最優(yōu)化問題，首先應(yīng)對(duì)可行域中的點(diǎn)進(jìn)行編碼，然后在可行域中隨機(jī)挑選一些編碼組成第一代編碼組，并計(jì)算每個(gè)解的目標(biāo)函數(shù)值即編碼的適應(yīng)度。接著，利用選擇機(jī)制挑選編碼作為繁殖前的樣本，且應(yīng)保證適應(yīng)度較高的解能夠保留較多的樣本；而適應(yīng)度較低的解則保留較少的樣本，甚至被淘汰。并進(jìn)行復(fù)制、交叉和變異操作，直到結(jié)束條件得到滿足為止。其基本過程如下：

（1）隨機(jī)生成一定數(shù)目的初始群體，每個(gè)個(gè)體編碼為對(duì)應(yīng)染色體的基因；

（2）定義并計(jì)算每個(gè)個(gè)體的適應(yīng)度函數(shù)，適應(yīng)度函數(shù)值越小，個(gè)體越優(yōu)良，但適應(yīng)度值不得為負(fù)；

（3）執(zhí)行選擇操作；

（4）執(zhí)行交叉操作；

（5）執(zhí)行變異操作；

（6）選擇并輸出最佳個(gè)體及其代表的最優(yōu)解并結(jié)束運(yùn)算，否則轉(zhuǎn)（3）。

2 試驗(yàn)設(shè)計(jì)

試驗(yàn)設(shè)計(jì)主要討論如何合理地安排試驗(yàn)以便對(duì)試驗(yàn)數(shù)據(jù)進(jìn)行有效分析。本文選擇其中兩種方法進(jìn)行分析：正交設(shè)計(jì)和均勻設(shè)計(jì)。

2.1 正交設(shè)計(jì)

正交試驗(yàn)設(shè)計(jì)是一種研究多因素多水平的試驗(yàn)設(shè)計(jì)方法，利用“正交表”進(jìn)行整體設(shè)計(jì)、綜合比較、統(tǒng)計(jì)分析。其特點(diǎn)是：“均勻分散，整齊可比”。用部分試驗(yàn)代替全面試驗(yàn)，通過對(duì)部分試驗(yàn)結(jié)果的分析，從而了解全面試驗(yàn)的情況。是一種高效、經(jīng)濟(jì)、快速的試驗(yàn)設(shè)計(jì)方法。

正交試驗(yàn)常記為L(zhǎng)n（q^p），是利用規(guī)格化的正交表安排試驗(yàn)，再分析試驗(yàn)數(shù)據(jù)的方法。n為試驗(yàn)次數(shù)，即正交表行數(shù)；q為因素的水平數(shù)，即列中出現(xiàn)不同數(shù)字的個(gè)數(shù)；p為最多能安排的因素?cái)?shù)，即正交表的列數(shù)。正交表按水平數(shù)可分為二水平正交表：L₄（2³）、L₈（2⁷）、L₁₂（2¹¹）、L₁₆（2¹⁵）等；三水平正交表：L₉（3⁴）、L₁₈（3⁷）、L₂₇（3¹³）等；四水平正交表：L₁₆（4⁵）等；五水平正交表：L₂₅（5⁶）等。例L₉（3⁴），如表1所示。

2.2 均勻設(shè)計(jì)

均勻設(shè)計(jì)是使試驗(yàn)點(diǎn)在所考察的試驗(yàn)范圍內(nèi)盡量均勻地分布，對(duì)于一個(gè)水平數(shù)為q的正交試驗(yàn)，至少要進(jìn)行q²次試驗(yàn)。若不考慮整齊可比，只考慮均勻性，可以從全面試驗(yàn)中挑選比正交試驗(yàn)設(shè)計(jì)更少的試驗(yàn)點(diǎn)作為代表進(jìn)行試驗(yàn)。

均勻設(shè)計(jì)表是均勻設(shè)計(jì)的一種規(guī)格化的表格，是用數(shù)論方法編制的，并用U_n（q^m）表示，簡(jiǎn)稱u表。表示有n行m列，每列的水平數(shù)是q。其特點(diǎn)是對(duì)任意的n都可以構(gòu)造均勻設(shè)計(jì)表，并且行數(shù)n與水平數(shù)q相同。對(duì)另一類均勻設(shè)計(jì)表U^*_n（q^m），此表避開了當(dāng)n為奇數(shù)時(shí)，最后一行全為n的情況。例U^*₆（6⁶），如表2所示。

每個(gè)均勻設(shè)計(jì)表都有相對(duì)應(yīng)的使用表，優(yōu)先使用均勻度偏差較小的表。

3 試驗(yàn)設(shè)計(jì)在遺傳算法參數(shù)優(yōu)化中的應(yīng)用

影響遺傳算法搜索優(yōu)化效果的因素有很多，通過比較篩選，本文選擇種群規(guī)模Ⅳ、交叉概率P_c、變異概率P_m這3個(gè)參數(shù)作為優(yōu)化對(duì)象；為了兼顧精度與試驗(yàn)速度，確定每個(gè)因素的水平數(shù)為6個(gè)，各參數(shù)常用的取值范圍為：N（40～260）、P_c（0.25～0.85）、Pm（0.01～0.09）。

3.1 均勻設(shè)計(jì)在參數(shù)優(yōu)化中的應(yīng)用

3.1.1 選擇合適的均勻設(shè)計(jì)表

根據(jù)因素和水平優(yōu)先選取均勻設(shè)計(jì)表U^*₆（6⁴）。

3.1.2 實(shí)驗(yàn)安排及結(jié)果

本文選取Schaffer2 Function函數(shù)和Rastrigin函數(shù)進(jìn)行函數(shù)測(cè)試。

（1）Schaffer2Function

（2）Rastrigin函數(shù)

對(duì)于Schaffer2 Function函數(shù)，由表3可知，在GA參數(shù)優(yōu)化的均勻設(shè)計(jì)表中最佳參數(shù)組合為第6組，即種群規(guī)模N為260，交叉概率只為0.75，變異概率P_m為0.04，此時(shí)最優(yōu)解為0.0013，平均解為0.0013。由表4可知，對(duì)于Rastrigin函數(shù)而言，最佳參數(shù)組合為第6組，即種群規(guī)模N為260，交叉概率P_c為0.75，變異概率P_m為0.04，此時(shí)最優(yōu)解為0.0095，平均解為0.0125。

3.2 正交設(shè)計(jì)在參數(shù)優(yōu)化中的應(yīng)用

3.2.1 選擇合適的正交表

在遺傳算法參數(shù)優(yōu)化問題中，滿足條件的最小正交表為L(zhǎng)₂₅（5⁶）。（注：由于沒有6水平的正交表，故本次試驗(yàn)選擇5水平）

3.2.2 試驗(yàn)安排及結(jié)果

對(duì)于Schaffer2 Function函數(shù)，由表5可知，采用正交設(shè)計(jì)法后，GA參數(shù)優(yōu)化的最佳參數(shù)組合為第25組，即種群規(guī)模N為200，交叉概率P_c為0.75，變異概率P_m為0.04，此時(shí)的最優(yōu)解為0.0013，平均解為0.0013；由表6可知，Rastrigin函數(shù)最佳組合為第11組，即種群規(guī)模N為120，交叉概率P_c為0.25，變異概率P_m為0.03，此時(shí)的最優(yōu)解為0.0095，平均解為0.0098。在文獻(xiàn)中，Ras-trigin函數(shù)的最優(yōu)解為0.0134，而正交設(shè)計(jì)法配置的參數(shù)結(jié)果最優(yōu)為0.0095，明顯小于其最優(yōu)解，由此可見采用試驗(yàn)設(shè)計(jì)法能在一定程度上優(yōu)化遺傳算法的結(jié)果。

3.3 結(jié)論

從表7可以看出，對(duì)于Schaffer2 Function函數(shù)，不論是均勻設(shè)計(jì)還是正交設(shè)計(jì)，用試驗(yàn)設(shè)計(jì)進(jìn)行GA參數(shù)配置所得的最優(yōu)解和平均解都優(yōu)于隨機(jī)產(chǎn)生的參數(shù)。

從表8中可以看出，對(duì)于Rastrigin函數(shù)，不論是均勻設(shè)計(jì)還是正交設(shè)計(jì)，用試驗(yàn)設(shè)計(jì)進(jìn)行GA參數(shù)配置所得的最優(yōu)解和平均解都優(yōu)于隨機(jī)產(chǎn)生的參數(shù)，而正交設(shè)計(jì)所的結(jié)果又比均勻設(shè)計(jì)的更精確。

此外，兩種試驗(yàn)設(shè)計(jì)設(shè)定參數(shù)的遺傳算法都收斂得很快，而隨機(jī)調(diào)整法最慢。這也進(jìn)一步證明將試驗(yàn)設(shè)計(jì)應(yīng)用在遺傳算法的參數(shù)優(yōu)化配置中可以提高遺傳算法的收斂性及尋優(yōu)性能。

4 結(jié)語(yǔ)

由于遺傳算法中種群大小N，交叉概率只，變異概率P_m等參數(shù)在進(jìn)行實(shí)驗(yàn)室都是隨機(jī)產(chǎn)生的，故本文對(duì)遺傳算法參數(shù)優(yōu)化配置進(jìn)行了研究。分析Schaffer2 Function函數(shù)和Rastrigin函數(shù)的模擬結(jié)果可以看出，不論是通過正交設(shè)計(jì)還是均勻設(shè)計(jì)配置的參數(shù)所得到的測(cè)試結(jié)果都明顯優(yōu)于隨機(jī)產(chǎn)生的參數(shù)的測(cè)試結(jié)果。因此，將試驗(yàn)設(shè)計(jì)應(yīng)用在遺傳算法的參數(shù)優(yōu)化配置中會(huì)提高遺傳算法的收斂性及尋優(yōu)性能。

責(zé)任編輯 祁秀春