<?php
/*
Binary Genetic Algorithm Class.
Version: 1.0.0
Copyright (C) 2008 Afshin Safarpour
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
Copy of GNU Lesser General Public License at: http://www.gnu.org/copyleft/lesser.txt
Contact author at: hide@address.com
*/
class individual
{
var $fitness_value;
var $gene_value;
var $birth_date;
function set($g_val,$f_val,$d_val)
{
$this->fitness_value = $f_val;
$this->gene_value = $g_val;
$this->birth_date = $d_val;
}
function crossOver($p1,$p2)
{
$rNumber=rand(1,15);
$this->gene_value = substr($p1->gene_value,0,$rNumber) . substr($p2->gene_value,$rNumber);
}
function mutate()
{
if(rand(1,5)==3)//this is only for probability , this function should not execute for all calls
{
$rNumber=rand(0,15);
$this->gene_value[$rNumber]=1-$this->gene_value[$rNumber];
}
}
}
class GA
{
var $population; //initial population
var $totalGeneration;
var $fitnessFunction; //string
var $lowerBound;
var $upperBound;
var $arr_individual; //array
var $arr_offspring; //array
var $date; //counter for today date
var $currentGeneration;
var $file_name;
var $arr_avefitness ; //for graph
var $counter_arr_avefitness ;
function GA()
{
$this->date = 1;
$this->currentGeneration = 0;
$this->counter_arr_avefitness = 0;
}
function create16Bit()
{
$string1 = "";
for($i=1;$i<=16;$i++)
$string1 .= floor(lcg_value()*1.99999999999);
return ($string1);
}
function fitness($x)
{
$x = bindec($x);
//----------------------
$x = ( ( ($this->upperBound - $this->lowerBound) / pow(2,16) ) * $x) + $this->lowerBound;
//----------------------
$f_str = $this->fitnessFunction ;
$result = 0;
$f_str = split(',',$f_str);
$size_fitness = count($f_str);
for($i=0 , $j=($size_fitness-1) ; $i<$size_fitness ; $i++ , $j--)
{
$result += $f_str[$i] * (pow($x,$j));
}
return ($result);
}
function buildFirstGeneration()
{
for ($i=1 ; $i<=$this->population ; $i++)
{
$indiv = new individual();
$g_value = $this->create16Bit();
$f_value = $this->fitness($g_value);
$indiv->set($g_value,$f_value,$this->date);
$this->arr_individual[$i]=$indiv;
$this->date++;
}
$this->currentGeneration++;
}
function buildChilds()
{
for ($i=1 ; $i<=$this->population ; $i++)
{
$indiv = new individual();
$parents = $this->selectParents();
$indiv->crossOver($parents[0],$parents[1]);
$indiv->mutate();
$f_value=$this->fitness($indiv->gene_value);
$indiv->set($indiv->gene_value,$f_value,$this->date);
$this->arr_offspring[$i]=$indiv;
$this->date++;
}
$this->currentGeneration++;
$this->arr_individual = $this->arr_offspring;
}
function selectParents()
{
//sort the individual array
for($i=0 ; $i<=$this->population ; $i++)
{
for($j=i+1 ; $j<$this->population ; $j++)
{
if( $this->arr_individual[$i]->fitness_value > $this->arr_individual[$j]->fitness_value )
{
$temp1 = $this->arr_individual[$i];
$this->arr_individual[$i] = $this->arr_individual[$j];
$this->arr_individual[$j] = $temp1;
}
}
}
//----------
$randTopNumber=floor(lcg_value() * ($this->population / 2))+1;
$randAllNumber=floor(lcg_value() * $this->population)+1;
while($randAllNumber == $randTopNumber)
$randAllNumber=floor(lcg_value() * $this->population)+1;
$indiv1 = $this->arr_individual[$randTopNumber];
$indiv2 = $this->arr_individual[$randAllNumber];
return array($indiv1, $indiv2);
}
function debug()
{
if(file_exists($this->file_name))
{
unlink($this->file_name);
}
$this->showHeader();
$this->buildFirstGeneration();
$this->showThisGeneration($this->arr_individual);
$this->writeFile($this->arr_individual);
for($i=($this->currentGeneration+1) ; $i<=($this->totalGeneration) ; $i++)
{
$this->buildChilds();
$this->showThisGeneration($this->arr_individual);
$this->writeFile($this->arr_individual);
}
}
function showThisGeneration($arr_val)
{
$sumFitness = 0;
for($i=1 ; $i<=$this->population ; $i++)
{
$sumFitness += $arr_val[$i]->fitness_value;
}
$averageFitness = $sumFitness / $this->population;
//------- max and min fitness
$max_fitness = $arr_val[1]->fitness_value;
$min_fitness = $arr_val[1]->fitness_value;
for($i=2 ; $i<=$this->population ; $i++)
{
if($max_fitness < $arr_val[$i]->fitness_value)
$max_fitness = $arr_val[$i]->fitness_value;
if($min_fitness > $arr_val[$i]->fitness_value)
$min_fitness = $arr_val[$i]->fitness_value;
}
//for graph
$this->arr_avefitness[$this->counter_arr_avefitness++]=$averageFitness;
//end
print ("<p>\n");
print ("Population data after " . ($this->population * $this->currentGeneration) . " births (generation " . $this->currentGeneration . ")<br />");
print ("Local fitness : max = " . $max_fitness . " , ave = " . $averageFitness . " , min = " . $min_fitness . "<br />" );
print ("<table width='35%' style='font-family:Tahoma;font-size:12px;'>\n");
print ("<tr><td><b>Indiv</b></td><td><b>birthdate</b></td><td><b>fitness</b></td><td><b>gene value</b></td></tr>\n");
for($i=1;$i<=$this->population;$i++)
{
print ("<tr>");
print ("<td>" . $i ."</td>");
print ("<td>" . $arr_val[$i]->birth_date . "</td>");
print ("<td>" . $arr_val[$i]->fitness_value . "</td>");
print ("<td>" . $arr_val[$i]->gene_value . "</td>");
print ("</tr>\n");
}
print ("</table>\n");
print ("</p>\n");
}
function showHeader()
{
print("<b>GA</b><br>");
print("<b>Simulation time limit (# births): " . $this->totalGeneration*$this->population . "</b><br />");
print("<b>Using a parabolic landscape defined on 1 parameter(s) with</b><br />");
print(" <b>parameter initialization bound of :</b><br />");
print(" <b>1 : " . $this->lowerBound . " " . $this->upperBound . "</b><br />");
print("<b>Using a genome with 16 binary genes .</b><br />");
print("<b>Using 1-point crossover </b><br />");
print("<b>Using randomly bit-flip mutation </b><br />");
print("<b>Parent population size : " . $this->population . " Offspring population size : " . $this->population . "</b><br />");
print("<center><input type='button' style='width:70px;font-size:12px;font-family:Tahoma;' value='back' onclick='window.history.back();' ></center><br/>");
print("<hr width='70%' align='left' /><br />");
}
function writeFile($arr_val)
{
$sumFitness = 0;
for($i=1 ; $i<=$this->population ; $i++)
{
$sumFitness += $arr_val[$i]->fitness_value;
}
$averageFitness = $sumFitness / $this->population;
$c_text = "Population data after " . ($this->population * $this->currentGeneration) . " births (generation " . $this->currentGeneration . ")\r\n";
$c_text .= "Local fitness : max = " . $arr_val[1]->fitness_value . " , ave = " . $averageFitness . " , min = " . $arr_val[$this->population]->fitness_value . "\r\n" ;
$c_text .= "Indiv birthdate fitness gene value\r\n";
for($i=1;$i<=$this->population;$i++)
{
$c_text .= $i . " " . $arr_val[$i]->birth_date . " " . $arr_val[$i]->fitness_value . " " . $arr_val[$i]->gene_value . "\r\n";
}
$c_text .= "--------------------------------------------------------------------------------\r\n";
$handle = fopen ($this->file_name, "a+");
fwrite($handle, $c_text);
fclose ($handle);
}
}
?>