Overzicht van genetisch algoritme
Optimalisatietechnieken zijn de technieken die worden gebruikt om de beste oplossing te vinden uit alle mogelijke oplossingen die beschikbaar zijn onder de aanwezige beperkingen. Dus het Genetische algoritme is zo'n optimalisatie-algoritme dat is gebouwd op basis van het natuurlijke evolutieproces van onze natuur. Het idee van natuurlijke selectie en genetische erfelijkheid wordt hier gebruikt. Het maakt gebruik van begeleide willekeurige zoekopdrachten, in tegenstelling tot andere algoritmen, dwz het vinden van de optimale oplossing door te beginnen met een willekeurige initiële kostenfunctie en dan alleen te zoeken in de ruimte die de minste kosten had (in de geleide richting). Geschikt wanneer u met enorme en complexe datasets werkt.
Wat is een genetisch algoritme?
Het genetische algoritme is gebaseerd op de genetische structuur en het gedrag van het chromosoom van de bevolking. De volgende dingen zijn de basis van genetische algoritmen.
- Elk chromosoom geeft een mogelijke oplossing aan. De populatie is dus een verzameling chromosomen.
- Elk individu in de populatie wordt gekenmerkt door een fitnessfunctie. Een betere fitheid is de oplossing.
- Van de beschikbare individuen in de populatie worden de beste individuen gebruikt voor de reproductie van de volgende generatie nakomelingen.
- Het voortgebrachte nageslacht zal kenmerken hebben van beide ouders en is een gevolg van mutatie. Een mutatie is een kleine verandering in de genstructuur.
Fasen van genetisch algoritme
Hieronder staan de verschillende fasen van het genetische algoritme:
1. Initialisatie van de bevolking (codering)
- Elk gen vertegenwoordigt een parameter (variabelen) in de oplossing. Deze verzameling parameters die de oplossing vormen, is het chromosoom. De populatie is een verzameling chromosomen.
- Volgorde van genen op het chromosoom is van belang.
- Meestal worden chromosomen in binair getal weergegeven als nullen en enen, maar er zijn ook andere coderingen mogelijk.
2. Fitnessfunctie
- Uit de beschikbare chromosomen moeten we de beste selecteren voor de reproductie van nakomelingen, dus elk chromosoom krijgt een fitnesswaarde.
- De fitnessscore helpt bij het selecteren van de individuen die voor reproductie zullen worden gebruikt.
3. Selectie
- Het hoofddoel van deze fase is om de regio te vinden waar de kansen om de beste oplossing te krijgen groter zijn.
- Inspiratie hiervoor is van het overleven van de sterkste.
- Het moet een evenwicht zijn tussen exploratie en exploitatie van zoekruimte.
- GA probeert het genotype naar hogere fitness in de zoekruimte te verplaatsen.
- Een te sterke voorkeur voor fitnessselectie kan leiden tot suboptimale oplossingen.
- Te weinig selectie van fitnessbias resulteert in ongericht zoeken.
- Er wordt dus gebruik gemaakt van proportionele fitnessgeschiktheid, ook bekend als roulettewielkeuze, een genetische operator die wordt gebruikt in genetische algoritmen voor het selecteren van potentieel bruikbare oplossingen voor recombinatie.
4. Reproductie
Het genereren van nakomelingen gebeurt op 2 manieren:
- crossover
- Mutatie
a) Crossover
Crossover is de meest vitale fase in het genetische algoritme. Tijdens de crossover wordt een willekeurig punt geselecteerd tijdens het paren van een paar ouders om nakomelingen te genereren.
Er zijn 3 hoofdtypen crossover.
- Single Point Crossover: een punt op de chromosomen van beide ouders wordt willekeurig gekozen en aangeduid als een 'crossover-punt'. Bits rechts van dat punt worden uitgewisseld tussen de twee ouder-chromosomen.
- Tweepunts crossover: twee crossover-punten worden willekeurig gekozen uit de ouder-chromosomen. De bits tussen de twee punten worden verwisseld tussen de ouderorganismen.
- Uniforme crossover: in een uniforme crossover wordt doorgaans elke bit met gelijke waarschijnlijkheid gekozen uit een van beide ouders.
De nieuwe nakomelingen worden aan de populatie toegevoegd.
b) Mutatie
In een paar nieuwe nakomelingen gevormd, kunnen sommige van hun genen worden onderworpen aan een mutatie met een lage willekeurige waarschijnlijkheid. Dit geeft aan dat sommige bits in het bitchromosoom kunnen worden omgedraaid. Mutatie zorgt voor diversiteit onder de bevolking en stopt voortijdige convergentie.
5. Convergentie (wanneer te stoppen)
Er zijn maar weinig regels die bepalen wanneer te stoppen:
- Wanneer er geen verbetering is in de kwaliteit van de oplossing na het voltooien van een bepaald aantal vooraf ingestelde generaties.
- Wanneer een hard en snel bereik van generaties en tijd wordt bereikt.
- Tot een acceptabele oplossing wordt verkregen.
Toepassing van genetisch algoritme
In deze sectie zullen we enkele van de gebieden bespreken waarop het genetische algoritme vaak wordt toegepast.
1. Reis- en verzendrouting
Het probleem van de reizende verkoper is een van de belangrijkste toepassingen van het genetische algoritme. Wanneer een reisplanner bijvoorbeeld wordt gevraagd om een reis te plannen, zou hij de hulp gebruiken van een genetisch algoritme dat niet alleen helpt om de totale kosten van de reis te verlagen, maar ook om de tijd te verminderen.GE wordt ook gebruikt voor het plannen van de levering van producten van plaats tot plaats op de best efficiënte manier.
2. Robotica
Het genetische algoritme wordt veel gebruikt op het gebied van robotica. Robots verschillen van elkaar door het doel waarvoor ze zijn gebouwd. Er zijn bijvoorbeeld weinig gebouwd voor een kooktaak, weinig zijn gebouwd voor onderwijstaken, enz.
- Selectie van belangrijke functies in de gegeven gegevensset.
- Bij de traditionele methode worden de belangrijke functies in de gegevensset geselecteerd met behulp van de volgende methode. dat wil zeggen, u kijkt naar het belang van dat model en stelt vervolgens een drempelwaarde in voor de functies, en als de functie een belangrijkheidswaarde heeft die groter is dan een drempel, wordt deze in overweging genomen.
- Maar hier gebruiken we een methode die een knapzakprobleem wordt genoemd.
- We zullen opnieuw beginnen met de populatie van een chromosoom, waarbij elk chromosoom een binaire string zal zijn. 1 geeft de "opname" van de functie in het model aan en 0 geeft de "uitsluiting" van de functie in het model aan.
- De fitnessfunctie hier is onze nauwkeurigheidsmaatstaf voor de concurrentie. Hoe nauwkeuriger onze set chromosomen bij het voorspellen van de waarde, hoe geschikter deze zal zijn.
- Er zijn veel andere toepassingen van genetische algoritmen zoals DNA-analyse, planningsapplicaties, engineeringontwerp.
Conclusie
In het huidige scenario wordt GE gebruikt in grote productiebedrijven zoals vliegtuigen, enz. Om het gebruik van tijd en middelen te optimaliseren. Verdere wetenschappers werken aan nieuwe manieren om genetische algoritmen te combineren met andere optimalisatietechnieken.
Aanbevolen artikelen
Dit is een gids voor Wat is genetisch algoritme? Hier bespreken we de introductie, fasen en toepassingen van Genetic Algorithm. U kunt ook onze andere voorgestelde artikelen doornemen -
- Routeringsalgoritmen
- Soorten algoritmen
- Neurale netwerkalgoritmen
- Datamining-algoritmen
- gids voor C ++ algoritme voorbeelden