java - Java中的遗传算法分类器:基于规则的系统

Question

我从无到有地编写了一个具有所有特征（竞赛选择、交叉、变异、精英主义等）的遗传算法，它成功地解决了“计数一个”的问题，也就是说，它操纵由1和0组成的随机生成的二元染色体群，直到达到一个充满1的完美种群。
现在我需要应用该算法并创建一个分类器。系统应将二进制数据分类为类“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
如果x（和y）然后z的形式是基于规则的上下文，我将如何应用我已经构建的遗传算法来解决这样一个问题？我不知道从哪里开始，我想我可能需要做一些规则提取，但我不知道如何在这种情况下进行。
编辑：进一步的代码

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元启发式框架，但是现在我需要确定和设计子启发式，使我能够解决这个特殊的问题我想我只完成了一半。
没错现在，关于气体的第二个重要的理解是：它们最好应用于部分成功（子解或非最优解）可以进一步改进以获得更好结果的问题。
例如，在通常具有连续性和局部性的情况下，天然气可以很好地解决数学优化问题或者解决一个迷宫，例如，一个好的部分解决方案绝对是尝试完整解决方案的一个不错的起点。
不幸的是，在您的特殊情况下，奇偶校验位问题（偶数或奇数问题）不是一个优化问题，也不是一个明显的迭代问题。这是一个全有或全无的问题，遗传算法与一个0或1二元染色体并不自然匹配。
这并不意味着你不能强制一个GA解决方案，你可以创建使用模或异或（例如）的各种查找规则，并非常迅速地发展出一个可行的解决方案但这几乎感觉像是作弊，因为你硬编码的基本“洞察”（模运算或异或），你会喜欢演变另一种将遗传算法归为一个解决方案的方法是开发“基因”来编码“编程”语法，并实际进化出一个小的程序函数bool result = f(x)，它将输出一个真值或假值（二进制分类）。但是这增加了很多的复杂性，比如语法等等，你很可能最终会出现在STGP（强类型遗传编程）领域，你应该知道，住在那里的土著人会对你没有准备好通过他们的土地而征收一个沉重的时间税。
我对奇偶性问题的建议是：把自己降低到只使用一个神经网络他们不太性感或普遍，但他们会完成工作，而不需要你要么欺骗或做更多的工作（stgp）。众所周知，具有足够节点数的神经网络可以学习异或，从而实现奇偶校验。
编辑：
为了将此作为GA学校作业进行分类，我建议采用数字门样式的方法您将需要从二进制染色体方案转移到三元染色体方案（由于您已经使用了int[] chromosome声明，因此不需要额外编码）。然后，每个trit（三位数字）可以为以下查找规则编码：

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

对于给定的输入位模式 B[]，三元染色体可以按位从左到右进行评估，初始 State变量为 0（其中 State是评估函数内的一个内部变量）和每个连续trit之间发生的隐式and操作（非类型除外）。因此，例如，假设您进化了三元溶液 2, 3, 3, 1，它将表示求值函数中的以下操作序列（对每个输入位应用一次）：

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

其中 State和 B[next]显然是位（ bool）变量。注意，中间附近的and操作来自我们定义的隐式and操作，它发生在任何非not类型的trit之间。例如，当对我们的示例染色体 100运行求值函数时，输入位字符串 2, 3, 3, 1如下所示：

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表示奇数这个选择并不重要，因为遗传算法可以很容易地学会在染色体末端附加一个非trit基因来反转结果。
这个求值函数的好处是它将处理任意长的输入位字符串，因为它只以滚动方式应用于每一位，而不关心整个位字符串的长度。我们知道理论上它可以演化出一个正确的解，因为 A XOR B = (A OR B) AND (NOT (A AND B))和xor是奇偶性所需要的全部。
为了实现这一点，你必须允许可变长度的解决方案（可变长度进化的trit序列），但要将染色体限制在一个合理的上限（比如15 trit左右），以防止遗传算法疯狂地使用更长的解决方案还有一件事你需要做，以便这项工作：评分的基础上批量评估许多输入位字符串。因为任何输入位字符串的求值函数的输出只是 0或 1，所以结果要么是100%正确，要么是0%正确。这本身不允许有用的适应度评分，因为你没有好的方法来对不同的trit序列（解决方案）进行排序，因为大约一半是100%正确的，另一半是0%但解决方法很简单：只需在正确标记的所有输入字符串的%上对每个trit序列进行评分。因此，如果您的数据集中有100个输入位字符串，并且解决方案1正确地标记了57%的输入位字符串，而解决方案2正确地标记了49%的输入，那么现在您有了一个很好的方法来排列您的解群，并为遗传交叉、变异、精英生存等进行选择。