求解TTP問題新優化模型的混合遺傳算法

馬梅，李和成

青海師范大學數學與統計學院，西寧810008

求解TTP問題新優化模型的混合遺傳算法

馬梅，李和成

青海師范大學數學與統計學院，西寧810008

CNKI網絡出版：2017-04-01,http://kns.cnki.net/kcms/detail/11.2127.TP.20170401.0908.046.html

1 引言

在實踐中，很多問題通常由兩個或兩個以上的子問題復合而成，而這些子問題并不是相互獨立的，一個子問題獲得最優解往往影響其他子問題的解，原問題的解需要綜合考慮所有子問題的解，如Bonyadi等提出的流竄犯問題（Traveling Thief Problem，TTP）[1]。TTP問題由旅行商問題（Traveling Sales Problem，TSP）和背包問題（Knapsack Problem，KP）復合而成，因此同時具備了TSP問題和KP問題的求解難度。一個TTP問題可以描述如下：假定有n個城市，兩兩距離已知，有m個物品分布在這n個城市中。一個小偷從某一城市出發，拜訪所有的城市僅一次，最后回到出發城市。在整個過程中，小偷從每個城市拿取一定的物品放入租賃的具有一定容量的背包中，但所拿物品的總重量不得超過背包容量。背包的租金與旅行時間相關，旅行時間既與選取的路徑有關，也與所負重量有關。重量越大，行走時間越長，支付的租金越多。在該問題中，小偷所拿的物品總價減去背包租金即為收益。問題求解的目的是收益最大化，即小偷需要找到一條路徑和一個物品的選取方案，使得旅途結束后所得的收益最大。

TTP問題的一個有趣應用是具有服務利潤的限量弧路由問題（Capacitated Arc Routing Problem，CARP）。限量弧路由問題由Golden等[2]提出，城市中灑水問題、垃圾清理、信件投遞等均可建模為CARP問題。目前基于不同的需求，限量弧路由問題及其各種變種被廣泛提出[3-7]。但這些問題忽視了兩個重要的現實因素：一是服務利潤。每個客戶在服務過程均具有一定的需求量和服務利潤，所有客戶在服務過程中均被服務一次且僅一次。給定車輛的負載量限制，則可能只需服務具有高利潤客戶的一小部分就可以最大化最后利益。二是基于車輛負載量的旅行花費。每輛車在服務過程中基于車輛的負載量還會產生一定的旅行花費（例如，汽油消耗量）。每輛車對于需求的負載量均有限且小于所有客戶需求量之和。問題求解的目標是在滿足下列條件時，最大化服務利潤：（1）每輛車從倉庫出發并最終回到出發倉庫；（2）每個客戶均被一輛且僅一輛車所服務；（3）對于每輛車，其服務的客戶所具有的總需求量不超過其容量。考慮了這些問題后，具有服務利潤的CARP問題其模型即為TTP問題。

TTP問題是近幾年被提出的一個復合組合優化問題。一方面，該問題同時具有TSP問題和KP問題的計算復雜度，對現有的組合優化算法提出了新的挑戰，另一方面，在實踐領域的應用越來越廣。這兩方面的需求吸引了越來越多的研究者。Mei等[8]針對大規模的TTP問題給出了相對簡單的算法，分析了不同算法的計算復雜度，并給出了減少計算復雜度的策略，提出的基于兩階段局部搜索的復合算法（MATLS）在計算結果上優于文獻[9]中提出的隨機局部搜索算法（RLS）和（1+1）進化策略。Bonyadi等[10]設計了一種協同進化算法。該算法利用TSP問題和KP問題間交互式信息進行求解，將得到的結果進行組合作為TTP問題的近似解。與該文提出的DH算法相比，協同進化算法的計算更有效。文獻[8-10]采用的算法框架是首先確定一個子問題的解，再求另一個問題的解。典型的方法就是初始化最短的TSP路徑的集合，然后求解相應的KP問題。這種做法雖然可以得到兩個子問題相對最優的解，但不能保證能找到對應TTP問題的最優解。

在文獻[11]中，Mei等提出了兩種復合算法。一個是協同進化算法（CC），該算法分別利用進化算法求解兩個子問題，在每一代交換子問題間的信息，最后獲得最優解。另一種復合算法將TTP問題作為一個整體進行求解。兩種算法在同一測試集上的結果表明，第二種復合算法優于第一種算法。Louren?o等[12]通過考慮兩個子問題之間關系，在進化過程中將路徑和物品選取方案作為種群個體，給出了一種進化算法。文獻[11-12]中，將TTP問題作為一個整體去求解，計算結果顯示這種處理技術是有效的。

另外，Polyakovskiy等[13]研究了一種非線性背包問題。該問題的主要特征是：（1）沿某條確定的路徑拿取物品；（2）考慮旅行時間。闡述了問題的復雜度并指出即使背包容量無約束，該問題也是NP-難問題，并給出了求解該問題的精確和近似混合整數規劃方法（Mixed Integer Programming，MIP）。

在以上提出的TTP問題中，總假設小偷提前知道每個城市中物品的分布情況，故在旅行開始前利用此信息對所有物品進行價值評估，提前決定物品選取策略。

本文從另一個角度考慮TTP問題，即假設小偷在到達前并不知道城市中物品的具體位置。為了行走前能有效規劃路徑，選取盡可能好的方案，本文假設知道物品在每個城市分布的概率。與現有模型相比，考慮的新問題具有如下特點：

（1）在TTP模型中考慮小偷提前不知道物品的具體位置更符合實際情況。

（2）模型中含有概率信息，具有不確定性，只能獲得概率意義上的最優解。

與一般TTP問題一樣，不同的出發點，具有不同的最優方案，這一點不同于TSP問題。不失一般性，本文選擇出發點為編號1的城市。另外，出發城市中的物品返回后再選擇是合理的。

2 TTP問題

2.1 問題描述

一個小偷拜訪每個城市一次且僅一次，并最終回到出發城市。在整個過程中，小偷從每個城市拿取一定的物品裝進背包，但所拿物品的總重量不得超過背包容量W。背包的租金R與旅行時間相關。小偷需要找到一條路徑和一種物品的拿取策略，使得旅途結束后所得的收益最大。

令ykj∈{0,1} 。當物品k從城市xj拿取時，ykj=1，否則ykj=0。記小偷離開城市xj時所拿物品的總重量為wj。那么，對任意一個路徑X（xj的一個排列，不失一般性，仍記為X=(x1,x2,…,xn)）和一個拿取策略ykj，其優化模型為：

其中：

表示小偷從城市xi到城市xj所花的時間。

2.2 問題分析

從TTP問題的優化模型可知，小偷旅行時間和所拿物品的重量通過速度聯系在一起。因此求解總的旅行時間必須知道路徑和拿取方案，同時，總收益又與旅行時間有關，由此可以看出，兩個子問題并不是相互獨立的。

圖1給出TTP問題的一個簡單例子[1]，除第一個點外，其他點均有物品分配。問題的相關參數值如下：

（1）n=4, m=5, W=3, vmax=1, vmin=0.1 。

（2）單位時間所花的租金為R=$1。

（4）每個物品的價值及重量定義為Ik=(pk,wk),k=1,2,3,4,5。則有

（5）物品的有效性C1={0}, C2={4,5}，C3={1,2,3} ，C4={4}。

圖1 TTP問題算例

在上述例子中，若將TTP問題分解為兩個子問題單獨求解，得到兩個對應子問題的最優解分別為：TSP問題的最短路徑為X={1,2,3,4}或X={1,4,3,2}。KP問題的最佳選取方案為Y={3,0,0,0,0}，此時TTP問題的收益G=-10。但事實上該TTP問題的最大收益G=50，最優路徑X={1,2,4,3}，選取方案Y={0,3,3,0,0}。

從上述例子可以看出，將兩個子問題分別求最優解，不能保證得到TTP問題的最優解，TTP問題的兩個子問題相互依賴。

3 基于概率分布的新模型及算法

3.1 新TTP問題模型

在實踐中小偷往往提前不知道物品的具體位置，因此行走前無法明確地規劃行走路線和拿取方案。為了解決這個問題，在新模型中假設已知物品分布的概率信息。基于這些概率信息規劃合適的路徑和制定好的拿取方案。

假設物品k在城市xj中存在的情況服從概率為Pkj的0-1分布。即物品k在城市xj的概率為Pkj，不在城市xj的概率為1-Pkj。則物品k在城市xj的價值均值為相應的，物品k在城市xj中的重量均值新的優化模型為：

3.2 物品有效價值及選取策略

對于路徑X={x1,x2,…,xn}，評估所有物品的有效價值。令----pkj表示物品k在城市xj中的有效價值。計算公式如下：

根據每個物品的有效價值，對所有物品進行排序，按次序選擇，有效價值大的物品優先拿取。在物品的選取過程中應用文獻[8]提出的策略消除不增加收益的物品。

3.3 局部搜索

在選擇的路徑上，物品的重量和行走距離有以下四種情況：

（1）城市中物品的重量較大，但行走距離較小（如圖2中的點a）；

（2）城市中物品的重量較小，且行走距離也較小（如圖2中的點b）；

（3）城市中物品的重量較小，但行走距離較大（如圖2中的點c）；

（4）城市中物品的重量較大，且行走距離也較大（如圖2中的點d）。

以上四種情形，（4）是不利于獲得最優解的情況，因此對該路徑進行局部調整，將重量大的物品放在后面拿取，即將相應城市的次序向后調整，使之變成（1）的情況，有利于改進解的質量。

圖2 城市中物品重量及行走距離

對于給定的路徑X={x1,x2,…,xn}，通過有效價值計算，獲得物品的拿取方案。定義集合Rj?Cj，表示城市xj中所拿物品的集合。則每個城市中所拿物品的重量定義為：

城市xj到城市x1的行走距離記為d(xj,x1)，則

特別的，d(x1,x1)=0。

給出局部搜索算法的步驟：

（1）對wj和距離d(xj,x1)進行標準化，其標準化形式如下：

其中wmax、wmin表示每個城市中拿取物品重量的最大值和最小值。

（2）對每個城市計算w′j和d′j的乘積，記作wdj=w′j×d′j,j=1,2,…,n，作為城市xj對最后收益是否有利的指標。

（3）令wdmax=max{wdj,j=1,2,…,n}，并記對應城市為xmax。

（4）對給定的路徑，在城市xmax所在位置后隨機產生兩個插入位置，將城市xmax分別移位至產生的兩個隨機位，得到兩個新的路徑，記為X1和X2。對產生的路徑X1和X2，利用物品選取策略求得相應的物品拿取方案。

（5）求解新方案(X1,Y1)、(X2,Y2)的目標函數值，兩者中較好者與原方案比較，若優于原方案，則替換原方案，否則保留原方案。

3.4 提出的復合算法

基于物品選擇策略和局部搜索方法，給出求解TTP問題新模型的一個復合遺傳算法（HGA算法）。考慮到遺傳算法的全局收斂性，在該算法框架中，利用遺傳算法搜索路徑。

HGA算法：

（1）初始化種群。采用文獻[14]中路徑的編碼方式產生初始種群P(0)。種群規模為N。個體雜交概率為pc，變異概率為pm。令代數t=0。

（2）適應度評估。利用物品拿取策略給出拿取方案，并計算目標函數值作為適應度。

（3）雜交、變異。采用文獻[14]中的雜交、變異算子產生后代集合，并基于相應的物品拿取方案評估個體。

（4）局部搜索。對后代中較差的v個個體進行局部搜索，并評估新產生的個體。

（5）終止條件。當迭代次數達到最大代數時，算法停止，輸出最大收益Gmax，否則，令t=t+1，轉（3）。

由于TTP問題的目標函數不僅與距離有關，而且與物品的拿取方案有關。遺傳算法能有效通過選擇算子搜索較好的個體。另外，局部搜索方法是在現有路徑上考慮了物品的重量和距離，這個方法有效彌補了單純路徑搜索的不足。

盡管遺傳算法具有全局收斂性，但考慮到問題中物品的分布具有不確定性，因此本文算法獲得的是概率意義下的最優解。

4 仿真實驗

目前文獻中對不知道物品具體位置的情況研究不多，為了檢驗本文模型的可行性和算法的有效性，本文在文獻[9]中選擇了7個TTP算例（eil51、u159、ts225、u574、u724、dsj1000、fl1577），城市數分別為51、159、225、574、724、1 000、1 577。按照文獻[8]中物品的重量與價值的3種關系（Uncorrelated Type with Similar Weights（UT/SW）、Bounded Strongly correlated Type（BST）、Uncorrelated Type（UT）），每個算例產生3個不同的算例，共計算21個算例。參照算例中物品的位置信息，給出了相應物品的分布概率。為了和現有結果作參考，按如下規則取概率分布：原例中若物品k在城市xj中出現，則在[0.9，1]中隨機產生一個數作為Pkj；若不出現，則在[0，0.1]中隨機產生一個數作為Pkj。

算法參數如下：種群規模N=500，雜交概率pc=0.8，變異概率pm=0.05，對算例eil51、u159、ts225，最大迭代次數為500，其他算例最大代數為1 000。對每個算例，算法重復執行20次。

計算結果分別見表1。其中mean表示20次計算的平均目標值，std表示20次計算所得目標值的均方差，CPU表示本文提出的HGA算法運行的平均CPU時間。

從實驗結果可以看出，HGA算法對算例計算的平均目標值和文獻中確定模型的最優目標值相差不大，同時看到，HGA算法計算的均方差較小，在算例eil51、u159、ts225-BST、ts225-UT/SW等14個算例上，HGA算法的均方差好于文獻方法，在其他算例上，不如文獻中得到的均方差，但結果相差不大。另外，從計算時間上可以看出，HGA算法獲得最好解的時間均在70 s內。這意味著本文算法能有效求解這種含不確定信息的TTP問題。

表1 實驗結果

5 結論

本文在已有的TTP問題的框架上，考慮了提前不知道物品分布的情況下，如何使收益“最大”的新模型。針對該問題，設計了一個混合遺傳算法。該算法利用遺傳算法搜索路徑，基于有效價值計算選定拿取方案，根據城市中物品的重量和行走距離對路徑進行局部優化。這個算法的特點是將兩個問題的優化有效地整合到一個算法框架內，這有別于一些文獻中分開優化，然后“對接”的思路。實驗結果表明，提出的算法是有效可行的。下一步將在算法中進一步綜合考慮路徑、價值和重量的關系，利用啟發式信息改進算法的搜索效率。

[1] Bonyadi M R，Michalewicz Z，Batone L.The traveling thief problem：The first step in the transition from theoretical problems to realistic problems[C]//IEEE Congress on Evolutionary Computation（CEC），2013：1037-1044.

[2] Golden B L，Wong R T.Capacitated arc routing problems[J].Networks，1981，11（3）：305-316.

[3] Dror M.Arc routing：Theory，solutions and application[M].[S.l.]：Springer Science&Business Media，2000.

[4] Mei Y，Tang K，Yao X.Improved memetic algorithm for capacitated arc routing problem[C]//2009 IEEE Congress on Evolutionary Computation，2009：1699-1706.

[5] Mei Y，Tang K，Yao X.Decomposition-based memetic algorithm for multi-objective capacitated arc routing problem[J].IEEE Transactions on Evolutionary Computation，2011，15（2）：151-165.

