基于動(dòng)態(tài)區(qū)域劃分的多種群進(jìn)化算法

陳 昊，許春蕾，黎 明，張聰炫

1.南昌航空大學(xué)無損檢測(cè)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，南昌330063

2.南昌航空大學(xué)信息工程學(xué)院，南昌330063

進(jìn)化算法現(xiàn)已應(yīng)用于實(shí)際的復(fù)雜優(yōu)化問題，而多種群策略表示子種群對(duì)解空間中不同區(qū)域采用不同的進(jìn)化策略，并通過遷移等操作實(shí)現(xiàn)子種群間的信息交互，此類算法被稱為多種群進(jìn)化算法.近年來，多種群進(jìn)化算法的研究主要包括以下三方面：

1）在進(jìn)化的過程中，以個(gè)體之間的相關(guān)性、相似程度以及個(gè)體分布等為依據(jù)，采用聚類策略劃分種群或搜索空間.文獻(xiàn)[1]首先根據(jù)聚類算法將搜索區(qū)域劃分成不同的等級(jí)，然后針對(duì)高等級(jí)區(qū)域加強(qiáng)搜索以逐步縮小搜索空間，這樣不但提高了收斂速率而且降低了復(fù)雜度.文獻(xiàn)[2]提出一種新的多種群遺傳算法，即以一個(gè)新的相似性測(cè)量函數(shù)決定兩個(gè)點(diǎn)是否屬于同一個(gè)集群，從而將種群分為N個(gè)小集群.文獻(xiàn)[3]提出一種基于多個(gè)子種群的參數(shù)自適應(yīng)差分進(jìn)化算法，通過一個(gè)循環(huán)實(shí)現(xiàn)子種群間的信息共享與交換，并借助上一級(jí)子種群的當(dāng)前最優(yōu)個(gè)體引導(dǎo)本種群的進(jìn)化.

2）基于解空間拓?fù)浣Y(jié)構(gòu)的多種群進(jìn)化算法先將整個(gè)解空間劃分為多個(gè)子區(qū)域，再以區(qū)域內(nèi)個(gè)體的適應(yīng)度評(píng)價(jià)區(qū)域?qū)傩?，且各區(qū)域中采用不同的進(jìn)化策略.為增強(qiáng)粒子的全局搜索能力，文獻(xiàn)[4]采用一種基于隨機(jī)圖論的鄰居拓?fù)浣Y(jié)構(gòu)，通過構(gòu)造均勻程度不同的拓?fù)浣Y(jié)構(gòu)來影響粒子群優(yōu)化算法的性能.文獻(xiàn)[5]研究了粒子間的信息交互與共享過程，分析了典型的靜態(tài)鄰居拓?fù)浣Y(jié)構(gòu)的圖形特征對(duì)粒子群算法性能的影響，并通過實(shí)驗(yàn)證明了算法的穩(wěn)定性較好，不過尋優(yōu)速度較慢.文獻(xiàn)[6]在進(jìn)化過程中確定一種對(duì)偶知識(shí)，通過引入不同類型的知識(shí)來影響進(jìn)化過程.

3）異構(gòu)多種群策略根據(jù)常規(guī)方法在一個(gè)區(qū)間上同時(shí)生成多個(gè)子種群，而各個(gè)子種群可以采用不同的進(jìn)化策略，但要確保此方法生成的子種群所在區(qū)間完全重合.文獻(xiàn)[7]研究一種將多種群粒子群算法和遺傳算法進(jìn)行混合的進(jìn)化策略，也就是將粒子群的群體分解為多個(gè)子種群，而各子種群可以利用不同的策略并行進(jìn)化使粒子具有不同特性，以此提高種群的多樣性.文獻(xiàn)[8]將多種群策略引入文化算法使每個(gè)子種群在進(jìn)化過程中單獨(dú)運(yùn)算，然后改變算法控制參數(shù)使各子種群并行尋優(yōu).文獻(xiàn)[9]針對(duì)動(dòng)態(tài)優(yōu)化問題提出一種自適應(yīng)多種群人工蜂群算法以便各子種群獨(dú)立尋優(yōu)，通過設(shè)計(jì)一種跨種群算子實(shí)現(xiàn)子種群間的信息交互.

除上述3 種子種群劃分方法以外還有其他群劃分方法，如各進(jìn)化策略間的相互協(xié)作關(guān)系、遷移策略等.文獻(xiàn)[10]依據(jù)每種差分進(jìn)化模型的特點(diǎn)為子種群動(dòng)態(tài)分配進(jìn)化策略，從而使多種策略之間協(xié)同進(jìn)化，并通過實(shí)驗(yàn)證明了該算法的性能提升幅度較大.文獻(xiàn)[11]以并行差分進(jìn)化策略優(yōu)化種群聚類，增強(qiáng)了子種群間的通信遷移能力.文獻(xiàn)[12]針對(duì)協(xié)同進(jìn)化中各策略的貢獻(xiàn)度差異，采用多種群合作的方法縮小算法的搜索空間，有利于求得全局最優(yōu)解.

上述研究表明，在進(jìn)化算法中采用多種群策略對(duì)提高算法的求解性能具有重要意義，這些探索為進(jìn)化算法應(yīng)用于求解復(fù)雜優(yōu)化問題提供了新的思路和途徑.然而，目前關(guān)于進(jìn)化算法的多種群策略研究大致有以下缺陷：1）利用拓?fù)浣Y(jié)構(gòu)進(jìn)行劃分時(shí)既不能區(qū)分每個(gè)區(qū)間的重要程度，也無法體現(xiàn)子種群之間的差異性；2）基于異構(gòu)的區(qū)域劃分方法通常只能針對(duì)一個(gè)特定的空間進(jìn)行操作；3）對(duì)子種群如何劃分沒有一個(gè)確定的標(biāo)準(zhǔn)，也無理論依據(jù)，不能保證劃分后的區(qū)域比原有區(qū)域找到最優(yōu)解的概率更大.鑒于此，本文提出一種基于動(dòng)態(tài)區(qū)域劃分的多種群進(jìn)化算法，主要是將云模型與原問題結(jié)合以重新估計(jì)原問題，并對(duì)估計(jì)后的新問題進(jìn)行解空間區(qū)域劃分，不僅提供了一套完整的子種群劃分標(biāo)準(zhǔn)，而且大大縮小了種群的搜索區(qū)域，降低了問題難度.除此之外，本文還推導(dǎo)了相關(guān)的定義和定理.

1 關(guān)鍵概念

1.1 云模型理論

為了處理定性概念中廣泛存在的隨機(jī)性和模糊性問題，文獻(xiàn)[13]提出了包括基本云模型、云發(fā)生器、虛擬云、云變換、云可視化等內(nèi)容在內(nèi)的云模型.這種云模型是用語言值表示的某個(gè)定性概念與其定量表示之間的不確定轉(zhuǎn)換模型，已解決了各種優(yōu)化問題[14-16].

1.1.1 云的定義

設(shè)U是一個(gè)用精確數(shù)值表示的定量論域，C是U空間上的定性概念，若定量值x(x ∈U)是定性概念C的一次隨機(jī)實(shí)現(xiàn)，x對(duì)C的確定度u(x)∈[0,1]是具有穩(wěn)定傾向的隨機(jī)數(shù)：u(x):U →[0,1],?x ∈U,x →u(x)，則x在論域U上的分布稱為云(Cloud)，記為云C(x)，每一個(gè)x稱為一個(gè)云滴.當(dāng)C(x)服從正態(tài)分布時(shí)，該模型稱為正態(tài)云模型.如果概念對(duì)應(yīng)的論域是n維空間，那么可以拓廣至n維云.

1.1.2 云的數(shù)字特征

