遗传算法停止变异

Question

我目前正在尝试使我的遗传算法 "generate" 或 "evolve" 朝向给定的单词。问题是，它永远不会完全达到这个词，它会停在一个过高的适应度分数上，即使它应该继续变异。

举个例子：

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

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

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

下面是基本的分步说明：

使用完全随机化的字符串创建 20 条染色体
计算与目标词相比的适应度分数。（计算 Ascii id 差异）
将得分最高的两条染色体配对。
随机突变一些染色体（更改随机字符串字符）
杀掉90%的弱种群，换成精英染色体（当前适应度最好的染色体）。
重复一切。

这里是我算法中最重要的方法：

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

您的 mutate 和 calculateCost 函数很奇怪。特别是， mutate() 看起来旨在陷入局部最小值。任何向上或向下的突变都会比精英更糟糕（精英可能是相同的，所以交叉不会改变任何东西）。使用不同的变异：选择一个随机索引并完全改变它。同时从 cost().

中删除 i*i

Answer 2

您的时间步长完全不对：

Create 20 Chromosomes with fully randomized strings. Seems okay.

Calculate the fitness score compared to the goal word. (Counting Ascii ids differences). Seems okay.

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

Mutate some of the Chromosomes randomly (change random string chars)

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.

Repeat everything.

因此将您的步骤更改为：

INIT. Initialise population, create 20 random chromosomes

Calculate score for each chromsome

Save the two fittest chromosomes to the next population (aka elitism), getthe other 18 needed individuals by breeding fitness proportionally

Mutate the chromsomes with a certain chance

Repeat

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

遗传算法停止变异

Genetic Algorithm stops mutating

c#

algorithm

genetic-algorithm