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 nnuolydž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 ttechnologijos 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 na

audojama 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 iindividų 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 įg

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 v

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 p

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]

Leave a Comment