Dirbtinio intelekto referatas: „Genetiniai algoritmai“

Į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 ttinklai 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ų iiš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 ffunkcija, 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 rrealų 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 WWeek 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]