Indian Institute of Technology Madras
BS Degree Programme · Examination & Study Paper
AI: Search Methods for Problem Solving
Genetic algorithms & tour edits
Examination Instructions & Guidelines
- Solve on notebook/paper first before checking solutions.
- MCQ: Exactly 1 option is correct. Negative marking applies.
- MSQ: One or more options correct. Select all to score.
- NAT: Numerical response. No negative marking.
- Scientific calculator allowed for all calculations.
- Official answer key is sealed at the end of this sheet.
Read the passage below, then answer Q1–Q4
Genetic Algorithm
Answer the given subquestions.
Q1MCQ1 Mark·Choose one optionConvert the path representation A,C,K,F,B,H,G,I,D,L,E,J to ordinal representation. Use A,B,C,...,L as the reference (index) sequence.
- A1,2,9,4,1,4,3,3,1,3,1,1
- B9,4,10,4,2,1,1,5,3,3,1,1
- C1,2,9,8,1,3,3,4,1,3,1,1
- D3,10,8,3,2,2,5,1,3,3,2,1
- Q2MSQ1 Mark·Choose all correct options
Path representations of two tours are given below. Generate offspring using Cycle Crossover. P1: I,D,L,E,J,A,C,K,F,B,H,G P2: C,K,I,D,B,E,J,A,H,L,G,F Select the child tours.
- AI,K,L,D,J,E,C,A,F,B,H,G
- BC,D,I,E,B,A,J,K,H,L,G,F
- CI,D,L,K,B,A,E,H,C,J,F,G
- DA,L,I,E,J,D,C,K,H,F,G,B
- Q3MCQ1 Mark·Choose one option
Single-point crossover can be used with __________ .
- AAdjacency Representation.
- BPath Representation
- COrdinal Representation
- DAll of these
- Q4NAT1 Mark·Write the number
For the case of 3-edge exchange, how many child tours are possible? Enter the number of child tours in the text box. (Assume that no pair of edges from the selected 3 edges share any city in common.) Enter an integer. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: 17
Your answer: