自調整的捕魚策略優化算法*

李景洋，王 勇，李春雷

(1.廣西民族大學信息科學與工程學院，廣西 南寧 530006；2 南寧市環境保護監測站，廣西 南寧 530012；3.南寧供電局，廣西 南寧 530031)

自調整的捕魚策略優化算法*

李景洋1,2，王 勇1，李春雷3

(1.廣西民族大學信息科學與工程學院，廣西 南寧 530006；2 南寧市環境保護監測站，廣西 南寧 530012；3.南寧供電局，廣西 南寧 530031)

針對基本捕魚策略優化算法(FSOA)在優化過程中存在易陷入局部最優、求解高維的復雜優化問題時優化性能不好的不足，對基本捕魚策略優化算法(FSOA)進行了改進，提出了自調整的捕魚策略優化算法(ADFSOA)：算法采用時變的搜索半徑，每個漁夫可根據自己所處的狀態自我調整搜索策略。通過與基本FSOA、RFSOA和標準PSO算法的數值實驗對比, 表明了所提算法的優化性能具有顯著的優勢，可用于求解高維的復雜優化問題。

捕魚策略優化算法(FSOA)；ADFSOA；時變搜索半徑；調整因子

1 引言

20世紀70年代，遺傳算法[1]的提出開啟了求解全局優化問題的新紀元。在過去的30年里，群智能算法得到了越來越多的關注。許多受生物學啟發的算法被陸續提出來[2～11]。大自然是提出新的元啟發式算法的重要靈感來源，仿生算法是受自然啟發的元啟發式算法的一個重要策略。如：蟻群算法[2]源于對自然界螞蟻覓食行為的模擬；粒子群算法[3]源自對鳥群為了尋找食物和保護群體所特有的行為的模擬；人工魚群算法[4]是受魚群的覓食行為、追尾行為和聚群行為啟發而提出的。而相比鳥、螞蟻、魚以及其他昆蟲，人類具有更高的智能。文獻[12]通過對現實世界中漁夫的捕魚行為的模擬,提出了一種采用捕魚策略的優化方法FSOA(Fishing Strategy Optimization Algorithm)。該算法具有理論方法簡單、設置參數少、易于編碼實現的優點。但是，同時也存在一些不足,主要表現為：(1)算法搜索缺乏隨機性,降低了算法的搜索效率；(2)針對高維的復雜優化問題，其優化能力比較差，易陷入局部極值。針對基本FSOA存在的不足，文獻[13～16]從不同的角度對基本FSOA進行了改進。文獻[13]提出采用正交變換確定探測點的改進方法，文獻[14]提出將FSOA與PSO相結合的優化方法，文獻[15,16]提出采用隨機動態選擇探測點的改進方法。盡管文獻[13～16]所提出的改進方法在一定程度上提高了算法的搜索效率，但面對高維的復雜優化問題仍顯得力不從心，仍無法用來解決高維的復雜優化問題，未能從根本上提高算法的優化能力。

針對以上仍存在的不足，本文提出了一種自調整的捕魚策略優化算法ADFSOA(ADjustive Fishing Strategy Optimization Algorithm)：不使用收縮搜索策略，而是采用自我調整搜索策略，搜索者根據自己所處的狀態來調整搜索方法。

2 基本FSOA介紹

在基本FSOA中，漁夫采用移動搜索與收縮搜索相結合的搜索策略,以“方體”格式確定探測點。具體方法如下：

其中,α(0<α<1)稱為收縮因子。然后按前面的方法來確定Ω(Xi(t+1))中是否有比Xi(t+1)更優的點。按這樣的方法展開搜索,稱之為收縮搜索。

說明：(1)算法設有公告板。公告板是記錄最優漁夫個體狀態的地方。每個漁夫將自己當前狀態與公告板中記錄進行比較,若優于公告板中的記錄,則用自身狀態更新公告板中的記錄,否則公告板的記錄不變；(2)算法設有在同一點處可進行收縮搜索次數的最大閾值。若某漁夫在某點處進行收縮搜索次數達到了最大閾值,但其狀態仍未發生改變,該漁夫則要在打魚作業區中重新隨機選點。

3 改進的捕魚策略優化算法

3.1 搜索行為描述

人類是自然界智能最高的行為主體，人類可依據周圍環境的變化不斷地調整自身狀態和行為策略，以更好地適應環境；人類有向他人學習、以克服自身存在之不足的天性。漁夫出海打魚，都希望能在較短的時間內找到水域中魚濃度最大的區域或位置，以期能捕獲更多的魚。漁夫根據周圍魚濃度的變化和群體狀況來不斷地調整自己的位置和行動策略。據此，本文提出的算法采用如下策略：(1)漁夫采用動態搜索方式。前期采取較大的搜索半徑，以期能盡快搜索到魚濃度比較高的區域。隨著搜索時間的增加，漁夫越來越有可能找到或靠近魚密度比較高的位置或區域，因而要逐漸縮小搜索范圍(縮小搜索半徑)，以期找到魚密度最高的位置。(2)以自我調整機制代替收縮機制。漁夫在當前位置搜索失敗后(即未搜索到魚濃度高于當前自己所在的位置的魚濃度)，漁夫則根據自己當前在群體中的優劣順序來調整其下一步的行為，調整自己的行動策略，以期盡快找到更好的捕魚區域或位置。

(1)搜索半徑是時變的。在搜索過程中，漁夫的搜索半徑l是時間t的函數，其變化規律按如公式(1)所示：

(1)

(2)

Case1若si(t)=1，即漁夫i處于當前群體最優位置，則下一步將按公式(1)和公式(2)，在B(Xi(t),l(t+1))中繼續進行移動搜索，并記Xi(t+1)=Xi(t)。

Case2若si(t)≠1，漁夫i則根據公式(3)來確定其自我調整因子AFi(t)(Adjustive Factor)，并根據公式(4)來確定其調整策略：

(3)

(4)

其中,r、α均為(0,1)中均勻分布的隨機數,k為{1,…,n}中的一個隨機整數。也就是說,漁夫依據自我調整因子AFi(t)來確定其下一步的捕魚策略：處于魚濃度比較高的位置的漁夫傾向于以換維的方式向最優漁夫靠近，即其j維換到最優漁夫的第k維，而處于適應度比較差的位置的漁夫傾向于向最優漁夫移動。

3.2 算法實施步驟：

算法ADFSOA

輸出：最優漁夫所在位置及所在位置魚的濃度。

步驟1初始化：在可行域內隨機生成M個漁夫，記錄群體最優漁夫所在的位置，評價漁夫所在位置魚的濃度，t←1

步驟2漁夫按公式(1)計算搜索半徑。

步驟3對漁夫i(i=1,…,M)執行以下操作：

步驟3.1按公式(2)在搜索域內選取N個探測點。

步驟3.3將所有漁夫按適應度從優到劣進行排序，以si(t)表示漁夫i的序號，若si(t)=1，則執行步驟3.3.1，否則執行步驟3.3.2;

步驟3.3.1漁夫位置不變,即Xi(t+1)= Xi(t)，轉步驟3.1;

步驟3.3.2根據公式(3)計算調整因子AFi(t)，根據公式(4)來確定自己的行動策略，改變位置。

步驟3.4記錄當前最優漁夫所在的位置。

步驟4t←t+1，判斷算法是否達到終止條件，若是則轉至步驟5，否則轉步驟2。

步驟5輸出最優漁夫所在位置及所在位置魚的濃度，運行結束。

4 實驗仿真與結果分析

4.1 測試函數

為了驗證本文提出的ADFSOA算法的有效性，我們將ADFSOA算法與FSOA、PSO、RFSOA[16]進行數值實驗對比。本文選擇以下六個基準測試函數進行數值實驗測試分析：

(1)Schwefel’sproblem2.12:

該函數在點(0,0,…,0)處取得全局極小值0。

(2)Ackley’s function:

該函數在點(0,0,…,0)處取得全局極小值0。

(3) Rastrigin’s function:

該函數在點(0,0,…,0)處取得全局極小值0。

(4) Griewank’s function:

該函數在點(0,0,…,0)處取得全局極小值0。

(5) Sphere function:

該函數在點(0,0,…,0)處取得全局極小值0。

(6) Step function:

該函數在-0.5≤xi≤0.5處取得全局極小值0。

4.2 數值實驗仿真

本次實驗使用的計算機為AMD Phenom(tm)ⅡP820、2 GB內存的PC機；編程軟件為Matlab2010a。

為了避免隨機性對實驗結果的影響，每一種算法針對每個函數均獨立運行50次，并求最優值、最差值、平均值、標準差、平均迭代次數以及50次優化測試中找到精確解的次數。本文得到的實驗結果如表1所示。

為了能更明顯地對比出各種算法的優化性能，我們給出了這六個測試函數的收斂曲線仿真圖。如圖1～圖6所示。

Figure 1 Comparison of convergence curve f1(X)圖1 函數f1(X)收斂曲線對比圖

Figure 2 Comparison of convergence curve f2(X)圖2 函數f2(X)收斂曲線對比圖

Figure 3 Comparison of convergence curve f3(X)圖3 函數f3(X)收斂曲線對比圖

實驗結果分析：(1)從表1中的“找到精確解的

Table 1 Experimental results

Figure 4 Comparison of convergence curve f4(X)圖4 函數f4(X)收斂曲線對比圖

Figure 5 Comparison of convergence curve f5(X)圖5 函數f5(X)收斂曲線對比圖

Figure 6 Comparison of convergence curve f6(X)圖6 函數f6(X)收斂曲線對比圖

次數”指標上看，在這50次的優化測試中，ADFSOA能以較大的概率找到函數f3、f4和f6的全局最優點，基本的PSO、 RFSOA和FSOA均沒有找到這些函數的全局最優點。(2)從表1中的“最優值”、“最差值”、“平均值”、“標準差”、“平均迭代次數”這幾項評價指標上看，ADFSOA的優化性能明顯優于基本FSOA、RFSOA和標準PSO。(3)從收斂曲線對比圖1～圖6中可以看出，ADFSOA的收斂速度明顯比基本FSOA、RFSOA和標準PSO都快。

5 結束語

針對基本FSOA在處理復雜優化問題中容易陷入局部極值、求解高維的復雜優化問題時優化性能不太好的不足，提出了一種自調整的捕魚策略優化算法。實驗結果表明，本文提出的算法能有效地克服基本FSOA難以克服的易陷入局部最優的問題；而對于高維的復雜優化問題，本文算法的優化性能良好，其優化性能均比基本FSOA、現有的改進FSOA以及標準PSO算法好。

[1] Holland J H.Adaptation in nature and artificial systems[M]. CA,MA:MIT Press, 1992.

[2] Dorigo M, Birattari M, Stüzle T. Ant colony optimization:Artificial ants as a computational intelligence technique[J]. IEEE Computing Intelligence Magazine, 2006, 1(4):28-39.

[3] Kennedy J, Eberhart R C. Particle swarm optimization[C]∥Proc of the IEEE International Conference on Neural Networks, 1995:1942-1948.

[4] Li Xiao-lei,Shao Zhi-jing,Qian Ji-xin.An optimizing method based on autonomous animals:Fish-swarm algorithm[J]. Systems Engineering Theory and Practice, 2002, 22(11):32-38.

[5] Jiao L C,Wang L. A novel genetic algorithm based on immunity[J].IEEE Transactions on System, Man and Cybernetic,2000,30(5):552-561.

[6] Oftadeh R, Mahjoob M J, Sharitatpanahi M. A novel meta-heuristic optimization algorithm inspired by group hunting of animals:Hunting search[J].Computer and Mathematics with Applications, 2010,60:2087-2098.

[7] Dai C,Chen W,Song Y,et al. Seeker optimization algorithm：A novel stochastic search algorithm for global numerical optimization[J].Journal of Systems Engineering and Electronics, 2010,21(2):300-311.

[8] Yang X-S. Firefly algorithm, Lévy flights and global optimization[M]∥Reaserch and developments in intelligent systemsXXVI. London:Springer-Verlag, 2010:209-218.

[9] Yang X-S, Deb S. Cuckoo search via Lévy flights[C]∥Proc of the World Congress on Nature & Biologically Inspired Computing (NaBIC 2009),2009:210-214.

