Spaces:
Sleeping
Sleeping
| title: Tour Generator GA | |
| emoji: 🚀 | |
| colorFrom: red | |
| colorTo: purple | |
| sdk: docker | |
| pinned: false | |
| license: apache-2.0 | |
| # tour_ga — Generatore di tour turistici con NSGA-II e TOP-TW | |
| Progetto Python per la generazione automatica di tour personalizzati in città (Roma come caso di studio) tramite un algoritmo genetico multi-obiettivo. Il problema è modellato come **Team Orienteering Problem with Time Windows (TOP-TW)** e risolto con una variante di **NSGA-II** (Non-dominated Sorting Genetic Algorithm II, Deb et al., 2002). | |
| --- | |
| ## Indice | |
| 1. [Il problema: TOP-TW](#1-il-problema-top-tw) | |
| 2. [Fondamenti teorici: NSGA-II](#2-fondamenti-teorici-nsga-ii) | |
| 3. [Struttura del progetto](#3-struttura-del-progetto) | |
| 4. [Modello dati](#4-modello-dati) | |
| 5. [Profilo turista (TouristProfile)](#5-profilo-turista-touristprofile) | |
| 6. [Funzione fitness multi-obiettivo](#6-funzione-fitness-multi-obiettivo) | |
| 7. [Operatori genetici](#7-operatori-genetici) | |
| 8. [Riparazione genetica (Repair Engine)](#8-riparazione-genetica-repair-engine) | |
| 9. [Greedy Seeding](#9-greedy-seeding) | |
| 10. [Modello di trasporto realistico](#10-modello-di-trasporto-realistico) | |
| 11. [Configurazione e avvio](#11-configurazione-e-avvio) | |
| 12. [Risultati di esempio](#12-risultati-di-esempio) | |
| 13. [Riferimenti](#13-riferimenti) | |
| --- | |
| ## 1. Il problema: TOP-TW | |
| Il **Team Orienteering Problem with Time Windows** è una generalizzazione del Travelling Salesman Problem in cui: | |
| - Esiste un insieme di **Punti di Interesse (PoI)** con uno score di attrattività, una durata di visita stimata e una finestra temporale di apertura `[open, close]`. | |
| - Non tutti i PoI possono essere visitati entro il **budget di tempo** giornaliero. | |
| - L'obiettivo è selezionare e ordinare un sottoinsieme di PoI in modo da **massimizzare lo score totale** rispettando i vincoli temporali. | |
| In questo progetto il problema viene esteso con tre obiettivi competitivi simultanei: | |
| | Obiettivo | Direzione | Significato | | |
| |-----------|-----------|-------------| | |
| | `total_score` | Massimizza | Interesse culturale/gastronomico del tour | | |
| | `total_distance` | Minimizza | Fatica e costi di spostamento | | |
| | `time_penalty` | Minimizza | Sforamento del budget giornaliero | | |
| La natura multi-obiettivo rende la ricerca di un'unica soluzione ottima impossibile: esistono molteplici soluzioni di compromesso (fronte di Pareto) tra le quali il turista sceglie in base alle proprie preferenze. | |
| --- | |
| ## 2. Fondamenti teorici: NSGA-II | |
| L'algoritmo NSGA-II (Deb, Pratap, Agarwal, Meyarivan — *IEEE Transactions on Evolutionary Computation*, Vol. 6, No. 2, 2002) risolve i tre limiti principali del suo predecessore NSGA: | |
| 1. **Complessità computazionale** — Il sorting non-dominato originale era O(MN³). NSGA-II lo riduce a **O(MN²)** con un algoritmo di conteggio della dominanza. | |
| 2. **Mancanza di elitismo** — NSGA-II combina popolazione corrente e figli in un pool di 2N individui e seleziona i migliori N: le soluzioni eccellenti non vengono mai perse. | |
| 3. **Parametro di sharing** — Sostituito dalla **crowding distance**, una metrica parameter-free che misura la densità delle soluzioni nell'intorno di un individuo nello spazio degli obiettivi. | |
| ### 2.1 Fast Non-Dominated Sorting | |
| Per ogni individuo `i` si calcolano: | |
| - `dom_count[i]`: numero di individui che dominano `i` | |
| - `dom_set[i]`: insieme degli individui dominati da `i` | |
| Un individuo `A` **domina** `B` se è migliore o uguale su tutti gli obiettivi e strettamente migliore su almeno uno. Gli individui con `dom_count = 0` formano il **Fronte 1** (Pareto front). Rimuovendo il fronte 1 e ripetendo si ottengono i fronti successivi. La complessità totale è **O(MN²)**. | |
| ### 2.2 Crowding Distance | |
| Per ogni fronte, la crowding distance di un individuo `i` è la somma delle distanze normalizzate tra i vicini immediati lungo ciascun obiettivo: | |
| ``` | |
| CD(i) = Σ_m |f_m(i+1) - f_m(i-1)| / (f_m_max - f_m_min) | |
| ``` | |
| Gli individui agli estremi del fronte ricevono distanza infinita. La crowding distance alta indica un individuo in una regione poco affollata — preferito nella selezione per mantenere diversità. | |
| ### 2.3 Crowded-Comparison Operator | |
| Nella selezione a torneo, un individuo `A` è preferito a `B` se: | |
| - `rank(A) < rank(B)` (rango Pareto migliore), oppure | |
| - `rank(A) == rank(B)` e `crowd(A) > crowd(B)` (regione meno affollata) | |
| ### 2.4 Ciclo evolutivo principale | |
| ``` | |
| Inizializzazione popolazione P (greedy seeding + casuale riparato) | |
| ↓ | |
| Valutazione fitness (3 obiettivi) | |
| ↓ | |
| Fast non-dominated sort → assegna rank e crowding distance | |
| ↓ | |
| ┌─────────────────────────────────────────────────────────┐ | |
| │ Selezione torneo (crowded-comparison) │ | |
| │ Crossover (OX | PoI-aware, prob cx_prob) │ | |
| │ Mutazione (swap | insert | reverse | add-remove) │ | |
| │ Riparazione (categoria → TW → budget → cap → pasto) │ | |
| │ → popolazione figli Q (size N) │ | |
| └─────────────────────────────────────────────────────────┘ | |
| ↓ | |
| Unione R = P ∪ Q (size 2N) | |
| ↓ | |
| Non-dominated sort su R → seleziona migliori N → nuova P | |
| ↓ | |
| Criterio di stop? (max generazioni | stagnazione) | |
| ↓ NO ↓ SÌ | |
| (loop) Restituisce Fronte 1 | |
| ``` | |
| ### 2.5 Adattamenti al TOP-TW | |
| L'NSGA-II standard opera su cromosomi di lunghezza fissa con variabili continue. Per il TOP-TW sono stati introdotti: | |
| - **Cromosomi a lunghezza variabile** — lista ordinata di PoI (sottoinsieme del pool, non permutazione completa) | |
| - **Repair-before-evaluation** — ogni individuo viene riparato dopo ogni operatore genetico, prima della valutazione fitness | |
| - **Gene Jolly** (via `add_remove_mutation`) — placeholder che viene sostituito con il PoI più conveniente disponibile | |
| - **Penalità dinamica sulle attese** — scoraggia tour con buchi temporali lunghi | |
| --- | |
| ## 3. Struttura del progetto | |
| ``` | |
| tour_generator_ga/ | |
| ├── core/ | |
| │ ├── models.py # PoI, Individual, TourSchedule, FitnessScore | |
| │ ├── distance.py # DistanceMatrix (Haversine × 1.3) | |
| │ ├── fitness.py # FitnessEvaluator multi-obiettivo | |
| │ └── profile.py # TouristProfile + modello trasporto realistico | |
| ├── ga/ | |
| │ ├── operators.py # crossover (OX, PoI-aware), mutation, selection | |
| │ ├── repair.py # RepairEngine: 7 step di riparazione | |
| │ └── seeding.py # GreedySeeder: costruzione iniziale α-greedy | |
| ├── data/ # (placeholder per loader OSM/CSV) | |
| ├── solver.py # NSGA2Solver: ciclo evolutivo completo | |
| ├── demo_rome.py # Demo con dataset Roma e confronto profili | |
| └── README.md | |
| ``` | |
| --- | |
| ## 4. Modello dati | |
| ### `PoI` | |
| ```python | |
| @dataclass | |
| class PoI: | |
| id: str | |
| name: str | |
| lat, lon: float | |
| score: float # attrattività [0, 1] | |
| visit_duration: int # minuti di visita | |
| time_window: TimeWindow # (open, close) in minuti dalla mezzanotte | |
| category: PoICategory # MUSEUM | MONUMENT | RESTAURANT | BAR | GELATERIA | PARK | VIEWPOINT | |
| tags: list[str] # es. ["arte", "antico", "fotogenico"] | |
| ``` | |
| ### `Individual` (cromosoma) | |
| ```python | |
| class Individual: | |
| genes: list[PoI] # sequenza ordinata del tour | |
| fitness: FitnessScore # calcolata dopo evaluate() | |
| _schedule: TourSchedule # cache dello schedule decodificato | |
| ``` | |
| La rappresentazione come lista ordinata permette di codificare naturalmente sia l'insieme dei PoI visitati sia l'ordine di visita, senza vincoli di lunghezza fissa. | |
| ### `TourSchedule` | |
| Output della decodifica del cromosoma: per ogni PoI vengono calcolati orario di arrivo, attesa all'apertura e orario di partenza. Il campo `total_wait` traccia i minuti di attesa cumulati e contribuisce alla penalità fitness. | |
| ### `PoICategory` | |
| ``` | |
| MUSEUM | MONUMENT | RESTAURANT | BAR | GELATERIA | PARK | VIEWPOINT | |
| ``` | |
| La distinzione tra `RESTAURANT` (pasto formale) e `BAR`/`GELATERIA` (sosta breve) permette al `RepairEngine` di applicare vincoli differenziati per tipo di sosta alimentare. | |
| --- | |
| ## 5. Profilo turista (TouristProfile) | |
| Il `TouristProfile` è l'oggetto centrale che attraversa l'intero pipeline e determina il comportamento di ogni componente. | |
| ```python | |
| @dataclass | |
| class TouristProfile: | |
| transport_mode: TransportMode # WALK | CAR | TRANSIT | MIXED | |
| mobility: MobilityLevel # NORMAL | LIMITED | |
| allowed_categories: list[str] # categorie PoI ammesse | |
| want_lunch: bool # richiede sosta pranzo | |
| want_dinner: bool # richiede sosta cena | |
| lunch_time: int # orario preferito pranzo (minuti) | |
| dinner_time: int # orario preferito cena (minuti) | |
| meal_window: int # flessibilità ±minuti attorno all'orario | |
| max_bar_stops: int = 1 # max soste bar nel tour | |
| max_gelateria_stops: int = 1 # max soste gelateria nel tour | |
| tag_weights: dict[str, float] # boost per tag di interesse | |
| max_entry_fee: float | None # budget biglietti per PoI | |
| group_size: int = 1 # persone (influenza durata visite) | |
| ``` | |
| **Profili predefiniti disponibili:** | |
| | Factory | Modalità | Categorie | Pasti | | |
| |---------|----------|-----------|-------| | |
| | `profile_cultural_walker()` | WALK | museum, monument, viewpoint, restaurant | pranzo | | |
| | `profile_foodie_transit()` | TRANSIT | restaurant, bar, gelateria, monument, viewpoint | pranzo + cena | | |
| | `profile_family_mixed()` | MIXED / LIMITED | monument, park, viewpoint, restaurant | pranzo | | |
| | `profile_art_lover_car()` | CAR | museum, monument | pranzo | | |
| **Effetti sul pipeline:** | |
| - `DistanceMatrix` — usa `profile.travel_time_min(km)` per i tempi di percorrenza | |
| - `GreedySeeder` — filtra `allowed_pois` per categoria; usa `effective_score()` (con boost tag) | |
| - `RepairEngine` — filtra categorie, applica cap ristoranti/snack, garantisce slot pasto | |
| - `FitnessEvaluator` — calcola score con boost da `tag_weights`; penalizza pasti mancanti | |
| --- | |
| ## 6. Funzione fitness multi-obiettivo | |
| La fitness è calcolata in `FitnessEvaluator.evaluate()` e comprende tre componenti separate per NSGA-II e uno scalare aggregato per confronti rapidi (tournament selection): | |
| ### Score effettivo con boost | |
| ```python | |
| effective_score(poi) = min(poi.score × Π(1 + tag_weight - 1), 1.5) | |
| ``` | |
| I `tag_weights` del profilo amplificano i PoI tematicamente rilevanti (es. `arte × 1.4` per un turista culturale). Il cap a 1.5 evita distorsioni eccessive. | |
| ### Scalare aggregato | |
| ``` | |
| scalar = w_score × norm(total_score) | |
| - w_dist × norm(total_distance) | |
| - time_over_penalty # solo sullo sforamento, non sull'uso del budget | |
| - wait_penalty # penalizza attese cumulate > 5 min | |
| - meal_penalty # penalizza slot pasto non coperti | |
| ``` | |
| La scelta deliberata di **non penalizzare l'uso del budget** (solo lo sforamento) evita che il GA produca tour brevissimi per minimizzare il tempo. Un tour di 10 ore che rispetta il budget di 11 ore non è peggio di uno da 3 ore. | |
| ### I tre obiettivi Pareto | |
| | Obiettivo | Misura | Direzione | | |
| |-----------|--------|-----------| | |
| | `total_score` | score effettivo cumulato | Massimizza | | |
| | `total_distance` | km percorsi (Haversine × 1.3) | Minimizza | | |
| | `total_time` | minuti totali del tour | Minimizza | | |
| La dominanza Pareto è implementata in `FitnessScore.dominates()`: | |
| ```python | |
| def dominates(self, other) -> bool: | |
| better_or_equal = (score ≥ and dist ≤ and time ≤) | |
| strictly_better = (score > or dist < or time <) | |
| return better_or_equal and strictly_better | |
| ``` | |
| --- | |
| ## 7. Operatori genetici | |
| ### Selezione | |
| **Tournament selection** con `k=3` candidati casuali. Con `use_pareto=True` (default) preferisce rango Pareto basso e crowding distance alta, implementando l'operatore crowded-comparison di NSGA-II. | |
| ### Crossover | |
| **Order Crossover (OX) adattato** — Preserva l'ordine relativo dei PoI condivisi tra i genitori senza duplicati. Adattato al TOP-TW per gestire cromosomi a lunghezza variabile (sottoinsiemi, non permutazioni complete). | |
| ``` | |
| Genitore A: [Trevi, Navona, Pantheon, Pranzo, Colosseo] | |
| Genitore B: [Colosseo, Pranzo, Borghese, Trevi, Castel] | |
| Segmento da A (pos 1-2): [Navona, Pantheon] | |
| Riempimento da B (escl. duplicati): [Colosseo, Pranzo, Trevi, Castel] | |
| Figlio: [Colosseo, Navona, Pantheon, Pranzo, Trevi, Castel] | |
| ``` | |
| **PoI-aware Crossover** — Scambia interi blocchi per categoria (es. tutti i musei da A, tutti i ristoranti da B). Preserva la "nicchia tematica" del genitore e mantiene la coerenza del profilo turista. | |
| ### Mutazione | |
| Quattro operatori applicati con probabilità adattiva: | |
| | Operatore | Effetto | Caso d'uso | | |
| |-----------|---------|------------| | |
| | `swap_mutation` | Scambia 2 PoI nella sequenza | Esplorazione locale | | |
| | `insert_mutation` | Rimuove e reinserisce un PoI | Fix ordinamento temporale | | |
| | `reverse_segment_mutation` | Inverte un sottosegmento | Elimina crossing geografici | | |
| | `add_remove_mutation` | Aggiunge/rimuove un PoI dal pool ammesso | Modifica lunghezza tour | | |
| La `add_remove_mutation` opera **solo sul pool filtrato** per le categorie del profilo — non può mai inserire un ristorante nel tour di un turista che li ha esclusi. | |
| --- | |
| ## 8. Riparazione genetica (Repair Engine) | |
| Ogni individuo viene riparato dopo ogni operatore genetico, prima della valutazione fitness. La pipeline di riparazione ha **7 step in sequenza**: | |
| ``` | |
| 1. _filter_allowed_categories → rimuove PoI di categorie non ammesse | |
| 2. _sort_by_earliest_deadline → riordina per orario di apertura (EDF) | |
| 3. repair_time_windows → rimuove PoI con TW violata o attesa > max_wait_min | |
| 4. repair_budget → rimuove PoI a minor score/durata finché budget rispettato | |
| 5. _cap_restaurants → limita ristoranti formali al numero di slot pasto | |
| 6. _cap_snacks → limita bar e gelaterie ai massimi del profilo | |
| 7. _ensure_meal_slots → garantisce un ristorante per ogni slot pasto richiesto | |
| ``` | |
| ### Step 3: max_wait_min | |
| Il parametro `max_wait_min` (default 30) definisce la massima attesa tollerata per qualsiasi PoI. Un ristorante che apre alle 12:00 e a cui si arriva alle 9:30 viene **rimosso** — non ha senso aspettare 2 ore e mezza. L'eccezione è `_ensure_meal_slots`, che tolera fino a 45 minuti di attesa per garantire la sosta pranzo/cena. | |
| ### Step 7: strategia di inserimento/sostituzione | |
| Quando deve garantire un pasto, `_ensure_meal_slots` prova due strategie: | |
| 1. **Inserimento diretto** — aggiunge il ristorante nella posizione temporalmente corretta senza sforare il budget. | |
| 2. **Sostituzione** — se non c'è spazio, rimuove il PoI con il peggior rapporto score/durata e lo sostituisce con il ristorante. Questo evita che tour a budget pieno perdano la garanzia del pasto. | |
| --- | |
| ## 9. Greedy Seeding | |
| La popolazione iniziale è costruita con una strategia mista 20/20/60: | |
| | Quota | Strategia | Scopo | | |
| |-------|-----------|-------| | |
| | 20% | Greedy puro (`alpha=0`) | Massima qualità iniziale, convergenza rapida | | |
| | 20% | α-greedy perturbato (`alpha` da 0.15 a 0.50) | Varietà controllata vicino all'ottimo | | |
| | 60% | Casuale riparato | Massima diversità genetica | | |
| ### Criterio greedy: ratio score/overhead | |
| ```python | |
| ratio = effective_score(poi) / (travel_min + wait_min + visit_duration) | |
| ``` | |
| Dove `effective_score` include già i boost da `tag_weights` del profilo. Il criterio seleziona il PoI che massimizza il valore per minuto di tempo investito (spostamento + attesa + visita). | |
| ### Restricted Candidate List (GRASP-like) | |
| Con `alpha > 0`, invece di scegliere sempre il candidato migliore, si sceglie **casualmente tra il top 20%** per ratio. Questo produce soluzioni diverse ma ancora di buona qualità, avvicinandosi alla strategia GRASP (Greedy Randomized Adaptive Search Procedure). | |
| Tutti gli individui iniziali (greedy inclusi) passano per `repair.repair()` per garantire la coerenza con i vincoli del profilo fin dalla prima generazione. | |
| --- | |
| ## 10. Modello di trasporto realistico | |
| Il calcolo dei tempi di percorrenza in `profile.travel_time_min(km)` usa un modello che riflette la realtà urbana: | |
| ### WALK | |
| ``` | |
| t = km / v_walk | |
| ``` | |
| - `v_walk_normal = 4.5 km/h`, `v_walk_limited = 3.0 km/h` | |
| ### TRANSIT (bus + metro) | |
| ``` | |
| if km < 0.40: # soglia: prendere il mezzo non conviene | |
| t = km / v_walk | |
| else: | |
| t = km / 20.0 + 10 min # 10 min overhead (attesa + fermata) | |
| ``` | |
| L'overhead fisso di 10 minuti per tratta modella la realtà di Roma: frequenza media bus 8-12 minuti, metro 4-5 minuti, più il cammino alle fermate. | |
| ### CAR / TAXI | |
| ``` | |
| t = km / 25.0 + 5 min # 5 min overhead parcheggio | |
| ``` | |
| ### MIXED | |
| Per distanze sotto `600 m` si usa `v_walk`; oltre si usa la velocità transit con overhead. | |
| --- | |
| ## 11. Configurazione e avvio | |
| ### Requisiti | |
| ``` | |
| Python ≥ 3.10 (per syntax X | None nei type hint) | |
| Nessuna dipendenza esterna (stdlib only) | |
| ``` | |
| ### SolverConfig | |
| ```python | |
| from tour_ga.solver import SolverConfig | |
| config = SolverConfig( | |
| pop_size = 80, # dimensione popolazione | |
| max_generations = 300, # generazioni massime | |
| cx_prob = 0.85, # probabilità crossover | |
| mut_prob = 0.20, # probabilità mutazione | |
| tournament_k = 3, # candidati per torneo | |
| stagnation_limit = 50, # early stop per stagnazione | |
| start_time = 540, # 09:00 (minuti dalla mezzanotte) | |
| budget = 480, # 8 ore di tour | |
| start_lat = 41.896, # coordinate punto di partenza | |
| start_lon = 12.484, | |
| max_wait_min = 30, # attesa massima tollerata per PoI | |
| w_score = 0.50, # peso obiettivo score | |
| w_dist = 0.20, # peso obiettivo distanza | |
| w_time = 0.30, # peso penalità tempo | |
| ) | |
| ``` | |
| ### Avvio base | |
| ```python | |
| from tour_ga.core.models import PoI, PoICategory, TimeWindow | |
| from tour_ga.core.distance import DistanceMatrix | |
| from tour_ga.core.profile import profile_cultural_walker | |
| from tour_ga.solver import NSGA2Solver, SolverConfig | |
| pois = [...] # lista di PoI | |
| profile = profile_cultural_walker() | |
| dm = DistanceMatrix(pois, profile=profile) | |
| dm.build() # calcola matrice distanze (una volta sola) | |
| solver = NSGA2Solver(pois, dm, config, profile=profile) | |
| pareto_front = solver.solve() # restituisce lista di Individual | |
| # Selezione della soluzione consigliata dal fronte | |
| best = max(pareto_front, key=lambda x: x.fitness.scalar) | |
| schedule = solver.evaluator.decode(best) | |
| print(schedule.summary()) | |
| ``` | |
| ### Profilo custom | |
| ```python | |
| from tour_ga.core.profile import TouristProfile, TransportMode | |
| profile = TouristProfile( | |
| transport_mode = TransportMode.TRANSIT, | |
| allowed_categories = ["monument", "viewpoint", "bar"], | |
| want_lunch = False, | |
| want_dinner = False, | |
| max_bar_stops = 2, | |
| tag_weights = {"fotogenico": 1.5, "panorama": 1.3}, | |
| ) | |
| ``` | |
| ### Callback di monitoraggio | |
| ```python | |
| def progress(gen, pareto_front, stats): | |
| print(f"Gen {gen}: pareto={stats['pareto_size']}, " | |
| f"best={stats['best_scalar']:.4f}, " | |
| f"feasible={stats['feasible_pct']:.0f}%") | |
| front = solver.solve(callback=progress) | |
| ``` | |
| ### Demo completa | |
| ```bash | |
| python tour_ga/demo_rome.py | |
| ``` | |
| --- | |
| ## 12. Risultati di esempio | |
| Configurazione: `budget=660 min` (11h), `start_time=570` (09:30), `pop_size=60`, `max_generations=200`, Roma. | |
| ### Profilo gastronomico con mezzi (TRANSIT, pranzo + cena) | |
| ``` | |
| 09:42–10:12 Fontana di Trevi | |
| 10:24–10:54 Piazza di Spagna | |
| 11:08–11:53 Piazza Navona | |
| 11:56–12:16 Sant'Eustachio il Caffè ← bar pomeridiano | |
| 12:27–13:27 Osteria del Rione ← pranzo garantito | |
| 13:41–15:11 Castel Sant'Angelo | |
| 15:24–16:24 Pantheon | |
| 16:37–18:07 Foro Romano | |
| 18:21–18:41 Fatamorgana ← gelateria pomeridiana | |
| 19:00–20:20 Ristorante San Pietro ← cena garantita (attesa 4 min) | |
| Totale: 650 min, 10.9 km, attese 4 min | |
| Composizione: 1×bar, 1×gelateria, 4×monument, 2×restaurant, 2×viewpoint | |
| ``` | |
| ### Profilo culturale a piedi (WALK, solo pranzo) | |
| ``` | |
| 09:39–10:09 Fontana di Trevi | |
| 10:18–10:48 Piazza di Spagna | |
| 11:06–11:51 Piazza Navona | |
| 12:00–13:00 Osteria del Rione ← pranzo (attesa 3 min) | |
| 13:05–14:05 Pantheon | |
| 14:21–15:51 Foro Romano | |
| 16:01–18:01 Colosseo | |
| 18:32–20:02 Trastevere | |
| Totale: 632 min, 8.1 km, attese 3 min | |
| ``` | |
| ### Profilo custom: solo viste, nessun pasto | |
| ``` | |
| 09:39–10:09 Fontana di Trevi | |
| 10:18–10:48 Piazza di Spagna | |
| 11:06–11:51 Piazza Navona | |
| 11:54–12:14 Sant'Eustachio il Caffè | |
| 12:16–13:16 Pantheon | |
| 13:33–15:03 Castel Sant'Angelo | |
| 15:14–15:34 Fatamorgana | |
| Totale: 364 min, 5.5 km | |
| ``` | |
| --- | |
| ## 13. Riferimenti | |
| ### Articolo scientifico principale | |
| Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). **A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II**. *IEEE Transactions on Evolutionary Computation*, 6(2), 182–197. | |
| [https://www.cse.unr.edu/~sushil/class/gas/papers/nsga2.pdf](https://www.cse.unr.edu/~sushil/class/gas/papers/nsga2.pdf) | |
| Il paper introduce tre contributi fondamentali qui implementati: il fast non-dominated sorting O(MN²) tramite conteggio della dominanza (implementato in `solver.py::_fast_non_dominated_sort`), la crowding distance come meccanismo di diversità parameter-free (implementato in `_assign_crowding_distance`), e il crowded-comparison operator per selezione a torneo (in `operators.py::tournament_select`). | |
| ### Riferimento divulgativo | |
| Non-Dominated Sorting Genetic Algorithm 2 (NSGA-II) — GeeksforGeeks. | |
| [https://www.geeksforgeeks.org/deep-learning/non-dominated-sorting-genetic-algorithm-2-nsga-ii/](https://www.geeksforgeeks.org/deep-learning/non-dominated-sorting-genetic-algorithm-2-nsga-ii/) | |
| ### Problema di riferimento | |
| Vansteenwegen, P., Souffriau, W., & Van Oudheusden, D. (2011). **The Orienteering Problem: A Survey**. *European Journal of Operational Research*, 209(1), 1–10. | |
| Chao, I. M., Golden, B. L., & Wasil, E. A. (1996). **The Team Orienteering Problem**. *European Journal of Operational Research*, 88(3), 464–474. | |
| ### Calcolo distanze | |
| Formula di Haversine per la distanza geodetica tra due coordinate GPS, con fattore correttivo 1.3 per approssimare il percorso urbano reale rispetto alla linea d'aria. |