How do genetic algorithms work exactly?

Question

I was looking at the basic genetic algorithm here

http://www.ai-junkie.com/ga/intro/gat1.html

But I have some questions about things I didn't get.

To reiterate:

---

You have a problem you want a good enough solution to.

You create N random solutions (encoded as bits of 0 and 1)

You evaluate a fitness or score for each for how good a solution it is.

Pick randomly 2 different of them. Based on each score, they have a higher chance of being picked. (i.e. higher score = higher chance of being picked, but the sum of all probabilities add to 100%)

Then for those 2 (call it A and B) picked, there is a cross over step. There is a chance associated with a crossover. The link uses 70%. So if the crossover happens, then we pick a random point and exchange the bits of both A and B after the point. This creates C.

1. We created a new solution. Do we remove one of the existing ones? If so, which one?

Then there is a mutation step. This is the part that confuses me most.

1. Does mutation step occur regardless of if the crossover step happened or not?

2. What do we mutate? A or B or C?

3. For whatever we mutate, does mutate mean we iterate over each bit, and for each bit there is a 0.1% chance to flip the bit?

Finally reevaluate the score for all and repeat all of this until you find a good enough solution.

---

Does anyone know?

Answer 1

Looking at the code the tutorial provides answers your questions. First of all, as it's described/implemented, crossover doesn't create a new string, it just modifies the two selected ones. So,

1. Yes, mutation always occurs
2. You mutate both A and B. There is no C
3. Yes.

Answer 2

There isn't one genetic algorithm, there are many variants on the same theme. All use a population (set of candidates); generations, where better candidates are kept; most use the idea of mutations (change some candidate at random) and/or crossover (take two, perhaps more, candidates and splice them together to get new ones). Details vary wildly, some don't use one or the other of the basic operations. Most use descriptions of candidates that codify potential solutions so that specialized "mutation" operations, not just random bit changes, don't create nonsense; some have mutation operators that "repair" broken candidates; the "crossover" is codified so the result is viable (again possibly with a repair step). Some even apply improvement operations on the newly created candidates after mutation/crossover, by doing local changes aimed at making the candidate somehow better. The right codification of the potential solutions (candidates) is crucial to simplify the above operations. And so is the proper generation of the starting population. Then they are tuned by selecting population size, probability of mutation, probability of crossover, the exact method used to select the members of the next generation (keep the best ones, select at random with a bias towards the better ones, ...). Bad candidates can very well carry parts of the optimal solution.

All of this is highly problem dependent.