一种求解多目标旅行商问题的混合进化算法
王娜;刘生;王洪峰
【摘 要】Many scientific and engineering problems can always transfer to multiobjective travelling salesman problems (TSPs),where there is only a t 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 propod for solving multiobjective TSP.Two different strategies are employed in the propod algorithm,that is,ACO operators are ud to make an exploration for a t of Pareto optimal solutions bad on a decomposition mechanism and DE operators are ud to makean exploitation to obtain a better Pareto front.Bad on the experiments on a ries of test instances,the propod algorithmshows a Pareto solution t with better distribution and convergence than tho from veral state-of-the-art algorithms.%许多科学与工程优化问题往往需要转化为多目标旅
行商问题进行求解,由于目标函数之间的冲突性,使得这类问题不存在能够优化所有目标函数的唯一最优解,而是存在一个Pareto最优解集或者Pareto Front.为了获得一个高质量的Pareto最优解集,提出了一种基于蚁群优化和差分进化的混合多目标进化算法.在提出的算法中,一方面采纳分解机制利用蚁群优化算子实现对Pareto最优解的开发,另一方面采纳拥挤度概念利用差分进化算子实现对ParetoFront的探索.通过对一组标准测试算例的仿真实验,结果表明所提出的算法比现有的算法能够获得分布性和收敛性更优的Pareto解集.
【期刊名称】usted《沈阳师范大学学报（自然科学版）》
【年(卷),期】2017(035)004
【总页数】5页(P425-429)
【关键词】旅行商问题;进化多目标优化;蚁群优化;差分进化
【作 者】王娜;刘生;王洪峰
【作者单位】沈阳师范大学计算机与数学基础教学部,沈阳110034;东北大学信息科学与工
异鬼夜王的真实面目程学院,沈阳 110819;东北大学信息科学与工程学院,沈阳 110819;东北大学信息科学与工程学院,沈阳 110819
【正文语种】中 文
【中图分类】disappear是什么意思O229
旅行商问题是运筹学领域中一类经典的组合优化问题,很多科学和工程问题往往可以转化为这类问题进行求解。由于实际应用问题中总是需要考虑多个优化目标,使得越来越多的学者开始关注多目标旅行商问题的研究工作[1-3]。然而由于目标函数之间通常都是相互冲突的,使得这种多目标优化问题中不存在一个能够优化所有目标函数的最优解,而是存在一组多个目标函数之间平衡解,即Pareto最优解[5]。
pillbox近年来,进化算法被广泛用于求解各种多目标优化问题[5-7]。作为一种基于种群机制的元启发式方法,多目标进化算法的目标是通过一次运行就能够获得一组分布均匀的Pareto最优解。这也就意味着在整个算法迭代过程中需要考虑两种不同的搜索,一种可以认为是对更好的非支配解的开发性(exploitation)搜索,另一种可以认为是对更优分布的非支配解集的探索性(exploration)搜索。值得注意的是,这2种搜索行为在目前的文献中很少同时考虑。
june怎么读
于是,本文将2种不同的进化算法(即蚁群优化ACO[8]和差分进化DE[9])思想结合起来,充分利用蚁群优化算子在旅行商问题上的高效性和差分进化算子在保持种群多样性上的有效性,设计一种混合多目标进化算法来求解多目标旅行商问题。
在本文所提出的算法中,2种主要的策略被采用。一方面,采纳分解的机制将一个多目标优化问题构造出若干个单目标子问题,在借鉴文献[10]中算法思想的基础上,通过利用蚁群优化算子对主种群进行更新迭代,以获得所构造的这些单目标子问题的最优解,即是原来多目标问题的Pareto最优解。在算法具体实现过程中,根据一组均匀分布的权重向量(其数量是预先设定的),利用Tchebycheff函数将一个多目标TSP问题构造出一系列单目标子问题。
strider另一方面,采纳文献[11]中多目标进化算法设计思想中拥挤度的概念,通过利用差分进化算子对外部种群(即所获得的非支配解集)进行更新,以保证所获得的非支配解集具有更好的分布性。这里需要说明的是由于差分进化算子是针对实数编码个体的,这就需要将实编码个体转化为旅行商问题的解。在算法具体实现过程中,根据数值的大小,将原来的实数编码个体转换为顺序编码个体,以获得旅行商问题的一个解。
图1给出了本文所提出算法流程的伪码图。在算法初始化阶段,首先需要根据一组预先产生
的权重向量,将原有的多目标问题构造出相应数量的单目标子问题;然后根据构造的子问题初始化对应的蚂蚁个体,并利用权重向量的相似性将所有蚂蚁个体分组;最后初始化外部种群。在算法迭代过程中,首先根据每个蚂蚁对应的启发信息矩阵和每组蚂蚁共享的信息素矩阵产生新解,然后根据产生的新解更新外部种群,对外部种群执行差分进化运算,最后根据蚁群优化和差分进化算子的运行效果更新每组蚂蚁共享的信息素矩阵。
Step 1 初始化,构造一组子问题(i=1,…,N);随机产生一组蚂蚁,蚂蚁i对应子问题i,初始化每个蚂蚁对应的启发信息矩阵ηi;根据蚂蚁对应权重向量的相似性,将蚂蚁分成K组,初始化每个小组j(j=1,…,K)的信息素矩阵τj;初始化外部种群。
Step 2 构造解,对于每个蚂蚁(i=1,…,N),用概率函数(表示为xi,ηi,τj的函数)求出解yi,计算其目标函数向量。对于每个蚂蚁i,更新当前最好解xi。y是在所有邻近蚂蚁找到的解中使得g(.|λi)的值最小的解。如果y没被用于更新其他旧解,且g(y|λi)<g(xi|λi),用y替换xi。
Step 3 更新外部种群,对于每个yi,如果外部种群中没有解支配yi,把yi添加到外部种群,移除其中所有被yi所支配的解。
Step 4 差分进化运算:对外部种群进行N′次差分进化,利用每次产生新解xp更新外部种群,计算拥挤距离,拥挤距离大的被添加进外部种群,拥挤距离小的被删除,限定外部种群大小。
Step 5 更新对应小组信息素:对于每个小组j,更新信息素矩阵τj,小组j中的蚂蚁在Step 2中获得的解,且在Step 3中被添加到外部种群,则该蚂蚁的解用来更新信息素;如果产生的新解xp,对每个小组j,找出使得g(xp|λj)值最小的小组q,用xp更新小组q的信息素。
Step 6 停止准则:如果满足问题的停止准则,停止运算。
为了验证本文所提出的算法(后文称之为ACO-DE)在求解多目标旅行商问题时的性能,选择了文献中4种具有代表性的多目标进化算法作为比较算法,其中:MODE属于早期的多目标差分进化算法[12],MOSADE是一种采用自适应策略的多目标差分进化算法[13],NSGA-II[11]和MOEA/D[14]是2种最为经典的多目标进化算法,上述算法均可以被用于求解本文所研究的多目标旅行商问题。
本文实验中所采用的测试函数均是根据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系统下Eclip环境下实现,算法测试的硬件环境为3.30GHz的因特尔处理器、4GB内存的HP台式机。
为了更好的检验各种算法在多目标旅行商问题上的性能,选取文献[15]中2个常用的多目标算法性能指标作为算法对比的评价指标。
1) IGD指标(Inverted generational distance):该指标通过从真实Pareto最优解集到算法获得的非支配解集的平均距离来评估该算法的性能。假定p*是理想Pareto front上的一组均匀采样,是由算法获得的一组非支配解集,则IGD指标定义如下:
matras
日语学习入门其中:d(v,P)为v与解集P中与之距离最近点之间的Euclidean距离;|p*|为p*中Pareto最优解的个数。
toastmasters
2) Hypervolume指标:该指标利用算法获得的非支配解集中所有点与参考点在目标空间所围成的超立方体体积来评估算法的性能。若P={p1,p2,…,pN}为算法获得的一组非支配解,r为参考点,满足pir,∀i=1,2,…,N,则Hypervolume指标定义如下:
其中:N为非支配解的个数;Leb(S)为解集S的勒贝格测度;vi为第i个非支配解和参考点围成的超立方体体积。
可能英文
为了公平合理地比较本文所提出的算法与比较算法的性能,所有算法均以3 000次估值作为停止条件,每种算法分别对每一算例求解30次,取30次运行结果的平均值作为其性能指标。
表1给出了所有算法在IGD指标方面的实验结果,从中可以看出,本文所提出的ACO-DE算法的性能远远优于其他4种对比算法的性能。例如,在KroAB100算例中,ACO-DE算法的IGD性能指标的均值为4 220,远远小于其他4种对比算法的平均性能,分别为18 254、35 198、55 395和8 772。
表2给出了所有算法在Hypervolume指标方面的实验结果,从表中能够发现本文所提出的ACO-DE算法在所有算例上Hypervolume指标的均值都是1.0,这也就意味着ACO-DE算法总是能够比其他4种对比算法获得收敛性和分布性更好的非支配解集。
