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

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

關鍵詞：遺傳算法；試驗設計；正交設計；均勻設計

中圖分類號：O212.6 文獻標識碼：A 文章編號：2095-7394（2016）02-0005-06

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

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

1 遺傳算法簡介

1.1 遺傳算法的基本要素

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

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

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

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

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

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

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

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

1.2 遺傳算法的基本原理

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

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

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

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

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

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

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

2 試驗設計

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

2.1 正交設計

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

正交試驗常記為Ln（q^p），是利用規(guī)格化的正交表安排試驗，再分析試驗數(shù)據(jù)的方法。n為試驗次數(shù)，即正交表行數(shù)；q為因素的水平數(shù)，即列中出現(xiàn)不同數(shù)字的個數(shù)；p為最多能安排的因素數(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 均勻設計

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

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

每個均勻設計表都有相對應的使用表，優(yōu)先使用均勻度偏差較小的表。

3 試驗設計在遺傳算法參數(shù)優(yōu)化中的應用

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

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

3.1.1 選擇合適的均勻設計表

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

3.1.2 實驗安排及結(jié)果

本文選取Schaffer2 Function函數(shù)和Rastrigin函數(shù)進行函數(shù)測試。

（1）Schaffer2Function

（2）Rastrigin函數(shù)

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

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

3.2.1 選擇合適的正交表

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

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

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

3.3 結(jié)論

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

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

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

4 結(jié)語

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

責任編輯 祁秀春