遺伝的アルゴリズムをExcelに実装して最小値問題を解いてみた。前へ次へ検索RSSFeedlyホーム>Excelで機械学習>Excelで試してみる遺伝的アルゴリズムをExcelに実装して最小値問題を解いてみた。Udemyの関連講座リンクリンク遺伝的アルゴリズムは交配や突然変異させながら最適値を探すコンピュータで数値問題を解かせる処理方法をアルゴリズムといいます。機械学習ではいろいろなアルゴリズムを使います。アルゴリズムにはある程度数学の知識が必要で難解なものもあれば、簡単なものもあります。勾配降下法はどちらかというと難解な部類に入るかな。【Excelでわかりやすく】勾配降下法で最小値が見つかる理由を視覚的に理解する遺伝的アルゴリズムは簡単な部類に入ります。微分積分や行列などの数学知識は不要です。管理人は以前メーカーに勤めていた時、隣に遺伝的アルゴリズムを生産工程に適用する研究をしてた人がいました。何かとても先進的なことをしているなと思っていたのですが、ある日やり方を聞いてみたらとても簡単で拍子抜けしたことを思い出します。遺伝的というと、遺伝子とかDNAとか難しそうな感じがしますが、遺伝的アルゴリズムでいう遺伝とは進化のことです。ダーウィンの進化論では生存競争と自然淘汰が進化の原動力であるとしていますね。良い遺伝子を持って生まれてきた種が生存競争で勝ち、負けた種は自然淘汰されます。コロナウィルスも同じで、たまたま突然変異してできたデルタ株だけが生き残り、他は自然淘汰されつつあります。これはウィルスが賢くて、人間の免疫を潜り抜けるように考えてカイゼンした結果ではありません。ランダムに起こる突然変異で「たまたま」環境に適応できた種がデルタ株だっただけのことです。遺伝的アルゴリズムの考え方も同じで、比較的良さそうな種をザックリ選んで、後はそれをランダムに交配させたり、ランダムに突然変異させたりして、もっと良い種ができたかどうかを判定します。後は、それを何回も繰り返して最強の種に育て上げるのです。初期値を複数テキトーに選ぶ面白そうだと思いませんか?実際にどのようにやるのかを、関数の最小値を求める問題で見てみましょう。次のような関数を想定します。グラフに描くと、このような複雑な形状になります。この関数の最小値は、グラフを見れば分かるように-50くらいで、その時のxの値は1くらいです。勾配降下法でもそうでしたが、まずは初期値を1点テキトーに決めて、アルゴリズムに則って動かしながらこれ以上動かない点(収束点)が見つかるまで繰り返します。違いは、遺伝的アルゴリズムでは初期値を複数点選ぶことです。しないと、交配できませんからね。二進法を使うあと、ここでもう一工夫します。xの値を二進法で表すのです。私たちが日頃使っている数字は十進法です。何気に使っているので意識はしませんが、1桁は0から9までで、それ以上は桁を一つ繰り上げます。二進法も同じで、1桁は0と1だけ、2を表したい時は桁を一つ繰り上げて10のように表します。1桁が0か1しか取れませんので、目まぐるしく桁が繰り上がります。3は11、4は100、5は101、6は110のようにどんどん桁が増えていきます。このように二進法で表すことにより、DNAを表す数字の羅列のようになり交配や突然変異がやり易いのです。初期値は何でも良いのですが、x=30、25、10、5としてみます。これを二進法で表すと、それぞれ11110、11001、01010、00101になります。優秀な種を選択するまずはこの中から比較的優秀そうな種を2つ選びましょう。優秀かどうかの判断は、それぞれのxに対応するf(x)の値で見ればよいでしょう。xが30の場合は、f(30)=302+30+50sin(5√30)=969同様に計算すると、f(25)=643、f(10)=105、f(5)=-19となります。f(x)の最小値を見つけたいので、x=10、5の2つが優秀な種になります。交配させる次にこの2つの種を交配させます。二進法で表すとx=01010、00101ですから、交配させたら5桁のうちの最初の3桁と最後の2桁の子供が生まれるとしましょう。これで最初の種11110、11001、01010、00101が01010、00101、01001、00110に置き換わりました。01010と00101は次世代では生き残れず淘汰されます。残酷ですが、これが自然の摂理です。変異させる次に残った4種の中で1種だけ突然変異が起きます。これはDNAの複製ミスでたまたま起こる出来事なので、どれに起こるかは全く予想がつきません。4つの中からランダムに選ぶことにします。これはExcel関数を使って=ROUNDUP(RAND()*4,0)のようにして選べば良いでしょう。エクセルを使って正規分布の【疑似乱数】を生成する方法を具体例で実演!ランダムに選んだ結果、00101が選ばれたとしましょう。この5つの数字の中の1つだけを、突然変異ということで逆の数字に変えます。0ならば1に、1ならば0に変えます。何番目の数字が変わるかも偶然起こる出来事なので、全く予想がつきません。これもエクセル関数で1から5の乱数を発生させます。エクセル関数からの乱数が3となった場合、3番目の数字は1ですので0に変えます。これにより、次の世代は01010、00001、01001、00110になります。これで第一世代から第三世代にまで進化しました。まとめると次のようになります。繰り返す第三世代の数字を十進法で表すと10、1、9、6になります。これらに対応するf(x)を計算するとf(10)=105、f(1)=-46、f(9)=123、f(6)=26になりますので、最初のステップに戻ってまた優秀な2つの種を選びます。この場合、関数値が小さいのはf(1)=-46とf(6)=26ですので、1と6が選択されます。いうように4つの数字のうち3つの数字が変わらなくなるまで繰り返します。3つかというと、4つの数字のうち1つは突然変異でいつも変わるからです。3つの数字が変わらなくなれば、収束したと見なすことができます。遺伝的アルゴリズムをExcelに実装するこのアルゴリズムをExcelに実装すると次のように書けます。クリックすると拡大しますこのシートで第一世代から第三代世代までが計算できます。あとは、第三世代の数字を第一世代にコピペして同じように繰り返します。第三世代の4つの関数値のうち3つが10回連続で変わらなければ収束したと見なして終了です。クリックすると拡大しますこの繰り返しと収束判定は、次のようなマクロを組むことでできます。クリックすると拡大します実際にマクロを実行してみると、次のように16回繰り返したところで収束しました。初期値をいろいろ変えてやってみても、早かれ遅かれ同じ値に収束します。変異のところで乱数を発生させているので、毎回違う突然変異が発生しますが、最終的には同じ値に収束します。これは、地球の歴史をもう一度始めからやり直したとしても、やはり私たち人間が支配しているだろうと言われることと同じです。途中の交配や突然変異は違うパターンになったとしても、それらはランダムに起こるため、何億世代も繰り返せば同じ結果に収束するのです。ちなみに遺伝的アルゴリズムでは交配というと生々しいので、交叉といいます。AI数学-文系でも理解できる!高校から始めるデータ分析、AIのための数学-データ分析、機械学習に関わる数学に絞り、効率的に学習できるようカリキュラムを構成しました。文系でも理解できるよう丁寧な説明をしています。Pythonエンジニア育成推進協会認定スクールによる高品質な数学コースです。–1000人以上が受講している(株)キカガクの『脱ブラックボックスセミナー』が遂に登場!機械学習の参考書を「閉じてしまった人」への再入門に最適な講座です。微分・線形代数といった数学の基礎からPythonでの実装まで短時間で習得しましょう。永遠の旅人よろしければシェアお願いしますTwitterFacebookLinkedInB!HatenaLINELINEExcelを使って遺伝的アルゴリズムで組み合わせ最適化問題を解いてみる。...Excelを使って遺伝的アルゴリズムで組み合わせ最適化問題を解いてみる。...ポアソン分布のパラメータλをExcelソルバーを使って最尤法で求めてみた。【区間推定の使い方】タイヤの摩耗を具体例にわかりやすく解説します。TOP28【作業分析6】MMCモデル|最適なトラックドック数をSimpyでシミュレーション【作業分析5】トラックの待機台数の多さを人の表情でアニメーション(2)カンボジアの物流でお困りのことがあればお気軽にご相談下さい。学生時代にアジアの雑踏にハマる。誰もが羨むメーカーを退職し「旅するように働く」ことを目指し物流業界に転職。理工学と経営学のダブル修士。2023年1月からカンボジアのオートレスビーチ在住。