211service.com
Evolutionär algoritm överträffar maskiner för djupinlärning vid videospel
Med all spänning över neurala nätverk och djupinlärningstekniker är det lätt att föreställa sig att datavetenskapens värld består av lite annat. Neurala nätverk har trots allt börjat överträffa människor i uppgifter som objekt- och ansiktsigenkänning och i spel som schack, Go och olika arkadspel.
Dessa nätverk är baserade på hur den mänskliga hjärnan fungerar. Ingenting kan ha mer potential än så, eller hur?
Inte riktigt. En helt annan typ av datoranvändning har potential att vara betydligt mer kraftfull än neurala nätverk och djupinlärning. Denna teknik är baserad på den process som skapade den mänskliga hjärnan – evolution. Med andra ord, en sekvens av iterativ förändring och urval som producerade de mest komplexa och kapabla maskiner som mänskligheten känner till – ögat, vingen, hjärnan och så vidare. Evolutionens kraft är ett under att se.
Det är därför datavetare länge har försökt att utnyttja dess kapacitet. Så kallad evolutionär datoranvändning har uppnått en del anmärkningsvärda prestationer under de 30 år som gått sedan den började användas för att optimera fabriksproduktionslinjer för traktorer.
Men under de senaste åren har detta område av datavetenskap fått spela andra fiol till maskiner för djupinlärning och deras enorma framgång.
Idag ser det ut att vända tack vare Dennis Wilsons och några kollegors arbete vid universitetet i Toulouse i Frankrike. Dessa killar har visat hur evolutionär datoranvändning kan matcha prestandan hos maskiner för djupinlärning på emblematisk uppgift som först fick dem att bli berömmelse 2013 – förmågan att överträffa människor i arkadspel som Pong, Breakout och Space Invaders. Arbetet föreslår att evolutionär datoranvändning bör presenteras lika brett som dess djupinlärningsbaserade relationer.
Evolutionär datoranvändning fungerar på ett helt annat sätt än neurala nätverk. Målet är att skapa datorkod som löser ett specifikt problem med ett tillvägagångssätt som är något kontraintuitivt.
Det konventionella sättet att skapa kod är att skriva den från första principer med ett specifikt mål i åtanke.
Evolutionär datoranvändning använder ett annat tillvägagångssätt. Det börjar med kod som genereras helt slumpmässigt. Och inte bara en version av den, utan massor av versioner, ibland hundratusentals slumpmässigt sammansatta kodbitar.
Var och en av dessa koder testas för att se om den uppnår det önskade målet. Och naturligtvis är all kod hemsk eftersom den genereras slumpmässigt.
Men av en slump är vissa kodbitar lite bättre än andra. Dessa bitar reproduceras sedan i en ny generation kod, som innehåller fler kopior av de bättre koderna.
Nästa generation kan dock inte vara en identisk kopia av den första. Istället måste det förändras på något sätt. Dessa förändringar kan innebära att man byter två termer i koden - en sorts punktmutation. Eller de kan involvera två koder som skärs på mitten och halvorna byts ut – som sexuell rekombination.
Var och en av den nya generationen testas sedan för att se hur väl den fungerar. De bästa kodbitarna reproduceras företrädesvis i en annan generation, och så vidare.
På så sätt utvecklas koden. Med tiden blir det bättre, och efter många generationer, om förutsättningarna är de rätta, kan det bli bättre än vad någon mänsklig kodare kan designa.
Datavetare har framgångsrikt tillämpat evolutionära metoder för problem som sträcker sig från att designa robotar till att bygga flygplansdelar.
Men det har fallit i onåd på grund av det enorma intresset för djupinlärning. Så en viktig fråga är om den kan matcha prestandan hos maskiner för djupinlärning. För att ta reda på det använde Wilson och co metoden för att utveckla kod som kunde styra arkaddatorspel från 1980- och 1990-talen.
Dessa spel finns tillgängliga i en databas som kallas Arcade Learning Environment, som i allt högre grad används för att testa inlärningsbeteendet hos algoritmer av olika slag. Databasen består av 61 Atari-spel, såsom Pong, Space Invaders, Breakout och Kung Fu Master.
Uppgiften är att skapa en algoritm som kan spela ett spel som Pong genom att bara titta på resultatet från skärmen, på samma sätt som människor spelar. Så algoritmen måste analysera varje spelposition och sedan bestämma hur den ska flytta för att maximera sin poäng.
Kontrollerna för alla spel är desamma. Dessa motsvarar de åtta riktningar som kontrollenheten kan flyttas (upp, ner, vänster och höger plus fyra diagonala riktningar), en knapptryckning, samma åtta rörelser kombinerade med en knapptryckning, och inte göra någonting alls. Alla spel använder inte alla 18 möjliga kombinationer, och vissa använder så få som fyra.
Koden måste först skapas. Det evolutionära tillvägagångssättet kräver en vokabulär av termer som kan sammanfogas för att bilda datorkod. Termerna sträcker sig från enkla åtgärder som ADD (x+y)/2 till mer komplexa, som att returnera 1-elementet x-vektor om x är en skalär.
Valet av termer som utgör detta ordförråd är viktigt, och Wilson och co använder en uppsättning som redan definierats för kartesisk genetisk programmering (som deras teknik kallas).
Processen börjar med att slumpmässigt skapa en kod som innehåller 40 termer. Detta är genomet av programmet. Detta genom testas sedan för att se hur bra det spelar spelet, enligt poängen. Beroende på hur bra det presterar reproduceras genomet sedan med mutationer och testas igen osv. Totalt testade teamet 10 000 genom på detta sätt.
Resultaten ger intressant läsning. Till en början är genomerna hemska på att spela spelet. Men med tiden blir de bättre. Och efter många generationer spelar de bra, ibland bättre än människor.
Många genom slutade med att spela helt nya spelstrategier, ofta komplexa. Men de hittade ibland enkla som människor hade förbisett.
Till exempel, när man spelade Kung Fu Master, upptäckte den evolutionära algoritmen att den mest värdefulla attacken var en hukning. Att huka sig är säkrare eftersom det undviker hälften av kulorna riktade mot spelaren och även attackerar allt i närheten. Algoritmens strategi var att upprepade gånger använda denna manöver utan andra åtgärder. I efterhand är det bara meningsfullt att använda crouch-punchen.
Det förvånade de mänskliga aktörerna som var inblandade i studien. Genom att använda denna strategi för hand fick man bättre poäng än att spela spelet normalt, och författaren använder nu enbart hukande slag när han attackerar i det här spelet, säger Wilson och co.
Sammantaget spelade den utvecklade koden många av spelen bra, till och med överträffade människor i spel som Kung Fu Master. Lika viktigt är att den utvecklade koden är lika bra som många djupinlärningsmetoder och överträffar dem i spel som Asteroids, Defender och Kung Fu Master.
Det ger också ett resultat snabbare. Även om programmen är relativt små, är många kontroller konkurrenskraftiga med toppmoderna metoder för Atari benchmark set och kräver mindre träningstid, säger Wilson och co.
Den utvecklade koden har en annan fördel. Eftersom den är liten är det lätt att se hur den fungerar. Däremot är ett välkänt problem med tekniker för djupinlärning att det ibland är omöjligt att veta varför de har fattat särskilda beslut, och detta kan få praktiska och juridiska konsekvenser.
Sammantaget är detta intressant arbete som borde antyda för datavetare som uteslutande fokuserar på djupinlärning att de kanske saknar ett knep. Det evolutionära tillvägagångssättet är ett kraftfullt alternativ som kan tillämpas i en mängd olika situationer.
Vissa forskare har faktiskt börjat använda det för att utveckla bättre djupinlärningsmaskiner. Vad kan gå fel?
Ref: https://arxiv.org/abs/1806.05695 : Utveckling av enkla program för att spela Atari-spel