Knihovna pro spojitou optimalizaci - FAKE GAME...

České vysoké učení technické v PrazeFakulta elektrotechnická

Katedra počítačů

Diplomová práce

Knihovna pro spojitou optimalizaci

Bc. Martin Hvizdoš

Vedoucí práce: Ing. Pavel Kordík, Ph.D.

Studijní program: Elektrotechnika a informatika, strukturovaný, Navazující mgisterský

Obor: Výpočetní technika

květen 2009

ii

Poděkování

Týmto sa chcem poďakovať Pavlovi Kordíkovi a Janovi Drchalovi za ich podporu a trpezlivosť. Ďakujem vám za príležitosť rozbehnúť JCool od základov a za voľnú ruku pri výbere technológií. A taktiež za vašu ochotu sa tieto technológie naučiť.

iii

iv

Prohlášení

Prohlašuji, že jsem práci vypracoval samostatně a použil jsem pouze podklady uvedené v přiloženém seznamu.

Nemám závažný důvod proti užití tohoto školního díla ve smyslu §60 Zákona č. 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonů (autorský zákon).

V Praze dne 21.5.2009 ............................................................................................

v

vi

Abstract

Optimization problems are ubiquitous. From data analysis and financial planning to modeling of chemical processes or design. There are many ways to their solution which range from purely numerical, hybrid to those inspired by nature. The diversity and complexity of the individual approaches and implementations is causing problems in understanding them. This thesis focuses on creations of instruments for optimization method testing and inspection. One of its main goals is simplicity. Simplicity not only for the end user but also for the optimization problem and method implementation creator. And thus seeks to attract both.

Abstrakt

Optimalizačné problémy sú všadeprítomné od analýzy dát a finančného plánovania až po modelovanie chemických procesov či dizajn. Existuje mnoho spôsobov ako ich riešiť, ktorých prístupy siahajú do metód numerických cez hybridné až k prírodou inšpirovanými. Rôznorodosť a často aj zložitosť jednotlivých prístupov a implementácií vytvára problémy do nich preniknúť. Táto práca sa zaoberá vytváraním nástrojov na pozorovanie vnútorného chovania a porovnávanie optimalizačných metód. Jedným z jej hlavných cieľov je jednoduchosť. Jednoduchosť nie len pre koncového užívateľa, ale aj pre tvorcu (programátora) optimalizačných problémov či metód. A tým sa snažiť prilákať oboch.

vii

viii

Table of contents1.Úvod.........................................................................................................................................12.Popis problematiky.................................................................................................................. 3

2.1.Optimalizačný problém.................................................................................................... 32.2.Optimalizačné metódy......................................................................................................32.3.Optimalizačné metódy implementované v GAME.......................................................... 42.4.Ukončovacie podmienky..................................................................................................5

3.State of the art.......................................................................................................................... 74.Analýza...................................................................................................................................11

4.1.Motivácia........................................................................................................................114.2.Prípady použitia..............................................................................................................11

4.2.1.Scenár: Testovanie novej optimalizačnej metódy...................................................124.2.2.Scenár: Skúmanie vnútorného chovania optimalizačnej metódy...........................124.2.3.Scenár: Pozorovanie výkonnosti optimalizačných metód...................................... 124.2.4.Scenár: Optimalizácia v zákazníckom prostredí.....................................................13

4.3.Funkčné požiadavky.......................................................................................................134.4.Dodatočné požiadavky................................................................................................... 14

5.Riešenie..................................................................................................................................155.1.Platforma JCool..............................................................................................................155.2.Framework JCool........................................................................................................... 185.3.Architektúra....................................................................................................................205.4.Správa projektov.............................................................................................................21

5.4.1.Maven..................................................................................................................... 215.4.2.Subversion.............................................................................................................. 225.4.3.SourceForge............................................................................................................22

5.5.Dizajn a implementácia.................................................................................................. 235.5.1.Core........................................................................................................................ 255.5.2.Solver......................................................................................................................305.5.3.Experiment..............................................................................................................355.5.4.Benchmark..............................................................................................................405.5.5.UI............................................................................................................................ 42

5.6.Distribúcia...................................................................................................................... 486.Zhodnotenie riešenia.............................................................................................................. 49

6.1.Príklad experimentu....................................................................................................... 496.2.Diskusia o frameworku.................................................................................................. 56

7.Záver...................................................................................................................................... 578.Budúcnosť projektu................................................................................................................599.Referencie.............................................................................................................................. 61Dodatok A – Ilustrácie vo farbe................................................................................................ 63Dodatok B – obsah priloženého CD......................................................................................... 73

ix

x

Zoznam ilustráciíJCool - Prípady použitia............................................................................................................11Platforma JCool ........................................................................................................................15Platforma JCool - headless mód................................................................................................16Platforma JCool - popis užívateľského rozhrania..................................................................... 16Platforma JCool - priblíženie telemetrie................................................................................... 17Platforma JCool - ukážka vizualizácie......................................................................................18JCool - architektúra...................................................................................................................20JCool - projektová štruktúra......................................................................................................23JCool - projektová štruktúra (detail)......................................................................................... 24Hlavné koncepty v projekte core.............................................................................................. 25Základný koncept - Funkcia......................................................................................................26Základný koncept - Komunikácia s funkciou........................................................................... 26Základný koncept - Optimalizačná metóda, Ukončovacia podmienka.....................................27Základný koncept - Telemetria..................................................................................................29Hlavné koncepty v projekte solver............................................................................................30Základný koncept - Solver........................................................................................................ 30BasicSolver - proces riešenia.................................................................................................... 31Základný koncept - výsledok optimalizácie..............................................................................32BaseObjectiveFunction............................................................................................................. 32Použitie návrhových vzorov dekorátor a stratégia v BaseObjectiveFunction..........................33Základný koncept - Štatistiky................................................................................................... 34Vytváranie a zber štatistík......................................................................................................... 34Hlavné koncepty v projekte experiment................................................................................... 35Producent - Konzument............................................................................................................ 36Príklady druhov komunikácie................................................................................................... 36Základný koncept - Vizualizácia...............................................................................................37BasicExperimentRunner - ekosystém....................................................................................... 38Stavy experimentu.....................................................................................................................40Boothova funkcia...................................................................................................................... 41Rosenbrockova funkcia.............................................................................................................41Funkcia Levy číslo 3................................................................................................................. 41Funkcia Levy číslo 5................................................................................................................. 42SADEMethod - konfiguračný panel (generovaný)................................................................... 43Využitie BeanConfigurations v platforme JCool...................................................................... 44Vizualizácia - aktuálna hodnota................................................................................................ 45Vizualizácia - jediný bod...........................................................................................................46Vizualizácia - viacero bodov.....................................................................................................47Vizualizácia - základná telemetria............................................................................................ 47Experiment - minimum............................................................................................................. 50Experiment - počet iterácií........................................................................................................50SD-1: uviaznutie v lokálnom minime....................................................................................... 51SD-1: uviaznutie v lokálnom minime (detail)...........................................................................51CG-1: uviaznutie v lokálnom minime.......................................................................................52CG-2: reštartovanie................................................................................................................... 52CG-2: prvý reštart..................................................................................................................... 52CG-2: druhý reštart................................................................................................................... 53CG-2: vypršanie cyklov............................................................................................................ 53SADE-1: priebeh.......................................................................................................................54SADE-2: priebeh.......................................................................................................................55

xi

Platforma JCool (farebne)......................................................................................................... 63Platforma JCool - popis užívateľského rozhrania (farebne)..................................................... 63Platforma JCool - priblíženie telemetrie (farebne)....................................................................64Platforma JCool - ukážka vizualizácie (farebne)...................................................................... 64Využitie BeanConfigurations v platforme JCool (farebne).......................................................65Vizualizácia - jediný bod (farebne)........................................................................................... 65Vizualizácia - viacero bodov (farebne)..................................................................................... 66Experiment – minimum (farebne).............................................................................................66Experiment - počet iterácií (farebne)........................................................................................ 66SD-1: uviaznutie v lokálnom minime (farebne)....................................................................... 67SD-1: uviaznutie v lokálnom minime (detail) (farebne)........................................................... 67CG-1: uviaznutie v lokálnom minime (farebne)....................................................................... 68CG-2: reštartovanie (farebne)................................................................................................... 68CG-2: prvý reštart (farebne)......................................................................................................69CG-2: druhý reštart (farebne)....................................................................................................69CG-2: vypršanie cyklov (farebne).............................................................................................70SADE-1: priebeh (farebne)....................................................................................................... 71SADE-2: priebeh (farebne)....................................................................................................... 72

xii

xiii

1.Úvod

1. Úvod

Identifikácia, klasifikácia a predikcia sú neoddeliteľnou súčasťou práce odborníkov v mnohých oboroch. Týmito netriviálnymi procesmi sa snažia pochopiť dáta a súvislosti v nich, ktoré získavajú z rôznych pokusov, meraní či štatistík. Stálym vývojom senzorov a počítačov sa však obnos zozbieraných dát dramaticky zvyšuje. FAKE GAME (Fully Automated Knowledge Extraction using Group of Adaptive Models Evolution)[23] je projektom prostredia slúžiaceho na automatické vyťažovanie znalostí z dát vyvíjaný na katedre počítačov.

FAKE GAME obsahuje metódy na automatické predspracovanie dát, adaptívny data mining1 a vyťažovanie znalostí, ktorými sa snaží asistovať doménovým expertom pri extrakcii užitočných znalostí z reálnych dát bez asistencie štatistikov. GAME generuje skupinu induktívnych modelov adaptujúcich sa charakteru a komplexnosti vstupných dát. Induktívny model (sieť) rastie, až do veľkosti potrebnej na vyriešenie daného problému dostatočnou presnosťou. Skladá sa z jednotiek (neurónov), ktoré boli najúspešnejšie pri modelovaní vzťahov vrámci dát. GAME pri evolúcii týchto modelov používa optimalizačné metódy na nastavovanie váh a koeficientov jednotiek siete. Zistilo sa, že neexistuje optimalizačná metóda vhodná na všetky typy dát (v súlade s teorémom No Free Lunch[22], ktorý spochybňuje existenciu univerzálneho optimalizačného algoritmu), preto sa v aplikácii FAKE GAME, pri evolúcii neurónových sietí, používa viac ako 20 optimalizačných metód rôzneho charakteru. Výber použitej metódy závisí na dátach.

Používaním FAKE GAME sa ukázalo, že najlepšie výsledky vykazovali neurónové siete, ktorých evolúcia využívala mnoho rôznorodých optimalizačných algoritmov. Taktiež sa ukázala potreba inšpekčného nástroja, ktorý by pomáhal odhaľovať ich vnútorné chovanie. Používanie rôznorodých optimalizačných algoritmov by mohlo prospieť aj riešeniu všeobecných optimalizačných problémov.

Táto práca sa zaoberá definíciou a technickým prevedením systému na pozorovanie a introspekciu optimalizačných algoritmov. V nasledujúcich kapitolách si rozoberieme typy užívateľov, pre ktorých je táto aplikácia určená, prípady jej použitia zvolenú architektúru a dizajn a zaujímavé časti jej implementácie.

1 Data mining – proces extrakcie skrytých vzorov z dát.

1

2

2.Popis problematiky

2. Popis problematiky

2.1. Optimalizačný problémV matematike a počítačových vedách sa optimalizačným problémom[01] myslí nájdenie najlepšieho riešenia z množiny všetkých možných riešení určitého problému a môže byť reprezentovaný následovne:

Zadané: funkciu f : Aℝ z nejakej množiny A do množiny reálnych čísel

Hľadáme: element, také x0∈A , pre ktoré platí f x0≤ f x (v prípadne minimalizácie) alebo f x0≥ f x (v prípade maximalizácie) pre všetky

x∈A

Typicky sú prvky množiny A podmnožinou Euklidovského priestoru ℝn často špecifikované množinou obmedzení, rovností alebo nerovností, ktoré musia prvky množiny

A spĺňať. Doména funkcie f je nazývaná prehľadávaným priestorom a prvky množinyA sú nazývané možnými riešeniami.

Funkcia f je nazývaná objektívnou funkciou, cenovou funkciou alebo energetickou funkciou. Optimálnym riešením sa nazýva každé možné riešenie, ktoré minimalizuje (alebo maximalizuje) hodnotu tejto funkcie.

Všeobecne, ak objektívna funkcia určitého problému nevykazuje konvexnosť, existuje niekoľko lokálnych minim (alebo maxím).

Lokálne minimum x* je definované ako bod, pre ktorý existuje nejaké 0 také, že pre všetky

∥x−x*∥≤

platí

f x*≤ f x

To znamená, že v určitom okolí bodu x* funkcie f sú hodnoty všetkých okolitých bodov vačšie alebo rovné hodnote v bode x* . Lokálne maximum je definované obdobným spôsobom.

Pre reálne problémy – funkcie s mnohými premennými – je bežná prítomnosť veľkého množstva lokálnych minim a maxím. Nájdenie ľubovoľného lokálneho optima je relatívne jednoduché za použitia metód lokálnej optimalizácie. Nájdenie globálneho minima alebo maxima funkcie je omnoho zložitejšie a bolo doteraz prakticky nemožné pre mnoho problémov. Táto skutočnosť naznačuje dôležitosť správneho výberu prístupu riešenia daného problému.

2.2. Optimalizačné metódyExistuje mnoho prístupov ako riešiť optimalizačné problémy, napríklad numerické, prírodou inšpirované, či hybridné metódy. Tieto spôsoby budeme súhrnne nazývať optimalizačnými metódami. Optimalizačnú metódu môžeme chápať ako predpis, ktorý popisuje spôsob výpočtu, akým sa vyhýbať alebo prekonávať lokálne minimá (maximá) v jej snahe dostať sa čo najefektívnejšie do minima (maxima) globálneho.

3


2.3. Optimalizačné metódy implementované v GAME

Quasi-Newtonova metóda

Quasi-Newtonova optimalizačná metóda[02][03] je založená Newtonovej metóde hľadania stacionárneho bodu funkcie, bodu v ktorom je gradient je 0. Newtonova metóda predpokladá, že funkcia môže byť lokálne aproximovaná a za pomoci gradientu2 a hessianu3 funkcie je nájdený stacionárny bod. Keďže výpočet druhých derivácií je veľmi náročný, vypočítava Quasi-Newtonova metóda Hesseho maticu len približne iteračne pomocou doplnkov.

Metóda najstrmejšieho zostupu (Steepest descent method)

Algoritmus pre nájdenie najbližšieho lokálneho minima funkcie, ktorý predpokladá, že funkcia má spočítateľný gradient. Metóda najstrmejšieho zostupu[04] je taktiež nazývaná metódou gradientného zostupu, pretože z počiatočného bodu P0 sa pohybuje PiPi1

minimalizovaním pozdĺž čiary vychádzajúcej Pi z v smere opačného gradientu v Pi teda −∇Pi .

Metóda združených smerov (Conjugate gradient method)

Metóda združených smerov[05][02] je algoritmus pre nachádzanie najbližšieho lokálneho minima funkcie o n premenných, ktorá predpokladá, že gradient funkcie je známi alebo spočítateľný. Používa združené smery (aktuálny a všetky predchádzajúce gradienty) namiesto jediného lokálneho gradientu na pohyb z kopca. Ak má okolie minima tvar dlhého a úzkeho údolia, minimum je dosiahnute v omnoho menšom počte krokov ako by to bolo použitím metódy najstrmejšieho zostupu. Túto metódu je možné nasadiť aj na nelineárne problémy. Vlastnosti metódy zlepšuje reštartovanie (zabudnutie predchádzajúcich smerov).

Diferenciálna evolúcia

Diferenciálna evolúcia[02] je algoritmus so špeciálnym reprodukčným mechanizmom, kde potomok vzniká ako súčet váženého rozdielu chromozómov dvoch rodičov pripočíta ku chromozómu tretieho rodiča. Do chromozómu potomka sa postupne vyberajú buď gény z výsledného chromozómu alebo gény štvrtého rodiča. Potomok nahradzuje štvrtého rodiča v populácii ak je kvalitnejší (má lepšiu fitness).

SADE algoritmus

SADE[02] (Simplified Atavistic Differential Evolution) je modifikovaný genetický algoritmus navrhnutý tak, aby obmedzil nežiaduce javy mnohých optimalizačných metód – hlavne ich predčasnú konvergenciu do lokálneho minima. Ako jeden zo svojich operátorov kríženia používa reprodukční mechanizmus diferenciálnej evolúcie. Zaujímavým prvkom sú takzvané radiačné polia, ktoré sú oblasťami prehľadávaného priestoru, v ktorých existuje zvýšená pravdepodobnosť mutácie. Ak sa nejaký jedinec do takéhoto miesta dostane, je pravdepodobné, že bude silne zmutovaný a tým sa presunie do inej časti priestoru. Vstup jedinca do radiačného priestoru zároveň oslabí intenzitu radiácie (zmenšením polomeru radiačného poľa). Radiačné polia sa vytvárajú v miestach lokálnych minim, aby zabraňovali

2 Gradient – gradient funkcie f je definovaný ako vektorové pole, ktorého komponenty sú parciálne derivácie f . Gradient funkcie v určitom bode určuje smer jej najväčšej zmeny.

3 Hessian (hesseho matica) – je štvorcová matica obsahujúca parciálne derivácie druhého stupňa funkcie. Tým popisuje lokálne zakrivenie funkcie mnohých premenných. Hesseho matica je pomenovaná podľa nemeckého matematika menom Ludwig Otto Hesse.

4


predčasnej konvergencii. Globálne minimum je nájdené, keď polomer niektorého radiačného poľa klesne na nulu.

Optimalizácia húfom častíc (Particle Swarm Optimization)

Optimalizácia húfom častíc[06] je stochastický, populačné založený optimalizačný algoritmus imitujúci inteligenciu pozorovanú u húfov vtákov, rýb či hmyzu. Jednotlivci patriaci do húfu sa pohybujú priestorom optimalizovanej funkcie. Ich rýchlosť a smer je ovplyvňovaný aktuálnym lokálnym a globálnym najlepším riešením ako aj určitou dávkou náhody. Každý jednotlivec húfu je náhodne inicializovaný a tak sa správa odlišne od ostatných jednotlivcov.

Optimalizácia pomocou mravcov (Ant Colony Optimization)

Táto pravdepodobnostná technika optimalizácie funkcií imituje chovanie mravcov v ich kolónii[07]. Na začiatku sa mravce pohybujú náhodne, až do doby kým sa jednému z nich nepodarí nájsť jedlo. Pri návrate do kolónie takýto mravec zanecháva za sebou feromónovú stopu vedúcu k zdroju jedla, ktorý našiel. Ak iný mravec nájde takúto feromónovú stopu je menej pravdepodobné, že bude pokračovať v náhodnom pohybe, ale namiesto toho bude nasledovať feromónovú stopu k jedlu. Čím viac mravcov sa vracia od jedla ku kolónii, tým silnejšia je feromónová stopa a tým viac mravcov ju bude nasledovať. Feromónová stopa postupom času slabne, aby sa zabránilo rýchlej konvergencii k lokálnemu minimu.

Hybridné GA a PSO

HGAPSO[02] je hybridný algoritmus spájajúci genetický algoritmus (GA) s optimalizáciou pomocou kolónie mravcov (PSO), ktoré sú spojené na fakte, že oba algoritmy si zakladajú na množine, či populácii jedincov. V PSO sa predpokladá, že všetci jedinci sú rovnako starí (z jednej generácie). Na druhej strane GA je založené na výmene generácií a šľachtení jedincov. Jedinci v rámci jednej generácie sa nemenia. HGAPSO je práve obohatením GA o priučovanie jedincov v rámci jednej generácie. PSO a GA sa dopĺňajú taktiež v tom, že PSO má charakter iteračného prehľadávania a GA prehľadáva priestor skôr spojito.

Ortogonálne prehľadávanie a Stochastické ortogonálne prehľadávanie

Ortogonálne vyhľadávanie (OS)[02] optimalizuje viacrozmernú funkciu postupným výberom a optimalizáciou dimenzie po dimenzii. Stochastické ortogonálne vyhľadávanie (SOS) sa líši od SO len spôsobom výberu optimalizovaných dimenzií. Ako názov napovedá u SOS sú dimenzie vyberané náhodne.

2.4. Ukončovacie podmienkyJednou z dôležitých otázok spojenou s optimalizačnými metódami je otázka: Kedy optimalizáciu ukončiť? Optimalizácia by samozrejme mala byť ukončená pri dosiahnutí globálneho optima. Väčšina metód, ale nevie rozpoznať rozdiel medzi lokálnym a globálnym optimom. Bez znalosti hodnoty optima optimalizovanej funkcie, nie je možné povedať s určitosťou či ho optimalizačná metóda už dosiahla alebo len uviazla v jednom z mnohých lokálnych optim. Väčšina pseudo-kódov vyššie uvedených algoritmov nepopisuje spôsob, ako zistiť kedy daný algoritmus ukončiť, preto sa uplatňujú rôzne metódy na limitovanie času výpočtu. Väčšinou sú špecifické pre jednotlivé metódy, ale väčšinou sú založené na princípe presne daného maximálneho času optimalizácie, počtu cyklov (optimalizačných krokov), určitej formy detekcie konvergencie alebo rozhodnutia, že výsledok je už dostatočne dobrý ako je popisovaný v [08], kapitola: The Structure of Optimization.

5

6

3.State of the art

3. State of the art

Optimalizačné metódy majú využitie v mnohých vedných oboroch pri riešení mnohých problémov, ako napríklad: optimálne plánovanie procesov a trás, návrh plošných spojov, analýza najhorších prípadov, predikcia štruktúry proteínov, či kalibrácia model pri automatickom vyťažovaní znalostí – FAKE GAME.

Z rozšírenosti optimalizačných problémov a metód sa dá predpokladať existencia mnohých softvérov riešiacich rôzne optimalizačné problémy. V tejto kapitole sa budeme v krátkosti venovať súčasnej situácii na poli optimalizačných frameworkov.

OptimJ

OptimJ[09] je algebraický modelovací jazyk. Optimalizačné koncepty ako sú rozhodovacie premenné, obmedzenia a optimalizačné funkcie sú vyjadrené priamo v OptimJ v jednoduchej a intuitívnej forme. OptimJ ďalej ponúka silné procesy na spracovanie veľkého množstva dát.

Plusy: inovatívny prístup k riešeniu problému

Mínusy: vysoká nástupná komplexnosť (potreba učiť sa nový jazyk) source-to-source kompilátor4 - ďalšia komplexnosť iba pre Eclipse

Mosek

Mosek[10] je optimalizačný softvér navrhnutý na riešenie rozsiahlych matematických optimalizačných problémov. Problémy, pre ktoré je Mosek navrhnutý zahŕňajú: lineárne problémy, kónické kvadratické problémy, kvadratické a kvadraticky obmedzené problémy, všeobecné konvexné problémy a zmiešané celočíselné, lineárne, kónické a kvadratické problémy.

Plusy: výborne pripravený na využitie paralelných možností moderných počítačov

schopný riešiť problém simultánne viacerými metódami

Mínusy: komerčný nástroj – uzavretý zdrojový kód implementovaný v jazyku C, poskytuje klientské Java API – žiadna

možnosť rozšírenia

KNITRO

KNITRO[11] je riešič nelineárnych optimalizačných problémov. Je najsilnejším a najflexibilnejším riešičom na trhu, poskytujúcim tri najmodernejšie algoritmy (Interior-point Direct, Interior-point CG, Active set). KNITRO je navrhovaný pre rozsiahle problémy s dimenziami siahajúcimi do stá tisícov. Je efektívny pri riešení lineárnych, kvadratických a nelineárnych optimalizačných problémov – konvexných a nekonvexných.

4 Source-to-source kompilátor znamená, že program napísané v OptimJ nie je možné spustiť priamo na virtuálnom stroji. Je potrebný dodatočný krok – pred-kompilácia do Javy.

7

3.State of the art

Plusy: vysoká výkonnosť množstvo poskytovaných rozhraní pre iné jazyky: C, C++, Fortran, Java,

AMPL, AIMMS, GAMS, MPL, Mathematica, MATLAB Microsoft Excel, and LabVIEW

Mínusy: komerčný nástroj – uzavretý zdrojový kód nie Java nie je ho možné rozširovať

Optimization Toolbox™

Optimization Toolbox™[12] je rozšírenie pre prostredie MATLAB® s nástrojmi a mnohými rozšírenými metódami pre štandardnú, ale aj rozsiahlu optimalizáciu. Tieto algoritmy riešia obmedzené aj neobmedzené, spojité aj diskrétne optimalizačné problémy.

Plusy: stále vyvíjaný a vylepšovaný

Mínusy: komerčný nástroj = uzavretý zdrojový kód nástroj určený pre MATLAB®

OAT

The Optimization Algorithm Toolkit (OAT)[13] je nástroj na vytváranie, vyhodnocovanie, experimentovanie s klasickými a najmodernejšími optimalizačnými algoritmami na obore štandardných vyhodnocovacích problémov. Softvér obsahuje množstvo referenčných implementácií optimalizačných metód, grafov, vizualizácií a mnoho ďalších. OAT poskytuje funkčnú knižnicu pre výpočetnú inteligenciu pre skúmanie existujúcich optimalizačných problémov a metód ako aj na implementáciu nových problémov a metód. Cieľom tejto knižnice bolo podporovať best practice5 optimalizačných problémov a metód, dizajnu a implementácie experimentov ako aj princípov softvérového inžinierstva. Užívateľské rozhranie malo umožniť prístup ne technickému obecenstvu ku konfigurácii a vizualizácii existujúcich techník na štandardných vyhodnocovacích problémoch.

Plusy: veľmi blízke nášmu zámeru open source implementované v Jave poskytuje užívateľské rozhranie umožňujúce manipuláciu s vnútornými

parametrami optimalizačných metód a ich vizualizácie množstvo implementácií

Mínusy: relatívne mŕtvy projekt (posledné vydanie v1.4 09/2007) nedotiahnuté z architektonického hľadiska (all-in-one solution, na

použitie čo i len najmenšej zložky, je potrebné do svojho projektu zaniesť celý OAT)

nezvládnuté z hľadiska objektovo orientovaného návrhu (rozsiahle zneužívanie dedičnosti, nahradzujúce v podstate všetky návrhové vzory)

silná zviazanosť domén, problémov a optimalizačných metód znižuje znovu použiteľnosť a zvyšuje komplexnosť implementácie nových prvkov

5 Best practice – doslovne „najlepšie praktiky“ alebo „osvedčené praktiky“ predstavujú akumuláciu znalostí v programátorskej praxy. Ich nasledovaním sa očakáva dosiahnutie kvalitných výsledkov v zmysle pripravenosti softwéru na zmeny požiadavkov.

8

3.State of the art

SIGOA

Simple Interface for Global Optimization Algorithms (SIGOA)[14][08] dovoľuje špecifikáciu a riešenie ľubovoľných vyhľadávacích a optimalizačných problémov. Algoritmy riešiace problém globálnej optimalizácie obsahujú randomizované algoritmy ako evolučné algoritmy, genetické algoritmy a PSO ako aj heuristiky ako vyhľadávací algoritmus A*. S knižnicou je dodávaná aj elektronická kniha, ktorá rozoberá témy od základných matematických podkladov až po rôzne globále optimalizačné techniky a ich konkrétne implementácie.

Plusy: veľmi blízke nášmu zámeru open source implementované v Jave množstvo implementácií sprievodná elektronická kniha[08] je kvalitná a obsiahla, veľmi užitočný

zdroj informácií

Mínusy: malá aktivita na projekt (posledné zmeny cca. 11/2008) nulové využitie už existujúceho kódu, open source knižníc, atd. nezvládnuté objektovo orientované princípy – ťažko udržiavateľný kód žiadne grafické užívateľské rozhranie

Týchto šesť produktov reprezentuje tri hlavné skupiny softvérov prítomné na súčasnom trhu. Sú to buď veľké, komerčné super riešiče implementovaná v jazyku C ako Mosek a KNITRO schopné riešit rozsiahle problémy s mnoho stránkovými manuálmi pre užívateľov dôkladne zoznámených s optimalizačnými problémami a optimalizačnými metódami. Alebo sa jedná o konceptuálne vyspelé a patrične náročne aplikácie ako Optimization Toolkit™ a OptimJ. Alebo zdanlivo neúspešné java implementácie skôr akademického charakteru – OAT, SIGOA.

9

10

4.Analýza

4. Analýza

V tejto kapitole sa budeme zaoberať motiváciou pre nový softvér a analýzou požiadavkov na tento softvér z užívateľského pohľadu.

4.1. Motivácia

Analýzou súčasného stavu trhu optimalizačných softvérov sme zistili, že neexistuje komerčný softvér, ktorý by pokryl naše potreby. Existujúce open source-ové projekty, ktoré by bolo možné rozšíriť o naše požiadavky, sa javia mŕtve a implementáciou neohybné. To by spôsobilo získavanie informácií o projekte a prípadné zmeny veľmi náročnými.

Rozhodli sme sa preto vytvoriť vlastnú Java implementáciu knižnice pre spojitú optimalizáciu - anglicky Java COntinuous Optimization Library – JCool.

4.2. Prípady použitia

Pri návrhu JCool by sme mali brať v úvahu dve skupiny užívateľov: užívateľa tvoriaceho optimalizačné metódy, teda užívateľa znalého, ktorý je

oboznámený s vnútorným chovaním optimalizačných metód, vyvívajúceho či testujúceho nové optimalizačné metódy alebo ich nové implementácie, nazvime tohto užívateľa napríklad užívateľ akademik

užívateľa, ktorý optimalizačné metódy chce použiť pre riešenie svojich optimalizačných problémov, buď hľadajúceho plné softvérové riešenie alebo “polotovar” - framework, ktorý by mohol využiť vo svojom softvéry – tomuto užívateľovi postačuje hľadieť na optimalizačné metódy ako na čierne skrinky, nazvime tohto užívateľa užívateľ inžinier

Na základe týchto dvoch odlišných užívateľov si môžeme predstaviť niekoľko prípadov použitia:

11

Obrázok 1: JCool - Prípady použitia

4.Analýza

4.2.1. Scenár: Testovanie novej optimalizačnej metódy

Aktér: akademik

Predpoklady: užívateľ ovláda programovací jazyk Java užívateľ implementoval alebo obdržal implementáciu novej

optimalizačnej metódy, ktorej výkonnosť a chovanie chce testovať na štandardných problémoch

optimalizačná metóda bola implementovaná bez znalostí API6 JCool-u

Priebeh: 1. Užívateľ prispôsobí optimalizačnú metódu tak, aby bola schopná interakcií vrámci JCool

2. Užívateľ importuje optimalizačnú metódu do JCool-u3. JCool importovanú optimalizačnú metódu rozpozná, zanalyzuje a

poskytne ako možnosť pri vytváraní experimentov4. Užívateľ experimentuje s nastavením parametrov optimalizačnej

metódy na rôznych optimalizačných problémoch5. JCool poskytne výsledky a priebehy experimentov pre ďalšie

spracovanie

4.2.2. Scenár: Skúmanie vnútorného chovania optimalizačnej metódy

Aktér: akademik

Priebeh: 1. Užívateľ manipuluje s nastaveniami vybranej optimalizačnej metódy

