How do you Cram all that Circus?

A Circus Train Optimizer

Sean Finney

Mark Angelillo

CS63 Fall 2002


The Problem at Hand

[circus train!]

What does the best circus train look like? This is what we hoped to find out, and why we pitted genetics against time in a battle the likes of which have not been seen since the three-eyed fish.

[a three eyed fish]
a three eyed fish

Representing the Task

A circus train consists of different kinds of cars, each designed to fullfill a specific task essential to the needs of a travelling circus. There are various animal cars, a car for the circus workers to sleep in, a dining car, a feed car, a car carrying the tent and supplies. Since we were dealing with "bit strings" (that is, integers set to either 0 or 1, pretending to be bits). The following table shows how each is represented:

circus train car types
car typepurposebit string
locomotiveto pull the train0000
cabooseeveryone knows...0001
sleeperwhere the workers sleep0010
diningwhere the workers eat0011
entertainmentwhere the workers play0100
ringleaderwhere the boss stays0101
monkeymonkeys0110
lionlions0111
horsehorses1000
elephantelephants1001
feedfeed for the animals1010
clownseveryone loves clowns...1011
freakshowswarthmore1100
cannonevery circus needs one1101
hobounused car, probably occupied by vagrants and swat grads1110
tentthe circus tent and supplies1111
table 1: circus car types

How We Optimized the Train

We optimized the train by sensically thinking about the things that would make most folks happy being on a circus train. For example, folks in a sleeper car would like to be next to a diner car or an entertainment car, whereas they wouldn't like being next to an animal car or the clown car (they'd have nightmares). Also, since the train could be of variable length, there needed to be a number of tents proportional to the size of the circus. There couldn't be more than one ringleader, and the animals had to be fed. For a full description of bonuses and penalties applied, please browse the source code.

Running the Algorithm

We found from experimentation that larger population sizes and slightly higher mutation rates led to greater improvement in the "fitness" of our circus train. The parameters we used were:

./ga -f results -s 199 -l 56 -g 1500 -m 0.05

and here's our table of results:

optimal results from running the GA
run numbergenerationfitnesstrain configuration
11132240locomotive-monkey-lion-tent-elephant..-horse-sleeper-dining-entertainment-ringleader-tent-clowns-feed-caboose
2380238locomotive-entertainment-dining-dining-sleeper-feed-tent-clowns-lion-monkey-feed-horse-elephant..-caboose
3365238locomotive-feed-tent-elephant..-lion-clowns-dining-sleeper-sleeper-entertainment-ringleader-horse-monkey-caboose
4949225locomotive-elephant..-horse-monkey-ringleader-entertainment-sleeper-dining-cannon-feed-lion-clowns-feed-caboose
5124229locomotive-monkey-ringleader-dining-entertainment-entertainment-sleeper-elephant..-feed-lion-clowns-horse-tent-caboose
6179228locomotive-clowns-tent-dining-sleeper-entertainment-monkey-feed-lion-horse-monkey-elephant..-feed-caboose
780230locomotive-tent-lion-horse-monkey-elephant..-feed-entertainment-sleeper-dining-entertainment-dining-tent-caboose
8115225locomotive-horse-entertainment-dining-entertainment-sleeper-ringleader-sleeper-entertainment-tent-feed-lion-clowns-caboose
91150234locomotive-entertainment-sleeper-dining-entertainment-dining-ringleader-dining-tent-elephant..-lion-feed-clowns-caboose
10275222locomotive-tent-tent-feed-horse-elephant..-monkey-lion-dining-entertainment-ringleader-sleeper-swarthmore-caboose

Discussion of Results

It is with great pleasure that we can say the study into the genetic algorithm-based construction of circus train configurations was successful. in each test run, the resulting car configuration was tailored with the wants and needs of those on the train in mind. in most cases, the humans would not find themselves having to walk through an animal car or freakshow car to get to the diner car, and the animals would find themselves next to other animals or the feed car. also, the locomotive was always in front and th caboose in the back (this is important, you know). The only question that remains to be answered is whether our optimal settings for mutation/crossover/population/generations in the actual ga program are actually the optimal ones (we found ours by trial and error). We leave such research to future circus train researchers

thanks: