Un algoritm genetic este un algoritm de căutare euristic adaptiv inspirat de „teoria evoluției în natură a lui Darwin”. .' Este folosit pentru a rezolva probleme de optimizare în învățarea automată. Este unul dintre algoritmii importanți, deoarece ajută la rezolvarea problemelor complexe care ar dura mult timp pentru a fi rezolvate.

Algoritmii genetici sunt utilizați pe scară largă în diferite aplicații din lumea reală, de exemplu, Proiectarea circuitelor electronice, ruperea codului, procesarea imaginilor și creativitatea artificială.

În acest subiect, vom explica în detaliu algoritmul genetic, inclusiv terminologiile de bază utilizate în algoritmul genetic, cum funcționează, avantajele și limitările algoritmului genetic etc.

Ce este un algoritm genetic?

Înainte de a înțelege algoritmul genetic, să înțelegem mai întâi terminologiile de bază pentru a înțelege mai bine acest algoritm:

Populatie:Populația este submulțimea tuturor soluțiilor posibile sau probabile, care pot rezolva problema dată.Cromozomi:Un cromozom este una dintre soluțiile din populație pentru problema dată, iar colecția de gene generează un cromozom.Gene:Un cromozom este împărțit într-o genă diferită sau este un element al cromozomului.Allele:Alela este valoarea furnizată genei într-un anumit cromozom.Funcția de fitness:Funcția de fitness este utilizată pentru a determina nivelul de fitness al individului în populație. Înseamnă capacitatea unui individ de a concura cu alți indivizi. În fiecare iterație, indivizii sunt evaluați pe baza funcției lor de fitness.Operatori genetici:Într-un algoritm genetic, cel mai bun partener individual pentru a regenera descendenții mai bine decât părinții. Aici operatorii genetici joacă un rol în schimbarea compoziției genetice a următoarei generații.Selecţie

După calcularea aptitudinii fiecărui existent din populație, se folosește un proces de selecție pentru a determina care dintre individualitățile din populație vor ajunge să se reproducă și să producă sămânța care va forma generația viitoare.

Tipuri de stiluri de selecție disponibile

Selectarea roții ruletei Selectarea evenimentului Selecție bazată pe rang

Deci, acum putem defini un algoritm genetic ca algoritm de căutare euristică pentru a rezolva problemele de optimizare. Este un subset de algoritmi evolutivi, care este utilizat în calcul. Un algoritm genetic folosește concepte genetice și de selecție naturală pentru a rezolva probleme de optimizare.

Cum funcționează algoritmul genetic?

Algoritmul genetic funcționează pe ciclul generațional evolutiv pentru a genera soluții de înaltă calitate. Acești algoritmi folosesc diferite operațiuni care fie îmbunătățesc, fie înlocuiesc populația pentru a oferi o soluție de potrivire îmbunătățită.

Practic, implică cinci faze pentru a rezolva problemele complexe de optimizare, care sunt prezentate mai jos:

Inițializare Misiunea de fitness Selecţie Reproducere Încetarea

1. Inițializare

Procesul unui algoritm genetic începe prin generarea setului de indivizi, care se numește populație. Aici fiecare individ este soluția pentru problema dată. Un individ conține sau este caracterizat de un set de parametri numiti Gene. Genele sunt combinate într-un șir și generează cromozomi, care este soluția problemei. Una dintre cele mai populare tehnici de inițializare este utilizarea șirurilor binare aleatorii.

2. Misiunea de fitness

Funcția de fitness este folosită pentru a determina cât de apt este un individ? Înseamnă capacitatea unui individ de a concura cu alți indivizi. În fiecare iterație, indivizii sunt evaluați pe baza funcției lor de fitness. Funcția de fitness oferă fiecărui individ un scor de fitness. Acest scor determină în continuare probabilitatea de a fi selectat pentru reproducere. Cu cât scorul de fitness este mare, cu atât sunt mai multe șanse de a fi selectat pentru reproducere.

3. Selectie

Faza de selecție presupune selecția indivizilor pentru reproducerea descendenților. Toți indivizii selectați sunt apoi aranjați într-o pereche de doi pentru a crește reproducerea. Apoi, acești indivizi își transferă genele către generația următoare.

Există trei tipuri de metode de selecție disponibile, care sunt:

• Selectarea roții ruletei
• Selecția turneului
• Selecția bazată pe rang

4. Reproducerea

După procesul de selecție, în etapa de reproducere are loc crearea unui copil. În acest pas, algoritmul genetic utilizează doi operatori de variație care sunt aplicați populației părinte. Cei doi operatori implicați în faza de reproducere sunt prezentați mai jos:

Crossover:Încrucișarea joacă un rol important în faza de reproducere a algoritmului genetic. În acest proces, un punct de încrucișare este selectat la întâmplare în cadrul genelor. Apoi, operatorul de încrucișare schimbă informațiile genetice ale doi părinți din generația actuală pentru a produce un nou individ reprezentând descendenții.

Genele părinților sunt schimbate între ei până la atingerea punctului de încrucișare. Acești descendenți nou generați sunt adăugați la populație. Acest proces se mai numește și crossover. Tipuri de stiluri crossover disponibile:
• Crossover cu un punct
• Crossover în două puncte
• Crossover cu livrea
• Crossover de algoritmi ereditabili
Mutaţie
Operatorul mutației inserează gene aleatorii în urmași (copil nou) pentru a menține diversitatea în populație. Se poate face prin răsturnarea unor bucăți în cromozomi.
Mutația ajută la rezolvarea problemei convergenței premature și sporește diversificarea. Imaginea de mai jos arată procesul de mutație:
Tipuri de stiluri de mutație disponibile,
Mutație flip bit Mutație gaussiană Mutație de schimb/schimbare

5. Rezilierea

După faza de reproducere, se aplică un criteriu de oprire ca bază pentru terminare. Algoritmul se termină după ce soluția de fitness este atinsă. Acesta va identifica soluția finală ca fiind cea mai bună soluție în populație.

Fluxul de lucru general al unui algoritm genetic simplu

Avantajele algoritmului genetic

• Capacitățile paralele ale algoritmilor genetici sunt cele mai bune.
• Ajută la optimizarea diferitelor probleme, cum ar fi funcții discrete, probleme cu mai multe obiective și funcții continue.
• Oferă o soluție pentru o problemă care se îmbunătățește în timp.
• Un algoritm genetic nu are nevoie de informații derivate.

Limitările algoritmilor genetici

• Algoritmii genetici nu sunt algoritmi eficienți pentru rezolvarea unor probleme simple.
• Nu garantează calitatea soluției finale a unei probleme.
• Calculul repetitiv al valorilor de fitness poate genera unele provocări de calcul.

Diferența dintre algoritmii genetici și algoritmii tradiționali

• Un spațiu de căutare este ansamblul tuturor soluțiilor posibile la problemă. În algoritmul tradițional, se menține un singur set de soluții, în timp ce, într-un algoritm genetic, se pot folosi mai multe seturi de soluții în spațiul de căutare.
• Algoritmii tradiționali au nevoie de mai multe informații pentru a efectua o căutare, în timp ce algoritmii genetici au nevoie de o singură funcție obiectivă pentru a calcula fitness-ul unui individ.
• Algoritmii tradiționali nu pot funcționa paralel, în timp ce algoritmii genetici pot funcționa paralel (calcularea aptitudinii individualităților este independentă).
• O mare diferență în algoritmii genetici este că, mai degrabă să opereze direct pe rezultatele căutării, algoritmii moșteniți operează pe reprezentările (sau randările) lor, adesea denumite cromozomi.
• Una dintre marile diferențe dintre algoritmul tradițional și algoritmul genetic este că nu operează direct pe soluții candidate.
• Algoritmii tradiționali pot genera doar un rezultat în cele din urmă, în timp ce algoritmii genetici pot genera mai multe rezultate optime din generații diferite.
• Algoritmul tradițional nu are mai multe șanse să genereze rezultate optime, în timp ce algoritmii genetici nu garantează generarea de rezultate globale optime, dar există și o mare posibilitate de a obține rezultatul optim pentru o problemă, deoarece utilizează operatori genetici precum Crossover și Mutation.
• Algoritmii tradiționali sunt de natură deterministă, în timp ce algoritmii genetici sunt de natură probabilistică și stocastică.