Evoluˇcn´ı algoritmy I - pozn´amky Martin Vˇsetiˇcka
Knihy • Goldberg: Generic algorithms, ’89 • John Holland - Adaptation in natural and artifical algorithms, ’75 a ’91. Holland poloˇzil z´aklady genetick´ ym algoritm˚ um, napsal na evoluˇcn´ı algoritmy disertaci. • Mellanie Mitchell: Introduction to Genetic algorithms ’95 - obsahuje vˇse, co bude na pˇredn´aˇsk´ach. • Michalewicz: Genetic algorithms + Data structures = Evolutionary Programs, 3ed
´ Uvod Evoluˇcn´ı algoritmy jsou algoritmy, kter´e se inspiruj´ı pˇr´ırodou a aplikuj´ı jej´ı mechanismy (selekce, kˇr´ıˇzen´ı a mutace) na hled´an´ı (alespoˇ n suboptim´aln´ıho) ˇreˇsen´ı r˚ uzn´ ych probl´em˚ u. Nejˇcastˇeji jde o probl´emy optimalizaˇcn´ıho charakteru. Nejsou to vˇsak prav´e optimalizaˇcn´ı algoritmy, je lepˇs´ı se na nˇe d´ıvat opravdu jako na pouhou simulaci pˇr´ırody, kter´a jako vedlejˇs´ı produkt ˇreˇs´ı nˇejakou optimalizaˇcn´ı u ´lohu. Pˇ r´ıklady pouˇ zit´ı evoluˇ cn´ıch algoritm˚ u Hled´an´ı Hamiltonovsk´e kruˇznice
1
D˚ uleˇzit´ ym abstraktn´ım pohledem na obecn´e ˇreˇsen´ı probl´em˚ u je d´ıvat se na hled´an´ı ˇreˇsen´ı jako na prohl´ed´av´an´ı prostoru potenci´aln´ıch ˇreˇsen´ı. Tento pohled na ˇreˇsen´ı probl´em˚ u se v evoluˇcn´ıch algoritmech objevuje velmi ˇcasto.
1.1
Ok´ enko do historie
Zakladatelem genetiky se stal Gregor Mendel, brnˇensk´ y mnich, kter´ y se zab´ yval kˇr´ıˇzen´ım hrachu a d˚ usledky, kter´e to pˇren´aˇs´ı na potomstvo. Neznal vˇsak podstatu genetiky, pouze si vˇsiml jist´e z´akonitosti. Charles Darvin byl britsk´ y pˇr´ırodovˇedec a zakladatel evoluˇcn´ı biologie. Dostal grant od kr´alovny na cestu kolem svˇeta, na Galap´ag´ach si vˇsiml, ˇze zde ˇzij´ı zv´ıˇrec´ı druhy, kter´e se adaptovali ve sv´em ˇzivotn´ım prostˇred´ı. Sepsal knihu ”O p˚ uvodu druh˚ u”, ve kter´e evoluˇcn´ı teorii opˇrel o proces, kter´ y nazval jako ”pˇr´ırodn´ı v´ ybˇer”. 1.1.1
Jean-Baptiste Lamarck
Vˇedec, kter´ y se pˇrel s Darwinem o tom, kdy se m˚ uˇze mˇenit genetick´a informace jednotlivce. Tvrdil, ˇze to m˚ uˇze b´ yt po celou dobu ˇzivota jednotlivce. Pˇ r´ıklad Pokud rachitick´ y ˇclovˇek bude m´ıt d´ıtˇe s dˇevˇcetem, tak bude tak´e rachitick´e, pokud se ale rachitick´ y ˇclovˇek vypracuje ve svalovce, tak d´ıtˇe bude tak´e svalovec. 1.1.2
John Holland
Holland prisel s myslenkou, ze si vezme to podstatne s genetiky. Inspiroval se konceptem evoluce od Charlese Darwina a od Mendelovy genetiky.
2
No free lunch theorem
The no free lunch theorem for search and optimization (Wolpert and Macready 1997) applies to finite spaces and algorithms that do not resample points. All 2
algorithms that search for an extremum of a cost function perform exactly the same when averaged over all possible cost functions. So, for any search/optimization algorithm, any elevated performance over one class of problems is exactly paid for in performance over another class.
3
Genetick´ e algoritmy
Jsou zaloˇzen´e na pozorov´an´ı pˇr´ırody. Vezmˇeme si napˇr´ıklad kr´al´ıky a liˇsky. ˇ ım je tedy kr´al´ık rychlejˇs´ı, Pomal´ı kr´al´ıc´ı nepˇreˇzij´ı, protoˇze je liˇska dohon´ı. C´ t´ım m´a vˇetˇs´ı ˇsanci, ˇze pˇreˇzije a t´ım p´adem, ˇze se i rozmnoˇz´ı. Populace kr´al´ık˚ u, kter´a pˇreˇzije m´a ˇsanci se rozmnoˇzit. Mnoˇz´ı se pomal´ı kr´al´ıci s rychl´ ymi, rychl´ı s rychl´ımi, pomal´ı s pomal´ ymi apod. Pˇr´ıroda nav´ıc ˇcas od ˇcasu zas´ahne a v genetick´em materi´alu se objev´ı mutace. Podstatn´e je, ˇze ve v´ ysledku bude n´asleduj´ıc´ı generace v pr˚ umˇeru rychlejˇs´ı neˇz minul´a. U liˇsek prob´ıh´a to sam´e (jinak by jiˇz ˇza´dn´eho kr´al´ıka nedohonily). Genetick´e algoritmy vyuˇz´ıv´aj´ı princip nast´ınˇen´ y v´ yˇse k ˇreˇsen´ı r˚ uzn´ ych probl´em˚ u. Evoluˇcn´ı proces urˇcit´e populace jedinc˚ u (ˇreˇsen´ı probl´emu) prohled´av´a prostor ˇreˇsen´ı a pˇritom mus´ı udrˇzet v rovnov´aze dva navz´ajem konfliktn´ı c´ıle: prohledat co nejˇsirˇs´ı prostor a z´aroveˇ n vyuˇz´ıt souˇcasn´e nejlepˇs´ı ˇreˇsen´ı k budouc´ımu zlepˇsen´ı. Pomoc´ı genetick´ ych algoritm˚ u se ˇreˇs´ı spousta praktick´ ych u ´loh, napˇr´ıklad u ´loha obchodn´ıho cestuj´ıc´ıho (TSP), optimalizace datab´azov´ ych dotaz˚ u, . . .
3.1
Pojmy
• Jedinec (nebo tak´e ˇretˇezec nebo chromozom) je jedno ˇreˇsen´ı probl´emu (odpov´ıd´a jednomu kr´alikovi z pˇr´ıbˇehu v´ yˇse :-)). V genetick´em algoritmu se jedn´a o pole bit˚ u. • Geny jsou jednotky, ze kter´ ych je sloˇzen chromozom. Gen reprezentuje nˇejakou vlastnost objektu, napˇr´ıklad rychlost kr´al´ıka, IQ kr´al´ıka apod. U genetick´eho algoritmu odpov´ıd´a gen jednomu bitu pole. • Allela je konkr´etn´ı hodnota genu. U genetick´eho algoritmu je to 1 nebo 0. 3
• Genotyp je vektor gen˚ u 1 jednotlivce (v´ıc informac´ı). • Fenotyp je konkr´etn´ı instance genotypu. • Selekce TODO • Kˇr´ıˇzen´ı TODO • Mutace TODO • M´ıra mutace TODO • Fitness funkce (tak´e u ´ˇcelov´a funkce) je funkce, kter´a pro dan´eho jedince vrac´ı re´aln´e ˇc´ıslo, kter´e ud´av´a, jak moc je jedinec dobr´ y. Z pohledu pˇr´ırody jde tedy o ˇc´ıslo, kter´e ud´av´a, jak moc je dan´ y jedinec v prostˇred´ı adaptovan´ y. Podle fitness funkce se typicky ˇr´ıd´ı selekce (napˇr. vyberu nejlepˇs´ıch n jedinc˚ u do dalˇs´ı generace). • Explorace je prohled´av´an´ı prostoru ˇreˇsen´ı. • Exploatace je vyuˇzit´ı slibn´ ych oblast´ı. prostoru ˇreˇsen´ı ke zleˇsen´ı. • Hillclimbing je pˇr´ıkladem exploatace. Jde o iterativn´ı strategii pro prohled´av´an´ı prostoru ˇreˇsen´ı vyuˇz´ıvaj´ıc´ı nejlepˇs´ı souˇcasn´e ˇreˇsen´ı, aby naˇsla v okol´ı tohoto ˇreˇsen´ı ˇreˇsen´ı jeˇstˇe lepˇs´ı. Tato strategie konˇc´ı v lok´aln´ım nebo glob´aln´ım maximu prostoru ˇreˇsen´ı. Protoˇze jeden hillclimber by ve velk´em prostoru ˇreˇsen´ı skonˇcil s velkou pravdˇepodobnost´ı v lok´aln´ım maximu, tak se ”vysad´ı”do prostoru ˇreˇsen´ı mnoho hillclimber˚ u, ˇc´ımˇz se zv´ yˇs´ı pravdˇepodobnost, ˇze nalezneme glob´aln´ı maximum.
3.2
Genetick´ y algoritmus
Klasick´e genetick´e algoritmy pouˇz´ıvaj´ı k reprezentaci jedinc˚ u bin´arn´ı ˇretˇezce pevn´e d´elky. • (Bin´arn´ı) mutace je pak jednoduch´a zmˇena jednoho ˇci v´ıce bit˚ u na opaˇcn´ y. Pˇresnˇeji m´ame danou nˇejakou pravdˇepodobnost (typicky mal´e ˇc´ıslo v ˇra´du procent) s jakou se m´a zmˇenit bit na opaˇcn´ y, generujeme tedy pro kaˇzd´ y bit n´ahodn´e ˇc´ıslo z intervalu [0,1] a pokud je menˇs´ı neˇz stanov´a pravdˇepodobnost, pak zmˇenu provedeme. Toto opakujeme pro vˇsechny bity. 4
• (Bin´arn´ı) kˇr´ıˇzen´ı probˇehne tak, ˇze vezmeme dva jedince (dvˇe pole), rozdˇel´ıme je ve stejn´ ych m´ıstech a prohod´ıme oc´asky, ˇc´ımˇz vzniknou dva potomci.
3.3
Obecn´ y genetick´ y (i evoluˇ cn´ı) algoritmus procedure Evolution_program begin t <- 0 5
initialize P(t) evaluate P(t) while (not termination-condition) do begin t <- t + 1 select P(t) from P(t-1) alter P(t) evaluate P(t) end end
3.4
Jednoduch´ y genetick´ y algoritmus
- Osnova algoritmu: - Prohledavaci metaheuristika - Generacni princip - Zakodovany problem | | v - Geneticke operatory - Reseni - Parametry si zakodujeme do binarniho retezce. [ | | | | ] - Ilustrace na problemu batohu: - v_1, ..., v_n (veci davane do batohu), kapacita batohu C [0|0|1|0|1]
<- dame do batohu v_3 a v_5
6
- Musime si udelat ohodnoceni, hantyrkou fitness funkce f: \sum v_i
(pokud nepresahnu C)
f(j) ~> - oo
(staci i nula) (pokud presahnu sumou C)
Pozn: Fitness funkci se take rika ucelova funkce. Pozn #2: Fitness funkce se obecne spocita velmi jednoduse, pouze projde zakodovany retezec.
- P_0 ... nahodne K jedincu - P_i -> P_{i+1} - ohodnot P_i - pokud uz je nejaky jedinec dost dobry, tak skonci - jinak: - selekce - vybira ze stare populace jedince - vetsinou jednoduse tak, ze vybereme dva jedince a - roulette wheel selection: \sum_{i \in P} f_i = 1
Kazdou fitness dokazu preskalovat, tak aby jeji hodnoty byly v interval Pak f(i) odpovida pravdepodobnosti vyberu i. - krizeni - vybereme jedince x z populace P_i y P_i pak krizime jedince x, y a dostavame x’ a y’. [oooooooooo] [----------] nekde udelam caru | 7
[----ooooo] - mutace - vezmeme jedince a koukam na jednotlive bity zakodovani a s nejakou pravdepodobnosti u kazdeho bitu zmenim hodnotu na opacnou. - vloz x’, y’ do P_{i+1} Pozn. pravdepodobnost krizeni je typicky velka: 0.5, 0.6 pst. mutace je vetsinou mala: setina, tisicina, ... Inicializace b´ yv´a n´ahodn´ y v´ ybˇer jedinc˚ u, pˇr´ıpadnˇe se mohou k inicializaci pouˇz´ıt ˇreˇsen´ı, kter´e z´ısk´ame z nˇejak´e heuristiky pro dan´ y probl´em.
Proˇ c funguj´ı genetick´ e algoritmy TODO page 57 (Michalewitz)
Genetick´ e vs. evoluˇ cn´ı algoritmy Genetick´e algoritmy jsou podtˇr´ıdou evoluˇcn´ıch algoritm˚ u, jelikoˇz evoluˇcn´ı algoritmy nemus´ı pouˇz´ıvat bin´arn´ı reprezentaci jedinc˚ u a oper´atory pro mutaci a kˇr´ıˇzen´ı mohou b´ yt tak´e jin´e.
3.5
Teorie sch´ emat
Def: Sch´ema je slovo v abecedˇe {0, 1, ∗}, kter´e reprezentuje mnoˇzinu (bin´arn´ıch) ˇretˇezc˚ u1 . Znak * je z´astupn´ y za hodnotu 1 nebo 0. Pˇ r´ıklad: Sch´ema ∗ ∗ ∗ ∗ ∗ reprezentuje 25 ˇretˇezc˚ u (jedinc˚ u). Reprezentuje napˇr´ıklad jedince 10101.
E E
Pozorov´ an´ı: Existuje 3m sch´emat d´elky m. ˇ ezec d´elky m je reprezentov´an 2m sch´ematy. Pozorov´ an´ı: Retˇ
1
ˇretˇezec = jedinec
8
D˚ ukaz. Pro kaˇzd´ y bit ˇretˇezce vyberu bud’ jeho hodnotu nebo pouˇziju hvˇezdiˇcku, tedy m´am dvˇe volby na jeden bit, z toho plyne 2m sch´emat.
E
Pozorov´ an´ı: V populaci velikosti n je 2m aˇz n · 2m sch´emat, kde m znaˇc´ı d´elku ˇretˇezc˚ u.
D˚ ukaz. Jednomu ˇretˇezci odpov´ıd´a 2m sch´emat. Horn´ı odhad na poˇcet sch´emat pro n ˇretˇezc˚ u je n · 2m . ˇ ad sch´ematu S, znaˇc´ıme o(S), je poˇcet nul a jedniˇcek v z´apisu sch´emata2 . Def: R´ Def: Definuj´ıc´ı d´elka sch´ematu S, znaˇc´ıme d(S), vzd´alenost mezi prvn´ı a posledn´ı pevnou pozic´ı3 . Pˇ r´ıklad: d(1**10*) = 4 Def: Fitness sch´ematu S, znaˇc´ıme F (S), je pr˚ umˇern´a fitness vˇsech ˇretˇezc˚ u v populaci. Vˇ eta: Kr´atk´a4 nadpr˚ umˇern´a5 s mal´ ym ˇra´dem sch´emata se v populaci bˇehem bˇehu genetick´eho algoritmu exponenci´alnˇe mnoˇz´ı6 . Pozn´ amka: L´ıb´ı se n´am napr˚ umˇen´ı jedinci, protoˇze jsou to kandid´ati na dobr´e ˇreˇsen´ı. Mal´ y ˇra´d n´am vyhovuje proto, ˇze neomezuje ˇreˇsen´ı. Mal´a d´elka je vhodn´a proto, aby kompaktn´ı bloky z˚ ustaly zachov´any. A vˇeta ˇr´ık´a, ˇze tac´ı jedinci se mnoˇz´ı exponenci´alnˇe. D˚ ukaz. Oznaˇcme si populace v jednotliv´ ych generac´ıch P (t), P (t + 1), . . . . Promˇenn´a n oznaˇcuje poˇcet jedinc˚ u ve vˇsech generac´ıch a m oznaˇcuje d´elku kaˇzd´eho jedince. D˚ ukaz je zaloˇzen na rozebr´an´ı, co se dˇeje s konkr´etn´ım sch´ematem S pˇri: • selekci, • kˇr´ıˇzen´ı a • mutaci. 2
Jednoduˇse nepoˇc´ıt´ ame hvˇezdiˇcky Pevn´ a pozice znaˇc´ı 0 nebo 1. 4 Ve smyslu definuj´ıc´ı d´elky. 5 Maj´ıc´ı fitness vˇetˇs´ı neˇz pr˚ umˇernou. 6 Bez pˇr´ıkras: Kr´ atk´ a sch´emata, kter´a maj´ı nadpr˚ umˇernou hodnotu fitness funkce a maj´ı mal´ y ˇr´ ad, se v populaci bˇehem pr´ace Genetick´eho algoritmu exponenci´alnˇe mnoˇz´ı. 3
9
Oznaˇcme si C(S, t) ˇcetnost sch´ematu S v populaci P (t), tedy poˇcet ˇretˇezc˚ u v populaci, kter´e vyhovuj´ı sch´ematu S. D˚ ukaz je zaloˇzen na postupn´em odhadov´an´ı hodnoty C(S, t + 1), tedy sledujeme, jak se zmˇen´ı hodnota v dalˇs´ı generaci. • Selekce ˇ ezec v m´a pravdˇepodobnost vybr´an´ı: Retˇ pS (v) = F (v)/F (t)
(1)
P kde F (t) = Fu∈P (t) (u). Hodnota pS (v) je jednoduˇse pomˇer fitness jedince v a souˇctu vˇsech fitness. Tento pomˇer7 je pravdˇepodobnost´ı v´ ybˇeru jedince jednoduˇse proto, ˇze pˇresnˇe takto funguje ruletov´a selekce. Sch´ ema S m´a pravdˇepodobnost vybr´an´ı: pS (S) = F (S)/F (t)
(2)
Selekce jedince prob´ıh´a n-kr´at8 . Pˇri kaˇzd´em v´ ybˇeru m´am pro dan´e sch´ema S fixn´ı pravdˇepodobnost pS (S), ˇze jej vyberu. Pravdˇepodobnost vyn´asob´ım ˇcetnost´ı sch´ematu S v souˇcasn´e populaci a dostanu ˇcetnost sch´ematu S v n´asleduj´ıc´ı populaci. Ve tvaru rovnice tedy: C(S, t + 1) = C(S, t) · n · pS (S)
(3)
Rovnice ˇr´ık´a kolikan´asobnˇe se zvˇetˇs´ı ˇcetnost sch´ematu S. Rovnici m˚ uˇzeme pˇrepsat takto: C(S, t + 1) = C(S, t) ·
Fpr˚umˇern´a (t) = 7 8
F (S) Fpr˚umˇern´a (t) F (t) n
Hodnota pS (v) je normalizovan´a hodnota fitness funkce. Z populace velikosti n mus´ım opˇet vybrat n jedinc˚ u.
10
(4)
(5)
• Kˇr´ıˇzen´ı • Mutace
4
Evoluˇ cn´ı algoritmy
TODO Pro jeden konkr´etn´ı probl´em je ˇcasto moˇzn´e vymyslet mnoho fitness funkc´ı, mnoho zp˚ usob˚ u kˇr´ıˇzen´ı, selekce ale i mutace. Nicm´enˇe spoleˇcn´ y z´aklad evoluˇcn´ıch algoritm˚ u spoˇc´ıv´a v tom, ˇze v jednom kroku algoritmu proved´ad´ıme transformace populace a jedinci v evoluˇcn´ım procesu bojuj´ı o pˇreˇzit´ı.
4.1 4.1.1
Selekce Ruleta (Roulette Wheel)
P˚ uvodn´ı Hollandova selekce na populaci velikosti n fungovala takto: • sum = f1 + f2 + · · · + fn je souˇcet hodnot fitness funkce vˇsech jedinc˚ u v populaci. fi • pi = sum m´a v´ yznam oˇcek´avan´eho poˇctu vybr´an´ı jedince do populace. U jedince s pi = 0.5 tedy oˇcek´av´ame, ˇze ho vybereme v polovinˇe pˇr´ıpad˚ u.
11
Algoritmus: /* Rucicka rulety; nahodne cislo z intervalu [0,1] */ ptr = Rand(); for (sum = i = 0; i < N; i++) for (sum += p(i,t); sum > ptr; ptr++) Select(i); Popis v jgapu: A basic implementation of NaturalSelector that models a roulette wheel. When a Chromosome is added, it gets a number of ”slots”on the wheel equal to its fitness value. When the select method is invoked, the wheel is ”spun”and the Chromosome occupying the spot on which it lands is 12
selected. Then the wheel is spun again and again until the requested number of Chromosomes have been selected. Since Chromosomes with higher fitness values get more slots on the wheel, there’s a higher statistical probability that they’ll be chosen, but it’s not guaranteed. 4.1.2
Turnajov´ a selekce
Dva jedinci a, b jsou n´ahodnˇe vybr´ani z populace, kde f itness(a) < f itness(b). Je zvoleno n´ahodnˇe ˇc´ıslo r ∈ [0, 1]. Pokud r < k, kde k je nˇejak´a pˇredem zvolen´a konstanta z intervalu [0, 1] (napˇr. 0.75), pak je puˇstˇen do nov´e populace jedinec a, pokud podm´ınka neplat´ı, je puˇstˇeno b. 4.1.3
Selekce nejlepˇ s´ıch
Ze souˇcasn´e generace vybereme n nejlepˇs´ıch do dalˇs´ı generace. V knihovnˇe jgap se oper´ator naz´ yv´a BestChromosomesSelector. 4.1.4
Elitismus
Elitismus funguje tak, ˇze nˇekteˇr´ı jedinci maj´ı zajiˇstˇeno, ˇze budou puˇstˇeni do dalˇs´ı generace. B´ yv´a to urˇcit´e procento nejlepˇs´ıch jedinc˚ u v populaci (typicky 5% aˇz nˇejak´ ych 15%). Tito jedinci jsou tedy automaticky zkop´ırov´ani do nov´e populace. Nejsou tam vˇsak pˇresunuti, jinak by na tˇechto jedinc´ıch nemohly pracovat oper´atory kˇr´ıˇzen´ı a mutace. Uk´azalo se, ˇze elitismus hodnˇe pom´ah´a zlepˇsovat v´ ykon genetick´ ych algoritm˚ u.
4.2
Vˇ ezˇ novo dilema (The prisoner’s dilemma)
Je jednoduch´a hra pro dva hr´aˇce. Alice a Bob jsou zatˇceni pro sp´ach´an´ı spoleˇcn´eho zloˇcinu a jsou drˇzeni v oddˇelen´ ych cel´ach. Mezi celami nelze nijak komunikovat. Alici je nab´ıdnuta n´asleduj´ıc´ı dohoda: Pokud se pˇrizn´a a bude svˇedˇcit proti Bobovi, pak dostatne podm´ınˇen´ y trest se zkuˇsebn´ı lh˚ utou a Bob p˚ ujde do vˇezen´ı na 5 let. Nicm´enˇe pokud v tu samou dobu se Bob pˇrizn´a 13
a bude souhlasit, ˇze bude svˇedˇcit proti Alici, jej´ı svˇedectv´ı bude zdiskreditov´ano a oba dostanou 4 roky za sv´e svˇedectv´ı. Alici je ˇreˇceno, ˇze Bob dostal pˇresnˇe tu samou dohodu. Bob a Alice v´ı, ˇze pokud ani jeden z nich nebude svˇedˇcit proti tomu druh´emu, pak mohou b´ yt obvinˇeni pouze na z´akladˇe m´enˇe z´avaˇzn´ ych obvinˇen´ı a oba dostanou 2 roky vˇezen´ı. Bob/Alice Nesvˇedˇc´ı Svˇedˇc´ı Nesvˇedˇc´ı 2,2 5,0 Svˇedˇc´ı 0,5 4,4 Mˇela by Alice ”zradit”Boba a doufat v podm´ınˇen´ y trest a pˇritom riskovat ˇctyˇrlet´ y ˇzal´aˇr pokud zrad´ı i Bob? Nebo by mˇela ”spolupracovat”s Bobem (pˇrestoˇze nemohou komunikovat) a doufat, ˇze bude tak´e spolupracovat a tedy ˇze oba dostanou pouze dva roky vˇezen´ı a pˇritom riskovat, ˇze Bob ji zrad´ı a ona dostane 5 let? V tomto pˇr´ıpadˇe je lepˇs´ı zradit. Pokud by se vˇsak hra hr´ala iterovanˇe, pak jiˇz mohou nastoupit r˚ uzn´e strategie. Anatol Rapoport v soutˇeˇzi v roce 1984 vyhr´al s algoritmem TIT-FOR-TAT (opl´acen´ı). V prvn´ım kroku algoritmus ”spolupracuje”. V dalˇs´ıch kroc´ıch dˇel´a to, co udˇelal protivn´ık v minul´em kole. Tedy oplac´ı spolupraci nebo opl´ac´ı zradu.
5
Diferenci´ aln´ı evoluce
ˇ (Optimalizace Hejnem Castic) ˇ PSO (Particle Swarm Optimality) = OHC Turing . . . Von Neumann . . . sebereprodukovaci algoritmus; vymyslel teorii celluarnich automatu; Celul´arn´ı automaty Conway’s Game of Life Zivot reprodukci Thomas Ray (biolog) - byl fascinovan tim, ze v pameti to zije...
14
- udelal smrtaka, ktery obcas nejaky program zabil - programy mutovali - bojovalo se o strojovy cas - programy zacaly parazitovat (upravoval cizi program, tak aby kopiroval tohoto parazita) - po nejake se vyvinuli jedinci, kteri se byli schopni parazitismu branit. - system, ktery postupne vyvinul se jmenuje Tierra (alternativa http://en.wikipedia.org/wiki/Avida) Brooks - hierarchicky relativni model Diferencialni evoluce Populace
x_t = (x_1, \dots, x_n) \downarrow |--- vyber kamaradu (vyberu nejlepsiho a 2 kamarady: a,b,c NEBO 3 kamarady(typic \downarrow x_{t+1} \leftarrow for i = 1 \dots n do (x_t)_i [Pokud mam krizit (dle nahodneh
6
Diferenci´ aln´ı evoluce (pokraˇ cov´ an´ı)
6.1
Evoluˇ cn´ı data-mining
Evolutionary data mining Michigan vs Pittsburgsky model - lisi se v tom, co povazuji za jedince v modelu - jedinec je jedno pravidlo (Michigan), resp. jedinec je mnozina pravidel
7
SAT a TSP
Dneˇsn´ım t´ematem jsou tˇeˇzk´e kombinatorick´e u ´lohy.
7.1
SAT
• Na k´odov´an´ı probl´emu se n´am vyloˇzenˇe hod´ı bin´arn´ı k´odov´an´ı, coˇz je k´odov´an´ı, kter´e m´ame r´adi, protoˇze oper´atory se na nˇem ˇcasto vytv´aˇrej´ı velmi jednoduˇse - bin´arn´ı mutace, bin´arn´ı kˇr´ıˇzen´ı. 15
• U SATu je ovˇsem probl´em se zvolen´ım fitness funkce. Jak fitness funkci zvolit? M˚ uˇzeme poˇc´ıtat napˇr´ıklad poˇcet splnˇen´ ych klauzul´ı, coˇz je strategie, na kterou lze velmi snadno vymyslet protipˇr´ıklady, kdy EV uv´ızne v lok´aln´ım maximu. Na druhou stranu probl´em je velmi tˇeˇzk´ y a nakonec o mnoho lepˇs´ı fitness funkce nevymysl´ıme. Probl´em SATu je svou povahou podobn´ y probl´emu batohu. U tohoto probl´emu m´ame informaci o naplnˇen´ı, pˇresto m˚ uˇze b´ yt nutn´e batoh vysypat a zaˇc´ıt znovu.
7.2
TSP (´ uloha obchodn´ıho cestuj´ıc´ıho)
Oproti SATu je zde situace obr´acen´a: • fitness - velmi jednoduˇse, nen´ı s n´ı probl´em • k´odov´an´ı - obt´ıˇzn´e (nejpˇrirozenˇejˇs´ı je asi k´odov´an´ı pomoc´ı permutac´ı) Pˇ r´ıklad: TSP m´a mnoho re´aln´ ych vyuˇzit´ı, napˇr´ıklad vrt´an´ı ploˇsn´ ych spoj˚ u, kde se snaˇz´ıme, co nejv´ıce zkr´atit dobu, kterou vrtaˇcka str´av´ı pˇresuny mezi dan´ ymi body. ˇ sen´ı, kter´a jsou suboptim´aln´ı, jsou ˇcasto dostateˇcn´a. U pˇr´ıkladu Pozn´ amka: Reˇ s vrtaˇckami m˚ uˇze b´ yt ˇreˇsen´ı, kter´e je o deset procent horˇs´ı neˇz optim´aln´ı ˇ sen´ı, kter´e budu m´ıt za noc hotov´e je lepˇs´ı st´ale jeˇstˇe dostateˇcnˇe dobr´e. Reˇ neˇz ˇreˇsen´ı, kter´e bych z´ıskal aˇz za rok, ale bylo by optim´aln´ı. Pozn´ amka: K TSP se vr´atil jak´ ysi nˇemeck´ y obchodn´ı cestuj´ıc´ı, kter´ y napsal pˇr´ıruˇcku pro obchodn´ı cestuj´ıc´ı, kde byly pops´ano, jak se m´a obchodn´ı cestuj´ıc´ı chovat a tak´e se zde zmiˇ nuje hled´an´ı nejlepˇs´ı trasy. 7.2.1
K´ odov´ an´ı
Mˇesto j je na pozici i ⇔ vede hrana z i → j. 1-2-4-3-8-5-9-6-7 2 4 8 3 9 7 1 5 6
<-- cesta <-- zakodovan´ ı
16
K ˇcemu je to dobr´e? Souvislost se sch´ematy. Je vˇsak nutno poznamenat, ˇze ne kaˇzd´ y k´od je validn´ı. 1. Alternuj´ıc´ı kˇr´ıˇzen´ı [2] 3 [8] 7 [9] 1 [4] 5 [6] 7 [5] 1 [6] 9 [2] 8 [4] 3
<-- vybiram liche <-- vybiram sude
Vznikne: nem˚ uˇ zeme sem d´ at 2 | v 2 5 8 6 9 3 4 1 7 Podtrˇzen´e ˇc´ıslice jsem musel vybrat n´ahodnˇe, ale tak, aby nevznikl cyklus. 2. Uniformn´ı kˇr´ıˇzen´ı - to sam´e, co v kˇr´ıˇzen´ı v´ yˇse, jen beru pol´ıˇcka nad sebou. 3. Alternov´an´ı podcest • Vyberu n´ahodnˇe podcestu n´ahodn´e d´elky z jednoho jedince • Vyberu n´ahodnˇe podcestu n´ahodn´e d´elky z druh´eho jedince
8
Zdroje • Pˇredn´aˇsky • An Introduction to Genetic Algorithms • Genetic Algorithms + Data Structures = Evolution Programs
17
