Genetiniai algoritmai intelektualiose sistemose. Genetiniai algoritmai arba kaip biologijos vadovėlis gali padėti optimizuoti funkcines galimybes

Vienas iš intelektualių sistemų uždavinių – rasti optimalų sprendimą: kai sistemai įtakos turi daug išorinių ir vidinių veiksnių, išmanusis įrenginys turi atsižvelgti į juos visus ir pasirinkti optimalus elgesys savo naudos požiūriu. Tarkime, jei esate sandėlio savininkas, turite atsižvelgti į daugybę faktorių (prekių vienetų savikaina, paklausa, įvairių prekių sandėliavimo sandėlyje kaštai ir kt.), kad sumažintumėte išlaidas ir gautumėte didžiausią pelną.

Kitas pavyzdys: važiuojate slidžiu keliu ir staiga jūsų automobilis pradeda slysti, už kelių metrų dešinėje yra stulpas ir priešpriešinio eismo juosta važiuoja sunkvežimis. Dėmesio klausimas: kaip išeiti iš situacijos su mažiausiai nuostolių, arba dar geriau – visai be jų. Yra daug faktorių, į kuriuos reikia atsižvelgti: jūsų greitis ir atvažiuojančio automobilio greitis, atstumas iki stulpo, slydimo „statumas“ ir kt. Ką turėčiau daryti? Duokite dujų, bandydami išlipti iš slydimo, arba stabdyti, o gal pabandykite atsargiai nuslysti į griovį, kad neatsitrenktumėte į stulpą. Variantų yra daug, o norint nustatyti optimaliausią, reikia išbandyti visas. Tebūnie taip kompiuterinis žaidimas- Galite išsaugoti ir žaisti, kol rezultatas jus tenkins. Tai yra optimalaus sprendimo paieška.

Sistemose dirbtinis intelektas išspręsti panašias užduotis taikyti .

Genetiniai algoritmai – adaptaciniai metodai paieška, kurios naudojamos funkcinio optimizavimo problemoms spręsti. Jie pagrįsti evoliucijos mechanizmais ir modeliais, ir genetiniai procesai biologiniai algoritmai.

Paprasčiau pasakykime: iš esmės genetinis algoritmas yra tų problemų sprendimų, kurių sprendimo neįmanoma rasti naudojant matematines formules. Tačiau paprastas sudėtingos daugiamatės problemos sprendimų išvardijimas užtrunka be galo ilgai. Todėl genetinis algoritmas neieško visų sprendimų, o tik geriausius. Algoritmas paima sprendimų grupę ir tarp jų ieško tinkamiausių. Tada jis juos šiek tiek pakeičia – gauna naujų sprendimų, tarp kurių vėl atrenka geriausius, o blogiausius išmeta. Taigi kiekviename darbo žingsnyje algoritmas parenka tinkamiausius sprendimus (atlieka atranką), manydamas, kad kitame žingsnyje (evoliucija) jie duos dar geresnius sprendimus.

Ką su tuo turi biologija?

Kaip jau suprantate, genetinių algoritmų teorijoje yra analogija tarp užduoties ir biologinis procesas. Taigi terminija...

Individualus– vienas problemos sprendimas.

Gyventojų skaičius— problemos sprendimų rinkinys. Algoritmo pradžioje atsitiktinai sugeneruojamas sprendimų rinkinys (pradinė populiacija). Šie sprendimai taps geresni (tobulės), kai algoritmas veiks tol, kol atitiks problemos sąlygas.

Ir iš karto paprasčiausias klasikinis pavyzdys. Tarkime, kad robotas turi apeiti šešis kontrolės punktus mažiausiai laiko. Atstumas nuo kiekvieno taško iki kiekvieno nurodomas kaip atstumo matrica.

Tai yra keliaujančio pardavėjo (keliautojo) problemos variantas – jis priklauso NP-pilno klasei, kitaip tariant, jo negalima išspręsti naudojant matematines formules.

Problemos sprendimas yra valdymo taškų perėjimo seka. Paimkime keletą galimi sprendimai(asmenys) – štai kas.

Sprendimo kokybės apibrėžimai

Fitneso funkcija– funkcija, lemianti populiacijos individų kokybę. Mūsų pavyzdyje tai bus atstumų nuo taško iki taško pasirinktame maršrute suma.

FP = P(1)+P(2)+P(3)+P(4)+P(5)+P(6),

čia P(1) ... P(6) – atstumas tarp taškų atitinkamame perėjime nuo atstumo matricos

Todėl turime rasti mažiausią atstumą, nei mažesnė vertė FP asmeniui, tuo geriau.

Apskaičiuokime fitneso funkcijas. Pirmajam asmeniui:

Likusius asmenis gauname tokiu pačiu būdu.

Evoliucijos procesas suvokiamas kaip „geresnių“ chromosomų gebėjimas daryti didesnę įtaką naujos populiacijos sudėčiai, pagrįsta ilgalaikiu išgyvenimu iš gausesnių palikuonių. Pagrindiniai evoliucinės paieškos etapai yra šie:

1. Konstruojama pradinė populiacija. Įvedamas kartos atskaitos taškas t = 0 Apskaičiuojamas kiekvienos populiacijos chromosomos tinkamumas, o tada apskaičiuojamas visos populiacijos tinkamumas.

2. Nustatykite t= t+1. Kryžminiam operatoriui įgyvendinti pasirenkami du tėvai (chromosomos). Jis atliekamas atsitiktinai, proporcingai tėvų prisitaikymui.

3. Susiformuoja palikuonių genotipas. Norėdami tai padaryti su duota tikimybe kryžminis operatorius atliekamas pasirinktų chromosomų genotipams. Tada su 0,5 tikimybe parenkamas vienas iš palikuonių P i (t) ir išsaugomas kaip naujos populiacijos narys. Po to inversijos operatorius nuosekliai taikomas P i (t), o tada mutacijos su nurodytomis tikimybėmis. Gautas palikuonio genotipas saugomas kaip P k (t).

4. Nustatomas chromosomų skaičius, kad jos būtų pašalintos iš populiacijos, kad jos dydis išliktų pastovus. Dabartinė populiacija atnaujinama pakeičiant pasirinktas chromosomas palikuonimis P k (t).

5. Fitnesas nustatomas ( objektyvią funkciją) ir visos gautos populiacijos vidutinio tinkamumo perskaičiavimas.

6. Jei t = t duota, tada eikite į 7, jei ne, tada eikite į 2.

7. Darbo pabaiga.

Šis algoritmas yra žinomas kaip supaprastintas „D Holland reprodukcinis planas“. Atkreipkite dėmesį, kad praktinėse problemose vietoj sąvokos „fitnesas“ vartojama „tikslinės funkcijos“ sąvoka.

Paprastą genetinį algoritmą (SGA) pirmasis aprašė D. Goldbergas, remdamasis D. Hollando darbais. Jo mechanizmas yra paprastas. Anksčiau PGA atsitiktinai generuodavo sekų populiaciją – chromosomas (alternatyvūs sutvarkyti ir netvarkingi sprendimai). Tada nukopijuojama chromosomų seka ir pertvarkomos jų dalys. Be to, PGA įgyvendina daug paprastų operacijų pradinėje populiacijoje ir generuoja naujus sprendimus.

PGA sudaro trys operatoriai:

reprodukcija;

kirsti;

Reprodukcija– procesas, kurio metu chromosomos yra kopijuojamos proporcingai jų CF vertei. Chromosomų, turinčių „geriausią“ CF vertę, kopijavimas turi didesnę tikimybę, kad bus įtrauktas į kitą kartą. Atsižvelgiant į Charleso Darwino evoliuciją, galima pastebėti, kad reprodukcijos operatorius (OR) yra dirbtinė natūralios atrankos versija - „tvirčiausio išlikimas“. Jis pateikiamas algoritmine forma įvairiais būdais. Paprasčiausias yra sukurti „ruletės rato“ modelį, kuriame kiekviena chromosoma turi lauką, proporcingą CF reikšmei.

Panagrinėkime D. Goldbergo pavyzdį: reikia rasti funkcijos f(x)=x 2 maksimumo reikšmę sveikajame intervale. Naudodami tradicinius metodus, galime keisti kintamojo x reikšmes, kol gauname maksimali vertė f(x).

Norėdami paaiškinti ir įdiegti PGA, sudarome šią lentelę:

2 lentelės stulpelyje. yra 4 chromosomos (pavaizduotos dvejetainiu kodu), sugeneruotos atsitiktinai. Kiekvienos chromosomos CF reikšmė (4 stulpelis) nustatoma kaip dvejetainio skaičiaus dešimtainės kodo reikšmės kvadratas, kuris pateikiamas chromosomoms antrajame lentelės stulpelyje. Tada bendra visų chromosomų CF vertė yra 890. Chromosomų atrankai naudojamas dauginimo operatorius, pagrįstas ruletės ratu. Paveiksle ruletės rato laukai atitinka kiekvienos chromosomos CF reikšmę procentais. Vienoje kartoje ruletės ratas sukasi, o sustojus jo rodyklė nustato chromosomą, pasirinktą įgyvendinti kitą operatorių. Akivaizdu, kad chromosoma, turinti didelę CF vertę dėl OR, ne visada bus pasirinkta tolimesnėms transformacijoms.

Pavyzdžiui, ruletės ratas

Remiantis OR įgyvendinimu, chromosomos parenkamos naudoti OR. Kryžminimo operatorius paprastai vykdomas 3 žingsniais, vienu iš aukščiau aprašytų OK. Lūžio taškas k parenkamas atsitiktinai tarp 1 ir skaičiaus, lygaus chromosomos ilgiui atėmus vieną, tai yra intervale (1, L-1). Chromosomos ilgis L yra skaičius reikšmingi skaičiai jos kode. Nagrinėjamoje pavyzdinėje lentelėje kiekvienos chromosomos ilgis yra penki (L=5). Remiantis OK, sukuriamos dvi naujos chromosomos, keičiant jų dalis tarp padėčių (k+1) ir L, atitinkamai.

Pavyzdžiui, apsvarstykite 1 ir 2 chromosomas iš pradinės populiacijos. Tegu k=1. Tada gauname:

P 1 0 | 1 1 0 0 Prieš naudojant kryžminį operatorių

P 2 1 | 0 0 0 0,

-----------------

P 1 0 0 0 0 0 Pritaikius krosoverio operatorių

P 2 1 1 1 0 0.

PGA darbas prasideda nuo reprodukcijos. Naujos kartos chromosomos parenkamos sukant ruletės ratą. Pavyzdyje ruletės ratas sukasi 4 kartus. Šis skaičius atitinka pradinės populiacijos galią.

Santykio dydis
vadinama kopijų (chromosomų) pasirinkimo tikimybe įgyvendinant atkūrimo operatorių ir reiškia:

čia f i (x) yra CF reikšmė i-oji chromosoma populiacijoje suma f(x) yra bendra visų populiacijos chromosomų CF vertė. Dydis
dar vadinama normalizuota atrankos tikimybe. Numatomas kopijų skaičius

I-oji chromosoma po OR įgyvendinimo nustatoma pagal formulę:

Kur
ištirtų chromosomų skaičius, N G įtrauktas į N.

Tikėtinas chromosomos Pi kopijų skaičius, pereinantis į kitą kartą, taip pat kartais nustatomas remiantis išraiška:

.

Kur
vidutinė CF reikšmė visai populiacijai.

Tuomet nagrinėjamame pavyzdyje numatomas pirmosios chromosomos kopijų skaičius iš lentelės yra 0,164 = 0,64 kopijos, antrosios – 0,294 = 1,16 kopijos, trečiosios – 0,054 = 0, 2 ir galiausiai ketvirtam0,54=2. Naudojant monetos metimo modelį, galima nustatyti gautų kopijų skaičių. Pavyzdžiui, (žr. lentelės 7 stulpelį) chromosomos P 1 ir P 2 gauna 1 kopiją, chromosoma P 4 gauna 2 kopijas, o 3 chromosoma negauna jokių kopijų. Palyginus šį rezultatą su numatomu kopijų skaičiumi, gauname tai, ką gamina „geriausios“ chromosomos didesnis skaičius kopijų, įdiegus dauginimo operatorių lieka „vidutiniai“, o „blogi“ ištrinami.

Nagrinėjamu pavyzdžiu sukursime lentelę. 2 stulpelyje rodoma 4 chromosomų atsiradimas po reprodukcijos operatoriaus vykdymo. 3 stulpelyje yra sąrašai chromosomų porų, kurios atsitiktinai parinktos kryžminiam operatoriui įgyvendinti. 4 stulpelyje nurodomas chromosomos pjūvio taško padėties numeris. 5 stulpelyje rodoma 4 chromosomų atsiradimas įvykdžius kryžminimo operatorių. 6 stulpelyje rodomos dešimtainės kodo reikšmės dvejetainis skaičius kiekviena chromosoma 5 stulpelyje. 7 stulpelyje pateikiama f(x) reikšmė kiekvienai iš 4 naujos populiacijos chromosomų. 5 eilutėje rodoma naujos populiacijos chromosomų bendra CF vertė, 6 eilutėje – vidutinė jų CF reikšmė, o 7 eilutėje – maksimali naujos populiacijos chromosomų CF vertė.

Pritaikius crossing over operatorių populiacijai, gautai įdiegus reprodukcijos operatorių (2 lentelės stulpelis), gauname naują chromosomų populiaciją (lentelės 5 stulpelis). Iš esmės kryžminimo operatorius gali būti naudojamas bet kokį skaičių kartų. Po vienos kartos PGA pagerėjo visi rodikliai: vidutinė ir maksimali CF reikšmės.

Toliau, pagal PGA vykdymo schemą, yra įdiegtas mutacijos operatorius. Yra daugybė mutacijų operatorių tipų. Atkreipkite dėmesį, kad šie operatoriai atitinka tam tikros rinkinio elementų permutacijas. Akivaizdu, kad esant mažam chromosomos ilgiui L (apie 10–20), galima atlikti pilną paiešką per priimtiną laiką ir rasti geriausius sprendimus. Kai L padidėja iki 50–200 ir daugiau, sunku atlikti pilną paiešką, reikia kitų paieškos mechanizmų. Čia į pagalbą ateina nukreipta atsitiktinė paieška, kuri įgyvendinama PGA pagrindu.

Atkreipkite dėmesį, kad pasaulinis maksimumas galėjo būti rastas kryžminio diegimo etape. Norėdami tai padaryti, reikėjo padidinti paieškos erdvę. Pavyzdžiui, jei lentelės 5 stulpelyje. atrinkę chromosomas P 2 ir P 4 ir atlikę tarp jų kirtimo operatorių (taškas OK parenkamas atsitiktinai ir lygus 3), gauname:

P 2: 1 0 1 | 1 1 (TsF-23)

P 4: 1 1 1 | 0 0 (CF-28)

P 2 : 1 0 1 0 0 (CF-20)

P 4 : 1 1 1 1 1 (CF-31).

Sprendimas P 4 , gautas atsitiktinai pritaikius OK, yra geriausias rezultatas (pasaulinis optimalus).

Kaip minėta pirmiau, genetiniuose algoritmuose galima išskirti du pagrindinius chromosomų dauginimosi mechanizmus:

palikuonys yra tikslios tėvų kopijos (nelytinis dauginimasis be mutacijos);

palikuonys turi „didelių“ skirtumų nuo savo tėvų.

Genetiniai algoritmai daugiausia naudoja šių mechanizmų derinius. Atkreipkite dėmesį, kad į inžinerinės problemos ai, pradinę populiaciją galima pasirinkti bet kokiu būdu, pavyzdžiui, imituojant „monetos metimą“ (galvos = 1, uodegos = 0). Tada atgaminimo operatorius atliekamas imituojant ruletės rato judėjimą. Kryžminis operatorius skaičiavimo uždaviniuose paprastai atliekamas dvejetainiu dviejų monetų pozicijų dekodavimu. Jai įgyvendinti dažnai naudojami kiti OK tipai ir kitos technologijos. Leidžiama, kad OK tikimybė būtų lygi Pr(OK) = 1,0 arba mažesnė, OM tikimybė – Pr(OM) = 0,01 ar daugiau. IN bendras atvejis tikimybė panaudoti mutacijos operatorių priklauso nuo žinių apie sprendžiamą problemą.

Štai kitas standartinis genetinio algoritmo tipas, aprašytas L. Daviso:

Chromosomų populiacijos inicijavimas.

Kiekvienos chromosomos svarbos populiacijoje įvertinimas.

Naujų chromosomų kūrimas kertant esamas chromosomas; mutacijų ir rekombinacijos operatorių taikymas.

Chromosomų pašalinimas iš populiacijos, kad būtų vietos naujoms chromosomoms.

Naujų chromosomų verčių įvertinimas ir įtraukimas į populiaciją.

Jei nustatytas laikas algoritmo įgyvendinimas, baigtas, sustokite ir grįžkite į geriausią chromosomą, jei ne, pereikite prie 3.

Algoritmo pabaiga.

Lyginant D. Goldbergo, D. Hollando ir L. Daviso PGA aprašymus, akivaizdu, kad jie įgyvendina vieną pagrindinę evoliucijos modeliavimo idėją su tam tikromis modifikacijomis. Tačiau atkreipkite dėmesį, kad šie pakeitimai gali labai paveikti galutinę sprendimo kokybę.

Štai modifikuoto PGA pavyzdys:

1. Pradinės sprendimų visumos sukūrimas.

2. Populiacijos modeliavimas (kiekvienos chromosomos CF nustatymas).

3. Kol bus baigtas reikiamas kartų skaičius arba nepasibaigs arba nebus rastas algoritmui įgyvendinti nurodytas laikas optimalią vertę TF (jei žinoma):

a) elementų parinkimas reprodukcijai;

Taikymas:

b) krosoverio operatorius vaikams kurti;

c) mutacijos operatorius;

d) inversijos operatorius;

e) perkėlimo operatorius;

f) perkėlimo operatorius;

g) atskyrimo operatorius;

h) viršūnių pašalinimo operatorius;

i) viršūnių įterpimo operatorius;

j) tėvų ir palikuonių rekombinacija kuriant naują kartą;

k) mažinimo operatorius.

4. Naujos kartos diegimas.

Naujos GA modifikacijos gali būti kuriamos derinant, pavyzdžiui, taškus „b – l“ arba jų dalinį pašalinimą, ar jų pertvarkymą, taip pat remiantis adaptacijos principų taikymu evoliucinei paieškai valdyti.

Įvadas į aksiomatinė teorija genetiniai algoritmai

Suformuluokime genetinių algoritmų aprašymą mokslinės teorijos forma. Atkreipkite dėmesį, kad mokslinės teorijos konstravimo metodas, kuris remiasi pradinėmis nuostatomis, vadinamomis aksiomomis, o visi kiti teorijos teiginiai gaunami kaip loginės aksiomų pasekmės, vadinamas aksiominis metodas.Aksioma - pozicija, priimta be įrodymų kaip duotosios teorijos atskaitos taškas. Svarbiausia jame yra interpretacijos metodas. Tada galima sukurti tokią pagrindinę genetinių algoritmų teoriją.

Tegul kiekviena pradinė GA aksiomatinės teorijos sąvoka ir ryšys yra susieti su kokiu nors konkrečiu matematiniu objektu. Tokių objektų kolekcija vadinama interpretacijos laukas. Kiekvienas GA teorijos teiginys U yra susietas su kokiu nors teiginiu U* apie interpretacijos lauko elementus, kurie gali būti teisingi arba klaidingi. Tada galime pasakyti, kad GA teorijos teiginys U yra atitinkamai teisingas arba klaidingas. Pats aiškinimo laukas ir jo savybės paprastai yra kitos PGA teorijos objektas, kuri ypač gali būti aksiomatinė. Šis metodas leidžia įrodyti tokius teiginius: jei GA teorija yra nuosekli, tada PGA teorija taip pat yra nuosekli.

Tegul GA teorija PGA teorijoje aiškinama taip, kad visos GA teorijos aksiomos A i būtų aiškinamos tikrais PGA teorijos sprendimais A i *. Tada kiekviena GA teorijos teorema, tai yra kiekvienas teiginys A, logiškai išvestas iš GA aksiomų A i, PGA interpretuojamas kokiu nors teiginiu A *, išvestu PGA iš A i * aksiomų A interpretacijų. aš ir, vadinasi, tiesa.

Interpretacijos metodas leidžia išspręsti ir aksiomų sistemų nepriklausomumo klausimą: įrodyti, kad GA teorijos aksioma A nepriklauso nuo kitų šios teorijos aksiomų, tai yra iš jų neišvedama, todėl , būtina norint gauti visą šios teorijos apimtį, pakanka sukurti tokią GA interpretaciją, kurioje aksioma A būtų klaidinga, o visos kitos šios teorijos aksiomos būtų teisingos. Aksiomatinės teorijos sampratos patikslinimas yra sąvoka formali sistema. Tai leidžia vaizduoti matematines teorijas kaip tikslius matematinius objektus ir konstruoti bendroji teorija arba tokių teorijų metateorija. Bet kuri formali sistema yra konstruojama kaip tiksliai apibrėžta išraiškų klasė – formulės, kuriose tam tikru tikslu išskiriamas formulių poklasis, vadinamas tam tikros formalios sistemos teoremomis. Tuo pačiu metu formalios sistemos formulės neturi tiesioginės prasmės. Jie gali būti pastatyti iš savavališkų ženklų ir simbolių. Bendra schema savavališkos formalios GA sistemos sukūrimas yra toks:

GA sistemos kalba: loginės algebros aparatas;

1. aibių teorija; grafų teorija, algoritmų teorija, pagrindiniai biologijos ir sistemų teorijos principai.

   Abėcėlė – elementarių sistemos simbolių sąrašas: dvejetainis, dešimtainis, abėcėlė, Fibonači ir kt.

Formavimo taisyklės (sintaksė), pagal kurias GA teorijos formulės sudaromos iš elementarių simbolių:

kūrimo evoliucijos modeliai;

populiacijų kūrimas;

skaitmeninio fondo kūrimas;

genetinių operatorių vystymas;

gyventojų dauginimasis;

populiacijų rekombinacija;

sumažinimas;

prisitaikymas.

Elementariųjų simbolių seka laikoma formule tada ir tik tada, kai ją galima sudaryti naudojant formavimo taisykles. GA sistemos aksiomos. Yra tam tikras rinkinys galutinės formulės

, kurios vadinamos sistemos aksiomomis. GA yra daug aksiomų rinkinių. Pavyzdžiui, pagrindinis aksiomų rinkinys yra toks:

Visuomenė sudaroma atsitiktinai.

Reprodukcijos operatoriaus egzekucija vykdoma „ruletės rato“ pagrindu.

Privalomas kryžminimo ir mutacijos operatorių naudojimas.

Po kiekvienos kartos populiacijos dydis išlieka pastovus.

Keičiasi populiacijos dydis.

Keičiasi į kitą kartą perkeliamų kopijų (sprendimų) skaičius.

GA išvedimo taisyklės. Visų sistemos formulių aibėje fiksuota baigtinė predikatų aibė П 1 , П 2 ,…, П k. Tegu P (x 1 ,…,x ni +1) yra bet kuris iš šių predikatų (n i 0), jei pateiktoms formulėms F 1 ,…,F ni +1 teiginys P (F 1 ,…,F ni + 1 ) yra tiesa, tada jie sako, kad formulė F ni +1 tiesiogiai išplaukia iš formulių F 1 ,...,F ni +1 pagal taisyklę П i .

1, 2, 3 užduotis išsemia formalios GA sistemos, kaip tikslaus matematinio objekto, užduotį. Šiuo atveju tikslumo laipsnis nustatomas pagal abėcėlės, formavimo ir išvados taisyklių tikslumo lygį. GA sistemos išvestinė yra bet kokia baigtinė formulių seka, kurioje kiekviena formulė yra arba GA sistemos aksioma, arba tiesiogiai išplaukia iš bet kokių prieš ją einančių formulių (šios sekos) pagal vieną iš sistemos išvedimo taisyklių P i.

Bet kuri konkreti matematinė GA teorija gali būti išversta į tinkamos formalios sistemos kalbą taip, kad kiekvienas klaidingas ar tikras GA teorijos sakinys būtų išreikštas kokia nors sistemos formule. Aiškinimo metodas leidžia nustatyti santykinio nuoseklumo faktą, tai yra įrodyti tokius teiginius kaip: „jei GA teorija yra nuosekli, tada PGA teorija taip pat yra nuosekli“. Apskritai nuoseklumo problema neišspręsta ir yra viena iš pagrindinių matematikoje.

Siūlomos kelios pagrindinės evoliucinės ir vietinės paieškos metodų sąveikos strategijos:

„paieška – evoliucija“;

„evoliucija – paieška“;

„paieška – evoliucija – paieška“;

„evoliucija – paieška – evoliucija“.

Atminkite, kad tokio tipo strategijas galima kurti hierarchiškai bet kokio sudėtingumo lygiu. Pavyzdžiui, „evoliucija – paieška – evoliucija – paieška – evoliucija – paieška“ ir kt. Atkreipkite dėmesį, kad tokia konstrukcija priklauso nuo turimų skaičiavimo išteklių ir laiko, skirto galutiniam sprendimui gauti.

Pirmuoju atveju bet kuris iš aprašytų paieškos algoritmų ar jų derinių nustato vieną ar porą alternatyvių problemos sprendimų. Remiantis šiais sprendimais, sukuriama populiacija, kuriai taikoma viena iš evoliucijos schemų. Tada procesas tęsiasi iteratyviai, kol pasiekiamas sustabdymo kriterijus.

Antruoju atveju sudaroma populiacija ir įgyvendinama viena iš evoliucinių schemų. Geriausias sprendimas analizuojamas ir (jei įmanoma) tobulinamas vienu iš paieškos algoritmų. Toliau procesas atliekamas kaip ir pirmuoju atveju. Kitais atvejais rezultatų paieškos procesas yra panašus.

Išvados

Genetiniai algoritmai yra paieškos algoritmai, pagrįsti natūralios atrankos ir natūralios genetikos mechanizmais. Jie yra galinga strategija, padedanti išvengti vietinių optimalių sąlygų. Jį sudaro lygiagretus rinkinio apdorojimas alternatyvių sprendimų, sutelkiant paiešką į perspektyviausius iš jų.

Be to, periodiškai kiekvienoje iteracijoje galima atlikti stochastinius mažiau perspektyvių sprendimų pakeitimus.

Yra keturi pagrindiniai skirtumai tarp GA ir optimizavimo metodų:

tiesioginis kodo konvertavimas;

paieška iš gyventojų, o ne iš vieno taško;

paieška per elementus (akloji paieška);

paieška, kuri naudoja stochastinius ir modifikuotus operatorius, o ne deterministines taisykles.

GA naudojimas sprendžiant inžinerines problemas leidžia sumažinti skaičiavimų apimtį ir laiką, supaprastinti funkcijų modeliavimą, sumažinti modeliavimo klaidų skaičių. Gamta stebina savo sudėtingumu ir visų apraiškų turtingumu. Pavyzdžiai yra sudėtingi socialines sistemas , imuninės ir nervų sistemos, sudėtingi ryšiai tarp rūšių. Tai tik dalis stebuklų, kurie išryškėjo, kai giliau tyrinėjame save ir mus supantį pasaulį. Mokslas yra viena iš nuoseklių tikėjimo sistemų, kuriomis stengiamės paaiškinti tai, ką stebime, taip keisdami save, kad prisitaikytume prie naujos informacijos, gautos iš išorinis pasaulis . Daug ką matome ir stebime, galima paaiškinti vieninga teorija

: evoliucijos per paveldimumą, kintamumą ir atranką teorija. Evoliucijos teorija nuo pat jos atsiradimo turėjo įtakos žmonių pasaulėžiūrai. Teorija, kurią Charlesas Darwinas pristatė 1859 m. veikale „Rūšių kilmė“, buvo šio pokyčio pradžia. Daugybė sričių dabar mėgaujasi minties laisve atmosferoje, kuri daug priklauso nuo evoliucijos ir vystymosi teorijos sukeltos revoliucijos. Tačiau Darvinas, kaip ir daugelis jo amžininkų, manančių, kad natūrali atranka yra vystymosi pagrindas, negalėjo neklysti. Pavyzdžiui, jis negalėjo parodyti paveldėjimo mechanizmo, kuris palaiko kintamumą. Jo hipotezė apie pangenezę pasirodė neteisinga. Tai buvo penkiasdešimt metų, kol paveldimumo teorija pradėjo plisti visame pasaulyje, o prieš trisdešimt metų „evoliucinė sintezė“ sustiprino ryšį tarp evoliucijos teorijos ir palyginti jauno genetikos mokslo. Tačiau Darvinas nustatė pagrindinį vystymosi mechanizmą: atranką kartu su kintamumu arba, kaip jis pavadino, „nusileidimą su modifikavimu“. Daugeliu atvejų specifinės savybės vystymasis per variaciją ir atranką vis dar nėra tikras, tačiau pagrindiniai mechanizmai paaiškina neįtikėtinai platų gamtoje stebimų reiškinių spektrą.

Taigi nenuostabu, kad kompiuterių mokslininkai įkvėpimo ėmėsi evoliucijos teorijos. Labai patraukli buvo galimybė, kad skaičiavimo sistema, aprūpinta paprastais variacijos ir atrankos mechanizmais, galėtų veikti analogiškai gamtos sistemų evoliucijos dėsniams. Ši viltis paskatino sukurti daugybę skaičiavimo sistemų, sukurtų remiantis šiais principais natūrali atranka.

Evoliucinio skaičiavimo istorija prasidėjo sukūrus daugybę skirtingų nepriklausomų modelių. Pagrindiniai iš jų buvo Olandijos genetiniai algoritmai ir klasifikavimo sistemos, išleistos šeštojo dešimtmečio pradžioje ir sulaukusios visuotinio pripažinimo po to, kai buvo išleista knyga, kuri tapo klasika šioje srityje - „Prisitaikymas natūraliuose ir dirbtinės sistemos"("Adaptacija natūraliose ir dirbtinėse sistemose", 1975). Aštuntajame dešimtmetyje atsitiktinės paieškos teorijos rėmuose L. A. Rastriginas pasiūlė daugybę algoritmų, naudodamasis individų bioninio elgesio idėjomis. Šių idėjų raida buvo atspindėta. evoliucinio modeliavimo darbų serijoje Neimarkas Yu.I Nepriklausomus automatus, imituojančius individų programavimo procesus, pristatė Fogelis ir Walshas, ​​nepaisant jų požiūrio skirtumų, kiekviena iš šių „mokyklų“ pasinaudojo gamtoje egzistuojančiais principais ir juos supaprastino. gali būti įdiegtas kompiuteryje.

Pagrindinis sunkumas, susijęs su galimybe kurti skaičiavimo sistemas, pagrįstas natūralios atrankos principais ir naudojant šias sistemas taikomosiose problemose, yra tai, kad natūralios sistemos yra gana chaotiškos, o visi mūsų veiksmai iš tikrųjų turi aiškią kryptį. Kompiuterį naudojame kaip įrankį tam tikroms problemoms, kurias patys suformuluojame, išspręsti ir orientuojamės į tai, kad jas kuo greičiau užbaigtume minimaliomis sąnaudomis. Natūralios sistemos neturi tokių tikslų ar apribojimų, bent jau mums nėra akivaizdžių. Išlikimas gamtoje nėra nukreiptas į kažkokį fiksuotą tikslą, o evoliucija juda į priekį bet kuria kryptimi.

Tai gali būti didelis apibendrinimas, bet aš manau, kad pastangos modeliuoti evoliuciją panašiai natūralios sistemos, dabar galima suskirstyti į dvi dalis didelės kategorijos: 1) sistemos, sukurtos remiantis biologiniais principais. Jie buvo sėkmingai naudojami sprendžiant tokias problemas kaip funkcinis optimizavimas ir gali būti lengvai aprašytas nebiologine kalba, 2) sistemos, kurios yra biologiškai tikroviškesnės, bet nepasirodė ypač naudingos taikomąja prasme. Jie panašesni į biologines sistemas ir mažiau nukreipti (arba visai nenukreipti). Jie turi kompleksinį ir įdomus elgesys, ir, matyt, netrukus ras praktinį pritaikymą.

Žinoma, praktiškai negalime šių dalykų taip griežtai atskirti. Šios kategorijos yra tiesiog du poliai, tarp kurių yra skirtingos skaičiavimo sistemos. Arčiau pirmojo poliaus yra evoliuciniai algoritmai, tokie kaip evoliucinis programavimas, genetiniai algoritmai ir evoliucijos strategijos. Arčiau antrojo poliaus yra sistemos, kurias galima priskirti prie Dirbtinės gyvybės.

Žinoma, evoliucija biologines sistemas nėra vienintelis „įkvėpimo šaltinis“ naujų modeliavimo metodų kūrėjams natūralių procesų. Pavyzdžiui, neuroniniai tinklai yra pagrįsti smegenų neuronų elgesio modeliavimu. Jie gali būti naudojami daugeliui klasifikavimo užduočių, tokių kaip modelio atpažinimo užduotys, mašininis mokymasis, vaizdo apdorojimas ir kt. Jų taikymo sritis iš dalies sutampa su GA taikymo sritimi. Imituotas atkaitinimas yra dar viena paieškos technika, pagrįsta fiziniais, o ne biologiniais procesais.

Genetinių algoritmų (GA) idėja atsirado gana seniai (1950-1975), tačiau iš tikrųjų jie tapo tyrimo objektu tik m. paskutiniais dešimtmečiais. Šios srities pradininku laikomas D. Hollandas, daug pasiskolinęs iš genetikos ir pritaikęs ją kompiuteriai. GA plačiai naudojami dirbtinio intelekto sistemose, neuroniniai tinklai ir optimizavimo problemos.

Evoliucinės paieškos

Genetinių algoritmų modeliai buvo sukurti remiantis gamtos evoliucija ir atsitiktiniais paieškos metodais. Šiuo atveju atsitiktinė paieška yra paprasčiausios evoliucijos funkcijos įgyvendinimas – atsitiktinės mutacijos ir vėlesnė atranka.

Evoliucinės paieškos su matematinis taškas vizija reiškia ne ką kita, kaip esamo transformaciją baigtinis rinkinys sprendimus į naują. Už šį procesą atsakinga funkcija yra genetinė paieška. Pagrindinis skirtumas tarp šio algoritmo ir atsitiktinės paieškos yra aktyvus naudojimas iteracijų (kartojimų) metu sukaupta informacija.

Kodėl reikalingi genetiniai algoritmai?

GA persekiojamas sekančius tikslus:

• paaiškinti prisitaikymo mechanizmai tiek natūralioje aplinkoje, tiek intelektinių tyrimų (dirbtinėje) sistemoje;
• evoliucinių funkcijų modeliavimas ir jų pritaikymas efektyvi paieškaįvairių problemų sprendimai, daugiausia optimizavimo.

Įjungta šiuo metu genetinių algoritmų esmė ir modifikuotos jų versijos gali būti vadinamos paieška veiksmingi sprendimai atsižvelgiant į rezultato kokybę. Kitaip tariant, rasti geriausią našumo ir tikslumo pusiausvyrą. Taip nutinka dėl gerai žinomos paradigmos „tvirčiausio individo išgyvenimas“ neaiškiomis ir neaiškiomis sąlygomis.

GA savybės

Išvardinkime pagrindinius skirtumus tarp GA ir daugelio kitų metodų, kaip rasti optimalų sprendimą.

• darbas su tam tikru būdu užkoduotais užduočių parametrais, o ne tiesiogiai su jais;
• sprendimo paieška vyksta ne tikslinant pradinį aproksimaciją, o įvairiuose galimuose sprendimuose;
• naudojant tik tikslinę funkciją, nesiimant jos išvestinių ir modifikacijų;
• tikimybinio požiūrio į analizę taikymas, o ne griežtai deterministinis.

Veiklos kriterijai

Genetiniai algoritmai atlieka skaičiavimus pagal dvi sąlygas:

1. Vykdymas duotas numeris iteracijos.
2. Rasto sprendimo kokybė atitinka keliamus reikalavimus.

Jei įvykdoma viena iš šių sąlygų, genetinis algoritmas nustos atlikti tolesnius iteravimus. Be to, GA naudojimas įvairiose srityse sprendimų erdvė leidžia jiems atlikti daug geresnį darbą ieškant naujų sprendimų, turinčių tinkamesnes tikslinių funkcijų reikšmes.

Pagrindinė terminija

Dėl to, kad GA yra pagrįsti genetika, tada dauguma terminija ją atitinka. Bet koks genetinis algoritmas veikia remiantis pradine informacija. Daugelis pradines vertes yra populiacija P t = (n 1, n 2, ..., n n), kur n i = (g 1, ..., g v). Pažiūrėkime atidžiau:

• t yra iteracijos skaičius. t 1, ..., t k - reiškia algoritmo iteracijas nuo skaičiaus 1 iki k, o kiekvienoje iteracijoje sukuriama nauja sprendinių populiacija.
• n yra populiacijos dydis P t .
• p 1, ..., p i – chromosoma, individas arba organizmas. Chromosoma arba eilutė yra užkoduota genų seka, kurių kiekvienas turi serijos numeris. Reikia turėti omenyje, kad chromosoma gali būti ypatingas individo (organizmo) atvejis.
• g v yra genai, kurie yra užkoduoto tirpalo dalis.
• Lokusas yra chromosomoje esančio geno serijos numeris. Alelis yra geno reikšmė, kuri gali būti skaitmeninė arba funkcinė.

Ką reiškia „užkoduota“ GA kontekste? Paprastai bet kokia reikšmė užkoduojama pagal tam tikrą abėcėlę. Paprasčiausias pavyzdys yra skaičių konvertavimas iš dešimtainės skaičių sistemos į dvejetainį vaizdavimą. Taigi abėcėlė vaizduojama kaip rinkinys (0, 1), o skaičius 157 10 bus užkoduotas 10011101 2 chromosomos, susidedančios iš aštuonių genų.

Tėvai ir palikuonys

Tėvai yra elementai, parenkami pagal tam tikrą sąlygą. Pavyzdžiui, dažnai tokia sąlyga yra atsitiktinumas. Pasirinkti elementai per kryžminimo ir mutacijos operacijas generuoja naujus, kurie vadinami palikuonimis. Taigi, įgyvendindami vieną genetinio algoritmo iteraciją, tėvai sukuria naują kartą.

Galiausiai, evoliucija šiame kontekste vyks kartų kaita, iš kurių kiekviena nauja skiriasi chromosomų rinkiniu, kad būtų geresnis fizinis pasirengimas, tai yra, tinkamesnis atitikimas nurodytoms sąlygoms. Bendras genetinis fonas evoliucijos procese vadinamas genotipu, o ryšio tarp organizmo ir išorinę aplinką- fenotipas.

Fitneso funkcija

Genetinio algoritmo magija slypi fitneso funkcijoje. Kiekvienas individas turi savo reikšmę, kurią galima sužinoti per adaptacijos funkciją. Ji pagrindinė užduotis yra įvertinti šias vertes įvairiems alternatyviems sprendimams ir pasirinkti geriausią. Kitaip tariant, tinkamiausias.

IN optimizavimo problemos fitneso funkcija vadinama tiksline funkcija, valdymo teorijoje ji vadinama klaida, žaidimo teorijoje - išlaidų funkcija ir tt Kas tiksliai bus pateikta kaip fitneso funkcija, priklauso nuo sprendžiamos problemos.

Galų gale galime daryti išvadą, kad genetiniai algoritmai analizuoja individų, organizmų ar chromosomų populiaciją, iš kurių kiekvieną atstovauja genų derinys (kai kurių reikšmių rinkinys), ir ieško optimalaus sprendimo, transformuodami populiacijos individus. dirbtinė evoliucija tarp jų.

Nukrypimai viena ar kita kryptimi atskiri elementai apskritai jie atitinka normalus įstatymas kiekių pasiskirstymai. Tuo pačiu metu GA užtikrina savybių, iš kurių labiausiai prisitaikiusios yra fiksuotos, paveldimumą, taip užtikrinant geresnę populiaciją.

Pagrindinis genetinis algoritmas

Žingsnis po žingsnio išskaidykime paprasčiausią (klasikinę) GA.

1. Pradinių verčių inicijavimas, tai yra pirminės populiacijos, individų, su kuriais vyks evoliucija, nustatymas.
2. Kiekvieno individo pirminio tinkamumo nustatymas populiacijoje.
3. Algoritmo iteracijų stabdymo sąlygų tikrinimas.
4. Naudojant pasirinkimo funkciją.
5. Genetinių operatorių taikymas.
6. Naujos populiacijos kūrimas.
7. 2–6 žingsniai kartojami kilpa, kol baigsite būtina sąlyga, po kurio atrenkamas labiausiai prisitaikęs individas.

Trumpai apžvelgsime mažiau akivaizdžias algoritmo dalis. Darbo nutraukimui gali būti dvi sąlygos:

1. Iteracijų skaičius.
2. Sprendimo kokybė.

Genetiniai operatoriai yra mutacijos operatorius ir kryžminimo operatorius. Mutacija su tam tikra tikimybe pakeičia atsitiktinius genus. Paprastai mutacijos tikimybė yra maža skaitinė reikšmė. Pakalbėkime plačiau apie genetinio algoritmo „perėjimo“ procedūrą. Tai atsitinka iki vadovaudamiesi tokiu principu:

1. Kiekvienai tėvų porai, turinčiai L genų, atsitiktinai parenkamas kirtimo taškas Tsk i.
2. Pirmasis palikuonis susidaro susijungus su pirmojo tėvo genais [Tsk i+1; L] antrojo tėvo genai.
3. Antrasis vaikas sukonstruotas atvirkščiai. Dabar pirmojo tėvo genai yra pridedami prie antrojo tėvo genų pozicijose [Tsk i+1; L].

Trivialus pavyzdys

Išspręskime problemą naudodami genetinį algoritmą, naudodami asmens paieškos pavyzdį maksimalus skaičius vienetų. Tegul individas susideda iš 10 genų. Nustatykime pirminę aštuonių asmenų populiaciją. Akivaizdu, kad geriausias asmuo turėtų būti 1111111111. Sukurkime GA, kurią reikia išspręsti.

• Inicijavimas. Išrinkime 8 atsitiktinius asmenis:

Lentelėje matyti, kad 3 ir 7 asmenys turi daugiausiai vienetų, todėl yra tinkamiausi populiacijos nariai problemai spręsti. Kadangi šiuo metu nėra reikiamos kokybės sprendimo, algoritmas veikia toliau. Būtina atlikti asmenų atranką. Kad būtų lengviau paaiškinti, atranka įvyksta atsitiktinai ir gauname asmenų imtį (n 7, n 3, n 1, n 7, n 3, n 7, n 4, n 2) – tai yra naujųjų tėvai. gyventojų.

• Naudojant genetinius operatorius. Vėlgi, dėl paprastumo darome prielaidą, kad mutacijos tikimybė yra 0. Kitaip tariant, visi 8 individai perduoda savo genus tokius, kokie yra. Norėdami atlikti kirtimą, atsitiktine tvarka sudarysime asmenų poras: (n 2, n 7), (n 1, n 7), (n 3, n 4) ir (n 3, n 7). Taip pat atsitiktinai parenkami kiekvienos poros kirtimo taškai:

• Naujos populiacijos, susidedančios iš palikuonių, sukūrimas:

Tolimesni veiksmai yra akivaizdūs. Įdomiausias dalykas, susijęs su GA, yra įvertinus vidutinį vienetų skaičių kiekvienoje populiacijoje. Pirmojoje populiacijoje vienam individui vidutiniškai teko 5,375 vnt., palikuonių populiacijoje - 6,25 vnt. Ir ši savybė bus pastebėta net jei mutacijų ir kryžminimo metu individas su didžiausias skaičius bus prarasti pirmosios populiacijos vienetai.

Įgyvendinimo planas

Sukurti genetinį algoritmą yra gana sunki užduotis. Pirmiausia išvardijame planą žingsnių pavidalu, po kurio kiekvieną iš jų išanalizuosime išsamiau.

1. Atvaizdavimo apibrėžimas (abėcėlė).
2. Atsitiktinių pokyčių operatorių apibrėžimas.
3. Asmenų išgyvenimo nustatymas.
4. Pirminės populiacijos karta.

Pirmasis etapas teigia, kad abėcėlė, kurioje bus užkoduoti visi sprendimų rinkinio elementai arba populiacija, turi būti pakankamai lanksti, kad vienu metu būtų galima sukurti būtinas operacijas atsitiktines permutacijas ir įvertinti elementų, tiek pirminių, tiek pakeitusių, tinkamumą. Matematiškai nustatyta, kad šiems tikslams sukurti idealios abėcėlės neįmanoma, todėl jos sudarymas yra vienas iš sunkiausių ir svarbiausių etapų, kuriuos reikia užtikrinti. stabilus darbas GA.

Ne mažiau sudėtingas yra modifikavimo ir kūrimo operatorių apibrėžimas. Yra daug operatorių, kurie gali atlikti reikiamus veiksmus. Pavyzdžiui, iš biologijos žinoma, kad kiekviena rūšis gali daugintis dviem būdais: lytiškai (kryžminis) ir nelytiniu būdu (mutacijos). Pirmuoju atveju tėvai keičiasi genetinė medžiaga, antroje – atsiranda mutacijų, nulemtų vidinių organizmo mechanizmų ir išorinis poveikis. Be to, gali būti naudojami reprodukcijos modeliai, kurių gamtoje nėra. Pavyzdžiui, naudokite trijų ar daugiau tėvų genus. Panašiai kaip kryžminimas, į genetinės mutacijos algoritmą gali būti įtraukti įvairūs mechanizmai.

Išgyvenimo metodo pasirinkimas gali būti labai apgaulingas. Genetiniame algoritme yra daugybė atrankos būdų. Ir, kaip rodo praktika, taisyklė „išgyventi stipriausią“ ne visada yra geriausia. Sprendžiant kompleksą techninių problemų dažnai taip ir paaiškėja geriausias sprendimas atsiranda iš daugybės vidutinių ar dar blogesnių. Todėl dažnai įprasta naudoti tikimybinį metodą, kuris teigia, kad geriausias sprendimas yra daugiau šansų už išlikimą.

Paskutinis etapas suteikia algoritmo veikimo lankstumo, kurio neturi niekas kitas. Pirminė sprendimų populiacija gali būti nustatyta remiantis bet kokiais žinomais duomenimis arba visiškai atsitiktinai, tiesiog pertvarkant genus individuose ir sukuriant atsitiktinius asmenis. Tačiau visada verta atsiminti, kad algoritmo efektyvumas labai priklauso nuo pradinės populiacijos.

Efektyvumas

Genetinio algoritmo efektyvumas visiškai priklauso nuo teisingo plane aprašytų žingsnių įgyvendinimo. Ypač įtakingas dalykas čia yra pirminės populiacijos sukūrimas. Yra daug požiūrių į tai. Apibūdinkime keletą:

1. Sukurti visą populiaciją, kuri apims visus galimus individų variantus tam tikroje srityje.
2. Atsitiktinis individų kūrimas remiantis viskuo priimtinos vertės.
3. Taškas atsitiktinis kūrimas asmenys, kai tarp leistinų verčių pasirenkamas kartos diapazonas.
4. Pirmųjų trijų populiacijos kūrimo metodų derinimas.

Taigi galime daryti išvadą, kad genetinių algoritmų efektyvumas labai priklauso nuo programuotojo patirties šiuo klausimu. Tai ir genetinių algoritmų trūkumas, ir privalumas.

Išskirtinis genetinio algoritmo bruožas – akcentuojamas operatoriaus „kirtimas“, kuris atlieka kandidatų sprendimų rekombinacijos operaciją, kurio vaidmuo yra panašus į kirtimo vaidmenį gyvojoje gamtoje.

Enciklopedinis „YouTube“.

1 / 5

✪ Genetinis algoritmas

✪ 20: Įvadas į genetinius algoritmus (1 iš 2)

✪ C# - Jūros mūšis- Geriausias AI algoritmas

✪ 2018-09-15 paskaita „Genetiniai algoritmai ieškant optimalių struktūrų“ Ulyantsev V.I.

✪ Genetinis algoritmas. Grafiko uždėjimas ant liniuotės

Subtitrai

Istorija

Pirmąjį evoliucijos modeliavimo darbą 1954 m. atliko Nilsas Baricelli kompiuteryje, įdiegtame Prinstono universitetas. Jo darbas, paskelbtas tais pačiais metais, sulaukė didelio visuomenės dėmesio. Nuo 1957 m. australų genetikas Alexas Fraseris paskelbė daugybę straipsnių apie dirbtinės organizmų atrankos modeliavimą su daugybe išmatuojamų savybių kontrolės. Pradžia padaryta leidžiama kompiuterinis modeliavimas evoliucijos procesai ir metodai, aprašyti Fraser ir Barnell (1970) ir Crosby (1973) knygose, nuo septintojo dešimtmečio tapo įprastesnė biologų veikla. Fraserio modeliavimas apėmė viską esminiai elementaiŠiuolaikiniai genetiniai algoritmai. Be to, Hansas-Joachimas Bremermannas septintajame dešimtmetyje paskelbė keletą straipsnių, kuriuose taip pat buvo priimtas metodas, pagal kurį optimizavimo problemose naudojamas tirpalo populiacija, kuriai taikoma rekombinacija, mutacija ir atranka. Bremermanno tyrimai apėmė ir šiuolaikinių genetinių algoritmų elementus. Kiti pradininkai yra Richardas Friedbergas, George'as Friedmanas ir Michaelas Conradas. Daugelis pradžios darbai buvo pakartotinai išspausdinti David B. Vogel (1998).

Nors Baricelli savo 1963 m. darbe imitavo mašinos gebėjimą žaisti paprastas žaidimas, dirbtinė evoliucija tapo visuotinai priimtu optimizavimo metodu po Ingo Rechenbergo ir Hanso Paulo Schwefelio darbų septintajame dešimtmetyje ir XX amžiaus aštuntojo dešimtmečio pradžioje – Rechenbergo grupė sugebėjo išspręsti sudėtingas problemas. inžinerinės problemos pagal evoliucines strategijas. Kitas būdas buvo Lawrence J. Vogel evoliucinio programavimo technika, kuri buvo pasiūlyta dirbtiniam intelektui sukurti. Evoliucinis programavimas iš pradžių naudojo baigtinių būsenų mašinas, kad nuspėtų aplinkybes, ir naudojo įvairovę bei pasirinkimą, kad optimizuotų nuspėjamąją logiką. Genetiniai algoritmai ypač išpopuliarėjo dėl 70-ųjų pradžioje Johno Holando darbų ir jo knygos „Adaptation in Natural and Artificial Systems“ (1975). Jo tyrimai buvo pagrįsti Olando atliktais eksperimentais su ląstelių automatais ir jo raštais Mičigano universitete. Holland pristatė formalizuotą naujos kartos kokybės prognozavimo metodą, žinomą kaip grandinės teorema. Genetinių algoritmų tyrimai išliko daugiausia teoriniai iki devintojo dešimtmečio vidurio, kai pagaliau buvo atliktas pirmasis tyrimas. tarptautinė konferencija apie genetinius algoritmus Pitsburge, Pensilvanijoje (JAV).

Su augimu mokslinių tyrimų interesas Skaičiavimo galia taip pat labai padidėjo staliniai kompiuteriai, tai leido naudoti naują kompiuterinės technologijos praktikoje. Devintojo dešimtmečio pabaigoje „General Electric“ pradėjo pardavinėti pirmąjį pasaulyje genetinio algoritmo produktą. Tai tapo pramoninių skaičiavimo įrankių rinkiniu. 1989 metais kita įmonė „Axcelis, Inc. išleido Evolver – pirmąjį pasaulyje komercinį genetinio algoritmo produktą, skirtą staliniams kompiuteriams. „New York Times“ technologijų žurnalistas Johnas Markoffas apie „Evolver“ rašė 1990 m.

Algoritmo aprašymas

Problema formalizuota taip, kad jos sprendimas gali būti užkoduotas kaip genų vektorius („genotipas“), kur kiekvienas genas gali būti bitas, skaičius ar koks nors kitas objektas. Klasikiniai genetinio algoritmo (GA) įgyvendinimai daro prielaidą, kad genotipas yra fiksuoto ilgio. Tačiau yra GA variantų, kuriems šis apribojimas netaikomas.

Tam tikru, dažniausiai atsitiktiniu būdu, sukuriama daug pradinės populiacijos genotipų. Jie vertinami naudojant „tinkamumo funkciją“, pagal kurią kiekvienas genotipas yra susietas su konkrečia verte („tinkamumas“), kuri nustato, kaip gerai jame aprašomas fenotipas išsprendžia esamą problemą.

Genetinių algoritmų taikymas

Genetiniai algoritmai naudojami šioms problemoms spręsti:

1. Funkcijų optimizavimas
2. Įvairios grafikų problemos (keliaujančio pardavėjo problema, spalvinimas, atitikmenų paieška)
3. Dirbtinio neuroninio tinklo nustatymas ir mokymas
4. Maketavimo užduotys
5. Žaidimo strategijos
6. Bioinformatika (baltymų lankstymas)
7. Baigtinių būsenų mašinų sintezė
8. PID valdiklių nustatymas

Paprasto C++ diegimo pavyzdys

Ieškokite vienmatėje erdvėje, be kryžminimo.

#įtraukti #įtraukti #įtraukti #įtraukti #įtraukti int main () ( srand ((nesigned int ) time (NULL )); const dydis_t N = 1000 ; int a [ N ] = ( 0 ); for ( ; ; ) ( //mutacija kiekvieno elemento atsitiktine kryptimi: for (dydis_t i = 0 ; i< N ; ++ i ) a [ i ] += ((rand () % 2 == 1 ) ? 1 : - 1 ); //dabar išrinkite geriausius, rūšiuodami didėjimo tvarka std::rūšiuoti(a, a + N); //ir tada geriausi bus antroje masyvo pusėje. //nukopijuokite geriausius į pirmąją pusę, kur paliko palikuonis, o pirmieji mirė: std::kopija(a + N / 2, a + N, a); //dabar pažiūrėkime į vidutinę gyventojų būklę. Kaip matote, tai darosi vis geriau ir geriau. std::cout<< std :: accumulate (a , a + N , 0 ) / N << std :: endl ; } }

Paprasto diegimo Delphi pavyzdys

Ieškoti vienmatėje erdvėje su išlikimo tikimybe, be kirtimo. (išbandyta Delphi XE)

programa Program1 ; ($APPTYPE CONSOLE) ($R *.res) naudoja sistemą . Generics. Numatytieji nustatymai, sistema. Generics. Kolekcijos, Sistema. SysUtils ; const N = 1000; Nh = N div2; MaxPopulation = Didelė(Sveikasis skaičius);< Integer >var A : masyvas [ 1 .. N ] iš sveikojo skaičiaus ;< Integer >I, R, C, taškai, gimimo rodiklis: sveikasis skaičius; Iptr: ^ Sveikasis skaičius; pradėti Randomize ; // Dalinis gyventojų skaičius for I := 1 to N do A [ I ] := Atsitiktinis ( 2 ) ; // Tarpinė suma Inc(C); iki (Taškai / N >= 1 ) arba (C >= MaxPopulation ) ; Writeln(Formatas(

„%d gyventojų skaičius (normas:%f) rezultatas:%f“

• , [ C , gimstamumas / Nh , taškai / N ])) ; pabaiga. Kultūroje