# Automatic Time Table Generation Agent (Genetic Algorithm) # A Gradio app that demonstrates timetable generation using a genetic algorithm. import random import copy from dataclasses import dataclass from typing import List, Tuple, Dict import gradio as gr # --- Problem definition (simple, configurable) --- DAYS = ["Mon", "Tue", "Wed", "Thu", "Fri"] SLOTS_PER_DAY = 6 @dataclass class Course: id: str teacher: str size: int @dataclass class Room: id: str capacity: int # Example default dataset DEFAULT_COURSES = [Course(f"C{i+1}", f"T{(i%4)+1}", random.choice([20,30,40])) for i in range(6)] DEFAULT_ROOMS = [Room(f"R{i+1}", cap) for i,cap in enumerate([30,40,50,35,25])] # Genome representation: list of assignments where each assignment = (course_id, day, slot, room_id) def random_assignment(courses: List[Course], rooms: List[Room]) -> List[Tuple[str,int,int,str]]: assignments = [] for c in courses: day = random.randrange(len(DAYS)) slot = random.randrange(SLOTS_PER_DAY) room = random.choice(rooms).id assignments.append((c.id, day, slot, room)) return assignments # Fitness function: penalize room capacity violations and teacher conflicts def fitness(genome: List[Tuple[str,int,int,str]], courses: List[Course], rooms: List[Room]) -> int: score = 0 room_caps = {r.id: r.capacity for r in rooms} teacher_map = {c.id: c.teacher for c in courses} course_size = {c.id: c.size for c in courses} # Room capacity penalty for course_id, day, slot, room_id in genome: if course_size.get(course_id, 0) > room_caps.get(room_id, 0): score -= (course_size[course_id] - room_caps.get(room_id, 0)) # Teacher conflict penalty (same teacher at same day+slot) schedule_map = {} for course_id, day, slot, room_id in genome: teacher = teacher_map.get(course_id, None) if teacher is None: continue key = (teacher, day, slot) if key in schedule_map: score -= 50 else: schedule_map[key] = course_id # Room double-booking penalty room_map = {} for course_id, day, slot, room_id in genome: key = (room_id, day, slot) if key in room_map: score -= 40 else: room_map[key] = course_id # Soft reward for spreading same teacher across more days teacher_days = {} for course_id, day, slot, room_id in genome: teacher = teacher_map.get(course_id, None) if teacher: teacher_days.setdefault(teacher, set()).add(day) for t, days in teacher_days.items(): score += len(days) return score # GA operators def crossover(a: List[Tuple], b: List[Tuple]) -> List[Tuple]: if len(a) < 2: return copy.deepcopy(a) idx = random.randrange(1, len(a)) child = a[:idx] + b[idx:] return child def mutate(genome: List[Tuple], courses: List[Course], rooms: List[Room], mutation_rate=0.1) -> List[Tuple]: new = copy.deepcopy(genome) for i in range(len(new)): if random.random() < mutation_rate: course_id, day, slot, room = new[i] if random.random() < 0.33: day = random.randrange(len(DAYS)) if random.random() < 0.33: slot = random.randrange(SLOTS_PER_DAY) if random.random() < 0.5: room = random.choice(rooms).id new[i] = (course_id, day, slot, room) return new def tournament_select(scored, k=5): participants = random.sample(scored, min(k, len(scored))) participants.sort(key=lambda x: x[0], reverse=True) return copy.deepcopy(participants[0][1]) def run_ga(courses: List[Course], rooms: List[Room], pop_size=200, generations=200, elite_frac=0.05, mutation_rate=0.1): # initialize population population = [random_assignment(courses, rooms) for _ in range(pop_size)] best = None for gen in range(generations): scored = [(fitness(ind, courses, rooms), ind) for ind in population] scored.sort(key=lambda x: x[0], reverse=True) if best is None or scored[0][0] > best[0]: best = (scored[0][0], copy.deepcopy(scored[0][1])) # selection (elitism + tournament) elites_count = max(1, int(pop_size * elite_frac)) elites = [copy.deepcopy(ind) for _, ind in scored[:elites_count]] new_pop = elites.copy() while len(new_pop) < pop_size: a = tournament_select(scored) b = tournament_select(scored) child = crossover(a, b) child = mutate(child, courses, rooms, mutation_rate) new_pop.append(child) population = new_pop return best # Helper to pretty-print timetable def format_timetable(genome: List[Tuple[str,int,int,str]]) -> str: table = { (d,s): [] for d in range(len(DAYS)) for s in range(SLOTS_PER_DAY)} for course_id, day, slot, room_id in genome: table[(day,slot)].append(f"{course_id}({room_id})") lines = [] hdr = ["Slot\\Day"] + DAYS lines.append("\t".join(hdr)) for s in range(SLOTS_PER_DAY): row = [f"S{s+1}"] for d in range(len(DAYS)): items = table[(d,s)] row.append(", ".join(items) if items else "-") lines.append("\t".join(row)) return "\n".join(lines) # Parsing helpers def parse_courses(text: str) -> List[Course]: # expects lines like: C1,T1,30 lines = [l.strip() for l in text.splitlines() if l.strip()] out = [] for ln in lines: parts = [p.strip() for p in ln.split(",")] if len(parts) >= 3: try: out.append(Course(parts[0], parts[1], int(parts[2]))) except ValueError: # skip malformed sizes continue return out def parse_rooms(text: str) -> List[Room]: # expects lines like: R1,40 lines = [l.strip() for l in text.splitlines() if l.strip()] out = [] for ln in lines: parts = [p.strip() for p in ln.split(",")] if len(parts) >= 2: try: out.append(Room(parts[0], int(parts[1]))) except ValueError: continue return out def generate_handler(courses_text, rooms_text, pop_size, generations, mutation_rate): courses = parse_courses(courses_text) rooms = parse_rooms(rooms_text) if not courses: courses = DEFAULT_COURSES if not rooms: rooms = DEFAULT_ROOMS best = run_ga(courses, rooms, int(pop_size), int(generations), elite_frac=0.05, mutation_rate=float(mutation_rate)) score, genome = best timetable = format_timetable(genome) assignments = "\n".join([f"{c}@{DAYS[d]} S{slot+1} in {r}" for c,d,slot,r in genome]) return f"Fitness: {score}\n\nTimetable:\n{timetable}", assignments # Gradio UI with gr.Blocks(title="Automatic Time Table Generation Agent (Genetic Algorithm)") as demo: gr.Markdown("# Automatic Time Table Generation Agent (Genetic Algorithm)") with gr.Row(): with gr.Column(scale=2): courses_input = gr.Textbox(lines=8, label="Courses (format: id,teacher,size)", value='\n'.join([f"{c.id},{c.teacher},{c.size}" for c in DEFAULT_COURSES])) rooms_input = gr.Textbox(lines=6, label="Rooms (format: id,capacity)", value='\n'.join([f"{r.id},{r.capacity}" for r in DEFAULT_ROOMS])) pop_size = gr.Slider(10, 500, value=200, step=10, label="Population Size") generations = gr.Slider(10, 1000, value=200, step=10, label="Generations") mutation_rate = gr.Slider(0.0, 1.0, value=0.1, step=0.01, label="Mutation Rate") run_btn = gr.Button("Generate Timetable") with gr.Column(scale=1): out_text = gr.Textbox(lines=20, label="Result (timetable)") out_assign = gr.Textbox(lines=12, label="Assignments (compact)") run_btn.click(generate_handler, inputs=[courses_input, rooms_input, pop_size, generations, mutation_rate], outputs=[out_text, out_assign]) if __name__ == "__main__": demo.launch(server_name="0.0.0.0", server_port=7860)