新型PSGA算法在通航物流系統(tǒng)效能優(yōu)化中的應(yīng)用

張昊，安景文

(1.中國礦業(yè)大學(xué) 管理學(xué)院，北京 100083；2.中航通飛華北飛機工業(yè)有限公司，河北 石家莊 051430)

然而，遺傳算法的運行性能除了與遺傳算子有關(guān)，更取決于算法結(jié)構(gòu)框架的效率水平.本文將嘗試對遺傳算法的算法結(jié)構(gòu)進行重新設(shè)計，同時設(shè)計引入一種新型適應(yīng)度調(diào)和因子(AF因子)，以使新算法的效率更高，更適合在通航物流系統(tǒng)等對算法時間效率要求較高的場景下應(yīng)用.

1 PSGA改進遺傳算法

1.1 基本遺傳算法

遺傳算法(GA)的算法流程是對自然界優(yōu)勝劣汰機制的模擬與抽象，它所面向的主要應(yīng)用領(lǐng)域是各種難以找到精確解的NP問題，主要由3種信息交換機制構(gòu)成，分別是：選擇算子、交叉算子與變異算子.通過建立包含多個個體的種群，對個體按照3種信息交換機制進行自身部分信息的隨機互換，同時循環(huán)對種群中的個體進行優(yōu)勝劣汰，使種群中個體趨于同一化，使個體的適應(yīng)度值收斂，進而獲得最優(yōu)解.遺傳算法的算法流程如圖1.

圖1 遺傳算法優(yōu)化流程

1.2 PSGA算法分析

與其他智能優(yōu)化算法相比，GA算法可以使搜索范圍快速遍布整個可行解空間，可以在理論意義上更加快速地發(fā)現(xiàn)最大值或最小值所在位置.但是從另一方面來看，GA算法也存在很明顯的局限性.例如：遺傳算法的個體基因構(gòu)成往往針對于具體工程問題，在問題規(guī)模較大的情況下，GA算法的基因構(gòu)造也會更加復(fù)雜，會使編程規(guī)模和求解效率受到顯著影響；GA算法的1個運行單位至少包含3個運算步驟，當(dāng)總遺傳個體的數(shù)量較多時，算法的整體性能也會受到顯著影響.

1.2.1 PSGA算法結(jié)構(gòu)

基于上述遺傳算法的特點分析，本文對傳統(tǒng)遺傳算法的結(jié)構(gòu)與流程進行了重新設(shè)計，提出了一種新型變種群極搜索遺傳算法(PSGA).PSGA算法的結(jié)構(gòu)邏輯是：首先在種群中找到需要繁殖的個體特征值，一般為最大值和最小值；之后，對個體特征值進行變種群繁殖，在繁殖過程中增加對繁殖方向進行實時控制的調(diào)節(jié)因子，即AF因子，使最大值的種群繁殖向當(dāng)前最優(yōu)值所在的周邊區(qū)域發(fā)散；同步地，使最小值的種群繁殖向整個解空間進行發(fā)散；通過多代迭代后，個體的搜索范圍在盡可能最大限度地覆蓋解空間的同時，也已經(jīng)盡可能最大限度地探索到了更加精確的最優(yōu)解.PSGA算法的結(jié)構(gòu)流程如圖2所示.

圖2 PSGA算法結(jié)構(gòu)流程

1.2.2 PSGA算法的適應(yīng)度調(diào)和因子

· 堪薩斯城(Kansas City Plant)國家安全園區(qū)負責(zé)39種重要非核組件的生產(chǎn)，包括點火、保險和控制組件；

PSGA算法中對“兩極”的控制以及對最大適應(yīng)度種群和最小適應(yīng)度種群搜索空間大小的控制是通過種群適應(yīng)度調(diào)和因子(AF因子)來實現(xiàn)的.AF因子調(diào)和能力的強弱與種群進化最大代數(shù)、當(dāng)前進化代數(shù)、當(dāng)前種群中的最大適應(yīng)度值和最小適應(yīng)度值以及當(dāng)前個體適應(yīng)度值相關(guān).當(dāng)進化過程中任意一代中的兩極個體進行新的種群繁衍時，其所生成的子個體分布位置即由AF調(diào)和因子來控制.當(dāng)進行繁殖的個體適應(yīng)度值更趨向于目標(biāo)函數(shù)理想值時，AF調(diào)和因子會控制其產(chǎn)生的子個體分布位置更集中于該個體周圍的空間范圍，以確認是否該個體的周圍空間還存在更好的個體；相應(yīng)地，當(dāng)進行繁殖的個體適應(yīng)度值與目標(biāo)函數(shù)理想值相差較大時，AF調(diào)和因子會讓被繁殖個體生成的子個體分布空間更大，使新的個體能夠在新的空間中探索更好的適應(yīng)度值，其大小由以下公式確定.

