Ottimizzazione Multi-Obiettivo

L'ottimizzazione multi-obiettivo affronta problemi della forma min/max f(x) = (f_1(x), f_2(x), ..., f_k(x)) con k≥2 obiettivi su un insieme di vincoli comune x ∈ X. In luogo di un singolo ottimo globale si cerca l'insieme Pareto-efficiente: x* è Pareto-ottimale se e solo se non esiste y ∈ X tale che f_i(y) ≤ f_i(x*) per ogni i con disuguaglianza stretta in almeno un j (Pareto 1906). Gli approcci di scalarizzazione si raggruppano in cinque famiglie: (1) Somma pesata — min Σ w_i f_i, recupera punti sull'inviluppo convesso della frontiera di Pareto ma manca le regioni non convesse; (2) Metodo ε-constraint (Haimes e altri 1971) — si ottimizza un obiettivo mentre gli altri sono vincolati come f_i ≤ ε_i; può percorrere l'intera frontiera; (3) Ordinamento lessicografico — gli obiettivi sono ottimizzati sequenzialmente per priorità e il valore ottimo precedente entra come vincolo nella fase successiva; (4) Goal programming (Charnes e Cooper 1961) — livello di aspirazione per obiettivo, minimizzando le deviazioni; (5) Metaeuristiche multi-obiettivo — NSGA-II (Deb e altri 2002), SPEA2 (Zitzler e altri 2001) evolvono una popolazione che converge in parallelo verso il fronte di Pareto. Complessità: ogni scalarizzazione è un LP se gli obiettivi sono lineari; enumerare o rappresentare l'intero insieme di Pareto è generalmente NP-difficile. Monografie canoniche: Miettinen (1999), Steuer (1986) ed Ehrgott (2005).