J 狩野 均 ; kanoh@cs.TAJ (TAJ=tsukuba.ac.jp)
J 研究室 3C211 http://www.kslab.cs.tsukuba.ac.jp/
J 秋学期
J 進化的アルゴリズムとは、生物の進化をヒントにした問題解決アルゴリズムです。プログラムで細かいところまで書かなくても、対象問題に合わせて自動的に進化して問題を解決します。代表的な応用例として、カーナビの経路探索、室内設備のレイアウト、プリント基板のＬＳＩのレイアウト、自動車エンジンルームの部品配置、仕事のスケジュ―リング、人員配置、旅行のプランニングなどが挙げられます。
J 本実験では制約充足問題と組み合わせ最適化問題を対象として、代表的な進化的アルゴリズムを系統的に学習します。これらの問題は、問題の規模が小さければすべての組合せを試して、制約条件を満たす最適解を求めれば解決できますが、組合せの数が１０の３０乗を越えると、縦型探索などの通常のアルゴリズムで解くことは難しくなってきます。そのため、大規模な実用問題では、進化的アルゴリズムなどの近似解法が用いられています。
J 実験内容としては、地図の色塗り問題と巡回セールスマン問題を対象として、以下のプログラムを作成し、比較・考察します。
・ 山登り法（Hill Climbing: HC）
・ 進化戦略（Evolution Strategy: ES）
・ 遺伝的アルゴリズム（Genetic Algorithm: GA）
・ ハイブリッド遺伝的アルゴリズム（Hybrid GA）
・ アントコロニー最適化法（Ant Colony Optimization: ACO）
・ ハイブリッドアントコロニー最適化法（Hybrid ACO）
J 知識処理概論（春AB学期）
J 北野宏明 編、遺伝的アルゴリズム、産業図書
J
川村他, 生命複雑系からの計算パラダイム, 森北出版