金 琦 蔣 敏 宋子健

(1.火箭軍工程大學 西安 710025)(2.66109部隊 北京 100044)

?

多目標智能規(guī)劃算法研究*

金 琦1蔣 敏1宋子健2

(1.火箭軍工程大學 西安 710025)(2.66109部隊 北京 100044)

為了解決多目標規(guī)劃難的問題，論文在闡述了相關問題的基礎上，首先對多目標規(guī)劃方法進行了描述；而后設計完成了GAPS-MMA算法，對其算法的主要部分，即適應度值的計算和Pareto解集的更新進行了重點研究，給出了GAPS-MMA算法流程；最后，以某飛行器航跡規(guī)劃為例，運用GAPS-MMA算法與模擬退火算法進行對比分析，得到了更好的全局最優(yōu)解。通過算例證明， GAPS-MMA算法是更為科學的、合理的。

多目標; 智能規(guī)劃; 進化算法; GAPS-MMA

Class Number TN99

1 引言

多目標優(yōu)化問題中各目標之間通過決策變量相互制約，對其中的一個目標優(yōu)化必須以犧牲其他目標作為代價，而且各目標的物理意義往往又不一致，因此很難評價多目標問題解的優(yōu)劣性[1～3]。與單目標優(yōu)化問題的本質區(qū)別在于，多目標優(yōu)化問題的解不是惟一的，而是存在一個最優(yōu)解集合，即Pareto最優(yōu)解集[4～5]。Pareto最優(yōu)解集中的元素，就所有目標而言是彼此不可比較的。

在過去的二十年中，進化算法(Evolutionary Algorithms，EA)[6～8]作為多目標優(yōu)化問題新的求解方法受到了廣泛關注。同時，作為一種概率性算法，進化算法應用于多目標優(yōu)化問題時，基于模式定理而非梯度信息產生群體中的最優(yōu)(滿意)個體，不像其他傳統(tǒng)的精確算法那樣對目標函數和約束條件有諸多限制。基于進化計算的多目標優(yōu)化方法大致分為三類[9～12]：經典的求解多目標優(yōu)化進化算法，非聚合、非基于Pareto占優(yōu)的多目標優(yōu)化進化算法，基于Pareto占優(yōu)的多目標優(yōu)化進化算法。這三種方法均是針對連續(xù)型多目標優(yōu)化問題，對于本文探討的多約束多目標非線性任務規(guī)劃問題無法直接適用，需要設計滿足其獨特需求的進化算法。基于這樣的指導思想，本文提出了多個任務規(guī)劃目標情形下的基于Pareto解集的遺傳進化算法(Genetic Algorithm based Pareto Set for Multi-objective Mission-planning Algorithm，GAPS-MMA)。

2 多目標任務規(guī)劃描述

通常對于任務規(guī)劃而言，一般涉及三個任務規(guī)劃指標：任務完成風險度最小指標F1、任務完成時間最短指標F2以及任務資源消耗最少指標F3。其中，對于規(guī)劃指標F3的理解可基于兩方面的認識：一方面，可以在要求任務完成風險度最小的情形下，追求任務資源消耗最少，規(guī)劃指標等同于F1∪F3；另一方面，可以在要求任務完成時間最短的情形下，追求任務資源消耗最少，規(guī)劃指標等同于F2∪F3。所以，規(guī)劃指標F3一定程度上表現為多目標規(guī)劃的形式。綜上，多目標任務規(guī)劃可歸結為以下幾種情形，如表1所示。

表1 不同情形下的多目標任務規(guī)劃方法

由上表可以看出，第二種規(guī)劃情形只需在第一種規(guī)劃情形上應用枚舉法即可解決，因此，多目標任務規(guī)劃著重在于解決第一種情形，即任務完成風險度和任務完成時間的組合問題。同時，對于多目標的任務規(guī)劃問題，主體算法重點在于適應度值計算以及規(guī)劃解集的選擇更新，下面重點對這兩方面進行詳細論述，其它次要部分不再贅述。

3 多目標智能規(guī)劃算法

3.1 適應度值計算

(1)

s(Xi)=|S(Xi)|

(2)

其中|·|表示集合的規(guī)模。

2) 最近鄰密度信息d(Xi)

由于個體Xi的Pareto占優(yōu)數是按照弱占優(yōu)關系計算的，當Pareto解集中兩個個體的Pareto占優(yōu)數相同時，最近鄰密度信息可進一步刻畫兩個個體在更細節(jié)層次上的優(yōu)劣關系。最近鄰密度概念來源于Zitzler和Thiele的改進SPEA算法。

(3)

(4)

3.2 Pareto解集更新

主要從三個方面來獲取Pareto最優(yōu)解：Pareto占優(yōu)關系、最近鄰密度信息以及相鄰個體的歐式距離。首先基于個體的Pareto占優(yōu)關系，將非劣解放入Pareto解集中。如果Pareto解集規(guī)模超過限制，則采用如下的裁剪方法：

1) 基于個體的最近鄰密度信息，裁剪較劣個體；

2) 如果最近鄰密度信息仍然不能確定兩個個體的優(yōu)劣關系時，則采用臨近排擠算法對較劣個體進行裁剪。具體步驟為：

(3)找出歐式距離最短的兩相鄰個體Xj和Xj+1；

(4)比較dj-1和dj+1的大小。若dj-1dj+1，則裁剪個體Xj+1；

3) 當上述方法仍然不能確定非劣解個體的優(yōu)劣關系時，則隨機選擇各層次上適應度相同的解個體予以裁剪。

Step 2：生成第t+1代外部Pareto解集：

3.3 GAPS-MMA算法流程

綜上所述，建立多個任務規(guī)劃目標情形下的任務規(guī)劃算法如下：

Step 1：輸入任務規(guī)劃信息；

Step 2：設置任務規(guī)劃目標：F1∪F2；

Step 3：設置遺傳算法控制參數以及結束條件(在此為最大迭代次數T)；

Step 5：按照傳統(tǒng)染色體解碼算法和初始種群生成算法隨機生成初始種群P0；

Step 9：依據適應度計算公式計算種群P″t中個體的適應度值；

Step 10.1：初始化Pt+1=φ

Step 10.2：Fori=1 to Sizepop，do

Step 11:t=t+1。如果t>T或者滿足其他結束條件，進入下一步，否則，轉入Step6；

4 算例

以某飛行器航跡規(guī)劃為例，其目標主要有兩個，即飛行風險小和時間短(飛行距離短)。

在水平區(qū)域為600km×600km的規(guī)劃空間中，采用地形高程數據進行實驗，圖1、圖2分別為數字地圖的三維顯示圖和數字地圖的等高線圖。為了后續(xù)方便展示規(guī)劃結果，結合飛行器航跡實際情況，采用簡圖形式展示。

圖1 數字地圖的三維顯示

圖2 數字地圖的等高線圖

飛行器起始點的平面坐標為(60，60)，目標點的平面坐標為(600，480)，干擾源平面坐標分別為(300，200)、(500，400)。以邊長為60km的網格對規(guī)劃空間進行劃分，每個網絡節(jié)點的地形高程為其所包含區(qū)域中所有地形高程的平均值。

通過仿真計算，分別給出模擬退火算法和GAPS-MMA算法在不同情況下的多目標規(guī)劃方案如下：

情況一：在僅考慮航跡長度(時間最短)的影響下，模擬退火算法和GAPS-MMA算法分別給出最優(yōu)航跡如圖3所示，虛線表示GAPS-MMA算法給出的規(guī)劃航跡，實線表示模擬退火算法給出的規(guī)劃航跡。

圖3 考慮航跡長度影響的全局最優(yōu)航跡平面簡圖

情況二：在僅考慮風險的影響下，最優(yōu)航跡應盡可能遠離威脅，模擬退火算法和GAPS-MMA算法分別給出最優(yōu)航跡如圖4所示。

圖4 考慮風險影響的全局最優(yōu)航跡簡圖

情況三：綜合考慮兩種因素的影響，得到全局最優(yōu)規(guī)劃結果為三種情況，如圖5所示。

從以上仿真實驗可以看出，由GAPS-MMA算法得到的結果是更為合理的，能夠在全局范圍內確定出最優(yōu)航跡，所用規(guī)劃時間不超過3s。同時，這些最優(yōu)航跡結果較為穩(wěn)定，具有一定的魯棒性，由此確定的全局最優(yōu)航跡的范圍是正確可靠的，也證明，對于多目標規(guī)劃而言，GAPS-MMA算法是更科學合理的。

圖5 考慮時間和風險兩種影響的全局最優(yōu)航跡簡圖

5 結語

對于多目標規(guī)劃而言，很難得到多目標規(guī)劃問題的最優(yōu)解，進化算法給出了解決問題的新思路。本文在闡述了相關問題的基礎上，首先對多目標規(guī)劃方法進行了描述；而后設計完成了GAPS-MMA算法，對其算法的主要部分，即適應度值的計算和Pareto解集的更新進行了重點研究，給出了GAPS-MMA算法流程；最后，以某飛行器航跡規(guī)劃為例，運用GAPS-MMA算法與模擬退火算法進行對比分析，得到了更好的全局最優(yōu)解。通過算例證明， GAPS-MMA算法是更為科學的、合理的。

[1] 任曉莉.LSO改進CGA解決多目標作業(yè)車間調度問題[J].計算機應用與軟件,2015,32(3):60-64. REN Xiaoli. IMPROVING CGA BY LSO FOR MULTIPLE-OBJECTIVE JOB SHOP SCHEDULING PROBLEM[J]. Computer Applications and Software,2015,2(3):60-64.

[2] Tan Y, Zhu Y. Fireworks algorithm for optimization[C]// Berlin: Springer,2010:355-364.

[3] 王培崇,高文超,錢旭,等.應用精英反向學習的混合煙花爆炸優(yōu)化算法[J].計算機應用,2014,34(10):886-2890. WANG Peichong, GAO Wenchao, QIAN Xu, et al. Hybrid fireworks explosion optimization algorithm using elite opposition-based learning[J]. Journal of Computer Applications,2014,34(10):886-2890.

[4] 陳剛.飛行航線的自動規(guī)劃方法研究[D].長沙:國防科技大學,2010.CHEN Gang. Study on the method of flight path automatic planning[D]. Changsha: National University of Defense Technology,2010.

[5] 潘全科.智能制造系統(tǒng)多目標車間調度研究[D].南京:南京航空航天大學,2013. PAN Quanke. Research on multi objective job shop scheduling in Intelligent Manufacturing System[D]. Nanjing: Doctoral Dissertation of Nanjing University of Aeronautics & Astronautics,2013.

[6] 劉衍民,隋常玲,牛奔.解決約束優(yōu)化問題的改進粒子群算法[J].計算機工程與應用，2011,47(12):23-26. LIU Yanmin, SUI Changling, NIU Ben. Improved particle swarm optimizer for constrained optimization problems[J]. Computer Engineering and Applications,2011,47(12):23-26.

[7] 葉媛媛.多UCAV協(xié)同任務規(guī)劃方法研究[D].長沙:國防科技大學,2010. YE Yuanyuan. Research on multi UCAV cooperative task planning method[D]. Changsha: National University of Defense Technology,2010.

[8] 劉長平,葉春明.基于邏輯自映射的變尺度混沌粒子群優(yōu)化算法[J].計算機應用研究,2011,28(8):2825-2827. LIU Changping ,YE Chunming. Mutative scale chaos particle swarm optimization algorithm based on self logical mapping function[J]. Application Research of Computers,2011,28(8):2825-2827.

[9] 譚營,鄭少秋.煙花算法研究進展[J].智能系統(tǒng)學報,2014,9(5):515-528. TAN Ying, ZHENG Shaoqiu. Recent advances in fireworks algorithm[J]. CAAI Transactions on Intelligent Systems,2014,9(5):515-528.

[10] Coello Coello C A, Lechuga M S. MOPSO: a proposal for multiple objective particle swarm optimization[M]. Washington DC: IEEE,2012:1051-1056.

[11] 程臨燕,張保會,郝治國,等.基于綜合靈敏度分析的快速控制算法研究[J].電力自動化設備,2011,29(4):46-49. CHENG Linyan, ZHANG Baohui, HAO Zhiguo, et al. Fast control algorithm based on integrative sensitivity analysis[J]. Electric Power Automation Equipment,2011,29(4):46-49.

[12] 覃朝勇,劉向,鄭建國.求解多目標job-shop生產調度問題的量子進化算法[J].計算機應用研究,2010,27(3):849-852. QIN Chaoyong, LIU Xiang, ZHENG Jianguo. Quantum-inspired evolutionary algorithm for multi-objective job-shop scheduling[J]. Application Research of Computers,2010,27(3):849-852.

Multi-objective Intelligent Planning Algorithm

JIN Qi1JIANG Min1SONG Zijian2

(1. Rocket Force Engineering University, Xi’an 710025)(2. No. 66109 Troops of PLA, Beijing 100044)

In order to solve the difficult problem of multi-objective planning, on the basis of introducing of relevant issues, firstly the paper describes multi-objective planning methods, then GAPS-MMA (Genetic Algorithm based Pareto Set for Multi-objective Mission-planning Algorithm) is completed, the main part of the algorithm, namely computing fitness value and updating Pareto sets are focused on research, and the process of GAPS-MMA is given. Finally, an air vehicle route planning for example is taken, through the comparison for GAPS-MMA and SA (simulated annealing algorithm), the better global optimal solution is gotten by GAPS-MMA. It is proved that GAPS-MMA algorithm is more scientific and reasonable by the example.

multi-objective, intelligent planning, evolutionary algorithm, GAPS-MMA

2016年5月12日,

2016年6月14日

金琦，女，研究方向：通信工程。蔣敏，女，研究方向：通信工程。宋子健，男，工程師，研究方向：電子工程。

TN99

10.3969/j.issn.1672-9722.2016.11.014