The idea of using population based methods to solve optimization problems __________ .
is only to exploit parallel search like in Iterative Hill Climbing
is to hope that one of the parallel Simulated Annealing searches will find the solution
is to go beyond parallelism and exploit interaction between members of the population
is to exploit the diversity in a population of candidates and try mixing up the candidate solutions
Which of the following are true? Mark all correct answers
Genetic Algorithms work with a population of problem solving agents
Genetic Algorithms work with a population of candidate solutions
Ant Colony Optimization works with a population of problem solving agents
Ant Colony Optimization works with a population of candidate solutions
Genetic Algorithms work best when __________ .
there is a large population of diverse candidates
there is a large population of similar candidates
there is a small population of diverse candidates
there is a small population of similar candidates
Darwin’s theory of natural selection can be seen as
a process of selecting the best leaders based on their education
a process of selecting the best leaders based on their ability to tell lies
a process to design life forms that evolve and improve over generations
a process where members of a population compete for survival
Which one of the following completes the quote from Paul Valery in the context of Genetic Algorithms? “It takes two to invent anything. The one makes up combinations, _________________”
the other creates the permutations
the other chooses
the other sorts the components
the other randomizes them
What is the role an individual ant plays in the Ant Colony Algorithm?
It conveys the messages from the queen to the soldiers
It constructs a candidate solution using divide and conquer approach
It constructs a candidate solution using a greedy local stochastic search approach
It guards the entrance of the ant colony
Consider chromosomes made of 5-bit binary strings and a fitness function f(a,b,c,d,e) that is a square of (a+2b+3c+4d+5e), where “abcde” is a 5-bit chromosome. An initial population is shown in the table.
Fill in the missing values in the table. Assuming that the actual candidates selected are proportional to the expected number, what are the values of A, B, C, and D? They represent how many copies of the candidate are selected, and will be in the range of 0 to 4.
Enter the values of A,B,C,D as a comma separated list.
DO NOT ENTER SPACE, TAB, DOT, BRACKET OR UNWANTED CHARACTERS.
Answer format: 1,2,3,4
In the previous question, the instances selected for crossover are _________ .
00011, 11000, 00110, 01100
00011, 00011, 00110, 01100
00011, 11000, 01100, 01100
00011, 11000, 00110, 00110
GROUP 2
A tour of 12 cities is shown in the figure below, the edges are bidirectional. Use A,B,C,D,E,F,G,H,I,J,K,L as reference sequence (index sequence) for preparing ordinal and adjacency representations.
Select the valid path representations of the tour.
C,H,A,D,L,I,K,E,B,G,J,F
B,G,C,H,A,D,L,I,K,E,J,F
B,G,J,F,C,H,A,D,L,I,K,E
C,H,A,D,L,I,K,E,J,F,B,G
The valid adjacency representations of the tour are _________ .
D,G,H,L,J,B,C,A,K,F,E,I
D,G,H,L,B,C,J,A,K,F,E,I
H,E,F,A,K,J,B,C,L,G,I,D
H,F,G,A,K,J,B,C,L,E,I,D
Select the ordinal representations of the valid path representations listed in Q9.
8,7,5,9,6,4,6,2,1,2,2,1
2,6,8,5,2,4,1,1,4,2,2,1
8,7,5,9,6,4,1,5,3,2,1,1
3,7,1,2,8,5,6,2,1,2,2,1
Path representations of two tours are given below. Generate two offspring using Partially Mapped Crossover, use the locations from 5 to 8 as the mapping segment.
P1: C,H,A,D,L,I,K,E,B,G,J,F
P2: H,G,E,L,I,D,A,K,F,C,B,J
Enter one of the child tours in the text box.
DO NOT ENTER SPACE, TAB, DOT, BRACKET OR UNWANTED CHARACTERS.
Path representations of two tours are given below. Generate two offspring using Order Crossover, use locations from 5 to 8 as the mapping segment.
P1: C,H,A,D,L,I,K,E,B,G,J,F
P2: H,G,E,L,I,D,A,K,F,C,B,J
In the child tour, place the mapping segment in the middle.
For example, C1 = ?,?,?,?,L,I,K,E,?,?,?,?
Enter one of the child tours in the text box.
DO NOT ENTER SPACE, TAB, DOT, BRACKET OR UNWANTED CHARACTERS.
Path representations of two tours are given below. Generate the two offspring using Cycle Crossover.
P1: C,H,A,D,L,I,K,E,B,G,J,F
P2: H,G,E,L,I,D,A,K,F,C,B,J
Enter one of the child tours in the text box.
DO NOT ENTER SPACE, TAB, DOT, BRACKET OR UNWANTED CHARACTERS.
Path representations of two tours are given below. Compute the ordinal representations of the parent tours and use single point crossover (cut in the middle) to generate the two offspring.
P1: C,H,A,D,L,I,K,E,B,G,J,F
P2: H,G,E,L,I,D,A,K,F,C,B,J
Enter one of the child tours in the text box, use ordinal representation.
DO NOT ENTER SPACE, TAB, DOT, BRACKET OR UNWANTED CHARACTERS.
GROUP 3
The classical single point crossover operator (cut two chromosomes and swap the pieces) used in genetic algorithms can be applied to _________ .
the path representation
the adjacency representation
the ordinal representation
all of the above
What is the tour generated by Greedy Heuristic? Use the edge costs given in the table below. Enter the path representation of the tour starting from city D.
Enter a comma separated list of city names.
DO NOT ENTER SPACE, TAB, DOT, BRACKET OR UNWANTED CHARACTERS.
Use the distance matrix in Q17. Starting from city D, what is the tour generated by the Nearest Neighbour Heuristic? Enter the path representation of the tour starting from city D.
Enter a comma separated list of city names.
DO NOT ENTER SPACE, TAB, DOT, BRACKET OR UNWANTED CHARACTERS.
Use the distance matrix in Q17. Construct the savings tour using D as the base city. Enter the path representation of the savings tour starting from city D.
Enter a comma separated list of city names.
DO NOT ENTER SPACE, TAB, DOT, BRACKET OR UNWANTED CHARACTERS.
With reference to questions 17, 18 and 19, which of the following tours is the cheapest?
The tour generated by the Greedy Heuristic.
The tour generated by the Nearest Neighbour Heuristic.
The tour generated by the Savings Heuristic.