Fuzzy-rendszerek. Fuzzy halmazm veletek. Fuzzy logika m veletek. Borgulya I. PTE KTK 2. 1.Fuzzy rendszerekr l általában

1.Fuzzy rendszerekrl általában

Fuzzy-rendszerek

Fuzzy-rendszerek

Témák Fuzzy rendszerekrl általában Fuzzy halmazelmélet

1. 2.

Fuzzy halmazmveletek

Fuzzy logika

3.

Fuzzy rendszerekrl általában

Fuzzy logika mveletek

Borgulya I. PTE KTK

1


Fuzzy közelít következtetés

4.

Borgulya I. PTE KTK

2

Borgulya I. PTE KTK

A bizonytalanság jellege: determinisztikus bizonytalanság (többérték) Fuzzy technika (Zadeh 65) „hozzátartozás foka”: elem halmazhoz tartozása

Fuzzy halmazelmélet klasszikus halmazelmélet A= {x | x> 120}

~Igazságfok (predikátummal)

A technika alapja:

Tagsági/ karakterisztikus függvénye

életlen, fuzzy halmazok: hozzátartozás foka

1

fuzzy halmazelmélet, fuzzy logika

fuzzy rendszer: halmaz- halmaz leképezés Ai o Bi formájú leképezéseket aggregál alacsony középm. magas

Neurális háló és fuzzy rendszer leképezés Borgulya I. PTE KTK

4

2.Fuzzy halmazelmélet

3



Fuzzy információ nem precíz, pontatlan kifejezések (ids ember, magas nyereség) bizonytalan információkon alapuló kif. (hitelképes vállalat) életlen relációk (körülbelül egyenl) Elfordulás mat. modellek, döntések, adatok analízise

Borgulya I. PTE KTK

5


Tagsági / tartalmazási függvény: μ :x ---> [0,1] Megadási formák:

Borgulya I. PTE KTK


Mveletek

Mveletek

Legyen A, B fuzzy halmaz, PA(x), PB(x) tart. függv. Aritmetikai mveletek: C=A°B (° lehet + - / *)

Legyen A, B fuzzy halmaz, PA(x), PB(x) tart. függv. Halmazmüv.:

Borgulya I. PTE KTK

7

Halmazmveletek:

metszet (minimum operátor) PA^B(x)= min (( PA(x), PB(x))

Borgulya I. PTE KTK

6

8

egyesítés (maximum operátor) PAvB(x)= max (( PA(x), PB(x)) szorzat PAB(x)= PA(x)* PB(x) Komlemens PA(x)= 1 - PA(x)

T-norma S-norma mvelettel definiálás Metszet: Borgulya I. PTE KTK

9

2.Fuzzy halmazelmélet T-norma


S-norma mveletek

Fuzzy reláció

R = ^((x1,x2,.,xn), PR (x1,x2, .,xn)) _ (x1,x2,.,xn) X1 x X2 x .. x Xn)` PR : x1,x2, ...,xn o [0,1] Példa:


(kartézi szorzat részhalmaz)

Reláció mveletek

Borgulya I. PTE KTK

10

Borgulya I. PTE KTK

projekció, cilindrikus kiterjesztés max-min kompozíció R1 és R2 max-min kompozíciója X,Y felett egy R fuzzy reláció: R = R1 qR2 = ^((x,z), supy min (PR1 (x,y), PR2 (y,z)) _ xX, yY, zZ`.

11

Borgulya I. PTE KTK

12

2.Fuzzy halmazelmélet 2.Fuzzy halmazelmélet


Kiterjesztési elv

Az f: X1 x X2 x ... x Xn o Y leképezés egy

Kiterjesztési elv ---- fuzzy aritmetika pl. egész számok körében f(x) = x+5 fuzzy: f*(x): „Körülbelül 3” + 5 (= „körülberül 8”)

f*:A1xA2x...xAn-->B kiterjesztése egy fuzzy halmaz Y felett:

Eredményhalmaz: 5 + { 0.4/1+ 0.8/2+ 1.0/3 + 0.8/4 +0.4/5} = { 0.4/6+ 0.8/7+ 1.0/8 + 0.8/9 +0.4/10}

ahol B= f*(A1,A2,...,An)= ³ PB (y) /y PB (y) =sup min (PA1 (x1), PA2 (x2), ... , PAn (xn) (x1, x2, ...,xn) f--1 (y)

Köv: a matematika módszerek kiterjeszthetk fuzzy –halmazokra.

Borgulya I. PTE KTK

13

Borgulya I. PTE KTK


3.Fuzzy logika

Néhány definíció tartóhalmaz, D-nívóhalmaz (szelet), normalizált, Konvex fuzzy szám

Borgulya I. PTE KTK

15

Borgulya I. PTE KTK

18

3.Fuzzy logika

Fuzzy logika

cél: emberi gondolodás modellezése összetett, bizonytalanságot tart. felt. esetén Jellemzk pl.

Nyelvi változó pl.

(konvex, normalizált, egy helyen 1 max., szakszonként folyt)

fuzzy intervallum

14

(fuzzy szám, egy intervallumon max. értékeket vesz fel és szak. folytonos) Borgulya I. PTE KTK

16

fuzzy halmazokon megfogalmazott kif.: =predikátum Igazságtérben a log. értékek fuzzy halmazok nyelvi változó számtalan kvantor logikai értékek: fuzzy halmazok (igazságtér) fuzzy következtetés: közelít, nem precíz Borgulya I. PTE KTK

17

3.Fuzzy logika

3.Fuzzy logika

nyelvi változók definició: ( név, T(N)terms halmaz, X,S,M)

T(N) terms halmaz (értékek elnevezése) X alaphalmaz, S szinataktikai szabály

M szemantikai szababály

nagyon μA(x)^2 többé kevésbé μA(x)^0.5 mveletek: AND, OR, ... több változat Igazságtér:

véges / végtelen pl. 9 elem (Igaz ..)

fuzzy halmaz def. Kiterjesztési elv alapján generálás

19

Borgulya I. PTE KTK

3.Fuzzy logika

20

Borgulya I. PTE KTK

21

23

Borgulya I. PTE KTK

24

3.Fuzzy logika

Szokásos mveletek:

módosítók

képzési szab.

Borgulya I. PTE KTK

3.Fuzzy logika

Fuzzy logika müvelet csoportok elemi mveletek továbbfejlesztései T-norma mv. (minimum, algebrai szorzat, Einstein-szorzat, …) „konjunkció”

gyakorlat: igazságtér pontérték (kevesebb számolás) pl.: μC(x)= min( μA(x), μB(x)) Borgulya I. PTE KTK

22

Borgulya I. PTE KTK

3.Fuzzy logika

3.Fuzzy logika

S-norma mv. (maximum , algebrai összeg, ..) „diszjunkció” mveletek

3.Fuzzy logika

Paraméteres mveletek: és, vagy mvelethez hasonlók

Paraméteres T-norma mv.: pl.

Kompenzációs müv. (és -vagy közti mv.) kritériumok egymás hatásait kompenzálhatják, szituáció modellezés: T és S norma közti mveletek.

Pl.

Borgulya I. PTE KTK

25

Paraméteres S-norma mv.: pl. Yager egyesítés mvelete Jt1 PC (x) = min (1, (PA(x) J+ PB (x) J)1/J)

Borgulya I. PTE KTK

26

Borgulya I. PTE KTK

27

3.Fuzzy logika

3.Fuzzy logika

Fuzzy közelít következtetés az általánosított modus ponens szimbolikus alakja:

Fuzzy közelít következtetés példa:

A o B, A’ B’ = A’ q (A o B)

ahol q a max-min a komp. PB’ (v) = max min (PA’(u), PAoB (u,v)) Változatok: implikációra, kompozícióra max-min köv.: implikáció: minimum és max-min kompozíció max-szorzat köv.: implikáció: algebrai szorzat és max-min kompozíció

Max-min köv.: Max-szorzat:

Borgulya I. PTE KTK

28

3.Fuzzy logika

Borgulya I. PTE KTK

29

Max-min és max-szorzat következtetés

Borgulya I. PTE KTK

Fuzzy-rendszerek

Fuzzy szabály, diagram f*: IF X is A1 THEN Y is B1 ………………………………….. IF X is An THEN Y is Bn Szabályok együtt -- diagram:

31

Gyakori fuzzy-rendszer modellek

Borgulya I. PTE KTK

32

Fuzzy-rendszerek

1

1. Az általános fuzzy rendszer

1. Az általános fuzzy rendszer

Témakörök

Gyakori fuzzy-rendszer modellek

Fuzzy rendszer típusok Fuzzy szabályozó

Borgulya I. PTE KTK

Fuzzy rendszerek

Fuzzy rendszerek

30

3.Fuzzy logika

Borgulya I. PTE KTK

fejleszt

Mamdani, Sugeno típus

felhasználó

inp.

FR

outp.

Szabályalapú rendszerek

felhasználó

Fuzzy reláció egyenletrendszer Produkciós rendszerek Hibrid rendszerek

eljárás

Hibrid rendszerek

Borgulya I. PTE KTK

2

Borgulya I. PTE KTK

3

fuzzy szabályozó, reláció egyenletrendszer, produkciós rendszerek neurofuzzy: kooperatív,hibrid; fuzzy neurális hálózat fuzzy SZR Borgulya I. PTE KTK

4

2. Fuzzy szabályozók

2. Fuzzy szabályozók 2. Fuzzy szabályozók Fuzzy szabályozók

Felépítés:

fuzzy szabályok fuzzy halmazok, mv.

Fuzzifikálás

fuzzifikálás tudásbázis - Fuzzy szabályok : - két típus Mamdani modell (diagram) (wi) IF x1 is A1 AND … xn is An THEN y is Bj CF

Fuzzifikálás

köv. mechanizmus defuzzifikálás

Sugano (TSK-) modell r: IF x1 is A1 AND... xn is An THEN y = fr( x1,x2, ...,xn) ált.: y = a0r+ a1r x1+ ... + anr xn

input

output Borgulya I. PTE KTK

5

Borgulya I. PTE KTK


Borgulya I. PTE KTK


Fuzzy szabályozók

6

2. Fuzzy szabályozók Következtetés Mamdani modellnél

Fuzzy szabályozók

nyelvi változók (tartalmazási függv.: háromszög, Gauss, trapéz,…)

7

Szabályok párhuzamos kiértékelése Eredményhalmazok uniója (vagy, wi *) A B output változó B1, B2, … Bn értékeinél

B’= B’1+ B’2+… +B’n Defuzzifikálás: egy valós szám

defuzifikálás

Pl.

Borgulya I. PTE KTK

8

Borgulya I. PTE KTK


9

Borgulya I. PTE KTK



Következtetés Mamdani modellnél If X is A then Y is A If X is B then Y is B. Input: A*=1.3

Következtetés a Sugeno modellnél Szabályok párhuzamos kiértékelése r-edik szabálynál: fr(x1, x2, …, xn) és a „súlya”: PRr (x1,x2, ...,xn ) = Pr1 (x1) ^...^Prn(xn)

1.Szabály eredmény 2.Szabály eredmény

n

y

f (x)

r 1

Rr

( x 1 , x 2 ,..., xn ) f r ( x 1 , x 2 ,..., xn ) n

¦P i 1

Borgulya I. PTE KTK

11

Sugeno példa:if input is low then output is line1 if input is high then output is line2

Output: „defuzzifikálással”

¦P defuzzifikálás: pl. COG

10

Rr

( x 1 , x 2 ,..., xn )

Borgulya I. PTE KTK

12

Borgulya I. PTE KTK

13

3. Fuzzy reláció egyenletrendszer

4. Fuzzy produkciós rendszerek


Reláció egyenletrendszer AoB szabály (implikáció) értelmezhet mint-- B = A q R reláció a szabályrendszer: Bi = Ai q R (i=1,2,...,n). Akkor oldható meg, ha az

Fuzzy produkciós rendszerek Szabályrendszer, következtetési mechanizmus +bizonytalan adatok (fuzzy halmazok /lehetségességi eloszlások) Az FPR felépítése: tudásbázis, ismeretszerz modul, munkamemória, következtet mech., magyarázó modul, felh. interfész (SZR szabályformalizmus ) Következtetés: adatvezérelt (soros, párhuzamos, hasonlóságon alapuló ), célvezérelt, kombinált

Adatvezérelt köv.: munkamemória fuzzy szabályok

n

R

Ai o Bi i 1

megoldása a rendszernek Borgulya I. PTE KTK

14

Borgulya I. PTE KTK


Borgulya I. PTE KTK

16

Pl. SYTEM Z-11 célvezérelt következtetése: Lehet: éles-, fuzzy tény, CF faktor Következtet séma: számítása:

18

Borgulya I. PTE KTK

19

21

Borgulya I. PTE KTK

22

5. Hibrid fuzzy rendszerek

Pl. SYTEM Z-11 célvezérelt következtetése: Összetett következtet séma:

Hibrid rendszerek

Borgulya I. PTE KTK

Hasonlóság képlet: R* meghatározása: legnagyobb S(A,B) érték szabály néhány legnagyobb s- érték sz., s(A,B)> limitet teljesítk Pontérték tagsági függvények Következmény számolás:

17


Borgulya I. PTE KTK


Pl. Fuzzy Toolbox (Turksen, Zwang) adatvezélet következtetése hasonlósági mértékkel:

Szabályok: n db. If A is Aj Then B is Bj; Input: A*1, A*2,…A*n lépések

Borgulya I. PTE KTK

15


Pl. Fuzzy Toolbox (Turksen, Zwang) adatvezélet következtetése hasonlósági mértékkel:

illeszkedésvizsgálat konfliktushalmaz képzése (lehet ellentmondó) konfliktus feloldás (kiválasztás) szabályok végrehajtása (eredmény a munkamemóriába)

20

Fuzzy SZR (fuzzy technika adaptálása) (REVEAL, CLIFS) Neurofuzzy rendszerek kooperatív offline kapcs. (f. szabályok, f. halmazok ) online kapcs. (f. halmaz paraméter, f.szabály súly módosítás)

Borgulya I. PTE KTK

5. Hibrid fuzzy rendszerek 1. mintapélda

hibrid neurofuzzy r.

Fuzzy mintapéldák MATLAB fuzzy tools

Készítsünk egy Mamdani típusú fuzzy szabályozót, amely javaslatot tesz arra, hogy egy étteremben hány % borravalót adjunk a pincérnek.

fuzzy neurális hálózat (f. input, f. neuron, mat. mvelet helyett: f. relációk, f. mveletek) Borgulya I. PTE KTK

23

1. mintapélda

Borgulya I. PTE KTK

Borgulya I. PTE KTK

Borgulya I. PTE KTK

1

1. mintapélda

3

1. mintapélda

Borgulya I. PTE KTK

4

Borgulya I. PTE KTK

1. mintapélda

6

Borgulya I. PTE KTK

2

1. mintapélda

5

1. mintapélda

Borgulya I. PTE KTK

Döntési szempontok: a.) a borravaló csak a kiszolgálás minségétl függ (0-10 pont) b.) az étel minsége is befolyásolja (0-10 pont)

