Įvadas
1. Tradicinių technologijų trūkumai
Sprendžiant praktinius uždavinius, daugelis klasikinių metodų yra
neefektyvūs. Taip yra todėl, kad neįmanoma baigtinių parametrų dėka
pakankamai realiai aprašyti tikrovę arba parinktas modelis reikalauja labai
daug laiko ir resursų. Pavyzdžiui, optimalus investicijų paskirstymas:
1. Realiame uždavinyje nė viena iš funkcijų nėra žinoma tiksliai.
Yra tik apytiksliai žinomos kai kurios reikšmės.
2. Algoritmas yra panaudojamas tik tuo atveju, jei funkcija yra
tiesinė. Iš tikrųjų ši sąlyga nėra išpildoma. Net jei mes
aproksimuosime tiesinę funkciją, mūsų sprendinys bus labai
nutolęs nuo tikrojo.
3. Jei nors viena funkcija yra netiesinė, tai naudojami perrinkimo
arba gradientinio nuolydžio metodai. Tačiau jie turi savo
trūkumų, kurie bus aprašyti žemiau.
2. Naujos technologijos
Per paskutiniuosius 10 metų dėl tradicinių technologijų trūkumų
aktyviai vystosi naujo tipo analitinės sistemos. Jų pagrindas yra dirbtinio
intelekto technologijos, imituojančios procesus, vykstančius gamtoje,
tokius, kaip smegenų neuronai ir natūrali atranka.
Populiariausi ir labiausiai patikrinti iš technologijų yra
neuroniniai tinklai ir genetiniai algoritmai. Pirmos tokio tipo programos
atsirado 80-tais metais ir plačiai paplito kitose šalyse.
Neuroniniai tinklai tai savotiška smegenų imitacija, todėl jų dėka
lengvai sprendžiami įvairūs „netikslūs“ uždaviniai – tai balso, vaizdo,
ranka rašyto teksto, klasifikacijų atpažinimas. Tokiuose uždaviniuose, kur
tradicinės technologijos bejėgės, neuroniniai tinklai yra vienintelė
išeitis. Ward Systems Group duomenimis, 1998 metais programos, parašytos
neuroninių tinklų pagrindu, buvo naudojamos daugiau nei 500 stambiose
pasaulio kompanijose iš Fortune 1000 sąrašo.
Genetiniai algoritmai – tai speciali technologija, naudojama
optimaliems sprendimams rasti. Ji efektyviai naudojama įvairiose mokslo ir
kitose srityse. Čia yra naudojama natūralios atrankos(evoliucijos Žemėje)
idėja, todėl ji ir vadinama genetine. Genetiniai algoritmai dažnai
naudojami kartu su neuroniniais tinklais, todėl yra labai lankstūs, greiti
ir efektyvūs analizuojant duomenis.
Genetiniai algoritmai
1. Natūrali atranka gamtoje
Evoliucijos teorija tvirtina, kad kiekviena biologinė rūšis tikslingai
vystosi ir keičiasi tam, kad geriausiai prisitaikytų prie aplinkos.
Evoliucijos eigoje dauguma vabzdžių ir žuvų rūšių įgavo apsauginę spalvą,
žmogus tapo sudėtingiausios nervų sistemos savininku. Galima pasakyti, kad
evoliucija – tai visų gyvų organizmų optimizavimosi procesas.
Išnagrinėsime, kokiais būdais gamta sprendžia šį optimizavimosi uždavinį.
Pagrindinis evoliucijos mechanizmas – tai natūrali atranka. Jos esmė
tame, kad labiau prisitaikę turi daugiau šansų išlikti ir palikti po savęs
palikuonis. Genetinės informacijos perdavimo dėka (genetinis paveldėjimas)
palikuonys paveldi būdingus tėvų bruožus. Todėl stiprių individų
palikuonys tap pat santykinai gerai bus prisitaikę, o jų dalis bendroje
masėje augs. Po kelių dešimčių ar šimtų kartų duotos individų rūšies
vidutinis prisitaikymas žymiai išaugs.
Kad suprasti genetinių algoritmų veikimo principus, panagrinėkime,
kaip yra sudarytas genetinio paveldėjimo mechanizmas gamtoje. Kiekvienoje
gyvūno ląstelėje yra visa genetinė informacija apie šį individą. Ši
informacija užrašyta labai ilgų molekulių DNR rinkinių pavidalu. Kiekviena
DNR molekulė – tai grandinėlė, susidedanti iš keturių rūšių nukleotido
molekulių, kurios žymimos A, T, C ir G raidėmis. Informacija užrašoma
nukleotidų rinkiniu DNR molekulėje. Tokiu būdu individo genetinis kodas –
labai, labai ilga eilutė simbolių, kur naudojamos iš viso 4 raidės. Gyvūno
ląstelėje kiekviena DNR molekulė apsupta plėvele – ir toks susidarymas
vadinamas chromosoma.
Kiekvienas įgimtas individo bruožas (akių spalva, paveldėtos ligos,
plaukų tipas ir t.t.) koduojamas tam tikroje chromosomos dalyje, kuri
vadinama šios savybės genu. Pvz.: akių spalvos genas saugo informaciją,
koduojančią tam tikrą akių spalvą. Įvairios genų reikšmės vadinamos
alleliais(allel).
Gyvūnams dauginantis, vyksta dviejų tėvų ląstelių sąveika, ir jų DNR
susijungia, sudarydami palikuonio DNR. Pagrindinis sąveikos būdas –
krossoveris (cross-over, kryžminimas). Vykstant kryžminimuisi, tėvų DNR
dalijasi į dvi dalis ir apsikeičia savo pusėmis.
Paveldint galimos visokios mutacijos, vykstančios dėl radioaktyvaus ir
kitų poveikių, kurių pasekoje gali pasikeisti kai kurie vieno iš tėvų genai
ląstelėse. Pasikeitę genai yra perduodami palikuoniui ir todėl atsiranda
naujos savybės. Jeigu šios
naujos savybės yra naudingos, jos,
greičiausiai, išlieka duotoje rūšyje. Todėl įvyks šuolingas prisitaikymo
padidėjimas šioje rūšyje.
2. Kas yra genetinis algoritmas
Tegul turime kažkokią sudėtingą funkciją, priklausančią nuo daugelio
nežinomųjų. Reikia rasti tokias nežinomųjų reikšmes, kurioms esant funkcija
įgyja maksimalias reikšmes. Tokio pobūdžio uždaviniai yra vadinami
maksimizavimo ir praktikoje pasitaiko labai retai.
Vienas iš akivaizdžių pavizdžių yra investicijų paskirstimo uždavinys.
Šiame uždavinyje nežinuomieji yra investicijų kiekiai ir kiekvienas
projektas (10 nežinomųjų), o funkcija, kurią reikia maksimizuoti – suminės
investuotojo pajamos. Taip pat yra žinomos minimalus ir maksimalus
investicijų kiekis į kiekvieną projektą.
Pabandysime išspręsti šį uždavinį, taikant natūralų optimizavimo būdą.
Peržiūrėsime kiekvieną investavimo variantą kaip individą, o šio varianto
pelningumą – kaip individo sugebėjimą prisitaikyti. Tada evoliucijos
procese (jei sugebėsime jį organizuoti) individų gebėjimas prisitaikyti
augs, o tap pat atsiras vis pelningesnių investavimo variantų. Tam tikru
momentu sustabdžius evoliuciją ir išrinkus patį geriausią individą, mes
gausime sąlyginai gerą uždavinio sprendinį.
Genetinis algoritmas – tai paprastas evoliucijos modelis gamtoje,
realizuotas kompiuterinės programos pavidalu. Joje naudojamas kaip
genetinio paveldėjimo mechanizmo analogas, taip ir natūralios atrankos
analogas. Taip pat lieka ir supaprastinta biologinė terminologija.
Štai kaip yra modeliuojamas genetinis paveldėjimas:
|Chromosoma |Vektorius (seka) iš nulių ir vienetų. |
| |Kiekviena pozicija (bitas) vadinama genu. |
|Individas = |Chromosomų rinkinys = uždavinių sprendimo |
|genetinis |variantas. |
|kodas | |
|Kryžminimas |Operacija, kurios metu dvi chromosomos apsikeičia |
| |savo dalimis. |
|Mutacija |Atsitiktinis vienos ar kelių pozicijų pasikeitimas|
| |chromosomoje. |
Evoliuciniam procesui sumodeliuoti iš pradžių sugeneruosime