Geneettinen algoritmi on adaptiivinen heuristinen hakualgoritmi, joka on saanut inspiraationsa Darwinin luonnon evoluutioteoriasta .' Sitä käytetään koneoppimisen optimointiongelmien ratkaisemiseen. Se on yksi tärkeimmistä algoritmeista, koska se auttaa ratkaisemaan monimutkaisia ​​ongelmia, joiden ratkaiseminen kestäisi kauan.

Geneettisiä algoritmeja käytetään laajalti erilaisissa reaalimaailman sovelluksissa, mm. Elektronisten piirien suunnittelu, koodinmurto, kuvankäsittely ja keinotekoinen luovuus.

Tässä aiheessa selitämme geneettisen algoritmin yksityiskohtaisesti, mukaan lukien geneettisessä algoritmissa käytetyt perusterminologiat, kuinka se toimii, geneettisen algoritmin edut ja rajoitukset jne.

java satunnainen matematiikka satunnainen

Mikä on geneettinen algoritmi?

Ennen kuin ymmärrät geneettisen algoritmin, ymmärrämme ensin perusterminologiat ymmärtääksemme paremmin tätä algoritmia:

Väestö:Populaatio on kaikkien mahdollisten tai todennäköisten ratkaisujen osajoukko, joka voi ratkaista annetun ongelman.Kromosomit:Kromosomi on yksi populaation ratkaisuista kyseiseen ongelmaan, ja geenikokoelma tuottaa kromosomin.Geeni:Kromosomi on jaettu eri geeniin tai se on kromosomin osa.Alleelit:Alleeli on arvo, joka annetaan geenille tietyssä kromosomissa.Kuntotoiminto:Kuntotoimintoa käytetään yksilön kuntotason määrittämiseen väestössä. Se tarkoittaa yksilön kykyä kilpailla muiden yksilöiden kanssa. Jokaisessa iteraatiossa yksilöitä arvioidaan heidän kuntonsa perusteella.Geneettiset operaattorit:Geneettisessä algoritmissa paras yksittäinen kumppani uusintaa jälkeläisiä paremmin kuin vanhemmat. Tässä geneettisillä toimijoilla on rooli seuraavan sukupolven geneettisen koostumuksen muuttamisessa.Valinta

Kun populaation jokaisen olennon sopivuus on laskettu, valitaan valintaprosessilla, mikä populaation yksilöllisistä saa lisääntyä ja tuottaa siemenen, josta tuleva sukupolvi muodostuu.

Valittavissa olevat tyylityypit

Rulettipyörän valinta Tapahtuman valinta Rank-maadoitettu valinta

Joten nyt voimme määritellä geneettisen algoritmin heuristiseksi hakualgoritmiksi optimointiongelmien ratkaisemiseksi. Se on evoluutioalgoritmien osajoukko, jota käytetään laskennassa. Geneettinen algoritmi käyttää geneettisiä ja luonnonvalinnan käsitteitä optimointiongelmien ratkaisemiseen.

Kuinka geneettinen algoritmi toimii?

Geneettinen algoritmi toimii evoluution sukupolvien syklissä tuottaakseen korkealaatuisia ratkaisuja. Nämä algoritmit käyttävät erilaisia ​​operaatioita, jotka joko parantavat tai korvaavat populaatiota paremman sovitusratkaisun aikaansaamiseksi.

Se sisältää periaatteessa viisi vaihetta monimutkaisten optimointiongelmien ratkaisemiseksi, jotka on esitetty alla:

Alustus Kuntotehtävä Valinta Jäljentäminen Irtisanominen

1. Alustus

Geneettisen algoritmin prosessi alkaa generoimalla yksilöiden joukko, jota kutsutaan populaatioksi. Tässä jokainen yksilö on ratkaisu annettuun ongelmaan. Yksilö sisältää joukon parametreja, joita kutsutaan geeneiksi, tai sille on tunnusomaista. Geenit yhdistetään merkkijonoksi ja muodostavat kromosomeja, mikä on ratkaisu ongelmaan. Yksi suosituimmista alustustekniikoista on satunnaisten binäärijonojen käyttö.

muuntaa merkkijonon päivämääräksi

2. Kuntotehtävä

Kuntotoimintoa käytetään määrittämään, kuinka hyvässä kunnossa henkilö on? Se tarkoittaa yksilön kykyä kilpailla muiden yksilöiden kanssa. Jokaisessa iteraatiossa yksilöitä arvioidaan heidän kuntonsa perusteella. Kuntotoiminto antaa jokaiselle kuntopisteen. Tämä pistemäärä määrittää edelleen todennäköisyyden tulla valituksi lisääntymistä varten. Mitä korkea kuntopisteet ovat, sitä suuremmat mahdollisuudet tulla valituksi lisääntymiselle.

3. Valinta

Valintavaiheessa valitaan yksilöt jälkeläisten lisääntymistä varten. Kaikki valitut yksilöt järjestetään sitten kahden pariksi lisääntymisen lisäämiseksi. Sitten nämä yksilöt siirtävät geeninsä seuraavalle sukupolvelle.

Käytettävissä on kolmenlaisia ​​valintamenetelmiä, jotka ovat:

• Rulettipyörän valinta
• Turnauksen valinta
• Sijoitusperusteinen valinta

4. Lisääntyminen

Valintaprosessin jälkeen lapsen luominen tapahtuu lisääntymisvaiheessa. Tässä vaiheessa geneettinen algoritmi käyttää kahta variaatiooperaattoria, joita sovelletaan emopopulaatioon. Kaksi lisääntymisvaiheeseen osallistuvaa toimijaa on lueteltu alla:

Crossover:Crossoverilla on merkittävin rooli geneettisen algoritmin lisääntymisvaiheessa. Tässä prosessissa geenien sisällä valitaan satunnaisesti risteytyspiste. Sitten crossover-operaattori vaihtaa kahden nykyisen sukupolven vanhemman geneettiset tiedot tuottaakseen uuden yksilön, joka edustaa jälkeläisiä.

Vanhempien geenejä vaihdetaan keskenään, kunnes risteytyskohta saavutetaan. Nämä vastasyntyneet jälkeläiset lisätään populaatioon. Tätä prosessia kutsutaan myös crossoveriksi. Saatavilla olevat crossover-tyypit:
• Yhden pisteen crossover
• Kahden pisteen crossover
• Livery crossover
• Perittyjen algoritmien ristikko
Mutaatio
Mutaatiooperaattori lisää satunnaisia ​​geenejä jälkeläisiin (uusi lapsi) populaation monimuotoisuuden ylläpitämiseksi. Se voidaan tehdä kääntämällä joitain bittejä kromosomeissa.
Mutaatio auttaa ratkaisemaan ennenaikaisen konvergenssiongelman ja lisää monipuolistumista. Alla oleva kuva näyttää mutaatioprosessin:
Saatavilla olevat mutaatiotyylityypit,

alimerkkijonoindeksi sql:ssä

Kääntöbitin mutaatio Gaussin mutaatio Vaihto/vaihtomutaatio

5. Irtisanominen

Lisääntymisvaiheen jälkeen lopettamisen perustana käytetään pysäytyskriteeriä. Algoritmi päättyy, kun kynnyskuntoratkaisu on saavutettu. Se tunnistaa lopullisen ratkaisun väestön parhaaksi ratkaisuksi.

Yksinkertaisen geneettisen algoritmin yleinen työnkulku

Geneettisen algoritmin edut

• Geneettisten algoritmien rinnakkaiset ominaisuudet ovat parhaat.
• Se auttaa optimoimaan erilaisia ​​​​ongelmia, kuten erilliset toiminnot, monitavoiteongelmat ja jatkuvat toiminnot.
• Se tarjoaa ratkaisun ongelmaan, joka paranee ajan myötä.
• Geneettinen algoritmi ei tarvitse johdannaista tietoa.

Geneettisten algoritmien rajoitukset

• Geneettiset algoritmit eivät ole tehokkaita algoritmeja yksinkertaisten ongelmien ratkaisemiseen.
• Se ei takaa ongelman lopullisen ratkaisun laatua.
• Toistuva kunto-arvojen laskeminen voi aiheuttaa laskennallisia haasteita.

Ero geneettisten algoritmien ja perinteisten algoritmien välillä

• Hakutila on joukko kaikkia mahdollisia ratkaisuja ongelmaan. Perinteisessä algoritmissa ylläpidetään vain yhtä ratkaisusarjaa, kun taas geneettisessä algoritmissa voidaan käyttää useita ratkaisujoukkoja hakuavaruudessa.
• Perinteiset algoritmit tarvitsevat enemmän tietoa voidakseen suorittaa haun, kun taas geneettiset algoritmit tarvitsevat vain yhden tavoitefunktion yksilön sopivuuden laskemiseksi.
• Perinteiset algoritmit eivät voi toimia rinnakkain, kun taas geneettiset algoritmit voivat toimia rinnakkain (yksilöllisyyksien sopivuuden laskeminen on riippumatonta).
• Eräs suuri ero geneettisissä algoritmeissa on se, että sen sijaan, että ne toimisivat suoraan hakutuloksilla, periytyvät algoritmit toimivat esityksillä (tai renderöinnillä), joita usein esiintyy kromosomeina.
• Yksi suurista eroista perinteisen algoritmin ja geneettisen algoritmin välillä on, että se ei toimi suoraan ehdokasratkaisuilla.
• Perinteiset algoritmit voivat tuottaa vain yhden tuloksen, kun taas geneettiset algoritmit voivat tuottaa useita optimaalisia tuloksia eri sukupolvilta.
• Perinteinen algoritmi ei tuota todennäköisemmin optimaalisia tuloksia, kun taas geneettiset algoritmit eivät takaa optimaalisia globaaleja tuloksia, mutta on myös suuri mahdollisuus saada optimaalinen tulos ongelmalle, koska se käyttää geneettisiä operaattoreita, kuten Crossover ja Mutation.
• Perinteiset algoritmit ovat luonteeltaan deterministisiä, kun taas geneettiset algoritmit ovat luonteeltaan probabilistisia ja stokastisia.