圖3 適應(yīng)度因子調(diào)和下的種群個體分布

其中，F(xiàn)AF為調(diào)和因子，itermax、iter為極種群的最大進化代數(shù)和當(dāng)前進化代數(shù)，fmax和fmin為當(dāng)前代數(shù)中的最大適應(yīng)度值和最小適應(yīng)度值，f為當(dāng)前個體的適應(yīng)度值，m為調(diào)和指數(shù)，α、β為調(diào)和系數(shù).

極種群中的個體按照各自的適應(yīng)度值所確定的上述適應(yīng)度調(diào)和因子來確定其分布的空間范圍.

圖3為1個PSGA算法算例中進化到最后一代的種群分布圖.可見適應(yīng)度調(diào)和因子在控制種群個體分布空間范圍上的效果.A區(qū)域中的星號非常集中，在一個很小的空間中排布，代表這些個體的適應(yīng)度值更趨于符合問題求解的理想解，這時AF調(diào)和因子在某個體的繁衍過程中將生成的新個體的分布控制在圍繞該個體的很小區(qū)域內(nèi)，即出現(xiàn)了A區(qū)域中的效果.由圖3中同樣可見，圓點的分布空間要比星號廣了很多，甚至其部分個體分布得更遠，如C點所示.這說明在進行某個體的繁殖過程中，該個體的適應(yīng)度值相對于問題的理想解相距很遠，這時通過AF因子的控制，使新生的個體在空間分布上更廣，更能有機會探索到更好的適應(yīng)度值.

2 PSGA算法運行性能分析

為了更加清楚地了解PSGA算法的運行特性，以下將利用PSGA算法對不同復(fù)雜度的標(biāo)準測試函數(shù)最優(yōu)解搜索過程進行考察，通過使用Matlab8.3平臺進行編程實現(xiàn).

2.1 Booth’s function測試

Booth’s function函數(shù)的基本形式為

f(x,y)=(x+2y-7)2+(2x+y-5)2,

其中，測試域為-20≤x≤20和-20≤y≤20.該函數(shù)有一個最小值，在(1,3)處取得最小值為f(1,3)=0.其三維空間如圖4所示.

表1 Booth’s function函數(shù)PSGA算法運行10次最優(yōu)解對比表Tab.1 Booth’s function’s optimal solution after 10 times operation with PSGA

由表1可見，在10次運算中使用PSGA算法求得的最優(yōu)解最小精度為10-6數(shù)量級，其中有6次達到了10次運算中的最大精度10-10數(shù)量級，平均最優(yōu)解的精度在10-7，為6.963 08×10-7,更接近函數(shù)已知的最優(yōu)解F(x,y)=0；相對地，使用傳統(tǒng)GA算法求解，在最優(yōu)值的精度上就低了一些，最高精度在10-8數(shù)量級，最低精度在10-4數(shù)量級，平均精度為2.329 04×10-5.另一方面，從最優(yōu)解的求解時間上看，使用PSGA算法所需要的時間最多為1.454 s，在連續(xù)10次運行中平均耗時為1.2931 s，普遍少于1.5 s，而相應(yīng)地，在規(guī)定的2 s時限內(nèi)，傳統(tǒng)GA算法運行求解的最小值平均水平要明顯低于PSGA算法.在限定時間內(nèi)，平均運算效率PSGA算法較GA算法高出35.35%.這說明，PSGA算法的運行效率要明顯高于傳統(tǒng)遺傳算法，在運行中能夠快速收斂，在進化代數(shù)上要小于遺傳算法，同時深度搜索能力更強，能夠快速定位最優(yōu)解的位置，求解質(zhì)量更好.

