1 0 0 0 OA GAにおけるビルディング・ブロックの進化評価と遺伝的操作の役割
GAがランダムな確率的探索と区別されるのは、操作論的には交叉や突然変異といった遣伝的操作と、理論的には染色体の優秀な断片の結合と成長が進化の主役であるとするビルディング・ブロック仮説である。しかし、GAの数学的基礎はまだほとんど確立していないため、ビルディング・ブロックそのものをどのように表現するか、その形成と成長が世代とともにどのように進化していくのか、よくわかっていないのが現状である。本研究では、ナップザック問題を対象に、世代を通じて伝えられる遺伝情報がどのように存在するか、また遺伝的操作が進化の過程においてどんな役割を果しているかを検討する。
1 0 0 0 最適配線経路選定問題に対する階層型遺伝的アルゴリズムの構成
- 著者
- 馬 〓 飯田 一弘 謝 孟春 西野 順二 小高 知宏 小倉 久和
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会論文誌. D-I, 情報・システム, I-情報処理 (ISSN:09151915)
- 巻号頁・発行日
- vol.85, no.1, pp.21-30, 2002-01-01
多数本のケーブルを最適に配線する最適配線経路選定問題に対する遺伝的アルゴリズム(GA)の構成法を提案する.配線経路に制約のない場合は, 個々のケーブルの最適経路を有限離散グラフにおけるダイクストラ法により得ればよい.しかし配線経路に容量の制約をもつ場合はダイクストラ法では最適化できない.提案するGAは, 2階層からなる染色体コーディングを採用した2階層GAである.各ケーブルの経路とケーブル経路の組合せとをそれぞれの階層とし, それぞれの階層における遺伝的操作によって全体として配線経路選定の最適化を図る.前者の階層における遺伝的操作として, ブロック交叉とブロック突然変異を導入した.また, 後者の階層で生成される制約条件を満たさない致死遺伝子を利用する手法も工夫した.コンピュータシミュレーションにより, これらの遺伝的操作をもつ2階層GAが, 経路探索問題に対して有効に働くことを確認した.