発表・業績 | Publications

@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}

}

@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}

}

@inproceedings{ITO-ICCCM-2022,

title = {An extended NEH based method for permutation flowshop scheduling problem},

author = {Shun Ito and Kazuho Kanahara and Tetsuya Oda and Kengo Katayama},

doi = {https://doi.org/10.1145/3556223.3556261},

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 = {252-256},

abstract = {The Permutation Flowshop Scheduling Problem (PFSP) is an important manufacturing scheduling problem where jobs have to be processed on machines, with each job following the same order at the machines. Since the problem to minimize makespan has been proven NP-hard when the number of machines is larger than three, a number of heuristic methods have been developed for finding high quality solutions in a reasonable computation time. NEH heuristic is one of the most efficient and effective constructive heuristic methods for PFSP. NEH algorithm consists of two key steps 1) order jobs based on priority rule (the original one is the sum (average) processing times of each job); 2) insert jobs one by one according to the initial job order to construct a sequence (solution) of jobs by testing all possible inserting positions for unscheduled jobs. Since the first step is crucial for the resulting solution quality, many different priority rules have been investigated. It is well known that the priority rule based on two moments of the average and standard deviation of processing times to order jobs is effective. Furthermore, a more effective priority rule including a third moment called skewness has been developed recently. In this paper, we present an extended NEH based method called Extended NEH (E-NEH) for PFSP in which the appropriate combination of moments is selected from the three moments step by step, depending on the search situation. Computational results on benchmark problem set showed that E-NEH obtained better results, or at least the competitive ones, than the original NEH and other NEH based methods including the rules based on the three moments although more computation times are required.},

keywords = {Heuristic, NEH, Permutation flowshop scheduling problem},

pubstate = {published},

tppubtype = {inproceedings}

}

@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}

}

@inproceedings{MIYAKE-GCCE-2020,

title = {Applying a local search for the uncapacitated p-median problem to the capacitated problem},

author = {Takafumi Miyake and Kengo Katayama and Kazuho Kanahara and Tetsuya Oda},

doi = {10.1109/GCCE50665.2020.9291874},

year  = {2020},

date = {2020-10-13},

urldate = {2020-10-13},

booktitle = {GCCE 2020: 2020 IEEE 9th Global Conference on Consumer Electronics},

pages = {835-836},

abstract = {Capacitated p-Median Problem (CPMP) is an important combinatorial optimization problem with practical applications such as determining the location and scale of power generation facilities in green energy field. The objective of CPMP is to find p facilities and assign each area to exactly one facility such that the total distance of assigned areas to their corresponding facilities is minimized, and the capacity limit on the facilities is not exceeded. In the CPMP solution, it is important to satisfy the capacity constraints of all opened facilities. In searching high quality solutions, the effectiveness of allowing the search for infeasible space has not been fully investigated in CPMP. In this paper, we present a novel search approach called Extend Space Strategy (ESS) that extends the search to infeasible space by using algorithms for a simplified and related problem not including major constraints. Computational results show that ESS is more effective to obtain better solutions than the standard approach that searches only feasible space.},

keywords = {Capacitated p-median problem, Local search},

pubstate = {published},

tppubtype = {inproceedings}

}

@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}

}

@inproceedings{OKANO-GEEC-2018,

title = {A local search based on variant variable depth search for the quadratic assignment problem},

author = {Takeshi Okano and Kengo Katayama and Kazuho Kanahara and Noritaka Nishihara},

doi = {10.1109/GCCE.2018.8574497},

year  = {2018},

date = {2018-10-09},

urldate = {2018-10-09},

booktitle = {GEEC-2018: 2018 IEEE 7th Global Conference on Consumer Electronics},

pages = {60-63},

abstract = {The quadratic assignment problem (QAP) has practical applications in the electronics domain, such as component placing on circuit boards, minimizing the number of transistors on integrated circuits, optimal placing of letters on touchscreen devices, etc. Since QAP is NP-hard and large problems are not practically solvable to optimality, heuristic methods such as local search are regarded as an efficient algorithm to obtain near optimal solutions within a reasonable time. In this paper, we present a new sophisticated local search algorithm, called variant k-opt local search (vKLS), based on a variant of the variable depth search for QAP. Computational results show that vKLS is capable of finding better solutions on average than the standard VDS and typical 2-opt local search algorithms.},

keywords = {Quadratic assignment problem, Variable depth search},

pubstate = {published},

tppubtype = {inproceedings}

}

@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}

}

@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}

}

@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}

}

@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}

}

@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}

}

@inproceedings{KATAYAMA-SAC-2005,

title = {Reinforcement learning agents with primary knowledge designed by analytic hierarchy process},

author = {Kengo Katayama and Takahiro Koshiishi and Hiroyuki Narihisa},

doi = {https://doi.org/10.1145/1066677.1066685},

year  = {2005},

date = {2005-03-13},

urldate = {2005-03-13},

booktitle = {SAC 2005: Proceedings of the 2005 ACM symposium on Applied computing},

pages = {14-21},

abstract = {This paper presents a novel model of reinforcement learning agents. A feature of our learning agent model is to integrate analytic hierarchy process (AHP) into a standard reinforcement learning agent model, which consists of three modules: state recognition, learning, and action selecting modules. In our model, AHP module is designed with primary knowledge that human intrinsically should have in order to attain a goal state. This aims at increasing promising actions of agent especially in the earlier stages of learning instead of completely random actions as in the standard reinforcement learning algorithms. We adopt profit-sharing as a reinforcement learning algorithm and demonstrate the potential of our approach on two learning problems of a pursuit problem and a Sokoban problem with deadlock in the grid-world domains, where results indicate that the learning time can be decreased considerably for the problems and our approach efficiently avoids the deadlock for the Sokoban problem. We also show that bad effect that can be usually observed by introducing a priori knowledge into reinforcement learning process can be restrained by a method that decreases a rate of using knowledge during learning.},

keywords = {Analytic hierarchy process, Machine learning, Profit-sharing, Reinforcement learning, Sokoban problem},

pubstate = {published},

tppubtype = {inproceedings}

}

@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}

}

@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}

}

@inproceedings{KATAYAMA-GECCO-1999,

title = {Iterated local search approach using genetic transformation to the traveling salesman problem},

author = {Kengo Katayama and Hiroyuki Narihisa},

url = {https://dl.acm.org/doi/10.5555/2933923.2933956},

year  = {1999},

date = {1999-07-13},

urldate = {1999-07-13},

booktitle = {GECCO 1999: Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation},

volume = {1},

pages = {321-328},

abstract = {When giving different approximate solutions that are near the optimal solution for a combinatorial optimization problem, these solutions may share several important or common parts. This empirical conjecture is often employed in developing good algorithms for solving combinatorial optimization problems. In this paper, we propose a new iterated local search (ILS) approach incorporating this conjecture for the symmetric traveling salesman problem. To escape from local optimum found by a local search procedure to another, standard ILS algorithms generally have an useful technique called the double-bridge move. However, in our approach we deal with two approximate solutions, which contain many edges which are not shared parts of these solutions. These edges are cleverly reconnected to create a newly escaped solution. From our experimental results, it was observed that our ILS algorithms could find better solution qualities with fewer iterations than standard ILS algorithms for well-known benchmarks of the TSPLIB. In particular, we showed that one algorithm combined with the Lin-Kernighan heuristic was a very high-performance approach.},

keywords = {Double-bridge, Genetic iterated local search, Genetic transformation, Lin-Kernighan heuristic, Traveling salesman problem},

pubstate = {published},

tppubtype = {inproceedings}

}