講演抄録/キーワード |
講演名 |
2014-03-10 15:40
粘菌アメーバ型解探索アルゴリズムとそのナノデバイスによる実現 ○巳波弘佳(関西学院大)・青野真士(東工大/JST)・成瀬 誠(NICT)・葛西誠也(北大) COMP2013-71 |
抄録 |
(和) |
これまで,計算困難問題に対する様々なメタヒューリスティックアルゴリズムが研究されてきた.その一つとして,粘菌アメーバの示す時空間振動ダイナミクスに着想を得た解探索アルゴリズムがある.このアルゴリズムは,高速な解探索能力を示し,さらに低消費エネルギーで超小型のナノデバイスにより実装することも比較的容易である.
本稿では,計算困難問題の一つである充足可能性判定問題(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 / / / |
文献情報 |
信学技報, vol. 113, no. 488, COMP2013-71, pp. 77-82, 2014年3月. |
資料番号 |
COMP2013-71 |
発行日 |
2014-03-03 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2013-71 |