布谷鳥搜索算法的優(yōu)化研究

布谷鳥搜索算法的優(yōu)化研究

1改進(jìn)的cs算法隨著現(xiàn)代科學(xué)技術(shù)的快速發(fā)展，人們需要解決更復(fù)雜的優(yōu)化問題。為了尋找解決這些優(yōu)化問題的有效方法,自20世紀(jì)后期始,模擬自然界生物行為的各種元啟發(fā)式算法不斷涌現(xiàn),如模擬生物遺傳和進(jìn)化過程的遺傳算法、模擬蟻群覓食行為的蟻群算法、模擬鳥類群體運(yùn)動(dòng)行為的粒子群優(yōu)化算法等。近年來,一些模擬生物行為的更高效的新型元啟發(fā)式算法還在不斷脫穎而出,如在2009年,劍橋大學(xué)的YangXS和DebS模擬布谷鳥尋窩產(chǎn)卵行為,創(chuàng)立了布谷鳥搜索算法(CuckooSearch,CS)。CS算法具有控制參數(shù)少、簡單易實(shí)現(xiàn)、搜索路徑優(yōu)、全局搜索尋優(yōu)能力強(qiáng)等優(yōu)點(diǎn),在許多優(yōu)化問題上較著名的遺傳算法和粒子群優(yōu)化算法更具潛力和高效,已成為元啟發(fā)式算法領(lǐng)域的1個(gè)新亮點(diǎn)。文獻(xiàn)對(duì)CS算法改進(jìn)后得到的二進(jìn)制布谷鳥搜索算法(BCS),用于求解離散型NP完全問題,其性能也好于遺傳算法、蟻群算法和粒子群優(yōu)化算法。但CS算法同其他元啟發(fā)式算法一樣,也存在局部搜索能力相對(duì)較弱,導(dǎo)致后期搜索速度慢、尋優(yōu)精度不高等缺點(diǎn)。為了改進(jìn)CS算法的缺點(diǎn),文獻(xiàn)將局部搜索能力很強(qiáng)的共軛梯度法引入CS算法中,能大幅度提高CS算法的收斂速度,但它在尋優(yōu)過程要用到函數(shù)的梯度信息,這對(duì)于大型復(fù)雜的工程優(yōu)化問題,若梯度的計(jì)算量大,則該算法就體現(xiàn)不出優(yōu)勢(shì)。文獻(xiàn)提出步長控制因子α隨著迭代次數(shù)與最大迭代次數(shù)的比值而變的自適應(yīng)方法,文獻(xiàn)將1種隨著迭代次數(shù)與最大迭代次數(shù)的比值而變的自適應(yīng)權(quán)重因子引入CS算法中,雖然這2種改進(jìn)的CS算法都能夠提高CS算法的性能,但是均未涉及到布谷鳥搜索路徑步長的參數(shù)β和布谷鳥蛋被宿主鳥發(fā)現(xiàn)的概率pa的自適應(yīng)調(diào)整。本文擬將影響CS算法中布谷鳥搜索路徑步長的參數(shù)β和布谷鳥蛋被宿主鳥發(fā)現(xiàn)(淘汰)的概率pa這2個(gè)重要參數(shù)由固定值改為隨搜索過程自適應(yīng)變化的動(dòng)態(tài)參數(shù),并對(duì)越界的布谷鳥提出1種新的處理方法,將這種改進(jìn)的CS算法稱為自適應(yīng)布谷鳥搜索算法(AdaptiveCuckooSearch,ACS),ACS算法試圖在保留CS算法強(qiáng)大的全局搜索尋優(yōu)能力的同時(shí),在不需要利用函數(shù)的梯度信息的前提下,能較大幅度地提高算法的局部搜索能力和收斂速度。2cs算法及其機(jī)制的分析2.1布谷鳥隨機(jī)線模式搜索鳥窩在自然界中,布谷鳥尋找適合自己產(chǎn)蛋的鳥窩位置是隨機(jī)的或是類似隨機(jī)的方式,為了模擬布谷鳥尋窩的方式,首先,需要設(shè)定以下3個(gè)理想的狀態(tài):(1)布谷鳥1次只產(chǎn)1個(gè)蛋,并隨機(jī)選擇鳥窩來孵化它;(2)在隨機(jī)選擇的1組鳥窩中,最好的鳥窩將會(huì)被保留到下1代;(3)可利用的鳥窩數(shù)量n是固定的,1個(gè)鳥窩的主人能發(fā)現(xiàn)1個(gè)外來鳥蛋的概率pa∈,在這種情況下,宿主鳥可能會(huì)將外來的鳥蛋移除或者放棄現(xiàn)有的鳥窩,另覓地方再重新建1個(gè)新的鳥窩。在以上3個(gè)理想狀態(tài)的基礎(chǔ)上,布谷鳥按萊維飛行(Lévyflights)模式搜索鳥窩的路徑和位置更新公式如下:式中和分別表示第i(i=1,2,...,n)個(gè)鳥窩在第和第(k+1)代的位置向量(Xi=xi1,xi2,…;xij…xid,d為每個(gè)鳥窩的維數(shù),j為鳥窩的任意第j維);為點(diǎn)對(duì)點(diǎn)乘法;α表示步長控制因子;Lévy(λ)為Lévy隨機(jī)搜索路徑。Lévy飛行的隨機(jī)搜索路徑與時(shí)間t的關(guān)系服從Lévy分布,YangXS將Lévy分布函數(shù)經(jīng)過簡化和傅里葉變換后得到其冪次形式的概率密度函數(shù):通過位置更新后,用隨機(jī)數(shù)rand∈與pa對(duì)比,在CS算法中取pa=0.25。若rand>pa,則對(duì)進(jìn)行隨機(jī)改變,即布谷鳥蛋被宿主鳥發(fā)現(xiàn),因而鳥窩被新的巢穴取代,反之則不變,最后保留測(cè)試值較好的1組鳥窩位置,此時(shí)仍記為。在實(shí)際的優(yōu)化問題中,鳥窩的位置代表所有變量的有效取值空間,而鳥窩的適應(yīng)度代表變量取不同值所對(duì)應(yīng)的目標(biāo)函數(shù)。具體的CS算法流程和步驟詳見文獻(xiàn)。2.2cs算法的理論分析CS算法主要基于布谷鳥的巢寄生繁殖機(jī)理和萊維飛行搜索原理2個(gè)方面。2.2.1巢寄生蟲繁殖機(jī)理布谷鳥是典型的巢寄生鳥類,自己從不筑巢而是將自己的蛋產(chǎn)于蛋的顏色和大小、孵化期和育雛期等與已相似,雛鳥食性也基本相同的鳥類如黃鶯、云雀等的宿主鳥巢窩里,讓這些鳥替自己精心孵化。而且,它每飛到1個(gè)巢窩里,只生產(chǎn)1個(gè)鳥蛋。因宿主鳥發(fā)現(xiàn)寄生的布谷鳥蛋,就會(huì)將其推出鳥窩之外或者在別的地方新建1個(gè)鳥窩繁殖后代,故布谷鳥多在宿主鳥開始孵蛋之前,乘宿主鳥離巢外出時(shí)快速寄生產(chǎn)蛋。一旦巢寄生的布谷鳥蛋被保留在宿主鳥窩里,宿主鳥就會(huì)同時(shí)孵化自己的蛋和布谷鳥的蛋,往往布谷鳥蛋會(huì)比宿主鳥蛋先被孵出,且巢寄生的雛鳥一旦孵出,它有將宿主鳥的鳥蛋推出巢外的習(xí)性,從而獨(dú)享宿主鳥的撫育。YangXS和DebS在2009年創(chuàng)立CS算法時(shí),對(duì)布谷鳥的巢寄生繁殖機(jī)理做了深入的研究后,將其抽象為2.1節(jié)中提到的3個(gè)理想狀態(tài)的假設(shè)和式(1)。其中第1個(gè)假設(shè)可簡單陳述為1個(gè)鳥窩里的每個(gè)蛋代表1個(gè)解決方案,1個(gè)布谷鳥蛋則代表1種新的解決方案,目的是利用新的以及潛在的更好的解決方案,來取代1個(gè)在鳥窩里的不那么好的解決方案。目前CS算法只采用每個(gè)鳥窩只有1個(gè)布谷鳥蛋的最簡單的方法,至于每個(gè)鳥窩有多個(gè)布谷鳥蛋的更復(fù)雜的方法,有待今后深入研究。第2個(gè)假設(shè)可促使布谷鳥在搜索過程向優(yōu)秀的解逼近,以提高算法的收斂速度,但該假設(shè)沒有涉及到可調(diào)整的算法參數(shù)。第3個(gè)假設(shè)可以近似地認(rèn)為:n個(gè)鳥窩被隨機(jī)產(chǎn)生的新巢替換(新的隨機(jī)解決方案)的概率為pa。在CS算法中,取概率pa為固定值0.25,用隨機(jī)數(shù)rand∈是否大于pa來決定是否對(duì)鳥窩的位置進(jìn)行隨機(jī)改變(更新),若rand>pa則進(jìn)行隨機(jī)改變,否則不變。據(jù)此不難推出,當(dāng)pa值愈小時(shí),被淘汰(更新)的鳥窩亦愈多,全局隨機(jī)搜索的多樣性就愈強(qiáng),局部搜索的收斂性則愈弱,反之亦然。對(duì)于任何元啟發(fā)式算法,全局高效的隨機(jī)搜索和局部精細(xì)搜索戰(zhàn)略之間保持好的平衡會(huì)使算法更有效,在CS算法中,一旦n固定,主要是pa控制了全局隨機(jī)搜索和局部搜索之間的平衡,故在CS算法中,將pa取為固定值0.25并不是好的解決方法。如何使pa隨搜索過程自適應(yīng)變化,將是本文研究的重點(diǎn)之2.2.2布谷鳥尋窩優(yōu)化算法20世紀(jì)30年代,法國數(shù)學(xué)家萊維Lévy提出了Lévy分布,認(rèn)為Lévy飛行的隨機(jī)搜索路徑與時(shí)間的關(guān)系服從Lévy分布。之后很多學(xué)者對(duì)其進(jìn)行了研究,并用于解釋自然界的隨機(jī)現(xiàn)象,如布朗運(yùn)動(dòng)、隨機(jī)行走等。自20世紀(jì)90年代起,自然界的許多動(dòng)物和昆蟲如信天翁、蜜蜂和果蠅的覓食軌跡被證明符合萊維飛行(Lévyflights)模式,并當(dāng)目標(biāo)位置隨機(jī)且稀疏分布時(shí),對(duì)于M個(gè)相互獨(dú)立的探索者來說,萊維飛行是最理想的搜索策略。萊維飛行屬于隨機(jī)行走(randomwalk)的1種,行走的步長滿足1個(gè)重尾(heavy-tailed)的穩(wěn)定分布,在這種形式的行走中,短距離的探索與偶爾較長距離的行走相間。2006年,ShlesingerMF的研究表明,在智能優(yōu)化算法中采用萊維飛行,能擴(kuò)大搜索范圍、增加種群多樣性,更容易跳出局部最優(yōu)點(diǎn)。YangXS和DebS在2009年創(chuàng)立CS算法時(shí),認(rèn)為布谷鳥尋窩過程是按萊維飛行搜索路徑進(jìn)行的,這體現(xiàn)在他們導(dǎo)出的式(1)中。式(1)本質(zhì)上是隨機(jī)行走方程,一般情況下,1個(gè)隨機(jī)行走是1個(gè)馬爾可夫鏈,其未來位置取決于當(dāng)前位置(式(1)中的第1項(xiàng))和轉(zhuǎn)移概率(式(1)中的第2項(xiàng)αLévy(λ))。轉(zhuǎn)移概率項(xiàng)中的Lévy(λ)為萊維飛行隨機(jī)搜索路徑,它與時(shí)間t的關(guān)系服從Lévy分布,可用YangXS導(dǎo)出的式(2)表達(dá)。式(2)是1個(gè)帶有重尾的概率分布,雖然能夠從本質(zhì)上描述布谷鳥按萊維飛行隨機(jī)行走(搜索)尋窩過程,但尚未能進(jìn)一步用更簡潔且易編程的數(shù)學(xué)語言描述這一分布,以實(shí)現(xiàn)CS算法,故YangXS和DebS在實(shí)現(xiàn)CS算法時(shí)是采用MantegnaRN于1992年提出的模擬萊維飛行隨機(jī)搜索路徑的公式,即式(3)中s即為式(1)中的Lévy飛行隨機(jī)搜索路徑Lévy(λ):參數(shù)β同式(2)中λ的關(guān)系為λ=1+β,β∈(0,2],在CS算法中取β=1.5;參數(shù)μ、v為正態(tài)分布隨機(jī)數(shù),服從式(4)所示的正態(tài)分布;式(4)中的正態(tài)分布的標(biāo)準(zhǔn)差σμ、σv根據(jù)式(5)計(jì)算由式(3)～式(5)可知,s取決于2個(gè)正態(tài)分布隨機(jī)數(shù)μ和v,μ和v可大可小、可正可負(fù),故布谷鳥每次尋窩過程的萊維飛行隨機(jī)搜索路徑s即Lévy(λ)的步長和方向都是高度隨機(jī)改變的,很容易從1個(gè)區(qū)域躍入另外1個(gè)區(qū)域,使CS算法的全局多樣性即全局搜索尋優(yōu)能力很強(qiáng),這特別有利于在算法前期隨機(jī)搜索鎖定最優(yōu)值所在的區(qū)域,但若在算法后期隨機(jī)性太強(qiáng),則不利于局部區(qū)域的精細(xì)搜索,造成收斂速度和收斂精度降低。若要使CS算法更高效,則需在全局性和收斂性兩方面能夠兼顧、達(dá)到好的平衡。除μ和v2個(gè)正態(tài)分布隨機(jī)數(shù)控制了萊維飛行隨機(jī)搜索路徑的步長和方向外,參數(shù)β亦會(huì)影響搜索步長,但在CS算法中將β取為固定值1.5,這不是很好的解決方法。如何使β隨搜索過程自適應(yīng)變化,以使CS算法在全局性和收斂性兩方面達(dá)到好的平衡,從而進(jìn)一步提高CS算法的效率,這將是本文研究的重點(diǎn)之二。另外,在CS算法的運(yùn)行過程中,所有鳥窩的位置均根據(jù)式(1)來進(jìn)行更新,但由于實(shí)際約束條件的限制,鳥窩只能安置在界內(nèi)即變量的定義域內(nèi),而由式(1)計(jì)算得到的新的鳥窩位置并不能均保證都在界內(nèi)。在CS算法中,統(tǒng)一將越界的鳥窩設(shè)定為邊界上的值,再根據(jù)這個(gè)值進(jìn)行下1代的更新,這種處理越界鳥窩的方式,可能會(huì)失去這些鳥窩位置變化的活力,使算法的收斂速度降低。如何更好地處理越界鳥窩,將是本文研究的重點(diǎn)之三。3acs算法3.1模型3:個(gè)人局部搜索能力根據(jù)2.2.1節(jié)的分析可知,將參數(shù)pa(即鳥窩被淘汰或更新的概率)取為固定值0.25不利于保持CS算法的全局隨機(jī)搜索和局部搜索之間的戰(zhàn)略平衡,這將影響算法的性能。為使CS算法更高效,ACS算法提出使pa隨算法進(jìn)程動(dòng)態(tài)變化的自適應(yīng)策略:在算法前期取相對(duì)小的pa值,被更新的鳥窩數(shù)相對(duì)多,使算法保持很強(qiáng)的全局搜索能力,同時(shí)兼顧局部搜索能力;在算法后期取相對(duì)大的pa值,被更新的鳥窩數(shù)相對(duì)少,使算法保持很強(qiáng)的局部搜索能力,同時(shí)兼顧全局搜索能力;在算法由前期到后期的進(jìn)化過程,使pa隨迭代次數(shù)的增加而增大。為實(shí)現(xiàn)pa的自適應(yīng)策略,進(jìn)行了大量的仿真實(shí)驗(yàn),結(jié)果表明:當(dāng)pa<0.1時(shí),被更新的鳥窩數(shù)太多,全局多樣性太強(qiáng),收斂性很弱;當(dāng)pa>0.75時(shí),被更新的鳥窩數(shù)太少,收斂性太強(qiáng),全局多樣性很弱,易陷入局部最優(yōu),故pa在[0.1,0.75]之間隨迭代次數(shù)的增加而逐漸增大效果較好。根據(jù)仿真實(shí)驗(yàn)結(jié)果,提出用式(6)實(shí)現(xiàn)參數(shù)pa的自適應(yīng)策略:式中k為算法當(dāng)前迭代次數(shù),kmax為人為設(shè)定的最大迭代次數(shù)。根據(jù)式(6),當(dāng)k=0時(shí),pa=0.1,當(dāng)k=kmax時(shí),pa=0.73。實(shí)際上,算法在尋優(yōu)過程中k是從1開始逐漸增大直至收斂為止,一般收斂時(shí)k<kmax,最大當(dāng)k=kmax時(shí),若算法仍未找到最優(yōu)值也終止計(jì)算。因此,由式(6)計(jì)算的pa在(0.1,0.73]的區(qū)間內(nèi)隨迭代次數(shù)的增加而增大,完全實(shí)現(xiàn)了本文提出的使pa隨算法進(jìn)程(k/kmax)的增加而由小到大動(dòng)態(tài)變化的自適應(yīng)策略,這將使改進(jìn)后的CS算法即ACS算法能夠在全局隨機(jī)搜索能力和局部搜索能力之間保持好的平衡。換言之,ACS算法通過pa的自適應(yīng)動(dòng)態(tài)變化,實(shí)現(xiàn)了在算法前期以全局搜索為主、局部搜索為輔,以期能在全局范圍內(nèi)快速鎖定最優(yōu)值可能存在的若干區(qū)域;而后隨算法進(jìn)程全局搜索逐漸減弱,局部搜索逐漸加強(qiáng),至算法后期以局部搜索為主、全局搜索為輔,以期能提高收斂的速度和精度,又不至于陷入局部最優(yōu),從而從整體上提升算法的性能。3.2模型2:隨機(jī)步長s根據(jù)2.2.2節(jié)的初步分析可知,參數(shù)β的取值將影響步長s的大小,而CS算法將其取為固定值1.5,不利于使算法在全局性和收斂性兩方面保持好的平衡,這將影響算法的性能。為了進(jìn)一步研究參數(shù)β究竟如何影響步長s,對(duì)0<β≤2范圍內(nèi)的β和步長s的關(guān)系進(jìn)行了大量的仿真實(shí)驗(yàn),結(jié)果表明:在0<β≤0.8的范圍內(nèi),隨參數(shù)β的逐漸增大,根據(jù)式(3)計(jì)算的步長s的波動(dòng)范圍從1個(gè)極大的范圍(如β取0.1時(shí),步長s在-10～10范圍內(nèi)波動(dòng))逐漸減小到β取0.8時(shí)的-35～35范圍,顯然當(dāng)β∈(0,0.8)時(shí),步長s的取值以及波動(dòng)范圍太大,全局搜索尋優(yōu)的能力太強(qiáng),局部搜索精度太低,收斂性太差;在0.8≤β≤1.8的范圍內(nèi),隨參數(shù)β的逐漸增大,步長s的波動(dòng)范圍從-35～35范圍繼續(xù)逐漸減小到β取1.8時(shí)的-3～3范圍,圖1列舉了在0.8<β≤1.8的范圍內(nèi)4個(gè)β值下,步長s的波動(dòng)情況,圖2為β取1.8時(shí)步長s波動(dòng)情況的放大圖。顯然在0.8≤β≤1.8范圍內(nèi),步長s的波動(dòng)范圍相對(duì)較合理;在1.8≤β≤2的范圍內(nèi),隨參數(shù)β的逐漸增大,步長s的值及其波動(dòng)范圍又逐漸增大,算法后期的隨機(jī)性又逐漸增強(qiáng),這不利于算法后期局部區(qū)域的精細(xì)搜索,會(huì)造成收斂速度和收斂精度降低。綜上分析,參數(shù)β在[0.8,1.8]之間取值較好。為使CS算法更高效,ACS算法提出使參數(shù)β隨算法進(jìn)程動(dòng)態(tài)變化的自適應(yīng)策略:從算法第1代k=1開始,β取0.8左右的值并隨算法進(jìn)程(k/kmax)的增加而隨機(jī)波動(dòng)增大,直至收斂時(shí)(k/kmax接近1)β取1.8左右的值。這種β自適應(yīng)策略,使β在算法的前期取相對(duì)較小的值,相應(yīng)的步長s的取值較大且波動(dòng)范圍也較大,使算法保持很強(qiáng)的全局搜索尋優(yōu)能力,同時(shí)兼顧一定的局部精細(xì)搜索能力即收斂能力;隨著算法進(jìn)程(k/kmax)的增加,β呈隨機(jī)波動(dòng)增大,相應(yīng)的步長s則呈隨機(jī)波動(dòng)減小;至算法的后期,使β的值逐漸波動(dòng)增大盡可能的接近1.8,相應(yīng)的步長s的取值較小且波動(dòng)范圍也較小,使算法保持很強(qiáng)的局部精細(xì)搜索能力即收斂能力,同時(shí)兼顧全局搜索尋優(yōu)能力。若能實(shí)現(xiàn)上述參數(shù)β隨算法進(jìn)程動(dòng)態(tài)變化的自適應(yīng)策略,有望使算法在全局性和收斂性兩方面保持好的平衡,從而較大幅度提升算法的性能。根據(jù)上述分析,提出用式(7)實(shí)現(xiàn)參數(shù)β的自適應(yīng)策略:式中randn(0.8,0.3)表示平均值為0.8,方差為0.3的正態(tài)分布隨機(jī)數(shù);radn(0,0.05)表示平均值為0,方差為0.05的正態(tài)分布隨機(jī)數(shù);k與kmax的符號(hào)意義與2.1節(jié)中所述的相同。式(7)由[randn0.8,0.3)+0.3+k/kmax]和[1.8+randn(0,0.05)]2項(xiàng)構(gòu)成,且在算法的進(jìn)程中取2項(xiàng)中小的1項(xiàng)。前項(xiàng)中的隨機(jī)數(shù)randn(0.8,0.3)和0.3這兩者相加已由仿真實(shí)驗(yàn)證明其值是隨機(jī)波動(dòng)的且通常都略大于0.8,而k/kmax的值隨算法進(jìn)程(k由1逐漸增大至收斂時(shí)接近kmax)在區(qū)間(0,1)的范圍內(nèi)由小到大逐漸增大,故前項(xiàng)[randn(0.8,0.3)+0.3+k/kmax]的值隨算法進(jìn)程從大約0.8逐漸隨機(jī)波動(dòng)增大至大約1.8,若β取前項(xiàng)的值,也即β做同樣的變化,但在算法后期,因k/kmax接近1,前項(xiàng)的值有可能大于1.8較多,為避免β大于1.8過多,β取2項(xiàng)中小的1項(xiàng),因后項(xiàng)[1.8+randn(0,0.05)]是在1.8附近很小的范圍隨機(jī)波動(dòng)的數(shù),故這樣取β值可保證在算法后期其值即使大于1.8也不會(huì)大太多。這樣就實(shí)現(xiàn)了參數(shù)β隨算法進(jìn)程(k/kmax)的增加而隨機(jī)波動(dòng)從約0.8增大至約1.8的自適應(yīng)策略,相應(yīng)的步長s則從大到小隨機(jī)波動(dòng)減小,在算法進(jìn)化過程中較好地保持了全局性和收斂性之間的平衡,因而能夠較大幅度地提升算法的性能。3.3邊界上的布谷鳥窩在CS算法中,統(tǒng)一將越界鳥窩設(shè)定為邊界上的值,這在一定程度上喪失了這些鳥窩位置變化的活力,使算法的收斂速度降低。該怎么樣處理越界鳥窩比較好呢?聯(lián)想到在殘酷的自然界,有些種群的動(dòng)物為了生存選擇了群居生活的方式,它們共同覓食、防御外敵并繁育后代。每個(gè)群居體都有自己的首領(lǐng),都會(huì)圈定自己的生活領(lǐng)域,當(dāng)群居體中的某個(gè)個(gè)體偶爾越界誤入其它群居體的領(lǐng)域時(shí),可能會(huì)遭受攻擊。受攻擊的越界個(gè)體一般會(huì)產(chǎn)生2種情況:一種是受攻擊后沒有受傷或者是受輕傷的個(gè)體,會(huì)選擇折返回自己的領(lǐng)域?qū)ふ沂最I(lǐng)并在首領(lǐng)所在區(qū)域附近生活,這會(huì)給它帶來安全感,減少其今后再越界的概率;另一種是受攻擊后受重傷的個(gè)體,一時(shí)無法折返回自己的領(lǐng)域內(nèi),只好選擇在領(lǐng)域的邊界附近養(yǎng)傷和生活。受動(dòng)物群居生活的上述行為的啟發(fā),將CS算法中當(dāng)前代(第k代)的最優(yōu)布谷鳥個(gè)體視為布谷鳥群體的首領(lǐng),將待優(yōu)化求解的函數(shù)的定義域視為布谷鳥群體的生活領(lǐng)域,將布谷鳥個(gè)體超出定義域?qū)ふ业降镍B窩稱為越界鳥窩,提出按隨機(jī)數(shù)r∈的不同分2種情況處理越界鳥窩的新方法:一種是當(dāng)0≤r≤0.9時(shí),即越界的布谷鳥有90%的概率放棄越界鳥窩,選擇折返回定義域內(nèi)當(dāng)前代(第k代)最優(yōu)鳥窩(首領(lǐng)的位置)附近的區(qū)域隨機(jī)建立1個(gè)新鳥窩開始生活(相當(dāng)于前述受攻擊的越界個(gè)體的情況一);另一種是當(dāng)0.9<r≤1時(shí),即越界的布谷鳥有10%的概率放棄越界鳥窩,選擇折返回定義域的邊界上重新建立鳥窩(相當(dāng)于前述的情況二)。這種處理越界鳥窩的新方法可由式(8)實(shí)現(xiàn)。式中為第k代越界的布谷鳥i折返回定義域內(nèi)或邊界上新建的鳥窩;為第k代的最優(yōu)鳥窩;randn(0,0.001)表示平均值為0,方差為0.001的正態(tài)分布隨機(jī)數(shù);為第k代當(dāng)0.9<r≤1時(shí),越界的布谷鳥i折返回邊界上新建的鳥窩。根據(jù)式(8),越界的布谷鳥中有90%的概率選擇折返回自己的領(lǐng)域內(nèi),在第k代最優(yōu)鳥窩附近的區(qū)域(該區(qū)域的范圍由正態(tài)分布隨機(jī)數(shù)randn(0,0.001)隨機(jī)確定)內(nèi)隨機(jī)建立1個(gè)鳥窩,這相當(dāng)于越界的布谷鳥向當(dāng)前代最優(yōu)布谷鳥的一次學(xué)習(xí)過程,不僅新建的鳥窩位置靠近最優(yōu)鳥窩,增強(qiáng)了安全感,減少了今后再次越界的可能性;而且新鳥窩與安置在邊界上的鳥窩相比,擁有更優(yōu)秀的位置信息,有利于算法沿更高效的尋優(yōu)途徑進(jìn)化,可提高算法的尋優(yōu)能力和收斂速度。根據(jù)式(8),另外還有約10%的越界布谷鳥與CS算法一樣,選擇在自己領(lǐng)域的邊界上建立新鳥窩,這樣處理的目的是為了避免所有越界的布谷鳥都向最優(yōu)鳥窩靠攏,以保持種群的多樣性,降低算法陷入局部最優(yōu)的可能性。綜上所述,與CS算法統(tǒng)一將全部越界鳥窩設(shè)定在邊界上的值的僵化處理方法相比,式(8)所提出的處理越界鳥窩的新方法,能使這些鳥窩的位置變化更具活力,有利于提升算法的性能。4模擬實(shí)驗(yàn)4.1測(cè)試函數(shù)的選取為了測(cè)試ACS算法的性能,選用如表1所示的8個(gè)各具典型特點(diǎn)的標(biāo)準(zhǔn)測(cè)試函數(shù),通過仿真實(shí)驗(yàn)測(cè)試其性能,并與CS算法的測(cè)試結(jié)果進(jìn)行比較。仿真環(huán)境為Windows7操作系統(tǒng),intel處理器,2.10GHz,內(nèi)存2GB,仿真軟件為MATLAB7.0。表1中,Easom函數(shù)是1個(gè)簡單的單谷函數(shù),它的特點(diǎn)是谷很窄,最小值在1個(gè)很小的范圍內(nèi)變化;Master函數(shù)是1個(gè)余弦波式的測(cè)試函數(shù);Ackley函數(shù)是1個(gè)多谷函數(shù),各小谷同最小值對(duì)應(yīng)的谷都較淺,算法較容易跳出局部最優(yōu),這3個(gè)測(cè)試函數(shù)常用于測(cè)試算法的收斂精度。NiH測(cè)試函數(shù)又名大海撈針函數(shù)(NeedleinaHaystack)是1個(gè)典型的欺騙問題,隨著參數(shù)a和b的變化,該函數(shù)將形成不同嚴(yán)重程度的欺騙性,在進(jìn)行測(cè)試的過程中a和b分別取值3.0與0.05,此時(shí)函數(shù)在(0,0)處取得全局最大值3600,在(5.12,5.12)、(-5.12,5.12)、(5.12,-5.12)和(-5.12,-5.12)處取得局部極大值約為2748.782(在函數(shù)進(jìn)行測(cè)試的時(shí)候轉(zhuǎn)化為求最小值問題)。Schaffer函數(shù)在距全局極小值約3.14的范圍內(nèi)隆起有無限多局部極小值,由于該函數(shù)的強(qiáng)烈震蕩性質(zhì)以及它的全局極小值被局部極小值所包圍的特性使得一般算法很難找到它的全局最優(yōu)解。Shubert函數(shù)和Langermann函數(shù)屬于多峰多谷的測(cè)試函數(shù),Shubert函數(shù)具有18個(gè)極小值,而Langermann函數(shù)也具有多個(gè)不均衡分布的極小值,都很容易陷入局部最優(yōu)。Rastrigin函數(shù)為典型的不可分離的多峰多谷的測(cè)試函數(shù),全局極小值在變量為0時(shí)達(dá)到,求解域內(nèi)存在大量的局部極小值,一般算法難以獲得全局最優(yōu)值。綜上所述,選取這8個(gè)不同特點(diǎn)的函數(shù)檢驗(yàn)算法的綜合優(yōu)化能力即全局尋優(yōu)能力和收斂能力。4.2算法性能分析為了公平的比較ACS算法和CS算法的性能,對(duì)2種算法、不同的測(cè)試函數(shù)分別獨(dú)立運(yùn)行100次,鳥窩數(shù)量均取n=30,步長控制因子α為0.01,收斂精度為10-7,大體上簡單、低維的函數(shù)優(yōu)化問題最大迭代次數(shù)kmax的取值相對(duì)小,復(fù)雜、高維的函數(shù)優(yōu)化問題最大迭代次數(shù)kmax的取值相對(duì)大,若收斂精度低于10-7或迭代次數(shù)超過kmax,則認(rèn)為算法未能成功收斂。為了對(duì)2種算法的收斂水平和尋優(yōu)能力進(jìn)行比較分析,分別記錄了2種算法最大收斂代數(shù)kc,max、最小收斂代數(shù)kc,min、平均收斂代數(shù)kc,avg、收斂率η,如表2所示。最佳適應(yīng)度隨進(jìn)化代數(shù)的變化曲線如圖3～圖5所示(5個(gè)2維函數(shù)最佳適應(yīng)度隨進(jìn)化代數(shù)的變化曲線圖形基本類似,僅畫出NiH函數(shù)的變化曲線作為代表)。由表2和圖3～圖5可知,ACS算法和CS算法對(duì)5個(gè)2維測(cè)試函數(shù)均能夠成功收斂,但達(dá)到同樣的收斂精度10-7,ACS算法所需的最大收斂代數(shù)、最小收斂代數(shù)和平均收斂代數(shù)均低于CS算法,且ACS算法的收斂率均高于CS算法,說明ACS算法的收斂速度、收斂性能均優(yōu)于CS算法。若在相同迭代次數(shù)的條件下,則能得到ACS算法的收斂精度優(yōu)于標(biāo)準(zhǔn)CS算法的結(jié)論。對(duì)于高維的Master函數(shù)和Rastrigin函數(shù),CS算法在設(shè)定的最大迭代次數(shù)內(nèi)均不能收斂,而ACS不僅能夠收斂,還能夠達(dá)到較高的收斂率。對(duì)于高維的Ackley函數(shù)ACS算法和CS算法都能夠成功收斂,但相比于CS算法而言,ACS算法收斂代數(shù)明顯減少,說明無論是對(duì)于低維函數(shù)還是高維