Knowledge Acquisition issues for intelligent route optimization by evolutionary computation
Knowledge Acquisition issues for intelligent route optimization by evolutionary computation
复制标题
进化计算智能路径优化的知识获取问题
DOI：
10.1109/cec.2014.6900415
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Yoshitaka Sakurai
中科院分区：
文献类型：
--
作者：
Masaki Suzuki;Setsuo Tsuruta;Rainer Knauf;Yoshitaka Sakurai
本文介绍了知识获取和维护的概念，基于案例的近似方法，以解决大规模的旅行商问题在很短的时间内（约3秒），错误率低于3%。这种方法是基于这样一种认识，即大多数解决方案与以前创建的解决方案非常相似。因此，在许多情况下，可以通过（1）从先前TSP解的库中选择最相似的TSP，（2）去除不是当前TSP的一部分的位置，以及（3）通过突变（即最近插入（NI））添加当前TSP的缺失位置，来从先前解导出解。这种通过基于案例的推理（CBR）创建解决方案的方式避免了从头开始创建新解决方案的计算成本。
The paper introduces a Knowledge Acquisition and Maintenance concept for a Case Based Approximation method to solve large scale Traveling Salesman Problems in a short time (around 3 seconds) with an error rate below 3 %. This method is based on the insight, that most solutions are very similar to solutions that have been created before. Thus, in many cases a solution can be derived from former solutions by (1) selecting a most similar TSP from a library of former TSP solutions, (2) removing the locations that are not part of the current TSP and (3) adding the missing locations of the current TSP by mutation, namely Nearest Insertion (NI). This way of creating solutions by Case Based Reasoning (CBR) avoids the computational costs to create new solutions from scratch.