# Q6(a) Genetic algorithm for four-city TSP [10]

Subject: Intelligent Systems II

Exam: TEE

Reader: https://deep-learning-study-room.vercel.app/is2/#tee/papers/paper-2024-reexam/q6a

Canonical: https://deep-learning-study-room.vercel.app/read/is2/tee/papers/paper-2024-reexam--q6a/

Actual historical paper ·100 marks attempted /140 offered · Q1 compulsory + any four of Q2–Q7. Source defects and solution assumptions are explicitly identified.

**Question. Q6(a)** [10 marks · 2024-06-25]

For a genetic algorithm applied to a4-city TSP: (1) cite how to initialize a population; (2) explain fitness calculation; (3) describe common crossover and mutation operators.

### Answer

**Representation.** A chromosome is a permutation of the cities. [A, B, C, D] means A→B→C→D→A; the return edge is implied. Each city appears exactly once before returning.

##### Step 1. Initialize distinct valid tours

Example population:[A, B, C, D], [A, C, B, D], [A, B, D, C], [A, D, B, C]. Fix A at the start to avoid counting rotations as different encodings. Randomly shuffle the other cities or include a heuristic tour; check feasibility.

##### Step 2. Evaluate route length and fitness



$$
L=d_{AB}+d_{BC}+d_{CD}+d_{DA},\qquad fitness=1/L\quad(L>0)
$$



For an illustrative symmetric distance table AB 10, AC 4, AD 3, BC 1, BD 2, CD 1: tour A–B–C–D–A has length 15 and fitness 1/15; A–C–B–D–A has length 10 and fitness 1/10. The shorter tour has larger inverse-distance fitness. These sample costs illustrate the method; the question itself supplies no cost table.

##### Step 3. Use permutation-preserving crossover

Order crossover (OX) copies a segment from one parent, then fills empty positions with cities from the other parent in cyclic order, skipping copied cities. Example P1=A B C D, P2=C D A B. Copy P1 positions 2–3(B C), then scan P2 from position 4:B(skip), C(skip), D, A. Fill child positions 4 then 1 to obtain A B C D. A different cut or parent can yield a different valid tour. Partially matched crossover (PMX) uses a mapping to resolve duplicates. Ordinary bit-string crossover can give repeated/missing cities and is not automatically valid.

##### Step 4. Mutate without losing cities

Swap: A B C D→A D C B by swapping B, D. Inversion: A | B C D→A | D C B. Insertion: remove D from A B C D and insert after A→A D B C. These preserve city uniqueness. Evaluate every child again because a valid route may still be longer.

##### Step 5. Select, replace and stop

Choose parents favoring shorter tours, apply crossover/mutation, evaluate offspring, retain a fixed-size population and optionally preserve the best tour (elitism). Stop after a generation limit or lack of improvement. Return the best observed tour, without claiming a guaranteed optimum unless all feasible tours have been checked.