Ottimizzazione della colonia di formiche in azione

Ottimizzazione delle formiche in azione

Una formica che lavora. Immagine creata con Dall-E 2 dall'autore.

Risoluzione dei problemi di ottimizzazione e miglioramento dei risultati con ACO in Python

Bentornato! Nel mio post precedente, ho introdotto i fondamenti dell’Ant Colony Optimization (ACO). In questa puntata, approfondiremo l’implementazione dell’algoritmo ACO da zero per affrontare due tipi di problemi distinti.

I problemi che affronteremo sono il Problema del Commesso Viaggiatore (TSP) e il Problema di Assegnazione Quadratica (QAP). Perché proprio questi due? Beh, il TSP è una sfida classica e ACO si rivela un algoritmo efficace per trovare il percorso più economico attraverso un grafo. D’altra parte, il Problema di Assegnazione Quadratica rappresenta una classe diversa di problemi legati all’ottimizzazione dell’arrangiamento di oggetti e in questo post voglio dimostrare che ACO può essere uno strumento prezioso anche per risolvere tali problemi di assegnazione. Questa versatilità rende l’algoritmo ACO applicabile a una vasta gamma di problemi. Infine, condividerò alcuni consigli per ottenere soluzioni migliorate più rapidamente.

Problema del Commesso Viaggiatore

Il TSP è facile da descrivere ma può rappresentare una sfida significativa nella ricerca di una soluzione. Ecco la definizione di base: ti viene assegnato il compito di scoprire il percorso più breve che visita tutti i nodi in un grafo. Questo problema rientra nella categoria dei problemi NP-hard, il che implica che se provi ad esplorare tutte le possibili strade, potrebbe richiedere un tempo impraticabile per trovare la soluzione. Invece, un approccio più efficace è cercare una soluzione di alta qualità entro un periodo di tempo ragionevole e questo è esattamente quello che otterremo utilizzando ACO.

Definizione del Problema

Con il seguente codice, possiamo creare un’istanza TSP con un dato numero di nodi:

import itertoolsimport mathimport randomfrom typing import Tupleimport networkx as nximport networkx.algorithms.shortest_paths.dense as nxalgclass TSP:    """    Crea un problema TSP con un certo numero di nodi    """    def __init__(self, nodes: int = 30, dimensions: Tuple[int, int] = (1000, 1000), seed: int = 5):        if seed:            random.seed(seed)        graph = nx.Graph()        nodes_dict = dict()        for i in range(nodes):            nodes_dict[i] =…