Algoritm genetic

Un algoritm genetic este un algoritm euristic folosit pentru a încerca să rezolve probleme de optimizare pentru care nu sunt cunoscuți alți algoritmi eficienți de complexitate liniară sau polinomială. Adjectivul „genetic”, inspirat de principiul selecției naturale și al evoluției biologice teoretizat în 1859 de Charles Darwin , derivă din faptul că, la fel ca modelul evolutiv darwinian care găsește explicații în ramura biologiei numită genetică , algoritmii genetici implementează mecanisme conceptual asemănătoare cu cele ale proceselor biochimice descoperite de această știință.

Istorie

Nașterea algoritmilor genetici provine din primele teorii ale lui Ingo Rechenberg care, pentru prima dată, în 1960, a început să vorbească despre „strategii evolutive” în cadrul informaticii.

Cu toate acestea, prima creație reală a unui algoritm genetic este atribuită istoric lui John Henry Holland care, în 1975, în cartea Adaptare în sisteme naturale și artificiale a publicat o serie de teorii și tehnici încă de o importanță fundamentală pentru studiul și dezvoltarea materiei. De fapt, studiile lui Holland sunt responsabile atât de teorema care asigură convergența algoritmilor genetici către soluții optime, cât și de așa-numita teoremă a schemei , cunoscută și sub numele de „teorema fundamentală a algoritmilor genetici”. ^{[ fără sursă ]} . Această ultimă teoremă a fost concepută și dovedită inițial pe ipoteza codării binare, dar în 1991, Wright a extins-o la cazurile de codificare cu numere reale, demonstrând , de asemenea , că o astfel de codificare este preferabilă în cazul problemelor de optimizare continuă. ^{[ fără sursă ]} .

Contribuții uriașe se datorează și lui John Koza, care în 1992 a inventat programarea genetică sau aplicarea algoritmilor genetici la producția de software capabil să evolueze devenind capabil să îndeplinească sarcini pe care inițial nu a fost capabil să le îndeplinească.

În 1995, Stewart Wilson a reinventat sistemele clasificatoare ale inteligenței artificiale, redenumindu-le ca XCS și făcându-le capabile să învețe prin tehnicile algoritmilor genetici, în timp ce în 1998 Herrera și Lozano au prezentat o analiză extinsă a operatorilor genetici. Operatorii Herrera și Lozano sunt aplicabili soluțiilor codificate cu numere reale și au făcut din câmpul numerelor reale o formă adecvată și consolidată de reprezentare pentru algoritmi genetici în domenii continue.

Descriere

În rezumat, algoritmii genetici constau în algoritmi care permit evaluarea diferitelor soluții inițiale (ca și cum ar fi diferiți indivizi biologici) și că prin recombinarea lor (în mod similar reproducerii biologice sexuale) și introducerea elementelor de tulburare (similar cu mutațiile genetice aleatorii) produc noi soluții (indivizi noi) care sunt evaluați alegându-i pe cei mai buni (selecția mediului) în încercarea de a converge către „cele mai bune” soluții. Fiecare dintre aceste faze de recombinare și selecție poate fi numită generație ca cele ale ființelor vii. În ciuda acestei utilizări în contextul optimizării, dată fiind natura inerent aleatorie a algoritmului genetic, nu există nici o modalitate de a ști a priori dacă va fi de fapt în măsură să găsească o soluție acceptabilă la problema luată în considerare. Dacă obțineți un rezultat satisfăcător, nu înțelegeți neapărat de ce a funcționat, deoarece nu a fost conceput de nimeni, ci printr-o procedură aleatorie.

Algoritmii genetici se încadrează în studiul inteligenței artificiale și mai ales în ramura calculului evolutiv , sunt studiați și dezvoltați în domeniul inteligenței artificiale și al tehnicilor de calcul ușor , dar își găsesc aplicarea într-o mare varietate de probleme aferente diferitelor contexte. precum electronica ^[1] , biologia ^[2] și economia ^[3] .

Operațiune

Înainte de explicația efectivă a funcționării algoritmilor genetici, este necesar să se presupună că aceștia moștenesc și adaptează din biologie unele terminologii care sunt prezentate anterior aici pentru o claritate ulterioară ulterioară:

Cromozom : una dintre soluțiile la o problemă luată în considerare. În general este codificat cu un bit sau un vector de caractere.
Populație : ansamblu de soluții legate de problema luată în considerare.
Gena : parte a unui cromozom. În general, este alcătuit din una sau mai multe părți ale vectorului de biți sau caractere care codifică cromozomul.
Fitness : grad de evaluare asociat unei soluții. Evaluarea se bazează pe o funcție special concepută numită funcția de fitness .
Crossover : generarea unei noi soluții prin amestecarea soluțiilor existente.
Mutație : alterarea aleatorie a unei soluții.

Un algoritm genetic tipic, în timpul execuției sale, face ca soluțiile să evolueze în conformitate cu următoarea schemă de bază:

Generarea aleatorie a primei populații de soluții (cromozomi).
Aplicarea funcției de fitness la soluțiile (cromozomii) aparținând populației actuale.
Selectarea soluțiilor considerate cele mai bune pe baza rezultatului funcției de fitness și a logicii de selecție alese.
Proces de încrucișare pentru a genera soluții hibride pornind de la soluțiile alese la punctul 3 .
Crearea unei noi populații pornind de la soluțiile identificate la punctul 4 .
Repetați procedura începând de la punctul 2 și folosind noua populație creată la punctul 5 .

Iterația pașilor prezentați permite evoluția către o soluție optimizată a problemei luate în considerare.

Deoarece acest algoritm de bază suferă de faptul că unele soluții optime ar putea fi pierdute în cursul evoluției și de faptul că evoluția ar putea să cadă înapoi și să stagneze în „optimii locali”, este adesea integrat cu tehnica „elitismului” și cu aceea de mutații aleatorii. Primul constă dintr-un pas suplimentar care precede punctul 3, care copiază chiar și pe cei mai buni indivizi din populația anterioară în noile populații, al doilea în loc de punctul 4 introduce mutații aleatorii ocazionale în soluțiile identificate pentru a permite ieșirea din orice recăderi în premise.

Codificarea

După cum sa menționat, soluțiile la problema luată în considerare, indiferent dacă acestea sunt cele inițiale aleatoare sau cele derivate din evoluție, trebuie codificate cu o anumită tehnică.

Cele mai frecvente codificări sunt:

Codare vectorială binară : este cea mai răspândită, constă dintr-un vector de n câmpuri binare în care valorile 1 sau 0 identifică caracteristicile elementare ale soluției. Avantajele acestei tehnici constau în faptul că este simplă de implementat și gestionat de-a lungul întregii evoluții. Dezavantajele constau în dificultățile inerente de a converti soluțiile în această codificare și posibilitățile reprezentative rare.
Codare vectorială reală : la fel ca codarea vectorială binară, dar se folosesc numere reale. Avantajul este de a introduce o mai mare expresivitate și versatilitate în codificare, în detrimentul complexității crescute.
Codare vectorială directă : constă dintr-o codare vectorială în care fiecare câmp conține direct valorile legate de problemă. Avantajul este acela al codării ușoare, dezavantajul constă în gestionarea dificilă a algoritmului și în proiectarea dificilă a funcției de fitness și a proceselor de încrucișare și mutație.
Codarea arborelui : fiecare cromozom este un arbore al unor obiecte, cum ar fi funcțiile și comenzile unui limbaj de programare. În acest caz, pentru semantica și sintaxa sa specifice, se folosește adesea limbajul de programare Lisp , care simplifică foarte mult operațiunile de codare.

În cadrul codării vectoriale este, de asemenea, corect să se introducă conceptele de „schemă” și „blocuri de construcție” strâns legate de teorema schemei Olandei.

Funcția de fitness

Funcția de fitness este cea care permite asocierea fiecărei soluții a unuia sau mai multor parametri legați de modul în care aceasta din urmă rezolvă problema luată în considerare. În general, este asociat cu performanța de calcul și, prin urmare, cu performanța în timp a soluției.

Logica selecției

Datorită fenomenelor complexe de interacțiune neliniară ( epistaticitate ), nu se ia de la sine înțeles că din două soluții promițătoare se naște o a treia una mai promițătoare și nici din două soluții cu valori de fitness reduse o a treia cu o fitness mai mare valoarea este generată. scăzută. Pentru a depăși aceste probleme, în timpul alegerii soluțiilor candidate la evoluție, pe lângă parametrul obținut din funcția de fitness, sunt utilizate și tehnici speciale de „selecție”. Cele mai frecvente sunt:

Selectarea ruletei : probabilitatea ca o soluție să fie aleasă pentru ao face să evolueze este direct proporțională cu valoarea returnată de funcția de fitness. Această tehnică prezintă probleme în cazul în care există diferențe mari de valori, deoarece cele mai proaste soluții ar fi selectate prea rar.
Selecția pe categorii : similară cu selecția pentru ruletă, dar evaluarea se efectuează proporțional cu suma valorii funcției de fitness pentru fiecare pereche posibilă de soluții. Problema prezentată de această tehnică de alegere este reprezentată de încetineala convergenței în cazul în care există diferențe prea mici între perechile de soluții candidate.
Selectarea turneului : soluțiile sunt grupate și continuăm să le evaluăm cu un algoritm precum cel prezentat în rândurile următoare.
- A. Alegeți aleatoriu indivizi care aparțin populației.
- B. Alegeți cel mai bun individ și stabiliți probabilitatea sa de alegere a $p$ ${\ displaystyle p}$ $p$ .
- C. Alegeți al doilea cel mai bun individ și setați probabilitatea alegerii a $p*(1-p)$ ${\ displaystyle p * (1-p)}$ $p * (1-p)$ .
- D. Alegerea celui de-al treilea cel mai bun individ și stabilirea probabilității sale de alegere a $p*(1-p)^{2}$ ${\ displaystyle p * (1-p) ^ {2}}$ $p * (1-p) ^ 2$ .
- ... continuați până când soluțiile alese sunt epuizate.
Selecția Boltzmann : soluțiile sunt alese cu un grad de probabilitate care, la începutul algoritmului, favorizează explorarea și apoi tinde să se stabilizeze. Parametrii utilizați de selecția lui Boltzmann sunt:
- $P=e^{-f_{max}-{f(X_{i}) \over T}}$ ${\ displaystyle P = e ^ {- f_ {max} - {f (X_ {i}) \ peste T}}}$ $P = e ^ {- f_ {max} - {f (X_i) \ peste T}}$
- $T=T_{0}*(1-\alpha )^{k}$ ${\ displaystyle T = T_ {0} * (1- \ alpha) ^ {k}}$ $T = T_0 * (1- \ alfa) ^ k$ cu $\alpha \in [0,1]$ ${\ displaystyle \ alpha \ in [0,1]}$ $\ alpha \ în [0,1]$ Și $T_{0}\in [5,100]$ ${\ displaystyle T_ {0} \ in [5,100]}$ $T_0 \ în [5.100]$
- $k=1+100*{g \over C}$ ${\ displaystyle k = 1 + 100 * {g \ peste C}}$ $k = 1 + 100 * {g \ peste C}$

Crossover-ul

Pentru simplitate, în timpul explicației încrucișării, se va face referire la codificarea vectorială, dar procedura pentru codificarea arborelui este similară și în loc să fie aplicată câmpurilor vectoriale, este aplicată nodurilor arborelui. Pe baza unui operator stabilit inițial, unele părți ale genelor soluțiilor candidate la evoluție sunt amestecate pentru a obține soluții noi.

Cei mai utilizați operatori sunt:

Crossover într-un punct

Crossover într-un singur punct: constă în luarea în considerare a două soluții potrivite pentru evoluție și tăierea vectorilor de codificare la un punct aleatoriu sau predefinit pentru a obține două capete și două cozi. Prima soluție nouă obținută va fi dată de combinația capului primei soluții cu coada celei de-a doua, în timp ce a doua soluție nouă va fi dată de coada primei soluții cu capul celei de-a doua.

Crossover în două puncte

Crossover în două puncte: constă în luarea în considerare a două soluții potrivite pentru evoluție și în tăierea vectorilor lor de codificare în două puncte predefinite sau aleatorii pentru a obține un cap, o parte centrală și o coadă din prima și a doua soluție. Prima soluție nouă va fi dată de capul și coada primei soluții și de partea centrală a celei de-a doua soluții. A doua nouă soluție va fi dată de partea centrală a primei soluții și de capul și coada celei de-a doua soluții.

Crossover neted

Crossover uniform: constă în schimbul aleator de biți între soluțiile care sunt candidate la evoluție. De asemenea, subliniem existența încrucișărilor uniforme parțiale, adică a încrucișărilor uniforme în care schimbul de biți este limitat la un procent fix sau dinamic al cromozomilor care sunt candidați la evoluție.
Crossover aritmetic: constă în utilizarea unei operații aritmetice pentru a crea noua soluție. (de exemplu, XOR sau un AND ).

Crossoverul nu trebuie neapărat să aibă loc la fiecare iterație a algoritmului genetic. În general, frecvența de încrucișare este reglementată de un parametru specific numit în mod obișnuit $p_{c}$ ${\ displaystyle p_ {c}}$ $p_ {c}$ .

Mutația

Mutația constă în modificarea pseudoaleatorie a unor părți ale genelor pe baza coeficienților inițial definiți. Aceste modificări sunt uneori folosite pentru a îmbunătăți valoarea funcției de fitness pentru soluția în cauză și alteori sunt utilizate pentru extinderea spațiului de cercetare și implementarea tehnicii elitiste pentru a nu face ca evoluția să cadă înapoi în premise excelente. Frecvența cu care trebuie să apară o mutație este, în general, reglementată de un parametru specific numit în mod obișnuit $p_{m}$ ${\ displaystyle p_ {m}}$ $p.m$ .

Variante

Algoritm genetic multi-obiectiv

În cazul în care aveți mai multe ținte de optimizat, puteți utiliza un algoritm genetic cu mai multe ținte.

Practic algoritmul funcționează ca atunci când urmărește un singur obiectiv, prin urmare pleacă întotdeauna de la un anumit număr de soluții posibile (populația) și încearcă să identifice, prin diferite iterații, un anumit număr de soluții optime, care vor fi găsite pe un Pareto față . Diferența este că există acum două sau mai multe funcții de fitness de evaluat.

Exemple didactice

În această secțiune vor fi analizate și abordate câteva probleme didactice pentru a arăta cum se aplică un algoritm genetic.

Problema rucsacului

Problema rucsacului constă în a putea introduce într-un rucsac cu o anumită capacitate cât mai multe obiecte posibile dintr-o listă dată, respectând totodată constrângerile de greutate specifice. Cea mai bună soluție este să poți pune cât mai multe obiecte în rucsac fără a depăși limitele de greutate impuse.

Codificare: Cel mai simplu mod de a codifica această problemă este de a utiliza vectori binari. Vectorul unei soluții ar trebui să aibă lungimea numărului total de obiecte disponibile și, pentru fiecare câmp, ar trebui să aibă un „1” sau un „0”. Una dintre cele două valori ar identifica obiectul ca prezent în rucsac, iar cealaltă ca absentă. Evident, soluțiile ar trebui formulate într-un mod compatibil cu problema, obiectele pentru o greutate mai mare decât cea permisă sau pentru un spațiu mai mare decât cel disponibil nu ar putea fi inserate.
Fitness: Funcția fitness ar trebui să fie concepută astfel încât să țină seama atât de numărul de obiecte plasate în rucsac, cât și de greutatea acestuia.
Selecție, încrucișare și mutație: pentru metoda de selecție, încrucișare și mutație ar fi indicat să se evalueze diferite posibilități și probabilități în funcție de mărimea problemei. Pentru o problemă cu un rucsac mic, o anumită metodă s-ar putea dovedi eficientă, dar s-ar putea să nu fie neapărat aceeași pentru o problemă cu un rucsac foarte mare și invers. Încrucișarea și mutația trebuie, evident, să fie predispuse pentru a menține coerența problemei luate în considerare. În acest caz, de exemplu, un crossover sau o mutație care va introduce același obiect de două ori în aceeași soluție nu ar fi acceptabilă.

Problema vânzătorului călător

Problema vânzătorului călător constă în posibilitatea de a vizita cel puțin o dată toate orașele de pe listă, valorificând la maximum conexiunile dintre ele și călătorind cât mai puțin posibil.

Codificare: Probabil cea mai simplă modalitate de a codifica această problemă este folosind vectori întregi. Câmpul unui vector asociat cu un cromozom ar identifica în mod unic unul dintre orașele de vizitat, în timp ce poziționarea acestuia ar identifica ordinea vizitei. Evident, această codificare trebuie să respecte constrângerile legate de natura problemei, cum ar fi prezența unui oraș cel puțin o dată în fiecare cromozom.
Fitness: funcția de fitness ar trebui să evalueze cromozomii pe baza distanței de parcurs pentru a implementa calea codificată.
Selecție, încrucișare și mutație: pentru metoda de selecție, încrucișare și mutație ar fi indicat să se evalueze diferite posibilități și probabilități în funcție de mărimea problemei. Pentru o problemă din câteva orașe, o anumită metodă s-ar putea dovedi eficientă, dar nu este neapărat cazul unei probleme cu multe orașe și invers. Încrucișarea și mutația trebuie, evident, să fie predispuse pentru a menține coerența problemei luate în considerare. În acest caz, de exemplu, un crossover sau mutație care elimină vizita unui oraș dintr-o soluție nu ar fi acceptabilă.

Proiecte reale cu algoritmi genetici

Acovea : software open source conceput pentru a găsi cele mai bune opțiuni de optimizare a profilului compilatorului gcc, care este o problemă extrem de complexă ^[4] .

Notă

Bibliografie

