求解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；李和成，男，博士，教授，博士研究生导师，主要研究方向为最优化理论与方法，进化算法及其应用。

◎图形图像处理◎