模糊自適應并行遺傳算法在函數優化中的應用

潘家文，錢 謙 ，伏云發，馮 勇

1(昆明理工大學 信息工程與自動化學院，昆明 650500)

2(昆明理工大學 云南省計算機技術應用重點實驗室，昆明 650500)

1 引 言

遺傳算法(Genetic Algorithm，GA)[1]是20世紀70年代初期由美國Michigan大學Holland提出來的借鑒生物界自然選擇思想和自然遺傳機制的一種全局隨機搜索算法.它把問題的可能解看做個體，多個個體組成種群，算法運行時按照預設的進化策略使種群在遺傳算子的控制下通過選擇、交叉、變異等運算操作進行尋優，適應度高的個體被遺傳繼承下來，適應度低的個體不斷被淘汰，直到產生最優或近似最優解.GA已廣泛應用于機器學習，控制，優化等領域[2-4].

GA以適應度函數作為搜索準則，能夠同時搜索多個點，具有較好的并行尋優能力，但是該算法也存在著“早熟”收斂和收斂速度慢等缺陷.目前已經提出了許多解決這一問題的方法，如自適應機制[5]、將遺傳算法與其他算法結合[6]等，這些方法都取得了較好的效果.

本文首先結合分析GA算法缺陷產生的原因對已有相關研究的不足之處進行討論，然后在前人研究基礎上提出了更加有效的優化算法.

2 相關研究

交叉概率Pc和變異概率Pm是控制交叉操作、變異操作及影響遺傳算法性能與收斂的關鍵控制參數[7].GA易陷入局部收斂的一個原因就是Pc和Pm的具體數值難以選取.傳統遺傳算法(Standard GA，簡稱SGA)的Pc和Pm具有固定的數值，如果取值過高，雖然有利于跳出局部最優，增大找到全局最優的可能性，但是會破壞現有的優良個體，使算法淪為隨機搜索算法;如果取值過低，又不容易產生新的個體，容易導致進化停滯不前.SGA對于不同優化問題需要反復實驗來確定Pc和Pm，過程異常繁瑣且效果有限.為了解決這個問題，多種群并行機制被引入遺傳算法中，通過對不同種群配置不同的參數能夠有效的控制子種群的獨立演化特性.文獻[8]將局部搜索與并行機制相結合提出一種改進的混合遺傳算法并用于求解課程排班問題.Zhou Yu[9]將改進的多種群并行遺傳算法用于列車組調度優化問題.文獻[10]采用多種群并行機制混合局部優化算法來加強算法的性能.但是上述方法仍存在一些問題，例如，算法中的單個種群均采用了固定的進化策略，不能根據該種群所處進化狀態動態調整進化策略，使得種群中大部分染色體進化效果較差.對于具有較大Pc和Pm數值的種群來說，雖然容易豐富群體多樣性，擴大種群的搜索范圍，但是其中有希望成為全局最優解的優秀個體的基因容易被破壞，使種群無法保持穩定，難以收斂.對于具有較小Pc和Pm數值的種群來說，雖然能夠充分利用現有染色體的基因，但其跳出局部最優解探尋全局最優解的可能性較小，并且也缺少對遷移來的優秀個體進行進一步開發的能力.

GA易陷入“早熟”收斂的另一個原因是群體多樣性不足，使得種群的搜索范圍被限制，算法只能在有限范圍內找到最優值，而不能得到滿意的全局最優值.為解決上述問題，需要保證算法在計算過程中種群的多樣性不能過快喪失，利用多樣性來保證種群的搜索范圍.目前已有的GA研究多數采用隨機初始化方法產生種群，隨機初始化方法會產生多樣性差，染色體分布不均勻的種群[11].文獻[12]提出半初始化方法，該方法雖然豐富了種群多樣性，但也增加了計算復雜度，還影響了種群的穩定性.文獻[13]提出在隨機產生的染色體集合基礎上通過海明距離作為標準約束個體來產生初始種群，但是若一開始隨機產生的種群多樣性就比較差，那么經過挑選后的種群仍無法避免多樣性較差的局面，且無法保證種群能夠散布在整個解空間，算法在進化時仍然容易陷入“早熟”收斂.若通過擴大種群規模的方法來解決多樣性問題，那么算法收斂速度又會受到極大影響.此外，僅通過改進初始化來提高種群多樣性的方法具有局限性，在進化過程中由于遺傳操作的作用會使得種群獲得的多樣性不斷喪失，種群在進化中后期的搜索范圍仍會被限制.為解決該問題，Cheng R等[14]提出了一種競技方法淘汰相似度較高的劣質染色體來保持種群的多樣性.文獻[15]也使用了競技方法作為一種約束來保證算法進化過程中種群具有豐富的多樣性.

作為GA算法最核心的3種遺傳操作之一，選擇操作是控制群體多樣性及收斂能力平衡的關鍵.目前大多數研究采用比例選擇作為選擇策略，但采用該策略會產生比較大的抽樣誤差.算法初期，優良個體的適應度與其他個體的適應度差距較大，按比例選擇策略進行選擇操作時，優秀個體有更大概率被選入種群并迅速復制使算法陷入“早熟”收斂;而在進化過程中，個體之間的適應度差距不斷縮小，優秀個體被選中的概率降低，影響收斂速度.為解決上述缺陷，適應度尺度變換方法被應用到遺傳算法中，通過改變個體之間的適應度的相對差異性來控制選擇操作的靈敏度，即通過縮放個體適應度在群體適應度區間的所占比例來改變個體被選入下一代的概率，該方法在算法進化前期降低了優秀個體被選擇的概率，增加了其他個體被選擇的概率，保護了種群的多樣性，在一定程度上避免了算法陷入“早熟”收斂的現象;而在算法進化中后期則提高了優秀個體被選擇的概率，加強了算法的收斂速度.但是若采用固定數值的尺度變換方法，往往不能取得令人滿意的效果，為使適應度的變換在算法的運行過程中更加合理，不少學者對適應度尺度變換的方法做出了改進.文獻[16]提出了對適應度進行指數變換來克服選擇操作對遺傳過程的制約，文獻[17]采用線性變換法對適應度進行尺度變換來克服比例選擇策略的缺陷.

GA不善于對局部區域進行細致搜索，導致該算法的局部搜索能力較差，影響算法的尋優性能.將局部搜索能力較強的優化算法如單純形法[18]、模擬退火算法[19]等作為局部搜索策略加入遺傳算法中，能夠提高算法收斂速度，減少遺傳代次，是提高遺傳算法運行效率和求解質量的一種有效手段.文獻[19]采用模擬退火思想對遺傳算法的選擇算子進行了改進并提出了新的變異算子用于搜索約束條件下的解空間，這一優化方法雖然一定程度上提升了算法的局部搜索能力，但本質上仍是用遺傳操作對染色體進行局部搜索，其搜索仍然不夠精細.文獻[20]使用模擬退火算法作為遺傳算法的局部搜索策略，該方法通過隨機擾動個體代表的可能解實現更加細致的搜索.但該方法的不足之處在于，Metropolis準則雖然使算法存在能夠探索個體其他方向鄰域結構的可能性，但每次只探索某單一方向的鄰域結構，若能產生稍好解就會以較大概率接收，對個體所在解空間的探索不夠充分.

為設計一種更加高效的遺傳算法，本文在前人研究基礎上做出改進，提出了一類模糊自適應的并行遺傳算法(FAPGA，Fuzzy Adaptive Parallel Genetic Algorithm).具體方法如下:

1)算法框架采用了模糊自適應的并行機制，該機制提升了算法克服Pc和Pm數值難以選取及早熟收斂等問題的能力，能夠根據染色體之間的個體差異性及種群進化情況自適應調整進化策略.

2)多樣性調整采用基于距離調整的種群初始化方法及競爭策略，初始化方法能夠使種群內染色體分布在解空間的不同區域，保證初始解的多樣性.競爭策略作為一種約束條件持續調整種群在進化過程中喪失的多樣性，使種群在進化過程中能夠保持豐富的多樣性及設置合理的搜索范圍.

3)算法進行選擇操作時采用改進的適應度變換方法，該方法使用更加穩定的尺度標準，并能夠非線性的控制適應度變換，使變換后的新適應度更貼近算法進化的要求.

4)算法局部搜索采用了基于模擬退火構建的Baldwin learning局部搜索策略，該策略能夠充分探索個體所在解空間區域，提升算法的局部搜索能力.

3 算法基本思想

在本節中，首先介紹算法的編碼方式，然后說明模糊自適應的并行機制的基本思想，接著對算法的初始化方法及競爭策略進行描述，最后對改進的尺度變換方法及局部搜索策略進行說明.FAPGA以并行機制為算法的基本框架，并將多種改進方法融入算法的不同環節中形成一種新的改進遺傳算法.

