ニューラルネットワークによる組合せ最適化問題の一般的解法

近松 良知  阿江 忠  山下 雅史  

誌名
電子情報通信学会論文誌 D   Vol.J78-D2   No.3   pp.532-539
発行日: 1995/03/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1923
論文種別: 論文
専門分野: バイオサイバネティックス,ニューロコンピューティング
キーワード: 
動的-静的ニューラルネットワーク,  CNF-3SAT問題,  シグマ-パイニューロン,  非線形制約付き最適化問題,  

本文: PDF(556.2KB)>>
論文を購入




あらまし: 
ダイナミックな動作をするサブネットとスタティックな動作をするサブネットの,二つのサブネットより構成される動的-静的ニューラルネットワーク(DS-net)による,組合せ最適化問題の解法について述べる.一般に,組合せ最適化問題をニューラルネットワークによって解く場合,変数の2次式(特に,双1次形式)で表された関数の最小化として定式化された問題を扱うが,Yaoらが提案したDS-netは,線形制約を処理するサブネットをもち,線形制約付き最小化問題をそのままの形でマッピングできるという特徴がある.本論文では,シグマ-パイニューロンの導入により,目的関数と制約条件がともに2次の非線形制約付き最適化問題をも扱うことができるように,DS-netを拡張する.そして,和積標準形論理式の充足可能性問題(CNF-3SAT問題)がこのような非線形制約付きの最小化問題へ変換できることから,提案するニューラルネットワーク解法がNP完全な組合せ問題の一般的な解法となり得ることを示す.また,シミュレーション実験により,本手法の有効性を検証する.その結果,本手法がグリーディー解法の動作をネットワーク動作に埋め込めることが示され,また最適解を求める上で重要となるネットワークの初期状態の選び方が与えられる.