段艷明 肖輝輝 譚黔林 趙翠芹
(河池學(xué)院大數(shù)據(jù)與計(jì)算機(jī)學(xué)院 河池 546300)
隨著科學(xué)技術(shù)的日新月異,云計(jì)算、人工智能、5G、傳感網(wǎng)、大數(shù)據(jù)和腦科學(xué)等眾多新技術(shù)新理論和社會(huì)經(jīng)濟(jì)的高速發(fā)展,許多科學(xué)研究和實(shí)際工程問(wèn)題日益復(fù)雜化,其各領(lǐng)域中所涉及的各類復(fù)雜優(yōu)化問(wèn)題的處理,越發(fā)成為社會(huì)各行各業(yè)迫切需要解決的問(wèn)題,這些問(wèn)題的求解對(duì)優(yōu)化技術(shù)提出了更高的要求,即求解精度要高,計(jì)算速度要快,穩(wěn)定性要好,而傳統(tǒng)的優(yōu)化方法(如Lagrange 乘數(shù)法及單純形法等)在解決這些復(fù)雜優(yōu)化問(wèn)題時(shí)存在計(jì)算精度不高且耗時(shí)過(guò)長(zhǎng)等不足。為了解決這些求解優(yōu)化問(wèn)題存在的瓶頸,人類需要尋求新的方法和途徑。受自然界進(jìn)化規(guī)律和生物群體智能行為的啟發(fā),一系列智能算法不斷被提出,并且由于這些元啟發(fā)式智能算法具有不需要傳統(tǒng)優(yōu)化方法所需要的連續(xù)、可微等限制條件的優(yōu)點(diǎn),這為解決復(fù)雜的優(yōu)化問(wèn)題提供了一種新途徑和新思路。
依據(jù)顯花植物繁殖機(jī)理,Yang 設(shè)計(jì)了一種名為花授粉算法(Flower Pollination Algorithm,F(xiàn)PA)的智能優(yōu)化算法[1],由于該算法實(shí)現(xiàn)過(guò)程簡(jiǎn)單且具有較好的全局探索和局部開(kāi)采平衡能力等優(yōu)點(diǎn),使其在大量?jī)?yōu)化領(lǐng)域取得了成功應(yīng)用。當(dāng)前,該算法已被成功應(yīng)用到企業(yè)投資分配[2]、醫(yī)學(xué)[3]、能源[4~7]、傳感網(wǎng)[8]等領(lǐng)域。然而該算法與其他智能算法一樣,也存在一些不足,如算法演化后期計(jì)算速度慢、容易早熟,尋優(yōu)精度不高,魯棒性差等缺陷,導(dǎo)致其在解決大量復(fù)雜優(yōu)化問(wèn)題時(shí)獲得的結(jié)果不盡人意。為了克服這些算法存在上述的不足,提高其收斂能力,當(dāng)前眾多學(xué)者依據(jù)各種智能算法的特征和優(yōu)缺點(diǎn),運(yùn)用了諸多的策略和方法對(duì)其進(jìn)行了改進(jìn),構(gòu)建了許多優(yōu)化能力更強(qiáng)的新算法模型,使得大量的工程優(yōu)化問(wèn)題得到更好的解決。因此,許多學(xué)者也對(duì)FPA 算法進(jìn)行了深入改進(jìn)研究,如Singh等[9]利用函數(shù)適應(yīng)度值對(duì)轉(zhuǎn)換概率p 進(jìn)行動(dòng)態(tài)調(diào)整,并取得了較好的效果;Tawhid 等[10]利用鯨魚優(yōu)化算法的搜索獵物策略和攻擊獵物方法替換了FPA 算法的全局搜索策略,構(gòu)建了一種新的混合算法WOFPA(Whale Optimization Algorithm and Flower Pollination Algorithm),其性能與對(duì)比算法相比,得到了一定程度的提升,但該算法增加了較多的參數(shù),降低了算法的靈活性,并只在低維上驗(yàn)證了其性能的優(yōu)越性,沒(méi)有在高維得到驗(yàn)證,使其缺少了說(shuō)服力;Gálvez等[11]為了改進(jìn)標(biāo)準(zhǔn)FPA 算法在優(yōu)化多模態(tài)問(wèn)題時(shí),僅依靠其萊維飛行策略和授粉穩(wěn)定性機(jī)制無(wú)法找到多個(gè)最優(yōu)解的缺點(diǎn),提出一種多模態(tài)花授粉算法MFPA(Multimodal Flower Pollination Algorithm),其思想是在基本花授粉的基礎(chǔ)上加入記憶機(jī)制識(shí)別潛在的全局和局部最優(yōu)解,引入一種新的選擇機(jī)制確保解的多樣性,融入凈化記憶處理方法循環(huán)消除重復(fù)的解,通過(guò)對(duì)14 個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的優(yōu)化,驗(yàn)證了其有效性,且性能優(yōu)于對(duì)比算法;El-Shahat 等[12]提出了一種改進(jìn)的花授粉算法,該算法利用懲罰函數(shù)對(duì)每個(gè)解進(jìn)行評(píng)估,對(duì)解中的不可行解運(yùn)用FRIO(Flower Repair and Improve Operator)進(jìn)行處理,經(jīng)過(guò)全局搜索或者局部搜索后,產(chǎn)生的新解再與全局最優(yōu)解進(jìn)行交叉操作,然后采用S函數(shù)對(duì)改進(jìn)算法進(jìn)行離散化,并對(duì)多維背包問(wèn)題進(jìn)行求解,其優(yōu)化性能要強(qiáng)于對(duì)比算法。
從上述可知,當(dāng)前的改進(jìn)方法對(duì)FPA算法的優(yōu)化性能具有一定的提升,但這些改進(jìn)的FPA算法的優(yōu)化能力還有較大的提升空間,且一些改進(jìn)策略降低了算法的靈活性和增加了算法的復(fù)雜性。為此,本文提出了一種自適應(yīng)骨干花授粉算法(Adaptive Bare Bones Flower Pollination Algorithm,ABFPA),算法把骨干思想利用到FPA算法的局部搜索部分,通過(guò)自適應(yīng)搜索中心的高斯變異對(duì)花朵個(gè)體進(jìn)行位置更新,在此基礎(chǔ)上進(jìn)一步利用指數(shù)變異進(jìn)行位置優(yōu)化;同時(shí),在保留基本FPA 算法的個(gè)體信息共享思想的基礎(chǔ)上增加信息共享的個(gè)體數(shù)量,更大程度上進(jìn)行個(gè)體的有效信息交換。實(shí)驗(yàn)結(jié)果表明ABFPA 算法簡(jiǎn)單且高效,尋優(yōu)效果好,收斂速度快,魯棒性好,與現(xiàn)有經(jīng)典的改進(jìn)FPA算法相比,亦顯示出良好的競(jìng)爭(zhēng)力。
FPA 算法是依據(jù)顯花植物繁殖機(jī)理而設(shè)計(jì)的一種優(yōu)秀的智能優(yōu)化算法。從其仿生原理可知,其全局搜索策略是模擬植物繁殖的異花授粉過(guò)程,而植物異花傳粉過(guò)程具有萊維飛行特征,這使FPA算法具有良好的探索能力,F(xiàn)PA 算法的局部搜索機(jī)制是源于植物繁殖的自花授粉過(guò)程。同時(shí),學(xué)者Yang 通過(guò)參數(shù)p 較好地處理了算法的探索和開(kāi)采的平衡問(wèn)題。
然而,從算法的局部搜索方程可知,其局部搜索是通過(guò)兩個(gè)隨機(jī)的個(gè)體進(jìn)行信息共享,增強(qiáng)了算法的種群多樣性,但單純地通過(guò)兩個(gè)隨機(jī)個(gè)體的信息共享來(lái)實(shí)現(xiàn)局部搜索,缺少個(gè)體位置更新的引導(dǎo)性,信息共享程度低,因此,F(xiàn)PA算法的局部?jī)?yōu)化能力較弱,制約著算法的優(yōu)化性能。
針對(duì)FPA 算法的局部搜索方程存在的不足和骨干思想的優(yōu)點(diǎn),本文提出了把骨干思想融入到FPA 算法的局部搜索策略中,運(yùn)用高斯變異的隨機(jī)分布策略來(lái)保持種群的多樣性,同時(shí)對(duì)高斯分布的搜索中心進(jìn)行自適應(yīng)調(diào)整,達(dá)到個(gè)體根據(jù)算法的進(jìn)化程度來(lái)進(jìn)行高斯變異;高斯變異增強(qiáng)了種群多樣性,但分散的個(gè)體也導(dǎo)致局部搜索速度和精度降低,并易脫離全局最優(yōu)位置,為此在高斯變異的基礎(chǔ)上進(jìn)一步進(jìn)行指數(shù)變異,使個(gè)體即保持多樣性又較集中在最優(yōu)區(qū)域,從而提高算法的局部搜索速度和精度;另外,通過(guò)0.5 的概率進(jìn)行二分交叉,對(duì)FPA 算法的局部搜索方程再增加一個(gè)隨機(jī)個(gè)體,通過(guò)兩組個(gè)體的差分矢量來(lái)擾動(dòng)個(gè)體的進(jìn)化,進(jìn)而更大程度上增強(qiáng)了種群的多樣性和開(kāi)采能力。
依據(jù)PSO算法的仿生原理可知,種群在演化過(guò)程中每個(gè)解都要利用進(jìn)化中的兩個(gè)最優(yōu)個(gè)體(全局和個(gè)體)進(jìn)行更新,文獻(xiàn)[13]提出每個(gè)種群個(gè)體都收斂于其自身的歷史最優(yōu)值和全局最優(yōu)值的加權(quán)平均值,與算法的參數(shù)設(shè)置關(guān)系不大。在此基礎(chǔ)上,2003年Kenedy等提出BBPSO算法,該算法中的高斯分布是以pbest和gbest為兩點(diǎn)的固定模式進(jìn)行搜索,而錯(cuò)過(guò)了所有有效區(qū)域或盡可能多的區(qū)域,忽略了種群中的普通個(gè)體,未能利用到更多個(gè)體所攜帶的有用信息,限制了種群的多樣性和算法的優(yōu)化性能,導(dǎo)致算法易陷入局部極值,這是現(xiàn)有的骨干算法存在的主要問(wèn)題。另外,由于事先并不知道pbest和gbest的相對(duì)位置,當(dāng)算法陷入局部最優(yōu)時(shí),依靠隨機(jī)產(chǎn)生的變異個(gè)體來(lái)跳出局部極值具有一定的難度。針對(duì)以上分析,本文把骨干思想引入FPA 算法的同時(shí)對(duì)高斯變異的搜索中心均值μ和方差δ進(jìn)行自適應(yīng)調(diào)整,增強(qiáng)花朵個(gè)體的多樣性。
首先,確定花朵i在d維進(jìn)行更新時(shí)的榜樣花朵xm。利用式(1)計(jì)算變量b,隨機(jī)產(chǎn)生一個(gè)數(shù)a∈(0,1),若a>b,xm為當(dāng)前種群中的一個(gè)隨機(jī)花朵,否則,xm為全局最優(yōu)花朵,如式(2)所示:
其中,xi是隨機(jī)花朵個(gè)體,xbest是全局最優(yōu)花朵個(gè)體。
接著,確定高斯分布的均值μ。以最小化問(wèn)題為例,按照式(3)~(6)計(jì)算μ的取值范圍[μmin,μmax],按式(7)得到高斯分布的均值μ:
式(3)中的fmax和fmin分別為當(dāng)前種群的最大值和最優(yōu)值,其擴(kuò)展因子w的范圍為(-1,1)。當(dāng)花朵i優(yōu)于榜樣花朵m時(shí),有f(xm)>f(xi),w為正值,μ值向著當(dāng)前花朵i的方向擴(kuò)展;當(dāng)花朵i劣于榜樣花朵m時(shí),有f(xm)<f(xi),w為負(fù)值,μ值向著榜樣花朵m的方向擴(kuò)展。在算法迭代初期,種群較為分散,花朵i遠(yuǎn)離榜樣花朵m,則xi和xm相差較大,f(xm)和f(xi)的差異也較大,擴(kuò)展因子 ||w也較大,進(jìn)而B2值也較大,最終使得μ的取值范圍中較多地為較優(yōu)花朵的區(qū)域,更多地關(guān)注了較優(yōu)花朵;隨著迭代的進(jìn)行,種群趨于集中,xi和xm的差異逐漸減小,f(xm)和f(xi)的差異也逐漸減小,擴(kuò)展因子 ||w較小,μ的取值范圍也逐漸縮小。因此,自適應(yīng)高斯變異的方差μ滿足算法前期的勘探能力和后期的開(kāi)采能力的性能要求。
然后,確定高斯分布的方差δ。若花朵i即為上一代的最優(yōu)個(gè)體,則根據(jù)式(8)計(jì)算方差δ,否則,按式(9)計(jì)算方差δ:
其中,Ub為函數(shù)的取值范圍的上限,Lb為函數(shù)的取值范圍的下限,xi為當(dāng)前花朵位置。
最后,通過(guò)式(10)得到高斯分布的花朵位置:
通過(guò)高斯分布得到隨機(jī)的花朵個(gè)體,很大程度上增大了種群中每個(gè)個(gè)體之間的差異性,從而達(dá)到改善算法的局部搜索能力,但也在某種程度上降低了算法的局部搜索速度和精度。因此,本文在高斯分布的基礎(chǔ)上再采用指數(shù)變異,使高斯分布的隨機(jī)個(gè)體進(jìn)一步向最優(yōu)位置靠攏。指數(shù)公式為
標(biāo)準(zhǔn)FPA 算法的局部授粉(優(yōu)化)部分是單純通過(guò)隨機(jī)的兩個(gè)個(gè)體之間的矢量差來(lái)進(jìn)行信息共享,在本文算法中除了通過(guò)高斯變異和指數(shù)變異來(lái)改進(jìn)局部?jī)?yōu)化部分外,還遵循了標(biāo)準(zhǔn)FPA算法的局部授粉(優(yōu)化)思想,依然利用了個(gè)體信息的共享,只不過(guò)在此基礎(chǔ)上,通過(guò)0.5的概率進(jìn)行二分叉,當(dāng)產(chǎn)生的隨機(jī)數(shù)小于0.5 時(shí)進(jìn)行高斯變異和指數(shù)變異,否則把進(jìn)行信息共享的個(gè)體增加到3個(gè),通過(guò)1組1個(gè)隨機(jī)個(gè)體與當(dāng)前個(gè)體的差分矢量和1組兩個(gè)隨機(jī)個(gè)體的差分矢量來(lái)擾動(dòng)個(gè)體的進(jìn)化,這樣就更大程度上提高了個(gè)體信息的共享程度,個(gè)體信息共享的公式為
其中,ε1,ε2 分別是[0,1]上服從均勻分布的隨機(jī)數(shù),是在種群中隨機(jī)選擇的三個(gè)個(gè)體。這樣,當(dāng)產(chǎn)生的隨機(jī)數(shù)大于0.5時(shí),利用式(12)替換FPA 算法中的局部搜索方程進(jìn)行個(gè)體間的信息共享。
根據(jù)以上分析,ABFPA 算法的具體實(shí)施步驟如下。
step1:對(duì)ABFPA 算法的參數(shù)n、p、D、Max_iter賦初值;
step2:求解每個(gè)解的值,并記錄所有值中的最小值或最大值和其相應(yīng)的解
step3:如果p>rand,執(zhí)行全局搜索,并判斷新產(chǎn)生的解是否越界,如果越界做越界處理;
step4:如果p<rand,生成隨機(jī)變量r;
step5:當(dāng)r<0.5,則執(zhí)行step6,否則執(zhí)行step8;
step6:利用式(10)對(duì)個(gè)體的位置進(jìn)行更新;
step7:對(duì)step6 的個(gè)體再運(yùn)用式(11)對(duì)其位置進(jìn)行更新;
step8:采用式(12)對(duì)個(gè)體的位置進(jìn)行更新;
step9:對(duì)step7 或step8 產(chǎn)生的新解做越界處理;
step10:求解step3或step7或step8產(chǎn)生的新解的值,并記錄所有值中的最小值或最大值和其相應(yīng)的解;
step11:如迭代次數(shù)大于閾值Max_iter,則進(jìn)化結(jié)束,并輸出所有解中的最優(yōu)解和其相應(yīng)的適應(yīng)度值,否則,轉(zhuǎn)step3繼續(xù)演化。
從上述ABFPA 算法的進(jìn)化過(guò)程可知,ABFPA算法與基本FPA算法的框架基本類似,但對(duì)其局部搜索部分進(jìn)行了改進(jìn),以0.5的概率進(jìn)行二分叉,一部分進(jìn)行自適應(yīng)搜索中心高斯變異和指數(shù)變異,另一部分增加了進(jìn)行信息共享的個(gè)體。
為了驗(yàn)證本文算法的有效性、可行性和正確性,本文對(duì)四類典型的優(yōu)化測(cè)試函數(shù)(求解問(wèn)題)進(jìn)行求解,函數(shù)的詳情見(jiàn)表1,且本文對(duì)所求函數(shù)的解都是求其最小值。為了全面客觀評(píng)價(jià)新算法的性能優(yōu)勢(shì),本文運(yùn)用新算法與現(xiàn)有經(jīng)典的改進(jìn)FPA算法對(duì)比實(shí)驗(yàn)及分析,具體包括:1)收斂精度對(duì)比分析;2)非參數(shù)統(tǒng)計(jì)檢驗(yàn);3)穩(wěn)定性和收斂速度對(duì)比分析,還包括基本FPA算法的對(duì)比。
表1 本文采用的典型測(cè)試函數(shù)
為了測(cè)試ABFPA 算法與現(xiàn)有經(jīng)典的改進(jìn)FPA算法在性能上是否具有不錯(cuò)的競(jìng)爭(zhēng)力,本文選用目前有代表性的四種改進(jìn)算法進(jìn)行對(duì)比,分別是混合差分進(jìn)化花授粉算法(a hybrid differential evolution-flower pollination algorithm,DE-FPA)[14],基于精英反向?qū)W習(xí)的花授粉算法(Elite Opposition-based Flower Pollination Algorithm,EOFPA)[15],改進(jìn)的花授粉算法(Modified Flower Pollination Algorithm,MFPA)[16],基于廣義反向?qū)W習(xí)的改進(jìn)花授粉算法(Modified Generalised Oppsition-based Flower Pollination Algorithm,MGOFPA)[16]。
本文的所有參數(shù)值分別設(shè)立為種群大小n=50,最大演化次數(shù)Max_iter=200;所有算法的參數(shù)p取相同的值0.8,其他參數(shù)取自相關(guān)文獻(xiàn)中;DE-FPA 算法的參數(shù)CR 和F 分別取值為0.9 和0.5。為了降低實(shí)驗(yàn)偏差,每種對(duì)比算法在其每個(gè)求解問(wèn)題上都單獨(dú)執(zhí)行30 次。各種對(duì)比算法的尋優(yōu)結(jié)果如表2 所示,其中“-/≈/?”符號(hào)分別表明本文算法的收斂精度低于、相當(dāng)于或高于對(duì)比優(yōu)化算法,“w/t/l”符號(hào)分別說(shuō)明ABFPA算法與對(duì)比算法對(duì)比,在求解問(wèn)題上,有w 個(gè)優(yōu)化結(jié)果好于比較算法,有t個(gè)尋優(yōu)結(jié)果與比較算法相當(dāng),有l(wèi)個(gè)優(yōu)化效果劣于比較算法,最優(yōu)結(jié)果用加粗凸顯。
對(duì)表2進(jìn)行分析可知,在12個(gè)函數(shù)中,ABFPA、EOFPA、MGOFPA 算法各自取得7 個(gè)、5 個(gè)和1 個(gè)理論解,其他算法都沒(méi)取得理論解,這表明ABFPA 算法的尋優(yōu)能力明顯好于其他算法。算法具體在4類求解問(wèn)題上的求解結(jié)果是在第1 類測(cè)試函數(shù)上,ABFPA、MGOFPA 和EOFPA 算法分別獲得了4 個(gè)、1 個(gè)和兩個(gè)理論解,其他兩個(gè)算法均沒(méi)有達(dá)到理論解,這表明ABFPA 比對(duì)比算法更適合用來(lái)求解這類問(wèn)題;對(duì)于第2 類多峰高維函數(shù),ABFPA 算法與EOFPA 算法的效果基本持平,優(yōu)勢(shì)不是很大,但要優(yōu)于其他對(duì)比算法,且從表4 中的函數(shù)f7的平均迭代次數(shù)可知,ABFPA 算法的求解速度要顯著快于比較算法;在第3 類低維多峰的函數(shù)中,ABFPA 算法優(yōu)勢(shì)不大;在第4 類多峰帶旋轉(zhuǎn)的高維函數(shù)上,ABFPA 算法和EOFPA 算法性能相當(dāng),但遠(yuǎn)遠(yuǎn)好于其余算法。ABFPA 算法的收斂性能總體上要明顯地優(yōu)于對(duì)比算法,展示出了較強(qiáng)的競(jìng)爭(zhēng)力。
表2 5種改進(jìn)算法的優(yōu)化均值偏差和標(biāo)準(zhǔn)差
為了更客觀評(píng)價(jià)對(duì)比算法的綜合性能,本文采用非參數(shù)統(tǒng)計(jì)檢驗(yàn)(Friedman 檢驗(yàn))進(jìn)行實(shí)驗(yàn)對(duì)比分析,其結(jié)果如表3 所示。對(duì)比算法的Rankings 值越小,其性能表現(xiàn)越突出,則排名越前。
從表3 中可知,ABFPA 算法的Rankings 值最小,在所有對(duì)比算法中,排在第一位,這表明ABFPA 算法的整體性能好于其他算法,具有良好的角逐力。
表3 5種FPA的Friedman檢驗(yàn)(D=30,4)
為了對(duì)ABFPA 算法的穩(wěn)定性和收斂速度進(jìn)行分析,驗(yàn)證其穩(wěn)定性和求解速度的優(yōu)勢(shì),實(shí)驗(yàn)結(jié)果如表4 所示。本文在每個(gè)求解問(wèn)題上都設(shè)置了一個(gè)尋優(yōu)精度邊界值,若每種對(duì)比算法收斂到上述設(shè)定的閾值(邊界值)且進(jìn)化代數(shù)已大于一定的代數(shù)(本文設(shè)置為3000),則斷定該算法對(duì)該求解問(wèn)題尋優(yōu)失敗;其他參數(shù)設(shè)置同上,對(duì)比算法在每個(gè)求解問(wèn)題上獨(dú)立執(zhí)行30 次;計(jì)算出SR(執(zhí)行成功率,執(zhí)行成功率=算法找到求解精度邊界值所需要的代數(shù)/算法總的執(zhí)行代數(shù))值和mean_iter(平均進(jìn)化代數(shù))值,對(duì)比算法的SR 越大且mean_iter 越小,其性能越優(yōu),表4 中符號(hào)“NA”表示對(duì)比算法尋優(yōu)受挫,最優(yōu)結(jié)果用加粗凸顯。
表4 6種算法的尋優(yōu)成功率及平均迭代次數(shù)
從表4 的最后一行的平均尋優(yōu)成功率和收斂迭代次數(shù)可以看出,F(xiàn)PA 和MFPA 算法的平均尋優(yōu)成功率為0%;ABFPA 的尋優(yōu)成功率為87%,均收斂迭代次數(shù)為418,較明顯地優(yōu)于對(duì)比算法。這說(shuō)明ABFPA 算法的穩(wěn)定性最強(qiáng),ABFPA 算法的求解速度是所有算法中最快的。
本文對(duì)基本FPA 算法的搜索策略進(jìn)行了理論分析,發(fā)現(xiàn)其存在著的不足,制約著該算法的優(yōu)化性能。為了提高其收斂能力,本文提出了一種自適應(yīng)骨干花授粉算法。為了驗(yàn)證新算法的有效性和先進(jìn)性,從解的質(zhì)量、魯棒性和收斂速度等多方面進(jìn)行了實(shí)驗(yàn)對(duì)比分析,實(shí)驗(yàn)結(jié)果驗(yàn)證了改進(jìn)算法是行之有效的。通過(guò)較豐富的實(shí)驗(yàn)結(jié)果證明,與具有代表性的其他改進(jìn)算法相比,新算法的優(yōu)化能力具有一定的優(yōu)勢(shì)。
在今后的工作中,如何利用新算法來(lái)處理能源、運(yùn)輸?shù)葘?shí)踐中各類復(fù)雜的優(yōu)化問(wèn)題進(jìn)行進(jìn)一步研究。