宋瑩瑩,王福林,蘭佳偉

(東北農(nóng)業(yè)大學(xué) 工程學(xué)院,哈爾濱 150030)

0 引言

遺傳算法是一種特殊的元啟發(fā)式優(yōu)化算法,它以生物進(jìn)化理論為基礎(chǔ),利用統(tǒng)計(jì)學(xué)方法對一個(gè)大而有限的解空間進(jìn)行智能搜索,是目前最常用、最有效的進(jìn)化算法,被成功地應(yīng)用于多個(gè)領(lǐng)域[1-6]。

遺傳算法的搜索能力主要受兩個(gè)因素影響,即種群競爭壓力與多樣性[5]。競爭壓力過小,算法的搜索過程會(huì)變得隨機(jī),降低收斂速度;而如果迭代初期種群就失去多樣性,會(huì)使算法搜索過程停滯,陷入局部最優(yōu)區(qū)域。由此可知,種群競爭壓力與多樣性成反比關(guān)系,增大競爭壓力會(huì)加速種群多樣性的喪失,而維持種群多樣性則抵消了競爭壓力的影響[7]。因此,只有當(dāng)種群同時(shí)具有多樣性與競爭壓力時(shí),算法才會(huì)有較強(qiáng)的搜索能力。

競爭壓力通常受交叉算子的影響,只有當(dāng)交叉算子能夠產(chǎn)生多個(gè)優(yōu)質(zhì)新個(gè)體時(shí),才會(huì)向種群內(nèi)部引入較大的競爭壓力,而替換操作則是通過決定哪一新個(gè)體能夠進(jìn)入種群取代舊個(gè)體來維持種群多樣性水平,消除競爭壓力對多樣性的影響。

因此,設(shè)計(jì)有效的交叉算子與替換操作對提升算法性能十分重要?，F(xiàn)有交叉算子的搜索方向過于單一,無法擴(kuò)展算子的搜索范圍,且替換操作需要計(jì)算復(fù)雜的種群結(jié)構(gòu),影響算法的運(yùn)行速度。

為了避免上述弊端,提出了一種改進(jìn)交叉算子(IX)與替換操作(SSR)。IX算子利用配對父代的遺傳信息,通過在不同的交叉方向上產(chǎn)生個(gè)體以實(shí)現(xiàn)擴(kuò)大算子的搜索范圍,提升解的質(zhì)量與收斂速度。SSR操作主要考慮了個(gè)體目標(biāo)函數(shù)值與多樣性貢獻(xiàn)率兩個(gè)特征,父代中特征值差的個(gè)體會(huì)被替換;同時(shí),替換操作還通過模擬方波函數(shù)的形式對種群進(jìn)行周期性的局部初始化操作,以維持種群多樣性。

1 改進(jìn)算法簡介

1.1 目標(biāo)函數(shù)的構(gòu)造方法

為了將有約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題,引入罰函數(shù)概念[3],通過懲罰不可行解將約束條件附加至原目標(biāo)函數(shù)中形成一個(gè)增廣目標(biāo)函數(shù),轉(zhuǎn)換形式為

F(x)=f(x)+MC

(1)

(2)

式中f(x)—約束優(yōu)化問題的原目標(biāo)函數(shù);

M—懲罰系數(shù);

C—懲罰項(xiàng)。

懲罰系數(shù)通常選取一個(gè)足夠的大的數(shù),而懲罰項(xiàng)由p個(gè)不等式約束gi(x)與q個(gè)等式約束hj(x)構(gòu)成。當(dāng)gi(x)為負(fù)值時(shí),符號(hào)‘< >’表示操作數(shù)的絕對值;當(dāng)gi(x)為非負(fù)數(shù)時(shí),則返回零值。

1.2 選擇算子

