METODY NEKONVENČNÍHO MODELOVÁNÍS PŘÍSTUPY UMĚLÉ INTELIGENCE

Miroslav Pokorný

OBSAH PREZENTACE

1. PROBLEMATIKA VĚDNÍHO OBORU UMĚLÁ INTELIGENCE

2. ZNALOSTNÍ MODELY FUZZY – LOGICKÉ

3. SAMOUČICÍ SE MODELY- UMĚLÉ NEURONOVÉ SÍTĚ

4. OPTIMALIZACE MODELU - GENETICKÉ ALGORITMY

UMĚLÁ INTELIGENCE

Náplň vědního oboru

konstrukce systémů pro řešení složitých problémů na stejně kvalitní úrovni, jako by je řešil člověk s využitím svých intelektuálních schopností.

Související problematika

Principy lidského myšlení – využívání jazykových (nenumerických) modelů

Vlastnosti jazykových formulací – vágnost jazykových pojmů

Využití vágnosti pro efektivní vyvozování závěrů lidských úvah

Počítačová formalizace vágních jazykových pojmů – změna paradigmatu

Forma jazykových modelů

Logické přístupy a algoritmy pro využití jazykových modelů k simulaci

ZNALOSTNÍ MODELY FUZZY - LOGICKÉ

Problém

- počítačová formalizace mentálního expertního modelu - nalezení vhodných procedur, které při respektování konkrétních dat

dovedou vyvodit stejně kvalitní závěry jako expert.

V kurzu bude uvedena metodika editace a použití jazykových modelů, využívajících

- k počítačové formalizaci slovních pojmů přístupů fuzzy množinové matematiky - k editaci a aplikaci takových fuzzy modelů přístupů fuzzy logiky.

Matematická formalizace jazykového pojmu VÍKEND

Intervalová definice obyčejná množina VIKEND

Sofistikovaná definice fuzzy množina VIKEND

1,0)( DENVIKEND 1,0)( DENVIKEND

Matematická formalizace jazykového pojmu ROČNÍ OBDOBÍ

Intervalová definice obyčejná množina ROCNI OBDOBI

Sofistikovaná definice fuzzy množina ROCNI OBDOBI

1,0)( MESICOBDOBI 1,0)( MESICOBDOBI

Numerická proměnnáVÝŠKA ČLOVĚKA

Jazyková proměnnáVÝŠKA ČLOVĚKA

Počítačová reprezentace fuzzy množin v počítači aproximovaných lomenými přímkami

A B

A : [30 6,0 6,0 8,0] B: [1,0 4,0 6,0 8,0]

Procedura fuzzifikace

využití fuzzy množin pro jazykovou proměnnou VÝŠE NÁKLADU

Nakl = 110tis Kč

Jazykové fuzzy pravidlo IF-THEN jednorozměrné funkce y = f(x) modelutypu MAMDANI

IF (x is A) THEN (y is B)

Příklad jazykových pravidel jazykového modelu závislosti délky brzdné dráhy vozidlana jeho okamžité rychlosti

IF (RYCHLOST is VYSOKA) THEN (BRZDNA DRAHA is DLOUHA)

IF (RYCHLOST is STREDNI) THEN (BRZDNA DRAHA is STREDNI)

IF (RYCHLOST is NIZKA) THEN (BRZDNA DRAHA is KRATKA)

R1: IF (x1 is A11) and (x2 is A21) and … and (xn is An1 ) THEN (y is B1 )R2: IF (x1 is A12) and (x2 is A22) and … and (xn is An2 ) THEN (y is B2 )

.

.RR: IF (x1 is A1R) and (x2 is A2R) and … and (xn is AnR ) THEN (y is BR )

Obecný jazykový fuzzy model soustavy s n vstupy a jedním výstupem

)...,( ,21 nxxxfy

Dvourozměrný jazykový fuzzy model stanovení výše spropitného TIP na kvaliě obsluhy SERVICE a kvaitě jídla FOOD

VÝŠE SPROPITNÉHO = f(KVALITA OBSLUHY, KVALITA JÍDLA)

Vstupní proměnné

SERVICE [0 - 10] POOR MizernýGOOD DobrýEXCELENT Výborný

FOOD [0 - 10] RANCID NechutnýDELICIOUS Chutný

Výstupní proměnná

TIP [0 – 25%] CHEAP NízkýAVERAGE PrůměrnýGENEROUS Velkorysý

Jazykové fuzzy pravidlo IF-THEN a jeho evaluace fuzzifikací

If (SERVICE is EXCELENT) and (FOOD is DELICIOUS) Then (TIP is GENEROUS)

Blokové schéma fuzzy systému pro podporu rozhodování

Procedura defuzzifikace

Expertní znalostní systém diagnostický

Expertní znalostní systém plánovací

Systém MATLAB Fuzzy ToolBox

SAMOUČICÍ SE MODELYUMĚLÉ NEURONOVÉ SÍTĚ

UMĚLÉ NEURONOVÉ SÍTĚ

Hlavním úkolem je simulovat a implementovat některé funkce lidského mozku, především schopnost vytváření modelů procesem učení.

Matematický model neuronu - perceptron

nixwn

iii ,...,1,

1

Aktivační funkce

Sz

Přenosová funkce

Vícevrstvá neuronová síť

x1 x2

y

Modelovaná funkce: y = f(x1, x2)

wjk k

wik

j

k

Sigmoidní přenosová funkce:

Přenos neuronové sítě je určen:

topologií sítě – počet vrstev a jejich neuronůparametry sítě

Parametry neuronové sítě:

- váhové koeficienty vazeb neuronů wjk < 0, 1 >- prahové hodnoty Θ- parametry přenosové funkce S

exp1

1S

n

iii xwSz

1

Proces učení neuronové sítě

automatické nastavení parametrů sítě k dosažení požadovaného přenosu f(x)pomocí na reálné soustavě naměřené tréninkové vstup/výstupní množiny dat. Uvažujme tréninkovou množinu s K- vzory

0K

003

02

01K

03

03

033

023

013

02

02

032

022

012

01

01

031

021

011

y;,...,,,

.

.

y;,...,,,

y;,...,,,

y;,...,,,

nKKK

n

n

n

xxxx

xxxx

xxxx

xxxx

Procedura učení – optimalizační gradientní algoritmus Back-Propagation (BP)

Strategie optimalizace min2

1

1

2*0

K

jjjn yyE

Adaptace váhyw(t)

E w(t)1)( n

tw 1,0

Proces vytvoření (adaptace) neuronové sítě jako modelu soustavy y=f(x)

- návrh topologie sítě

- naměření tréninkové datové množiny na soustavě

- fáze učení sítě – algoritmus BP

- fáze využívání sítě jako modelu soustavy

OPTIMALIZACE MODELUGENETICKÉ ALGORITMY

GENETICKÉ ALGORITMY

Představují umělé napodobení procesů, které jsou základem utváření charakteru jedince v populaci a mechanizmu dědění jeho vlastností v potomstvu. Jsou to vyhledávací algoritmy, založené na principech biologické evoluce a na mechanizmu přirozeného výběru. Obecně jsou určeny k vyhledávání optimálních řešení různých problémů.

OPTIMALIZACE SOUSTAVY NASTAVENÍM HODNOT JEJÍCH PARAMETRU

Základem pro operace GA je znakový řetězec, v němž jsou tyto měnitelné parametry (určující vlastnosti soustavy) zakódovány. Tento řetězec je, ve shodě se svým biologickým vzorem, nazván chromozomem. Příkladem je chromozom, představující jeden parametr soustavy, zakódovaný pomocí binárního kódu do pětibitového řetězce nul a jedniček

p: [0 1 1 0 1]

který reprezentuje dekadickou hodnotu p = 13.

Každý chromozom populace je vybaven fitness hodnotou. která vyjadřuje míru přiblížení se chromosomu optimálnímu. Fitness hodnota chromozomu je dána hodnotou účelové funkce optimalizační procedury.

Množina chromozomů je nazývána populací.

PROCEDURA GENETICKÉ OPTIMALIZACE

– vyhledávání optimálních hodnot parametrů soustavy – probíhá po krocích. V každém kroku tvoří příslušná populace tzv. generaci chromozomů. Nová generace chromozomů vzniká reprodukcí populace.

V procesu tvorby nové generace chromozomů se používá GA mechanizmy, umožňují modifikaci chromozomů pomocí tří operací

- operace reprodukce,- operace křížení,- operace mutace.

Operace reprodukce

je proces, při němž jsou jednotlivé chromozomy kopírovány do nové populace podle velikosti jejich fitness hodnoty. Čím je její velikost vyšší, tím má chromozomvětší pravděpodobnost přežití, tj. výběru do další generace chromozomů. Tím jsou "dobrá" řešení vybírána pro další reprodukci a "špatná" jsou eliminována.

0 1 1 0 1 F = 56

0 0 1 1 1 F = 64

P = 25

P = 13

Operace křížení

umožňuje rekombinaci částí vybraných párů chromozomů (rodiče)a vznik dvounových párů (potomci). Tento proces je tvořen dvěma kroky:

- v prvním jsou vybrány náhodné páry dvou chromozomů,- ve druhém je realizován vlastní proces výměny informace křížením.

Operace mutace

Touto procedurou je změněna hodnota vybraných bitů vybraných chromozomů z 1 na 0 nebo opačně.

Průběh procedury GA

1. Definice optimalizační úlohy a tvaru účelové (fitness) funkce 2. Rozhodnutí o způsobu kódování chromozomů3. Stanovení parametrů křížení a mutace 4. Stanovení způsobu výběru chromozomů do nové populace3. Vygenerování nulté (výchozí) populace chromozomů4. Výpočet hodnot fitness funkcí chromozomů populace5. Aplikace operací křížení a mutace - vygenerování potomků6. Výpočet hodnot fitness funkcí chromozomů potomků7. Výběr chromozomů do nové populace8. Opakování procedury od bodu ad 4)9. Rozhodnutí o ukončení procedury GA

