GP experiment

forked:0
favorite:5
lines:295
license : see code comments
modified : 2012-04-24 12:36:43

Embed: Tweet

package {
	import com.bit101.components.HSlider;
	import com.bit101.components.TextArea;
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.utils.setInterval;
	
	/** Genetic programming experiment. */
	[SWF (height=465, width=465)]
	public class GeneticProgramming extends Sprite {
		
		public var anchors:Vector.<Anchor> = new Vector.<Anchor>;
		public var pool:Vector.<NodeRoot> = new Vector.<NodeRoot>;
		
		public function GeneticProgramming () {
			pool.push (new NodeRoot);
			addEventListener (Event.ENTER_FRAME, loop);
			
			text = new TextArea (this, 50, 400, "");
			text.width = 400; text.height = 50;
			setInterval (updateText, 2345);
			
			rate = new HSlider (this, 50, 380, changeRate);
			rate.width = 400; rate.value = Node.MUTATION_RATE;
			rate.minimum = 0.05; rate.maximum = 0.5; rate.tick = 0.01;
			
			for (var i:int = 0; i <= 10; i++) {
				var anchor:Anchor = new Anchor (46.5 * i);
				anchors.push (anchor); addChild (anchor);
			}
		}
		
		public function updateText ():void {
			text.text = pool [0].toAS3 ();
		}
		
		public function changeRate (e:Event):void {
			Node.MUTATION_RATE = HSlider (e.target).value;
		}
		
		public function targetFunction (t:Number):Number {
			var i:int = t * (anchors.length - 1);
			var k:Number = (t * 465.0 - anchors [i].x) / (anchors [i + 1].x - anchors [i].x);
			return (k * anchors [i + 1].y + (1 - k) * anchors [i].y) / 465.0;
		}
		
		public function loop (e:Event):void {
			// step 1: programs reproduction
			for (var i:int = 0, n:int = pool.length; i < n; i++) {
				var offspring:NodeRoot = pool [i].clone () as NodeRoot;
				offspring.mutate ();
				pool.push (offspring);
			}
			
			// step 2: evaluation
			for (i = 0, n = pool.length; i < n; i++) {
				var program:NodeRoot = pool [i];
				program.metric = 0;
				
				// how closely do we follow target function?
				for (var j:int = 0, m:int = 20; j < m; j++) {
					var t:Number = j / m;
					var d:Number = program.evaluate (t) - targetFunction (t);
					program.metric += d * d;
				}

// short programs are boring and inaccurate, long are expensive
				var L:int = program.depth ();
				program.metric *= Math.exp (L * 0.008) + 4 * Math.exp ( -0.2 * L );
			}
			
			// step 3: selection
			pool.sort (comparePrograms);
			while (pool.length > 50) pool.pop ().dispose ();
			
			// draw best function found so far
			graphics.clear ();
			graphics.lineStyle (4, 0x9f9f9f);
			for (j = 0; j <= 30; j++) {
				graphics [(j == 0) ? "moveTo" : "lineTo"] (465 * j / 30.0, 465 * pool [0].evaluate (j / 30.0));
			}

// draw worse function at the moment
			graphics.lineStyle (0, 0x9f9f9f);
			for (j = 0; j <= 30; j++) {
				graphics [(j == 0) ? "moveTo" : "lineTo"] (465 * j / 30.0, 465 * pool [pool.length -1].evaluate (j / 30.0));
			}
		}
		
		public function comparePrograms (a:NodeRoot, b:NodeRoot):int {
			if (isFinite (a.metric) && isFinite (b.metric)) {
				if (a.metric > b.metric) {
					return 1;
				}
				if (a.metric < b.metric) {
					return -1;
				}
				return 0;
			}
			
			if (isFinite (b.metric) /* a > b */) {
				return 1;
			}
			if (isFinite (a.metric) /* a < b */) {
				return -1;
			}
			// both NaN
			return 0;
		}
		
		public var text:TextArea;
		public var rate:HSlider;
	}
}

import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.geom.Rectangle;
class Anchor extends Sprite {
	public var bounds:Rectangle;
	public function Anchor (x0:Number) {
		bounds = new Rectangle (x0, 0, 0, 465);
		x = x0;
		
		// just some initial function
		var t:Number = x0 / 465;
		y = 465 * (0.5 - (t - 0.5) * (t - 0.5));
		
		graphics.beginFill (123456);
		graphics.drawRect ( -8, -8, 16, 16);
		useHandCursor = buttonMode = true;
		addEventListener (Event.ADDED_TO_STAGE, onStage);
	}
	public function onStage (e:Event):void {
		addEventListener (MouseEvent.MOUSE_DOWN, startDragMe);
		stage.addEventListener (MouseEvent.MOUSE_UP, stopDragMe);
	}
	public function startDragMe (e:MouseEvent):void { startDrag (false, bounds); }
	public function stopDragMe (e:MouseEvent):void { stopDrag (); }
}

/** Program node base class. */
class Node {
	
	/** Defines how much the offspring is different; 0..1. */
	static public var MUTATION_RATE:Number = 0.2;
	
	protected var children:Vector.<Node> = new Vector.<Node>;
	
	final public function dispose ():void {
		for each (var child:Node in children) child.dispose ();
		children.length = 0; children = null;
	}
	
	/** Override. */
	public function evaluate (arg:Number):Number {
		return NaN;
	}
	
	/** Override. */
	public function toAS3 ():String {
		return null;
	}
	
	/** Override for terminal nodes. */
	protected function mutateSelf ():void {
		var n:int = children.length;
		n = int (n * Math.random ()) % n; // n = 0..n-1
		children.splice (n, 1, NodeFactory.randomNode ()) [0].dispose ();
	}
	
	final public function mutate ():void {
		for each (var child:Node in children) child.mutate ();
		if (Math.random () < MUTATION_RATE) mutateSelf ();
	}
	
	final public function cloneChildrenOf (template:Node):void {
		// get rid of whatever we have (default children, for example)
		while (children.length > 0) children.pop ().dispose ();
		
		for (var i:int = 0, n:int = template.children.length; i < n; i++) {
			children.push (template.children [i].clone ());
		}
	}

/** Override. */
	public function clone ():Node {
		return null;
	}
	
	final public function depth ():int {
		var d:int = 0;
		for each (var child:Node in children) d = Math.max (d, child.depth () + 1);
		return d;
	}
}

class NodeRoot extends Node {
	public var metric:Number = 0;

public function NodeRoot () {
		children.push (NodeFactory.randomNode ());
	}
	override public function evaluate (arg:Number):Number {
		return children [0].evaluate (arg);
	}
	override public function toAS3():String {
		return "function f(t:Number):Number {\n\treturn " + children [0].toAS3 () + ";\n}";
	}
	override public function clone():Node {
		var node:Node = new NodeRoot; node.cloneChildrenOf (this); return node;
	}
}

class NodeArgument extends Node {
	override public function evaluate(arg:Number):Number { return arg; }
	override public function toAS3():String { return "t"; }
	override protected function mutateSelf():void { /* do nothing */ }
	override public function clone():Node { return new NodeArgument; }
}

class NodeConstant extends Node {
	private var value:Number = Math.random ();
	override public function evaluate(arg:Number):Number { return value; }
	override public function toAS3():String { return value.toPrecision (5); }
	override protected function mutateSelf():void { value = Math.random (); }
	override public function clone():Node {
		var c:NodeConstant = new NodeConstant; c.value = value; return c;
	}
}

class NodeAddition extends Node {
	public function NodeAddition () {
		children.push (NodeFactory.randomTerminalNode (), NodeFactory.randomTerminalNode ());
	}
	override public function evaluate(arg:Number):Number {
		return children [0].evaluate (arg) + children [1].evaluate (arg);
	}
	override public function toAS3():String {
		return "(" + children [0].toAS3 () + " + " + children [1].toAS3 () + ")";
	}
	override public function clone():Node {
		var node:Node = new NodeAddition; node.cloneChildrenOf (this); return node;
	}
}

