\chapter{From Theory to Practice}

Four main parts make up the whole system: the actual genetic algorithm,
a parser, a lexical database, and a corpus of natural input sentences.
One additional part can be used, namely a brute force search algorithm,
to finish up the search for the optimal solution.

\section{Implementing the GA}

Implementing a simple genetic algorithm is very straightforward. As
described in section 2.2, the first step is to devise a way to encode
relevant information into individuals. Then, a fitness function or test
is made to determine the fitness of these individuals. To move from
generation to generation, the process of reproduction, mating, and
mutation is carried out. The choice of the starting generation is mainly
arbitrary, but there are some issues to consider. 

\subsection{Individuals}

Individuals which comprise the population in this genetic algorithm are
a set of numbers which indicate the order of each binary phrase in the
grammar. (See figure 2-3 for the template grammar.) ``0'' means that the
order the right-hand side of a phrase is the same as in the template
grammar, ``1'' means that it is the opposite of the order in the
template grammar, and ``2'' means that the order is free. Since there
are 14 phrases in the grammar being used, and thus 14 parameters, an
individual consists of 14 numbers from 0 to 2, i.e. the settings of each
parameter. Each of these numbers can be thought of as a gene which
specifies a certain trait, where a trait is just the order of a certain
phrase. The order of the numbers follows the order of the phrases in the
template grammar, i.e. the first number indicates the order of the first
phrase in the template.

\subsection{Fitness}

To determine the fitness of individuals, the genes, i.e. parameter
settings, in an individual are used to create the corresponding grammar
which the parameter settings specify. This grammar is then given to the
parser along with each of the sentences in the corpus of English
sentences. A count is kept of how many of these sentences an
individual's grammar can successfully parse.  The fitness of an
individual is the percentage of the sentences from the corpus that its
grammar parsed successfully.

\subsection{Reproduction}

The gene pool for the next generation is created by determining the
fitness of every individual in the current generation. All of these
fitnesses are summed together to represent the total fitness of the
generation. For each individual, the number of replicas to be placed in
the gene pool is the fraction of the total fitness the individual
represents times the total number of individuals in a generation,
rounded to the nearest integer.

Occasionally, due to rounding errors, the above algorithm for creating
the gene pool results in either too few or too many individuals for the
next generation. Thus individuals are removed from or added to the gene
pool at random to produce a gene pool with the right number of
individuals.

\subsection{Mating}

Once the gene pool for the generation is ready, mating is done randomly
among individuals in the gene pool. In the algorithm I use, mating
consists only of cross-over. An even random number of individuals are
paired up randomly and a locus for each of these pairs is chosen at
random.  The locus is a number between 0 and 13 which indicates at which
location to split the two individuals. Two new individuals are created
in a splitting and recombining process where each has the first part of
one of the original individuals and the last part of the other
individual (see figure 3-1). In this way, the genes in the gene pool are
mixed around to create new combinations of genes.

\begin{figure}
\center{\leavevmode{\epsfbox{cross-over.ps}}}
\caption{The cross-over of two individuals creates two new individuals,
each of which have traits from both parents.}
\end{figure}

\subsection{Mutation}

Every so often, mutation can occur. Mutation involves the changing of
one gene in one individual. Although this seems like a very minor change
in a large population of individuals, it can make a difference if it
introduces a substantially beneficial trait. The choices of individuals
and genes for mutation are random. The new value for a gene targeted for
mutation is randomly chosen to be one of the two values which the gene
currently does not have. It is best to keep the mutation rate low so
that good combinations of genes are not destroyed randomly by mutation.
In my implementation, the mutation rate can have different values for
different simulations. The mutation rate is a number indicating how many
generation there are between each single mutation.

\subsection{The Zeroth Generation}

For the starting generation, the choice of individuals is random. That
is, individuals are created by randomly choosing each of the 14 genes.
The one restriction on this randomness is that the value ``2'', or free
order, is never given to a gene. Free order phrases are assumed to be
rare, although they do occur frequently in certain languages. The
presence of free order phrases slows down the parsing of sentences and
creates overgeneralized parameter settings. Thus, all of the individuals
in the zeroth generation have genes with only the values of ``0'' or
``1''.  However, mutation can still change a gene to have the value of
``2''. With each mutation on an individual from the zeroth generation,
there is a 50\% chance that a ``2'' gene will be introduced into an
individual since individuals from the zeroth generation only have ``0''s
and ``1''s and the new value has a 50\% chance of being a ``2''. 

\section{The Parser}

The parser that I have written for my thesis takes a grammar, which kind
of phrase to parse, and an input sentence. It is a recursive
descent parser\footnote{A recursive descent parser is one which expands each
phrase it encounters and recursively calls itself to try to parse each
expanded phrase.} and returns true if it was able to successfully
parse the input, otherwise it returns false.

The way the parser works is simple. It tries to match each word in the
input to each terminal (such as Noun, Verb, etc) specified by the
grammar.  The parser determines the part of speech of a word by looking
it up in the lexical database. It knows how to handle optional
components of phrases, so if a terminal (or even a phrase) is optional
and there is no matching word in the input it will ignore the optional
terminal (or phrase). It also handles free-order phrases by trying both
orders of a phrase before returning false or moving on to the next
phrase, if the free-order phrase is optional. When trying to a match a
word in the input to the next possible terminal in the grammar, the
parser will expand the next entry in the grammar if it is not a
terminal. In order to avoid entering an infinite loop when parsing
potentially recursive phrases such as a noun phrase, the parser keeps
track of whether it is currently parsing an optional complement phrase
(CP) or prepositional phrase (PP).  If it is, it will not try to parse
another such phrase which is optional.  This rules out noun phrases such
as ``the dog in the house on the corner'', but without such a addition
to the parser it would hang infinitely trying to expand the noun phrase
in the prepositional phrase in the noun phrase, etc. Fully recursive
phrases such as adjective phrases are not allowed to be recursive at
all, and so phrases with two adjectives like ``big blue block'' are not
allowed since such a phrase would involve a recursive expansion of the
adjective phrase. Thus, although the parser is not completely capable of
parsing recursive phrases, it suffices for the simple grammars and
simple sentences that are used in my thesis.

\section{The Input}

The corpus of input sentences which is used as part of the fitness test
for individuals is taken from the Childes database of natural
child-parent interactions. In the Input appendix, the specific sources
of sentences are listed. Only the parents' utterances are used. The idea
behind using natural utterances directed to children is to show that the
genetic algorithm can acquire the parameter settings given the same
input as children\footnote{However, three sentences which do not appear
in the database are used, although they are modelled somewhat after the
sentences used from the database. These ``unnatural'' sentences are used
to provide more variety than could be easily found in the database. For
example, sentences which have noun phrase with its optional complement
phrase in the subject position are not easy to find.}. However, given
any good variety of sentences, not necessarily ``natural'' sentences,
the genetic algorithm should be able to set the parameters.

\section{The Lexical Database}

Once the corpus of input sentences was chosen, a lexical database
including all of the words used in the sentences was constructed. The
words were hand-tagged with parts of speech and placed into a binary
tree. The parser uses this lexical database to find the parts of speech
of the words in the input it is given.

\section{Overcoming Randomness}

One problem with genetic algorithms is that there is a certain amount of
randomness. This randomness can cause the GA to perform a ``random
walk'' around the optimal solution once it has found a near-optimal
solution (see figure 3-2). It can sometimes take a long time before the
GA randomly stumbles on the remaining parameter settings for the optimal
solution.  Thus, in order to avoid this random walk, a brute force
search method can be used once the fittest individual in a generation
exceeds a certain fitness threshold. This brute force method simply
takes the fittest individual and changes each parameter setting. Any
changes that improve the fitness of the individual are kept. In this
way, an optimal solution is found.

\begin{figure}
\begin{verbatim}
> (evolve 50 1 100)
Generation 1: Best=(0 1 1 0 0 1 1 1 0 0 1 1 0 0), 86% fit
Generation 2: Best=(0 1 1 0 0 1 1 1 0 0 1 1 0 0), 86% fit
Generation 3: Best=(0 1 1 0 0 0 1 1 0 0 0 0 0 0), 88% fit
Generation 4: Best=(0 1 1 0 0 0 1 1 0 0 1 1 0 0), 91% fit
Generation 5: Best=(0 1 1 0 0 0 0 1 0 0 1 1 0 0), 95% fit
...
Generation 43: Best=(0 1 1 0 0 0 0 1 0 0 1 1 0 0), 95% fit
Generation 44: Best=(0 1 1 0 0 0 0 1 0 0 2 2 0 0), 95% fit
Generation 45: Best=(0 1 1 0 0 0 0 1 0 0 2 2 0 0), 95% fit
Generation 46: Best=(0 1 1 0 0 0 0 1 0 0 2 2 0 0), 95% fit
Generation 47: Best=(0 1 1 0 0 0 0 1 0 0 2 2 0 0), 95% fit
Generation 48: Best=(0 1 1 0 0 0 0 1 0 0 2 2 0 0), 95% fit
Generation 49: Best=(0 1 1 0 0 0 0 1 0 0 2 2 0 0), 95% fit
Generation 50: Best=(0 1 1 0 0 0 0 1 0 0 2 2 0 0), 95% fit
(0.9464285714285714 (0 1 1 0 0 0 0 1 0 0 2 2 0 0))
\end{verbatim}
\caption{An example run in which the genetic algorithm performs a random
walk around an optimal solution, namely {\tt (0 1 1 0 0 0 2 1 0 0 1 1 0
0)}. In this example, brute force search could have been used once it
reached 95\% fitness.}
\end{figure}

\section{{\tt evolve}}

The main procedure for the genetic algorithm I wrote is called {\tt
evolve}. It takes five arguments, two of which are optional. The first
arguments is the number of generations to run the GA. If a solution has
not been found by the time this number of generations have been run, the
procedure will return the best individual and its fitness from the last
generation run. The second argument is the mutation rate, representing
the number of generations between mutations. The third is the generation
size, that is, the number of individuals in each generation. The fourth
argument is optional and indicates the fitness threshold above which to
run the brute force search on the best individual. If it not specified,
it defaults to {\tt nil} and brute force search will never be used. The
fifth argument is also optional. It provides the option of prohibiting
free order phrases, by specifying the number of gene values that are
allowed. The default number is 3, meaning that a gene can have ``0'',
``1'', or ``2'' as a value. If this argument is set to 2, the corpus of
input should reflect the fact that there are no free order phrases
allowed. In English, this means that all adverbial phrases must appear
on one side of the verb or the other.

See Appendix C for some results of running {\tt evolve}.
