遺伝的アルゴリズム

世の中にはさまざまな最適化が潜んでいます。より今よりも最適な状態が作れれば同じ目的を達成するのにもより効率的で資源をうまく使えます。

数理最適化 - 最適化問題のうち解が連続的なもの。 組合せ最適化 - 最適化問題のうち、解が離散的なもの。

https://ja.wikipedia.org/wiki/%E6%9C%80%E9%81%A9%E5%8C%96

数理最適化や組合せ最適化のように値が連続値もしくは離散値のものを最適化するのが主のようです。そのようなものを扱ってみたいと思います。

最適化は身の回りの様々な事象を数式の形に落とし込み、それらを最小化最大化することで組合せ最適化に落とし込み問題を解くことができます。

実際には数式が最小化された時に答えに到達するように数式が設計されており、その数式で最小値などを探すことで最適化を行います。

実際の身の回りでは例えば、時間や距離を最小化することで最適化でき、

・ルート・経路最適化 ・シフト・工程最適化

など各種最適化を使いこなすことで、様々な問題に適用ができます。最近では例えば配送などは最適化を行うほどに、配送時間などが効率化され、時間の有効活用やコストダウンに繋がります。最終的に同じ結果をもたらすにしても途中経過を最適化で効率化することで利益を得ることができます。

数理最適化：連続値最適化。機械学習などで使われる。 組合せ最適化：離散値最適化。業務などで使われる。

今回は後半の組合せ最適化をメインに見ます。

・遺伝的アルゴリズム ・タブーサーチ ・シミュレーテッドアニーリング

この３つが代表的らしい。今回は遺伝的アルゴリズムを見ていきます。 メタヒューリスティクスはさまざまな最適化問題をプログラムできるような汎用性のあるアルゴリズムですが、 確率的な動きをするので精度の保証がありません。

遺伝的アルゴリズム（いでんてきアルゴリズム、英語：genetic algorithm、略称：GA）とは、1975年にミシガン大学のジョン・H・ホランド（John Henry Holland）によって提案された近似解を探索するメタヒューリスティックアルゴリズムである。人工生命同様、偶然の要素でコンピューターの制御を左右する。4つの主要な進化的アルゴリズムの一つであり、その中でも最も一般的に使用されている。 https://ja.wikipedia.org/wiki/%E9%81%BA%E4%BC%9D%E7%9A%84%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

とても一般的なもので、製造業でもよく使われている汎用性の高いアルゴリズムです。

遺伝的アルゴリズムは一般に以下の流れで実装される。なお、下記では個体数をN, 最大世代数をGと置く。

1.あらかじめN個の個体が入る集合を二つ用意する。以下、この二つの集合を「現世代」、「次世代」と呼ぶことにする。 2. 現世代にN個の個体をランダムに生成する。

• 評価関数により、現世代の各個体の適応度をそれぞれ計算する。
• ある確率で次の3つの動作のどれかを行い、その結果を次世代に保存する。 　　1. 個体を二つ選択（選択方法は後述）して交叉（後述）を行う。 　　2. 個体を一つ選択して突然変異（後述）を行う。 　　3. 個体を一つ選択してそのままコピーする。
• 次世代の個体数がN個になるまで上記の動作を繰り返す。
• 次世代の個体数がN個になったら次世代の内容を全て現世代に移す。
• 3.以降の動作を最大世代数G回まで繰り返し、最終的に「現世代」の中で最も適応度の高い個体を「解」として出力する。

https://ja.wikipedia.org/wiki/%E9%81%BA%E4%BC%9D%E7%9A%84%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

選択は生物の自然淘汰をモデル化したもので、適応度にもとづいて個体を増やしたり削除したりする操作である。 選択のアルゴリズムには次のようなものがある。

・ルーレット選択 ・ランキング選択 ・トーナメント選択 ・その他

交叉（組み換え）は生物が交配によって子孫を残すことをモデル化したもので、個体の遺伝子の一部を入れ換える操作である。交叉はその性質上、最も重要な遺伝的操作と言うことができる。

・二点交叉 ・多点交叉 ・一様交叉

突然変異は生物に見られる遺伝子の突然変異をモデル化したもので、個体の遺伝子の一部を変化させる操作である。局所（的）最適解に陥ることを防ぐ効果がある。

初期収束とは、最初の方の世代で「偶然」他の個体より適応度が圧倒的に高い個体が生まれたとき、その個体の遺伝子が集団中に爆発的に増えて探索がかなり早い段階で収束してしまう現象である。ルーレット選択の設定が甘い場合や、突然変異の効果が上手く表れないときに起こりやすい。

最適解と一致するビットの近くにいて最適解の生成を妨げる現象をヒッチハイキングと呼び問題となる。

早速ツールを使ってみたいと思います。うちの会社にバイトに来てた安田氏が会社を作ってGA最適化のパッケージを出しました。

https://vigne-cla.com/vcopt-usage/

無料のPythonパッケージで、遺伝的アルゴリズム（Genetic Algorithm, GA）による本格的な最適化がお手軽にできます。読み方は「ぶいしーおぷと」です。

GAは「調整が難しい」と言われること多いですが、vcoptではすべてのハイパーパラメータが動的に決定されますので、思考停止で使うことができます。

ユーザーがハイパーパラメータを設定する必要がない

できること ＜目的＞ ＜コマンド＞ 順序（並び替え）の局所最適化 vcopt().opt2() 順序（並び替え）の大域最適化(1) vcopt().tspGA() 離散値の組合せ最適化(*1) vcopt().dcGA() 連続値の組合せ最適化(1) vcopt().rcGA() (*1) いずれも大域解を保証するものではありません ということでとても便利そうです。

pip 最新バージョンは 1.4.9 です（2019年5月13日時点）

Copy
!pip install vcopt

Processing /home/jovyan/.cache/pip/wheels/ed/2a/67/375845537daa7c25054eff6cc6af9b7017b19f44ba160d9145/vcopt-1.6.3-py3-none-any.whl

Requirement already satisfied: numpy in /opt/conda/lib/python3.8/site-packages (from vcopt) (1.19.1)

Requirement already satisfied: joblib in /opt/conda/lib/python3.8/site-packages (from vcopt) (0.16.0)

Requirement already satisfied: matplotlib in /opt/conda/lib/python3.8/site-packages (from vcopt) (3.2.2)

Requirement already satisfied: kiwisolver>=1.0.1 in /opt/conda/lib/python3.8/site-packages (from matplotlib->vcopt) (1.2.0)

Requirement already satisfied: python-dateutil>=2.1 in /opt/conda/lib/python3.8/site-packages (from matplotlib->vcopt) (2.8.1)

Requirement already satisfied: pyparsing!=2.0.4,!=2.1.2,!=2.1.6,>=2.0.1 in /opt/conda/lib/python3.8/site-packages (from matplotlib->vcopt) (2.4.7)

Requirement already satisfied: cycler>=0.10 in /opt/conda/lib/python3.8/site-packages (from matplotlib->vcopt) (0.10.0)

Requirement already satisfied: six>=1.5 in /opt/conda/lib/python3.8/site-packages (from python-dateutil>=2.1->matplotlib->vcopt) (1.15.0)

Installing collected packages: vcopt
Display all output >>>

from vcopt import vcopt

順序の局所最適化｜vcopt().opt2() このコマンドでは順序の局所最適化ができます。2-opt法を独自に高速化したアルゴリズムを用いています。

para, score = vcopt().opt2(para,
                           score_func,
                           aim,
                           show_para_func=None,
                           seed=None,
                           step_max=float('inf'))

vcopt().tspGA() このコマンドでは順序の大域最適化ができます。親のもつ「辺」を受け継ぐような交叉法を採用し、独自の高速化アルゴリズムを用いています。

para, score = vcopt().tspGA(para_range,
                            score_func,
                            aim,
                            show_pool_func=None,
                            seed=None,
                            pool_num=None)

vcopt().dcGA() このコマンドでは離散値の組合せ最適化ができます。一点交叉と二点交叉を組み合わせた交叉法を採用しています。

para, score = vcopt().dcGA(para_range,
                           score_func,
                           aim,
                           show_pool_func=None,
                           seed=None,
                           pool_num=None)

vcopt().rcGA() このコマンドでは連続値の組合せ最適化ができます。交叉法には REX (Real-Coded Ensemble Crossover) を採用しています。

para, score = vcopt().rcGA(para_range,
                           score_func,
                           aim,
                           show_pool_func=None,
                           seed=None,
                           pool_num=None)

評価関数の書き方｜score_func() score_func() は評価値を計算する関数です。GA中に頻繁に呼び出されます。 評価します。

#評価関数
def score_func(para):

    #スコアの計算
    score = ...

    return score

可視化関数の書き方｜show_pool_func() show_pool_func() は、GA中にpoolを可視化するための関数です。これを設定することで、GA中の個体群の様態や、最適値の推移を見ることができます。

#poolの可視化
def show_pool_func(pool, **info):

    #GA中の諸情報はinfoという辞書に格納されて渡されます
    #これらを受け取って使用することができます
    gen = info['gen'] #現在の世代
    best_index = info['best_index'] #エリート個体のインデックス
    best_score = info['best_score'] #エリート個体の評価値
    mean_score = info['mean_score'] #個体群の平均評価値
    mean_gap = info['mean_gap'] #目標値と評価値の差の絶対値平均
    time = info['time'] #経過時間（秒）

    #可視化
    print(...)

ドレッシングをつくる。人の評価を元に評価を行い、ドレッシングを生成。 「6-1. 遺伝的アルゴリズムを用いたドレッシングのレシピ最適化」 https://vigne-cla.com/6-1/

スケジュールを解く。 「9-2. VCOPTでスケジューリング問題を解く（12種のレシピ編）」 https://vigne-cla.com/9-2/

二足歩行のゲームを解く。 「9-4. VCOPTで二足歩行を最適化する」 https://vigne-cla.com/9-4/

それ以外にも様々な応用があり、応用範囲の広さが伺えます。

GAはとても使い所のいいアルゴリズムで経験者のパラメータチューニングを元に様々なものを最適化できるということで価値がありそうです。以上です。