遺伝的アルゴリズム

Genetic Algorithm の定義

cBots の最適化について説明する際、cBots を「遺伝的アルゴリズム」メソッドで洗練できると述べました。このガイドでは、それが正確に何であるか、どのように機能するかを説明します。

遺伝的アルゴリズムメソッドは自然選択理論に基づいています。この理論では、最も適応した個体だけが次世代の繁殖に進むとされています。

cBot の最適化においては、各最適化パスが「個体」と見なされます。個々のパスを評価するために、遺伝的アルゴリズムは各パスに対して特定の適応度スコアを計算し、このスコアを他のすべてのパスと比較します。

機能させるためには、遺伝的アルゴリズムは初期集団が必要です。それを生成するために、最適化ツールはランダム化されたパラメータでいくつかの異なるパスを実行します。初期集団が作成された後、アルゴリズムは最も適応した最適化パスを見つけるプロセスを開始します。このプロセスは「子」パスの適応度スコアが停滞し、収束し始めるまで続きます。この時点で、アルゴリズムは停止します。

遺伝的アルゴリズムのステージ

遺伝的アルゴリズムには、以下のステージがあります。

 
 
 
選択
交叉
突然変異

各ステージの説明は以下の通りです。

選択

このステージでは、アルゴリズムがそれぞれの適応度スコアを使用して、最も適応した2つの最適化パスを見つけます。

交叉

最も適応した2つの最適化パスが見つかった後、アルゴリズムはこれらを使用して「子」(または「子孫」) パスを作成します。これは、両方の「親」パスのパラメータ値の組み合わせを使用して行います。

cBot に最適化のための4つの異なるパラメータがある場合、アルゴリズムは「子孫」パスの最初と第二のパラメータの値を一つの「親」から取得し、第三と第四のパラメータの値を二つ目の「親」から取得します。

突然変異

このステージでは、アルゴリズムが「子孫」パスを突然変異させ、1つまたは複数のパラメータ値をランダムに変更します。

突然変異ステージの後、最適化ツールは新しい「子孫」最適化パスを実行します。その後、すべてのステージを繰り返しますが、「子孫」パスの適応度スコアが最後の最適化パスよりも高かった場合のみ繰り返します。この結果は、改善の余地があることを示しており、最適化を続けるべきであることを意味します。

そうでない場合、アルゴリズムはその停滞カウンターを増加させます。停滞カウンターがアルゴリズムの停滞期間パラメータの値に達すると、最適化プロセスは自動的に停止します。

遺伝的アルゴリズムのパラメータ

遺伝的アルゴリズムには、ライフサイクル中に使用されるいくつかのパラメータがあります。これらのパラメータは変更できません。

パラメータ定義
集団サイズ集団の最大サイズ、または各最適化イテレーション中に実行される最大パス数。
最大イテレーションカウントアルゴリズムが実行する最適化イテレーションの最大数。
停滞期間停滞カウンターの最大値。この値に達すると、アルゴリズムは停止します。
エリート割合この値は、現在のアルゴリズムイテレーションから最も適応度スコアが高い X% の個体を選択するために使用されます。これらのパスは次のイテレーションに「生き残る」ことになります。
トーナメントサイズ割合この値は、親パスを見つけるためにイテレーションから選択される X% の個体に使用されます。
移住者割合この値は、各新しいイテレーションまたは集団生成中に追加される X% のランダムに作成されたパスに使用されます。
突然変異割合突然変異される「子孫」パスのパラメータの割合。
突然変異確率割合突然変異される「子孫」パスの割合。この割合に含まれないパスは突然変異ステージを通過しません。
目次

このページについて