Surrogate-Assisted Genetic Programming with Rank-Based Phenotypic Characterisation for Dynamic Multi-Mode Project Scheduling

Each language version is independently generated for its own context, not a direct translation.

🏗️ Il Problema: Costruire un grattacielo con il meteo che cambia

Immagina di dover organizzare la costruzione di un enorme grattacielo. Hai dei lavori da fare (i "lavori"), dei macchinari limitati (le "risorse") e delle regole ferree (non puoi mettere il tetto prima delle fondamenta). Questo è il problema di schedulazione.

Ma c'è un problema enorme: il meteo è imprevedibile! A volte un lavoro che pensavi durasse 2 giorni ne dura 5, a volte ne dura 1. Questo è il problema dinamico: devi prendere decisioni in tempo reale mentre il cantiere avanza, senza sapere esattamente cosa succederà domani.

Per gestire questo caos, gli ingegneri usano delle regole intuitive (chiamate "euristiche"). Ad esempio: "Se piove, lavora sui tetti interni; se c'è sole, posa i mattoni".

🧬 Il Metodo Vecchio: Evoluzione per tentativi ed errori

Per trovare la regola perfetta, gli scienziati usano un metodo chiamato Programmazione Genetica (GP). Immagina di avere una "scuola" di migliaia di regole diverse.

Le fai provare tutte su un simulatore al computer (come un videogioco di costruzione).
Quelle che fanno bene vengono "riprodotte" e mescolate per creare regole figlie migliori.
Quelle che falliscono vengono eliminate.

Il problema? Simulare un intero cantiere è lentissimo e costoso. È come se dovessi costruire il grattacielo vero e proprio ogni volta per vedere se una regola funziona. Per trovare la regola migliore, dovresti fare milioni di simulazioni, e il computer si blocca per giorni.

🚀 La Soluzione: L'Oracolo (Il Modello Surrogato)

Gli autori di questo paper hanno pensato: "E se invece di costruire il grattacielo ogni volta, avessimo un oracolo veloce che ci dice solo una stima di come andrà?"

Hanno creato un modello surrogato. È come un assistente intelligente che guarda una regola e dice: "Sembra che questa regola funzioni bene, non serve farla simulare per intero, fidati di me".

Ma c'è un ostacolo: come fa l'oracolo a capire se una regola è brava senza vederla all'opera? Deve avere un modo per "leggere il carattere" della regola.

👁️ La Chiave Segreta: La "Carta d'Identità" (Caratterizzazione Fenotipica)

Qui entra in gioco la parte geniale del paper: la Caratterizzazione Fenotipica basata sul Ranking.

Immagina che ogni regola sia un allenatore di calcio. Invece di guardare la partita intera (la simulazione costosa), l'oracolo guarda come l'allenatore sceglie i giocatori quando deve decidere chi mandare in campo.

La situazione: Arriva un momento di decisione (es. "Abbiamo 3 gru e 10 lavori da fare").
La lista: L'allenatore (la regola) guarda tutti i lavori disponibili e li mette in fila dal "più urgente" al "meno urgente".
La carta d'identità: Invece di scrivere cosa ha scelto, l'oracolo scrive l'ordine in cui li ha messi.
- Se la Regola A mette il "Lavoro X" al primo posto, la sua carta d'identità ha un "1" in quella posizione.
- Se la Regola B lo mette al decimo, la sua carta ha un "10".

Questa lista di numeri (il vettore) è la carta d'identità della regola. È veloce da calcolare!

🎯 Come funziona il nuovo sistema (SKGGP)

Ora il sistema funziona così:

Genera figli: Crea migliaia di nuove regole (figli) mescolando quelle vecchie.
Fai la foto: Calcola la "carta d'identità" (l'ordine di priorità) per ogni nuova regola.
Chiedi all'oracolo: L'oracato confronta la nuova carta d'identità con quelle delle regole che già sa essere brave. Se la nuova regola ha una carta d'identità simile a una regola "brava", l'oracolo dice: "Questa sembra promettente!".
Scegli i migliori: Si scelgono solo le regole che l'oracolo ha giudicate buone e solo quelle vengono mandate a fare la simulazione costosa e lenta.

🏆 I Risultati: Più veloci, ugualmente bravi

Grazie a questo trucco:

Risparmio di tempo: Il sistema trova regole eccellenti molto prima rispetto ai metodi vecchi.
Efficienza: Ha bisogno di fare molte meno simulazioni costose (fino al 40% in meno!).
Qualità: Le regole trovate sono almeno buone quanto quelle vecchie, ma sono arrivate lì molto più velocemente.

💡 In sintesi

Immagina di dover scegliere il miglior cuoco per un ristorante.

Metodo vecchio: Assumi 1000 cuochi, fai loro cucinare un banchetto intero per 3 giorni ciascuno, e vedi chi è il migliore. (Lento e costoso).
Metodo nuovo: Chiedi a ogni cuoco di scrivere la lista degli ingredienti che userebbe per un piatto difficile. Confronti queste liste con quelle dei cuochi famosi che già conosci. Se la lista è simile a quella di un cuoco stellato, lo assumi e gli fai cucinare davvero il piatto solo alla fine. (Veloce ed efficace).

Questo paper insegna a un computer a fare proprio questo: capire il "carattere" di una regola di decisione per prevedere il suo successo, risparmiando tempo e risorse preziose.

Each language version is independently generated for its own context, not a direct translation.

Titolo: Programmazione Genetica Assistita da Surrogati con Caratterizzazione Fenotipica Basata su Ranking per la Pianificazione Dinamica di Progetti Multi-Modalità

1. Il Problema: DMRCPSP

Il lavoro si concentra sul Problema di Pianificazione Dinamica delle Risorse con Vincoli e Multi-Modalità (DMRCPSP - Dynamic Multi-Mode Resource-Constrained Project Scheduling Problem).

Natura del problema: È una variante dinamica del classico MRCPSP in cui la durata esatta delle attività non è nota a priori, ma viene rivelata solo durante l'esecuzione del progetto.
Obiettivo: Prendere decisioni in tempo reale su quali attività eseguire e in quale modalità (ogni attività ha diverse modalità con durate e requisiti di risorse diversi), rispettando i vincoli di precedenza e di risorse rinnovabili, al fine di minimizzare la durata totale del progetto (makespan).
Sfida principale: Le soluzioni tradizionali basate su simulazioni sono computazionalmente costose. L'uso di regole euristiche evolve tramite Programmazione Genetica (GP) è promettente, ma richiede un numero elevato di valutazioni di fitness basate su simulazioni complete, rendendo il processo poco scalabile per ambienti decisionali dinamici.

2. Metodologia Proposta

Gli autori propongono un algoritmo di Programmazione Genetica Assistita da Surrogati (Surrogate-Assisted GP) per ridurre i costi computazionali mantenendo l'efficacia delle soluzioni. La metodologia si articola in tre componenti principali:

A. Nuova Caratterizzazione Fenotipica (Phenotypic Characterisation - PC):
- Il cuore dell'innovazione è un nuovo schema di PC specifico per il DMRCPSP. Le euristiche GP per questo problema sono composte da due alberi: una regola di ordinamento delle attività e una regola di selezione dei gruppi di attività.
- Lo schema esistente (basato su un singolo indice di scelta) non era applicabile perché il DMRCPSP richiede sia un ordinamento (ranking) che una selezione di sottoinsiemi.
- Soluzione: Viene proposto uno schema basato sul ranking. Per ogni "situazione decisionale" campionata dalla simulazione:
  1. Si calcolano i valori di priorità per tutte le coppie attività-modalità eleggibili.
  2. Si estrae il vettore dei rank (posizioni) di tutte le candidate, non solo della scelta finale.
  3. Si fa lo stesso per i gruppi di attività selezionati.
- Questi vettori di decisione vengono concatenati per formare un vettore fenotipico unico per ogni individuo GP, che cattura il comportamento di ordinamento dell'euristica in contesti rappresentativi.
B. Stima del Fitness tramite Modello Surrogato:
- Viene utilizzato un modello surrogato semplice basato sul vicino più prossimo (Nearest-Neighbour).
- Il modello non sostituisce la valutazione completa, ma stima il fitness degli individui intermedi (offspring) prima della simulazione costosa.
- La stima avviene calcolando la distanza di Manhattan tra il vettore PC del nuovo individuo e quelli degli individui già valutati nel database (della generazione corrente). Il fitness dell'individuo più vicino nello spazio dei PC viene assegnato come stima.
- Nota: Il database non accumula dati tra generazioni perché le simulazioni sono stocastiche (semi diversi), rendendo i valori di fitness non direttamente comparabili tra generazioni diverse.
C. Flusso dell'Algoritmo (SKGGP):
1. Si genera una popolazione di offspring intermedi.
2. Si calcolano i vettori PC per tutti gli offspring.
3. Si rimuovono i duplicati basandosi sul vettore PC.
4. Il modello surrogato stima il fitness degli offspring unici.
5. Si selezionano i migliori offspring (basati sulla stima) per sottoporli alla valutazione completa (simulazione reale).
6. Si procede con l'evoluzione.

3. Contributi Chiave

Superamento del gap nella PC per DMRCPSP: È il primo lavoro che definisce uno schema di caratterizzazione fenotipica adatto alla natura ibrida (ordinamento + selezione di sottoinsiemi) delle euristiche GP per la pianificazione dinamica multi-modalità.
Algoritmo SKGGP: Sviluppo di un framework GP assistito da surrogati che integra lo schema PC proposto, permettendo di identificare regole euristiche di alta qualità molto prima rispetto agli approcci GP tradizionali.
Analisi dell'Efficienza: Dimostrazione che l'uso di un moltiplicatore di offspring (generare più candidati di quelli necessari) combinato con la selezione surrogata migliora l'efficienza evolutiva con un overhead computazionale marginale.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su scenari con 200 attività, 3 modalità e 12 risorse, variando la complessità delle dipendenze (Order Strength). L'algoritmo proposto (SKGGP) è stato confrontato con lo stato dell'arte (KGGP).

Prestazioni: Le varianti SKGGP (specialmente con moltiplicatori $k=2$ e $k=4$ ) hanno superato lo stato dell'arte (KGGP) in termini di qualità della soluzione (makespan più basso) in tutti gli scenari testati.
Velocità di Convergenza: Le curve di convergenza mostrano che SKGGP raggiunge soluzioni di alta qualità significativamente più velocemente.
Risparmio di Budget: L'analisi mostra che SKGGP può risparmiare dal 20% al 40% delle valutazioni complete necessarie per raggiungere le stesse prestazioni di KGGP.
Overhead Computazionale: Il tempo richiesto per la stima surrogata (calcolo PC e distanza) è trascurabile rispetto alla simulazione completa (circa 1/20 - 1/40 del tempo totale).
Impatto del Moltiplicatore ( $k$ ):
- Aumentare il numero di offspring intermedi ( $k$ ) migliora la qualità della popolazione finale.
- Tuttavia, la precisione del modello surrogato diminuisce all'aumentare di $k$ (da ~80-90% per $k=1.5$ a ~50-60% per $k=4$ ).
- Nonostante la minore precisione a $k=4$ , l'approccio rimane efficace perché il numero assoluto di individui "correttamente aggiunti" (che migliorano la popolazione) aumenta, compensando gli errori di selezione.

5. Significato e Implicazioni

Questo lavoro è significativo perché:

Abilita l'uso pratico del GP in scenari dinamici complessi: Riducendo drasticamente il costo computazionale, rende fattibile l'uso di euristiche evolute in tempo reale per la gestione di progetti reali soggetti a incertezze.
Fornisce un nuovo paradigma di rappresentazione: Lo schema di PC basato sul ranking offre un modo più ricco e informativo per confrontare il comportamento delle euristiche rispetto ai metodi basati su singola scelta, preservando le relazioni semantiche tra le diverse opzioni.
Bilanciamento Efficienza/Qualità: Dimostra che è possibile ottenere guadagni sostanziali in termini di efficienza evolutiva con un investimento computazionale minimo, rendendo l'approccio scalabile per problemi di grandi dimensioni.

In sintesi, il paper risolve un collo di bottiglia computazionale critico nella pianificazione di progetti dinamici introducendo un metodo intelligente di filtraggio degli individui promettenti basato sul loro comportamento fenotipico, aprendo la strada a soluzioni di hyper-heuristics più robuste ed efficienti.