Een genetisch algoritme is een adaptief heuristisch zoekalgoritme geïnspireerd op 'Darwin's evolutietheorie in de natuur' .' Het wordt gebruikt om optimalisatieproblemen bij machine learning op te lossen. Het is een van de belangrijke algoritmen omdat het helpt bij het oplossen van complexe problemen die veel tijd in beslag nemen.

Genetische algoritmen worden op grote schaal gebruikt in verschillende toepassingen in de echte wereld, bijvoorbeeld Het ontwerpen van elektronische circuits, het breken van codes, beeldverwerking en kunstmatige creativiteit.

In dit onderwerp zullen we het genetische algoritme in detail uitleggen, inclusief de basisterminologieën die worden gebruikt in het genetische algoritme, hoe het werkt, de voordelen en beperkingen van het genetische algoritme, enz.

plank honden

Wat is een genetisch algoritme?

Voordat we het genetische algoritme begrijpen, moeten we eerst de basisterminologieën begrijpen om dit algoritme beter te begrijpen:

Bevolking:Bevolking is de subset van alle mogelijke of waarschijnlijke oplossingen die het gegeven probleem kunnen oplossen.chromosomen:Een chromosoom is een van de oplossingen in de populatie voor het gegeven probleem, en de verzameling genen genereert een chromosoom.Gen:Een chromosoom is verdeeld in een ander gen, of het is een onderdeel van het chromosoom.Allelen:Allel is de waarde die aan het gen binnen een bepaald chromosoom wordt gegeven.Fitness functie:De fitnessfunctie wordt gebruikt om het fitnessniveau van een individu in de populatie te bepalen. Het betekent het vermogen van een individu om te concurreren met andere individuen. In elke iteratie worden individuen geëvalueerd op basis van hun fitnessfunctie.Genetische operators:In een genetisch algoritme kan de beste individuele partner het nageslacht beter regenereren dan de ouders. Hier spelen genetische operators een rol bij het veranderen van de genetische samenstelling van de volgende generatie.Selectie

Na het berekenen van de fitheid van iedereen in de populatie, wordt een selectieproces gebruikt om te bepalen welke van de individualiteiten in de populatie zich zullen kunnen voortplanten en het zaad zullen produceren dat de komende generatie zal vormen.

Soorten selectiestijlen beschikbaar

Roulette wiel selectie Selectie van evenementen Op rang gebaseerde selectie

Nu kunnen we een genetisch algoritme definiëren als een heuristisch zoekalgoritme om optimalisatieproblemen op te lossen. Het is een subset van evolutionaire algoritmen die bij computergebruik worden gebruikt. Een genetisch algoritme maakt gebruik van genetische en natuurlijke selectieconcepten om optimalisatieproblemen op te lossen.

Hoe werkt het genetische algoritme?

Het genetische algoritme werkt op de evolutionaire generatiecyclus om oplossingen van hoge kwaliteit te genereren. Deze algoritmen gebruiken verschillende bewerkingen die de populatie vergroten of vervangen om een ​​betere pasvormoplossing te bieden.

Het omvat in principe vijf fasen om de complexe optimalisatieproblemen op te lossen, die hieronder worden weergegeven:

Initialisatie Fitness opdracht Selectie Reproductie Beëindiging

1. Initialisatie

Het proces van een genetisch algoritme begint met het genereren van een reeks individuen, die populatie wordt genoemd. Hier is elk individu de oplossing voor het gegeven probleem. Een individu bevat of wordt gekarakteriseerd door een reeks parameters die genen worden genoemd. Genen worden gecombineerd tot een reeks en genereren chromosomen, wat de oplossing voor het probleem is. Een van de meest populaire technieken voor initialisatie is het gebruik van willekeurige binaire strings.

2. Fitnessopdracht

Fitnessfunctie wordt gebruikt om te bepalen hoe fit iemand is? Het betekent het vermogen van een individu om te concurreren met andere individuen. In elke iteratie worden individuen geëvalueerd op basis van hun fitnessfunctie. De fitnessfunctie geeft aan elk individu een fitnessscore. Deze score bepaalt verder de kans om geselecteerd te worden voor reproductie. Hoe hoog de fitnessscore, hoe groter de kans om geselecteerd te worden voor voortplanting.

3. Selectie

De selectiefase omvat de selectie van individuen voor de reproductie van nakomelingen. Alle geselecteerde individuen worden vervolgens in een paar van twee gerangschikt om de reproductie te vergroten. Vervolgens dragen deze individuen hun genen over aan de volgende generatie.

Er zijn drie soorten selectiemethoden beschikbaar, namelijk:

• Roulette wiel selectie
• Toernooi selectie
• Op rang gebaseerde selectie

4. Reproductie

Na het selectieproces vindt de creatie van een kind plaats in de reproductiestap. In deze stap gebruikt het genetische algoritme twee variatie-operatoren die worden toegepast op de ouderpopulatie. De twee operators die betrokken zijn bij de reproductiefase worden hieronder weergegeven:

Cross-over:De crossover speelt een zeer belangrijke rol in de reproductiefase van het genetische algoritme. In dit proces wordt willekeurig een crossoverpunt binnen de genen geselecteerd. Vervolgens wisselt de crossover-operator genetische informatie van twee ouders van de huidige generatie uit om een ​​nieuw individu te produceren dat het nageslacht vertegenwoordigt.

De genen van ouders worden onderling uitgewisseld totdat het kruispunt is bereikt. Deze nieuw gegenereerde nakomelingen worden aan de populatie toegevoegd. Dit proces wordt ook wel crossover genoemd. Soorten crossover-stijlen beschikbaar:
• Eén punt-crossover
• Tweepunts cross-over
• Cross-over in kleurstelling
• Overerfbare algoritmen crossover
Mutatie
De mutatieoperator voegt willekeurige genen in het nageslacht (nieuw kind) in om de diversiteit in de populatie te behouden. Dit kan worden gedaan door enkele stukjes in de chromosomen om te draaien.
Mutatie helpt bij het oplossen van het probleem van voortijdige convergentie en bevordert de diversificatie. De onderstaande afbeelding toont het mutatieproces:
Soorten mutatiestijlen beschikbaar,
Flip-bit-mutatie Gaussische mutatie Exchange/Swap-mutatie

5. Beëindiging

Na de reproductiefase wordt een stopcriterium toegepast als basis voor beëindiging. Het algoritme eindigt nadat de drempelfitheidsoplossing is bereikt. Het zal de uiteindelijke oplossing identificeren als de beste oplossing in de populatie.

Algemene workflow van een eenvoudig genetisch algoritme

Voordelen van genetisch algoritme

• De parallelle mogelijkheden van genetische algoritmen zijn het beste.
• Het helpt bij het optimaliseren van verschillende problemen, zoals discrete functies, problemen met meerdere doelstellingen en continue functies.
• Het biedt een oplossing voor een probleem dat in de loop van de tijd verbetert.
• Een genetisch algoritme heeft geen afgeleide informatie nodig.

Beperkingen van genetische algoritmen

• Genetische algoritmen zijn geen efficiënte algoritmen voor het oplossen van eenvoudige problemen.
• Het garandeert niet de kwaliteit van de uiteindelijke oplossing voor een probleem.
• Herhaalde berekeningen van fitnesswaarden kunnen enkele rekenproblemen met zich meebrengen.

Verschil tussen genetische algoritmen en traditionele algoritmen

• Een zoekruimte is de verzameling van alle mogelijke oplossingen voor het probleem. In het traditionele algoritme wordt slechts één reeks oplossingen gehandhaafd, terwijl in een genetisch algoritme meerdere reeksen oplossingen in de zoekruimte kunnen worden gebruikt.
• Traditionele algoritmen hebben meer informatie nodig om een ​​zoekopdracht uit te voeren, terwijl genetische algoritmen slechts één objectieve functie nodig hebben om de fitheid van een individu te berekenen.
• Traditionele algoritmen kunnen niet parallel werken, terwijl genetische algoritmen parallel kunnen werken (het berekenen van de geschiktheid van de individualiteiten is onafhankelijk).
• Een groot verschil in genetische algoritmen is dat erfelijke algoritmen niet rechtstreeks op zoekerresultaten werken, maar op hun representaties (of weergave), vaak aangeduid als chromosomen.
• Een van de grote verschillen tussen traditionele algoritmen en genetische algoritmen is dat het niet rechtstreeks op kandidaat-oplossingen inwerkt.
• Traditionele algoritmen kunnen uiteindelijk maar één resultaat opleveren, terwijl genetische algoritmen meerdere optimale resultaten uit verschillende generaties kunnen genereren.
• Het is niet waarschijnlijker dat het traditionele algoritme optimale resultaten zal genereren, terwijl genetische algoritmen geen garantie bieden voor optimale globale resultaten, maar er is ook een grote kans om het optimale resultaat voor een probleem te verkrijgen, aangezien het gebruik maakt van genetische operatoren zoals Crossover en Mutation.
• Traditionele algoritmen zijn deterministisch van aard, terwijl genetische algoritmen probabilistisch en stochastisch van aard zijn.