| 講演名 | 1997/2/6 SAを用いたラグランジェ調整型TSPニューラルネットの大域的最適化 佐藤 義宣, 村上 謙二, 大掘 隆文, 渡辺 一央, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 著者らは、以前、Hopfieldニューラルネット(NN)により、巡回セールスマン問題(TSP)を解くとき、エネルギー関数として拡大ペナルティ関数を用いたラグランジェ調整型TSPNN(LNN)を提案した。しかし、LNN)はエネルギー関数の局所的鞍点を求めるNNであるため、解の質がニューロンばかりではなくラグランジェ乗数の初期値に大きく依存するという問題があった。本論文では、LNNの収束点である局所的鞍点の中から原問題の大域的最適解を探索するために、シミュレーティッドアニーリング(SA)に基づきラグランジェ乗数を制御する方法を提案する。すなわち、LNNによりある局所的鞍点を求めた後、乱数により摂動したラグランジェ乗数を初期値とするLNNを再び動作させ、その収束点である局所的鞍点を確率的に受理しながら探索を行う手法である。提案手法の有効性を確認するために、20都市のTSPに対するシミュレーション実験を行い、Hopfield NN 及びLNNとの比較を行う。 |
| 抄録(英) | The augmented penalty function using the Lagrange multipliers was proposed to improve the feasibility and the performance of the Hopfield network with the penalty function for the travelling salesmans problem(TSP). However, the network converges a local saddle point of the augmented penalty function, and thus the performance of the network depends on initial Lagrange multipliers as well as initial neuron outputs. We propose a new simulated annealing algorithm to find the global optimum among local saddle points. Any local saddle point is perturbed by random noises and the network converges to another local saddle point, which is accepted stochastically based on the quality of the saddle point. Computational results for the TSP with random 20 cities show that the proposed method significantly improves the quality of the solutions, compared with the conventional methods. |
| キーワード(和) | Hopfieldニューラルネット / 巡回セールスマン問題 / ラグランジェ乗数 / 拡大ペナルティ関数 / シミュレーティッドアニーリング |
| キーワード(英) | Hopfield neural network / travelling salesman problem / Lagrange multipliers / augmented penalty function / simulated annealing |
| 資料番号 | NLP96-124,NC96-78 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NLP |
|---|---|
| 開催期間 | 1997/2/6(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Nonlinear Problems (NLP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | SAを用いたラグランジェ調整型TSPニューラルネットの大域的最適化 |
| サブタイトル（和） | |
| タイトル（英） | Global Optimization of the TSP Neural Networks with Lagrange Multipliers by Using Simulated Annealing. |
| サブタイトル（和） | |
| キーワード(1)（和/英） | Hopfieldニューラルネット / Hopfield neural network |
| キーワード(2)（和/英） | 巡回セールスマン問題 / travelling salesman problem |
| キーワード(3)（和/英） | ラグランジェ乗数 / Lagrange multipliers |
| キーワード(4)（和/英） | 拡大ペナルティ関数 / augmented penalty function |
| キーワード(5)（和/英） | シミュレーティッドアニーリング / simulated annealing |
| 第 1 著者 氏名（和/英） | 佐藤 義宣 / Yoshinobu SATO |
| 第 1 著者 所属（和/英） | 北海道工業大学電気工学科 Department of Electrical Engineering, Hokkaido Institute of Technology |
| 第 2 著者 氏名（和/英） | 村上 謙二 / Kenji MURAKAMI |
| 第 2 著者 所属（和/英） | 北海道工業大学電気工学科 Department of Electrical Engineering, Hokkaido Institute of Technology |
| 第 3 著者 氏名（和/英） | 大掘 隆文 / Takahumi OOHORI |
| 第 3 著者 所属（和/英） | 北海道工業大学電気工学科 Department of Electrical Engineering, Hokkaido Institute of Technology |
| 第 4 著者 氏名（和/英） | 渡辺 一央 / Kazuhisa WATANABE |
| 第 4 著者 所属（和/英） | 北海道工業大学電気工学科 Department of Electrical Engineering, Hokkaido Institute of Technology |
| 発表年月日 | 1997/2/6 |
| 資料番号 | NLP96-124,NC96-78 |
| 巻番号（vol） | vol.96 |
| 号番号（no） | 509 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |