Nästan alla vetenskaps- och ingenjörsfält använder sökalgoritmer, som automatiskt utforskar ett sökområde för att hitta högpresterande lösningar: kemister söker genom molekyler för att upptäcka nya läkemedel; ingenjörer söker efter starkare, billigare, säkrare konstruktioner, forskare söker efter modeller som bäst förklarar data, etc. Målet med sökalgoritmer har traditionellt varit att returnera den enskilda lösningen med högsta prestanda i ett sökområde. Här beskriver vi en ny, fundamentalt annorlunda typ av algoritm som är mer användbar eftersom den ger en helhetsbild av hur högpresterande lösningar distribueras i ett sökområde. Det skapar en karta över högpresterande lösningar vid varje punkt i ett utrymme som definieras av dimensioner av variation som en användare får välja. Detta flerdimensionella arkiv av fenotypiska Eliter (MAP-Elites) algoritm belyser sökytor, så att forskare kan förstå hur intressanta attribut av lösningar kombineras för att påverka prestanda, antingen positivt eller, lika av intresse, negativt. Till exempel, ett läkemedelsföretag kan vilja förstå hur prestandaförändringar som storleken på molekyler och deras kostnad-till-produce varierar. MAP-Elites producerar en stor mångfald av högpresterande, men kvalitativt olika lösningar, som kan vara till större hjälp än en enda, högpresterande lösning. Intressant, eftersom MAP-Elites utforskar mer av sökområdet, tenderar den också att hitta en bättre övergripande lösning än toppmoderna sökalgoritmer. Vi demonstrerar fördelarna med denna nya algoritm i tre olika problemområden som sträcker sig från att producera modulära neurala nätverk till att designa simulerade och riktiga mjuka robotar. Eftersom MAPElites (1) belyser förhållandet mellan prestanda och dimensioner av intresse för lösningar, (2) returnerar en uppsättning högpresterande, men ändå olika lösningar, och (3) förbättrar state-of-the-art för att hitta en enda, bästa lösning, kommer det att katalysera framsteg inom alla vetenskaps- och ingenjörsfält. Författarens anmärkning: Detta dokument är ett preliminärt utkast till ett dokument som introducerar MAP-Elites algoritm och utforskar dess möjligheter. Normalt skulle vi inte posta ett så tidigt utkast med endast preliminära experimentella data, men många människor i samhället har hört talas om MAP-Elites, använder det i sina egna papper, och har bett oss om en uppsats som beskriver det så att de kan citera det, hjälpa dem att genomföra MAP-Elites, och som beskriver de experiment vi redan har genomfört med det. Vi vill alltså dela med oss av både detaljerna i denna algoritm och vad vi har lärt oss av våra preliminära experiment. Alla experiment i denna tidning kommer att göras om innan den slutliga versionen av tidningen publiceras, och uppgifterna kan därmed komma att ändras. Varje område inom vetenskap och teknik använder sig av sökalgoritmer, även kallade optimeringsalgoritmer, som automatiskt försöker hitta en högkvalitativ lösning eller uppsättning högkvalitativa lösningar bland ett stort utrymme av möjliga lösningar 1, 2. Sådana algoritmer hittar ofta lösningar som överträffar de designade Fig. 1................................................................ MAP-Elites algoritm söker i ett högdimensionellt utrymme för att hitta den högst presterande lösningen vid varje punkt i ett lågdimensionellt funktionsutrymme, där användaren får välja dimensioner av variation av intresse som definierar det låga dimensionsutrymmet. Vi kallar denna typ av algoritm en "belysningsalgoritm", eftersom det belyser lämpligheten i varje område av funktionen utrymme, inklusive kompromisser mellan prestanda och funktioner av intresse. Till exempel kunde MAP-Elites söka i utrymmet för alla möjliga robotkonstruktioner (ett mycket stort utrymme) för att hitta den snabbaste roboten (ett prestandakriterium) för varje kombination av längd och vikt. av mänskliga ingenjörer 3 : de har utformat antenner som NASA flög till rymden 4, fann patenterbara elektroniska kretsmönster 3, automatiserad vetenskaplig upptäckt 5, och skapade artificiell intelligens för robotar [6] [7] [8] [9] [10] [11] [12] [12] [13] [14] [15]. På grund av deras utbredda användning ger förbättrade sökalgoritmer betydande fördelar för samhället. De flesta sökalgoritmer fokuserar på att hitta en eller en liten uppsättning högkvalitativa lösningar i ett sökområde. Vad som utgör hög kvalitet bestäms av användaren, som anger ett eller några mål som lösningen bör poängsätta högt på. Till exempel, en användare kan vilja lösningar som är högpresterande och låg kostnad, där var och en av dessa desiderata är kvantifierbar mäts antingen med en ekvation eller simulator. Traditionella sökalgoritmer inkluderar klättring av kullar, simulerad glödgning, evolutionära algoritmer, lutningsstigning/nedstigning, Bayesian optimering och multiobjektiva optimeringsalgoritmer 1, 2. Den senare återger en uppsättning lösningar som utgör de bästa kompromisserna mellan mål 16. En delmängd av optimeringsproblem är utmanande eftersom de kräver sökning efter optima i en funktion eller system som antingen är icke-differentiable eller inte kan uttryckas matematiskt, typiskt eftersom ett fysiskt system eller en komplex simulering krävs. Sådana problem kräver "svarta box" optimeringsalgoritmer, som söker efter högpresterande lösningar beväpnade endast med förmågan att bestämma prestandan hos en lösning, men utan tillgång till den utvärderingsfunktion som bestämmer denna prestanda. Vid sådana problem kan man inte använda optimeringsmetoder som kräver att man beräknar gradienten för funktionen, såsom lutningsstigning/uppstigning. En ökänd utmaning i svart box optimering är närvaron av lokala optima (även kallad lokala minima) 1, 2. Ett problem med de flesta sökalgoritmer i denna klass är att de försöker följa en väg som kommer att leda till den bästa globala lösningen genom att förlita sig på heurismen att slumpmässiga förändringar till bra lösningar leder till bättre lösningar. Detta tillvägagångssätt fungerar dock inte för mycket vilseledande problem, eftersom man i sådana problem måste korsa lågpresterande dalar för att hitta den globala optiman, eller bara för att hitta bättre optima 2. Eftersom evolutionära algoritmer är en av de mest framgångsrika-
MAP-Elites algoritm av Mouret och Clune REF kombinerar ett prestandamål f och ett användardefinierat utrymme av funktioner som beskriver kandidatlösningar (som inte krävs av FFA).
Illuminating search spaces by mapping elites
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Biology']}