[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
2022
Kazuho Kanahara, Shun Ito, Kengo Katayama
The performance of a local search based on vertex coloring for the maximum clique problem Proceedings Article
In: ICCCM 2022: Proceedings of the 10th International Conference on Computer and Communications Management, pp. 79-83, 2022.
Abstract | BibTeX | タグ: Local search, Maximum clique problem, Vertex coloring | Links:
@inproceedings{KANAHARA-ICCCM-2022,
title = {The performance of a local search based on vertex coloring for the maximum clique problem},
author = {Kazuho Kanahara and Shun Ito and Kengo Katayama},
doi = {https://doi.org/10.1145/3556223.3556235},
year = {2022},
date = {2022-10-16},
urldate = {2022-10-16},
booktitle = {ICCCM 2022: Proceedings of the 10th International Conference on Computer and Communications Management},
pages = {79-83},
abstract = {The maximum clique problem (MCP) is a fundamental combinatorial optimization problem that has many practical applications. In the exact methods, the idea of approximate coloring of vertices has been employed in the one proposed by Tomita, et al. in 1970's in order to prune unnecessary searching, and it now has become the important idea in the field of developing efficient exact algorithms for solving MCP. On the other hand, in the heuristic and metaheuristic research fields, few heuristics have been presented for MCP that use vertex coloring, and the search performance of a local search using the degree of saturation based on vertex coloring information is not clear. In this paper, we investigate the performance of a Local Search based on vertex coloring for MCP. Experimental results on the benchmark graphs show that the proposed algorithm is more effective than other simple Local Search for several difficult graphs such as perfect graphs.},
keywords = {Local search, Maximum clique problem, Vertex coloring},
pubstate = {published},
tppubtype = {inproceedings}
}
The maximum clique problem (MCP) is a fundamental combinatorial optimization problem that has many practical applications. In the exact methods, the idea of approximate coloring of vertices has been employed in the one proposed by Tomita, et al. in 1970's in order to prune unnecessary searching, and it now has become the important idea in the field of developing efficient exact algorithms for solving MCP. On the other hand, in the heuristic and metaheuristic research fields, few heuristics have been presented for MCP that use vertex coloring, and the search performance of a local search using the degree of saturation based on vertex coloring information is not clear. In this paper, we investigate the performance of a Local Search based on vertex coloring for MCP. Experimental results on the benchmark graphs show that the proposed algorithm is more effective than other simple Local Search for several difficult graphs such as perfect graphs.
Kazuho Kanahara, Tetsuya Oda, Elis Kulla, Akira Uejima, Kengo Katayama
An efficient local search for the maximum clique problem on massive graphs Proceedings Article
In: EIDWT 2022: Advances in Internet, Data & Web Technologies, Proceedings of the 10th International Conference on Emerging Internet, Data & Web Technologies, Lecture Notes on Data Engineering and Communications Technologies (LNDECT, volume 118), pp. 201–211, 2022.
Abstract | BibTeX | タグ: Local search, Massive graphs, Maximum clique problem, Multi-start k-opt local search | Links:
@inproceedings{KANAHARA-EIDWT-2022,
title = {An efficient local search for the maximum clique problem on massive graphs},
author = {Kazuho Kanahara and Tetsuya Oda and Elis Kulla and Akira Uejima and Kengo Katayama},
doi = {https://doi.org/10.1007/978-3-030-95903-6_22},
year = {2022},
date = {2022-02-02},
urldate = {2022-02-02},
booktitle = {EIDWT 2022: Advances in Internet, Data & Web Technologies, Proceedings of the 10th International Conference on Emerging Internet, Data & Web Technologies, Lecture Notes on Data Engineering and Communications Technologies (LNDECT, volume 118)},
pages = {201–211},
abstract = {The Maximum Clique Problem (MCP) is one of the most important combinatorial optimization problems that has many practical applications such as community search in social networks. Since the MCP is known to be NP-hard, much effort has been devoted to the development of metaheuristic algorithms to find a high quality clique (solution) within reasonable running times. The Multi-start k-opt Local Search incorporating k-opt local search (MKLS) is well known as a simple and effective metaheuristic for MCP. However it takes long time to search the high-quality solution for difficult massive graphs such as real world social networks, because the search space is too large. In the case of applying metaheuristic algorithms for massive sparse graphs, adequate process such as reduction process is necessary to focus on promising search space. In this paper, we present a Multi-start k-opt Local Search with graph Reduction process (MKLS-R), for solving the maximum clique problem on massive graphs. MKLS-R is evaluated on difficult massive graphs of Network-Repository graphs. The experimental results showed that the graph reduction process in MKLS-R contributes to the improvement of the search performance of MKLS for the difficult massive graphs.},
keywords = {Local search, Massive graphs, Maximum clique problem, Multi-start k-opt local search},
pubstate = {published},
tppubtype = {inproceedings}
}
The Maximum Clique Problem (MCP) is one of the most important combinatorial optimization problems that has many practical applications such as community search in social networks. Since the MCP is known to be NP-hard, much effort has been devoted to the development of metaheuristic algorithms to find a high quality clique (solution) within reasonable running times. The Multi-start k-opt Local Search incorporating k-opt local search (MKLS) is well known as a simple and effective metaheuristic for MCP. However it takes long time to search the high-quality solution for difficult massive graphs such as real world social networks, because the search space is too large. In the case of applying metaheuristic algorithms for massive sparse graphs, adequate process such as reduction process is necessary to focus on promising search space. In this paper, we present a Multi-start k-opt Local Search with graph Reduction process (MKLS-R), for solving the maximum clique problem on massive graphs. MKLS-R is evaluated on difficult massive graphs of Network-Repository graphs. The experimental results showed that the graph reduction process in MKLS-R contributes to the improvement of the search performance of MKLS for the difficult massive graphs.
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.
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.
2005
Kengo Katayama, Akihiro Hamamoto, Hiroyuki Narihisa
An effective local search for the maximum clique problem Journal Article
In: Information Processing Letters, vol. 95, no. 5, pp. 503-511, 2005, ISSN: 0020-0190.
Abstract | BibTeX | タグ: Combinatorial optimization, Graph algorithms, Maximum clique problem, Neighborhood, Variable depth search | Links:
@article{KATAYAMA-IPL-2005,
title = {An effective local search for the maximum clique problem},
author = {Kengo Katayama and Akihiro Hamamoto and Hiroyuki Narihisa},
url = {https://www.sciencedirect.com/science/article/pii/S0020019005001444},
doi = {https://doi.org/10.1016/j.ipl.2005.05.010},
issn = {0020-0190},
year = {2005},
date = {2005-01-01},
urldate = {2005-01-01},
journal = {Information Processing Letters},
volume = {95},
number = {5},
pages = {503-511},
abstract = {We propose a variable depth search based algorithm, called k-opt local search (KLS), for the maximum clique problem. KLS efficiently explores the k-opt neighborhood defined as the set of neighbors that can be obtained by a sequence of several add and drop moves that are adaptively changed in the feasible search space. Computational results on DIMACS benchmark graphs indicate that KLS is capable of finding considerably satisfactory cliques with reasonable running times in comparison with those of state-of-the-art metaheuristics.},
keywords = {Combinatorial optimization, Graph algorithms, Maximum clique problem, Neighborhood, Variable depth search},
pubstate = {published},
tppubtype = {article}
}
We propose a variable depth search based algorithm, called k-opt local search (KLS), for the maximum clique problem. KLS efficiently explores the k-opt neighborhood defined as the set of neighbors that can be obtained by a sequence of several add and drop moves that are adaptively changed in the feasible search space. Computational results on DIMACS benchmark graphs indicate that KLS is capable of finding considerably satisfactory cliques with reasonable running times in comparison with those of state-of-the-art metaheuristics.