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

金 琦 蔣 敏 宋子健

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

?

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

金 琦1蔣 敏1宋子健2

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

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

多目標(biāo); 智能規(guī)劃; 進(jìn)化算法; GAPS-MMA

Class Number TN99

1 引言

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

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

2 多目標(biāo)任務(wù)規(guī)劃描述

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

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

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

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

3.1 適應(yīng)度值計(jì)算

(1)

s(Xi)=|S(Xi)|

(2)

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

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

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

(3)

(4)

3.2 Pareto解集更新

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

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

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

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

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

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

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

3.3 GAPS-MMA算法流程

綜上所述，建立多個(gè)任務(wù)規(guī)劃目標(biāo)情形下的任務(wù)規(guī)劃算法如下：

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

Step 2：設(shè)置任務(wù)規(guī)劃目標(biāo)：F1∪F2；

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

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

Step 9：依據(jù)適應(yīng)度計(jì)算公式計(jì)算種群P″t中個(gè)體的適應(yīng)度值；

Step 10.1：初始化Pt+1=φ

Step 10.2：Fori=1 to Sizepop，do

Step 11:t=t+1。如果t>T或者滿足其他結(jié)束條件，進(jìn)入下一步，否則，轉(zhuǎn)入Step6；

4 算例

以某飛行器航跡規(guī)劃為例，其目標(biāo)主要有兩個(gè)，即飛行風(fēng)險(xiǎn)小和時(shí)間短(飛行距離短)。

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

圖1 數(shù)字地圖的三維顯示

圖2 數(shù)字地圖的等高線圖

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

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

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

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

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

圖4 考慮風(fēng)險(xiǎn)影響的全局最優(yōu)航跡簡圖

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

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

圖5 考慮時(shí)間和風(fēng)險(xiǎn)兩種影響的全局最優(yōu)航跡簡圖

5 結(jié)語

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

[1] 任曉莉.LSO改進(jìn)CGA解決多目標(biāo)作業(yè)車間調(diào)度問題[J].計(jì)算機(jī)應(yīng)用與軟件,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īng)用精英反向?qū)W習(xí)的混合煙花爆炸優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用,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] 陳剛.飛行航線的自動(dòng)規(guī)劃方法研究[D].長沙:國防科技大學(xué),2010.CHEN Gang. Study on the method of flight path automatic planning[D]. Changsha: National University of Defense Technology,2010.

[5] 潘全科.智能制造系統(tǒng)多目標(biāo)車間調(diào)度研究[D].南京:南京航空航天大學(xué),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ìn)粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用，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é)同任務(wù)規(guī)劃方法研究[D].長沙:國防科技大學(xué),2010. YE Yuanyuan. Research on multi UCAV cooperative task planning method[D]. Changsha: National University of Defense Technology,2010.

[8] 劉長平,葉春明.基于邏輯自映射的變尺度混沌粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究,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ìn)展[J].智能系統(tǒng)學(xué)報(bào),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] 程臨燕,張保會(huì),郝治國,等.基于綜合靈敏度分析的快速控制算法研究[J].電力自動(dòng)化設(shè)備,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] 覃朝勇,劉向,鄭建國.求解多目標(biāo)job-shop生產(chǎn)調(diào)度問題的量子進(jìn)化算法[J].計(jì)算機(jī)應(yīng)用研究,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