云模型所表達(dá)概念的整體特性可用云的數(shù)字特征來表征，分別為期望Ex、熵En、超熵He，記作C(Ex,En,He).期望是在數(shù)域空間中最能代表定性概念的點(diǎn)，反映云滴群的重心；熵用來綜合度量定性概念的模糊度和概率，反映了這個(gè)概念的不確定性；超熵是熵的不確定度量，反映了在數(shù)域空間代表該語言值所有點(diǎn)不確定度的凝聚性.多維云模型的整體特征可由多組數(shù)字特征表示.

1.1.3 云模型的產(chǎn)生方法

生成云滴的算法或硬件稱為云發(fā)生器，本文用的云發(fā)生器為X條件云發(fā)生器.給定云的3 個(gè)數(shù)字特征{Ex,En,He}、特定的x0及云滴數(shù)k，產(chǎn)生云滴drop(x0,ua)的偽代碼如下：

1.2 進(jìn)化算法困難性指標(biāo)

用適應(yīng)值距離關(guān)聯(lián)測(cè)試法[17](fitness distance correlation,FDC)作為衡量進(jìn)化算法的困難性指標(biāo)，該方法表明：如果R中的可行解與全局最優(yōu)解的距離和它與全局最優(yōu)解的適應(yīng)值的差成正比，則問題比較容易；反之則問題比較困難.FDC 方法以測(cè)試樣本集P上的適應(yīng)值與距離之間的相關(guān)系數(shù)描述進(jìn)化算法的困難性.適應(yīng)值距離相關(guān)系數(shù)FDCP的具體公式如下：

式中，d(x)表示x到最優(yōu)解的距離；分別表示樣本集P的適應(yīng)值均值和所有樣本到最優(yōu)解的距離均值.FDCp ∈[?1,1]，當(dāng)最大(小)值問題趨于?1(1)時(shí)，難度變小.

2 基于云模型的問題估計(jì)

假設(shè)當(dāng)前最優(yōu)解為全局最優(yōu)解，則可以找到一個(gè)與原問題相對(duì)應(yīng)的云模型，且只存在一個(gè)云模型與原問題差異最小.若此假設(shè)成立，則估計(jì)的云模型與原問題的最優(yōu)解相同，且原問題可以轉(zhuǎn)化為一個(gè)難度降低的新問題.云模型可在任意時(shí)刻對(duì)原問題進(jìn)行估計(jì)，進(jìn)而根據(jù)估計(jì)結(jié)果劃分解空間的區(qū)域.按照原問題與云模型估計(jì)的結(jié)果，可以將原問題的解空間劃分為期望區(qū)域與違背區(qū)域.

定義1若原問題為fg(x)，估計(jì)的云模型為fc(x)，則在云模型上的數(shù)值大于原問題數(shù)值的種群空間區(qū)域?yàn)槠谕麉^(qū)域(expectation area,EA).

定義2將不滿足期望區(qū)域定義的種群空間作為違背區(qū)域(breach area,BA).

原問題與云估計(jì)的位置對(duì)比如圖1所示，此處以單維問題為例，其中連續(xù)復(fù)雜適應(yīng)值曲面代表原問題，云估計(jì)代表在過程中的某一時(shí)刻建立的云模型.針對(duì)此模型，可引出定理1.

定理1若云模型的中心點(diǎn)xT不是全局最優(yōu)解xO，則xO一定在違背區(qū)域內(nèi).

證明假設(shè)在當(dāng)前進(jìn)化過程中問題的全局最優(yōu)解為xO,云模型的中心點(diǎn)為xT，則中心點(diǎn)在云模型上的適應(yīng)值為fc(xT)，對(duì)于有fc(x)< fc(xT).因?yàn)樗詅g(xT)< fg(xO)，又fg(xT) =fc(xT)，于是有fc(xO)< fc(xT) =fg(xT)< fg(xO)，可以得出fc(xO)< fg(xO)，進(jìn)一步可以得出如下結(jié)論：若云模型中心點(diǎn)不是全局最優(yōu)解，則全局最優(yōu)解一定在違背區(qū)域內(nèi).此時(shí)，對(duì)于一個(gè)優(yōu)化問題，若能根據(jù)估計(jì)的云模型尋找到其違背區(qū)域，則可縮小種群的搜索范圍，有助于降低問題的難度.

