GA Practice Questions

[Eamonn]

10th March Post your answers here. link to slides https://docs.google.com/presentation/d/1TSEiKMIXNg7J3upIVnvKNcbQ44QFFXQSTIlw7U_PQyU/edit#slide=id.p

[ArinN_]

a) Describe the 4 listed approaches to Selection.
– roulette wheel selection
– stochastic universal sampling
– tournament selection
– truncation selection

b) Discuss the characteristics of a good selection approach
– Doesn’t lead to premature convergence and doesn’t lead to local minima convergence
– Meets with the situation (For example, Truncation selection isn’t popular unless the population size is large)
– Assures genetic diversity

[girwan]

Describe the 4 listed approaches to Selection:

Roulette wheel: In a roulette wheel selection, the circular wheel is divided and allocated to each potential candidate in proportion to their fitness level. A fixed point is chosen on the wheel circumference as shown and the wheel is rotated. The region of the wheel which comes in front of the fixed point is chosen as the parent. For the second parent, the same process is repeated. This ensures even the weakest candidates have a chance of entering into the mating pool.

Stochastic universal sampling: It similar to roulette wheel selection where a circular wheel is divided and allocated to each potential candidate in proportion to their fitness level, however instead of having just one fixed point on the wheel, we have multiple fixed points. Therefore, all the parents are chosen in just one spin of the wheel.

Tournament selection: N number of individuals are selected from the population at random and they are paired together, the best out of the two are selected to become a parent. The same process is repeated for selecting the next parent. Tournament Selection can even work with negative fitness values unlike fitness proportionale selections and also gives the opportunity for lower ranked solutions to be chosen for recombination.

Truncation selection:
In this sort of selection, the population is sorted by fitness, and then a certain percentage of the bottom are dropped. The remaining solutions at the top are then selected. It is the most simple method of selection but it could lead to a lack of diversity without a mutation operator.

Discuss the characteristics of a good selection approach.

Diversity: A lack of diversity can lead to a premature convergence and the optimal solution cannot be achieved.
Quality of solutions: The quality of solutions needs improve over every iteration of the genetic algorithm. If it doesnt it can be said that either the optimal solution has been reached or it has prematurely converged.
Chance for everyone: No solution should have no probability of getting into the mating pool. Doing so would lead to a better selection but a loss of diversity over the long run

[Sang]

Describe the 4 listed approaches to Selection.
– Fitness proportionate selection: Fitness proportionate selection, also known as roulette wheel selection, is a genetic operator used in genetic algorithms for selecting potentially useful solutions for recombination. Usually, a proportion of the wheel is assigned to each of the possible selections based on their fitness value. In this method, an individual can become a parent with a probability that is proportional to its fitness. Therefore, fitter individuals have a higher chance of reproduction.
– Stochastic universal sampling: Stochastic universal sampling is a technique used in genetic algorithm for selecting potentially useful solutions for recombination.
It is said to be a development of fitness proportionate selection which exhibits no bias and minimal spread. Where fitness proportionate selection chooses several solutions from the population by repeated random sampling, stochastic universal sampling uses a single random value to sample all of the solutions by choosing them at evenly spaced intervals which gives weaker members of the population a chance to be chosen.
– Tournament sampling: Tournament selection is a method of selecting an individual from a population of individuals in a genetic algorithm.
Tournament selection involves running several tournaments among a few individuals chosen at random from the population. The winner of each tournament is selected for crossover.
– Truncation selection: Truncation selection is a selection method used in genetic algorithm to select potential candidate solutions for recombination modeled after the breeding method. In truncation selection, the candidate solutions are ordered by fitness, and some proportion of the fittest individuals are selected and reproduced.

[ArinN_]

a) List the steps in a GA. Suggest use pseudo code to show the steps, the iterative nature and exit criteria

Define algorithm {
* Choose an initial population of individuals: P(0)
* Evaluate the fitness of all individuals of P(0)
* Choose a maximum number of generations: t_max
* Loop while not satisfied and t < t_max:
– t = t + 1;
– Select parents for offspring production
– Apply reproduction and mutation operators
– Create a new population of survivors: P(t)
– Evaluate P(t) <– #Must meet with exit criteria#
* end loop
* Return the best individual of P(t)
}

[joshua7]

a) Describe the 4 listed approaches to Selection.
– roulette wheel selection is when we spin the roulette to randomly select the parent
– stochastic universal sampling is very similar to the roulette wheel selection, only difference is that there are multiple fixed points instead of one
– tournament selection is when we compare two different randomly chosen parent at a time, whichever is better in terms of fitness or survival, it goes to the next round until one remains
– truncation selection is a method of selective breeding as we select animals/plant traits to be bred for the next generation

b) Discuss the characteristics of a good selection approach
– Is able to reject a large number of under-qualified candidates, such as extremely low fitness levels
– It continuously enhances examining pass rates, efficiency, accuracy, and fairness
– Is able to create diversity
– It meets the requirement and situation to assure accuracy and efficiency

[girwan]

Algorithm for GA:
Generate initial population(P0)
Find fitness level through fitness function
NumGen = k
Termination_condition = False
loop while t<numGen and termination_condition = False
apply selection method
crossover operator
mutation operator
create the new generation
evaluate fitness function of new generation
t = t + 1
termination condition met?
end loop
return optimal solution

[Author]

Posts