Lokální prohledávání 24. dubna 2023 1 Lokální prohledávání obecně 2 Tabu prohledávání 3 Simulované žíhání 4 Genetické algoritmy Konstruktivní vs. lokální metody Konstruktivní metody začneme s prázdným rozvrhem do rozvrhu přidáváme postupně jednotlivé úlohy tak, aby byl rozvrh stále konzistentní Lokální prohledávání začneme s úplným nekonzistentním rozvrhem triviálně: s náhodně vygenerovaným snažíme se najít lepší „podobný” rozvrh lokálními změnami kvalitu rozvrhu posuzujeme optimalizačními kritérii např. makespan optimalizační kritéria vyhodnocují také konzistenci rozvrhu např. počet porušených precedenčních omezení Hybridní přístupy kombinace obou metod Hana Rudová, FI MU: Lokální prohledávání 2 24. dubna 2023 Algoritmus lokálního prohledávání  ¡ ¢£ x F(S) globální optimum lokální optimum 1 Inicializace k = 0 výběr iniciálního rozvrhu S0 zaznamenání dosud nejlepšího rozvrhu: Sbest = S0 a best_cost = F(S0) 2 Výběr a aktualizace výběr rozvrhu z okolí: Sk+1 ∈ N(Sk ) pokud kriterium přijetí rozvrhu nesplňuje žádný prvek N(Sk ), pak algoritmus končí jestliže F(Sk+1) < best_cost pak Sbest = Sk+1 a best_cost = F(Sk+1) 3 Ukončení jestliže platí podmínky ukončení pak algoritmus končí jinak k = k + 1 a skok na krok 2. Hana Rudová, FI MU: Lokální prohledávání 3 24. dubna 2023 Jeden stroj + nepreemptivní úlohy Reprezentace rozvrhu permutace n úloh příklad se šesti úlohami: 1,4,2,6,3,5 Definice okolí párová výměna sousedních úloh příklad: 1,4,2,6,3,5 se změní např. na 1,4,2,6,5,3 možných rozvrhů v okolí: n − 1 nebo výběr libovolné úlohy v rozvrhu a umístění na libovolnou pozici příklad: z 1,4,2,6,3,5 náhodně vybereme 4 a dáme ji jinam: 1,2,6,3,4,5 možných rozvrhů v okolí: ≤ n(n − 1) Hana Rudová, FI MU: Lokální prohledávání 4 24. dubna 2023 Iniciální řešení & podmínky ukončení Iniciální řešení generujeme náhodně heuristicky např. konstruktivním algoritmem jako jsou řídící pravidla Podmínka ukončení typicky zadaný počet iterací omezená doba běhu počet porovnání účelové funkce žádné zlepšení nezískáno po daném počtu iterací Hana Rudová, FI MU: Lokální prohledávání 5 24. dubna 2023 Výběr rozvrhu z okolí Lokální změna úprava rozvrhu výběrem rozvrhu z okolí Výběr rozvrhu z okolí, tj. prohledání okolí a výběr vhodného kandidáta náhodný výběr výběr nejslibnějšího kandidáta vybíráme rozvrh s nejlepší hodnotou účelové funkce v okolí snaha o zlepšení hodnoty účelové funkce Hana Rudová, FI MU: Lokální prohledávání 6 24. dubna 2023 Kritérium výběru rozvrhu Kritérium výběru rozvrhu = kriterium přijetí/odmítnutí rozvrhu akceptovat vždy lepší rozvrh? někdy akceptovat i horší rozvrh? Metody akceptování horšího rozvrhu pravděpodobnostní náhodná procházka: s malou pravděpodobností (např. 0.01) akceptujeme i horší rozvrh simulované žíhání deterministická tabu prohledávání: udržujeme tabu seznam několika posledních stavů/změn, které jsou pro další výběr nepřípustné Hana Rudová, FI MU: Lokální prohledávání 7 24. dubna 2023 Tabu prohledávání Deterministické kritérium přijetí/odmítnutí rozvrhu Udržován tabu seznam několika posledních změn v rozvrhu tabu seznam = seznam zakázaných změn každá nová změna je umístěna na vrchol tabu seznamu př. uchovávané změny: výměna úloh j a k okolí omezeno na rozvrhy, které nepožadují změnu z tabu seznamu zabraňuje cyklení příklad triviáního cyklení: první krok: prohození úloh 3 a 4, druhý krok: prohození úloh 4 a 3 pevná délka seznamu (typicky: 5-9) nejstarší změny z tabu seznamu odstraněny příliš malá délka: nebezpečí cyklení příliš velká délka: může omezit prohledávání příliš Aspirační kritérium určuje, kdy je možné akceptovat i změny v tabu seznamu př. změna z tabu seznamu povolena, pokud zlepšeno F(Sbest) Hana Rudová, FI MU: Lokální prohledávání 8 24. dubna 2023 Algoritmus tabu prohledávání 1 k = 1 výběr iniciálního rozvrhu S1 použitím heuristiky, Sbest = S1 2 výběr Sc ∈ N(Sk ) jestliže je změna Sk → Sc zakázána protože je v tabu seznamu a není splněno aspirační kritérium pak běž na krok 2 3 jestliže změna Sk → Sc není zakázána tabu seznamem nebo je splněno aspirační kritérium pak Sk+1 = Sc ulož reversní změnu na vrchol tabu seznamu posuň další pozice v tabu seznamu o pozici níže smaž poslední položku z tabu seznamu jestliže F(Sc ) < F(Sbest) pak Sbest = Sc 4 k = k + 1 jestliže platí podmínka ukončení pak konec jinak běž na krok 2. Hana Rudová, FI MU: Lokální prohledávání 9 24. dubna 2023 Příklad: tabu seznam Uvažujte rozvrhovací problém s 1|| wj Tj opakování: Tj = max(Cj − dj , 0) úlohy 1 2 3 4 pj 10 10 13 4 dj 4 2 1 12 wj 14 12 1 12 Okolí: všechny rozvrhy získané párovou výměnou sousedních úloh Výběr rozvrhu z okolí: vybereme nejlepší rozvrh Tabu seznam: páry úloh (j, k), které byly přehozeny při posledních dvou změnách S1 = (2, 1, 4, 3) F(S1) = wj Tj = 12 · 8 + 14 · 16 + 12 · 12 + 1 · 36 = 500 = F(Sbest) F(1, 2, 4, 3) = 480 F(2, 4, 1, 3) = 436 = F(Sbest) F(2, 1, 3, 4) = 652 Tabu seznam: (1, 4) Hana Rudová, FI MU: Lokální prohledávání 10 24. dubna 2023 Příklad: tabu seznam (pokračování) S2 = (2, 4, 1, 3), F(S2) = 436 F(4, 2, 1, 3) = 460 F(2, 1, 4, 3)(= 500) tabu! F(2, 4, 3, 1) = 608 Tabu seznam: (2, 4), (1, 4) S3 = (4, 2, 1, 3), F(S3) = 460 F(2, 4, 1, 3)(= 436) tabu! F(4, 1, 2, 3) = 440 F(4, 2, 3, 1) = 632 Tabu seznam: (2, 1), (2, 4) F4 = (4, 1, 2, 3), F(S4) = 440 F(1, 4, 2, 3) = 408 = F(Sbest) F(4, 2, 1, 3)(= 460) tabu! F(4, 1, 3, 2) = 586 Tabu seznam: (4, 1), (2, 1) F(Sbest) = 408 Hana Rudová, FI MU: Lokální prohledávání 11 24. dubna 2023 Cvičení: tabu seznam Uvažujte rozvrhovací problém s 1|| wj Tj úlohy 1 2 3 4 pj 10 10 13 4 dj 4 2 1 12 wj 14 12 1 12 Aplikujte tabu prohledávání pro iniciální řešení (2, 1, 4, 3) Okolí: všechny rozvrhy získané párovou výměnou sousedních úloh Výběr rozvrhu z okolí: vybereme nejlepší rozvrh Proveďte čtyři iterace Tabu seznam: páry úloh (j, k), které byly přehozeny při 1 jedné poslední změně výsledek: F(Sbest) = 408 2 třech posledních změnách výsledek: F(Sbest) = 436 Hana Rudová, FI MU: Lokální prohledávání 12 24. dubna 2023 Simulované žíhání: principy Myšlenka: simulace procesu ochlazování kovů na začátku při vyšší teplotě atomy více kmitají a pravděpodobnost změny krystalické mřížky je vyšší postupným ochlazováním se atomy usazují do „nejlepší polohy” s nejmenší energií a pravděpodobnost změny je menší ⇒ na začátku je tedy pravděpodobnost toho, že akceptujeme zhoršování řešení, vyšší Aplikace u lokálního prohledávání lepší nebo stejné řešení akceptováno algoritmus umožňuje akceptovat horší řešení, abychom unikli z lokálního minima pravděpodobnost přijetí horšího řešení se postupně snižuje Hana Rudová, FI MU: Lokální prohledávání 13 24. dubna 2023 Simulované žíhání: realizace Parametr chlazení t t je iniciálně vysoké: hodně změn je akceptováno t postupně klesá: horší změny jsou skoro vždy odmítnuty Rozdíl mezi kvalitou nového a existujícího řešení ∆c = F(Snew ) − F(Sold ) Metropolisovo kritérium předpoklad: minimalizace F lepší nebo stejné řešení akceptováno: ∆c ≤ 0, tj. F(Snew ) ≤ F(Sold ) pravděpodobnostní přijetí/odmítnutí rozvrhu: horší řešení (∆c > 0) akceptováno pokud U < e−∆c/t U náhodné číslo z intervalu (0, 1) Hana Rudová, FI MU: Lokální prohledávání 14 24. dubna 2023 Metropolisovo kritérium Horší řešení (F(Snew ) − F(Sold ) = ∆c > 0) akceptováno pokud U < e−∆c/t U náhodné číslo z intervalu (0, 1) ∆c > 0, tj. −∆c < 0 pokud klesá t nebo klesá −∆c, tak klesá i e−∆c/t pomůcka: porovnej e−10/100 vs. e−100/100 a e−10/100 vs. e−10/1 Graf ex Hana Rudová, FI MU: Lokální prohledávání 15 24. dubna 2023 Algoritmus simulovaného žíhání 1 k = 1 výběr iniciálního rozvrhu S1 použitím heuristiky, Sbest = S1 nastavení iniciální teploty t > 0 výběr funkce redukce teploty α(t) 2 výběr Snew ∈ N(Sk ) jestliže F(Snew ) < F(Sbest) pak Sbest = Snew , Sk+1 = Snew jinak jestliže F(Snew ) ≤ F(Sk ) pak Sk+1 = Snew jinak generuj náhodné číslo Uk jestliže Uk < e F(Sk )−F(Snew ) t pak Sk+1 = Snew jinak Sk+1 = Sk 3 t = α(t) k = k + 1 jestliže platí podmínka ukončení pak konec jinak běž na krok 2. Hana Rudová, FI MU: Lokální prohledávání 16 24. dubna 2023 Příklad: simulované žíhání Opakování: Tj = max(Cj − dj , 0) Uvažujte rozvrhovací problém s 1|| wj Tj úlohy 1 2 3 4 pj 9 9 12 3 dj 10 8 5 28 wj 14 12 1 12 Použijte simulované žíhání s iniciálním rozvrhem (3, 1, 4, 2) Okolí: všechny rozvrhy, které dostaneme sousedními párovými výměnami Výběr rozvrhu z okolí náhodně Zvolte α(t) = 0.9 × t t0 = 0.9 Použijte následující náhodná čísla: 0.17, 0.91, . . . Hana Rudová, FI MU: Lokální prohledávání 17 24. dubna 2023 Příklad: simulované žíhání (řešení) Sbest = S1 = (3, 1, 4, 2) F(S1) = wj Tj = 1 · 7 + 14 · 11 + 12 · 0 + 12 · 25 = 461 = F(Sbest ) t0 = 0.9 Snew = (1, 3, 4, 2) F(Snew ) = 316 < F(Sbest ) Sbest = (1, 3, 4, 2) F(Sbest ) = 316 S2 = (1, 3, 4, 2) t = 0.9 × 0.9 = 0.81 Snew = (1, 3, 2, 4) F(Snew ) = 340 > F(Sbest ) = 316 F(Snew ) > F(S2) = 316 U1 = 0.17 > e−(340−316)/0.81 = 1.35 × 10−13 S3 = S2 = (1, 3, 4, 2) t = 0.729 Snew = (1, 4, 3, 2) F(Snew ) = 319 > F(Sbest ) = 316 F(Snew ) > F(S3) = 316 U3 = 0.91 > e−(319−316)/0.729 = 0.016 S4 = S3 = (1, 3, 4, 2) t = 0.6561 . . . Hana Rudová, FI MU: Lokální prohledávání 18 24. dubna 2023 Praktické úvahy Iniciální teplota musí být „vysoká” kritérium přijetí rozvrhu: 40%–60% vykazuje dobré výsledky v mnoha situacích Parametr chlazení několik změn při dané teplotě jedna změna při každé teplotě t = α × t α typicky v intervalu [0.9,0.99] t = t 1+βt β typicky blízké k 0 Hana Rudová, FI MU: Lokální prohledávání 19 24. dubna 2023 Genetické algoritmy Srovnání simulované žíhání, tabu prohledávání jedno řešení je přenášeno z jedné iterace do druhé genetické algoritmy udržována populace (několika přenášených) řešení Genetické algoritmy rozvrhy jsou jednotlivci (chromozomy), kteří tvoří populaci rozhodovací proměnná (např. čas jedné úlohy) je gen hodnota rozhodovací proměnné (např. konkrétní čas) je alela každý jednotlivec je vyhodnocen kritériem vhodnosti (fitness) někteří jednotlivci mutují jednotlivci jsou vybrání k reprodukci křížením a mají děti tvořící následující populaci nejvhodnější jedinci přežijí do další populace Hana Rudová, FI MU: Lokální prohledávání 20 24. dubna 2023 Reprodukce Křížení (crossover): kombinování posloupnosti operací na jednom stroji v jednom rodičovském rozvrhu s posloupností operací na jiném stroji u jiného rodiče Operátor jednoduchého křížení není užitečný! P1=[2 1 3 4 5 6 7] P2=[4 3 1 2 5 7 6] O1=[2 1 3 2 5 7 6] O2=[4 3 1 4 5 6 7] bod řezu Každá alela (hodnota) se musí výskytnout v jedinci právě jednou používány různé formy mapování Hana Rudová, FI MU: Lokální prohledávání 21 24. dubna 2023 Křížení dané pořadím Křížení dané pořadím (Order crossover, OX) 1 Vybrány náhodně dva body křížení 2 Z rodiče 1 hodnoty mezi nimi zkopírovány na stejné pozice v potomkovi 3 Z rodiče 2 začneme od druhého bodu křížení vybírat prvky, které již nebyly vybrány z rodiče 1, a dávame je do potomka od 2. bodu křížení Hana Rudová, FI MU: Lokální prohledávání 22 24. dubna 2023 Mutace Mutace umožňuje genetickému algoritmu prohledávat prostor nedosažitelný operátorem křížení Párová výměna sousedů v posloupnosti [1, 2, . . . , n] → [2, 1, . . . , n] Mutace výměnou: změna dvou náhodně vybraných prvků permutace Mutace posunem: přesun náhodně vybraného prvku o náhodný počet míst doleva nebo doprava Mutace promícháním podseznamu: výběr dvou bodů v řetězci náhodně a náhodná permutace prvků mezi těmito dvěma pozicemi Hana Rudová, FI MU: Lokální prohledávání 23 24. dubna 2023 Výběr Ruletové kolo šance na reprodukci jsou proporcionálně závislé na vhodnosti jedince velikost každého dílu ruletového kola záleží na vhodnosti konkrétního jedince př. kritérium vhodnosti pro 6 jedinců: 5,7,1,3,3,3 první díl má velikost 5, druhý 7, třetí 1, čtvrtý 3, páty 3, šestý 3 vybraný jedinec díl pro 1.jedince díl pro 2.jedince Kroky pro ruletové kolo 1 sečti vhodnost všech jednotlivců populace: TF př. TF = 5 + 7 + 1 + 3 + 3 + 3 = 22 2 generuj náhodné číslo m mezi 0 a 22 3 vrať prvního jednotlivce populace do jehož dílu spadá m čím větší vhodnost jedince, tím větší pravděpodobnost, že se na něj strefíme Hana Rudová, FI MU: Lokální prohledávání 24 24. dubna 2023 Výběr (pokračování) Turnajový výběr 1 výběr jednoho jedince náhodně vyber skupinu t jedinců z populace vyber nejlepšího jedince 2 pokud potřebujeme vybrat k jedinců, pak postup opakujeme k-krát Jak garantovat, že nejlepší člen/členové populace přežijí? Elitářský model: nejlepší člen populace je vybrán jako člen následující populace nebo nejlepší potomci a rodiče jsou vybírání do následující populace Hana Rudová, FI MU: Lokální prohledávání 25 24. dubna 2023 Základní implementace genetického algoritmu 1 k = 1 vyber N iniciálních rozvrhů S1,1, . . . , S1,N použitím heuristiky vyhodnoť jednotlivce populace 2 vytvoř nové jednotlivce spojením jednotlivců současné populace pomocí křížení a mutace smaž členy existující populace, aby udělali místo novým jednotlivcům vyhodnoť nové jednotlivce a přidej je do populace Sk+1,1, . . . , Sk+1,N 3 k = k + 1 jestliže platí podmínka ukončení pak vrať nejlepšího jedince jako řešení a skonči jinak běž na krok 2. Hana Rudová, FI MU: Lokální prohledávání 26 24. dubna 2023 Příklad: genetické algoritmy Uvažujte rozvrhovací problém s 1| | Tj úlohy 1 2 3 4 5 pj 4 3 7 2 2 dj 5 6 8 8 17 Velikost populace: 3 Výběr v každé populaci se reprodukuje nejvhodnější jedinec triviální verze pro snadný výpočet! pro reprodukci je použita párová výměna sousedů počet možných potomků: 4 pro reprodukci náhodně vybrán jeden z nich potomek nahradí nejhoršího rodiče Iniciální populace: náhodné posloupnosti permutací Hana Rudová, FI MU: Lokální prohledávání 27 24. dubna 2023 Příklad: genetické algoritmy (řešení) Populace 1 Jedinec 25314 14352 12345 Cena 25 17 16 Vybraný jedinec: 12345 s potomkem 13245, cena 20 Populace 2 Jedinec 13245 14352 12345 Cena 20 17 16 Vybraný jedinec: 12345 s potomkem 12354, cena 17 Populace 3 Jedinec 12354 14352 12345 Cena 17 17 16 Vybraný jedinec: 12345 s potomkem 12435, cena 11 Populace 4 Jedinec 14352 12345 12435 Cena 17 16 11 Vybraný jedinec: 12435 – optimální řešení Nevýhoda takto jednoduchého nastavení algoritmu: výběr nejlepšího jedince způsobuje opakovanou reprodukci nejlepšího jedince, dokud není nahrazen lepším potomkem Hana Rudová, FI MU: Lokální prohledávání 28 24. dubna 2023 Praktické úvahy Velikost populace malá populace riskuje příliš malé pokrytí prohledávacího prostoru velká populace má velké výpočetní nároky dle empirických výsledků velikost populace kolem 30 často adekvátní velikost populace 20-100 je běžná Mutace: obvykle použita s velmi malou pravděpodobností např. mutace jednoho genu jedince Hana Rudová, FI MU: Lokální prohledávání 29 24. dubna 2023