Jugant al dilema del presoner diverses vegades hom es planteja la pregunta: quina és la millor estratègia?
La resposta és complexa i no és única. Com ho podem avaluar? Una manera és posar diversos individus amb diverses estratègies a competir entre ells (ara no hi ha només un jugador i Llucifer, però juguen per parelles). Les millors estratègies (les que guanyen més) es poden reproduir amb més facilitat, i els seus fills n'hereten les propietats - tal i com passa amb la selecció natural de les espècies i la genètica. De tant en tant, apareix una mutació que fa variar els esquemes i introdueix un nou tipus d'adversari que pot ser molt més eficaç que els seus progenitors i descendents.

El següent applet pretén simular aquest joc que acabem de proposar. Aquest cop la màquina juga sola (el que volem saber és quina és la millor estratègia després de molts segles de jugar al joc, molts tipus d'oponents). Observem els següents aspectes:

• 0 és delatar 1 es cooperar.
• El número de l'esquerra és el percentatge de cel·les amb la població d'aquest individu (gen), és a dir, com més èxit tingui una generació, més població hi haurà d'aquell gen a la següent generació.
• El color de la segona columna és el color del gen (sense rellevància).
• El nombre a continuació designa el que fa el jugador quan no té prou història de com ha jugat l'oponent. Per exemple, a l'estratègia tip for tat és el que es farà a la primera jugada, quan encara no sabem què ha fet Llucifer.
• El grup de bits a continuació són el codi genètic dels individus. El codi genètic marca les estratègies a seguir segons el que ha fet l'adversari. En aquest applet es poden recordar fins a les 5 últimes accions, amb un total de 32 bits. El que això vol dir és el següent: 

                Exemples:     

1. Codi genètic del tipus a/bcde-té memòria de 2 jugades i per això calen 2x2=4 caracters (veure la taula anterior)
   La primera opció és a (recordem, a=0 delatar, a=1 cooperar).
   La segona opció és b i correspon al que fem si l'oponent delata els dos últims cops seguits. Si b val 1 vol dir que quan l'oponent fa 2 jugades ha delatat i la jugada anterior ha tornat a delatar, tú cooperes (1 és cooperar  i el que fa el rival ve determinat per la posició al codi genètic).
   La tercera opció és c i correspon al que farem si l'oponent ens delata i a continuació coopera.
   La quarta opció és d i correspon al que farem is l'oponent coopera i a continuació delata.
   La cinquena opció és el que fem si l'oponent ens coopera dos cops seguits.
2. L'estratègia d'un codi genètic 1/11 és cooperar sempre. Vegem com funciona: és del tipus a/bc. El paràmetre a indica què fariem a la primera jugada (1 correspon a cooperar i per tant, la primera jugada cooperem). La segona vegada ja tenim un registre d'història del rival que és el que ha fet a la primera jugada. Com que el codi genètic té 2 valors només tenim 1 registre d'història. El primer valor, b, correspon al que fariem si el rival ens ha traït (com que el valor és 1, vol dir que cooperem si ens ha traït) i el valor c és el que fariem si ens ha col·laborat (també cooperem). De manera que el codi 1/11 correspon a cooperar sempre.
3. El codi 0/00 correspon a delatar sempre.
4. El codi 1/01 correspon a l'estratègia "Tip for Tat" ("ull per ull i dent per dent"). Comencem cooperant, i si el rival delata nosaltres delatem i si coopera cooperem. Cal veure que l'estratègia 1/0101 ó 1/010101 també són del tipus "Tip for Tat", tot i que els calen 2 i 3 registres de reaccions del rival per començar l'estratègia i fins llavors cooperariem. Per exemple, l'estratègia 1/010101 a la primera, la segona i la tercera jugades cooperariem encara que Llucifer delatés, però a la quarta, com que ja tenim 3 jugades de Llucifer mirariem què ha fet. És clar que com que els 1 ocupen les posicions parelles, si la última opció de l'oponent ha sigut cooperar, cooperem i si no delatem.
5. 1/0001 Revenja. Si l'oponent ens traeix un cop no ho oblidem  i el delatem fins que l'oponent coopera dos cops seguits. (NOTA: si l'oponent traeix a la primera jugada, la segona encara cooperem, però a la tercera ja funciona per revenja).
   

• L'estratègia mínima es 1 bit (codi genètic mínim del tipus a/bc), que vol dir que el jugador només utilitza l'últim resultat de l'adversari. Per tant, no es contempla l'estratègia aleatòria, que no té memòria del que ha fet l'oponent. Per a una estratègia d'aquest tipus cal saber què es farà si l'oponent delata i si l'oponent coopera. El codi genètic tipus és a/bc.
• Hi ha 4 tipus de mutacions:
  (1) Mutació del tercer número (permutar cooperar per delatar 0<->1)
  (2) Mutació d'un punt, per exemple: 0101 -> 0100
  (3) Reducció del número de resultats previs que utilitza l'estratègia. 0100->01 (es queda amb el que ha fet quan el resultat previ correspon a cooperar, els primers números)
  (4) Doblar la memòria de l'estratègia. 0011->00110011

http://www.bekkoame.ne.jp/~ishmnn/java/ga_dlm.html

Que és un Algoritme Genétic?

Els algoritmes genètics (genetic algorithms, o GAs) son un tipus especial d'algoritmes. Els algoritmes normalment donen una recepta per a la manipulació de certes dades, amb l'objectiu de produir un resultat, ja sigui un càlcul o una transformació. Els GAs intenten resoldre problemes que per la via habitual trigarien segles amb la potència actual dels ordinadors. I ho fan d'una altra manera: imitant la selecció natural. Se simula doncs una població de possibles solucions al problema, que es reprodueixen i muten de manera que exploren l'espai de possibles solucions.

Vídeo de Kalr Sims Provant múltiples combinacions de sistemes formats per peces unides amb una rigidesa, una gravetat i associades a un medi generades aleatòriament per un ordinador seguint unes regles es posen a competir entre elles i s'associen les més òptimes per buscar uns "fills" que compleixin l'objectiu encara millor. Aquest vídeo presenta resultats sorprenentment semblants a comportaments d'éssers vius quan realment estan generalts aleatòriament a partir de normes senzilles i combinant els sistemes més eficaços, tal i com passa a la natura.

Tornar a l'índex de la Visita guiada pels sistemes complexos