Artificial Intelligence Assignment 1

by Jake O Grady & Chukwuma George Anayo-Ezikeoha

Overview

This project implements Genetic Algorithm (GA) to solve a simplified exam timetabling problem. The objective is to assign exams to timeslots while minimizing student conflicts and improving schedule quality.

The algorithm evolves a population of candidate timetables over multiple generations using selection, crossover, mutation, and elitism.

Code Structure

The project is structured around a single main GA pipeline, supported by helper utility functions.

1. Input Handling

read_instance(filename)

• Reads the problem instance file.
• Extracts:
  • No. of exams
  • No. of timeslots
  • Size of population

2. Population Initialization

initialize_population(num_exams, num_schedules)

• Generates the initial population.

random_init(num_exams)

• Creates a random timetable.
• Each exams is assigned a random timeslot.

Each individual is represented as: [timeslot_exam0, timeslot_exam1, ..., timeslot_examN]

3. Fitness Evaluation

evaluate_schedule(student, solution)

• Checks:
  • Hard constraint violations (same timeslot exams for a student)
  • Soft constraint violations (consecutive exams)

evaluate_fitness(students, solution)

• Computes fitness with hard and soft constraint violation penalty weights.

4. Selection

`elitism_selection(...)'

• Propagates best individuals to next generation.

select_parents(...)

• Combines tournament selection with elitism to create next generation

5. Genetic Operators

crossover(parent1, parent2)

• Uniform crossover implementation

mutate(solution, students)

• Mutates chromosomes in such a way as to improve diversity while reducing number of conflicts.

adaptive_mutation_rate(gen)

• Mutation rate decreases over generations.
• Allows for proper exploration of search space and refinement of later generations.

6. Diversity Control

reinitialize_population_bottom(population, num_exams)

• Reinitializes the bottom portion of the population.
• Triggered when fitness stagnates.

7. Main GA Loop

run_ga()

The main pipeline:

1. Read instance data
2. Initialize population
3. Evaluate fitness
4. Repeat for NUM_GENERATIONS:
   • Selection
   • Crossover
   • Mutation
   • Fitness evaluation
   • Track best and average fitness
   • Detect stagnation
5. Output best solution
6. Plot fitness progression

External Utilities (utils.py)

The following helper functions are imported:

• plot_fitness_generation
• print_best_solution
• print_alternative_solutions
• print_student_timetables

These handle visualization and formatted output.

Key Parameters

• HARD_PENALTY
• SOFT_PENALTY
• CROSSOVER_RATE
• ELITE_COUNT
• NUM_GENERATIONS
• TOURNAMENT_SIZE

These are adjusted to study algorithmic variation in performance.

Runnable Script

Look run_ga_params.sh to test performance of crossover rate and tournament size.