John Holland, „Adaptare în sisteme naturale și artificiale: o analiză introductivă cu aplicații la biologie, control și inteligență artificială”, Bradford Books, 1992 ISBN 0262581116
DB Fogel, Calcul evolutiv: spre o nouă filozofie a inteligenței mașinilor , IEEE Press, NewYork, 1995 ISBN 0-7803-5379-X
JR Koza, Programare genetică: programarea computerelor prin selecție naturală , MIT Press, Cambridge, MA, 1992 ISBN 0-262-11170-5
Poli, R., Langdon, WB, McPhee, NF (2008), A Field Guide to Genetic Programming , Lulu.com, disponibil gratuit pe internet ISBN 978-1-4092-0073-4
Alden H. Wright, Algoritmi genetici pentru optimizarea parametrilor reali, 1991 [1]
( EN ) Algoritmi genetici de J. Holland , pe econ.iastate.edu .
( EN ) Algoritmi de optimizare globală - Teorie și aplicație ( PDF ), pe it-weise.de .

Elemente conexe

linkuri externe

( EN ) Algoritm genetic , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.
( EN ) Exemplu animat și interactiv de algoritm genetic (necesită java). , pe obitko.com .
( EN ) Exemplu animat și interactiv de algoritm genetic pentru rezolvarea problemei vânzătorului călător (necesită java). , pe obitko.com .
( RO ) Joc multiplayer de strategie online bazat pe algoritmi genetici (necesită înregistrare). , pe geneoverload.com . Adus pe 9 octombrie 2011 (arhivat din original la 25 septembrie 2011) .
Braț mecanic de învățare genetică Simularea fizică a unui braț mecanic cu auto-învățare bazată pe algoritmi genetici (necesită descărcare de program).

Controlul autorității	Thesaurus BNCF 57105 · LCCN (RO) sh92002377 · GND (DE) 4265092-6 · BNF (FR) cb12418734h (data) · NDL (RO, JA) 00918134

Portalul de biologie	Portal IT
Portal de inginerie	Portalul de statistici

[1] (EN) al prevederilor LVSI Proiectarea prin algoritmi genetici. Studiu realizat de Volker Schnecke și Oliver Vornberger de la Universitatea din Osnabrück

[2] (EN) Prezentarea unui algoritm pentru studiul plierii proteinelor MJ Bayley, J. Jones și William G. Williamson MP, NCBI SUA

[3] (EN) Economie de algoritmi genetici JL Reddinger, Universitatea de Stat din Montana Arhivat pe 5 martie 2016 Internet Archive .

[4] (EN) Codul și programul de informare acovea Filed 13 octombrie 2012 în Internet Archive .

[1]

[2]

[3]

[4]

V · D · M Genetica
Material genetic	Nucleotide · baze azotate · Acizi nucleici ( ADN · ARN ) · Cromozomi · Genom
Concepte cheie	Gene · Cod genetic · Alele · Locus · Moștenire · Diversitate genetică · Mutație
Domenii de genetică	Genetica formale · genetica moleculara · genetica populatiei · Genomics · Human Genetics
Geneticieni	Gregor Mendel · Thomas Hunt Morgan · Ronald Fisher · Frederick Griffith · Erwin Chargaff · Barbara McClintock · James Watson · Francis Crick · Rosalind Franklin · Alec Jeffreys

V · D · M Învățare automată
Probleme	Clasificarea · Regresie · asociere Reguli · Învățare nesupravegheați · Supravegheat de învățare · Reinforcement Learning · învățare profundă
Învățare nesupravegheată	Clustering · clustering Ierarhica · K mijloace · Așteptarea maximizare · DBSCAN · schimbare medie · antagonist generativă rețea (CGAN · cycleGAN VAE-GAN)
Învățare supravegheată	Arborele decizional · Pădure aleatorie · CRF · HMM · KNN · Clasificator bayesian · Rețea neuronală artificială · Regresie liniară · Regresie logistică · PGM · SVM
Consolidarea învățării	Q-learning · SARSA · TD
Reducerea dimensiunii	Analiza factorilor · CCA · ICA · LDA · PCA · Selecția caracteristicilor · Extragerea caracteristicilor · t-SNE
Rețele neuronale artificiale	Perceptron · RBF · N · FFN · Rețea Hopfield · MLP · RNN ( LSTM ) · RBM · SOM · CNN · TDNN · SNN
Software	Keras · Microsoft Cognitive Toolkit · scikit-learn · TensorFlow · Theano · Torch · Weka
Alte	Algoritm genetic · PSO · Caracteristic