具有收縮因子的自適應(yīng)鴿群算法用于函數(shù)優(yōu)化問題

郭瑞+趙汝鑫+吳海舟+任東+范佳偉

摘 要：文中在鴿群算法的基礎(chǔ)上添加收斂因子并使用自適應(yīng)策略，通過標準的函數(shù)優(yōu)化對算法進行了測試，實驗結(jié)果表明，通過添加收斂因子和自適應(yīng)策略的鴿群算法能有效提高收斂速度且具有一定競爭力，同時驗證了在一些情況下全局搜索的優(yōu)越性。

關(guān)鍵詞：鴿群算法；收斂因子；自適應(yīng)策略；測試函數(shù)；群智能優(yōu)化算法

中圖分類號：TP114 文獻標識碼：A 文章編號：2095-1302（2017）05-00-04

0 引 言

元啟發(fā)式優(yōu)化技術(shù)非常流行，在過去二十年，它們中的一些算法如遺傳算法，蟻群算法和粒子群算法在計算機科學領(lǐng)域及其他科學領(lǐng)域非常有名[1]。基于群體的群體智能算法已被廣泛接受，并成功應(yīng)用于求解優(yōu)化問題中。近年來，出現(xiàn)許多基于群體的群體智能算法，如人工蜂群算法[2]，人工魚群算法[3]和布谷鳥算法[4]等。一些生物啟發(fā)優(yōu)化算法正在嘗試模擬自然生態(tài)系統(tǒng)機制，增強現(xiàn)代優(yōu)化技術(shù)的可行性，為復雜組合優(yōu)化問題提供了切實可行的解決方案。對基于生態(tài)機制創(chuàng)建的元啟發(fā)式算法進行改進，使算法具有更好的收斂速度，并提高原算法的競爭力。

1 鴿群算法及收縮因子與自適應(yīng)策略

鴿群算法（Pigeon-Inspired Optimization，PIO）[5]是一種群智能優(yōu)化算法，該算法的靈感來源于鴿群利用地磁和地標歸巢，對歸巢過程分析建立的數(shù)學模型。一項檢測鴿子在不同磁場探測能力的調(diào)查表明：鴿子具有很強的歸巢能力，是因為鴿子嘴上的鐵晶體可以根據(jù)地磁場強弱為鴿子指明方向。在古羅馬時代就有人知道鴿子具有歸巢的本能，而信鴿在較早時就被用作通信工具。當信鴿距離自己目的地較遠時利用地磁場來辨別方向，當距離目的地較近時就利用當?shù)氐貥诉M行導航。信鴿利用地磁場和地標可以很容易地找到目的地。在PIO中地圖和指針算子模型的提出基于地磁場和太陽，而地標算子模型的提出則基于地標。收縮因子和策略的添加能使PIO算法具有更快的收斂速度和優(yōu)越性。

1.1 地圖模型

地圖模型的建立基于地磁場，我們分別用xi和yi來表示第i只鴿子的位置和速度。在二維空間里，位置和速度在每次迭代中進行更新。第i只鴿子的速度和位置將用如下公式進行迭代計算：

（1）

（2）

第i只鴿子的速度由它上一代速度和當前鴿子最好位置和所在位置共同決定，其中R是地圖因子，rand是一個隨機數(shù)，t為代數(shù)。而第i只鴿子的位置由之前的位置和當前速度決定。所有鴿子的飛行均通過地圖來保證，進行比較可得到鴿子的最好位置，即Xg。每一只鴿子將根據(jù)公式（1）向擁有最好位置的鴿子進行方向調(diào)整和飛行，而公式（2）則進行的是位置調(diào)整。

1.2 地標模型

地標模型根據(jù)鴿子利用地標來進行導航而建立。在利用地標導航時，距離目的地的位置比利用地圖導航的距離更近，如果鴿子對現(xiàn)在所處位置地標不熟悉，則在附近鴿子的帶領(lǐng)下飛行，當找到標志性建筑物或者熟悉位置時，則根據(jù)經(jīng)驗自由飛行。在地標模型中，用Np來記錄每一代中一半鴿子的個數(shù)，Xc（t）為第t代所有鴿子的中心位置，假如每一只鴿子可以飛直線距離到達目的地，將有如下公式：

