当研究室で取り組んでいる研究に関する論文・講演などの情報（一部抜粋）です。
Here is a selection of our published papers on the research we’ve been working on in our laboratory.
Our Selected Papers and Keywords
2004
Peter Merz, Kengo Katayama
Memetic algorithms for the unconstrained binary quadratic programming problem Journal Article
In: Biosystems, vol. 78, no. 1, pp. 99-118, 2004, ISSN: 0303-2647.
Abstract | BibTeX | タグ: Combinatorial optimization, Evolutionary algorithm, Fitness landscape analysis, Local search, Memetic algorithms, Unconstrained binary quadratic programming problem | Links:
@article{MERZ-Biosystems-2004,
title = {Memetic algorithms for the unconstrained binary quadratic programming problem},
author = {Peter Merz and Kengo Katayama},
url = {https://www.sciencedirect.com/science/article/pii/S0303264704001376},
doi = {https://doi.org/10.1016/j.biosystems.2004.08.002},
issn = {0303-2647},
year = {2004},
date = {2004-01-01},
urldate = {2004-01-01},
journal = {Biosystems},
volume = {78},
number = {1},
pages = {99-118},
abstract = {This paper presents a memetic algorithm, a highly effective evolutionary algorithm incorporating local search for solving the unconstrained binary quadratic programming problem (BQP). To justify the approach, a fitness landscape analysis is conducted experimentally for several instances of the BQP. The results of the analysis show that recombination-based variation operators are well suited for the evolutionary algorithms with local search. Therefore, the proposed approach includes — besides a highly effective randomized k-opt local search — a new variation operator that has been tailored specially for the application in the hybrid evolutionary framework. The operator is called innovative variation and is fundamentally different from traditional crossover operators, since new genetic material is included in the offspring which is not contained in one of the parents. The evolutionary heuristic is tested on 35 publicly available BQP instances, and it is shown experimentally that the algorithm is capable of finding best-known solutions to large BQPs in a short time and with a high frequency. In comparison to other approaches for the BQP, the approach appears to be much more effective, particularly for large instances of 1000 or 2500 binary variables.},
keywords = {Combinatorial optimization, Evolutionary algorithm, Fitness landscape analysis, Local search, Memetic algorithms, Unconstrained binary quadratic programming problem},
pubstate = {published},
tppubtype = {article}
}
This paper presents a memetic algorithm, a highly effective evolutionary algorithm incorporating local search for solving the unconstrained binary quadratic programming problem (BQP). To justify the approach, a fitness landscape analysis is conducted experimentally for several instances of the BQP. The results of the analysis show that recombination-based variation operators are well suited for the evolutionary algorithms with local search. Therefore, the proposed approach includes — besides a highly effective randomized k-opt local search — a new variation operator that has been tailored specially for the application in the hybrid evolutionary framework. The operator is called innovative variation and is fundamentally different from traditional crossover operators, since new genetic material is included in the offspring which is not contained in one of the parents. The evolutionary heuristic is tested on 35 publicly available BQP instances, and it is shown experimentally that the algorithm is capable of finding best-known solutions to large BQPs in a short time and with a high frequency. In comparison to other approaches for the BQP, the approach appears to be much more effective, particularly for large instances of 1000 or 2500 binary variables.
2001
Kengo Katayama, Hiroyuki Narihisa
Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem Journal Article
In: European Journal of Operational Research, vol. 134, no. 1, pp. 103-119, 2001, ISSN: 0377-2217.
Abstract | BibTeX | タグ: Heuristics, Large-size problems, Local search, Simulated annealing, Unconstrained binary quadratic programming problem | Links:
@article{KATAYAMA-EJOR-2001,
title = {Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem},
author = {Kengo Katayama and Hiroyuki Narihisa},
url = {https://www.sciencedirect.com/science/article/pii/S0377221700002423},
doi = {https://doi.org/10.1016/S0377-2217(00)00242-3},
issn = {0377-2217},
year = {2001},
date = {2001-01-01},
urldate = {2001-01-01},
journal = {European Journal of Operational Research},
volume = {134},
number = {1},
pages = {103-119},
abstract = {The unconstrained binary quadratic programming problem (BQP) is known to be NP-hard and has many practical applications. This paper presents a simulated annealing (SA)-based heuristic for the BQP. The new SA heuristic for the BQP is based on a simple (1-opt) local search heuristic and designed with a simple cooling schedule, but the multiple annealing processes are adopted. To show practical performances of the SA, we test on publicly available benchmark instances of large size ranging from 500 to 2500 variables and compare them with other heuristics such as multi-start local search, the previous SA, tabu search, and genetic algorithm incorporating the 1-opt local search. Computational results indicate that our SA leads to high-quality solutions with short times and is more effective than the competitors particularly for the largest benchmark set. Furthermore, the values of new best-known solutions found by the SA for several large instances are also reported.},
keywords = {Heuristics, Large-size problems, Local search, Simulated annealing, Unconstrained binary quadratic programming problem},
pubstate = {published},
tppubtype = {article}
}
The unconstrained binary quadratic programming problem (BQP) is known to be NP-hard and has many practical applications. This paper presents a simulated annealing (SA)-based heuristic for the BQP. The new SA heuristic for the BQP is based on a simple (1-opt) local search heuristic and designed with a simple cooling schedule, but the multiple annealing processes are adopted. To show practical performances of the SA, we test on publicly available benchmark instances of large size ranging from 500 to 2500 variables and compare them with other heuristics such as multi-start local search, the previous SA, tabu search, and genetic algorithm incorporating the 1-opt local search. Computational results indicate that our SA leads to high-quality solutions with short times and is more effective than the competitors particularly for the largest benchmark set. Furthermore, the values of new best-known solutions found by the SA for several large instances are also reported.
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.