【アルゴリズム】遺伝的 アルゴリズム について

水曜日, 10月 17, 2012
【Curious Vehicle 第12回 勉強会ネタ】

『遺伝的アルゴリズムについて』

みなさま初めまして。makino です。

それでは今回のネタですが、『アルゴリズム』として『遺伝的アルゴリズム』を取り扱います。

そうアルゴリズム!魅惑の響きですね。最近まったくそういった響きとは離れた作業ばかりしていますが、面白い技術を広く書き連ねていきたいと思ってます!

【解説】遺伝的アルゴリズムについて

  • 遺伝的アルゴリズムは、生物の進化をプログラムで表現するAIアルゴリズムの1種です
  • 生物の進化は世代交代を繰り返すごとに染色体の情報をクロスオーバし、環境などに適用するよう常に進化します
  • この動きをアルゴリズムとして表現したものが遺伝的アルゴリズムとなります

遺伝的アルゴリズム 001

  • ある一定の確率で突然変異を発生させるアルゴリズムも必要です
  • 突然変異の必要性は後半にあるサンプルを確認してみてください

遺伝的アルゴリズム 001

  • アルゴリズムフローは 以下の2~3を繰り返し進化を行います

遺伝的アルゴリズム 001

    1. 第1世代の作成 (初期化)
    2. 適応性の評価
    3. エリートの選択
    4. 進化 (新世代の作成)
  • 世代交代を繰り返すことで徐々に徐々にこちらが求める水準まで各ゲノムが進化していきます!

【サンプル】 遺伝的アルゴリズムサンプル

  • では非常に見ずらく申し訳ないのですがSampleでもご覧ください
  • このサンプルは、以下の表にある条件で繰り返し実行します
  • サンプルなので、各染色体の値が1となる(合計50となる)ゲノムが優秀として評価する単純な評価で進めます

遺伝的アルゴリズム sample 004

1. 第1世代作成 (初期化)

    • 初期化として、第1世代となるゲノム因子をランダムにて作成します
    • 適応値についても20前後の低い値のゲノムが揃っています

遺伝的アルゴリズム sample 001

2. いきなりですが、80世代目まで経過しました

    • 適応性も 20前後だったのが、40台まで成長しています
    • ココで注目していただきたいのは、赤でくくられた 全世代が “0” の の染色体があります
    • 通常のクロスオーバでは、この染色体はいつまでたっても、“0” のままですが ...。

遺伝的アルゴリズム sample 001

3. またまた飛びますが 100世代目

    • 親が “0” の因子しかもっていなかった要素に “1” を持つゲノムが発生しています
    • 突然変異(1%) により、絶対生まれてこない条件で必要な”1″の因子が発生しているのがわかります
    • 今回では約 100世代 目で 必要な 50の適正値を持つゲノムが発生しました

遺伝的アルゴリズム sample 003

【まとめ】 遺伝的アルゴリズムとは

  • 統計アルゴリズムではありますが、AI的なアルゴリズム
  • 問題の予測が難しい場合 などに有用 (サンプルは単純すぎますが...。)
  • EC系でも、ロングテイルではなく優良顧客に特化した情報パターンを検出したい場合などに有用
  • ゲノムごとに分散が可能なので、MapReduceなどとも相性がよさそうです
こんなところで今回はまとめとさせていただきます!!

コメントを残す

CAPTCHA