Algoritm genetic

Ce este

Evoluția naturală poate fi modelată ca un joc, în care recompensele pentru un organism care joacă un joc bun al vieții sunt transmiterea materialului său genetic către succesorii săi și supraviețuirea sa continuă.^[2] În evoluția naturală, cât de bine se comportă un individ depinde de cei cu care lucrează și cu care concurează, precum și de mediu. Algoritmii genetici reprezintă o simulare a selecției naturale asupra unei populații de soluții candidate la o problemă de optimizare (cromozomi, indivizi, creaturi sau fenotipuri).

Candidații sunt evaluați și încrucișați în încercarea de a găsi soluții bune. Astfel de soluții pot necesita mult timp și nu sunt evidente pentru un om. O fază de evoluție este inițiată cu o populație de ființe generate aleatoriu. În fiecare generație, se evaluează capacitatea fizică a fiecărui individ din populație. Unii sunt selectați aleatoriu din populația curentă (pe baza aptitudinii lor) și modificați (recombinați și, eventual, mutați aleatoriu) pentru a forma o nouă populație. Ciclul se repetă cu această nouă populație. Algoritmul se încheie fie după ce a trecut un număr stabilit de generații, fie după ce s-a atins un nivel bun de fitness pentru populație. În cazul în care algoritmul s-a încheiat ca urmare a atingerii unui număr maxim de generații, nu înseamnă neapărat că s-a obținut un nivel bun de fitness.

Programarea acestui lucru pe un computer

Pseudocodul este:

1. Inițializare: Sunt create câteva soluții posibile; foarte des acestea vor avea valori aleatorii.
2. Evaluare: O funcție de fitness evaluează fiecare soluție; scorul va fi un număr care indică cât de bine rezolvă soluția respectivă problema.
3. Etapele următoare se execută până când este îndeplinită cerința de oprire:
1. Selecție: Alege soluțiile/individualii pentru următoarea iterație.
2. Recombinare: Combină soluțiile culese
3. Mutație: Schimbarea aleatorie a soluțiilor nou create
4. Evaluare: Se aplică funcția de fitness, a se vedea pasul 2.
5. În cazul în care nu este îndeplinită cerința de oprire, reîncepeți cu etapa de selecție.

Exemplu

Descrierea de mai sus este abstractă. Un exemplu concret ajută.

Aplicații

În general

Algoritmii genetici sunt buni la rezolvarea problemelor care includ stabilirea orarului și programarea. Aceștia au fost, de asemenea, aplicați în inginerie. Aceștia sunt adesea utilizați pentru a rezolva probleme de optimizare globală.

Ca regulă generală, algoritmii genetici ar putea fi utili în domenii cu probleme care au un peisaj de fitness complex, deoarece amestecul este conceput pentru a îndepărta populația de optimi locali în care un algoritm tradițional de urcare pe dealuri ar putea rămâne blocat. Operatorii de încrucișare utilizați în mod obișnuit nu pot modifica nicio populație uniformă. Mutația singură poate asigura ergodicitatea procesului general al algoritmului genetic (văzut ca un lanț Markov).

Exemple de probleme rezolvate cu ajutorul algoritmilor genetici includ: oglinzi proiectate pentru a canaliza lumina soarelui către un colector solar, antene proiectate pentru a capta semnale radio în spațiu, metode de mers pe jos pentru figuri de calculator, proiectarea optimă a corpurilor aerodinamice în câmpuri de curgere complexe.

În Manualul său de proiectare a algoritmilor, Skiena ne sfătuiește să nu folosim algoritmi genetici pentru orice sarcină: "Este destul de nefiresc să modelăm aplicațiile în termeni de operatori genetici precum mutația și încrucișarea pe șiruri de biți. Pseudobiologia adaugă un alt nivel de complexitate între tine și problema ta. În al doilea rând, algoritmii genetici durează foarte mult timp în cazul problemelor non-triviale. [...] Analogia cu evoluția - unde progresul semnificativ necesită [sic] milioane de ani - poate fi foarte potrivită. [...] Nu am întâlnit niciodată o problemă în care algoritmii genetici să mi se pară calea potrivită pentru a o ataca. Mai mult, nu am văzut niciodată rezultate de calcul raportate cu ajutorul algoritmilor genetici care să mă fi impresionat favorabil. Rămâneți la recoacerea simulată pentru nevoile dumneavoastră de voodoo de căutare euristică."

Jocuri de masă

Jocurile de societate sunt o parte foarte relevantă a domeniului algoritmilor genetici aplicați la problemele din teoria jocurilor. O mare parte din primele lucrări privind inteligența computațională și jocurile au fost orientate către jocurile de societate clasice, cum ar fi tic-tac-toe,^[3] șah și dame.^[4] În prezent, în majoritatea cazurilor, jocurile de societate pot fi jucate de un calculator la un nivel mai ridicat decât cel al celor mai buni oameni, chiar și cu ajutorul tehnicilor de căutare exhaustivă oarbă. Go este o excepție notabilă de la această tendință și a rezistat până în prezent atacurilor mașinilor. Cei mai buni jucători de Go pe calculator joacă acum la nivelul unui bun începător.^[5][6] Se spune că strategia de Go se bazează în mare măsură pe recunoașterea modelelor, și nu doar pe analiza logică, ca în cazul șahului și al altor jocuri mai independente de piese. Factorul enorm de ramificare efectivă necesar pentru găsirea unor soluții de înaltă calitate restricționează foarte mult capacitatea de anticipare care poate fi utilizată în cadrul unei căutări de secvențe de mutări.

Jocuri pe calculator

Algoritmul genetic poate fi utilizat în jocurile pe calculator pentru a crea inteligență artificială (calculatorul joacă împotriva ta). Acest lucru permite o experiență de joc mai realistă; dacă un jucător uman poate găsi o secvență de pași care să ducă întotdeauna la succes chiar și atunci când se repetă în diferite jocuri, nu mai poate exista nicio provocare. În schimb, dacă o tehnică de învățare, cum ar fi un algoritm genetic pentru un strateg, poate evita repetarea greșelilor din trecut, jocul va fi mai ușor de jucat.

Algoritmii genetici au nevoie de următoarele părți:

• O metodă de reprezentare a provocării în termeni de soluție (de exemplu, dirijarea soldaților într-un atac într-un joc de strategie)
• O funcție de fitness sau de evaluare pentru a determina calitatea unei instanțe (de exemplu, măsurarea pagubelor provocate adversarului în cadrul unui astfel de atac).

Funcția de fitness acceptă o instanțiere modificată a unei entități și îi măsoară calitatea. Această funcție este adaptată la domeniul problemei. În multe cazuri, în special cele care implică optimizarea codului, funcția de fitness poate fi pur și simplu o funcție de sincronizare a sistemului. Odată ce sunt definite o reprezentare genetică și o funcție de fitness, un algoritm genetic va instanția candidații inițiali, așa cum s-a descris anterior, și apoi se va îmbunătăți prin aplicarea repetitivă a operatorilor de mutație, încrucișare, inversare și selecție (așa cum sunt definiți în funcție de domeniul problemei).

Limitări

Există limitări în utilizarea algoritmului genetic în comparație cu alți algoritmi de optimizare:

