/**
* Copyright tepe ( http://wonderfl.net/user/tepe )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/hmil
*/
package {
import flash.display.Sprite;
import flash.events.*;
public class FlashTest extends Sprite {
private var node:Node;
private var salesperson:Salesperson;
private var nodeNum:int = 20;
private var salespersonNum:int = 60;
private var startFlag:Boolean = false;
public function FlashTest() {
// write as3 code here..
// ノード作成
node = new Node(nodeNum);
addChild(node);
onStart();
}
/**
* 交叉を開始する
*
* @param event
*/
private function onStart(event:Event=null):void
{
if (!startFlag) {
salesperson.generation = 0;
salesperson.mutationProb = 0.7;
salesperson.mutationVolume = 0.2;
salesperson.aliveVolume = 0.2;
salesperson.nextGeneration(node);
node.dragFalse();
startFlag = true;
addEventListener(Event.ENTER_FRAME, nextGeneration);
}
}
/**
* 次の世代へ進める
*
* @param event
*/
private function nextGeneration(event:Event):void
{
node.drawRoute(salesperson);
salesperson.nextGeneration(node);
}
/**
* 交叉を停止する
*
* @param event
*/
private function onStop(event:Event):void
{
removeEventListener(Event.ENTER_FRAME, nextGeneration);
}
/**
* クリアする
*
* @param event
*/
private function onClear(event:Event):void
{
node.clearRoute(salesperson);
node.dragTrue();
startFlag = false;
salesperson.generation = 0;
}
/**
* nodeの位置をランダムにする
*
* @param event
*/
private function random(event:Event):void
{
if (!startFlag) {
node.randomize();
}
}
}
}
/**
* セールスマン(GAでコントロール)
* ...
* @author sabotenbrother
*/
class Salesperson {
private var _gene:Array = new Array(); // 遺伝子情報
private var _nodeNum:int;
private var _personNum:int;
private var _generation:int = 0; // 世代
private var _mutationProb:Number = 0.7; // 突然変異の確立
private var _mutationVolume:Number = 0.2; // 突然変異の量
private var _aliveVolume:Number = 0.2; // 生存率
private var mask:Array = new Array(); // 一様交叉用のマスクパターン
public function Salesperson(nodeNum:int =20, personNum:int = 60){
_nodeNum = nodeNum;
_personNum = personNum;
_gene = generateGene(nodeNum, personNum);
// マスクパターンの生成 000111000111...
for (var i:int = 0; i < _nodeNum; i++) {
mask.push(Math.floor((i / 3) % 2));
}
}
/**
* 遺伝子を作る
*
* @param nodeNum ノードの数だけ gene を持つ
* @param personNum セールスパーソンの数
* @return 遺伝子情報(route, score, rank)
*/
public function generateGene(nodeNum:int, personNum:int):Array {
var rtnArr:Array = new Array();
for (var i:int = 0; i < personNum; i++)
{
var arr:Array = new Array();
for (var j:int = 0; j < nodeNum; j++) arr[j] = j;
arr = shuffle(arr);
rtnArr[i] = {route: arr, score: 0, rank: 0};
}
return rtnArr;
}
/**
* 次の世代へ進める
*/
public function nextGeneration(node:Node):void {
_generation++;
var aliveNum:int = Math.floor(gene.length * _aliveVolume) + 2; // 親の遺伝子ふたつは必ず残す
crossbreed(node, aliveNum);
}
/**
* 遺伝子を一様交叉させる
* マスクパターンは000111000111000111...
*
* @param node ノード情報
* @param aliveNum 親以外に残す遺伝子の数
*/
private function crossbreed(node:Node, aliveNum:int):void {
// 遺伝子情報を一時的に保管するための配列を作成
var _geneTmp:Array = new Array();
_geneTmp = generateGene(_nodeNum, 1);
_geneTmp[0].route = new Array();
// 遺伝子情報に優越をつける
rankingSort(node);
var genePosArr:Array = new Array(); // 遺伝子の配列位置
// 父親の遺伝子を入力
for (var i:int = 0; i < _nodeNum; i++) {
if (mask[i] == 0) {
_geneTmp[0].route[i] = _gene[0].route[i];
}
}
// 母親の遺伝子を入力
for (var j:int = 0; j < _nodeNum; j++) {
if (mask[j] == 1) {
// 遺伝子情報を持っていない場合だけ入力(既に持っている遺伝子情報であれば入力しない)
if (_geneTmp[0].route.indexOf(_gene[1].route[j], 0) == -1) {
_geneTmp[0].route[j] = _gene[1].route[j];
} else {
genePosArr.push(j); // 埋められなかった場所を記憶する
}
}
}
var nothingGene:Array = new Array(); // 欠けている遺伝子情報を格納する配列
// 欠けている遺伝子情報を調べる(どの数字がないか調べる)
for (var k:int = 0; k < _nodeNum; k++) {
if (_geneTmp[0].route.indexOf(k, 0) == -1) nothingGene.push(k);
}
nothingGene = shuffle(nothingGene); // 位置をシャッフル
// 欠けている遺伝子を補う
for (var l:int = 0; l < genePosArr.length; l++) {
_geneTmp[0].route[genePosArr[l]] = nothingGene[l];
}
// 交叉させた遺伝子情報を子供たちに与える
for (var m:int = 2 + aliveNum; m < _gene.length; m++) {
_gene[m].route = _geneTmp[0].route.concat(); // 配列は参照渡しになるので deepcopy する
}
// mutationProb の確立で遺伝子に突然変異を起こす
if (Math.random() < _mutationProb) {
mutate(aliveNum);
//mutate(10);
}
/*
// デバッグ用に全遺伝子をトレース
for (var j:int = 0; j < _gene.length; j++) {
trace(j, _gene[j].route);
}
*/
}
/**
* 遺伝子に優越をつける
* 各ノード間の距離が短い順にソートする(距離が短い方が優秀)
*
* @param node ノード情報
*/
private function rankingSort(node:Node):void {
var totalLength:Number = 0;
for (var j:int = 0; j < _personNum; j++) {
for (var i:int = 0; i < _nodeNum - 1; i++) {
totalLength += node.getDistance(_gene[j].route[i], _gene[j].route[i + 1]);
}
totalLength += node.getDistance(_gene[j].route[i], _gene[j].route[0]);
_gene[j].score = totalLength;
totalLength = 0;
}
_gene.sortOn('score', Array.NUMERIC);//数値のソート
}
/**
* 突然変異させる
*
* @param aliveNum 突然変異させない遺伝子の数
*/
private function mutate(aliveNum:int):void {
var flipVolume:int = Math.round(_nodeNum * mutationVolume); // 何個の遺伝子を組み換えるか
for (var i:int = aliveNum; i < _gene.length; i++) {
for (var j:int = 0; j < flipVolume; j++) {
var firstPos:int = Math.round(Math.random() * (_nodeNum - 1));
var secondPos:int = Math.round(Math.random() * (_nodeNum - 1));
var tmp:int;
tmp = _gene[i].route[firstPos];
_gene[i].route[firstPos] = _gene[i].route[secondPos];
_gene[i].route[secondPos] = tmp;
}
}
}
/**
* 遺伝子情報をシャッフルする
*
* @param arr 遺伝子情報を持った配列
* @return シャッフルした配列
*/
private function shuffle(arr:Array):Array {
var num:int = arr.length; // 配列の数
for (var i:int = 0; i < num; i++) {
var rundomNum:int = Math.floor(Math.random() * num);
var temp:int = arr[rundomNum];
arr[rundomNum] = arr[i];
arr[i] = temp;
}
return arr;
}
/**
*
* setter / getter
*
*/
public function get gene():Array {
return _gene;
}
public function get mutationProb():Number {
return _mutationProb;
}
public function set mutationProb(value:Number):void {
_mutationProb = value;
}
public function get mutationVolume():Number {
return _mutationVolume;
}
public function set mutationVolume(value:Number):void {
_mutationVolume = value;
}
public function get aliveVolume():Number {
return _aliveVolume;
}
public function set aliveVolume(value:Number):void {
_aliveVolume = value;
}
public function get generation():int {
return _generation;
}
public function set generation(value:int):void {
_generation = value;
}
}
import flash.display.Sprite;
import flash.events.MouseEvent;
import flash.geom.Rectangle;
/**
* ノード = 各都市
* ...
* @author sabotenbrother
*/
class Node extends Sprite
{
private var nodeArr:Array = new Array();
private var blocker:Sprite = new Sprite();
private var line:Sprite = new Sprite();
private var boundary:Sprite = new Sprite();
private const radius:int = 6;
public function Node(nodeNum:int)
{
initNode(nodeNum);
}
/**
* nodeを引数の数だけ初期化
*
* @param nodeNum ノードの数
*/
public function initNode(nodeNum:int):void
{
for (var i:int = 0; i < nodeNum; i++) {
var sp:Sprite = new Sprite();
nodeArr.push(sp);
nodeArr[i].graphics.beginFill(0x000000);
nodeArr[i].graphics.drawCircle(0, 0, radius);
nodeArr[i].graphics.endFill();
nodeArr[i].buttonMode = true;
nodeArr[i].x = radius + Math.floor(Math.random() * (465 - radius * 2));
nodeArr[i].y = 110 + radius + Math.floor(Math.random() * (300 - radius * 2));
nodeArr[i].addEventListener(MouseEvent.MOUSE_DOWN, startDragging);
addChild(nodeArr[i]);
}
// ノード表示区域境界線用のスプライト
boundary.graphics.lineStyle(1, 0x0);
boundary.graphics.drawRect(0, 110, 464, 300);
boundary.graphics.endFill();
addChild(boundary);
// ルート表示用のスプライト
addChild(line);
// 非選択用のレクタングル
blocker.graphics.beginFill(0x000000);
blocker.graphics.drawRect(0, 110, 465, 300);
blocker.graphics.endFill();
blocker.alpha = 0.1;
blocker.visible = false;
addChild(blocker);
}
/**
* nodeを再設定
*
* @param nodeNum
*/
public function setNode(nodeNum:int):void
{
var length:int = nodeArr.length;
for (var i:int = 0; i < length; i++) {
removeChild(nodeArr[0]);
nodeArr.shift();
}
for (var j:int = 0; j < nodeNum; j++) {
var sp:Sprite = new Sprite();
nodeArr.push(sp);
nodeArr[j].graphics.beginFill(0x000000);
nodeArr[j].graphics.drawCircle(0, 0, radius);
nodeArr[j].graphics.endFill();
nodeArr[j].buttonMode = true;
nodeArr[j].x = radius + Math.floor(Math.random() * (465 - radius * 2));
nodeArr[j].y = 110 + radius + Math.floor(Math.random() * (300 - radius * 2));
nodeArr[j].addEventListener(MouseEvent.MOUSE_DOWN, startDragging);
addChild(nodeArr[j]);
}
}
/**
* 一番優秀なセールスパーソンのルートを描画
*
* @param salesperson セールスパーソン
*/
public function drawRoute(salesperson:Salesperson):void
{
line.graphics.clear();
line.graphics.lineStyle(1, 0x0);
for (var i:int = 0; i < nodeArr.length - 1; i++) {
line.graphics.moveTo(nodeArr[salesperson.gene[0].route[i]].x, nodeArr[salesperson.gene[0].route[i]].y);
line.graphics.lineTo(nodeArr[salesperson.gene[0].route[i + 1]].x, nodeArr[salesperson.gene[0].route[i + 1]].y);
}
line.graphics.moveTo(nodeArr[salesperson.gene[0].route[nodeArr.length - 1]].x, nodeArr[salesperson.gene[0].route[nodeArr.length - 1]].y);
line.graphics.lineTo(nodeArr[salesperson.gene[0].route[0]].x, nodeArr[salesperson.gene[0].route[0]].y);
}
public function clearRoute(saleperson:Salesperson):void
{
line.graphics.clear();
}
/**
* node間の距離を測る
*
* @param pt1 ひとつめのノード配列番号
* @param pt2 ふたつめのノード配列番号
* @return node間の距離をピクセルで返す
*/
public function getDistance(pt1:int, pt2:int):Number
{
var distance:Number = Math.sqrt(Math.pow(nodeArr[pt1].x - nodeArr[pt2].x, 2) + Math.pow(nodeArr[pt1].y - nodeArr[pt2].y, 2));
return Math.round(distance);
}
/**
* nodeの位置をランダムにする
*/
public function randomize():void
{
for (var i:int = 0; i < nodeArr.length; i++) {
nodeArr[i].x = 6 + Math.floor(Math.random() * (465 - 12));
nodeArr[i].y = 110 + 6 + Math.floor(Math.random() * (300 - 12));
}
}
/**
* nodeを円状に配置
*/
public function circlePattern():void
{
var angle:Number = 0.02;
var radius:int = 130;
for (var i:int = 0; i < nodeArr.length; i++) {
nodeArr[i].x = (stage.stageWidth / 2) + radius * Math.cos(angle + i / nodeArr.length * Math.PI * 2);
nodeArr[i].y = 260 + radius * Math.sin(angle + i / nodeArr.length * Math.PI * 2);
}
}
/**
* 全nodeを移動できるようにする
*/
public function dragTrue():void
{
blocker.visible = false;
}
/**
* 全nodeを移動できないようにする
*/
public function dragFalse():void
{
blocker.visible = true;
}
private function startDragging(event:MouseEvent):void
{
event.target.startDrag(false, new Rectangle(0 + radius, 110 + radius, 465 - radius * 2, 300 - radius * 2));
this.addEventListener(MouseEvent.MOUSE_UP, stopDragging);
}
private function stopDragging(event:MouseEvent):void
{
event.target.stopDrag();
this.removeEventListener(MouseEvent.MOUSE_UP, stopDragging);
}
}