圖1 原問題與云估計(jì)位置的對(duì)比Figure1 Comparison of original problem and cloud estimation position

3 基于動(dòng)態(tài)區(qū)域劃分的多種群進(jìn)化算法研究

3.1 問題適應(yīng)值曲面估計(jì)算子

問題適應(yīng)值曲面估計(jì)算子的作用是產(chǎn)生與原問題差異最小的云模型重新估計(jì)原問題，其本質(zhì)是尋找云模型的最優(yōu)期望值與熵值，從而可將尋找過程歸納為一個(gè)優(yōu)化問題，用數(shù)學(xué)模型描述為

式中，α為縮放因子，R={x1,x2,··· ,xm}為當(dāng)前評(píng)價(jià)集的集合，m為評(píng)價(jià)集中點(diǎn)的數(shù)目.評(píng)價(jià)集的構(gòu)造原理詳見3.2 節(jié).

本文以當(dāng)前最優(yōu)個(gè)體Pbest作為云模型的期望值Ex，以原問題與云模型在評(píng)價(jià)集上的差值為評(píng)價(jià)標(biāo)準(zhǔn)產(chǎn)生云模型的熵值En.產(chǎn)生熵值的偽代碼如下：

3.2 評(píng)價(jià)算子

評(píng)價(jià)算子可以產(chǎn)生評(píng)價(jià)個(gè)體優(yōu)劣的適應(yīng)值函數(shù)，并構(gòu)造規(guī)模固定的評(píng)價(jià)集對(duì)問題進(jìn)行評(píng)價(jià).評(píng)價(jià)個(gè)體優(yōu)劣的適應(yīng)值函數(shù)f(x)按如下方法選取：

構(gòu)造評(píng)價(jià)集的偽代碼如下：

其中，違背區(qū)域劃分準(zhǔn)則以及代表個(gè)體的選擇詳見3.3 節(jié).

3.3 區(qū)域劃分算子

區(qū)域劃分算子的作用主要是將原問題的解空間劃分為期望區(qū)域與違背區(qū)域，并按聚類方法將違背區(qū)域劃分為多個(gè)子區(qū)域.在子區(qū)域中，運(yùn)用差分進(jìn)化算法(differential evolution algorithm,DE)和遺傳算法(genetic algorithm,GA)進(jìn)行精細(xì)搜索，即根據(jù)異構(gòu)策略在不同的區(qū)域采用不同的進(jìn)化方式進(jìn)行搜索，則子區(qū)域間的信息交互及相互轉(zhuǎn)化可保證整個(gè)種群之間的信息共享.異構(gòu)策略圖如圖2所示.

圖2 異構(gòu)策略圖Figure2 Heterogeneous strategy graph

假設(shè)違背區(qū)域中有N個(gè)違背點(diǎn)，于是根據(jù)K-均值聚類算法將違背點(diǎn)聚類，聚類完成后參照評(píng)價(jià)個(gè)體優(yōu)劣的適應(yīng)值函數(shù)在每一類中選出代表個(gè)體，并為每個(gè)代表個(gè)體定義新的搜索區(qū)域進(jìn)行局部搜索.新區(qū)域每一維的搜索范圍定義如下：

式中，表示第t代第i個(gè)代表個(gè)體的第j維變量，l為可調(diào)因子.

區(qū)域劃分算子偽代碼如下：

其中，N為違背點(diǎn)數(shù)目，n為劃分區(qū)域數(shù)目，Np為種群個(gè)體數(shù)目.

