当研究室で取り組んでいる研究に関する論文・講演などの情報（一部抜粋）です。
Here is a selection of our published papers on the research we’ve been working on in our laboratory.
Our Selected Papers and Keywords
2016
Kengo Katayama, Yusuke Okamoto, Elis Kulla, Noritaka Nishihara
Variable neighborhood search Algorithms for the node placement problem in multihop networks Proceedings Article
In: BWCCA 2016: Advances on Broad-Band Wireless Computing, Communication and Applications, Proceedings of the 11th International Conference On Broad-Band Wireless Computing, Communication and Applications, Lecture Notes on Data Engineering and Communications Technologies (LNDECT, volume 2), pp. 631–638, 2016.
Abstract | BibTeX | タグ: Multihop networks, Node placement problem, Perturbation, Variable neighborhood search | Links:
@inproceedings{KATAYAMA-BWCCA-2016,
title = {Variable neighborhood search Algorithms for the node placement problem in multihop networks},
author = {Kengo Katayama and Yusuke Okamoto and Elis Kulla and Noritaka Nishihara},
doi = {https://doi.org/10.1007/978-3-319-49106-6_62},
year = {2016},
date = {2016-10-22},
booktitle = {BWCCA 2016: Advances on Broad-Band Wireless Computing, Communication and Applications,
Proceedings of the 11th International Conference On Broad-Band Wireless Computing, Communication and Applications, Lecture Notes on Data Engineering and Communications Technologies (LNDECT, volume 2)},
pages = {631–638},
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 known to be NP-hard. Therefore, several heuristic and metaheuristic algorithms have been proposed for solving NPP, such as local search, genetic algorithm, simulated annealing, tabu search, iterated local search, ant colony optimization, etc. Although Variable Neighborhood Search (VNS) is known to be one of the most promising and efficient metaheuristic algorithms for optimization problems, VNS has not been shown for NPP yet. In this paper we propose VNS algorithms for NPP. The proposed VNSs consist of two phases: local search phase to obtain a local optimum and perturbation phase to get out of the corresponding valley in the search space. We show six types of neighborhood change schemes for the perturbation phase of VNS, and through computational experiments, we compare each performance of six VNSs incorporating k-swap local search, called VNS1, VNS2,…, VNS6. The experimental results indicate that VNS4 outperformed the others for large problem instances particularly, which adopts a suitable perturbation size selected by exploring from the upper bound that is adaptively lower in the search.},
keywords = {Multihop networks, Node placement problem, Perturbation, Variable neighborhood search},
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 known to be NP-hard. Therefore, several heuristic and metaheuristic algorithms have been proposed for solving NPP, such as local search, genetic algorithm, simulated annealing, tabu search, iterated local search, ant colony optimization, etc. Although Variable Neighborhood Search (VNS) is known to be one of the most promising and efficient metaheuristic algorithms for optimization problems, VNS has not been shown for NPP yet. In this paper we propose VNS algorithms for NPP. The proposed VNSs consist of two phases: local search phase to obtain a local optimum and perturbation phase to get out of the corresponding valley in the search space. We show six types of neighborhood change schemes for the perturbation phase of VNS, and through computational experiments, we compare each performance of six VNSs incorporating k-swap local search, called VNS1, VNS2,…, VNS6. The experimental results indicate that VNS4 outperformed the others for large problem instances particularly, which adopts a suitable perturbation size selected by exploring from the upper bound that is adaptively lower in the search.
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.