Intelligent Systems II · TEE · papers
Q1(b) Genetic algorithm applications [5]
Final / re-examination · 28 Apr 2025
Actual historical paper ·100 marks attempted /140 offered · Q1 compulsory + any four of Q2–Q7. Source defects and solution assumptions are explicitly identified.
List the applications of genetic algorithm and explain any one application in detail.
Answer
Genetic algorithm (GA) is a population-based search method that evolves encoded candidate solutions using fitness evaluation, selection, crossover and mutation.
- Job-shop scheduling and timetable construction.
- Vehicle routing and travelling-salesman-type optimization.
- Feature selection and hyperparameter search in machine learning.
- Engineering design, such as selecting dimensions subject to strength or cost constraints.
- Resource allocation and placement problems.
Detailed application: examination timetable
| Stage | How it is used |
|---|---|
| Representation | A chromosome assigns a time slot and room to every examination. A gene identifies one exam's assignment. |
| Fitness | Penalize student clashes, room-capacity violations and unavailable slots; among feasible schedules, reward spread-out exams and efficient room use. |
| Initial population | Create several different candidate timetables, using random assignments or constructive rules. |
| Selection | Prefer feasible and lower-penalty timetables while retaining diversity. |
| Crossover | Combine assignments from two parents; repair conflicts if the operator can violate feasibility. |
| Mutation | Move an exam to another permitted slot or swap compatible assignments. Recheck constraints. |
| Replacement / stopping | Keep useful candidates, often protecting the best feasible schedule; stop at a generation/time limit or sufficient improvement. |
Illustrative example: two exams sharing students cannot occupy the same slot. A candidate with that clash receives a strong penalty or is repaired before acceptance. This shows why fitness must reflect the actual constraints, not merely how many rooms are occupied.
Benefit: explores many combinations without exhaustively listing all timetables. Limitation: stochastic search can stagnate and does not guarantee a global optimum; poorly designed penalties can reward unusable schedules.