Category: アルゴリズム

モチベーション 以前子供たちと一緒にめんぼうで遺伝的アルゴリズムを実装しました。その内容をPythonプログラムとして実装することでより一層理解を深めたいと思い始めました。 そもそも遺伝的アルゴリズムとは？ 以下の書籍が非常に参考となります。今回の実装もこちらに基づいております。 ソースコード 実際の実装は以下リンク先から参照してください。 サンプルコード 3つの3択問題についての解答を試行するGAになります。 設計コンセプト 遺伝的アルゴリズムは大まかに以下の4つの処理を繰り返していきます。 以下に各処理に関連するメソッドを載せておきます。 解候補の生成 generateでは単一の候補が決められた範囲内（range_ans）からint型の解を生成します。次にgen_populationでは解候補を指定数生成して各候補ごとにgenerateで解を生成します。 各解候補の評価 各候補の解と生成した解を比較して候補ごとの評価を下します。 優秀な解候補の選別 evaluateを使って候補ごとにスコアが出たので次の世代に残したい候補数（num_survive）を上位から順に確保しておきます。 新規解候補の生成（交叉・変異） 交叉と変異の実装です。簡易的なものなのでここは工夫のしがいがあります。今後の伸び代としてとっておきます。 最後に 実は以前にの簡単なGAの実装に試みたことがあったのですがうまくいきませんでした。前回との違いはアソビワークショップで綿棒実装したことでかなり理解が深まっていたものと思います。今後の課題としては適用可能な問題が整数型の選択問題に限ったものなのでその適用範囲を広げるといった試みは必要かと思います。 そういえば変異を実装せずに一度サンプルスクリプトを動かしてみるとなかなか解が収束しない状況に陥りました。やはり候補の多様性というのが遺伝子の生き残りにおいては重要な要素なのだと改めて実感した次第です。