Problemes d'Optimització Combinatòria

La Optimització Combinatòria és una branca de la optimització. El seu domini consisteix en problemes d'optimització a on el conjunt de possibles solucions és discret o es pot reduir a un conjunt discret.

Quan s'ha de treballar amb problemes d'optimització combinatòria, l'objectiu és trobar la millor solució possible que existeixi, també anomenada solució òptima, que és aquella que minimitza una funció de cost donada.

Si el problema no és complexe, existeixen tècniques per a resoldre aquest tipus de problemes, com el Branch and Bound, Branch and Cut, etc. Quan va agumentant la complexitat de l'espai de cerca, el cost en temps d'execució d'aquests algorismes pot augmentar de forma exponencial, cosa que fa que la resolució d'aquests problemes de forma òptima no sigui una opció ja que trigaria massa temps.

Una altra possiblitat per atacar aquest tipus de problemes, consisteix en trobar una solució subòptima (una solució bona però que no és la millor), però en un temps reanoble. Si la complexitat del problema és petita, aquests algorismes també poden trobar la solució òptima.

Aquestes darreres tècniques es poden separar en dos grans grups:

  • Heurístiques

  • Metaheurístiques

A més a més d'aquests grups, als darrers anys ha sorgit una nova tecnologia que es pot emprar per a aquest tipus de problemes, el Raonament Basat en Casos o CBR (Case Based Reasoning).

Heurístiques

Les tècniques heurístiques són algorismes que troben solucions de bona qualitat per a problemes combinatoris complexos explotant el coneixement del domini d'aplicació. Són fàcils d'implementar i obtenen bons resultats amb realtivament poc temps de computació; renuncien però, des del pun te vista teòric, a trobar la millor solució del problema. En problemes complexos, normalment no troben la solució òptima global.

Metaheurístiques

Els algorismes metaheurístics són algorismes de propòsit general, que no depenen del domini del problema, i que ofereixen bons resultats, però no la solució òptima. S'acostumen a utilitzar per als problemes dels quals no existeix cap algorisme o heurística específics que els resolgui, o bé quan no és pràctic implementar aquests mètodes.

Case Based Reasoning (CBR) o Raonament Basat en Casos

El Raonament Basat en Casos és una tècnica d'Intel·ligència Artificial que aprofita experiències anteriors per a resoldre nous problemes mitjançant la hipòtesi de que a problemes ssemblants, solucions semblants.

Donat un problema a resoldre, el CBR cerca, en una base de dades anomenada Base de Casos, problemes ssemblants que anteriorment s'hagin resolt amb èxit, anomenats casos, i adapta les solucions per a donar una solució del problema actual. Aquest mecanisme de raonament és emprat pels humans en múltiples problemes i permet que sigui un sistema de comprensió senzilla.


Algorithms Classification

Figura basada en la següent imatge de la viquipèdia