I aftenens afsnit forekommer der evolutionære algoritmer. Opgaven er at finde abnorm opførsel i et online computerspil á la World of Warcraft.
Evolutionære algoritmer kalder man de typer algoritmer, der finder frem til et resultat ved brug af metoder, der er baseret på principperne bag biologisk evolution, nemlig
– Rekombinering og mutation, der skaber mangfoldighed inden for en population af individer, og
– Udvælgelsen af de “bedst egnede” individer
Den grundlæggende observation bag evolutionære algoritmer er, at naturen har kunnet løse rigtig mange problemer og frembringe meget avancerede organismer ved brug af disse simple principper. Derfor må man også kunne bruge en tilsvarende tilgang, når man vil løse et svært problem ved brug af en algoritme.
Der er mange forskellige tilgange til evolutionære algoritmer. Den, jeg vil beskrive her, kaldes genetiske algoritmer, og jeg vil tage udgangspunkt i et eksempel, der på samme tid er let at forklare og formodentlig svært at løse, nemlig rygsækproblemet.
Rygsækproblemet er dette:
Givet en øvre grænse MAX og en mængde af n naturlige tal c_1,…,c_n, hvordan kan vi da vælge en delmængde af disse tal, således at deres sum er mindre end MAX og så forskellen MAX – S er minimal?
Tænk på problemet som et problem om at pakke en rygsæk, der kan rumme MAX liter med ejendele med rumfang c_1,…,c_n således at rygsækken bliver så fyldt som overhovedet muligt.
Rygsækproblemet er det, man kalder optimeringsversionen af det tilsvarende beslutningsproblem:
Givet en øvre grænse MAX, en forskelsværdi K (der er et naturligt tal) og en mængde af n naturlige tal c_1,…,c_n, kan vi da vælge en delmængde af disse tal, deres sum er mindre end MAX og så forskellen MAX – S er mindre end eller lig K?
Dette beslutningsproblem er NP-fuldstændigt, og vi har talt om denne slags problemer før her på bloggen. Hvis et beslutningsproblem er NP-fuldstændigt gælder det, at ingen kender en hurtig algoritme der altid kan give det korrekte svar for vilkårlige instanser af problemet. Af denne grund kan der derfor heller ikke være en hurtig algoritme, der kan beregne en løsning for optimeringsversionen af problemet. Hvis man vil have en hurtig algoritme, må man give køb på at være sikker på at finde en optimal løsning – og her er netop en evolutionær algoritme et godt bud.
Her er et eksempel på en evolutionær algoritme (af den slags, man kalder en genetisk algoritme) til at beregne en løsning på rygsækproblemet.
Ideen er vi repræsenterer et bud på en løsning som en streng af k bits, dvs. en streng af 0’er og 1’er. Hvis tallet c_i er med i mængden, skal der være et 1 på position nr. i i strengen, ellers skal der være et 0.
Lad os som eksempel antage, at vi har de 4 c-værdier 3,4,9 og 12. Så svarer delmængden {4,9} til strengen 0110.
Der er et problem her, da strengens værdi kan blive > MAX. Så nogle strenge kan aldrig være bud på løsninger. Dette kan vi nemmest løse ved at beregne strengens “faktiske værdi” V(S) på denne måde:
Vi læser positionerne i strengen S fra venstre, så længe den samlede værdi af de læste bits er højst MAX. Herefter skal evt. følgende bits ignoreres.
Fitness af en streng S kan vi nu definere som F(S) = MAX – V(S). Hvis M er en mængde af strenge, er FV(M) den højeste fitness-værdi for strengene i M.
Algoritmen udvælger en mængde af K startstrenge og gennemløber derefter en løkke indtil populationens fitness er stabil. Lad os sige at dette kræver 25 generationer, og at der er 500 startstrenge. Så ser algoritmen således ud:
1. Lav 500 start-strenge.
2. Gentag følgende
– Skab en ny generation M’
– Beregn FV(M’)
3. Indtil FV(M’) ikke har ændret sig i 25 generationer
Nu skal vi bare have defineret, hvordan man skaber en ny generation.
Vi skaber en ny generation fra M på denne måde:
– Inddel generationen i forældrepar ved en turnering.
– Hvert forældrepar får 2 afkom ved rekombinering og mutation.
– Mængden af disse afkom udgør den nye generation.
“Forældre-turneringen” kan f.eks. foretages ved en udvælgelse uden tilbagelægning: Vi vælger en tilfældig mængde af 4 strenge og lade et nhyt forældrepar være de to strenge hvis V(S) er størst.
En enkel form for rekombinering er overkrydsning. Overkrydsning finder sted med en på forhånd fastlagt sandsynlighed; lad os her sige at denne sandsynlighed er 70%.
Vi tager to bitstrenge. Herefter vælger vi et tilfældigt tal x mellem 0 og 1. Hvis x > 0,7 beholder vi de to bitstrenge som de er. Ellers vælger vi en vilkårlig position og bytter de to strenges indhold efter denne position. Hvis positionen er 4 og vi har strengene
0001110101
1010100010
får vi således de nye strenge
0001100010
1010110101
En enkel form for mutation er at ændre en tilfældig bit i strengen. Mutation finder også sted med en på forhånd fastlagt sandsynlighed; lad os her sige at denne sandsynlighed er 5%.
Her tager vi én bitstreng. Herefter vælger vi et tilfældigt tal x mellem 0 og 1. Hvis x < 0,95 beholder vi strengen som den er. Ellers vælger vi en vilkårlig position og ændrer den bit, der er på positionen. Hvis positionen er 6 og vi har strengen
0001110101
får vi
0001100101
Vores evolutionære algoritme er derfor en systematisk prøven-sig-frem. Af denne grund er der heller ingen garanti for at den finder den optimale løsning, endsige at den finder en god løsning. Hvis vores startstrenge er valgt uhensigtsmæssigt, er der nemlig en lille (omend meget lille) sandsynlighed for at vi efter 25 gennemløb stadig vil have de strenge, der var vores start-strenge.