Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

ECE 457A - Cooperative & Adaptive Algorithms > Week 6: Genetic Algorithms # 1 > Flashcards

Week 6: Genetic Algorithms # 1 Flashcards

1
Q

<p>What are the 2 classes/types of meta-heuristics</p>

A

Population-based methods & Trajectory Methods

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

<p>In population-based methods, what does a "population" refer to?</p>

A

<p>A group of solutions/states</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

<p>A population of individuals exists in an environment with limited \_\_\_\_\_\_\_</p>

A

<p>resources</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

<p></p>

<p></p>

<p>Individuals with higher fitness act as seeds for the next \_\_\_\_\_\_ of individuals through \_\_\_\_\_\_ and \_\_\_\_\_\_</p>

A

generation/population
recombination/mutation
mutation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

<p></p>

<p></p>

<p>New individuals have their \_\_\_\_\_ evaluated and compete for survival</p>

A

<p></p>

<p></p>

<p>fitness</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

<p></p>

<p></p>

<p>Over time \_\_\_\_\_ \_\_\_\_\_ causes a rise in the \_\_\_\_\_ of the population</p>

A

<p></p>

<p></p>

<p>Natural Selection
<br></br>Fitness</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

<p></p>

<p></p>

<p>What are stochastic algorithms?</p>

A

<p></p>

<p></p>

<p>algorithms that explicitly use randomness to find the next state - it is not determined by the current state</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

<p></p>

<p></p>

<p>Are Evolutionary Algorithms Deterministic or Stochastic?
<br></br>
<br></br>Are they population based? or Trajectory based?</p>

A

<p></p>

<p></p>

<p>Evolutionary Algorithms are stochastic, population-based algorithms</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

<p></p>

<p></p>

<p>Are Evolutionary Algorithms Deterministic or Stochastic?
<br></br>
<br></br>Are they population based? or Trajectory based?</p>

A

<p></p>

<p></p>

<p>Evolutionary Algorithms are stochastic, population-based algorithms</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

<p></p>

<p></p>

<p>What must a search algorithm do in order to perform better than a random search?</p>

A

<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>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

<p></p>

<p></p>

<p>What is Active information</p>

A

Measures the contribution of problem-specific information for successfully finding a target

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

<p></p>

<p></p>

<p>An algorithm does not create \_\_\_\_\_ information, it performs very valuable transformation of \_\_\_\_\_ information</p>

A

<p></p>

<p></p>

<p>new

| known</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

fitness

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

<p></p>

<p></p>

<p>For evolutionary algorithms, we require \_\_\_\_\_ information. This prevents the algorithm from behaving like a \_\_\_\_\_\_ search</p>

A

active

random

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

In Genetic Algorithms, the fitness of an individual is determined by the _______ traits.
These can be behavioural features, or physical features

A

phenotypic

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

in Genetic Algorithms, Selected individuals _______, passing their properties to the _______. Whereas other individuals die without _______, and their properties are ______

A

reproduce
offspring
mating/reproducing
discarded

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

<p></p>

<p></p>

<p>In Genetic Algorithms, small random variations called \_\_\_\_\_\_ occur in phenotypic traits during \_\_\_\_\_\_\_</p>

A

mutations

reproduction

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

In Genetic Algorithms, through mutations, new ______ of traits occur and get evaluated

A

combinations

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

<p></p>

<p></p>

<p>In Genetic Algorithms, for a given population, the basic operations are \_\_\_\_\_\_, \_\_\_\_\_\_ and \_\_\_\_\_\_</p>

A

<p></p>

<p></p>

<p>Selection
Reproduction
Mutation</p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

<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>

A

population
evolve
applying
stochastic (random)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

describe the flow of a Genetic Algorithm

A

<p></p>

<p></p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

<p></p>

<p>Genetic Algorithms evolve from one \_\_\_\_\_\_\_\_ to the next according to selection and the \_\_\_\_\_\_\_</p>

A

population/iteration

search operators

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

<p></p>

<p>What are the search operators in GA?</p>

A

Recombination (crossover)
Mutation
Selection

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

<p></p>

<p>What is the general flow for Simple Genetic Algorithm?</p>

A

<p></p>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

<p></p>

<p>What is the specialty of Simple Genetic Algorithms?</p>

A

<p></p>

<p>Emphasis on crossover</p>

26
Q

<p>Describe the Simple Genetic Algorithm procedure in steps</p>

A
  1. initialize population with random candidates
  2. Evaluate all individuals
  3. Check if termination criteria is met. Stop if it is.
  4. Select parents
  5. Apply crossover
  6. Mutate offspring
  7. Replace current generation
  8. Go back to step 3
27
Q

<p>What should the termination criteria be in SGA?</p>

A

<p>- Specified number of generations

- A minimum threshold from optimal reached
- No improvement is possible
- Memory/time constraints</p>

28
Q

<p>In SGA, a mapping is applied from the \_\_\_\_\_\_ domain to the \_\_\_\_\_\_ domain.</p>

A

<p>parameter
<br></br>binary</p>

29
Q

<p>Abstract representation of phenotype is called \_\_\_\_\_\_\_ or \_\_\_\_\_\_\_\_</p>

A

<p>chromosomes

| genotype</p>

30
Q

<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>

A

<p>Genotype/Chromosome
<br></br>Features
<br></br>Order</p>

31
Q

<p>The \_\_\_\_\_\_ is a lower-level (less abstracted) encoding of a \_\_\_\_\_\_</p>

A

<p>genotype
<br></br>phenotype</p>

32
Q

<p>How do you go from phenotype space to genotype space?
<br></br>How about the other way around?</p>

A

<p>Phenotype -> Genotype: Encode into a binary string.
<br></br>
<br></br>Genotype -> Phenotype: Decode binary string</p>

33
Q

<p>What does the SGA reproduction cycle consist of?</p>

A

<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>

34
Q

<p>What does mutation do to a binary represented genotype in SGA?</p>

A

<p>flips bits in order to randomly change the features of an individual</p>

35
Q

<p>In SGA, parents are selected with a probability proportional to their \_\_\_\_\_\_</p>

A

<p>fitness</p>

36
Q

<p>What is the main idea behind SGA selection?</p>

A

<p>Better individuals (who have higher fitness) get higher chance</p>

37
Q

In SGA, what is a common method for selecting the parents given the set of individuals and their fitnesses?

A

<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>

38
Q

<p>In SGA, if crossover does not happen, how are the 2 parents copied over into their children?</p>

A

<p>They are copied into the offspring unmodified</p>

39
Q

<p>In SGA, the crossover probability is Pc. What is the typical range of Pc?</p>

A

<p>between 0.6 and 0.9</p>

40
Q

<p>What is the 1-point crossover? Note that this is only for binary strings (genotypes)</p>

A

<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>

41
Q

<p>How doesthe n-point crossover (in the binary case) work?</p>

A

<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>

42
Q

<p>How doesthe Uniform Crossover (binary) work?</p>

A

<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>

43
Q

<p>In SGA mutation, we alter each \_\_\_\_\_ independently with a probability Pm</p>

A

<p>gene/bit</p>

44
Q

<p>In SGA mutation, Pm is the mutatuon rate. What is the typical range for this?</p>

A

<p>between 1/pop_size and 1/chromosome_length.</p>

<p>Note that chromosome_length is the same as genotype_length</p>

45
Q

<p>What is the motivation behind crossover and mutation in SGA?</p>

A

Crossover: Exploration, discovering promising areas in the search space
Mutation: Exploitation, optimizing within a promising area

46
Q

<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>

A

<p>explorative</p>

<p>exploitative</p>

47
Q

<p>In SGA:</p>

<p>only \_\_\_\_\_\_ can combine information from two parents, whereas only \_\_\_\_\_\_ can introduce new information</p>

A

<p>crossover</p>

<p>mutation</p>

48
Q

<p>An alternative binary representation is "Gray Coding". What is Gray coding, and why is it prefered for GAs?</p>

A

<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>

49
Q

<p>What are other possible representations are possible for phenotypes?</p>

A

<p>- Integers</p>

<p>- Real-valued or floating-point numbers</p>

<p>- Permutations</p>

<p>Crossover and mutation implementation depends on the representation</p>

50
Q

<p>What are the characteristics ofGenerational Genetic Algorithms (GGAs)?</p>

A

<p>- Each individual survives for exactly one generation</p>

<p>- The entire set of parents is replaced by the offspring</p>

51
Q

<p>What is the Steady-State Genetic Algorithm (SSGA) model?</p>

A

<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>

52
Q

<p>In Genetic Algorithms, Selection can occur in two places. What are they?</p>

A

<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>

53
Q

<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>

A

<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>

54
Q

<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>

A

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
55
Q

What are common pitfalls for Fitness-Proportionate Selection (FPS)?

A
  • 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
56
Q

One alternative to FPS is Rank-Based Selection. Describe this selection algorithm

A

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
57
Q

One alternative to FPS is Tournament Selection. Describe this selection algorithm

A
  • Pick k members 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
58
Q

What does Elitism mean in FPS? Characteristics?

A
  • 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)
59
Q

What are the 2 GA population models?

A

SSGA - Steady State Genetic Algorithm

GGA - General Genetic Algorithm

60
Q

What does GENITOR mean in FPS? Characteristics?

A
  • Delete Worst
  • Can lead to rapid improvement and potential premature convergence
  • Used with large populations, or “no duplicates” policy
61
Q

In GA, there are two approaches to survivor selection. What are they?

A

Age-Based Selection

Fitness-Based Selection

ECE 457A - Cooperative & Adaptive Algorithms (7 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions