潘家文，錢(qián) 謙 ，伏云發(fā)，馮 勇

1(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，昆明 650500)

2(昆明理工大學(xué) 云南省計(jì)算機(jī)技術(shù)應(yīng)用重點(diǎn)實(shí)驗(yàn)室，昆明 650500)

1 引 言

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

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

本文首先結(jié)合分析GA算法缺陷產(chǎn)生的原因?qū)σ延邢嚓P(guān)研究的不足之處進(jìn)行討論，然后在前人研究基礎(chǔ)上提出了更加有效的優(yōu)化算法.

2 相關(guān)研究

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

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

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

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

為設(shè)計(jì)一種更加高效的遺傳算法，本文在前人研究基礎(chǔ)上做出改進(jìn)，提出了一類(lèi)模糊自適應(yīng)的并行遺傳算法(FAPGA，F(xiàn)uzzy Adaptive Parallel Genetic Algorithm).具體方法如下:

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

2)多樣性調(diào)整采用基于距離調(diào)整的種群初始化方法及競(jìng)爭(zhēng)策略，初始化方法能夠使種群內(nèi)染色體分布在解空間的不同區(qū)域，保證初始解的多樣性.競(jìng)爭(zhēng)策略作為一種約束條件持續(xù)調(diào)整種群在進(jìn)化過(guò)程中喪失的多樣性，使種群在進(jìn)化過(guò)程中能夠保持豐富的多樣性及設(shè)置合理的搜索范圍.

3)算法進(jìn)行選擇操作時(shí)采用改進(jìn)的適應(yīng)度變換方法，該方法使用更加穩(wěn)定的尺度標(biāo)準(zhǔn)，并能夠非線性的控制適應(yīng)度變換，使變換后的新適應(yīng)度更貼近算法進(jìn)化的要求.

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

3 算法基本思想

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

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

3.1 模糊自適應(yīng)的并行機(jī)制

3.1.1 并行機(jī)制的基本原理

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

主從式模型并不改變遺傳算法的框架結(jié)構(gòu)，而是采用單一種群，所有個(gè)體的進(jìn)化均在主處理器上以遺傳操作進(jìn)行，而將開(kāi)銷(xiāo)較大的適應(yīng)度評(píng)估等計(jì)算交付給多個(gè)從處理器并行處理，該模型簡(jiǎn)單且易實(shí)現(xiàn)，能夠有效減少算法運(yùn)行時(shí)間.

細(xì)粒度模型采用某種鄰域模型將單一種群劃分為多個(gè)子種群，并把每個(gè)種群交付給不同處理器獨(dú)立演化，算法運(yùn)行過(guò)程中不同種群之間按照其拓?fù)浣Y(jié)構(gòu)在邊界上進(jìn)行通信來(lái)交換信息.該模型能夠有效減少算法運(yùn)行時(shí)間并能夠充分發(fā)揮遺傳算法的并行特性.

本文提出的并行機(jī)制采用了粗粒度模型，該機(jī)制通過(guò)多個(gè)種群代替單一種群并行演化來(lái)擴(kuò)大搜索范圍，其中每個(gè)種群自成一個(gè)演化單位按照不同的進(jìn)化策略獨(dú)立進(jìn)化，當(dāng)算法遺傳代次達(dá)到一定周期時(shí)會(huì)進(jìn)行個(gè)體遷移，即各種群之間會(huì)交換一定數(shù)目的優(yōu)秀個(gè)體.該并行機(jī)制對(duì)不同種群配置不同的算法參數(shù)而有效的控制種群的獨(dú)立演化特性，保證了種群進(jìn)化過(guò)程中的多樣性，并通過(guò)遷移來(lái)實(shí)現(xiàn)各種群之間相互協(xié)調(diào)，提升了算法的性能.

混合模型是由上述模型混合形成的結(jié)構(gòu)，如粗粒度-細(xì)粒度、粗粒度-主從式等模型.采用混合模型的并行遺傳算法更具普遍性，但算法也更為復(fù)雜，實(shí)現(xiàn)代價(jià)較高.

3.1.2 并行機(jī)制的進(jìn)化策略

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

定義1.個(gè)體xi通過(guò)局部搜索(詳見(jiàn)3.4節(jié))展現(xiàn)的進(jìn)化潛能由公式(1)定義:

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

(1)

式(1)中，ω表示進(jìn)化潛能的權(quán)重，K表示溫度衰減系數(shù)，λ表示新解搜索次數(shù)，f′(xi)表示染色體xi經(jīng)局部搜索后的最優(yōu)解，fmax表示種群適應(yīng)度最大值.個(gè)體的進(jìn)化潛能與新解搜索次數(shù)及最優(yōu)解的適應(yīng)度相關(guān)，搜索次數(shù)越少，進(jìn)化潛能越大.

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

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

(2)

公共種群的目的在于使種群能夠探索個(gè)體周?chē)慕饪臻g，挖掘具有進(jìn)化潛能的個(gè)體及發(fā)現(xiàn)新解.進(jìn)化潛能大的個(gè)體有更大概率被選入下一代，一方面能夠豐富群體多樣性，維持種群的搜索范圍，另一方面與其他優(yōu)秀個(gè)體進(jìn)行交叉有希望產(chǎn)生更加優(yōu)良的新個(gè)體.

3.1.3 自適應(yīng)判定策略變換的概率

種群進(jìn)化過(guò)程中若處于停滯或者陷入局部最優(yōu)解，應(yīng)當(dāng)根據(jù)種群進(jìn)化情況更換進(jìn)化策略，本文引入最優(yōu)解維持不變的進(jìn)化代數(shù)Gf來(lái)衡量種群的進(jìn)化狀態(tài)，并以式(3)計(jì)算種群更改策略的概率.

(3)

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

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

3.1.4 模糊推理進(jìn)化策略

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

(4)

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

(5)

E2的值越小，說(shuō)明種群適應(yīng)度較分散，此時(shí)種群差異度較大，多樣性好，反之說(shuō)明種群多樣性差.

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

模糊變量E1和E2劃分為3個(gè)語(yǔ)言集合{大，中，小}.進(jìn)化策略劃分為3個(gè)語(yǔ)言集合{探索，普通，開(kāi)發(fā)}.表1顯示算法根據(jù)E1和E2推理進(jìn)化策略的模糊規(guī)則.如果E1為“大”，E2為“小”，說(shuō)明種群進(jìn)化程度低且多樣性好，進(jìn)化策略應(yīng)取“開(kāi)發(fā)”.如果E1為“小”，E2為“大”，說(shuō)明種群進(jìn)化程度高且多樣性差，進(jìn)化策略應(yīng)取“探索”，其他規(guī)則可以按上述規(guī)律進(jìn)行類(lèi)似推理得到.

表1 模糊進(jìn)化策略規(guī)則

交叉算子通過(guò)重組開(kāi)發(fā)現(xiàn)有基因來(lái)獲取優(yōu)良個(gè)體，若群體內(nèi)所有個(gè)體都沒(méi)有某位基因，通過(guò)交叉算子無(wú)論如何也無(wú)法得到這個(gè)缺失的基因.變異算子能夠模仿生物界的基因突變產(chǎn)生原先個(gè)體內(nèi)不存在的基因，若種群只產(chǎn)生新基因，不進(jìn)行進(jìn)一步的開(kāi)發(fā)探索，種群內(nèi)優(yōu)秀個(gè)體會(huì)不斷的被破壞，遲遲無(wú)法收斂.當(dāng)種群陷入停滯狀態(tài)時(shí)，若種群的適應(yīng)度較為集中，此時(shí)種群收斂程度較高，染色體之間比較相似，種群多樣性差，需要更換能夠產(chǎn)生新基因擴(kuò)大種群多樣性的進(jìn)化策略.若種群適應(yīng)度較為分散，種群收斂程度低，染色體之間相似度較低，種群內(nèi)染色體的基因較為豐富，應(yīng)以探索當(dāng)前個(gè)體的解空間為主，需要更換能夠開(kāi)發(fā)現(xiàn)有基因的進(jìn)化策略.

