遺伝的アルゴリズムの簡単な紹介

Transcript

1. 遺伝的アルゴリズムの
   簡単な紹介
   板倉健太（農学博士）
   

   View Slide

2. はじめに: ナップザック問題
   2
    容量30Lのナップザックが1つと、各々の値段がPi
   、容積がVi
   であるn個の品物があ
   る。30Lを超えない範囲でいくつかの品物をナップザックに詰め、入れた品物の値
   段の合計値を最大化するにはどの品物を選べばよいか？
   画像出典：第２回 数理最適化とは②
   https://www.chuo-computer.co.jp/archives/10581
   

   View Slide

3. 遺伝的アルゴリズムについて
   3
    生物は，交叉，突然変異，淘汰を繰り返しながら，環境に適合するように進化
   画像出典：同志社大学理工学部知的システムデザイン研究室
   https://se.doshisha.ac.jp/education/laboratory/information/intelligent_system_de
   sign.html
   進化の仕組みをアイデアにして、最適化を行うことはできないか
   

   View Slide

4. 遺伝的アルゴリズムについて
   4
    遺伝的アルゴリズムのイメージ：
   個体（サンプル）の交配や自然淘汰、突然変異などを通して、最適な組み合わせ
   やサンプルを得る
   第一世代 第二世代
   明るい色： 強
   交配
   突然変異
   

   View Slide

5. 遺伝的アルゴリズムの簡単な例
   5
   A, B, C, D…など親をたくさん用意する
   親 B
   親 A
   親 C
   親 D
   ・
   ・
   ・
   交配
   ランダムな場所で
   遺伝子をかけあわせ
   スコア（ここでは配列の合計）の高い個
   体を中心にかけ合わせていく
   自然と強い個体（ここでは配列の合計が
   高いもの）が残っていくはず…
   1 0 1 0 1 0 0
   0 1 0 0 1 1 0
   1 0 0 0 1 1 0
   1 0 0 0 1 1 0
   0 1 0 0 1 1 0
    [1 0 0 1 0 0 0]などのランダムな0 or 1の配列から[1 1 1 1 1 1 1]を作る
   

   View Slide

6. ナップザック問題に沿った簡単な例
   6
   画像出典：第２回 数理最適化とは②
   https://www.chuo-computer.co.jp/archives/10581
   150円 200円 80円 120円 110円 160円
   1 1 1 1 1 1
   1L 1.2L 0.3L 0.2L 0.3L 0.4L
   体積3.4Lで820円
   買う個数
    決められた体積と価格のもと、一定の体積の袋で得をするような詰め方をする
    [キャベツ かぼちゃ 玉ねぎ トマト ナス リンゴ] の配列の中身を最適化させていく
   前ページの課題を解くコードを簡単に実装してみた
   

   View Slide

7. 遺伝的アルゴリズムを簡単に実装してみた結果
   7
   画像出典：第２回 数理最適化とは②
   https://www.chuo-computer.co.jp/archives/10581
    結果：次第に増加するものの最大値100には届かない
    「突然変異」のオプションを加えない場合
   50
   60
   70
   80
   90
   100
   0 200 400 600 800 1000
   スコア
   世代数
   最大値
   

   View Slide

8. 遺伝的アルゴリズムを簡単に実装してみた結果
   8
   画像出典：GMO INTERNET GROUP 遺伝的アルゴリズムで遊んでみる
   https://recruit.gmo.jp/engineer/jisedai/blog/genetic_algorithm/
    シンプルな複製や交叉といった操作に加え、突然変異を実装
   繰り返し、以下のように世代の作成を行い、一定の回数を繰り返す
   

   View Slide

9. 遺伝的アルゴリズムを簡単に実装してみた結果
   9
    「突然変異」をさせることで、最適な値に収束した
   50
   60
   70
   80
   90
   100
   0 200 400 600 800 1000
   スコア
   世代数
   突然変異なし 突然変異あり
   最大値
   

   View Slide

10. まとめ
    10
     遺伝的アルゴリズムについて簡単に紹介しました
     遺伝的アルゴリズムはロケットや新幹線の設計などにも使われているそうです
    画像出典：名古屋大学古橋研究室HP
    https://xn--nuee-9e6f200sf8wb.nagoya-u.ac.jp/labs/furuhasilab/ga.php
     機械学習などで重要な変数選択にも利用することができます
    

    View Slide

11. 参考ページ
    11
     ものづくりの集大成、 N700系が走る! - 三重大学
    https://www.mie-u.ac.jp/about/pr/item/vol010_9_10.pdf
     遺伝的アルゴリズムはロケットや新幹線の設計などにも使われているそうです
    

    View Slide