import matplotlib.pyplot as plt import networkx as nx import numpy as np import random import math import os from collections import defaultdict import scipy as sp # ------------------------------- # Funzioni per inizializzare il grafo e visualizzarlo # ------------------------------- def crea_grafo_esempio(): """Crea un semplice grafo con pesi per la simulazione ACO.""" G = nx.Graph() edges = [ ('A', 'B', 1), ('A', 'C', 2), ('B', 'C', 1), ('B', 'D', 4), ('C', 'D', 2), ('C', 'E', 3), ('D', 'E', 1) ] for u, v, w in edges: G.add_edge(u, v, weight=w) return G def crea_grafo_complesso(): """Crea un grafo più complesso con pesi per la simulazione ACO.""" G = nx.Graph() edges = [ ('A', 'B', 2), ('A', 'C', 3), ('A', 'D', 4), ('B', 'E', 2), ('B', 'F', 1), ('C', 'F', 1), ('C', 'G', 5), ('D', 'G', 2), ('D', 'H', 1), ('E', 'I', 4), ('F', 'I', 2), ('F', 'J', 3), ('G', 'J', 1), ('G', 'K', 4), ('H', 'K', 2), ('I', 'L', 3), ('J', 'L', 2), ('J', 'M', 4), ('K', 'M', 3), ('L', 'N', 2), ('M', 'N', 1) ] for u, v, w in edges: G.add_edge(u, v, weight=w) return G def crea_grafo_random(n,m): # Crea un grafo planare con struttura a griglia G = nx.grid_2d_graph(n, m) # 5 righe x 6 colonne G = nx.convert_node_labels_to_integers(G) mapping = {node: str(node) for node in G.nodes()} G = nx.relabel_nodes(G, mapping) # Aggiungi pesi casuali agli archi for (u, v) in G.edges(): G[u][v]['weight'] = random.randint(1, 5) return G def inizializza_feromoni(G, iniziale=1.0): """Inizializza i livelli di feromone su ogni arco del grafo.""" feromoni = {} for edge in G.edges(): feromoni[edge] = iniziale return feromoni def disegna_grafo(G, feromoni=None, path=None, title="Grafo iniziale"): """Visualizza il grafo con pesi e intensità di feromoni.""" pos = nx.kamada_kawai_layout(G) edge_labels = nx.get_edge_attributes(G, 'weight') # Colore archi in base al feromone if feromoni: max_feromone = max(feromoni.values()) edge_colors = [feromoni.get((u,v), feromoni.get((v,u), 0)) / max_feromone for u,v in G.edges()] else: edge_colors = 'black' # Disegno plt.figure(figsize=(8, 6)) nx.draw(G, pos, with_labels=True, node_color='lightblue', edge_color=edge_colors, width=2.5, edge_cmap=plt.cm.plasma) nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels) if path: edges_in_path = list(zip(path, path[1:])) nx.draw_networkx_edges(G, pos, edgelist=edges_in_path, edge_color='lime', width=4) plt.title(title) plt.axis('off') plt.show() # ------------------------------- # Funzioni principali ACO # ------------------------------- def scelta_prossimo_nodo(G, feromoni, corrente, visitati, alfa, beta): """ Scelta probabilistica del prossimo nodo basata sui livelli di feromone e sull'euristica della distanza. Args: G (networkx.Graph): Il grafo su cui si sta eseguendo l'algoritmo. feromoni (dict): Dizionario che associa a ogni arco il livello di feromone. corrente (str): Nodo corrente in cui si trova la formica. visitati (set): Insieme dei nodi già visitati dalla formica. alfa (float): Peso dell'influenza del feromone. beta (float): Peso dell'influenza dell'euristica della distanza. Returns: str: Il prossimo nodo scelto probabilisticamente, oppure None se non ci sono nodi disponibili. """ # Ottieni i vicini del nodo corrente che non sono stati ancora visitati vicini = [n for n in G.neighbors(corrente) if n not in visitati] if not vicini: return None # Nessun nodo disponibile, cammino bloccato # Calcola il peso (probabilità relativa) per ogni vicino pesi = [] for vicino in vicini: # Determina l'arco corrente (direzione non importa) arco = (corrente, vicino) if (corrente, vicino) in feromoni else (vicino, corrente) # Calcola il contributo del feromone (tau) e dell'euristica (eta) tau = feromoni[arco] ** alfa # Influenza del feromone eta = (1.0 / G[corrente][vicino]['weight']) ** beta # Influenza della distanza (euristica) # Aggiungi il prodotto di tau e eta alla lista dei pesi pesi.append(tau * eta) # Calcola la somma totale dei pesi somma = sum(pesi) # Normalizza i pesi per ottenere le probabilità probabilita = [p / somma for p in pesi] # Seleziona un vicino in base alle probabilità calcolate scelto = random.choices(vicini, weights=probabilita, k=1)[0] return scelto def costruisci_cammino(G, feromoni, start, destinazioni, alfa, beta): """ Costruisce un cammino valido da start a uno qualsiasi dei nodi in destinazioni usando la politica ACO. Args: G (networkx.Graph): Il grafo su cui si sta eseguendo l'algoritmo. feromoni (dict): Dizionario che associa a ogni arco il livello di feromone. start (str): Nodo di partenza. destinazioni (list): Lista di nodi di destinazione. alfa (float): Peso dell'influenza del feromone. beta (float): Peso dell'influenza dell'euristica della distanza. Returns: list: Il cammino costruito, oppure None se non è possibile raggiungere una destinazione. """ corrente = start path = [corrente] visitati = set(path) while corrente not in destinazioni: prossimo = scelta_prossimo_nodo(G, feromoni, corrente, visitati, alfa, beta) if prossimo is None: return None # Cammino bloccato path.append(prossimo) visitati.add(prossimo) corrente = prossimo return path def aggiorna_feromoni(G, feromoni, cammini, evaporazione, feromone_deposito): """Aggiorna i feromoni con evaporazione e rinforzo.""" # Evaporazione for arco in feromoni: feromoni[arco] *= (1 - evaporazione) # Deposito for cammino in cammini: if cammino is None: continue lunghezza = sum(G[u][v]['weight'] for u, v in zip(cammino, cammino[1:])) deposito = feromone_deposito / lunghezza for u, v in zip(cammino, cammino[1:]): arco = (u, v) if (u, v) in feromoni else (v, u) feromoni[arco] += deposito def modifica_grafo_dinamicamente(G, pheromone_matrix, iteration, config, pos): # Rimozione di nodi if (iteration+1) % config['frequenza_rimozione'] == 0: # Evita di rimuovere nodi se troppo pochi if len(G.nodes) > config['nodi_min']: # Scegli un nodo da rimuovere che non sia start o end nodi_possibili = [n for n in G.nodes if n not in config['nodi_protetti']] if nodi_possibili: nodo_da_rimuovere = random.choice(nodi_possibili) G.remove_node(nodo_da_rimuovere) # Rimuovi tutti gli archi associati al nodo rimosso edges_to_remove = [(u, v) for u, v in pheromone_matrix.keys() if u == nodo_da_rimuovere or v == nodo_da_rimuovere] for edge in edges_to_remove: del pheromone_matrix[edge] # Aggiunta di nuovi nodi if (iteration+1) % config['frequenza_nuovi_nodi'] == 0: if len(G.nodes) < config['nodi_max']: nuovo_id = f"N{iteration}" G.add_node(nuovo_id) nodi_esistenti = list(G.nodes) nodi_esistenti.remove(nuovo_id) nodi_connessi = random.sample(nodi_esistenti, min(config['archi_nuovo_nodo'], len(nodi_esistenti))) for n in nodi_connessi: peso = random.randint(1, 10) G.add_edge(nuovo_id, n, weight=peso) # Aggiunta alla matrice dei feromoni for n in nodi_connessi: arco = (nuovo_id, n) pheromone_matrix[arco] = config['pheromone_iniziale'] # Aggiorna il layout per il nuovo nodo pos = aggiorna_layout(G, pos) return G, pheromone_matrix, pos def aggiorna_layout(G, pos): # Aggiorna il layout per i nuovi nodi mantenendo fisso il resto for node in G.nodes: if node not in pos: # Assegna posizione media dei vicini neighbors = list(G.neighbors(node)) if neighbors: x = np.mean([pos[n][0] for n in neighbors if n in pos]) y = np.mean([pos[n][1] for n in neighbors if n in pos]) pos[node] = np.array([x + 0.05*np.random.randn(), y + 0.05*np.random.randn()]) else: pos[node] = np.random.rand(2) # Fallback casuale return pos # ------------------------------- # Esecuzione multi-iterazione # ------------------------------- def esegui_aco(G, num_formiche, num_iterazioni, alfa, beta, evaporazione, feromone_iniziale, feromone_deposito, nodo_partenza, nodi_destinazione, output_folder, config): """ Esegue l'algoritmo ACO sul grafo G con i parametri specificati. Args: G (networkx.Graph): Il grafo su cui si sta eseguendo l'algoritmo. num_formiche (int): Numero di formiche per iterazione. num_iterazioni (int): Numero di iterazioni. alfa (float): Peso dell'influenza del feromone. beta (float): Peso dell'influenza dell'euristica della distanza. evaporazione (float): Tasso di evaporazione del feromone. feromone_iniziale (float): Livello iniziale di feromone. feromone_deposito (float): Quantità di feromone depositata. nodo_partenza (str): Nodo di partenza. nodi_destinazione (list): Lista di nodi di destinazione. output_folder (str): Cartella per salvare i risultati. Returns: tuple: Il miglior cammino trovato e la sua lunghezza. """ # Inizializza i feromoni feromoni = inizializza_feromoni(G, feromone_iniziale) # Inizializza le cartelle per i frames output_aco_frames = f"{output_folder}/frames/aco" os.makedirs(output_aco_frames, exist_ok=True) output_feromone_hist = f"{output_folder}/frames/feromone" os.makedirs(output_feromone_hist, exist_ok=True) output_path_frames = f"{output_folder}/frames/path" os.makedirs(output_path_frames, exist_ok=True) output_img = f"{output_folder}/img" os.makedirs(output_img, exist_ok=True) miglior_cammino = None miglior_lunghezza = math.inf costs = [] best_costs = [] edge_visit_count = defaultdict(int) pos = nx.kamada_kawai_layout(G) for iterazione in range(num_iterazioni): cammini = [] for _ in range(num_formiche): cammino = costruisci_cammino(G, feromoni, nodo_partenza, nodi_destinazione, alfa, beta) if cammino is not None: lunghezza = sum(G[u][v]['weight'] for u, v in zip(cammino, cammino[1:])) if lunghezza < miglior_lunghezza: miglior_lunghezza = lunghezza miglior_cammino = cammino cammini.append(cammino) if cammino is not None: for i in range(len(cammino) - 1): u, v = cammino[i], cammino[i+1] edge_visit_count[(min(u,v), max(u,v))] += 1 best_costs.append(miglior_lunghezza) # Salva il miglior costo globale trovato finora costs.append(lunghezza) # Salva il miglior costo trovato finora aggiorna_feromoni(G, feromoni, cammini, evaporazione, feromone_deposito) # Visualizza e salva l'immagine della rete aggiornata salva_frame_iterazione(G, feromoni, iterazione, output_aco_frames, nodo_partenza, nodi_destinazione,pos) plot_feromone_histogram(feromoni, iterazione, G, output_feromone_hist, config) plot_path_evolution(costs, best_costs, iterazione, output_path_frames) G, feromoni, pos = modifica_grafo_dinamicamente(G, feromoni, iterazione, config, pos) # Resetta la miglior lunghezza se viene aggiunto o rimosso un nodo if (iterazione + 1) % config['frequenza_rimozione'] == 0 or (iterazione + 1) % config['frequenza_nuovi_nodi'] == 0: miglior_lunghezza = 10000 plot_ant_choice_distribution(edge_visit_count, save_path=os.path.join(output_folder, "img/ant_choice_distrib.png")) return miglior_cammino, miglior_lunghezza def salva_frame_iterazione(G, feromoni, iterazione, output_folder, nodo_partenza=None, nodi_destinazione=None, pos=None): """Salva un frame della rete con i feromoni aggiornati.""" fig, ax = plt.subplots(figsize=(10, 8)) #pos = nx.kamada_kawai_layout(G) pesi = [G[u][v]['weight'] for u, v in G.edges()] # Colori dei nodi node_colors = [] for nodo in G.nodes(): if nodo == nodo_partenza: node_colors.append('red') # Nodo di partenza elif nodi_destinazione and nodo in nodi_destinazione: node_colors.append('green') # Nodi di destinazione else: node_colors.append('skyblue') # Altri nodi nx.draw_networkx_nodes(G, pos, ax=ax, node_color=node_colors, node_size=300) nx.draw_networkx_labels(G, pos, ax=ax) nx.draw_networkx_edges(G, pos, ax=ax, edge_color='gray', width=2) #nx.draw_networkx_edge_labels(G, pos, edge_labels={(u, v): G[u][v]['weight'] for u, v in G.edges()}, ax=ax) #Aggiunge il peso degli archi # Feromoni: colore e spessore max_feromone = max(feromoni.values()) for (u, v), livello in feromoni.items(): alpha = livello / max_feromone if max_feromone > 0 else 0 nx.draw_networkx_edges( G, pos, edgelist=[(u, v)], width=12 * alpha, # Aumenta ulteriormente lo spessore degli archi edge_color=plt.cm.plasma(alpha), # Usa una mappa cromatica più vivida alpha=0.9, # Aumenta la trasparenza per maggiore visibilità ax=ax ) ax.set_title(f"Iterazione {iterazione + 1}") ax.axis('off') fig.tight_layout() os.makedirs(output_folder, exist_ok=True) fig.savefig(f"{output_folder}/iter_{iterazione + 1:03d}.png") plt.close(fig) def plot_feromone_histogram(pheromone_matrix, iteration, graph, output_dir, config): """ Plotta e salva un istogramma dei livelli di feromone su ogni arco. """ plt.figure(figsize=(10, 6)) edge_labels = [] pheromone_levels = [] for i, (u, v) in enumerate(graph.edges()): label = f"{u}-{v}" edge_labels.append(label) total_pheromone = sum(pheromone_matrix.values()) pheromone_levels.append((pheromone_matrix.get((u, v), pheromone_matrix.get((v, u), 0))) / total_pheromone * 100 if total_pheromone > 0 else 0) # Ordinamento per consistenza visiva edge_labels, pheromone_levels = zip(*sorted(zip(edge_labels, pheromone_levels), key=lambda x: x[0])) block_index = (iteration // config['frequenza_rimozione']) % 2 color = 'crimson' if block_index == 0 else 'darkorange' plt.bar(edge_labels, pheromone_levels, color=color) plt.xlabel("Archi") plt.ylabel("Livello percentuale di feromone") plt.title(f"Istogramma dei feromoni - Iterazione {iteration+1}") plt.xticks(rotation=45, fontsize=6) plt.tight_layout() plt.savefig(f"{output_dir}/hist_feromone_{iteration+1:03d}.png") plt.close() def plot_path_evolution(costs, best_costs, iteration, output_dir): """ Plotta l'evoluzione del costo del miglior cammino nel tempo, includendo il costo globale migliore. Parameters: costs (list): lista dei costi trovati a ogni iterazione. best_costs (list): lista dei costi globali minimi trovati fino a ogni iterazione. iteration (int): numero dell'iterazione corrente. output_dir (str): directory dove salvare il grafico. """ plt.figure(figsize=(8, 5)) max_points = 70 if len(costs) > max_points: plt.plot(range(len(costs) - max_points, len(costs)), costs[-max_points:], linestyle='-', linewidth=2, color='blue', alpha=0.8, label='Costo formica') plt.plot(range(len(best_costs) - max_points, len(best_costs)), best_costs[-max_points:], linestyle='-', linewidth=1, color='red', alpha=0.8, label='Miglior costo globale') else: plt.plot(costs, linestyle='-', linewidth=2, color='blue', alpha=0.8, label='Costo formica') plt.plot(best_costs, linestyle='-', linewidth=1, color='red', alpha=0.8, label='Miglior costo globale') plt.title("Evoluzione del costo del cammino di una formica") plt.xlabel("Iterazione") plt.ylabel("Costo") plt.legend(loc='upper left', fontsize='small') plt.grid(True) plt.savefig(f"{output_dir}/ant_path{iteration+1:03d}.png") plt.close() def plot_ant_choice_distribution(edge_visit_count, save_path="ant_choice_distribution.png"): """ Plotta la distribuzione delle scelte delle formiche sugli archi. Parameters: edge_visit_count (dict): mappa da tuple (u, v) a numero di visite. save_path (str): dove salvare l'immagine. """ edges = list(edge_visit_count.keys()) visits = [edge_visit_count[edge] for edge in edges] labels = [f"{u}-{v}" for (u, v) in edges] plt.figure(figsize=(12, 6)) plt.bar(labels, visits, color='slateblue') plt.xlabel("Archi") plt.ylabel("Numero di passaggi") plt.title("Distribuzione delle scelte delle formiche sugli archi") plt.xticks(rotation=45) plt.tight_layout() plt.savefig(save_path) plt.close() def crea_gif(output_folder, durata_frame=0.5): """Crea una GIF animata dai frame salvati e include i parametri iniziali.""" from glob import glob import imageio from PIL import Image output_aco_frames = f"{output_folder}/frames/aco" gif_path = f"{output_folder}/aco.gif" # Ordina i frame frames = sorted(glob(f"{output_aco_frames}/iter_*.png")) # Crea GIF with imageio.get_writer(gif_path, mode="I", duration=durata_frame) as writer: for frame in frames: image = Image.open(frame) writer.append_data(image) def crea_gif_feromone_hist(output_folder, durata_frame=0.5): """Crea una GIF animata dai frame degli istogrammi dei feromoni.""" from glob import glob import imageio from PIL import Image, ImageDraw, ImageFont # Ordina i frame degli istogrammi output_feromone_hist_frames = f"{output_folder}/frames/feromone" gif_path = f"{output_folder}/feromone_hist.gif" frames = sorted(glob(f"{output_feromone_hist_frames}/hist_feromone_*.png")) # Crea GIF with imageio.get_writer(gif_path, mode="I", duration=durata_frame) as writer: for frame in frames: try: image = Image.open(frame) writer.append_data(image) except Exception as e: print(f"DEBUG: Error while adding frame {frame}: {e}") def crea_gif_path_frames(output_folder, durata_frame=0.5): """Crea una GIF animata dai frame dei cammini delle formiche.""" from glob import glob import imageio from PIL import Image # Ordina i frame dei cammini output_path_frames = f"{output_folder}/frames/path" gif_path = f"{output_folder}/path_frames.gif" frames = sorted(glob(f"{output_path_frames}/ant_path*.png")) # Crea GIF with imageio.get_writer(gif_path, mode="I", duration=durata_frame) as writer: for frame in frames: try: image = Image.open(frame) writer.append_data(image) except Exception as e: print(f"DEBUG: Error while adding frame {frame}: {e}") def salva_grafo_iniziale(G, output_folder, nodo_partenza=None, nodi_destinazione=None, pos=None): """Salva un frame della rete con i feromoni aggiornati.""" # Crea la cartella per le immagini os.makedirs(os.path.join(output_folder, "img"), exist_ok=True) # Salva il grafo iniziale output_img = f"{output_folder}/img/initial_graph.png" fig, ax = plt.subplots(figsize=(10, 8)) pos = nx.kamada_kawai_layout(G) pesi = [G[u][v]['weight'] for u, v in G.edges()] # Colori dei nodi node_colors = [] for nodo in G.nodes(): if nodo == nodo_partenza: node_colors.append('red') # Nodo di partenza elif nodi_destinazione and nodo in nodi_destinazione: node_colors.append('green') # Nodi di destinazione else: node_colors.append('skyblue') # Altri nodi nx.draw_networkx_nodes(G, pos, ax=ax, node_color=node_colors, node_size=300) nx.draw_networkx_labels(G, pos, ax=ax) nx.draw_networkx_edges(G, pos, ax=ax, edge_color='gray', width=2) nx.draw_networkx_edge_labels(G, pos, edge_labels={(u, v): G[u][v]['weight'] for u, v in G.edges()}, ax=ax) #Aggiunge il peso degli archi ax.set_title(f"Grafo Iniziale") ax.axis('off') fig.tight_layout() os.makedirs(output_folder, exist_ok=True) fig.savefig(output_img) plt.close(fig) # ------------------------------- # Parametri dell'algoritmo ACO # ------------------------------- if __name__ == "__main__": G= crea_grafo_random(7,8) NUM_FORMICHE = 50 NUM_ITERAZIONI = 200 ALFA = 0.5 # Influenza del feromone ridotta per favorire esplorazione BETA = 1 # Influenza della distanza (euristica) ridotta per bilanciare esplorazione e sfruttamento EVAPORAZIONE = 0.3 # Tasso di evaporazione del feromone aumentato per ridurre accumulo rapido FEROMONE_INIZIALE = 0.01 # Livello iniziale di feromone molto basso per favorire esplorazione iniziale FEROMONE_DEPOSITO = 0.5 # Deposito di feromone ridotto per evitare convergenza rapida NODO_PARTENZA = '0' # Nodo di partenza NODI_DESTINAZIONE = [ '7', '48', '27'] # Lista di nodi di destinazione OUTPUT_FOLDER_BASE = "results/prova3" CONFIG = { 'frequenza_rimozione': 30, # ogni 10 iterazioni 'frequenza_nuovi_nodi': 50, # ogni 5 iterazioni 'nodi_min': 5, # minimo numero di nodi da mantenere 'nodi_max': 1000, # massimo numero di nodi da raggiungere 'archi_nuovo_nodo': 2, # numero di archi per ogni nuovo nodo 'pheromone_iniziale': 1.0, # valore iniziale per i nuovi archi 'nodi_protetti': ['0', '50'] # es. start e end da non rimuovere } # Cartella per salvare le immagini os.makedirs(OUTPUT_FOLDER_BASE, exist_ok=True) os.makedirs(os.path.join(OUTPUT_FOLDER_BASE, "frames"), exist_ok=True) os.makedirs(os.path.join(OUTPUT_FOLDER_BASE, "img"), exist_ok=True) salva_grafo_iniziale(G, OUTPUT_FOLDER_BASE, NODO_PARTENZA, NODI_DESTINAZIONE) # Esegui l'algoritmo ACO esegui_aco(G, NUM_FORMICHE, NUM_ITERAZIONI, ALFA, BETA, EVAPORAZIONE, FEROMONE_INIZIALE, FEROMONE_DEPOSITO, NODO_PARTENZA, NODI_DESTINAZIONE, OUTPUT_FOLDER_BASE, CONFIG) # Crea GIF animata crea_gif(OUTPUT_FOLDER_BASE, durata_frame=0.5) crea_gif_feromone_hist(OUTPUT_FOLDER_BASE, durata_frame=0.5) crea_gif_path_frames(OUTPUT_FOLDER_BASE, durata_frame=0.5)