Optimalizační metody v informačním managementu

Optimalizační metody v informačním managementu

1


prof. Ing. Petr Dostál, CSc. Ing. Jindřich Petrucha, Ph.D.


Recenzenti: prof. Ing. Karel Rais, CSc., MBA, dr. h. c. prof. Ing. Pavel Ošmera, CSc.

ISBN 978-80-7204-852-6 © Petr Dostál, Jindřich Petrucha, 2013

2


OBSAH

ÚVOD…………………………………………………………….

4

1

FUZZY LOGIKA ……………………………………………….

5

1.1

Fuzzy logika – teorie ……………………………………………………. 5

1.2

Fuzzy logika - aplikace v praxi …………………………………………. 14

2

UMĚLÉ NEURONOVÉ SÍTĚ ………………………………… 36

2.1

Umělé neuronové sítě – teorie …………………………………………. 36

2.2

Umělé neuronové sítě - aplikace v praxi ………………………………. 41

2.3

Predikce časových řad programem NEURO PROJEKT ……………… 48

3

GENETICKÉ ALGORITMY ………………………………… 54

3.1

Genetické algoritmy – teorie …………………………………….…….. 54

3.2

Genetické algoritmy - aplikace v praxi ………………………….…….. 59

4

KLASICKÉ METODY ………………………….……………. 89

Literatura ……………………….……………..………………. 110

3


ÚVOD

Publikace se zabývá optimalizačními metodami v informačním managementu s využitím pokročilých metod, jako je fuzzy logika, neuronové sítě, genetické algoritmy Ve skriptech jsou uvedeny základní principy těchto teorií a četné aplikace použití v oblasti informačního managementu.

Pro účely optimalizace si definujeme model. Model M zapíšeme jako množinu M = {P, V, I, O}, kde P je neprázdná množina prvků, V je neprázdná množina všech vazeb (závislostí) mezi prvky, I je neprázdná množina vstupů a O je neprázdná množina výstupů. Prvky tedy umožňují popsat chování modelu. Schéma ukázky modelu M s dvěma vstupy I1, I2 výstupem O1, třemi prvky P1, P2, P3 a možnými vazbami V je zobrazen na následujícím obrázku. I1

VI,P1

P1 VP3,P1

V1,P2 V2,P1

VP1,P2 VP1,P3 VP2,P1 VP2,P3

I2

VP3,O1 VP3,P2

V2,P2

O1

P3

P2

Obr. Příklad schématu modelu M

Jako modelu pro optimalizaci rozhodování bude v publikaci využito fuzzy logiky, umělých neuronových sítí a genetických algoritmů.

4


1 FUZZY LOGIKA Teorie množin definuje množinu jako soubor prvků určitých vlastností. Prvek potom do množiny patří, nebo ne (0 nebo 1). Jde tedy pouze o dva stavy. L. Zadeh vytvořil teorie fuzzy množin a fuzzy logiky, kdy se určuje, „jak moc“ prvek do množiny patří nebo ne (proměnná x a její příslušnost k množině se značí µ(x) a je definována v rozmezí od 0 po 1; 0 znamená úplné nečlenství a 1 úplné členství). Užití míry členství odpovídá v řadě situací lépe než užití konvenčních způsobů zařazování členů do množiny podle přítomnosti či nepřítomnosti. Fuzzy logika tedy měří jistotu nebo nejistotu příslušnosti prvku k množině. Obdobně se rozhoduje člověk při činnosti v oblasti duševní a fyzické u ne zcela algoritmizovaných činností. Pomocí fuzzy logiky lze najít řešení pro daný případ z pravidel, která byla definována pro podobné případy. Metoda, užívající nezřetelných množin (fuzzy), patří mezi metody, které se používají v oblasti optimalizace informačního managementu. Kromě aplikací z fuzzy logiky se lze setkat i s kombinovanými systémy, např. s neuronovými sítěmi, tzv. neurofuzzy aplikacemi, apod.

1.1 Fuzzy logika - teorie Tvorba systému s fuzzy logikou obsahuje tři základní kroky: fuzzifikaci, fuzzy inferenci a defuzzifikaci. Viz obr. 1. fuzzifikace

fuzzy inference

deffuzifikace

Obr. 1 Rozhodování řešené fuzzy zpracováním První krok znamená převedení reálných proměnných na jazykové proměnné. Definování jazykových proměnných vychází ze základní lingvistické proměnné, např. u proměnné riziko lze zvolit následující atributy: žádné, velmi nízké, nízké, střední, vysoké, velmi vysoké riziko. Obvykle se používá tří až sedm atributů základní proměnné. Stupeň členství atributů proměnné v množině je vyjadřován matematickou funkcí. Existuje mnoho tvarů těchto členských funkcí. Typy, které našly v praxi největší uplatnění, se nazývají standardními funkcemi členství a patří k nim typy: Λ, π, Z a S zobrazené na obr. 2.

5


Obr. 2 Tvary členských funkcí typu Λ, π, S a Z V seznamu standardních funkcí členství existuje i řada jiných typů, např. vyhlazené S křivky. Stupeň členství v množině se týká jak vstupních, tak výstupních funkcí. Druhý krok definuje chování systému pomocí pravidel typu , na jazykové úrovni. V těchto algoritmech se objevují podmínkové věty, vyhodnocující stav příslušné proměnné. Tyto podmínkové věty mají známou formu z programovacích jazyků: Vstupa Vstupb ….. Vstupx Vstupy …….. Výstup1 tj. když (nastane stav) Vstupa a Vstupb, ….., Vstupx a Vstupy …… , potom (je situace) Výstup1. Pravidla fuzzy logiky představují expertní systém. Každá kombinace atributů proměnných, vstupujících do systému a vyskytujících se v podmínce , představuje jedno pravidlo. Místo logické operace může být . Pro každé pravidlo je třeba určit stupeň podpory, tj. váhu pravidla v systému. Výsledek systému s fuzzy logikou závisí do značné míry na správném určení významu definovaných pravidel. Váhu těchto pravidel lze v rámci průběhu optimalizace systému měnit. Podobně jako pro část pravidla umístěného za je třeba vybrat odpovídající atribut za částí . Tato pravidla si tvoří uživatel sám. Fuzzy logika používá odlišných postupů u čtyřech základních operací - sčítání, odčítání, násobení, dělení. Tyto pravidla jsou:

[a,b] + [d,e] = [a+d, b+e] , [a,b] - [d,e] = [a-e, b-d], [a,b] . [d,e] = [min(ad,ae,bd,be), max(ad,ae,bd,be)], [a,b] / [d,e] = [min(a/d,a/e,b/d,b/e), max(a/d,a/e,b/d,b/e)]. Např. [2,5] + [1,3] = [3,8] , [2,5] - [1,3] = [-1,4] , [3,4] . [2,2] = [6, 8], [4,10] / [1,2] = [2, 10].

6


Stejně tak používá fuzzy logika odlišných postupů při vyhodnocování logických operátorů , a , které se vyskytují v pravidlech vyjadřovaných podmínkovými větami , . Viz tab. 1.

A

µ(x∧y)=MIN(µx,µy)

Nebo

µ(x∨y)=MAX(µx,µy)

Ne

µ(¬x)=1-µ(x)

Tab. 1 Logické operace a fuzzy logika Výsledkem fuzzy inference je jazyková proměnná. V případě analýzy rizika mohou mít atributy hodnotu např. velmi nízké, nízké, střední, vysoké, velmi vysoké riziko, atd., což může vést k výstupům jako investici provést ano, ne. Třetí krok převádí výsledek předchozí operace fuzzy inference na reálné hodnoty. Reálnou akcí může být stanovení výše rizika. Cílem deffuzifikace je převedení fuzzy hodnoty výstupní proměnné tak, aby slovně co nejlépe reprezentovala výsledek fuzzy výpočtu. Při postupném zadávání dat funguje systém s fuzzy logikou jako automat. Na vstupu může být mnoho proměnných.

Příklad 1. Uveďme jednoduchý příklad, který bude na základě dílčích rizik vyhodnocovat celkové riziko a rozhodovat, zda investici realizovat, či nikoliv. Budeme uvažovat dílčí rizika politické - Po, ekonomické - Ek, surovinové - Su a prodejní - Pr. Tabulka 2 zobrazuje transformační matici TM, která definuje číselně jednotlivé míry rizika v závislosti na oblasti a stupni rizika (velmi vysoké - VVR, vysoké - VR, střední - SR , nízké - NR, velmi nízké - VNR a žádné – ZR). Tabulku je nutné pro jednotlivá rizika a jejich míru stanovit na základě vlastních zkušeností nebo zkušeností expertů.

VVR VR SR NR VNR ZR

Po 0,500 0,400 0,300 0,200 0,100 0,000

Ek 0,250 0,200 0,150 0,100 0,050 0,000

Su 0,125 0,100 0,075 0,050 0,025 0,000

Tab. 2 Transformační matice TM

7

Pr 0,125 0,100 0,075 0,050 0,025 0,000


Stavová matice S zobrazená v tab. 3 určuje, jaké je riziko u konkrétního případu. I tuto tabulku je nutné vyplnit na základě vlastních zkušeností nebo zkušeností expertů.

Po Ne Ne Ne Ne Ano Ne

VVR VR SR NR VNR ZR

Ek Ne Ne Ne Ano Ne Ne

Su Ne Ne Ano Ne Ne Ne

Pr Ne Ano N N N N

Tab. 3 Stavová matice S Skalární součin matic (v programu Excel je definovaný jako součet násobků jednotlivých položek uvedených polí a tedy odlišně od matematické definice) transformační matice TM a stavové matice S číselně určuje míru celkového rizika R. Dle potřeby je možné definovat retransformační matici RM, která na základě míry celkového rizika R převede číselný údaj na lingvistickou hodnotu. Toto je patrné z tab. 4.

Míra celkového rizika R

VR R>0.7

SR 0.7=>R>=0.4

NR R<0.4

Tab. 4 Retransformační matice RM

Definovaná tabulka 4 míry celkového rizika má tedy atributy: celkové riziko vysoké VR, střední – SR nebo nízké - NR. Jiný způsob vyhodnocení je zobrazen v tab. 5, kde retransformační matice RM na základě míry celkového rizika R převede číselný údaj na lingvistickou hodnotu Ano, Ne, tj. zda investovat či nikoliv. Investice Ano Ne R R <= 0.4 R >0.4 Tab. 5 Retransformační matice RM V našem příkladě (hodnoty Ano je nutno zaměnit za hodnotu 1, a Ne za hodnotu 0) výpočet skalárního součinu transformační matice TM a stavové matice S dá hodnotu celkového rizika R, tj. R = 1.0,100 + 1.0,100 + 1.0,075 + 1.0,100 = 0,375 (výpočet je

8


proveden skalárním součinem matic, kdy nulové hodnoty po součinu dávají 0 a nejsou ve vzorci uvedeny). Toto riziko představuje v našem případě nízké riziko a to znamená, že jde o takové riziko, kdy investici realizujeme. Při jiném zadání stavové matice může výpočet ukázat nevhodnost uvažované investice. Potom lze provádět analýzy, např. zda změnou míry politického rizika, tj. zvolení jiné stabilnější země, vyjde doporučení pro investování. V případech, kdy vystačíme s logickými funkcemi Když, A, Nebo a funkcí v Excelu Součin.skalární, lze použít program Excel od firmy Microsoft. Tímto programem lze řešit i případy, ve kterých je nutné podchytit mnoho vstupních proměnných a lze navolit jednoduché funkce členství. Pokud řešíme složité příklady, budeme muset použít komerčně prodávané programy, jako je např. FuzzyTech od firmy INFORM, GmbH nebo MATLAB od firmy MathWorks Inc.

Příklad 2. Uvedený příklad 1 vyřešíme za pomoci programu FuzzyTech. a) Nejdříve je třeba navolit počet vstupních a výstupních proměnných s jejich atributy a funkcemi členství a počet bloků s pravidly. Vstupní proměnné budou tvořit riziko politické, ekonomické, surovinové a prodejní (Po, Ek, Su, Pr), tj. čtyři vstupy, u kterých zvolíme šest atributů – velmi vysoké riziko, vysoké riziko, střední riziko, nízké riziko, velmi nízké riziko, žádné riziko (např.: PoVVR, PoVR, PoSR, PoNR, PoVNR, PoZR). Výstupem bude míra celkového rizika, tj. jeden výstup, u kterého zvolíme 5 atributů – velmi vysoké riziko, vysoké riziko, střední riziko, nízké riziko, velmi nízké riziko (VVR, VR, SR, NR, VNR). Nejdříve je nutné navolit počet vstupních a výstupních proměnných a jejich proměnné. Viz obr. 3.

Obr. 3 Zadání vstupních proměnných Schéma propojení vstupů s blokem pravidel a výstupem je na obr. 4.

9


Obr. 4 Schéma fuzzy modelu b) Je nezbytné navolit tvary členství pro všechny čtyři vstupy. Zvolíme S, Λ, Z typ pro všechny čtyři vstupy s šesti atributy (tvary členství lze navolit libovolně) pro výše uvedená rizika. Obr. 5 znázorňuje průběhy funkcí pro politické riziko, obdobně to platí pro ostatní rizika.

Obr. 5 Definice atributů a funkce členství pro politické riziko c) Je nutné navolit tvary členství pro výstupní funkci. Zvolíme S, π a Z, které nejlépe vystihují skutečnost. Na obr. 6 je průběh členství pro celkové riziko.

Obr. 6 Definice atributů a funkce členství pro celkové riziko

10


d) Je nezbytné u bloku pravidel navolit pravidla a jejich váhy (DoS = degree of support) mezi vstupy a výstupem. Váhu pravidel lze v průběhu optimalizace měnit. Část tabulky pravidel je v tab. 6.

Tab. 6 Část tabulky pravidel Např. první řádek tab. 6 říká, že je-li politické riziko velmi vysoké (PoVVR) a zároveň ekonomické riziko velmi vysoké (EkVVR)

a zároveň surovinové riziko velmi vysoké

(SuVVR) a současně prodejní riziko velmi vysoké (PrVVR), potom je celkové riziko také velmi vysoké (VVR).

Sestavený program lze používat pro podporu rozhodování. Jakým způsobem se toho dosáhne, uvedeme na jednodušším, následujícím příkladě 3.

Příklad 3. Pro pochopení využití fuzzy logiky a závislosti mezi vstupními a výstupními veličinami uveďme nejjednodušší případ, kdy budeme mít dva vstupy in1 a in2 a jeden výstup out1. Viz obr. 7.

11


Obr. 7 Fuzzy logika – schéma

Obr. 8 Fuzzy logika – stav Low

a b c d

Funkce členství bude křivka ve tvaru S a Z pro Low a High u obou vstupů a křivka Λ pro Low a High na výstupu, které nejlépe vystihují skutečnost.

Obrázek 8 zobrazuje navolení funkcí členství pro vstup in1 (obr. 8a), in2 (obr. 8b) a výstup out1 (obr. 8c) a pravidel (obr. 8d). Obrázky v obr. 8 ukazují, že je-li navolen vstup in1 jako Low a in2 jako Low, potom je výstup out1 Low (viz dolní šipka vlevo). Platí tedy pravidlo in1 = Low in2 = Low out1 = Low. Tato skutečnost je znázorněna vyčerněním políček v pravém dolním obrázku pravidel.

12


Obrázek 9 je obdobný obr. 8. a zobrazuje navolení funkce členství pro vstup in1 (obr. 9a), in2 (obr. 9b) a výstup out1 (obr.9c) a pravidel (obr. 9d). Obrázky v obr. 9 ukazují, že je-li navolen vstup in1 jako High a in2 jako High, potom je výstup out1 High (viz dolní šipka vpravo). Platí tedy pravidlo in1 = High in2 = High out1 = High. Tato skutečnost je znázorněna vyčerněním políček v pravém dolním obrázku pravidel.

Obr. 9 Fuzzy logika – stav High

a b c d

Obrázek 10 je obdobný obr. 8 a zobrazuje navolené funkce členství pro vstup in1 (obr. 10a), in2 (obr. 10b) a výstup out1 (obr. 10c) a pravidel (obr. 10d). Obrázky v obr. 10 ukazují, že je-li navolen vstup in1 jako Middle a in2 jako Middle, potom je výstup out1 Middle (viz dolní šipka uprostřed). Platí tedy pravidlo in1 = Middle in2 = Middle out1 = Middle. Tato skutečnost je znázorněna vyčerněním poloviny políček v pravém dolním obrázku pravidel.

13


Obr. 10 Fuzzy logika – stav Middle

a b c d

1.2 Fuzzy logika – aplikace v praxi Příklad 4. Příklad představuje variantu možnosti využití fuzzy logiky při rozhodování koupě nemovitosti. Byla použita metodika výpočtu, která byla popsána v příkladu 1 využívajícího program Excel. Z tohoto důvodu se omezíme pouze na zobrazení matic a krátký popis. Popis transformační matice TM je uveden v tab. 7 a transformační matice s vyobrazením funkcí členství v tab. 8. Hodnoty funkcí členství se volí na základě priorit, které si člověk pracující s programem stanoví. Příslušné buňky popisu a hodnot si odpovídají. Hodnoty transformační matice se stanoví podle požadavků jedince, firmy nebo organizace. Hodnoty jednotlivých atributů mohou mít lineární i nelineární průběh, např. hodnoty 0; 4; 6; 10;

6;

2.

Uvedené

hodnoty

znamenají,

že

upřednostňujeme

nemovitost

o 4 místnostech, jejíž váha je ohodnocena hodnotou 10. Poměr maximálních hodnot mezi jednotlivými vstupními veličinami se volí dle potřeb, např. hodnoty 10:14:10:10:10:16:10 znamenají, že upřednostňujeme kritérium ceny před ostatními.

14


Poč. místností

Velikost v m2

Vlastnictví

Kuchyně

Poloha

1 2 3 4 5 >5

0–50 51-70 71-90 91-110 111-140 141-více

Státní Pronájem Družstevníí Osobní

ano ne

město okraj města vesnice samota

1 2 3 4 5 6

Cena 106 Kč <0,5 0,5-1 1-2 2-5 5-10 >10

Zahrada Není Velmi malá Malá Střední Velká Velmi velká

Tab. 7 Popis transformační matice TM

Poč. místností

Velikost v m2

Vlastnictví

Kuchyně

Poloha

Cena

2,0

0,0

1,0

10,0

8,0

2,0

Zahrada 0,0

4,0

4,0

4,0

0,0

10,0

5,0

5,0

6,0

5,0

8,0

4,0

16,0

10,0

10,0

14,0

10,0

2,0

8,0

5,0

6,0

10,0

4,0

2,0

2,0

5,0

0,0

0,0

Max. 10

Max. 14

Max. 10

Max. 10

Max. 10

Max. 16

Max. 10

∑=80

Min. 2

Min. 0

Min. 1

Min. 0

Min. 2

Min. 0

Min. 0

∑=5

Tab. 8 Transformační matice TM

Pro konkrétní nemovitost dostáváme vždy jednu stavovou matici S, např. viz tab. 9, jejíž hodnoty odpovídají parametrům vyhodnocované nemovitosti. V tabulce použijeme symboly A (ano), N (ne), protože lépe odpovídají realitě. Při výpočtu je nutné tyto hodnoty převést na čísla 1 (ano) a 0 (ne).

1 2 3 4 5 6

Poč. místností

Velikost v m2

Vlastnictví

Kuchyně

Poloha

Cena

Zahrada

N N A N N N

N N N A N N

N N N A

A N

N N A N

N A N N N

N A N N

Tab. 9 Stavová matice S Pro konkrétní situaci dostáváme konkrétní hodnotu, která je skalárním součinem transformační TM a stavové matice S

15


R = 1*6 + 1*14 + 1*10 + 1*10 +1*4 + 1*5 + 1*5 = 54. Protože výsledek chceme v procentech v rozsahu 0-100 %, musíme odečíst sumu minimálních hodnot, vydělit je rozdílem maximální a minimální sumy a vynásobit hodnotou 100, tj. 100 * (54 - 5) / (80 - 5) = 65.3 %.

Je-li stanovena retransformační matice RM, např. tabulkou 10, a obdržíme-li v našem případě 67.5 %, potom výstupem je lingvistická proměnná nemovitost Sledovat.

1 2 3 4

Body [%] 0-50 50-70 70-90 90-100

Nemovitost Nezajímat se Sledovat Zvážit koupi Ihned koupit

Tab. 10 Retransformační matice RM Porovnáváme-li více nemovitostí (tj. dosadíme-li pro každou nemovitost její parametry do stavové matice, odpovídající zkoumané nemovitosti), lze si zobrazit všechny konkrétní případy a vybrat tu nejlepší, jak je to patrné z obr. 11, kde na svislé ose jsou procenta, která nemovitost oceňují.

Nemovitosti 75

Zvážit koupi

[%]

60

Sledovat

45 Nezajímat se

30 15 0 Nem. č.1

Nem. č.2

Nem. č.3

Nem. č.4

Obr. 11 Rozhodování pomocí fuzzy logiky – výběr nemovitosti

16


Příklad 5. Příklad představuje variantu možnosti využití fuzzy logiky při manažerském rozhodnutí týkajícího se výběru nejvhodnějšího bankovního ústavu, působícího na území České republiky, dle našich potřeb. Metodika byla popsána v příkladu 1, proto se omezíme pouze na krátký popis a zobrazení výsledku. Transformační matice TM obsahuje např. tyto parametry: minimální vklad, roční úroková sazba v procentech, poplatek za otevření účtu, poplatek za vedení účtu, poplatek za výběr z bankomatu u vlastní banky, poplatek za výběr z bankomatu u jiné banky, poplatek za zrušení účtu, poplatek za měsíční přímé bankovnictví, atd. Nastavíme-li hodnoty transformační matice TM dle našich požadavků a dosadíme-li do stavové matice S, charakterizující parametry zkoumaných bank, údaje Ano, Ne, lze provést výpočet skalárního součinu R. Hodnota R určuje vhodnost banky na základě námi navolených priorit (funkcí členství). Výsledek je patrný na obr. 12, kdy pro nás nejvhodnější banka má největší počet bodů.

Hodnocení běžných účtů bank

80

70

75

74 57

60

GE

KB

70 60 50 40 30 20 10 0 ČS

ČSOB

eBanka

Obr. 12 Rozhodování pomocí fuzzy logiky – výběr banky

Příklad 6. Příklad představuje variantu možnosti využití fuzzy logiky v manažerské praxi při rozhodnutí, kterého uchazeče – analytika do zaměstnání přijmout (popř. propustit).

Metodika byla popsána v příkladu 1, proto se omezíme pouze na zobrazení tab. 11, která je výsledkem výpočtu. Tabulka, vypracovaná Vlastimilem Koutníkem, studentem UTB ve Zlíně v roce 2002, zobrazuje odpovědi (Ano, Ne) včetně vah jednotlivých odpovědí,

17


vyhodnocuje úspěšnost jednotlivých zájemců na pozici analytika a stanovuje jako vítěze řízení pana Kučeru.

Přijímací řízení na pozici analytika Odp. Základní informace:

Znalosti práce na PC:

Cizí jazyk:

Ostatní kritéria: Počet bodů: Úspěšnost: Hodnocení: Rozhodnutí:

Pohlaví Věk Vzdělání Praxe MS DOS MS Windows MS Word MS Excel MS Access Internet FTP MS Visual Basic Ostatní programy AJ NJ RJ FrJ Řidičský průkaz Vlastní automobil

M 40 ZV 5 Ne Ano Ano Ano Ne Ano Ne Ne Ano Ano Ne Ne Ne Ano Ne

Adam Body 60 30 10 20 0 30 20 60 0 20 0 0 10 30 0 0 0 20 0 310 62.00% Průměrné

Odp. M 30 VV 5 Ano Ano Ano Ano Ano Ano Ano Ano Ano Ne Ano Ano Ne Ano Ano

Kučera Body 60 50 45 20 5 30 20 60 40 20 10 15 10 0 15 10 0 20 20 450 90.00% Dobré Vítěz řízení

Novotná Odp. Body

Odp.

Z 35 ZV 1 Ne Ano Ano Ano Ne Ano Ne Ne Ne Ano Ne Ne Ano Ano Ne

M 60 SV 20 Ne Ano Ano Ne Ne Ano Ne Ne Ne Ne Ano Ne Ano Ne Ne

60 40 10 0 0 30 20 60 0 20 0 0 0 30 0 0 10 20 0 300 60.00% Průměrné

Novák Body 60 10 25 40 0 30 20 0 0 20 0 0 0 0 15 0 10 0 0 230 46.00% Nevyhovující

Tab. 11 Rozhodování pomocí fuzzy logiky – přijímací řízení

Příklad 7. Příklad představuje variantu možnosti využití fuzzy logiky v manažerské praxi při hodnocení klientů advokátní kanceláře, zpracovaný Martinem Řehůřkem studentem VUT Brno v roce 2005. Byla použita metodika uvedená v příkladě 1. Nejzajímavějším částí je dvacet pět vstupních proměnných, jejichž popis je uveden v tab. 12.

Součástí řešení je určení hodnot transformační matice TM podle priorit, které advokátní kancelář preferuje. Na základě dosazení hodnot Ano, Ne do stavové matice S, charakterizující konkrétního klienta, obdržíme po výpočtu hodnotu R. V tomto případě je výsledkem programu jedna hodnota, která představuje „kvalitu“ klienta pro advokátní kancelář. Na základě této informace se kancelář může rozhodnout na způsobu jednání s klientem.

18


I II III IV V VI VII VIII IX X XI XII XIII

Časová náročnost případu Doba trvání Maximální dosažitelný zisk Minimální zisk Hodinové ohodnocení Nákladovost Možnost přísudku Vymožitelnost přísudku Odborná náročnost Perspektiva klienta Stálost klienta Image klienta Solventost klienta

XIV XV XVI XVII XVIII XIX XX XXI XXII XXIII XXIV XXV

Názor na klienta Místo poskytování právní pomoci Způsob poskytnutí právní pomoci Právní sféra SP vs. VP Právní sféra HmP vs PP Převažující právní odvětví Oprávněnost nároku Výsledek pro klienta Subjektivní hodnocení zakázky Jednáni s veřejnými orgány Možnost postoupení práce Celkové osobní ohodnocení

Tab. 12 Popis vstupních proměnných transformační matice TM

Součástí řešení je určení hodnot transformační matice TM podle priorit, které advokátní kancelář preferuje. Na základě dosazení hodnot Ano, Ne do stavové matice S, charakterizující konkrétního klienta, obdržíme po výpočtu hodnotu R. V tomto případě je výsledkem programu jedna hodnota, která představuje „kvalitu“ klienta pro advokátní kancelář. Na základě této informace se kancelář může rozhodnout na způsobu jednání s klientem.

Příklad 8. Příklad představuje variantu možnosti využití fuzzy logiky v odběratelskododavatelských vztazích při hodnocení dodavatelů firmy, zpracované Ivou Jančíkovou studentkou VUT Brno v roce 2007. Byla použita metodika uvedená v příkladě 1. Nejzajímavějším částí je dvanáct vstupních proměnných, jejichž popis je uveden v tab. 13.

1 2 3 4 5 6 7

I.

II.

III.

Cena

Termín dodání (rychlost dny)

Kvalita

příliš vysoká

0-1

vynikající

vysoká

dobrá

podezřele nízká

1-3 3-6 6 - 10 > 10

x x

x x

přijatelná nízká

uspokojivá neuspokojivá

x x x

19

IV.

V.

Dostupnost Spolehlivost (km) dodávky (%)

0 -10 10 - 25 25 - 35 35 - 50 > 50 x x

0 -20 20 - 40 40 - 60 60 - 75 75 - 90 90 - 100 neznáme

VI. Způsob platby

hotovost dobírka splátky faktura x x x


1 2

VII.

VIII.

IX.

X.

XI.

XII.

Zkušenost s dodavatelem

Přístup zaměstnanců (ochota, komunikace)

Slevy (%)

Záruky, servis

Balení

Odhad životaschopnosti dodavatele

dobrá záruka i servis

palety krabice

prosperující stagnující

špatná zatím žádná

3 4 5

uspokojivá

6 7

velmi dobrá

dobrá vyhovující

vynikající

vynikající, ochotný výborný

0 - 0,5 0,5 - 2

dobrý uspokojivý neochota

2 - 3,5

x x

10 - 12

dobrý servis

kontejner vhodné nedostatečná záruka nedostatečný servis nevhodné dobrá záruka

3,5 - 6 6 - 10

žádný servis x

> 12

x x

známky problémů

v konkurzu v počátcích neumíme odhadnout

x

Tab. 13 Popis vstupních proměnných transformační matice TM

Součástí řešení je určení hodnot transformační matice TM podle priorit, které firma preferuje. Na základě dosazení hodnot Ano, Ne do stavové matice S, charakterizující konkrétního dodavatele, obdržíme po výpočtu hodnotu R. V tomto případě je výsledkem programu jedna hodnota, která představuje „kvalitu“ dodavatele pro firmu. Na základě této informace se firma může rozhodnout na spolupráci s dodavatelem např. pojmy ukončit, varovat, monitorovat a pokračovat ve spolupráci. Tato úloha se velmi často vyskytuje v praxi a je potřeba ji řešit např. výše uvedeným způsobem.

Příklad 9. Z důvodu relaxace od obtížné tématiky, která se v manažerském rozhodování vyskytuje, uvedeme příklad možného využití fuzzy logiky při hledání ideální partnerky, zpracovaný Petrem Fuskem studentem UTB ve Zlíně v roce 2002. Byla použita metodika uvedená v příkladě 1. Omezíme se pouze na nejzajímavější část příkladu a tou je popis transformační matice TR. Viz tab. 14.

Způsob vyhodnocení je zobrazen v tab. 15, kde retransformační matice RM na základě hodnoty R převede číselný údaj na lingvistickou hodnotu, podle níž se uchazeč o dívku rozhodne jak dále postupovat.

20


Vzhled

Inteligence

Majetek

Rodinné choroby

Tchýně a tchán

velmi vysoká

Miss

>130

Zazobaná

Sportovci

vysoká

Kráska

120-130

Bohatá

Nežijí Velmi staří Mimo ČR Vlažný vztah Vřelý vztah

Žádné

nadprůměrná

Kočka

110-120

Stabilní příjem

podprůměrná

Průměrná

100-110

Závislá

nízká

Špatná

90-100

Nemajetná

<90

Sociální případ

velmi nízká

Příšerná

Téměř žádné Méně vážné Vážná choroba Vážné a mnoho

V domě

Vzdělání

Povaha

Rodinný stav

VŠ

Náruživá

Svobodná

VOŠ

Společenská

Zadaná

Maturita

Náladová

Vdaná

Vyučená

Dominantní

Gravidní

Základní

Hrabivá

Rozvedená

Blondýna

Hysterická

Důchodkyně

Tab. 14 Popis transformační matice T

Zařazení do kategorie žádný poměr příležitostné schůzky vážný vztah okamžitá svatba

Body 〈0 – 60) 〈60 – 90) 〈90 – 99) 〈99 - 100〉

Tab. 15 Retransformační matice RM

Hodnoty transformační matice TR a využití úlohy si může každý muž vytvořit podle svých požadavků na partnerku.

Příklad 10. Bylo by vhodné uvést i opačný příklad, tj. hledání ideálního partnera, který zpracovala Jana Vojtová studentka VUT v Brně v roce 2005. Opět se omezíme pouze na nejzajímavější část práce, a tou je popis transformační matice TM. Viz tab. 16.

Výška (cm)

Postava

Vzdělání

Zaměstnání

Smysl pro humor

Trávený volný čas

Oblíbenost kulturních akcí

"Jiskření"

Věk

1

< 150

podvyživený

vyučený

dělník

ano

ano

ano

ano

< 25

2

150 - 160

štíhlý

maturita

zaměstnanec

ne

ne

ne

ne

25 - 30

VŠ

střední management

jak kdy

3

160-170

střední

4

170-180

mírně obézní

5

180-190

obézní

6

>190

top management

30 - 35 35 - 40

Tab. 16 Popis transformační matice TM

21


Hodnoty transformační matice TR a využití úlohy si může každá dívka hledající partnera vytvořit podle svých představ či nároků.

Po uvedení příkladů 3. až 10, které využívaly pro práci programu Excel, a dokládají všestrannost použití fuzzy logiky, se zaměříme na profesionálnější zpracování a to za pomoci programu FuzzyTech.

Příklad 11. Příklad představuje variantu možnosti využití fuzzy logiky při rozhodování banky, zda hypoteční úvěr poskytnout či nikoliv. Pro výpočet byl použit program FuzzyTech. Práce s programem byla vysvětlena na příkladu 2. Aplikace bude řešena pěti vstupními proměnnými se třemi nebo pěti atributy, čtyřmi bloky pravidel a jednou výstupní proměnnou s pěti atributy. Po spuštění programu FuzzyTech vyplníme tabulku projektu zobrazenou na obr. 13 dle potřeb námi vytvořeného modelu.

Obr. 13 Zadání projektu Po ukončení zadání má nepropojený model následující tvar. Viz obr. 14.

22


Obr. 14 Schéma projektu Vstupní a výstupní proměnné je nutné popsat a propojit s bloky pravidel. Vstupem jsou proměnné Budova, Pozemek, Majetek, Prijem a Urok. Výstupy z bloků pravidel jsou Stavba, Zadatel a Uver. Výstupní proměnnou je Uver. Výsledné schéma je na obr. 15.

Obr. 15 Schéma projektu

23


Následuje volba atributů a funkcí členství. Bylo navoleno pět atributů pro vstupní proměnnou Budova a tři atributy pro vstupní proměnné Pozemek, Majetek, Prijem, Urok, Stavba a Zadatel. Výstupní proměnná Uver má pět atributů. Funkce členství jsou tvaru S, Λ a Z. U proměnné Prijem je použito S-křivky. Následující obrázky zobrazují atributy a funkce členství všech proměnných. Při volbě atributů musíme promyslet jejich počet pro jednotlivé proměnné. U funkcí členství pak jejich tvar a průběh. Záleží na zkušenostech tvůrce modelu a na procesu jeho odlaďování, kdy lze porovnávat výsledky modelů se skutečností, a tím provádět zásahy do tvaru a průběhu funkcí členství. Teprve tehdy, je-li model odladěn, lze jej využívat v praxi. Následující obrázky zobrazují atributy a průběhy funkce členství pro vstupní proměnnou Budova (obr. 16), Pozemek (obr. 17), Majetek (obr. 18), Prijem (obr. 19) a Uver (obr. 20).

Obr. 16 Atributy a funkce členství proměnné Budova

Obr. 17 Atributy a funkce členství proměnné Pozemek

24


Obr. 18 Atributy a funkce členství proměnné Majetek

Obr. 19 Atributy a funkce členství proměnné Prijem

Obr. 20 Atributy a funkce členství proměnné Urok

25


Následující obrázky zobrazují atributy a průběhy funkce členství pro proměnné vystupující z bloku pravidel a to Stavba (obr. 21) a Zadatel (obr. 22).

Obr. 21 Atributy a funkce členství proměnné Stavba

Obr. 22 Atributy a funkce členství proměnné Zadatel Atributy a průběhy funkce členství pro výstupní proměnnou Uver jsou na obr. 23, kdy byly navolené atributy v jaké částce má být poskytnut úvěr: Velmi nízké, Nízké, Střední, Vysoké a Velmi vysoké.

26


Obr. 23 Atributy a funkce členství proměnné Uver Obrázek 24 zobrazuje čtyři bloky pravidel včetně tzv. váhy pravidla (DoS = Degree of Support), řešící vztah mezi vstupními a výstupními proměnnými. Blok pravidel Stavba je na obr. 24a, blok pravidel Zadatel na obr. 24b, blok pravidel Uver (vstup Prijem, Urok) na obr. 24c a blok pravidel Uver (vstup Stavba, Zadatel) na obr. 24d.

Tvorba pravidel byla

vysvětlena na příkladu 2.

Obr. 24a

Bloky pravidel

Obr. 24b

Obr. 24c

Bloky pravidel

Obr. 24d

27


Po vytvoření modelu lze program buď odlaďovat (zadáváme známé vstupní hodnoty, porovnáváme výsledek se skutečností a provádíme změny v tvaru funkcí členství) nebo, je-li hotový, tak využívat (zadáváme vstupní hodnoty a výstupní veličina je pro nás podkladem pro rozhodování). Obrázek 25 zobrazuje stav, kdy na základě vstupních proměnných je vyhodnocena možnost poskytnutí hypotéky jako vysoká.

Obr. 25 Výsledek fuzzy výpočtu

Příklad 12. Příklad představuje zjednodušenou variantu možnosti využití fuzzy logiky při rozhodování, zda máme počítač koupit či nikoliv. Pro výpočet byl použit program FuzzyTech. Práce s programem byla vysvětlena na příkladu 2. Aplikace bude řešena třemi vstupními proměnnými

se třemi atributy, jedním blokem s pravidly a jednou výstupní

proměnnou s dvěma atributy. Po spuštění programu vyplníme tabulku projektu dle obr. 26.

Obr. 26 Zadání projektu

28


Po ukončení zadání se zobrazí model v základním tvaru; je nutné popsat proměnné a propojit bloky. Vstupem jsou proměnné Kapacita_HD, Rych_procesoru, Vnitrni_pamet a Cena. Výstupem je Koupe. Vytvořený model má tvar zobrazený na obr. 27.

Obr. 27 Schéma projektu Následuje volba atributů a funkcí členství. Byly navoleny tři atributy pro vstupní proměnnou Kapacita_HD, Rych_procesoru a Vnitrni_pamet a dva atributy pro výstupní proměnnou Koupe. Funkce členství jsou tvaru S, Λ a Z. Následující obrázky zobrazují atributy a průběhy funkce členství pro vstupní proměnnou Kapacita_HD (obr. 28), Rychlost_procesoru (obr. 29) a Vnitrni_pamet (obr. 30).

Obr. 28 Atributy a funkce členství proměnné Kapacita_HD

29


Obr. 29 Atributy a funkce členství proměnné Rychlost_procesoru

Obr. 30 Atributy a funkce členství proměnné Vnitrni_pamet

Obrázek 31 zobrazuje blok pravidel včetně tzv. váhy pravidla (DoS = Degree of Support), řešící vztah mezi vstupními a výstupní proměnnou. Tvorba pravidel byla vysvětlena na příkladu 2. Je zřejmé, že je-li Kapacita_HD malá a zároveň Rychlost procesoru malá a zároveň Vnitrni_pamet malá, je výsledné doporučení Koupe Ne, tj. počítač nekupovat.

30


Obr. 31 Blok pravidel U výstupní proměnné jsou navoleny dva atributy s funkcí členství S a Z. Průběh funkce členství výstupní proměnné Koupe je na obr. 32.

Obr. 32 Atributy a funkce členství proměnné Vnitrni_pamet Obrázek 33 zobrazuje stav, kdy na základě vstupních hodnot je vyhodnocen stav, kdy není doporučena koupě počítače.

31


Obr. 33 Výsledek fuzzy výpočtu Uvedený model je jen nástinem možné realizace a je zřejmé, že další potřebnou vstupní veličinou bude Cena.

Příklad 13. V následujícím příkladu nastíníme možnost řešení rozhodování za pomoci fuzzy logiky programem FuzzyTech, kdy je vydavatelstvím vyhodnocován záměr, zda knihu vydat či nikoliv. Aplikace je řešena deseti vstupními proměnnými se třemi až pěti atributy, čtyřmi bloky pravidel a jednou výstupní proměnnou se třemi atributy. Schéma projektu je na obr. 34. Vstupy prvního bloku Kniha jsou tvořeny veličinami Autor (známý, neznámý), Naklad knihy (malý, střední, velký), Rozsah počtu stran (malý, střední, velký). Vstupy druhého bloku Prodejnost jsou tvořeny veličinami Ctenar, jejich odhadovaný počet (malý, střední, velký) a Obor, který obsahuje (např. technický, přírodní, ostatní).

Vstupy třetího bloku

Vydani/Podpora jsou tvořeny veličinami Grant (ano, ne), Inzerce (ano, ne), Reklamní kampaň (malá, střední, velká) a Sponzor (ano, ne). Výstupy z bloku Kniha a Prodejnost, společně se samostatným vstupem Zkusenost vydavatele, který může ovlivnit počet výtisků knihy na základě svých dlouhodobých zkušeností a intuice, definují blok Vydani/Rentabilita určující rentabilitu vydání (malá, střední, velká). Výstupní veličina Vydání určuje na základě vstupů z bloků Rentabilita a Podpora, zda knihu vydat a v jakém množství (nevydat, malý, střední, velký počet vydání).

32


Obr. 34 Schéma projektu Po sestavení modelu, určení atributů a funkcí členství lze po odladění model využívat. Obrázek 35 zobrazuje výsledek výpočtu, kdy je s velkou váhou doporučeno knihu vydat ve středním nákladu (viz výše tmavých úseček na obrázku).

Obr. 35 Výsledek fuzzy výpočtu

33


Pokud vydavatel považoval za malý náklad 500 ks, za střední náklad 750 ks a velký náklad 1000 ks, potom doporučení odpovídá nákladu 800 ks výtisků.

Uvedený model může postačovat, nebo se může realizovat detailnější provedení. Odladěný a fungující model se potom stává know how a je tajemstvím firmy, která jej využívá.

Příklad 14. Jako příklad využití fuzzy logiky úřadem státní správy lze uvést rozhodnutí o výběru vhodné banky. Podstatnými kritérii je finanční stránka a stránka služeb. Finanční stránka zahrnuje úvahu nad poplatky, které mohou být nízké, ale v rámci častých plateb může jít o značnou finanční částku. Stránka služeb zahrnuje, zda služby, které potřebujeme, jsou dostupné a v jaké kvalitě.

Obr. 36 Schéma projektu

Aplikace je řešena devíti vstupními proměnnými se třemi až pěti atributy, třemi bloky pravidel a jednou výstupní proměnnou se čtyřmi atributy. Vstupy bloku Poplatky jsou tvořeny veličinami:

poplatek

za

Odchozi_platbu

34

tuzemskou,

Odchozi_platbu

zahraniční,


Prichozí_platbu, Trvalou_platbu, Vedeni_uctu. Vstupy bloku Služby jsou tvořeny veličinami: poplatek za výběr v Bankomatu, placení Kartou, Vypisy. (Atributy vstupních proměnných jsou: velmi nízký, nízký, střední, vysoký a velmi vysoký poplatek). Vstupní proměnná Urok představuje výši úroku z uložených peněz (nízký, střední vysoký). Výstup z bloku Poplatky (velmi nízký, nízký, střední, vysoký, velmi vysoký) a Služby, představující úroveň služeb (nízká, střední, vysoká), společně se vstupní proměnnou Urok definují výstupní proměnnou Zrizení_uctu (Ne, Asi ne, Asi ano, Ano). Obr. 36 zobrazuje vytvořený model.

Provedeme-li vyhodnocení bank, které zkoumáme a máme o nich informace, obdržíme návrh rozhodnutí se kterou bankou smlouvu uzavřít.

Závěr: Uvedených čtrnáct příkladů je jen zlomkem variant možného použití fuzzy logiky v nejrůznějších oblastech na nejrůznější úrovni rozhodování v personální, správní, ekonomické, finanční a dalších oblastech. Z velkého množství variant lze dále uvést již odzkoušené projekty, např. výběr banky klientem za účelem poskytnutí úvěru a půjčky, vyhodnocení bonity klienta bankou pro poskytnutí úvěru nebo půjčky, výběru pojišťovny, spořitelny, kampeličky, fondu, realitní kanceláře, koupě nemovitosti, pozemku, podnájmu, auta, mobilu, mobilního operátora, satelitu, fotoaparátu, televize, zbraně, počítače, internetového poskytovatele, zaměstnání, zaměstnance, dodavatele materiálu, ale i rozdělení prémií, výběr školy, vyhledání nadaných studentů, volba zahraničního studia, nákupu hráče v kopané, jezdeckého koně, dovolené, zájezdu, atd.

35


2 UMĚLÉ NEURONOVÉ SÍTĚ Umělé neuronové sítě jsou jistým (nedokonalým) modelem myšlení lidského mozku. Umělé neuronové sítě jsou označovány termínem „černá skříňka“ neboť nelze znát detailně vnitřní strukturu systému. Na vnitřní strukturu systému, jenž je modelován „černou skříňkou“, klademe pouze několik předpokladů, které nám umožní popsat chování systému funkcí, které provádí transformaci vstup - výstup. Neuronové sítě je vhodné použít v případě, kdy značnou roli v modelovaném procesu hraje náhoda a kde deterministické závislosti jsou natolik složité a provázané, že je nedokážeme separovat a analyticky identifikovat. Jsou tedy vhodné pro modelování složitých, často nevratných, strategických rozhodnutí.

2.1 Umělé neuronové sítě - teorie Černá skříňka umělé neuronové sítě prakticky pracuje ve dvou fázích. V první fázi vystupuje síť (model složitého systému) v roli "zvídavého žáka", tj. učí se nastavit své parametry tak, aby co nejlépe vyhovovaly požadované topologii sítě. V druhé fázi se stává síť "odborníkem", neboť produkuje výstupy na základě znalostí získaných v první fázi. Při konstrukci každé neuronové sítě musíme definovat jednotlivé vrstvy sítě (vstupní, skryté, výstupní), jednotlivé vstupní a výstupní neurony, způsoby propojení neuronů navzájem mezi sebou (formulace přenosové funkce neuronů mezi skrytými vrstvami). Historie vzniku umělých neuronových sítí spadá do první poloviny 20. století. První práce uveřejnil W.S. McCulloch, dále W. Pitts vypracoval model nejjednoduššího neuronu a F. Rosenblatt vytvořil funkční perceptronovou síť, která řešila pouze problémy lineárně separabilní, tj. oblasti musely být od sebe lineárně odděleny. w1

p1

w2

p2

w3

p3

.

. pR

∑

.

.

a

n

f .

.

.

.

.

wR b

Obr. 37 Jednovrstvá neuronová síť 36


Později došlo k dalšímu vývoji umělých neuronových sítí po objevení vícevrstevných sítí, které tento nedostatek odstraňovaly. Šlo o práci D. Rumelharta, G. Hintona a R. Williamse, kteří vytvořili výpočetní metodu nazvanou backpropagation. Od tohoto období došlo k velkému rozmachu umělých neuronových sítí, což se zejména týká matematického zpracování a struktury sítě. Nejjednodušší umělou neuronovou síť (označovanou jako perceptron) si lze představit, viz. obr. 37 jako vstup R hodnot, které označíme p1, p2, p3, …., pR, přičemž tyto hodnoty jsou násobeny váhovými koeficienty w1,w2, w3, …., wR. Vliv má také tzv. prahová hodnota b. Platí tedy, že a = w1 *p1 + w2 *p2 + w3 *p3 + … + wR *pR + b =

∑

R

i =1

wi pi + b .

Dále platí, že n = f(a), kdy se používá různých tzv. přenosových funkcí f, z nichž nejdůležitější jsou:

hardlim

e a − e −a 1 n = 0 pro a < 0 , purelin n = a , logsig n = , tansig n = a . n = 1 pro a ≥ 0 1 + e −a e + e −a

Grafy průběhů těchto funkcí jsou na obr. 38.

Obr. 38 Přenosové funkce hardlim, purelin, logsig a tansig Nejjednodušší funkcí je funkce hardlim, kdy výstupní hodnota je rovna 1 nebo 0 podle toho, je-li vstupní hodnota větší a rovna nebo menší jak 0. Smyslem použití transformace uvedenými nebo jim podobných funkcí je modifikace úrovně výstupů na normované hodnoty. V případě uvedené funkce logsig jde o hodnoty mezi 0 a 1 a u funkce tansig jde o hodnoty mezi -1 a 1. Bez použití takovýchto nebo podobných transformací by vstupní hodnota mohla dosáhnout vysokých hodnot, což by bylo problémem zejména u vícevrstvých umělých neuronových sítí. Hodnota b, tzv. prahová hodnota, zvětšuje hodnotu sumy (součet vstupů x váhový koeficient) právě o tuto hodnotu. 37


• • • • • • • • • • • • • • • • • •

• • • •

vstupní vrstva

skrytá vrstva

• • • •

• • • •

skrytá vrstva

• • • •

• • • •

• • • •

• • • •

• • • •

• • • •

• • • •

výstupní vrstva

Obr. 39 Schéma vícevrstevné sítě se vstupní, skrytými a výstupní vrstvou Pro perceptron i vícevrstevnou síť platí rovnice v maticovém tvaru n = f (w . p + b). Na obr. 39 je schéma vícevrstevné sítě se vstupní vrstvou, skrytými vrstvami a výstupní vrstvou. Pro výpočet vah umělé neuronové sítě se často používá tzv. metoda back–propagation, která se skládá ze dvou kroků. Nejdříve se provede výpočet výstupů na základě vstupů a vah (krok vpřed), dále se provede výpočet chyby E kterou definujeme vzorcem E = Σ (ni - oi )2, kde n je i-tá hodnota na výstupu a o je i-tá očekávaná hodnota. Výpočet se provádí přes všechny výstupy a v každém cyklu. Tohoto rozdílu se využije k zpětnému výpočtu vah (krok zpět) a proces se opakuje tak dlouho, až chyba E konverguje k akceptovatelné hodnotě. Učící proces lze proto interpretovat jako optimalizační úlohu s účelovou funkcí E definovanou v hyperprostoru, při které se hledá její minimum. Tento postup si uvedeme v příkladu 15.

Příklad 15. Na ukázku si můžeme popsat jednoduchý neuron se dvěma vstupy a jedním výstupem. Vstupem bude riziko politické a ekonomické, představované stavem, zda riziko existuje či nikoliv. Výstupem bude informace, jestli investovat nebo neinvestovat. Perceptron je třeba nejdříve naučit, zda-li investovat či nikoliv, a pak teprve používat pro automatické třídění. Při procesu učení zadáváme, jestli existuje (-1) či neexistuje (1) riziko politické a ekonomické společně s tím, jestliže tento případ vedl k investování (1) či nikoliv (0). Po několika krocích učení pak perceptron dokáže rozlišit po zadání, zda riziko politické a ekonomické existuje či nikoliv (-1,1), u obou rizik, jestli investovat či ne (0,1). Tento příklad je nejjednodušší z možných a byl použit pro ilustraci, jak umělá neuronová síť

38


pracuje. Postup inicializace, učení a vlastní činnosti je následující a předpokládá následující operace práce s maticemi (součin resp. součet) ve tvaru:

   

 a  b  . [c ; d ]  = [ac + bd ] ,   

[a ; b] + k . [c ; d]

= [a + k .c; b + k .d ] .

Pro učení použijeme dvou stavů. První stav bude mít na vstupech i = -1, představující existující riziko politické a ekonomické, jež vedlo k výstupu o = 0, tedy neinvestování. Druhý stav bude mít na vstupech i = 1, představující neexistující riziko politické a ekonomické, jež vedlo k výstupu o = 1, tedy investování. Proces učení je nutné několikrát opakovat s oběma stavy. V počátečním kroku nastavíme váhy perceptronu w1 a w2 na libovolné, ale vhodné číslo, např. 0,5 a -0,5. Proces ukončíme až v případě, kdy výpočtem dojde k nastavení vah perceptronu w1 a w2 tak, aby hodnota vypočtená a skutečná byly shodné pro oba stavy, tedy aby byl rozdíl těchto hodnot (chyba) byl nulový. Tuto podmínku je v praxi obtížné realizovat, proto se chyba má blížit k hodnotě 0. Kroky výpočtu v maticovém tvaru jsou následující: = ii

=i

i =i

w = w + e . i = [ 0.5; − 0.5] + (−1) * [ −1; − 1] = [1.5; 0.5] , =i = ii − 1 = i 1 = ii = i =  , o = [0] , Druhý stav = i =  , o = [1] . − 1 1

První stav

=i

Inicializace: w

a = 0 pro w = w , o = o , i = i , o = o , atd . , funkce hardlim =   a = 1 pro = iii

Platí:

= [0,5;−0,5].

=i

= iii

= i = iv

= ii

= vi

= ii

Proces učení: = i =i  - 1 I. a i = hardlim( w * i ) =  [0,5;−0,5]*   - 1 

=i

  = hardlim (0) = 1 ,  

i

e = o − a = 0 − 1 = −1 , i

= ii

=i

i =i

w = w + e . i = [ 0.5; − 0.5] + (−1) * [ −1; − 1] = [1.5; 0.5] , 39

n < 0,0 . n ≥ 0,0


= ii = ii  1 II. a ii = hardlim( w . i ) =  [1,5;0,5].   1  = ii

  = hardlim (2) = 1,  

ii

e ii = o − a = 1,0 − 1,0 = 0 ,

= iii

= ii

ii = ii

w = w + e . i = [1.5; 0.5] + (0).[1; 1] = [1.5; 0.5] ,

= iii = iii  - 1  III. a iii = hardlim( w . i ) =  [1,5;0,5].    = hardlim (-2) = 0 , - 1  

= iii

iii

= iii

iii

e = o −a = 0−0 = 0, iii

= iv

= i ii

w = w +e .i

= [1 .5; 0 .5] + ( 0 ).[− 1; − 1] = [1 .5; 0 .5 ].

Váhové koeficienty, které měly při inicializaci hodnoty w1 = 0,5 a w2 = -0,5, mají po naučení hodnoty w1 = 1,5 a w2 = 0,5.

Proces testování:

Proces využití naučeného perceptronu je pak následující: • Existuje-li riziko politické (-1) a ekonomické (-1), perceptron nám dá hodnotu 0, což znamená neinvestovat, tj.: = =  - 1 a = hardlim ( w . i ) =  [1,5;0,5] .   - 1 

  = hardlim (-2) = 0 ⇒ Investice - Ne .  

• Neexistuje-li riziko politické (1) a ekonomické (1), perceptron nám dá hodnotu 1, což znamená investovat, tj.: = =  a = hardlim ( w . i ) =  [1,5;0,5]. 

1 1 

  = hardlim (2) = 1 ⇒ Investice - Ano.  

40


2.2 Umělé neuronové sítě – aplikace v praxi Příklad 16. Pro představu, jak pracuje umělá neuronová síť, rozebereme situaci, kdy určíme např. cenu nemovitosti. Práce s umělou neuronovou sítí tedy zahrnuje proces učení umělé neuronové sítě, kdy síti poskytneme reálné vstupní i výstupní údaje o konkrétních nemovitostech. Takto naučenou síť můžeme následně využít k ohodnocení zkoumané nemovitosti, kdy na základě znalosti vstupních parametrů konkrétní nemovitosti je poskytnuto výstupní řešení (které je založeno na principu analogie s naučenými případy). Umělá neuronová síť pracuje tedy obdobně jako člověk. Výhoda spočívá v tom, že při velkém množství kritérií a množství případů člověk nemusí toto kvantum informací pojmout a správně interpretovat, popř. dojde k opomenutí nějakého kritéria nebo lidskému omylu. Vstupem pro program je matice hodnot zobrazená v tab. 17, která nám charakterizuje jednotlivé parametry konkrétní nemovitosti.

Y1 Y2 Y3 Y4 … YN-2 YN-1 YN

X1 A1,1 A2,1 A3,1 A4,1 … A N-2,1 A N-1,1 AN,1

X2 A1,2 A2,2 A3,2 A4,2 ….. A A-12,2 A A-1,2 AN,2

X3 A1,3 A2,3 A3,3 A4,3 ….. A N-2,3 A N-1,3 AN,3

….. ….. ….. ….. ….. …… ….. ….. …..

….. ….. ….. ….. ….. ….. ….. ….. …..

XM-1 A1,M-1 A2,M-1 A3,M-1 A4,M-1 ….. A N-2,M-1 A N-1,M-1 AN,M-1

XM A1,M A2,M A3,M A4,M …… A N-2,M A N-1,M AN,M

Tab. 17 Matice vstupních hodnot

V našem případě volíme v záhlaví na vodorovné ose X kritéria X1 = cena, X2 = oblast, kde se nachází nemovitost, X3 = typ nemovitosti, X4 = zda nemovitost obsahuje bazén, X5 = počet pokojů, X6 = počet dětských pokojů, X7 = vybavení nábytkem, X8 = počet podlaží, X9 = XM-1 = zastavěná plocha, X10 = XM = úroveň vnitřního vybavení nemovitosti - zařízení. V levém sloupci jsou uvedeny jednotlivé případy prodejů nemovitostí, tj. Y1, Y2, Y3, …, YN, kde N je celkový počet případů. Označíme-li u třetí nemovitosti v pořadí neznámou hodnotu ceny symbolem ? s uvedením jednotlivých konkrétních údajů o sledované nemovitosti A3,2, …, A3,M, potom spuštěním výpočtu neuronové sítě můžeme získat návrh prodejní ceny A3,1. Viz obr. 40.

41


Uvedený příklad budeme řešit komerčně prodávaným programem NeuroForecastor od firmy NIBS, Pte. Ltd. Program umožňuje načíst připravenou matici vstupních hodnot, kterou jsme popsali. Po načtení vstupních dat označíme, která kritéria jsou vstupní, a která výstupní. V našem případě bude vstupním kritériem cena nemovitosti. Dále volíme parametry umělé neuronové sítě jako je její přenosová funkce (program NeuroForecaster jich nabízí 12 Hyperbolic Tangent, Mixed Functions, Basic, Sigmoid, Hyperbolic Tanh and Sine, Competitive, Radial Basic Function, Fast Prop Hyperbolic Tangent, Fast Prop Sigmoid, Fast Prop Linear, Fast Prop Radial Basis Function, Neuro Fuzzy nebo Genetiku, která využívá genetických algoritmů k tzv. klestění sítě). Viz. obr. 41.

Obr. 40 Vstupní tabulka

42


