当研究室で取り組んでいる研究に関する論文・講演などの情報（一部抜粋）です。
Here is a selection of our published papers on the research we’ve been working on in our laboratory.
Our Selected Papers and Keywords
2014
Kengo Katayama, Yuto Akagi, Elis Kulla, Hideo Minamihara, Noritaka Nishihara
New Kick Operators in Iterated Local Search Based Metaheuristic for Solving the Node Placement Problem in Multihop Networks Proceedings Article
In: NBiS 2014: Proceedings of 2014 17th International Conference on Network-Based Information Systems, pp. 141-148, 2014.
Abstract | BibTeX | タグ: Iterated local search, Kick, Multihop networks, Node placement problem | Links:
@inproceedings{KATAYAMA-NBiS-2014,
title = {New Kick Operators in Iterated Local Search Based Metaheuristic for Solving the Node Placement Problem in Multihop Networks},
author = {Kengo Katayama and Yuto Akagi and Elis Kulla and Hideo Minamihara and Noritaka Nishihara},
doi = {10.1109/NBiS.2014.35},
year = {2014},
date = {2014-09-10},
booktitle = {NBiS 2014: Proceedings of 2014 17th International Conference on Network-Based Information Systems},
pages = {141-148},
abstract = {We consider a problem of finding an optimal node placement that minimizes the amount of traffic by reducing the weighted hop distances in multihop networks. The problem is called Node Placement Problem (NPP) and is one of the most important issues in multihop networks. NPP is known to be NP-hard. Therefore, several heuristic and metaheuristic algorithms have been proposed for optimizing NPP. Recently we proposed Iterated k-swap Local Search (IKLS) algorithm, which showed better performance than previous metaheuristic algorithms proposed by other researchers. IKLS simply consists of k-swap local search and a kick (mutation or perturbation) operator called Cross-Kick, a method that aims to escape from local optima. In this paper we focus on the kick operators in order to improve the performance of IKLS for NPP. New kick operators are presented and their effectivities are shown through computational experiments on the benchmark instances of NPP. The results show that IV-Kick with Rhombus is more effective than Cross-Kick and other kick operators, particularly for large-scaled instances.},
keywords = {Iterated local search, Kick, Multihop networks, Node placement problem},
pubstate = {published},
tppubtype = {inproceedings}
}
We consider a problem of finding an optimal node placement that minimizes the amount of traffic by reducing the weighted hop distances in multihop networks. The problem is called Node Placement Problem (NPP) and is one of the most important issues in multihop networks. NPP is known to be NP-hard. Therefore, several heuristic and metaheuristic algorithms have been proposed for optimizing NPP. Recently we proposed Iterated k-swap Local Search (IKLS) algorithm, which showed better performance than previous metaheuristic algorithms proposed by other researchers. IKLS simply consists of k-swap local search and a kick (mutation or perturbation) operator called Cross-Kick, a method that aims to escape from local optima. In this paper we focus on the kick operators in order to improve the performance of IKLS for NPP. New kick operators are presented and their effectivities are shown through computational experiments on the benchmark instances of NPP. The results show that IV-Kick with Rhombus is more effective than Cross-Kick and other kick operators, particularly for large-scaled instances.
2007
Kengo Katayama, Masashi Sadamatsu, Hiroyuki Narihisa
Iterated k-opt local search for the maximum clique problem Proceedings Article
In: EvoCOP 2007: Proceedings of 7th European Conference on Evolutionary Computation in Combinatorial Optimization, Lecture Notes in Computer Science (LNCS, volume 4446), pp. 84-95, 2007, ISBN: 978-3-540-71615-0.
Abstract | BibTeX | タグ: Iterated local search, Kick, Maximum clique problem, Metaheuristics | Links:
@inproceedings{KATAYAMA-EvoCOP-2007,
title = {Iterated k-opt local search for the maximum clique problem},
author = {Kengo Katayama and Masashi Sadamatsu and Hiroyuki Narihisa},
doi = {https://doi.org/10.1007/978-3-540-71615-0_8},
isbn = {978-3-540-71615-0},
year = {2007},
date = {2007-03-30},
urldate = {2007-03-30},
booktitle = {EvoCOP 2007: Proceedings of 7th European Conference on Evolutionary Computation in Combinatorial Optimization, Lecture Notes in Computer Science (LNCS, volume 4446)},
issuetitle = {7th European Conference, EvoCOP 2007, Valencia, Spain, April 11-13, 2007, Proceedings},
pages = {84-95},
abstract = {This paper presents a simple iterated local search metaheuristic incorporating a k-opt local search (KLS), called Iterated KLS (IKLS for short), for solving the maximum clique problem (MCP). IKLS consists of three components: LocalSearch at which KLS is used, a Kick called LEC-Kick that escapes from local optima, and Restart that occasionally diversifies the search by moving to other points in the search space. IKLS is evaluated on DIMACS benchmark graphs. The results showed that IKLS is an effective algorithm for the MCP through comparisons with multi-start KLS and state-of-the-art metaheuristics.},
keywords = {Iterated local search, Kick, Maximum clique problem, Metaheuristics},
pubstate = {published},
tppubtype = {inproceedings}
}
This paper presents a simple iterated local search metaheuristic incorporating a k-opt local search (KLS), called Iterated KLS (IKLS for short), for solving the maximum clique problem (MCP). IKLS consists of three components: LocalSearch at which KLS is used, a Kick called LEC-Kick that escapes from local optima, and Restart that occasionally diversifies the search by moving to other points in the search space. IKLS is evaluated on DIMACS benchmark graphs. The results showed that IKLS is an effective algorithm for the MCP through comparisons with multi-start KLS and state-of-the-art metaheuristics.