算法的設計首先要考慮編碼方案.遺傳算法有不同的編碼形式，多數可以總結為二進制碼方案(二進制碼，格雷碼等)和十進制碼方案(實數編碼、整數編碼等).相較十進制編碼，二進制編碼在相同種群規模下進化時變化更加多元，有更強的探索新解空間的能力.而十進制編碼在當前個體所映射定義域中的搜索范圍更大，相比較二進制編碼能更充分的探索當前解空間.FAPGA采用混合編碼方案，即二進制編碼和十進制編碼混用.具體來說，局部搜索操作使用十進制編碼進行，其余操作以二進制碼進行.將兩種編碼混合起來，在不同作用的基因操作中使用不同的碼制，能充分發揮不同編碼方案的優勢，更好的提升算法性能.

3.1 模糊自適應的并行機制

3.1.1 并行機制的基本原理

在遺傳算法中引入并行機制(Parallel mechanism)能夠有效結合GA的天然并行性和計算機的快速并發性，是近年來提出的改進算法性能的一個重要方向.目前遺傳算法并行機制的模型包括4個基本類型:主從式模型(Master-slave Model)、細粒度模型(Fine-grained Model)、粗粒度模型(Coarse-grained Model)、及混合模型(Hybrid Model).

主從式模型并不改變遺傳算法的框架結構，而是采用單一種群，所有個體的進化均在主處理器上以遺傳操作進行，而將開銷較大的適應度評估等計算交付給多個從處理器并行處理，該模型簡單且易實現，能夠有效減少算法運行時間.

細粒度模型采用某種鄰域模型將單一種群劃分為多個子種群，并把每個種群交付給不同處理器獨立演化，算法運行過程中不同種群之間按照其拓撲結構在邊界上進行通信來交換信息.該模型能夠有效減少算法運行時間并能夠充分發揮遺傳算法的并行特性.

本文提出的并行機制采用了粗粒度模型，該機制通過多個種群代替單一種群并行演化來擴大搜索范圍，其中每個種群自成一個演化單位按照不同的進化策略獨立進化，當算法遺傳代次達到一定周期時會進行個體遷移，即各種群之間會交換一定數目的優秀個體.該并行機制對不同種群配置不同的算法參數而有效的控制種群的獨立演化特性，保證了種群進化過程中的多樣性，并通過遷移來實現各種群之間相互協調，提升了算法的性能.

混合模型是由上述模型混合形成的結構，如粗粒度-細粒度、粗粒度-主從式等模型.采用混合模型的并行遺傳算法更具普遍性，但算法也更為復雜，實現代價較高.

3.1.2 并行機制的進化策略

目前已有遺傳算法改進可以總結為編碼、微觀遺傳策略(對遺傳算子及參數選擇的改進)、宏觀遺傳策略(對算法運行機制的改進).本文研究的是宏觀多種群并行機制而并非具體的進化策略，因此并行機制采用文獻[21]所提出的較簡單的進化策略并做出改進.具體來說，將數值較大的Pm和數值較小的Pc稱為探索策略(Exploration strategy)，并且在遺傳操作上選擇先進行變異操作再進行交叉操作，最后執行選擇復制操作，該進化策略有利于種群跳出局部最優，探索新的解空間.將數值較小的Pm和數值較大的Pc稱為開發策略(Development strategy)，該策略首先執行交叉操作再進行變異操作，最后執行選擇復制操作，該策略能夠重組現有基因產生新的個體以期待獲得更好的性狀改變.普通策略(Normal strategy)采用介于開發策略和探索策略之間程度的Pc和Pm，在進化操作上采用SGA的選擇復制、交叉、變異操作，該策略兼具以上兩者的功能.此外，FAPGA使用公共種群作為一個容器不斷接收其他種群傳遞過來的優秀個體并進一步開發.首先，給出進化潛能的定義:

定義1.個體xi通過局部搜索(詳見3.4節)展現的進化潛能由公式(1)定義:

Q(xi)=ω(1-Kλ)(f′(xi)-fmax)

(1)

式(1)中，ω表示進化潛能的權重，K表示溫度衰減系數，λ表示新解搜索次數，f′(xi)表示染色體xi經局部搜索后的最優解，fmax表示種群適應度最大值.個體的進化潛能與新解搜索次數及最優解的適應度相關，搜索次數越少，進化潛能越大.

