Įvadas
1. Tradicinių technologijų trūkumai
Sprendžiant praktinius uždavinius, daugelis klasikinių metodų yraneefektyvūs. Taip yra todėl, kad neįmanoma baigtinių parametrų dėkapakankamai realiai aprašyti tikrovę arba parinktas modelis reikalauja labaidaug 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 dirbtiniointelekto technologijos, imituojančios procesus, vykstančius gamtoje,tokius, kaip smegenų neuronai ir natūrali atranka.
Populiariausi ir labiausiai patikrinti iš technologijų yraneuroniniai tinklai ir genetiniai algoritmai. Pirmos tokio tipo programosatsirado 80-tais metais ir plačiai paplito kitose šalyse.
Neuroniniai tinklai tai savotiška smegenų imitacija, todėl jų dėkalengvai sprendžiami įvairūs „netikslūs“ uždaviniai – tai balso, vaizdo,ranka rašyto teksto, klasifikacijų atpažinimas. Tokiuose uždaviniuose, kurtradicinės technologijos bejėgės, neuroniniai tinklai yra vienintelėišeitis. Ward Systems Group duomenimis, 1998 metais programos, parašytosneuroninių tinklų pagrindu, buvo naudojamos daugiau nei 500 stambiosepasaulio kompanijose iš Fortune 1000 sąrašo.
Genetiniai algoritmai – tai speciali technologija, naudojamaoptimaliems sprendimams rasti. Ji efektyviai naudojama įvairiose mokslo irkitose srityse. Čia yra naudojama natūralios atrankos(evoliucijos Žemėje)idėja, todėl ji ir vadinama genetine. Genetiniai algoritmai dažnainaudojami 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 tikslingaivystosi 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, kadevoliucija – 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ęspalikuonis. 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 bendrojemasėje augs. Po kelių dešimčių ar šimtų kartų duotos individų rūšiesvidutinis prisitaikymas žymiai išaugs.
Kad suprasti genetinių algoritmų veikimo principus, panagrinėkime,kaip yra sudarytas genetinio paveldėjimo mechanizmas gamtoje. Kiekvienojegyvūno ląstelėje yra visa genetinė informacija apie šį individą. Šiinformacija užrašyta labai ilgų molekulių DNR rinkinių pavidalu. KiekvienaDNR molekulė – tai grandinėlė, susidedanti iš keturių rūšių nukleotidomolekulių, kurios žymimos A, T, C ir G raidėmis. Informacija užrašomanukleotidų rinkiniu DNR molekulėje. Tokiu būdu individo genetinis kodas –labai, labai ilga eilutė simbolių, kur naudojamos iš viso 4 raidės. Gyvūnoląstelėje kiekviena DNR molekulė apsupta plėvele – ir toks susidarymasvadinamas chromosoma.
Kiekvienas įgimtas individo bruožas (akių spalva, paveldėtos ligos,plaukų tipas ir t.t.) koduojamas tam tikroje chromosomos dalyje, kurivadinama šios savybės genu. Pvz.: akių spalvos genas saugo informaciją,koduojančią tam tikrą akių spalvą. Įvairios genų reikšmės vadinamosalleliais(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ų DNRdalijasi į dvi dalis ir apsikeičia savo pusėmis.Paveldint galimos visokios mutacijos, vykstančios dėl radioaktyvaus irkitų poveikių, kurių pasekoje gali pasikeisti kai kurie vieno iš tėvų genailąstelėse. Pasikeitę genai yra perduodami palikuoniui ir todėl atsirandanaujos savybės. Jeigu šios naujos savybės yra naudingos, jos,greičiausiai, išlieka duotoje rūšyje. Todėl įvyks šuolingas prisitaikymopadidėjimas šioje rūšyje.
2. Kas yra genetinis algoritmas
Tegul turime kažkokią sudėtingą funkciją, priklausančią nuo daugelionežinomųjų. Reikia rasti tokias nežinomųjų reikšmes, kurioms esant funkcijaįgyja maksimalias reikšmes. Tokio pobūdžio uždaviniai yra vadinamimaksimizavimo 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 kiekvienasprojektas (10 nežinomųjų), o funkcija, kurią reikia maksimizuoti – suminėsinvestuotojo pajamos. Taip pat yra žinomos minimalus ir maksimalusinvesticijų 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 variantopelningumą – kaip individo sugebėjimą prisitaikyti. Tada evoliucijosprocese (jei sugebėsime jį organizuoti) individų gebėjimas prisitaikytiaugs, o tap pat atsiras vis pelningesnių investavimo variantų. Tam tikrumomentu sustabdžius evoliuciją ir išrinkus patį geriausią individą, mesgausime sąlyginai gerą uždavinio sprendinį.
Genetinis algoritmas – tai paprastas evoliucijos modelis gamtoje,realizuotas kompiuterinės programos pavidalu. Joje naudojamas kaipgenetinio paveldėjimo mechanizmo analogas, taip ir natūralios atrankosanalogas. 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ų sugeneruosimeatsitiktinę populiaciją – paimkime kelis individus su atsitiktiniuchromosomų rinkiniu (skaitiniais vektoriais). Genetinis algoritmas imituojašios populiacijos evoliuciją, kurią sudaro ciklinis individų kryžminimoprocesas ir jų kartų keitimasis.
[pic]
Populiacijos gyvenimo ciklas – tai atsitiktinis kryžminimasis irmutacijos, kurių pasekoje prie populiacijos prisideda dar kažkiek naujųindividų. Atranka genetiniame algoritme – tai naujos populiacijos sudarymasiš senos, po ko sena populiacija žūsta. Po naujos populiacijos atrankos vėltaikomas kryžminimas ir mutacija, po to vėl atranka, ir t.t.
Atranka genetiniame algoritme su naturalia atranka gamtoje glaudžiaisiejasi 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čioskartos populiaciją. Kaip taisyklė, individo dalyvavimo kryžminimosi procesetikimybė tiesiogiai priklauso nuo jo prisitaikymo. Dažnai naudojama taipvadinama elitizmo strategija, kur keli geriausi individai pereina į kitąkartą nepakitę, nedalyvaudami kryžminimesi ir atrankoje. Bet kuriuo atvejukiekviena kita karta bus vidutiniškai geresnė už pieš tai būvusią. Kaiindividų prisitaikymas pastebimai nedidėja, procesas sustoja iroptimizacijos uždavinio sprendiniu bus geriausias iš geriausių individas.
Grįšime prie optimizacijos uždavinio paskirstant investicijas, irpaaiš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 trimsskirtingiems 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, kuriepelningi esant minimalioms investicijoms.
Jeigu padidiname suminį investicijų kiekį, atsiranda prasmė investuotiir į brangesnius projektus.
Dar padidinus K, pasiekiama maksimalaus investicijų įdėjimo į pelningąprojektą riba, vėl yra prasmė investuoti į mažai atnešančius pelnoprojektus.
3. Genetinių algoritmų ypatybės
Genetinis algoritmas – naujausias, bet ne vienintelis būdas spręstioptimizavimo uždavinius. Nuo seno tokiems uždaviniams spręsti yra žinomi dubūdai: tai perrinkimo ir lokalinis-gradientinis. Kiekvienas iš metodų turisavo privalumų ir trūkumų, ir kiekvienu atveju rekėtų pagalvoti, kurį iš jųpasirinkti.
Išanalizuosime standartinių ir genetinių metodų privalumus irtrūkumus, pasinaudodami klasikiniu pavyzdžiu – komivojažeriouž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 jau30-čiai miestų optimalų kelią rasti yra sunku. Tai paskatino vystyti naujusuždavinio sprendimo metodus (taip pat ir neurotinklus bei genetiniusalgoritmus).
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 trivialusprogramavime. Optimaliam sprendiniui rasti (funkcijos maksimumo taškai)riekia rasti visas funkcijos reikšmes kiekviename galimame taške irišskirti maksimumą. Trūkumas: reikia atlikti labai daug skaičiavimų.Aukščiau nagrinėtam uždaviniui reikės patikrinti daugiau kaip 1030variantų, kas visiškai nerealu. Net šiuolaikiniam kompiuteriui tam reikėskelių 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šrenkamiatsitiktiniai parametrų dydžiai, po to palaipsniui jie keičiami, siekiantkuo didesnio funkcijos augimo. Pasiekus maksimumą, toks algoritmas sustoja,todėl bus reikalingos papildomos sąlygos. Gradientinio nuolydžio metodas yra labai veiksmingas, bet negarantuojarasto sprendinio optimalumo. Šis metodas yra labai veiksmingas sprendžianttaip vadinamus unimodalinius uždavinius, kur funkcija turi tik vienąlokalinų maksimumą (kartu jis yra ir globalus). Anksčiau nagrinėtaspavyzdys toks nėra.
Tipinis pavyzdys yra multimodalinis ir turi daug parametrų. Tokiemsuž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 augsdidinant iteracijų skaičių.
Genetinis algoritmas kaip tik ir yra kombinuotas. Kryžminimo irmutacijų mechanizmai realizuoja perrinkimo metodą, o geriausių sprendiniųatrinkimas – gradientinį. Grafike parodyta, kad šis metodas užtikrinatikslų sprendinį įvairaus tipo uždaviniams. Kaip taisyklė, genetiniaialgoritmai „klysta“ ne daugiau 5-10%. Tačiau tai kompensuojama tuom, kaduždavinys išsprendžiamas labai greitai. Neretai genetiniai algoritmaijungiami su dar kitais metodais, kurie leidžia padidinti tikslumą.
Jei uždavinys – sudėtinga funkcija su daugelis nežinomųjų, taigenetinis algoritmas – programa, kuri per realų laiką randa tašką, kuriamefunkcijos reikšmė artima maksimumui. Pasirinkdami mums tinkamą skaičiavimolaiką, mes gausime vieną iš geriausių sprendinių, kuriuos iš vis galimagauti per šį laiką.
Kompanija Ward Systems Group paruošė aukščiau aprašyto uždaviniosprendimą genetinio algoritmo dėka. Tam jie pasinaudojo produkto GeneHunterfunkcijų biblioteka. Miestus galime pažymėti pelyte, o trumpiausias keliasparenkamas 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]