Overview
Goals: The goals for this assignment are
- Design and implement instantiable classes.
- Use arrays of objects.
- Read from and write to files.
- Implement basic exception handling.
Description: Imagine having an algorithm that has several parameters, but not knowing how to set them. Since there are an exponential number of combinations of settings for the parameters, trying out every possibility can be infeasible, even for a computer. One way of solving this problem is to use a meta-heuristic search algorithm to try to find a very good solution but by only searching through a much smaller number of possibilities. One such class of algorithms are genetic algorithms. With genetic algorithms, the parameters for the algorithm you are trying to set are viewed as a sequence of genes. The algorithms that are made up of these genes are experimentally tested in a computational simulation, and the algorithms that perform the best are used to create new algorithms, that consist of some of the genes from one algorithm, and some of the genes from a second algorithm. Additionally, random mutations are performed on the genes to produce further variation. You will use genetic algorithms to determine how creatures should move about in an environment to find food.
SPECIFICATIONS:
High-Level Algorithm
At a high level, your program will:
- Read configuration information and the initial set of gene sequences from a text file
- Add to the world the initial set of movers with the specified genes
- For the specified number of rounds:
- Add food to the world as specified
- For the specified number of time steps:
- Move all of the movers and record if food was eaten
- Update the graphical user interface
- Select the specified portion of movers who performed the best
- Mate the selected movers to create additional movers
- Mutate the genes of the movers based on the specified mutation rate
- Clear the world of all movers and food
- Add the new set of movers to the world
- Write the configuration and the genes of the current set of movers to a text file
Dealing with Probabilities: This program uses many probabilities to give lots of randomness to the program's execution. Probabilities are real numbers in the range of 0.0 to 1.0, which means from won't happen to will happen. A probability of 0.2, means there is a 20% chance that it will happen. To get this effect, use your random number generator to get the nextDouble. If that double is less than or equal to the probability value, then it will happen. If it is greater than the probability, then it won't happen.
Steps 2 and 3g - Adding Movers: Movers are added to the world initially and at the end of each round. Each mover is placed in a random cell of the world that is not already occupied by another mover. The mover is added facing up.
Step 3a - Adding Food Groups: Food is added to the world in groups at the beginning of each round. For each food group, select a random cell as the center of the food group. Then fill the surrounding unoccupied cells (i.e., doesn't have a mover) with food based on the food probability. Only cells within the specified food group radius are considered. To do this you'll be iterating over a rectangle from the center row minus the food group "radius" up to and including the center row plus the food group "radius", and from the center column minus the food group "radius" up to and including the center column plus the food group "radius". Note the center of the food group might be near the border so make sure you stay within bounds of the world.
Step 3bi - Eating and Movement: Movers eat food when they move into a cell with food. When a mover eats a piece of food in a cell, that piece of food ceases to exist, and the number of pieces of food the mover has eaten is incremented. The amount of food that a mover eats in each a round determines if it will mate at the end of a round.
Movers move based on their genes. For each time step of each round, all of the movers will either move forward, turn left, turn right, or not make a movement. Movers are immediately moved, but are not move more than once per time step. If a mover attempts to move to a cell occupied by another mover or would move off the world, then the mover doesn't move at all.
Each mover has a nine-digit "gene" sequence that determines its movement. The genes are grouped into three triplets. The first digit of a triplet is used to determine the probability of the mover moving forward, the second digit is used to determine the probability of the mover turning left, and the third is used to determine the probability of the mover turning right. Each digit is divided by ten to obtain the probability. For example, if the first digit is 6, then there is a 0.6 probability (60%) that the mover moves forward.
The values in the triplet are evaluated in order. First determine if the mover moves forward. If it doesn't attempt to move forward, then determine if the mover turns left. If the mover did not turn left, then determine if the mover will turn right. If the mover did not turn right, the mover does not move.
There are three triplets in the "gene" sequence. The mover's surroundings determine which triplet will be used to determine movement. If there is food in front of a mover, the first triplet will be used. If there is not food in front of a mover, but there is food in an adjacent cell (diagonals are not considered adjacent), the second triplet is used. Otherwise, the third triplet is used.
Step 3c - Selection: After all of the time steps have been done for a round, the movers who eat the most food are selected. Make a list of movers sorted by how much food they've eaten (hint: carefully insert the movers into an ArrayList). Use the specified proportion of the population for mating. For example, if that proportion was 0.3, then the top 30% of the population would be used to produce the next population of movers. You may determine how to break ties. Unselected movers are removed and those that were selected have their food counts set to 0.
Step 3d - Mating: The movers that were selected for mating and their "offspring" will be used as movers in the next round. Create as many offspring as needed to have the same number of movers in each round. Randomly choose with equal probability two different movers from the selected movers as the parents. (Hint: if you have a list of 10 selected movers, choose a random index from 0 to 9 to get an equally probable random choice.) Create a new mover based on the parent's genes. For each triplet, randomly determine whether parent 1 or parent 2 will provide its triplet using a 0.5 probability (i.e., a 50-50 chance).
Step 3e - Mutating: After the new population of movers is made, mutate each "offspring". For each digit in an offspring's gene sequence, determine if the digit will mutate using the probability of mutation. If it does, get the next random integer (from 0 to 9 inclusive) and replace that digit.
Command Line Arguments
Your program uses two command-line arguments. The first is the name of the input file and the second is the name of the output file. If any other number of arguments is provided, print a brief error message stating how the command-line arguments are used by this program and then exit. If either file name is invalid, display a brief error message and then exit.
Recall, to pass command-line arguments into a program executed from Eclipse, right-click on the class that contains the main method and select "Run As → Run Configurations... Next, under the "Arguments" tab, there is a text field labeled "Program arguments:". You can type your arguments there separated by spaces.
Input/Output File Format
Your program reads a text file containing configuration information and an initial set of gene sequences. After your program finishes running the simulation, it must write an output file with the configuration information and the gene sequences of the last set of movers. Both the input and output files are in the following format:
- Line 1: two ints - the number of rows followed by the number of columns in the world
- Line 2: two doubles between 0 and 1 - the probability of mutations followed by the proportion of the population that is selected for mating
- Line 3: two ints - the number of rounds followed by the number of time steps of each round
- Line 4: two ints followed by a double between 0 and 1 - the number of food groups, the "radius" of each food group, and the food probability
- Line 5: an int - a seed for your random number generator
- Line 6 and beyond: each subsequent line will have a nine-digit sequence representing the genes of a mover
See the Testing section below for a sample input file. You may assume that the input files are valid, that is, they are in the specified format with at least 1 line having a gene sequence.
Graphical User Interface
We've provided a graphical user interface for your program so that you can watch the movers evolve. You'll need to download two files:
MoverWorldGUI.jar Add this jar file to your project in the same manner that you've been doing in the lab exercises. (https://pages.cs.wisc.edu/~cs302/?r=programs&programNumber=4 )
MoverWorldGUIImages.zip Unzip this file in your project directory. It contains the images that are used by our GUI. (https://pages.cs.wisc.edu/~cs302/?r=programs&programNumber=4 )
Construct a MoverWorldGUI object to open the GUI window. Use this object to update the GUI each time step after all of the movers have moved. You'll need to pass a two-dimensional array of characters created from your representation of the mover world. Use the class constants in the MoverWorldGUI class for the values in the character array. We've provided a javadoc (https://pages.cs.wisc.edu/~cs302/programs/p4/MoverWorldGUI.html) for you to understand how to make use of this class in your program.
Testing
Sample File: We've provided a sample input file for you to use with testing your program sampleConfig.txt
25 40
0.3 0.2
100 50
3 4 0.5
11
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
In addition to this file, you should verify that the output file created by your program is able to be read by your program. Once you have completed the program, you might also want to experiment with the configuration settings to see how they affect your program's results.
Execution Correctness: You will earn 75% for execution correctness if your program successfully reads the input file, runs the simulation, and writes the output file without doing steps 3c - 3e, that is, it runs the simulation with the same movers each round without creating new movers. You'll earn the additional 25% for implementing steps 3c - 3e, that is, it is a complete program that generates new movers as specified.