b'\n_START_ARTICLE_\nGenetinis algoritmas\n_START_PARAGRAPH_\nGenetinis algoritmas (GA) \xe2\x80\x93 algoritmas, paremtas biologijos \xc5\xbeiniomis apie gyvyb\xc4\x97s evoliucij\xc4\x85. GA yra tam tikra evoliucini\xc5\xb3 algoritm\xc5\xb3 klas\xc4\x97, naudojanti gamtoje egzistuojan\xc4\x8dius gyvyb\xc4\x97s evoliucinius mechanizmus: paveld\xc4\x97jim\xc4\x85, mutacij\xc4\x85, nat\xc5\xabrali\xc4\x85j\xc4\x85 atrank\xc4\x85 ir rekombinacij\xc4\x85. Genetiniai algoritmai yra metodas analizuoti duomenis, j\xc5\xb3 d\xc4\x97ka galima rasti apytiksl\xc4\xaf u\xc5\xbeduoties sprendim\xc4\x85. Sprendimas randamas naudojant evoliucin\xc4\xaf cikl\xc4\x85, veikiant\xc4\xaf gamtoje. Genetiniai algoritmai tinka ne visur, ta\xc4\x8diau jais galima rasti palyginti neblogus sprendinius u\xc5\xbeduo\xc4\x8di\xc5\xb3, kuri\xc5\xb3 tikslaus sprendimo algoritmai ne\xc5\xbeinomi._NEWLINE_GA yra priemon\xc4\x97 kompiuteryje atkartoti tam tikros populiacijos (vad. chromosomomis) ir sprendim\xc5\xb3 kandidat\xc5\xb3 (vad. individais) evoliucij\xc4\x85, art\xc4\x97jant prie geriausio u\xc5\xbeduoties sprendimo. Tradici\xc5\xa1kai naudojami dvejetainis kodavimas, sudarytas i\xc5\xa1 0 ir 1, ta\xc4\x8diau galimas ir kitoks kodavimas.\n_START_SECTION_\nAlgoritmas\n_START_PARAGRAPH_\nPasirinkus pradin\xc4\x99 populiacij\xc4\x85, evoliucija prasideda nuo visi\xc5\xa1kai atsitiktini\xc5\xb3 kitim\xc5\xb3. Gavus nauj\xc4\x85 populiacijos kart\xc4\x85 (kandidatus) \xc4\xafvertinamas jos tinkamumas, atrenkamas tam tikras naujos kartos individ\xc5\xb3 skai\xc4\x8dius, pagal atrankos kriterij\xc5\xb3. Atrinktieji individai pakei\xc4\x8diami darant mutacijas arba rekombinacijas ir sukuriama nauja populiacija. V\xc4\x97liau viskas kartojama, atrenkant naujus tinkamiausius individus, sukuriant nauj\xc4\x85 populiacij\xc4\x85. Ciklas kartojamas, kol gaunamas u\xc5\xbeduot\xc4\xaf tenkinantis sprendim\xc4\x85.\n_START_SECTION_\nIstorija\n_START_PARAGRAPH_\nGenetiniai algoritmai kilo studijuojant l\xc4\x85steli\xc5\xb3 mechanizm\xc4\x85. Tyrimus vykd\xc4\x97 John Holland vadovaujama grup\xc4\x97 i\xc5\xa1 JAV Mi\xc4\x8digano universiteto. Apie 1985-sius Ilinojaus universitete \xc4\xafvyko Pirmoji tarptautin\xc4\x97 konferencija skirta genetiniams algoritmams, iki tol genetini\xc5\xb3 algoritm\xc5\xb3 tyrimai buvo daugiausia tik teoriniai. Augant akademiniam susidom\xc4\x97jimui bei vystantis kompiuterijai atsirado galimyb\xc4\x97 praktiniam genetini\xc5\xb3 algoritm\xc5\xb3 \xc4\xafgyvendinimui. 1989 m. JAV laikra\xc5\xa1tis The New York Times i\xc5\xa1spausdino ra\xc5\xa1ytojo John Markoff straipsn\xc4\xaf apie pirm\xc4\x85 komercin\xc4\x99 genetin\xc4\xaf algoritm\xc4\x85 naudojan\xc4\x8di\xc4\x85 program\xc4\x85 Evolver. V\xc4\x97liau atsirado \xc4\xafvairios kompiuterin\xc4\x97s programos skirtos \xc4\xafvairioms sritims. Dabartiniu metu programas naudojan\xc4\x8dias genetinius algoritmus naudoja did\xc5\xbeioji dalis Fortune 500 kompanij\xc5\xb3, i\xc5\xa1spr\xc4\x99sti tvarkara\xc5\xa1\xc4\x8di\xc5\xb3, duomen\xc5\xb3 talpinimo, biud\xc5\xbeeto paskirstymo ir kitas svarbias u\xc5\xbeduotis, kur galima pritaikyti kombinatorin\xc4\xaf optimizavim\xc4\x85.\n_START_SECTION_\nDa\xc5\xbeniausi pritaikymai\n_START_PARAGRAPH_\nYpatingai tinkamos genetini\xc5\xb3 algoritm\xc5\xb3 panaudojimui u\xc5\xbeduotys yra tvarkara\xc5\xa1\xc4\x8di\xc5\xb3 ir grafik\xc5\xb3 sudarymas, tod\xc4\x97l daugyb\xc4\x97 \xc5\xa1ios srities programin\xc4\x97s \xc4\xafrangos paket\xc5\xb3 yra paremta genetiniais algoritmais. Genetiniai algoritmai naudojami in\xc5\xbeinerijoje bei spr\xc4\x99sti globalias optimizavimo problemas._NEWLINE_Genetiniai algoritmai panaudojami ir ten, kur tradiciniai laiptiniai algoritmai (angl. hill climbing algorithms) gali u\xc5\xbestrigti. Genetiniai algoritmai gali b\xc5\xabti naudojami ten, kur u\xc5\xbeduoties strukt\xc5\xabra gan\xc4\x97tinai sud\xc4\x97tinga, d\xc4\x97l rekombinacijos jie nuo minimumo gali jud\xc4\x97ti toliau link teisingo sprendinio, ko nesugeba laiptiniai algoritmai.\n_START_SECTION_\nPritaikymo elementai\n_START_PARAGRAPH_\nGA panaudojimui ie\xc5\xa1kant u\xc5\xbeduoties sprendimo reikalingi du pagrindiniai elementai: tinkama pradin\xc4\x97 duomen\xc5\xb3 strukt\xc5\xabra ir atrankos kriterijus. Algoritmui paprastai reikia, jog u\xc5\xbedavinio sprendimas gal\xc4\x97t\xc5\xb3 b\xc5\xabti pateikiamas kaip duomen\xc5\xb3 strukt\xc5\xabra, kad b\xc5\xabt\xc5\xb3 galima nesunkiai kurti \xc5\xa1ios strukt\xc5\xabros pakeistas kopijas. Antrasis elementas tam tikras atrankos metodas \xe2\x80\x93 funkcija, apra\xc5\xa1anti atrankos kriterij\xc5\xb3. Jos d\xc4\x97ka galima taikyti kiekybinius atrankos kriterijus, atrenkant geresnius ir blogesnius sprendinius.\n_START_SECTION_\nGA pritaikymo pavyzdys\n_START_PARAGRAPH_\nPavyzd\xc5\xbeiui, u\xc5\xbeduotis yra kuo didesn\xc4\x99 mas\xc4\x99 sutalpinti \xc4\xaf krep\xc5\xa1\xc4\xaf, jo nesupl\xc4\x97\xc5\xa1ius. Sprendimas gali b\xc5\xabti vaizduojamas kaip bit\xc5\xb3 eilut\xc4\x97, kur kiekvienas bitas rei\xc5\xa1kia atskir\xc4\x85 krovin\xc4\xaf (turint\xc4\xaf savo mas\xc4\x99), o bito reik\xc5\xa1m\xc4\x97 (0 arba 1) rei\xc5\xa1kia buvo krovinys \xc4\xafd\xc4\x97tas \xc4\xaf krep\xc5\xa1\xc4\xaf ar ne. Sprendimo tinkamum\xc4\x85 parodo gauta bendra mas\xc4\x97. Kuo didesn\xc4\x97 mas\xc4\x97 gaunama susumavus visas \xc4\xafd\xc4\x97t\xc5\xb3 krovini\xc5\xb3 mases, tuo tinkamesnis sprendimas.\n_START_SECTION_\nGA prad\xc5\xbeia\n_START_PARAGRAPH_\nPrad\xc5\xbeioje daug individuali\xc5\xb3 sprendim\xc5\xb3 yra atsitiktinai generuojami suformuojant atsitiktin\xc4\x99 pradin\xc4\x99 populiacij\xc4\x85. Populiacijos dydis pasirenkamas pagal u\xc5\xbeduoties sud\xc4\x97tingum\xc4\x85. Da\xc5\xbeniausiai populiacij\xc4\x85 sudaro keletas \xc5\xa1imt\xc5\xb3 ar net t\xc5\xabkstan\xc4\x8di\xc5\xb3 galim\xc5\xb3 sprendim\xc5\xb3. Tradici\xc5\xa1kai populiacija generuojama atsitiktinai, apimant didel\xc4\xaf sprendini\xc5\xb3 paie\xc5\xa1kos diapazon\xc4\x85. Kartais nubr\xc4\x97\xc5\xbeiamos tam tikros ribos, kuriose sprendinys tik\xc4\x97tinai tur\xc4\x97t\xc5\xb3 b\xc5\xabti, tokiu b\xc5\xabdu sutrumpinamas paie\xc5\xa1kos laikas.\n_START_SECTION_\nAtranka\n_START_PARAGRAPH_\nI\xc5\xa1 populiacijos atrenkama dalis tinkamiausi\xc5\xb3 sprendini\xc5\xb3 (s\xc4\x97kmingiausi\xc5\xb3 \xe2\x80\x9epalikuoni\xc5\xb3\xe2\x80\x9c), i\xc5\xa1 kuri\xc5\xb3 bus kuriama naujoji populiacija. Atrankos kriterij\xc5\xb3 apra\xc5\xa1o tinkamumo funkcija, kuri ir lemia atrank\xc4\x85. Da\xc5\xbeniausiai taikomas metodas, kai i\xc5\xa1 visos populiacijos atrenkami labiausiai tinkami sprendiniai. Ta\xc4\x8diau yra ir kitas atrankos metodas, kurio metu yra vertinami tik atsitiktinai populiacijos sprendiniai. \xc5\xa0is, antrasis metodas, yra ma\xc5\xbeiau efektyvus nei pirmasis, kadangi \xc5\xa1iuo metodu tiksliausio sprendimo paie\xc5\xa1ka trunka \xc5\xbeymiai ilgiau._NEWLINE_Dauguma atrankos funkcij\xc5\xb3 yra tikimybin\xc4\x97s ir sukurtos taip, kad atrinkt\xc5\xb3 tinkamais ir nedidel\xc4\x99 dal\xc4\xaf sprendini\xc5\xb3, kuri yra ma\xc5\xbeiau tinkama. Tokiu b\xc5\xabdu u\xc5\xbetikrinim\xc4\x85, kad i\xc5\xa1likt\xc5\xb3 \xc4\xafvairov\xc4\x97 ir i\xc5\xa1vengiama pirmalaik\xc4\x97s konvergencijos bei nukrypimo \xc4\xaf netinkamus sprendinius. Da\xc5\xbeniausi ir daugiausiai i\xc5\xa1studijuoti atrankos metodai: rulet\xc4\x97s ir turnyrin\xc4\x97 atranka.\n_START_SECTION_\nElito atranka\n_START_PARAGRAPH_\nIgnoruojantis \xc4\xafprast\xc4\x85 eig\xc4\x85, ta\xc4\x8diau labai efektyvus yra variantas, kai konstruojant nauj\xc4\x85 populiacij\xc4\x85, leid\xc5\xbeiama keliems s\xc4\x97kmingiausiems organizmams (sprendiniams) pereiti \xc4\xaf nauj\xc4\x85 populiacijai visai nepakitus. \xc5\xa0i strategija vadinama elito atranka (angl. elitist selection).\n_START_SECTION_\nMutacija ir rekombinacija\n_START_PARAGRAPH_\nAntrosios ir kit\xc5\xb3 populiacij\xc5\xb3 k\xc5\xabrim\xc4\x85 sudaro genetini\xc5\xb3 mechanizm\xc5\xb3: rekombinacijos ir mutacijos \xe2\x80\x93 pritaikymas. Rekombinacij\xc4\x85 ir mutacija yra biologini\xc5\xb3 mechanizm\xc5\xb3 analogai._NEWLINE_Kiekvieno naujo sprendinio suk\xc5\xabrimui i\xc5\xa1 populiacijos imama pora sprendini\xc5\xb3 \xe2\x80\x9et\xc4\x97v\xc5\xb3\xe2\x80\x9c, kurie sukry\xc5\xbeminami ir mutacijos ar rekombinacijos b\xc5\xabdu gaunamas sprendinys \xe2\x80\x9evaikas\xe2\x80\x9c. Toliau imama kita \xe2\x80\x9et\xc4\x97v\xc5\xb3\xe2\x80\x9c pora ir v\xc4\x97l sukuriamas \xe2\x80\x9evaikas\xe2\x80\x9c ir taip t\xc4\x99siama kol pasiekiamas tam tikras naujos kartos individ\xc5\xb3 skai\xc4\x8dius, sukuriama pilna nauja sprendini\xc5\xb3 populiacija._NEWLINE_Galiausiai po \xc5\xa1i\xc5\xb3 proces\xc5\xb3 nauj\xc4\x85sias kartas sudarys individai, kuri\xc5\xb3 chromosomos (sandara) yra visi\xc5\xa1kai skirtinga nei pradin\xc4\x97s populiacijos. Bendras populiacijos tinkamumo vidurkis taip pat pakils, kadangi i\xc5\xa1liks tik geriausi individai (sprendiniai) ir dalis ma\xc5\xbeiau tinkam\xc5\xb3 individ\xc5\xb3 (prie\xc5\xbeastys pamin\xc4\x97tos prie\xc5\xa1 tai skyriuje \xe2\x80\x9eAtranka\xe2\x80\x9c.)\n_START_SECTION_\nMutacija\n_START_PARAGRAPH_\nMutacija yra b\xc5\xabdas genetiniuose algoritmuose i\xc5\xa1laikyti genetin\xc4\x99 \xc4\xafvairov\xc4\x99. Mutacija naudojama GA yra biologin\xc4\x97s mutacijos analogas, kadangi jos mechanizmas buvo kuriamas pagal biologin\xc4\x99 mutacij\xc4\x85. Mutacijos padeda i\xc5\xa1vengti populiacijos chromosom\xc5\xb3 supana\xc5\xa1\xc4\x97jimo (lokalaus konvergavimo), o tai vest\xc5\xb3 \xc4\xaf evoliucijos sul\xc4\x97t\xc4\x97jim\xc4\x85 ar net visi\xc5\xa1k\xc4\x85 stagnacij\xc4\x85. Tai taip pat paai\xc5\xa1kina, kod\xc4\x97l GA sistemos vengia naudoti tok\xc4\xaf atrinkimo b\xc5\xabd\xc4\x85, kai atrenkami vien tik geriausi._NEWLINE_Klasikin\xc4\xaf mutacij\xc5\xb3 operatoriaus veikim\xc4\x85 sudaro atsitiktinai generuojami skai\xc4\x8diai, kurie nurodo \xc4\xafvyks ar ne\xc4\xafvyks mutacij\xc4\x85 tam tikrai duomen\xc5\xb3 daliai.\n_START_SECTION_\nSteb\xc4\x97jimai\n_START_PARAGRAPH_\nYra keletas pagrindini\xc5\xb3 steb\xc4\x97jim\xc5\xb3 susijusi\xc5\xb3 su GA. Dauguma GA problem\xc5\xb3 kyla d\xc4\x97l didelio j\xc5\xb3 sud\xc4\x97tingumo.\n_START_SECTION_\nLokalus konvergavimas\n_START_PARAGRAPH_\nGA gali tur\xc4\x97ti tendencij\xc4\x85 konverguoti link lokalaus (riboto) sprendimo, vietoje globalaus (visa apiman\xc4\x8dio) tinkamiausio sprendimo. \xc5\xa0ios problemos tik\xc4\x97tinumas priklauso nuo architekt\xc5\xabrin\xc4\x97s tinkamumo formos. Tam tikr\xc5\xb3 problem\xc5\xb3 sprendimai lengviau krypsta link globalaus sprendinio, kitoms funkcijos lengviau rasti vietin\xc4\xaf tinkamiausi\xc4\x85 sprendin\xc4\xaf._NEWLINE_J\xc4\x85 suma\xc5\xbeinti ar net visai i\xc5\xa1spr\xc4\x99sti gali skirtingos atrankos funkcijos, arba metodai naudojami i\xc5\xa1laikyti kuo \xc4\xafvairiapusi\xc5\xa1kesn\xc4\x99 sprendini\xc5\xb3 populiacij\xc4\x85.\n_START_SECTION_\nMutacija ar rekombinacija?\n_START_PARAGRAPH_\nAtranka yra pats svarbiausias veiksnys, ta\xc4\x8diau yra dvi vyraujan\xc4\x8dios nuomon\xc4\x97s d\xc4\x97l to kas svarbiau mutacija ar rekombinacija. Rekombinacij\xc4\x85 palaikantieji teigia, kad ji svarbiausia, o mutacija tik u\xc5\xbetikrinanti, kad neb\xc5\xabt\xc5\xb3 prarastas sprendimo potencialas. Kiti teigia, kad rekombinacija reikalinga tik tam, kad paskleist\xc5\xb3 naujoves, sukurtas mutacij\xc5\xb3. Ir tam kad, nepastoviose populiacijose rekombinacija yra tapati didelei mutacijai (kuri da\xc5\xbeniausiai b\xc5\xabna katastrofi\xc5\xa1ka). Da\xc5\xbeniausiai GA greitai lokalizuoja ger\xc4\x85 sprendim\xc4\x85, net ir sud\xc4\x97tingose paie\xc5\xa1kos srities vietose.\n_START_SECTION_\nOptimizavimo u\xc5\xbeduotys\n_START_PARAGRAPH_\nSpecifin\xc4\x97ms optimizavimo u\xc5\xbeduotims, paprastesni optimizavimo algoritmai gali rasti geresni sprendim\xc4\x85 nei genetiniai algoritmai, jeigu b\xc5\xabt\xc5\xb3 duotas tas pats skai\xc4\x8diavimams laikas. GA naudotojai gali pam\xc4\x97ginti papildomai naudoti kitus algoritmus, kadangi GA negali efektyviai spr\xc4\x99sti t\xc5\xb3 u\xc5\xbeduo\xc4\x8di\xc5\xb3, kur negalima nustatyti, kuris variantas yra geresnis ar blogesnis, tod\xc4\x97l negali konverguoti link tam tikro geriausio sprendimo.\n_START_SECTION_\nParametr\xc5\xb3 suderinimas\n_START_PARAGRAPH_\nVisoms ma\xc5\xa1inoms (programoms), kurios ie\xc5\xa1ko u\xc5\xbeduo\xc4\x8di\xc5\xb3 sprendim\xc5\xb3 yra b\xc5\xabtina teisingai suderinti parametrus, b\xc5\xabtinus geram sprendimo paie\xc5\xa1kos veikimui, atsi\xc5\xbevelgiant \xc4\xaf u\xc5\xbeduoties sud\xc4\x97tingum\xc4\x85 ir tip\xc4\x85. Reikia suderinti \xc5\xa1iuos parametrus: mutacijos parametr\xc4\x85 (tikimyb\xc4\x99, dyd\xc4\xaf), rekombinacijos parametr\xc4\x85 (tikimyb\xc4\x99, dyd\xc4\xaf), populiacijos dyd\xc4\xaf. Pernelyg ma\xc5\xbeas mutacij\xc5\xb3 da\xc5\xbenumas gali vesti link genetinio dreifo ar pirmalaik\xc4\x97s konvergencijos \xc4\xaf lokal\xc5\xb3 sprendin\xc4\xaf. Jei mutacij\xc5\xb3 parametras yra per didelis, gali vesti link ger\xc5\xb3 sprendim\xc5\xb3 praradim\xc5\xb3. Yra m\xc4\x97ginama nustatyti \xc5\xa1iuos r\xc4\x97\xc5\xbeius, ta\xc4\x8diau kol kas tai daroma tik teori\xc5\xa1kai. Kitas nema\xc5\xbeiau svarbus veiksnys yra atrankos funkcijos greitis ir efektyvumas, nuo to priklauso algoritmo darbas. Siekiama, kad atrankos funkcijos greitis ir efektyvumas b\xc5\xabt\xc5\xb3 kuo didesni.\n_START_SECTION_\nVariantai\n_START_PARAGRAPH_\nPapras\xc4\x8diausias algoritmo duomen\xc5\xb3 strukt\xc5\xabros variantas, kai kiekvien\xc4\x85 chromosom\xc4\x85 i\xc5\xa1rei\xc5\xa1kiama bit\xc5\xb3 eilute. Da\xc5\xbenai parametrai u\xc5\xbera\xc5\xa1omi integer (sveikaisiais) tipo skai\xc4\x8diais, ta\xc4\x8diau galima juos u\xc5\xbera\xc5\xa1yti ir real (slankiojan\xc4\x8dio kablelio, de\xc5\xa1imtainiai ir kt.) tipo skai\xc4\x8diais. Algoritmo pagrindas yra mutacijos ir rekombinacijos mechanizmai atliekami bit\xc5\xb3 lygyje. Kiti duomen\xc5\xb3 strukt\xc5\xabros variantai: chromosoma yra \xc5\xbeymima skai\xc4\x8di\xc5\xb3 s\xc4\x85ra\xc5\xa1u, kuris indeksuojamas instrukcij\xc5\xb3 lentel\xc4\x97je, ta\xc5\xa1kais susietais su s\xc4\x85ra\xc5\xa1u, objektais ir kitomis duomen\xc5\xb3 strukt\xc5\xabromis. Rekombinacija ir mutacija atliekamos taip, kad b\xc5\xabt\xc5\xb3 paisoma duomen\xc5\xb3 strukt\xc5\xabros element\xc5\xb3 rib\xc5\xb3. Daugumai duomen\xc5\xb3 tip\xc5\xb3 galima sukurti specifinius operatorius. Skirtingi chromosom\xc5\xb3 duomen\xc5\xb3 tipai veikia nevienodai sprend\xc5\xbeiant skirting\xc5\xb3 sri\xc4\x8di\xc5\xb3 u\xc5\xbeduotis._NEWLINE_Kai bit\xc5\xb3 eilut\xc4\x97s naudoja integer tipo duomenis, da\xc5\xbenai naudojamas Gr\xc4\x97jaus kodavimas (ang. Gray coding) \xe2\x80\x93 specifinis dvejetainio kodo i\xc5\xa1d\xc4\x97stymas. \xc5\xa0iuo kodavimu lengvai padaromi ma\xc5\xbei pakeitimai, sukelti mutacij\xc5\xb3 ir rekombinacij\xc5\xb3. Tai taip pat padeda i\xc5\xa1vengti pirmalaikio konvergavimo, kai tur\xc4\x97t\xc5\xb3 \xc4\xafvykti tuo pat metu daugyb\xc4\x97 mutacij\xc5\xb3 (ar rekombinacij\xc5\xb3), kad b\xc5\xabt\xc5\xb3 pasiektas pokytis link geresnio sprendimo radimo._NEWLINE_Kiti b\xc5\xabdai siejami su masyvais, naudojan\xc4\x8diais real tipo skai\xc4\x8dius, kuriais i\xc5\xa1rei\xc5\xa1kiama chromosoma. Teori\xc5\xa1kai tur\xc4\x97t\xc5\xb3 b\xc5\xabti, kad kuo ma\xc5\xbeesnis alfabetas, tuo geresnis veikimas ir rezultatas, ta\xc4\x8diau i\xc5\xa1 tikr\xc5\xb3j\xc5\xb3 yra atvirk\xc5\xa1\xc4\x8diai, kadangi geriausi rezultatai gaunami naudojant b\xc5\xabtent real tipo chromosomas.\n_START_SECTION_\nParalelinis \xc4\xafgyvendinimas\n_START_PARAGRAPH_\nParalelinis GA \xc4\xafgyvendinimo gali b\xc5\xabti du variantai. Prastai padarytas paralelinis genetinis algoritmas apima populiacijas, esan\xc4\x8dias kiekviename kompiuterio ta\xc5\xa1ke ir migracij\xc4\x85 tarp j\xc5\xb3. Gerai padarytas paralelinis genetinis algoritmas apima individ\xc4\x85 kiekviename procesoriaus ta\xc5\xa1ke, kuris s\xc4\x85veikauja su kitais \xe2\x80\x9ekaimyniniais\xe2\x80\x9c individais, pasirinkdamas ir daugindamasis. Kiti variantai kai GA naudojamas tinklinio optimizavimo u\xc5\xbeduotims prideda papildomas laiko ar netvarkos priklausomybes atrankos funkcijoje.\n_START_SECTION_\nGiminingos metodikos\n_START_PARAGRAPH_\nGenetinis programavimas (angl. Genetic programming) \xe2\x80\x93 naudojamas med\xc5\xbeio tipo duomen\xc5\xb3 strukt\xc5\xabrose, vaizduojant kompiuterio program\xc5\xb3 adaptacij\xc4\x85, vietoje s\xc4\x85ra\xc5\xa1o ar masyvo, kur\xc4\xaf da\xc5\xbeniausiai naudoja genetiniai algoritmai. Genetinio programavimo algoritmai da\xc5\xbeniausiai reikalauja ilgesnio veikimo laiko, ta\xc4\x8diau j\xc5\xb3 didesnis galingumas. Jie gali b\xc5\xabti pritaikomi spr\xc4\x99sti tuos u\xc5\xbedavinius, kuriuos spr\xc4\x99sti sunkiai pavyksta su genetiniais algoritmais._NEWLINE_S\xc4\x85veikaujantys genetiniai algoritmai (angl. Interactive genetic algorithms) \xe2\x80\x93 genetiniai algoritmai, kurie naudoja \xc5\xbemogaus \xc4\xafvertinim\xc4\x85. Jie naudojami srityse, kur sunku apra\xc5\xa1yti atrankos funkcij\xc4\x85. Pavyzd\xc5\xbeiui, evoliucionuojantys vaizdai, muzika, kitos menin\xc4\x97s formos, kurios priklauso nuo naudotoj\xc5\xb3 estetinio pasirinkimo._NEWLINE_angl. Simulated annealing (SA) \xe2\x80\x93 siejami su globaliais optimizavimo metodais, kurie keliauja paie\xc5\xa1kos erdve, bandydami \xc4\xafvairias mutacijas ir individualius sprendimus. Priimama ta mutacija kuri padidina veikimo efektyvum\xc4\x85. Mutacija, kuri ma\xc5\xbeina efektyvum\xc4\x85 priimama tikimybi\xc5\xa1kai priklausomai nuo tinkamumo pasiskirstymo, da\xc5\xbeniausiai ma\xc5\xbeinant temperat\xc5\xabros parametr\xc4\x85. Egzistuoja skirtingi prioritet\xc5\xb3 vystymo keliai: pagal vien\xc4\x85 siekiama suvartoti kuo ma\xc5\xbeiau energijos, pagal kit\xc4\x85 siekiama did\xc5\xbeiausio sprendimo tinkamumo. SA gali b\xc5\xabti naudojami GA viduje, papras\xc4\x8diausiai pradedama naudojant didesn\xc4\xaf mutacij\xc5\xb3 da\xc5\xben\xc4\xaf, kuris v\xc4\x97liau pagal grafik\xc4\x85 ma\xc5\xbeinamas._NEWLINE_Tabu tyrimai (angl. Tabu search, (TS)) \xe2\x80\x93 pana\xc5\xa1\xc5\xabs \xc4\xaf SA, abiejuose ie\xc5\xa1koma sprendimo keliaujant paie\xc5\xa1kos erdve ir bandomos \xc4\xafvairios mutacijas bei individual\xc5\xabs sprendimai. SA generuoja vien\xc4\x85 mutavus\xc4\xaf sprendim\xc4\x85, o TS generuoja daugyb\xc4\x99 mutavusi\xc5\xb3 sprendini\xc5\xb3, bet ima ma\xc5\xbeiausia tinkamum\xc4\x85 (sveikum\xc4\x85) pademonstravus\xc4\xaf sprendin\xc4\xaf. Tam kad b\xc5\xabt\xc5\xb3 i\xc5\xa1vengta cikli\xc5\xa1kumo u\xc5\xbetikrinama didesn\xc4\x97 jud\xc4\x97jimo laisv\xc4\x97 sprendini\xc5\xb3 erdv\xc4\x97je. Tabu s\xc4\x85ra\xc5\xa1\xc4\x85 sudaro daliniai arba pilni sprendiniai. Yra draud\xc5\xbeiama imti sprendin\xc4\xaf i\xc5\xa1 tabu s\xc4\x85ra\xc5\xa1o, kuris atnaujinamas vykstant sprendinio paie\xc5\xa1kai._NEWLINE_Skruzd\xc4\x97li\xc5\xb3 kolonijos optimizavimas (angl. Ant colony optimization) naudoja daug skruzd\xc4\x97li\xc5\xb3 (agent\xc5\xb3), kurios keliauja sprendim\xc5\xb3 erdv\xc4\x97je ir ie\xc5\xa1ko produktyviausi\xc5\xb3 viet\xc5\xb3. Skruzd\xc4\x97li\xc5\xb3 kolonijos optimizavimas gali b\xc5\xabti naudojamas spr\xc4\x99sti u\xc5\xbedaviniams, kurie n\xc4\x97ra global\xc5\xabs ar neturi naujausios informacijos, kurios reikia kitiems metodams, tod\xc4\x97l gali b\xc5\xabti pritaikytas ten kur kiti negali veikti._NEWLINE_Memetitinis algoritmas (angl. Memetic algorithm, MA) \xe2\x80\x93 terminas, kur\xc4\xaf naudoja mokslininkai \xc4\xafvardindami gentini\xc5\xb3 algoritmus, kurie yra kombinuoti su kitomis lokali\xc5\xb3 paie\xc5\xa1k\xc5\xb3 formomis, tokiomis kaip SA. Kai kurie mokslininkai juos \xc4\xafvardija kaip genetini\xc5\xb3 algoritm\xc5\xb3 ir paralelini\xc5\xb3 genetini\xc5\xb3 algoritm\xc5\xb3 hibridus. Memetiniai algoritmai yra efektyvesni u\xc5\xbe genetinius algoritmus ie\xc5\xa1kant sprendimo kai kuriose srityse.'