公共種群首先對優秀個體進行交叉操作，交叉結束后所有個體按照局部搜索策略進行搜索并計算進化潛能，然后按式(2)更新適應度，最后按照適應度選擇種群大小數目的染色體進入下一代.

f(xi)=f(xi)+Q(xi)

(2)

公共種群的目的在于使種群能夠探索個體周圍的解空間，挖掘具有進化潛能的個體及發現新解.進化潛能大的個體有更大概率被選入下一代，一方面能夠豐富群體多樣性，維持種群的搜索范圍，另一方面與其他優秀個體進行交叉有希望產生更加優良的新個體.

3.1.3 自適應判定策略變換的概率

種群進化過程中若處于停滯或者陷入局部最優解，應當根據種群進化情況更換進化策略，本文引入最優解維持不變的進化代數Gf來衡量種群的進化狀態，并以式(3)計算種群更改策略的概率.

(3)

式(3)中，Gt是當前進化代數，G是總進化代數，β是控制參數，在文本中值為6，Gf表示種群停滯的代數，Gmax為最大停滯代數.

圖1中實體曲線表示進化代數不變時Pch隨停滯代數變換的規律，非線性的概率能夠更合理的控制種群變換進化策略.Pch在進化停滯前期緩慢增長，留出一定的時間使種群依靠現有進化策略擺脫停滯.隨著停滯代數的增加，算法確定種群陷入停滯狀態，相比線性控制的概率，顯著提升了Pch，避免種群浪費時間在現有的進化策略上.最后，為保持種群探索與算法收斂速度的平衡，當停滯代數不變時Pch隨進化代數的進一步增加呈現線性下降的趨勢.

3.1.4 模糊推理進化策略

本文借鑒模糊控制的思想，利用模糊推理根據種群個體的差異性及進化狀況調整種群的進化策略.采用式(4)表示種群進化狀況.

(4)

fmax-favg的大小常被用來衡量種群的進化程度，該方法確實有效，但不足之處在于，適應度函數是依據具體問題而設計的，其數值隨具體問題而變化，并且在算法計算過程中，種群最大適應度與最小適應度也在不斷變化，因此很難確定合適的閾值去判斷種群的進化程度，而采用式(4)衡量種群進化程度更具普遍性.E1的數值越小，種群平均適應度越接近種群最優適應度，說明種群進化程度較高，反之說明種群進化程度較低.式(5)表示種群個體的差異性.

(5)

E2的值越小，說明種群適應度較分散，此時種群差異度較大，多樣性好，反之說明種群多樣性差.

式(4)和式(5)中，f(xi)表示個體xi的適應度，fmax是種群適應度最大值，fmin是種群適應度最小值，favg是種群適應度的平均值，N為種群染色體的數目.

模糊變量E1和E2劃分為3個語言集合{大，中，小}.進化策略劃分為3個語言集合{探索，普通，開發}.表1顯示算法根據E1和E2推理進化策略的模糊規則.如果E1為“大”，E2為“小”，說明種群進化程度低且多樣性好，進化策略應取“開發”.如果E1為“小”，E2為“大”，說明種群進化程度高且多樣性差，進化策略應取“探索”，其他規則可以按上述規律進行類似推理得到.

表1 模糊進化策略規則

交叉算子通過重組開發現有基因來獲取優良個體，若群體內所有個體都沒有某位基因，通過交叉算子無論如何也無法得到這個缺失的基因.變異算子能夠模仿生物界的基因突變產生原先個體內不存在的基因，若種群只產生新基因，不進行進一步的開發探索，種群內優秀個體會不斷的被破壞，遲遲無法收斂.當種群陷入停滯狀態時，若種群的適應度較為集中，此時種群收斂程度較高，染色體之間比較相似，種群多樣性差，需要更換能夠產生新基因擴大種群多樣性的進化策略.若種群適應度較為分散，種群收斂程度低，染色體之間相似度較低，種群內染色體的基因較為豐富，應以探索當前個體的解空間為主，需要更換能夠開發現有基因的進化策略.

3.2 基于距離調整的多種群初始化方法及競爭策略

3.2.1 個體相似度

衡量個體相似度的一種傳統方法是海明距離.設xi，xj為兩個不同個體，它們之間的距離D(xi，xj)可以定義為:

(6)

