Optimalizace & soft omezení: modely (dokončení) Omezení nad polookruhy 3 Semiring-based CSP c-polookruh (JA, + , x,0,1) J4. množina polookruhu (množina preferencí) M 0 g J4. (úplné nesplnění), 1 e J4. (úplné splnění) ^ + komutativní, idempotentní, asociativní operace I s jednotkovým prvkem 0, s absorbujím prvkem 1 x komutativní, asociativní operace, distributivní nad +, s jednotkovým prvkem 1, s absorbujím prvkem 0 J x se používá ke kombinaci preferencí několika omezení min u fuzzy CSP 0 minimum (nesplnění), 1 maximum (splnění) ^ Částečné uspořádání ((a x b) < (c xb)) fakt, že něco lze lokálně zlepšit nelze globálně ignorovat (platí pro CSP s váhami) př. a = 0.3, c = 0.4, b = 0.2 pro fuzzy CSP: není striktní monotoniel M idempotence: Va e JA: ax a = a (platí pro fuzzy CSP) omezení, které je v problému obsaženo, může být do něj přidáno beze změny významu př. x > l@10,x > l@10,x = 0@oo, přiřazení x = 0 má pro CSP s váhami úroveň konz. 20 I striktní monotonie a idempotence x zároveň pouze pro dvouprvkové JA, tj. jen pro CSPl 3 Existující vztahy: CSP = fuzzy CSP na dvouprvkové JA fuzzy CSP lze polynomiálně transformovat na CSP s váhami Hana Rudová, Omezující podmínky, 9. prosince 2019 3 Optimalizace & soft omezení: modely Definice omezení nad polookruhy Systém (S,D, V): S c-polookruh, D konečná doména, V uspořádaná množina proměnných Soft omezení (def, con): rozsah omezení con c y, def : D|Cřm| — J4. Soft problém je (C, con) nad (S,D, V), kde con ^ V, C množina omezení Projekce n-tic t ly příklad: (1,2,3,4,5) i|SÄe)d'e)= (4,1,5)1 | Kombinace c = c\ ® c 2 Ci = (defí, con{) and c 2 = (defei con-i) c = (def, con), con = coni u co^2, def {i) = defľ(t 1™) x def 2{t icZ2)l M příklad: CSP s váhami: J4 = N u {oo}, + = min, x = +, +oo, 0 zadáno omezení c\ na xy: aa 2, ab 4, ba 1, bb 0, zadáno omezení C2 na x: a 0, b 1 kombinace c = ci ® c2:1 aa 2(=2+0) ab 4(=4+0) ba 2(=1+1) bb 1 (=0+1) Hana Rudová, Omezující podmínky, 9. prosince 2019 4 Optimalizace & soft omezení: modely Řešení pro omezení nad polookruhy M Projekce c U/ c = (def, con), I c' = (def, con'), con' = con n J def (ť) S def (t) f/ftcon ft LILiIncon L M příklad (pokračování): c\ na xy: aa 2, ab 4, ba 1, bb 0, projekce c\ tt{X}- a 2, b 0 3 kombinace všech omezení v C a následovně projekce na proměnné v con M pro každé přiřazení proměnných v con vrací omezení Sol(P) jeho úroveň splnění «• příklad (pokračování): c\ na xy: aa 2, ab 4, ba 1, bb 0 c2 na x: a 0, b 1 problém Pi = ({ci,c2}, {x,y}): Sol(Pi) = (a ® c2) ^{x,yY- aa 2, ab 4, ba 2, bb 11 problém P2 = ({ci,c2}, {x}): Sol(P2) = (a ® c2) V{x}: 1 2, b ll Úroveň konzistence: blevel(P) = Sol(P) 3 příklad (pokračování): blevel(Pi) = blevel(P2) = 1 Úroveň splnění problému P = (C, con) udává omezení Sol(P) = ((g) C) U con Hana Rudová, Omezující podmínky, 9. prosince 2019 Optimalizace & soft omezení: modely Optimalizace & soft omezení: algoritmy Soft propagace 3 Klasická propagace: eliminace nekonzistentních hodnot z domén proměnných M Soft propagace: propagace preferencí (cen) nad fc-ticemi hodnot proměnných 3 snaha o získání realističtějších preferencí M výpočet realističtějších příspěvků pro cenovou funkcil ^ C je soft ^-konzistentní, jestliže pro všechny podmnožiny (k - 1) proměnných W a libovolnou další proměnnou y platí ®{cí I Ci e C a coyií ^ W} — (® {ci | Ci G Ca coyií ^ (W u {j7})}) coyií označuje proměnné v omezení a 3 uvažování (def) pouze omezení ve W stejné jako: uvažování (def) omezení ve W a omezení spojující y s W, s následnou projekcí na W Hana Rudová, Omezující podmínky, 9. prosince 2019 7 Optimalizace & soft omezení: algoritmy Soft hranová konzistence (SAC) M k = 2,W = {x} : cx = (®{Cy,cxy,cx}) tt{x}i 3 CSP: libovolná hodnota v doméně x může být rozšířena o hodnotu v doméně y tak, že je cxy splněno hodnoty a v doméně x, které nelze rozšířit na y, mají def((a)) = Ol Fuzzy CSP: úroveň preference všech hodnot x v cx je stejná jako úroveň preference daná (®{cy,cxy,cx}) tt{x}i I M Příklad na fuzzy CSP: J4. = (0,1), + = max, x = min, 0, 1 x,y e {a,b} 9 Cx ■ CL . . . 0.9, fc... 0.1, C-y • & • • • 0.9, fc... 0.5, 0.8, ab ... 0.2, ba...0, bb ... 0 * není SAC: cx dává 0.9 na x = a, ale (®{cy, cxy, cx}) ^{X} dává 0.8 na x = a ®{cy,cXy,cx} dává na (a, a) : Inm(0.9,0.8,0.9) = 0.8l ®{cy,cxy,cx} dává na (a,b) :Inm(0.5,0.2,0.9) = 0.2l projekce (<8>{cy, cxy, cx}) ^{X} dává na (a) : lnax(0.8,0.2) = 0.8 Hana Rudová, Omezující podmínky, 9. prosince 2019 8 Optimalizace & soft omezení: algoritmy Výpočet SAC Základní algoritmus pro výpočet SAC: M pro každé x a y změnit definici cx tak, aby korespondovala s (®{Cy,CXy,CX}) tt{x} 3 iterace až do dosažení stability x idempotentní (fuzzy CSP) zajištěna ekvivalence, tj. původní i nový (po dosažení SAC) problém mají stejné řešení zajištěno ukončení algoritmul x není idempotentní (CSP s váhami) 3 pro každé u, v e JA existuje w e JA taková, že v xw = u f> w se nazývá rozdíl mezi u a v, maximální rozdíl se značí u - v ± nutno požadovat novou vlastnost pro systém (a rozšířit projekci a kombinaci) M s novou vlastností zajištěna ekvivalence, při striktní monotonii zajištěno i ukončení tato vlastnost platí pro CSP s váhami Hana Rudová, Omezující podmínky, 9. prosince 2019 9 Optimalizace & soft omezení: algoritmy Řešení COP Cíl: nalezení úplného řešení s optimální hodnotou cenové funkce 3 Prohledávání lokální prohledávání i* přímé zahrnutí optimalizačního kriteria do evaluace (hodnota obj. funkce) stromové prohledávání I * metoda větví a mezí + její rozšíření CSP s omezeními: minimalizace součtu vah omezení minXCecc(^) «• velmi častá optimalizační úloha váha (cena) omezení: 0 = úplné splnění, (0, oo) částečné nesplnění, oo úplné nesplnění M hodnota cenové funkce: cena přiřazení/řešení M maximalizace je duální problém * algoritmy pro fuzzy CSP na podobných principech Hana Rudová, Omezující podmínky, 9. prosince 2019 10 Optimalizace & soft omezení: algoritmy COP jako série CSP problémů 3 Triviální metoda řešení Řešení COP jako CSP a nalezení iniciální hodnoty cenové funkce W1 M Opakované řešení CSP (í = 1...) s přidáním omezení XCecc(^) < Wl 3 Když řešení nového CSP neexistuje, pak poslední Wl dává optimum I Výpočetně zbytečně náročné Efektivní rozšíření obtížné Hana Rudová, Omezující podmínky, 9. prosince 2019 Optimalizace & soft omezení: algoritmy Metoda větví a mezí (branch&bound) BB 3 Prohledávání stromu do hloubky M přiřazené=minulé proměnné P, nepřiřazené=budoucí proměnné F M omezení pouze na minulých proměnných O, omezení na minulých i budoucích proměnných Cpp, omezení pouze na budoucích proměnných C>l Výpočet mezí 3 horní mez UB: cena nejlepšího dosud nalezeného řešení dolní mez LB: dolní odhad minimální ceny pro současné částečné přiřazení Ořezávání: LB > UB (cíl: minimalizace) M víme, že rozšíření současného částečného řešení už bude mít horší (vyšší) cenu LB než dosud nalezené řešení UB M lze proto ořezat tuto část prohledávacího prostoru M příklad: pokud nalezneme řešení s cenou 10 odřízneme všechny větve, které mají cenu vyssi nez 9 Hana Rudová, Omezující podmínky, 9. prosince 2019 12 Optimalizace & soft omezení: algoritmy Metoda větví a mezí: výběr hodnoty M Algorimus metody větví a mezí generický algoritmus rozšiřitelný jako implementace backtrackingu S možná rozšíření zejména o: pohled dopředu, výpočet dolní meze LB(d) vrací dolní odhad ceny pro každé částečné přiřazení d M použití při rozšíření o jednu proměnnou LB(dí-\,a)i I M Optimistický výběr hodnoty proceduře Select-Value-BB while D[ i s not empty vyber a smaž libovolný a e D[ takový, že min LB(ät-i,a) if Consistent(aí_i,Xí = a) a LB(ät-i,a) < UB return a (jinak ořezej a) return null (konzistentní' hodnota neexistuje) Hana Rudová, Omezující podmínky, 9. prosince 2019 13 Optimalizace & soft omezení: algoritmy Algoritmus metody větví a mezí proceduře Branch-Bound((X,D, C), UB,f^) rozdíly od backtrackingu i : = 1, D[ := Di (inicializace čitače proměnných, kopirováni domény) Reseni := null (řešeni dosud nenalezeno) repeat while 1 < i < n přiřazeni xt : = Select-Value-BB if Xi is null (žádná hodnota nebyla vrácena) i := i-1 (zpětná fáze) else i := í + 1 (dopředná fáze) D: := Di I if i = 0 if Reseni is not null return UB, Reseni else return , ,nekonzistentni ' ' else Reseni := x\,...,xn (uloženi hodnot dosud nejlepšiho přiřazeni) spočítej cenu současného přiřazení W = SCecc(^)' UB:=mm{W, UB} i := 1, nastav D'k na Dk pro k = 1... n until true end Branch-Bound Hana Rudová, Omezující podmínky, 9. prosince 2019 14 Optimalizace & soft omezení: algoritmy Dolní mez Kvalita dolní meze: velmi důležitá pro efektivitu BB Dolní mez lze ovlivnit pomocí 3 ceny minulých proměnných x vzdálenost (součet vah omezení na minulých proměnných) M lokální ceny budoucích proměnných vzhledem k minulým proměnným 3 NC* M lokální ceny budoucích proměnných ^ AC* 3 globální ceny budoucích proměnných prohledávání ruská panenka Hana Rudová, Omezující podmínky, 9. prosince 2019 Optimalizace & soft omezení: algoritmy NC* algoritmus Projekce ceny hodnot (j, *) pro každou proměnnou j do dolní hranice LB ceny řešení I j j OJ) 0,2) 0,3) ß i 0 © _»■ ni_ 1 LB=6 LB=8 Smazání hodnot (j,a) převyšující (nebo rovné) horní hranici UB LB=8 UB=10 LB=8 UB=10 Hodnotu a proměnné j značíme (j,a) 3 obrázek: proměnná j má nejprve tři hodnoty (j, 1), {j, 2), (j, 3), jejichž cena je 2,4 a 5 Všechny hodnoty proměnné j značíme (j, *) Hana Rudová, Omezující podmínky, 9. prosince 201 9 16 I Optimalizace & soft omezení: algoritmy AC* algoritmus (A) Projekce ceny hrany (i,a)(j,b) do 3 ceny hodnoty (í, a), pokud je tato cena zahrnuta ve všech hranách (í,a)(j, *) UB=11 UB=11 (í,2)(j,l) — (1,2)0', 2) — (í,2) (í,2)0'5 3) ^1 Hana Rudová, Omezující podmínky, 9. prosince 201 9 17 NC* algoritmus (B) projekce ceny hodnot pro každou proměnnou (C) smazání hodnot s cenou > UB UB=11 UB=11 Optimalizace & soft omezení: algoritmy Prohledávání ruská panenka (Russion doll search) n po sobě jdoucích BB prohledávání, každé má navíc jednu proměnnou ........ „ statické uspořádání proměnných M první podproblem obsahuje pouze n-tou proměnnou í-tý podproblem obsahuje posledních i proměnných ((n - i + 1)... n) ^0 podproblémy řešeny pomocí BB s využitím LB a UB z předchozích běhůl Při řešení podproblému (n - i + 1) M problém zahrnuje proměnné xuXí+i,...,xn I mějme částečné přiřazení pro tento podproblem (aucíí+i,cií+j) s nepřiřazenými proměnnými Xí+j+i, xnl do dolní meze lze zahrnout optimální cenu (n-í- j) podproblému optim(Xi+j+i,xn) & LB((auai+i,...,ai+j)) = dist((auai+i,... ,ai+j)) + optim(xi+j+i,... ,xn) dist{{auOLi+i,CLi+j)) vzdálenost (součet vah omezení na minulých proměnných) optimální řešení přechozích problémů použita pro: výběr hodnoty, pro zlepšení iniciální horní mezel Vnořená prohledávání se vyplatí vzhledem k prořezání stavového prostoru Hana Rudová, Omezující podmínky, 9. prosince 2019 18 Optimalizace & soft omezení: algoritmy