[10] Yang X-S. A new metaheuristic bat-inspired algorithm[C]∥Proc of Nature Inspired Cooperative Strategies for Optimization NISCO, 2010:65-74.

[11] Passino K M. Biomimicry of bacterial foraging for distributed optimization[M].NJ:Princeton:University Press, 2001.

[12] Chen Jian-rong, Wang Yong. Optimization approach on using fishing stragety[J].Computer Engineering and Applications,2009，45(9):53-56.(in Chinese)

[13] Wang Yong, He De-niu, Guan Yi-jun, et al. An improving FSOA optimization by using orthogonal transform[C]∥Proc of the International Conference on Electronic Commerce,Web Application, and Communication, 2011:63-69.

[14] Pang Xing, Wang Yong. Optimization approach combined PSO with fishing strategy[J].Computer Engineering and Applications，2011，47(8)：36-40.(in Chinese)

[15] Chen Shi-liang, Wang Yong, Chen Jian-rong. Improved FSOA by using random detection strategy[J]. Computer Engineering and Applications,2011,47(26):49-52.(in Chinese)

[16] He De-niu,Wang Yong, Guan Yi-jun. Improved FSOA by using random detecting[J]. Computer Engineering and Applications 2011, 47(36):44-46.(in Chinese)

附中文參考文獻：

[12] 陳建榮,王勇.采用捕魚策略的優化方法[J]. 計算機工程與應用,2009, 45(9):53-56.

[14] 龐興,王勇.PSO與捕魚策略相結合的優化方法[J]. 計算機工程與應用, 2011, 47(8):36-40.

[15] 陳士亮, 王勇, 陳建榮.一種采用隨機探測策略的改進FSOA[J]. 計算機工程與應用, 2011, 47(26):49-52.

[16] 何德牛,王勇,管憶軍.采用隨機探測的改進FSOA[J]. 計算機工程與應用, 2011, 47(36):44-46.

LIJing-yang,born in 1989,MS,her research interest includes computational intelligence.

王勇(1963-),男,廣西南寧人，博士，教授，研究方向為計算智能和數據挖掘。E-mail:wangygxnn@sina.com

WANGYong,born in 1963,PhD,professor,his research interests include computational intelligence, and data mining.

李春雷(1987-),男,河南信陽人，碩士，研究方向為智能計算、電力系統保護與控制。E-mail:lichunlei0218@126.com

LIChun-lei,born in 1987,MS,his research interests include computational intelligence, power system protection and control.

Adjustivefishingstrategyoptimizationalgorithm

LI Jing-yang1,2,WANG Yong1,LI Chun-lei3

(1.College of Information Science and Engineering,Guangxi University for Nationalities,Nanning 530006;2.Environmental Protection Monitoring Station of Nanning，Nanning 530012;3.Nanning Power Supply Bureaus,Nanning 530031,China)

In order to overcome the shortcomings that basic FSOA is easily trapped in local optimum and unable to solve the high-dimensional complex optimization problems,an improved FSOA,named ADjustive Fishing Strategy Optimization Algorithm (ADFSOA),is proposed.In the algorithm,every fisherman (searcher) uses a time-varying search-radius and can adjust his searching strategy according to his own state.Numerical experiments show that,compared with basic FSOA,RFSOA and standard PSO,the proposed algorithm is much superior to other algorithms and can be used to solve the complex high-dimensional optimization problems.

FSOA;ADFSOA;time-varying search radius;adjustive factor

1007-130X(2014)05-0923-06

2012-10-22;

：2013-01-21

國家自然科學基金資助項目(61074185);廣西自然科學基金資助項目(0832084);廣西高等學校科研項目(201202ZD032)

TP18

：A

10.3969/j.issn.1007-130X.2014.05.023

李景洋(1989-),女,河南漯河人，碩士，研究方向為計算智能。E-mail:miaolianjingyang@126.com

通信地址：530006 廣西南寧市廣西民族大學信息科學與工程學院

Address:College of Information Science and Engineering,Guangxi University for Nationalities,Nanning 530006，Guangxi,P.R.China