劉劍英，楊文艷，劉丹丹

(1.大連職業(yè)技術學院 信息工程學院，遼寧 大連 116035；

2. 黑龍江科技大學 電氣與控制工程學院，哈爾濱 150022)

?

基于混沌映射協(xié)同差分進化的最優(yōu)路徑規(guī)劃

劉劍英1，楊文艷1，劉丹丹2

(1.大連職業(yè)技術學院 信息工程學院，遼寧 大連 116035；

2. 黑龍江科技大學 電氣與控制工程學院，哈爾濱 150022)

摘要：為提高軌跡優(yōu)化的精度，提出一種基于混沌映射的協(xié)同差分進化算法。該模型不依賴數(shù)學模型和梯度信息，即可對優(yōu)化目標進行分組尋優(yōu)和信息共享，實現(xiàn)快速軌跡優(yōu)化。在尋優(yōu)后期的子代構建過程中引入混沌映射，使算法在保持種群多樣性的同時，平衡了全局搜索能力和局部搜索能力。通過標準函數(shù)對比測試，所提算法在全局尋優(yōu)能力方面取得明顯的改進效果，將其應用于解決軌跡優(yōu)化的實際問題，可以高效地獲得全局最優(yōu)軌跡，有效地提升差分進化算法的性能。

關鍵詞：差分進化；協(xié)同進化；軌跡優(yōu)化；混沌映射

最優(yōu)路徑規(guī)劃軌跡優(yōu)化是運動控制領域中的一個重要分支，在大型礦井中最優(yōu)路徑規(guī)劃等領域得到廣泛的應用[1]?？傮w目標是使物體運動到指定目標位置，并且不碰到障礙物，與此同時路徑最短或耗時最少[2]。自由空間法[3]是其中最經典的方法，該方法將環(huán)境空間分為自由空間和障礙物空間兩部分，然后采用搜索策略在自由空間中找到一條較優(yōu)的軌跡，但其計算復雜度受到障礙物數(shù)目的影響，不能保證每次獲得最優(yōu)軌跡。隨著遺傳算法、群體智能計算算法等方法的發(fā)展，軌跡優(yōu)化領域也獲得進步[4-5]。

差分進化(Differential Evolution, DE)算法是于1995年為了求解切比雪夫多項式而提出來的一種采用浮點矢量編碼在連續(xù)空間中進行隨機搜索的優(yōu)化算法[6]。該算法的原理簡單，受控參數(shù)少，實施隨機、并行、直接的全局搜索，易于理解和實現(xiàn)[7-9]。近20年里差分進化算法在自適應控制[10]、遙感圖像處理[11-13]等領域得到深入研究。Qu等[14]利用鄰域突變特性改進差分進化算法，并將其應用于多峰函數(shù)優(yōu)化。焦李成等[15]提出一種基于差分進化的多目標優(yōu)化算法，提高了算法的均勻性和寬廣性。向萬里等[16]提出高效率反向差分進化算法，改進變異搜索方程，獲得了較好的收斂精度和速度。在模糊聚類中也可以使用差分進化框架進行有效的初始化[17]。然而由于差分進化算法是根據父代個體間的差分矢量進行變異、交叉和選擇操作的，因此，它與其他群體智能算法一樣存在早熟收斂現(xiàn)象。此外，差分進化在尋優(yōu)過程后期，收斂速度會明顯減慢。

本文提出一種基于混沌映射的協(xié)同差分進化算法，將待優(yōu)化進行有效分組，然后進行信息共享，提高搜索效率。在尋優(yōu)后期引入混沌映射機制，提高群體的多樣性，從而提高優(yōu)化結果。最終將其應用于實際最優(yōu)路徑規(guī)劃問題中，分析其有效性。

1差分進化算法

差分進化算法是通過引入差分變異算子進行迭代的隨機算法。首先隨機生成初始種群，再利用當前群體中的個體差異構造變異個體，并與第3個隨機選擇的個體向量進行加權加和，隨后將以一定的概率進行雜交生產試驗矢量。若試驗矢量優(yōu)于目標矢量，則將較優(yōu)個體矢量保持到下一代。通過逐步迭代尋找到最優(yōu)結果。差分進化算法一般包括如下4個基本操作：

步驟1隨機初始化

利用均勻隨機分布的方法產生初始種群xij：

xij,1=xjmin+rand×(xjmax-xjmin),

i=1,2,…,NP,j=1,2,…,D

(1)

式中，rand為[0,1]之間的隨機數(shù)，xjmin和xjmax分別為第j個變量的下界和上界，NP為種群規(guī)模，D為優(yōu)化問題的維數(shù)。NP越大，種群多樣性越強，獲得最優(yōu)解的概率越大。

步驟 2差分變異策略

變異矢量定義為

DG=xr1,G-xr2,G，

(2)

式中，G為進化代數(shù)，r1，r2分別為不同的索引號。將差分矢量隨機疊加另外一個個體矢量上，實現(xiàn)變異操作如下：

vi,G+1=xr1,G+F×(xr2,G-xr3,G) ，

(3)

式中，r1，r2，r3和i為[1,2,…,NP]中表示3個不同個體，F(xiàn)為變異因子。

步驟 3交叉操作

將群體中的目標矢量個體xi,G與變異矢量vi,G+1進行交叉操作，產生試驗矢量個體ui,G+1：

(4)

式中， rand(j)為[0,1]間的隨機數(shù)；CR為交叉概率因子，取值范圍為[0,1]；randn(i)為[1,2,…,D]之間的隨機整數(shù)。為保證矢量xi,G能夠進化，必須使得ui,G+1中至少有一位由vi,G+1貢獻。

步驟 4選擇策略

通過目標函數(shù)進行試驗矢量ui,G+1和目標矢量xi,G的選擇：

(5)

這里f為目標函數(shù)。若ui,G+1的目標函數(shù)值小于xi,G的目標函數(shù)值，則由ui,G+1替代目標矢量xi,G；反之，則保留xi,G生成新矢量，迭代計算直至符合停止條件。

2基于混沌映射的協(xié)同差分進化算法

為了提高差分進化算法的優(yōu)化能力，構造協(xié)同進化框架，將待優(yōu)化問題進行拆分，然后在每個組內利用混沌映射差分進化算法進行快速尋優(yōu)，之后進行信息共享。

2.1　協(xié)同進化框架

在協(xié)同進化(CooperativeCoevolution,CC)框架中，首先對待優(yōu)化問題進行隨機初始化，令最大迭代次數(shù)為Tmax，迭代次數(shù)變量time=0，種群數(shù)目NP，每組內的最大迭代次數(shù)T1，整個循環(huán)的分組內當前循環(huán)次數(shù)k=0，進而設定交叉概率因子CR和變異因子F。在整個循環(huán)過程中，首先對待優(yōu)化進行隨機分組，拆分成L個小組，分別利用混沌映射差分進化算法(ChaosMappingDifferentialEvolution,CMDE)在小組內進行尋優(yōu)。之后將各個位置矢量信息進行共享，構建整體矢量，對目標函數(shù)進行比較，獲得最優(yōu)個體，循環(huán)迭代直至算法收斂停止。協(xié)同進化模式可以提高并行計算速度，對大規(guī)模模型參數(shù)優(yōu)化具有較好的優(yōu)勢。在利用計算機進行模擬優(yōu)化的過程中，可以采用圖形圖像處理單元(GraphicProcessingUnit，GPU)進行硬件上的并行處理分析。通過ComputeUnifiedDeviceArchitecture(CUDA)統(tǒng)一編程平臺，利用cudaMalloc和cudaMemcpy命令將GPU計算所需要的參數(shù)設定等數(shù)據讀入到顯存中，采用NCVV生成設備端代碼。采用Kernel程序為每一個分組建立一個線程塊。每個線程代表一個矢量，計算每個矢量的目標函數(shù)值，通過每個Block中的共享內存，記錄每個矢量的當前位置信息，從而實現(xiàn)組內每個Thread的信息共享和交互，完成變異、交叉和選擇的操作，實現(xiàn)子問題的有效快速尋優(yōu)。當分組尋優(yōu)之后，滿足全局停止條件，將全部結果返回主機內存，獲得全局最優(yōu)位置，提高算法的計算效率。

2.2　 混沌映射矢量變異

混沌運動獨有的特征表現(xiàn)為：有界性、遍歷性、隨機性、分維性、標度性、普適性和統(tǒng)計特征。

定義1混沌定義。 [a,b]上的連續(xù)自映射f稱為是混沌的，若其滿足：

(1)f的周期點無上界；

(2)存在不可數(shù)子集S?[a,b]，S中無周期點，且滿足：

①對任意x,y∈S，有

