Algorismes genètics a la recerca de la solució més adequada

2008/01/01 Galarraga Aiestaran, Ana - Elhuyar Zientzia Iturria: Elhuyar aldizkaria

• Eboluzioa
• Matematika

En la naturalesa, la població inicialment existent canvia amb el temps. De generació en generació, alguns factors fan que els individus que pitjor s'adapten desapareguin, mentre que els que millor s'adapten perviuen. Per tant, dins de la població augmenta la proporció de millors. No obstant això, és possible que algun que no sembla tan bo continuï per tenir una estratègia diferent o per atzar. I podria creuar-se amb els altres, com es creuen els altres. Per tant, és possible que la característica de l'individu, suposadament dolenta, aparegui en la pròxima generació en altres membres.

De tant en tant apareix una altra variable: la mutació. Encara que no és molt freqüent, influeix en les característiques dels membres de la població. A causa dels encreuaments, mutacions i agents que aposten pels millors, una vegada transcorregut el temps, la població està formada pels membres més ben adaptats a l'entorn.

Així ho va explicar, més o menys, Darwin en la teoria de l'evolució de les espècies, i és el que fan els algorismes genètics. La població inicial està constituïda per les possibles solucions a un problema. Aquestes possibles solucions se seleccionen aleatòriament i es denominen cromosomes. Els diferents aspectes de cada cromosoma es denominen gens.

En cas de ser candidats, se'ls aplica una funció que mesura la seva idoneïtat. Com és normal, la majoria dels candidats són inadequats, però uns altres, d'alguna manera, funcionen i es mantenen.

Els candidats que han avançat es multipliquen i es creuen. Per tant, en la següent generació, alguns tenen diverses còpies i unes altres s'han equivocat. A més, uns pocs no són exactament iguals als anteriors: s'han mutat, és a dir, s'han modificat aleatòriament algun gen.

La generació resultant és diferent a l'anterior i es mesura la idoneïtat d'aquests candidats. Així, els candidats que no són millors que els anteriors es descarten, els que queden són millors solucions que els inicials. Ells es reprodueixen i es produeixen creus i fins i tot mutacions. S'avaluen els nous candidats i es torna a triar als millors, el procés es repeteix cada cent o mil vegades. La població resultant està formada per molt bones solucions al problema.

Números, lletres i arbres

Per a començar a treballar els algorismes genètics és necessari codificar les possibles solucions del problema perquè l'ordinador pugui processar-lo. Una opció és codificar en cadenes binàries: Són cadenes formades per 1 i 0 i el dígit que hi ha en cada lloc de la cadena representa el valor d'un aspecte de la resolució.

Una altra manera de codificar és mitjançant cadenes de nombres enters o decimals. Com en el cas anterior, el número que hi ha en cada lloc indica el valor d'un aspecte concret de la resolució. S'obté major precisió i complexitat que amb el codi binari, ja que limita menys que usar dos números. D'altra banda, els números es poden substituir per lletres per a codificar els candidats.

Amb aquests tres mètodes és molt fàcil definir les operacions que realitzaran a l'atzar creuis i mutacions entre els candidats; és fàcil posar un 1 on hi ha un 0 o viceversa; afegir o llevar un valor a un número; o substituir una lletra per una altra.

A més, existeixen altres maneres de codificar, com la que es realitza amb arbres. Les dades es representen ramificats i els canvis es realitzen canviant el valor dels pegats o substituint algunes branques de l'arbre per unes altres.

Selecció i modificació

Codificar d'una manera o una altra, programar l'elecció dels individus a copiar per a la següent generació. La selecció es pot realitzar de diverses formes i normalment s'utilitzen diverses d'elles alhora. Una d'elles és la selecció elitista, és a dir, la selecció dels millors de cada generació. Una altra forma depèn de la capacitat: a major capacitat, més possibilitats d'elecció.

A més, per a garantir la diversitat de la població, es pot utilitzar una roda de ruleta: a cada candidat li correspon una part de la ruleta; a major capacitat, major part s'adapta al candidat. Girant la roda, els que tenen una part gran tenen més possibilitats de ser triats, però pot ser que s'adapti a un candidat amb poca capacitat per a ser triat per a la següent generació. Això garanteix que la següent generació no sigui massa igualitària.

