Genetinio faktorizavimo algoritmas. Įvadas: Genetinių algoritmų pagrindai

Maždaug prieš ketverius metus universitete išgirdau apie optimizavimo metodą, vadinamą genetiniu algoritmu. Visur apie jį buvo pranešama lygiai du dalykai: jis kietas ir nedirba. Tiksliau, jis veikia, bet yra lėtas, nepatikimas ir niekur neturėtų būti naudojamas. Bet jis gali gražiai parodyti evoliucijos mechanizmus. Šiame straipsnyje parodysiu gražų būdą, kaip gyvai pažvelgti į evoliucijos procesus, naudodamas pavyzdį, kaip tai padaryti paprastas metodas. Viskas, ko jums reikia, yra šiek tiek matematikos, programavimo ir šiek tiek vaizduotės.

Trumpai apie algoritmą

Pati metodo esmė yra ta, kad mes moduliuojame evoliucijos procesą: turime kažkokią populiaciją (vektorių rinkinį), kuri dauginasi, kurią veikia mutacijos, o natūrali atranka vykdoma remiantis minimizavimu. objektyvią funkciją. Pažvelkime į šiuos procesus atidžiau.

Taigi, visų pirma, mūsų gyventojai turi padauginti. Pagrindinis dauginimosi principas – palikuonis yra panašus į savo tėvus. Tie. turime apibrėžti kažkokį paveldėjimo mechanizmą. Ir bus geriau, jei jame bus atsitiktinumo elementas. Bet tokių sistemų vystymosi tempai labai žemi – mažėja genetinė įvairovė, populiacija išsigimsta. Tie. funkcijos reikšmė nustoja būti minimizuota.

Siekiant išspręsti šią problemą, buvo sukurtas mechanizmas mutacijos, kurį sudaro atsitiktiniai kai kurių asmenų pokyčiai. Šis mechanizmas leidžia mums į genetinę įvairovę įvesti kažką naujo.
Kitas svarbus mechanizmas - pasirinkimas. Kaip buvo sakyta, atranka yra asmenų atranka (galbūt iš ką tik gimusių, arba iš visų – praktika rodo, kad tai neturi lemiamo vaidmens), kurie geriau minimizuoja funkciją. Paprastai atrenkama tiek individų, kiek buvo iki dauginimosi, kad iš epochos į epochą mes turime pastovus kiekis individai populiacijoje. Taip pat įprasta atrinkti „laiminguosius“ - tam tikrą skaičių asmenų, kurie galbūt nesumažina funkcijos, bet įves įvairovę kitose kartose.

Šių trijų mechanizmų dažniausiai nepakanka funkcijai sumažinti. Taip populiacija išsigimsta – anksčiau ar vėliau vietinis minimumas savo verte užvaldo visus gyventojus. Kai tai įvyksta, procesas vadinamas sukrėtimas(gamtoje analogijos yra globalūs kataklizmai), kai sunaikinama beveik visa populiacija, pridedami nauji (atsitiktiniai) individai.

Čia yra klasikinio genetinio algoritmo aprašymas, jį lengva įgyvendinti, yra vietos fantazijai ir tyrinėjimams.

Problemos pareiškimas

Matematiniu požiūriu toks optimizavimas yra tik smulkmena. Tokios funkcijos grafikas yra didžiulė daugiamatė „skylė“ (pavyzdžiui, paveiksle trimatis parabaloidas), į kurią, laikydamiesi gradiento, neišvengiamai įslysite. Vienintelis vietinis minimumas yra pasaulinis. .

Bėda tik ta, kad jau arti minimumo labai sumažėja takų, kuriais galima leistis žemyn, o iš viso turime tiek krypčių, kiek yra matmenų (t.y. pikselių). Akivaizdu, kad neverta šios problemos spręsti naudojant genetinį algoritmą, bet galime pasižiūrėti įdomių procesų pasitaiko mūsų populiacijoje.

Įgyvendinimas

Kaip pradines nuotraukas paėmiau negramas („japoniškus nuskaitymo žodžius“), bet, tiesą sakant, galite paimti tik juodus kvadratus - nėra jokio skirtumo. Žemiau pateikiami kelių vaizdų rezultatai. Čia visiems, išskyrus „namą“, kiekvienam individui vidutiniškai buvo 100 mutacijų, populiacijoje buvo 100 individų, o dauginimosi metu populiacija padidėjo 4 kartus. Kiekvienoje eroje buvo 30% laimingųjų. Namui buvo pasirinktos mažesnės vertės (30 individų populiacijoje, 50 mutacijų vienam individui).

Eksperimentu pastebėjau, kad „laimingųjų“ naudojimas atrankoje sumažina populiacijos tendenciją iki minimumo, tačiau padeda išbristi iš sąstingio – be „laimingųjų“ sąstingis bus pastovus. Ką matyti iš grafikų: kairysis grafikas rodo „faraonų“ populiacijos raidą su laimingaisiais, dešiniajame – be laimingųjų.

Taigi matome, kad šis algoritmas leidžia mums išspręsti problemą, nors ir labai ilgą laiką. Didelių vaizdų atveju gali išspręsti per daug drebėjimo daugiau individai populiacijoje. Optimalus parametrų pasirinkimas skirtingų dydžių Aš palieku tai už šio įrašo ribų.

Visuotinis optimizavimas

Bet yra ir daugiau įdomus sprendimas pateikta problema: galime suprasti, kad pasiekėme vietinį minimumą, stipriai sujudinti (ar net vėl inicijuoti asmenis) ir tada pridėti bausmes, kai artėjame prie žinomo minimumo. Kaip matote, nuotraukos keičiasi. Atkreipiu dėmesį, kad mes neturime teisės liesti pradinės funkcijos. Tačiau galime prisiminti vietinius minimumus ir patys pridėti baudų.

Šiame paveikslėlyje parodytas rezultatas pasiekus vietinis minimumas(stipri stagnacija), populiacija tiesiog išmiršta.

Čia populiacija išmiršta ir pridedama nedidelė bauda (atitinka normalų atstumą iki žinomo minimumo). Tai labai sumažina pasikartojimų tikimybę.

Įdomiau, kai populiacija neišnyksta, o tiesiog pradeda prisitaikyti prie naujų sąlygų (kitas paveikslas). Tai pasiekiama taikant 0,000001 * sumos ^ 4 baudą. Tokiu atveju nauji vaizdai tampa šiek tiek triukšmingi:

Šis triukšmas pašalinamas apribojant baudą iki max (0,000001 * suma ^ 4, 20). Bet matome, kad ketvirto vietinio minimumo (dinozauro) pasiekti nepavyks – greičiausiai todėl, kad jis per arti kažkokio kito.

Biologinis aiškinimas

Kokias išvadas galime padaryti iš, drįsčiau teigti, modeliavimo? Visų pirma, matome, kad lytinis dauginimasis yra svarbiausias vystymosi ir prisitaikymo variklis. Tačiau vien to neužtenka. Atsitiktinių, nedidelių pokyčių vaidmuo yra nepaprastai svarbus. Būtent jie užtikrina naujų gyvūnų rūšių atsiradimą evoliucijos procese, o mūsų šalyje – populiacijos įvairovę.

Svarbiausią vaidmenį Žemės evoliucijoje suvaidino stichinės nelaimės ir masiniai išnykimai (dinozaurų, vabzdžių ir kt. išnykimai – pagrindinių buvo apie dešimt – žr. diagramą žemiau). Tai patvirtino ir mūsų modeliavimas. Ir „laimingųjų“ atranka parodė, kad silpniausi organizmai šiandien gali tapti pagrindu kitoms kartoms ateityje.

Kaip sakoma, viskas kaip gyvenime. Šis „pasidaryk pats“ evoliucijos metodas aiškiai parodo įdomius mechanizmus ir jų vaidmenį plėtojant. Žinoma, yra daug vertingesnių evoliucinių modelių (pagrįstų, žinoma, difurais), atsižvelgiant į daugiau veiksnių, kurie yra arčiau gyvybės. Žinoma, yra ir daugiau veiksmingi metodai optimizavimas.

P.S.

Šaltinio kodas

funkcija res = genetinis(failas) %generuojantis globalus A B;

im2line(failas);

dim = ilgis(A(1,:)); skaičius = 100; reprod = 4; mut = 100; pasirinkti = 0,7; stagnacija = 0,8;

Genetinio algoritmo efektyvumas sprendžiant kiekvieną konkreti užduotis lemia du pagrindiniai veiksniai: darbo greitis ir stabilumas. Genetinio algoritmo greitis matuojamas pagal laiką, reikalingą vartotojo nurodytam iteracijų skaičiui atlikti. Jei stabdymo kriterijus yra populiacijos kokybė arba jos konvergencija, tai greitis apskaičiuojamas pagal laiką, kai genetinis algoritmas pasiekia vieną iš šių įvykių. Paieškos stabilumas vertinamas pagal algoritmo atsparumo pataikymo taškams laipsnį vietiniai kraštutinumai ir galimybė nuolat iš kartos į kartą didinti gyventojų kokybę.

Genetinių algoritmų pranašumai ypač akivaizdūs juos svarstant, palyginti su tradiciniais metodais.

1. GA veikia su kodais, kurie yra formalizuota parametrų rinkinio forma, kuri yra tikslinės funkcijos argumentai. Šių kodų interpretavimas vyksta tik prieš pradedant algoritmą ir jį užbaigus. GA veikimo metu manipuliacijos su kodais vyksta nepriklausomai nuo jų semantinio turinio, t.y. kodas traktuojamas tiesiog kaip bitų eilutė.

2. Diegiant paieškos procedūrą, GA vienu metu apdoroja kelis paieškos erdvės taškus ir nejuda nuosekliai iš taško į tašką, kaip tradiciniais metodais. Tai leidžia mums įveikti pavojų patekti į multimodalinės tikslo funkcijos vietinį ekstremumą. Kelių taškų naudojimas vienu metu žymiai sumažina tokio įvykio tikimybę.

3. GA darbo metu jie nenaudoja jokių papildomos informacijos be duomenų apie leistinų parametrų verčių diapazoną ir tikslinę funkciją savavališkas taškas, o tai padidina jų darbo greitį.

4. Norėdami generuoti naujus taškus paieškos erdvėje, GA vienu metu naudoja ir tikimybines, ir deterministines taisykles, kurios duoda daug didesnį efektą nei kiekvienas iš šių metodų atskirai.

GA trūkumai yra šie:

· optimalaus sprendimo gavimas negarantuojamas;

· tik specialistas gali efektyviai suformuluoti problemą, nustatyti chromosomų atrankos kriterijų (nustatyti kodą) ir kitus GA parametrus;

· problemos formulavimas GA požiūriu neleidžia analizuoti statistinis reikšmingumas jų pagalba gautas sprendimas;

· gana didelis GA skaičiavimo resursų intensyvumas lemia tai, kad evoliucijos modeliavimo metu daugelis sprendimų yra atmetami kaip neperspektyvūs;

· kurių laiko sudėtingumas yra vidutiniškai mažesnis nei geriausių konkuruojančių algoritmų, bet ne didesnis (gautas remiantis eksperimentiniais duomenimis) kaip viena eilė;

· mažas efektyvumas paskutinėse evoliucijos modeliavimo fazėse, paaiškinamas tuo, kad GA paieškos mechanizmai nėra griežtai orientuoti į kuo greitesnį vietinį optimalumą;

· kai kurios kitos problemos lieka neišspręstos, pavyzdžiui, GA savarankiško prisitaikymo problema.

Kalbant apie evoliucinius skaičiavimus apskritai, reikia pažymėti, kad jie, kaip ir bet kuris metodas, naudojantys atsitiktinumo elementą, negarantuoja tikslo funkcijos (arba optimalaus sprendimo) globalaus ekstremumo aptikimo. tam tikrą laiką. Pagrindinis jų privalumas yra tai, kad jie leidžia jums rasti „gerą“ sprendimą sunki užduotis per trumpesnį laiką nei kiti metodai. Evoliucinis skaičiavimas nėra optimalus įrankis visoms problemoms spręsti, tačiau jis gana efektyvus inžinerinio projektavimo, planavimo, maršruto parinkimo, prognozavimo ir kt.

Reikėtų pažymėti, kad evoliucinis skaičiavimas yra optimizavimo problemų sprendimo būdas, o ne algoritmas. Dėl to juos reikia pritaikyti prie kiekvienos konkrečios užduočių klasės, pasirenkant tam tikras charakteristikas ir parametrus. Šiuo metu vyksta abipusė įvairių evoliucinio skaičiavimo paradigmų skverbtis ir jų sujungimas į vieną koncepciją.

Priemonių, teikiančių sprendimus, link optimizavimo problemos naudojant genetinius algoritmus yra šie programinės įrangos produktai:

· Palisade Corp. sukurtas Evolver 4.0 paketas, kuris yra MS Excel skaičiuoklių procesoriaus priedas;

· Gene Hunter 1.0 paketas Senovės įmonė Sistemos grupė;

· Genetic Training Option (GTO) paketas iš California Scientific Software, sukurtas specialiai neuroniniams tinklams lavinti ir yra Brain Maker paketo programa.

5.4. Integruotas požiūris į sistemos projektavimą
dirbtinis intelektas

Sudėtingas pritaikymas Apsvarstyti protingi informacijos apdorojimo metodai gali žymiai padidinti sukurtos InS efektyvumą.

Galimybė vienoje sistemoje naudoti ir simbolinį, ir posimbolinį metodą (dažniausiai laikomas vienas kitą nesuderinančiu) lėmė vadinamųjų hibridinių sistemų atsiradimą. Tokios sistemos yra potencialiai galingi sprendimo įrankiai sudėtingos problemos, kurios nepriklauso nuo atskirų „grynųjų“ metodų.

Pavyzdžiui, genetiniai algoritmai gali būti naudojami neuroniniam tinklui treniruoti, o neaiškioji sistema įgyvendinama kaip neaiški NN.

Dirbtinio intelekto sistemų teorijoje dar reikia daug nuveikti, kad tokios sistemos galėtų pakankamai pamėgdžioti žmogiškojo eksperto turimus nuolatinio tobulėjimo pajėgumus. Šiuo tikslu šiandien mokslininkai ir kūrėjai turi išspręsti daugybę problemų.

Pavyzdžiui, VIII tarptautinėje mokslinėje ir techninėje konferencijoje „Inteligentinės sistemos“ kuriant dirbtinio intelekto sistemas buvo nustatytos šios pagrindinės tolesnio tobulėjimo dirbtinio intelekto srityje kryptys:

· loginės išvados paralelizmas;

· ekspertų sistemos ir išvadas neapibrėžtumo sąlygomis;

· argumentacija ir abdukcinė produkcija;

· kvaziaksiomatinės sistemos;

· mašininis mokymasis ir indukcinė išvada;

· minkštasis skaičiavimas: fuzzy logika ir apytiksliai skaičiavimai;

· neuroniniai tinklai;

· genetiniai algoritmai;

· pažintinės grafikos sistemos;

· semantinio tinklo ir ontologijos sistemos;

· agentais pagrįstas ir paskirstytas problemų sprendimas;

· natūralios kalbos supratimas.

1 skyrius. Genetiniai algoritmai

1.1 Natūrali atranka gamtoje

1.2 Objektų pristatymas. Funkcijų kodavimas

1.3 Pagrindiniai genetiniai operatoriai

1.4 Genetinio algoritmo veikimo schema

2 skyrius. Optimizavimo problemos

2.1 Problemos, sprendžiamos naudojant genetinius algoritmus

2.2 Matematinė optimizavimo uždavinio formuluotė

2.3 Diofanto lygties sprendimas

2.4 Optimizavimo problemų sprendimo būdai

2.5 Keliaujančio pardavėjo problema

3 skyrius. Programinės įrangos diegimas. Genetinių algoritmų vadovo kūrimas

3.1 Programinės įrangos pasirinkimo pagrindas

3.2 Programinės įrangos diegimo aprašymas

Išvada

1.1. Natūrali atranka gamtoje

„XIX amžiuje Charlesas Darwinas padarė laivyba aplinkui, renkant informaciją evoliucijos teorijai remiantis natūrali atranka, kurioje išgyvena stipriausias. Ar jis galėjo įsivaizduoti, kad po šimto metų matematikai pasinaudos šia teorija, kad išspręstų optimalaus maršruto kelionę aplink pasaulį su sustojimais daugelyje mažų salelių?...“

Pagrindinis vaidmuo evoliucijos teorija vaidina natūrali atranka. Jos esmė ta, kad labiausiai tinkami asmenys išgyvena geriau ir susilaukia daugiau palikuonių nei mažiau tinkami asmenys. Atkreipkite dėmesį, kad pati natūrali atranka neužtikrina biologinės rūšies vystymosi. Todėl labai svarbu suprasti, kaip atsiranda paveldėjimas, tai yra, kaip palikuonio savybės priklauso nuo jo tėvų savybių.

Pagrindinis paveldėjimo dėsnis intuityviai aiškus kiekvienam – būtent palikuonys yra panašūs į savo tėvus. Visų pirma, tinkamų tėvų palikuonys yra labiau linkę būti tarp stipriausių savo kartos. Norint suprasti, kuo grindžiamas šis panašumas, reikia šiek tiek pasigilinti į natūralios ląstelės konstrukciją – į genų ir chromosomų pasaulį.

Beveik kiekvienoje kiekvieno žmogaus ląstelėje yra chromosomų rinkinys, turintis informaciją apie tą asmenį. Pagrindinė chromosomos dalis yra DNR grandinė, kuri lemia, kokios cheminės reakcijos vyks tam tikroje ląstelėje, kaip ji vystysis ir kokias funkcijas atliks. Genas yra DNR grandinės dalis, atsakinga už konkretus turtas asmenų, pavyzdžiui, dėl akių spalvos, plaukų tipo, odos spalvos ir kt. Kai gyvūnai dauginasi, susilieja dvi tėvų lytinės ląstelės ir jų DNR sąveikauja, kad susidarytų palikuonių DNR. Pagrindinis sąveikos metodas yra kryžminis. Kryžminimo metu protėvių DNR yra padalinta į dvi dalis, o tada keičiamos jų pusės.

Paveldėjimo metu dėl radioaktyvumo ar kitokio poveikio galimos mutacijos, dėl kurių vieno iš tėvų lytinėse ląstelėse gali pakisti kai kurie genai. Pasikeitę genai perduodami palikuoniui ir suteikia jam naujų savybių. Jei šios naujos savybės bus naudingos, tikėtina, kad jos išliks tam tikroje rūšyje – ir laipsniškai didės rūšies tinkamumas. Panašų algoritmą 1975 m. pirmą kartą pasiūlė Johnas Hollandas iš Mičigano universiteto. Jis buvo vadinamas „Olandijos reprodukciniu planu“ ir buvo beveik visų genetinių algoritmų variantų pagrindas. Tačiau prieš pažvelgdami į tai išsamiau, būtina pažvelgti į tai, kaip realaus pasaulio objektai gali būti užkoduoti naudoti genetiniuose algoritmuose.

1.2. Objektų vaizdavimas. Funkcijų kodavimas

Iš biologijos žinome, kad bet kurį organizmą galima pavaizduoti pagal jo fenotipą, kuris iš tikrųjų lemia, koks objektas yra realiame pasaulyje, ir jo genotipu, kuriame yra visa informacija apie objektą chromosomų rinkinio lygmeniu. Be to, kiekvienas genas, tai yra genotipo informacijos elementas, atsispindi fenotipe. Taigi, norėdami išspręsti problemas, turime pavaizduoti kiekvieną objekto požymį tokia forma, kuri tinka naudoti genetiniame algoritme. Visas tolesnis genetinio algoritmo mechanizmų veikimas vykdomas genotipo lygmeniu, todėl galima apsieiti be informacijos apie objekto vidinę struktūrą, o tai lemia platų jo naudojimą atliekant įvairias užduotis.

Labiausiai paplitęs genetinio algoritmo tipas naudoja bitų eilutes, kad pavaizduotų objekto genotipą. Šiuo atveju kiekvienas objekto atributas fenotipe atitinka vieną objekto genotipo geną. Genas yra bitų eilutė, dažniausiai fiksuoto ilgio, kuri atspindi to bruožo vertę.

Norėdami užkoduoti tokias funkcijas, galite naudoti paprasčiausią parinktį – šios funkcijos bitų reikšmę. Tada mums bus gana lengva panaudoti tam tikro ilgio geną, pakankamą visiems atstovauti galimas vertes toks ženklas. Toks kodas yra Gray kodas, kurį patartina naudoti įgyvendinant genetinį algoritmą. Gray kodų reikšmės aptariamos toliau esančioje lentelėje:

Taigi, norėdami nustatyti objekto fenotipą (tai yra objektą apibūdinančių savybių reikšmes), turime žinoti tik šias savybes atitinkančių genų reikšmes, tai yra genotipą. objekto. Šiuo atveju objekto genotipą apibūdinančių genų rinkinys yra chromosoma. Kai kuriuose įgyvendinimuose jis taip pat vadinamas individu. Taigi, įgyvendinant genetinį algoritmą, chromosoma yra fiksuoto ilgio bitų eilutė. Šiuo atveju kiekviena linijos dalis atitinka geną. Genų ilgis chromosomoje gali būti vienodas arba skirtingas. Dažniausiai naudojami vienodo ilgio genai. Pažvelkime į chromosomos pavyzdį ir jos reikšmės aiškinimą. Tarkime, objektas turi 5 charakteristikas, kurių kiekvieną užkoduoja 4 elementų ilgio genas. Tada chromosomos ilgis bus 5*4=20 bitų

Įvadas

Evoliucija gamtoje pasirodė esanti galingas gyvų organizmų vystymosi ir prisitaikymo prie jų mechanizmas aplinką ir stebina sprendimų įvairove bei efektyvumu. Todėl šios srities mokslininkai kompiuterinės technologijos pasuko į gamtą ieškodamas naujų algoritmų.

Algoritmų grupė, pagrįsta idėja Darvino evoliucija, vadinami evoliuciniais algoritmais. Jis identifikuoja šias sritis.

• Genetiniai algoritmai (GA).
• Evoliucinės strategijos.
• Genetinis programavimas.
• Evoliucinis programavimas.

Genetiniai algoritmai naudojami sprendžiant tokias problemas kaip:

• ieškoti visuotinio kelių parametrų funkcijos ekstremumo,
• funkcijos aproksimacija,
• trumpiausio kelio problemos,
• vietos problemos,
• sukurti dirbtinį neuroninį tinklą,
• žaidimų strategijos,
• mašinų mokymas.

Tiesą sakant, genetiniai algoritmai maksimaliai padidina kelių parametrų funkcijas. Štai kodėl jų taikymo sritis yra tokia plati. Visos aukščiau pateiktos problemos išsprendžiamos būtent suformuojant funkciją, kuri priklauso nuo tam tikro skaičiaus parametrų, kurių globalus maksimumas atitiks problemos sprendimą.

Natūralus mechanizmas

Gyvoms būtybėms būdingi jų išoriniai parametrai (fenotipas).

Kai kurie parametrai yra naudingi išgyvenimui ir dauginimuisi, o kiti labiau kenkia. Visi išoriniai individo duomenys yra užkoduoti jo DNR grandinės (genotipo). Atskiros šios grandinės atkarpos (genai) lemia įvairius individo parametrus.

Pagal Charleso Darwino evoliucijos teoriją, populiacijos individai konkuruoja tarpusavyje dėl išteklių (maisto) ir norėdami pritraukti draugą.

Labiausiai prie aplinkos sąlygų prisitaikę asmenys gyvens ilgiau ir susikurs daugiau palikuonių nei jų kolegos.

Natūrali atranka, kryžminimas ir mutacija užtikrina populiacijos vystymąsi. Kiekviena nauja karta vidutiniškai yra labiau tinkama nei ankstesnė, tai yra, geriau atitinka išorinės aplinkos reikalavimus. Šis procesas vadinamas evoliucija.

Atsižvelgiant į evoliuciją gamtoje, kyla mintis, kad pagal tam tikrus parametrus galima dirbtinai atrinkti mums tinkančius individus, taip sukuriant dirbtines išorines sąlygas. Tai vadinama selektyviu veisimu, kurią žmonės naudoja kurdami naujas gyvūnų veisles, pavyzdžiui, tuos, kurie duoda daugiau pieno arba turi storesnius plaukus. Bet kodėl nesutvarkius savo evoliucijos naudojant kompiuterį? Iš tiesų, tebūnie funkcija, kuri, esant tam tikram skaitinių parametrų rinkiniui, grąžina tam tikrą reikšmę (kelių parametrų funkcija). Sukurkime daug eilučių, kurių kiekvienoje bus užkoduotas skaičių vektorius (vektoriaus ilgis lygus funkcijos parametrų skaičiui). Autorius duotas vektorius galite apskaičiuoti atitinkamą funkcijos reikšmę. Tos linijos, kurioms ši vertė yra didelė, bus laikomos tinkamesnėmis nei tos, kurioms ji yra maža. Pradėdami evoliuciją stygomis, panašiomis į natūralias, kiekvienoje kartoje gausime stygas su visomis didelės vertės funkcijas. Taigi tokia evoliucija išsprendžia daugiaparametrinės funkcijos padidinimo problemą.

Klasikinis genetinis algoritmas

Tėvas šiuolaikinė teorija genetiniais algoritmais (GA) laikomas J. Hollandas, kurio darbas „Adaptacija natūraliose ir dirbtinėse sistemose“ (1975) tapo šios srities klasika. Jame Olandija pirmą kartą įvedė terminą „genetinis algoritmas“. Dabar ten aprašytas algoritmas vadinamas „klasikiniu GA“ (kartais „kanoniniu GA“, kanoniniu GA), o „genetinių algoritmų“ sąvoka tapo labai plati ir dažnai apima algoritmus, kurie labai skiriasi nuo klasikinio GA.

Olando mokiniai Kennethas De Jongas ir Davidas E. Goldbergas labai prisidėjo prie GA kūrimo. Goldbergo knyga „Genetic algoritmai paieškos optimizavime ir mašininiame mokymesi“ (1989) remiasi beveik kiekvieno darbo šia tema autoriais.