2.2 Lévi function測試

Lévi function函數(shù)的基本形式如下：

f(x,y)=sin2(3πx)+(x-1)2(1+sin2(3πy))+(y-1)2(1+sin2(2πy)),

其中，測試域為-20≤x≤20和-20≤y≤20.該函數(shù)有一個最小值，在(1,1)處取得最小值為F(1,1)=0.其三維空間如圖5所示.

圖4 Booth’s function測試函數(shù)三維圖

圖5 Lévi function測試函數(shù)三維圖

在使用PSGA算法進行優(yōu)化求解時，預(yù)設(shè)參數(shù)與Booth’s function函數(shù)相同，同樣連續(xù)運行10次，對比遺傳算法運行數(shù)據(jù)如表2記錄所示.

表2 Lévi function函數(shù)PSGA算法運行10次最優(yōu)解對比表Tab.2 Lévi function’s optimal solution after 10 times operation with PSGA

續(xù)表2Continued Tab.2

由表2可見，在Lévi function函數(shù)的尋優(yōu)過程中，PSGA算法與GA算法的平均運算精度都有所下降，但在規(guī)定時間內(nèi)，PSGA算法的精度基本穩(wěn)定在10-7量級，在10次運算中有8次達到了10-7量級，最小精度為10-6次數(shù)為2次，對比函數(shù)已知的最優(yōu)解F(1,1)=0可知，在對精度要求不是極高的應(yīng)用環(huán)境下，PSGA算法10次運行所求得的最優(yōu)解是有效的；相對地，可以看到GA算法在精度上下降了很多，求解平均精度只有10-2，平均值為0.044 253 646，最高精度也只有10-5，最低精度下降到了10-1數(shù)量級，比PSGA算法的平均精度低很多.同時這也說明在時效性要求高的應(yīng)用場景中，傳統(tǒng)遺傳算法的尋優(yōu)效率會有一定局限性.此外，從最優(yōu)解求解時間上看，使用PSGA算法最多為1.245 s，平均耗時為1.130 6 s，平均運算效率比GA高出43.50%.說明PSGA算法的運行效率和求解質(zhì)量更好.

3 PSGA算法在通航物流配載系統(tǒng)優(yōu)化中的應(yīng)用

本文以通航物流配載系統(tǒng)的配載效能為目標(biāo)，以飛行高度、飛行速度、商載重量、燃油質(zhì)量、大氣壓強以及通用飛機自身的設(shè)計特性為主要參考因素，建立單位任務(wù)配載經(jīng)濟效能優(yōu)化模型，以某型號通航貨運飛機的實際狀態(tài)參數(shù)為例，使用PSGA算法對模型進行求解.

設(shè)PSGA算法的目標(biāo)函數(shù)為

Fmax=max{Feco},

其中，F(xiàn)eco={Fe1,Fe2,…Fei…}，且有

其飛行狀態(tài)環(huán)境約束為

其中，

Feco為經(jīng)濟效能水平指數(shù)，Ml、Mp、Ms分別為某型通航飛機的燃油載量、飛機空重和飛機商載，KAB為執(zhí)行一次單位通航物流任務(wù)從A點到B的飛行距離，α、β為配載系數(shù)，α>0、β>0，令α+β=1，C0、C1、C2、C0D、C1D、C2D為與通用飛機飛行特性相關(guān)的狀態(tài)系數(shù)，vmax為飛機最大巡航速度，hmax為飛機最大巡航高度.

設(shè)目標(biāo)函數(shù)為PSGA算法的個體適應(yīng)度函數(shù)，種群擴張的最大代數(shù)為itermax，當(dāng)前代數(shù)為iter，個體當(dāng)前適應(yīng)度為ad，本代中最大適應(yīng)度為admax，最小適應(yīng)度為admin，當(dāng)前代初始個體為adini.

設(shè)PSGA算法的AF因子為F(α,β)，則有

相關(guān)參數(shù)初始值為

C0=0.013,C1=0.000 06,C0D=0.003 6,C1D=-0.067,C2D=0.18;θ=0°,

Mp=3 402,vmax=100,hmax=6 000,Mmax=5 250,