Una altra manera de garantir això és mitjançant la realització de grups per nivell de competència i l'elecció dels millors de cada grup, de manera que el millor del grup de baixa capacitat avançaria. Els equips també es poden fer a l'atzar i després es poden obligar a competir entre ells, els vencedors passen a la següent generació.

Existeixen altres mètodes de selecció: selecció escalonada, jeràrquica... En qualsevol cas, l'objectiu és que els candidats de la següent generació siguin de mitjana millors que els anteriors. A més, als candidats seleccionats per a la següent generació se'ls realitzen alguns canvis aleatoris amb l'esperança que apareguin millors individus.

Existeixen dues maneres de realitzar els canvis: mutació i encreuament. La mutació és canviar un aspecte concret, un gen. L'encreuament consisteix a canviar part del codi per un altre candidat. El "nen" així format té en comú les característiques dels dos "pares". Es tracta, per tant, d'una recombinació entre els cromosomes paterns i materns en la reproducció sexual.

A favor i en contra

Mitjançant la selecció, la mutació i l'encreuament, de generació en generació, els algorismes genètics van acostant-se a la solució del problema. En molts casos, l'algorisme genètic no serà suficient per a deixar anar el problema, però pot donar solucions raonablement bones, i aplicant els mètodes habituals a aquesta població final es pot obtenir la millor solució.

Una dels avantatges dels algorismes genètics és que són “cecs”, és a dir, que no saben res del problema que han de resoldre. Pot ser que més que un avantatge sembli un desavantatge, però és molt bona, ja que no rebutja des del principi a cap candidat amb mal aspecte. A més, el creuer i la mutació creen sorprenents solucions. D'alguna manera, els prejudicis no afecten els algorismes genètics, només els importa avançar.

A més, treballen en paral·lel, és a dir, per diferents vies alhora. La majoria dels algorismes treballen en sèrie i només poden avançar en una direcció en cada ocasió. Quan s'adonen que han pres el camí equivocat, han d'abandonar tot el treball i començar de nou. No obstant això, els algorismes genètics no tenen aquest problema i són especialment eficaços en la resolució de problemes amb moltes solucions possibles.

Tenen més avantatges però també alguns inconvenients. La primera és la dificultat d'escriure la definició del problema. La codificació dels candidats no és senzilla i a vegades costa molt escriure la funció que mesura la capacitat. La grandària de la població, la freqüència de mutacions i creus, així com el tipus i la força de la selecció, són factors molt importants en els algorismes genètics, que si no es dissenyen bé, no avancen.

Apps

Malgrat les seves limitacions, s'utilitzen per a resoldre problemes com a acústica, enginyeria aeroespacial, astronomia i astrofísica, química, mercat financer, jocs, geofísica, enginyeria de materials, matemàtiques, biologia molecular, telecomunicacions, etc.

Per exemple, en 2002 investigadors de la Universitat Kobe del Japó van utilitzar algorismes genètics per a dissenyar una sala de música. Van partir d'una sala en forma de caixa de sabates i van definir els paràmetres que havia de tenir per a aconseguir la millor acústica. L'algorisme va donar dos resultats, tots dos en forma d'host, que semblen tenir una acústica espectacular. Segons els investigadors, són com el Grosser Musikvereinsaal de Viena, el millor del món.

Per part seva, la NASA els ha utilitzat en el disseny d'envasos, però també en l'estudi de nanes blanques i en el disseny d'horaris. De fet, els algorismes genètics són molt eficaços per a la realització d'horaris tant en empreses, aeroports i escoles.

A les escoles, per exemple, és un problema l'horari adequat. Es requereix un professor per aula i un professor no pot estar en dues aules simultàniament. Per descomptat, cada professor ha de donar el seu tema i, tal vegada, alguns temes millor que es donin a una hora i no a una altra (no convé posar a última hora les matemàtiques, la física, etc.). A més, cal tenir en compte les preferències o necessitats del professorat. Atès que cal tenir en compte tants factors, en els grans centres és molt difícil aconseguir un bon programa horari. Doncs bé, els algorismes genètics són perfectes.

Els experts no tenen dubte que, a pesar que són relativament nous (els primers van aparèixer en la dècada de 1960), han tingut un ràpid desenvolupament i, segons la matemàtica Mª Teresa Iglesias, "no cal detenir-los".