VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ BRNO UNIVERSITY OF TECHNOLOGY
FAKULTA STROJNÍHO INŽENÝRSTVÍ ÚSTAV AUTOMATIZACE A INFORMATIKY FACULTY OF MECHANICAL ENGINEERING INSTITUTE OF AUTOMATION AND COMPUTER SCIENCE
EVOLUČNÍ ALGORITMY - MATLAB GATE TOOLBOX EVOLUTIONARY ALGORITHMS – MATLAB GATE TOOLBOX
DIPLOMOVÁ PRÁCE DIPLOMA THESIS
AUTOR PRÁCE
BC. JAN MINAŘÍK
AUTHOR
VEDOUCÍ PRÁCE SUPERVISOR
BRNO 2007
ING. RADOMIL MATOUŠEK, PH.D.
2
3
ZADÁNÍ ZÁVĚREČNÉ PRÁCE
4
5
LICENČNÍ SMLOUVA POSKYTOVANÁ K VÝKONU PRÁVA UŽÍT ŠKOLNÍ DÍLO uzavřená mezi smluvními stranami: 1. Pan/paní Jméno a příjmení: Jan Minařík Bytem: Blatnička 161, 696 71 Narozen/a (datum a místo): 17.12.1979, Zlín (dále jen „autor“) a 2. Vysoké učení technické v Brně Fakulta strojního inženýrství se sídlem Technická 2896/2, 616 69 Brno jejímž jménem jedná na základě písemného pověření děkanem fakulty: Doc. RNDr. Ing. Miloš Šeda, Ph.D., ředitel ÚAI
(dále jen „nabyvatel“)
LICENČNÍ SMLOUVA Čl. 1 Specifikace školního díla 1. Předmětem této smlouvy je vysokoškolská kvalifikační práce (VŠKP): □ disertační práce □ P diplomová práce □ bakalářská práce □ jiná práce, jejíž druh je specifikován jako ................................................. (dále jen VŠKP nebo dílo) Název VŠKP:
Evoluční algoritmy – Matlab GATE toolbox
Vedoucí/ školitel VŠKP:
Ing. Radomil Matoušek, PhD.
Ústav:
Ústav Automatizace a Informatiky
Datum obhajoby VŠKP: VŠKP odevzdal autor nabyvateli v*: □ P tištěné formě
*
–
počet exemplářů: 2
□ P elektronické formě –
počet exemplářů: 3
hodící se zaškrtněte
6
2. Autor prohlašuje, že vytvořil samostatnou vlastní tvůrčí činností dílo shora popsané a specifikované. Autor dále prohlašuje, že při zpracovávání díla se sám nedostal do rozporu s autorským zákonem a předpisy souvisejícími a že je dílo dílem původním. 3. Dílo je chráněno jako dílo dle autorského zákona v platném znění. 4. Autor potvrzuje, že listinná a elektronická verze díla je identická. Článek 2 Udělení licenčního oprávnění 1
Autor touto smlouvou poskytuje nabyvateli oprávnění (licenci) k výkonu práva uvedené dílo nevýdělečně užít, archivovat a zpřístupnit ke studijním, výukovým a výzkumným účelům včetně pořizovaní výpisů, opisů a rozmnoženin. 2 Licence je poskytována celosvětově, pro celou dobu trvání autorských a majetkových práv k dílu. 3 Autor souhlasí se zveřejněním díla v databázi přístupné v mezinárodní síti □ P ihned po uzavření této smlouvy □ 1 rok po uzavření této smlouvy □ 3 roky po uzavření této smlouvy □ 5 let po uzavření této smlouvy □ 10 let po uzavření této smlouvy (z důvodu utajení v něm obsažených informací) 4 Nevýdělečné zveřejňování díla nabyvatelem v souladu s ustanovením § 47b zákona č. 111/ 1998 Sb., v platném znění, nevyžaduje licenci a nabyvatel je k němu povinen a oprávněn ze zákona. Článek 3 Závěrečná ustanovení
1. Smlouva je sepsána ve třech vyhotoveních s platností originálu, přičemž po jednom vyhotovení obdrží autor a nabyvatel, další vyhotovení je vloženo do VŠKP. 2. Vztahy mezi smluvními stranami vzniklé a neupravené touto smlouvou se řídí autorským zákonem, občanským zákoníkem, vysokoškolským zákonem, zákonem o archivnictví, v platném znění a popř. dalšími právními předpisy. 3. Licenční smlouva byla uzavřena na základě svobodné a pravé vůle smluvních stran, s plným porozuměním jejímu textu i důsledkům, nikoliv v tísni a za nápadně nevýhodných podmínek. 4. Licenční smlouva nabývá platnosti a účinnosti dnem jejího podpisu oběma smluvními stranami.
V Brně dne: 23.5.2007
…………………………………… Nabyvatel
…………………………………… Autor
7
ABSTRAKT Tato diplomová práce se zabývá problematikou řešení optimalizačních úloh za pomocí vybraných heuristických metod. Hlavním cílem bylo zdokonalení již existujícího Matlab GATE toolboxu pomocí externí dynamicky linkované knihovny DLL napsané v programovacím jazyce C++. Tato knihovna přebírá většinu stěžejních funkcí GATE toolboxu a veškeré kritické operace nadále probíhají v ní. GATE-DLL toolbox je rozšířen také o univerzální rozhraní XML, které umožňuje ukládání a uživatelskou editaci důležitého nastavení. Do služeb DLL knihovny byla také přidána podpora pro distribuované výpočty. V teoretické části práce jsou stručně popsány principy metod použitých při praktické realizaci. Jedná se o horolezecký algoritmus HCA a genetický algoritmus GA. V praktické části je nastíněna celková koncepce knihovny DLL, popis jejího rozhraní, implementace použitých algoritmů a rozhraní XML. Ke konci kapitoly je vysvětlen systém komunikace klient – server pro distribuované výpočty. Závěr práce je věnován praktickým testům vylepšeného GATE-DLL toolboxu, srovnání rychlosti, schopnosti nalezení optimálního řešení a testování distribuovaných výpočtů.
ABSTRACT This thesis deals with the solution of optimizing problems by means of selected heuristic methods. The main purpose of the work was to improve still existing Matlab GATE toolbox through the use of external dynamic-link library DLL written in the programming language C++. This library takes over most of the pivotal functions of GATE toolbox and performs all the critical operations. In addition, GATE-DLL toolbox is enlarged with the universal interface XML which enables storage and user’s editing of the important setup. The services of the DLL library were supplemented with the support for distributed computing. The section of the thesis dealing with theory describes in brief the principles of methods applied to practical implementation. Respectively hill climbing algorithm HCA and genetic algorithm GA. The practical section outlines the general concept of the DLL library, gives the description of its interface, implementation of applied algorithms and XML interface. The client – server system of communication used for distributed computing is explained at the end of the chapter. The final section deals with practical tests of improved GATE-DLL toolbox, as well as with comparison of the speed, ability of finding the optimal solution and with testing the distributed computing.
KLÍČOVÁ SLOVA Optimalizační problém, optimalizační funkce, horolezecký algoritmus, genetický algoritmus, Matlab, GATE, DLL, C++, XML, klient - server komunikace, distribuované výpočty.
KEYWORDS Optimizing problem, optimizing function, hill climbing algorithm, genetic algorithm, Matlab, GATE, DLL, C++, XML, client - server communication, distributed computing.
8
9
PODĚKOVÁNÍ
Touto cestou bych chtěl poděkovat mému vedoucímu diplomové práce Ing. Radomilu Matouškovi, PhD. za jeho cenné rady a čas, který mi při realizaci této práce věnoval.
10
11
Obsah:
1 2
3
4
5
6
Zadání závěrečné práce................................................................................................... 3 Licenční smlouva............................................................................................................. 5 Abstrakt........................................................................................................................... 7 Poděkování ...................................................................................................................... 9 Seznam použitých zkratek ............................................................................................ 13 Úvod............................................................................................................................... 15 Teoretické základy ........................................................................................................ 17 2.1 Optimalizační problém ............................................................................................... 17 2.2 Heuristické metody .................................................................................................... 18 2.2.1 Horolezecký algoritmus........................................................................................ 18 2.2.2 Genetický algoritmus ........................................................................................... 18 GATE toolbox................................................................................................................ 21 3.1 Koncepce původního GATE toolboxu ........................................................................ 21 3.2 Vylepšení GATE – DLL GATE ................................................................................. 22 3.2.1 Koncepce GATE-DLL ......................................................................................... 22 Implementace ................................................................................................................ 25 4.1 Vnitřní implementace DLL......................................................................................... 25 4.1.1 Optimalizační jádro COptMethod......................................................................... 25 4.1.2 HCA algoritmy..................................................................................................... 28 4.1.3 Genetický algoritmus GA a GA-HC ..................................................................... 30 4.1.4 XML parser.......................................................................................................... 31 4.2 Rozhraní DLL knihovny............................................................................................. 34 4.3 Popis exportních funkcí DLL...................................................................................... 34 4.3.1 Základní funkce.................................................................................................... 34 4.3.2 Výkonné metody .................................................................................................. 36 4.3.3 Funkce pro GA-HC .............................................................................................. 36 4.3.4 Funkce pro kompatibilitu s původním GATE........................................................ 37 4.3.5 Funkce pro podporu XML .................................................................................... 38 4.3.6 Funkce pro podporu distribuovaných výpočtů....................................................... 38 4.3.7 Koeficient „míry pokrytí“ Hammingova prostoru ................................................. 39 4.3.8 Struktura OptParams ............................................................................................ 40 4.4 Propojení DLL se systémem Matlab ........................................................................... 40 4.4.1 Systém GATE-DLL ............................................................................................. 41 4.4.2 Popis hlavní struktury GATE-DLL....................................................................... 41 4.4.3 Popis GATE-DLL funkcí ..................................................................................... 42 4.4.4 Sestavení vektorizované funkce............................................................................ 45 4.5 Systém distribuovaných výpočtů ................................................................................ 46 4.5.1 Struktura master XML souboru ............................................................................ 47 4.5.2 Průběh komunikace: ............................................................................................. 47 4.5.3 Server aplikace..................................................................................................... 48 4.5.4 Popis ovládání server aplikace:............................................................................. 48 4.5.5 Klientská část....................................................................................................... 51 Praktické testy GATE-DLL.......................................................................................... 53 5.1 Testovací funkce F6 ................................................................................................... 53 5.2 Testování rychlosti GATE vs. GATE-DLL................................................................. 54 5.3 Test využití paměti RAM ........................................................................................... 56 5.4 Schopnost nalezení řešení........................................................................................... 57 5.5 Srovnání algoritmů GA a GA-HC............................................................................... 58 5.6 Statistické zobrazení vývoje výpočtů GA.................................................................... 59 5.7 Testování distribuovaných výpočtů............................................................................. 60 Závěr.............................................................................................................................. 63 Seznam literárních zdrojů............................................................................................. 65
12
13
SEZNAM POUŽITÝCH ZKRATEK CPU DLL GA GA-HC HCA HW LAN PC RAM XML
- Central Processing Unit, procesor počítače - Dynamic Linking Library - Genetic Algorithm, genetický algoritmus - Genetický algoritmus s vylepšenou mutací pomocí HCA - Hill Climbing Algorithm, horolezecký algoritmus - Hardware - Local Area Network - Personal Computer - Random Access Memory - eXtended Markup Language
14
15
1
ÚVOD
Cílem této diplomové práce je zdokonalení již existujícího GATE toolboxu, jenž slouží k optimalizaci úloh pomocí implementovaných heuristických metod. GATE toolbox je naprogramován a pracuje v systému Matlab, který se však příliš nehodí k operacím s binárními řetězci dat. GATE obsahuje několik variant horolezeckých algoritmů HCA, genetický algoritmus GA a v neposlední řadě také vylepšený genetický algoritmus GA-HC. Hlavním požadavkem bylo zvýšení rychlosti výpočtů, protože rychlost stávajícího GATE nebyla příliš vysoká. Zároveň bylo požadováno zachování určité kompatibility s původním GATE. Dalšími úkoly bylo navrhnout, implementovat a otestovat univerzální XML rozhraní pro ukládání nastavení GATE toolboxu. Posledním bodem zadání byla realizace a testování distribuovaných výpočtů při řešení složitých optimalizačních problémů. Problém rychlosti výpočtů jsem se rozhodl řešit jako externí dynamicky linkovanou knihovnu DLL, která je připojena k systému Matlab, a veškeré kritické výpočty probíhají v ní. Kompatibilitu s původním GATE řeší několik funkcí, které se starají o export a import binárních dat. Knihovna totiž pracuje zcela autonomně a veškeré datové struktury se uchovávají uvnitř. XML rozhraní umožňuje uložení většiny nastavení do XML souboru, což se hodí např. když chceme ve výpočtu později pokračovat, nebo když provádíme testy se stejným nastavením, atp. Systém distribuovaných výpočtů je řešen netradičně s komunikací pomocí master XML souboru, do kterého serverová aplikace uloží potřebné nastavení. Připojující se klienti si jej načítají a posílají výsledky své činnosti v nadefinovaných intervalech zpět serveru. Ten umožňuje jejích zobrazování, porovnávání a manuální nebo automatické předávání lepších hodnot klientům, kteří se nejlepšímu nalezenému řešením už příliš vzdálili.
16
17
2
TEORETICKÉ ZÁKLADY
V dnešní době se k řešení optimalizačních úloh používá mnoho různých metod a postupů. Vhodnost použití dané metody či algoritmu ovlivňuje mnoho faktorů, jako např. oblast použití, požadovaná přesnost nalezeného řešení, implementační a časová složitost a mnoho dalších. Jak tomu obvykle bývá, většina metod má svoje výhody i nevýhody. Výběr vhodné metody závisí zejména na složitosti dané problematiky, požadované přesnosti získaného řešení, ale také zde hraje nemalou roli otázka časových výpočetních nároků. O metodách řešení optimalizačních problémů již bylo napsáno velmi mnoho, proto se v této kapitole zmíním jen okrajově o metodách, které souvisí s problémem řešeným v této práci. Místo toho se budu věnovat praktické realizaci a testování dosaženého řešení.
2.1
Optimalizační problém
Je charakterizován především účelovou funkcí, omezujícími podmínkami a požadavkem minimalizace nebo maximalizace, dále mohou být stanoveny ještě další speciální podmínky, např. nalezené parametry řešení musí být celočíselného typu. Účelová funkce charakterizuje daný problém a většinou obsahuje více parametrů, které chceme optimalizovat. Úkolem je nalézt její optimum, tj. nalézt minimální nebo maximální hodnotu této funkce. Omezující podmínky udávají, v jakém rozsahu se mohou dané parametry pohybovat. Bývají většinou zadány jako přídavné rovnice, nebo rozpětí hodnot, kterých může daný parametr nabývat. Požadavek minima nebo maxima určuje, jaký extrém hledáme na účelové funkci. Hledáme-li minimum, je třeba nalézt globální minimum účelové funkce v rozsazích, které určují omezující podmínky pro jednotlivé parametry. Pokud hledáme maximum, je tomu naopak. Heuristické metody a algoritmy hledání optima pracují obvykle s diskrétní reprezentací účelové funkce. To znamená, že je nejdříve potřeba takovou funkci převést do tvaru vhodného ke zpracování heuristickými metodami; tento proces nazýváme vzorkování. Ta převede funkci ze spojitého tvaru do tvaru diskrétního. Obvykle se vzorkuje jenom ta část funkce, která nás zajímá (tedy část ohraničená omezujícími podmínkami) a ta se rozdělí na 2n bitů. To umožní algoritmům převést optimalizační problém na bitové řetězce, se kterými obvykle heuristické metody pracují. Vzorkování má ovšem jednu velkou nevýhodu. Dost často se může stát, že se hledané optimum při vzorkování spojité funkce „ztratí“, pokud neleží přímo v bodě, ve kterém se provede diskrétní konverze. Proto většinou nemohou heuristické metody nalézt hledané optimum úplně přesně, ale s přesností pouze omezenou. Čím užší bude kódovací interval a čím více kódujících bitů použijeme, tím větší přesnosti bude možno dosáhnout při hledání optima.
f(x)
kódovací interval
.....................
.......... x
Obr. 1 Provedení vzorkování u spojité funkce mezi hranicemi omezujících podmínek
18
2.2
Heuristické metody
V posledních letech se rok od roku neustále zvyšuje výpočetní síla počítačů, což otevřelo dveře mnoha novým odvětvím. Nový rozmach také nastal ve vývoji a experimentování s heuristickými metodami řešení složitých optimalizačních problémů. Tyto optimalizační metody sice nezaručují nalezení globálního řešení úplně přesně, ale poskytují řešení, které se globálnímu optimu velmi blíží. Výsledné řešení je nalezeno v uspokojivé době a s dostatečnou přesností. Používají se zejména pro optimalizaci mnohaparametrových funkcí, které nabývají mnoha extrémů. 2.2.1
Horolezecký algoritmus
Tento algoritmus je zástupcem jednoduchých heuristických metod. V každém kroku řešení vygeneruje nejbližší okolí v určitém rozsahu a v něm hledá další nejlepší řešení. Nalezené lepší řešení se použije v následujícím kroku jako základ pro generování nového okolí. f(x) I1
I6 x
Obr. 2 Prohledávání okolí HCA algoritmem a uváznutí v lokálním extrému Horolezecký algoritmus má jednu velikou nevýhodu. Jeho prohledávání je totiž závislé na šířce generování nejbližšího okolí. Pokud nastane případ, kdy v cestě prohledávání stojí lokální extrém, může se stát, že se zde algoritmus zastaví. Říkáme, že algoritmus uvázne v lokálním extrému a v tom případě nenajde globální optimum, ale optimum pouze lokální. Vše je patrné z Obr. 2. Ten zachycuje, jak postupuje algoritmus při hledání optimálního řešení a uvázne v lokálním extrému v šestém iteračním kroku. Volba šířky generovaného okolí nám určuje časovou složitost algoritmu. Šířka okolí nemůže být příliš velká, protože by se neúměrně zvedla časová složitost algoritmu. Ukončení výpočtu u horolezeckých algoritmů může nastat např. sledováním hodnot nejlepších řešení. K ukončení dojde tehdy, pokud dva kroky jdoucí po sobě naleznou dvě naprosto stejné hodnoty. Ukončení lze také provést omezením iteračních kroků. 2.2.2
Genetický algoritmus
Genetické algoritmy jsou inspirovány přírodou a Darwinovými zákony přirozeného výběru. Jedinci dané populace nesou informace zakódované pomocí genetických chromozomů. Tyto chromozomy je možno dekódovat a určit, jaké vlastnosti má určitý člen populace. Sledujeme charakteristiky, které jsou důležité pro hodnocení řešeného problému, tedy v případě řešení optimalizačního problému hodnotu účelové funkce. Jedinci s lepšími charakteristikami jsou vybíráni do další generační populace a horší jedinci jsou eliminováni. Genetický algoritmus provede v jedné generaci několik kroků, které mají tři základní, jasně dané cíle – nejlepší jedince vybrat do další generace, vytvořit z nich pomocí křížení potencionálně lepší jedince a v poslední řadě udržovat celkovou populaci dostatečně heterogenní (překonání lokálních extrémů, zefektivnění křížení). Počáteční populace jedinců je obvykle generována náhodně na předem definovaném prostoru možných řešení.
19 Počáteční populace fitness selekce křížení mutace fitness
-
podmínka ukončení + Konec
Obr. 3 Typický průběh genetického algoritmu Jeden iterační krok genetického algoritmu je naznačen na Obr. 3. Počáteční populace je nejdříve ohodnocena, a vzápětí jsou z ní vybráni nejlepší jedinci. Poté je provedeno mezijedincové křížení, které pomáhá vytvářet jedince s potencionálně lepšími vlastnostmi. V závěru iteračního kroku je provedena mutace, jenž má za úkol udržovat celou populaci dostatečně různorodou, aby se pokrylo co nejširší okolí od aktuálně nejlepšího jedince. Základní operátory genetického algoritmu jsou tedy čtyři a to: • fitness – provádí ohodnocení jedinců podle určitého kritéria • selekce – vybírá předem definovaným způsobem jedince do další generace • křížení – výměna genů mezi jedinci, získání potenciálně lepšího • mutace – náhodná změna některých genů v populaci, zachování heterogenity Genetické algoritmy jsou obvykle v počítačích reprezentovány pomocí binárních čísel, ale mohou být řešeny i jinak, záleží na dané implementaci a cílené oblasti použití. Pokud uvažujeme binární kódování, jedinci jsou kódováni binárními řetězci, které představují jejich chromozomy. Ohodnocování může probíhat různými způsoby, např. konverzí binárních řetězců na reálná čísla apod. Křížení pak výměnou bitů mezi jedinci a mutace náhodnou změnou některých bitů v celé populaci. V dnešní době existuje nepřeberné množství variant a typů genetických algoritmů. Liší se způsobem implementace, různými způsoby křížení, mutace a selekce, reprezentací řešeného problému apod. Genetické algoritmy mají v dnešní době velké uplatnění a velmi širokou oblast použití.
20
21
3
GATE TOOLBOX
GATE toolbox je sada optimalizačních funkcí, určených pro heuristickou optimalizaci, patřící do tzv. „soft-computing“ metod. Je napsán a určen pro použití v systému Matlab, což s sebou přináší jisté „výhody“, ale bohužel i nevýhody. Za výhody lze považovat zejména snadnou uživatelskou deklaraci účelové funkce, její grafické zobrazení, zobrazení průběhu optimalizace, dosaženého řešení, apod. Jedna z jeho nevýhod je, jak se později ukázalo, příliš pomalé výpočetní jádro, pokud se snažíme provádět nějaké binární operace. Systém Matlab je sice velmi efektivním nástrojem pro matematické výpočty, avšak naprosto neefektivní, co se týče práce a metod prováděných v čistém binárním kódu. Genetické a horolezecké algoritmy jsou však na binárních operacích a binární reprezentaci postaveny. GATE balík funkcí ve své implementaci obsahuje několik variant horolezeckého algoritmu, genetický algoritmus a rozšířenou verzi genetického algoritmu, kombinujícího výhody GA a HC algoritmů.
3.1
Koncepce původního GATE toolboxu Celá implementace původního GATE toolboxu se dá rozdělit na několik částí: • • • •
definice účelové funkce servisní metody datové struktury sada výkonných metod HCA, GA, GA-HC
Celý původní GATE je implementován v prostředí systému Matlab. Obsahuje několik výkonných HCA algoritmů (HCA5, HCA6, HCA7), genetický algoritmus GA. Varianta horolezeckého algoritmu HCA7 se používá k mutaci v tzv. hybridním genetickém algoritmu GA-HC. GATE toolbox VÝKONNÉ HCA METODY VSTUPY GA-HC
DATOVÁ STRUKTURA GA
VÝKONNÉ GA METODY
SERVISNÍ METODY ÚČELOVÁ FUNKCE
VÝSTUPY
Obr. 4 Blokové schéma původního GATE toolboxu Datová struktura GATE toolboxu je hlavní datová struktura, ve které jsou uchovávána veškerá nastavení, ale i výsledky a průběh celého optimalizačního procesu. Část této struktury definuje uživatel před samotným spuštěním procesu optimalizace. Zadává zde požadavek
22 minimalizace či maximalizace, odkaz na definici účelové funkce, počet parametrů, kolika bity jsou kódovány jednotlivé parametry, typ binárního kódování, aj. Jako servisní metody jsou označovány v GATE toolboxu takové funkce, které jsou nezbytné pro činnost výkonných metod, nebo mají ještě i další pomocné funkce. Účelovou funkci je třeba sestavit jako vektorizovanou Matlab funkci. Musí být napsána tak, aby byla schopna vypočítat matici s parametrovými vektory. Problém celého řešení je, jak jsem již naznačil v úvodu kapitoly, velmi pomalá implementace. Pro systém Matlab je evidentně velký problém, pokud se snažíme provádět nějaké binární operace. Veškeré výpočty zřejmě provádí na hodnotách, které převede na datový typ double. Každá taková hodnota je v paměti počítače zakódována 64 bity, ačkoliv se jedná o binární číslo, které by bylo možno zakódovat pouze v jediném bitu. Proto je práce v binárních operacích dost neefektivní. Více informací a detailní popis struktur a funkcí GATE 2.0 je možno najít v [1].
3.2
Vylepšení GATE – DLL GATE
Počáteční nápad byl použít stávající GATE toolbox a k němu připojit externí dynamicky linkovanou knihovnu DLL, ve které by byly veškeré stěžejní funkce pro práci s binárním kódem. Postupem času jsem však zjistil, že takto postupovat nelze. GATE uchovává binární populaci v matici s prvky typu double. Při každé operaci by se tak musela neustále posílat z Matlabu do DLL velká matice čísel a v zápětí opět matice stejného rozměru zpět do Matlabu, což by značně snižovalo rychlost celé implementace. Rozhodl jsem se vytvořit DLL tak, aby pracovalo interně naprosto autonomně. Veškeré datové struktury jsou uchovávány uvnitř DLL a teprve na požadavek uživatele jsou data (binární populace) odesílána zpět do systému Matlab. Tato koncepce se později ukázala jako velice výhodná a vysoce efektivní z hlediska rychlosti výpočtů. Dále jsem se snažil, aby byl nový GATE-DLL toolbox z větší části kompatibilní s původním toolboxem; aby se postup zadávání optimalizačního problému z hlediska uživatele změnil co možná nejméně. Při inicializačním volání DLL knihovny se jí předá nastavení z původní datové struktury, která zůstává kompatibilní s původním toolboxem. Nový toolbox byl také vylepšen o rozhraní XML, které umožňuje v jakékoliv části výpočtu uložit nastavení do XML datového souboru. Z tohoto XML je možné spustit znovu celý optimalizační proces s uloženými parametry a hodnotami. Načtení parametrů z XML lze provést v jakékoliv části výpočtu, nebo přímo inicializovat nový výpočet pomocí XML souboru. Další věcí, která je v GATE-DLL nová, je podpora pro distribuované výpočty. Umožňuje připojit jakýkoliv GATE-DLL před započetím optimalizačního procesu k serveru, který registruje GATE klienty, umožňuje jejich sledování, automatické předávání lepší hodnoty nalezeného optima horším klientům, apod. Koncepce klient - server je pojata poněkud netradičním způsobem. Komunikace probíhá přes master XML soubor, který zakládá serverová aplikace. Klienti komunikují se serverem prostřednictvím tohoto souboru. 3.2.1
Koncepce GATE-DLL
Jak jsem již zmínil v předchozím odstavci, knihovna DLL zcela nahrazuje většinu funkcí GATE toolboxu a má také vlastní datovou strukturu, ve které uchovává nastavení, binární populaci, hodnocení populace, aktuální vektor, aj. Všechny výpočty pracují s touto interní datovou strukturou, čímž se značně zvyšuje výpočetní síla oproti původně navrhované koncepci volaných funkcí z DLL. Jediné, v čem Matlab zůstává nadále nápomocen výpočtům, je v ohodnocování jedinců pomocí vektorizované účelové funkce. Definice této funkce zůstává (opět z důvodů kompatibility) naprosto stejná s původním GATE.
23
GATE-DLL toolbox ÚČELOVÁ FUNKCE
XML SOUBOR
VSTUPY DLL DATOVÁ STRUKTURA GA
KOMUNIKAČNÍ ROZHRANÍ S MATLABEM
HC1 HC2 HC12
GA
GA-HC
XML PARSER
VÝSTUPY
Obr. 5 Blokové schéma GATE-DLL toolboxu Na Obr. 5 je naznačeno celkové blokové schéma spojení DLL knihovny se systémem Matlab. Jak je ze schématu patrné, veškeré výkonné metody a servisní funkce byly vypuštěny a nové funkce obstarává knihovna DLL. Dále byly implementovány vybrané algoritmy a to: HC1, HC2, HC12, GA a GA-HC. Zachovány byly možnosti původních konverzních metod REAL⇔INT⇔BIN nebo REAL⇔INT⇔GRAY. Komunikační rozhraní tvoří systém vhodně navržených funkcí, který dokáže datové typy a požadavky Matlabu přeložit do tvaru kompatibilního s vnitřními algoritmy DLL knihovny. XML parser je schopen načítat a ukládat nastavení do souboru XML a to jak ve standardním módu, tak i v klient módu (distribuované výpočty).
24
25
4
IMPLEMENTACE
Jak již bylo naznačeno v dřívějších kapitolách, bylo potřeba vytvořit dynamicky linkovanou knihovnu DLL, která by přebrala veškeré stěžejní funkce pro práci s binárním kódem. Volba programovacího jazyka byla od počátku jasná. Programovací jazyk Java byl po předběžných testech rychlosti zcela vyloučen, proto jsem se rozhodl pro objektové C++. Java je sice moderní programovací jazyk, v systému Matlab je velmi dobře podporován, avšak běží (stejně jako sytém Matlab) ve virtuálním stroji, proto jsem ani neočekával přílišné zvýšení rychlosti výpočtů. Ukázalo se, že C++ kód přeložený vhodným kompilátorem dokáže být při složitějších matematických operacích až 4x rychlejší než podobně napsaný zdrojový kód v jazyce Java. Od začátku jsem ještě přesně nevěděl, jak bude finální knihovna vypadat co se týče počtu a odlišnosti algoritmů. Nejdříve jsem psal metody do samostatných zdrojových kódů a chtěl jsem mít ve finálním řešení několik samostatných DLL knihoven (každá metoda optimalizace ve zvláštní knihovně). Nakonec se ukázalo, že algoritmy mají mnoho společného, takže jsem celou knihovnu přepracoval a algoritmy sloučil do jedné DLL knihovny.
4.1
Vnitřní implementace DLL
DLL se skládá z několika celků, naprogramovaných jako samostatné objekty. Jedná se o hlavní jádro COptMethod, metody HCA: CHca1, CHca2, CHca12, genetický algoritmus CGa (obsahuje také modifikaci GA-HC), XML parser CXml, a v poslední řadě také celé DLL exportní rozhraní. DLL knihovna CGa CHca1
Matlab
DLL I/O rozhraní
COptMethod
CHca2
CHca12 CXml
Obr. 6 Vnitřní blokové schéma knihovny DLL V I/O rozhraní DLL knihovny mohou být pouze exportní a importní metody. Jsou uzpůsobeny tak, aby dokázaly obsloužit vstupní a výstupní požadavky všech optimalizačních metod a XML parseru. 4.1.1
Optimalizační jádro COptMethod
Hlavní jádro obsahuje veškeré metody společné pro všechny algoritmy. Je to hlavní objekt, který je předek pro objekty optimalizačních metod HCxx a GA. Obsahuje strukturu pro nastavení parametrů optimalizace, dynamická pole pro binární populaci a její ohodnocení, všechny konverzní metody mezi binárním kódem a reálnými čísly, funkce pro náhodnou inicializaci populace, exportní funkce pro XML nastavení, podporu pro distribuované výpočty a výkonné metody. Výkonné části kódu jsou řešeny virtuálními metodami, protože potomci (konkrétní optimalizační algoritmy) mají tyto metody zcela odlišné.
26 Všechny potřebné struktury a metody ke správné funkci jádra jsou uvedeny na následujícím obrázku: Hlavní datové struktury:
Konverzní metody:
Důležité parametry:
Gray/Bin ⇔ Int ⇔ Real
ActValue
Podpora XML:
1
iParam
sVect
nParam
Save/Load XML, ReinitXMLCore, FreeXMLCore
ActVect
nParam nBitParam nIndi mCode funcOpt funcName iParam sVect
Kompatibilita s GATE: Get/SetBinPool, Get/SetActVect, ExportParams Podpora distrib. výpočtů:
PopArr
Fz
nIndi
AddClient, GetClientStatus Výkonné metody:
nParam ⋅ nBitParam
1
Fitness, Selection, Cross, Mutation, FitnessHC, MutationHC
Obr. 7 Důležité metody a struktury jádra COptMethod Popis důležitých parametrů: nParam nBitParam nIndi mCode funcOpt funcName
- počet parametrů optimalizační úlohy - udává, kolika bity je kódován každý parametr - počet jedinců populace (liší se u jednotlivých metod HCA a GA) - druh použitého kódování chromozomů – binární nebo Grayův kód - požadavek optimalizace – minimum nebo maximum - jméno účelové funkce (Matlab „m“ souboru)
Popis důležitých struktur: PopArr Fz ActVect ActValue iParam sVect
- hlavní binární struktura pro populaci jedinců ( nIndi × nParam ⋅ nBitParam ) - fitness, tedy ohodnocení jedinců ( nIndi × 1 ) - aktuální, nejlepší nalezený jedinec ( 1 × nParam ⋅ nBitParam ) - ohodnocení nejlepšího jedince ( 1×1 ) - rozsahy kódovaných parametrů (omezující podmínky) ( nParam × 2 ) - vektor reálných čísel použitý pro start HCA ( 1 × nParam )
Binární populace jedinců PopArr je řešena jako dvourozměrné dynamické pole typu unsigned char, takže každá binární hodnota je uchovávána v jednobajtové buňce. Toto řešení se mi jevilo jako nejlepší, uvažoval jsem i o implementaci typu „bit na bit“. Ovšem adresace takového pole by byla extrémně složitá a pole by muselo by být „slepeno“ z mnoha např. 32 bitových neznaménkových buněk, musel by se řešit plynulý přechod bitů mezi jednotlivými buňkami, atp. Celá implementace by se zřejmě dosti zpomalila, ovšem za cenu osminásobně menšího obsazení paměti. Vzhledem k tomu, že dnešní počítače jsou vybaveny operační pamětí
27 s velkou kapacitou, zvolil jsem raději rychlejší implementaci, byť za cenu vyššího využití operační paměti. Pole fitness Fz je jednorozměrné dynamické pole typu double. Při každém iteračním kroku do něj systém Matlab ukládá ohodnocení jedinců. ActVect je pole typu unsigned char, ukládá se do něj nejlepší jedinec z populace, ActValue pak ohodnocení nejlepšího jedince. iParam je důležitá vstupní tabulka, jsou zde uloženy rozsahy pro kódování parametrů do reálných čísel (omezující podmínky optimalizačního problému). sVect je vstupní parametr pouze pro algoritmy HCA, pokud uživatel požaduje začátek výpočtu od konkrétních bodů. Je to pole hodnot, které reprezentuje tzv. start vektor. Konverzní metody Gray/Bin ⇔ Int ⇔ Real Optimalizační problém je na začátku obvykle zadáván v podobě reálných čísel. Taktéž ohodnocení jedinců je prováděno na základě účelové funkce, která se pohybuje v prostoru reálných čísel. Ovšem varianta algoritmů HCA a GA implementovaná v GATE potřebuje převést reálná čísla do binární podoby, jelikož provádí operace přímo s binárními řetězci. Je potřeba metod, které převedou reálná čísla do binární formy a zpět. O to se stará sada konverzních metod implementovaných v jádře COptMethod. Jedná se o Gray2Int, Int2Gray, Bin2Int, Int2Bin, Int2Real a Real2Int. Tyto metody jsou základním stavebním kamenem pro správnou funkci všech optimalizačních algoritmů. Převod reálných čísel probíhá následujícím způsobem: reálné číslo se převede pomocí kódovacích rozsahů z tabulky iParam na číslo typu unsigned int64 (Real2Int) a poté na číslo v binárním (Int2Bin) nebo Grayově kódu (Int2Gray), zároveň se bere v potaz, kolika bity je nutno kódovat daný parametr (nBitParam). Int = MaxInt ⋅ Re = Int ⋅
Re − Μin Μax − Μin
Max − Min + Min MaxInt
(1) (2)
Vzorce (1) a (2) udávají převodní vztah pro konverzi mezi reálným a přirozeným číslem. Int je hodnota celočíselného typu a Re je reálné číslo. Min a Max jsou kódovací rozsahy parametrů uvedené v tabulce iParam. MaxInt je číslo, jehož hodnota udává maximální hodnotu pro kódování na nBitParam bitech (3). MaxInt = 2nBitParam
(3)
Převodní metody pro převod z přirozených čísel Int do čísel binárních a zpět fungují tradičním způsobem podle vzorce (4). Int = a0 ⋅ 20 + a1 ⋅ 21 + ... + ai ⋅ 2i + ... + an −1 ⋅ 2 n −1 + an ⋅ 2 n Kde : a0 ...an − bity binárního čísla Bin
(4)
Chromozomy lze také kódovat pomocí Grayova kódování (Int2Gray, Gray2Int). Uvážíme-li, že v Grayově kódu je mezi dvěma libovolnými sousedními čísly změna pouze v jediném bitu, jeví se takové kódování jako výhodnější (změna jednoho bitu v chromozomu způsobí adekvátní změnu v reprezentaci reálného čísla). Převod probíhá nejdříve do binárního kódu a poté se převede do Grayova kódu pomocí následujícího algoritmu: 1) Dvojková číslice přímého binárního kódu s nejvyšší vahou se ponechá beze změny. 2) Každá následující dvojková číslice přímého binárního kódu se invertuje, pokud jí v přímém kódu předchází na vyšší váze jednička.
28 V konverzních metodách jsem nejdříve používal datový typ double, který pracuje s 64bitovou přesností. Reálné číslo je zde uloženo ve formátu plovoucí desetinné čárky jako 52bitová mantisa, 11bitový exponent a 1 bit na znaménko. Reálné číslo potom dostaneme podle vztahu (5). X Re = 10e ⋅ m
Kde : e = exponent, m = mantisa
(5)
Jde o to, že takový datový typ může poskytnout pouze přesnost v omezeném rozsahu. Problémy s přesností v plovoucí desetinné čárce jsou již dlouho známy, více o této problematice pojednává článek [2]. Po pár zkušebních testech jsem dospěl k závěru, že přesnost typu double nedostačuje. Některé kompilátory C++ podporují ještě datový typ long double, který pracuje s 80bitovou rozšířenou přesností. Př.: Provedeme konverzi pomocí funkce Int2Real. Funkce bude pracovat nejprve s přesností typu double, posléze s přesností long double. Konvertujeme na rozsahu 0.1 − 0.8 , simulujeme konverzi na čtyř bitech, tedy rozparcelujeme rozsah na celkem 16 hodnot. Konvertujeme číslo 7. Výsledná hodnota by měla být Re = 0.426 . Výsledky jsou následující: Rdouble = 0.42666666666666675 Rlong double = 0.42666666666666669 Z předchozího příkladu je vidět, že přesnost datového typu long double je o něco vyšší, než v případě datového typu double. Uvážíme-li však, že takových konverzních cyklů probíhá v jednom kroku výpočtu HCA či GA až několik desítek tisíc, je i takové malé zlepšení obrovským úspěchem. Bohužel systém Matlab odmítl komunikovat s knihovnou DLL ve zvýšené 80bitové přesnosti, nakonec jsem tedy vyřešil tento problém následujícím způsobem: konverzní metody pracují interně se zvýšenou 80bitovou přesností, ale vrací reálné číslo pouze v 64bitové přesnosti. Podle pár zkušebních testů měla i taková úprava velice pozitivní vliv na celkové zvýšení přesnosti výsledků. Jelikož maximální velikost přirozeného čísla, které lze ve většině vyšších programovacíh jazyků efektivně uložit, je 64 bitů (datový typ unsigned long long), jsou konverzní metody a tím pádem i všechny optimalizační algoritmy GA a HCA omezeny na maximálně 64 bitovou přesnost na 1 optimalizovaný parametr.
4.1.2
HCA algoritmy
Do implementace knihovny DLL jsem zahrnul tyto HCA algoritmy: HC1, HC2 a HC12. Jedná se o horolezecké algoritmy s reprezentací pomocí binárního kódování. Využil jsem výhod dědičnosti objektů a implementoval je jako potomky jádra COptMethod. Využívají jeho sdílených metod (konverze, XML podpora, fitness, nalezení nejlepšího vektoru v populaci, aj.). Tyto algoritmy mají navíc pouze jednu metodu: generování okolí pro aktuální vektor. Vyřešil jsem ji jako virtuální metodu jádra COptMethod, což umožnilo využití výhod polymorfního objektového programování a tím pádem i velké zjednodušení komunikačního rozhraní DLL knihovny. Jednotlivé algoritmy se od sebe liší pouze šířkou generovaného okolí: • HC1 - generuje šířku okolí se vzdáleností ρ H = 1 od původního řešení • HC2 - generuje šířku okolí se vzdáleností ρ H = 2 od původního řešení • HC12 - generuje šířku okolí se vzdáleností ρ H = 1 a ρ H = 2 od původního řešení
29 ρH =1
ρH = 2
00000
00000
10000 01000 00100 00010 00001
11000 10100 10010 10001 01100 01010 01001 00110 00101 00011
Obr. 8 Příklad generování šířky okolí ρ H = 1 a ρ H = 2 pro nulový vektor Parametry optimalizační úlohy jsou uloženy za sebou v binárním řetězci, ze kterého se následně generuje okolí. Pracuje se s celou délkou řetězce, tedy s parametry uloženými postupně vedle sebe, jak je vidět z následujícího obrázku. iParam
Hodnoty parametrů
[-5.100;5.000] [-5.100;5.000] [-5.100;5.000]
x3=+1.9898039216 x2=+0.9996078431
nParam = 3 nBitparam = 8
x1=+0.4847058824 10000011 10001010 10000101 Aktuální binární vektor
FZ=+0.169896039984621210 Hodnota účelové funkce
Obr. 9 Reprezentace parametrů v binárním řetězci algoritmu HCA Inicializace algoritmů HCA může být provedena dvěma způsoby: buď pomocí startvektoru nebo náhodného vektoru. Při inicializaci startvektorem uživatel zadá požadavek počátečních bodů pro každý parametr. Pro druhý případ se vygeneruje náhodný startvektor. Algoritmy HCA pracují podle následujících kroků: 1) Na začátku je uživatelem zadán startvektor nebo je vygenerován náhodně, který se stává zároveň vektorem aktuálním. 2) Provede se vygenerování dané šířky okolí pro aktuální vektor. 3) Pošle se požadavek na ohodnocení okolí systému Matlab v podobě matice reálných čísel (matice rozměru nInd × nParam ). 4) Systém Matlab ohodnotí vygenerované okolí pomocí vektorizované účelové funkce. 5) Ohodnocené okolí je posláno zpět do knihovny DLL ve formě vektoru reálných čísel a uloží se do dynamického pole Fz. 6) DLL knihovna vyhledá pomocí pole Fz nejlepší binární vektor a ten překopíruje na místo aktuálního vektoru. 7) Pokračuje se znovu bodem 2, ukončení se provádí omezením počtu iteračních cyklů. Algoritmy HC2 a HC12 generují okolí s relativně mnoha řádky matice, zvlášť pokud je potřeba optimalizovat více parametrů s velkým počtem bitů na parametr. Např. při optimalizaci pěti parametrů s 64 bity na parametr generuje HC2 binární matici o rozměru 51360× 320 . Pro optimalizaci více parametrů je proto vhodnější použít nějakou efektivnější metodu, např. genetický algoritmus.
30 4.1.3
Genetický algoritmus GA a GA-HC
Genetický algoritmus zahrnutý v DLL má chromozomy kódovány pomocí binárních řetězců. Ty jsou opět tvořeny parametry v binární reprezentaci poskládanými za sebou. Celý algoritmus je řešen jako potomek jádra COptMethod, výkonné části kódu jsou opět deklarovány jako virtuální metody. Algoritmy GA a GA-HC se od sebe liší pouze typem mutace, GA-HC využívá mutaci s jádrem, které je optimalizováno algoritmy HCA. Velikost populace jedinců a ostatní parametry volí uživatel při inicializaci modelu algoritmu (nIndi, nParam, nBitParam, iParm, mCode, funcOpt, funcName). Popis všech důležitých metod: Selection
- metoda selekce nejlepších jedinců, je řešena turnajovým výběrem, uživatel volí počet jedinců vstupujících do turnaje. Turnaj probíhá tak dlouho, dokud se nenaplní nová populace, tj. nIndikrát. Stará populace 011001011100101001 101001010010110101 011010100111010101 101010100101010101 011100111010111010
Nová populace 101001010010110101 101010100101010101
Obr. 10 Příklad dvou cyklů turnajové selekce ze dvou jedinců Cross
- metoda křížení jedinců, implementovány jsou tři druhy křížení, které volí uživatel: bodové, bodové pouze v parametrech a uniformní. Uživatel volí, kolik procent jedinců z populace bude zkříženo. Bodové křížení 111111 111111 111111 000000 000000 000000
111100 000001 111111 000011 111110 000000
Bodové křížení s respektováním parametrů 111111 111111 111111 000000 000000 000000
111111 000000 111111 000000 111111 000000
Uniformní křížení (swapbits) 111111 111111 111111 000000 000000 000000
110111 111111 101111 001000 000000 010000
Obr. 11 Příklady všech druhů křížení pro dva náhodné body Mutation
- metoda mutace, která je řešena jako náhodná změna určitého počtu bitů v celé populaci, uživatel volí počet mutovaných bitů, nebo kolik procent populace má mutovat. 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000
00000000000000000 00000000000000000 00001000000000000 00000000000000000 00000000000000000
Obr. 12 Mutace náhodného bitu v populaci jedinců
31 MutationHC - metoda mutace pro GA-HC, jedná se o cílenou mutaci několika jader bitů. Ty jsou nejdříve optimalizovány pomocí algoritmu HCA a pro mutaci se použije jádro s nejlepším fitness po aplikaci HCA. Šířku jádra, algoritmus HCA a počet jader v populaci volí uživatel. Pozice jádra v populaci se vybírá náhodně, je možno volit náhodnou nebo náhodnou s respektováním parametrů. Počet jader v populaci může být zadán procentuálně (0-50%) nebo číslem, udávajícím kolik náhodně umístěných jader se bude v populaci vyskytovat. 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000
HC1
best
00001000000000000 00000100000000000 00000010000000000 00000001000000000
00000000000000000 00000000000000000 00000001000000000 00000000000000000 00000000000000000
Obr. 13 MutationHC s optimalizací jádra metodou HC1 Kroky GA jsou následující: 1) Inicializace binární populace jedinců je náhodná. 2) Systému Matlab je poslána k ohodnocení matice reálných čísel, která reprezentuje parametry v populaci jedinců. 3) Ohodnocení jedinců z Matlabu je uloženo do pole Fz. 4) Je provedena selekce s uživatelským nastavením. 5) Jedinci jsou kříženi metodou Cross se zadaným nastavením. 6) Proběhne mutace bitů v populaci podle nastavení. 7) Systému Matlab je poslána k ohodnocení matice reálných čísel, která reprezentuje parametry v populaci jedinců. 8) Ohodnocení jedinců z Matlabu je uloženo do pole Fz. 9) Ukončení algoritmu je provedeno omezením iteračních cyklů. Algoritmus GA-HC se od kroku 6 liší: 6) MutationHC provede optimalizaci jádra pomocí zvoleného algoritmu HCA. 7) Systému Matlab je poslána k ohodnocení matice reálných čísel, která reprezentuje parametry ve vygenerované HCA populaci. 8) Z ohodnocených jedinců HCA populace se vybere nejlepší řešení a vloží se zpět na místo původního chromozomu. 9) Skok na krok 6, dokud se neprovede mutace požadovaného počtu jader. 10) Systému Matlab je poslána k ohodnocení matice reálných čísel, která reprezentuje parametry v populaci jedinců. 11) Ohodnocení jedinců z Matlabu je uloženo do pole Fz. 12) Ukončení algoritmu je provedeno omezením iteračních cyklů. Genetické algoritmy mají proti HCA algoritmům velkou výhodu v tom, že v relativně malé populaci jedinců (obvykle 50-5000) dokáží optimalizovat až několik desítek parametrů. Velikost populace přitom není závislá na počtu parametrů a nastavené bitové přesnosti, ale je volena uživatelem. 4.1.4
XML parser
Tato část kódu nemá s optimalizačními algoritmy příliš mnoho společného, proto jsem ji vytvořil jako samostatný univerzální objekt CXml. Poskytuje podporu pro zápis a načítání klíčů z XML souboru. Zápis a čtení dat ze souboru je řešeno pomocí souborových streamů. Tento objekt je připojen do jádra COptmethod a je využíván při požadavku ukládat či načítat
32 nastavení do/z XML souboru na pevném disku počítače. XML parser je také využit v serverové aplikaci pro podporu distribuovaných výpočtů. Metody, které poskytuje CXml jsou následující: WriteKey AddKey ReadKey DeleteKey ChangeKey
- založení nového XML a zápis nového klíče na konec XML - přidání klíče do XML před ukončovací hlavičku - načtení hodnoty klíče, vrací ji ve tvaru pole znaků - smazání klíče z XML - změna hodnoty zvoleného klíče za hodnotu jiné délky (vyžaduje použití dočasného souboru) ChangeKeyDirect - změna hodnoty zvoleného klíče za hodnotu stejné délky
Struktura zapisovaného souboru je naznačena na Obr. 14. XML byl uložen metodou GA a dále bylo nastaveno: dva optimalizované parametry s přesností 16 bitů na parametr, byla prováděna minimalizace, použito binární kódování chromozomů, optimalizační funkce „f6.m“, velikost populace 500 jedinců, rozsahy kódovaných parametrů na rozsazích − 5;5 a hodnota pro inicializaci generátoru náhodných čísel byla 1179507480. Nejlepší nalezené řešení v době uložení XML bylo 2,3096583170456597 ⋅10 −6 a vítězný chromozom je uložen jako BestVector. Hodnota sVect je zde kvůli kompatibilitě s algoritmy HCA, které zde ukládají hodnotu startovních pozic. <xml>
GA 2 16 min <mCode>BC
f6 500 [-5.000000e+000 +5.000000e+000;-5.000000e+000 +5.000000e+000] <sVect>[+0.000000e+000 +0.000000e+000]
1179507480 +2.3096583170456597e-006 10000000000000000111111111111111
Obr. 14 Struktura uloženého XML souboru I když je soubor exportován z metody HCA, lze jej opět načíst do jiné metody, např. GA. Položka OptMethod zde má pouze informativní charakter. Takové XML rozhraní má mnoho výhod. Uživatel si může podobný sobor XML sestavit sám (pomocí vhodného textového editoru), definovat veškeré parametry zde a následně jej jenom načítat v procesech optimalizovaných pomocí GATE-DLL. Další možností je úprava a editace již existujícího XML, možná změna parametrů, atp. Neposlední výhodou je i to, že v XML je uložena i inicializační hodnota pro generátor náhodných čísel, potom lze libovolný průběh optimalizace zopakovat s naprosto stejným výsledkem. Je ovšem nutno provést stejné nastavení výkonných metod použitého algoritmu (vhodné např. pro účely různého testování, atp.).
33 Popis a formáty jednotlivých položek XML:
Formát, možné hodnoty
Popis
Příklad hodnoty
OptMethod
- Informační hodnota pro identifikaci algoritmu, který byl použit při optimalizaci před uložením XML - Nepovinná položka, je možno vynechat
nParam
- Počet parametrů optimalizační úlohy
nBitParam
- Počet bitů, kolika budou kódovány jednotlivé parametry
mCode
- Typ kódování chromozomů, Grayovo nebo binární
funcOpt
- Požadavek optimalizace, minimum nebo maximum
funcName
- Jméno Matlab „m“ funkce
nIndi rndSeed
iParam
sVect
BestFitness
BestVector
-
Velikost populace jedinců pro GA Nepovinná položka pro HCA Inicializační hodnota pro generátor náhodných čísel Pokud je zadána 0, bude provedena náhodná inicializace
- Rozsahy, na kterých jsou kódovány parametry - Jedná se o matici reálných čísel ve stylu zápisu Matlab [min max;min max; ...] - Co řádek, to parametr - Čísla musí být v exponenciálním tvaru tohoto formátu [+/-][1 číslice].[6 číslic]e[+/-][3 číslice] - Matice startovacích bodů pro HCA algoritmus, pokud požadujeme inicializaci startvektorem - Načítá se pouze pokud je v XML u HCA nastaven rndSeed na hodnotu 0 - Pro algoritmus GA není třeba definovat - Vektor reálných čísel (1 x nParam) - Čísla musí být v exponenciálním tvaru tohoto formátu [+/-][1 číslice].[6 číslic]e[+/-][3 číslice] - Nejlepší nalezená hodnota optima - Reálné číslo - Číslo musí být v exponenciálním tvaru tohoto formátu [+/-][1 číslice].[16 číslic]e[+/-][3 číslice] - Pokud je zadána možnost pokračování výpočtu, načítá se tato hodnota, jinak má pouze informativní charakter -
Nejlepší nalezený chromozom Jedná se o binární řetězec znaků Délka (nParam x nBitParam) znaků Povoleny jsou pouze znaky „0“ a „1“ Pokud je zadána možnost pokračování výpočtu, načítá se tato hodnota, jinak má pouze informativní charakter
{HC1, HC2, HC12, GA} HC12 celé číslo [1..999] 15 celé číslo [1..64] 64 {GC, BC} GC {min, max} min znakový řetězec, max. 50 znaků f6 celé číslo [2..264] 500 celé číslo [-232..(232-1)] 1179507480 Matice reálných čísel ve formátu Matlab. Délka každého čísla musí být přesně 14 znaků! [-5.000000e+000 +5.000000e+000;5.000000e+000 +5.000000e+000] Matice reálných čísel ve formátu Matlab. Délka každého čísla musí být přesně 14 znaků! [+1.000000e+000 +1.000000e+000 +2.000000e+000] Reálné číslo v exponenciálním tvaru. Délka musí být přesně 24 znaků! +2.3096583170456597e-006 binární řetězec délky (nParam x nBitParam) 0101001100011010
Tab. 1 Popis všech možných položek v XML souboru Vytvoření souboru XML může být provedeno uživatelem na základě dokumentace dle Tab.1. Pokud budou hodnoty zadány nekorektně nebo mimo rozsah, který udává tato tabulka, není zaručena správná funkčnost GATE-DLL toolboxu po načtení takového XML. Příklady XML souborů s různým nastavením jsou přiloženy na CD s přílohami.
34
4.2
Rozhraní DLL knihovny
Knihovna DLL komunikuje se systémem Matlab pomocí vhodně navržených funkcí. Sestavit vhodné komunikační rozhraní bylo v začátcích velmi problematické. Algoritmy obsažené v DLL knihovně potřebují k správné funkci komunikovat se systémem Matlab prostřednictvím matic reálných čísel, které jsou obvykle dost velkého rozměru. Také je potřeba přenášet některé struktury (např. při inicializaci algoritmů ze souboru XML) a nastavení. Několik měsíců po sestavení rozhraní jsem zjistil, že systém Matlab používá při ukládání matic do paměti počítače naprosto odlišný přístup, než jak je zvykem deklarovat matice v C++. Nepoužívá model dvourozměrného pole, ale pouze jednorozměrné pole, navíc jsou přehozeny řádky a sloupce. To značně zkomplikovalo práci a musel jsem celé rozhraní přepsat do jiné podoby. Postupem času jsem narazil ještě na jiný problém, který začal pomalu celkovou koncepci čím dál víc ovlivňovat. Ze začátku měla knihovna jenom velmi málo funkcí a algoritmů. Posléze však začínalo být čím dál obtížnější ladění a nalezení chyb, které vznikaly uvnitř knihovny DLL. Knihovnu DLL nebylo možno ladit v klasickém debugeru, jak se to běžně dělá u aplikací, které běží autonomně z EXE souboru. Začínal jsem tak, že jsem odladil algoritmy a objekty v klasickém EXE souboru a poté připojil na rozhraní DLL. Tato metoda ovšem nemohla odhalit chyby, které byly ve vlastním komunikačním rozhraní, jak jsem brzy zjistil. Nakonec jsem postupoval tak, že jsem si vytvořil menší simulační prostředí, které nahrazovalo systém Matlab a ladil jsem celý projekt nejdříve takto a až potom byla knihovna testována v sytému Matlab. I tak byl postup ladění dosti zdlouhavý, ve srovnání s laděním EXE projektu.
4.3
Popis exportních funkcí DLL
Komunikační rozhraní sestává právě z takových funkcí. Jsou navrženy tak, aby byl systém Matlab schopen načíst, modifikovat a poslat zpět data, ať se jedná o matice, struktury či jednotlivé hodnoty. Součástí DLL knihovny je i externí hlavičkový „h“ soubor, který je potřeba distribuovat s knihovnou. Jsou v něm uloženy všechny prototypy funkcí, které nabízí DLL. Při načítání knihovny v systému Matlab je potřeba i tento „h“ soubor. Hlavní hlavičkový soubor je dále závislý na souboru „globals.h“, ve kterém jsou předdefinovány datové typy a také prototyp struktury pro export parametrů. Tento způsob se jevil jako nejvhodnější, protože jinak by byla deklarace vlastních prototypů v hlavním hlavičkovém souboru knihovny extrémně dlouhá. 4.3.1
Základní funkce
Funkce
InitModel(Method,OptType,mCode,funcName,nParam,nBitParam,*iParam,*sVect,PopSize,rSeed)
Popis
Inicializace paměti pro vybraný optimalizační algoritmus, nastavení hodnot Parametr Method
Popis Volba algoritmu optimalizace (HC1,HC2,HC12,GA)
Možné hodnoty {0,1,2,3}
OptType
Volba optimalizace (min,max)
{0,1}
mCode
Volba kódování (BC,GC)
{0,1}
funcName Jméno vektorizované „m“ fukce
max. 50 znaků
nParam
[1..999]
Počet parametrů optimalizační úlohy
Parametry nBitparam Počet bitů kódujících jeden parametr v binárním kódu *iParam *sVect PopSize rSeed
Pole hodnot typu double - rozsah kódování parametrů Vektor hodnot typu double - start vektory pro HCA, nebo nulový ukazatel (pokud je požadována náhodná inicializace HCA) Velikost populace pro GA (nIndi), pro HCA se ignoruje - Hodnota pro inicializaci generátoru náhodných čísel - Pokud je 0, použije se inicializace pomocí aktuálního času TIME
[1..64] vektor rozměru ( 1 × nParam ⋅ 2 ) vektor rozměru ( 1 × nParam ) [2..264] [-232..(232-1)]
35
Funkce
FreeModel()
Popis
Uvolnění paměti, zavolání destruktorů modelu algoritmu vybraného při InitModelu
Parametry Žádné Funkce
GetRealPop(*RealArr)
- Načtení hodnot populace ve formě matice čísel typu double - Důležitá pro to, aby mohl systém Matlab spočítat fitness pro danou populaci jedinců - Je třeba volat s parametrem naalokované matice správného rozměru! Parametr Popis Možné hodnoty - Ukazatel na matici typu double ukazatel na - Matice musí být předem naalokována! Parametry jednorozměrné - Musí být rozměru (nIndi x nParam) *RealArr double pole - Pro algoritmy HCA lze zjistit rozměr nIndi voláním funkce HowMuchAlloc Popis
Funkce
SendFitness(*Fz)
Popis
Odeslání ohodnocení jedinců zpět do DLL
Parametry
Funkce Popis
Parametry
Parametr *Fz
Popis - Matice ohodnocení jedinců, typu double - Rozměru (nIndi x 1)
ret = HowMuchAlloc(BitWidth,Mthd) - Pomocná funkce, vrací počet řádků matice, kolik je třeba naalokovat - Pro algoritmy HCA a GA-HC Parametr Popis BitWidth Počet sloupců matice (X rozměr)
Možné hodnoty int [1..232]
Mthd
Algoritmus HCA (HC1,HC2,HC12)
int {0,1,2}
ret
Návratová hodnota (počet řádků matice, Y rozměr)
int [1..264]
Funkce
ret = GetActualValue()
Popis
Zjištění aktuálně nejlepšího ohodnocení (Best Fitness)
Parametry
Parametr ret
Funkce
SetActualValue(Value)
Popis
Nastavení aktuálně nejlepšího ohodnocení (Best Fitness)
Parametry
Parametr Value
Funkce
GetActualVectors(*dblArr)
Popis
Zjištění aktuálně nejlepších hodnot parametrů Parametr
Parametry
*dblArr
Popis Návratová hodnota typu double
Popis Hodnota typu double
Popis - Ukazatel na matici typu double - Matice musí být předem naalokována! - Musí být rozměru (1 x nParam)
Funkce
ret = GetnParam()
Popis
Zjištění počtu parametrů nastavených v DLL; pomocná funkce
Parametry
Možné hodnoty jednorozměrné double pole
Možné hodnoty double
Možné hodnoty double
Možné hodnoty jednorozměrné double pole
Parametr
Popis
Možné hodnoty
ret
Návratová hodnota typu int
int [1..216]
36 4.3.2
Výkonné metody
Funkce
Mutation(Type,Percent)
- Metoda mutace populace - V případě zavolání této funkce pro HCA provede vygenerování okolí v šířce podle zvoleného algortimu HCA Parametr Popis Možné hodnoty Type - Rezervováno, ignoruje se int {0} Kolik procent bitů populace bude mutovat (0,00..0,99) Parametry double [1..N] - Kolik bitů v populaci bude zmutováno (1..N) Percent [0,00 - 0,99] - Pokud je toto číslo < 1, bere se tento parametr jako procento, v druhém případě jako počet bitů Popis
Funkce
Cross(Percent,Method,nCrossPts) - Metoda křížení populace - Pouze pro algoritmus GA Parametr Popis
Popis
Percent
Kolik procent populace bude zkříženo (0,00..0,99)
- Metoda křížení (pcross,paramcross,ucross) pcross – bodové křížení Parametry Method paramcross – bodové s respektováním parametrů ucross – uniformní křížení (swapbits) - Počet křížících bodů, pozice se generuje náhodně nCrossPts - Interně je počet křížících bodů omezen na maximálně (nParam x nBitparam) Funkce
Možné hodnoty double [0,00 - 0,99] int {0,1,2}
int [0..216]
Selection(nInd)
- Turnajová selekce jedinců - Pouze pro GA Parametr Popis Parametry - Počet jedinců vstupujících do turnaje nInd - Interně omezeno na max (nIndi) Popis
4.3.3
int [1..216]
Funkce pro GA-HC
Funkce
MutationHC(Method,Selection,CoreSize)
Popis
Metoda mutace populace pro algoritmus GA-HC Parametr Method
Parametry
Selection CoreSize
Funkce
Možné hodnoty
Popis Volba algoritmu optimalizace jader (HC1,HC2,HC12) - Metoda výběru pozice jádra (rand,randp) rand – náhodná kdekoliv randp – náhodná pouze v hranicích parametrů Velikost jádra v bitech
Možné hodnoty int {0,1,2} int {0,1} int [0..216]
GetRealHC(*RealArr)
- Načtení hodnot bloku populace zoptimalizované pomocí HCA - Matice čísel typu double Popis - Důležitá pro to, aby mohl systém Matlab spočítat fitness pro daný blok populace jedinců - Je třeba volat s parametrem naalokované matice správného rozměru! Parametr Popis Možné hodnoty - Ukazatel na matici typu double - Matice musí být předem naalokována! ukazatel na Parametry *RealArr - Musí být rozměru (Y x nParam) jednorozměrné - Rozměr Y zjistíme voláním funkce double pole HowMuchAlloc(CoreSize,Method)
37 Funkce
FitnessHC(*FzHC)
Popis
Odeslání ohodnocení bloku jedinců, kteří jsou optimalizovaní HCA algoritmem, zpět do DLL Parametr
Parametry
*FzHC
Popis - Matice ohodnocení jedinců, typu double - Rozměru (Y x 1) - Rozměr Y zjistíme voláním funkce HowMuchAlloc(CoreSize,Method)
Možné hodnoty jednorozměrné double pole
Algoritmus GA-HC pracuje stejně jako algoritmus GA, pouze mutace je vylepšena. V populaci jsou náhodně vybírána jádra o předem zvolené šířce a tato jádra jsou optimalizována pomocí definovaného algoritmu HCA. Poté je třeba tento nový blok jedinců (blok populace celých chromozomů se změněnými jádry) ohodnotit v systému Matlab a hodnocení odeslat zpět do knihovny DLL. Metoda MutationHC tedy není pouze jenom jedna exportní funkce, ale je součástí tří metod (MutationHC,GetRealHC,FitnessHC). Bez dalších dvou metod by ji nebylo možné realizovat (vzhledem k tomu, že DLL jádro pracuje interně, ale ohodnocování provádí externě systém Matlab). 4.3.4
Funkce pro kompatibilitu s původním GATE
Tyto funkce jsou implementovány proto, aby zůstal nový GATE-DLL kompatibilní s původním GATE toolboxem. Uvážíme-li, že knihovna DLL pracuje interně naprosto autonomně (veškeré struktury a nastavení jsou modifikovány pouze uvnitř), je třeba doplnit několik funkcí, které by dokázaly exportovat některé struktury do systému Matlab. Jedná se hlavně o binární populaci jedinců, která je nutná, pokud by se uživatel rozhodl pokračovat ve výpočtu v původním GATE toolboxu. Rozhodnutí udržovat struktury po celou dobu optimalizačního procesu pouze v DLL knihovně bylo učiněno na základě rychlostních testů. Když si uvědomíme, že v každém kroku libovolného algoritmu by bylo třeba exportovat celou binární populaci (jedná se většinou o matici dost velkého rozměru) do systému Matlab, je jasné, že rychlost výpočtů nového GATE-DLL by zřejmě nebyla o moc vyšší, než u původního GATE. A GATE-DLL byl zadán s jasným cílem: urychlit stávající výpočty. Funkce
GetBinPool(*BinArr)
- Získání populace jedinců z DLL v binárním tvaru - Je třeba volat s parametrem naalokované matice správného rozměru! Parametr Popis - Ukazatel na matici typu double Parametry *BinArr - Matice musí být předem naalokována! - Rozměr matice musí být (nInd x nParam ∙ nBitParam) Popis
Funkce
SetBinPool(*BinArr)
Popis
Nastavení interní binární populace jedinců DLL na určité hodnoty
Parametry
Funkce
Parametr *BinArr
Popis - Matice typu double - Rozměr matice musí být (nInd x nParam ∙ nBitParam)
Možné hodnoty jednorozměrné double pole
Možné hodnoty jednorozměrné double pole
GetBinActVec(*BinArr)
- Získání nejlepšího chromozmu z DLL v binárním tvaru - Je třeba volat s parametrem naalokované matice správného rozměru! Parametr Popis - Ukazatel na matici typu double Parametry *BinArr - Matice musí být předem naalokována! - Rozměr matice musí být (1 x nParam ∙ nBitParam) Popis
Možné hodnoty jednorozměrné double pole
38
Funkce
SetBinActVec(*BinArr)
Popis
Nastavení nejlepšího interního chromozmu v DLL na určité hodnoty
Parametry
4.3.5
Parametr *BinArr
Popis - Matice typu double - Rozměr matice musí být (1 x nParam ∙ nBitParam)
Možné hodnoty jednorozměrné double pole
Funkce pro podporu XML
Tyto funkce zajišťují obsluhu požadavků uživatele na uložení či načtení nastavení z/do XML souboru. SaveXML je možné volat kdykoliv v průběhu výpočtu, uloží právě aktuální hodnoty (aktuální v DLL). LoadXML je možné použít dvěma způsoby. Buď je možno volat tuto funkci kdekoliv v průběhu výpočtu, nebo ji použít jako inicializaci hodnot pro odstartování nového výpočtu. V případě, že ji použijeme pro inicializaci, je třeba nejdříve zavolat tzv. slepý start, tj. zavolat funkci InitModel(Method,0,0,'',0,0,[],0,0,0). Method je číslo metody, kterou hodláme pokračovat po načtení hodnot z XML {0, 1, 2, 3}, což odpovídá metodám {HC1, HC2, HC12, GA}. Slepá inicializace je nutná, protože je potřeba spustit konstruktory objektů. Alokace paměti pro dynamická pole se provede až ve funkci LoadXML. Funkce
ret = SaveXML(filename)
Popis
Uloží parametry interních struktur DLL do XML souboru Parametr
Parametry filename ret
Popis Jméno XML souboru (včetně cesty), do kterého chceme uložit parametry („d:\\test.xml“) Návratová hodnota, zda se zápis XML podařil či ne (no,yes)
pole znaků int {0,1}
Funkce
ret = LoadXML(filename,StartMode)
Popis
Načte parametry z XML souboru a reincializuje interní struktury podle těchto parametrů Parametr
Popis Jméno XML souboru (včetně cesty), ze kterého chceme načíst filename parametry („d:\\test.xml“) - Určuje způsob pokračování výpočtu (restart,continue) Parametry StartMode restart – reinicializuje výpočet od začátku continue – načte hodnoty z XML a pokračuje od těchto hodnot Návratová hodnota, zda se XML podařilo otevřít a načíst všechny ret položky (no,yes) Funkce
ExportParams(*aStruct)
Popis
Export parametrů do systému Matlab po načtení hodnot z XML Parametr
Parametry 1
Možné hodnoty
*aStruct
Popis - Struktura typu OptParams1 - Struktura musí být dopředu naalokována! - Do této struktury se uloží načtené parametry
Možné hodnoty pole znaků int {0,1} int {0,1}
Možné hodnoty struktura OptParams
Jedná se o strukturu se všemi uloženými parametry, detailní popis je v kapitole 4.3.7
4.3.6
Funkce pro podporu distribuovaných výpočtů
Do knihovny DLL byla přidána podpora pro distribuované výpočty. V takovém případě se z ní stává klientská aplikace, tudíž musí obsahovat podporu i pro tento druh činnosti. Snažil jsem se maximálně zjednodušit ovládání na straně klientské aplikace, veškeré ovládání klienta spočívá pouze ve dvou funkcích. Funkce AddClient jej připojí do právě probíhajícího distribuovaného výpočtu. Ovládání veškeré činnosti potom probíhá na straně serverové aplikace, klient potom pracuje zcela autonomně a nezávisle. Aby však mohla serverová aplikace
39 klienta ukončit i v prostředí systému Matlab (hlavní výpočetní cyklus probíhá zde), je třeba ještě jedna funkce, která bude zjišťovat stav klienta a určovat, zda má být výpočet ukončen či ne. O to se stará funkce ClientStatus. Komunikace mezi serverem a klienty při distribuovaných výpočtech je prováděna přes master XML soubor, který zakládá serverová aplikace. Nejdříve je tedy nutno spustit server a založit tento XML. Poté je možno připojit klienty na tento soubor. Z toho vyplývá ještě jedna věc. Před samotným přidáním klienta do distribuovaných výpočtů je potřeba nejdříve inicializovat model genetického algoritmu z master XML souboru (LoadXML), odkud si načte veškeré nastavení. Poté je možno volat funkci AddClient a klient se automaticky připojí k serveru prostřednictvím master XML souboru. Na závěr nutno dodat, že distribuované výpočty pracují pouze s algoritmy GA nebo GA-HC.
Popis funkcí: Funkce
AddClient()
Popis
- Přepne DLL knihovnu do módu klient pro distribuované výpočty - Před samotným voláním této funkce je třeba načíst master XML soubor (LoadXML)
Parametry Žádné Funkce
ret = ClientStatus()
Popis
Zjištění stavu klienta při průběhu distribuovaného výpočtu
Parametry
4.3.7
Parametr ret
Popis - Návratová hodnota - Vrací stav klienta (working,stopped)
Možné hodnoty int {0,1}
Koeficient „míry pokrytí“ Hammingova prostoru
Jedná se o speciální funkci, která dokáže spočítat, jaká je variabilita jedinců v dané populaci, bližší informace viz [4]. Funkce
ret = GetQHD()
Popis
Vypočtení koeficientu „míry pokrytí“ Hammingova prostoru pro aktuální populaci Parametr
Parametry
ret
Popis - Návratová hodnota - Vrací hodnotu qvar HD
Funkce
ret = GetRoHsum()
Popis
Vypočtení sumy Hammingovy matice pro aktuální populaci Parametr
Parametry
ret
Popis - Návratová hodnota - Vrací hodnotu ρ Hsum
Možné hodnoty double <0,1>
Možné hodnoty int [0..232]
40 4.3.8
Struktura OptParams
Struktura OptParams je definována v hlavičkovém souboru „globals.h“. Jedná se o strukturu, ve které se odesílají parametry do systému Matlab po načtení z XML souboru. Tato struktura musí být dopředu alokována, aby do ní mohla DLL knihovna exportovat patřičné parametry. Popis položek struktury nParam nBitParam PopSizeX PopSizeY funcName funcOpt mCode *iParam *sVect rSeed
4.4
- počet parametrů optimalizační úlohy - počet bitů, kolika jsou kódovány jednotlivé parametry v binárním kódu - velikost binární populace jedinců, počet sloupců - velikost binární populace jedinců, počet řádků - jméno vektorizované účelové funkce (Matlab „m“ souboru) - požadavek optimalizace, minimum nebo maximum {0, 1} ~ {min, max} - typ kódování, binární nebo Grayovo {0, 1} ~ {BC, GC} - matice intervalů, na kterých jsou kódovány jednotlivé intervaly, je potřeba ji alokovat také dopředu; je rozměru ( nParam × 2 ) - vektor start bodů pro HCA, je třeba alokovat také dopředu; má rozměr ( 1× nParam ) - hodnota pro inicializaci generátoru náhodných čísel
Propojení DLL se systémem Matlab
V systému Matlab lze používat externí knihovny ve formě dynamicky linkovaných knihoven DLL, nebo tříd Java. Využil jsem tedy rychlosti C++ jazyka a podpory DLL k urychlení výpočtů původního GATE toolboxu. Zpočátku jsem nevěděl, jak přenášet rozsáhlé struktury (velké matice čísel, struktura s parametry) mezi DLL a Matlabem. Jediná rozumná nápověda, která se k tomuto problému dala najít, byl help Matlabu, kde byly příklady, jak použít podpory DLL knihoven. Ovšem žádný příklad, jak předat např. rozsáhlé pole čísel. Nakonec jsem tedy skončil u experimentování a testování, což práci na začátku poněkud zpomalilo. Systém Matlab podporuje předávání datových struktur i velkých matic v klasickém formátu C++ jako ukazatele do paměti. Je však potřeba kontrolovat alokaci paměti a také to, zda se čte a zapisuje z/do povolené oblasti paměti. Jedná se o trochu netradiční přístup k datovým položkám. Pro získání pole čísel je potřeba postupovat následovně: nejdříve se musí alokovat matice správného rozměru v Matlabu. Poté předáme knihovně DLL ukazatel na tuto matici a DLL je schopno do této matice zapsat hodnoty. Nakonec se tyto hodnoty mohou přiřadit do matice Matlabu. U struktury je to ještě o něco složitější, nejdříve se musí založit prototyp struktury, kterou chceme získat z DLL, alokovat paměť pro veškeré položky, poté je potřeba volat DLL s ukazatelem na tuto strukturu a nakonec je možno hodnoty z ukazatele předat založené struktuře v Matlabu. Další problém nastal u přenášení dvourozměrných polí. Jak jsem již zmínil v kapitole 4.2, systém Matlab používá odlišný přístup k ukládání rozsáhlých polí čísel (matic), než jak je to obvyklé ve vyšších programovacích jazycích (C++, Delphi). V jazyce C++ obvykle deklarujeme matici jako dvourozměrné dynamické nebo statické pole. Systém Matlab podobnou matici ale ukládá do paměti jako jednorozměrné datové pole. Při přenosu dat mezi Matlabem a DLL knihovnou nastává tedy problém, že data je třeba konvertovat do jiného formátu a při předávání zpět opět do původního tvaru. O transformaci dat se stará rozhraní DLL knihovny, které převádí indexaci datových polí z jednorozměrného formátu do dvourozměrné reprezentace. Původní GATE toolbox byl vyřešen jako sada Matlab funkcí, které uživatel volal a používal v prostředí Matlab. Jelikož je přístup k algoritmům v DLL přes rozhraní knihovny dosti komplikovaný (je třeba deklarovat vhodné ukazatele a struktury), sestavil jsem podobnou sadu Matlab funkcí, které se liší od původního GATE toolboxu co možná nejméně. Ovládání nového GATE se tak stává velmi jednoduchým a pro uživatele velmi příjemným (ve srovnání
41 s přímým voláním funkcí DLL knihovny). Toto zjednodušení si ovšem vybralo menší daň v podobě nepatrného zpomalení výpočtů (časové náklady na volání Matlab funkcí a návrat zpět do hlavního programu). Pro získání maximální rychlosti výpočtů by bylo potřeba sestavit hlavní program, který by volal přímo funkce DLL. Tímto by bylo možno dosáhnout dalšího, až 50procentního urychlení oproti programu, který bude volat GATE-DLL funkce. 4.4.1
Systém GATE-DLL
Koncepce GATE-DLL je z pohledu uživatele tvořena sadou předdefinovaných Matlab funkcí, které je třeba volat v určitém smysluplném pořadí. GA a HCA algoritmy mají odlišnou strukturu volání funkcí, ale některé funkce jsou pro všechny algoritmy společné. GATE-DLL funkce mají téměř shodnou syntaxi jako zápis funkcí původního GATE. Snažil jsem se o maximální kompatibilitu funkcí. Také hlavní struktura je z větší části naprosto stejná. Některé funkce a parametry nebyly implementovány (externí DLL by v tomto případě nepřineslo žádné urychlení, nebo byla vhodnost parametrů posouzena jako ne moc výhodná, proto byl vývoj DLL zaměřen hlavně na ty funkce a parametry, které jsou důležitější). 4.4.2
Popis hlavní struktury GATE-DLL
Hlavní struktura GATE-DLL byla navržena tak, aby byla co nejvíce podobná původní GATE struktuře a uživatel mohl v případě nutnosti pokračovat ve výpočtu pomocí GATE. Jako strukturu pro GATE by však použil GATE-DLL strukturu. Jedná se o strukturu, ve které jsou uchovávány veškeré parametry a nastavení pro řešení dané optimalizační úlohy. Popis položek GATE-DLL Matlab struktury: nParam nBitParam nIndi funName funOpt mCode iParam mInit rndSeed Method sVect
- počet parametrů optimalizační úlohy - počet bitů, kolika jsou kódovány jednotlivé parametry - velikost populace jedinců GA algoritmů - jméno vektorizované účelové funkce - druh optimalizace, minimum nebo maximum {'min', 'max'} - typ binárního kódování, binární nebo Grayovo {'BC', 'GC'} - rozsahy, na kterých jsou kódovány jednotlivé parametry; matice rozměru nParam × 2 - typ inicializace, náhodná nebo startvektorem {'random', 'svect'} (inicializace startvektorem pouze pro HCA) - inicializační hodnota pro generátor náhodných čísel - typ metody HCA {'HC1', 'HC2', 'HC12'} - startvektor pro inicializaci HCA ve formě matice rozměru 1 × nParam
GA.funName GA.funOpt GA.iParam GA.nParam GA.nBitParam GA.nIndi GA.mCode GA.mInit GA.rndSeed
= = = = = = = = =
'f6'; 'min'; [-5 5]; 2; 16; 500; 'BC'; 'random' 156;
HC.funName HC.funOpt HC.iParam HC.mCode HC.Method HC.mInit HC.sVect HC.nParam HC.nBitParam HC.rndSeed
= = = = = = = = = =
'f1'; 'min'; [-5.1 5]; 'BC'; 'HC12'; 'svect'; [1 1 2]; 3; 63; 156;
Obr. 15 Příklady správně definovaných struktur pro GA a HCA
42 4.4.3
Popis GATE-DLL funkcí
V následujících tabulkách bude shrnut popis všech funkcí a parametrů, které jsem sestavil v systému Matlab. Zdrojové kódy těchto funkcí jsou přiloženy na CD, kde je možno se podívat, jak jsou řešeny, nebo použít přímo sestavené demo aplikace (demoGA a demoHC). Pro odlišení od původního GATE začínají všechny metody GATE-DLL slovem „DLL“. Společné funkce: Funkce
[GA|HC res] = DLLXMLinit(Method,Filename,Mode)
Popis
Inicializuje algoritmy GA nebo HCA ze souboru XML Parametr Method Filename
Parametry
Mode GA|HC res
Funkce
Popis Volba algoritmu optimalizace (HC1,HC2,HC12,GA) Jméno XML souboru (včetně cesty), ze kterého chceme načíst parametry ('d:\test.xml') - Určuje způsob pokračování výpočtu (restart,continue) restart – reinicializuje výpočet od začátku continue – načte hodnoty z XML a pokračuje od těchto hodnot Jméno GA nebo HC hlavní struktury, kterou funkce vrací Validační hodnota, zda se podařilo otevřít soubor a načíst všechny parametry (no,yes)
Možné hodnoty int {0,1,2,3} pole znaků int {0,1} jméno struktury int {0,1}
[GA|HC res] = DLLloadXML(GA|HC,Filename,Mode)
- Načte nastavení GA nebo HCA algoritmů z XML souboru - Pokračuje v optimalizaci dříve vybraným algoritmem Parametr Popis Jméno vstup/výstupní GA nebo HC hlavní struktury, kterou funkce GA|HC modifikuje a vrací Jméno XML souboru (včetně cesty), ze kterého chceme načíst Filename parametry ('d:\test.xml') Parametry - Určuje způsob pokračování výpočtu (restart,continue) restart – reinicializuje výpočet od začátku Mode continue – načte hodnoty z XML a pokračuje od těchto hodnot Validační hodnota, zda se podařilo otevřít soubor a načíst všechny res parametry (no,yes) Popis
Funkce
[res] = DLLsaveXML(Filename)
Popis
Uloží aktuální nastavení do XML souboru Parametr
Parametry
Filename res
Funkce
Popis Jméno XML souboru (včetně cesty), ze kterého chceme načíst parametry ('d:\test.xml') Validační hodnota, zda se podařilo otevřít soubor a načíst všechny parametry (no,yes)
Možné hodnoty jméno struktury pole znaků 'restart' 'continue' int {0,1}
Možné hodnoty pole znaků int {0,1}
[GA|HC] = DLLfitness(GA|HC)
- Ohodnocení populace jedinců - Pro GA i HCA algoritmy Parametr Popis Možné hodnoty Parametry Jméno vstup/výstupní GA nebo HC hlavní struktury, kterou funkce GA|HC jméno struktury modifikuje a vrací Popis
43 Funkce
DLLviewProgress(GA|HC,Mode)
Popis
Zobrazí průběh a výsledky optimalizačního procesu Parametr
Parametry
GA|HC Mode
Funkce
Popis Jméno vstup/výstupní GA nebo HC hlavní struktury, kterou funkce modifikuje a vrací Typ výpisu, jenom účelová funkce, nebo i parametry (small,full)
Možné hodnoty jméno struktury 'small' 'full'
[GA|HC] = DLLfreeModel(GA|HC)
- Uvolnění paměti a DLL knihovny - Je třeba volat na konci výpočetního cyklu Parametr Popis Možné hodnoty Parametry Jméno vstup/výstupní GA nebo HC hlavní struktury, kterou funkce GA|HC jméno struktury uvolní Popis
Funkce
[GA|HC] = DLLGetPool(GA|HC)
- Export binární populace jedinců do Matlab GA/HCA struktury - Kvůli zachování kompatibility s původním GATE - Je třeba zavolat před převedením výpočtu do původního GATE Parametr Popis Možné hodnoty Parametry Jméno vstup/výstupní GA nebo HC hlavní struktury, kterou funkce GA|HC jméno struktury vrací Popis
Metody pro HCA algoritmy: Funkce
[HC] = DLLstepHC(HC)
- Jeden krok HCA algoritmu - Je dobré volat opakovaně v cyklu spolu např. výpisem hodnot (DLLviewProgress) Parametr Popis Možné hodnoty Parametry Jméno vstup/výstupní GA nebo HC hlavní struktury, kterou funkce GA|HC jméno struktury vrací Popis
Metody pro GA algoritmy: Funkce
[GA] = DLLselect(GA,mSelect,pSelect)
Popis
Výkonná metoda selekce pro GA Parametr
Parametry
GA mSelct pSelect
Popis Jméno vstup/výstupní GA hlavní struktury, kterou funkce modifikuje a vrací - Metoda selekce (tournament) tournament – turnajová selekce z několika jedinců Počet jedinců vstupujících do turnaje
Funkce
[GA] = DLLcross(GA,mCross,pCross)
Popis
Výkonná metoda křížení pro GA Parametr GA
Parametry mCross
pCross
Popis Jméno vstup/výstupní GA hlavní struktury, kterou funkce modifikuje a vrací - Metoda křížení (pcross,paramcross,ucross) pcross – bodové křížení paramcross – bodové s respektováním parametrů ucross – uniformní křížení (swapbits) - Matice se dvěma parametry [p1 p2] p1 – kolik procent populace bude zkříženo [0.00 – 0.99] p2 – počet křížících bodů [1..N]
Možné hodnoty jméno struktury 'tournament' int [2..N]
Možné hodnoty jméno struktury 'pcross' 'paramcross' 'ucross' matice (1 x 2)
44 Funkce Popis
[GA] = DLLmutation(GA,mMut,pMut) Výkonná metoda mutace pro algoritmus GA Parametr
Popis Jméno vstup/výstupní GA hlavní struktury, kterou funkce modifikuje a vrací - Metoda mutace (bitmut) bitmut – náhodná bitová mutace
GA Parametry
mMut pMut
- Kolik procent bitů (pMut < 1), nebo bitů mutuje
Funkce
[GA] = DLLmutationHC(GA,mHC,nKer,mKer,pKer)
Popis
Výkonná metoda mutace pro algoritmus GA-HC Parametr
Popis Jméno vstup/výstupní GA nebo HC hlavní struktury, kterou funkce modifikuje a vrací
GA mHC
Volba algoritmu optimalizace jader (HC1,HC2,HC12)
Parametry
- Počet jader nebo procent populace jedinců [1..N] nebo [0.00 - 0.50] - Metoda výběru pozice jádra (rand,randp) rand – náhodná kdekoliv randp – náhodná pouze v hranicích parametrů Velikost jader v bitech
nKer mKer pKer
Možné hodnoty jméno struktury 'bitmut' [1..N] [0.00 – 0.99]
Možné hodnoty jméno struktury 'HC1' 'HC2' 'HC12' [1..N] [0.00 – 0.50] 'rand' 'randp' [1..N]
Metody pro distribuované výpočty: Funkce
DLLAddClient
- Přepne DLL knihovnu do módu klient pro distribuované výpočty - Před samotným voláním této funkce je třeba načíst master XML soubor (DLLLoadXML) nebo (DLLXMLinit) Parametr Popis Možné hodnoty Parametry Žádný Popis
Funkce Popis Parametry
[res] = DLLClientStatus Zjištění stavu klienta při průběhu distribuovaného výpočtu Parametr res
Popis - Návratová hodnota - Vrací stav klienta (working,stopped)
Možné hodnoty {0,1}
Metody pro výpočet „míry pokrytí Hammingova prostoru: Funkce Popis
[res] = DLLGetQHD Výpočet „míry pokrytí“ Hammingova prostoru pro aktuální populaci jedinců Parametr
Parametry
res
Popis - Návratová hodnota - Vrací hodnotu qvar HD
Funkce
[res] = DLLGetRoHsum
Popis
Výpočet sumy Hammingovy matice pro aktuální populaci jedinců Parametr
Parametry
res
Popis - Návratová hodnota - Vrací hodnotu ρ Hsum
Možné hodnoty <0,1>
Možné hodnoty [0..232]
45 Příklady použití GATE-DLL funkcí: [HC res] = DLLXMLinit('hc12','d:\hc.xml','restart'); if(res) HC = DLLfitness(HC); for i=1:100 if(mod(HC.nGener,10) == 0) DLLviewProgress(HC,'small'); end HC = DLLstepHC(HC); HC = DLLfitness(HC); HC.nGener = HC.nGener + 1; end DLLviewProgress(HC,'small'); else fprintf('Chyba pri nacitani XML souboru.\n'); end HC = DLLfreeModel(HC); clear HC i res;
Obr. 16 Příklad GATE-DLL funkcí při použití HCA GA.funName = 'f6'; GA.funOpt = 'min'; GA.iParam = [-5 5]; GA.iType = '[0)'; GA.nParam = 4; GA.nBitParam = 16; GA.nIndi = 500; GA.mCode = 'BC'; GA.mInit = 'random'; GA = DLLinitPool(GA); GA = DLLfitness(GA); for i=1:1000 GA = DLLselect(GA,'tournament',10); GA = DLLcross(GA,'pcross',[0.2 5]); GA = DLLmutation(GA,'bitmut',0.02); GA = DLLfitness(GA); if(mod(GA.nGener,100) == 0) DLLviewProgress(GA,'small'); end GA.nGener = GA.nGener + 1; end DLLviewProgress(GA,'small'); GA = DLLfreeModel(GA); clear GA i;
Obr. 17 Příklad GATE-DLL funkcí při použití GA
4.4.4
Sestavení vektorizované funkce
Správné sestavení vektorizované funkce je pro řešení optimalizačního problému pomocí GATE nebo GATE-DLL klíčovou záležitostí. Aby bylo možno spočítat víceparametrovou optimalizaci, musí být účelová funkce převedena na vektorizovaný tvar. Je třeba funkci sestavit tak, aby pracovala s jedním vstupním parametrem hodnot. Tímto parametrem je matice hodnot rozměru ( m × n ), ve které jsou jednotlivé sloupce jako parametry optimalizační úlohy, tedy vektory hodnot. Výstupním parametrem pak musí být vektor rozměru ( m × 1 ), který reprezentuje ohodnocení jednotlivých řádků pomocí účelové funkce.
46
Matice vstupních vektorů x10 x20 ......... xn0 x11 x21 ......... xn1 . . . . . . . . . . . . x1m x2m ......... xnm
Výstupní vektor
Vektorizovaná účelová funkce
y10 y11 . . . . y1m
Obr. 18 Princip správně sestavené vektorizované účelové funkce Převedení funkce na tento tvar nemusí být vždy snadnou záležitostí, podrobnější informace lze najít v [1]. Příklady správně sestavených vektorizovaných funkcí: Jednorozměrná funkce:
f ( x) = x − e x
2
function [fce] = fce1(x) fce = x-(exp(x.^2)); end
Víceparametrová funkce:
1 2 f ( x ) = 12 ⋅ x1 + ⋅ x2 + 2 ⋅ x3 2
function [fce] = fce2(x) fce = 12.*x(:,1)+1./2.*x(:,2)+2.*x(:,3); end
Obr. 19 Příklady správně sestavených vektorizovaných funkcí
4.5
Systém distribuovaných výpočtů
Pro účely optimalizace funkcí s mnoha parametry, kdy by jeden výpočetní stroj hledal optimální řešení velmi dlouho, byla do GATE-DLL přidána podpora pro distribuované výpočty. Umožňuje spustit výpočet složitého optimalizačního problému na více výpočetních strojích a tím získat potenciálně velmi výkonný nástroj optimalizace. Nutno dodat, že při distribučních výpočtech lze využívat pouze genetické algoritmy jak GA tak GA-HC, ale ne algoritmy HCA. Každý klient může být nastaven naprosto nezávisle na jiných klientech (samozřejmě kromě globálních hodnot optimalizace jako: počet parametrů, počet bitů na parametr, ap.).
47 4.5.1
Struktura master XML souboru
V dřívějších kapitolách jsem již zmínil, že komunikace probíhá netradičním způsobem, a to přes master XML soubor, který zakládá serverová aplikace. Klienty jsou jednotlivé GATE−DLL sady funkcí, spouštěné v systému Matlab. Zamezení kolizím při zápisu je řešeno pomocí archivního atributu souboru. Každá zapisující strana nejdříve testuje stav atributu a pokud není nastaven, nastaví jej a provede čtení/zápis z/do XML. Po dokončení operace jej zase vrátí do původního stavu. Popis položek master XML souboru: nParam nBitParam nIndi mCode funcOpt funcName iParam rndSeed GenStep BestFit BestBinFit Clients
- počet parametrů optimalizační úlohy - počet bitů, kolika bude kódován každý parametr - velikost populace jedinců - typ binárního kódování – binární nebo Grayovo - požadavek optimalizace – minimum nebo maximum - jméno vektorizované účelové funkce (Matlab „m“ souboru) - intervaly, na kterých jsou kódovány parametry (omezující podmínky) - inicializační hodnota pro generátor náhodných čísel (vždy 0) - počet generací GA algoritmu, po kterých hlásí klienti svůj stav server aplikaci - celkově nejlepší fitness ze všech připojených klientů - celkově nejlepší chromozom ze všech připojených klientů - počet klientů připojených k serveru
Položky, které přidávají jednotliví klienti: ClientXFit - nejlepší fitness nalezené klientem číslo X ClientXBinFit - nejlepší chromozom nalezený klientem číslo X ClientXStatus - stav klienta číslo X (0, 1, 2, 3) ~ (working, restart, stop, starting) 4.5.2
Průběh komunikace:
Komunikace mezi serverem a klienty probíhá následujícím způsobem: 1) Server aplikace založí master XML soubor s celkovým nastavením optimalizační úlohy. 2) Master soubor musí být nasdílen na síti, aby byl pro klienty pracující na různých výpočetních strojích dostupný. 3) Server poté monitoruje master XML v 3sekundových intervalech, zda se připojil nějaký nový klient. 4) Spuštěný klient si ihned na začátku načte globální nastavení z XML souboru, zároveň zvětší hodnotu Clients o 1. Dále nastaví svůj ClientStatus na hodnotu 3 (starting), čímž dá najevo serveru, že se připojil nový klient a že ještě nemá vypočteno žádné řešení. Také si načte hodnotu GenStep, která udává, po kolika generacích GA má hlásit stav výpočtu serveru. 5) Klient dokončí jeden výpočetní cyklus a předá nalezené řešení do XML. Svůj status nastaví na hodnotu 0 (runing). 6) Server zaznamená při dalším intervalu monitoringu XML souboru, že se připojil nový klient a načte jeho řešení. 7) Pokud nastane požadavek restartovat nebo zastavit klienta, zapíše do stavu klienta buď 1 (restart), nebo 2 (stop). 8) Klient si v dalším cyklu nejdříve testuje status, pokud je požadavek k ukončení, zastaví se. Pokud je požadavek k restartu, načte celkovou nejlepší hodnotu serveru BestFit a porovnává, zda mezitím on sám nenašel lepší hodnotu (komunikace je zpožděna o 1 cyklus klienta). Pokud je celková hodnota serveru lepší, zařadí chromozom BestBinFit do populace místo nejhoršího jedince a pokračuje ve výpočtech. 9) Při zastavení serveru se odešle všem klientům stav stop.
48 4.5.3
Server aplikace
Server aplikace je vytvořena jako klasická EXE aplikace v prostředí C++ s grafickým rozhraním. Nastavování všech hodnot je tedy pro uživatele velmi snadné a příjemné. Pokud je server spuštěn, může uživatel klienty ovládat na dálku manuálně nebo nastavit automatické hlídání, kdy server aplikace nezávisle na uživatelově zásahu restartuje klienty, kteří mají nejlepší fitness pod určitou procentuální hranicí celkového fitness.
Obr. 20 Grafické rozhraní server aplikace 4.5.4
Popis ovládání server aplikace:
Nejdříve je potřeba zadat globální nastavení optimalizační úlohy. Zadává se počet parametrů, počet bitů na parametr, velikost populace jedinců, druh binárního kódování, druh optimalizace, jméno funkce (Matlab „m“ souboru) a hodnota, po kolika generacích GA hlásí klienti stav výpočtu serveru.
49
Počet parametrů optimalizační úlohy Počet bitů, kolika jsou kódovány jednotlivé parametry Velikost populace jedinců Typ binárního kódování Druh optimalizace Jméno vektorizované účelové funkce Číslo, které udává, po kolika generacích GA mají hlásit klienti serveru nalezené fitness
Obr. 21 Globální nastavení serveru Po nastavení těchto hodnot je možno vkládat intervaly, na kterých jsou kódovány jednotlivé parametry. Tlačítkem „+“ přidáváme daný interval a tlačítkem „−“ intervaly odebíráme. Všechny intervaly jsou zobrazeny v okně ve formátu Matlab matice. Počet vložených intervalů se zobrazuje dole a je třeba je zadávat tak dlouho, dokud počet vložených intervalů nebude roven počtu nastavených parametrů (poté se zobrazí dole zelený nápis „OK“). Hodnota minima kódovaného intervalu Hodnota maxima kódovaného intervalu
Tlačítko pro odebrání hodnot intervalu Tlačítko pro přidání hodnot intervalu
Zobrazení všech vložených intervalů Stav kódovaných intervalů Celkový počet intervalů
Obr. 22 Přidávání intervalů, na kterých jsou kódovány parametry Nyní je možno uložit master XML soubor (tlačítko dole „Save XML and Start Server“). Zároveň začne server aplikace po 3sekundových intervalech monitorovat, zda se nepřipojují klienti. Po připojení klientů server zobrazuje klienty v okně označeném „Clientlist“.
50
Číslo připojeného klienta Rozdíl fitness klientů od nejlepšího fitness serveru (v procentech) Stav klienta (starting, stopped, restarting, running) Hodnota fitness klienta
Seznam připojených klientů
Obr. 23 Seznam připojených klientů Činnost klientů lze ovládat buď manuálně nebo lze nechat ovládání klientů na automatice serveru. V případě manuálního ovládání lze libovolného klienta restartovat nebo úplně zastavit. V případě automatického ovládání server sleduje fitness jednotlivých klientů a klienti, kteří se dostanou pod nastavenou procentuální hranici rozdílu fitness, jsou automaticky restartováni s novou hodnotou. Aktivace automatického sledování Nastavení maximálního rozdílu pro automatický restart klientů (v procentech)
Nejlepší hodnota fitness ze všech klientů
Manuální restart klienta číslo X Manuální stop klienta číslo X
Výběr klienta X
Obr. 24 Ovládání klientů a nejlepší hodnota fitness Server je možno kdykoliv zastavit tlačítkem „Stop“. V tom případě se všem klientům rozešle požadavek na ukončení práce; jejich stav se přepne na stav 2 (stop). Server aplikace byla otestována při optimalizaci až 999 parametrů při maximální bitové přesnosti 64 bitů na parametr. Takový druh optimalizace ovšem není velmi častý a vyžadoval by
51 adekvátní velikost populace jedinců. Průběh optimalizace by tak byl velmi pomalý a vyžadoval by výpočet za použití mnoha klientů. 4.5.5
Klientská část
Je tvořena GATE-DLL toolboxem, ve kterém je na začátku výpočtu volána funkce DLLinitXML s parametrem master XML souboru, založeným serverovou aplikací. Poté je možné zavolat funkci DLLAddClient. Ta připojí klienta do master XML. Následně probíhá klasický výpočetní cyklus genetického algoritmu, který má jako ukončovací podmínku volání funkce DLLClientStatus. Příklad typického GATE-DLL klient Matlab kódu: [GA res] = DLLXMLinit('GA','d:\server.xml','restart'); if(res) DLLAddClient; GA = DLLfitness(GA); GA.nGener = GA.nGener + 1; while(~DLLClientStatus) GA = DLLselect(GA,'tournament',10); GA = DLLcross(GA,'pcross',[0.3 30]); GA = DLLmutationHC(GA,'HC12',10,'rand',15); GA = DLLfitness(GA); GA.nGener = GA.nGener + 1; if(mod(GA.nGener,100) == 0) DLLviewProgress(GA,'small'); end end DLLviewProgress(GA,'full'); else fprintf('Chyba pri nacitani XML souboru.\n'); end GA = DLLfreeModel(GA); clear GA res;
52
53
5
PRAKTICKÉ TESTY GATE-DLL
V této kapitole bude provedeno srovnání původního GATE a GATE-DLL týkající se rychlosti výpočtů a využití paměti RAM. Dále se zaměřím na statistické zpracování schopnosti GATE-DLL nalézt řešení optimalizačního problému do určité generace jedinců. V závěru kapitoly budou popsány praktické zkušenosti při testování distribuovaných výpočtů.
5.1
Testovací funkce F6
Tato funkce byla vytvořena pro testování optimalizačních algoritmů zahrnutých v GATE a DLL−GATE toolboxech. Jedná se o funkci, která simuluje optimalizační problém s mnoha lokálními extrémy. Je sestavena v tzv. optimálním vektorizovaném tvaru a je na ní možno testovat optimalizační problémy v libovolné dimenzi prostoru řešení n. F6 ( x) = A ⋅ n +
∑ (x n
2 i
− A ⋅ cos( 2 ⋅ π ⋅ xi2 )
i =1
)
kde: A = 10 n = dimenze prostoru řešení
Zápis funkce F6 v systému Matlab: function fce = f6(x) [r s] = size(x); A = 10; fce = A*s + sum((x.^2-A*cos(2*pi.*x)),2); end Definice testovacího problému:
Řešení testovacího problému:
min{ F6 ( x ) | xi ∈ [−5.1,5.0], i ∈ Ν}
min F6 (0,...,0) = 0
Obr. 25 Testovací funkce F6 a testovací optimalizační problém
Obr. 26 Průběh funkce F6 na rozsahu x = (-5,5)
n
54
5.2
Testování rychlosti GATE vs. GATE-DLL
Při vytváření GATE-DLL jsem uvažoval, jak využít potenciál vícejádrových CPU. Po pár testech jsem zjistil, že systém výpočtů a celá koncepce řešení GATE-DLL je příliš roztříštěná (hlavní cyklus běží v systému Matlab a volají se funkce DLL knihovny) a že nelze provést vhodnou optimalizaci pro vícejádrové CPU (část výpočetního času připadne na volání Matlab funkcí). To ovšem nemění nic na faktu, že na vícejádrových CPU lze spustit systém distribuovaných výpočtů a že na každém jádře CPU lze nechat běžet jednoho klienta. Testovací PC sestava při prováděných testech rychlosti byla následující: AMD Athlon X2 2.5GHz, 2GB RAM. Test 1: Rychlost GA při nastavení: nParam = 3, nBitParam = 64, nIndi = 500, funName = 'F6', funOpt = 'min', iParam = [−5.1 5], iType = [-], mInit = 'random' select(GA,'tournament',10) cross(GA,'pcross',[0.3 5]) mutation(GA,'bitmut',0.01) Bylo testováno při obou typech binárního kódování mCode (BC i GC), průběh 1000 generací GA, měřeno v systému Matlab pomocí funkcí TIC a TOC. GATE: číslo měření 1 2 3 4 5 6 7 8 9 10 BC 32,46 32,45 32,59 32,57 32,35 32,63 32,69 32,79 32,32 32,55 t [s] GC 38,34 38,12 38,20 38,34 38,18 38,71 38,23 38,30 38,26 38,91
průměr 32,540 38,359
GATE-DLL číslo měření BC t [s] GC
1 1,59 2,33
2 1,60 2,33
3 1,60 2,32
4 1,60 2,32
5 1,59 2,32
6 1,60 2,32
7 1,60 2,33
8 1,59 2,36
9 1,60 2,32
10 1,60 2,34
průměr 1,597 2,329
GATE-DLL, přímé volání DLL funkcí: číslo měření 1 2 3 4 BC 0,93 0,95 0,97 0,96 t [s] GC 1,67 1,68 1,67 1,69
5 0,94 1,67
6 0,99 1,68
7 0,93 1,67
8 0,97 1,69
9 0,93 1,69
10 0,99 1,66
průměr 0,956 1,677
40 t [s] 35 30 25 BC GC
20 15 10 5 0 GATE
GATE-DLL
DLL-Direct
Obr. 27 Srovnání rychlostí GATE, GATE-DLL a přímého volání DLL funkcí při GA
55 Z provedených testů rychlosti je zřejmé, že nový GATE-DLL je průměrně 16 až 20krát rychlejší než původní GATE toolbox. Poslední tabulka byla sestavena jen pro zajímavost, jaké rychlosti by bylo možno dosáhnout při přímém volání DLL funkcí (bez obálky Matlab funkcí). Test 2: Rychlost GA-HC při nastavení: nParam = 3, nBitParam = 64, nIndi = 500, funName = 'F6', funOpt = 'min', iParam = [−5.1 5], iType = [-], mInit = 'random' select(GA,'tournament',10) cross(GA,'pcross',[0.3 5]) mutationHC(GA,'HC12',10,'rand',15) Bylo testováno při obou typech binárního kódování mCode (BC i GC), průběh 1000 generací GA-HC, měřeno v systému Matlab pomocí funkcí TIC a TOC. GATE: n t [s]
BC GC
GATE-DLL n BC t [s] GC
1 2 3 4 5 6 7 8 9 10 51,29 52,07 52,50 51,95 52,02 51,25 51,60 51,82 51,14 51,46 71,45 71,87 70,86 72,18 71,23 71,80 71,52 71,72 71,18 71,85
průměr 51,710 71,566
1 5,30 8,03
průměr 5,313 8,107
2 5,45 8,23
3 5,32 8,20
4 5,27 7,94
5 5,28 8,08
6 5,31 8,03
7 5,30 8,05
8 5,34 8,12
9 5,28 8,13
10 5,28 8,26
80 t [s] 70 60 50
BC GC
40 30 20 10 0 GATE
GATE-DLL
Obr. 28 Srovnání rychlostí GATE a GATE-DLL při algoritmu GA-HC I u algoritmu GA-GC je nárůst rychlosti velmi dobrý. Urychlení se zde pohybuje kolem hodnoty 9 až 10násobného zrychlení. Test 3: Rychlost HC algoritmů: Vzhledem k tomu, že koncepce HC algoritmů je v původním GATE jiná než v GATEDLL, nebylo možno je porovnat z hlediska rychlosti. V původním GATE pracují totiž HCA opakovaně tak dlouho, dokud se nezacyklí, kdežto v GATE-DLL jsou implementovány jako jeden krok. Volají se v hlavním programu cyklicky a uživatel volí ukončovací podmínku manuálně.
56
5.3
Test využití paměti RAM
Jelikož jsou hlavní binární struktury v původním GATE řešeny jako pole s datovými položkami typu double, bylo zajímavé srovnat, jak tomu bude u GATE-DLL, kde jsou hlavní binární pole řešena jako datový typ unisgned char. Pro provedení takového testu bylo zvoleno nastavení s mnoha parametry optimalizační úlohy a velkou populací jedinců, aby byl patrný rozdíl mezi GATE a GATE-DLL. Bylo provedeno pět měření a vždy změřena špička (algoritmy v průběhu činnosti alokují dynamicky paměť) paměťového využití celého systému Matlab. Měření bylo zastaveno po 30 sekundách. Po této době bylo změřeno využití paměti samotného systému Matlab a tato hodnota odečtena, aby se získalo čisté využití paměti. Testovací PC sestava při prováděných testech byla následující: AMD Athlon X2 2.5GHz, 2GB RAM. Test 4: Využití paměti při GA: nParam = 50, nBitParam = 64, nIndi = 5000, funName = 'F6', funOpt = 'min', iParam = [−5.1 5], iType = [-], mInit = 'random' select(GA,'tournament',10), cross(GA,'pcross',[0.3 5]), mutation(GA,'bitmut',0.01) Paměťová špička byla měřena programem Process Explorer v10.2 GATE: n 1 2 3 4 5 RAM celkově 624,5 624,0 624,2 620,6 623,3 [MB] Matlab 127,4 129,1 126,4 128,1 126,6
průměr 623,32 127,52
GATE-DLL: n 1 2 3 4 5 RAM celkově 275,5 280,0 279,1 279,3 279,1 [MB] Matlab 122,8 123,8 124,0 123,9 123,9
průměr 278,60 123,68
delta 495,8
delta 154,92
RAM [MB] 500 450 400 350 300 250 200 150 100 50 0 GATE
GATE-DLL
Obr. 29 Srovnání využití paměťového prostoru GATE a GATE-DLL U algoritmů GA-HC bylo využití paměťového prostoru RAM téměř identické jako u GA, tudíž nebylo třeba provádět stejné měření i tam. Jak je vidět z výsledků měření, nový GATE-DLL potřebuje ke své činnosti asi 3krát méně operační paměti než původní GATE při stejném nastavení.
57
5.4
Schopnost nalezení řešení
Heuristické optimalizační metody by měly umožňovat nalezení řešení v přijatelné době a s dostatečně velkou přesností. Bylo by proto ještě dobré statisticky otestovat, jestli tomu tak skutečně je i u GATE-DLL. Test byl proveden pomocí algoritmu GA s nastavením uvedeným níže. Celkem bylo provedeno pět testů, a to schopnost nalézt řešení po 80, 90, 100, 120 a 150 generacích GA. Byla prováděna optimalizace funkce F6, jako hranice přijatelné přesnosti byla stanovena hodnota řešení větší než 10-8. Řešení, která přesností přesáhla hranici 10-15, byla zařazena do kategorie „přesná řešení“. Každý z pěti testů byl zopakován 1000krát, aby byl k dispozici dostatečně velký statistický soubor dat. Nastavení GA: nParam = 4, nBitParam = 64, nIndi = 500, funName = 'F6', funOpt = 'min', iParam = [−5 5], mInit = 'random', mCode = 'GC' select(GA,'tournament',10) cross(GA,'pcross',[0.3 5]) mutation(GA,'bitmut',0.01) Měření bylo opakováno pro každý generační limit 1000krát. Limit nalezených řešení je 10-8. Za přesné řešení je považováno to, které je s přesností větší než 10-15. Za uvázlé řešení se považuje to, u kterého jeden nebo více parametrů uvázlo v lokálním extrému. Generační limit: 80 generací GA
x
~ x
s
8,49600 ⋅ 10−2
9,42180 ⋅10 −12
0, 27844
Nalezených Přesných Uvázlých řešení [%] řešení [%] řešení [%] 81,4
2,4
7,8
Generační limit: 90 generací GA
x
~ x
s
6,96682 ⋅10 −2
2,70006 ⋅ 10−13
0, 29577
Nalezených Přesných Uvázlých řešení [%] řešení [%] řešení [%] 87,9
14,7
5,5
Generační limit: 100 generací GA
x
~ x
s
2,48694 ⋅ 10 −2
1, 42109 ⋅10 −14
0,15099
Nalezených Přesných Uvázlých řešení [%] řešení [%] řešení [%] 93,7
40,3
2,0
Generační limit: 120 generací GA
x
~ x
s
1,55514 ⋅ 10−2
0,00000
0,12039
Nalezených Přesných Uvázlých řešení [%] řešení [%] řešení [%] 96,4
80,4
1,4
Generační limit: 150 generací GA
x
~ x
s
3,98261⋅ 10−3
0,00000
0,06283
Nalezených Přesných Uvázlých řešení [%] řešení [%] řešení [%] 99,2
97,4
0,4
Soubor statistických dat jasně prokázal, že GATE-DLL je schopen nalézt řešení testovacího optimalizačního problému v uspokojivé době (150 generací GA trvalo na testovacím stroji průměrně 0,5 sekundy) a s dostatečnou přesností. Počet uvázlých řešení v optimalizačním problému se přitom s větším počtem generací GA příznivě snižuje.
58
5.5
Srovnání algoritmů GA a GA-HC
Tento test byl zaměřen na to, jaký rozdíl bude při řešení optimalizačního problému pomocí GA a GA-HC algoritmu. GA-HC by měl poskytovat stabilnější metodu k hledání složitějších optimalizačních problémů. Jako testovací optimalizační problém byla opět použita funkce F6 a testování probíhalo následovně: byla provedena opakovaná optimalizace s nastavením uvedeným níže, a to nejdříve algoritmem GA a poté pomocí GA-HC. Nalezená řešení po 100 generacích byla zaznamenána. Tento pokus se 1000krát zopakoval, aby byl k dispozici dostatečně velký soubor statistických dat. Jako hranice přijatelné přesnosti byla stanovena hodnota řešení s přesností větší než 10-8. Řešení, která přesností přesáhla hranici 10 -15 , byla zařazena do kategorie „přesná řešení“. Nastavení GA a GA-HC: nParam = 6, nBitParam = 64, nIndi = 500, funName = 'F6', funOpt = 'min', iParam = [−5 5], mInit = 'random', mCode = 'GC' select(GA,'tournament',10) cross(GA,'pcross',[0.3 5]) mutation(GA,'bitmut',0.01) mutationHC(GA,'HC12',15,'rand',15) Měření bylo opakováno pro každý generační limit 1000krát. Limit nalezených řešení je 10-8. Za přesné řešení je považováno to, které je s přesností větší než 10-15. Za uvázlé řešení se považuje to, u kterého jeden nebo více parametrů uvázlo v lokálním extrému. Algoritmus GA:
~ x
s
1,90257 ⋅ 10−8
0, 45769
x
~ x
s
2,67448 ⋅ 10−14
0,000000
5,334 ⋅ 10−13
x 1,66793 ⋅ 10 −1
Nalezených Přesných Uvázlých řešení [%] řešení [%] řešení [%] 44,4
0,0
13,5
Algoritmus GA-HC: Nalezených Přesných Uvázlých řešení [%] řešení [%] řešení [%] 100,0
85,1
0,0
Z uvedených statistik je zřejmé, že algoritmus GA-HC je podstatně lepší, co se týká nalezení řešení v minimálním počtu generací. Je také vidět, že GA-HC nemá takové problémy s uváznutím řešení jako GA. To však nemění nic na faktu, že GA-HC je o něco pomalejší.
59
5.6
Statistické zobrazení vývoje výpočtů GA
Tento test zobrazuje průběh hledání optima pomocí GA algoritmu. Bylo testováno na funkci F6 a vytvořeny řezy po 10 generacích GA a zaznamenán výsledek. Každé měření bylo zopakováno 100krát, aby byl k dispozici dostatečně velký soubor statistických dat. Výsledkem měření je statistický graf, kde jsou na ose x vynášeny generace a na ose y průměr z nalezených řešení, medián a směrodatná odchylka. Nastavení GA: nParam = 4, nBitParam = 64, nIndi = 500, funName = 'F6', funOpt = 'min', iParam = [−5 5], mInit = 'random', mCode = 'GC' select(GA,'tournament',10) cross(GA,'pcross',[0.3 8]) mutation(GA,'bitmut',0.01) Měření bylo opakováno pro každý generační limit 100krát. GA algoritmus, generační řezy (n = číslo generace): n 10 20 30 40
50
60
70
80
x ~ x s
1,52∙100
7,49∙10-1
5,34∙10-1
4,17∙10-1
2,87∙10-1
2,93∙10-1
6,98∙10-2
1,24∙10-1
1,19∙100
9,95∙10-1
5,22∙10-3
8,74∙10-5
4,68∙10-7
1,37∙10-8
4,12∙10-10
1,65∙10-11
0,9155
0,7383
0,7554
0,6209
0,5984
0,5058
0,2551
0,3416
n
90
100
110
120
130
140
150
160
2,98∙10
2,34∙10-13 0,1706
5,28∙10
-2
1,42∙10-14 0,2194
2,98∙10
-2
9,95∙10
0,00 0,1706
-3
1,99∙10
0,00 0,0995
-2
1,64∙10
0,00
-2
0,00
0,1400
1,27∙10
-15
0,00
0,00
0,1181
9,55∙10
0,00 -15
0,00
2,5 fitness
x ~ x s
-2
2
1,5
1
průměr
0,5
medián
0 0
20
40
60
80
100
120
140
160
generace GA
Obr. 30 Generační řezy průběhu optimalizace F6 10 – 160 generací
60
5.7
Testování distribuovaných výpočtů
V této kapitole bude otestován systém distribuovaných výpočtů, který má prokázat, že rychlost řešení složitého optimalizačního problému je vyšší u systému distribuovaných výpočtů, než u jednoho GATE-DLL. K testování byla opět využita funkce F6, která simulovala složitý optimalizační problém s mnoha parametry. Test byl prováděny následovně: bylo spuštěno n klientů a po jednominutových intervalech hledání optima se zaznamenával nejlepší výsledek, který zobrazovala serverová aplikace. Po 5 minutách byl celý test ukončen. Měření bylo opakováno 5krát pro každých n klientů. Byly provedeny dva testy, jeden při 4 hardwarových strojích spojených pomocí sítě LAN a druhý byl prováděn na jednom HW stroji, kde běželi 4 klienti virtuálně. Nastavení GA, GA-HC: nParam = 100, nBitParam = 64, nIndi = 5000, funName = 'F6', funOpt = 'min', iParam = [−5.1 5], mInit = 'random', mCode = 'GC' Nastavení jednotlivých klientů bylo individuální, ponechala se tak výhoda variabilních výsledků a tím lepší kooperace klientů. Klienti byli po celou dobu měření nastaveni stejně. Algoritmem pro jednoho klienta byl zvolen účinnější GA-HC. Při testování více klientů bylo nastaveno 30% rozdílová hodnota pro automatický restart horších klientů.
Test 1: Hardwarové distribuční stroje HW stroje (průměrné výsledky z pěti měření): n 1 2 4 čas 1 min
3,088∙102
1,881∙102
8,751∙101
2 min
1,841∙102
6,852∙101
3,453∙101
3 min
1,148∙102
2,775∙101
1,849∙101
4 min
7,203∙101
1,496∙101
8,990∙100
5 min
4,602∙101
1,373∙101
4,428∙100
Test 2: Virtuální distribuční stroje Virtuální stroje (průměrné výsledky z pěti měření): n 1 4 čas 1 min
3,088∙102
3,232∙102
2 min
1,841∙102
2,493∙102
3 min
1,148∙102
1,702∙102
4 min
7,203∙101
1,252∙102
5 min
4,602∙101
1,041∙102
Měření výsledků bylo časově náročné, proto jsem měřil vždy pouze pět hodnot u každého testu. Hodnoty fitness jsou tak vysoké, protože vyřešení optimalizačního problému se 100 parametry by zřejmě vyžadovalo hodně času i pro distribuované výpočty. Jen pro zajímavost uvedu mé pozorování práce čtyř HW klientů. Na dvou strojích běžely GA-HC, jeden s nastavením rand a druhý randp. Na zbylých dvou strojích běžely GA s různým nastavením. GA-HC poskytovaly celou dobu konstantní postup a většinu času byli „tahouni“. Naopak GA algoritmy předváděly větší skokové pokroky, obzvláště pokud jim bylo posláno lepší řešení od serveru. Tím se klienti navzájem velmi dobře doplňovali. Jak je z tabulek patrné, čtyři kooperující klienti nalezli za stejný čas řešení průměrně zhruba o jeden řád přesnější, než jeden samostatně pracující GATE-DLL. Čím složitější optimalizační problém, tím více by se zřejmě projevil přínos distribuovaných výpočtů.
61
fitness
350
300
250
200
150
1 klient
100
2 klienti 4 klienti
50
0 0
1
2
3
4
5
6 t [min]
Obr. 31 Časové řezy 1, 2 a 4 klientů pracujících na HW strojích
fitness
350
300
250
200 1 klient 4 klienti
150
100
50
0 0
1
2
3
4
5
Obr. 32 Časové řezy 1 a 4 klientů pracujících na virtuálním stroji (1 CPU)
6 t [min]
62 Z grafů je patrné, že spuštění 2 a 4 klientů na HW strojích propojených v síti LAN výrazně urychlilo výpočet optimalizačního problému. Ovšem spuštění 4 klientů na jednom virtuálním stroji (1 fyzický CPU) mělo nežádoucí vliv na rychlost výpočtu. Klienti se spíše navzájem brzdili a nepomohla ani výměna lepšího řešení mezi klienty.
63
6
ZÁVĚR
Řešení pomocí externí dynamicky linkované knihovny DLL se ukázalo jako velmi efektivní. Jak prokázaly výsledky testování, GATE-DLL toolbox je po většině stránek výkonnější než původní GATE toolbox. Zvýšení rychlosti se pohybuje v rozmezí 9 až 20násobného urychlení. GATE-DLL má také menší požadavky na využití operační paměti RAM počítače. Spotřebuje až 3krát méně operační paměti než původní GATE toolbox. Testy schopnosti nalezení řešení prokázaly, že algoritmy GA i GA-HC dokáží najít požadovaná řešení s dostatečnou přesností a v přijatelném čase ve většině testovaných případů. Algoritmus GA-HC je podstatně efektivnější, co se týče hledání optimálního řešení, v méně generačních cyklech. Distribuované výpočty byly implementovány sice velmi jednouše, ale i tak se jedná o výkonný nástroj k optimalizaci velmi složitých optimalizačních problémů. Umožňují vyhledávat řešení pro optimalizační problémy s více než 900 parametry, kde by jeden GATE−DLL klient hledal řešení velmi dlouho. Čtyři klienti dokáží zvýšit rychlost hledání optima asi na dvojnásobek, ovšem za předpokladu, že každý klient pracuje na samostatném hardwarovém stroji.
64
65
SEZNAM LITERÁRNÍCH ZDROJŮ [1]
MATOUŠEK, Radomil. GATE 2.0 - Toolbox pro heuristickou optimalizaci. In Technical Computing Prague 2005, [online]. 2005 [cit. 10.5.2007]. Dostupné z WWW: http://dsp.vscht.cz/konference_matlab/MATLAB05/prispevky/matousek/matousek.pdf
[2]
TIŠNOVSKÝ, Pavel. Fixed Point Arithmetic. Root.cz [online]. 2006. [cit. 9.5.2007] Dostupný na WWW: http://www.root.cz/clanky/fixed-point-arithmetic/
[3]
SEKAJ, Ivan. Evolučné výpočty a ich využitie v praxi. Iris. Bratislava, 2005. 159 s. ISBN 80-89018-87-4
[4]
MATOUŠEK, Radomil. Vybrané metody umělé inteligence – implementace a aplikace. Brno, 2004. Disertační práce FSI VUT Brno 2004.
[5]
MSDN Library 2005. [online]. Dostupné z WWW: http://msdn2.microsoft.com/en-us/default.aspx
[6]
Builder.cz. [online]. Dostupné z WWW: http://www.builder.cz/
[7]
cplusplus.com [online]. Dostupné z WWW: http://www.cplusplus.com/
[8]
CodeGuru [online]. Dostupné z WWW: http://www.codeguru.com/
[9]
Matlab help. [online]. Dostupné z WWW: http://www.mathworks.com/access/helpdesk/help/techdoc/matlab.shtml
