改進的正弦余弦算法在函數優化問題中的研究

張校非，白艷萍，郝 巖，王永杰

(中北大學 理學院,太原 030051)

改進的正弦余弦算法在函數優化問題中的研究

張校非，白艷萍，郝 巖，王永杰

(中北大學 理學院,太原 030051)

正弦余弦算法(SCA)是2015年提出的一種新型的群智能算法。針對標準正弦余弦算法局部搜索能力差、精度低的缺點，提出改進的正弦余弦算法(簡稱ISCA)。首先，引入動態慣性權重平衡算法的局部與全局搜索能力；然后，為更進一步加強迭代后期局部搜索能力，將參數r1由線性遞減函數變成了指數型遞減函數；最后，引入自適應變異因子，增強種群的多樣性；最后，將改進的SCA算法對10個經典的單峰、多峰函數進行測試，并同標準SCA算法、粒子群算法(PSO)、遺傳算法(GA)進行比較。實驗結果表明：ISCA算法優于其他幾種算法。

正弦余弦算法；動態慣性權重；指數遞減參數；自適應變異因子；函數優化

目前，用群智能算法解決優化問題是一個十分活躍的研究領域[1]，而用于解決優化問題的群智能算法有很多，如遺傳算法(GA)[2]、粒子群算法(PSO)[3-4]、人工蜂群算法(ACO)[5-7]、果蠅算法(FOA)[8-11]等。正弦余弦算法(SCA)[12]是一種新型的元啟發試算法，它是建立在正弦余弦函數上的自組織和群智能基礎上的數值優化計算方法。最先由Seyedali和 Mirjalili提出了正余弦概念的自組織模型。通常來說，群優化技術開始于一組隨機解，這個隨機解通過一個目標函數反復被評估，并且通過一組規則來提高，這是優化技術的核心。因為基于群的優化技術隨機尋找優化問題的最優解，所以不能保證再一次運行中找到最優解。然而，通過足夠的隨機解和優化迭代，能夠大大增加找到全局最優解的可能性。

雖然SCA算法具有較強的全局搜索能力，但局部搜索能力較差。本文提出的改進的SCA算法是為了進一步加強標準SCA算法的局部搜索能力，提高算法精度以及減少早熟、過學習的發生。通過引入動態慣性權重，平衡了局部搜索和全局搜索的過程；在算法中引入自適應變異因子，增加了種群的多樣性；又將參數r1變為指數遞減函數，增強了其后期的局部搜索能力。最后，將改進的SCA算法在函數優化問題上進行了仿真實驗。

1 標準的正弦余弦算法(SCA)

標準的SCA算法是由澳大利亞學者Seyedali和 Mirjalili于2015年提出。算法始于一組隨機解，通過搜索和開發階段不斷逼近全局最優解。首先，初始化解的位置，算法更新如式(1)所示：

(1)

(2)

如式(1)所示，在SCA算法中有4個主要參數，分別是r1,r2,r3和r4。參數r1決定了下一個位置的區域(或移動方向)，它既可以是當前解和目標解之間的區域，也可以是二者之外的區域；參數r2定義了當前解應該朝目標解或遠離目標解的距離；參數r3為目標解隨機地賦予一個權值，目的是加強(r3>1)或削弱(r3<1)所定義的距離對目標解的影響；參數r4使式(1)中的正余弦的組成部分均等轉換。

圖1表明了當r1取不同值范圍時，解的搜索區域。

圖1 不同r1值對解搜索區域的影響

圖1只說明了一個二維模型，應該注意的是這個模型可以擴展到更高的維度。正弦余弦函數的循環模式允許一個解在其他解的周圍被重新復位，這能保證在兩個解之間的空間進行搜索。對于搜索空間，解應該能夠同時搜索到它們相關的目標點之間的空間外側， 這是通過改變正弦余弦函數的范圍來實現的，如圖2所示。

圖2 在區間[-2,2]的正弦余弦函數Fig.2 Sine cosine function in interval[-2,2]

