TECHNICKÁ UNIVERZITA V KOŠICIACH FAKULTA ELEKTROTECHNIKY A INFORMATIKY. Katedra kybernetiky a umelej inteligencie. Interná výskumná správa

TECHNICKÁ UNIVERZITA V KOŠICIACH FAKULTA ELEKTROTECHNIKY A INFORMATIKY Katedra kybernetiky a umelej inteligencie

Interná výskumná správa

Milan Schmotzer

Košice, október 1998

Prehlásenie V správe použité názvy programových produktov, firiem apod. môžu byť ochrannými známkami alebo registrovanými ochrannými známkami príslušných vlastníkov. Prehlasujem na svoju česť, že som internú výskumnú správu vypracoval sám a všetku v nej použitú literutúru uvádzam. V Košiciach, 5.10.1998

__________________________________ Milan Schmotzer

Milan Schmotzer: PXLMX (interná výskumná správa)

Obsah PREDSLOV...................................................................................................................................................... 2 1

PROSTRIEDKY ECLIPSE NA RIEŠENIE ÚLOH ČASOVÉHO ROZVRHOVANIA................... 3 1.1 1.2

LOGICKÉ PROGRAMOVANIE OHRANIČENÍ ............................................................................................. 3 OPTIMALIZÁCIA ................................................................................................................................... 5

2

ZABUDOVANÝ MIN_MAX................................................................................................................. 6

3

LOGARITMICKÝ MIN_MAX ............................................................................................................ 7 3.1 3.2 3.3

4

UPOZORNENIE ...................................................................................................................................... 7 ZÁKLADNÝ PREDIKÁT .......................................................................................................................... 7 URÝCHLENIE ALGORITMU LOGARITMICKÝ MIN_MAX ........................................................................... 8

XLMX A PLMX ( VYLEPŠENIA ALGORITMU LOGARITMICKÝ MIN_MAX) ...................... 9 4.1

RÝCHLOSŤ ALGORITMU (X)LMX......................................................................................................... 9

5

PXLMX — VYLEPŠENIE ALGORITMU XLMX .......................................................................... 11

6

BENCHMARKOVÉ TESTY .............................................................................................................. 12

7

ZÁVER.................................................................................................................................................. 29

LITERATÚRA............................................................................................................................................... 30

strana 1


Predslov Predikčný logaritmický aproximačný min_max je algoritmus implementovaný do jadra (tela) rozvrhovacieho agenta systému ProPlanT (Schmotzer, 1998). Vznikol ako vylepšenie môjho algoritmu aproximačný logaritmický min_max navrhnutého v mojej diplomovej práci (Schmotzer, 1997).

strana 2


i

e

1 Prostriedky ECL PS na riešenie úloh časového rozvrhovania 1.1 Logické programovanie ohraničení Pod názvom logické programovanie ohraničení je potrebné rozumieť dva programátorské štýly: 1. Logické programovanie používa logiku Hornových klauzúl, pomocou ktorej programátor popíše problém, a dedukciu, pomocou ktorej úlohu systém rieši. Existuje viacero jazykov a systémov (programových balíkov) pracujúcich na princípe logického programovania. Jedným z najznámejších jazykov je Prolog. Prolog je deklaratívny jazyk (viď prílohu 5 mojej diplomovej práce (Schmotzer, i e 1997) — Popis systému ECL PS ). Na rozdiel od procedurálnych jazykov typu Fortran, Pascal či C programátorovi umožňuje sústrediť sa na problém čo naprogramovať, nie ako to urobiť. Prolog má však dva problémy:

2.

a)

Syntaktická inferencia, ktorej základom je unifikácia. Prolog nevie zistiť konzistentnosť v prípadoch, keď rozličná syntax vyjadruje tú istú skutočnosť. Týka sa to aj jednoduchých príkladov typu A = 1 + 2, pretože A je jednoduchá premenná, zatiaľ čo 1 + 2 je operátorový zápis interne reprezentovaný ako štruktúra +(1,2). Hoci by sme očakávali, že premenná A nadobudne hodnotu 3, unifikačný mechanizmus Prologu pri unifikácii priradí premennej A štruktúru +(1,2). Porovnanie A = 3 potom skončí neúspechom. O to, čo sa má v takýchto prípadoch premenným priradzovať či ako sa majú pri testoch a unifikácii interpretovať, sa preto často musí starať programátor.

b)

Samotná inferencia Prologovského systému je založená na prehľadávaní do hĺbky, s ktorým sú nevyhnutne spojené dva problémy: i)

Kombinatorická explózia (pretože bez zásahu programátora ide o algoritmus generuj a testuj).

ii)

Zacyklenie v prípade, že sa inferenčný mechanizmus „rozbehne“ po nekonečnej vetve stromu riešení alebo po kružnici v prípade stavového grafu.

Programovanie ohraničení dokáže čiastočne obísť práve Prologovský problém kombinatorickej explózie tým, že dokáže veľmi rýchlo odhaliť nekonzistentnosti podmienok, ktoré musí spĺňať riešenie úlohy. Je založené na riešení úloh spĺňania ohraničení (CSP - Constraint Satisfaction Problems). i

e

Ako príklad možno uviesť na Prologu založený systém ECL PS . Okrem klasickej Prologovskej inferencie umožňuje používať doplnkovú inferenciu riešiacu spĺňanie ohraničení. Typický program sa navrhuje takto:

strana 3

Milan Schmotzer: PXLMX (interná výskumná správa) 1. Zvolia sa premenné reprezentujúce problém a priradia sa im konečné domény.1 Princíp využívajúci konečné domény umožňuje meniť stratégiu generuj a testuj na stratégiu ohranič a generuj z domény. Konečná doména je jednoducho zoznam nejakých prvkov (napríklad celých čísel alebo nejakých atómov2), ktorého prvky smie premenná i e nadobúdať. Vo všeobecnosti sa počet prvkov zoznamu môže meniť, v ECL PS sa doména môže len zmenšovať. 2. Stanovia sa ohraničenia medzi premennými. Sú to podmienky, ktoré musia byť v riešení splnené. Stratégia generuj z domény a testuj sa mení na stratégiu stanov ohraničenia a len v prípade nejednoznačností generuj z domény. V niektorých prípadoch sa totiž už samotnými ohraničeniami natoľko orežú domény, že je hneď k dispozícii riešenie. Dôjde k tomu vtedy, ak sa domény premenných orezali natoľko, že obsahujú iba jediný prvok. Ak doména nejakej premennej obsahuje iba jediný prvok, inferenčný mechanizmus danú premennú na daný prvok okamžite naviaže.3 3. V prípade nejednoznačností (aspoň jedna konečná doména má viac ako jeden prvok) sa spustí algoritmus prehľadávania stavového priestoru možných riešení. Len čo je jasné, že nejaká premenná nemôže nadobúdať časť hodnôt zo svojej domény, doplnkový inferenčný mechanizmus riešiaci spĺňanie ohraničení nevhodné hodnoty z jej domény odstráni. Okrem toho algoritmus propagácie ohraničení pri každej takejto zmene ale aj pri pribudnutí nejakého ohraničenia na danú premennú otestuje konzistentnosť ostatných premenných vďaka ohraničeniam závislých na hodnote danej premennej. Výsledkom je rýchle odstraňovanie nekonzistentností a dynamické orezávanie priestoru možných riešení.4 Ak program nepoužíva nijaké disjunktívne ohraničenia, často stačí na hľadanie riešenia použiť predikát labeling/1 (jeho definíciu uvádzam na strane 51 v mojej diplomovej práci (Schmotzer, 1997)), ktorý premenným zo zoznamu (dostane ho ako svoj jediný argument) priradzuje prvky z ich domén. Po každom naviazaní premennej na prvok jej domény dôjde k orezaniu domén premenných závislých na hodnote, ktorú nadobúda daná premenná. Po naviazaní niekoľkých premenných sa vo väčšine prípadov natoľko orežú domény ostatných premenných, že obsahujú iba jediný prvok a unifikačný mechanizmus ich automaticky naviaže na tento prvok. Hľadanie riešenia sa takýmto orezávaním konečných domén premenných urýchľuje. Poradie, v akom sa naviazujú jednotlivé premenné, je kľúčové. Správnym poradím premenných je možné veľmi rýchlo orezať priestor prehľadávania. Programy využívajúce princíp CLP sú vďaka orezávaniu priestoru riešení pomerne efektívne. Samotná efektivita je založená práve na kvalite stanovených ohraničení. Programy písané v jazykoch využívajúcich princíp CLP (najmä v deklaratívnych) sú navyše aj ľahko modifikovateľné (rozširovateľné), pretože pri riešení nového typu

1

Termín konečné tu nemá časový význam. Doména je konečná, pretože má konečný počet prvkov. Pojmom atóm v Prologu označujeme textovú alebo číselnú konštantu. 3 To znamená, že voľná (neviazaná) premenná sa stane viazanou. Ak sú všetky premenné naviazané, je k dispozícii riešenie. 4 Úplné testy konzistentnosti pri každej zmene domény alebo novom ohraničení nie sú možné, pretože je s nimi spojená kombinatorická explózia. Preto sa uspokojujeme so slabším orezaním domén - nedetekujú sa všetky nekonzistentnosti. O výsledku môžeme predpokladať, že je správny, až keď sa premenné naviažu na konkrétne termy, pretože v prípade naviazania sú testy úplné. 2

strana 4

Milan Schmotzer: PXLMX (interná výskumná správa) problému často stačí len úprava alebo pridanie niekoľkých ohraničení bezo zmeny zvyšku programu. Výhodou CLP je aj fakt, že programátor nemusí poznať princípy, na základe ktorých samotné orezávanie domén, propagácia ohraničení a testy konzistencie v danom systéme fungujú. Samozrejme, ich znalosť nie je na škodu - ako príklad môže poslúžiť algoritmus logaritmický minimize, ktorý som naprogramoval tak, že sa vyhol trashingu, problému i e vyskytujúcemu sa u v systéme ECL PS zabudovaného predikátu minimize. 1.2 Optimalizácia Optimalizácia je tretím bodom z predošlého popisu typického programovania v systémoch umožňujúcich programovanie ohraničení. V prípade časových rozvrhovacích úloh existujú dva typy ohraničení: 1. Precedenčné ohraničenia (ktorá úloha danej práce má byť vykonaná pred ktorou) a iné dopredu známe technologické obmedzenia. 2. Disjunktívne ohraničenia vyjadrujúce zdieľanie zdrojov, z ktorých musí vždy platiť určitá skupina reprezentujúca riešenie. Na vyriešenie optimalizácie je potrebné odskúšať všetky takéto skupiny (skupiny sa prekrývajú) a vybrať tú, ktorá dáva z hľadiska optimalizačnej kriteriálnej funkcie najlepší výsledok. Práve disjunktívne ohraničenia spôsobujú kombinatorickú explóziu rozvrhovacích úloh. Samotná optimalizácia prebieha pomocou modifikovaného algoritmu Branch and Bound. i e V systéme ECL PS existujú dva zabudované predikáty využívajúce túto technológiu — min_max a minimize.5

5

V prípade, že nejaký výrok platí o obidvoch uvedených algoritmoch, budem sa na ne odvolávať ako na algoritmy typu min*. strana 5


2 Zabudovaný min_max Samotná optimalizácia prebieha pomocou modifikovaného algoritmu Branch and Bound. i e V systéme ECL PS existujú dva zabudované predikáty využívajúce túto technológiu — min_max a minimize. Pre účely nasledujúceho textu je pre nás zaujímavý predikát min_max. Predikát min_max dostáva ako argument cieľ, ktorý má byť optimalizovaný a premennú (resp. štruktúru obsahujúcu premenné), ktorej hodnota má byť optimalizáciou minimalizovaná. Ďalšími argumentami môžu byť hranice, v ktorých sa má hodnota danej premennej nachádzať. Predpokladá sa, že premenná (resp. všetky premenné zo zadanej štruktúry — napríklad zo zoznamu) je nejakým spôsobom prepojená s cieľom a vyjadruje jeho cenu — hodnotu priradenú danému cieľu ohodnocovacou funkciou. Pri optimalizácii sa predikát min_max snaží dokázať existenciu riešenia tak, že postupne odstraňuje najväčšie prvky z domény premennej označujúcej cenu a pokúsi sa splniť cieľ. Akonáhle cieľ už splniteľný nie je, je to dôkaz, že minimálna cena riešenia je cena predošlého splneného cieľa (ak taký existuje). Predikát min_max vráti splnený cieľ aj s jeho cenou.

strana 6


3 Logaritmický min_max 3.1 Upozornenie Upozorňujem cteného čitateľa, že benchmarky k logaritmickému min_maxu ako aj vysvetlivky skratiek už boli zverejnené v mojej diplomovej práci (Schmotzer, 1997). 3.2

Základný predikát i

e

V príručke logických rozšírení systému ECL PS sú predikáty min_max a minimize popísané len veľmi stručne. Pri hľadaní možností, ako zvýšiť rýchlosť programu, som sa preto musel pustiť do detailnej analýzy ich činnosti priamym sledovaním ich čiastkových výsledkov. Ak je spodná hranica ceny Min a horná hranica Max, predikáty min* prehľadávajú stavový priestor riešení tak, že hodnotu Max znižujú po jednom a tak musia v najhoršom prípade existenciu riešenia dokázať Max − Min + 1 krát za predpokladu, že cena riešenia je vyjadrená jedinou premennou Cena.6 Zrýchlenie prehľadávania umožňuje volanie predikátov min* s nenulovou hodnotou povolenej odchýlky ceny nájdeného riešenia od ceny optimálneho riešenia.7 To síce neumožní zvýšenie LB, dokážeme však aspoň rýchlejšie znižovať UB. Potom môžeme znížiť povolenú odchýlku, znovu volať min* s nižšou hodnotou povolenej odchýlky ceny atď. Predošlý postup má určitú nevýhodu (nezvyšuje LB), preto som navrhol predikát inteligentnejšie prehľadávajúci priestor možných riešení. Pri testoch na praktických úlohách sa ukázalo, že pri jeho použití sa rýchlosť v priemere zvyšuje niekoľkonásobne.8 So zvyšujúcou sa zložitosťou úloh je rozdiel oproti klasickým predikátom typu min* markantnejší. Algoritmus logaritmický min_max9:

 Max − Min  1. Hranica = Max − fix  .   2 2. Ak platí, že Hranica = Max , priraď Hranica = Max − 1 . 3. Dá sa dokázať existencia riešenia s cenou menšou ako Hranica ? Ak áno, priraď Max = CenaDôkazu 10, ak nie, priraď Min = Hranica + 1. 4. Priraď Odchýlka = 100 *

Max − Min . Min

6

Najhorší prípad nastane, ak cena nájdeného riešenia nikdy nie je menšia, než stanovená horná hranica a optimálne riešenie má cenu Min. 7 Zadáva sa v percentách. 8 Výsledky testov sú uvedené v kapitole 6 a v prílohe 4 mojej diplomovej práce (Schmotzer, 1997). 9 Predikát je potrebné, podobne ako klasický min*, volať s Min=LB a Max=UB. 10 Cena dôkazu môže byť len menšia alebo rovná ako Hranica. strana 7

Milan Schmotzer: PXLMX (interná výskumná správa) 5. Ak platí, že Max = Min alebo že Odchýlka <= PrípustnáOdchýlka, nájdi a vráť riešenie s cenou Max a skonči, inak choď na bod 1. Algoritmus označujem ako logaritmický min_max, pretože ak sa klasický min* pokúsi o dôkaz existencie riešenia v najhoršom prípade Max − Min + 1krát, predikátu logaritmický min_max stačí vzhľadom na neustále delenie intervalu na polovicu rádovo log 2( Max − Min) dôkazov. Ako sa dá očakávať, čím väčšia je hodnota UB − LB , tým markantnejší je rozdiel v počte potrebných dôkazov medzi klasickým a logaritmickým min_maxom. 3.3 Urýchlenie algoritmu logaritmický min_max Hornú hranicu nájdeme tak, že heuristickým spôsobom rýchlo vygenerujeme rozvrh úloh. Keďže predikát logaritmický min_max (odteraz LMX) voláme s cenou tohoto rozvrhu ako hornou hranicou (ako hodnotu Max), uvedomil som si, že sa môžeme vyhnúť časovo drahému opätovnému získaniu riešenia pri splnenej podmienke v bode 5 jednoducho tak, že si každé nájdené riešenie zapamätáme. Vzhľadom na charakter činnosti Prologu však musíme každé nájdené riešenie zabudnúť. Unifikačný systém Prologu by inak nedovolil hľadať lepšie riešenie. Tento problém môžeme obísť využitím schopnosti Prologu i e pracovať s databázou a riešenie uložiť do nej. Systém ECL PS ponúka možnosť využiť externé premenné, práca s ktorými je rýchlejšia. Preto riešenie radšej uchovávam v externej premennej. S uvedeným zvýšením rýchlosti predikátu sú spojené dve nepríjemnosti: 1. Predikát LMX používa na uchovanie cieľa, ktorý sa podarilo splniť, externú premennú. Pretože však program pri hľadaní hornej hranice ceny riešenia nájde riešenie s cenou UB, ktorú v podobe argumentu Max odovzdáva predikátu LMX, je vhodné nájdené riešenie uložiť do príslušnej externej premennej. Ak by totiž toto riešenie bolo optimálnym, predikát LMX by jeho existenciu už nemusel dokazovať a mohol by priamo vrátiť toto riešenie. Predikát LMX riešenie nedostáva vo forme argumentov, ale program mu musí riešenie s cenou menšou alebo rovnou ako Max explicitne uložiť do externej premennej alebo do databázy. Predikát preto nemožno vnárať, t.j. cieľ nesmie volať predikát LMX.

2. Pretože sa už na záver činnosti predikátu LMX riešenie nehľadá, nie je možné navracaním hľadať ďalšie riešenie, ak existuje viac riešení s optimálnou cenou.11 Problému spomínanému v prvom bode sa môžeme vyhnúť, ak predikát LMX upravíme tak, aby jedným z jeho argumentov bol unikátny názov externej premennej, do ktorej si bude ukladať medzivýsledky. S výhodou tak využijeme fakt, že počet obyčajných externých i e premenných (na rozdiel od referencií) nie je v systéme ECL PS obmedzený. Druhý bod je obzvlášť nepríjemný v situácii, keď chceme okrem hlavného optimalizačného kritéria splniť ešte nejaké vedľajšie kritérium. V takom prípade budeme musieť algoritmus modifikovať tak, aby pri pokuse o navracanie splnil cieľ ešte raz, avšak nájdené riešenie nesmie byť totožné s riešením uloženým v externej premennej. Ak je,

11

Túto schopnosť však nemajú ani predikáty min*, ktoré sú súčasťou systému ECLiPSe, strana 8

Milan Schmotzer: PXLMX (interná výskumná správa) jednoducho sa hľadá ďalšie riešenie - predikátom fail/0 sa vyvolá navracanie. Takáto úprava predikátu LMX je pomerne jednoduchá.

4 XLMX a PLMX ( vylepšenia algoritmu logaritmický min_max) Pri analýze hľadania riešenia som zistil, že v niektorých prípadoch sa stáva, že LMX pomerne rýchlo nájde riešenie a už iba v postupne sa zmenšujúcich intervaloch < Min, Max ) dokazuje neexistenciu horšieho riešenia. Preto som navrhol dve modifikácie predikátu LMX - adaptívny logaritmický min_max (PLMX) a aproximačný logaritmický min_max (XLMX). Ak algoritmus PLMX detekuje, že sa Max opakoval N-krát za sebou, t.j. že za sebou nastalo N neúspešných pokusov o dokázanie riešenia, interval nezníži na polovicu, ale  Max − Min  na štvrtinu, t.j. premennej Hranica priradí hodnotu Hranica = Max − fix .   4 V prípade, že Max je naozaj cenou optimálneho riešenia, PLMX zbytočne nehľadá riešenie  Max − Min  pre Hranica = Max − fix  . Keďže je pokusov o dôkaz riešenia pomerne   2 málo, zvýšenie rýchlosti vynechaním jedného môže byť oproti LMX signifikantné. Ak algoritmus XLMX zistí, že sa Max opakoval N-krát za sebou, t.j. že za sebou nastalo N neúspešných pokusov o dôkaz riešenia, priamo ho pokladá za optimálne riešenie a v ďalšej iterácii premennej Hranica priradí hodnotu Hranica = Max − 1 . V prípade, že Max je naozaj cenou optimálneho riešenia, XLMX už viac pokusov nevykoná. Aj tu sa dá očakávať určité zvýšenie rýchlosti v porovnaní s LMX. Otázkou je, ako stanoviť N. Ak ho nastavíme na hodnotu 2, zrejme bude v priemere vykonávať viac pokusov - celková činnosť algoritmu sa spomalí. Na druhej strane, príliš vysoká hodnota N nemusí priniesť očakávané zrýchlenie. Ako najrozumnejšie sa mi zdalo jednoducho odskúšať PLMX i XLMX pre N=2 až N=6. Využil som 30 konkrétnych náhodne vygenerovaných Job-Shopov, z toho desať pre problém 5x5 (rozvrhnutie piatich prác na päť strojov), desať pre problém 8x8 a desať pre problém 10x10.12 Našiel som optimálne N pre obidve modifikácie algoritmu LMX. Ukázalo sa, že PLMX nie je lepší ako klasický LMX. XLMX lepší bol a optimálne preň bolo N=3. Víťazom výkonnostných testov sa teda stal aproximačný logaritmický min_max. 4.1 Rýchlosť algoritmu (X)LMX Pri navrhovaní algoritmu LMX a jeho ďalších modifikácií som intuitívne predpokladal, že dôkaz existencie riešenia je časovo rovnako drahý pre akúkoľvek hornú hranicu. Bližším pozorovaním som zistil, že zatiaľ čo dôkaz existencie riešenia v oblastiach blízko UB ako aj blízko LB prebieha veľmi rýchlo, dôkaz existencie riešenia s cenou blízkou cene optimálneho riešenia je veľmi pomalý. Časovo najnáročnejší je pritom dôkaz neexistencie riešenia pre hornú hranicu ceny o 1 menšiu, než je cena optimálneho riešenia. Pokiaľ sa teda stane, že Hranica = Optimum − V , pričom V je malé prirodzené číslo väčšie ako 1, 12

Týchto 30 problémov mi slúžilo ako testovacie príklady pre všetky testy, ktoré som v diplomovej práci i v tejto práci vykonal. Výsledky najdôležitejších testov uvádzam v kapitole 6 ako aj v prílohe 4 mojej diplomovej práce (Schmotzer, 1997). strana 9

Milan Schmotzer: PXLMX (interná výskumná správa) program strávi veľa času dokazovaním neexistencie riešenia v tejto oblasti eliminačného stromu. Keď si uvedomíme, že nakoniec aj tak bude dokazovať neexistenciu riešenia pre Hranica = Optimum − 1 , dá sa očakávať, že sa LMX dosť spomalí. V skutočnosti k tomu pri testovaní došlo len v jedinom prípade (20 % spomalenie). V ostatných prípadoch bolo badateľné výrazné zrýchlenie hľadania optimálneho riešenia, ktoré bolo v porovnaní s klasickým predikátom min_max tým lepšie, čím zložitejší problém sa riešil. Pri riešení 5x5 Job-Shopu bol XLMX od klasického min_maxu v priemere 1,21 krát lepší, u 8x8 bol lepší už viac než 3,5 krát. Pri 10x10 Job-Shope dosiahol viac než 4.5 násobné zvýšenie rýchlosti.

strana 10


5 PXLMX — vylepšenie algoritmu XLMX Posledné vylepšenie algoritmu aproximatívneho logaritmického min_maxu (XLMX) som nazval predikčný aproximatívny logaritmický min_max (PXLMX). Vzniklo na základe nasledujúcej úvahy: Ak sledujeme výpis pri hľadaní riešenia pomocou algoritmu XLMX implementovaného v mojej diplomovej práci (Schmotzer, 1997), zistíme, že dôkaz existencie alebo neexistencie riešenia trvá v oblasti optimálneho riešenia omnoho dlhšie, než v oblastiach intervalu prehľadávania vzdialených od optimálneho riešenia. Znamená to, že v prípadoch, v ktorých dôkaz neexistencie riešenia pre spodnú hranicu trvá omnoho dlhšie ako hľadanie riešenia pre hornú hranicu môžeme predpokladať, že sa optimálne riešenie nachádza bližšie k spodnej hranici než k hornej. Interval by preto bolo vhodné nedeliť na polovicu, ale Limit priblížiť k spodnej hranici ešte viac. Obrátene to platí v prípadoch, v ktorých dôkaz neexistencie riešenia pre dolnú hranicu trval omnoho kratšiu dobu, než hľadanie riešenia pre hornú hranicu. V týchto prípadoch môžeme stanoviť Limit vyšší, než je polovica intervalu. Ako je možné vidieť z výkonnostných testov v ďalšej kapitole, ukázalo sa, že najlepšie je interval zúžiť na tretinu (posúvame samozrejme tú hranicu, pre ktorú výpočet trval kratšie) a to len vtedy, ak je rozdiel K časov výpočtu pre dolnú a hornú hranicu väčší ako 10. Matematicky môžeme algoritmus PXLMX vyjadriť ako: UB − LB   T ( H )〉 K * T (S ) ⇒ Limit = UB − (V − 1) V  a v opačnom prípade UB − LB   T ( S )〉 K * T (H ) ⇒ Limit = UB −  V kde T (S ) je doba výpočtu dôkazu pre spodnú hranicu intervalu T (H ) je doba výpočtu riešenia pre hornú hranicu intervalu V je počet delení intervalu (napr. 3 delenia — zúženie pôvodného intervalu na tretinu)

strana 11


6 Benchmarkové testy Do tejto novej verzie programu na riesenie problemu zvaneho job-shop som zahrnul vypis spotrebovaneho pouzivatelskeho a realneho casu. Zaverecny vypis casu je spravne sklonovany (1 minuta, 2 minuty apod.). Osetril som tiez chybu, ktora sa mohla vyskytnut pri poziadavke odchylky 100%, lebo to mohlo znamenat, ze sa hned vyhlasia vysledky, hoci sa explicitne nerataju. Toto v starom programe nebolo osetrene. V novom som zvysil rozmer externeho pola ciel, ciel(2) sa na zaciatku inicializuje na nulu (riesenie neexistuje) a ak sa najde aspon jedno riesenie, nastavi sa na 1. Nastavenie na 1 v pripade existencie riesenia treba urobit vsade tam, kde sa Ciel vola. V tejto novej verzii som OPRAVIL povodnu verziu XLMX. V povodne naprogramovanom algoritme bola chyba (oproti jeho zverejneniu), preto ak sa MAX opakovalo hned od zaciatku, bolo pocitane s N=3. Ak sa neopakovalo hned od prveho okamihu, pocitalo sa s N=2. Dovodom bola pociatocna inicializacia externeho pola na [0,0] namiesto na spravnych [Maximum,1]. Druhy prvok zoznamu pritom oznacuje, kolkokrat sa Maximum vyskytlo. Pri dalsom vyskyte rovnakeho maxima sa druhy prvok zoznamu povodne inkrementoval na 1 namiesto na spravnych 2. Test starej (chybne naprogramovanej) verzie aproximacneho min-maxu, v ktorej bolo N=3 ak sa upper bound opakoval hned od zaciatku, inac N=2. Nove casy ziskane pre staru verziu porovnavam s casmi ziskanymi pre novu opravenu verziu. Nemusim pritom za vitaza vybrat N s nizkym cislom. Logicky by malo byt vseobecne vyhovujuce vysoke N. Maximalne mozne N je pre povolenu domenu v ECLiPSe (-10.000.000 az 10.000.000) 12, preto za vyhovujuce N odhadujem bez vyhodnotenia testov 3 az 4. Pozrime si to v testoch. Hviezdickou oznacujem minimum, suma minim je za dany typ uloh, celkova suma je sucet minim za vsetky ulohy a celkova vazena suma je celkova suma so zohladnenim vacsej dolezitosti zvysenia rychlosti pri "velkych" ulohach.

strana 12

Milan Schmotzer: PXLMX (interná výskumná správa) Stary N=3/2

Novy program N=2 N=3

N=4

N=5

jsa_5_5_0 jsa_5_5_1 jsa_5_5_2 jsa_5_5_3 jsa_5_5_4 jsa_5_5_5 jsa_5_5_6 jsa_5_5_7 jsa_5_5_8 jsa_5_5_9

1.64 0.83* 1.57 1.31* 0.68 1.07* 1.48* 0.7 1.05 1.24*

1.76 1.01 2.02 1.68 0.69 1.28 1.64 0.71 1.15 1.54

1.55* 0.84 1.52* 1.32 0.66* 1.1 1.48* 0.66* 1.04* 1.26

1.78 0.9 1.84 1.36 0.7 1.2 1.62 0.71 1.15 1.35

1.78 0.89 1.86 1.34 0.7 1.21 1.6 0.72 1.15 1.36


10.41 9.35 73.01 8.07 9.63* 51.28 7.72 11.97 15.46 23.16

14.65 13.96 47.56* 12.1 11.98 43.35* 9.54 9.49* 16.9 34.08

10.18* 9.22* 72.03 8.02* 9.65 50.91 7.6 * 11.06 15.41* 22.73*

10.94 9.84 63.74 8.54 10.19 53.89 8.17 12.47 16.44 32.2

10.9 9.86 63.69 8.53 10.1 53.8 8.23 12.5 16.46 40.22

111.33 44.02 317.93 880.45 119.42 59.55 44.88 12166.8 122.78* 875.51

272.66 45.91 280.43* 801.3 * 130.72 46.84* 51.05 14118.2 136.09 1681.48

109.22* 42.04* 309.06 858.52 116.03* 58.95 44.2 * 12584.3 123.05 870.9 *

115.82 51.36 422.53 901.96 120.16 62.76 46.61 12077.9 * 128.72 915.31

116.02 60.44 422.55 902.46 120.35 62.68 46.72 12278.7 128.95 914.92

5 1 1

0 3 3

6 6 5

0 0 1

0 0 0

7 43

7 54

17 128

1 10

0 0


suma minim 5x5 suma minim 8x8 suma minim 10x10 celkova suma vazena suma

Moj odhad bol dobry, vitazom sa stava opravena N=3 (nie stara). V porovnani s neaproximacnym algoritmom min-max (najviac sa k nemu blizi algoritmus s najvyssim N), bola opravena N=3 rychlejsia vo viac nez 93% pripadov (28 z 30). V porovnani so starou verziou aproximacneho min-maxu bola nova verzia rychlejsia vo viac nez 73% pripadov (22 z 30). Porovnajme percentualne rychlosti vsetkych ktory nikdy nemal minimalny cas vypoctu.

algoritmov

voci

N=5,

strana 13

Milan Schmotzer: PXLMX (interná výskumná správa) Stary Novy program N=3/2 N=2

N=3

N=4

N=5


7.87 6.74* 15.59 2.24* 2.86 11.57* 7.5 * 2.78 8.7 8.82*

1.12 -13.48 -8.6 -25.37 1.43 -5.79 -2.5 1.39 0 -13.24

12.92* 5.62 18.28* 1.49 5.71* 9.09 7.5 * 8.33* 9.57* 7.35

0 -1.12 1.08 -1.49 0 0.83 -1.25 1.39 0 0.74

0 0 0 0 0 0 0 0 0 0


4.5 5.17 -14.63 5.39 4.65* 4.68 6.2 4.24 6.08 42.42

-34.4 -41.58 25.33* -41.85 -18.61 19.42* -15.92 24.08* -2.67 15.27

6.61* 6.49* -13.09 5.98* 4.46 5.37 7.65* 11.52 6.38* 43.49*

-0.37 0.2 -0.08 -0.12 -0.89 -0.17 0.73 0.24 0.12 19.94

0 0 0 0 0 0 0 0 0 0

4.04 27.17 24.76 2.44 0.77 4.99 3.94 0.91 4.78* 4.31

-135.01 24.04 33.63* 11.21* -8.62 25.27* -9.27 -14.98 -5.54 -83.78

5.86* 30.44* 26.86 4.87 3.59* 5.95 5.39* -2.49 4.58 4.81*

0.17 15.02 0 0.13 0.16 -0.13 0.24 1.64* 0.18 -0.04

0 0 0 0 0 0 0 0 0 0

-65.04 -70.93 -163.05

85.86 84.86 89.86

0.18 19.6 17.37

0 0 0

-299.02 -2523.14

260.58 2006.78

37.15 331.4

0 0


suma zisku 5x5 74.67 suma zisku 8x8 68.7 suma zisku 10x10 78.11 celkova suma vazena suma

221.48 1704.05

Z prvej tabulky je vidiet, ze novy N=3 dal na pokusnych prikladoch takmer 2.5 krat viac minim ako stary N=3 algoritmus aproximacneho min-maxu. Ako vidime v druhej tabulke, percentualne porovnanie ukazuje, ze novy (opraveny) N=3 aproximacny min-max bol v testoch oproti staremu v priemere rychlejsi len asi o 1.3 %. Napriek tomu ho odporucam pouzivat, ved preco nepouzivat najrychlejsi algoritmus? --------------------------------------------------------------------

strana 14

Milan Schmotzer: PXLMX (interná výskumná správa) Test pre implementaciu PXLMX - predikcneho aproximacneho logaritmickeho min_max-u. Toto je test pre K=2 a V=3..6. V=3

V=4

V=5

V=6


1.69* 0.97 1.68* 1.45* 0.71* 1.25 1.64 0.73* 1.17* 1.42

1.71 0.97 1.7 1.46 0.71* 1.25 1.62 0.74 1.18 1.39

1.7 0.93* 1.71 1.45* 0.73 1.23* 1.63 0.74 1.17* 1.37*

1.7 0.95 1.71 1.46 0.73 1.23* 1.61* 0.74 1.17* 1.4


11.99 9.25 67.85 10.07 13.83 59.78* 8.26 12.47* 16.57* 24.87

12.05 9.36 54.57* 9.9 11.91 65.98 8.29 12.49 16.6 24.53

10.77* 9.23 62.0 9.87* 14.18 60.24 8.23* 12.59 16.74 24.46*

10.83 9.2 * 61.33 10.46 11.85* 60.22 8.29 12.58 16.57* 24.66

97.19 45.53* 354.11* 1184.59 128.64 62.75* 46.88 8291.52 160.49 991.37

102.9 48.1 368.44 1140.88* 136.33 62.82 46.69* 11865.6 128.25 902.28

102.99 49.03 381.01 1433.27 153.86 62.89 46.94 8281.55* 128.19 1363.35

81.39* 49.64 381.05 1539.11 121.34* 62.87 46.83 12559.7 128.18* 871.1 *

suma minim 5 suma minim 8 suma minim 10

6 3 3

1 1 2

5 4 1

3 3 4

celkova suma vazena suma

12 84

4 33

10 67

10 79


strana 15

Milan Schmotzer: PXLMX (interná výskumná správa) Test pre K=2 a V=3..6 v percentach (v pomere ku K=2 a V=4). V=3 jsa_5_5_0 jsa_5_5_1 jsa_5_5_2 jsa_5_5_3 jsa_5_5_4 jsa_5_5_5 jsa_5_5_6 jsa_5_5_7 jsa_5_5_8 jsa_5_5_9

V=4

V=5

V=6

1.17 0 1.176 0.685 0 0 -1.235 1.351 0.847 -2.158

0 0 0 0 0 0 0 0 0 0

0.585 4.124 -0.588 0.685 -2.817 1.6 -0.617 0 0.847 1.439

0.585 2.062 -0.588 0 -2.817 1.6 0.617 0 0.847 -0.719


5.549 5.343 3.889 -3.831 5.641 0.111 -0.407 30.121 -25.138 -9.874

0 0 0 0 0 0 0 0 0 0

-0.087 -1.933 -3.412 -25.628 -12.859 -0.111 -0.535 30.205 0.047 -51.109

20.904 -3.202 -3.423 -34.906 10.995 -0.08 -0.3 -5.85 0.055 3.456

suma 5 suma 8 suma 10

1.836 -31.787 11.404

0 0 0

5.258 -12.297 -65.422

1.587 2.002 -12.351

-18.547 -131.076 -848.068

0 0 0

-72.461 -726.306 -7197.758

-8.762 -99.559 -1067.297

celkova suma vazena suma kvadrat suma

Pre K=2 sa vitazom stava V=4. Dalsie poradie je V=6,3,5. Dalsie kvadraticke poradie je V=3,6,5. ------------------------------------------------------------------

strana 16

Milan Schmotzer: PXLMX (interná výskumná správa) Toto je test pre K=3 a V=3..6. V=3

V=4

V=5

V=6


1.71 0.93* 1.75 1.42* 0.73 1.21* 1.63* 0.75 1.19 1.38*

1.72 0.95 1.68 1.42* 0.72* 1.22 1.64 0.76 1.16* 1.4

1.69* 0.96 1.67* 1.44 0.72* 1.25 1.64 0.76 1.2 1.38*

1.7 0.94 1.67* 1.43 0.73 1.23 1.64 0.74* 1.18 1.38*


10.94* 9.87 76.69 10.05 10.25 57.28* 8.21 12.53 16.56 24.5

11.08 9.85 76.68 9.81* 10.26 58.25 8.24 12.48* 16.56 24.49

10.97 9.84* 76.65 9.85 10.15* 60.1 8.24 12.54 16.53* 24.44*

10.94* 9.85 76.61* 9.85 10.17 60 8.2 * 12.57 16.53* 24.49

115.93 45.45* 354.09* 1183.98 128.63 62.86 46.76 8291.27 163.16 991.22

115.77* 47.95 368.64 1140.3 * 136.28 62.9 46.7 * 11855.2 163.06 902.71

115.99 49.28 381.27 1433.22 153.97 62.78 46.87 8247.63* 163.25 1362.9

115.98 49.7 381.37 1538.69 121.48* 62.77* 46.89 12556.6 163.02* 870.54*


5 2 2

3 2 3

4 4 1

3 4 4


9 61

8 61

9 62

11 87


strana 17

Milan Schmotzer: PXLMX (interná výskumná správa) Test pre K=3 a V=3..6 v percentach (v pomere ku K=3 a V=3). V=3

V=4

V=5

V=6


0 0 0 0 0 0 0 0 0 0

-0.585 -2.151 4 0 1.37 -0.826 -0.613 -1.333 2.521 -1.449

1.17 -3.226 4.571 -1.408 1.37 -3.306 -0.613 -1.333 -0.84 0

0.585 -1.075 4.571 -0.704 0 -1.653 -0.613 1.333 0.84 0


0 0 0 0 0 0 0 0 0 0

-1.28 0.203 0.013 2.388 -0.098 -1.693 -0.365 0.399 0 0.041

-0.274 0.304 0.052 1.99 0.976 -4.923 -0.365 -0.08 0.181 0.245

0 0.203 0.104 1.99 0.78 -4.749 0.122 -0.319 0.181 0.041


0 0 0 0 0 0 0 0 0 0

0.138 -5.501 -4.109 3.689 -5.947 -0.064 0.128 -42.984 0.061 8.929

-0.052 -8.427 -7.676 -21.051 -19.7 0.127 -0.235 0.526 -0.055 -37.497

-0.043 -9.351 -7.704 -29.959 5.559 0.143 -0.278 -51.444 0.086 12.175


0 0 0

0.934 -0.392 -45.66

-3.615 -1.894 -94.04

3.284 -1.647 -80.816

celkova suma vazena suma kvadrat suma

0 0 0

-45.118 -455.066 -4567.738

-99.549 -973.627 -9615.591

-79.179 -804.916 -8104.908

Pre K=3 sa vitazom stava V=3. Dalsie poradie V=4,6,5. -----------------------------------------------------------

strana 18


V=4

V=5

V=6


1.7 * 0.95 1.69 1.4 * 0.72* 1.22* 1.64 0.76 1.18* 1.4

1.7 * 0.95 1.7 1.43 0.72* 1.24 1.63* 0.75 1.19 1.38

1.71 0.92 1.68 1.45 0.72* 1.25 1.65 0.75 1.19 1.37*

1.71 0.9 * 1.67* 1.43 0.75 1.26 1.65 0.74* 1.19 1.37*


11.0 9.91 76.61 9.52* 10.22* 54.07 8.29 12.48* 16.51 24.49

11.0 9.85* 76.59* 9.81 10.41 53.99 8.26 12.49 16.49* 24.44*

10.95* 9.87 76.63 9.81 10.27 53.93* 8.25* 12.56 16.6 24.48


10.99 9.97 76.68 9.78 10.55 54.07 8.27 12.56 16.52 24.54

115.91 45.52* 353.78* 1183.42 131.11 62.66 46.66* 8087.69 129.21 994.72

115.83 48.04 368.31 1140.25* 142.39 62.75 46.69 11584.2 129.06* 893.48

115.86 49.11 381.15 1440.83 153.89 62.61* 46.77 8013.36* 129.22 1319.89

115.71* 49.61 381.26 1543.2 121.53* 62.78 46.83 12141.3 129.08 861.38*


5 3 3

3 0 2

2 4 2

4 3 3


11 79

5 35

8 62

10 74

strana 19


V=4

V=5

V=6


0 0 0.588 2.098 0 1.613 -0.613 -1.333 0.84 -1.449

0 0 0 0 0 0 0 0 0 0

-0.588 3.158 1.176 -1.399 0 -0.806 -1.227 0 0 0.725

-0.588 5.263 1.765 0 -4.167 -1.613 -1.227 1.333 0 0.725


-0.091 0.602 0.091 2.658 3.128 0 -0.242 0.637 0.061 0.204

0 0 0 0 0 0 0 0 0 0

-0.091 1.204 0.117 -0.307 1.327 0.148 0.121 0.557 0.182 0.407

0.364 1.003 0.065 -0.307 2.654 0.259 0.242 0 -0.484 0.244

-0.069 5.246 3.945 -3.786 7.922 0.143 0.064 30.183 -0.116 -11.331

0 0 0 0 0 0 0 0 0 0

-0.026 -2.227 -3.486 -26.361 -8.076 0.223 -0.171 30.825 -0.124 -47.425

0.104 -3.268 -3.516 -35.339 14.65 -0.048 -0.3 -4.809 -0.015 3.593

1.744 7.048 32.201

0 0 0

1.039 3.665 -56.848

1.491 4.04 -28.948

40.993 387.114 3714.772

0 0 0

-52.144 -533.965 -5424.265

-23.417 -249.705 -2598.965

jsa_10_10_0 jsa_10_10_1 jsa_10_10_2 jsa_10_10_3 jsa_10_10_4 jsa_10_10_5 jsa_10_10_6 jsa_10_10_7 jsa_10_10_8 jsa_10_10_9 suma minim 5 suma minim 8 suma minim 10 celkova suma vazena suma kvadrat suma

Pre K=4 sa vitazom stava V=3. Dalsie poradie je V=4,6,5. ---------------------------------------------------------

strana 20


V=4

V=5

V=6


1.69* 0.92* 1.69 1.45 0.73 1.22* 1.64 0.75* 1.16* 1.38

1.69* 0.95 1.66* 1.42 0.73 1.22* 1.64 0.76 1.17 1.37*

1.7 0.93 1.67 1.41* 0.72* 1.24 1.66 0.75* 1.17 1.38

1.72 0.93 1.67 1.43 0.72* 1.24 1.6 * 0.75* 1.18 1.38

jsa_8_8_0 jsa_8_8_1 jsa_8_8_2 jsa_8_8_3 jsa_8_8_4 jsa_8_8_5 jsa_8_8_6 jsa_8_8_7 jsa_8_8_8 Jsa_8_8_9

11.01 9.86* 76.61* 9.55* 10.2 53.98* 8.23 12.54 16.57 24.52

10.92* 9.88 76.62 9.83 10.29 54.07 8.23 12.54 16.52 24.46*

11.03 9.86* 76.61* 9.82 10.14* 54 8.18* 12.51* 16.49* 24.54

115.74* 45.51* 354.26* 1279.53 131.13 62.88 46.82 8291.45 129.15 1032.74

115.85 47.98 368.69 1140.7 * 142.42 62.82 46.84 11858.4 129.05* 911.76

115.88 49.23 381.18 1433.21 154.07 62.78 46.73 8248.62* 129.07 1362.82

115.79 49.68 381.19 1538.53 121.47* 62.77* 46.67* 12575.8 129.29 881.62*


5 4 3

4 2 2

3 6 1

3 0 4


12 87

8 56

10 73

7 55


10.99 9.87 76.66 9.87 10.21 54.07 8.23 12.53 16.59 24.49

strana 21


V=4

V=5


1.744 1.075 -1.198 -1.399 -1.389 1.613 -2.5 0 1.695 0

1.744 -2.151 0.599 0.699 -1.389 1.613 -2.5 -1.333 0.847 0.725

1.163 0 0 1.399 0 0 -3.75 0 0.847 0