Obr. 41 Volba vstupů, výstupů a přenosové funkce Dále se určuje počet skrytých vrstev neuronové sítě, např. 2, postačující k tvorbě složitého modelu a rozsah dat pro učení a testování. Oblast dat nad kterými bude provedeno učení a testování, se doporučuje volit odlišně. Tato skutečnost přispívá ke kvalitě naučeného modelu. Viz obr. 42.

Obr. 42 Volba dat pro učení a testování

Po těchto přípravách lze zvolit proces učení a testování, kdy sledujeme velikost chyby testování a učení, pokud je chyba malá (např. 0,1) pak proces ukončíme. Viz. obr. 43.

Obr. 43 Tabulka údajů o úspěšnosti učení a testování

43


Obr. 44 Výstupní tabulka Výsledek výpočtu je uveden na obr. 44, kde je místo symbolu ? ve sloupečku Cena u třetího řádku navržena cena 550 tisíc USD.

Příklad 17. Uvedeme si příklad využití umělé neuronové sítě pro predikci hodnot časové řady, která je tvořena vývojem kurzu měny eura EUR a dolaru USD. Postup výpočtu s programem Neuroforecaster jsme uvedli v příkladu 16, proto se zmíníme pouze o odlišnostech výpočtu, pracujeme-li s časovou řadou. Protože provádíme predikci časové řady, je nutné v programu volit TYPE TIME, vložit počet sloupců 5 do COLUMN, 1 do DATE, protože pracujeme s časem, 4 do OUTPUT, protože výstup je tvořen sloupcem 4, tj. hodnotami u kterých budeme chtít znát hodnoty predikce. Viz obr. 45. Poznámka: Časová řada kurzu měn se ve skutečnosti skládá ze čtyř řad, které jsou tvořeny hodnotami řady: Close (zavírací), Open (otvírací), High (nejvyšší) a Low (nejnižší). Po provedení procesu učení a testování lze spustit proces predikce (Forecast). Po ukončení procesu výpočtu obdržíme výsledek ve formě grafu, zobrazujícího hodnoty skutečné a predikované. Viz. obr. 46.

44


Obr. 45 Vstupní tabulka

Predikce

Obr. 46 Graf hodnot skutečných a predikce

45


Uvedeným způsobem lze provést predikci libovolné časové řady. Kvalitu predikce lze ovlivnit volbou počátku časové řady (krátká řada může být pro predikci stejně nevhodná jako dlouhá řada), volbou přenosové funkce a jejími parametry, určením rozsahu dat pro testování a učení, okamžikem ukončení procesu učení a testování, apod.

Příklad 18. Umělé neuronové sítě mají využití také v oblasti, která se nazývá data mining. Uvedeme příklad vyhodnocení míry rizikovosti klienta, která může být hodnocena škálou 0 až 100 %. Vstupem umělé neuronové sítě je matice hodnot, která nám charakterizuje jednotlivé parametry. V záhlaví matice jsou uvedena kritéria X1 = rizikovost zákazníka, X2 = pohlaví, X3 = věk, X4 = stav, X5 = počet dětí, X6 = výše příjmu, X7 = výše konta, X8 = výše dluhů, X9 = délka zaměstnání, X10 = doba kontaktu s klientem, X11 = počet nákupů, X12 = počet plateb mimo termín. Na jednotlivých řádcích jsou uvedeny jednotlivé případy klientů, tj. Y1, Y2, Y3, …, YN, kde N je celkový počet klientů. Neznáme-li a chceme-li určit riziko klienta u třetího případu, označíme jej symbolem ?. Spuštěním výpočtu neuronové sítě získáme hodnotu rizikovosti zákazníka A1,3. Viz. obr. 47.

Obr. 47 Vstupní tabulka pro výpočet rizika

46


Podrobný postup výpočtu programem Neuroforecaster byl uveden v příkladu 16. Graf hodnot rizika je na obr. 48. V průběhu grafu je mezera, která je dána chybějící hodnotou, již chceme získat výpočtem jako odhad.

Obr. 48 Nastavení rozsahu učení a testování Výsledek je zobrazen tabulkou zobrazenou na obr. 49, kde ve sloupečku Riziko u třetího řádku je místo symbolu ? vypočtena míra rizika 42 %.

Obr. 49 Výstupní tabulka pro výpočet rizika

47


2.3 Predikce časových řad programem NEURO PROJEKT Příklad 19. Pro účely predikce časových řad byl na EPI Kunovice vyvinut Ing. Petruchou. Ph.D. program s názvem NEURO PROJEKT. Postup predikce spočívá ve vytvoření vstupního souboru v textovém formátu txt např. v Poznámkovém bloku, který je součástí MS Windows. Viz tab. 18. První řádek je hlavička označující titul časové řady, druhý řádek určuje pro výpočet počet vstupů (6), počet výstupů (1), počet hodnot časové řady (85) a počet neuronů modelu (5). Další řádek odděluje data od vstupních parametrů. Dále je uvedeno deklarovaných 85 hodnot časových řad. První hodnotou je tedy 35.22 a poslední 29.24.

Casova rada - MSFT 6 -pocet vstupu 1 -pocet vzstupu 1krok predikce 85 -pocet dat casove rady 5 -pocet neuronu ve skryte vrstve **** data casove rady **** 35.22 35.37 34.38 34.61 33.45 34.44 34.33 33.91 34.39 34 33.23 33.11 33.01 31.96 31.93 33.25 32.94 32.72 32.6 32.2 32.6 30.45 30.19 29.07 28.52 28.12 28.56

48


28.21 28.34 28.96 28.5 28.42 28.17 28.22 28.1 27.68 27.84 28.38 28.26 27.93 27.2 26.99 27.59 28.12 27.57 27.87 28.05 29.28 28.63 28.62 27.96 28.3 29.42 28.62 29.18 29.17 29.14 28.56 28.05 27.91 28.38 29.5 29.16 29 29.16 29.16 28.75 28.89 29.11 28.28 28.06 28.25 28.95 29.22 30 30.42 30.25

49


31.45 31.8 29.83 28.99 28.64 28.52 29.4 29.24 Tab. 18 Vstupní hodnoty Po uložení souboru a spuštění programu pro predikci PROJECT1.exe se provede načtení pomocí menu cteni dat, kdy vybereme textový soubor msf, a tlačítkem Otevřít jej nahrajeme do programu. Viz obr. 50. Dále je možné navolit počet cyklů výpočtu (1000), přesnost v % (5%), rozsah trénovacích dat (1-65) a testovacích (10-85).

Obr. 50 Výpočet predikce

50


Dalším krokem je spuštění učení neuronové sítě pomocí menu uceni site. Po výpočtu obdržíme důležitý graf závislosti globální chyby na uceni site. Průběh by měl být exponencielně klesající a blížící se k nule. Není-li tomu tak, je možné odzkoušet změny parametru počet neuronů modelu, popř. počet vstupů (6) a/nebo, počet hodnot časové řady. Chceme-li provést predikci, provedeme to pomocí menu test site. V grafu budou vykresleny nejenom hodnoty skutečné, ale i predikované (řada je kratší o počet vstupů neuronové sítě). Čím více se křivky překrývají, tím lepší je predikce. Hodnoty jsou uvedeny ve třetím sloupečku tabulky. Tedy predikce poslední hodnoty činí 28,7341. Viz obr. 51.

Obr. 51 Výpočet predikce Chceme-li provést výpočet další predikce, následuje otevření textového souboru msf v Poznámkovém bloku, přepíšeme hodnotu časové řady 85 na 86 a doplníme predikovanou hodnotu 28.7341 za poslední hodnotu 29.24. Viz část tabulky tab. 19. Po uložení souboru opakujeme již popsaný výpočet.

51


Casova rada - MSFT 6 -pocet vstupu 1 -pocet vystupu 1krok predikce 86 -pocet dat casove rady 5 -pocet neuronu ve skryte vrstve **** data casove rady **** 35.22 35.37 34.38 34.61 ….. ….. 29.4 29.24 28.7341 Tab. 19 Vstupní hodnoty

Obr. 52 Výpočet predikce

52


Obdržíme jako další v pořadí predikci 28,8860. Viz obr. 52. Takto lze postup opakovat, dokud nedosáhneme potřebné délky predikce (např. jsou-li hodnoty uloženy po dnech, jde o predikci na 1, 2 a více dní). Nedoporučuje se více predikcí než 1/5 celkového počtu hodnot. Počet hodnot časové řady by měl být co největší, minimálně 20, z důvodu potřeby neuronové sítě naučit se na vzorech.

Závěr: Je nutné upozornit, že kvalitu naučené sítě je třeba testovat před použitím, protože záleží nejen na kvalitě vstupních dat, ale i na navolení parametrů umělé neuronové sítě, např. typu přenosové funkce, topologie sítě, počet vstupů, atd. Hovoříme o tzv. ladění neuronové sítě, která je nejsložitější a nejdůležitější částí uvedení aplikace do praxe. U uvedených příkladů je zřejmá výhoda neuronových sítí, kdy velké množství případů a charakteristik není jednoduché pro člověka vyhodnocovat, popř. neopomenout vzít je v úvahu.

53


3 GENETICKÉ ALGORITMY Genetické algoritmy se používají tam, kde přesné řešení úloh z praxe by systematickým prozkoumáváním trvalo téměř nekonečně dlouho. Umožňují tak řešit složité problémy velmi elegantně. Genetické procesy v přírodě odhalil v 19. stol. Mendel a rozvinul Charles Darwin. Počítačová realizace genetických algoritmů se začala objevovat v 70. letech 20. století a je spojena se jmény J. Hollanda a D. Goldberga. Teprve v nedávné době lze pozorovat značné rozšíření aplikací genetických algoritmů do oblastí řízení firem. V evolučním vývoji nebo při šlechtění rostlin či živočichů se prosazují jedinci, kteří mají jisté žádoucí charakteristiky, které jsou na genetické úrovni determinovány kombinováním rodičovských chromozomů. U zrodu genetických algoritmů stála myšlenka, že při hledání lepších řešení složitých problémů by bylo možno obdobným způsobem kombinovat části existujících řešení.

3.1 Genetické algoritmy - teorie Uveďme zde několik pojmů z genetiky, které se objevují i v terminologii genetických algoritmů. Chromozóm se skládá ze sekvenčně uspořádaných genů. Každý gen řídí dědičnost jednoho nebo několika znaků a jeho pozice v chromozómu má název locus. Chromozóm představuje tzv. genotyp a jeho význam, tj. informace zakódovaná v chromozómu, má název fenotyp. Většina implementací genetických algoritmů pracuje s původní reprezentací chromozomu pomocí nul a jedniček, tj. s binární reprezentací. V tomto případě jsou chromozomy představovány binárními řetězci, např. 01100110. Tyto binární řetězce většinou představují zakódovaná dekadická čísla – parametry optimalizované funkce. Schéma je tedy řetězec, v němž se alespoň na jedné pozici vyskytuje povolený symbol (v případě binární reprezentace je to 0 nebo 1). Pro manipulace s chromozómy bylo navrženo několik genetických operátorů. Nejčastěji používanými operátory jsou selekce (selection), křížení (crossover) a mutace (mutation).

Při selekci se jedná o výběr chromozómů, které se stanou rodiči. Důležitým hlediskem, jež se přímo čí nepřímo uplatňuje při výběru alespoň jednoho z rodičů, je jeho „zdatnost“ (fitness). Tuto, tzv. selekci, ukazuje příklad, kdy číslo 122 (binárně 01111010) je

54


větší jak 34 (binárně 00100010), proto chromozom 01111010 přejde do další generace. Viz tab. 20. 01111010 122

> 00100010 > 34

Tab. 20 Selekce Křížení představuje výměnu částí dvou čí více rodičovských chromozómů, které způsobuje modifikaci chromozómů, při němž vzniká jeden nebo více potomků. Toto tzv. jednobodové křížení je ukázáno v tab. 21. Rodiče 011|0010 011|1001

potomci 0111001 0110010

Tab. 21 Křížení Uvedené křížení může být zdokonaleno vybíráním takových bodů křížení, které zajistí, že potomci budou odlišní od rodičů. Z řady dalších modifikací operace křížení zde ještě uveďme vícebodové křížení, při němž se generuje několik dělicích bodů a zobecněné křížení (zvané též uniformní), které se uskutečňuje pomocí vzoru z nul a jedniček, generovaného opakovaným užitím alternativního rozdělení.

Mutace představuje modifikaci chromozómu, při níž dojde k náhodné změně. Tato činnost se v přírodě vyskytuje zřídka. Mutace je znázorněna v tab. 22.

před 0110010

po 0010110

Tab. 22 Mutace Genetické algoritmy pracují tím způsobem, že se nejprve vytvoří počáteční populace m chromozómů, a potom se tato populace mění pomocí genetických operátorů tak dlouho, dokud není proces ukončen, např. počtem cyklů (generací). Viz obr. 53.

55


Selekce

Inicializace

Křížení

Mutace

Ne Kone c? Ano Ukončení

Obr. 53 Proces reprodukce Proces reprodukce, který se opakuje, se nazývá epochou evoluce populace (jednou generací) a představuje uvedené tři kroky: selekce, křížení a mutace.

Počáteční populace se obvykle získá náhodným generováním. Byly provedeny také pokusy nasadit do počáteční populace kvalitní řešení, získaná jinými heuristickými technikami a pomoci tak genetickému algoritmu dospět rychleji k lepšímu řešení. Při tomto způsobu se však zvyšuje nebezpečí předčasné konvergence do nějakého, ještě ne dost dobrého lokálního optima. Pokud jde o velikost populace, je jasné, že příliš malá populace může zavinit špatné pokrytí prostoru řešení, zatímco příliš velká populace zvyšuje výpočetní náročnost. Experimentální práce naznačují, že v mnoha případech je dostačující velikost populace kolem 100, resp. mezi n a 2n, kde n je délka binárního řetězce.

Jednou z možností změny m-členné populace je vygenerovat pomocí křížení a mutace novou generaci m potomků a nahradit rodičovskou generaci an bloc. Jiné způsoby umožňují nějaké překrývání populace rodičů a potomků. Např. vygenerovaný potomek nahrazuje náhodně vybraného příslušníka aktuální populace. Při řešení optimalizačních problémů se objevuje požadavek, aby nejlepší člen aktuální populace se objevil i v populaci nové. To je možno zajistit např. tak, že nový chromozóm nahrazuje jedince náhodně vybraného z těch, kteří mají podprůměrnou kvalitu.

56


Při aplikaci genetických algoritmů na problémy řízení firem (resp. nevratného rozhodování), každý chromozóm kóduje nějaké řešení problému (tedy chromozóm je genotyp a odpovídající řešení je fenotyp) a jeho fitness je kladná hodnota, která nějakým způsobem odpovídá hodnotě účelové funkce v tomto řešení. V genetických algoritmech jsou preferovány chromozómy s vyšší hodnotou fitness. Fitness funkce musí být konstruovaná tak, že její hodnota je tím vyšší, čím lepší je hodnota účelové funkce.

Příklad 20. Na jednoduchém příkladu s použitím populace o čtyřech členech a čtyřbitovém chromozómu uvedeme, jak pracují genetické algoritmy. Viz tab. 23. Při inicializaci, kdy volíme chromozómy s dekadickými hodnotami 8, 4, 2, 1, nabývá účelová funkce (suma hodnot Xi(10)) hodnoty 15. Prvním krokem první generace (populace) je selekce, kdy nejsilnější chromozóm s dekadickou hodnotou 8 je dvakrát zopakován a nejslabší chromozóm s hodnotou 1 vypadá z tabulky. Dále dojde ke křížení mezi (chromozómy) x1 a x3 od 2. pozice (bitu) vlevo včetně a mezi x2 a x4 od 3. pozice vlevo včetně, mutace se neprovede u žádného bitu žádného chromozómu. V druhé populaci, kdy hodnota účelové funkce nabývá hodnoty 22 (což je 47 % zlepšení), dojde nejdříve k selekci, kdy nejsilnější chromozóm s dekadickou hodnotou 12 je dvakrát zopakován a nejslabší chromozom s dekadickou hodnotou 0 vypadá z tabulky. Dále dojde ke křížení mezi x1a x3 od 3. pozice vlevo včetně a mezi x2 a x4 od 4. pozice vlevo včetně, mutace se provede u x4 v 2. pozici vlevo. Po ukončení druhé generace je suma hodnoty účelové funkce rovna 38 (což je zlepšení o 153 % proti počáteční hodnotě účelové funkce). Takto je možné pokračovat dalšími populacemi, kdy v praxi nalézáme stále lepší řešení. Inicializace i 1 2 3 4

První generace

Druhá generace

Xi(10) 8 4 2

Xi(2) 1000 0100 0010

Po selekci 1/000 10/00 0/100

K 2 3 2

Po křížení 1/100 10/10 0/000

M 0 0 0

Po mutaci x'i(2) 1100 1010 0000

1

0001

00/10

3

00/00

0

0000

15

x' i(10) 12 10 0

Po selekci 11/00 110/0 10/10

K 3 4 3

Po křížení 11/10 110/0 10/00

M 0 0 0

Po mutaci x''i(2) 1110 1100 1000

0

000/0

4

000/0

2

0100

22

x'' i(10) 14 12 8 4 38

Tab. 23 Výpočet genetickým algoritmem Pro řešení úloh z praxe použijeme komerčně prodávaný program GeneHunter od firmy Ward Systems Group. Ostatní programy pracují podobným způsobem a liší se jen uživatelským prostředím. Program pracuje s tabulkou v prostředí programu Excel. Máme-li vyplněnou tabulku, postup kroků je následující:

57


a) Je nutné určit účelovou funkci, tj. rovnici, kterou budeme optimalizovat na maximum, respektive minimum, respektive určitou hodnotu. b) Je nutné určit hodnoty, které mají být optimalizovány. c) Je nutné určit typ chromozómů, který záleží na typu úlohy. Jde-li o spojitý problém (racionální čísla) nebo problém v rámci celých (integer) čísel, používá se typ chromozómu continuous, pokud jde o úlohy typu obchodního cestujícího nebo optimalizace portfolia, jde o typ chromozómu enumerated. d) Dále se volí omezení optimalizovaných hodnot, a to rozsahy, podmínkami a funkcemi. Omezení rozsahem znamená, že optimalizovaná buňka je limitována rozsahem. Omezení podmínkou znamená, že hodnota v buňce má být menší, větší nebo rovná jiné hodnotě v buňce nebo konkrétní hodnotě se zvolenou tolerancí. Omezení funkcí znamená, že kromě hlavní účelové funkce lze použít další podružné funkce, které budeme optimalizovat na maximum, respektive minimum, respektive určitou hodnotu. Poznámka: Je zřejmé, že pokud podmínky „neuhlídáme“ a zadáme je chybně, pak řešení nebude existovat nebo bude chybné. Např. zadáme-li chybnou podmínku ve tvaru, že proměnná má být větší jak 50 a zároveň menší jak –50. e) Dále se volí další důležité hodnoty pro nastavení optimalizace, a to: • Population size - určuje počet populací, které bude program používat při výpočtu. V příkladu 20 to byly čtyři členové populace. Při běžném výpočtu volíme hodnotu Population size 100 členů. • Chromozome length - určuje délku chromozómu, který bude program používat při výpočtu. V příkladu 20 to byly čtyři chromozómy. Při běžném výpočtu volíme délku chromozómu 8, 16 nebo 32. Větší hodnota dává lepší výsledek, ale proces se zpomaluje. • Crossover rate - značí četnost křížení, tj. jak často při výpočtu dochází ke křížení (rozsah je 0 až 1). V běžném výpočtu se volí vysoká hodnota, např. 0,9. • Mutation rate značí četnost mutace, tj. jak často při výpočtu dochází k procesu mutace (rozsah je 0 až 1). V běžném výpočtu se volí nízká hodnota, např. 0,01. • Generation gap - značí četnost populace, která nepřechází do další generace bez mutace a křížení (rozsah je 0 až 1). V běžném výpočtu se volí vysoká hodnota, např. 0,98. Volba parametrů pro program pro optimalizaci je ukázána na obr. 54.

58


Obr. 54 Volba parametrů pro optimalizaci

3.2 Genetické algoritmy – aplikace v praxi Příklad 21. Jako první uvedeme velmi jednoduchý problém. Pro výrobu desetilitrových plechovek budeme chtít určit poloměr plechovky r a její výšku v tak, aby spotřeba materiálu byla minimální. Tento úkol vyřešíme pomocí programu takovým způsobem, že program mění poloměr r a výšku v tak, aby povrch válce P byl minimální při zachování objemu V. Pro objem válce platí vzorec V = πr2v a pro povrch P = 2πr2 + 2πrv. Tyto vzorce zapíšeme do buněk programu Excel. Viz tab. 24. B

C Výška V 0

D Poloměr R 0

6

Povrch

P

=2*3.1415*D4*C4+2*3.1415*D4*D4

7

Objem

V

=3.1415*D4*D4*C4

2 3 4 5

Tab. 24 Tabulka závislosti vzorců V Excelu tedy máme výraz pro povrch v buňce D6 a pro objem v buňce D7. Hodnotu výšky v buňce C4 nastavíme na 0 a poloměr r v buňce D4 také na 0. Viz obr. 55.

59


Obr. 55 Tabulka před výpočtem Po spuštění programu GeneHunter se zobrazí okno (viz obr. 56.), kde navolíme údaje nezbytné pro výpočet.


V našem případě je účelová funkce rovnice pro povrch P, která se nachází v buňce D6. Hledáme minimum této funkce, proto volíme Search for Min. Hodnoty, které program mění, jsou výška v a poloměr r, které se nacházejí v buňce C4 a D4. Typ chromozómu Chromozome type volíme Continuous, protože výška v a poloměr r jsou čísla reálná. Dále volíme omezení

60


maximálního a minimálního poloměru r a výšky v, která je dána nerovnicemi 0,5 <= v <= 4 a 0,1 <= r <= 2. Tato podmínka se zapíše ve volbě Show list of ranges kliknutím na tlačítko Add. Protože výška v, která je umístěna v buňce C4, má být menší jak 4, provedeme vyplnění tabulky, tak jak je to patrné na obr. 57.

Obr. 57 Tvorba podmínek pro výpočet optimalizace

Tuto činnost opakujeme pro všechny podmínky. Viz obr. 58.

Obr. 58 Omezující podmínky pro výšku v a poloměr r

Poslední podmínkou je, že objem nádoby má být deset litrů. Tuto podmínku stanovíme s vysokou mírou platnosti (splnění) s toleranci + 0,01. Tato podmínka se zapíše ve volbě Show list of constraints vyplněním tabulky, tak jak je to patrné na obr. 59. Objem V se nachází v buňce D7.


61


Navolená podmínka pro objem V je zobrazena na obr. 60.

Obr. 60 Omezující podmínka pro objem V Dále se provede navolení podmínek pro výpočet, kdy využijeme menu pro volby Options. Počet populace volíme střední velikosti, tj. Population size = 100, délku chromozómu zvolíme také střední, tj. Chromozome length = 16-bit, parametr křížení, tj. Crossover rate = 0,9, parametr mutace, tj. Mutation rate = 0,01, parametr přechodu jedinců populace do další generace, tj. Generation gap = 0,98. Dále navolíme použití strategie elit Elitist strategy a diversifikační operátor Diversity operator. Obnovu obrazovky při výpočtu volíme občasnou, tj. Screen diversity = Smart. Ukončení programu můžeme navolit podmínkou, nedojde-li ke změně populace po dobu 75 generací, program se ukončí. Viz obr. 61.


62


Máme-li nastaveny všechny parametry výpočtu (viz obr. 61), spustíme výpočet, který se po několika minutách ukončí. Výsledek optimalizace je patrný z obr. 62. Zvolíme-li výšku v = 2,34 dm a poloměr r = 1,14 dm, bude objem V = 10,01 litrů a minimalizovaný povrch bude činit P = 25,72 dm2.

Obr. 62 Tabulka po výpočtu Význam optimalizace je zde zřejmý. Další příklady již nebudeme rozebírat tak detailně.

Příklad 22. Velmi častou úlohou je aproximace naměřených bodů polynomem. Tuto úlohu můžeme řešit regresní analýzou, lze použít i genetických algoritmů. Máme naměřeny hodnoty dané tabulkou 25.

xi

yi

xi

yi

xi

yi

1

2,00

6

11,45 11 39,41

2

2, 91 7

15,56 12 47,22

3

3,56

8

20,41 13 55,77

4

5,45

9

26,00 14 65,06

5

8,08

10 32,30 15 75,09

Tab. 25 Tabulka naměřených hodnot Tyto naměřené body budeme chtít proložit polynomem 2. stupně tvaru y(x) = a2x2 + a1x +a0. Způsob zadání je obdobné příkladu 21. Účelová funkce, kterou budeme minimalizovat, je

63


součet kvadrátů odchylek hodnot naměřených a vypočtených polynomem. Měněné hodnoty jsou a2, a1, a a0. Po ukončení výpočtu dostaneme hodnoty viz tab. 26.

a2 a1 a0 0,376 0,699 2,334 Tab. 26 Hodnoty konstant

Dosadíme-li získané konstanty do polynomu, má tvar

y(x) = 0,376x2 – 0,699x + 2,334.

Tab. 27 zobrazuje skutečné hodnoty a hodnoty vypočtené polynomem. Obr. 63 zobrazuje graf těchto skutečných hodnot a hodnot vypočtených polynomem. Překrytí těchto křivek je důkazem o správnosti výpočtu konstant polynomu. Hodnota účelové funkce (suma kvadrátů odchylek) je 16,88.

Pořadí 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Skutečnost 2 2,91 3,56 5,45 8,08 11,45 15,56 20,41 26,00 32,30 39,41 47,22 55,77 65,06 75,09

Polynom 4,95 2,77 2,77 4,30 7,03 10,74 15,31 20,62 26,60 33,20 40,35 48,03 56,19 64,80 73,85

Tab. 27 Hodnoty naměřené a získané z polynomu

64


80 70 60 50 40 30 20 10 0

Obr. 63 Graf průběhu hodnot

Příklad 23. Genetických algoritmů lze použít pro řešení jednoduchých neuronových sítí (např. viz obr. 64). V kapitole o neuronových sítích byla zmínka, že učící se proces umělé neuronové sítě lze interpretovat jako optimalizační úlohu s účelovou funkcí E, definovanou v hyperprostoru, při které se hledá její minimum. Pokud sestavíme tabulku, obsahující vstupní, výstupní hodnoty a hodnoty vah (viz tab. 27) umělé neuronové sítě s odpovídajícími vzorci, lze spustit optimalizaci, která nastaví váhové koeficienty umělé neuronové sítě za pomoci genetických algoritmů. Účelová funkce, kterou budeme minimalizovat, je výpočet chyby E, kterou definujeme vzorcem

E = Σ (ni - oi )2,

kde ni je i-tá hodnota na výstupu a oi je i-tá očekávaná hodnota. Měněné hodnoty jsou w11,1, w11,2, w12,1, w12,2, b11, b12, w21,1, w22,1, b21. Umělá neuronová síť je učena na vstupních hodnotách p1,k a p2,k s výstupem O1,k. Z obr. 64 je patrné, že je-li vstupem dvojice 1,1 (0,0), je výstupem 1 (0). Pro výpočet je použito přenosové funkce tansig, jehož výstup je v intervalu (1, 1). Smyslem použití transformace je modifikace úrovně výstupů na normované hodnoty.

65


vstupní vrstva

skrytá vrstva

výstupní vrstva a

w11,1

1

p1

p2

w11,2

w21,1

w12,1

w22,1 w12,2

a1 b

1

b

1

a2

b 21

1 2

Obr. 64 Typologie neuronové sítě Výsledkem optimalizace je nastavení vah w11,1, w11,2, w12,1, w12,2, b11, b12, w21,1, w22,1, b21 tak, aby síť byla naučená a dávala správné výsledky na výstupu po zadání vstupních hodnot. V tomto jednoduchém příkladu bylo dosaženo nulové hodnoty chyby E. Viz tab. 28.

i 1 2 3 4

p1,k 1 0 0 1

p2,k 1 0 0 1

o1,k 1 0 0 1

w11,1 w12,1 b 11

-0.984 -0.090 0.812

w11,2 w12,2 b 12

-0.835 -0.796 0.663

a11,k -0.26 0.67 0.67 -0.26

a12,k -0.75 0.58 0.58 -0.75

a21,k 1.00 -1.00 -1.00 1.00

n1,k 1.00 0.00 0.00 1.00 E w21,1 w22,1 b 21

E1,k 0.00 0.00 0.00 0.00 0.00 -0.906 -0.875 0.114

Tab. 28 Zadané a vypočtené hodnoty Nemáme-li tedy k dispozici program pro řešení umělých neuronových sítí, lze si vypomoci programem GeneHunter pro optimalizaci, kdy se minimalizuje chyba E. Z uvedené ukázky, kdy jsme měli jen 5 neuronů, je patrné, že realizace složitější umělé neuronové sítě s větším počtem neuronů by byla pomocí genetických algoritmů velmi pracná.

Příklad 24. Genetických algoritmů

lze použít pro stanovení optima výroby. Na

ukázku uvedeme následující příklad. 66


Máme vyrobit 12 výrobků, z toho 5 výrobků typu A, 3 výrobky typu B, 2 výrobky typu C, 1 typ výrobku D a E. K výrobě je potřeba 6 různých pracovišť. Doba ke zpracování různých typů výrobků na různých pracovištích je různá a je dána křížovou tab. 29 vpravo nahoře. Počet strojů na pracovištích je určen tab. 29 uprostřed dole. Pokud bychom výrobky zadávali libovolně, např. tak jak je to uvedeno v tab. 29 uprostřed, od čísla 1 po číslo 12, potřebný čas na zpracování všech výrobků, které by byly zadávány do výroby v uvedeném pořadí, by činil 13 hodin 54 minut. Volit lze jak počet strojů na jednotlivých pracovištích, tak dobu zpracování různých výrobků na různých pracovištích.

Plánování výroby: Číslo výrobku

Typ výrobku

1 2 3 4 5 6 7 8 9 10 11 12

A B C D E A B C A A A A Celkový čas:

Pořadí výrobku Výchozí - stav - konečný

1 2 3 4 5 6 7 8 9 10 11 12 13:54

První

Poslední

3 8 5 4 7 1 6 11 2 9 10 12 12:00

Číslo pracoviště

A

B

C

D

E

1 2 3 4 5 6

0,1 0,2 0,3 0,4 0,3 0,2

0,2 0,3 0,4 0,3 0,2 0,1

1,5 2 2,5 2 1,5 1

0,7 0,6 0,5 0,4 0,8 0,3

0,6 0,3 0,4 0,5 5 0,8

Číslo pracoviště

Počet strojů

1

1 2 3 4 5 2

2 3 4 5 6

Tab. 29 Optimalizace plánování výroby Účelová funkce, kterou budeme minimalizovat, je celková doba výroby všech výrobků. Měněnými hodnotami je pořadí výrobků vstupujících do výroby, které je nastaveno na počátku v pořadí 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Provedeme-li výpočet optimalizace programem GeneHunter, je určeno pořadí výrobků řazených do technologického procesu tak, aby čas výroby všech výrobků byl minimální. Po skončení procesu optimalizace jsme obdrželi výsledek, že v případě řazení výrobků do výroby v pořadí 3, 8, 5, 4, 7, 1, 6, 11, 2, 9, 10, 12, bude celkový čas výroby 12 hodin, tedy čas téměř o dvě hodiny kratší. Viz tab. 29 uprostřed. Takto lze optimalizovat výrobní proces, snížit náklady, popř. zvýšit zisk ve výrobě.

67


Příklad 25. Genetických algoritmů

lze použít při úloze dělení materiálu, tzn.

stanovení řezných plánů. Úloha může být řešena pro materiál jedno, dvou i tří dimenzionální. Optimalizace tohoto problému umožňuje minimalizovat odpad. Řešení řezného plánu u jednorozměrné úlohy lze ukázat na následujícím případě. Na skladě máme zásoby různých délek potrubí (kulatiny, prutů, atd.), např. 10 kusů délky 4 m a 20 kusů délky 5 m. Požadujeme 9 kusů potrubí délky 1 m, 14 kusů délky 2 m a 20 kusů délky 3 m, přičemž chceme nalézt variantu, která zajistí nulové nebo minimální množství odpadu. Cílem je tedy určení počtu a velikosti trubek a určení způsobu jejich rozřezání. Pro řešení je nutné určit možné varianty rozřezání trubek, které jsou k dispozici na skladě. Řezné varianty můžeme omezit například počtem trubek ve skladu. Účelová funkce, kterou budeme minimalizovat, je odpad. Měněné hodnoty jsou počty kusů, které mají být nařezány u jednotlivých řezných variant (viz tab. 30), kde tabulka nalevo zobrazuje jednotlivé řezné plány. Počáteční stav je dán nulovými počty kusů, které mají být nařezány u jednotlivých řezných variant. Po ukončení výpočtu optimalizace obdržíme výsledek ve formě počtu kusů, které mají být nařezány u jednotlivých řezných variant. Viz tab. 30 vpravo. Náš případ je vyřešen potřebou 3 kusů trubek délky 4 m (tyto 3 kusy budou rozřezány po 1 jednometrovém kusu a 1 třímetrovém kusu) a 17 kusů trubek délky 5 m (3 kusy budou rozřezány po 2 jednometrových kusech a 1 třímetrovém kuse, 14 kusů bude rozřezáno po 1 dvoumetrovém kuse a po 1 třímetrovém kuse).

Tabulka dole zobrazuje výsledek optimalizace, kdy je určen počet potřebných trubek dostupných ve skladu (je kontrolováno maximální množství materiálu na skladě), splnění podmínky minimálního odpadu a kontrola správného množství nařezaného materiálu (není-li přebytek). Vypočtený řezný plán nemusí splňovat požadavek, že odpad bude nulový a počet nařezaných trubek bude přesně požadovaný, ale řešení se bude tomuto požadavku přibližovat. Neúplné splnění požadavků může být dáno neexistencí řešení problému nebo skutečností, že algoritmus nenalezne nejlepší řešení. Nalezení co možná nejlepšího řešení můžeme realizovat opakováním procesu optimalizace s různě nastavenými parametry optimalizačního algoritmu, např. velikostí populace, délkou chromozómů, parametrem křížení, parametrem mutace, parametrem přechodu generace, apod.

68


Varianta

1m

4a

4

2m

4b

3

4c

2

1

4d

1

1

4e

1

5a

5

5b

4

5c

3

1

5d

2

1

5e

2

5f

1

5g

1

Varianta:

ks.

1m

2m

3m

4a

0 0 0 0

0

0

0

0

0

0

0

0

0

0

0

0

3 0

3

0

3

0

0

0

0 0

0

0

0

0

0

0

0 3 0 0

0

0

0

6

0

3

0

0

0

0

0

0

0

0

0

5i

0 14

0

14

14

Délka:

1m

2m

3m

4b 4c

1

4d

1

4e 5a 1

5b 5c

1

5d

1

5e

2

5f 1

2

5i

1

0

Zbytek 1

5h

Odpad:

3m

1

5g

1

5h

1

Díly 4m:

3

10

Skutečnost:

9

14

20

Díly 5m:

17

20

Požadavek:

9

14

20

Skut.

Sklad

Přebytek(+):

0

0

0

Tvary: 1m 2m 3m Materiál: 4m 5m

Tab. 30 Řezný plán – jednorozměrná úloha Poznámka: Úlohu je možné řešit též formou lineárního programování.

Příklad 26. Obdobnou úlohou, jako příklad 25, je řezný plán u dvourozměrné úlohy. Na skladě máme zásoby plechů různých rozměrů, např. 10 kusů plechů rozměru 2x2 m2 a 20 kusů plechů rozměru 2x3 m2. Požadavek je na 20 kusů plechů rozměrů 1x1 m2, 15 kusů plechů rozměru 1x2 m2 a 10 kusů plechů rozměru 1x3 m2. Podmínkou, respektive účelovou funkcí je nalezení varianty, která zajistí nulové nebo minimální množství odpadu. Cílem je tedy určení počtu a velikosti plechů potřebných ze skladu a určení způsobu jejich rozřezání. Pro řešení je nutné určit možné varianty rozřezání plechů, které jsou k dispozici ve skladě. Tab. 31 nalevo ukazuje možné varianty rozřezání plechů. Tabulka napravo zobrazuje výsledek optimalizace, kdy je určeno kolikrát a které řezné varianty má být použito (počáteční stav byl 0). Tabulka dole zobrazuje splnění nulového nebo minimálního odpadu, počet potřebných kusů plechů a stav na skladě, počet a typ požadovaných rozměrů a skutečnost, které dosáhneme použitím optimalizovaného řezného plánu. Pro vypočtený řezný plán a splnění podmínek platí stejné poznatky jako u jednorozměrné úlohy.

69


Varianta:

1x1

(2x2)a

4

(2x2)b

3

(2x2)c

2

(2x2)d

1

(2x2)e

1x2

Zbytek 1

1 1

1

6

(2x3)b (2x3)c

5 4

1

(2x3)d

3

1

(2x3)e

2

2

(2x3)f

1

2

(2x3)g

3

(2x3)h

2

(2x3)i

1x1

1x2

1x3

(2x2)a

0

0

0

0

(2x2)b

0

0

0

0

(2x2)c

0

0

0

0

1

1

1

0

0

0

0

0

(2x3)a

1

6

0

0

1

(2x3)b (2x3)c

0 0

0 0

0 0

0 0

1

(2x3)d

0

0

0

0

(2x3)e

7

14

14

0

(2x3)f

0

0

0

0

(2x3)g

0

0

0

0

(2x3)h

0

0

0

0

(2x3)i

5

0

0

10

1

2

0

ks.

(2x2)d

1 1

Varianta:

(2x2)e

2

(2x3)a

Odpad:

1x3

Rozměr:

1x1

1x2

1x3

(2x2)

1

10

Skutečnost:

21

15

10

(2x3)

13

20

Požadavek:

20

15

10

Skut.

Sklad

Přebytek(+):

1

0

0

Tvary: 1x1 1x2 1x3 Materiál:

2x2

2x3

Tab. 31 Řezný plán – dvourozměrná úloha

Popíšeme-li stav po optimalizaci, zjistíme, že je splněn požadavek nulového odpadu, ale jeden plech o rozměru 1x1 m2 bude navíc. Náš případ je tedy vyřešen nařezáním 1 kusu plechu rozměru 2x2 m2 (tento 1 plech bude rozřezán po 1 kusu rozměru 1x1 m2 a po 1 kusu rozměru 1x2 m2, 1 kus rozměru 1x1 m2 bude navíc) a 13 kusů plechu rozměru 2x3 m2 (1 plech bude rozřezán po 6 kusech rozměru 1x1 m2, 7 kusů plechu bude rozřezáno po 2 kusech rozměru 1x1 m2 a po 2 kusech rozměru 1x2 m2, 5 kusů plechu bude rozřezáno po 2 kusech rozměru 1x3 m2).

