In real-world optimisation, it is common to face several sub-problems interacting and forming the main problem. There is an inter-dependency between the sub-problems, making it impossible to solve such a problem by focusing on only one component. The traveling thief problem~(TTP) belongs to this category and is formed by the integration of the traveling salesperson problem~(TSP) and the knapsack problem~(KP). In this paper, we investigate the inter-dependency of the TSP and the KP by means of quality diversity~(QD) approaches. QD algorithms provide a powerful tool not only to obtain high-quality solutions but also to illustrate the distribution of high-performing solutions in the behavioural space. We introduce a MAP-Elite based evolutionary algorithm using well-known TSP and KP search operators, taking the TSP and KP score as behavioural descriptor. Afterwards, we conduct comprehensive experimental studies that show the usefulness of using the QD approach applied to the TTP. First, we provide insights regarding high-quality TTP solutions in the TSP/KP behavioural space. Afterwards, we show that better solutions for the TTP can be obtained by using our QD approach and show that it can improve the best-known solution for a wide range of TTP instances used for benchmarking in the literature.


翻译:在现实世界的优化中,常见的情况是面对几个小问题相互作用和形成主要问题。子问题之间存在相互依存关系,因此不可能通过只注重一个组成部分来解决该问题。旅行小偷问题~(TTP)属于这一类别,由旅行推销员问题~(TSP)和 knapsack问题~(KP)的整合构成。在本文件中,我们通过高质量的多样性~(QD) 方法调查TSP和KP的相互依存性。QD算法不仅提供了获得高质量解决方案的有力工具,而且还展示了行为空间中高性能解决方案的分布情况。我们采用了基于MAP-Elite的演化算法,使用众所周知的TSP和KP搜索操作员,将TSP和KP的评分作为行为描述符。随后,我们进行了全面的实验研究,表明采用适用于TTP的QD方法是否有用。首先,我们为TSP/KP的高质量TTP的解决方案提供了深刻的洞察理解,然后用广度空间展示了我们所了解的TTP的高质量TTP文献解决方案。我们随后可以展示了一种更好的解决办法。

0
下载
关闭预览

相关内容

IFIP TC13 Conference on Human-Computer Interaction是人机交互领域的研究者和实践者展示其工作的重要平台。多年来,这些会议吸引了来自几个国家和文化的研究人员。官网链接:http://interact2019.org/
【硬核书】矩阵代数基础,248页pdf
专知会员服务
84+阅读 · 2021年12月9日
专知会员服务
88+阅读 · 2021年6月29日
专知会员服务
61+阅读 · 2020年3月4日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
CCF推荐 | 国际会议信息6条
Call4Papers
9+阅读 · 2019年8月13日
灾难性遗忘问题新视角:迁移-干扰平衡
CreateAMind
17+阅读 · 2019年7月6日
计算机 | 国际会议信息5条
Call4Papers
3+阅读 · 2019年7月3日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
计算机 | CCF推荐期刊专刊信息5条
Call4Papers
3+阅读 · 2019年4月10日
已删除
将门创投
3+阅读 · 2018年6月20日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
A General and Adaptive Robust Loss Function
Arxiv
8+阅读 · 2018年11月5日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关VIP内容
【硬核书】矩阵代数基础,248页pdf
专知会员服务
84+阅读 · 2021年12月9日
专知会员服务
88+阅读 · 2021年6月29日
专知会员服务
61+阅读 · 2020年3月4日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
CCF推荐 | 国际会议信息6条
Call4Papers
9+阅读 · 2019年8月13日
灾难性遗忘问题新视角:迁移-干扰平衡
CreateAMind
17+阅读 · 2019年7月6日
计算机 | 国际会议信息5条
Call4Papers
3+阅读 · 2019年7月3日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
计算机 | CCF推荐期刊专刊信息5条
Call4Papers
3+阅读 · 2019年4月10日
已删除
将门创投
3+阅读 · 2018年6月20日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员