講演名 | 2000/7/17 DSP2000-74 / SST2000-33 GA経路探索における収束速度の改善に関する考察 稲垣 潤, 長谷山 美紀, 北島 秀夫, |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | 遺伝的アルゴリズム(GA)を用いて指定された複数ノードを経由する最短経路探索手法が既に提案されている.この手法は, 個体の持つ経由点数に基づいて制御される重みが導入された新たな評価関数を用いることにより, 従来法における初期集団の発生や交叉の処理において生じる致死遺伝子が保持していた有効なスキマタを消失させずに探索を行い, 計算量を削減している.本稿では, 評価関数の重みの制御手法を改良することにより, より効率的に最適解に収束させる手法を提案する.さらに, 初期集団の発生方法を改良することにより収束速度を改善し, その有効性を実験によって確認する. |
抄録(英) | The authors have proposed a method of searching the shortest route through several designated points with a genetic algorithm. It uses a fitness function including weight parameters which are controlled based on a building block hypothesis. This function makes it possible to reduce the calculation cost by letting good schemata even in the lethal chromosomes survive. This paper proposes a method which can converge to the optimum more efficiently by using a new approach: each weight parameter is varied independently in a GA process according to the number of designated points of individuals; and some chromosomes with many designated points are added to an initial population generated at random. This paper also verifies its validity by several experiments. |
キーワード(和) | 遺伝的アルゴリズム / 経路探索 / 経由点 |
キーワード(英) | genetic algorithm / routing / designated points |
資料番号 | DSP2000-74,SST2000-33 |
発行日 |
研究会情報 | |
研究会 | DSP |
---|---|
開催期間 | 2000/7/17(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | Digital Signal Processing (DSP) |
---|---|
本文の言語 | JPN |
タイトル(和) | DSP2000-74 / SST2000-33 GA経路探索における収束速度の改善に関する考察 |
サブタイトル(和) | |
タイトル(英) | A Note on Convergence of a Genetic Algorithm for Routing Application |
サブタイトル(和) | |
キーワード(1)(和/英) | 遺伝的アルゴリズム / genetic algorithm |
キーワード(2)(和/英) | 経路探索 / routing |
キーワード(3)(和/英) | 経由点 / designated points |
第 1 著者 氏名(和/英) | 稲垣 潤 / Jun Inagaki |
第 1 著者 所属(和/英) | 北海道大学工学研究科 Faculty of Engineering, Hokkaido University |
第 2 著者 氏名(和/英) | 長谷山 美紀 / Miki Haseyama |
第 2 著者 所属(和/英) | 北海道大学工学研究科 Faculty of Engineering, Hokkaido University |
第 3 著者 氏名(和/英) | 北島 秀夫 / Hideo Kitajima |
第 3 著者 所属(和/英) | 北海道大学工学研究科 Faculty of Engineering, Hokkaido University |
発表年月日 | 2000/7/17 |
資料番号 | DSP2000-74,SST2000-33 |
巻番号(vol) | vol.100 |
号番号(no) | 209 |
ページ範囲 | pp.- |
ページ数 | 6 |
発行日 |