COMP 3200 - Intro to Artificial Intelligence - Lecture 13 - Evolutionary Computing
Watch on YouTube →
Overview
Dave Churchill explains evolutionary computing as a family of population-based optimization methods inspired by natural selection, where candidate solutions are encoded as genotypes, scored by fitness, and improved through parent selection, crossover, and mutation. He details the algorithm’s design choices using Sudoku, roulette-wheel selection, elitism, and simulation examples, while emphasizing that evolutionary algorithms often find good local solutions quickly but may struggle to reach a global optimum.
Key takeaways
- An evolutionary algorithm needs a representation that can encode every candidate solution, a way to decode it, and a fitness function that ranks candidates for selection.
- Roulette-wheel selection chooses candidates in proportion to fitness: an individual with fitness 10 has twice the selection probability of one with fitness 5, while weaker candidates can still be selected.
- Crossover recombines existing candidate information, while mutation introduces variation that can help a population escape local optima.
- Elitism preserves top candidates, such as the best 5%, and guarantees that the best fitness retained by the population will not decrease between generations.
- Evolutionary algorithms often deliver useful solutions quickly but can plateau; Sudoku demonstrates why a high fitness score may not mean a candidate is close to a globally solved board.
- Representation should fit the problem: integer arrays suit genetic algorithms, real-valued vectors suit evolutionary strategies, and tree structures support genetic programming.
Chapters
- Dave Churchill maps a problem to an environment, a candidate solution to an individual, and solution quality to fitness.
- Fitness in an evolutionary algorithm is represented by a function, unlike natural fitness, which is inferred from survival and reproduction.
- Evolutionary computing and evolutionary algorithms are used interchangeably, and the lecture frames the topic as preparation for Assignment 4.
- A phenotype is an organism’s realized traits, shaped by both inheritance and development, or nature and nurture.
- A genotype is the genetic information that contributes to producing a phenotype; offspring inherit combinations of traits from both parents.
- Churchill distinguishes individual selection from population-level evolution: reproduction selects individuals, while trait frequencies change across generations.
- DNA uses the bases A, T, C, and G; genes are functional stretches of DNA, and a genome is an individual’s complete genetic material.
- Humans typically have 23 pairs of chromosomes, while sperm and egg cells carry 23 individual chromosomes.
- Crossover recombines genetic material from two parents; in evolutionary algorithms, it similarly combines parts of two encoded candidate solutions.
- Mutations can result from replication errors or environmental causes such as radiation, and can be harmful, neutral, or advantageous.
- Evolutionary algorithms use mutation to introduce new candidate traits that may improve fitness.
- Natural selection does not involve individuals intentionally adapting; random variation followed by differential reproduction changes populations over time.
- Peppered moth coloration illustrates that fitness depends on the environment: light moths were camouflaged on lighter trees before industrial soot darkened them.
- After trees became soot-covered, darker moths were less visible to predators and had more opportunities to reproduce.
- The example shows how environmental change can shift which inherited traits are advantageous without organisms choosing to change.
- Evolutionary computing uses natural selection as inspiration for solving increasingly complex computer-science problems.
- A simulation can evaluate millions of individuals and generations far faster than real-world generations occur.
- To apply the method, a problem must be modeled with candidate individuals, an environment or evaluation setting, and a fitness measure.
- The basic loop initializes a randomized population, evaluates fitness, selects parents, creates offspring through crossover and mutation, and replaces the population.
- A car-design example scores each candidate by simulated travel distance, such as 23 metres versus 150 metres.
- Population size, parent selection, crossover, and mutation all introduce parameters that can make an otherwise correct algorithm perform well or poorly.
- Genetic algorithms commonly use binary strings or integer arrays; evolutionary strategies use real-valued vectors.
- Evolutionary programming can encode finite-state machines, while genetic programming represents candidates as trees.
- These methods share the same core evolutionary loop and differ chiefly in representation and the operators suited to that representation.
- A Sudoku board is the phenotype; flattening its 9-by-9 grid into an 81-value sequence provides a genotype for genetic operations.
- Encoding and decoding must work both ways, and the genotype space must be able to represent every possible solution.
- Fitness evaluates a candidate phenotype; if the original objective is minimization, such as reducing Sudoku conflicts, the score can be transformed into a maximization objective.
- Churchill’s Sudoku example counts repeated values within rows, columns, and 3-by-3 squares, then converts conflicts into a score to maximize.
- A useful fitness scale should distinguish candidates finely; nonlinear scaling can give a solved board a stronger advantage over a nearly solved one.
- Other fitness functions include measuring how far a simulated robot walks, how far a car travels on a track, or how well a rag-doll character walks.
- A population is typically a fixed-size collection of candidate genotypes, often represented as an array of arrays.
- Diversity reflects variation in genotypes, phenotypes, or fitness values; a useful population balances fit candidates with enough variation to explore alternatives.
- Parent selection assigns higher-fitness candidates a greater probability of reproduction while retaining a nonzero chance for weaker candidates.
- Roulette-wheel selection chooses a random value from the total fitness range and returns the individual whose cumulative fitness first exceeds it.
- A basic crossover can split two parent arrays and exchange their halves to produce two children.
- Mutation can flip a bit, replace a Sudoku value with a random number from 1 to 9, or swap two values; swapping can preserve the count of each digit.
- Survivor selection determines which candidates persist; elitism carries top candidates, such as the best 5%, directly into the next generation.
- With elitism, the best fitness seen so far cannot decrease because the strongest individual is retained.
- Initialization may be fully random or use problem knowledge, while termination can depend on reaching target fitness, a generation limit, or a time limit.
- Evolutionary algorithms often improve candidates toward local optima, but reaching a better global optimum may require crossing a lower-fitness region.
- Sudoku boards can have high scores while remaining far from solved because fixing a few conflicts may require changing many other values.
- Mutation can sometimes move candidates out of a local optimum; typical runs improve quickly at first and then plateau, making the method useful when a good-enough answer is acceptable.
- Genetic programming represents mathematical expressions, Boolean formulas, or code as trees, allowing crossover to exchange subtrees and mutation to change operators or values.
- A browser-based vehicle example encodes car structure and evaluates fitness by how far the simulated car travels over a randomly generated track.
- Successful cars are more likely to contribute to later generations, while small differences among related designs can result from mutation.
Transcript excerpt
0:00 So today we're going to be talking about uh an introduction to evolutionary computing and evolutionary algorithms. And this is a bit of a uh it's a cool lecture. I like I really like this topic. And um we're going to have this one lecture and then we're going to have an assignment about this lecture. So it's not like we need to learn a bunch of stuff. This is a kind of self-contained lecture. It'll it'll have everything that we need to know um algorithmically for the assignment. And then the next lecture we'll go over what the assignment is about. So um the positioning of evolutionary computing, what does that mean? Well, evolutionary computing mostly is part of computer science. Um it's not necessarily a part of life sciences or biology, but biology, you know, we're talking about the term evolutionary, so
0:48 of course you'd associate that with biology. and biology and the natural world are going to be the inspiration for these types of algorithms and also inspire the terminology for the algorithm but not the actual um process or yes the process itself is going to be based on nature but we're not simulating all of the things that happen in nature. So evolutionary computing can be applied in biological research but it has uh many possible applications. So also just realize that um evolutionary computing, evolutionary algorithms, EA or EC, I'm probably going to use those terms interchangeably. So EC is EA, it's just evolutionary methods. So what is the metaphor that we're trying to say here when we talk about evolutionary computing? Well, so far
1:36 throughout the the class, we've been talking about problem solving, right? So in problem solving we have a problem we have a candidate solution to that problem and we have some sort of measure
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Dave Churchill.