Prírodou inšpirované algoritmy

Evolúcia spolupráce

Definujme platby medzi hráčmi podľa tabuľky. Hra iterovaná väzenská dilema bude použitá pre štúdium evolúcie spolupráce v populácii.

Experiment uskutočníme na populácii agentov, reprezentujúcich rôzne stratégie, ktoré budú kódované na troch bitoch takto :

a = (a1, a2, a3)

• a1 určuje prvý ťah hráča: ak a1=0, potom hráč spolupracuje, v opačnom prípade nespolupracuje.
• a2 určuje ťah hráča v prípade, že druhý hráč v predchádzajúcom kroku spolupracoval: ak a2=0, potom hráč spolupracuje, v opačnom prípade nespolupracuje.
• a3 určuje ťah hráča v prípade, že druhý hráč v predchádzajúcom kroku nespolupracoval: ak a1=0, potom hráč spolupracuje nespolupracuje.

Ide o stratégiu, ktorá vyžaduje len krátkodobú pamäť hráčov, požaduje len znalosť posledného kroku protihráča. Existujú stratégie tejto hry aj pre dlhodobejšiu pamäť, potom hovoríme o hre väzenská dilema s dvoj-, troj-, ... násobnou pamäťou.

Sila agentov z populácie je určená tak, že sa usporiada turnaj, v ktorom každý agent hrá so všetkými ostatnými agentmi predpísaný počet krokov. Sila chromozómu je potom určená ako suma platieb zo všetkých krokov a za každého súpera. Operácia reprodukcie obsahuje dve klasické operácie genetických algoritmov, a to kríženie a mutáciu. Genetický algoritmus je inicializovaný náhodne generovanou populáciou, ktorá obsahuje 1000 agentov. Výsledky genetického algoritmu sú znázornené na grafe.

V priebehu evolúcie populácie zvíťazila stratégia (001), ktorá odpovedá stratégii tit-for-tat a je evolučne stabilná. Iné stratégie, napr. stratégia vždy spolupracuj (000) alebo vždy zraď sú evolučne nestabilné. Na grafe je vidieť, že stratégia vždy zraď (111) v počiatkoch evolúcie bola dominantnou stratégiou, avšak v priebehu ďalšej evolúcie začala dominovať stratégia (001), ktorá sa stala aj víťazom evolúcie.

Veľmi podobný experimet, s rozdielným kódovaním jedincov a pozmeneným evolučným algoritmom je možné si pozrieť v tomto applete