0 0 0 0 0 0 0 0 0 0

jsa_8_8_0 jsa_8_8_1 jsa_8_8_2 jsa_8_8_3 jsa_8_8_4 jsa_8_8_5 jsa_8_8_6 jsa_8_8_7 jsa_8_8_8 Jsa_8_8_9

-0.182 0.101 0.065 3.242 0.098 0.166 0 -0.08 0.121 -0.122

0.637 -0.101 0.052 0.405 -0.784 0 0 -0.08 0.422 0.122

-0.364 0.101 0.065 0.507 0.686 0.129 0.608 0.16 0.603 -0.204

0 0 0 0 0 0 0 0 0 0

0.043 8.394 7.065 16.834 -7.953 -0.175 -0.321 34.068 0.108 -17.141

-0.052 3.422 3.279 25.858 -17.247 -0.08 -0.364 5.705 0.186 -3.419

-0.078 0.906 0.003 6.845 -26.838 -0.016 -0.129 34.409 0.17 -54.581

0 0 0 0 0 0 0 0 0 0

-0.359 3.409 40.922

-1.146 0.673 17.288

-0.341 2.291 -39.309

0 0 0

43.972 434.697 4301.401

16.815 172.534 1743.222

-37.359 -376.467 -3792.801

0 0 0


V=6

Pre K=5 sa vitazom stava V=3. Dalsie poradie je V=4,6,5. ---------------------------------------------------------

strana 22

Milan Schmotzer: PXLMX (interná výskumná správa) Toto je test pre K=6 a V=3..6 V=3

V=4

V=5

V=6


1.68* 0.93* 1.7 1.44 0.69* 1.22* 1.65 0.77 1.19 1.38

1.7 0.93* 1.69 1.42 0.75 1.22* 1.68 0.73* 1.16* 1.39

1.68* 0.95 1.68* 1.43 0.7 1.26 1.64* 0.74 1.19 1.39

1.71 1.01 1.68* 1.4 * 0.72 1.26 1.66 0.75 1.19 1.37*


11.04 9.93 77.2 8.62* 10.3 54.11 8.31 12.51* 16.61 24.73

10.97* 9.93 77.06 8.62* 10.33 54.12 8.35 12.54 16.56* 24.51*

10.99 9.9 * 76.94 8.66 10.25* 54.03* 8.2 * 12.57 16.57 24.9

11.08 9.92 76.93* 8.64 10.4 54.05 8.29 12.54 16.56* 25.52

116.32* 45.62* 355.63* 906.33 131.71 62.89* 46.82 8295.96 129.67 1033.89

116.46 48.09 371.37 903.14* 143.01 63.08 46.65* 11858.6 129.85 912.11

116.38 49.27 383.98 903.34 121.79 62.9 46.72 8277.24* 129.5 * 1364.21

116.99 49.85 384.02 903.4 121.48* 62.92 46.76 12503.7 129.6 881.77*


4 2 4

4 4 2

3 4 2

3 2 2


10 76

10 72

9 67

7 51


strana 23


V=4

V=5


1.754 7.921 -1.19 -2.857 4.167 3.175 0.602 -2.667 0 -0.73

0.585 7.921 -0.595 -1.429 -4.167 3.175 -1.205 2.667 2.521 -1.46

1.754 5.941 0 -2.143 2.778 0 1.205 1.333 0 -1.46

0 0 0 0 0 0 0 0 0 0


0.361 -0.101 -0.351 0.231 0.962 -0.111 -0.241 0.239 -0.302 3.096

0.993 -0.101 -0.169 0.231 0.673 -0.13 -0.724 0 0 3.958

0.812 0.202 -0.013 -0.231 1.442 0.037 1.086 -0.239 -0.06 2.429

0 0 0 0 0 0 0 0 0 0

0.573 8.485 7.393 -0.324 -8.421 0.048 -0.128 33.652 -0.054 -17.252

0.453 3.531 3.294 0.029 -17.723 -0.254 0.235 5.159 -0.193 -3.441

0.521 1.163 0.01 0.007 -0.255 0.032 0.086 33.802 0.077 -54.713

0 0 0 0 0 0 0 0 0 0

10.175 3.783 23.972

8.013 4.731 -8.91

9.408 5.465 -19.27

0 0 0

37.93 320.859 2893.687

3.834 -11.187 -387.891

-4.397 -101.94 -1342.02

0 0 0


V=6

Vitazom pre K=6 sa stava V=3. Dalsie poradie je V=6,4,5. -----------------------------------------------------------

strana 24

Milan Schmotzer: PXLMX (interná výskumná správa) Toto je test pre V=3 a K=2..6. NORMAL(V=2)

K=2,V=3

K=3,V=3

K=4,V=3

K=5,V=3

K=6,V=3

1.71 0.94 1.69* 1.42 0.72 1.24 1.63 0.73* 1.18 1.37*

1.71 0.97 1.7 1.46 0.71 1.25 1.62* 0.74 1.18 1.39

1.71 0.93 1.75 1.42 0.73 1.21* 1.63 0.75 1.19 1.38

1.7 0.95 1.69* 1.4 * 0.72 1.22 1.64 0.76 1.18 1.4

1.69 0.92* 1.69* 1.45 0.73 1.22 1.64 0.75 1.16* 1.38

1.68* 0.93 1.7 1.44 0.69* 1.22 1.65 0.77 1.19 1.38

10.93* 9.87 76.52 8.56* 10.2 * 54.01 8.25 12.5 16.46* 24.5

12.05 9.36* 54.57* 9.9 11.91 65.98 8.29 12.49 16.6 24.53

10.94 9.87 76.69 10.05 10.25 57.28 8.21* 12.53 16.56 24.5

11.0 9.91 76.61 9.52 10.22 54.07 8.29 12.48* 16.51 24.49*

11.01 9.86 76.61 9.55 10.2 * 53.98* 8.23 12.54 16.57 24.52

116.06 45.4 * 331.18* 902.6 * 124.35* 62.89 46.64* 12610.6 129.3 916.32

102.9 * 48.1 368.44 1140.88 136.33 62.82 46.69 11865.6 128.25* 902.28*

115.93 45.45 354.09 1183.98 128.63 62.86 46.76 8291.27* 163.16 991.22

115.91 45.52 353.78 1183.42 131.11 62.66* 46.66 8087.69 129.21 994.72

115.74 45.51 354.26 1279.53 131.13 62.88 46.82 8291.45 129.15 1032.74

116.32 45.62 355.63 906.33 131.71 62.89 46.82 8295.96 129.67 1033.89

3 4 5

1 2 3

1 1 1

2 2 1

3 2 0

2 0 0

12 97 831

6 51 453

3 23 189

5 36 278

5 31 203

2 10 50

11.04 9.93 77.2 8.62 10.3 54.11 8.31 12.51 16.61 24.73

strana 25

Milan Schmotzer: PXLMX (interná výskumná správa) Test pre V=3 a K=2..6 v percentach (v pomere ku K=6). NORMAL(V=2)

K=2,V=3

K=3,V=3

K=4,V=3

K=5,V=3

K=6,V=3

-1.786 -1.075 0.588 1.389 -4.348 -1.639 1.212 5.195 0.84 0.725

-1.786 -4.301 0 -1.389 -2.889 -2.459 1.818 3.896 0.84 -0.725

-1.786 0 -2.941 1.389 -5.797 0.82 1.212 2.597 0 0

-1.19 -2.151 0.588 2.778 -4.348 0 0.606 1.299 0.84 -1.449

-0.595 1.075 0.588 -0.694 -5.797 0 0.606 2.597 2.521 0

0 0 0 0 0 0 0 0 0 0

0.996 0.604 0.881 0.696 0.971 0.185 0.722 0.08 0.903 0.93

-9.149 5.74 29.313 -14.849 -15.631 -21.937 0.241 0.16 0.06 0.809

0.906 0.604 0.661 -16.589 0.485 -5.858 1.203 -0.16 0.301 0.93

0.362 0.201 0.764 -10.441 0.777 0.074 0.241 0.24 0.602 0.97

0.272 0.705 0.764 -10.789 0.971 0.24 0.963 -0.24 0.241 0.849

0 0 0 0 0 0 0 0 0 0

0.224 0.482 6.875 0.412 5.588 0 0.384 -52.009 0.285 11.372

11.537 -5.436 -3.602 -25.879 -3.508 0.111 0.278 -43.029 1.095 12.73

0.335 0.373 0.433 -30.635 2.338 0.048 0.128 0.057 -25.827 4.127

0.352 0.219 0.52 -30.573 0.456 0.366 0.342 2.51 0.355 3.789

0.499 0.241 0.385 -41.177 0.44 0.016 0 0.054 0.401 0.111

0 0 0 0 0 0 0 0 0 0

SUMA: 1.101 6.968 -26.387

-6.995 -25.243 -55.703

-4.506 -17.517 -48.623

-3.027 -6.21 -21.664

0.301 -6.024 -39.03

0 0 0

-18.318 -202.621 -2165.223

-87.941 -793.949 -7360.727

-70.646 -648.896 -6096.038

-30.901 -281.455 -2639.515

-44.753 -436.987 -4281.011

0 0 0

Ako najrychlejsi sa ukazal algoritmus PREDIKCNY APROXIMACNY LOGARITMICKY MIN_MAX pre K=6 a V=3. Hned potom nasleduje V=2; K=4,5,3,2. Z toho vyplyva odporucanie dalej otestovat V=3, K=7..12. ---------------------------------------------------------

strana 26

Milan Schmotzer: PXLMX (interná výskumná správa) Toto je test pre V=3 a K=6..10. NORMAL(V=2) 1.71 0.94 1.69 1.42* 0.72 1.24 1.63* 0.73* 1.18 1.37 10.93 9.87 76.52* 8.56* 10.2 54.01 8.25 12.5 16.46* 24.5

K=6,V=3

K=7,V=3

K=8,V=3

K=9,V=3

1.68* 0.93* 1.7 1.44 0.69* 1.22 1.65 0.77 1.19 1.38

1.7 0.94 1.68 1.42* 0.71 1.22 1.65 0.74 1.17 1.36*

1.69 0.94 1.66* 1.44 0.73 1.22 1.65 0.76 1.19 1.39

1.69 0.95 1.69 1.42* 0.72 1.23 1.66 0.76 1.19 1.39

1.69 0.93* 1.66* 1.45 0.72 1.21* 1.65 0.74 1.16* 1.4

11.2 9.81* 76.57 8.66 10.19* 53.96* 8.23 12.66 16.49 24.51

10.88* 9.86 76.57 8.57 10.2 53.96* 8.25 12.48* 16.52 24.44*

11.04 9.93 77.2 8.62 10.3 54.11 8.31 12.51 16.61 24.73

10.99 9.88 77.4 8.6 10.18 54.05 8.21* 12.55 16.52 25.05

11.02 10.18 76.89 8.79 10.33 54.14 8.23 12.6 16.8 24.67

K=10,V=3

116.06 45.4 * 331.18* 902.6 124.35 62.89* 46.64* 12610.6 129.3 916.32*

116.32 45.62 355.63 906.33 131.71 62.89* 46.82 8295.96 129.67 1033.89

115.72* 45.4 * 353.18 901.08* 131.22 63.16 46.79 8277.14* 129.48 1031.63

116.43 46.05 356.9 906.9 113.67 63.53 47.4 8277.4 130.31 1035.26

116.1 45.62 356.47 903.81 113.12 62.94 46.89 8306.37 129.61 1033.32

115.93 45.47 353.93 902.28 112.79* 62.9 46.75 8307.69 129.04* 1033.03

3 3 5

3 0 1

2 1 4

1 0 0

1 3 0

4 4 2

11 89 767

4 25 175

7 58 514

1 5 25

4 29 217

10 72 556

strana 27

Milan Schmotzer: PXLMX (interná výskumná správa) Test pre V=3 a K=6..10 v percentach (v pomere ku K=8). NORMAL(V=2)

K=6,V=3

K=7,V=3

-1.183 0 -1.807 1.389 1.37 -1.639 1.212 3.947 0.84 1.439

0.592 1.064 -2.41 0 5.479 0 0 -1.316 0 0.719

-0.592 0 -1.205 1.389 2.74 0 0 2.632 1.681 2.158

0.817 3.045 0.481 2.617 1.258 0.24 -0.243 0.794 2.024 0.689

-0.181 2.456 -0.403 1.934 0.29 0.055 -0.972 0.714 1.131 -0.243

0.318 1.412 7.207 0.474 -9.396 1.007 1.603 -52.35 0.775 11.489 5.568 11.722 -37.461 -20.171 -252.994 -2856.692

K=9,V=3

K=10,V=3

0 0 0 0 0 0 0 0 0 0

0 -1.064 -1.807 1.389 1.37 -0.82 -0.606 0 0 0

0 1.064 0 -0.694 1.37 0.82 0 2.632 2.521 -0.719

0.272 2.947 -0.663 2.162 1.452 0.166 0.243 0.397 1.667 -1.54

0 0 0 0 0 0 0 0 0 0

-1.633 3.635 0.416 1.479 1.335 0.332 0 -0.476 1.845 0.649

1.27 3.143 0.416 2.503 1.258 0.332 -0.243 0.952 1.667 0.932

0.094 0.934 0.356 0.063 -15.871 1.007 1.224 -0.224 0.491 0.132

0.61 1.412 1.042 0.642 -15.439 0.582 1.287 0.003 0.637 0.351

0 0 0 0 0 0 0 0 0 0

0.283 0.934 0.12 0.341 0.484 0.929 1.076 -0.35 0.537 0.187

0.429 1.26 0.832 0.509 0.774 0.992 1.371 -0.366 0.975 0.215

4.128 4.781 -11.794

8.803 7.103 -8.873

0 0 0

-1.538 7.582 4.541

6.994 12.23 6.991

7.033 12.109 -212.633

0 0 0

10.585 98.376 900.898

26.215 202.72 1656.67

-2.885 -59.052 -770.216

K=8,V=3

strana 28


7 Záver Ako najrýchlejší z testovaných algoritmov sa ukázal algoritmus PREDIKČNÝ APROXIMAČNÝ LOGARITMICKÝ MIN_MAX pre K=10 a V=3. Riešenie najťažšej úlohy (js_10_10_7) prebehne pri K=10 a V=3 o 72 minút skôr, t.j. výpočet je rýchlejší o 34%.

strana 29


Literatúra Schmotzer M.: Analýza a návrh nových prostriedkov pre riešenie úloh časového rozvrhovania v prostredí logického programovania ohraničení. Diplomová práca, Katedra kybernetiky a umelej inteligencie, Fakulta elektrotechniky a informatiky, Technická univerzita v Košiciach, Apríl 1997 Schmotzer M.: ProPlanT. Interná výskumná správa, Katedra kybernetiky a umelej inteligencie, Fakulta elektrotechniky a informatiky, Technická univerzita v Košiciach, September 1998

strana 30

TECHNICKÁ UNIVERZITA V KOŠICIACH FAKULTA ELEKTROTECHNIKY A INFORMATIKY. Katedra kybernetiky a umelej inteligencie. Interná výskumná správa

Recommend Documents