3.2　求解過程

求解函數優化問題的學習型遺傳算法^[181]的優化流程如圖3.1所示。學習型遺傳算法的改進之處主要體現在：將多種不同操作算子集成到學習型遺傳算法中；基于算子績效知識動態地選擇下一步操作中需要使用的操作算子。

3.2.1　種群初始化

本書采用浮點數方式對函數優化問題的解進行編碼。在浮點數編碼方式下，每個一維浮點數組（染色體）對應于函數優化問題的一個解；所有染色體的長度都等于優化問題的維度。在求解函數優化問題之前，通常很難知道全局最優點的分布區域，需要在種群初始化階段就均勻地、離散地搜索整個可行空間。正交表在所有可能的組合中指定了均勻離散分布的數量規模比較小的組合群，能產生一組比較好的初始種群^[180]。因此本書采用正交設計方法來產生學習型遺傳算法的初始種群。

（1）根據公式（3.5）將優化問題的可行空間[L，U]分割成B個子空間。

這里，L=[l₁，l₂，…，l_n]^T和U=[u₁，u₂，…，u_n]^T分別表示優化問題n個自變量的下邊界和上邊界；B為設計參數；I_k表示第k位為1，其他位為0的n維列向量；L_i和U_i分別表示類似于L和U的n維列向量。優化問題的可行空間[L，U]被分割成B個子空間，即[L₁，U₁]，[L₂，U₂]，…，[L_B，U_B]。

（2）按照公式（3.6）將每個子空間內的每個自變量進行離散化。假設自變量x_i的定義域為[l_i，u_i]，根據設計參數Q₁（奇數），將x_i量化成Q₁個水平a_i1，a_i2，…，，a_ij的計算方式如公式（3.6）所示。

（3）從每個子空間中選出M₁個染色體。構造正交表，n為優化問題的維數，，J₁是滿足條件的正整數；從這個組合中選取M₁個組合，應用這些組合生成M₁個染色體。

（4）根據適應度值從M₁B個潛在染色體中選擇最優秀的G個（種群規模）染色體作為初始種群。

3.2.2　選擇操作

選擇操作從當前種群中選出優良個體，將它們作為父代為下一代繁殖子孫，故被稱為再生操作。選擇操作的原則是向適應度較強的個體賦予較大的生存機會。選擇操作根據個體對環境的適應度來決定其繁殖量，也稱為非均勻再生（differential reproduction）。本書采用輪盤賭法來執行學習型遺傳算法的選擇操作。

3.2.3　交叉操作

求解函數優化問題的學習型遺傳算法^[181]中用到了5種交叉算子：“取大”“取小”交叉算子^[213]、量化正交交叉算子^[180]、算術交叉算子^[214]、單點交叉算子和雙點交叉算子。這5種交叉算子的基本信息如表3.1所示，這些交叉算子的操作方式描述如下。假設兩個父代個體為

3.2.3.1　“取大”“取小”交叉算子

采用“取大”“取小”交叉算子執行交叉操作后，新產生的兩個子代個體為

3.2.3.2　量化正交交叉算子

兩個父代個體決定的求解空間[l_parent，u_parent]為

按照公式（3.6）將求解空間[l_parent，u_parent]離散化成Q₂份。隨機生成F–1個整數1＜k₁＜k₂＜…＜k_F–1＜n；對于每個父代個體來講，可產生F個因素

生成正交表，，J₂是滿足條件的最小正整數；從個組合中選取M₂個組合；應用這些組合生成M₂個潛在子代。從潛在子代個體和父代個體中，選擇適應度值最好的兩個個體，作為本次交叉操作的結果。

3.2.3.3　算術交叉算子

產生一個位長為n的雜交模板s₁，s₂，…，s_n，其中0表示不雜交，1表示雜交。依據雜交模板對兩個父代個體進行雜交，雜交方式為算術雜交，即生成n個在[0，1]區間上服從均勻分布的隨機數t₁，t₂，…，t_n。按照雜交模板對這組隨機數進行修改，即將模板與隨機數組上相同位置的數字相乘，得到一組交叉系數r₁=s₁t₁，r₂=s₂t₂，…，r_n=s_nt_n。采用算術交叉算子執行交叉操作后，新產生的兩個子代個體為

