Tag Archives: machine learning

What is a Genetic Algorithm?

“Genetic algorithm” is also called “genetic search”. It’s modeled after an idealized view of natural selection, but very, very loosely. Really it’s method of making guesses at an answer to a question based on combinations of previous answers and how they did.

 A genetic search starts with two things:

 1) A population of solutions encoded as “gene” strings. These are usually randomly generated to start with.

 2) One or more methods for combining and mutating those strings.

Implicit in both of those is a way to “score” the strings, so that you can tell good answers from bad ones.

The genetic algorithm is just a process:

a) select two gene strings from the population

b) combining them into a new solution

c) score that solution to see how good it is

d) put that solution into the population & remove one that has a lower score

So, over time, the population contains strings that reflect the best parts of their ancestors & have the highest scores. If there’s a single “right” solution, eventually the algorithm will probably find it. If there’s no “right” solution, the algorithm will ruthlessly optimize the scores to find ones that work best.

It all sounds vaguely racist, maybe not so vaguely, but you have to remember that a) it’s just a computer algorithm and not a metaphor for natural processes, and b) animals and humans don’t have a “score” associated with them.

The search can get hung up on a local maximum, so sometimes you have to blow away the population and start over. But there’s no rule against keeping a log of the best solutions so you can see how they did over time.

 One of the neat things about genetic algorithms is because it’s mindlessly and ruthlessly optimizing that score, it will often discover solutions you didn’t consider, or even don’t like, but which meet the criteria best. That can be fun, and it can also be frustrating. But I think it’s more fun than frustrating.

 

Leave a comment

Filed under computer algorithms, machine learning