混合算法求解多目标平衡旅行商问题

董学士 董文永 王豫峰

(武汉大学计算机学院 武汉 430072) (dxs_cs@163.com)

混合算法求解多目标平衡旅行商问题

董学士 董文永 王豫峰

(武汉大学计算机学院 武汉 430072) (dxs_cs@163.com)

平衡旅行商问题(balanced traveling salesman problem, BTSP)是旅行商问题(traveling salesman problem, TSP)的变化模型，是另一种组合优化问题，可在汽轮机(gas turbine engines, GTE)等的优化问题中得到应用，但BTSP模型只能对含单个旅行商一个任务的优化问题建模，不能同时对含多个旅行商多任务的问题进行建模和优化.基于此，首次提出了一种多目标平衡旅行商问题(multi-objective balanced traveling salesman problem, MBTSP)模型,可建模含多个旅行商多任务的优化问题，具体可应用在含多个目标或个体的实际问题，例如含多个GTE的优化.相关文献的研究已证实，伊藤算法和遗传算法(genetic algorithm, GA)在求解组合优化问题中具有较好的性能，因此，应用混合伊藤算法(hybrid ITO algorithm, HITO)和混合遗传算法来求解MBTSP问题.HITO通过蚁群算法(ant colony optimization, ACO)来产生基于图的概率生成模型，再用伊藤算法的漂移和波动算子对该图模型进行更新,从而得到MBTSP的最优解.对于混合遗传算法，第一个用贪心法对遗传算法进行改进，命名为贪心法遗传算法(genetic algorithm with greedy initialization, GAG)，第二个用爬山算法优化遗传算法，称之为爬山法遗传算法(genetic algorithm by hill-climbing, GAHC)，最后一个为模拟退火遗传算法(genetic algorithm with simulated annealing, GASA).为了有效验证该算法，使用小尺度到大尺度的不同规模MBTSP问题的数据进行实验，结果表明：混合算法在求解MBTSP问题是有效的，并表现出不同的特点.

混合伊藤算法；混合遗传算法；平衡旅行商问题；多目标平衡旅行商问题；蚁群算法

平衡旅行商问题(balanced traveling salesman problem, BTSP)是TSP的变化模型，可应用在汽轮机的优化等问题.但是BTSP模型只能对含一个旅行商单个任务的问题建模，没法同时对含多个旅行商有多个单独任务的问题进行建模和优化，基于此，本文提出了多目标的平衡旅行商问题(multi-objective balanced traveling salesman problem, MBTSP)，该模型可应用于含多个旅行商多任务的优化问题.相关文献研究已证实伊藤算法和遗传算法在求解组合优化问题上具有一定的优势[1-2]，因此，本文将混合的伊藤算法(hybrid ITO algorithm, HITO)和遗传算法(genetic algorithm, GA)应用到求解MBTSP问题，通过3种不同尺度的实验表明各种算法在求解该问题上是有效的，并表现出不同的特点.

着色旅行商问题(colored traveling salesman problem, CTSP)[1-4]是近年被提出的一个问题，国内外在这方面的研究文献较少，李俊等人[1,3]首次提出了CTSP，并将遗传算法、贪心初始化的遗传算法(genetic algorithm with greedy initialization, GAG)、爬山算法遗传算法(genetic algorithm by hill-climbing, GAHC)、模拟退火遗传算法(genetic algorithm with simulated annealing, GASA)应用在求解该问题中.CTSP是TSP和MTSP一种扩展模型，一定条件下它可以转化成TSP和MTSP问题[1]；董文永等人将伊藤算法应用于求解CTSP问题[2].CTSP可在一定条件下(共享城市只含有起始点)转换成多个单一的TSP[1]，然后改变目标函数可转化为MBTSP.Ahmed将一种混合的遗传算法应用于求解瓶颈旅行商问题(bottleneck traveling salesman problem)[5]；Plante等人给出可将瓶颈TSP和BTSP应用在汽轮机的导向叶片组的优化问题，其中，BTSP可应用于最小化平均喷嘴流的区域的最大平方差和最小平方差的差值[6]；另外，文献[7-8]对BTSP的模型和应用做了更详细的介绍.此外，利用混合算法或策略求解优化问题的工作包括：文献[9]给出了混合策略在演化算法求解优化问题有效性的理论支持；文献[10]将一种混合算法应用在求解有实际限制的车辆路径问题；文献[11-12]分别提出了一种混合算法用于求解多目标优化问题和最小权重支配集问题.

