java - 遗传算法适应度分数问题

Question

我正在尝试编写一个java程序，它生成一组随机字符并最终到达输入的字符串以模拟诸如无限猴子定理( https://en.wikipedia.org/wiki/Infinite_monkey_theorem )之类的东西。我遇到的问题是，当我测试它时，所有起始种群的适应度均为 0，因此在自然选择过程中没有任何内容添加到交配池中。以下是该项目的内容。

目标:字符串“Hello”

突变率:0.01

群体上限: 100 个 DNA 对象，每个对象包含一个 char[] 基因数组。

这是我计算适应度的函数:

public void calcFitness(String target){
        double score = 0.0;
        for(int i = 0; i < this.genes.length; i++){
            if(this.genes[i] == target.charAt(i)){
                score++;
            }
        }
        this.fitness = score/this.genes.length;
    }

我是遗传编程的新手，不确定我做错了什么，任何帮助将不胜感激，任何有关遗传编程的提示或见解也将不胜感激。

编辑

以下是选择过程的代码:

 public void naturalSelection(){
        ArrayList<DNA> selection = new ArrayList<>();
        Random rand = new Random();
        String child = "";
        DNA[] newPop = new DNA[popMax];
        for(int i = 0; i < population.length; i++){
            for(int j = 0; j < population[i].getFitness(); j++){
                selection.add(population[i]);
            }
        }
        for(int i = 0; i < selection.size(); i++){
            int parentSelect = rand.nextInt(selection.size());
            DNA parent1 = selection.get(parentSelect);
            child = parent1.split(true);
            parentSelect = rand.nextInt(selection.size());
            DNA parent2 = selection.get(parentSelect);
            child += parent2.split(false);
            newPop[i] = new DNA(child);
        }
        double mutation = rand.nextDouble();
        if(mutation < this.mutationRate){
            this.population = swapMutation(newPop);
            calcFittest();
        }
        else{
            this.population = newPop;
            calcFittest();
        }
    }

如果发生突变，交换突变会交换两个随机字符。

Answer 1

我建议使用适应度函数来测量候选字符串到目标字符串的距离。然后，您将最小化整体健康度，而不是最大化。

要执行此操作:

public void calcFitness(String target){
    double score = 0.0;
    for(int i = 0; i < this.genes.length; i++){
        score += Math.abs((int)this.genes[i] - (int)target.charAt(i));
    }
    this.fitness = score / this.genes.length;
}

这应该效果更好，因为它可以更好地区分每个候选人。如果没有看到您正在使用的随机字符串生成器，很难说，但可能的候选者数量可能是天文数字，其中任何一个通过您的适应度函数获得单分的机会非常低。

可能还值得指出的是，您的代码可能是遗传算法而不是遗传编程的一部分。

如果你想改进选择，我会推荐一种易于编程的技术:锦标赛选择 - 从群体中随机选择 n 个个体，然后从 n 个个体中选择最佳适应度个体。这使得更好的候选者比其他个体有更高的被选中的机会，并且还有一个额外的好处，即您不需要计算群体中每个人的适应度。