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 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) I 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í 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ů nalezení řešení je nejobtížnější za předpokladu, že cca 50% problémů je splnitelnýchl 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} M domény D = {Di,... ,Dn} M omezení C = {Ci,..., Cn} i* Q je definováno na Y* ^ X, Yi = {x^,... ,Xík} ±> Q je podmnožina x ... x Diki 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í Ch = {Ci,..., Cn} 3 Q je definováno na Y* ^X,Yi= {xh,... ,xik} 3 d je podmnožina x ... x Difc 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ř + Optimalizační problém s podmínkami (COP): (X,D,Ch,Cs)i Objektivní funkce relace funkce I zjednodušení na X F(d) = X^Qj]) d[Qj]... projekce d na Qjl Řešení COP: d° splňující všechna omezení z Ch tak, že = maxjF(d) nebo = min^FW) 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 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 @ 4l Problémy s nejistotou Je 0.7 nezbytné, abych přišla do středy. po..st 0.7, ct..ne 0 M 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 Ol Š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í 3 zobecňující: omezení nad polookruhy (semiring-based)i 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í 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)/10l * 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í Projekce n-tic (di,...,^) \YX příklad: (1,2,3,4,5) Í(dae)d'e)= (4-5) 3 Kombinace c = cx © cY, dom(c) = Z = X u Y c,cx,cY omezení nad Z,X,Y jL/c(di,...,dfc) = min(jucx((di,...,í4) if ),ji/Cy((di, ■ ■ ■ ,dk) ^ 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) Jiciec2ec3(l,3) = min(Aici((l)), /ic2((l, 3)), jic3((1, 3))) =min(l,0.1,0.4) = O.ll 1 M Projekce C = Cy ^x, dom(c) = X,X c y omezení nad y lAc(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(/ic3(l, l),/ic3(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í (d\,..., dn) dána jako jL/0c(di, ■ ■ ■, dn)t 3 Řešení - přiřazení (d\,..., dn) takové, že max jU0C(^i,...,^n) = C(P^)I 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.11 => (3,3) je řešení, C(P^) = 0.61 Úroveň nekonzistence 1 - CCF^) 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 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, 0CU{A,u}(2,2) = O.4,...l ■» ©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,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.61 ■» ©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