根据存在的问题和实际需求，本文提出了一种含多个旅行商多单独任务的问题模型MBTSP，并首次将混合伊藤算法和遗传算法应用其中.HITO采用ACO来生成基于图的概率生成模型，然后应用伊藤算法的波动和漂移算子对该图模型进行动态的更新来求得问题的最优解.混合遗传算法应用贪心算法、爬山算法和模拟退火算法对基本的遗传算法进行优化，通过不同尺度的实验和分析表明，混合算法在求解问题上表现出不同的特点，GAHC在求解MBTSP问题的求解质量表现较好，在多数实例情况下，要好于其他对比算法，GASA和HITO在该方面也表现较优，HITO是ACO与伊藤算法的混合算法，在求解质量方面要好于ACO.

1 多目标平衡旅行商问题

1.1MBTSP问题

多目标平衡旅行商问题MBTSP含有m个旅行者和n个城市，m，n∈Z={1,2,3,…},m

城市数据集V被分成m个非空集.另一个数据集Vi,∀i∈Zm={1,2,3,…,m}表示只有旅行者i才能访问.定点depot表示站点或起始点，是旅行者i开始和结束的地方.

变量xijk(i≠j,i,j∈V,k∈Zm)为第k个旅行者是否经过城市i到j，变量uik(i∈V,k∈Zm)为第k个旅行者从起点到城市i的城市数目.

MBTSP的目标就是在G中寻找m个Hamilton回路，并使得所有旅行回路中的最大边与最小边的差最小，其中所有的城市只能被访问一次.

MBTSP的目标函数为

Minf=maxedge(i,j)m-minedge(i,j)m，
i,j=0,1,2,…,n-1.

(1)

MBTSP限制条件为

(2)

式(2)为旅行者开始和结束于该起始点；

j≠i,i∈V{0}，

(3)

式(3)代表在每个问题中，除了起始点之外，每个城市只能被访问一次.

1.2MBTSP与CTSP

MBTSP与CTSP的相同点是都为TSP的变化模型，都有多个旅行商，属于NP难问题，都可对实际的优化问题进行建模，每个问题都有独享城市，并且每个城市只能被访问一次，MBTSP中的独享城市与CTSP的独享城市有相同的访问规则和限制条件.不同点是：MBTSP与CTSP的目标函数不同,前者是使所有旅行回路的最大边与最小边的差值最小，而后者是使所有旅行回路的总的旅行距离最小.但是，CTSP在一定条件下，可转化为MBTSP，当CTSP的共享城市为0，即只含一个起始点，CTSP会变成多个单一的TSP[1].然后改变多个单一TSP问题的目标函数，即最小化所有旅行回路的最大边与最小边的差，即可将CTSP转化为MBTSP问题.

1.3MBTSP相关应用

文献[6-8]已给出BTSP可在汽轮机GTE的喷嘴导叶片组(nozzel guide vane assembly problem, NGVAP)等优化问题得到应用，并可用于建模资源均匀分配的实际问题.但BTSP模型不能同时对含多个旅行者有多个任务的优化问题进行建模和优化，譬如含多个GTE的优化，本文提出的模型MBTSP可用来建模该类问题.MBTSP中的多目标可指多个旅行者和车辆等，本文给出了该问题的另外一类应用实例.例如有多个人或车辆需要对某个地区的资源或物资进行均匀的分配，该地区根据目标或个体(人或车辆)的数量被分成若干区域，每个个体将单独负责一个区域，对该区域的资源进行均匀分配，一个区域包涵若干地点，一个地点被访问之后，无需再次访问，该问题有多个个体及其单独的任务，其目标是完成任务并使资源均匀分配在整个地区.实例问题中的个体、任务和目标与MBTSP中的旅行商、任务和目标相匹配，因此该类问题可用MBTSP进行建模和优化.

2 混合算法求解MBTSP

2.1混合伊藤算法求解MBTSP

伊藤算法[13-17]是由武汉大学董文永等人提出，该算法用粒子来表示问题的解，其全局优化的关键点是漂移和波动算子.

2.1.1 概率生成公式

混合算法采用ACO路径选择策略来生成MBTSP解的构造方案[16-17]：

(4)

其中，α和β为控制参数，η(i,j)表示经验能见度，也是距离的倒数；tabuk为禁忌表，在此表示已被旅行者走过的城市.

2.1.2 设计伊藤算法算子

1) 微粒半径

在求解过程中需要对粒子解的适应度值排序，然后计算粒子半径[16-17]：

(5)

式(5)中粒子的适应度值均匀地分布在粒子半径界限值rmax和rmin之间.

2) 环境温度

算法环境温度的更新公式：

T(t)=ρT(t-1)，