Ukončení procesu genetické optimalizace

- realizace určitého počtu kroků GA (generací) – předepsaný max čas

- nalezení chromozomu s dostatečnou velikostí fitness funkce (nalezení vyhovujícího řešení optimalizační úlohy) - konvergence

1. Úloha optimalizace složitosti výrobku

Ukazatel užitná hodnota/cena = f(cena výrobku, užitná hodnota)

2. Úloha hledání minima dvojrozměrné funkce

Struktura chromozomu – souřadnice x, y

souřadnice x souřadnice y

0 1 0 1 1 1 0 0 1 0

minyxfzJ ),(

Fitness funkce J

Průběh a výsledek minimalizační procedury

Souřadnice minima: x = -4,712 y = 0Extrém (minimum) fitness funkce Jmin = zmin = -1,999999237060392

3, Úloha obchodního cestujícího

- obchodní cestující musí navštívit každé ze 40 měst- minimalizace cestovních nákladů - trasa musí být nejkratší možná- každé město může být navštíveno pouze jednou

Struktura chromozomu – vektor posloupnosti navštívených měst Mk na trase

M1 M2 M3 . Mk. . . M38 M39 M40

min... 40,3939,383,22,1 labelblabelblabelblabelblabelblabelblabelblabelb distdistdistdistJ

b1 b2 b3 bk b38 b39 b40

Fitness funkce J – celková délka ujeté trasy – minimalizace

Počet kroků při slepém prohledávání úplného prostoru řešení (počet permutací)

478.10!

40

n

n

Výsledná optimální trajektorie