②對任意x,y∈S，有

③對任意x∈S和f的任意周期點y，有

基于混沌映射協(xié)同差分進化算法的流程如圖1。

基于混沌映射協(xié)同差分進化算法首先進行初始化設定，然后對待優(yōu)化參數(shù)隨機分組，在每個組內采用混沌映射差分進化算法開始分組尋優(yōu)，通過信息交互之后，返回上層循環(huán)迭代，直至算法收斂。差分進化算法在尋優(yōu)后期過程中個體差異減弱，整個算法的尋優(yōu)能力會大幅度的下降，出現(xiàn)“早熟”的現(xiàn)象，所以為了保證軌跡優(yōu)化過程中搜索的尋優(yōu)成功概率，就要充分利用混沌映射的遍歷性來提高矢量群體的多樣性。

圖1　基于混沌映射協(xié)同差分進化算法流程圖

為進一步確定矢量子代重構標準，對第j個分組內的多樣性定義為

(6)

式中，S為分組內的矢量個數(shù)，R為各矢量之間的位置距離。當diversity<ε時，進行子代矢量重構。另一方面采用目標函數(shù)變化閾值分析，獲得子代重構的判定標準：

f(xn)-f(xn+1)≤ε 。

(7)

當目標函數(shù)變化小于ε時，采用混沌重構模式。采用Chebyshev混沌映射，其迭代方程為

xn+1=cos(μacos(xn)),xn∈[-1,1]，

(8)

令μ=4，數(shù)據序列處于混沌狀態(tài)。

當目標函數(shù)變化小于ε時，采用混沌重構模式，對矢量中的每一維數(shù)據加入混沌變異量，產生NP×D 個混沌隨機序列，建立對應矩陣

(9)

然后將混沌隨機矩陣賦值于xi,j，產生遷移位置量：

(10)

式中，[xjmin,xjmax]為矢量個體的取值范圍，將其加入到原始矢量中，得到新的群體：

(11)

式中，λ為[0,1]之間的混沌映射編譯比例系數(shù)，控制矢量混沌遷移的大小。在每個分組內的混沌映射差分進化算法的偽代碼如下：

Start

initializethepopulation

evaluatethefitness: = f(x)

While(terminationcondition=false)

Do

Mutation,cross,chooseprocessusing(3), (4)and(5),respectively;

Evaluatethediversityandthechangeoffitnessfunctionusing(6)and(7),respectively;

IF(reconstructcondition=ture)

Calculatechaossequenceandreconstructthevectorsusing(8)-(11);

EndIF

EndDo

End

3基于CMDE-CC的最優(yōu)路徑規(guī)劃

本研究主要探索運動物體無碰撞且軌跡最短的多目標最優(yōu)路徑規(guī)劃。在軌跡長度方面，可以通過歐幾里得距離而得到長度能量函數(shù)——長度能量函數(shù)值越小，軌跡長度越短；無碰撞方面，可以通過碰撞罰函數(shù)來約束——碰撞罰函數(shù)值越小，碰撞的可能性越小，當碰撞罰函數(shù)的值小于一定閾值時，表示軌跡無碰撞。因此，多目標最優(yōu)路徑規(guī)劃的目標函數(shù)可以表示為長度能量函數(shù)和碰撞罰函數(shù)兩部分的加權和：

E=wEl+(1-w)Ec，

選擇起始點和目標點連線上均勻分布的點向量作為初始最優(yōu)個體，然后再進一步進化尋優(yōu)。整個流程如圖2。

當最優(yōu)解經過一定代數(shù)后沒有發(fā)生變化或變化不大，而且碰撞罰函數(shù)大于一定閾值時，對群體中所有個體進行混沌映射重構，隨后進行變異、交叉和選擇操作。

圖2　基于CMDE-CC最優(yōu)路徑規(guī)劃流程圖

4仿真分析

為驗證所提CMDE-CC算法的有效性，選用4個標準測試函數(shù)進行比較不同差分進化算法的有效性。此外，通過最優(yōu)路徑規(guī)劃模擬實驗進行數(shù)據對比分析。

4.1　標準函數(shù)測試

為了驗證所提CMDE-CC算法的有效性，選擇4個不同類型的標準測試函數(shù)進行分析，這些函數(shù)有單峰的、多峰的、連續(xù)的、非連續(xù)的和不可導的，從而充分驗證所提算法的適應性。

標準函數(shù)1：Sphere函數(shù)

(12)

標準函數(shù)2：Ackley‘s函數(shù)

(13)

標準函數(shù)3：Griewank’s函數(shù)

(14)

標準函數(shù)4：復合函數(shù)

f1,…,f10:GriewankFunction

[σ1,…,σ10]=[1,…,1]

[λ1,…,λ10]=[5/100,…,5/100]。

(15)

在仿真實驗中令維數(shù)D分布為100，1 000，其他參數(shù)L=10，F(xiàn)=0.5，CR=0.9，NP=100，T1=3 000和Tmax=3 000D。每次實驗重復20次，記錄其平均值和方差。為了驗證所提算法CMDE-CC的有效性，仿真中與經典差分進化算法(DE)和協(xié)同差分進化算法(DE-CC)進行比較，仿真結果平均值和方差分別見表1和表2。從數(shù)據中可以看出，本文提出的CMDE-CC算法在大部分平均最優(yōu)值和標準差上精度都有所提高，說明該算法不僅尋優(yōu)能力更強，而且具有更高的穩(wěn)定性。

表1　函數(shù)優(yōu)化平均值結果

表2　函數(shù)優(yōu)化方差結果

4.2　最優(yōu)路徑規(guī)劃

采用CMDE-CC算法作為搜索算法，即計算出式(10)的一系列軌跡節(jié)點pi,i=1,…,D的位置坐標，采用直角坐標系，故其每個軌跡節(jié)點的位置坐標用(xi,yi)來表示，待優(yōu)化的個體參數(shù)矢量可以表示為

xi=[(x1,y1),…,(xi,yi),…,(xD,yD)] 。

(16)

可以看出軌跡節(jié)點數(shù)越多，得到的軌跡越精確，但是相應所花費的時間也就越長。為了保證精確度，本文中取15個節(jié)點，即D=15。為了簡化運動物體的模型，本文將運動物體視為質點。CMDE-CC的參數(shù)設置為：D=15，NP=100，F(xiàn)=0.5，CR=0.9，n=5，λ=0.3，g=0.001，Tmax=500，T1=100，L=3。目標函數(shù)中，w=0.001，起始點坐標p1=[5,5]，目標點坐標pm=[95,95]。路徑迭代優(yōu)化過程中函數(shù)變化曲線如圖3。

(a)目標函數(shù)變化曲線

(b)長度能量函數(shù)變化曲線

從圖3(a)可以看出，CMDE-CC算法在大約40步的時候就已經收斂，而且是全局最優(yōu)，軌跡長度也是所有可行軌跡中最短的，且沒有與障礙物發(fā)生碰撞(如圖3(b))，即軌跡優(yōu)化成功。經過CMDE-CC優(yōu)化得到的最優(yōu)路徑規(guī)劃結果如圖4。

(a)原始最優(yōu)路徑

(b)經過差值平滑處理的最優(yōu)路徑

圖4(a)為最終得到的最優(yōu)軌跡，圖4(b)將所得最優(yōu)軌跡經過簡單的三次樣條插值處理，得到速度與加速度均沒有跳變的符合運動學約束的平滑可行軌跡，獲得較好的結果。

5結語

本文提出的基于混沌映射協(xié)同差分進化算法，不依賴具體問題數(shù)學模型，將待優(yōu)化問題進行隨機分解，然后進行分組學習和信息共享，當維數(shù)較高時優(yōu)化效果的改進程度更加明顯。此外，在算法的后期引入混沌映射，提高了種群的多樣性和算法的優(yōu)化能力，在最優(yōu)路徑規(guī)劃的應用中快速準確地尋找到最優(yōu)路徑，充分驗證了模型的有效性。

參考文獻：

[1] XIA Q L, GUO T, QI Z K. Study of trajectory optimization using terminal-node adaptive-altered spline algorithm [J]. Journal of Systems Engineering and Electronics, 2009, 20(3): 551-557.

[2] KUWATA Y, HOW J P. Cooperative distributed robust trajectory optimization using receding horizon MILP [J]. IEEE Transactions on Control Systems Technology, 2011, 19(2): 423-431.

[3] ALEXOPOULOS C, GRIFFIN P M. Path planning for a mobile robot [J]. IEEE Transactions on Systems Man and Cybernerics, 1992, 22(2): 318-322.

[4] VASILE M, MINISCI E, LOCATELLI M. An inflationary differential evolution algorithm for space trajectory optimization [J]. IEEE Transactions on Evolutionary Computation, 2011, 15(2): 267-281.

[5] FU Y G, DING M Y, ZHOU C P, et al. Route planning for unmanned aerial vehicle (UAV) on the sea using hybrid differential evolution and quantum-behaved particle swarm optimization [J]. IEEE Transactions on Systems Man and Cybernetics: Systems, 2013, 43(6): 1451-1465.

[6] RAINER S, KENNETH P. Differential Evolution-A simple and efficient adaptive scheme for global optimization over continuous spaces [R]. Technical report International Computer Science Institute, Berkeley, California, USA , 1995.

[7] 劉劍英. 基于GPU的并行協(xié)同差分進化算法研究[J]. 計算機工程與應用, 2012, 48(7): 48-50.

[8] FAN Q Q, YAN X F. Self-adaptive differential evolution algorithm with discrete mutation control parameters [J]. Expert Systems with Applications, 2015, 42(3): 1551-1572.

[9] 董麗麗, 黃賁, 介軍. 云計算中基于差分進化算法的任務調度研究[J]. 計算機工程與應用, 2014, 50(5): 90-95.

[10] GUO H X, LI Y N, LI J L, et al. Differential evolution improved with self-adaptive control parameters based on simulated annealing [J]. Swarm and Evolutionary Computation, 2014, 19: 52-67.

[11] ZHONG Y F, ZHANG S, ZHANG L P. Automatic fuzzy clustering based on adaptive multi-objective differential evolution for remote sensing imagery [J]. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 2013, 6(5): 2290-2301.

[12] ZHONG Y F, ZHANG L P. Remote sensing image subpixel mapping based on adaptive differential evolution [J]. IEEE Transactions on Systems Man and Cybernetics, Part B: Cybernetics, 2012, 42(5): 1306-1329.

[13] BAZI Y, ALAJLAN N, MELGANI F, et al. Differential evolution extreme learning machine for the classification of hyperspectral images [J]. IEEE Geoscience and Remote Sensing Letters, 2014, 11(6): 1066-1070.

[14] QU B Y, SUGANTHAN P N, LIANG J J. Differential evolution with neighborhood mutation for multimodal optimization [J]. IEEE Transactions on Evolutionary Computation, 2012, 16(5): 601-614.

[15] 劉若辰, 焦李成, 馬亞娟. 一種差分多目標優(yōu)化算法 [J]. 模式識別與人工智能, 2011, 24(6): 748-755.

[16] 向萬里, 馬壽峰. 一種高效率收斂的反向差分進化算法 [J]. 小型微型計算機系統(tǒng), 2014, 35(2): 343-347

[17] POIKOLAINEN I, FERRANTE N, FABIO C. Cluster-Based Population Initialization for differential evolution frameworks [J]. Information Sciences, 2015, 297(10):216-235.

(責任編輯鄒永紅)

Optimal Trajectory Planning Based on Chaos Mapping

Cooperative Differential Evolution

LIU Jian-ying1, YANG Wen-yan1, LIU Dan-dan2

(1. School of Information Engineering, Dalian Vocational Technology College, Dalian

Liaoning 116023, China;2. College of Electrization and Control Engineering,

Heilongjiang University of Science and Technology, Harbin Heilongjiang 150022, China)

Abstract:In order to improve the precision of trajectory optimization, a cooperative differential evolution algorithm based on chaotic mapping is proposed. The algorithm does not rely on mathematical model and gradient information. It can optimize by group and share information for the optimizing target, and achieve rapid trajectory optimization. We introduce the chaos mapping into the process of children construction in the later period of optimization, which makes the algorithm keep the diversity of the population and balance the ability of global search and local search. By comparing with standard functions, we validate the global optimization ability of the cooperative differential evolution algorithm. Furthermore, the practical application of the algorithm is applied to the trajectory optimization ,which can obtain the global optimal trajectory. The performance of differential evolution algorithm is improved effectively.

Key words:differential evolution; cooperative coevolution; trajectory optimization; chaos mapping

中圖分類號：TP391.9

文獻標志碼：A

文章編號：2096-1383(2016)01-0050-05

作者簡介：劉劍英 (1979-), 女，黑龍江黑河人, 副教授，主要從事智能計算、計算機軟件研究。

基金項目：國家自然科學基金資助項目 (51374099) 。

收稿日期：2015-06-04；最后修回日期：2015-09-20