Algoritm genetic

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 20 ianuarie 2020; verificările necesită 17 modificări .

Un algoritm genetic este un  algoritm de căutare euristică utilizat pentru a rezolva probleme de optimizare și modelare prin selecția aleatorie, combinarea și variația parametrilor doriti folosind mecanisme similare selecției naturale din natură. Este un tip de calcul evolutiv care rezolvă probleme de optimizare folosind metode naturale de evoluție, cum ar fi moștenirea , mutația , selecția și crossing-over . O trăsătură distinctivă a algoritmului genetic este accentul pus pe utilizarea operatorului „încrucișare”, care efectuează operația de recombinare a soluțiilor candidate, al cărei rol este similar cu rolul încrucișării în fauna sălbatică.

Istorie

Prima lucrare de simulare a evoluției a fost realizată în 1954 de Nils Baricelli pe un computer instalat la Institutul de Studii Avansate de la Universitatea Princeton. [1] [2] Lucrarea sa, publicată în același an, a atras atenția publicului pe scară largă. Din 1957, [3] geneticianul australian Alex Fraser a publicat o serie de lucrări care simulează selecția artificială între organisme cu controale multiple pentru caracteristici măsurabile. Această revoluționare a permis ca simularea computerizată a proceselor evolutive și a metodelor descrise în cărțile lui Fraser și Barnell (1970) [4] și Crosby (1973) [5] să devină o activitate mai comună în rândul biologilor din anii 1960. Simulările lui Fraser au inclus toate elementele esențiale ale algoritmilor genetici moderni. Pe lângă aceasta, Hans-Joachim Bremermann a publicat o serie de lucrări în anii 1960 care au adoptat și abordarea utilizării unei populații de decizie supuse recombinării, mutațiilor și selecției în probleme de optimizare. Cercetările lui Bremermann au inclus și elemente ale algoritmilor genetici moderni. [6] Alți pionieri includ Richard Friedberg, George Friedman și Michael Conrad. Multe lucrări timpurii au fost republicate de David B. Vogel (1998). [7]

Deși Baricelli, în lucrarea sa din 1963, a simulat capacitatea unei mașini de a juca un joc simplu [8] , evoluția artificială a devenit o tehnică de optimizare acceptată după lucrările lui Ingo Rechenberg și Hans-Paul Schwefel în anii 1960 și începutul anilor 1970 ai secolului XX. secolul - grupul lui Rechenberg a fost capabil să rezolve probleme complexe de inginerie conform strategiilor de evoluție . [9] [10] [11] [12] O altă abordare a fost tehnica de programare evolutivă a lui Lawrence J. Vogel , care a fost propusă pentru a crea inteligență artificială. Programarea evolutivă a folosit inițial mașini de stare pentru a prezice circumstanțele, iar diversitatea și selecția pentru a optimiza logica predicției. Algoritmii genetici au devenit deosebit de populari datorită lucrării lui John Holland la începutul anilor '70 și cărții sale Adaptation in Natural and Artificial Systems (1975) [13] . Cercetările lui Vogel s-au bazat pe experimentele lui Holland cu automate celulare și pe scrierile sale (ale Olandei) scrise la Universitatea din Michigan . Holland a introdus o abordare formalizată pentru prezicerea calității generației următoare, cunoscută sub numele de Teorema Schemei . Cercetarea în algoritmi genetici a rămas în mare parte teoretică până la mijlocul anilor 1980, când Prima Conferință Internațională privind algoritmii genetici a avut loc în sfârșit la Pittsburgh, Pennsylvania (SUA) .

Odată cu creșterea interesului de cercetare, puterea de calcul a computerelor desktop a crescut, de asemenea, semnificativ, ceea ce a făcut posibilă utilizarea în practică a noii tehnologii informatice. La sfârșitul anilor 80, General Electric a început să vândă primul produs de algoritm genetic din lume. Au devenit un set de instrumente de calcul industriale. În 1989, o altă companie, Axcelis, Inc. a lansat Evolver  , primul produs comercial de algoritm genetic pentru computere desktop. Jurnalistul de tehnologie din New York Times John Markoff a scris [14] despre Evolver în 1990.

Descrierea algoritmului

Problema este formalizată în așa fel încât soluția sa poate fi codificată ca un vector (" genotip ") al genelor, unde fiecare genă poate fi un bit , un număr sau un alt obiect. În implementările clasice ale algoritmului genetic (GA), se presupune că genotipul are o lungime fixă. Cu toate acestea, există variații ale GA care sunt libere de această limitare.

În unele moduri, de obicei aleatorii, sunt create multe genotipuri ale populației inițiale. Ele sunt evaluate folosind o „ funcție de fitness ”, prin care o anumită valoare („fitness”) este asociată fiecărui genotip, care determină cât de bine rezolvă problema fenotipului descris de acesta.

Atunci când alegeți o „ funcție de fitness ” (sau o funcție de fitness în literatura engleză), este important să vă asigurați că „relieful” acesteia este „neted”.

Din setul de soluții rezultat („generații”), ținând cont de valoarea „aptității”, sunt selectate soluții (de obicei cei mai buni indivizi au o probabilitate mai mare de a fi aleși), cărora li se aplică „operatori genetici” (în majoritatea cazuri, „ încrucișare ” - încrucișare și „ mutație ” - mutație), rezultând soluții noi. Pentru ei, se calculează și valoarea de fitness și apoi se realizează selecția („selectarea”) celor mai bune soluții pentru generația următoare.

Acest set de acțiuni se repetă în mod iterativ, modelând astfel un „proces evolutiv” care durează mai multe cicluri de viață ( generații ) până la îndeplinirea criteriului de oprire al algoritmului. Acest criteriu ar putea fi:

Algoritmii genetici servesc în principal la căutarea soluțiilor în spații de căutare multidimensionale.

Astfel, se pot distinge următoarele etape ale algoritmului genetic:

  1. Setați funcția țintă (fitness) pentru indivizii din populație
  2. Creați populația inițială
  1. Reproducere (încrucișare)
  2. Mutaţie
  3. Calculați valoarea funcției obiective pentru toți indivizii
  4. Formarea unei noi generații (selecție)
  5. Dacă sunt îndeplinite condițiile de oprire, atunci (sfârșitul buclei), în caz contrar (începutul buclei).

Crearea populației inițiale

Înainte de primul pas, trebuie să creați aleatoriu o populație inițială; chiar dacă se dovedește a fi complet necompetitiv, este probabil ca algoritmul genetic să îl transfere rapid într-o populație viabilă. Astfel, în primul pas, nu se poate încerca în mod special să-i facă pe indivizi prea apți, este suficient ca aceștia să corespundă formatului indivizilor din populație, iar funcția de fitness poate fi calculată pe aceștia. Rezultatul primului pas este populația H, formată din N indivizi.

Selecție (selecție)

La etapa de selecție este necesar să se selecteze o anumită proporție din întreaga populație care va rămâne „în viață” în acest stadiu de evoluție. Există diferite moduri de a selecta. Probabilitatea de supraviețuire a unui individ h trebuie să depindă de valoarea funcției de fitness Fitness(h). Rata de supraviețuire în sine este de obicei un parametru al algoritmului genetic și este pur și simplu dat în avans. Ca urmare a selecției, din N indivizi din populația H trebuie să rămână sN indivizi care vor fi incluși în populația finală H'. Restul indivizilor mor.

Alegerea părinților

Reproducerea în algoritmi genetici necesită mai mulți părinți, de obicei doi, pentru a produce descendenți.

Există mai mulți operatori de selecție a părinților:

  1. Panmixia - ambii părinți sunt aleși la întâmplare, fiecare individ al populației are șanse egale de a fi ales
  2. Consangvinizare - primul părinte este ales la întâmplare, iar al doilea este ales cel mai asemănător cu primul părinte
  3. Outbreeding - primul părinte este ales la întâmplare, iar al doilea părinte este ales cel mai puțin asemănător cu primul părinte

Consangvinizarea și consangvinizarea vin sub două forme: fenotipică și genotipică. În cazul formei fenotipice, asemănarea se măsoară în funcție de valoarea funcției de fitness (cu cât valorile funcției obiective sunt mai apropiate, cu atât indivizii sunt mai asemănători), iar în cazul formei genotipice, asemănarea este măsurată. în funcție de reprezentarea genotipului (cu cât sunt mai puține diferențe între genotipurile indivizilor, cu atât indivizii sunt mai asemănători).

Reproducere (încrucișare)

Reproducerea în diferiți algoritmi este definită diferit - depinde, desigur, de reprezentarea datelor. Principala cerință pentru reproducere este ca urmașii sau urmașii să aibă posibilitatea de a moșteni trăsăturile ambilor părinți, „amestecându-le” într-un fel.

De ce sunt de obicei selectați indivizii pentru reproducere din întreaga populație H, și nu dintre elementele lui H' care au supraviețuit la prima etapă (deși cea din urmă opțiune are și dreptul de a exista)? Faptul este că principalul dezavantaj al multor algoritmi genetici este lipsa diversității la indivizi. Destul de repede, iese în evidență un singur genotip, care este un maxim local, iar apoi toate elementele populației își pierd selecția, iar întreaga populație este „înfundată” cu copii ale acestui individ. Există diferite moduri de a face față unui astfel de efect nedorit; una dintre ele este alegerea pentru reproducere nu a celor mai adaptați, ci în general a tuturor indivizilor. Totuși, această abordare ne obligă să stocăm toți indivizii preexistenți, ceea ce crește complexitatea de calcul a problemei. Prin urmare, metodele de selectare a indivizilor pentru încrucișare sunt adesea folosite în așa fel încât nu doar cei mai adaptați, ci și alți indivizi cu condiție fizică slabă să se „înmulțească”. Cu această abordare, rolul mutațiilor crește pentru diversitatea genotipului.

Mutații

Același lucru se aplică mutațiilor ca și reproducerii: există o anumită proporție de mutanți m, care este un parametru al algoritmului genetic, iar la etapa de mutație, trebuie să selectați mN indivizi și apoi să le modificați în conformitate cu operațiunile de mutație predefinite. .

Critica

Există mai multe motive pentru critici cu privire la utilizarea unui algoritm genetic în comparație cu alte metode de optimizare:

Există mulți sceptici cu privire la fezabilitatea utilizării algoritmilor genetici. De exemplu, Steven S. Skiena, profesor de inginerie informatică la Universitatea Stony Brook, un cunoscut cercetător de algoritmi, câștigător al IEEE Institute Award, scrie [17] :

Eu personal nu am întâlnit niciodată o singură problemă pentru care algoritmii genetici ar fi instrumentul cel mai potrivit. Mai mult, nu am întâlnit niciodată rezultate ale calculelor obținute prin algoritmi genetici care să-mi facă o impresie pozitivă.

Aplicații ale algoritmilor genetici

Algoritmii genetici sunt utilizați pentru a rezolva următoarele probleme:

  1. Optimizarea caracteristicilor
  2. Optimizarea interogărilor bazei de date
  3. Probleme diverse pe grafice ( problema vânzătorului ambulant , colorare, găsirea potrivirilor)
  4. Configurarea și antrenarea unei rețele neuronale artificiale
  5. Construiți sarcini
  6. Programare
  7. Strategii de joc
  8. Teoria aproximării
  9. viata artificiala
  10. Bioinformatica ( plierea proteinelor )
  11. Sinteza automatelor finite
  12. Reglarea controlerelor PID

Un exemplu de implementare C++ simplă

Caută în spațiu unidimensional, fără încrucișare.

#include <cstdlib> #include <ctime> #include <algoritm> #include <iostream> #include <număr> int main () { srand (( unsigned int ) time ( NULL )); const size_t N = 1000 ; int a [ N ] = { 0 }; pentru ( ; ; ) { //mutație în partea aleatorie a fiecărui element: pentru ( dimensiunea_t i = 0 ; i < N ; ++ i ) a [ i ] += (( rand () % 2 == 1 ) ? 1 : -1 ); //acum selectați cel mai bun, sortat în ordine crescătoare std :: sort ( a , a + N ); //și apoi cele mai bune vor fi în a doua jumătate a matricei. //copie cele mai bune în prima jumătate, unde au lăsat urmași, iar primii au murit: std :: copie ( a + N / 2 , a + N , a ); //acum uitați-vă la starea medie a populației. După cum puteți vedea, este din ce în ce mai bine. std :: cout << std :: acumulează ( a , a + N , 0 ) / N << std :: endl ; } }

Un exemplu de implementare simplă în Delphi

Caută în spațiu unidimensional cu probabilitate de supraviețuire, fără traversare. (testat pe Delphi XE)

program Program1 ; {$APPTYPE CONSOLE} {$R *.res} folosește System . generice . Implicite , Sistem . generice . Colecții , Sistem . Sysutils ; const N = 1000 ; Nh = N div 2 ; MaxPopulation = High ( Integer ) ; var A : matrice [ 1 .. N ] de Integer ; I , R , C , Puncte , Rata natalitatii : Integer ; Iptr : ^ Integer ; începe Randomize ; // Populație parțială pentru I := 1 la N do A [ I ] := Aleatoriu ( 2 ) ; repetare // Mutație pentru I := 1 la N do A [ I ] := A [ I ] + ( - Aleatoriu ( 2 ) sau 1 ) ; // Selecție, cele mai bune la sfârșitul TArray . Sort < Integer > ( A , TComparer < Integer >. Implicit ) ; // Preset Iptr := Adr ( A [ Nh + 1 ]) ; Puncte := 0 ; Rata natalitatii := 0 ; // Rezultate crossover pentru I := 1 to Nh do begin Inc ( Puncte , Iptr ^ ) ; // Succes încrucișat aleatoriu R := Aleatoriu ( 2 ) ; Inc ( Rata Nașterii , R ) ; A [ I ] := Iptr ^ * R ; Iptr ^ := 0 ; Inc ( Iptr , 1 ) ; sfârşitul ; // Subtotal Inc ( C ) ; până la ( Puncte / N >= 1 ) sau ( C >= MaxPopulation ) ; Writeln ( Format ( 'Populația %d (rata:%f) scor:%f' , [ C , BirthRate / Nh , Puncte / N ])) ; sfârşitul .

În cultură

  • În filmul din 1995 Virtuozity , creierul principalului răufăcător este crescut de un algoritm genetic care folosește amintirile și trăsăturile comportamentale ale criminalilor.

Note

  1. ↑ Barricelli, Nils AallEsempi numerici di procesi di evoluzione  (neopr.)  // Methodos. - 1954. - S. 45-68 .
  2. ↑ Barricelli, Nils AallProcese de evoluție simbiogenetică realizate prin metode artificiale  (engleză)  // Methodos : journal. - 1957. - P. 143-182 .
  3. ↑ Fraser, AlexSimularea sistemelor genetice prin calculatoare digitale automate. I. Introducere  (engleză)  // Aust. J Biol. sci. : jurnal. - 1957. - Vol. 10 . - P. 484-491 .
  4. ↑ Fraser, Alex; Donald Burnell. Modele computerizate în genetică  (neopr.) . - New York: McGraw-Hill Education , 1970. - ISBN 0-07-021904-4 .
  5. ↑ Crosby, Jack L. Computer Simulation in Genetics  (nedefinite) . - Londra: John Wiley & Sons , 1973. - ISBN 0-471-18880-8 .
  6. ↑ 27.02.96 - Hans Bremermann de la UC Berkeley, profesor emerit și pionier în biologie matematică, a murit la 69 de ani . Preluat la 17 mai 2012. Arhivat din original la 23 martie 2012.
  7. ↑ Fogel, David B. (editor). Evolutionary Computation: The Fossil Record  (engleză) . - New York: Institutul de Ingineri Electrici și Electronici , 1998. - ISBN 0-7803-3481-7 .
  8. ↑ Barricelli, Nils Aall. Testarea numerică a teoriilor evoluției. Partea a II-a. Teste preliminare de performanță, simbiogeneză și viață terestră  (engleză)  // Acta Biotheoretica : jurnal. - 1963. - Nr. 16 . - P. 99-126 .
  9. ↑ Rechenberg, Ingo. Evolutionsstrategy  (neopr.) . - Stuttgart: Holzmann-Froboog, 1973. - ISBN 3-7728-0373-3 .
  10. ↑ Schwefel, Hans-Paul. Numerische Optimierung von Computer-Modellen (teză de doctorat)  (germană) . — 1974.
  11. ↑ Schwefel, Hans-Paul. Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie: mit einer vergleichenden Einführung in die Hill-Climbing- und Zufallsstrategie  (germană) . — Basel; Stuttgart: Birkhauser, 1977. - ISBN 3-7643-0876-1 .
  12. ↑ Schwefel, Hans-Paul. Optimizarea numerică a modelelor computerizate (Traducerea din 1977 Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie  (engleză) . - Chichester; New York: Wiley, 1981. - ISBN 0-471-09988-0 .
  13. ↑ JH Holland. Adaptarea în sisteme naturale și artificiale. University of Michigan Press, Ann Arbor, 1975.
  14. ↑ Markoff, John . Care este cel mai bun răspuns? Este Survival of the Fittest , New York Times (29 august 1990). Arhivat din original pe 2 decembrie 2010. Preluat la 9 august 2009.
  15. ↑ Melanie Mitchell. O introducere în algoritmii genetici . - MIT Press, 1998. - S. 167. - 226 p. — ISBN 9780262631853 . Arhivat la 1 noiembrie 2018 la Wayback Machine
  16. ↑ Wolpert, DH, Macready, WG, 1995. No Free Lunch Theorems for Optimization. Institutul Santa Fe, SFI-TR-05-010, Santa Fe.
  17. ↑ Steven S. Skiena. Manualul de proiectare a algoritmului. a doua editie. Springer, 2008.

Cărți

  • Simon D. Algoritmi pentru optimizarea evolutivă. — M. : DMK Press, 2020. — 940 p. - ISBN 978-5-97060-812-8 .
  • Emelyanov VV, Kureichik VV, Kureichik VM Teoria și practica modelării evolutive. - M. : Fizmatlit, 2003. - 432 p. — ISBN 5-9221-0337-7 .
  • Kureichik V. M., Lebedev B. K., Lebedev O. K. Căutare adaptare: teorie și practică. - M. : Fizmatlit, 2006. - 272 p. — ISBN 5-9221-0749-6 .
  • Gladkov L. A., Kureichik V. V., Kureichik V. M. Algoritmi genetici: manual. - Ed. a II-a. - M. : Fizmatlit, 2006. - 320 p. - ISBN 5-9221-0510-8 .
  • Gladkov L.A., Kureichik V.V., Kureichik V.M. et al. Metode bioinspirate în optimizare: monografie. - M. : Fizmatlit, 2009. - 384 p. - ISBN 978-5-9221-1101-0 .
  • Rutkowska D., Pilinsky M., Rutkowski L. Neural networks, genetic algorithms and fuzzy systems = Sieci neuronowe, algorytmy genetyczne i systemy rozmyte. - Ed. a II-a. - M . : Hot line-Telecom, 2008. - 452 p. — ISBN 5-93517-103-1 .
  • Skobtsov Yu. A. Fundamentele calculului evolutiv. - Donețk: DonNTU, 2008. - 326 p. - ISBN 978-966-377-056-6 .

Link -uri

  Accesați articolul Wikidata  Dicționare și enciclopedii