講演抄録/キーワード |
講演名 |
2007-11-19 10:15
巡回セールスマン問題のための逆関数遅延ネットワーク ○曽田尚宏・早川吉弘・中島康治(東北大) NC2007-64 |
抄録 |
(和) |
ニューラルネットワークの超並列性を活かして,組み合わせ最適化問題を解く研究が,これまで多くなされてきた.我々は,ダイナミクス中に負性抵抗を設定することができる逆関数遅延モデル(IDモデル)を提案しており,これによって極小値問題を回避できることが確認されている.実際,N-Queenに代表される問題では,ネットワークの状態が静止すれば100%正解が得られることが示されている.しかし,巡回セールスマン問題(TSP)については,静止状態で必ずしも正解を得ることができなかった.
そこで本研究では,IDモデルに高次シナプス結合を導入した高次シナプスIDモデルを提案する.そして高次シナプスIDネットワークをTSPに適応することで,最小値のみを安定にできる可能性があることを確認する.さらに,実際に4都市のTSPについて,静止状態では100%正解が得られることを示した. |
(英) |
Many researchers have attempted to solve the combinatorial optimization problems by using neural networks which have high parallel processing ability. We have proposed the Inverse function Delayed model(ID model) which has tha negative resistance in its dynamics, and confirmed that it solved local minimum problems. In some problems typified by the N-Queen problem, we have shown that the ID model achieves 100% sucess rate when
the output of the neuron reaches a final stationary state. However, for a Traveling Salesman Problem (TSP), it is not always possible to obtain optimal solutions at the stationary state.
In this paper, we introduce higher-order connections to the ID Model. In case of the higher-order connections, we confirm the possibility that the only global minimum in TSP is stabilized by the negative resistance. Moreover, in the computer simulation of 4cities TSP, we show that the ID model can get optimal solutions at a rate of 100% when it reaches the stationary state. |
キーワード |
(和) |
ニューラルネットワーク / 巡回セールスマン問題 / 逆関数遅延モデル / 高次シナプス結合 / 負性抵抗領域 / / / |
(英) |
neural network / Traveling Salesman Problem / Inverse function Delayed model / higher-order connection / negative resistance / / / |
文献情報 |
信学技報, vol. 107, no. 328, NC2007-64, pp. 55-60, 2007年11月. |
資料番号 |
NC2007-64 |
発行日 |
2007-11-11 (NC) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
NC2007-64 |
研究会情報 |
研究会 |
NC |
開催期間 |
2007-11-18 - 2007-11-19 |
開催地(和) |
佐賀大学 |
開催地(英) |
Saga Univ. |
テーマ(和) |
ニューロハードウェア, 一般 |
テーマ(英) |
neuro-hardware, and general |
講演論文情報の詳細 |
申込み研究会 |
NC |
会議コード |
2007-11-NC |
本文の言語 |
日本語 |
タイトル(和) |
巡回セールスマン問題のための逆関数遅延ネットワーク |
サブタイトル(和) |
|
タイトル(英) |
Inversed Function Delayed Network for Traveling Salesman Problem |
サブタイトル(英) |
|
キーワード(1)(和/英) |
ニューラルネットワーク / neural network |
キーワード(2)(和/英) |
巡回セールスマン問題 / Traveling Salesman Problem |
キーワード(3)(和/英) |
逆関数遅延モデル / Inverse function Delayed model |
キーワード(4)(和/英) |
高次シナプス結合 / higher-order connection |
キーワード(5)(和/英) |
負性抵抗領域 / negative resistance |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第1著者 氏名(和/英/ヨミ) |
曽田 尚宏 / Takahiro Sota / ソタ タカヒロ |
第1著者 所属(和/英) |
東北大学 (略称: 東北大)
Tohoku University (略称: Tohoku Univ.) |
第2著者 氏名(和/英/ヨミ) |
早川 吉弘 / Yoshihiro Hayakawa / ハヤカワ ヨシヒロ |
第2著者 所属(和/英) |
東北大学 (略称: 東北大)
Tohoku University (略称: Tohoku Univ.) |
第3著者 氏名(和/英/ヨミ) |
中島 康治 / Koji Nakajima / ナカジマ コウジ |
第3著者 所属(和/英) |
東北大学 (略称: 東北大)
Tohoku University (略称: Tohoku Univ.) |
第4著者 氏名(和/英/ヨミ) |
/ / |
第4著者 所属(和/英) |
(略称: )
(略称: ) |
第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著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2007-11-19 10:15:00 |
発表時間 |
25分 |
申込先研究会 |
NC |
資料番号 |
NC2007-64 |
巻番号(vol) |
vol.107 |
号番号(no) |
no.328 |
ページ範囲 |
pp.55-60 |
ページ数 |
6 |
発行日 |
2007-11-11 (NC) |