}

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

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

Els algorismes genètics són una tècnica de programació que imita l'evolució biològica i que s'utilitza per a resoldre problemes molt difícils o impossibles de resoldre mitjançant mètodes convencionals. No saben molt bé per què, però les tècniques convencionals funcionen en problemes que fallen, per la qual cosa són cada vegada més utilitzades per a resoldre problemes pràctics.
Algorismes genètics a la recerca de la solució més adequada
01/01/2008 | Galarraga Aiestaran, Ana | Elhuyar Zientzia Komunikazioa

(Foto: D'arxiu)
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.

Esquema del funcionament dels algorismes genètics.

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.

Els algorismes genètics es basen en la teoria de l'evolució de Darwin.
D'arxiu
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ó.

Un venedor ha de creuar diversos punts i arribar al punt de partida, realitzant el recorregut més adequat. A això se'n diu problema del venedor i no es pot resoldre amb mètodes convencionals, però es resol bé mitjançant algorismes genètics.
D'arxiu

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.

El disseny d'horaris és realment complex, i per a això els algorismes genètics són una gran eina.
P. Gene
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.

Els algorismes genètics s'utilitzen per al disseny de pèptids, entre moltes altres aplicacions.

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".

Mª Teresa Iglesias: "L'objectiu dels algorismes genètics és adaptar-se a l'entorn"
Mª Teresa Iglesias, professora del departament de Matemàtiques per la Universitat de La Corunya, va impartir recentment en la Facultat de Ciència i Tecnologia de la UPV/EHU la conferència "Matemàtiques evolutives: algorismes genètics", "La dona, innovadora de la ciència?" Dins de les jornades. Després de la xerrada vam tenir l'oportunitat de parlar amb aquesta innovadora científica.
En el seu discurs ha afirmat que els algorismes genètics són molt bons per a resoldre problemes que no tenen una solució senzilla, encara que per si mateixos no sempre maximitzen.
Això és. L'evolució tampoc tendeix al màxim sinó a adaptar-se. L'evolució produeix individus que s'ajusten bé a un determinat entorn, el mateix que els algorismes genètics. Per exemple, en comparació amb els homes i dones de fa mil anys, ens adaptem millor que ells en la societat actual, però no ens emportaríem tan bé si de sobte ens despertéssim en aquella època... Les solucions que proporcionen els algorismes genètics no sempre seran les millors, però s'adaptaran molt bé a una situació concreta.
(Foto: A. Galarraga)
A més no s'utilitzen solos. Normalment s'utilitzen inicialment i, una vegada que s'ha aconseguit un conjunt de solucions relativament bones, se segueix amb els mètodes tradicionals.
No obstant això, no sempre funcionen. Si no m'equivoco, investigues per què ocorre això.
Sí, algunes funcions ( deceptive functions ) enganyen d'alguna manera a l'algorisme i l'allunyen de l'òptim. Antigament es pensava que els algorismes genètics no funcionaven amb aquestes funcions, però ara veiem que amb uns sí i amb uns altres no. És difícil saber per què, i en el nostre grup treballem just en això; tractem d'aclarir quines característiques fan que una funció sigui difícil d'optimitzar mitjançant algorismes genètics. I ja hem trobat algunes.
No obstant això, encara queda molt per investigar. Són relativament nous i, com en molts casos funcionen bé, els informàtics els utilitzen, encara que encara no hi ha una base teòrica sòlida. Però el que ens toca és treballar els fonaments teòrics.
Galarraga d'Aiestaran, Ana
Serveis
238
2008
1.
032
Matemàtiques; Evolució
Article
Uns altres

Gai honi buruzko eduki gehiago

Elhuyarrek garatutako teknologia