基于交叉因子和模擬退火的群搜索優(yōu)化算法

楊文璐，寧玉富，2

（1.山東師范大學(xué) 管理科學(xué)與工程學(xué)院，山東 濟(jì)南250014；2.德州學(xué)院不確定系統(tǒng)實(shí)驗(yàn)室，山東德州253023）

0 引 言

群集智能算法是一些啟發(fā)于群居性生物的覓食、筑巢等行為而形成的優(yōu)化算法，正越來越受到人們的重視，吸引了大量國內(nèi)外學(xué)者的學(xué)習(xí)與研究。與遺傳算法和蟻群算法相類似，群搜索優(yōu)化 （group search optimizer，GSO）算法也是一種基于群集智能的演化計(jì)算技術(shù)。該算法是由He和Wu在2006年根據(jù)群居動(dòng)物如鳥、魚、獅子的覓食行為而提出的全局優(yōu)化算法［1，2］。研究和實(shí)踐表明，GSO在多維空間函數(shù)尋優(yōu)和動(dòng)態(tài)目標(biāo)尋優(yōu)等方面有著收斂速度快、非劣解質(zhì)量高及魯棒性好等優(yōu)點(diǎn)，所以被廣泛應(yīng)用在函數(shù)優(yōu)化、醫(yī)學(xué)及電力系統(tǒng)研究等工程設(shè)計(jì)中［3，4］。但是，與此同時(shí)GSO算法也存在早熟收斂、搜索精度不高、后期迭代效率不高，以及在后期運(yùn)算中容易陷入局部極優(yōu)點(diǎn)等缺點(diǎn)［4］。針對(duì)其在應(yīng)用中存在的以上問題，本文在原有GSO算法的基礎(chǔ)上進(jìn)行了改進(jìn)，提出了一種基于交叉因子和模擬退火的群搜索優(yōu)化 （integrated cross－factor and metropolis rule group search optimizer，CMGSO）算法。CMGSO 算法不僅可以通過增加粒子的多樣性來提高搜索的精確度及迭代效率，而且可以充分利用群集智能的優(yōu)良特性來跳出局部最優(yōu)的限制，同時(shí)加快了原算法的收斂速度，并提高了解決高維函數(shù)全局尋優(yōu)問題的優(yōu)化效率。

1 CMGSO算法

1.1 GSO算法

在最優(yōu)化問題中，未知最優(yōu)解被隨機(jī)分布于解集合中的一個(gè)未知點(diǎn)所標(biāo)識(shí)，則在GSO算法中，群體的任一個(gè)體都可以被假設(shè)為在解集合中尋找到的最優(yōu)解所在的那個(gè)點(diǎn)。因此GSO算法基于PS模型，并在此基礎(chǔ)上使用了游蕩者策略和動(dòng)物視覺搜索機(jī)制。在動(dòng)物覓食的策略中，主要有：①發(fā)現(xiàn)食物；②追隨發(fā)現(xiàn)者，一同分享事物；③個(gè)別游蕩尋找食物。該算法根據(jù)動(dòng)物覓食策略將群成員分為發(fā)現(xiàn)者（producer）、加入者 （scrounger）和游蕩者 （ranger）3種，并利用生物學(xué)的視覺搜索原理對(duì)食物進(jìn)行搜索，其中所有成員都有初始化的位置與角度。在算法開始后的迭代計(jì)算過程中，都將會(huì)對(duì)所有個(gè)體的適應(yīng)值進(jìn)行計(jì)算比較，并從中搜索出擁有最佳適應(yīng)值的個(gè)體設(shè)置為原始發(fā)現(xiàn)者，之后原始發(fā)現(xiàn)者會(huì)在當(dāng)前位置上對(duì)周圍一切可行解區(qū)域進(jìn)行尋優(yōu)搜索，尋找是否存在比當(dāng)前位置更好的位置，如果發(fā)現(xiàn)更好位置便向新位置移動(dòng)，否則保持原位置不變；而群體中的其它成員中80% 作為Scrounger按搜索公式跟隨Producer進(jìn)行搜索，其余的20%作為Ranger按搜索方程在覓食區(qū)域內(nèi)進(jìn)行隨機(jī)地游弋［5］。在迭代過程中發(fā)現(xiàn)者始終保持最優(yōu)位置，加入者則向發(fā)現(xiàn)者靠攏，游蕩者起到了加大搜索范圍的作用，每個(gè)個(gè)體都可以在3種角色中切換，直至滿足結(jié)束條件時(shí)，算法結(jié)束。

