Aplicabilitatea algoritmului genetic în lumea reală

 

Algoritmul genetic reprezintă un tip de algoritm de optimizare. Este folosit pentru a găsi soluția optimă la o anumită problemă de calcul, și utilizează o funcție specială. Algoritmul imită procesele biologice de reproducere și selecție naturală pentru soluțiile cele mai potrivite. [1] Acest algoritm este mult mai eficient decât algoritmul de căutare aleatorie și cel de căutare cu forță brută. [2]

Deoarece algoritmii genetici sunt concepuți pentru a simula un proces biologic, o mare parte din terminologie este împrumutată din biologie. Componentele de bază pentru aproape toți algoritmii genetici sunt:

 

1)     o populație de cromozomi

2)     o funcție de fitness pentru optimizare

3)     selectarea cromozomilor care se vor reproduce

4)     încrucișarea pentru a produce următoarea generație de cromozomi

5)     mutația aleatorie a cromozomilor în noua generație.

 

Algoritmul genetic este utilizat în diferite aplicații și domenii, cum ar fi programarea automată, modelarea economică, sistemul imunitar uman, și altele.

Un grup de kazaci a propus ideea de translație a textului scris de mână, dintr-un set de date mare, în format electronic. Motivul principal pentru care aceștia au creat o astfel de aplicație constă în aceea că taxele, chestionarele, răspunsurile la examene sau alte documente sunt scrise de mână. Pentru a descifra mai ușor cele scrise, se face o conversie din textul scris de mână în contextul digital. [3] Kazacii au propus un algoritm genetic pentru segmentarea liniilor din fișierul text și a cuvintelor din propoziții pe baza enumerării aleatoare a unui parametru.

Și la problema vânzătorului călător se aplică algoritmul genetic. La această problemă se presupune că există un vânzător călător care trebuie să viziteze n orașe urmând cel mai scurt traseu posibil. Se vizitează fiecare oraș exact o dată, apoi se revine la orașul inițial parcurgându-se o altă rută sau aceeași rută. Astfel, cromozomii pentru algoritmul genetic vor fi diferitele permutări ale numerelor întregi de la 1 la n. Se implementează, ulterior, o funcție de potrivire a orașului (se privesc distanțele dintre orașe) pentru a găsi calea cea mai scurtă de la orașul o_i la orașul o_j.

Algoritmul genetic se mai folosește și pentru repararea sateliților GEO conform misiunii programate. [4] Fiecare navă spațială de întreținere trebuie să se apropie de sateliții țintă pentru a efectua misiuni de reparare cu combustibil limitat. Trebuie comunicată secvența optimă de întreținere a navei și ora de întâlnire a fiecărei nave spațiale la un anumit punct, pentru a minimiza costul total de combustibil al tuturor navelor spațiale, obținând, totuși, repararea tuturor sateliților țintă.

Algoritmii genetici sunt utilizați de companii pentru a optimiza programele și proiectează produse care variază de la sateliți și probleme astronautico-științifice până la mici cipuri de calculator și chiar conținutul medicamentelor.

Spre exemplu, laboratorul Național Los Alamos a folosit algoritmul pentru a analiza datele de la sateliți și pentru a crea efecte realiste pentru filmele precum The Lord of the Rings sau Troy. [5] Cu siguranță, algoritmul nu este ușor de implementat și necesită cunoștințe aprofundate din domeniul informaticii și al geneticii, și din domeniul în care se săvârșește proiectul sau operațiunea.

 

Bibliografie

[1] Goldberg, D. E., & Holland, J. H. (1988). Genetic algorithms and machine learning.

[2] Kinnear, K. E., Langdon, W. B., Spector, L., Angeline, P. J., & O'Reilly, U. M. (Eds.). (1994). Advances in genetic programming (Vol. 3). MIT press.

[3] Toiganbayeva, N., Kasem, M., Abdimanap, G., Bostanbekov, K., Abdallah, A., Alimova, A., & Nurseitov, D. (2021). KOHTD: Kazakh Offline Handwritten Text Dataset. 

[4] Han, P., Guo, Y., Li, C., Zhi, H., & Lv, Y. (2021). GEO satellites. 

[5] Mitchell, M. (2009). Complexity: A guided tour. Oxford University Press.