Modelare evolutivă

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 30 septembrie 2017; verificările necesită 8 modificări .

Calculul evolutiv folosește caracteristicile teoriei lui Darwin pentru a construi  sisteme inteligente (metode de contabilitate de grup, algoritmi genetici ). Face parte din domeniul mai larg al inteligenței artificiale  - inteligența computațională .

Modelarea evolutivă este deja un domeniu destul de stabilit în care este posibil să distingem:

  1. modele de apariție a sistemelor informaționale genetice moleculare;
  2. modelarea modelelor generale de evoluție ( Algoritmi evoluționari ). Acestea sunt sisteme care folosesc doar principii evolutive. Ele au fost utilizate cu succes pentru probleme de tip optimizare funcțională și pot fi ușor descrise în limbaj matematic. Acestea includ algoritmi evolutivi precum programarea evolutivă , algoritmii genetici , strategiile evolutive , programarea genetică ;
  3. modele evolutive. Acestea sunt sisteme care sunt mai realiste din punct de vedere biologic decât algoritmii evolutivi, dar nu s-au dovedit a fi utile în sens aplicat. Sunt mai mult ca sistemele biologice și mai puțin concentrate pe rezolvarea problemelor tehnice. Au un comportament complex și interesant și, se pare, vor avea în curând aplicații practice. Aceste sisteme includ așa-numita viață artificială .
  4. modelarea evolutivă aplicată.

Istorie

Utilizarea principiilor darwiniene pentru rezolvarea automată a problemelor a început în anii 1950. Până în 1960, trei interpretări diferite ale acestei idei au fost dezvoltate în trei locuri diferite. Programarea evolutivă a fost introdusă de Lawrence J. Vogel în SUA, în timp ce John Henry Holland a numit metoda sa algoritm genetic . În Germania, Ingo Rechenberg și Hans-Paul Schwefel au introdus abordarea strategiei evoluționiste . Aceste zone au fost dezvoltate separat de aproximativ 15 ani. De la începutul anilor 1990, ele au fost unificate ca „dialecte” ale unei singure tehnologii numite calcul evolutiv. În plus, la începutul anilor nouăzeci, a apărut un al patrulea flux - programarea genetică . Începând cu anii 1990, calculul evolutiv a devenit în mare măsură asociat cu ideea de inteligență roi , iar algoritmii inspirați din natură devin o parte din ce în ce mai semnificativă a acestei tendințe.

Astfel, termenii „programare evolutivă”, „strategii evolutive”, „algoritmi genetici” și „programare genetică” sunt considerați cazuri speciale ale termenului general de „calculatură evolutivă” sau „modelare evolutivă”.

Modelarea evoluției folosind ideile algoritmilor evoluționari și a vieții artificiale a început cu munca lui Niels Aall Barricelli în anii 1960 și a fost extinsă de Alex Fraser, care a publicat o serie de lucrări despre modelarea selecției artificiale . [1] Algoritmii evolutivi au devenit o tehnică de optimizare consacrată ca rezultat al lucrării lui Ingo Rechenberg în anii 1960 și începutul anilor 1970, care i-a folosit pentru a rezolva probleme complexe de inginerie. [2] Algoritmii genetici au devenit deosebit de populari datorită lucrării lui John Holland . [3] Odată cu creșterea interesului academic, creșterea dramatică a puterii computerelor a permis aplicații practice, inclusiv evoluția automată a programelor de calculator. [4] Algoritmii evolutivi sunt utilizați în prezent pentru a rezolva probleme multidimensionale mai eficient decât software-ul dezvoltat de om. [5]

Idee generală

Figura prezintă o diagramă a funcționării uneia dintre varietățile de calcule evolutive - un algoritm genetic (GA), dar poate fi folosit pentru a înțelege ideea generală a abordării.

Populația inițială este înțeleasă ca un anumit număr de obiecte obținute, de obicei aleatoriu. În GA, astfel de obiecte sunt vectori („genotipuri”) ai genelor, unde fiecare genă poate fi un bit, un număr sau un alt obiect. Strategia evolutivă (ES) operează cu vectori de numere reale. În programarea genetică (GP) și evolutivă (EP), rolul obiectelor este jucat de programe care din ce în ce mai bine (în funcție de o anumită funcție de fitness) rezolvă problema de calcul setată.

Mutații și încrucișări

O mutație este o modificare aleatorie a unui „genotip”. În GA și ES, operatorul de mutație poate fi implementat prin simpla adăugare a unei variabile aleatoare distribuite normal la fiecare componentă a vectorului. În GP și EP această operațiune depinde foarte mult de modul de codificare a programelor dezvoltate. De exemplu, cu codificarea arborelui (vezi figura), se poate face prin modificarea aleatorie a informațiilor dintr-un nod sau prin adăugarea sau ștergerea unui nod sau a unui subarboresc întreg.