2. Užívateľ spúšťa experimenty3. JCool vizualizuje priebehy vnútorného chovania optimalizačnej

metódy

4.2.3. Scenár: Pozorovanie výkonnosti optimalizačných metód

Aktér: inžinier

Predpoklady: užívateľ má optimalizačný problém, ktorý potrebuje riešiť optimalizačný problém nepatrí do sady problémov obsiahnutých v

JCool užívateľ ovláda programovací jazyk Java

Priebeh: 1. Užívateľ prispôsobí problém tak, aby bol schopný interakcií vrámci JCool

2. Užívateľ importuje optimalizačný problém do JCool-u3. JCool importovaný optimalizačný problém rozpozná, zanalyzuje a

poskytne ako možnosť pri vytváraní experimentov4. Užívateľ spúšťa experimenty na importovanom probléme

používajúc rôzne optimalizačné metódy5. JCool poskytne výsledky a priebehy experimentov pre ďalšie

rozhodovanie

6 API (Application Programming Interface) – rozhranie pre programovanie aplikácií (alebo knižníc), je súbor rutín, dátových štruktúr, objektov/tried alebo protokolov poskytovaných knižnicami pre podporu vytvárania aplikácií.

12

4.Analýza

4.2.4. Scenár: Optimalizácia v zákazníckom prostredí

Aktér: inžinier

Predpoklady: užívateľ potrebuje opakovanie riešiť optimalizačný problém vrámci svojho softvéru

užívateľ ovláda programovací jazyk Java užívateľ absolvoval Scenár: Pozorovanie výkonnosti

optimalizačných metód a vybral si optimalizačnú metódu, ktorou chce problém riešiť

Priebeh: 1. JCool poskytne svoj interný mechanizmus riešenia optimalizačných problémov ako modul, ktorý je možné používať vrámci klientského softvéru

2. Užívateľ zakomponuje tento modul do svojho softvéru3. Užívateľ použitím API tohto modulu prevedie optimalizáciu

problému

4.3. Funkčné požiadavky

Experiment – vo vedeckom pátraní, experiment (z latinského: ex- periri, “vyskúšať”) je metóda skúmania kauzálnych závislostí medzi premennými. Experiment je základom empirického prístupu získavania dát o svete a je používaný v prírodných a sociálnych vedách. Experiment môže byť použitý na riešenie praktických problémov a na potvrdenie alebo vyvrátenie teoretických predpokladov.

Wikipedia, 2009

JCool by mal slúžiť ako platforma, na ktorej je možné prevádzať experimenty pri riešení optimalizačných problémov. Za pomoci výsledkov z týchto experimentov by mal byť užívateľ schopný odpovedať na otázky o výkonnosti alebo vhodnosti použitia jednotlivých optimalizačných metód na rôzne optimalizačné problémy.

JCool preto musí poskytovať možnosť ako adaptovať existujúce implementácie optimalizačných problémov a optimalizačných metód, tak aby boli schopné existovať v jeho prostredí. Musí mať schopnosť rozpoznávať parametre optimalizačných problémov, optimalizačných metód a ich ukončovacích podmienok a umožniť užívateľom ich manipuláciu. Manipuláciou týchto parametrov a opakovaným spúšťaním experimentov bude získavať informácie o priebehu a výsledkov experimentov a tie bude prezentovať užívateľom, ktorí si potom budú môcť urobiť obraz o ich vplyve.

Prajeme si, aby mal JCool GUI (grafické užívateľské rozhranie). Tým by sa mali znížiť nároky na začatie experimentovania a taktiež na vyhodnocovanie ich výsledkov. Užívatelia nebudú musieť študovať návody ovládania aplikácie a môžu okamžite začať experimentovať. Pri experimentovaní bude užívateľ nastavovať rôzne parametre optimalizovaného problému, optimalizačných metód a ich ukončovacích podmienok. Preto by bolo vhodné mať ucelenú grafickú koncepciu nastavovania rôznorodých parametrov.

JCool by mal poskytovať akýsi riešiaci modul dovoľujúci spúšťanie optimalizačných procesov alebo experimentov v prostredí softvéru tretích strán. Tým dovolí užívateľom experimentovať s riešením ich optimalizačného problému v kontrolovanom prostredí JCool-u a v prípade spokojnosti s pozorovanými výsledkami jednoduchý prechod do klientského prostredia a reprodukciu výsledkov pozorovaných v prostredí JCool.

13

4.Analýza

4.4. Dodatočné požiadavkyDodatočné požiadavky, anglicky zvané nonfunctional requirements, sú požiadavky, ktorými sa súdi spracovanie systému. Narozdiel od funkčných požiadavok, ktoré súdia systém podľa jeho správania, teda či systém robí to, čo bolo požadované. Nonfunctional requirements špecifikujú akúsi pridanú hodnotu po naplnení správania systému definovanom funkčnými požiadavkami. Naše dodatočné požiadavky na JCool vychádzajú hlavne z pozorovaní utvorených pri prieskume optimalizačných softvérov na súčasnom trhu.

Jedným z hlavných cieľov JCool-u by malo byť neskončiť ako OAT a SIGOA teda softvérové riešenia, ktoré majú najbližšie koncepcii JCool-u. Oba sú relatívne mŕtve. Domnievame sa, že sa tak stalo z nasledujúcich dôvodov:

Slabé vzbudenie záujmu u prispievateľov – počet ľudí prispievajúcich zdrojovým kódom okrem autora je okolo 2. Úspešné open source-ové projekty, napríklad z dielne Jakarta commons alebo Google code, mávajú niekoľko (väčšinou do 10) tvorcov a aj niekoľko desiatok prispievateľov. Domnievame sa, že slabý záujem prispievateľov mohol byť spôsobený nedostatočnou infraštruktúrou projektu.

Slabá znovu použiteľnosť vytvoreného kódu – v prípade záujmu o použitie jedného z týchto softvérov sa im musí klientsky program prakticky prispôsobiť. Nie je možné použiť len jednu časť, ale je potrebné závisieť na celom softvéry (a jeho knižniciach). To môže odrádzať užívateľov od použitia týchto kódov vo svojom softvéry.

Silná viazanosť na základné koncepty – všetky základné koncepty sú implementované abstraktnými triedami namiesto rozhraní. To spôsobuje silnú viazanosť klientského kódu na knižnicu. Interface7-y umožňujú bezpečné a silné rozšírenia funkcionality napríklad cez tzv. wrapper class idióm opísaný v [15], kapitola 16. Použitím abstraktných tried na definovanie typov nenecháva tvorca knižnice programátorom, ktorý chcú pridať funkcionalitu, žiadnu alternatívu len používať dedičnosť. Výsledné triedy sú slabšie a krehšie než wrapper classes[15].

Ako dodatočné požiadavky na JCool si teba zadávame:

vytvorenie robustnej infraštruktúry projektu na obraz úspešným open source-ovým projektom typu Jakarta commons a Google code – čím viac uľahčíme prispievateľom spôsob prispievania, tým je väčšia pravdepodobnosť ich prilákania

myslieť na znovu použiteľnosť kódu – čím jednoduchšie sa bude JCool používať, tým má väčšie šance na to, že bude používaný v softvéroch tretích strán

minimálne režijné požiadavky na implementáciu základných konceptov – minimalizovaním nárokov kladených na už existujúce implementácie konceptov zvyšujeme pravdepodobnosť ich adaptácie do JCool-u a tým zväčšovanie množstva poskytovaných implementácií

7 Interface (rozhranie) – je abstrakcia, ktorú poskytuje entita svojmu okoliu. Separuje metódy externej komunikácie od interných operácií a tým umožňuje zmenu interných operácií bez ovlyvnenia komunikácie.

14

5.Riešenie

5. Riešenie

V tejto kapitole si predstavíme JCool ako platformu a JCool ako framework. Popíšeme si v krátkosti ich funkcionalitu a potom si detailne predstavíme architektúru a dizajn oboch častí. Popíšeme rozhodnutia, ktoré sme museli urobiť a ako vyzerá súčasný stav manažmentu projektu.

5.1. Platforma JCool

Platformou JCool myslíme aplikáciou umožňujúcu spúšťanie experimentov – optimalizácie rôznych problémov optimalizačnými metódami, zbierajúcu a prezentujúcu ich priebeh a výsledky. Platforma má dva módy: plne grafický mód Obrázok 2 a takzvaný headless alebo bezhlavý mód Obrázok 3, v ktorom sa spustí bez grafického rozhrania.

Obrázok 2 ukazuje JCool v grafickom móde po skončení experimentu. Ukončenie experimentu je signalizované oknom zhrňujúci experiment, ktoré prezentuje základné nastavenia ako je:

optimalizovaný problém (Function)

metódu použitú na optimalizáciu (Optimization method)

spôsob riešenia (Solver)

jednoduché štatistiky vyhodnocovania optimalizačnej funkcie (evaluations)

výsledok optimalizácie (Solution)

informáciu o tom ako bol optimalizačný problém ukončený (Stopped on)

Toto okno umožňuje výsledky a priebeh spoločne uložiť v XML formáte do súboru za pomoci

15

Obrázok 2: Platforma JCool

5.Riešenie

tlačítka Save results.

Spustenie platformy JCool v headless (bezhlavom) móde sa deje cez príkazový riadok. Ak pri spúšťaní užívateľ zadá prepínač --headless, ktorý ako parameter očakáva súbor obsahujúci definíciu experimentu, JCool prevedie experiment podľa tejto definície bez štartovania užívateľského rozhrania a bez potreby akejkoľvek ďalšej interakcie s užívateľom. Zhromažďuje priebeh experimentu a jeho výsledky. Výsledky prezentuje do konzole a všetko uloží do súboru so štandardným názvom. Podobne ako v prípade grafického módu. Headless mód dovoľuje JCool spúšťať napríklad vzdialene na serveri alebo lokálne bez užívateľského rozhrania pre dlho trvajúce optimalizácie. Vďaka tomu, že JCool zhromažďuje aj samotný priebeh optimalizácie, je možné si ho prezrieť aj po jej skončení.

Hlavné okno grafického módu platformy má niekoľko základných častí:

Konfiguračný panel (označený číslom 1) umožňuje výber optimalizačného problému, metódy a spôsobu riešenia. Za pomoci špeciálneho konfiguračného frameworku (ktorý umožňuje interaktívne konfigurovať ľubovoľnú JavaBean8 komponentu - bude popísaný

8 JavaBean – konvencia softvérových komponent v jazyku Java, ktorá napomáha jej znovupoužiteľnosti.

16

Obrázok 4: Platforma JCool - popis užívateľského rozhrania

Obrázok 3: Platforma JCool - headless mód

5.Riešenie

neskôr), konzistentným spôsobom umožňuje zmenu parametrov optimalizovanej funkcie, optimalizačnej metódy, riešiča, ukončovacích podmienok a vizualizácií (viď záložky na pravej strane panelu). Tento panel bol modelovaný podľa návrhového vzoru Action Panel popísanom v [16].

Panel vizualizácií (označený číslom 2) zobrazuje aktuálne hodnoty vnútorného stavu či terajšej hodnoty optimalizovanej veličiny v (nie len) grafickej forme. JCool poskytuje možnosť zobrazovať dve užívateľské vizualizácie počas behu experimentu. V dolnej časti panelu sa nachádzajú jeho ovládacie prvky. Pomocou nich je možné skryť/odkryť zobrazenie takzvaných telemetrii (panel označený číslom 3), vybrať si hlavnú a vedľajšiu vizualizáciu a vybrať si medzi niekoľkými typmi rozloženia vyzualizácií. Tento panel bol modelovaný podľa návrhového vzoru Center stage popísanom v [16].

Panel telemetrie (označený číslom 3) je jedinou stále prítomnou vizualizáciou priebehu optimalizácie. Zobrazuje niektoré základné údaje o priebehu, ako je: trvanie optimalizácie, počet iterácií (počet vykonaných optimalizačných krokov), hodnotu momentálne prehľadávaného miesta a doteraz najlepšiu nájdenú hodnotu. Tento panel je možné skryť pomocou prepínača Show telemetry, ktoré sa nachádza medzi ovládacími prvkami panela vizualizácií.

Panel záznamov (označený číslom 4) sa nachádza v spodnej časti užívateľského rozhrania platformy. Do tohto panelu JCool zapisuje správy o svojom fungovaní, ako sú napríklad spúšťanie experimentov. Ich úspešné alebo neúspešné dokončenie. Informácie o uložených výsledkoch a pod.

Vizualizácie priebehu optimalizácie sú asi najzaujímavejšou časťou užívateľského rozhrania a tak sa ich plocha dá zväčšiť na maximum. Pomocou nastavenia položky View type je možné zmeniť pomer v akom sa zobrazuje hlavná vizualizácia proti vedľajšej – od vyváženej plochy (viď Obrázok 5) cez preferovanie hlavnej vizualizácie až po výlučné zobrazovanie jednej z vizualizácií.

Zvoliť si vizualizácie je možné pred spustením experimentu (počas behu experimentu sú

17

Obrázok 5: Platforma JCool - priblíženie telemetrie

5.Riešenie

prvky výberu vizualizácií zašednuté – neaktívne). Vizualizácie sú počas behu experimentu upovedomené pri každom optimalizačnom kroku o jeho priebehu. Nie každá vizualizácie dokáže zobrazovať informácie poskytované každou optimalizačnou metódou a naopak, nie každá metóda je schopná produkovať dáta vhodné pre každú vizualizáciu. Preto sa zoznam možných vizualizácií dynamicky mení na základe momentálne vybranej optimalizačnej metódy na panele konfigurácií.

Momentálne sa s JCool platformou dodáva 5 funkcií, 3 optimalizačné metódy a 3 vizualizácie.

5.2. Framework JCool

Jednou z hlavných častí, na ktorej stavia platforma JCool je framework JCool. Platforma zároveň slúži ako ukážka ako framework používať. JCool framework obsahuje všetko potrebné na spustenie optimalizácie v klientskom prostredí. Buduje na ďalšom z modulov JCool, ktorým je takzvané jadro alebo core, ktoré obsahuje centrálne koncepty optimalizácie, ktorými sú napríklad definícia bodu, gradientu, hessianu, funkcie, optimalizačnej metódy, ukončovacích podmienok atď.

Aby bol JCool framework ľahko adoptovateľný (čo považujeme za jeden z kľúčových faktorov úspechu celého projektu) má jediný presne definovaný vstupný bod a tým je interface Solver. Implementácie tohto rozhrania (teda jednotlivé typy riešičov) sú zodpovedné za jednorázové vyriešenie optimalizačného problému optimalizačnou metódov, pri ktorom zbierajú jeho štatisticky.

JCool framework je interne využívaný platformou JCool vrámci experimentovania. Tým chceme dosiahnuť reprodukovateľnosť výsledkov dosiahnutých testovaním na platforme v klientskom prostredí za použitia len JCool frameworku.

V snahe zjednodušiť narábanie s riešičom a odtieniť užívateľa (v tomto prípade programátora) od komplikovaných výpočtov pri optimalizácii sme dospeli k nasledujúcemu kódu pokrývajúcemu priebeh optimalizácie. Je to všetko, čo musí programátor obsiahnuť vo svojom kóde, aby bol schopný reprodukovať výsledky dosahované s platformou.

18

Obrázok 6: Platforma JCool - ukážka vizualizácie

5.Riešenie

// vytvorenie riešiča dovoľujúceho maximálne 50 iteráciíSolver solver = SolverFactory.getNewInstance(50);

// inicializácia riešiča spočíva v predaní funkcie a optimalizačnej metódy// metóde initsolver.init(new RosenbrockFunction(), new SteepestDescentMethod());

// samotný optimalizačný proces sa spustí volaním metódy solve a skoncí sa

// pri dosiahnutí optima (alebo v tomto prípade vyčerpaním maximálneho počtu // iterácií)solver.solve();

// po skončení optimalizačného procesu je možné odobrať jeho výsledok// a štatistikyOptimizationResults r = solver.getResults();

// a prezentovať ich svetuSystem.out.println(r.getSolution());

19

5.Riešenie

5.3. Architektúra

Existujú dva obvyklé elementy vnímané ako architektúra systému: Jedným je rozdelenie aplikácie na časti na najvyššej úrovni a druhým sú rozhodnutia, ktoré sa dajú len ťažko zmeniť. Je však stále jasnejšie, že existuje viacero spôsobov ako poňať architektúru systému alebo ináč povedané, existujú viaceré architektúry systému a predstava toho čo je architektonicky dôležité sa mení počas jeho života -

Martin Fowler, Patterns of Enterprise Application Architecture[17].

V tejto kapitole sa budeme zaoberať rozdelením komponent JCool-u na najvyššej úrovni a vysvetlíme si rozhodnutia za týmto rozdelením.

Separáciou celej optimalizačnej knižnice do niekoľkých nezávislých projektov sa snažíme dosiahnuť flexibilitu nie len voči koncovým užívateľom (v tomto prípade programátorom), ktorí tak majú možnosť vybrať si len to čo presne potrebujú a tým neutvárať vo svojom projekte nepotrebné závislosti. Ale aj voči vývojárom samotnej knižnice, ktorí sa tak môžu venovať len svojej danej časti projektu.

JCool sa skladá z týchto častí:

Jadro (core) obsahujúce základné koncepty.

Riešič (solver) obsahujúci koncepty a implementácie procesov spojených s optimalizáciou. Riešič spolu s jadrom vytvárajú JCool framework.

Porovnávač (benchmark) obsahujúci implementácie základných funkcií a optimalizačných metód poskytovaných platformou JCool na testovanie a porovnávanie výkonnosti nových optimalizačných metód.

Experiment (experiment) je nadstavba nad riešičom zodpovedná za vykonávanie experimentov, akumuláciu priebehu a jeho vizualizáciu a perzistenciu. Spolu s poslednou časťou vytvára platformu JCool.

Užívateľské rozhranie (UI) je časť projeku spájajúca všetky predchádzajúce časti do prezentovateľnej a interaktívnej podoby.

20

Obrázok 7: JCool - architektúra

5.Riešenie

JCool obsahuje ešte na jednú časť, ktorá sa však od JCool odčlenila a vytvorila samostatný projekt – BeanConfigurations. Ide o framework umožňujúci jednoduché a konzistentné nastavovanie parametrov ľubovoľnej JavaBean. Okrem časti core je tento framework používaný v každej z častí JCool-u. Taktiež sa začína používať v projekte FAKE GAME.

Časti JCool-u na sebe závisia vrstvovito zdola nahor. Závislosti projektu core sa snažíme udržať na minimum. Na projekte core zavisí projekt solver a tranzitívne (cez projekt solver) aj celá platforma JCool. Každá časť JCool je vedená ako samostatný projekt, ktorý je uložený vo verzovacom systéme pod vlastnou adresárovou štruktúrou, je budovaná samostatne, má samostatné verzovanie (číslo aktuálnej verzie), dokumentáciu a môže mať aj odlišných tvorcov a prispievateľov.

Obmedzením rozsahu projektov dávame tvorcom jednotlivých projektov viac priestoru na ich kreatívne riešenia. V projekte solver je napríklad možné riešiť viac vláknové optimalizačné výpočty bez uvažovania nad požiadavkami na užívateľské rozhranie. A naopak v projekte experiment môže vývojár ťažiť z inovácií implementovaných v projekte solver aj bez, nahliadnutia do jeho zdrojových kódov.

Vyčlenenie jadra do samostatného projektu core umožňuje tvorcovi, implementátorovi, novej optimalizačnej metódy závisieť (a zaoberať sa) len na projekte core, v ktorom nájde všetky základné koncepty, s ktorými sa jeho metóda počas svojho života v JCool stretne. Prípadne sa môže inšpirovať jednou z implementácií v projekte benchmark. Všetkými ostatnými projektami (a tým aj značným množstvom zdrojového kódu) sa nemusí vôbec zaoberať. Znižovaním počtu konceptov, ktorými sa musí tvorca zaoberať, mu nechávame priestor venovať sa problému, ktorý rieši namiesto zápasenia so zložitými väzbami či závislosťami vrámci JCool.

O to, aby tento systém fungoval spoľahlivo a čo najmenej zaťažoval vývojárov sa musíme postarať my dôkladnou správou všetkych projektov. Spôsobom akým to chceme dosiahnuť si popíšeme v nasledujúcej kapitole.

5.4. Správa projektov

5.4.1. MavenNa minimalizovanie réžie spojenej s udržiavaním viacerých projektov, namiesto jedného, používame na ich správu Maven[18]. Maven, z hebrejského mevin, je možné preložiť ako zberateľ znalostí alebo dôveryhodný odborník, v určitom obore, ktorý sa snaží predávať svoje znalosti ostatným.

Maven (softvér) vychádza z kuchyne Apache Software Foundation. Konkrétne začínal v projekte Jakarta Turbine. Je to softvér na správu projektov založený na koncepte objektového modelu projektu (POM). Maven dokáže spravovať celý životný cyklus projektu od kompilácie, testovania, archivácie, reportovanie až po dokumentáciu a distribúciu, všetko z centrálneho zdroja informácií. Hlavným cieľom Maven-u je umožniť vývojárom pochopenie stavu projektu v čo najkratšom čase, čo robí jedným a hlavne jednotným vstupným bodom do každého projektu (založenom na Maven-e), ktorým je súbor obsahujúci projektový objektový model vo formáte XML – pom.xml. Vrámci propagácie best practices Maven predpokladá (hoci nevyžaduje) jednotnú adresárovú štruktúru projektov. Umožňuje tým jednoduchosť prechodu od projektu ku projektu prakticky odstránením fáze zoznamovania sa s projektovou štruktúrou. Ak vývojár pozná jeden Maven projekt, pozná ich všetky.

Jeho vlastností úspešne využívajú projekty Apache Software Foundation či Google code, ktorých úspechu by sme sa chceli pripodobniť. Preto budeme používať Maven vo všetkých fázach projektu od kompilácie až po vydávanie jednotlivých verzií.

21

5.Riešenie

5.4.2. SubversionAko verzovací systém pre naše projekty sme si vybrali Subversion. Subversion je voľný, open source verzovací systém vytvorený ako (z veľkej časti) kompatibilný následník široko rozšíreného Concurrent Version System (CVS). Subversion spravuje súbory a adresáre skrz čas. Strom súborov je vložený do centrálneho úložiska. Toto úložisko je podobné obyčajnému file serveru, až na to, že si pamätá zmeny, ktoré boli prevedené na spravovaných súboroch a adresároch. To užívateľom dovoľuje obnoviť staršie verzie svojich dát alebo študovať ako sa ich dáta menili v čase[19]. Subversion vie pristupovať k svojmu úložisku cez počítačové siete a internet, čo dovoľuje užívateľom pracovať na jednom úložišti z rôznych počítačov. Na určitej úrovni schopnosť viacerých ľudí meniť a spravovať určitú množinu dát z rôznych lokácií podporuje kolaboráciu. Celý tento proces môže prebiehať omnoho rýchlejšie ak existuje viac než jedna cesta, cez ktorú musia všetky modifikácie prebiehať. A pretože všetko v úložišti je verzované, ak sa doňho dostane škodlivá zmena je jednoduché túto zmenu vrátiť späť.

Subversion je dôverne známy v open source komunite a je používaný ako verzovací systém v mnohých projektoch ako sú: Apache Software Foundation, KDE, Python, Ruby, SourceForge.net Tigris.org a taktiež Google code. Jeho prednosti oproti CVS sú zjavné aj pre komerčné firmy, kde CVS postupne nahradzuje.

Medzi hlavné črty Subversion patria:

Verzovanie adresárov – narozdiel od CVS, ktoré zaznamenáva históriu len na súboroch, implementuje Subversion celý virtuálny súborový systém zaznamenávajúci zmeny na celých adresárových stromoch.

Atomické commit9-y – zmeny vytvorené v jednom commite bežne ovplyvňujú niekoľko súborov, či adresárov naraz, Subversion zabezpečuje, že kolekcia zmien buď prejde do úložiska kompletne alebo vôbec.

Abstraktná sieťová vrstva – vďaka ktorej Subversion umožnuje implementáciu nových prenosových mechanizmov.

Open source – CollabNet/Tigris.org Apache-style licencia.

5.4.3. SourceForgeSourceForge je internetové nálezisko open source projektov. Developerov open source softvéru slúži ako centralizovaná lokácia pre kontrolu a splavovanie nie len samotného softvéru ale aj jeho vývoja. K augustu 2008 hosťuje SourceForge 180 000 projektov a skoro dva milióny registrovaných užívateľov. SourceForge ako platforma pre kolaboráciu umožňuje vývojárom zadarmo hosťovať stránky ich projektu a dodáva štandardné nástroje na kolaboráciu a vývoj, medzi ktoré patrí projektové CVS, Subversion, Git alebo Mercurial úložisko pre správu zdrojových kódov, projektové wiki stránky pre bázu znalostí, metriky a štatistiky prístupov do MySQL databáze a unikátnu subdoménu pre každý projekt.

Pri zvyšovaní aktivity na určitom projekte, sa ho interný hodnotiaci systém SourceForge snaží viac zviditeľniť a tým povzbudiť príliv nových prispievateľov. Vzhľadom na to, že mnoho open source projektov zlyháva kvôli nedostatočnej podpory vývojárov, vystavenie projektov takejto rozsiahlej komunite môže kontinuálne vnášať projektom nový život.

FAKE GAME, rodičovský projekt JCool-u, využíva SourceForge a možnosti, ktoré poskytuje a JCool pôjde v jeho šľapajách.

9 Commit – akákoľvek zmena vykonaná na súbore alebo adresári v úložišti. Napríklad pridanie nových súborov či adresárov, zmena ich obsahu, alebo premiestnenie či pomenovanie.

22

5.Riešenie

5.5. Dizajn a implementácia

V tejto kapitole sa budeme zaoberať popisom najzaujímavejších častí návrhu a implementácie jednotlivých projektových častí JCool, ich kritické miesta a popíšeme si návrhové vzory a open source knižnice použité v týchto miestach.

Aj JCool samotný je Maven projekt. A ako každý Maven projekt má jediný vstupný bod, ktorým je súbor pom.xml. Tento súbor sa nachádza priamo v hlavnom adresári projektu viď Obrázok 8. V ňom sú definované všetky podprojekty (teda – core, solver, benchmark, experiment, ui) ako moduly a tým sa z tohto projektu stáva takzvaný rodičovský projekt. Každá akcia spustená na tomto projekte sa zároveň propaguje do jeho modulov, tj. spustením kompilácie na tomto projekte, skompilujeme každý projekt definovaný ako jeho modul. V zmysle DRY10 sú v rodičovskom pom.xml definované všetky zdroje, ktoré sú spoločné pre jeho modul, ako napríklad definícia interného úložiska zdrojových kódov, úložiska artefaktov či spoločných závislostí.

Každý pom.xml musí definovať takzvané Maven koordináty: meno artefaktu, ktorý predstavuje (artifactId), meno skupiny artefaktov, do ktorých tento artefakt patrí (groupId) a jeho verziu (version).

Koordináty projekty JCool sú:

<groupId>cz.cvut.felk.cig</groupId><artifactId>jcool</artifactId>

Jednotlivé podprojekty sa líčia v artifactId:

<artifactId>jcool-core</artifactId>

Vďaka týmto koordinátom sa je možné na výsledný skompilovaný artefakt odkazovať, používať a závisieť na ňom v iných projektoch.

Maven umožňuje dediť definície z rodičovského pom.xml do pom.xml potomkov. Ak chce mat potomok prístup k informáciám v rodičovskom pom.xml, musí sa prihlásit ako jeho potomok. To urobí vo svojom pom.xml nadefinovaním koordinátov svojho rodiča. Podľa konvencie sa rodičovský pom.xml vyhľadáva v adresáry, ktorý je o úroveň vyššie od pom.xml patriaceho potomkovi. Obrázok 9 ukazuje vzťah medzi rodičovským pom.xml (nachádzajúcim sa v adresári jcool) a pom.xml jeho modulov (podprojektov nachádzajúcich sa v podadresároch adresára jcool).

