\documentclass[a4paper,11pt]{report} \parindent .4in % .2in or .3 in or any indent you want \pagestyle{plain} % plain gives numbering of pages \setlength{\oddsidemargin}{0in} % -.25in makes wider magrins, e.g. \setlength{\topmargin}{-25pt} % -.5in makes top margin higher \headheight 0pt \headsep 25pt \textheight 9in % Change this when changing topmargin \textwidth 6.5in % Change this when changing oddsidemargin \parskip 8pt \renewcommand{\baselinestretch}{1.1} % Change this 1.5 or whatever %\usepackage{fancyhdr} %\pagestyle{fancy} %\lhead{} \rhead{\itshape \rightmark} \cfoot{\thepage} %\pagestyle{plain} %\usepackage[dvips]{graphics} \usepackage[latin1]{inputenc} \usepackage[T1]{fontenc} \usepackage[english]{babel} \usepackage{graphicx} %\documentstyle{epsf} \title{\LARGE \textbf{BRAINBALL}} \author{\normalfont Andrea, Anne, Jerome, NiKo Nicolas Godzik - INSA de Rouen - DEA Sciences De l'Ingénieur \\ DEA project carried out at the "Centre de Mathématiques Appliquées, Ecole Polytechnique" \\ under the supervision of Marc Schoenauer } \date{June 2001} \begin{document} \maketitle \renewcommand{\sectionmark}[1]{\markright{\thesection.\ #1}} %\pagenumbering{roman} %\markright{Introduction} \tableofcontents \pagenumbering{roman} \chapter*{Introduction} \addcontentsline{toc}{chapter}{Introduction} \markright{introduction} \pagenumbering{arabic} \section{Problem definition} \subsection{The brainball puzzle} \begin{figure}[htbp] \begin{center} \includegraphics{brainball.eps} \end{center} \caption{\small The brain ball moves } \label{fig:brainball1} \end{figure} \begin{figure}[htbp] \begin{center} \includegraphics{brainball3.eps} \end{center} \caption{\small Basic Operators } \label{fig:brainball2} \end{figure} The brainball puzzle belongs to a category of combinatorial puzzle. Its moves are easily described as in figures. The basic actions are a Swap S and a Turn S and the full move of the whole puzzle. \subsection{Problem representation} Some brainteasers can be modelled with the algebraic structure of groups. The main interest in such models is to find heuristics to solve these brainteasers.\\ For the brainball puzzle we shall call position the ordered list of the 13 numbers and their colour, we note these positions $p_{a}$. The basic actions, $a_{i}$ , (defined below) act upon these positions to change them into another position. \begin{equation} a_{i}(p_{a})=p_{b} \end{equation} \\ All these actions form a group which we call the brainball group, which is an algebraic structure with three crucial properties. These properties are : \begin{itemize} \item{ there exists a neutral element: when you don't move the brainball.} \item{The stability property: When you compose two actions, the result is another action \begin{equation} a_{i}.a_{j}=a_{k} \end{equation}} \item{The existence of an inversible element : for each action there is a reversible action} \end{itemize}. Here is an other useful example of group called the symetric group. \\ It is interesting when one has a group structure, to try to identify it with a known group or to embed it in an other one. This way we find properties of its structure and of its decomposition. The group structure we consider in this work is groups, which are subgroup products of $S_{n}$ where $n$ is an integer. For the brainball example, there are two ways to identify the group. First we can simply identify the $26$ numbers with an alphabet letter without taking in account the fact that there is a link between each number and the same number in the other colour. So, the brainball group is a subgroup of $S_{26}$, each action scrambles the $26$ numbers. The other way is to say there is one number on the first side with one colour, and the same stick on the other side with the complementary colour. This leads to embed the brainball group in $S_{13}\times(S_{2})^{13}$. \section{ Methodology: The 3 steps} \subsection{Use a fair representation} The representation is a subgroup of a product of symmetric groups. The representation should be faithful, typically as mentioned above G_{26} is not a very good representation for the brain ball Whereas S_{13}x{S_{2}}-13 is. \subsection{Produce a good set of operators} An operator is defined as an order succession of basic actions. So an operator goes from one position to another, and may be seen as a kind of macro-action. A set of operators is good if it helps to solve the problem. To avoid software development's costs, one should try to produce this set in a way independent of the brain teaser to solve. \subsection{Apply Evolution Strategy} When the evolution strategy is finally applied, an individual is a position. In order to produce an offspring one picks up an element from one's set of operators and applies it to the parent(position) to produce offspring giving some other position. \section{ Producing a good set of operators } \subsubsection{ The need of automation} Producing a good set of operators can be costly if done by hand. Typically for the Rubik's cube, one would take any book of how to solve it and pickup some nice operator such as the exchange of two corners without disturbing the rest. Then one would input the definition in one's software. Doing this for every new puzzle would be costly. \subsubsection{ Conjugation and commutator } A commutator is an operator of the form : K= $ABA^{-1}B^{-1}$ where A and B are any basic action or any operator.\\ It is noted K=$[A,B]$ A conjugation is an operator of the form : K=$ABA^{-1}$ where A and B are any basic action or any operator.\\ It is noted K=$A(B)= ABA^{-1}$ A simple example of conjugation in real life is : 1) Open the door 2) Switch the light on 3) close the door. Though apparently simple this process might require some forethought for a young child. In the same way using conjugation on a puzzle is difficult for an adult. \subsubsection{ Telling a good operator} The only generic criteria we know for designing a good operator is:\\ CRIT0: Maximize the number of fixed points.\\ In the extreme an operator moves no pieces except two ,so it performs a simple exchange. The group G_{n} is generated by simple exchanges, moreover the algorithm to recover from a substitution using only simple exchanges is easy to understand to see to and implement. This provides some motivation for the rule, though not a very strong one. \subsubsection{ Achieving a set good operators} \subsubsubsection{ Rules for conception} The building rules are simple easy to implement and do not depend on the brainteaser at hand.\\ \begin{itemize} \item 1: Use conguation\\ \item 2: Use commutation\\ \item 3: Combine R1 an R2 (for example commutator of two congates)\\ \item 4: Use power of any element produced by above rules or action.\\ \end{itemize} \subsubsubsection{ Heuristics of rules} Commutation is justified as they are typical algebra techniques used to divide groups.\\ The combine rule has also motivation in a deep theorem[REF.] which says that iterating the process of commutation leads to identity for a many finite groups (Finite simple groups are soluble). Though we probably don't know that our group is simple, experts in brain teasers tells us that iterated commutation leads to a lot of fixed points[REF. jerome ?]. The motivation for rule 4 is : powering any element lead to identity, and may only increase the number of fixed points. \subsubsection{ Building your set of operators } A typical description for generating operators would be:\\ FORGEN $=\{ S^{i} , T^{i} , [S,T^(j)] , [(ST)^{i}] \}$ Instantiating the above description may produce thousands of operators, from which you will retain those that maximize fixed points rule. \section{Fitness - How to get a good fitness function} The original fitness function for the brainball problem was a sum of the fitness function for the numbers problem and the colors problem. For the numbers problem it was calculated as follows:\\ \begin{equation} \label{eqn:FitMNumbProb} F1_{N} = \sum_{N} F_{N-1} + abs(actualValue_{N} - targetValue_{N}) \end{equation} For the colors problem it was calculated as follows:\\ \begin{equation} \label{eqn:FitMColorProb} F2_{N} = \sum_{N} F_{N-1} + 1 \end{equation} The total fitness is given as: $F1_{N} + F2_{N}$. The numbers problem is harder than the colors problem. For this reason the penalty for an incorrect number is weighted more than an incorrect color. However, this is not enough when applied to a hard instance for the target in the brainball problem. In order to get a better fitness function this is incorporated into the original fitness function. Two different ways were tested. \subsection{Normalization} In relation to the numbers problem the equation \ref{eqn:FitMNumbProb} needed to be up-dated with the \alpha parameter (the factor in the $F1_{N}$). However, it needs to be carefully adjusted. The new fitness function is given as follow: \begin{equation} \label{eqn:FirstNewFit} F'1_{N} = \sum_{N} F_{N-1} + \alpha(abs(actualValue_{N} - targetValue_{N})) \end{equation} This means that the total fitness function can be calculated as: $F'1_{N} + F2_{N}$. The brainball problem was tested for $\alpha = 1, 2, 3, 4 and 5$ and when $\alpha = 1$ it represents the original fitness function exactly. The power of this normalization can be seen in the results section, and to establish how powerful it is, some results are presented for the numbers problem alone (without to consider colors one). \subsection{Adding constant values} The second method is to add constant values for the penalty for each wrong number chosen in the numbers problem. In this case the $F1_{N}$ is given as follows: \begin{equation} \label{eqn:SecondNewFit} F"1_{N} = \sum_{N} F_{N-1} + C \end{equation} The brainball problem now was tested for $\C = 13, 16 and 26$ where in the case of $\C = 13$ represent total numbers that can be chosen. \section{Results} The tests were done for 15 runs for each instance of brainball problem since that one instance was the original target and the other it was change \section{Conclusion} Though a problem about a toy, the brain ball is not a toy problem, it is a hard problem. Also it a very good media because customer relates strongly to this well known puzzle such as the Rubik's cube. Again we have illustrated the idea that the fitness function is the only time on the real world, by taking into account the structure of the given problem.