超適当GA

/**
 * Copyright keno42 ( http://wonderfl.net/user/keno42 )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/lNPb
 */

package 
{
	import flash.display.Graphics;
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.text.TextField;
	
	/**
	 * Graphics.drawCircle と drawRoundRect が壊れました。
	 * 別の方法で、半径 CIRCLE_RADIUS の 円を書きなさい。
	 * @mxmlc -o bin/CircleTest.swf -load-config+=obj\Alltest3Config.xml
	 * @author jc at bk-zen.com
	 */
	public class Main extends Sprite
	{
		private const ANSWER_COLOR: uint = 0x003366;
		private const COLOR: uint = 0x3399CC;
		private const CIRCLE_RADIUS: Number = 50;
		
		public function Main() 
		{
			if (stage) init();
			else addEventListener(Event.ADDED_TO_STAGE, init);
		}
		
		private function init(e: Event = null): void 
		{
			removeEventListener(Event.ADDED_TO_STAGE, init);
			//
			var centerX: Number = (stage.stageWidth - CIRCLE_RADIUS) / 2;
			var centerY: Number = (stage.stageHeight - CIRCLE_RADIUS) / 2;
			var g: Graphics = graphics;
			// 差を見るために解答として先に半径+1 の円を描いておきます。
			
			var answer:Sprite = new Sprite();
			g = answer.graphics;
			g.beginFill(ANSWER_COLOR); g.drawCircle(CIRCLE_RADIUS, CIRCLE_RADIUS, CIRCLE_RADIUS + 1);
			g.endFill();
			Teacher.sample = answer;
			addChild(tf);
			tf.text = "0";
			// 
			addEventListener(Event.ENTER_FRAME, onEnterFrame);
		}
		private function onEnterFrame(e:Event):void{
			var centerX: Number = (stage.stageWidth - CIRCLE_RADIUS) / 2;
			var centerY: Number = (stage.stageHeight - CIRCLE_RADIUS) / 2;
			var g: Graphics = graphics;
			g.clear();
			g.beginFill(ANSWER_COLOR); g.drawCircle(centerX, centerY, CIRCLE_RADIUS + 1);
			g.endFill();
			drawCircle(g, centerX, centerY, CIRCLE_RADIUS, COLOR);
		}
		private var people:GApeople = new GApeople(10, 2 * int(CIRCLE_RADIUS * CIRCLE_RADIUS * Math.PI));
		private var tf:TextField = new TextField();
		/**
		 * これを作る。
		 * @param	g
		 * @param	x
		 * @param	y
		 * @param	r
		 * @param	color
		 */
		public function drawCircle(g: Graphics, x: Number, y: Number, r: Number, color: uint): void
		{
			var best:GAperson = Teacher.evol(people, 2);
			g.lineStyle(0, color);
			g.moveTo(x, y);
			var arr:Array = best.param;
			var count:int = best.param.length;
			for ( var i:int = 0; i < count; i++ ) {
				x += arr[i] + arr[i] - 1; // 0 -> -1, 1 -> 1
				i++;
				y += arr[i] + arr[i] - 1; // 0 -> -1, 1 -> 1
				g.lineTo(x, y);
			}
			tf.text = String(int(tf.text) + 1);
		}
		
	}

}

class GAperson {
	public var param:Array = [];
	public function GAperson(length:int):void {
		for ( var i:int = 0; i < length; i++ ) {
			param.push( (Math.random() + 0.5) | 0);
		}
		
	}
}

class GApeople {
	public var people:Array = [];
	public function GApeople(peopleNum:int, geneLength:int):void {
		for ( var i:int = 0; i < peopleNum; i++ ) {
			people.push(new GAperson(geneLength));
		}
	}
}

import flash.display.BitmapData;
import flash.display.DisplayObject;
import flash.display.Sprite;

class Teacher {
	public static var sample:DisplayObject;
	private static const MUTATE_RATE:Number = 0.99;
	/**
	 * 進化。最優秀な一人を返す。
	 * @param	people
	 * @return
	 */
	public static function evol(people:GApeople, parentsNum:int = 1):GAperson {
		var arr:Array = people.people;
		var best:Array = [];
		var worst:Array = [];
		var bestScore:Array = [];
		var worstScore:Array = [];
		var parentsNum2:int = 2 * parentsNum;
		for ( var j:int = 0; j < parentsNum; j++ ) {
			best.push(arr[0], arr[0]);
			worst.push(arr[0], arr[0]);
			bestScore.push( -9999999999999, -9999999999999 );
			worstScore.push( 9999999999999, 9999999999999 );
		}
		
		
		var count:int = arr.length;
		for ( var i:int = 0; i < count; i++ ) {
			var score:int = test(arr[i]);
			for ( j = 0; j < parentsNum2; j++ ) {
				if ( score > bestScore[j] ) {
					bestScore[j] = score;
					best[j] = arr[i];
					break;
				} else if ( score < worstScore[j] ) {
					worstScore[j] = score;
					worst[j] = arr[i];
					break;
				}
			}
		}
                var maxScore:int = -999999999;
                var ret:GAperson;
                for ( j = 0; j < parentsNum2; j++ ) {
                    if( bestScore[j] > maxScore ) ret = best[j];
                }
		for ( j = 0; j < parentsNum2; j+=2 ) {
			var fatherIndex:int = best.length * Math.random();
			var father:GAperson = best[fatherIndex];
			best = best.splice(fatherIndex, 1);
			var motherIndex:int = best.length * Math.random();
			var mother:GAperson = best[motherIndex];
			best = best.splice(motherIndex, 1);
			cross( father, mother, worst[j], worst[j + 1] );
		}
		return ret;
	}
	
	// 点数判定
	private static function test(person:GAperson):int {
		var sp:Sprite = new Sprite();
		var arr:Array = person.param;
		var count:int = arr.length;
		var score:int = 0;
		var x:int = sample.width * 0.5;
		var y:int = sample.height * 0.5;
		var bmp:BitmapData = new BitmapData(sample.width, sample.height, true, 0x0);
		bmp.draw( sample );
		for ( var i:int = 0; i < count; i++ ) {
			x += arr[i] + arr[i] - 1; // 0 -> -1, 1 -> 1
			i++;
			y += arr[i] + arr[i] - 1; // 0 -> -1, 1 -> 1
			if ( bmp.getPixel32(x, y) ){
                            score++;
			    bmp.setPixel32(x, y, 0x0);
                        } else score--;
		}
		return score;
	}
	
	private static function cross(father:GAperson, mother:GAperson, son:GAperson, daughter:GAperson):void {
		var count:int = father.param.length;
		var p:int = count * Math.random();
		for ( var i:int = 0; i < p; i++ ) {
			son.param[i] = father.param[i];
		}
		for ( ; i < count; i++ ) {
			son.param[i] = mother.param[i];
		}
		p = count * Math.random();
		for ( i = 0; i < p; i++ ) {
			daughter.param[i] = mother.param[i];
		}
		for ( ; i < count; i++ ) {
			daughter.param[i] = father.param[i];
		}
		while ( Math.random() < MUTATE_RATE ) {
			p = count * Math.random();
			son.param[p] = 1 - son.param[p];
		}
		while ( Math.random() < MUTATE_RATE ) {
			p = count * Math.random();
			daughter.param[p] = 1 - daughter.param[p];
		}
	}
	
}