抵抗クロスバー回路を備えた粘菌型アナログ電子解探索システムにおける最大カット問題解法

DOI オープンアクセス

書誌事項

タイトル別名
  • Amoeba-Inspired All-Analog Electronic Computing System Integrating Crossbar Circuit That Solves Maximum Cut Problem

抄録

社会的要請の高まる組合せ最適化処理を従来型コンピュータ(CPU)より大幅に高速化できる専用マシンの実現を目指し,我々はアメーバ生物・粘菌が環境適応的な変形行動により組合せ最適化問題の解を探索するダイナミックスをアナログ電子回路で模倣する「電子アメーバ」を提案している.本研究では,NP困難問題である最大カット問題を対象とし,ブレッドボード上に構成された抵抗クロスバー回路を具備する電子アメーバが,最小規模の問題例の最適解を正しく探索できることを実証した.更に,規模をノード数5000まで拡大した問題例について数値シミュレーションを行い,電子アメーバが規模に依らずほぼ一定の時間で比較的質の高い(カットサイズの大きい)準最適解に収束する結果を得た.しかし,それら準最適解の質は,初期値の選択に依存することが,遺伝的アルゴリズムを用いた調査により確かめられた.今後,初期値の選択に依らず大域最適解に近い質の解を高速に導出できる電子アメーバの実現に向け,準最適解での収束を回避する機構の導入が鍵となることが明らかになった.

関連プロジェクト

もっと見る

詳細情報 詳細情報について

  • CRID
    1390291189507615104
  • DOI
    10.14923/transelej.2021jci0011
  • ISSN
    18810217
  • 本文言語コード
    ja
  • データソース種別
    • JaLC
    • KAKEN
  • 抄録ライセンスフラグ
    使用不可

問題の指摘

ページトップへ