Azərbaycan
Deutschland
Lietuva
Malta
ශ්රී ලංකාව
Türkmenistan
Türkiyə
Украина
Genetinis algoritmas GA algoritmas paremtas biologijos žiniomis apie gyvybės evoliuciją GA yra tam tikra klasė naudojant
Genetiniai algoritmai
Genetinis algoritmas (GA) – algoritmas, paremtas biologijos žiniomis apie gyvybės evoliuciją. GA yra tam tikra klasė, naudojanti gamtoje egzistuojančius gyvybės evoliucinius mechanizmus: paveldėjimą, mutaciją, natūraliąją atranką ir . Genetiniai algoritmai yra metodas analizuoti duomenis, jų dėka galima rasti apytikslį užduoties sprendimą. Sprendimas randamas naudojant evoliucinį , veikiantį gamtoje. Genetiniai algoritmai tinka ne visur, tačiau jais galima rasti palyginti neblogus sprendinius užduočių, kurių tikslaus sprendimo algoritmai nežinomi.
GA yra priemonė kompiuteryje atkartoti tam tikros populiacijos (vad. chromosomomis) ir sprendimų kandidatų (vad. individais) evoliuciją, artėjant prie geriausio užduoties sprendimo. Tradiciškai naudojami dvejetainis , sudarytas iš 0 ir 1, tačiau galimas ir kitoks kodavimas.
Algoritmas
Pasirinkus pradinę populiaciją, evoliucija prasideda nuo visiškai atsitiktinių kitimų. Gavus naują populiacijos kartą (kandidatus) įvertinamas jos tinkamumas, atrenkamas tam tikras naujos kartos individų skaičius, pagal atrankos kriterijų. Atrinktieji individai pakeičiami darant mutacijas arba rekombinacijas ir sukuriama nauja populiacija. Vėliau viskas kartojama, atrenkant naujus tinkamiausius individus, sukuriant naują populiaciją. Ciklas kartojamas, kol gaunamas užduotį tenkinantis sprendimą.
Bendras algoritmas
- Pasirenkama pradinė populiacija;
- Ciklo pradžia:
- Pagal atrankos kriterijų įvertinamas tam tikros dydžio populiacijos individų tinkamumas;
- Atrenkami geriausi kandidatai, iš kurių palikuonių bus sudaryta naujoji populiacija;
- Atliekama reprodukcija, daromi pakeitimai (mutacijos ir rekombinacijos), gaunama nauja populiacija;
- Ciklas kartojamas, jeigu netenkinama nutraukimo sąlyga.
Istorija
Genetiniai algoritmai kilo studijuojant ląstelių mechanizmą. Tyrimus vykdė John Holland vadovaujama grupė iš JAV Mičigano universiteto. Apie 1985-sius Ilinojaus universitete įvyko Pirmoji tarptautinė konferencija skirta genetiniams algoritmams, iki tol genetinių algoritmų tyrimai buvo daugiausia tik teoriniai. Augant akademiniam susidomėjimui bei vystantis kompiuterijai atsirado galimybė praktiniam genetinių algoritmų įgyvendinimui. 1989 m. JAV laikraštis The New York Times išspausdino rašytojo John Markoff straipsnį apie pirmą komercinę genetinį algoritmą naudojančią programą Evolver. Vėliau atsirado įvairios kompiuterinės programos skirtos įvairioms sritims. Dabartiniu metu programas naudojančias genetinius algoritmus naudoja didžioji dalis Fortune 500 kompanijų, išspręsti , duomenų talpinimo, biudžeto paskirstymo ir kitas svarbias užduotis, kur galima pritaikyti kombinatorinį optimizavimą.
Pritaikymai
Dažniausi pritaikymai
Ypatingai tinkamos genetinių algoritmų panaudojimui užduotys yra tvarkaraščių ir grafikų sudarymas, todėl daugybė šios srities programinės įrangos paketų yra paremta genetiniais algoritmais. Genetiniai algoritmai naudojami inžinerijoje bei spręsti globalias optimizavimo problemas.
Genetiniai algoritmai panaudojami ir ten, kur tradiciniai laiptiniai algoritmai (angl. hill climbing algorithms) gali užstrigti. Genetiniai algoritmai gali būti naudojami ten, kur užduoties struktūra ganėtinai sudėtinga, dėl rekombinacijos jie nuo minimumo gali judėti toliau link teisingo sprendinio, ko nesugeba laiptiniai algoritmai.
Pritaikymo sritys
Pritaikymo sritys yra labai įvairios ir ne tik tos, kurios buvo paminėtos prieš tai buvusiame skyrelyje. Pateikiama tik dalis dabar egzistuojančių pritaikymų, kadangi jų tikrai daug, GA sparčiai vystosi ir yra pritaikomi naujose srityse.
- Dirbtinio intelekto kūryba;
- Automatizuotas eskizų, modelių kūrimas (taip pat ir ieškant modeliams), daugiafunkcinių detalių modelių kūrimas automobilių (ir kitose) pramonėje, vertinamas detalių tvirtumas, masės mažinimas ir kitos svarbios charakteristikos;
- Žaidimų teorija (karo mokslas);
- ;
- Techninės įrangos kūrimas;
- Kriptografija - kodų nulaužimas;
- Konteinerio užpildymo optimizavimas;
- Vandentiekio ;
- Kompiuteriniai tinklai;
- ;
- Failų paskirstymas;
- Biologijoje, ląstelių sąveikavimas;
- Tvarkaraščių, grafikų sudarymas;
- Biudžeto optimizavimas;
- ;
- Keliaujančio pirklio uždavinys;
- Elektroninių schemų kūrimas, vadinamosios evoliucionuojančios
- Tekstinių dokumentų klasifikacija
- Ir daugybė kitų sričių.
Pritaikymo elementai
GA panaudojimui ieškant užduoties sprendimo reikalingi du pagrindiniai elementai: tinkama pradinė duomenų struktūra ir atrankos kriterijus. Algoritmui paprastai reikia, jog uždavinio sprendimas galėtų būti pateikiamas kaip duomenų struktūra, kad būtų galima nesunkiai kurti šios struktūros pakeistas kopijas. Antrasis elementas tam tikras atrankos metodas – funkcija, aprašanti atrankos kriterijų. Jos dėka galima taikyti kiekybinius atrankos kriterijus, atrenkant geresnius ir blogesnius sprendinius.
GA pritaikymo pavyzdys
Pavyzdžiui, užduotis yra kuo didesnę masę sutalpinti į krepšį, jo nesuplėšius. Sprendimas gali būti vaizduojamas kaip bitų eilutė, kur kiekvienas bitas reiškia atskirą krovinį (turintį savo masę), o bito reikšmė (0 arba 1) reiškia buvo krovinys įdėtas į krepšį ar ne. Sprendimo tinkamumą parodo gauta bendra masė. Kuo didesnė masė gaunama susumavus visas įdėtų krovinių mases, tuo tinkamesnis sprendimas.
GA algoritmas detaliau
GA pradžia
Pradžioje daug individualių sprendimų yra atsitiktinai generuojami suformuojant atsitiktinę pradinę populiaciją. Populiacijos dydis pasirenkamas pagal užduoties sudėtingumą. Dažniausiai populiaciją sudaro keletas šimtų ar net tūkstančių galimų sprendimų. Tradiciškai populiacija generuojama atsitiktinai, apimant didelį sprendinių paieškos diapazoną. Kartais nubrėžiamos tam tikros ribos, kuriose sprendinys tikėtinai turėtų būti, tokiu būdu sutrumpinamas paieškos laikas.
Atranka
Iš populiacijos atrenkama dalis tinkamiausių sprendinių (sėkmingiausių „palikuonių“), iš kurių bus kuriama naujoji populiacija. Atrankos kriterijų aprašo , kuri ir lemia atranką. Dažniausiai taikomas metodas, kai iš visos populiacijos atrenkami labiausiai tinkami sprendiniai. Tačiau yra ir kitas atrankos metodas, kurio metu yra vertinami tik atsitiktinai populiacijos sprendiniai. Šis, antrasis metodas, yra mažiau efektyvus nei pirmasis, kadangi šiuo metodu tiksliausio sprendimo paieška trunka žymiai ilgiau.
Dauguma atrankos funkcijų yra tikimybinės ir sukurtos taip, kad atrinktų tinkamais ir nedidelę dalį sprendinių, kuri yra mažiau tinkama. Tokiu būdu užtikrinimą, kad išliktų įvairovė ir išvengiama pirmalaikės konvergencijos bei nukrypimo į netinkamus sprendinius. Dažniausi ir daugiausiai išstudijuoti atrankos metodai: ruletės ir turnyrinė atranka.
Elito atranka
Ignoruojantis įprastą eigą, tačiau labai efektyvus yra variantas, kai konstruojant naują populiaciją, leidžiama keliems sėkmingiausiems individams (sprendiniams) pereiti į naują populiacija nedalyvaujant atrankoje. Ši strategija vadinama elito atranka (angl. elitist selection).
Mutacija ir rekombinacija
Antrosios ir kitų populiacijų kūrimą sudaro genetinių mechanizmų: rekombinacijos ir mutacijos – pritaikymas. Rekombinaciją ir mutacija yra biologinių mechanizmų analogai.
Kiekvieno naujo sprendinio sukūrimui iš populiacijos imama pora sprendinių „tėvų“, kurie sukryžminami ir mutacijos ar rekombinacijos būdu gaunamas sprendinys „vaikas“. Toliau imama kita „tėvų“ pora ir vėl sukuriamas „vaikas“ ir taip tęsiama kol pasiekiamas tam tikras naujos kartos individų skaičius, sukuriama pilna nauja sprendinių populiacija.
Galiausiai po šių procesų naująsias kartas sudarys individai, kurių chromosomos (sandara) yra visiškai skirtinga nei pradinės populiacijos. Bendras populiacijos tinkamumo vidurkis taip pat pakils, kadangi išliks tik geriausi individai (sprendiniai) ir dalis mažiau tinkamų individų (priežastys paminėtos prieš tai skyriuje „Atranka“.)
Mutacija
Mutacija yra būdas genetiniuose algoritmuose išlaikyti genetinę įvairovę. Mutacija naudojama GA yra biologinės mutacijos analogas, kadangi jos mechanizmas buvo kuriamas pagal biologinę mutaciją. Mutacijos padeda išvengti populiacijos chromosomų supanašėjimo (lokalaus konvergavimo), o tai vestų į evoliucijos sulėtėjimą ar net visišką stagnaciją. Tai taip pat paaiškina, kodėl GA sistemos vengia naudoti tokį atrinkimo būdą, kai atrenkami vien tik geriausi.
Klasikinį mutacijų operatoriaus veikimą sudaro atsitiktinai generuojami skaičiai, kurie nurodo įvyks ar neįvyks mutaciją tam tikrai duomenų daliai.
Kryžminimasis
Kryžminimasis (angl. crossover) yra būdas genetiniuose algoritmuose perteikti vienos chromosomos ar kelių chromosomų sandarą į kitą kartą. Ji yra biologinio kryžminimosi analogas.
Yra nemažai kryžminimosi būdų, kurie skirtingai perteikia biologinio kryžminimosi esmę:
- Su vienu kryžminimosi tašku. Pasirenkamas rekombinacijos taškas tėvų duomenyse. Vėliau visi „tėvų“ (pav. parents) duomenys, buvę už taško, apkeičiami vietomis. Rezultatas – „vaikai“ (pav. Children), kurie turi dalį vieno ir kito tėvo (genetinių) duomenų.
- Su dviem kryžminimosi taškais. Pasirenkami du kryžminimosi taškai tėvų duomenyse. Vėliau visi „tėvų“ duomenys, esantys tarp šių taškų sukeičiami vietomis. Rezultatas – „vaikai“, kurie turi dalį vieno ir kito tėvo duomenų.
- „Pjaustymas“ – kryžminimosi technika, kai keičiamas „vaikų“ duomenų ilgis. Skirtumas nuo anksčiau minėtų technikų yra tas, kad čia tėvų duomenyse pasirenkami taškai skirtingose vietose.
- Vienodas ir pusiau vienodas kryžminimasis. Abiejų technikų atvejais „tėvų“ duomenų pagrindu sukuriami du nauji „vaikai“. Pirmuoju atveju „tėvų“ duomenys sulyginami tarpusavyje ir sukeičiami vietomis su 50 proc. tikimybe. Pusiau vienodos rekombinacijos atveju sukeičiama vietomis pusė nesutampančių tėvų duomenų.
Proceso nutraukimas
Bendras sprendinių evoliucijos procesas yra cikliškai kartojamas kol pasiekiama nutraukimo sąlyga.
Dažniausios nutraukimo sąlygos: Sprendinys tenkina minimalų kriterijų;
- Pasiektas nustatytas generacijų skaičius;
- Tam skirtas biudžetas (laikas/pinigai) išnaudotas;
- Pasiekta stabili būsena, kai nėra gaunama geresnių sprendinių;
- Rankinis sustabdymas, atliekama rezultatų patikrinimas;
- Aukščiau minėtų priežasčių kombinacijos.
Stebėjimai
Yra keletas pagrindinių stebėjimų susijusių su GA. Dauguma GA problemų kyla dėl didelio jų sudėtingumo.
Lokalus konvergavimas
GA gali turėti tendenciją konverguoti link lokalaus (riboto) sprendimo, vietoje globalaus (visa apimančio) tinkamiausio sprendimo. Šios problemos tikėtinumas priklauso nuo architektūrinės tinkamumo formos. Tam tikrų problemų sprendimai lengviau krypsta link globalaus sprendinio, kitoms funkcijos lengviau rasti vietinį tinkamiausią sprendinį.
Ją sumažinti ar net visai išspręsti gali skirtingos atrankos funkcijos, arba metodai naudojami išlaikyti kuo įvairiapusiškesnę sprendinių populiaciją.
Ankstyvas konvergavimas
Sunkumų iškyla dirbant su dinaminiais duomenų rinkiniais, kai genomai pradeda anksti konverguoti, tokiu būdu nelieka reikalingų duomenų, iš jų sekančių sprendinių kūrimui.
Šiai problema spręsti variantai:
- galima padidinti genetinį įvairumą, tokiu būdu bus išvengta ankstyvos konvergencijos,
- galima padidinti mutacijos stiprumą, sukeliant vadinamas hipermutacijas (tačiau nukenčia kokybė),
- galima retkarčiais įtraukti visiškai naujus, atsitiktinai generuotus, genų fondo elementus (vad. atsitiktiniais imigrantais),
- naujausi tyrimai parodė preadaptacijos teikiama naudą sprendžiant šią problemą.
Mutacija ar rekombinacija?
Atranka yra pats svarbiausias veiksnys, tačiau yra dvi vyraujančios nuomonės dėl to kas svarbiau mutacija ar rekombinacija. Rekombinaciją palaikantieji teigia, kad ji svarbiausia, o mutacija tik užtikrinanti, kad nebūtų prarastas sprendimo potencialas. Kiti teigia, kad rekombinacija reikalinga tik tam, kad paskleistų naujoves, sukurtas mutacijų. Ir tam kad, nepastoviose populiacijose rekombinacija yra tapati didelei mutacijai (kuri dažniausiai būna katastrofiška). Dažniausiai GA greitai lokalizuoja gerą sprendimą, net ir sudėtingose paieškos srities vietose.
Optimizavimo užduotys
Specifinėms optimizavimo užduotims, paprastesni optimizavimo algoritmai gali rasti geresni sprendimą nei genetiniai algoritmai, jeigu būtų duotas tas pats skaičiavimams laikas. GA naudotojai gali pamėginti papildomai naudoti kitus algoritmus, kadangi GA negali efektyviai spręsti tų užduočių, kur negalima nustatyti, kuris variantas yra geresnis ar blogesnis, todėl negali konverguoti link tam tikro geriausio sprendimo.
Parametrų suderinimas
Visoms mašinoms (programoms), kurios ieško užduočių sprendimų yra būtina teisingai suderinti parametrus, būtinus geram sprendimo paieškos veikimui, atsižvelgiant į užduoties sudėtingumą ir tipą. Reikia suderinti šiuos parametrus: mutacijos parametrą (tikimybę, dydį), rekombinacijos parametrą (tikimybę, dydį), populiacijos dydį. Pernelyg mažas mutacijų dažnumas gali vesti link genetinio dreifo ar pirmalaikės konvergencijos į lokalų sprendinį. Jei mutacijų parametras yra per didelis, gali vesti link gerų sprendimų praradimų. Yra mėginama nustatyti šiuos rėžius, tačiau kol kas tai daroma tik teoriškai. Kitas nemažiau svarbus veiksnys yra atrankos funkcijos greitis ir efektyvumas, nuo to priklauso algoritmo darbas. Siekiama, kad atrankos funkcijos greitis ir efektyvumas būtų kuo didesni.
Variantai
Paprasčiausias algoritmo duomenų struktūros variantas, kai kiekvieną chromosomą išreiškiama bitų eilute. Dažnai parametrai užrašomi integer (sveikaisiais) tipo skaičiais, tačiau galima juos užrašyti ir real (slankiojančio kablelio, dešimtainiai ir kt.) tipo skaičiais. Algoritmo pagrindas yra mutacijos ir rekombinacijos mechanizmai atliekami bitų lygyje. Kiti duomenų struktūros variantai: chromosoma yra žymima skaičių sąrašu, kuris indeksuojamas instrukcijų lentelėje, taškais susietais su sąrašu, objektais ir kitomis duomenų struktūromis. Rekombinacija ir mutacija atliekamos taip, kad būtų paisoma duomenų struktūros elementų ribų. Daugumai duomenų tipų galima sukurti specifinius operatorius. Skirtingi chromosomų duomenų tipai veikia nevienodai sprendžiant skirtingų sričių užduotis.
Kai bitų eilutės naudoja integer tipo duomenis, dažnai naudojamas Grėjaus kodavimas (ang. Gray coding) – specifinis dvejetainio kodo išdėstymas. Šiuo kodavimu lengvai padaromi maži pakeitimai, sukelti mutacijų ir rekombinacijų. Tai taip pat padeda išvengti pirmalaikio konvergavimo, kai turėtų įvykti tuo pat metu daugybė mutacijų (ar rekombinacijų), kad būtų pasiektas pokytis link geresnio sprendimo radimo.
Kiti būdai siejami su masyvais, naudojančiais real tipo skaičius, kuriais išreiškiama chromosoma. Teoriškai turėtų būti, kad kuo mažesnis alfabetas, tuo geresnis veikimas ir rezultatas, tačiau iš tikrųjų yra atvirkščiai, kadangi geriausi rezultatai gaunami naudojant būtent real tipo chromosomas.
Paralelinis įgyvendinimas
Paralelinis GA įgyvendinimo gali būti du variantai. Prastai padarytas paralelinis genetinis algoritmas apima populiacijas, esančias kiekviename kompiuterio taške ir migraciją tarp jų. Gerai padarytas paralelinis genetinis algoritmas apima individą kiekviename procesoriaus taške, kuris sąveikauja su kitais „kaimyniniais“ individais, pasirinkdamas ir daugindamasis. Kiti variantai kai GA naudojamas tinklinio optimizavimo užduotims prideda papildomas laiko ar netvarkos priklausomybes atrankos funkcijoje.
Giminingos metodikos
(angl. Genetic programming) – naudojamas medžio tipo duomenų struktūrose, vaizduojant kompiuterio programų adaptaciją, vietoje sąrašo ar masyvo, kurį dažniausiai naudoja genetiniai algoritmai. Genetinio programavimo algoritmai dažniausiai reikalauja ilgesnio veikimo laiko, tačiau jų didesnis galingumas. Jie gali būti pritaikomi spręsti tuos uždavinius, kuriuos spręsti sunkiai pavyksta su genetiniais algoritmais.
(angl. Interactive genetic algorithms) – genetiniai algoritmai, kurie naudoja žmogaus įvertinimą. Jie naudojami srityse, kur sunku aprašyti atrankos funkciją. Pavyzdžiui, evoliucionuojantys vaizdai, muzika, kitos meninės formos, kurios priklauso nuo naudotojų estetinio pasirinkimo.
angl. Simulated annealing (SA) – siejami su globaliais optimizavimo metodais, kurie keliauja paieškos erdve, bandydami įvairias mutacijas ir individualius sprendimus. Priimama ta mutacija kuri padidina veikimo efektyvumą. Mutacija, kuri mažina efektyvumą priimama tikimybiškai priklausomai nuo tinkamumo pasiskirstymo, dažniausiai mažinant temperatūros parametrą. Egzistuoja skirtingi prioritetų vystymo keliai: pagal vieną siekiama suvartoti kuo mažiau energijos, pagal kitą siekiama didžiausio sprendimo tinkamumo. SA gali būti naudojami GA viduje, paprasčiausiai pradedama naudojant didesnį mutacijų dažnį, kuris vėliau pagal grafiką mažinamas.
(angl. Tabu search, (TS)) – panašūs į SA, abiejuose ieškoma sprendimo keliaujant paieškos erdve ir bandomos įvairios mutacijas bei individualūs sprendimai. SA generuoja vieną mutavusį sprendimą, o TS generuoja daugybę mutavusių sprendinių, bet ima mažiausia tinkamumą (sveikumą) pademonstravusį sprendinį. Tam kad būtų išvengta cikliškumo užtikrinama didesnė judėjimo laisvė sprendinių erdvėje. Tabu sąrašą sudaro daliniai arba pilni sprendiniai. Yra draudžiama imti sprendinį iš tabu sąrašo, kuris atnaujinamas vykstant sprendinio paieškai.
(angl. Ant colony optimization) naudoja daug skruzdėlių (agentų), kurios keliauja sprendimų erdvėje ir ieško produktyviausių vietų. Skruzdėlių kolonijos optimizavimas gali būti naudojamas spręsti uždaviniams, kurie nėra globalūs ar neturi naujausios informacijos, kurios reikia kitiems metodams, todėl gali būti pritaikytas ten kur kiti negali veikti.
(angl. Memetic algorithm, MA) – terminas, kurį naudoja mokslininkai įvardindami gentinių algoritmus, kurie yra kombinuoti su kitomis lokalių paieškų formomis, tokiomis kaip SA. Kai kurie mokslininkai juos įvardija kaip genetinių algoritmų ir paralelinių genetinių algoritmų hibridus. Memetiniai algoritmai yra efektyvesni už genetinius algoritmus ieškant sprendimo kai kuriose srityse.
Literatūra
- Fentress, Sam W (2005), Exaptation as a means of evolving complex solutions, MA Thesis, University of Edinburgh. (pdf)
- Goldberg, David E (1989), Genetic Algorithms in Search, Optimization and Machine Learning, Kluwer Academic Publishers, Boston, MA.
- Goldberg, David E (2002), The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Addison-Wesley, Reading, MA.
- Harvey, Inman (1992), Species Adaptation Genetic Algorithms: A basis for a continuing SAGA, in 'Toward a Practice of Autonomous Systems: Proceedings of the First European Conference on Artificial Life', F. J. Varela and P. Bourgine (eds.), MIT Press/Bradford Books, Cambridge, MA, pp. 346-354.
- Holland, John H (1975), „Adaptation in Natural and Artificial Systems“, University of Michigan Press, Ann Arbor
- Koza, John (1992), Genetic Programming: On the Programming of Computers by Means of Natural Selection
- Matthews, Robert A J (1993), The use of genetic algorithms in cryptanalysis, Cryptologia vol 17 187-201
- Michalewicz, Zbigniew (1999), Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag.
- Mitchell, Melanie, (1996), An Introduction to Genetic Algorithms, MIT Press, Cambridge, MA.
- Langdon, W. B., Poli, R. (2002), Foundations of Genetic Programming, Springer-Verlag
- Poli, R., Langdon, W. B., McPhee, N. F. (2008), A Field Guide to Genetic Programming, freely available via Lulu.com.
- Schmitt, Lothar M (2001), Theory of Genetic Algorithms, Theoretical Computer Science (259), pp. 1-61
- Schmitt, Lothar M (2004), Theory of Genetic Algorithms II: models for genetic operators over the string - tensor representation of populations and convergence to global optima for arbitrary fitness function under scaling, Theoretical Computer Science (310), pp. 181-231
- Vose, Michael D (1999), The Simple Genetic Algorithm: Foundations and Theory, MIT Press, Cambridge, MA.
- Whitley, D. (1994). A genetic algorithm tutorial. Statistics and Computing 4, 65–85.
Nuorodos
- JGap – atviro kodo genetinių algoritmų biblioteka.
Autorius: www.NiNa.Az
Išleidimo data:
vikipedija, wiki, lietuvos, knyga, knygos, biblioteka, straipsnis, skaityti, atsisiųsti, nemokamai atsisiųsti, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, pictu, mobilusis, porn, telefonas, android, iOS, apple, mobile telefl, samsung, iPhone, xiomi, xiaomi, redmi, pornografija, honor, oppo, Nokia, Sonya, mi, pc, web, kompiuteris, Informacija apie Genetiniai algoritmai, Kas yra Genetiniai algoritmai? Ką reiškia Genetiniai algoritmai?
Genetinis algoritmas GA algoritmas paremtas biologijos ziniomis apie gyvybes evoliucija GA yra tam tikra klase naudojanti gamtoje egzistuojancius gyvybes evoliucinius mechanizmus paveldejima mutacija naturaliaja atranka ir Genetiniai algoritmai yra metodas analizuoti duomenis ju deka galima rasti apytikslį uzduoties sprendima Sprendimas randamas naudojant evoliucinį veikiantį gamtoje Genetiniai algoritmai tinka ne visur taciau jais galima rasti palyginti neblogus sprendinius uzduociu kuriu tikslaus sprendimo algoritmai nezinomi GA yra priemone kompiuteryje atkartoti tam tikros populiacijos vad chromosomomis ir sprendimu kandidatu vad individais evoliucija artejant prie geriausio uzduoties sprendimo Tradiciskai naudojami dvejetainis sudarytas is 0 ir 1 taciau galimas ir kitoks kodavimas Algoritmas Pasirinkus pradine populiacija evoliucija prasideda nuo visiskai atsitiktiniu kitimu Gavus nauja populiacijos karta kandidatus įvertinamas jos tinkamumas atrenkamas tam tikras naujos kartos individu skaicius pagal atrankos kriteriju Atrinktieji individai pakeiciami darant mutacijas arba rekombinacijas ir sukuriama nauja populiacija Veliau viskas kartojama atrenkant naujus tinkamiausius individus sukuriant nauja populiacija Ciklas kartojamas kol gaunamas uzduotį tenkinantis sprendima Bendras algoritmas Pasirenkama pradine populiacija Ciklo pradzia Pagal atrankos kriteriju įvertinamas tam tikros dydzio populiacijos individu tinkamumas Atrenkami geriausi kandidatai is kuriu palikuoniu bus sudaryta naujoji populiacija Atliekama reprodukcija daromi pakeitimai mutacijos ir rekombinacijos gaunama nauja populiacija Ciklas kartojamas jeigu netenkinama nutraukimo salyga IstorijaGenetiniai algoritmai kilo studijuojant lasteliu mechanizma Tyrimus vykde John Holland vadovaujama grupe is JAV Micigano universiteto Apie 1985 sius Ilinojaus universitete įvyko Pirmoji tarptautine konferencija skirta genetiniams algoritmams iki tol genetiniu algoritmu tyrimai buvo daugiausia tik teoriniai Augant akademiniam susidomejimui bei vystantis kompiuterijai atsirado galimybe praktiniam genetiniu algoritmu įgyvendinimui 1989 m JAV laikrastis The New York Times isspausdino rasytojo John Markoff straipsnį apie pirma komercine genetinį algoritma naudojancia programa Evolver Veliau atsirado įvairios kompiuterines programos skirtos įvairioms sritims Dabartiniu metu programas naudojancias genetinius algoritmus naudoja didzioji dalis Fortune 500 kompaniju isspresti duomenu talpinimo biudzeto paskirstymo ir kitas svarbias uzduotis kur galima pritaikyti kombinatorinį optimizavima PritaikymaiDazniausi pritaikymai Ypatingai tinkamos genetiniu algoritmu panaudojimui uzduotys yra tvarkarasciu ir grafiku sudarymas todel daugybe sios srities programines įrangos paketu yra paremta genetiniais algoritmais Genetiniai algoritmai naudojami inzinerijoje bei spresti globalias optimizavimo problemas Genetiniai algoritmai panaudojami ir ten kur tradiciniai laiptiniai algoritmai angl hill climbing algorithms gali uzstrigti Genetiniai algoritmai gali buti naudojami ten kur uzduoties struktura ganetinai sudetinga del rekombinacijos jie nuo minimumo gali judeti toliau link teisingo sprendinio ko nesugeba laiptiniai algoritmai Pritaikymo sritysPritaikymo sritys yra labai įvairios ir ne tik tos kurios buvo paminetos pries tai buvusiame skyrelyje Pateikiama tik dalis dabar egzistuojanciu pritaikymu kadangi ju tikrai daug GA sparciai vystosi ir yra pritaikomi naujose srityse Dirbtinio intelekto kuryba Automatizuotas eskizu modeliu kurimas taip pat ir ieskant modeliams daugiafunkciniu detaliu modeliu kurimas automobiliu ir kitose pramoneje vertinamas detaliu tvirtumas mases mazinimas ir kitos svarbios charakteristikos Zaidimu teorija karo mokslas Technines įrangos kurimas Kriptografija kodu nulauzimas Konteinerio uzpildymo optimizavimas Vandentiekio Kompiuteriniai tinklai Failu paskirstymas Biologijoje lasteliu saveikavimas Tvarkarasciu grafiku sudarymas Biudzeto optimizavimas Keliaujancio pirklio uzdavinys Elektroniniu schemu kurimas vadinamosios evoliucionuojancios Tekstiniu dokumentu klasifikacija Ir daugybe kitu sriciu Pritaikymo elementaiGA panaudojimui ieskant uzduoties sprendimo reikalingi du pagrindiniai elementai tinkama pradine duomenu struktura ir atrankos kriterijus Algoritmui paprastai reikia jog uzdavinio sprendimas galetu buti pateikiamas kaip duomenu struktura kad butu galima nesunkiai kurti sios strukturos pakeistas kopijas Antrasis elementas tam tikras atrankos metodas funkcija aprasanti atrankos kriteriju Jos deka galima taikyti kiekybinius atrankos kriterijus atrenkant geresnius ir blogesnius sprendinius GA pritaikymo pavyzdysPavyzdziui uzduotis yra kuo didesne mase sutalpinti į krepsį jo nesuplesius Sprendimas gali buti vaizduojamas kaip bitu eilute kur kiekvienas bitas reiskia atskira krovinį turintį savo mase o bito reiksme 0 arba 1 reiskia buvo krovinys įdetas į krepsį ar ne Sprendimo tinkamuma parodo gauta bendra mase Kuo didesne mase gaunama susumavus visas įdetu kroviniu mases tuo tinkamesnis sprendimas GA algoritmas detaliauGA pradzia Pradzioje daug individualiu sprendimu yra atsitiktinai generuojami suformuojant atsitiktine pradine populiacija Populiacijos dydis pasirenkamas pagal uzduoties sudetinguma Dazniausiai populiacija sudaro keletas simtu ar net tukstanciu galimu sprendimu Tradiciskai populiacija generuojama atsitiktinai apimant didelį sprendiniu paieskos diapazona Kartais nubreziamos tam tikros ribos kuriose sprendinys tiketinai turetu buti tokiu budu sutrumpinamas paieskos laikas Atranka Is populiacijos atrenkama dalis tinkamiausiu sprendiniu sekmingiausiu palikuoniu is kuriu bus kuriama naujoji populiacija Atrankos kriteriju apraso kuri ir lemia atranka Dazniausiai taikomas metodas kai is visos populiacijos atrenkami labiausiai tinkami sprendiniai Taciau yra ir kitas atrankos metodas kurio metu yra vertinami tik atsitiktinai populiacijos sprendiniai Sis antrasis metodas yra maziau efektyvus nei pirmasis kadangi siuo metodu tiksliausio sprendimo paieska trunka zymiai ilgiau Dauguma atrankos funkciju yra tikimybines ir sukurtos taip kad atrinktu tinkamais ir nedidele dalį sprendiniu kuri yra maziau tinkama Tokiu budu uztikrinima kad isliktu įvairove ir isvengiama pirmalaikes konvergencijos bei nukrypimo į netinkamus sprendinius Dazniausi ir daugiausiai isstudijuoti atrankos metodai ruletes ir turnyrine atranka Elito atranka Ignoruojantis įprasta eiga taciau labai efektyvus yra variantas kai konstruojant nauja populiacija leidziama keliems sekmingiausiems individams sprendiniams pereiti į nauja populiacija nedalyvaujant atrankoje Si strategija vadinama elito atranka angl elitist selection Mutacija ir rekombinacija Antrosios ir kitu populiaciju kurima sudaro genetiniu mechanizmu rekombinacijos ir mutacijos pritaikymas Rekombinacija ir mutacija yra biologiniu mechanizmu analogai Kiekvieno naujo sprendinio sukurimui is populiacijos imama pora sprendiniu tevu kurie sukryzminami ir mutacijos ar rekombinacijos budu gaunamas sprendinys vaikas Toliau imama kita tevu pora ir vel sukuriamas vaikas ir taip tesiama kol pasiekiamas tam tikras naujos kartos individu skaicius sukuriama pilna nauja sprendiniu populiacija Galiausiai po siu procesu naujasias kartas sudarys individai kuriu chromosomos sandara yra visiskai skirtinga nei pradines populiacijos Bendras populiacijos tinkamumo vidurkis taip pat pakils kadangi isliks tik geriausi individai sprendiniai ir dalis maziau tinkamu individu priezastys paminetos pries tai skyriuje Atranka Mutacija Mutacija yra budas genetiniuose algoritmuose islaikyti genetine įvairove Mutacija naudojama GA yra biologines mutacijos analogas kadangi jos mechanizmas buvo kuriamas pagal biologine mutacija Mutacijos padeda isvengti populiacijos chromosomu supanasejimo lokalaus konvergavimo o tai vestu į evoliucijos suletejima ar net visiska stagnacija Tai taip pat paaiskina kodel GA sistemos vengia naudoti tokį atrinkimo buda kai atrenkami vien tik geriausi Klasikinį mutaciju operatoriaus veikima sudaro atsitiktinai generuojami skaiciai kurie nurodo įvyks ar neįvyks mutacija tam tikrai duomenu daliai Kryzminimasis Kryzminimasis angl crossover yra budas genetiniuose algoritmuose perteikti vienos chromosomos ar keliu chromosomu sandara į kita karta Ji yra biologinio kryzminimosi analogas Yra nemazai kryzminimosi budu kurie skirtingai perteikia biologinio kryzminimosi esme Rekombinacija naudojant 1 taskaSu vienu kryzminimosi tasku Pasirenkamas rekombinacijos taskas tevu duomenyse Veliau visi tevu pav parents duomenys buve uz tasko apkeiciami vietomis Rezultatas vaikai pav Children kurie turi dalį vieno ir kito tevo genetiniu duomenu Rekombinacija naudojant 2 taskusSu dviem kryzminimosi taskais Pasirenkami du kryzminimosi taskai tevu duomenyse Veliau visi tevu duomenys esantys tarp siu tasku sukeiciami vietomis Rezultatas vaikai kurie turi dalį vieno ir kito tevo duomenu Pjaustymas Pjaustymas kryzminimosi technika kai keiciamas vaiku duomenu ilgis Skirtumas nuo anksciau minetu techniku yra tas kad cia tevu duomenyse pasirenkami taskai skirtingose vietose Vienodas ir pusiau vienodas kryzminimasis Abieju techniku atvejais tevu duomenu pagrindu sukuriami du nauji vaikai Pirmuoju atveju tevu duomenys sulyginami tarpusavyje ir sukeiciami vietomis su 50 proc tikimybe Pusiau vienodos rekombinacijos atveju sukeiciama vietomis puse nesutampanciu tevu duomenu Proceso nutraukimas Bendras sprendiniu evoliucijos procesas yra cikliskai kartojamas kol pasiekiama nutraukimo salyga Dazniausios nutraukimo salygos Sprendinys tenkina minimalu kriteriju Pasiektas nustatytas generaciju skaicius Tam skirtas biudzetas laikas pinigai isnaudotas Pasiekta stabili busena kai nera gaunama geresniu sprendiniu Rankinis sustabdymas atliekama rezultatu patikrinimas Auksciau minetu priezasciu kombinacijos StebejimaiYra keletas pagrindiniu stebejimu susijusiu su GA Dauguma GA problemu kyla del didelio ju sudetingumo Lokalus konvergavimas GA gali tureti tendencija konverguoti link lokalaus riboto sprendimo vietoje globalaus visa apimancio tinkamiausio sprendimo Sios problemos tiketinumas priklauso nuo architekturines tinkamumo formos Tam tikru problemu sprendimai lengviau krypsta link globalaus sprendinio kitoms funkcijos lengviau rasti vietinį tinkamiausia sprendinį Ja sumazinti ar net visai isspresti gali skirtingos atrankos funkcijos arba metodai naudojami islaikyti kuo įvairiapusiskesne sprendiniu populiacija Ankstyvas konvergavimas Sunkumu iskyla dirbant su dinaminiais duomenu rinkiniais kai genomai pradeda anksti konverguoti tokiu budu nelieka reikalingu duomenu is ju sekanciu sprendiniu kurimui Siai problema spresti variantai galima padidinti genetinį įvairuma tokiu budu bus isvengta ankstyvos konvergencijos galima padidinti mutacijos stipruma sukeliant vadinamas hipermutacijas taciau nukencia kokybe galima retkarciais įtraukti visiskai naujus atsitiktinai generuotus genu fondo elementus vad atsitiktiniais imigrantais naujausi tyrimai parode preadaptacijos teikiama nauda sprendziant sia problema Mutacija ar rekombinacija Atranka yra pats svarbiausias veiksnys taciau yra dvi vyraujancios nuomones del to kas svarbiau mutacija ar rekombinacija Rekombinacija palaikantieji teigia kad ji svarbiausia o mutacija tik uztikrinanti kad nebutu prarastas sprendimo potencialas Kiti teigia kad rekombinacija reikalinga tik tam kad paskleistu naujoves sukurtas mutaciju Ir tam kad nepastoviose populiacijose rekombinacija yra tapati didelei mutacijai kuri dazniausiai buna katastrofiska Dazniausiai GA greitai lokalizuoja gera sprendima net ir sudetingose paieskos srities vietose Optimizavimo uzduotysSpecifinems optimizavimo uzduotims paprastesni optimizavimo algoritmai gali rasti geresni sprendima nei genetiniai algoritmai jeigu butu duotas tas pats skaiciavimams laikas GA naudotojai gali pameginti papildomai naudoti kitus algoritmus kadangi GA negali efektyviai spresti tu uzduociu kur negalima nustatyti kuris variantas yra geresnis ar blogesnis todel negali konverguoti link tam tikro geriausio sprendimo Parametru suderinimasVisoms masinoms programoms kurios iesko uzduociu sprendimu yra butina teisingai suderinti parametrus butinus geram sprendimo paieskos veikimui atsizvelgiant į uzduoties sudetinguma ir tipa Reikia suderinti siuos parametrus mutacijos parametra tikimybe dydį rekombinacijos parametra tikimybe dydį populiacijos dydį Pernelyg mazas mutaciju daznumas gali vesti link genetinio dreifo ar pirmalaikes konvergencijos į lokalu sprendinį Jei mutaciju parametras yra per didelis gali vesti link geru sprendimu praradimu Yra meginama nustatyti siuos rezius taciau kol kas tai daroma tik teoriskai Kitas nemaziau svarbus veiksnys yra atrankos funkcijos greitis ir efektyvumas nuo to priklauso algoritmo darbas Siekiama kad atrankos funkcijos greitis ir efektyvumas butu kuo didesni Variantai Paprasciausias algoritmo duomenu strukturos variantas kai kiekviena chromosoma isreiskiama bitu eilute Daznai parametrai uzrasomi integer sveikaisiais tipo skaiciais taciau galima juos uzrasyti ir real slankiojancio kablelio desimtainiai ir kt tipo skaiciais Algoritmo pagrindas yra mutacijos ir rekombinacijos mechanizmai atliekami bitu lygyje Kiti duomenu strukturos variantai chromosoma yra zymima skaiciu sarasu kuris indeksuojamas instrukciju lenteleje taskais susietais su sarasu objektais ir kitomis duomenu strukturomis Rekombinacija ir mutacija atliekamos taip kad butu paisoma duomenu strukturos elementu ribu Daugumai duomenu tipu galima sukurti specifinius operatorius Skirtingi chromosomu duomenu tipai veikia nevienodai sprendziant skirtingu sriciu uzduotis Kai bitu eilutes naudoja integer tipo duomenis daznai naudojamas Grejaus kodavimas ang Gray coding specifinis dvejetainio kodo isdestymas Siuo kodavimu lengvai padaromi mazi pakeitimai sukelti mutaciju ir rekombinaciju Tai taip pat padeda isvengti pirmalaikio konvergavimo kai turetu įvykti tuo pat metu daugybe mutaciju ar rekombinaciju kad butu pasiektas pokytis link geresnio sprendimo radimo Kiti budai siejami su masyvais naudojanciais real tipo skaicius kuriais isreiskiama chromosoma Teoriskai turetu buti kad kuo mazesnis alfabetas tuo geresnis veikimas ir rezultatas taciau is tikruju yra atvirksciai kadangi geriausi rezultatai gaunami naudojant butent real tipo chromosomas Paralelinis įgyvendinimasParalelinis GA įgyvendinimo gali buti du variantai Prastai padarytas paralelinis genetinis algoritmas apima populiacijas esancias kiekviename kompiuterio taske ir migracija tarp ju Gerai padarytas paralelinis genetinis algoritmas apima individa kiekviename procesoriaus taske kuris saveikauja su kitais kaimyniniais individais pasirinkdamas ir daugindamasis Kiti variantai kai GA naudojamas tinklinio optimizavimo uzduotims prideda papildomas laiko ar netvarkos priklausomybes atrankos funkcijoje Giminingos metodikos angl Genetic programming naudojamas medzio tipo duomenu strukturose vaizduojant kompiuterio programu adaptacija vietoje saraso ar masyvo kurį dazniausiai naudoja genetiniai algoritmai Genetinio programavimo algoritmai dazniausiai reikalauja ilgesnio veikimo laiko taciau ju didesnis galingumas Jie gali buti pritaikomi spresti tuos uzdavinius kuriuos spresti sunkiai pavyksta su genetiniais algoritmais angl Interactive genetic algorithms genetiniai algoritmai kurie naudoja zmogaus įvertinima Jie naudojami srityse kur sunku aprasyti atrankos funkcija Pavyzdziui evoliucionuojantys vaizdai muzika kitos menines formos kurios priklauso nuo naudotoju estetinio pasirinkimo angl Simulated annealing SA siejami su globaliais optimizavimo metodais kurie keliauja paieskos erdve bandydami įvairias mutacijas ir individualius sprendimus Priimama ta mutacija kuri padidina veikimo efektyvuma Mutacija kuri mazina efektyvuma priimama tikimybiskai priklausomai nuo tinkamumo pasiskirstymo dazniausiai mazinant temperaturos parametra Egzistuoja skirtingi prioritetu vystymo keliai pagal viena siekiama suvartoti kuo maziau energijos pagal kita siekiama didziausio sprendimo tinkamumo SA gali buti naudojami GA viduje paprasciausiai pradedama naudojant didesnį mutaciju daznį kuris veliau pagal grafika mazinamas angl Tabu search TS panasus į SA abiejuose ieskoma sprendimo keliaujant paieskos erdve ir bandomos įvairios mutacijas bei individualus sprendimai SA generuoja viena mutavusį sprendima o TS generuoja daugybe mutavusiu sprendiniu bet ima maziausia tinkamuma sveikuma pademonstravusį sprendinį Tam kad butu isvengta cikliskumo uztikrinama didesne judejimo laisve sprendiniu erdveje Tabu sarasa sudaro daliniai arba pilni sprendiniai Yra draudziama imti sprendinį is tabu saraso kuris atnaujinamas vykstant sprendinio paieskai angl Ant colony optimization naudoja daug skruzdeliu agentu kurios keliauja sprendimu erdveje ir iesko produktyviausiu vietu Skruzdeliu kolonijos optimizavimas gali buti naudojamas spresti uzdaviniams kurie nera globalus ar neturi naujausios informacijos kurios reikia kitiems metodams todel gali buti pritaikytas ten kur kiti negali veikti angl Memetic algorithm MA terminas kurį naudoja mokslininkai įvardindami gentiniu algoritmus kurie yra kombinuoti su kitomis lokaliu paiesku formomis tokiomis kaip SA Kai kurie mokslininkai juos įvardija kaip genetiniu algoritmu ir paraleliniu genetiniu algoritmu hibridus Memetiniai algoritmai yra efektyvesni uz genetinius algoritmus ieskant sprendimo kai kuriose srityse LiteraturaFentress Sam W 2005 Exaptation as a means of evolving complex solutions MA Thesis University of Edinburgh pdf Goldberg David E 1989 Genetic Algorithms in Search Optimization and Machine Learning Kluwer Academic Publishers Boston MA Goldberg David E 2002 The Design of Innovation Lessons from and for Competent Genetic Algorithms Addison Wesley Reading MA Harvey Inman 1992 Species Adaptation Genetic Algorithms A basis for a continuing SAGA in Toward a Practice of Autonomous Systems Proceedings of the First European Conference on Artificial Life F J Varela and P Bourgine eds MIT Press Bradford Books Cambridge MA pp 346 354 Holland John H 1975 Adaptation in Natural and Artificial Systems University of Michigan Press Ann Arbor Koza John 1992 Genetic Programming On the Programming of Computers by Means of Natural Selection Matthews Robert A J 1993 The use of genetic algorithms in cryptanalysis Cryptologia vol 17 187 201 Michalewicz Zbigniew 1999 Genetic Algorithms Data Structures Evolution Programs Springer Verlag Mitchell Melanie 1996 An Introduction to Genetic Algorithms MIT Press Cambridge MA Langdon W B Poli R 2002 Foundations of Genetic Programming Springer Verlag Poli R Langdon W B McPhee N F 2008 A Field Guide to Genetic Programming freely available via Lulu com Schmitt Lothar M 2001 Theory of Genetic Algorithms Theoretical Computer Science 259 pp 1 61 Schmitt Lothar M 2004 Theory of Genetic Algorithms II models for genetic operators over the string tensor representation of populations and convergence to global optima for arbitrary fitness function under scaling Theoretical Computer Science 310 pp 181 231 Vose Michael D 1999 The Simple Genetic Algorithm Foundations and Theory MIT Press Cambridge MA Whitley D 1994 A genetic algorithm tutorial Statistics and Computing 4 65 85 NuorodosJGap atviro kodo genetiniu algoritmu biblioteka