Heuristické grafické metody hledání globálních extrémů

XXVI. ASR '2001 Seminar, Instruments and Control, Ostrava, April 26 - 27, 2001

Paper 26

Heuristické grafické metody hledání globálních extrémů HODÁL, Jaroslav Ing.

UAI FSI VUT v Brně, Technická 2 Brno, 616 69

[email protected]

Abstrakt: Tato práce se zabývá vytvořením vizuálního nástroje pro podporu hledání optimálních řešení nelineárních optimalizačních úloh pracujícím v součinnosti se systémem pro řešení optimalizačních úloh GAMS (General Algebraic Modeling System). Zkoumá možnosti zjednodušení ovládání řešícího softwaru pomocí grafického rozhraní propojujícího vizualizační nadstavbu s řešičem. Pojednává o metodách, účinnosti a vhodnosti klasických grafických algoritmů pro vizualizaci a navrhuje jejich vylepšení. Jistá část této práce byla také věnována problematice vytváření syntaktického analyzátoru některých matematických výrazů. Při tvorbě výsledného programu byla v rámci heuristického přístupu k řešení optimalizačních úloh využita vizualizace. Konkrétně ve formě grafického znázornění účelové funkce a omezení kladených na proměnné. Pomocí troj-, resp. dvourozměrných řezů nehledáme přímo optimální body, ale pouze oblasti, v nichž by tyto body mohly ležet. Připojeným klasickým řešičem s lokálně konvergentním algoritmem nalezneme nejbližší lokální extrém. Tato částečně heuristická metoda značně redukuje oproti jiným algoritmům objem nutných výpočtů. Program ve speciálních objektových strukturách uchovává a zpracovává model celé úlohy. Pomocí svých metod provede dekompozici modelu a umožní jeho rychlé grafické zpracování. Podstatná část této práce se zabývá právě vývojem algoritmů pro tyto programové realizace. Propojují se zde poněkud netradičním způsobem tři samostatné obory – klasická nelineární optimalizace, počítačová grafika a syntaktická analýza. Výsledkem je původní vizuální modulový programový systém schopný propojení s souborově komunikujícími řešiči optimalizačních úloh, který může usnadnit práci především u úloh s více než dvěmi proměnnými, přičemž maximální počet proměnných je 27. Program byl otestován na reálných příkladech z inženýrské praxe a potvrdila se jeho využitelnost. Klíčová slova: heuristické metody, nelineární optimalizace, grafika

1 Úvod Dosud chybí snadno dostupné nástroje, které by propojily možnosti vizualizace s kvalitním řešičem do uživatelsky snadno ovladatelného celku. Cílem této práce je vytvoření programového nástroje, který by v součinnosti se systémem pro řešení optimalizačních úloh GAMS pomocí vizualizace vstupů optimalizačních úloh umožňoval snazší hledání lokálních resp. globálních extrémů těchto úloh.

2 Globální optimalizace Vývoj jednotlivých oblastí optimalizace probíhal souběžně, ale byl různě rychlý. V současné době zůstává k dořešení několik důležitých okruhů problémů: -1-

• • • •

lineární programování - řešení velmi rozsáhlých úloh nelineární programování - vhodný zápis úloh nelineárního programování, urychlení řešení a nalezení globálních extrémů kombinatorické úlohy (včetně mnoha úloh celočíselného programování) složité úlohy obsahující náhodnost aj.

Účinné metody nalezení globálních extrémů existují pouze pro úlohy s konvexními funkcemi. Pro řešení úloh konvexního programování lze s výhodou použít lokálně konvergentních algoritmů. Nekonvexní úlohy však mají obecně více lokálních extrémů. Lokálně konvergentní algoritmy dokáží nalézt jen nějaký lokální extrém. Ten nemusí být nutně nejbližší, to zaleží na konkrétním postupu, na němž je algoritmus založen. Obecně nedokáží s určitostí rozhodnout, zda je nalezený extrém také extrémem globálním. Takové rozhodnutí úzce souvisí s pojmem konvexnosti úlohy. Přesto některé úlohy, které nejsou úlohami konvexního programování lze řešit lokálně konvergentními algoritmy (např. Rosenbrockova funkce, obrázek 3.15, řešení pomocí metody proměnné metriky). Tato situace je však spíše výjimečná a je obtížné zjistit, zda je nalezený lokální extrém i globální. Za globálně konvergentní algoritmy lze považovat pouze algoritmy deterministické a to jen teoreticky. Deterministické algoritmy prohledávají celou množinu přípustných řešení, a proto by měly garantovat nalezení globálního extrému. Při programové realizaci však musíme množinou přípustných řešení postupovat po konečných krocích, protože je principielně nemožné procházet ji kontinuálně. Množství výpočtů by pak bylo samozřejmě nekonečné. Ať bychom nastavili krok, po němž se množinou přípustných řešení postupuje, libovolně malý, vždy existuje možnost, že se účelová funkce chová v některém svém úseku kratším, než je zvolený krok, velmi „divoce“ (např. osciluje s vysokou frekvencí) a algoritmus takové místo přeskočí. Přitom právě tam může hledaný globální extrém být. Vizualizaci lze nejlépe užít v úlohách u nichž s rostoucím počtem proměnných neroste počet lokálních extrémů příliš rychle. Čím složitější je struktura úlohy, tím slabší a nejednoznačnější jsou algoritmy, které lze použít k řešení těchto úloh. Deterministické algoritmy postupují, jak již bylo řečeno, systematicky množinou přípustných řešení. Stochastické algoritmy fungují tak, že se náhodně vybere n bodů z množiny přípustných řešení, v nich se spočte hodnota účelové funkce a vyberou se z nich ty „nejslibnější“, které se využijí jako startovací body pro lokálně konvergentní algoritmy. Stochastické restarty se provádějí obdobně. Klasickým algoritmem nalezneme lokální extrém (výchozí bod), pak vybere z nějakého jeho okolí náhodně jiný bod, který opět použijeme jako startovací pro lokálně konvergentní algoritmus. Nalezenou hodnotu srovnáme s původní a v případě lepšího výsledku jej nastavíme jako výchozí. Heuristické algoritmy již vyžadují znalostní spoluúčast uživatele.

3 Počítačová grafika Je zřejmé, že účelovou funkci n proměnných vystupující v optimalizační úloze lze chápat jako obecnou plochu v n+1 –rozměrném prostoru. Ovšem kvůli omezení lidského vnímání na trojrozměrný prostor má smysl zobrazovat pouze její dvou- resp. trojrozměrné řezy. Dalším vhodným způsobem zobrazení účelové funkce jsou vrstevnicové grafy. Dvourozměrný řez účelové funkce kolmý k osám zafixovaných proměnných je vlastně grafem funkce jedné proměnné. Takovéto grafy jsou celkem snadné na vykreslování, protože není potřeba používat žádné promítání, ale zobrazuje se přímo na rovinu totožnou s rovinou obrazovky. Díky fyzikálním omezením zobrazovacích zařízení znázorňujeme pouze konečný -2-

počet hodnot v diskrétních bodech. Tyto body získáme rozdělením logického intervalu, který zobrazujeme, podle počtu pixelů, které při vykreslení připadají u daného výstupního zařízení (obrazovka, tiskárna) na úsek, na který se tento interval promítne. V případě, že bychom požadovali rychlejší vykreslení, ovšem za cenu snížení přesnosti zobrazení, nepočítali bychom hodnotu v každém dělícím bodě, ale např. jen v každém pátém. Potom bychom obdrželi graf jako lomenou čáru, kde by průmět každého lineárního úsek do směru osy proměnné měl délku 5 pixelů. Narozdíl od dvourozměrných řezů je vytváření trojrozměrných mnohem složitější. Zobrazování prostorových útvarů v rovině se provádí tzv. promítáním. Pro zobrazování je nejdůležitější kolmá axonometrie. Ta se v praxi užívá nejčastěji, protože je nejvíc názorná. Kolmou axonometrií se z hlediska deskriptivní geometrie rozumí promítání na dvě navzájem kosé průmětny. Body prostoru se tedy zobrazují na uspořádané dvojice svých axonometrických obrazů a půdorysů. Pro potřeby počítačové grafiky však vystačíme bez pomocné průmětny. Zobrazení trojrozměrného objektu na obrazovce je vlastně kolmá axonometrie, kdy za axonometrickou průmětnu slouží rovina, v níž leží obrazovka. Protože mozek zpracovává světelné paprsky dopadající přibližně kolmo na kulovou plochu sítnice, bylo by lepší simulovat skutečný vjem například použitím lineární perspektivy (středové promítání na rovinu se středem ve vlastním bodě) s odpovídajícím zorným úhlem, neboť tak lze znázornit i velikost objektu. Tento postup se užívá převážně při znázorňování skutečných předmětů a vyžaduje složitější přepočty souřadnic průmětu každého bodu, a proto vystačíme bez užití perspektivy. V některých případech není nutné, aby objekt byl zobrazen zcela realisticky. Pak lze použít pro znázornění i kosoúhlou axonometrii. Programovat kosoúhlou axonometrii může být jednodušší a můžeme také značně urychlit práci programu, pokud nám nevadí malé zkreslení. Znázorňování funkcí pro matematické účely nevyžaduje nezbytně realističnost, a tak lze kosoúhlou axonometrii s úspěchem použít. Nejjednodušším způsobem znázornění prostorových objektů při programové realizaci znázornění jsou tzv. hranové modely. Zajímat nás bude hlavně konstrukce ploch zadaných ve tvaru z=f(x,y), tedy ve tvaru, v jakém jsou i řezy zadané účelové funkce optimalizační úlohy. Výsledkem cyklického volání výpočtové a vykreslovací procedury přes interval je osnova řezů. Přehozením cyklů získáme osu řezů kolmých na osu x. Z těchto dvou osnov křivek sestrojíme hranový model grafu funkce f(x,y) nad obdélníkem <x1;x2> × ). Algoritmy pro vykreslování hranových modelů jsou celkem rychlé, výsledné obrázky však mají tu nevýhodu, že znázorňované objekty jsou průhledné. To u ploch popsaných složitějšími funkčními předpisy komplikuje orientaci v obrázku. Proto je vhodné znázornit, které části objektu jsou viditelné a které zakryté. Jeden z nejrozšířenějších algoritmů řešících viditelnost je tzv. malířův algoritmus (Painter’s algorithm, Priority list). Princip spočívá v přímém vykreslování ploch na obrazovku, a to v pořadí od nejvzdálenějších po nejbližší vzhledem k pozorovateli. Bližší plochy překryjí vzdálenější a viditelnost je tak vyřešena přirozeným způsobem. Algoritmus je však rychlostně téměř srovnatelný s algoritmem řešícím viditelnost výpočtově. Při realizaci malířova algoritmu však narážíme na dva problémy. Plochy se mohou překrývat dosti složitým způsobem, a proto někdy nelze jednoznačně rozhodnout, která plocha má být kreslena dříve. Viditelnost je pak třeba řešit dosti složitými testy. V případě této práce byl tento problém vyřešen právě využitím zobrazení v kosoúhlé axonometrii se speciálním promítacím úhlem. Druhý problém tkví v tom, že chceme-li, aby později kreslená plocha překryla plochu dříve kreslenou, je třeba každou plochu vyplnit určitou barvou. Standardní vyplňovací procedury nedávají vždy uspokojivé výsledky. Vyžadují totiž zadání barvy, která definuje hranici plochy -3-

