![事例１：関数の最大値探索
設問：下記の関数の区間[0,1]における最大値を求めたい
f (x) ＝ 2 sin(29x －1) ＋ 5 sin(1 － 8 x) ＋ 3 sin(1－70 x)](https://image.slidesharecdn.com/geneticalgorithmfullscratchwithr-180826104320/85/Genetic-algorithm-full-scratch-with-R-30-320.jpg)
![事例１：関数の最大値探索
実行結果
設問： 下記の関数の区間[0,1]における最大値を求めたい](https://image.slidesharecdn.com/geneticalgorithmfullscratchwithr-180826104320/85/Genetic-algorithm-full-scratch-with-R-45-320.jpg)
More Related Content
What's hot (20)
More from Satoshi Kato (14)
Genetic algorithm full scratch with R
- 1. Rを使って 0から始める遺伝的アルゴリズム 第72回R勉強会＠東京（#TokyoR） Topic ? 遺伝的アルゴリズム（概要） ? 事例１：関数の最大値探索 ? 事例２：巡回セールスマン問題 Full scratch implementations of genetic algorithm using R
- 2. @kato_kohaku ? 遊牧＠モンゴル → 臨床検査事業の研究所 ? 生態学／環境科学 → 医療情報学／疫学 1cm 誰？
- 3. ※ 勝手に宣伝 著者： 大谷 紀子 著 定価： 2,916円 （本体2,700円＋税） 判型： A5 頁 ：196頁 ISBN：978-4-274-22238-2 発売日：2018/06/06 発行元：オーム社 目次 ? まえがき ? 第1章 最適化問題と進化計算アルゴリズム ? 第2章 遺伝的アルゴリズム ? 第3章 アントコロニー最適化 ? 第4章 人工蜂コロニーアルゴリズム ? 第5章 粒子群最適化 ? 第6章 ホタルアルゴリズム ? 第7章 コウモリアルゴリズム ? 第8章 カッコウ探索 ? 第9章 ハーモニーサーチ ? 索引 http://shop.ohmsha.co.jp/shopdetail/000000005724/
- 4. 概要 遺伝的アルゴリズム Genetic Algorithm (GA) ? 最適解を探索するアルゴリズム ? 生物の進化メカニズムを模倣する ? 環境に適応できる個体ほど、次世代に自分の遺伝子を残せる ? 2個体の交配（交叉）により子を作る ? ときどき突然変異が起こる ? https://ja.wikipedia.org/wiki/遺伝的アルゴリズム ? 大谷紀子 『進化計算アルゴリズム入門』
- 5. 概要 基本用語集
- 6. 1 0 0 1 0 1 1 1１0 初期個体群の生成 個体群の適応度評価 240 190 170 120 80 80 各世代のすぐれた個体は 次世代に持ち越す 選択（淘汰） 交叉 （親個体間の遺伝子交換） 突然変異 毎世代のサイクル 遺伝子の適応度順に 次世代候補を選択する 設定した条件で打ち切り ① ランダムな初期個体群を生成する ② 進化的な操作によって各個体の適応度を上げるように探索 ③ 最終世代のなかで最良個体（群）を得る 遺伝的アルゴリズム 最も適応度の良い 個体を探す 進化的操作の例 アルゴリズムの流れ
- 7. Agenda ? 問題の理解と表現 ? 設問に応じた遺伝的アルゴリズムの設計 ? 実装?実行?評価 ? 事例１：関数の最大値探索 ? 事例２：巡回セールスマン問題
- 8. Agenda ? 問題の理解と表現 ? Why 遺伝的アルゴリズム？ ? 設問に応じた遺伝的アルゴリズムの設計 ? 実装?実行?評価
- 9. 遺伝的アルゴリズムの設計と実装 問題の理解と表現 ? そのタスク、GAじゃなきゃダメですか？ ? 総当たりじゃダメですか、ベイズ最适化のほうが良くありませんか ? だいたい3番目くらいにベターなアルゴリズム、だそうです要出典 ? メリット ? 挙動が可愛い ? 基本的な考え方はシンプル＆直感的で、実装が（比較的）楽 ? 遺伝子表現の工夫次第で、さまざまな問題に適用できる ? ローコストハイリターンな並列化 ? デメリット ? 厳密な最適解は保証しない ? 一試行あたりのコストが超高価な問題の探索には不向き
- 10. 問題の表現 － 「適応度」の評価 「適応度」の例 ? スタート地点から進んだ距離を最大化する ? with NeuroEvolution of Augmenting Topologies (NEAT) MarI/O - Machine Learning for Video Games (4:58 / 5:57) MarI/O is a program made of neural networks and genetic algorithms that kicks butt at Super Mario World. ? https://www.youtube.com/watch?v=qv6UVOQ0F44
- 11. （参考）多目的最適化 と 遺伝的アルゴリズム ? 複数の適応度を同時に考慮しながら最適化を行う問題を多目的最適化問題という。 ? この種の問題では、各目的間にはトレードオフの関係があることが多く、そうした場合に、 パレート最適解の集合をGAで一度に求めるアプローチを多目的 GA という ? https://en.wikipedia.org/wiki/Multi-objective_optimization ? http://www.mis.doshisha.ac.jp/text/moga20090221.pdf ? /kato_kohaku/non-dominnt-sortandparetofrontwithrpref 問題の表現 － 「適応度」が複数ある場合
- 12. ワークフロー ? 問題の理解と表現 ? 設問に応じた遺伝的アルゴリズムの設計 ? 評価関数 ? 問題の表現 － 「適応度」の評価 ? 解候補のエンコード ? 解の遺伝子型表現→表現型→適応度 ? 遺伝的操作の設計 ? 交叉 ? 突然変異 ? 選択（淘汰）の方法 ? 実装?実行?評価
- 13. 解の遺伝子表現 エンコーディング ? また、可変長の遺伝子型を考える問題も存在する ? バイナリエンコーディング ? 10進数→2進数や、組合せの探索などを あり（１）?なし（０）で表現する ? 数値型エンコーディング ? 解と関係する数字?対応番号の配列を 表現する ? ニューラルネットの最適な荷重の探索 ? 巡回セールスマン問題のような最適な 順序
- 15. 遺伝的操作 による解群の更新 ? 遺伝子型の多様性を得たい ? 未探索の領域にジャンプ（局所解から脱出）するための仕組み ? 交叉（組み換え） ? ２つの遺伝子配列の一部を交換して、新しい遺伝子型を作る ? 突然変異 ? １つの遺伝子配列の一部を、一定の確率で別の値に置き換えて、 新しい遺伝子型を作る ? 確率が低すぎると局所解に陥りやすくなり、高すぎるとランダム 探索に近づく
- 17. 遺伝的操作による解群の更新 － 交叉 順序交叉 親１と親2の順序パターンをなるべく 保存しつつ、重複を避けて交換する 順序交叉の例 ① 交叉点の選択： 親１の染色体から（5,6）を残す ② 子１の置き換え箇所から見た 親２の遺伝子型は （4,2,1,6,5,3） ③ 子１の遺伝子と重複しているものを削除して （4,2,1,3） ④ 子１の置き換え箇所に③を当てはめる ① ④ ② ③
- 20. 余談 遺伝的プログラミング ? 遺伝子型の表現に木構造を使う ? 関数の同定問題やニューラルネットワークや電子回路の設計、あるいはロボットの制御プ ログラミングの作成などに応用できる 関数の同定問題における交叉の例 ? https://ja.wikipedia.org/wiki/遺伝的プログラミング 3 × ((x × 4) + x) (3 + x) - (2/(x × x)) 3 × (x × x) (3 + x) - (2/(x × 4) + x)
- 26. 1 0 0 1 0 1 1 1１0 初期個体群の生成 個体群の適応度評価 240 190 170 120 80 80 各世代のすぐれた個体は 次世代に持ち越す 選択（淘汰） 交叉 （親個体間の遺伝子交換） 突然変異 毎世代のサイクル 遺伝子の適応度順に 次世代候補を選択する 設定した条件で打ち切り ① ランダムな初期個体群を生成する ② 進化的な操作によって各個体の適応度を上げるように探索 ③ 最終世代のなかで最良個体（群）を得る 遺伝的アルゴリズム 最も適応度の良い 個体を探す 進化的操作の例 （再掲） アルゴリズムの流れ
- 27. 遺伝的アルゴリズム アルゴリズムの流れ 終了 判定 ランダムな初期個体群の生成 世代の更新 ? エリート保存 ? 選択 ? 交叉 ? 突然変異 最終世代の最良解の出力 NO YES
- 28. Agenda ? 問題の理解と表現 ? 設問に応じた遺伝的アルゴリズムの設計 ? 実装?実行?評価 ? 事例１：関数の最大値探索 ? https://github.com/katokohaku/evolutional_comptutation/blob/master/chap2.1.Rmd ? 事例２：巡回セールスマン問題 ? https://github.com/katokohaku/evolutional_comptutation/blob/master/chap2.2.Rmd
- 29. 事例１：関数の最大値探索 ? 設問：与えられた区間内で関数f(x)を最大にするｘを求めたい ? Why 遺伝的アルゴリズム？ ? 設問の理解と表現 ? 解候補のエンコード ? 評価関数（適応度） ? 交叉の設計 ? 突然変異の設計 ? 実行結果
- 30. 事例１：関数の最大値探索 設問：下記の関数の区間[0,1]における最大値を求めたい f (x) ＝ 2 sin(29x －1) ＋ 5 sin(1 － 8 x) ＋ 3 sin(1－70 x)
- 31. 事例１：関数の最大値探索 不要 例えば、10-7の精度でも1000万回。 総当たりでよいのでは？ 目的関数の計算コストが大きいと？ ? 1セットのパラメータの評価に1秒かかる 機械学習だと、 107パターンの総当たり 探索をした場合、115日以上 必要 ? そういう事例だと思ってすすめましょう 1.6秒 Why 遺伝的アルゴリズム？
- 32. 事例１：関数の最大値探索 設問の理解と表現 適応度関数f(x)の入力となる、0~1の実数 x を 遺伝子型で表現する 最大値は sum(20:5)=63
- 33. 事例１：関数の最大値探索 応用 機械学習の変数選択 → あり?なしの組み合わせを遺伝子型で表現する mlr::makeFeatSelControlGA() ? https://mlr-org.github.io/mlr/articles/feature_selection.html#wrapper-methods
- 42. 遺伝的アルゴリズム アルゴリズムの流れ 終了 判定 ランダムな初期個体群の生成 世代の更新 ? エリート保存あり ? 選択=トーナメント方式 ? 交叉＝1点交叉 ? 突然変異＝ビット反転 最終世代の最良解の出力 NO YES
- 43. 事例１：関数の最大値探索 － アルゴリズムの流れ 初期個体群（第一世代）の生成 遺伝子パターン生成 → 表現型 → 適応度
- 46. 事例１：関数の最大値探索 （備考）結果のアニメーション {animation}パッケージは、 Imagemagickでアニメーション生成してくれる。 別途ImageMagick のインストールが必要 ? https://www.imagemagick.org/script/index.php
- 47. 事例２：巡回セールスマン問題 ? 設問：与えられたノードをすべて通る最短経路を求めたい ? Why 遺伝的アルゴリズム？ ? 設問の理解と表現 ? 解候補のエンコード ? 評価関数（適応度） ? 交叉の設計 ? 突然変異の設計 ? 実行結果
- 48. 事例２：巡回セールスマン問題 設問：与えられたノードをすべて通る最短経路を求めたい START 巡回セールスマン問題（Travelling Salesman Problem; TSP) セールスマンがいくつかの都市を1度ずつすべて訪問して出発点に戻ってくるときに、 移動距離が最小になる経路」を求める、組合わせ最適化の有名なトイプロブレム 都市の数:25
- 49. 事例２：巡回セールスマン問題 Why 遺伝的アルゴリズム？ 組み合わせ爆発 ? 都市の数:10 ? ＞3.6×106通り ? 都市の数:20 ? ＞2.4×1018通り ? 都市の数:30 ? ＞2.7×1032通り START 都市の数:25
- 50. 事例２：巡回セールスマン問題 設問の理解と表現 移動経路 の 総移動距離 ＝ 適応度
- 54. 事例２：巡回セールスマン問題 解候補のデコード 移動経路 の 総移動距離 が 適応度 表現型 適応度
- 55. 事例２：巡回セールスマン問題 － 交叉 順序交叉を改変 ? スタート地点を固定する ? 親１と親2の順序パターンをなるべく保存しつ つ交換する 順序交叉の例 ① 交叉点の選択： 親１の遺伝子から（5,6）を 残す ② 子１の置き換え箇所から見た、親２の遺伝子 は（4,2,1,6,5,3） ③ 子１の遺伝子と重複しているものを削除して （4,2,1,3） ④ 子１の置き換え箇所に③を当てはめる （4,2,1,3,5,6 ） ⑤ スタートが1になるように回転ソート （1,3,5,6,4,2） 交叉の設計 ⑤
- 56. 事例２：巡回セールスマン問題 － 交叉 ① ② ③ ④ ０ 切り出し位置を選択する：4~5 ① 交叉点の選択： 親１の遺伝子から選択範囲を 残す(,,,8,5,,,,,) ② 子１の置き換え箇所から見た、親２の遺伝子 は（ 2,8,5,7,6,1,3,10,4,9 ） ③ 子１の遺伝子と重複しているものを削除して （ 2,,,7,6,1,3,10,4,9 ） ④ 子１の置き換え箇所に③を当てはめる （ 2,7,6,8,5,1,3,10,4,9 ） ⑤ スタートが1になるように回転ソート （1,3,10,4,9,2,7,6,8,5） ０ ⑤
- 57. 事例２：巡回セールスマン問題 － 交叉 ① ② ③ ④ ０ 交叉点の選択：切り出し位置を選択する ① 親１の遺伝子から選択範囲を残す ② 子１から見た、親２の遺伝子の順序から、 ③ 子１の遺伝子と重複しているものを削除して、 ④ 子１の置き換え箇所に③を当てはめる ⑤ スタートが1になるように回転ソート ０ ⑤
- 60. 事例２：巡回セールスマン問題 選択（淘汰）の方法 ルーレット選択を採用する ? 適応度 → ルーレット占有率（→閾値）
- 63. 遺伝的アルゴリズム アルゴリズムの流れ 終了 判定 ランダムな初期個体群の生成 世代の更新 ? エリート保存あり ? 選択＝ルーレット方式 ? 交叉＝順序交叉 ? 突然変異＝入換え 最終世代の最良解の出力 NO YES