選擇算子作用于整個(gè)種群,選擇最具潛力的個(gè)體參與交叉操作,目的在于將有利基因遺傳到下一代。本文選用排序分組選擇,根據(jù)目標(biāo)函數(shù)值將種群分為兩組:一組由目標(biāo)函數(shù)值較好的個(gè)體構(gòu)成,另一組由目標(biāo)函數(shù)值較差的個(gè)體構(gòu)成。兩組個(gè)體依次配對能夠增大配對個(gè)體差異性,避免近親繁殖[7]。

1.3 交叉算子

交叉算子通過混合遺傳數(shù)據(jù),重組父代基因的方式產(chǎn)生優(yōu)質(zhì)個(gè)體,增大種群內(nèi)部競爭壓力,改善種群特性,被認(rèn)為是影響算法收斂的核心算子[4]。為了提高算法收斂速度與搜索能力,提出了IX算子。設(shè)參與交叉的配對個(gè)體為X1與X2(X1的目標(biāo)函數(shù)值優(yōu)于X2),IX算子按照如下公式產(chǎn)生個(gè)體,即

(3)

式中m—變量維數(shù);

r1—取值范圍[0,1]均勻分布的隨機(jī)數(shù);

r2—取值范圍[-1,0]均勻分布的隨機(jī)數(shù)。

IX算子首先利用了配對個(gè)體中目標(biāo)函數(shù)值較優(yōu)的個(gè)體X1,確定了一個(gè)基準(zhǔn)方向X2X1,通過給定步長r的不同取值范圍使算子能夠更加全面地探索交叉區(qū)域,增大優(yōu)質(zhì)個(gè)體產(chǎn)生概率,提升算法搜索能力與收斂速度。為了能夠更加直觀地了解IX算子的搜索范圍,以二維空間為例,IX算子產(chǎn)生交叉方向的示意圖如圖1所示。

圖1 IX算子產(chǎn)生交叉方向的二維空間示意圖

圖1中帶箭頭實(shí)線代表了配對個(gè)體在IM操作下產(chǎn)生的兩個(gè)交叉方向。由圖1可知:IX算子明顯增大了算子的搜索區(qū)域,而且在配對個(gè)體不同的分布狀態(tài)下,即便IM算子不能產(chǎn)生直接指向最優(yōu)解Xbest的方向,也能產(chǎn)生1個(gè)引導(dǎo)種群向最優(yōu)區(qū)域進(jìn)化的交叉方向。

1.4 變異算子

本文改進(jìn)的算法選用高斯變異算子,保證變異操作作用于個(gè)體附近的局部區(qū)域內(nèi),有助于提升算子的局部搜索能力[7-8]。

1.5 替換操作

對于多數(shù)實(shí)際問題,算法在優(yōu)化搜索空間的同時(shí)會(huì)逐漸喪失種群多樣性,這是造成早熟收斂的主要原因[9]。種群多樣性對算法搜索能力的影響如圖2所示。其中,圖2(a)中種群多樣性水平較低,算法在全局最優(yōu)解附近無解,而圖2(b)中種群多樣性水平較高,算法在全局最優(yōu)解附近有解,算法在圖2(b)中有更多的機(jī)會(huì)從點(diǎn)C到達(dá)全局最優(yōu)解,因此算法在圖2(b)中的搜索能力要強(qiáng)于圖2(a)。由此可見,種群多樣性對算法的搜索能力至關(guān)重要。

圖2 種群多樣性對算法搜索能力的影響

為了更好地維持種群多樣性、精煉搜索空間,本文提出了一種基于方波函數(shù)的替換操作SSR。SSR主要考慮了種群中個(gè)體的兩大特征值,即目標(biāo)函數(shù)與多樣性貢獻(xiàn)率,并以方波函數(shù)的模式對種群中部分個(gè)體進(jìn)行周期性的初始化操作。

規(guī)模為n的種群中個(gè)體c的多樣性貢獻(xiàn)率被定義為與其最鄰近個(gè)體間的歐氏距離[5],即

