巡回セールスマン問題
/**
* Copyright kuma360 ( http://wonderfl.net/user/kuma360 )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/dEED
*/
//最短経路を探す。
//
//参考
//
//巡回セールスマン問題
//http://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E%E3%82%BB%E3%83%BC%E3%83%AB%E3%82%B9%E3%83%9E%E3%83%B3%E5%95%8F%E9%A1%8C
//
//遺伝的アルゴリズム
//http://ja.wikipedia.org/wiki/%E9%81%BA%E4%BC%9D%E7%9A%84%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
package
{
import flash.display.Bitmap;
import flash.display.Sprite;
import flash.events.Event;
import flash.display.BitmapData ;
import flash.events.MouseEvent;
public class Main extends Sprite
{
public function Main():void
{
_canvas = new BitmapData ( 465 , 465 , false , 0 ) ;
addChild ( new Bitmap ( _canvas ) ) ;
var C:City = new City ;
var P:Population = new Population ;
addEventListener (
Event.ENTER_FRAME ,
function ():void {
_canvas.fillRect ( _canvas.rect , 0 ) ;
C.render () ;
P.run ( C ) ;
P.render ( C ) ;
}
);
stage.addEventListener (
MouseEvent.CLICK ,
function ():void {
C = new City ;
P = new Population ;
_WORTH = -99999 ;
_INDEX = null ;
}
) ;
}
}
}
import flash.display.BitmapData;
import flash.events.AsyncErrorEvent;
import flash.geom.Point;
import flash.geom.Rectangle;
var _canvas:BitmapData;
const City_NUM:int = 12;
const Population_NUM:int = 50 ;
var _WORTH:int = -99999 ;
var _INDEX:Chromosome = null ;
class City {
public var _v:Vector.<Point> ;
public function City() {
_v = new Vector.<Point> ;
var I:int ;
for ( I = 0 ; I < City_NUM ; ++ I ) {
_v.push ( new Point ( Math.random() * 465 , Math.random() * 465 ) ) ;
}
}
public function render():void {
var I:int ;
for ( I = 0 ; I < City_NUM ; ++ I ) {
_canvas.fillRect ( new Rectangle ( _v[I].x - 5 , _v[I].y - 5 , 10 , 10 ) , 0xFF00 ) ;
}
}
}
class Chromosome {
public var _v:Vector.<int> ;
public var _fitness:int = 0 ;
public function Chromosome () {
var I:int ;
_v = new Vector.<int> ;
for ( I = 0 ; I < City_NUM ; ++ I ) {
_v[I] = I ;
}
for ( I = 0 ; I < City_NUM ; ++ I ) {
var J:int = Math.floor ( Math.random() * City_NUM ) ;
var T:int = _v[J] ;
_v[J] = _v[I] ;
_v[I] = T ;
}
}
public function fitnessFunction ( city:City ):void {
var I:int ;
_fitness = 0 ;
for ( I = 1 ; I < City_NUM ; ++ I ) {
var I1:int = _v[I-1] ;
var I2:int = _v[I] ;
_fitness -= Point.distance ( city._v[I1] , city._v[I2] ) ;
}
}
public function crossOver ( O:Chromosome ):Chromosome {
var I:int ;
var J:int ;
var Q:int = 0 ;
var R:int = Math.floor ( Math.random() * _v.length ) ;
var T:Chromosome = new Chromosome ;
for ( I = 0 ; I < _v.length ; ++ I ) {
T._v[I] = _v[I] ;
}
for ( I = 0 ; I < _v.length ; ++ I ) {
if ( R < I ) {
for ( J = 0 ; J < City_NUM ; ++ J ) {
if ( O._v[I] == T._v[J] ) {
Q = T._v[J] ;
T._v[J] = T._v[I];
T._v[I] = Q ;
break ;
}
}
}
}
return T ;
}
public function mutation () :Chromosome {
var C:Chromosome = new Chromosome ;
for ( I = 0 ; I < _v.length ; ++ I ) {
C._v[I] = _v[I] ;
}
var I:int = Math.floor ( Math.random() * City_NUM ) ;
var J:int = Math.floor ( Math.random() * City_NUM ) ;
var T:int = C._v[J] ;
C._v[J] = C._v[I] ;
C._v[I] = T ;
return C ;
}
}
class Population {
private var _now:Vector.<Chromosome> ;
public function Population () {
var I:int ;
_now = new Vector.<Chromosome> ;
for ( I = 0 ; I < Population_NUM ; ++ I ) {
_now.push ( new Chromosome ) ;
}
}
public function run ( city:City ) :void {
var I:int ;
var C:Chromosome ;
var L:int ;
L = _now.length ;
for ( I = 0 ; I < L ; ++ I ) {
if ( _now[I] == _INDEX ) {
continue ;
}
if ( Math.random() < .5 ) {
C = _now[I].crossOver ( _now[ Math.floor ( Math.random() * _now.length ) ] ) ;
_now.push ( C ) ;
}
}
L = _now.length ;
for ( I = 0 ; I < L ; ++ I ) {
if ( _now[I] == _INDEX ) {
continue ;
}
if ( Math.random() < .005 ) {
C = _now[I].mutation () ;
_now.push ( C ) ;
}
}
for ( I = 0 ; I < _now.length ; ++ I ) {
_now[I].fitnessFunction ( city ) ;
}
_now.sort ( function ( A:Chromosome , B:Chromosome ) :Number { return B._fitness - A._fitness ; } ) ;
if ( _WORTH < _now[0]._fitness ) {
_INDEX = _now[0] ;
_WORTH = _now[0]._fitness ;
trace ( _WORTH ) ;
}
for ( I = 1 ; I < _now.length ; ++ I ) {
if ( _now[I - 1]._fitness == _now[I]._fitness ) {
_now.splice ( I , 1 ) ;
}
}
if ( Population_NUM < _now.length ) {
_now.splice ( Population_NUM , _now.length - Population_NUM ) ;
}
}
public function render ( city:City ):void {
var I:int ;
var J:int ;
var Q:int ;
var R:Number ;
var D1:Point ;
var D2:Point ;
var C:Vector.<int> ;
for ( I = 0 ; I < _now.length ; ++ I ) {
C = _now[I]._v ;
for ( J = 1 ; J < C.length ; ++ J ) {
D1 = city._v[C[J-1]] ;
D2 = city._v[C[J]] ;
for ( Q = 0 ; Q < 150 ; ++ Q ) {
R = Q / 150 ;
_canvas.setPixel (
D1.x * ( 1 - R ) + D2.x * R ,
D1.y * ( 1 - R ) + D2.y * R ,
0x0080
) ;
}
}
}
if ( _INDEX ) {
C = _INDEX._v ;
for ( J = 1 ; J < C.length ; ++ J ) {
D1 = city._v[C[J-1]] ;
D2 = city._v[C[J]] ;
for ( Q = 0 ; Q < 300 ; ++ Q ) {
R = Q / 300 ;
_canvas.setPixel (
D1.x * ( 1 - R ) + D2.x * R ,
D1.y * ( 1 - R ) + D2.y * R ,
0xFF0000
) ;
}
}
}
}
}