Op het gebied van kunstmatige intelligentie is een evolutionair algoritme (EA) een subset van berekeningen van de totale populatie op basis van metaheuristische optimalisatie. EA gebruikt mechanismen die zijn geïnspireerd op biologische ontwikkeling zoals reproductie, mutatie, recombinatie en selectie. De kandidaat-oplossing in het probleem van evolutionaire optimalisatie-algoritmen speelt de rol van individuen in de populatie. En ook de fitnessfunctie bepa alt de kwaliteit van de antwoorden.
Evolutionaire algoritmen benaderen vaak oplossingen voor alle soorten problemen goed. Omdat ze idealiter geen aannames doen over het onderliggende fitnesslandschap. Methoden die worden gebruikt voor evolutionaire modellering en genetische algoritmen zijn meestal beperkt tot studies van micro-evolutionaire processen en planningsmodellen op basis van cellulaire stadia. In de meeste echte EA-toepassingen is computationele complexiteit een belemmerende factor.
Eigenlijkdit probleem houdt verband met de schatting van de fitnessfunctie. Geschiktheidsbenadering is een oplossing om deze moeilijkheid te overwinnen. Een ogenschijnlijk eenvoudige EA kan echter vaak complexe problemen oplossen. Daarom kan er geen directe relatie zijn tussen de complexiteit van de reeks en het probleem. Meer details zijn te vinden in de boeken "Evolutionary Algorithms".
Implementatie
Stap één is om willekeurig een eerste populatie van individuen te maken.
Stap twee is het beoordelen van de geschiktheid van elk individu in deze groep (tijdslimiet, voldoende paraatheid, enz.).
Stap drie - herhaal de volgende regeneratiestappen tot ze zijn voltooid:
- Selecteer de meest geschikte mensen om mee te fokken (ouders).
- Breng nieuwe individuen die het evolutionaire algoritme hebben doorstaan met behulp van crossover en mutatie om nakomelingen te krijgen.
- Beoordeel de individuele fitheid van nieuwe mensen.
- Vervang de minst geschikte populatie door hen.
Typen
Genetisch algoritme is een evolutionaire reeks, het meest populaire type deskundige adviseur. Een oplossing voor het probleem wordt gezocht in de vorm van reeksen getallen (traditioneel binair, hoewel de beste representaties meestal die zijn die meer weerspiegelen in het probleem dat wordt opgelost) door operatoren toe te passen zoals recombinatie en mutatie (soms één, in sommige gevallen beide).). Dit type Expert Advisor wordt vaak gebruikt bij optimalisatieproblemen. Een andere naam hiervoor is fetura (van het Latijn voor "geboorte"):
- Genetische programmering. Het presenteert oplossingen als computercodes, en hun geschiktheid wordt bepaald door hun vermogen om rekentaken uit te voeren.
- Evolutionaire programmering. Vergelijkbaar met het evolutionaire genetische algoritme, maar de structuur is vast en de numerieke parameters kunnen veranderen.
- Programmeren van genexpressie. Ontwikkelt computertoepassingen, maar verkent het genotype-fenotype-systeem, waarbij projecten van verschillende grootte worden gecodeerd op lineaire chromosomen met een vaste lengte.
- Strategie. Werkt met vectoren van reële getallen als representaties van oplossingen. Gebruikt meestal zelfaanpassende evolutionaire mutatiesnelheidsalgoritmen.
- Differentiële ontwikkeling. Gebaseerd op vectorverschillen en daarom vooral geschikt voor numerieke optimalisatieproblemen.
- Neuroevolutie. Vergelijkbaar met evolutionair programmeren en genetische algoritmen. Maar de laatste zijn kunstmatige neurale netwerken, die de structuur en het gewicht van de verbindingen beschrijven. Genoomcodering kan direct of indirect zijn.
Vergelijking met biologische processen
Een mogelijke beperking van veel evolutionaire algoritmen is het ontbreken van een duidelijk onderscheid tussen genotype en fenotype. In de natuur ondergaat een bevruchte eicel een complex proces dat bekend staat als embryogenese om volwassen te worden. Aangenomen wordt dat deze indirecte codering genetische zoekopdrachten betrouwbaarder maakt (d.w.z. minder kans op fatale mutaties) en ook het vermogen van het organisme om zich te ontwikkelen kan verbeteren. Dergelijke indirecte (met andere woorden,generatieve of ontwikkelings) coderingen maken het ook mogelijk dat evolutie de regelmaat in de omgeving benut.
Recent werk in kunstmatige embryogenese of ontwikkelingssystemen probeert deze problemen aan te pakken. Bij het programmeren van genexpressie wordt het genotype-fenotype-gebied met succes verkend, waarbij het eerste bestaat uit lineaire multigene chromosomen met een vaste lengte, en het tweede uit vele expressiebomen of computerprogramma's van verschillende groottes en vormen.
Verwante technieken
Algoritmen omvatten:
- Mierenkolonie optimalisatie. Het is gebaseerd op het idee dat insecten naar voedsel zoeken door zich met feromonen te verbinden om paden te vormen. Vooral geschikt voor combinatorische optimalisatie en grafiekproblemen.
- Root slider algoritme. De maker werd geïnspireerd door de functie van plantenwortels in de natuur.
- Algoritme voor kunstmatige bijenkolonies. Gebaseerd op het gedrag van honingbijen. Het wordt voornamelijk voorgesteld voor numerieke optimalisatie en uitgebreid om combinatorische, begrensde en multiobjectieve problemen op te lossen. Het bijenalgoritme is gebaseerd op het foerageergedrag van insecten. Het is in veel toepassingen toegepast, zoals routering en planning.
- Particle zwerm optimalisatie - gebaseerd op ideeën over kuddegedrag van dieren. En ook vooral geschikt voor numerieke procestaken.
Andere populaire metaheuristische methoden
- Zoeken op jacht. Een methode die gebaseerd is op het in groep vangen van bepaalde dieren, zoals wolven, die:verdelen hun taken om de prooi te omringen. Elk van de leden van het evolutionaire algoritme heeft op de een of andere manier betrekking op de anderen. Dit geldt vooral voor de leider. Dit is een continue optimalisatiemethode aangepast als een combinatorische procesmethode.
- Zoeken op afmetingen. In tegenstelling tot op de natuur gebaseerde metaheuristische methoden, gebruikt het adaptieve procesalgoritme geen metafoor als hoofdprincipe. Het gebruikt eerder een eenvoudige prestatiegerichte methode die is gebaseerd op het bijwerken van de parameter voor zoekdimensieverhouding bij elke iteratie. Het Firefly-algoritme is geïnspireerd op hoe vuurvliegjes elkaar aantrekken met hun flitsende licht. Dit is vooral handig voor multimodale optimalisatie.
- Zoek naar harmonie. Gebaseerd op de ideeën van het gedrag van muzikanten. In dit geval zijn evolutionaire algoritmen de beste keuze voor combinatorische optimalisatie.
- Gaussiaanse aanpassing. Gebaseerd op informatietheorie. Wordt gebruikt om de prestaties en de gemiddelde beschikbaarheid te maximaliseren. Een voorbeeld van evolutionaire algoritmen in deze situatie: entropie in thermodynamica en informatietheorie.
Memetic
Een hybride methode gebaseerd op Richard Dawkins' idee van een meme. Het neemt meestal de vorm aan van een populatiegebaseerd algoritme in combinatie met individuele leerprocedures die lokale verfijningen kunnen uitvoeren. Benadrukt het gebruik van probleemspecifieke kennis en pogingen om fijnmazige en globale zoekopdrachten op een synergetische manier te organiseren.
Evolutionairalgoritmen zijn een heuristische benadering van problemen die niet gemakkelijk in polynomiale tijd kunnen worden opgelost, zoals klassieke NP-harde problemen en al het andere dat te lang zou duren om volledig te verwerken. Wanneer ze onafhankelijk worden gebruikt, worden ze meestal gebruikt voor combinatorische problemen. Genetische algoritmen worden echter vaak gebruikt in combinatie met andere methoden, en fungeren als een snelle manier om meerdere optimale startplaatsen te vinden om mee te werken.
Het uitgangspunt van het evolutionaire algoritme (bekend als een adviseur) is vrij eenvoudig, aangezien je bekend bent met het proces van natuurlijke selectie. Het bevat vier hoofdstappen:
- initialisatie;
- keuze;
- genetische operatoren;
- einde.
Elk van deze stappen komt ruwweg overeen met een bepaald aspect van natuurlijke selectie en biedt gemakkelijke manieren om die categorie algoritmen te modulariseren. Simpel gezegd, in EA zullen de sterkste leden overleven en zich voortplanten, terwijl de ongeschikte leden zullen sterven en niet bijdragen aan de genenpool van de volgende generatie.
Initialisatie
Om het algoritme te starten, moet u eerst een reeks oplossingen maken. De populatie zal een willekeurig aantal mogelijke probleemstellingen bevatten, vaak leden genoemd. Ze worden vaak willekeurig gegenereerd (binnen de beperkingen van de taak) of, als enige voorkennis bekend is, voorlopig gecentreerd rond wat als ideaal wordt beschouwd. Het is belangrijk dat de populatie een breed scala aan oplossingen omvat,omdat het in wezen een genenpool is. Daarom, als men veel verschillende mogelijkheden binnen een algoritme wil onderzoeken, moet men ernaar streven om veel verschillende genen te hebben.
Keuze
Zodra de populatie is gemaakt, moeten de leden ervan worden geëvalueerd volgens de fitnessfunctie. De fitnessfunctie neemt de kenmerken van een lid en geeft een numerieke weergave van hoe fit het lid is. Het maken ervan kan vaak erg moeilijk zijn. Het is belangrijk om een goed systeem te vinden dat de gegevens nauwkeurig weergeeft. Dit is heel specifiek voor het probleem. Nu is het nodig om de geschiktheid van alle deelnemers te berekenen en enkele van de beste leden te selecteren.
Meerdere objectieve functies
EA's kunnen ook worden uitgebreid om deze systemen te gebruiken. Dit bemoeilijkt het proces enigszins, omdat in plaats van het identificeren van één optimaal punt, een set wordt verkregen wanneer ze worden gebruikt. De reeks oplossingen wordt de Pareto-grens genoemd en bevat elementen die even geschikt zijn in die zin dat geen van hen de andere domineert.
Genetische operatoren
Deze stap omvat twee substappen: crossover en mutatie. Na het selecteren van de beste termen (meestal de top 2, maar dit aantal kan variëren), worden ze nu gebruikt om de volgende generatie in het algoritme te creëren. Door de eigenschappen van de gekozen ouders toe te passen, ontstaan nieuwe kinderen die een mengelmoes zijn van eigenschappen. Dit kan vaak moeilijk zijn, afhankelijk van het type gegevens, maar meestal bij combinatorische problemenhet is heel goed mogelijk om geldige combinaties te mixen en uit te voeren.
Nu is het nodig om nieuw genetisch materiaal in de generatie te introduceren. Als deze belangrijke stap niet wordt gezet, zal de wetenschapper heel snel vast komen te zitten in lokale extremen en geen optimale resultaten krijgen. Deze stap is een mutatie, en het wordt heel eenvoudig gedaan, waarbij een klein deel van de kinderen zodanig wordt veranderd dat ze overwegend geen subsets van de genen van de ouders weerspiegelen. Mutatie treedt meestal probabilistisch op, aangezien de kans dat een kind het zal krijgen, evenals de ernst ervan, wordt bepaald door de verdeling.
Beëindiging
Uiteindelijk moet het algoritme eindigen. Dit gebeurt meestal in twee gevallen: of het heeft een maximale uitvoeringstijd bereikt, of het heeft een prestatiedrempel bereikt. Op dit punt wordt de uiteindelijke oplossing geselecteerd en geretourneerd.
Voorbeeld van evolutionaire algoritmen
Om het resultaat van dit proces te illustreren, moet u de adviseur in actie zien. Om dit te doen, kunnen we ons herinneren hoe verschillende generaties dinosaurussen leerden lopen (geleidelijk het land beheersen), de structuur van hun lichaam optimaliseerden en spierkracht toepasten. Hoewel de reptielen van de vroege generatie niet konden lopen, was de adviseur in staat om ze in de loop van de tijd door mutatie en kruising te ontwikkelen tot een vorm die kon lopen.
Deze algoritmen worden steeds relevanter in de moderne wereld, aangezien oplossingen op basis ervan steeds vaker worden gebruikt in sectoren zoals digitale marketing, financiën engezondheidszorg.
Waar worden EA's gebruikt?
Meer in het algemeen worden evolutionaire algoritmen gebruikt in een breed scala aan toepassingen, zoals beeldverwerking, voertuigroutering, optimalisatie van mobiele communicatie, softwareontwikkeling en zelfs kunstmatige neurale netwerktraining. Deze tools vormen de kern van veel van de apps en websites die mensen dagelijks gebruiken, waaronder Google Maps en zelfs games zoals The Sims. Bovendien gebruikt de medische sector EA om klinische beslissingen te nemen over de behandeling van kanker. Evolutionaire algoritmen zijn zelfs zo robuust dat ze kunnen worden gebruikt om bijna elk optimalisatieprobleem op te lossen.
Wet van Moore
De groeiende prevalentie van EO wordt aangedreven door twee hoofdfactoren: beschikbare rekenkracht en de accumulatie van grote datasets. De eerste kan worden beschreven door de wet van Moore, die in wezen stelt dat de hoeveelheid rekenkracht in een computer ongeveer elke twee jaar verdubbelt. Deze voorspelling geldt al tientallen jaren. De tweede factor heeft betrekking op de groeiende afhankelijkheid van technologie, waardoor instellingen een ongelooflijk grote hoeveelheid gegevens kunnen verzamelen, waarmee ze trends kunnen analyseren en producten kunnen optimaliseren.
Hoe kunnen evolutionaire algoritmen marketeers helpen?
De marktomstandigheden veranderen snel en zijn zeer competitief. Dit heeft marketingmanagers gedwongen om te strijden voor betere besluitvorming. Toename in beschikbaarrekenkracht heeft ertoe geleid dat werknemers EA gebruiken voor het oplossen van problemen.
Conversie-optimalisatie
Een van de belangrijkste doelen is om het aantal bezoekers van de site te verhogen. Dit probleem komt neer op het optimaliseren van het aantal gebruikers dat doet wat de marketeer wil. Als een bedrijf bijvoorbeeld laptops verkoopt, is het ideaal om het aantal sitebezoekers dat het product uiteindelijk koopt, te vergroten. Dit is de essentie van optimalisatie van de conversieratio.
Een van de verrassend belangrijke aspecten is de keuze van de gebruikersinterface. Als het webdesign niet erg gebruiksvriendelijk is, zijn er mensen die het product om de een of andere reden niet kopen. Het doel is dan om het aantal gebruikers dat uiteindelijk niet converteert te verminderen, wat de totale winst verhoogt.
