Genetic Algorithms 20091
Switch branches/tags
Nothing to show
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.


Team Members:
     Adam Risi
     Jon Potter

Project Description/Checkpoint 2:

		In project Robo-War, we will be using genetic
		algorithms to generate small programs that simulated
		robots will execute. The whole of the population will
		be executing at the same time, allowing the robots to
		"war" against eachother. When the number of remaining
		robots in the population reaches a given amount, new
		robots will be generated using crossover and
		mutatation methods. This "live" approach to a fitness
		function means that as the program runs, we will get
		to see the actual evolution of the robots from
		"brainless" drones, to something that should be a
		considerably stong warrior.

		The parameters of the problem are mostly the
		description of what the robots can "do" (motion,
		wepons, etc.) and the environment that they will be
		doing it in. The robots tentative abilities will be to
		turn, move forward or reverse, aim, and fire. As the
		programs development continues, the robots will be
		given more specific senses, like the ability to find
		groupings of other robots, etc. The environment will
		be a NxN space, with (presumably) a couple of


		As a system with no perfect solution, the solution
		space is infinitely large. The program has the ability
		ot keep running as long as the user wants, and the
		ability to generate more and more complex
		warriors. The system will be run for as long as
		possible once development has reached stability. In
		code, each robot will have a "solution," - its
		internal program.


		The output of this GA will be the source code for the
		different warring robots, and how well that given
		source code has done over time. How many battles the
		robot has survived, how many robots it has killed,
		etc. will all be used to judge the functionality of
		the robot.

Phenotype and Genotype Definition and Translation/Checkpoint 3:
	Work Summary:

		For this checkpoint, we have written the code to
		represent the robots genotype, and the robot
		phenotype. We have also written the fitness function
		(the simulator). There is still a significant amount
		of work that needs to be done on the simulatior;
		however, it does currently function.

		In this project, a robots instructions are defined as a
		finite set of program operation codes. These codes
		include things like "forward", "reverse", "rotate",
		etc. All robots are going to have the same length
		program, comprised of the same instructions.

		DATA STRUCTURE: We are using a simple ordered list to
		store the robots operation codes.

		GENETIC MAPPING: Genetic mapping is essentially the
		the simple execution of the ordered instruction codes.

		GENETIC REPAIR: All instruction codes are valid at any
		time. To prevent robots from roaming off the edge of
		the world, they will roll from one side to the

		BEST INDIVIDUAL AFTER ALL RUNS: The simulation starts
		with 2 individuals, and they are inherently the best,
		as they never die. As soon as the simulator is
		finished, they will be able to kill eachother, and the
		genetic algorithm will be able to start producting

		GRAPH GENERATED BY CODE: Graph is currently infinitely
		linear (y=x), because the simulator does not yet
		implement "fire." This means that the greatest fitness
		at any time slice is mearly the current time slice
		number (because no robots die, or kill any other


		A robot will be graded based on its performance in a
		simulated battle. The phenotype for a given robot are
		its statistics while battling. So far, this includes
		the number of kills, and the number of time slices the
		robot has managed to stay alive. 

	Genotype/Phenotype Translation:
		In this project, the translation function is actually
		a complex, live, robot-battle simulation. As the
		robots battle, their statistics change, and so does
		their fitness (the sum of the kills and time
		alive). When a robot dies, a new robot is generated
		(from the living population) to take the place of the
		lost robot. The simulation itself executes each robots
		instructions, and calculates kills and life times.

Fitness / Checkpoint 4:
		In this project, the battle statistics of a robot are evaluated to determine the fitness of the robot.
		The fitness for a robot is determined by a live simulated robot battle.  The entire population is on the battle field at the beginning, and the battle is every robot for itself.  When a robot dies in this simulation, we remove it from the battle, and we replace it with a new robot formed by doing crossover and mutation.  We can judge the fitness of a robot by the statistics collected during the battle for each robot.  For example a high kill count, a long lifespan, and a high accuracy rating all contribute to a good fitness score.  We are not applying any scaling or penalties other than to weight the different battle statistics so that, for example, lifespan matters more than accuracy.
		We currently have the simulation working and almost entirely completed, but as of yet we do not collect sufficient battle statistics to accurately determine the fitness of each robot.  At this point, we simply use the lifespan as the fitness, by removing robots that die from the arena so as to encourage those who can survive longer.  We will record full battle statistics soon.
	Generation 0
		We initialize robots with a random instruction set (genomes) drawn from a list of possible instructions and limited to a fixed length.
	Bad Mojo
		We handle bad genotypes by simply never creating them.  Our genotype is a list of robot instructions, and any order is valid.  Therefore when we create a robot, we pick instructions from a list of legal instructions, and we limit the list to a certain length.  This way we only ever have legal robots, and when legal robots crossover and mutate they will produce more legal robots.
		Because our simulation is so complex, we are not able to record the desired statistics yet.  Also, since the simulation is what gives life to the robot's instructions, recording the best fit, worst fit, and average fit individual not very meaningful, because it will appear in every case as a random list of instructions, and will only make sense by watching the robot in action.  Eventually, we want to showcase best and worse individuals by dueling them in the battle arena.
Reproduction, Selection / Checkpoint 5:
	We now keep track of each robot's lifetime, which is the number of time slices that it has been alive in the arena.  Therefore we can select only the best robots (longest lifetime) for reproduction and selection.  We also keep statistics about the best robot (longest lifetime) and we write the time slice and the lifespan of the best robot into the file "stats" at every time slice.  Therefore we can see how our robots are evolving to become better and better.  We also graph this relation in realtime (assuming gnuplot is installed) so we can see it progressing more clearly.
	We've included a graph, and a stats file for a sample run in this submission.
	Our selection scheme is overlapping.  We do selection and reproduction whenever a robot dies, so the crossover rate is tied to the death rate.  We mutate 1/4 of the time.  When a robot dies, we produce one to replace it by sorting our population based on lifetime and clamping it at the population limit so that we get only the best robots.  We then pick two random parents from that set of robots and perform crossover.  Therefore we do a modified survival selection.
	This selection and reproduction scheme seems to work very well.  You can see from the stats file and the graph that robot lifespan increases throughout the generations.  As the robots evolve, they become more effective killers and survivors and it is evident that we start to converge on a solution after around 2000 time slices.
Population / Checkpoint 6:
	We chose to vary the population size to see its affect on convergence.  We used population sizes of small (5 robots), medium (25 robots), and large (50 robots).  Surprisingly smaller population sizes seem to converge to much higher values.  We expected larger population to work better since there are more robots to choose from in crossover and mutation, but small populations yield higher individual fitness.  The reason for this is that with a larger population size, there are more robots that can defeat the "best" robot, so its fitness (longevity) will never be as high.  For the extreme case, a small population of one robot will give very high fitness because there is no competition to kill the robot - one robot isn't much of a battle.  However looking at the graphs you can see that with larger populations we converge on a value sooner, even though it is a lower value.
	Therefore we find that small populations yield better individual fitness, but do not necessarily produce the greatest performance robots.  We included graphs for each population size: "large_population.png",  "medium_population.png", and "small_population.png".  These graphs illustrate the above conclusions about population size.
	We decided on a population size of medium so that our robots will have a little bit of breathing room to get high individual fitnesses, but also have enough competition to make them high performance.  This should result in a good compromise.

		Note: to see graphs of fitness over time you need to install gnuplot and make sure it is on your path (i.e. you can run "gnuplot" from the terminal).  For linux you can get it from your distro repository, and for mac you need to install MacPorts and then run "sudo port install gnuplot".
		This program does not need to be built - simply run and the simulator will begin. While the
		fitness for a given robot is being calculated, we are
		working on a way to display it.