De algoritmi genetici fac parte din familia de algoritmi evolutivi . Scopul lor este de a obține o soluție aproximativă la o problemă de optimizare , atunci când nu există o metodă exactă (sau soluția este necunoscută) pentru a o rezolva într-un timp rezonabil. Algoritmii genetici iau noțiunea de selecție naturală și o aplică unei populații de soluții potențiale la problema dată. Soluția este abordată prin „salturi” succesive, ca într-o procedură de separare și evaluare ( ramură și legătură ) , cu excepția faptului că formulele sunt căutate și nu mai sunt valori direct.
Utilizarea algoritmilor genetici în rezolvarea problemelor este inițial rezultatul cercetărilor efectuate de John Holland și colegii săi și studenții de la Universitatea din Michigan care, încă din 1960 , au lucrat la acest subiect. Noutatea introdusă de acest grup de cercetători a fost includerea operatorului de crossover ( crossover ) pe lângă mutații . Și acest operator este cel mai adesea care face posibilă abordarea optimă a unei funcții prin combinarea genelor conținute de diferiții indivizi ai populației. Primul rezultat al acestei cercetări a fost publicarea în 1975 a Adaptării în sistem natural și artificial .
Popularizarea algoritmilor genetici va fi opera lui David Goldberg prin cartea sa Genetic Algorithms in Search, Optimization, and Machine Learning (1989). Această carte este încă în curs de editare astăzi. În Europa, prima conferință pe acest tip de subiect a fost Conferința europeană despre viața artificială din 1991 (a sărbătorit 20 de ani în 2011), co-organizată de Francisco Varela și Paul Bourgine . Una dintre primele lucrări care prezintă algoritmi genetici în limba franceză va fi cartea Inteligență artificială și calcul teoretic, care îi va dedica un capitol în 1993. Prima conferință francofonă cu lucrări pe această temă va fi organizată în 1994 de Jean- Marc Alliot ( IRIT ), Evelyne Lutton ( INRIA ), Marc Schoenauer ( INRIA ) și Edmund Ronald.
Algoritmii genetici bazându-se pe fenomene biologice, este recomandabil să ne amintim în prealabil câțiva termeni de genetică .
Organismele vii sunt formate din celule, ale căror nuclee conțin cromozomi care sunt șiruri de ADN . Elementul de bază al acestor lanțuri este o nucleotidă , identificată prin baza sa azotată (A, T, C sau G). Pe fiecare dintre acești cromozomi, o secvență de nucleotide constituie un lanț care codifică funcționalitățile organismului (culoarea ochilor, de exemplu). Deci, o genă este o frază funcțională de-a lungul lanțului. Poziția unei gene pe cromozom este locusul acesteia . Setul de gene al unui individ este genotipul său, iar setul de patrimoniu genetic al unei specii este genomul . Diferitele versiuni ale aceleiași gene se numesc alele .
De asemenea, folosim, în algoritmi genetici, o analogie cu teoria evoluției, care propune că, în timp, genele conservate într-o anumită populație sunt cele care sunt cele mai adaptate nevoilor speciei față de mediul său. Într-adevăr, anumite variații ale genelor oferă indivizilor care le posedă un avantaj competitiv față de restul populației. Acest avantaj competitiv se traduce apoi printr-o mai bună reproducere a acestor indivizi, ceea ce face posibilă transmiterea alelelor către întreaga populație după mai multe generații.
Instrumente bio-inspirate (din biologie)Genetica a demonstrat existența unor procese importante în cadrul unui grup de organisme din aceeași specie (sau specii strâns înrudite în bacterii) dând naștere amestecului genetic . Aceste procese au loc în timpul fazei de reproducere , când cromozomii a două organisme fuzionează pentru a crea un organism nou.
Aceste operații sunt „ imitate ” de algoritmi genetici pentru a evolua progresiv populațiile de soluții.
Selecţie Pentru a determina ce indivizi sunt mai înclinați să obțină cele mai bune rezultate, se face o selecție. Acest proces este analog cu un proces de selecție naturală , cei mai adaptați indivizi câștigând competiția de reproducere în timp ce cei mai puțin adaptați mor înainte de reproducere, ceea ce îmbunătățește adaptarea generală. Întrucât selecția este rezultatul intervenției umane sau, cel puțin, a aplicării unui criteriu definit de oameni, algoritmii genetici ar trebui, prin urmare, să fie mai degrabă mai apropiați de selecția artificială , practicată de fermieri, cea a selecției naturale , care funcționează „orb”. Trecerea , încrucișarea sau recombinarea În timpul acestei operații, doi cromozomi schimbă părți ale lanțurilor lor, pentru a da noi cromozomi. Aceste întinderi pot fi simple sau multiple. În primul caz, cei doi cromozomi traversează și schimbă porțiuni de ADN într-un singur punct. În al doilea caz, există mai multe puncte de trecere. Pentru algoritmii genetici, această operație (cel mai adesea în forma sa simplă) este preponderentă. Probabilitatea sa de apariție în timpul unei încrucișări între doi cromozomi este un parametru al algoritmului genetic și depinde de problemă și de tehnica de recombinare. Mutații În mod aleatoriu, o genă poate fi înlocuită cu un alt cromozom. În același mod ca și pentru straddling, definim aici o rată de mutație în timpul modificărilor populației care este în general între 0,001 și 0,01. Este necesar să alegeți o valoare relativ scăzută pentru această rată, pentru a nu cădea într-o căutare aleatorie și pentru a păstra principiul selecției și evoluției. Mutația servește pentru a evita convergența prematură a algoritmului. De exemplu, în timpul unei căutări extreme , mutația este utilizată pentru a evita convergența către un extremum local .Algoritmii genetici, pentru a permite rezolvarea problemelor, se bazează pe diferitele principii descrise mai sus. Problema teoretică a convergenței a fost rezolvată de Raphaël Cerf , bazat pe teoria Friedlin (en) și Wentzell (en) a perturbațiilor stochastice ale sistemelor dinamice. Dovada lui Cerf arată în plus că procesul de convergență depinde în esență de mutație, traversarea putând fi eliminată în teorie. Cu toate acestea, dovada teoretică a convergenței este puțin utilă în practică, în care operatorul de trecere este foarte des bogăția algoritmului genetic în comparație cu metodele de tip simulat de recoacere .
În general, începem cu o populație de bază care constă cel mai adesea în șiruri de caractere care corespund fiecare unui cromozom. Vom reveni mai târziu la diferitele structuri de date posibile (vezi Codificare ), dar pentru moment vom păstra utilizarea codării binare (de exemplu: 0100110).
Conținutul acestei populații inițiale este generat aleatoriu. Fiecărei soluții i se atribuie un scor care corespunde adaptării sale la problemă. Apoi, se face o selecție în cadrul acestei populații.
Există mai multe tehnici de selecție. Iată principalele utilizate:
Selecție după rang Această tehnică de selecție alege întotdeauna indivizii cu cele mai bune scoruri de adaptare, deci șansa nu intră în acest mod de selecție. De fapt, dacă n indivizi constituie populația, selecția aplicată constă în păstrarea celor mai buni k indivizi (în sensul funcției de evaluare) în funcție de o probabilitate care depinde de rang (și nu de funcția de evaluare). Probabilitatea de selecție proporțională cu adaptarea Numită și „ruletă” sau „roată a averii”, pentru fiecare individ, probabilitatea de a fi selectat este proporțională cu adaptarea lor la problemă. Pentru a selecta o persoană, se utilizează principiul roții părtinitoare a averii. Această roată este o roată clasică a averii pe care fiecare individ este reprezentat de o porțiune proporțională cu adaptarea sa. Pe această roată se efectuează apoi o loterie omogenă. Selecție după turneu Această tehnică utilizează selecția proporțională pe perechi de indivizi, apoi alege dintre aceste perechi individul care are cel mai bun scor de adaptare. Selecție uniformă Selecția se face aleatoriu, uniform și fără intervenția valorii potrivite. Fiecare individ are deci o probabilitate de 1 / P de a fi selectat, unde P este numărul total de indivizi din populație.Când au fost selectați doi cromozomi, se face o cruce . Mutațiile sunt apoi efectuate pe o mică proporție de indivizi, aleși la întâmplare. Acest proces ne oferă o nouă populație. Procesul se repetă de mai multe ori, astfel încât să imite principiul evoluției, care capătă sens doar pe un număr mare de generații. Procesul poate fi oprit după un număr arbitrar de generații sau când o soluție are un scor suficient de satisfăcător.
Luați în considerare, de exemplu, următoarele două persoane dintr-o populație în care fiecare individ corespunde unui șir de 8 biți: A = 00110010 și B = 01010100 . Reglăm probabilitatea de încrucișare la 0,7 ( 8 × 0,7 = 5,6, deci vom traversa 6 biți pe cei 8 biți ai celor două cuvinte).
Cromozom | Conţinut |
LA | 00: 110010 |
B | 01: 010100 |
LA' | 00 010 100 |
B ′ | 01 110010 |
Să presupunem aici că traversarea are loc, se alege apoi aleatoriu locul acestei traversări (toate locurile având aceeași probabilitate de a fi alese). Presupunând că trecerea are loc după a doua alelă, obținem A ′ și B ′ („:” marcând trecerea pe A și B). Apoi, fiecare dintre genele fiilor (aici, fiecare dintre biții șirurilor) este supusă mutației. În același mod ca și pentru combinații, definim o rată de mutație (foarte scăzută, de ordinul 0,001 - aici ne putem aștepta ca A ′ și B ′ să rămână aceleași).
Prin efectuarea acestor operațiuni (selectarea a doi indivizi, încrucișare, mutație), de câte ori corespunde dimensiunii populației împărțite la două, ajungem apoi la o nouă populație (prima generație) având aceeași dimensiune ca populația. inițială și care conține la nivel global soluții mai apropiate de optim. Principiul algoritmilor genetici este acela de a efectua aceste operații de maximum ori pentru a crește precizia rezultatului.
Există mai multe tehnici care fac posibilă optimizarea acestor algoritmi, de exemplu, există tehnici în care câțiva indivizi care nu provin din descendenții generației anterioare, dar generați aleatoriu, sunt introduși în fiecare generație. Astfel, putem spera să evităm convergența către un optim local.
Pentru algoritmii genetici, unul dintre cei mai importanți factori, dacă nu cel mai important, este modul în care soluțiile sunt codificate (ceea ce am numit aici cromozomi), adică structurile de date care vor codifica genele.
Codare binarăAcest tip de codificare este cu siguranță cel mai utilizat, deoarece are mai multe avantaje. Principiul său este de a codifica soluția în conformitate cu un șir de biți (care pot lua valorile 0 sau 1). Motivele pentru care acest tip de codificare este cel mai utilizat sunt în primul rând istorice. Într-adevăr, în timpul lucrărilor timpurii ale Olandei, teoriile au fost dezvoltate pe baza acestui tip de codificare. Și, deși majoritatea acestor teorii pot fi extinse la alte date decât șirurile de biți, ele nu au fost studiate la fel de mult în aceste contexte. Cu toate acestea, avantajul acestui tip de codificare față de concurenții săi tinde să fie pus la îndoială de cercetătorii actuali care cred că demonstrațiile Olandei despre presupusele avantaje ale acestei codificări nu sunt revelatoare.
Demonstrația Olandei (în 1975) pentru a demonstra superioritatea acestui tip de codare este următoarea. El a comparat două tipuri de codare pentru aceeași problemă. Primul a fost compus din câteva tipuri de alele, dar cu cromozomi de o lungime semnificativă (lanțuri de 100 de biți, de exemplu), celălalt a fost compus din lanțuri mai scurte, dar conținând mai multe alele (știind că tot ceea ce va codifica în continuare, pentru același cromozom, va rezulta într-un lanț mai scurt). El a dovedit că codarea biților era mai eficientă într-un mod destul de simplu. Într-adevăr, lanțurile de 100 de biți permit să aibă mai multe posibilități de întindere. Între doi cromozomi de primul tip, traversarea poate avea loc în 100 de locuri diferite față de 30 pentru cei de al doilea tip. Amestecul genetic pe care se bazează eficiența algoritmilor genetici va fi, prin urmare, mai important în primul caz.
Cu toate acestea, există cel puțin o parte negativă a acestui tip de codificare care determină existența altora. Într-adevăr, această codare este adesea nefirească în ceea ce privește o problemă dată (evoluția greutăților arcurilor într-un grafic, de exemplu, este dificil de codificat sub forma unui șir de biți).
Codificare de caractere multipleUn alt mod de codificare a cromozomilor într-un algoritm genetic este deci codificarea utilizând mai multe caractere (spre deosebire de biți). Adesea, acest tip de codificare este mai natural decât cel menționat mai sus. Mai mult decât atât, acesta este utilizat în multe cazuri avansate de algoritmi genetici pe care îl vom prezenta ulterior.
Codificare sub formă de copacAceastă codificare folosește o structură de copac cu o rădăcină din care pot proveni unul sau mai mulți copii. Unul dintre avantajele lor este că pot fi utilizate în cazul problemelor în care soluțiile nu au o dimensiune finită. În principiu, arborii de orice dimensiune pot fi formați prin trecere și mutare.
Problema cu acest tip de codificare este că arborii rezultați sunt adesea dificil de analizat și că putem ajunge la arbori „de soluție” a căror dimensiune va fi mare în timp ce există soluții mai simple și mai structurate alături de care se va trece algoritmul. În plus, performanța acestui tip de codificare în comparație cu codarea șirului nu a fost încă comparată sau foarte puțin. Într-adevăr, acest tip de experiment abia a început și informațiile sunt prea slabe pentru a fi comentate.
În cele din urmă, alegerea tipului de codificare nu poate fi făcută cu certitudine în starea actuală a cunoașterii. Potrivit cercetătorilor din acest domeniu, metoda actuală de aplicat în alegerea codării este de a alege cea care pare cea mai naturală în funcție de problema de tratat și apoi de a dezvolta algoritmul de tratament.
Așa cum s-a spus mai sus, algoritmii genetici pot fi o soluție bună pentru rezolvarea unei probleme. Cu toate acestea, utilizarea lor trebuie să fie condiționată de anumite caracteristici ale problemei.
Caracteristicile de luat în considerare sunt următoarele:
Prin natura lor, algoritmii genetici pot fi folosiți în scopuri pur recreative și răspund la problemele din jocurile care se joacă singure. Într-adevăr, o muncă de învățare datorită unui sistem de scor este mai mult decât adecvată lumii jocului, deoarece scorul este un element central al oricărui joc pentru a putea clasifica jucătorii între ei. Deoarece funcția de evaluare este deja calculată prin intermediul jocului, este cu atât mai ușor să dezvolți algoritmi genetici.
Putem nota, de asemenea, câteva exemple interesante de aplicare la titluri de jocuri video cult:
Problema vânzătorului călător : această problemă este un clasic algoritmic. Subiectul său se referă la călătoriile unui vânzător călător. Acest lucru trebuie să se oprească în mai multe puncte, iar scopul algoritmului este de a optimiza calea astfel încât să fie cât mai scurtă posibil. Dacă există opt puncte de oprire, acest lucru este încă posibil prin enumerare (2520 posibilități: pentru n opriri, n mai mare sau egal cu 3, există( n - 1)!2 posibile căi), dar apoi creșterea numărului de opriri determină creșterea exponențială a numărului de posibilități.
Prin intermediul algoritmilor genetici, este posibil să găsim căi relativ corecte. Mai mult, acest tip de problemă este destul de ușor de codat sub forma unui algoritm genetic. Ideea de bază este de a lua lungimea căii ca funcție de evaluare. Pentru a traversa două căi:
cale | Codificare |
LA | 1 2 3 4 : 5 6 7 8 9 |
B | 4 1 6 3 : 9 8 2 5 7 |
fiule | 1 2 3 4: 6 9 8 5 7 |
Pentru un itinerar care conține 9 clienți, presupunem că traversăm următoarele două căi (un număr reprezintă un client). Trecem aceste două căi după locusul 4: obținem calea copilului.
Pe baza acestui principiu, au fost dezvoltați mulți algoritmi genetici, fiecare folosind diferite variante pentru a se apropia cât mai mult de maxim în toate cazurile. Există, de asemenea, o competiție pe internet care propune dezvoltarea unui algoritm capabil să găsească cea mai bună cale pe o problemă a vânzătorului călător în 250 de orașe.
Aplicații industrialeUn prim exemplu este o implementare efectuată în cadrul companiei Motorola . Problema Motorola a folosit algoritmi genetici pentru se referă la testarea aplicațiilor computerizate. Într-adevăr, în timpul fiecărei modificări aduse unei cereri, este recomandabil să retestăm cererea pentru a vedea dacă modificările aduse nu au avut o influență negativă asupra restului cererii. Pentru aceasta, metoda clasică este de a defini manual planurile de testare care să permită trecerea în toate funcțiile aplicației. Dar acest tip de test necesită multă muncă umană. Prin urmare, scopul Motorola a fost automatizarea acestei faze de definire a planurilor de testare. Pentru aceasta, au definit un algoritm în care fiecare individ corespunde unui rezultat al execuției unui program (lanțul de valori transmise programului) și în care fiecare individ primește o valoare care corespunde capacității sale de a trece în maximum părți ale codului aplicației. În cele din urmă, instrumentul dezvoltat face posibilă, utilizând un algoritm genetic, dezvoltarea acestor programe de testare pentru a maximiza suprafețele testate, astfel încât atunci când se aduc modificări aplicației, acesta poate fi supus testelor. Alte domenii industriale folosesc astăzi algoritmi genetici. Se poate păstra, printre altele, aerodinamica în care sunt dezvoltate optimizări folosind aceste instrumente, optimizarea structurală, care constă în minimizarea greutății unei structuri luând în considerare tensiunile admisibile de tensiune pentru diferitele elemente și căutarea rutelor: acești algoritmi au fost utilizate de NASA pentru misiunea de explorare pe Marte , în gestionarea mișcărilor robotului Pathfinder .
Compania Sony și-a folosit și robotul Aibo . Într-adevăr, acest robot a „învățat” să meargă într-un dispozitiv experimental în care sistemul său de control a fost supus unei evoluții artificiale. Au fost testate diferite moduri de control, cele mai eficiente au fost încrucișate și rezultatul a fost foarte pozitiv. Din generație în generație, robotul s-a îndreptat, apoi a început să meargă, adesea căzând și a ajuns să meargă cu un pas constant.
Business intelligenceAlgoritmii genetici sunt implementați în anumite instrumente de business intelligence sau data mining , de exemplu pentru a căuta o soluție optimă la o problemă prin mutația atributelor (variabilelor) populației studiate.
Acestea sunt utilizate, de exemplu, într-un studiu de optimizare a unei rețele de puncte de vânzare sau agenții (bancă, asigurări etc.) pentru a încerca să răspundă la întrebări:
Algoritmii genetici folosesc teoria lui Darwin : selecția naturală a variațiilor individuale: cei mai potriviți indivizi (cei mai în formă ) tind să supraviețuiască mai mult și să se reproducă mai ușor.
Îmbunătățirea foarte rapidă a populației la început ( căutare globală ); din ce în ce mai lent pe măsură ce trece timpul ( căutare locală ).
Convergență : valoarea medie a funcției de adaptare tinde să se apropie de cea a celui mai adaptat individ: creșterea standardizării populației.
Timpul teoretic de calcul al algoritmilor genetici crește odată cu , fiind numărul de variabile.