Srovnání prohledavačích algoritmů Srovnání prohledávacích algoritmů A — B znamená, že uzly prohledávacího stromu B jsou i v stromě A Hana Rudová, Omezující podmínky, 2. prosince 2019 2 Srovnání prohledávacích algoritmů Srovnání prohledávacích algoritmů A — B znamená, že uzly prohledávacího stromu B jsou i v stromě A M za předpokladu stejného uspořádání hodnot i proměnných Existuje srovnání i pro další algoritmy? Jaké algoritmy používat pro daný problém? Experimentální porovnání na různýc sadách problémů (benchmarks) M reálné problémy M náhodně vygenerované problémy aplikačně založené náhodné problémy Kriteria CPU čas M velikost generovaného prohledávacího stromu počet volání procedury (např. Consi stent) Hana Rudová, Omezující podmínky, 2. prosince 2019 Srovnání prohledávacích algoritmů Experimenty na reálných problémech 3 Sady reálných problémů (benchmarks), na kterých lze algoritmy porovnávat 3 CSPLib http://www.csplib.org 3 knihovna problémů pro omezující podmínky (otevřená pro nové problémy) M kolem 130 problémů z oblasti jako je rozvrhování, návrh a konfigurace, kombinatorika, bioinformatika, hry 3 popis problému, reference na jeho řešení, data, výsledky někdy i řešení nebo podrobné studie různých možností řešení M příklady ±> dopravní signalizace v čase na zadaných křižovatkách, výrobní linka, problém batohu, sledování cíle v distribuovaných senzorických sítích, ... 3 Problém: výsledky lze stále velice obtížně zobecnit na další problémy pro jeden problém je lepší jeden algoritmus, pro další problém jiný algoritmus Hana Rudová, Omezující podmínky, 2. prosince 2019 3 Srovnání prohledávacích algoritmů Náhodné problémy 3 Algoritmy porovnávány na umělých, náhodně vygenerovaných problémech M lze generovat problémy různé obtížnosti (fáze přechodu) libovolný počet datových instancí M lze testovat, co se stane (např. s parametry algoritmu) při změnách problému Náhodné binární CSP (random binary CSP) M parametry (n, m, pi, p2) M n počet proměnných 3 m počet hodnot v doméně proměnných pi pravděpodobnost, že existuje omezení na páru proměnných P2 pravděpodobnost, že omezení povoluje daný pár hodnot Hana Rudová, Omezující podmínky, 2. prosince 2019 4 Srovnání prohledávacích algoritmů Aplikačně založené náhodné problémy Identifikace problémové domény lze definovat parametrizovatelné problémy 3 problémy mají přitom specifickou (z aplikace vycházející) strukturu problémy lze náhodně generovat s různým nastavením parametrů Výhody M zaměřené na reálné problémy generování řady problémů umožňuje statistické porovnání Příklad: shop scheduling problémy 3 m strojů 3 n úloh, každá úloha se skládá z m operací prováděných na odlišných strojích operace jedné úlohy nesmí být prováděny zároveň 3 podmínky na sekvencování operací úlohy (žádné, dáno pořadí, stejné pořadí pro všechny) 3 minimalizace dokončení poslední úlohy, minimalizace největšího zpoždění úlohy, ... Hana Rudová, Omezující podmínky, 2. prosince 2019 5 Srovnání prohledávacích algoritmů Fáze přechodu 3 Náhodný fc-SAT problém M formule pevné délky jsou generovány výběrem m klauzulí každá klauzule délky k je uniformně náhodně generována z množiny všech klauzulí Obtížnost nalezení řešení M při malém počtu klauzulí Hana Rudová, Omezující podmínky, 2. prosince 2019 6 Srovnání prohledávacích algoritmů Fáze přechodu 3 Náhodný fc-SAT problém M formule pevné délky jsou generovány výběrem m klauzulí každá klauzule délky k je uniformně náhodně generována z množiny všech klauzulí Obtížnost nalezení řešení 3 při malém počtu klauzulí je většina problémů splnitelná a snadno řešitelná při velkém počtu klauzulí Hana Rudová, Omezující podmínky, 2. prosince 2019 6 Srovnání prohledávacích algoritmů Fáze přechodu 3 Náhodný fc-SAT problém M formule pevné délky jsou generovány výběrem m klauzulí každá klauzule délky k je uniformně náhodně generována z množiny všech klauzulí Obtížnost nalezení řešení 3 při malém počtu klauzulí je většina problémů splnitelná a snadno řešitelná při velkém počtu klauzulí je detekována snadno nesplnitelnost většiny problémů 3 nalezení řešení je nejobtížnější za předpokladu, že cca 50% problémů je splnitelných Hana Rudová, Omezující podmínky, 2. prosince 2019 6 Srovnání prohledávacích algoritmů Fáze přechodu 3 Náhodný fc-SAT problém M formule pevné délky jsou generovány výběrem m klauzulí každá klauzule délky k je uniformně náhodně generována z množiny všech klauzulí Obtížnost nalezení řešení 3 při malém počtu klauzulí je většina problémů splnitelná a snadno řešitelná při velkém počtu klauzulí je detekována snadno nesplnitelnost většiny problémů 3 nalezení řešení je nejobtížnější za předpokladu, že cca 50% problémů je splnitelných Fenomén fáze předchodu (phase transition) M fáze přechodu z obtížně řešitelných problémů na snadno řešitelné problémů počet volání Využití fáze přechodu: lze generovat problémy různé obtížnosti poměr počtu klauzulí vůči počtu proměných Hana Rudová, Omezující podmínky, 2. prosince 2019 6 Srovnání prohledávacích algoritmů Optimalizace & soft omezení: modely Optimalizační problém s podmínkami (COP) 3 Problém splňování podmínek (X,D,C) 3 proměnné X = {x\,... ,xn} * domény D = {Di,... ,Dn} M omezení C = {Ci,..., Cn} i* Oje definováno na Yi ^ X, Yi = {x^,... ,Xík} St d je podmnožina Du x ... x Du Hana Rudová, Omezující podmínky, 2. prosince 2019 8 Optimalizace & soft omezení: modely Optimalizační problém s podmínkami (COP) 3 Problém splňování podmínek (X, D, C) 3 proměnné X = {x\,... ,xn} M domény D = {Di,... ,Dn} M omezení C = {Ci,..., Cn} i* Q je definováno na Y* ^ X, Yi = {x^,... ,Xík} S* d je podmnožina x ... x Dik 3 Objektivní funkce obj : Sol — Základní definice: Optimalizační problém s podmínkami (constraint optimization problem) M nalezení řešení d pro (X, D, C) takové, že obj (d) je optimálni -t optimální = maximální nebo minimálni Hana Rudová, Omezující podmínky, 2. prosince 2019 8 Optimalizace & soft omezení: modely COP: operační výzkum Pevné (hard, required) omezení Cu = {Ci,..., Cn} relace 3 Q je definováno na Y* c x, Yt = {xh,... ,xik} 3 d je podmnožina x ... x Difc Měkké (soft) omezení Cs = {F\, ...,Fi} funkce Fj je definované nad Qj ^ X, Qj = {Xjlt... ,Xjt} 3 Fj je funkce do reálných čísel DJ: x ... x Djt — M+ Optimalizační problém s podmínkami (COP): (X,D,Ch,Cs) Hana Rudová, Omezující podmínky, 2. prosince 2019 9 Optimalizace & soft omezení: modely COP: operační výzkum Pevné (hard, required) omezení Cu = {Ci,..., Cn} relace 3 Q je definováno na Y* c x, Yt = {xh,... ,xik} 3 d je podmnožina x ... x Difc Měkké (soft) omezení Cs = {F\, ...,Fi} funkce Fj je definované nad Qj ^ X, Qj = {Xjlt... ,Xjt} 3 Fj je funkce do reálných čísel DJ: x ... x Djt — M+ Optimalizační problém s podmínkami (COP): (X,D,Ch,Cs) Objektivní funkce zjednodušení na X = ^ F/(d[Qj]) ^[Qj] ■ ■ ■ projekce d na Qj Hana Rudová, Omezující podmínky, 2. prosince 2019 9 Optimalizace & soft omezení: modely COP: operační výzkum Pevné (hard, required) omezení Ch = {Ci,..., Cn} 3 Q je definováno na Y* ^X,Yi= {xh,... ,xik} 3 d je podmnožina x ... x D;fc Měkké (soft) omezení Cs = {F\,..., Fi\ 3 F j je definované nad Qj ^ X, Qj = {Xjlt... ,Xjt} Fj je funkce do reálných čísel Dj1 x ... x DJř + relace funkce Optimalizační problém s podmínkami (COP): (X,D,Ch,Cs) Objektivní funkce zjednodušení na X F(d) = X^Qj]) d[Qj] ■ ■ ■ projekce d na Qj Řešení COP: d° splňující všechna omezení z tak, že = max^d) nebo F(d°) = mmdF(d) Hana Rudová, Omezující podmínky, 2. prosince 2019 Optimalizace & soft omezení: modely Použití soft omezení Problémy optimalizační, příliš podmíněné, špatně definované problémy, ... Fuzzy preference, pravděpodobnosti, ceny, váhy, úrovně požadavků,... Příliš podmíněné problémy: řešení CSP neexistuje Fi Přednáška < Cvičeni @ 10 tj . pokud PrednaskaCviceni pak Fi=10 F2 Přednáška in 4. .5 @6 t j . pokud Prednaskae{4, 5} pak F2=0 pokud Prednaska<£{4,5} pak F2=6 F3 Cviceni in 1. .4 @ 4 Hana Rudová, Omezující podmínky, 2. prosince 2019 10 Optimalizace & soft omezení: modely Použití soft omezení Problémy optimalizační, příliš podmíněné, špatně definované problémy, ... Fuzzy preference, pravděpodobnosti, ceny, váhy, úrovně požadavků,... Příliš podmíněné problémy: řešení CSP neexistuje Fi Prednáška < Cvičeni @ 10 tj . pokud PrednaskaCviceni pak Fi=10 F2 Prednáška in 4. .5 @6 t j . pokud Prednaskae{4, 5} pak F2=0 pokud Prednaska<£{4,5} pak F2=6 F3 Cviceni in 1. .4 @ 4 Problémy s nejistotou Je 0.7 nezbytné, abych přišla do středy. po..st 0.7, ct..ne 0 3 Je nezbytné, abych nepřišla příliš později než ve středu, po..st 0.7, ct 0.5, pa 0.3, so..ne 0 Hana Rudová, Omezující podmínky, 2. prosince 2019 10 Optimalizace & soft omezení: modely Použití soft omezení Problémy optimalizační, příliš podmíněné, špatně definované problémy, ... Fuzzy preference, pravděpodobnosti, ceny, váhy, úrovně požadavků,... Příliš podmíněné problémy: řešení CSP neexistuje Fi Prednáška < Cvičeni @ 10 tj . pokud PrednaskaCviceni pak Fi=10 F2 Prednáška in 4. .5 @6 t j . pokud Prednaskae{4, 5} pak F2=0 pokud Prednaska<£{4,5} pak F2=6 F3 Cviceni in 1. .4 @ 4 Problémy s nejistotou Je 0.7 nezbytné, abych přišla do středy. po..st 0.7, ct..ne 0 3 Je nezbytné, abych nepřišla příliš později než ve středu, po..st 0.7, ct 0.5, pa 0.3, so..ne 0 Špatně definované problémy: není zřejmé, která omezení definují CSP Zitra = pekne @ 80% Zitra = zamračeno @ 30% Hana Rudová, Omezující podmínky, 2. prosince 2019 10 Optimalizace & soft omezení: modely Přístupy pro soft omezení Vybrané přístupy M základní: MAX-CSP, omezení s váhami, fuzzy omezení M zobecňující: omezení nad polookruhy (semiring-based) Hana Rudová, Omezující podmínky, 2. prosince 2019 Optimalizace & soft omezení: modely Přístupy pro soft omezení Vybrané přístupy M základní: MAX-CSP, omezení s váhami, fuzzy omezení 3 zobecňující: omezení nad polookruhy (semiring-based) Rozlišení systémů na základě: (v závorkách popis pro CSP) 3 omezení - rozšíření klasického omezení (c = relace) 3 problém - rozšíření CSP (trojice (V,D,C)) 3 úroveň splnění - jak přiřazení hodnot splňuje problém (/\c0) 3 řešení - které přiřazení je (optimálním) řešením (splňují všechna omezení) úroveň konzistence problému - jak je možné nejlépe splnit problém tj. jak (optimální) řešení splňuje problém (true) Hana Rudová, Omezující podmínky, 2. prosince 2019 11 Optimalizace & soft omezení: modely Omezení s váhami, MAX-CSP 3 Omezení s váhami: Váha/cena spojená s každým omezením Omezení - dvojice (c,w(c)) M Problém - trojice (V,D,CW) M Úroveň splnění - funkce na množině přiřazení co(0) = Xčn-c => součet vah nesplněných omezení Řešení - přiřazení 9 s minimální co(9) 3 Úroveň konzistence - úroveň splnění řešení Hana Rudová, Omezující podmínky, 2. prosince 2019 12 Optimalizace & soft omezení: modely Omezení s váhami, MAX-CSP 3 Omezení s váhami: Váha/cena spojená s každým omezením Omezení - dvojice (c,w(c)) M Problém - trojice (V,D,CW) M Úroveň splnění - funkce na množině přiřazení co(0) = Xčn-c => součet vah nesplněných omezení Řešení - přiřazení 9 s minimální co(9) 3 Úroveň konzistence - úroveň splnění řešení M MAX-CSP (maximální CSP) M Váhaje rovna jedné => maximalizace počtu splněných omezení Hana Rudová, Omezující podmínky, 2. prosince 2019 12 Optimalizace & soft omezení: modely Omezení s váhami: příklad Přednáška < Cvičeni @ 10 Přednáška in 4.. 5 @6 Cvičeni in 1..4 @ 4 Přiřazení: @1 tj . juC2=1 = 1 => @0.5 tj. juc2=0. 5 = 2 => @0.1 tj. jUC2=0.1 c3: max(A + B) @(A + B)/10 tj . juc3=(A + B)/10 Hana Rudová, Omezující podmínky, 2. prosince 2019 14 Optimalizace & soft omezení: modely Fuzzy CSP 3 Fuzzy množiny: příslušnost prvku k množině zadána číslem z intervalu [0,1] & Fuzzy omezení: fuzzy relace ji/c(di,dk) e (0,1) udává úroveň preference DA = DB = {1,2,3} cl: A = 1 @(1,0.7) tj . pokud A=l, pak /jci=1 pokud A^l, pak /jci=0.7 c2: min( abs(A - B) ) , abs(A - B) = 0 => @1 tj . juC2=1 = 1 => @0.5 tj. juc2=0. 5 = 2 => @0.1 tj. jUC2=0.1 c3: max(A + B) @(A + B)/10 tj . juc3=(A + B)/10 * Fuzzy CSP (X,D,Cf) M Cf je množina fuzzy omezení X uspořádaná množina proměnných Hana Rudová, Omezující podmínky, 2. prosince 2019 14 Optimalizace & soft omezení: modely Kombinace a projekce omezení M Projekce n-tic (di,...,dt) \YX příklad: (1,2,3,4,5) i(dIaIe)0'^ = (4,1,5) Hana Rudová, Omezující podmínky, 2. prosince 2019 Optimalizace & soft omezení: modely Kombinace a projekce omezení Projekce n-tic (dlt...,di) iYx příklad: (1,2,3,4,5) l$%n'E)= (4,1,5) Kombinace c = Cx © Cy, dom(c) = Z = X u Y c,cx,cY omezení nad Z,X, Y lic(di,...,dk) = mm(^x((d1,...,dk) if ),jL/Cy((di,... ^ udává, jaká je úroveň splnění všech přiřazení Z vzhledem k cx a cy příklad (pokračování): kombinace cl e c2 e c3 pro (1, 3) /idec2ec3(l,3) = min(/ici((l)), /ic2((l, 3)),/ic3((l, 3))) =min(l,0.1,0.4) =0.1 Hana Rudová, Omezující podmínky, 2. prosince 2019 Optimalizace & soft omezení: modely Kombinace a projekce omezení Projekce n-tic (dl9...,di) iYx příklad: (1,2,3,4,5) l$;J[;Éf'E) = (4,1,5) 3 Kombinace c = cx © cY, dom(c) = Z = X u Y c,cx,cY omezení nad Z,X,Y jL/c(di,...,dfc) = mm(iiCx((di,...tdk) i f), £/Cy((di,... ,dk) lf)) 3 udává, jaká je úroveň splnění všech přiřazení Z vzhledem k cx a cy 3 příklad (pokračování): kombinace cl e c2 e c3 pro (1, 3) /iaec2ec3(l,3) = min(Aici((l)), /ic2((l, 3)), Aicaíd, 3))) = min(l, 0.1,0.4) =0.1 M Projekce C = Cy ^x, dom(c) = X,X c Y c,cx,cY omezení nad X,X, Y L*c(dxi,...,dXk) = max [\CY(dy\,...,dyi) ((dyi,...,dyi)eDyix---xDyi)A((dyi,...,dyi)ix=(dxi,...,dx]c)) 3 udává, jaká je úroveň splnění všech přiřazení X vzhledem k cy 3 příklad (pokračování): projekce c3 ^(b) na (1) JUc3u(b)(1) = max(jLic3(l, l),jUC3(2, 1),juC3(3, 1)) = max(0.2,0.3,0.4) = 0.4 Hana Rudová, Omezující podmínky, 2. prosince 2019 15 Optimalizace & soft omezení: modely Řešení fuzzy CSP Úroveň splnění přiřazení (di,..., dn) dána jako jL/0c(di, ■ ■ ■, dn) Hana Rudová, Omezující podmínky, 2. prosince 2019 16 Optimalizace & soft omezení: modely Řešení fuzzy CSP M Úroveň splnění přiřazení (di,..., dn) dána jako ji/0c(di,..., dn) 3 Řešení - přiřazení (di,..., dn) takové, že max v®c(di,...,dn) = C(P^) (di,...,dn)£DiX---xDn Hana Rudová, Omezující podmínky, 2. prosince 2019 16 Optimalizace & soft omezení: modely Řešení fuzzy CSP Úroveň splnění přiřazení (di,..., dn) dána jako jL/0c(di, ■ ■ ■, dn) 3 Řešení - přiřazení (d\,..., dn) takové, že max jU0C(^i,...,^n) = C(P^) příklad: © C = cl e c2 e c3 pro všechna (A, B) (3,3) ...0.6, (2,2)...0.4, (1,1)...0.2 (2,3) a (3,2) ...0.5, (2,1) a (1,2)...0.3 (1,3) a (3,1)...0.1 Hana Rudová, Omezující podmínky, 2. prosince 2019 16 Optimalizace & soft omezení: modely Řešení fuzzy CSP Úroveň splnění přiřazení (d\,..., dn) dána jako jL/0c(di, ■ ■ ■, dn) 3 Řešení - přiřazení (d\,..., dn) takové, že max jU0C(^i,...,^n) = C(P^) příklad: © C = cl e c2 e c3 pro všechna (A, B) (3,3) ...0.6, (2,2)...0.4, (1,1)...0.2 (2,3) a (3,2) ...0.5, (2,1) a (1,2)...0.3 (1,3) a (3,1)...0.1 => (3,3) je řešení, C(P„) = 0.6 Hana Rudová, Omezující podmínky, 2. prosince 2019 16 Optimalizace & soft omezení: modely Řešení fuzzy CSP Úroveň splnění přiřazení (d\,..., dn) dána jako jL/0c(di, ■ ■ ■, dn) 3 Řešení - přiřazení (d\,..., dn) takové, že max jU0C(^i,...,^n) = C(P^) příklad: © C = cl e c2 e c3 pro všechna (A, B) (3,3) ...0.6, (2,2)...0.4, (1,1)...0.2 (2,3) a (3,2) ...0.5, (2,1) a (1,2)...0.3 (1,3) a (3,1)...0.1 => (3,3) je řešení, C(P^) = 0.6 Úroveň nekonzistence 1 - C(P^ 3 C (Piu) je úroveň konzistence také jako projekce na prázdnou množinu proměnných ©C ^0 Hana Rudová, Omezující podmínky, 2. prosince 2019 16 Optimalizace & soft omezení: modely Příklad: řešení fuzzy CSP ■0 Viz dříve: © C = cl © c2 © c3 pro všechna (A, B) (3,3) ...0.6, (2,2)...0.4, (1,1)...0.2, (2,3) a (3,2) ...0.5, (2,1) a (1,2)...0.3, (1,3) a (3,1)...0.1 * ©C = ©C %,B} © C ^{a,b} (3, 3) = max(A/ec(3, 3)) = 0.6, © C "U- {a,b} (2,2) = 0.4,... Hana Rudová, Omezující podmínky, 2. prosince 2019 17 Optimalizace & soft omezení: modely Příklad: řešení fuzzy CSP ■0 Viz dříve: © C = cl © c2 © c3 pro všechna (A, B) (3,3) ...0.6, (2,2)...0.4, (1,1)...0.2, (2,3) a (3,2) ...0.5, (2,1) a (1,2)...0.3, (1,3) a (3,1)...0.1 * ©C = ©C %,B} © C ^{a,b} (3, 3) = max(A/ec(3, 3)) = 0.6, © C -U- {a,b} (2,2) = 0.4,... ■» ©C -U-{a} ©C^{A} (D =max(/i©c(l.l)./iec(1.2),/iec(1.3)) = max(0.2,0.3,0.1) =0.3 ©C^a} (2) =max(AJ©c(2,D,A/ec(2,2),AJec(2,3)) = max(0.3,0.4,0.5) =0.5 ©C^{A} (3) =max(AJ©c(3,D,A/ec(3,2),AJec(3,3)) = max(0.1,0.5,0.6) =0.6 Hana Rudová, Omezující podmínky, 2. prosince 2019 17 Optimalizace & soft omezení: modely Příklad: řešení fuzzy CSP M Viz dříve: © C = cl © c2 © c3 pro všechna (A, B) (3,3) ...0.6, (2,2)...0.4, (1,1)...0.2, (2,3) a (3,2) ...0.5, (2,1) a (1,2)...0.3, (1,3) a (3,1)...0.1 * ©C = ©C %,B} © C ^{a,b} (3, 3) = max(A/ec(3, 3)) = 0.6, ©C ^{a,b} (2,2) = 0.4,... ■» ©C ^{AÍ ©C^{A} (1) =max(/i©c(l.l)./iec(1.2),/iec(1.3)) = max(0.2,0.3,0.1) =0.3 ©C^{A} (2) =max(AJ©c(2,l),A/ec(2,2),AJec(2,3)) = max(0.3,0.4,0.5) =0.5 ©C^{A} (3) =max(AJ©c(3,D,A/ec(3,2),AJec(3,3)) = max(0.1,0.5,0.6) =0.6 ■» ©C U0 ©C U0 () =max(jU©c(l,D,A/©c(l,2),A'©c(l,3),jU©c(2,l),iU©c(2,2), jU©c(2,3),jU©c(3,l),A'©c(3,2),jU©c(3,3)) = 0.6 Hana Rudová, Omezující podmínky, 2. prosince 2019 17 Optimalizace & soft omezení: modely