（3）

（4）

（5）

公式中，fitness（x）是每只鴿子的質(zhì)量，當fitness（Xi （t））= 1/[fmin（Xi （t））+ε]時，針對的是最小優(yōu)化問題；當fitness（Xi（t））= fmax（Xi（t））時，則針對的是最大優(yōu)化問題。用Xp來代替每次迭代的最優(yōu)位置，Xp=min（Xi1，Xi2，...，XiNc）。所有鴿子的中心是每次迭代的目的地，在Np之外的鴿子將跟著那些靠近目的地的鴿子飛行。而靠近目的地的鴿子將更快地飛到目的地。

1.3 添加收縮因子及自適應(yīng)策略

鴿群優(yōu)化算法的基本思想來源于對鴿群歸巢過程的研究及行為模擬。在原始PIO算法基礎(chǔ)上提出一種改進的收縮因子PIO（Constriction Factor PIO，CFPIO）算法，用以加速算法收斂。CFPIO算法在收斂性方面效果良好。速度更新原則如下：

（6）

其中，，φ=φ1+φ2，φ>4。添加收縮因子后發(fā)現(xiàn)CFPIO容易陷入局部最優(yōu)，因為鴿群不斷向全局最優(yōu)靠攏，當鴿群的位置接近全局最優(yōu)位置Xg，速度更新公式的第二項為0時，鴿子位置就得不到更新，出現(xiàn)停滯情況。若出現(xiàn)這種情況，便重新初始化鴿群的i位置，以增強鴿群活力，避免因停滯而陷入局部最優(yōu)。

在CFPIO的基礎(chǔ)上添加一個位置因子γ（γ≥0），測試鴿子當前位置與全局最優(yōu)鴿子的距離d（d=‖X-G‖2），速度因子ε（ε≥0），判斷鴿子的飛行速度，一旦鴿子接近Xg（d<γ），并且飛行速度小于設(shè)定的速度因子ε（|V|<ε），則認為該鴿子可能出現(xiàn)停滯，對該鴿子進行位置初始化，保持鴿子的多樣性，增加活力，以避免局部最優(yōu)。

2 結(jié)果與討論

2.1 實驗環(huán)境與參數(shù)設(shè)置

本文使用10個基準測試函數(shù)來驗證添加收縮因子的鴿群算法的有效性和可行性。本實驗采用Matlab R2012a編寫仿真程序，在Windows XP、主頻為2.99 GHz，RAM為1.75 GB的PC機上實現(xiàn)。除添加收縮因子的鴿群算法（CFPIO）外，實驗中還用到蝙蝠算法（BA）以及PIO。設(shè)置種群數(shù)量為20個，最大迭代次數(shù)為1 000次，維數(shù)為20，采用獨立運行30次最優(yōu)的平均值作為測試結(jié)果。

2.2 測試函數(shù)

由于單峰函數(shù)和多峰函數(shù)各有所長，所以在該仿真實驗中，主要選取這兩類基準測試函數(shù)，函數(shù)f1～f5是單峰，函數(shù)f6～f10是多峰。兩類函數(shù)的區(qū)別在于多峰函數(shù)有大量局部最優(yōu)值，它們對探測檢查和避免局部最優(yōu)有好處。而單峰函數(shù)只有全局最優(yōu)值，這適合標記算法的開采。實驗中用到的10個測試函數(shù)如下：

（1）Step函數(shù)

，-100≤xi≤100（i=1，2，…，n；n=30），在（0，0，…，0）處取得全局最小值0。

（2）Rosenbrock函數(shù)

，-30≤xi≤30（i=1，2，…，n； n=30），在（0，0，…，0）處取得全局最小值0。

（3）Schwefels 2.22 函數(shù)

，-10≤xi≤10（i=1，2，…，n；n=30），在（0，0，…，0）處取得全局最小值0。

（4） Schwefels 1.2 函數(shù)

，-100≤xi≤100（i=1，2，…，n；n=30），在（0，0，…，0）處取得全局最小值0。

（5）Sphere函數(shù)

，-100≤xi≤100（i=1，2，…， n； n=30），在（0，0，…，0）處取得全局最小值0。

（6）Penalized2函數(shù)

，-50≤xi≤50（i=1，2，…，n； n=30），在（0，0，…，0）處取得全局最小值0。

（7）Penalized1函數(shù)

其中，-50≤xi≤50（i=1，2，…，n； n=30），在（0，0，…，0）處取得全局最小值0。

（8）Griewangk函數(shù)

，-600≤xi≤ 600（i=1，2，…，n；n=30），在（0，0，…，0）處取得全局最小值0。

（9）Ackley函數(shù)

，-32≤xi≤32（i=1，2，…，n； n=30），在（0，0，…，0）處取得全局最小值0。

（10）Rastrigin函數(shù)

，-5.12≤xi≤5.12（i=1，2，…，n； n=30），在（0，0，…，0）處取得全局最小值0。

2.3 實驗結(jié)果

實驗結(jié)果見表1所列。

從表1可看出，在單峰函數(shù)方面，對于函數(shù)f1，CFPIO的最優(yōu)精度和平均值可達到0，均比PIO和BA高。對于函數(shù)f2，BA的最優(yōu)精度相對于CFPIO較好，均比PIO高出2個數(shù)量級，在平均值方面CFPIO和BA都比PIO高3個數(shù)量級。對于函數(shù)f3，CFPIO的最優(yōu)值精度和平均值都比BA和PIO高14個數(shù)量級。對于函數(shù)f4，BA與PIO在最優(yōu)精度和平均值方面相差不大，而CFPIO在最優(yōu)精度和平均值方面比它們高出25個和19個精度。對于函數(shù)f5，PIO比BA的最優(yōu)精度和平均值分別高出1個數(shù)量級，而CFPIO比PIO高出62個數(shù)量級。

在多峰函數(shù)方面，對于函數(shù)f6，CFPIO的最優(yōu)值精度比BA和PIO高3個數(shù)量級，而平均值分別高4和6個數(shù)量級。對于函數(shù)f7，CFPIO的最優(yōu)值精度達到e-3，分別比BA和PIO高4和5個數(shù)量級，而平均值分別比BA和PIO高出3和4個數(shù)量級。對于函數(shù)f8，CFPIO的最優(yōu)值精度均好于BA和PIO，而平均值優(yōu)于BA和PIO達5和4個數(shù)量級。對于函數(shù)f9，BA和PIO的最優(yōu)精度和平均值只相差一個數(shù)量級，而CFPIO均高于它們14和15個數(shù)量級。對于函數(shù)f10，整體而言BA和PIO相差不大，CFPIO有最優(yōu)精度為0，均值比BA和PIO高2個數(shù)量級。

f1～f10的適應(yīng)度函數(shù)收斂曲線如圖1～圖10所示。

表1 BA、PIO和CFPIO實驗結(jié)果比較

測試函數(shù) 算法 最優(yōu)值 平均值

f1 BA 1.322 2e+04 2.014 1e+04

PIO 153.805 9 1.041 0e+03

CFPIO 0 0

f2 BA 23.699 7 86.788 5

PIO 5.312 3e+04 1.700 3e+05

CFPIO 25.989 9 26.887 2

f3 BA 55.889 2 64.615 0

PIO 13.786 5 24.155 2

CFPIO 1.324 2e-16 1.165 9e-14

f4 BA 1.003 1e+04 2.820 1e+04

PIO 225.509 7 1.209 9e+04

CFPIO 2.333 6e-21 7.075 6e-15

f5 BA 1.464 7e+04 2.115 2e+04

PIO 184.139 2 1.366 9e+03

