当研究室で取り組んでいる研究に関する論文・講演などの情報（一部抜粋）です。
Here is a selection of our published papers on the research we’ve been working on in our laboratory.
Our Selected Papers and Keywords
1999
Kengo Katayama, Hiroyuki Narihisa
Iterated local search approach using genetic transformation to the traveling salesman problem Proceedings Article
In: GECCO 1999: Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation, pp. 321-328, 1999.
Abstract | BibTeX | タグ: Double-bridge, Genetic iterated local search, Genetic transformation, Lin-Kernighan heuristic, Traveling salesman problem | Links:
@inproceedings{KATAYAMA-GECCO-1999,
title = {Iterated local search approach using genetic transformation to the traveling salesman problem},
author = {Kengo Katayama and Hiroyuki Narihisa},
url = {https://dl.acm.org/doi/10.5555/2933923.2933956},
year = {1999},
date = {1999-07-13},
urldate = {1999-07-13},
booktitle = {GECCO 1999: Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation},
volume = {1},
pages = {321-328},
abstract = {When giving different approximate solutions that are near the optimal solution for a combinatorial optimization problem, these solutions may share several important or common parts. This empirical conjecture is often employed in developing good algorithms for solving combinatorial optimization problems. In this paper, we propose a new iterated local search (ILS) approach incorporating this conjecture for the symmetric traveling salesman problem. To escape from local optimum found by a local search procedure to another, standard ILS algorithms generally have an useful technique called the double-bridge move. However, in our approach we deal with two approximate solutions, which contain many edges which are not shared parts of these solutions. These edges are cleverly reconnected to create a newly escaped solution. From our experimental results, it was observed that our ILS algorithms could find better solution qualities with fewer iterations than standard ILS algorithms for well-known benchmarks of the TSPLIB. In particular, we showed that one algorithm combined with the Lin-Kernighan heuristic was a very high-performance approach.},
keywords = {Double-bridge, Genetic iterated local search, Genetic transformation, Lin-Kernighan heuristic, Traveling salesman problem},
pubstate = {published},
tppubtype = {inproceedings}
}
When giving different approximate solutions that are near the optimal solution for a combinatorial optimization problem, these solutions may share several important or common parts. This empirical conjecture is often employed in developing good algorithms for solving combinatorial optimization problems. In this paper, we propose a new iterated local search (ILS) approach incorporating this conjecture for the symmetric traveling salesman problem. To escape from local optimum found by a local search procedure to another, standard ILS algorithms generally have an useful technique called the double-bridge move. However, in our approach we deal with two approximate solutions, which contain many edges which are not shared parts of these solutions. These edges are cleverly reconnected to create a newly escaped solution. From our experimental results, it was observed that our ILS algorithms could find better solution qualities with fewer iterations than standard ILS algorithms for well-known benchmarks of the TSPLIB. In particular, we showed that one algorithm combined with the Lin-Kernighan heuristic was a very high-performance approach.