每次迭代中Producer（Xp）的搜索過程如下：

步驟1 Producer（Xp）從度角0開始進(jìn)行搜索，并按搜索式 （1）在前方尋找一個(gè)點(diǎn)，同樣分別按搜索式 （2）和 （3）在左方和右方再各自搜索一個(gè)點(diǎn)

其中，r1∈R1是均值為0、方差為1的一個(gè)正態(tài)分布隨機(jī)數(shù)；r2∈Rn－1為 ［0，1］間的均勻分布隨機(jī)數(shù)表示搜索方向。

步驟2 對(duì)所有位置的適應(yīng)值進(jìn)行比較計(jì)算后，若新位置適應(yīng)值優(yōu)于老位置適應(yīng)值，則此時(shí)Producer便主動(dòng)跳至新位置；反之，Producer便保持不動(dòng)，并按角度調(diào)整式（4）進(jìn)行搜索方向變換，以進(jìn)入到下面的迭代搜尋中

式中：αmax——最大的搜索角度。

步驟3 在算法的迭代中，使用者設(shè)定哨兵 “n”，用于重置搜索過程。當(dāng)Producer經(jīng)過多次迭代計(jì)算直到n次迭代，仍未搜索更優(yōu)解，則它將會(huì)按照公式 （5）把角度重新轉(zhuǎn)回到0度

同時(shí)，群體中的Scrounger跟隨Producer并加入到對(duì)更優(yōu)解的搜索過程中，如式 （6）中所示

Ranger用于避免算法陷入到局部最優(yōu)解的情況，所以分布于整個(gè)群體的內(nèi)部，且以隨機(jī)步長(zhǎng)來進(jìn)行獨(dú)立搜索，這種隨機(jī)走動(dòng)策略是極為有效地隨機(jī)資源分布尋找方法。假設(shè)第m次迭代中的第i個(gè)個(gè)體為Ranger，則它將按照角度搜索式 （7）、步長(zhǎng)搜索式 （8）和位置搜索式 （9）進(jìn)行迭代計(jì)算

據(jù)此，群搜索優(yōu)化算法中的發(fā)現(xiàn)者、加入者和游蕩者這3種角色，分別按照上文中提到的各自的迭代公式來進(jìn)行搜索，從而使其尋找到最優(yōu)的食物來源［6］。

1.2 交叉因子算法

我們?cè)跇?biāo)準(zhǔn)GSO算法的基礎(chǔ)上借鑒了遺傳算法中的組合交叉思想［7］，通過采用交叉因子產(chǎn)生出代表新解集的種群來替換原有種群。該過程將導(dǎo)致像自然進(jìn)化一樣的后代種群比前代更加適應(yīng)環(huán)境，從而加快搜索到問題的全局最優(yōu)解。

在CMGSO算法中，根據(jù)精英保留策略在每次迭代過程中選取Scrounger中適應(yīng)度值較高的一半群成員直接進(jìn)入下一代，同時(shí)用適應(yīng)度好的前一半群成員，與后一半群成員兩兩之間隨機(jī)通過位置和搜索角度進(jìn)行交叉，產(chǎn)生子代，再和父代作比較，并通過利用Metropolis準(zhǔn)則作為判定誰為新的群成員進(jìn)入下一次迭代的標(biāo)準(zhǔn)，得到新的群體，這樣通過交叉操作既可以增加群成員多樣性，跳出局部最優(yōu)，同時(shí)還可以加快算法的收斂速度。交叉操作公式如下

其中，x是D 維的位置向量；fCi（x）和fPi（x）兩個(gè)函數(shù)分別指明的是孩子成員還是父母成員的位置；p是D維均勻分布的隨機(jī)數(shù)向量，p的每個(gè)分量都在 ［0，1］取值

1.3 模擬退火算法

模擬退火算法是根據(jù)固體退火原理提出的，它是一種基于Metropolis準(zhǔn)則的通用隨機(jī)優(yōu)化算法。該算法基于物理中固體從較高初始溫度出發(fā)，隨著溫度的不斷下降，固體內(nèi)部能力發(fā)生相應(yīng)變化這一特質(zhì)，并結(jié)合概率的突跳特性使其在解空間中可以隨機(jī)對(duì)目標(biāo)函數(shù)的全局最優(yōu)解進(jìn)行尋找，利用這一特點(diǎn)可以有效避免陷入局部最優(yōu)解的問題［8］。冷卻進(jìn)度表 （cooling schedule）是用來控制退火過程這一機(jī)制的。在冷卻進(jìn)度表中主要包括一下幾個(gè)參數(shù)，固體溫度的初始值t、衰減因子Δt、迭代次數(shù)L及停止條件S［9］。由Metropolis準(zhǔn)則可知，當(dāng)固體受到擾動(dòng)時(shí)固體狀態(tài)發(fā)生改變，狀態(tài)通過固體的內(nèi)能來表示，固體內(nèi)能Ei小于Ej時(shí)，Ej＝Ei；反之當(dāng)Ei大于Ej時(shí)，則根據(jù)固體處于該狀態(tài)時(shí)的概率P來進(jìn)行判斷［10－11］，概率P的公式如下

式中：ΔE為其改變量；K 為Boltzmann常數(shù)［12－13］。

1.4 CMGSO算法

在CMGSO算法中對(duì)于由交叉操作更新所得到的新加入者Xik＋1來說，如何確定其能否成為替代原有個(gè)體，加入到本次迭代中，主要通過Metropolis準(zhǔn)則的優(yōu)值增量Δf＝f（）－f）計(jì)算來作為判定標(biāo)準(zhǔn)。上式中的f（x）為所要滿足的目標(biāo)函數(shù)。將由交叉操作得到的的位置和搜索角度代入目標(biāo)函數(shù)中來計(jì)算，如果Δf＜0，則替換原有的成員，進(jìn)行下一步的計(jì)算，否則通過Metropolis準(zhǔn)則中的概率exp（－Δf／MaxIter）來判定是否用替換原有成員進(jìn)入第k次迭代，即公式 （16）。這樣保存了較好的移動(dòng)方向以便預(yù)測(cè)到更好的移動(dòng)位置的同時(shí)又能達(dá)到概率性跳出局部最優(yōu)值的目的

式中：rand—— ［0，1］間的隨機(jī)數(shù)，MaxIter——最大迭代次數(shù)。

對(duì)于群體中的Ranger來說，在第k次的迭代中，對(duì)于新產(chǎn)生的，如果f（）－f（）＞0，則不選擇更新，即，否則，進(jìn)行更新。

在SGSO的基礎(chǔ)上通過引入交叉因子和模擬退火算法的思想改進(jìn)了SGSO算法，提高了該算法的優(yōu)化效率，其算法描述如下：

（1）選定GSO種群規(guī)模S；

（2）初始化每個(gè)群成員的位置和角度；

（3）對(duì)每個(gè)成員計(jì)算其適應(yīng)度值；

（4）比較各個(gè)群成員的適應(yīng)度值，記錄其自身最優(yōu)值Xbest和群體最優(yōu)成員Producer；

（5）根據(jù)公式 （1）（2）（3）和公式 （4）改變粒子的位置和搜索角度；

（6）執(zhí)行輪盤賭選擇和本文2.2中提到的交叉操作，生成新一代種群；

（7）將更新得到的運(yùn)用本文2.3中提到的模擬退火算法選擇是否對(duì)其進(jìn)行保留；

（8）檢查是否滿足GSO算法終止條件，若否，轉(zhuǎn)至第（4）步，繼續(xù)；若是，則求出最優(yōu)解。

2 CMGSO算法分析及性能測(cè)試

2.1 測(cè)試函數(shù)

本文在這里主要選取了4中較常用的測(cè)試函數(shù)，它們分別為Sphere函數(shù)、Rosenbrock函數(shù)、Griewank函數(shù)和Rastrign函數(shù)，其中前兩種函數(shù)常被用于某算法對(duì)于單模態(tài)優(yōu)化能力的測(cè)試，而后兩種函數(shù)則常被用于某算法對(duì)于多模態(tài)函數(shù)優(yōu)化能力的測(cè)試。這4個(gè)測(cè)試函數(shù)見表1。

表1 4個(gè)常用測(cè)試函數(shù)表達(dá)式

2.2 性能測(cè)試及結(jié)果分析

本節(jié)中擬用4個(gè)常用的測(cè)試函數(shù)對(duì)CMGSO的全局尋優(yōu)性能進(jìn)行了測(cè)試，并將其與標(biāo)準(zhǔn)GSO算法和PSO算法進(jìn)行了比較。在測(cè)試中，將種群大小設(shè)為30，每個(gè)測(cè)試函數(shù)運(yùn)行次數(shù)設(shè)為50次，每次運(yùn)行代數(shù)設(shè)為1000代。表2和表3分別顯示了函數(shù)f1－f4在30維和3維的情況下運(yùn)行50次的結(jié)果平均值和標(biāo)準(zhǔn)差，實(shí)驗(yàn)結(jié)果見表2和表3。

表2 f1－f4在30維時(shí)運(yùn)行的平均值和標(biāo)準(zhǔn)差

表3 f1－f4在3維時(shí)運(yùn)行的平均值和標(biāo)準(zhǔn)差

從表2中可以看出，在高維情況下標(biāo)準(zhǔn)GSO算法比PSO算法尋優(yōu)效率更高，尋優(yōu)結(jié)果更好，并且結(jié)果相對(duì)穩(wěn)定。通過標(biāo)準(zhǔn)測(cè)試函數(shù)f1－f4的測(cè)試，本文的CMGSO所得到的結(jié)果更趨向于已知最優(yōu)解。在多次運(yùn)算后，所得結(jié)果的平均值明顯優(yōu)于標(biāo)準(zhǔn)GSO算法得到的結(jié)果。進(jìn)一步證明了CMGSO算法繼承了標(biāo)準(zhǔn)GSO算法在高維情況下所具有的優(yōu)勢(shì)，且進(jìn)一步提高了優(yōu)化的效果。同時(shí)，通過對(duì)比3個(gè)算法在多次試驗(yàn)中結(jié)果的標(biāo)準(zhǔn)，可以看出CMGSO算法標(biāo)準(zhǔn)差相對(duì)較小，這充分說明了該算法具有比較穩(wěn)定的優(yōu)化性能。表3則是3個(gè)算法在低維中的優(yōu)化表現(xiàn)，CMGSO算法與標(biāo)準(zhǔn)GSO算法和PSO算法相比都有較好的數(shù)據(jù)結(jié)果，且算法的穩(wěn)定性較高。由測(cè)試結(jié)果可知，CMGSO算法相對(duì)于標(biāo)準(zhǔn)的GSO和PSO等優(yōu)化算法而言，提高了全局搜索能力和收斂速度，減小了陷入局部最優(yōu)的可能性，并對(duì)整體的優(yōu)化性能有了很好的改善和提高。

圖1至圖4分別為標(biāo)準(zhǔn)PSO、GSO和CMGSO算法在4個(gè)測(cè)試函數(shù)f1－f4中的收斂性能及尋優(yōu)性能的曲線比較圖，從這四個(gè)圖中能清晰地看出經(jīng)過改進(jìn)后的GSO在收斂速度和尋優(yōu)效果上與標(biāo)準(zhǔn)的PSO和GSO相比存在一定程度的優(yōu)越性。

圖1 f1（x）的收斂曲線效果對(duì)比

3 結(jié)束語

本文提出一種基于交叉因子和模擬退火的群搜索優(yōu)化算法CMGSO，它主要是在原有GSO的基礎(chǔ)上加入并融合了交叉因子和模擬退火的算子，解決了標(biāo)準(zhǔn)GSO中存在的早熟收斂、搜索精度不高、后期迭代效率不高，以及在后期運(yùn)算中容易陷入局部極優(yōu)點(diǎn)等問題，并能取得更好的最優(yōu)解。

本文通過實(shí)驗(yàn)證明了CMGSO與標(biāo)準(zhǔn)的PSO和GSO相比，有較好的整體收斂性能及較優(yōu)的尋優(yōu)效果，并在整體上提高了原有GSO算法的優(yōu)化性能，為解決優(yōu)化問題又提供了—種新的選擇與方案。

但是在低維函數(shù)情況下其優(yōu)化效果并不如高維函數(shù)的理想，說明CMGSO算法在低維中的優(yōu)化性能還有待于進(jìn)一步的改進(jìn)和提高，這將成為該算法下一步研究方向。

：

