Risolvere problemi di ottimizzazione e migliorare i risultati con ACO in Python
Bentornato! Nel mio messaggio precedenteHo introdotto i fondamenti di Ant Colony Optimization (ACO). In questa puntata approfondiremo l’implementazione dell’algoritmo ACO da zero per affrontare due distinti tipi di problemi.
I problemi che affronteremo sono il Problema del Commesso Viaggiatore (TSP) e il Problema dell’Assegnazione Quadratica (QAP). Perché questi due? Bene, il TSP è una sfida classica e ACO sembra essere un algoritmo efficace per trovare il percorso più conveniente attraverso un grafico. D’altra parte, il problema dell’assegnazione quadratica rappresenta una diversa classe di problemi legati all’ottimizzazione della disposizione degli elementi e in questo post mi propongo di dimostrare che ACO può essere uno strumento prezioso per risolvere anche tali problemi relativi all’assegnazione. Questa versatilità rende l’algoritmo ACO applicabile ad un’ampia gamma di problemi. Infine, condividerò alcuni suggerimenti per ottenere soluzioni migliori più rapidamente.
Il TSP è semplice da descrivere ma può rappresentare una sfida significativa nel trovare una soluzione. Ecco la definizione di base: hai il compito di scoprire il percorso più breve che visita tutti i nodi in un grafico. Questo problema rientra nella categoria di Problemi NP-difficiliil che implica che se si tenta di esplorare tutti i percorsi possibili, può essere necessario un tempo impraticabile per trovare la soluzione. Invece, un approccio più efficace consiste nel cercare una soluzione di alta qualità entro un periodo di tempo ragionevole, ed è esattamente ciò che realizzeremo utilizzando ACO.
Definizione del problema
Con il seguente codice possiamo creare un’istanza TSP con un determinato numero di nodi:
import itertools
import math
import random
from typing import Tupleimport networkx as nx
import networkx.algorithms.shortest_paths.dense as nxalg
class TSP:
"""
Creates a TSP problem with a certain number of nodes
"""
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) =…
Fonte: towardsdatascience.com
