<commit_before>#+TITLE:     Project #1 Genetic Algorithm
#+AUTHOR:    <NAME>
#+EMAIL:     <EMAIL>
#+OPTIONS:   H:3 num:t toc:nil \n:nil @:t ::t |:t ^:t -:t f:t *:t <:t
#+OPTIONS:   TeX:t LaTeX:t skip:nil d:nil todo:t pri:nil tags:not-in-toc
#+INFOJS_OPT: view:nil toc:nil ltoc:t mouse:underline buttons:0 path:http://orgmode.org/org-info.js
#+EXPORT_SELECT_TAGS: export
#+EXPORT_EXCLUDE_TAGS: noexport

#+BEGIN_abstract
For Project #1 I implemented a Genetic Algorithm in C++ to solve the
Ackley, Griewangk, Rastrigin, Rosenbrock, Schwefel, and Spherical test
functions. With the =random= library from C++11, random number
generation is so efficient that, for certain problems, the fitness
evaluation is actually the bottleneck in the program (specifically
problems which use trigonometric functions). Through testing I found
that the best setup for the GA used a generational population,
tournament selection, two-point crossover, and a "jumping" mutation
sequence. The initial population of 512 members is randomly generated
with valid solutions. To produce the replacement generation, first
parents are selected. To do this a tournament among 4 randomly
selected members is held, with the most fit member being chosen as a
parent. For every two parents, a binary two-point crossover is done to
produce two children.  For each child, the jumping mutation sequence
performs, with a 2.5 percent chance per gene, a mutation of that gene
to some random value in the problem's domain. Finally, 2 random
offspring are replaced with the best member from the last
generation. This GA finds an adequate solution to every problem except
the Rosenbrock function (for which it stills fares well) in under a
second.

This code is available at:

https://github.com/andschwa/uidaho-cs472-project1
#+END_abstract

* Build :noexport:
Makes use of autotools. Necessary files:
- configure.ac (with help from autoscan)
- Makefile.am
- m4/* for C++11 and Boost macros

To configure and build:
#+begin_src sh
autoreconf -vfi
./configure && make
#+end_src

* Assignment :noexport:
   DEADLINE: <2014-02-21 Fri>
The goal of this project is to write a genetic algorithm (GA) for a
series of benchmark optimization problems. In each case the problem is
to optimize, i.e. find the (global) minimum, of a real valued
function.

To test the GA we'll use 6 standard, benchmark, real-valued functions:

1. Spherical
2. Rosenbrock
3. Rastrigin
4. Schwefel
5. Ackley
6. Griewangk

Each of these functions is defined at [[http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume24/ortizboyer05a-html/node6.html#tabla:DefFunc][here]]. (Note the first function
labeled as Schwefel on this page is actually the double sum, which we
are not using. We are using the Schwefel function defined immediately
after the Rastrigin function.)

Pay careful attention to the ranges of the functions. You will want to
use those ranges both in creating initial individuals and in
controlling the generation of neighbors, e.g. you don't want your GA
'wandering' out of the search space. Note that here the functions are
all defined with 30 dimensions, e.g. P = 30 in the function
definitions.

** Task
Write a GA to find the input values (x_{1}, ... ,x_{30}) that minimizes each
of the six benchmark problems.

You need to pick the details of the GA, including:
- Representation
- Fitness function
- Algorithm type: Steady state or generational
- Crossover type: 1-point, 2-point, uniform, arithmetic, etc.
- Mutation rate
- etc.

** Write-up
You must write a short paper describing the results of your project
that includes the following sections:

- Abstract - a short (~200 words) summary of what you did and what the
  results were.
- Algorithm descriptions - clear, complete descriptions of your GA. Be
  careful to include all of the details someone would need to
  replicate your work.
- Examples of necessary details include (there are others):
  - How fitness is measured
  - Exactly how initial random solutions are generated
  - Mutation rates
  - etc.
- Basically every time you make a decision about how the algorithm
  works (what type of crossover it will use, how mutation is
  performed, etc.) you should make a note of it.
- Results - you should include graphs and/or tables to make it easy to
  understand the results. Make sure that the graphs and table are
  clearly labeled.
- Conclusions - based on your results draw some specific conclusions
  about how well the algorithm performed.

* Notes :noexport:
** Functions
*** Ackley
- f_{Ack}(x) = 20 + e - 20exp(-0.2\radic((1/p)(\sum_{i=1})^{p}(x_{i})^{2})) - exp((1/p)(\sum_{i=1})^{p}cos(2(\pi)x_{i}))
- x_{i} \in [-30, 30]
- x^{\*} = (0, 0, ..., 0); f_{Ack}(x^{\*}) = 0

*** Griewangk
- f_{Gri}(x) = 1 + (\sum_{i=1})^{p}(x_{i})^{2}/4000 - (\prod_{i=1})^{p}cos(x_{i}/\radic(i))
- x_{i} \in [-600, 600]
- x^{\*} = (0, 0, ..., 0); f_{Gri}(x^{\*}) = 0

*** Rastrigin
- f_{Ras}(x) = 10p + (\sum_{i=1})^{p} ((x_{i})^{2} - 10cos(2(\pi)x_{i}))
- x_{i} \in [-5.12, 5.12]
- x^{\*} = (0, 0, ..., 0); f_{Ras}(x^{\*}) = 0

*** Rosenbrock
- f_{Ros}(x) = (\sum_{i=1})^{p-1}[100(x_{i+1} - (x_{i})^{2})^{2} + (x_{i} - 1)^{2}]
- x_{i} \in [-2.048, 2.048]
- x^{\*} = (1, 1, ..., 1); f_{Ros}(x^{\*}) = 0

*** Schwefel
f_{Sch}(x) = 418.9829 \cdot p + (\sum_{i=1})^{p} x_{i }sin(\radic|x_{i}|)
x_{i} \in [-512.03, 511.97]
x^{\*} = (-420.9687, ..., -420.9687); f_{Sch}(x^{\*}) = 0

Use more random restarts, fewer neighbors

*** Spherical
- f_{Sph}(x) = (\sum_{i=1})^{p} (x_{i})^{2}
- x_{i} \in [-5.12, 5.12]
- x^{\*} = (0, 0, ..., 0); f_{Sph}(x^{\*}) = 0

Use fewer random restarts, more neighbors

* Implementation

** Structure

The main component of this program is the =Genetic= class derived from
the =Algorithm= base class; this structure allows me to swap in the
prior algorithms with ease (the =HillClimber= and =SimulatedAnnealing=
classes). When instaniated, this class requires a =Problem= object,
which is a base class representing the interface to the various test
functions we were given. Potential solutions to a problem are
represented by an =Individual= class.

** Individual

The =Individual= class's primary data structure is a C++11 array
container, a template similar to a vector, but more efficient and
requiring a size (the given dimension of thirty). Thus its genome
(potential solution) is an array of thirty parameter types, where
parameter is a =typedef= for =double= ("parameter" could honestly be
"chromosome", except that it is used elsewhere not as a chromosome but
where it should still share the type). It additionally has a =fitness=
parameter, set when created by the =Problem= class, and updated when
mutated by the =Algorithm= class. The =Individual= class has a
=mutate(gene, gene_i)= function whose purpose is to bound-check a
mutation operation on any single given gene, and clip it to the
domain's minimum and maximum value as needed. Through the use of
templated operator overloads and =begin()= and =end()= member
functions, an =Individual= object can be treated like an iterator (of
its genome =array=), compared by fitness such that a greater fitness
is defined by its minimization flag (that is, =if(minimize)= then zero
is greater than positive (worse) fitnesses), and arithmetically added
by fitness. This makes the implementation of the algorithms very
clean.

** Problem

The =Problem= class holds the following data: the interval of the
domain, the interval of the range (used for normalization), a
minimization flag (that is, whether or not the goal is to minimize the
problem's value), the goal itself, and the maximum number of
iterations/generations the algorithm should run for that problem. The
=Problem= class provides several member functions:
=fitness(Individual)= which is a =virtual= function implemented by the
derived classes and calculates the fitness score using the definition
of the problem's function, =potential()= which returns an =Individual=
object instaniated with the data it needs (the domain interval,
minimization flag, random potential solution generated by using a
=uniform_real_distribution= object, and fitness value for that
potential solution), =normal(Individual)= which normalizes an
=Individual= object's fitness score onto the interval $[0, 1]$ using
the problem's range (where 1 is the maximum fitness, with minimization
taken into account), =worst()= which finds the worst fitness using an
in-place search across =iterations= number of random potential
solutions (used to find an adequate range), and finally =represent()=
which returns a friendly string representation of the problem,
including its name and other parameters.

We were asked to implement the following problems defined at:

https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume24/ortizboyer05a-html/node6.html

The source of the fitness functions is included here:

*** Ackley

- Domain: =[-30, 30]=
- Approximate range: =[0, 22]=

#+begin_src c++
parameter Ackley::fitness(const Individual & subject) const {
  parameter p_inverse = 1. / subject.size();<commit_msg>Quick fix in readme<commit_after>#+TITLE:     Project #1 Genetic Algorithm
#+AUTHOR:    <NAME>
#+EMAIL:     <EMAIL>
#+OPTIONS:   H:3 num:t toc:nil \n:nil @:t ::t |:t ^:t -:t f:t *:t <:t
#+OPTIONS:   TeX:t LaTeX:t skip:nil d:nil todo:t pri:nil tags:not-in-toc
#+INFOJS_OPT: view:nil toc:nil ltoc:t mouse:underline buttons:0 path:http://orgmode.org/org-info.js
#+EXPORT_SELECT_TAGS: export
#+EXPORT_EXCLUDE_TAGS: noexport

#+BEGIN_abstract
For Project #1 I implemented a Genetic Algorithm in C++ to solve the
Ackley, Griewangk, Rastrigin, Rosenbrock, Schwefel, and Spherical test
functions. With the =random= library from C++11, random number
generation is so efficient that, for certain problems, the fitness
evaluation is actually the bottleneck in the program (specifically
problems which use trigonometric functions). Through testing I found
that the best setup for the GA used a generational population,
tournament selection, two-point crossover, and a "jumping" mutation
sequence. The initial population of 512 members is randomly generated
with valid solutions. To produce the replacement generation, first
parents are selected. To do this a tournament among 4 randomly
selected members is held, with the most fit member being chosen as a
parent. For every two parents, a binary two-point crossover is done to
produce two children.  For each child, the jumping mutation sequence
performs, with a 2.5 percent chance per gene, a mutation of that gene
to some random value in the problem's domain. Finally, 2 random
offspring are replaced with the best member from the last
generation. This GA finds an adequate solution to every problem except
the Rosenbrock function (for which it stills fares well) in under a
second.

This code is available at:

https://github.com/andschwa/uidaho-cs472-project1
#+END_abstract

* Build :noexport:
Makes use of autotools. Necessary files:
- configure.ac (with help from autoscan)
- Makefile.am
- m4/* for C++11 and Boost macros

To configure and build:
#+begin_src sh
autoreconf -vfi
./configure && make
#+end_src

* Assignment :noexport:
   DEADLINE: <2014-02-21 Fri>
The goal of this project is to write a genetic algorithm (GA) for a
series of benchmark optimization problems. In each case the problem is
to optimize, i.e. find the (global) minimum, of a real valued
function.

To test the GA we'll use 6 standard, benchmark, real-valued functions:

1. Spherical
2. Rosenbrock
3. Rastrigin
4. Schwefel
5. Ackley
6. Griewangk

Each of these functions is defined at [[http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume24/ortizboyer05a-html/node6.html#tabla:DefFunc][here]]. (Note the first function
labeled as Schwefel on this page is actually the double sum, which we
are not using. We are using the Schwefel function defined immediately
after the Rastrigin function.)

Pay careful attention to the ranges of the functions. You will want to
use those ranges both in creating initial individuals and in
controlling the generation of neighbors, e.g. you don't want your GA
'wandering' out of the search space. Note that here the functions are
all defined with 30 dimensions, e.g. P = 30 in the function
definitions.

** Task
Write a GA to find the input values (x_{1}, ... ,x_{30}) that minimizes each
of the six benchmark problems.

You need to pick the details of the GA, including:
- Representation
- Fitness function
- Algorithm type: Steady state or generational
- Crossover type: 1-point, 2-point, uniform, arithmetic, etc.
- Mutation rate
- etc.

** Write-up
You must write a short paper describing the results of your project
that includes the following sections:

- Abstract - a short (~200 words) summary of what you did and what the
  results were.
- Algorithm descriptions - clear, complete descriptions of your GA. Be
  careful to include all of the details someone would need to
  replicate your work.
- Examples of necessary details include (there are others):
  - How fitness is measured
  - Exactly how initial random solutions are generated
  - Mutation rates
  - etc.
- Basically every time you make a decision about how the algorithm
  works (what type of crossover it will use, how mutation is
  performed, etc.) you should make a note of it.
- Results - you should include graphs and/or tables to make it easy to
  understand the results. Make sure that the graphs and table are
  clearly labeled.
- Conclusions - based on your results draw some specific conclusions
  about how well the algorithm performed.

* Notes :noexport:
** Functions
*** Ackley
- f_{Ack}(x) = 20 + e - 20exp(-0.2\radic((1/p)(\sum_{i=1})^{p}(x_{i})^{2})) - exp((1/p)(\sum_{i=1})^{p}cos(2(\pi)x_{i}))
- x_{i} \in [-30, 30]
- x^{\*} = (0, 0, ..., 0); f_{Ack}(x^{\*}) = 0

*** Griewangk
- f_{Gri}(x) = 1 + (\sum_{i=1})^{p}(x_{i})^{2}/4000 - (\prod_{i=1})^{p}cos(x_{i}/\radic(i))
- x_{i} \in [-600, 600]
- x^{\*} = (0, 0, ..., 0); f_{Gri}(x^{\*}) = 0

*** Rastrigin
- f_{Ras}(x) = 10p + (\sum_{i=1})^{p} ((x_{i})^{2} - 10cos(2(\pi)x_{i}))
- x_{i} \in [-5.12, 5.12]
- x^{\*} = (0, 0, ..., 0); f_{Ras}(x^{\*}) = 0

*** Rosenbrock
- f_{Ros}(x) = (\sum_{i=1})^{p-1}[100(x_{i+1} - (x_{i})^{2})^{2} + (x_{i} - 1)^{2}]
- x_{i} \in [-2.048, 2.048]
- x^{\*} = (1, 1, ..., 1); f_{Ros}(x^{\*}) = 0

*** Schwefel
f_{Sch}(x) = 418.9829 \cdot p + (\sum_{i=1})^{p} x_{i }sin(\radic|x_{i}|)
x_{i} \in [-512.03, 511.97]
x^{\*} = (-420.9687, ..., -420.9687); f_{Sch}(x^{\*}) = 0

Use more random restarts, fewer neighbors

*** Spherical
- f_{Sph}(x) = (\sum_{i=1})^{p} (x_{i})^{2}
- x_{i} \in [-5.12, 5.12]
- x^{\*} = (0, 0, ..., 0); f_{Sph}(x^{\*}) = 0

Use fewer random restarts, more neighbors

* Implementation

** Structure

The main component of this program is the =Genetic= class derived from
the =Algorithm= base class; this structure allows me to swap in the
prior algorithms with ease (the =HillClimber= and =SimulatedAnnealing=
classes). When instaniated, this class requires a =Problem= object,
which is a base class representing the interface to the various test
functions we were given. Potential solutions to a problem are
represented by an =Individual= class.

** Individual

The =Individual= class's primary data structure is a C++11 array
container, a template similar to a vector, but more efficient and
requiring a size (the given dimension of thirty). Thus its genome
(potential solution) is an array of thirty parameter types, where
parameter is a =typedef= for =double= ("parameter" could honestly be
"chromosome", except that it is used elsewhere not as a chromosome but
where it should still share the type). It additionally has a =fitness=
parameter, set when created by the =Problem= class, and updated when
mutated by the =Algorithm= class. The =Individual= class has a
=mutate(gene, gene_i)= function whose purpose is to bound-check a
mutation operation on any single given gene, and clip it to the
domain's minimum and maximum value as needed. Through the use of
templated operator overloads and =begin()= and =end()= member
functions, an =Individual= object can be treated like an iterator (of
its genome =array=), compared by fitness such that a greater fitness
is defined by its minimization flag (that is, =if(minimize)= then zero
is greater than positive (worse) fitnesses), and arithmetically added
by fitness. This makes the implementation of the algorithms very
clean.

** Problem

The =Problem= class holds the following data: the interval of the
domain, the interval of the range (used for normalization), a
minimization flag (that is, whether or not the goal is to minimize the
problem's value), the goal itself, and the maximum number of
iterations/generations the algorithm should run for that problem. The
=Problem= class provides several member functions:
=fitness(Individual)= which is a =virtual= function implemented by the
derived classes and calculates the fitness score using the definition
of the problem's function, =potential()= which returns an =Individual=
object instaniated with the data it needs (the domain interval,
minimization flag, random potential solution generated by using a
=uniform_real_distribution= object, and fitness value for that
potential solution), =normal(Individual)= which normalizes an
=Individual= object's fitness score onto the interval =[0, 1]= using
the problem's range (where 1 is the maximum fitness, with minimization
taken into account), =worst()= which finds the worst fitness using an
in-place search across =iterations= number of random potential
solutions (used to find an adequate range), and finally =represent()=
which returns a friendly string representation of the problem,
including its name and other parameters.

We were asked to implement the following problems defined at:

https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume24/ortizboyer05a-html/node6.html

The source of the fitness functions is included here:

*** Ackley

- Domain: =[-30, 30]=
- Approximate range: =[0, 22]=

#+begin_src c++
parameter Ackley::fitness(const Individual & subject) const {
  parameter p_inverse = 1. / subject.size();
{'fraction_non_alphanumeric': 0.10939924628685435, 'fraction_numerical': 0.02128131234759477, 'mean_word_length': 4.425435959110042, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 9, 'https://': 4, 'lorem ipsum': 0, 'www.': 4, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7092109', 'n_tokens_mistral': 5820, 'n_tokens_neox': 5313, 'n_words': 2470}