Geneettinen algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 20.1.2020 tarkistetusta versiosta . tarkastukset vaativat 17 muokkausta .

Geneettinen algoritmi on heuristinen  hakualgoritmi , jota käytetään optimointi- ja mallinnusongelmien ratkaisemiseen satunnaisella valinnalla, yhdistämällä ja muuntelemalla haluttuja parametreja luonnonvalinnan kaltaisia ​​mekanismeja käyttäen . Se on eräänlainen evoluutiolaskenta , joka ratkaisee optimointiongelmia käyttämällä luonnollisia evoluution menetelmiä, kuten periytymistä , mutaatiota , valintaa ja ylittämistä . Geneettisen algoritmin erottuva piirre on "risteytys"-operaattorin käytön korostaminen, joka suorittaa ehdokasratkaisujen rekombinaatiooperaation, jonka rooli on samanlainen kuin risteyksen rooli villieläimissä.

Historia

Ensimmäisen työn evoluution simuloimiseksi suoritti Nils Baricelli vuonna 1954 Princetonin yliopiston Institute for Advanced Study -instituuttiin asennetulla tietokoneella. [1] [2] Hänen samana vuonna julkaistu teoksensa herätti laajaa julkista huomiota. Vuodesta 1957 [3] australialainen geneetikko Alex Fraser on julkaissut julkaisuja, jotka simuloivat keinotekoista valintaa organismien joukosta, joilla on useita kontrolleja mitattavissa olevien ominaisuuksien saamiseksi. Tämä uraauurtava kehitys mahdollisti evoluutioprosessien tietokonesimuloinnin ja Fraserin ja Barnellin (1970) [4] ja Crosbyn (1973) [5] kirjoissa kuvattujen menetelmien yleistymisen biologien keskuudessa 1960-luvulta lähtien. Fraserin simulaatiot sisälsivät kaikki nykyaikaisten geneettisten algoritmien olennaiset elementit. Tämän lisäksi Hans-Joachim Bremermann julkaisi 1960-luvulla sarjan artikkeleita, joissa myös lähestyttiin rekombinaatioon, mutaatioon ja valintaan kohdistuvaa päätöspopulaatiota optimointiongelmissa. Bremermannin tutkimus sisälsi myös elementtejä nykyaikaisista geneettisistä algoritmeista. [6] Muita pioneereja ovat Richard Friedberg, George Friedman ja Michael Conrad. David B. Vogel (1998) on julkaissut uudelleen monia varhaisia ​​teoksia . [7]

Vaikka Baricelli vuoden 1963 artikkelissaan simuloi koneen kykyä pelata yksinkertaista peliä, [8] keinotekoisesta evoluutiosta tuli hyväksytty optimointitekniikka Ingo Rechenbergin ja Hans-Paul Schwefelin työn jälkeen 1960- luvulla ja 1970-luvun alussa 1900 -luvulla. vuosisadalla - Rechenbergin ryhmä pystyi ratkaisemaan monimutkaisia ​​teknisiä ongelmia evoluutiostrategioiden mukaisesti . [9] [10] [11] [12] Toinen lähestymistapa oli Lawrence J. Vogelin evoluutioohjelmointitekniikka , jota ehdotettiin tekoälyn luomiseksi. Evoluutioohjelmointi käytti alun perin tilakoneita ennustamaan olosuhteita ja monimuotoisuutta ja valintaa optimoimaan ennustuslogiikka. Geneettisistä algoritmeista tuli erityisen suosittuja John Hollandin 70-luvun alussa tekemän työn ja hänen kirjansa Adaptation in Natural and Artificial Systems (1975) [13] ansiosta . Vogelin tutkimus perustui Hollandin kokeisiin soluautomaateilla ja hänen (Hollannin) Michiganin yliopistossa kirjoitettuihin kirjoituksiinsa . Holland esitteli formalisoidun lähestymistavan seuraavan sukupolven laadun ennustamiseen, joka tunnetaan nimellä Scheme Theorem . Geneettisten algoritmien tutkimus pysyi suurelta osin teoreettisena 1980-luvun puoliväliin saakka, jolloin ensimmäinen kansainvälinen geneettisten algoritmien konferenssi pidettiin lopulta Pittsburghissa, Pennsylvaniassa (USA) .

Tutkimuskiinnostuksen kasvaessa myös pöytätietokoneiden laskentateho on kasvanut merkittävästi, mikä on mahdollistanut uuden tietotekniikan käytön käytännössä. 80-luvun lopulla General Electric aloitti maailman ensimmäisen geneettisen algoritmituotteen myynnin. Niistä tuli joukko teollisia laskentatyökaluja. Vuonna 1989 toinen yritys, Axcelis, Inc. julkaisi Evolverin  , maailman ensimmäisen kaupallisen geneettisen algoritmituotteen pöytätietokoneille. New York Timesin teknologiatoimittaja John Markoff kirjoitti [ 14 ] Evolverista vuonna 1990.

Algoritmin kuvaus

Ongelma on formalisoitu siten, että sen ratkaisu voidaan koodata geenien vektoriksi (" genotyyppi "), jossa jokainen geeni voi olla bitti , numero tai jokin muu objekti. Geneettisen algoritmin (GA) klassisissa toteutuksissa oletetaan, että genotyypillä on kiinteä pituus. GA:sta on kuitenkin muunnelmia, jotka eivät koske tätä rajoitusta.

Jollain, yleensä satunnaisella tavalla, luodaan monia alkuperäisen populaation genotyyppejä. Ne arvioidaan " kuntofunktiolla ", jolloin jokaiseen genotyyppiin liitetään tietty arvo ("fitness"), joka määrittää, kuinka hyvin sen kuvaama fenotyyppi ratkaisee ongelman.

Kun valitset ” kuntotoimintoa” (tai englanninkielisessä kirjallisuudessa fitness- toimintoa ), on tärkeää varmistaa, että sen ”kehotus” on ”tasainen”.

Tuloksena olevasta ratkaisujoukosta ("sukupolvet") valitaan "kuntoisuuden" arvon huomioon ottaen ratkaisut (yleensä parhaiden yksilöiden valituksi tulemisen todennäköisyys on suurempi), joihin sovelletaan "geneettisiä operaattoreita" (useimmissa tapauksissa). tapauksia, " crossover " - crossover ja " mutaatio " - mutaatio ), mikä johtaa uusiin ratkaisuihin. Heille lasketaan myös kunto-arvo, jonka jälkeen suoritetaan seuraavan sukupolven parhaiden ratkaisujen valinta ("valinta").

Tämä toimintosarja toistetaan iteratiivisesti, jolloin mallinnetaan "evoluutioprosessia", joka kestää useita elinkaareja ( sukupolvia ), kunnes algoritmin pysäytyskriteeri täyttyy. Tämä kriteeri voisi olla:

Geneettiset algoritmit palvelevat pääasiassa ratkaisujen etsimistä moniulotteisista hakuavaruksista.

Siten geneettisen algoritmin seuraavat vaiheet voidaan erottaa:

  1. Aseta tavoitetoiminto (kunto) väestön yksilöille
  2. Luo alkupopulaatio
  1. Jäljentäminen (risteytys)
  2. Mutaatio
  3. Laske tavoitefunktion arvo kaikille yksilöille
  4. Uuden sukupolven muodostuminen (valikoima)
  5. Jos pysäytysehdot täyttyvät, niin (silmukan loppu), muuten (silmukan alku).

Alkupopulaation luominen

Ennen ensimmäistä vaihetta sinun on luotava satunnaisesti alkupopulaatio; vaikka se osoittautuisi täysin kilpailukyvyttömäksi, on todennäköistä, että geneettinen algoritmi siirtää sen silti nopeasti elinkelpoiseen populaatioon. Ensimmäisessä vaiheessa ei siis voi erityisesti yrittää saada yksilöitä liian kuntoon, riittää, että ne vastaavat populaation yksilöiden muotoa ja niistä voidaan laskea kuntofunktio. Ensimmäisen vaiheen tulos on populaatio H, joka koostuu N yksilöstä.

Valinta (valinta)

Valintavaiheessa on tarpeen valita tietty osa koko väestöstä, joka pysyy "elossa" tässä kehitysvaiheessa. On olemassa erilaisia ​​tapoja valita. Yksilön h selviytymistodennäköisyyden tulee riippua kuntofunktion arvosta Fitness(h). Itse eloonjäämisprosentti s on yleensä geneettisen algoritmin parametri, ja se on yksinkertaisesti annettu etukäteen. Valinnan tuloksena populaation H N yksilöstä on jäätävä sN yksilöitä, jotka sisällytetään lopulliseen populaatioon H'. Loput yksilöt kuolevat.

Parents' Choice

Lisääntyminen geneettisillä algoritmeilla vaatii useita vanhempia, yleensä kaksi, tuottaakseen jälkeläisiä.

Vanhemman valintaoperaattoreita on useita:

  1. Panmixia - molemmat vanhemmat valitaan sattumanvaraisesti, jokaisella populaation yksilöllä on yhtäläiset mahdollisuudet tulla valituksi
  2. Sukusiitos - ensimmäinen vanhempi valitaan sattumanvaraisesti ja toinen vanhempi, joka muistuttaa eniten ensimmäistä vanhempaa
  3. Outsiitos - ensimmäinen vanhempi valitaan sattumanvaraisesti ja toinen vanhempi, joka on vähiten samanlainen kuin ensimmäinen vanhempi

Sisäsiitosta ja ulkosiitosta on kaksi muotoa: fenotyyppinen ja genotyyppinen. Fenotyyppisen muodon tapauksessa samankaltaisuus mitataan kuntofunktion arvosta riippuen (mitä lähempänä kohdefunktion arvot ovat, sitä samankaltaisempia yksilöt) ja genotyyppimuodossa samankaltaisuus mitataan. riippuen genotyypin edustuksesta (mitä vähemmän yksilöiden genotyyppien välillä on eroja, sitä samankaltaisempia yksilöt ovat).

Jäljentäminen (Crossing)

Toistaminen eri algoritmeissa määritellään eri tavalla - se tietysti riippuu datan esityksestä. Lisääntymisen päävaatimus on, että jälkeläisellä tai jälkeläisellä on mahdollisuus periä molempien vanhempien piirteet "sekoittaen" niitä jollain tavalla.

Miksi lisääntymiseen tarkoitettuja yksilöitä valitaan yleensä koko populaatiosta H, eikä ensimmäisessä vaiheessa säilyneistä H'-elementeistä (vaikka jälkimmäiselläkin vaihtoehdolla on oikeus olla olemassa)? Tosiasia on, että monien geneettisten algoritmien suurin haittapuoli on yksilöiden monimuotoisuuden puute. Melko nopeasti erottuu yksi genotyyppi, joka on paikallinen maksimi, ja sitten kaikki populaation elementit menettävät valinnan sille, ja koko populaatio "tukkoon" tämän yksilön kopioilla. On olemassa erilaisia ​​tapoja käsitellä tällaista ei-toivottua vaikutusta; yksi niistä on valinta lisääntymiseen ei mukautuneimpien, vaan yleensä kaikkien yksilöiden. Tämä lähestymistapa pakottaa meidät kuitenkin tallentamaan kaikki olemassa olevat yksilöt, mikä lisää ongelman laskennallista monimutkaisuutta. Siksi menetelmiä yksilöiden valitsemiseksi ylittämistä varten käytetään usein siten, että ei vain sopeutuneimmat, vaan myös muut huonokuntoiset yksilöt "lisääntyvät". Tällä lähestymistavalla mutaatioiden rooli kasvaa genotyypin monimuotoisuuden kannalta.

Mutaatiot

Sama koskee mutaatioita kuin lisääntymistä: mutantteja m on tietty määrä, joka on geneettisen algoritmin parametri, ja mutaatiovaiheessa sinun on valittava mN yksilöä ja vaihdettava ne ennalta määritettyjen mutaatiooperaatioiden mukaisesti. .

Kritiikki

On useita syitä kritisoida geneettisen algoritmin käyttöä muihin optimointimenetelmiin verrattuna:

Geneettisten algoritmien käyttökelpoisuudesta on monia skeptikkoja. Esimerkiksi Steven S. Skiena, Stony Brookin yliopiston tietokonetekniikan professori, tunnettu algoritmien tutkija, IEEE Institute Awardin voittaja, kirjoittaa [17] :

Itse en ole koskaan törmännyt yhteenkään ongelmaan, johon geneettiset algoritmit olisivat sopivin työkalu. Lisäksi en ole koskaan törmännyt geneettisten algoritmien avulla saatuihin laskelmiin, jotka tekisivät minuun positiivisen vaikutuksen.

Geneettisten algoritmien sovellukset

Geneettisiä algoritmeja käytetään ratkaisemaan seuraavat ongelmat:

  1. Ominaisuuden optimointi
  2. Tietokantakyselyn optimointi
  3. Erilaisia ​​​​ongelmia kaavioissa ( matkamyyjän ongelma , väritys, vastaavuuksien löytäminen)
  4. Keinotekoisen hermoverkon perustaminen ja koulutus
  5. Rakenna tehtäviä
  6. Ajoitus
  7. Pelistrategiat
  8. Approksimaatioteoria
  9. keinotekoinen elämä
  10. Bioinformatiikka ( proteiinien laskostaminen )
  11. Äärillisten automaattien synteesi
  12. PID-säätimien viritys

Esimerkki yksinkertaisesta C++- toteutuksesta

Hae yksiulotteisesta avaruudesta ilman risteyksiä.

#include <cstdlib> #include <ctime> #include <algoritmi> #include <iostream> #sisällytä <numero> int main () { srand (( unsigned int ) aika ( NULL )); const koko_t N = 1000 ; int a [ N ] = { 0 }; varten ( ;; ) _ { //mutaatio kunkin elementin satunnaiselle puolelle: for ( koko_t i = 0 ; i < N ; ++ i ) a [ i ] += (( rand () % 2 == 1 ) ? 1 : -1 ); //valitse nyt paras nousevassa järjestyksessä std :: lajittele ( a , a + N ); //ja sitten parhaat ovat taulukon toisella puoliskolla. //kopioi parhaat ensimmäiselle puoliskolle, johon he jättivät jälkeläisiä ja ensimmäiset kuolivat: std :: kopioi ( a + N / 2 , a + N , a ); //katso nyt väestön keskimääräinen tila. Kuten näet, se paranee ja paranee. std :: cout << std :: kerätä ( a , a + N , 0 ) / N << std :: endl ; } }

Esimerkki yksinkertaisesta toteutuksesta Delphissä

Etsi yksiulotteisesta avaruudesta selviytymistodennäköisyydellä ilman ylitystä. (testattu Delphi XE:llä)

ohjelma Ohjelma1 ; {$APPTYPE CONSOLE} {$R *.res} käyttää System . geneeriset lääkkeet . Oletukset , System . geneeriset lääkkeet . Kokoelmat , järjestelmä . Sysutils ; vakio N = 1000 ; Nh = N div2 ; _ MaxPopulation = Suuri ( kokonaisluku ) ; var A : kokonaisluvun taulukko [ 1..N ] ; _ _ _ I , R , C , Pisteet , Syntyvyys : Kokonaisluku ; Iptr : ^ Kokonaisluku ; aloita satunnainen ; // Osittainen populaatio I : = 1 - N do A [ I ] := Satunnainen ( 2 ) ; toista // Mutaatio I : = 1 - N do A [ I ] := A [ I ] + ( - Satunnainen ( 2 ) tai 1 ) ; // Valinta, parhaat TArrayn lopussa . Lajittele < Kokonaisluku > ( A , TComparer < Kokonaisluku >. Oletus ) ; // Esiasetettu Iptr := Addr ( A [ Nh + 1 ]) ; Pisteet := 0 ; Syntyvyys := 0 ; // Jatkotulokset kohteelle I := 1 to Nh do begin Inc ( Pisteet , Iptr ^ ) ; // Satunnainen crossover menestys R := Satunnainen ( 2 ) ; Inc ( Syntyvyyssuhde , Ranska ) ; A [ I ] := Iptr ^ * R ; Iptr ^ := 0 ; Inc ( Iptr , 1 ) ; loppu ; // Välisumma Inc ( C ) ; asti ( Pisteitä / N >= 1 ) tai ( C >= Suurin populaatio ) ; Writeln ( Muoto ( 'Väestö %d (nopeus:%f) pisteet:%f' , [ C , Syntyvyys / Nh , Pisteet / N ])) ; loppua .

Kulttuurissa

  • Vuoden 1995 elokuvassa Virtuosity pääpahiksen aivoja kasvatetaan geneettisellä algoritmilla käyttämällä rikollisten muistoja ja käyttäytymispiirteitä.

Muistiinpanot

  1. ↑ Barricelli, Nils AallEsempi numerici di processi di evoluzione  (neopr.)  // Methodos. - 1954. - S. 45-68 .
  2. ↑ Barricelli, Nils AallSymbiogeneettiset evoluutioprosessit toteutetaan keinotekoisilla menetelmillä  (englanniksi)  // Methodos : Journal. - 1957. - s. 143-182 .
  3. ↑ Fraser, AlexGeneettisten järjestelmien simulointi automaattisilla digitaalisilla tietokoneilla. I. Johdanto  (englanniksi)  // Aust. J Biol. sci. : päiväkirja. - 1957. - Voi. 10 . - s. 484-491 .
  4. ↑ Fraser, Alex; Donald Burnell. Tietokonemallit genetiikassa  (uuspr.) . - New York: McGraw-Hill Education , 1970. - ISBN 0-07-021904-4 .
  5. ↑ Crosby, Jack L. Tietokonesimulaatio genetiikassa  (määrittämätön) . - Lontoo: John Wiley & Sons , 1973. - ISBN 0-471-18880-8 .
  6. ↑ 02.27.96 - UC Berkeleyn Hans Bremermann, emeritusprofessori ja matemaattisen biologian pioneeri, on kuollut 69-vuotiaana . Haettu 17. toukokuuta 2012. Arkistoitu alkuperäisestä 23. maaliskuuta 2012.
  7. ↑ Fogel, David B. (toimittaja). Evolutionary Computation: The Fossil Record  (englanniksi) . - New York: Institute of Electrical and Electronics Engineers , 1998. - ISBN 0-7803-3481-7 .
  8. ↑ Barricelli, Nils Aall. Evoluutioteorioiden numeerinen testaus. Osa II. Suorituskyvyn, symbiogeneesin ja maanpäällisen elämän alustavat testit  (englanniksi)  // Acta Biotheoretica : päiväkirja. - 1963. - Ei. 16 . - s. 99-126 .
  9. ↑ Rechenberg, Ingo. Evoluutiostrategia  (uuspr.) . - Stuttgart: Holzmann-Froboog, 1973. - ISBN 3-7728-0373-3 .
  10. ↑ Schwefel, Hans-Paul. Numerische Optimierung von Computer-Modellen (PhD-tutkielma)  (saksa) . – 1974.
  11. ↑ Schwefel, Hans-Paul. Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie : mit einer vergleichenden Einführung in die Hill-Climbing- und Zufallsstrategie  (saksa) . - Basel; Stuttgart: Birkhauser, 1977. - ISBN 3-7643-0876-1 .
  12. ↑ Schwefel, Hans-Paul. Tietokonemallien numeerinen optimointi (Käännös julkaisusta 1977 Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie  (englanniksi) . - Chichester; New York: Wiley, 1981. - ISBN 0-471-09988-0) .
  13. ↑ JH Holland. Sopeutuminen luonnollisiin ja keinotekoisiin järjestelmiin. University of Michigan Press, Ann Arbor, 1975.
  14. ↑ Markoff, John . Mikä on paras vastaus? Se on Survival of the Fittest , New York Times (29. elokuuta 1990). Arkistoitu alkuperäisestä 2. joulukuuta 2010. Haettu 9. elokuuta 2009.
  15. ↑ Melanie Mitchell. Johdatus geneettisiin algoritmeihin . - MIT Press, 1998. - S. 167. - 226 s. — ISBN 9780262631853 . Arkistoitu 1. marraskuuta 2018 Wayback Machineen
  16. ↑ Wolpert, DH, Macready, WG, 1995. No Free Lunch Theorems for Optimization. Santa Fe Institute, SFI-TR-05-010, Santa Fe.
  17. ↑ Steven S. Skiena. Algoritmin suunnittelun käsikirja. toinen painos. Springer, 2008.

Kirjat

  • Simon D. Algoritmit evolutionaariseen optimointiin. — M. : DMK Press, 2020. — 940 s. - ISBN 978-5-97060-812-8 .
  • Emelyanov VV, Kureichik VV, Kureichik VM Evoluutiomallinnuksen teoria ja käytäntö. - M .: Fizmatlit, 2003. - 432 s. — ISBN 5-9221-0337-7 .
  • Kureichik V. M., Lebedev B. K., Lebedev O. K. Hakusopettelu : teoria ja käytäntö. - M .: Fizmatlit, 2006. - 272 s. — ISBN 5-9221-0749-6 .
  • Gladkov L. A., Kureichik V. V., Kureichik V. M. Geneettiset algoritmit: Oppikirja. - 2. painos - M .: Fizmatlit, 2006. - 320 s. - ISBN 5-9221-0510-8 .
  • Gladkov L.A., Kureichik V.V., Kureichik V.M. et ai. Bioinspired menetelmät optimoinnissa: monografia. - M. : Fizmatlit, 2009. - 384 s. - ISBN 978-5-9221-1101-0 .
  • Rutkowska D., Pilinsky M., Rutkowski L. Neuroverkot, geneettiset algoritmit ja sumeat järjestelmät = Sieci neuronowe, algorytmy genetyczne i systemy rozmyte. - 2. painos - M . : Hot line-Telecom, 2008. - 452 s. — ISBN 5-93517-103-1 .
  • Skobtsov Yu. A. Evolutionaarisen laskennan perusteet. - Donetsk: DonNTU, 2008. - 326 s. - ISBN 978-966-377-056-6 .

Linkit

  Siirry Wikidata-kohteeseen  Sanakirjat ja tietosanakirjat