Untitled

import random

def read_map_for_ga(filename):
    """Reads the map file and returns grid, starts, and goals for GA."""
    with open(filename, 'r') as f:
        n, m = map(int, f.readline().split())
        grid = []
        starts = {}
        goals = {}
        for i in range(n):
            row = f.readline().split()
            grid.append(row)
            for j in range(m):
                cell = row[j]
                if cell.startswith("S"):
                    starts[cell] = (i, j)
                elif cell.startswith("G"):
                    goals[cell] = (i, j)
    return grid, starts, goals

def manhattan_distance(point1, point2):
    x1, y1 = point1
    x2, y2 = point2
    return abs(x1 - x2) + abs(y1 - y2)

def calculate_route_time(start_position, target_names, goals):
    total_time = 0
    current_position = start_position
    for target in target_names:
        target_position = goals[target]
        total_time += manhattan_distance(current_position, target_position)
        current_position = target_position
    return total_time

def calculate_makespan(assignment, starts, goals):
    route_times = {}
    for start_name in assignment:
        start_position = starts[start_name]
        target_list = assignment[start_name]
        time = calculate_route_time(start_position, target_list, goals)
        route_times[start_name] = time
    makespan = max(route_times.values())
    return makespan, route_times

def create_random_assignment(starts, goals):
    assignment = {}
    for start_name in starts:
        assignment[start_name] = []
    goal_names = list(goals.keys())
    random.shuffle(goal_names)
    start_names = list(starts.keys())
    for goal_name in goal_names:
        chosen_start = random.choice(start_names)
        assignment[chosen_start].append(goal_name)
    return assignment

def create_initial_population(starts, goals, population_size):
    population = []
    for _ in range(population_size):
        assignment = create_random_assignment(starts, goals)
        population.append(assignment)
    return population

def select_best_assignments(population, starts, goals, number_of_parents):
    scored_population = []
    for assignment in population:
        makespan, route_times = calculate_makespan(assignment, starts, goals)
        scored_population.append((makespan, assignment))
    scored_population.sort(key=lambda item: item[0])
    parents = []
    for i in range(number_of_parents):
        parents.append(scored_population[i][1])
    return parents

def find_assigned_start(assignment, goal_name):
    for start_name in assignment:
        if goal_name in assignment[start_name]:
            return start_name
    return None

def crossover(parent1, parent2, starts, goals):
    child = {}
    for start_name in starts:
        child[start_name] = []
    goal_names = list(goals.keys())
    for goal_name in goal_names:
        chosen_parent = random.choice([parent1, parent2])
        chosen_start = find_assigned_start(chosen_parent, goal_name)
        if chosen_start is not None:
            child[chosen_start].append(goal_name)
    return child

def mutate(assignment, starts, goals, mutation_rate):
    new_assignment = {}
    for start_name in assignment:
        new_assignment[start_name] = assignment[start_name].copy()
    random_number = random.random()
    if random_number > mutation_rate:
        return new_assignment
    goal_names = list(goals.keys())
    start_names = list(starts.keys())
    chosen_goal = random.choice(goal_names)
    old_start = find_assigned_start(new_assignment, chosen_goal)
    if old_start is None:
        return new_assignment
    possible_starts = []
    for start_name in start_names:
        if start_name != old_start:
            possible_starts.append(start_name)
    if len(possible_starts) == 0:
        return new_assignment
    new_assignment[old_start].remove(chosen_goal)
    new_start = random.choice(possible_starts)
    new_assignment[new_start].append(chosen_goal)
    return new_assignment

def create_next_generation(population, starts, goals, population_size, mutation_rate):
    parents = select_best_assignments(population, starts, goals, 2)
    new_population = []
    new_population.append(parents[0])
    new_population.append(parents[1])
    while len(new_population) < population_size:
        child = crossover(parents[0], parents[1], starts, goals)
        child = mutate(child, starts, goals, mutation_rate)
        new_population.append(child)
    return new_population

def get_best_assignment(population, starts, goals):
    best_assignment = population[0]
    best_makespan, best_route_times = calculate_makespan(best_assignment, starts, goals)
    for assignment in population:
        makespan, route_times = calculate_makespan(assignment, starts, goals)
        if makespan < best_makespan:
            best_assignment = assignment
            best_makespan = makespan
            best_route_times = route_times
    return best_assignment, best_makespan, best_route_times

def run_genetic_algorithm(starts, goals, population_size, generations, mutation_rate):
    population = create_initial_population(starts, goals, population_size)
    for generation in range(generations):
        population = create_next_generation(population, starts, goals, population_size, mutation_rate)
        best_assignment, best_makespan, best_route_times = get_best_assignment(population, starts, goals)
        print("Generation", generation + 1, "- Best makespan:", best_makespan)
    best_assignment, best_makespan, best_route_times = get_best_assignment(population, starts, goals)
    return best_assignment, best_makespan, best_route_times

def print_final_result(best_assignment, best_makespan, best_route_times, starts, goals):
    print()
    print("Final result:")
    print("Best makespan (minutes):", format(best_makespan, ".2f"))
    for start_name in best_assignment:
        target_names = best_assignment[start_name]
        target_coords = []
        for target in target_names:
            target_coords.append(goals[target])
        print(start_name, "at", starts[start_name], "assigned targets:", target_names, "-> coords:", target_coords)
    for start_name in best_route_times:
        print(start_name, "route time =", float(best_route_times[start_name]), "minutes")

def run_scenario_3(filename):
    grid, starts, goals = read_map_for_ga(filename)
    population_size = 10
    generations = 20
    mutation_rate = 0.2
    best_assignment, best_makespan, best_route_times = run_genetic_algorithm(starts, goals, population_size, generations, mutation_rate)
    print_final_result(best_assignment, best_makespan, best_route_times, starts, goals)

if __name__ == "__main__":
    # For standalone testing
    import sys
    if len(sys.argv) > 1:
        run_scenario_3(sys.argv[1])
    else:
        print("Please provide a filename: python genetic_algorithm.py <map_file>")