7

Újabb szempont: az étel minsége

Borgulya I. PTE KTK

8

1. mintapélda

1. mintapélda

2. mintapélda

Sugeno modellel függvények közelítése

Borgulya I. PTE KTK

9

Borgulya I. PTE KTK

2. mintapélda

Borgulya I. PTE KTK

Borgulya I. PTE KTK

2. mintapélda

12

Borgulya I. PTE KTK

2. mintapélda

15

13

Borgulya I. PTE KTK

14

2. mintapélda

3D felület:

Borgulya I. PTE KTK

11

2. mintapélda

2. mintapélda

Borgulya I. PTE KTK

10

Kétváltozós függvény (parabola) Háromváltozós felület közelítés

16

3D felület:

Borgulya I. PTE KTK

17

2. mintapélda

2. mintapélda

Fuzzy szakérti rendszer fejlesztés

3D felület:

XpertRule Knowledge Builder 3-4. Gyakorló feladat (két fuzzy példa)

Borgulya I. PTE KTK

18

Borgulya I. PTE KTK

XpertRule, 3. gyakorló feladat

Körülbelüli értékekkel dolgozik: fuzzy objektumok az életkor, jövedelem, eredmémy (risk)

Borgulya I. KTK GI

2

Borgulya I. KTK GI


3

5

Borgulya I. KTK GI

4

A megvalósítás lépései:

hitel_kockázat (fuzzy)

Borgulya I. KTK GI

Életkor (fuzzy)


Attribútum értékek definiálása (Ins. Property):

Jövedelem (fuzzy)

Borgulya I. KTK GI







Új projekt létrehozás: varázslóval Access adatbázis hozzárendelés (felhasználói névvel, jelszóval) Új tudás modul definiálás (itt: hitel kockázat) Attribútumok definiálása: életkor_év (numerikus), életkor (fuzzy), jövedelem (fuzzy), jövedelem_Ft (num.), hitel_kockázat (fuzzy).

1



Egy banki SZR egy személynél megállapítja a hitelezés kockázatát: alcsony, átlagos, vagy magas. Döntési szempontok: életkor, jövedelem

Borgulya I. KTK GI


A feladat: „Hitel kockázat”

19

6

Attribútum értékek definiálása (Ins. Property): hitel_kockázat (fuzzy)+ „tudás” (döntési fa):

Borgulya I. KTK GI

7


XpertRule, 3. gyakorló feladat A megvalósítás lépései:


A futtatás lépései, megjelen kérdések és riport pl.:

A végrehajtás szabályozása (fprogram):

A feladat: „Kazán diagnosztika”

A SZR három gyakori hiba „valószínségét” prognosztizálja (vagy azt, hogy nincs hiba) Döntési szempontok: nyomás, hmérséklet

input kor - fuzzy értéke input fizetés – fuzzy ért. fuzzy hitel_kockázat ért. és konvertálása numer.

Körülbelüli értékekkel dolgozik: fuzzy objektumok a nyomás, a hmérséklet Diagnosztikai esetek: a fuzzy szabályok alapjai

+ riport Borgulya I. KTK GI

8

Borgulya I. KTK GI


11

12

Diagnózis: list + esetek –fuzzy szabályok

hmérséklet (fuzzy)

Borgulya I. KTK GI

13



Attribútum értékek definiálása (Ins. Prop.):




nyomás (fuzzy)

Borgulya I. KTK GI




10



Új projekt létrehozás: varázslóval Access adatbázis hozzárendelés (felhasználói névvel, jelszóval) Új tudás modul definiálás (itt: kazán diagnosztika) Attribútumok definiálása: nyomás (fuzzy)- és num. hmérséklet (fuzzy) - és num. diagnózis (list+esetek)

Borgulya I. KTK GI

Borgulya I. KTK GI



9

A futtatás lépései, megjelen kérdések és riport pl.:

A végrehajtás szabályozása (fprogram):

Input nyomás, hmérséklet, fuzzy értékeik, diagnózis értéke, +riport Borgulya I. KTK GI

14

Borgulya I. KTK GI

15

Borgulya I. KTK GI

16

Fuzzy rendszerek alkalmazása

Fuzzy-rendszerek

Gyakori alkalmazások

Problématípusok

Borgulya I. PTE KTK


folyóvízbl ivóvíz 3 tartály, 3-5 órás kezelés tartályonként

2

2

3

Ri. PH AL TE p0 1 K K K 8858 2 K K N -7484 …. 4

1. probléma def., 2. Kritériumok 3. Alternatíva - krit. kapcsolat (mátrix, súlyok) 4. Aggregációs elj. , rendezés (preferencia sorrend, súlyozás…) eredmény: kiválasztás, osztályozás, rendezés