Operatorul „încrucișare” produce o recombinare a soluțiilor candidate, al căror rol este similar cu rolul de încrucișare în natură. Reproducerea în calculele evolutive este de obicei sexuală - este nevoie de mai mulți părinți, de obicei doi, pentru a produce urmași. 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.

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 așa-numitei funcție de fitness Fitness(h). Această funcție ar trebui să fie setată în așa fel încât valoarea sa pentru un anumit genotip (vector genetic, rezultatele programului în curs de dezvoltare) să poată fi utilizată pentru a evalua gradul de succes al unui anumit genotip. 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.

Modele pentru apariția sistemelor de informații genetice moleculare

La începutul anilor 1970, câștigătorul Premiului Nobel M. Eigen a făcut o încercare impresionantă de a construi modele pentru apariția sistemelor de procesare a informațiilor genetice moleculare în biosfera timpurie a Pământului [6] . Cel mai faimos dintre ele este modelul „cvasispecie”, care descrie evoluția simplă a secvențelor de polinucleotide (informații). În urma lui Eigen în 1980, oamenii de știință de la Novosibirsk V. Ratner și V. Shamin au propus un model de „sizeri” [7] .

Modelul de cvasispecii are în vedere evoluția treptată a unei populații de secvențe de informații ( vectori ), ale căror componente capătă un număr mic de valori discrete. Aptitudinea „indivizilor” din modele este dată în funcție de vectori. În fiecare etapă, există o selecție de indivizi din populația următoarei generații cu probabilități proporționale cu fitness-ul lor, precum și mutații ale indivizilor - înlocuiri aleatorii echiprobabile ale componentelor vectorului.

Modelul de mărime în cel mai simplu caz ia în considerare un sistem de trei tipuri de macromolecule : un șablon polinucleotidic și enzime de translație și replicare codificate de acest șablon. O matrice de polinucleotide este ca un dispozitiv de memorie care stochează informații despre unitățile funcționale ale calibratorului - enzime. Enzima de translație asigură „producția” unei enzime arbitrare conform informațiilor înregistrate în matrice. Enzima de replicare asigură copierea șablonului polinucleotidic. Dimensiunile sunt suficiente pentru auto-reproducere . Prin includerea unor enzime suplimentare codificate de șablonul polinucleotidic în schema de calibrare, este posibil să se asigure calitorului cu orice proprietăți, de exemplu, capacitatea de a regla sinteza anumitor enzime și de a se adapta la schimbările din mediul extern. [opt]

Aplicație în probleme de optimizare funcțională

Calculul evolutiv (EC) este adesea folosit pentru a organiza căutarea stocastică, mai ales în cazul problemelor multimodale, când metodele de optimizare deterministă sau metodele stocastice mai simple nu permit studierea comportamentului funcției obiectiv în afara regiunilor optime locale. Metodele EV nu garantează găsirea optimului global în timp polinomial. Interesul practic pentru ele se datorează faptului că aceste metode, după cum arată practica, fac posibilă găsirea de soluții mai bune (sau „suficient de bune”) la problemele de căutare foarte dificile în mai puțin timp decât alte metode utilizate de obicei în aceste cazuri. O limitare tipică a utilizării lor este necesitatea (de a construi o soluție bună) de a calcula în mod repetat funcția obiectiv (cuvântul „în mod repetat” înseamnă de obicei numere de la sute la milioane). Cu toate acestea, metodele EV s-au dovedit a fi destul de eficiente pentru rezolvarea unui număr de probleme reale în proiectarea inginerească, planificare, rutare și plasare, managementul portofoliului, căutarea stărilor energetice optime ale structurilor chimice și moleculare, precum și în multe alte domenii care permit un set adecvat de reprezentări, operatori, volume și structuri ale populațiilor etc.

Modelarea evolutivă ca metodă de cercetare în informatică

Deoarece evoluția pare să fie baza mecanismului de procesare a informațiilor în sistemele naturale, cercetătorii se străduiesc să construiască modele teoretice și computerizate care să explice de fapt principiile acestui mecanism (vezi „ Informația naturală ”). Cercetările în acest domeniu se caracterizează prin înțelegerea faptului că modelele ar trebui să conțină nu numai nașterea și moartea populațiilor, ci și ceva între ele. Următoarele concepte sunt cel mai adesea implicate.

Inteligența roiului descrie comportamentul  colectiv al unui sistem de auto-organizare descentralizat. Considerată în teoria inteligenței artificiale ca metodă de optimizare. Termenul a fost introdus de Gerardo Beni și Wang Jing în 1989, în contextul sistemului robotizat celular [9] . Sistemele de inteligență Swarm, de regulă, constau dintr-un set de agenți ( sistem multi-agenți ) care interacționează local între ei și cu mediul. Agenții înșiși sunt de obicei destul de simpli, dar toți împreună, interacționând local, creează așa-numita inteligență roi. Un exemplu în natură este o colonie de furnici , un roi de albine , un stol de păsări, pești...