3.2 基于距離調(diào)整的多種群初始化方法及競(jìng)爭(zhēng)策略

3.2.1 個(gè)體相似度

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

(6)

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

(7)

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

個(gè)體之間的距離由加權(quán)海明距離與最大加權(quán)海明距離的比值定義:

(8)

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

(9)

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

(10)

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

種群進(jìn)化過(guò)程中，采用固定數(shù)值的距離閾值α?xí)绊懰惴ㄟM(jìn)程.FAPGA采用式(11)隨著算法的進(jìn)程改變距離閾值α.

(11)

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

3.2.2 種群初始化

多樣性是GA能夠搜索到全局最優(yōu)解的基本條件，有效控制種群的多樣性是提高算法性能的一個(gè)重要途徑.種群在建立時(shí)應(yīng)當(dāng)具有豐富的多樣性，F(xiàn)APGA首先產(chǎn)生初始種群，群體內(nèi)每個(gè)個(gè)體都需要計(jì)算個(gè)體相似度r(xi)，并隨機(jī)產(chǎn)生新染色體代替相似個(gè)體，直到種群內(nèi)不存在相似個(gè)體.

3.2.3 競(jìng)爭(zhēng)策略

FAPGA通過(guò)競(jìng)爭(zhēng)策略在進(jìn)化過(guò)程中每代結(jié)束時(shí)調(diào)整種群的多樣性.首先計(jì)算群體內(nèi)所有個(gè)體的個(gè)體相似度，將群體內(nèi)低于種群平均適應(yīng)度且個(gè)體相似度高于相似度閾值η的個(gè)體以數(shù)值較小的變異概率Pmd進(jìn)行變異.

小數(shù)值的Pmd能減小破壞種群優(yōu)良性的風(fēng)險(xiǎn).采用變異的方法來(lái)調(diào)整相似個(gè)體，這是因?yàn)楦?jìng)爭(zhēng)策略調(diào)整個(gè)體時(shí)，群體已經(jīng)進(jìn)化到一定程度，若采用隨機(jī)產(chǎn)生新染色體的方法調(diào)整相似個(gè)體，新染色體往往適應(yīng)度值比較低，無(wú)法與群體內(nèi)其他個(gè)體相比較，會(huì)減緩算法收斂速度.而被調(diào)整的個(gè)體雖然適應(yīng)度較其他個(gè)體低，但也有比較高的進(jìn)化程度，對(duì)該類(lèi)個(gè)體進(jìn)行調(diào)整不但能夠擺脫相似性，還能探索新的解空間區(qū)域，有幾率在當(dāng)前基礎(chǔ)上獲得更優(yōu)解.

3.3 改進(jìn)的自適應(yīng)尺度變換

(12)

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

FAPGA通過(guò)式(13)進(jìn)行適應(yīng)度變換，并以變換后的適應(yīng)度進(jìn)行比例選擇操作.

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

(13)

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

(14)

式(14)中，g表示當(dāng)前進(jìn)化代數(shù)，G表示總進(jìn)化代數(shù)，a的值為6.

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

3.4 基于模擬退火構(gòu)建的Baldwin learning局部搜索策略

3.4.1 遺傳算法與生物進(jìn)化原理

拉馬克進(jìn)化學(xué)說(shuō)(Lamarckian learning)主張環(huán)境條件的改變能引起生物發(fā)生適應(yīng)環(huán)境的變異，即生物體通過(guò)后天學(xué)習(xí)獲得性狀改變，這種改變可以通過(guò)基因遺傳給后代，即“用進(jìn)廢退”和“獲得性遺傳”.將Lamarckian learning應(yīng)用在遺傳算法中，如果染色體在“環(huán)境”影響下個(gè)體的表現(xiàn)型(即適應(yīng)度值)發(fā)生改變，會(huì)引起個(gè)體基因型變化并遺傳到下一代.

鮑德溫進(jìn)化學(xué)說(shuō)(Baldwin learning)主張生物后天通過(guò)環(huán)境改變自身的性狀指導(dǎo)了生物進(jìn)化的方向，即生物在這種指導(dǎo)下通過(guò)自然選擇改變自身基因并遺傳下去.將Baldwin learning應(yīng)用到遺傳算法中，如果染色體在“環(huán)境”影響下個(gè)體表現(xiàn)型發(fā)生改變，不會(huì)直接影響到個(gè)體的基因型，而是會(huì)作為一種“壓力”指導(dǎo)下一代的進(jìn)化.

3.4.2 局部搜索策略基本原理

本文提出一種新的局部搜索策略來(lái)加強(qiáng)算法的局部尋優(yōu)能力，首先將鄰域結(jié)構(gòu)X定義為:

(15)

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

圖2 不同維度鄰域結(jié)構(gòu)

個(gè)體進(jìn)行局部搜索時(shí)，首先探索其周?chē)徲蚪Y(jié)構(gòu)，并以式(16)代表的Metropolis準(zhǔn)則判斷鄰域結(jié)構(gòu)的接收率.若不存在使當(dāng)前個(gè)體優(yōu)于全局最優(yōu)解的鄰域結(jié)構(gòu)，每個(gè)鄰域結(jié)構(gòu)被賦予小于1的接受率，并以比例選擇的方法隨機(jī)選擇一個(gè)鄰域結(jié)構(gòu)產(chǎn)生新解進(jìn)入下一跳.若發(fā)現(xiàn)使當(dāng)前個(gè)體優(yōu)于全局最優(yōu)解的鄰域結(jié)構(gòu)，賦予該鄰域結(jié)構(gòu)大于1的接收率.若存在多個(gè)使當(dāng)前個(gè)體優(yōu)于全局最優(yōu)解的鄰域結(jié)構(gòu)，選擇接受率最大的鄰域結(jié)構(gòu)產(chǎn)生新解進(jìn)入下一跳.每一跳的鄰域結(jié)構(gòu)被確定后產(chǎn)生新解代替當(dāng)前解時(shí)，只有個(gè)體的表現(xiàn)型發(fā)生變化，而不改變個(gè)體的基因型.當(dāng)個(gè)體通過(guò)局部搜索發(fā)現(xiàn)優(yōu)于全局最優(yōu)解的解時(shí)，認(rèn)定該個(gè)體具有進(jìn)化潛能(詳見(jiàn)3.1.2節(jié)定義1).進(jìn)化潛能越大，說(shuō)明個(gè)體通過(guò)進(jìn)化搜索到全局最優(yōu)的概率也就越大，調(diào)整具有進(jìn)化潛能個(gè)體的適應(yīng)度，使其有更大幾率進(jìn)入下一代.

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

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

2)對(duì)染色體xi采用鄰域結(jié)構(gòu)nj進(jìn)行局部搜索，按式(16)改進(jìn)的Metropolis準(zhǔn)則計(jì)算nj被選中的概率:

(16)

3)若j

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

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

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

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

圖3 個(gè)體理論搜索區(qū)域

3.5 算法流程

算法流程如圖4所示.

圖4 FAPGA算法流程圖

步驟1.初始化參數(shù).種群數(shù)量M，染色體數(shù)量N，染色體長(zhǎng)度l，鄰域結(jié)構(gòu)范圍系數(shù)δ，鄰域結(jié)構(gòu)大小系數(shù)θ，決策變量維數(shù)u，初始溫度T，溫度衰減系數(shù)K，最大停滯代數(shù)Gmax，按3.2.2小節(jié)初始化種群并隨機(jī)賦予進(jìn)化策略.

步驟2.計(jì)算各種群每個(gè)個(gè)體的適應(yīng)度，按照式(13)進(jìn)行適應(yīng)度變換.

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

