基于分解法與軌跡搜索的無人機群軌跡多目標優化模型

柳雋琰，江沸菠*，彭于波，董莉

基于分解法與軌跡搜索的無人機群軌跡多目標優化模型

柳雋琰1，江沸菠1*，彭于波1，董莉2

（1.湖南師范大學 信息科學與工程學院，長沙 410081； 2.湖南工商大學 計算機學院，長沙 410205）（?通信作者電子郵箱jiangfb@hunnu.edu.cn）

基于深度學習（DL）的傳統多目標求解器存在模型利用率低以及容易陷入局部最優的問題。針對這些問題，提出了基于分解法與軌跡搜索的無人機群軌跡多目標優化模型（DTMO-UT）。所提模型包含編碼與解碼部分。首先，編碼部分由設備編碼器（Dencoder）和權重編碼器（Wencoder）組成，用于提取物聯網（IoT）設備的狀態信息與權重向量的特征，其中權重向量代表分解多目標優化問題（MOP）的標量優化子問題，因此解決所有子問題即可解決該MOP。權重編碼器可以實現對所有子問題的編碼，從而提高了模型的利用率。然后，使用包含軌跡解碼器（Tdecoder）的解碼部分對編碼特征進行解碼，以生成帕累托最優解。最后，為了減少貪婪策略陷入局部最優的現象，為軌跡解碼器設計軌跡搜索技術，即通過生成多個候選軌跡選標量值最優的軌跡作為帕累托最優解，從而增強了軌跡解碼器在軌跡規劃時的探索能力，并獲得質量更好的帕累托集。仿真實驗結果表明，所提模型相較于主流的基于DL的MOP求解器，在模型參數量降低98.93%的情況下，MOP解的分布性提高了0.076%，延展性提高了0.014%，平均綜合性提高了1.23%，表現出較強的實用性路徑規劃能力。

軌跡規劃；深度學習；多目標優化；分解法；帕累托集

0 引言

物聯網（Internet of Things， IoT）技術的快速發展提高了諸多時延敏感型應用的服務質量（Quality of Service， QoS），例如智能交通［1］、智能輔助醫療［2］和應急救援［3］等。在這些應用中，被采集的信息需要盡快傳輸到中心服務器進行分析與決策，過時信息可能導致嚴重的控制錯誤或安全事故；因此，保證信息的新鮮度非常重要［4］，衡量信息新鮮度的指標為信息年齡（Age of Information， AoI）。數據收集系統中AoI的優化也在近幾年受到了廣泛關注［5］。無人機（Unmanned Aerial Vehicle， UAV）具有強大的機動性與靈活性，適合在數據收集系統中作為數據采集器［6］。一架UAV能按設定的軌跡依次采集沿線所有物聯網設備（IoT Device， IoTD）的數據再返回數據中心，以實現高效化的數據收集；但相較于無人車和基站，UAV更易受到自身數據存儲和電池容量的限制，所以在UAV輔助數據收集系統的設計中，通常需要考慮UAV的數據存儲約束與能耗優化，而能耗與AoI存在的競爭關系會導致二者難以同時最小化［7］。如果降低系統能耗，那么被采集數據的AoI就會延長；同理，若縮短AoI，系統總能耗則會增加，因此，該優化問題是一個典型的多目標優化問題（Multi-objective Optimization Problem， MOP）［8］。在軌跡規劃過程中，多目標規劃存在多個需要優化的目標，且這些目標之間通常是互相競爭的關系。MOP的目的是同時極大化或極小化多個具有沖突性或矛盾性的目標的最優化問題［9］；而解決MOP不同于解決經典的單目標優化問題，它的解并非唯一，即不存在一個最優解，因此傳統的單目標優化器［10］難以解決MOP［9］。所以只能通過在多個目標的優化中進行協調［7， 11］得到一組折中解以解決MOP，其中折中解也被稱為帕累托最優解，這組折中解的集合被稱為帕累托集。對于本文研究的場景，帕累托最優解是不被帕累托支配UAV軌跡，即如果一個UAV軌跡的能耗與AoI不能被其他任何UAV軌跡全面超越，那么該軌跡是一個帕累托最優解。

求解帕累托集的方法有精確法與近似法。由于帕累托集中解的數量龐大，且每個帕累托最優解的求解難度隨著問題規模呈指數級上升，所以用精確法求解大規模的多目標優化問題是不實用的［12］，因此，在合理時間內找到接近最優解的近似法成為更實用的方法。其中：Srinivas等［13］提出了NSGA（Non-dominated Sorting Genetic Algorithm），通過生成數量龐大的解并篩選非支配解求出不被支配的帕累托最優解；Deb等［14］在NSGA中引入了精英策略并得到了著名的二代NSGA（NSGA-Ⅱ），大幅提高了運算效率；Bozorgchenani等［7］采用NSGA對移動邊緣計算系統中的能耗與處理延遲進行優化；Ghambari等［15］改進了NSGA以優化UAV軌跡規劃中的能耗與效率。NSGA可以快速、直觀地得到帕累托集；然而，需要考慮多目標的適應度分配與解的多樣化維護，需要大量的專家知識從而難以執行［16］，因此，復雜度更低且更容易實現的分解法成為了解決多目標優化問題的主流方法［9］。該方法把MOP分解為若干標量優化子問題，每個子問題采用一個權重向量聚合多個目標值從而得到一個標量值，目的是最小化該標量值。每個子問題的最優解都是帕累托最優解［16］，因此解決所有子問題即可求得整個帕累托集。在基于分解法的傳統方法中，啟發式搜索算法是主流：Zhang等［16］結合分解法與進化算法，并采用近鄰策略優化種群，提出了MOEA/D（Multiple Objective Evolutionary Algorithm based on Decomposition）；周愛民等［17］在MOEA/D的基礎上采用了一個改進的混合高斯模型對群體建模并采樣產生新個體，并利用貪婪策略更新群體，從而求解整個帕累托集；侯薇等［18］采用混合交叉策略充分利用不同交叉算子的優勢，同時針對演化過程收斂的特點與結合局部搜索策略求解帕累托集。在分解法的基礎上采用經典單目標優化方法也能夠解決子問題，其中較著名的工具為谷歌團隊研發的OR-Tools（Operations Research-Tools）［19］，OR-Tools整合并改進了諸多經典優化器，如Concorde［20］、Gurobi［21］等，并在實際使用時根據問題規模與數據特點進行自適應選擇。相較于帕累托占優的方法，基于分解法的方法具有更低的復雜度且更容易實現［16］

在基于深度學習（Deep Learning， DL）的優化方法中，已經有諸多解決單目標優化問題的研究，如循環神經網絡（Recurrent Neural Network， RNN）［22］、指針網絡（Pointer Network， PN）［23］和注意力模型（Attention Model， AM）［24］等。相較于啟發式搜索算法，基于DL的方法運算速度大幅提升，且整體性能已經接近甚至超越啟發式搜索算法。在DL解決MOP的研究中，Li等［25］采用分解法與PN模型對每個子問題進行求解，并訓練了多組模型適應不同的權重向量；Wu等［26］采用分解法與AM求解所有子問題，并采用聯合優化策略讓權重向量接近的模型聯合解決子問題；Zhang等［27］采用進化算法對AM的所有子問題的解二次優化，并用優化后的結果調優模型，同時解決了多目標優化中帶時間窗的問題；董健等［28］提出了基于全連接神經網絡的天線結構多目標設計方法，并采用多目標離子群算法對網絡進行優化；黃博南等［29］采用若干RNN作為子問題的求解器解決綜合能源系統的污染物排放量和綜合運行成本。然而，這些方法需要訓練多個模型以適應權重向量不同的子問題，因此模型利用率低［9］；同時，DL方法在輸出軌跡時通常采用貪婪策略輸出所有訪問節點，容易陷入局部最優［30］。

本文的主要工作如下：

1）首先將UAV輔助的數據收集系統中能耗與AoI的優化建模為一個MOP，通過求解帕累托集解決該MOP。為此，采用分解法把MOP轉換為多個標量優化子問題，每個子問題都是通過優化UAV軌跡最小化一個標量目標值，解決所有子問題可得到帕累托集，即優化能耗與AoI的折中方案下中所有最優UAV軌跡；同時，提出了高性能的DTMO-UT模型解決所有子問題，從而得到高質量的帕累托集。

2）在DTMO-UT模型的編碼器部分，提出了設備編碼器（Device encoder， Dencoder）與權重編碼器（Weight encoder， Wencoder）分別提取IoTD狀態信息與權重向量的特征，其中IoTD狀態信息包含該IoTD的位置與帶傳輸數據量。采用Dencoder與Wencoder即可編碼所有標量優化子問題的特征，實現用一個模型解得整個帕累托集，提高了模型的參數利用率。

3）在軌跡解碼器（Trajectory decoder， Tdecoder）中加入軌跡搜索。在解決子問題時，Tdecoder首先輸出多個IoTD均不相同的初始訪問候選軌跡，之后選擇標量值最優的候選軌跡作為帕累托最優解。軌跡搜索增強了Tdecoder的全局搜索能力，能夠得到質量更好的帕累托集。

1 系統模型與優化問題

1.1　系統建模

圖1　多UAV輔助的數據收集系統

1.2　數據收集模型

1.3　路徑規劃模型

1.4　UAV能耗模型

傳輸（T表示傳輸（Transfering））能耗為：

1.5　信息年齡模型

1.6　問題定義

在本文系統，有兩個優化目標：一是最小化能耗，二是最小化采集數據的AoI。系統能耗的定義為：

系統的AoI定義為所有UAV的最大AoI：

所以，本文的優化目標為：

1.7　問題分析

2 本文模型

圖2　DTMO-UT模型的訓練與驗證流程

為了得到高性能的DTMO-UT模型，訓練階段需要產生大量訓練數據，其中一個訓練數據包含隨機分布的IoTD、不同的待傳輸數據量和一個對應偏好權重。之后DTMO-UT針對每個訓練數據采樣大量軌跡用于計算策略梯度從而優化DTMO-UT模型。當達到最大訓練次數后即可完成訓練。在驗證階段，DTMO-UT的Dencoder與Wencoder分別對IoTD狀態信息與權重向量進行編碼以提取特征，之后在Tdecoder中解碼并生成解，軌跡搜索通過生成多個軌跡并擇優的方式能幫助Tdecoder減輕局部最優并找到更好的解，當所有標量優化子問題解決后即可得到帕累托集。DTMO-UT模型實現了高參數利用率并能得到高質量帕累托集。所有帕累托最優解在多目標空間的映射稱為帕累托前沿，也能體現多目標優化算法的綜合性能，本文研究的多目標為能耗與AoI，因此每個帕累托最優解映射為一個點。當帕累托前沿越接近“左下”時，帕累托集的質量越高。得到帕累托前沿的過程如圖3所示。

圖3　DTMO-UT模型得到帕累托前沿的過程

在處理MOP時，本文采用在MOEA/D的分解法把能耗與AoI優化問題分解為若干標量優化子問題，并采用一組權重向量表示所有子問題。不過在解決子問題時，本文采用基于DL的DTMO-UT模型提取IoTD信息與權重向量的特征并生成對應的帕累托最優解，而非MOEA/D的啟發式搜索；其次，DTMO-UT模型支持輸入實數范圍內的權重向量，因此能解決的子問題數為無窮，而MOEA/D僅能處理固定數量的子問題。

2.1　DTMO-UT模型

圖4　DTMO-UT模型的結構

2.2　設備編碼器

Dencoder主要用于提取IoTD狀態信息。場景中的IoTD以圖的形式進行存儲，包含節點信息與邊信息。Dencoder包含3個部分：圖嵌入層、LSA層和特征合并層。

2.2.1圖嵌入層

本文提出了基于圖嵌入與LSA機制的Dencoder對IoTD狀態信息編碼。圖嵌入可以有效提取IoTD的圖信息，因此本文采用了基于Structure2Vector（S2V）［31］結構實現圖嵌入層。注意力機制可以使模型注意重要的特征信息，并通過加權的方式體現關注程度［32］，LSA機制則可以讓模型對輸入的信息自發地產生不同的關注，從而提取IoTD自注意力特征以產生當前權重向量下的一組帕累托最優UAV軌跡。最后通過一個特征合并層合并所有IoTD自注意力為一個全局圖特征。

2.2.2線性自注意力層

2.2.3特征合并層

在得到IoTD的自注意力特征后，對IoTD的自注意力特征進行合并。在合并特征時，文獻［24］中對LSA特征以求平均值的方式進行合并；雖然平均值法非常高效，但是容易導致特征不可恢復的缺失［37］。所以本文采用一個可學習的線性特征合并層合并所有IoTD的自注意力特征得到全局圖特征，公式為：

2.3　權重編碼器

2.4　軌跡解碼器

2.4.1軌跡搜索下的場景狀態

2.4.2線性自注意力輸出層

2.5　多目標REINFORCE訓練算法

為了在無標簽數據下訓練得到高性能DTMO-UT模型，本節將介紹針對MOP的DL訓練方法。因此，狀態、行為和獎勵如下。

狀態 在每一步的軌跡規劃中，輸入的狀態為：

行為 DTMO-UT模型的行為是讓UAV選擇一個IoTD進行數據收集或者回到數據中心：

獎勵 獎勵為能耗與AoI與權重向量的加權和的負數：

3 實驗與結果分析

3.1　參數設定

本文將設計DL模型的參數對比、與主流方法的綜合性能的對比實驗驗證DTMO-UT模型的高效性。此外，為了使模型收斂，本文的訓練采用的學習率為0.001，學習率衰減（learning rate decay）為0.96，訓練迭代次數為200［9］。運行環境配置是Windows 11操作系統，PyTorch 1.7.1框架，顯卡為NVIDIA RTX3060，處理器為i7-11500與16 GB內存。

3.2　模型參數對比

首先，本文將DTMO-UT模型與同樣基于分解法和AM的MODRL/D-AM（Multiple Objective Deep Reinforcement Learning using Attention Model）［26］模型的參數量與可解決的子問題數量進行對比，其中D（Decomposition）是多目標優化中常用的分解法。MODRL/D-AM把多目標問題分解為101個［9，16，39］標量優化子問題。因此，對比結果展示在表1中。

表1參數量與可解決的子問題數的對比

Tab.1　Comparison of parameter quantities and solvable sub-problems

在許多基于分解法的DL方法中，分解的子問題數為101［25-27］，在MODRL/D-AM中，由于需要針對每個子問題專門優化參數，因此總體參數量遠超DTMO-UT模型。DTMO-UT模型的參數量相較于MODRL/D-AM減少了98.93%，且MODRL/D-AM只支持有限個標量子問題的權重向量；而DTMO-UT模型的Wencoder支持輸入實數范圍內的權重向量，因此可以解決數量不固定的子問題。從表1可以看出DTMO-UT模型具有更少的參數使用量，并支持靈活數量的權重向量。

3.3　總體性能對比

為了檢驗DTMO-UT模型的總體性能，本文采用對比帕累托前沿的方式，帕累托前沿是所有帕累托最優解在多目標解空間的映射，因為每個解有能耗與AoI兩個指標，因此可以映射到一個二維平面。在對比算法中，除了上一小節提到的MODRL/D-AM，還有OR-Tools［19］、NSGA-Ⅱ［14］、MOEA/D［16］和未采用軌跡搜索的DTMO-UT（DTMO-UT model with No trajectory search， DTMO-UTN）模型。參數設定為：

1）MOEA/D。分解的子問題數為100，鄰向量數為10，種群數為100，個體長度為150，單點交叉算子概率為0.9，變異算子概率為0.01，迭代次數為150。

2）NSGA-Ⅱ。種群數為2 000，個體長度為150，交叉算子概率為0.9，變異算子概率為0.01，迭代次數為25 000。

3）OR-Tools。子問題數為101，并采用加權求和的方式定義所有子問題。

4）MODRL/D-AM。分解的子問題數為100，隱藏層維度為128，訓練數據批大小為200，數據量總大小為500 000。

由圖5可得，所有方法得到的帕累托前沿均為凹狀，其中DTMO-UT與MODRL/D-AM的曲線是接近的，因為這兩個方法所提出的模型都是基于AM且采用深度強化學習進行訓練，而它們均優于NSGA-Ⅱ、MOEA/D與OR-Tools。

圖5　不同場景下所有方法所得到的帕累托前沿對比

表2分布性與延展性指標的對比

Tab.2　Comparison of distribution and ductility indicators

從表2中可以總結出DTMO-UT模型在分布性與延展性都優于其他方法，是因為：1）分解法更容易得到均勻的解集，2）DTMO-UT模型的軌跡搜索能提升每個子問題的解的質量，因此提高了解極端值的能力。在啟發式方法中，NSGA-Ⅱ并非基于分解法，因此容易產生不均勻的解集，所以MOEA/D能得到比NSGA-Ⅱ更好的解集。

從表3可以總結出基于DRL的DTMO-UT、DTMO-UTN與MODRL/D-AM在所有測試數據中的性能以及運算時間均優于基于啟發式搜索的NSGA-Ⅱ、MOEA/D與OR-Tools。

在運算時間的對比中，MODRL/D-AM優于DTMO-UTN與DTMO-UT，并遠少于NSGA-Ⅱ、MOEA/D與OR-Tools，原因是：1）谷歌團隊對OR-Tools的優化器進行了優化，從而比NSGA-Ⅱ、MOEA/D運算更快。2）基于DL的方法無須反復迭代且有并行計算的加持，使運算速度遠超NSGA-Ⅱ與MOEA/D。3）MODRL/D-AM僅設計一個編碼器用于編碼IoTD信息，其模型結構比DTMO-UT簡單，因此MODRL/D-AM運算速度較快。4）DTMO-UT的軌跡搜索會生成若干候選軌跡，因此DTMO-UTN運算比DTMO-UT更快。但是表1與表3所示MODRL/D-AM需要占用更多存儲空間且性能不及DTMO-UT，采用軌跡搜索后DTMO-UT的運算效率并未損失太多同時性能上有提升。

在性能對比中，對于所有HV值的指標，DTMO-UT最高，DTMO-UTN與MODRL/D-AM次之，之后是OR-Tools、MOEA/D與NSGA-Ⅱ，原因是：1）DRL方法訓練的模型具有更好的泛化能力。2）自注意力模型比啟發式搜索算法具有更強的特征提取能力。3）采用了軌跡搜索的DTMO-UT模型能夠減輕局部最優的現象，得到更高質量的帕累托集，從而提高了HV值，并降低了多次測試結果的標準差。

表3HV值的最大值、最小值、平均值、標準差以及算法運算時間的對比

Tab.3　Comparison of maximum， minimum， average and standard deviation of HV value as well as algorithm running time

4 結語

本文研究的是一個通過優化UAV軌跡最小化數據收集系統中的能耗與AoI的MOP，通過求出帕累托集解決該MOP。考慮到求解帕累托集的傳統方法存在模型利用率低和容易陷入局部最優的問題，本文在分解法的基礎上提出了DTMO-UT模型。該模型的編碼部分通過編碼IoTD的信息與權重向量得到所有子問題的特征，實現了利用一個模型解決所有子問題的目的，從而提高了模型利用率。在解碼器部分采用了軌跡搜索，提高了模型在軌跡生成時的探索能力與帕累托集的質量，減輕了陷入局部最優的現象。

然而，本文模型依然存在一些限制，本文所研究的MOP僅考慮了最小化能耗與AoI，而實際的數據收集系統中存在諸多指標需要優化，比如UAV的數量、任務完成時間等。因此，在未來研究中，將考慮更多的優化指標，并根據多個指標的特性進行優化，找到最合適的優化方法。

[1] CUI Q， WANG Y， CHEN K-C， et al. Big data analytics and network calculus enabling intelligent management of autonomous vehicles in a smart city ［J］. IEEE Internet of Things Journal， 2019， 6（2）： 2021-2034.

[2] VERMA P，SOOD S K. Fog assisted-IoT enabled patient health monitoring in smart homes ［J］. IEEE Internet of Things Journal， 2018， 5（3）： 1789-1796.

[3] PATHAK N， DEB P K， MUKHERJEE A， et al. IoT-to-the-rescue： A survey of IoT solutions for COVID-19-like pandemics ［J］. IEEE Internet of Things Journal， 2021， 8（17）： 13145-13164.

[4] HU H， XIONG K， QU G， et al. AoI-minimal trajectory planning and data collection in UAV-assisted wireless powered IoT networks ［J］. IEEE Internet of Things Journal， 2021， 8（2）： 1211-1223.

