多群體云人口遷移算法*

廉侃超，孟朝霞，王琴竹

（運城學院 公共計算機教學部，山西 運城 044000）

人口遷移算法 PMA（Population Migration Algorithm）[1，2]是我國學者周永華、毛宗源于2003年提出的一類模擬人口遷移機理的全局優化算法，已應用于多個領域。但對復雜的優化問題，PMA存在著搜索速度慢、易陷入局部最優等缺點。云模型（Cloud model）是我國學者李德毅教授提出的定性和定量轉換模型，已成功應用于眾多領域。

提出一種多群體云人口遷移算法CMPMA（Cloudmodel-based Multi-colony Population Migration Algorithm），將云模型和人口遷移算法相結合，增加了群最優記錄，進化過程中多個群體協作尋優。典型的測試函數和應用實例的仿真結果表明，CMPMA是可行、高效、穩定的。

1 人口遷移算法和云模型

1.1 基本人口遷移算法原理

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

（1）人們在原籍進行人口流動；（2）受優惠地區吸引出現人口遷移；（3）人口在優惠地區進行流動直到人口壓力達到一定限度；（4）人口從優惠地區遷出，向外擴散，尋找新的機會。

在這個持續不斷的過程中，人口一方面經遷移而聚集到優惠區域，另一方面又因人口壓力的增加而遷離優惠區域向外擴散。可見，人口遷移是人口在不斷的聚集和擴散的矛盾運動中尋找優惠區域的過程。

1.2 云模型[3]

定義 設U是一個用精確數值表示的論域 （一維的或多維的），U上對應著定性概念?A，對于論域中的任意一個元素 x，都存在一個有穩定傾向的隨機數 y=μA（x），叫作x對概念?A的確定度，μA（x）在U上的分布稱為云模型，簡稱云。當μA（x）服從正態分布時，稱為正態云模型。

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

基本云發生器的算法步驟如下：

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

輸出：n個云滴的定量值以及每個云滴代表概念A?的確定度。

（1）生成以En為期望值，He為標準差的一個正態隨機數 En′；

（2）生成以Ex為期望值，En′為標準差的正態隨機數x；

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

（4）計算 y=

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

（6）（x，y）完整地反映了這一次定性定量轉換的全部內容；

（7）重復步驟（1）～步驟（6）直到產生 n 個云滴為止。

2 多群體云人口遷移算法

2.1 人口流動思想的改進

在人口遷移算法中，人口流動是“人們在原籍進行人口流動”，即每一次迭代過程中，人口的多次流動都是在初始人口的鄰域范圍內流動。本文提出一種改進的人口流動方法，人口在其鄰域范圍流動后，再次流動的鄰域范圍以新人口為中心重新構建。實驗結果表明，改進的人口流動提高了算法效率。

2.2 云模型與人口遷移算法的結合

人口遷移算法初始群體的隨機性和人口流動的漫無目的性，在一定程度上影響了算法的尋優性能。云模型具有隨機性和穩定傾向性的特點，隨機性可以避免搜索陷入局部極值，而穩定傾向性又可以很好地定位全局最值。分別用不同參數的基本云發生器來產生初始群體和實現人口流動操作，同時增加了群最優記錄，提出CMPMA算法。

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

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

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

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

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

（3）群體遷移：對群最優記錄中的每個人口執行：以其為中心，按δ各分量的大小確定優惠區域，在該區域內均勻隨機產生N個點，更新群最優記錄，收縮優惠區域：δ=（1-Δ）δ。若 max δj>α（α 為人口壓力參數），則重復步驟（3）。以群最優記錄更新最優記錄。

（4）人口擴散：用基本云發生器重新產生初始群體并確定人口流動區域，更新最優記錄，清空群最優記錄。迭代次數m加1，若迭代次數不大于指定次數則轉步驟（2）。

（5）輸出最優記錄。

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

3.1 函數測試

本文選取了3個典型的基準測試函數[4]進行仿真實驗，仿真均在Matlab2006a下編程運行。

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

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

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

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

表1 參數Δ和α設置表

表2 本文算法CMPMA與參考文獻[4]比較

為便于比較，對函數f1～f3獨立運行30次，統計30次中搜索到的最優值中的最好值、最差值、平均值作為評價指標，與參考文獻[4]比較，結果如表2所示。

從表 2可知，對函數 f1～f3，參考文獻[4]的 CAFSA算法的搜索結果只是接近理論最優，本文算法CMPMA可以穩定收斂到理論上的最優值，且參考文獻 [4]的CAFSA算法設定的迭代次數為50，而本文算法CMPMA設定的迭代次數為2。可見，CMPMA算法對復雜函數的尋優效率和精度都較高，搜索結果令人滿意。

3.2 實例測試

為進一步驗證算法的有效性，將CMPMA應用到最小推力滾珠導軌優化設計模型[5-6]中，該實例設計要求在外載荷一定時，推力最小，即運動最靈敏。優化數學模型描述如下：

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

各參數采用參考文獻 [5-6]的取值：p=50 N，k=0.01 mm，K=0.5 N/mm2，z=4。 CMPMA 各參數設置為：人口規模 N=3，人口流動次數 l=10，收縮系數 Δ=0.01，人口壓力參數α=0.1，迭代次數m=2。進行20次獨立實驗，每次得到的最優推力值T=0.68248707619912（N），優化參數 α=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。 參考文獻[6]的復合形法得到的最優值 T=0.68 428（N），參考文獻[5]的最優結果為 T=0.682 5（N），優化參數 α=30.052 8°，β=59.998 4°，ε=0.3，p0=40.000 5。 可見，與參考文獻[5-6]相比，本文的尋優結果精度更高。實例測試表明，CMPMA在工程設計領域是可行、有效的。

基于原人口遷移算法，增加了群最優記錄，由多個群體協作尋優，并改進了人口流動的思想。借鑒正態云模型的隨機性和穩定傾向性，提出用不同參數設置的基本云發生器分別產生初始群體和實現人口流動。多群體云人口遷移算法通過利用人口遷移算法的進化體制保留了其尋優性能，又通過多群體合作，并結合正態云模型的穩定傾向性、隨機性特點進一步提高了算法的搜索效率。經典函數和實例測試結果證明了CMPMA算法的尋優高效性和穩定性。算法在其他領域的進一步拓展和其理論證明是下一步要做的工作。

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

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

[3]戴朝華，朱云芳，陳維榮，等.云遺傳算法及其應用[J].電子學報，2007，35（7）：1419-1424.

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

[5]張梅鳳，邵誠，甘勇，等.基于變異算子與模擬退火混合的人工魚群優化算法 [J].電子學報，2006，34（8）：1381-1385.

[6]何獻忠，李萍，黃航汗，等.優化技術及其應用（第二版）[M].北京：北京理工大學出版社，1995.