2

我从头开始编写了一个具有所有功能（比赛选择、交叉、突变、精英等）的遗传算法，它成功地发展了解决“计数”问题的方法——即它操纵随机生成的由 1 组成的二元染色体群体& 0s，直到达到一个充满 1s 的完美。

现在我需要应用该算法并创建一个分类器。系统应将二进制数据分类为“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 x (AND y) THEN 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;
}
4

1 回答 1

1

遗传算法 (GA) 是一种受自然选择过程启发的元启发式算法。元启发式定义为更高级别的过程或启发式，旨在查找、生成或选择子启发式，或子启发​​式的组合或排列。使用 GA 本身并不能告诉您子启发式应该如何或是什么样的。因此，您可以将当前的实现重新表述为：

我已经开发了一个 GA 元启发式框架，但现在我需要确定和设计可能允许我解决这个特定问题的子启发式。我想我只完成了一半。

这是正确的。现在对于关于 GA 的第二个重要理解：它们最适用于部分成功（子解决方案或非最佳解决方案）可能被进一步细化以获得更好结果的问题。

GA 可以很好地解决数学优化问题，例如，在经常存在连续性和局部性的情况下。或者解决一个迷宫，例如，一个好的部分解决方案绝对是尝试完整解决方案的一个不错的起点。

不幸的是，在您的特定情况下，奇偶校验位问题（偶数或奇数问题）不是优化问题或明显的迭代问题。这是一个全有或全无的问题，遗传算法不是与一条0或1二元染色体的自然契合。

这并不意味着您不能强制使用 GA 解决方案——您可以创建各种使用模数或 XOR（例如）的查找规则，并很快开发出可行的解决方案。但这几乎感觉像是在作弊，因为您硬编码了您希望发展的基本“洞察力”（模运算或 XOR）。在这里将 GA 归类为解决方案的另一种方法是开发“基因”，该“基因”为“程序化”语法编码，并实际上演变出一个小程序功能bool result = f(x)，该功能将输出真或假值（您的二进制分类）。但这增加了很多复杂性，例如语法等，

我对奇偶校验问题的建议：降低自己，只使用神经网络。它们并不那么性感或普遍，但它们会完成工作，而不需要你作弊或做更多的工作（STGP）。众所周知，具有足够数量节点的神经网络可以学习异或，从而学习奇偶校验。

编辑：

要将其归类为 GA 学校作业，我建议采用数字门式方法。您需要从二元染色体方案转移到三元染色体方案（这应该不需要额外的编码，因为您已经使用了int[] chromosome声明）。然后每个trit（三进制数字）可以为以下查找规则编码：

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

对于给定的输入位模式B[]，三元染色体可以在每个位的基础上从左到右进行评估，初始State变量为0（其中State是评估函数内部的内部变量），并且在每个连续的三元组之间发生隐式与运算（NOT 类型除外）。因此，例如，假设您改进了三元解决方案2, 3, 3, 1，它将表示评估函数中的以下操作序列（对每个输入位应用一次）：

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

其中State和B[next]显然是位 ( bool) 变量。请注意，中间附近的 AND 操作来自我们定义的隐式 AND 操作，该操作发生在任何非 NOT 类型的三元组之间。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 的结果表示奇数。选择并不重要，因为 GA 可以很容易地学会在染色体末端添加一个额外的 NOT trit 来反转结果。

这个评估函数的好处是它可以处理任意长的输入位串，因为它仅以滚动方式应用于每个位，而不关心整体位串长度。而且我们知道它理论上可以演化出一个正确的解决方案，因为A XOR B = (A OR B) AND (NOT (A AND B))奇偶校验只需要 XOR。

为了使它起作用，您将必须允许可变长度的解决方案（可变长度进化的 trit 序列），但将染色体限制在一个合理的上限（比如 15 个 trit 左右）以防止 GA 永远疯狂-更长的解决方案。为了使它起作用，您还需要做另一件事：基于对许多输入位字符串的批量评估进行评分。因为任何输入位串的评估函数的输出只是0或1，结果将是 100% 正确或 0% 正确。这本身并不允许有用的适应度评分，因为您没有比较好的方法来对不同的 trit 序列（解决方案）进行排名，因为大约一半是 100% 正确的，另一半是 0%。但解决方案很简单：只需根据正确标记的所有输入字符串的百分比对每个 trit 序列进行评分。因此，如果您的数据集中有 100 个输入位串，并且解决方案 1 正确标记了 57% 的输入位串，而解决方案 2 仅正确标记了 49% 的输入，那么现在您有一个很好的方法来对解决方案群体进行排名并选择用于基因交叉、突变、精英生存等。

于 2016-11-20T22:11:18.380 回答