Created
December 16, 2014 23:44
-
-
Save masudianpour/5393a70d7f9856a98b63 to your computer and use it in GitHub Desktop.
DE (Differential Evolution) Algorithm implementation in PHP
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <?php | |
| /** | |
| * DE[Differential Evolution] Algorithm implementation | |
| * | |
| * ############################################################################# | |
| * #FUNCTION: <Booth's function> | |
| * #EQUATION: <f(x,y)=(x+2y-7)^2 + (2x+y-5)^2> | |
| * #MINIMUM: <f(1,3)=0> | |
| * #SEARCH DOMAIN: < -10<=x,y<=10 > | |
| * @link http://en.wikipedia.org/wiki/Test_functions_for_optimization the function link | |
| * ############################################################################# | |
| * | |
| * @author Ali MasudianPour <[email protected]> | |
| */ | |
| class Problem { | |
| /* @var DIMENSION Problem problem dimension */ | |
| const DIMENSION = 2; | |
| /* @var MAX_VALUE Problem maximum value for x,y */ | |
| const MAX_VALUE = 10; | |
| /* @var MAX_VALUE Problem maximum value for x,y */ | |
| const MIN_VALUE = -10; | |
| /** | |
| * fitness function <Booth's function> | |
| * | |
| * @param integer $x x | |
| * @param integer $y y | |
| * @return integer the function result | |
| */ | |
| protected function fitnessFunction($x, $y) { | |
| return pow(($x + (2 * $y) - 7), 2) + pow(((2 * $x) + $y - 5), 2); | |
| } | |
| } | |
| class De extends Problem { | |
| // As original paper says: F is a real and constant factor 2 [0, 2] | |
| const F = 0.7; | |
| //As original paper says: CR is the crossover constant 2 [ 0 ; 1 ] | |
| const CR = 0.9; | |
| //max iteration | |
| const MAX_ITERATION = 1000; | |
| //number of individuals | |
| const INDIVIDUALS = 50; | |
| //best index | |
| private $bestIndex; | |
| //populaton | |
| private $population; | |
| //all population's costs [Fitness] | |
| private $cost; | |
| /** | |
| * Constructor function | |
| * all initializations take place in the following method | |
| */ | |
| public function __construct() { | |
| $this->bestIndex = 0; //initial best index is 0 | |
| for ($i = 0; $i < self::INDIVIDUALS; $i++) { | |
| for ($j = 0; $j < Problem::DIMENSION; $j++) { | |
| //random numbers between min and max of PROBLEM | |
| $this->population[$i][$j] = rand(Problem::MIN_VALUE, Problem::MAX_VALUE); | |
| } | |
| //calculation of fitness | |
| $fitness = $this->fitnessFunction($this->population[$i][0], $this->population[$i][1]); | |
| //putting the fitness into cost array | |
| $this->cost[$i] = $fitness; | |
| //updating best index | |
| $this->bestIndex = $fitness < $this->fitnessFunction($this->population[$this->bestIndex][0], $this->population[$this->bestIndex][1]) ? $i : $this->bestIndex; | |
| } | |
| } | |
| private function getPopulationCount() { | |
| return count($this->population); | |
| } | |
| public function run() { | |
| $generation = 1; | |
| //main loop | |
| while ($generation != self::MAX_ITERATION && !$this->checkTermination()) { | |
| //to make output more beautiful -- some sleep :) | |
| usleep(10000); | |
| echo "GENERATION [{$generation}]\t BEST INDEX : [{$this->bestIndex}]\t BEST X = [{$this->population[$this->bestIndex][0]}]\t BEST Y = [{$this->population[$this->bestIndex][1]}]\n"; | |
| //a loop through population | |
| for ($i = 0; $i < count($this->population); $i++) { | |
| //a random index | should not be equal to current index | |
| do { | |
| $a = rand(0, $this->getPopulationCount() - 1); | |
| } while ($a == $i); | |
| //a random index|should not be equal to current index and $a | |
| do { | |
| $b = rand(0, $this->getPopulationCount() - 1); | |
| } while ($b == $i || $b == $a); | |
| //a random index|should not be equal to current index and $a and $b | |
| do { | |
| $c = rand(0, $this->getPopulationCount() - 1); | |
| } while ($c == $i || $c == $a || $c == $b); | |
| //random dimension | |
| $j = rand(0, Problem::DIMENSION - 1); | |
| for ($k = 0; $k < Problem::DIMENSION; $k++) { | |
| //just the same as paper equation | |
| if ($this->frand(0, 1) < self::CR || $k == (Problem::DIMENSION - 1)) { | |
| $trial[$j] = $this->population[$c][$j] + self::F * ($this->population[$a][$j] - $this->population[$b][$j]); | |
| } else { | |
| $trial[$j] = $this->population[$i][$j]; | |
| } | |
| //if dimension was 0 then 1 else 0 | |
| $j = $j == 1 ? 0 : 1; | |
| } | |
| //fitness calculation | |
| $fitness = $this->fitnessFunction($trial[0], $trial[1]); | |
| //updating temp array and costs[fitness][best] | |
| if ($fitness <= $this->cost[$i]) { | |
| $this->cost[$i] = $fitness; | |
| for ($j = 0; $j < Problem::DIMENSION; $j++) { | |
| $secondaryArray[$i][$j] = $trial[$j]; | |
| } | |
| } else { | |
| //if fitness was more than old fitness, nothing, just replacing the old values | |
| for ($j = 0; $j < Problem::DIMENSION; $j++) { | |
| $secondaryArray[$i][$j] = $this->population[$i][$j]; | |
| } | |
| } | |
| } | |
| //updating all individuals with temp array | |
| for ($i = 0; $i < $this->getPopulationCount(); $i++) { | |
| for ($j = 0; $j < Problem::DIMENSION; $j++) { | |
| $this->population[$i][$j] = $secondaryArray[$i][$j]; | |
| } | |
| } | |
| //updaring the best index | |
| for ($i = 0; $i < count($this->cost); $i++) { | |
| $this->bestIndex = $this->cost[$i] < $this->fitnessFunction($this->population[$this->bestIndex][0], $this->population[$this->bestIndex][1]) ? $i : $this->bestIndex; | |
| } | |
| //next generation | |
| $generation++; | |
| } | |
| } | |
| /** | |
| * to produce a float random value | |
| * @param float $min minimum range | |
| * @param float $max maximum range | |
| * @return float generated random value | |
| */ | |
| public function frand($min, $max) { | |
| return $min + lcg_value() * (abs($max - $min)); | |
| } | |
| /** | |
| * check termination | |
| * @return boolean whether to terminate or not | |
| */ | |
| public function checkTermination() { | |
| return $this->fitnessFunction($this->population[$this->bestIndex][0], $this->population[$this->bestIndex][1]) == 0 ? TRUE : FALSE; | |
| } | |
| } | |
| //new instance from DE class | |
| $test = new De(); | |
| //running the algorithm | |
| $test->run(); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment