In java: Based on the concept of natural selection. They allow us to explore a search space by "evolving“ a set of solutions to a problem that score well against a fitness function. An example is particularly helpful in understanding this concept. We'll use the bin packing problem, which is a famous problem in computer science. Pretend that your town is being attacked by zombies, and you have to abandon your house and go on the run. (It's possible that this isn't *exactly* how the problem is elassically deseribed, but this version is way more interesting.) You are only able to carry 10 pounds of stuff with you in addition to food and other necessities, and you want to bring things that you can sell for the greatest amount of money possible. Below is a list of items you could take, along with their weight and selling price. Which items should you take with you in order to maximize the amount of money you can get? Item weight.worth Cell phone, 0.25, 600 Gaming laptop, 10, 2000 Jewelry, 0.5, 500 Kindle, 0.5, 300 Video game console, 3, 500 Small cuckoo clock, 5, 1500 Silver paperweight, 2, 400 It turns out that the best you can do in this situation is to take the cell phone, jewelry, Kindle, video game console, and small cuckoo clock. Together, these items weigh 9.25 pounds and are worth $3400. The tricky thing about the bin packing problem is that the only way you can be sure that you have the optimal set of items is to try all possible combinations. You might be tempted to try short cuts, like taking items in order of worth until you hit the weight limit (which in this case would mean taking just the gaming laptop, worth $2000) or taking the lightest items until you reach the weight limit (which in this case would be the cell phone, jewelry, Kindle, silver paperweight, and video game console, worth $2300). Neither of these strategies nets as much money as the optimal combination. Trying all possible combinations is a lot of work, and the zombies might get you while you're trying to work things out. The solution we end up with is not guaranteed to be the optimal one, but it is likely to at least be pretty good.
Crossover and Mutation
The two main operations in evolutionary computing are crossover and mutation. Crossover
works like this:
Randomly choose two parents from the population. Let’s say these:
Parent 1: T F T F T T F
Parent 2: T T T F F T T
Those two parents will create a child whose DNA is related to the parents’. It works like
this: for each of the seven genes in the chromosome, we will randomly pick a number
between 1 and 10 and use it to choose which parents’ value the child will get. If the random
number is 1 through 5, we will use Parent 1’s included value for the child; if it is 6 through
10, we’ll use Parent 2’s. Let’s assume our seven random numbers are:
1 4 10 3 6 6 9
Then the child’s set of item included =ields would be:
Child: T F T F F T T
Mutation is even simpler: we choose a single individual from our population and again
generate a random number between 1 and 10 for each nucleotide. Mutation generally
happens more rarely than reproduction, so if the random number is 1, we will =lip that gene
in the individual; otherwise, we will leave it the same. Let’s assume our seven random
numbers are:
5 1 7 8 9 2 7
and the chosen individual’s included values are:
T T F T T T F
Then after mutation, that individual now looks like this (with the second gene =lipped from
a T to a F):
T F F T T T F
public class Chromosome extends ArrayList implements Comparable private static Random rng Used for random number generation public Chromosome() This no-arg constructor can be empty public Chromosome(ArrayList items) Adds a copy of each of the items passed in to this Chromosome. Uses a random number to decide whether each item’s included =ield is set to true or false.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 2 images
