Location: PHPKode > scripts > Binary GA > binary-ga/ga.class.php
<?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("&nbsp;&nbsp;&nbsp;&nbsp;<b>parameter initialization bound of :</b><br />");
		print("&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<b>1 : " . $this->lowerBound . "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;" . $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 . " &nbsp;&nbsp;&nbsp;&nbsp; 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);
		
	}
	
}
?>
Return current item: Binary GA