由于二進制碼中不同基因位對個體的影響不同，即海明距離很小的兩個個體在解空間的實際距離可能很大，海明距離不能充分說明個體之間的差異性.加權海明距離可以根據基因位作用的不同，在海明距離基礎上為不同位置的基因賦予權重，計算式如式(7)所示:

(7)

wk表示基因位k的權值，在本文中wk=2k.設x1=100101，x2=100000，x3=000100，3個個體之間的海明距離均為2，其加權海明距離分別為Dw(x1，x2)=20+22=5;Dw(x1，x3)=20+25=33;Dw(x2，x3)=22+25=36.可以看出具有相同海明距離的兩個個體具有不同的加權海明距離，加權海明距離可以更好的衡量個體之間的差異性.

個體之間的距離由加權海明距離與最大加權海明距離的比值定義:

(8)

式(8)中，l為染色體基因長度.個體相似判定的公式如式(9)所示:

(9)

式(9)中，α表示個體相似的距離閾值，低于該閾值時，算法認為xi與xj具有相似性，否則兩者之間并不相似.群體內每個個體都需要與其他個體進行個體相似判定，以此來計算個體相似度r(xi):

(10)

可以看出r(xi)表示個體xi與其他個體的相似累積值，r(xi)數值越大，表示群體內有更多與之相似的個體.若r(xi)大于相似度閾值η，則稱個體xi為相似個體.

種群進化過程中，采用固定數值的距離閾值α會影響算法進程.FAPGA采用式(11)隨著算法的進程改變距離閾值α.

(11)

式(11)中，α1是最大距離閾值，α2是最小距離閾值，g表示當前進化代數，G表示總進化代數.進化初期α的值較大，調整較多相似個體可以維護種群多樣性;隨著算法的進行，個體之間的距離也在縮小，個體的相似程度也越來越高，若使用固定數值的α，算法后期會判定更多個體為相似個體，調整更多的個體會減緩算法收斂速度，因此隨著進化代數的增加，應不斷縮小α的值，避免影響算法收斂速度.

3.2.2 種群初始化

多樣性是GA能夠搜索到全局最優解的基本條件，有效控制種群的多樣性是提高算法性能的一個重要途徑.種群在建立時應當具有豐富的多樣性，FAPGA首先產生初始種群，群體內每個個體都需要計算個體相似度r(xi)，并隨機產生新染色體代替相似個體，直到種群內不存在相似個體.

3.2.3 競爭策略

FAPGA通過競爭策略在進化過程中每代結束時調整種群的多樣性.首先計算群體內所有個體的個體相似度，將群體內低于種群平均適應度且個體相似度高于相似度閾值η的個體以數值較小的變異概率Pmd進行變異.

小數值的Pmd能減小破壞種群優良性的風險.采用變異的方法來調整相似個體，這是因為競爭策略調整個體時，群體已經進化到一定程度，若采用隨機產生新染色體的方法調整相似個體，新染色體往往適應度值比較低，無法與群體內其他個體相比較，會減緩算法收斂速度.而被調整的個體雖然適應度較其他個體低，但也有比較高的進化程度，對該類個體進行調整不但能夠擺脫相似性，還能探索新的解空間區域，有幾率在當前基礎上獲得更優解.

3.3 改進的自適應尺度變換

(12)

式(12)中，fmin表示種群適應度最小值，fmax表示種群適應度最大值，T為該文獻使用的模擬退火方法的溫度，β為衰減系數.式(12)能夠根據進化時期修正適應度，避免了算法前期因選擇超級個體過多陷入“早熟”收斂.但缺陷在于原適應度使用式(12)變換后，個體之間的新適應度差距變得過小，優良的個體在進化前期被選擇的概率降低的幅度過大，影響了尋優能力.隨著算法的進行，種群的最小適應度與最大適應度的差距變小，算法后期所進行的適應度變換很難如預期般達到改變個體適應度之間的相對差異而促進算法收斂的效果.

FAPGA通過式(13)進行適應度變換，并以變換后的適應度進行比例選擇操作.

f′(xi)=f(xi)+Afavg

(13)

式(13)中，favg表示種群適應度平均值，A是適應度變換的重要參數，計算方式如式(14)所示.

(14)

式(14)中，g表示當前進化代數，G表示總進化代數，a的值為6.

根據前面的分析，式(13)采用種群適應度平均值作為尺度標準可以使適應度變換在算法計算期間更加穩定.文獻[17]所提的適應度變換是基于線性的改變，而式(14)可以根據進化時期非線性地控制適應度變換，能夠更好地根據算法的運行過程進行尺度變換.算法初期，A的值趨近于1，經過適應度變換后，不同個體之間的新適應度差距比原適應度差距小，降低了超級個體的選擇概率，增加了其他個體的選擇概率，有利于保持群體多樣性.隨著算法進行，相比線性控制的選擇靈敏度，A的下降趨勢較為緩慢，能更好的保持進化前期的群體多樣性;進化接近后期時，A更快的接近于0，可以更有效的提升f′(xi)的選擇靈敏度，增加優秀個體被選擇的概率，促進算法加速收斂.

3.4 基于模擬退火構建的Baldwin learning局部搜索策略

3.4.1 遺傳算法與生物進化原理

拉馬克進化學說(Lamarckian learning)主張環境條件的改變能引起生物發生適應環境的變異，即生物體通過后天學習獲得性狀改變，這種改變可以通過基因遺傳給后代，即“用進廢退”和“獲得性遺傳”.將Lamarckian learning應用在遺傳算法中，如果染色體在“環境”影響下個體的表現型(即適應度值)發生改變，會引起個體基因型變化并遺傳到下一代.

鮑德溫進化學說(Baldwin learning)主張生物后天通過環境改變自身的性狀指導了生物進化的方向，即生物在這種指導下通過自然選擇改變自身基因并遺傳下去.將Baldwin learning應用到遺傳算法中，如果染色體在“環境”影響下個體表現型發生改變，不會直接影響到個體的基因型，而是會作為一種“壓力”指導下一代的進化.

3.4.2 局部搜索策略基本原理

本文提出一種新的局部搜索策略來加強算法的局部尋優能力，首先將鄰域結構X定義為:

(15)

式(15)中，pi(max)，pi(min)分別表示決策變量pi定義域的上下界，u表示決策變量維數(即問題維度)，基因長度由l表示，δ為搜索空間的范圍系數，θ是控制鄰域結構大小的系數.

圖2 不同維度鄰域結構

個體進行局部搜索時，首先探索其周圍鄰域結構，并以式(16)代表的Metropolis準則判斷鄰域結構的接收率.若不存在使當前個體優于全局最優解的鄰域結構，每個鄰域結構被賦予小于1的接受率，并以比例選擇的方法隨機選擇一個鄰域結構產生新解進入下一跳.若發現使當前個體優于全局最優解的鄰域結構，賦予該鄰域結構大于1的接收率.若存在多個使當前個體優于全局最優解的鄰域結構，選擇接受率最大的鄰域結構產生新解進入下一跳.每一跳的鄰域結構被確定后產生新解代替當前解時，只有個體的表現型發生變化，而不改變個體的基因型.當個體通過局部搜索發現優于全局最優解的解時，認定該個體具有進化潛能(詳見3.1.2節定義1).進化潛能越大，說明個體通過進化搜索到全局最優的概率也就越大，調整具有進化潛能個體的適應度，使其有更大幾率進入下一代.

基于模擬退火構建的Baldwin learning局部搜索策略流程如下:

1)初始化策略參數:搜索空間系數δ，決策變量數目u，Markov鏈長度m=(2δ)u，初始溫度T，溫度衰減系數K，溫度衰減次數k，新解搜索次數λ，B={n1，n2，…，nm}代表鄰域結構的集合，f(xi)為染色體xi的初始適應度，局部搜索最優值f′(xi)=fmax，fmax是全局最優適應度.

2)對染色體xi采用鄰域結構nj進行局部搜索，按式(16)改進的Metropolis準則計算nj被選中的概率:

(16)

3)若j

4)若存在p(nj)>1，轉5)，否則轉6).

7)若滿足終止條件，轉8).否則轉2).

8)局部搜索結束，輸出f′(xi).

如圖3所示，圓狀實體代表個體，虛線矩陣表示解空間內的鄰域結構，箭頭表示搜索方向，其序號表示當前搜索次數，圖3(a)表示個體通過第1次搜索能夠搜索到的鄰域結構，圖3(b)表示通過第2次搜索理論上能夠搜索到的鄰域結構.上述策略使個體可以探索多個方向鄰域結構，鄰域結構的范圍可以通過式(15)調整，從而建立起搜索范圍與強度均可控的局部搜索策略.局部搜索的目的是充分探索個體所在解空間，只有探索到比全局最優解更加優良的個體才有意義，因此以大于1的接收率采用搜索到更加優良解的鄰域結構.若當前溫度未搜索到比全局最優解更優良的解，采用比例選擇的方法隨機選擇一個鄰域結構產生新解，這種隨機方法能夠充分利用鄰域結構的有效信息進行深度探索，避免了盲目的隨機性.已有研究[10，20]多采用以拉馬克進化理論為基礎的局部搜索策略.其中文獻[10]采用爬山法作為算法的局部搜索策略進行細致搜索，文獻[20]在遺傳算法中加入模擬退火隨機擾動決策變量進行局部搜索.以上方法雖然增強了算法的局部尋優能力，但是無法對新個體是否為局部最優解進行有效區分，即個體通過局部搜索發現更優良的表現型就改變原個體的基因型并進入下一代，使得種群更容易陷入局部收斂.而本文提出的局部搜索策略是以鮑德溫進化理論為基礎，個體通過局部搜索發現了新的最優解的同時，并不改變原個體的基因型，而是一方面記錄該最優解，另一方面以該最優解計算個體的進化潛能(即式(1))并作為一種“選擇壓力”指導個體的進化.通過這樣的方式不但達到搜索新最優解的目的，還減少了種群陷入局部最優的風險.

圖3 個體理論搜索區域

3.5 算法流程

算法流程如圖4所示.

圖4 FAPGA算法流程圖

步驟1.初始化參數.種群數量M，染色體數量N，染色體長度l，鄰域結構范圍系數δ，鄰域結構大小系數θ，決策變量維數u，初始溫度T，溫度衰減系數K，最大停滯代數Gmax，按3.2.2小節初始化種群并隨機賦予進化策略.

步驟2.計算各種群每個個體的適應度，按照式(13)進行適應度變換.

步驟3.按照式(3)計算各種群更換策略的概率.根據E1與E2按表1中的規則進行模糊推理產生進化策略.

步驟4.各種群按進化策略獨立演算進行遺傳操作，共享種群內的優秀個體，公共種群首先對個體進行交叉操作，然后按3.4小節的方法進行局部搜索，擁有進化潛能的個體及時修正適應度.

步驟5.判斷終止準則，若滿足條件，轉步驟7，否則轉步驟6.

步驟6.種群通過競爭策略進行約束，轉步驟2.

步驟7.輸出最優解，算法結束.

4 仿真實驗

4.1 測試函數及對比算法

為驗證FAPGA算法的性能，將本文提出的FAPGA與標準并行遺傳算法(SMGA)和近年新提出的HGA算法[10]進行對比，以驗證算法各方面性能.其中以SMGA主要驗證FAPGA所改進的并行機制的性能.HGA將并行遺傳算法與局部搜索策略混合增強了并行遺傳算法的局部搜索能力，具有較好的局部搜索能力，以該算法主要驗證FAPGA改進的局部搜索策略的有效性;3種算法共同對比來驗證FAPGA的整體性能.

仿真實驗選取3個指標評價算法的性能:1)平均最優解(Average Optimum Solution，AOS)，該指標是算法多次運行的最優適應度的均值，反映求解質量的好壞.2)收斂代數平均值(Average Optimum Iteration，AOI)，該指標用于評價算法的收斂速度及尋優能力.3)收斂次數/收斂率(Convergence times/Convergence rate，CT/CR)，該指標是函數收斂次數及函數收斂次數占實驗總執行次數的百分比.其中，收斂成功是指函數求解結果滿足于指定的收斂精度(收斂精度設置見表3).收斂精度應綜合考量函數維度及不同算法之間的性能來設定，以便更好的區分算法之間的優劣.

將上述3種算法對表2給出的12個標準測試函數進行仿真實驗，表2同時給出了測試函數的取值范圍及理論最優解，其中D是變量的維數(具體數值見表3).f1-f6為多峰函數，用于測試算法勘探和挖掘信息的能力及擺脫局部收斂的能力，f7-f12為高維函數，用于測試算法并行搜索能力及收斂能力.

表2 測試函數

在算法參數設置上，SMGA、HGA、FAPGA均采用相同的進化策略.SMGA與HGA采用二進制編碼，FAPGA采用混合編碼(詳見第2節).種群數目M為4，種群規模N為50，染色體長度為u×20，u為問題維度，算法執行代數均為400代.3種算法均采用比例選擇操作、雙點交叉操作及多點變異操作，進化策略遵循2.1.2小節，具體參數為pc1=0.7，pm1=0.1，pc2=0.5，pm2=0.3，pc3=0.85，pm3=0.05.在FAPGA中，δ=3，θ=105，T=100，K=0.9，Gmax=15，η=N/5.所有仿真實驗均在windows10計算機操作系統，MATLAB2018b仿真平臺下進行，每種算法運行30次.

