廉侃超

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

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

1 柯西變異

1.1 柯西分布

高斯分布和柯西分布[2]是概率論與數(shù)理統(tǒng)計中的常見分布。圖1是標(biāo)準(zhǔn)柯西分布和標(biāo)準(zhǔn)高斯分布概率密度函數(shù)曲線?？挛鞣植純啥粟呌诹愕乃俣缺雀咚狗植悸?，如在PMA中對人口狀態(tài)變異，相對于高斯變異，柯西變異顯然具有更強(qiáng)的擾動能力，人口更易跳出局部極值，可提高搜索速度和全局尋優(yōu)能力。

圖1 標(biāo)準(zhǔn)柯西、高斯分布概率密度函數(shù)圖

1.2 柯西變異

鑒于柯西分布及人口遷移算法的特點，本文對人口遷移后優(yōu)惠區(qū)域的人口 xi=（x，…，x）進(jìn)行柯西變異，規(guī)則如下：

由隨機(jī)變量生成函數(shù)定理[2]，式中標(biāo)準(zhǔn)柯西分布的隨 機(jī) 變 量 生 成 函 數(shù) Cauchy（0，1）為：Cauchy（0，1）=tan[（ξ-0.5）π]，其中 ξ是[0，1]上服從均勻分布的隨機(jī)變量。

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

2 自適應(yīng)柯西變異的改進(jìn)人口遷移算法

本文取消人口擴(kuò)散過程，將算法步驟簡化為5步；當(dāng)算法限入局部最優(yōu)時，自適應(yīng)對優(yōu)惠區(qū)域的人口進(jìn)行柯西變異。算法步驟如下：

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

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

步驟2：人口流動：在每個人口xi的鄰域內(nèi)隨機(jī)產(chǎn)生一個人口，用其更新xi和最優(yōu)記錄，人口流動次數(shù)加1。人口流動次數(shù)l若小于預(yù)先指定的次數(shù)，則重復(fù)步驟2，否則執(zhí)行步聚3。

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

步驟4：迭代次數(shù)M加1，若迭代次數(shù)小于指定次數(shù)則轉(zhuǎn)步驟1，否則執(zhí)行步驟5。

步驟5：輸出最優(yōu)記錄。

3 算法的性能測試

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

3.1 本文算法與PMA的比較

選取以下4個函數(shù)對本算法及PMA算法進(jìn)行測試：

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

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

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

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

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

由表1知，本文算法從平均值、成功率和標(biāo)準(zhǔn)偏差幾個方面比PMA都更優(yōu)。

3.2 本文算法與其他優(yōu)化算法的比較

選取Schaffer函數(shù)作為測試函數(shù)。

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

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

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

從表2可知，從平均最優(yōu)值和收斂成功率來看，本文算法比NSMPSO、IOANGA、PMA算法效果都好?？梢姡珹CMPMA具有較好的尋優(yōu)性能。

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

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

[2]王梓坤.概率論基礎(chǔ)及其應(yīng)用[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]華潔，崔杜武.基于個體優(yōu)化的自適應(yīng)小生境遺傳算法[J].計算機(jī)工程，2010，36（1）：194-196.

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