TSP Simulator - with GA
/**
* Copyright greentec ( http://wonderfl.net/user/greentec )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/msq8
*/
package {
import flash.display.Sprite;
import com.bit101.components.Label;
import com.bit101.components.NumericStepper;
import com.bit101.components.PushButton;
import flash.display.BitmapData;
import flash.display.Bitmap;
import flash.display.Sprite;
import flash.events.Event;
import com.bit101.charts.LineChart;
[SWF(width=465, height=465, backgroundColor=0x292929, frameRate=60)]
public class FlashTest extends Sprite {
public var tileNum_X:int = 50;
public var tileNum_Y:int = 50;
public var tile_width:int = 6;
public var tile_height:int = 6;
public var cityNum:int = 24;
public var cityArray:Array = [];
public var tileBitmapData:BitmapData;
public var tileBitmap:Bitmap;
public var gridSprite:Sprite;
public var cityBitmapData:BitmapData;
public var cityBitmap:Bitmap;
public var citySprite:Sprite;
public var routeSprite:Sprite;
public var titleLabel:Label;
public var populationLabel:Label;
public var populationNumericStepper:NumericStepper;
public var generationLabel:Label;
public var generationNo:int = 0;
public var endGeneration:int = 50000;
public var parentLabel:Label;
public var parentNumericStepper:NumericStepper;
public var mutationLabel:Label;
public var mutationNumericStepper:NumericStepper;
public var cityNumLabel:Label;
public var cityNumNumericStepper:NumericStepper;
public var fitnessLabel:Label;
public var bestFitness:int = 0;
public var prevBestFitness:int = 0;
public var fitnessLineChart:LineChart;
public var fitnessLineChartLabel:Label;
public var chartRefreshCycle:int = 50;
public var bestFitnessLineChart:LineChart;
public var bestFitnessLineChartLabel:Label;
public var bestData:Array = [];
public var multiFactor:int = 1000;
public var parentRate:Number = 0.4;
public var eliteRate:Number = 0.05;
public var mutationRate:Number = 0.05;
public var populationNum:int = 1000;
public var population:Vector.<Vector.<int>> = new Vector.<Vector.<int>>(populationNum);
public var populationScore:Vector.<int> = new Vector.<int>(populationNum);
public var selectionExpect:Vector.<int> = new Vector.<int>(populationNum * parentRate);
public var cityCheckSum:int = 0;
public var startButton:PushButton;
public var stopButton:PushButton;
public var resetButton:PushButton;
public function FlashTest() {
// write as3 code here..
stage.scaleMode = "noScale";
//Style.setStyle(Style.DARK);
cityArray = printRandomNumber(tileNum_X * tileNum_Y, cityNum);
tileBitmapData = new BitmapData(465, 465, true, 0x00ffffff);
//print Tile Grid
gridSprite = new Sprite();
gridSprite.graphics.lineStyle(1, 0xffffff, 1);
gridSprite.graphics.beginFill(0xc0c0c0, 1);
gridSprite.graphics.drawRect(0, 0, tileNum_X * tile_width, tileNum_Y * tile_height);
gridSprite.graphics.endFill();
for (var i:int = 0; i < tileNum_X; i += 1)
{
gridSprite.graphics.moveTo(i * tile_width, 0);
gridSprite.graphics.lineTo(i * tile_width, tileNum_Y * tile_height);
}
for (i = 0; i < tileNum_Y; i += 1)
{
gridSprite.graphics.moveTo(0, i * tile_height);
gridSprite.graphics.lineTo(tileNum_X * tile_width, i * tile_height);
}
tileBitmapData.draw(gridSprite);
tileBitmap = new Bitmap(tileBitmapData);
addChild(tileBitmap);
//draw City
cityBitmapData = new BitmapData(465, 465, true, 0x00ffffff);
citySprite = new Sprite();
citySprite.graphics.lineStyle(1, 0x9d9dff, 1);
citySprite.graphics.beginFill(0x0080ff);
for (i = 0; i < cityArray.length; i += 1)
{
var cityX:int = cityArray[i] % tileNum_X;
var cityY:int = cityArray[i] / tileNum_X;
citySprite.graphics.drawRect(cityX * tile_width, cityY * tile_height, tile_width, tile_height);
cityCheckSum += i;
}
//trace(cityCheckSum);
citySprite.graphics.endFill();
cityBitmapData.draw(citySprite);
cityBitmap = new Bitmap(cityBitmapData);
addChild(cityBitmap);
routeSprite = new Sprite();
addChild(routeSprite);
//draw UI
titleLabel = new Label(this, tile_width * tileNum_X + 10, 10, "TSP Simulator - with GA");
generationLabel = new Label(this, titleLabel.x, titleLabel.y + titleLabel.height, "Generation : " + String(generationNo) + " / " + String(endGeneration));
fitnessLabel = new Label(this, generationLabel.x, generationLabel.y + generationLabel.height, "Best Fit. : " + String(bestFitness));
populationLabel = new Label(this, fitnessLabel.x, fitnessLabel.y + fitnessLabel.height, "Population Num");
populationNumericStepper = new NumericStepper(this, 465 - 80, populationLabel.y, onChangeValue);
populationNumericStepper.width = 80;
populationNumericStepper.value = populationNum;
populationNumericStepper.step = 50;
populationNumericStepper.minimum = 50;
parentLabel = new Label(this, populationLabel.x, populationLabel.y + populationLabel.height, "Parent %");
parentNumericStepper = new NumericStepper(this, 465 -80, parentLabel.y, onChangeValue);
parentNumericStepper.width = 80;
parentNumericStepper.value = parentRate * 100;
parentNumericStepper.step = 5;
parentNumericStepper.minimum = 10;
mutationLabel = new Label(this, parentLabel.x, parentLabel.y + parentLabel.height, "Mutation %");
mutationNumericStepper = new NumericStepper(this, 465 - 80, mutationLabel.y, onChangeValue);
mutationNumericStepper.name = "mu";
mutationNumericStepper.width = 80;
mutationNumericStepper.value = mutationRate * 100;
mutationNumericStepper.step = 0.5;
mutationNumericStepper.minimum = 0;
cityNumLabel = new Label(this, mutationLabel.x, mutationLabel.y + mutationLabel.height, "City Num");
cityNumNumericStepper = new NumericStepper(this, 465 - 80, cityNumLabel.y, onChangeValue);
cityNumNumericStepper.width = 80;
cityNumNumericStepper.value = cityNum;
cityNumNumericStepper.minimum = 10;
startButton = new PushButton(this, cityNumLabel.x, cityNumLabel.y + cityNumLabel.height + 10, "Start", onStart);
stopButton = new PushButton(this, startButton.x, startButton.y + startButton.height, "Stop", onStop);
stopButton.enabled = false;
resetButton = new PushButton(this, stopButton.x, stopButton.y + stopButton.height, "Reset", onReset);
fitnessLineChart = new LineChart(this, 40, tile_height * tileNum_Y + 30, null);
fitnessLineChart.showGrid = true;
fitnessLineChart.showScaleLabels = true;
fitnessLineChart.lineColor = 0xff0080;
fitnessLineChart.width = 180;
fitnessLineChartLabel = new Label(this, 10, fitnessLineChart.y - 20, "All Population Fitness");
fitnessLineChartLabel.x = fitnessLineChart.x;
bestFitnessLineChart = new LineChart(this, fitnessLineChart.x + fitnessLineChart.width + 50 + 5, fitnessLineChart.y, null);
bestFitnessLineChart.showGrid = true;
bestFitnessLineChart.showScaleLabels = true;
bestFitnessLineChart.lineColor = 0x00ff00;
bestFitnessLineChart.width = 180;
bestFitnessLineChartLabel = new Label(this, 10, bestFitnessLineChart.y - 20, "Best Population Fitness");
bestFitnessLineChartLabel.x = bestFitnessLineChart.x;
initPopulation(populationNum);
drawBestRoute();
}
private function onChangeValue(e:Event):void
{
switch(e.target.name)
{
case "mu": //mutation
mutationRate = e.target.value / 100;
break;
}
}
private function onStart(e:Event):void
{
addEventListener(Event.ENTER_FRAME, onLoop);
e.target.enabled = false;
stopButton.enabled = true;
resetButton.enabled = false;
populationNumericStepper.enabled = false;
parentNumericStepper.enabled = false;
cityNumNumericStepper.enabled = false;
}
private function onStop(e:Event):void
{
removeEventListener(Event.ENTER_FRAME, onLoop);
e.target.enabled = false;
startButton.enabled = true;
resetButton.enabled = true;
populationNumericStepper.enabled = true;
parentNumericStepper.enabled = true;
cityNumNumericStepper.enabled = true;
}
private function onReset(e:Event):void
{
var i:int;
cityNum = cityNumNumericStepper.value;
cityArray = printRandomNumber(tileNum_X * tileNum_Y, cityNum);
//draw City
cityBitmapData.fillRect(cityBitmapData.rect, 0x00ffffff);
citySprite.graphics.clear();
citySprite.graphics.lineStyle(1, 0x9d9dff, 1);
citySprite.graphics.beginFill(0x0080ff);
cityCheckSum = 0;
for (i = 0; i < cityArray.length; i += 1)
{
var cityX:int = cityArray[i] % tileNum_X;
var cityY:int = cityArray[i] / tileNum_X;
citySprite.graphics.drawRect(cityX * tile_width, cityY * tile_height, tile_width, tile_height);
cityCheckSum += i;
}
citySprite.graphics.endFill();
cityBitmapData.draw(citySprite);
routeSprite.graphics.clear();
generationNo = 0;
populationNum = populationNumericStepper.value;
initPopulation(populationNum);
parentRate = parentNumericStepper.value / 100;
drawUI();
bestData = [];
}
private function onLoop(e:Event):void
{
var i:int;
var j:int;
var temp:int;
//select
sortDescending();
var selectionSum:int = 0;
selectionExpect = new Vector.<int>(populationNum * parentRate);
for (i = 0; i < populationNum * parentRate ; i += 1)
{
selectionExpect[i] = 1000000000000 / Math.pow(populationScore[i], 2);
selectionSum += selectionExpect[i];
//trace(selectionExpect[i]);
}
//crossover
for (i = populationNum * eliteRate; i < populationNum; i += 1) //i = pop * elite => elite preserve; not elite => new pop
{
var firstParent:int = Math.random() * selectionSum;
var secondParent:int = Math.random() * selectionSum;
for (j = 0; j < selectionExpect.length; j += 1)
{
if (firstParent < selectionExpect[j])
{
firstParent = j;
break;
}
firstParent -= selectionExpect[j];
}
for (j = 0; j < selectionExpect.length; j += 1)
{
if (secondParent < selectionExpect[j])
{
secondParent = j;
break;
}
secondParent -= selectionExpect[j];
}
if (firstParent == secondParent) //same parent - reSelect
{
i -= 1;
continue;
//trace("HI");
}
else //find crossover point
{
for (var k:int = 0; k < cityNum; k += 1)
{
population[i][k] = population[firstParent][k];
}
var crossOverPoint1:int = Math.random() * (cityNum - 1);
var crossOverPoint2:int = int( Math.random() * (cityNum - crossOverPoint1) ) + crossOverPoint1;
//trace(crossOverPoint1, crossOverPoint2);
for (k = crossOverPoint1; k < crossOverPoint2; k += 1)
{
if (population[i][k] != population[secondParent][k])
{
for (var l:int = 0; l < cityNum; l += 1)
{
if (population[i][l] == population[secondParent][k] && l != k)
{
temp = population[i][l];
population[i][l] = population[i][k];
population[i][k] = temp;
break;
}
}
}
else
{
population[i][k] = population[secondParent][k];
}
}
}
}
//mutate
for (i = populationNum * eliteRate; i < populationNum; i += 1) //not elite => mutation
{
for (j = 0; j < cityNum; j += 1)
{
if (Math.random() < mutationRate)
{
var second:int = Math.random() * cityNum;
while (second == j)
{
second = Math.random() * cityNum; //trace("HI" + j);
}
temp = population[i][j];
population[i][j] = population[i][second];
population[i][second] = temp;
}
}
}
//evaluate Score
prevBestFitness = bestFitness;
bestFitness = int.MAX_VALUE;
for (i = 0; i < populationNum; i += 1)
{
populationScore[i] = evalPopulation(population[i]); //trace(populationScore[i]);
bestFitness = Math.min(bestFitness, populationScore[i]);
}
generationNo += 1;
//draw UI
drawUI();
//draw Route & bestChart
bestData.push(bestFitness);
if(prevBestFitness != bestFitness)
{
drawBestRoute();
drawBestChart();
}
if (generationNo >= endGeneration)
{
removeEventListener(Event.ENTER_FRAME, onLoop);
}
}
private function sortDescending():void
{
var temp:Array = [];
var obj:Object;
for (var i:int = 0; i < population.length; i += 1)
{
obj = new Object();
obj.population = population[i];
obj.score = populationScore[i];
temp.push(obj);
}
temp.sortOn("score", Array.NUMERIC);
for (i = 0; i < population.length; i += 1)
{
population[i] = temp[i].population;
populationScore[i] = temp[i].score;
}
drawChart();
}
private function drawUI():void
{
generationLabel.text = "Generation : " + String(generationNo) + " / " + String(endGeneration);
fitnessLabel.text = "Best Fit. : " + String(bestFitness);
}
private function drawBestChart():void
{
bestFitnessLineChart.data = bestData;
bestFitnessLineChart.draw();
}
private function drawChart():void
{
if (generationNo % chartRefreshCycle == 2)
{
var dataArray:Array = [];
for (var i:int = 0; i < populationScore.length; i += 1)
{
dataArray.push(populationScore[i]);
}
fitnessLineChart.data = dataArray;
fitnessLineChart.minimum = 0;
fitnessLineChart.draw();
//trace(dataArray);
}
}
private function drawBestRoute():void
{
//var minimum:int = int.MAX_VALUE;
//var minimumPop:int = -1;
//
//for (var i:int = 0; i < populationScore.length; i += 1)
//{
//if (Math.min(populationScore[i], minimum) != minimum)
//{
//minimum = populationScore[i];
//minimumPop = i;
//}
//
//minimum = Math.min(populationScore[i], minimum);
//}
var minimumPop:int = 0;
var i:int;
routeSprite.graphics.clear();
routeSprite.graphics.lineStyle(2, 0x800040, 1);
var prevX:int;
var prevY:int;
var nextX:int;
var nextY:int;
//trace(population[minimumPop]);
for (i = 0; i < population[minimumPop].length - 1; i += 1)
{
//trace(population[minimumPop][i]);
prevX = cityArray[population[minimumPop][i]] % tileNum_X * tile_width + tile_width / 2;
prevY = int(cityArray[population[minimumPop][i]] / tileNum_X) * tile_height + tile_height / 2;
nextX = cityArray[population[minimumPop][i + 1]] % tileNum_X * tile_width + tile_width / 2;
nextY = int(cityArray[population[minimumPop][i + 1]] / tileNum_X) * tile_height + tile_height / 2;
routeSprite.graphics.moveTo(prevX, prevY);
routeSprite.graphics.lineTo(nextX, nextY);
//trace(prevX, prevY);
}
routeSprite.graphics.moveTo(nextX, nextY); //move to 0
routeSprite.graphics.lineTo(cityArray[population[minimumPop][0]] % tileNum_X * tile_width + tile_width / 2, int(cityArray[population[minimumPop][0]] / tileNum_X) * tile_height + tile_height / 2);
}
private function initPopulation(populationNum:int):void
{
for (var i:int = 0; i < populationNum; i += 1)
{
var onePopulation:Array = printRandomNumber(cityNum, cityNum);
population[i] = new Vector.<int>(cityNum);
for (var j:int = 0; j < cityNum; j += 1)
{
population[i][j] = onePopulation[j];
}
//init Score
populationScore[i] = evalPopulation(population[i]);
//trace(populationScore[i]);
}
generationNo += 1;
}
private function evalPopulation(pop:Vector.<int>):int
{
var score:int = 0;
var check:int = 0;
for (var i:int = 0; i < pop.length - 1; i += 1)
{
var prevX:int = cityArray[pop[i]] % tileNum_X;
var prevY:int = cityArray[pop[i]] / tileNum_X;
var nextX:int = cityArray[pop[i + 1]] % tileNum_X;
var nextY:int = cityArray[pop[i + 1]] / tileNum_X; //trace(cityArray[pop[i]]);
score += ( Math.pow(Math.abs(prevX - nextX), 2) + Math.pow(Math.abs(prevY - nextY), 2) ) * multiFactor;
}
score += ( Math.pow(Math.abs(nextX - (cityArray[pop[0]] % tileNum_X)), 2) + Math.pow(Math.abs(nextY - (cityArray[pop[0]] / tileNum_X)), 2) ) * multiFactor; //move to 0
//trace(score);
return Math.sqrt(score);
}
private function printRandomNumber(n:int, k:int) : Array
{
var original:Array=[];
var result:Array=[];
var i:int;
var randInt:int;
var temp:Object;
for(i=0;i<n;i+=1)
{
original.push(i);
}
for(i=0;i<k;i+=1)
{
randInt = Math.random()*(n-i) + i;
temp = original[i];
original[i] = original[randInt];
original[randInt] = temp;
result.push(original[i]);
}
return result;
}
}
}