% Example LaTeX Document

% Preamble:  Sets up General Parameters which are Global
\documentclass[12pt]{article}
\usepackage{doublespace,fullpage}
\usepackage{epsfig}
\usepackage{wrapfig}

% Body:  Main Document
\begin{document}
\title{Techlab Project Proposal}
\author{Austin Rachlin}
\maketitle

\begin{abstract}
      This document presents my project proposal for my senior techlab computer systems project.
	  I am attempting to create an algorithm that will solve the Majority Classification Problem
	  in an efficient and successful manner.
\end{abstract}

\section{Introduction}
I am a senior at Thomas Jefferson High School of Science and Technology in Alexandria, VA.  I am
working in the computer systems lab to complete my senior tech project.  I have chosen to use the
Java programming language to approach the Majority Classification Problem.

\section{Proposal}
    I am currently working with cellular automata and evolutionary
	computations to solve the {\bf Majority Classification
	Problem}.  I hope to beat the existing record of about .85
	completion in the MCP.  I am working with test arrays that are of length 145.
	The rules are based off of a 7-neighbor system and therefore need to be at
	least of length
	128 (there are 128 possible combinations of 7 binary cells).  However, I 
	also added an extra cell where the value (success rate)
	of the rule is stored.


\subsection{Majority Classification Problem}
{\bf Majority Classification Problem:}  The goal of the
	 Majority Classification Problem is to use evolutionary computations to
	 evolve sets of rules that will manipulate a cellular automata system
	 towards its majority.  For example, if there is an array with 65% black
	 cells, the rule (a defined array) should eventually develop the
	 landscape to an all-black array.
	 
\section{Components Necessary}
	The two main components of my project are a cellular automata system and a genetic algorithm.
	The cellular automata system will drive the program and the genetic algorithm will be modified
	to produce the best result. I do not yet know what kind of genetic algorithm I will use.
	 I will most likely have to do a lot of testing and trial-and-error to
	 figure out which variable values work the best.

\section{Project Expansion}
	 If I complete the stated problem in a timely fashion,
	 there are many direction that I would like to expand.  Instead of
	 working with a 1-D cellular automata, I could expand the program to
	 deal with 2-D or perhaps even 3-D landscapes.  Also, I might try
	 comparing the results of simultaneous evolution of the whole system
	 verses random evolution of isolated cells.  There is also the
	 possibility of dealing with systems that are not just black and white.
	 Lastly, if I complete the MCP and wish to try something else, I can
	 apply my cellular automata system to a variety of other problems.


\begin{thebibliography}{99}
\bibitem{DecRan} John December and Neil Randall, 
\underline{The World Wide Web Unleashed}, Sams Publishing, 1994.
\end{thebibliography}

\newpage
\renewcommand{\baselinestretch}{1}
\begin{appendix}
\begin{verbatim}
import java.util.Random;

/**
* @author Austin Rachlin
* Summer 2002
* Majority Classification Problem
*/

//Uses 7 neighbors


class test
{
   int[] array = new int[149];
}

class rule
{
   int[] array = new int[128];
   int val;
}
   
public class MCP
{
   public static Random rand;
   static { rand = new java.util.Random();}
   
   public static void main(String[] args)
   {
       //Calls CreateArrays
       //Calls CreateRules
       //Calls RunAllRules
       ////GA
       //Returns some value
       
       System.out.println("Hajimemashoo");
       
       //Modifiable variables
       //
       int NumberOfTests=100;
       int NumberOfRules=100;
       int NumberOfFinalTests=1000;
       //
       
       test[] TestList = new test[NumberOfTests];
       CreateArrays(TestList);
       
       rule[] RuleList = new rule[NumberOfRules];
       CreateArrays(RuleList);
       
//      int nbrs = 3;
       
       RunAllRules(RuleList, TestList);

       rule Best = SelectBest(RuleList);
       System.out.println("");
       System.out.println("BEST");
       DisplayArrays(Best);
       test[] FinalTestList = new test[NumberOfFinalTests];
       CreateArrays(FinalTestList);
       
       float result = FinalExam(Best, FinalTestList);
       //Calls SelectBest
       //Calls FinalExam
       
       System.out.println("Result: " + result + "%");


       System.out.println("");
       System.out.println("owatta!");
   }
   
   public static void DisplayArrays(test List)
   {
       String str = "";
       for (int i = 0; i < List.array.length; i++)
       {      
           str += List.array[i];
       }
       System.out.println(str);
   }
   
   public static void DisplayArrays(rule List)
   {
       String str = "";
       for (int i = 0; i < List.array.length; i++)
       {
           str += List.array[i];
       }
       System.out.println("Rule: " + str + "   val: " + List.val);
   }
   
   public static void PrintArray(test List)
   {
       String str = "";
       for (int i = 0; i < List.array.length; i++)
       {
           if (List.array[i] == 1)
           {
               str += "|";
           }
           else
           {
               str += " ";
           }
       }
       System.out.println(str);
   }

   
   public static void CreateArrays(test[] List) //Takes 2D array of arrays (empty) and # of desired arrays
   {
       //Creates all of the arrays
       //2D array of all the individual arrays
       
       for (int i = 0; i < List.length; i++)
       {
           List[i] = new test();
           for (int j = 0; j < List[i].array.length; j++)
           {
               if (rand.nextBoolean() == true)
               {
                   List[i].array[j] = 0;
               }
               else
               {
                   List[i].array[j] = 1;
               }
           }
       }
   }
   
   public static void CreateArrays(rule[] List) //Takes 2D array of arrays (empty) and # of desired arrays
   {
       //Creates all of the arrays
       //2D array of all the individual arrays
       
       for (int i = 0; i < List.length; i++)
       {
           List[i] = new rule();
           for (int j = 0; j < List[i].array.length; j++)
           {
               List[i].val = 0;
               if (rand.nextBoolean() == true)
               {
                   List[i].array[j] = 0;
               }
               else
               {
                   List[i].array[j] = 1;
               }
           }
       }
   }
   
   public static void RunAllRules(rule[] RuleList, test[] TestList) //Takes all rules and tests
   {
       //Runs a loop to call ApplyRuleToAllTests for every rule
       boolean prnt = false;
       for (int i=0; i < RuleList.length; i++)
       {
               ApplyRuleToAllTests(RuleList[i], TestList, prnt);
       }
   }
   
   public static void ApplyRuleToAllTests(rule Rule, test[] TestList, boolean prnt) //Takes a rule and all tests
   {
       //Runs a loop to call ApplyRuleToSingleTest for all tests
       for (int i =0; i < TestList.length; i++)
       {
           ApplyRuleToSingleTest(Rule, TestList[i], prnt);
       }
   }
   
   public static void ApplyRuleToSingleTest(rule Rule, test Test, boolean prnt) //Takes a rule and a test
   {
       //Applies the individual rule to an individual test
       //Calls EvalArray
       //Calls StoreArray
       //Calls RecordSuccess
       int runTime = 100;
       
       test T1 = Test;
       
       int maj = FindMajority(Test, prnt);
       
       int runs = 0;
       do
       {
           for (int i=0; i < Test.array.length; i++)
           {
               T1.array[i] = EvalArray(i, Rule, Test);
           }
           if (prnt == true)
           {
               PrintArray(Test);
           }
           runs ++;
       }while ((AllSame(Test) == false) & (runs < runTime));
       
       if (prnt == true)
       {
           for (int i=0; i < 5; i++)
           {
               System.out.println("^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^");
           }
           System.out.println("");
       }
       Rule.val += RecordSuccess(maj, T1);
   }
   

   public static int FindMajority(test Test, boolean prnt)
   {
       int on = 0;
       int off = 0;
       for (int i=0; i < Test.array.length; i++)
       {
           if (Test.array[i] == 0)
           {
               off++;
           }
           if (Test.array[i] == 1)
           {
               on++;
           }
       }
       if (prnt == true)
       {
           System.out.println("BLACK: " + on);
           System.out.println("WHITE: " + off);
       }
       
       if (on > off)
       {
           if (prnt == true)
           {
               System.out.println("majority: ON");
           }
           return 1;
       }
       
       else
       {
           if (prnt == true)
           {
               System.out.println("majority: OFF");
           }
           return 0;
       }
   }
   
   
/*  public static int EvalArray(int pos, rule Rule, test Test) //Takes a single position and a rule
   {
       //Evaluates the array at a single position according to the rule
       
       int x;
       int y;
       int z;
       
       if (pos == 0)
       {
           x = Test.array[Test.array.length-1];
       }
       else
       {
           x = Test.array[pos-1];
       }
       
       y = Test.array[pos];
       
       if (pos == Test.array.length - 1)
       {
           z = Test.array[0];
       }
       else
       {
           z = Test.array[pos + 1];
       }
       
       int val = (((x << 1) | y) << 1) | z;
       return Rule.array[val];
   }
*/

   public static int EvalArray(int pos, rule Rule, test Test) //Takes a single position and a rule
   {
       //Evaluates the array at a single position according to the rule
       
       int min3;
       int min2;
       int min1;
       int cntr;
       int max1;
       int max2;
       int max3;
       
       if (pos == 0)
       {
           min3 = Test.array[Test.array.length-3];
           min2 = Test.array[Test.array.length-2];
           min1 = Test.array[Test.array.length-1];
       }
       else if (pos == 1)
       {
           min3 = Test.array[Test.array.length-2];
           min2 = Test.array[Test.array.length-1];
           min1 = Test.array[pos-1];
       }
       else if (pos == 2)
       {
           min3 = Test.array[Test.array.length-1];
           min2 = Test.array[pos-2];
           min1 = Test.array[pos-1];
       }
       else
       {
           min3 = Test.array[pos-3];
           min2 = Test.array[pos-2];
           min1 = Test.array[pos-1];
       }
       
       cntr = Test.array[pos];
       
       if (pos == Test.array.length - 1)
       {
           max1 = Test.array[0];
           max2 = Test.array[1];
           max3 = Test.array[2];
       }
       else if (pos == Test.array.length - 2)
       {
           max1 = Test.array[pos + 1];
           max2 = Test.array[0];
           max3 = Test.array[1];
       }
       else if (pos == Test.array.length - 3)
       {
           max1 = Test.array[pos + 1];
           max2 = Test.array[pos + 2];
           max3 = Test.array[0];
       }
       else
       {
           max1 = Test.array[pos + 1];
           max2 = Test.array[pos + 2];
           max3 = Test.array[pos + 3];
       }
       
       int val = (((((((((((min3 << 1) | min2) << 1) | min1) << 1) | cntr) << 1) | max1) << 1) | max2) << 1) | max3;
           
   //  int val = (((x << 1) | y) << 1) | z;
       return Rule.array[val];
   }
   
/*  public static void StoreArray() //Takes a single position value and location (x and y)
   {
       //Stores the resultant position of the array in the 2D array
   }
*/
   
   public static int RecordSuccess(int maj, test T1) //Takes a rule and modified array
   {
       //Modifies the value of the rule depending upon the outcome
       if (AllSame(T1) == true)
       {
           if (maj == T1.array[0])
           {
               return 1;
           }
       }

       return 0;
   }
   
   public static boolean AllSame(test T1)
   {
       int check = T1.array[0];
       boolean result = true;
       for (int i = 0; i < T1.array.length; i++)
       {
           if (check != T1.array[i])
           {
               result = false;
           }
       }
       return result;
   }
   
   public static int ReturnSuccess(rule Rule) //Takes a rule
   {
       //Returns the success of a single rule
       return Rule.val;
   }
   
   public static rule SelectBest(rule[] RuleList)
   {
       //Chooses the best rule
       rule Best = new rule();
       Best.val = -1;
       for (int i = 0; i < RuleList.length; i++)
       {
           if (RuleList[i].val > Best.val)
           {
               Best.array = RuleList[i].array;
               Best.val = RuleList[i].val;
           }
       }
       return Best;
   }
   
   public static float FinalExam(rule Best, test[] FinalTestList)
   {
       System.out.println("_________________________");
       //Calls CreatArrays with enormous number

       //Applies best rule to giant 2D array of landscapes
       //Returns success rate

       System.out.println("FINAL TEST");
//      DisplayArrays(Best);
       Best.val = 0;
       boolean prnt = false;
       
       
       ApplyRuleToAllTests(Best, FinalTestList, prnt);
       System.out.println(Best.val + " / " + FinalTestList.length);
       float val = Best.val;
       float success = (100 * val / FinalTestList.length);
       return success;
   }
}
\end{verbatim}
\end{appendix}

\end{document}