一個范圍在[-2,2]的正弦余弦函數的概念模型如圖3所示。表明無論怎樣改變正弦和余弦函數的范圍，在這個解和其它解之間都需要一個解在空間內部和外部更新它的位置。在等式(1)中的內、外部隨機位置通過定義一個范圍在[0,2π]的隨機數來實現。因此，這種機制保證了搜索空間的搜索和開發。

圖3 在當前解和目標點的內部和外部區域

圖4顯示了在式(1)迭代過程中如何降低正、余弦函數的范圍。從圖3和4中可以看出：當正余弦函數的區間范圍在(1,2]和[-2,-1)上時，SCA算法搜索搜尋空間；當區間范圍在[-1,1]上時，算法開發搜索空間。

經過以上操作，SCA算法能在理論上得到優化問題的全局最優解，主要有以下原因：

1) 對于一個問題，SCA提高了隨機解的質量，與基于個體的算法相比，它本質上得益于較強的搜索能力和避免局部最優的能力。

2) 當正弦和余弦函數的返回值大于1或小于-1時，將搜索不同的空間區域。

3) 當正余弦值在[-1,1]時，期望的搜索空間區域被開發。

4) SCA算法從搜索到開發將進行平滑的過度，使用恰當的正余弦函數的范圍。

5) 最接近全局最優的解作為目標點被儲存在變量中，并且在優化過程中不會丟失。

6) 由于該解能隨時更新當前在它周圍得到最優解的位置，在優化過程中搜索空間有一個朝向最優區域的趨勢。

7) 由于提出的算法將優化問題視為一個黑箱子，它可以很容易地結合不同領域的問題。

圖4 遞減的正弦余弦模式

2 改進的正弦余弦算法

2.1 動態慣性權重

經研究發現：慣性權重體現的是粒子位置多大程度上繼承先前的位置。如果保持慣性權重不變，粒子在搜索的后期非常容易發生震蕩。為了更好地平衡算法的全局搜索與局部搜索能力，本文在式(1)的基礎上提出了線性型遞減的慣性權重即：

w(t)=w0×(1.1-t/T)

(3)

式中，w0=1,w(t)為第t次迭代的慣性權重。隨著迭代的進行，慣性權重從1.1遞減到0.1，迭代初期保持了較強的搜索能力，而到了后期較小的慣性權重加強了局部開發，使解的搜索更精確。更新后的式(1)如式(4)所示：

(4)

2.2 指數型遞減參數r1

為了進一步加強迭代后期局部搜索能力，將參數r1由線性遞減函數變成了指數型遞減函數即：

(5)

一般來說，r1start=0.9、rend=0.4時，算法性能最好。

2.3 自適應變異

SCA優化算法收斂快、結構簡單，具有很強的通用性，但同時存在搜索精度低、容易早熟收斂、后期迭代效率低等缺點。本文借鑒了遺傳算法中的粒子變異的思想，將變異算子引入SCA算法中，即以一定的概率對粒子進行初始化。變異操作擴大了在迭代過程中不斷減少的搜索空間，使粒子可以跳出先前搜索到的最優值位置，保持了種群的多樣性。其基本思想是粒子每次更新之后，以一定的概率重新初始化粒子，Matlab代碼如下：

if rand>0.5

k=ceil(2*rand);

ifk== 1

X(i,k) =(20-1)*rand+1;

else

X(i,k)=(Xmax-Xmin)*rand+Xmin;

end

end

其中，Xmax、Xmin分別是粒子位置坐標的上界和下界；rand表示在(0,1)之間的隨機數；X(i,k)表示第i個粒子在第k維搜索空間中的位置。

2.4 改進SCA算法流程

算法中每個粒子對應一個解，尋優過程如下：

步驟1 初始化解集xij，i=1,2,…,N,j=1,2…,D,其中N為粒子的數量，D為粒子維數。

步驟2 計算粒子的適應度找出全局最優。

步驟3 根據式(4)對粒子進行更新。

步驟4 以一定的概率重新初始化粒子；

