CS341EA-F26 - Genetic Algorithms

Genetic Algorithms

Genetic algorithms are a set of approaches that seek to optimize a "fitness" function by iteratively generating populations.

Some terms:

Genotype: a sequence of "genes" (we will use bits) encoding an individual
Phenotype: the expression of those "genes"
Fitness: a score/value assigned to an individual capturing how well it performs with respect to the problem at hand

Here is the version we will use in the class activity:

A. Initialize population with n individuals, represented by a k-bit string

B. Iteratively:

1. Score the fitness of each individual
2. Produce the next generation by repeating n times
  1. Select 2 individuals with high fitness scores
  2. Crossover their genotype to produce a new k-bit string
  3. Mutate this k-bit string to produce and individual for the next generation

Let k = 6. Divide into 3 groups.

Initialization

Each student writes down one ingredient (e.g., salt, chocolate, ginger...) on a slip of paper
Each student represents a countertop with generations of dishes.
For the initial generation, each student uses dice to randomly fill out their first k-bit string of 0s and 1s to obtain a genotype.
Randomly pick out k slips of paper -- this will tell us how to map genotypes --> phenotypes.
Score each dish (collect votes from the class).

Iterate generations

Each student generates their next dish by:

Selection: Roll a die twice and select the higher-scoring dish for Parent A. Repeat for Parent B.
Crossover: Copy Parent A's genes for the first half of the genotype and Parent B's for the second half.
Mutation: Roll a die to select a gene and flip its bit.
Score by voting

Genetic Algorithm Activity

Today's coding activity: Link here!

You should have completed:

You should be working on:

Waypoint 3: Reading Algorithms (due Wed 9/30 by 9am)
Project 2: Musical Genetic Algorithms (due Thu 10/8 by 11:59pm, Milestone 1 due Friday 10/2 by 9am)

Page updated

Report abuse