GP experiment makc3d forked:0favorite:5lines:295license : 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 : geneticgenetic-programming genetic genetic-programming clone isFinite Math.exp child toPrecision graphics useHandCursor children addEventListener stopDrag startDrag sort buttonMode String pop Rectangle target MouseEvent.ADDED_TO_STAGE splice MouseEvent