p3 p4 11230 -1147 761 52

p5 -2218 -17

5

a1 a2 a3

A = ^a1,a2, ...,an`, K=^k1,k2,...,km`, g1, g2, ...,gm (6gi = m) Pkj (ai): milyen jó az ai alternatíva a kj szempontjából Számolási lépések:

k2 0.3 0.8 0.6

k3 0.2 0.3 0.8

7

Borgulya I. PTE KTK

Még egy rendez módszer: “Osztályozó m.”

A = ^a1,a2, ...,an`, K=^k1,k2,...,km`, kj = {Sj1,.. Sjpj), ahol Sj1, . . ., Sjpj nyelvi vált. értékek, g1, g2, ...,gm súlyok

k4 0.5 0.1 0.2

(g12) IF k1 is S11 (g12) IF k1 is S12 ………… (gj2) IF kj is Sjs ………… (gm2) IF km is Smpn

g1=2.32, g2=1.2, g3=0.32, g4=0.16, pl. Pk3 (a2)=0.3 PD (a1) = min ~ P kj(a1) = min ^0.44, 0.24, 0.6, 0.9 ` =0.24. PD (a2) = min ~ P kj(a2) = min ^0.2, 0.76, 0.68, 0.69` =0.2 PD (a3) = min ~ P kj(a3) = min ^0.12, 0.54, 0.93, 0.72` =0.12 Az optimális megoldás: aA. PD (a) = max ^PD (a1) , PD (a2) PD (a3`) =0.24 = PD (a1)

aPkj(ai) = [Pkj(ai) ] gj minden aiA-ra. Legyen D a döntési tér: PD(ai) = min ~Pkj(ai) j=1,2,...,m. (aggregálás min mvelettel) eredmény: PD(a*) = max PD(ai) aiA.

6


Példa Yager módszerére k1 0.7 0.5 0.4

Fuzzy módszerek 3-4-ben Borgulya I. PTE KTK


Rendez módszerek Yager “max-min” módszere

Borgulya I. PTE KTK

p2 -8093 -427

Borgulya I. PTE KTK


p1 2664 124

3

Döntések fuzzy környezetben Döntéshozatal: alapprobléma, többkrit. döntések MCDM lépései:

Víztisztító példája Sugeno-modell 8 szabállyal THEN T1= p0 + p1* x4 + p2*x5 + p3*x1 +p4*x2 +p5*x3. (ahol x1, x2, …,x5: PH, AL, TE, SZ1, SZ2) pi: becslés, függv. illesztés (40 elem példasor ismert)

Hipotézis: 1. tartály T1 vízmennyiségét kell szabályozni. Jellemzk: AL(lúgosság), PH, TE (hm.), kétféle szennyezettség fok ( SZ1 - SZ2 ) (fuzzy termek: kicsi, nagy minden változónál)

Borgulya I. PTE KTK

Borgulya I. PTE KTK


Ri: IF A is x1 AND B is x2 AND C is x3 1

Víztisztító példája


Víztisztító példája folyóvíz

Fuzzy szabályozó: ipari szab. -(univ. függv. köz.) Ipari példák: (gzgép, cementéget, metró, házt. gépek, szennyvíztisztító, blokkolásgátló, …)

szabályozás (ipari ) közelít köv. (fuzzy SZR) döntések fuzzy környezetben adatanalízis (osztályozás, klaszterképzés) információ visszakeresés (adatbázisból ) optimalizálás (fuzzy aritmetika, …) képfeldolgozás, ...

Borgulya I. PTE KTK

1

Szabályozás

(közlekedés, autóipar,

háztartási elektronika, ipari robot, gazd. élet,)

Alkalmazások I.


THEN E = S11 THEN E = S12 THEN E = Sjs THEN E = Smpm

(s=1,2, …,pj) (j = 1, 2, . . ., m )

8

Borgulya I. PTE KTK

9



Még egy rendez módszer: “Osztályozó m.”

Alternatívák a. üzleti élet optimalizálása általában b. mezgazdaság optimalizálása c. nagyobb terület vízzel elárasztása d. részlegesen területek vízzel elárasztása, megtartva a jelenlegi mezgazdasági termelést e. részlegesen területek vízzel elárasztása, optimalizálva a mezgazdasági termelést.

szabályozó: 6pji darab szabály minden ai-hez egy érték (“osztályzat”) rendezi az alternatívákat (eltérés a Yager max-min-tl: nyelvi változó értékeket alkalmaz)

Mintapélda: Po-delta nemzeti park hasznosításának problémája. Borgulya I. PTE KTK

10

Borgulya I. PTE KTK


k2 k3 k4 k5 k6

8 rossz mérs. rossz mérs.

2. 3. 4. 5. 6.

11

13

nagy nyereség; foglalkoztatás növelése; turisztikai vonzer növelése; pihenésre, szórakozásra vonzer növelés; a táj ökológiai egyensúlya, az ökológiai károk okozta veszély csökkentése.

Borgulya I. PTE KTK

12

Fuzzy rendszerek alkalmazása Függvényközelítés, prognózis

b 159.m.

c közel. 143.m. 20 9 rossz jó mérsékelt jó rossz jó rossz jó

d közel 95.m. 8 mérsékelt mérsékelt jó rossz

e közel. 147.m. 14 mérsékelt mérsékelt mérsékelt rossz

eredmény: e>c>b>d>a lobbik hatása: c. Borgulya I. PTE KTK


14

Példa: folyó árhullám elrejelzés (6 óraval, Mosel) Adott: d(t) vízmennyiség idsorok (11 áradás adatai) NH modell: vízmennyiség változás idsor idablak (n adat, n+1-dik becslése) backpropagation modell (20-10-10-1) csak átlagosan jó Borgulya I. PTE KTK

15


Függvényközelítés, prognózis

Függvényközelítés, prognózis

FR modell szakérti vélemény: do (t) = do (t- 6) + 'do (t),

'do (t) = f('d1 (t - 't1), 'd2 (t- 't2), ... ,'dn (t- 'tn)),

ahol 'di az i-dik idsor vízmennyiség változása 3, 6 és 9 óránként. Sugeno modell do (t) -re

16

Fuzzy-rendszerek

Sugeno modell do (t) -re Ri: if x1 is Ai1 and … xn is Ain then yi=pi0+ pi1*x1+ …+ pin*xn

Borgulya I. PTE KTK

1.

Adatok:

a k1 64. m.

Kritériumok


Tartalmazási függvények:

Borgulya I. PTE KTK


Alkalmazások II.

Input tér particionálás: klaszterezéssel Ai-k Külön szabályok minden idsorra (folyóra) (p0, p1, …pn optimalizálása függvény illesztéssel) 'ti optimalizálása

Eredmény: jobb mint a szakértké Borgulya I. PTE KTK

17

Borgulya I. KTK GI

1



Adatanalízis Fuzzy klaszteranalízis Fuzzy osztályozás Alkalmazási példa: függvényközelítés

Borgulya I. KTK GI

2


Adatanalízis

Fuzzy klaszteranalízis

Lépések: 1. Gyakoriságok, szelektálás 2. Mintafelismerés 3. mat. modellezés (funk. kapcsolatok) 4. Elemzés, értékelés Pl. 2. lépcs: Fuzzy klaszteranalízis Pl. 3. lépcs: Fuzzy osztályozás, fuzzy shell klaszter algoritmusok, szabályfelismerés

Borgulya I. KTK GI

3


megállás: uik stabil Gustafson-Kessel alg.,lineáris klaszter elj., shell klaszter eljárások…. Borgulya I. KTK GI

4


Fuzzy klaszteranalízis

Fuzzy c-Means-algoritmus o(x, u,v)= 66uikm d(vk,xi)2 minimum keresés 6uik >0 (k=1, ..,n) 6uik =1 (i=1,…,c) uik =1/(6( d(vi,xk) / d(vj,xk))(1/(m-1)) vi= 6(uim xi )/ (6uikm )

Fuzzy-osztályozás

Fuzzy c-Means-algoritmus

Kitekintés: minta osztályozás - csoportosítás

tudásábrázolás (explicit, implicit) tanulási mód (supervised, unsup.) minta tulajdonság ( numerikus, heterogén)

Tudásábrázolás Implicit: statisztika (diszkrim fg., kovariancia m., hasonlóság , val. érték) Bayes régió, potenciál fg.,NH F(minta) oosztály tartalmazási fg érték.

Borgulya I. KTK GI

5


Borgulya I. KTK GI

6


Borgulya I. KTK GI

7

Fuzzy rendszerek alkalmazása IRIS adatsor: a generált szabályok a következk:

Fuzzy-osztályozás

NEFCLASS: egy neurofuzzy osztályozó

Tudásábrázolás Explicit: If- then.., frame, log. kifejezések. Tudásalapú: szabályalapú (szabály – osztály kapcs.) hierarchikus osztályozók Optimalizálás - tanítás explicit esetnél evoluciós algorimusok segítségével NH közremködéssel fuzzy NH-val elállítás neurofuzzy rendszerrel Tanulóalgoritmussal finomítás

Borgulya I. KTK GI

R1: IF X1 is S AND X2 is M AND X3 is S AND X4 is S THEN osztály is 1; R2: IF X1 is L AND X2 is M AND X3 is M AND X4 is M THEN osztály is 2; … R7: ...

Pl. 2 input adat x1 (u1,u2,u3) x2 (u4,u5 u6) c1, c2 osztályok 8

Borgulya I. KTK GI

9

Borgulya I. KTK GI

10



1.

Yager-Filev módszere

2.

mountain clastering eljárás két lépcs: induló szabályhalmaz finomítás (optimalizálás) közelítési forma: bázisfüggvényekkel (gauss)

Borgulya I. KTK GI

Fuzzy szabályozó kialakítás adatok alapján

Fuzzy szabályozó kialakítás adatok alapján Montain Clustering algoritmus (Yager-Filev)

Fuzzy szabályozó kialakítás adatok alapján


3.

Yager-Filev módszere Input: x1, x2, …, xn, y minden klaszterre egy szabály: IF x1 is Br1 AND … AND xn is Brn THEN y is Dr r=1,2,…,m és, (cr1 cr2,…, crn, cr) az r-dik centrum Brl (xil) = exp(-1/Vrl2 (xil-crl)2) Dr (y) = exp(-1/V2 (y-cr)2) y-ra kifejezve egy adott input x1k,… xrk esetén: Y= (6m ci* exp( - 6r 1/Vij2 (xjk-cij)2)) / (6m exp( - 6r 1/Vrl2 (xjk-cij)2) )

2 dim. rács (térbeli): Nij lehetséges centrumok Mi montain fg. Nij-ben M1 (Nij)= 6 e^(-a* d(Nki,Njk)) (a konstans) Centrum választás: M1* =max M1(Nij) , (Njj* a rácspont) M2(Ni)= M1 (Ni)- M1* e^(-b* d(Nj,Nk)) M2o M1 Vége ha M1*
Klaszterek: a kiválasztott centrumok

Finomítás: centrumok, szórások tanuló algoritmussal 11

Borgulya I. KTK GI

12

Borgulya I. KTK GI

13

Hitel kockázat becslés Feladat: Az FT Investment Bank ügyfelei adatbázisából megfelel ügyfeleket kíván választani egy közvetlen levelezési kampányhoz. A kiválasztás marketing szakértk ismeretei alapján történik (hitelképes ügyfeleknek írnak).

Fuzzy mintapéldák FuzzyTech 5.54 alkalmazása

Borgulya I. KTK GI

14

Borgulya I. PTE KTK

1

Hitel kockázat becslés

Hitel kockázat becslés

Megoldás: Egy Access adatbázis menübl érhetk el a szolgáltatások (f rlap)

Ügyfél elemzés fuzzyTech segítségével: 3 szabálybázis Pénzügyi felt. elemz (input: jövedelem költés, valós vagyon+teher/hitel) Személyi felt. elemz (input: kor, gyerekek száma, házas) Levelezési kockázat (input: pénzügyi elemzés értéke, személyi elemzés értéke, földrajzidemogfráfiai jellemz)

Ügyfél adatok kezelése egy adatbázisban Földrajzi-demográfiai jellemzk megadása, kezelése Ügyfelek elemzése

Ügyfél elemzés fuzzyTech segítségével:

Pénzügyi feltételek elemzése Személyi feltételek elemzése Levelezési kockázat elemzése Borgulya I. PTE KTK

3

Borgulya I. PTE KTK

4

Borgulya I. PTE KTK

2

Borgulya I. PTE KTK

5

Borgulya I. PTE KTK

6

Borgulya I. PTE KTK

7

Borgulya I. PTE KTK

8

Fuzzy rendszerek generálása: ANFIS használat Egyváltozós függvény illesztés pontokra Demo feladatok Borgulya I. PTE KTK

Borgulya I. PTE KTK

1

2

Borgulya I. PTE KTK

3

A hozzárendelt NH

Generált fuzzy t. függvények

Generált szabályok

Borgulya I. PTE KTK

4

Borgulya I. PTE KTK

5

Borgulya I. PTE KTK

6

A generált fuzzy rendszer eredménye a tanulás eltt. Borgulya I. PTE KTK

7

Borgulya I. PTE KTK

8

Borgulya I. PTE KTK

9

Tanulás után

A közelít függvény Tanulás eltt

Borgulya I. PTE KTK

10

Borgulya I. PTE KTK

11

Borgulya I. PTE KTK

12

Újabb függvényillesztés pontokra

A generált NH (klaszterezéssel)

NH tanulása

Borgulya I. PTE KTK

13

Borgulya I. PTE KTK

14

Borgulya I. PTE KTK

15

Tanulás után

Tanulás eltt

A közelít függvény

Eredmények

Borgulya I. PTE KTK

16

Borgulya I. PTE KTK

17

Borgulya I. PTE KTK

18

Borgulya I. PTE KTK

19

Borgulya I. PTE KTK

20

Borgulya I. PTE KTK

21

Borgulya I. PTE KTK

22

Borgulya I. PTE KTK

23

Borgulya I. PTE KTK

24

IRIS adatok osztályozása - 3 osztály Klaszterezéssel - 4 szabály

Evolúciós algoritmusok Evolúciós algoritmusok

Intelligens szoftverek

Bevezetés EA alapfogalmak, változatok GA, GP, ES, EP technikák Alkalmazások

Ismeret szimbólikus strukturált

szakérti r.

strukturálatlan Borgulya I. PTE KTK

Borgulya I. PTE KTK

1

Evolúciós algoritmus koncepció Populáció

modell

utódok

Modell koncepció alapja

Biológiai evolúció,

Modell koncepció alapja

4

Evolúciós algoritmusok

Borgulya I. PTE KTK

Holland séma elmélet

statisztikai mechanika 7

Borgulya I. PTE KTK

EA általános ciklus

Rekombináció/crossover, mutáció, szelekció

Fitnesz (megoldás értékelésre) generáció

Borgulya I. PTE KTK

6


individum/kromoszóma (egy megoldás) Populáció (megoldás halmaz) szül, utód (régi- új megoldás) keres operátorok (mveletek)

Számítási igény

Borgulya I. PTE KTK

5

EA alapfogalmak

Markov-láncok statisztika döntéselmélete

Lineáris kombináció alapú Valószínségi modell a populáció alapján Valószínségi modell a korábbi populációk alapján


EA: probléma megoldó metaheurisztika EA elméleti háttér (MI - Op.kut.)

Sztochasztikus keres eljárás Tanuló algoritmus Populáció alapú algoritmus, amely információ csereként értelmezi az evolúciót

Matematikai modell

Borgulya I. PTE KTK

Immun rendszer faj információ csere pl. méhek, hangyák

3

Az EA mint módszer

Öröklés (szül – utód), vírusok, baktériumok

Egy biológiai rendszer

Biológiai evolúció, Biológiai rendszer, faj információ csere Matematikai modell

Borgulya I. PTE KTK


fuzzy r. ev. alg neur. háló

Evolúciós algoritmus koncepció

2

numerikus

8

stratégiai par. választása populáció inicializálás individumok értékelése generációs ciklus: szülk választása, autódok generálása utódok értékelése, uj populáció elállítás megállási feltétel eredmény

Borgulya I. PTE KTK

9


Genetikus algoritmusok

EA változatok

genotípus változtatás (kromoszóma vált.)

evolúciós stratégia (ES)

fenotípus vált. (mutáció, rekombináció, det szelekció-- legjobb túlél)

Alap GA lépések generációs ciklus

Holland ‘60, genetikus mech. Optimalizálás individum: kromoszóma= bitsorozat (gensor.) n-változó, kódolásuk

szülk: sztoch. szelekció ( szerencsekerék) utódok: szülk sztoch. választása, rekombináció/crossover/ mutáció, értékelés

szülk utódok Új populáció: az utódok megállási feltétel --- eredmény

Alap GA lépések

evolúciós programozás (EP)

Alap GA

genetikus algoritmusok (GA)

Genetikus algoritmusok

faj fenotip. vált. (mutáció, sztoch. szelekció)

inicializálás 30-500 individum, véletlen ért. értékelés fitnesz ~ célfüggvény generációs ciklus (teljesen új populáció)

Borgulya I. PTE KTK

10

Evulúciós stratégiák

inicializálás értékelés

P pont szórásokkal célfüggvény = fitnesz

Borgulya I. PTE KTK

13

Genetikus programozás

Koza 1992, programkód aut. elállítás individum: generált program (fa-struktúra, változók, fg.-ek, konstansok), LISP programnyelv (mveletek, út., változó, ..) aut. definiálható függvények fitnesz érték: teszt halmazon helyes találat/hiba

stratégiai par.: fa-srtruktúra szintek száma, ..

Borgulya I. PTE KTK

16

inicializálás (P>200), értékelés: fitnesz=célf. Generációs ciklus (P utód)

14

replikáció: másolat mutáció: pl. xj‘ =xj + fitnesz(xj) ^0.5 * N(0,1) sztochasztikus szelekció P legjobb (gyözelmek sz.) megállási feltétel, eredmény

Borgulya I. PTE KTK

15


inicializálás rekurziv fa-strukturák értékelés fitnesz értékek (teszthalmazon) generáció ciklus mvelet választás: crossover, mutáció adott valószínséggel (*a(+b c d) (-c 2) ) (*11 (+a b) ) (*a(+b c d) (+a b) ) értékelés, megállási feltétel, eredmény

Borgulya I. PTE KTK

C.J. Fogel, Owens Walhs ‘60 D. Fogel 92 ~ES, de csak mutáció (faj alkalmazkodása)

EP lépések

GP lépések

12

EP


GP

generációs ciklus szülök sztoch. választása (visszatevéses) rekombináció pl. (a b c d ) ( e f g h) (a f g d ) +szórás mutáció pl. Vk‘ = Vk * exp(t1*N(0,1)) xj‘ = xj + Vj‘ *N(0,1) értékelés determinisztikus szelekció (P legjobb elit) megállási felt., eredmény

Borgulya I. PTE KTK

Borgulya I. PTE KTK

Evulúciós programozás

ES lépések

Rechenberg, Schwefel ‘60 opt. módszer individum valós számokkal n pont (n dim) szórásokkal (normál eloszlás) P-böl O-utód P<< O ( P+ O ) ES

ES lépések

11

Evulúciós stratégiák

ES

Borgulya I. PTE KTK

Alkalmazási példák

17

fuzzy szabályozó elállítás osztályozó r. generálás multimodál fg. optimalizálás áramkör tervezés, … csoportosítás (klaszter, repül útvonal) paraméter meghat. (NH, SZR, FR) piac szegmentálás, kávépiac opt. árai, széria nagyság, prognózis, ...

Borgulya I. PTE KTK

18




Alkalmazási példák: fuzzy szabályozó gen.

Alkalmazási példák: géptelepítés tervezés

n gép, n munkahely, gép install. költs.,anyag szállítási költség min. jelölés Cij i. hely, j. gép inst. költség Bjm j - m. gép közti anyag sz. Aik i - k. hely közti anyag sz. költ. f(i) a permutáció i. helyén a gép sor. Célfg.

6 Cif(i) + 6 6 Aik*Bf(i)f(k)

-----

Géptelepítés

(1+100) ES -el individum (n=7)

Tervezési eljárás

GA tanulás fuzzy szabályok

4356217

fuzzy halmazok, mv. 3. helyen 5. gép

Fuzzifikálás köv. Mechanizmus defuzzifikálás

replikáció: 100 másolat mutáció 1-2 helyen gépcsere

min

input

output

Alapgondolat : Hibrid GA - ES algoritmus Borgulya I. PTE KTK

19


Tudásbázis: Ri: IF x1 is Ai1 AND … xn is Ain THEN y is Bi Aij (aij, bij, cij) háromsz. term (n fuzzy halmaz) individum (szabály): C=C1C2 =(c1 c2 …cn ai1bi1ci1 ai2 bi2 ci2 …. Ain+1 bin+1 cin+1) inicializálás t példa t szabály (vázlatosan) szabályonként n term

Borgulya I. PTE KTK

20



Borgulya I. PTE KTK


Fitnesz: max Z(Ri)= Ri , példák átl. kompatibilitási foka * pozitív példák átl. “ “ * büntet fg. (negatív pédák
Borgulya I. PTE KTK

23

Hibrid GA - ES (m szabály generálás) Szabálybázis egyszersítés (GA újabb fitnesz) Szabálybázis optimalizálás (GA újabb fitnesz)

Borgulya I. PTE KTK

24

EA alaptechnikák

x1, x2 [-1,1]


F(x1,x2)= x1^2+x2^2-cos(18 x1)-cos (18 x2)

Teszt: 1681 adatpár, hibrid GA (50 gener. ) ES (25 gener.) egyszerüsítés (500 gener.) optim. (1000 gener.) Eredmény: 232 szabály 0.19 a négyzetes hibák összege

2. Alaptechnikák

O. Cordón, F. Herrera: A Hybrid Algorithm-Evolution Strategy Process for Learning Fuzzy Logic Controller Knowledge Bases In Herrera, Verdegay: Genetic Algoritms and Soft Computing Physica Verlag 1996. pp. 250-278.

Borgulya I. PTE KTK

Fuzzy szabályozó gen. lépések

Evolúciós algoritmusok Pl. multimodál fg.:

21


22

Borgulya I. PTE KTK

25

Borgulya I. PTE KTK

1

Reprezentáció, ábrázolási forma Szelekció Rekombináció Mutáció Visszahelyettesítés EA ciklus kialakítás

Borgulya I. PTE KTK

2

EA alaptechnikák

EA alaptechnikák

EA alaptechnikák

Ábrázolási forma (Változatos forma)

Szelekció

Szelekció

Valós (egész) vektor E= (x1,x2, …,xn) Permutáció E=(S1, S2,…, Sn) i. pozíció: Si objektum S1, S2,…, Sn x1,x2, …,xn Bináris vektor genotípus – fenotípus(szting) 1011101011010 x1,x2, …,xn xi kódolás: Gray-kód (Hamming távolság =1)

Borgulya I. PTE KTK

3

Borgulya I. PTE KTK

EA alaptechnikák

Borgulya I. PTE KTK

-

lineáris rekombináció: a hiperk. egy egyenese, h. síkja (mint a köztes rekombináció, de a állandó.)

Borgulya I. PTE KTK

9

0.1

0

E2

1.0

1

E3

0.4

1

E4

2.5

2

ui=a xi + (1-a) yi 7

5

1011001101

0011 001101

0011010111 szülk

1011010111 utódok

(i=1,2,…, n) a{0, 1}

Borgulya I. PTE KTK

8

EA alaptechnikák Rekombináció

Bináris sztringek rekombinációja

Borgulya I. PTE KTK

E1

(x1, x2, …, xn), (y1, y2, …, yn) és (u1, u2, …, un):

GA genotípus szint: keresztezés (crossover) változók bitpozíció határát nem figyeli Gray-kód! Keresési tér: L-elem bitsorozatok tere - egypontos keresztezés

ui=a xi + (1-a) yi (i=1,2,…, n) a>-h, 1+h] (rnd!)

Kiválasztott egyedek száma

Szülk állományából 1-több szül - utód(ok) Szülk által kijelölt keresési térben generál utódot. örökölt tulajdonságok, változatosság fenntartás Diszkrét rekombináció általános mvelet, több típusra keresési tér: néhány diszkrét érték (hiperkocka csúcsok)

Si=Si-1+pi od r=Rnd; Ei’=Jz ha Sz-1 d r<Sz od

Rekombináció

Egész és valós változók rekombinációja a hiperkocka „több” pontja válaszható - köztes rekombináció: a hiperk. bármely pontja növelhet a kocka

Várható másolatok száma

Borgulya I. PTE KTK

EA alaptechnikák

Rekombináció

Egyed

Rekombináció

Lineáris sorrend alapú szelekció (lin, ranking sel.) 1. növekv sorrend fitnesz szerint 2. sorszám osztás (1 a legrosszabb)

S0=0 For i=1 to P do For i=1 to P do

6

Sztochasztikus univerzális mintavétel (fitnesz arányos) Ei –> P*p(Ei) ív egy szülhöz (várható másolatok száma) P számú mutató

EA alaptechnikák

3. egyed választás valószínség szerint (lineárisan sorszám függ): K->0, 1]. p1= K- / P a legrosszabb egyed val. (pP = (2- K- )/ P ) Legyen J a fitnesz értékek alapján növekvbe rendezett szelekciós halmaz.

EA alaptechnikák

4

Szelekció

Verseng szelekció (tournament sel.) egyedek sorrendjét használja fel 1.tour paraméter: tour számú egyedválasztás (rnd) 2. legjobb kiválasztása ismétlés P-ször (változatosság megmarad!) Csonkolásos szelekció (truncation sel.) csak a legjobbakat választja ki 1. növekv sorrend fitnesz szerint 2. P legjobb T-ed részét kijelöljük, P-ször választás (rnd) Borgulya I. PTE KTK

EA alaptechnikák

Szelekció

Vizsgálható: pl. fitnesz értékek változása, varianciája Szelekciós állomány (selection pool), szülk állománya (matching pool) – köztes populációk Rulett szelekció (fitnesz arányos) szelekciós valószínség: p(Ei)=f(Ei)/6f(EI) rulett: Ei –> p(Ei) ív egy szülhöz P-ször ismétlés sok ismétldés – szupermegoldások, javítás: fitnesz skálázás (lineáris, logaritmikus, exp.)

10

Bináris sztringek rekombinációja - többpontos keresztezés véletlen keresztezési pontok, növekv sorrendben - uniform keresztezés (diszkrét rek.) - kever keresztezés (shuffle crossover) mindkét szülnél véletlen bitpozíció keverés egypontos keresztezés eredeti sorrend visszaállítás

Borgulya I. PTE KTK

11

EA alaptechnikák

EA alaptechnikák

Rekombináció

Permutációk rekombinációja helyes permutációt megtartó transzformációk

Uniform sorrendalapú rekombináció

Szül1 1 2 3 4 5 szül2 4 3 5 2 1 bitmaszk 1 0 0 1 0 közbüls állapot utód1 utód2

1 0 1 2

0 3 3 3

0 5 5 5

4 0 4 4

0 1 2 1

Véletlen bitmaszk!

Mutáció

Mutáció

X szomszédsági környezetében új pont Nhd(x,H)= {yS| d(x, y) < H} Változtatás: 1-több változó, H csökken, pontosság szélesebbl – kisebb környezet felé Valós/ egész változók mutációja zi= xi r Hi * G, G= 2 -k D D>0, 1]

12

Borgulya I. PTE KTK

EA alaptechnikák

15

EA alaptechnikák

Borgulya I. PTE KTK

EA ciklus kialakítás Stratégiai paraméterek:

-

VR=1 – teljesen új P VR<1 – adott számút cserélünk (pl. elit szelekció) URVR - utódok egy része kerül csak P-be szelektálni kell: szelekciós mveletekkel

EA ciklus kialakítás

Megállási feltétel: -max. generációszám elérése -max. futási id elérése -adott id alatt nem javul a megoldás minsége -hasonlók az egyedek -elre adott érték megközelítése -P minsége megfelel (mérték: célfüggvény értékek szórása/átlaga, legjobb- legrosszabb eltérése P-ben) -kombinációk (nem teljesül, …)

Fitnesz kiértékelés: szerep: egyedek sorrendje, keresési tér struktúrálás célfüggvény adaptálás általában bináris eset: bináris – valós kódolás sorrend esetén: sorrend – sorszámok – fitnesz a sorszámra több célfüggvény – Pareto dominancia alapján nincs célfüggvény: elvárások/korlátok megfogalmazása, kombinálás – összetett fitneszfüggvény kialakítás Borgulya I. PTE KTK

A populáció mérete (az egyedek száma), A rekombináció alkalmazásának pr valószínsége, A mutáció alkalmazásának pm valószínsége Az utódképzési ráta értéke A visszahelyezési ráta értéke.

Kezd populáció kialakítása: elz feladatmegoldás felhasználása+véletlen egyedek, módosított elz eredmények, többszörös újraindítás, véletlenszeren kialakítás

Steady-state EA: 1-2 utód Borgulya I. PTE KTK

14

EA alaptechnikák

16

EA alaptechnikák

18

j=(i,i-1, i-2, …), i=1,2,…,n xi-tl távolodva csökken a változás Bináris változók mutációja bitenként: ha Rnd ! pm x zi ® i ¯1 xi ha Rnd d pm

Utódképzési ráta( UR) (generation gap): utódok száma hányszorosa P-nek Visszahelyezési ráta (VR) lecserélt egyedek aránya P-ben

EA ciklus kialakítás

Borgulya I. PTE KTK

13

Visszahelyezés (reinsertion)

Permutációk mutációja változó: pozíción található érték sorrend változtatás pm alapján - beszúrás, csere, inverz, scramble

Borgulya I. PTE KTK

EA alaptechnikák

Mutáció

Valós/ egész változók mutációja több változót érint mutáció:

zj= xi r Hi * G*J|i-j|, G= 2 -k D D>0, 1] J<1

pl. Hi 0.1 - > 10-7, k =4, 5, ->20 a változók számát pm befolyásolja

Minél több sorszám egyezés legyen!

Borgulya I. PTE KTK

EA alaptechnikák

Borgulya I. PTE KTK

17

EA alaptechnikák EA ciklus struktúra: stratégiai paraméterek beállítása kezdpopuláció kilakítása fitnesz kiértékelés Repeat szelekció, mutáció fitnesz kiértékelés visszahelyezés until megállási feltétel teljesül

19

Borgulya I. PTE KTK

20

3. Általános, standard módszerek

Alap GA

Témakör Standard és származtatott módszerek GA (alap, változatok) ES és változatok EP és változatok Terjeszked (scatter) keresés

Evolúciós algoritmusok 3. Általános, standard módszerek

Jellemzk:

Borgulya I. PTE KTK

Borgulya I. PTE KTK

1

2

Alap GA

Alap GA

Reprezentáció: bitsztring - változókhoz egy-egy rész Fitnesz kiértékelés: bitsztring részek dekódolása, transzformálása Szelekció: rulett szelekció Rekombináció: keresztezés – egypontos, uniform pr valószínséggel alk. (~pr=0.6), f mvelet Mutáció: bitmutáció, ált. pm =0.001 Visszahelyezés (UR=1, VR=1)

Borgulya I. PTE KTK

3

Alap GA

Jellemzk:

EA ciklus

Kezdpopuláció: véletlen (30-500 egyed) Megállási feltétel: max. generációszám /futásid Stratégiai paraméterek (P, pm, pr, bitsztring hossz, ai, bi)

Fbb lépések Kezd P, fitnesz kiértékelés Repeat

szelekció, rekombináció, mutáció, visszahelyezés megállási felt. teljesül

Until

Borgulya I. PTE KTK

4

Borgulya I. PTE KTK

Alap GA

Borgulya I. PTE KTK

Alap GA

Jellemzk:

Kezd populáció generálása: t=0, P(t) = {E1, E2, …, En} fitnesz kiértékelés )(Ei) i=1,2,…,n Repeat

