Home » Intelligenza Artificiale » 📋 URL
Problema di ottimizzazione semplice
Un problema di ottimizzazione P è composto dai seguenti elementi
\min\{f(x)\}\quad\text{o}\quad\max\{f(x)\}\\
S\\
x\in DDove:
- f(x): funzione a valori reali nella variabile x che chiamiamo funzione obiettivo
- D: il dominio di x
- S: insieme finito di vincoli
Ogni x\in D si dice soluzione di P. Una soluzione che soddisfi tutti i vincoli in S si dice ammissibile.
L’insieme delle soluzioni ammissibili di un problema di ottimizzazione P si indica con F(p).
Problema di ottimizzazione discreto
Se il dominio D del problema è discreto, il problema si dice si ottimizzazione discreta.
Se il dominio D è finito, si parla di ottimizzazione combinatoria.
Soluzioni ottime di un problema
Una soluzione si dice ottima se
f(x^*)\leq f(x)\quad\forall\,\,x\in F(p)
Problemi impossibili
Un problema di ottimizzazione si dice impossibile (infeasible) se non ammette alcuna soluzione ammissibile, si ha dunque
F(p)=\emptyset
Problemi illimitati
Un problema di ottimizzazione si dice illimitato (unbounded) se non esiste alcun limite inferire a f(x) (la funzione tende a \pm\infty) per x\in F(p).
Altri problemi di ottimizzazione
Dalla nozione di problema di ottimizzazione non siamo però in grado—nemmeno tramite metodi computazionali!—di ottenere delle soluzioni.
Dobbiamo dunque introdurre dei casi particolari in cui i problemi di ottimizzazione assumono delle caratteristiche specifiche.
Tratteremo problemi di:
- Programmazione lineare (LP: Linear Programming)
- Programmazione lineare intera (MIP: Mixed-Integer Programming)
- Programmazione con vincoli (CP: Constraint Programming)
- Soddisfacibilità booleana (SAT: boolean SATisfiability problem)
Spiegati in nella pagina sui diversi paradigmi di ottimizzazione.
Trattiamo però prima dei concetti legati all’ottimizzazione in generale.
Ricerca
Dato un problema di ottimizzazione P, la ricerca consiste nel risolvere una sequenza di restrizioni di P. Ogni restrizione P_i è ottenuta da P aggiungendo dei vincoli.
Si aggiungono tali vincoli perché si vuole cercare di restringere lo spazio delle soluzioni—per far diventare il problema più semplice.
Se la ricerca nello spazio delle soluzioni è esaustiva (ovvero copre tutto lo spazio) si ha
\bigcup_i F(P_i)=F(p)
A parole: la funzione F(\cdot) indica l’insieme delle soluzioni ammissibili. I problemi P_i sono i sotto-problemi ottenuti tramite l’aggiunta di vincoli. Stiamo dunque prendendo l’unione di tutte le soluzioni dei sotto-problemi, che equivalgono all’insieme delle soluzioni F(p) del problema originale.
La forma più esaustiva di ricerca consiste nel generare esplicitamente tutte le soluzioni possibili e verificare quali soddisfino i vincoli.
Delle tipologie di ricerca più evolute non hanno però bisogno di esplorare l’intero insieme delle soluzioni e riescono a ottimizzare la ricerca nella direzione della soluzione migliore. Alcuni algoritmi di ricerca più evoluti vengono trattati in questa pagina.
Rilassamento di un problema di ottimizzazione
Un rilassamento di un problema di ottimizzazione consiste in un altro problema di ottimizzazione che presenza però delle caratteristiche diverse, nello specifico si può:
- Eliminare alcuni vincoli
- Sostituire la funzione obiettivo f(x) con una sua approssimazinoe inferiore g(x), che permetta dunque di semplificare il problema.
Definizione formale
R si dice un rilassamento di P se:
- F(P)\subseteq F(R)
- g(x)\leq f(x)\quad\forall\,\,x\in F(p)
A parole: nel primo punto indichiamo che l’insieme delle soluzioni F(R), ovvero quelle del problema sul rilassamento R, sono un sottoinsieme delle soluzioni F(P) che risolvono il problema originale P.
Le soluzioni del rilassamento beneficiano inoltre delle seguenti proprietà:
- Se F(R)=\emptyset allora il problema P è impossibile
- Se x^* è una soluzione ottima in R e appartiene all’insieme delle soluzioni F(P) del problema originale, se vale
g(x^*)=f(x^*)
dunque che il valore restituito dalle funzioni obiettivo “rilassata” e originale tramite l’utilizzo di x^* è uguale, allora x^* è una soluzione ottima anche per il problema originale. - Se x^* è una soluzione ottima in R, allora il valore di g(x^*) è un limite inferiore valido per il valore ottimo di che risolve f(x)