GAFT: Python で実装された遺伝的アルゴリズムフレームワーク

序文

最近、遺伝的アルゴリズムを使用していくつかのことを最適化する必要があります。当初は、最適化のためにいくつかのアルゴリズムに基づいて簡単な関数を実装する予定でしたが、後で実行するために非一般的な関数を単に記述するだけでは、演算子を改善したり、他の人が使用したりすることが困難になると感じています。同時に、遺伝的アルゴリズムの基本的な概念と操作プロセスは比較的固定されており、一般的にはエンコードメカニズム、選択戦略、交差突然変異演算子、およびパラメーター設計を通じて改善が行われ、アルゴリズムの全体的な構造に大きな影響を与えません。これにより、遺伝的アルゴリズムでは、比較的固定されたフレームワークを記述し、演算子やパラメーターなどのためのスペースを残して、新しいアルゴリズムをテストおよび改善することが非常に適したものになります。そこで、GAFT という小さな遺伝的アルゴリズムフレームワークを作成しました。この記事では、このフレームワークを紹介し、1 次元検索と 2 次元検索を例に使用してその使用方法について説明します。

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

現在、フレームワークは初期バージョンのみが完成しており、比較的シンプルで、よく使用される基本的な演算子がいくつか組み込まれています。ユーザーは、インターフェースルールに従ってカスタム演算子を実装し、フレームワークに組み込んで操作することができます。また、自分のニーズに応じてさらに改良された演算子を追加し、フレームワークをより汎用的なものにするために改良していきます。

文章

遺伝的アルゴリズム入門

ここでは、遺伝的アルゴリズムの基本概念を簡単に紹介し、GAFT の設計原則について説明します。

簡単に言えば、遺伝的アルゴリズムは集団探索技術を使用して、問題に対する実行可能な解決策のグループを表します。選択、交差、突然変異などの一連の遺伝的操作を現在の集団に適用することで、新しい世代の集団が生成され、集団は徐々に、おおよその全体最適解を含む状態に進化します。以下に、遺伝学と遺伝的アルゴリズム関連の用語の対応をまとめます。

用語

アルゴリズムの特徴

決定変数のエンコードを操作オブジェクトとして使用することで、最適化プロセスで生物学の概念を借用することが可能になります。
目的関数を検索情報として直接使用して、検索方向と範囲を決定します。これは、導関数を使用しない最適化に属します。
複数の検索ポイントからの検索情報を同時に使用することは、暗黙的な並列処理です。
これは確率ベースの検索手法です。
自己組織化、自己適応、自己学習の特性を備えています。

アルゴリズムフロー

GAFT 設計原則

遺伝的アルゴリズムのプロセスは比較的固定されているため、私たちの最適化アルゴリズムは基本的に、プロセスの全体的なフレームワーク内でエンコードメカニズム、演算子、パラメータなどを変更します。そのため、フレームワークを作成するときに、それらの固定された遺伝的演算子と適応度関数をインターフェースに書き込み、メタクラス、デコレータなどを使用してインターフェースを制限および最適化し、その後の演算子と適応度関数のカスタマイズに便利になるようにしたいと考えました。 *** すべてのパーツを組み合わせてエンジンを形成し、アルゴリズムフローに従って遺伝的アルゴリズムを実行してターゲットを最適化します。

この方法により、遺伝的アルゴリズムのプロセスを毎回記述する面倒さから解放されます。プラグインを作成するように独自の演算子と適応度関数を実装し、それらを GAFT に組み込むだけで、アルゴリズムのテストや目的関数の最適化を開始できます。

GAFT ファイル構造

このセクションでは、私が実装したフレームワークの全体的な構造を紹介します。

 。 
 
 ├── ライセンス
 
 ├──マニフェスト。   
 
 ├── README.rst 
 
 ├── 例
 
 │ ├── ex01 
 
 │ └── ex02 
 
 ├── ガフト
 
 │ ├── __init__.py 
 
 │ ├── __pycache__ 
 
 │ ├── 分析
 
 │ ├── コンポーネント
 
 │ ├── engine.py 
 
 │ ├── 演算子
 
 │ └── プラグインインターフェース
 
 ├── セットアップ.cfg 
 
 ├── セットアップ.py 
 
 └── テスト
 
 ├── flip_bit_mutation_test.py 
 
 ├── gaft_test.py 
 
 ├── 個別テスト.py 
 
 ├── population_test.py 
 
 ├── ルーレットホイール選択テスト.py 
 
 └── ユニフォームクロスオーバーテスト.py

