講演抄録/キーワード |
講演名 |
2021-03-08 15:15
A hyper-heuristic for the maximum clique problem ○Kazuho Kanahara・Kengo Katayama(OUS)・Etsuji Tomita(UEC) COMP2020-34 |
抄録 |
(和) |
(まだ登録されていません) |
(英) |
The maximum clique problem (MCP) is one of the most important combinatorial optimization problems that has many practical applications.
Since the MCP is known to be NP-hard, much effort has been devoted to the development of (meta) heuristic algorithms such as Iterated Local Search (ILS) based algorithms to find a high quality clique (solution) within reasonable running times.
In this paper, we propose a selection based hyper-heurisitc that adaptively switches between multiple ILSs by an online learning search strategy controller based on Thompson Sampling on a given graph to find a high quality solution for the MCP.
Computational results on DIMACS and BHOSLIB benchmark graphs indicate that the proposed hyper-heuristic is capable of finding considerably satisfactory solutions and at least competitive in comparison with those of state-of-the-art metaheuristics. |
キーワード |
(和) |
/ / / / / / / |
(英) |
combinatorial optimization / maximum clique problem / hyper-heuristic / meta heuristic / iterated local search / / / |
文献情報 |
信学技報, vol. 120, no. 426, COMP2020-34, pp. 30-37, 2021年3月. |
資料番号 |
COMP2020-34 |
発行日 |
2021-03-01 (COMP) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2020-34 |