最適化と遺伝的アルゴリズム

最適化と遺伝的アルゴリズム

とはある条件のもとである関数を最大にする解を求めること。

最適化問題で考えうるすべての解の組み合わせを試し

必ず最も良い解を得ることができるが

計算負荷が大きく大規模な最適化問題に適応。

生物はそれぞれの答えが自然淘汰されながら交差、突然変異を繰り返すことで、種全体の遺伝子がより環境に適応するよう進化しています。

遺伝的アルゴリズムではこの仕組みに倣い、目的関数を環境への適応度、求める解を遺伝子とみなし、何世代にもわたって選択、交叉、突然変異処理を繰り返すことによってその最適化問題における最も良い解を探す。

1. 初期世代の生成

最初の世代のみで行う。最初の世代では親がいないため、制約条件に合うよう遺伝子をランダムで決定して個体を生成する

2. 個体の評価

その世代のすべてのことに対して評価を行う。各個体の遺伝子を目的完遂入力して計算を行い、その結果を評価値として記録する

3. 自然淘汰

個体の評価値をもとに、黄砂行って次の世代に遺伝子を残す個体を選り分ける。この処理で全個体の遺伝子がより優れた方向へ変化していくことになる。生物の交配において優秀な答えだけが遺伝子を残すわけでは無いように遺伝的アルゴリズムでも評価値の高い順に選択するのではなく、ランダム要素を入れた手法で答えを選択する。手法としてルーレット選択、ランキング選択、トーナメント選択がある

4. 交叉

選り分けられた個体同士の遺伝子を掛け合わせ新たな遺伝子の個体を生成します。この処理によって優れた個体の遺伝子の良い部分同士を掛け合わせることができより良い遺伝子を生成することができる。1点交叉、多点交叉、一様交叉がある。

5. 突然変異

その世界のすべてのことに対して一定の確率で遺伝子一部をランダムに変更する