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.
On Addiction
And The Void Mooned Back...
The Spirit Of The World
A Machine to Steal Souls
More Anti Digital
Thync
Robotic Sensory Loops and Whatnot
Cartestian Robot Roundup.
Post-Scarcity Link-Dump
Servo Bender
What this seems to do is get very close to the goal… ie: get a stable population that are of equal merit but still not quite right (and these are often the same “solution”), then wait until a mutation finally hits on the correct value… so the type of mutation is quite important.
In the streamlined zip version above, I’ve changed the mutation from being just another random number to a random 1 or -1, which makes it far more efficient.
I also assumed from the original example that what was required was an entire population of correct results rather than just a single correct result – either are valid, but the streamlined version stops when it gets to the first correct result.
You can also tweak the efficiency by changing the mutation and population sizes. I think I might make one of these that tests the inputs of another one of these to see which is the optimal combination.