pro omezené návrhové prostory Optimization of uniformity of computer experiments for constrained design spaces

ˇ ´ VYSOKE ´ UCEN ˇ Í TECHNICKE ´ V PRAZE CESK E Fakulta stavebn´ı Katedra mechaniky

Optimalizace uniformity poˇ c´ıtaˇ cov´ ych n´ avrh˚ u pro omezen´ e n´ avrhov´ e prostory Optimization of uniformity of computer experiments for constrained design spaces

Diplomová práce

Studijn´ı program: Stavebn´ı inˇzen´ yrstv´ı Studijn´ı obor: Materiálové inˇzen´ yrstv´ı Vedouc´ı práce: doc. Ing. Matˇej Lepˇs, Ph.D.

Bc. Eva Myˇ s´ akov´ a Praha 2013

ˇ Cestn´ e prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem tuto diplomovou práci vypracovala samostatnˇe pouze za odborného veden´ı vedouc´ıho diplomové práce doc. Ing. Matˇeje Lepˇse, Ph.D. Dále prohlaˇsuji, ˇze veˇskeré podklady, ze kter´ ych jsem ˇcerpala, jsou uvedeny v seznamu pouˇzité literatury.

Datum:

Podpis:

3

Na tomto m´ıstˇe bych ráda srdeˇcnˇe podˇekovala doc. Ing. Matˇeji Lepˇsovi, Ph.D. za jeho cenné pˇripom´ınky, nekoneˇcnou trpˇelivost a ochotu pˇri veden´ı mé diplomové práce.

4

Abstrakt Návrh experiment˚ u - design of experiments (DoE) pˇredstavuje základn´ı a ned´ılnou ˇcást experimentován´ı v mnoha oblastech vˇedy a v´ yzkumu stejnˇe jako v procesu optimalizace v´ yrobn´ıch proces˚ u i v´ yrobk˚ u samotn´ ych. Má zásadn´ı v´ yznam pˇri tvorbˇe a testován´ı metamodel˚ u, v citlivostn´ı anal´ yze ˇci ve spolehlivostn´ıch v´ ypoˇctech. V této práci se vˇenujeme pˇr´ıpad˚ um, v nichˇz jsou na vstupn´ı parametry experimentu kladeny omezuj´ıc´ı podm´ınky, jeˇz ˇcin´ı tyto parametry vzájemnˇe závisl´ ymi. Takové omezuj´ıc´ı podm´ınky mˇen´ı tvar návrhového prostoru z regulárn´ıho prostoru hyperkrychle na prostor obecnˇe nepravideln´ y. Speciáln´ım pˇr´ıpadem experimentu s omezen´ım je návrh smˇesi, ve kterém tvoˇr´ı jednotlivé vstupn´ı parametry (zastoupen´ı sloˇzek smˇesi) jednotkov´ y objem nebo hmotnost. V práci se vˇenujeme metodám tvorby návrh˚ u experiment˚ u v omezen´ ych návrhov´ ych prostorech a jejich hodnocen´ı. Pro to jsou zvolena dvˇe kritéria zamˇeˇrená na rovnomˇernost pokryt´ı návrhového prostoru - kritérium Euklidovské Maximin vzdálenosti (EM M ) a kritérium miniMax (mM ). Kaˇzdé z tˇechto kritéri´ı je schopné jasnˇe poukázat na závaˇzné nedostatky návrhu. Vyhodnocen´ı druhého ze jmenovan´ ych kritéri´ı nav´ıc samo o sobˇe pˇredstavuje problém, jemuˇz se v práci vˇenujeme. Jednotlivé metody tvorby návrh˚ u aplikované na nˇekolik konkrétn´ıch ilustraˇcn´ıch pˇr´ıklad˚ u jsou v práci porovnány z pohledu kvality v´ ysledn´ ych návrh˚ u (pomoc´ı uveden´ ych kritéri´ı) a ˇcasové nároˇcnosti.

5

Abstract Design of experiments (DoE) creates an essential and integral part of any experimentation in many fields of science research and optimization of production processes and products themselves. It is also essentially important for meta-models development, sensitivity analysis or probability calculations. This thesis is focused on cases with limiting conditions put on input parameters like dependency of input parameters. Presence of limiting conditions changes shape of design space from regular hypercube to a generally irregular constrained design space. A special case of this type of experiment is a mixture experiment, where individual parameters (ingredients) form a unity volume or weight. In this thesis we are focused on methods for creation of experimental designs in constrained design spaces as well as on their ranking. For this purpose two space-filling criteria are chosen - Euclidean Maximin distance (EM M ) and criterion miniMax (mM ). Both these criteria are able to point out serious shortcomings of the design. Evaluation of the second mentioned criterion is a problem itself which is also discussed in this thesis. Individual methods for creation of experimental designs applied on several illustrative examples are compared in terms of quality of resulting designs (evaluated by mentioned criteria) and computational demands.

6

Kl´ıˇ cov´ a slova návrh experiment˚ u, omezené návrhové prostory, omezuj´ıc´ı podm´ınky, návrh smˇesi, simplex, konvexn´ı polytop, rovnomˇernost pokryt´ı, Maximin, miniMax, evoluˇcn´ı strategie, Delaunayova triangulace, ploˇsné souˇradnice, implementace

Keywords design of experiments, constrained design spaces, limiting conditions, mixture experiment, simplex, convex polytope, space-filling, Maximin, miniMax, evolution strategy, Delaunay triangulation, barycentric coordinates, implementation

7

Obsah Obsah

8

Seznam obr´ azk˚ u

10

´ 1 Uvod 12 1.1 Návrhové prostory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.2 Návrh smˇesi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3 Návrhy v obecn´ ych omezen´ ych spojit´ ych prostorech . . . . . . . . . . . . . 17 2 Krit´ eria uniformity 2.1 Euklidovská Maximin vzdálenost (EM M ) . 2.2 Kritérium miniMax (mM ) . . . . . . . . . . 2.2.1 Pˇresná hodnota kritéria miniMax . . 2.2.2 Evoluˇcn´ı strategie pro odhad hodnoty

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . kritéria miniMax

3 Metody pro tvorbu n´ avrh˚ u v omezen´ ych n´ avrhov´ ych 3.1 Generátor náhodn´ ych bod˚ u . . . . . . . . . . . . . . . 3.2 Metoda LHS na opsaném hyperkvádru . . . . . . . . . 3.3 Metoda odeb´ırán´ı bod˚ u z pˇrehuˇstˇeného návrhu . . . . . 3.3.1 Metoda ub´ ır´ an´ ı . . . . . . . . . . . . . . . . . 3.3.2 Metoda ub´ ır´ an´ ı NEW . . . . . . . . . . . . . . . 3.4 Nástroj Distmesh . . . . . . . . . . . . . . . . . . . . . 3.5 Simplexové mˇr´ıˇzkové (lattice) návrhy . . . . . . . . . . 4 Zp˚ usoby vracen´ı bod˚ u opustivˇ s´ıch dom´ enu 4.1 Kolm´ y pr˚ umˇet na facetu . . . . . . . . . . . 4.2 Nulován´ı záporn´ ych ploˇsn´ ych souˇradnic . . . 4.3 Pomocná sada bod˚ u uvnitˇr domény . . . . . 4.4 Porovnán´ı . . . . . . . . . . . . . . . . . . .

8

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

prostorech . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . . . .

. . . .

. . . .

. . . . . . .

. . . .

. . . .

. . . . . . .

. . . .

. . . .

19 20 20 21 23

. . . . . . .

25 27 28 29 29 29 30 31

. . . .

33 34 35 36 37

OBSAH

5 Pˇ r´ıklady aplikace metod 5.1 Pˇr´ıklady návrh˚ u s mal´ ym poˇctem bod˚ u ve 2D a ve 3D . . . . . . . . . . . . . . . . . . . . . 5.2 Návrh smˇesi . . . . . . . . . . . . . . . . . . . 5.2.1 Trojsloˇzková smˇes . . . . . . . . . . . . ˇ 5.2.2 Sestisloˇ zková smˇes . . . . . . . . . . .

39 . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

6 Implementace

39 41 41 43 44

7 V´ ysledky 45 7.1 Porovnán´ı metod vyhodnocen´ı kritéria miniMax . . . . . . . . . . . . . . . 45 7.2 Porovnán´ı metod tvorby návrh˚ u experiment˚ u . . . . . . . . . . . . . . . . . 47 8 Z´ avˇ er

51

Literatura

52

A Pˇ rehled prvk˚ u (0-5)-dimenzion´ aln´ıho simplexu a hyperkrychle

57

B Algoritmus pro v´ ypoˇ cet EM M

58

C Delaunayova triangulace

59

D Ploˇ sn´ e souˇ radnice

61

E V´ ypoˇ cet hodnoty krit´ eria miniMax v regul´ arn´ım prostoru E.1 Pˇresné ˇreˇsen´ı . . . . . . . . . . . . . . . . . . . . . . . . . . E.2 Sériová evoluˇcn´ı strategie . . . . . . . . . . . . . . . . . . . . E.3 Paraleln´ı evoluˇcn´ı strategie . . . . . . . . . . . . . . . . . . . E.4 Porovnán´ı a shrnut´ı . . . . . . . . . . . . . . . . . . . . . . .

63 63 64 66 67

F Ruˇ cn´ı v´ ypoˇ cet hled´ an´ı vrchol˚ u polytopu pomoc´ı LP

9

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

70

Seznam obr´ azk˚ u 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8

Návrh experiment˚ u. . . . . . . . . . . . . . . . . . . . . Porovnán´ı návrh˚ u experiment˚ u. . . . . . . . . . . . . . Tvary návrhov´ ych prostor˚ u ve 3D. . . . . . . . . . . . Transformace návrhu z regulárn´ıho prostoru. . . . . . . Spojit´ y a diskrétn´ı omezen´ y návrhov´ y prostor ve 2D. . Návrhov´ y prostor pro návrh smˇesi. . . . . . . . . . . . Návrhov´ y prostor pro návrh smˇesi s dalˇs´ım omezen´ım. Doporuˇcen´ y postup ˇcetby. . . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

13 13 14 15 15 16 17 18

2.1 2.2 2.3 2.4

Kritéria Maximin a miniMax. . V´ ypoˇcet pˇresné hodnoty kritéria Sériová evoluˇcn´ı strategie. . . . Paraleln´ı evoluˇcn´ı strategie. . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

19 22 23 24

3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10

1. skupina metod tvorby . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2. skupina metod tvorby . . . . . . . . . . . . . . . . . . . . . . . . . . . . Vrcholov´ y simplex. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Varianty rozdˇelen´ı bod˚ u do simplex˚ u. . . . . . . . . . . . . . . . . . . . . . Pˇr´ıklady LHS návrhu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Pouˇzit´ı LHS v opsaném hyperkvádru. . . . . . . . . . . . . . . . . . . . . . Odeb´ırán´ı z pˇrehuˇstˇeného návrhu. . . . . . . . . . . . . . . . . . . . . . . . Tvorba rovnomˇerné s´ıtˇe z náhodnˇe vytvoˇren´ ych bod˚ u nástrojem Distmesh. Pˇr´ıklady simplexov´ ych lattice návrh˚ u. . . . . . . . . . . . . . . . . . . . . . Aplikace simplexov´ ych lattice návrh˚ u ve ztriangulované doménˇe. . . . . . .

25 26 26 27 28 29 30 31 31 32

4.1 4.2 4.3 4.4 4.5

Posun Posun Posun Posun Posun

33 34 34 35 36

bod˚ ubod˚ ubod˚ ubod˚ ubod˚ u-

. . . . . . miniMax. . . . . . . . . . . . .

kolm´ y pr˚ umˇet. . . . . . . nejbliˇzˇs´ı bod ve vrcholu. kolm´ y pr˚ umˇet - ˇreˇsen´ı na nulován´ı záporné pl. s. . pomocná sada. . . . . . .

10

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . . . . . . . . . . . . . celé doménˇe. . . . . . . . . . . . . . . . .

. . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

´ U ˚ SEZNAM OBRAZK 4.6 4.7

P˚ ulen´ı intervalu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Porovnán´ı zp˚ usob˚ u vracen´ı bod˚ u. . . . . . . . . . . . . . . . . . . . . . . . 38

5.1 5.2 5.3

Pˇr´ıklady návrh˚ u s mal´ ym poˇctem bod˚ u ve 2D a 3D. . . . . . . . . . . . . . 40 Mnoˇzina pˇr´ıpustn´ ych ˇreˇsen´ı v kartézské soustavˇe. . . . . . . . . . . . . . . 42 Mnoˇzina pˇr´ıpustn´ ych ˇreˇsen´ı v trojosé soustavˇe. . . . . . . . . . . . . . . . . 42

7.1 7.2 7.3

V´ ysledky evoluˇcn´ı strategie pro vyˇc´ıslen´ı mM . . . . . . . . . . . . . . . . . 46 V´ ysledky metod tvorby na 2D a 3D pˇr´ıkladech. . . . . . . . . . . . . . . . 48 V´ ysledky metod tvorby na pˇr´ıkladech návrh˚ u smˇes´ı. . . . . . . . . . . . . . 49

C.1 Triangulace. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 C.2 Dualita DT a VD. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 D.1 Ploˇsné souˇradnice. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 D.2 Trojos´ y souˇradnicov´ y systém a ploˇsné souˇradnice. . . . . . . . . . . . . . . 62 D.3 Urˇcen´ı polohy bodu pomoc´ı ploˇsn´ ych souˇradnic. . . . . . . . . . . . . . . . 62 E.1 E.2 E.3 E.4 E.5 E.6 E.7 E.8 E.9

miniMax I. . . . . . . . . . . . . . . . . . . . . . . . . . . . miniMax II. . . . . . . . . . . . . . . . . . . . . . . . . . . Sériová evoluˇcn´ı strategie. . . . . . . . . . . . . . . . . . . Paraleln´ı evoluˇcn´ı strategie - zp˚ usoby dˇelen´ı na subdomény. Paraleln´ı evoluˇcn´ı strategie ve 2D. . . . . . . . . . . . . . . Paraleln´ı evoluˇcn´ı strategie. . . . . . . . . . . . . . . . . . Speed-up paraleln´ı ES. . . . . . . . . . . . . . . . . . . . . Boxplot hodnot mM . . . . . . . . . . . . . . . . . . . . . . V´ yvoj hodnoty mM v pr˚ ubˇehu v´ ypoˇctu. . . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

63 64 65 66 66 67 68 68 69

F.1 F.2 F.3 F.4 F.5

Simplexová tabulka obecnˇe. Simplexové tabulky ˇc. 1-3. . Simplexové tabulky ˇc. 4-6. . Simplexové tabulky ˇc. 7-9. . Simplexové tabulky ˇc. 10-12.

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

70 71 72 73 74

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

11

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

Kapitola 1 ´ Uvod ˇadné mnoˇzstv´ı experiment˚ Z´ u nem˚ uˇze prokázat, ˇze mám pravdu; jediný staˇc´ı k pro” 1 kázán´ı opaku.“ Albert Einstein. Provádˇen´ı experiment˚ u je nepostradatelnou a nesˇcetnˇekrát opakovanou ˇcinnost´ı nejen kaˇzdého vˇedce, programátora, návrháˇre, v´ yrobce, ale i ˇclovˇeka v kaˇzdodenn´ım ˇzivotˇe. Experimentem chápeme proveden´ı testu za urˇcit´ ych podm´ınek s c´ılem zjiˇstˇen´ı odezvy. Pˇr´ıkladem nám m˚ uˇze b´ yt chemick´ y experiment, ve kterém vol´ıme zastoupen´ı jednotliv´ ych slouˇcenin a zjiˇst’ujeme napˇr´ıklad mnoˇzstv´ı uvolnˇené energie pˇri reakci. Nebo návrh v´ yrobku, kdy vol´ıme rozmˇery jednotliv´ ych prvk˚ u a zaj´ımá nás vliv takové volby napˇr´ıklad na pevnost nebo ˇzivotnost. Za experiment ovˇsem m˚ uˇzeme povaˇzovat i peˇcen´ı nového mouˇcn´ıku - vol´ıme mnoˇzstv´ı (pomˇery) jednotliv´ ych surovin a zjiˇst’ovanou odezvou m˚ uˇze b´ yt zpracovatelnost tˇesta nebo chutnost v´ ysledného produktu. Experiment tedy slouˇz´ı ke zjiˇstˇen´ı odezvy (reakce) nˇejakého systému na urˇcité hodnoty vstupn´ıch parametr˚ u, respektive k z´ıskán´ı pˇredstavy o chován´ı takového systému (a následnˇe k vyˇsˇs´ı pravdˇepodobnosti, ˇze budeme schopni chován´ı systému v r˚ uzn´ ych situac´ıch správnˇe pˇredv´ıdat). V ideáln´ım pˇr´ıpadˇe bychom tedy provedli co nejvˇetˇs´ı mnoˇzstv´ı experiment˚ u (s r˚ uzn´ ymi vstupn´ımi parametry) a z´ıskali tak informaci, jak systém zareaguje v r˚ uzn´ ych situac´ıch. Ve skuteˇcnosti b´ yvá ovˇsem poˇcet experiment˚ u, jeˇz je moˇzné provést, znaˇcnˇe limitován (z d˚ uvod˚ u finanˇcn´ıch, ˇcasov´ ych, ˇci faktick´ ych). Je proto zapotˇreb´ı vˇenovat znaˇcnou pozornost vhodnému naplánován´ı experiment˚ u, konkrétnˇe volbˇe kombinac´ı hodnot vstupn´ıch parametr˚ u pro jednotlivá proveden´ı. K tomu slouˇz´ı návrh experiment˚ u - design of experiments (DoE). Návrh experiment˚ u je soubor návrhov´ ych bod˚ u (jejich poˇcet odpov´ıdá poˇctu moˇzn´ ych uskuteˇcnˇen´ı experimentu), jejichˇz souˇradnice odpov´ıdaj´ı konkrétn´ım hodnotám vstupn´ıch 1

P˚ uvodnˇe No amount of experimentation can ever prove me right; a single experiment can prove me ” wrong.“ Albert Einstein [Wynn and Wiggins, 1997].

12

´ KAPITOLA 1. UVOD

Obrázek 1.1: Návrh experiment˚ u. Obrázek vlevo ukazuje návrh experiment˚ u ve 2D. Obrázek vpravo pak zachycuje aplikaci návrhu experiment˚ u - urˇcen´ı odezvy systému (ˇcervené body) v návrhov´ ych bodech (ˇcerné body). Pro ilustraci byla pouˇzita funkce peaks dostupná v programu MATLAB.

parametr˚ u (promˇenn´ ych). V tˇechto bodech je následnˇe provedeno vyˇc´ıslen´ı (proveden experiment s odpov´ıdaj´ıc´ımi hodnotami parametr˚ u). Obrázek 1.1 znázorˇ nuje návrh experiment˚ u se dvˇema vstupn´ımi parametry. Tvorbˇe návrhu experiment˚ u je tˇreba vˇenovat znaˇcnou pozornost; je zˇrejmé, ˇze v závislosti na pouˇzitém návrhu m˚ uˇzeme z´ıskat znaˇcnˇe odliˇsnou pˇredstavu o chován´ı systému. Obrázek 1.2 ukazuje rozd´ılné návrhy z pohledu rovnomˇernosti pokryt´ı návrhového prostoru. Pouˇzit´ım návrhu vpravo bychom jistˇe z´ıskali o chován´ı systému lepˇs´ı pˇredstavu.2 1

0 0

0 0 0.5 x1

0.5 1 x1

0.5

0 1 0

x2

2

0.5

x

0.5

1

1

x2

x2

1

0.5

0 0 0.5 x1

0.5 1 x1

1

Obrázek 1.2: Porovnán´ı návrh˚ u experiment˚ u. Vlevo nekvalitn´ı návrh, vpravo návrh rovnomˇernˇe pokr´ yvaj´ıc´ı návrhov´ y prostor (návrhovou doménu). 2

Existuj´ı samozˇrejmˇe pˇr´ıpady, kdy nen´ı jedin´ ym kritériem pro hodnocen´ı návrhu rovnomˇernost pokryt´ı n´ avrhového prostoru. V mnoha aplikac´ıch je zámˇernˇe zahuˇst’ován“ návrhov´ ymi body urˇcit´ y ” konkrétn´ı prostor v n´ avrhové doménˇe.

13

´ KAPITOLA 1. UVOD

Obecnˇe je u návrh˚ u experiment˚ u d˚ uraz kladen pˇredevˇs´ım na zm´ınˇenou rovnomˇernost pokryt´ı (space-filling) a ortogonalitu. Je tˇreba zm´ınit, ˇze návrhy experiment˚ u se liˇs´ı rovnˇeˇz podle toho, pro jakou aplikaci jsou urˇceny. Jak jiˇz bylo zm´ınˇeno, setkáváme se s touto problematikou v mnoha oblastech lidské ˇcinnosti. P˚ uvodnˇe byly návrhy experiment˚ u pouˇzity v chemii, dnes se s nimi setkáváme kromˇe vˇedeck´ ych discipl´ın v mnoha odvˇetv´ıch pr˚ umyslu i ve sluˇzbách ˇci v marketingu. Nezastupitelnou roli hraj´ı v experimentech poˇc´ıtaˇcov´ ych (simulac´ıch), ve spolehlivostn´ıch v´ ypoˇctech, ˇci citlivostn´ıch anal´ yzách. O reáln´ ych experimentech (fyzikáln´ıch, chemick´ ych [Liang et al., 2001]...), jejich navrhován´ı i anal´ yze pojednává kniha [Montgomery, 2000], poˇc´ıtaˇcov´ ym experiment˚ um se pak vˇenuj´ı napˇr´ıklad autoˇri v [Sacks et al., 1989] nebo [Fang et al., 2006]. Rozd´ıl mezi experimenty reáln´ ymi a poˇc´ıtaˇcov´ ymi je moˇzné demonstrovat napˇr´ıklad na tom, zda pro stejné kombinace vstupn´ıch parametr˚ u obdrˇz´ıme stejnou odezvu systému. U poˇc´ıtaˇcov´ ych experiment˚ u tomu tak zpravidla je (pokud nen´ı do modelu zámˇernˇe vloˇzen nˇejak´ y prvek náhodnosti), zat´ımco u reáln´ ych experiment˚ u toto platit nemus´ı. Proto je napˇr´ıklad odliˇsnˇe nahl´ıˇzeno na pˇr´ıtomnost duplikovan´ ych návrhov´ ych bod˚ u v návrz´ıch experiment˚ u pro jednotlivá odvˇetv´ı.

1.1

N´ avrhov´ e prostory

Tvorba návrh˚ u experiment˚ u se liˇs´ı pˇredevˇs´ım v závislosti na tvaru návrhového prostoru. Ten je dán vˇsemi pˇr´ıpustn´ ymi kombinacemi hodnot vstupn´ıch parametr˚ u. V pˇr´ıpadˇe, ˇze jsou jednotlivé návrhové parametry (promˇenné) nezávislé a kaˇzd´ y z nich má zadané urˇcité rozdˇelen´ı, je návrhov´ ym prostorem hyperkrychle (Obrázek 1.3a). I v pˇr´ıpadˇe, ˇze parametry nemaj´ı stejné rozdˇelen´ı, m˚ uˇzeme návrh experiment˚ u vytvoˇrit rovnomˇern´ y v jedn noduché hyperkrychli [0, 1] (kde n je dimenze/poˇcet parametr˚ u) a jednotlivé parametry pak pomoc´ı inverzn´ı kumulativn´ı distribuˇcn´ı funkce pˇrevést do zadaného rozdˇelen´ı [Myˇsáková and Lepˇs, 2013c], jak je znázornˇeno na Obrázku 1.4. Velmi ˇcast´ ym pˇr´ıpadem experimentu s omezen´ım je návrh smˇesi (mixture experiment), ve kterém tvoˇr´ı jednotlivé vstupn´ı parametry jednotkovou váhu ˇci objem. Tomuto typu

(a) Hyperkrychle.

(b) Simplex.

(c) Polytop.

Obrázek 1.3: Tvary návrhov´ ych prostor˚ u ve 3D. 14

´ KAPITOLA 1. UVOD

1 0.9

8

0.8

7

0.7

6 5

0.5

x2

u2

0.6

4

0.4 3

0.3 2

0.2

1

0.1 0 0

0.2

0.4

0.6

0.8

1

-5

0 x

u

1

5

1

(a) Rovnomˇern´ y n´ avrh v regul´ arn´ım prostoru (b) Pˇreveden´ı do zadan´ ych rozdˇelen´ı: 1. parametr hyperkrychle (ve 2D: ˇctverec). (osa x1 ) - normáln´ı rozdˇelen´ı (µ = 0, σ = 1), 2. parametr (osa x2 ) - exponenciáln´ı rozdˇelen´ı (µ = 1).

Obrázek 1.4: Transformace návrhu z regulárn´ıho prostoru hyperkrychle [0, 1]n (kde n je dimenze/poˇcet parametr˚ u) do prostoru daného zadan´ ymi rozdˇelen´ımi jednotliv´ ych parametr˚ u.

x 2 x2

x2 x2

experimentu odpov´ıdá návrhov´ y prostor ve tvaru simplexu (Obrázek 1.3b). V´ıce se tomuto druhu experimentu vˇenuje následuj´ıc´ı Sekce. Jsou-li zadány jiné nebo dalˇs´ı omezuj´ıc´ı podm´ınky, je návrhov´ ym prostorem polytop3 (Obrázek 1.3c). Zásadn´ı rozd´ıl v tvorbˇe návrh˚ u experiment˚ u (a v podobˇe návrhového prostoru) je

x1 x1

x1 x1

(a) Spojit´ y n´ avrhov´ y prostor je d´ an nekoneˇcn´ ym poˇctem pˇr´ıpustn´ ych kombinac´ı vstupn´ıch parametr˚ u (modrá plocha).

(b) Diskrétn´ı návrhov´ y prostor je dán koneˇcn´ ym poˇctem pˇr´ıpustn´ ych kombinac´ı vstupn´ıch parametr˚ u (modré body).

Obrázek 1.5: Pˇr´ıklady spojitého a diskrétn´ıho omezeného návrhového prostoru ve 2D. 3

V této pr´ aci uvaˇzujeme pouze konvexn´ı polytopy.

15

´ KAPITOLA 1. UVOD

rovnˇeˇz dán t´ım, zda mohou jednotlivé parametry nab´ yvat libovoln´ ych hodnot v rámci sv´ ych mez´ı - jsou spojité, ˇci zda je poˇcet pˇr´ıpustn´ ych hodnot koneˇcn´ y - jsou diskrétn´ı. Rozd´ıl ukazuje Obrázek 1.5.

1.2

N´ avrh smˇ esi

Speciáln´ı, ale velmi ˇcast´ y pˇr´ıpad experimentu s omezen´ ym návrhov´ ym prostorem je návrh smˇesi. Je dán omezuj´ıc´ı podm´ınkou x1 + x2 + ... + xn = 1,

0 ≤ xi ≤ 1,

i = 1, ..., n ,

(1.1)

kde n odpov´ıdá poˇctu sloˇzek dané smˇesi. Tato samotná podm´ınka urˇcuje tvar návrhového prostoru jako (n − 1)-dimenzionáln´ı simplex (Obrázek 1.3b a 1.6). Hodnoty jednotliv´ ych parametr˚ u (zastoupen´ı sloˇzek smˇesi) je dáno ploˇsn´ ymi (troj´ uheln´ıkov´ ymi, barycentrick´ ymi) souˇradnicemi bod˚ u v simplexu [Cruise, 1966] (v´ıce v Pˇr´ıloze D). Jejich poˇcet je vˇzdy o jednu vyˇsˇs´ı neˇz dimenze odpov´ıdaj´ıc´ıho simplexu. Napˇr´ıklad návrhu smˇesi s pˇeti sloˇzkami tedy odpov´ıdá návrhov´ y prostor ve tvaru 4-dimenzionáln´ıho simplexu; kaˇzd´ y bod v tomto simplexu je moˇzné popsat pˇeti barycentrick´ ymi souˇradnicemi, jejichˇz souˇcet je vˇzdy roven jedné. Kromˇe základn´ı omezuj´ıc´ı podm´ınky návrhu smˇesi (Rovnice 1.1) b´ yvaj´ı zpravidla pˇr´ıtomny jeˇstˇe dalˇs´ı omezuj´ıc´ı podm´ınky: ty nejˇcastˇeji stanovuj´ı limity zastoupen´ı jednotliv´ ych sloˇzek smˇesi. Kaˇzdá taková podm´ınka mˇen´ı tvar návrhového prostoru - oˇrezává“ ” p˚ uvodn´ı simplex, jak je vidˇet napˇr´ıklad na Obrázku 1.7. Návrhov´ ym prostorem se pak x3 1

1

x2

0

1

x1

1 0

x1 x1 + x2 = 1

1

x2

x1 + x2 + x3 = 1

(a)

(b)

Obrázek 1.6: Návrhov´ y prostor pro návrh smˇesi se dvˇema (vlevo) a tˇremi (vpravo) sloˇzkami.

16

´ KAPITOLA 1. UVOD

stává obecnˇe nepravideln´ y, ale vˇzdy konvexn´ı polytop. Návrhu experiment˚ u pro návrh smˇesi je vˇenována pozornost jiˇz nˇekolik desetilet´ı, jak je popsáno v [Khuri, 2006, Kapitola 12] nebo v [Chan, 2000]. Pˇred nástupem poˇc´ıtaˇcov´ ych experiment˚ u byly pouˇz´ıvány klasické ˇsablony o nˇekolika návrhov´ ych bodech [Cornell, 1973, Cornell, 1979]. Napˇr´ıklad mˇr´ıˇzkové návrhy (v´ıce v Kapitole 3) se ve vhodn´ ych pˇr´ıpadech [JMP, 2005] stále ˇcasto vyuˇz´ıvaj´ı. V dneˇsn´ı dobˇe se vˇsak pozornost zamˇeˇruje sp´ıˇse na poˇc´ıtaˇcovˇe optimalizované návrhy experiment˚ u [Lepˇs, 2009, Kapitola 2].

1.3

N´ avrhy v obecn´ ych omezen´ ych spojit´ ych prostorech

Tato práce se zab´ yvá návrhy experiment˚ u v omezen´ ych spojit´ ych prostorech. Návrhov´ ymi doménami tedy jsou simplexy nebo obecné konvexn´ı polytopy. Jelikoˇz uvaˇzujeme tvorbu návrh˚ u pro experimenty poˇc´ıtaˇcové, je pro nás základn´ım poˇzadavkem rovnomˇernost pokryt´ı návrhového prostoru. Metodami pro tvorbu takov´ ych návrh˚ u se zab´ yvá ˇrada autor˚ u. Napˇr´ıklad autoˇri v ˇclánku [Hofwing and Strömberg, 2010] optimalizuj´ı D-optimalitu návrh˚ u v omezen´ ych prostorech pomoc´ı sekvenˇcn´ıho lineárn´ıho programován´ı v kombinaci s genetick´ ym algoritmem. [Draguljic et al., 2012] se zamˇeˇruje na projekˇcn´ı vlastnosti návrh˚ u experiment˚ u v omezen´ ych prostorech. Podm´ınˇené rozdˇelen´ı pravdˇepodobnosti v metodách Monte Carlo je pouˇzito pro tvorbu rovnomˇern´ ych návrh˚ u v [Fang and Yang, 2000]. [Petelet et al., 2010] pˇri tvorbˇe vycház´ı z LHS návrhu (viz Sekci 3.2), na kterém provád´ı permutace, dokud (0,0,1)

x3

Podm´ınka návrhu smˇesi: x1 + x2 + x3 = 1

0.8 x3 = 0.7 0.6

0.2 0.4 0.6 x3 = 0.1 x1

(1/4,1/4,1/2) Limity pro zastoupen´ ı sloˇzek: (0,1/2,1/2) (1/2,0,1/2) x2 ≤ 0, 6 (1/3,1/3,1/3) x3 ≥ 0, 1 x3 ≤ 0, 7 (1/2,1/4,1/4) (1/4,1/2,1/4)

0.2 0.4 0.4 0.2

0.6

0.8

0.8

x2 = 0.6

x2

(1,0,0)

(1/2,1/2,0)

(0,1,0)

Obrázek 1.7: Zmˇena podoby návrhového prostoru pro návrh smˇesi pˇri zaveden´ı limit˚ u pro ˇ zastoupen´ı jednotliv´ ych sloˇzek. Cervené u ´seˇcky znaˇc´ı hraniˇcn´ı pˇr´ımky podm´ınek, r˚ uˇzovˇe ˇsrafovaná oblast pak v´ ysledn´ y návrhov´ y prostor.

17

´ KAPITOLA 1. UVOD

nejsou splnˇeny omezuj´ıc´ı podm´ınky. Dva pˇr´ıstupy jsou popsány autory v [Prescott, 2008]: pro domény ve tvaru simplexu nebo simplexu bl´ızkém je navrˇzen postup zaloˇzen´ y na tzv. sphere packingu - tedy plnˇen´ı domény dan´ ym poˇctem hyperkoul´ı. Návrhov´ ymi body jsou pak stˇredy tˇechto hyperkoul´ı. Pro dlouhé a u ´zké domény podobné obdéln´ık˚ um potom autoˇri navrhuj´ı pˇrizp˚ usoben´ı pravidelné s´ıtˇe. V této práci se vˇenujeme tvorbˇe optimalizovan´ ych (z pohledu rovnomˇernosti poˇ en´ı práce kryt´ı) návrh˚ u experiment˚ u ve spojitém omezeném návrhovém prostoru. Clenˇ je následuj´ıc´ı. V Kapitole 2 pˇredstav´ıme dvˇe kritéria zvolená pro hodnocen´ı i optimalizaci jednotliv´ ych návrh˚ u. Vyhodnocen´ı jednoho z nich je samo o sobˇe nároˇcné, je mu proto vˇenována znaˇcná pozornost. Kapitola 3 se vˇenuje vlastn´ım metodám tvorby návrh˚ u. Dále je v Kapitole 4 ˇreˇsen problém vracen´ı bod˚ u, které opust´ı návrhovou doménu, zpˇet na jej´ı povrch. To m˚ uˇze b´ yt zapotˇreb´ı jak pˇri tvorbˇe návrhu, tak pˇri jeho hodnocen´ı. Pˇr´ıklady, na nˇeˇz jsou pˇredstavené metody aplikovány, jsou uvedeny v Kapitole 5. Kapitola 6 se vˇenuje popisu implementace uveden´ ych algoritm˚ u. V Kapitole 7 nalezneme v´ ysledky z´ıskané pouˇzit´ım metod na uveden´ ych pˇr´ıkladech následované shrnut´ım v Kapitole 8. Práce obsahuje rovnˇeˇz ˇradu pˇr´ıloh, Obrázek 1.8 proto ukazuje doporuˇcen´ y postup jej´ı ˇcetby. Text je rovnˇeˇz doprovázen ˇradou obrázk˚ u, které slouˇz´ı k ilustraci, v mnoha pˇr´ıpadech jsou proto vynechány popisy os.

1) Úvod A) Přehled prvků (0-5)dimenzionálního simplexu a hyperkrychle

B) Algoritmus pro výpočet EMM

E) Výpočet hodnoty kritéria miniMax v regulárním prostoru

2) Kritéria uniformity

C) Delaunayova triangulace D) Plošné souřadnice

3) Metody pro tvorbu návrhů v omezených návrhových prostorech

5) Příklady aplikace metod

4) Způsoby vracení bodů opustivších doménu F) Ruční výpočet hledání vrcholů polytopu pomocí LP

6) Implementace 7) Výsledky

8) Závěr

Obrázek 1.8: Doporuˇcen´ y postup ˇcetby, respektive návaznost jednotliv´ ych kapitol a sekc´ı.

18

Kapitola 2 Krit´ eria uniformity

(a) Euklidovsk´ a Maximin vzd´ alenost (EM M ). Legenda: modré kruˇznice - kruhy se stˇredy v n´ avrhov´ ych bodech s polomˇery rovn´ ymi vzd´ alenostem k nejbliˇzˇs´ımu z ostatn´ıch n´ avrhov´ ych bod˚ u; ˇcervené kruˇznice - nejmenˇs´ı z tˇechto kruh˚ u; ˇcerven´ a u ´seˇcka - spojnice vz´ ajemnˇe si nejbliˇzˇs´ıch n´ avrhov´ ych bod˚ u; délka ˇcervené u ´seˇcky - EM M .

(b) Kritérium miniMax (mM ). Legenda: modré body - vrcholy Voronoiova diagramu (kandidátn´ı body); modré kruˇznice - nejvˇetˇs´ı pr´ azdné kruhy se stˇredy v modr´ ych bodech; ˇcerven´ a kruˇznice - nejvˇetˇs´ı prázdn´ y kruh; ˇcerven´ y bod stˇred nejvˇetˇs´ıho prázdného kruhu; délka ˇcervené u ´seˇcky - mM .

Obrázek 2.1: Kritéria Maximin a miniMax. Obrázky slouˇz´ı pro ilustraci, popisky os jsou proto vynechány. Legenda: ˇcerné u ´seˇcky - hranice návrhové domény; ˇcerné body - návrhové body. Kvalitu návrhu m˚ uˇzeme hodnotit ˇradou kritéri´ı zamˇeˇren´ ych pˇredevˇs´ım na ortogonalitu [Cioppa and Lucas, 2007, Hofwing and Strömberg, 2010] nebo rovnomˇernost pokryt´ı [Crombecq et al., 2009, Myˇsa´ková and Lepˇs, 2011, Janouchová and Kuˇcerová, 2013]. V té19

´ KAPITOLA 2. KRITERIA UNIFORMITY

to práci jsme pro hodnocen´ı jednotliv´ ych návrh˚ u zvolili kritérium Euklidovská Maximin vzdálenost (EM M ) a kritérium miniMax (mM ) [Johnson et al., 1990, Auffray et al., 2012]. Tato kritéria byla vybrána pro jejich snadnou zobrazitelnost a jednoduchou interpretaci. Zároveˇ n se jedná o kritéria, která jasnˇe upozorˇ nuj´ı na závaˇzné nedostatky návrhu. V pˇr´ıpadˇe Euklidovské Maximin vzdálenosti je to neˇza´douc´ı bl´ızkost experiment˚ u. V pˇr´ıpadˇe kritéria miniMax pak nedostateˇcné pokryt´ı nˇekter´ ych oblast´ı návrhového prostoru.

2.1

Euklidovsk´ a Maximin vzd´ alenost (EM M )

Prvn´ım kritériem pouˇzit´ ym v této práci pro hodnocen´ı návrh˚ u experiment˚ u je Euklidovská Maximin vzdálenost (EM M ). Jedná se o jednoduchou a snadno zobrazitelnou metriku. Toto kritérium nejlépe poukazuje na vzájemnou bl´ızkost experiment˚ u (návrhov´ ych bod˚ u). Euklidovská Maximin vzdálenost je vhodná pro hodnocen´ı návrh˚ u experiment˚ u klasick´ ych reáln´ ych (fyzikáln´ıch, chemick´ ych, biologick´ ych, ...) stejnˇe jako virtuáln´ıch tzv. simulac´ı (napˇr´ıklad armádn´ıch bojov´ ych scénáˇr˚ u). Jedná se o kritérium ˇcasto pouˇz´ıvané k optimalizaci návrh˚ u experiment˚ u, jak m˚ uˇzeme vidˇet napˇr´ıklad v [Grosso et al., 2009], [Morris, 2014] nebo v [Pronzato and Walter, 1988]. EM M je nejkratˇs´ı ze vˇsech vzájemn´ ych vzdálenost´ı mezi body návrhu: EM M = min{..., Lij , ...},

i = 1, ..., np;

j = (i + 1), ..., np ,

(2.1)

kde np je poˇcet návrhov´ ych bod˚ u a Lij je euklidovská vzdálenost mezi body i a j. Snaˇz´ıme se tedy o maximalizaci hodnoty EM M . K urˇcen´ı hodnoty EM M je nutné spoˇc´ıst vzájemné vzdálenosti mezi vˇsemi body návrhu. Efektivn´ı algoritmus je pouˇzit ve funkci lhsdesign ze statistického toolboxu programu MATLAB. D´ıky vhodné indexaci jsou vˇsechny vzdálenosti spoˇcteny bˇehem jediného for-cyklu. Algoritmus je uveden v Pˇr´ıloze B. V´ yznam kritéria je ilustrován na Obrázku 2.1a.

2.2

Krit´ erium miniMax (mM )

Problematika kritéria miniMax je v literatuˇre téˇz oznaˇcována jako the largest empty sphere problem (LES) [Dickerson and Eppstein, 1995] - problém nejvˇetˇs´ı prázdné koule“ ” (Obrázek 2.1b). Je-li dána sada (návrhov´ ych) bod˚ u v omezeném prostoru, hodnota miniMax je polomˇer nejvˇetˇs´ı hyperkoule, která neobsahuje ˇza´dn´ y z bod˚ u sady (maximálnˇe se dot´ yká) a jej´ıˇz stˇred leˇz´ı uvnitˇr daného prostoru. Kritérium miniMax tedy slouˇz´ı k hodnocen´ı kvality pokryt´ı návrhového prostoru t´ım, ˇze ukazuje nejvˇetˇs´ı nepokrytou oblast. Máme-li zadánu sadu np návrhov´ ych bod˚ u D = di , i = 1, ..., np v omezeném prostoru 20


S, hledáme bod p ∈ S takov´ y, ˇze jeho vzdálenost k nejbliˇzˇs´ımu návrhovému bodu je nejdelˇs´ı: mM = max min d(p, di ), p∈S

i

i = 1, ..., np ,

(2.2)

kde d(x, y) je euklidovská vzdálenost mezi body x a y. Pro návrh rovnomˇernˇe pokr´ yvaj´ıc´ı návrhov´ y prostor je tedy ˇza´douc´ı co nejniˇzˇs´ı hodnota mM . Vyˇc´ıslen´ı hodnoty tohoto kritéria je v´ yraznˇe nároˇcnˇejˇs´ı neˇz v pˇr´ıpadˇe Euklidovské Maximin vzdálenosti. Jednou z moˇznost´ı pro nalezen´ı stˇredu nejvˇetˇs´ı prázdné koule (a poté hodnoty mM ) je provˇeˇren´ı vˇsech vrchol˚ u Voronoiova diagramu [Okabe et al., 2000] (v´ıce v Pˇr´ıloze C) sestaveného pro danou sadu návrhov´ ych bod˚ u. Poˇcet tˇechto vrchol˚ u vˇsak roste ddim/2e O(np ) v pˇr´ıpadˇe, kdy prostor nen´ı ohraniˇcen, a v ohraniˇceném prostoru je poˇcet bod˚ u nutn´ ych k provˇeˇren´ı jeˇstˇe vyˇsˇs´ı. Aˇckoli m˚ uˇzeme problém hraniˇcn´ıch oblast´ı domény efektivnˇe ˇreˇsit pomoc´ı zrcadlen´ı [Pronzato and M¨ uller, 2012], ve vyˇsˇs´ıch dimenz´ıch jsou pamˇet’ové a ˇcasové nároky algoritm˚ u pro sestaven´ı Voronoiova diagramu velmi vysoké. Ve vyˇsˇs´ıch dimenz´ıch je tedy nutné spokojit se s odhadem hodnoty kritéria miniMax. Tento odhad nám m˚ uˇze poskytnout napˇr´ıklad metoda zaloˇzená na evoluˇcn´ı strategii. Zp˚ usoby vyˇc´ıslen´ı kritéria miniMax v regulárn´ım návrhovém prostoru byly pˇredmˇetem pˇredchoz´ıho studia a jsou uvedeny v Pˇr´ıloze E. Pˇr´ıstupy aplikované zde - v omezeném návrhovém prostoru - jsou jejich rozˇs´ıˇren´ım.

2.2.1

Pˇ resn´ a hodnota krit´ eria miniMax

Pˇresnou hodnotu kritéria miniMax, resp. polohu bodu v návrhovém prostoru, kter´ y je nejv´ıce vzdálen od návrhov´ ych bod˚ u, je moˇzné nalézt pomoc´ı Voronoiova diagramu. Kandidátn´ımi body jsou vrcholy Voronoiova diagramu, samotné vrcholy ˇreˇsené domény a pr˚ useˇc´ıky hran diagramu s hraniˇcn´ımi objekty ˇreˇsené domény. Efektivnˇejˇs´ı, neˇz hledat zm´ınˇené pr˚ useˇc´ıky, je pouˇzit´ı zrcadlen´ı návrhov´ ych bod˚ u skrze vˇsechny (n − 1)dimenzionáln´ı facety (kde n oznaˇcuje dimenzi) návrhového prostoru a aˇz následné sestaven´ı Voronoiova diagramu [Pronzato and M¨ uller, 2012]. Tento pˇr´ıstup je funkˇcn´ı v regulárn´ım návrhovém prostoru (viz opˇet Pˇr´ılohu E). Zdá se ovˇsem pouˇziteln´ y (zde bez d˚ ukazu; správnost testována porovnán´ım v´ ysledk˚ u z´ıskan´ ych touto metodou s v´ ysledky z´ıskan´ ymi pomoc´ı dále popsan´ ych metod) i ve zde ˇreˇsen´ ych konvexn´ıch omezen´ ych návrhov´ ych prostorech. Postup ilustruje Obrázek 2.2.

21

´ KAPITOLA 2. KRITERIA UNIFORMITY 2.5

2.5

2

2

1.5

1.5

1

1

0.5

0.5

0

0

−0.5

−0.5

−1

−1

−1.5 −1.5 2.5

(a) N´ avrhov´ e body v omezen´ e2 m−1.5−1.5 2.5 (b) Zrcadlen´ ı0 návrhov´ ych bod˚ u skrze −1 −0.5 0 0.5 1 1.5 −1 −0.5 0.5 1 1.5 2 n´ avrhovém prostoru. vˇsechny (n − 1)-dimenzionáln´ı facety. 2.5

2

2

1.5

1.5

1

1

0.5

0.5

0

0

−0.5

−0.5

−1

−1

−1.5 −1.5

2.5

−1.5 (c) Sestrojen´ ı Voronoiova diagramu. (d) Oznaˇ cen´ı0 vrchol˚ u Voronoiova di−1 −0.5 0 0.5 1 1.5 2 −1.5 2.5 −1 −0.5 0.5 1 1.5 2 agramu spadaj´ıc´ıch dovnitˇr nebo na hranici návrhového prostoru - kandidátn´ı body. 2.5

2

2

1.5

1.5

1

1

0.5

0.5

0

0

−0.5

−0.5

−1

−1

−1.5 −1.5

(e) Sestrojen´ ı nejvˇ etˇs´ıch pr´ azdn´ y2ch−1.5−1.5 2.5 (f) Nalezen´ ı 0nejvˇe0.5tˇs´ı z 1 tˇechto koul´ ı. −1 −0.5 0 0.5 1 1.5 −1 −0.5 1.5 2 hyperkoul´ı (ve 2D: kruh˚ u) se stˇredy Jej´ı stˇred je bod nejvzdálenˇejˇs´ı v kandid´ atn´ıch bodech. od návrhov´ ych bod˚ u. Polomˇer této koule odpov´ıdá hodnotˇe mM .

2.5

2.5

2.5

Obrázek 2.2: V´ ypoˇcet pˇresné hodnoty kritéria miniMax. Ilustrace ve 2D.

22


2.2.2

Evoluˇ cn´ı strategie pro odhad hodnoty krit´ eria miniMax

Ve vyˇsˇs´ıch dimenz´ıch (problémy nastávaj´ı zpravidla jiˇz v ˇsestirozmˇerném návrhovém prostoru) je z´ıskán´ı pˇresné hodnoty kritéria miniMax v´ yˇse uveden´ ym zp˚ usobem a za pouˇzit´ı bˇeˇzn´ ych v´ ypoˇcetn´ıch prostˇredk˚ u nemoˇzné. Odhad hodnoty mM a pozice nej” osamˇelejˇs´ıho“ bodu v doménˇe vˇsak m˚ uˇzeme z´ıskat pomoc´ı stochastické metody evoluˇcn´ı strategie (ES). Tento zp˚ usob byl u ´spˇeˇsnˇe pouˇzit v regulárn´ıch návrhov´ ych prostorech (Pˇr´ıloha E), pokus´ıme se jej tedy aplikovat i zde.

ˇ sen´ı po zvoleném (a) Rodiˇce“ a potomci“ (b) Rodiˇce“ a potomci“ (c) Reˇ ” ” ” ” v prvn´ı generaci. v 50. generaci. poˇctu generac´ı.

Obrázek 2.3: Sériová evoluˇcn´ı strategie pro vyhodnocen´ı miniMax kritéria v omezeném návrhovém prostoru. Legenda: ˇcerné body - návrhové body; ˇcervené body - rodiˇce“; ” modré body - potomci“; purpurov´ y bod - stˇred nejvˇetˇs´ıho prázdného kruhu; purpurová ” kruˇznice - nejvˇetˇs´ı prázdn´ y kruh. Sériová verze evoluˇcn´ı strategie je znázornˇena na Obrázku 2.3. Stˇred nejvˇetˇs´ı prázdné hyperkoule (bod v doménˇe nejv´ıce vzdálen´ y od návrhov´ ych bod˚ u) je hledán v rámci celé této domény. Populace potomk˚ u“ je z rodiˇc˚ u“ odvozována mutac´ı, konkrétnˇe pˇriˇcten´ım ” ” normálnˇe rozdˇelen´ ych náhodn´ ych ˇc´ısel4 , coˇz vede k tomu, ˇze jsou vytvoˇreny body mimo návrhov´ y prostor. Ty je tˇreba posunout zpˇet dovnitˇr, aby byly platné pˇri hledán´ı stˇredu prázdné koule. Zp˚ usoby, jak toho dosáhnout, jsou popsány v Kapitole 4. Právˇe toto je vˇsak nejvˇetˇs´ım u ´skal´ım sériové verze evoluˇcn´ı strategie v omezeném návrhovém prostoru v porovnán´ı s jej´ım pouˇzit´ım v prostoru regulárn´ım (tam staˇc´ı souˇradnici nab´ yvaj´ıc´ı hodnoty mimo dané meze poloˇzit rovné právˇe hodnotˇe limitu). Praktiˇctˇejˇs´ı je zde pouˇzit´ı paraleln´ı verze evoluˇcn´ı strategie pro vyhodnocen´ı miniMax kritéria. A to nejen z d˚ uvodu moˇznosti v´ ypoˇctu na vˇetˇs´ım poˇctu v´ ypoˇcetn´ıch jednotek zároveˇ n. Zparalelizován´ı provedeme rozdˇelen´ım ˇreˇsené návrhové domény na menˇs´ı celky - subdomény - a to pomoc´ı Delaunayovy triangulace (viz Pˇr´ılohu C). Stˇred nejvˇetˇs´ı prázdné hyperkoule poté hledáme paralelnˇe nezávisle v kaˇzdé této subdoménˇe. Z´ıskáme 4

Stˇredn´ı hodnota µ = 0; smˇerodatná odchylka σ a) klesaj´ıc´ı s poˇrad´ım generace, b) ˇr´ızena tzv. pˇetinov´ ym pravidlem“. ”

23


(a) Rodiˇce“ a potomci“ (b) Kandidátn´ı ˇreˇsen´ı z jednot- (c) V´ ysledné ˇreˇsen´ı vybrané ” ” v prvn´ı generaci v soubˇeˇznˇe liv´ ych subdomén. z kandidátn´ıch ˇreˇsen´ı. ˇreˇsen´ ych subdomén´ ach.

Obrázek 2.4: Paraleln´ı evoluˇcn´ı strategie pro vyhodnocen´ı miniMax kritéria v omezeném návrhovém prostoru. Legenda: ˇcerné body - návrhové body; ˇcervené body - rodiˇce“; ” modré body - potomci“; b´ılé body - v kaˇzdé subdoménˇe bod nejv´ıce vzdálen´ y od ” návrhov´ ych bod˚ u; teˇckované kruˇznice - nejvˇetˇs´ı prázdné kruhy se stˇredy v b´ıl´ ych bodech; purpurov´ y bod - stˇred nejvˇetˇs´ıho prázdného kruhu; purpurová kruˇznice - nejvˇetˇs´ı prázdn´ y kruh. tak mnoˇzinu kandidátn´ıch ˇreˇsen´ı z kaˇzdé z nich a jako koneˇcné ˇreˇsen´ı vybereme z tˇechto bod˚ u ten, jehoˇz vzdálenost k nejbliˇzˇs´ımu návrhovému bodu je nejdelˇs´ı. Metodu ilustruje Obrázek 2.3. V této verzi ES je snazˇs´ı vracen´ı bod˚ u, které opust´ı ˇreˇsenou subdoménu. To právˇe proto, ˇze drˇz´ıme“ body v jednom konkrétn´ım simplexu a do nˇeho je lze jednoduˇse ” vracet pomoc´ı nulován´ı záporn´ ych ploˇsn´ ych souˇradnic, jak je popsáno v Sekci 4.2.

24

Kapitola 3 Metody pro tvorbu n´ avrh˚ u v omezen´ ych n´ avrhov´ ych prostorech Vytvoˇrit návrh experiment˚ u v omezeném návrhovém prostoru je moˇzné v zásadˇe dvˇema zp˚ usoby: 1. obalit“ nepravidelnou doménu regulárn´ı doménou (hyperkrychl´ı/hyperkvádrem) ” bounding boxem, v tomto prostoru vytvoˇrit návrhové body a z tˇechto bod˚ u následnˇe vybrat ty, které leˇz´ı v p˚ uvodn´ı ˇreˇsené doménˇe (viz Obrázek 3.1). V tomto pˇr´ıpadˇe lze pouˇz´ıt jakékoli metody tvorby návrhu experiment˚ u v regulárn´ım návrhovém prostoru. Tˇem se vˇenuje práce [Myˇsa´ková, 2012] a nˇekteré z metod uveden´ ych v této práci budou aplikovány i zde.

Obrázek 3.1: 1. skupina metod tvorby - bounding box.

2. rozdˇelit doménu na jednoduˇsˇs´ı objekty (simplexy), v tˇechto objektech vytvoˇrit návrhové body a tyto body sjednotit (viz Obrázek 3.2) Oba pˇr´ıstupy maj´ı svá u ´skal´ı. U prvn´ıho je to nemoˇznost zaruˇcen´ı, ˇze do omezené domény padne“ právˇe poˇzadované mnoˇzstv´ı bod˚ u. Rovnˇeˇz nen´ı zaruˇceno, ˇze kvalitn´ı ” návrh v opsaném regulárn´ım prostoru pˇrinese i kvalitn´ı návrh v omezené doménˇe. Nejvˇetˇs´ım u ´skal´ım se vˇsak m˚ uˇze stát pomˇer objemu omezené domény a opsaného hyperkvádru. 25

´ ˚ V OMEZENYCH ´ KAPITOLA 3. METODY PRO TVORBU NAVRH U ´ ´ NAVRHOVYCH PROSTORECH

Obrázek 3.2: 2. skupina metod tvorby - rozdˇelen´ı na simplexy.

Obzvláˇstˇe pak se zvyˇsuj´ıc´ı se dimenzionalitou návrhového prostoru. Pro vrcholov´ y simplex a jemu odpov´ıdaj´ıc´ı opsanou hyperkrychli (viz Obrázek 3.3) je to: 1 , (3.1) dim! kde dim oznaˇcuje dimenzi prostoru. Napˇr´ıklad v 10dimenzionáln´ım prostoru by tedy bylo nutno vytvoˇrit v opsané hyperkrychli témˇeˇr 4 miliony rovnomˇernˇe rozprostˇren´ ych bod˚ u, aby bylo pravdˇepodobné, ˇze alespoˇ n jeden z nich bude leˇzet v ˇreˇseném simplexu. Problémy druhého pˇr´ıstupu spoˇc´ıvaj´ı pˇredevˇs´ım v rozdˇelen´ı domény. Námi pouˇz´ıvaná Delaunayova triangulace (v´ıce informac´ı v Pˇr´ıloze C) je se zvyˇsuj´ıc´ı se dimenzionalitou ˇcasovˇe i pamˇet’ovˇe nároˇcná. Druh´ y pˇr´ıstup m˚ uˇze rovnˇeˇz vést k nekvalitn´ım návrh˚ um pˇredevˇs´ım v m´ıstech spojen´ı jednotliv´ ych simplex˚ u. Vsimplex /Vhyperkrychle =

Obrázek 3.3: Vrcholov´ y simplex ve 2D a ve 3D.

26


3.1

Gener´ ator n´ ahodn´ ych bod˚ u

Prvn´ı metoda tvorby vyuˇz´ıvá generátor náhodn´ ych bod˚ u v simplexu. Metoda spadá do druhé skupiny (dle rozdˇelen´ı v´ yˇse), nebot’ jsou body vytváˇreny v jednotliv´ ych simplexech poté, co byla zadaná návrhová doména ztriangulována pomoc´ı Delaunayovy triangulace. Námi pouˇz´ıvan´ y generátor [Devroye, 1986] je uveden n´ıˇze. Souˇradnice bodu jsou vytvoˇreny s exponenciáln´ım rozdˇelen´ım a následnˇe normalizovány. 1 2 3 4 5

y=rand(1,n); % funkce rand - tvoˇ r´ ı bod z rovnomˇ ern´ eho rozdˇ elen´ ı [0-1]^(dim+1) x=-log(y); S=sum(x’)’; X=x./repmat(S,1,n); L=X*T; % v T jsou uloˇ zeny souˇ radnice vrchol˚ u simplexu, v nˇ emˇ z tvoˇ r´ ıme n´ ahodn´ y bod

Poˇcet návrhov´ ych bod˚ u vytvoˇren´ ych v jednotliv´ ych simplexech je závisl´ y na pomˇeru objem˚ u tˇechto simplex˚ u. Teoretick´ y poˇcet bod˚ u npsimplexi v simplexu i je: npsimplexi = np ·

Vsimplexi Vsimplexi = np · P Vdomena i Vsimplexi

,

(3.2)

kde np znaˇc´ı poˇzadovan´ y poˇcet bod˚ u v celé doménˇe, Vsimplexi objem simplexu i a Vdomena objem celé domény. Pˇri urˇcován´ı poˇctu bod˚ u skuteˇcnˇe um´ıstˇen´ ych do jednotliv´ ych simplex˚ u je pouˇzita spodn´ı celá ˇcást z teoretické hodnoty a zbylé body jsou a) vytvoˇreny v nejvˇetˇs´ım ze simplex˚ u triangulace, b) rozm´ıstˇeny po jednom do simplex˚ u seˇrazen´ ych sestupnˇe dle objemu (Obrázek 3.4). Takov´ ychto variant by bylo moˇzno vyzkouˇset celou ˇradu, na v´ ysledek maj´ı vliv pouze v pˇr´ıpadˇe malého poˇctu poˇzadovan´ ych bod˚ u nebo podobného poˇctu bod˚ u a poˇctu simplex˚ u v triangulaci, pˇr´ıpadnˇe pokud by triangulace obsahovala simplexy s v´ yraznˇe odliˇsn´ ymi objemy.

3,57 b. → 3 b.

3,83 b. → 3 b.

3

4 5

1,58 b. → 1 b.

(a) Triangulace n´ avrhové domény s oznaˇcen´ım poˇctu bod˚ u teoreticky n´ aleˇzej´ıc´ıch jednotliv´ ym simplex˚ um a poˇctu bod˚ u skuteˇcnˇe um´ıstˇen´ ych do jednotliv´ ych simplex˚ u v prvn´ım kroku.

1

4

1

(b) Zbytek bod˚ u um´ıstˇen do nejvˇetˇs´ıho simplexu.

(c) Zbylé body um´ıstˇeny po jednom postupnˇe do simplex˚ u seˇrazen´ ych sestupnˇe dle objemu.

Obrázek 3.4: Varianty rozdˇelen´ı bod˚ u do simplex˚ u. Poˇcet bod˚ u: 9. 27


3.2

Metoda LHS na opsan´ em hyperkv´ adru

Obrázek 3.5: Pˇr´ıklady LHS návrhu ve 2D s 5 body um´ıstˇen´ ymi do stˇred˚ u interval˚ u (vlevo) a náhodnˇe v rámci intervalu (vpravo).

Dalˇs´ı metoda spadá do 1. kategorie dle rozdˇelen´ı v u ´vodu této kapitoly. Nepravidelné návrhové doménˇe op´ıˇseme pravo´ uhl´ y hyperkvádr a v nˇem vytvoˇr´ıme návrh experiment˚ u. Tento návrh by mˇel b´ yt co nejkvalitnˇejˇs´ı a co nejrovnomˇernˇeji pokr´ yvat zvolen´ y prostor. Proto je vhodné zvolit návrh splˇ nuj´ıc´ı podm´ınky LHS - latin hypercube sampling [Cioppa and Lucas, 2007, Toropov et al., 2007], nebot’ ten jiˇz ze své podstaty zajiˇst’uje urˇcitou u ´roveˇ n rovnomˇernosti pokryt´ı. LHS je ˇcasto pouˇz´ıvan´ y typ návrhu, v nˇemˇz je kaˇzdá z dimenz´ı (promˇenn´ ych) rozdˇelena na np interval˚ u (kde np odpov´ıdá poˇzadovanému poˇctu bod˚ u) a do kaˇzdého intervalu kaˇzdé promˇenné je um´ıstˇen právˇe jeden bod. Bˇeˇznˇe se pouˇz´ıvaj´ı dvˇe varianty, v prvn´ı je bod um´ıstˇen do stˇredu intervalu (Obrázek 3.5 vlevo), ve druhé pak náhodnˇe v rámci celého intervalu (Obrázek 3.5 vpravo). Pouˇzit´ı LHS návrhu zde tedy prob´ıhá tak, ˇze jej vytvoˇr´ıme v opsaném hyperkvádru a následnˇe vybereme body, které leˇz´ı uvnitˇr ˇreˇsené omezené domény. Nelze tedy pˇredem zaruˇcit, kolik bod˚ u padne“ do c´ılového prostoru, vod´ıtkem pro volbu poˇctu bod˚ u v LHS ” návrhu nám m˚ uˇze b´ yt pomˇer mezi objemem opsaného hyperkvádru a samotné omezené domény, jak ilustruje Obrázek 3.6. Je tedy zˇrejmé, ˇze pouˇzit´ı takovéto metody je vhodné pouze v pˇr´ıpadˇe, kdy ˇreˇsená doména vyplˇ nuje znaˇcnou ˇcást opsaného hyperkvádru. Pro srovnán´ı byly vyzkouˇseny dvˇe varianty této metody - prost´ y neoptimalizovan´ y LHS návrh a LHS návrh optimalizovan´ y prohazován´ım pozic jednotliv´ ych návrhov´ ych bod˚ u vzhledem ke kritériu Euklidovské Maximin vzdálenosti5 .

5 V kaˇzdé iteraci je nalezena dvojice vzájemnˇe si nejbliˇzˇs´ıch bod˚ u (tˇem odpov´ıdá aktuáln´ı hodnota EM M ). Z této dvojice je n´ ahodnˇe vybrán jeden bod a k nˇemu opˇet náhodnˇe jeden bod ze vˇsech ostatn´ıch bod˚ u n´ avrhu. Poté je zvolena jedna ze souˇradnic (opˇet náhodnˇe) a u zvolen´ ych bod˚ u je hodnota této souˇradnice prohozena. Pokud dojde ke zlepˇsen´ı (zv´ yˇsen´ı hodnoty EM M ), je taková v´ ymˇena pˇrijata. Tato metoda je podrobnˇe pops´ ana v [Myˇsáková, 2012, Kapitola 2.1.2.2]

28


Obrázek 3.6: Pouˇzit´ı LHS v opsaném hyperkvádru. Omezené návrhové doménˇe je opsán hyperkvádr, v nˇemˇz je vytvoˇren LHS návrh (ˇcerné body). Následnˇe jsou vybrány pouze body spadaj´ıc´ı do omezeného prostoru (ˇcervené body). Poˇzadovan´ y poˇcet bod˚ u v omezeném prostoru je 10 a pomˇer objem˚ u omezené domény a opsaného hyperkvádru je 0,6796 = 1/1,4714; LHS návrh byl tedy vytvoˇren s 15 body a vid´ıme, ˇze právˇe poˇzadovan´ ych 10 bod˚ u leˇz´ı uvnitˇr omezené domény.

3.3

Metoda odeb´ır´ an´ı bod˚ u z pˇ rehuˇ stˇ en´ eho n´ avrhu