對(duì)于一個(gè)具體的優(yōu)化問題，首先建立與其相對(duì)應(yīng)的云模型進(jìn)行重新估計(jì)，并根據(jù)估計(jì)后的新問題將解空間劃分為期望區(qū)域與違背區(qū)域，然后在劃分后的各個(gè)子區(qū)域使用不同的搜索策略，以期減小搜索區(qū)域，降低問題難度，從而使問題求解變得更加簡單.因此，本文提出一種基于動(dòng)態(tài)區(qū)域劃分的多種群進(jìn)化算法(multi-population evolutionary algorithm based on dynamic area division,DD-MEA)，具體實(shí)現(xiàn)步驟如下：

步驟1種群初始化.設(shè)進(jìn)化代數(shù)為t，初始化種群為Pt.

步驟2以評(píng)價(jià)算子構(gòu)造初始評(píng)價(jià)集Rt.

步驟3由問題適應(yīng)值曲面估計(jì)算子產(chǎn)生云模型Ct=[Ex(t),En(t),He(t)].

步驟4依據(jù)區(qū)域劃分算子將解空間劃分為期望區(qū)域EAt和違背區(qū)域BAt，得到代表個(gè)體{b1,b2,··· ,bn}.

步驟5適應(yīng)值計(jì)算.

步驟5.1y1=fg(Pt)

步驟5.2y2=fc(Pt)

步驟5.3以評(píng)價(jià)算子評(píng)估個(gè)體的適應(yīng)值fitness(Pt)=max(y1,y2)

步驟6將種群中適應(yīng)值較低的個(gè)體替換為{b1,b2,··· ,bn}.

步驟7執(zhí)行遺傳操作（選擇、交叉、變異）后更新種群.

步驟8對(duì)當(dāng)前最優(yōu)個(gè)體進(jìn)行局部搜索.

步驟9以評(píng)價(jià)算子更新評(píng)價(jià)集.

步驟10終止條件判斷.若t>tmax，則算法結(jié)束并輸出結(jié)果，否則跳轉(zhuǎn)到步驟3.其中，當(dāng)前最優(yōu)個(gè)體的搜索原理同代表個(gè)體.

4 實(shí)驗(yàn)數(shù)據(jù)及分析

本文以CEC2013 測(cè)試函數(shù)庫中的6 個(gè)函數(shù)為測(cè)試函數(shù)來分析4 種算法的性能.這4 種算法分別為文化算法(cultural algorithm,CA)、差分進(jìn)化算法(DE)、元胞遺傳算法(cellular genetic algorithm,CGA)、本文所提出的基于動(dòng)態(tài)區(qū)域劃分的多種群進(jìn)化算法(DD-MEA)，其種群規(guī)模都為200.在這6 個(gè)測(cè)試函數(shù)中，每種算法在不同維度上獨(dú)立運(yùn)行30 次，進(jìn)化代數(shù)均設(shè)置為500 代.在分析本文算法與其他算法尋優(yōu)性能的基礎(chǔ)上，增添7 個(gè)簡單的測(cè)試函數(shù)，運(yùn)用DD-MEA 算法測(cè)試算法的困難性指標(biāo).

4.1 算法性能對(duì)比分析實(shí)驗(yàn)

CEC2013 測(cè)試函數(shù)如表1所示，其中F1、F2、F3為連續(xù)單峰函數(shù)，F(xiàn)4、F5、F6為復(fù)雜多峰函數(shù)，每個(gè)測(cè)試函數(shù)的特點(diǎn)各不相同，在下面的測(cè)試結(jié)果分析中會(huì)具體說明.

表1 CEC2013 測(cè)試函數(shù)Table1 CEC2013 test functions

函數(shù)測(cè)試結(jié)果如表2所示，其中f表示算法的平均尋優(yōu)值，即30 次尋優(yōu)結(jié)果的目標(biāo)函數(shù)值的平均值；s為平均收斂代數(shù)，即算法收斂到全局最優(yōu)解所用進(jìn)化代數(shù)的平均值；t為平均收斂時(shí)間，即滿足收斂條件時(shí)所用時(shí)間的平均時(shí)間，單位為s；“+”表示在同等條件下本文算法所得結(jié)果與其他3 種算法所得結(jié)果具有顯著性差異，顯著性分析采用T檢驗(yàn)方法，顯著性水平設(shè)置為0.05；數(shù)據(jù)加粗表示本文算法在同等條件下得到的指標(biāo)數(shù)據(jù)最優(yōu).

