How do genetic algorithms work, specifically, what is the origin of mutations?

539 views
0

I understand that genetic algorithms try a series of functions to see which one is the “best” but where does the variance come from (programmed, random, etc.)? And does this relate to Machine Learning?

In: Biology

It’s pretty straightforward – whoever designs the system decides how mutations & matings occur, what the fitness function is and every other aspect. It’s not that things “naturally” occur – the “genetics” and “evolution” of the system are just a metaphor. The easiest way to put one together is to have a fixed algorithm & make the elements that change some constants. [If you look at this GA demo](https://rednuht.org/genetic_cars_2/), you’ll see that the shape of the “car” and the size of the wheels start out pretty random but over multiple generations, they tend to give you a better “car” that can actually travel a long distance over the various obstacles in the way.

Lets say you are looking for a program that receives a number and returns another. Your input is something like 1,2,3,4,5 and the known output is 2, 5, 10, 17, 26. We are looking for the function that convers the input x into the output y.

Lets consider a random population of 2 individuals/programs:

Y=x^3
Y=x+1

In the next generation, you might have a mutation on the first and get

Y=x^2, which has a better fitness (less average error).

Another alternative would be y=x/3, but lets consider the first one.

Now the first and second individuals can be crossed into:

Y=x^2+1, which has error 0 and its the right solution for this dataset.

Now, mutations and crossovers occur usually in a tree representation. A value might change into a literal (3), q variable (x) or an operation (_ + _). This depends heavily with the language of the expression.

For machine learning you have multiple inputs, x1, x2, x3…