Příklad 27. Genetických algoritmů lze využít při shlukové analýze, tedy klastrování. Jedná se o způsob, kdy se snažíme rozdělit data do oblastí (shluků, klastrů) a nalézt jejich středy. Vstupem může být libovolný počet vektorů o libovolném počtu hodnot a lze zvolit libovolný počet oblastí. Úloha může být vícedimenzionální. Jako příklad bude uvedena dvoudimenzionální úloha, řešící svoz odpadu, prezentovaná tab. 32.

70


Číslo místa odvozu

X ….. 25.00 16.00 111.00 66.80 20.40 120.00 56.80 59.90 …..

….. 22 23 24 25 26 27 28 29 ….. Tab. 32

Souřadnice místa odvozu

Přiřazení místa svozu

Y ….. 4.19 2.62 16.79 10.10 4.10 17.01 5.69 10.80 …..

A A C B A C B B …...

Shluková analýza – část vstupní tabulky

Místo svozu A B C

Souřadnice místa svozu X Y 18.4 3.1 59.8 9.0 106.8 15.9

Tab. 33 Souřadnice míst svozu

Vstupem jsou souřadnice míst odvozu X a Y, uvedené ve 2. a 3. sloupci levé části tab. 32. Účelová funkce, která se minimalizuje, je součet vzdáleností mezi místy odvozu a svozu. Měněné hodnoty jsou souřadnice X, Y míst svozu A, B, C a přiřazení míst svozu A, B, C k místům odvozu. Po ukončení procesu optimalizace dojde na základě zadaných souřadnic míst odvozu a zvoleného počtu (např. tří míst svozu A, B, C) k rozdělení míst odvozu do tří oblastí a určení souřadnic místa svozu tak, aby vzdálenosti mezi místy odvozu a svozu byly minimální. Výstupem jsou tedy nejen souřadnice tří míst svozu, vyhovující podmínce optimálnosti (viz tab. 33), ale i přiřazení příslušných míst odvozu k místu svozu (viz pravý sloupec v tab. 32). Obr. 65 reprezentuje grafickou realizaci uvedeného příkladu. (Příklad byl uveden s ilustrativními souřadnicemi, v praxi však souřadnice míst odvozu jsou více rozptýleny.)

71


20 C

15 B

10 A

5

0 0

20

40

60

80

100

120

Obr. 65 Místa odvozu a svozu A,B,C Poznámka: Lze najít mnoho variant využití shlukové analýzy v ekonomice, jednou z nich může být predikce finanční krize firmy. Lze vytvořit shluky, které budou představovat malou, střední nebo vysokou míru možnosti finanční krize firmy. Při zkoumání nové firmy lze výpočtem zjistit, do které oblasti firma patří a tím zjistit její míru možnosti finanční krize. Důležitým faktorem při použití shlukové analýzy je určení správných znaků pro tuto analýzu.

Příklad 28. Další ukázkou použití genetických algoritmů je řešení úlohy obchodního cestujícího. Tato úloha spočívá v nalezení součtu nejkratších cest, při podmínce návštěvy všech zadaných míst pouze jednou. Řešení této úlohy se stává téměř nerealizovatelným i pro počítač v případě většího počtu míst, pokud bychom zkoumali všechny varianty. Použití genetických algoritmů u této úlohy zkracuje dobu potřebnou pro výpočet.

Jako příklad uvedeme případ měst v ČR, uvedených v tabulce 34. Vstupem je uvedená křížová tabulka se vzdálenostmi mezi všemi městy (jak je to uváděno v automapách), které se mají navštívit. Genetický algoritmus provádí optimalizaci tak, aby ujetá celková trasa byla co nejkratší, při zachování podmínky, že každé město má být navštíveno jednou. Výsledkem je tedy doporučené navštívení měst v takovém pořadí, aby celková ujetá trasa byla minimální.

72


Účelová funkce, která se minimalizuje, je celková délka trasy ujetá mezi městy. Měněnými hodnotami je pořadí měst, jak mají být navštíveny. Před výpočtem je nutné nastavit inicializační hodnoty pořadí měst, které je libovolné. V našem případě jsme inicializační hodnoty nastavili podle velikosti počtu obyvatel od 1 do 12. (Viz tab. 34, první sloupeček vlevo.) Délka ujeté trasy by v tomto případě byla 3959 km. Genetický algoritmus nalezl nejkratší celkovou trasu ve variantě navštívení měst v pořadí 6, 9, 1, 12, 14, 4, 8, 15, 2, 11, 3, 13, 5, 10, 7 s celkovou délkou 1342 km. (Viz tab. 34, druhý sloupeček vlevo.) Došlo tedy o zkrácení trasy o 2617 km, tedy o 66%.

Před opt.

Po opt.

Město

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

6

Praha

0

202

362

94

275

102

112

140

92

104

297

31

349

133

123

2

9

Brno

202

0

165

296

78

239

142

186

294

138

100

233

152

335

93

3

1

Ostrava

362

165

0

456

93

335

240

346

454

240

104

393

35

495

253

4

12

Plzeň

94

296

456

0

369

196

206

133

146

198

391

87

443

83

186

5

14

Olomouc

275

78

93

369

0

246

149

259

367

147

63

306

74

408

166

6

4

Liberec

102

239

335

196

246

0

97

242

92

118

309

133

300

205

185

7

8

Hrad. Králové

112

142

240

206

149

97

0

217

166

21

212

143

205

245

110

8

15

Č. Budějovice

140

186

346

133

259

242

217

0

232

196

281

166

333

216

126

9

2

Ústí n Labem

92

294

454

146

367

92

166

232

0

196

389

81

369

122

215

10

11

Pardubice

104

138

240

198

147

118

21

196

196

0

210

135

210

237

89

11

3

Zlín

297

100

104

391

63

309

212

281

389

210

0

328

111

430

188

12

13

Kladno

31

233

393

87

306

133

143

166

81

135

328

0

380

114

154

13

5

Opava

349

152

35

443

74

300

205

333

369

210

111

380

0

482

240

14

10

Karlovy Vary

133

335

495

83

408

205

245

216

122

237

430

114

482

0

256

15

7

Jihlava

123

93

253

186

166

185

110

126

215

89

188

154

240

256

0

Tab. 34 Obchodní cestující – křížová tabulka vzdáleností měst

Pokud zobrazíme trasu mezi městy v ČR v grafu, pak obdržíme obr. 66a pro variantu s inicializačními hodnotami před optimalizací a obr. 66b pro variantu po optimalizaci.

73


Trasa po ČR

Trasa po ČR

Obr. 66a Řešení úlohy obchodního cestujícího Obr. 66b

Uvedená úloha se velmi často objevuje v praxi při řešení dopravní obslužnosti měst, oblastí, krajů, svozu nebo rozvozu pošty, materiálu, odpadů, atd.

Značné množství úloh, které jsou řešeny v praxi při manažerském rozhodování, je oblast využívající kvantitativních metod. Mnohé úlohy vedou na řešení úloh lineárního programování, kdy při optimalizaci můžeme využít výhod genetických algoritmů. Optimalizace se provádí buď za účelem nalezení maximálního zisku nebo minimálních nákladů. Oba příklady uvedeme s použitím programu GeneHunter.

Příklad 29. Uveďme situaci, kdy strojírenský závod vyrábí čtyři výrobky V1, V2, V3, V4. Při sestavování výrobního programu je třeba počítat s omezenou kapacitou výrobního zařízení, které je 1 200 hodin a s omezeným množstvím suroviny S, které je 1 400 tun. Výrobky V1 a V2 jsou polotovary potřebné pro výrobu výrobků V2, V3 a V4 a mohou být též prodávány. Odbytové ceny těchto výrobků jsou 300, 600, 1000 a 3000 na jednu tunu. Úkolem je stanovit výrobní program, kterým firma dosáhne maximální hodnoty produkce. Tyto údaje lze převést do tab. 35.

Z S V1 V2 Cena

V1 1,5 2 0 0 300

V2 0 1,5 0,5 0 600

V3 2 2 0 0,5 1000

V4 2,5 0 1 2 3000

Tab. 35 Tabulka zadaných hodnot

74

Kapacita 1200 1400


Pro výše uvedený příklad můžeme psát soustavu nerovnic ve tvaru 1,5 V1 2,0 V1 + 1,5 V2 - V1 + 0,5 V2 V2 300 V1 + 450 V2

Způsob

sestavení

+ 2,0 V3 + 2,0 V3 + 0,5 V3 + 700 V3

+ 2,5 V4 <= 1200 <= 1400 + V4 <= 0 + 2,0 V4 <= 0 + 1500 V4 = z

soustavy lineárních

nerovnic je předmětem

ekonomicko

matematických metod a nebude zde probírán. Podstatné pro náš příklad je skutečnost, že chceme maximalizovat zisk, který je dán účelovou funkcí z. Můžeme tedy využít možnosti optimalizace genetickými algoritmy (existují i jiné způsoby řešení, např. simplexová metoda). Měněnými veličinami jsou počet výrobků V1, V2, V3 a V4. Počáteční nulové hodnoty počtu výrobků a příslušné rovnice zapíšeme do tabulky Excelu. Viz tab. 36.

A B 1 Optimalizace výrobního programu 2 3 Optimalizované proměnné 4 V1= V2= 5 0 0 6 Účelová funkce 7 z= =300*A5+450*B5+700*C5+1500*D5 8 Omezující podmínky 9 Z =1.5*A5+2*C5+2.5*D5 10 S =2*A5+1.5*B5+2*C5 11 V1 =-1*A5+0.5*B5+1*D7 12 V2 =-1*B5+0.5*C5+2*D5

C

D

V3= 0

V4= 0

1200 1400 0 0

Tab. 36 Tabulka vzorců a hodnot

Je-li tab. 36 vyplněna, je potřebné zadat do programu GeneHunter parametry pro výpočet. Viz obr. 67.

75


Obr. 67 Volba parametrů pro optimalizaci Optimalizací hledáme maximum účelové funkce z, kdy měníme počty výrobků V1, V2, V3 a V4. Omezení, vyplývající z uvedených nerovností, jsou zobrazeny ve spodní části obr. 67. Po výpočtu obdržíme optimalizované hodnoty. Viz tab. 37.

Optimalizace výrobního programu Optimalizované proměnné V1= V2= 400 400 Účelová funkce z= 600000 Omezující podmínky Z 1100 S 1400 V1 0 V2 0

V3= V4= 0 200

1200 1400 0 0

Tab. 37 Tabulka po optimalizaci V našem konkrétním případě tedy bude maximální zisk 600 000 Kč v případě, že vyrobíme 400 ks výrobku V1, 400 ks výrobku V2 a 200 ks výrobku V4, výrobek V3 nebudeme vyrábět. Z tab. 36 je zřejmé, že podmínky pro výrobu jsou splněny (Z <= 1200, S <= 1400).

76


Příklad 30. Další použití genetických algoritmů pro úlohy operační analýzy uvedeme na případu, kdy tři prvky A,B,C jsou obsaženy ve čtyřech sloučeninách. Obsah prvků v jednotlivých sloučeninách, jakož i ceny sloučenin a potřebné množství prvků jsou v tab. 38. Úkolem je zjistit, které sloučeniny a v jakém množství je třeba nakoupit, abychom získali potřebné množství prvků za nejnižší cenu.

S1 0 2 10 15

A B C Cena sloučeniny (Kč/kg)

S2 2 2 5 10

S3 4 0 4 12

S4 5 4 10 25

Potřebné množ. 5000 6000 18000

Tab. 38 Tabulka zadaných hodnot Pro výše uvedený příklad můžeme psát soustavu nerovnic ve tvaru 2S2 + 4S3 + 5S4 >= 5000 2S1 + 2S2 + 4S4 >= 6000 10S1 + 5S2 + 4S3 +10S4 >= 18000 15S1 +10S2 + 12S3 + 25S4 = z Způsob sestavení soustavy lineárních nerovnic je předmětem operační analýzy a nebude zde probírán. Podstatné pro náš příklad je skutečnost, že chceme minimalizovat náklady, které jsou dány účelovou funkcí z. Optimalizací obdržíme údaje, které sloučeniny a v jakém množství je třeba nakoupit, abychom získali potřebné množství prvků co nejlevněji. Můžeme tedy opět využít možnosti optimalizace genetickými algoritmy Měněnými veličinami budou potřebné množství suroviny S1, S2, S3 a S4. Počáteční nulové hodnoty množství surovin a příslušné rovnice zapíšeme do tabulky Excelu. Viz tab. 39.

1 2 3 4 5 6 7 8 9 10 11

A Optimalizace výrobního programu Optimalizované proměnné S1 0 Účelová funkce

B

C

D

S2 0

S3 0

S4 0

z= =15*A5+10*B5+12*C5+25*D5 Omezující podmínky A B C

=2*B5+4*C5+5*D5 =2*A5+2*B5+4*D5 =10*A5+5*B5+4*C5+10*D5

Tab. 39 Tabulka vzorců a hodnot

77

5000 6000 18000


Je-li tab. 39 vyplněna, je potřebné zadat do programu GeneHunter parametry pro výpočet. Viz obr. 68.

Obr. 68 Volba parametrů pro optimalizaci Optimalizací hledáme minimum účelové funkce z, kdy měníme množství suroviny S1, S2, S3 a S4. Omezení, vyplývající z uvedených nerovností, jsou zobrazeny ve spodní části okna. Po výpočtu obdržíme optimalizované hodnoty. Viz tab. 40.

Optimalizace výrobního programu Optimalizované proměnné S1 S2 550 2500 Účelová funkce z= 33250 Omezující podmínky A 5000 B 6100 C 18000

S3 0

S4 0

5000 6000 18000

Tab. 40 Tabulka po optimalizaci

Příklad 31. Jako příklad použití programovacího prosředí MATLAB s Genetic Algorithm Toolboxem uvedeme nalezení minima Rastriginsovy funkce, která patří svým průběhem mezi ty, kterými se prověřuje schopnost algoritmů hledat optimum. Tato funkce je definována následujícím vzorcem

78


z(x,y) = 20 + x2 +y2 – 10 * (cos2πx + cos2πy). Nejdříve budou popsány možnosti voleb. Spuštění provedeme v příkazovém okně příkazem optimtool. Na obrazovce se zobrazí okno. Viz obr.69.

Obr. 69 Okno nástroje optimtool Jednotlivá menu mají následující významy. V levé části okna se zadává metoda řešení Solver, v našem případě ga-Genetic algorithm, dále odkaz na fitness funkci ve tvaru @fitnessf, kde fitnessf.m je M-soubor, který vrací hodnotu účelové funkce v zadaném bodě (pro zadaný vektor). Dále se specifikuje počet nezávislých proměnných fitness funkce, které jsou reprezentovány jednotlivými chromozomy a mají se optimalizovat. Lze zadat i omezení na proměnné ve tvaru soustavy lineárních (ne)rovnic A * x = b (resp. A * x ≤ b). Rovněž lze vymezit dolní a horní hranice hodnot, které mohou nezávislé proměnné nabývat ve tvaru vektoru. Pokud je třeba použít nelineární omezení, musí se vytvořit M-soubor s názvem např. omezeni.m, na který se v příslušném poli odkážeme přes funkci @omezeni. Funkce popsaná v tomto souboru musí vracet vektory C a Ceq, které odpovídají nelineárním omezením tvaru C ≤ 0 a Ceq = 0.

79


V další části okna se zadává, které funkce si přejeme vykreslovat v průběhu výpočtu -

best fitness – zobrazuje hodnotu fitness funkce nejúspěšnějšího jedince dané generace,

-

expectation – zobrazuje očekávaný počet potomků jednotlivých jedinců dané populace v závislosti na jejich „skóre“ (hodnotě fitness funkce),

-

score diversity – zobrazuje histogram četností jednotlivých hodnot fitness funkce v dané generaci,

-

stopping – zobrazuje aktuální úroveň kritérií pro ukončení výpočtu,

-

best individual – zobrazuje hodnotu nezávislých proměnných pro nejúspěšnějšího jedince dané generace,

-

genealogy – zobrazuje genealogii jedinců (černé linie označují elitní jedince, kteří přecházejí do následující generace, červené úsečky indikují jedince kteří vznikli mutací a modré úsečky spojují jedince, kteří vznikli křížením s jejich rodiči),

-

scores – zobrazuje hodnoty fitness funkce pro jednotlivé jedince dané generace

-

max constraint – znázorňuje maximální vzdálenost (míru nesplnění) nelineárního omezení pro danou generaci,

-

distance – zobrazuje průměrnou vzdálenost mezi jedinci v dané generaci,

-

range – znázorňuje minimální, maximální a průměrnou hodnotu fitness funkce v dané generaci,

-

selection – zobrazuje histogram počtu potomků připadajících na jednotlivé třídy rodičů v dané generaci.

Do pole Custom lze zadat libovolnou definovanou kreslící funkci formou M-souboru. Pole Plot interval popisuje frekvenci vykreslování výše popsaných grafických výstupů. V pravé části okna se zadávají další parametry výpočtu týkající se zejména funkce křížení, mutace a selekce. Lze využít již předdefinovaných funkcí nebo si opět formou Msouboru vytvořit vlastní. Najdeme zde následující menu -

population - zde se zadávají parametry týkající se námi zvolené populace, tj. typ populace (double, bit string, custom - vlastní), velikost populace (počet jedinců), vytvořující funkci (uniform – pomocí rovnoměrného rozdělení, custom - vlastní), počáteční populaci, počáteční skóre a interval, z něhož se mají vybírat hodnoty pro počáteční populaci,

-

fitness scaling – zde se zadává způsob, jakým budou hodnoceni jedinci dané populace (lze volit: rank – vychází z pořadí jedinců, proportional – proporcionálně odpovídá 80


hodnotě fitness funkce, top – zadává se počet nejlepších jedinců, kteří budou produkovat potomky, shift linear – zadává se konstanta očekávání pro nejlepšího jedince, custom - vlastní), -

selection – zde se zadává, jakým způsobem se budou vybírat rodiče pro vznik další generace (stochastic uniform – náhodný rovnoměrný výběr vzhledem k očekávání, remainder – deterministický výběr s užitím rulety, uniform – náhodný výběr z rovnoměrného rozdělení s ohledem na očekávání a počet rodičů, roulette – simuluje kolo rulety, kde jednotlivá pole odpovídají očekávání jednotlivých segmentů rodičů, tournament – náhodně vybere určitý počet jedinců a z nich toho nejlepšího, custom vlastní),

-

reproduction – do pole elite count se zadává počet nejlepších jedinců, kteří automaticky přecházejí do další generace a dále se zadává, kolik procent jedinců bude kromě těchto elitních vytvořeno křížením (crossover fraction), zbývající počet vznikne mutací,

-

mutation – zde se zadává, jakým způsobem bude probíhat mutace (Gaussian – na základě Gaussova rozdělení, uniform – na základě rovnoměrného rozdělení, adaptive feasible – adaptivně s ohledem na dodržení omezení, custom - vlastní),

-

crossover – zde se zadává způsob křížení (scattered – zobecněné křížení, single point – jednobodové křížení, two point – dvoubodové křížení, intermediate – vážený průměr rodičů, heuristic – uvažuje i účelovou funkci, arithmetic – vážený aritmetický průměr rodičů s ohledem na přípustnost, custom - vlastní),

-

migration – migrací se rozumí pohyb jedinců mezi subpopulacemi a používá se, zadáme-li velikost populace ve tvaru vektoru délky alespoň 2. Nejlepší jedinci jedné subpopulace tak nahrazují nejhorší jedince druhé subpopulace. Může jít o migraci dopřednou forward, kdy jedinci přecházejí z n - té do n+1 - té populace nebo o migraci oběma směry both. Počet přecházejících jedinců se zadává zlomkem fraction a frekvence migrace číslem interval,

-

algorithm settings initial penalty – počáteční penalizace algoritmu (větší než 1), penalty factor – zvyšuje hodnotu parametru penalizace, není-li problém vyřešen s požadovanou přesností a omezení nejsou splněna (větší než 1),

-

hybrid function – zde se nastavuje další optimalizační funkce, která se spustí po ukončení genetického algoritmu (fminsearch, patternsearch, fminunc, fmincon),

-

stopping criteria – zde se zadávají kritéria pro ukončení výpočtu (počet generací, časový limit, fitness limit, počet generací, po které nedojde k významné změně fitness 81


funkce, čas, po který nedojde k významné změně fitness funkce, kumulativní změna fitness funkce, maximální tolerance porušení nelineárního omezení), -

output function – zde lze zadat výpis historie algoritmu,

-

display to command window – zde lze zadat, jaké informace si přejeme zobrazovat v příkazovém okně (iterative – v každé iteraci výpočtu, diagnose – navíc se zobrazí další informace, final – zobrazí se důvod ukončení výpočtu),

-

vectorize – vektorizace udává, zda se fitness funkce volá pro každého jedince zvlášť.

Po zadání všech parametrů algoritmu se spustí výpočet stiskem tlačítka Start. Výpočet lze kdykoli pozastavit stiskem tlačítka Pause, resp. zastavit tlačítkem Stop. V příkazovém okně se pak objeví popis průběhu výpočtu a na závěr výsledné hodnoty nezávisle proměnných.

Pro výpočet v programovém prostředí MATLAB musíme nejdříve naprogramovat Rastriginsovu funkci v M-souboru, který nazveme rfcn.m. Viz prog.1.

function scores = rfcn(pop) scores = 10.0 * size(pop,2) + sum(pop .^2 - 10.0 * cos(2 * pi .* pop),2); Prog. 1 Rastriginsova funkce Do okna Optimization Tools se zadá do pole Solver metoda ga - Genetic Algorithm a do Fitness function účelová funkce zapsaná v M-souboru @rfcn a do pole Number of variables počet proměnných 2. Ostatní parametry lze ponechat s defaultním nastavením. Takto připravené údaje nám umožní spustit výpočet tlačítkem Start. Viz obr.69.

Po ukončení výpočtu obdržíme výsledky v okně Final point 1 a 2. Výsledek nás informuje, že při hodnotách x = 0 a y = 0 je nalezene minimum, který najdeme v poli Status and results, kde hodnota fitness funkce Fitness function value z = 0. Minimum funkce se nachází na souřadnicích [0 0] a jho hodnota je nulová, což odpovídá výpočtu. Viz obr.70.

82


Obr. 70 Graf Rastriginovy funkce

Příklad 32. Pro ukázku řešení v prostředí MATLAB využijeme případ popsaný v příkladu 21. Pro výrobu desetilitrových plechovek budeme chtít určit poloměr plechovky r a její výšku v tak, aby spotřeba materiálu byla minimální. Tento úkol vyřešíme pomocí programu takovým způsobem, že program mění poloměr r a výšku v tak, aby povrch válce P byl minimální při zachování objemu V. Pro objem válce platí vzorec V = πr2v a pro povrch P = 2πr2 + 2πrv. Při použití Genetic Algorithm Toolboxu v programovém prostředí MATLAB musíme nejdříve definovat fitness funkci povrch_fun jako soubor povrch_fun.m. Viz prog.2.

function z = povrch_fun(x) z = 2*3.1415*x(1)*x(1)+2*3.1415*x(1)*x(2); Prog. 2 Funkce výpočtu povrchu Dále je zapotřebí zadat opět v souboru typu M-file nelineární omezení, které odpovídá zadanému objemu. Funkci nazveme omezeni. Viz prog.3.

83


function [c, ceq] = omezení(x) c = []; ceq = [3.1415*x(1)*x(1)*x(2)-10]; Prog. 3 Funkce omezení konstantního objemu Po spuštění příkazu optimtool a zvolení řešitele Solver ga - Genetic Algorithm je nutné do okna Optimization Tool zadat do pole Fitness function účelovou funkci zapsanou v M-souboru @povrch_fun, do pole Number of variables počet proměnných 2, omezení, že řešením jsou pouze nezáporná čísla tj. r ≥ 0 a v ≥ 0 zapíšeme do pole Bounds Lower [0 0], omezení že objem V má být konstantní je zapsán v souboru omezeni.m a proto je nutné tuto skutečnost uvést do pole Nonlinear constraint function ve tvaru @omezení. Pokud chceme při výpočtu sledovat průběh hodnoty účelové funkce, zaškrtneme políčko Best fitness. Je vhodné změnit velikost populace na počet 100. Proto v poli Population size zapíšeme 100. Ostatní parametry ponecháme s defaultním nastavením. Viz obr. 72. Takto připravené údaje v tabulce nám umožní spustit výpočet tlačítkem Start. Průběh výpočtu můžeme sledovat na grafu zobrazující hodnoty účelové funkce. Viz obr.71. Po ukončení výpočtu obdržíme výsledky v okně Final point 1 a 2. Výsledek nás informuje, že při poloměru r = 1.17 dm a výšce v = 2.34 dm je povrch optimalizovaný na minimum. Údaj o velikosti povrchu se dozvíme v poli Status and results, kde hodnota fitness funkce Fitness function value P = 25.6947 dm2. Zde je také uvedena informace o ukončení optimalizace, kdy chyba výpočtu je nižšší jak nastavená Current tolerance on f(x) =3.4383e-32. Ukazuje se, že s vyšším počtem jedinců v populaci se přesnost výpočtu zvyšuje. Okno nástroje optimtool po výpočtu je na obr.72.

84


Obr. 71 Graf průběhu hodnot účelové funkce při výpočtu

Obr. 72 Okno nástroje gatool po výpočtu

85


Příklad 33. (MS Excel-Řešitel) V softwaru MS Excel byla v poslední verzi programu Řešitel, umožněna volba Evolutionary, která umožňuje provést optimalizaci pomocí genetických algoritmů. Kladem zařazení metody do Řešitele je její dostupnost pro řešení nelineárních úloh v prostředí běžně dostupného programu MS Excel. Nevýhodou je nemožnost nastavení některých parametrů pro výpočet genetickými algoritmy, jako je velikost populace, chromozomu, nastavení parametrů selekce, křížení, mutace a rozšířené možnosti omezujících podmínek. Toto se projeví jako problém při řešení složitějších úloh. Jako ukázku výpočtu v prostředí MS Excel využijeme případ popsaný v příkladu 21, řešený v programu Genehunter a v příkladu 32, řešený v programovém prostředí MATLAB s využitím Optimization Global Toolboxu a příklad 34 řešený v MS Excelu v programu Řešitel klasickou metodou. Pro výrobu desetilitrových plechovek budeme chtít určit poloměr plechovky r a její výšku v tak, aby spotřeba materiálu byla minimální. Tento úkol vyřešíme pomocí programu takovým způsobem, že program mění poloměr r a výšku v tak, aby povrch válce P byl minimální při zachování objemu V. Pro objem válce platí vzorec V = πr2v a pro povrch P = 2πr2 + 2πrv. Při použití Řešitele v prostředí MS Excel musíme tyto vzorce zapsat do buněk programu Excel. Viz tab.41. B

C Výška V 0

D Poloměr R 0

6

Povrch

P

=2*3.1415*D4*C4+2*3.1415*D4*D4

7

Objem

V

=3.1415*D4*D4*C4

2 3 4 5

Tab. 41 Tabulka vzorců V Excelu tedy máme výraz pro povrch v buňce D6 a pro objem v buňce D7. Hodnotu výšky v buňce C4 nastavíme na 0 a poloměr r v buňce D4 také na 0. Viz obr.73.

Obr. 73 Tabulka před výpočtem

86


V prostředí MS Excel spustíme Řešitele volbou Data – Řešitel, kde navolíme údaje nezbytné pro výpočet. Viz obr.74.

Obr. 74 Volba parametrů pro optimalizaci Nastavení je v našem případě následující. Účelová funkce rovnice pro povrch P, která se nachází v buňce D6, nastavíme v poli Nastavit cíl. Hledáme minimum této funkce, proto volíme nastavení Na: Min. Hodnoty, které program mění, jsou výška v a poloměr r, které se nacházejí v buňce C4 a D4, které nastavíme v poli Na základě změny proměnných buněk:. Dále volíme omezení maximálního a minimálního poloměru r a výšky v, která je dána nerovnicemi 0.5 <= v <= 4 a 0.1 <= r <= 2. Tyto podmínky se zapíší v poli Omezující podmínky:. Vložení podmínek provedeme kliknutím na tlačítko Přidat. Protože výška v, která je umístěna v buňce C4, má být menší než 4, provedeme vyplnění tabulky, tak jak je to patrné

87


na obr.75. Zapíšeme odkaz na buňku, dále v roletovém menu volíme typ nerovnosti a hodnotu omezující podmínku. Potvrzení provedeme příkazem OK nebo tlačítkem Přidat přidáme další omezující podmínku. Tuto činnost opakujeme pro všechny podmínky. Poslední podmínkou je, že objem nádoby má být deset litrů. Výsledek je patrný na předchozím obr.74.


Nezaškrtnuté políčko Nastavit proměnné bez omezujících podmínek jako nezáporné nám omezuje řešení pouze na kladné hodnoty, což je vzhledem k úloze důležité stejně tak jako u podnikatelských úloh u počtu výrobků, strojů a lidských zdrojů. Zbývá jen nastavit Vyberte metodu řešení: na Evolutionary.

Máme-li nastaveny všechny údaje pro výpočet, spustíme jej tlačítkem Řešit. Výpočet je po několika minutách ukončen. Výsledek optimalizace je patrný z obr.76. Zvolíme-li výšku v = 2.28 dm a poloměr r = 1.18 dm, bude objem V = 10.01 litrů a minimalizovaný povrch bude činit P = 25.71 dm2.

Obr. 76 Tabulka po výpočtu Výsledkem řešení jsou obdobné hodnoty, nikoliv naprosto stejné, jako u příkladu příkladu 21 i příkladu 32. Je to dáno jiným způsobem výpočtu a neumožněním volby omezení tolerancí a nastavením parametrů selekce, křížení a mutace.

88


4 KLASICKÉ METODY Metody použité v této kapitole vycházejí z možnosti realizovat optimalizační proces pomocí nástrojů, které jsou součástí základního programového vybavení PC a disponují matematickým aparátem vhodným pro optimalizaci. Takovým příkladem použití je tabulkový kalkulátor Excel nebo webový prohlížeč s instalací Java pro spouštění appletů. Příklady zde uvedené navazují na optimalizaci pomocí genetických algoritmů a ukazují u jednoduchých úloh pracovní postupy, které vedou ke stejným nebo velmi podobným výsledkům při řešení vybrané problematiky.

Instalace doplňku Řešitel Pro realizaci tohoto příkladu je nutné mít nainstalován doplněk programu MS Excel nazývaný Řešitel, anglicky Solver. Jeho instalace pro verzi MS Excel 2010 je uvedena v následujícím postupu: Z hlavního menu ikony Windows vlevo vybereme ve spodní části variantu „Možnosti aplikace Excel”„ a klikneme na toto tlačítko. Viz obr. 77.

Obr. 77. Instalace modulů v programu Excel Zobrazí se následující okno, které obsahuje seznam modulů, které jsou instalovány v tomto programu. Vybereme v horní části Doplňky a klikneme na tlačítko „Přejít“, tím dojde k výběru doplňku. Viz obr.78. 89


Obr. 78 Instalace doplňku Řešitel Zaškrtneme volbu Řešitel a potvrdíme tlačítkem „OK“. Viz obr.79.

Vybereme řešitele

Obr. 79 Výběr modulu řešitele Nyní bude program instalovat Řešitele do svého systému a po instalaci ověříme tuto činnost prohlídkou záložky „Data“ v horním menu. Na pravé straně se zobrazí ikona pro spuštění Řešitele. Viz obr.80.

90


Řešitele nalezneme v záložce Data -> Řešitel

Obr. 80. Zobrazení řešitele na liště programu Excel V této fázi je již možné pracovat s Řešitelem a používat jeho možnosti pro řešení optimalizačního problému.

Příklad 34. Příklad optimalizace povrchu plechovky. Realizujte řešení optimálních parametrů poloměru r a výšky v pro plechovku s objemem 10 litrů. Při optimalizaci výroby jsou tyto parametry ovlivněny možnostmi výroby a proto parametry r - poloměr a v - výška plechovky musejí být v určitém rozsah dle možností výrobních strojů, které jsou k dispozici. V tomto případě řešíme co nejmenší spotřebu materiálu. Tento příklad bude uveden velmi podrobně z důvodu seznámení se s prací s programem Řešitel.

Analýza zadání • Cílem optimalizace je minimalizace povrchu plechovky • Měněné parametry během optimalizace jsou r - poloměr, v - výška Omezující podmínky • Poloměr r je omezen rozsahem • Výška plechovky v je omezena rozsahem • Objem plechovky je konstantní 10 litrů Použité vzorce Objem plechovky V = plocha podstavy x výška V= 3,1415 * r2 * v Povrch plechovky P = 2 x plocha podstavy + plášt 91


S= 2 * 3,1415 * r * v + 2 *3,1415 * r2 V následujících obrázcích je uveden postup řešení v programu Excel s využitím doplňku Řešitel, do kterého vložíme uvedené vzorce, omezující podmínky a parametry optimalizace.

Pro případ optimalizačního problému plechovky volíme následující postup, kdy zapíšeme inicializační hodnoty, např. r = 1 a v = 1 do buněk C4 a D4 a vzorec pro povrch P do buňky D6 a pro objem V do buňky D7. Viz obr.81.

Vytvoříme si následující tabulku Do buňky D6 vložíme vzorec: =2*3,1415*D4*D4+2*3,1415*D4*C4 Do buňky D7 vložíme vzorec: =3,1415*D4*D4*C4

Obr. 81. Model programu Excel pro výpočet plechovky Program Řešitel spustíme kliknutím na jeho ikonu vpravo nahoře. Viz obr. 82.

Spustíme Řešitele

Obr. 82. Spuštění Řešitele v programu Excel

92


Následuje nastavení parametrů optimalizace a omezujících podmínek. Nejdříve se nastaví účelová funkce (minimalizace nákladů) uložená v buňce D6 v poli „Nastavit buňku“, dále minimalizaci nákladů zajistíme přepínačem „Rovno“ přepnutým v našem případě na Min. Hodnoty, které bude program optimalizovat (poloměr r a výška v) vyhrazené v buňce C4 a D4 nastavíme v poli „Měněné buňky“. Viz obr. 83.

Buňku nastavíme na D6

Buňky, které budeme měnit nastavíme na C4 a D4

Obr. 83. Doplnění parametrů Řešitele podle požadavků

Podmínky nastavíme pomocí tlačítka přidat

Obr. 84. Postupné přidání omezujících podmínek

93


Postupné přidávání omezujících podmínek $C$4<=5, $C$4>=0.5, $D$4<=5, $D$4>=0.5 a $D$7=10 je zobrazeno na následujícím obrázku, kdy využíváme menu „Přidat“. Viz obr.84. Podmínky vkládáme pomocí menu „Odkaz na buňku“, nerovnosti < = > nastavíme pomocí roletového menu a do pole Omezující položka“ vložíme hodnotu omezení, popř. odkaz na buňku. Viz obr.85.

Postupně nastavíme jednotlivé podmínky

Obr. 85. Výběr operátorů omezujících podmínek Po spuštění Řešitele tlačítkem „Řešit“ se spustí optimalizace. Viz obr.86.

Řešitele spustíme pomocí tlačítka Řešit

Obr. 86. Spuštění výpočtu pro dosažení výsledných hodnot 94


Výsledkem optimalizace jsou hodnoty poloměru r a výšky v, u kterých je splněna minimální spotřeba materiálu - povrch P (minimální náklady), při splnění omezujících podmínek objem V=10 litrů a rozsahu povoleného poloměru r a výšky v. Viz obr.87.

Výsledek vidíme zde.

Obr. 87. Zobrazení výsledku po optimalizaci Optimalizační úlohu je možné řešit i pomocí genetického algoritmu a provést porovnání rozdílů. Výsledek optimalizace se může lišit v řádu setin z důvodu použité metody, což nemá vliv na konečný výsledek pro výrobu plechovky. Příklad 35. Příklad optimalizace výroby. Firma vyrábějící vánoční baňky má za úkol připravit výrobu dvou druhů vánočních kolekcí baněk. Do první kolekce dává 12 ks červených baněk a 18 ks modrých baněk. Do druhé dává 15 ks červených baněk a 10 ks modrých baněk. Na prvním druhu kolekce vydělá 25 Kč a na druhém druhu vydělá 21 Kč. Má k dispozici 250 červených baněk a 290 kusů modrých baněk. Jaký bude výrobní program firmy? Analýza: Co jsou proměnné, se kterými budeme řešit problém optimalizace výroby? Proměnnými jsou počty kolekcí, které potřebujeme vyrobit. Co budeme optimalizovat? Optimalizovat budeme zisk z prodeje kolekcí na maximální hodnotu. Jaké jsou omezující podmínky? 95


• •

Počet kolekcí musí být nezáporné číslo Omezení z rovnic vycházející z počtu baněk jednotlivých druhů, které jsou k dispozici

Použité rovnice: x1 počet kolekce prvního druhu x2 počet kolekce druhého druhu. Sestavíme rovnice pro jednotlivé druhy baněk Červené baňky 12 x1 + 18 x2 =< 250 Modré baňky 15 x1 + 10 x2 =< 290. Rovnice pro hodnotu zisku je následující 25 x1 + 21 x2 =zmax maximální zisk. Podle sestavených rovnic vytvoříme matematický model v Excelu, který bude sloužit pro výpočet pomocí doplňku Řešitele s potřebnými údaji pro výpočet. Nejprve do jednotlivých buněk zadáme konstantní hodnoty a doplníme vzorce do Excelu. Postup, který byl popsán, v předešlém příkladu, je stejný. Účelová funkce je zapsána v buňce D7, optimalizace je nastavena na maximální zisk, měněné buňky (počet kolekcí) jsou v buňce C10 a D10 s příslušnými rovnicemi. Viz obr.88.

Obr. 88. Zobrazení matematického modelu pro výpočet Dále je nezbytné zapsat omezující podmínky, které je možné kumulovat. Jde o podmínku, že počet kolekcí musí být celé číslo, dále, že počet kolekcí musí být nezáporné

96


číslo (výpočet by mohl vést k záporným hodnotám, což není možné v ekonomii) a poslední podmínka vyjadřuje omezený počet kusů baněk pro výrobu. Viz obr.89.

Obr. 89. Zobrazení parametrů řešitele Po spuštění řešení obdržíme výsledek, počet jednotlivých kolekcí, který splňuje omezující podmínky a zajišťuje maximalizaci zisku. Viz obr.90.

Obr. 90. Zobrazení dosažených výsledků po optimalizaci počtu kolekcí

97


Příklad 36. Optimalizace výroby podle kapacity. Firma vyrábí čtyři druhy výrobků, na kterých se provádějí následující operace, vrtání, spojování a řezaní výrobků. Pro jednotlivé druhy těchto operací jsou stanoveny výrobní kapacity v hodinách, které nelze překročit. Tyto kapacity jsou dány následující tabulkou tab.42.

Operace Vrtání Spojování Řezání

výrobek1 10 7 0

výrobek2 9 6 8

výrobek3 13 0 9

výrobek4 11 10 0

Kapacita 800 500 400

Tab. 42 Kapacity a operace pro jednotlivé výrobky Zisk z prodeje jednotlivých druhů výrobků je následující: Zisk pro výrobek prvního druhu = 80 Kč Zisk pro výrobek druhého druhu = 100 Kč Zisk pro výrobek třetího druhu = 140 Kč Zisk pro výrobek čtvrtého druhu = 110 Kč. Naším úkolem je navrhnout, kolik výrobků od každého druhu se má vyrobit, tak aby nebyly překročeny výrobní kapacity a výroba byla optimální. Analýza: Co jsou proměnné, se kterými budeme řešit problém optimalizace výroby? Proměnnými jsou počty jednotlivých druhů výrobků. Co budeme optimalizovat? Optimalizovat budeme zisk z výroby jednotlivých výrobků při využití stávajících kapacit. Jaké jsou omezující podmínky? • Počet výrobků jednotlivých druhů musí být nezáporné číslo • Počet výrobků jednotlivých druhů musí být celé číslo • Omezení výrobními kapacitami pro jednotlivé výrobní operace vrtání, spojování a řezání. Použité rovnice: x1 počet výrobku prvního druhu x2 počet výrobku druhého druhu x3 počet výrobku druhého druhu x4 počet výrobku druhého druhu. Sestavíme rovnice pro jednotlivé druhy výrobků s využitím tabulky pro operace a výrobky Operace vrtání 10x1 + 9x2 + 13x3 + 11x4=< 800 Operace spojování 7x1 + 6x2 + 0x3 + 10x4=<500 0x1 + 8x2 + 9x3 + 0x4=<400. Operace řezání

98


Rovnice pro hodnotu zisku z jednotlivých výrobků je následující zmax= 80x1 + 100x2 + 140x3 + 110x4 maximální zisk. Vytvoříme matematický model v Excelu, podle uvedených rovnic a výrobních operací. Při výpočtu skutečných kapacit doplníme vzorce pro výpočet zbývajících kapacit pro jednotlivé operace. Jednotlivé hodnoty jsou uvedeny v buňkách a jsou zobrazeny na obrázku obr.91.

Obr. 91. Model v Excelu pro výrobu s hodnotami a vzorci Pozn.: Při výpočtu skutečných kapacit, který vychází z jednotlivých rovnic, můžeme použít vzorce Excelu s využitím absolutní adresace buněk označených symbolem $, které dovolují kopírování vzorce ve sloupci G pro jednotlivé operace. Další variantou je použití vzorce pro skalární součin pro násobení matice B13 : E13 a matic v rozsahu B4 : E4. Vzorec pro výpočet zisku je v buňce F8 = B13*B8+C13*C8+D13*D8+E13*E8. Vzorce pro výpočet skutečných kapacit představuje vypočtenou levou stranu rovnic Buňka G4 = $B$13*B4+$C$13*C4+$D$13*D4+$E$13*E4 Buňka E4 = $B$13*B5+$C$13*C5+$D$13*D5+$E$13*E5 Buňka F4 = $B$13*B6+$C$13*C6+$D$13*D6+$E$13*E6. V následujícím kroku nastavíme parametry Řešitele pro optimalizaci následujícím způsobem

99


• • • • • • •

Optimalizujeme zisk, který je dán vzorcem v buňce F8, tj. nastavit buňku na $F$8 Optimalizujeme na maximum, provedeme zaškrtnutí na Max. Měněné buňky nastavíme na $B$13 : $E$13 Omezující podmínky zapíšeme do podmínek $B$13 : $E$13 = celé číslo – výrobky nelze rozdělit $B$13 : $E$13 >= 0 – počet výrobků musí být nezáporná hodnota $G$4 : $G$6 <=$F$4 : $F$6 - podmínka pro nepřesáhnutí výrobních kapacit.

Viz obr.92.

Obr. 92. Nastavení parametrů řešitele Po nastavení všech potřebných údajů pro řešení, tj. vložení rovnic, nastavení parametrů optimalizace a omezujících podmínek spustíme řešení příkazem Řešit. Program provede optimalizaci, kdy u měněných buněk obdržíme optimální hodnoty splňující dosažení maximálního zisku při splnění požadovaných podmínek. Viz obr.93.

Obr. 93. Ukázka dosažených hodnot výrobků po optimalizaci pomocí Řešitele

100


Po výpočtu hodnot počtu jednotlivých výrobků v buňkách B13 : E13 vidíme, že první výrobek se nebude vyrábět a počty pro další výrobky jsou následující: • • •

Výrobek2 počet 33 Výrobek3 počet 15 Výrobek4 počet 28. Ve sloupci G jsou skutečné potřebné kapacity pro výrobu při určitých výrobních

operací. Je vidět z vypočtených hodnot, že při operaci spojování máme k dispozici ještě 22 hodin navíc a při operaci řezání 1 hodinu navíc.

Výhodou modelu je možnost měnit kapacity podle požadavků výroby a možností kapacit na různých pracovištích, která bývají různě vytížena a hledat možnost optimálních výrobních kapacit pro krátkodobé nebo operativní plánování různých výrobků.

Příklad 37. Příklad optimalizace chemické výroby. Chemická firma nakupuje čtyři druhy sloučenin S1,S2,S3,S4, ze kterých chce získat tři různé prvky A, B, C. Obsah jednotlivých prvků je dán následující tabulkou tab.43 ve které je popsáno kolik množství prvků obsahuje určitá sloučenina. Dále je určena cena jednotlivé sloučeniny v Kč/kg. Našim úkolem je určit optimální nákup sloučenin tak abychom získali minimální nebo i více potřebného množství prvků A, B, C.

Prvek A Prvek B Prvek C Cena sloučeniny

sloučenina1 0 2 10

sloučenina2 2 2 5

sloučenina3 4 0 4

sloučenina4 5 4 10

15

10

12

25

Potřebné množství 5000 6000 18000

Tab. 43 Množství prvků v jednotlivých sloučeninách Analýza: Co jsou proměnné, se kterými budeme řešit problém nákupu jednotlivých sloučenin? Proměnnými jsou počty jednotlivých druhů sloučenin S1, S2, S3, S4. Co budeme optimalizovat? Optimalizovat budeme náklady pro nákup jednotlivých sloučenin, aby cena nákupu byla co nejnižší. Jaké jsou omezující podmínky?

101


• •

Množství jednotlivých druhů sloučenin musí být nezáporné číslo Omezení minimálním množstvím jednotlivých prvků, které musíme ze sloučenin získat.

Použité rovnice: S1 první sloučenina S2 druhá sloučenina S3 třetí sloučenina S4 čtvrtá sloučenina.

Sestavíme rovnice pro jednotlivé prvky s využitím potřebného množství určité sloučeniny Prvek A: Prvek B: Prvek C:

2S2 + 4S3 + 5S4 >= 5000 2S1 + 2S2 + 4S4 >= 6000 10S1 + 5S2 + 4S3 +10S4 >= 18000

Účelová funkce pro výpočet minimálních nákladů je následující zmin =15S1 +10S2 + 12S3 + 25S4

Podle sestavených rovnic vytvoříme matematický model v Excelu. Provedeme zápis jednotlivých hodnot a vzorců. Viz obr.94.

Obr. 94. Zobrazení modelu v Excelu Dále provedeme nastavení parametrů a omezujících podmínek. Viz obr.95.

102


Obr. 95. Zobrazení parametrů Řešitele Po nastavení všech potřebných údajů pro řešení, tj. vložení rovnic, nastavení parametrů optimalizace a omezujících podmínek spustíme řešení příkazem Řešit. Program provede optimalizaci, kdy u měněných buněk obdržíme optimální hodnoty splňující dosažení minimálních nákladů za podmínky získání minimálního množství prvků a více. Viz obr.96.

Obr. 96. Zobrazení výsledků optimalizace v Excelu

Příklad 38. Příklad optimalizace výroby konzerv. Výrobce potravy pro psy vyrábí masové konzervy. Obsah konzervy musí dle normy splňovat obsah nejméně 85g proteinů, přesně 140g karbohydrátů a nejvýše 135g tuků. Jako výchozí suroviny jsou k dostání 4 druhy masových směsí S1, S2, S3, S4. Obsahy jednotlivých složek ve směsích jsou uvedeny v tabulce tab.44. Stanovte výrobu tak, aby výroba byla pro výrobce optimální.

103


Proteiny 85 140 55 75

S1 S2 S3 S4

Karbohydráty 200 115 60 25

Tuky 140 170 175 60

Cena suroviny 160 240 80 120

Tab. 44. Obsah jednotlivých složek ve směsích Analýza: Co jsou proměnné, se kterými budeme řešit problém nákupu jednotlivých směsí? Proměnnými jsou počty jednotlivých směsí S1, S2, S3, S4. Co budeme optimalizovat? Optimalizovat budeme náklady pro nákup jednotlivých směsí, aby cena nákupu směsí byla co nejnižší a byla splněna norma o obsahu prvků. Jaké jsou omezující podmínky? • Množství jednotlivých druhů směsí musí být nezáporné číslo. • Omezení množství prvků dle normy, které musíme kombinací směsí získat. Použité rovnice: x1 první směs x2 druhá směs x3 třetí směs x4 čtvrtá směs Sestavíme rovnice pro jednotlivé prvky, které jsou obsaženy v jednotlivých směsích Proteiny: Karbohydráty: Tuky: Směšovací úloha:

85x1 + 140x2 + 55x3 + 75x4 >= 85 200x1 + 115x2 + 60x3 + 25x4 = 140 140x1 + 170x2 + 175x3 + 60x4 <= 135 x1 + x2 + x3 + x4 = 1

Náklady na nákup směsí

zmin = 160x1 + 240x2 + 80x3 + 120x4

Pozn.: U směšovacích úloh je nutné uvést podmínku, že celkové množství odpovídá celku tj. 1 nebo 100%, Potom vychází množství jako poměr k 1 nebo 100%.

Podle sestavených rovnic vytvoříme matematický model v Excelu. Provedeme zápis jednotlivých hodnot a vzorců. Viz obr.97.

104


Obr. 97. Matematický model v Excelu

Dále provedeme nastavení parametrů a omezujících podmínek. Viz obr.98.

Obr. 98. Zobrazení parametrů Řešitele Po nastavení všech potřebných údajů pro řešení, tj. vložení rovnic, nastavení parametrů optimalizace a omezujících podmínek spustíme řešení příkazem Řešit. Program provede optimalizaci, kdy u měněných buněk obdržíme optimální hodnoty splňující dosažení maximálního zisku při splnění požadovaných omezení. Viz obr.99.

105


Obr. 99. Zobrazení výsledků optimalizace v Excelu

Celkové náklady jsou 150,28 Kč na jeden kg, kdy poměr optimálního množství na 1 kg je na řádku 22 v jednotlivých buňkách B22:E22. Nad tabulkou je zobrazen koláčový graf zobrazující údaje uvedené v buňkách B22:E22 ve kterých je zobrazen výsledek a umožňuje přehled o rozložení jednotlivých druhů směsí k jednotkovému množství.

Příklad 39. Příklad optimalizace rozměrů kužele s využitím genetického algoritmu. Následující příklad bude řešit jednoduchý problém podobného charakteru, jako byl výpočet minimálního množství materiálu při výrobě plechovky. Rozdíl při řešení je v použití metody „Evolutionary“ v nastavení Řešitele v nabídce „Vyberte metodu řešení“. Tato metoda používá genetický algoritmus pro nalezení optima s nastavením jednotlivých parametrů dle obr. 100. Metoda používá při optimalizaci postupy genetických algoritmů jako je selekce, křížení a mutace. Informace o metodě lze nalézt na webovém serveru www.frontsys.com .

106


Obr. 100. Nastavení genetického algoritmu Realizujte řešení optimálních parametrů poloměru r a výšky v pro kužel s objemem 4 litrů. Při optimalizaci výroby jsou tyto parametry ovlivněny možnostmi výroby a proto parametry r - poloměr a v - výška kužele musejí být v určitém rozsah dle možností výroby. V tomto případě řešíme co nejmenší spotřebu materiálu. Analýza zadání • Cílem optimalizace je minimalizace povrchu kužele pro výrobu • Měněné parametry během optimalizace jsou r – poloměr podstavy, v – výška kužele Omezující podmínky • Poloměr r je omezen rozsahem 0,3 - 6 • Výška kužele v je omezena rozsahem 0,5 - 5 • Objem kužele je konstantní 4 litrů Použité vzorce Objem kužele V = plocha podstavy x výška / 3 V= 3,1415 * r2 * v / 3 Povrch kužele P = plocha podstavy + plášt S= 3,1415 * r2 +3,1415 * r * √(v2 + r2 ) V následujících obrázcích je uveden postup řešení v programu Excel s využitím doplňku Řešitel, do kterého vložíme uvedené vzorce obr.101, omezující podmínky a parametry optimalizace.

107


Obr. 101 Model programu Excel pro výpočet kužele Vzorce v programu Excel, které jsou použity v modelu dle obr.4.24 G6=3,14*F4*F4+3,14*F4*ODMOCNINA(F4*F4+G4*G4) G7=(3,14*F4*F4*G4)/3 Dále provedeme nastavení parametrů a omezujících podmínek. Viz obr.102 s nastavením metody řešení.

Obr. 102. Zobrazení parametrů Řešitele – metoda Evolutionary Po nastavení všech potřebných údajů spustíme řešení příkazem Řešit. V tomto okamžiku je možné sledovat ve spodním řádku postupnou minimalizaci buňky která je vybraná jako cíl pro minimalizaci a počet epoch genetického algoritmu. Celý proces je ukončen po několika desítkách sekund nalezením optimální varianty. Viz obr.103.

108


Obr. 103. Zobrazení výsledků optimalizace v Excelu Při použití genetického algoritmu dostaneme shodné řešení s řešením používající simplexovou metodu, které používá Excel při řešení optimalizačního problému. Pro řešení potřeboval genetický algoritmus přibližně 5200 epoch.

Zhodnocení dosažených výsledků při použití klasických metod Jednotlivé příklady zobrazují možnosti, které dovoluje realizovat doplněk programu Excel Řešitel v praxi. Tyto příklady ukazují, že velmi významnou částí při řešení dané úlohy je provedení analýzy ze které vyplynou základní rovnice podle kterých je sestaven matematický model v Excelu a omezující podmínky, které je nutné při optimalizaci splnit. Výhodou předcházejících matematických modelů v Excelu je možnost měnit buňky s hodnotami množství a provádět opakovaně optimalizační proces spuštěním Řešitele. V praxi se velmi často změní vstupní hodnoty u jednotlivých proměnných se zachováním omezujících podmínek, kdy je nutno reagovat novým výpočtem s novými výsledky. Rychlost výpočtů předcházejících matematických modelů se pohybuje v rozsahu sekund, což je pro praxi dostačující a uživatel má možnost opakovaně velmi rychle spouštět optimalizační úlohu. Z hlediska přesnosti je možné výsledky ovlivnit v nastavení Řešitele se zaměřením na požadavky výsledku. Celá kapitola ukazovala různé varianty příkladů od nejjednoduššího ke složitějším s důrazem vysvětlení postupu a jednotlivých kroků uživatele, tak aby je bylo možné co nejrychleji aplikovat v praxi. 109


LITERATURA ALLIEV,A., ALLIEV,R. Soft Computing and Its Applications, World Scientific Publishing Co, UK 2002, ISBN 981-02-4700-1. BOSE K., LIANG P. Neural Network, Fundamental with Graphs, Algorithm and Applications, Mc Graw-Hill, 1996, ISBN 0-07-114064-6. BROZ, Z., DOSTÁL, P. Multilingual dictionary of artificial intelligence. Brno: CERM Akademické nakladatelství, 2012. 142 p. ISBN 978-80-7204-800-7 , e-ISBN 978-80-7204801-4. DOSTÁL, P. Moderní metody ekonomických analýz,UTB – FAME - Zlín 2002, ISBN 807318-075-8. DOSTÁL, P. Pokročilé metody analýz a modelování, CERM, Brno, 2006, ISBN 80-2143324-8. DOSTÁL, P. Advanced Decision Making in Business and Public Services. CERM, Brno, 2011, ISBN 978-80-2204-747-5. DOSTÁL, P., MATUŠTÍKOVÁ, V., JEVČÁKOVÁ, I. Ekonomicko-matematické metody. 2011, pp.150., EPI Kunovice. 978-80-7314-242-1. DOSTÁL, P. Pokročilé metody rozhodování v podnikatelství a veřejné správě. Brno: CERM Akademické nakladatelství, 2012. 718 p. ISBN 978-80-7204-798-7, e-ISBN 978-80-7204799-4. DOSTÁL, P. The Use of Optimization Methods in Business and Public Services. In Zelinka, I., Snášel, V., Abraham, A. Handbook of Optimization, USA: Springer, 2012. ISBN 978-3642-30503-0. DOSTÁL, P. The Use of Soft Computing for Optimization in Business, Economics, and Finance. In Vasant, P. Meta-Heuristics Optimization Algorithms in Engineering, Business, Economics, and Finance, USA: IGI Globe, 2012. DOI: 10.4018/978-1-4666-2086-5, ISBN13: 9781466620865, ISBN10: 1466620862, EISBN13: 9781466620872. DOSTÁL P. The Use of Soft Computing Methods for Forecasting in Business, Their Applications in Practice, In Nostradamus: Modern Methods of Prediction, Modeling and Analysis of Nonlinear Systems, Springer, 2013, p. 49-60, ISSN 2194-5357. DOSTÁL, P., RAIS, K., SOJKA, Z. Pokročilé metody manažerského rozhodování, Grada, 2005, ISBN 80-247-1338-1. DOSTÁL, P. Moderní metody ekonomických analýz, UTB – FAME - Zlín 2002, ISBN 807318-075-8. GATELY E. Neural Networks for Financial Forecasting, John Wiley & Sons Inc., 1996, ISBN 0-471-11212-7. HAGAN T, DEMUTH B. Neural Network Design, PWS Publishing Comp., 1996, ISBN 0534-94332-2. KAZABOV,N., KOZMA,R. Neuro-Fuzzy – Techniques for Intelligent Information Systems, Physica-Verlag, 1998, ISBN 3-7908-1187-4. KLIR,G.J., YUAN, B. Fuzzy Sets and Fuzzy Logic, Theory and Applicatio Applications, Prentice Hall, New Jersy, USA, 1995, ISBN 0-13-101171-5.

110


THE MATHWORKS. MATLAB – Global Optimization Toolbox – User’s Guide, The MathWorks, Inc., 2012. PETRUCHA, J. Simulátor umělé neuronové sítě. EPI Kunovice 2003. ZADEH, L.A. (1965). Fuzzy sets. Information and Control 8, 338-353. ZADEH, L.A. & KACPRZYK, J. (1992). Fuzzy logic for the management of uncertainty. Wiley, New York.

111


112

Optimalizační metody v informačním managementu

Recommend Documents