Math 378 Small
Projects Page

Format for writing up projects.

This project requires three files:

• GBSE.cpp
• Random378.h
• Random378.cpp

g++ -lm -O3 -o evolve.exe GBSE.cpp Random378.cpp

Which creates evolve.exe. In its current for this code produces output that looks like this:

0.01  417.376  6.52233
0.02  350.076  5.19813
0.03  332.649  5.02359
0.04  330.435  5.10764
0.05  333.509  5.30713
0.06  345.107  5.73019
0.07  351.79   6.08572
0.08  372.599  6.33311
0.09  399.346  7.35021
0.1   426.721  8.09928
0.11  462.4    9.32055
0.12  492.945 10.6268
0.13  550.984 11.8843
0.14  591.358 13.8628
0.15  645.663 15.1924
0.16  717.709 17.9274
0.17  813.593 21.943
0.18  907.325 25.6104
0.19 1039.86  30.8957
0.2  1158.49  35.1688

The code is the G(eneric) B(inary) S(tring) E(volver). The GBSE is contained in the routine TimeToSolution which takes a boatload of parameters and returns the mean and standard deviation of time to solution. The main program is currently configured to evolve a binary string with probabilistic mutation and two point crossover using size four tournament selection. It reports the mutation rate, mean time to solution, and the +/- factor for a 95% confidence interval. Here are the about numbers plotted with gnuplot:

What to turn in.

This project requires four files:

• SawSHC.cpp
• walk1.cpp
• Random378.h
• Random378.cpp

They are set for the 4x4 SAW problem from Chapter 2.

Compile them to make a hill climber and an evolutionary algorithm as follows:

g++ -lm -O3 -o HillClimb.exe SawSHC.cpp Random378.cpp
g++ -lm -O3 -o Evolve.exe walk1.cpp Random378.cpp

The hill climber is a stochastic hillclimber. It starts with a random gene for the SAW problem. It then generates a mutation of that gene and keeps it if it is no worse 10,000 times. It performs this sampling procedure 1000 times and then reports the fitnesses it finds. The output of the hill climber looks like this:

0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 0
11 0
12 6
13 58
14 292
15 571
16 73

 #define Mutations 1 

Onve you've done this also run the evolutionary algorithm with 1,2,3, and 4 mutations. The evolutionary algorithm will output a file (times.dat) that says how many generations the code took to find an answer or will report 1000 as the time if no answer was found. It also creates a file, best.wlk, with the walks found in it. It has the gene and an ASCII graphic of the walk:

RDRURDDDLULDLUU
APON
BCLM
EDKJ
FGHI

What to turn in.

Give histograms of the solutions found by the hill climber and the probability of failure for the evolutionary algorithm for each of the numbers of point mutations. Do the two techniques agree on the "best" nunber of mutations? Which technique is more efficient for finding an optimal walk, the hill climber of the evolutionary algorithm? Be sure to support your conclusions. Also: is the evolutionary algororithm more likely to find some solutions that others? How can you tell?

This project requires five files:

• evosun.cpp
• sunburn.h
• sunburn.cpp
• Random378.h
• Random378.cpp

The compile line (at least on my Linux box) is:

g++ -lm -O3 -o evolve.exe evosun.cpp sunburn.cpp Random378.cpp

TME: 38867 S13.485 D7.685 G5.13 L0.965 M1.725 r2+/-3.49571 dr7.14417%

What to turn in.

You should look at the system useage plots you get and explain them in terms of the dynamics of evolution. In addition to the normal writeup, evolve or design a single ship and turn in the gene (by e-mail) in the following format:

Your Name Here
GMMSMMSMSSMSMSMSLMMD14

Sunburn Tournament Code

The tournament software requires six files:

• tournament.cpp
• sunburn.h
• sunburn.cpp
• Random378.h
• Random378.cpp
• tentry.txt

Compile:

g++ -o tourney.exe tournament.cpp sunburn.cpp Random378.cpp

The file tentry.txt needs to be in the same directory with the tournament software. The software runs 100 round-robin tournaments and reports the total number of victories. An example output is given below. REMEMBER: what is good depends on what else is submitted.

