Week 6: Genetic Algorithms # 1 Flashcards
<p>What are the 2 classes/types of meta-heuristics</p>
Population-based methods & Trajectory Methods
<p>In population-based methods, what does a "population" refer to?</p>
<p>A group of solutions/states</p>
<p>A population of individuals exists in an environment with limited \_\_\_\_\_\_\_</p>
<p>resources</p>
<p></p>
<p></p>
<p>Individuals with higher fitness act as seeds for the next \_\_\_\_\_\_ of individuals through \_\_\_\_\_\_ and \_\_\_\_\_\_</p>
generation/population
recombination/mutation
mutation
<p></p>
<p></p>
<p>New individuals have their \_\_\_\_\_ evaluated and compete for survival</p>
<p></p>
<p></p>
<p>fitness</p>
<p></p>
<p></p>
<p>Over time \_\_\_\_\_ \_\_\_\_\_ causes a rise in the \_\_\_\_\_ of the population</p>
<p></p>
<p></p>
<p>Natural Selection
<br></br>Fitness</p>
<p></p>
<p></p>
<p>What are stochastic algorithms?</p>
<p></p>
<p></p>
<p>algorithms that explicitly use randomness to find the next state - it is not determined by the current state</p>
<p></p>
<p></p>
<p>Are Evolutionary Algorithms Deterministic or Stochastic?
<br></br>
<br></br>Are they population based? or Trajectory based?</p>
<p></p>
<p></p>
<p>Evolutionary Algorithms are stochastic, population-based algorithms</p>
<p></p>
<p></p>
<p>Are Evolutionary Algorithms Deterministic or Stochastic?
<br></br>
<br></br>Are they population based? or Trajectory based?</p>
<p></p>
<p></p>
<p>Evolutionary Algorithms are stochastic, population-based algorithms</p>
<p></p>
<p></p>
<p>What must a search algorithm do in order to perform better than a random search?</p>
<p></p>
<p></p>
<p>The search algorithm must take advantage of problem-specific information about the search target or the environment (just like heuristics)</p>
<p></p>
<p></p>
<p>What is Active information</p>
Measures the contribution of problem-specific information for successfully finding a target
<p></p>
<p></p>
<p>An algorithm does not create \_\_\_\_\_ information, it performs very valuable transformation of \_\_\_\_\_ information</p>
<p></p>
<p></p>
<p>new
| known</p>
In Genetic Algorithms, each point in the parameter space has a _____ value. The problem of the search is to find a sufficiently good such value
fitness
<p></p>
<p></p>
<p>For evolutionary algorithms, we require \_\_\_\_\_ information. This prevents the algorithm from behaving like a \_\_\_\_\_\_ search</p>
active
random
In Genetic Algorithms, the fitness of an individual is determined by the _______ traits.
These can be behavioural features, or physical features
phenotypic
in Genetic Algorithms, Selected individuals _______, passing their properties to the _______. Whereas other individuals die without _______, and their properties are ______
reproduce
offspring
mating/reproducing
discarded
<p></p>
<p></p>
<p>In Genetic Algorithms, small random variations called \_\_\_\_\_\_ occur in phenotypic traits during \_\_\_\_\_\_\_</p>
mutations
reproduction
In Genetic Algorithms, through mutations, new ______ of traits occur and get evaluated
combinations
<p></p>
<p></p>
<p>In Genetic Algorithms, for a given population, the basic operations are \_\_\_\_\_\_, \_\_\_\_\_\_ and \_\_\_\_\_\_</p>
<p></p>
<p></p>
<p>Selection
Reproduction
Mutation</p>
<p></p>
<p></p>
<p>A Genetic Algorithm maintains a \_\_\_\_\_\_ of candidate solutions for the problem at hand, and makes it \_\_\_\_\_\_ by iteratively \_\_\_\_\_\_ a set of \_\_\_\_\_\_ operators</p>
population
evolve
applying
stochastic (random)
describe the flow of a Genetic Algorithm
<p></p>
<p></p>
<p></p>
<p>Genetic Algorithms evolve from one \_\_\_\_\_\_\_\_ to the next according to selection and the \_\_\_\_\_\_\_</p>
population/iteration
search operators
<p></p>
<p>What are the search operators in GA?</p>
Recombination (crossover)
Mutation
Selection
<p></p>
<p>What is the general flow for Simple Genetic Algorithm?</p>
<p></p>
<p></p>
<p>What is the specialty of Simple Genetic Algorithms?</p>
<p></p>
<p>Emphasis on crossover</p>
<p>Describe the Simple Genetic Algorithm procedure in steps</p>
- initialize population with random candidates
- Evaluate all individuals
- Check if termination criteria is met. Stop if it is.
- Select parents
- Apply crossover
- Mutate offspring
- Replace current generation
- Go back to step 3
<p>What should the termination criteria be in SGA?</p>
<p>- Specified number of generations
- A minimum threshold from optimal reached
- No improvement is possible
- Memory/time constraints</p>
<p>In SGA, a mapping is applied from the \_\_\_\_\_\_ domain to the \_\_\_\_\_\_ domain.</p>
<p>parameter
<br></br>binary</p>
<p>Abstract representation of phenotype is called \_\_\_\_\_\_\_ or \_\_\_\_\_\_\_\_</p>
<p>chromosomes
| genotype</p>
<p>in SGA, a \_\_\_\_\_\_ is a string in the binary domain.
<br></br>
<br></br>0 and 1 represents the presence or absence of \_\_\_\_\_\_
<br></br>
<br></br>The \_\_\_\_\_ of genes can be important</p>
<p>Genotype/Chromosome
<br></br>Features
<br></br>Order</p>
<p>The \_\_\_\_\_\_ is a lower-level (less abstracted) encoding of a \_\_\_\_\_\_</p>
<p>genotype
<br></br>phenotype</p>
<p>How do you go from phenotype space to genotype space?
<br></br>How about the other way around?</p>
<p>Phenotype -> Genotype: Encode into a binary string.
<br></br>
<br></br>Genotype -> Phenotype: Decode binary string</p>
<p>What does the SGA reproduction cycle consist of?</p>
<p>- Selecting parents for the mating pool
- Shuffling the mating pool
- Applying crossover for each consecutive pair with probability Pc
- Apply mutation for each offspring with probability Pm
- Replace the whole population with the resulting offspring</p>
<p>What does mutation do to a binary represented genotype in SGA?</p>
<p>flips bits in order to randomly change the features of an individual</p>
<p>In SGA, parents are selected with a probability proportional to their \_\_\_\_\_\_</p>
<p>fitness</p>
<p>What is the main idea behind SGA selection?</p>
<p>Better individuals (who have higher fitness) get higher chance</p>
In SGA, what is a common method for selecting the parents given the set of individuals and their fitnesses?
<p>Roulette wheel technique
<br></br>- Assign each individual part of the roulette wheel to a normalized probability (they should all add up to 1)
<br></br>- Spin the wheel "n" times to get "n" individuals</p>
<p>In SGA, if crossover does not happen, how are the 2 parents copied over into their children?</p>
<p>They are copied into the offspring unmodified</p>
<p>In SGA, the crossover probability is Pc. What is the typical range of Pc?</p>
<p>between 0.6 and 0.9</p>
<p>What is the 1-point crossover? Note that this is only for binary strings (genotypes)</p>
<p>- Choose a random point on the two parents<br></br>
- Split the Parents at this crossover point<br></br>
- Create two children by exchanging tails (they become opposites of each other)</p>
<p>How doesthe n-point crossover (in the binary case) work?</p>
<p>- Choose `n` random crossover points</p>
<p>- Split along these points</p>
<p>- Glue parts, alternating between parents</p>
<p>- The 2 children become opposites of each other</p>
<p>How doesthe Uniform Crossover (binary) work?</p>
<p>- Treats genes independently</p>
<p>- Assigns "heads" to one parent, and "tails" to another</p>
<p>- Flips a coin for each gene (bit)of the first child</p>
<p>- Make an inverse copy which isthe second child</p>
<p>- The 2 children are opposites</p>
<p>In SGA mutation, we alter each \_\_\_\_\_ independently with a probability Pm</p>
<p>gene/bit</p>
<p>In SGA mutation, Pm is the mutatuon rate. What is the typical range for this?</p>
<p>between 1/pop_size and 1/chromosome_length.</p>
<p>Note that chromosome_length is the same as genotype_length</p>
<p>What is the motivation behind crossover and mutation in SGA?</p>
Crossover: Exploration, discovering promising areas in the search space
Mutation: Exploitation, optimizing within a promising area
<p>In SGA:</p>
<p>Crossover is \_\_\_\_\_\_\_, it makes a big jump into an area somewhere between the 2 parent areas</p>
<p>Mutation is \_\_\_\_\_\_\_, it creates random small diversions, thereby staying near (in the area of)the parent</p>
<p>explorative</p>
<p>exploitative</p>
<p>In SGA:</p>
<p>only \_\_\_\_\_\_ can combine information from two parents, whereas only \_\_\_\_\_\_ can introduce new information</p>
<p>crossover</p>
<p>mutation</p>
<p>An alternative binary representation is "Gray Coding". What is Gray coding, and why is it prefered for GAs?</p>
<p>Gray code is a system of binary representation in which thehamming distance between any conscecutive numbers is always 1.</p>
<p>Using Gray Coding in genotype representation means that small changes in the genotype (binary form)causes small changes in the phenotype (non-binary form). This results in "smoother" genotype-phenotype mapping & speeds up the GA</p>
<p>What are other possible representations are possible for phenotypes?</p>
<p>- Integers</p>
<p>- Real-valued or floating-point numbers</p>
<p>- Permutations</p>
<p>Crossover and mutation implementation depends on the representation</p>
<p>What are the characteristics ofGenerational Genetic Algorithms (GGAs)?</p>
<p>- Each individual survives for exactly one generation</p>
<p>- The entire set of parents is replaced by the offspring</p>
<p>What is the Steady-State Genetic Algorithm (SSGA) model?</p>
<p>- Only part of the population is replaced by the offspring</p>
<p>- Usually only one member of population is replaced</p>
<p>- The proportion of the population replaced is called the "Generational Gap"</p>
<p>- Generational Gap is 1 for GGA and 1/pop_size for SSGA</p>
<p>In Genetic Algorithms, Selection can occur in two places. What are they?</p>
<p>- Selection from current generation to take part in mating (parent selection)</p>
<p>- Selection from parents + offspring to go into next generation (survivor selection)</p>
<p>In GA parent selection, what is Fitness-Proportionate Selection (FPS)?</p>
<p>What is the expected number of copies of an individual being selected `i` in FPS?</p>
<p>FPS is when the probability of parent `i` selection is:</p>
<p>(fitness of `i`)/ (sum of all fitnesses)</p>
<p>The expected number of coppies of an individual `i` is:</p>
<p>(fitness of `i`) / (average fitness)</p>
<p>Fitness-Proportionate Selection can be implemented using 2 methods:</p>
<p>Roulette Wheel Algorithm, andBaker's Stochastic Universal Sampling Algorithm</p>
<p>Describe both of these methods and how they work</p>
Routlette wheel Algorithm:
- Given a probability distribution, spin a 1-armed wheel n times to make n selections
- There are no guarantees on the actual value of n_i (it is random)
Baker’s Stochastic Universal Sampling Algorithm:
- n evenly spaced arms on a wheel and spin once
- Guaranteed as floor(E[n_i]) < n_i < ceil(E[n_i])
- E[n_i] is the expected number of copies of n_i in the selection
What are common pitfalls for Fitness-Proportionate Selection (FPS)?
- Premature convergence: One highly fit member can rapidly take over if the rest of the population is much less fit
- No selection pressure at the end of runs when fitnesses are similar
- Function Transposition
One alternative to FPS is Rank-Based Selection. Describe this selection algorithm
Rank based selection:
- Selection probabilities is based on relative fitness (not absolute fitness)
- Population is ranked according to fitness, and selection is based on which is the fittest
- There is a sorting overhead involved in this, but is usually negligible when compared to the fitness evaluation time
One alternative to FPS is Tournament Selection. Describe this selection algorithm
- Pick
kmembers at random and then select the best of these - Repeat to select more individuals
- Uses an external fitness function
- Eliminates the bottleneck of global population statistics
What does Elitism mean in FPS? Characteristics?
- Always keep best individuals (at least one copy of the fittest solution so far)
it is widely used in both population models (GGA and SSA)
What are the 2 GA population models?
SSGA - Steady State Genetic Algorithm
GGA - General Genetic Algorithm
What does GENITOR mean in FPS? Characteristics?
- Delete Worst
- Can lead to rapid improvement and potential premature convergence
- Used with large populations, or “no duplicates” policy
In GA, there are two approaches to survivor selection. What are they?
Age-Based Selection
Fitness-Based Selection
