An Evolutionary algorithm (a.k.a genetic algorithm) is a search heuristic inspired by Darwin's theory of evolution. It reflects the process of selection where the fittest individual is selected for reproduction to pass on traits. In its simplest form, there are 5 phases: initial population, fitness function, selection, crossover, mutation. The initial population is the starting point. There is a set number of individuals, which represent solutions to the problem you want to solve. Each individual is characterized by a set of parameters (usually binary values) that can be joined to form a string. The fitness function assigns a fitness value to each individual based on how fit they are. Selection involves picking the fittest individuals who will pass their traits to the next generation. In crossover, a crossover point is selected for each pair at random. Each offspring is created by exchanging genes of parents until the crossover point is reached. Mutation occurs in a small percentage of offspring by flipping some of the bits in the string. This is done to ensure diversity to prevent premature convergence. Termination occurs when convergence is achieved and signals the end of the program. Convergence occurs when the offspring generation are not significantly different from the parents. This also means that a solution has been reached. It is also important to note that the population has a fixed size, and the least fit individuals are eliminated each round to leave space for new offspring.
We implemented a Genetic algorithm
Pseudocode:
START
Generate the initial population
Compute fitness
REPEAT
Selection
Crossover
Mutation
Compute fitness
UNTIL population has converged
STOP
Object-oriented programming: Each fish has an rgb value and a score variable
Initial Population:
Generate 16 fish with random rgb values. Add each fish in a list of Fish.
The score will act as our fitness function. The score measures the “sameness” of the fish’s colour and that of the environment(background color) it is in.
Fitness function:
The euclidean distance of the rgb values of the fish and its environment
Scoring Function
Selection:
We sort the list of fish based on their scores such that the fish which are most similar to their environment are at the beginning of the list and those that are the most different are at the back of the list.
Crossover:
We take the first half of the list of fish and breed the offsprings.
There is a 50% chance that the r,g,b values will come from parent1 and parent2 respectively.
The fish are bred twice so as to get a population of 16 again.
The score of the offspring is then calculated same as above.
Mutation:
There is a 4% chance that a mutation can occur, and the way it occurs is that an offspring would just have random values for its r,g,b.
Termination:
We chose not to terminate the program(as a design choice) so that we can observe the mutations