Dalˇs´ı metoda pracuje na principu odeb´ırán´ı bod˚ u ze zámˇernˇe pˇrehuˇstˇeného návrhu. Tento pˇr´ıstup byl rovnˇeˇz u ´spˇeˇsnˇe pouˇzit v regulárn´ım prostoru ([Myˇsa´ková and Lepˇs, 2011, Myˇsáková, 2012]. Pomoc´ı generátoru náhodn´ ych bod˚ u (Sekce 3.1) je v návrhovém prostoru vytvoˇren návrh s vyˇsˇs´ım neˇz poˇzadovan´ ym poˇctem bod˚ u. Nadbyteˇcné body jsou následnˇe z návrhu odeb´ırány a to nikoli náhodnˇe, n´ ybrˇz heuristicky na základˇe kritéria Maximin. Metodu pˇredstavujeme ve dvou dále popsan´ ych verz´ıch.

3.3.1

Metoda ub´ ır´ an´ ı

V prvn´ı variantˇe metody je v kaˇzdé iteraci (poˇcet iterac´ı odpov´ıdá poˇctu nadbyteˇcn´ ych bod˚ u) nalezena dvojice vzájemnˇe si nebliˇzˇs´ıch návrhov´ ych bod˚ u. Této dvojici odpov´ıdá aktuáln´ı hodnota EM M . Náhodnˇe zvolen´ y bod z této dvojice je z návrhu odebrán. Je tedy zˇrejmé, ˇze s kaˇzd´ ym dalˇs´ım odebran´ ym bodem se zlepˇsuje (zvyˇsuje) hodnota kritéria Maximin. Idea této metody je nav´ıc taková, ˇze po odebrán´ı vˇsech nadbyteˇcn´ ych bod˚ u z´ıskáme návrh, jehoˇz kvalita bude vyˇsˇs´ı neˇz u návrhu, kter´ y je vytvoˇren najednou pˇr´ımo s poˇzadovan´ ym poˇctem bod˚ u.

3.3.2

Metoda ub´ ır´ an´ ı NEW

Druhá varianty metody se liˇs´ı zp˚ usobem volby odebraného bodu z dvojice s aktuáln´ı nejmenˇs´ı vzájemnou vzdálenost´ı. Ta zde nen´ı náhodná jako v prvn´ı variantˇe, n´ ybrˇz deterministická. Odebrán je ten z bod˚ u z dvojice, jehoˇz druhá nejkratˇs´ı vzdálenost k bod˚ um

29


Obrázek 3.7: Odeb´ırán´ı z pˇrehuˇstˇeného návrhu. Zelené body znaˇc´ı pˇrehuˇstˇen´ y návrh. V kaˇzdém kroku je oznaˇcena dvojice vzájemnˇe si nejbliˇzˇs´ıch bod˚ u (ˇcervená u ´seˇcka odpov´ıdá hodnotˇe EM M ). Z této dvojice je jeden bod odebrán (zv´ yraznˇen azurovˇe).

návrhu (tedy vzdálenost k nejbliˇzˇs´ımu bodu návrhu jinému, neˇz je druh´ y z dvojice) je kratˇs´ı. Rozd´ıl je patrn´ y i z Obrázku 3.7, kdy odebrán´ı azurovˇe zv´ yraznˇeného bodu je jistˇe v´ yhodnˇejˇs´ı neˇz odebrán´ı druhého z bodu dvojice.

3.4

N´ astroj Distmesh

Nástroj Distmesh detailnˇe popsan´ y v [Persson and Strang, 2004] je heuristick´ y algoritmus pro tvorbu rovnomˇern´ ych s´ıt´ı [Chen and Holst, 2011] primárnˇe urˇcen´ ych pro metodu koneˇcn´ ych prvk˚ u (MKP) - Finite Element Method (FEM). Je známé, ˇze v rovnomˇern´ ych s´ıt´ıch jsou jednotlivé uzly vzájemnˇe srovnatelnˇe vzdáleny. Proto tohoto nástroje vyuˇz´ıváme rovnˇeˇz pro tvorbu návrh˚ u experiment˚ u jak v regulárn´ıch [Myˇsáková, 2012], tak v omezen´ ych návrhov´ ych prostorech [Myˇsáková and Lepˇs, 2012, Myˇsa´ková et al., 2012]. Algoritmus je zaloˇzen na jednoduchém dynamickém systému rozp´ınaj´ıc´ı se pˇr´ıhradové konstrukce. Pˇr´ıliˇs krátké pruty vyvolávaj´ı s´ıly, jeˇz tlaˇc´ı navzájem bl´ızké uzly smˇerem od ˇ sebe. Casto tak ovˇsem nastává situace, ˇze je uzel (návrhov´ y bod) vysunut z návrhové domény. V takovém pˇr´ıpadˇe je tˇreba jej vrátit zpˇet. Nástroj Distmesh obsahuje tyto procedury pro jednoduché objekty, napˇr´ıklad 2D polygon, pro sloˇzitˇejˇs´ı u ´tvary jako je simplex nebo polytop v ND je tˇreba vloˇzit vlastn´ı ˇreˇsen´ı, napˇr´ıklad nˇekteré z uveden´ ych v Kapitole 4. Postup metody vyuˇz´ıvaj´ıc´ı nástroje Distmesh je znázornˇen na Obrázku 3.8. Do návrhové domény je tˇreba nejprve vloˇzit prvotn´ı sadu bod˚ u6 a na tu aplikovat popsan´ y nástroj. 6

Kvalita této v´ ychoz´ı sady nem´ a velk´ y vliv na v´ ysledek, zpravidla tedy postaˇc´ı pouˇzit´ı jednoduchého gener´ atoru n´ ahodn´ ych bod˚ u v simplexech ztriangulované omezené návrhové domény.

30


(a) Triangulace n´ avrhové domény a um´ıstˇen´ı v´ ychoz´ıch bod˚ u do jednotliv´ ych simplex˚ u.

(b) Tvorba prutové konstrukce triangulac´ı v´ ychoz´ıch bod˚ u.

(c) Fináln´ı návrh po aplikaci nástroje Distmesh.

Obrázek 3.8: Tvorba rovnomˇerné s´ıtˇe z náhodnˇe vytvoˇren´ ych bod˚ u pomoc´ı nástroje Distmesh.

3.5

Simplexov´ e mˇ r´ıˇ zkov´ e (lattice) n´ avrhy

Klasick´ ym zp˚ usobem tvorby návrh˚ u v simplexovém prostoru jsou simplexové mˇr´ıˇzkové (lattice) návrhy [Montgomery, 2000, Kapitola 11-5]. Vznikaj´ı pravideln´ ym rozdˇelen´ım jednotliv´ ych barycentrick´ ych souˇradnic a jsou tak obdobou plnˇe faktoriáln´ıch návrh˚ u v regulárn´ıch doménách. Pˇri rozdˇelen´ı kaˇzdé z n barycentrick´ ych souˇradnic (kde n odpov´ıdá poˇctu sloˇzek) na m stejnˇe dlouh´ ych interval˚ u vznikne simplexov´ y lattice návrh obsahuj´ıc´ı x3 = 1

x3 = 1 x3 = 2/3, x2 = 1/3 x2 = x3 = 1/2

x1 = 0

x1 = 0 x1 = 1

x2 = 1

x3 = 0

x1 = 1

x2 = 1

[3,2] lattice

[3,3] lattice x3 = 1

x3 = 1

x1 = 1

x2 = 1

x4 = 1

x1 = 1

x2 = 1

x4 = 1

[4,2] lattice

[4,3] lattice

Obrázek 3.9: Pˇr´ıklady simplexov´ ych lattice návrh˚ u se tˇremi a ˇctyˇrmi sloˇzkami.

31


M=

(n + m − 1)! m!(n − 1)!

(3.3)

návrhov´ ych bod˚ u. Pˇr´ıklady návrh˚ u jsou uvedeny na Obrázku 3.9 (oznaˇceny [n, m]). Tyto návrhy lze tedy chápat jako ˇsablony, které m˚ uˇzeme pouˇz´ıt jak v jakémkoli simplexu, tak i v jednotliv´ ych simplexech vznikl´ ych triangulac´ı libovolné domény, jak je znázornˇeno napˇr´ıklad na Obrázku 3.10 vlevo. Uveden´ y pˇr´ıklad má ovˇsem ˇspatné vlastnosti z hlediska rovnomˇernosti pokryt´ı. Bylo by vˇsak moˇzné pouˇz´ıt r˚ uzné lattice návrhy (s r˚ uzn´ ymi poˇcty interval˚ u, na nˇeˇz jsou rozdˇeleny jednotlivé souˇradnice) v závislosti na objemu jednotliv´ ych simplex˚ u tvoˇr´ıc´ıch triangulaci domény. To je znázornˇeno na Obrázku 3.10 vpravo, kde jsou ve vˇetˇs´ıch“ simplexech pouˇzity lattice návrhy [3, 4] (modré ” body), zat´ımco v tˇech menˇs´ıch“ návrhy [3, 2] (ˇcervené body). ”

Obrázek 3.10: Aplikace simplexov´ ych lattice návrh˚ u ve ztriangulované doménˇe. Vlevo pouˇzit stejn´ y lattice návrh ve vˇsech simplexech triangulace, vpravo pouˇzity r˚ uzné návrhy v závislosti na objemech simplex˚ u (resp. obsaz´ıch troj´ uheln´ık˚ u).

32

Kapitola 4 Zp˚ usoby vracen´ı bod˚ u opustivˇ s´ıch dom´ enu Pˇri tvorbˇe návrh˚ u (pˇri pouˇzit´ı nástroje Distmesh) stejnˇe jako pˇri hodnocen´ı kvality návrh˚ u (napˇr´ıklad evoluˇcn´ı strategi´ı pro vyhodnocen´ı kritéria miniMax) docház´ı k situac´ım, kdy je potˇreba posunout body, které z nˇejakého d˚ uvodu opustily návrhovou doménu, zpˇet do n´ı, respektive na jej´ı povrch. V regulárn´ım návrhovém prostoru se jedná o triviáln´ı u ´kon. V omezeném návrhovém prostoru to pˇredstavuje problém, k jehoˇz ˇreˇsen´ı lze pˇristupovat mnoha zp˚ usoby. Tˇri z nich jsou uvedeny v této kapitole.

X

V3

3

X 3'

X 2'

X1 X 1'

V

2

V1 X2

Obrázek 4.1: Posun bod˚ u - kolm´ y pr˚ umˇet.

33

˚ ˚ OPUSTIVSˇÍCH DOMENU ´ KAPITOLA 4. ZPUSOBY VRACENÍ BODU

nejbližší bod ve vrcholu V3

V V nejbližší bod ve vrcholu

2

nejbližší bod ve vrcholu 1

Obrázek 4.2: Posun bod˚ u - nejbliˇzˇs´ı bod ve vrcholu.

4.1

Kolm´ y pr˚ umˇ et na facetu

Nejpˇresnˇeji lze problém ˇreˇsit analyticky - naj´ıt nejbliˇzˇs´ı bod návrhového prostoru. Tedy nejbliˇzˇs´ı z kolm´ ych pr˚ umˇet˚ u ˇreˇseného bodu (bodu leˇz´ıc´ıho mimo návrhov´ y prostor) do vˇsech facet návrhové domény; n oznaˇcuje dimenzi návrhového prostoru. Kolm´ y pr˚ umˇet hledáme stejnˇe jako ve 2D: pomoc´ı vektorového souˇcinu nalezneme vektor kolm´ y na facetu, dále pˇr´ımku procházej´ıc´ı ˇreˇsen´ ym bodem s nalezen´ ym vektorem coby sv´ ym normálov´ ym

(a) Nalezen´ı pr˚ umˇet˚ u (b) Urˇcen´ı, které z pr˚ umˇet˚ u (c) V´ ybˇer nejbliˇzˇs´ıho z tˇechto ˇreˇseného bodu do facet. se nacházej´ı na povrchu bod˚ u. ˇreˇsené domény, a spoˇcten´ı absolutn´ı vzdálenosti k tˇemto pr˚ umˇet˚ um a k vrchol˚ um návrhového prostoru.

Obrázek 4.3: Posun bod˚ u - kolm´ y pr˚ umˇet - ˇreˇsen´ı na celé doménˇe.

34


a kolm´ y pr˚ umˇet ˇreˇseného bodu je poté pr˚ useˇc´ıkem této pˇr´ımky s facetou. Obrázek 4.1 ukazuje nˇekolik pˇr´ıklad˚ u ve 2D. Je tedy nutné nalézt pr˚ umˇet ˇreˇseného bodu do vˇsech facet návrhové domény a vybrat ten nejbliˇzˇs´ı. V´ yˇse zm´ınˇen´ y postup hledán´ı kolmého pr˚ umˇetu ovˇsem nerozliˇs´ı, zda nalezen´ y pr˚ umˇet leˇz´ı na facetˇe návrhové domény nebo aˇz na jej´ım prodlouˇzen´ı“. Je tedy nutné ” nejprve mnoˇzinu nalezen´ ych kolm´ ych pr˚ umˇet˚ u zredukovat na ty, které leˇz´ı skuteˇcnˇe na povrchu návrhového prostoru (v´ıce o tomto rozliˇsen´ı v Pˇr´ıloze D). Nyn´ı je jeˇstˇe tˇreba oˇsetˇrit pˇr´ıpad, kdy bod leˇz´ı v nˇekteré z oblast´ı znázornˇen´ ych na Obrázku 4.2. Pro body z tˇechto oblast´ı je nejbliˇzˇs´ım bodem domény jej´ı vrchol. Vˇsechny vrcholy návrhového prostoru tedy pˇridáme k mnoˇzinˇe kolm´ ych pr˚ umˇet˚ u leˇz´ıc´ıch na jej´ım povrchu, pro tyto body vypoˇcteme absolutn´ı vzdálenost k ˇreˇsenému bodu a do nejbliˇzˇs´ıho z nich posuneme ˇreˇsen´ y bod. Postup ilustruje Obrázek 4.3.

4.2

Nulov´ an´ı z´ aporn´ ych ploˇ sn´ ych souˇ radnic

Jin´ y zp˚ usob vrácen´ı bodu zpˇet na povrch domény vyuˇz´ıvá ploˇsn´ ych souˇradnic (viz Pˇr´ılohu D). Máme-li dan´ y simplex a bod, m˚ uˇzou nastat v zásadˇe dvˇe situace: a) bod leˇz´ı uvnitˇr daného simplexu - v tom pˇr´ıpadˇe jsou vˇsechny ploˇsné souˇradnice tohoto bodu v˚ uˇci tomuto simplexu kladné; b) bod leˇz´ı mimo dan´ y simplex - minimálnˇe jedna (maximálnˇe vˇsechny kromˇe jedné) ploˇsná souˇradnice je záporná. Posun bodu na povrch simplexu je pak následuj´ıc´ı: záporné ploˇsné souˇradnice poloˇz´ıme rovny 0 a zbylé (kladné) ploˇsné souˇradnice zmˇen´ıme v jejich p˚ uvodn´ım vzájemném pomˇeru tak, aby celkov´ y souˇcet X2 V3 X 2' X1 X 1'

V1

X 3'

V2 X3

Obrázek 4.4: Posun bod˚ u - nulován´ı záporné ploˇsné souˇradnice.

35


ploˇsn´ ych souˇradnic z˚ ustal roven 1. Posun bod˚ u na povrch simplexu touto metodou ukazuje Obrázek 4.4. Problém s t´ımto pˇr´ıstupem nastává v pˇr´ıpadˇe, kdy neˇreˇs´ıme jen posun na povrch simplexu, n´ ybrˇz na povrch nepravidelné domény. Doménu v takovém pˇr´ıpadˇe m˚ uˇzeme rozdˇelit na jednotlivé simplexy pomoc´ı Delaunayovy triangulace (viz Pˇr´ılohu C), poté ovˇsem nejsme schopni urˇcit, vzhledem ke kterému ze simplex˚ u této triangulace provést onen posun pomoc´ı u ´pravy ploˇsn´ ych souˇradnic. Z ˇc´ıseln´ ych hodnot ploˇsn´ ych souˇradnic vztaˇzen´ ych k jednotliv´ ym simplex˚ um to zjistit nelze, nebot’ ty jsou v jistém smyslu relativn´ı. Je tedy nutné provést posun ˇreˇseného bodu na povrch vˇsech simplex˚ u triangulace v´ yˇse popsan´ ym zp˚ usobem a následnˇe spoˇc´ıst absolutn´ı vzdálenosti k tˇemto bod˚ um a vybrat ten nejbliˇzˇs´ı.

4.3

Pomocn´ a sada bod˚ u uvnitˇ r dom´ eny

Dalˇs´ı moˇznost´ı, jak posunout bod zpˇet do ˇreˇsené domény, je vyuˇzit´ı pomocné sady bod˚ u [Lepˇs, 2009]. Tu vytvoˇr´ıme uvnitˇr návrhového prostoru nˇekter´ ym z rychl´ ych algoritm˚ u. Následnˇe je pro body, které chceme posunovat, nalezen nejbliˇzˇs´ı z pomocné sady bod˚ u (do této sady jsou pˇridány rovnˇeˇz vˇsechny vrcholy návrhového prostoru). Pomoc´ı metody p˚ ulen´ı intervalu“ (viz Obrázek 4.6) nalezneme bod na hranici ˇreˇsené domény a do ” tohoto bodu pˇresuneme bod z vnˇejˇsku domény. Je tˇreba zm´ınit, ˇze nalezen´ y bod neleˇz´ı pˇresnˇe na hranici domény, n´ ybrˇz uvnitˇr ˇreˇsené domény libovolnˇe (ovlivnˇeno poˇctem iterac´ı pˇri aplikaci metody p˚ ulen´ı intervalu) bl´ızko jej´ımu povrchu. Pˇr´ıklad je znázornˇen

V3 X3

X1 X 3' V1

X 1'

X 2'

V2

X2

Obrázek 4.5: Posun bod˚ u - pomocná sada.

36


A

V1

2

4

X 2'

3 5

V2

1

B

X

2

Obrázek 4.6: Pouˇzit´ı metody p˚ ulen´ı intervalu. Hledáme bod mezi dvˇema zadan´ ymi body (které leˇz´ı kaˇzd´ y na opaˇcné stranˇe zadané hranice) takov´ y, aby leˇzel co nejbl´ıˇze zvolené hranici a nav´ıc na dané stranˇe této hranice. V prvn´ım kroku nalezneme bod uprostˇred mezi p˚ uvodn´ımi body; zjist´ıme, na které stranˇe hranice nov´ y bod leˇz´ı; pouˇzijeme jej v dalˇs´ım kroku m´ısto pˇredchoz´ıho bodu na této stranˇe hranice.

na Obrázku 4.5. Pokud je nebliˇzˇs´ım bodem z pomocné sady vrchol návrhového prostoru, neprovád´ıme jiˇz p˚ ulen´ı intervalu, n´ ybrˇz ˇreˇsen´ y bod posuneme rovnou do vrcholu domény. Pro zrychlen´ı je rovnˇeˇz nejprve kontrolováno, jak daleko je nejbliˇzˇs´ı pomocn´ y bod od hranice domény (jak hluboko je pod jej´ım povrchem): pokud by se bod z pomocné sady pˇri posunu o tis´ıcinu (moˇzno zvolit libovolnˇe) vzdálenosti k ˇreˇsenému bodu dostal jiˇz mimo návrhov´ y prostor, je ˇreˇsen´ y bod posunut pˇr´ımo do nejbliˇzˇs´ıho pomocného bodu. K omezen´ı vzniku duplikovan´ ych bod˚ u (obzvláˇstˇe ve vrcholech) bylo rovnˇeˇz zavedeno opatˇren´ı, které vyˇskrtává jiˇz pouˇzit´ y pomocn´ y bod z v´ ybˇeru. Tato metoda vracen´ı bod˚ u je jednoduchá a pˇrináˇs´ı dalˇs´ı prvek náhodnosti do algoritm˚ u, v nichˇz je aplikována. Je vˇsak ˇcasovˇe nároˇcná z d˚ uvodu nutnosti v´ ypoˇctu velkého mnoˇzstv´ı vzájemn´ ych vzdálenost´ı. M˚ uˇze téˇz docházet k posunu nepˇrirozen´ ym“ smˇerem ” 0 (viz bod X1 → X1 na Obrázku 4.5).

4.4

Porovn´ an´ı

Porovnán´ı uveden´ ych ˇreˇsen´ı posunu bod˚ u na povrch ˇreˇsené domény ve 2D ukazuje Obrázek 4.7. Vid´ıme, ˇze v´ ysledek m˚ uˇze b´ yt znaˇcnˇe rozd´ıln´ y. To vˇsak nemus´ı b´ yt na ˇskodu v pˇr´ıpadˇe, kdy si urˇcitou náhodnost a nepravidelnost v algoritmu pˇrejeme. Kritériem 37


V3

V4

X4 V

X1

V3

5

X3 V6

X2

X2

V1

V

V7 X

X

3

V2

2

1

V1

Obrázek 4.7: Porovnán´ı zp˚ usob˚ u vracen´ı bod˚ u do simplexu (vlevo) a do nepravidelné domény (vpravo). Legenda: azurové body - metoda kolmého pr˚ umˇetu; zelené body - metoda nulován´ı záporn´ ych ploˇsn´ ych souˇradnic; purpurové body - metoda pomocné sady bod˚ u.

v´ ybˇeru metody je nav´ıc (a pˇredevˇs´ım) jej´ı ˇcasová nároˇcnost. Srovnán´ı ˇcasové nároˇcnosti posunu bodu zpˇet do nepravidelné domény ve 2D (pˇr´ıklad odpov´ıdá Obrázku 4.7 vpravo) a 5D (70 vrchol˚ u, 970 4-dimenzionáln´ıch facet, 2909 simplex˚ u triangulace) ukazuje Tabulka 4.1. Je vˇsak nutno pˇripomenout, ˇze ˇcasová nároˇcnost metody s pomocnou sadou bod˚ u je urˇcena právˇe poˇctem bod˚ u v této sadˇe a rovnˇeˇz zvolen´ ym poˇctem iterac´ı v algoritmu p˚ ulen´ı intervalu. V´ ysledek naznaˇcuje dominanci metody nulován´ı záporn´ ych ploˇsn´ ych souˇradnic, zat´ımco metoda vyuˇz´ıvaj´ıc´ı kolmého pr˚ umˇetu bodu do facet domény znatelnˇe ztrác´ı. 2D pˇr´ıklad 5D pˇr´ıklad

kolm´ y pr˚ umˇ et“ ” 0,0032 s 66,3531 s

nulov´ an´ı“ ” 0,0007 s 0,3350 s

pomocn´ a sada“ ” 0,0087 s 5,2703 s

ˇ Tabulka 4.1: Casov´ a nároˇcnost zp˚ usob˚ u posunu bod˚ u.

38

Kapitola 5 Pˇ r´ıklady aplikace metod Aplikac´ı, na nˇeˇz je moˇzné uvedené pˇr´ıstupy aplikovat, je celá ˇskála a prostupuj´ı nejr˚ uznˇejˇs´ımi odvˇetv´ımi. Typick´ ym a ˇcast´ ym pˇr´ıkladem experimentu, v nˇemˇz jsou jednotlivé vstupn´ı parametry limitovány omezuj´ıc´ımi podm´ınkami, je navrhován´ı smˇesi. S t´ım se setkávaj´ı chemici ve sv´ ych laboratoˇr´ıch, stejnˇe tak tv˚ urci receptur v jakémkoli podniku vyrábˇej´ıc´ım materiály. Jin´ ym pˇr´ıkladem experimentu s omezen´ım m˚ uˇze b´ yt navrhován´ı nosn´ıku, kde je zadána podm´ınka vzájemného pomˇeru v´ yˇsky a ˇs´ıˇrky apod. Ve zde uvádˇen´ ych metodách jsme vˇzdy uvaˇzovali u ´lohu zadanou pomoc´ı vrchol˚ u omezené domény. Tak to ale nemus´ı b´ yt vˇzdy, u ´loha m˚ uˇze b´ yt zadána jen omezuj´ıc´ımi podm´ınkami a vrcholy návrhové domény je pak tˇreba naj´ıt. Je rovnˇeˇz tˇreba rozd´ıln´ y pˇr´ıstup k problému, pokud konkrétn´ı omezuj´ıc´ı podm´ınky známe, nebo neznáme. Napˇr´ıklad urˇcen´ı, zda bod leˇz´ı uvnitˇr nebo vnˇe návrhového prostoru je snadné v prvém pˇr´ıpadˇe, kdy jeho souˇradnice staˇc´ı dosadit do jednotliv´ ych omezuj´ıc´ıch podm´ınek a zjistit, zda jsou splnˇeny. Následuje nˇekolik konkrétn´ıch pˇr´ıklad˚ u, na nichˇz otestujeme uvedené metody pro tvorbu návrh˚ u experiment˚ u.

5.1

Pˇ r´ıklady n´ avrh˚ u s mal´ ym poˇ ctem bod˚ u ve 2D a ve 3D

Nejprve budeme metody aplikovat na sadˇe pˇr´ıklad˚ u zobrazen´ ych na Obrázku 5.1. Ty jsou pˇrevzaty z ˇclánku [Hofwing and Strömberg, 2010] odeˇcten´ım souˇradnic vrchol˚ u. Neuvaˇzujeme zde znalost konkrétn´ıch omezuj´ıc´ıch podm´ınek. Pomˇery objem˚ u daného návrhového prostoru a opsaného hyperkvádru se pohybuj´ı v rozmez´ı 0,5 ((a) a (3D)) a 0,8438 ((7)). Návrhov´ y prostor tedy vyplˇ nuje znaˇcnou ˇcást opsaného hyperkvádru; pˇri pouˇzit´ı metod tvoˇr´ıc´ıch body v opsaném hyperkvádru tedy nen´ı nutné tvoˇrit v´ yraznˇe v´ıce bod˚ u, neˇz je poˇzadováno v zadané omezené doménˇe. 39

ˇ ÍKLADY APLIKACE METOD KAPITOLA 5. PR

1

1

1

0

0

0

-1 0 1 (a) N´ avrhov´ y prostor: troj´ uheln´ık. 6 bod˚ u. Oznaˇcen´ı pˇr´ıkladu: (a). Pomˇer objem˚ u: 0,5000.

-1 0 1 (b) Návrhov´ y prostor: kosodéln´ık. 6 bod˚ u. Oznaˇcen´ı pˇr´ıkladu: (b). Pomˇer objem˚ u: 0,6650.

-1 0 1 (c) Návrhov´ y prostor: pˇeti´ uheln´ık. 6 bod˚ u. Oznaˇcen´ı pˇr´ıkladu: (c). Pomˇer objem˚ u: 0,6917.

1

1

1

0

0

0

-1 0 1 (d) N´ avrhov´ y prostor: ˇsesti´ uheln´ık. 6 bod˚ u. Oznaˇcen´ı pˇr´ıkladu: (d). Pomˇer objem˚ u: 0,7500.

-1 0 1 (e) Návrhov´ y prostor: sedmi´ uheln´ık. 6 bod˚ u. Oznaˇcen´ı pˇr´ıkladu: (e). Pomˇer objem˚ u: 0,7354.

-1 0 1 (f) Návrhov´ y prostor: osmi´ uheln´ık. 6 bod˚ u. Oznaˇcen´ı pˇr´ıkladu: (f ). Pomˇer objem˚ u: 0,8260.

1 1 0 0 -1 0

-1 0 -1 0 1 1 (g) N´ avrhov´ y prostor: (h) Návrhov´ y prostor: kvádr. ˇsesti´ uheln´ık. 12 bod˚ u. 15 bod˚ u. Oznaˇcen´ı pˇr´ıkladu: Oznaˇcen´ı pˇr´ıkladu: (7). Pomˇer (3D). Pomˇer objem˚ u: 0,5000. objem˚ u: 0,8438.

Obrázek 5.1: Pˇr´ıklady návrh˚ u s mal´ ym poˇctem bod˚ u ve 2D a 3D. Na obrázc´ıch jsou vyznaˇceny návrhové prostory a zelen´ ymi body referenˇcn´ı návrhy (z´ıskané metodou popsanou v [Hofwing and Strömberg, 2010]). Dále pak pomˇer objemu návrhové domény a opsaného obdéln´ıku (ve 3D kvádru). Jednotky na osách jsou bezrozmˇerné, popisky os jsou vynechány.

40


5.2

N´ avrh smˇ esi

Následuj´ıc´ı pˇr´ıklady spadaj´ı do skupiny experiment˚ u naz´ yvan´ ych návrh smˇesi. Jak jiˇz bylo ˇreˇceno dˇr´ıve, tento typ experimentu je dán omezuj´ıc´ı podm´ınkou danou Rovnic´ı 1.1. Suma zastoupen´ı jednotliv´ ych sloˇzek smˇesi je tedy pevnˇe dána. Návrhov´ ym prostorem je simplex nebo polytop vznikl´ y ze simplexu d´ıky pˇr´ıtomnosti dalˇs´ıch omezuj´ıc´ıch podm´ınek. Zastoupen´ı jednotliv´ ych sloˇzek takového experimentu je pak dáno ploˇsn´ ymi souˇradnicemi návrhového bodu. Jelikoˇz se vˇsak (na rozd´ıl od filmového pr˚ umyslu, kter´ y vykazuje tendenci pˇridávat jedno D“ za druh´ ym) snaˇz´ıme sn´ıˇzit dimenzionalitu ˇreˇseného ” problému, tvoˇr´ıme návrh experiment˚ u nikoli v ploˇsn´ ych, ale v kartézsk´ ych souˇradnic´ıch. Tˇech je vˇzdy o jednu ménˇe neˇz ploˇsn´ ych, tedy neˇz sloˇzek dané smˇesi. Transformace mezi souˇradn´ ymi soustavami je uvedena v Pˇr´ıloze D.

5.2.1

Trojsloˇ zkov´ a smˇ es

Prvn´ı pˇr´ıklad návrhu smˇesi je pˇrevzat z referenc´ı [Snee, 1979, Piepel, 1988]. Jedná se o trojsloˇzkovou smˇes zadanou omezuj´ıc´ımi podm´ınkami: x1 x1 x1

+

x2

+

x3

x2 x2 85 · x1 85 · x1 0, 7 · x1

+ +

90 · x2 90 · x2

x3 + 100 · x3 + 100 · x3 + x3

= ≥ ≤ ≥ ≤ ≤ ≥ ≤ ≥

1 0, 1 0, 5 0, 1 0, 7 0, 7 90 95 0, 4

Dˇr´ıve, neˇz m˚ uˇzeme zaˇc´ıt tvoˇrit návrh experiment˚ u, je tˇreba naj´ıt vrcholy návrhové domény. To je moˇzné provést pomoc´ı simplexové metody, nebot’ se jedná o u ´lohu lineárn´ıho programován´ı [Demel, 2011]. Hledáme krajn´ı body mnoˇziny pˇr´ıpustn´ ych ˇreˇsen´ı. Cel´ y postup ruˇcn´ıho“ ˇreˇsen´ı je uveden v Pˇr´ıloze F. V´ ysledkem je 6 vrchol˚ u o tˇrech souˇradnic´ıch. ” Ty po vynesen´ı do 3D prostoru (Obrázek 5.2) tvoˇr´ı ovˇsem pouze 2-dimenzionáln´ı objekt - ˇcást roviny. To je dáno právˇe onou souˇctovou podm´ınkou. Návrhov´ y prostor jde pˇrevést do 2D a body popisovat stejnou trojic´ı souˇradnic jako v prostoru. Ve 2D se vˇsak bude jednat o trojici souˇradnic ploˇsn´ ych. Pomoc´ı transformace mezi ploˇsn´ ymi a kartézsk´ ymi souˇradnicemi vˇsak m˚ uˇzeme body popisovat pouze dvˇema kartézsk´ ymi souˇradnicemi (oznaˇceny K1 a K2 ), jak je znázornˇeno na Obrázku 5.3. Takto s body zacház´ıme v této práci. Pomˇer objem˚ u návrhové domény a jednoduchého opsaného obdéln´ıku je v tomto pˇr´ıpadˇe roven 0,6236; i zde je tedy moˇzné pouˇz´ıt metodu bounding boxu. 41


Obrázek 5.2: Krajn´ı body mnoˇziny pˇr´ıpustn´ ych ˇreˇsen´ı z´ıskané pomoc´ı simplexové metody (Pˇr´ıloha F).

Obrázek 5.3: Krajn´ı body mnoˇziny pˇr´ıpustn´ ych ˇreˇsen´ı v trojosé soustavˇe se znázornˇen´ım jednotliv´ ych omezuj´ıc´ıch podm´ınek.

42


5.2.2

ˇ Sestisloˇ zkov´ a smˇ es

Posledn´ı pˇr´ıklad popisuje návrh ˇsestisloˇzkové smˇesi, konkrétnˇe vysokopevnostn´ıho betonu. Je pˇrevzat´ y z referenc´ı [Simon et al., 1997, Simon, 2003]. Je rovnˇeˇz zadán pouze pomoc´ı následuj´ıc´ıch omezuj´ıc´ıch podm´ınek: Podm´ınka návrhu smˇesi Voda (Water) Cement Kˇremiˇcit´ yu ´let (Silica fume) Plastifikátor HRWRA Hrubé kamenivo (Coarse aggregate) Jemné kamenivo (Fine aggregate)

x1 + x2 + x3 + x4 + x5 + x6 = 1 0, 16 ≤ x1 ≤ 0, 185 0, 13 ≤ x2 ≤ 0, 15 0, 013 ≤ x3 ≤ 0, 027 0, 0046 ≤ x4 ≤ 0, 0074 0, 40 ≤ x5 ≤ 0, 4424 0, 25 ≤ x6 ≤ 0, 2924

Hledat vrcholy návrhového prostoru pˇr´ısluˇsného tˇemto omezuj´ıc´ım podm´ınkám ruˇcnˇe“ ” (jako u pˇredchoz´ıho pˇr´ıkladu) by bylo znaˇcnˇe zdlouhavé. Proto byl zvolen zp˚ usob zaloˇzen´ y na stejné metodˇe, ovˇsem pomoc´ı funkce linprog z programového prostˇred´ı MATLAB. Ta ovˇsem nen´ı urˇcena pro hledán´ı krajn´ıch bod˚ u mnoˇziny pˇr´ıpustn´ ych ˇreˇsen´ı, n´ ybrˇz pro hledán´ı optimáln´ıho ˇreˇsen´ı pˇri zadané c´ılové funkci (smˇeru hledán´ı). Hledán´ı krajn´ıch bod˚ u bylo tedy provedeno tak, ˇze byl ˇreˇsiˇc spuˇstˇen mnohokrát s r˚ uznou c´ılovou funkc´ı (aby nahlédl do mnoha r˚ uzn´ ych smˇer˚ u“). Tak bylo z´ıskáno velké mnoˇzstv´ı krajn´ıch bod˚ u. ” Po odstranˇen´ı duplikát˚ u je za mnoˇzinu vrchol˚ u návrhové domény povaˇzováno 51 bod˚ u. I zde uvád´ıme pomˇer objem˚ u návrhové domény a opsaného hyperkvádru, ten je roven 0,1630. Návrh v opsaném hyperkvádru tedy vytváˇr´ıme se 7násobkem bod˚ u, neˇz je c´ılem v omezeném prostoru. V obou pˇr´ıkladech návrhu smˇesi bylo pro porovnán´ı metod tvorby experiment˚ u tvoˇreno 10 a 100 návrhov´ ych bod˚ u.

43

Kapitola 6 Implementace Veˇskeré metody popsané v této práci byly implementovány v programovém prostˇred´ı MATLAB R2010a. Kromˇe bˇeˇzn´ ych funkc´ı byly pouˇz´ıvány funkce lhsdesign pro tvorbu neoptimalizovaného LHS návrhu v regulárn´ım prostoru, funkce delaunayn pro sestrojen´ı Delaunayovu triangulace, funkce voronoin pro konstrukci Voronoiova diagramu nebo funkce linprog pro hledán´ı krajn´ıch bod˚ u mnoˇziny pˇr´ıpustn´ ych ˇreˇsen´ı. Nástroj Distmesh byl staˇzen z webové stránky http://persson.berkeley.edu/distmesh/distmesh.zip.

44

Kapitola 7 V´ ysledky Následuj´ıc´ı sekce pˇrináˇsej´ı v´ ysledky a srovnán´ı metod pˇredstaven´ ych v této práci.

7.1

Porovn´ an´ı metod vyhodnocen´ı krit´ eria miniMax

Na vˇsech pˇr´ıkladech, v nichˇz bylo moˇzno pouˇz´ıt exaktn´ı metodu pro vyhodnocen´ı miniMax kritéria (vˇsechny 2D a 3D pˇr´ıklady, na pˇr´ıklad se ˇsestisloˇzkovou smˇes´ı jiˇz nepostaˇcovaly v´ ypoˇcetn´ı prostˇredky pouˇzitého poˇc´ıtaˇce) tato metoda poskytla v´ ysledek následnˇe potvrzen´ y evoluˇcn´ı strategi´ı. Byla rovnˇeˇz testována na ˇradˇe dalˇs´ıch dvou- aˇz ˇctyˇrdimenzionáln´ıch pˇr´ıklad˚ u s pozitivn´ım v´ ysledkem. Lze tedy konstatovat, ˇze se exaktn´ı metoda pro vyhodnocen´ı miniMax kritéria vyuˇz´ıvaj´ıc´ı zrcadlen´ı návrhov´ ych bod˚ u a Voronoiova diagramu zdá pouˇzitelná jak v regulárn´ım, tak v konvexn´ım omezeném návrhovém prostoru. Ve vyˇsˇs´ıch dimenz´ıch je tˇreba spokojit se s odhadem hodnoty kritéria miniMax z´ıskan´ ym pomoc´ı evoluˇcn´ı strategie. V omezeném návrhovém prostoru je jej´ı sériová verze v souˇcasné u ´rovni implementace v praxi nepouˇzitelná. V rámci testován´ı byla pouˇzita na jeden z návrh˚ u experiment˚ u vytvoˇren´ ych pro pˇr´ıklad ˇsestisloˇzkové smˇesi z Kapitoly 5. Bylo tedy moˇzné vyuˇz´ıt znalosti konkrétn´ıch omezuj´ıc´ıch podm´ınek a zjiˇstˇen´ı, zda body metoda vracen´ı bod˚ u ˇ cas [s] sériová verze pomocná sada bod˚ u 1308 s sériová verze nulován´ı záporn´ ych pl. s. 7225 s sériová verze kolm´ y pr˚ umˇet paraleln´ı verze (1 CPU) nulován´ı záporn´ ych pl. s. 35 s ˇ Tabulka 7.1: Casov´ a nároˇcnost verz´ı evoluˇcn´ı strategie pro vyˇc´ıslen´ı mM . Testováno na návrhu se 100 body v návrhovém prostoru ˇsestisloˇzkové smˇesi popsané v Kapitole 5. Pouˇzito bylo 50 chromozom˚ u a celkov´ y poˇcet 6900 generac´ı.

45

´ KAPITOLA 7. VYSLEDKY

leˇz´ı vnˇe ˇci uvnitˇr návrhové domény, neprovádˇet v´ ypoˇcetnˇe nároˇcn´ ymi zp˚ usoby“, n´ ybrˇz ” pouze ovˇeˇren´ım (ne)splnˇen´ı tˇechto podm´ınek. Pˇresto byl ˇcas potˇrebn´ y k vyhodnocen´ı nesrovnatelnˇe vyˇsˇs´ı neˇz u verze paraleln´ı, byt’ s pouˇzit´ım jediné v´ ypoˇcetn´ı jednotky (CPU), jak uvád´ı Tabulka 7.1. V´ yraznˇe lepˇs´ıch v´ ysledk˚ u dosahuje paraleln´ı verze evoluˇcn´ı strategie pro vyhodnocen´ı miniMax kritéria. Pro vracen´ı bod˚ u, jeˇz mutac´ı opustily jednotlivé subdomény (simplexy ztriangulované domény), byla pouˇzita metoda nulován´ı záporn´ ych ploˇsn´ ych souˇradnic popsaná v Sekci 4.2. Obrázek 7.1a zobrazuje speed-up pˇri pouˇzit´ı 2, 4, 6 a 8 v´ ypoˇcetn´ıch jednotek. Za v´ ychoz´ı vyhodnocen´ı (bod [1,1]) nen´ı z v´ yˇse popsan´ ych d˚ uvod˚ u povaˇzována sériová verze v´ ypoˇctu, n´ ybrˇz verze v´ ypoˇctu v subdoménách s pouˇzit´ım jedné v´ ypoˇcetn´ı jednotky. Jednotlivé kˇrivky odpov´ıdaj´ı r˚ uzn´ ym volbám poˇctu generac´ı ve v´ ypoˇctu. Vid´ıme, ˇze ˇc´ım vˇetˇs´ı“ je u ´loha, t´ım v´ yraznˇejˇs´ıho zrychlen´ı dosahujeme pomoc´ı pouˇzit´ı v´ıce v´ ypoˇcet” n´ıch jednotek. To je dáno pˇredevˇs´ım t´ım, ˇze ˇcas nutn´ y ke zparalelizován´ı u ´lohy hraje u u ´lohy s n´ızk´ ym poˇctem generac´ı znaˇcnou roli, zat´ımco u u ´lohy celkovˇe déle trvaj´ıc´ı se ztrác´ı. Obrázek 7.1b zobrazuje boxplot odhad˚ u hodnoty miniMax z´ıskan´ ych pomoc´ı paraleln´ı verze s r˚ uzn´ ym poˇctem generac´ı. Vid´ıme, ˇze je splnˇen pˇredpoklad, ˇze ˇc´ım v´ıce generac´ı je pouˇzito, t´ım lepˇs´ıho (vyˇsˇs´ıho, tedy skuteˇcnosti bliˇzˇs´ıho) v´ ysledku dosáhneme;

-3

x 10 8.3

8 8.25

7 8.2 8.15 mM [-]

Speed-up

6 5 4

8.1 8.05

3 8

2 7.95

1 7.9 6900

1

2

4 6 Počet CPU

8

(a) Speed-up paraleln´ı verze evoluˇcn´ı strategie.

34500 172500 Počet generací (iterací)

(b) Boxplot odhad˚ u hodnot kritéria miniMax pomoc´ı paraleln´ı verze evoluˇcn´ı strategie.

Obrázek 7.1: V´ ysledky paraleln´ı evoluˇcn´ı strategie pro vyˇc´ıslen´ı mM . Pˇri testován´ı bylo pouˇzito 50 chromozom˚ u. Zelené objekty odpov´ıdaj´ı celkovému poˇctu 6900 generac´ı ve v´ ypoˇctu (20 generac´ı v kaˇzdé subdoménˇe), ˇcervené objekty 34500 generac´ı ve v´ ypoˇctu (100 generac´ı v kaˇzdé subdoménˇe), modré objekty 172500 generac´ı ve v´ ypoˇctu (500 generac´ı v kaˇzdé subdoménˇe).

46


samozˇrejmˇe za cenu delˇs´ıho ˇcasu v´ ypoˇctu. Lze tedy konstatovat, ˇze k vyhodnocen´ı kritéria miniMax v omezen´ ych prostorech je vhodné pouˇzit´ı exaktn´ı metody v n´ızk´ ych dimenz´ıch a paraleln´ı verze metody zaloˇzené na algoritmu evoluˇcn´ı strategie (s pouˇzit´ım co nejvyˇsˇs´ıho poˇctu v´ ypoˇcetn´ıch jednotek) v dimenz´ıch vyˇsˇs´ıch. Je tˇreba pamatovat na to, ˇze pomoc´ı evoluˇcn´ı strategie z´ıskáme pouze odhad hodnoty kritéria miniMax, skuteˇcná hodnota m˚ uˇze b´ yt vˇzdy vyˇsˇs´ı.

7.2

Porovn´ an´ı metod tvorby n´ avrh˚ u experiment˚ u

V´ ysledky tvorby návrh˚ u experiment˚ u v návrhov´ ych prostorech odpov´ıdaj´ıc´ıch pˇr´ıklad˚ um uveden´ ym v Kapitole 5 jsou uvedeny na Obrázc´ıch 7.2 a 7.3. Jedná se o statistiku ze 100, respektive 10 (u ˇcasovˇe nároˇcnˇejˇs´ıch metod) spuˇstˇen´ı. Metody porovnáváme z hlediska tˇr´ı kritéri´ı - metrik EM M a mM a ˇcasové nároˇcnosti. Kompletn´ı informaci o v´ ysledc´ıch by tedy pˇrináˇsel trojrozmˇern´ y graf. Pro lepˇs´ı orientaci vˇsak byly pro vizualizaci v´ ysledk˚ u zvoleny dva grafy dvojrozmˇerné. Spodn´ı ˇca´st jednotliv´ ych obrázk˚ u ukazuje kvalitu vznikl´ ych návrh˚ u - tedy porovnán´ı kritéri´ı EM M a mM . Kritérium Maximin se snaˇz´ıme maximalizovat, zat´ımco u kritéria miniMax je ˇza´douc´ı co nejniˇzˇs´ı hodnota nejkvalitnˇejˇs´ı návrhy z pohledu rovnomˇernosti pokryt´ı se tedy nalézaj´ı v pravém doln´ım rohu tohoto grafu. Horn´ı ˇca´st obrázk˚ u potom pˇrináˇs´ı informace o ˇcasové nároˇcnosti jednotliv´ ych metod tvorby. Na vodorovné ose je, stejnˇe jako na spodn´ım grafu, vynesena hodnota EM M , i u tohoto grafu tedy leˇz´ı nejv´ yhodnˇejˇs´ı návrhy v pravém doln´ım rohu. Legenda k obrázk˚ um je uvedena n´ıˇze:

0.6

-0.4

-0.2

0.6

-0.4

-0.2

-1

0

generátor náhodn´ ych bod˚ u (Sekce 3.1) neoptimalizovan´ y LHS návrh v opsaném hyperkvádru (Sekce 3.2) optimalizovan´ y LHS návrh v opsaném hyperkvádru (Sekce 3.2) ub´ ır´ an´ ı (Sekce 3.3.1) (22 · np → np, 23 · np → np, 24 · np → np, ...) b. ub´ ır´ an´ ı NEW (Sekce 3.3.2) (22 · np → np, 23 · np → np, 24 · np → np, ...) b. nástroj Distmesh I (Sekce 3.4) nástroj Distmesh II (Sekce 3.4) pozn.: u metod s odeb´ırán´ım bod˚ u z pˇrehuˇstˇeného návrhu bylo vˇzdy vyzkouˇseno nˇekolik u ´rovn´ı pˇrehuˇstˇen´ı v´ ychoz´ıho návrhu, oznaˇcen´ı (x → y) znamená y bod˚ u v návrhu zbyl´ ych po odeb´ırán´ı z x p˚ uvodnˇe vytvoˇren´ ych 0

0.2

0.4

0.6

0.8

1

0

0.2

0.4

0.6

0.8

1

1

2

3

4

0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

1

0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

1

0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

1

0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

1

V´ ysledky jasnˇe naznaˇcuj´ı korelaci mezi kritérii Maximin a miniMax. Dá se tedy ˇr´ıci, ˇze optimalizac´ı jednoho z nich se zlepˇsuje kvalita návrhu i z pohledu druhého kritéria. Ve 2D jednoznaˇcnˇe dominuje tvorba návrhu experimentu pomoc´ı nástroje Distmesh, aˇckoli je jeho ˇcasová nároˇcnost vyˇsˇs´ı neˇz u ostatn´ıch metod, coˇz je dáno opakovanou triangulac´ı bˇehem bˇehu algoritmu. Jiˇz ve 3D se vˇsak jeho pouˇzit´ı nevyplat´ı, nebot’ jeho

47


5

5

-5

10 čas [s]

0

10

0

10

-5

0.5 0

0.5 EMM [-]

10

1 mM [-]

1

0.6

0.4 0

1

0

10

-5

10 0.8 mM [-]

10 1.5 mM [-]

5

10 čas [s]

čas [s]

10

0.2

0.4 EMM [-]

0.6

0.9 0.8 0.7 0.2

0.8

0.4

0.6 EMM [-]

0.8

1

(a) N´ avrhov´ y prostor: (b) Návrhov´ y prostor: ko- (c) Návrhov´ y prostor: troj´ uheln´ık. 6 bod˚ u. Oznaˇcen´ı sodéln´ık. 6 bod˚ u. Oznaˇcen´ı pˇeti´ uheln´ık. 6 bod˚ u. Oznaˇcen´ı pˇr´ıkladu: (a). pˇr´ıkladu: (b). pˇr´ıkladu: (c). 5

5

-5

0

10

-5

-5

10

1

0.9

0.9

mM [-]

1

0.8 0.4

0.6 EMM [-]

0.8

1

0

10

10 1.5 mM [-]

10

mM [-]

10 čas [s]

0

10

0.7 0.2

5

10 čas [s]

čas [s]

10

0.8 0.7 0.2

0.4

0.6 EMM [-]

0.8

1

1

0.5 0.2

0.4

0.6 EMM [-]

0.8

1

(d) N´ avrhov´ y prostor: (e) Návrhov´ y prostor: (f) Návrhov´ y prostor: ˇsesti´ uheln´ık. 6 bod˚ u. Oznaˇcen´ı sedmi´ uheln´ık. 6 bod˚ u. Oznaˇcen´ı osmi´ uheln´ık. 6 bod˚ u. Oznaˇcen´ı pˇr´ıkladu: (d). pˇr´ıkladu: (e). pˇr´ıkladu: (f ). 5

10 čas [s]

čas [s]

10

0

10

10 1.2 mM [-]

mM [-]

0

-5

-5

10 0.8

0.6

0.4 0

10

5

0.2

0.4 EMM [-]

0.6

1

0.8 0

0.8

0.2

0.4 EMM [-]

0.6

0.8

(g) N´ avrhov´ y prostor: (h) Návrhov´ y prostor: kvádr. 15 ˇsesti´ uheln´ık. 12 bod˚ u. Oznaˇcen´ı bod˚ u. Oznaˇcen´ı pˇr´ıkladu: (3D). pˇr´ıkladu: (7).

Obrázek 7.2: V´ ysledky metod tvorby na 2D a 3D pˇr´ıkladech. 48


5

5

10 čas [s]

čas [s]

10

0

10

-5

-5

10 0.08 mM [-]

mM [-]

10 0.2

0.15

0.1 0

0.05 0.1 EMM [-]

5

0.02 0.03 EMM [-]

0.04

5

10

0

-5

0

10

-5

10 0.015 mM [-]

0.03 0.02 0.01 0

0.01

(b) Trojsloˇzková smˇes. 100 bod˚ u.

10 0.04 mM [-]

0.04

čas [s]

čas [s]

10

0.06

0.02 0

0.15

(a) Trojsloˇzkov´ a smˇes. 10 bod˚ u. 10

0

10

0.005 0.01 EMM [-]

0.005 0

0.015

ˇ (c) Sestisloˇ zkov´ a smˇes. 10 bod˚ u.

0.01

2

4 EMM [-]

6 -3 x 10

ˇ (d) Sestisloˇ zková smˇes. 100 bod˚ u.

