I have a schedule generation task, which, according to this question, could be solved with help of genetic algorithm.
I've run through Google search and found many very useful literature and two "Hello World!" examples. So far, I've tried to translate them into php, and reincapsulate to make code reusable for my future tasks.
Here are the links of examples on C++ and on Java (sorry, last one is on russian, but still, code from there might be useful).
Here is my implementation:
<?php
abstract class Creature
{
protected $fitness;
public function __construct()
{
$this->fitness = 0;
}
public function getFitness()
{
return $this->fitness;
}
abstract public function calculateFitness();
public function compareTo($creature)
{
return $this->fitness - $creature->fitness;
}
abstract public function mateWith($creature);
abstract public function mutate();
}
abstract class Population
{
protected $creatures;
protected $generation;
public function __construct()
{
$this->creatures = array();
$this->generation = 1;
$this->populate();
}
public function __destruct()
{
unset($this->creatures);
}
public function get($index)
{
return isset($this->creatures[$index]) ? $this->creatures[$index] : null;
}
public function getCount()
{
return count($this->creatures);
}
public function getGeneration()
{
return $this->generation;
}
abstract protected function populate();
public function sort($order = SORT_ASC)
{
switch($order)
{
case SORT_ASC:
$fn = function($c1, $c2){ return $c1->compareTo($c2); };
break;
case SORT_DESC:
$fn = function($c1, $c2){ return $c2->compareTo($c1); };
break;
default: return false;
}
return usort($this->creatures, $fn);
}
public function select(array $params)
{
$result = false;
if(isset($params['top']))
{
$length = round(abs($this->getCount() * $params['top']) / 100);
$this->creatures = array_slice($this->creatures, 0, $length);
$result = true;
}
if(isset($params['fn']) && is_callable($params['fn']))
{
$this->creatures = array_filter($this->creatures, $params['fn']);
$result = true;
}
return $result;
}
public function breed()
{
$candidates = $this->creatures;
shuffle($candidates);
$candidates = array_chunk($candidates, 2);
$result = 0;
foreach($candidates as &$pair)
{
if(count($pair) < 2)continue;
list($mother, $father) = $pair;
$children = $mother->mateWith($father);
$result += count($children);
$this->creatures = array_merge($this->creatures, $children);
}
$this->generation++;
return $result;
}
}
class HWCreature extends Creature
{
protected $string;
protected function randChar()
{
return chr(rand(0, 255));
}
protected function fill()
{
$length = strlen(Algorithm::TARGET);
for($i = 0; $i < $length; $i++)
{
$this->string .= $this->randChar();
}
}
public function __construct($fill = true)
{
parent::__construct();
$this->string = '';
if(!$fill)return;
$this->fill();
$this->calculateFitness();
}
public function __toString()
{
return $this->string;
}
public function calculateFitness()
{
$length = strlen($this->string);
$target = Algorithm::TARGET;
for($i = 0; $i < $length; $i++)
{
$this->fitness += abs(ord($this->string[$i]) - ord($target[$i]));
}
}
public function mateWith($creature)
{
$length = strlen(Algorithm::TARGET) - 1;
$place = rand(0, $length);
$child1 = new self(false);
$child1->string = substr($this->string, 0, $place) . substr($creature->string, $place);
$child1->mutate();
$child1->calculateFitness();
$child2 = new self(false);
$child2->string = substr($creature->string, 0, $place) . substr($this->string, $place);
$child2->mutate();
$child2->calculateFitness();
return array($child1, $child2);
}
public function mutate()
{
if(rand(1, 100) > Algorithm::MUTATION_RATE)return;
$char = $this->randChar();
$length = strlen(Algorithm::TARGET);
$place = rand(0, $length - 1);
$this->string = substr_replace($this->string, $char, $place, 1);
}
}
class HWPopulation extends Population
{
protected function populate()
{
for($i = 0; $i < Algorithm::POPULATION_SIZE; $i++)
{
$this->creatures[] = new HWCreature();
}
}
}
class Algorithm
{
const POPULATION_SIZE = 100; // 1000 in my original test
const ELITE_RATE = 50; // %
const MUTATION_RATE = 25; // %
const MAX_GENERATIONS = 1000;
const TARGET = 'Hello World!';
protected $population;
public function __construct()
{
$this->population = new HWPopulation();
}
public function __destruct()
{
unset($this->population);
}
public function __invoke()
{
do
{
$generation = $this->population->getGeneration();
$representer = $this->population->get(0);
echo sprintf(
'gen %d > %s',
$generation, $representer
),
'<br>',
PHP_EOL;
if($representer == self::TARGET)break;
$selector = array('top' => self::ELITE_RATE);
$this->population->sort();
$this->population->select($selector);
$this->population->breed();
}
while($generation < self::MAX_GENERATIONS);
}
}
$algorithm = new Algorithm();
$algorithm();
unset($algorithm);
?>
However, my results on 16Gb RAM machine with i7 @ 2.4 GHz CPU are:
...
gen 739 > HfkkoWotlc!
gen 740 > HfkkoWotlc!
gen 741 > HfkkoWotlc!
gen 742 > HfkkoWotlc!
gen 743 > HfkkoWotlc!
gen 744 > HfkkoWotlc!
gen 745 > HfkkoWotlc!
Fatal error: Maximum execution time of 30 seconds exceeded in {script} on line 126
So, looks like it is extremely inefficient. I believe, that problem might be in selection or breeding strategy... And I'm completely lost there.
Could anyone, please, explain, why is this happening? Also, am I doing something wrong by mating only elite group of genes / creatures?
Any help will be appreciated.
For debugging/testing at least you may need to run the algorithm for a long time so you should increase the value of max_execution_time in php.ini (or use the set_time_limit function).
There seems to be some confusion in terminology in your code. From a very brief glance you don't appear to have implemented elitism. What you seem to have is truncation selection. Is it wrong to select parents in this way? Well it's often sub-optimal as it completely discards the weaker candidates, which although not viable themselves, may contain genetic material that could contribute to the final solution. In this simple example it probably doesn't matter, but in general you may find a fitness-proportionate selection strategy, such as Roulette Wheel Selection, to be more effective. Such strategies favour the stronger individuals but permit the possibility of weaker candidates being selected as parents.
If you want to implement elitism, you should copy the elite candidates unmodified into the next generation and then breed the rest of the that generation by selecting parents from the entire current generation (including the elite individuals). The percentage of candidates preserved via elitism should be about 5% (you can experiment to find the best ratio).
Some other observations: