進化的アルゴリズム

生命の進化を模倣した最適化手法

良い解同士を掛け合わせればより良い解が生成されるという考え

選択→交叉→突然変異→淘汰(世代交代)の手順を踏む

選択

個体群の中から良い解を選ぶ操作

エリート選択

適合度が高い順に次の世代に残す個体を選ぶ方法

収束が速い

一方局所解に陥りやすい

ルーレット選択

適合度ごとに確率を設定し、確率的に選ぶ方法

適合度が低いものが選択される可能性もある

局所解に陥りにくい

トーナメント選択

個体群の中から一定数の個体を抜き出して、適合度を基準にトーナメントを行い選択する方法

局所解に陥りにくい

収束が遅い

交叉

新しい組み合わせを作る

遺伝子的な役割としてバイナリ型や文字列、実数等がある

突然変異

遺伝子的なものを変化させる

淘汰(世代交代)

生物同様、弱い個体(適合度が低い個体)は淘汰される

親グループと子グループを合併させて与えられた条件に応じて上位個体のみを残し、それ以外のものを削除する

関連記事