Genetic algorithm, Which Chromosomes to crossover given fitness?

  • Thread starter Superposed_Cat
  • Start date
  • Tags
    Algorithm
In summary, you should start with a population of 100 and then breed more. You should rate the parents and the children together to find the best ones and keep those.
  • #1
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.
 
Technology news on Phys.org
  • #2
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).
 
  • Like
Likes Superposed_Cat
  • #3
Seem to be having issues, is my crossover function correct?
Code:
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?
Code:
 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,
 
Last edited:
  • #4
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.
 
  • Like
Likes Superposed_Cat
  • #5
timthereaper said:
It seems your XOR function is just duplicating your original chromosomes.
Code:
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?
 
  • #6
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.
 
  • #7
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.
 
  • #8
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.
 

1. What is a genetic algorithm?

A genetic algorithm is a computational technique inspired by the process of natural selection. It mimics the process of evolution by randomly generating a population of potential solutions and using methods such as crossover and mutation to create new generations of solutions with improved fitness.

2. How does a genetic algorithm select which chromosomes to crossover?

The selection of chromosomes for crossover is typically based on their fitness, which is a measure of how well they perform in solving the problem at hand. The fitter chromosomes are more likely to be selected for crossover as they have a higher chance of producing offspring with desirable traits.

3. What is the role of fitness in a genetic algorithm?

Fitness is a crucial aspect of genetic algorithms as it determines which solutions are more likely to be selected for reproduction and which traits are more likely to be passed down to future generations. By optimizing for fitness, genetic algorithms can find better and more efficient solutions to complex problems.

4. How do genetic algorithms ensure diversity in the population?

Genetic algorithms use a variety of techniques, such as crossover and mutation, to introduce new genetic material into the population and prevent it from becoming too homogeneous. This allows for the exploration of a wider range of potential solutions and increases the chances of finding the optimal solution.

5. Can genetic algorithms be used for any problem?

While genetic algorithms can be used for a wide range of problems, they are most effective for optimization problems with a large search space and complex solution space. They are not suitable for problems that require logical reasoning or human intuition.

Suggested for: Genetic algorithm, Which Chromosomes to crossover given fitness?

Replies
13
Views
1K
Replies
2
Views
433
Replies
1
Views
576
Replies
1
Views
701
Replies
6
Views
2K
Replies
1
Views
797
Replies
4
Views
1K
Replies
28
Views
1K
Back
Top