遺伝的アルゴリズム。 理論から実践へ

こんにちは 最近、私は独学をすることにしました。 遺伝的アルゴリズムから始めることにしました。

GAの注目すべき特性の1つは、選択、交差、および突然変異の手順が世代の個体について何も知らないことです。それらは0と1のみです。これらの0と1が何であるかを知る唯一の関数は-これはフィットネス機能です。

したがって、すべてのGAにワイヤフレームクラスを作成するとよいと判断しました。 これがこの記事の目的です。 遺伝的アルゴリズムの基礎をすでに理解していることを前提としています。

おもしろい人には猫の下でお願いします。


コードはJavaで記述されます。

ワイヤフレームを作成しているという事実にもかかわらず、テストする必要があります。 このために、私は古典的なNP完全問題、つまり巡回セールスマン問題を取り上げました。

アプリケーションアーキテクチャについて少し：

ゲノム（個々）を表すために、長い[]を使用します。 何らかの理由で、このオプションはブール[]よりも良いように思えました。

インターフェースも必要です。

public interface FitnessFunction { int getArity(); //-    long run(long[] genom); //    . } 

開発中のクラス：

 public class GeneticEngine{ public GeneticEngine(FitnessFunction fitnessFunction) {...} // public long[] run() {...} //  private void generateFirstGeneration() {...} //   private void selection(){...} //  private void crossing() {...} //  private void mutation() {...} //  } 

「ユニバーサル」クラスを作成しているため、異種交配および選択のさまざまなバリアントをサポートする必要があります。したがって、2つの列挙型が追加されました（列挙型）。

 public enum SelectionType { TOURNEY, ROULETTE_WHEEL } public enum CrossingType { ONE_POINT_RECOMBINATION, TWO_POINT_RECOMBINATION, ELEMENTWISE_RECOMBINATION, ONE_ELEMENT_EXCHANGE } 

...およびいくつかのプライベートフィールド：

 private int genomLength; //    private long generationCount; //-  private int individualCount; //- (,)   private SelectionType selectionType; //  private CrossingType crossingType; //  private boolean useMutation; //  private double mutationPercent; //    

それらにはセッターとゲッターがあります。

そして今、まず最初に...

第一世代。

すべてが非常に単純です：ランダムにロングを生成し、ロングからゲノムを構成し、それらを配列に入れます。 コードは提供しません。

セレクション

2種類の選択が見つかりました。

• ルーレット盤
• トーナメント

選択手順により、ゲノムの新しい配列が作成されます。

 private void selection(){ switch (selectionType) { case ROULETTE_WHEEL:{ float[] wheel = new float[this.individualCount]; wheel[0] = //   1-  for (int i=1;i<this.individualCount;i++){ wheel[i] = wheel[i-1] + //   i-  } float all = wheel[this.individualCount-1]; for (int i=0;i<this.individualCount;i++){ float index = Math.abs(this.random.nextFloat())*all; int l = 0; int r = individualCount-1; int c = 0; while (l < r){ c = (l+r) >> 1; if (index <= while[c]){ r = c; }else{ l = c + 1; } } this.genomListOffsprings[i] = this.genomListParents[l].clone(); } break; } case TOURNEY:{ for (int i=0;i<this.individualCount;i++){ int index1 = random.nextInt(individualCount); int index2 = random.nextInt(individualCount); long fr1 = //   index1  long fr2 = //   index2  this.genomListOffsprings[i] = fr1 > fr2 ? this.genomListParents[index1].clone() : this.genomListParents[index2].clone(); } break; } } 

「自分で」いくつかのコメント：

• テスト中に、実行されたフィットネス機能のほとんど（時間の約90％）が判明しました。
• 各世代の関数の結果のキャッシュを使用して、アルゴリズム全体のパフォーマンスを3〜4倍向上させることができました。
• 上記の2つのポイントにより、ルーレットはトーナメントよりもはるかに悪いアルゴリズムであることが判明しました。

交配。

交差が起こります：

• シングルポイント組換え。
• ポイントツーポイント組換え。
• エレメンタル交配。
• 単一の遺伝子を共有する。

「自分で」いくつかのコメント：

• テスト中、要素ごとの交配が最も効果的であることが判明しました。 残りの3つのアルゴリズムには同じ「ユーティリティ」があります。
• （明らか） 1つの遺伝子の交換はO（1）で機能し、残りのアルゴリズムはO（L）で機能します。ここで、lはゲノムの長さです。
• 前の段落にもかかわらず、4つのアルゴリズムはすべてほぼ同じ時間 （つまり時間）で動作します。 より正確には：フィットネス関数はGAの動作時間全体の90％を占めます。その背景に対して、O（1）とO（L）は交差に相当します。
• 前の3つの点から、要素交差は最適な交差アルゴリズムであると考えています（信じています）。

*交配と突然変異の機能については、二項演算を使用しました。 したがって、いくつかの静的変数を宣言する必要がありました。

 public static final int OCTET_LENGTH = 64; // -    public static final int MASK_FOR_MOD = OCTET_LENGTH - 1; //  "x%64"   "x & MASK_FOR_MOD" public static final int SHIFT_FOR_DIVISION; //  "x/64" - "x >> SHIFT_FOR_DIVISION" 

2つのゲノムを交差させる機能：
（表示されているコードはビットワイズクロッシング専用です）

 private void cross(long[] genom1, long[] genom2) { switch (crossingType) { ... case ELEMENTWISE_RECOMBINATION:{ for (int outerOffset = 0; outerOffset < this.sizeOfArray; outerOffset++) { long mask = this.random.nextLong(); //   ,    (1- , 0-) long swapMask = (genom1[outerOffset] ^ genom2[outerOffset]) & mask; genom1[outerOffset] ^= swapMask; genom2[outerOffset] ^= swapMask; } break; } } 

説明：
番号aとbを相互に交換するには、以下を行う必要があります。
swapMask = a xor b;
a = a xor swapMask;
b = b xor swapMask;

そして、swapMaskにマスク（および）を課すと、aとbはマスク番号の== 1のビットのみを変更します。

swapMask =（a xor b）およびマスク。
a = a xor swapMask;
b = b xor swapMask;

突然変異。

 private void mutation() { for (long[] genom : this.genomListOffsprings) { if (random.nextDouble() <= mutationPercent) { mutate(genom); } } } private void mutate(long[] genom) { int index = this.random.nextInt(this.genomLength); int outerOffset = index >> SHIFT_FOR_DIVISION; int innerOffset = (index & MASK_FOR_MOD); long mask = 1L << innerOffset; genom[outerOffset] ^= mask; } 

少し反転させるには、以下を行う必要があります。
ビット=ビットxor 1;
したがって、数字のビットを反転するには、ユニットを目的の位置に移動する必要があります。

「体」

そして、前のものすべてをリンクするメイン関数：

 public long[] run() { generateFirstGeneration(); while (currentGeneration < generationCount) { selection(); this.crossing(); if (useMutation) { mutation(); } currentGeneration++; } return . } 

アプリケーション。

すべてを使用するのは非常に簡単です。
最初に、FitnessFunctionsクラスを記述する必要があります。
そして...

 MyFitnessFunction ff = new MyFitnessFunction(); GeneticEngine ge = new GeneticEngine(ff); ge.setIndividualCount(1000); // -    ge.setGenerationCount(10000); // -  ge.setSelectionType(SelectionType.TOURNEY); //  ge.setCrossingType(CrossingType.ELEMENTWISE_RECOMBINATION); //  ge.setUseMutation(true); //    ge.setMutationPercent(0.02d); //    long[] better = ge.run(); // 

巡回セールスマンの問題に戻りましょう。

都市間の距離はrandom.nextInt（256）で埋められたため。 2つの都市間の平均距離= 128であることをお勧めします。=>すべての都市のルートの平均の長さ= 128 * 256 = 32768。 （！私は間違っている可能性があります）。

で

 IndividualCount = 100; GenerationCount = 10000; SelectionType = SelectionType; CrossingType = ELEMENTWISE_RECOMBINATION; UseMutation = true; MutationPercent = 0.02d; 

GAは6〜7秒間、パス= 10000-12000を見つけます。 これは平均の3倍です。

で

 IndividualCount = 1000; GenerationCount = 10000; 

1分あたり5500〜7000。

で

 IndividualCount = 10000; GenerationCount = 100000; 

コードは約15時間実行されます。 ルート= 3500-4000を見つけます。

さらに成長する場所。

• 知識のある人がルーレットを実装する最善の方法を教えてくれることを願っています。
• 世代数ではなく、フィットネス関数の値に到達した後、または世代のフィットネス関数の平均値の差が小さくなったときにGAを停止できます。
• すべての世代に最適なフィットネス機能を持つ個人を保存できます。 またはすべての世代のためではなく、フィットネス関数が計算された個人からのみ-これは高価ではありません。

GitHubへのリンク。 誰かが重宝してくれたら嬉しいです。

UPD：コードはJavaで記述されていますが、java.utilを使用せずに記述しようとしたため、Cのように見えました。
この側面の理由は何ですか：

• データを保存するときにオーバーヘッドは発生しません。
• コードは、C / C ++ / php / Cに似た言語で簡単に移植可能になります。
• パフォーマンスを損なうことはありません（多分少し増えます）。
• コードが読みにくくなることはありません。

（コメントでは、コードはS-shnyと混同されていたため、このタスクは完了したと考えています）

UPD2： LeoCcoderがルーレット（バイナリ検索）でエラーを検出しました。 修正済み。