Anders Hesselbom

Hur kan vi utnyttja evolutionen?

2016-06-22

Tack vare den ofrånkomliga utveckling som följer från förändring över tid, med selektion, och tack vare att vem som helst idag har tillgång till starka datorer, kan vi tämja evolutionen till att göra lite vad vi vill. Låt säga att jag t.ex. vill skapa ett korsord från en lista av ord. Antingen sätter jag mig ner och flätar orden manuellt, vilket kan vara nog så svårt. Eller så använder jag min PC för att skapa en algoritm som beskriver hur orden ska flätas ihop, vilket inte heller är speciellt enkelt.

Fördelen med evolutionära algoritmer är att jag bara behöver veta vad jag vill åstadkomma – jag behöver inte tänka på hur något görs. Om det är ett korsord som ska byggas, så skulle jag kunna tänka mig att mitt indata är t.ex. 20 – de ord som ska flätas ihop till ett korsord. Om jag kan definiera vad ett bra korsord är, så kan jag göra ett urval. Och kan jag göra ett urval, så kan jag låta slumpen göra jobbet. Jag behöver även ha två regler: en regel som säger att t.ex. ordet ASKA inte får korsas med ordet PILBÅGE, och en regel som säger att om ordet ASKA ska korsas t.ex. med ordet MATROS, så måste det ske på någon av de gemensamma bokstäverna (vilket är S eller A).

En tänkt initiering av korsordet skulle kunna vara att skapa 15 giltiga korsord genom att låta slumpen avgöra om ett ord ska vara vågrätt eller lodrätt, och sedan placera ut ordet på en tänkt matris, på en slumpvis utvald plats. Om ordet inte kan placeras på den plats som tilldelas, så slumpar vi fram en ny plats, så att reglerna upprätthålls. Detta upprepas för varje ord till dess att alla ord ligger på en giltig plats, vilket innebär att vi har ett giltigt korsord, om än förmodligen ett väldigt spretigt sådant.

Dessa 15 korsord kan vi betrakta som en lista av föräldrar. Jag brukar jobba med två generationer – en föräldrageneration och en barngeneration. Och det är från någon av dessa 15 korsord som det perfekta korsordet ska komma.

Nästa steg blir att låta varje korsord få 3 barn. Ett barn i detta fall är en kopia av ett korsord, med en slumpmässig förändring. Man kan låta slumpen avgöra om man ska positionera om ett ord, två ord eller tre ord. Man kan låta slumpen avgöra om något eller alla av dessa ord ska förvandlas från vågrätt till lodrätt, eller tvärt om. Vi som bygger evolutionära algoritmer har lånat en biologisk term för detta skeende, nämligen mutation. Barnen, 45 stycken, lagras i listan som representerar barngenerationen.

Varje barn poängsätts efter hur väl det är anpassat till sin miljö (där miljö egentligen är mina kriterier). En liten area ger högre poäng än en stor area, antal intersektioner mellan ord ger poäng, en mer rektangulär form ger högre poäng än en mer långsmal form, och så vidare. När alla 45 barnkorsord är poängsatta, sparar jag de bästa 15 i föräldragenerationen, tömmer barngenerationen, och upprepar processen.

Över tid kommer kvalitén (alltså likheten med mina kriterier) att förbättras, men om tillräckligt lång tid får passera så upphör förbättringen. Man kan tänka sig ett tröskelvärde som säger att om inte något korsord har förbättrats på, säg, 10 000 generationer, så är vi nöjda med vårt korsord – det korsord som har högst poäng.

Och därmed har jag skapat ett korsord utan att själv vara förmögen att varken placera ut orden på egen hand eller beskriva den algoritm som skulle göra detta. Allt samman bygger på att nästan var och varannan person idag, i sin ficka, förvaltar något som för 20 år sedan skulle betraktas som en superdator.

Categories: Science