講演抄録/キーワード |
講演名 |
2015-05-18 15:20
A Method for Deciding Feasible Solution of Quadratic Assignment Problem from Mutually Connected Chaotic Neural Network ○Takafumi Matsuura(Nippon Inst. of Tech.)・Tohru Ikeguchi(Tokyo Univ. Sci.) NLP2015-31 |
抄録 |
(和) |
2次割当問題の良好な近似解を求める発見的解法として,相互結合型カオスニューラルネットを用いた手法が提案されている.この解法は,ニューラルネットを構成するカオスニューロンのカオスダイナミクスが局所最適解を回避し効果的な解探索を実現している.しかし,カオスニューロンの出力は実数値であるため,ニューラルネットワークの出力値から0-1整数計画問題である2次割当問題の実行可能解を得ることは非常に困難である.カオスニューラルネットワークの状態から,解を決定する手法として,筆者らは,解を構成するニューロンの内部状態値の総和が大きくなように2次割当問題の解を決定する方法を提案し,小さいサイズの問題例に対して良好な解が得られることを報告している.本論文では,大規模サイズのべンチマーク問題に対して性能評価を行い,大規模問題に対しても良好な近似解が得られたことを報告する. |
(英) |
For finding good near-optimal solutions of quadratic assignment problems (QAPs), a heuristic method which uses a mutually connected chaotic neural network (CNN) has already been proposed. In the method, chaotic dynamics of the CNN controls to search a solution space effectively. However, it is difficult to generate feasible solutions of the QAP from the CNN, because an output of a chaotic neuron takes a real-valued. To generate a feasible solution of the QAP, we have already proposed a method for deciding feasible solutions of the QAP from the CNN. In the method, a sum of value of an internal state of neurons which construct the solution of the QAP is maximized. As a result, the method showed good performances for small-size of instances. In this report, we investigate performances of the method for large-size of instances and show that the method also finds good approximate solutions of large-size of instances. |
キーワード |
(和) |
2次割当問題 / カオスニューラルネットワーク / カオスニューロン / 発見的解法 / / / / |
(英) |
quadratic assignment problem / chaotic neural network / chaotic neuron / heuristic algorithm / / / / |
文献情報 |
信学技報, vol. 115, no. 34, NLP2015-31, pp. 23-28, 2015年5月. |
資料番号 |
NLP2015-31 |
発行日 |
2015-05-11 (NLP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
NLP2015-31 |