需要帮助查明Java遗传算法单点交叉机制中的问题 [英] Need help pinpointing issue in Genetic Algorithm Single-Point Crossover Mechanism in Java

问题描述

我一直在使用Java实现简单的遗传算法(GA).我的GA的步骤基本上是二进制编码，锦标赛选择，单点交叉和按位突变.人口中的每个人都由一类由二进制基因和适应度值组成的类代表.

I have been implementing a simple genetic algorithm(GA) using Java. The steps of my GA are basically binary encoding, tournament selection, single-point crossover, and bit-wise mutation. Each individual of the population is represented by a class consisting of binary genes and a fitness value.

public class Individual {
    int gene[];
    int fitness;

    public Individual(int n){
        this.gene = new int[n];
    }
}

下面的代码不包括按位突变部分，因为我在GA的单点交叉部分遇到了问题.我实现单点交叉算法的方式是，随机找到两个连续的单个数组元素的点，然后交换它们的尾巴.然后，对每对个人重复尾部交换.我还创建了printGenome()方法，以打印出所有要比较的数组，交叉处理后的结果数组未正确交换.我已经分别测试了我的单点交叉算法，它可以工作.但是，当我尝试在下面的代码中运行它时，交叉功能根本无法正常工作.我是否知道是因为比赛选择"算法存在问题?还是其他东西(愚蠢的错误)?我一直在进行修改，但仍然无法查明错误.

The codes below does not include the bit-wise mutation part as I have been facing problem at the single-point crossover part of the GA. The way I have implemented the single-point crossover algorithm is by randomly finding a point for two consecutive Individual array elements and then swap their tails. The tail swapping is then repeated for each pair of Individual. I have also created the printGenome() method to print out all the arrays to compare, the resulting array after the crossover process is not properly swapped. I have tested my single-point crossover algorithm separately, it works. However when I tried to run it here in the codes below, the crossover simply does not work. May I know is it because there is something wrong within the Tournament Selection algorithm? Or is it something else(silly mistakes)? I have been reworking on it and still I could not pinpoint the error.

对于提供的任何帮助和信息，我将不胜感激！ :)

I would be grateful for any help and information provided! :)

public class GeneticAlgorithm {

    public static void main(String[] args) {
        int p = 10;
        int n = 10;
        Individual population[];

        //create new population
        population = new Individual[p];

        for (int i = 0; i < p; i++) {
            population[i] = new Individual(n);
        }

        //fills individual's gene with binary randomly
        for (int i = 0; i < p; i++) {
            for (int j = 0; j < n; j++) {
                population[i].gene[j] = (Math.random() < 0.5) ? 0 : 1;
            }
            population[i].fitness = 0;
        }

        //evaluate each individual
        for (int i = 0; i < p; i++) {
            for (int j = 0; j < n; j++) {
                if (population[i].gene[j] == 1) {
                    population[i].fitness++;
                }
            }
        }

        //total fitness check
        System.out.println("Total fitness check #1 before tournament selection: " + getTotalFitness(population, p));
        System.out.println("Mean fitness check #1 before tournament selection: " + getMeanFitness(population, p));
        System.out.println("");

        //tournament selection
        Individual offspring[] = new Individual[p];

        for (int i = 0; i < p; i++) {
            offspring[i] = new Individual(n);
        }

        int parent1, parent2;
        Random rand = new Random();
        for (int i = 0; i < p; i++) {
            parent1 = rand.nextInt(p); //randomly choose parent
            parent2 = rand.nextInt(p); //randomly choose parent

            if (population[parent1].fitness >= population[parent2].fitness) {
                offspring[i] = population[parent1];
            } else {
                offspring[i] = population[parent2];
            }
        }

        //total fitness check
        System.out.println("Total fitness check #2 after tournament selection: " + getTotalFitness(offspring, p));
        System.out.println("Mean fitness check #2 after tournament selection: " + getMeanFitness(offspring, p));
        System.out.println("");

        //genome check
        System.out.println("Before Crossover: ");
        printGenome(offspring, p, n);

        //crossover
        for (int i = 0; i < p; i = i + 2) {
            int splitPoint = rand.nextInt(n);
            for (int j = splitPoint; j < n; j++) {
                int temp = offspring[i].gene[j];
                offspring[i].gene[j] = offspring[i + 1].gene[j];
                offspring[i + 1].gene[j] = temp;
            }
        }

        //genome check
        System.out.println("After Crossover:");
        printGenome(offspring, p, n);

        //evaluate each individual by counting the number of 1s after crossover
        for (int i = 0; i < p; i++) {
            offspring[i].fitness = 0;
            for (int j = 0; j < n; j++) {
                if (offspring[i].gene[j] == 1) {
                    offspring[i].fitness++;
                }
            }
        }

        //total fitness check
        System.out.println("Total fitness check #3 after crossover: " + getTotalFitness(offspring, p));
        System.out.println("Mean fitness check #3 after crossover: " + getMeanFitness(offspring, p));
    }

    public static void printGenome(Individual pop[], int p, int n) {
        for (int i = 0; i < p; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(pop[i].gene[j]);
            }
            System.out.println("");
        }
    }

    public static int getTotalFitness(Individual pop[], int p) {
        int totalFitness = 0;
        for (int i = 0; i < p; i++) {
            totalFitness = totalFitness + pop[i].fitness;
        }
        return totalFitness;
    }

    public static double getMeanFitness(Individual pop[], int p) {
        double meanFitness = getTotalFitness(pop, p) / (double) p;
        return meanFitness;
    }

}

推荐答案

问题是，当您说:

后代[i] =人口[父母1]

offspring[i] = population[parent1]

您实际上是在后代[i]中存储对种群[parent1]的引用.因此，您的后代数组可以多次包含相同的引用，因此同一对象将与多个伙伴多次参与交叉.

You are actually storing a reference to population[parent1] in offspring[i]. As a result your offspring array can contain the same reference multiple times, hence the same object will participate in crossover multiple times with multiple partners.

作为解决方案，您可以存储克隆而不是对同一对象的引用.在个人"中添加:

As a solution, you can store a clone instead of a reference to the same object. In Individual add:

    public Individual clone(){
        Individual clone = new Individual(gene.length);
        clone.gene = gene.clone();
        return clone;
    }

然后在您的选择中(请注意添加的.clone()):

And in your selection (note the added .clone()):

    for (int i = 0; i < p; i++) {
        parent1 = rand.nextInt(p); //randomly choose parent
        parent2 = rand.nextInt(p); //randomly choose parent

        if (population[parent1].fitness >= population[parent2].fitness) {
            offspring[i] = population[parent1].clone();
        } else {
            offspring[i] = population[parent2].clone();
        }
    }

这样，即使基因组相同，后代中的每个元素也是一个不同的对象.

This way every element in offspring is a different object, even if the genome is the same.

这解决了Java部分.关于GA理论，我希望有些事情，例如您的健康指标只是占位符，对吧?

That solves the Java part. Regarding the GA theory I hope some things, for instance your fitness measure are just placeholders, right?

这篇关于需要帮助查明Java遗传算法单点交叉机制中的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！