There’s a really good example/explanation of genetic algorithms over here
These are the things that were used to make the image I was going on about here a while back. A cool way of getting from A to B with particular relevence to robotics etc.
Anyway, if anyone’s interested I’ve had a first hacky go at putting a PHP version together. It’s not terribly optimised code, and I’m not sure if I’ve got it 100% right because I’m not fluent in Python, which is what the original was written in… but it does seem to work. A fair bit of tweakage can be done with the mutation rates etc, but… well, c’mon. It’s 4am.
If you want to download it, there’s a zip here
(edit) : there’s a streamlined (and far more efficient) version here
/*
|----------------------------------------------------------------------------------------------------------------------------------
| genetic Algorithm
|----------------------------------------------------------------------------------------------------------------------------------
|
| First hacky attempt at a genetic Algorithm, based upon :
| http://lethain.com/entry/2009/jan/02/genetic-algorithms-cool-name-damn-simple/
|
| nick@tangerineworks.com :: 04/01/2009
| http://www.genomicon.com
| http://www.tangerineworks.com
|
*/
$g=new geneticAlgorithm();
$population=$g->makePopulation();
$history=array($g->grade($population));
for ($i=0; $i<100 ;$i++){
$population=$g->evolve($population);
$grade=$g->grade($population);
$history[]=$g->grade($population);
if (!$grade) break;
}
print_r($history);
foreach($population as $i){
print implode(',',$i).'='.array_sum($i).'
';
}
/*
|----------------------------------------------------------------------------------------------------------------------------------
| class : geneticAlgorithm
|----------------------------------------------------------------------------------------------------------------------------------
|
|
*/
class geneticAlgorithm{
var $target=200; // number we're trying to get the genes to add up to
var $len=5; // number of genes in an individual
var $minVal=0; // the range of values a gene can be
var $maxVal=99;
var $populationSize=20; // population size
var $numToRetain=5; // this must be smaller than the population
var $mutateChancePercent=10; // percentage chance of a mutation
var $randomSelectChancePercent=5; // percentage chance of a non-optimal shag
/*
|----------------------------------------------------------------------------------------------------------------------------------
| initialise
|----------------------------------------------------------------------------------------------------------------------------------
|
|
*/
function geneticAlgorithm(){
srand(time());
}
/*
|----------------------------------------------------------------------------------------------------------------------------------
| makeIndividual
|----------------------------------------------------------------------------------------------------------------------------------
|
|
*/
function makeIndividual(){
for ($i=0; $i<$this->len ;$i++){
$individual[]=rand($this->minVal,$this->maxVal);
}
return $individual;
}
/*
|----------------------------------------------------------------------------------------------------------------------------------
| makePopulation
|----------------------------------------------------------------------------------------------------------------------------------
|
|
*/
function makePopulation(){
for ($i=0; $i<$this->populationSize ;$i++){
$population[]=$this->makeIndividual();
}
return $population;
}
/*
|----------------------------------------------------------------------------------------------------------------------------------
| mutate
|----------------------------------------------------------------------------------------------------------------------------------
|
|
*/
function mutate($individual){
if (rand(1,100)<=$this->mutateChancePercent) {
$individual[rand(0,$this->len-1)]=rand($this->minVal,$this->maxVal);
}
return $individual;
}
/*
|----------------------------------------------------------------------------------------------------------------------------------
| breed
|----------------------------------------------------------------------------------------------------------------------------------
|
| breeds a couple, with a chance of a random mutation
|
*/
function breed($father, $mother){
// if ($father==$mother) return false; // this was causing timeouts because sometimes they're al the same.
for ($i=0; $imutate($child);
return $child;
}
/*
|----------------------------------------------------------------------------------------------------------------------------------
| test
|----------------------------------------------------------------------------------------------------------------------------------
|
| tests an individual against the the target
|
*/
function test($individual){
return abs($this->target-array_sum($individual));
}
/*
|----------------------------------------------------------------------------------------------------------------------------------
| grade
|----------------------------------------------------------------------------------------------------------------------------------
|
| grades an entire population
|
*/
function grade($population){
foreach($population as $individual){
$summed=$summed+$this->test($individual);
}
$average=round($summed/count($population),1);
return $average;
}
/*
|----------------------------------------------------------------------------------------------------------------------------------
| evolve
|----------------------------------------------------------------------------------------------------------------------------------
|
| evolves an entire population
|
*/
function evolve($population){
// sort according to fittest
$n=1;
foreach($population as $individual) {
$key=$this->test($individual) . (0.001*$n++);
$graded[$key]=$individual;
}
ksort($graded);
// choose the fittest
$n=1;
foreach($graded as $individual){
$parents[]=$individual;
$newGeneration[]=$individual;
if ($n++>=$this->numToRetain) break;
}
// randomly add remaining individuals to promote genetic diversity (every dog has his day)
krsort($graded);
$n=count($population)-1;
foreach($graded as $individual){
if (rand(1,100)<=$this->randomSelectChancePercent){
$parents[]=$individual;
$newGeneration[]=$individual;
}
if ($n--<$this->numToRetain) break;
}
// go get the new generation
while(count($newGeneration)breed($parents[rand(0,count($parents)-1)],$parents[rand(0,count($parents)-1)]);
if ($shag!=false) $newGeneration[]=$shag;
}
return $newGeneration;
}
}
?>
What this particular example does is to try to find a group of number-lists that add up to 200, by choosing lists of random numbers and “breeding” them, then selecting the ones that work best. What you end up with is something that looks like this:
(accuracy of each iteration)
Array
(
[0] => 60.6
[1] => 40.7
[2] => 28.9
[3] => 11.8
[4] => 8.4
[5] => 5.3
[6] => 1.9
[7] => 0.2
[8] => 0.2
[9] => 0.1
[10] => 0
)
(final result)
33,27,59,64,17=200
33,27,59,64,17=200
33,27,59,64,17=200
33,27,59,64,17=200
33,27,59,64,17=200
33,27,59,64,17=200
33,27,59,64,17=200
33,27,59,64,17=200
33,27,59,64,17=200
33,27,59,64,17=200
33,27,59,64,17=200
33,27,59,64,17=200
33,27,59,64,17=200
33,27,59,64,17=200
33,27,59,64,17=200
33,27,59,64,17=200
33,27,59,64,17=200
33,27,59,64,17=200
33,27,59,64,17=200
33,27,59,64,17=200
I haven’t set it up to chose different lists so it’s zeroing on on the same one… it doesn’t always do this though. In this example it’s taken 10 steps to get to its target… the top list represents the accuracy of the attempt… with 0 being 100% right. You can tweak the values for mutation, mortality etc.
Seems like a daft thing to want to do, but imagine if you’re trying to do something really complex like getting an auto-piloted plane to fly level… it’s a hell of a lot easier to do something like this, and I have a feeling you’ll wind up with a far more adaptable and faster bit of code.
So there you go. This is an example of a fairly complex meme spreading… leaping from one language to another in a matter of hours… and as I said in the previous post on this subject, it’s of particular interest because it is a codified example of artificial natural selection. Machine learning and all that.
