equationgenome.cs

More AI...(GEP) Gene Expression Programming in C# and .NET 由Michael Gold用C#开发的GEP程序.

using System;
using System.Collections;
using GEPAlgorithm;

namespace GeneticAlgorithm
{
	/// <summary>
	/// Summary description for EquationNode.
	/// Equation node represents a symbolic equation that solves a problem
	/// In this case we'll use the following keys to represent our node
	/// 0: a 1: b 2: *  3: / 4: + 5: -  6: Q (square root)
	/// </summary>
	/// 
	public class EquationGenome : Genome
	{
		EquationNode TheNode;
		ArrayList TheArray = new ArrayList();
		public static Random TheSeed = new Random((int)DateTime.Now.Ticks);
		int TheMin = 0;
		int TheMax = 6;
		int CurrentXPos = 0;
		int CurrentYPos = 0;
		int PreviousSeed = 2;
		public bool TrialFitness; // this needs to be perfect or else we have to throw out the gene

		public override int CompareTo(object a)
		{
			EquationGenome Gene1 = this;
			EquationGenome Gene2 = (EquationGenome)a;
			return Math.Sign(Gene2.CurrentFitness  -  Gene1.CurrentFitness);
		}


		public override void SetCrossoverPoint(int crossoverPoint)
		{
			CrossoverPoint = 	crossoverPoint;
		}

		public EquationGenome()
		{
		}


		public EquationGenome(long length, object min, object max)
		{
			//
			// TODO: Add constructor logic here
			//
			Length = length;
			TheMin = (int)min;
			TheMax = (int)max;
			CurrentXPos = 0;
			CurrentYPos = 0;
			for (int i = 0; i < Length; i++)
			{
				int nextValue = (int)GenerateGeneValue(min, max);
				TheArray.Add(nextValue);
			}
		}

		public override void Initialize()
		{

		}

		public override bool CanDie(float fitness)
		{
			if (CurrentFitness <= (int)(fitness * 100.0f))
			{
				return true;
			}

			return false;
		}


		public override bool CanReproduce(float fitness)
		{
			if (EquationGenome.TheSeed.Next(100) >= (int)(fitness * 100.0f))
			{
				return true;
			}

			return false;
		}


		public override object GenerateGeneValue(object min, object max)
		{
			int nextSeed = 0;
			nextSeed = TheSeed.Next((int)min, (int)max);
			return nextSeed;
		}

		#region GenerateSmartGene
		/*
				public override object GenerateGeneValue(object min, object max)
				{
					bool hasWall = true;
					int nextSeed = 0;
					int counter = 0;
					while (hasWall)
					{
						nextSeed = TheSeed.Next((int)min, (int)max);
						switch (nextSeed)
						{
							case 0:  // up
								if (PreviousSeed == 2)
								{	
									break; // don't backtrack
								}
								hasWall = TheMaze.HasWall(CurrentXPos, this.CurrentYPos, CurrentXPos, CurrentYPos - 1);
								if (hasWall == false)
								{
								 CurrentYPos--;
								}
								break;
							case 1:  // left
								if (PreviousSeed == 3)
								{	
									break; // don't backtrack
								}

								hasWall = TheMaze.HasWall(CurrentXPos, this.CurrentYPos, CurrentXPos - 1, CurrentYPos);
								if (hasWall == false)
								{
									CurrentXPos--;
								}
								break;
							case 2:  // down
								if (PreviousSeed == 0)
								{	
									break; // don't backtrack
								}
								hasWall = TheMaze.HasWall(CurrentXPos, this.CurrentYPos, CurrentXPos, CurrentYPos + 1);
								if (hasWall == false)
								{
									CurrentYPos++;
								}
								break;
							case 3:  // right
								if (PreviousSeed == 1)
								{	
									break; // don't backtrack
								}

								hasWall = TheMaze.HasWall(CurrentXPos, this.CurrentYPos, CurrentXPos + 1, CurrentYPos);
								if (hasWall == false)
								{
									CurrentXPos++;
								}
								break;
						}

						counter++;
						if (counter > 10)
							break;

					}

					return nextSeed;

				}

		*/

#endregion 



		public override void Mutate()
		{
			int AffectedGenes = TheSeed.Next((int)this.Length); // determine how many genes to mutate
			for (int i = 0; i < AffectedGenes; i++)
			{
				MutationIndex = TheSeed.Next((int)Length);
				//				int val = (int)GenerateGeneValue(TheMin, TheMax);
				TheArray[MutationIndex] = ((int)TheArray[MutationIndex] + 1) % 7;
			}

		}

		// This fitness function calculates the closest product sum
		private float CalculateClosestProductSum()
		{
			// fitness for a perfect number

			float sum = 0.0f;
			float product = 1.0f;
			for (int i = 0; i < Length; i++)
			{
				sum += (int)TheArray[i];
				product *= (int)TheArray[i];
			}
			if (product == sum)
			{
				CurrentFitness = 1;
			}
			else
			{
				CurrentFitness = Math.Abs(Math.Abs(1.0f/(product - sum)) - 0.02f);
			}
			
			return CurrentFitness;
		}


		// This fitness function calculates the closest product sum
		private float CalculateClosestSumTo10()
		{
			float sum = 0.0f;
			for (int i = 0; i < Length; i++)
			{
				sum += (int)TheArray[i];
			}

			if (sum == 10)
				return 1;
			else
				return Math.Abs(Math.Abs(1.0f/(sum - 10)) - 0.02f);

		}

		// This fitness function calculates the fitness of distance travelled
		// from upper left to lower right



		#region fitness2

		// This fitness function calculates the fitness of distance travelled
		/*		// from upper left to lower right
				private float CalculateMazeDistanceFitness()
				{
					float sum = 0.0f;
					int cellPreviousPosX = 0;
					int cellPreviousPosY = 0;
					int cellPosX = 0;
					int cellPosY = 0;
					int trialnumber = 0;
					int backTrack = 0;
					int hasWall = 0;
					int maxConsecutiveNoWalls = 0;
					int consecutiveNoWalls = 0;
					int previousDirection = 0;
					for (int i = 0; i < Length; i++)
					{
						switch ((int)TheArray[i])
						{
							case 0:  // up
								cellPosY--;
								break;
							case 1:  // left
								cellPosX--;
								break;
							case 2:  // down
								cellPosY++;
								break;
							case 3:  // right
								cellPosX++;
								break;
						}

						if ( (previousDirection + 2) % 4 == (int)TheArray[i])
						{
							backTrack++;
						}

						previousDirection = (int)TheArray[i];

						if (maxConsecutiveNoWalls < consecutiveNoWalls)
								maxConsecutiveNoWalls = consecutiveNoWalls;

						if (TheMaze.HasWall(cellPreviousPosX, cellPreviousPosY, cellPosX, cellPosY))
						{
							consecutiveNoWalls = 0;
						}
						else
						{
							consecutiveNoWalls++;
						}

		//				trialnumber++;


						cellPreviousPosX = cellPosX;
						cellPreviousPosY = cellPosY;
					}

					// the score is the distance squared from the origin
					// since the greatest distance is the distance to the destination
					// the lower right hand corner
		//			sum = ((float)(cellPosX*cellPosX + cellPosY*cellPosY))/((float)(Maze.kDimension*Maze.kDimension));  

					sum = sum + ((float)(maxConsecutiveNoWalls))/((float)this.Length);
					sum = sum + ((float)(Length - backTrack))/((float)this.Length);

					sum = sum/2;

					return sum;
				}
		*/

		#endregion 


		Stack _stack = new Stack();

		public string ReturnOperationString(string a, string b, int operation)
		{
			string result = "";
			switch(operation)
			{
				case 2: // *
					result += "(" + a + "*" + b + ")";
					break;
				case 3: // / 
					result += "(" + a + "/" + b + ")";
					break;
				case 4: // +
					result += "(" + a + "+" + b + ")";
					break;
				case 5: // - 
					result += "(" + a + "-" + b + ")";
					break;
				case 6: // Q
					result += "Sqrt(" + a +  ")";
					break;
				default:
					// +
					break;
			} // end switch

			return result;

		}


		public float DoOperation(float a, float b, int operation)
		{
			float result = 0.0f;
			switch(operation)
			{
				case 2: // *
					result = a * b;
					break;
				case 3: // / 
					if (b == 0.0f) // problem just set b to small number
					{
						b = .0001f;
					}
					result = a/b;
					break;
				case 4: // +
					result = a + b;
					break;
				case 5: // - 
					result = a - b;
					break;
				case 6: // Q
					result = (float)Math.Sqrt(a);
					break;
				default:
					// +
					break;
			} // end switch

			return result;

		}

		public string FormEquationString()
		{
			string _result = "";
			string x;
			string y;

			_stack.Clear();

			for (int i = 0; i < TheArray.Count; i++)
			{
				if ((int)TheArray[i] <= 1) // its a number
				{
					if ((int)TheArray[i] == 0) // put a on the stack
					{
						_stack.Push("a");
					}

					if ((int)TheArray[i] == 1) // put a on the stack
					{
						_stack.Push("b");
					}

				}
				else
				{
					// check if unary
					if ((int)TheArray[i] == 6) // sqrt
					{
						if (_stack.Count > 0)
						{
							x = (string)_stack.Pop();
							_result = ReturnOperationString(x, "", (int)TheArray[i]);
							_stack.Push(_result);
						}
					}
					else
					{
						if (_stack.Count > 0)
						{
							x = (string)_stack.Pop();
							if (_stack.Count > 0)
							{
								y = (string)_stack.Pop();
								_result = ReturnOperationString(x, y, (int)TheArray[i]);
								_stack.Push(_result);
							}
						}
					}

				}

			}

			return _result;
		}

