c# - 遗传算法停止变异

Question

我目前正在尝试让我的遗传算法“生成”或“进化”给定的词。问题是，它永远不会完全达到这个词，它会停在一个过高的适应度分数上，即使它应该继续变异。

举个例子:

User input = "HelloWorld"
After 500 generations = "XelgoWorfd"

而且我不知道为什么它不会继续变异。通常它应该随机更改字符串中的一些字符来恢复。

所以我很乐意提供一些帮助。

这是一个基本的逐步解释:

1. 用完全随机化的字符串创建 20 条染色体
2. 计算与目标词相比的适应度分数。(计算 Ascii id 差异)
3. 将得分最高的两条染色体配对。
4. 随机突变一些染色体(改变随机字符串字符)
5. 杀死 90% 的弱种群，并用精英染色体(当前适应度得分最高的染色体)替换它。
6. 重复一切。

所以这里是我的算法最重要的方法:

public Chromoson[] mate(string gene) {
    Console.WriteLine("[MATING] In Progress : "+gens+" "+gene);

    int pivot = (int)Math.Round((double)gens.Length / 2) - 1;

    string child1 = this.gens.Substring(0, pivot) + gene.Substring(pivot);
    string child2 = gene.Substring(0, pivot) + this.gens.Substring(pivot);

    Chromoson[] list = new Chromoson[2];

    list[0] = new Chromoson(child1);
    list[1] = new Chromoson(child2);

    Console.WriteLine("[MATING] Pivot : "+pivot);
    Console.WriteLine("[MATING] Children : "+child1+" "+child2);

    return list;
}

public void mutate(float chance, int possiblyChanges) {
    if (random.Next(0,101) <= chance) return;

    int changes = random.Next(0, possiblyChanges + 1);
    //int index = (int) Math.Floor((double)random.Next() * this.gens.Length);

    for (int i = 0; i < changes; i++) {
        int index = random.Next(0, 13);
        StringBuilder builder = new StringBuilder(gens);
        int upOrDown = random.Next(0, 101);

        if (upOrDown <= 50 && (int)builder[index] > 0 && chars.Contains(Convert.ToChar(builder[index] - 1)))
            builder[index] = Convert.ToChar(builder[index] - 1);
        else if (upOrDown >= 50 && (int)builder[index] < 127 && chars.Contains(Convert.ToChar(builder[index] + 1)))
            builder[index] = Convert.ToChar(builder[index] + 1);
        else
            mutate(chance, possiblyChanges);

        gens = builder.ToString();
    }
    Console.WriteLine("[MUTATING] In Progress");
}

public void calculateCost(string otherGens)
{
    int total = 0;
    for (int i = 0; i < gens.Length; i++)
    {
        total += (((int)gens[i] - (int)otherGens[i]) * ((int)gens[i] - (int)otherGens[i])) * (i*i);
    }
    Console.WriteLine("[CALCULATING] Costs : " + total);
    this.cost = total;
}

Answer 1

您的时间步长中出现了一些问题:

1. Create 20 Chromosomes with fully randomized strings. Seems okay.
2. Calculate the fitness score compared to the goal word. (Counting Ascii ids differences). Seems okay.
3. Mate the two Chromosomes with the best score. What? Your only breeding the two fittest chromosomes to create the new population? That means you will have a population that is nearly completely similar. Breedfitness proportionally, so all genomes have a chance to have an offspring
4. Mutate some of the Chromosomes randomly (change random string chars)
5. Kill 90% of the weak population and replace it with elite chromosomes (The chromosomes with the currently best fitness score). You kill 90%? So basically, you're keeping the 2 best genomes every iteration and then replacing the other 18 with step 1? What you want is to keep the 2 fittest at step 3, and create the other 18 individuals by breeding.
6. Repeat everything.

因此将您的步骤更改为:

INIT. Initialise population, create 20 random chromosomes

1. Calculate score for each chromsome
2. Save the two fittest chromosomes to the next population (aka elitism), getthe other 18 needed individuals by breeding fitness proportionally
3. Mutate the chromsomes with a certain chance
4. Repeat

不要每轮都随机创建个体。这会将您的算法变成随机搜索。