| 講演名 | 2014-03-10 粘菌アメーバ型解探索アルゴリズムとそのナノデバイスによる実現 巳波 弘佳, 青野 真士, 成瀬 誠, 葛西 誠也, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | これまで,計算困難問題に対する様々なメタヒューリスティックアルゴリズムが研究されてきた.その一つとして,粘菌アメーバの示す時空間振動ダイナミクスに着想を得た解探索アルゴリズムがある.このアルゴリズムは,高速な解探索能力を示し,さらに低消費エネルギーで超小型のナノデバイスにより実装することも比較的容易である.本稿では,計算困難問題の一つである充足可能性判定問題(SAT)を解く粘菌アメーバ型解探索アルゴリズムについて,粘菌アメーバ型解探索が安定状態に入ったことを判定するための条件を明らかにした.さらに,安定状態であることと,そのときSATの解が得られていることが等価であることを示した.これにより,安定条件を満たすことがわかれば直ちにSATの解を得ることができるため,粘菌アメーバ型解探索アルゴリズムを実装したデバイスによる厳密で高速な解到達判定が可能となった. |
| 抄録(英) | Many metaheuristic algorithms have been studied so far to search for fairy good solutions to intractable computational problems. Amoeba-inspired computing, which is based on complex spatiotemporal oscillatory dynamics, is one of the metaheiristics; and it can search for a solution to a highly complex combinatorial optimization problem quickly. Amoeba-inspired computing can be implemented using various nanoscale devices with low energy consumption that exhibit suitable spatiotemporal dynamics resembling the amoeba's problem-solving process. However, because no effective judgement condition to halt the search process was known, we had to wait for sufficiently long time till the system stabilizes persistently. In addition, it was unknown whether, when the system reaches a stable state, the stable state represents a solution to the problem or not. In this article, first, we define the stability of an amoeba-inspired algorithm for solving the satisfiability problem (SAT). The stability can be easily checked. Moreover, we prove that, if and only if the algorithm reaches a stable state, the state gives a solution to SAT. These results reduce the execution time of the algorithm and guarantee theoretically that, when the algorithm stabilizes, we can obtain a solution. |
| キーワード(和) | 粘菌 / メタヒューリスティック / アルゴリズム / 計算困難問題 / ナノデバイス |
| キーワード(英) | Amoeba / Metaheuristics / Algorithm / Intractable Computational Problem / Nanodevice |
| 資料番号 | COMP2013-71 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2014/3/3(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 粘菌アメーバ型解探索アルゴリズムとそのナノデバイスによる実現 |
| サブタイトル（和） | |
| タイトル（英） | Amoeba-inspired Algorithm and Its Realization Using Nanodevice |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 粘菌 / Amoeba |
| キーワード(2)（和/英） | メタヒューリスティック / Metaheuristics |
| キーワード(3)（和/英） | アルゴリズム / Algorithm |
| キーワード(4)（和/英） | 計算困難問題 / Intractable Computational Problem |
| キーワード(5)（和/英） | ナノデバイス / Nanodevice |
| 第 1 著者 氏名（和/英） | 巳波 弘佳 / Hiroyoshi MIWA |
| 第 1 著者 所属（和/英） | 関西学院大学大学院理工学研究科 Graduate School of Science and Technology, Kwansei Gakuin University |
| 第 2 著者 氏名（和/英） | 青野 真士 / Masashi AONO |
| 第 2 著者 所属（和/英） | 東京工業大学大学院地球生命研究所:JSTさきがけ Earth-Life Science Institute, Tokyo Institute of Technology:JST PRESTO |
| 第 3 著者 氏名（和/英） | 成瀬 誠 / Makoto NARUSE |
| 第 3 著者 所属（和/英） | 情報通信研究機構光ネットワーク研究所 Photonic Network Research Institute, National Institute of Information and Communications Technology |
| 第 4 著者 氏名（和/英） | 葛西 誠也 / Seiya KASAI |
| 第 4 著者 所属（和/英） | 北海道大学大学院情報科学研究科:北海道大学量子集積エレクトロニクス研究センター Graduate School of Information Science and Technology, Hokkaido University:RCIQE, Hokkaido University |
| 発表年月日 | 2014-03-10 |
| 資料番号 | COMP2013-71 |
| 巻番号（vol） | vol.113 |
| 号番号（no） | 488 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |