Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

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

What is the specialty of Simple Genetic Algorithms?

Emphasis on crossover

26

Describe the Simple Genetic Algorithm procedure in steps

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

What should the termination criteria be in SGA?

- Specified number of generations - A minimum threshold from optimal reached - No improvement is possible - Memory/time constraints

28

In SGA, a mapping is applied from the ______ domain to the ______ domain.

parameter
binary

29

Abstract representation of phenotype is called _______ or ________

chromosomes | genotype

30

in SGA, a ______ is a string in the binary domain.

0 and 1 represents the presence or absence of ______

The _____ of genes can be important

Genotype/Chromosome
Features
Order

31

The ______ is a lower-level (less abstracted) encoding of a ______

genotype
phenotype

32

How do you go from phenotype space to genotype space?
How about the other way around?

Phenotype -> Genotype: Encode into a binary string.

Genotype -> Phenotype: Decode binary string

33

What does the SGA reproduction cycle consist of?

- 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

34

What does mutation do to a binary represented genotype in SGA?

flips bits in order to randomly change the features of an individual

35

In SGA, parents are selected with a probability proportional to their ______

fitness

36

What is the main idea behind SGA selection?

Better individuals (who have higher fitness) get higher chance

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

Roulette wheel technique
- Assign each individual part of the roulette wheel to a normalized probability (they should all add up to 1)
- Spin the wheel "n" times to get "n" individuals

38

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

They are copied into the offspring unmodified

39

In SGA, the crossover probability is Pc. What is the typical range of Pc?

between 0.6 and 0.9

40

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

- Choose a random point on the two parents
- Split the Parents at this crossover point
- Create two children by exchanging tails (they become opposites of each other)

41

How does the n-point crossover (in the binary case) work?

- Choose `n` random crossover points

- Split along these points

- Glue parts, alternating between parents

- The 2 children become opposites of each other

42

How does the Uniform Crossover (binary) work?

- Treats genes independently

- Assigns "heads" to one parent, and "tails" to another

- Flips a coin for each gene (bit) of the first child

- Make an inverse copy which is the second child

- The 2 children are opposites

43

In SGA mutation, we alter each _____ independently with a probability Pm

gene/bit

44

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

between 1/pop_size and 1/chromosome_length.

Note that chromosome_length is the same as genotype_length

45

What is the motivation behind crossover and mutation in SGA?

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

In SGA:

Crossover is _______, it makes a big jump into an area somewhere between the 2 parent areas

Mutation is _______, it creates random small diversions, thereby staying near (in the area of) the parent

explorative

exploitative

47

In SGA:

only ______ can combine information from two parents, whereas only ______ can introduce new information

crossover

mutation

48

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

Gray code is a system of binary representation in which the hamming distance between any conscecutive numbers is always 1.

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 

49

What are other possible representations are possible for phenotypes?

- Integers

- Real-valued or floating-point numbers

- Permutations

Crossover and mutation implementation depends on the representation

50

What are the characteristics of Generational Genetic Algorithms (GGAs)?

- Each individual survives for exactly one generation

- The entire set of parents is replaced by the offspring

51

What is the Steady-State Genetic Algorithm (SSGA) model?

- Only part of the population is replaced by the offspring

- Usually only one member of population is replaced

- The proportion of the population replaced is called the "Generational Gap"

- Generational Gap is 1 for GGA and 1/pop_size for SSGA

52

In Genetic Algorithms, Selection can occur in two places. What are they?

- Selection from current generation to take part in mating (parent selection)

- Selection from parents + offspring to go into next generation (survivor selection)

53

In GA parent selection, what is Fitness-Proportionate Selection (FPS)?

What is the expected number of copies of an individual being selected `i` in FPS?

FPS is when the probability of parent `i` selection is:

(fitness of `i`) / (sum of all fitnesses)

The expected number of coppies of an individual `i` is:

(fitness of `i`) / (average fitness)

54

Fitness-Proportionate Selection can be implemented using 2 methods:

Roulette Wheel Algorithm, and Baker's Stochastic Universal Sampling Algorithm

Describe both of these methods and how they work

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
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
56
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
57
One alternative to FPS is Tournament Selection. Describe this selection algorithm
- 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
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)
59
What are the 2 GA population models?
SSGA - Steady State Genetic Algorithm | GGA - General Genetic Algorithm
60
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
61
In GA, there are two approaches to survivor selection. What are they?
Age-Based Selection | Fitness-Based Selection

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

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