自適應柯西變異人口遷移算法*

廉侃超

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

人口遷移算法PMA（Population Migration Algorithm）[1]于2003年由我國學者周永華、毛宗源提出，是一個性能較好的全局優化搜索算法。該算法主要模擬人類遷移的社會活動機理：隨經濟重心而轉移，隨人口壓力增大而擴散。但算法步驟繁瑣，對較復雜的優化問題，存在著優化精度低，易陷入局部最優等缺點。為進一步改善算法的性能，提出一種自適應柯西變異人口遷移算法ACMPMA （Adaptive Cauchy Mutation Population Migration Algorithm），數值實驗表明，改進后的人口遷移算法有效提高了算法的性能，具有搜索質量高，性能穩定等特點。

1 柯西變異

1.1 柯西分布

高斯分布和柯西分布[2]是概率論與數理統計中的常見分布。圖1是標準柯西分布和標準高斯分布概率密度函數曲線。柯西分布兩端趨于零的速度比高斯分布慢，如在PMA中對人口狀態變異，相對于高斯變異，柯西變異顯然具有更強的擾動能力，人口更易跳出局部極值，可提高搜索速度和全局尋優能力。

圖1 標準柯西、高斯分布概率密度函數圖

1.2 柯西變異

鑒于柯西分布及人口遷移算法的特點，本文對人口遷移后優惠區域的人口 xi=（x，…，x）進行柯西變異，規則如下：

由隨機變量生成函數定理[2]，式中標準柯西分布的隨 機 變 量 生 成 函 數 Cauchy（0，1）為：Cauchy（0，1）=tan[（ξ-0.5）π]，其中 ξ是[0，1]上服從均勻分布的隨機變量。

表1 本文算法（ACMPMA）與PMA的比較

2 自適應柯西變異的改進人口遷移算法

本文取消人口擴散過程，將算法步驟簡化為5步；當算法限入局部最優時，自適應對優惠區域的人口進行柯西變異。算法步驟如下：

設：Rn表示搜索空間，xi＝（x，…，x）表示第 i個人口，xi∈Rn，x表示第 i個人口的第 j分量；δi＝（，…，）表示第 i個人口的鄰域半徑，δi∈Rn，表示 δi的第 j個分量，＞0；i＝1，2，…，N，N 表示人口規模；j＝1，2，…，n，n表示 Rn的維數。

步驟 1：在搜索空間隨機產生 N 個點，x1，x2，…，xN。以每一個點 xi為中心確定其鄰域上下界 xi±δi，其中取δ＝（bj-aj）/（2N）。 計算 N 個點的值，并更新最優記錄。

步驟2：人口流動：在每個人口xi的鄰域內隨機產生一個人口，用其更新xi和最優記錄，人口流動次數加1。人口流動次數l若小于預先指定的次數，則重復步驟2，否則執行步聚3。

步驟3：人口遷移：以最優記錄的鄰域為優惠區域，在優惠區域隨機產生N個人口，替換原人口群體，更新最優記錄。若最優記錄連續兩次未變化，則對優惠區域的每個人口進行柯西變異，并更新最優記錄。收縮優惠區域：δ＝（1-Δ）δ。 若 maxδj＞α（α 為人口壓力參數），則重復步驟3，否則執行步驟4。

步驟4：迭代次數M加1，若迭代次數小于指定次數則轉步驟1，否則執行步驟5。

步驟5：輸出最優記錄。

3 算法的性能測試

本文采用 Windows XP操作系統、CPU為 Intel（R）Core（TM）2 Duo CPU T5870@2.00 GHz，內存為 2.00 GB的ThinkPad SL400筆記本電腦。編程軟件為Matlab R2006a。

3.1 本文算法與PMA的比較

選取以下4個函數對本算法及PMA算法進行測試：

該函數在（0，0）處有全局最小值 0.9。

該函數在（0，0）處有全局最小值 0。

該函數在（0，0）處有全局最小值-2。

該函數在（0，0）處有全局最小值 0。

實驗中，兩種算法分別對每個函數獨立運行50次，取最好值、最差值、平均值、成功率和標準偏差作為評價算法的性能指標。若運行的結果在全局最優值的1%范圍內，則稱本次運行是成功的。兩種算法的參數設置保持一致，均為：人口規模 N＝3，收縮系數△＝0.01，人口壓力參數 α＝1e-7，迭代次數 M＝2，人口流動次數 L＝10。測試結果如表1所示。

由表1知，本文算法從平均值、成功率和標準偏差幾個方面比PMA都更優。

3.2 本文算法與其他優化算法的比較

選取Schaffer函數作為測試函數。

該函數僅在（0，0）處有最小值 0，但在最小值附近有無窮多個局部極小值，使得尋優極為困難。

測試中，本文算法對Schaffer函數獨立運行50次，以平均最優值和收斂成功率作為評價指標。實驗比較數據如表2所示。

表2 本文算法（ACMPMA）與其他算法的比較

從表2可知，從平均最優值和收斂成功率來看，本文算法比NSMPSO、IOANGA、PMA算法效果都好。可見，ACMPMA具有較好的尋優性能。

基于人口遷移算法，算法步驟精簡，借用柯西變異的強擾動性，自適應地促使人口跳出局部極值，提高了算法的尋優精度，增強了算法的全局尋優能力。實驗數據表明，該算法具有較好的穩定性能和較高的求解質量，可有效求解無約束復雜函數的優化問題。但算法的理論證明有待研究，在更多領域的應用需進一步探索。

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

[2]王梓坤.概率論基礎及其應用[M].北京：科技出版社，1979.

[3]FAN S K S，ZAHARA E.A hybrid simplex search and particle swarm optimization for unconstrained optimization[J].European Journal of Operational Research， 2007， 108（2）：527-548.

[4]華潔，崔杜武.基于個體優化的自適應小生境遺傳算法[J].計算機工程，2010，36（1）：194-196.

[5]鄧輝，王勇，陳士亮.融合模式搜索與人口遷移的優化算法[J].計算機工程，2011，37（13）：175-177.