• Evaluarea repetată a funcției de fitness pentru probleme complexe este adesea cel mai limitativ segment al algoritmilor evolutivi artificiali. Găsirea soluției optime pentru probleme complexe necesită adesea evaluări foarte costisitoare ale funcției de fitness. În problemele din lumea reală, cum ar fi problemele de optimizare structurală, o singură evaluare a funcției poate necesita de la câteva ore până la câteva zile de simulare completă. Metodele tipice de optimizare nu pot face față unor astfel de tipuri de probleme. Este adesea necesar să se utilizeze aproximarea, deoarece calcularea soluției exacte durează prea mult timp. Algoritmii genetici combină uneori diferite modele de aproximare pentru a rezolva probleme complexe din viața reală.
• Algoritmii genetici nu se extind bine. Adică, atunci când numărul de elemente care sunt expuse la mutație este mare, există adesea o creștere exponențială a dimensiunii spațiului de căutare. Acest lucru face extrem de dificilă utilizarea acestei tehnici în probleme precum proiectarea unui motor, a unei case sau a unui avion. Pentru a utiliza algoritmii genetici cu astfel de probleme, acestea trebuie să fie împărțite în cea mai simplă reprezentare posibilă. Din acest motiv, vedem algoritmi evolutivi care codifică proiecte de palete de ventilator în loc de motoare, forme de clădiri în loc de planuri detaliate de construcție și profiluri aerodinamice în loc de proiecte de aeronave întregi. Cea de-a doua problemă de complexitate este legată de modul de protejare a părților care au evoluat pentru a reprezenta soluții bune împotriva mutațiilor distructive ulterioare, în special atunci când evaluarea aptitudinii lor necesită o bună combinație cu alte părți.
• Soluția "mai bună" este doar în comparație cu alte soluții. Ca urmare, criteriul de oprire nu este clar în fiecare problemă.
• În multe probleme, algoritmii genetici au tendința de a converge spre optimi locali sau chiar spre puncte arbitrare, mai degrabă decât spre optimul global al problemei. Acest lucru înseamnă că algoritmul nu "știe cum" să sacrifice capacitatea pe termen scurt pentru a obține capacitatea pe termen lung. Probabilitatea ca acest lucru să se întâmple depinde de forma funcției de fitness: anumite probleme facilitează găsirea optimului global, în timp ce în cazul altora poate fi mai ușor pentru funcție să găsească optimi locali. Această problemă poate fi atenuată prin utilizarea unei funcții de fitness diferite, prin creșterea ratei de mutație sau prin utilizarea unor tehnici de selecție care mențin o populație diversă de soluții. O tehnică obișnuită de menținere a diversității este utilizarea unei "penalizări de nișă": oricărui grup de indivizi cu o similitudine suficientă (raza de nișă) i se adaugă o penalizare, care va reduce reprezentarea grupului respectiv în generațiile următoare, permițând păstrarea în populație a altor indivizi (mai puțin similari). Acest truc, însă, poate să nu fie eficient, în funcție de peisajul problemei. O altă tehnică posibilă ar fi înlocuirea pur și simplu a unei părți a populației cu indivizi generați aleatoriu, atunci când majoritatea populației este prea asemănătoare între ele. Diversitatea este importantă în algoritmii genetici (și în programarea genetică), deoarece trecerea peste o populație omogenă nu produce soluții noi. În strategiile de evoluție și în programarea evolutivă, diversitatea nu este esențială, deoarece se bazează mai mult pe mutație.
• Operarea pe seturi de date dinamice este dificilă, deoarece genomurile încep să converge devreme spre soluții care pot să nu mai fie valabile pentru datele ulterioare. Au fost propuse mai multe metode pentru a remedia acest lucru prin creșterea diversității genetice și prin prevenirea convergenței timpurii, fie prin creșterea probabilității de mutație atunci când calitatea soluției scade (numită hipermutație declanșată), fie prin introducerea ocazională de elemente complet noi, generate aleatoriu în fondul genetic (numite imigranți aleatori). Din nou, strategiile de evoluție și programarea evolutivă pot fi puse în aplicare cu o așa-numită "strategie cu virgulă", în care părinții nu sunt menținuți, iar noii părinți sunt selectați numai din descendenți. Acest lucru poate fi mai eficient în cazul problemelor dinamice.
• Algoritmii genetici nu pot rezolva în mod eficient probleme în care singura măsură de fitness este o singură măsură corectă/nepotrivită (cum ar fi problemele de decizie), deoarece nu există nicio modalitate de convergență a soluției (nu există un deal de urcat). În aceste cazuri, o căutare aleatorie poate găsi o soluție la fel de repede ca un AG. Cu toate acestea, dacă situația permite repetarea încercării de succes/eșec care dă (posibil) rezultate diferite, atunci raportul dintre succese și eșecuri oferă o măsură adecvată a adecvării.
• Pentru anumite probleme de optimizare și cazuri de probleme specifice, alți algoritmi de optimizare pot fi mai eficienți decât algoritmii genetici în ceea ce privește viteza de convergență. Algoritmii alternativi și complementari includ strategiile de evoluție, programarea evolutivă, recoacerea simulată, adaptarea gaussiană, escaladarea dealurilor și inteligența roiului (de exemplu: optimizarea în colonii de furnici, optimizarea roiului de particule) și metodele bazate pe programarea liniară cu numere întregi. Caracterul adecvat al algoritmilor genetici depinde de gradul de cunoaștere a problemei; problemele bine cunoscute au adesea abordări mai bune și mai specializate.

Istoric

În 1950, Alan Turing a propus o "mașină de învățare" care să fie paralelă cu principiile evoluției. Simularea pe calculator a evoluției a început încă din 1954, odată cu lucrările lui Nils Aall Barricelli, care folosea calculatorul la Institutul pentru Studii Avansate din Princeton, New Jersey. Publicația sa din 1954 nu a fost remarcată pe scară largă. Începând cu 1957, geneticianul australian Alex Fraser, specialist în genetică cantitativă, a publicat o serie de lucrări privind simularea selecției artificiale a organismelor cu loci multipli care controlează o trăsătură măsurabilă. De la aceste începuturi, simularea computerizată a evoluției de către biologi a devenit mai frecventă la începutul anilor 1960, iar metodele au fost descrise în cărțile lui Fraser și Burnell (1970) și Crosby (1973). Simulările lui Fraser au inclus toate elementele esențiale ale algoritmilor genetici moderni. În plus, Hans-Joachim Bremermann a publicat în anii 1960 o serie de lucrări care adoptau, de asemenea, o populație de soluții la probleme de optimizare, supusă recombinării, mutației și selecției. Cercetările lui Bremermann au inclus, de asemenea, elementele algoritmilor genetici moderni. Alți pionieri timpurii demni de remarcat sunt Richard Friedberg, George Friedman și Michael Conrad. Multe dintre primele lucrări sunt reeditate de Fogel (1998).

Deși Barricelli, în lucrările pe care le-a prezentat în 1963, a simulat evoluția abilității de a juca un joc simplu, evoluția artificială a devenit o metodă de optimizare recunoscută pe scară largă ca urmare a activității lui Ingo Rechenberg și Hans-Paul Schwefel în anii 1960 și la începutul anilor 1970 - grupul lui Rechenberg a reușit să rezolve probleme complexe de inginerie prin strategii de evoluție. O altă abordare a fost tehnica de programare evolutivă a lui Lawrence J. Fogel, care a fost propusă pentru a genera inteligență artificială. Inițial, programarea evolutivă a folosit mașini cu stări finite pentru a prezice mediile și a utilizat variația și selecția pentru a optimiza logica predictivă. Algoritmii genetici, în special, au devenit populari datorită activității lui John Holland la începutul anilor 1970 și, în special, a cărții sale Adaptation in Natural and Artificial Systems (1975). Activitatea sa își are originea în studiile privind automatele celulare, efectuate de Holland și de studenții săi de la Universitatea din Michigan. Holland a introdus un cadru formalizat pentru prezicerea calității generației următoare, cunoscut sub numele de teorema schemei lui Holland. Cercetările în domeniul AG au rămas în mare parte teoretice până la mijlocul anilor 1980, când a avut loc la Pittsburgh, Pennsylvania, prima conferință internațională privind algoritmii genetici.