论文标题
深度学习是针对旅行销售人员问题选择自动化算法的无竞争功能方法
Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection on the Traveling Salesperson Problem
论文作者
论文摘要
在这项工作中，我们关注众所周知的欧几里得旅行销售人员问题（TSP）和两个高度竞争性不精确的启发式TSP求解器EAX和LKH，在每种定义算法选择的背景下（AS）。我们通过1,000个节点进化了实例，在该节点中，求解器显示出强烈不同的性能曲线。这些实例是探索性研究的基础，以识别弥歧视的问题特征（特征）。简而言之：我们表明，即使存在（1）有希望的功能，（2）这些功能与文献的先前结果一致，并且（3）接受这些功能训练的模型比采用复杂的特征选择方法的模型更准确，但是在惩罚性的平均运行时，该优势与单个最佳求解者相比，该优势与虚拟的最佳求解器相近，因此比单个Best best best Best Best Best Best Bests beast temver相比。但是，我们表明，基于无特征的深神网络方法仅基于已经与经典作为模型结果相匹配的实例的视觉表示，因此显示了未来研究的巨大潜力。
In this work we focus on the well-known Euclidean Traveling Salesperson Problem (TSP) and two highly competitive inexact heuristic TSP solvers, EAX and LKH, in the context of per-instance algorithm selection (AS). We evolve instances with 1,000 nodes where the solvers show strongly different performance profiles. These instances serve as a basis for an exploratory study on the identification of well-discriminating problem characteristics (features). Our results in a nutshell: we show that even though (1) promising features exist, (2) these are in line with previous results from the literature, and (3) models trained with these features are more accurate than models adopting sophisticated feature selection methods, the advantage is not close to the virtual best solver in terms of penalized average runtime and so is the performance gain over the single best solver. However, we show that a feature-free deep neural network based approach solely based on visual representation of the instances already matches classical AS model results and thus shows huge potential for future studies.
