改進(jìn)量子粒子群算法在航材初始配置中的應(yīng)用

田 靜，張恩豪，付維方

（中國民航大學(xué)航空工程學(xué)院，天津 300300）

當(dāng)今國內(nèi)外航空市場競爭日趨激烈，航空公司比以往任何時候都更加重視成本控制，而航材的初始購置成本是企業(yè)運(yùn)營成本中的重要組成部分，因此對初始航材的成本控制是提高公司經(jīng)濟(jì)效益的重要途徑。

對于航材初始配置的研究需要解決模型構(gòu)建和求解兩個問題。在模型構(gòu)建方面，航空公司往往將保障率作為重要的保障目標(biāo)，因此優(yōu)化模型目標(biāo)函數(shù)的構(gòu)建中需以保障率為基礎(chǔ)[1]，并引入成本變量，構(gòu)建單位成本系統(tǒng)保障率最大的模型，將系統(tǒng)保障率均勻分配到每一單位成本上，尋求單位成本最大化，進(jìn)而達(dá)到單位成本效益最高的目的。在模型求解方面，啟發(fā)式算法[2]、遺傳算法[3]、粒子群算法（PSO）[4]、量子粒子群算法（QPSO，quantumparticleswarmalgorithm）[5]等智能算法均被應(yīng)用于函數(shù)優(yōu)化問題的求解中。其中，粒子群算法因原理簡單、操作性強(qiáng)被廣泛應(yīng)用，但粒子群算法存在無法以概率為1進(jìn)行全局收斂的局限性[6]。為解決此問題，Sun等[7]和Wang等[8]提出具有量子行為的新型粒子群算法，即量子粒子群算法，該算法引入了吸引勢的概念，通過建立量子化的勢場對粒子進(jìn)行約束，從而實(shí)現(xiàn)粒子種群的聚集性，擴(kuò)大了粒子在空間的搜索范圍，提高收斂能力。但標(biāo)準(zhǔn)的量子粒子群算法由于后期粒子多樣性降低仍會存在過早收斂和全局尋優(yōu)不完美的情況。針對此問題，需對進(jìn)化因子和收縮擴(kuò)張系數(shù)兩方面進(jìn)行改進(jìn)，并將其應(yīng)用于初始航材優(yōu)化模型中。

1 模型建立

1.1 系統(tǒng)保障率模型

趙建忠等[1]提出改進(jìn)系統(tǒng)保障率模型，該模型從系統(tǒng)保障率定義出發(fā)結(jié)合基層級維修方式，得出第i種備件的保障率Pi滿足

其中：T為備件維修周期；Ni（T）是第i種備件維修周期（0，T）內(nèi)需要進(jìn)行更換的次數(shù)；Si（T）是第i種備件維修周期（0，T）內(nèi)的庫存量。而系統(tǒng)整體保障率可表示為

式中，n為備件種類數(shù)。

1.2 單位成本保障率最大模型

航空公司優(yōu)化航材購置是為了實(shí)現(xiàn)效益最大化，即每單位成本內(nèi)效益最大。因此在改進(jìn)系統(tǒng)保障率基礎(chǔ)上引入總成本變量，將單位成本內(nèi)系統(tǒng)保障率最大作為目標(biāo)函數(shù)值。構(gòu)建模型如下

T內(nèi)的航材需求量服從均值為λiT的泊松分布[9]，即

其中

其中：L是某機(jī)隊(duì)該機(jī)型飛機(jī)數(shù)量；H是該機(jī)型飛機(jī)每日平均飛行時數(shù)；Mi是第i種航材在每架飛機(jī)上的裝機(jī)數(shù)；MTBURi是第i種航材平均故障拆換時間。由泊松分布疊加性質(zhì)可知，整個系統(tǒng)的保障率為

2 算法描述