Obrázek 7.3: V´ ysledky metod tvorby na pˇr´ıkladech návrh˚ u smˇes´ı. v´ ypoˇcetn´ı nároky rostou, zat´ımco kvalita j´ım tvoˇren´ ych návrh˚ u v porovnán´ı s jin´ ymi metodami klesá. V pˇr´ıpadˇe ˇsestisloˇzkové smˇesi byl dokonce metodou vytvoˇren návrh s duplikovan´ ymi body. Generátor náhodn´ ych bod˚ u v jednotliv´ ych simplexech ztriangulované omezené domény byl ve vˇsech pˇr´ıkladech nejrychlejˇs´ı metodou, kvalita j´ım vytvoˇren´ ych návrh˚ u vˇsak byla aˇz na v´ yjimky nejniˇzˇs´ı. Lepˇs´ıch v´ ysledk˚ u dosahuje metoda vyb´ırán´ı bod˚ u z LHS návrhu vytvoˇreném v hyperkvádru opsaném omezené doménˇe. V´ ysledky potvrzuj´ı, ˇze pouˇzit´ı optimalizovaného LHS návrhu m´ısto neoptimalizovaného zajiˇst’uje lepˇs´ı v´ ysledek i v omezené doménˇe. Z˚ ustává vˇsak otázka poˇctu bod˚ u, jeˇz tvoˇrit v opsaném regulárn´ım prostoru. Zde jsme vycházeli z pomocného v´ ypoˇctu pomˇeru objem˚ u. Takto jsme se vˇsak pˇresnˇe do poˇzadovaného poˇctu bod˚ u uvnitˇr omezené domény trefili“ pr˚ umˇernˇe jednou z 29 pokus˚ u (v jednom ” z pˇr´ıklad˚ u dokonce jednou z 263 pokus˚ u). Jelikoˇz stejnˇe nen´ı moˇzné o návrhu takto vytvoˇreném v omezené doménˇe hovoˇrit jako o návrhu LHS, nab´ız´ı se moˇznost zkombinován´ı 49


této metody s metodou odeb´ırán´ı bod˚ u z pˇrehuˇstˇeného návrhu. Pˇrebyteˇcné body v omezené doménˇe se jednoduˇse odeberou pomoc´ı této metody. Samotná metoda odeb´ırán´ı bod˚ u ze zámˇernˇe pˇrehuˇstˇeného návrhu dosahuje velmi dobr´ ych v´ ysledk˚ u. V posledn´ım pˇr´ıkladu je Pareto-front dokonce tvoˇren právˇe jen touto metodou. Druhá varianta, kde je pozornost vˇenována konkrétn´ı volbˇe odebraného bodu z aktuálnˇe vzájemnˇe si nejbliˇzˇs´ı dvojice bod˚ u, dosahuje lepˇs´ıch v´ ysledk˚ u pˇri naprosto srovnatelném ˇcase. Uˇzivatel si m˚ uˇze snadno zvolit m´ıru pˇrehuˇstˇen´ı v´ ychoz´ıho návrhu a tak ovlivnit jak ˇcas, tak kvalitu v´ ysledného návrhu. Je patrná pozitivn´ı korelace mezi m´ırou pˇrehuˇstˇen´ı v´ ychoz´ıho návrhu a kvalitou v´ ysledného návrhu, ovˇsem jen do jisté m´ıry. Ve zde uvádˇen´ ych pˇr´ıkladech nemá v´ yznam tvoˇrit ve v´ ychoz´ım návrhu v´ıce neˇz 30násobek poˇzadovan´ ych bod˚ u. Na základˇe pˇredloˇzen´ ych v´ ysledk˚ u m˚ uˇzeme jako nejvhodnˇejˇs´ı metody pro tvorbu návrh˚ u experiment˚ u v omezen´ ych návrhov´ ych prostorech v n´ızké dimenzi oznaˇcit pouˇzit´ı nástroje Distmesh. Ve vyˇsˇs´ıch dimenz´ıch se potom nejv´ıce osvˇedˇcilo vytvoˇren´ı pˇrehuˇstˇeného návrhu a následné heuristické odeb´ırán´ı bod˚ u aˇz k dosaˇzen´ı jejich poˇzadovaného poˇctu.

50

Kapitola 8 Z´ avˇ er Návrh experiment˚ u, j´ımˇz se zab´ yvala tato diplomová práce, slouˇz´ı k naplánován´ı konkrétn´ıch proveden´ı experiment˚ u v pˇr´ıpadech, kdy je moˇzno volit hodnoty jednotliv´ ych vstupn´ıch parametr˚ u. C´ılem je pokr´ yt zvolen´ ym poˇctem návrhov´ ych bod˚ u (jejichˇz souˇradnice odpov´ıdaj´ı kombinac´ım konkrétn´ıch hodnot vstupn´ıch parametr˚ u) zadan´ y prostor, jak nejrovnomˇernˇeji je to moˇzné, abychom z´ıskali co nejlepˇs´ı pˇredstavu o chován´ı systému, kter´ y je na tˇechto vstupn´ıch parametrech závisl´ y. Návrh experiment˚ u je tak nepostradateln´ ym nástrojem v mnoha oblastech vˇedy, v´ yzkumu i pr˚ umyslu. Aplikac´ı kvalitn´ıho návrhu je snad moˇzno zm´ırnit obavu mezi ˇrádky vypl´ yvaj´ıc´ı z citátu, j´ımˇz byla tato práce uvedena. Práce se vˇenovala návrh˚ um experiment˚ u v omezen´ ych návrhov´ ych prostorech, tedy v situac´ıch, kdy jsou zadány omezuj´ıc´ı podm´ınky a jednotlivé vstupn´ı parametry jsou na sobˇe závislé. Bylo pˇredstaveno nˇekolik metod pro tvorbu návrh˚ u v odpov´ıdaj´ıc´ıch návrhov´ ych prostorech a návrhy tˇemito metodami vytvoˇrené byly hodnoceny dvˇema kritérii. Rovnˇeˇz byla hodnocena ˇcasová nároˇcnost tˇechto metod. V dalˇs´ı práci se hodláme zamˇeˇrit na zefektivnˇen´ı nˇekter´ ych z metod tvorby návrh˚ u i jejich hodnocen´ı. Napˇr´ıklad zrychlen´ı vyˇc´ıslen´ı odhadu kritéria miniMax pomoc´ı evoluˇcn´ı strategie s jinou formou mutace chromozom˚ u. Samo kritérium miniMax je námˇetem pro dalˇs´ı práci. Stˇred nejvˇetˇs´ı prázdné hyperkoule se jev´ı jako ideáln´ı kandidát pˇri adaptivn´ım samplován´ı, tedy v situac´ıch, kdy je tˇreba pˇridávat dalˇs´ı body do návrhu experiment˚ u. Samotná vzdálenost od jiˇz um´ıstˇen´ ych návrhov´ ych bod˚ u nav´ıc nemus´ı b´ yt jedin´ ym kritériem pro um´ıstˇená dalˇs´ıho bodu. Napˇr´ıklad v oboru stochastické spolehlivosti konstrukc´ı m˚ uˇze b´ yt dalˇs´ım kritériem vzdálenost k hranici poruchy (limit state function), tedy k rozmez´ı mezi oblast´ı bezpeˇcnou a oblast´ı poruchy. V tomto prostoru je zpravidla ˇza´douc´ı vyˇsˇs´ı zahuˇstˇen´ı návrhu, jak je patrné i na pˇredbˇeˇzn´ ych v´ ysledc´ıch v [Myˇsa´ková and Lepˇs, 2013b, Posp´ıˇsilová and Lepˇs, 2013] nebo v [Myˇsa´ková et al., 2013, Posp´ıˇsilová et al., 2013].

51

Literatura [Sim, 2002] (2002). Hypercube. www stránky: http://en.wikipedia.org/wiki/Simplex/. Posledn´ı zmˇena 3. listopadu 2013. [Hyp, 2002] (2002). Hypercube. www stránky: http://en.wikipedia.org/wiki/Hypercube/. Posledn´ı zmˇena 31. ˇr´ıjna 2013. [JMP, 2005] (2005). JMP design of experiments, release 6. SAS Institute Inc., Cary, NC, USA. [Auffray et al., 2012] Auffray, Y., Barbillon, P., and Marin, J.-M. (2012). Maximin design on non hypercube domains and kernel interpolation. Statistics and Computing, 22(3):703–712. [Bäck and Schwefel, 1995] Bäck, T. and Schwefel, H.-P. (1995). Evolution Strategies I: Variants and their computational implementation. In Periaux and Winter, editors, Genetic Algorithms in Engineering and Computer Science, chapter 6, pages 111–126. John Wiley & Sons Ltd. [Chan, 2000] Chan, L.-Y. (2000). Optimal designs for experiments with mixtures: A survey. Communications in Statistics. Theory and Methods, 29(9-10):2281–2312. [Chen and Holst, 2011] Chen, L. and Holst, M. (2011). Efficient mesh optimization schemes based on Optimal Delaunay Triangulations. Computer Methods in Applied Mechanics and Engineering, 200(9-12):967–984. [Cioppa and Lucas, 2007] Cioppa, T. M. and Lucas, T. (2007). Efficient nearly orthogonal and space-filling latin hypercubes. Technometrics, 49(1):45–55. [Cornell, 1973] Cornell, J. A. (1973). Experiments with Mixtures: A Review. Technometrics, 15(3):437–455. [Cornell, 1979] Cornell, J. A. (1979). Experiments with Mixtures: An Update and Bibliography. Technometrics, 21(1):95–106. [Crombecq et al., 2009] Crombecq, K., Couckuyt, I., Gorissen, D., and Dhaene, T. (2009). Space-filling sequential design strategies for adaptive surrogate modelling. In Topping, B. H. V. and Tsompanakis, Y., editors, Proceedings of the First International Conference on Soft Computing Technology in Civil, Structural and Environmental Engineering. Civil-Comp Press, Stirlingshire, UK. [Cruise, 1966] Cruise, D. R. (1966). Plotting the composition of mixtures on simplex coordinates. Journal of Chemical Education, 43(1):30. 52

LITERATURA

[Demel, 2011] Demel, J. (2011). Operaˇcn´ı v´ yzkum. Skriptum, Katedra aplikované inforˇ matiky, Fakulta stavebn´ı, Ceské vysoké uˇcen´ı technické v Praze. [Devadoss and O’Rourke, 2011] Devadoss, S. and O’Rourke, J. (2011). Discrete and Computational Geometry. Princeton University Press. [Devroye, 1986] Devroye, L. (1986). Non-uniform random variate generation. SpringerVerlag. [Dickerson and Eppstein, 1995] Dickerson, M. and Eppstein, D. (1995). Algorithms for proximity problems in higher dimensions. Comput. Geom., 5:277–291. [Draguljic et al., 2012] Draguljic, D., Dean, A. M., and Santner, T. J. (2012). Noncollapsing space-filling designs for bounded nonrectangular regions. Technometrics, 54(2):169–178. [Fang et al., 2006] Fang, K., Li, R.-Z., and Sudjianto, A. (2006). Design And Modeling for Computer Experiments. Computer Science & Data Analysis. CRC PressINC. [Fang and Yang, 2000] Fang, K.-T. and Yang, Z.-H. (2000). On uniform design of experiments with restricted mixtures and generation of uniform distribution on some domains. Statistics & Probability Letters, 46(2):113–120. [Fauvel et al., 1993] Fauvel, J., Flood, R., and Wilson, R. (1993). Möbius and his band: mathematics and astronomy in nineteenth-century Germany. Oxford University Press. [Grosso et al., 2009] Grosso, A., Jamali, A. R. M. J. U., and Locatelli, M. (2009). Finding maximin latin hypercube designs by iterated local search heuristics. European Journal of Operational Research, 197(2):541–547. [Hofwing and Strömberg, 2010] Hofwing, M. and Strömberg, N. (2010). D-optimality of non-regular design spaces by using a bayesian modification and a hybrid method. Structural and multidisciplinary optimization (Print), 42(1):73–88. [Janouchová and Kuˇcerová, 2013] Janouchová, E. and Kuˇcerová, A. (2013). Competitive comparison of optimal designs of experiments for sampling-based sensitivity analysis. Computers & Structures, 124(0):47 – 60. [Joe and Wang, 1993] Joe, B. and Wang, C. (1993). Duality of constrained Voronoi diagrams and Delaunay triangulations. Algorithmica, 9(2):142–155. [Johnson et al., 1990] Johnson, M. E., Moore, L. M., and Ylvisaker, D. (1990). Minimax and maximin distance designs. Journal of Statistical Planning and Inference, 26(2):131– 148. [Khuri, 2006] Khuri, A. (2006). Response Surface Methodology And Related Topics. World Scientific. [Lee et al., 2004] Lee, J.-S., Cho, T.-S., Lee, J., Jang, M.-K., Jang, T.-K., Nam, D., and Park, C. H. (2004). A stochastic search approach for the multidimensional largest empty sphere problem. 53

LITERATURA

[Lepˇs, 2009] Lepˇs, M. (2009). Soft computing methods in concrete mix performance approximation and optimization. Associate Professor Thesis, Faculty of civil engineering, Czech technical university in Prague. [Liang et al., 2001] Liang, Y., Fang, K., and Xu, Q. (2001). Uniform design and its applications in chemistry and chemical engineering. Chemometrics and Intelligent Laboratory Systems, 58(1):43 – 57. [Montgomery, 2000] Montgomery, D. C. (2000). Design and Analysis of Experiments, 5th Edition. Wiley. [Morris, 2014] Morris, M. D. (2014). Maximin distance optimal designs for computer experiments with time-varying inputs and outputs. Journal of Statistical Planning and Inference, 144(0):63 – 68. [Myˇsáková, 2012] Myˇsa´ková, E. (2012). Metody pro tvorbu rovnomˇernˇe rozprostˇren´ ych ˇ návrh˚ u. Bakaláˇrská práce, Katedra mechaniky, Fakulta stavebn´ı, Ceské vysoké uˇcen´ı technické v Praze. [Myˇsáková, 2013] Myˇsa´ková, E. (2013). Paraleln´ı evoluˇcn´ı strategie pro vyhodnocen´ı miˇ e vysoké niMax kritéria. Soutˇeˇzn´ı práce, Katedra mechaniky, Fakulta stavebn´ı, Cesk´ uˇcen´ı technické v Praze. [Myˇsáková and Lepˇs, 2011] Myˇsa´ková, E. and Lepˇs, M. (2011). Comparison of spacefilling design strategies. In Proceedings of the 17th International Conference Engineering ´ ˇ Mechanics, pages 399–402. Ustav termomechaniky AV CR. [Myˇsáková and Lepˇs, 2012] Myˇsa´ková, E. and Lepˇs, M. (2012). Method for constrained designs of experiments in two dimensions. In Proceedings of the 18th International ´ ˇ Conference Engineering Mechanics, pages 222–224. Ustav termomechaniky AV CR. [Myˇsáková and Lepˇs, 2013b] Myˇsa´ková, E. and Lepˇs, M. (2013b). Multiobjective minimax designs of experiments. In Proceedings of the 19th International Conference ´ ˇ Engineering Mechanics, pages 371–379. Ustav termomechaniky AV CR. [Myˇsáková and Lepˇs, 2013c] Myˇsa´ková, E. and Lepˇs, M. (2013c). Uniform Designs of Experiments for Asymptotic Sampling. In Proceedings of the 4th Conference Nano & Macro Mechanics, pages 143–150. Praha: Czech Technical University in Prague. [Myˇsáková and Lepˇs, 2013a] Myˇsa´ková, E. and Lepˇs, M. (Sent for publication, 2013a). Comparison of parallel evolutionary approaches for minimax metric of designs of experiments. Advances in Engineering Software. [Myˇsáková et al., 2012] Myˇsa´ková, E., Lepˇs, M., and Kuˇcerová, A. (2012). A Method for Maximin Constrained Design of Experiments. In Topping, B. H. V., editor, Proceedings of the Eighth International Conference on Engineering Computational Technology. Civil-Comp Press, Stirlingshire, UK. [Myˇsáková et al., 2013] Myˇsa´ková, E., Posp´ıˇsilová, A., and Lepˇs, M. (2013). Multiobjective Adaptive Updating of Surrogate Models. In Proceedings of the 19th International ´ ˇ Conference Engineering Mechanics, pages 87–88. Ustav termomechaniky AV CR. 54

LITERATURA

[Okabe et al., 2000] Okabe, A., Boots, B., Sugihara, K., and Chiu, S. N. (2000). Spatial tessellations: concepts and applications of Voronoi diagrams. Wiley series in probability and statistics: Applied probability and statistics. Wiley. [Persson and Strang, 2004] Persson, P.-O. and Strang, G. (2004). A simple mesh generator in MATLAB. SIAM Review, 46(2):329–345. [Petelet et al., 2010] Petelet, M., Iooss, B., Asserin, O., and Loredo, A. (2010). Latin hypercube sampling with inequality constraints. AStA Advances in Statistical Analysis, 94:325–339. 10.1007/s10182-010-0144-z. [Piepel, 1988] Piepel, G. (1988). Programs for generating extreme vertices and centroids of linearly constrained experimental regions. Journal of Quality Technology, 20(2):125– 139. [Posp´ıˇsilová and Lepˇs, 2013] Posp´ıˇsilová, A. and Lepˇs, M. (2013). Multi-Objective Optimization with Asymptotic Sampling for RBDO. In Proceedings of The Third International Conference on Soft Computing Technology in Civil, Structural and Environmental Engineering. Civil-Comp Press, Stirlingshire, UK. [Posp´ıˇsilová et al., 2013] Posp´ıˇsilová, A., Myˇsa´ková, E., and Lepˇs, M. (2013). Multiobjective Adaptive DoE for RBDO. In Proceedings of the 11th International Probabilistic Workshop, pages 325–336. Ing. Vladislav Pokorn´ y - LITERA, Brno. [Prescott, 2008] Prescott, P. (2008). Nearly uniform designs for mixture experiments. Communications in Statistics - Theory and Methods, 37(13):2095–2115. [Pronzato and M¨ uller, 2012] Pronzato, L. and M¨ uller, W. G. (2012). Design of computer experiments: space filling and beyond. Statistics and Computing, 22(3):681–701. [Pronzato and Walter, 1988] Pronzato, L. and Walter, E. (1988). Robust experiment design via maximin optimization. Mathematical Biosciences, 89(2):161 – 176. [Rechenberg, 1973] Rechenberg, I. (1973). Evolution strategy: Optimization of technical systems by means of biological evolution. Fromman-Holzboog, Stuttgart. [Sacks et al., 1989] Sacks, J., Welch, W., Mitchell, T., and Wynn, H. (1989). Design and analysis of computer experiments. Statistical Science, 4(4):409–435. [Sanches, 2005] Sanches, S. M. (2005). Nolhdesigns spreadsheet. Available online via http://diana.cs.nps.navy.mil/SeedLab/LinkedFiles/NOLHdesigns v4.xls. [Schuster, 2008] Schuster, M. (2008). The largest empty circle problem. In Proceedings of the Class of 2008 Senior Conference, Computer Science Department, Swarthmore College, pages 28–37. [Simon, 2003] Simon, M. J. (2003). Concrete mixture optimization using statistical methods: final report. U.S. Dept. of Transportation, Federal Highway Administration, Research, Development and Technology, Turner-Fairbank Highway Research Center.

55

LITERATURA

[Simon et al., 1997] Simon, M. J., Lagergreen, E. S., and Snyder, K. A. (1997). Concrete Mixture Optimization Using Statistical Mixture Design Methods. In Proc. of the PCI/FHWA, New Orleans, Lousiana, pages 230 – 244. [Snee, 1979] Snee, R. D. (1979). Experimental designs for mixture systems with multicomponent constraints. Communications in Statistics - Theory and Methods, 8(4):303–326. [Toropov et al., 2007] Toropov, V. V., Bates, S. J., and Querin, O. M. (2007). Generation of extended uniform latin hypercube designs of experiments. In Topping, B. H. V., editor, Proceedings of the Ninth International Conference on the Application of Artificial Intelligence to Civil, Structural and Environmental Engineering. Civil-Comp Press, Stirlingshire, UK. [Toussaint, 1983] Toussaint, G. (1983). Computing largest empty circles with location constraints. International Journal of Computer & Information Sciences, 12:347–358. [van Dam, 2005] van Dam, E. R. (2005). Two-dimensional minimax latin hypercube designs. Discussion Paper 2005-105, Tilburg University, Center for Economic Research. [Wynn and Wiggins, 1997] Wynn, C. and Wiggins, A. (1997). The five biggest ideas in science. Barnes & Noble Books.

56

Pˇ r´ıloha A Pˇ rehled prvk˚ u (0-5)-dimenzion´ aln´ıho simplexu a hyperkrychle dimenze 0 1 2 3 4 5

n´ azev Bod ´ Useˇcka Troj´ uheln´ık ˇ Ctyˇrstˇen Tetrahedron 4-simplex 5-simplex

vrcholy hrany stˇ eny 1 2 1 3 3 1

buˇ nky 4-facety 5-facety

4

6

4

1

5 6

10 15

10 20

5 15

1 6

1

Tabulka A.1: Pˇrehled prvk˚ u simplexu pro 0-5 dimenz´ı.

dimenze 0 1 2 3 4 5

n´ azev vrcholy hrany stˇ eny Bod 1 ´ Useˇcka 2 1 ˇ Ctverec 4 4 1 Tetragon Krychle 8 12 6 Hexahedron Teserakt 16 32 24 Octachoron Penterakt 32 80 80 Decateron

buˇ nky 4-facety 5-facety

1 8

1

40

10

1

Tabulka A.2: Pˇrehled prvk˚ u hyperkrychle pro 0-5 dimenz´ı. V Tabulkách A.1 a A.2 uvád´ıme pˇrehled prvk˚ u simplex˚ u a hyperkrychl´ı do pˇeti dimenz´ı. V´ıce informac´ı na [Sim, 2002, Hyp, 2002].

57

Pˇ r´ıloha B Algoritmus pro v´ ypoˇ cet hodnoty EM M V této pˇr´ıloze uvád´ıme algoritmus pro v´ ypoˇcet nejkratˇs´ı vzájemné vzdálenosti mezi body návrhu. D´ıky vhodné indexaci (promˇenné I a J) je vyˇc´ıslen´ı moˇzné za pomoci jediného for-cyklu. Algoritmus je souˇcást´ı funkce lhsdesign statistického toolboxu programu MATLAB. 1

function s=metrika_EMM_N(x)

2 3 4 5 6 7 8 9 10 11

[m,p] = size(x); pp = (m-1):-1:2; I = zeros(m*(m-1)/2,1); I(cumsum([1 pp])) = 1; I = cumsum(I); J = ones(m*(m-1)/2,1); J(cumsum(pp)+1) = 2-pp; J(1)=2; J = cumsum(J);

12 13

d = zeros(size(I));

14 15 16 17

for j=1:p d = d + (x(I,j)-x(J,j)).^2; end

18 19

s = sqrt(min(d));

58

Pˇ r´ıloha C Delaunayova triangulace

(a) N´ ahodn´ a triangulace.

(b) Delaunayova triangulace.

Obrázek C.1: Triangulace sady bod˚ u ve 2D. Legenda: modré body - sada návrhov´ ych bod˚ u; modré troj´ uheln´ıky - triangulace; ˇcervené kruˇznice - kruˇznice opsané jednotliv´ ym troj´ uheln´ık˚ um triangulace. Triangulac´ı chápeme rozdˇelen´ı ˇcásti roviny dané sadou bod˚ u na troj´ uheln´ıky. Samotn´ y pojem je vhodn´ y pro 2D, princip je vˇsak pouˇziteln´ y v n-dimenzionáln´ım prostoru: takov´ y prostor poté rozdˇelujeme na n-dimenzionáln´ı simplexy (troj´ uheln´ık je 2-dimenzionáln´ı simplex). Pro danou sadu bod˚ u existuje velké mnoˇzstv´ı takov´ ych ˇreˇsen´ı. Obrázek C.1 ukazuje dvˇe moˇznosti. Delaunayova triangulace (DT) [Devadoss and O’Rourke, 2011] je d˚ uleˇzit´ ym a ˇcasto pouˇz´ıvan´ ym typem triangulace. Mezi jej´ı vlastnosti patˇr´ı, ˇze kruˇznice opsaná kaˇzdému z troj´ uheln´ık˚ u triangulace (v nD: hyperkoule opsaná kaˇzdému ze simplex˚ u) tvoˇrenému tˇremi body (v nD: n + 1 body) ze zadané sady neobsahuje ˇzádn´ y dalˇs´ı z tˇechto bod˚ u. To je patrné na srovnán´ı Obrázk˚ u C.1a a C.1b. Delaunayova triangulace maximalizuje minimáln´ı u ´hel v jednotliv´ ych troj´ uheln´ıc´ıch pro zabránˇen´ı vzniku u ´zk´ ych troj´ uheln´ık˚ u. Dalˇs´ı ze znám´ ych vlastnost´ı Delaunayovy triangulace je jej´ı dualita s Voronoiovým diagramem (VD) [Joe and Wang, 1993]. Voronoi˚ uv diagram rozdˇeluje rovinu se zadanou sadou bod˚ u na oblasti (Voronoiovy buˇ nky) podle toho, ke kterému ze zadan´ ych bod˚ u maj´ı body roviny nejbl´ıˇze. Jin´ ymi slovy, máme-li zadánu sadu bod˚ u P = {p1 , ..., pi , ..., pn }, Voronoiova buˇ nka V Ci je mnoˇzina bod˚ u v rovinˇe takov´ ych, ˇze jejich vzdálenost k za59

ˇ ÍLOHA C. DELAUNAYOVA TRIANGULACE PR

danému bodu pi je menˇs´ı neˇz ke vˇsem ostatn´ım zadan´ ym bod˚ um pj , j 6= i. To je ukázáno na Obrázku C.2. Jednotlivé Voronoiovy buˇ nky se st´ ykaj´ı v hranách a vrcholech. Právˇe tyto Voronoiovy vrcholy odpov´ıdaj´ı stˇred˚ um opsan´ ych kruˇznic jednotliv´ ych troj´ uheln´ık˚ u Delaunayovy triangulace.

Obrázek C.2: Dualita Delaunayovy triangulace a Voronoiova diagramu. Legenda: modré body - sada návrhov´ ych bod˚ u; modré troj´ uheln´ıky - triangulace; ˇcerné u ´seˇcky - Voronoi˚ uv diagram (Voronoiovy hrany); ˇcerné body - Voronoiovy vrcholy; zelená oblast - Voronoiova buˇ nka odpov´ıdaj´ıc´ı zelenému návrhovému bodu; ˇcervená kruˇznice - kruˇznice opsaná jednomu z troj´ uheln´ık˚ u triangulace.

60

Pˇ r´ıloha D Ploˇ sn´ e souˇ radnice

C [xC, yC] A=AABC

a

b A1=APBC A =A 2 PCA

l1 = AP BC /A l2 = AP CA /A l3 = AP AB /A xP = l1 xA + l2 xB + l3 xC yP = l1 yA + l2 yB + l3 yC

P [l , l , l ] 1 2 3

A =A 3

A [x , y ] A

A

PAB

c

B [xB, yB] Obrázek D.1: Ploˇsné souˇradnice.

Ploˇsné (troj´ uheln´ıkové, barycentrické) souˇradnice poprvé pˇredstavil August Ferdinand Möbius (1790 - 1816) ve své knize The Barycentric Calculus [Fauvel et al., 1993]. Máme-li dan´ y troj´ uheln´ık ABC, ploˇsné souˇradnice libovolného bodu P jsou dány pomˇerem plochy troj´ uheln´ıku tvoˇreného bodem P a jednotliv´ ymi stranami troj´ uheln´ıku ABC a plochy samotného troj´ uheln´ıku ABC (Obrázek D.1). Ploˇsné souˇradnice tak odpov´ıdaj´ı souˇradnic´ım v trojosé soustavˇe (Obrázek D.2 vlevo). Transformace mezi kartézsk´ ymi souˇradnicemi a ploˇsn´ ymi souˇradnice je dána rovnic´ı:      1 1 1  l1   1  xp =  xA xB xC  l2 (D.1)     yp yA yB yC l3 Souˇcet ploˇsn´ ych souˇradnic bodu je vˇzdy roven jedné (viz Obrázek D.2 vpravo s pˇr´ıklady bod˚ u a jejich ploˇsn´ ych souˇradnic). Bod leˇz´ıc´ı mimo dan´ y troj´ uheln´ık má nˇekteré (jednu 61

ˇ ÍLOHA D. PLOSN ˇ E ´ SOURADNICE ˇ PR (0,0,1)

x3

0.8

0.6 (1/4,1/4,1/2)

(1/2,0,1/2) 0.2 0.4 0.6

0.2 0.4

(1/3,1/3,1/3)

0.4 0.2

(0,1/2,1/2)

0.6

0.8

(1/2,1/4,1/4)

(1/4,1/2,1/4)

0.8

x1

x2

(1,0,0)

(1/2,1/2,0)

(0,1,0)

(a) y souˇradnicový systém (vlevo) a ploˇsné souˇ (b) Obrázek D.2: Trojos´ radnice (vpravo). nebo dvˇe) ploˇsné souˇradnice záporné. Toho lze vyuˇz´ıt právˇe pro urˇcen´ı, zda bod leˇz´ı uvnitˇr nebo vnˇe zadaného troj´ uheln´ıku nebo obecnˇe simplexu (pˇri rozˇs´ıˇren´ı do nD). Dále, máme-li ztriangulovan´ y návrhov´ y prostor a bod, u nˇehoˇz chceme zjistit, zda leˇz´ı uvnitˇr nebo vnˇe této domény, m˚ uˇzeme spoˇc´ıst ploˇsné souˇradnice ke vˇsem simplex˚ um triangulace a rozhodnout: bod leˇz´ı uvnitˇr návrhové domény, pokud v triangulaci existuje simplex takov´ y, ˇze ploˇsné souˇradnice k nˇemu vztaˇzené jsou vˇsechny kladné (Obrázek D.3).

[-0.4.1.0.4] [0.3,-0.5,1.2] [-0.2,1.4,-0.2]

[0.2,0.2,0.6]

[0.6,1.5,-1.1]

[1.2,-0.6,0.4] [0.7,1,-0.7]

[-1.7,1.2,1.5]

ˇ Obrázek D.3: Urˇcen´ı polohy bodu pomoc´ı ploˇsn´ ych souˇradnic. Cerven´ y bod leˇz´ı uvnitˇr návrhového prostoru, nebot’ je v triangulaci troj´ uheln´ık, vzhledem ke kterému má ˇreˇsen´ y bod vˇsechny ploˇsné souˇradnice kladné (obrázek vlevo). Zelen´ y bod leˇz´ı mimo doménu, nebot’ jeho ploˇsné souˇradnice ke vˇsem troj´ uheln´ık˚ um triangulace obsahuj´ı záporná ˇc´ısla (obrázek vpravo).

62

Pˇ r´ıloha E V´ ypoˇ cet hodnoty krit´ eria miniMax v regul´ arn´ım prostoru7

Obrázek E.1: miniMax I. Legenda: ˇcerné body - návrhové body; ˇcerné u ´seˇcky - Voronoi˚ uv diagram; ˇcervené body - vrcholy Voronoiova diagramu; zelené body - pr˚ useˇc´ıky hran Voronoiova diagramu s hranicemi ˇreˇsené domény; modré body - vrcholy domény; ˇcervené, zelené a modré kruˇznice - nejvˇetˇs´ı prázdné kruhy se stˇredy v ˇcerven´ ych, zelen´ ych a modr´ ych bodech; purpurová kruˇznice - nejvˇetˇs´ı prázdn´ y kruh; purpurov´ y bod - stˇred nejvˇetˇs´ıho prázdného kruhu. Obrázky slouˇz´ı pro ilustraci pr˚ ubˇehu metody, popisky os jsou proto vynechány.

E.1

Pˇ resn´ eˇ reˇ sen´ı

Pˇresnou hodnotu kritéria miniMax lze z´ıskat pomoc´ı Voronoiova diagramu. Stˇred nejvˇetˇs´ı prázdné koule (jej´ıˇz polomˇer odpov´ıdá hodnotˇe mM ) leˇz´ı v nˇekterém z vrchol˚ u Voronoiova diagramu, nebo pr˚ uniku hrany Voronoiova diagramu s hranic´ı ˇreˇsené domény. Ve 2D je vˇsechny tyto kandidátn´ı body moˇzné naj´ıt ruˇcnˇe“. Jsou to vrcholy Voro” noiova diagramu, pr˚ useˇc´ıky hran Voronoiova diagramu se ˇctyˇrmi stranami ˇreˇsené domény (ve 2D ˇctverce) a ˇctyˇri vrcholy ˇreˇsené domény [Schuster, 2008, Toussaint, 1983]. Zde tuto metodu oznaˇcujeme jako miniMax I a jej´ı pr˚ ubˇeh je znázornˇen na Obrázku E.1. Ve vyˇsˇs´ıch 7ˇ

C´ ast této kapitoly byla publikována v [Myˇsáková and Lepˇs, 2013a] a v [Myˇsáková, 2013].

63

ˇ ÍLOHA E. VYPO ´ ˇ ´ ´ ÍM PR CET HODNOTY KRITERIA MINIMAX V REGULARN PROSTORU

Obrázek E.2: miniMax II. Legenda: velké ˇcerné body - návrhové body; malé ˇcerné body ozrcadlené návrhové body; ˇcerné u ´seˇcky - Voronoi˚ uv diagram; ˇcervené body - vrcholy Voronoiova diagramu leˇz´ıc´ı uvnitˇr nebo na hranici ˇreˇsené domény; ˇcervené kruˇznice - nejvˇetˇs´ı prázdné kruhy se stˇredy v ˇcerven´ ych bodech; purpurová kruˇznice - nejvˇetˇs´ı prázdn´ y kruh; purpurov´ y bod - stˇred nejvˇetˇs´ıho prázdného kruhu.

dimenz´ıch je vˇsak pouˇzit´ı této metody obt´ıˇznˇejˇs´ı. Nalezen´ı vˇsech pr˚ unik˚ u Voronoiova diagramu s hraniˇcn´ımi objekty ˇreˇsené domény nen´ı triviáln´ı a je nutné vz´ıt v u ´vahu i vˇsechny vrcholy ˇreˇsené hyperkrychle. V ˇclánku [Pronzato and M¨ uller, 2012] je popsána jiná metoda pro nalezen´ı pˇresného ˇreˇsen´ı. Návrhové body jsou zrcadleny skrz vˇsechny (n − 1)-facety (kde n znaˇc´ı poˇcet dimenz´ı prostoru) a aˇz následnˇe je sestrojen Voronoi˚ uv diagram. Kandidátn´ımi body jsou pak ty vrcholy Voronoiova diagramu leˇz´ıc´ı uvnitˇr nebo na hranici ˇreˇsené domény. Tuto metodu ilustruje Obrázek E.2 a oznaˇcujeme ji jako miniMax II. Zrcadlen´ı zaruˇcuje, ˇze i body na hranici a ve vrcholech domény budou uvedeny mezi kandidátn´ımi body. I tato metoda vˇsak má své limity. Sestrojen´ı Voronoiova diagramu je ve vyˇsˇs´ıch dimenz´ıch velice nároˇcné (ˇcasovˇe i pamˇetovˇe) a zrcadlen´ı (kaˇzd´ y bod mus´ı b´ yt ozrcadlen (2n)-krát) tyto nároky jeˇstˇe zvyˇsuje. To dokumentuje i Tabulka E.1 - v niˇzˇs´ıch dimenz´ıch jsou exaktn´ı metody efektivnˇejˇs´ı, ve vyˇsˇs´ıch dimenz´ıch ale jejich pamˇet’ové nároky v´ yraznˇe rostou. Problémy, se kter´ ymi se setkáváme v inˇzen´ yrské praxi, jsou vˇsak zpravidla multidimenzionáln´ı, proto potˇrebujeme metody schopné pracovat i v takov´ ych návrhov´ ych prostorech.

E.2

S´ eriov´ a evoluˇ cn´ı strategie

Jednou z moˇznost´ı je odhadnout hodnotu miniMax pomoc´ı heuristické nebo metaheuristické metody. My jsme zvolili evoluˇcn´ı strategii (ES). Jedná se o metodu zaloˇzenou na principech znám´ ych z pˇr´ırody - pˇrizp˚ usobován´ı (adaptation), mutace (mutation), kˇr´ıˇzen´ı (crossover) a v´ ybˇer (selection). Tato technika byla vyvinuta v 60. a 70. letech 20. stolet´ı Rechenbergem, Schwefelem a jejich spolupracovn´ıky, v´ıce informac´ı v [Rechenberg, 1973] nebo [Bäck and Schwefel, 1995]. Základem procedury je cyklus, jehoˇz iterace jsou naz´ yvány generace. Kaˇzdá generace obsahuje populaci sloˇzenou z jednotliv´ ych chromosom˚ u - bod˚ u, které pokr´ yvaj´ı ˇreˇsenou doménu. C´ılová funkce je pak vyhodnocena pro kaˇzd´ y chromosom (s parametry odpov´ıdaj´ıc´ımi souˇradnic´ım chromosomu). Nová populace ( potomci“) je odvozena ” z pˇredchoz´ı populace ( rodiˇce“) pomoc´ı mutace a kˇr´ıˇzen´ı. Rozliˇsuj´ı se dva typy: v (µ, λ)” 64


Obrázek E.3: Sériová evoluˇcn´ı strategie. Legenda: ˇcerné body - návrhové body; ˇcervené body - rodiˇce“; modré body - potomci“; purpurov´ y bod - stˇred nejvˇetˇs´ıho prázdného ” ” kruhu; purpurová kruˇznice - nejvˇetˇs´ı prázdn´ y kruh.

ES je nová generace odvozena z potomk˚ u z pˇredchoz´ı generace, v (µ + λ)-ES ze sjednocen´ı rodiˇc˚ u a potomk˚ u z pˇredchoz´ı generace. Poˇcet generac´ı m˚ uˇze b´ yt stanoven uˇzivatelem pevnˇe, nebo je pro algoritmus urˇceno zastavovac´ı kritérium. (µ+λ)-evoluˇcn´ı strategie pouˇzitá zde je inspirována ˇclánkem [Lee et al., 2004]. Nejprve je vytvoˇrena v´ ychoz´ı populace. Ta by mˇela rovnomˇernˇe pokr´ yvat cel´ y prostor, proto je vytvoˇrena pomoc´ı LHS (latin hypercube sampling). Jelikoˇz se zde zamˇeˇrujeme na porovnán´ı ˇcasové nároˇcnosti vlastn´ıho cyklu evoluˇcn´ı strategie (sériové vs. paraleln´ı), je poˇca´teˇcn´ı populace vytvoˇrena pomoc´ı funkce lhsdesign ze statistického toolboxu programu MATLAB ve v´ ychoz´ım nastaven´ı tak, aby nebyl celkov´ y ˇcas t´ımto procesem v´ yraznˇe ovlivnˇen. Potomci jsou odvozováni pomoc´ı mutace - pˇriˇcten´ım normálnˇe rozdˇelen´ ych (pr˚ umˇer roven nule, standardn´ı odchylka klesaj´ıc´ı s poˇrad´ım cyklu) náhodn´ ych ˇc´ısel k rodiˇcovské populaci. Následnˇe jsou ze sjednocen´ı rodiˇcovské populace a potomk˚ u vytvoˇreny náhodné páry a z kaˇzdého tohoto páru je do nové rodiˇcovské populace vybrán ten chromosom, kter´ y má delˇs´ı vzdálenost k nejbliˇzˇs´ımu návrhovému bodu. Toto v´ ybˇerové schéma upˇrednostˇ nuje lepˇs´ı jednotlivce k postupu do dalˇs´ı generace. Metoda je znázornˇena na Obrázku E.3. Je na nˇem patrné, jak se populace pˇribliˇzuje k hledanému ˇreˇsen´ı. Metoda je robustn´ı a uˇzivatel m˚ uˇze volit velikost populace i poˇcet generac´ı podle dimenze ˇreˇseného problému. Pˇresto je ve vyˇsˇs´ıch dimenz´ıch obt´ıˇzné prozkoumat celou ˇreˇsenou doménu. To by mˇela zajistit dále popsaná paraleln´ı metoda.

65


dělená

dělená

nedělená

dělená

nedělená

dělená

dělená

dělená

nedělená

Obrázek E.4: Paraleln´ı evoluˇcn´ı strategie - zp˚ usoby dˇelen´ı na subdomény ve 3D s k = 5, kde k je poˇcet interval˚ u na dˇelené hranˇe domény.

E.3

Paraleln´ı evoluˇ cn´ı strategie

Paralelizovat evoluˇcn´ı strategii lze dvˇema zp˚ usoby: za prvé, m˚ uˇze prob´ıhat nˇekolikeré hledán´ı v celé doménˇe paralelnˇe nezávisle na sobˇe; za druhé, ˇreˇsenou doménu m˚ uˇzeme rozdˇelit na menˇs´ı celky - subdomény - a hledán´ı pomoc´ı ES pak prob´ıhá paralelnˇe v tˇechto subdoménách. Zde je zvolena druhá z moˇznost´ı. Doménu lze dˇelit nˇekolika zp˚ usoby, jak ukazuje Obrázek E.4. Prvn´ı z uveden´ ych variant je pravdˇepodobnˇe nejvhodnˇejˇs´ı k zaruˇcen´ı prohledán´ı celého prostoru. Poˇcet vznikl´ ych subdomén je potom k n , kde k oznaˇcuje poˇcet interval˚ u na dˇelené hranˇe domény. Mnoˇzstv´ı subdomén tedy roste velice rychle s dimenz´ı ˇreˇsené domény a v pˇr´ıpadˇe vyˇsˇs´ıch domén je tedy nutné pouˇz´ıt nˇekterou z dalˇs´ıch alternativ dˇelen´ı. Zde je pouˇzita prvn´ı varianta dˇelen´ı na subdomény s k = 2. Poˇcet chromosom˚ u v populaci je zvolen 10n. Popsanou metodu znázorˇ nuje Obrázek E.5. Nˇekolik subdomén je tedy ˇreˇseno zároveˇ n paralelnˇe na jednotliv´ ych CPU. Z kaˇzdé subdomény obdrˇz´ıme kandidátn´ı ˇreˇsen´ı/bod (Obrázek E.6), jako stˇred nejvˇetˇs´ı prázdné koule (jej´ı polomˇer je pak hodnota mM ) je z tˇechto bod˚ u oznaˇcen ten, kter´ y má nejdelˇs´ı vzdálenost k bod˚ um návrhu.

Obrázek E.5: Paraleln´ı evoluˇcn´ı strategie ve 2D s k = 3. Legenda: ˇcerné body - návrhové body; ˇcervené body - rodiˇce“; modré body - potomci“; b´ılé body - v kaˇzdé subdoménˇe ” ” bod nejv´ıce vzdálen´ y od návrhov´ ych bod˚ u; purpurov´ y bod - stˇred nejvˇetˇs´ıho prázdného kruhu; purpurová kruˇznice - nejvˇetˇs´ı prázdn´ y kruh.

66


1

0.8

x2

0.6

0.4

0.2

0

0.2

0.4

0.6

0.8

1

x1

Obrázek E.6: Paraleln´ı evoluˇcn´ı strategie. Legenda: ˇcerné body - návrhové body; b´ılé body - v kaˇzdé subdoménˇe bod nejv´ıce vzdálen´ y od návrhov´ ych bod˚ u; teˇckované kruˇznice - nejvˇetˇs´ı prázdné kruhy se stˇredy v b´ıl´ ych bodech; purpurov´ y bod - stˇred nejvˇetˇs´ıho prázdného kruhu; purpurová kruˇznice - nejvˇetˇs´ı prázdn´ y kruh.

E.4

Porovn´ an´ı a shrnut´ı

K porovnán´ı pˇredstaven´ ych metod byly pouˇzity tˇri typové pˇr´ıklady: (i) 2D návrh s 27 body pˇrevzat´ y z [van Dam, 2005], (ii) 6D návrh se 17 body a (iii) 12D návrh s 65 body. Tvorba uveden´ ych 6D a 12D návrh˚ u je popsána v [Cioppa and Lucas, 2007] a v´ ysledné návrhy byly staˇzeny ze [Sanches, 2005]. Nejprve byly jednotlivé metody porovnány z pohledu v´ ypoˇcetn´ıch nárok˚ u. Ty jsou uvedeny v Tabulce E.1. Jedná se o pr˚ umˇerné hodnoty z 10 nezávisl´ ych spuˇstˇen´ı kaˇzdé procedury. Je zˇrejmé, ˇze v n´ızk´ ych dimenz´ıch jasnˇe v´ıtˇez´ı metody poskytuj´ıc´ı pˇresné ˇreˇsen´ı (oznaˇceny miniMax I a miniMax II). Jiˇz v 12D pˇr´ıkladu ovˇsem nestaˇc´ı operaˇcn´ı pamˇet’ kv˚ uli extrémn´ı nároˇcnosti sestrojen´ı Voronoiova diagramu. Sériová verze evoluˇcn´ı strategie je pˇri zvolené velikosti populace a poˇctu generac´ı v´ıce neˇz 20krát pomalejˇs´ı neˇz exaktn´ı metody. Efektivita paraleln´ı verze je pak ve 2D pˇr´ıpadˇe nulová. Komunikace v poˇc´ıtaˇci nutná k rozdˇelen´ı problému na jednotlivé subdomény zde ˇcasovˇe vysoce pˇrevyˇsuje samotn´ y 2D metoda miniMax I miniMax II ES miniMax - sériová ES miniMax - paraleln´ı - 2 CPU ES miniMax - paraleln´ı - 4 CPU ES miniMax - paraleln´ı - 8 CPU

6D

12D ˇ cas [s]

0,007 0,004 0,183 7,338 7,489 7,935

– – 2,265 - (vyˇcerpáno 12 GB RAM) 47,193 2489,557 36,634 1455,274 22,617 756,122 15,774 404,693

ˇ Tabulka E.1: Casov´ a nároˇcnost metod vyˇc´ıslen´ı kritéria miniMax.

67


8

8

7

7

6

6 Speed-up

Speed-up

6D, 17 bodů - 60 chromosomů, 12800 generací, 64 12D, subdomén 65 bodů - 120 chromosomů, 204800 generací, 4096 subdomén

5 4

5 4

3

3

2

2

1

1

1

2

3

4 5 6 Počet CPU

7

8

1

2

3

4 5 6 Počet CPU

7

8

Obrázek E.7: Speed-up paraleln´ı ES pro v´ ypoˇcet hodnoty miniMax: 6D, 17 bod˚ u - 60 chromosom˚ u, 12800 generac´ı, 64 subdomén (vlevo) a 12D, 65 bod˚ u - 120 chromosom˚ u, 204800 generac´ı, 4096 subdomén (vpravo).

v´ ypoˇcet a celkov´ y potˇrebn´ y ˇcas tu dokonce roste s poˇctem pouˇzit´ ych CPU. Zaj´ımavˇejˇs´ı je vˇsak situace ve vyˇsˇs´ıch dimenz´ıch. Obrázek E.7 ukazuje speed-up (závislost zrychlen´ı v´ ypoˇctu na poˇctu vyuˇzit´ ych CPU) pro 6D a 12D problémy. Se zvyˇsuj´ıc´ı se dimenz´ı se ˇcas potˇrebn´ y ke komunikaci mezi jednotliv´ ymi CPU stává zanedbateln´ ym a paraleln´ı metoda zde dosahuje témˇeˇr lineárn´ıho speed-upu. Nyn´ı metody porovnáme z pohledu kvality z´ıskaného ˇreˇsen´ı - hodnoty kritéria miniMax. Pˇripomeˇ nme, ˇze evoluˇcn´ı strategie je stochastick´ y algoritmus s náhodn´ ym chován´ım a hodnota j´ı z´ıskaná je tedy pouze odhadem - pˇresná hodnota m˚ uˇze b´ yt vyˇsˇs´ı. V niˇzˇs´ıch 12D, 65 bodů - 120 chromosomů, 204800 generací, 4096 subdomén 1.57 1.56

mM

1.55 1.54 1.53 1.52 1.51 sériová ES

paralelní ES

Obrázek E.8: Boxplot hodnot mM z´ıskan´ ych uveden´ ymi metodami pro problém ve 12D.

68


12D, 65 bodů - 120 chromosomů, 204800 generací, 4096 subdomén 1.6 1.55 1.5

mM

1.45 1.4 1.35 1.3 1.25 -1

10

0

10

1

10 čas [s]

2

10

3

10

Obrázek E.9: V´ yvoj hodnoty mM v pr˚ ubˇehu v´ ypoˇctu pro 10 spuˇstˇen´ı ES. Legenda: modré kˇrivky - sériová verze; ˇcervené kˇrivky - paraleln´ı verze (8 CPU).

dimenz´ıch, tedy ve 2D a 6D pˇr´ıkladu poskytuj´ı naˇse metody zaloˇzené na ES (sériová a paraleln´ı) pˇresné ˇreˇsen´ı pˇri vˇsech 10 spuˇstˇen´ıch. Pro 12D problém pˇresnou hodnotu mM neznáme. Obrázek E.8 ukazuje boxplot hodnot kritéria miniMax z´ıskan´ ych pomoc´ı obou verz´ı evoluˇcn´ı strategie. Sériová verze je nˇekdy schopná nalézt pˇresnˇejˇs´ı ˇreˇsen´ı (vyˇsˇs´ı hodnotu odhadu mM ), vykazuje vˇsak vyˇsˇs´ı rozptyl v porovnán´ı s verz´ı paraleln´ı ˇreˇs´ıc´ı problém v jednotliv´ ych subdoménách. Poznamenejme, ˇze celkov´ y poˇcet proveden´ ych iterac´ı a v´ ypoˇct˚ u vzdálenost´ı byl shodn´ y pro sériovou verzi i pro verzi paraleln´ı (souˇcet poˇct˚ u generac´ı v jednotliv´ ych subdoménách je shodn´ y s poˇctem generac´ı v sériové verzi). Srovnán´ı metod z hlediska reálného ˇcasu ukazuje Obrázek E.9. Sériová verze ES se zdá b´ yt velmi rychlá z pohledu nalezen´ı kvalitn´ıho ˇreˇsen´ı. V´ ysledek je vˇsak ze znaˇcné ˇcásti dán ˇstˇest´ım“ v zasaˇzen´ı oblasti stˇredu nejvˇetˇs´ı prázdné koule (ten se velmi ˇcasto nacház´ı na ” hranici ˇreˇsené domény). Paraleln´ı verze ztrác´ı urˇcit´ y ˇcas na zaˇcátku v´ ypoˇctu rozdˇelen´ım prostoru na subdomény a komunikac´ı nutnou k paralelizaci. Poté vˇsak paraleln´ı verze poskytuje robustnˇejˇs´ı ˇreˇsen´ı s menˇs´ım rozptylem. Byly pˇredstaveny dvˇe tradiˇcn´ı metody poskytuj´ıc´ı pˇresné ˇreˇsen´ı miniMax kritéria spoleˇcnˇe s algoritmem evoluˇcn´ı strategie v sériové a paraleln´ı verzi. Ten poskytuje odhad hodnoty kritéria. Naˇse v´ ysledky ukazuj´ı, ˇze v niˇzˇs´ıch dimenz´ıch navrˇzené metody zaloˇzené na ES pˇresné ˇreˇsen´ı naleznou. Ve vyˇsˇs´ıch dimenz´ıch pak bez problém˚ u s nedostatkem operaˇcn´ı pamˇeti (typické pro exaktn´ı metody vyuˇz´ıvaj´ıc´ı Voronoi˚ uv diagram) poskytuj´ı odhad hodnoty mM . Paraleln´ı verze pˇredstavuje zp˚ usob rozparcelován´ı“, tedy ” rozdˇelen´ı celé ˇreˇsené domény na menˇs´ı subdomény. Tato verze dosahuje ve vyˇsˇs´ıch dimenz´ıch témˇeˇr lineárn´ıho speed-upu a odhady j´ı z´ıskané maj´ı menˇs´ı rozptyl v porovnán´ı se sériovou verz´ı (kde je ˇreˇsena celá doména najednou).

69

Pˇ r´ıloha F Ruˇ cn´ı v´ ypoˇ cet hled´ an´ı vrchol˚ u polytopu pomoc´ı LP

c cB

ti

T

A

b

(z - c) T

L

Obrázek F.1: Simplexová tabulka obecnˇe. Základem simplexové tabulky je rozˇs´ıˇrená maˇ adek cT obsahuje cenové koeficienty, sloupec ti oznaˇcuje poˇrad´ı tice soustavy (A|b). R´ sloupc˚ u matice A, které tvoˇr´ı bázi a sloupec cB cenové koeficienty odpov´ıdaj´ıc´ı tˇemto sloupc˚ um. V ˇra´dku (z − c)T najdeme relativn´ı ceny a v poli L aktuáln´ı hodnotu u ´ˇcelové funkce. Simplexové tabulky uvedené na Obrázc´ıch F.2, F.3, F.4 a F.5 znázorˇ nuj´ı ˇreˇsen´ı u ´lohy hledán´ı krajn´ıch bod˚ u mnoˇziny pˇr´ıpustn´ ych ˇreˇsen´ı pomoc´ı simplexové metody lineárn´ıho programován´ı [Demel, 2011]. Uspoˇra´dán´ı tabulek odpov´ıdá obecnému schématu uvedenému na Obrázku F.1. Neznámé x1 , x2 , x3 odpov´ıdaj´ı hledan´ ym neznám´ ych ze zadán´ı u ´lohy, neznámé x4 - x11 jsou tzv. doplˇ nkové a neznámé x12 - x16 naz´ yváme umˇelé. Cenové koeficienty (odpov´ıdaj´ıc´ı normále u ´ˇcelové funkce) byly zvoleny rovny 1, coˇz onu u ´ˇcelovou funkci ˇcin´ı nepodstatnou a nen´ı tak preferován ˇza´dn´ y smˇer hledán´ı krajn´ıch bod˚ u. Je tak zaruˇceno, ˇze budou nalezeny vˇsechny, a to moˇzn´ ymi kombinacemi sloupc˚ u matice A v bázi (sloupce v bázi jsou zv´ yraznˇeny r˚ uˇzov´ ym podbarven´ım). Touto metodou bylo nalezeno vˇsech ˇsest krajn´ıch bod˚ u mnoˇziny pˇr´ıpustn´ ych ˇreˇsen´ı, coˇz odpov´ıdá jak v´ ysledku z referenc´ı, tak v´ ysledku grafické metody.

70

2

71 3

-1E+06 -1E+06 0 -1E+06 0 0 -1E+06 0 1

-1E+06 -1E+06 0 -1E+06 0 0 -1E+06 0 1

12 13 5 14 7 8 15 10 16

12 13 5 14 7 8 15 10 3

12 13 5 14 7 11 15 10 3

2 1 1

3 1 1

4 0

5 0

1 1 0,3 1 1

-0,7 15 15 0,7 -1,6E+07 1 1 1 1 1

-0,7 85 85 0 -8,7E+07

7 0

8 0

9 0

10 0

-1

11 12 13 14 15 16 0 -1000000 -1000000 -1000000 -1000000 -1000000 1 1

1 1 1

85 85 0,7 -8,8E+07

6 0

-1

-9,2E+07

1 100 100 1 -1E+08

2 1 1

3 1 0

90 90

1 1 1 -1

1 1

1000000

0

1000000

0

0

1000000

0

4 0 0 -1

5 0 0

6 0 0

7 0 0

8 0 0

9 0 0

10 0 0

-1 1000000

0

0

0

0

1 0,1 0,5 0,1 0,7 0,7 90 95 1 0,4 0 -9E+07

11 12 13 14 15 16 0 -1000000 -1000000 -1000000 -1000000 -1000000 1 1 0 0 0 -1 1

1 1 1 0 90 90

-1

-9,2E+07

0 0 0 1 0

2 1 1

3 1 0

1

0 0 0

0 0 0

0 0 0

1 0 0 0

1000000

0

1000000

0

0

1000000

0

4 0 0 -1

5 0 0

6 0 0

7 0 0

8 0 -1

9 0 0

10 0 0

1 0 0

0 -1 0

0 0 1

1 100 100 -1 -1E+08

0 0 0

0 0 0

0 0 0

0

0

0

0 1 0

-1 -100 -100 1 0 1,02E+08

11 12 13 14 15 16 0 -1000000 -1000000 -1000000 -1000000 -1000000 0 1 0 0 0 0 1

1 1 1 0 90 90 0 -9,2E+07

-1 0 0 0 1 0

0 0 0 0 1000000

0 0 0 0 0

0 0 0 0 1000000

1 1 0 1 0 -100 0 -100 0 1 0 1,01E+08

0 -1 0 0 1000000

0 0 1 0 0

1 0 0 0 0

Obrázek F.2: Simplexové tabulky ˇc. 1-3.

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 1 0 0 0

-1 0 0 0 1000000

0,6 0,1 0,5 0,1 0,7 0,3 50 55 0,4 -5E+07

0,3 0,1 0,5 0,1 0,7 0,3 20 25 0,7 -2E+07

ˇ ÍLOHA F. RUCN ˇ Í VYPO ´ ˇ ´ Í VRCHOLU ˚ POLYTOPU POMOCÍ LP PR CET HLEDAN

1

-1E+06 -1E+06 0 -1E+06 0 0 -1E+06 0 -1E+06

1 1 1 1 1

5

72 6

12 13 5 2 7 11 15 10 3

-1E+06 12 1 1 0 5 1 2 0 7 0 8 0 6 0 10 1 3

-1E+06 12 1 1 0 5 1 2 0 7 0 8 0 6 0 10 1 3

2 1 0

3 1 0

4 0 0 -1

5 0 0

6 0 1

7 0 0

8 0 -1

9 0 0

10 0 0

1 0 0 1 0 -100 0 -100 0 1 0 1,01E+08

0 0 -1 0 0 1000000

0 0 0 1 0 0

1 1 0 0 0 0 0 0

0 0 0 0 1 0

0 0 0 0 0 1000000

0 0 0 0 0 0

-1 1 0 90 90 0 -9,1E+07

1 1 0 1 0 0 0 0 0 0 0 0

2 1 0

3 1 0

5 0 0

6 0 0

7 0 0

8 0 0,11

9 0 0,01

10 0 0

0 1 0 0 0 0 0 0

0 0 0 0 0 0 1 0

4 0 0,06 -1 1 0,94 -0,94 -0,7 0,94 0 0 -55555,6

1 0 0 0 0 0 0 0

0 0 0 0 1 0 0 0

0 0 1 0 0 0 0 0

0 -1,11 1,11 1 -1,11 1 -111111

0 -0,01 0,01 0 -0,01 1 0 -11111,1

0 0 0 0 0 1 0 0

1 1 0 1 0 0 0 0 0 0 0 0

2 1 0

3 1 0

5 0 0

6 0 0

7 0 0

8 0 0

9 0 0,01

10 0 0

0 1 0 0 0 0 0 0

0 0 0 0 0 0 1 0

4 0 0,13 -1 1 0,17 -0,17 -0,7 0,17 0 0,7 -133333

1 0 0 0 0 0 0 0

0 0 0 0 1 0 0 0

0 0 1 0 0 0 0 0

0 0 0 1 0 0 0 0

0 -0,01 0,01 0 -0,01 1 0 -11111,1

0 0 0 0 0 1 0 0

0 -0,7 85 85 0 -8,7E+07

11 12 13 14 15 16 0 -1000000 -1000000 -1000000 -1000000 -1000000 0 1 0 -1 0 0 1

0,00

0 1 0 0 0 0

0 0 0 0 0 0

1 0 -1 0 0 0 -90 0 -90 0 0 0 92000001

0 0 1 0 0 0

0 -1 0 0 0 1000000

0,2 0,1 0,5 0,1 0,6 0,3 11 16 0,7 -1E+07

11 12 13 14 15 16 0 -1000000 -1000000 -1000000 -1000000 -1000000 0 1 -0,06 0 -0,01 0 0,0722 1 0,1 0 0 -1 0 0 0 0,4 0 0 -0,94 0 0,01 0 0,1278 0 0 0,94 0 -0,01 0 0,5722 1 0 0,7 0 0 -1 0,37 0 0 -0,94 -1 0,01 0 0,0278 0 0 0 0 -1 0 5 0 0 0 0 0 0 0,7 0 0 1055556 1000000 1011111 1000000 -72221 11 12 13 14 15 16 0 -1000000 -1000000 -1000000 -1000000 -1000000 -0,11 1 -0,13 0 -0,01 0,11 1 0 0 -1 0 0 0 1,11 0 -0,17 0 0,01 -1,11 -1,11 0 0,17 0 -0,01 1,11 1 0 0,7 0 0 -1 1,11 0 -0,17 -1 0,01 -1,11 0 0 0 0 -1 0 -1 0 -0,7 0 0 1 111111,2 0 1133333 1000000 1011111 888888,8


0,0311 0,1 0,4 0,5389 0,1611 0,37 0,4389 5 0,33 -31110


4

-1E+06 -1E+06 0 1 0 0 -1E+06 0 1

1 1 1 1 1

2 1 0 0 0 1 0 0 0 0 0 0

3 1 0 0 0 0 0 0 0 0 1 0

4 0 1 0 0 0 0 0 0 0 0 0

5 0 0 0 1 0 0 0 0 0 0 0

6 0 0 0 0 0 0 0 1 0 0 0

7 0 0 0 0 0 1 0 0 0 0 0

8 0 0 0 0 0 0 1 0 0 0 0

9 0 0,08 0,08 -0,08 -0,02 0,02 0,06 -0,02 1 -0,06 0

10 0 0 0 0 0 0 0 0 1 0 0

11 12 13 14 15 16 0 -1000000 -1000000 -1000000 -1000000 -1000000 -0,83 7,5 -1 0 -0,08 0,83 -0,83 7,5 0 0 -0,08 0,83 0,83 -7,5 0 0 0,08 -0,83 1,25 -1,25 0 0 0,02 -1,25 -1,25 1,25 0 0 -0,02 1,25 0,42 5,25 0 0 -0,06 -0,42 1,25 -1,25 0 -1 0,02 -1,25 0 0 0 0 -1 0 -0,42 -5,25 0 0 0,06 0,42 0 1000001 1000000 1000000 1000000 1000000

0,2333 0,3333 0,1667 0,5 0,2 0,5333 0,4 5 0,1667 1

1 1 0 1 0 0 0 0 0 0 0 0

2 1 0 0 0 1 0 0 0 0 0 0

3 1 0 0 0 0 0 0 0 0 1 0

4 0 12 -1 1 0,3 -0,3 -0,7 0,3 -12 0,7 0

5 0 0 0 1 0 0 0 0 0 0 0

6 0 0 0 0 0 0 0 1 0 0 0

7 0 0 0 0 0 1 0 0 0 0 0

8 0 0 0 0 0 0 1 0 0 0 0

9 0 1 0 0 0 0 0 0 0 0 0

10 0 0 0 0 0 0 0 0 1 0 0

11 12 13 14 15 16 0 -1000000 -1000000 -1000000 -1000000 -1000000 -10 90 -12 0 -1 10 0 0 1 0 0 0 0 0 -1 0 0 0 1 1 -0,3 0 0 -1 -1 -1 0,3 0 0 1 1 0 0,7 0 0 -1 1 1 -0,3 -1 0 -1 10 -90 12 0 0 -10 -1 0 -0,7 0 0 1 0 1000001 1000000 1000000 1000000 1000000

2,8 0,1 0,4 0,57 0,13 0,37 0,47 2,2 0,33 1

1 1 0 1 0 0 0 0 0 0 0 0

2 1 0 0 0 1 0 0 0 0 0 0

3 1 0 0 0 0 0 0 0 0 1 0

4 0 0 -1 1 1,5 -1,5 0,5 1,5 -1,2 -0,5 0

5 0 0 0 1 0 0 0 0 0 0 0

6 0 0 0 0 0 0 0 1 0 0 0

7 0 0 0 0 0 1 0 0 0 0 0

8 0 0 0 0 0 0 1 0 0 0 0

9 0 1 0 0 0 0 0 0 0 0 0

10 0 1 0 0 -0,1 0,1 -0,1 -0,1 0,1 0,1 0

11 12 13 14 15 16 0 -1000000 -1000000 -1000000 -1000000 -1000000 0 0 0 0 -1 0 0 0 1 0 0 0 0 0 -1 0 0 0 0 10 -1,5 0 0 0 0 -10 1,5 0 0 0 0 9 -0,5 0 0 0 0 10 -1,5 -1 0 0 1 -9 1,2 0 0 -1 0 -9 0,5 0 0 0 0 1000001 1000000 1000000 1000000 1000000

5 0,1 0,4 0,35 0,35 0,15 0,25 0,22 0,55 1

x1 0,3333 x2 0,5 x3 0,1667

hledání dalších vrcholů (změnou báze):

8

73 9

0 9 1 1 0 5 1 2 0 7 0 8 0 6 0 10 1 3

0 9 1 1 0 5 1 2 0 7 0 8 0 6 0 11 1 3


x1 x2 x3

0,1 0,57 0,33

x1 x2 x3

0,1 0,35 0,55


7

0 4 1 1 0 5 1 2 0 7 0 8 0 6 0 10 1 3

1 1 0 1 0 0 0 0 0 0 0 0

11

74 12

0 9 1 1 0 10 1 2 0 7 0 8 0 4 0 11 1 3

0 6 1 1 0 10 1 2 0 7 0 8 0 4 0 11 1 3

2 1 0 0 0 1 0 0 0 0 0 0

3 1 0 0 0 0 0 0 0 0 1 0

4 0 0 0 0 0 0 0 1 0 0 0

5 0 0 0 1 0 0 0 0 0 0 0

6 0 0 0,67 -0,67 -1 1 -0,33 0,67 0,8 0,33 0

7 0 0 0 0 0 1 0 0 0 0 0

8 0 0 0 0 0 0 1 0 0 0 0

9 0 1 0 0 0 0 0 0 0 0 0

10 0 1 -0,07 0,07 0 0 -0,07 -0,07 0,02 0,07 0

11 12 13 14 15 16 0 -1000000 -1000000 -1000000 -1000000 -1000000 0 0 0 0 -1 0 0 6,67 0 -0,67 0 0 0 -6,67 0 0,67 0 0 0 0 0 1 0 0 0 0 0 -1 0 0 0 5,67 0 0,33 0 0 0 6,67 -1 -0,67 0 0 1 -1 0 -0,8 0 -1 0 -5,67 0 -0,33 0 0 0 1000001 1000000 1000000 1000000 1000000

5 0,2667 0,2333 0,1 0,6 0,0667 0,1667 0,42 0,6333 1

1 1 0 1 0 0 0 0 0 0 0 0

2 1 0 0 0 1 0 0 0 0 0 0

3 1 0 0 0 0 0 0 0 0 1 0

4 0 0 0 0 0 0 0 1 0 0 0

5 0 -15 1 15 0 0 1 1 -0,3 -1 0

6 0 10 0 -10 -1 1 -1 0 1 1 0

7 0 0 0 0 0 1 0 0 0 0 0

8 0 0 0 0 0 0 1 0 0 0 0

9 0 1 0 0 0 0 0 0 0 0 0

10 0 0 0 1 0 0 0 0 0 0 0

11 12 13 14 15 16 0 -1000000 -1000000 -1000000 -1000000 -1000000 0 100 0 -10 -1 0 0 0 0 0 0 0 0 -100 0 10 0 0 0 0 0 1 0 0 0 0 0 -1 0 0 0 -1 0 1 0 0 0 0 -1 0 0 0 1 1 0 -1 0 -1 0 1 0 -1 0 0 0 1000001 1000000 1000000 1000000 1000000

1,5 0,5 3,5 0,1 0,6 0,3 0,4 0,35 0,4 1

1 1 0 1 0 0 0 0 0 0 0 0

2 1 0 0 0 1 0 0 0 0 0 0

3 1 0 0 0 0 0 0 0 0 1 0

4 0 0 0 0 0 0 0 1 0 0 0

5 0 -1,5 1 0 -1,5 1,5 -0,5 1 1,2 0,5 0

6 0 1 0 0 0 0 0 0 0 0 0

7 0 0 0 0 0 1 0 0 0 0 0

8 0 0 0 0 0 0 1 0 0 0 0

9 0 0,1 0 1 0,1 -0,1 0,1 0 -0,1 -0,1 0

10 0 0 0 1 0 0 0 0 0 0 0

11 12 13 14 15 16 0 -1000000 -1000000 -1000000 -1000000 -1000000 0 10 0 -1 -0,1 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 10 0 0 -0,1 0 0 -10 0 0 0,1 0 0 9 0 0 -0,1 0 0 0 -1 0 0 0 1 -9 0 0 0,1 -1 0 -9 0 0 0,1 0 0 1000001 1000000 1000000 1000000 1000000

0,15 0,5 5 0,25 0,45 0,45 0,4 0,2 0,25 1

vrcholy přípustné domény: (x1) =

0,333 0,500 0,167

(x2) =

0,100 0,570 0,330

(x3) =

0,100 0,350 0,550

(x4) =

0,267 0,100 0,633

(x5) =

0,500 0,100 0,400

(x6) =


0,500 0,250 0,250

x1 0,2667 x2 0,1 x3 0,6333

x1 x2 x3

0,5 0,1 0,4

x1 x2 x3

0,5 0,25 0,25


10

0 9 1 1 0 5 1 2 0 7 0 8 0 4 0 11 1 3

1 1 0 1 0 0 0 0 0 0 0 0

pro omezené návrhové prostory Optimization of uniformity of computer experiments for constrained design spaces

Recommend Documents