GA.py

import random
import matplotlib.pyplot as plt
import numpy as np
import time 
import json


N, M = 50, 50
start, goal = (0, 0), (49, 49)
# obstacles = {(1, 1), (1, 2), (2, 2), (3, 1)}
obstacles = {
    (3, 21), (3, 33), (4, 4), (5, 43), (9, 31),
    (10, 13), (10, 41), (11, 2), (11, 25), (13, 33),
    (15, 25), (18, 25), (19, 14), (21, 30), (22, 3),
    (26, 7), (26, 36), (27, 47), (31, 14), (31, 28),
    (31, 39), (32, 17), (32, 33), (34, 24), (35, 24),
    (37, 2), (42, 24), (43, 48), (48, 16), (49, 32), (25, 25), (26,25)
}

MOVES = ['U', 'D', 'L', 'R']
DIR = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}


random.seed(42)
population_size, L = 70, 150 # L=kromozom uzunlugu
GEN = 100 
pc, pm = 0.9, 0.01 #pc=caprazlama olasiligi, pm=mutasyon olasiligi




def plot_path(path, start, goal, obstacles):
    grid = np.zeros((N, M))
    for r, c in obstacles:
        grid[r, c] = -1  # engeller

    r, c = start
    coords = [(r, c)]
    for mv in path:
        (r, c), _, _ = step((r, c), mv)
        coords.append((r, c))

    ys, xs = zip(*coords)

    plt.figure(figsize=(6, 6))
    plt.imshow(grid, cmap="Greys", origin="upper", alpha=0.3)

    # Engelleri kırmızı karelerle göster
    if obstacles:
        obs_y, obs_x = zip(*obstacles)
        plt.scatter(obs_x, obs_y, marker='s', color='red', label='Obstacle', s=80, edgecolors='black', linewidths=0.5)

    # Yol çizgisi
    plt.plot(xs, ys, color="blue", linewidth=2, label="Path")
    plt.scatter(xs, ys, color="blue", s=10)

    # Başlangıç noktası
    plt.scatter([start[1]], [start[0]], color="green", marker="o", s=100, label="Start", edgecolors='black', zorder=5)
    plt.text(start[1], start[0], "Start", color="green", fontsize=10, fontweight="bold", ha="right", va="bottom")

    # Hedef noktası
    plt.scatter([goal[1]], [goal[0]], color="gold", marker="*", s=200, label="Goal", edgecolors='black', zorder=5)
    plt.text(goal[1], goal[0], "Goal", color="goldenrod", fontsize=10, fontweight="bold", ha="left", va="top")

    plt.title("Genetic Algorithm Path", fontsize=14)
    plt.xlabel("X koordinatı")
    plt.ylabel("Y koordinatı")
    plt.xlim(-0.5, M-0.5)
    plt.ylim(-0.5, N-0.5)
    plt.gca().set_aspect('equal')
    plt.grid(True, which='both', color='gray', linewidth=0.3, linestyle='--', alpha=0.5)
    plt.legend(loc="upper left", fontsize=10)
    plt.tight_layout()
    # plt.show()

def step(pos, move):
    r, c = pos
    dr, dc = DIR[move]
    nr, nc = r+dr, c+dc

    #duvar veya engelse yerinde say
    if 0 <= nr < N and 0 <= nc < M:
        if (nr, nc) not in obstacles:
            return (nr, nc), 0, 0
        else:
            return pos, 1, 0
    else:
        return pos, 0, 1

def manhattan(a, b): 
    return abs(a[0]-b[0]) + abs(a[1]-b[1]) 

def cost(path):
    pos = start
    for mv in path:
        # pos, p = step(pos, mv)
        pos, c, o = step(pos, mv)
    return len(path) + 5*(c + o) + manhattan(pos, goal)

def fitness(path):
    return -cost(path)

def tournament(pop): 
    a, b = random.sample(pop, 2)
    return a if fitness(a) >= fitness(b) else b

def crossover(p1, p2): #tek noktalı caprazlama
    if random.random() > pc: return [p1[:], p2[:]]
    k = random.randint(1, L-1)
    return [p1[:k]+p2[k:], p2[:k]+p1[k:]]

def mutate(ch): # her gen icin pm ihtimalle yeni bir mutasyon
    for i in range(L):
        if random.random() < pm:
            ch[i] = random.choice(MOVES)
    return ch

def rand_path(L): return [random.choice(MOVES) for _ in range(L)] #random path generator

if __name__ == "__main__":

    t0 = time.time()
    pop = [rand_path(L) for _ in range(population_size)] #aday cozumler

    for g in range(GEN):
        pop = sorted(pop, key=fitness, reverse=True)
        best = pop[0]
        print(f"Gen {g:02d}  best_cost={-fitness(best)}  best={''.join(best)}")


        pos = start
        reached = False
        col, oob = 0, 0
        used = 0
        for mv in best:
            pos, c, o = step(pos, mv)
            col += c
            oob += o
            used += 1
            if pos == goal:
                reached = True
                break
        if reached:
            print(f"Erken durdurma: {g}. jenerasyonda hedefe ulaşıldı!")
            break



        new_pop = [best]  # best bireyi kaybetmemek için tutarız, elitizm
        while len(new_pop) < population_size:
            p1, p2 = tournament(pop), tournament(pop) # rastgele iki birey seçilir ve fitness büyük olan döndürülür. (Aynı birey de seçilebilir. önlem alınmalı)
            c1, c2 = crossover(p1, p2)
            new_pop.append(mutate(c1))
            if len(new_pop) < population_size:
                new_pop.append(mutate(c2))
        pop = new_pop


    pop = sorted(pop, key=fitness, reverse=True)
    best = pop[0]
    print("\nBEST:", ''.join(best), "cost=", -fitness(best))


    t1 = time.time() - t0
    result = {
        "algorithm":"GA",
        "gens": GEN,
        "population": population_size,
        "chromozome_lenght": L,
        "reached": reached,
        "steps_used": used,
        "collisions": col,
        "oob": oob,
        "cost": -fitness(best), 
        "time_sec": t1
    }
    print("RESULTS: ", result)

    with open("GA_result.json", "w", encoding="utf-8") as f:
        json.dump(result, f, ensure_ascii=False, indent=4)

    plot_path(best, start, goal, obstacles)
    plt.savefig("best_path.png")