Algoritem genetske faktorizacije. Uvod: Osnove genetskih algoritmov

Pred približno štirimi leti sem na univerzi slišal za metodo optimizacije, imenovano genetski algoritem. Povsod so o njem poročali natanko dve stvari: kul je in ne dela. Oziroma deluje, vendar je počasen, nezanesljiv in se ga ne bi smelo uporabljati nikjer. Lahko pa čudovito prikaže mehanizme evolucije. V tem članku bom pokazal čudovit način pogleda na procese evolucije v živo na primeru, kako to poteka preprosta metoda. Vse kar potrebujete je malo matematike, programiranja in nekaj domišljije.

Na kratko o algoritmu

Bistvo metode je v tem, da moduliramo evolucijski proces: imamo nekakšno populacijo (nabor vektorjev), ki se razmnožuje, na katero vplivajo mutacije in naravna selekcija poteka na podlagi minimizacije. objektivna funkcija. Oglejmo si te procese podrobneje.

Torej, najprej mora naše prebivalstvo pomnožiti. Osnovno načelo razmnoževanja je, da je potomec podoben svojim staršem. Tisti. opredeliti moramo nekakšen mehanizem dedovanja. In bolje bo, če vključuje element naključja. Toda stopnja razvoja takih sistemov je zelo nizka - genetska raznolikost se zmanjšuje, populacija degenerira. Tisti. vrednost funkcije preneha biti minimizirana.

Za rešitev tega problema je bil uveden mehanizem mutacije, ki je sestavljen iz naključnih sprememb pri nekaterih posameznikih. Ta mehanizem nam omogoča, da v gensko raznolikost vnesemo nekaj novega.
Naprej pomemben mehanizem - izbor. Kot rečeno, selekcija je selekcija posameznikov (lahko izmed tistih, ki so se šele rodili, ali pa izmed vseh - praksa kaže, da to ni odločilna vloga), ki bolje minimizirajo funkcijo. Običajno se izbere toliko osebkov, kot jih je bilo pred razmnoževanjem, tako da imamo iz obdobja v obdobje stalna količina posameznikov v populaciji. Običajno je tudi, da se izberejo "srečneži" - določeno število posameznikov, ki morda ne bodo dobro zmanjšali funkcije, vendar bodo v naslednjih generacijah vnesli raznolikost.

Ti trije mehanizmi najpogosteje ne zadostujejo za zmanjšanje delovanja. Tako se populacija degenerira - lokalni minimum prej ali slej s svojo vrednostjo preplavi celotno populacijo. Ko se to zgodi, se sproži postopek, imenovan pretresanje(v naravi so analogije globalne kataklizme), ko je uničena skoraj celotna populacija in dodani novi (naključni) posamezniki.

Tukaj je opis klasičnega genetskega algoritma, ki ga je enostavno implementirati in je prostor za domišljijo in raziskovanje.

Izjava problema

Z matematičnega vidika je takšna optimizacija zgolj malenkost. Graf takšne funkcije je ogromna večdimenzionalna "luknja" (kot tridimenzionalni parabaloid na sliki), v katero boste neizogibno zdrsnili, če boste sledili gradientu. Edini lokalni minimum je globalen. .

Težava je le v tem, da se že blizu minimuma močno zmanjša število poti, po katerih se lahko spustiš, skupno pa imamo toliko smeri, kolikor je dimenzij (torej števila pikslov). Očitno se tega problema ne splača reševati z uporabo genetskega algoritma, vendar si ga lahko ogledamo zanimivi procesi ki se pojavljajo v naši populaciji.

Izvedba

Kot začetne slike sem vzel nonograme ("japonske skenerske besede"), ampak, če sem iskren, lahko vzamete samo črne kvadratke - ni nobene razlike. Spodaj so rezultati za več slik. Tu je bilo za vse razen za »hišo« število mutacij v povprečju 100 za vsakega posameznika, v populaciji je bilo 100 osebkov, med razmnoževanjem pa se je populacija povečala 4-krat. V vsaki dobi je bilo 30 % srečnežev. Za hišo so bile izbrane manjše vrednosti (30 posameznikov v populaciji, 50 mutacij na posameznika).

Eksperimentalno sem ugotovil, da uporaba "srečnežev" pri selekciji zmanjša stopnjo strmljenja populacije na minimum, vendar pomaga izstopiti iz stagnacije - brez "srečnežev" bo stagnacija stalna. Kaj je razvidno iz grafov: levi graf je razvoj »faraonske« populacije s srečneži, desni brez srečnežev.

Tako vidimo, da nam ta algoritem omogoča rešitev problema, čeprav za zelo dolgo za dolgo časa. Preveč tresenja v primeru velikih slik lahko reši več posameznikov v populaciji. Optimalna izbira parametrov za različne velikosti To puščam izven obsega te objave.

Globalna optimizacija

Vendar je še več zanimiva rešitev dana težava: lahko razumemo, da smo zdrsnili v lokalni minimum, naredimo močan pretres (ali celo znova sprožimo posameznike) in nato dodamo kazni, ko se približamo znanemu minimumu. Kot vidite, se slike izmenjujejo. Ugotavljam, da se nimamo pravice dotikati izvirne funkcije. Lahko pa se spomnimo lokalnih minimumov in sami dodamo kazni.

Ta slika prikazuje rezultat, ko dosežete lokalni minimum(močna stagnacija), populacija enostavno izumre.

Tukaj populacija izumre in doda se majhna kazen (enakovredna normalni razdalji do znanega minimuma). To močno zmanjša verjetnost ponovitev.

Bolj zanimivo je, ko populacija ne izumre, ampak se preprosto začne prilagajati novim razmeram (naslednja slika). To se doseže s kaznijo 0,000001 * vsota ^ 4. V tem primeru nove slike postanejo nekoliko motne:

Ta hrup je odpravljen z omejitvijo kazni na max(0,000001 * vsota ^ 4, 20). Vidimo pa, da četrtega lokalnega minimuma (dinozavra) ni mogoče doseči - najverjetneje zato, ker je preblizu kakšnega drugega.

Biološka interpretacija

Kakšne sklepe lahko potegnemo iz, upam si reči, manekenstva? Najprej vidimo, da je spolno razmnoževanje najpomembnejši motor razvoja in prilagodljivosti. A samo to ni dovolj. Vloga naključnih, majhnih sprememb je izjemno pomembna. Prav oni zagotavljajo nastanek novih vrst živali v procesu evolucije, pri nas pa zagotavlja pestrost populacije.

Najpomembnejšo vlogo pri razvoju Zemlje so imele naravne katastrofe in množična izumrtja (izumrtja dinozavrov, žuželk ipd. - bilo je približno deset večjih - glej spodnji diagram). To je potrdila tudi naša simulacija. In izbor "srečnežev" je pokazal, da so najšibkejši organizmi danes sposobni postati osnova za naslednje generacije v prihodnosti.

Kot pravijo, je vse tako kot v življenju. Ta metoda »naredi sam evolucije« jasno prikazuje zanimive mehanizme in njihovo vlogo pri razvoju. Seveda obstaja veliko več vrednih evolucijskih modelov (seveda na podlagi difurs), ki upoštevajo več dejavnikov, ki so bližje življenju. Seveda jih je več učinkovite metode optimizacija.

P.S.

Izvorna koda

funkcija res = genetic(file) %generiranje globalnega A B;

im2line(datoteka);

dim = dolžina (A(1,:)); štetje = 100; ponovitev = 4; mut = 100; izberite = 0,7; stagn = 0,8;

Učinkovitost genetskega algoritma za reševanje vsakega določeno nalogo določata dva glavna dejavnika: hitrost in stabilnost dela. Hitrost genetskega algoritma se meri s časom, ki je potreben za dokončanje uporabniško določenega števila iteracij. Če je merilo ustavitve kakovost populacije ali njena konvergenca, potem je hitrost ocenjena s časom, ko genetski algoritem doseže enega od teh dogodkov. Stabilnost iskanja se ocenjuje glede na stopnjo, do katere je algoritem odporen na udarne točke lokalni ekstremi in sposobnost nenehnega povečevanja kakovosti prebivalstva iz generacije v generacijo.

Prednosti genetskih algoritmov so še posebej očitne, če jih upoštevamo v primerjavi s tradicionalnimi metodami.

1. GA delujejo s kodami, ki so formalizirana oblika nabora parametrov, ki so argumenti ciljne funkcije. Interpretacija teh kod se pojavi šele pred začetkom algoritma in po njegovem zaključku. Med delovanjem GA prihaja do manipulacij s kodami ne glede na njihovo pomensko vsebino, tj. koda se obravnava preprosto kot bitni niz.

2. Pri izvajanju postopka iskanja GA obdeluje več točk iskalnega prostora hkrati in se ne premika zaporedno od točke do točke, kot pri tradicionalne metode. To nam omogoča, da premagamo nevarnost padca v lokalni ekstrem multimodalne ciljne funkcije. Uporaba več točk hkrati znatno zmanjša verjetnost takšnega dogodka.

3. Med delom GS ne uporabljajo nobenih dodatne informacije poleg podatkov o razponu dovoljenih vrednosti parametrov in ciljni funkciji v poljubna točka, kar poveča hitrost njihovega dela.

4. Za generiranje novih točk v iskalnem prostoru GA hkrati uporablja tako verjetnostna kot deterministična pravila, kar daje veliko večji učinek kot vsaka od teh metod posebej.

Slabosti GA vključujejo naslednje:

· pridobitev optimalne rešitve ni zagotovljena;

· le specialist lahko učinkovito oblikuje problem, določi kriterij za izbiro kromosomov (nastavi kodo) in druge parametre GA;

· formulacija problema v smislu GA ne omogoča analize statistična pomembnost rešitev, pridobljena z njihovo pomočjo;

· precej visoka intenzivnost računalniških virov GA vodi v dejstvo, da je med evolucijskim modeliranjem veliko rešitev zavrženih kot neobetavnih;

· s časovno zahtevnostjo v povprečju nižjo kot pri najboljših konkurenčnih algoritmih, vendar ne več (pridobljeno na podlagi eksperimentalnih podatkov) kot za en red velikosti;

· nizka učinkovitost v končnih fazah evolucijskega modeliranja, razložena z dejstvom, da iskalni mehanizmi GA niso strogo osredotočeni na čim hitrejše doseganje lokalnega optimuma;

· nekatera druga vprašanja ostajajo nerešena, na primer problem samoprilagajanja GA.

Ko govorimo o evolucijskih izračunih na splošno, je treba opozoriti, da ti, tako kot katera koli metoda, ki uporablja element naključnosti, ne zagotavljajo odkrivanja globalnega ekstrema ciljne funkcije (ali optimalne rešitve) znotraj določen čas. Njihova glavna prednost je, da vam omogočajo, da najdete "dobro" rešitev težka naloga v krajšem času kot druge metode. Evolucijsko računalništvo ni optimalno orodje za reševanje vseh problemov, je pa precej učinkovito na področju inženirskega načrtovanja, načrtovanja, usmerjanja, napovedovanja itd.

Opozoriti je treba, da je evolucijsko računanje pristop k reševanju problemov optimizacije in ne algoritem. Posledično zahtevajo prilagajanje posameznemu razredu nalog z izbiro določenih karakteristik in parametrov. Trenutno obstaja medsebojno prodiranje različnih evolucijskih računalniških paradigem in njihovo združevanje v en koncept.

K orodjem, ki ponujajo rešitve težave z optimizacijo z uporabo genetskih algoritmov vključujejo naslednje programski izdelki:

· Paket Evolver 4.0, ki ga je razvil Palisade Corp., je dodatek procesorju za preglednice MS Excel;

· Paket Gene Hunter 1.0 Ward družba sistemska skupina;

· Paket Genetic Training Option (GTO) podjetja California Scientific Software, ustvarjen posebej za usposabljanje nevronskih mrež in je aplikacija paketa Brain Maker.

5.4. Integriran pristop k oblikovanju sistema
umetna inteligenca

Kompleksna aplikacija Obravnavane inteligentne metode obdelave informacij lahko bistveno povečajo učinkovitost razvitega InS.

Možnost uporabe tako simbolnih kot podsimboličnih pristopov (ki se običajno štejejo za medsebojno izključujoče) znotraj enega sistema je pripeljala do nastanka tako imenovanih hibridnih sistemov. Takšni sistemi so potencialno močno orodje za reševanje kompleksne težave, ki presegajo moč posameznih »čistih« pristopov.

Na primer, genetske algoritme je mogoče uporabiti za usposabljanje nevronske mreže, mehki sistem pa je implementiran kot mehka NN.

V teoriji sistemov umetne inteligence je treba opraviti še veliko dela, preden lahko takšni sistemi v zadostni meri posnemajo sposobnost stalnega izboljševanja, ki jo ima človeški strokovnjak. V ta namen morajo danes raziskovalci in razvijalci rešiti številne probleme.

Na VIII mednarodni znanstveni in tehnični konferenci "Inteligentni sistemi" pri razvoju sistemov umetne inteligence so bile opredeljene naslednje glavne smeri nadaljnjega razvoja na področju umetne inteligence:

· vzporednost v logičnem sklepanju;

· ekspertni sistemi in sklepanje v pogojih negotovosti;

· argumentacija in abduktivni izhod;

· kvaziaksiomatski sistemi;

· strojno učenje in induktivno sklepanje;

· mehko računalništvo: mehka logika in približni izračuni;

· nevronske mreže;

· genetski algoritmi;

· kognitivni grafični sistemi;

· semantični splet in ontološki sistemi;

· agentsko in porazdeljeno reševanje problemov;

· razumevanje naravnega jezika.

1. poglavje Genetski algoritmi

1.1 Naravna selekcija v naravi

1.2 Predstavitev predmetov. Kodiranje funkcij

1.3 Osnovni genetski operaterji

1.4 Shema delovanja genetskega algoritma

Poglavje 2. Težave z optimizacijo

2.1 Problemi, rešeni z uporabo genetskih algoritmov

2.2 Matematična formulacija optimizacijskega problema

2.3 Rešitev Diofantove enačbe

2.4 Načini reševanja optimizacijskih problemov

2.5 Problem trgovskega potnika

Poglavje 3. Izvedba programske opreme. Izdelava priročnika o genetskih algoritmih

3.1 Utemeljitev izbire programske opreme

3.2 Opis izvedbe programske opreme

Zaključek

1.1. Naravna selekcija v naravi

»V 19. stoletju je Charles Darwin naredil obkroženje, zbiranje informacij za teorijo evolucije na podlagi naravna selekcija, v katerem preživi najmočnejši. Ali si je lahko predstavljal, da bodo sto let pozneje matematiki s to teorijo rešili problem optimalne poti za potovanje okoli sveta s postanki na številnih majhnih otokih?..«

Ključno vlogo pri evolucijska teorija igra naravna selekcija. Njegovo bistvo je, da najsposobnejši posamezniki bolje preživijo in proizvedejo več potomcev kot manj sposobni. Upoštevajte, da naravna selekcija sama po sebi ne zagotavlja razvoja biološke vrste. Zato je zelo pomembno razumeti, kako pride do dedovanja, torej kako so lastnosti potomca odvisne od lastnosti njegovih staršev.

Osnovni zakon dedovanja je intuitivno jasen vsakomur - to je, da so potomci podobni svojim staršem. Zlasti je večja verjetnost, da bodo potomci bolj fit staršev med najsposobnejšimi v svoji generaciji. Da bi razumeli, na čem temelji ta podobnost, se morate nekoliko poglobiti v zgradbo naravne celice – v svet genov in kromosomov.

