Una de les disciplines de la informàtica en què mai he aprofundit però que em crida l’atenció des del dia que vaig estudiar-la a la universitat és una branca de la intel·ligència artificial anomenada “algorismes genètics”.
Comencem pel principi: un algorisme és un conjunt de passos organitzats de tal manera que resolen un problema determinat. Generalment és feina del programador dissenyar quins són aquests passos i com s’han d’estructurar per tal que, com és d’esperar, aportin realment una solució al problema. Doncs resulta que aquesta branca de la intel·ligència artificial proposa aplicar tècniques pròpies de la genètica i l’evolució per a trobar l’algorisme que busquem. La idea general, per no complicar massa la qüestió, és crear un algorisme “aleatori”; enfrontar-lo al problema i assignar-li una puntuació (arbitrària però objectiva i comparable) per a valorar com de bona (o de dolenta) és la resolució que ha fet del problema.
Per ser més exactes (anem-nos acostant a la realitat de mica en mica) el que fem no és generar un algorisme aleatori sinó que dissenyem un algorisme –diguem-ne– genèric amb un conjunt de variables lliures del qual sabem que donarà la solució al problema (o una bona aproximació) quan trobem els valors “òptims” per a totes les variables. En el fons és una qüestió d’optimització (o d’adaptació al medi, si fem servir terminologia evolutiva) o de resoldre una equació amb moltes incògnites.
El procediment plantejat per la intel·ligència artificial és el següent: un cop definits aquest algorisme genèric i les variables que el configuren, prenem un valor a l’atzar per a cadascuna d’elles i anomenem cromosoma aquest conjunt de valors . Repetim el procés fins a crear una població de 10, 20, 100… 1000… cromosomes. Anomenem generació aquesta població de cromosomes i enfrontem cada cromosoma al problema, avaluant-ne amb una nota el grau d’aproximació a la solució (segons el problema això serà més o menys difícil) o com a mínim amb un indicador que permeti comparar si un cromosoma ho ha fet millor que un altre o no.
Quan haguem avaluat tota la generació, aplicarem un procés natural d’evolució que consistirà en:
- Selecció natural: eliminarem els cromosomes que pitjors resultats hagin obtingut.
- Reproducció: farem combinacions entre els cromosomes supervivents creant nous cromosomes derivats fins a tenir una població amb el mateix nombre d’individus que la original.
- Mutació: aplicarem certa aleatorietat en els paràmetres dels cromosomes que acabem de crear.
En aquest procés haurem obtingut una segona generació, teòricament una mica més adaptada al medi que l’anterior. La mutació la fem per intentar reflectir la realitat (un fill no és mai una combinació lineal dels paràmetres del pare i de la mare; sinó que es produeixen mutacions “aleatòries” en els seus gens) i de la mateixa manera podem redefinir lleugerament altres processos. La selecció natural, per exemple, pot deixar viu algun dels cromosomes que –per dir-ho finament– no se n’ha acabat de sortir i matar-ne algun dels bons; de la mateixa manera que no sempre el nyu més dèbil és el que cau a les urpes dels lleons ni el més fort té la seguretat que arribarà a la vellesa.
Sigui com vulguem aquest procés (aquí juguem a fer de Déu), repetint aquesta evolució durant generacions i generacions en teoria obtindrem una població que cada vegada serà més bona enfrontant-se al problema… No és fascinant? I el millor de tot és que funciona! Vegem-ne un exemple:
BoxCar 2D és un joc per a zero jugadors que utilitza algorismes genètics per a dissenyar un vehicle capaç de superar els obstacles d’un terreny en dues dimensions. El disseny del cotxe (a la imatge superior n’hi ha un exemple) parteix d’una estructura octogonal en què cada vèrtex està unit amb el centre i és modificable segons els següents paràmetres:
- Angle d’obertura (respecte el centre) de cada parell de vèrtexs de l’octàgon
- Distància de cadascun dels vèrtex al centre
- Existència (o no) d’una roda en cadascun dels 8 vèrtex (pot haver-hi més d’una roda en el mateix vèrtex però no més de 8 rodes)
- Angle de l’eix de cada roda amb el seu vèrtex
- Diàmetre de cada roda
- Color de cada triangle format pel centre i dos vèrtexs
- Color de cadascun dels eixos de les rodes
De manera que, en aquest cas, un cromosoma (que és la definició del cotxe) consta de 8 angles i 8 distàncies per a la carrosseria, 8 valors que indiquen en quins dels vèrtex situem cadascuna de les 8 possibles rodes, 8 angles per als eixos de les rodes, 8 diàmetres per a les rodes i 16 valors de colors (no en aquest ordre). És fàcil adonar-se que la quantitat de vehicles diferents que podem generar és, a la pràctica, infinita. Vegeu un exemple de cotxe que he dissenyat manualment i el seu corresponent cromosoma numèric:
|
|
<a href=“http://jordinebot.cat/blog/wp-content/uploads/2011/02/Captura-de-pantalla-2011–02-16-a-las-20.28.29.png”><img class=“alignleft size-full wp-image-3008″ title=“El meu cotxe” src=“http://jordinebot.cat/blog/wp-content/uploads/2011/02/Captura-de-pantalla-2011–02-16-a-las-20.28.29.png” alt=”” width=“172” height=“101” /></a>1,1.492,0.9335,1.84,0.867,2.101,0.9905,
2.797,0.3635,0.564,0.7245,0.622,
0.5630000000000001,0.941,0.9905,3,3,
0.9424777960769379,1.5,7,
2.199114857512855,1.1973478311672807,6,
2.0202854348261674,1.192,-1,2.3271512214521963,
0.94,-1,5.615403641975675,0.9525596981868147,
-1,4.075827107587588,0.2819843692705035,-1,5.063380270569343,
1.4500815817154944,-1,4.654724898535651,1.4973793599754572,
13054,13054,16321673,16321673,16321673,16321673,
16321673,16321673,16321673,16321673,16321673,
16321673,16321673,16321673,16321673,16321673,8 |
Quan comença el joc (tan bon punt obrim la pàgina) es crea una pista i una població inicial de 20 vehicles a l’atzar (alguns no tenen ni rodes!
XD) i es posen, d’un en un, sobre la pista. En aquest cas la nota que obté cada vehicle està formada per la distància recorreguda i el temps emprat en completar la pista. Si un vehicle no es mou de lloc durant 3 segons es passa al següent i, en qualsevol cas, no se’ls dóna més de 4 minuts a cadascun per a intentar arribar al final de la pista. Tant el disseny dels vehicles, com la composició dels cromosomes, els processos de selecció, reproducció i mutació, etc. estan perfectament explicats a la pàgina de
The Algorithm del joc.
A més a més, el joc inclou la possibilitat de provar una sèrie de pistes no aleatòries, crear el nostre propi vehicle i introduir-lo a la població inicial per veure com evoluciona o modificar el grau de mutacions que hi haurà en cada canvi de generació. La veritat és que ho he trobat molt interessant, didàctic i divertidíssim! De fet, hi ha pocs jocs de zero jugadors, però m’encanten! :P
{lang: «ca»}
Amb els viatges que faig, em surt més a compte una T-MES o una T-50/30? O val més que vagi comprant una T-10 rere l’altra, per si de cas? Quin dels usuaris regulars de transport públic no es deu haver fet aquesta pregunta algun cop a la vida?
