A "Hello World!" Genetic Algorithm Example in PHP

This is a hello world example genetic algorithm example written in php. You can use the same algorithm to build useful applications.

Download zip here

The output is something like this:

hello wojed - 0.81818181818182
stay still
mutated unexpectedly!
hello sorhd - 0.81818181818182
stay still
mutated unexpectedly!
hella woryd - 0.81818181818182
stay still
mutated unexpectedly!
hello worpe - 0.81818181818182
stay still
mutated unexpectedly!
hello porbd - 0.81818181818182
stay still
mutated unexpectedly!
hella worfd - 0.81818181818182
stay still
mutated unexpectedly!
hello world - 1
mutated unexpectedly!
hello woead - 0.81818181818182
crossed nothing!
mutated unexpectedly!
mutation
hellxrworzd - 0.72727272727273
hello world found after 1900 try

Here is the class:

 

 

  1. class Gac{
  2.  
  3. const POPULATION_SIZE = 20;
  4. const MUTATION_RATE = 10;
  5. const MUTATION_SIZE = 100;
  6. const SURVIVORS = 10;
  7. const SUCCESS_RATE = 1;
  8. const LETTERS = "abcdefghijklmnopqrstuvwxyz ";
  9. const OFFSPRING = 2;
  10.  
  11. public function Gac($text)
  12. {
  13. $this->text = $text;
  14. $this->lenght = strlen($this->text);
  15. $this->population = 0;
  16. $this->max_rate = 0;
  17. $this->avarage_suc_rate = 0;
  18. $this->best = array();
  19. $this->passed = FALSE;
  20. $this->generations = 0;
  21. }
  22.  
  23. private function check_success($data)
  24. {
  25. $rate = 0;
  26.  
  27. for($i=0;$i<$this->lenght;$i++)
  28. {
  29. $original_letter = substr($this->text,$i,1);
  30. $text_letter = substr($data,$i,1);
  31. if($original_letter == $text_letter)
  32. {
  33. $rate++;
  34. }
  35. }
  36.  
  37. $rate = $rate/$this->lenght;
  38.  
  39. return $rate;
  40. }
  41.  
  42. private function first_population($gene_code)
  43. {
  44. $words = array();
  45. for($i=0;$i<self::POPULATION_SIZE;$i++)
  46. {
  47. $this->population++;
  48. $mutation = TRUE; //this is the first population, so mutate everything
  49.  
  50. $new_ind = $this->generate($gene_code,$mutation);
  51. $words[$i]["word"] = $new_ind["word"];
  52. $words[$i]["rate"] = $new_ind["rate"];
  53. $words[$i]["gene_code"] = $new_ind["gene_code"];
  54.  
  55. echo $new_ind["word"] . " - " . $new_ind["rate"] ."<br>\n";
  56.  
  57. }
  58. echo "end of first generation <br>\n";
  59. echo "----------------------------<br>\n";
  60. array_unique($words);
  61. usort($words, "cmp");
  62. return $words;
  63. }
  64.  
  65. private function kill($genes)
  66. {
  67. if(count($genes)>self::SURVIVORS)
  68. {
  69. $diff = count($genes) - self::SURVIVORS;
  70.  
  71. for($i=0;$i<$diff;$i++)
  72. {
  73. array_pop($genes);
  74. }
  75.  
  76. echo "killed $diff individuals<br>\n";
  77. }
  78.  
  79. return $genes;
  80. }
  81.  
  82. private function populate($genes)
  83. {
  84. $this->generations++;
  85. $new_genes = array();
  86. echo "------------ START OF " . $this->generations . " th GENERATION ----------------<br>\n";
  87. //cross everything
  88. usort($this->best,"cmp");
  89. for($j=0;$j<self::OFFSPRING;$j++)
  90. {
  91. for($i=0;$i<count($genes);$i++)
  92. {
  93. $this->population++;
  94. $best = FALSE;
  95.  
  96. if($genes[$i]["rate"]>=$this->max_rate)
  97. {
  98. $new_gene = $genes[$i]["gene_code"];
  99. $best = TRUE;
  100. echo "stay still<br>";
  101. }
  102. else
  103. {
  104. if($genes[$i]["gene_code"]!==$genes[$i+1]["gene_code"] && $genes[$i+1]["gene_code"])
  105. {
  106. $new_gene = $this->cross($genes[$i]["gene_code"],$genes[$i+1]["gene_code"]);
  107. }
  108. else if($genes[$i]["gene_code"]!==$genes[$i+2]["gene_code"] && $genes[$i+2]["gene_code"])
  109. {
  110. $new_gene = $this->cross($genes[$i]["gene_code"],$genes[$i+2]["gene_code"]);
  111. }
  112. else
  113. {
  114. $new_gene = $genes[$i]["gene_code"];
  115. echo "crossed nothing!<br>\n";
  116. }
  117. }
  118.  
  119. if($new_gene==$genes[$i]["gene_code"] && $i!==0)
  120. {
  121. $new_gene = $this->mutate($new_gene);
  122. echo "<span style='color:red'>mutated unexpectedly!</span><br>\n";
  123. }
  124.  
  125. $mutation = FALSE;
  126.  
  127. if($this->population % self::MUTATION_SIZE == 0)
  128. {
  129. //mutate the new created gene if the mutation size reached
  130. echo "mutation<br>\n";
  131. $mutation = TRUE;
  132. }
  133.  
  134. $new_ind = $this->generate($new_gene,$mutation);
  135. $new_genes[$i]["word"] = $new_ind["word"];
  136. $new_genes[$i]["rate"] = $new_ind["rate"];
  137. $new_genes[$i]["gene_code"] = $new_ind["gene_code"];
  138.  
  139. if($new_ind["rate"]>=$this->max_rate && !in_array($new_ind,$this->best) )
  140. {
  141. $this->max_rate = $new_ind["rate"];
  142. $this->best[] = $new_ind;
  143. usort($this->best,"cmp");
  144. }
  145.  
  146. echo $new_ind["word"] . " - " . $new_ind["rate"] ."<br>\n";
  147. }
  148. }
  149.  
  150.  
  151. array_unique($new_genes);
  152. usort($new_genes, "cmp");
  153. return $new_genes;
  154. }
  155.  
  156. private function cross($gene1,$gene2)
  157. {
  158. $new_gene = array();
  159. for($i=0;$i<$this->lenght;$i++)
  160. {
  161. $rand = rand(0,1);
  162. if($rand)
  163. {
  164. $new_gene[$i] = $gene1[$i];
  165. }
  166. else
  167. {
  168. $new_gene[$i] = $gene2[$i];
  169. }
  170. }
  171.  
  172. if($new_gene !== $gene1 && $new_gene !== $gene2)
  173. {
  174. echo "<span style='color:green'>cross successfull </span><br>";
  175. }
  176.  
  177. return $new_gene;
  178. }
  179.  
  180. public function execute()
  181. {
  182. //the first gene code
  183. $gene_code = $this->generate_gene_code();
  184. $first_population = $this->first_population($gene_code);
  185. $result = $this->evolution($first_population);
  186.  
  187. return $result;
  188. }
  189.  
  190. private function evolution($genes_data)
  191. {
  192. //return $genes_data;
  193. if($genes_data[0]["rate"]>=self::SUCCESS_RATE)
  194. {
  195. echo $genes_data[0]["word"]. " found after ". $this->population . " try";
  196. return $genes_data;
  197. }
  198. else
  199. {
  200. if(count($this->best)>self::SURVIVORS || $this->passed)
  201. {
  202. usort($this->best,"cmp");
  203. $this->best = $this->kill($this->best);
  204. $genes = $this->best;
  205. $this->passed = TRUE;
  206. }
  207. else
  208. {
  209. $genes = $genes_data;
  210. }
  211. return $this->evolution($this->populate($genes));
  212. }
  213. }
  214.  
  215. private function generate_gene_code()
  216. {
  217. $code = array();
  218. for($i=0;$i<$this->lenght;$i++)
  219. {
  220. $code[] = rand(0,strlen(self::LETTERS));
  221. }
  222. return $code;
  223. }
  224.  
  225. private function generate($gene_code,$mutation)
  226. {
  227. //generates new individuals according to genetic code
  228. if($mutation)
  229. {
  230. $gene_code = $this->mutate($gene_code);
  231. }
  232.  
  233. $new_word = "";
  234.  
  235. for($i=0;$i<$this->lenght;$i++)
  236. {
  237. $letter = substr(self::LETTERS,$gene_code[$i],1);
  238. $new_word .= $letter;
  239. }
  240.  
  241. $new_ind = array();
  242.  
  243. $new_ind["gene_code"] = $gene_code;
  244. $new_ind["word"] = $new_word;
  245. $new_ind["rate"] = $this->check_success($new_word);
  246.  
  247. return $new_ind;
  248. }
  249.  
  250. private function mutate($gene_code)
  251. {
  252. //mutate original data and returns it
  253. $mutate_letter_num = floor(self::MUTATION_RATE * $this->lenght / 100);
  254. $mutate_letters = array();
  255.  
  256. for($i=0;$i<$mutate_letter_num;$i++)
  257. {
  258. $which = rand(0,$this->lenght-1);
  259. $mutate_letters[] = $which;
  260. }
  261.  
  262. array_unique($mutate_letters);
  263.  
  264. foreach($mutate_letters as $letter_num)
  265. {
  266. $gene_code[$letter_num] = rand(0,strlen(self::LETTERS));
  267. }
  268. return $gene_code;
  269. }
  270. }

and here is the usage:

  1. ini_set("memory_limit","256M");
  2. function cmp($a, $b)
  3. {
  4. if ($a["rate"] == $b["rate"]) {
  5. return 0;
  6. }
  7. return ($a["rate"] > $b["rate"]) ? -1 : 1;
  8. }
  9.  
  10. include("gac.php");
  11.  
  12. $text = "hello world";
  13. $my_ga = new Gac($text);
  14.  
  15.  
  16. $first_gene_code = $my_ga->execute();