Abstract-Den icke-linjära komplexiteten hos evolutionära algoritmer (EAs) gör dem till en utmaning att förstå. Svårigheten att utföra detaljerade analyser av en EA är att sortera igenom den stora mängd data som kan genereras på en enda körning. Detta dokument beskriver ett visualiseringsverktyg som underlättar navigering genom detaljerna i en EA-körning. Visualiseringsverktyget organiserar och visar EA-data på olika detaljnivåer och möjliggör enkla övergångar mellan relaterade data. Det stora antalet komplexa, icke-linjära interaktioner som komponerar evolutionära algoritmer (EAs) gör dem svåra att analysera och en utmaning att förstå. De vanligaste metoderna för utvärdering av EA, som inkluderar evolutionär programmering, evolutionära strategier och genetiska algoritmer (GAS), fokuserar på övergripande resultat och statistik över bruttopopulationen. Sådana metoder inkluderar att jämföra antalet funktionsutvärderingar som krävs för att hitta en godtagbar lösning, kvaliteten på den lösning som hittats, eller graden av ökning av befolkningens lämplighet. Effektiviteten hos särskilda mekanismer, t.ex. crossover, kan uppskattas genom att man jämför EA:s totala prestanda med och utan att mekanismen slås på. Även om sådana mätningar är viktiga och ger användbar uppifrån-och-ned-information om EA-körningar, kan fokusering endast på denna information leda till att vi missar andra viktiga detaljer. Till exempel har flera studier undersökt icke-kodande regioners effekter på GA-prestanda. Dessa regioner förväntades förbättra prestanda genom att tillhandahålla en buffert mot de störande effekterna av crossover; jämförelser visade dock liten skillnad i övergripande C A prestanda (Forrest & Mitchell, 1992; Wu & Lindsay, 1995). I en senare studie som undersökte detaljerna i reproduktionen konstaterades det att icke-kodningsregioner faktiskt minskade de störande effekterna av crossover i byggstenar (Wu, Lindsay & Riolo, 1997). Icke-kodande regioner minskade faktiskt crossovers totala verksamhet inom byggblocksregioner, inklusive crossovers förmåga att bygga nya byggstenar. Denna minskning av konstruktionen tycktes ta bort alla fördelar med den förväntade minskningen av störningar, vilket resulterade i små märkbara förbättringar av den totala prestandan. Sådana komplexa, icke-linjära interaktioner finns i alla typer av EA och föreslår att vi, för att till fullo förstå hur EA fungerar, inte bara måste undersöka slutresultatet av EA-körningar utan också medlen för att nå målet. Svårigheten att utföra sådana analyser ligger i att sortera igenom den stora mängd data som kan genereras i en enda EA-körning. All data från en EA-körning kan enkelt sparas i filer, men att få tillgång till och tolka en så stor mängd information är ingen trivial uppgift. Utvecklingen av verktyg för att sortera, organisera och visa sådana databaser skulle i hög grad kunna underlätta tillgången till och analysen av sådana data. Sådana verktygs önskvärda förmåga inkluderar förmågan att göra följande: att undersöka individer och deras kodningar i detalj för att spåra källan till och överlevnaden av byggstenar eller partiella lösningar för att spåra släktträd för att undersöka effekterna av genetiska aktörer för att undersöka populationer för konvergens, specificering, etc. Att spåra statistik över bruttobefolkningar och trender för att röra sig fritt i tid och genom befolkningar. En strategi för detta problem är off-line visualisering. Vi har utvecklat ett sådant system, VIS, för att underlätta analys av data från projektet Virtual Virus (VIV) (Burke, De Jong, Grefenstette, Ramsey & Wu, 1999). VIS utnyttjar effektiviteten i grafiska representationer och flexibiliteten i en "klickbar" länk för att tillhandahålla ett navigeringsverktyg för åtkomst och visning av data. I resten av detta dokument kommer vi att sammanfatta tidigare tillvägagångssätt för att visualisera EA och beskriva VIS-systemet och hur det adresserar några av de önskade funktionerna som anges ovan. Även om de exempel som visas i detta dokument främst kommer från VIV-projektet som bygger på en GA, kan VIS-programmet enkelt utvidgas till att stödja andra EA-data. Grafisk visualisering teknik är några av de enklaste och samtidigt mest kraftfulla metoder för att analysera och kommunicera information (Tufte, 1983). Väl utformad 0-7803-5536-9/99/$10.00 0 1999 IEEE 1419 grafiska element kan förmedla stora mängder information i mycket koncisa och kompakta format. Dessutom är det mänskliga visionssystemet extremt känsligt för grafiska mönster, vilket gör grafiska representationer till ett extremt användbart analysverktyg. Visualiseringstekniker har använts för att studera EAS både on-line och offline. Nätbaserade system gör det möjligt för användare att noggrant följa och utvärdera utvecklingen av ett EA och kan i vissa fall göra det möjligt för användare att interaktivt påverka eller vägleda utvecklingen av systemet (Collins, 1998; Jones, 1993). Off-line-system använder visualiseringstekniker för att visa information om en EA-körning efter den är klar och kan tillåta visning av data från flera gånger av en körning och rörelse både framåt och bakåt i den evolutionära processen (Shine & Eick, 1997). De mest grundläggande visningarna som har använts inkluderar populationsdatamatriser som helt enkelt presenterar en hel population i råtextformat och tvådimensionella figurer av enskilda aspekter av befolkningen (t.ex. bästa eller genomsnittliga lämplighet) med avseende på tid. Mer komplexa tekniker har fokuserat på hur man kan visa mer omfattande information om hela populationer. Exempel är metoder för att visa fördelningen av befolkningen i lösningsutrymmet (Collins, 1997; Collins, 1998; Nassersharif, Ence & Au, 1994; Shine & Eick, 1997), allelfrekvenser (Collins, 1997; Wu & Lindsay, 1996), bildandet och variationen av arter (Spears, 1994), och anor av individer (Spears, 1994 ) från generation till generation. EA-systemens flerdimensionella karaktär gör detta till en balansgång mellan tydligheten i displayen och den mängd information som kan ingå. VIS är ett off-line visualiseringsprogram utvecklat för att underlätta undersökning och analys av GA-körningar. Detta system utformades med två huvudmål i åtanke. Ge användare med ett verktyg som de kan undersöka detaljerna i en C A körning. Verktyget bör ge enkel tillgång till önskad information och enkla övergångar mellan tillhörande information. Utveckla nya metoder och representationer för att visa flerdimensionella data på ett enhetligt och informativt sätt. VIS är organiserat som en samling fönster som visar data på olika upplösningsnivåer. Inom dessa fönster kombinerar VIS grafiska och textvisa displayer för att göra det möjligt för användare att se "snapshots" i tid från en C A körning, att undersöka specifika individer och populationer från en körning, och att navigera framåt och bakåt genom en körning. "Clickable" element i displayerna länka relaterade delar av information och gör det möjligt för användare att enkelt röra sig genom tid och bland befolkningen i en GA körning. Medan de flesta av de system som beskrivs i avsnitt 2 fokuserar på sätt att visa innehåll och utveckling av hela populationer och en EAS framsteg i lösningsutrymmet, är målet med VIS-verktyget att göra data från enskilda GA-körningar tillgängliga och lättillgängliga för observation och analys. Som ett resultat av detta fokuserar VIS mindre på att utveckla abstrakta representationer som kan vara genomsnittliga, interpolerade eller på annat sätt förlora detaljer, och mer på att visa fullständig information och tillhandahålla navigationsmöjligheter för att flytta från en del av en körning till en annan. Eftersom VIS är ett offlinesystem används det endast efter att en GA-körning är klar. Varje C A-körning som ska analyseras ska generera en uppsättning datafiler som innehåller all information som krävs för att VIS ska kunna rekonstruera körningen fullständigt. Detaljer om filer och format ges i (Grefenstette, Burke, De Jong, Ramsey & Wu, 1997). De viktigaste inslagen i en GA är individerna från CA-populationerna. Dessa individer representerar potentiella lösningar på problemet som ska lösas och är vanligtvis kodade som strängar av tecken eller värden. Förmågan att undersöka individers bildande och struktur i ett C A är ett av de viktigaste syftena med att utveckla VIS-verktyget. Som ett resultat, hur vi representerar eller visar individer är mycket viktigt. VIS kan visa individerna i en C A-körning i både text- och grafiska representationer. Grafiska representationer kan förbättra analysen av textinformation av flera skäl. Färgblock eller remsor är både lättare att särskilja och kräver mindre utrymme än enskilda tecken eller bokstäver (tillåt visning av längre individer). Dessutom, likheter och skillnader i färgband mönster är mycket lätt för mänskliga synsystem för att upptäcka, underlätta jämförelsen av flera individer. VIS gör det möjligt för användare att välja mellan flera olika metoder för att representera enskilda personer. Medan nuvarande representationer fokuserar på diskreta alfabet -binär och multi-tecken -VIS kan enkelt utökas för att stödja flyttal representationer och andra problemspecifika representationer vid behov. I tabell 1 visas exempel på de representationer som för närvarande finns tillgängliga. Genotyp- representationen visar varje individ som en teckensträng. För binära alfabet är tecknen antingen noll (0) eller ett (1). Alternativa representationer som använder mer än två värden kan bestå av andra tecken. Denna representation kan användas för alla alfabet. Zebra representation fungerar med binära alfabet och visar individuaIs som en serie av svarta och vita ränder. En svart rand representerar en 0; en vit rand representerar en 1. Den neopolitiska representationen arbetar också med binära alfabet. Den här representationen tilldelar varje teckenpar en färg. Det finns fyra möjliga teckenpar; ett exempel på färgkodningsschema skulle vara: 0 0 = svart, 11 = vitt, ränder. Till exempel användes följande färgkodningsschema för VIV alfabetet: A = blått, C = rött, G = gult, T = grönt. Gene platsen fungerar med problem där grupper av tecken tillsammans komponera byggstenar eller partiella lösningar. Varje byggsten visas i en unik färg på en individ. Denna representation är särskilt användbar för att spåra konstruktion, spridning och avbrott i byggstenar. En av de mest grundläggande förmågorna som behövs för att studera GAS är enkel och direkt tillgång till någon individ av en körning. Eftersom individer är de mest grundläggande elementen i en CA, förmågan att undersöka dem i detalj, i själva verket, ger oss förmågan att rekonstruera händelser från någon del eller hela en körning. Eftersom lösningar kodas som individer, undersöker lämpligheten och sammansättningen av en individ i huvudsak gör att vi kan utvärdera en GAS framsteg vid en viss tidpunkt av en körning. Föräldra- och avkommajämförelser kan avslöja dynamiken kring fortplantningshändelser och hur effektivt information konstrueras, förökas och störs av olika genetiska aktörer. Enkel tillgång till en individs "familjemedlemmar" ger oss förmågan att spåra upptäckten och arvet av information från generation till generation. VIS tillhandahåller vissa av dessa funktioner med sitt individuella fönster. Ett enskilt fönster visar alla relevanta data som hör samman med en viss individ. Två format finns tillgängliga: Dataformatet visar vitalstatistiken för en individ och familjeformatet visar en grafisk representation av en komplett familj (en individ, dess föräldrar och dess avkomma). Figur 1 visar ett exempel på dataformatet. Följande information ingår i denna display.  Förutom att undersöka individer isolerat är det också viktigt att förstå hur individer förhåller sig till andra individer i befolkningen. Väl utformade grafiska displayer av en befolkning kan underlätta upptäckt av mönster eller trender i befolkningen som kan föreslå konvergens eller specificering. Övergripande egenskaper som mångfald, konvergens och specificeringsnivå kan vara viktiga indikatorer för en CA:s framsteg.  Fönster för den generationen. Consensus-formatet, som visas --i figur 7, visar statistik och en "consensus" individ för varje generation av en körning. Samförståndspersonen visar den vanligaste ordningen av gener i en population. Förutom att ge tillgång till mycket specifika uppgifter från en körning visar VIS även uppgifter om en hel körning. Spårning av bruttopopulation och körstatistik ger en allmän uppfattning om VIS-verktyget är ett off-line visualiseringsprogram utvecklat för att underlätta undersökning och analys av GAS. I stället för att enbart fokusera på metoder för att visa en god jordbrukshävd och goda miljöförhållanden i ett lösningsutrymme koncentrerar VIS sig på sätt att göra alla detaljer i en körning tillgängliga och lättillgängliga. Detta verktyg gör det möjligt för användare att undersöka ögonblicksbilder av en CA kör och undersöka frågor som hur var bitarna av en lösning ihop, när och varför gjorde en population konvergera, och vilka är de omedelbara effekterna av variation av parametrar såsom population storlek eller urvalsmetod. Vi har funnit VIS vara ett mycket användbart verktyg för att undersöka detaljer i en C A köra utöver genomsnittet och bästa kondition för varje befolkning. VIS gör det möjligt för oss att f0cu.s in på specifika detaljer av intresse, hålla relaterade data lättillgängliga och alla andra data tillgängliga. Det har varit särskilt användbart i situationer där vi annars skulle behöva skriva ut ohanterliga mängder data bara för att hitta eller undersöka några specifika exempel. VIS-verktyget spelade en viktig roll i våra analyser av experiment från VIV-projektet. Med hjälp av VIS kunde vi hitta specifika exempel för att verifiera att en CA, med tanke på möjligheten, kommer att behålla säkerhetskopior av användbar information och använda denna säkerhetskopia information om primär information störs. Dessutom kunde vi i detalj undersöka befolkningskonvergensen och de genetiska aktörernas effekter. Fullständiga beskrivningar av dessa studier finns i (Burke, De Jong, Grefenstette, Ramsey & Wu, 1999;. Vi har också funnit VIS-verktyget vara mycket användbart för utvecklings- och verifieringsändamål. I utvecklingen av nya CA program och applikationer, med hjälp av ett visualiseringsverktyg för att verifiera nya representationer och metoder kan vara betydligt enklare och mindre tidskrävande än alternativet att skriva ut och kontrollera information på papper eller på skärmen. I huvudsak kan VIS ses som en avlusare, men på algoritmisk nivå snarare än kodnivå. I det framtida arbetet med detta projekt ingår fortsatt utveckling av effektiva displayer av individ- och befolkningsdata och interaktiva sorteringsmöjligheter. Vi skulle vilja utvidga grafiska representationer av individer för att stödja ytterligare problem representationer, inklusive flyttalsvärden och eventuellt tvådimensionella strukturella representationer. Dessutom planerar vi också att lägga till automatiserad datainsamling och statistiska analysalternativ för att samla in, beräkna och plotta data som antal avkomma som genereras eller upptäckt och förlust av partiella lösningar över hela körningar eller populationer. Erkännande
Ett verktyg utvecklat av Wu et al. REF ) kallas VIS för att analysera detaljerna i en evolutionär algoritm (EA) kör.
Visual analysis of evolutionary algorithms
{'venue': 'Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406)', 'journal': 'Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406)', 'mag_field_of_study': ['Computer Science']}