(4)

式中d—個(gè)體間的歐式距離函數(shù)。

種群多樣性為種群中個(gè)體多樣性貢獻(xiàn)率之和。由此可見,只有個(gè)體與其最臨近個(gè)體間有較大距離時(shí)才會(huì)對種群多樣性做出貢獻(xiàn)。

本文提出的替換操作具體步驟為:通過對比遺傳操作產(chǎn)生的新個(gè)體與父代個(gè)體的目標(biāo)函數(shù)值大小,搜索父代個(gè)體中目標(biāo)函數(shù)值次于新個(gè)體的群體,用新個(gè)體去替換群體中多樣性貢獻(xiàn)率最差的父代個(gè)體,更新種群。同時(shí),替換操作通過模擬方波函數(shù)的特定周期與幅值變化對種群進(jìn)行局部初始化操作,即當(dāng)算法運(yùn)行至相應(yīng)的迭代周期次數(shù)(T)時(shí),替換操作從更新后的種群中選擇目標(biāo)函數(shù)值最差的K個(gè)個(gè)體進(jìn)行初始化操作(K

圖3 種群局部初始化的周期方案

圖4 改進(jìn)遺傳算法的進(jìn)化策略流程圖

2 實(shí)例分析

2.1 油茶果采摘機(jī)優(yōu)化模型建立

隨著我國油茶果種植面積的不斷擴(kuò)增,油茶果采摘效率低下制約著其產(chǎn)業(yè)的發(fā)展,因此優(yōu)化油茶果采摘機(jī)具有重大的研究意義[10]。

油茶果采摘機(jī)的優(yōu)化主要包括兩方面:一是采摘臂長度的優(yōu)化,二是采摘機(jī)工作空間的優(yōu)化。油茶果采摘機(jī)的執(zhí)行機(jī)構(gòu)及油茶果分布空間的詳細(xì)信息如文獻(xiàn)所示[11]。采摘機(jī)優(yōu)化過程中涉及的變量包括:主柱高L1,主臂長L2,副臂長L3,主臂的轉(zhuǎn)角θ2,副主臂的轉(zhuǎn)角θ3。通過固定限制角的分段作圖法得出采摘機(jī)執(zhí)行機(jī)構(gòu)末端在二維平面內(nèi)的工作空間圖,如圖5(a)所示。工作空間由4條曲線構(gòu)成,曲線的方程依次為

(5)

圖5 油茶果采摘機(jī)空間示意圖

根據(jù)油茶果的分布圖,可以將所需的工作空間定義為一個(gè)4.5m×4.5m×2.7m的空間立方體,通過分析可將其轉(zhuǎn)化為4.5m×2.7m的平面矩形ABCD。由此可知,采摘機(jī)的工作空間需要滿足油茶果分布的平面矩形,主截面如圖5(b)所示?，F(xiàn)將工作空間分為S2與S3兩部分,分析可知S1=S3,因此工作空間的總面積S=S1+S2,且S1與S2均在圓C1與C2之間。假設(shè)ABCD等4點(diǎn)的坐標(biāo)依次為A(a,b),B(a,d),C(c,d),D(c,d),由此可以建立采摘機(jī)的優(yōu)化模型。

油茶果采摘機(jī)優(yōu)化模型的目標(biāo)函數(shù)為在滿足作業(yè)空間的要求下,執(zhí)行機(jī)構(gòu)的臂長之和最小;其次,執(zhí)行機(jī)構(gòu)的實(shí)際工作空間與所需的工作空間之差最小。因此,目標(biāo)函數(shù)為

(6)

約束條件關(guān)鍵在于確定邊界點(diǎn),主要包括軌跡區(qū)域約束、執(zhí)行機(jī)構(gòu)臂長約束和關(guān)節(jié)變量約束。

軌跡區(qū)域約束為

(7)

執(zhí)行機(jī)構(gòu)臂長約束條件為

(8)

關(guān)節(jié)變量約束條件為

(9)

2.2 優(yōu)化計(jì)算結(jié)果分析

根據(jù)油茶果的生長范圍對a、b、c、d進(jìn)行賦值,依次為a=1.5、b=0.3、c=1.9、d=2.8。利用本文改進(jìn)的算法進(jìn)行求解,本文改進(jìn)算法的參數(shù)設(shè)置如表1所示。

表1 改進(jìn)算法的參數(shù)設(shè)置

為了驗(yàn)證本文改進(jìn)算法對于優(yōu)化采摘機(jī)的有效性,選取近期發(fā)表較為先進(jìn)的遺傳算法進(jìn)行對比實(shí)驗(yàn),算法依次記為RCGA-1[12]、 RCGA-2[6]、RCGA-3[7],對比算法的參數(shù)設(shè)置如相應(yīng)文獻(xiàn)所示。為了實(shí)驗(yàn)的公平性,所有算法均在同一實(shí)驗(yàn)條件下進(jìn)行,將算法的最大迭代次數(shù)設(shè)為1 000代,且每個(gè)算法均運(yùn)行1 000次,取目標(biāo)函數(shù)的最小值(min)、最大值(max)、均值(mean)和方差(std)作為實(shí)驗(yàn)評(píng)價(jià)指標(biāo),實(shí)驗(yàn)結(jié)果如表2所示。取各算法求解的最優(yōu)值為最終結(jié)果,則油茶果采摘機(jī)優(yōu)化后各變量的取值如表3和表4所示。

表2 不同算法優(yōu)化的實(shí)驗(yàn)結(jié)果

表3 最優(yōu)結(jié)果對應(yīng)的變量取值

表4 最優(yōu)結(jié)果對應(yīng)的變量取值

由表2可知:本文改進(jìn)的算法RCGA求得的最優(yōu)解的均值最小,表明了RCGA在優(yōu)化采摘機(jī)模型時(shí)算法的整體性能最好。結(jié)合表3與表4可知:RCGA-1、RCGA-2與RCGA-3求得的最優(yōu)解相應(yīng)的變量中均有取值為負(fù)數(shù)的變量,不滿足實(shí)際約束條件。因此,相比于對比算法,本文改進(jìn)的算法具有較好的性能。對比優(yōu)化前與RCGA算發(fā)優(yōu)化后的油茶果采摘機(jī)的參數(shù)值進(jìn)行對比,如表5、表6所示。

表5 優(yōu)化前后采摘機(jī)的參數(shù)值

表6 優(yōu)化前后采摘機(jī)的參數(shù)值

由表5～表6的實(shí)驗(yàn)結(jié)果可知,RCGA將目標(biāo)函數(shù)f(x)提升了63.49%?？梢?改進(jìn)的算法能夠有效地優(yōu)化油茶果采摘機(jī)的臂長及工作空間。

3 結(jié)論

為了提升算法搜索性能,提出了一種簡單的IX交叉算子及SSR替換操作。IX算子的特點(diǎn)在于通過增加交叉方向,擴(kuò)大算子的搜索區(qū)域來提升解的質(zhì)量與收斂速度。SSR操作的特點(diǎn)則是根據(jù)父代目標(biāo)函數(shù)值與多樣性貢獻(xiàn)率兩個(gè)因素更新種群,同時(shí)對種群進(jìn)行周期性的初始化操作,以維持種群多樣性。將改進(jìn)后的算法應(yīng)用于油茶果采摘機(jī)的優(yōu)化問題上,通過對比實(shí)驗(yàn)可知:改進(jìn)的算法性能優(yōu)于其他先進(jìn)的算法,且改進(jìn)的算法能夠明顯優(yōu)化采摘機(jī)模型,使采摘機(jī)能夠在滿足工作空間的前提下機(jī)械臂的長度最小。