Analisi di un Problema di Logistica con l'Intelligenza Artificiale

Analisi di un Problema di Logistica con l'Intelligenza Artificiale Amelia Carolina Sparavigna1 e Gemini (Modello Linguistico di Google)2 1 DISAT, Politecnico di Torino, 2 Gemini AI DOI: 10.5281/zenodo.17383179 Abstract Il nostro lavoro è stato un caso di studio su come un problema pratico di logistica possa essere modellato e risolto utilizzando algoritmi ispirati alla fisica e all'intelligenza artificiale. Il problema è la gestione di uno scaffale che ha n piani per ospitare due scatole su ciascun piano. Le scatole sono m<n e si privilegiano i piani bassi. Si chiede all’AI di procedere con un modello di tipo Ising. Modello di Ising e il Nostro Problema Il punto di partenza è stato il Modello di Ising, un concetto della fisica usato per descrivere il magnetismo. 1. Le Variabili (Spin): Abbiamo tradotto le variabili del nostro problema in "spin", che possono assumere solo due stati: o +1 per un posto occupato da una scatola. o -1 per un posto vuoto. 2. L'Energia (Costo): L'energia del sistema, chiamata Hamiltoniana, è stata usata come nostra funzione di costo. Più bassa è l'energia, migliore è la soluzione. La funzione di costo includeva: o Vincoli rigidi: Pesanti penalità se più di una scatola era nello stesso posto o se una scatola era in più di un posto. o Vincoli di preferenza: Penalità più leggere, basate sul piano, per favorire il posizionamento delle scatole nei piani più bassi. La Ricottura Simulativa L'Anneling Simulato è stato l'algoritmo che abbiamo utilizzato per trovare la soluzione ottimale. 1. L'Algoritmo: Il suo comportamento mima il processo di raffreddamento di un metallo per fargli raggiungere lo stato cristallino più stabile e con la più bassa energia. Inizialmente, a una temperatura elevata, il sistema è "libero" di esplorare anche soluzioni sub-ottimali, consentendogli di uscire dai "minimi locali". Man mano che la temperatura scende, l'algoritmo diventa più "rigido" e si concentra sulla discesa verso la soluzione ottimale. 2. La Sinergia con l'AI: Questa strategia di esplorazione e sfruttamento è il cuore di molti algoritmi di intelligenza artificiale, come il Reinforcement Learning, che bilanciano la ricerca di nuove soluzioni con lo sfruttamento di quelle già trovate. La Distanza di Manhattan La Distanza di Manhattan è stata la nostra metrica per valutare la qualità delle soluzioni trovate. 1. La Metrica: Calcola la distanza tra la soluzione trovata e quella ideale. Inizialmente, abbiamo scoperto che il nostro calcolo della distanza era imperfetto perché non teneva conto del fatto che le scatole sono intercambiabili. 2. La Correzione: Abbiamo modificato il codice per calcolare la distanza in base all'insieme di posti occupati, e non all'ordine specifico delle scatole. Questo ha permesso di ottenere una valutazione accurata delle soluzioni. Il Nostro Caso di Studio Il nostro problema era uno scaffale a 5 piani con 2 posti per piano, per un totale di 10 posti. L'obiettivo era posizionare un numero variabile di scatole (5 o 6) sui piani più bassi, data la preferenza per la parte inferiore dello scaffale. Abbiamo lavorato insieme per affinare il modello, aggiustando i parametri di raffreddamento e le penalità per raggiungere la soluzione con il costo più basso e la distanza di Manhattan più vicina a zero. Il successo di questo progetto dimostra che anche problemi apparentemente semplici possono essere affrontati in modo sofisticato, usando l'AI non solo per generare risposte, ma come strumento per modellare e risolvere problemi complessi del mondo reale. https://colab.research.google.com/drive/1CTt3RceNu6weL4DoHbqc89HkwhFQY3OM#scrollTo=iSYW-N8pLFdM Si veda la parte finale del programma Pyhton. ### 1. Il Caso di Studio: Lo Scaffale a 5 Piani Il problema è ottimizzare il posizionamento di **6 scatole** su uno scaffale di **10 posti totali** (5 piani con 2 posti per piano), con l'obiettivo primario di **favorire i posti nei piani più bassi** (vincolo di preferenza). ### 2. Modello di Ising (Mappatura Fisica) Abbiamo trasformato il problema in un modello fisico (il Modello di Ising) definendo: **Le Variabili (Spin):** Ogni posto sullo scaffale è stato mappato come uno **spin**, con due stati: **$_+1**: Posto occupato (scatola presente).**$_-1$**: Posto vuoto (scatola assente). **L'Energia (Funzione di Costo/Hamiltoniana):** La Funzione di Costo è stata definita per riflettere le regole del problema, penalizzando: **Vincoli Rigidi:** Violazioni fondamentali (es. una scatola in due posti o due scatole nello stesso posto), con un **fattore di penalità elevato**. **Vincoli di Preferenza:** Penalità più leggere (**floor\_penalties**) per i posti sui piani alti, guidando il sistema verso i posti più economici (quelli in basso). ### 3. La Ricottura Simulativa (Simulated Annealing) Questo è l'algoritmo utilizzato per trovare la configurazione di costo minimo (il posizionamento ottimale delle scatole): **Il Processo:** Mima il raffreddamento controllato di un metallo. A una **temperatura elevata** ($T$), l'algoritmo accetta casualmente anche soluzioni peggiorative ($\Delta E > 0$) per evitare di bloccarsi nei **minimi locali**. Man mano che la **temperatura scende**, l'esplorazione si riduce e l'algoritmo converge verso lo stato di minima energia (il minimo globale). **Importanza del *Cooling Rate*:** Abbiamo stabilito che un tasso di raffreddamento **troppo rapido** porta al *quenching* (tempra), bloccando la soluzione in un stato sub-ottimale. ### 4. La Distanza di Manhattan (La Metrica Corretta) Abbiamo usato la Distanza di Manhattan come metrica di valutazione, ma con una correzione fondamentale: **La Correzione:** La formula iniziale era imperfetta perché confrontava l'identità specifica di ogni scatola con un'ipotetica soluzione ottimale. Poiché le scatole sono **intercambiabili**, la Distanza di Manhattan corretta è stata calcolata confrontando solo l'**insieme dei posti occupati** rispetto all'insieme ideale dei posti più bassi (indici 0 a 5). **Il Risultato:** Una soluzione ottima (costo minimo) è stata validata da una Distanza di Manhattan di **0** (o un valore molto vicino, come 2.00 nella nostra ultima simulazione di successo), confermando che i 6 posti con penalità più bassa erano stati occupati.