采用聚類的變異正余弦優(yōu)化算法研究

王華秋,熊維雙

(重慶理工大學(xué) 兩江人工智能學(xué)院， 重慶 401135)

0 引言

在現(xiàn)實生活中，存在很多群體，如蟻群、鯨魚群、狼群、鳥群等，他們都是非常智慧的群體。這些群居動物，單獨生存生命力弱，但群體生存會表現(xiàn)出強大的生命力與智慧，群體生物之間存在著各種各樣的信息交換方式，個體隨著群體信息進行調(diào)整，展現(xiàn)出強大的群體智能。

迄今為止，群體智能與解決優(yōu)化問題的融合已然成為一個非常熱門的研究話題[1]，將群體智能應(yīng)用到優(yōu)化問題中，目前對應(yīng)的算法還不少，如遺傳優(yōu)化算法(GA)[2]、粒子群優(yōu)化算法[3]、蜂群優(yōu)化算法[4]、果蠅優(yōu)化算法[5]等?？偟膩碚f，群體優(yōu)化技術(shù)都是從一組隨機解開始，然后對解進行評估，并采用對應(yīng)優(yōu)化算法規(guī)則對解進行更新，直到找到最優(yōu)質(zhì)的評估和解，這就是群體優(yōu)化算法的技術(shù)核心。然而，這些傳統(tǒng)的優(yōu)化算法通常計算時間較長，尋找的結(jié)果解也不夠優(yōu)質(zhì)。例如，傳統(tǒng)的粒子群算法結(jié)構(gòu)復(fù)雜，可調(diào)參數(shù)多，對于單峰問題表現(xiàn)出收斂過快而降低了解的質(zhì)量，對于多峰問題易得局部最優(yōu)，搜索不充分。

近年來，隨著對群體智能的深入研究，國內(nèi)外研究人員提出一些結(jié)構(gòu)簡單，易操作、高效的智能優(yōu)化算法。這些算法擁有更加智能的搜索規(guī)則，收斂速度快，收斂精度高，對于復(fù)雜優(yōu)化問題也具有優(yōu)越性。正余弦優(yōu)化算法(SCA)是2016年澳大利亞研究員Mirjalili[6]提出的，它是一種較為新型的、高效率的智能優(yōu)化算法。SCA具有結(jié)構(gòu)簡單、可調(diào)參數(shù)少、實現(xiàn)簡單、收斂快速等優(yōu)點，Mirjalili的仿真實驗驗證了正余弦算法的收斂精度與收斂速度相比同類型PSO、GA和BA更加優(yōu)秀。但是依然有陷入局部最優(yōu)的風(fēng)險和局部搜索不充分等不足，尤其是對于復(fù)合多峰類的函數(shù)。

針對上述不足，國內(nèi)外研究人員也提出了很多改進正余弦優(yōu)化算法的策略。如 Nenavath等[7]對SCA局部搜索能力進行改進，利用PSO算法的局部開發(fā)能力來彌補SCA局部搜索的短板。實驗仿真分析驗證了PSO改進后的正余弦優(yōu)化算法對單峰測試函數(shù)，具有更高效的局部探索能力，結(jié)合SCA全局搜索的優(yōu)勢，使PSO-SCA優(yōu)化算法性能得到整體提升。Gupta等[8]提出正余弦結(jié)合反向?qū)W習(xí)的M-SCA優(yōu)化算法，設(shè)計反向?qū)W習(xí)避免局部最優(yōu)，設(shè)計自適應(yīng)振幅調(diào)整因子擴大搜索空間，增加候選解的多樣性。Nenavath等[9]提出一種SCA-DE，采用差分算法策略優(yōu)化SCA避免局部最優(yōu)，提升算法跳出局部最優(yōu)的能力，仿真實驗驗證了改進后的SCA-DE比傳統(tǒng)的SCA或單純的DE的優(yōu)化效果要好，收斂速度與精度都有很大的提高。文獻[10]提出了融合貪婪選擇、交叉機制、反向?qū)W習(xí)策略的ISCA優(yōu)化算法，用來增加全局與局部搜索的力度，前期全局搜索廣，后期局部搜索快，提供一個精英解，為種群尋找優(yōu)質(zhì)解提供搜索方向，并在CEC2017(congress on evolutionary computation 2017)基準(zhǔn)函數(shù)上檢驗了ISCA算法的優(yōu)越性和魯棒性。

盡管現(xiàn)有研究在傳統(tǒng)SCA尋優(yōu)性能方面有所改進，到目前為止，從SCA提出到對SCA算法的改進，這方面的研究還是相對較少。SCA容易陷入局部最優(yōu)、收斂速度較慢等問題，依然缺乏有效的解決手段，尤其針對復(fù)雜優(yōu)化問題。本文提出KMeans聚類與柯西混沌變異的改進 KVSCA方法，KVSCA算法擴大了搜索范圍，加強了局部搜索能力，更有效地避免局部最優(yōu)，提高了算法收斂精度與收斂速度。本文采用拉丁超立方體抽樣方法(LHS)隨機初始化種群解，提高初始化種群解的多樣性。

結(jié)合柯西混沌變異與KMeans聚類算法，重點改進了局部搜索的收斂方式，避免局部最優(yōu)，加快收斂; 在算法中振幅調(diào)整因子進行自適應(yīng)更新，改進個體位置更新方式; 設(shè)計非線性的指數(shù)函數(shù)對振幅調(diào)整因子進行自適應(yīng)更新，平衡局部搜索和全局搜索。最后，將改進的KVSCA算法應(yīng)用到CEC2017基準(zhǔn)函數(shù)和工程測試優(yōu)化問題上，進行仿真實驗。驗證了改進后KVSCA算法的高魯棒性和優(yōu)越性。

1 正余弦算法

SCA是一種啟發(fā)式優(yōu)化算法，結(jié)構(gòu)簡單，易于實現(xiàn)，泛化能力強，可應(yīng)用于不同領(lǐng)域。在尋優(yōu)過程中，正余弦優(yōu)化算法利用隨機分布的解在搜索空間中快速震蕩地進行搜索更新。解的搜索隨著震蕩的收斂而收斂。具體的搜索方式為：首先對候選解進行隨機初始化，然后與正弦函數(shù)或余弦函數(shù)再結(jié)合隨機因子在候選解的每個維度上更新當(dāng)前解的值。位置更新方程為:

(1)

(2)

式中:r1取值范圍為[0,a];a為常數(shù);t為當(dāng)前迭代次數(shù);T為最大迭代次數(shù);參數(shù)r1表示搜索方向。r1>1，則往當(dāng)前解與最優(yōu)解之間的區(qū)域更新位置，有助于全局探索；r1≤1，則往當(dāng)前解與最優(yōu)解之外的區(qū)域更新位置，有助于局部探索。并且r1會隨著迭代次數(shù)t的增加而減小，平衡正余弦優(yōu)化算法的局部搜索和全局搜索，改善了傳統(tǒng)的SCA局部搜索不足的缺點。r2,r3,r4作為一個隨機因素組，r2參數(shù)定義了當(dāng)前解離最優(yōu)解的距離。 參數(shù)r3為隨機權(quán)值，r3>1，則加強候選解向精英解進行位置更新，更新跨度更大，r3≤1，則減弱候選解向精英解進行位置更新，更新跨度減小。r4參數(shù)調(diào)整正弦或余弦變化方式。

正弦和余弦搜索過程如圖1所示。正余弦值域范圍為考慮了隨機權(quán)重的正余弦函數(shù)，值域為[-2，2]。當(dāng)正弦函數(shù)和余弦函數(shù)取值范圍屬于(-1,1)之間時，候選解的搜索范圍在當(dāng)前解到最優(yōu)解的半徑范圍內(nèi)進行最優(yōu)解搜索；當(dāng)正弦函數(shù)和余弦函數(shù)值范圍在[-1,-2]和[1,2]范圍時，候選解在當(dāng)前解到最優(yōu)解的半徑范圍之外進行搜索最優(yōu)解。在實際優(yōu)化過程中，全局最優(yōu)解的位置被存儲，表現(xiàn)為一個可變的精英個體。候選解總是圍繞當(dāng)前精英個體并利用正余弦函數(shù)更新位置。

圖1 正弦和余弦搜索過程

2 改進正余弦算法

2.1 LHS方法初始化種群

