<? // -*-Mode: c++;-*-
/*
PhpGa - PHP Genetic Algorithm Class Library
Copyright (C) 2000 Bill C. White
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
/*
PhpGa.inc - Bill White - 7/19/00
This class is used to perform genetic optimization of binary strings. It is
based on a the simple genetic algorithm as described by David Goldberg in
"Genetic Algorithms in Search, Optimization and Machine Learning" (1989).
7/30/00 - Working (?) with binary tournament selection and no mutation.
*/
if(defined("_Php_Ga_inc_"))
return;
define("_Php_Ga_inc_", 1);
// currently the GA supports only bit string genomes
include("include/BitString.inc");
include("include/PhpGaLimits.inc");
class PhpGa
{
// class data members
// set this flag to "1" for debugging output
var $debug = 0;
// GA parameters
var $bitStringLength = 8;
var $populationSize = 10;
var $pCrossover = 0.9;
var $pMutation = 0.0;
var $population = array();
var $selectionMethod = "rouletteWheelSelection";
// GA processing
var $curGeneration = 0;
var $numGenerationsToRun = 10;
var $parents = array();
// population statistics - 7/22/00
var $fitnessValues = array();
var $fitnessSum = 0; // used in roulette wheel selection - 8/2/00
var $popMean;
var $popStdDev;
var $popVar;
// class methods
/****************************************************************************
* PhpGa - constructor
*
* $stringLength = length of binary string being optimized
*/
function PhpGa($stringLength) {
if(($stringLength >= MIN_STRING_LENGTH) && ($stringLength <= MAX_STRING_LENGTH)) {
$this->bitStringLength = $stringLength;
}
else {
echo "Attempt to set string length to $stringLength. Outside valid range " .
MIN_STRING_LENGTH . " < stringLength < " . MAX_STRING_LENGTH . "<br>\n";
echo "Using default string length: $this->bitStringLength<br>\n";
}
if($this->debug) { echo "In PhpGa constructor: \$bitStringLength = $this->bitStringLength<br>\n"; }
}
/****************************************************************************
* PhpGa - SetPopulationSize
*
* Set the population size
*/
function SetPopulationSize($popSize)
{
if(($popSize > 1) && ($popSize < 100)) {
$this->populationSize = $popSize;
}
else {
echo "Attempt to set population size to $popSize. Outside valid range " .
MIN_POP_SIZE . " < N < " . MAX_POP_SIZE . "<br>\n";
echo "Using default population size: $this->populationSize<br>\n";
}
}
/****************************************************************************
* PhpGa - SetCrossoverRate
*
* Set the crossover rate
*/
function SetCrossoverRate($crossRate)
{
if(($crossRate >= 0.0) && ($crossRate <= 1.0)) {
$this->pCrossover = $crossRate;
}
else {
echo "Attempt to set crossover probability to $crossRate. Outside valid range " .
MIN_P_CROSSOVER . "< pC < " . MAX_P_CROSSOVER . "<br>\n";
echo "Using default crossover probability: $this->pCrossover<br>\n";
}
}
/****************************************************************************
* PhpGa - SetSelectionMethod
*
* Set the mthod to use for selecting parents for the next generationn
*/
function SetSelectionMethod($selectChoice)
{
// ehh, this is not very good design, but it'll do for now - 8/2/00
$this->selectionMethod = $selectChoice;
}
/****************************************************************************
* PhpGa - SetGenerationCount
*
* Set the number of generations to run
*/
function SetGenerationCount($genCount)
{
if(($genCount >= 1) && ($genCount <= 100)) {
$this->numGenerationsToRun = $genCount;
}
else {
echo "Attempt to set generation count to $genCount. Outside valid range " .
MIN_GEN_COUNT . " < genCount < " . MAX_GEN_COUNT . "<br>\n";
echo "Using default generation count: $this->numGenerationsToRun<br>\n";
}
}
/****************************************************************************
* PhpGa - SetDebugFlag
*
* Set the debugging output flag
*/
function SetDebugFlag($flag)
{
if($flag) {
$this->debug = 1;
}
else {
$this->debug = 0;
}
}
/****************************************************************************
* PhpGa - Initialize
*
* Initialize the GA by creating and evaluating the initial (random) population
*/
function Initialize()
{
// seed random number generator
// srand((double) microtime() * 1000000);
mt_srand((double)microtime()*1000000);
// initialize the population with random strings
$this->curGeneration = 0;
for($i=0; $i < $this->populationSize; $i++) {
$bitString = new BitString($this->bitStringLength);
$this->population[$i] = $bitString;
}
$this->EvaluatePopulation();
}
/****************************************************************************
* PhpGa - EvaluatePopulation
*
* Evaluate the fitness of each member of the population and update
* the population statistics
*/
function EvaluatePopulation()
{
// sum the fitnesses
$this->fitnessSum = 0;
for($i=0; $i < $this->populationSize; $i++) {
$this->fitnessValues[$i] = FitnessFunction($this->population[$i]);
$this->fitnessSum += $this->fitnessValues[$i];
}
// mean/average fitness
$this->popMean = $this->fitnessSum / $this->populationSize;
// variance/standard deviation
$SSE = 0;
for($i=0; $i < $this->populationSize; $i++) {
$SSE += (($this->fitnessValues[$i] - $this->popMean)*($this->fitnessValues[$i] - $this->popMean));
}
$this->popVar = $SSE / ($this->populationSize - 1);
$this->popStdDev = sqrt($this->popVar);
}
/****************************************************************************
* PhpGa - PrintPopulation
*
* Print out the bit strings in the population with descriptive fitness statistics
*/
function PrintPopulation()
{
EmitTextBoxHeader("Population at generation $this->curGeneration");
for($i=0; $i < $this->populationSize; $i++) {
$bitString = $this->population[$i];
$bitString->EmitAsHTML();
echo " " . $this->fitnessValues[$i] . "<br>\n";
}
printf("\nPopulation mean: %7.2f<br>\n", $this->popMean);
printf("Population variance: %7.2f<br>\n", $this->popVar);
printf("Population standard deviation: %7.2f<br>\n", $this->popStdDev);
EmitTextBoxFooter();
}
/****************************************************************************
* PhpGa - Step - 7/30/00
*
* Take one step in the population's evolution:
* - grab two parents by "select()"ing them (various selection schemes)
* - reproduce/probabilistic crossover: creates two offspring
* - probabilistic mutation
* - add child(ren) to new population
*/
function Step()
{
if($this->curGeneration < $this->numGenerationsToRun) {
$newPopulation = array();
// select parents: how can we make this variable? switch() on constant?
switch($this->selectionMethod) {
case "rouletteWheelSelection":
$this->SelectParentsByRouletteWheel();
break;
case "binaryTournamentSelection":
$this->SelectParentsByBinaryTournament();
break;
default:
echo "PANIC: Invalid selection method: $this->selectionMethod<br>\n";
exit;
}
if($this->debug) {
for($i=0; $i < count($this->parents); $i++) {
$pi = $this->parents[$i];
$pbs = $this->population[$pi];
$ps = $pbs->myString;
echo "Parent $i: $pi: $ps<br>\n";
}
}
// crossover at pCrossover and add to new population
for($i=0; $i < count($this->parents); $i += 2) {
$index1 = $this->parents[$i];
$index2 = $this->parents[$i+1];
$bitString1 = $this->population[$index1];
$bitString2 = $this->population[$index2];
// if random number exceeds crossover probability
$thisProb = mt_rand(0,1);
if($thisProb <= $this->pCrossover) {
$string1 = $bitString1->myString;
$string2 = $bitString2->myString;
$crossPoint = mt_rand(0, $this->bitStringLength-2);
$s1prefix = substr($string2, 0, $crossPoint+1);
$s2prefix = substr($string1, 0, $crossPoint+1);
$bitString1->myString = $s1prefix . substr($string1, $crossPoint+1, strlen($string1) - $crossPoint - 1);
$bitString2->myString = $s2prefix . substr($string2, $crossPoint+1, strlen($string2) - $crossPoint - 1);
}
// add offspring to new population
$newPopulation[$i] = $bitString1;
$newPopulation[$i+1] = $bitString2;
}
// replace old population with new population
for($i=0; $i < $this->populationSize; $i++) {
$this->population[$i] = $newPopulation[$i];
}
// regenerate population stats
$this->EvaluatePopulation();
$this->curGeneration++;
return 1;
}
else {
return 0;
}
}
/*
##!
### NAME: SelectParentsByBinaryTournament
### PURPOSE: Populates the parents array using binary tournament algorithm
### DATE: 7/30/00
### LAST MODIFIED: 7/30/00
### NOTES: used to generate pairings of parents in PhpGa
### EXPECTS: nothing
### RETURNS: nothing
##!
*/
function SelectParentsByBinaryTournament()
{
$randomIndexes1 = array();
$randomIndexes2 = array();
// initialize the random index arrays
for($i=0; $i < $this->populationSize; $i++) {
$randomIndexes1[$i] = $i;
$randomIndexes2[$i] = $i;
if($this->debug) { echo "[init] $i: $randomIndexes1[$i], $randomIndexes2[$i]<br>\n"; }
}
// shuffle 'em up!
for ($i=0; $i < $this->populationSize-1; $i++) {
/* pick a random array index j in [i,ihi] to swap with */
$j = mt_rand($i, $this->populationSize-1);
$contents = $randomIndexes1[$i];
$randomIndexes1[$i] = $randomIndexes1[$j];
$randomIndexes1[$j] = $contents;
$j = mt_rand($i, $this->populationSize-1);
$contents = $randomIndexes2[$i];
$randomIndexes2[$i] = $randomIndexes2[$j];
$randomIndexes2[$j] = $contents;
}
// if odd number of elements, add one more random index
if(($this->populationSize % 2) == 1) {
$randomIndexes1[$this->populationSize] = mt_rand(0, $this->populationSize-1);
$randomIndexes2[$this->populationSize] = mt_rand(0, $this->populationSize-1);
}
if($this->debug) {
for($i=0; $i < count($randomIndexes1); $i++) {
echo "[shuffled] $i: $randomIndexes1[$i], $randomIndexes2[$i]<br>\n";
}
}
// pair up the parents
unset($this->parents);
$this->parents = array();
for($i=0; $i < count($randomIndexes1); $i += 2) {
if($this->fitnessValues[$randomIndexes1[$i]] > $this->fitnessValues[$randomIndexes1[$i+1]]) {
$this->parents[] = $randomIndexes1[$i];
}
else {
$this->parents[] = $randomIndexes1[$i+1];
}
}
for($i=0; $i < count($randomIndexes2); $i += 2) {
if($this->fitnessValues[$randomIndexes2[$i]] > $this->fitnessValues[$randomIndexes2[$i+1]]) {
$this->parents[] = $randomIndexes2[$i];
}
else {
$this->parents[] = $randomIndexes2[$i+1];
}
}
if($this->debug) {
for($i=0; $i < count($this->parents); $i++) {
$t = $this->parents[$i];
echo "[parents] $i: $t<br>\n";
}
}
}
/*
##!
### NAME: SelectParentsByRouletteWheel
### PURPOSE: Populates the parents array using spins of a "roulette
### wheel"; biased towards individuals with best fitness relative to
### population mean
### DATE: 8/2/00
### LAST MODIFIED: 8/2/00
### NOTES: used to generate pairings of parents in PhpGa
### EXPECTS: nothing
### RETURNS: nothing
##!
*/
function SelectParentsByRouletteWheel()
{
$parentsGenerated = 0;
while($parentsGenerated <= $this->populationSize) {
$partSum = 0.0;
$randNum = 0.0;
$newParentIndex = 0;
$randNum = (mt_rand()/mt_getrandmax()) * $this->fitnessSum;
while(($partSum < $randNum) && ($newParentIndex < $this->populationSize-1)) {
$newParentIndex++;
$partSum += $this->fitnessValues[$newParentIndex] ;
}
$this->parents[$parentsGenerated++] = $newParentIndex;
}
if(($parentsGenerated % 2) == 1) {
$this->parents[$parentsGenerated++] = mt_rand(0, $this->populationSize-1);
}
}
} // end of class definition
?>