步驟5 檢查粒子的范圍是否超出邊界。若是，則把上界的值賦給大于上界的值，把下界的值賦給小于下界的值。反之，不作處理。

步驟6 判斷當前粒子的適應度是否優于之前種群的全局最優解。若是，將當前的粒子的適應度值替換為全局最優解，反之，則返回步驟3；

步驟7 如果t

3 仿真試驗和結論

3.1 測試函數及算法參數設置

為了檢驗改進的SCA算法的性能，本文選用10個典型的測試函數進行數值實驗。將改進的SCA算法與標準SCA算法進行比較，來測試改進后的SCA算法的效果和可行性。表1列出了10個測試函數，其中f1～f7為單峰函數，f8～f10為多峰函數。算法參數設置的表達式、維數、解初始范圍、最優解如表1。

3.2 仿真實驗

種群規模固定為30，迭代次數固定為1 000，算法運行30次。首先，對比 SCA 和 ISCA 的函數優化效果。實驗選取了3個經典高維單峰函數和3個經典高維多峰函數。二者的收斂效果見圖5；其次，選取表1的10個經典函數，分別從均值(ave)、方差(std)評估了ISCA的收斂精度，并與同類研究參考文獻中標準的SCA算法、粒子群算法(PSO)、遺傳算法(GA)相比較,結果見表2。

從圖5(a)～(c)可以看出：對于單峰函數，ISCA在收斂精度和收斂速度上都遠優于SCA。從圖5(d)～(f)可以看出：對于某些多峰函數，兩種算法的收斂精度近似，但ISCA收斂速度明顯快得多。而對于另外一些多峰函數,ISCA的收斂精度和速度均有著明顯的優勢。

從表2中可以看出：對于單峰函數和多峰函數，ISCA無論是在收斂能力還是穩定性上，都優于其它3種群算法，這得益于其較強的跳出局部最小值的能力。觀察表2中最后一行可以發現：ISCA算法中這10個測試函數的累積均值和累積標準差分別為2.1×10-4和9.875×10-5，而其他3種算法分別為9.51×10-3和1.05×10-3、7.88×10-1和1.56、5.19和3.995，說明該算法具有廣泛的適用性。

表1 測試函數的基本信息

表2 4種算法的平均值和標準差

圖5 函數 f1～f3、f8～f10在SCA和ISCA算法的收斂趨勢比較

4 結束語

本文在原有SCA算法的基礎上對其進行了的改進。通過引入動態慣性權重、改變參數r1的函數表達式、引入自適應變異因子等方式，使算法在尋優過程中不僅保持了較強的全局搜索能力，而且加強了其局部搜索能力，且豐富了種群的多樣性。同其它的群智能算法相比，ISCA算法具有更好的收斂速度及精度，且適應性、穩定性更強。然而，該算法也有一些不足，比如在某些多峰函數中搜索精度不高，這些方面有待今后重點研究。

[1] 胡中功,李靜.群智能算法的研究進展[J].自動化技術與應用,2008,27(2):13-15.

HU Zhonggong,LI Jing.Research progress of swarm intelligence algorithms[J].Automation techtechnology and Application,2008,27(2):13-15.

[2] 馬永杰,云文霞.遺傳算法研究進展[J].計算機應用研究,2012,29( 4):1201-1206.

MA Yongjie,YUN Wenxia.Research progress of genetic algorithm[J].Computer applicationr research,2012,29(4):1201-1206.

[3] KENNEDY J.Particle swarm optimization[M].New York:Springer,2011.

[4] 梁軍,程燦.改進的粒子群算法[J].計算機工程與設計,2008,29(11):2893-2896.

LIANG Jun,CHENG Can.Improved particle swarm optimization algorithm[J].Computer engengineering and design,2008,29(11)：2893-2896.

[5] KARABOGA D.An idea based on honey bee swarm for numerical optimization[R].Technical report-tr06,Erciyes university,engineering faculty,computer engineering department,2005.

[6] 鄭偉,劉靜,曾建潮.人工蜂群算法及其在組合優化中的應用研究[J].太原科技大學學報,2012,31(6):467-471.

ZHENG Wei,LIU Jing,ZENG.Jianchao.Research on artificial bee colony algorithm and its appapplaication in combinatorial optimization[J].Journal of Taiyuan University of Science and TecTechnology,2010,31(6):467-471.

[7] 王慧穎,劉建軍,王全洲.改進的人工蜂群算法在函數優化問題中的應用[J].計算機工程與應用,2012,48(19):36-39.

WANG Huiying，LIU Jianjun,WANG Quanzhou.Application of improved artificial bee colony algoralgorithm in function optimization[J].Computer engineering and ApplApplication,2010,31(6):467-471.

[8] PAN W T.A new fruit fly optimization algorithm:taking the financial distress model as an example[J].Knowledge-Based Systems,2012,26:69-74.

[9] 段艷明,肖輝輝.求解TSP問題的改進果蠅優化算法[J].計算機工程與應用,2016,52(6):144-149.

DUAN Yanming,XIAO Huihui.Improved fruit fly optimization algorithm for solving TSP proproblem[J].Computer engineering and Applications,2016,52(6):144-149.

[10]楊立君,付雅琴,殷旅江,等.一種改進的果蠅優化算法求解連續函數優化問題[J].湖北汽車工業學院學報,2016,30(1):71-74.

YANG Lijun,FU yanqin,YIN Lvjiang,et al.An improved optimization algorithm for the the optimization of fruit fly optimization algorithm for continuous function optimoptimization[J].Journal of Hubei automobile and automobile industry collecollege,2016,30(1):71-74.[11]徐富強,陶有田,呂洪升.一種改進的果蠅優化算法[J].蘇州大學學報(自然科學版),2014,29(1):16-23.

Xu Fuqiang,Tao Youtian,LV Hongsheng.An improved fruit fly optimization algorithm[J].JourJournal of Soochow University(NATURAL SCIENCE EDITION),20142014,29(1):16-23.[12]MIRJALILI S.SCA:A Sine Cosine Algorithm for solving optimization problems[J].Knowledge-Based Systems,2016,96:120-133.

(責任編輯 陳 艷)

Research of Improved Sine Cosine Algorithm in Function Optimization

ZHANG Xiao-fei, BAI Yan-ping, HAO Yan, WANG Yong-jie

(School of Science, North University of China, Taiyuan 030051, China)

The sine cosine algorithm (SCA) is a new kind of swarm intelligence algorithm which was proposed in 2015. In view of the poor local search capability and low precision of the standard sine cosine algorithm, an improved sine cosine algorithm (ISCA) was proposed. Firstly, we introduced dynamic inertia weight and balance the algorithm of local and global search ability; and the, we further strengthened the late iterative local search ability, and made parameters R1 turn from linear decreasing function into the exponential decreasing function; thirdly, we introduced self-adaptive mutation factor to enhance the diversity of the population. Finally, the improved SCA algorithm was tested on 10 classical single peak and multimodal functions, and compared it with standard SCA algorithm, particle swarm optimization (PSO) and genetic algorithm (GA). Experimental results show that the ISCA algorithm is better than other algorithms.

sine cosine algorithm; dynamic inertia weight; exponential decline parameter; adaptive mutation factor; function optimization

2016-10-12 基金項目：國家自然科學基金資助項目(61275120)

張校非(1991—)，男，碩士研究生，主要從事現代優化算法、神經網絡在組合優化中的應用研究，E-mail：598095564@qq.com。

張校非，白艷萍，郝巖，等.改進的正弦余弦算法在函數優化問題中的研究[J].重慶理工大學學報(自然科學)，2017(2):146-152.

format：ZHANG Xiao-fei, BAI Yan-ping, HAO Yan, et al.Research of Improved Sine Cosine Algorithm in Function Optimization[J].Journal of Chongqing University of Technology(Natural Science)，2017(2):146-152.

10.3969/j.issn.1674-8425(z).2017.02.024

TP301

A

1674-8425(2017)02-0146-07