Genetic_Algorithm_Example.txt


Untitled Document



 13) ) 
					continue;
				else
				{
					$bOperator		= false;
					$buffer[$cBuff++] = $this_gene;
					continue;
				}
			}
			
			//find a gene which represents a number
			else
			{
				if ($this_gene > 9)
					continue;
				else
				{
					$bOperator		= true;
					$buffer[$cBuff++] = $this_gene;
					continue;
				}
			}
			
		}//next gene
	
		//	now we have to run through buffer to see if a possible divide by zero
		//	is included and delete it. (ie a '/' followed by a '0'). We take an easy
		//	way out here and just change the '/' to a '+'. This will not effect the 
		//	evolution of the solution
		for ($i=0; $i < $cBuff; $i++)
		{
			if (($buffer[$i] == 13) && ($buffer[$i + 1] == 0))
				$buffer[$i] = 10;
		}
	
		return $cBuff;
	}
	
	function AssignFitness($bits, $target_value)
	{
	
		//holds decimal values of gene sequence
		$buffer = array((int)(CHROMO_LENGTH / GENE_LENGTH));
	
		$num_elements = ParseBits($bits, $buffer);
		
		// ok, we have a buffer filled with valid values of: operator - number - operator - number..
		// now we calculate what this represents.
		$result = 0.0;
	
		for ($i=0; $i < $num_elements-1; $i+=2)
		{
			switch ($buffer[$i])
			{
				case 10:
	
					$result += $buffer[$i + 1];
					break;
	
				case 11:
					
					$result -= $buffer[$i + 1];
					break;
	
				case 12:
	
					$result *= $buffer[$i + 1];
					break;
	
				case 13:
		
					$result /= $buffer[$i + 1];
					break;
	
			}//end switch
	
		}
	
		// Now we calculate the fitness. First check to see if a solution has been found
		// and assign an arbitarily high fitness score if this is so.
	
		if ($result == (float)$target_value)
	
			return 999.0;
	
		else
	
			return 1/(float)abs((double)($target_value - $result));
		//	return result;
	}

	
	// chromosome Class
	class chromo
	{
		var $bits;
		var $fitness;
		
		function chromo($start_bits = "", $start_fitness = 0.0)
		{
			$this->bits = $start_bits;
			$this->fitness = $start_fitness;
		}
		
		function GetRandomBits()
		{
			// clear the bits
			$this->bits = "";
			
			for($i = 0; $i < CHROMO_LENGTH; $i++)
			{
				$r = rand(0, RAND_MAX) / (RAND_MAX + 1);
				//echo $r."
"; if($r > 0.5) $this->bits .= "1"; else $this->bits .= "0"; } } function ToDec($start = 0, $stop = 0) { $val = 0; $value_to_add = 1; // convert the whole string if($start == $stop) { for ($i = strlen($this->bits); $i > 0; $i--) { if ($this->bits[($i - 1)] == '1') $val += $value_to_add; $value_to_add *= 2; } } else { $str = substr($this->bits, $start, $stop); for ($i = strlen($str); $i > 0; $i--) { if ($str[($i - 1)] == '1') $val += $value_to_add; $value_to_add *= 2; } } return $val; } function PrintChromo() { //holds decimal values of gene sequence $buffer = array((int)(CHROMO_LENGTH / GENE_LENGTH)); //parse the bit string $num_elements = ParseBits($this->bits, &$buffer); for ($i=0; $i < $num_elements; $i++) { PrintGeneSymbol($buffer[$i]); } return; } } // end class chromo function Mutate($bits = "") { for ($i=0; $i < strlen($bits); $i++) { if ((rand(0, RAND_MAX) / (RAND_MAX + 1)) < MUTATION_RATE) { if ($bits[$i] == '1') $bits[$i] = '0'; else $bits[$i] = '1'; } } return; } function Crossover(&$offspring1, &$offspring2) { //dependent on the crossover rate if ((rand(0, RAND_MAX) / (RAND_MAX + 1)) < CROSSOVER_RATE) { //create a random crossover point $crossover = (int) ((rand(0, RAND_MAX) / (RAND_MAX + 1)) * CHROMO_LENGTH); $t1 = substr($offspring1, 0, $crossover) . substr($offspring2, $crossover, CHROMO_LENGTH); $t2 = substr($offspring2, 0, $crossover) . substr($offspring1, $crossover, CHROMO_LENGTH); $offspring1 = $t1; $offspring2 = $t2; } } function Roulette($total_fitness, &$Population) { //generate a random number between 0 & total fitness count $Slice = (float)((rand(0, RAND_MAX) / (RAND_MAX + 1)) * $total_fitness); //go through the chromosones adding up the fitness so far $FitnessSoFar = 0.0; for ($i = 0; $i < POP_SIZE; $i++) { $FitnessSoFar += $Population[$i]->fitness; //if the fitness so far > random number return the chromo at this point if ($FitnessSoFar >= $Slice) return $Population[$i]->bits; } return ""; } function BinToDec($bits) { $val = 0; $value_to_add = 1; for ($i = strlen($bits); $i > 0; $i--) { if ($bits[($i - 1)] == '1') $val += $value_to_add; $value_to_add *= 2; } return $val; } function PrintGeneSymbol($val) { if ($val < 10 ) echo $val." "; else { switch ($val) { case 10: "+"; break; case 11: echo "-"; break; case 12: echo "*"; break; case 13: echo "/"; break; }//end switch echo " "; } return; } $Population = array(POP_SIZE); for ($i=0; $iGetRandomBits(); $Population[$i]->fitness = 0.0; } $GenerationsRequiredToFindASolution = 0; $bFound = false; while(!$bFound) { $TotalFitness = 0.0; for($i=0; $ifitness = AssignFitness($Population[$i]->bits, $Target); $TotalFitness += $Population[$i]->fitness; } // check to see if we have found any solutions (fitness will be 999) for ($i=0; $ifitness == 999.0) { echo "Solution found in ".$GenerationsRequiredToFindASolution." generations!
"; $Population[$i]->PrintChromo(); $bFound = true; break; } } $temp = array(POP_SIZE); for ($i=0; $iGetRandomBits(); $temp[$i]->fitness = 0.0; } $cPop = 0; //loop until we have created POP_SIZE new chromosomes while ($cPop < POP_SIZE) { // we are going to create the new population by grabbing members of the old population // two at a time via roulette wheel selection. $offspring1 = Roulette($TotalFitness, $Population); $offspring2 = Roulette($TotalFitness, $Population); //add crossover dependent on the crossover rate Crossover($offspring1, $offspring2); //now mutate dependent on the mutation rate Mutate($offspring1); Mutate($offspring2); //add these offspring to the new population. (assigning zero as their //fitness scores) $temp[$cPop++] = new chromo($offspring1, 0.0); $temp[$cPop++] = new chromo($offspring2, 0.0); }//end loop for ($i=0; $i MAX_ALLOWABLE_GENERATIONS) { echo "No solutions found this run!"; $bFound = true; } } ?>