Created
September 18, 2012 01:11
-
-
Save tlhunter/3740694 to your computer and use it in GitHub Desktop.
PHP Traveling Salesman Genetic Algorithm
This file contains 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 | |
| ini_set("error_reporting", E_ALL & ~E_NOTICE); | |
| ?> | |
| <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> | |
| <html xmlns="http://www.w3.org/1999/xhtml"> | |
| <head> | |
| <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> | |
| <title>Genetic Algorithm : TSP : PHP Implementation by Thomas Hunter</title> | |
| <style> | |
| body { | |
| text-align: center; | |
| margin: 0px; padding: 0px; | |
| } | |
| body, td, th, input { | |
| font-family: Verdana, Arial, Helvetica, sans-serif; | |
| font-size: 11px; | |
| } | |
| h1 { | |
| font-family: Arial, Helvetica, sans-serif; | |
| font-size: 15px; | |
| text-align: center; | |
| } | |
| .cityCell { | |
| width: 60px; | |
| } | |
| .input { | |
| background-color: #CCFFFF; | |
| border: 1px solid #ccc; | |
| padding: 1px; | |
| margin: 1px; | |
| } | |
| #container { | |
| margin: 0 auto 0 auto; padding: 10px; | |
| width: 520px; | |
| text-align: left; | |
| border-left: 2px solid #333; | |
| border-right: 2px solid #333; | |
| border-bottom: 2px solid #333; | |
| } | |
| form { | |
| margin: 0px; padding: 0px; | |
| } | |
| .debug td { | |
| padding: 0 2px 0 2px; | |
| } | |
| </style> | |
| </head> | |
| <body> | |
| <div id="container"> | |
| <h1>Genetic Algorithm : TSP : PHP Implementation by Thomas Hunter</h1> | |
| <form method="post"> | |
| <table width="500" border="0" cellspacing="2" cellpadding="0" style='border: 1px solid #999;' align="center"> | |
| <tr> | |
| <td><strong>Cities</strong></td> | |
| <td align="center" class='cityCell'>City A</td> | |
| <td align="center" class='cityCell'>City B</td> | |
| <td align="center" class='cityCell'>City C</td> | |
| <td align="center" class='cityCell'>City D</td> | |
| <td align="center" class='cityCell'>City E</td> | |
| <td align="center" class='cityCell'>City F</td> | |
| <td align="center" class='cityCell'>City G</td> | |
| </tr> | |
| <tr> | |
| <td>City A</td> | |
| <td bgcolor="#CC3333"><div align="center">0</div></td> | |
| <td><div align="center"> | |
| <input name="1_2" type="text" class="input" id="textfield" size="4" maxlength="4" value="<?=$_POST['1_2']?>" /> | |
| </div></td> | |
| <td><div align="center"> | |
| <input name="1_3" type="text" class="input" id="textfield2" size="4" maxlength="4" value="<?=$_POST['1_3']?>" /> | |
| </div></td> | |
| <td><div align="center"> | |
| <input name="1_4" type="text" class="input" id="textfield3" size="4" maxlength="4" value="<?=$_POST['1_4']?>" /> | |
| </div></td> | |
| <td><div align="center"> | |
| <input name="1_5" type="text" class="input" id="textfield4" size="4" maxlength="4" value="<?=$_POST['1_5']?>" /> | |
| </div></td> | |
| <td><div align="center"> | |
| <input name="1_6" type="text" class="input" id="textfield5" size="4" maxlength="4" value="<?=$_POST['1_6']?>" /> | |
| </div></td> | |
| <td><div align="center"> | |
| <input name="1_7" type="text" class="input" id="textfield6" size="4" maxlength="4" value="<?=$_POST['1_7']?>" /> | |
| </div></td> | |
| </tr> | |
| <tr> | |
| <td>City B</td> | |
| <td><div align="center"></div></td> | |
| <td bgcolor="#CC3333"><div align="center">0</div></td> | |
| <td><div align="center"> | |
| <input name="2_3" type="text" class="input" id="textfield7" size="4" maxlength="4" value="<?=$_POST['2_3']?>" /> | |
| </div></td> | |
| <td><div align="center"> | |
| <input name="2_4" type="text" class="input" id="textfield8" size="4" maxlength="4" value="<?=$_POST['2_4']?>" /> | |
| </div></td> | |
| <td><div align="center"> | |
| <input name="2_5" type="text" class="input" id="textfield9" size="4" maxlength="4" value="<?=$_POST['2_5']?>" /> | |
| </div></td> | |
| <td><div align="center"> | |
| <input name="2_6" type="text" class="input" id="textfield10" size="4" maxlength="4" value="<?=$_POST['2_6']?>" /> | |
| </div></td> | |
| <td><div align="center"> | |
| <input name="2_7" type="text" class="input" id="textfield11" size="4" maxlength="4" value="<?=$_POST['2_7']?>" /> | |
| </div></td> | |
| </tr> | |
| <tr> | |
| <td>City C</td> | |
| <td><div align="center"></div></td> | |
| <td><div align="center"></div></td> | |
| <td bgcolor="#CC3333"><div align="center">0</div></td> | |
| <td><div align="center"> | |
| <input name="3_4" type="text" class="input" id="textfield12" size="4" maxlength="4" value="<?=$_POST['3_4']?>" /> | |
| </div></td> | |
| <td><div align="center"> | |
| <input name="3_5" type="text" class="input" id="textfield13" size="4" maxlength="4" value="<?=$_POST['3_5']?>" /> | |
| </div></td> | |
| <td><div align="center"> | |
| <input name="3_6" type="text" class="input" id="textfield14" size="4" maxlength="4" value="<?=$_POST['3_6']?>" /> | |
| </div></td> | |
| <td><div align="center"> | |
| <input name="3_7" type="text" class="input" id="textfield15" size="4" maxlength="4" value="<?=$_POST['3_7']?>" /> | |
| </div></td> | |
| </tr> | |
| <tr> | |
| <td>City D</td> | |
| <td><div align="center"></div></td> | |
| <td><div align="center"></div></td> | |
| <td><div align="center"></div></td> | |
| <td bgcolor="#CC3333"><div align="center">0</div></td> | |
| <td><div align="center"> | |
| <input name="4_5" type="text" class="input" id="textfield16" size="4" maxlength="4" value="<?=$_POST['4_5']?>" /> | |
| </div></td> | |
| <td><div align="center"> | |
| <input name="4_6" type="text" class="input" id="textfield17" size="4" maxlength="4" value="<?=$_POST['4_6']?>" /> | |
| </div></td> | |
| <td><div align="center"> | |
| <input name="4_7" type="text" class="input" id="textfield18" size="4" maxlength="4" value="<?=$_POST['4_7']?>" /> | |
| </div></td> | |
| </tr> | |
| <tr> | |
| <td>City E</td> | |
| <td><div align="center"></div></td> | |
| <td><div align="center"></div></td> | |
| <td><div align="center"></div></td> | |
| <td><div align="center"></div></td> | |
| <td bgcolor="#CC3333"><div align="center">0</div></td> | |
| <td><div align="center"> | |
| <input name="5_6" type="text" class="input" id="textfield19" size="4" maxlength="4" value="<?=$_POST['5_6']?>" /> | |
| </div></td> | |
| <td><div align="center"> | |
| <input name="5_7" type="text" class="input" id="textfield20" size="4" maxlength="4" value="<?=$_POST['5_7']?>" /> | |
| </div></td> | |
| </tr> | |
| <tr> | |
| <td>City F</td> | |
| <td><div align="center"></div></td> | |
| <td><div align="center"></div></td> | |
| <td><div align="center"></div></td> | |
| <td><div align="center"></div></td> | |
| <td><div align="center"></div></td> | |
| <td bgcolor="#CC3333"><div align="center">0</div></td> | |
| <td><div align="center"> | |
| <input name="6_7" type="text" class="input" id="textfield21" size="4" maxlength="4" value="<?=$_POST['6_7']?>" /> | |
| </div></td> | |
| </tr> | |
| <tr> | |
| <td>City G</td> | |
| <td><div align="center"></div></td> | |
| <td><div align="center"></div></td> | |
| <td><div align="center"></div></td> | |
| <td><div align="center"></div></td> | |
| <td><div align="center"></div></td> | |
| <td><div align="center"></div></td> | |
| <td bgcolor="#CC3333"><div align="center">0</div></td> | |
| </tr> | |
| </table> | |
| <br /> | |
| <br /> | |
| <table border="0" cellspacing="2" cellpadding="0" style='border: 1px solid #999;' align="center"> | |
| <tr> | |
| <td>Population</td> | |
| <td align="right"><input name="population" type="text" class="input" id="population" value="<?=$_POST['population']?>" size="5" maxlength="5" /></td> | |
| </tr> | |
| <tr> | |
| <td>Generations</td> | |
| <td align="right"><input name="generations" type="text" class="input" id="textfield24" value="<?=$_POST['generations']?>" size="5" maxlength="5" /></td> | |
| </tr> | |
| <tr> | |
| <td>Elitism</td> | |
| <td align="right"><input name="elitism" type="text" class="input" id="textfield25" value="<?=$_POST['elitism']?>" size="5" maxlength="2" /></td> | |
| </tr> | |
| <tr> | |
| <td colspan="2" align="center"><input type="submit" name="button" id="button" value="Calculate Shortest Route" /></td> | |
| </tr> | |
| </table> | |
| </form> | |
| <?php | |
| if (!empty($_POST)) { | |
| define('CITY_COUNT', 7); | |
| $population = $_POST['population'] + 0; | |
| if ($population > 999) # Gotta protect my CPU... | |
| $population = 999; | |
| $generations = $_POST['generations'] + 0; | |
| $elitism = $_POST['elitism'] + 0; | |
| $names = array(); | |
| $distances = array(); | |
| $initialPopulation = array(); | |
| $currentPopulation = array(); | |
| # Take user city names and put it into an array | |
| for ($i = 1; $i <= CITY_COUNT; $i++) { | |
| $names[$i] = $_POST['name'.$i]; | |
| } | |
| # Take user distance data and put it into a multidimensional array | |
| for ($i = 1; $i <= CITY_COUNT; $i++) { | |
| for ($j = 1; $j <= CITY_COUNT; $j++) { | |
| if (isset($_POST[$i . '_' . $j])) | |
| $distances[$i][$j] = $_POST[$i . '_' . $j]; | |
| else if (isset($_POST[$j . '_' . $i])) | |
| $distances[$i][$j] = $_POST[$j . '_' . $i]; | |
| else | |
| $distances[$i][$j] = 32767; | |
| } | |
| } | |
| # Building our initial population | |
| for($i = 0; $i < $population; $i++) { | |
| $initialPopulation[$i] = pickRandom(); | |
| } | |
| for ($k = 1; $k <= $generations; $k++) { | |
| echo "<div><strong>Generation $k</strong></div>\n"; | |
| # Rating population (I do some weird math to figure out their goodness level, not sure if it is good). | |
| echo "<pre>"; | |
| $i = 0; | |
| $distanceSum = 0; | |
| $biggest = 0; | |
| foreach ($initialPopulation AS $entity) { | |
| $currentPopulation[$i]['dna'] = $entity; | |
| $currentPopulation[$i]['rate'] = rate($entity, $distances); | |
| $distanceSum += $currentPopulation[$i]['rate']; | |
| if ($currentPopulation[$i]['rate'] > $biggest) | |
| $biggest = $currentPopulation[$i]['rate']; | |
| $i++; | |
| } | |
| $biggest += 1; | |
| $chancesSum = 0; | |
| for ($i = 0; $i < $population; $i++ ) { | |
| $currentPopulation[$i]['metric'] = $biggest - $currentPopulation[$i]['rate']; | |
| $chancesSum += $currentPopulation[$i]['metric']; | |
| } | |
| for ($i = 0; $i < $population; $i++ ) { | |
| $currentPopulation[$i]['chances'] = $currentPopulation[$i]['metric'] / $chancesSum; | |
| } | |
| util::sort($currentPopulation, 'rate'); | |
| $ceilSum = 0; | |
| for ($i = 0; $i < $population; $i++ ) { | |
| $currentPopulation[$i]['floor'] = $ceilSum; | |
| $ceilSum += $currentPopulation[$i]['chances']; | |
| } | |
| debug($currentPopulation); | |
| echo "</pre>\n"; | |
| if (converging($initialPopulation)) | |
| break; | |
| #Breeding time | |
| $initialPopulation = array(); | |
| for ($j = 0; $j < $elitism; $j++) { | |
| $initialPopulation[] = $currentPopulation[$j]['dna']; | |
| } | |
| for ($j = 0; $j < $population - $elitism; $j++) { | |
| $rouletteMale = rand(0, 100) / 100; | |
| for ($i = $population - 1; $i >= 0; $i--) { | |
| if ($currentPopulation[$i]['floor'] < $rouletteMale) { | |
| $dad = $currentPopulation[$i]['dna']; | |
| break; | |
| } | |
| } | |
| $rouletteFemale = rand(0, 100) / 100; | |
| for ($i = $population - 1; $i >= 0; $i--) { | |
| if ($currentPopulation[$i]['floor'] < $rouletteFemale) { | |
| $mom = $currentPopulation[$i]['dna']; | |
| break; | |
| } | |
| } | |
| $child = mate($mom, $dad); | |
| $initialPopulation[] = $child; | |
| } | |
| } | |
| echo "<div>The best solution I found is <strong>{$currentPopulation[0]['dna']}</strong> with a mileage of <strong>".rate($currentPopulation[0]['dna'], $distances)."</strong> which took <strong>$k</strong> generations.</div>\n"; | |
| } | |
| ?> | |
| </div> | |
| </body> | |
| </html> | |
| <?php | |
| function converging($pop) { | |
| $items = count(array_unique($pop)); | |
| if ($items == 1) | |
| return true; | |
| else | |
| return false; | |
| } | |
| function pickRandom() { | |
| $choices = array('A', 'B', 'C', 'D', 'E', 'F', 'G'); | |
| shuffle($choices); | |
| return implode('',$choices); | |
| } | |
| function rate($dna, $distances) { | |
| $mileage = 0; | |
| $letters = str_split($dna); | |
| for ($i = 0; $i < CITY_COUNT - 1; $i++) { | |
| $mileage += $distances[let2num($letters[$i])][let2num($letters[$i+1])]; | |
| } | |
| return $mileage; | |
| } | |
| function debug($ar) { | |
| echo "<table class='debug'>"; | |
| echo "<tr><th> </th><th>DNA</th><th>Fit</th><th>Roulette</th></tr>\n"; | |
| foreach($ar as $element => $value) { | |
| echo "<tr><td>" . leadingZero($element) . "</td><td>" . $value['dna'] . "</td><td>" . $value['rate'] . "</td><td>" . sprintf("%01.2f", $value['chances'] * 100) . "%</td></tr>\n"; | |
| } | |
| echo "</table>\n"; | |
| } | |
| function leadingZero($value) { | |
| if ($value < 10) | |
| $value = '00' . $value; | |
| else if ($value < 100) | |
| $value = '0' . $value; | |
| return $value; | |
| } | |
| function mate($mommy, $daddy) { # VERY INEFFICIENT! Combines genes randomly from both parents and if genes are repeated we do it again. | |
| $baby = "AAAAAA"; | |
| while (substr_count($baby, 'A') != 1 || substr_count($baby, 'B') != 1 || substr_count($baby, 'C') != 1 || substr_count($baby, 'D') != 1 || substr_count($baby, 'E') != 1 || substr_count($baby, 'F') != 1 || substr_count($baby, 'G') != 1) { | |
| $baby = ""; | |
| for($i = 0; $i < CITY_COUNT; $i++) { | |
| $chosen = mt_rand(0,1); | |
| if ($chosen) | |
| $baby .= substr($mommy, $i, 1); | |
| else | |
| $baby .= substr($daddy, $i, 1); | |
| } | |
| } | |
| return $baby; | |
| } | |
| function let2num($char) { | |
| if ($char == 'A') | |
| return 1; | |
| else if ($char == 'B') | |
| return 2; | |
| else if ($char == 'C') | |
| return 3; | |
| else if ($char == 'D') | |
| return 4; | |
| else if ($char == 'E') | |
| return 5; | |
| else if ($char == 'F') | |
| return 6; | |
| else if ($char == 'G') | |
| return 7; | |
| else | |
| die("WHOOPS"); | |
| } | |
| class util { | |
| static private $sortfield = null; | |
| static private $sortorder = 1; | |
| static private function sort_callback(&$a, &$b) { | |
| if($a[self::$sortfield] == $b[self::$sortfield]) return 0; | |
| return ($a[self::$sortfield] < $b[self::$sortfield])? -self::$sortorder : self::$sortorder; | |
| } | |
| static function sort(&$v, $field, $asc=true) { | |
| self::$sortfield = $field; | |
| self::$sortorder = $asc? 1 : -1; | |
| usort($v, array('util', 'sort_callback')); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment