introduction genetic algorithms machine learning
generator de numere aleatorii 0-1
Acest tutorial pentru algoritmi genetici explică detaliat ce sunt algoritmii genetici și rolul lor în învățarea automată :
În Tutorial anterior , am aflat despre modele de rețea neuronală artificială - Perceptron multistrat, Backpropagation, Radial Bias și Kohonen Self Organizing Maps, inclusiv arhitectura lor.
Ne vom concentra asupra algoritmilor genetici care au apărut înainte decât rețelele neuronale, dar acum GA a fost preluată de NN. Deși, GA mai are aplicații în viața reală, cum ar fi probleme de optimizare, cum ar fi programarea, jocuri, robotică, proiectare hardware, probleme de vânzător de călătorie etc.
Algoritmii genetici sunt algoritmi care se bazează pe ideea evolutivă a selecției naturale și a geneticii. GA sunt algoritmi de căutare euristică adaptivi, adică algoritmii urmează un model iterativ care se schimbă cu timpul. Este un tip de învățare prin întărire în care feedback-ul este necesar fără a spune calea corectă de urmat. Feedback-ul poate fi fie pozitiv, fie negativ.
=> Citiți seria completă de formare pentru învățarea automată
Ce veți învăța:
- De ce să folosiți algoritmi genetici
- Ce sunt algoritmii genetici
- Avantajele și dezavantajele algoritmului genetic
- Aplicații ale algoritmilor genetici
- Concluzie
De ce să folosiți algoritmi genetici
GA-urile sunt algoritmi mai robusti care pot fi utilizați pentru diverse probleme de optimizare. Acești algoritmi nu deviază ușor în prezența zgomotului, spre deosebire de alți algoritmi AI. GA-urile pot fi utilizate în căutarea spațiului mare sau a spațiului multimodal.
Contextul biologic al algoritmilor genetici
Genetica este derivată din cuvântul grecesc „geneză” care înseamnă a crește. Genetica decide factorii de ereditate, asemănările și diferențele dintre descendenți în procesul de evoluție. Algoritmii genetici sunt, de asemenea, derivați din evoluția naturală.
Unele terminologii într-un cromozom biologic
- Cromozomi: Toate informațiile genetice ale unei specii sunt cromozomi stocați.
- Gene: Cromozomii sunt împărțiți în mai multe părți numite gene.
- Alele: Genele identifică caracteristica unui individ. Posibilitatea unei combinații de gene pentru a forma proprietăți se numește alele. O genă poate avea alele diferite.
- Fondului genetic: Toate combinațiile posibile de gene care sunt alele într-un grup de populație se numește grup de gene.
- Genom: Ansamblul genelor unei specii se numește genom.
- Locus: Fiecare genă are o poziție într-un genom care se numește locus.
- Genotip: O combinație completă de gene la un individ se numește genotip.
- Fenotip: Un set de genotipuri într-o formă decodificată se numește fenotip.
Ce sunt algoritmii genetici
Algoritmii genetici stimulează procesul ca și în sistemele naturale de evoluție. Charles Darwin a afirmat teoria evoluției că, în evoluția naturală, ființele biologice evoluează în conformitate cu principiul „supraviețuirii celor mai în formă”. Căutarea GA este concepută pentru a încuraja teoria „supraviețuirii celor mai în formă”.
GA efectuează o căutare aleatorie pentru a rezolva problemele de optimizare. GA folosește tehnici care folosesc informațiile istorice anterioare pentru a-și direcționa căutarea către optimizare în noul spațiu de căutare.
Corelația unui cromozom cu GA
Corpul uman are cromozomi care sunt compuși din gene. Un set al tuturor genelor unei specii specifice se numește genom. La ființele vii, genomii sunt depozitați în diverși cromozomi, în timp ce în GA toate genele sunt depozitate în același cromozom.
Comparație între evoluția naturală și terminologia algoritmului genetic
| Evoluția naturală | Algoritm genetic |
|---|---|
| Cromozom | Şir |
| Gene | Caracteristică |
| Alele | Valoarea caracteristicii |
| Genotip | Șir codat |
| Fenotip | Structura decodificată |
Terminologie importantă în GA
- Populație: Este un grup de indivizi. Populația include numărul de indivizi testați, informații despre spațiul de căutare și parametrii fenotipului. În general, populația este inițializată aleatoriu.
- Persoane fizice: Indivizii sunt o singură soluție în populație. Un individ are un set de parametri numiți gene. Gene combinate pentru a forma cromozomi.
- Gene: Genele sunt elemente constitutive ale algoritmilor genetici. Un cromozom este format din gene. Genele pot determina soluția la problemă. Ele sunt reprezentate printr-un șir de biți (0 sau 1) de lungime aleatorie.
- Fitness: Fitness-ul indică valoarea fenotipului problemei. Funcția de fitness spune cât de aproape este soluția de soluția optimă. Funcția de fitness este determinată în mai multe moduri, cum ar fi suma tuturor parametrilor legați de problemă - distanța euclidiană etc. Nu există o regulă pentru evaluarea funcției de fitness.
Un algoritm genetic simplu
O GA simplă are o populație de cromozomi individuali. Acești cromozomi reprezintă soluții posibile. Operatorii de reproducere sunt aplicați peste aceste seturi de cromozomi pentru a efectua mutații și recombinare. Astfel, este important să găsiți operatori de reproducere corespunzători, deoarece comportamentul GA depinde de acesta.
Un algoritm genetic simplu este următorul:
# 1) Începeți cu populația creată la întâmplare.
#Două) Calculați funcția de fitness a fiecărui cromozom.
# 3) Repetați pașii până când se creează n descendenți. Puii sunt creați așa cum se arată mai jos.
- Selectați o pereche de cromozomi din populație.
- Treceți perechea cu probabilitatea pcpentru a forma descendenți.
- Mutați încrucișarea cu probabilitatea pm.
# 4) Înlocuiți populația inițială cu populația nouă și treceți la pasul 2.
Să vedem pașii urmați în acest proces de iterație. Se generează populația inițială de cromozomi. Populația inițială ar trebui să conțină suficiente gene pentru a putea genera orice soluție. Primul fond de populație este generat aleatoriu.
- Selecţie: Cel mai bun set de gene este selectat în funcție de funcția de fitness. Se alege șirul cu cea mai bună funcție de fitness.
- Reproducere: Descendenții noi sunt generați prin recombinare și mutație.
- Evaluare: Noii cromozomi generați sunt evaluați pentru fitnessul lor.
- Înlocuire: În acest pas, populația veche este înlocuită cu populația nou generată.
Metoda de selectare a ruletei
Selectarea roții de ruletă este metoda de selecție utilizată pe scară largă.
Procesul de selecție este scurt așa cum se arată mai jos:
În această metodă, se efectuează o căutare liniară prin intermediul ruletei. Sloturile din roată sunt cântărite în funcție de valoarea individuală de fitness. Valoarea țintă este stabilită în mod aleatoriu în funcție de proporția din suma aptitudinii în populație.
Populația este apoi căutată până la atingerea valorii țintă. Această metodă nu garantează cel mai potrivit dintre indivizi, dar are probabilitatea de a fi cel mai potrivit.
Să vedem pașii implicați în selecția roții ruletei.
Valoarea așteptată a unui individ = Fitness individual / fitness al populației. Sloturile pentru roți sunt atribuite persoanelor în funcție de capacitatea lor fizică. Roata este rotită de N ori, unde N este numărul total de indivizi din populație. Când s-a terminat o rotație, individul selectat este introdus într-un grup de părinți.
- Să fie valoarea totală așteptată a unui număr de indivizi din populație să fie S.
- Repetați pașii de 3-5 ori.
- Selectați un număr întreg între 0 și S.
- Buclați prin indivizi din populație, suma valorilor așteptate până când suma este mai mare decât s.
- Este selectat individul a cărui valoare așteptată plasează suma peste limita s.
Dezavantaje ale selecției roții de ruletă:
- Dacă fitnessul diferă foarte mult, atunci circumferința roții de ruletă va fi luată maxim de cea mai înaltă funcție de fitness cromozom, deci celelalte au foarte puține șanse să fie selectate.
- Este zgomotos.
- Evoluția depinde de diferența de fitness a populației.
Alte metode de selecție
Există multe alte metode de selecție utilizate în 'Selecţie' pasul Algoritmului genetic.
Vom discuta despre celelalte 2 metode utilizate pe scară largă:
# 1) Selectarea rangului: În această metodă, fiecărui cromozom i se acordă o valoare de fitness din clasament. Cea mai proastă condiție fizică este 1 și cea mai bună formă fizică este N. Este o metodă de convergență lentă. În această metodă, diversitatea este păstrată, ducând la o căutare de succes.
Se selectează potențiali părinți și apoi se organizează un turneu pentru a decide care dintre indivizi va fi părinte.
# 2) Selecția turneului: În această metodă, o strategie de presiune selectivă este aplicată populației. Cel mai bun individ este cel cu cea mai înaltă formă fizică. Această persoană este câștigătoarea competiției turneului în rândul indivizilor Nu din populație.
Populația turneului împreună cu câștigătorul este din nou adăugată în grup pentru a genera noi descendenți. Diferența dintre valorile de fitness ale câștigătorului și ale persoanelor din piscina de împerechere oferă o presiune selectivă pentru rezultate optime.
Crossover
Este un proces de a lua 2 persoane și de a produce un copil din ele. Procesul de reproducere după selecție face clone ale înțepăturilor bune. Operatorul de crossover este aplicat peste corzi pentru a produce o descendență mai bună.
Implementarea operatorului crossover este după cum urmează:
- Doi indivizi sunt selectați aleatoriu din populație pentru a produce descendenți.
- Un site încrucișat este selectat la întâmplare de-a lungul lungimii șirului.
- Valorile de pe site sunt schimbate.
Crossover-ul efectuat poate fi un crossover cu un singur punct, crossover în două puncte, crossover multipunct, etc. Crossoverul cu un singur punct are un site de crossover, în timp ce un site de crossover în două puncte are 2 site-uri în care valorile sunt schimbate.
Putem vedea acest lucru în exemplul de mai jos:
Crossover cu un singur punct
Crossover în două puncte
Probabilitate de încrucișare
Pc, probabilitatea de încrucișare este termenul care descrie cât de des se va efectua încrucișarea. 0% probabilitate înseamnă că noii cromozomi vor fi o copie exactă a vechilor cromozomi, în timp ce 100% probabilitate înseamnă că toți cromozomii noi sunt realizați prin încrucișare.
Mutaţie
Mutația se face după încrucișare. În timp ce încrucișarea se concentrează doar asupra soluției actuale, operația de mutație caută tot spațiul de căutare. Această metodă este de a recupera informațiile genetice pierdute și de a distribui informațiile genetice.
Acest operator ajută la menținerea diversității genetice a populației. Ajută la prevenirea minimelor locale și previne generarea de soluții inutile de la orice populație.
Mutația este efectuată în multe moduri, cum ar fi inversarea valorii fiecărei gene cu o probabilitate mică sau efectuarea mutației numai dacă îmbunătățește calitatea soluției.
Unele dintre modalitățile de mutație sunt:
- Flipping: Schimbarea de la 0 la 1 sau 1 la 0.
- Schimb: Sunt alese două poziții aleatorii, iar valorile sunt schimbate.
- Inversare: Se alege poziția aleatorie și biții de lângă aceasta sunt inversați.
Să vedem câteva exemple:
Flipping
Schimbând
Inversare
Probabilitatea de mutație
Pm, probabilitatea mutației este un termen care decide cât de des vor fi mutați cromozomii. Dacă probabilitatea mutației este de 100%, atunci înseamnă că întregul cromozom este schimbat. Dacă nu se efectuează o mutație, atunci sunt generați noi descendenți direct după încrucișare.
Un exemplu de algoritm genetic general Probabilitatea mutației: Pm, probabilitatea mutației este un termen care decide cât de des vor fi mutați cromozomii. Dacă probabilitatea mutației este de 100%, atunci înseamnă că întregul cromozom este schimbat.
Dacă nu se efectuează o mutație, atunci noua descendență este generată direct după încrucișare. Populația inițială de cromozomi este dată ca A, B, C, D. Dimensiunea populației este de 4.
Funcția de fitness este luată ca un număr de 1 în șir.
| Cromozom | Fitness |
|---|---|
| Către: 00000110 | Două |
| B: 11101110 | 6 |
| C: 00100000 | unu |
| D: 00110100 | 3 |
Suma de fitness este 12 ceea ce implică, funcția medie de fitness ar fi ~ 12/4 = 3
Probabilitate de încrucișare = 0,7
Probabilitatea mutației = 0,001
# 1) Dacă sunt selectate B și C, încrucișarea nu se efectuează, deoarece valoarea de fitness a lui C este sub fitness-ul mediu.
#Două) B este mutat => B: 11101110 -> B': 01101110 pentru a păstra diversitatea populației
# 3) B și D sunt selectate, se efectuează încrucișarea.
B: 11101110 E: 10110100 -> D: 00110100 F: 01101110
# 4) Dacă E este mutat, atunci
E: 10110100 -> E': 10110000
Cromozomii corespunzători sunt afișați în tabelul de mai jos. Comanda este pusă la întâmplare.
| Cromozom | Fitness |
|---|---|
| A: 01101110 | 5 |
| B: 00100000 | unu |
| C: 10110000 | 3 |
| D: 01101110 | 5 |
Deși cel mai potrivit individ cu o valoare de fitness de 6 se pierde, capacitatea medie generală a populației crește și ar fi: 14/4 = 3,5
Când să oprești algoritmul genetic
Un algoritm genetic este oprit când sunt îndeplinite unele condiții enumerate mai jos:
# 1) Cea mai bună convergență individuală: Când nivelul minim de fitness scade sub valoarea de convergență, algoritmul este oprit. Aceasta duce la o convergență mai rapidă.
# 2) Cea mai proastă convergență individuală: Atunci când cei mai puțini indivizi din populație ating o valoare de fitness minimă sub convergență, atunci algoritmul este oprit. În această metodă, standardul minim de fitness este menținut în populație. Înseamnă că cel mai bun individ nu este garantat, dar vor fi prezenți o valoare minimă a fitnessului.
# 3) Suma de fitness: În această metodă, dacă suma aptitudinii este mai mică sau egală cu valoarea convergenței, atunci căutarea este oprită. Acesta garantează că toată populația se află în raza de fitness.
# 4) Fitness mediu: În această metodă, cel puțin jumătate din indivizii din populație vor fi mai buni sau egali cu valoarea convergenței.
Unele criterii de convergență sau condiții de oprire pot fi:
- Când au evoluat un număr specificat de generații.
- Când timpul specificat pentru a rula algoritmul a fost îndeplinit.
- Când valoarea de fitness a populației nu se schimbă în continuare cu iterații.
Avantajele și dezavantajele algoritmului genetic
Avantajele unui algoritm genetic sunt:
- Are un spațiu mai larg de soluții.
- Este mai ușor să descoperiți optimul global.
- Paralelism: Mai multe GA-uri pot rula împreună folosind același procesor fără a interfera unul cu celălalt. Funcționează paralel izolat.
Limitări ale GA:
- Identificarea funcției de fitness este o limitare.
- Convergența algoritmilor poate fi prea rapidă sau prea lentă.
- Există o limitare a selectării parametrilor precum crossover, probabilitatea mutației, mărimea populației etc.
Aplicații ale algoritmilor genetici
GA este eficient pentru rezolvarea problemelor cu dimensiuni ridicate. Un GA este utilizat în mod eficient atunci când spațiul de căutare este foarte mare, nu există tehnici matematice de rezolvare a problemelor disponibile și alți algoritmi tradiționali de căutare nu funcționează.
Unele aplicații în care se folosește GA:
- Problemă de optimizare: Unul dintre cele mai bune exemple ale problemelor de optimizare este problema vânzătorului de călătorii care folosește GA. Sunt utilizate pe scară largă alte probleme de optimizare, cum ar fi programarea lucrărilor, optimizarea calității sunetului GA.
- Modelul sistemului imunitar: GA-urile sunt utilizate pentru modelarea diferitelor aspecte ale sistemului imunitar pentru genele individuale și familiile multi-genice în timpul evoluției.
- Învățare automată: GA au fost folosite pentru a rezolva problemele legate de clasificare, predicție, crearea de reguli pentru învățare și clasificare .
Concluzie
Algoritmii genetici se bazează pe metoda evoluției naturale. Acești algoritmi sunt diferiți de ceilalți algoritmi de clasificare deoarece utilizează parametri codificați (0 sau 1), există un număr multiplu de indivizi într-o populație și folosesc metoda probabilistică pentru convergență.
Odată cu procesul de încrucișare și mutație, GA converg la generații succesive. Executarea unui algoritm GA nu garantează întotdeauna o soluție de succes. Algoritmii genetici sunt extrem de eficienți în optimizare - probleme de planificare a lucrărilor.
Sper că acest tutorial v-ar fi îmbogățit cunoștințele despre conceptul de algoritmi genetici !!
=> Vizitați aici pentru seria exclusivă de învățare automată
Lectură recomandată
- Testare bazată pe model folosind algoritmul genetic
- Data Mining Vs Machine Learning Vs Intelligence Artificial Vs Deep Learning
- Tutorial de învățare automată: Introducere în ML și aplicațiile sale
- Tipuri de învățare automată: învățare supravegheată împotriva supravegherii
- Un ghid complet pentru rețeaua neuronală artificială în învățarea automată
- 11 Cele mai populare instrumente software de învățare automată în 2021
- Top 13 cele mai bune companii de învățare automată (Lista actualizată 2021)
- Ce este Support Vector Machine (SVM) în învățarea automată