Optimisació combinatòria

La optimisació combinatòria és una branca de l'optimisació en matemàtiques aplicades i en ciències de la computació, relacionada en l'investigació d'operacions, Teoria algorítmica de l'informació i teoria de la complexitat computacional. També està relacionada en atres camps, com l'inteligència artificial i ingenieria de software. Els algoritmes d'optimisació combinatòria resolen instàncies de problemes que es creuen ser difícils en general, explorant l'espai de solucions (usualment gran) per a estes instàncies. Els algoritmes d'optimisació combinatòria conseguixen açò reduint el tamany efectiu de l'espai, i explorant l'espai de busca eficientement.

Els algoritmes d'optimisació combinatòria a sovint són implementats en llenguages imperatius com a C i C++ entre atres softwares inteligents en llenguages de programació llògics tals com Prolog, o inclús en llenguages multi-paradigma tals com Oz.

Per mig de l'estudi de la teoria de la complexitat computacional és possible comprendre l'importància de l'optimisació combinatòria. Els algoritmes d'optimisació combinatòria es relacionen comunament en problemes NP-hard. Dits problemes en general no són resolts eficientement, no obstant, vàries aproximacions de la teoria de la complexitat sugerixen que certes instàncies (ej. "menudes" instàncies) d'estos problemes poden ser resoltes eficientement. Dites instàncies a sovint tenen ramificacions pràctiques molt importants.

Definició formal

Una instància d'un problema d'optimisació combinatòria pot ser descrit formalment com una tupla $(X,P,Y,f,\mathrm{e}\mathrm{x}\mathrm{t}\mathrm{r})$ a on

• X és l'espai de solucions (en el qual f i P estan definits)
• P és la factibilidad predicat.
• I és el conjunt de solucions factibles.
• f és la funció objectiu.
• extr és l'extrem (normalment min o max).

Definició de problema d'optimisació

Un problema d'optimisació combinatòria es definix com aquell en el que el conjunt de solucions possibles és discret. En atres paraules, es tracta d'un problema d'optimisació que involucra una cantitat finita o numerable de solucions possibles.

Este tipo de problemes es diferencia dels problemes d'optimisació continus, en els quals el conjunt de solucions possibles és infinit i incontable. Esta branca de l'optimisació es relaciona estretament en l'investigació operativa, la teoria algorítmica i la teoria de la complexitat computacional. Els algoritmes d'optimisació combinatòria resolen problemes que, en general, es consideren difícils en explorar l'ampli espai de solucions del problema en qüestió. Els bons algoritmes d'optimisació combinatòria conseguixen reduir el tamany efectiu de l'espai de busca i explorar-ho de manera eficient.

Ací entren els algoritmes d'optimisació combinatòria. Estos són capaços de resoldre problemes que solen ser considerats difícils, ya que exploren un ampli espai de solucions. Per a conseguir-ho, estos algoritmes reduïxen efectivament el tamany de l'espai i ho exploren de manera eficient.

En el camp de l'optimisació combinatòria, és comuna que la majoria dels processos de resolució de problemes no puguen garantisar la solució òptima, inclús dins del context del model que s'estiga utilisant. No obstant, l'aproximació a l'òptim sol ser suficient per a resoldre els problemes en la pràctica.

Existixen diferents métodos de resolució que poden ser classificats en quatre grans grups:

1. Algoritmes constructius, que construïxen la solució a partir d'una solució incompleta i utilisant les senyes del problema i el coneiximent previ.
2. Algoritmes de millora, que comencen en una solució factible i completa i la modifiquen gradualment de manera progressiva.
3. Estratègies de "dividix i venceràs", que dividixen el problema en fragments i apliquen qualsevol atra estratègia per a resoldre cada fragment, i finalment recomponen la solució.
4. Estratègies d'aprenentage, que prenen decisions en funció de senyes conegudes pel resultat de resolucions anteriors o en la mateixa resolució.

Els métodos més comuns utilisats per a resoldre problemes en optimisació combinatòria són heurístics o metaheurísticos. Estos métodos són capaços de generar solucions per al problema, encara que siguen aproximacions que no necessàriament alcancen la solució òptima.

En els primers dies de l'Investigació Operativa, les llimitacions de càlcul automàtic varen dur a la creació de procediments heurístics que pogueren trobar solucions de manera ràpida, encara que no necessàriament les millors.

Encara que els métodos heurístics de resolució no poden garantisar la solució òptima, són fonamentals per vàries raons. En primer lloc, són capaços de generar solucions, la qual cosa és millor que no tindre cap solució. En segon lloc, obtindre la solució òptima per a un model que no representa exactament el problema real no és necessàriament essencial. Per últim, dissenyar una bona heurística exigix un coneiximent profunt del problema, la qual cosa pot conduir a millores d'un atre tipo.

Per lo tant, els métodos heurístics, incloent els processos de millora local i els algoritmes metaheurísticos, són ferramentes valioses per a resoldre problemes d'optimisació combinatòria en la pràctica.

Vore també

• Optimisació discreta
• Algoritmes de busca
• Evolució diferencial
• Optimisació Combinatòria

Referències

William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver; Combinatorial Optimization; John Wiley & Sons; 1 edition (November 12, 1997); ISBN 047155894X.

• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger, A Compendium of NP Optimization Problems.
• Christos H. Papadimitriou, and Kenneth Steiglitz; Combinatorial Optimization: Algorithms and Complexity; Dover Pubns; (paperback, Unabridged edition, July 1998) ISBN 0486402584.