在1.2節(jié)的模型中，涉及的變量相對較多，且設(shè)備清單中涉及的航材種類較多。若采用邊際優(yōu)化算法計(jì)算相對復(fù)雜[10]，計(jì)算量大、迭代步驟多，因此，選擇智能算法進(jìn)行求解。

2.1 量子粒子群優(yōu)化算法

在量子力學(xué)基礎(chǔ)上發(fā)展出的量子粒子群的新算法[11]認(rèn)為，粒子具有量子的特點(diǎn)，即粒子的速度和位置不能同時確定，無需考慮速度因素，而是利用波函數(shù)描述位置，且其只有一個參數(shù)即收縮擴(kuò)張系數(shù)，與標(biāo)準(zhǔn)粒子群算法相比，該算法相對簡單、搜索速度較快、尋優(yōu)能力強(qiáng)。

在標(biāo)準(zhǔn)的粒子群算法中，最小勢能位置為

其中：N為種群規(guī)模；D為搜索空間的維數(shù)；γij（t）為均勻分布在[0，1]的隨機(jī)數(shù)；Ki為個體最優(yōu)；Kg為全局最優(yōu)。

利用蒙特卡羅法，在t次搜索后第t+1時所處的位置為

其中：ε為收縮擴(kuò)張系數(shù)；mbest為平均最優(yōu)搜索位置，即

個體最優(yōu)與全局最優(yōu)的更新方程如下其中，g（x）為適應(yīng)度函數(shù)。

2.2 改進(jìn)量子粒子群算法

針對量子粒子群存在過早收斂的問題，許多學(xué)者在量子粒子群基礎(chǔ)上做了一定改進(jìn)[9，12-14]。在傳統(tǒng)量子粒子群算法中，收縮擴(kuò)張系數(shù)ε是線性變化的，但在實(shí)際尋優(yōu)過程中往往是非線性的且具有較高的復(fù)雜度[15]，ε應(yīng)能根據(jù)尋優(yōu)過程實(shí)際變化而自適應(yīng)調(diào)整。種群粒子在尋優(yōu)過程中不斷向最優(yōu)位置靠攏，種群多樣性的減少會造成后期陷入局部尋優(yōu)。因此，引入進(jìn)化因子μt對mbest進(jìn)行動態(tài)化非線性調(diào)整。

2.2.1 收縮擴(kuò)張系數(shù)

收縮擴(kuò)張系數(shù)與傳統(tǒng)粒子群中的慣性權(quán)值相似，用于計(jì)算粒子的適應(yīng)度。引入動態(tài)權(quán)值，對收縮擴(kuò)張系數(shù)進(jìn)行動態(tài)化調(diào)節(jié)，可表示為

其中，εmax與εmin分別為ε的最大值與最小值。

在搜索初期迭代次數(shù)較少時，ε與εmax相近，可保證算法的全局尋優(yōu)搜索能力；隨著后期迭代次數(shù)遞增，ε以非線性變化遞減，可確保局部尋優(yōu)搜索能力。通過該方法靈活調(diào)整全局搜索能力與局部搜索能力間的變化，進(jìn)而實(shí)現(xiàn)一種動態(tài)平衡。

2.2.2 mbest的進(jìn)化因子

針對算法后期搜索易陷入局部最優(yōu)的問題，引入種群粒子最優(yōu)平均值mbest的進(jìn)化因子μt，即

其中：Kt（0，1）和Gt（0，1）分別為基于柯西分布和基于高斯分布在[0，1]范圍內(nèi)產(chǎn)生的隨機(jī)數(shù)；m1、m2為擾動因子，動態(tài)變化如下

其中：m1max、m1min、m2max、m2min分別為 m1、m2的最大值與最小值；tmax為更新次數(shù)的最大值。引入進(jìn)化因子后，種群粒子平均迭代最優(yōu)位置為

2.3 模型求解

算法求解過程如下：

1）初始化粒子群，并在標(biāo)準(zhǔn)算法基礎(chǔ)上引入式（13）和式（16），對傳統(tǒng)量子粒子群中參數(shù)進(jìn)行改進(jìn)；

2）計(jì)算出粒子適應(yīng)度值；

3）將新粒子的適應(yīng)度值對比當(dāng)前最優(yōu)值，若更優(yōu)則根據(jù)式（11）和式（12）進(jìn)行更新；

4）根據(jù)式（4）判斷各變量是否超出其取值范圍，若超出，即取其對應(yīng)的限制，防止其超出可行的搜索區(qū)域。

5）根據(jù)是否達(dá)到最大迭代次數(shù)判斷是否停止。

3 實(shí)例分析

以某航空公司使用的設(shè)備清單（表1）為例，驗(yàn)證算法有效性。分別采用PSO、標(biāo)準(zhǔn)QPSO、改進(jìn)QPSO 3種算法進(jìn)行求解，種群規(guī)模N為20，最大迭代次數(shù)為100，在改進(jìn)QPSO中引入收縮擴(kuò)張系數(shù)ε、進(jìn)化因子μt，基本參數(shù)與QPSO、PSO相同。仿真結(jié)果如表2和表3所示，適應(yīng)度曲線如圖1～圖3所示。從航材配置數(shù)量、購置成本和適應(yīng)度值來看：3種智能算法均優(yōu)于首期設(shè)備清（RSPL）計(jì)算結(jié)果，證明了優(yōu)化的必要性；QPSO和改進(jìn)QPSO結(jié)果優(yōu)于傳統(tǒng)PSO的計(jì)算結(jié)果，達(dá)到了優(yōu)化的效果。

表1 航材參數(shù)表Tab.1 Parameter list of aviation spare parts

表2 首期設(shè)備清單及不同算法航材配置數(shù)量對比Tab.2 First stage equipment list and number comparision of aviation spare parts by different algorithms個

分析QPSO與改進(jìn)QPSO的實(shí)驗(yàn)結(jié)果如下。在航材配置數(shù)量方面，兩者結(jié)果相近。在購置成本方面，改進(jìn)QPSO比QPSO節(jié)省了約一萬美元；在適應(yīng)度值方面，兩者的最大值相同均為1.78×10-6。因此，改進(jìn)QPSO實(shí)現(xiàn)了用更少的投入獲取更高的收益，達(dá)到了單位最大化的目的。從收斂速率來看，QPSO在38代左右，達(dá)到最大值，此后穩(wěn)定不變，未出現(xiàn)局部收斂和不收斂的情況，而改進(jìn)QPSO在適應(yīng)度最大值相同的情況下，迭代速率有明顯的提升。

表3 不同算法優(yōu)化結(jié)果對比Tab.3 Optimized result comparision of different algorithms

圖1 PSO適應(yīng)度曲線Fig.1 PSO fitness curve

圖2 QPSO適應(yīng)度曲線Fig.2 QPSO fitness curve

圖3 改進(jìn)QPSO適應(yīng)度曲線Fig.3 Improved QPSO fitness curve

4 結(jié)語

針對量子粒子群優(yōu)化算法在優(yōu)化配置中存在過早收斂和全局尋優(yōu)能力不完美的情況，從收縮擴(kuò)張系數(shù)和進(jìn)化因子方面進(jìn)行改進(jìn)。在目標(biāo)函數(shù)中引入總成本變量，構(gòu)造出單位成本系統(tǒng)保障率最大模型，將改進(jìn)的量子粒子群應(yīng)用在航材初始備件配置優(yōu)化領(lǐng)域中。通過實(shí)驗(yàn)得出，改進(jìn)的量子粒子群的結(jié)果要優(yōu)于傳統(tǒng)粒子群（PSO）及首期設(shè)計(jì)清單中的結(jié)果，在收斂速率上優(yōu)于QPSO，提高了優(yōu)化效率，同時節(jié)省總的購置成本，可為航空公司在制定首期設(shè)備采購策略時提供參考。