期刊
2018 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC)
卷 -, 期 -, 页码 1176-1183出版社
IEEE
DOI: 10.1109/CEC.2018.8477821
关键词
-
类别
资金
- CONACyT through the Ciencia Basica project [285599]
Real-world problems complexity is often a consequence of the interdependence of the sub-problems that compose them. The Travelling Thief Problem (TTP) is a novel benchmark problem that aims to be a good model of this interdependence. It combines two classical well known problems: The Travelling Salesman Problem (TSP) and the Knapsack Problem (KP). Some state-of-the-art techniques, after a complex initialization, alternate between two different optimization stages, one focused on the tour and the other one on the selection of items. The optimization of the tour usually involves a simple trajectory-based search, meaning that important drawbacks might appear when the initial optimized TSP tours are not suitable for the TTP problem. In this paper a Guided Local Search (GLS) approach is proposed to improve further the tour optimization and compared against state-of-the-art techniques. Experimental validation shows the important benefits provided by our proposal, meaning that in fact many state-of-the-art techniques are too focused in a subset of the search space. Although at the moment the computational cost of our method is large, meaning that this approach does not scale well, new best-known solutions were generated in three well-known TTP instances. The main benefits were obtained in small and medium-sized instances.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据