表2 函數(shù)測(cè)試結(jié)果Table2 Testing results of function

分析表2數(shù)據(jù)可以發(fā)現(xiàn)：根據(jù)2 維F1和F6函數(shù)優(yōu)化結(jié)果可知4 種算法都能完全找到最優(yōu)解.在種群規(guī)模都相同的情況下，DD-MEA 的平均收斂代數(shù)和平均收斂時(shí)間最小，且平均收斂代數(shù)顯著性差異明顯，說明DD-MEA 相比于其他3 種算法具有更快的尋優(yōu)速率.F2函數(shù)為一個(gè)單峰、不可分離函數(shù)，當(dāng)F2函數(shù)的維數(shù)變?yōu)?0 時(shí)，CA 和DE 幾乎找不到全局最優(yōu)解；CGA 尋找的結(jié)果與最優(yōu)解接近，但進(jìn)化時(shí)間太長；DD-MEA 不僅可以找到全局最優(yōu)解，而且其進(jìn)化代數(shù)和尋優(yōu)時(shí)間也遠(yuǎn)遠(yuǎn)小于CGA，顯然優(yōu)于其他3 種算法.F3函數(shù)屬于多模態(tài)函數(shù)且具有一個(gè)非常窄的峽谷，F(xiàn)4函數(shù)屬于非均勻、多峰函數(shù)，這就使得算法的函數(shù)值很容易陷入局部最優(yōu)解.對(duì)于F3和F4函數(shù)，CA、DE 和DD-MEA 在低維時(shí)通常能求到最優(yōu)解，但各項(xiàng)指標(biāo)與其他3 種算法存在顯著性差異，而大于等于5 維時(shí)CA、DE 和CGA 并不能求到最優(yōu)解，其值已經(jīng)出現(xiàn)大幅度跳變的情況，DD-MEA 測(cè)試的結(jié)果是在最優(yōu)解附近跳動(dòng)，能求到與最優(yōu)解附近相近的值.F5函數(shù)具有非對(duì)稱及旋轉(zhuǎn)的特性且局部最優(yōu)解的數(shù)量很多，CA 在由低維至高維的測(cè)試過程中，算法的穩(wěn)定性越來越差；DE 在低維時(shí)能找到最優(yōu)解；DD-MEA 不僅在低維時(shí)能完全找到最優(yōu)解，花費(fèi)時(shí)間較少，而且高維時(shí)求到的解也幾乎接近全局最優(yōu)解.F6為可分離且不對(duì)稱函數(shù)，當(dāng)維數(shù)較低維時(shí)，4 種算法均能求到最優(yōu)解.若以時(shí)間來衡量，則CGA 和DD-MEA 優(yōu)于CA 和DE 且具有明顯差異，因?yàn)镈D-MEA 收斂代數(shù)遠(yuǎn)小于CGA，所以DD-MEA 求解低維F6問題時(shí)比其他3 種算法效果好，求解高維時(shí)更接近最優(yōu)解，且在收斂代數(shù)上表現(xiàn)出較明顯的優(yōu)勢(shì).

通過以上實(shí)驗(yàn)測(cè)試結(jié)果可以看出，不管是對(duì)于低維還是高維優(yōu)化問題，DD-MEA 在收斂效率、收斂精度以及收斂代數(shù)等方面都表現(xiàn)出較好的測(cè)試性能，在通用性和穩(wěn)定性方面也取得了令人滿意的測(cè)試效果.

4.2 困難性測(cè)試分析實(shí)驗(yàn)

困難性測(cè)試函數(shù)如表3所示，測(cè)試函數(shù)的維數(shù)均為2 維，采用DD-MEA 在一定搜索范圍內(nèi)分析函數(shù)在進(jìn)化過程中各階段的難度變化.