(6)

其中，T(t)为t时刻的温度，ρ为温度下降的速率.

3) 漂移和波动算子的设计

本文用ACO的信息素浓度进行漂移和波动操作:1)漂移算子是指用吸引元来吸引当前粒子，从而增强其信息素浓度；2)因随机扰动可以产生了波动，因此可以选取路径增强其浓度；3)路径信息素的挥发可使其浓度的大小均衡[16-17].

布朗运动中，微粒半径和环境温度控制粒子的运动能力，本文运动能力为[17]

(7)

其中，δ表示运动能力，λ为控制半径运动能力的参数.

信息素更新[17]

τ(i,j)=(1-ρ)×τ(i,j)，

(8)

ρ为信息素挥发因子，1≤i≤n,1≤j≤n.

增强信息浓度：

τ(i,j)=τ(i,j)+δ,e(i,j)∈σ′，

(9)

其中，δ表示运动能力.

增强随机路径之上的浓度：

τ(i,j)=τ(i,j)+δ, ife(i,j)∈σ‴∩rand()<ρ，

(10)

其中，ρ为选择随机路径的概率，可调整波动强度的参数，rand()表示随机产生0～1的函数.更新公式如下：

(11)

其中，σ‴表示粒子和最优粒子都未经过的路径.

2.1.3 算法设计步骤

混合伊藤算法的设计步骤如算法1所示[2].

算法1.Optimumsolution←HITO /*HITO求解问题的最优解*/

①MAX_NO_UPDATE_TIME;GEN; /*初始化*/

②α=4.7;β=3.8;p=0.55;T=1 000;Tlength=2; /*初始化参数*/

③ 读取MBTSP数据集;

④ 初始化所有路径的活动强度;

⑤ 初始化粒子群M;

⑥ whilenoUpdateTimes

⑦ 根据适应值fitness对所有粒子进行排序;

⑧currentBestSolution←particles[0]; /*首个粒子为当前最优解*/

⑨ ifallBestSolution.fitness

⑩noUpdateTimes←0; /*将未更新次数设置为0*/

算法1中MAX_NO_UPDATE_TIME表示最大未更新迭代次数，指算法在一定迭代次数后仍未求得更好解则终止，GEN为最大迭代次数.步骤①②是初始化阶段，需对种群大小、终止条件、算法参数等进行初始化；步骤③～⑤读取案例数据和产生初始的种群；下一步是算法的迭代过程，在此将执行漂移和波动，并找最优解，其中步骤⑦ 根据适应度对粒子进行分类，步骤⑧～表示找到当前最优解和更新最优解未变的次数；步骤～为更新算法的主操作，包括粒子半径、环境温度、漂移和波动强度等；最后，步骤～漂移和波动所有的粒子，构建新的解.算法1最大未更新迭代次数为停机条件的代码，用最大迭代次数做终止条件时，将步骤⑥～的最大未更新迭代次数的地方对应的替换为迭代次数即可.

2.2混合遗传算法

本文所用混合遗传算法包括贪心法遗传算法GAG、模拟退火遗传算法GASA、爬山法遗传算法GAHC[1].这3种混合算法以及遗传算法均采用双染色体编码的方法来表示问题的解，其中一个染色体表示城市集合;另一个染色体为旅行者[1].混合遗传算法都采用交叉算子和变异算子对城市染色体进行交叉和变异操作，通过该方式可以产生问题的最优解.在求解过程中适应度值可用来表示问题的解.

从图1中可看出，3种混合的遗传算法求解MBTSP的步骤比较相似，首先是编码和产生初始种群，然后计算适应度值，并选择最优个体a，之后运用贪心法、爬山法或模拟退火法进行优化，并产生个体b，如果b的适应度值大于a的适应度值，则将b替换a，如果满足终止条件，输出结果，否则，执行选择、交叉和变异操作.

Fig. 1 The steps of GAG,GAHC and GASA for MBTSP图1 GAG，GAHC和GASA求解MBTSP的步骤[1]

下面主要介绍GAG和GASA的步骤或原理，GAHC的具体介绍可参考CTSP文献[1].

1) 贪心法遗传算法GAG[1].在每个步骤中，由一个贪心算法做出的决策应该不能取得一个全局的最优解而只是一个局部的最优解.但是，因为它避免了去寻找最优解的一些可能的开销，所以它能快速地得到一个满意的解.在遗传算法的第1步，我们使用它随机产生初始种群的个体.一个高质量的初始种群，能加速遗传算法的种群演化，快速获得一个满意的解，我们把这种改进的算法叫做贪心初始化的遗传算法GAG.对于MBTSP问题，一个城市访问需要满足一个邻近度，也就是，当前城市的旅行者选择下一个最靠近它的城市，通过重新排列顺序可优化一个解.GAG初始种群的产生过程为：

步骤1.确定当前初始种群的个体数量是否等于集合数量N，如果等于，则退出；

步骤2.随机产生一个城市序列，随机赋值独享城市到指定的旅行者，结果序列命名为个体a；

步骤3.通过最短距离的方法来记录a的城市序列，最小化开销和获得个体a′；

步骤4.检测在种群中是否存在a′，如果存在返回步骤2，否则，将其插入到种群，并返回到步骤1.

2) 模拟退火遗传算法GASA[1].是一种元启发式算法，在大的搜索空间中，它适合于全局优化问题，该问题定位于给定函数的全局最优解的好的邻近值.尤其在搜索过程中，根据Metropolis准则，它不仅接受一个好的解还接受一个差的解.它能跳出局部最优解的区域和保证它的收敛性能，模拟退火被用来改进上述GAG问题的收敛性.MBTSP的解和最优解类似于每个粒子的状态和模拟退火中的最低的能量状态.MBTSP的目标函数到最短路径和模拟退火的能量函数相对应.通过设置合适的初始化温度和按照某些设计的冷却规划，能解决MBTSP问题.

3 实验与分析

本文的实验是用Java平台开发，运行环境为AMD AthlonTMⅡ X4 640 3.01 GHz处理器和3.25 GB内存.本文使用混合算法求解该问题，算法参数的选取依据大量的实验，即该参数组合使算法求解问题的求解结果较好，混合伊藤算法和蚁群算法参数设置情况为：种群m=30，α和β分别为4.7与3.8，随机选择概率p=0.55，初始温度T=1 000；混合遗传算法与遗传算法的参数与CTSP论文[1]对应的算法相同.实验所有算法的最大未更新迭代次数设置为60，最大迭代次数为2 000.文献[18-19]对算法对比的停机条件或终止条件做了介绍，并指出相同的适应函数评价次数也难以做到公平的比较.本文算法的停机条件相同，用两种方式的停机条件分别做实验，可使对比更全面，第1种终止条件是所有算法执行相同的最大迭代次数，第2种是执行相同的最大未更新迭代次数.表1为在3种不同尺度下不同算法求解MBTSP实验所用数据.

Table 1 The Experiment Data for MBTSP表1 MBTSP的实验数据

表1中n表示MBTSP的城市数量，m表示旅行者的数目，e表示共享的城市数量，s表示MBTSP起始点数.其中n的取值为21～665，m的取值在2～33.表1的数据是根据原始的TSP数据，按照MBTSP数据要求制作而成.

图2表示当n=51和m=5时，以相同最大未更新迭代次数为终止条件的6种算法求解MBTSP的最优路线图.该实例运行30次，分别求得6种算法求解MBTSP的最优解、最差解、平均求解质量(平均解)和求解时间.图2中，6种算法求解MBTSP问题的具体情况为：1)GA.最优解24.12，最差解34.20，平均求解质量29.31，求解时间0.10；2)GAG.最优解21.92，最差解35.79，平均解29.78，求解时间0.10；3)GAHC.最优解18.00，最差解31.75，平均解26.45，求解时间0.13；4)GASA.最优解24.09，最差解31.57，平均解28.07，求解时间1.33；5)ACO.最优解51.03，最差解56.52， 平均解51.93，求解时间0.31；6)HITO.最优解19.69，最差解29.05，平均解23.21，求解时间0.73.从该实例的数据对比可看出，GAHC的最优解在6种算法中表现最好，HITO 求解该实例的平均解要好于GAHC和GASA 等算法，在6种算法中最优，SAGA求解所用时间最长，其次是HITO.

表2为不同尺度下，GA,GAG,GAHC求解MBTSP的实验数据对比，其中GAG,GAHC来自CTSP的论文[1].求解质量或求解精度的单位km，求解时间单位s，n为城市数量，取值在21～665，m表示旅行者数，取值在2～33，最优(Best)、最差(Worst)、均值(Average)分别为算法运行30次的最优解、最差解和平均解，时间(Time)为算法运行30次的平均时间.从表2可以看出，3种算法之中，GAHC在3种尺度下的最优解、平均解最好，但GA和GAG的求解所用时间要少于GAHC.图3和图4是用表2和表3六种算法求解MBTSP的平均解的数据生成对比图，通过图中的曲线可以看出不同实例下平均解的大小.图3～4为6种算法求解MBTSP的求解质量或求解精度数据对比图.