a její vnitřní bod. Svírá-li promítaná plocha s promítacím paprskem malý úhel, promítne se do úsečky. V takových případech zcela selhávají. Zde se jevilo jako velmi vhodné pozměnit algoritmus tak, aby šlo využít pokročilejších programátorských technik za pomoci Win32 API. Spojíme každou čtveřici bodů ležících nad obdélníky <xi-1;xi> × uzavřenou křivkou pomocí API procedury Polygon, která je schopna správně obarvit vnitřní body plochy ohraničené zadanými body. Na obrazovce obdržíme systém čtyřúhelníků. V případě, že chceme odlišit pomocí barev i hodnoty funkce, namapujeme si barevný interval na interval hodnot, jichž funkce nabývá na obdélníku <x1;x2> × . Při vykreslování zvolíme reprezentanta (obvykle některý z rohových bodů) každého čtyřúhelníka a podle hodnoty funkce v tomto bodě zvolíme výplňovou barvu z intervalu barev (obrázek 3.10).

Obrázek 3.10 Vrstevnice plochy z=f(x,y) sestrojujeme jako systémy funkcí f(x,y)=C. Nejjednodušší algoritmus pro sestrojování těchto křivek na počítači využívá rozdílu mezi fyzickými a logickými pixely. Křivku f(x,y)=C je možno vykreslit samozřejmě pouze fyzickými pixely. Každý takový pixel je však logicky obdélník o stranách hx a hy (reálná velikost stran závisí na rozměrech uživatelské kreslící plochy). Je zřejmé, že fyzický pixel má být vykreslen právě tehdy, protíná-li křivka hranice tohoto pixelu. Je tedy třeba nastavit kroky hx a hy po nichž postupujeme ve vykreslovacím algoritmu tak, aby logické obdélníky přesně pokrývaly fyzické pixely. Kritériem pro zobrazení fyzického pixelu jsou pak různá znaménka funkce f(x,y) alespoň ve dvou vrcholech obdélníka.

Obrázek 3.12 Prochází-li však křivka pixelem tak, jak je znázorněno na obrázcích 3.13a,b,c, pak toto kritérium selhává, protože znaménko funkce f(x,y) je v každé dvojici sousedících vrcholů -4-

stejné. Pixel pak není vykreslen, i když jej křivka protíná. Chybí-li jen jeden pixel (obrázek 3.13a), nemá to na správnost grafického výstupu téměř vliv. Chová-li se však křivka tak jako na obrázku 3.13b na více pixelech za sebou, je tento nedostatek již značně patrný.

Obrázek 3.13 Protože při kreslení vrstevnicového grafu znázorňujeme systém křivek, algoritmus musí obsahovat navíc jeden cyklus pro proměnnou hodnotu C. Výpočet se tím ale silně zpomaluje. Rychlost algoritmu tak přímo závisí na počtu vrstevnic, které chceme vykreslit. Jde sice o algoritmus nejjednodušší, ale protože na generování větších obrázků se složitějšími funkčními předpisy je potřeba někdy i hodiny, často se používají algoritmy jiné. Konstrukci lze urychlit za cenu poněkud menší přesnosti tak, že na kreslící plochu položíme čtvercovou resp. obdélníkovou síť, přičemž strana čtverce resp. strany obdélníka jsou celočíselnými násobky odpovídajících stran fyzického pixelu. Kreslící plochu neprocházet bod po bodu, ale po těchto čtvercích resp. obdélnících. Testováním znamének funkce f(x,y) ve vrcholech zjišťujeme zda křivka protíná obvod čtverce resp. obdélníka podobně, jako tomu bylo u algoritmu předchozího. Najdeme-li dvě takovéto strany, pak metodou půlení intervalu najdeme průsečíky A, B s obvodem s přesností na jeden pixel. Těmito body pak proložíme úsečku, pomocí níž křivku na tomto čtverci resp. obdélníku interpolujeme. I zde se však projeví nedostatek testovacího kritéria, které je stejné jako u vykreslování po pixelech. Je navíc mnohem zřetelnější, protože se může projevit přerušením křivky na úseku odpovídajícím velikosti jednoho nebo více dílků sítě (obrázek 3.15a). Na srovnávacím obrázku 3.15b je tatáž funkce (Rosenbrockova testovací funkce – 100(x-y2)2+(1-y)2 ) vykreslená po jednotlivých pixelech.

Obrázek 3.15a

Obrázek 3.15 b

-5-

Obrázek 3.15a nevznikl přesně podle algoritmu popsaného v předchozích dvou odstavcích, ale postupem, byl navržen už pro program GENESys. Je kombinací obou popsaných algoritmů. Stejně jako druhý algoritmus, postupuje i tento po větších obdélnících. Pokud pomocí testovacího kritéria zjistí, že křivka protíná některou z hran obdélníka, nehledá průsečíky hran a funkce, ale na celém obdélníku se provede postup stejný jako v prvním algoritmu. Dosahuje tak téměř rychlosti druhého algoritmu při přesnosti, jakou nabízí algoritmus první. Ovšem i zde, kvůli stejnému testovacímu kritériu dochází k nepřesnostem, je-li počet průsečíků některé hrany sudý. Jinou možností, jak algoritmus urychlit nabízí využití obrazové analýzy, konkrétně na speciálně vykreslený dvoubarevný obrázek použijeme vhodný filtr typu horní propust. Ten odfiltruje vše kromě obrysů jednotlivých úseků, což jsou požadované vrstevnice. Nevýhodou algoritmu je, že selhává v oblastech, kde je koncentrace vrstevnic příliš vysoká. Výstup je také celkem nedokonalý z hlediska celistvosti čar, a proto je většinou potřeba použít ještě nějaký algoritmus na zvýraznění těchto čar. Další možností, jak zobrazit hodnoty účelové funkce v řezech je rozlišení hodnot pomocí barev podobně jako se na geografické mapě zobrazují nadmořské výšky. I v tomto případě lze z obrázků pomocí obrazové analýzy (tj. aplikací vhodných filtrů) získat vrstevnice.

4 Softwarové řešení Existuje několik druhů algoritmů. Deterministické, stochastické a heuristické. Možnost využít heuristický přístup k řešení úloh byla donedávna dost omezená a jen málo využívaná, protože pro úlohy s malou dimenzí lze výhodněji použít jiné druhy algoritmů a pro ostatní úlohy by nepomohly ani velmi dobré znalosti o průběhu funkce, hlavně kvůli omezení lidské představivosti na maximálně trojrozměrný prostor. Nyní lze využít v rámci heuristického přístupu k řešení optimalizačních úloh vizualizaci ve formě grafického znázornění účelové funkce a omezení kladených na proměnné. V platnosti sice zůstává omezení těchto zobrazení na troj-, resp. dvourozměrné řezy, nicméně vzhledem k faktu, že pomocí těchto řezů nehledáme přímo optimální body, ale pouze oblasti, v nichž by tyto body mohly ležet, nám takové omezení již tolik nevadí. Můžeme pomocí řezů postupovat po konečných krocích celou množinou přípustných řešení a v oblastech, které se nám jeví jako podezřelé z možné existence lokálního extrému, zvolíme startovací bod, který se předá klasickému řešiči s lokálně konvergentním algoritmem a nechá se již na něm, aby nejbližší lokální extrém nalezl. Pokud hodnota účelové funkce v takto nalezeném bodě splňuje naše požadavky, můžeme jej akceptovat jako suboptimální řešení. Pokud ne, může nám nalezený bod sloužit jako srovnávací bod pro další hledání. Ani tento postup nezaručuje vždy nalezení globálního extrému, ze stejného důvodu jako algoritmus deterministický, ale oproti deterministickým algoritmům je značně redukován objem výpočtů, protože se nemusíme zabývat výpočty v oblastech, které zjevně nějaký výrazný extrém neobsahují. Pro vytvoření programu bylo zvoleno vývojové prostředí Delphi s tím, že většina grafických funkcí je programována přímo ve Win32 API. Celý program je koncipován jako modulový systém, což je uspořádání blízké objektově orientovaným jazykům. Modulová koncepce umožňuje vytvářet samostatné uzavřené bloky programu, určené k provádění jednoho nebo i celé skupiny dílčích úkolů, které od výsledného programu požadujeme. Takovýto modul je nezávislý na ostatních částech programu, se kterými komunikuje pomocí funkcí rozhraní. Díky tomu lze pouhým doplněním dalšího modulu snadno a rychle rozšířit program o nové funkce. -6-

Program GENESys sestává ze čtyř základních modulů. Ke své plné funkčnosti vyžaduje ještě nainstalovanou některou verzi řešiče GAMS. Není-li řešič k dispozici, lze používat grafickou část programu a některé další funkce, které jsou na řešiči nezávislé. Vnitřní strukturu programu GENESys ukazuje obrázek 4.1.

Obrázek 4.1 Uživatelské rozhraní je komunikační vrstva mezi programem a uživatelem postavená na pěti vstupních formulářích. První z nich je ovládací panel. Kontrolními prvky na tomto panelu lze řídit celý program. Další dva formuláře připojené k ovládacímu panelu slouží jednak k zadání účelové funkce, jednak k přidávání, úpravě a odebírání omezení. Existující omezení lze upravovat pomocí editační nabídky, kterou lze vyvolat poklepáním myší na příslušné omezení. Zbývající dva formuláře umožňují nastavit parametry grafického výstupu (rozměry výstupního okna, intervaly zobrazovaných proměnných, dimenzi výstupu, barevné schéma, krok sítě pro 3D zobrazení a některé další doplňkové volby) a parametry prostředí (umístění řešiče v počítači, jazyk prostředí, barva pozadí výstupního okna pro potřeby snímkování a další). Program GENESys je schopen komunikovat s uživatelem ve dvou jazycích – češtině a angličtině – a je snadno rozšiřitelný o další jazykové mutace. Ovládací panel je také vlastníkem objetu Model, který obsahuje veškerá data úlohy zadané uživatelem. Objektová forma těchto informací umožňuje jejich rychlejší předávání mezi jednotlivými procedurami. Protože se je potřeba k těmto datům přistupovat velmi často, znamená to značné zrychlení celého programu a menší paměťové nároky. Objekt Model má také několik metod sloužících ke zpracování vstupů a vyčíslení hodnoty účelové funkce nebo omezení ve zvoleném bodě. Kopie objektu Model se předává každému novému grafickému oknu. Zajišťuje se tak možnost pracovat s několika úlohami najednou.

-7-

Veškeré informace o nastavení programu lze uložit do rozšířeného systémového registru počítače. Podmínkou ke spuštění grafické části programu je zadání alespoň účelové funkce. Není tedy nutné zadávat omezení proměnných. Účelová funkce a omezení jsou primární vstupy programu. Doplňující informace, jako oblast na které nás výsledky zajímají, typ výstupu, volby kroku, barev a další, lze zadat po stisku tlačítka „Grafika“ na ovládacím panelu. Pokud je počet proměnných v účelové funkci větší než je 1 resp. 2 v případě dvourozměrného resp. trojrozměrného řezu či vrstevnicového grafu, pak je před samotným vykreslením ještě realizován dotaz, které proměnné mají být zafixovány, hodnoty těchto zafixovaných proměnných a ve kterých proměnných se bude graf vykreslovat. Kvůli jistým zrychlení práce s proměnnými mohou být jako identifikátory proměnných použity pouze symboly a,b,..,y. Uživatel zatržením políčka u proměnné může zvolit, zda tato proměnná bude zafixovaná, nebo bude použita jako jedna z proměnných v grafu. U zafixovaných proměnných lze vyplnit v editačním poli napravo od identifikátoru proměnné také její hodnotu. Kvůli nedostatku kvalitních nástrojů pro vyčíslování hodnot účelové funkce a omezení bylo do programu nutno vytvořit také tento podprogram, protože musel obsahovat mimo jiné i syntaktický analyzátor. Navíc bylo třeba se zadanými vzorci pracovat na poněkud hlubší úrovni než je obvyklé. Tedy nejen je vyčíslovat v zadaných bodech, ale také převádět je do interpretačního jazyka GAMSu. To znamená mít přístup do vnitřní struktury zpracovaného vzorce, aby ve chvíli jeho vyčíslování byla možnost volby, zda se za jeho jednotlivé části dosadí číselné hodnoty v daném bodě, nebo pouze jejich textový přepis v jiném jazyce. Vzhledem k faktu, že celý program je jakousi nadstavbou řešiče GAMS, podporuje výpočtový podprogram, až na několik výjimek, množinu funkcí podporovaných přímo GAMSem. Výpočtový program provádí tři základní funkce: • zajištění výpočtů hodnot účelové funkce a výrazů v omezeních • interpretaci zadané účelové funkce a omezení • převod funkčních předpisů do jazyka zvoleného řešiče Interpretací zadané účelové funkce a omezení se v tomto případě rozumí zpracování obecných vstupů od uživatele. Program má být schopen přijmout téměř jakýkoli funkční předpis od uživatele ve formě textového řetězce, proto jej musí napřed nějak předzpracovat tak, aby jej pak mohl vhodným způsobem interpretovat. Třetí funkce umožňuje propojit program GENESys s libovolným řešičem, který podporuje formátované vstupy pomocí souboru. Stačí jen doplnit způsob, jakým daný řešič zapisuje určité funkce a jejich parametry. Výpočtový modul pracuje podle schématu, které je shodné jak pro účelovou funkci, tak pro všechna omezení. Celá logika operací prováděných výpočtovým modulem spočívá v tom, že účelová funkce je vždy nuceně zadána ve tvaru z = ϕ (a,..., y ) a libovolné omezení lze vždy převést na tvar 0°(a,..., y ) kde symbol ° značí některý z operátorů <, >, =, ≤ nebo ≥. Proto stačí dále pracovat pouze s jednou stranou rovnice resp. nerovnice. Do instance objektu Model jsou tyto části rovnic a nerovnic uloženy. V případě omezení se ukládá ještě symbol nerovnosti, který v nerovnici vystupuje. Poté je spuštěna metoda „Decompose“ objektu Model. Jejími parametry jsou uložená data. Nejdříve projdou syntaktickým analyzátorem. Syntaktický analyzátor nejprve ověří, zda neobsahují nepovolené znaky a zkontroluje správnost pořadí a počtu závorek. Poté se provede první kontrola syntaxe zaměřená na jednodušší chyby. Následuje další, tentokrát již složitější kontrola syntaxe (vyhodnocení správnosti užití funkcí a proměnných), při které se také získá seznam použitých proměnných. -8-

Po provedení předchozích kroků je činnost syntaktického analyzátoru u konce a lze provést rozklad funkčního předpisu na nejjednodušší substruktury. Postupuje se po úrovních, které jsou dány použitím závorek a elementárních funkcí. Celý postup sestává ze dvou kroků a je demonstrován na příkladu funkce z=abs(sin(x))*(cos(y+2)-exp(x+y)). Jsou nalezeny výrazy, které jsou odděleny operátory +, -, * nebo /. abs(sin(x))*(cos(y+2)-exp(x+y)) ↓ ↓ abs(sin(x)) (cos(y+2)-exp(x+y)) Složitost získaných jednodušších výrazů je snížena (tzn. je-li výraz elementární funkcí, je do paměti uložen příznak, že jde o elementární funkci a o jakou se jedná, a poté je osamostatněn argument této funkce; jde-li o výraz v závorkách, uloží se příznak uzávorkování a závorky jsou odstraněny). Je-li však některý z výrazů přímo proměnná nebo číselná hodnota, větvení se v tomto „směru“ zastaví. V opačném případě se znovu s každým ze zjednodušených výrazů provedou kroky 1 a 2. abs(sin(x)) (cos(y+2)-exp(x+y)) ↓ ↓ sin(x) cos(y+2)-exp(x+y) ↓ ↓ ↓ x cos(y+2) exp(x+y) ↓ ↓ y+2 x+y ↓ ↓ ↓ ↓ y 2 x y V tomto příkladu je takto v pěti úrovních rozložen celý vzorec až na nejjednodušší části do stromu. V této podobě jsou uloženy účelová funkce a všechna omezení v objektu Model. Chceme-li později určit hodnotu funkce v nějakém bodě, zavoláme metodu Evaluate, jejímž parametrem je seznam hodnot proměnných. Metoda postupuje v opačném směru než metoda Decompose. V nejnižších úrovních dosadí za proměnné jejich hodnoty v zadaném bodě. Pak postupuje směrem nahoru a přitom rekonstruuje celý vzorec. V každé úrovni se za argument dosadí hodnota vypočtená nebo dosazená v úrovni nižší. Na nejvyšší úrovni nakonec dostaneme hodnotu funkce. Pokud některá operace vede na bod nespojitosti (dělení nulou, nedefinovaná hodnota), je vyvolána chyba, která se šíří až k místu, odkud vyšel požadavek na výpočet hodnoty funkce. Místo ní je uložen příznak nedefinované hodnoty a při vykreslování je tento bod přeskočen. Pro potřeby řešícího modulu je možné požadovat opětovné sestavení vzorce, tentokrát však v jazyce, který používá pro matematické zápisy zvolený řešič. Místo proměnných nejsou dosazeny hodnoty a výstupem není reálné číslo, ale textový řetězec. Grafický modul je založen na prototypu výstupního okna. Instance prototypu se vytváří ve chvíli, kdy je programu předán korektní požadavek na grafický výstup. Ovládací panel obsahuje seznam všech takto vytvořených grafických oken a slouží k jejich správě. Konkrétní grafický výstup lze obsluhovat pomocí ovládacích prvků umístěných v každém grafickém okně. Ovládací prvky jsou dvojího druhu, hlavní nabídka a panel nástrojů. Panel nástrojů mimo jiné obsahuje i posuvník fixovaných proměnných. Tento nástroj slouží ke změně hodnot zafixovaných proměnných. Pokud je hodnota některé proměnné změněna, zvolený grafický výstup se automaticky aktualizuje. -9-

Výstupní okno obsahuje kromě ovládacích prvků také komponentu Image, která v Delphi obsluhuje fyzické pixely, pomocí vlastnosti Pixels. To je dvourozměrné pole barevných hodnot (nezáporná celá čísla). Při vytváření řezu se opakovaným voláním metody Evaluate objektu Model naplní pole hodnot, které má stejný počet prvků, jako komponenta Image pixelů ve směru zobrazované osy x. Protože počet prvků tohoto pole závisí na uživatelem nastaveném rozměru výstupního okna, bylo vhodnější realizovat ho jako dynamickou strukturu. Dynamické struktury jsou při větších objemech dat mnohem rychlejší a flexibilnější než struktury statické, což přináší další zrychlení výpočtů. Před vykreslením lze zvolit, zda se má rozsah hodnot funkce Z, který je kreslen, automaticky nastavit podle největší a nejmenší hodnoty, které byly obdrženy při výpočtech. Uživatel si může pevně zvolit rozsah hodnot Z podle svých potřeb. Dále může využít nabídku „Kreslit přesahy Z“, která, je-li zvolena, zajistí, že se hodnoty přesahující zvolené meze hodnot Z vykreslí jinou barvou než hodnoty ležící uvnitř těchto mezí a není na ně brán ohled při výpočtu koeficientů zobrazení. Je-li volba vypnutá, nezobrazí se přesahující hodnoty vůbec. Uživatel má při kreslení 3D řezů možnost vybrat si z pěti druhů grafického znázornění monochromatický graf, R-B schéma (barevný přechod mezi červenou a modrou barvou), alternativní schéma (R-B schéma bez mřížky), síť (hranový model plochy bez vyřešené viditelnosti), síť – viditelnost (hranový model plochy s vyřešenou viditelností) Závažným problémem, se kterým se programy pro vizualizaci funkcí musí potýkat je znázorňování funkcí, které mají body nespojitosti nebo nabývají na části svého definičního oboru hodnoty +∞ nebo -∞. Takovéto funkce mohou způsobit dva druhy chyb: • •

Funkce má bod nespojitosti a vykreslovací algoritmus při výpočtech tento bod kvůli zvolenému kroku přeskočí. Počítá však hodnoty v jeho okolí, které se od sebe velmi liší a protože neví, že je mezi nimi bod nespojitosti, spojí je čarou. Používá-li program automatiku rozsahu hodnot funkce, může dojít u stejného druhu funkcí ke znehodnocení výstupního obrázku. Pokud je v některém bodě vypočtena řádově mnohem větší nebo menší hodnota, než je v ostatních bodech, nastaví se interval funkčních hodnot příliš velký a hodnoty ve většině bodů leží jen v úzkém podintervalu, takže se jeví po vykreslení (kromě malého okolí bodu nespojitosti) téměř jako přímka.

Oba druhy chyb jsou odstraněny zavedením položky „Nekonečno“ v nastavení grafického výstupu. Zde lze zvolit hodnotu, která už má být považována za tak blízkou nekonečnu, že se s nekonečnem „ztotožní“. Pomůckou, která nahrazuje v obrázku popis os, je zobrazování hodnoty proměnných a účelové funkce v reálném čase pod kurzorem myši. Pohybuje-li se kurzorem po obrázku, ze souřadnic polohy kurzoru se zpětně vypočtou hodnoty proměnných a provede se výpočet hodnoty. Získaná hodnota účelové funkce je, stejně jako hodnoty proměnných, vepsána do stavového řádku. U trojrozměrných řezů jsou hodnoty proměnných určovány polohou kurzoru myši vůči rastru „pod“ grafem. Řešící modul zajišťuje veškerou komunikaci s externím řešičem tj. předá vstupní hodnoty do překladové části řešícího modulu, kde se vygeneruje překlad účelové funkce a omezení do jazyka řešiče. S jejich využitím se vytvoří kód v jazyce řešiče. Ten se zapíše do souboru s jedinečným jménem. Tuto akci již provádí Správce souborů, který je součástí řešícího modulu. Správce souborů se také postará o jeho spuštění řešiče, počká na dokončení jeho běhu a převezme výsledky optimalizace. Ty pak předá interpretační části řešícího modulu. - 10 -

Pokud bylo nalezeno řešení, program nabídne dotazem „Přejít na nové souřadnice?“ automatickou aktualizaci souřadnic řezu. Pokud je nastavena volba „textový výstup“, zobrazí se vstupy a výsledky také v textové podobě. Protože je uvedený program novým přínosem a je to heuristický nástroj, jsou teprve formulována pravidla a doporučení pro jeho používání. Dále uvedená pravidla byla zformulována jako úvodní na základě zkušeností s řešenou aplikací. Měla by se dále vyvíjet , ale již v této podobě jsou použitelná. • • • • •

vykreslit dvourozměrné řezy účelové funkce kolmé k osám proměnných ve všech osách provedeme starty řešiče z bodů lokálních extrémů dvourozměrných řezů v některých technických problémech může být některá z proměnných dominantní a ovlivňuje pak polohu lokálních extrémů; snažíme se identifikovat takové proměnné vykreslit trojrozměrné řezy, které znázorňují interakce mezi proměnnými (jak jsou svázány) provádět starty z lokálních minim a maxim trojrozměrných řezů

5 Závěr V rámci této práce byl vytvořen původní vizuální programový nástroj pro podporu hledání lokálních resp. globálních extrémů úloh nelineárního programování. Program může usnadnit práci především u úloh s více než dvěmi proměnnými. Pomocí vylepšených grafických algoritmů, jejichž návrh je také součástí této práce, umožňuje kvalitně graficky znázorňovat vstupy optimalizačních úloh. Program byl otestován na reálných příkladech z inženýrské praxe a potvrdila se jeho využitelnost. V teoretické části diplomové práce je také pojednána problematika vytváření syntaktických analyzátorů, jakožto nezbytných součástí počítačových programů sloužících k vyčíslování uživatelských funkčních předpisů. Dále jsou zde shrnuty poznatky z optimalizace týkající se hledání globálních extrémů a z počítačové grafiky o metodách vizualizace a klasických i alternativních grafických algoritmech. Možnosti dalšího rozvoje programu spočívají především ve vylepšení syntaktického analyzátoru, umožnění volby úhlu pohledu do uživatelské souřadné soustavy a záměně použité kosoúhlé axonometrie za kolmou. Práce byla zpracována v rámci vědecko-výzkumného záměru CEZ: J22/98: 261100009 Netradiční metody studia komplexních a neurčitých systémů.

6 Použitá literatura KLAPKA J., DVOŘÁK J., POPELA P. 1996. Metody operačního výzkumu. Brno : VUT v Brně, 1996. MARTIŠEK, D. 1999. Počítačová grafika pro matematické inženýry. Brno : VUT v Brně, Brno, 1999. WIRTH, N. 1987. Algoritmy a štruktúry údajov. Bratislava : Alfa Bratislava, 1987. CHARAMZA, P. a kol. 1993. Modelovací systém GAMS. Praha : MFF UK Praha, 1993. BROOKE, A., KENDRICK, D., MEERAUS, A. 1996. Release 2.25 GAMS a user’s guide. Dennvers : Boyd & Fraser publishing company Dennvers Massachusetts, 1992-96 GAMS – installation and system notes. 1996. Washington DC. : GAMS development corporation Washington DC, 1992-96 HADLEY, G. 1964. Nonlinear and Dynamic Programming. Addison-Wesley,1964 - 11 -

BAZARAA, M.S., SHERALI, H.D., SHETTY, C.M. 1993. Nonlinear programing: Theory and Algorithms. 2nd ed. New York : John Wiley & Sons, New York, 1993. RAVINDRAN, A., PHILLIPS, D.T., SOLBERG, J.J. 1987. Operations Research: Principles and Practice. 2nd ed. NewYork : John Wiley & Sons New York, 1987. WINSTON, W.L. 1991. Introduction to Operations Research: Applications and Algorithms. Boston : PWS-Kent Publishing Co. Boston, 1991. TAHA, H.A. 1992. Operations Research: An Introduction. 5th ed. New York : Macmillan New York, 1992.

- 12 -