4.2 仿真實驗結果分析

表3表示3種算法對表2給出的12個標準測試函數各執行30次的優化結果對比.在收斂次數及收斂率上，FAPGA相比SMGA、HGA有更高的CT/CR值，其中FAPGA對f1和f2求解的收斂次數與實驗總執行次數一致，在求解高維函數時，收斂率比其他兩個算法都要高，說明FAPGA有更好的收斂能力和尋優能力.在求解f3時，HGA雖然收斂次數少，但是該算法收斂時的平均代數也比較少，這是由于HGA在拉馬克進化理論的基礎上融入了局部優化方法加強了算法的局部尋優能力，但該算法通過局部搜索到新的最優值同時也改變了原有個體的基因，使得算法陷入局部最優的幾率增加.從平均最優解的對比來看，FAPGA在整體上都要好于SMGA和HGA，尤其是在f4和f7兩個函數最為明顯，說明FAPGA的求解質量和穩定性較好.此外，f4中全局最優值附近存在多個局部最優值，算法在求解函數時極易陷入局部最優值，因此該函數可以較好的測試算法的跳出局部最優值的能力，從表3的優化結果可以看出，FAPGA在求解該函數時收斂次數較高，因此算法有較好的跳出局部最優的能力.

表3 函數測試實驗結果

從收斂代數平均值可以看出FAPGA的AOI值遠小于其他兩個算法，說明該算法有較快的收斂速度.這是由于算法采用模糊自適應的并行機制和適應度變換方法，前者使種群能夠根據自己的情況及時更換進化策略，與競爭策略共同保證了群體的多樣性.而后者通過對適應度進行變換減小了算法前期“超級個體”被選入下一代的概率，降低了種群陷入“早熟”收斂的風險;在算法中后期又加強了優秀個體的選取概率，促進了算法的收斂，兩者共同作用使得FAPGA有較好的全局搜索能力和收斂能力.此外，各種群每代都與公共種群進行遷移，公共種群對遷移過來的個體進行二次開發和局部搜索，加強了算法的局部搜索能力.由于公共種群的存在，使其他種群不必考慮群體內優秀個體被破壞的風險而能夠不斷的勘探解空間，通過這樣的方式，各種群之間互相協作使得算法在很少遺傳代數內就能收斂.

為直觀展現算法的尋優能力，圖5描繪了某次實驗中3種算法在求解函數f1-f12時每代最優值的比較.其中橫軸表示算法的迭代次數，縱軸表示目標函數值.由圖5中的(a)、(c)和(g)可以看出，相比較SMGA與HGA，FAPGA在計算初期有更好的解，這是由于種群初始化時對種群進行調整，改善了群體的多樣性，使個體在解空間內比較分散，避免了隨機初始化方法會導致個體聚集在解空間局部一側的情況.由圖5中的(i)和(j)可以看出，算法前期，HGA的收斂能力要好于SMGA，但是如果該算法前中期算法未能收斂，則該算法后期的收斂曲線一般呈持平狀態，這是因為該算法融入局部優化方法，雖然使算法的尋優能力加強，但也使得該算法更易陷入局部收斂.相反，SMGA雖然前期收斂能力較差，但算法中后期總能擺脫局部收斂，這是用于該算法使用不同的進化策略，使種群能夠不斷探索新的區域.從圖5的整體來看，在較少的迭代次數內，FAPGA所代表的收斂曲線在多數函數求解的圖像內出現了“陡峭”的趨勢，說明算法具有更好的尋優能力和收斂能力.

圖5 算法尋優曲線對比圖

5 結 論

針對遺傳算法存在的優缺點，本文秉承揚長棄短的思想，首先分析GA算法缺陷產生的原因，并討論了已有研究的不足之處，在前人研究的基礎上提出了改進的多種群并行機制、適應度變換方法、種群初始化方法、競爭策略及局部搜索方法.將上述改進方法作用于遺傳算法的不同環節形成一種新的改進遺傳算法.最后，函數優化實驗表明，FAPGA算法能夠較好的平衡算法的收斂速度和群體多樣性，在優化多峰及高維函數方面具有良好的性能.