Žinių bazė

Genetiniai algoritmai (GA) ir jų sudarymo principas buvo pasiūlytas XX-ojo amžiaus 70-aisiais metais Hollando. Pradedant Hollando pirmuoju darbu, genetiniai algoritmai buvo sėkmingai išbandyti, sprendžiant įvairius optimizavimo uždavinius, pvz., tokius, kaip elektroninių komponentų išdėstymas , operacijų planavimas ir kt.

Genetiniai algoritmai (GA), jų veikimas yra pagrįstas evoliucijos, vykstančios gyvojoje gamtoje, t. y., natūraliosios atrankos proceso imitavimu. Pagrindinės sąvokos, kurios naudojamos modeliuojant biologinės evoliucijos procesus, yra „individas“ ir „populiacija“. „Individas“ yra tam tikras elementarus, daugiau neskaidomas vienetas, objektas. Didesnė ar mažesnė „individų“ grupė sudaro „populiaciją“. Dar vienas svarbus dalykas yra vadinamasis „individo tinkamumas“ − savotiška „individo vertė“. „Individo vertę“ galima traktuoti kaip „individo“ sugebėjimo sėkmingai prisitaikyti (prie aplinkos), išlikti ir reprodukuotis laipsnį. Šia prasme „vertingesnis“ (grynai biologiškai) yra tas „individas“, kuris sugeba geriausiai prisitaikyti (būti „stipresnis“ už kitus) ir, gal būt, palikti didesnį palikuonių („vaikų“) skaičių. Optimizavime vietoje sąvokų „individas“, „populiacija“, „individo vertė“ naudojamos tradicinės, įprastos sąvokos: „individui“ atitinka atskiras sprendinys, „populiacijai“ − sprendinių aibė (grupė, rinkinys), pagaliau, „individo vertė“ yra asocijuojama su tikslo funkcijos reikšme duotajam sprendiniui. Taip, kaip gyvosios gamtos evoliucijoje išlieka tik „vertingiausi“ („stipriausi“) „individai“, taip ir optimizavime siekiama gauti kuo „geresnį“ sprendinį, t. y., sprendinį su kuo mažesne (ar didesne) − nelygu, koks optimizavimo uždavinys (minimizavimo ar maksimizavimo) sprendžiamas − tikslo funkcijos reikšme.

Iš tikrųjų, terminas „genetiniai algoritmai“ reiškia ne kokį nors atskirą, specifinį euristinį optimizavimo algortimą. Greičiau šis terminas nusako tam tikrą bendrą, gana universalų metodą, strategiją − metaheuristiką, t. y., šeimą euristinių algoritmų su panašiais veikimo principais ir savybėmis. Taigi genetiniai algoritmai priklauso tai euristinių metodų klasei, kuriai būdingos sekančias savybės: 1. Operuojama su viena ar daugiau leistinų sprendinių „populiacijų“. 2. Atskiri sprendiniai iš vienos ar kelių „populiacijų“ parenkami (panaudojant kurią nors heuristinę taisyklę) tolimesniam nagrinėjimui, apdorojimui, teikiant pirmenybę tiems sprendiniams, kuri turi „geresnes“ tikslo funkcijos reikšmes. 3. Naudojamas tam tikras „mechanizmas“, kuris skirtas formuoti naujiems leistiniems sprendiniams, kombinuojant (derinant) anksčiau gautus sprendinius ar kurias nors jų savybes, charakteristikas. 4. Esant reikalui, panaudojamas papildomas „mechanizmas“ generuoti naujiems galimiems sprendiniams iš atskirų anksčiau gautų sprendinių (atliekant atsitiktinius tų sprendinių elementų perstatymus (perturbacijas)). 5. Atlikus (2)−(4) žingsnius, esama(os) „populiacija(os)“ „atnaujinama“, pašalinant iš jos (jų) tam tikrus sprendinius (paprastai, „blogesnius“) bei paliekant joje (jose) „geresniuosius“ sprendinius, tame tarpe, naujus suformuotus (sugeneruotus) (jeigu jie „pakankamai geri“).

Nuo 1965 metų, po profesoriaus Lotfi A. Zadech darbo apie neraiškiąją logiką, taip išpopuliarėjo ši mokslo šaka, kad žodis „fuzzy“ tapo tarptautiniu ir daugelyje šalių tiesiog neverčiamas. Kas tai yra ir kodėl tai verta naudoti kuriant robotus?

Kasdieniniame gyvenime mes dažnai susiduriame su ne griežtai apibrėžtais reiškiniais, kuriuose sunku įžvelgti ribą tarp tiesos ir netiesos, t.y. nėra taip, kad reiškinys arba vyksta arba ne,- jis gali vykti ir iš dalies. Tokius netikslius, neaiškius reiškinius aprašyti klasikine aibių teorija pagrįsta matematika yra sudėtinga, o be tikslaus matematinio modelio valdyti neaiškius procesus yra sudėtinga arba visai neįmanoma. Tokiu atveju išeitis gali būti neraiškioji logika, kuri leidžia matematiškai apibrėžti dalinį teisingumą, netikslumą panaudojant lingvistinius kintamuosius. Pavyzdžiui terminai „aukštas“ arba „žemas“, „toli“ arba „arti“ gali būti lingvistiniai terminai, apibūdinantys fizikinį dydį – slėgį. Pasitelkiant neraiškiąją aibių teoriją, lingvistinę, kasdieninės kalbos informaciją galima perteikti kompiuteriui, o tai leidžia lengviau ir suprantamai formuoti įvairias valdymo ar kt. užduotis.

Vienas pačių svarbiausių neraiškiosios logikos elementų yra lingvistiniai kintamieji, kurie yra suformuojami iš eilės persidengiančių neraiškiųjų aibių, fizikine prasme apibūdinančių tą kintamąjį. Pvz. lingvistinis kintamasis „Slėgis“ gali būti sudaromas iš neraiškiųjų aibių „Žemas“, „Vidutinis“ ir „Aukštas“. Atskirose situacijose neraiškiosios aibės gali turėti skirtingas reikšmių sritis, skirtingas savybes, nes pvz. Vidutinis slėgis kalbant apie orą automobilio padangose tikrai fizikine prasme nesutaps su „Vidutiniu“ slėgiu kalbant apie slėgį dujų balionuose.

Aprašykime iš ko sudarytas ir kaip veikia DNT. 1943 metais McClloch ir Pitts pasiūlė dirbtinio neurono modelį. Neuronas gauna keletą įėjimo reikšmių (tai DNT įėjimo reikšmės arba kitų tinklo neuronų išėjimo reikšmės). Kiekviena įėjimo jungtis turi savo perdavimo koeficientą (svorį). Kiekvienas neuronas turi savo sužadinimo slenksčio reikšmę. Slenksčio sužadinimo reikšmė formuojama skaičiuojant svorinę įėjimo signalų sumą ir atimant slenksčio reikšmę. Pagal sužadinimo signalą naudojant aktyvacijos funkciją (neurono perdavimo funkciją) skaičiuojama neuronų išėjimo reikšmė. Kai naudojama šuolinė perdavimo funkcija (neurono išėjimas lygus 0, jei aktyvacijos reikšmė mažiau už 0, ir lygus 1, jei reikšmė didesnė ar lygi 0), dirbtinis neuronas veikia kaip biologinis neuronas, aprašytas anksčiau. Neurono svoriai gali būti neigiami, tai reiškia, kad jungtis turi slopinantį, o ne žadinantį poveikį. Tokių slopinančių neuronų yra ir biologinėje sistemoje. Atskiri neuronai yra jungiami į neuroninį tinklą.

Visi neuroniniai tinklai turi įėjimus (perduodančius kintamųjų reikšmes iš išorės) ir išėjimus (formuojančius prognozę, valdymo signalus ir t.t.). Įėjimai ir išėjimai atitinka sensorinius ir motorinius nervus, tačiau dažniausiai egzistuoja ir tarpiniai (paslėptieji) neuronai, atliekantys vidinį vaidmenį tinkle. Visi šie neuronai yra jungiami vieni su kitais. Dažniausiai DNT turi tiesioginio sklidimo struktūrą: signalai sklinda iš įėjimo pirmyn per visus paslėptuosius neuronus ir pasiekia išėjimo neuronus. Tokia struktūra yra stabili, tačiau jei neuroninis tinklas yra rekurentinis (turintis junktis atgal iš vėlesnio į ankstesnį), jis gali būti nestabilus ir dažniausia turi be galo sudėtingą dinamiką. Šiuo metu dirbama ir su rekurentiniais tinklais, bet realių problemų sprendimui dažniausiai naudojami tiesioginio sklidimo DNT. Įėjimo sluoksnis įveda į tinklą įėjimo kintamųjų reikšmes. Tai nėra neuronų sluoksnis, nors dažnai ir vaizduojamas kaip neuronai, nes prieš duomenų apdorojimą DNT dažniausiai eina pirminio duomenų apdorojimo etapas (pvz.: normavimas, centravimas ir pan.). Paslėptų ir išėjimo sluoksnių neuronai sujungti su visais prieš tai esančio sluoksnio neuronais. Turint įėjimo reikšmes, jos patenka į įėjimo sluoksnį ir paeiliui skaičiuojamos paslėptų sluoksnių neuronų išėjimo reikšmes, po to – išėjimo sluoksnio neuronų išėjimo reikšmės.

Nors kaip ir kiekvienoje kvalifikacijoje yra prieštaringu vertinimų, galima išskirti tokius pagrindinius DI taikomus metodus: "Planning" — į kompiuterį įvedama daugybė įvairių veiksmų variantų. Po to jam suteikiamas esamos padėties ir laukiamo rezultato apibrėžimas. Kompiuteris, peržiūrinėdamas visus galimus variantus ir atmesdamas neteisingus, ieško optimalaus tikslo pasiekimo kelio. Pagal turimus duomenis sudaromas sprendimo algoritmas (teisingų veiksmų seka). Tipiškas pavyzdys: šachmatų mašina "Deep Blue".

"Machine Learning" — bandymas sukurti tokią sistemą, kuri galės pati tobulintis savarankiškai papildydama savo duomenų bazę. Kažką panašaus jau moka kai kurios programos, tačiau galimybės čia labai ribotos, ir jos visos taip pat priklauso nuo žmogaus. Ideali sistema privalo mokėti atpažinti ir analizuoti tekstą, susijungti su internetu ir važinėtis jo platybėse, susiurbti milžiniškus informacijos srautus.

"Automating Programming" — kompiuteris turi galingą vidinę programavimo kalbą. Kuomet jam duodamas suformuluotas uždavinys, jis pats rašo programą jo išsprendimui.

"Pattern Recognition" — kai programa bendrauja su aplinka, ji nuolat sulygina "tai, ką pamatė" su duomenų bazėje esančiais šablonais ir, priklausomai nuo užprogramuotos reakcijos, adekvačiai reaguoja. Akivaizdus bandymas kompiuteriu atgaminti žmogaus regėjimą, visuotinai naudojamas vaizdų ir karinių taikymo sistemų atpažinimo sistemose.

"Inference" — priešingybės metodas. Tai reiškia, kad programa priima kokį nors sprendimą ir laiko jį vieninteliu teisingu, kol nėra įrodyta priešingai. Pavyzdžiui, pamatęs paukščio skrydį, kompiuteris visus paukščius laiko mokančiais skraidyti tvariniais. Tačiau pakanka jam pamatyti pingviną arba strutį, jog įsitikintų priešingai.

"Knowledge Represantation" — darbas kuriant programą-transliatorių, išverčiantis gaunamus duomenis į suprantamą kompiuteriui kalbą. Tai užduotis, kad kiekvienas AK "pamatytas" vaizdas pavirstų nulių ir vienetų seka, pranešančia jam apie daikto pavadinimą, formą, spalvą ir kitus atributus. "Neural Networks" — bandymas atkurti vykstančius mūsų smegenyse procesus neuronų tinklais. Neuronų tinklas — tai didžiulis kiekis tarpusavyje susietų paprastų procesorių, sąveikaujančių vienas su kitu ir sugebančių keisti savybes priklausomai nuo pageidaujamo rezultato. Tokios konstrukcijos lankstumas leidžia spręsti praktiškai bet kokias skaičiavimo ir logines operacijas, todėl "NN" laikoma viena iš perspektyviausių Dirbtinio Intelekto sričių. Problemą sudaro tik tai, kad pilnaverčio smegenų modelio sukūrimui prireiks gerokai daugiau kompiuterių, nei dabar išvis yra visame pasaulyje.

"Heuristics" — visų galimų situacijų sudarymo metodas, jų apdorojimas pašalinant neefektyvius sprendimus ir ėjimas optimaliu keliu. Kažkas panašaus į "Planning", tačiau čia kompiuteris pats modeliuoja galimus įvykių vystimosi variantus. Vėlgi, geru pavyzdžiu bus "Deep Blue". Mašina apdoroja visas lentos figūrų kombinacijas 5-10 ėjimų į priekį, įvertindama bet kuriuos priešininko sprendimus, ir nustato tokią elgesio linkmę, kuri duos geriausią rezultatą. "Deep Blue" duomenų apdorojimo greitis — per 200 milijonų situacijų per sekundę, o dabar jau egzistuoja kompiuteriai, keliasdešimt kartų viršijantys šį rodiklį.

"Genetic Algorithms" — proceso organizavimas, primenantis evoliuciją gamtoje. Tai vyksta maždaug taip: programavimo kalba "Lisp" rašomos kelios programos, kurios tarpusavyje "sukryžminamos" ir taip sudaro begalę alternatyvių. Šios, savo ruožtu, pakartoja tą patį veiksmą. Iš gautų milijonų kombinacijų atrenkamos tos "kolonijos", kurios labiausiai atitinka uždavinio sąlygas, kitos — savaime susinaikina. Papildydamos viena kitą, išlikusios programos ir yra optimalus sprendinys.