相互結合型カオスニューラルネットワークから二次割当問題の解を決定する方法

概要

論文の詳細を見る
二次割当問題(QAP)はNP困難なクラスに属する組合せ最適化問題である.現実的な時間内でQAPの良好な解を求める近似解法として相互結合型カオスニューラルネット(CNN)を用いた手法が提案されている.CNNを用いた解法では,CNNを構成するカオスニューロンのカオスダイナミクスが局所最適解を回避し効果的な解探索を実現している.しかし,カオスニューロンの出力はアナログ値であるため,ニューラルネットワークの出力値からQAP.の実行可能解を得ることは困難である.そのため,強制的に解を決定する手法が必要である.筆者らは,強制的に解を決定する方針として,ニューロンの内部状態値の和が最大となようにQAPの解を構成するニューロンを選択することで,良い解が得られることを報告している.本論文では,カオスニューロンの状態からQAPの解を決定するさい,内部状態値の和を改善するための改善法を提案する.提案手法は単純な改善操作であるが,QAPLIBのベンチマーク問題を用いて性能評価を行った結果,良好な解が得られることが明らかとなった.
2013-10-21