［1］HE S，WU Q H.A novel group search optimizer inspired by animal behavioural ［C］／／IEEE Congress on Evolutionary Computation，2006：4415－4421.

［2］WU Q H，HE S，Saunders J R.Group search optimizer：An optimization algorithm inspired by animal searching behavior［J］.IEEE Transactions on Evolutionary Computation，2009，13 （5）：973－990.

［3］ZHANG Wenwen，TENG Shaohua，LI Lijuan.Improved group search optimization algorithm ［J］.Computer Engineering and Applications，2009，45 （4）：48－51 （in Chinese）. ［張?chǎng)?，騰少華，李麗娟.改進(jìn)的群搜索優(yōu)化算法 ［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45 （4）：48－51.］

［4］LIU Feng，TAN Guang，LI Lijuan.A quick group search optimizer with passive congregation and its application in spatial structures［J］.Journal of Engineering Design，2010，17 （6）：420－425 （in Chinese）.［劉鋒，覃廣，李麗娟.快速被動(dòng)群搜索優(yōu)化算法及其在空間結(jié)構(gòu)中的應(yīng)用 ［J］.工程設(shè)計(jì)學(xué)報(bào)，2010，17 （6）：420－425.］

［5］FANG Juanyan，ZENG Jianchao，CUI Zhihua.A mixed group search optimization algorithm and its application ［D］.Taiyuan：Taiyuan University of Science and Technology，Computer Science and Technology Institute，2010 （in Chinese）.［房 娟艷，曾建潮，崔志華.混合群搜索優(yōu)化算法及其應(yīng)用研究［D］.太原：太原科技大學(xué)，計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，2010.］

［6］SHEN Hai，ZHU Yunlong，NIU Ben，et al.An improved group search optimizer for mechanical design optimization problems［J］.Progress in Natural Science，2009 （19）：91－97.

［7］LIU Qinjie，CHEN Guiming，LIU Xiaofang，et al.Genetic algorithm based SVM parameter composition optimization ［J］.Computer Applications and Software，2012，29 （4）：94－100（in Chinese）.［劉鯖潔，陳桂明，劉小方，等.基于遺傳算法的SVM參數(shù)組合優(yōu)化 ［J］.計(jì)算機(jī)應(yīng)用與軟件，2012，29（4）：94－100.］

［8］CHEN Xiaojuan，XHEN Jing.QoS routing algorithm based on genetic simulated anncaling algorithm ［J］.Application Research of Computers，2012，29 （12）：4680－4682 （in Chinese）.［陳曉娟，陳婧.基于遺傳模擬退火的QoS單播路由算法 ［J］.計(jì)算機(jī)應(yīng)用研究，2012，29（12）：4680－4682.］

［9］ZHOU Yuting，LIU Guangyuan，LAI Xiangwei.Applications of simulated annealing－immune particle swarm optimization in emotion recognition of galvanic skin response signal［J］.Journal of Computer Applications，2011，31 （10）：2814－2817 （in Chinese）.［周鈺婷，劉光遠(yuǎn)，賴祥偉.模擬退火免疫粒子群算法在皮膚電信號(hào)情感識(shí)別中的應(yīng)用 ［J］.計(jì)算機(jī)應(yīng)用，2011，31 （10）：2814－2817.］

［10］Lukasik S，Zak S.Firefly algorithm for continuous constrained optimization task ［J］.72ICCCI，Lecture Notes in Artificial Intelligence，2009，57 （96）：97－100.

［11］YANY Xinshe.Firefly algorithm，stochastic test functions and design optimisation ［J］.International Journal of Bio－inspired Computation，2010，2 （2）：78－84.

［12］XU Pengfei，MIAO Qiguan，LI Weisheng，et al.Adaptive simulated annealing algorithm and tabu search algorithm based on the function complexity ［J］.Acta Electronica Sinica，2012，40 （6）：1218－1222 （in Chinese）.［許鵬飛，苗啟廣，李偉生，張軍英.基于函數(shù)復(fù)雜度的自適應(yīng)模擬退火和禁忌搜索新算法 ［J］.電子學(xué)報(bào)，2012，40 （6）：1218－1222.］

［13］LI L J，XU X T，LIU F.The group search optimizer and its application to truss structure design ［J］.Advances in Structural Engineering，2010，13 （1）：43－51.