English
资源说明：Genetic Algorithms 20091
Project:
Robo-Wars
Team Members:
Adam Risi
Jon Potter
Project Description/Checkpoint 2:
Overview:
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.
Instance:
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
obstacles.
Solution:
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.
Output:
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.
Genotype:
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
opposite.
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
offspring.
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
robots).
Phenotype:
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.
Statistics
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.
Building:
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
robo-war.py and the simulator will begin. While the
fitness for a given robot is being calculated, we are
working on a way to display it.
本源码包内暂不包含可直接显示的源代码文件，请下载源码包。