步驟4.各種群按進(jìn)化策略獨(dú)立演算進(jìn)行遺傳操作，共享種群內(nèi)的優(yōu)秀個(gè)體，公共種群首先對(duì)個(gè)體進(jìn)行交叉操作，然后按3.4小節(jié)的方法進(jìn)行局部搜索，擁有進(jìn)化潛能的個(gè)體及時(shí)修正適應(yīng)度.

步驟5.判斷終止準(zhǔn)則，若滿足條件，轉(zhuǎn)步驟7，否則轉(zhuǎn)步驟6.

步驟6.種群通過(guò)競(jìng)爭(zhēng)策略進(jìn)行約束，轉(zhuǎn)步驟2.

步驟7.輸出最優(yōu)解，算法結(jié)束.

4 仿真實(shí)驗(yàn)

4.1 測(cè)試函數(shù)及對(duì)比算法

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

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

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

表2 測(cè)試函數(shù)

在算法參數(shù)設(shè)置上，SMGA、HGA、FAPGA均采用相同的進(jìn)化策略.SMGA與HGA采用二進(jìn)制編碼，F(xiàn)APGA采用混合編碼(詳見(jiàn)第2節(jié)).種群數(shù)目M為4，種群規(guī)模N為50，染色體長(zhǎng)度為u×20，u為問(wèn)題維度，算法執(zhí)行代數(shù)均為400代.3種算法均采用比例選擇操作、雙點(diǎn)交叉操作及多點(diǎn)變異操作，進(jìn)化策略遵循2.1.2小節(jié)，具體參數(shù)為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.所有仿真實(shí)驗(yàn)均在windows10計(jì)算機(jī)操作系統(tǒng)，MATLAB2018b仿真平臺(tái)下進(jìn)行，每種算法運(yùn)行30次.

4.2 仿真實(shí)驗(yàn)結(jié)果分析

表3表示3種算法對(duì)表2給出的12個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)各執(zhí)行30次的優(yōu)化結(jié)果對(duì)比.在收斂次數(shù)及收斂率上，F(xiàn)APGA相比SMGA、HGA有更高的CT/CR值，其中FAPGA對(duì)f1和f2求解的收斂次數(shù)與實(shí)驗(yàn)總執(zhí)行次數(shù)一致，在求解高維函數(shù)時(shí)，收斂率比其他兩個(gè)算法都要高，說(shuō)明FAPGA有更好的收斂能力和尋優(yōu)能力.在求解f3時(shí)，HGA雖然收斂次數(shù)少，但是該算法收斂時(shí)的平均代數(shù)也比較少，這是由于HGA在拉馬克進(jìn)化理論的基礎(chǔ)上融入了局部?jī)?yōu)化方法加強(qiáng)了算法的局部尋優(yōu)能力，但該算法通過(guò)局部搜索到新的最優(yōu)值同時(shí)也改變了原有個(gè)體的基因，使得算法陷入局部最優(yōu)的幾率增加.從平均最優(yōu)解的對(duì)比來(lái)看，F(xiàn)APGA在整體上都要好于SMGA和HGA，尤其是在f4和f7兩個(gè)函數(shù)最為明顯，說(shuō)明FAPGA的求解質(zhì)量和穩(wěn)定性較好.此外，f4中全局最優(yōu)值附近存在多個(gè)局部最優(yōu)值，算法在求解函數(shù)時(shí)極易陷入局部最優(yōu)值，因此該函數(shù)可以較好的測(cè)試算法的跳出局部最優(yōu)值的能力，從表3的優(yōu)化結(jié)果可以看出，F(xiàn)APGA在求解該函數(shù)時(shí)收斂次數(shù)較高，因此算法有較好的跳出局部最優(yōu)的能力.

表3 函數(shù)測(cè)試實(shí)驗(yàn)結(jié)果

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

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

圖5 算法尋優(yōu)曲線對(duì)比圖

5 結(jié) 論

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