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