java - 无法定位这个简单的遗传算法程序中的问题

Question

我用java写了一个简单的遗传算法程序。它所做的是最大化由染色体中的位表示的十进制值。不知何故突变没有按预期工作，例如当只有一个基因发生变化时，会导致两个基因发生突变。我在那里包含的打印语句显示了哪些要突变，但除此之外还有更多的染色体发生突变。我不知道问题是什么:-(

这是我的 java 类。

Gene.java

public class Gene {

    private int value;
    public Gene() {
        value = Math.random() < 0.5 ? 0 : 1;
    }

    public Gene(int value) {
        if (value != 0 && value != 1) {
            throw new IllegalArgumentException("value must be either 0 or 1");
        }
        else {
            this.value = value;
        }
    }

    public void mutate() {
        value = 1 - value;
    }

    public int value() {
        return value;
    }

    @Override
    public String toString() {
        return String.valueOf(value);
    }
}

Chromosome.java

import java.util.ArrayList;
import java.util.List;

public class Chromosome implements Comparable {

    private ArrayList<Gene> genes;
    private final int chromosomeLength;

    public Chromosome(int length) {
        this.genes = new ArrayList<>();

        this.chromosomeLength = length > 0 ? length : 16;

        for (int i = 0; i < chromosomeLength; i++) {
            this.genes.add(i, new Gene());
        }
    }

    public List<Gene> getAllele(int fromIndex, int toIndex) {
        return new ArrayList<>(genes.subList(fromIndex, toIndex));
    }

    public void setAllele(int fromIndex, List<Gene> allele) {

        int lastIndex = fromIndex + allele.size();
        if (lastIndex > chromosomeLength) {
            throw new IndexOutOfBoundsException("the allele exceeds beyond the size of the chromosome");
        }
        for (int i = fromIndex, j = 0; i < lastIndex; i++, j++) {
            genes.set(i, allele.get(j));
        }
    }

    public int getChromosomeLength() {
        return chromosomeLength;
    }

    public void setGeneAt(int index, Gene gene) {
        genes.set(index, gene);
    }

    public Gene getGeneAt(int index) {
        return genes.get(index);
    }

    public int value() {
        return Integer.parseInt(this.toString(), 2);
    }

    @Override
    public String toString() {
        StringBuilder chromosome = new StringBuilder("");

        genes.stream().forEach((Gene g) -> chromosome.append(g));

        return chromosome.toString();
    }

    @Override
    public int compareTo(Object anotherChromosome) {
        Chromosome c = (Chromosome) anotherChromosome;
        return this.value() - c.value();
    }
}

GenePool.java

import java.util.ArrayList;
import java.util.Arrays;

public class GenePool {

    private final ArrayList<Chromosome> genePool;
    private final int genePoolSize;
    private final int chromosomeLength;
    private final double crossOverRate;
    private final double mutationRate;
    private int[] crossPoints;

    public GenePool(int numOfChromosome, int chromosomeLength, double crossOverRate, double mutationRate) {

        this.genePoolSize = numOfChromosome;
        this.chromosomeLength = chromosomeLength > 0 ? chromosomeLength : 16;
        this.crossOverRate = crossOverRate;
        this.mutationRate = mutationRate;

        crossPoints = new int[1];
        crossPoints[0] = this.chromosomeLength / 2;

        genePool = new ArrayList<>();
        for (int i = 0; i < numOfChromosome; i++) {
            genePool.add(new Chromosome(chromosomeLength));
        }
    }

    public int getGenePoolSize() {
        return genePoolSize;
    }

    public Chromosome getChromosomeAt(int index) {
        return genePool.get(index);
    }

    public void setChromosomeAt(int index, Chromosome c) {
        genePool.set(index, c);
    }

    public int getChromosomeLength() {
        return chromosomeLength;
    }

    public Chromosome[] crossOver(Chromosome c1, Chromosome c2) {

        Chromosome[] offsprings = new Chromosome[2];
        offsprings[0] = new Chromosome(c1.getChromosomeLength());
        offsprings[1] = new Chromosome(c1.getChromosomeLength());

        Chromosome[] parentChromosomes = {c1, c2};

        int selector = 0;
        for (int i = 0, start = 0; i <= crossPoints.length; i++) {

            int crossPoint = i == crossPoints.length ? c1.getChromosomeLength() : crossPoints[i];

            offsprings[0].setAllele(start, parentChromosomes[selector].getAllele(start, crossPoint));
            offsprings[1].setAllele(start, parentChromosomes[1 - selector].getAllele(start, crossPoint));
            selector = 1 - selector;
            start = crossPoint;
        }
        return offsprings;
    }

    public void mutateGenePool() {

        int totalGeneCount = genePoolSize * chromosomeLength;

        System.out.println("Mutating genes:");
        for (int i = 0; i < totalGeneCount; i++) {
            double prob = Math.random();
            if (prob < mutationRate) {
                System.out.printf("Chromosome#: %d\tGene#: %d\n", i / chromosomeLength, i % chromosomeLength);
                genePool.get(i / chromosomeLength).getGeneAt(i % chromosomeLength).mutate();
            }
        }
        System.out.println("");
    }

    public int getLeastFitIndex() {
        int index = 0;
        int min = genePool.get(index).value();
        int currentValue;
        for (int i = 1; i < genePoolSize; i++) {
            currentValue = genePool.get(i).value();
            if (currentValue < min) {
                index = i;
                min = currentValue;
            }
        }
        return index;
    }

    public void saveFittest(ArrayList<Chromosome> offsprings) {
        // sort in ascending order
        offsprings.sort(null);

        offsprings.stream().forEach((offspring) -> {
            int leastFitIndex = getLeastFitIndex();
            if (offspring.value() > genePool.get(leastFitIndex).value()) {
                genePool.set(leastFitIndex, offspring);
            }
        });
    }

    public void evolve(int noOfGeneration) {

        for (int generation = 1; generation <= noOfGeneration; generation++) {

            System.out.println("Generation :" + generation);

            ArrayList<Integer> selection = new ArrayList<>();

            for (int i = 0; i < genePoolSize; i++) {
                if (Math.random() <= crossOverRate) {
                    selection.add(i);
                }
            }

            if (selection.size() % 2 == 1) {
                selection.remove(selection.size() - 1);
            }

            ArrayList<Chromosome> offsprings = new ArrayList<>();
            for (int i = 0; i < selection.size(); i += 2) {
                int index1 = selection.get(i);
                int index2 = selection.get(i + 1);
                offsprings.addAll(Arrays.asList(crossOver(genePool.get(index1), genePool.get(index2))));
            }

            System.out.println("Before saving the offsprings");
            displayChromosomes(genePool, "GenePool");
            displayChromosomes(offsprings, "Offsprings");

            saveFittest(offsprings);

            System.out.println("Before mutation:");
            displayChromosomes(genePool, "GenePool");

            mutateGenePool();

            System.out.println("After mutation:");
            displayChromosomes(genePool, "GenePool");

            System.out.println("\n\n");
        }
    }

    public void displayChromosomes(ArrayList<Chromosome> geneList, String name) {
        System.out.println(name);
        if (geneList.isEmpty()) {
            System.out.println("Empty list");
        }

        geneList.stream().forEach((c) -> {
            System.out.println(c + " -> " + c.value());
        });
        System.out.println("");

    }
}

GADemo.java

public class GADemo {


    public static void main(String[] args) {
        GenePool gp = new GenePool(6, 8, 0.25, 0.01);

        gp.evolve(10);

    }
}

经过数代进化后，所有染色体都趋向于完全相同或非常相似。问题是这个值不是那么多位的最大值，有时甚至是一个很小的值。例如，对于 8 位，值应该(倾向于)接近 255，但在我的代码中并没有这样做。请有人提供提示在哪里/如何寻找和解决问题。

Answer 1

关注这些行并想象引用。这些来自 setAllele()

for (int i = fromIndex, j = 0; i < lastIndex; i++, j++) {
    genes.set(i, allele.get(j));
}

您基本上是将引用从一个复制到另一个。它们是相同的基因，因此无论您对这些基因进行何种突变，都会影响其他染色体。

您必须生成 deep copy在这里。