文獻[11]研究分析出，種群初始化的好壞嚴(yán)重影響著優(yōu)化算法的初始性能與結(jié)果，太過單一的初始化易得局部最優(yōu)，缺少魯棒性。在基本 SCA 算法中，采用隨機的方法產(chǎn)生初始化種群，這種方法產(chǎn)生的初始化種群易導(dǎo)致產(chǎn)生的種群個體分布不均和出現(xiàn)個體重疊，導(dǎo)致易得局部最優(yōu)，降低了SCA算法的尋優(yōu)性能。本文提出采用LHS方法初始化種群，具備如下優(yōu)點：

能實現(xiàn)滿空間填充，產(chǎn)生的采樣點個體具有隨機性，并能較好地將其均勻分布在搜索空間中；穩(wěn)定性強，希望采樣點總均值可提供無偏估計，同時方差小。從LHS方法的特點看，若采用LHS方法初始化種群，既可以保證產(chǎn)生的初始化種群個體的隨機性，得到均勻分布、不重疊的初始化種群，從而保證了初始化種群的多樣性，提高了算法尋優(yōu)性能和減避免部最優(yōu)。

步驟1確定種群規(guī)模S；

步驟3生成S行h列的且每一列都為{1，2,…,s}的一個隨機全排列矩陣As*h；

步驟4劃分后的As*h矩陣的每一行就為一個子立方體，代表選取的一個種群個體，這樣得到的每個種群個體都不會重復(fù)，最后采集到分布均勻的種群個體。

2.2 自適應(yīng)的振幅調(diào)整因子

在SCA算法中，參數(shù)r1用于平衡全局探索和局部探索。當(dāng)r1>1時，候選解往當(dāng)前解與最優(yōu)解之外的區(qū)域更新位置，進行全局搜索。當(dāng)r1≤1時，候選解往當(dāng)前解與最優(yōu)解之內(nèi)的區(qū)域更新位置，進行局部搜索。全局搜索和局部開發(fā)的有效協(xié)調(diào)和自適應(yīng)轉(zhuǎn)換決定了SCA算法能否獲得更好的穩(wěn)定性和更高的尋優(yōu)精度。式(2)表明，r1屬于[0,a]，隨迭次數(shù)增加而減小的線性遞減函數(shù)。表明：較大r1使得迭代早期搜索步長更大，全局搜索能力更強，但調(diào)整因子遞減速率過快，全局搜索不充分，易陷入局部最優(yōu)；較小r1使得迭代晚期搜索步長更小，但遞減速率慢，算法無法快速收斂。振幅調(diào)整因子線性的遞減對于SCA算法的尋優(yōu)精度和收斂速度提升作用不大，算法性能提高不明顯。為此，KVSCA算法設(shè)計了一種基于指數(shù)函數(shù)的曲線自適應(yīng)振動調(diào)整因子的更新方法，定義為：

(3)

式中：k為調(diào)節(jié)系數(shù)。根據(jù)式(3)，r1的遞減速率隨迭代先慢后快，這表明前期的迭代次數(shù)比原始SCA算法更多，可以相對增強全局搜索能力，而削弱局部開發(fā)能力，這有助于在更大空間內(nèi)搜尋最優(yōu)解。而后期r1將加速遞減，加快算法收斂。與未改進的r1對比，如圖2所示。

由圖2和式(3)可看出，傳統(tǒng)SCA算法的振幅調(diào)整因子r1隨算法迭代次數(shù)的增加呈線性遞減，改進振幅調(diào)整因子r1隨算法迭代次數(shù)的增加而非線性遞減。這種方式在算法前期振幅調(diào)整因子r1以較小的速度減小，保證了較大的振幅，加快算法全局搜索，到算法迭代后期，振幅調(diào)整因子r1以較大的速度減小，使得振幅后期較小，使其能在最優(yōu)解附近進行精確搜索。均衡全局搜索與局部搜索，提高尋優(yōu)性能。

圖2 r1的變化曲線

2.3 變中心數(shù)的KMeans劃分

傳統(tǒng)的KMeans算法以歐式距離聚類度量標(biāo)準(zhǔn)，尋找初始聚類中心V=(v1,v2,…,vk)T向量的最優(yōu)分類，使評價指標(biāo)具有最小值。以誤差平方和的大小作為聚類好壞的評判標(biāo)準(zhǔn)，誤差平方和公式定義如下：

(4)

式中：ci為聚類后的簇；Mi為聚類的對象；p為簇中的平均值。

KMeans算法的核心思想是對一個數(shù)據(jù)對象按照歐式距離，將數(shù)據(jù)點到該聚類中心的平方和最小化。本文在傳統(tǒng)的優(yōu)化算法上增加KMeans聚類劃分，主要目的有：① 劃分后，利用不同簇種群個數(shù)的統(tǒng)計特征，使SCA優(yōu)化算法在不同簇搜索開發(fā)的能力有所不同；② 增強傳統(tǒng)SCA在局部收斂時的搜索能力。原理如下：

1) 根據(jù)SCA優(yōu)化算法的位置更新公式，即式(1)，當(dāng)r1>1時，隨著迭代次數(shù)的增加，候選解總是圍繞當(dāng)前精英個體并利用正余弦函數(shù)更新位置，所有種群粒子都會逐漸向著最優(yōu)去收斂。從整個收斂空間看，這樣做收斂速度較快，卻也很容易陷入局部最優(yōu)。本文采用KMeans聚類劃分平衡全局搜索速度與范圍。KMeans劃分后，不同的簇包含的種群粒子數(shù)目不同。隨著SCA算法迭代收斂，種群數(shù)目多的簇，存在最優(yōu)值的可能性越大，反之，可能性越小，然后對于每個簇利用公式(1)更新位置，種群多的收斂速度依然快，保證全局搜索速度，種群少的簇也會給與一定的開發(fā)，保證全局搜索范圍不會急速縮小。

2) 在SCA優(yōu)化算法的局部搜索時，當(dāng)r1≤1時，位置更新方向為當(dāng)前解與最優(yōu)解之外的區(qū)域，此時的當(dāng)前解與最優(yōu)解之外的搜索區(qū)域較廣。其中r1越小，這個區(qū)域范圍越大。對于多峰類的目標(biāo)優(yōu)化函數(shù)，收斂變得不穩(wěn)定，很容易在當(dāng)前解與最優(yōu)解之外的搜索區(qū)域找到最優(yōu)解，局部搜索變得非常不穩(wěn)定，容易陷入局部最優(yōu)。增加KMeans聚類劃分后，SCA在局部搜索時，當(dāng)前解與最優(yōu)解之外區(qū)域范圍減小，并且對于每個簇搜索是獨立的。在避免局部最優(yōu)的同時，使收斂變得更加穩(wěn)定，增強傳統(tǒng)SCA的局部搜索能力。

具體實現(xiàn)方法：由式(1)可知，傳統(tǒng)SCA算法在實際優(yōu)化過程中，全局最優(yōu)解的位置被存儲，表現(xiàn)為一個可變的精英個體。所有的種群粒子利用正余弦函數(shù)向著精英個體更新位置，可將種群粒子分為基本種群粒子和精英種群粒子來體現(xiàn)。在此基礎(chǔ)上，本文在KMeans聚類劃分后，將所有種群粒子重新分為3類：基本種群粒子x、精英種群粒子xb和最優(yōu)種群粒子xgb。基本種群粒子x為每個簇的所有種群粒子，精英種群粒子xb為簇內(nèi)被存儲的最優(yōu)位置，最優(yōu)種群粒子xgb為全局最優(yōu)解。KVSCA優(yōu)化算法提出精英種群粒子xb向最優(yōu)種群粒子xgb進行位置更新，同時基本種群粒子x進行柯西混沌擾動的策略。在KVSCA優(yōu)化算法進行尋優(yōu)時，KMeans聚類數(shù)同時發(fā)生變化，形成變中心數(shù)KMeans劃分。采用變中心數(shù)KMeans劃分相對于標(biāo)準(zhǔn)KMeans劃分的區(qū)別在于，變中心數(shù)變的是精英種群粒子xb的個數(shù)。其優(yōu)勢在于，隨著KMeans劃分中心數(shù)K值的增加，精英種群粒子xb個數(shù)也增加，進而向著最優(yōu)種群粒子xgb收斂的速度加快，加速整個優(yōu)化算法的收斂。另外，相對于單個最優(yōu)個體xgb的擾動機制，本文采取對所有基本種群粒子x進行擾動，可增加擾動開發(fā)范圍，最大限度降低KVSCA算法進入局部的風(fēng)險。同時，基本種群粒子x隨K值的增加而減少，使KVSCA算法進入局部搜索時加快收斂速度。保持基本種群粒子x個數(shù)與精英種群粒子xb個數(shù)的和等于初始的種群粒子數(shù)，以確保KVSCA算法優(yōu)化開銷不會增大。

2.4 基于自適應(yīng)慣性權(quán)重的位置跟新

由SCA算法的位置更新方式可知，新的個體位置x(t+1)通過將原個體位置x(t)向當(dāng)前最優(yōu)解xgb(t)移動而生成，該過程更有利于種群進行全局搜索，相對而言，局部搜索時易早熟收斂。因此，改進位置更新方式，也成為一個改進重點。

文獻[12]在分析了SCA算法的不足后引入慣性權(quán)重w，對粒子的速度更新公式進行改進，使得PSO算法能快速收斂于全局最優(yōu)解。受此改進算法的啟發(fā)，本文在傳統(tǒng)SCA位置更新方式上引入慣性權(quán)重w，以此避免早熟，改善優(yōu)化性能。得到改進的個體位置更新公式如下:

(5)

式中：w為慣性權(quán)重，r2為0到2π的隨機數(shù)；r3為0～2之間的隨機數(shù)；r4為(0,1)的隨機數(shù)，r4調(diào)節(jié)位置更新方式，r4<0.5正弦位置更新方式，r4≥0.5余弦位置更新方式。

根據(jù)文獻[13]仿真實驗表明，慣性權(quán)重較大時，主要進行全局搜索，慣性權(quán)重較小時，主要進行局部搜索，并且慣性權(quán)重隨著迭代次數(shù)的增加而減小。前期慣性權(quán)重大，進行全局探索；后期慣性權(quán)重小，進行局部探索。具體公式如式(5)：

(6)

式中：wmax為迭代過程中最大慣性權(quán)重，wmin為迭代過程中最小慣性權(quán)重。

在此基礎(chǔ)上，本文在KMeans聚類劃分后，種群粒子分為基本種群粒子x、精英種群粒子xb和最優(yōu)種群粒子xgb；提出了精英種群粒子xb向最優(yōu)粒子xgb進行位置更新的策略，保證算法的快速收斂與收斂精度。對基本種群粒子x進行柯西擾動和混沌擾動，保證算法的全局搜索，減緩進入局部最優(yōu)。提升算法的搜索性能，擴大搜索范圍。兩者同時作用，保證KVSCA優(yōu)化算法快速、穩(wěn)定地收斂。

基于KMeans改進后的位置更新方式為：

(7)

式中：r4為(0,1)的隨機數(shù)；r4調(diào)節(jié)位置更新方式；r4<0.5正弦位置更新方式；r4≥0.5余弦位置更新方式。

2.5 基于KMeans劃分后的變異擾動

由新的位置更新式(5)可知，個體在進行搜索時，當(dāng)前的精英最優(yōu)個體xgb具有引領(lǐng)作用。盡管該方式可以有效發(fā)揮精英個體的導(dǎo)向作用，但在處理多峰函數(shù)優(yōu)化時，此時忽略了最優(yōu)個體的多樣性，易導(dǎo)致局部最優(yōu)。

目前，將精英個體擾動機制應(yīng)用到智能優(yōu)化算法的改進有很多，可以有效避免局部最優(yōu)，具有更快的收斂速度、更高的收斂精度，魯棒性也更強。然而，改進也有一些不足，如在某些多峰函數(shù)中搜索精度不高，算法優(yōu)化性能不穩(wěn)定，如文獻[14-15]。單純的精英個體的擾動，缺乏多樣性的基本個體群，尤其在局部搜索時，過于依賴精英個體擾動帶來的避免局部最優(yōu)的擾動效果，較容易陷入局部最優(yōu)，最優(yōu)值的獲取極其不穩(wěn)定。如果單純采用較多的精英個體擾動，產(chǎn)生精英個體群，提升局部搜索開發(fā)能力，精英個體群的自適應(yīng)選取不易，且收斂速度慢。算法優(yōu)化性能提升不大。所以，本文采用變中心數(shù)KMeans對種群劃分的方式，增加算法在局部搜索與全局搜索的開發(fā)力度，提升全局和局部搜索能力。K值增加，加快算法的收斂速度，實現(xiàn)更加穩(wěn)定和快速的收斂。

將初始化后的總?cè)海肒Means進行劃分成k類，每一類中選取最優(yōu)的精英個體，形成精英個體群。然后對精英個體xb采取式(7)的位置更新方式，提升算法的收斂速度。分別對基本個體x和最優(yōu)個體xgb采用柯西變異或混沌變異，增加種群多樣性，提高算法探索開發(fā)能力，避免局部最優(yōu)。

基于柯西變異的個體更新方式為：

xnew=X+cauch*yX

(8)

式中：參數(shù)cauchy表示服從柯西分布的柯西算子；xnew為基本個體或者最優(yōu)個體經(jīng)過柯西變異的個體；X為基本個體或最優(yōu)個體。

基于混沌變異的個體更新方式為：

xnew=xmin+φ(xmax-xmin)

(9)

式中：φ為Logistic混沌值，定義為：

φ(t+1)=c*φ(t)(1-φ(t))

(10)

式中：c為混沌參數(shù)，c=4。

綜上，將基本個體和最優(yōu)個體的變異擾動方式定義為：

(11)

式中：r5為(0，1)內(nèi)的隨機值。

2.6 改進后的算法流程

算法尋優(yōu)流程如下:

步驟1初始化參數(shù)，設(shè)種群規(guī)模為Sn，設(shè)最大迭代次數(shù)為Tmax，設(shè)聚類個數(shù)K初始化為1。 全局最優(yōu)gbest初始化為INF，精英個體群(gbest1,gbest2,…,gbestk,gbestk+1)T初始化為(INF1,INF2,…,INFk,INFk+1)T。

步驟2利用拉丁超立方體方法(LHS)初始化種群。

步驟3對均勻分布的種群進行KMeans聚類，聚類數(shù)為k。

步驟4計算所有種群粒子的適應(yīng)度，找出每個簇的簇內(nèi)最優(yōu)，產(chǎn)生新精英個體群(b1,b2,…,bk)T。更新并存儲迭代過程中每個簇的簇內(nèi)最大解Xmaxi=(xmax1,xmax2,…,xmaxk)T與每個簇的簇內(nèi)最小解Xmini=(xmin1,xmin2,…,xmink)T。

步驟5精英個體群中選取最大值為此次迭代的全局最優(yōu)gb。

步驟6剩余的所有基本種群粒子進行柯西混沌擾動,將Xmaxi、Xmini用于混沌擾動。

步驟7KMeans劃分后精英個體群按式(6)進行位置更新。

步驟8對每個種群個體的所有維度進行檢查，檢查是否超出邊界。若是，則把上界值替換給維度大于上界的值，把下界值替換給維度小于下界的值。反之，不作處理。

步驟9對當(dāng)前精英個體群(b1,b2,…,bk)T中的bi種群粒子依次判斷，判斷bi的適應(yīng)度值是否優(yōu)于(gbest1,gbest2,…,gbestk,gbestk+1)T中的gbesti的適應(yīng)度值，若是，更新gbesti=bi。繼續(xù)判斷gb是否大于gbest。若是，更新gbest=gb。

步驟10對全局最優(yōu)gb進行柯西擾動或混沌擾動。

步驟11將所有簇重新組合到一起，迭代次數(shù)t加1；返回步驟3，當(dāng)t為，聚類數(shù)k=k+1。

步驟12當(dāng)?shù)螖?shù)t≥Tmax時，迭代結(jié)束，尋優(yōu)完成，輸出全局最優(yōu)gbest。

算法流程如圖3所示。

圖3 KVSCA算法流程框圖

2.7 算法復(fù)雜度分析

時間復(fù)雜度分析，令KVSCA算法的種群規(guī)模為N，最大迭代數(shù)為Tmax，個體維度為d。則LHS種群隨機初始化的時間復(fù)雜度為O(N*d)。利用KMeans進行聚類需要時間復(fù)雜度為O(N*k*m)，k為聚類個數(shù)，m為迭代個數(shù)。一般k,m均可認(rèn)為是常量，所以時間可以簡化為：O(N)，即線性的。遍歷所有精英種群個體，以及每個精英個體的所有維度，計算精英個體適應(yīng)度，則計算適應(yīng)度的時間復(fù)雜度為O(N1*d*Tmax)。N1精英個體的個數(shù)，N1屬于[1,k]。每次迭代中，需要對基本個體群進行擾動變異，該過程的時間復(fù)雜度為O(k*N*d*Tmax)。綜上，KVSCA算法的總體時間復(fù)雜度為O(k*N*d*Tmax)。該時間復(fù)雜度比基本SCA算法時間復(fù)雜度多一個k的數(shù)量級，k是常數(shù)，且會隨著迭代次數(shù)增加減小到1，表明KVSCA算法增加計算代價并不大。

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

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

為了檢驗KVSCA算法的性能，本文選用23個典型的測試函數(shù)和1個工程測試問題進行實驗仿真，測試KVSCA算法的效果和可行性。表1列出了 23個測試函數(shù)，其中 f1～f7為單模態(tài)基準(zhǔn)函數(shù)，f8～f13為多模態(tài)基準(zhǔn)函數(shù)函數(shù)，f14～f18為復(fù)合型基準(zhǔn)函數(shù)函數(shù)。統(tǒng)計的基準(zhǔn)測試函數(shù)的名稱、維度、區(qū)域和理論最小值如表1。

表1 測試函數(shù)

續(xù)表(表1)

實際工程測試問題為齒輪設(shè)計問題。齒輪數(shù)設(shè)計問題是一種離散問題，所有變量都必須為整數(shù)。齒輪數(shù)設(shè)計問題中，涉及(x1,x2,x3,x4)4個決策變量，它們代表了一列4個齒輪的齒數(shù)。這個問題的目標(biāo)是找到一個最佳的齒數(shù)，以盡量減少齒輪比。本文采用四舍五入的方式處理離散參數(shù)為整數(shù)，齒輪數(shù)設(shè)計優(yōu)化問題目標(biāo)函數(shù)為：

(12)

式中：約束條件為12≤xi≤60，xi∈Z+，?i=1,2,3,4。

3.2 測試函數(shù)性能對比

1) 種群規(guī)模N設(shè)為40、最大迭代數(shù)Tmax設(shè)為400、振幅調(diào)整因子a設(shè)為2、初始慣性權(quán)重wmax設(shè)為0.9、wmin設(shè)為0.4，實驗運行次數(shù)為20。對比算法選擇如下：基本正余弦算法SCA[6]、柯西混沌變異改進的正余弦算法優(yōu)IWCCSCA[13]。

表2中(a)～(c)統(tǒng)計了30次實驗中不同優(yōu)化函數(shù)優(yōu)化基準(zhǔn)函數(shù)的均值、標(biāo)準(zhǔn)方差和最小值表現(xiàn)，同步觀測算法尋優(yōu)精度和穩(wěn)定性。表格中標(biāo)準(zhǔn)方差體現(xiàn)了優(yōu)化算法的穩(wěn)定性，方差越小，算法越穩(wěn)定。表格中均值和最小值體現(xiàn)的是優(yōu)化算法的收斂精度。每個目標(biāo)函數(shù)收斂精度可以從表1的理想最小值屬性查看，實際適應(yīng)度值越接近理論最小值則收斂精度越高。

表2 優(yōu)化結(jié)果的平均值、標(biāo)準(zhǔn)差和最小值

從統(tǒng)計結(jié)果分析：對于所有函數(shù)，改進后的KVSCA算法與IWCCSCA算法比傳統(tǒng)的SCA算法的尋優(yōu)精度和穩(wěn)定性都好。除了在一些復(fù)合型目標(biāo)函數(shù)中IWCCSCA算法的表現(xiàn)與傳統(tǒng)的SCA差不多，如f21-f23。IWCCSCA算法采用拉丁超立方體抽樣方法、柯西混沌變異、非線性的指數(shù)函數(shù)對振幅調(diào)整因子，性能提升較為有限，尤其是局部收斂不足，如在優(yōu)化復(fù)合型目標(biāo)函數(shù)中，明顯表現(xiàn)出收斂精度較差，局部收斂極不穩(wěn)定。

(b)標(biāo)準(zhǔn)差

續(xù)表[表2(b)]

