Yleiskatsaus geneettiseen algoritmiin
Optimointitekniikat ovat tekniikoita, joita käytetään parhaan ratkaisun löytämiseen kaikista mahdollisista ratkaisuista, jotka ovat käytettävissä rajoissa. Joten geneettinen algoritmi on yksi sellainen optimointialgoritmi, joka on rakennettu luontamme luonnollisen evoluutioprosessin perusteella. Tässä käytetään ajatusta luonnollisesta valinnasta ja geneettisestä perinnöstä. Se käyttää ohjattua satunnaista hakua, toisin kuin muut algoritmit, ts. Etsimään optimaalinen ratkaisu aloittamalla satunnaisella alkuperäisellä kustannustoiminnolla ja etsimällä sitten vain tilassa, jolla oli vähiten kustannuksia (opastettuun suuntaan). Sopii, kun työskentelet valtavien ja monimutkaisten tietojoukkojen kanssa.
Mikä on geneettinen algoritmi?
Geneettinen algoritmi perustuu populaation kromosomin geneettiseen rakenteeseen ja käyttäytymiseen. Seuraavat asiat ovat geneettisten algoritmien perusta.
- Jokainen kromosomi osoittaa mahdollisen ratkaisun. Siksi populaatio on kokoelma kromosomeja.
- Jokaiselle väestön yksilölle on ominaista kunto-toiminta. Parempi kunto on parempi ratkaisu.
- Väestön käytettävissä olevista yksilöistä parhaita yksilöitä käytetään seuraavan sukupolven jälkeläisten lisääntymiseen.
- Tuotetulla jälkeläisellä on ominaisuuksia molemmilla vanhemmilla ja se on seurausta mutaatiosta. Mutaatio on pieni muutos geenirakenteessa.
Geneettisen algoritmin vaiheet
Alla on geneettisen algoritmin eri vaiheet:
1. Väestön alustus (koodaus)
- Jokainen geeni edustaa parametria (muuttujia) ratkaisussa. Tämä ratkaisun muodostava parametrikokoelma on kromosomi. Väestö on kokoelma kromosomeja.
- Geenien järjestys kromosomissa on tärkeä.
- Suurin osa ajasta kromosomeja on kuvattu binaareina 0: na ja 1: nä, mutta on myös muita koodauksia mahdollista.
2. Kunto-toiminto
- Käytettävissä olevista kromosomeista on valittava parhaat jälkeläisten lisääntymiselle, joten jokaiselle kromosomille annetaan kuntoarvo.
- Kuntotulos auttaa valitsemaan lisääntymiseen käytettäviä henkilöitä.
3. Valinta
- Tämän vaiheen päätavoite on löytää alue, jolla mahdollisuudet saada paras ratkaisu ovat enemmän.
- Inspiraatio tähän on heikoimman selviytymistä.
- Sen pitäisi olla tasapaino etsintätilan etsinnän ja hyödyntämisen välillä.
- GA yrittää siirtää genotyypin korkeampaan kuntoon etsintätilassa.
- Liian voimakas kuntovalinnan puolueellisuus voi johtaa optimaalisiin ratkaisuihin.
- Liian pieni kuntoharhojen valinta johtaa kohdistamattomaan hakuun.
- Näin ollen käytetään Fitness-suhteellista valintaa, joka tunnetaan myös nimellä rulettipyörän valinta, on geneettinen toimija, jota käytetään geneettisissä algoritmeissa potentiaalisesti hyödyllisten ratkaisujen valitsemiseksi rekombinaatiota varten.
4. Lisääntyminen
Jälkeläisiä syntyy kahdella tavalla:
- crossover
- Mutaatio
a) Crossover
Crossover on geneettisen algoritmin tärkein vaihe. Risteytyksen aikana satunnainen piste valitaan parittaessaan paria vanhempia jälkeläisten tuottamiseksi.
Crossover-tyyppejä on 3 päätyyppiä.
- Yhden pisteen ristinopeus: Piste molemman vanhemman kromosomeissa poimitaan satunnaisesti ja nimetään ”ristin pisteeksi”. Tuon pisteen oikealla puolella olevat bitit vaihdetaan kahden vanhemman kromosomin välillä.
- Kaksipisteinen risteys : Kaksi ristiinpistettä poimitaan satunnaisesti vanhemmista kromosomeista. Kahden pisteen väliset bitit vaihdetaan emo-organismien välillä.
- Yhdenmukainen ristiinvaihto: Yhdenmukaisessa risteyksessä jokainen bitti valitaan tyypillisesti jompikummasta vanhemmista yhtä todennäköisyydellä.
Uudet jälkeläiset lisätään väestöön.
b) Mutaatio
Muutamissa muodostuneissa uusissa jälkeläisissä joillekin heidän geeneistä voidaan suorittaa mutaatio pienellä satunnaisella todennäköisyydellä. Tämä osoittaa, että jotkut bittikromosomin biteistä voidaan kääntää. Mutaatio sattuu huolehtimaan väestön monimuotoisuudesta ja estämään ennenaikaisen lähentymisen.
5. Lähentyminen (milloin lopettaa)
Muutamia seuraavia sääntöjä, jotka kertovat, milloin lopettaa:
- Kun ratkaisun laatu ei parane, kun tietty määrä sukupolvia on asetettu eteenpäin.
- Kun saavutetaan kova ja nopea sukupolvien ja ajanjakso.
- Ennen kuin saadaan hyväksyttävä ratkaisu.
Geneettisen algoritmin soveltaminen
Tässä osassa käsittelemme joitain alueita, joilla geneettistä algoritmia käytetään usein.
1. Matkustaminen ja lähetysten reititys
Matkustava myyntimies-ongelma on yksi geneettisen algoritmin tärkeimmistä sovelluksista. Esimerkiksi, kun matkan suunnittelijaa pyydetään suunnittelemaan matka, hän käyttäisi geneettisen algoritmin apua, joka ei vain auta vähentämään matkan kokonaiskustannuksia, vaan myös vähentämään aikaa.GE: tä käytetään myös toimituksen suunnittelussa Tuotteita paikasta toiseen parhaalla mahdollisella tavalla.
2. Robotiikka
Geneettistä algoritmia käytetään laajalti robotiikan alalla. Robotit eroavat toisistaan sen mukaan, mihin ne on rakennettu. Esimerkiksi harvat rakennetaan ruoanlaitto-tehtäviä varten, harvat rakennetaan opetustehtäviin jne.
- Tärkeiden ominaisuuksien valinta annetussa tietoaineistossa.
- Perinteisessä menetelmässä tietojoukon tärkeät ominaisuudet valitaan seuraavalla menetelmällä. Toisin sanoen tarkastelet mallin merkitystä, asetat sitten kynnysarvon ominaisuuksille, ja jos ominaisuuden tärkeysarvo on enemmän kuin kynnysarvo, sitä pidetään.
- Mutta tässä käytämme menetelmää, jota kutsutaan repussa esiintyväksi ongelmaksi.
- Aloitamme jälleen kromosomipopulaatiolla, jossa jokainen kromosomi on binaarinen merkkijono. 1 tarkoittaa ominaisuuden "sisällyttämistä" malliin ja 0 tarkoittaa ominaisuuden "poissulkemista" mallissa.
- Tässä oleva kunto-toiminto on kilpailun tarkkuusmittari. Mitä tarkempi kromosomijoukkomme ennakoi arvoa, sitä sopivampi se on.
- Geneettisten algoritmien sovelluksia on monia muita, kuten DNA-analyysi, aikataulutussovellukset, tekniikan suunnittelu.
johtopäätös
Nykyisessä tilanteessa GE: tä käytetään suurissa valmistusyrityksissä, kuten lentokoneissa jne., Ajan ja resurssien käytön optimoimiseksi. Muut tutkijat pyrkivät löytämään uusia tapoja yhdistää geneettiset algoritmit muihin optimointitekniikoihin.
Suositellut artikkelit
Tämä on opas kohtaan Mikä on geneettinen algoritmi? Tässä keskustellaan geneettisen algoritmin johdannosta, vaiheista ja sovelluksista. Voit myös käydä läpi muiden ehdottamiemme artikkeleidemme -
- Reititysalgoritmit
- Algoritmien tyypit
- Neuraaliverkon algoritmit
- Tietojen louhinnan algoritmit
- opas C ++ -algoritmitesimerkkeihin