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

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

改進(jìn)的正弦余弦算法在函數(shù)優(yōu)化問題中的研究

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

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

正弦余弦算法(SCA)是2015年提出的一種新型的群智能算法。針對(duì)標(biāo)準(zhǔn)正弦余弦算法局部搜索能力差、精度低的缺點(diǎn)，提出改進(jìn)的正弦余弦算法(簡稱ISCA)。首先，引入動(dòng)態(tài)慣性權(quán)重平衡算法的局部與全局搜索能力；然后，為更進(jìn)一步加強(qiáng)迭代后期局部搜索能力，將參數(shù)r1由線性遞減函數(shù)變成了指數(shù)型遞減函數(shù)；最后，引入自適應(yīng)變異因子，增強(qiáng)種群的多樣性；最后，將改進(jìn)的SCA算法對(duì)10個(gè)經(jīng)典的單峰、多峰函數(shù)進(jìn)行測(cè)試，并同標(biāo)準(zhǔn)SCA算法、粒子群算法(PSO)、遺傳算法(GA)進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明：ISCA算法優(yōu)于其他幾種算法。

正弦余弦算法；動(dòng)態(tài)慣性權(quán)重；指數(shù)遞減參數(shù)；自適應(yīng)變異因子；函數(shù)優(yōu)化

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

雖然SCA算法具有較強(qiáng)的全局搜索能力，但局部搜索能力較差。本文提出的改進(jìn)的SCA算法是為了進(jìn)一步加強(qiáng)標(biāo)準(zhǔn)SCA算法的局部搜索能力，提高算法精度以及減少早熟、過學(xué)習(xí)的發(fā)生。通過引入動(dòng)態(tài)慣性權(quán)重，平衡了局部搜索和全局搜索的過程；在算法中引入自適應(yīng)變異因子，增加了種群的多樣性；又將參數(shù)r1變?yōu)橹笖?shù)遞減函數(shù)，增強(qiáng)了其后期的局部搜索能力。最后，將改進(jìn)的SCA算法在函數(shù)優(yōu)化問題上進(jìn)行了仿真實(shí)驗(yàn)。

1 標(biāo)準(zhǔn)的正弦余弦算法(SCA)

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

(1)

(2)

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

圖1表明了當(dāng)r1取不同值范圍時(shí)，解的搜索區(qū)域。

圖1 不同r1值對(duì)解搜索區(qū)域的影響

圖1只說明了一個(gè)二維模型，應(yīng)該注意的是這個(gè)模型可以擴(kuò)展到更高的維度。正弦余弦函數(shù)的循環(huán)模式允許一個(gè)解在其他解的周圍被重新復(fù)位，這能保證在兩個(gè)解之間的空間進(jìn)行搜索。對(duì)于搜索空間，解應(yīng)該能夠同時(shí)搜索到它們相關(guān)的目標(biāo)點(diǎn)之間的空間外側(cè)， 這是通過改變正弦余弦函數(shù)的范圍來實(shí)現(xiàn)的，如圖2所示。

圖2 在區(qū)間[-2,2]的正弦余弦函數(shù)Fig.2 Sine cosine function in interval[-2,2]

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

圖3 在當(dāng)前解和目標(biāo)點(diǎn)的內(nèi)部和外部區(qū)域

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

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

1) 對(duì)于一個(gè)問題，SCA提高了隨機(jī)解的質(zhì)量，與基于個(gè)體的算法相比，它本質(zhì)上得益于較強(qiáng)的搜索能力和避免局部最優(yōu)的能力。

2) 當(dāng)正弦和余弦函數(shù)的返回值大于1或小于-1時(shí)，將搜索不同的空間區(qū)域。

3) 當(dāng)正余弦值在[-1,1]時(shí)，期望的搜索空間區(qū)域被開發(fā)。

4) SCA算法從搜索到開發(fā)將進(jìn)行平滑的過度，使用恰當(dāng)?shù)恼嘞液瘮?shù)的范圍。

5) 最接近全局最優(yōu)的解作為目標(biāo)點(diǎn)被儲(chǔ)存在變量中，并且在優(yōu)化過程中不會(huì)丟失。

6) 由于該解能隨時(shí)更新當(dāng)前在它周圍得到最優(yōu)解的位置，在優(yōu)化過程中搜索空間有一個(gè)朝向最優(yōu)區(qū)域的趨勢(shì)。

7) 由于提出的算法將優(yōu)化問題視為一個(gè)黑箱子，它可以很容易地結(jié)合不同領(lǐng)域的問題。

圖4 遞減的正弦余弦模式

2 改進(jìn)的正弦余弦算法

2.1 動(dòng)態(tài)慣性權(quán)重

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

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

(3)

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

(4)

2.2 指數(shù)型遞減參數(shù)r1

為了進(jìn)一步加強(qiáng)迭代后期局部搜索能力，將參數(shù)r1由線性遞減函數(shù)變成了指數(shù)型遞減函數(shù)即：

(5)

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

2.3 自適應(yīng)變異

SCA優(yōu)化算法收斂快、結(jié)構(gòu)簡單，具有很強(qiáng)的通用性，但同時(shí)存在搜索精度低、容易早熟收斂、后期迭代效率低等缺點(diǎn)。本文借鑒了遺傳算法中的粒子變異的思想，將變異算子引入SCA算法中，即以一定的概率對(duì)粒子進(jìn)行初始化。變異操作擴(kuò)大了在迭代過程中不斷減少的搜索空間，使粒子可以跳出先前搜索到的最優(yōu)值位置，保持了種群的多樣性。其基本思想是粒子每次更新之后，以一定的概率重新初始化粒子，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分別是粒子位置坐標(biāo)的上界和下界；rand表示在(0,1)之間的隨機(jī)數(shù)；X(i,k)表示第i個(gè)粒子在第k維搜索空間中的位置。

2.4 改進(jìn)SCA算法流程

算法中每個(gè)粒子對(duì)應(yīng)一個(gè)解，尋優(yōu)過程如下：

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

步驟2 計(jì)算粒子的適應(yīng)度找出全局最優(yōu)。

步驟3 根據(jù)式(4)對(duì)粒子進(jìn)行更新。

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

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

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

步驟7 如果t

3 仿真試驗(yàn)和結(jié)論

3.1 測(cè)試函數(shù)及算法參數(shù)設(shè)置

為了檢驗(yàn)改進(jìn)的SCA算法的性能，本文選用10個(gè)典型的測(cè)試函數(shù)進(jìn)行數(shù)值實(shí)驗(yàn)。將改進(jìn)的SCA算法與標(biāo)準(zhǔn)SCA算法進(jìn)行比較，來測(cè)試改進(jìn)后的SCA算法的效果和可行性。表1列出了10個(gè)測(cè)試函數(shù)，其中f1～f7為單峰函數(shù)，f8～f10為多峰函數(shù)。算法參數(shù)設(shè)置的表達(dá)式、維數(shù)、解初始范圍、最優(yōu)解如表1。

3.2 仿真實(shí)驗(yàn)

種群規(guī)模固定為30，迭代次數(shù)固定為1 000，算法運(yùn)行30次。首先，對(duì)比 SCA 和 ISCA 的函數(shù)優(yōu)化效果。實(shí)驗(yàn)選取了3個(gè)經(jīng)典高維單峰函數(shù)和3個(gè)經(jīng)典高維多峰函數(shù)。二者的收斂效果見圖5；其次，選取表1的10個(gè)經(jīng)典函數(shù)，分別從均值(ave)、方差(std)評(píng)估了ISCA的收斂精度，并與同類研究參考文獻(xiàn)中標(biāo)準(zhǔn)的SCA算法、粒子群算法(PSO)、遺傳算法(GA)相比較,結(jié)果見表2。

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

從表2中可以看出：對(duì)于單峰函數(shù)和多峰函數(shù)，ISCA無論是在收斂能力還是穩(wěn)定性上，都優(yōu)于其它3種群算法，這得益于其較強(qiáng)的跳出局部最小值的能力。觀察表2中最后一行可以發(fā)現(xiàn)：ISCA算法中這10個(gè)測(cè)試函數(shù)的累積均值和累積標(biāo)準(zhǔn)差分別為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 測(cè)試函數(shù)的基本信息

表2 4種算法的平均值和標(biāo)準(zhǔn)差

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

4 結(jié)束語

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

[1] 胡中功,李靜.群智能算法的研究進(jìn)展[J].自動(dòng)化技術(shù)與應(yīng)用,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ìn)展[J].計(jì)算機(jī)應(yīng)用研究,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ìn)的粒子群算法[J].計(jì)算機(jī)工程與設(shè)計(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] 鄭偉,劉靜,曾建潮.人工蜂群算法及其在組合優(yōu)化中的應(yīng)用研究[J].太原科技大學(xué)學(xué)報(bào),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ìn)的人工蜂群算法在函數(shù)優(yōu)化問題中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,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ìn)果蠅優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用,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ìn)的果蠅優(yōu)化算法求解連續(xù)函數(shù)優(yōu)化問題[J].湖北汽車工業(yè)學(xué)院學(xué)報(bào),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]徐富強(qiáng),陶有田,呂洪升.一種改進(jìn)的果蠅優(yōu)化算法[J].蘇州大學(xué)學(xué)報(bào)(自然科學(xué)版),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.

(責(zé)任編輯 陳 艷)

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 基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61275120)

張校非(1991—)，男，碩士研究生，主要從事現(xiàn)代優(yōu)化算法、神經(jīng)網(wǎng)絡(luò)在組合優(yōu)化中的應(yīng)用研究，E-mail：598095564@qq.com。

張校非，白艷萍，郝巖，等.改進(jìn)的正弦余弦算法在函數(shù)優(yōu)化問題中的研究[J].重慶理工大學(xué)學(xué)報(bào)(自然科學(xué))，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