itermax=50,m=2,α=10,β=3.

根據(jù)以上配載狀態(tài)設(shè)計和算法參數(shù)設(shè)置，在Matlab8.3軟件環(huán)境下進行編程和數(shù)據(jù)分析.

圖6所示為單位通航物流配載任務(wù)效能極小值種群的進化過程比較圖.圖6a是極小值衍生的初始種群空間分布圖，圖6b是極小值種群經(jīng)過30代進化后的空間分布圖.圖6中的任意一個三角形標(biāo)志都代表了一個滿足問題要求的配載狀態(tài)解.根據(jù)2幅個體種群進化對比圖，初代中的三角形個體隨機分布在解空間的不同位置，呈現(xiàn)局部聚集和全局發(fā)散的態(tài)勢，有些個體甚至分布到了空間的角落部分，這是在自適應(yīng)調(diào)和因子的作用下，種群具備了較強的解空間開拓能力所致；而在經(jīng)過若干代的迭代之后，個體已經(jīng)完成了大部分解空間的探索過程，找到了相對初代更加優(yōu)秀的解和相應(yīng)的局部解空間，這時種群整體體現(xiàn)出來的是總體適應(yīng)度水平更高且在解空間中呈現(xiàn)集中性、聚集性的特點.圖6b中所示的三角形區(qū)域相較于圖6a更加聚集，即是適應(yīng)度調(diào)和因子在迭代后期進行有向性調(diào)節(jié)的結(jié)果.

a.第1代極小值種群分布；b.第30代極小值種群分布.

圖7是單位通航物流任務(wù)配載效能水平優(yōu)化曲線對比圖.圖7a點線為使用經(jīng)典遺傳算法進行優(yōu)化的過程.圖7b中的連續(xù)實線為使用PSGA算法進行優(yōu)化的過程，2種算法都是在最大種群規(guī)模為20，最大進化代數(shù)為50的同等環(huán)境下進行的，其中遺傳算法的3個算子的概率為：選擇概率0.6、交叉概率0.6、變異概率0.1.兩種算法都進行10次運算后取平均值.據(jù)圖7b可見，在PSGA算法中的種群適應(yīng)度值跨度明顯更大，這說明PSGA算法在各代的進化過程中解空間搜索范圍更大；同時在圖7中也可以看出遺傳算法的進化曲線更緩，PSGA算法的曲線則更加陡峭，這說明PSGA算法在進化中的最優(yōu)解搜索速度更快，但由于搜索范圍更大，PSGA算法不易陷入局部最優(yōu)解.由圖7c中的聯(lián)合比較圖可見，PSGA算法在第10代搜索到的最優(yōu)效能水平指數(shù)為537.931 0，遺傳算法在第35代搜索到的最優(yōu)效能水平指數(shù)為536.476 3，可見PSGA算法在同種群條件下的收斂速度更快，尋找到的最優(yōu)解質(zhì)量更好，運行效率更高.

a.GA算法；b.PSGA算法；c.GA算法/PSGA算法.

在上述所搜索到的最優(yōu)個體中，任務(wù)載機在飛行狀態(tài)穩(wěn)定在高空2 212.55 m，飛行速度維持在215.21 km/h，商載量965.13 kg，燃油量836.92 kg，最遠飛行距離為1 442.90 km時的單位通航物流配載任務(wù)效能指數(shù)達到最優(yōu).

4 總結(jié)

設(shè)計和提出了一種新型變種群極搜索遺傳算法(PSGA)以及為該算法所設(shè)計的適應(yīng)度調(diào)和因子(AF因子).通過以2類不同復(fù)雜度的基準測試函數(shù)為例進行MATLAB編程，比較了同環(huán)境下PSGA算法與GA算法的時間效率和求解精度.根據(jù)測試數(shù)據(jù)表明，PSGA算法在效率和精度上要明顯優(yōu)于傳統(tǒng)GA算法.通過將該算法和傳統(tǒng)GA算法同時應(yīng)用于通航物流系統(tǒng)配載效能優(yōu)化問題，比較兩者在收斂效率和求解精度上的差別，說明了PSGA算法在時間效率要求較高的應(yīng)用場景下,其有效性和適用性均比傳統(tǒng)GA算法要好.