(c)最小值

觀察統(tǒng)計表格可知，在表格中的KVSCA算法，標(biāo)準(zhǔn)方差、均值和最小值的表現(xiàn)結(jié)果都是最優(yōu)的。本文所采用的KVSCA算法，在結(jié)合IWCCSCA改進優(yōu)點的同時，利用變中心數(shù)的KMeans劃分方式擴大局部搜索范圍，加大局部搜索力度。從而對SCA算法的開發(fā)空間、種群多樣性、收斂速度及擾動的多樣性等方面進行了優(yōu)化，得到更高的收斂精度和更快的收斂速度。因此，KVSCA算法在綜合性能提升方面是所有算法中最好的，得到的理論最優(yōu)解也是最多的。證明了變中心數(shù)的KMeans劃分方式的有效性。

收斂性分析：圖4為最大迭代為400時算法的收斂曲線。圖中點線為SCA，虛線為IWCCSCA，實線為KVSCA?？梢钥闯?，3種算法的尋優(yōu)曲線都有下墜趨勢，說明都在迭代地向理論最優(yōu)解位置靠近。從圖 4(a)～(c)可以看出:對于單峰函數(shù)，KVSCA不僅收斂精度高，收斂速度最快，而且都可以找到理論最小值。從圖4(d)～(f)可以看出：對于多峰函數(shù)，KVSCA與IWCCSCA兩種算法的收斂精度近似，收斂精度遠(yuǎn)高于SCA，但KVSCA收斂速度明顯快得多。從圖4(g)～(i)可以看出:對于復(fù)合型函數(shù)，KVSCA同樣可以找到理論最小值，收斂速度也是最快，基本沒有陷入局部最優(yōu)。綜合24個基準(zhǔn)函數(shù)的測試結(jié)果，KVSCA算法在處理單峰、多峰函數(shù)和復(fù)合函數(shù)都具有很好尋優(yōu)效率及穩(wěn)定性。

圖4 收斂曲線

3.3 實際工程測試問題分析

表3統(tǒng)計了30次實驗中齒輪設(shè)計問題的優(yōu)化均值、標(biāo)準(zhǔn)方差和最小值，很明顯可以看出表現(xiàn)最好的是KVSCA的優(yōu)化效果，收斂的精度、穩(wěn)定性都是最好的。

表3 齒輪設(shè)計問題優(yōu)化結(jié)果

KVSCA優(yōu)化在實際應(yīng)用中也同樣優(yōu)秀，相比于其他2種算法。表4為最終優(yōu)化結(jié)果，KVSCA的優(yōu)化結(jié)果分別為：x1=43，x2=16，x3=19，x4=49。

表4 齒輪設(shè)計問題優(yōu)化結(jié)果

收斂性分析：圖5為最大迭代為400時算法的收斂曲線。F24為齒輪設(shè)計問題的目標(biāo)優(yōu)化函數(shù)。從圖中看出，3種算法都收斂下降。KVSCA下降最快、最低，同樣顯示了KVSCA算法的魯棒性高，收斂快，精度高。

圖5 齒輪設(shè)計問題收斂曲線

4 結(jié)論

1) 在 SCA 算法的基礎(chǔ)上進行改進,通過引入超拉丁立方體LHS方法初始化種群，均勻分布初始化種群，提高初始種群多樣性。

2) 引入自適應(yīng)慣性權(quán)重、引入非線性遞減振幅因子r1、設(shè)計結(jié)合柯西變異和混沌變異避免局部最優(yōu)，提高算法開發(fā)能力。利用KMeans聚類算法對種群進行聚類，擴大搜索范圍，既增強了局部搜索能力，又增加收斂速度。

3) 對比傳統(tǒng)智能算法和IWCCSCA，本文的KVSCA算法具有更快的收斂速度和更高的收斂精度，以及更好的適應(yīng)性和魯棒性。尤其是在復(fù)合型函數(shù)的表現(xiàn)上，更加凸顯了KVSCA擺脫局部最優(yōu)，快速收斂的優(yōu)勢。

4) 未來的研究工作可以考慮進一步提高啟發(fā)式算法的效率，減少迭代次數(shù)，同時引入并行化的思路提升尋優(yōu)效率，滿足大數(shù)據(jù)處理需求。