Į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 atsitiktinę populiaciją – paimkime kelis individus su atsitiktiniu chromosomų rinkiniu (skaitiniais vektoriais). Genetinis algoritmas imituoja šios populiacijos evoliuciją, kurią sudaro ciklinis individų kryžminimo procesas ir jų kartų keitimasis.
[pic]
Populiacijos gyvenimo ciklas – tai atsitiktinis kryžminimasis ir mutacijos, kurių pasekoje prie populiacijos prisideda dar kažkiek naujų individų. Atranka genetiniame algoritme – tai naujos populiacijos sudarymas iš senos, po ko sena populiacija žūsta. Po naujos populiacijos atrankos vėl taikomas kryžminimas ir mutacija, po to vėl atranka, ir t.t.
Atranka genetiniame algoritme su naturalia atranka gamtoje glaudžiai siejasi tokiu būdu:
|Individo |Funkcijos reikšmė, esant šiam individui. |
|prisitaikymas | |
|Labiausiai |Kitos kartos populiacija formuojama priklausomai |
|prisitaikiusių |nuo funkcijos.Kuo labiau prisitaikęs individas, |
|išlikimas |tuo didesnė tikimybė, kad jis dauginsis. |
Tokiu būdu, atrankos modelis nustato, kaip reikia sudaryti ateinančios kartos populiaciją. Kaip taisyklė, individo dalyvavimo kryžminimosi procese tikimybė tiesiogiai priklauso nuo jo prisitaikymo. Dažnai naudojama taip vadinama elitizmo strategija, kur keli geriausi individai pereina į kitą kartą nepakitę, nedalyvaudami kryžminimesi ir atrankoje. Bet kuriuo atveju kiekviena kita karta bus vidutiniškai geresnė už pieš tai būvusią. Kai individų prisitaikymas pastebimai nedidėja, procesas sustoja ir optimizacijos uždavinio sprendiniu bus geriausias iš geriausių individas.
Grįšime prie optimizacijos uždavinio paskirstant investicijas, ir paaiškinsime genetinio algoritmo taikymą šiuo atveju.
• Individas = uždavinio sprendimo variantas = 10 chromosomų rinkinys Xj
• Chromosoma Xj = įdėtų investicijų kiekis į projektą j = šio skaičiaus užrašymas 16-taine sistema
• ne visos chromosomų reikšmės yra leistinos, nes įdėtų investicijų kiekis yra ribotas. Tai įskaitoma generuojant populiaciją.
• realiai keičiasi tik 9 chromosomos, o 10-os reikšmė nusatatoma vienareikšmiškai, nes suminis investicijų kiekis yra fiksuotas.
Žemiau pateikti genetinio algoritmo rezultatai esant trims skirtingiems suminiams investicijų kiekiams K.
Spalvotais keturkampiais pelno grafikuose pažymėta, kokį investicijų kiekį rekomenduojama įdėti į projektą.
Matome, kad esant mažai K reikšmei investuojama į projektus, kurie pelningi esant minimalioms investicijoms.
Jeigu padidiname suminį investicijų kiekį, atsiranda prasmė investuoti ir į brangesnius projektus.
Dar padidinus K, pasiekiama maksimalaus investicijų įdėjimo į pelningą projektą riba, vėl yra prasmė investuoti į mažai atnešančius pelno projektus.
3. Genetinių algoritmų ypatybės
Genetinis algoritmas – naujausias, bet ne vienintelis būdas spręsti optimizavimo uždavinius. Nuo seno tokiems uždaviniams spręsti yra žinomi du būdai: tai perrinkimo ir lokalinis-gradientinis. Kiekvienas iš metodų turi savo privalumų ir trūkumų, ir kiekvienu atveju rekėtų pagalvoti, kurį iš jų pasirinkti.
Išanalizuosime standartinių ir genetinių metodų privalumus ir trūkumus, pasinaudodami klasikiniu pavyzdžiu – komivojažerio uždaviniu(zadacia komivojazora) (TSP – travelling salesman problem).
Uždavinio esmė tokia: reikia rasti trumpiausią kelių miestų apėjimo uždarą kelią. Yra nurodytos kiekvieno miesto koordinatės. Pasirodo, kad esant jau
30-čiai miestų optimalų kelią rasti yra sunku. Tai paskatino vystyti naujus uždavinio sprendimo metodus (taip pat ir neurotinklus bei genetinius algoritmus).
Kiekvienas sprendimo variantas (30 miestų) – tai skaičių eilutė, kur j-
ojoje vietoje yra j-asis miesto apėjimo numeris.
Perrinkimo metodas iš esmės yra paprastesnis ir trivialus programavime. Optimaliam sprendiniui rasti (funkcijos maksimumo taškai)
riekia rasti visas funkcijos reikšmes kiekviename galimame taške ir išskirti maksimumą. Trūkumas: reikia atlikti labai daug skaičiavimų.
Aukščiau nagrinėtam uždaviniui reikės patikrinti daugiau kaip 1030
variantų, kas visiškai nerealu. Net šiuolaikiniam kompiuteriui tam reikės kelių mėnesių. Tačiau, jei per trumpą laiką įmanomas toks perrinkimas, tai būsime tikrai garantuoti, kad rastas sprendinys yra optimalus.
Kitas būdas yra paremtas gradientinio nuolydžio metodu. Išrenkami atsitiktiniai parametrų dydžiai, po to palaipsniui jie keičiami, siekiant kuo didesnio funkcijos augimo. Pasiekus maksimumą, toks algoritmas sustoja, todėl bus reikalingos papildomos sąlygos.
Gradientinio nuolydžio metodas yra labai veiksmingas, bet negarantuoja rasto sprendinio optimalumo. Šis metodas yra labai veiksmingas sprendžiant taip vadinamus unimodalinius uždavinius, kur funkcija turi tik vieną lokalinų maksimumą (kartu jis yra ir globalus). Anksčiau nagrinėtas pavyzdys toks nėra.
Tipinis pavyzdys yra multimodalinis ir turi daug parametrų. Tokiems uždaviniams neegzistuoja nė vieno universalaus metodo, kuris leistų pakankamai greitai rasti gerą sprendinį.
Tačiau kombinuojant perrinkimo ir gradientinio nuolydžio metodus, galima tikėtis rasti nors apytikslį sprendinį, kurio tikslumas augs didinant iteracijų skaičių.
Genetinis algoritmas kaip tik ir yra kombinuotas. Kryžminimo ir mutacijų mechanizmai realizuoja perrinkimo metodą, o geriausių sprendinių atrinkimas – gradientinį. Grafike parodyta, kad šis metodas užtikrina tikslų sprendinį įvairaus tipo uždaviniams. Kaip taisyklė, genetiniai algoritmai „klysta“ ne daugiau 5-10%. Tačiau tai kompensuojama tuom, kad uždavinys išsprendžiamas labai greitai. Neretai genetiniai algoritmai jungiami su dar kitais metodais, kurie leidžia padidinti tikslumą.
Jei uždavinys – sudėtinga funkcija su daugelis nežinomųjų, tai genetinis algoritmas – programa, kuri per realų laiką randa tašką, kuriame funkcijos reikšmė artima maksimumui. Pasirinkdami mums tinkamą skaičiavimo laiką, mes gausime vieną iš geriausių sprendinių, kuriuos iš vis galima gauti per šį laiką.
Kompanija Ward Systems Group paruošė aukščiau aprašyto uždavinio sprendimą genetinio algoritmo dėka. Tam jie pasinaudojo produkto GeneHunter funkcijų biblioteka. Miestus galime pažymėti pelyte, o trumpiausias kelias parenkamas mažiau nei per minutę.
Literatūra:
1. Францкевич Г.И., Костюк В.П. Разработка экспертной системы для анализа и прогноза финансовой деятельности предприятий.// Математическое и программное обеспечение вычислительных систем. Межвузовский сборник научных трудов, М.-1998 г. с. 111-115
2. Францкевич Г.И., Новиков А.Н., Костюк В.П. Модели и методы принятия, поддержки и реализации решений в управлении финансовыми процессами на основе нейросетевых технологий. // Математическое и программное обеспечение вычислительных систем. Межвузовский сборник научных трудов, Рязань.-1999 г. с. 64-68
3. Г. И. Францкевич, В. П. Костюк РАЗРАБОТКА И АДАПТАЦИЯ
НЕЙРОСЕТЕВОЙ МОДЕЛИ ДЛЯ АНАЛИЗА И УПРАВЛЕНИЯ ФИНАНСОВОЙ
ДЕЯТЕЛЬНОСТЬЮ ПРЕДПРИЯТИЯ// Математическое и программное обеспечение вычислительных систем. Межвузовский сборник научных трудов, Рязань.-2000 г. с. 48-52
4. Таунсенд К., Фохт Д. Проектирование и программная реализация экспертных систем на персональных ЭВМ: Пер с англ. – М.: Финансы и статистика, 1990. – 320 с. ил.
5. Naylor C. Build your own expert system. John Wiley&Sons
Ltd., Chichester, 1987
6. e-mail bull_q@inbox.ru
7. T.Strunkov, PC Week RE, 19/99.
8. Hans Moravec „Mind Children” (Future of robotics and machine intelligence.)
9. Marvin Minsky „Society of the mind.” (Description of the mind as a society of separate agents. Artificial intelligence.)
VILNIAUS GEDIMINO TECHNIKOS UNIVERSITETAS
INŽINERINĖS INFORMATIKOS KATEDRA
Dirbtinio intelekto referatas
Genetiniai algoritmai
Atliko: FMU-9gr. stud. Diana Būgaitė
Tikrino: R. Kulvietienė
Vilnius 2002
[pic]
[pic]
[pic]