class NodeSubtraction extends Node {
	public function NodeSubtraction () {
		children.push (NodeFactory.randomTerminalNode (), NodeFactory.randomTerminalNode ());
	}
	override public function evaluate(arg:Number):Number {
		return children [0].evaluate (arg) - children [1].evaluate (arg);
	}
	override public function toAS3():String {
		return "(" + children [0].toAS3 () + " - " + children [1].toAS3 () + ")";
	}
	override public function clone():Node {
		var node:Node = new NodeSubtraction; node.cloneChildrenOf (this); return node;
	}
}

class NodeMultiplication extends Node {
	public function NodeMultiplication () {
		children.push (NodeFactory.randomTerminalNode (), NodeFactory.randomTerminalNode ());
	}
	override public function evaluate(arg:Number):Number {
		return children [0].evaluate (arg) * children [1].evaluate (arg);
	}
	override public function toAS3():String {
		return "(" + children [0].toAS3 () + " * " + children [1].toAS3 () + ")";
	}
	override public function clone():Node {
		var node:Node = new NodeMultiplication; node.cloneChildrenOf (this); return node;
	}
}

class NodeDivision extends Node {
	public function NodeDivision () {
		children.push (NodeFactory.randomTerminalNode (), NodeFactory.randomTerminalNode ());
	}
	override public function evaluate(arg:Number):Number {
		return children [0].evaluate (arg) / children [1].evaluate (arg);
	}
	override public function toAS3():String {
		return "(" + children [0].toAS3 () + " / " + children [1].toAS3 () + ")";
	}
	override public function clone():Node {
		var node:Node = new NodeDivision; node.cloneChildrenOf (this); return node;
	}
}

class NodeSine extends Node {
	public function NodeSine () {
		children.push (NodeFactory.randomTerminalNode ());
	}
	override public function evaluate(arg:Number):Number {
		return Math.sin (children [0].evaluate (arg));
	}
	override public function toAS3():String {
		return "Math.sin (" + children [0].toAS3 () + ")";
	}
	override public function clone():Node {
		var node:Node = new NodeSine; node.cloneChildrenOf (this); return node;
	}
}

class NodeSqrt extends Node {
	public function NodeSqrt () {
		children.push (NodeFactory.randomTerminalNode ());
	}
	override public function evaluate(arg:Number):Number {
		return Math.sqrt (children [0].evaluate (arg));
	}
	override public function toAS3():String {
		return "Math.sqrt (" + children [0].toAS3 () + ")";
	}
	override public function clone():Node {
		var node:Node = new NodeSqrt; node.cloneChildrenOf (this); return node;
	}
}

class NodeExp extends Node {
	public function NodeExp () {
		children.push (NodeFactory.randomTerminalNode ());
	}
	override public function evaluate(arg:Number):Number {
		return Math.exp (children [0].evaluate (arg));
	}
	override public function toAS3():String {
		return "Math.exp (" + children [0].toAS3 () + ")";
	}
	override public function clone():Node {
		var node:Node = new NodeExp; node.cloneChildrenOf (this); return node;
	}
}

class NodeFactory {
	static public function randomTerminalNode ():Node {
		return (Math.random () < 0.5) ? new NodeArgument : new NodeConstant;
	}
	static public function randomNode ():Node {
		var n:int = 3;//7;
		switch (int (n * Math.random ()) % n) {
			case 0: return new NodeAddition; break;
			case 1: return new NodeSubtraction; break;
			case 2: return new NodeMultiplication; break;
			case 3: return new NodeDivision; break;
			case 4: return new NodeSine; break;
			case 5: return new NodeSqrt; break;
			case 6: return new NodeExp; break;
		}
		// never
		return null;
	}
}

Code Fullscreen

Preview Fullscreen

bradsedito

k0rin

0xABCDEF

nki2

aobyrne :

genetic genetic-programming