Skoraj vsaka celica katerega koli posameznika ima nabor kromosomov, ki prenašajo informacije o tem posamezniku. Glavni del kromosoma je veriga DNK, ki določa, kakšne kemične reakcije se bodo zgodile v določeni celici, kako se bo razvijala in katere funkcije bo opravljala. Gen je del verige DNK, ki je odgovoren za specifično lastnino posamezniki, na primer za barvo oči, tip las, barvo kože itd. Ko se živali razmnožujejo, se dve starševski zarodni celici združita in njuna DNK medsebojno vplivata, da tvorita DNK potomcev. Glavna metoda interakcije je crossover. Pri križanju se DNK prednikov razdeli na dva dela, nato pa se njuni polovici zamenjata.

Pri dedovanju so možne mutacije zaradi radioaktivnosti ali drugih vplivov, zaradi česar se lahko spremenijo nekateri geni v zarodnih celicah enega od staršev. Spremenjeni geni se prenašajo na potomce in mu dajejo nove lastnosti. Če so te nove lastnosti uporabne, se bodo verjetno obdržale v dani vrsti – in postopno se bo povečala primernost vrste. Podoben algoritem je leta 1975 prvič predlagal John Holland z Univerze v Michiganu. Imenovali so ga "nizozemski načrt razmnoževanja" in je bil osnova za skoraj vse različice genetskih algoritmov. Preden pa si ga podrobneje ogledamo, je treba pogledati, kako je mogoče predmete iz resničnega sveta kodirati za uporabo v genetskih algoritmih.

1.2. Predstavitev predmetov. Kodiranje funkcij

Iz biologije vemo, da je vsak organizem lahko predstavljen z njegovim fenotipom, ki dejansko določa, kaj je predmet v resničnem svetu, in njegovim genotipom, ki vsebuje vse informacije o objektu na ravni kromosomske garniture. Poleg tega se vsak gen, to je element informacije o genotipu, odraža v fenotipu. Zato moramo za reševanje problemov predstaviti vsako značilnost predmeta v obliki, primerni za uporabo v genetskem algoritmu. Vse nadaljnje delovanje mehanizmov genetskega algoritma se izvaja na ravni genotipa, kar omogoča brez informacij o notranji strukturi predmeta, kar določa njegovo široko uporabo pri različnih nalogah.

Najpogostejša vrsta genetskega algoritma uporablja bitne nize za predstavitev genotipa predmeta. V tem primeru vsak atribut predmeta v fenotipu ustreza enemu genu v genotipu predmeta. Gen je bitni niz, največkrat fiksne dolžine, ki predstavlja vrednost te lastnosti.

Za kodiranje takšnih funkcij lahko uporabite najpreprostejšo možnost - bitno vrednost te funkcije. Potem bo za nas povsem preprosto uporabiti gen določene dolžine, ki zadostuje za predstavitev vseh možne vrednosti tak znak. Takšna koda je Grayeva koda, ki jo je priporočljivo uporabiti pri implementaciji genetskega algoritma. Pomeni Grayovih kod so obravnavani v spodnji tabeli:

Torej, da bi določili fenotip predmeta (to je vrednosti značilnosti, ki opisujejo predmet), moramo poznati le vrednosti genov, ki ustrezajo tem značilnostim, to je genotip predmeta. V tem primeru je niz genov, ki opisujejo genotip predmeta, kromosom. V nekaterih izvedbah se imenuje tudi posameznik. Tako je pri izvajanju genetskega algoritma kromosom bitni niz fiksne dolžine. V tem primeru vsak del črte ustreza genu. Dolžina genov v kromosomu je lahko enaka ali različna. Najpogosteje se uporabljajo geni enake dolžine. Poglejmo si primer kromosoma in razlago njegovega pomena. Recimo, da ima predmet 5 značilnosti, od katerih je vsaka kodirana z genom, dolgim ​​4 elemente. Potem bo dolžina kromosoma 5*4=20 bitov

Uvod

Evolucija v naravi se je izkazala kot močan mehanizem za razvoj in prilagajanje živih organizmov okolju ter preseneča z raznolikostjo in učinkovitostjo rešitev. Zato raziskovalci na terenu računalniška tehnologija obrnili k naravi v iskanju novih algoritmov.

Skupina algoritmov, ki temelji na ideji Darvinistična evolucija, se imenujejo evolucijski algoritmi. Določa naslednja področja.

• Genetski algoritmi (GA).
• Evolucijske strategije.
• Genetsko programiranje.
• Evolucijsko programiranje.

Genetski algoritmi se uporabljajo za reševanje težav, kot so:

• iskanje globalnega ekstrema večparametrske funkcije,
• aproksimacija funkcije,
• težave z najkrajšo potjo,
• težave s postavitvijo,
• postavitev umetne nevronske mreže,
• igralne strategije,
• strojno usposabljanje.

Pravzaprav genetski algoritmi maksimizirajo funkcije z več parametri. Zato je njihov obseg uporabe tako širok. Vsi zgoraj navedeni problemi se rešujejo prav tako, da se oblikuje funkcija, ki je odvisna od določenega števila parametrov, katerih globalni maksimum bo ustrezal rešitvi problema.

Naravni mehanizem

Za živa bitja so značilni njihovi zunanji parametri (fenotip).

Nekateri parametri so koristni za preživetje in razmnoževanje, drugi pa bolj škodijo. Vsi zunanji podatki posameznika so kodirani z njegovo verigo DNK (genotip). Posamezni deli te verige (geni) določajo različne parametre posameznika.

Po teoriji evolucije Charlesa Darwina posamezniki v populaciji tekmujejo med seboj za vire (hrano) in za privabljanje partnerja.

Tisti posamezniki, ki so najbolj prilagojeni okoljskim razmeram, bodo živeli dlje in ustvarili številnejše potomce kot njihovi dvojniki.

Naravna selekcija, križanje in mutacija zagotavljajo razvoj populacije. Vsaka nova generacija je v povprečju bolj fit od prejšnje, to pomeni, da bolje ustreza zahtevam zunanjega okolja. Ta proces se imenuje evolucija.

Ob upoštevanju evolucije v naravi se poraja ideja, da je mogoče umetno izbrati osebke, ki nam ustrezajo po določenih parametrih, in tako ustvariti umetne zunanje pogoje. To se imenuje selektivna vzreja in jo ljudje uporabljajo za ustvarjanje novih pasem živali, na primer tistih, ki dajejo več mleka ali imajo gostejšo dlako. Toda zakaj ne bi uredili lastne evolucije z uporabo računalnika? Dejansko naj obstaja funkcija, ki glede na dano množico numeričnih parametrov vrne določeno vrednost (funkcija z več parametri). Ustvarimo veliko vrstic, od katerih bo vsaka kodirala vektor števil (dolžina vektorja je enaka številu parametrov funkcije). Avtor: dani vektor lahko izračunate ustrezno vrednost funkcije. Tiste črte, za katere je ta vrednost velika, bodo veljale za primernejše od tistih, za katere je majhna. Z zagonom evolucije na strunah, podobnih naravnim, bomo v vsaki generaciji prejeli strune z vsemi velike vrednosti funkcije. Tako ta vrsta evolucije rešuje problem maksimiranja večparametrske funkcije.

Klasični genetski algoritem

starš sodobna teorija genetske algoritme (GA) obravnava J. Holland, čigar delo »Prilagajanje v naravnih in umetnih sistemih« (1975) je postalo klasika na tem področju. V njem je Holland prvi uvedel izraz »genetski algoritem«. Zdaj se tam opisani algoritem imenuje »klasični GA« (včasih »kanonični GA«, kanonski GA), koncept »genetskih algoritmov« pa je postal zelo širok in pogosto vključuje algoritme, ki se zelo razlikujejo od klasičnega GA.

Nizozemska študenta Kenneth De Jong in David E. Goldberg sta ogromno prispevala k razvoju GA. Avtorji skoraj vseh del na to temo se sklicujejo na Goldbergovo knjigo "Genetski algoritmi pri optimizaciji iskanja in strojnem učenju" (1989).

Kot že omenjeno, genetski algoritmi delujejo po analogiji z naravo. Delujejo z nizom »posameznikov«, ki so nizi, od katerih je v vsakem zakodirana ena od rešitev problema. Pripravljenost posameznika se oceni s posebno funkcijo. Najmočnejši dobijo možnost križanja in ustvarjanja potomcev. Najslabši posamezniki so odstranjeni in ne proizvajajo potomcev. Tako je kondicija nove generacije v povprečju višja od prejšnje.

Funkcija fitnesa in kodiranje odločitev

Torej, soočimo se s problemom optimizacije. S spreminjanjem nekaterih parametrov, na primer, če rešite problem postavitve, koordinate elementov, ki jih želite postaviti, morate najti njihovo kombinacijo, da zmanjšate zasedeno površino. Takšen problem lahko preformuliramo kot problem iskanja maksimuma neke funkcije f (x 1, x 2, ..., x n). Ta funkcija se imenuje fitnes funkcija in se uporablja za izračun telesne pripravljenosti posameznikov. Imeti mora nenegativne vrednosti, obseg parametrov pa mora biti omejen.

Če moramo na primer najti minimum določene funkcije, potem je dovolj, da njen obseg vrednosti premaknemo v pozitivno območje in ga nato obrnemo. Tako največ nova funkcija bo ustrezal minimumu prvotnega.

Genetski algoritmi tega ne uporabljajo funkcijske lastnosti, kot kontinuiteta, diferenciabilnost itd. Mišljen je kot naprava ( črna škatla), ki prejme parametre kot vhod in izpiše rezultat.

Zdaj pa se obrnemo na kodiranje nabora parametrov. Kodirajmo vsak parameter z nizom bitov. Če zavzema zvezen niz vrednosti, potem izberemo dolžino niza v skladu z zahtevano natančnostjo. Tako bo parameter lahko samo sprejel diskretne vrednosti

(te vrednosti bodo potenca 2), v določenem določenem območju.

Na primer, naj spremenljivka x k pripada segmentu [ x min , x max ].

Kodirajmo ga z binarnim nizom l bitov. Nato vrstica s k označuje naslednjo vrednost spremenljivke x k:

X k = x min + s k (x max − x min) ⁄ 2 l če v formuli s k označuje vrednost binarnega števila, ki ga kodira ta niz. 10. Dodatnih 23 vrstic lahko ponovi že kodirane vrednosti parametra ali pa jih je mogoče dodatno definirati v fitnes funkciji kot "najslabše", tj. če je parameter kodiran z eno od teh vrstic, potem funkcija očitno prevzame najmanjša vrednost.

Torej smo za vsak parameter definirali niz, ki ga kodira. Posameznik bo niz, ki je veriženje nizov celotnega urejenega niza parametrov:

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

Prilagojenost posameznika se izračuna na naslednji način: niz se razdeli na podnize, ki kodirajo parametre. Nato se za vsak podniz izračuna ustrezna vrednost parametra, nakar se pridobi fitnes posameznika kot vrednost funkcije fitnesa iz nastalega niza.

Na splošno so od določene naloge odvisni le parametri GA, kot sta fitnes funkcija in kodiranje rešitev. Preostali koraki za vse naloge se izvajajo na enak način, kar dokazuje vsestranskost GA.

Delovni algoritem

Slika prikazuje diagram delovanja katerega koli genetskega algoritma:

V klasičnem GA se začetna populacija oblikuje naključno.

Velikost populacije je fiksna (število osebkov v njej bo označeno s simbolom N), ki se med delovanjem celotnega algoritma ne spreminja. Vsak posameznik je generiran kot naključni L -bitni niz, kjer je L dolžina kodiranja posameznika, prav tako je fiksna in enaka za vse posameznike. Opozoriti je treba, da vsak

posameznik je ena od rešitev problema. Bolj pripravljeni posamezniki pomenijo ustreznejše odzive. Ta GA se razlikuje od večine drugih optimizacijskih algoritmov, ki delujejo samo z eno rešitvijo in jo izboljšujejo. Korak algoritma je sestavljen iz treh stopenj: generiranje vmesne populacije ( vmesna generacija ) z izbiro ( izbor ) trenutna generacija ( trenutna generacija ), križišče ( rekombinacija ) posamezniki vmesne populacije po (križanec križanec ), kar vodi do oblikovanja nove generacije ( naslednjo generacijo

) in mutacijo nove generacije. Slika prikazuje prvi dve stopnji:

Vmesna populacija je skupek osebkov, ki so pridobili pravico do razmnoževanja. Prilagojene posameznike lahko tam posnamemo večkrat. »Slabi« posamezniki tja najverjetneje sploh ne bodo prišli. V klasični GA je verjetnost, da bo vsak posameznik prišel v vmesno populacijo, sorazmerna z njegovo sposobnostjo, tj. (proporcionalna izbira). Lahko se izvede na naslednji način: posamezniki naj se nahajajo na kolesu rulete, tako da je velikost sektorja vsakega posameznika sorazmerna z njegovo pripravljenostjo. Na začetku je vmesna populacija prazna..

Z N-kratnim zagonom rulete izberemo potrebno število posameznikov, ki jih bomo zabeležili v vmesno populacijo. Noben izbran posameznik ni odstranjen iz kolesa rulete. Ta izbor se imenuje stohastično vzorčenje< f > = 1.36 (< f >Druga metoda izbire, ki je prav tako proporcionalna, je

. Za vsakega posameznika se izračuna razmerje med njegovo telesno pripravljenostjo in povprečno telesno pripravljenostjo populacije.

Celo število tega razmerja pove, kolikokrat je treba posameznika zapisati v vmesno populacijo, delni del pa je njegova verjetnost, da bo tja spet prišel. Naj bo na primer za nek posameznik i f i ⁄ — povprečna telesna pripravljenost trenutne populacije). Nato bo izbran enkrat in nato z verjetnostjo 0,36 še enkrat. Ta način izbire je priročno izvesti na naslednji način: posameznike postavimo na ruleto na enak način, kot je opisano. Zdaj naj ruleta nima ene puščice, ampak N, in odrežejo enake sektorje. Nato bo en vrtljaj kolesa rulete takoj izbral vseh N posameznikov, ki jih je treba zabeležiti v vmesno populacijo. Ta metoda je prikazana na naslednji sliki:

Po izboru so osebki vmesne populacije naključno razdeljeni v pare. Vsak od njih je križan z verjetnostjo p c, kar pomeni, da se nanj uporabi križanjski operater, kar ima za posledico dva potomca. Pridružujejo se novi generaciji. Če se par nima možnosti križanja, se osebki tega para sami zapišejo v novo generacijo.

1011001100 101101 ⇒ 1011001101 101101

Klasični genetski algoritem uporablja enotočkovni križni operator (

1-točkovno križišče ): Za starševske kromosome (tj. nize) je točka rezanja naključno izbrana in izmenjata odrezane dele. Nastali dve vrstici sta potomci: (Operator mutacije se uporabi za novo generacijo, ki izhaja iz križanja. Vsak bit vsakega posameznika v populaciji je obrnjen z verjetnostjo p m. Ta verjetnost je običajno zelo majhna, manj kot 1 %. Tako proces selekcije, križanja in mutacije vodi do oblikovanja nove generacije. Korak algoritma se konča z razglasitvijo nove generacije za trenutno. Nato se vsa dejanja ponovijo.

Konvergenca je stanje populacije, ko so vse vrstice populacije skoraj enake in se nahajajo v območju nekega ekstrema.

V takšnih razmerah križanec praktično sploh ne spremeni populacije.

In posamezniki, ki zapustijo to območje zaradi mutacije, ponavadi izumrejo, saj imajo pogosto nižjo kondicijo, še posebej, če je ta ekstrem globalni maksimum. Konvergenca populacije tako običajno pomeni, da je bila najdena boljša ali bližja rešitev.

Odgovor na problem je lahko nabor parametrov, ki jih kodira najboljši posameznik zadnje generacije. Predloge Predloga (

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

shema ) je niz dolžine L (tj. enake dolžine kot kateri koli niz v populaciji), sestavljen iz znakov (0, 1, *) (kjer je * znak »ne zanima«). niz je reprezentativen za dano predlogo, če ima na položajih, kjer je znak vzorca 0 ali 1, enak simbol. Na primer, predloga 01*0*110 ima naslednje predstavnike: Po vrstnem redu ( naročilo) vzorca je število fiksnih bitov v njem. Določitev dolžine (

določitev dolžine

) vzorca je razdalja med njegovimi najbolj oddaljenimi fiksnimi biti. Na primer, za vzorec *1***01* je vrstni red o = 3 in definirajoča dolžina Δ = 5.

Očitno je število predstavnikov vzorca H enako 2 L − o (H) , število vzorcev pa 3 L (dejansko so vzorci nizi, ki imajo lahko enega od treh znakov na vsaki poziciji).

Če si iskalni prostor predstavljate kot hiperkocko, potem so vrstice njena oglišča, vzorec pa v njem določa hiperravnino. Na primer, vzorec **1 določa desni rob te 3D kocke:

Zato se izraza "hiperravnina" in "vzorec" uporabljata izmenično. Naslednja slika prikazuje drugo predstavitev predlog: Kaže, da so nekateri vzorci v povprečju v celotnem iskalnem prostoru bolj primerni kot drugi.

Navzven se zdi, da genetski algoritem izbira niz, a implicitno izbira tudi vzorce, katerih predstavnik je. To pomeni, da se pri vsaki generaciji število predstavnikov vzorca spreminja v skladu s trenutno ustreznostjo tega vzorca. Predstavniki »dobrih« predlog so v povprečju bolj primerni, kar pomeni, da bodo pogosteje izbrani v vmesno populacijo. »Slabi« vzorci imajo veliko možnosti, da izumrejo. Ena črta je reprezentativna za več vzorcev hkrati (namreč 2 L: na vsakem položaju bodisi pustimo bit črte ali pa ga nadomestimo z "*"). Zato se pri izbiri ene vrstice naenkrat izbere celoten niz predlog. Ta pojav se imenuje implicitni paralelizem (implicitni paralelizem).

Izrek vzorca

Izrek vzorca (Izrek o shemi) je bil podan v zgoraj omenjenem Hollandovem delu in je prvi poskus razlage, zakaj genetski algoritmi delujejo. Prikazuje, kako se spreminja delež predstavnikov vzorca v populaciji.

Naj bo M(H, t) število predstavnikov predloge H v t-ti generaciji. Ker se pri konstruiranju vmesne populacije uporablja sorazmerna selekcija, bo število predstavnikov tega vzorca v njej

M (H, t + intermediat) = M (H, t) f (H, t) ⁄< f (t)>

kjer je f (H, t) primernost predloge H v t-ti generaciji in< f (t)>— povprečna pripravljenost t-te generacije.

Posamezniki vmesne populacije so podvrženi križanju z verjetnostjo p c. Enotočkovno križanje lahko prekine vzorec, kar pomeni, da je bil eden od staršev predstavnik zadevnega vzorca, nobeden od otrok pa ne bo. Verjetnost uničenja je manjša od

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

kjer je P(H, t) delež predstavnikov šablone H v t.generaciji. Prvi dejavnik izdelka enako verjetnosti ločnice padejo med fiksne bite predloge, druga pa je verjetnost izbire predstavnika druge predloge v par.

Dejansko križanje ne uniči vzorca pogosteje kot takrat, ko drugi starš (in je izbran v vmesni populaciji) ni predstavnik tega vzorca in ločnica pade med fiksne bite vzorca. Tudi v teh situacijah ni nujno uničen, na primer, če gledamo vzorec 11**** in sta vrstici 110101 in 100000 prekrižani in točka križanja pade med prva dva bita, čeprav druga vrstica ni reprezentativna za želeni vzorec, vsi enako, eden od potomcev bo primeren in vzorec ne bo uničen.

Tako po križanju, prehajanju s števila predstavnikov na njihov delež, dobimo naslednjo neenakost:

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

Zdaj pa upoštevajmo učinek mutacije. Za vsak fiksni bit je verjetnost, da ne bo obrnjen, (1 − p m). Ker je skupno število fiksnih bitov v vzorcu o (H), je pravilna naslednja končna formula izreka o vzorcu:

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

Dobljeni izraz ni preveč primeren za analizo delovanja genetskega algoritma. Prvič, vsebuje znak neenakosti, kar je tudi posledica dejstva, da nismo upoštevali primerov, ko obravnavani vzorec nastane kot rezultat križanja para nizov, ki niso njegovi predstavniki. Drugič, primernost predloge in povprečna sposobnost populacije se hitro spreminjata iz generacije v generacijo, tako da nastala neenakost dobro opiše le situacijo za naslednjo generacijo.

Kljub temu je izrek predloge vsaj nekakšna teoretična utemeljitev za delo klasičnega genetskega algoritma (opozoriti je treba, da velja le za klasični GA s proporcionalno selekcijo in enotočkovnim križanjem). Vklopljeno v tem trenutku Obstajajo natančnejše različice tega izreka, pa tudi drugi argumenti, ki dokazujejo smiselnost uporabe genetskih algoritmov.

Gradniki

Iz izraza, pridobljenega v izreku o predlogi, je jasno, da so predloge z nizkim vrstnim redom in majhno določevalno dolžino manj dovzetne za uničenje zaradi križanja ali mutacije, zato se rast (ali zmanjšanje) njihovega deleža v populaciji pojavlja bolj dinamično. . Vzorci z visoko ustreznostjo, nizkim vrstnim redom in nizko definirajočo dolžino se imenujejo gradniki ( gradniki).

Holland (1992) je pokazal, da medtem ko GA obdela N vrstic pri vsaki generaciji, je implicitno obdelanih tudi približno N 3 hiperravnin. To je dokazano na podlagi realno uporabnih velikosti populacije in dolžin nizov. V praksi to pomeni, da lahko velika populacija hitreje lokalizira rešitev kot majhna. Za oceno priporočene velikosti populacije glede na dolžino niza se lahko spomnimo, da je skupno 3 hiperravnine L.

Še en argument v prid velikim populacijam: če je širjenje sposobnosti predstavnikov bloka veliko, potem je verjetnost, da izberemo določeno število predstavnikov bloka z nižjo sposobnostjo namesto predstavnikov boljšega, precej velika, saj posameznik posamezniki "šibkega" bloka se lahko izkažejo za boljše od mnogih posameznikov "močnih". Povečanje velikosti populacije bo povečalo število vzorcev, vzetih pri ustvarjanju vmesne populacije, in verjetnost, da boste na koncu izbrali napačen blok, bo precej majhna.

Hipoteza gradnikov pravi, da ko se populacija približuje globalnemu optimumu, se vrstni red in primernost gradnikov povečujeta. To je enostavno videti s preprostim primerom:

Vsi lokalni maksimumi dane funkcije se pojavljajo v bloku **0*, minimumi pa v **1*, zato je očitno, da bo po izboru večina posameznikov predstavnikov prvega bloka. Leva polovica grafa je v povprečju nižja od desne, zato bo delež bloka 1*** prevladal nad deležem 0***. Izkazalo se je, da bo večina posameznikov predstavnikov bloka 1*** in hkrati **0*, kar pomeni, da jih bo veliko predstavnikov bloka 1*0*. Zdaj, ko izbiramo med blokoma 100* in 110*, ugotovimo, da bo drugi blok prevladal nad prvim. Tako lahko rečemo, da so se dobri gradniki malega reda oblikovali v prilagojene bloke višjega reda, zaradi česar smo se znašli v območju globalnega maksimuma, kar nas je približalo rešitvi problema.

Nastavitev GA

Genetski algoritem išče rešitve z dvema metodama hkrati: z izbiro hiperravnin ( hiperravninsko vzorčenje) in hribovsko metodo. Crossover doseže prvo od teh, ker združuje in združuje vzorce staršev v njihovih otrocih. Mutacija zagotavlja drugo metodo: posameznik je naključen na nek način spremeni

Postavlja se vprašanje: katera od teh metod je boljša pri iskanju dobrih rešitev? Študije so pokazale, da pri preprostih problemih, kot je maksimiranje unimodalne funkcije, GA z mutacijo (in brez križanja) hitreje najdejo rešitve. Ta metoda zahteva tudi manjšo velikost populacije. Za kompleksne večekstremne funkcije je bolje uporabiti GA s križanjem, saj je ta metoda bolj zanesljiva, čeprav zahteva večja velikost populacije.

Z vidika šablonskega izreka mutacija le škoduje rasti števila predstavnikov dobre predloge, ker jih spet uniči. Vendar pa je mutacija preprosto potrebna za GA z majhno populacijo. Dejstvo je, da majhne populacije ponavadi (prezgodnja konvergenca prezgodnja konvergenca

). To je situacija, ko imajo v nekaterih položajih vsi posamezniki enak bit, vendar tak niz bitov ne ustreza globalnemu ekstremu. Hkrati križanec praktično ne spremeni populacije, saj so vsi posamezniki skoraj enaki. V tem primeru lahko mutacija obrne "zagozden" bit v enem od posameznikov in ponovno razširi iskalni prostor. (Predstavimo koncept selekcijski pritisk< f >selekcijski pritisk

) je merilo, kako različne so možnosti, da so najboljši in najslabši posamezniki v populaciji v vmesni populaciji. Pri proporcionalnem izboru se ta vrednost ponavadi zmanjšuje z naraščajočo povprečno pripravljenostjo populacije. Dejansko je za vsakega posameznika razmerje f ⁄ teži k 1, kar pomeni, da so možnosti, da slabi in dobri posamezniki ustvarijo potomce, enake. Ko se poveča p c ali p m in zmanjša selekcijski pritisk (na primer z uporabo drugih selekcijskih strategij), se reprodukcija predstavnikov prilagojenih predlog upočasni, vendar se pojavi intenzivno iskanje drugih predlog. Nasprotno pa zmanjšanje p c ali p m in povečanje selekcijskega pritiska vodi do intenzivne uporabe najdenih dobrih vzorcev, manj pozornosti pa se posveča iskanju novih. Tako za učinkovito delo genetski algoritem mora vzdrževati občutljivo ravnovesje med raziskovanje in uporaba

. To lahko formuliramo tudi kot potrebo

uravnotežena konvergenca

Klasični GA je dober za razumevanje delovanja genetskih algoritmov, vendar ni najučinkovitejši med njimi. Zdaj si bomo ogledali različne možnosti kodiranja, genetske operaterje in izbirne strategije ter druge modele GA.

Kodiranje

Če primerjamo kodiranje z binarno in nebinarno abecedo, potem ponuja prva možnost najboljše iskanje z uporabo hiperravnin, saj zagotavlja največje število le-teh. Dejansko, če morate kodirati 2 vrednosti L, potem bo za binarno abecedo število hiperravnin 3 L, medtem ko bo pri uporabi, na primer, štirimestne abecede, dolžina besed 2-krat manjša in tam bo 5 L ⁄ 2 hiperravnin, tj. manj .

Drug argument v prid binarnih abeced je, da zahtevajo manjšo velikost populacije za vsak znak, ki se pojavi na vsakem položaju. Dejansko, tudi če obstajata samo dve vrstici, obstaja možnost, da sta na vsakem položaju v populaciji tako 0 kot 1 (to pomeni, da je ena vrstica rezultat inverzije druge). Če je abeceda močnejša, potem populacija dveh vrstic zagotovo ne bo vsebovala več znakov na vsakem mestu in pred uporabo mutacije večina

iskalni prostor bo nedostopen s križnega vidika. Po uporabi mutacije bo drugi del postal nedostopen.

Po drugi strani pa nebinarne abecede pogosto zagotavljajo bolj vizualno predstavitev rešitev problema. Raziskave so pokazale, da bodo genetski algoritmi za večino funkcij delovali bolje, če so parametri kodirani v niz siva koda , namesto neposredne binarne kode. To je posledica t.i. Hamming klifi , ko se na primer števili 7 in 8 razlikujeta za 4 bite. Binarno kodiranje doda dodatne vrzeli, kar oteži iskanje. To lahko pokažemo s primerom: naj bo funkcija f (x) = x 2 minimizirana. Če je v populaciji sprva prevladovalo negativno dobre rešitve

Kodiranje s plavajočo vejico je tudi boljše od neposrednega binarnega kodiranja. Na vprašanje, ali je boljše od kodiranja s kodo Gray, lahko odgovorimo, da prva možnost deluje bolje za nekatere naloge, druga možnost pa za druge. Kako določiti, katero možnost uporabiti za določeno nalogo, še ni znano.

Crossover

Zgoraj smo razpravljali o enotočkovnem križišču.

pri dvotočkovno križišče Za starševski par sta naključno izbrani 2 ločilni točki, starša pa izmenjata vrzeli med njima. Rezultat sta dva otroka. V tem primeru je nize priročno predstaviti kot obroče:

Določujoča dolžina je v tem primeru prav tako izmerjena v obroču, tako da je za vzorec, kot je 1*****1, z enotočkovnim križiščem določujoča dolžina 6, točka odseka pa vedno pade med najbolj oddaljene fiksne bite , pri dvotočkovnem križišču pa je ta dolžina 1.

Opozoriti je treba, da je enotočkovno križišče poseben primer dvotočkovnega križišča, ko je ena od točk križišča fiksna.

Homogeno križanje se izvede na naslednji način: eden od otrok podeduje vsak bit z verjetnostjo p 0 od prvega starša, sicer pa od drugega. Drugi otrok prejme vse preostale nepodedovane bite. Običajno je p0 = 0,5. Za homogeno križanje odločilna dolžina vzorca ni pomembna in na splošno je v večini primerov vzorec uničen. Ta agresivni operator ni najbolj primeren za izbiro hiperravnin, vendar je njegova uporaba upravičena, ko je velikost populacije majhna, saj preprečuje prezgodnjo konvergenco, ki je značilna za takšne populacije.

Izbirne strategije

Kot smo že omenili, je za proporcionalno selekcijo značilno zmanjšanje selekcijskega pritiska s povečanjem povprečne sposobnosti populacije. To pomanjkljivost je mogoče popraviti s skaliranjem ( skaliranje): pri vsaki generaciji se lahko najslabši posameznik šteje za ničelnega.

Izbor ranga (izbor ranga) se razlikuje od sorazmernega v tem, da je za vsakega posameznika njegova verjetnost, da konča v vmesni populaciji, sorazmerna z njegovo zaporedno številko v populaciji, razvrščeni glede na naraščajočo sposobnost. Tovrsten izbor ni odvisen od povprečne kondicije populacije.

Izbor turnirja (izbor turnirja) se izvede na naslednji način: t posameznikov je naključno izbranih iz populacije in najboljši med njimi je uvrščen v vmesno populacijo. Ta postopek se ponovi N-krat, dokler ni vmesna populacija zapolnjena. Najpogostejša možnost je t = 2. Turnirska izbira je bolj agresivna kot proporcionalna izbira.

Izbira obrezovanja (izbira obrezovanja): populacija je razvrščena po sposobnosti, nato se vzame določen delež najboljših in izmed njih se N-krat naključno izbere posameznik za nadaljnji razvoj.

Strategije za ustvarjanje nove generacije

Obstajata dve vrsti oblikovanja nove generacije po prejemu številnih otrok zaradi križanja in mutacije:

1. otroci nadomeščajo starše;
2. nova generacija je sestavljena iz celote tako otrok kot njihovih staršev, na primer z izbiro N najboljših.

Tudi za oblikovanje nove generacije je mogoče uporabiti načelo elitizma: določeno število najboljših posameznikov prejšnje generacije (pogosto enega najboljšega posameznika) je treba vključiti v novo generacijo.

Uporaba druge strategije in elitizma se izkaže za zelo koristno za učinkovitost GA, saj ne dopušča izgube. najboljše rešitve.

Na primer, če se je populacija zbližala na lokalnem maksimumu in je mutacija prinesla eno od vrstic v globalno regijo, potem je s prvo strategijo zelo verjetno, da bo ta posameznik izgubljen zaradi križanja, in rešitev za problem ne bo dosežen. Če se uporabi elitizem, bo nastala dobra rešitev ostala v populaciji, dokler se ne najde še boljša.

Nekateri modeli genetskih algoritmov

Klasični GA je bil obravnavan zgoraj. Naj spomnimo, da ga je ustvaril Holland (1975).

Genitor Ta algoritem je ustvaril D. Whitley. Genitor

• -podobni algoritmi se od klasičnih GA razlikujejo po naslednjih treh lastnostih: Le na vsakem koraku eno nekaj naključnih staršev ustvari le eno
• otrok. Ta algoritem je ustvaril D. Whitley. Ta otrok ne nadomešča starša, ampak enega najslabših posameznikov v populaciji (v izvirniku
• - najslabši).

Izbor posameznika za nadomeščanje se izvaja glede na njegov čin (rating), in ne glede na njegovo sposobnost. Ta algoritem je ustvaril D. Whitley. Trdi se (Syswerda, 1991), da v

iskanje hiperravnin je boljše, konvergenca pa hitrejša kot pri klasičnem GA.

C.H.C. C.H.C. stoji za Medgeneracijska elitistična selekcija, heterogena rekombinacija, kataklizmična mutacija

• . Ta algoritem je ustvaril Eshelman (1991) in ima naslednje parametre: Za novo generacijo so izbrani najboljši N posamezniki med starši in otroki. Podvojene vrstice niso dovoljene.
• Za križanje je izbran naključni par, vendar ni dovoljeno, da je Hammingova razdalja med staršema majhna ali da je razdalja med skrajnima različnima bitma majhna.
• Za križanje se uporablja vrsta homogenega križanja HUX (Polenotni križanec): točno polovica bitov vsakega starša gre otroku.
• Velikost populacije je majhna, okoli 50 posameznikov. To upravičuje uporabo homogenega križanca.
• CHC nasprotuje agresivni selekciji agresivnemu križanju, a ga majhna populacija vseeno hitro pripelje do stanja, ko se ustvarijo le bolj ali manj enake linije. V tem primeru velja CHC kataklizmična mutacija: Vsi nizi razen najmočnejših so podvrženi močni mutaciji (približno tretjina bitov se spremeni). Tako se algoritem znova zažene in nato nadaljuje z delom, pri čemer uporabi samo križanje.

Hibridni algoritmi

Ideja hibridni algoritmi (hibridni algoritmi) je sestavljen iz kombinacije genetskega algoritma z neko drugo metodo iskanja, primerno za dano težavo (to se pogosto zgodi plezanje v hribe). Pri vsaki generaciji je vsak nastali otrok optimiziran s to metodo, nato pa se izvedejo običajna dejanja GA. Pri uporabi plezanje v hribe Izkazalo se je, da vsak posameznik doseže lokalni maksimum, blizu katerega se nahaja, nato pa je podvržen selekciji, križanju in mutaciji.

Takšen način razvoja imenujemo Lamarckova evolucija, pri kateri se posameznik lahko uči, nato pa pridobljene veščine zabeleži v svoj genotip, da bi jih nato prenesel na svoje potomce. In čeprav ta metoda zmanjšuje sposobnost algoritma, da najde rešitev z izbiro hiperravnin, se v praksi hibridni algoritmi izkažejo za zelo uspešne. To je posledica dejstva, da je običajno velika verjetnost, da bo eden od posameznikov padel v območje globalnega maksimuma in se bo po optimizaciji izkazal za rešitev problema.

Genetski algoritem lahko hitro najde dobre rešitve v iskalnem prostoru, vendar ima lahko težave pri izpeljavi najboljših iz njih. Metoda, kot je plezanje v hribe hitro doseže lokalni maksimum, vendar ne more iskati globalnega. Kombinacija teh dveh algoritmov lahko izkoristi oboje.

Vzporedni GA

V naravi se vsi procesi odvijajo vzporedno in neodvisno drug od drugega. Genetske algoritme je mogoče organizirati tudi kot več procesov, ki tečejo vzporedno, kar bo povečalo njihovo učinkovitost.

Spremenimo klasični GA v vzporednega. Za to bomo uporabili izbor turnirjev. Ustvarimo N ⁄ 2 procesov (v nadaljevanju je proces mišljen kot določen stroj, procesor, ki lahko deluje samostojno). Vsak izmed njih bo naključno izbral 4 posameznike iz populacije, organiziral 2 turnirja in križal zmagovalce. Nastali otroci bodo vpisani v novo generacijo. Tako se bo v enem ciklu delovanja enega procesa zamenjala cela generacija.

Otoški modeli

Občasno (npr. vsakih 5 generacij) procesi (ali otoki) izmenjajo nekaj dobrih osebkov. To se imenuje migracija. Otokom omogoča izmenjavo genskega materiala.

Ker so otoške populacije običajno majhne, ​​se podpopulacije ponavadi prezgodaj zbližajo. Zato je pomembno, da pravilno nastavite frekvenco selitve. Prepogosta selitev (ali selitev prevelikega števila osebkov) bo povzročila mešanje vseh podpopulacij in takrat se otoški model ne bo veliko razlikoval od običajnega GA. Če je selitev preredka, ne bo mogla preprečiti prezgodnje konvergence subpopulacij.

Genetski algoritmi so stohastični, zato lahko različna izvajanja algoritma povzročijo, da se populacija zbliža z različnimi rešitvami (čeprav so vse do neke mere "dobre"). Otočni model vam omogoča, da algoritem zaženete večkrat hkrati in poskušate združiti »dosežke« različnih otokov, da dobite najboljšo rešitev v eni od podpopulacij.

Celični genetski algoritmi

Cellular Genetic Algorithms je vzporedni model GA.

Vsak proces lahko komunicira samo s štirimi svojimi sosedi (zgoraj, spodaj, levo, desno). Vsaka celica vsebuje točno enega posameznika. Vsak proces bo med svojimi sosedi izbral najboljšega posameznika, z njim križal posameznika iz svoje celice in v svojo celico namestil enega nastalega otroka namesto svojega starša.

Ko takšen algoritem deluje, se pojavijo učinki, podobni modelu otoka. Sprva imajo vsi posamezniki naključno sposobnost (na sliki je določena z barvo). Po več generacijah se oblikujejo majhna območja podobnih osebkov s podobno kondicijo. Ko algoritem deluje, ta področja rastejo in tekmujejo med seboj.

Drugi modeli

Doslej smo upoštevali GA s fiksnimi parametri, kot so velikost populacije, dolžina niza, križanje in verjetnost mutacije. Vendar pa obstajajo genetski algoritmi, v katerih je mogoče te parametre spreminjati in prilagajati.

Na primer, naj bo verjetnost mutacije za vsakega posameznika ločena.

Nizu posameznika lahko dodate podniz, ki kodira to verjetnost. Pri izračunu primernosti bo ta podniz prezrt, vendar bo podvržen križanju in mutaciji na enak način kot preostali del niza. Verjetnost, da bo vsak bit danega posameznika obrnjen med mutacijo, bo enaka vrednosti, ki jo kodira dodan podniz.

Verjetnosti mutacije se inicializirajo naključno.

Thomas Back (1992) je v svojem delu ugotovil, da pri unimodalnih funkcijah možnost z globalno verjetnostjo mutacije deluje bolje, pri multiekstremalnih funkcijah pa uporaba adaptivne mutacije daje boljše rezultate.

Opažanja

Naj izpostavimo nekaj ugotovitev raziskovalcev genetskih algoritmov.

Dejavniki, ki ustvarjajo kompleksnost za GA

Če želite doseči dobre rezultate, morate izbrati pravo velikost populacije. Graf prikazuje odvisnost števila izračunov fitnes funkcije za iskanje maksimuma unimodalne funkcije od velikosti populacije. Vidimo lahko, da obstaja optimalna velikost populacije. Dejansko, če je populacija majhna, potem bo z dano omejitvijo števila izračunov funkcije fitnesa (in s tem fiksnim časom izračuna) imela čas za ustvarjanje večjega števila generacij, vendar bo najverjetneje konvergirala prezgodaj .

Prevelika populacija mora najti rešitev, vendar morda nima časa doseči to točko, saj ima majhno število generacij.

Za algoritme s križanjem (tj. brez mutacije) obstajajo ocene optimalne velikosti, za GA z mutacijo (in brez križanja) pa jih še ni. Poskusi pa kažejo, da tudi zanje obstaja optimalna velikost populacije. V vsakem primeru je odvisno od naloge.

• Sklepi
• Genetski algoritmi so univerzalna metoda za optimizacijo večparametrskih funkcij in so zato sposobni rešiti širok nabor problemov. Genetski algoritmi zagotavljajo ogromno raziskovalnega materiala zaradi velika količina
• modifikacije in parametri. Pogosto lahko majhna sprememba enega od njih vodi do nepričakovanega izboljšanja rezultata.

Hkrati je treba zapomniti, da je uporaba GA uporabna le v primerih, ko za določen problem ni primernega posebnega algoritma rešitve. V primerjavi s takim algoritmom se GA ne bo obnesel vsaj nič bolje (z morebitno izjemo hibridnega algoritma).

• Primeri uporabe GA
• Prikaz dela klasičnega GA na multiekstremalni funkciji (http://ai.bpa.arizona.edu/~mramsey/ga.html).
• Reševanje problema trgovskega potnika (TSP) z uporabo GA (http://lib.training.ru/Lib/ArticleDetail.aspx?ar=803&l=&mi=93&mic=112).
• Usposabljanje človeškega modela za hojo z uporabo GA (http://www.naturalmotion.com/pages/technology.htm).

Literatura

1. Še en prikaz dela GA (http://www.rennard.org/alife/english/gavgb.html).
2. Darrel Whitley, Vadnica za genetski algoritem, Statistika in računalništvo (4): 65-85, 1994.
3. Darrel Whitley, An Overview of Evolutionary Algorithms: Practical Issues and Common Pitfalls, Journal of Information and Software Technology 43: 817-831, 2001.
4. K. Deb, S. Agrawal, Razumevanje interakcij med parametri genetskega algoritma, 1998.
5. Isaev S.A. Priljubljeno o genetskih algoritmih (http://algolist.manual.ru/ai/ga/ga1.php).

Bulat Yaminov

Hvala, uporaben članek.

Rad bi vas opozoril na več točk.

V razdelku?Predloge? V stolpcu so navedeni predstavniki vzorca. Pri tretjem in četrtem predstavniku naj bo na četrtem mestu namesto 1 zapisano število 0. V odstavku pred sliko kocke piše, da »vzorec določa hiperravnino v njej?«, kar velja le za nekatere vzorce. . Na primer *11 ni več hiperravnina (kodimenzija ni enaka 1).

Upamo, da bodo obiskovalci te strani upoštevali vaše komentarje.

In nekaj jezikovnih napak.<... ...="">

Hvala, tipkarske napake, ki ste jih omenili, so popravljene.

V razdelku »Primeri uporabe GA« so na žalost 3 nedelujoče povezave.

Ta razdelek opisuje koncept preprostega genetskega algoritma (GA), namenjenega reševanju različnih problemov optimizacije. Predstavljeni in smiselno opisani so pojmi, ki se uporabljajo v teoriji in aplikacijah GA. Predstavljen je temeljni izrek GA in predstavljena je teorija vezij, ki predstavljajo teoretično osnovo GA. Obravnavana so konceptualna vprašanja glede prednosti in slabosti GA.

1.1. Preprost genetski algoritem

Osnove teorije genetskih algoritmov je oblikoval J. G. Holland v svojem temeljnem delu, nato pa so jih razvili številni drugi raziskovalci. Najbolj znana in pogosto citirana monografija D. Goldberga, ki sistematično predstavlja glavne rezultate in področja. praktična uporaba GA.

GA uporabljajo načela in terminologijo, izposojeno iz biološka znanost– genetika. V GA vsak posameznik predstavlja potencialno rešitev nekega problema. V klasičnem GA je posameznik kodiran z nizom binarnih znakov – kromosomom, katerega vsak del se imenuje gen. Skupina posameznikov – možnih rešitev – sestavlja populacijo. Iskanje optimalne ali suboptimalne rešitve problema se izvaja v procesu evolucije populacije, tj. zaporedno pretvorbo enega končna množica rešitve drugemu z uporabo genetskih operaterjev reprodukcije, križanja in mutacije. EV uporablja mehanizme naravna evolucija, ki temelji na naslednjih načelih:

1. Prvo načelo temelji na konceptu preživetja najmočnejših in naravni selekciji po Darwinu, ki ga je leta 1859 oblikoval v knjigi »Izvor vrst s pomočjo naravne selekcije«. Po Darwinu imajo posamezniki, ki so sposobni bolje reševati probleme v svojem okolju, več možnosti za preživetje in se pogosteje razmnožujejo (razmnožujejo). V genetskih algoritmih vsak posameznik predstavlja rešitev nekega problema. Po analogiji s tem načelom posamezniki z najboljše vrednosti ciljne (fitnes) funkcije imajo veliko možnost preživetja in razmnoževanja. Formalizacijo tega načela, kot bomo videli kasneje, izvaja operater reprodukcije.
2. Drugo načelo izhaja iz dejstva, da je kromosom potomca sestavljen iz delov, ki izvirajo iz kromosomov staršev. To načelo je leta 1865 odkril G. Mendel. Njegova formalizacija zagotavlja osnovo za upravljavca prehoda.
3. Tretje načelo temelji na konceptu mutacije, ki ga je leta 1900 odkril de Vres. Sprva je bil ta izraz uporabljen za opis pomembnih (ostrih) sprememb v lastnostih potomcev in njihovo pridobitev lastnosti, ki jih starši niso imeli. Po analogiji s tem principom genetski algoritmi uporabljajo podoben mehanizem za dramatično spreminjanje lastnosti potomcev in s tem povečanje raznolikosti (variabilnosti) posameznikov v populaciji (nabor rešitev).

Ta tri načela tvorijo jedro EV. Z njihovo uporabo se populacija (številne rešitve določenega problema) razvija iz generacije v generacijo.

Razvoj umetne populacije – iskanje več rešitev za določen problem – lahko formalno opišemo v obliki algoritma, ki je predstavljen na sliki 1.1.

GA prejme nabor parametrov optimizacijskega problema in jih kodira v zaporedja končne dolžine v neki končni abecedi (v najpreprostejšem primeru v binarni abecedi "0" in "1").

Predpreprosti GA naključno ustvari začetno populacijo kromosomov (nizov). Algoritem nato ustvari naslednjo generacijo (populacijo) z uporabo naslednjih treh osnovnih genetski operaterji:

1. reprodukcijski operater (OR);
2. operater prehoda (crossover, OK);
3. operator mutacije (OM).

Genetski algoritmi niso le naključno iskanje, temveč učinkovito uporabljajo informacije, ki so se nabrale v procesu evolucije.

V procesu iskanja rešitve je potrebno ohraniti ravnotežje med »izkoriščanjem« trenutno najboljših rešitev in širjenjem iskalnega prostora. Različne metode iskalniki to težavo rešujejo na različne načine.

Na primer, gradientne metode praktično temeljijo le na uporabi najboljših trenutnih rešitev, kar na eni strani poveča hitrost konvergence, na drugi strani pa povzroči problem lokalnih ekstremov. Pri polarnem pristopu naključne metode iskanja uporabljajo vsi