Genetic algorithm, Which Chromosomes to crossover given fitness?

[Superposed_Cat]

Hi all, I'm busy writing my first genetic algorithm. A simple one that finds an expression to give a desired number, ie you'll give it the number 40 and it will give you 5*7+5. I have the fitness function, the parser that uses the string to compute the number and the crossover system, so only the final step remains, but I'm confused, say I have the 6 chromosomes with a fitness assigned to each, what do I do from there? I can't just breed the best two and remove the others?

Do I select the best 2 then breed them but change how they crossover each time?
Any help appreciated, apologies for newbieness.

 

[timthereaper]

IMHO, the 2 main things that make a genetic algorithm work are fitness pressure and a good sized population. Mutation helps, but IMO it only helps the rate of convergence. Thus, I wouldn't keep only the best 2. The way I've implemented GAs in the past is to start with a population of like 100, breed 100 more children, rate both the parents and the children together, and then take the top 100. You might have parents that keep surviving after many generations, but that's fine because it helps the algorithm converge faster. If it's allowed to run for a long enough time, the entire population should become essentially identical (since you're only considering 1 fitness function) and that will be the strongest one (optimal).

 

[Superposed_Cat]

Seem to be having issues, is my crossover function correct?

public static void CrossoverGG(Chromosome a, Chromosome b, out Chromosome aa, out Chromosome bb)
        {
            Chromosome at = a;
            Chromosome bt = b;
            for (int i = ran.Next(a.genes.Count); i < a.genes.Count; i++)
            {
                Gene y;
                Gene y2;
         
                    XOR(a.genes[i], b.genes[i], out y, out y2);
                    at.genes[i] = y;
                    bt.genes[i] = y2;
           
            }
            aa = at;
            bb = bt;
        }
    }

public static void XOR(Gene a, Gene b,out Gene aa,out Gene bb)
        {        
                char[] ac = a.gene.ToArray();
                char[] bc = b.gene.ToArray();
            for (int i = 0; i < a.gene.Length; i++)
            {
                char temp = ac[i];
                ac[i] = bc[i];
                bc[i] = temp;
            }
            aa = new Gene(new string(ac));
            bb = new Gene(new string(bc));
        }

and then essentially (for a small population) something liek this for breeding?

 Genome dna = new Genome();
            for (int i = 0; i < 10; i++)
            {           
                Genome.CrossoverGG(dna.genome[0], dna.genome[1], out a, out b);
                Genome.CrossoverGG(dna.genome[2], dna.genome[3], out c, out d);
                dna.genome.Clear();
                dna.genome.Add(a);
                dna.genome.Add(b);
                dna.genome.Add(c);
                dna.genome.Add(d);
                dna.genome.
                dna.Evolve();
            }

Where evolve sorts by fitness. In this instance the .Evolve() is frivolous but was just to show you my general thinking,

 

[timthereaper]

It seems your XOR function is just duplicating your original chromosomes. You're just swapping every gene in AC and BC. You need to randomize gene swapping so that say 15% of the time a gene swap occurs. You can modify that parameter later. If you want, you can add a mutation rate like 0.1% by putting a random but meaningful value in that gene.

Also, you need to select the parents somewhat randomly. You don't want to only use the fittest parents like you're doing because then you're not letting the algorithm find other possible combinations that might be better than the fittest functions. A good way to view GAs is that you're trying to search the solution space for an optimum. Weaker chromosomes might contribute important values that will improve the overall fitness.

Keep it up though! GAs are tricky until you implement them a few times.

 

[Superposed_Cat]

It seems your XOR function is just duplicating your original chromosomes.

for (int i = ran.Next(a.genes.Count); i < a.genes.Count; i++)

I'm only duplicating some genes, any other ideas? ie this should work from what I've shown you right?

 

[timthereaper]

Oh I missed that you had a Random.Next() in the declaration. I think it should work, but won't it then continue swapping until i=a.genes.Count-1, then increment, then terminate the loop? The possibility is that the genes would be swapped, then swapped back a lot. What I would do is go through all the genes, but get a random number between 0 and 1, then do an if(randomValue < 0.15) XOR(); or something.

 

[Superposed_Cat]

I just added that function, also increased number of generations and population size, the output is totally inconsistent,
sometimes final 'guess' is close, like 22 and 26 (aiming for 24) other times it's 11 or 36. if I could get it consistently within the 20's id be happy. no other ideas? Profuse apologies.

 

[timthereaper]

It seems the algorithm might be working, but there's a few things you might want to modify:

• The 15% I told you before was just an example. That's a parameter you can tweak. The same goes for mutation rate and number of generations.
• Are you sure your fitness function is the best one suited to your problem? Sometimes there's a problem if your fitness function doesn't allow good values to be kept.
• Do you have a sufficiently starting random population?

Genetic algorithms are kind of an art. The actual values for a mutation rates, crossover rates, and so on depend a lot on the problem being solved. Also, genetic algorithms aren't always going to give you the most optimal solution, Especially if there's a large amount of possible combinations. I think you have it implemented correctly, so I would just start playing with values and seeing what you get. Step through your code everything few generations and see what it's doing.