Inom området artificiell intelligens är en evolutionär algoritm (EA) en delmängd av totala populationsberäkningar baserade på metaheuristisk optimering. EA använder mekanismer inspirerade av biologisk utveckling såsom reproduktion, mutation, rekombination och selektion. Kandidatlösningen i problemet med evolutionära optimeringsalgoritmer spelar rollen som individer i befolkningen. Och även fitnessfunktionen avgör kvaliteten på svaren.
Evolutionära algoritmer uppskattar ofta lösningar på alla typer av problem väl. Eftersom de idealiskt sett inte gör några antaganden om det underliggande fitnesslandskapet. Metoder som används för evolutionär modellering och genetiska algoritmer är vanligtvis begränsade till studier av mikroevolutionära processer och planeringsmodeller baserade på cellulära stadier. I de flesta riktiga EA-applikationer är beräkningskomplexitet en oöverkomlig faktor.
Faktisktdet här problemet är relaterat till uppskattning av fitnessfunktion. Konditionsuppskattning är en lösning för att övervinna denna svårighet. En till synes enkel EA kan dock lösa ofta komplexa problem. Därför kan det inte finnas något direkt samband mellan sekvensens komplexitet och problemet. Mer information finns i böckerna "Evolutionära algoritmer".
Implementation
Steg ett är att skapa en initial population av individer slumpmässigt.
Steg två är att bedöma lämpligheten för varje individ i denna grupp (tidsgräns, tillräcklig beredskap etc.).
Steg tre – upprepa följande regenereringssteg tills de är klara:
- Välj de mest lämpliga personerna för avel (föräldrar).
- Ta med nya individer som har klarat den evolutionära algoritmen med hjälp av crossover och mutation för att få avkomma.
- Utvärdera nya människors individuella kondition.
- Ersätt den minst vältränade befolkningen med dem.
Typer
Genetic Algorithm är en evolutionär sekvens, den mest populära typen av expertrådgivare. En lösning på problemet söks i form av talsträngar (traditionellt binära, även om de bästa representationerna vanligtvis är de som återspeglar mer i problemet som löses) genom att använda operatorer som rekombination och mutation (ibland en, i vissa fall båda). Denna typ av expertrådgivare används ofta i optimeringsproblem. Ett annat namn för detta är fetura (från latin för "födelse"):
- Genetisk programmering. Den presenterar lösningar som datorkoder, och deras lämplighet bestäms av deras förmåga att utföra beräkningsuppgifter.
- Evolutionär programmering. Liknar den evolutionära genetiska algoritmen, men strukturen är fixerad och dess numeriska parametrar kan ändras.
- Programmering av genuttryck. Utvecklar datorapplikationer, men utforskar genotyp-fenotypsystemet, där projekt av olika storlekar kodas på linjära kromosomer med fast längd.
- Strategi. Arbetar med vektorer av reella tal som representationer av lösningar. Använder vanligtvis självanpassande evolutionära mutationshastighetsalgoritmer.
- Differentiell utveckling. Baserat på vektorskillnader och därför i första hand lämplig för numeriska optimeringsproblem.
- Neuroevolution. Liknar evolutionär programmering och genetiska algoritmer. Men de senare är artificiella neurala nätverk, som beskriver strukturen och vikten av anslutningarna. Genomkodning kan vara direkt eller indirekt.
Jämförelse med biologiska processer
En möjlig begränsning av många evolutionära algoritmer är avsaknaden av en tydlig skillnad mellan genotyp och fenotyp. I naturen genomgår ett befruktat ägg en komplex process som kallas embryogenes för att bli mogen. Denna indirekta kodning tros göra genetiska sökningar mer tillförlitliga (dvs mindre sannolikt att orsaka dödliga mutationer) och kan också förbättra organismens förmåga att utvecklas. Sådana indirekta (med andra ord,generativa eller utvecklingsmässiga) kodningar tillåter också evolution att utnyttja regelbundenhet i miljön.
Närare arbete med artificiell embryogenes eller utvecklingssystem försöker ta itu med dessa problem. Vid programmering av genuttryck utforskas genotyp-fenotypregionen framgångsrikt, där den första består av linjära multigenkromosomer med fast längd, och den andra av många uttrycksträd eller datorprogram av olika storlekar och former.
Relaterade tekniker
Algorithms inkluderar:
- Optimering av myrkolonier. Det bygger på idén att insekter söker efter mat genom att ansluta sig till feromoner för att bilda stigar. I första hand lämplig för kombinatorisk optimering och grafproblem.
- Root slider-algoritm. Skaparen inspirerades av växtrötternas funktion i naturen.
- Algorithm för konstgjorda bisamhällen. Baserat på honungsbins beteende. Det föreslås i första hand för numerisk optimering och utökas för att lösa kombinatoriska, avgränsade och multiobjektiva problem. Bialgoritmen är baserad på insekters födosöksbeteende. Det har använts i många applikationer som routing och schemaläggning.
- Partikelsvärmoptimering - baserat på idéer om djurflockbeteende. Och även i första hand lämplig för numeriska processuppgifter.
Andra populära metaheuristiska metoder
- Jaktsökning. En metod som bygger på gruppfångst av vissa djur, som till exempel vargar, somfördela sina plikter för att omge bytet. Var och en av medlemmarna i den evolutionära algoritmen relaterar till de andra på något sätt. Detta gäller särskilt för ledaren. Detta är en kontinuerlig optimeringsmetod anpassad som en kombinatorisk processmetod.
- Sök efter mått. Till skillnad från naturbaserade metaheuristiska metoder använder den adaptiva processalgoritmen inte metafor som huvudprincip. Snarare använder den en enkel prestationsorienterad metod baserad på uppdatering av sökdimensionsförhållandeparametern vid varje iteration. Firefly-algoritmen är inspirerad av hur eldflugor attraherar varandra med sitt blinkande ljus. Detta är särskilt användbart för multimodal optimering.
- Sök efter harmoni. Baserat på idéer om musikernas beteende. I det här fallet är evolutionära algoritmer vägen att gå för kombinatorisk optimering.
- Gaussisk anpassning. Baserat på informationsteori. Används för att maximera prestanda och genomsnittlig tillgänglighet. Ett exempel på evolutionära algoritmer i denna situation: entropi i termodynamik och informationsteori.
Memetic
En hybridmetod baserad på Richard Dawkins idé om ett meme. Det tar vanligtvis formen av en populationsbaserad algoritm i kombination med individuella inlärningsprocedurer som kan utföra lokala förfining. Framhåller användningen av problemspecifik kunskap och försök att organisera finkorniga och globala sökningar på ett synergistiskt sätt.
EvolutionärtAlgoritmer är ett heuristiskt förhållningssätt till problem som inte enkelt kan lösas i polynomtid, såsom klassiskt NP-hårda problem och allt annat som skulle ta för lång tid att uttömmande bearbeta. När de används oberoende används de vanligtvis för kombinatoriska problem. Men genetiska algoritmer används ofta tillsammans med andra metoder, vilket fungerar som ett snabbt sätt att hitta flera optimala startplatser att arbeta med.
Förutsättningen för den evolutionära algoritmen (känd som en rådgivare) är ganska enkel med tanke på att du är bekant med processen med naturligt urval. Den innehåller fyra huvudsteg:
- initiering;
- choice;
- genetiska operatorer;
- end.
Var och en av dessa steg motsvarar ungefär en viss aspekt av naturligt urval och ger enkla sätt att modularisera den kategorin av algoritmer. Enkelt uttryckt, i EA kommer de starkaste medlemmarna att överleva och fortplanta sig, medan de olämpliga medlemmarna kommer att dö och inte bidra till nästa generations genpool.
initiering
För att starta algoritmen måste du först skapa en uppsättning lösningar. Populationen kommer att innehålla ett godtyckligt antal möjliga problemformuleringar, ofta kallade medlemmar. De genereras ofta slumpmässigt (inom uppgiftens begränsningar) eller, om vissa förkunskaper är kända, preliminärt centrerade kring vad som anses vara idealiskt. Det är viktigt att befolkningen täcker ett brett utbud av lösningar,eftersom det i grunden är en genpool. Därför, om man vill utforska många olika möjligheter inom en algoritm, bör man sträva efter att ha många olika gener.
Choice
När populationen har skapats måste dess medlemmar nu utvärderas enligt fitnessfunktionen. Fitnessfunktionen tar en medlems egenskaper och ger en numerisk representation av hur vältränad medlemmen är. Att skapa dem kan ofta vara mycket svårt. Det är viktigt att hitta ett bra system som korrekt representerar data. Detta är mycket specifikt för problemet. Nu är det nödvändigt att beräkna lämpligheten för alla deltagare och välja ut några av de bästa medlemmarna.
Flera målfunktioner
EA:er kan också utökas för att använda dessa system. Detta komplicerar processen något, eftersom istället för att identifiera en optimal punkt, erhålls en uppsättning när du använder dem. Uppsättningen av lösningar kallas Pareto-gränsen och innehåller element som är lika lämpliga i den meningen att ingen av dem dominerar någon annan.
Genetiska operatorer
Detta steg inkluderar två delsteg: korsning och mutation. Efter att ha v alt de bästa termerna (vanligtvis topp 2, men detta antal kan variera), används de nu för att skapa nästa generation i algoritmen. Genom att tillämpa egenskaperna hos de utvalda föräldrarna skapas nya barn som är en blandning av egenskaper. Detta kan ofta vara svårt beroende på typen av data, men oftast i kombinatoriska problemdet är fullt möjligt att blanda och mata ut giltiga kombinationer.
Nu är det nödvändigt att introducera nytt genetiskt material i generationen. Om detta viktiga steg inte tas kommer forskaren mycket snabbt att fastna i lokala extremer och inte få optimala resultat. Detta steg är en mutation, och det görs helt enkelt genom att förändra en liten del av barnen på ett sådant sätt att de till övervägande del inte återspeglar undergrupper av föräldrarnas gener. Mutation uppstår vanligtvis sannolikt, eftersom sannolikheten för att ett barn ska få det, såväl som dess svårighetsgrad, bestäms av distributionen.
Uppsägning
I slutändan måste algoritmen avslutas. Detta händer vanligtvis i två fall: antingen har det nått en viss maximal körningstid eller så har det nått en prestandatröskel. Vid denna tidpunkt väljs den slutliga lösningen och returneras.
Exempel på evolutionära algoritmer
Nu, för att illustrera resultatet av denna process, måste du se rådgivaren i aktion. För att göra detta kan vi komma ihåg hur flera generationer av dinosaurier lärde sig att gå (gradvis bemästra landet), optimera strukturen på sin kropp och applicera muskelstyrka. Även om den tidiga generationens reptiler inte kunde gå, kunde rådgivaren utveckla dem över tiden genom mutation och crossover till en form som kunde gå.
Dessa algoritmer blir allt mer relevanta i den moderna världen, eftersom lösningar baserade på dem i allt högre grad används i branscher som digital marknadsföring, finans ochsjukvård.
Var används EA?
Evolutionära algoritmer används i ett brett spektrum av applikationer som bildbehandling, fordonsdirigering, mobilkommunikationsoptimering, mjukvaruutveckling och till och med utbildning i konstgjorda neurala nätverk. Dessa verktyg är kärnan i många av de appar och webbplatser människor använder dagligen, inklusive Google Maps och till och med spel som The Sims. Dessutom använder det medicinska området EA för att hjälpa till att fatta kliniska beslut angående cancerbehandling. Faktum är att evolutionära algoritmer är så robusta att de kan användas för att lösa nästan alla optimeringsproblem.
Moores lag
Den växande prevalensen av EO drivs av två huvudfaktorer: tillgänglig datorkraft och ackumuleringen av stora datamängder. Den första kan beskrivas av Moores lag, som i huvudsak säger att mängden datorkraft i en dator fördubblas ungefär vartannat år. Denna förutsägelse har hållit i årtionden. Den andra faktorn hänför sig till det växande beroendet av teknik, vilket gör det möjligt för institutioner att samla in en otroligt stor mängd data, vilket gör att de kan analysera trender och optimera produkter.
Hur kan evolutionära algoritmer hjälpa marknadsförare?
Marknadsförhållandena förändras snabbt och är mycket konkurrenskraftiga. Detta har tvingat marknadschefer att konkurrera om bättre beslutsfattande. Ökning av tillgängligadatorkraft har fått arbetare att använda EA för problemlösning.
Konverteringsoptimering
Ett av huvudmålen är att öka antalet besökare på webbplatsen. Detta problem handlar om att optimera antalet användare som gör vad marknadsföraren vill. Till exempel, om ett företag säljer bärbara datorer, är det idealiska att öka antalet besökare som slutar med att köpa produkten. Detta är kärnan i omvandlingsfrekvensoptimering.
En av de förvånansvärt viktiga aspekterna är valet av användargränssnitt. Om webbdesignen inte är särskilt användarvänlig finns det de som slutar med att köpa produkten av en eller annan anledning. Målet är då att minska antalet användare som inte konverterar, vilket ökar den totala vinsten.
