Since its inception in 2013, the Travelling Thief Problem (TTP) has been
widely studied as an example of problems with multiple interconnected
sub-problems. The dependency in this model arises when tying the travelling
time of the "thief" to the weight of the knapsack. However, other forms of
dependency as well as combinations of dependencies should be considered for
investigation, as they are often found in complex real-world problems. Our goal
is to study the impact of different forms of dependency in the TTP using a
simple local search algorithm. To achieve this, we use Local Optima Networks, a
technique for analysing the fitness landscape.

本文主要研究尝试不同形式的 TTP（Travelling Thief Problem）依赖性对于简单局部搜索算法的影响，使用适应性景观分析技术进行分析，旨在探讨复杂实际问题的多个相互关联子问题的依赖性。

关于旅行窃贼问题中相互依赖模型的适应性景观

On the Fitness Landscapes of Interdependency Models in the Travelling Thief Problem

This paper presents a framework to tackle combinatorial optimization problems
using neural networks and reinforcement learning. We focus on the traveling
salesman problem (TSP) and train a recurrent network that, given a set of city
coordinates, predicts a distribution over different city permutations. Using
negative tour length as the reward signal, we optimize the parameters of the
recurrent network using a policy gradient method. We compare learning the
network parameters on a set of training graphs against learning them on
individual test graphs. Despite the computational expense, without much
engineering and heuristic designing, Neural Combinatorial Optimization achieves
close to optimal results on 2D Euclidean graphs with up to 100 nodes. Applied
to the KnapSack, another NP-hard problem, the same method obtains optimal
solutions for instances with up to 200 items.

本文提出了一种利用神经网络和强化学习解决组合优化问题的框架，特别关注旅行推销员问题和背包问题，证明了该方法在不需要太多工程和启发式设计的情况下在二维欧几里得图上取得接近最优结果，并且可以得到具有多达 200 个项目实例的最优解。

强化学习的神经组合优化

Neural Combinatorial Optimization with Reinforcement Learning

We study the problem of predicting a set or list of options under knapsack
constraint. The quality of such lists are evaluated by a submodular reward
function that measures both quality and diversity. Similar to DAgger (Ross et
al., 2010), by a reduction to online learning, we show how to adapt two
sequence prediction models to imitate greedy maximization under knapsack
constraint problems: CONSEQOPT (Dey et al., 2012) and SCP (Ross et al., 2013).
Experiments on extractive multi-document summarization show that our approach
outperforms existing state-of-the-art methods.

本文研究了在背包约束下预测选项集或列表的问题，并通过在线学习的降级模型，证明了如何使两个序列预测模型适应贪心的最大化背包约束问题，实验结果表明，我们的方法优于现有的最先进方法。