Algoritmii genetici pe înțeles
Evoluția a produs ochi, aripi și creiere fără niciun proiectant, pur și simplu păstrând ceea ce funcționează și variindu-l. Un algoritm genetic împrumută această idee pentru a rezolva probleme pe calculator. Nu trebuie să înțeleagă problema, ci doar să deosebească un răspuns mai bun de unul mai slab, ceea ce îl face un instrument puternic atunci când spațiul răspunsurilor posibile este prea mare și prea ciudat pentru a fi explorat în orice alt mod.
Ideea
În anii 1960 și 1970, John Holland de la Universitatea din Michigan a transformat teoria lui Darwin într-un algoritm, descris în cartea sa Adaptation in Natural and Artificial Systems din 1975. Cam în aceeași perioadă, Ingo Rechenberg și Hans-Paul Schwefel au dezvoltat în Germania strategiile evolutive pentru proiectarea inginerească. Rețeta comună: se păstrează o populație de soluții candidate, se evaluează, cele mai bune se reproduc cu variație și totul se repetă de-a lungul multor generații.
Genele și populația
Fiecare candidat este descris de un cromozom, o listă de gene. În laborator, genele unei rachete sunt impulsurile ei, câte unul pentru fiecare moment al zborului; în alte probleme ar putea fi biții unui număr, ordinea orașelor pe un traseu sau dimensiunile pieselor dintr-un proiect. Prima generație este aleatorie, ceea ce înseamnă că explorează larg spațiul răspunsurilor, dar aproape că nu are răspunsuri bune.
Funcția de fitness
Fitnessul este singurul număr care spune cât de bun este un candidat și singurul lucru pe care algoritmul îl știe despre problemă. Pentru rachete, el răsplătește cel mai mult sosirea timpurie, apoi terminarea zborului aproape de țintă, și penalizează prăbușirea. O funcție de fitness bine aleasă ghidează căutarea lin spre răspunsuri bune; una neglijentă răsplătește ce nu trebuie, iar algoritmul va exploata orice portiță lăsată deschisă.
Selecția
Părinții sunt aleși astfel încât candidații mai adaptați să aibă mai mulți copii, dar și cei mai slabi au o șansă, pentru că genele lor pot conține fragmente utile. Selecția prin ruletă îi dă fiecărui candidat o felie dintr-o roată proporțională cu fitnessul său; selecția prin turneu alege câțiva la întâmplare și îl ia pe cel mai bun dintre ei. O selecție mai puternică grăbește progresul, dar face și populația mai uniformă, ceea ce poate încheia căutarea prea devreme.
Încrucișarea și mutația
Încrucișarea combină doi părinți: aici un copil preia prima parte a genelor de la un părinte și restul de la celălalt, astfel încât manevrele de la începutul zborului unei rachete se pot întâlni cu cele de la final ale alteia. Mutația înlocuiește câteva gene la întâmplare. Încrucișarea recombină ceea ce populația are deja; mutația aduce ceea ce nu a avut niciodată. Teorema schemelor a lui Holland descrie cum se răspândesc în populație blocurile scurte de gene bune sub acest amestec de selecție și recombinare.
Elitism, explorare și exploatare
Copierea neschimbată a câtorva dintre cei mai buni candidați în generația următoare, elitismul, garantează că cel mai bun răspuns nu se pierde niciodată. Orice algoritm genetic trebuie să echilibreze explorarea, adică încercarea unor regiuni noi ale spațiului de căutare, cu exploatarea, adică rafinarea a ceea ce este deja bun. Cu prea puțină variație, populația converge spre un singur răspuns mediocru; cu prea multă, nu se stabilizează niciodată. Mărimea populației, rata de mutație și presiunea selecției sunt butoanele care reglează acest echilibru.
Optimuri locale
Un algoritm genetic urmează doar fitnessul, așa că poate fi păcălit. Când drumul spre cel mai bun răspuns trece mai întâi prin răspunsuri mai slabe, populația urcă pe cel mai apropiat deal și rămâne acolo: un optim local. În spatele pereților decalați din laborator, rachetele care se prăbușesc sub țintă obțin un scor mai bun decât cele care se întorc pentru a găsi deschiderea, așa că populația se îngrămădește lângă perete. Remediile includ populații mai mari, o mutație mai puternică, menținerea diversității populației și, mai presus de toate, o funcție de fitness mai bună.
Explorați singur
Deschideți laboratorul de algoritmi genetici pentru a face rachetele să evolueze în jurul unui perete, al unei deschideri, al unor stâlpi, al unor pereți decalați sau al unor pereți desenați chiar de dumneavoastră. Schimbați populația, rata de mutație, durata de viață și metoda de selecție, activați și dezactivați elitismul și urmăriți în grafic cât de repede crește proporția rachetelor care ating ținta sau de ce nu crește.
Întrebări frecvente
Este un algoritm genetic o formă de inteligență artificială?
Face parte din domeniul mai larg al IA și al învățării automate, ca metodă de căutare și optimizare. Nu învață din exemple ca o rețea neuronală; îmbunătățește soluțiile candidate prin încercări și selecție. Cele două sunt adesea combinate, de exemplu prin evoluția structurii sau a ponderilor rețelelor neuronale, o abordare numită neuroevoluție.
Găsește un algoritm genetic întotdeauna cel mai bun răspuns?
Nu. Este o euristică: de obicei găsește răspunsuri bune la probleme dificile, dar nu garantează cel mai bun răspuns și nu dovedește cât de aproape este de el. Pentru problemele la care o metodă exactă este suficient de rapidă, acea metodă este mai bună.
Care este diferența dintre un algoritm genetic și strategiile evolutive?
Ambele sunt algoritmi evolutivi. Algoritmii genetici clasici pun accentul pe încrucișarea unor cromozomi asemănători șirurilor de caractere; strategiile evolutive lucrează în principal cu mutația numerelor reale și își adaptează adesea singure mărimea mutațiilor pe parcurs. Metodele moderne combină idei din ambele.
De ce sunt rachetele atât de stângace la început?
Primele lor gene sunt impulsuri complet aleatorii, care în medie se anulează, așa că rachetele plutesc în derivă. Abia după ce selecția a păstrat rarele rachete care s-au întâmplat să împingă aproximativ în direcția bună, iar încrucișarea le-a combinat porțiunile bune, apar zboruri coordonate.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Deschideți laboratorul de algoritmi genetici