現在のファイルの結果は上記に表示されます。

組み込みの個体および集団タイプは /gaft/components で定義され、バイナリエンコーディングと実数エンコーディングという 2 つの異なる遺伝子エンコーディング方法を提供します。
/gaft/plugin_interfaces にはプラグインインターフェース定義が含まれており、オンザフライ分析のためのすべての演算子定義とインターフェースルールが含まれています。ユーザーはこれを基に独自のプラグインを作成し、エンジンに組み込むことができます。
/gaft/operators には組み込みの遺伝的演算子が含まれています。これらは /gaft/plugin_interfaces のルールに従って記述されており、演算子の記述例として使用できます。演算子の中には、ルーレットホイール選択演算子、ユニフォーム交差演算子、フリップビット突然変異演算子が組み込まれています。ユーザーは組み込み演算子を直接使用して、GAFT を使用して独自の問題を最適化できます。
/gaft/analysis には、遺伝的アルゴリズムの反復プロセスで変数を分析できる組み込みのオンザフライ分析プラグインが含まれています。たとえば、進化曲線の描画を容易にするために、コンソールログ情報出力プラグインと反復適応値保存プラグインを組み込みました。
/gaft/engine は遺伝的アルゴリズムのプロセス制御モジュールです。これは、以前に定義されたすべての部分を結合し、遺伝的アルゴリズムのプロセスを使用して最適化の反復を実行します。

GAFTの使用

以下では、GAFT を使用して目的関数を最適化する例として 2 つの関数を使用します。

一次元検索

まず、複数の局所極値を持つ単純な関数を最適化してみましょう。組み込み演算子を使用して、関数f(x)=x+10sin(5x)+7cos(4x)の最大値を見つけます。ここで、xの値は範囲[0,10]にあります。

1.まず必要なモジュールをインポートする

数学からインポート sin、cos 
 
  
 
 # population と組み込み演算子関連のクラスをインポートする
 
 gaftからGAEngine をインポート
 
 gaft.componentsからGAIndividual をインポートします
 
 gaft.componentsからGAPopulation をインポートします
 
 gaft.operatorsからRouletteWheelSelection をインポートします
 
 gaft.operatorsからUniformCrossover をインポートします
 
 gaft.operatorsからFlipBitMutation をインポートします
 
  
 
 #分析プラグインを書くためのインターフェースクラス
 
 gaft.plugin_interfaces.analysisからOnTheFlyAnalysis をインポートします
 
  
 
 # 組み込みアーカイブ適合関数の分析クラス
 
 gaft.analysis.fitness_storeからFitnessStoreAnalysis をインポートします
 
  
 
 # 解析プラグインを遺伝的アルゴリズムエンジンに登録するには2つの方法があります

2. エンジンを作成する

# 人口を定義する
 
 indv_template = GAIndividual(範囲=[(0, 10)]、エンコード= 'バイナリ' 、eps=0.001) 
 
人口 = GAPopulation(indv_template=indv_template、サイズ=50) 
 
  
 
 # 遺伝的演算子を作成する
 
選択 = ルーレットホイール選択() 
 
クロスオーバー = UniformCrossover(pc=0.8, pe=0.5) 
 
突然変異 = FlipBitMutation(pm=0.1) 
 
  
 
 # 遺伝的アルゴリズムエンジンを作成します。分析プラグインと適応度関数は、パラメータとしてエンジンに渡すことができます。 
 
エンジン = GAEngine(人口 = 人口、選択 = 選択、 
 
                  交差＝クロスオーバー、突然変異＝突然変異、 
 
                  分析=[FitnessStoreAnalysis])

3. カスタムフィットネス関数

適合関数は、修飾子を使用してエンジンに登録できます。

 @engine.fitness_register 
 
定義フィットネス(indv): 
 
    x, = 独立変数
 
 x + 10*sin(5*x) + 7*cos(4*x)を返します

4. カスタムオンザフライ分析プラグイン

プラグインを定義する際に修飾子を使用して、プラグインをエンジンに直接登録することもできます。

 @engine.analysis_register 
 
クラス ConsoleOutputAnalysis(OnTheFlyAnalysis): 
 
    間隔 = 1 
 
  
 
    def register_step(self, ng, population, engine): 
 
        best_indv = population.best_indv(engine.fitness) 
 
        msg = '世代: {}、最適な適応度: {:.3f}' .format(ng, engine.fitness(best_indv)) 
 
        engine.logger.info(メッセージ) 
 
  
 
    def finalize(self, population, engine): 
 
        best_indv = population.best_indv(engine.fitness) 
 
        x = ベスト_indv.variants 
 
        y = engine.fitness(ベストインダストリー) 
 
        msg = '最適解: ({}, {})' .format(x, y) 
 
        engine.logger.info(メッセージ)

5. では、実行（最適化）を始めましょう！

ここでは 100 世代の人口を飼育しています。

 '__main__' == __name__ の場合: 
 
    # GA エンジンを実行します。 
 
    エンジンを実行(ng=100)

組み込みの分析プラグインは、各反復で各世代の最良の個体を記録し、保存用のデータを生成します。

関数自体の曲線と遺伝的アルゴリズムを使用して得られる進化曲線をプロットします。

最適化プロセスのアニメーション:

2D検索

次に、GAFTの組み込み演算子を使用して、複数の極値点を持ち、x、yの範囲が[−2,2]であるバイナリ関数f(x) = ysin(2πx) + xcos(2πy)の最大値を検索します。

ここでは、分析プラグインをカスタマイズするのではなく、組み込みの分析クラスを直接使用し、エンジンの構築時に直接渡します。

 '' ' 
 
グローバル最大値を見つける バイナリ 関数: f(x) = y*sim(2*pi*x) + x*cos(2*pi*y) 
 
 '' ' 
 
  
 
数学からsin、cos、pi をインポート
 
  
 
 gaftからGAEngine をインポート
 
 gaft.componentsからGAIndividual をインポートします
 
 gaft.componentsからGAPopulation をインポートします
 
 gaft.operatorsからRouletteWheelSelection をインポートします
 
 gaft.operatorsからUniformCrossover をインポートします
 
 gaft.operatorsからFlipBitMutation をインポートします
 
  
 
 #最適なフィットネス分析が組み込まれています。 
 
 gaft.analysis.fitness_storeからFitnessStoreAnalysis をインポートします
 
 gaft.analysis.console_outputからConsoleOutputAnalysis をインポートします
 
  
 
 # 人口を定義します。 
 
 indv_template = GAIndividual(範囲=[(-2, 2), (-2, 2)], エンコーディング= 'バイナリ' , eps=0.001) 
 
人口 = GAPopulation(indv_template=indv_template、サイズ=50) 
 
  
 
 # 遺伝的演算子を作成します。 
 
選択 = ルーレットホイール選択() 
 
クロスオーバー = UniformCrossover(pc=0.8, pe=0.5) 
 
突然変異 = FlipBitMutation(pm=0.1) 
 
  
 
 # 遺伝的アルゴリズムエンジンを作成します。 
 
 # ここでは、すべての組み込み分析をエンジンコンストラクターに渡します。 
 
エンジン = GAEngine(人口 = 人口、選択 = 選択、 
 
                  交差＝クロスオーバー、突然変異＝突然変異、 
 
                  分析=[コンソール出力分析、フィットネスストア分析]) 
 
  
 
 # 適応度関数を定義します。 
 
 @engine.fitness_register 
 
定義フィットネス(indv): 
 
    x, y = 独立変数
 
 y*sin(2*pi*x) + x*cos(2*pi*y) を返します。 
 
  
 
 '__main__' == __name__ の場合: 
 
    エンジンを実行(ng=100)

進化曲線:

2次元関数面:

検索プロセスのアニメーション:

この例から、現在組み込まれている基本演算子は関数のクライマックスを非常にうまく見つけることができることがわかります。

要約する

この記事では主に、遺伝的アルゴリズムの最適化計算用に私が開発した Python フレームワークを紹介します。このフレームワークには、個体、集団、さまざまなエンコード方法を持つ遺伝的演算子など、遺伝的アルゴリズムでよく使用されるコンポーネントが組み込まれています。同時に、このフレームワークはカスタム遺伝的演算子と分析プラグイン用のインターフェースも提供しており、遺伝的アルゴリズムのプロセスを簡単かつ迅速に構築し、アルゴリズムのテストに使用することができます。

現在、このフレームワークはまだ初期段階にあります。今後、私自身が使用していく過程で、より多くの組み込み演算子が徐々に改善され、フレームワークの汎用性が高まります。この記事の両方の最適化例のソースコードは、GitHub (https://github.com/PytLab/gaft/tree/master/examples) にあります。

現在の計画: 1. 組み込み演算子の追加、2. 組み込み演算子とコンポーネントへの C++ バックエンドの追加、3. 並列化

参照する