表3 困難性測(cè)試函數(shù)Table3 Difficulty test functions

函數(shù)困難性測(cè)試實(shí)驗(yàn)結(jié)果如表4所示，DD-MEA 運(yùn)用適應(yīng)值距離關(guān)聯(lián)測(cè)試法(FDC)分別測(cè)試了T1～T7這7 個(gè)函數(shù)的初始難度、第25 代難度、最后難度、平均難度以及最后難度和平均難度相對(duì)于初始難度有無顯著性差異，測(cè)試方法與4.1 節(jié)中顯著性分析部分相同.

根據(jù)表4中FDC 的測(cè)試結(jié)果可以發(fā)現(xiàn)，7 個(gè)測(cè)試函數(shù)由難到易分別為T4、T7、T6、T3、T5、T2、T1.由初始難度可知，這7 個(gè)測(cè)試函數(shù)既包括簡單問題，也包括復(fù)雜問題.函數(shù)T4、T5、T6、T7的最后難度和平均難度相對(duì)于初始難度具有顯著性差異，且最后難度與初始難度顯著性差異明顯.從問題難度降低的幅度來看，對(duì)于函數(shù)T4來說，難度降低的幅度最大，初始難度為0.04，平均難度為0.85；對(duì)于本身比較簡單的函數(shù)T1來說，難度降低的幅度為2.24%，降低的幅度較小.函數(shù)T7為一多峰復(fù)雜函數(shù)，具有大量局部最優(yōu)解，其最初始難度為0.29，進(jìn)化到后期的難度降低為0.95，難度降低3.2 倍，由此可說明T7函數(shù)在進(jìn)化過程中由原來的復(fù)雜問題轉(zhuǎn)換成為一個(gè)簡單的問題.

表4 函數(shù)困難性測(cè)試實(shí)驗(yàn)結(jié)果Table4 Experimental results for difficulty of functions

5 結(jié) 語

本文介紹了以多種群進(jìn)化算法解決優(yōu)化問題的重要性，引入了云模型理論和進(jìn)化算法困難性指標(biāo)兩個(gè)基本概念，提出了一種基于動(dòng)態(tài)區(qū)域劃分的多種群進(jìn)化算法.在傳統(tǒng)進(jìn)化算法的基礎(chǔ)上引入云模型，從而將云模型與原問題相結(jié)合，通過對(duì)云模型的期望與熵的自適應(yīng)調(diào)整來重構(gòu)優(yōu)化問題，對(duì)種群空間進(jìn)行區(qū)域劃分而簡化原有復(fù)雜問題.

最后分別對(duì)3 種不同的進(jìn)化算法和本文算法進(jìn)行測(cè)試，通過比較分析得到以下結(jié)果：1）差分進(jìn)化算法與文化算法在求解低維問題時(shí)效果較好，而求解遇到高維復(fù)雜問題時(shí)存在求解精度不高、易陷入局部最優(yōu)以及穩(wěn)定性差等問題.2）元胞遺傳算法在一定程度上能夠有效解決上述問題，但是通用性不高，因而對(duì)各類優(yōu)化問題不具備良好的適應(yīng)性.3）基于動(dòng)態(tài)區(qū)域劃分的多種群進(jìn)化算法不僅能夠有效避免差分進(jìn)化算法與文化算法求解精度不高、易陷入局部最優(yōu)以及元胞遺傳算法通用性差等缺陷，在解決高維復(fù)雜問題時(shí)同樣能準(zhǔn)確快速地找到全局最優(yōu)解.根據(jù)進(jìn)化算法困難性測(cè)試結(jié)果發(fā)現(xiàn)，在進(jìn)化算法過程中問題的困難性有所降低，特別是復(fù)雜多峰問題的困難指標(biāo)降低得更明顯，因此利用云模型對(duì)優(yōu)化問題進(jìn)行估計(jì)并對(duì)種群空間進(jìn)行區(qū)域劃分能夠獲得較好的求解效果，同時(shí)又可以提高算法的收斂速度.