diszkrét rekombináció (1-es) köztes rekombináció (2-es) aritmetikai keresztezés (3-as) lineáris keresztezés (4-es) véletlen köztes rekombináció (5-tel jelölt egyenes pontjai) globális köztes rekombináció (6-tal jelölt téglalap pontjai) kiterjesztett köztes rekombináció (7-tel jelölt) fuzzy rekombináció (8-al jelölt)

Repeat Szelekció: két szül választás, (lin. sorrend alapú szel.) Rekombináció (utódok: Ei’,Ej’), Mutáció ()(Ei’), )(Ej’)), Duplikált utód törlése Fitnesz kiértékelés ()(Ei’), )(Ej’)) Until az utódok száma>=q Visszahelyezés: P(t) = P(t-1), rendezés, törlés,+ q utód Until megállási feltétel teljesül

Borgulya I. PTE KTK

Reprezentáció: E= (x1, V1, …, xn, Vn).

Vn (lépésköz): állandó / különböz és önadaptív

t=t+1

7

6

Általános ES

Változatok: steady-state GA – q utód (1-2)

Változatok: folytonos GA – csak fenotípus szint.

Borgulya I. PTE KTK

5

8

Fitnesz kiértékelés: ~ célfüggvénnyel azonos Szelekció: véletlen egyed választás (ismétléssel) Rekombináció: két szül – egy utód pl. diszkrét rekombináció + szórások: átlag (köztes, globális köztes )

Borgulya I. PTE KTK

9

Általános ES

Általános ES

Jellemzk:

Jellemzk:

Mutáció Azonos szórások esetén (hipergömb pontjai xi körül) V’ = V exp(W0 N(0, 1)) xi’= xi+ V’ Ni(0, 1). W0 =n -0.5

10

O) –szelekció új P: a legjobb P számú utód diszkrimináló: a rosszabb utódnak nincs esélye elny: állandóan változik, mutáció lépésköz mindig változik P/ O ~ 1/7 és P~15 (P+O) –szelekció új P: a legjobb P számú a szülk+ utódok közül elit szelekció: a legjobbak tovább „élnek” Borgulya I. PTE KTK

kezd populáció generálása: t=0, P(t)= {E1, E2, …, EP} fitnesz kiértékelés )(Ei) i=1,2,…,P Repeat

t=t+1 Rekombináció (utódok: E1’,E2’, …EO’), Mutáció ( E1’,E2’, …EO’) Fitnesz kiértékelés ()(Ei’) i=1,2,…, O), If (P,O) szelekció then P(t) = P legjobb utód fi If (P+O) szelekció then P(t) = P legjobb P(t-1) {E1’,E2’, …EO’} közül fi Until megállási feltétel teljesül 11

Borgulya I. PTE KTK

Változatok: (1+1) ES 1 egyed (vektor), rekombináció: másolat, azonos szórások Rechenberg-szabály: szórás megválasztására sikeres mutációk aránya ~1/5 –nél megfelel <1/5: csökkenteni kell V-t >1/5: növelni kell V-t

Jellemzk:

Reprezentáció: valós vektor + 2n mutáció paraméter Fitnesz kiértékelés: ~ célfüggvény,

transzformálás >0-ra: )(Ei)= F(f(Ei),zi).

Rekombináció: másolat Mutáció: dinamikusan változó szórás, ki, zi paraméterek

Vi '

ki * ) ( Ei ) zi

Borgulya I. PTE KTK

Standard EP

14

Borgulya I. PTE KTK

Standard EP

kezd populáció generálása: P(t)= {E1, E2, …, EP} fitnesz kiértékelés )(Ei) i=1,2,…,P Repeat t=t+1, Rekombináció (utódok: E1’,E2’, …EP’) Mutáció (E1’,E2’, …EP’), Fitnesz kiértékelés ()(Ei’) i=1,2,…, P) Visszahelyezés: P(t-1) {E1’,E2’, …EP’} súlyok meghatározása, rendezés P(t) = az els P egyed a rendezettek közül. Until megállási feltétel teljesül

Alapgondolat: korábbi megoldások lineáris kombinációi közt

Változatok: önadaptív, meta-EP meta-EP ~ ES egyed: E= (x1, V1, …, xn, Vn), mutáció: Vi’ = Vi+ D Vi Ni(0, 1) xi’= xi+ Vi’ Ni(0, 1). D stratégiai szerepe (kisebb, nagyobb változások)

keressük a jobb megoldásokat megoldások populációja – de nem evolúciós mveletek Fbb lépések: 1.

2. 3.

5.

Borgulya I. PTE KTK

15

Terjeszked (scatter) keresés

4.

16

Visszahelyezés: verseny a szülk és utódok közt „sztochasztikus szelekció” ~ verseng szelekció minden szülhöz, utódhoz súly rendelés lépések: - minden Ei-hez q egyed választás (rnd) - súly =gyzelmek száma (jobb a )(Ei)) - új P: P egyed a legjobb súlyokkal (q~0.05 P és P>200)

xi ' xi Vi * Ni (0,1)

13

EA ciklus

12

Standard EP

Jellemzk:

egyed: Ei= (xi, Vi, Di ), Di szintén változik (~5 fok)

Borgulya I. PTE KTK

EA ciklus

Standard EP

Változatok: korrelált mutáció alkalmazása legjobb irányba történ módosítás: rotációs szögek