10 DRY (Don't Repeat Yourself) – v preklade „neopakuj sa“ je jedným z princípov obmedzovania duplikácie. Duplikácia je v programovaní považovaná nežiadúca, pretože znižuje prehľadnosť, sťažuje zmeny a vedie k príležitostiam na inkonzistenciu.

23

Obrázok 8: JCool - projektová štruktúra

5.Riešenie

Táto štruktúra je zároveň prítomná aj v projektovom Subversion úložisku na serveroch SourceForge.net. Z nasledujúceho obrázku by mala byť zjavná aj rovnomerná štruktúra Maven projektov a z nej vyplývajúca jednoduchosť orientácie sa v nich. Každý projekt má svoj pom.xml, ktorý o ňom poskytuje všetky potrebné informácie a je vstupným bodom do tohto projektu.

Každý projekt môže obsahovať množinu závislostí, teda projektov, ktoré pre svoje fungovanie vyžaduje. O splnenie týchto závislostí sa Maven stará automaticky, ich sťahovaním z takzvaných úložísk artefaktov. Závislosti medzi časťami JCool-u popísané v kapitole 5.3 sú implementované práve definíciou týchto závislostí. Nasledujúci kus pom.xml ukazuje závislosť projektu solver na projekte core.

<?xml version="1.0" encoding="UTF-8"?><project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="...">  <parent> <artifactId>jcool</artifactId> <groupId>cz.cvut.felk.cig</groupId> <version>1.0-SNAPSHOT</version> </parent> <modelVersion>4.0.0</modelVersion> <groupId>cz.cvut.felk.cig</groupId> <artifactId>jcool-solver</artifactId> <packaging>jar</packaging> <version>1.0-SNAPSHOT</version> <name>jcool-solver</name>

<dependencies>  <dependency> <groupId>cz.cvut.felk.cig</groupId> <artifactId>jcool-core</artifactId> <version>1.0-SNAPSHOT</version> </dependency> ... </dependencies>...</project>

24

Obrázok 9: JCool - projektová štruktúra (detail)

5.Riešenie

V nasledujúcich kapitolách si preberieme štruktúru a koncepty jednotlivých projektov.

5.5.1. CoreJedným z hlavných balíčkov projektu core, je balíček cz.cvut.felk.cig.jcool.core, ďalej nazývaný len balíček core. Nasledujúci obrázok ukazuje jeho najdôležitejšie časti:

Už hneď v prvom balíčku je možné objaviť rozdiel oproti projektom OAT a SIGOA. Všetky základné koncepty JCool-u akými sú funkcie, optimalizačné metódy, ukončovacie podmienky a telemetrie, sú vyjadrené rozhraniami narozdiel od abstraktných tried implementujúcich základné koncepty OAT s SIGOA. Ako bolo spomenuté v kapitole 4.4., použitím rozhraní otvárame priestor návrhovým vzorom, ktoré nemajú veľa priestoru pri použití abstraktných tried. Ako príklad môžeme uviesť implementáciu rozhrania ObjectiveFunction s názvom BaseObjectiveFunction, ktorá je opísaná v kapitole 5.5.2.

Optimalizačné funkcie

Na definíciu funkcií slúžia prvé štyri rozhrania: Function, FunctionBounds, FunctionGradient a FunctionHessian. Každá funkcia, ktorá má existovať v prostredí JCool musí implementovať rozhranie Function. Každý objekt implementujúci toto rozhranie vie odpovedať na dotaz na jeho hodnotu v určitom bode pomocou metódy Function#valueAt(Point) a taktiež na dotaz na jeho dimenziu Function#getDimension(). Objekty typu Point, teda body, v ktorých nás funkčná hodnota zaujíma, sú nemenné schránky schopné udržiavať v sebe jednorozmerné polia hodnôt typu double. Je ich možné vytvárať pomocou statickej factory metódy Point#at(double...). Implementácia ostatných rozhraní závisí na tom, či je definičný obor funkcie obmedzený (vyjadruje FunctionBounds) a či funkcia má analytický gradient resp. analytický hessian (vyjadruje FunctionGradient resp. FunctionHessian).

25

Obrázok 10: Hlavné koncepty v projekte core

5.Riešenie

Implementáciou určitej množiny týchto rozhraní tvorca optimalizačnej funkcie priamo v hlavičke novej optimalizačnej funkcie definuje jej charakter. Ukážme si príklad.

public class BoothFunction implements Function, FunctionBounds {

public double valueAt(Point point) { double[] ax = point.toArray(); return (((ax[0] + 2 * ax[1] - 7 ) * (ax[0] + 2 * ax[1] - 7 )) + ((2 * ax[0] + ax[1] - 5) * (2 * ax[0] + ax[1] - 5 ))); }

public int getDimension() { return 2; }

public double[] getMinimum() { return new double[] { -1.0, -1.0 }; }

public double[] getMaximum() { return new double[] { 1.0, 1.0 }; }}

Toto je implementácia Boothovej funkcie, jednej z funkcií dodávaných v projekte benchmark. Hlavička funkcie nám prezrádza, že táto funkcia má obmedzený definičný obor a taktiež, že táto funkcia (alebo jej implementácia) nemá analytický gradient ani hessian. Metóda getDimension() vracia číslo 2, čo vraví, že je to funkcia dvoch parametrov (a teda ako parameter metódy valueAt(Point) očakáva dvojrozmerný bod). Metódy getMinumum() a getMaximum() vrátia pole o dvoch prvkoch reprezentujúce minimálne a maximálne hranice Boothovej funkcie v jednotlivých dimenziách.

Point, Gradien a Hessian

Funkcie komunikujú so svojím okolím za pomoci objektov troch špeciálnych tried dodávaných s balíčkom core: Point, Gradient a Hessian.

Tieto triedy nie sú ničím viac ako obalmi jedno a dvojrozmernými polí primitívneho typu double. Tieto triedy neposkytuje public alebo protected konštruktory a tým sú pre okolitý svet efektívne final (nerozšíriteľné). Každá z nich poskytuje factory metódu na vytváranie inštancií. Žiadna z inštancií týchto troch tried neposkytuje metódy schopné pozmeniť jej vnútorný stav a to ešte dopĺňa vytváraním defenzívnych kópií interných polí. Toto všetko spoločne vytvára z objektov týchto tried takzvané immutable alebo nemenné (nezmeniteľné)

26

Obrázok 11: Základný koncept - Funkcia

Obrázok 12: Základný koncept - Komunikácia s funkciou

5.Riešenie

objekty. Takéto objekty sú nie len jednoduché, ale aj inherentne thread safe11. Pretože ich dáta nemôže nikto pozmeniť, môže k nim pristupovať viacero threadov (výpočetných vláken) naraz. Tento prístup k vytváraniu threadovo bezpečných objektov je opísaný v jednej z najznámejších kníh o Jave od Joshuu Blocha - Effective Java[15] v kapitole 15 Minimizing mutability.

Prečo je dôležité, aby inštancie týchto tried boli thread safe? Je to kvôli tomu, že budú na nich pristupovať viaceré výpočetné vlákna naraz. V najjednoduchšom prípadne pri použití užívateľského rozhrania bude potrebné tieto dáta zbierať a vizualizovať, čo sa bude diať v inom vlákne ako samotný optimalizačný výpočet.

Implementácie funkcií teda vďaka týmto triedam komunikujú zo svetom threadovo bezpečným spôsobom.

Optimalizačná metóda a ukončovacie podmienky

Optimalizačné metódy sú definované implementovaním rozhrania OptimizationMethod. Toto rozhranie definuje tri metódy, ktoré obkolesujú optimalizačný proces. Definuje metódu volanú pred začatím optimalizačného procesu, ktorá zoznámi optimalizačnú metódu s optimalizovanou funkciou (OptimizationMethod#init(ObjectiveFunction)), metódu, ktorá určuje kedy sa optimalizačný proces má ukončiť (OptimizationMethod#getStopConditions()) a metódu, ktorá definuje optimalizačný krok (OptimizationMethod#optimize()).

Každá optimalizačná metóda je zároveň aj producentom telemetrie, čo je vyjadrené implementovaním rozhrania Producer<? extends Telemetry>. Telemetria je používaná nie len ako medzi výsledok, ale aj ako samotný výsledok optimalizačného procesu. Telemetrie budú v krátkosti vysvetlené neskôr v tejto kapitole a detailne v kapitole 5.5.3.

Koncept veľmi úzko spojený s optimalizačnými metódami sú ukončovacie podmienky. Ukončovacie podmienky informujú riešiteľa optimalizačného problému či má proces ukončiť alebo má pokračovať nasledujúcim optimalizačným krokom. Tomuto účelu slúži jednoduché rozhranie StopCondition definujúce jedinú metódu odpovedajúcu presne na túto jednu otázku.

Implementáciu optimalizačnej metódy ukážeme na príklade SteepestDescentMethod.

11 Thread safety – threadovo (vláknovo) bezpečná časť programu, je taká časť, ktorú môžu volať viaceré výpočetné vlákna bez nežiadúcich interakcií medzi nimi.

27

Obrázok 13: Základný koncept - Optimalizačná metóda, Ukončovacia podmienka

5.Riešenie

public class SteepestDescentMethod implements OptimizationMethod<ValuePointTelemetry> { ...

public SteepestDescentMethod() { this.stopCondition = new SimpleStopCondition(); }

public void init(ObjectiveFunction function) { this.function = function;

p = new double[function.getDimension()]; Point startingPoint = Point.at(1.5, 1.5); this.fx = function.valueAt(startingPoint); this.gradient = function.gradientAt(startingPoint).toArray(); this.x = startingPoint.toArray();

this.stopCondition.init(function.valueAt(startingPoint), 1.0e-20, MachineAccuracy.SQRT_EPSILON, 0); }

public StopCondition[] getStopConditions() { return new StopCondition[]{stopCondition}; }

public void optimize() { for (int i = 0; i < p.length; i++) { p[i] = -gradient[i]; }

//Line search fx = lineSearchMethod.minimize(x, p, fx, gradient);

consumer.notifyOf(this);

//test for convergence stopCondition.setValue(fx); }

...}

V metóde init() si optimalizačná metóda musí zapamätať funkciu, ktorú má v optimalizačnom kroku optimalizovať a pripraviť optimalizačnú metódu na začatie optimalizačného procesu. Metódou getStopConditions() vráti všetky ukončovacie podmienky (v tomto prípade jedinú, ktorou je inštancia triedy SimpleStopCondition) schopné zastaviť opakovanie optimalizačného kroku. Optimalizačný krok, definovaný v metóde optimize(), je volaný dovtedy, kým niektorá z ukončovacích podmienok nedá povel na ukončenie celého optimalizačného procesu. V metóde optimize() musí byť ukončovacia podmienka aktualizovaná. Optimalizačné metódy nie sú zodpovedné za vyhodnocovanie ukončovacích podmienok, len za aktualizáciu ich rozhodovacieho kritéria. Samotnú kontrolu, či sa má optimalizačný proces ukončiť alebo má pokračovať, má na starosti ten, kto optimalizačný problém rieši. Ukončovacie podmienky sú len akýmsi nástrojom na rozpoznanie splnenia určitých podmienok počas optimalizačného procesu.

Jednou zo zaujímavostí rozhrania OptimizationMethod je, že metóda OptimizationMethod#init(ObjectiveFunction) dostáva ako parameter objekty typu ObjectiveFunction a nie typu Function. Ako naznačuje Obrázok 10 ObjectiveFunction v

28

5.Riešenie

sebe obsahuje rozhranie Function spolu s rozhraniami FunctionBounds, FunctionGradient a FunctionHessian. Tým zabezpečuje, že optimalizačná metóda smie volať na optimalizovanej funkcii všetky z uvedených metód. Odkiaľ sa, ale implementácie tohto rozhrania vezmú, ak ich optimalizačná funkcia neposkytuje (ako je tomu aj u Boothovej funkcie), si povieme v nasledujúcej kapitole.

Telemetria

Proces tvorby a predávania medzivýsledkov medzi participantami optimalizačného procesu, ktorý telemetria umožňuje, bude vysvetlený v kapitole 5.5.3. Na tomto mieste si predstavíme jeho médium – Telemetrie.

Tak ako zabezpečujú Point, Gradient a Hessian threadovo bezpečnú komunikáciu pre implementácie funkcií, tak by mali implementácie rozhrania Telemetry poskytovať threadovú bezpečnosť komunikácie pre implementácie optimalizačných metód (a nie len ich). Tri implementácie tohto rozhrania dostupné v baličku core threadovú bezpečnosť dosahujú podobným spôsobom ako Point, Gradient a Hessian. Sú založené na troch hlavných typoch hodnôt, s ktorými sa pri optimalizácii stretneme: hodnota (ValueTelemetry), aktuálny bod spolu s jeho hodnotou (ValuePointTelemetry) a zoznam aktuálnych bodov spolu s ich hodnotami (ValuePointListTelemetry).

29

Obrázok 14: Základný koncept - Telemetria

5.Riešenie

5.5.2. SolverProjekt Solver zakladá na jadre JCool a rozširuje ho o koncepty spojené s ovládaním optimalizačného procesu, zberu štatistík a výsledkov. Hlavným balíčkom projektu Solver je cz.cvut.felk.cig.jcool.solver, ďalej označovaný len ako balíček solver.

Solver

Centrálnym konceptom balíčka solver je interface Solver. Solver (riešič) predstavuje entitu, ktorá je zodpovedná za riešenie optimalizačného problému optimalizačnou metódou, teda aplikovaním optimalizačného kroku optimalizačnej metódy až do určitej doby. Optimalizačná metóda teda nie je vnímaná ako riešiteľ optimalizačného problému, len ako predpis definujúci koncepty a postupnosť krokov na jeho riešenie. Entitami zodpovednými za samotnú aplikáciu týchto konceptov a krokov na konkrétny problém sú implementácie rozhrania Solver.

Funkciu rozhrania Solver si vysvetlíme na jeho jednoduchej implementácii, prítomnej v balíčku solver, s názvom BasicSolver. BasicSolver je riešič, ktorý stelesňuje jednoduchý optimalizačný proces znázornený na obrázku 17.

30

Obrázok 15: Hlavné koncepty v projekte solver

Obrázok 16: Základný koncept - Solver

5.Riešenie

Implementácie metód rozhrania Solver v triede BasicSolver mapujú na jednotlivé aktivity v procese riešenia optimalizačného problému.

Zahájenie procesu (aktivita 1) je implementovaná v metóde BasicSolver#init(Function, OptimizationMethod). V tejto metóde prebehne inicializácia optimalizačnej metódy, teda volanie OptimizationMethod#init(ObjectiveFunction). Spôsob rozšírenia objektu typu Function na objekt typu ObjectiveFunction, ktorý je parametrom inicializácie optimalizačnej metódy, úzko súvisí s jeho funkciou a bude opísaný v odstavci venovanom rozhraniu ObjectiveFunction. Nasleduje získavanie ukončovacích podmienok poskytovaných optimalizačnou metódou, ktoré sú používané v metóde BasicSolver#solve() na kontrolu stavu optimalizácie.

Metóda BasicSolver#solve() obaľuje aktivity 2 a 3 spolu s rozhodovaním o ukončení optimalizácie. Kontrola ukončovacích podmienok sa deje na dvoch úrovniach: na úrovni metódy a na úrovni systému. Ukončenie optimalizačného procesu totiž môžu spôsobiť dva druhy ukončovacích podmienok:

podmienky optimalizačnej metódy

dodatočné (tzv. systémové) podmienky

Samotný BasicSolver obsahuje jednu systémovú ukončovaciu podmienku, ktorá vyvolá prerušenie optimalizačného procesu pri dosiahnutí maximálneho počtu optimalizačných krokov. Zabezpečuje tak, že sa optimalizačný proces skončí po určitom čase (definovanom počtom optimalizačných krokov). Ďalším príkladom systémovej ukončovacej podmienky môže byť interná podmienka inej implementácie rozhrania Solver s názvom TimeoutSolver. Táto implementácia je len dekorátorom (Decorator pattern ako je popísaný v [20] kapitola 15) akejkoľvek inej implementácie rozhrania Solver. Dynamicky tak pridáva iným riešičom možnosť ukončiť optimalizačný proces ak presiahne určitú nastaviteľnú maximálnu dobu behu. Ukončenie optimalizačného procesu z dôvodu vypršania časového limitu je signalizované systémovou ukončovacou podmienkou pridávanou TimeoutSolver-om. Vďaka metóde Solver#addSystemStopCondition(StopCondition) je každý solver schopný poňať externé ukončovacie podmienky, ktoré predstavujú podmienky kladené na beh optimalizačného procesu prostredím, v ktorom optimalizácia prebieha.

Pripravovanie výsledkov optimalizačného procesu, ktoré pozostávajú z nájdeného riešenia, štatistík a splnených ukončovacích podmienok prebieha v metóde BasicSolver#getResults(). Tieto výsledky sú prezentované ako objekty typu

31

Obrázok 17: BasicSolver - proces riešenia

5.Riešenie

OptimizationResults.

ObjectiveFunction

ObjectiveFunction je rozšírením rozhrania Function o všetky ostatné rozhrania spojené s funkciami. Optimalizačné metódy komunikujú s týmto rozhraním namiesto rozhrania Function. To umožňuje tvorcom funkcií implementovať len tie rozhrania, ktoré potrebujú a zároveň tvorcom optimalizačných metód volať na funkcii metódy všetkých rozhraní aj keď ich tá nemusí implementovať všetky. Základnou implementáciou tohto rozhrania dodávanou v balíčku solver je BaseObjectiveFunction.

BaseObjectiveFunction v sebe spája tri návrhové vzory: Decorator, Strategy a NullObject[20]. Dekorátor je umožňuje obaliť a analyzovať pôvodnú funkciu:

// konštruktor analyzujúci dekorovanú funkciupublic BaseObjectiveFunction(Function function) { this.function = function; this.statistics = Statistics.newInstance();

if (function instanceof FunctionGradient) { hasAnalyticalGradient = true; gradient = (FunctionGradient) function; }

if (function instanceof FunctionHessian) { hasAnalyticalHessian = true; hessian = (FunctionHessian) function; }

if(function instanceof FunctionBounds) { bounds = (FunctionBounds) function;

32

Obrázok 18: Základný koncept - výsledok optimalizácie

Obrázok 19: BaseObjectiveFunction

5.Riešenie

isFunctionBound = true; }}

Na základe tejto analýzy vie BaseObjectiveFunction či môže volania svojich metód bezpečne posielať na pôvodnú funkciu alebo či sú potrebné dodatočné operácie.

Návrhový vzor stratégia (Strategy) využíva BaseObjectiveFunction pri vyhodnocovaní gradientu a hessianu pôvodnej funkcie. Funkcia nemusí mať (implementovaný) analytický gradient resp. hessian. BaseObjectiveFunction dodáva možnosť vyhodnocovať gradient resp. hessian numericky. Nastaviť spôsob (stratégiu) numerického výpočtu gradientu resp. hessianu funkcie je možné pomocou metód BaseObjectiveFunction#setNumericalGradient(NumericalGradient) a BaseObjectiveFunction#setNumericalHessian(NumericalHessian).

Obrázok 20 ukazuje ako vďaka vzoru dekorátor volanie funkcie ObjectiveFunction#gradientAt() v sebe v skutočnosti skrýva aktualizáciu štatistík (vyhodnocovanie funkcie StatisticsBuilder#incrementGradientAt()), vrátenie objektu Gradient z pôvodnej funkcie, ak funkcia poskytuje analytický gradient, alebo vrátenie objektu Gradient spočítaním numerického gradientu zvolenou stratégiou (cez rozhranie NumericalGradient), ak pôvodná funkcia analytický gradient neposkytuje.

Návrhového vzoru NullObject je využité v implementáciách metód rozhrania FunctionBounds:

public double[] getMinimum() { if(isFunctionBound) { return bounds.getMinimum(); }

// NullObject – vrátenie neutrálnej hodnoty v prípade funkcie s // neobmedzeným definičným oborom double[] minimum = new double[function.getDimension()]; Arrays.fill(minimum, Double.MIN_VALUE); return minimum;}

Spoločne tieto opatrenia dovoľujú optimalizačným metódam volať na inštanciách BaseObjectiveFunction metódy všetkých rozhraní spojených s definíciou funkcie aj keď

33

Obrázok 20: Použitie návrhových vzorov dekorátor a stratégia v BaseObjectiveFunction

5.Riešenie

ich pôvodná funkcia nedefinuje. Návratové hodnoty neexistujúcich metód pritom poskytujú relevantné informácie.

Štatistiky

BaseObjectiveFunction sa okrem dopĺňania neexistujúcich implementácií metód stará aj o zber štatistík. Štatistikami v tomto prípade myslíme počet vyhodnocovaní optimalizačnej funkcie. Konkrétne sa jedná o počty vyhodnocovaní metód Function#valueAt(), FunctionGradient#gradientAt() a FunctionHessian#hessianAt() počas optimalizačného procesu. Vyhodnocovanie hodnoty, gradientu či hessianu funkcie v určitom bode môže byť náročná operácia. Ak optimalizačný proces trvá príliš dlho, tieto štatistiky môžu byť jednou s užitočných informácií pri zisťovaní prečo tomu tak je.

Objekty triedy Statistics sú nemenné. Je to výhodou nie len v multi-vláknovej komunikácii, ale dodáva im to aj určitú dôveryhodnosť. Dáta štatistík teda nie je možné pozmeniť bez zmeny inštancie a držiteľ takého objektu si môže byť istý, že mu ho nikto v zákulisí nezmení. Jeden vedľajší efekt, ktorý so sebou prinášajú nemenné objekty je fakt, že pre každú novú hodnotu nemenného objektu (v tomto prípade štatistík) je potrebný nový objekt.

Pre zjednodušenie tvorby objektov štatistík sme implementovali Builder pattern[15] – návrhový vzor staviteľ.

Predchádzajúci obrázok ukazuje, že BaseObjectiveFunction nekomunikuje s objektami typu Statistics, ale ich staviteľom StatisticsBuilder, ktorý si vytvorí vo svojom konštruktore. Objekty typu Statistics sú vytvárané na požiadanie volaním metódy StatisticsBuilder#build(). Momentálny staviteľ štatistík je len sada jednoduchých

34

Obrázok 21: Základný koncept - Štatistiky

Obrázok 22: Vytváranie a zber štatistík

5.Riešenie

čítačov, no v budúcnosti môžu štatistiky nabrať omnoho väčších rozmerov. Builder pattern vtedy pomôže udržať zložitosť tvorby štatistík na minime.

5.5.3. ExperimentExperimentovanie je proces, v ktorom nás zaujímajú nie len výsledky optimalizačného procesu, ale aj jeho priebeh a jeho vizuálna reprezentácia. Projekt experiment v sebe spája viaceré koncepty z predchádzajúcich projektov za účelom prezentácie procesu optimalizácie a jeho výsledkov užívateľom (teda vizuálne) v multi-vláknovom prostredí. Hlavným balíčkom projektu experiment je cz.cvut.felk.cig.jcool.experiment.

Centrálnym konceptom tohto balíčka, ako ukazuje obrázok, je ExperimentRunner. Je to rozhranie, ktoré v sebe skrýva zodpovednosť za životný cyklus experimentov, vizualizáciu medzivýsledkov a záznam celého experimentu. Pred tým, než si toto rozhranie a jeho základnú implementáciu BasicExperimentRunner predstavíme, musíme si povedať niečo o tom ako fungujú vizualizácie, ale hlavne zdroj vizualizovaných dát, ktorým sú telemetrie.

Telemetrie

Médiom, ktorým telemetrie komunikujú sme sa zaoberali v kapitole 5.5.1, v ktorej sme si povedali, že optimalizačné metódy, ale aj iné objekty, komunikujú v prostredí JCool so svojím okolím pomocou nemenných objektov implementujúcich rozhranie Telemetry<T>. Telemetrie súžia na externalizáciu interných informácií komponent bez možnosti ich pozmenenia druhou stranou. Preto musia sú nemenné (immutable), aby hodnoverne reprezentovali aktuálny stav informácií v komponente, ktorá ich vyprodukovala – v takzvanom producentovi. A ukázali sme si tri implementácie tohto rozhrania z balíčka core. Každá optimalizačná metóda je zároveň producentom jednej z týchto telemetrií, ako ilustruje Obrázok 13 na strane 27. Telemetrií sa v JCool nachádza viac. Napríklad každý riešič je zdrojom tzv. synchronizácie (Obrázok 16 strana 30). Synchronizácia je telemetria obsahujúca číslo posledného dokončeného optimalizačného kroku a riešič ňou informuje zainteresovaných o tom v ako kroku sa momentálne nachádza. Iteration je ďalšia špeciálna telemetria obaľujúca rôzne druhy telemetrií spolu s informáciou o kroku, v ktorom boli

35

Obrázok 23: Hlavné koncepty v projekte experiment

5.Riešenie

vyprodukované. Každý objekt, ktorý chce telemetriu produkovať, to musí dať najavo implementovaním rozhrania Producer<? extends Telemetry>. A každý konzument telemetrie (teda objekt, ktorý sa zaujíma o určitý druh telemetrie) musí implementovať rozhranie Consumer<? extends Telemetry>.

Načo je toto všetko potrebné? Je to nutné pre korektné fungovanie experimentu. Experiment sám o sebe môže bežať vo viacerých vlákna, v grafickom užívateľskom rozhraní či dokonca na rôznych počítačoch. Počas behu experimentu optimalizačné metódy a riešiče informujú o svojom aktuálnom stave. Postupnosť týchto stavov je zhromažďovaná, ukladaná a prípadne distribuovaná vizualizáciám počas behu experimentu. Vytváranie telemetrie môže byť náročná operácia a vytvorená hodnota nemusí byť v multi-vláknovom prostredí spracovaná (nedostatok času alebo úmyselné vypustenie cyklu), preto sa vytvorenie hodnoty odkladá až na poslednú chvíľu. Konzument nie je upovedomený konkrétnou hodnotou, ale len odkazom na producenta (Consumer#notifyOf(Producer)), ktorý túto hodnotu vie vyprodukovať (Producer#getValue()). To dáva konzumentovi možnosť rozhodnúť sa či danú hodnotu odoberie hneď alebo až v inom čase. Vždy však dostane informáciu o dostupnosti novej

36

Obrázok 25: Príklady druhov komunikácie

Obrázok 24: Producent - Konzument

5.Riešenie

hodnoty.

Obrázok 25 ukazuje ako príklad štyri druhy komunikácií, ktoré môžu prebiehať (a aj prebiehajú) medzi optimalizačnou metódou a vizualizáciou. Buffer (vyrovnávacia pamäť) je akýmsi mediátorom medzi týmito dvoma komponentami a môže dodávať zaujímavé vlastnosti. Buffer implementuje zároveň rozhranie Producer aj Consumer (na obrázku je zobrazený len ako konzument telemetrií optimalizačnej metódy).

1. Ignorovanie (segment ignore) – vizualizácia ako konzument telemetrie dostane notifikáciu o novej hodnote telemetrie od optimalizačnej metódy skrz buffer. Telemetria sa vôbec nevytvára.

2. Synchrónny odber hodnoty (segment synchronous) – pri obdržaní notifikácie o novej telemetrii si ju vizualizácia okamžite vyzdvihne. Pri volaní Producer#getValue() sa telemetria vytvorí.

3. Asynchrónny odber hodnoty (segment asynchronous) – pri obdržaní notifikácie o novej hodnote sa jej odber naplánuje na určitý čas v budúcnosti. Telemetria je vytvorená až v tej dobe.

4. Zapamätaná hodnota (segment buffered) – hodnota je synchrónne odobraná vyrovnávacou pamäťou a ako producent hodnoty sa potom hlási namiesto optimalizačnej metódy vyrovnávacia pamäť. To môže byť užitočné v prípade, že sa hodnota telemetrie optimalizačnej metódy nemení tak často ako je odoberaná vizualizáciou (vizualizáciami).

Ak si predstavíme, že každý z objektov znázornených na predchádzajúcom obrázku existuje v inom výpočetnom vlákne, je potreba thread safe komunikície (napríklad použitím immutable objektov) zjavná.

Vizualizácie

Možnosť vizualizovať nie len výsledok práce optimalizačnej metódy, ale dokonca jej vnútorné chovanie je mocným nástrojom ich skúmania. Vizualizácie spolu s telemetriami sú nástroje práve na takéto pozorovanie. Vizualizácie sú objekty, ktoré konzumujú telemetrie prichádzajúce z optimalizačných metód a prezentujú ich vizuálne užívateľom.

Nijakým spôsobom sa neviažu na optimalizačnú metódu, aj keď je rozumné predpokladať, že vysoko špecializované optimalizačné metódy si budú vyžadovať vlastné, na mieru šité vizualizácie. Jediné na čo sa vizualizácia viaže je druh telemetrie. Vizualizácia cez metódu TelemetryVisualization#getAcceptableType() definuje aký typ telemetrie požaduje. O novej hodnote telemetrie tohto typu bude upovedomená volaním metódy notifyOf(Producer). Preto je jednou vizualizáciou možné zobrazovať rôzne druhy optimalizačných metód ak produkujú rovnakú telemetriu. Zaujímavosťou je, že vizualizácia nedostáva telemetriu priamo, ale dostáva ju obalenú v Iteration telemetrii. Aj keď

37

Obrázok 26: Základný koncept - Vizualizácia

5.Riešenie

optimalizačná metóda produkuje len obyčajnú telemetriu, vizualizácia dostáva obohatené informácie, napríklad o číslo iterácie, v ktorej bola táto telemetria vyprodukovaná. V nasledujúcej kapitole si predstavíme zopár vizualizácií, ktoré sú implementované v platforme JCool.

Experiment

Teraz, keď už vieme čo sú to telemetrie a vizualizácie, si môžeme predstaviť samotný priebeh experimentu. O každý beh experimentu sa starajú implementácie rozhrania ExperimentRunner (Obrázok 23). Medzi ich úlohy patrí:

správna inicializácia riešičov, optimalizačných metód a vizualizácií

distribúcia telemetrií medzi producentmi a konzumentmi

záznam priebehu optimalizácie (zber postupnosti telemetrií optimalizačných metód)

spustenie a správa priebehu experimentu

prezentácia výslednej správy experimentu vo forme objektov ExperimentRun

Základnou implementáciou tohto rozhrania prítomnou v balíčku experiment je BasicExperimentRunner rozširujúci tzv. skeletálnu implementáciu rozhrania ExperimentRunner. Rozhrania nesmú poskytovať implementácie ich metód, používanie rozhraní na definíciu typov nám však nezabraňuje poskytnúť asistenciu tvorcom nových implementácií. Je možné kombinovať žiadúce vlastnosti rozhraní a abstraktných tried poskytovaním takzvaných abstraktných skeletálnych implementácií[15] pre každé netriviálne rozhranie, ktoré poskytujeme. Rozhranie stále definuje typ, no skeletálna implementácia odoberá všetku prácu z ich implementácie. Podľa konvencie sú skeletálne implementácie pomenované pridaním slova Abstract pred názov rozhrania, ktoré implementujú[15]. Teda v našom prípade skeletálna implementácia rozhrania ExperimentRunner má názov AbstractExperimentRunner.

38

Obrázok 27: BasicExperimentRunner - ekosystém

5.Riešenie

BasicExperimentRunner je implementácia rozhrania ExperimentRunner. Spravuje beh experimentu definovaného zvolením funkcie, optimalizačnej metódy a riešiča. Akceptuje vizualizácie schopné zobrazovať telemetriu produkovanú práve zvolenou optimalizačnou metódou. Správa sa podľa stavového automatu popísaného na obrázku 28, pričom do stavu pripravený prejde, až keď sú funkcia, metóda a riešič zadefinované. Samotný beh experimentu sa spustí volaním metódy ExperimentRunner#statExperiment(). BasicExperimentRunner spúšťa optimalizačný proces v samostatnom výpočetnom vlákne. Na vytvorenie a spravovanie tohto vlákna používa sadu nástrojov z balíčka java.util.concurrent prítomných v Jave od verzie 5, konkrétne executor framework ([21] kapitola 6.2). Metóda ExperimentRunner#statExperiment() vráti okamžite a nečaká na ukončenie optimalizačného procesu. Ten prebieha vo vlastnom vlákne spravovanom ExecutorService. Výsledná hodnota (ešte nedokončeného) optimalizačného procesu sa uloží do premennej runningExperiment, ktorá je typu Future<ExperimentRunBuilder>.

public void startExperiment() { final ExperimentRunBuilder builder = ExperimentRun.newInstance(); final List<TelemetryVisualization<? extends Telemetry>> visualizations; lock.lock(); // uzamknutie kritickej časti try { builder.setFunction(currentExperiment.getFunction()); builder.setMethod(currentExperiment.getMethod()); builder.setSolver(currentExperiment.getSolver()); visualizations = new ArrayList<TelemetryVisualization<? Extends Telemetry>>(currentVisualizations); } finally { lock.unlock(); // odomknutie kritickej časti }... // vytváranie spojov medzi optimalizačnou metódou, vizualizáciami // ExperimentRunBuilder-om... // inicializácia vizualizácií... // inicializácia riešiča experiment.getSolver().init(experiment.getFunction(), experiment.getMethod());

// spustenie optimalizačného procesu vo vlastnom vlákne // vlákno je spravované es - inštanciou ExecutorService runningExperiment = es.submit(new Callable<ExperimentRunBuilder>() { public ExperimentRunBuilder call() throws Exception { setState(State.RUNNING); experiment.getSolver().solve(); setState(State.FINISHED); return builder; } });}

Počas behu experimentu je stav BasicExperimentRunner-u nastavený na running a po jeho skončení sa nastaví na finished. Až v stave finished je možné odobrať výsledok experimentu, bez blokovania, volaním metódy ExperimentRunner#getExperimentResults(). Výpočetné vlákno, ktoré zavolá túto metódu počas stavu running, je pozastavené a čaká na dokončenie experimentu. Kritické oblasti, ako je prístup ku premennej currentExperiment a zoznamu vizualizácií musia byť synchronizované. Určité úseky metód BasicExperimentRunner-u sú

39

5.Riešenie

preto obalené uzamknutým blokom try-finally.

Ešte pred samotným spustením optimalizácie BasicExperimentRunner zabezpečí distribúciu telemetrií od optimalizačnej metódy a riešiča do vybraných vizualizácií a ExperimentRunBuilder-u obalením týchto komponent vrstvou agregujúcich a filtrujúcich producentov a konzumentov telemetrií.

ExperimentRunBuilder

Triedy ExperimentRun a ExperimentRunBuilder boli vytvárané podľa vzoru tried Statistics a StatisticsBuilder (kapitola 5.5.2.) . ExperimentRunBuilder zabezpečuje jednoduché vytváranie záznamu priebehu celého experimentu pomocou Builder patternu rovnako ako v porovnaní jednoduchší StatisticsBuilder. Udržiava v sebe nie len nastavenie experimentu a jeho výsledky, ale aj záznam jeho priebehu (sled telemetrií v čase). Ako ukazuje obrázok 27 ExperimentRunBuilder je konzument zoznamu telemetrií. Tento zoznam v sebe v každej iterácii obsahuje zoznam aktuálnych telemetrií. Po ukončení experimentu je zavolaním ExperimentRunBuilder#build() možné vybudovať nemenný obraz priebehu celého experimentu.

StatisticalRunner

StatisticalRunner je jednoduchým dekorátorom BasicExperimentRunner-u, ktorý pripravený experiment spustí preddefinovaný počet krát a namiesto výsledkov jedného experimentu, prezentuje súhrnné štatistické výsledky všetkých behov.

5.5.4. BenchmarkProjekt benchmark slúži ako kontainer pre implementácie štandardných optimalizačných funkcií, používaných na testovanie výkonnosti optimalizačných metód. Tento projekt je dodávaný ako doplnok platformy JCool. V súčasnej dobe sa v tomto projekte nachádzajú implementácie štyroch funkcií.

40

Obrázok 28: Stavy experimentu

5.Riešenie

Rosenbrockova funkcia – f x , y =1−x2100 y−x22

(http://www.wolframalpha.com/input/?i=(x%2B2*y-7)^2%2B(2*x%2By-5)^2)Obsahuje jedno globálne minimum v bode (0,0) s hodnotou 1.

Boothova funkcia – f x , y =x2y−722x y−52

(http://mathworld.wolfram.com/RosenbrockFunction.html)Obsahuje jedno globálne minimum v bode (1,3) o hodnote 0.

Levyho funkcia číslo 3 – ∑1

5

cosi1 xi ∑1

5

cos j1 y j

V rozpätí −10≤x , y≤10 obsahuje okolo 760 lokálnych minim a 18 globálnych minim s hodnotou -176.542.

41

Obrázok 30: Rosenbrockova funkcia

Obrázok 29: Boothova funkcia

Obrázok 31: Funkcia Levy číslo 3

5.Riešenie

Levyho funkcia číslo 5 –

∑1

5

cosi1 xi ∑1

5

cos j1 y j x1.425132 y0.800322

V rozpätí −10≤x , y≤10 obsahuje okolo 760 lokálnych minim a jedno globálne minimum v bode (-1.3068,-1.4248) s hodnotou -176.1375.

5.5.5. UIProjekt užívateľského prostredia, UI (User Interface), je tvárou platformy JCool. Platforma JCool obsahuje dva druhy užívateľských rozhraní:

Grafické užívateľské rozhranie (GUI) – grafickú aplikáciu založenú na framework-och Swing a Spring.

Headless – takzvané bezhlavé rozhranie, bez grafickej nadstavby ovládané z príkazového riadku za pomocu frameworku commons-cli.

Grafické rozgranie obsahuje nástroje na konzistentnú konfiguráciu rôznych komponent spojených s experimentmi, tri testovacie metódy a štyri základné vizualizácie. V tejto kapitole si ich predstavíme.

BeanConfigurations

Chovanie komponent spojených s optimalizačným procesom (inštancie rozhraní OptimizationMethod, StopCondition, Solver, TelemetryVisualization či ExperimentRunner) väčšinou závisí na mnohých parametroch a práve nastavovanie týchto parametrov je podstatou experimentovania. Pri tvorbe konfiguračných rozhraní týchto komponent hrajú úlohu dva faktory:

konfiguračné rozhranie je špecifické komponente, to znamená musí byť vytvárané tvorcom komponenty

každý tvorca má vlastný prístup k dizajnu konfiguračného užívateľského rozhrania

Jednoduché a hlavne konzistentné užívateľské rozhranie má však mnoho výhod od jednoduchého používania, ľahkého zoznamovania sa s novými funkciami či prechodom na vyššie verzie projektu.

Projekt BeanConfigurations bol vytvorený v snahe udržať konfiguračné užívateľské rozhrania všetkých komponent konzistentnými a zároveň v snahe minimalizovať prácu tvorcov komponent pri ich vytváraní. Podstatou riešenia problému tvorby konzistentných rozhraní, v BeanConfigurations, je nevytvárať tieto rozhranie vôbec. A nechať si ich vytvoriť

42

Obrázok 32: Funkcia Levy číslo 5

5.Riešenie

automaticky. Tvorca svoju komponentu a jej parametre len označí špeciálnymi anotáciami12 a o zvyšok sa postará framework BeanConfigurations. Ako príklad môže uvedieme časť implementácie SADEMethod, v ktorej sme zvýraznili anotácie, ktoré sú cez BeanConfigurations preložená do užívateľského rozhrania.

@Component(name="SADE genetic algorithm")public class SADEMethod implements OptimizationMethod {

@Property(name="Pool rate", description="Determines the size of the + + pool.") @Range(from=1, to=Integer.MAX_VALUE) private int poolRate = 10;

@Property(name="Radioactivity", description="The probability of the + + MUTATION.") @Range(from=0.0, to=1.0) private double radioactivity = 0.1; @Property(name="Local radioactivity", description="The probability of+ + the LOCAL_MUTATION.") @Range(from=0.0, to=1.0) private double localRadioactivity = 0.1;

@Property(name="Mutation rate", description="Determines the amount of+ + MUTATION.") @Range(from=0.0, to=10.0) private double mutationRate = 0.5;

@Property(name="Mutagen rate", description="Determines the amount of + + LOCAL_MUTATION.") @Range(from=0.0, to=1000.0) private double mutagenRate = 400.0;

@Property(name="DE rate") @Range(from=0.0, to=10.0) private double deRate = 0.3;...

Výsledné užívateľské rozhranie je možné nájsť aj v samotnej platforme JCool. Nasledujúci obrázok ukazuje konfiguračné užívateľské rozhranie SADEMethod v podobe tabuľky parametrov a ich hodnôt vygenerované automaticky framework-om BeanConfigurations.

12 Annotations (anotácie) – sú v jazyku Java špeciálnou formou syntaktických metadát.

43

Obrázok 33: SADEMethod - konfiguračný panel (generovaný)

5.Riešenie

Konfiguračné rozhrania generované BeanConfigurations majú mnoho tvárí a používajú sa v platforme JCool nie len na konfiguráciu jednotlivých komponent (Obrázok 34 číslo 1), ale aj nastavovanie experimentu (Obrázok 34 číslo 2) či výber vizualizácií (Obrázok 34 číslo 3).

Testovacie optimalizačné metódy

Platforma JCool v sebe momentálne obsahuje tri testovacie optimalizačné metódy spolu so štyrmi testovacími funkciami z projektu benchmark. Každou s týchto metód je možné optimalizovať každú z funkcií. To nám dáva 12 rôznych konštalácii experimentov. Ak sa k tomu pridá fakt, že optimalizačné metódy majú v sebe množstvo parametrov (viď Obrázok28), je už teraz možné pri platforme JCool stráviť celý deň experimentovaním (nepočítajúc nastavenia vizualizácií). Platforma obsahuje tieto optimalizačné metódy:

Metóda najstrmejšieho zostupu (Steepest descent method)

Metóda združených smerov (Conjugate gradient method)

SADE algoritmus

Princípy funkcie týchto metód boli popísané v kapitole 2.3.

44

Obrázok 34: Využitie BeanConfigurations v platforme JCool

5.Riešenie

Implementácie vizualizácií

Rôzne optimalizačné metódy pracujú s rôznymi vnútornými reprezentáciami optimalizačného procesu, preto produkujú rôzne druhy telemetrií a tie sú vizualizované rôznymi vizualizáciami. Napríklad metódy Steepest descent a Conjugate gradient prehľadávajú funkciu v každom kroku len v jednom bode, ale metóda SADE ich naraz používa niekoľko. V platforme JCool sa momentálne nachádzajú tieto štyri vizualizácie:

Aktuálna hodnota – vizualizácia vývoja optimalizovanej veličiny počas jednotlivých optimalizačných krokov. Pracuje so všetkými druhmi optimalizačných metód.

45

Obrázok 35: Vizualizácia - aktuálna hodnota

5.Riešenie

Jediný bod – vizualizácia, ktorá prezentuje postupnosť bodov, ktoré navštívila optimalizačná metóda v jednotlivých optimalizačných krokoch. Táto postupnosť je prezentovaná pred farebným pozadím, ktoré reprezentuje funkčné hodnoty v danom mieste. Farebné spektrum je počítané na základe momentálne viditeľných funkčných hodnôt. Vysoké funkčné hodnoty sú predstavovaný farbami blízkymi červenej časti farebného spektra a naopak nízke hodnoty farbami siahajúcimi do fialovej časti spektra. Táto vizualizácia je schopná zapamätať si až štyri behy (aj rôznych) optimalizačných metód na jedinej funkcii a prezentovať ich súčasne.

46

Obrázok 36: Vizualizácia - jediný bod

5.Riešenie

Viaceré body – modifikácia jednobodovej vizualizácie pre metódy pracujúce s množinou bodov.

Základná telemetria – je to jediná vždy prítomná vizualizácia. Nie je ju možné vypnúť, iba skryť. Nachádza sa v ľavom hornom rohu panela vizualizácií a informuje o dĺžke trvania experimentu, počte vykonaných iterácií, terajšej hodnote a doteraz najlepšej nájdenej hodnote optimalizovanej veličiny.

47

Obrázok 37: Vizualizácia - viacero bodov

Obrázok 38: Vizualizácia - základná telemetria

5.Riešenie

5.6. DistribúciaJCool zatiaľ nie je samostatným projektom na servery SourceForge a jeho zdrojové kódy sú prístupné v Subversion úložisku (na servery SourceForge) projektu FAKE GAME pod adresárom jcool.http://sourceforge.net/projects/fakegame/

Aktuálne binárne distribúcie jednotlivých podprojektov sú dostupné aj v internej Maven repository zriadenej na servery neuron.http://neuron.felk.cvut.cz:8080/artifactory/repo

Na pridanie JCool framework ako závislosti v akomkoľvek Maven projekte je potrebné v pom.xml definovať projekt solver medzi závislosťami:

<dependency> <groupId>cz.cvut.felk.cig</groupId> <artifactId>jcool-solver</artifactId> <version>1.0-SNAPSHOT</version></dependency>

Kým je JCool v pre-release verzii (verzia pred vydaním), nie je dostupný v centrálnej Maven repository. Preto je potrebné v pom.xml definovať aj naše interné úložisko Maven artefaktov.

<repositories> <repository> <id>neuron</id> <url>http://neuron.felk.cvut.cz:8080/artifactory/repo</url> <snapshots> <enabled>false</enabled> </snapshots> </repository> <repository> <id>neuron-snapshots</id> <url>http://neuron.felk.cvut.cz:8080/artifactory/snapshots-only</url> <releases> <enabled>false</enabled> </releases> </repository></repositories>

Kým je JCool platforma v pre-release verzii je ju možné jedine vybudovať zo zdrojových kódov. Projekt jcool v sebe definuje assembly13, ktorá vytvorí súbor s príponou zip obsahujúci všetky potrebné knižnice a zároveň aj bat a shell skripty na spustenie užívateľského rozhrania.

13 Maven assembly – je skupina súborov, adresárov a závislostí, ktoré sú zostavené do archívu a distribuované.

48

http://sourceforge.net/projects/fakegame/

http://neuron.felk.cvut.cz:8080/artifactory/repo

6.Zhodnotenie riešenia

6. Zhodnotenie riešenia

Architektúrou, dizajnom a implementáciu sme si predstavili JCool z technického hľadiska. V tejto kapitole si ho predstavíme z užívateľského hľadiska plnením jeho hlavného prípadu použitia, ktorým je experimentovanie. V nasledujúcej kapitole si ukážeme príklad experimentu prevedeného s JCool platformou. A v kapitole po nej si uvedieme zopár výhod používania JCool framework-u pre tvorcov (programátorov) komponent.

6.1. Príklad experimentu

Ukážme si experiment, v ktorom porovnáme výkonnosti a chovanie troch implementácií optimalizačných metód – Steepest descent (SD), Conjugate Gradient (CG) a SADE s rôznymi nastaveniami pri optimalizácii funkcie Levy 5. Funkcia Levy 5 má známe globálne minimum v bode (-1.3068,-1.4248) s hodnotou -176.1375 a veľké množstvo lokálnych minim, ktoré predstavujú prekážky pre optimalizačné metódy. Ako základné metriky výkonnosti použijeme hodnotu nájdeného optima, počet krokov, v ktorých je optimum dosiahnuté (alebo optimalizačný proces ukončený) a základné štatistiky vyhodnocovania funkcie. Predpokladáme, že algoritmus SADE dosiahne najlepšej hodnoty optima, pretože prehľadáva funkciu skupinou bodov narozdiel od SD a CG, ktoré používajú len jeden a tým majú väčšiu šancu na uviaznutie v lokálnom minime. Ďalej predpokladáme, že metóda CG bude kovergovať rýchlejšie k výsledku ako metóda SD. Metódy SD a CG budú pri tom začínať v rovnakom bode, aby sme ich priebehy mohli ľahšie porovnávať.

Nastavenia metód

Na všetky nasledujúce nastavenia poskytuje platforma konfiguračné rozhranie (viď Obrázok33).

SD-1 Štartovací bod (x,y) = (10,-10)

Line search Brent (no derivates)

SD-2 Štartovací bod (x,y) = (10,-10)

Line search Brent (with derivates)

CG-2 Štartovací bod (x,y) = (10,-10)


Update method FLETCHER_REEVES

CG-2 Štartovací bod (x,y) = (10,-10)


Update method FLETCHER_REEVES

49


SADE-1 Pool rate 10

Radioactivity 0.1

Local radioactivity 0.1

Mutation rate 0.5

Mutagen rate 400

DE rate 0.3

SADE-2 Pool rate 10

Radioactivity 0.8

Local radioactivity 0.8

Mutation rate 0.5

Mutagen rate 400

DE rate 0.3

Pre každú z týchto šiestich konfigurácií sme spustili experiment s riešičom obmedzujúcim maximálny počet optimalizačných cyklov na 1000.

Výsledky experimentu

Platforma JCool počas experimentu prezentovala jednotlivé priebehy, zbierala štatistiky a na konci prezentovala výsledky spolu s možnosťou ich uložiť (viď Obrázok 2). V tomto odstavci sú uvedené práve tieto údaje.

50

SD-1 SD-2 CG-1 CG-2 SADE-1 SADE-2Výsledok -18.471330 45.505602 -76.513195 -173.006129 -174.039911 -173.994144

9 2 9 1000 91 73Nájdený bod (-2.79,2.52) (-3.96,-8.88) (-7.78,-1.39) (-1.52,-0.01) (-1.50,-0.00) (-1.50,-0.00)

Metóda Metóda Metóda Systém Metóda MetódaŠtatistikyHodnota 253 146 287 34139 1861 1501Gradient 10 28 10 1002 0 0Hessian 0 0 0 0 0 0

Počet iterácií

Typ ukončujúcejPodmienky

Obrázok 39: Experiment - minimum

-176.130000

-126.130000

-76.130000

-26.130000

23.870000

SD-1SD-2CG-1CG-2SADE-1SADE-2

Obrázok 40: Experiment - počet iterácií

0

100

200

300

400

500

600

700

800

900

1000



Z výsledkov experimentu je hneď jasné, že prvé tri konfigurácie (SD-1, SD-2 a CG-1) veľmi rýchlo uviazli v lokálnych minimách. Narozdiel od nich sa ostatné konfigurácie dostali veľmi blízko globálnemu minimu nielen hodnotou, ale aj pozíciou.

SD-2 sa ukončila hneď po dvoch iteráciách. To svedčí o akomsi internom probléme. Od konfigurácie SD-1 sa líši len v parametre Line search. Je teda možné, že chyba sa nachádza práve v Line search typu Brent (no derivates).

Ďalšou zaujímavosťou je, že konfigurácia CG-2 bola ukončená na systémovej podmienke. Počet jej iterácií dosiahol nami nastavenú maximálnu povolenú hodnotu (1000).

Bližší pohľad na priebehy

Samotné priebehy experimentov nám o konfiguráciách prezrádzajú ešte viac. Pozrime sa na najzaujímavejšie z nich. Nasleduje séria obrázkov zozbieraných počas behu jednotlivých experimentov. Ich farebné a detailnejšie verzie môže čitateľ nájsť v Error: Reference sourcenot found.

Na obrázku 41 je možné vidieť, že konfigurácia SD-1 (začína v vpravo dole) rýchlo uviazla v lokálnom minime (označenom číslom 1). Na obrázku 42 je detailný pohľad na toto minimum.

51

Obrázok 41: SD-1: uviaznutie v lokálnom minime

Obrázok 42: SD-1: uviaznutie v lokálnom minime (detail)


CG-1 uviazla v inom lokálnom minime.

Priebeh konfigurácie CG-2 ukazuje jej špecialitu, ktorou je tzv. reštartovanie, kedy metóda spojených gradientov zabudne všetky predchádzajúce smery. CG-2 tým vyskúšala tri veľmi hlboké minimá (Na obrázku 44 označené číslami 1-3). Na nasledujúcich obrázkoch si tieto úseky experimentu ukážeme.

Obrázok 46 ukazuje ako sa CG-2 pri druhom reštarte dostáva zo špirály, okolo lokálneho minima. Na ďalšom obrázku je číslom 1 označené miesto posledného prehľadaného bodu funkcie Levy 5 konfiguráciu CG-2 pre vypršanie maximálneho počtu iterácií. CG-2 sa opäť dostávala do špirály okolo minima ako aj pred druhým reštartom.

52

Obrázok 43: CG-1: uviaznutie v lokálnom minime

Obrázok 44: CG-2: reštartovanie

Obrázok 45: CG-2: prvý reštart


Predchádzajúce ilustrácie boli vyprodukované vizualizáciou jediného bodu (pretože CG a SD pracujú len s jediným bodom). Nasledujúce vizualizácie boli vyprodukované vizualizáciou mnohých bodov, schopnou zobrazovať stav metódy SADE.

53

Obrázok 46: CG-2: druhý reštart

Obrázok 47: CG-2: vypršanie cyklov


Iterácia: 10, vyhodnotení: 241 Iterácia: 20, vyhodnotení: 441 Iterácia: 30, vyhodnotení: 641

Iterácia: 40, , vyhodnotení: 841 Iterácia: 50, vyhodnotení: 1041 Iterácia: 60, vyhodnotení: 1241


Obrázok 48: SADE-1: priebeh

Konfigurácia SADE-1 rýchlo nájde okolie s najnižšími hodnotami a jedinci populácie sa od vtedy pohybujú zväčša okolo tohto bodu. Naopak jedinci SADE-2 vďaka vysokým hodnotám mutácie (0.8) sú silne zmutovaní pri dlhom pobyte v mutačnej zóne vytvorenej v okolí minima a presúvajú sa v omnoho väčšom okolí nájdeného minima.

54




Iterácia: 73, vyhodnotení: 1501

Obrázok 49: SADE-2: priebeh

Aj krátky pohľad na vizualizácie priebehov experimentov nám vie rýchlo zdôvodniť ich výsledky. Konfigurácie SD dosiahli najhoršie výsledky na metóde Levy 5 kvôli rýchlemu uviaznutiu v lokálnom minime (SD-1) a chybe v algoritme line search (SD-2). Konfigurácie CG síce dosiahli lepších výsledkov ako konfigurácie SD no priebeh CG-2 musel byť dokonca ukončený samotným riešičom. Vizualizácia (obrázky 46 a 45) ukázala, že veľké množstvo iterácií strávi CG-2 krútením sa okolo pozícií minim. Konfigurácie SADE sa chovali robustne a našli hodnoty blízke minimu no potrebovali nato značné množstvo vyhodnocovaní funkcie kvôli tomu, že pracujú v každej iterácii na skupine bodov narozdiel od SD a CG.

55


6.2. Diskusia o frameworku

Platforma JCool je postavená na framework-u JCool spolu s projektom experiment, ktorý poskytuje ďalšiu vrstvu abstrakcie nad optimalizačným procesom. Vďaka dizajnu celého framework-u má implementácia platformy zaujímavý charakter. Pozostáva zo skupiny viacmenej nezávislých konceptov (funkcií, optimalizačných metód, vizualizácií atd.) a správy presne definovaných dátových ciest medzi nimi. Framework poskytuje minimalistické abstrakcie, ktoré sú od seba dostatočne separované. Napríklad metódy prítomné v platforme sú prevzatými implementáciami z projektu GAME. Vďaka malému rozhraniu optimalizačných metód v prostredí JCool bola ich migrácia veľmi jednoduchá. To isté je možné povedať aj o funkciách. Framework sa stará o mnohé veci. Jednou z nich je multi threadová komunikácia. Framework si kvôli tomu od programátor vynucuje používanie určitých tried, no tým definuje komunikačný protokol, ktorý odtieni programátora od multi threadového prostredia platformy JCool. Predávanie telemetrie a vôbec jej vytváranie je odkladané až kým telemetria nie je určite nutná. Zber telemetrie a jej zobrazovanie je totiž v platforme JCool variabilne. To znamená, že ExperimentRunner sa môže rozhodnúť znížiť počet „vzorkov“ telemetrie žiadaných od optimalizačnej metódy. Metóda síce informuje o možnosti odobrania novej telemetrie vždy ak sa pozmení, no toto upozornenie je z jej pohľadu, pri cykloch ignorujúcich zber telemetrie, neblokujúce. To znamená, že môžu existovať cykly nie len bez odberu, ale dokonca bez vytvárania telemetrie. Optimalizačnej metóde tak zostáva viac výpočetného času na optimalizáciu. Otvorená architektúra a využívanie rozhraní pre hlavné koncepty znamená, že celý framework je elastický. Je ho možné naťahovať a formovať na rôznych úrovniach tak, aby čo najviac vyhovoval prostrediu tretích strán.

56

7.Záver

7. Záver

Táto práca sa venovala popisom a vývojom systému na spojitú optimalizáciu, ktorý má pomáhať odhaľovať vnútorné chovanie optimalizačných metód na rôznych optimalizačných problémoch. JCool (Java COntinuous Optimization Library), výsledok tohto snaženia, je open source projekt flexibilného framework-u a nad týmto framework-om vystavanej platformy na testovanie a introspekciu optimalizačných metód.

JCool má dve hlavné časti: platformu a framework. Otvorenosť architektúry a dizajnu JCool-u, ktorá je zabezpečená použitím moderných technológií, nástrojov a návrhových vzorov, je snahou pootvoriť užívateľom svet optimalizačných problémov a algoritmov. JCool neslúži len koncovým užívateľom, ale taktiež tvorcom optimalizačných metód a softvérovým vývojárom hľadajúcim jednoduchý spôsob riešenia optimalizačných problémov rôznorodými metódami vo svojich programoch. Práve im je určený framework JCool, ktorého hlavným cieľom je čo najjednoduchšie popísať základné koncepty optimalizácie. Uľahčovaním práce pri tvorbe nových alebo adaptácii existujúcich optimalizačných problémov a algoritmov sa snažíme vzbudzovať záujem o problematiku spojitej optimalizácie.

Platforma je vizuálny program, ktorý dovoľuje užívateľom experimentovať s nastavením parametrov optimalizačných metód za účelom odhaľovania ich vplyvu na rôznych problémoch. Konfigurácia mnohých parametrov je neoddeliteľnou súčasťou tohto procesu a preto poskytuje platforma konzistentný spôsob nastavovania parametrov automatickým generovaním sofistikovaných konfiguračných rozhraní. Budovaním na konceptoch telemetrie a vizualizácií obsiahnutých vo frameworku JCool je platforma schopná používať rôzne vizualizície s rôznymi optimalizačnými metódami. Práve vizuálnou prezentáciou vnútorného chovania umožňuje užívateľom spoznávať vhodnosť optimalizačných metód na konkrétne optimalizačné problémy.

Primárnym cieľom JCool-u je umožniť lepšie preskúmať rôznorodú množinu optimalizačných metód používaných pri generovaní induktívnych modelov softvéru GAME. Dúfame však, že sa nám podarí vybudovať úspešný projekt, ktorý bude pomáhať užívateľom prenikať do tajov optimalizácie.

57

58

8.Budúcnosť projektu

8. Budúcnosť projektu

V blízkej budúcnosti by mala pribudnúť špeciálna implementácia rozhrania ExperimentRunner tvz. ReplayRunner. Spolu s ňou pribudne aj užívateľské rozhranie pre „prehrávanie“ uložených experimentov. Budeme sa snažiť zapojiť viacerých ľudí do nových implementácie jednotlivých konceptov a na základe ich vstupov rozšírime bázu poskytovaných funkcií a optimalizačných metód a doladíme základné rozhrania.

Platforma JCool sa stane súčasťou projektu Meta-Learning and Meta-Optimization, ktorého cieľom je aplikácia znalostí získaných pri výskume meta-learning-u na meta-optimalizáciu. V tomto projekte sa bude musieť adaptovať na systematickú kombináciu optimalizačných metód počas riešenia jedného optimalizačného problému.

Projekt JCool sa momentálne dostáva do fáze alfa, teda interného, testovania.Z infraštrukturálneho hľadiska chceme mať, do doby prvej release verzie, vybudovanú stabilnú projektovú infraštruktúru. Konkrétne:

samostatný projekt na servery SourceForge

kontinuálnu integráciu s použitím napríklad serveru Apache Continuum

projektové stránky s aktuálnymi informáciami z reportovacích pluginov Maven-u

Pre vzbudenie záujmu o JCool framework a platformu by bolo zaujímavou možnosťou

vybudovanie služby dostupnej cez internet umožňujúcej otestovať implementácie optimalizačných metód na štandardnej na určitej štandardnej sade optimalizačných problémov na dedikovaných serveroch. Užívateľ by dodal službe svoju implementáciu a služba by previedla určitú štandardnú sadu štatistických a ukážkových experimentov. Výsledky tohto testovania by si užívateľ mohol neskôr prezrieť „prehrať“ na svojom lokálnom počítači.

59

60

9.Referencie

9. Referencie

[01] Optimization (mathematics), http://en.wikipedia.org/wiki/Optimization_(mathematics),

2009

[02] Přírodou inspirované metody optimalizující modely pro vytěžování znalostí, Šnorek M.,

Kordík P., České vysoké učení technické, 2007

[03] Quasi-Newton method, http://en.wikipedia.org/wiki/Quasi-Newton_method, 2009

[04] Method of Steepest Descent,

http://mathworld.wolfram.com/MethodofSteepestDescent.html,

[05] Conjugate Gradient Method,

http://mathworld.wolfram.com/ConjugateGradientMethod.html, 1994

[06] Particle swarm optimization, http://en.wikipedia.org/wiki/Particle_Swarm_Optimization,

2009

[07] Ant colony optimization, http://en.wikipedia.org/wiki/Ant_colony_optimization, 2009

[08] Global Optimization Algorithms – Theory and Application, Thomas Weise, 2008

[09] Object-Oriented Modeling with OptimJ, http://www.ateji.com/optimj.html, 2008

[10] The MOSEK optimization tools manual, http://www.mosek.com/fileadmin/products/5_0/

tools/doc/html/tools/index.html?id=2, 2009

[11] Knitro User’s Manual, www.ziena.com, 2009

[12] Optimization Toolbox™ 4 User’s Guide, www.mathworks.com, 2009

[13] OAT: The Optimization Algorithm Toolkit, Jason Brownlee, 2007

[14] Simple Interface for Global Optimization Algorithms, http://www.sigoa.org/, 2006

[15] Effective Java (2nd Edition), Joshua Bloch, 2008

[16] Designing Interfaces: Patterns for Effective Interaction Design, Jenifer Tidwell, 2005

[17] Patterns of Enterprise Application Architecture, Martin Fowler, David Rice, Matthew

Foemmel, Edward Hieatt, Robert Mee, Randy Stafford, 2002

[18] Maven: The Definitive Guide, Tim O'Brien, John Casey, Brian Fox, Bruce Snyder, Jason

Van Zyl, Eric Redmond, 2009

[19] Version Control with Subversion, Ben Collins-Sussman, Brian W. Fitzpatrick, C. Michael

Pilato, 2004

[20] Design Patterns Explained, Alan Shalloway, James Trott, 2001

[21] Java Concurrency in Practice, Brian Goetz, Tim Peierls, Joshua Bloch, Joseph Bowbeer,

David Holmes, Doug Lea, 2006

61

9.Referencie

[22] No free lunch theorems for optimization. Evolutionary Computation, D.H. Wolpert and

W.G. Macready, 1997

[23] Fully Automated Knowledge Extraction using Group of Adaptive Models Evolution,

Pavel Krdík,2006

62

Dodatok A – Ilustrácie vo farbe


63

Obrázok 50: Platforma JCool (farebne)

Obrázok 51: Platforma JCool - popis užívateľského rozhrania (farebne)


64

Obrázok 52: Platforma JCool - priblíženie telemetrie (farebne)

Obrázok 53: Platforma JCool - ukážka vizualizácie (farebne)


65

Obrázok 54: Využitie BeanConfigurations v platforme JCool (farebne)

Obrázok 55: Vizualizácia - jediný bod (farebne)


66

Obrázok 56: Vizualizácia - viacero bodov (farebne)

Obrázok 57: Experiment – minimum (farebne)

-176.130000

-126.130000

-76.130000

-26.130000

23.870000


Obrázok 58: Experiment - počet iterácií (farebne)

0

100

200

300

400

500

600

700

800

900

1000



67

Obrázok 59: SD-1: uviaznutie v lokálnom minime (farebne)

Obrázok 60: SD-1: uviaznutie v lokálnom minime (detail) (farebne)


68

Obrázok 62: CG-2: reštartovanie (farebne)

Obrázok 61: CG-1: uviaznutie v lokálnom minime (farebne)


69

Obrázok 63: CG-2: prvý reštart (farebne)

Obrázok 64: CG-2: druhý reštart (farebne)


70

Obrázok 65: CG-2: vypršanie cyklov (farebne)



Iterácia: 40, , vyhodnotení: 841 Iterácia: 50, vyhodnotení: 1041 Iterácia: 60, vyhodnotení: 1241


Obrázok 66: SADE-1: priebeh (farebne)

71




Iterácia: 73, vyhodnotení: 1501

Obrázok 67: SADE-2: priebeh (farebne)

72

Dodatok B – Obsah priloženého CD

Dodatok B – Obsah priloženého CD

Binárna distribúciaVerzia distribúcieAdresár so spustiteľnými súbormishell script na spustenie platformy JCoolbat script na spustenie platformy JCoolHlavný súbor platformy JCoolĎalšie knižnice vyžadované platformouJavaDoc

Výsledky experimentu z kapitoly 6.1.Súbor s odkazmi na obsahAko spustiť platformuZdrojové kódy JCool

Text tejto práce vo formáte pdf

73

Date post:	12-Sep-2019
Category:	Documents
Upload:	others
View:	6 times
Download:	0 times

Knihovna pro spojitou optimalizaci - FAKE GAME...

Documents