Genetic Algorithm stops mutating

Question

I'm currently trying to make my genetic algorithm "generate" or "evolve" towards an given word. The problem is, that it never fully reaches this word, it stops at an too high fitness score, even if it should continue mutating.

Heres an example:

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

And I have no clue why it won't continue mutating. Normally it just should resume with changing randomly some chars in the string.

So I would be very glad about some help.

Here's an basic step by step explanation:

Create 20 Chromosomes with fully randomized strings
Calculate the fitness score compared to the goal word. (Counting Ascii ids differences)
Mate the two Chromosomes with the best score.
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).
Repeat everything.

So here the most important methods of my algorithm:

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;
}

May be because of the random? if (random.Next(0,101) <= chance) return; — Samvel Petrosov
This is not complete code. Please post Minimum, complete, verifiable example. — Renats Stozkovs

Ray Ray · Accepted Answer · 2017-05-12T07:17:23

Your mutate and calculateCost functions are weird. In particular, mutate() looks designed to get trapped in local minimas. Any mutation up or down will be worse than the elites (which are probably identical so crossover changes nothing). Use a different mutate: Pick a random index and change it completely. Also remove i*i from cost().

Genetic Algorithm stops mutating

2 Answers