基于柯西變異的自適應花授粉算法

王興凡　孟繼志

摘 要：本文在異花授粉過程中引入自適應步長，使得算法在初期以較大的步長提高搜索能力，后期以較小的步長提高尋優精度。在自花授粉過程引入柯西變異進行隨機擾動，增加種群的多樣性，由此提出了一種基于柯西分布的自適應花授粉算法（CFPA），并通過6個標準測試函數進行測試比較。仿真結果表明，改進算法在尋優速度、精度和魯棒性方面均存在優勢。最后，將改進算法用于求解非線性方程組，算例結果證明了其優越性。

關鍵詞：花授粉算法； 柯西變異； 尋優性能

Abstract： In view of the defects of floral pollination algorithms in plants， this paper introduces an adaptive step size in the process of cross-pollination， which makes the algorithm improve the search ability in a larger step at an early stage and improve the search accuracy in a smaller step at a later stage. The Cauchy mutation is introduced into the self-pollination process to carry out random perturbation to increase the diversity of the population. A Cauchy-distribution-based adaptive flower pollination algorithm （CFPA） is proposed and tested and compared by using six standard test functions. Simulation results show that the improved algorithm has advantages in optimization speed， optimization accuracy and robustness. Finally， the improved algorithm is used to solve the nonlinear equations. The results of the example prove its superiority.

Key words： flower pollination algorithm； Cauchy mutation； optimizing performance

引言

受自然界生物群體智能行為和自然界進化規律的啟發，國內外學者提出了眾多的群智能優化算法，如螢火蟲算法[2]（FA）、布谷鳥算法[3]（CS）、蝙蝠算法[4]（BA）。2012年，受植物花朵授粉過程的啟發，著名學者Yang提出了植物花授粉算法[1]（Flower Pollination Algorithm），該算法通用性強、魯棒性好、編程簡易，具有較好的穩定性，已成功應用于多目標優化[5]、RGB圖像壓縮[6]、數獨問題求解[7]、大整數規劃問題[8]，現已成為人工智能一個新的熱點。但FPA也存在易陷入局部最優、理論基礎薄弱、收斂性證明缺乏等不足。鑒于花授粉算法存在的不足，眾多學者對其進行了改進。肖輝輝[9]等人把模擬退火算法融入到花朵授粉算法中，其概率突跳策略使算法避免陷入局部最優，其全域搜索的性能增強了算法的全局尋優能力； 崔麗群[10]等人引入和聲搜索算法提升花授粉算法收斂速度，引入折射原理提高種群的多樣性，使得算法易于跳出局部最優。本文在異花授粉過程中引入自適應步長，使得算法初期能夠以較大的步長提高搜索能力，后期能夠以較小的步長提高尋優精度，并在自花授粉過程引入柯西變異進行隨機擾動，增加種群的多樣性，增強算法的尋優能力。

1 基本花授粉算法

螢火蟲算法（FA）靈感來自于螢火蟲發光吸引異性、布谷鳥算法（CS）來源于布谷鳥的巢寄卵生行為、蝙蝠算法（BA）受啟發于蝙蝠的回聲定位行為，而FPA同樣是受到自然界植物花授粉這一行為啟發而得出靈感，自然界大約有90%的植物進行生物傳粉（Biotic pollination），10%左右進行非生物傳粉（Abiotic pollination）。非生物傳粉需要通過一些介質進行傳播，如：蜜蜂、蝙蝠、鳥類等，而這些動物的行為服從萊維分布。

基于植物花授粉的一些特征，在提出算法之前應當遵循以下理想化規則[1]：

（1）異花授粉是通過蜜蜂或者鳥類來進行的，而這些異花授粉的‘媒介是進行萊維飛行來傳播花粉的，異花授粉可視為全局授粉的過程；

（2）自花授粉可看做一個局部授粉的過程；

（3）花恒常性可認為是授粉行為，涉及到2朵花的繁殖概率與相似度成比例；

（4）全局授粉和局部授粉由轉換概率p∈[0，1]控制，受物理位置鄰近性以及自然因素（風、雨、雪等）的影響，在局部授粉和全局授粉中p代表著重要的意義。

結果表明所有測試算例中CFPA求出值與理論值的接近程度均優于參考文獻給出的結果，唯一的不足是求解例1時，雖然給出的答案和3個解之中的1個完全一致，但是由30次運行結果來看，其余的2個解未能求出，該算法還需改進。

5 結束語

本文介紹了一種帶柯西變異的自適應花授粉算法，針對花授粉算法中異花授粉和同花授粉進行局部改進。在異花授粉的過程中，對步長進行自適應的設計，使其初期和后期都有良好的尋優表現；在自花授粉過程中，引入柯西變異進行隨機擾動，以增強種群的多樣性，避免陷入局部最優。最后選取了6個高維函數進行測試，證明其結果較好。選擇了5個工程設計中的非線性方程組求解問題，證明改進的算法性能較好，尤其是針對高維函數。花授粉算法還存在一些問題，有待完善。

參考文獻

[1] YANG Xinshe. Flower pollination algorithm for global optimization [J]. Unconventional computation and natural computation， 2012，7445： 240-249.

[2] YANG Xinshe. Firefly algorithms for multimodal optimization [M]//WATANABE O， ZEUGMANN T. Stochastic algorithms： Foundations and applications. SAGA 2009. Lecture Notes in Computer Science. Berlin： Springer-Verlag，2009，5792： 169-178.

[3] YANG Xinshe，DEB S. Cuckoo search via Levy flights[C]//Proc. of World Congress on Nature & Biologically Inspired Computing （NaBIC 2009）. India： IEEE，2009：210-214 .

[4] YANG Xinshe. A new metaheuristic bat-inspired algorithm[M]/ /GONZLEZ JR， PELTA D A， CRUZ C， et al. Nature Inspired Cooperative Strategies for Optimization （NICSO 2010）. Studies in Computational Intelligence.Berlin： Springer-Verlag，2010： 65-74.

[5] YANG Xinshe， KARAMANOGLU M， HE Xingshi. Multi-objective flower algorithm for optimization [J]. Procedia Computer Science， 2013， 18： 861-868.

[6] KAUR G， SINGH D， KAUR M. Robust and efficient ‘RGBbased fractal image compression： Flower pollination based optimization [J]. Proc. of International Journal of Computer Applications， 2013， 78（10）： 11-15.

[7] ABDEL-RAOUF O， ABDEL-BASET M， EL-HENAWY I. A novel hybrid flower pollination algorithm with chaotic harmony search for solving Sudoku Puzzles [J]. International Journal of Engineering Trends and Technology（IJETT）， 2014， 7（3）： 126-132.

[8] EL-HENAWY I， ISMAIL M. An improved chaotic flower pollination algorithm for solving large integer programming problems [J]. International Journal of Digital Content Technology and its Applications， 2014， 8（3）： 72.

[9] 肖輝輝， 萬常選， 段艷明，等. 基于模擬退火的花朵授粉優化算法[J]. 計算機應用， 2015， 35（4）：1062-1066，1070.

[10]崔麗群，張晨，鄭寶林，等. 基于折射原理的混合型花朵授粉算法[J/OL]. 計算機應用研究，2019，36（5）：1-7[2018-03-09]. HTTP：//WWW.AROCMAG.COM/ARTICLE/02-2019-05-003.HTML.

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

[12]張建科，王曉智，劉三陽，等. 求解非線性方程及方程組的粒子群算法[J]. 計算機工程與應用，2006（7）：56-58.

[13]薛西峰，邢志棟，孟紅云. 求解非線性方程組的信賴域算法[J]. 西北大學學報（自然科學版），2001，31（4）：289-291.

[14]趙華敏，陳開周. 解非線性方程組的神經網絡方法[J]. 電子學報，2002，30（4）：601-604.

[15]陽萬安，曾安平. 求解復雜非線性方程組的新方法[J]. 計算機工程與應用，2009，45（28）：41-42，47.