Pythonでシンプルな遺伝的アルゴリズムをゼロから実装する

遺伝的アルゴリズム

遺伝的アルゴリズムは、自然選択のプロセスを模倣した最適化アルゴリズムです。 彼らは「数学のトリック」を一切使わず、機能することが分かっている論理をそのままコピーしただけです。

[[329691]]

遺伝的アルゴリズムにおける自然選択

この自然選択のプロセスは、適者生存、つまり最も優れた個体（動物、植物など）が生き残れるようにする自然界のプロセスに基づいています。 これらの最も適応した個体は互いに交配し、新しい世代を生み出します。 自然はまた、ゲノムの突然変異という形で、ある程度のランダム性を加えます。

新しい世代には善良な人々と悪人が混在していますが、ここでは善良な人々が生き残り、交尾し、新しい世代を生み出し続けます。

その結果、世代から世代へと継続的な改善が実現します。

人材計画のための遺伝的アルゴリズム

人員計画は多くの企業で行われている最適化研究の対象です。 企業に多くの従業員がいる場合、特定の制約を満たしながらビジネスニーズに合ったプランを見つけることが難しくなります。 遺伝的アルゴリズムは、他の既存のソリューションの中でこの問題を解決するための最適化手法です。

Python実装

この記事では、遺伝的アルゴリズムのさまざまな部分を理解する方法について詳しく説明します。

以下のコードは、遺伝的アルゴリズムの製品コードの簡略化されたバージョンです。 速度や再利用性よりも、例の理解を深めるために最適化されています。 サンプル データに適用されたリストされた各ステップが含まれます。

遺伝的アルゴリズムのコードウォークスルーの 6 つのステップ

遺伝的アルゴリズムの手順:

• 遺伝的アルゴリズムのデータをエンコードするにはどうすればいいですか?
• 遺伝的アルゴリズムのソリューションを評価するにはどうすればよいでしょうか?
• 遺伝的アルゴリズムの交配（交差）をコード化するにはどうすればいいですか?
• 遺伝的アルゴリズムの突然変異をエンコードするにはどうすればよいでしょうか?
• 遺伝的アルゴリズムの選択をどのように定義するのでしょうか?
• 遺伝的アルゴリズムの反復と停止をどのように定義するのでしょうか?

ノートブックを持ち歩きたい場合は、ここからダウンロードできます。

ステップ 1 - 遺伝的アルゴリズム用にデータをエンコードする方法

入力データ - 2つのプラン

このコードでは、同じ従業員プランの 2 つの異なるシェイプを使用します。

カテゴリー 1 プラン - 従業員 1 人あたり:

> 遺伝的アルゴリズム用のデータのエンコード - タイプ 1 計画 - 従業員ごと。写真は著者によるものです。

最初の図形は、従業員ごとのスケジュール、詳細ビューになります。 週間スケジュールの合計は、各日 (この場合は 5 日間) のリストを含むリストです。 各日次リストにはシフトのリスト (この場合は従業員の 11 シフト) が含まれます。 各シフトは、従業員 ID (0 から 11、参考値)、開始時刻 (0 から 24 時の間)、シフト期間 (0 から 10 時間の間) のリストです。

従業員はいつ働いているかを知るために、このようなスケジュールを必要としています。

カテゴリー2プラン - 時間合計:

> 遺伝的アルゴリズム用のデータのエンコード - タイプ 2 計画 - 時間あたりの合計。写真は著者によるものです。

2 番目のプラン タイプは、1 時間あたりに雇用される従業員の総数です。 店舗オーナーはこの計画を使用して、計画が店舗の推定ニーズに対応しているかどうかを判断します。

ステップ 2 - 遺伝的アルゴリズムのソリューションを評価するには?

時間単位の人員配置計画を評価するには、目標状況を定義する必要があります。 この目標を定義することは最適化の一部ではありません。これは別のプロジェクトの問題になります。

> 遺伝的アルゴリズムの評価の定義 — 目標状況の定義。写真は著者によるものです。

提案された計画と目標計画の違いをどのように評価するかを定義する必要があります。 これは、従業員の超過勤務時間の合計を従業員の休業勤務時間の合計に加算することにより、時間単位で実行されます。 これはコスト関数であり、最小限に抑える必要があります。

> 遺伝的アルゴリズムの評価の定義 — コスト関数の定義。写真は著者によるものです。

人員過剰または人員不足の重みを増やすこともできますが、この例ではそれらを等しくしました。

ステップ 3 — 遺伝的アルゴリズムの交配 (クロスオーバー) をどのようにコーディングするか?

遺伝的アルゴリズムには、交配（交差または組み換えとも呼ばれる）と突然変異という 2 つの重要なステップがあります。

交配の段階では、自然選択と同様に、親集団の個体の子孫から新しい世代が形成されます。

これを例に当てはめると、後で、あまり良くない従業員プランを多数生成し、その中で最も良いプランをつなぎ合わせようとすることになります。 したがって、2 つの個人 (従業員プラン) を互いに「混合」する方法を定義する必要があります。

この例では、次のようにコーディングすることにしました。

• 人口からランダムに母親を選ぶ
• 人口からランダムに父親を選ぶ
• 親と同じサイズですが、0 と 1 がランダムに埋め込まれた子を作成します。
• 子供の位置は 1 で、父親からデータを取得します。子供の位置は 0 で、母親からデータを取得します。
• これを各子供に対して繰り返します（子供の数は人口に等しい）

> 遺伝的アルゴリズムにおける交差の定義。写真は著者による。

これは 1 つの方法であり、他にも多くの方法が可能です。 遺伝的アルゴリズムが機能するためには、組み合わせコードにランダム性を持たせることが重要です。 もちろん、組み合わせはステップ 1 で選択したデータ構造に適合する必要があります。

ステップ 4 - 遺伝的アルゴリズムの突然変異をエンコードするにはどうすればよいでしょうか?

遺伝的アルゴリズムにおける 2 番目の重要なステップは突然変異です。 新世代の製品に完全にランダムな変更を加えることが含まれます。 このランダムな変化により、もはや存在しない集団に新しい値を追加することができます。

たとえば、アルゴリズムが数回反復実行され、選択と組み合わせのプロセスにおけるランダム性により、午前 10 時までのすべての開始時刻が選択解除された状況を考えてみましょう。 突然変異がなければ、アルゴリズムはその値を取り戻すことはできず、後でより良い解決策を提供できる可能性があります。

（少数の）新しい値をランダムに挿入すると、アルゴリズムがこの状況から抜け出すのに役立ちます。

> 遺伝的アルゴリズムにおける突然変異の定義。写真は著者による。

ここでは、シフト期間またはシフト開始時刻の追加を 0 から 10 までのランダムな値に置き換えるものとしてエンコードされます。 n_mutations 値を指定すると、操作を繰り返すことができます。

ステップ 5 - 遺伝的アルゴリズムの選択をどのように定義しますか?

選択プロセスは非常に簡単です。

まず、実行可能なソリューションをすべて選択します。従業員が 10 時間以上働くソリューションは除外します。

> 遺伝的アルゴリズムの選択の定義 — 実現可能性。写真は著者による。

そして、各人（つまり各従業員プラン）に評価関数を適用し、最適な候補者を選択します。 選択された個体の数はコード内で可変に保持されます。

> 遺伝的アルゴリズムの選択の定義 — コスト。写真は著者による。

ステップ 6 - 遺伝的アルゴリズムの反復と停止をどのように定義しますか?

コードの最後の部分では、反復される全体のコードに以前のすべての構成要素を追加します。

> 遺伝的アルゴリズムの反復の定義。写真は著者によるものです。

最適化パラメータ調整

遺伝的アルゴリズムが完璧に機能するためには、適切なパラメータを選択することが重要です。ここでは、generation_size、n_mutations、n_best が重要です。

これら 3 つを調整することで、両方の最適な組み合わせを見つけることができます。

• 解決策に収束する（改善が見られない場合にランダムに方向転換するのではなく）
• 局所最適に陥らないようにする

アルゴリズムを調整した後もまだ問題が解決しない場合は、交配機能と突然変異機能を適応させて何が起こるかを確認するのも改善の方向性の 1 つです。

(この記事は Joos Korstanje の記事「Python でゼロから作るシンプルな遺伝的アルゴリズム」からの翻訳です。参照:

https://towardsdatascience.com/a-simple-genetic-algorithm-from-scratch-in-python-4e8c66ac3121)