Spaces:
Sleeping
Sleeping
| # 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 | |
| class Course: | |
| id: str | |
| teacher: str | |
| size: int | |
| 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) | |