(P,

Általános ES

Borgulya I. PTE KTK

Jellemzk:

Visszahelyezés: két változat (P egyed O utód)

Változónként eltér szórások (hiperellipszoid pontjai xi körül) Vi’ = Vi exp(W’N(0, 1)+ W Ni(0, 1)) xi’= xi+ Vi’ Ni(0, 1). W’~ (2n)-1/2 és W ~ (2n1/2)-1/2

Borgulya I. PTE KTK

Általános ES

17

Kezd megoldás halmaz generálása, és egy megoldás halmaz (Refset: reference set) elkülönítése. Új megoldások képzése a Refset elemeinek kombinálásával. Az új megoldások javítása helyi kereséssel. A legjobb új megoldások kiválasztása és a Refset-be illesztése. Folytatás a 2. ponttól, ha a Refset még változott, vagy max. generációszámot nem érte el. Borgulya I. PTE KTK

18


Terjeszked (scatter) keresés


Részletek: Kezd P: generátor programmal ( minden régióból..) Javító eljárás: helyi keres elj. minden egyednél Refset módosítás (Refset=Refset’+Refset2): Refset1 – a legjobbak, Refset2 – a legrosszabbak vizsgálat, hova helyezhet (Resfset1-2) Részhalmaz generálás: 2,3,4,..|Refset| elem halmazok pl. kételem +a legjobb kimaradó, … Megoldás kombináló eljárás: a részhalmaz egyed-párok lineáris kombinációi (többféle típus)

Borgulya I. PTE KTK

5. Genetikus programozás (GP)

Borgulya I. PTE KTK


(+1 2 ( IF ( > Time 10) 3 4 ) ).

3


6

4

Borgulya I. PTE KTK

5

Genetikus programozás Az általános GP módszer

Kezdpopuláció: véletlen, irányított véletlen (halframping). Csomópontokban F elemek, leveleknél T elemek Szelekció: fitnesz arányos, verseng szelekció, verseng + Pareto dominancia (több célnáleddigi legjobbak lista) Rekombináció: egypontos keresztezés; (0.9 val. bels csomópontnál kijelölés), vagy reprodukció

Borgulya I. PTE KTK

T halmat: konstans, változó, függvény() F halmaz: aritmetikai, matematikai, logikai, szelekciós, ciklus utasítások, spec. függvények (problémás: osztás, ciklus, különböz adattípusok) Fitneszfüggvény: hibafüggvény / sikeres tesztek száma több cél kezelés: büntet fg. / Pareto dominancia

Az általános GP módszer

Stratégiai paraméterek: programhossz, pr, pm , |P| (több ezer), szintek száma (max. 7) Megállási feltétel: pontos/közelít eredmény, max generációszám (50) Program felépítés (egy egyed): egy fa (fprogram), több fa (eljárások/ akciók)

Borgulya I. PTE KTK

GP alapkoncepció


GP alapkoncepció

GP alapkoncepció

Borgulya I. PTE KTK

2


Fbb lépések, definiálni kell: 1. a végpontok halmazát (terminal set) 2. a függvények halmazát (fuction set) 3. a fitneszfüggvényt 4. a stratégiai paramétereket 5. a megállási feltételt és 6. a program felépítését.

Automatikus programírás Koza (1992): LISP programok írása Programfa írásmód

Borgulya I. PTE KTK

Borgulya I. PTE KTK

1


Alapfeladat

19

Alapfeladat GP alapkoncepció Az általános GP módszer Fejlettebb GP technikák Példa ADF-el Alkalmazások

Mutáció:

7

részfa lecserélés (rnd), pont mutáció (F elem csere), részfa képzés (önálló fa lesz a részfa) rövidítés( részfa helyett T elem), konstans mutáció, szisztematikus konstans mutáció (input változó – konstans csere)

Borgulya I. PTE KTK

8



GP definíció


Fejlettebb GP technikák

Fejlettebb GP technikák

Automatikusan definiálható függvény - ADF

Memória használat: skalár, read/write indexelt (-k,k), read(index), write(index, érték), Elkülöníthet tevékenységek/ akciók (multi-tree) - minden akciónak külön belépési pont, - minden akciót külön tesztelünk, - rekombináció, mutáció kiválasztott akcióra

Borgulya I. PTE KTK

9

Borgulya I. PTE KTK


Alkalmazási példa: veremkezelés

12

push down verem 5 tevékenységgel: Inicializálás (makenull) Üresség vizsgálat (empty) Csúcs olvasás (top) Csúcs olvasás és törlés (pop) Újadat elhelyezés (push)

(PROGN (DEFUN ADF0 (PAR0 PAR1 PAR2) (VALUES (-(*PAR2 PAR0) (*(+ PAR0 (* PAR0 PAR1) (% PAR2 (% PAR2 PAR2))))) (VALUES (-(ADF0 a2 b2 c2 ) (ADF0 b1 c1 a1))))) GP definíció módosítás: F halmaz a fprogramnál Ff={+,-,*,%, ADF0} T halmaz az ADF0-nál Ta={ PAR0, PAR1, PAR2 } F halmaz az ADF0-nál Fa={+,-,*,%}

mutató:=maxméret +1 üres:= (mutató> maxméret) csúcs:= verem (mutató) törölt:= verem (mutató) mutató:=mutató+1 mutató:=mutató-1 verem(mutató):=újadat

Borgulya I. PTE KTK

13


definiálások: T halmaz: pl. +index memória, verem mutató, maxméret konstans F halmaz: spec. függvények (read(mutató), write, mutató kezel mveletek) Fitnesz: pontszám (helyes teszteredmények száma) tevékenységenként külön teszt Borgulya I. PTE KTK

Témakörök


Fuzzy osztályozó rendszer fejlesztés (biztosító, anyag felhaszn.) Képfeldolgozás (röntgen, MRT) pl. filter tervezés Tervezés (áramkör, repül részek, auto karosszéria) Kereskedelem: piacmodellezés (fuzzy rendszer) Mesterséges élet: mozgás, ágesnek

Paraméterek beállítása Csoportosítás (niching)

4. Fejlettebb EA technikák I.

15

Borgulya I. PTE KTK

1

Fitnesz megosztás (fitnes sharing) Tömörítés (crowding) Ritkítás (clearing)

Memóriát alkalmazó módszerek

Mvészet: videó film, jazz, 3D kép

Borgulya I. PTE KTK

14

Fejlettebb EA technikák

GP alkalmazások

11


Alkalmazási példa: veremkezelés

Feladat: Két téglatest különbsége D= a1* b1* c1 - a2* b2* c2 13. generációnál a jó végeredmény:

Borgulya I. PTE KTK


Alkalmazási példa ADF-el

Borgulya I. PTE KTK

10

Virtuális vesztes Hangya kolónia Kulturális algoritmus

Borgulya I. PTE KTK

2



Paraméterek beállítása



Megfelel kombináció kiválasztás, módosítás kölcsönösen függnek egymástól Beállítási technikák: paraméter értékadás

futás eltt par. beállítása


futás közben par. ellenrzés

Futás eltti par. beállítás: kézi beállítás, változatok próbálgatása - csak néhány kombináció próbálható ki - idigényes - bizonytalan a legjobb megtalálása Futás közbeni változtatás (minden változtatható!) Determinisztikus par. ellenrzés: det. szabályt alkalmaz Adaptív par. ellenrzés: visszacsatolás a hatékonyságról Önadaptív par. ellenrzés: evolúciós folyamat változtatja

Pl. futás közbeni mutáció par. változtatás ES-nél Determinisztikus: xi’= xi + N(0, V) és V(t)=1 -0.9 t/T Adaptív: ps sikeres mutációk aránya (Rechenberg )

determinisztikus adaptív önadaptív

Borgulya I. PTE KTK

3

Borgulya I. PTE KTK

4

Borgulya I. PTE KTK


Alap GA-nál vizsgálatok:

Adaptív populáció méret: egyedhez max élettartam, amely csökken generációnként a fitnesz függvényében

Önadaptív mutáció: pm 0.001-0.15 közt (tárolják pm-t) Önadaptív keresztezés: pr változik (tárolják pr-t)pr –tl függen uniform keresztezés (mindkét szülnél RND<pr) Másolás ( egyik szülnél sem RND<pr) csak mutáció (egy szülnél Rnd<pr)

HETi

Csoportosítás (niching)

Afit (átlagos fitness), HET (hátralév élettartam), Rofit (legrosszabb f), Jofit (legjobb f), K=1/2(MAXHET-MINHET) MINHET – MAXHET intervallumban változhat

Rofit fitneszi ha fitneszi ! Afit °°MINHET K Rofit Afit ® Afit fitneszi °1 / 2( MINHET MAXHET ) K ha fitneszi Afit °¯ Afit Jofit

Ha több lehetséges megoldást keresünk Stabil csoportok kialakítása párhuzamos keresésnél. Technikák: fitnesz megosztás, tömörítés, ritkítás. Fitnesz megosztás (fitnes sharing) cél: a csoportokban megmaradjanak a legjobbak, fitnesz érték csökkentés a csoportban fi’= fi / mi

(sh a sharing függvény, Vs becsült küszöbérték (niche sugár))

P

mi

¦ sh(d ) ij

j 1

Borgulya I. PTE KTK

6

Borgulya I. PTE KTK


Determinisztikus tömörítés: standard tömörítés, de

visszahelyezésnél verseny az utód és a legközelebbi, csoportbeli szül közt. (utódonként)

Korlátozott verseng szelekció (standard változat)

°1 (d / V )D ha d V ij s ij s ® °¯ 0 különben

Borgulya I. PTE KTK

8

Memóriát alkalmazó módszerek Hatékonyság növelés „problémamegoldó tudással”; Sikeres / sikertelen lépések, ismeretek memorizálása.

Ritkítás (clearing) Fitnesz változtatás a csoporton belül, csak a legjobbak maradnak. A mechanizmus: - egy csoportban csak k egyed lehet - csoporthoz tartozás: Vc –nél kisebb a távolságuk - k számú legjobb egyed változatlan, többi fitnesz értéke nulla.

Kollektív memória (EC-memory) Használható: szelekciónál, mvelet par. beállításnál, stb. Típusok: numerikus és szimbolikus Numerikus:

mveletek valószínségeivel, virtuális egyed mint valószínségi vektor/mátrix a legjobb egyedekbl

visszahelyezés: CF számú (rnd) egyed közül a leghasonlóbb szülvel versenyez Borgulya I. PTE KTK

sh(dij )


Csoportosítás (niching)

csak néhány utód, visszahelyezés: CF számú (rnd) egyed közül a leghasonlóbb szül helyére kerül egy-egy utód

7


Csoportosítás (niching) Tömörítés (crowding) csoportok fenntartása: új egyed a hasonlót cserélheti le Standard tömörítés:

5



If (t mod n=0) then V(t)= V(t-n)/c ha ps>1/5 V(t)= V(t-n)*c ha ps<1/5 V(t)= V(t-n) ha ps=1/5 else V(t)= V(t-1) fi ahol c>0.817, 1] Önadaptív mutáció ellenrzés: általános ES-nél

Szimbolikus:

keresési intervallumok, szabályok tanulása 9

Borgulya I. PTE KTK

10

Borgulya I. PTE KTK

11



Fejlettebb EA technikák Memóriát alkalmazó módszerek



Virtuális vesztes

Hangya kolónia (AC: Ant colony)

Korábbi sikertelen egyedekbl levonható tanulságok Valószínségi vektor bitérték választására (VL) Képzése: legrosszabb egyedek bitpozíció átlagai Aktualizálás: VL t+1= (1- D) VLt + D 'VL (D ~ 0.2)

'VL a t-dik generációban képzett VL Alkalmazás: egy X egyed xi bitjénél pi= 1-|VLi- Xi| valószínséggel kell 1 érték

Borgulya I. PTE KTK

12

Lépésenkénti útvonal kialakítás a k-dik hangya pij valószínséggel lép i-bl j állapotba pij függ:- az átmenet „vonzerejétl” Kij - Wij feromon csík értéktl - a lehetséges átmenettl (tabuk lista) Feromon aktualizálás: Wij (t) = Wij (t-1)+ 'Wij

Nincs szelekció, rekombináció , mutáció

Hosszútávú memória diszkrét értékeknél (permutációk) Populáció egyedei „hangyák” párhuzamosan több útvonalat bejárnak, a jó útvonalat feromonnal megjelölik, feromon intenzitás nhet… Feromon csik koncepció átvétele Állapottér leírás gráffal, (i,j) élhez Wij feromon csík érték feromon mátrix, sikeres út aktualizálja

Borgulya I. PTE KTK


Hangya kolónia

13


( 'Wij : hangyák száma amelyek i-j-t sikeresen alkalmazták)

Borgulya I. PTE KTK





Hangya kolónia lépések:

Kulturális algoritmus

Kulturális algoritmus lépések:

Véletlen kezdértékek a W feromon csík mátrixnál. Repeat For k=1 to |P| Kezdállapot választás; legyen i. Repeat Minden j-re ij kiszámolása. Egy állapot átmenet kiválasztása tabuk lista bvítése az új állapot átmenettel. Until k-dik megoldás kész endfor For a hangyák minden i-j állapot átmenetére. 'Wij kiszámítása. Feromon mátrix aktualizálás. endfor Until megállási feltétel teljesül. Borgulya I. PTE KTK

A kultúra által motivált modell, EA újabb elemekkel egy mechanizmussal az ismeretek kinyerésére Két populáció: - szociális P (pl. normál ES) - hihet BLF (ismereteket tárol) BLF részek: -SZ legjobb példák halmaza - N intervallum halmaz Mveletek: szelekció BLF-hez P-bl (Accept), BLF aktualizálás (Adjust), paraméter módosítás önadaptíven (influence)

Kezdpopuláció kialakítása: t=0, P(t), BLF(t). Fitnesz kiértékelés: P(t)-n. Repeat

t=t+1 P(t) evolúciója az influence mvelettel. BLF(t) aktualizálása: Accept (P(t)), Adjust (BLF(t)). Until megállási feltétel teljesül.

15


Borgulya I. PTE KTK

16

Borgulya I. PTE KTK



Témakörök

4. Fejlettebb EA technikák II.

Párhuzamos EA változatok Globális modell Regionális modell Konkurens modell Kooperáló modell Lokális modell

1

Borgulya I. PTE KTK

2

17

Párhuzamos EA változatok Nehéz problémák megoldására Multiprocesszoros rendszerek, nagyobb populáció, elfogadható futási id párhuzamos számításokkal Különböz modellek: populáció struktúrák, szelekció mvelet alapján

Borgulya I. PTE KTK

14

Globális: párhuzamos számítások Regionális: régiók, migráció Regionális modell változatok: koevolúció (szimultán evolúció) - konkurens, kooperáló lokális

Borgulya I. PTE KTK

3



Globális modell

Populáció struktúra változatlan Párhuzamosan végrehajtható: rekombináció, mutáció, célfüggvény számítás Master-slave processzor struktúra: - master osztott memóriával tárolja P-t - slave-ek számolnak

Borgulya I. PTE KTK

4


Regionális modell (island, coarse grained modell) Egyenl nagyságú alpopulációk (régiók) Alpopulációk önálló EA-ként mködnek, egy-egy mikroprocesszorral Nagy populáció kialakításhoz: migrációs mvelet Hatékonyságát befolyásolja: alpopulációk száma /mérete topológia, migrációs egyedek száma egyedkiválasztás mód

Borgulya I. PTE KTK

Regionális modell

alpopulációk száma /mérete tapasztalati képlet: alpopulációk száma=n0.5 alpop. méret= 20+n/10 (processzorszám fontos) pl. n=150 esetén 13 régió, 35-35 egyed (420) Alpopulációk közti topológia: irányított gráf a populációk közt, migráció használja. Lehet: teljes kapcsolat, egydimenziós gyr (+távolság), szomszédsági (2-dimenziós rács + távolság)

5

Borgulya I. PTE KTK

6

Fejlettebb EA technikák Fejlettebb EA technikák


Regionális modell

Topológia: teljes

Migrációs ráta és periódus

egyedek száma amit kicserélünk, cserék gyakorisága. tapasztalati képlet: Migrációs ráta= régióméret 20%-a /*egyedszám Migrációs periódus= régióméret /*generációszám Egyedek kiválasztása, lecserélése: migrációs mv.

gyrs

1. egy régióhoz - régiók kiválasztása (topológia alapján) 2. egyedek kiválasztása régiónként –> migrációs halmaz 3. migrációs halmazból egyedcsere a régiónál

szomszédsági

Borgulya I. PTE KTK

7

Borgulya I. PTE KTK


Felhasználás: Nagy populáció kialakításhoz, nagyobb keresési tér lefedés (megfelel izolálás ) Különböz stratégiai paraméterek alkalmazása sikeresebbek befolyásolják a többi EA-t Ismeretlen stratégiai par. keresése (sikerességet mérni kell!)

Borgulya I. PTE KTK

8

Borgulya I. PTE KTK


Regionális modell

Kezdértékek a P1, P2, …, Pk alpopulációknál. Fitnesz kiértékelés a P1, P2, …, Pk alpopulációknál. Repeat For j=1 to migrációs_ periódus Párhuzamos végrehajtás minden Pi-re (i=1,2,…,k): Szekvenciális_EA(Pi) endfor For i=1 to k For i minden j szomszédjára Migráció (Pi,Pj) /* csak két populáció közt! Fitnesz kiértékelés Pi –nél endfor endfor until megállási feltétel teljesül

Regionális modell


Konkurens modell (competing subpopulation)

Regionális modell változat – különböz stratégiákkal Sikeresség függvényében változhat: régió méret, számítások biztosítása a sikeresek javára. Konkuráló régiók rangsorolása sikeresség alapján. Pl.: 1. reprezentáns egyedek választása régiónként 2. lineáris rendezés alapú fitnesz kiértékelés 3. Régiók értékelése: reprez. egyedeik átlagos fitnesz értéke 4. rendezzük , majd sorszámozzuk a régiókat.

Borgulya I. PTE KTK

Konkurens modell

Források felosztása pozíciók alapján. Változatok:

Legjobb stratégia térnyerése: a legjobb kap csak forrásokat Sikeres / sikertelen régiók: els 25% sikeres. Csak a sikeresek kapnak újabb forrásokat Erforrások súlyozott elosztása: pozíciók, sorszámok függvényében felosztás (minimális régióméret biztosított)

Konkurencia ráta és periódus (migráció átfogalmazás) konkurencia_ráta = 10 % alpopuláció méret Konkurencia_periódus = 20% alpopuláció_méret

5. pozíció számolás: pozíciót= 0.9 pozíciót-1 + 0.1 sorszám

10

9

11

Borgulya I. PTE KTK

12



Kooperáló modell

Nagy számítási igénynél, EA helyi szélsértékhez konvergál Alkalmazható:

Borgulya I. PTE KTK

14

Borgulya I. PTE KTK

Lokális modell Topológia jellemzk:

Alapja a topológia:

16

centrumok, szomszédságból szülk választása (legjobb egyed / szelekció)

Visszahelyezés: a szomszédságba.

minden egyed csomópont, közvetlen szomszéd távolsága 1, a szomszédsági topológia az egyed/centrum körül, a szomszédság méret növelhet. (2, vagy 1,2 …)

1-több dimenziós, „távolság” pl. egész/ fél gyr, négyzetes-átlós rácson egész/fél kereszt, csillag, kör, stb.

Szelekció:

15


Lokális modell – mveletek

Borgulya I. PTE KTK

• Lokális modell - topológiák


(minden régiónál és egyednél)

egyeden/környezeten

Borgulya I. PTE KTK

Izolált egyedek (egy-egy mikroprocesszor), csak a szomszédossal van kapcsolatuk Párhuzamos számítások minden kiválasztott

Kooperáló modell Potter et al. (2000. modellje)

Közös adatstruktúra a domain modellben


Lokális modell (diffúz, cella modell)

reprezentatív egyedek választása régiónként, megoldások összeállítása, tesztelése

13

A régiók kooperálnak egymással, de függetlenek Egy régió a megoldás egy részletét fejleszti, közös adatstruktúrában lépnek kapcsolatba A fitnesz a közös adatstrukturán értelmezett, az együttmködés milyenségétl függ. Ehhez:


Kooperáló modell

Összetett problémáknál, részekre bontható a probléma, a megoldásrészek ersen függnek egymástól, a megoldásrészek ersen befolyásolják a fitneszt Pl. fuzzy rendszer (szabályok, halmazok) n-dim fgv. optimalizálás (dimenziónként…)


utódok kiválogatása, Szülk / egyedek válogatása cserére

Modell hatékonyság: - jobb utódok, legrosszabb szülk válogatása visszahelyezésnél, - szomszédság kiterjedése: kisebb távolság jobb eredmény Borgulya I. PTE KTK

19

Borgulya I. PTE KTK

17

Borgulya I. PTE KTK

18

Fuzzy-rendszerek. Fuzzy halmazm veletek. Fuzzy logika m veletek. Borgulya I. PTE KTK 2. 1.Fuzzy rendszerekr l általában

Recommend Documents