Genetic Algorithms

Question 1

Alteration (Crossover)

Answer 1

the random exchange of 2 parents’ chromosomes during reproduction, resulting in offspring that have some traits of each parent

Question 2

Alteration requires

Answer 2

genetic diversity to ensure sufficiently varied offspring

Question 3

Mutation

Answer 3

occurence of errors during the process of copying chromosome, can be harmful, beneficial, or neither

Question 4

Natural Selection

Answer 4

the fittest survive in a competitive environment resulting in better organisms; better traits survive longer, better chance to reproduce; species improves as whole as better traits outnumber

Question 5

representation of individuals for genetic algorithms

Answer 5

solutions represented as a vector of values

Question 6

genetic algorithm

Answer 6

create initial population; evaluate fitness of each individual, check if termination criteria met; select parents according to fitness; recombine parents to generate offspring; mutate offspring; replace pop with new offspring

Question 7

Initialization of population issues

Answer 7

size and diversity of initial population

Question 8

A lack of diversity for initial population leads to what?

Answer 8

Premature convergence to a non-optimal solution

Question 9

How is a diverse initial population generated?

Answer 9

uniformly random; grid initialization; non-clustering; local optimization

Question 10

uniformly random

Answer 10

generate individuals randomly from a solution space with uniform distribution

Question 11

grid initialization

Answer 11

choose individuals at regular “intervals” from the solution space

Question 12

non-clustering

Answer 12

require individuals to be a predefined “distance” away from those already in the population

Question 13

local optimization

Answer 13

find an initial population of local optima; does’t enforce diversity but guarantees solution to be no worse

Question 14

evaluation ranks the individuals by what?

Answer 14

fitness measure

Question 15

fitness measure

Answer 15

corresponds with the quality of the individual solutions

Question 16

what happens if selection is too dependent on evalution/fitness function?

Answer 16

like greedy search, non-optimal solution may be found

Question 17

what happens if selection is not dependent enough on evaluation/fitness function?

Answer 17

may not converge to a solution at all

Question 18

2 types of proportional fitness selection techniques?

Answer 18

rank selection; proportional selection

Question 19

rank selection

Answer 19

individual selected with a probability proportional to its rank in population, sorted by fitness

Question 20

proportional selection

Answer 20

individual selected with a probability (given fitness values, sum fitnesses, determine probabilities)

Question 21

tournament selection

Answer 21

randomly select two individuals and the one with the highest rank goes on and reproduces; only care about one with higher rank, puts upper and lower bound on the chances that any individual has to reproduce for the next generation

Question 22

crowding

Answer 22

problem with selection - when individuals that are most fit quickly reproduce so that very large percentage of population looks similar; reduces diversity; may hinder long-run progress of the algorithm

Question 23

crossover

Answer 23

pick pairs of individuals as parents and randomly swap their segments (parameters: crossover rate, number of crossover points, positions of the crossover points)

Question 24

1-point crossover

Answer 24

pick a dividing point in the parents’ vectors and swap the segments

Question 25

N-point crossover

Answer 25

pick n dividing points in the parents’ vectors and splice together alternating segments

Question 26

Uniform crossover

Answer 26

the value of each element of the vector is randomly chosen from the values in the corresponding elements of the two parents

Question 27

Mutation

Answer 27

randomly change an individual; parameters = mutation rate, size of mutation

Question 28

Genetic algorithm

Answer 28

have an inition population; let p[i] be fitness probabilities, randomly pick 2 parents with probabilites, randomly select 1 crossover point, swap strings of parents 1 and 2 to generate children, randomly mutate each posision in child with small prob; new generation replaces old

Question 29

Problem of Local Maxima

Answer 29

individuals get stuck at pretty good but not optimal solutions