EvoJ-遺伝的アルゴリズムの便利なフレームワーク

こんにちは同僚！



遺伝的アルゴリズムのトピックに関する記事がしばしばここに表示されますので、5セントにしましょう。



ここ数年、趣味としてGA専用のJavaフレームワークEvoJを開発しています。 私が最初にGAを使い始めたとき、最大の不便はソリューションを構成する変数をベクトル化する必要があることでした。そこで、私のフレームワークでは、変数のベクトル化をプログラマーに意識させず、すべての汚い仕事をフレームワークの肩にかけようとしました。 さらに、GAは非常によく並列化できるので、マルチスレッドへの移行も簡単にしようとしました。



EvoJの基本的な考え方を理解するために、次の例を検討してください。 簡単にするために、関数Z(x, y)=12 * x^2 + 8 * x + 9 * y^2.



の最小値を見つける必要があると仮定しますZ(x, y)=12 * x^2 + 8 * x + 9 * y^2.



当然、この問題はGAに頼ることなくより効果的に解決できますが、まずそれを見てみましょう。次に、EvoJの完全なパワーを明らかにする例を分析します。



そのため、まず、必要な変数を含むJavaインターフェイスを作成する必要があります。 XとYの2つの変数があり、これらの変数のゲッターを含むインターフェイスを作成します。

 public interface Solution { @Range(min = "-10", max = "10") double getX(); @Range(min = "-10", max = "10") double getY(); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

セッターは宣言する必要がないことに注意してください; EvoJはセッターなしで変数を変更できます。 ただし、独自の突然変異戦略を実装する場合は、セッターを宣言する必要があります。そうしないと、自分で変数を変更できません。



@Range



アノテーションに注意して@Range



。これは、変数が取ることができる値の範囲を設定します。 変数は、指定された範囲のランダムな値によってトリガーされます。 ただし、突然変異の結果として、指定された範囲を超える可能性があります。 これは、setterメソッドを使用して設定しようとしても、変数が無効な値を受け入れることを許可しないstrict=”true”



パラメーターを使用することで防止できます。



ここで注意する必要があるもう1つの点は、EvoJのすべての注釈のパラメーターはすべて文字列であるため、パラメーター値を直接指定するか、特定の値ではなくnameプロパティを指定できるため、コンパイル時に注釈パラメーターの値をハードコーディングしないようにします。時間。



それで、変数を持つインターフェースがあります。フィットネス関数を書きましょう。 EvoJのフィットネス機能は、インターフェイスによって表示されます。

 public interface SolutionRating<T> { Comparable calcRating(T solution); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで、パラメーターT



は変数とのインターフェイスです。 （ Comparable



契約による）戻り値が高いほど、ソリューションの適応度が高くなります。 null



を返すことができnull



。これは最小のフィットネス関数値と見なされます。



一部のサービス機能を引き受けるヘルパークラスを介して、このインターフェイスを間接的に実装することをお勧めします：古いソリューションの破棄（ソリューションの最大有効期間が指定されている場合）、以前のGA反復で削除されなかったソリューションの関数値のキャッシュ。



このケースのフィットネス関数は次のようになります。

 public class Rating extends AbstractSimpleRating<Solution> { public static double calcFunction(Solution solution) { double x = solution.getX(); double y = solution.getY(); return 12 * x * x + 8 * x + 9 * y * y; } @Override public Comparable doCalcRating(Solution solution) { double fn = calcFunction(solution); if (Double.isNaN(fn)) { return null; } else { return -fn; } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここではすべてが明らかです。最初のインターフェイスの変数を使用して関数を取得し、カウントします。 最小値を探しており、クラスコントラクトは最高のソリューションの評価が高いと想定しているため、関数の値-1を返します。



さらに、左の決定（NaNが判明した場合）を除外してnull



返しnull



。



さて、2つの主要なコンポーネントがあります。すべてを機能させましょう。

 DefaultPoolFactory pf = new DefaultPoolFactory(); GenePool<Solution> pool = pf.createPool(200, Solution.class, null); DefaultHandler handler = new DefaultHandler(new Rating(), null, null, null); handler.iterate(pool, 200); Solution solution = pool.getBestSolution();
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

上記のコードを行に解析してみましょう：

 DefaultPoolFactory pf = new DefaultPoolFactory();
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このファクトリは多くの初期ソリューションを提供します。覚えているなら、ソリューションはクラスではなくインターフェイスで表されているため、独自にインスタンスを作成することはできません。

 GenePool<Solution> pool = pf.createPool(200, Solution.class, null);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここでは、200のランダムソリューションの集団（遺伝子プール）が作成されます。 最後のパラメーターに注意してください-注釈パラメーターを明示的に指定しなかった場合、ここにプロパティの値を持つMap<String, String>



を指定する必要があります。

 DefaultHandler handler = new DefaultHandler(new Rating(), null, null, null);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ハンドラーは、遺伝的アルゴリズムの具体化であり、突然変異、交配、選択および評価戦略の組み合わせです。 これらのうち、評価の計算のみを独自に実装する必要があります。残りには、対応するパラメーターの代わりにnull



渡された場合に使用される標準実装があります。

 handler.iterate(pool, 200);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この行は、母集団に対してGAの200回の反復を実行します。 タスクはかなり原始的であるため、関数の最小値を見つけるには200回の反復で十分です。 （より複雑なタスクのソリューションを見つけるには、数時間と数百万回の反復が必要になる場合がありますが、幸いなことに、マルチスレッドを使用してソリューションの選択を高速化できます。

 Solution solution = pool.getBestSolution();
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここでは、最適なソリューションが見つかります。 このインターフェイスのインスタンスで、 getX()/getY()



を自由に呼び出しgetX()/getY()



、 getX()/getY()



いる変数の値を取得できます。

ソリューションがあなたに合わない場合、ソリューションの望ましい品質が達成されるまでGAの反復を続けることができます。



したがって、EvoJを使用して問題を解決するには、次のものが必要です。

1. 変数を使用してインターフェイスを作成する
2. フィットネス機能のインターフェースを実装する
3. ソリューションの母集団を作成し、上記のコードを使用して必要な数のGA反復を実装します

さて、これはウォームアップでしたが、EvoJが実際にできることを見てみましょう。



限られたポリゴンのセットでフルカラー画像を近似したいとします。 このような問題の解決策は、単純な変数を備えた単一のインターフェースでは説明できません。これは、EvoJの全機能が発揮される場所です。 次のインターフェイスセットを宣言できます。

 public interface PolyPicture { @ListParams(length = "50") List<Polygon> getPolygons(); } public interface Polygon { Colour getColor(); @ListParams(length = "8") List<Point> getPoints(); } public interface Point { @Range(min = "-5", max = "325", strict = "true") float getX(); @Range(min = "-5", max = "245", strict = "true") float getY(); void setX(float x); void setY(float y); } public interface Colour { @MutationRange("0.2") @Range(min = "0", max = "1", strict = "true") float getRed(); @MutationRange("0.2") @Range(min = "0", max = "1", strict = "true") float getGreen(); @MutationRange("0.2") @Range(min = "0", max = "1", strict = "true") float getBlue(); void setRed(float red); void setGreen(float green); void setBlue(float blue); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

インターフェイスの上部には全体像があり、単一のプロパティ-ポリゴンのリストで構成されています。 各ポリゴンは、色と点のリストです。 ポイントは2つの座標、色は3つのコンポーネントです。



新しいアノテーションのうち、 @ListParams



リストの長さやその他のプロパティを指定すること、および@MutationRange



変数の突然変異の最大半径を指定すること、つまり、 1回の突然変異で変数がどれだけ変化するか。

また、色成分を記述する変数の値の範囲が固定されていることに注意してください（ strict=”true”



）。



次に、前回ヘルパークラスを拡張して行ったように、フィットネス関数を実装する必要があります。 以下に、スペースを節約するために、不完全なクラスコードを示します（元のコードはマルチスレッド用に設計されており、読みにくくなる多くの明白でない最適化が含まれています）。

 public class PictureRating extends AbstractSimpleRating<PolyPicture> { public PictureRating(BufferedImage originalImage){....} @Override protected Comparable doCalcRating(PolyPicture picture) { BufferedImage testImage = drawPicture(picture); int[] originalPix = getPixels(originalImage); int[] testPix = getPixels(testImage); return -calcError(originalPix, testPix); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで、インターフェイスで記述された画像を描画し、そのピクセルを取得して、元の画像のピクセルと比較します。 結果として、マイナス記号付きの累積偏差を返します（エラーが多い-悪い解、エラーが少ない-より良い解）。



次に、最小限の関数を探していた例に似たコードを書きます。

 DefaultPoolFactory factory = new DefaultPoolFactory(); GenePool<PolyPicture> pool = factory.createPool(40, PolyPicture.class, null); DemoRating rating = new DemoRating(PICTURE_TO_APPROXIMATE); MultithreadedHandler handler = new MultithreadedHandler(2, rating, null, null, null); handler.iterate(pool, 1000); handler.shutdown();
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

違いが1つありますMultithreadedHandler



です。 単純なハンドラーとは異なり、複数のスレッドのソリューションの集合に対してGAを反復します（スレッドの数は、コンストラクターの最初のパラメーターで指定されます）。 したがって、プロセッサに複数のコアがある場合、スレッドの数を増やすだけで、ソリューションの検索を本当に高速化できます。 たとえば、8つのスレッドでハイパースレッディングが有効になっているCore i7での画像近似の考慮された問題に対する許容可能な品質のソリューションは、15〜20分です。

EvoJのマルチスレッドコードは、ロックを最小限に抑えるように記述されているため、スレッド数の増加に伴ってパフォーマンスがほぼ線形に向上します（最大のパフォーマンスを得るには、母集団内の個人の数がスレッドの数の倍数である必要があります。そうでない場合、十分なタスクがありません）。



まだラインに注意を払う価値があります

 handler.shutdown();
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

保留中のエグゼキュータースレッドを完了するために必要です。



EvoJについてお伝えしたかったのはそれだけです。 要約として、EvoJの主な機能を説明します。

• 変数を独立してベクトル化する必要はありません。ドメインドメインの観点からコードをすぐに書くことができます。
• メインのGA戦略の標準的な実装（育種、交配、突然変異）
• 宣言的突然変異制御（注釈）
• すぐに使えるマルチスレッド
• 小さいサイズ（120 kb）および外部依存関係なし（はい、1つのjarファイルのみが必要です）
• 任意の時点での拡張性（選択、交差、突然変異など、GA戦略の独自の実装を作成できます）

興味がある場合は、次のようにEvoJをMavenプロジェクトに追加できます。

• まず、リポジトリにリンクを追加する必要があります（まだ中心的なものをレイアウトしていません）

 <repositories> <repository> <id>EvojHome</id> <name>EvoJ</name> <url>http://evoj-frmw.appspot.com/repository</url> </repository> </repositories>
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

• その後、直接中毒

 <dependency> <groupId>net.sourceforge.evoj</groupId> <artifactId>evoj</artifactId> <version>2.1</version> </dependency>
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Mavenと友達でない人は、プロジェクトのWebサイトhttp://evoj-frmw.appspot.com/からEvoJを直接ダウンロードできます。 また、英語のこのチュートリアルのコピー、詳細な技術ガイド、さまざまなタスク（画像近似、ニューラルネットワークのトレーニング）にEvoJを使用した結果もあります。



ご清聴ありがとうございました。 ご質問にお答えします。



UPD：以下は、近似によって得られるものの例です

ソース画像	一致した画像