3.2.3.4　單點交叉算子

在區間[0，1]上產生一個隨機數r，采用單點交叉算子執行交叉操作，新產生的兩個子代個體為

3.2.3.5　雙點交叉算子

在區間[0，1]上產生兩個隨機數r₁和r₂，采用雙點交叉算子執行交叉操作，新產生的兩個子代個體為

在每次交叉操作之前，學習型遺傳算法都基于交叉算子的績效知識來動態地選擇本次交叉操作中需要使用的交叉算子；在每次交叉操作之后，學習型遺傳算法將基于當前交叉操作的結果（采用哪種算子執行了交叉操作，當前交叉操作是否得到改進解）來更新交叉算子的績效知識。通過交叉算子績效知識的更新與應用，學習型遺傳算法盡可能地選擇適合當前優化問題的交叉算子執行后續的演化過程。

在標準遺傳算法中，通常給所有個體都賦予一個常數交叉概率，這種方式帶有一定盲目性和隨機性。依據每代個體的適應度值來調整交叉概率，使交叉沿著有利于算法收斂的方向進行。采用公式（3.7）來計算每個個體的交叉概率：

這里，Pc[i]代表第i個個體的交叉概率，f_i表示第i個個體的適應度值，f_min和f_avg分別表示當前種群中個體適應度值的最小值和平均值。假設個體i和個體j的交叉概率分別為Pc[i]和Pc[j]，如果個體i和個體j被選作父代個體來進行交叉操作，則以概率min{Pc[i]，Pc[j]}作為依據判斷它們是否要進行交叉操作。

3.2.4　變異操作

求解函數優化問題的學習型遺傳算法^[181]中用到了8種變異算子：隨機數變異算子、隨機一維變異算子^[215]、附加擾動變異算子^[215]、多位互換變異算子^[215]、逆序變異算子^[215]、i步循環移位變異算子^[215]、外拋變異算子^[216]和高斯變異算子^[180]。這8種變異算子的基本信息如表3.2所示。假設執行變異操作之前的個體為

P=（p₁，p₂，p₃，p₄，p₅，p₆，p₇，p₈）

對于當前優化問題，假設第i（1≤i≤8）個變量的可行區間為[l_i，u_i]。

3.2.4.1　隨機數變異算子

在區間[1，8]上產生隨機整數r，在區間[l_r，u_r]上產生隨機數ε，采用隨機數變異算子執行變異操作。假設隨機數r=3，則子代個體為

P′=（p₁，p₂，ε，p₄，p₅，p₆，p₇，p₈）

3.2.4.2　隨機一維變異算子

在區間[1，8]上產生隨機整數r，在區間[0，1]上產生隨機數ε，令ε′=max{l_r，min{u_r，p_r+ε}}，采用隨機一維變異算子執行變異操作，假設隨機數r=5，則子代個體為

P′=（p₁，p₂，p₃，p₄，ε′，p₆，p₇，p₈）

3.2.4.3　附加擾動變異算子

在區間[0，1]上產生8個隨機數ε₁，ε₂，…，ε₈，令（1≤i≤8），采用附加擾動變異算子執行變異操作，新產生的子代個體為

3.2.4.4　多位互換變異算子

采用多位互換變異算子執行變異操作時，可能出現以下兩種情況：

（1）在區間[1，8]上產生隨機整數j，將第k（k=1，2，…，8–j）位的基因與第k+j位的基因進行互換。假設隨機數j=3，則子代個體為

P′=（p₄，p₅，p₆，p₇，p₈，p₃，p₁，p₂）

假設隨機數j=5，則子代個體為

P′=（p₆，p₇，p₈，p₄，p₅，p₁，p₂，p₃）

（2）在區間[1，8]上產生兩個隨機整數i和j，將第k（k=1，2，…，i）位的基因與第k+j（如果k+j＞8，則為k+j–8）位的基因進行互換，假設隨機數為i=3和j=4，則子代個體為

P′=（p₅，p₆，p₇，p₄，p₁，p₂，p₃，p₈）

假設隨機數為i=5和j=4，則子代個體為

P′=（p₁，p₆，p₇，p₈，p₅，p₂，p₃，p₄）

3.2.4.5　逆序變異算子

在區間[1，8]上產生兩個隨機整數1≤i＜j≤8，采用逆序變異算子執行變異操作，假設隨機數為i=3和j=6，則子代個體為

P′=（p₁，p₂，p₆，p₅，p₄，p₃，p₇，p₈）

3.2.4.6　i步循環移位變異算子

在區間[1，8]上產生隨機整數i，采用i步循環移位變異算子執行變異操作，假設隨機數為i=3，則子代個體為

P′=（p₆，p₇，p₈，p₁，p₂，p₃，p₄，p₅）

3.2.4.7　外拋變異算子

在區間[–1，1]上產生8個隨機整數r_i（外拋方向），在區間上產生8個隨機數s_i（外拋步長），令，采用外拋變異算子執行變異操作，則子代個體為

3.2.4.8　高斯變異算子

在區間上產生隨機數δ，產生8個方差為δ均值為0的正態隨機數r₁，r₂，…，r₈，令，采用高斯變異算子執行變異操作，則子代個體為

在每次變異操作之前，學習型遺傳算法都基于變異算子的績效知識來動態地選擇本次變異操作中需要使用的變異算子；在每次變異操作之后，學習型遺傳算法將基于當前變異操作的結果（采用哪種算子執行了變異操作，當前變異操作是否得到改進解）來更新變異算子的績效知識。通過變異算子績效知識的更新與應用，學習型遺傳算法盡可能地選擇適合當前優化問題的變異算子執行后續的演化過程。

在標準遺傳算法中，通常給所有個體都賦予固定的變異概率，這種方式帶有一定盲目性和隨機性。本書依據每代個體的適應度值來調整變異概率，使變異沿著有利于算法收斂的方向進行。本書采用公式（3.8）來計算每個個體的變異概率：

這里，Pm[i]代表第i個個體的變異概率，f_i表示第i個個體的適應度值，f_min和f_avg分別表示當前種群中個體適應度值的最小值和平均值。

3.2.5　災變操作

求解函數優化問題的學習型遺傳算法^[181]中用到了5種災變（局部優化）算子：動態更新災變算子、免疫災變算子^[217]、單純形災變算子^[218]、混沌搜索災變算子^[219]和最速下降災變算子^[220]。這5種災變算子的基本信息如表3.3所示。

3.2.5.1　動態更新災變算子

采用隨機方法產生200個可行方案（優化問題的解），計算這200個可行方案的目標值，從這200個可行方案中選出最好的G/2（當前種群規模的一半，四舍五入使之為整數）個優秀個體，采用挑選出來的G/2個優秀個體替換當前種群中最差的G/2個個體。采用動態更新災變算子進行局部優化操作，既可向當前種群中注入一些新的個體；也可有效保證當前種群的多樣性。

3.2.5.2　免疫災變算子

免疫災變操作的核心在于如何抽取疫苗和利用疫苗。疫苗的實質就是對最優個體在某一分量上值的估計。免疫災變包括疫苗提取、接種疫苗和免疫選擇三個步驟。接種疫苗是為了提高個體的適應度，免疫選擇則是為了防止群體的退化。

（1）疫苗提取。疫苗提取可通過利用所求問題的一些特征信息或對問題的先驗知識來進行。先驗知識可以是最優個體某些分量x_i的大概取值范圍，也可以是一些分量之間的制約關系。為了提高算法的通用性與應用的便利性，同時為了避免在某些情況下，對所求解的問題一時很難形成較為成熟的先驗知識，從而無法正確地提取疫苗或為了提取正確的疫苗而要做大量的工作，本書提出了一種自適應疫苗抽取算法。其過程是：將每個變量x_i的可行區間[l_i，u_i]平均分割成20個子區間，對每代的最優個體進行分析，統計這些最優個體中每個分量x_i的取值落入各個子區間的次數。本書將這些共同特點和有效信息看作疫苗庫H。