		public string PostFixString = "";
		public float PerformPostFixCalculation(float a, float b)
		{
			float _result = 0.0f;
			float x;
			float y;

			_stack.Clear();

			for (int i = 0; i < TheArray.Count; i++)
			{
				if ((int)TheArray[i] <= 1) // its a number
				{
					if ((int)TheArray[i] == 0) // put a on the stack
					{
						_stack.Push(a);
					}

					if ((int)TheArray[i] == 1) // put a on the stack
					{
						_stack.Push(b);
					}

				}
				else
				{
					// check if unary
					if ((int)TheArray[i] == 6) // sqrt
					{
						if (_stack.Count > 0)
						{
							x = (float)_stack.Pop();
							_result = DoOperation(x, 0, (int)TheArray[i]);
							_stack.Push(_result);
						}
					}
					else
					{
						if (_stack.Count > 0)
						{
							x = (float)_stack.Pop();
							if (_stack.Count > 0)
							{
								y = (float)_stack.Pop();
								_result = DoOperation(x, y, (int)TheArray[i]);
								_stack.Push(_result);
				
							}
						}
					}

				}
			} // end for

			return _result;
		}

		float[,] measure = new float[8,3]{{3,4,5}, {1, 1, 1.4142f}, {1, 2, 2.23607f}, {3, 1, 3.16228f}, {6, 13, 14.31782f}, {4,3,5}, {1,3, 3.16228f}, {2, 1, 2.23607f}};

		public float CalculatePythagoreanFitness()
		{
			int index = 0;
			TheNode = new EquationNode(this, null, ref index);
			// use the node to calculate the fitness

//			Console.WriteLine (EquationNode.OutputStraightEquation(this));

			float calc = 0.0f;
			float sum = 0.0f;
			int count = measure.GetLength(0);
			for (int i = 0; i < count; i++)
			{
				calc = PerformPostFixCalculation(measure[i, 0],  measure[i, 1]);
				sum +=  100 - Math.Abs(measure[i,2] - calc);
			}
			CurrentFitness = sum;

			if (float.IsNaN(CurrentFitness))
				CurrentFitness = 0.01f;

			return CurrentFitness;
		}

		public override float CalculateFitness()
		{
			// CurrentFitness = CalculateClosestProductSum();
			//			CurrentFitness =  CalculateClosestSumTo10();
			//			CurrentFitness = CalculateMazeDistanceFitness();
			CurrentFitness = CalculatePythagoreanFitness();
			return CurrentFitness;
		}


		public override string ToString()
		{
			string strResult = "";
			//			for (int i = 0; i < Length; i++)
			//			{
			//			  strResult = strResult + ((int)TheArray[i]).ToString() + " ";
			//			}

			int index = 0;
			//			TheArray[0] = 5;			
			//			TheArray[1] = 3;			
			//			TheArray[2] = 1;			
			//			TheArray[3] = 0;			
			//			TheArray[4] = 2;			
			TheNode = new EquationNode(this, null, ref index);
			strResult += " -->  " + EquationNode.OutputStraightEquation(this);
			strResult += " -->  " + this.FormEquationString();

			strResult += " --> " + CurrentFitness.ToString();

			return strResult;
		}

		public override void CopyGeneInfo(Genome dest)
		{
			EquationGenome theGene = (EquationGenome)dest;
			theGene.Length = Length;
			theGene.TheMin = TheMin;
			theGene.TheMax = TheMax;
		}


		public override Genome Crossover(Genome g)
		{
			EquationGenome aGene1 = new EquationGenome();
			EquationGenome aGene2 = new EquationGenome();
			g.CopyGeneInfo(aGene1);
			g.CopyGeneInfo(aGene2);

			// Pick a random crossover point
			CrossoverPoint = TheSeed.Next(1, (int)Length);

			EquationGenome CrossingGene = (EquationGenome)g;
			for (int i = 0; i < CrossoverPoint; i++)
			{
				aGene1.TheArray.Add(CrossingGene.TheArray[i]);
				aGene2.TheArray.Add(TheArray[i]);
			}

			for (int j = CrossoverPoint; j < Length; j++)
			{
				aGene1.TheArray.Add(TheArray[j]);
				aGene2.TheArray.Add(CrossingGene.TheArray[j]);
			}

			// 50/50 chance of returning gene1 or gene2
			EquationGenome aGene = null;
			if (TheSeed.Next(2) == 1)			
			{
				aGene = aGene1;
			}
			else
			{
				aGene = aGene2;
			}

			return aGene;
		}

		public int this[int arrayindex]
		{
			get
			{
				return (int)TheArray[arrayindex];
			}
		}

	}
}