Extended Speciation in Open-Ended Coevolution

Abstract

Åpne koevolusjonære algoritmer er inspirert av naturlig evolusjon og samhandlingen mellom arter og miljøer. De kan genere problemer med økende kompleksitet samtidig som de har en løsning for hver. Ved å fokusere på simple kriterier fremfor fitness-verdier vanligvis brukt i tradisjonelle evolusjonære algoritmer, fortsetter søkeprosessen å innovere uten grenser i forskjellige retninger. Prosesser som fortsetter å innovere slik som i naturlig evolusjon er ikke enkelt å simulere, men har et stort potensial da en generell slik algoritme kan generere løsninger og design med økende kompleksitet til hvilket som helst problem.

Et utgangspunkt for åpen koevolusjon var nylig introdusert i Brant og Stanley [2017], hvor Minimal Criterion Coevolution (MCC) ble brukt for å parallelt utvikle labyrinter og løsningsagenter på en evoluasjonær måte. Labyrinter og agenter var i stand til å øke i kompleksitet i parallell. En metode som deler labyrint- og agent-populasjonene i forskjellige arter ble brukt for å kunne utvikle de i flere retninger samtidig. Denne oppgaven utvider denne funksjonalitet i MCC til å rangere og prioritere de beste artene, basert på hvor mye den gjennomsnittlig øker i størrelse og kompleksitet.

To forskjellige metoder er undersøkt. Den første utvider metoden til å støtte et varierende antall individer i hver art, hvor kapasitet i de dårligste artene blir periodisk overført til de beste. Den andre utvidelsen unders\o ker effekten av å periodisk bytte ut de verste artene med nye gjennom hele utviklingen. Hvordan labyrinter og agenter i MCC utvikler seg med disse utvidelsene vil bli sammenlignet mot MCC uten noen utvidelser, der arter alltid har like mye kapasitet og blir aldri byttet ut.

Inspired by natural evolution and the dynamics between species and environments, open-ended coevolutionary algorithms are able to generate increasingly complex problems while simultaneously having a solution for each. By focusing on fulfilling simple criteria instead of objectives and fitness values commonly used in traditional evolutionary computation, the search process continues to invent without boundaries and maintains diversity. Continual innovation as in natural evolution is not easy to simulate, however, the rewards and implications of a general open-ended algorithm would be extraordinary as it could endlessly generate increasingly complex solutions and designs to any problem.

A base for open-ended coevolution was recently proposed by Brant og Stanley [2017], where a method called Minimal Criterion Coevolution (MCC) was used to coevolve a set of mazes and navigator agents that were able to solve them. Mazes and agents were able to increase in complexity in parallel. A method called speciation was used to split the maze- and agent populations to evolve multiple lineages in the same run. In this thesis, the speciation method in MCC is further extended with ranking and prioritization of the most performant species. Species are ranked based on their average growth in size and complexity.

Two different methods are investigated. First, the speciation is extended to support a dynamic number of maximum individuals in each species, where the capacity is transferred periodically from the least to most performant species. The other method investigates the effects of replacing the worst species with new ones periodically throughout evolution. How the mazes and agents evolve in MCC with these extensions are compared against MCC with the base speciation, where the size of all species is static and never replaced.