Week 2 - Search Landscapes and Hillclimbing Flashcards
Describe the hillclimbing algorithm.
Generate a random solution with a fitness f1. Generate another random solution, with fitness f2. If f2>f1 then discard the first solution and select the second solution - effectively only “climbing up the hill”.
What is the difference between local search and hillclimbing?
Local search allows downwards moves.
What does PBS stand for?
Population based search
What are the two types of genetic algorithms?
Generational and steady state.
Describe generational genetic algorithms.
Genetic operators applied repeatedly to generate new populations. Generational elitist algorithms copy n best individuals unchanged to the next generation.
Describe steady state genetic algorithms.
Genetic operators applied N times (N small, 1 or 2) and bad solutions replaced.
Name 2 strategies for replacement in steady-state algorithms.
Replace weakest, replace first weakest.
What does selection represent?
Our strategy for deciding which areas of the search space to focus our efforts on.
What do genetic operators do?
Provide our means to generate new candidate solutions (exploitation and exploration).
What is single gene mutation?
Choose a gene at random, add a small random deviation to it. Often chosen from a Gaussian distribution.
What is vector mutation?
Generate a small random vector of length L, and add it to the candidate solution.
What is the difference between direct and indirect encoding?
Indirect allows you to “code away” undesirable features, whereas direct is a much faster interpretation of the chromosome, but may generate unwanted chromosomes.
Direct = variable in problem, indirect = variables of a constructive heuristic
Direct is fast and straightforward. Indirect is slow and rugged.
What’s the difference between exploration and exploitation? Give an example algorithm for each.
Exploration -> you want to explore every option and path (the whole search landscape) (e.g. EAs, genetic algorithms)
Exploitation -> you have domain knowledge, you want to get close to an answer -> adjust parameters as we want operators to have a fair chance of yielding good new solutions (small change and/or combine bits from solutions we already know are good) (e.g. hill climbing)
