[Contents]
Toggle当研究室で取り組んでいる研究に関する論文・講演などの情報（一部抜粋）です。
Here is a selection of our published papers on the research we’ve been working on in our laboratory.
Our Selected Papers and Keywords
2018
Kazuho Kanahara, Kengo Katayama, Takeshi Okano, Elis Kulla, Tetsuya Oda, Noritaka Nishihara
A restart diversification strategy for iterated local search to maximum clique problem Proceedings Article
In: CISIS 2018: Complex, Intelligent, and Software Intensive Systems, Proceedings of the 12th International Conference on Complex, Intelligent, and Software Intensive Systems, Advances in Intelligent Systems and Computing (AISC, volume 772), pp. 670–680, 2018.
Abstract | BibTeX | タグ: Diversification, Iterated local search, Maximum clique problem | Links:
@inproceedings{KANAHARA-CISIS-2018,
title = {A restart diversification strategy for iterated local search to maximum clique problem},
author = {Kazuho Kanahara and Kengo Katayama and Takeshi Okano and Elis Kulla and Tetsuya Oda and Noritaka Nishihara},
doi = {https://doi.org/10.1007/978-3-319-93659-8_61},
year = {2018},
date = {2018-06-19},
booktitle = {CISIS 2018: Complex, Intelligent, and Software Intensive Systems, Proceedings of the 12th International Conference on Complex, Intelligent, and Software Intensive Systems, Advances in Intelligent Systems and Computing (AISC, volume 772)},
pages = {670–680},
abstract = {Iterated local search metaheuristic provides high quality solutions, in spite of a simple framework, for a large number of combinatorial optimization problems. However the search stagnation sometimes occur before finding a high quality solution for difficult problem instances particularly. One simple way to overcome such stagnation is to introduce a restart strategy into the framework that forcibly changes its search point. In this paper, we present a restart diversification strategy (RDS) for an iterated local search incorporating k-opt local search (KLS), called Iterated KLS (IKLS), for the maximum clique problem. For the RDS, we accumulate the information of solutions by KLS and it occasionally diversifies the main search of IKLS by moving to unexplored points based on the information. IKLS with the RDS is evaluated on DIMACS graphs. The experimental results showed that the RDS contributes to the improvement of the main search of IKLS for several difficult graphs.},
keywords = {Diversification, Iterated local search, Maximum clique problem},
pubstate = {published},
tppubtype = {inproceedings}
}
Iterated local search metaheuristic provides high quality solutions, in spite of a simple framework, for a large number of combinatorial optimization problems. However the search stagnation sometimes occur before finding a high quality solution for difficult problem instances particularly. One simple way to overcome such stagnation is to introduce a restart strategy into the framework that forcibly changes its search point. In this paper, we present a restart diversification strategy (RDS) for an iterated local search incorporating k-opt local search (KLS), called Iterated KLS (IKLS), for the maximum clique problem. For the RDS, we accumulate the information of solutions by KLS and it occasionally diversifies the main search of IKLS by moving to unexplored points based on the information. IKLS with the RDS is evaluated on DIMACS graphs. The experimental results showed that the RDS contributes to the improvement of the main search of IKLS for several difficult graphs.
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, Hiroshi Yamashita, Hiroyuki Narihisa
Variable depth search and iterated local search for the node placement problem in multihop WDM lightwave networks Proceedings Article
In: CEC 2007: Proceedings of 2007 IEEE Congress on Evolutionary Computation, pp. 3508-3515, 2007.
Abstract | BibTeX | タグ: Iterated local search, Multihop networks, Node placement problem, Variable depth search | Links:
@inproceedings{KATAYAMA-CEC-2007,
title = {Variable depth search and iterated local search for the node placement problem in multihop WDM lightwave networks},
author = {Kengo Katayama and Hiroshi Yamashita and Hiroyuki Narihisa},
doi = {10.1109/CEC.2007.4424927},
year = {2007},
date = {2007-09-25},
urldate = {2007-09-25},
booktitle = {CEC 2007: Proceedings of 2007 IEEE Congress on Evolutionary Computation},
pages = {3508-3515},
abstract = {We address a problem of finding an optimal node placement that minimizes the amount of traffics by reducing the weighted hop distances in multihop lightwave networks. The problem is called Node Placement Problem (NPP). NPP is known to be NP-hard and one of the most important problems in wavelength division multiplexing (WDM) based networks. In this paper we propose a new local search algorithm for the NPP based on variable depth search, and show its extension to an iterated local search algorithm. To evaluate the performance of the proposed methods, we provided the benchmark instances with known optimal solutions, and performed extensive experiments on the instances. The computational results showed that our iterated local search outperformed multistart local search methods and the best available metaheuristic for the problem.},
keywords = {Iterated local search, Multihop networks, Node placement problem, Variable depth search},
pubstate = {published},
tppubtype = {inproceedings}
}
We address a problem of finding an optimal node placement that minimizes the amount of traffics by reducing the weighted hop distances in multihop lightwave networks. The problem is called Node Placement Problem (NPP). NPP is known to be NP-hard and one of the most important problems in wavelength division multiplexing (WDM) based networks. In this paper we propose a new local search algorithm for the NPP based on variable depth search, and show its extension to an iterated local search algorithm. To evaluate the performance of the proposed methods, we provided the benchmark instances with known optimal solutions, and performed extensive experiments on the instances. The computational results showed that our iterated local search outperformed multistart local search methods and the best available metaheuristic for the problem.
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.
2001
Kengo Katayama, Hiroyuki Narihisa
On fundamental design of parthenogenetic algorithm for the binary quadratic programming problem Proceedings Article
In: CEC 2001: Proceedings of the 2001 Congress on Evolutionary Computation, pp. 356-363, 2001.
Abstract | BibTeX | タグ: Iterated local search, Metaheuristics, Unconstrained binary quadratic programming problem | Links:
@inproceedings{KATAYAMA-CEC-2001,
title = {On fundamental design of parthenogenetic algorithm for the binary quadratic programming problem},
author = {Kengo Katayama and Hiroyuki Narihisa},
doi = {10.1109/CEC.2001.934412},
year = {2001},
date = {2001-05-27},
urldate = {2001-05-27},
booktitle = {CEC 2001: Proceedings of the 2001 Congress on Evolutionary Computation},
volume = {1},
pages = {356-363},
abstract = {The aims of this paper are to develop a heuristic called Parthenogenetic Algorithm (PA) for the binary quadratic programming problem (BQP) and to show empirical performance of PA on large test instances of the BQP. The PA may be interpreted as iterated local search where a population consists of a single individual and a mutation operator rather than a crossover is fully used to generate new offspring, which is used as a starting solution for a local search process in each iteration. Due to the first attempt of PA approach to the BQP, we investigate several PA implementations to choose the best PA. Each of them incorporates each of four local search heuristics (deterministic 1-opt, randomized 1-opt, deterministic k-opt, and randomized k-opt) known for the BQP so far and has a random mutation controlled by a probability parameter. Computational results after extensive experiments show that search abilities of PAs with k-opt are not as sensitive in the parameter values as PAs with 1-opt. Moreover, it turns out that the PA incorporating the randomized k-opt local search and with the near-optimal parameter value of the mutation is superior or at least competitive to the other existing powerful heuristics.},
keywords = {Iterated local search, Metaheuristics, Unconstrained binary quadratic programming problem},
pubstate = {published},
tppubtype = {inproceedings}
}
The aims of this paper are to develop a heuristic called Parthenogenetic Algorithm (PA) for the binary quadratic programming problem (BQP) and to show empirical performance of PA on large test instances of the BQP. The PA may be interpreted as iterated local search where a population consists of a single individual and a mutation operator rather than a crossover is fully used to generate new offspring, which is used as a starting solution for a local search process in each iteration. Due to the first attempt of PA approach to the BQP, we investigate several PA implementations to choose the best PA. Each of them incorporates each of four local search heuristics (deterministic 1-opt, randomized 1-opt, deterministic k-opt, and randomized k-opt) known for the BQP so far and has a random mutation controlled by a probability parameter. Computational results after extensive experiments show that search abilities of PAs with k-opt are not as sensitive in the parameter values as PAs with 1-opt. Moreover, it turns out that the PA incorporating the randomized k-opt local search and with the near-optimal parameter value of the mutation is superior or at least competitive to the other existing powerful heuristics.