一种求解多目标旅行商问题的混合进化算法

王 娜, 刘 生, 王洪峰

(1. 沈阳师范大学 计算机与数学基础教学部, 沈阳 110034;2. 东北大学 信息科学与工程学院, 沈阳 110819)

一种求解多目标旅行商问题的混合进化算法

王 娜1.2, 刘 生2, 王洪峰2

(1. 沈阳师范大学 计算机与数学基础教学部, 沈阳 110034;2. 东北大学 信息科学与工程学院, 沈阳 110819)

许多科学与工程优化问题往往需要转化为多目标旅行商问题进行求解,由于目标函数之间的冲突性,使得这类问题不存在能够优化所有目标函数的唯一最优解,而是存在一个Pareto最优解集或者Pareto Front。为了获得一个高质量的Pareto最优解集,提出了一种基于蚁群优化和差分进化的混合多目标进化算法。在提出的算法中,一方面采纳分解机制利用蚁群优化算子实现对Pareto最优解的开发,另一方面采纳拥挤度概念利用差分进化算子实现对Pareto Front的探索。通过对一组标准测试算例的仿真实验,结果表明所提出的算法比现有的算法能够获得分布性和收敛性更优的Pareto解集。

旅行商问题; 进化多目标优化; 蚁群优化; 差分进化

0 引 言

旅行商问题是运筹学领域中一类经典的组合优化问题,很多科学和工程问题往往可以转化为这类问题进行求解。由于实际应用问题中总是需要考虑多个优化目标,使得越来越多的学者开始关注多目标旅行商问题的研究工作[1-3]。然而由于目标函数之间通常都是相互冲突的,使得这种多目标优化问题中不存在一个能够优化所有目标函数的最优解,而是存在一组多个目标函数之间平衡解,即Pareto最优解[5]。

近年来,进化算法被广泛用于求解各种多目标优化问题[5-7]。作为一种基于种群机制的元启发式方法,多目标进化算法的目标是通过一次运行就能够获得一组分布均匀的Pareto最优解。这也就意味着在整个算法迭代过程中需要考虑两种不同的搜索,一种可以认为是对更好的非支配解的开发性(exploitation)搜索,另一种可以认为是对更优分布的非支配解集的探索性(exploration)搜索。值得注意的是,这2种搜索行为在目前的文献中很少同时考虑。

于是,本文将2种不同的进化算法(即蚁群优化ACO[8]和差分进化DE[9])思想结合起来,充分利用蚁群优化算子在旅行商问题上的高效性和差分进化算子在保持种群多样性上的有效性,设计一种混合多目标进化算法来求解多目标旅行商问题。

1 提出的算法

1.1 基本思想

在本文所提出的算法中,2种主要的策略被采用。一方面,采纳分解的机制将一个多目标优化问题构造出若干个单目标子问题,在借鉴文献[10]中算法思想的基础上,通过利用蚁群优化算子对主种群进行更新迭代,以获得所构造的这些单目标子问题的最优解,即是原来多目标问题的Pareto最优解。在算法具体实现过程中,根据一组均匀分布的权重向量(其数量是预先设定的),利用Tchebycheff函数将一个多目标TSP问题构造出一系列单目标子问题。

另一方面,采纳文献[11]中多目标进化算法设计思想中拥挤度的概念,通过利用差分进化算子对外部种群(即所获得的非支配解集)进行更新,以保证所获得的非支配解集具有更好的分布性。这里需要说明的是由于差分进化算子是针对实数编码个体的,这就需要将实编码个体转化为旅行商问题的解。在算法具体实现过程中,根据数值的大小,将原来的实数编码个体转换为顺序编码个体,以获得旅行商问题的一个解。

1.2 算法流程

图1给出了本文所提出算法流程的伪码图。在算法初始化阶段,首先需要根据一组预先产生的权重向量,将原有的多目标问题构造出相应数量的单目标子问题;然后根据构造的子问题初始化对应的蚂蚁个体,并利用权重向量的相似性将所有蚂蚁个体分组;最后初始化外部种群。在算法迭代过程中,首先根据每个蚂蚁对应的启发信息矩阵和每组蚂蚁共享的信息素矩阵产生新解,然后根据产生的新解更新外部种群,对外部种群执行差分进化运算,最后根据蚁群优化和差分进化算子的运行效果更新每组蚂蚁共享的信息素矩阵。

Proceduretheproposedalgorithm:BeginGenerateanumberofsingle-objectivesubproblemsbasedonasetofNweightvectors;InitializeapopulationofNantsforeachgeneratedsubproblem;DivideNantsintoKgroupsbasedonthesimilaritiesoftheircorrespondingweightvectors;Initializeanexternalpopulation;Repeat GenerateNsolutionsviaexecutingACOoperationsonNantsinthemainpopulation; Updatetheexternalpopulationviathenewgeneratedsolutions; ExecuteDEoperationsontheexternalpopulation; Updatethepheromonematrixforeachgroupofants;Untilaterminationconditionismet.End

图1本文所提出算法流程的伪码
Fig.1 Pseudo-code for the proposed algorithm in this paper

1.3 实现步骤

Step1 初始化,构造一组子问题(i=1,…,N);随机产生一组蚂蚁,蚂蚁i对应子问题i,初始化每个蚂蚁对应的启发信息矩阵ηi;根据蚂蚁对应权重向量的相似性,将蚂蚁分成K组,初始化每个小组j(j=1,…,K)的信息素矩阵τj;初始化外部种群。

Step2 构造解,对于每个蚂蚁(i=1,…,N),用概率函数(表示为xi,ηi,τj的函数)求出解yi,计算其目标函数向量。对于每个蚂蚁i,更新当前最好解xi。y是在所有邻近蚂蚁找到的解中使得g(.|λi)的值最小的解。如果y没被用于更新其他旧解,且g(y|λi)

Step3 更新外部种群,对于每个yi,如果外部种群中没有解支配yi,把yi添加到外部种群,移除其中所有被yi所支配的解。

Step4 差分进化运算:对外部种群进行N′次差分进化,利用每次产生新解xp更新外部种群,计算拥挤距离,拥挤距离大的被添加进外部种群,拥挤距离小的被删除,限定外部种群大小。

Step5 更新对应小组信息素:对于每个小组j,更新信息素矩阵τj,小组j中的蚂蚁在Step 2中获得的解,且在Step 3中被添加到外部种群,则该蚂蚁的解用来更新信息素;如果产生的新解xp,对每个小组j,找出使得g(xp|λj)值最小的小组q,用xp更新小组q的信息素。

Step6 停止准则:如果满足问题的停止准则,停止运算。

2 实验结果与分析

为了验证本文所提出的算法(后文称之为ACO-DE)在求解多目标旅行商问题时的性能,选择了文献中4种具有代表性的多目标进化算法作为比较算法,其中:MODE属于早期的多目标差分进化算法[12],MOSADE是一种采用自适应策略的多目标差分进化算法[13],NSGA-II[11]和MOEA/D[14]是2种最为经典的多目标进化算法,上述算法均可以被用于求解本文所研究的多目标旅行商问题。

2.1 实验设置

本文实验中所采用的测试函数均是根据TSPLIB中benchmark问题构造的,选择了5个100个城市的旅行商benchmark问题,即KroA100、KroB100、KroC100、KroD100、KroE100。通过两两组合的方式构造出多目标旅行商问题,例如KroAB100是由KroA100和KroB100这2个benchmark问题组合而成,其他的以此类推。

本文所提出的ACO-DE算法参数设置如下:蚂蚁总数N=24,小组总数K=3,邻近蚂蚁数量T=10,信息素挥发系数ρ=0.95,信息启发式因子α=1,期望启发因子β=2,r=0.9(随机数大于r,用轮盘赌方式选择下一个城市),ε=1/2n(信息素最小值与信息素最大值的比),Δ=0.05×τmax(反应当前最优值在状态转移概率中的作用),变异算子范围是0.1～0.9,交叉算子范围是0.1～1.0。所有对比算法的相关参数均采用其初始设置方法。所有算法均利用Win7系统下Eclipse环境下实现,算法测试的硬件环境为3.30GHz的因特尔处理器、4GB内存的HP台式机。

为了更好的检验各种算法在多目标旅行商问题上的性能,选取文献[15]中2个常用的多目标算法性能指标作为算法对比的评价指标。

1) IGD指标(Inverted generational distance):该指标通过从真实Pareto最优解集到算法获得的非支配解集的平均距离来评估该算法的性能。假定p*是理想Pareto front上的一组均匀采样,是由算法获得的一组非支配解集,则IGD指标定义如下:

其中:d(v,P)为v与解集P中与之距离最近点之间的Euclidean距离;|p*|为p*中Pareto最优解的个数。

2) Hypervolume指标:该指标利用算法获得的非支配解集中所有点与参考点在目标空间所围成的超立方体体积来评估算法的性能。若P={p1,p2,…,pN}为算法获得的一组非支配解,r为参考点,满足pir,∀i=1,2,…,N,则Hypervolume指标定义如下:

其中:N为非支配解的个数;Leb(S)为解集S的勒贝格测度;vi为第i个非支配解和参考点围成的超立方体体积。

2.2 实验结果分析

为了公平合理地比较本文所提出的算法与比较算法的性能,所有算法均以3 000次估值作为停止条件,每种算法分别对每一算例求解30次,取30次运行结果的平均值作为其性能指标。

表1给出了所有算法在IGD指标方面的实验结果,从中可以看出,本文所提出的ACO-DE算法的性能远远优于其他4种对比算法的性能。例如,在KroAB100算例中,ACO-DE算法的IGD性能指标的均值为4 220,远远小于其他4种对比算法的平均性能,分别为18 254、35 198、55 395和8 772。

表1 5种算法在不同算例上IGD指标的实验结果Tab.1 Experimental results of five algorithms in test instances with IGD index

表2给出了所有算法在Hypervolume指标方面的实验结果,从表中能够发现本文所提出的ACO-DE算法在所有算例上Hypervolume指标的均值都是1.0,这也就意味着ACO-DE算法总是能够比其他4种对比算法获得收敛性和分布性更好的非支配解集。

表2 5种算法在不同算例上Hypervolume指标的实验结果Tab.2 Experimental results of five algorithms in test instances with Hypervolume index

3 结 论

为了有效求解多目标旅行商问题,本文提出了一种基于蚁群优化和差分进化的混合多目标进化算法。在这种算法中,一方面采纳分解的机制利用蚁群优化算子搜索一组非支配解,另一方面采用拥挤度的思想利用差分进化算子对所获得非支配解进行充分开发,以保证获得更好的分布性,通过利用一组标准测试函数进行仿真实验,实验结果表明本文所提出的算法比文献中现有算法具有更好的性能。

[ 1 ]肖晓伟,肖迪,林锦国,等. 多目标优化问题的研究概述[J]. 计算机应用研究, 2011,28(3):805-809.

[ 2 ]CHENG Jixang,ZHANG Gexiang,LI Zhidan,et al. Multi-objective ant colony optimization based on decomposition for bi-objective traveling salesman problems[J]. Soft Computing, 2012,16(4):597-614.

[ 4 ]张瑞芳,王海军. 广义凸条件下一类多目标优化问题的对偶[J]. 沈阳师范大学学报(自然科学版), 2014,32(4):482-485.

[ 5 ]ANGUS D,WOODWARD C. Multiple objective ant colony optimization [J]. Swarm intelligence, 2009,3(1):69-85.

[ 6 ]WANG Hongfeng,FU Yaping,HUANG Min,et al. Multiobjective optimization design for enterprise system operation in the case of schedulingproblem with deteriorating jobs[J]. Enterprise Information Systems, 2016,10(3):268-285.

[ 7 ]ZHOU Aimin,QU Boyang,LI Hui,et al. Multiobjective evolutionary algorithms: a survey of the state of the art[J]. Swarm Evolutionary Computation, 2011,1:32-49.

[ 8 ]DORIGO M,GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation, 1997,1(1):53-66.

[ 9 ]STORN R,PRICE K.Different evolution-A simple and efficient adaptive scheme for global optimization over continuous spaces[R]. International Computer Science Institute, Berkley, 1995.

[10]KE Liangjun,ZHANG Qqingfu,BATTITI R. MOEA/D-ACO: A multiobjective evolutionary algorithm using decomposition and ant colony[J]. IEEE Transactions on Systems Man and Cybernetics Part A-Systems and Human, 2013,99:1-15.

[11]DEB K,PRATAP A,AGARWALl S,et al. A fast and elitist multi-objective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002,6(2):182-197.

[12]BABU B,CHAKOLEP G,MUBEENJH S. Multiobjective differential evolution (MODE) for optimization ofadiabatic styrene reactor[J]. Chemical Engineering Science, 2005,60(17):4822-4837.

[13]WANG Yaonan,WU Lianghong,YUAN Xiaofang. Multi-objective self-adaptive differential evolution with elitist archive and crowding entropy-based diversity measure[J]. Soft Computing, 2009,14 (3):193-209.

[14]ZHANG Qingfu,LI Hui. MOEA D: A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007,11(6):712-731.

[15]HUBAND S,HINGSTON P,BARONE L,et al. A review of multiobjective test problems and a scalable test problem toolkit[J]. IEEE Transactions on Evolutionary Computation, 2006,10(5):477-506.

Ahybridevolutionaryalgorithmformultiobjectivetravellingsalesmanproblem

WANGNa1.2,LIUSheng2,WANGHongfeng2

(1. Department of Computer and Mathematical Teaching, Shenyang Normal University, Shenyang 110034, China; 2.Information Science and Engineering College, Northeastern University, Shenyang 110819, China)

Many scientific and engineering problems can always transfer to multiobjective travelling salesman problems (TSPs), where there is only a set of Pareto optimal solution or Pareto front, rather than one single optimal solution that can optimize all objective functions simultaneously, due to the existence of multiple conflicting objectives. In this paper, a hybrid multiobjective evolutionary algorithm, which hybridizes the mechanism of ant colony optimization (ACO) and differential evolution (DE), is proposed for solving multiobjective TSP. Two different strategies are employed in the proposed algorithm, that is, ACO operators are used to make an exploration for a set of Pareto optimal solutions based on a decomposition mechanism and DE operators are used to makean exploitation to obtain a better Pareto front. Based on the experiments on a series of test instances, the proposed algorithmshows a Pareto solution set with better distribution and convergence than those from several state-of-the-art algorithms.

traveling salesman problem; evolutionary multiobjective optimization; ant colony optimization; differential evolution

2017-06-19。

国家自然科学基金资助项目(71671032)。

王 娜(1979-),女,辽宁盘锦人,沈阳师范大学讲师,东北大学博士研究生。

1673-5862(2017)04-0425-05

O229

A

10.3969/ j.issn.1673-5862.2017.04.009