图3横轴表示不同实例的序号，对应表1中的实例，纵轴表示平均求解质量或精度，该数据为表中的均值(平均解).从图3可以看出GAHC的求解质量最优，GASA和HITO也表现出较好的性能，ACO在6种算法中的求解质量最差.图4表示6种算法求解MBTSP的求解质量或求解精度实验结果对比图.

图4中，横轴表示不同实例的序号，对应表1中的实例，纵轴表示平均求解质量.从图4可以看出，ACO的解的质量最差，GAHC的求解质量最好.

表3表示GASA,ACO和HITO求解MBTSP的实验对比，Best,Worst,Average,Time分别表示算法运行30次的最优解、最差解、平均解和平均求解时间.

图5和图6表示算法求解MBTSP的求解时间对比情况，图中横轴表示不同实例的序号，对应表1中的实例，纵轴表示平均求解时间.该2图是由表2和表3的时间数据生成.从图5～6中可以看出，在3种不同尺度下，GASA和HITO所用时间较长，GAG和GA所用时间最短，GAHC求解时间较短.从表2～3和图5～6中可以看出，4种混合算法之中，GAHC和GAG所用求解时间较短，要好于其他的对比混合算法GASA和HITO，HITO所用时间要长于ACO.

Fig. 2 Solving optimum routes of the case with n=51 and m=5 using GA,GAG,GAHC,GASA,ACO and HITO图2 n=51,m=5时GA,GAG,GAHC,GASA,ACO和HITO求解MBTSP的最优路线图

ScaleInstancenmGAGAGGAHCBest∕kmWorst∕kmAverage∕kmTime∕sBest∕kmWorst∕kmAverage∕kmTime∕sBest∕kmWorst∕kmAverage∕kmTime∕sSmall12125．9210．267．860．475．9210．267．610．475．9210．267．480．58231211．5318．4514．690．5410．9316．7214．310．5511．3815．0013．180．87331311．6620．0815．020．6311．6619．6815．500．6111．5820．5114．720．90441212．7017．9414．940．6713．0118．4315．630．6810．3413．7512．401．23541315．6121．4918．500．7214．6321．0718．050．7314．6319．4716．111．35641420．4726．1223．130．8319．3425．6622．530．8419．3425．2221．791．42751318．4027．1922．610．8518．9726．1222．150．8415．1222．7318．151．73Medium851418．0027．9422．970．9018．0029．1222．530．9015．5925．8820．531．82951519．3831．2325．930．9620．4331．7525．330．9718．0029．9823．761．881076324．6328．6226．791．1523．8330．4525．971．1511．9216．4715．012．831176426．6832．0429．641．2126．6834．0529．751．2217．2520．9319．483．151276521．8327．7825．051．2919．5528．2224．341．2616．2420．3618．153．301376632．8338．0035．381．3330．9537．3334．581．3129．0034．3931．343．4314101425．9431．8227．801．5525．9431．0527．671．5814．1722．2618．144．55Large15101534．0041．1737．741．5732．1439．9737．301．5820．0327．2221．114．6116101631．4436．8533．861．5931．4136．6333．801．6519．5423．4521．274．9817101728．3435．0431．241．7727．1434．9230．221．7623．1432．8226．645．211820699210．0010108．009782．133．769438．0010718．009860．803．728003．0011214．008641．1318．2219431129700．0011390．0010674．0010．129837．0011451．0010684．209．758892．0010191．009632．3675．0620547149457．0010924．0010073．7013．689367．0010793．0010100．4613．296685．008516．006998．10129．23216122311268．0012961．0012095．3616．9911215．0012844．0011960．3317．569154．0011070．009795．80194．62226653314402．0015281．0014847．1021．5914379．0015479．0014858．9320．8914127．0014825．0014590．56270．19

Fig. 3 The solving solution quality comparison of the algorithms for MBTSP图3 算法求解MBTSP的求解质量对比图

Fig. 4 The solving solution quality comparison of the algorithms for MBTSP图4 算法求解MBTSP的求解质量对比图

ScaleInstancenmGASAACOHITOBest∕kmWorst∕kmAverage∕kmTime∕sAverage∕kmTime∕sBest∕kmWorst∕kmAverage∕kmTime∕sSmall12125．926．986．069．1522．902．385．538．397．653．74231212．0215．1914．0412．4241．594．9313．2814．0413．407．68331312．5314．6513．8613．3243．944．2916．1418．7817．786．60441214．8217．6216．5317．1248．928．4216．6318．6417．1713．48541314．9118．7317．7818．2959．517．2019．6225．6221．8410．80641420．5222．9721．5319．3143．646．6520．3521．9120．769．84751322．0625．1323．6921．6159．7210．7522．9426．3925．2316．26Medium851420．3025．0723．6422．8755．189．9321．4024．1623．3714．44951522．2327．0125．0624．0651．889．5718．6121．6220．3313．681076323．7327．8926．4833．9859．5122．6423．9328．9027．8834．931176427．2131．5929．8435．7053．7620．5027．4130．3229．0530．861276523．6026．8125．5036．6155．5719．3024．0628．1725．8428．561376634．4436．9836．0037．9954．8618．6631．0039．2937．0927．3114101427．0129．9128．6843．6955．7234．3623．4227．2225．3753．80Large15101536．1439．0537．8445．8168．4432．2529．7836．4833．1848．7216101633．0534．9833．9947．7961．0130．6831．0336．6634．0246．1217101730．7434．8132．8749．6159．0530．1030．7236．5933．4644．551820697642．008921．008153．33113．1719126．00110．2010093．0012300．0011425．00172．0719431129184．0010535．009934．03267．6717664．00435．089877．0013940．0011367．36659．0320547147237．007591．007458．93379．6618556．00668．278192．0012971．0011270．301018．3121612238933．0011261．009744．53505．8418553．00803．2612081．0014368．0013566．131173．01226653314342．0015333．0014766．93667．1219113．00953．6215015．0016008．0015826．101346．53

Fig. 5 The time comparison of the algorithms for MBTSP图5 算法求解MBTSP的求解时间对比

Fig. 6 The time comparison of the algorithms for MBTSP图6 算法求解MBTSP的求解时间对比

为了充分验证算法的有效性，本文运用求解TSP问题的文献[20]给出的最优解方差PDbest和平均解方差PDav，对6种不同算法求解MBTSP问题进行显著性分析.PDbest计算方法为算法当前最优解减去已知最优解，然后除以已知最优解，再乘以100；PDav计算方法是算法当前平均最优解减去已知平均最优解，然后除以已知平均最优解，再乘以100[20].

表4表示用最大未更新迭代次数为停机条件的GA,GAG,GAHC,GASA,ACO和HITO求解MBTSP的实验结果对比数据.

本文选择表2和表3的最优解和平均解的数据做方差分析，GA,GAG,GAHC,GASA,ACO和HITO求解MBTSP的方差数据，计算结果如表5所示.

表2和表3中，当前最优解为算法求解MBTSP的最优解，对应着表中相应算法的最优解，已知最优解为6种算法求解该问题的最优解的最优值，即6种算法求得最优解的最小值，表中GAHC最优解的最优值出现的次数最多；当前平均最优解是算法求解该问题的平均最优解，已知最优解为6种算法中求得的最好的平均最优解，表中6种算法中GAHC在该方面结果最好.在以上数据的基础上，通过计算可求得6种不同算法求解MBTSP的方差.

表4表示用最大未更新迭代次数为停机条件的6种不同算法求解MBTSP问题的实验对比数据，表中Average为算法运行30次的平均求解质量(平均解)，Time为算法运行30的平均求解时间.从表4中3种尺度的实验数据对比可看出，在6种算法中，GAHC最好均值出现的次数最多，其次是GASA和HITO，HITO求解质量要好于ACO.从求解时间来看，GA,GAG和ACO求解该问题的运行时间较短.

Table 4 Experiment Data of Algorithms for MBTSP with Same Maximum No-update Iterations as Stopping Condition表4 相同最大未更新迭代次数为停机条件的算法求解MBTSP的实验数据

Table 5 Experiment Deviation Data of Algorithms for MBTSP with Same Maximum Iterations as Stopping Condition表5 相同最大迭代次数为停机条件的算法求解MBTSP的实验方差数据 km

表5表示GA,GAG,GAHC,GASA,ACO和HITO求解MBTSP的方差数据，表中Best为最优解方差PDbest，Average为平均解方差PDav，表中分别对小尺度、中尺度和大尺度不同算法求解该问题的方差数据求平均值，最后又给出3种尺度的方差数据总的平均值.从表5可以看出，GAHC的平均PDbest与PDav值最小，GA,GAG,GAHC的该平均值相差不大，HITO求解该问题的平均PDbest与PDav值小于ACO.

从本节实验数据与分析可看出，在求解小尺度到大尺度的MBTSP问题时，GAHC的求解精度或求解质量优于其他6种算法，GASA与HITO在该方面也表现较好，从求解时间来看，GA,GAG与ACO的时间较短.从表2～5数据可以看出，各种算法在求解MBTSP时，使用不同尺度的实例，会表现出不同的性能，GAHC在求解精度或求解质量方面表现最好，在6种算法中，最优求解质量出现的次数最多.GAHC,GASA和HITO是较优的元启发式算法，在求解组合优化问题中，表现出较好的性能，本文通过实验与数据分析可看出，GAHC在求解MBTSP中求解质量表现最好，其次是GASA和HITO.在求解MBTS问题的不同尺度的实例时，6种算法表现出不同的特点.

HITO是一种较新的群体智能算法，该算法是蚁群算法与伊藤算法的混合算法，与ACO相类似，都是运用蚂蚁觅食的原理设计相关的概率图模型，但HITO与ACO不同，它可以利用伊藤算法的波动与漂移操作来更新图模型，从而进一步提升了求解问题的能力.从本文的求解结果可以看出，HITO在求解MBTSP的求解质量要好于ACO.GAHC是一种爬山算法和遗传算法结合后的混合算法，在求解组合优化问题中也表现出较好的性能，从本文实验可看出，该算法在求解MBTSP的求解质量表现最好.

4 结语与展望

本文提出了一种新的组合优化问题模型，可对含有多个旅行商的优化问题建模和优化，为了扩展该问题模型的应用领域，研究和设计先进的算法求解MBTSP问题有一定的意义，因此，本文将混合伊藤算法和遗传算法应用于求解该问题，通过实验验证与分析表明，6种算法在求解MBTSP问题上是有效的，GAHC在求解该问题的求解质量要优于其他的对比算法，HITO求解质量要好于ACO.

未来的研究工作主要从3方面开展：1)开发和研究更先进的算法，来求解MBTSP问题，使其在求解质量和求解速度方面有所提高；2)研究更大规模的MBTSP，分析各种算法在求解更大规模该问题的性能和规律；3)探索和研究MBTSP其他的应用和相关的变化模型，使其可以建模更加复杂的优化问题，并有更多的应用领域.

[1] Li Jun, Zhou Mengchu, Sun Qirui, et al. Colored traveling salesman problem[J]. IEEE Trans on Cybernetics, 2015, 45(11): 2390-2401

[2] Dong Wenyong, Cai Yongle, Wang Yufeng, et al. Discrete ITO algorithm to the coloured travelling salesman problem[J]. International Journal of Wireless and Mobile Computing, 2016, 11(2): 157-165

[3] Li Jun, Sun Qirui, Zhou Mengchu, et al. A new multiple traveling salesman problem and its genetic algorithm-based solution[C] //Proc of the 2013 IEEE Int Conf on Systems Man and Cybernetics. Piscataway, NJ: IEEE, 2013: 1-6

[4] Meng Xianghu, Li Jun, Zhou Mengchu, et al. Population-based incremental learning algorithm for a serial colored traveling salesman problem[J]. IEEE Trans System, Man, Cybernetics: System, 2016, PP(99): 1-12

[5] Ahmed Z H. A hybrid genetic algorithm for the bottleneck traveling salesman problem[J]. ACM Trans on Embedded Computing Systems, 2013, 12(1): No.9

[6] Plante R D, Lowe T J and Chhandrasekaran R. The product matrix traveling salesman problem: An application and solution heuristic[J]. Operations Research, 1987, 35(5): 772-783

[7] John L R. The bottleneck traveling salesman problem and some variants[D]. Burnaby, BC: Master of Science of Simon Fraser University, Cannada, 2010, 21-23

[8] John L R, Abraham P P. The balanced traveling salesman problem[J]. Computer & Operations Research, 2011: 868-875

[9] Qian Chao, Tang Ke, Zhou Zhihua. Selection hyper-heuristics can provably be helpful in evolutionary multi-objective optimization[G] //LNCS 9921: Proc of the 14th Int Conf on Parallel Problem Solving from Nature. Berlin: Springer, 2016: 835-846

[10] Zhang Defu, Cai Sifan, Ye Furong, et al. A hybrid algorithm for a vehicle routing problem with realistic constraints[J]. Information Science, 2017, 394/395: 167-182

[11] Lin Qiuzhen, Chen Jianyong, Zhan Zhihui, et al. A hybrid evolutionary immune algorithm for multiobjective optimization problems[J]. IEEE Trans on Evolutionary Computation, 2016, 20(5): 711-729

[12] Lin Geng, Zhu Wenxing, Ali M M. An effective hybrid memetic algorithm for the minimum weight dominating set problem[J]. IEEE Trans on Evolutionary Computation, 2016, 20(5): 892-906

