著者

馬 〓 飯田 一弘 謝 孟春 西野 順二 小高 知宏 小倉 久和

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-情報処理 (ISSN:09151915)

巻号頁・発行日

vol.85, no.1, pp.21-30, 2002-01-01

---

多数本のケーブルを最適に配線する最適配線経路選定問題に対する遺伝的アルゴリズム(GA)の構成法を提案する.配線経路に制約のない場合は, 個々のケーブルの最適経路を有限離散グラフにおけるダイクストラ法により得ればよい.しかし配線経路に容量の制約をもつ場合はダイクストラ法では最適化できない.提案するGAは, 2階層からなる染色体コーディングを採用した2階層GAである.各ケーブルの経路とケーブル経路の組合せとをそれぞれの階層とし, それぞれの階層における遺伝的操作によって全体として配線経路選定の最適化を図る.前者の階層における遺伝的操作として, ブロック交叉とブロック突然変異を導入した.また, 後者の階層で生成される制約条件を満たさない致死遺伝子を利用する手法も工夫した.コンピュータシミュレーションにより, これらの遺伝的操作をもつ2階層GAが, 経路探索問題に対して有効に働くことを確認した.