| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 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 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2014-03-10 - 2014-03-10 |
| 開催地（和） | 明治大学 |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2014-03-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | 粘菌アメーバ型解探索アルゴリズムとそのナノデバイスによる実現 |
| サブタイトル（和） | |
| タイトル（英） | Amoeba-inspired Algorithm and Its Realization Using Nanodevice |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 粘菌 / Amoeba |
| キーワード(2)（和/英） | メタヒューリスティック / Metaheuristics |
| キーワード(3)（和/英） | アルゴリズム / Algorithm |
| キーワード(4)（和/英） | 計算困難問題 / Intractable Computational Problem |
| キーワード(5)（和/英） | ナノデバイス / Nanodevice |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 巳波 弘佳 / Hiroyoshi Miwa / ミワ ヒロヨシ |
| 第1著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 青野 真士 / Mashashi Aono / アオノ マサシ |
| 第2著者 所属（和/英） | 東京工業大学/JSTさきがけ (略称： 東工大/JST) Tokyo Institute of Technology/JST PRESTO (略称： Tokyo Tech/JST) |
| 第3著者 氏名（和/英/ヨミ） | 成瀬 誠 / Makoto Naruse / ナルセ マコト |
| 第3著者 所属（和/英） | 情報通信研究機構 (略称： NICT) National Institute of Information and Communications Technology (略称： NICT) |
| 第4著者 氏名（和/英/ヨミ） | 葛西 誠也 / Seiya Kasai / カサイ セイヤ |
| 第4著者 所属（和/英） | 北海道大学 (略称： 北大) Hokkaido University (略称： Hokkaido Univ.) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2014-03-10 15:40:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2013-71 |
| 巻番号（vol） | vol.113 |
| 号番号（no） | no.488 |
| ページ範囲 | pp.77-82 |
| ページ数 | 6 |
| 発行日 | 2014-03-03 (COMP) |
[研究会発表申込システムのトップページに戻る]