[13] Dong Wenyong. The multi-objective ITO algorithms[C] //Proc of the 2nd Int Symp on Intelligence Computation and Applications (ISICA). Piscataway, NJ: IEEE, 2007: 21-23

[14] Dong Wenyong. Time series modeling based on ITO algorithm[C] //Proc of the 3rd Int Conf on Natural Computation. Piscataway, NJ: IEEE, 2007: 398-402

[15] Dong Wenyong, Lei M, Yu Ruiguo. BBOB-benchmarking: A new evolutionary algorithms inspired by ITO process for noiseless function tested[J]. Journal of Computational Information Systems, 2011: 2195-2203

[16] Dong Wenyong, Zhang Wensheng, Yu Ruiguo. Convergence and runtime analysis of ITO algorithm for one class of combinatorial optimization[J]. Chinese Journal of Computers, 2011, 34(4): 636-646 (in Chinese)(董文永, 张文生, 于瑞国. 求解组合优化问题伊藤算法的收敛性和期望收敛速度分析[J]. 计算机学报, 2011, 34(4): 636-646)

[17] Yi Yunfeng, Cai Yongle, Dong Wenyong, et al. Improved ITO for multiobjective real-time vehicle routing problem with customers satisfaction[J]. Acta Electronica Sinica, 2015, 43(10): 2053-2061 (in Chinese)(易云飞, 蔡永乐, 董文永, 等. 求解带用户满意度的多目标实时车辆路径问题的改进伊藤算法[J]. 电子学报, 2015, 43(10): 2053-2061)

[18] Engelbrecht A P. Fitness function evaluations: A fair stopping condition?[C] //Proc of IEEE Swarm Intelligence Symp on Swarm Intelligence. Piscataway, NJ: IEEE, 2014: 1-8

[19] Mernik M, Liu S H, Karaboga D, et al. On clarifying misconceptions when comparing variants of the artificial bee colony algorithm by offering a new implementation[J]. Information Science, 2015, 291: 115-127

[20] Zhang Hongguang, Zhou Jie. Dynamic multicale region search algorithm using vitality selection for traveling salesman problem[J]. Expert Systems with Applications, 2016, 60: 81-95

HybridAlgorithmsforMulti-ObjectiveBalancedTravelingSalesmanProblem

Dong Xueshi, Dong Wenyong, and Wang Yufeng

(ComputerSchool,WuhanUniversity,Wuhan430072)

Balanced traveling salesman problem (BTSP), a variant of traveling salesman problem (TSP), is another combination optimization problem, which can be applied in many fields such as the optimization problem for gas turbine engines (GTE). BTSP can only model optimization problems with the single traveling salesman and task, but can’t model and optimize the problem with multiple salesmen and tasks at the same time. Therefore, this paper firstly provides a multi-objective balanced traveling salesman problem (MBTSP) model, which can model the optimization problems with multiple salesmen and tasks. Specifically it can be applied to the real-world problems with multiple objectives or individuals, for example, the optimization for multiple GTE. Some literatures have proved that ITO algorithm and genetic algorithms can show better performance in solving combination optimization problems, therefore, the paper utilizes the hybrid ITO algorithm (HITO) and hybrid genetic algorithm (GA) to solve MBTSP. For HITO, it utilizes ant colony optimization (ACO) to produce a probabilistic generative model based on graph, and then uses the drift and volatility operators to update the model, and obtains optimum solution. For the hybrid GA, the first is improved by greedy method called GAG, the second GA is optimized by incorporating hill-climbing named GAHC, and the final one is GASA. In order to effectively test the algorithms, the paper makes extensive experiments using small scale to large scale MBTSP data. The experiments show that the algorithms are effective and reveal the different characteristics in solving MBTSP problem.

hybrid ITO (HITO) algorithm; hybrid genetic algorithms; balanced traveling salesman problem (BTSP); multi-objective balanced traveling salesman problem (MBTSP); ant colony optimization (ACO)

Dong Xueshi, born in 1985. PhD candidate in Computer School, Wuhan University. His main research interests include intelligent computing and simulation optimization.

Dong Wenyong, born in 1973. Professor in Computer School, Wuhan University. His main research interests include intelligent computing, system control and simulation optimization.

Wang Yufeng, born in 1982. PhD candidate in Computer School, Wuhan University. His main research interests include intelligent computing and simulation optimization.

2017-05-23；

：2017-06-25

国家自然科学基金项目(61672024,61170305) This work was supported by the National Natural Science Foundation of China (61672024, 61170305).

董文永(dwy@whu.edu.cn)

TP301