Genetic algorithms: cool name & damn simple.
Genetic algorithms are a mysterious sounding technique in mysterious sounding field--artificial intelligence. This is the problem with naming things appropriately. When the field was labeled artificial intelligence, it meant using mathematics to artificially create the semblance of intelligence, but self-engrandizing researchers and Isaac Asimov redefined it as robots.
The name genetic algorithms does sound complex and has a faintly magical ring to it, but it turns out that they are one of the simplest and most-intuitive concepts you'll encounter in A.I.
What Can Genetic Algorithms Do?
In a word, genetic algorithms optimize. They can find better answers to a question, but not solve new questions. Given the definition of a car, they might create a better car, but they'll never give you an airplane.
I Like The Term Genetic Programming More!
Me too--it has a much nicer ring to it--but unfortunately using one or the other isn't a personal preference; they refer to different techniques. Genetic algorithms are about optimization, while genetic programming is about using the techniques from genetic algorithms to build computer programs from primordial programming language soup.
Imagine, if you will, that you have spent the last decade trying to write a "Hello World" program in Scheme, but simply cannot overcome that tremendous hurdle. But imagine that you were smart enough to put together a tremendous list of commands and strings, such that some combination could print "Hello World" to standard out. Then you could mix and match the commands and strings and eventually you might generate "Hello World", much like monkeys typing randomly will--given an infinitely long period of time--recreate Shakespeare. Sort of.
So, where generic algorithms are a collection of optimization techniques, genetic programming is a novel approach for solving problems for which you already know the answer. Ok, ok, this isn't a fair description. We'll take a more indepth look later in another article, for the time being lets just remember they aren't the same.
Defining a Problem to Optimize
Now we're going to put together a simple example of using a genetic
algorithm in Python. We're going to optimize a very simple problem:
trying to create a list of N numbers that equal X when summed together.
If we set N = 5 and X = 200, then these would all be appropriate
solutions.
lst = [40,40,40,40,40]
lst = [50,50,50,25,25]
lst = [200,0,0,0,0]
(I've been told that randomly stating Pretty easy, right? at random junctions of articles is not helpful. Otherwise I would have uselessly added one here.)
Ingredients of The Solution
Each suggested solution for a genetic algorithm is referred to
as an individual. In our current problem, each list of N
numbers is an individual.
>>> from random import randint
>>> def individual(length, min, max):
... 'Create a member of the population.'
... return [ randint(min,max) for x in xrange(length) ]
...
>>> individual(5,0,100)
[79, 0, 20, 47, 40]
>>> individual(5,0,100)
[64, 1, 25, 84, 87]
The collection of all individuals is referred to as our population.
>>> def population(count, length, min, max):
... """
... Create a number of individuals (i.e. a population).
...
... count: the number of individuals in the population
... length: the number of values per individual
... min: the min possible value in an individual's list of values
... max: the max possible value in an individual's list of values
...
... """
... return [ individual(length, min, max) for x in xrange(count) ]
...
>>> population(3,5,0,100)
[[51, 55, 73, 0, 80], [3, 47, 18, 65, 55], [17, 64, 77, 43, 48]]
Next we need a way to judge the how effective each solution is;
to judge the fitness of each individual. Predictably enough,
we call this the fitness function. For our problem, we want
the fitness to be a function of the distance between the sum of
an individuals numbers and the target number X.
We can implement the fitness function as follows:
>>> from operator import add
>>> def fitness(individual, target):
... """
... Determine the fitness of an individual. Lower is better.
...
... individual: the individual to evaluate
... target: the sum of numbers that individuals are aiming for
... """
... sum = reduce(add, individual, 0)
... return abs(target-sum)
...
>>> x = individual(5,0,100)
>>> fitness(x, 200)
165
Personally, I'd prefer to have a high fitness score correlate to
a fit individual rather than the current implementation where a
perfectly fit individual has a fitness of 0, and the higher
the worse. Ah well, regardless, keep that detail in mind while
following this code.
It's also helpful to create a function that will determine a population's average fitness.
>>> def grade(pop, target):
... 'Find average fitness for a population.'
... summed = reduce(add, (fitness(x, target) for x in pop), 0)
... return summed / (len(pop) * 1.0)
...
>>> x = population(3,5,0,100)
>>> target = 200
>>> grade(x, target)
116
Now we just need a way evolve our population; to advance the population from one generation to the next.
Evolution
This is the secret sauce of genetic algorithms, where secret means fairly obvious, and sauce means sauce. Consider a population of elk which are ruthlessly hunted by a pack of wolves. With each generation the weakest are eaten by the wolves, and then the strongest elk reproduce and have children. Abstract those ideas a bit, and we can implement the evolution mechanism.
For each generation we'll take a portion of the best performing individuals as judged by our fitness function. These high-performers will be the parents of the next generation.
We'll also randomly select some lesser performing individuals to be parents, because we want to promote genetic diversity. Abandoning the metaphor, one of the dangers of optimization algorithms is getting stuck at a local maximum and consequently being unable to find the real maximum. By including some individuals who are not performing as well, we decrease our likelihood of getting stuck.
Breed together parents to repopulate the population to its desired size (if you take the top 20 individuals in a population of 100, then you'd need to create 80 new children via breeding). In our case, breeding is pretty basic: take the first
N/2digits from the father and the lastN/2digits from the mother.>>> father = [1,2,3,4,5,6] >>> mother = [10,20,30,40,50,60] >>> child = father[:3] + mother[3:] >>> child [1,2,3,40,50,60]
It's okay to have one parent breed multiple times, but one parent should never be both the father and mother of a child.
Merge together the parents and children to constitute the next generation's population.
Finally we mutate a small random portion of the population. What this means is to have a probability of randomly modifying each individual.
>>> from random import random, randint >>> chance_to_mutate = 0.01 >>> for i in population: ... if chance_to_mutate > random(): ... place_to_modify = randint(0,len(i)) ... i[place_to_modify] = randint(min(i), max(i)) ...
This--just like taking individuals who are not performing particularly well--is to encourage genetic diversity, i.e. avoid getting stuck at local maxima.
Putting it all together, the code to evolve a generation can be implemented like this:
def evolve(pop, target, retain=0.2, random_select=0.05, mutate=0.01):
graded = [ (fitness(x, target), x) for x in pop]
graded = [ x[1] for x in sorted(graded)]
retain_length = int(len(graded)*retain)
parents = graded[:retain_length]
<span class="c"># randomly add other individuals to promote genetic diversity</span>
<span class="k">for</span> <span class="n">individual</span> <span class="ow">in</span> <span class="n">graded</span><span class="p">[</span><span class="n">retain_length</span><span class="p">:]:</span>
<span class="k">if</span> <span class="n">random_select</span> <span class="o">></span> <span class="n">random</span><span class="p">():</span>
<span class="n">parents</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">individual</span><span class="p">)</span>
<span class="c"># mutate some individuals</span>
<span class="k">for</span> <span class="n">individual</span> <span class="ow">in</span> <span class="n">parents</span><span class="p">:</span>
<span class="k">if</span> <span class="n">mutate</span> <span class="o">></span> <span class="n">random</span><span class="p">():</span>
<span class="n">pos_to_mutate</span> <span class="o">=</span> <span class="n">randint</span><span class="p">(</span><span class="mf">0</span><span class="p">,</span> <span class="nb">len</span><span class="p">(</span><span class="n">individual</span><span class="p">)</span><span class="o">-</span><span class="mf">1</span><span class="p">)</span>
<span class="c"># this mutation is not ideal, because it</span>
<span class="c"># restricts the range of possible values,</span>
<span class="c"># but the function is unaware of the min/max</span>
<span class="c"># values used to create the individuals,</span>
<span class="n">individual</span><span class="p">[</span><span class="n">pos_to_mutate</span><span class="p">]</span> <span class="o">=</span> <span class="n">randint</span><span class="p">(</span>
<span class="nb">min</span><span class="p">(</span><span class="n">individual</span><span class="p">),</span> <span class="nb">max</span><span class="p">(</span><span class="n">individual</span><span class="p">))</span>
<span class="c"># crossover parents to create children</span>
<span class="n">parents_length</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">parents</span><span class="p">)</span>
<span class="n">desired_length</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">pop</span><span class="p">)</span> <span class="o">-</span> <span class="n">parents_length</span>
<span class="n">children</span> <span class="o">=</span> <span class="p">[]</span>
<span class="k">while</span> <span class="nb">len</span><span class="p">(</span><span class="n">children</span><span class="p">)</span> <span class="o"><</span> <span class="n">desired_length</span><span class="p">:</span>
<span class="n">male</span> <span class="o">=</span> <span class="n">randint</span><span class="p">(</span><span class="mf">0</span><span class="p">,</span> <span class="n">parents_length</span><span class="o">-</span><span class="mf">1</span><span class="p">)</span>
<span class="n">female</span> <span class="o">=</span> <span class="n">randint</span><span class="p">(</span><span class="mf">0</span><span class="p">,</span> <span class="n">parents_length</span><span class="o">-</span><span class="mf">1</span><span class="p">)</span>
<span class="k">if</span> <span class="n">male</span> <span class="o">!=</span> <span class="n">female</span><span class="p">:</span>
<span class="n">male</span> <span class="o">=</span> <span class="n">parents</span><span class="p">[</span><span class="n">male</span><span class="p">]</span>
<span class="n">female</span> <span class="o">=</span> <span class="n">parents</span><span class="p">[</span><span class="n">female</span><span class="p">]</span>
<span class="n">half</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">male</span><span class="p">)</span> <span class="o">/</span> <span class="mf">2</span>
<span class="n">child</span> <span class="o">=</span> <span class="n">male</span><span class="p">[:</span><span class="n">half</span><span class="p">]</span> <span class="o">+</span> <span class="n">female</span><span class="p">[</span><span class="n">half</span><span class="p">:]</span>
<span class="n">children</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">child</span><span class="p">)</span>
<span class="n">parents</span><span class="o">.</span><span class="n">extend</span><span class="p">(</span><span class="n">children</span><span class="p">)</span>
<span class="k">return</span> <span class="n">parents</span>
Now we've written all the pieces of a genetic algorithm, and we just have to try it out and see if it works.
Testing It Out
Here is a simple way to use the code we've written:
>>> target = 371
>>> p_count = 100
>>> i_length = 5
>>> i_min = 0
>>> i_max = 100
>>> p = population(p_count, i_length, i_min, i_max)
>>> fitness_history = [grade(p, target),]
>>> for i in xrange(100):
... p = evolve(p, target)
... fitness_history.append(grade(p, target))
...
>>> for datum in fitness_history:
... print datum
...
Running that code, you'll get to watch as generations' fitness gradually (but non-deterministically) approach zero. The output of one of my runs looked like this:
['76.06', '32.13', '26.34', '18.32', '15.08', '11.69', '14.05', '9.460', '4.950', '0.0', '0.0', '0.0', '0.0', '0.0', '0.800', '0.0', '0.239', '0.780', '0.0', '0.0', '0.0', '0.0', '1.48', '0.0', '0.0', '0.0', '0.0', '0.0', '0.0', '0.149', '0.239', '0.12', '0.0', '0.0', '0.0', '0.0', '0.0', '0.0', '0.0', '0.149', '0.0', '0.0', '0.0', '0.0', '0.0', '0.0', '4.200', '0.0', '2.049', '0.0', '0.200', '0.080', '0.0', '1.360', '0.0', '0.0', '0.0', '0.0', '1.399', '0.0', '0.0', '0.149', '1.389', '1.24', '0.0', '0.16', '0.0', '0.680', '0.0', '0.0', '1.78', '1.05', '0.0', '0.0', '0.0', '0.0', '1.860', '4.080', '3.009', '0.140', '0.0', '0.38', '0.0', '0.0', '0.0', '0.0', '0.0', '2.189', '0.0', '0.0', '3.200', '1.919', '0.0', '0.0', '4.950', '0.0', '0.0', '0.0', '0.0', '0.0', '0.0']
With 20% survival (plus an additional 5% of other individuals) and 1% mutation, it only took nine generations to reach a perfect solution. Then the algorithm joyfully runs in circles for as long as you'll let the mutations continue But this is a good feeling right? If it only took us half an hour to solve a problem of this magnitude, imagine what we could do with a day. A genetic algorithm for optimizing your Apache2 configuration file for number of children processes? Easy as pie.
There are a nearly endless variety of techniques for and variations of genetic algorithms, but all of them rest on this straight forward foundation. We'll look more at those sometime in the future, but for now you know enough to go out and throw together something interesting.
Complete Code
"""
# Example usage
from genetic import *
target = 371
p_count = 100
i_length = 6
i_min = 0
i_max = 100
p = population(p_count, i_length, i_min, i_max)
fitness_history = [grade(p, target),]
for i in xrange(100):
p = evolve(p, target)
fitness_history.append(grade(p, target))
for datum in fitness_history:
print datum
"""
from random import randint, random
from operator import add
def individual(length, min, max):
'Create a member of the population.'
return [ randint(min,max) for x in xrange(length) ]
def population(count, length, min, max):
"""
Create a number of individuals (i.e. a population).
count: the number of individuals in the population
length: the number of values per individual
min: the minimum possible value in an individual's list of values
max: the maximum possible value in an individual's list of values
"""
return [ individual(length, min, max) for x in xrange(count) ]
def fitness(individual, target):
"""
Determine the fitness of an individual. Higher is better.
individual: the individual to evaluate
target: the target number individuals are aiming for
"""
sum = reduce(add, individual, 0)
return abs(target-sum)
def grade(pop, target):
'Find average fitness for a population.'
summed = reduce(add, (fitness(x, target) for x in pop))
return summed / (len(pop) * 1.0)
def evolve(pop, target, retain=0.2, random_select=0.05, mutate=0.01):
graded = [ (fitness(x, target), x) for x in pop]
graded = [ x[1] for x in sorted(graded)]
retain_length = int(len(graded)*retain)
parents = graded[:retain_length]
# randomly add other individuals to
# promote genetic diversity
for individual in graded[retain_length:]:
if random_select > random():
parents.append(individual)
# mutate some individuals
for individual in parents:
if mutate > random():
pos_to_mutate = randint(0, len(individual)-1)
# this mutation is not ideal, because it
# restricts the range of possible values,
# but the function is unaware of the min/max
# values used to create the individuals,
individual[pos_to_mutate] = randint(
min(individual), max(individual))
# crossover parents to create children
parents_length = len(parents)
desired_length = len(pop) - parents_length
children = []
while len(children) < desired_length:
male = randint(0, parents_length-1)
female = randint(0, parents_length-1)
if male != female:
male = parents[male]
female = parents[female]
half = len(male) / 2
child = male[:half] + female[half:]
children.append(child)
parents.extend(children)
return parents