Friday, February 4, 2011

Simple Genetic Algorithm to create Equation equaling a target number

/*By Akhier Dragonheart 2-4-2011*/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Genetic1_01console
{
    class Program
    {
        const Int32 Mutation_Rate = 100; /*the higher the number the less likely it is*/
        static Int32 sm = 1, ssm;   /*stores the number for the smallest(sm) fitness score and second smallest(ssm) fitness score*/
        static Int32[] fit = new Int32[20];   /*fitness of each equation*/
        static Int32 a, b, d; static String c, f = "";   /*free use variables for all your for and while loop needs or if you just want to store a number for a bit*/
        static Int32[,] num = new Int32[20, 36];   /*stores the zeros and ones*/
        static Int32[,] numstore = new Int32[2, 36]; /*Stores num smallest and second smallest*/
        static String[, ,] chst = new String[20, 9, 2];   /*stores symbols and whether operator or number*/
        static String[] equ = new String[20]; static String[,] cequ = new String[20, 10];   /*stores equations*/
        static Char[] CT = { '+', '-', '*', '/' };   /*To trim operators off the end of equation string equ[]*/
        static Int32 target;   /*the target number*/
        static String[] numstr = new String[20];
        static Random rng = new Random();   /*used to get a random number form a min to a max+1 - rng.next(min,max+1)*/

        static void ss(int a1, int a2, int b1, int b2, int c1, int c2)   /*Finds smallest and second smallest number out of 3*/
        {
            if ((a1 < b1) && (a1 < c1))
            {
                sm = a2;
                if (b1 < c1)
                {
                    ssm = b2;
                }
                else
                {
                    ssm = c2;
                }
            }
            else if ((b1 < a1) && (b1 < c1))
            {
                sm = b2;
                if (a1 < c1)
                {
                    ssm = a2;
                }
                else
                {
                    ssm = c2;
                }
            }
            else if ((c1 < a1) && (c1 < b1))
            {
                sm = c2;
                if (a1 < b1)
                {
                    ssm = a2;
                }
                else
                {
                    ssm = b2;
                }
            }
            else
            {
                if (a1 == b1)
                {
                    if (a1 < c1)
                    {
                        sm = a2;
                        ssm = b2;
                    }
                    else
                    {
                        sm = c2;
                        ssm = a2;
                    }
                }
                else if (a1 == c1)
                {
                    if (a1 < b1)
                    {
                        sm = a2;
                        ssm = c2;
                    }
                    else
                    {
                        sm = b2;
                        ssm = a2;
                    }
                }
                else
                {
                    if (b1 < a1)
                    {
                        sm = b2;
                        ssm = c2;
                    }
                    else
                    {
                        sm = a2;
                        ssm = b2;
                    }
                }
            }
        }
        static void find_and_store_small()   /*Finds and then stores the 2 smallest fitness num[,]*/
        {
            ss(fit[0], 0, fit[1], 1, fit[2], 2);
            for (a = 3; a < 20; a++)
            {
                ss(fit[sm], sm, fit[ssm], ssm, fit[a], a);
            }
            for (a = 0; a < 20; a++) { numstore[0, a] = num[sm, a]; numstore[1, a] = num[ssm, a]; }
        }

        static void trans(string input, int output1, int output2)   /*Translates the binary to characters*/
        {
            switch (input)
            {
                case "0000":
                    chst[output1, output2, 0] = "0";
                    chst[output1, output2, 1] = "n";
                    break;
                case "0001":
                    chst[output1, output2, 0] = "1";
                    chst[output1, output2, 1] = "n";
                    break;
                case "0010":
                    chst[output1, output2, 0] = "2";
                    chst[output1, output2, 1] = "n";
                    break;
                case "0011":
                    chst[output1, output2, 0] = "3";
                    chst[output1, output2, 1] = "n";
                    break;
                case "0100":
                    chst[output1, output2, 0] = "4";
                    chst[output1, output2, 1] = "n";
                    break;
                case "0101":
                    chst[output1, output2, 0] = "5";
                    chst[output1, output2, 1] = "n";
                    break;
                case "0110":
                    chst[output1, output2, 0] = "6";
                    chst[output1, output2, 1] = "n";
                    break;
                case "0111":
                    chst[output1, output2, 0] = "7";
                    chst[output1, output2, 1] = "n";
                    break;
                case "1000":
                    chst[output1, output2, 0] = "8";
                    chst[output1, output2, 1] = "n";
                    break;
                case "1001":
                    chst[output1, output2, 0] = "9";
                    chst[output1, output2, 1] = "n";
                    break;
                case "1010":
                    chst[output1, output2, 0] = "+";
                    chst[output1, output2, 1] = "o";
                    break;
                case "1011":
                    chst[output1, output2, 0] = "-";
                    chst[output1, output2, 1] = "o";
                    break;
                case "1100":
                    chst[output1, output2, 0] = "*";
                    chst[output1, output2, 1] = "o";
                    break;
                case "1101":
                    chst[output1, output2, 0] = "/";
                    chst[output1, output2, 1] = "o";
                    break;
                default:
                    chst[output1, output2, 0] = "x";
                    chst[output1, output2, 1] = "x";
                    break;
            }
        }

        static int mab(int input1, int input2)   /*Used in calcequ to do the actual math*/
        {
            switch (cequ[a, input2 - 1])
            {
                case "+":
                    return Math.Abs(input1 + Convert.ToInt32(cequ[a, input2]));
                case "-":
                    return Math.Abs(input1 - Convert.ToInt32(cequ[a, input2]));
                case "*":
                    return Math.Abs(input1 * Convert.ToInt32(cequ[a, input2]));
                case "/":
                    if ((input1 != 0) && (Convert.ToInt32(cequ[a, input2]) != 0))   /*Prevents deviding by zero*/
                    {
                        return Math.Abs(input1 / Convert.ToInt32(cequ[a, input2]));
                    }
                    else
                    {
                        return 0;
                    }
                default:   /*If it gets here something is really wrong so make it extra unfit*/
                    return 1000;
            }
        }
        static void calcequ()   /*Takes the chst and makes real equations then calculates fitness*/
        {
            for (a = 0; a < 20; a++)
            {
                equ[a] = ""; b = 0; c = "x"; d = 0;
                while (b < 9)   /*This and the other b<9 checks inside this make sure you do not excede the chst array bounds*/
                {
                    while ((c != "n") && (b < 9)) { c = chst[a, b, 1]; b++; }
                    if (b < 9) { equ[a] += "" + chst[a, b - 1, 0]; cequ[a, d] = chst[a, b - 1, 0]; d++; }
                    while ((c != "o") && (b < 9)) { c = chst[a, b, 1]; b++; }
                    if (b < 9) { equ[a] += "" + chst[a, b - 1, 0]; cequ[a, d] = chst[a, b - 1, 0]; d++; }
                }
                if (((d % 2) == 0) && (d != 0)) { d -= 1; }
                cequ[a, d] = "x";
                equ[a] = equ[a].TrimEnd(CT);   /*Trim operators of end of string*/
                if (cequ[a, 1] == "x") { fit[a] = Math.Abs(target - Convert.ToInt32(cequ[a, 0])) - 1; }
                else if (cequ[a, 3] == "x") { fit[a] = Math.Abs(target - mab(Convert.ToInt32(cequ[a, 0]), 2)) - 1; }
                else if (cequ[a, 5] == "x") { fit[a] = Math.Abs(target - mab(mab(Convert.ToInt32(cequ[a, 0]), 2), 4)) - 1; }
                else if (cequ[a, 7] == "x") { fit[a] = Math.Abs(target - mab(mab(mab(Convert.ToInt32(cequ[a, 0]), 2), 4), 6)) - 1; }
                else if (cequ[a, 9] == "x") { fit[a] = Math.Abs(target - mab(mab(mab(mab(Convert.ToInt32(cequ[a, 0]), 2), 4), 6), 8)) - 1; }
                else { fit[a] = 1000; }   /*A problem has happened if it gets here so make it extra unfit*/
            }
        }

        static void Main_Calc()   /*Where all the first calculations happen and lst is updated*/
        {
            calcequ();
            Console.Clear();
            for (a = 0; a < 20; a++) { Console.WriteLine(numstr[a]); Console.WriteLine(equ[a] + f.PadRight(10 - equ[a].Length) + "Fitness: " + fit[a]); }
            find_and_store_small();
            Console.WriteLine(""); Console.WriteLine(""); Console.WriteLine("");
            Console.WriteLine("Fittest"); Console.WriteLine(numstr[sm]);
            Console.WriteLine(equ[sm] + f.PadRight(10 - equ[sm].Length) + "Fitness: " + fit[sm]);
            Console.WriteLine("");
            Console.WriteLine("Secon Fittest"); Console.WriteLine(numstr[ssm]);
            Console.WriteLine(equ[ssm] + f.PadRight(10 - equ[sm].Length) + "Fitness: " + fit[ssm]);
            if (fit[sm] == 0) { Console.WriteLine("You have reached the goal of matching the target!"); }
        }
        static void ReCalc()   /*Where new numbers are put together and the next generation is formed*/
        {
            for (a = 0; a < 20; a++)
            {
                numstr[a] = "";
                d = rng.Next(0, 36);
                for (b = 0; b < 36; b++)
                {
                    if (b < d) { num[a, b] = numstore[0, b]; } else { num[a, b] = numstore[1, b]; }   /*When b is less then random number d it uses num[20,b] otherwise it will use num[21,b]*/
                    if (rng.Next(0, Mutation_Rate) == 0) { if (num[a, b] == 0) { num[a, b] = 1; } else { num[a, b] = 1; } }   /*This flips a bit and mutates the code with a 1 in a hundred chance*/
                    numstr[a] += num[a, b];
                }
                for (b = 0; b < 9; b++) { trans("" + num[a, 0 + (b * 4)] + num[a, 1 + (b * 4)] + num[a, 2 + (b * 4)] + num[a, 3 + (b * 4)], a, b); }   /*Fills chst from num*/
            }
        }

        static void Main(string[] args)
        {
            Int64 Gen = 1;   /*the generation*/
            ConsoleKeyInfo cki;

            target = rng.Next(0, 101);   /*sets the target number*/
            Console.WriteLine("The target is : " + target + "   Generation:" + Convert.ToString(Gen));   /*makes label show target number*/
            for (a = 0; a < 20; a++)
            {
                numstr[a] = "";
                for (b = 0; b < 36; b++) { num[a, b] = Convert.ToInt32(rng.Next(0, 2)); numstr[a] += num[a, b]; }   /*Fills num completely by random and fills numstr with num*/
                for (b = 0; b < 9; b++) { trans("" + num[a, 0 + (b * 4)] + num[a, 1 + (b * 4)] + num[a, 2 + (b * 4)] + num[a, 3 + (b * 4)], a, b); }   /*Fills chst from num*/
            }
            Main_Calc();
            do
            {
                cki = Console.ReadKey();
                Gen++;
                Console.WriteLine("The target is : " + target + "   Generation:" + Convert.ToString(Gen));
                ReCalc();
                Main_Calc();
            } while (cki.Key != ConsoleKey.Escape);

           
        }
    }
}

No comments:

Post a Comment