CFPIO 1.297 5e-61 7.155 8e-59

f6 BA 90.623 5 1.201 2e+03

PIO 34.298 1 1.006 0e+05

CFPIO 0.100 1 0.503 0

f7 BA 21.531 2 34.623 9

PIO 3.608 8 428.106 7

CFPIO 0.006 5 0.047 0

f8 BA 388.079 7 500.091 2

PIO 4.874 6 11.705 2

CFPIO 0 0.002 9

f9 BA 18.441 9 19.153 9

PIO 6.349 4 8.833 3

CFPIO 1.154 6e-14 1.604 6e-14

f10 BA 122.605 0 197.323 3

PIO 88.616 1 163.301 5

CFPIO 0 0.288 2

圖1 f1的適應(yīng)度函數(shù)收斂曲線

圖2 f2的適應(yīng)度函數(shù)收斂曲線

圖3 f3的適應(yīng)度函數(shù)收斂曲線

圖4 f4的適應(yīng)度函數(shù)收斂曲線

圖5 f5的適應(yīng)度函數(shù)收斂曲線

圖6 f6的適應(yīng)度函數(shù)收斂曲線

圖7 f7的適應(yīng)度函數(shù)收斂曲線

圖8 f8的適應(yīng)度函數(shù)收斂曲線

圖9 f9的適應(yīng)度函數(shù)收斂曲線

圖10 f10的適應(yīng)度函數(shù)收斂曲線

由上圖可知，當?shù)Y(jié)束時，CFPIO優(yōu)于BA和PIO。CFPIO不僅收斂速度快，且其算法收斂精度接近0。通過以上各函數(shù)的優(yōu)化結(jié)果可以看出，該改進算法有效、可行。

3 結(jié) 語

對PIO算法添加收縮因子和自適應(yīng)策略進行分析，該算法模擬了鴿群歸巢的特性，利用地磁場和地標向目的地飛行。從函數(shù)優(yōu)化結(jié)果可以看出，收縮因子和自適應(yīng)改善了鴿群算法，不僅可有效提高收斂速度，還讓鴿群算法具有競爭力，也驗證了在一些情況下全局搜索的優(yōu)越性。此外，雖然添加收縮因子和策略后的PIO提高了收斂速度，但在求解一些復雜收斂速度問題時速度較慢，收斂精度偏低，穩(wěn)定性較差，而這些問題將在后期進行進一步研究。

參考文獻

[1] Seyedali Mirjalili， Seyed Mohammad Mirjalili， Andrew Lewis. Grey Wolf Optimizer[J].Advances in Engineering Software， 2014，69（3）：46 - 61.

[2] Karaboga D， Basturk B.A powerful and efficient algorithm for numerical function optimization： artificial bee colony algorithm[J]. Journal of Global Optimization2007，39（3）： 459-471.

[3] LI X L，SHAO Z，QIAN J .An optimizing method based on autonomous animats： fish-swarm algorithm[J].Systems Engineering Theory and Practice，2002，22（11） ： 32-38.

[4] Rajabioun R.Cuckoo optimization algorithm[J].Applied Soft Computing，2011，11（8）：5508-5518.

[5] Haibin Duan ，Peixin Qiao.Pigeon-inspired optimization：a new swarm intelligence optimizer for air robot path planning[J]. International Journal of Intelligent Computing and Cybernetics，2014， 7（1）：24-37.

[6]錢偉懿，王艷杰.帶自適應(yīng)壓縮因子粒子群優(yōu)化算法[J].遼寧工程技術(shù)大學學報，2010，29（5）：949-952.

[7]胡欣欣.求解函數(shù)優(yōu)化問題的改進布谷鳥搜索算法[J].計算機工程與技術(shù)，2013，34（10）：3639-3642.

[8]聶建亮，程傳錄，郭春喜，等.基于粒子群優(yōu)化算法的多因子自適應(yīng)濾波[J].武漢大學學報（信息科學版），2013，38（2）：136-139.