（2）接種疫苗。對第k代種群P^（k）接種疫苗，就是按照比例α（0≤α≤1）（將α設置為0.6）從種群P^（k）中隨機抽取G_a=α·G個個體來接種疫苗。給個體X=（x₁，x₂，…，x_n）接種疫苗，就是按照先驗知識（疫苗庫H）強制性修改個體X中某些分量x_i的取值。在對個體接種疫苗時，首先需要判斷對哪些基因位進行接種，然后從疫苗庫H中抽取有用疫苗對這些基因位接種疫苗。在判斷哪些基因位需要進行接種操作時，可隨機生成一個長度為n的布爾數組R（對于數組R的每個分量，以20%的概率取1，80%的概率取0），如果R（i）=1，則第i個基因位需要執行接種操作；反之，第i個基因位不需要執行接種操作。在從疫苗庫H中選取分量x_k的疫苗時，首先按照概率選取一個合適的子區間，這里a（i）表示在前期演化過程中已經獲得的準最優解中分量x_k的取值落入到第i個子區間內的次數；然后在所選子區間上產生隨機數R_p，R_p就是從疫苗庫H中選取出來的分量x_k的疫苗。

（3）免疫選擇。對接種疫苗的個體進行檢測，若其適應度比原來退化了，這時該個體將被接種前的個體所替代；反之，接種后的個體將進入下一代種群。免疫選擇對算法的收斂性將起到決定性作用，對加強免疫災變算子的功能有著積極的作用，具有較強的魯棒性。

3.2.5.3　單純形災變算子

單純形方法針對n維向量給出n+1個點，將選取的n+1個點作為n維單純形的n+1個頂點；求取n+1個頂點上的函數值，找出其中帶有最大函數值的頂點（最高點）、最小函數值的頂點（最低點），僅低于最高點的頂點（次高點）。通過反射、擴展和壓縮求取一個新的較好的頂點代替最高點，形成一個新的單純形；或通過向最低點收縮形成一個新的單純形，以逐步逼近函數的極小值點。采用單純形災變算子執行局部優化操作的具體步驟如圖3.2所示。單純形災變算子中的參數設置為a_m=1.2，a_c=0.5，a_e=2，ε=10^–6。

3.2.5.4　混沌搜索災變算子

混沌是非線性系統中的普遍現象，具有一些特異性質：如混沌運動能在一定范圍內按其自身規律不重復地遍歷所有狀態（遍歷性）；初值條件極其微弱的變化會引起系統行為的巨大變化，即對初值變化強烈的敏感性。混沌優化算法容易跳出局部解，計算效率高。假設某系統的運動狀態為

這里，0≤t₀＜1，k=0，1，2，…，u為控制變量，u=4時公式（3.9）刻畫的系統完全處于混沌狀態。混沌搜索災變算子的基本步驟如圖3.3所示。混沌搜索災變算子中的參數設置如下：c_i和d_i均為區間[0，10]上的隨機數，每次混沌搜索的最大迭代次數為200次。

3.2.5.5　最速下降災變算子

采用最速下降災變算子執行局部優化操作的具體步驟如圖3.4所示。最速下降災變算子中的參數設置為δ=0.1，ε=10^–6，β=0.5，α=2。

在每次災變操作之前，學習型遺傳算法都基于災變算子的績效知識來動態地選擇本次災變操作中需要使用的災變算子；在每次災變操作之后，學習型遺傳算法將基于當前災變操作的結果（采用哪種算子執行了災變操作，當前災變操作有沒有得到改進解）來更新災變算子的績效知識。通過災變算子績效知識的更新與應用，學習型遺傳算法盡可能地選擇適合當前優化問題的災變算子來執行后續的演化過程。

在每次迭代之后，學習型遺傳算法都執行一次災變操作，從而盡可能地提高當前種群的質量。局部優化操作對于初始解是比較敏感的：如果初始解選的比較合適，局部優化操作就能快速地得到最優解。鑒于此，在每次災變操作之前，都從當前種群中選擇一些比較優秀（通常從適應度較高的前30%的個體中隨機選擇）的個體作為局部優化操作的初始解。如果在局部操作中得到了改進解，則用這些改進解來替換當前種群中適應度最差的一些個體。

3.2.6　終止條件

當下列條件之一滿足時，求解函數優化問題的學習型遺傳算法^[181]立即終止：如果優化過程中得到的全局最優解與實際最優解的相對誤差小于0.001%；如果優化過程中得到的全局最優解在連續SI次迭代內沒有被改進；如果預先設置的MI次（最大迭代次數）迭代已經完成。