[5] YATES R D， SUN Y， BROWN D R， et al. Age of information： An introduction and survey ［J］. IEEE Journal on Selected Areas in Communications， 2021， 39（5）： 1183-1210.

[6] CHEN Z， CHI K， ZHENG K， et al. Minimization of transmission completion time in UAV-enabled wireless powered communication networks ［J］. IEEE Internet of Things Journal， 2020， 7（2）： 1245-1259.

[7] BOZORGCHENANI A， MASHHADI F， TARCHI D， et al. Multi-objective computation sharing in energy and delay constrained mobile edge computing environments ［J］. IEEE Transactions on Mobile Computing， 2021， 20（10）： 2992-3005.

[8] LIAO Y， FRIDERIKOS V. Energy and age Pareto optimal trajectories in UAV-assisted wireless data collection ［J］. IEEE Transactions on Vehicular Technology， 2022， 71（8）： 9101-9106.

[9] LIN X， YANG Z， ZHANG Q. Pareto set learning for neural multi-objective combinatorial optimization ［EB/OL］. （2022-03-29）［2022-08-10］. https：//arxiv.org/pdf/2203.15386.pdf.

[10] HELSGAUN K. An effective implementation of the Lin–Kernighan traveling salesman heuristic ［J］. European Journal of Operational Research， 2000， 126（1）： 106-130.

[11] 肖曉偉，肖迪，林錦國，等. 多目標優化問題的研究概述［J］. 計算機應用研究， 2011， 28（3）： 805-808， 827.（XIAO X W， XIAO D， LIN J G， et al. Overview on multi-objective optimization problem research ［J］. Application Research of Computers， 2011， 28（3）： 805-808，827.）

[12] FLORIOS K， MAVROTAS G. Generation of the exact Pareto set in multi-objective traveling salesman and set covering problems ［J］. Applied Mathematics and Computation， 2014， 237： 1-19.

[13] SRINIVAS N， DEB K. Muiltiobjective optimization using nondominated sorting in genetic algorithms ［J］. Evolutionary Computation， 1994， 2（3）： 221-248.

[14] DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm： NSGA?Ⅱ ［J］. IEEE Transactions on Evolutionary Computation， 2002， 6（2）： 182-197.

[15] GHAMBARI S， GOLABI M， LEPAGNOT J， et al. An enhanced NSGA?Ⅱ for multiobjective UAV path planning in urban environments［C］// Proceedings of the 2020 IEEE 32nd International Conference on Tools with Artificial Intelligence. Piscataway： IEEE， 2020： 106-111.

[16] ZHANG Q， LI H. MOEA/D： A multiobjective evolutionary algorithm based on decomposition ［J］. IEEE Transactions on Evolutionary Computation， 2007， 11（6）： 712-731.

[17] 周愛民，張青富，張桂戌.一種基于混合高斯模型的多目標進化算法［J］. 軟件學報， 2014， 25（5）： 913-928.（ZHOU A M， ZHANG Q F， ZHANG G X. Multi-objective evolutionary algorithm based on mixed Gaussian models［J］. Journal of Software， 2014， 25（5）： 913-928.）

[18] 侯薇，董紅斌，印桂生.一種改進的基于分解的多目標進化算法［J］. 計算機科學， 2014， 41（2）： 114-118.（HOU W， DONG H B， YIN G S. Enhanced multi-objective evolutionary algorithm based on decomposition ［J］. Computer Science， 2014， 41（2）： 114-118.）

[19] LAURENT P， VINCENT F. OR-Tools ［EB/OL］. （2022-11-25）［2023-11-29］. https：//developers.google.com/optimization/.

[20] COOK W. Concorde ［EB/OL］. （2003-11-05）［2022-12-05］. https：//www.math.uwaterloo.ca/tsp/concorde.html.

[21] GU Z H， ROTHBERG E， BIXBY R. Gurobi ［EB/OL］. （2021-11-16）［2022-12-05］. https：//www.gurobi.com.

[22] SUTSKEVER I， VINYALS O， LE Q V. Sequence to sequence learning with neural networks ［C］// Proceedings of the 27th International Conference on Neural Information Processing Systems-Volume 2. New York： ACM， 2014： 3104-3112.

[23] VINYALS O， FORTUNATO M， JAITLY N. Pointer networks ［C］// Proceedings of the 28th International Conference on Neural Information Processing Systems-Volume 2. New York： ACM， 2015： 2692-2700.

[24] KOOL W， VAN HOOF H， WELLING M. Attention， learn to solve routing problems！［EB/OL］. （2018-03-22）［2022-08-29］. https：//arxiv.org/pdf/1803.08475.pdf

[25] LI K， ZHANG T， WANG R. Deep reinforcement learning for multiobjective optimization ［J］. IEEE Transactions on Cybernetics， 2021， 51（6）： 3103-3114.

[26] WU H， WANG J， ZHANG Z. MODRL/D-AM： multiobjective deep reinforcement learning algorithm using decomposition and attention model for multiobjective optimization ［C］// Proceedings of the 11th International Symposium on Artificial Intelligence Algorithms and Applications. Singapore： Springer， 2020： 575-589.

[27] ZHANG Y， WANG J， ZHANG Z， et al. MODRL/D-EL： multiobjective deep reinforcement learning with evolutionary learning for multiobjective optimization ［C］// Proceedings of the 2021 International Joint Conference on Neural Networks. Piscataway： IEEE， 2021： 1-8.

[28] 董健，欽文雯，李瑩娟，等. 基于改進反向傳播神經網絡代理模型的快速多目標天線設計［J］. 電子與信息學報， 2018， 40（11）： 2712-2719.（DONG J， QIN W W， LI Y J， et al. Fast multi-objective antenna design based on improved back propagation neural network surrogate model ［J］. Journal of Electronics & Information Technology， 2018， 40（11）： 2712-2719.）

[29] 黃博南，王勇，李玉帥，等. 基于分布式神經動態優化的綜合能源系統多目標優化調度［J］. 自動化學報， 2022， 48（7）： 1718-1736.（HUANG B N， WANG Y， LI Y S， et al. Multi-objective optimal scheduling of integrated energy systems based on distributed neurodynamic optimization ［J］. Acta Automatica Sinica， 2022， 48（7）： 1718-1736.）

[30] KWON Y D， CHOO J， KIM B， et al. POMO： policy optimization with multiple optima for reinforcement learning ［J］. Advances in Neural Information Processing Systems， 2020， 33： 21188-21198.

[31] DAI H， KHALIL E， ZHANG Y， et al. Learning combinatorial optimization algorithms over graphs ［C］// Proceedings of the 31st International Conference on Neural Information Processing Systems. Red Hook： Curran Associates Inc.， 2017： 6351-6361.

[32] YANG L， WANG S， CHEN X， et al. High-fidelity permeability and porosity prediction using deep learning with the self-attention mechanism ［J］. IEEE Transactions on Neural Networks and Learning Systems， 2023， 34（7）： 3429-3443.

[33] NAIR V， HINTON G E. Rectified linear units improve restricted Boltzmann machines［C］// Proceedings of the 27th International Conference on Machine Learning. New York： ACM， 2010： 807-814.

[34] VASWANI A， SHAZEER N， PARMAR N， et al. Attention is all you need ［J］. Advances in Neural Information Processing Systems， 2017， 30： 6000-6010.

[35] KATHAROPOULOS A， VYAS A， PAPPAS N， et al. Transformers are RNNs： fast autoregressive transformers with linear attention［C］// Proceedings of the 37th International Conference on Machine Learning. New York： ACM， 2020： 5156-5165.

[36] CLEVERT D-A， UNTERTHINER T， HOCHREITER S. Fast and accurate deep network learning by exponential linear units （ELUs）［EB/OL］. （2015-11-23）［2022-12-26］. https：//arxiv.org/pdf/1511.07289.pdf.

[37] FANELLO S R， NOCETI N， CILIBERTO C， et al. Ask the image： supervised pooling to preserve feature locality ［C］// Proceedings of the 27th IEEE Conference on Computer Vision and Pattern Recognition. Piscataway： IEEE， 2014： 851-858.

[38] WILLIAMS R J. Simple statistical gradient-following algorithms for connectionist reinforcement learning［J］. Machine Learning， 1992， 8： 229-256.

[39] ISHIBUCHI H， SAKANE Y， TSUKAMOTO N， et al. Adaptation of scalarizing functions in MOEA/D： an adaptive scalarizing function-based multiobjective evolutionary algorithm ［C］// Proceedings of the 2009 International Conference on Evolutionary Multi-Criterion Optimization. Berlin： Springer， 2009： 438-452.

[40] NAZARI M， OROOJLOOY A， TAKá? M， et al. Reinforcement learning for solving the vehicle routing problem ［C］// Proceedings of the 32nd International Conference on Neural Information Processing Systems. Red Hook： Curran Associates Inc.， 2018： 9861-9871.

[41] RIQUELME N， VON LüCKEN C， BARAN B. Performance metrics in multi-objective optimization ［C］// Proceedings of the 41st Latin American Computing Conference. Piscataway： IEEE， 2015： 1-11.

[42] ZITZLER E， THIELE L， LAUMANNS M， et al. Performance assessment of multiobjective optimizers： an analysis and review ［J］. IEEE Transactions on Evolutionary Computation， 2003， 7（2）： 117-132.

Multi-objective optimization model for unmanned aerial vehicles trajectory based on decomposition and trajectory search

LIU Junyan1， JIANG Feibo1*， PENG Yubo1， DONG Li2

（1，，410081，；2，，410205，）

The traditional Deep Learning （DL）-based multi-objective solvers have the problems of low model utilization and being easy to fall into the local optimum. Aiming at these problems， a Multi-objective Optimization model for Unmanned aerial vehicles Trajectory based on Decomposition and Trajectory search （DTMO-UT） was proposed. The proposed model consists of the encoding and decoding parts. First， a Device encoder （Dencoder） and a Weight encoder （Wencoder） were contained in the encoding part， which were used to extract the state information of the Internet of Things （IoT） devices and the features of the weight vectors. And the scalar optimization sub-problems that were decomposed from the Multi-objective Optimization Problem （MOP） were represented by the weight vectors. Hence， the MOP was able to be solved by solving all the sub-problems. The Wencoder was able to encode all sub-problems， which improved the utilization of the model. Then， the decoding part containing the Trajectory decoder （Tdecoder） was used to decode the encoding features to generate the Pareto optimal solutions. Finally， to alleviate the phenomenon of greedy strategy falling into the local optimum， the trajectory search technology was added in trajectory decoder， that was generating multiple candidate trajectories and selecting the one with the best scalar value as the Pareto optimal solution. In this way， the exploration ability of the trajectory decoder was enhanced during trajectory planning， and a better-quality Pareto set was found. The results of simulation experiments show that compared with the mainstream DL MOP solvers， under the condition of 98.93% model parameter quantities decreasing， the proposed model reduces the distribution of MOP solutions by 0.076%， improves the ductility of the solutions by 0.014% and increases the overall performance by 1.23%， showing strong ability of practical trajectory planning of DTMO-UT model.

trajectory planning; Deep Learning (DL); multi-objective optimization; decomposition; Pareto set

This work is partially supported by National Natural Science Foundation of China （41904127）.

LIU Junyan， born in 1998， M. S. candidate. His research interests include deep learning， combinatorial optimization.

JIANG Feibo， born in 1982， Ph. D.， association professor. His research interests include deep learning， reinforcement learning， federated learning.

PENG Yubo， born in 1996， M. S. candidate. His research interests include edge computing， federated learning.

DONG Li， born in 1982， Ph. D.， association professor. Her research interests include deep learning， reinforcement learning.

TP183

A

1001-9081（2023）12-3806-10

10.11772/j.issn.1001-9081.2022121882

2022?12?22；

2023?03?15；

2023?03?17。

國家自然科學基金資助項目（41904127）。

柳雋琰（1998—），男，湖南岳陽人，碩士研究生，主要研究方向：深度學習、組合優化；江沸菠（1982—），男，湖南長沙人，副教授，博士，主要研究方向：深度學習、強化學習、聯邦學習；彭于波（1996—），男，重慶人，碩士研究生，主要研究方向：邊緣計算、聯邦學習；董莉（1982—），女，湖南長沙人，副教授，博士，主要研究方向：深度學習、強化學習。