Victories      Contestant           Gene
2045                   MJH : SSSSSSSDGGGGGGGGGGGD1
2026                    DD : SSSSSSSGGGGGGGGGGGDD1
1880                   AJB : SLGGLGSSGSSGGGGSGGGD6
1797                    PB : SSSSSSSDDDDGGGGGGGGD1
1669                    MF : SGDGLGGSSGLSSGSSMGGD4
1438                   CJL : SSSSSSSDDDDDGGGGGGGD1
1402                    AO : MDSGSGSSGGGGSDGSSDDS1
1233                   AJW : SSSSSSSMMLLGGGGDDGGD1
1079                    KG : SSSSSSSMMGMLMMMMMDDD20
1017                   NPL : SSSSSGLMMMMMDMDMDDLD20
 982                   JRS : SSSSSSMMMMLLDLLGGGGD11
 939                    GH : MSLLSMMSMMMMGSSGGSDS14
 884                    AH : SSMMSGLMMGSSMMMMSMSD20
 871                    JD : SSSSSSMMLLLGGGGDDDGD1
 866                    LG : MSDGMMMSSSSMMLLMMLSD19
 865                   JGR : SSMMSGLMMGSSMGMMSMSD20
 647                   PEJ : LSSMSSGSDSSGLLSLSLMD8
 503                    CF : SSSSSSMMMGGGGLMDMDGD6
 471                   LLH : SSSSSSSSSSSGMLMLMMMD17
 306                   PRJ : GLLSGSGSGGGGGDDDDDDD2
 300                   MCK : SMMMSDDSSSSMMGGGGDDD2

Script for plotting

Assuming you have gnuplot and convert available on your system then click here for a script for plotting one of the "run" flies generated by the evosun software. Save this in PlotFit.sh and set the file permission to include "executable".

Usage

./PlotFit 0

Will create qplot0.jpg from run0.dat. Hope this helps.

This project requires five files:

• Symbots04.cpp
• symbot.h
• symbot.cpp
• Random378.h
• Random378.cpp

Linux compile:

g++ -o symevo.exe -lm -O3 Symbots04.cpp symbot.cpp Random378.cpp

When the code is run it produces 30 run?.dat files and a best.dat file that contains the most fit symbot in the last beneration of each run. The individual run files contain one line per generation. Each line contains the the mean, deviation and maximum of fitness followed by the average for each of the five symbot parameters across the population. A line of a run file thus has values:

mean dev max LL LR RL RR S

0.001       //constant of integration
2           //number of eyes
0.05        //radius
0.175501    //x position
0.712202    //y position
14.3667     //heading
0.785398    //eye 0 angle
1           //eye 0 radius
-0.494729   //eye 0 to left
0.977191    //eye 0 to right
-0.785398   //eye 1 angle
1           //eye 1 radius
0.890991    //eye 1 to left
-0.553923   //eye 1 to right
0.148893    //roll forward with no stimulation

A typical fitness plot for a run might look like:

While the trajectory of the connections is given by:

What to turn in.

In addition to the usual writeup address the following questions:

• Is there one basic behavior arising or several? How can you tell?
• Do symbots usually drive forward or backward? Why?
• A symmetric or asymmetric control nets more common?

Script for plotting

Assuming you have gnuplot and convert available on your system then FitPlot.sh and PlotConnect.sh are script for plotting fitness and neural connections from a run file. Call the script with the number of the runfile to generate the plot, e.g.

./PlotConnect.sh 0

This project requires five files:

• PDproject.cpp
• vaut.h
• vaut.cpp
• Random378.h
• Random378.cpp

You may also want the tournament scoring software TournamentPD.cpp and an example contenstants file test.con. This file is of the form:

Name
Machine
Name
Machine
...

The compile line (at least on my Linux box) is:

g++ -lm -O3 -o evolve.exe PDproject.cpp vaut.cpp Random378.cpp
g++ -lm -O3 -o PDtourn.exe TournamentPD.cpp vaut.cpp Random378.cpp

run*.dat  *=1..20  statistical stracking of runs
pop*.dat  *=1..20  final populations of finite state machines

The random number seed is keyed to the time - change it to your own fixed value. Run the code.

The run files contain the average Prisoner's Dilemma score and its standard deviation in each generation, one per line. The pop files contain the finite state machines present in the final population. This is the format in which to turn in finite state machines for the tournament.

What to turn in.

In addition to the usual writeup E-mail one finite state machine, designed or evolved (say which), to Dr. Ashlock. You may use no more than 200 states. This machine will be used in a tournament. For the 20 runs you did, look at the fitness straces and report and deviations from cooperation, count how many of your populations were basically cooperative, and explain the strategy you use to create your tournament entry. An example of a non-coperative population trace is:

This project requires six files:

• Packer.cpp
• perm.h
• perm.cpp
• RK_Packer.cpp
• rkperm.h
• rkperm.cpp
• Random378.h
• Random378.cpp

The compile line (at least on my Linux box) is:

g++ -lm -O3 -o packer.exe Packer.cpp perm.cpp Random378.cpp
g++ -lm -O3 -o rkpacker.exe .cpp RK_Packer.cpp rkperm.cpp Random378.cpp

The code contains an example bin packing problem specified by the following for lines of code (which are not adjacent):

#define permlen 17
#define nbins 5
int goods[permlen]={30,30,40,40,30,40,18,16,33,33,40,35,35,15,22,23,20};
int bins[nbins]={100,100,100,100,100};

The two programs used different representations for permutataions; direct and random key. Compare time-to-solution for these programs on the canned example in the code and at least two other examples you construct. There must be at least 80\% success on those examples and their mean time to solution must be 100 generations or more.

What to turn in.

In addition to the usual writup discuss what makes a hard or easy bin-packing problem. Clearly more goods and more bins make things hard so concentrate on what combinations of good sizes and bin sizes cause trouble.

The Herbivore World

This project will let us study the herbivore task discussed in class. We will have robotic agents capable of turning left or right, advancing, and of eating a box that is in front of them operating on a 16x16 grid with walls at the edge. There are 16 boxes on the grid and when a box is eaten a new box appears. The robotswill be controlled with GP-Automatat:

A GP-Automata:

--------------
Start:0->4
   If Even  |  If Odd  | Deciders
-----------------------------------
 0)  2-> 6  |   3-> 2  |  (min (~ x7) 2)
 1)  3-> 5  |   0-> 1  |  (< (<= x5 2) x1)
 2)  2-> 1  |   4-> 5  |  (+ x7 (<= x1 (~ 2)))
 3)  0-> 5  |   0-> 6  |  (<> (Odd 0) (max (~ x7) -2))
 4)  3-> 0  |   1-> 6  |  (Com (ITE (Odd 1) 2 0))
 5)  2-> 2  |   0-> 2  |  (min (~ x7) (< (Com x6) x4))
 6)  2-> 5  |   0-> 0  |  (ITE (ITE x1 2 x3) x8 x8)
 7)  2-> 4  |   2-> 2  |  (= 1 (+ (Com x3) -2))
------------------------------------

The code required for this project is as follows:

• botworld.cpp
• botworld.h
• Forager.cpp
• intGPAstack.cpp
• intGPAstack.h
• its.cpp
• its.h
• Random378.h
• Random378.cpp

The compile line (at least on my Linux box) is:

 g++ -lm -O3 -o forage.exe Forager.cpp its.cpp intGPAstack.cpp botworld.cpp Random378.cpp 

Right now the code is set to do three fitness evaluations per creature with eight state machines. Reset this to cover all possible combinations of 8 or 12 states and 1 or 3 boards per fitness evaluation. The porgram produces run files that contain:

mean_fitness dev_fitness max_fitness left right forward eat think

What to turn in.

In addition to the usual writup do the following: compare performance for the four run regimes, and pick a single GP-Automata perform an analysis of the algorithm it encodes. Be sure to discuss the evolution of the action numbers. Extra Credit: Turn in a GP-Automata for a competative foraging contest. Uo to 20 points may be earned in this manner. The contest simulator will be made available presently. You GP-Automata should be in the format above, as output by the routines handed out with the project. Use eight states and turn it in by Thursday May 6th.

Contest Software

• Contest.cpp

The compile line (at least on my Linux box) is:

 g++ -lm -O3 -o countest.exe Contest.cpp its.cpp intGPAstack.cpp botworld.cpp Random378.cpp