遺伝的アルゴリズムにおけるルーレットの選択

1. 概要

このチュートリアルでは、遺伝的アルゴリズムのルーレットホイール選択方法を学習します。

組換えのための染色体の選択は、遺伝的アルゴリズムの必須のステップです。後者は、次に、生物種の進化過程に還元することはできませんが、触発されたアルゴリズムです。

遺伝的アルゴリズムは、機械学習で重要なアプリケーションを見つけます。たとえば、強化学習のポリシーの選択にそれらを使用します。しかしまた、深層学習、サブセット和問題、パスファインディング、または一般に、多くの検索のソリューションのパラメーターの最適化で推論と学習の問題。

それらが解決するのに役立つ現実の問題は、新しい材料の発見から計算生物学におけるバイオマーカーの同定にまで及びます。しかしまた、医学における病気のスクリーニングと創薬。したがって、これらはデータサイエンティストのツールボックスの重要なツールです。

遺伝的アルゴリズムが意図したとおりに機能するためには、染色体間の組換えの関連する問題を最初に解決する必要があります。

染色体の典型的な定義は、それをバイナリ変数を含む固定長配列と見なします。

次に、変数の各ビットは、あるタイプのパラメーターまたは特性にマップされます。 このようにして、染色体に関して排他的にバイナリ特性の有限集合を所有する個人を記述することができます。したがって、染色体は、さまざまなタイプの個体を含む集団の表現を可能にします。

これにより、複数のサブシステムで構成される複雑なエージェントを表すことができます。たとえば、強化学習のポリシーの場合、染色体は通常、エージェントの知覚システムまたはその移動コントローラー、あるいはその両方に対応します。

それぞれが独自の染色体を持つすべての個人が、環境で活動を開始します。彼らがそうであるように、それぞれはそのパフォーマンスに応じてフィットネスの尺度を受け取ります。次に、母集団内のすべての個人の適合度を計算した後、組換えフェーズに進みます。

このフェーズでは、親として機能する個人を選択します。これらの親は、クロスオーバーまたは組換えと呼ばれる手順に従って染色体を混合します。

したがって、染色体が組換えの対象となる親を特定する方法が必要です。

この方法では、母集団内の個人の適応度を使用する必要があります。 または、そうでなければ、ある世代と次の世代の間で学習はありません。

選択をサポートするためにフィットネスを使用する方法には、主に2つのカテゴリがあります。

決定論的方法は、例えば、組換えのための集団の中で最も適合する個体の選択を含む。彼らは、地域の最大値に達した後、進化を停止する人口を開発する傾向があるため、一般的に信用を失っています。

あるいは、確率論的方法を使用して親を選択することもできます。これらの方法の中で最も極端な方法は、均一な確率でランダムに個人を選択し、したがって、個人の適応度を完全に無視します。

代わりに、ルーレットホイールの選択が適切な中間方法です。これにより、クロスオーバーの染色体を識別する離散確率分布が作成されます。

ルーレット選択は確率的選択方法であり、個人の選択の確率はその適応度に比例します。この方法は実際のルーレットに触発されていますが、それらとは重要な違いがあります。カジノやギャンブルの映画からわかるように、ルーレットには常に同じサイズのスロットがあります。

ただし、これは、すべてのスロットが同じ確率で選択されることを意味します。代わりに、ルーレットの加重バージョンを実装できます。 これを使用すると、個人の適応度が高くなるほど、その選択が行われる可能性が高くなります：

したがって、ルーレット選択方法の最初の要素は、個々の適合度が選択の可能性に比例することです。

しかし、これでは十分ではありません。これは、母集団に個人がいる場合、それらの選択の確率の合計が1に等しいためです。 結果として、個々の確率のすべての値を区間に正規化する必要もあります。

最後に、上記の考慮事項を要約して、設定した要件を満たす方法を開発できます。

個人のいる母集団では、対応する適応度の値を持つ各染色体について、対応する選択の確率を次のように計算します。

次に、確率分布を、組換えのために選択した親をサンプリングするものとして単純に扱うことができます。

この記事では、遺伝的アルゴリズムのルーレット選択を実行する方法を学習しました。