geneticalgorithm.as

遗传算法,Flex做的算法.比较能够说明算法的精确性

package com.mh.genetics
{
	import flash.display.Shape;
	import flash.display.Graphics;
	import mx.collections.ArrayCollection;
	import mx.collections.Sort;
	import mx.collections.SortField;
	
	public class GeneticAlgorithm
	{
		[Bindable]
		public var chromosomes:ArrayCollection;
		
		private var chromosomeNumber:int;		
		private var chromosomeLength:int;

		private var crossoverLikelihood:Number;		
		private var mutationLikelihood:Number;
		
		private var width:Number;
		private var height:Number;
		
		private var startX:Number;
		private var startY:Number;
		
		private var generationCount:Number = 0;
		
		[Bindable]
		public var isInitialised:Boolean = false;
		
		private var _obstacle:Boolean = false;	
		
		
		public function GeneticAlgorithm( chromosomeNumber:int, chromosomeLength:int, crossoverLikelihood:Number, mutationLikelihood:Number, 
											width:Number, height:Number, startX:Number, startY:Number, obstacle:Boolean )
		{
			this.chromosomeNumber = chromosomeNumber;
			this.chromosomeLength = chromosomeLength;
			
			this.crossoverLikelihood = crossoverLikelihood;
			this.mutationLikelihood = mutationLikelihood;
			
			this.width = width;
			this.height = height;
			this.startX = startX;
			this.startY = startY;		
			
			if( crossoverLikelihood >= 1 )
				throw new Error("High crossover percentages will cause massive performance reductions");

			addObstacle( obstacle );

			this.isInitialised = false;
		}		
		
		/**
		 * Initialise all chromosomes to random values
		 */
		public function init():void
		{	
			chromosomes = new ArrayCollection();
			generationCount++;
			
			var sort:Sort = new Sort();
			sort.fields = [new SortField("fitness",true,true,true)];
			chromosomes.sort = sort;
			chromosomes.refresh();
				
			for( var i:int = 0; i<chromosomeNumber;i++)
			{
				var current:Chromosome = new Chromosome()
				
				while( current.dna.length < chromosomeLength )
				{
					current.dna += randomGene();
				}
				
				current.fitness = testFitness( current );
				current.generation = generationCount;
				
				chromosomes.addItem(current);
			}
			
			this.isInitialised = true;
		}
		
		/**
		 * Returns the fitness of the given chromosome
		 */
		private function testFitness(c:Chromosome):Number
		{
			var fitness:Number = 0;
			var x:int = startX;
			var y:int = startY;
				
			for( var j:int = 0;j<c.dna.length;j++)
			{
				switch( c.dna.charAt(j) )
				{
					case "A":
						x += 1;
						break;
					case "B":
						x -= 1;
						break;
					case "C":
						y += 1;
						break;
					case "D":
						y -= 1;
						break;
				}
				
				if( !isInBounds(x,y) )
					break;
					 
				fitness = Math.max( x, fitness );
			}
			
			return fitness;
		}
		
		/**
		 * Adds an obstacle to the problem space
		 * This adds a different selective pressure
		 */
		private function addObstacle(value:Boolean):void
		{
			_obstacle = value;
			
			if( !isInitialised )
				return;
			
			for( var i:int = 0; i<chromosomeNumber;i++)
			{				
				chromosomes[i].fitness = testFitness( chromosomes[i] );
			}
		}
		/**
		 * Compute the next generation of the algorithm
		 * This includes selection and breeding
		 */
		public function nextStep():void
		{
			if( !isInitialised )
				throw new Error("Must initialise algorithm first.");
			
			selection();
			
			breeding();
			
			chromosomes.refresh();
		}
		
		/**
		 * selection()
		 * Only the fittest individuals survive, so the population is reduced by half.
		 * We randomly kill an individual in the bottom third of the population until only half are left
		 */
		private function selection():void
		{
			var targetNum:int = chromosomes.length/2;
				
			while( chromosomes.length > targetNum )
			{
				var safe:int = chromosomes.length * 2/3;
				var danger:int = chromosomes.length/3;
			
				var death:int = ( Math.random() * danger )
				
				chromosomes.removeItemAt( safe + death );
			}
		}
		
		/**
		 * breeding()
		 * Two individuals are selected at random and bred to make two chilren
		 * This repeats until the population is restored to the full number
		 */
		private function breeding():void
		{
			generationCount++;
			
			while( chromosomes.length < chromosomeNumber )
			{
				var parent1:Chromosome = chromosomes.getItemAt( Math.random()*chromosomes.length ) as Chromosome;
				var parent2:Chromosome = chromosomes.getItemAt( Math.random()*chromosomes.length ) as Chromosome;
				
				var child1:Chromosome = new Chromosome();
				var child2:Chromosome = new Chromosome();
				
				for( var i:int=0; i<chromosomeLength; i++ )
				{
					if( Math.random() < crossoverLikelihood )
					{
						var tmp:Chromosome = parent1;
						parent1 = parent2;
						parent2 = tmp;
					}
					
					var gene:String = parent1.dna.charAt(i);
					if( Math.random() < mutationLikelihood )
						child1.dna += randomGene();
					else
						child1.dna += gene;
					
					gene = parent2.dna.charAt(i);
					if( Math.random() < mutationLikelihood )
						child2.dna += randomGene();
					else
						child2.dna += gene;
				}
				
				child1.fitness = testFitness( child1 );
				child1.generation = generationCount;
				chromosomes.addItem(child1);
				
				child2.fitness = testFitness( child2 );
				child2.generation = generationCount;
				chromosomes.addItem(child2);				
			}
		}
			
		/**
		 * Returns a random letter from {A,B,C,D}
		 */
		private function randomGene():String
		{
			var tmp:int = ( Math.random() * 1000 ) % 4;
			switch( tmp )
			{
				case 0:
					return "A";
				case 1:
					return "B";
				case 2:
					return "C";
				case 3:
					return "D";
				default: // impossible to get here
					return "A";
			}
		}
		
		/**
		 * Displays the paths represented by each chromosome 
		 */
		public function visualise( g:Graphics ):void
		{
			if( !isInitialised )
				throw new Error("Must initialise algorithm first.");
			
			g.clear();
			
			var startColour:Number = 0x0000FF;
			var colourStep:Number = ( 0xFF0000 - 0x0000FF ) / chromosomes.length;
			
			for( var i:int = 0; i<chromosomes.length;i++)
			{
				drawChromosome( g, chromosomes[i], startColour + i*colourStep, 0 );
			}
			
			var best:Chromosome = chromosomes[0];
			if( best.fitness == width )
			{
				drawChromosome( g, best, 1, 2 );
			}
			
			if( _obstacle )
			{
				g.moveTo( 0.6*width, 0.25*height );
				g.lineStyle( 0, 0);
				g.beginFill( 0x555555 );
				g.drawRect( 0.6*width, 0.25*height, 0.1*width, 0.5*height );
				g.endFill();
			}
			
		}
		
		private function drawChromosome( g:Graphics, chromosome:Chromosome, colour:uint, lineWidth:Number ):void
		{
			var x:int = startX;
			var y:int = startY;
			
			g.lineStyle( lineWidth, colour);			
			g.moveTo( x, y );
			
			for( var j:int = 0; j<chromosome.dna.length; j++)
			{
				switch( chromosome.dna.charAt(j) )
				{
					case "A":
						x += 1;
						break;
					case "B":
						x -= 1;
						break;
					case "C":
						y += 1;
						break;
					case "D":
						y -= 1;
						break;
				}
				
				if( !isInBounds(x,y) )
					break;
					 
				g.lineTo( x, y );
			}
		}
		
		/**
		 * Determines is the given point is a legal one for this problem space
		 */ 
		private function isInBounds(x:int,y:int):Boolean
		{
			if( x < 0 || x > width )
				return  false;
			
			if( y < 0 || y > height )
				return  false; 
				
			if( _obstacle )
			{
				if( y > 0.25*height && y < 0.75*height && x > 0.6*width && x < 0.7*width )
					return false;
			}
				
			return true;			
		}
	}
}