ACO.py

import numpy as np
import random
import math
import matplotlib.pyplot as plt
from vis_tools import harita_gorsellestir_aco


class GridMap:

    def __init__(self, boyut, start, goal):
        self.BOYUT = boyut
        self.START = start
        self.GOAL = goal
        self.HARITA = self._harita_olustur()
        self.ENGEL_CEZASI = 5000 # 3000
        self.SINIR_CEZASI = 15000 # 5000


    def _harita_olustur(self):

        harita = np.zeros((self.BOYUT, self.BOYUT), dtype=int)

        harita[2:8, 4] = 1
        harita[7, 2:4] = 1
        harita[5, 7] = 1
        harita[6, 7] = 1

        harita[self.START] = 0
        harita[self.GOAL] = 0
       
        return harita

    def kontrol_et_engel (self, koordinat):

        x = int(round(koordinat[0]))
        y = int(round(koordinat[1]))


        if not (0 <= x < self.BOYUT and 0 <= y < self.BOYUT):
            return self.SINIR_CEZASI
        
        if self.HARITA[x, y] == 1:
            return self.ENGEL_CEZASI 
        
        return 0
    

def get_neighbors(y, x, BOYUT):
    komşular = []
    for dy in [-1, 0, 1]:
        for dx in [-1, 0, 1]:
            if dy == 0 and dx == 0:
                continue
            ny, nx = y + dy, x + dx
            if 0 <= ny < BOYUT and 0 <= nx < BOYUT:
                komşular.append((ny, nx))
    return komşular


def heuristic(y, x, GOAL):
    uzaklik = math.sqrt((GOAL[0] - y)**2 + (GOAL[1] - x)**2)
    return 1.0 / (uzaklik + 1e-6) 


def aco_pathfinding(grid_map, max_iter, karinca_sayisi, alpha, beta, rho, Q):
    N = grid_map.BOYUT
    START = grid_map.START
    GOAL = grid_map.GOAL

    T0 = 1.0 / (N * N) # Başlangıç feromon değeri
    feromon_matris = np.full((N, N), T0)

    en_iyi_yol = None
    en_iyi_maliyet = float('inf')
    maliyet_gecmisi = []

    for t in range(max_iter):
        
        yollar = []
        
        for k_idx in range(karinca_sayisi):
            
            karinca = {'pozisyon': START, 'yol': [START], 'uzunluk': 0.0, 'tikandi': False, 'ziyaretler': {START}}
            
            max_adimlar = N * N * 3 
            adim_sayisi = 0
            
            while karinca['pozisyon'] != GOAL and not karinca['tikandi'] and adim_sayisi < max_adimlar:
                cy, cx = karinca['pozisyon']
                
                komşular = get_neighbors(cy, cx, N)
                
                geçerli_komşular = []
                for ny, nx in komşular:
                    # if grid_map.HARITA[ny, nx] != 1: 
                    #     geçerli_komşular.append((ny, nx))
                    if grid_map.HARITA[ny, nx] != 1 and (ny, nx) not in karinca['ziyaretler']: 
                        geçerli_komşular.append((ny, nx))
                if not geçerli_komşular:
                    karinca['tikandi'] = True
                    break

                olasiliklar_listesi = []
                toplam_payda = 0.0
                
                for ny, nx in geçerli_komşular:
                    tau = feromon_matris[ny, nx]**alpha
                    eta = heuristic(ny, nx, GOAL)**beta
                    toplam_payda += tau * eta
                
                if toplam_payda == 0: 
                     sonraki_düğüm = random.choice(geçerli_komşular)
                     olasiliklar_listesi = [1.0/len(geçerli_komşular)] * len(geçerli_komşular)
                else:
                    for ny, nx in geçerli_komşular:
                        tau = feromon_matris[ny, nx]**alpha
                        eta = heuristic(ny, nx, GOAL)**beta
                        olasilik = (tau * eta) / toplam_payda
                        olasiliklar_listesi.append(olasilik)
                    
                    olasiliklar_array = np.array(olasiliklar_listesi) / np.sum(olasiliklar_listesi)
                    
                    secilen_index = np.random.choice(len(geçerli_komşular), p=olasiliklar_array)
                    sonraki_düğüm = geçerli_komşular[secilen_index]

                ny, nx = sonraki_düğüm
                
                uzunluk_artisi = math.sqrt((ny - cy)**2 + (nx - cx)**2)
                karinca['uzunluk'] += uzunluk_artisi

                karinca['pozisyon'] = sonraki_düğüm
                karinca['yol'].append(sonraki_düğüm)
                karinca['ziyaretler'].add(sonraki_düğüm)
                adim_sayisi += 1
            
            if karinca['pozisyon'] == GOAL:
                yollar.append(karinca)
        
        
        
        # 1. Buharlaşma
        feromon_matris = (1.0 - rho) * feromon_matris
        
        # 2. Depozito: Sadece hedefe ulaşan karıncalar feromon bırakır
        hedefe_ulaşanlar = [k for k in yollar if k['pozisyon'] == GOAL]
        
        if hedefe_ulaşanlar:
            
            mevcut_en_iyi_yol_k = min(hedefe_ulaşanlar, key=lambda k: k['uzunluk'])
            
            if mevcut_en_iyi_yol_k['uzunluk'] < en_iyi_maliyet:
                en_iyi_maliyet = mevcut_en_iyi_yol_k['uzunluk']
                en_iyi_yol = mevcut_en_iyi_yol_k['yol']
            
            # for karinca in hedefe_ulaşanlar:
            #     delta_tau = Q / karinca['uzunluk']
            #     # Karıncanın geçtiği tüm hücrelere feromon ekle
            #     for y, x in karinca['yol']:
            #         feromon_matris[y, x] += delta_tau
            if en_iyi_yol:
                delta_tau_gbest = Q / en_iyi_maliyet 
                for y, x in en_iyi_yol:
                    feromon_matris[y, x] += delta_tau_gbest 

        maliyet_gecmisi.append(en_iyi_maliyet)
        
        if  t == max_iter - 1: #t % 5 == 0 or
            print(f"İterasyon: {t+1}/{max_iter}, En İyi Maliyet: {en_iyi_maliyet:.2f}")
            harita_gorsellestir_aco(grid_map, en_iyi_yol, t)
    return en_iyi_yol, en_iyi_maliyet, maliyet_gecmisi




if __name__ == "__main__":
    print("selam")
    HARITA_BOYUTU = 10
    BASLANGIC = (0, 0)
    HEDEF = (9,9)
    grid_map = GridMap(HARITA_BOYUTU, BASLANGIC, HEDEF)


    #ACO parametreleri
    MAX_ITER_ACO = 50
    KARINCA_SAYISI = 10
    ALPHA = 1.0  # Feromon önemi
    BETA = 2.0   # Heuristik önemi
    RHO = 0.2    # Buharlaşma Oranı
    Q = 10.0     # Feromon Sabiti

    en_iyi_rota_aco, en_iyi_maliyet_aco, maliyet_gecmisi_aco = aco_pathfinding(grid_map, MAX_ITER_ACO, KARINCA_SAYISI, ALPHA, BETA, RHO, Q)



    # --- SONUÇ GÖRSELLEŞTİRMESİ ---
    plt.figure(figsize=(10, 5))
    plt.plot(maliyet_gecmisi_aco, label='En İyi Rota Maliyeti', color='red')
    plt.title('ACO Optimizasyon Performansı (Maliyet vs. İterasyon)')
    plt.xlabel('İterasyon Sayısı')
    plt.ylabel('Rota Uzunluğu (Maliyet)')
    plt.legend()
    plt.grid(True)
    # plt.show()

    print("\n" + "="*50)
    print("ACO YOL BULMA SONUÇ ÖZETİ (10x10)")
    print("="*50)
    print(f"Bulunan En İyi Rota Uzunluğu (Maliyet): {en_iyi_maliyet_aco:.2f}")
    
    # if en_iyi_rota_aco:
    #     print(f"Rota Adım Sayısı: {len(en_iyi_rota_aco)}")
        
    #     # Harita üzerinde rotayı görselleştirme
    #     rota_harita = grid_map.HARITA.copy()
    #     for i, (y, x) in enumerate(en_iyi_rota_aco):
    #         if i == 0: rota_harita[y, x] = 2 # Başlangıç
    #         elif i == len(en_iyi_rota_aco) - 1: rota_harita[y, x] = 3 # Hedef
    #         elif rota_harita[y, x] == 0: rota_harita[y, x] = 8 # Yol (Engelsiz alanı işaretle)

    #     print("\nHarita ve En İyi Rota (2:Başlangıç, 3:Hedef, 1:Engel, 8:Yol):")
    #     print(rota_harita)
    # else:
    #     print("HİÇBİR KARINCA HEDEFE ULAŞAMADI.")