Kaip minėta aukščiau, genetiniai algoritmai veikia panašiai kaip gamta. Jie veikia su „individų“ rinkiniu, kuris yra eilutės, kurių kiekviena užkoduoja vieną iš problemos sprendimų. Asmens tinkamumas vertinamas naudojant specialią funkciją. Stipriausi turi galimybę kryžmintis ir susilaukti palikuonių. Blogiausi individai pašalinami ir palikuonių nesusilaukia. Taigi naujosios kartos tinkamumas yra vidutiniškai aukštesnis nei ankstesnės.

Fitneso funkcija ir sprendimų kodavimas

Taigi, susidurkime su optimizavimo problema. Keičiant kai kuriuos parametrus, pavyzdžiui, jei sprendžiate išdėstymo problemą, dedamų elementų koordinates, reikia rasti tokią jų kombinaciją, kad užimtas plotas būtų kuo mažesnis. Tokią problemą galima performuluoti kaip kokios nors funkcijos f (x 1, x 2, ..., x n) maksimumo radimo uždavinį. Ši funkcija vadinama kūno rengybos funkcija ir naudojama asmenų tinkamumui apskaičiuoti. Ji turi turėti neneigiamas reikšmes, o parametrų apimtis turi būti ribota.

Pavyzdžiui, jei mums reikia rasti tam tikros funkcijos minimumą, tada pakanka perkelti jos verčių diapazoną į teigiamą sritį ir tada jį apversti. Taigi maksimalus nauja funkcija atitiks pradinio minimumo.

Genetiniai algoritmai tokių nenaudoja funkcijos savybės, kaip tęstinumas, diferencijavimas ir t. t. Tai reiškia kaip prietaisas ( juodoji dėžė), kuris gauna parametrus kaip įvestį ir išveda rezultatą.

Dabar pereikime prie parametrų rinkinio kodavimo. Užkoduokime kiekvieną parametrą bitų eilute. Jei reikia ištisinio reikšmių rinkinio, tada eilutės ilgį pasirenkame pagal reikiamą tikslumą. Taigi parametras galės tik priimti diskrečiųjų vertybių

(šios reikšmės bus 2 laipsniai), tam tikrame nurodytame diapazone.

Pavyzdžiui, tegul kintamasis x k priklauso atkarpai [ x min , x max ].

Užkoduokime jį dvejetaine l bitų eilute. Tada eilutė s k žymi tokią kintamojo x k reikšmę:

X k = x min + s k (x max − x min) ⁄ 2 l jei formulėje s k žymi šia eilute užkoduoto dvejetainio skaičiaus reikšmę. 10. Papildomos 23 eilutės gali kartoti jau užkoduotas parametro reikšmes arba gali būti toliau apibrėžtos fitneso funkcijoje kaip „blogiausios“, t. mažiausia vertė.

Taigi, kiekvienam parametrui apibrėžėme eilutę, koduojančią jį. Individas bus eilutė, kuri yra viso užsakyto parametrų rinkinio eilučių junginys:

101100 11001011 01101100 1100 1 11101 | x 1 | x 2 | | | | x n |

Individo tinkamumas apskaičiuojamas taip: eilutė suskirstoma į eilutes, koduojančias parametrus. Tada kiekvienai poeiliui apskaičiuojama atitinkama parametro reikšmė, po kurios individo tinkamumas gaunamas kaip tinkamumo funkcijos reikšmė iš gautos aibės.

Paprastai tariant, nuo konkrečios užduoties priklauso tik tokie GA parametrai kaip fitneso funkcija ir sprendimų kodavimas. Likę visų užduočių veiksmai atliekami vienodai, tai rodo GA universalumą.

Darbo algoritmas

Paveiksle parodyta bet kurio genetinio algoritmo veikimo schema:

Klasikinėje GA pradinė populiacija susidaro atsitiktinai.

Populiacijos dydis yra fiksuotas (individų skaičius joje bus žymimas simboliu N), kuris nesikeičia viso algoritmo veikimo metu. Kiekvienas individas generuojamas kaip atsitiktinė L bitų eilutė, kur L yra individo kodavimo ilgis, jis taip pat yra fiksuotas ir vienodas visiems asmenims. Reikėtų pažymėti, kad kiekviena

individas yra vienas iš problemos sprendimo būdų. Tinkamesni asmenys reiškia tinkamesnius atsakymus. Ši GA skiriasi nuo daugumos kitų optimizavimo algoritmų, kurie veikia tik su vienu sprendimu, jį tobulindami. Algoritmo žingsnis susideda iš trijų etapų: tarpinės populiacijos generavimas ( tarpinė karta ) pagal pasirinkimą ( pasirinkimas ) dabartinė karta ( dabartinė karta ), kirtimas ( rekombinacija ) tarpinės populiacijos individai pagal (krosoveris krosoveris ), kuris veda į naujos kartos formavimąsi ( naujos kartos

), ir naujos kartos mutacija. Paveikslėlyje parodyti pirmieji du etapai:

Tarpinė populiacija – tai individų, įgijusių teisę daugintis, visuma. Ten kelis kartus galima įrašyti adaptuotus individus. „Blogi“ asmenys greičiausiai ten nepateks. Klasikinėje GA tikimybė, kad kiekvienas individas pateks į tarpinę populiaciją, yra proporcinga jo tinkamumui, t. y. ji veikia (proporcingas pasirinkimas). Jį galima įgyvendinti taip: leiskite individams išsidėstyti ant ruletės rato taip, kad kiekvieno individo sektoriaus dydis būtų proporcingas jo tinkamumui. Iš pradžių tarpinė populiacija yra tuščia..

Vykdydami ruletę N kartų, parenkame reikiamą skaičių individų, kuriuos reikia įrašyti į tarpinę populiaciją. Nė vienas pasirinktas asmuo nepašalinamas iš ruletės rato. Šis pasirinkimas vadinamas stochastinė atranka< f > = 1.36 (< f >Kitas atrankos būdas, kuris taip pat yra proporcingas, yra

. Kiekvienam individui apskaičiuojamas jo tinkamumo ir vidutinės populiacijos darbingumo santykis.

Sveikoji šio santykio dalis rodo, kiek kartų individą reikia įrašyti į tarpinę populiaciją, o trupmeninė dalis – jo tikimybė vėl ten patekti. Tegu, pavyzdžiui, kai kuriems asmenims i f i ⁄ — vidutinis dabartinės populiacijos tinkamumas). Tada jis bus pasirinktas vieną kartą, o tada vėl su tikimybe 0,36. Šį atrankos būdą patogu įgyvendinti taip: individus ant ruletės dedame taip, kaip aprašyta. Tegul ruletė turi ne vieną rodyklę, o N, ir jie nupjauna identiškus sektorius. Tada vienas ruletės rato sukimas iš karto atrinks visus N asmenų, kuriuos reikia įrašyti į tarpinę populiaciją.Šį metodą iliustruoja šis paveikslas:

Po atrankos tarpinės populiacijos individai atsitiktinai suskirstomi į poras. Kiekvienas iš jų kertamas su tikimybe p c, tai yra, jam taikomas kryžminimo operatorius, todėl gaunami du palikuonys. Jie prisijungia prie naujos kartos. Jei pora neturi galimybės kryžmintis, patys šios poros individai įrašomi į naują kartą.

1011001100 101101 ⇒ 1011001101 101101

Klasikinis genetinis algoritmas naudoja vieno taško kryžminimo operatorių (

1 taško krosoveris ): pirminėms chromosomoms (t. y. stygoms) atsitiktinai parenkamas pjovimo taškas ir jie keičiasi nupjautomis dalimis. Gautos dvi eilutės yra palikuonys iš: (Mutacijos operatorius taikomas naujai kartai, gautai kryžminimo būdu. Kiekvienas kiekvieno individo bitas populiacijoje yra apverstas su tikimybe p m. Ši tikimybė paprastai yra labai maža, mažesnė nei 1%. Taigi atrankos, kryžminimo ir mutacijos procesas veda į naujos kartos formavimąsi. Algoritmo žingsnis baigiasi naujos kartos paskelbimu dabartine. Tada visi veiksmai kartojami.

Konvergencija – populiacijos būsena, kai visos populiacijos eilės yra beveik identiškos ir yra kokio nors ekstremumo srityje.

Tokioje situacijoje krosoveris praktiškai visai nekeičia gyventojų.

Ir asmenys, kurie palieka šią sritį dėl mutacijos, linkę išmirti, nes dažnai būna prastesni, ypač jei šis ekstremumas yra pasaulinis maksimumas. Taigi gyventojų konvergencija dažniausiai reiškia, kad buvo rastas geresnis ar artimesnis sprendimas.

Atsakymas į problemą gali būti parametrų rinkinys, užkoduotas geriausio paskutinės kartos individo. ŠablonaiŠablonas (

• 010 00 110
• 010 01 110
• 011 10 110
• 011 11 110

schema ) yra eilutė, kurios ilgis yra L (t. y. tokio pat ilgio kaip ir bet kuri populiacijos eilutė), susidedanti iš simbolių (0, 1, *) (kur * yra simbolis „nerūpi“). eilutė reprezentuoja duotą šabloną, jei pozicijose, kuriose šablono ženklas yra 0 arba 1, jis turi tą patį simbolį. Pavyzdžiui, šablonas 01*0*110 turi šiuos atstovus: eilės tvarka ( tvarka) yra fiksuotų jame esančių bitų skaičius. Ilgio apibrėžimas (

apibrėžiantis ilgį

) yra atstumas tarp jo atokiausių fiksuotų bitų. Pavyzdžiui, modelio *1***01* tvarka yra o = 3, o apibrėžiantis ilgis Δ = 5.

Akivaizdu, kad modelio H atstovų skaičius yra lygus 2 L − o (H) , o modelių skaičius lygus 3 L (iš tikrųjų šablonai yra eilutės, kurios kiekvienoje padėtyje gali turėti vieną iš trijų simbolių).

Jei paieškos erdvę įsivaizduojate kaip hiperkubą, tai eilutės yra jo viršūnės, o šablonas joje apibrėžia hiperplokštumą. Pavyzdžiui, modelis **1 apibrėžia dešinįjį šio 3D kubo kraštą:

Todėl terminai „hiperplokštuma“ ir „raštas“ vartojami pakaitomis. Toliau pateiktame paveikslėlyje pavaizduotas kitas šablonų vaizdas: Tai rodo, kad kai kurie modeliai vidutiniškai visoje paieškos erdvėje yra labiau tinkami nei kiti.

Išoriškai atrodo, kad genetinis algoritmas pasirenka eilutę, bet taip pat netiesiogiai pasirenka modelius, kuriems jis atstovauja. Tai reiškia, kad kiekvienoje kartoje šablono atstovų skaičius keičiasi atsižvelgiant į dabartinį to šablono tinkamumą. „Gerų“ šablonų atstovai vidutiniškai labiau tinka, o tai reiškia, kad jie bus labiau atrinkti į tarpinę populiaciją. „Blogi“ modeliai turi daug galimybių išnykti. Viena linija vienu metu reprezentuoja daug raštų (būtent 2 L: kiekvienoje padėtyje paliekame linijos bitą arba pakeičiame jį „*“). Todėl renkantis vieną eilutę iš karto pasirenkamas visas šablonų rinkinys. Šis reiškinys vadinamas numanomas paralelizmas (numanomas paralelizmas).

Šablono teorema

Šablono teorema (Schemos teorema) buvo pateiktas aukščiau minėtame Olando darbe ir yra pirmasis bandymas paaiškinti, kodėl veikia genetiniai algoritmai. Tai parodo, kaip keičiasi modelio atstovų dalis populiacijoje.

Tegu M(H, t) yra šablono H atstovų skaičius t-oje kartoje. Dėl to, kad kuriant tarpinę populiaciją naudojama proporcinga atranka, šio modelio atstovų skaičius joje bus

M (H, t + tarpinis produktas) = ​​M (H, t) f (H, t) ⁄< f (t)>

kur f (H, t) yra šablono H tinkamumas t-oje kartoje ir< f (t)>— vidutinis t-osios kartos tinkamumas.

Tarpinės populiacijos individai kryžminami su tikimybe p c. Vieno taško kryžminimas gali sugadinti modelį, o tai reiškia, kad vienas iš tėvų buvo atitinkamo modelio atstovas, bet nė vienas vaikas nebus. Sunaikinimo tikimybė mažesnė nei

Δ(H) (1 − P (H , t) f (H , t) ⁄< f (t)>) ⁄ (L –1)

čia P(H, t) yra šablono H atstovų dalis t-oje kartoje. Pirmasis produkto veiksnys lygus tikimybei skirstymo taškai patenka tarp fiksuotų šablono bitų, o antrasis – tikimybė pasirinkti kito šablono atstovą į porą.

Iš tiesų, kryžminimas sunaikina šabloną ne dažniau nei tada, kai antrasis pirminis (ir jis pasirenkamas tarpinėje populiacijoje) nėra šio modelio atstovas, o skirstymo taškas patenka tarp fiksuotų šablono bitų. Net ir tokiomis situacijomis jis nebūtinai sunaikinamas, pavyzdžiui, jei žiūrime į 11**** šabloną, o 110101 ir 100000 eilutės yra kryžminės, o kryžminimo taškas patenka tarp pirmųjų dviejų bitų, tada nors antroji eilutė neatspindi norimo rašto, visi vienodai, tiks vienas iš palikuonių ir raštas nebus sunaikintas.

Taigi, po kryžminimo, pereinant nuo atstovų skaičiaus prie jų dalies, gauname tokia nelygybė:

< f (t)>) ⁄ (L −1)] ⁄< f (t)>

Dabar atsižvelkime į mutacijos poveikį. Kiekvieno fiksuoto bito tikimybė, kad jis nebus apverstas, yra (1 − p m). Kadangi bendras fiksuotų bitų skaičius šablone yra o (H), tokia galutinė modelio teoremos formulė yra teisinga:

P (H, t + 1) ≥ P (H, t) f (H, t) (1 − p m) o (H) ⁄< f (t)>

Gauta išraiška nėra labai tinkama analizuoti genetinio algoritmo veikimą. Pirma, jame yra nelygybės ženklas, kuris taip pat yra dėl to, kad neatsižvelgėme į atvejus, kai nagrinėjamas modelis gaunamas sukryžiavus stygų porą, kurios nėra jos atstovai. Antra, šablono tinkamumas ir vidutinis gyventojų tinkamumas greitai keičiasi iš kartos į kartą, todėl susidariusi nelygybė tik gerai apibūdina situaciją kitai kartai.

Nepaisant to, šablono teorema yra bent tam tikras teorinis klasikinio genetinio algoritmo darbo pagrindimas (reikia pažymėti, kad tai tinka tik klasikiniam GA su proporcingu pasirinkimu ir vieno taško kryžminiu perėjimu). Įjungta šiuo metu Yra ir tikslesnių šios teoremos versijų, ir kitų argumentų, įrodančių genetinių algoritmų naudojimo tikslingumą.

Statybiniai blokeliai

Iš šablono teoremos gautos išraiškos aišku, kad žemos eilės ir mažo lemiamo ilgio šablonai yra mažiau jautrūs sunaikinimui dėl kryžminimo ar mutacijos, todėl jų dalies populiacijoje augimas (arba mažėjimas) vyksta dinamiškiau. . Aukšto tinkamumo, žemos eilės ir mažo ilgio modeliai vadinami statybiniais blokais ( statybiniai blokai).

Holland (1992) parodė, kad nors GA apdoroja N eilučių kiekvienoje kartoje, maždaug N 3 hiperplokštumos taip pat yra netiesiogiai apdorojamos. Tai įrodyta remiantis realiai taikomu populiacijos dydžiu ir stygų ilgiu. Praktiškai tai reiškia, kad didelė populiacija turi galimybę greičiau lokalizuoti sprendimą nei maža. Norėdami įvertinti rekomenduojamą populiacijos dydį, priklausomai nuo eilutės ilgio, galime prisiminti, kad iš viso yra 3 L hiperplokštumos.

Kitas argumentas didelių populiacijų naudai: jei bloko atstovų tinkamumo sklaida yra didelė, tada tikimybė pasirinkti tam tikrą skaičių žemesnio pasirengimo bloko atstovų vietoj geresnio atstovų yra gana didelė, nes individas „silpno“ bloko asmenys gali pasirodyti geresni už daugelį „stiprių“. Padidinus populiacijos dydį, generuojant tarpinę populiaciją paimtų mėginių skaičius padidės, o tikimybė, kad galiausiai bus pasirinktas netinkamas blokas, bus gana maža.

Statybinių blokų hipotezė teigia, kad populiacijai artėjant prie pasaulinio optimalumo, statybinių blokų tvarka ir tinkamumas didėja. Tai galima lengvai pamatyti paprastu pavyzdžiu:

Visi nurodytos funkcijos lokalūs maksimumai atsiranda bloke **0*, o minimumai - **1*, todėl akivaizdu, kad po atrankos didžioji dalis individų bus pirmojo bloko atstovai. Kairioji grafiko pusė vidutiniškai yra žemiau nei dešinė, todėl 1*** bloko dalis vyraus prieš 0*** dalį. Pasirodo, kad didžioji dalis asmenų bus 1*** ir tuo pačiu **0* atstovai, o tai reiškia, kad nemaža dalis jų bus 1*0* bloko atstovai. Dabar, pasirinkę tarp 100* ir 110* blokų, matome, kad antrasis blokas bus viršesnis už pirmąjį. Taigi galima teigti, kad iš gerų mažos tvarkos statybinių blokų susiformavo pritaikyti blokai aukštesnė tvarka, ir dėl to atsidūrėme globalaus maksimumo regione, kuris priartino mus prie problemos sprendimo.

GA sąranka

Genetinis algoritmas ieško sprendimų dviem būdais vienu metu: pasirenkant hiperplokštumus ( hiperplaninis mėginių ėmimas) ir kopimo į kalną metodas. „Crossover“ įgyvendina pirmąjį iš jų, nes sujungia ir sujungia tėvų vaikų modelius. Mutacija suteikia antrąjį metodą: individas yra atsitiktinis tam tikra prasme keičiasi

Kyla klausimas: kuris iš šių būdų yra geresnis ieškant gerų sprendimų? Tyrimai parodė, kad paprastoms problemoms, tokioms kaip unimodalinės funkcijos padidinimas, GA su mutacija (ir be kryžminimo) randa sprendimus greičiau. Šis metodas taip pat reikalauja mažesnio gyventojų skaičiaus. Sudėtingoms kelių ekstremalioms funkcijoms geriau naudoti GA su kryžminiu perjungimu, nes šis metodas yra patikimesnis, nors tam reikia didesnio dydžio gyventojų.

Šablono teoremos požiūriu mutacija tik kenkia atstovų skaičiaus augimui geri šablonai, nes tai dar kartą juos sunaikina. Tačiau mutacija yra tiesiog būtina mažo populiacijos dydžio GA. Faktas yra tas, kad mažos populiacijos linkusios (priešlaikinė konvergencija priešlaikinė konvergencija

). Tai situacija, kai kai kuriose pozicijose visi individai turi tą patį bitą, tačiau toks bitų rinkinys neatitinka globalaus ekstremumo. Tuo pačiu metu krosoveris praktiškai nekeičia populiacijos, nes visi asmenys yra beveik identiški. Šiuo atveju mutacija gali apversti „įstrigusį“ bitą viename iš individų ir vėl išplėsti paieškos erdvę. (Supažindinkime su koncepcija atrankos slėgis< f >atrankos slėgis

) yra matas, nurodantis, kiek skiriasi geriausių ir blogiausių populiacijos individų tikimybė patekti į tarpinę populiaciją. Atliekant proporcingą atranką, ši vertė mažėja didėjant vidutiniam gyventojų tinkamumui. Iš tiesų, kiekvienam asmeniui santykis f ⁄ linkęs į 1, o tai reiškia, kad blogų ir gerų individų tikimybė susilaukti palikuonių yra vienoda. Didėjant p c ar p m ir mažėjant atrankos spaudimui (pavyzdžiui, naudojant kitas atrankos strategijas), adaptuotų šablonų atstovų dauginimasis sulėtėja, tačiau vyksta intensyvi kitų šablonų paieška. Ir atvirkščiai, p c arba p m sumažėjimas ir atrankos spaudimo padidėjimas lemia intensyvų rastų gerų modelių naudojimą, tačiau mažiau dėmesio skiriama naujų paieškai. Taigi, už efektyvus darbas genetinis algoritmas turi išlaikyti subtilią pusiausvyrą tarp tyrimai ir naudojimas

. Tai taip pat gali būti suformuluota kaip poreikis

subalansuota konvergencija

Klasikinis GA yra geras norint suprasti, kaip veikia genetiniai algoritmai, tačiau jis nėra pats efektyviausias. Dabar apžvelgsime įvairias kodavimo parinktis, genetinius operatorius ir atrankos strategijas, taip pat kitus GA modelius.

Kodavimas

Jei palyginsime kodavimą su dvejetaine ir ne dvejetaine abėcėle, tada pateikiama pirmoji parinktis geriausia paieška naudojant hiperplokštumus, nes tai suteikia maksimalų jų skaičių. Iš tiesų, jei reikia užkoduoti 2 L reikšmes, tada dvejetainėje abėcėlėje hiperplokštumų skaičius bus 3 L, o naudojant, pavyzdžiui, keturženklę abėcėlę, žodžių ilgis bus 2 kartus mažesnis. bus 5 L ⁄ 2 hiperplokštumos, t.y. mažiau .

Kitas dvejetainių abėcėlių argumentas yra tas, kad kiekvienam simboliui kiekvienoje pozicijoje reikalingas mažesnis populiacijos dydis. Iš tiesų, net jei yra tik dvi eilutės, yra galimybė, kad kiekvienoje populiacijos vietoje yra ir 0, ir 1 (tai yra, viena eilutė yra kitos apvertimo rezultatas). Jei abėcėlė yra galingesnė, tada dviejų eilučių populiacijoje tikrai nebus kelių simbolių kiekvienoje padėtyje ir prieš taikant mutaciją dauguma

paieškos erdvė bus neprieinama kryžminiu požiūriu. Pritaikius mutaciją, kita dalis taps neprieinama.

Kita vertus, ne dvejetainės abėcėlės dažnai pateikia vizualesnį problemos sprendimų vaizdą. Tyrimai parodė, kad daugumos funkcijų genetiniai algoritmai veiks geriau, jei parametrai bus užkoduoti į eilutę pilkas kodas , o ne tiesioginis dvejetainis kodas. Taip yra dėl vadinamųjų. Hamingo uolos , kai, pavyzdžiui, skaičiai 7 ir 8 skiriasi 4 bitais. Dvejetainis kodavimas prideda papildomų spragų, o tai apsunkina paiešką. Tai galima parodyti pavyzdžiu: tegul funkcija f (x) = x 2 yra sumažinta. Jei populiacijoje iš pradžių vyravo negatyvas geri sprendimai

Slankaus kablelio kodavimas taip pat yra geresnis nei tiesioginis dvejetainis kodavimas. Paklausus, ar tai geriau nei pilkojo kodo kodavimas, galima atsakyti, kad kai kurioms užduotims geriau tinka pirmasis variantas, kitoms – antrasis variantas. Kaip nustatyti, kurią parinktį naudoti konkrečiai užduočiai, vis dar nežinoma.

Crossover

Aukščiau aptarėme vieno taško kryžminimą.

At dviejų taškų krosoveris Tėvų porai atsitiktinai parenkami 2 atskyrimo taškai, o tėvai keičiasi tarpais. Rezultatas – du vaikai. Šiuo atveju patogu eilutes pavaizduoti kaip žiedus:

Apibrėžiamasis ilgis šiuo atveju taip pat matuojamas žiede, todėl tokiam modeliui kaip 1*****1 su vieno taško kryžminiu apibrėžiamasis ilgis yra 6, o pjūvio taškas visada patenka tarp atokiausių fiksuotų bitų. , o naudojant dviejų taškų kryžminimą šis ilgis yra 1.

Pažymėtina, kad vieno taško kryžminimas yra ypatingas dviejų taškų kryžminimo atvejis, kai yra fiksuotas vienas iš kryžminimo taškų.

Homogeniškas krosoveris atliekama taip: vienas iš vaikų paveldi kiekvieną bitą su tikimybe p 0 iš pirmojo tėvo, o kitu atveju iš antrojo. Antrasis vaikas gauna visus likusius nepaveldėtus bitus. Paprastai p0 = 0,5. Vienalyčiam kryžminiui modelio ilgis nėra svarbus, ir apskritai daugeliu atvejų raštas sunaikinamas. Šis agresyvus operatorius nėra gerai pritaikytas hiperplokštumų parinkimui, tačiau jo naudojimas yra pateisinamas, kai populiacijos dydis yra mažas, nes jis apsaugo nuo ankstyvos konvergencijos, būdingos tokioms populiacijoms.

Atrankos strategijos

Kaip minėjome aukščiau, proporcingai atrankai būdingas atrankos spaudimo sumažėjimas, padidėjus vidutiniam gyventojų tinkamumui. Šį trūkumą galima ištaisyti keičiant mastelį ( mastelio keitimas): kiekvienoje kartoje prasčiausias asmuo gali būti laikomas nuliniu.

Reitingo pasirinkimas (rango pasirinkimas) skiriasi nuo proporcingos tuo, kad kiekvieno individo tikimybė patekti į tarpinę populiaciją yra proporcinga jo eilės numeriui populiacijoje, surūšiuotoje pagal didėjantį tinkamumą. Šis atrankos tipas nepriklauso nuo vidutinio gyventojų tinkamumo.

Turnyro pasirinkimas (turnyro atranka) atliekama taip: iš populiacijos atsitiktinai atrenkami t individai, o geriausias iš jų patalpinamas į tarpinę populiaciją. Šis procesas kartojamas N kartų, kol užpildoma tarpinė populiacija. Dažniausias variantas, kai t = 2. Turnyro atranka yra agresyvesnė nei proporcinga.

Sutrumpinimo pasirinkimas (sutrumpinimo pasirinkimas): populiacija surūšiuojama pagal fizinį pasirengimą, tada paimama tam tikra geriausiųjų dalis ir iš jų atsitiktinai N kartų atrenkamas individas tolesniam vystymuisi.

Naujos kartos kūrimo strategijos

Yra du naujos kartos formavimosi tipai, gavus daug vaikų dėl kryžminimo ir mutacijos:

1. vaikai pakeičia tėvus;
2. naujoji karta susideda tiek iš vaikų, tiek iš jų tėvų visumos, pavyzdžiui, pasirenkant N geriausią.

Taip pat formuojant naują kartą galima pasinaudoti elitizmo principu: į naująją kartą turi būti įtrauktas tam tikras skaičius geriausių ankstesnės kartos individų (dažnai vienas geriausias individas).

Antrosios strategijos ir elitizmo naudojimas yra labai naudingas GA efektyvumui, nes neleidžia prarasti geriausi sprendimai.

Pavyzdžiui, jei populiacija susiliejo iki vietinio maksimumo, o mutacija atnešė vieną iš eilučių į globalų regioną, tai taikant pirmąją strategiją labai tikėtina, kad šis individas bus prarastas dėl kirtimo, o sprendimas problema nebus pasiekta. Jei naudojamas elitizmas, tai gautas geras sprendimas išliks populiacijoje, kol bus rastas dar geresnis.

Kai kurie genetinių algoritmų modeliai

Klasikinis GA buvo aptartas aukščiau. Prisiminkime, kad jį sukūrė Olandija (1975).

Genitor Šį algoritmą sukūrė D. Whitley. Genitor

• - panašūs algoritmai skiriasi nuo klasikinių GA šiomis trimis savybėmis: Tik kiekviename žingsnyje vienas pora atsitiktinių tėvų kuria tik vienas
• vaikas. Šį algoritmą sukūrė D. Whitley.Šis vaikas pakeičia ne tėvą, o vieną blogiausių individų populiacijoje (originale
• – pats blogiausias).

Asmens atranka pakeitimui vykdoma pagal jo rangą (reitingą), o ne pagal tinkamumą. Šį algoritmą sukūrė D. Whitley. Teigiama (Syswerda, 1991), kad in

hiperplokštumų paieška yra geresnė, o konvergencija greitesnė nei klasikinio GA.

C.H.C. C.H.C. reiškia Kryžminė elito atranka, heterogeninė rekombinacija, kataklizminė mutacija

• . Šį algoritmą sukūrė Eshelman (1991) ir turi šiuos parametrus: Naujai kartai atrenkami geriausi N asmenys tarp tėvų ir vaikų. Pasikartojančios eilutės neleidžiamos.
• Kryžminimui parenkama atsitiktinė pora, tačiau neleidžiama, kad Hamingo atstumas tarp tėvų būtų mažas arba atstumas tarp kraštutinių skirtingų bitų būtų mažas.
• Kryžminimui naudojamas vienalytis krosoveris HUX (Pusiau vienodas krosoveris): lygiai pusė kiekvieno iš tėvų bitų atitenka vaikui.
• Populiacijos dydis nedidelis, apie 50 individų. Tai pateisina vienalyčio krosoverio naudojimą.
• CHC supriešina agresyvią atranką su agresyviu krosoveriu, tačiau mažas populiacijos dydis vis tiek greitai priveda prie būsenos, kai sukuriamos tik daugiau ar mažiau identiškos linijos. Tokiu atveju taikomas CHC kataklizminė mutacija: Visose eilutėse, išskyrus tinkamiausias, vyksta stipri mutacija (pakeičiama apie trečdalis bitų). Taigi, algoritmas paleidžiamas iš naujo ir toliau veikia, taikydamas tik kryžminimą.

Hibridiniai algoritmai

Idėja hibridiniai algoritmai (hibridiniai algoritmai) susideda iš genetinio algoritmo sujungimo su kitu paieškos metodu, tinkamu tam tikrai problemai (taip dažnai nutinka kopimas į kalną). Kiekvienoje kartoje kiekvienas gautas vaikas optimizuojamas šiuo metodu, o po to atliekami įprasti GA veiksmai. Naudojant kopimas į kalną Pasirodo, kiekvienas individas pasiekia vietinį maksimumą, šalia kurio jis yra, po kurio jis yra atrenkamas, kryžminamas ir mutuojamas.

Šis vystymosi tipas vadinamas Lamarko evoliucija, kai individas gali mokytis, o vėliau įrašyti įgytus įgūdžius į savo genotipą, kad vėliau perduotų juos savo palikuonims. Ir nors šis metodas pablogina algoritmo galimybes rasti sprendimą parenkant hiperplokštumas, praktiškai hibridiniai algoritmai pasirodo labai sėkmingi. Taip yra dėl to, kad dažniausiai yra didelė tikimybė, kad vienas iš individų pateks į globalaus maksimumo sritį ir po optimizavimo pasirodys problemos sprendimas.

Genetinis algoritmas gali greitai rasti gerų sprendimų visoje paieškos erdvėje, tačiau gali būti sunku iš jų gauti geriausius. Toks metodas kaip kopimas į kalną greitai pasiekia vietinį maksimumą, bet negali ieškoti globalaus. Šių dviejų algoritmų derinys gali išnaudoti abu.

Lygiagrečios GA

Gamtoje visi procesai vyksta lygiagrečiai ir nepriklausomai vienas nuo kito. Genetiniai algoritmai taip pat gali būti organizuojami kaip keli procesai, vykstantys lygiagrečiai, ir tai padidins jų našumą.

Paverskime klasikinį GA lygiagrečiu. Tam naudosime turnyro atranką. Sukurkime N ⁄ 2 procesų (toliau procesas reiškia tam tikrą mašiną, procesorių, kuris gali dirbti savarankiškai). Kiekvienas iš jų atsitiktine tvarka atrinks 4 asmenis iš populiacijos, surengs 2 turnyrus ir sukryžmins nugalėtojus. Gauti vaikai bus įtraukti į naują kartą. Taigi per vieną vieno proceso veikimo ciklą bus pakeista visa karta.

Salos modeliai

Retkarčiais (pvz., kas 5 kartos) procesai (arba salos) apsikeis keliais gerais individais. Tai vadinama migracija. Tai leidžia saloms keistis genetine medžiaga.

Kadangi salų populiacijos paprastai yra mažos, subpopuliacijos bus linkusios per anksti suartėti. Todėl svarbu teisingai nustatyti migracijos dažnį. Per dažna migracija (arba per daug individų migracija) sukels visų subpopuliacijų susimaišymą, o tada salos modelis nedaug skirsis nuo įprasto GA. Jei migracija bus per reta, ji negalės užkirsti kelio priešlaikiniam subpopuliacijų suartėjimui.

Genetiniai algoritmai yra stochastiniai, todėl skirtingos algoritmo eigos gali lemti, kad populiacija susilieja su skirtingais sprendimais (nors visi jie tam tikru mastu yra „geri“). Salos modelis leidžia paleisti algoritmą kelis kartus iš karto ir bandyti sujungti skirtingų salų „pasiekimus“, kad gautumėte geriausią sprendimą vienoje iš pogrupių.

Ląstelių genetiniai algoritmai

Cellular Genetic Algorithms yra lygiagretus GA modelis.

Kiekvienas procesas gali sąveikauti tik su keturiais savo kaimynais (viršuje, apačioje, kairėje, dešinėje). Kiekvienoje ląstelėje yra tiksliai vienas asmuo. Kiekvienas procesas atrinks geriausią asmenį iš savo kaimynų, perkels asmenį iš savo ląstelės su juo ir vieną gautą vaiką įkels į savo ląstelę, o ne į tėvą.

Kai toks algoritmas veikia, atsiranda efektų, panašių į salos modelį. Iš pradžių visi asmenys turi atsitiktinį tinkamumą (paveiksle jį lemia spalva). Po kelių kartų susidaro nedideli panašių, panašaus pasirengimo individų plotai. Veikiant algoritmui šios sritys auga ir konkuruoja viena su kita.

Kiti modeliai

Iki šiol mes svarstėme GA su fiksuotais parametrais, tokiais kaip populiacijos dydis, eilutės ilgis, kryžminimas ir mutacijos tikimybė. Tačiau yra genetinių algoritmų, kuriuose šiuos parametrus galima keisti ir koreguoti.

Pavyzdžiui, tegul kiekvieno individo mutacijos tikimybė yra atskira.

Galite pridėti poeilelę prie asmens eilutės, kuri koduoja šią tikimybę. Skaičiuojant tinkamumą, ši poeilutė bus ignoruojama, tačiau ji bus perjungta ir mutuojama taip pat, kaip ir likusi eilutė. Tikimybė, kad mutacijos metu kiekvienas konkretaus individo bitas bus apverstas, bus lygi reikšmei, užkoduotai pridėtos poeilutės.

Mutacijų tikimybė inicijuojama atsitiktinai.

Thomas Back (1992) savo darbe pažymėjo, kad unimodalinėms funkcijoms variantas su globalios mutacijos tikimybe veikia geriau, tačiau kelių ekstremalių funkcijų atveju adaptyviosios mutacijos naudojimas duoda geresnių rezultatų.

Stebėjimai

Atkreipkime dėmesį į kai kuriuos genetinių algoritmų tyrinėtojų pastebėjimus.

Veiksniai, sukuriantys GA sudėtingumą

Norint gauti gerų rezultatų, reikia pasirinkti tinkamą populiacijos dydį. Grafike parodyta tinkamumo funkcijos skaičiavimų skaičiaus, norint rasti unimodalinės funkcijos maksimumą, priklausomybė nuo populiacijos dydžio. Matyti, kad yra optimalus populiacijos dydis. Iš tiesų, jei populiacija yra maža, tada esant tam tikram tinkamumo funkcijos skaičiavimų skaičiaus (taigi ir fiksuoto skaičiavimo laiko) apribojimui, jis turės laiko sukurti didesnį kartų skaičių, tačiau greičiausiai jis susilies per anksti. .

Per didelė populiacija turi rasti sprendimą, tačiau ji gali nespėti pasiekti šį tašką, nes jai skirta nedaug kartų.

Algoritmams su kryžminiu (t. y. be mutacijos) yra optimalaus dydžio įvertinimai, tačiau GA su mutacija (ir be kryžminimo) dar nėra. Tačiau eksperimentai rodo, kad jiems yra ir optimalus populiacijos dydis. Bet kokiu atveju tai priklauso nuo užduoties.

• Išvados
• Genetiniai algoritmai yra universalus būdas optimizuoti kelių parametrų funkcijas, todėl gali išspręsti daugybę problemų. Genetiniai algoritmai suteikia didžiulę tyrimų medžiagą, nes didelis kiekis
• modifikacijos ir parametrai. Dažnai nedidelis vieno iš jų pakeitimas gali lemti netikėtą rezultato pagerėjimą.

Tuo pačiu reikia atsiminti, kad GA naudojimas yra naudingas tik tais atvejais, kai tam tikrai problemai nėra tinkamo specialaus sprendimo algoritmo. Palyginti su tokiu algoritmu, GA veiks bent jau ne ką geriau (išskyrus galimą hibridinį algoritmą).

• GA taikymo pavyzdžiai
• Klasikinio GA darbo su multiekstremalia funkcija demonstravimas (http://ai.bpa.arizona.edu/~mramsey/ga.html).
• Keliaujančio pardavėjo problemos (TSP) sprendimas naudojant GA (http://lib.training.ru/Lib/ArticleDetail.aspx?ar=803&l=&mi=93&mic=112).
• Žmogaus modelio mokymas vaikščioti naudojant GA (http://www.naturalmotion.com/pages/technology.htm).

Literatūra

1. Kitas GA darbo demonstravimas (http://www.rennard.org/alife/english/gavgb.html).
2. Darrel Whitley, Genetic Algorithm Tutorial, Statistics and Computing (4): 65-85, 1994.
3. Darrel Whitley, Evoliucinių algoritmų apžvalga: praktinės problemos ir bendri spąstai, Informacijos ir programinės įrangos technologijų žurnalas 43: 817-831, 2001.
4. K. Deb, S. Agrawal, Interactions among Genetic Algorithm Parameters supratimas, 1998 m.
5. Isajevas S.A. Populiaru apie genetinius algoritmus (http://algolist.manual.ru/ai/ga/ga1.php).

Bulatas Jaminovas

Ačiū, naudingas straipsnis.

Norėčiau atkreipti jūsų dėmesį į keletą dalykų.

Skyriuje?Šablonai? Stulpelyje surašyti modelio atstovai. Trečiame ir ketvirtame atstovuose skaičius 0 turėtų būti rašomas ketvirtoje pozicijoje, o ne 1. Pastraipoje prieš kubo atvaizdą rašoma, kad „raštas lemia hiperplokštumą jame?“, tai galioja tik kai kuriems raštams. . Pavyzdžiui, *11 nebėra hiperplokštuma (kodimensija nelygi 1).

Tikimės, kad šio puslapio lankytojai atkreips dėmesį į jūsų pastabas.

Ir keletas kalbos klaidų.<... ...="">

Ačiū, jūsų nurodytos rašybos klaidos buvo ištaisytos.

Skiltyje „GA naudojimo pavyzdžiai“, deja, yra 3 neveikiančios nuorodos.

Šiame skyriuje aprašoma paprasto genetinio algoritmo (GA) koncepcija, skirta įvairioms optimizavimo problemoms spręsti. Supažindinama ir prasmingai aprašomos GA teorijoje ir taikymuose vartojamos sąvokos. Pateikiama pagrindinė GA teorema ir grandinių, kurios sudaro GA teorinį pagrindą, teorija. Aptariami konceptualūs GA privalumų ir trūkumų klausimai.

1.1. Paprastas genetinis algoritmas

Genetinių algoritmų teorijos pagrindus savo pagrindiniame darbe suformulavo J. G. Holland, o vėliau juos sukūrė daugybė kitų tyrinėtojų. Žymiausia ir dažniausiai cituojama D. Goldbergo monografija, kurioje sistemingai pateikiami pagrindiniai rezultatai ir sritys praktinis pritaikymas GA.

GA naudojami principai ir terminija, pasiskolinta iš biologijos mokslas– genetika. GA kiekvienas asmuo yra potencialus tam tikros problemos sprendimas. Klasikiniame GA individą užkoduoja dvejetainių simbolių eilutė – chromosoma, kurios kiekvienas bitas vadinamas genu. Asmenų rinkinys – galimi sprendimai – sudaro populiaciją. Optimalaus ar neoptimalaus problemos sprendimo paieška vykdoma populiacijos evoliucijos procese, t.y. nuoseklus vieno konvertavimas baigtinis rinkinys sprendimus kitam naudojant genetinius reprodukcijos, kryžminimo ir mutacijos operatorius. EV naudoja mechanizmus natūrali evoliucija remiantis šiais principais:

1. Pirmasis principas grindžiamas Darvino tvirtiausios ir natūralios atrankos išlikimo koncepcija, kurią jis suformulavo 1859 m. knygoje „Rūšių kilmė natūralios atrankos būdu“. Anot Darvino, asmenys, kurie geriau sugeba spręsti savo aplinkos problemas, turi didesnę tikimybę išgyventi ir dažniau daugintis (daugintis). Genetiniuose algoritmuose kiekvienas asmuo yra tam tikros problemos sprendimas. Analogiškai su šiuo principu asmenys su geriausios vertybės tikslinės (fitneso) funkcijos turi didelę galimybę išgyventi ir daugintis. Šio principo formalizavimą, kaip matysime vėliau, įgyvendina reprodukcijos operatorius.
2. Antrasis principas kyla iš to, kad palikuonių chromosoma susideda iš dalių, gautų iš tėvų chromosomų. Šį principą 1865 metais atrado G. Mendelis. Jo įforminimas suteikia pagrindą pervažos operatoriui.
3. Trečiasis principas grindžiamas mutacijos koncepcija, kurią 1900 m. atrado de Vres. Iš pradžių šis terminas buvo vartojamas apibūdinti reikšmingiems (staigiems) palikuonių savybių pokyčiams ir jų įgijimui savybių, kurių nebuvo jų tėvams. Analogiškai su šiuo principu, genetiniai algoritmai naudoja panašų mechanizmą, kad dramatiškai pakeistų palikuonių savybes ir taip padidintų populiacijos (sprendimų rinkinio) individų įvairovę (kintamumą).

Šie trys principai sudaro EV šerdį. Juos naudojant populiacija (daugybė tam tikros problemos sprendimų) evoliucionuoja iš kartos į kartą.

Dirbtinės populiacijos evoliucija – kelių tam tikros problemos sprendimų paieška – gali būti formaliai aprašyta algoritmo forma, kuri pateikta 1.1 pav.

GA gauna optimizavimo uždavinio parametrų rinkinį ir užkoduoja juos baigtinio ilgio sekomis tam tikroje baigtinėje abėcėlėje (paprasčiausiu atveju dvejetainėje abėcėlėje „0“ ir „1“).

Iš anksto paprastas GA atsitiktinai sukuria pradinę chromosomų (stygų) populiaciją. Tada algoritmas generuoja kitą kartą (populiaciją), naudodamas šiuos tris pagrindinius genetiniai operatoriai:

1. reprodukcijos operatorius (OR);
2. kirtimo operatorius (kryžimas, OK);
3. mutacijos operatorius (OM).

Genetiniai algoritmai nėra tik atsitiktinė paieška, jie efektyviai panaudoja evoliucijos procese sukauptą informaciją.

Sprendimo paieškos procese būtina išlaikyti balansą tarp šiuo metu gautų geriausių sprendimų „išnaudojimo“ ir paieškos erdvės išplėtimo. Įvairūs metodai paieškos sistemos šią problemą sprendžia įvairiais būdais.

Pavyzdžiui, gradiento metodai praktiškai pagrįsti tik geriausių srovės sprendimų naudojimu, o tai, viena vertus, padidina konvergencijos greitį, bet iš kitos pusės sukelia vietinių ekstremalių problemų. Taikant polinį metodą, visi naudoja atsitiktinės paieškos metodus