| 講演名 | 2021-03-08 A hyper-heuristic for the maximum clique problem 金原 一歩(岡山理科大), 片山 謙吾(岡山理科大), 富田 悦次(電通大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | |
| 抄録(英) | 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 ?nding considerably satisfactory solutions and at least competitive in comparison with those of state-of-the-art metaheuristics. |
| キーワード(和) | |
| キーワード(英) | combinatorial optimizationmaximum clique problemhyper-heuristicmeta heuristiciterated local search |
| 資料番号 | COMP2020-34 |
| 発行日 | 2021-03-01 (COMP) |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2021/3/8(から1日開催) |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 増澤 利光(阪大) |
| 委員長氏名（英） | Toshimitsu Masuzawa(Osaka Univ.) |
| 副委員長氏名（和） | 小野 廣隆(名大) |
| 副委員長氏名（英） | Hirotaka Ono(Nagoya Univ) |
| 幹事氏名（和） | 大下 福仁(奈良先端大) / 安藤 映(専修大) |
| 幹事氏名（英） | Fukuhito Ooshita(NAIST) / Ei Ando(Senshu Univ.) |
| 幹事補佐氏名（和） | 大舘 陽太(名大) |
| 幹事補佐氏名（英） | Yota Otachi(Nagoya Univ) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | A hyper-heuristic for the maximum clique problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | / combinatorial optimizationmaximum clique problemhyper-heuristicmeta heuristiciterated local search |
| 第 1 著者 氏名（和/英） | 金原 一歩 / Kazuho Kanahara |
| 第 1 著者 所属（和/英） | 岡山理科大学(略称：岡山理科大) Okayama University of Science(略称：OUS) |
| 第 2 著者 氏名（和/英） | 片山 謙吾 / Kengo Katayama |
| 第 2 著者 所属（和/英） | 岡山理科大学(略称：岡山理科大) Okayama University of Science(略称：OUS) |
| 第 3 著者 氏名（和/英） | 富田 悦次 / Etsuji Tomita |
| 第 3 著者 所属（和/英） | 電気通信大学(略称：電通大) The University of Electro-Communications(略称：UEC) |
| 発表年月日 | 2021-03-08 |
| 資料番号 | COMP2020-34 |
| 巻番号（vol） | vol.120 |
| 号番号（no） | COMP-426 |
| ページ範囲 | pp.30-37(COMP), |
| ページ数 | 8 |
| 発行日 | 2021-03-01 (COMP) |