[6] Mei Y，Tang K，Yao X.A memetic algorithm for periodic capacitated arc routing problem[J].IEEE Transactions on Systems，Man，and Cybernetics：Part B Cybernetics，2011，41（6）：1654-1667.

[7] Mei Y，Tang K，Yao X.Cooperative co-evolution with route distance grouping for large-scale capacitated arc routing problem[J].IEEE Transactions on Evolutionary Computation，2014，18（3）：435-449.

[8] Mei Y，Li X，Yao X.Improving efficiency of heuristics for the large scale traveling thief problem[C]//Simulated Evolution and Learning，2014，8886：631-643.

[9] Polyakovskiy S，Bonyadi M R，Michalewicz Z，et al.A comprehensive benchmark set and heuristics for the traveling thief problem[C]//Genetic and Evolutionary Computation Conference（GECCO），2014：477-484.

[10] Bonyadi M R，Michalewicz Z，Przybylek M R，et al.Socially inspired algorithms for the traveling thief problem[C]//Genetic and Evolutionary Computation Conference（GECCO），2014：421-428.

[11] Mei Y，Li X，Yao X.On investigation of interdependence between sub-problems of the traveling thief problem[J].Soft Computing，2014：1-16.

[12] Louren?o N，Francisco B，Costa E.An evolutionary approach to the full optimization of the traveling thief problem[C]//16th European Conference on Evolutionary Computation，2016，9595：34-45.

[13] Polyakovskiy S，Neumann F.Packing while traveling：Mixed integer programming for a class of nonlinear knapsack problems[C]//International Conference on AI and OR Techniques in Constraint Programming for CombinatorialOptimizationProblems，2015，9075：332-346.

[14] Wang Y P，Han L X，Li Y H，et al.A new encoding based genetic algorithm for the traveling salesman problem[J].Engineering Optimization，2006，38（1）：1-13.

MA Mei,LI Hecheng.Hybrid genetic algorithm for solving new optimization model of TTP.Computer Engineering andApplications,2018,54（6）：156-160.

MAMei,LI Hecheng

School of Mathematics and Statistics,Qinghai Normal University,Xining 810008,China

The Traveling Thief Problem（TTP）is a composite optimization problem which combines the Traveling Salesman Problem（TSP）with the Knapsack Problem（KP）,and has an accumulated computational complexity caused by these two problems.In this paper,based on the original version of TTP,a new optimization model with probability distribution information is firstly proposed by considering that the thief doesn’t explicitly know the item location in advance in all cities.Then,by calculating the effective value of each item,a selection scheme of items is provided.Finally,taking advantage of a present genetic algorithm for solving TSP and a designed local search scheme,a new hybrid genetic algorithm is developed for dealing with the new TTP model.The simulation results show the proposed algorithm is feasible and efficient.

traveling thief problem;genetic algorithm;effective value;maximum profit

流竄犯問題（Traveling Thief Problem，TTP）是旅行商問題和背包問題的一個組合問題，同時具有兩個問題的計算復雜度。在現有TTP問題中考慮了小偷提前不知道物品具體位置的情況，給出了新的具有概率分布信息的優化模型；利用有效價值指標，給出了物品的選取方法；基于一個TSP的遺傳算法框架和新設計的局部搜索策略，提出了求解該模型的混合遺傳算法。數值仿真結果表明，提出的算法是可行有效的。

流竄犯問題；遺傳算法；有效價值；最大收益

2016-09-27

2017-01-11

1002-8331（2018）06-0156-05

A

TP39

10.3778/j.issn.1002-8331.1609-0392

國家自然科學基金（No.61463045，No.11301291）；青海省自然科學基金（No.2013-Z-937Q）。

馬梅（1991—），女，碩士研究生，主要研究方向為最優化理論及應用，E-mail：1450670013@qq.com；李和成，男，博士，教授，博士研究生導師，主要研究方向為最優化理論與方法，進化算法及其應用。

◎圖形圖像處理◎