Ģenētiskais algoritms

Ģenētiskā algoritma evolūcionārā loģika attēlota

Ģenētiskais algoritms ir pie evolucionārās skaitļošanas metodēm pieskaitāms optimizēšanas algoritms. Tas ir heiristiskas dabas algoritms un tiek pielietots gan precīzu, gan tuvinātu risinājumu meklēšanai.

Algoritma pamatā ir esošā risinājuma iteratīva uzlabošana, taču viena risinājuma vietā tiek izmantota risinājumu kopa, kuru, iedvesmojoties no bioloģijas, sauc par populāciju. Populācijas locekļus nereti sauc par risinājuma kandidātiem un par indivīdiem. Risinājumu kopa iteratīvi tiek uzlabota, izpildot ar šo populāciju dabiskajai evolūcijai līdzīgas darbības: indivīdu pārošanās, mutēšana un cīņa par izdzīvošanu.

Algoritma pseidokods

1. Sākotnējās populācijas izveidošana.
2. Kamēr neizpildās beigšanas nosacījumi:
   1. Atlasa indivīdus pārošanai.
   2. Sapāro indivīdus un rada jaunus pēcnācējus.
   3. Atlasa indivīdus atmešanai no populācijas.
3. Atgriež labāko vai vairākus labākos indivīdus no populācijas.

Algoritma 2. soļa katra izpilde tiek saukta par vienu paaudzi. Algoritmu beidz izpildīt vai nu tad, kad iegūts indivīds, kas atbilst pieņemama risinājuma nosacījumiem, vai, kad algoritms izpildīts noteiktu paaudžu skaitu.

Sākotnējo populāciju var veidot gan no nejauši ģenerētiem indivīdiem, gan no mērķtiecīgi ģenerētiem indivīdiem.

Noteikumus, kas nosaka indivīdu atlasi pārošanai un atmešanai sauc par atlases operatoriem (angļu: selection operators), bet noteikumus, kā pārot indivīdus un, iespējams, piemērot tiem mainību, sauc par mainības operatoriem (angļu: variation operators).

Svarīgs algoritma atribūts ir indivīdu reprezentācija. Vēsturiski pirmā pielietotā reprezentācija bija binārā virkne, taču tagad tiek izmantoti arī veselo skaitļu un reālo skaitļu masīvi.

Literatūra

• Eiben, A. E., Smith, J. E., Introduction to Evolutionary Computing. Springer, 2003.