首页> 外文期刊>Computers & mathematics with applications >A decomposition based estimation of distribution algorithm for multiobjective traveling salesman problems
【24h】

A decomposition based estimation of distribution algorithm for multiobjective traveling salesman problems

机译:基于分解的多目标旅行商问题的分布估计

获取原文
获取原文并翻译 | 示例

摘要

The traveling salesman problem (TSP) is a well known NP-hard benchmark problem for discrete optimization. However, there is a lack of TSP test instances for multiobjective optimization and some current TSP instances are combined to form a multiobjective TSP (MOTSP). In this paper, we present a way to systematically design MOTSP instances based on current TSP test instances, of which the degree of conflict between the objectives is measurable. Furthermore, we propose an approach, named multiobjective estimation of distribution algorithm based on decomposition (MEDA/D), which utilizes decomposition based techniques and probabilistic model based methods, to tackle the newly designed MOTSP test suite. In MEDA/D, an MOTSP is decomposed into a set of scalar objective sub-problems and a probabilistic model, using both priori and learned information, is built to guide the search for each sub-problem. By the cooperation of neighbor sub-problems, MEDA/D could optimize all the sub-problems simultaneously and thus find an approximation to the original MOTSP in a single run. The experimental results show that MEDA/D outperforms MOACO and MOEA/D-ACO, two ant colony based methods, on most of the given test instances and MEDA/D is insensible to its control parameters.
机译:旅行商问题(TSP)是用于离散优化的众所周知的NP硬基准问题。但是,缺少用于多目标优化的TSP测试实例,并且将一些当前的TSP实例组合在一起以形成多目标TSP(MOTSP)。在本文中,我们提出了一种基于当前TSP测试实例系统设计MOTSP实例的方法,其中目标之间的冲突程度是可测量的。此外,我们提出了一种基于分解的分布算法(MEDA / D)多目标估计方法,该方法利用了基于分解的技术和基于概率模型的方法来解决新设计的MOTSP测试套件。在MEDA / D中,将MOTSP分解为一组标量目标子问题,并使用先验信息和学习信息来构建概率模型,以指导每个子问题的搜索。通过相邻子问题的协作,MEDA / D可以同时优化所有子问题,从而在一次运行中找到与原始MOTSP的近似值。实验结果表明,在大多数给定的测试实例上,MEDA / D优于基于两种蚁群方法的MOACO和MOEA / D-ACO,而MEDA / D对其控制参数不敏感。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号