遺伝的アルゴリズムとPython実装におけるいくつかの異なる選択演算子

序文

この論文では、遺伝的アルゴリズムにおけるいくつかの選択戦略についてまとめています。

• 比例ルーレットホイールの選択
• 線形ランキング選択
• 指数ランキング選択
• トーナメントの選択

それぞれの選択戦略を Python を使用して実装し、組み込みプラグインとして作成した遺伝的アルゴリズム フレームワーク GAFT に統合しました。遺伝的アルゴリズムを使用して問題を最適化したり、遺伝的アルゴリズムを学習したりする必要がある人にとって参考資料として使用できます。

プロジェクトリンク:

• GitHub: https://github.com/PytLab/gaft
• pypi: https://pypi.python.org/pypi/gaft について

遺伝的アルゴリズムにおける選択演算子

遺伝的アルゴリズム (GA) は、ダーウィンの進化論における「適者生存」の原理を模倣し、最終的に最適化目標に対する最適なソリューションを取得する適応型ヒューリスティック検索アルゴリズムです。次の図は、単純な遺伝的アルゴリズムのプロセスを示しています。

集団内で交配する必要がある種を選択する方法は多数あり、適切な選択戦略を選択すると、遺伝的アルゴリズムの全体的なパフォーマンスに大きな影響を与えます。選択アルゴリズムが選択の多様性を減らすと、集団は、望ましい全体最適ではなく、局所最適に早期に収束することになります。これを「早期成熟」と呼びます。選択戦略があまりにも多岐にわたると、アルゴリズムが最適なポイントに収束することが難しくなります。したがって、遺伝的アルゴリズムが効率的にグローバル最適点に収束できるように、これら 2 つの点のバランスをとる必要があります。

GAFT フレームワークのオペレータ プラグイン

GAFT は私が独自のニーズに基づいて開発した遺伝的アルゴリズムフレームワークです。関連の紹介ブログは「GAFT - Python で実装された遺伝的アルゴリズムフレームワーク」および「MPI を使用して遺伝的アルゴリズムフレームワーク GAFT を並列化する」を参照してください。このフレームワークはプラグイン インターフェイスを提供し、ユーザーはカスタム オペレーターとオンザフライ分析プラグインを使用して、GAFT フレームワークで遺伝的アルゴリズム プロセスを実行し、対象の問題を最適化できます。

このセクションでは、遺伝的演算子に関する GAFT のインターフェース仕様と、GAFT で使用できる演算子の記述方法について簡単に紹介します。

GAFT では、遺伝的演算子を記述するには、フレームワークの組み込み基本クラスを継承し、基本クラスによって提供されるインターフェースに基づいて独自の演算子を実装する必要があります。基本クラスの定義はすべて /gaft/plugin_interfaces/operators/ ディレクトリにあります。以下では、選択演算子を例にしてインターフェースを紹介します。

GAFT の選択演算子の基本クラスは GASelection です。遺伝的アルゴリズム プロセスでは、このクラスのインスタンスの選択メソッドが呼び出され、演算子の関連する選択戦略に従って、子孫を生成するために、集団から 1 組の種が父親と母親として選択されます。基本クラスは次のように定義されます。

クラス GASelection(メタクラス=SelectionMeta):
 '' '
    選択の動作を簡単に拡張するためのインターフェースを提供するクラス
    手術。
 '' '
    def select (self, population, fitness):
 '' '
        必要なときに呼び出されます 後に繁殖させるために集団から親を選択する。
        :param population:現在の人口。
        :type population: GA人口
        : 親を返します:交差のために選択された 2 つの個体。
        :type parents: 2 つの GAIndividual オブジェクトのタプル。
 '' '
        NotImplementedError を発生させる

select メソッドのパラメーターは、現在の人口 population と対応する適応度関数 fitness です。ここで、population は GAPopulation オブジェクトである必要があり、fitness も呼び出し可能なオブジェクトである必要があります。

もちろん、これらは Python のような動的型付け言語では少し役に立たないように思えるかもしれませんが、ユーザーを標準化できるようにするために、クラス オブジェクトをインスタンス化するときに、インターフェイスの実装とインターフェイスのパラメーター型を制限するために Python のメタクラスを使用します。具体的な実装は /gaft/plugin_interfaces/metaclasses.py にあります。興味のある方は実装方法をご覧ください。

カスタム演算子の具体的な記述方法と選択戦略については、次のセクションで紹介します。

異なる選択戦略

このセクションでは、主に 4 つの異なる選択戦略をまとめ、gaft プラグインの形式で Python に実装します。

選択演算子は、集団の次の世代で新しい個体を再生するために集団からどの個体を選択するかを決定します。その主な原則は次のとおりです。

個体が優れているほど、親になる可能性が高くなる

選択演算子は、適応度関数が個体が十分に「優れている」かどうかを判断するための重要な基準であるため、遺伝的アルゴリズムの反復に適応度関数を導入します。しかし、集団内の最適な種が必ずしも全体最適点の近くにあるとは限らないため、選択プロセスは適応度関数のみに依存することはできません。したがって、比較的「良い」とは言えない個体にも繁殖の機会を与え、「早熟」を避けるべきです。

選択演算子は、適応度関数が個体が十分に「優れている」かどうかを判断するための重要な基準であるため、遺伝的アルゴリズムの反復に適応度関数を導入します。しかし、集団内の最適な種が必ずしも全体最適点の近くにあるとは限らないため、選択プロセスは適応度関数のみに依存することはできません。したがって、比較的「良い」とは言えない個体にも繁殖の機会を与え、「早熟」を避けるべきです。

比例ルーレットホイールの選択

このルーレットホイール選択戦略は、最も基本的な選択戦略の 1 つです。集団内の個体が選択される確率は、個体に対応する適応度関数の値に比例します。集団内のすべての個体の適応度値を累積して正規化し、最後にカジノの回転するルーレットホイールと同様に、乱数を通じて乱数が落ちる領域に対応する個体を選択する必要があります。

それぞれの個別のaiが選択される確率は次のとおりです。

さて、これでこのアルゴリズムを GAFT で実行できる演算子として記述できるようになりました。

ランダムインポートからランダム
bisect_right をインポート
itertoolsからインポートして蓄積する
  
 ...plugin_interfaces.operators.selectionからGASelection をインポートします
  
クラス RouletteWheelSelection(GASelection):
    __init__(self)を定義します。
 '' '
        適応度比例選択(FPS)による選択演算子または 
        いわゆるルーレットホイール選択の実装。
 '' '
        合格
  
    def select (self, population, fitness):
 '' '
 FPS アルゴリズムを使用して親のペアを選択します。
 '' '
        # フィットネス値を正規化する のために すべての個人。
        fit = [ population.individuals内のindvの適合度 (indv)]
        min_fit =最小（フィット）
        fit = [(i - min_fit)、 iが fitの場合] 
  
        # ルーレットホイールを作成します。
        sum_fit =合計（フィット）
        ホイール = リスト([i/sum_fit for i in fit])) 
  
        #父親と母親を選択します。
        父親のidx = bisect_right(ホイール、ランダム())
        父親 = 人口[父親IDX]
        mother_idx = (father_idx + 1) % len(ホイール)
        母親 = 人口[mother_idx] 
  
父、母を返す

プロセスは主に以下の部分に分かれています。

1. GASelectionクラスの継承
2. 選択メソッドの実装
3. 選択されたパラメータはGAPopulationインスタンスと適応度関数である。
4. アルゴリズムに従って繁殖する必要がある2つの種を選択し、それらを返します

トーナメントの選択

アルゴリズム実行の効率性と実装の容易さにより、トーナメント選択アルゴリズムは遺伝的アルゴリズムで最も人気のある選択戦略です。実際の応用では、この戦略は確かに基本的なルーレットよりも優れています。彼の戦略も非常に直感的です。つまり、集団全体から n 個の個体を選択し、それらを競争させ (トーナメント)、その中から最良の個体を抽出します。トーナメントに参加する人数をトーナメント サイズと呼びます。通常、n=2 が最も一般的に使用されるサイズであり、バイナリ トーナメント選択とも呼ばれます。

トーナメント選択の利点:

1. より小さい複雑度 O(n)
2. 並列化が容易
3. 局所最適点に陥りにくい
4. すべてのフィットネス値をソートする必要はない

次の図は、n=3 の場合のトーナメント選択のプロセスを示しています。

GAFT で実行するカスタム演算子の作成を開始できます。

ランダムインポートサンプルから
  
 ...plugin_interfaces.operators.selectionからGASelection をインポートします
  
クラスTournamentSelection(GASelection):
    def __init__(self, トーナメントサイズ=2):
 '' '
        トーナメント戦略を使用したトーナメントサイズが等しい選択演算子
2つまで デフォルト。
 '' '
        self.tournament_size = トーナメントサイズ
  
    def select (self, population, fitness):
 '' '
トーナメント戦略を使用して親のペアを選択します。
 '' '
        # 競争機能。
        完了 = lambda 競合相手:最大(競合相手、キー= 適応度) 
  
        #トーナメントサイズの有効性を確認します。
        self.tournament_size >= len(population)の場合:
            msg = 'トーナメント サイズ ({}) が人口サイズ ({}) より大きいです'  
            ValueError を発生させます(msg.format(self.tournament_size, len(population))) 
  
        # 2 つのグループの勝者を親として選択します。
        競争相手1 = サンプル(人口.個人、自己.トーナメントサイズ)
        競争相手2 = サンプル(人口.個人、自己.トーナメントサイズ)
        父親、母親 = 完了(競合相手1)、完了(競合相手2) 
  
父、母を返す

以下に紹介する 2 つの選択戦略は、どちらもソート選択戦略に基づいています。上記の最初の基本的なルーレット選択アルゴリズムには欠点があります。つまり、個体の適応度値が 0 の場合、選択される確率は 0 になり、この個体は子孫を産むことができません。したがって、各個体に対応する選択確率を割り当てるには、ソートベースのアルゴリズムが必要です。

線形ランキング選択では、集団内の個体は最初に適応度の値に従ってソートされ、次にすべての個体にシリアル番号が割り当てられます。最良の個体は N で、選択される確率は Pmax です。最悪の個体のシリアル番号は 1 で、選択される確率は Pmin です。したがって、それらの間の他の個体の確率は、次の式に従って取得できます。

実装コード:

ランダムインポートからランダム
itertoolsからインポートして蓄積する
bisect_right をインポート
  
 ...plugin_interfaces.operators.selectionからGASelection をインポートします
  
クラス LinearRankingSelection(GASelection):
    __init__(self, pmin=0.1, pmax=0.9)を定義します。
 '' '
        線形ランキング選択方法を使用する選択演算子。
        参考文献：ベイカーJE.遺伝的適応選択法
        アルゴリズム[C]//遺伝学に関する国際会議の議事録
        アルゴリズムとその応用。1985:101-111。
 '' '
        #最悪および最善の個体の選択確率。
        自己.pmin、自己.pmax = pmin、pmax 
  
    def select (self, population, fitness):
 '' '
線形ランキング法を使用して親個体のペアを選択します。
 '' '
        # 個人番号。
        NP = len(人口)
        #ランクを追加 人口内のすべての個人。
        sorted_indvs = sorted(population.individuals, key =fitness, reverse= True ) です。 
  
        # 選択確率を線形に割り当てます。
        # 注意: ここで、ランク i は{1, ..., N}に属します。
        p = ラムダ i: (self.pmin + (self.pmax - self.pmin)*(i-1)/(NP-1))
        確率 = [self.pmin] + [ iが範囲(2, NP)内の場合のp(i)] + [self.pmax] 
  
        # 確率を正規化します。
        psum =合計（確率）
        wheel = list(accumulate([確率pのp/psum ])) 
  
        # 親を選択します。
        父親のidx = bisect_right(ホイール、ランダム())
        父親 = 人口[father_idx]
        mother_idx = (father_idx + 1) % len(ホイール)
        母親 = 人口[mother_idx] 
  
父、母を返す

上記の線形ランキング選択戦略と同様に、この指数ランキングでは、各個体の選択確率を決定する際に指数式を使用します。ここで、c は基数で、0<c<1 を満たします。

実装コード:

ランダムインポートからランダム
itertoolsからインポートして蓄積する
bisect_right をインポートする
  
 ...plugin_interfaces.operators.selectionからGASelection をインポートします
  
クラスExponentialRankingSelection(GASelection):
    def __init__(self, ベース=0.5):
 '' '
        指数ランキング選択方法を使用する選択演算子。
        :param base:指数の底
        :type 基数:浮動小数点数 範囲内(0.0, 1.0)
 '' '
        そうでない場合（0.0 < ベース < 1.0）:
            ValueError を発生させます( '指数 c の底は範囲 (0.0, 1.0) 内になければなりません' )
        自己.base = ベース
  
    def select (self, population, fitness):
 '' '
指数ランキング法を使用して親個体のペアを選択します。
 '' '
        # 個人番号。
        NP = len(人口)
        # 注意: ここで、ランク i は{1, ..., N}に属します。
        p = ラムダ i: self.base**(NP - i)
        確率 = [ iが範囲(1, NP + 1)内の場合のp(i)]
        # 確率を正規化します。
        psum =合計（確率）
        wheel = list(accumulate([確率pのp/psum ]))
        # 親を選択します。
        父親のidx = bisect_right(ホイール、ランダム())
        父親 = 人口[father_idx]
        mother_idx = (father_idx + 1) % len(ホイール)
        母親 = 人口[mother_idx]
父、母を返す

要約する

この記事では、遺伝的アルゴリズムにおける 4 つの異なる選択戦略を紹介し、まとめます。また、この記事で記述した遺伝的アルゴリズム フレームワークのカスタム演算子インターフェイスについても簡単に紹介します。インターフェイスの要件に従って、この記事の選択戦略に対応する演算子が実装されています。これらの演算子は、GAFT フレームワークの組み込み演算子として GAFT にも組み込まれており、GAFT を使用するユーザーが直接使用できます。

参照する

• Shukla、Anupriya、Hari Mohan Pandey、Deepti Mehrotra。「遺伝的アルゴリズムにおける選択手法の比較レビュー」Futuristic Trends on Computational Analysis and Knowledge Management (ABLAZE)、2015 International Conference on。IEEE、2015 年。