人工知能（遺伝的アルゴリズム GA）で巡回セールスマン問題を解く
初めて遺伝的アルゴリズムを実装してみました。
OOPもままならぬ冗長で拙く長いコードですし、あってるかどうか不安ですが…。
■操作説明
start 開始
stop 停止
clear クリア
random node（都市）の位置をランダムにします
circle node(都市)を円状に配置
setValue パラメータを設定
STOP→CLEARでクリア。
各nodeは移動（ドラッグ&ドロップ）可能です。
■パラメータ説明
node 都市の数
salesperson セールスマンの数(nodeの数だけ遺伝子を所有)
mutationProb 突然変異の確立
mutationVolume 突然変異の量
aliveVolume 生存率（次の世代で淘汰されない量）
...
@author sabotenbrother
巡回セールスマン問題とは…
12都市を回るセールスマンがいたとすると12 * 11 * 10 * 9 … ≒ 約4億8千万通りのルートがあってそれを最短で求めるには？さらに一都市増えたら？
/**
* Copyright postnum ( http://wonderfl.net/user/postnum )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/sNOO
*/
package
{
import flash.display.Sprite;
import flash.events.Event;
import com.bit101.components.PushButton;
import com.bit101.components.HUISlider;
import com.bit101.components.VUISlider;
import com.bit101.components.Label;
import com.bit101.components.Text;
[SWF(width = '465', height = '465', backgroundColor = '#FFFFFF', frameRate = '120')]
/**
* 人工知能（遺伝的アルゴリズム GA）で巡回セールスマン問題を解く
* ...
* @author sabotenbrother
*/
public class World 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;
// GUIパーツ
private var startButton:PushButton;
private var stopButton:PushButton;
private var clearButton:PushButton;
private var randomButton:PushButton;
private var circleButton:PushButton;
private var setValueButton:PushButton;
private var nodeLabel:Label;
private var salespersonLabel:Label;
private var nodeHUISlider:HUISlider;
private var salespersonHUISlider:HUISlider;
private var mutationProbHUISlider:HUISlider;
private var mutationVolumeHUISlider:HUISlider;
private var aliveVolumeHUISlider:HUISlider;
private var totalLengthText:Text;
private var generationLengthText:Text;
public function World():void
{
if (stage) init();
else addEventListener(Event.ADDED_TO_STAGE, init);
}
private function init(event:Event = null):void
{
createWorld();
}
/**
* 世界を創造する
*/
public function createWorld():void
{
// 巡回セールスマン（遺伝子作成）
salesperson = new Salesperson(nodeNum, salespersonNum);
// GUI作成
startButton = new PushButton(this, 0, 0, "start", onStart);
startButton.width = 60;
stopButton = new PushButton(this, 60, 0, "stop", onStop);
stopButton.width = 60;
clearButton = new PushButton(this, 120, 0, "clear", onClear);
clearButton.width = 60;
randomButton = new PushButton(this, 190, 0, "random", random);
randomButton.width = 60;
circleButton = new PushButton(this, 250, 0, "circle", circlePattern);
circleButton.width = 60;
setValueButton = new PushButton(this, 320, 0, "setValue", setValue);
setValueButton.width = 60;
nodeLabel = new Label(this, 10, 40, "node");
salespersonLabel = new Label(this, 10, 60, "saleperson");
nodeHUISlider = new HUISlider(this, 60, 40, "");
nodeHUISlider.width = 150;
nodeHUISlider.value = nodeNum;
nodeHUISlider.minimum = 10;
nodeHUISlider.maximum = 30;
nodeHUISlider.tick = 1;
salespersonHUISlider = new HUISlider(this, 60, 60, "");
salespersonHUISlider.width = 150;
salespersonHUISlider.value = salespersonNum;
salespersonHUISlider.minimum = 10;
salespersonHUISlider.maximum = 180;
salespersonHUISlider.tick = 1;
mutationProbHUISlider = new HUISlider(this, 290, 40, "");
mutationProbHUISlider.width = 150;
mutationProbHUISlider.value = salesperson.mutationProb;
mutationProbHUISlider.minimum = 0;
mutationProbHUISlider.maximum = 1.00;
mutationProbHUISlider.tick = 0.1;
mutationVolumeHUISlider = new HUISlider(this, 290, 60, "");
mutationVolumeHUISlider.width = 150;
mutationVolumeHUISlider.value = salesperson.mutationVolume;
mutationVolumeHUISlider.minimum = 0;
mutationVolumeHUISlider.maximum = 1.00;
mutationVolumeHUISlider.tick = 0.1;
aliveVolumeHUISlider = new HUISlider(this, 290, 80, "");
aliveVolumeHUISlider.width = 150;
aliveVolumeHUISlider.value = salesperson.aliveVolume;
aliveVolumeHUISlider.minimum = 0;
aliveVolumeHUISlider.maximum = 1.00;
aliveVolumeHUISlider.tick = 0.1;
var muttionProbLabel:Label = new Label(this, 210, 40, "mutationProb");
var mutationVolumeLabel:Label = new Label(this, 210, 60, "mutationVolume");
var aliveVolumeLabel:Label = new Label(this, 210, 80, "aliveVolume");
var generationLabel:Label = new Label(this, 10, 420, "Generation");
var totalLengthLabel:Label = new Label(this, 10, 440, "TotalLength");
generationLengthText = new Text(this, 80, 420, "");
generationLengthText.width = 200;
generationLengthText.height = 20;
totalLengthText = new Text(this, 80, 440, "");
totalLengthText.width = 200;
totalLengthText.height = 20;
// ノード作成
node = new Node(nodeNum);
addChild(node);
}
/**
* 交叉を開始する
*
* @param event
*/
private function onStart(event:Event):void
{
if (!startFlag) {
salesperson.generation = 0;
salesperson.mutationProb = mutationProbHUISlider.value;
salesperson.mutationVolume = mutationVolumeHUISlider.value;
salesperson.aliveVolume = aliveVolumeHUISlider.value;
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);
generationLengthText.text = String(salesperson.generation);
totalLengthText.text = String(salesperson.gene[0].score);
}
/**
* 交叉を停止する
*
* @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;
generationLengthText.text = String('');
totalLengthText.text = String('');
}
/**
* nodeの位置をランダムにする
*
* @param event
*/
private function random(event:Event):void
{
if (!startFlag) {
node.randomize();
}
}
/**
* nodeをサークル上に配置する
*
* @param event
*/
private function circlePattern(event:Event):void
{
if (!startFlag) {
node.circlePattern();
}
}
/**
* パラメータを再設定する
*
* @param event
*/
private function setValue(event:Event):void
{
if (!startFlag) {
salesperson.mutationProb = mutationProbHUISlider.value; // 突然変異の確立
salesperson.mutationVolume = mutationVolumeHUISlider.value; // 突然変異の量
salesperson.aliveVolume = aliveVolumeHUISlider.value; // 生存率
salesperson = new Salesperson(nodeHUISlider.value, salespersonHUISlider.value); // 巡回セールスマン（遺伝子作成）
node.setNode(nodeHUISlider.value);
}
}
}
}
/**
* セールスマン(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, personNum:int)
{
_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);
}
}