Javaの遺伝的アルゴリズムクラシファイア：ルールベースのシステム

Question

私は、「カウントするもの」問題への解決策を成功裏に進化させるすべての機能（トーナメント選択、クロスオーバー、突然変異、エリートなど）を持つ遺伝的アルゴリズムをゼロからコード化しました。すなわち、それは、完全に1で満たされるまで、1s& 0からなる2進染色体の無作為に生成された集団を操作する。

ここで、そのアルゴリズムを適用してクラシファイアを作成する必要があります。システムはバイナリデータをクラス "0"またはクラス "1"に分類する必要があります。私は、トレーニングデータのいくつかのセットを持っていますが、ここでは最も基本的なものです：私はルールベースのコンテキストでこのような問題に、私はすでに構築されてきた遺伝的アルゴリズムを適用しに行くかどう

32 rows x 5 variables (+ class, space separated, CR EOL) 00000 0 00001 0 00010 0 00011 1 00100 0 00101 1 00110 1 00111 0 01000 0 01001 1 01010 1 01011 0 01100 1 01101 0 01110 0 01111 1 10000 0 10001 1 10010 1 10011 0 10100 1 10101 0 10110 0 10111 1 11000 1 11001 0 11010 0 11011 1 11100 0 11101 1 11110 1 11111 0

IF×（AND y）THEN z？私はどこから始めるべきかわからないが、私はルール抽出をしなければならないかもしれないと思うが、私はこのような状況でこれを行う方法を知らない。

EDIT：さらにコード

public class Controller { 

public static void main(String[] args) { 
    final int P = 50;     // population size 
    final int N = 32;     // chromosome length 
    final double C = 0.95;    // crossover rate 
    final double M = (double) 1/P; // mutation rate 
    final int G = 50;     // # of generations 

    GA ga = new GA(P, N, C, M); 

    // Initialise population of random individuals 
    Individual[] population = ga.initPop(); 

    // "Counting ones" fitness evaluation 
    System.out.println("GEN0"); 
    ga.evaluatePop(population); 
    ga.printFitness(population); 

    int generation = 1; 
    for (int i = 0; i < G; i++) { 

     System.out.println("\nGeneration: " + generation); 

     // Tournament selection 
     population = ga.tournament(population); 

     // Tournament winners fitness evaluation 
     ga.evaluatePop(population); 

     // Single-point crossover 
     population = ga.crossover(population); 

     // Crossover children fitness evaluation 
     ga.evaluatePop(population); 

     // Bit-wise mutation 
     population = ga.mutate(population); 

     // Post-mutation population fitness evaluation 
     ga.evaluatePop(population); 

     // Elitism replacement (remove the worst gene and replace with a copy of the best) 
     population = ga.elitism(population); 

     // Post-elitism population fitness evaluation 
     ga.evaluatePop(population); 
     ga.printFitness(population); 

     generation++; 

     if (ga.bestFitness(population) == N) { 
      break; 
     } 
    } 
} 

`

public class GA { 

int populationSize; 
int chromosomeSize; 
double crossoverRate; 
double mutationRate; 
Random random = new Random(); 

public GA(int populationSize, int chromosomeSize, double crossoverRate, double mutationRate) { 
    this.populationSize = populationSize; 
    this.chromosomeSize = chromosomeSize; 
    this.crossoverRate = crossoverRate; 
    this.mutationRate = mutationRate; 
} 

public Individual[] initPop() { 
    Individual[] population = new Individual[populationSize]; 
    for (int i = 0; i < populationSize; i++) { 
     population[i] = new Individual(chromosomeSize); 
    } 
    return population; 
} 

public void evaluatePop(Individual[] population) {       
    for (int i = 0; i < population.length; i++) { 
     population[i].evaluate(); 
    } 
} 

public Individual[] tournament(Individual[] population) { 
    Individual[] selectionTemp = new Individual[populationSize]; 
    for (int i = 0; i < population.length; i++) { 

     Individual parent1 = population[random.nextInt(population.length)]; 
     Individual parent2 = population[random.nextInt(population.length)]; 

     if (parent1.getFitness() >= parent2.getFitness()) { 
      selectionTemp[i] = parent1; 
     } else { 
      selectionTemp[i] = parent2; 
     } 
    } 
    population = selectionTemp; 
    return population; 
} 

public Individual[] crossover(Individual[] population) { 
    for (int i = 0; i < population.length - 1; i += 2) { 
     Individual offspring1 = new Individual(population[0].getChromosome().length); 
     Individual offspring2 = new Individual(population[0].getChromosome().length); 

     int xpoint = 1 + random.nextInt(chromosomeSize - 1); 

     if (random.nextDouble() < crossoverRate) { 
      for (int j = 0; j < xpoint; j++) { 
       offspring1.setGene(j, population[i].getGene(j)); 
       offspring2.setGene(j, population[i+1].getGene(j)); 
      } 
      for (int j = xpoint; j < population[0].getChromosome().length; j++) { 
       offspring1.setGene(j, population[i+1].getGene(j)); 
       offspring2.setGene(j, population[i].getGene(j)); 
      } 
     } 
     population[i] = offspring1; 
     population[i+1] = offspring2; 
    } 
    return population; 
} 

public Individual[] mutate(Individual[] population) { 
    for (int i = 0; i < population.length; i++) { 
     for (int j = 0; j < population[i].getChromosome().length; j++) { 
      if (random.nextDouble() < mutationRate) { 
       population[i].mutate(j); 
      } 
     } 
    } 
    return population; 
} 

public Individual[] elitism(Individual[] population) { 
    Individual min = population[0]; 
    int minOffset = 0; 
    for (int i = 0; i < population.length; i++) { 
     if (population[i].getFitness() <= min.getFitness()) { 
      min = population[i]; 
      minOffset = i; 
     } 
    } 
    Individual max = population[0]; 
    int maxOffset = 0; 
    for (int i = 0; i < population.length; i++) { 
     if (population[i].getFitness() >= max.getFitness()) { 
      max = population[i]; 
      maxOffset = i; 
     } 
    } 
    population[minOffset] = population[maxOffset]; 
    return population; 
} 

// <editor-fold defaultstate="collapsed" desc="Debug logic..."> 
public int totalFitness(Individual[] population) { 
    int population_fitness = 0; 
    for (int i = 0; i < population.length; i++) { 
     population_fitness += population[i].getFitness(); 
    } 
    return population_fitness; 
} 

public double avgFitness(Individual[] population) { 
    return (double) totalFitness(population)/population.length; 
} 

public int bestFitness(Individual[] population) { 
    int max = population[0].getFitness(); 
    for (int i = 0; i < population.length; i++) { 
     if (population[i].getFitness() > max) { 
      max = population[i].getFitness(); 
     } 
    } 
    return max; 
} 

    public Individual bestIndividual(Individual[] population) { 
    Individual max = population[0]; 
    for (int i = 0; i < population.length; i++) { 
     if (population[i].getFitness() >= max.getFitness()) { 
      max = population[i]; 
     } 
    } 
    return max; 
} 

public void printFitness(Individual[] population) { 
    System.out.println("Total fitness: " + totalFitness(population)); 
    System.out.println("Average fitness: " + avgFitness(population)); 
    //System.out.println("Best fitness: " + bestFitness(population)); 
    System.out.println("Best individual: " + bestIndividual(population)); 
} 

public void printPop(Individual[] population) { 
    for (int i = 0; i < population.length; i++) { 
     System.out.println(Arrays.toString(population)); 
    } 
} 
// </editor-fold> 

`

public class Individual { 

public int[] chromosome; 
public int fitness = 0; 
Random random = new Random(); 

public Individual(int chromosomeSize) { 
    this.chromosome = new int[chromosomeSize]; 
    for (int i = 0; i < chromosomeSize; i++) { 
     this.setGene(i, random.nextInt(2)); 
    } 
} 

// Initializes individual with a blank chromosome (all genes 0) 
public Individual(int chromosomeSize, boolean isBlank) { 
    this.chromosome = new int[chromosomeSize]; 
    Arrays.fill(chromosome, 0); 
} 

public void mutate(int offset) { 
    if (this.getGene(offset) == 1) { 
     this.setGene(offset, 0); 
    } else { 
     this.setGene(offset, 1); 
    } 
} 

public void evaluate() { 
    int count = 0; 
    for (int offset = 0; offset < this.chromosome.length; offset++) { 
     if (this.getGene(offset) == 1) { 
      count++; 
     } 
    } 
    this.setFitness(count); 
} 

public int getGene(int offset) { 
    return this.chromosome[offset]; 
} 

public void setGene(int offset, int gene) { 
    this.chromosome[offset] = gene; 
} 

public int[] getChromosome() { 
    return chromosome; 
} 

public int getFitness() { 
    return fitness; 
} 

public void setFitness(int fitness) { 
    this.fitness = fitness; 
} 

@Override 
public String toString() { 
    String output = "Binary gene representation: "; 
    for (int i = 0; i < this.chromosome.length; i++) { 
     output += this.getGene(i); 
    } 
    System.out.println(output); 
    System.out.println("Fitness: " + this.getFitness()); 
    return output; 
} 

Answer 1

遺伝的アルゴリズム（GA）は自然淘汰のプロセスに触発メタヒューリスティックあります。 メタヒューリスティックは、サブヒューリスティック、またはサブヒューリスティックの組み合わせまたは並べ替えを検索、生成、または選択するように設計された、より高いレベルの手順またはヒューリスティックとして定義されています。 GAを使用すると、サブヒューリスティックがどのように表示されるか、どのように表示されるかはわかりません。

私はGAメタ遺言フレームワークを開発しましたが、今私はこの特定の問題を解決できるかもしれないサブヒューリスティックを決定して設計する必要があります。私は半分しかやっていないと思う。

これは正しいです。そして今、GAについての第二の重要な理解のために：部分的な成功（サブ解決策または最適ではない解決策）がより良い結果を得るためにさらに改良されるかもしれない問題に最も適しています。

GAは、連続性と局所性がある場合など、数学的な最適化を解決するうえでうまく機能します。たとえば、迷路を解決するには、たとえば、良い部分解が完全な解を試みるためのまともな出発点である場合などです。

残念ながら、特定のケースでは、パリティビットの問題（偶数または奇数の問題）は、最適化問題または明らかに反復的な問題ではありません。それは問題のすべてか何かの問題であり、GAは0または1バイナリ染色体の自然な適合ではありません。

これは、あなたが（たとえば）モジュラスまたはXORを使用して、さまざまな検索規則を作成することができ— GAソリューションを強制することができませんでした意味と非常に迅速に機能するソリューションを進化させていません。しかし、あなたが進化したいと思っていたであろう不可欠な "洞察"（モジュロオペレーションまたはXOR）をハードコーディングして以来、ほとんど浮気を感じています。GAをソリューションに鳩目にする別の方法は、「プログラム的」構文をコード化し、実際には真偽値（バイナリ分類）を出力する小さなプログラム関数bool result = f(x)を展開する「遺伝子」を開発することです。しかし、これは文法などの複雑さを増やし、STGP（強タイピング遺伝プログラミング）領域で終わる可能性が高く、そこに住むネイティブは厳密な時間的税金を渡す彼らの土地は準備ができていない。

パリティの問題に対する私のアドバイス：自分自身を神経網だけで下ろしてください。彼らはセクシーでも普遍的でもありませんが、あなたがカンニングをしたり、もっと多くの仕事（STGP）をする必要なく、仕事を終わらせます。十分な数のノードを有するニューラルネットがXORを、したがってパリティを学習できることはよく知られている。

編集：

GA学校の割り当てとしてこれを分類整理するために、私は、デジタル・ゲートスタイルのアプローチを取ってお勧めします。バイナリ染色体スキームから3進染色体スキーム（既にint[] chromosome宣言を使用しているので、余分なコーディングを必要としない）に移行する必要があります。各トリット（三元桁）は、次のルックアップルールのコード可能性：所与の入力ビットパターンB[]について

1: prior State AND B[next] 
2: prior State OR B[next] 
3: NOT 

、三染色体は初期で、ビット毎ベースで左から右に評価することができStateの変数0（ここで、Stateは評価関数内の内部変数）と、連続する各トリット間で発生する暗黙のAND演算（NOT型を除く）です。 bool（

((!(!(prior State | B[next]))) & (prior State & B[next])) 

StateとB[next]が少し明らかにしている。したがって、たとえば、あなたが（各入力ビットに対して一度適用される）あなたの評価関数に次の一連の操作を表すことになり三元ソリューション2, 3, 3, 1を、進化想像）変数。中間付近のAND演算は、NOT型でない任意のトリット間で発生すると定義した暗黙のAND演算に由来することに注意してください。したがって、たとえば、次のようになり2, 3, 3, 1の例題の染色体に対する評価関数を介して実行入力ビット列100は次のとおりです。

1. State = 0 
2. B[next] = 1, State = ((!(!(0 | 1))) & (0 & 1)) = 0 
3. B[next] = 0, State = ((!(!(0 | 0))) & (0 & 0)) = 0 
4. B[next] = 0, State = ((!(!(0 | 0))) & (0 & 0)) = 0 
5. Return final State value (0 here) from evaluation function. 

あなたが任意にさえ意味する0の結果を定義し、1の結果に可能性あなたが好きなら、奇妙なことを意味するGAは染色体の終わりに追加のNOT tritで結果を逆転させることを簡単に学ぶことができるので、選択は重要ではありません。

この評価関数の優れた点は、ビットごとにローリング方式で適用され、ビット列全体の長さに関わらず、任意の長い入力ビット列を処理できることです。そして、我々は理論的には正しい解決策を進化させることができることを知っています。A XOR B = (A OR B) AND (NOT (A AND B))であり、XORはパリティに必要なすべてです。

これを行うには、可変長の解決法（可変長進化トリット配列）を許可する必要がありますが、合理的な上限（例えば15トリット程度）で染色体をキャップして、ずっと長いソリューションで狂っている。これを実現するために必要なもう1つのこと：多くの入力ビットストリングのバッチ評価に基づいてのスコアリング。入力ビット列の評価関数の出力は0または1なので、結果は100％正解または0％正解になります。これはそれ自体で有用なフィットネススコアリングを許可していません。なぜなら、約半分が100％正確で残りの半分が0％になるので、異なるトリートシーケンス（ソリューション）を比較的ランク付けする良い方法がないからです。しかし、解決策は簡単です。正確にラベル付けされたすべての入力文字列の％で各トリットシーケンスをスコアリングするだけです。したがって、データセットに100ビットの入力ビット列があり、ソリューション1では入力ビット列の57％が正しくラベル付けされていますが、ソリューション2では49％の入力しか正しく表示されません。突然変異、エリート生存などのために使用されます。