フクロウ・ノート（１３）遺伝的アルゴリズム１

ミネルバ大学修士課程の1−2学期は2クラス履修します。一つはEmpirical Analysis（実証分析）といって解きたい問題に対して科学的手法を適用したり仮説検証や推論を導くもの（これまでのnote記事はこの授業から）です。そしてもう一つはFormal Analysis(形式分析）といって論理・合理的思考や統計、計算的思考やR言語を使った具体的な分析技法を学んでいます。

2学期目のFormal Analysisの授業は、相関とは何か、そしてどのようにR言語を使って計算・分析するのかから始まり、線形回帰モデルの基礎とR言語を使った具体的な計算・分析、ディープラーニングの概念的な基礎を学んできました。この1−2週間は「最適化問題」について議論をしていて昨日はその仕上げの日でした。来週からはシミュレーション技法を学ぶことになります。

授業で習った遺伝的アルゴリズムがあまりピンと来なかったので復習として追加で調べて書くことにしました。

最適化問題（Optimization Problem）ってなに？

最適化問題とは、与えられた制約条件の中で指定した目的関数を最大または最小にする値を求めることです。下に貼り付けたAlphaOpt. (2017).の短い動画が予習教材の中にあって解りやすかったです。動画の中で実例が紹介されていて、許容できるリスクの範囲の中で最大のリターンを得られる株式ポートフォリオとは、ギリギリ必要な強度を保ちながら最軽量の機体を設計するには、より多くの消費者に最短時間で商品を届けるためにどこに在庫を置く倉庫を建てるのかなど身近なところで使われていることがわかります。新幹線のN700系の顔の部分を決めるときに、騒音と振動を抑えながら東京〜新大阪駅間の所要時間を5分短くする設計をするにはどうしたら良いか分析する際にも使われたらしいです。

遺伝的アルゴリズム(Genetic Algorithm)とは？

遺伝的アルゴリズムは人工知能の一種です。変数の多いより複雑な問題に対する「大体こんな感じ」という解を比較的短時間で出せることが長所で様々な分野で使われています。一方、真の解を求めることは保証できないのが短所です。その短所をたくさんシミュレーションを繰り返すことで最小化しています。先ほど事例として出した株式・航空機・新幹線・倉庫の場所の事例はいずれも遺伝的アルゴリズムを使うのに適した問題です。

遺伝的アルゴリズムはダーウィンの進化論をはじめとした生物の進化の原理をヒントに作られた最適化のための探索型アルゴリズムです。生物の進化では自然淘汰によって「優秀な個体」の遺伝子が次世代にも引継がれます。遺伝的アルゴリズムでは「優秀な個体」＝「より最適化された答え」を求めることが目的になります。

遺伝的アルゴリズムの主要な概念は、選択（Selection）・交差/繁殖(Crossover)・変異(Mutation）です。Selectionとは親となるペアが決まり自然淘汰が起きること、Crossoverとは子が生まれ遺伝子が引き継がれること、そしてMutationとは突然変異が起きてより優秀な個体ができる場合があることです。で、これらが繰り返されることで、より環境に適合した種が残り世代交代していくのと同じように、より最適化された答えが出せるようにアルゴリズムが進化していきます。

では具体的にどのような手順を踏んでいくのか、次にこの授業について書く時に説明をしてみようと思います。

引用

AlphaOpt. (2017). Introduction to optimization: what is optimization?
Retrieved from https://www.youtube.com/watch?v=Q2dewZweAtU