Inteligența colectivă  este un termen care a apărut în sociologie la mijlocul anilor 1980 când studia procesul de luare a deciziilor colective. Cercetătorii de la NJIT au definit inteligența colectivă ca fiind capacitatea unui grup de a găsi soluții la probleme care sunt mai bune decât cea mai bună soluție individuală din acel grup.

Direcția sociologică – întrucât societatea umană este un real, de altfel, bine observabil și documentat (spre deosebire de creierul uman), instrument de procesare a informațiilor, metaforele și reminiscențe sociologice au fost prezente în lucrările despre cibernetică și domenii conexe încă de la începuturile lor. Dacă inteligența roi este axată pe obținerea unui comportament complex într-un sistem din elemente simple, această abordare, dimpotrivă, explorează construcția obiectelor simple și speciale pe baza unora complexe și universale: „statul este mai prost decât majoritatea membrilor săi. ” [10] . Această direcție se caracterizează prin dorința de a da definiții conceptelor sociologice din domeniul informaticii. Deci în [11] elita este definită ca purtătoarea unui anumit model privat al lumii reale, iar baza (adică oamenii) joacă rolul unui arbitru între elite. Procesul evolutiv constă în generarea și moartea elitelor. Baza nu este capabilă să înțeleagă esența ideilor și modelelor prezentate de elite și nu își propune o astfel de sarcină. Totuși, tocmai din cauza neimplicarii sale, își păstrează capacitatea de evaluare emoțională clară, care îi permite să distingă cu ușurință elitele carismatice de cele în decadență care încearcă să-și mențină privilegiile, realizând că ideea sau modelul lor nu a fost confirmat.

Conferințe majore

Note

  1. ↑ Fraser AS Monte Carlo analize ale modelelor genetice   // Nature . - 1958. - Vol. 181 , nr. 4603 . - P. 208-209 . - doi : 10.1038/181208a0 . — PMID 13504138 .
  2. ↑ Rechenberg, Ingo. Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (teză de doctorat)  (germană) . Fromman-Holzboog, 1973.
  3. ↑ Holland, John H. Adaptation in Natural and Artificial Systems  . - University of Michigan Press , 1975. - ISBN 0-262-58111-6 .
  4. ↑ Koza, John R. Programare genetică  (nedefinită) . - MIT Press , 1992. - ISBN 0-262-11170-5 .
  5. ↑ Jamshidi M. Instrumente pentru control inteligent: controlere fuzzy, rețele neuronale și algoritmi genetici  (engleză)  // Tranzacții filozofice. Seria A, Științe matematice, fizice și inginerie : jurnal. - 2003. - Vol. 361 , nr. 1809 . - P. 1781-1808 . doi : 10.1098 / rsta.2003.1225 . — PMID 12952685 .
  6. ↑ Eigen M., Schuster P. Hypercycle. Principii de organizare a macromoleculelor / Per. din engleza. ed. M. V. Volkenstein și D. S. Chernavsky. — M.: Mir, 1982. — 270 p.
  7. ↑ Ratner V. A., Shamin V. Sizers: modeling of fundamental features of molecular biological organization. Corespondența proprietăților comune și a caracteristicilor de proiectare ale grupurilor de macromolecule // Zh. total biologie. - 1983. - T.44. Nu. 1. - c.51-61.
  8. ↑ Arutsev A. A., Ermolaev B. V., Kutateladze I. O., Slutsky M. S. Concepte ale științelor naturale moderne. Tutorial. - M., 2007.
  9. ↑ Beni, G., Wang, J. Swarm Intelligence in Cellular Robotic Systems, Proceed. Atelier avansat NATO despre roboți și sisteme biologice, Toscana, Italia, 26-30 iunie (1989)
  10. ↑ Wiener N. Cibernetică, sau Control și comunicare în animal și mașină. / Per. din engleza. I. V. Solovyov și G. N. Povarov; Ed. G. N. Povarova. — ediția a II-a. — M.: Nauka; Ediţia principală a publicaţiilor pentru ţări străine, 1983. - 344 p.
  11. ↑ Igor Weisband. 5000 de ani de informatică. M. - „Vverița neagră”, 2010
  12. ↑ Conferința Internațională privind Teoria și Aplicațiile Calculației Evolutive (link inaccesibil) . ECTA. Consultat la 29 aprilie 2013. Arhivat din original pe 10 mai 2013. 
  13. ↑ Grup de interes special pentru calcularea genetică și evolutivă (link nu este disponibil) . SIGEVO. Consultat la 29 aprilie 2013. Arhivat din original pe 15 iulie 2012. 
  14. ↑ Rezolvarea paralelă a problemelor din natură (link în jos) . Preluat la 6 martie 2012. Arhivat din original la 4 mai 2012. 

Literatură

  Accesați articolul Wikidata  Dicționare și enciclopedii
În cataloagele bibliografice