[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
2024
Tomoya Iseki, Shun Ito, Kengo Katayama
Iterated Local Search Metaheuristic for the Vehicle Routing Problem with Drones Proceedings Article
In: Innovative Design and Engineering Applications of Intelligent Systems Under the Framework of Industry 4.0. ISDEA 2024. Lecture Notes in Electrical Engineering (LNEE,volume 856), pp. 89-103, Springer, 2024, ISBN: 978-981-97-9242-9.
Abstract | BibTeX | タグ: Drone, Iterated local search, Metaheuristics, Vehicle routing problem | Links:
@inproceedings{ISEKI-ISDEA-2024,
title = {Iterated Local Search Metaheuristic for the Vehicle Routing Problem with Drones},
author = {Tomoya Iseki and Shun Ito and Kengo Katayama},
url = {https://link.springer.com/chapter/10.1007/978-981-97-9243-6_8},
doi = {https://doi.org/10.1007/978-981-97-9243-6_8},
isbn = {978-981-97-9242-9},
year = {2024},
date = {2024-11-30},
urldate = {2024-11-30},
booktitle = {Innovative Design and Engineering Applications of Intelligent Systems Under the Framework of Industry 4.0. ISDEA 2024. Lecture Notes in Electrical Engineering (LNEE,volume 856)},
pages = {89-103},
publisher = {Springer},
abstract = {This paper presents an iterated local search (ILS) based metaheuristic for the Vehicle Routing Problem with Drones (VRPD) that involves unmanned aerial vehicles, also known as drones, working collaboratively with capacitated trucks in parcel delivery. Due to the limited research of local searches for the VRPD currently, we first present several neighborhood structures important for the local search design. We then extend to iterated local search algorithms combining these neighborhood searches and simple perturbation. For a new set of instances to minimize total delivery service times, we show that the best application order of the neighborhood searches in the local search process and the ILS obtains better results than the multi-start local search approach for the problem.},
keywords = {Drone, Iterated local search, Metaheuristics, Vehicle routing problem},
pubstate = {published},
tppubtype = {inproceedings}
}
This paper presents an iterated local search (ILS) based metaheuristic for the Vehicle Routing Problem with Drones (VRPD) that involves unmanned aerial vehicles, also known as drones, working collaboratively with capacitated trucks in parcel delivery. Due to the limited research of local searches for the VRPD currently, we first present several neighborhood structures important for the local search design. We then extend to iterated local search algorithms combining these neighborhood searches and simple perturbation. For a new set of instances to minimize total delivery service times, we show that the best application order of the neighborhood searches in the local search process and the ILS obtains better results than the multi-start local search approach for the problem.
2020
Kazuho Kanahara, Kengo Katayama, Nobuo Funabiki, Etsuji Tomita
The performance of a metaheuristic algorithm for finding a maximal weight clique in the fill-in-blank problem Proceedings Article
In: ICIET 2020: Proceedings of the 2020 8th International Conference on Information and Education Technology, pp. 257-261, 2020.
Abstract | BibTeX | タグ: Fill-in-blank problem, Maximal weight clique problem, Metaheuristics | Links:
@inproceedings{KANAHARA-ICIET-2020,
title = {The performance of a metaheuristic algorithm for finding a maximal weight clique in the fill-in-blank problem},
author = {Kazuho Kanahara and Kengo Katayama and Nobuo Funabiki and Etsuji Tomita},
doi = {https://doi.org/10.1145/3395245.3396407},
year = {2020},
date = {2020-05-23},
urldate = {2020-05-23},
booktitle = {ICIET 2020: Proceedings of the 2020 8th International Conference on Information and Education Technology},
pages = {257-261},
abstract = {A programming education is one of the most important fields in Information and Education Technology. Funabiki et al. have developed a Web-based Java Programming Learning Assistant System (JPLAS). JPLAS mainly provides two types of problems, namely the code writing problem and the fill-in-blank problem, to support students' self-studies at various learning levels. Particularly in the fill-in-blank problem (FIBP), the system requires an efficient algorithm to find a maximal clique of the compatibility graph in advance in order to obtain a maximal set of blank elements with unique answers. In this paper, we investigate the performance of a metaheuristic algorithm based on an iterated local search for solving the maximum weight clique problem (MWCP), which is an important generalization of the maximum clique problem, given as an extension of the compatibility graph in the FIBP. Computational results show that our metaheuristic algorithm is capable of finding satisfactory weighted cliques efficiently for well-known benchmark graphs and the performance of our algorithm is comparable to those of state-of-the-art metaheuristics for the MWCP.},
keywords = {Fill-in-blank problem, Maximal weight clique problem, Metaheuristics},
pubstate = {published},
tppubtype = {inproceedings}
}
A programming education is one of the most important fields in Information and Education Technology. Funabiki et al. have developed a Web-based Java Programming Learning Assistant System (JPLAS). JPLAS mainly provides two types of problems, namely the code writing problem and the fill-in-blank problem, to support students' self-studies at various learning levels. Particularly in the fill-in-blank problem (FIBP), the system requires an efficient algorithm to find a maximal clique of the compatibility graph in advance in order to obtain a maximal set of blank elements with unique answers. In this paper, we investigate the performance of a metaheuristic algorithm based on an iterated local search for solving the maximum weight clique problem (MWCP), which is an important generalization of the maximum clique problem, given as an extension of the compatibility graph in the FIBP. Computational results show that our metaheuristic algorithm is capable of finding satisfactory weighted cliques efficiently for well-known benchmark graphs and the performance of our algorithm is comparable to those of state-of-the-art metaheuristics for the MWCP.
2011
Kengo Katayama, Akinori Kohmura, Keiko Kohmoto, Hideo Minamihara
Memetic algorithm with strategic controller for the maximum clique problem Proceedings Article
In: SAC 2011: Proceedings of the 2011 ACM Symposium on Applied Computing, pp. 1062-1069, 2011.
Abstract | BibTeX | タグ: Maximum clique problem, Memetic algorithm, Metaheuristics | Links:
@inproceedings{KATAYAMA-SAC-2011,
title = {Memetic algorithm with strategic controller for the maximum clique problem},
author = {Kengo Katayama and Akinori Kohmura and Keiko Kohmoto and Hideo Minamihara},
doi = {https://doi.org/10.1145/1982185.1982419},
year = {2011},
date = {2011-03-21},
urldate = {2011-03-21},
booktitle = {SAC 2011: Proceedings of the 2011 ACM Symposium on Applied Computing},
pages = {1062-1069},
abstract = {Most of standard evolutionary algorithms consist of a mutation, a crossover, a selection and often a local search. Each of these operators is specifically designed for a combinatorial optimization problem. These can be considered as tools for the optimization searches, and the interplay between them in the searches is not apparently controlled in many cases.
In this paper, we present a flexible control method, called Strategic Controller (SC), for multiple mutation methods equipped in a memetic algorithm (MA) for the maximum clique problem (MCP). The SC is used to choose a suitable method from the candidate mutations. To perform an adaptive search, the SC evaluates each mutation method based on the contribution information which is served as novel "memes" for the mutations in the MA. To achieve the SC, we apply the idea of analytic hierarchy process.
Although standard MAs have a population of multiple solutions as memes usually, a single solution is used in our MA. We evaluated the performance of MA with SC (MA-SC) on DIMACS benchmark graphs of the MCP. The results showed that MA-SC is capable of finding comprehensive solutions through comparisons with MAs in which each mutation is used. Moreover, we observed that it is highly effective particularly for hardest graphs in the benchmark set in comparisons with recent metaheuristics to the MCP.},
keywords = {Maximum clique problem, Memetic algorithm, Metaheuristics},
pubstate = {published},
tppubtype = {inproceedings}
}
Most of standard evolutionary algorithms consist of a mutation, a crossover, a selection and often a local search. Each of these operators is specifically designed for a combinatorial optimization problem. These can be considered as tools for the optimization searches, and the interplay between them in the searches is not apparently controlled in many cases.
In this paper, we present a flexible control method, called Strategic Controller (SC), for multiple mutation methods equipped in a memetic algorithm (MA) for the maximum clique problem (MCP). The SC is used to choose a suitable method from the candidate mutations. To perform an adaptive search, the SC evaluates each mutation method based on the contribution information which is served as novel "memes" for the mutations in the MA. To achieve the SC, we apply the idea of analytic hierarchy process.
Although standard MAs have a population of multiple solutions as memes usually, a single solution is used in our MA. We evaluated the performance of MA with SC (MA-SC) on DIMACS benchmark graphs of the MCP. The results showed that MA-SC is capable of finding comprehensive solutions through comparisons with MAs in which each mutation is used. Moreover, we observed that it is highly effective particularly for hardest graphs in the benchmark set in comparisons with recent metaheuristics to the MCP.
In this paper, we present a flexible control method, called Strategic Controller (SC), for multiple mutation methods equipped in a memetic algorithm (MA) for the maximum clique problem (MCP). The SC is used to choose a suitable method from the candidate mutations. To perform an adaptive search, the SC evaluates each mutation method based on the contribution information which is served as novel "memes" for the mutations in the MA. To achieve the SC, we apply the idea of analytic hierarchy process.
Although standard MAs have a population of multiple solutions as memes usually, a single solution is used in our MA. We evaluated the performance of MA with SC (MA-SC) on DIMACS benchmark graphs of the MCP. The results showed that MA-SC is capable of finding comprehensive solutions through comparisons with MAs in which each mutation is used. Moreover, we observed that it is highly effective particularly for hardest graphs in the benchmark set in comparisons with recent metaheuristics to the MCP.
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.
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.
2000
Kengo Katayama, Masafumi Tani, Hiroyuki Narihisa
Solving large binary quadratic programming problems by effective genetic local search algorithm Proceedings Article
In: GECCO 2000: Proceedings of the 2nd Annual Conference on Genetic and Evolutionary Computation, pp. 643-650, 2000.
Abstract | BibTeX | タグ: Genetic local search, Metaheuristics, Unconstrained binary quadratic programming problem | Links:
@inproceedings{KATAYAMA-GECCO-2000,
title = {Solving large binary quadratic programming problems by effective genetic local search algorithm},
author = {Kengo Katayama and Masafumi Tani and Hiroyuki Narihisa},
url = {https://dl.acm.org/doi/abs/10.5555/2933718.2933833},
year = {2000},
date = {2000-07-10},
urldate = {2000-07-10},
booktitle = {GECCO 2000: Proceedings of the 2nd Annual Conference on Genetic and Evolutionary Computation},
pages = {643-650},
abstract = {A genetic local search (GLS) algorithm, which is a combination technique of genetic algorithm and local search, for the unconstrained binary quadratic programming problem (BQP) is presented. An effective local search algorithm, which is a variant of the k-opt local search for the BQP by Merz et al., is described, and the performance of the GLS with the variant local search heuristic is demonstrated on several large-scale problem instances. Our computational results indicate that the GLS is able to frequently find the best-known solution with a relatively short running time and obviously our average solution values obtained are better than previous powerful heuristic approaches especially for the large problem instances of 2,500 variables.},
keywords = {Genetic local search, Metaheuristics, Unconstrained binary quadratic programming problem},
pubstate = {published},
tppubtype = {inproceedings}
}
A genetic local search (GLS) algorithm, which is a combination technique of genetic algorithm and local search, for the unconstrained binary quadratic programming problem (BQP) is presented. An effective local search algorithm, which is a variant of the k-opt local search for the BQP by Merz et al., is described, and the performance of the GLS with the variant local search heuristic is demonstrated on several large-scale problem instances. Our computational results indicate that the GLS is able to frequently find the best-known solution with a relatively short running time and obviously our average solution values obtained are better than previous powerful heuristic approaches especially for the large problem instances of 2,500 variables.