廉侃超，孟朝霞，王琴竹

（運(yùn)城學(xué)院 公共計(jì)算機(jī)教學(xué)部，山西 運(yùn)城 044000）

人口遷移算法 PMA（Population Migration Algorithm）[1，2]是我國(guó)學(xué)者周永華、毛宗源于2003年提出的一類模擬人口遷移機(jī)理的全局優(yōu)化算法，已應(yīng)用于多個(gè)領(lǐng)域。但對(duì)復(fù)雜的優(yōu)化問題，PMA存在著搜索速度慢、易陷入局部最優(yōu)等缺點(diǎn)。云模型（Cloud model）是我國(guó)學(xué)者李德毅教授提出的定性和定量轉(zhuǎn)換模型，已成功應(yīng)用于眾多領(lǐng)域。

提出一種多群體云人口遷移算法CMPMA（Cloudmodel-based Multi-colony Population Migration Algorithm），將云模型和人口遷移算法相結(jié)合，增加了群最優(yōu)記錄，進(jìn)化過程中多個(gè)群體協(xié)作尋優(yōu)。典型的測(cè)試函數(shù)和應(yīng)用實(shí)例的仿真結(jié)果表明，CMPMA是可行、高效、穩(wěn)定的。

1 人口遷移算法和云模型

1.1 基本人口遷移算法原理

原人口遷移算法的基本框架[1]如下：

（1）人們?cè)谠M(jìn)行人口流動(dòng)；（2）受優(yōu)惠地區(qū)吸引出現(xiàn)人口遷移；（3）人口在優(yōu)惠地區(qū)進(jìn)行流動(dòng)直到人口壓力達(dá)到一定限度；（4）人口從優(yōu)惠地區(qū)遷出，向外擴(kuò)散，尋找新的機(jī)會(huì)。

在這個(gè)持續(xù)不斷的過程中，人口一方面經(jīng)遷移而聚集到優(yōu)惠區(qū)域，另一方面又因人口壓力的增加而遷離優(yōu)惠區(qū)域向外擴(kuò)散?？梢?，人口遷移是人口在不斷的聚集和擴(kuò)散的矛盾運(yùn)動(dòng)中尋找優(yōu)惠區(qū)域的過程。

1.2 云模型[3]

定義 設(shè)U是一個(gè)用精確數(shù)值表示的論域 （一維的或多維的），U上對(duì)應(yīng)著定性概念?A，對(duì)于論域中的任意一個(gè)元素 x，都存在一個(gè)有穩(wěn)定傾向的隨機(jī)數(shù) y=μA（x），叫作x對(duì)概念?A的確定度，μA（x）在U上的分布稱為云模型，簡(jiǎn)稱云。當(dāng)μA（x）服從正態(tài)分布時(shí)，稱為正態(tài)云模型。

云的數(shù)字特征用期望Ex、熵En和超熵He來表征，如圖1所示。它們反映了定性概念?A整體上的定量特征。生成云滴的算法或硬件稱為云發(fā)生器。

基本云發(fā)生器的算法步驟如下：

輸入：表示定性概念A(yù)?的3個(gè)數(shù)字特征值Ex、En、He和云滴數(shù)n。

輸出：n個(gè)云滴的定量值以及每個(gè)云滴代表概念A(yù)?的確定度。

（1）生成以En為期望值，He為標(biāo)準(zhǔn)差的一個(gè)正態(tài)隨機(jī)數(shù) En′；

（2）生成以Ex為期望值，En′為標(biāo)準(zhǔn)差的正態(tài)隨機(jī)數(shù)x；

（3）令x為定性概念A(yù)?的一次具體量化值，稱為云滴；

（4）計(jì)算 y=

（5）令y為x屬于定性概念A(yù)?的確定度；

（6）（x，y）完整地反映了這一次定性定量轉(zhuǎn)換的全部?jī)?nèi)容；

（7）重復(fù)步驟（1）～步驟（6）直到產(chǎn)生 n 個(gè)云滴為止。

2 多群體云人口遷移算法

2.1 人口流動(dòng)思想的改進(jìn)

在人口遷移算法中，人口流動(dòng)是“人們?cè)谠M(jìn)行人口流動(dòng)”，即每一次迭代過程中，人口的多次流動(dòng)都是在初始人口的鄰域范圍內(nèi)流動(dòng)。本文提出一種改進(jìn)的人口流動(dòng)方法，人口在其鄰域范圍流動(dòng)后，再次流動(dòng)的鄰域范圍以新人口為中心重新構(gòu)建。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的人口流動(dòng)提高了算法效率。

2.2 云模型與人口遷移算法的結(jié)合

人口遷移算法初始群體的隨機(jī)性和人口流動(dòng)的漫無目的性，在一定程度上影響了算法的尋優(yōu)性能。云模型具有隨機(jī)性和穩(wěn)定傾向性的特點(diǎn)，隨機(jī)性可以避免搜索陷入局部極值，而穩(wěn)定傾向性又可以很好地定位全局最值。分別用不同參數(shù)的基本云發(fā)生器來產(chǎn)生初始群體和實(shí)現(xiàn)人口流動(dòng)操作，同時(shí)增加了群最優(yōu)記錄，提出CMPMA算法。

2.3 多群體云人口遷移算法（CMPMA）

設(shè)Rn表示搜索空間，人及其所在地用點(diǎn)表示，xi=（，…，)表示第 i個(gè)人口，xi∈Rn，表示第 i個(gè)人口的第 j個(gè)分量；δi=（，…，δni）表示第 i個(gè)人口的鄰域半徑，δi∈Rn，表示 δi的第 j個(gè)分量，>0；i=1，2，…，N，N表示人口規(guī)模；j=1，2，n，n，表示 Rn的維數(shù)。

多群體云人口遷移算法的具體步驟如下：

（1）設(shè)定Ex為搜索空間中心點(diǎn)，En為尋優(yōu)空間的1/6，He=1，用基本云發(fā)生器在尋優(yōu)空間產(chǎn)生N個(gè)點(diǎn)，x1，x2，…，xN。 以每一個(gè)點(diǎn) xi為中心確定其鄰域上下界 xi±δi，其中取=（bj-aj）/（2N）。 計(jì)算 N 個(gè)點(diǎn)的值，并按其初始化最優(yōu)記錄和群最優(yōu)記錄。

（2）人口流動(dòng)（由基本云發(fā)生器實(shí)現(xiàn)）：對(duì)每一個(gè) xi都執(zhí)行的操作有：①Ex=xi；②En=δi；③He=En/10；（式中的參數(shù)10是實(shí)驗(yàn)中的經(jīng)驗(yàn)取值。）④由基本云發(fā)生器生成一個(gè)云滴更新 xi。 若>bj，則令 xji=bj；若＜aj，則令=aj。更新群最優(yōu)記錄。以更新后的每個(gè)xi為中心重新構(gòu)建鄰域空間，構(gòu)建方法同步驟（1）。人口流動(dòng)次數(shù)若小于預(yù)先指定的次數(shù)則重復(fù)步驟（2）。

（3）群體遷移：對(duì)群最優(yōu)記錄中的每個(gè)人口執(zhí)行：以其為中心，按δ各分量的大小確定優(yōu)惠區(qū)域，在該區(qū)域內(nèi)均勻隨機(jī)產(chǎn)生N個(gè)點(diǎn)，更新群最優(yōu)記錄，收縮優(yōu)惠區(qū)域：δ=（1-Δ）δ。若 max δj>α（α 為人口壓力參數(shù)），則重復(fù)步驟（3）。以群最優(yōu)記錄更新最優(yōu)記錄。

（4）人口擴(kuò)散：用基本云發(fā)生器重新產(chǎn)生初始群體并確定人口流動(dòng)區(qū)域，更新最優(yōu)記錄，清空群最優(yōu)記錄。迭代次數(shù)m加1，若迭代次數(shù)不大于指定次數(shù)則轉(zhuǎn)步驟（2）。

（5）輸出最優(yōu)記錄。

3 多群體云人口遷移算法（CMPMA）性能分析

3.1 函數(shù)測(cè)試

本文選取了3個(gè)典型的基準(zhǔn)測(cè)試函數(shù)[4]進(jìn)行仿真實(shí)驗(yàn)，仿真均在Matlab2006a下編程運(yùn)行。

（1）f1（x1，x2）=x12+x22-5≤x1，x2≤5

DeJong 函數(shù)，單峰函數(shù)，在（x1，x2）處，有最小值 0。（2）f2（x1，x2）=100（x12+x2）2+（1-x1）2-5≤x1，x2≤5 Rosenbrock 函數(shù)：二維非凸、病態(tài)函數(shù)， 在（x1，x2）=（1，1）處，有最小值 0。

Sinc 函數(shù)，多峰函數(shù)，在（x1，x2）=（0，0）處，有最大值 1。

算法參數(shù)為：人口規(guī)模N=3，人口流動(dòng)次數(shù)l=10，迭代次數(shù)m=2。收縮系數(shù)Δ和人口壓力參數(shù)α的設(shè)置如表1所示。

表1 參數(shù)Δ和α設(shè)置表

表2 本文算法CMPMA與參考文獻(xiàn)[4]比較

為便于比較，對(duì)函數(shù)f1～f3獨(dú)立運(yùn)行30次，統(tǒng)計(jì)30次中搜索到的最優(yōu)值中的最好值、最差值、平均值作為評(píng)價(jià)指標(biāo)，與參考文獻(xiàn)[4]比較，結(jié)果如表2所示。

從表 2可知，對(duì)函數(shù) f1～f3，參考文獻(xiàn)[4]的 CAFSA算法的搜索結(jié)果只是接近理論最優(yōu)，本文算法CMPMA可以穩(wěn)定收斂到理論上的最優(yōu)值，且參考文獻(xiàn) [4]的CAFSA算法設(shè)定的迭代次數(shù)為50，而本文算法CMPMA設(shè)定的迭代次數(shù)為2?？梢?，CMPMA算法對(duì)復(fù)雜函數(shù)的尋優(yōu)效率和精度都較高，搜索結(jié)果令人滿意。

3.2 實(shí)例測(cè)試

為進(jìn)一步驗(yàn)證算法的有效性，將CMPMA應(yīng)用到最小推力滾珠導(dǎo)軌優(yōu)化設(shè)計(jì)模型[5-6]中，該實(shí)例設(shè)計(jì)要求在外載荷一定時(shí)，推力最小，即運(yùn)動(dòng)最靈敏。優(yōu)化數(shù)學(xué)模型描述如下：

s.t.30°≤α≤90°，30°≤β≤60°，0.3≤ε≤1，40≤p0≤80式中，α是負(fù)荷p與水平軸夾角；β是導(dǎo)軌V形槽半角；ε是表面硬度系數(shù)；p0是初安裝負(fù)荷；k是滾動(dòng)摩擦系數(shù)；K是許用應(yīng)力；p是運(yùn)動(dòng)件上全部負(fù)荷；z是滾珠個(gè)數(shù)。

各參數(shù)采用參考文獻(xiàn) [5-6]的取值：p=50 N，k=0.01 mm，K=0.5 N/mm2，z=4。 CMPMA 各參數(shù)設(shè)置為：人口規(guī)模 N=3，人口流動(dòng)次數(shù) l=10，收縮系數(shù) Δ=0.01，人口壓力參數(shù)α=0.1，迭代次數(shù)m=2。進(jìn)行20次獨(dú)立實(shí)驗(yàn)，每次得到的最優(yōu)推力值T=0.68248707619912（N），優(yōu)化參數(shù) α=30.000 000 000 000 00°，β=60.000 000 000 000 00°，ε=0.300 000 000 000 00，p0=40.000 000 000 000 00。 參考文獻(xiàn)[6]的復(fù)合形法得到的最優(yōu)值 T=0.68 428（N），參考文獻(xiàn)[5]的最優(yōu)結(jié)果為 T=0.682 5（N），優(yōu)化參數(shù) α=30.052 8°，β=59.998 4°，ε=0.3，p0=40.000 5。 可見，與參考文獻(xiàn)[5-6]相比，本文的尋優(yōu)結(jié)果精度更高。實(shí)例測(cè)試表明，CMPMA在工程設(shè)計(jì)領(lǐng)域是可行、有效的。

基于原人口遷移算法，增加了群最優(yōu)記錄，由多個(gè)群體協(xié)作尋優(yōu)，并改進(jìn)了人口流動(dòng)的思想。借鑒正態(tài)云模型的隨機(jī)性和穩(wěn)定傾向性，提出用不同參數(shù)設(shè)置的基本云發(fā)生器分別產(chǎn)生初始群體和實(shí)現(xiàn)人口流動(dòng)。多群體云人口遷移算法通過利用人口遷移算法的進(jìn)化體制保留了其尋優(yōu)性能，又通過多群體合作，并結(jié)合正態(tài)云模型的穩(wěn)定傾向性、隨機(jī)性特點(diǎn)進(jìn)一步提高了算法的搜索效率。經(jīng)典函數(shù)和實(shí)例測(cè)試結(jié)果證明了CMPMA算法的尋優(yōu)高效性和穩(wěn)定性。算法在其他領(lǐng)域的進(jìn)一步拓展和其理論證明是下一步要做的工作。

[1]周永華，毛宗源.一種新的全局優(yōu)化搜索算法-人口遷移算法（I）[J].華南理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2003，31（3）：1-5.

[2]周永華，毛宗源.一種新的全局優(yōu)化搜索算法-人口遷移算法（II）[J].華南理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2003，31（4）：41-43.

[3]戴朝華，朱云芳，陳維榮，等.云遺傳算法及其應(yīng)用[J].電子學(xué)報(bào)，2007，35（7）：1419-1424.

[4]曲良東，何登旭.一種混沌人工魚群優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（22）：40-42.

[5]張梅鳳，邵誠(chéng)，甘勇，等.基于變異算子與模擬退火混合的人工魚群優(yōu)化算法 [J].電子學(xué)報(bào)，2006，34（8）：1381-1385.

[6]何獻(xiàn)忠，李萍，黃航汗，等.優(yōu)化技術(shù)及其應(yīng)用（第二版）[M].北京：北京理工大學(xué)出版社，1995.