自調(diào)整的捕魚策略優(yōu)化算法*

李景洋，王 勇，李春雷

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

自調(diào)整的捕魚策略優(yōu)化算法*

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

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

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

捕魚策略優(yōu)化算法(FSOA)；ADFSOA；時變搜索半徑；調(diào)整因子

1 引言

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

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

2 基本FSOA介紹

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

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

說明：(1)算法設(shè)有公告板。公告板是記錄最優(yōu)漁夫個體狀態(tài)的地方。每個漁夫?qū)⒆约寒?dāng)前狀態(tài)與公告板中記錄進(jìn)行比較,若優(yōu)于公告板中的記錄,則用自身狀態(tài)更新公告板中的記錄,否則公告板的記錄不變；(2)算法設(shè)有在同一點(diǎn)處可進(jìn)行收縮搜索次數(shù)的最大閾值。若某漁夫在某點(diǎn)處進(jìn)行收縮搜索次數(shù)達(dá)到了最大閾值,但其狀態(tài)仍未發(fā)生改變,該漁夫則要在打魚作業(yè)區(qū)中重新隨機(jī)選點(diǎn)。

3 改進(jìn)的捕魚策略優(yōu)化算法

3.1 搜索行為描述

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

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

(1)

(2)

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

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

(3)

(4)

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

3.2 算法實(shí)施步驟：

算法ADFSOA

輸出：最優(yōu)漁夫所在位置及所在位置魚的濃度。

步驟1初始化：在可行域內(nèi)隨機(jī)生成M個漁夫，記錄群體最優(yōu)漁夫所在的位置，評價漁夫所在位置魚的濃度，t←1

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

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

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

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

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

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

步驟3.4記錄當(dāng)前最優(yōu)漁夫所在的位置。

步驟4t←t+1，判斷算法是否達(dá)到終止條件，若是則轉(zhuǎn)至步驟5，否則轉(zhuǎn)步驟2。

步驟5輸出最優(yōu)漁夫所在位置及所在位置魚的濃度，運(yùn)行結(jié)束。

4 實(shí)驗(yàn)仿真與結(jié)果分析

4.1 測試函數(shù)

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

(1)Schwefel’sproblem2.12:

該函數(shù)在點(diǎn)(0,0,…,0)處取得全局極小值0。

(2)Ackley’s function:

該函數(shù)在點(diǎn)(0,0,…,0)處取得全局極小值0。

(3) Rastrigin’s function:

該函數(shù)在點(diǎn)(0,0,…,0)處取得全局極小值0。

(4) Griewank’s function:

該函數(shù)在點(diǎn)(0,0,…,0)處取得全局極小值0。

(5) Sphere function:

該函數(shù)在點(diǎn)(0,0,…,0)處取得全局極小值0。

(6) Step function:

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

4.2 數(shù)值實(shí)驗(yàn)仿真

本次實(shí)驗(yàn)使用的計(jì)算機(jī)為AMD Phenom(tm)ⅡP820、2 GB內(nèi)存的PC機(jī)；編程軟件為Matlab2010a。

為了避免隨機(jī)性對實(shí)驗(yàn)結(jié)果的影響，每一種算法針對每個函數(shù)均獨(dú)立運(yùn)行50次，并求最優(yōu)值、最差值、平均值、標(biāo)準(zhǔn)差、平均迭代次數(shù)以及50次優(yōu)化測試中找到精確解的次數(shù)。本文得到的實(shí)驗(yàn)結(jié)果如表1所示。

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

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

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

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

實(shí)驗(yàn)結(jié)果分析：(1)從表1中的“找到精確解的

Table 1 Experimental results

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

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

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

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

5 結(jié)束語

針對基本FSOA在處理復(fù)雜優(yōu)化問題中容易陷入局部極值、求解高維的復(fù)雜優(yōu)化問題時優(yōu)化性能不太好的不足，提出了一種自調(diào)整的捕魚策略優(yōu)化算法。實(shí)驗(yàn)結(jié)果表明，本文提出的算法能有效地克服基本FSOA難以克服的易陷入局部最優(yōu)的問題；而對于高維的復(fù)雜優(yōu)化問題，本文算法的優(yōu)化性能良好，其優(yōu)化性能均比基本FSOA、現(xiàn)有的改進(jìn)FSOA以及標(biāo)準(zhǔn)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)

附中文參考文獻(xiàn)：

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

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

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

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

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

王勇(1963-),男,廣西南寧人，博士，教授，研究方向?yàn)橛?jì)算智能和數(shù)據(jù)挖掘。E-mail:wangygxnn@sina.com

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

李春雷(1987-),男,河南信陽人，碩士，研究方向?yàn)橹悄苡?jì)算、電力系統(tǒng)保護(hù)與控制。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

國家自然科學(xué)基金資助項(xiàng)目(61074185);廣西自然科學(xué)基金資助項(xiàng)目(0832084);廣西高等學(xué)?？蒲许?xiàng)目(201202ZD032)

TP18

：A

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

李景洋(1989-),女,河南漯河人，碩士，研究方向?yàn)橛?jì)算智能。E-mail:miaolianjingyang@126.com

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

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