テーマ6講義メモ

第13回

遺伝的アルゴリズム

進化をヒントにした最適化プログラム

環境に適応したものが残っていく

新幹線の先端の形状など

最適化問題の解決

決定したいものを決定変数、何を持ってよいとしたいのかを評価関数（目的関数）として数学的に表現する

最適化アルゴリズムの適用

勾配法（ニュートン法、再急降下法など）

傾きが正なら左へ傾きが負なら右方向へ

弱点

局所最適解（最小値ではなく、谷となっている別の極小値）になってしまいやすい

勾配が小さいと探索が進みにくい

評価関数の形がわかっていて、微分可能でないといけない

ヒューリスティクス

うまくいく保証はないが大体うまくいくことが経験的にうまくいくことがわかっている方法（発見的解法）

メタヒューリスティクス

より汎用的に対応できるヒューリスティクス

生物にヒントを得た手法が多い→自然界には「最適解」のアナロジーでとらえれる仕組みが多く存在

進化的アルゴリズム

生物の染色体にあたるものを決定変数を記号化したものを対応づけ

決定変数を二進数で表した０，１の数字列などを染色体として扱う

遺伝情報を世代ごとに変化させる→淘汰や交叉、逆位、突然変異

操作するかは確率的（乱数で）決定

利点

様々な可能性を並列に探れる

評価関数の勾配情報が必要ない

局所的解を抜け出しえる

つまりは総当たりなどの手法を変数の選び方をアレンジして、ステップ的なモノではなくありていに言えばランダムに選んで行くものと認識。評価が高いほど変数は生き残りやすくなるようにしている。

第14回

交叉確率、突然変異確率を高くしすぎても良い解もすぐ変化してしまい、最小値との差の平均が振動したような挙動になる。

突然変異→新たな探索範囲を開拓する(exploration)

交叉→得られた良い解の「知見」をうまく活用する(exploitation:活用)

局所解でも計算されたデータの平均値が最適解周辺に集まった計算結果よりも小さい場合、前者の計算結果の方が良い場合もある。

多目的最適化

パレート最適解

横軸、縦軸にそれぞれ別の目的関数の値としたとき、明らかにすべての目的関数での値が小さいことを優越という。

ほかのどの解にも優越されない解を、パレート最適解という。