Intelligens számítástechnikai modellek identifikációja evolúciós és gradiens alapú tanuló algoritmusokkal

Intelligens számítástechnikai modellek identifikációja evolúciós és gradiens alapú tanuló algoritmusokkal Ph.D. értekezés

Botzheim János okleveles mérnök-informatikus

Témavezet˝o:

Dr. Kóczy T. László egyetemi tanár, az MTA doktora Budapesti M˝uszaki és Gazdaságtudományi Egyetem Villamosmérnöki és Informatikai Kar Távközlési és Médiainformatikai Tanszék

Budapest, 2007

Alulírott, Botzheim János kijelentem, hogy ezt a doktori értekezést magam készítettem és abban csak a megadott forrásokat használtam fel. Minden olyan részt, amelyet szó szerint, vagy azonos tartalomban, de átfogalmazva más forrásból átvettem, egyértelm˝uen, a forrás megadásával megjelöltem. Az értekezés bírálatai és a védésr˝ol készült jegyz˝okönyv megtekinthet˝o a Budapesti M˝uszaki és Gazdaságtudományi Egyetem Villamosmérnöki és Informatikai Karának Dékáni Hivatalában. Budapest, 2007. november 11.

Botzheim János

i

Köszönetnyilvánítás Ezúton fejezem ki köszönetemet témavezet˝omnek, Kóczy László professzor úrnak, hogy kutatásaimat segítette, valamint lehet˝oséget adott arra, hogy az érintett tématerületek legnevesebb kutatói mellett folytathattam tanulmányokat. Köszönöm Antonio Ruanonak, a portugáliai Algarve egyetem professzorának, hogy irányításával folyamatosan segítette kutatásaimat és szakmailag komoly segítséget nyújtott. Köszönöm Cristiano Cabritának, az Algarve egyetem doktoranduszának a szakmai segítséget. Köszönöm Erich Peter Klement professzor úrnak, hogy többször fogadott a linzi Johannes Kepler egyetemen és segítette munkámat. Köszönöm Dr. Mario Drobics és Dr. Edwin Lughofer támogatását a Johannes Kepler egyetemen. Köszönöm Gedeon Tamás professzor úrnak, hogy több hónapra fogadott az Australian National University egyetemen Canberrában, ahol a vezetése alatt álló tanszéken tanulmányozhattam a legfrissebb kutatási eredményeket. Végül, de nem utolsó sorban, szeretnék külön köszönetet mondani családomnak a támogatásért.

ii

Tartalomjegyzék 1. Bevezetés. Célkituzések, ˝ módszerek, el˝ozmények. 2. A számítási intelligencia fejl˝odésének és módszereinek áttekintése 2.1. Fuzzy rendszerek . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1. Fuzzy halmazok . . . . . . . . . . . . . . . . . . . . . 2.1.2. Alapm˝uveletek fuzzy halmazokon . . . . . . . . . . . . 2.1.2.1. Fuzzy komplemensek . . . . . . . . . . . . . 2.1.2.2. Fuzzy metszetek . . . . . . . . . . . . . . . . 2.1.2.3. Fuzzy uniók . . . . . . . . . . . . . . . . . . 2.1.3. Fuzzy relációk . . . . . . . . . . . . . . . . . . . . . . 2.1.4. Fuzzy szabályok . . . . . . . . . . . . . . . . . . . . . 2.1.5. Mamdani-típusú fuzzy következtet˝o rendszerek . . . . . 2.1.5.1. A szabálybázis . . . . . . . . . . . . . . . . . 2.1.5.2. Az illeszkedés mértéke . . . . . . . . . . . . 2.1.5.3. A következtetés . . . . . . . . . . . . . . . . 2.1.5.4. Defuzzifikáció . . . . . . . . . . . . . . . . . 2.1.6. Takagi-Sugeno-típusú fuzzy irányítási rendszerek . . . . 2.2. Evolúciós algoritmikus módszerek . . . . . . . . . . . . . . . . 2.2.1. Genetikus algoritmusok . . . . . . . . . . . . . . . . . 2.2.1.1. Gyakran használt fogalmak . . . . . . . . . . 2.2.1.2. Az algoritmus . . . . . . . . . . . . . . . . . 2.2.1.3. Az alkalmassági (fitnesz) függvény . . . . . . 2.2.1.4. Szelekció . . . . . . . . . . . . . . . . . . . . 2.2.1.5. Keresztezés . . . . . . . . . . . . . . . . . . 2.2.1.6. Mutáció . . . . . . . . . . . . . . . . . . . . 2.2.1.7. Visszahelyettesítés . . . . . . . . . . . . . . . 2.2.1.8. Migráció . . . . . . . . . . . . . . . . . . . . 2.2.2. Genetikus programozás . . . . . . . . . . . . . . . . . . 2.2.2.1. Keresztezés . . . . . . . . . . . . . . . . . . 2.2.2.2. Mutáció . . . . . . . . . . . . . . . . . . . . 2.2.3. Bakteriális evolúciós algoritmusok . . . . . . . . . . . . 2.2.3.1. Bakteriális mutáció . . . . . . . . . . . . . . 2.2.3.2. Génátadás . . . . . . . . . . . . . . . . . . . 2.2.3.3. Összehasonlítás, paraméterek . . . . . . . . .

iii

1

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 8 9 10 11 12 13 14 14 15 15 16 17 17 18 19 20 20 21 22 22 22 23 23 24 24 25 26 27 27 27 28

2.2.4. Fuzzy szabályoptimalizálás bakteriális evolúciós algoritmussal 2.2.5. Egyéb módszerek . . . . . . . . . . . . . . . . . . . . . . . . 2.3. Neurális hálózatok . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1. Többréteg˝u perceptron . . . . . . . . . . . . . . . . . . . . . 2.3.2. Radiális bázisfüggvény hálózatok . . . . . . . . . . . . . . . 2.3.3. B-spline neurális hálózatok . . . . . . . . . . . . . . . . . . . 2.3.3.1. Normalizált bemeneti tér réteg . . . . . . . . . . . 2.3.3.2. A bázisfüggvények rétege . . . . . . . . . . . . . . 2.3.3.3. A súlyvektor réteg . . . . . . . . . . . . . . . . . . 2.3.3.4. Almodulok . . . . . . . . . . . . . . . . . . . . . . 2.3.3.5. B-spline neurális hálózatok tervezése . . . . . . . . 2.3.4. Más típusú neurális hálózatok . . . . . . . . . . . . . . . . . 2.3.5. Backpropagation eljárás . . . . . . . . . . . . . . . . . . . . 2.3.6. Levenberg-Marquardt algoritmus . . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

3. Új módszerek és megközelítések az intelligens számítási modellek identifikációjában 3.1. Szabályredukciós operátorokkal kiegészített bakteriális evolúciós algoritmus alkalmazása . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1. A javasolt algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1.1. Szabályredukciós operátorok . . . . . . . . . . . . . . . 3.1.1.2. Szabály megszüntetés . . . . . . . . . . . . . . . . . . . 3.1.1.3. Szabály egyesítés . . . . . . . . . . . . . . . . . . . . . 3.1.1.4. Szemantikus elemzés . . . . . . . . . . . . . . . . . . . 3.1.1.5. Szabály eltávolítás . . . . . . . . . . . . . . . . . . . . . 3.1.2. A módszer tesztelése . . . . . . . . . . . . . . . . . . . . . . . . . 3.2. A Levenberg-Marquardt algoritmus alkalmazása Mamdani-típusú fuzzy szabálybázis optimalizálására . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1. A Jacobi-mátrix meghatározása . . . . . . . . . . . . . . . . . . . 3.2.2. A módszer alkalmazása . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2.1. Referenciaproblémák . . . . . . . . . . . . . . . . . . . 3.2.2.2. Hibadefiníciók . . . . . . . . . . . . . . . . . . . . . . . 3.2.2.3. Két paraméter optimalizációja . . . . . . . . . . . . . . . 3.2.2.4. Az összes paraméter egyidej˝u optimalizációja . . . . . . 3.3. Bakteriális memetikus algoritmus alkalmazása Mamdani-típusú fuzzy szabálybázis optimalizálására . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1. A javasolt algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2. Az algoritmus alkalmazása . . . . . . . . . . . . . . . . . . . . . . 3.3.2.1. Rögzített szabályszám . . . . . . . . . . . . . . . . . . . 3.3.2.2. Változó szabályszám . . . . . . . . . . . . . . . . . . . 3.4. Takagi-Sugeno-típusú fuzzy rendszerek paramétereinek optimalizálása . . . 3.4.1. A javasolt algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1.1. A kódolási elrendezés . . . . . . . . . . . . . . . . . . . 3.4.1.2. Kezdeti populáció . . . . . . . . . . . . . . . . . . . . .

iv

29 31 31 32 33 35 35 36 36 36 37 37 38 39

41 41 42 44 45 46 46 47 47 49 49 51 52 53 53 58 60 61 62 62 70 72 73 73 74

3.4.1.3. Antecedens tanulás . . . . . . . . . . . . . . . . . . . . 3.4.1.4. Konzekvens tanulás . . . . . . . . . . . . . . . . . . . . 3.4.2. Az algoritmus alkalmazása . . . . . . . . . . . . . . . . . . . . . . 3.5. Bakteriális programozás alkalmazása B-spline neurális hálózatok identifikációjára . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.1. A javasolt módszer . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.1.1. A kódolási elrendezés . . . . . . . . . . . . . . . . . . . 3.5.1.2. Az evolúciós folyamat . . . . . . . . . . . . . . . . . . . 3.5.1.3. Bakteriális mutáció . . . . . . . . . . . . . . . . . . . . 3.5.1.4. Génátadás . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.1.5. A baktériumok kiértékelése . . . . . . . . . . . . . . . . 3.5.2. A módszer alkalmazása . . . . . . . . . . . . . . . . . . . . . . . . 3.5.2.1. A bakteriális programozás paramétereinek meghatározása 3.5.2.2. A bakteriális és genetikus programozás összehasonlítása . 3.5.2.3. Statisztikai elemzés . . . . . . . . . . . . . . . . . . . . 3.6. Feature kiválasztás bakteriális evolúciós algoritmusokkal . . . . . . . . . . 3.6.1. A javasolt algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . 3.6.1.1. A kódolási elrendezés . . . . . . . . . . . . . . . . . . . 3.6.1.2. A baktériumok kiértékelése . . . . . . . . . . . . . . . . 3.6.1.3. Az evolúciós folyamat . . . . . . . . . . . . . . . . . . . 3.6.1.4. Bakteriális mutáció . . . . . . . . . . . . . . . . . . . . 3.6.1.5. Génátadás . . . . . . . . . . . . . . . . . . . . . . . . . 3.6.2. A módszer alkalmazása . . . . . . . . . . . . . . . . . . . . . . . . 3.6.2.1. Sztochasztikus jelleg˝u illeszkedési függvény . . . . . . . 3.6.2.2. RENO optimalizáció . . . . . . . . . . . . . . . . . . . 3.6.2.3. Döntési fa optimalizáció . . . . . . . . . . . . . . . . . . 3.6.2.4. Változó hosszúságú baktériumok . . . . . . . . . . . . .

74 76 78 80 80 80 82 82 83 84 84 84 86 88 92 93 94 94 94 95 95 97 97 98 99 100

4. Összefoglalás és kitekintés

103

Irodalomjegyzék

107

v

Ábrák jegyzéke 2.1. Példák tagsági függvényekre . . . . . . . . . . . . . . 2.2. Emberek magasságának jellemzése fuzzy halmazokkal 2.3. Standard (Zadeh-féle) fuzzy m˝uveletek . . . . . . . . . 2.4. Fuzzy következtet˝o rendszer vázlata . . . . . . . . . . 2.5. Illeszkedési mérték meghatározás . . . . . . . . . . . 2.6. Szabály következménye . . . . . . . . . . . . . . . . . 2.7. Teljes Mamdani-következtetés . . . . . . . . . . . . . 2.8. Példák defuzzifikációra . . . . . . . . . . . . . . . . . 2.9. Az evolúció folyamata egy maximumkeresési példában 2.10. A szelekció m˝uvelete . . . . . . . . . . . . . . . . . . 2.11. A keresztezés operáció (bináris példa) . . . . . . . . . 2.12. A keresztezés operáció (valós példa) . . . . . . . . . . 2.13. A mutáció m˝uvelete . . . . . . . . . . . . . . . . . . . 2.14. Példa program és a hozzátartozó kifejezésfa . . . . . . 2.15. A keresztezés operáció . . . . . . . . . . . . . . . . . 2.16. A mutáció m˝uvelete . . . . . . . . . . . . . . . . . . . 2.17. Bakteriális evolúciós algoritmus . . . . . . . . . . . . 2.18. A génátadás m˝uvelete . . . . . . . . . . . . . . . . . . 2.19. A kódolási elrendezés . . . . . . . . . . . . . . . . . . 2.20. Többréteg˝u perceptron (MLP) . . . . . . . . . . . . . 2.21. Egy neuron bemenetei és kimenete . . . . . . . . . . . 2.22. Radiális bázisfüggvény hálózat (RBF) . . . . . . . . . 2.23. B-spline neurális hálózat . . . . . . . . . . . . . . . . 2.24. Kétváltozós B-spline függvény . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

9 10 11 15 16 17 18 19 21 23 23 24 24 25 26 26 28 29 30 32 33 34 35 37

3.1. A tagsági függvény paraméterei . . . . . . . . 3.2. A kódolási elrendezés . . . . . . . . . . . . . . 3.3. Kromoszóma a génátadásnál . . . . . . . . . . 3.4. Tagsági függvény megszüntetése . . . . . . . . 3.5. Tagsági függvények egyesítése . . . . . . . . . 3.6. Kezdeti szabálybázis a pH problémára . . . . . 3.7. Kezdeti szabálybázis az ICT problémára . . . . 3.8. LM módszer teljesítménye a pH problémára . . 3.9. BProp módszer teljesítménye a pH problémára 3.10. LM módszer teljesítménye az ICT problémára .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

42 43 44 45 46 54 54 55 55 56

vi

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

3.11. BProp módszer teljesítménye az ICT problémára . . . . . . . . . . . . . . 3.12. A fuzzy rendszer paramétereinek alakulása . . . . . . . . . . . . . . . . . 3.13. Az MSE érték fejl˝odése . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.14. Bakteriális memetikus algoritmus . . . . . . . . . . . . . . . . . . . . . . 3.15. A legjobb MSE érték˝u egyed cél- és hibaértékei az egyes mintákra a pH probléma esetén BEA használatával . . . . . . . . . . . . . . . . . . . . . 3.16. A legjobb MSE érték˝u egyed cél- és hibaértékei az egyes mintákra a pH probléma esetén BMA használatával . . . . . . . . . . . . . . . . . . . . . 3.17. MSE alakulása a pH probléma esetén . . . . . . . . . . . . . . . . . . . . 3.18. MSE alakulása az ICT probléma esetén . . . . . . . . . . . . . . . . . . . 3.19. MSE alakulása a 6 változós probléma esetén . . . . . . . . . . . . . . . . . 3.20. Iteratív hibrid tanulási stratégia az antecedens és a konzekvens paraméterekre 3.21. Nemlineáris antecedens paraméterek kódolási elrendezése Takagi-Sugeno fuzzy rendszerekben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.22. Példa B-spline neurális hálózat kifejezésfájára . . . . . . . . . . . . . . . . 3.23. A függvény mutáció m˝uvelete . . . . . . . . . . . . . . . . . . . . . . . . 3.24. A terminális mutáció m˝uvelete . . . . . . . . . . . . . . . . . . . . . . . . 3.25. A génátadás m˝uvelete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.26. Cél- és hibaértékek a 6 változós problémára GP használatával . . . . . . . . 3.27. Cél- és hibaértékek a 6 változós problémára BP használatával . . . . . . . . 3.28. Tapasztalati valószín˝uségi eloszlásfüggvény a pH problémára . . . . . . . . 3.29. Tapasztalati valószín˝uségi eloszlásfüggvény az ICT problémára . . . . . . . 3.30. Tapasztalati valószín˝uségi eloszlásfüggvény a 6 változós problémára . . . . 3.31. Minta baktérium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.32. A bakteriális mutáció m˝uvelete . . . . . . . . . . . . . . . . . . . . . . . . 3.33. A génátadás m˝uvelete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.34. Szimulációs eredmények a második függvényre lineáris approximációt alkalmazva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.35. Szimulációs eredmények a második függvényre RENO-t alkalmazva . . . . 3.36. Szimulációs eredmények a második függvényre FS-ID3-t alkalmazva . . . 3.37. Szimulációs eredmények változó baktériumhosszra lineáris approximációt alkalmazva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vii

56 58 59 61 65 66 66 67 68 75 75 81 83 83 84 89 90 91 91 91 95 96 96 99 100 100 101

Táblázatok jegyzéke 3.1. 3.2. 3.3. 3.4. 3.5.

Rögzített szabályszám . . . . . . . . . . . . . . . . . . . . . . . . . . . . A megszüntet˝o paraméter (β) hatása . . . . . . . . . . . . . . . . . . . . . Az eredmények összefoglalása a pH problémára . . . . . . . . . . . . . . . Az eredmények összefoglalása az ICT problémára . . . . . . . . . . . . . . A teljes fuzzy szabálybázis optimalizálása a pH problémára a LevenbergMarquardt módszerrel és a Bakteriális Evolúciós Algoritmussal . . . . . . . 3.6. MSE, MSRE és MREP átlagértékek a tanító és a tesztelési mintákra minden probléma esetén a BEA használatával . . . . . . . . . . . . . . . . . . . . 3.7. MSE, MSRE és MREP átlagértékek a tanító és a tesztelési mintákra minden probléma esetén a BMA használatával . . . . . . . . . . . . . . . . . . . . 3.8. Az MSE kritérium alapján az összes futtatás során talált legjobb egyed . . . 3.9. Az MREP kritérium alapján az összes futtatás során talált legjobb egyed . . 3.10. Hiba átlagértékek változó szabályszám esetén . . . . . . . . . . . . . . . . 3.11. Legjobb egyedek változó szabályszám esetén . . . . . . . . . . . . . . . . 3.12. Takagi-Sugeno fuzzy modellek identifikálására kapott eredmények . . . . . 3.13. A BIC, MSE, MSRE, és MREP átlagértékei és a modellbonyolultság az Nkl´on paraméter értékét változtatva . . . . . . . . . . . . . . . . . . . . . . 3.14. A BIC, MSE, MSRE, és MREP átlagértékei és a modellbonyolultság az Ninf paraméter értékét változtatva . . . . . . . . . . . . . . . . . . . . . . . . . 3.15. A két módszerben (genetikus és bakteriális) használt paraméter értékek . . 3.16. A BIC, MSE, MSRE, és MREP átlagértékei és a modellbonyolultság a pH problémára . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.17. Az összes futtatás során talált legkisebb BIC érték˝u egyedhez tartozó modellstruktúra a pH probléma esetén . . . . . . . . . . . . . . . . . . . . . . 3.18. A BIC, MSE, MSRE, és MREP átlagértékei és a modellbonyolultság az ICT problémára . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.19. Az összes futtatás során talált legkisebb BIC érték˝u egyedhez tartozó modellstruktúra az ICT probléma esetén . . . . . . . . . . . . . . . . . . . . . 3.20. A BIC, MSE, MSRE, és MREP átlagértékei és a modellbonyolultság a 6 változós problémára . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.21. Az összes futtatás során talált legkisebb BIC érték˝u egyedhez tartozó modellstruktúra a 6 változós probléma esetén . . . . . . . . . . . . . . . . . . 3.22. A BP-re és a GP-re vonatkozó statisztikai következmények a Mann-Whitney és a medián teszt módszerekkel . . . . . . . . . . . . . . . . . . . . . . . . 3.23. Szimulációs eredmények illusztrációja . . . . . . . . . . . . . . . . . . . . viii

47 48 57 57 59 63 63 64 65 71 71 79 85 85 86 87 87 87 88 88 89 90 98

1. fejezet Bevezetés. Célkituzések, ˝ módszerek, el˝ozmények. A számítási intelligencia módszerek egyre jelent˝osebb szerepet játszanak a nagy bonyolultságú m˝uszaki és más alkalmazott rendszerek modellezésében, irányításában és a velük kapcsolatos döntési, és optimalizációs feladatok végrehajtásában. Ma már ismertek olyan intelligens számítástechnikai modellek és technikák, amelyekkel az egyre nagyobb bonyolultságú modellezési, irányítási és optimalizációs feladatok hatékonyan végrehajthatók. Számos m˝uszaki területen, mint például a folyamatirányítás, távközlés, logisztika témájában, és más alkalmazott tudományban sok olyan probléma van, amelyek klasszikus matematikai módszerekkel nem jól kezelhet˝ok. A matematikailag nem jól kezelhet˝oséget többféle kategóriába sorolhatjuk. Az els˝o csoportba azok a feladatok tartoznak, melyeknél a rendszer analitikus modellje legalább elméletileg ismert. Ezen belül kétféle esetet különböztethetünk meg. Az els˝o alcsoportba tartozó problémák esetén a megoldáshoz szükséges algoritmus elméleti szempontból nem kezelhet˝o, azaz a számítási bonyolultsága polinomiálisnál rosszabb. Ide tartoznak például az NP-teljes problémák, melyek esetén a feladat méretének növekedésekor a megoldáshoz szükséges id˝o annyira megnövekszik, hogy az kezelhetetlenné válik. A második alcsoportba azokat a problémákat sorolhatjuk, amelyeknél a modell ugyan ismert, de nem adható meg rájuk zárt matematikai megoldás. Itt példaként említhetnénk az er˝osen nemlineáris rendszereket, amelyeket a folyamatirányításban lineáris módszerekkel próbálunk kezelni, ezek azonban rosszul approximálnak. A lineáris módszerek helyett érdemes ilyen esetekben numerikus iteratív megoldásokkal kísérletezni. A második f˝o kategóriába azok a problémák tartoznak, amelyeknél az analitikus modell nem ismert, esetleg nem is létezik, mert a rendszer nem-determinisztikus viselkedés˝u. Itt példaként hozhatjuk fel az orvos-biológiai mérnöki problémák legnagyobb részét, az id˝ojárással, mez˝ogazdasággal kapcsolatos modelleket, illetve az olyan nagyon bonyolult m˝uszaki rendszeregyütteseket, amelyekben nagyszámú változó van, melyek közül bizonyosak küls˝o változók és esetleg random viselkedés˝uek. Ide tartoznak az er˝osen nem-determinisztikus zajjal terhelt rendszerek is. A nehéz ipari, vagy pénzügyi problémákban sem rendelkezünk általában azzal a tudással, ami az algoritmikus megoldáshoz elengedhetetlen lenne. Például nem ismerjük az adott folyamat törvényszer˝uségeit. A harmadik, legnehezebben kezelhet˝o csoportba az olyan feladatokat sorolhatjuk, ahol

1

eleve jelent˝osége van az emberi pszichének, szubjektív tényez˝oknek is szerepük van. Ilyenek például az ember-gép rendszerek. Érdekes, hogy ezeknek a problémáknak egy jelent˝os részét emberi kezel˝ok meg tudják oldani, még ha szuboptimális módon is. A járm˝uvezetést hozhatnánk fel kézenfekv˝o példaként. A természettudósok, mérnökök régi ambíciója, hogy az ilyen problémákra automatizmust generáljanak. Ezt a vágyat jól mutatja Kempelen Farkas sakkozó automatája. Az érdemi megoldás lehet˝osége azonban csak a számítógép megjelenésével vált lehet˝ové, mely nagy lökést adott az olyan módszerekre irányuló kutatásnak, melyek az emberi intelligencia elemeit igyekeznek utánozni. Az ‘50-es években megjelentek már klasszikus mesterséges intelligencia módszerek, amelyek alapvet˝oen a szimbolikus logikára épültek és kisméret˝u, demonstratív példák esetében adtak megoldást, de valóságos problémákra nem, mivel nem tudták legy˝ozni a számítási bonyolultság korlátait. Ezeknek a módszereknek azonban számos olyan eleme van, amelyet a kés˝obbi módszerek fel tudtak használni továbbfejlesztve, ilyenek például a „ha-akkor” típusú modellek. A szekvenciális számítógéppel egyid˝oben elvi síkon megszülettek a párhuzamos gépek is (sejtautomaták) csak ezeket nem tudták realizálni technológiai és anyagi vonzataik miatt. Az 1960-as évek közepe táján megjelentek a korszer˝u intelligens módszerek, amelyeket összefoglaló néven lágy számítástudománynak (soft computing) nevezünk. E terület három f˝o alkotóelemét a fuzzy rendszerek, a neurális hálózatok és a különböz˝o evolúciós algoritmusok képezik. A fuzzy rendszerek alapötlete az emberi gondolkodásmód, emberi következtetések, döntések utánzásán alapul [53, 63]. Az ember gondolkodásmódja és bizonyos jelenségek nem írhatóak le pontosan a kétérték˝u logikával. Régebben is felmerült már a kétérték˝u logika kiterjesztésének az igénye, hogy ne csak „igaz” és „hamis” logikai értékeket használjunk, hanem lehet˝oség legyen átmenetek definiálására is. Sok olyan állítás van, amelyikr˝ol nem lehet élesen eldönteni, hogy igaz-e vagy hamis, hanem csak valamilyen mértéket lehet mondani az igazságtartalmáról. Ez a gondolat vezette el a ‘60-as években L. A. Zadeh-t a fuzzy logika megalkotásához [105]. A fuzzy logika a hagyományos (Boole-i) logika kiterjesztése. A fuzzy logikai változó a 0 és az 1 érték között tetsz˝oleges értéket felvehet, a 0 jelöli a „teljesen hamis” állítást, az 1 pedig a „teljesen igaz”-at. Ilyen értelemben a 0,5 körüli érték jelképezi a „félig igaz”-at, és például a 0,9 a „majdnem igaz”-at. A hagyományos logikai m˝uveletek is kiterjeszthet˝ok fuzzy logikára. A fuzzy logika segítségével definiálhatunk fuzzy halmazokat, fuzzy szabályokat és következtet˝o rendszereket is létrehozhatunk. Az A fuzzy halmazt az úgynevezett tagsági függvénnyel adhatjuk meg. A tagsági függvény minden egyes x alaphalmazbeli értékhez egy a [0,1] intervallumból vett értéket rendel aszerint, hogy az adott x érték mekkora mértékben eleme (tagja) az A fuzzy halmaznak. A tagsági függvény alakjától függ˝oen különböz˝o mérték˝u bizonytalanságot lehet belevinni az adott fogalom leírásába. A legelterjedtebb alakú tagsági függvények a háromszög, trapéz, és Gauss-görbe alakú tagsági függvények. A fuzzy halmazok segítségével fuzzy szabályokat definiálhatunk. A Zadeh által javasolt megoldás a fuzzy halmazok és a klasszikus „ha–akkor” típusú szabályok kombinációja volt. A korábbi szimbolikus megközelítéshez képest ez szubszimbolikus módszert eredményezett. A szubszimbolikus információ használata közel áll az emberi gondolkodásmódhoz, hiszen így olyan szabályokat fogalmazhatunk meg, amelyek ember által is könnyen értelmezhet˝ok, megadhatók. Az adott problémát leíró fuzzy szabályok alkotják a szabálybázist. A fuzzy következtet˝o rendszer egy adott bemenetre (megfigyelésre) a szabályok segítségével valamilyen kimenetet ad. 2

A Zadeh által javasolt kompozíciós következtetési algoritmust [106] a ‘70-es években E. H. Mamdani átalakította [77]. Olyan módszert fejlesztett ki, mely alacsonyabb számítási bonyolultságú, és a gyakorlatban könnyebben megvalósítható. Módszerét sikeresen alkalmazta egy nagy bonyolultságú er˝osen nemlineáris g˝ozgépes rendszer irányítására. Kés˝obb több sikeres ipari alkalmazás született, els˝oként például egy dániai cementm˝u irányítása fuzzy rendszerrel. A lágy számítási módszerek másik fontos kategóriáját a neurális hálózatok alkotják [46, 108]. Az emberek, és a különféle él˝olények sok olyan feladatot képesek megoldani, amellyel a számítógépek nem tudnak mit kezdeni. „A mindenki által jól ismert szúnyog például robotpilótával ellátott, helyb˝ol felszálló repül˝ogépnek is felfogható. Man˝overez˝oképessége tökéletes, soha nem zuhan le, sem induláskor, sem landoláskor. Sötétben és világosban egyforma biztonsággal repül. Motorja igen kis h˝oveszteséggel dolgozik, h˝ofoka szinte a környezetével azonos. Hajtóanyaga a természet megújuló er˝oforrásai közül való. Fény, szag, h˝osugárzás segítségével egyaránt navigál. Robotpilótája, amely mindezt irányítja és vezérli – és ezen kívül még sok minden mást is – ezredgramm nagyságrend˝u. A szúnyog még csak nem is a legkisebb „robotrepül˝ogép”. A Mymaridá-k (tojásparazita hártyásszárnyúak) közé tartozó parányfürkész (Allaptus minimus) testhossza 0,2 mm, szárnyainak fesztávolsága 0,6 mm, súlya 0,02-0,03 milligramm. Szárnyát másodpercenként 400 fordulattal forgatja, jól repül. És nemcsak repülni tud, de ugyanezeknek a szárnyaknak a mozgatásával a víz alatt kit˝un˝oen úszik is. Teljes irányító és vezérl˝oberendezésének – azaz idegrendszerének – összsúlya milliomod gramm nagyságrend˝u” [41]. Az ilyen él˝olények anélkül képesek ezeket az összetett feladatokat megoldani, hogy bármit is tudnának a bonyolult matematikáról. Idegrendszerük másként m˝uködik, mint a számítógépek összetett algoritmusai. A biológiai kutatások, az idegsejt tanulmányozása indította útjára azt az elképzelést, hogy a bonyolult, él˝o szervezetek mintájára hozzanak létre újfajta számítási rendszereket. A cél az volt, hogy az él˝olények agyának, a biológiai neurális hálózatnak a mintájára mesterséges neurális hálózatot alkossanak. Olyan eszközt, mely az adott feladatot nem algoritmikusan oldja meg, hanem a természetb˝ol ellesett módon, mintákból, példákból nyert tapasztalatok felhasználásával, tanulás útján alakítja ki a feladatmegoldó képességét. A mesterséges neurális hálózat nagy hasonlóságot mutat a természetes neurális hálózatokkal felépítésében is, mert a feladatot a sok, egymással összekötött elemi egység (neuron, idegsejt) oldja meg, a párhuzamos m˝uködés miatt elég gyorsan. A neurális hálózatok számos feladat megoldásánál, nemcsak alkalmasnak, hanem alapvet˝oen jobbnak is bizonyulnak, mint a hagyományos szekvenciális algoritmikus számítási rendszerek. Ilyen feladatok tipikusan a különféle felismerési problémák, kezdve a viszonylag egyszer˝u nyomtatott számok és karakterek felismerését˝ol a jóval bonyolultabb kézírás, kép- és egyéb alakzat-felismerésekig. A felismerési feladatokat az él˝olények minták alapján tanulják meg. Egy felismerési feladat az ember számára nem jelent gondot, annak ellenére, hogy nehéz megmondani, hogy milyen módon végzi a felismerést, és ezért nehéz olyan algoritmikus megoldást találni, amely hasonlóan sikeres a felismerési feladat megoldásában, mint az ember. A tudás rendelkezésre állhat adatok formájában is. Ezeket az adatokat felhasználva taníthatjuk meg a neurális hálózatot a feladat megoldására. A tanítás során az a cél, hogy a hálózat megvalósítsa a kívánt leképezést a bemen˝o adatok és a kimen˝o adatok között. A megtanított háló egy bemenetre adott válaszának és a mintaadatok között szerepl˝o 3

kívánt válasznak a különbsége kell hogy minimális legyen. Tehát a háló úgy fog viselkedni, hogy követi a minták formájában megfogalmazott törvényszer˝uségeket. A tanítási folyamatban a háló aktuális kimenetének és a kívánt kimenetnek a különbségét kell minimalizálni. Számos tanítási módszert fejlesztettek ki, melyek a hiba visszaterjesztésén alapulnak, vagyis a háló kimenet és a kívánt kimenet közötti különbséget visszaterjesztve módosulnak a háló paraméterei (súlyok) lépésr˝ol-lépésre, egyre jobb megoldást adva ezáltal az adott problémára. Nem kell a hálózatnak tökéletes leképezést megvalósítania, azaz nem kell a mintákra tökéletesen ráilleszkednie. Fontosabb az általánosító képesség, vagyis az, hogy más adatokra is megfelel˝o eredményt adjon a hálózat. A neurális hálózatoknak sok fajtája van, számos tanuló algoritmus létezik, és sok feladattípusra alkalmazhatóak. A számítási intelligencia terület harmadik csoportját az evolúciós algoritmusok alkotják [36, 42]. Számos optimalizációs módszer van, melyet a természetben folyó jelenségek inspiráltak. Ezen algoritmusok el˝onye, hogy képesek megoldani a problémákat és közelít˝o megoldást találni akkor is, ha a probléma nemlineáris, magas dimenziószámú, nem folytonos. Semmilyen speciális tulajdonságot nem követelnek meg a modellezni kívánt rendszerr˝ol, az irányítani kívánt folyamatról. Az eredeti genetikus algoritmust J. Holland fejlesztette ki a magasabbrend˝u él˝olények populációit, fejl˝odését meghatározó biológiai folyamatok modellezésére [48]. Ezekben az algoritmusokban az egyedek, akárcsak a természetben, populációkat alkotnak, amelyek egymástól részben vagy egészben elzártan létez˝o szaporodási közösségek. Az egyed reprezentációja technikailag egy kód (kromoszóma, gén), amely úgy tárolja az egyed tulajdonságait, mint ahogy a DNS egy él˝olényét. Mutációnak nevezzük egy egyed génkészletének véletlenszer˝u megváltozását, ezt az algoritmusban a kód véletlenszer˝u megváltoztatása reprezentálja. A szelekció azt jelenti, hogy csak a legmegfelel˝obb egyedek hozhatnak létre utódokat, a gyengék kipusztulnak. Ez az algoritmusban a rossz tulajdonságú egyedek törlését, és a jó tulajdonságúak megtartását jelenti. A szaporodás során, keresztezéssel hoznak létre utódokat az egyedek, és az utódok még megfelel˝obbek lehetnek, mint a szüleik. Ezek az evolúciós folyamatokat utánzó módszerek könnyen alkalmazhatók optimalizációs problémák megoldására. Egy egyed a feladat egy megoldását jelenti. A populáció folyamatos fejl˝odése biztosítja, hogy egyre jobb egyedeket kapunk, azaz a problémát egyre jobban sikerül megoldani, a közelítés egyre pontosabb lesz. A természet sok ötletet ad különböz˝o evolúciós módszerek alkotására a hagyományos genetikus algoritmus mintájára. Az egyik legújabb ilyen módszer a ‘90-es évek második felében kifejlesztett bakteriális evolúciós algoritmus [82]. Ez az eljárás a baktériumok evolúciós jelenségén alapul, és hasonlóan a genetikus algoritmusokhoz, a természetben végbemen˝o jelenségeket próbálja utánozni, és felhasználni problémák megoldására. Ennél a módszernél is egy populáció fejl˝odése zajlik (baktériumpopuláció), és az él˝olények különböz˝o folyamatokban vesznek részt. Az egyes baktériumok képesek átadni génrészleteiket más baktériumoknak. Az algoritmusban erre alapozva két operátort alkalmazunk, az ún. bakteriális mutációt és a génátadást (géntranszfert). A bakteriális mutáció egy baktériumon hoz létre olyan változásokat, amelyek által a baktérium fejl˝odik. Ellentétben a genetikus algoritmusoknál használt mutációval, itt ez a folyamat másképp hajtódik végre. A kromoszómán végrehajtott változtatás el˝ott ugyanis a baktérium osztódik, és több ugyanolyan példány („klón”) keletkezik bel˝ole. A változtatás a baktérium összes példányán végrehajtódik (az eredeti baktérium kivételével), természetesen mindegyik lemásolt baktériumon más jelleg˝u változtatást okozva. 4

Ezek után a legmegfelel˝obb baktérium megmarad, a többi elpusztul. A bakteriális mutáció biztosítja tehát az egyedek fejl˝odését, egyre tökéletesebbé válását. Az algoritmusban használt másik operátor a génátadás. Ez teszi lehet˝ové az egyedek közti információáramlást a populációban. Ennek során a populációt két egyenl˝o részre bontjuk: „jó egyedekre” és „rossz egyedekre”. A jó egyedek átadják valamely génrészletüket a rossz egyedeknek. Ezáltal az egész populációban a keresett megoldáshoz közeled˝o, egyre jobb egyedek lesznek. A fentin kívül sok egyéb evolúciós és él˝olényeket, él˝olénypopulációk viselkedését utánzó módszert fejlesztettek ki. Említhetjük például a genetikus programozást [66, 67], a többpopulációs genetikus algoritmust [87, 107], a többkritériumú genetikus algoritmusokat [38, 39], az ún. hangyakolóniákat [29, 30], a vírus alapú evolúciós algoritmust [68], a „ragadozó-zsákmány” módszert [3], a méhkirályn˝o evolúciós algoritmust [51], a mesterséges immunrendszereket [27, 44], és a részecske-sereg optimalizációt [33, 52]. A számítási intelligencia módszerek a klasszikus szimbolikus mesterséges intelligencia módszerekhez képest bonyolultságcsökkenést eredményeztek. Annak ellenére, hogy ez a csökkenés a problémák jó részének megoldásához nem elegend˝o, sikerült a kezelhet˝o és modellezhet˝o problémák határait kitolni. Az utolsó évtized fejlesztései már lényegesebb csökkenést eredményeztek. Olyan módszerek jelentek meg, melyek a korábbi technikákat továbbfejlesztették, kombinálták, valamint egyéb trükkökkel hatékonyabbá tették. A szimbolikus logikához képest a Zadeh-féle megközelítésmód komplexitáscsökkenést eredményezett, de a leíráshoz szükséges szimbólumok számának redukciója csak valamilyen konstans faktorral történhetett, tehát amennyiben egy k dimenziós állapottérben modellezhet˝o rendszer leírásához pl. a szimbolikus megközelítésben O(T k ) nagyságrend˝u szabályra volt szükség, a fuzzy megoldásban O((T /c)k ) szabály is elegend˝o, azaz a redukció tényez˝oje ck . Az így megmaradó modellméret azonban még mindig exponenciális k, vagyis az állapotváltozók számának függvényében. A bonyolultság azonban tovább csökkenthet˝o, széls˝oséges esetben akár – az adott modelltípuson belül maradva – a lehetséges minimumig, amely 2k számú szabály. E redukció alapja a s˝ur˝u szabálybázisokról a ritka szabálybázisokra történ˝o áttéréssel lehetséges. Ilyenkor azonban nem alkalmazhatóak a Mamdani-féle (és az ezzel rokon) fuzzy következtet˝o algoritmusok, hanem sajátos, interpolatív következtet˝o módszereket kell alkalmazni [61]. Nyilvánvaló azonban, hogy ezeknek az eljárásoknak a közös korlátját az jelenti, hogy egy k állapotváltozós modell mindenképpen exponenciális, mégpedig k-adik hatvánnyal arányos bonyolultságú. A bonyolultság akkor csökkenthet˝o tovább, ha lehet˝oség van a bemeneti állapottér valamilyen partícionálására. Ilyenkor a modell állapotterét legalább két altérre partícionáljuk, melyek direkt szorzata adja a tényleges állapotteret. Az egyik altérben az állapotváltozóknak egy olyan csoportja szerepel, amelyek alkalmasak arra, hogy segítségükkel a modell további résztvev˝o állapotváltozóit lokálisan redukáljuk, tehát a teljes állapotteret ebben az altérben partícionáljuk, majd a partíció minden egyes elemében egymástól független, és lehet˝oség szerint a teljes állapotváltozó-készlethez képest csökkentett méret˝u állapotváltozó-számú alszabálybázisok, azaz részmodellek alkothatók. Ezzel az eljárással a bonyolultság igen drasztikusan csökkenthet˝o, hiszen az eredeti állapotváltozó-számhoz képest lényegesen kisebb hatványkitev˝oj˝u exponenciális bonyolultság is elérhet˝o. Ily módon hierarchikus szabályrendszer jön létre, melyben van egy metaszabálybázis, és lokális alszabálybázisok. A fels˝o szinten (metaszint) el˝oször a megfelel˝o alszabálybázis kiválasztására kerül sor. Ez a metaszabályok segítségével történik, amelyek vagy bizonyos, a lokális mo5

delleket lényegében elkülönít˝o változók értéke alapján, vagy speciálisan a rendszer lokális m˝uködését szabályozó változó értéke alapján választják ki a megfelel˝o lokális modellt. Hierarchikus szabályrendszerekre jó példa Sugeno pilóta nélküli helikopter kísérlete [96], mely azóta tényleges alkalmazásba is került. A helikoptervezetési probléma értelemszer˝uen strukturálható, a természetes struktúrát a különböz˝o repülési man˝overek összessége adja, melyeknél más és más állapotváltozó-részhalmaz a jellemz˝o. A pilóta ennek megfelel˝oen mindig csak a m˝uszerek egy részhalmazát figyelve vezeti a gépet, ugyanis más változók dominálnak az „emelkedés”, és megint mások például az „el˝ore repülés” vagy a „helyben lebegés” m˝uvelete közben. Nagyméret˝u komplexitáscsökkenés érhet˝o el az el˝obbi két módszer kombinálásával, azaz a hierarchikus interpolatív fuzzy szabálybázisos modellek alkalmazásával [62]. Tekintettel arra, hogy analitikus modellel nem rendelkez˝o, vagy nemlineáris problémákkal foglalkozunk, ezért központi jelent˝osége van annak, hogy numerikus mérési adatok alapján hatékony közelít˝o modelleket állítsunk fel. A modell közelít˝o pontosságú ezért csak kvázi-optimális, a rendszert valamilyen pontossági határon belül modellezi, vagy a problémát valamilyen pontossággal oldja meg. Ugyanakkor a módszernek hatékonynak is kell lennie, azaz a számítási bonyolultságnak kezelhet˝onek kell lennie. Ennek a két követelménynek az egyidej˝u teljesítése, azaz a pontosság-kezelhet˝oség viszonynak a megfelel˝o beállítása nehéz, ám kulcsfontosságú kérdés. Nehéz, mert e két követelmény egymásnak ellentmondó. Kulcsfontosságú, hiszen amennyiben a kett˝o közül az egyik nem megfelel˝o, akkor az alkalmazott módszer nem oldja meg a problémát, az továbbra is kezelhetetlen marad. Ezt a kérdéskört jól illusztrálja az úgynevezett fuzzy macska-egér probléma [64, 65]. A macska szeretné elfogni az egeret. Ehhez egy szabálybázist használ, melynek segítségével az egér mozgási jellemz˝oi (pozíció, sebesség stb.) és ismert tulajdonságai alapján képes kikövetkeztetni, hogy hol lesz az egér egy bizonyos id˝o múlva. Az egér mozgástere egy raszterhálóval felosztott sík. A macska két lépésben próbálja megtalálni az egeret. Az els˝o lépésben a szabálybázis alapján megpróbálja meghatározni, hogy az egér melyik rasztermez˝oben lesz a keresés id˝oszakában, a második lépésben pedig a mez˝on belül pl. kimerít˝o kereséssel keresi meg az egeret. Ha a szabálybázis sok szabályt tartalmaz, azaz a modell finom és pontos, akkor a rasztermez˝o mérete kicsi, ezért a megfelel˝o rasztermez˝o azonosítása után az egér könnyen megtalálható. A gond viszont az, hogy a sok szabály miatt a következtetés lassabb lesz, ezért a következtetési fázis tovább tart, és nem eléggé hatékony a módszer. Ha viszont a szabálybázis kisméret˝u, akkor a következtetés gyorsabb, de ilyenkor a modell pontatlanabb, a rasztermez˝o nagy kiterjedés˝u, ezért a keresés második lépése fog tovább tartani. A cél tehát egy olyan modell felállítása, mely esetén a pontosság és kezelhet˝oség együttesen a legkedvez˝obb, a komplex optimumot kell megtalálni, ami elfogadható pontosságú és költség˝u. Az értekezés célkit˝uzése olyan numerikus adatok alapján történ˝o identifikációs módszerek kifejlesztése amelyek az irodalomban ismerteknél meghatározott kritériumok szerint jobbak. A modell-identifikáció alapvet˝oen két lépésb˝ol áll. Az els˝o lépésben a problémát, rendszert még kell˝o pontossággal leíró változók minimális halmazát keressük meg. A második lépésben ezen állapotváltozók terében egy adott kritérium szempontjából megfelel˝o jóságú modellt határozunk meg. Ebben az értekezésben a második lépéssel foglalkozom els˝osorban, mégpedig olyan problémáknál, ahol numerikus adatok alapján tetsz˝oleges dimenziószámú statikus modell identifikációja történt meg. Többféle technikával felállított modellt, 6

többféle identifikációs technikával határoztam meg, ezek alternatívaként is szóba jönnek, de lehetséges, hogy valamelyik lényegesen kedvez˝obb. A következ˝okben ismertetem az értekezés felépítését. A jelen bevezetésben megkíséreltem röviden megfogalmazni a m˝uszaki problémát, a megoldásra rendelkezésre álló eszköztárat és az értekezés szempontjából szóba jöv˝o módszereket. A 2. fejezet szakirodalmi áttekintést ad a vizsgálat tárgyát képez˝o számítási intelligencia módszerekr˝ol, valamint a numerikus adatok alapján identifikációt megvalósító módszerekr˝ol. A 3. fejezet tartalmazza a saját kutatási eredményeimet és ezen belül kerülnek megfogalmazásra az ezen eredményeim lényegét megfogalmazó tézisek. Az új eredmények bemutatása kapcsán minden alkalommal kitérek arra, hogy az irodalomból megismert eljárásokkal esetenként többféle kiértékelési szempontból összehasonlítsam a kapott eredményeket, kiértékeljem azok el˝onyeit, hátrányait. A 4. fejezet tartalmazza az elért eredmények rövid összefoglaló értékelését, és a további kutatási irányokat. Az értekezést az irodalmi hivatkozások jegyzéke zárja, amely tartalmazza saját közleményeimet is.

7

2. fejezet A számítási intelligencia fejl˝odésének és módszereinek áttekintése Ez a fejezet szakirodalmi áttekintést nyújt a számítási intelligencia módszerekr˝ol és az alkalmazott identifikációs technikákról. A fejezet els˝o részében a fuzzy rendszerek alapjait tekintem át. A második alfejezetben az evolúciós módszerekr˝ol mutatok átfogó képet, és részletesen bemutatom a bakteriális evolúciós algoritmusokat. A harmadik rész a neurális hálózatok témakörébe enged betekintést, és tanuló algoritmusokat is bemutat.

2.1. Fuzzy rendszerek A mindennapi emberi gondolkodásmód sok eleme és bizonyos objektív jelenségek nem írhatóak le pontosan a megszokott (Boole-féle) kétérték˝u logikával. Régebben felmerült már a kétérték˝u logika kiterjesztésének az igénye, azaz hogy ne csak „igaz” és „hamis” logikai értékeket használjunk, hanem lehet˝oség legyen átmenetek definiálására is. Sok olyan állítás van, amelyikr˝ol nem lehet élesen eldönteni, hogy igaz-e vagy hamis, hanem csak valamilyen mértéket lehet állítani az igazságtartalmáról. Ez a gondolat vezette el a ‘60-as években L. A. Zadeh-t a fuzzy logika megalkotásához [105]. Nyilvánvalóvá vált, hogy ha bonyolult feladatok megoldására alkalmas intelligensebb eszközöket szeretnénk létrehozni, jobb eredményt érhetünk el úgy, ha az emberi logikához jobban közelít˝o módon írjuk le a rendszerek viselkedését. A fuzzy logika a hagyományos logika kiterjesztése. A fuzzy logikai változó a 0 és az 1 érték között tetsz˝oleges értéket felvehet, a 0 jelöli a „teljesen hamis” állítást, az 1 pedig a „teljesen igaz”-at. Ilyen értelemben a 0,5 körüli érték jelképezi a „félig igaz” állítást, és például a 0,9 a „majdnem igaz”-at. A hagyományos logikai m˝uveletek is kiterjeszthet˝ok fuzzy logikára. Definiálhatunk fuzzy halmazokat, fuzzy szabályokat és következtet˝o rendszereket is létrehozhatunk. A következ˝okben a fuzzy halmazokat, a fuzzy halmazokon értelmezett alapm˝uveleteket, a fuzzy relációkat, a fuzzy szabályokat és a fuzzy következtet˝o rendszereket vezetem be.

8

2.1.1. Fuzzy halmazok A hagyományos halmazelméletben valamely X alaphalmaz egy A halmazát megadhatjuk például a karakterisztikus függvénye segítségével, amely minden olyan x alaphalmazbeli értékhez 1-et rendel, amelyik eleme az A halmaznak, a többi x értékhez pedig 0-át: ( 1, ha x ∈ A κA (x) = 0, ha x ∈ / A. Minden egyes x alaphalmazbeli érték tehát egyértelm˝uen vagy eleme az A halmaznak vagy pedig nem eleme az A halmaznak. A fuzzy halmazok elmossák a határt a két eset között, egy halmazhoz való tartozás illetve nem tartozás között tetsz˝oleges átmenetet megengedve. A fuzzy halmazok határa tehát nem éles (crisp), hanem elmosódott (fuzzy). Az A fuzzy halmazt az úgynevezett tagsági függvénnyel adhatjuk meg [105]. A tagsági függvény minden egyes x alaphalmazbeli értékhez egy a [0,1] intervallumból vett értéket rendel aszerint, hogy az adott x érték mekkora mértékben eleme (tagja) az A fuzzy halmaznak: µA (x) : X 7→ [0, 1], ahol µA az A fuzzy halmaz tagsági függvénye, mely egyértelm˝uen megadja a halmazt, ha magát az X alaphalmazt ismerjük. Gyakorlati célokra különféle alakú tagsági függvényeket szoktak definiálni. A gyakorlati alkalmazások céljából a m˝uszaki rendszerekben leginkább a háromszög, a trapéz és a Gauss-görbe alakú tagsági függvények terjedtek el. A 2.1. áb-

2.1. ábra. Példák tagsági függvényekre

rán a „kb. 5” valós fuzzy szám leírását láthatjuk különféle alakú tagsági függvényekkel. A háromszög alakú esetben csak az x = 5-nél kapunk 1-es tagsági értéket, a trapéz alakúnál az 5-nél kicsit kisebb és az 5-nél kicsit nagyobb értéket is 1-es érték˝unek vesszük, míg a Gauss görbénél még a távoli valós számok sem kapnak pontosan 0 értéket. Ez a koncepció tehát kiválóan alkalmazható mérési bizonytalanságok, zajok megfelel˝o kezelésére is. Az ábrán látható tagsági függvények paramétereinek különböz˝o beállításaival megfelel˝oen finom átmenetet lehet elérni a 0-ás és az 1-es érték között. A 2.2. ábrán emberi magasságokat láthatunk fuzzy halmazokkal jellemezni. Három kategóriát különböztethetünk meg: „alacsony”, „középtermet˝u” és „magas” halmazokat. A tagsági függvények ebben a példában trapéz alakúak. Az ábrán jól látszanak a fuzzy megközelítés el˝onyei a hagyományos kétérték˝u logikával szemben. Kétérték˝u esetben éles lenne az átmenet, a 164 cm-es ember 1-es értékkel 9

2.2. ábra. Emberek magasságának jellemzése fuzzy halmazokkal

lenne „alacsony”, a 166 cm-es pedig egyáltalán nem számítana „alacsony”-nak. Fuzzy halmazokkal az átmenetet sokkal finomabban lehet megadni. Egy A fuzzy halmaz magján azt a crisp halmazt értjük, mely az alaphalmaz azon elemeit tartalmazza, amelyeknek a tagsági értékük az A fuzzy halmazban 1: core(A) = {x ∈ X | µA (x) = 1}. A halmaz tartója pedig a pozitív tagsági érték˝u alaphalmazbeli elemeket jelenti: supp(A) = {x ∈ X | µA (x) > 0}. Az A fuzzy halmaz α-vágata valamely α ∈ [0, 1] értékre azokat az alaphalmazbeli elemeket tartalmazó halmaz, amelyek tagsági értéke az A fuzzy halmazban legalább α: Aα = {x ∈ X | µA (x) ≥ α}. Ha az egyenl˝oséget nem engedjük meg, akkor a szigorú α-vágat definíciójához jutunk. Egy fuzzy halmaz konvex, ha minden α-vágata konvex. Az A fuzzy halmaz magassága a tagsági függvényének legnagyobb értéke: h(A) = sup µA (x). x∈X

Egy fuzzy halmaz akkor normális, ha a magassága 1.

2.1.2. Alapmuveletek ˝ fuzzy halmazokon A hagyományos halmazelméletben értelmezett három alapm˝uveletet végtelen sokféleképpen lehet általánosítani a fuzzy halmazok elméletében. A legelterjedtebbek a klasszikusnak számító Zadeh-féle definíciók [105]. Egy X alaphalmazon értelmezett A fuzzy halmaz Zadeh-féle komplemense A, ahol minden x ∈ X értékre: µA (x) = 1 − µA (x). 10

Az A és B fuzzy halmazok Zadeh-féle metszete: µA∩B (x) = min(µA (x), µB (x)), Zadeh-féle uniója pedig: µA∪B (x) = max(µA (x), µB (x)). A Zadeh-féle m˝uveletek illusztrációi a a 2.3. ábrán láthatók. Ha a tagsági függvényérték csak 0 és 1 lehet (crisp eset) akkor a hagyományos komplemens, metszet és unió m˝uveleteket kapjuk vissza. A három alapm˝uvelet sok egyéb módon is definiálható. Néhány általánosan elfogadott axiómát azonban mindig ki kell elégíteniük ezeknek a m˝uveleti definícióknak.

2.3. ábra. Standard (Zadeh-féle) fuzzy m˝uveletek

2.1.2.1. Fuzzy komplemensek A fuzzy komplemensképzés az egyváltozós c : [0, 1] 7→ [0, 1] függvénnyel adható meg. A függvénynek a következ˝o két axiómát kell teljesítenie: 1. axióma. c(0) = 1 és c(1) = 0 (peremfeltételek). 2. axióma. ∀a, b ∈ [0, 1] esetén, ha a ≤ b, akkor c(a) ≥ c(b) (monotonitás). Ezeken kívül még általában a következ˝o enyhébb (3a), vagy er˝osebb (3b) axiómát is meg szokás követelni a komplemenst˝ol: 11

3a. axióma. c folytonos függvény. 3b. axióma. ∀a ∈ [0, 1]-re c(c(a)) = a, vagyis c involutív. (3b teljesülése esetén 3a biztosan kielégül.) Mind a három (illetve négy) axiómának eleget tev˝o, két általános komplemens osztály, a Sugeno- és a Yager-féle komplemens. A Sugeno-komplemens alakja [95]: cλ (a) =

1−a , 1 + λa

(2.1)

ahol λ ∈ (−1, ∞). λ = 0 esetén a Zadeh-féle komplemenst kapjuk. A Yager-komplemens általános alakja: cw (a) = (1 − aw )1/w , (2.2) ahol w ∈ (0, ∞). w = 1 esetén itt is visszakapjuk a Zadeh-féle komplemenst. 2.1.2.2. Fuzzy metszetek A fuzzy metszetképzés általánosított m˝uveletét egy geometriai valószín˝uségi analógia alapján (trianguláris) t-normának nevezzük, és a következ˝o kétváltozós függvénnyel adjuk meg: t : [0, 1] × [0, 1] 7→ [0, 1]. A t-normára vonatkozó axiómák [63]: 1. axióma. ∀a ∈ [0, 1]-re t(a, 1) = a (peremfeltétel). 2. axióma. ∀a, b, c ∈ [0, 1]-re b ≤ c-b˝ol következik, hogy t(a, b) ≤ t(a, c) (monotonitás). 3. axióma. ∀a, b ∈ [0, 1]-re t(a, b) = t(b, a) (kommutativitás). 4. axióma. ∀a, b, c ∈ [0, 1]-re t(a, t(b, c)) = t(t(a, b), c) (asszociativitás). Általában további feltételeket is megkövetelnek a t-normától: 5. axióma. t folytonos függvény. 6a. axióma. t(a, a) < a (szubidempotencia), vagy 6b. axióma. t(a, a) = a (idempotencia). 7. axióma. Ha a1 < a2 és b1 < b2 , akkor t(a1 , b1 ) < t(a2 , b2 ) (szigorú monotonitás). A leggyakrabban használt t-normák a Zadeh-félén kívül az algebrai szorzat: t(a, b) = ab, a korlátos különbség: t(a, b) = max(0, a + b − 1) és a drasztikus metszet:

  a, tmin (a, b) = b,   0, 12

ha b = 1, ha a = 1, egyébként.

2.1.2.3. Fuzzy uniók A fuzzy unióképzés m˝uveletét a t-normával való duál kapcsolata miatt t-konormának (vagy másként s-normának) nevezzük és szintén egy kétváltozós függvénnyel adjuk meg: s : [0, 1] × [0, 1] 7→ [0, 1]. A t-normához hasonló axiómákat követelünk meg az s-normától is [63]: 1. axióma. ∀a ∈ [0, 1]-re s(a, 0) = a (peremfeltétel). 2. axióma. ∀a, b, c ∈ [0, 1]-re b ≤ c-b˝ol következik, hogy s(a, b) ≤ s(a, c) (monotonitás). 3. axióma. ∀a, b ∈ [0, 1]-re s(a, b) = s(b, a) (kommutativitás). 4. axióma. ∀a, b, c ∈ [0, 1]-re s(a, s(b, c)) = s(s(a, b), c) (asszociativitás). A t-normához hasonlóan általában további axiómákat is megkövetelnek: 5. axióma. s folytonos függvény. 6a. axióma. s(a, a) > a (szuperidempotencia), vagy 6b. axióma. s(a, a) = a (idempotencia). 7. axióma. Ha a1 < a2 és b1 < b2 , akkor s(a1 , b1 ) < s(a2 , b2 ) (szigorú monotonitás). A leggyakrabban használt s-normák a Zadeh-félén kívül az algebrai összeg: s(a, b) = a + b − ab, a korlátos összeg: s(a, b) = min(1, a + b) és a drasztikus unió:

  a, smax (a, b) = b,   1,

ha b = 0, ha a = 0, egyébként.

A t- és s-normák alkalmas megválasztásával különböz˝o mérték˝u szubjektivitást tudunk belevinni a halmazm˝uveletekbe, mivel érvényesek a következ˝o korlátok: tmin (a, b) ≤ t(a, b) ≤ min(a, b) illetve max(a, b) ≤ s(a, b) ≤ smax (a, b). Ilyenkor az egyenl˝otlenségek baloldalai jelentik a „pesszimista”, a jobboldalai pedig az „optimista” szemléletmódot.

13

2.1.3. Fuzzy relációk Két vagy több halmaz elemei közötti kapcsolat mértékét fuzzy relációkkal írhatjuk le. Ez a fogalom a klasszikus (crisp) reláció fogalmát általánosítja, amelynél két vagy több elem közötti kapcsolat vagy fenn áll, vagy pedig nem. A fuzzy relációt a halmazokhoz hasonlóan a tagsági függvénnyel adhatjuk meg: µR(x1 ,...,xn ) : X 7→ [0, 1], ahol X = X1 × X2 × · · · Xn , a relációban szerepl˝o alaphalmazok Descartes-szorzata. Az n alaphalmaz Descartes-szorzatával képzett halmaz egy x elemének részsorozata egy y elem (y ≺ x) akkor, ha yj = xj minden j ∈ J-re, J ⊂ Nn , ahol y = {yj | j ∈ J} az ×j∈J Xj halmaz eleme és |J| ≤ n. Egy X1 × X2 × · · · Xn halmazon értelmezett fuzzy relációnak egy sz˝ukebb Y halmazcsaládra vett projekcióját (vetületét) a µ[R↓Y] (y) = max µR (x) y≺x

összefüggés alapján határozhatjuk meg. A projekció bizonyos értelemben vett inverzének tekinthet˝o a hengeres kiterjesztés: µ[R↑X−Y] (x) = µR (y) minden x-re, amelyre (y ≺ x). Egy R fuzzy reláció valamely projekcióinak hengeres lezártja: µcyl{Pi } (x) = min µ[Pi ↑X−Yi ] (x), i∈I

ahol Yi az a halmazcsalád, amelyen a Pi projekció definiálva van.

2.1.4. Fuzzy szabályok A fuzzy halmazok segítségével természetes emberi nyelven könnyen tudunk szabályokat megfogalmazni. Egy f˝utési rendszerben például mondhatunk egy olyan szabályt, hogy „Ha kicsit hideg van és a h˝omérséklet süllyed, akkor közepesen f˝uts”. Ha ezután definiáljuk a h˝omérsékletre, a h˝omérsékletváltozásra és a f˝utésre vonatkozó tagsági függvényeket, akkor fuzzy szabályhoz jutunk. Egy egy bemenet˝u, egy kimenet˝u egyszer˝u fuzzy szabály alakja: R : Ha x = A akkor y = B, ahol x ∈ X a bemeneti változó, y ∈ Y a kimeneti változó, X a bemeneti változó alaphalmaza, Y a kimeneti változó alaphalmaza. A és B nyelvi változók. Az A az R szabály antecedense (premisszája), a B pedig az R szabály konzekvense (konklúziója). Több bemenet˝u, egy kimenet˝u fuzzy szabály általános ún. Mamdani-féle (ortogonálisan dekomponált) alakja [77]: R : Ha x1 = A1 és . . . és xn = An akkor y = B, ahol x = (x1 , . . . xn ) a bemeneti értékek vektora, xj ∈ Xj , X = X1 × X2 × · · · Xn az n-dimenziós alaphalmaz, A = (A1 , . . . An ) az antecedens halmazok vektora, A @ X, y ∈ Y 14

2.4. ábra. Fuzzy következtet˝o rendszer vázlata

a kimeneti változó, Y a kimeneti változó alaphalmaza, B a konzekvens halmaz, B @ Y . (A @ jel fuzzy részhalmazt jelent.) A szabály alkalmazásának feltétele, hogy az összes bemeneti változó pozitív mértékben essék a megfelel˝o antecedens halmazba. Több kimenet˝u szabályok esetén a kimenetek függetlenek egymástól, ezért az ilyen szabályok dekomponálhatók a fentivel megegyez˝o alakú egy kimenet˝ure, csökkentve ezzel a számítási igényt. Egyes szerz˝ok a fuzzy szabályokat implikációként interpretálják, például egy bemenet˝u esetben: R : A → B formában. Ez az interpretáció azonban a m˝uszaki gyakorlati alkalmazások szemszögéb˝ol nem jól értelmezhet˝o, ezért nem tárgyaljuk.

2.1.5. Mamdani-típusú fuzzy következtet˝o rendszerek A fuzzy halmazok elméletét felhasználhatjuk bonyolult, analitikus módon nem modellezhet˝o rendszerek kezelhet˝o leírására. Fuzzy szabályok segítségével az emberi gondolkodáshoz hasonlító következtet˝o rendszereket hozhatunk létre. A fuzzy rendszer vázlata a a 2.4. ábrán látható. Az illeszkedési mértéket meghatározó egység a megfigyelést hasonlítja össze a szabályok feltételrészeivel. Ennek alapján a következtet˝o gép valamilyen következtetési algoritmussal meghatározza a kimeneti fuzzy halmazt. Többféle következtetési módszer ismert, gyakorlati alkalmazásokban legelterjedtebb a Mamdani-módszer [77]. A kimenetet defuzzifikációs egységgel alakítjuk át éles (crisp) értékre. 2.1.5.1. A szabálybázis A szabálybázis tartalmazza a problémát leíró szabályokat, melyek a következ˝o alakúak: Ri : Ha x1 = A1,i és . . . és xn = An,i akkor y = Bi , ahol x = (x1 , . . . xn ) a bemeneti vektor, y a kimenet, Ai = (A1,i . . . An,i ) az antecedens halmazok vektora, Bi pedig a konzekvens halmaz az i. szabályban. A szabályokat alkotó nyel15

2.5. ábra. Illeszkedési mérték meghatározás

vi változóknak olyan fuzzy halmazokat kell tartalmazniuk, melyek együttesen legalább αvágataik uniójával lefedik a változó alaphalmazát, azaz bármely bemenetre van olyan fuzzy halmaza a változónak, mely ≥ α (ahol α ≥ 0, 5) tagsági érték˝u az adott bemenetre vonatkozóan. Vagyis ha egy nyelvi változó lehetséges értékei az A1 . . . An fuzzy halmazok, akkor ∀x ∈ X-re ∃i ∈ [1, n], hogy µAi (x) ≥ ε teljesül valamely pozitív ε-ra (ε lefedettség). Ez azért szükséges, hogy minden megfigyelésre legyen olyan szabály, amely alapján a rendszer képes valamilyen következtetést meghozni. 2.1.5.2. Az illeszkedés mértéke A következtetés elején meghatározzuk, hogy az adott bemenet mennyire illeszkedik a szabályokra. A megfigyelésvektor minden egyes elemét összehasonlítjuk mindegyik szabály feltételrészének ugyanezen komponensével. Legyen A∗ az n-dimenziós megfigyelésvektor. Az illeszkedési (tüzelési) mérték a j. dimenzióban az i. szabályban: n n oo wj,i = max min µA∗j (xj ), µAj,i (xj ) xj

(2.5 ábra), ahol µAj,i (xj ) az i. szabály j. dimenziójának tagsági függvénye. Ha a megfigyelés crisp vektor, akkor a fenti összefüggés a következ˝ore egyszer˝usödik: x∗ állapot (helyzet-) vektor esetén, a j. dimenzióban az illeszkedés mértéke: wj,i = µAj,i (x∗j ). Miután minden dimenzióban meghatároztuk az illeszkedés mértékét, kiszámítjuk az ered˝ot az egész antecedensre vonatkozóan is. Egy szabály alkalmazhatóságának (érvényességének) a mértékét antecedense minden egyes dimenziójának illeszkedési mértéke együttesen befolyásolja. Egy Ri szabály tüzelési mértéke a szabály antecedensei illeszkedési mértékeinek a minimuma lesz: n wi = min wj,i . j=1

A wi értéke azt adja meg, hogy az Ri szabály mekkora mértékben befolyásolja a következmény el˝oállítását az A∗ megfigyelés esetén. 16

2.6. ábra. Szabály következménye

2.1.5.3. A következtetés Miután egy megfigyelésre minden egyes Ri szabályhoz meghatároztuk annak wi tüzelési súlyát, el˝oállítjuk a szabályhoz tartozó következtetést. Ez a szabály konzekvensének wi -vel való „csonkolásával” (azaz halmazmetszetével) történik. A szabályhoz tartozó következtetés: µBi∗ (y) = min (wi , µBi (y)) (2.6 ábra). A teljes szabálybázishoz tartozó következtetést az így kapott Bi∗ következtetések uniójaként állítjuk el˝o: r µB ∗ (y) = max µBi∗ (y), i=1

ahol r a szabályok száma, uniónak pedig a Zadeh-féle m˝uveletet használtuk. A 2.7. ábrán a teljes következtetés látható egy éles bemenetre. A Mamdani-következtetésen kívül a gyakorlatban használatos más m˝uveleteken alapuló eljárás is. Az elterjedt Larsen-módszernél [70] csonkolás helyett a tüzelési súllyal szorozzuk a következményt, azaz a Zadeh-féle m˝uvelet helyett algebrai metszetet alkalmazunk: r

µB ∗ (y) = max{wi · µBi (y)}. i=1

2.1.5.4. Defuzzifikáció A következtetés ered˝ojeként a B ∗ fuzzy következményhalmazt kapjuk. Legtöbbször azonban egy rendszer kimeneteként nem fuzzy halmazt várunk, hanem éles értéket, mely konkrétan megadja a beavatkozás mértékét vagy módját. Ennek értelmében meghatározzuk azt az éles kimenetet, amely a következtet˝o gép által eredményezett fuzzy halmazt a legjobban jellemzi. Ez az eljárás a defuzzifikáció, melyre számos módszer ismert az irodalomban [47]. Az egyik a geometriai középpont módszer (COA), melynél a kimenetet a következ˝oképpen számítjuk ki: R µ ∗ (y)ydy y∈B ∗ B yCOA = R . µ ∗ (y)dy y∈B ∗ B 17

2.7. ábra. Teljes Mamdani-következtetés

Ennek hátránya, hogy bonyolult alakú B ∗ következmény esetén az integrál nehezen számolható. Egyszer˝ubb a hasonló elven alapuló, igen elterjedt súlypont módszer (COG)1 : Pr R ∗ i=1 y∈B ∗ µBi (y)ydy . yCOG = Pr R i ∗ i=1 y∈B ∗ µBi (y)dy i

Ez egyszer˝ubben számolható, mert itt az egyes Bi∗ részkonklúziókat külön integráljuk. Viszont az átlapolódó területeket többszörösen számoljuk. Egy másik defuzzifikációs eljárás a középs˝o maximum módszer (COM), mely a legnagyobb tagsági értékkel rendelkez˝o kimenetek közül a legnagyobb és a legkisebb y érték átlagát adja vissza eredményként. A magasság módszer is a fontosabb defuzzifikációs technikák közé tartozik. E módszer lényege, hogy mindegyik részkonklúzió legnagyobb tagsági érték˝u y értékeinek közepeit a részkonklúziók magasságaival súlyozva számítjuk a defuzzifikált y-t. A COG és a COM módszer összevetését illusztrálja a 2.8. ábra.

2.1.6. Takagi-Sugeno-típusú fuzzy irányítási rendszerek A Mamdani-típusú fuzzy rendszerekre alternatívát jelentenek az olyan rendszerek, amelyekben a szabályok konzekvense nem fuzzy halmaz, hanem valamilyen függvény. A szabá1

Az egyes irodalmi források gyakran eltér˝o neveket használnak ugyanarra a defuzzifikációs alapmódszerre illetve ugyanazt a nevet alkalmazzák különböz˝o eljárásokra. Célszer˝u mindig az adott defuzzifikációs módszer képlet alapján történ˝o definícióját tekinteni a konkrét elnevezés helyett. Az értekezésben COG defuzzifikációs módszeren az itt definiált összefüggést értem.

18

2.8. ábra. Példák defuzzifikációra

lyok általános alakja az ilyen típusú rendszerekben: Ri : Ha x1 = A1,i és . . . és xn = An,i akkor yi = fi (x1 , . . . , xn ), ahol xi , i ∈ [1, n] a bemeneti változók, fi pedig n-változós függvény. Ha fi konstans, akkor (nulladrend˝u) Sugeno, ha a bemenetek lineáris függvénye, akkor Takagi-Sugeno (vagy els˝orend˝u Sugeno), ha pedig magasabbrend˝u függvény, akkor Takagi-Sugeno-Kang (vagy általános Sugeno) fuzzy rendszerr˝ol beszélünk [97]. A következtetés menete hasonló a Mamdanitípusú rendszerekéhez, azaz el˝oször a szabályok illeszkedési mértékét határozzuk meg az adott megfigyelésre. Az illeszkedési mértékek alapján a kimenet könnyen számítható: Pr Pr wi · yi wi · fi (x1 , . . . , xn ) i=1 y = Pr = i=1 Pr . i=1 wi i=1 wi Nulladrend˝u Sugeno esetben, amikor a kimenetek konstansok (ci ), az ered˝o kimenet még egyszer˝ubb alakú: Pr i=1 wi · ci . y= P r i=1 wi A Sugeno típusú rendszerek el˝onye, hogy nincs szükség defuzzifikációs lépésre, a kimenet gyorsabban számítható. A Mamdani- és Takagi-Sugeno-típusú rendszerek határértékben ekvivalens voltát tárgyalja [54].

2.2. Evolúciós algoritmikus módszerek Az evolúciós módszerek a természetben lejátszódó, az él˝olények biológiai folyamatait utánzó optimalizációs technikák. Ezen módszerek el˝onye, hogy képesek megoldani a problémákat és közelít˝o megoldást találni akkor is, ha a probléma nemlineáris, sokdimenziós, nem folytonos. Hatékony eszköznek bizonyulnak nemlineáris, multikritériumú, kényszerekkel kiegészített optimalizációs feladatok megoldására. Alapelvük a megoldások egy populációján 19

történ˝o keresés, melyet a biológiából megismert törvényszer˝uségek vezérelnek. A modellezni kívánt rendszert˝ol semmilyen speciális tulajdonságot nem követelnek meg. Ebben a részben ennek a területnek az alapjait tekintem át. Az els˝o részben a klasszikusnak számító genetikus algoritmusokat mutatom be röviden. Utána a genetikus programozást részletezem, majd pedig az értekezésben fontos szerepet játszó bakteriális evolúciós algoritmusokról írok. Végezetül egyéb technikákra is utalok.

2.2.1. Genetikus algoritmusok A genetikus algoritmusok alapötlete J. Holland-tól származik [48], aki Darwin evolúciós elméletét [28] felhasználva hatékony optimalizációs módszert fejlesztett ki. Az evolúciós elmélet szerint az él˝olénypopulációk folyamatosan fejl˝odnek, az él˝olények egyre tökéletesebbé válnak, egyre jobb egyedek fejl˝odnek ki. A fejl˝odési folyamatot a természetes kiválasztódás vezérli, jobb egyedek nagyobb eséllyel maradnak fent, míg a gyengébb él˝olények elpusztulnak. Ezt az elvet felhasználva, az evolúciós folyamatot szimulálva optimalizálási feladatok megoldására alkalmas algoritmusokat kapunk. Ezekben az algoritmusokban egy egyed a feladat egy megoldását jelenti. A populáció folyamatos fejl˝odése biztosítja, hogy egyre jobb egyedeket kapunk, azaz a problémát egyre jobban sikerül megoldani, a közelítés egyre pontosabb lesz. 2.2.1.1. Gyakran használt fogalmak Az alábbiakban összefoglalom a evolúciós algoritmikus módszerekben leggyakrabban használt fogalmakat: gén: funkcionális entitás, amely az egyed egy speciális tulajdonságát kódolja (pl. fuzzy szabály) allél: a gén értéke (pl. a fuzzy szabályt alkotó fuzzy halmazok paramétereinek az értékei) genotípus: az egyed alléljainak kombinációja fenotípus: az egyed tulajdonságainak az összessége egyed: kromoszóma, egy jelölt a feladat megoldására populáció: egyedek összessége generáció: egyid˝oben létez˝o egyedek alkalmassági (fitnesz) függvény: az egyedek jóságának, alkalmasságának mértéke evolúció: a populáció fejl˝odése, tökéletesedése szelekció, kiválasztás: bizonyos egyedek vagy egyedcsoportok életben maradását vagy szaporodását gátolja, másokét pedig megengedi keresztezés: két egyed kromoszómájának kombinálása mutáció: véletlenszer˝u változás a kromoszómában migráció: egyed vándorlása egyik populációból a másikba konvergencia: az egyedek tulajdonságainak fokozatos közeledése egymáshoz és az optimumhoz

20

2.9. ábra. Az evolúció folyamata egy maximumkeresési példában

2.2.1.2. Az algoritmus Az eredeti genetikus algoritmus folyamata a következ˝o: kezdeti populáció létrehozása generáció=0 amíg generáció < max. generáció { egyedek rangsorolása az alkalmassági érték alapján szelekció keresztezés mutáció visszahelyettesítés generáció = generáció + 1 } El˝oször a kezdeti populációt alakítjuk ki. A populáció egyedei a probléma egy-egy megoldását adják. Megkülönböztetünk bináris és valós-kódolású genetikus algoritmusokat. El˝obbinél az egyedek kromoszómája egy bináris string, utóbbi esetén pedig valós számokból álló vektor. A kezdeti populáció kialakítása véletlenszer˝uen történik, a keresési térb˝ol Negyed pont kiválasztásával. Az algoritmus futása során az egyedek egyre jobban közelednek az optimális megoldás felé. Ezt szemlélteti a 2.9. ábra maximumkeresési probléma esetén. A maximális generáció szám és az egyedek száma (Negyed ) paraméterek, melyeket el˝ore megadunk. A maximális generáció szám helyett megadhatunk más leállási feltételt is, például megfelel˝o megoldás elérésekor megállhatunk.

21

2.2.1.3. Az alkalmassági (fitnesz) függvény Az alkalmassági (fitnesz) függvény segítségével rangsoroljuk az egyedeket a populációban. Az algoritmus megfelel˝oen hatékony m˝uködéséhez fontos az alkalmassági függvény helyes megválasztása. Minél nagyobb egy egyed alkalmassági értéke, annál nagyobb a túlélési esélye. Minimumkeresési probléma esetén az adott függvényt transzformáljuk az alkalmassági érték kiszámításához, hiszen minél kisebb a függvény értéke annál nagyobb alkalmassági érték tartozik hozzá. Ezenkívül az alkalmassági értékek pozitívak. Gyakran egy probléma megoldása során a cél a hibaérték minimalizálása. Ilyenkor a hibából valamilyen transzformációval állíthatjuk el˝o az alkalmassági értéket. 2.2.1.4. Szelekció A szelekció (kiválasztás) során azokat az egyedeket választjuk ki a populációból, melyek az utódok létrehozásában fognak részt venni. Egy egyed több utódot is létrehozhat, az alkalmassági értékét˝ol függ˝oen. A legegyszer˝ubb kiválasztási algoritmus a rulett kerék módszer, vagyis a sztochasztikus kiválasztás cserével („stochastic sampling with replacement”). A populációt egy rulett keréken ábrázoljuk, ahol az egyes egyedekhez az alkalmassági értékükkel arányos méret˝u körcikk tartozik. A kerék kerülete az egyedek alkalmassági értékeinek összege. Ezután generálunk annyi véletlen számot a [0, alkalmassági-összeg] tartományban, ahány egyed van a populációban. Amelyik egyedhez tartozó körcikkbe a generált szám beleesik, azt az egyedet kiválasztjuk. Így a nagyobb alkalmassági érték˝u egyedek nagyobb valószín˝uséggel kerülnek kiválasztásra, többször is kiválasztódhatnak (azaz többször szerepelhetnek majd szül˝oként), míg a kis alkalmassági értékkel rendelkez˝ok ritkábban vagy egyszer sem. Ennél az eljárásnál van egy hatékonyabb, általánosan használt módszer, a sztochasztikus univerzális kiválasztás („stochastic universal sampling”). Itt nem cseréljük le az összes egyedet a populációban, hanem csak az egyedek bizonyos hányadát. A populációnak csak egy részét jelöljük ki utódok létrehozására. A szül˝ok számát tehát úgy határozzuk meg, hogy a populáció méretét megszorozzuk egy 0 és 1 közötti számmal. Az alkalmas egyedek többször is lehetnek szül˝ok, éppúgy, mint az el˝oz˝o módszer esetén. A kihalók száma – vagyis akiknek a helyére az utódokat tesszük majd – megegyezik a szül˝ok számával. A kiválasztás a rulett kerék módszerhez hasonlóan történik, de most csak egy véletlenszám generálásával a [0, összalkalmassági/szül˝ok száma] intervallumban. Ehhez a számhoz adjuk hozzá az összalkalmassági/szül˝ok száma érték többszöröseit. Amelyik körcikkbe mutat az aktuális szám, az ahhoz tartozó egyedet kiválasztjuk. A 2.10. ábrán például egy 20 egyedb˝ol álló populáció látható egy kiterített rulett keréken. A szül˝ok aránya legyen 0,3, azaz 6 egyed kerül kiválasztásra. A kiválasztott egyedek a 2.10. ábrán: a 2., 5., 9., 11., 14., és a 18. egyed. 2.2.1.5. Keresztezés A kiválasztott egyedeket párokba rendezzük, és a párok (szül˝ok) között végrehajtjuk a keresztezést (crossover). Ez a m˝uvelet valósítja meg a két szül˝o „genetikus anyagának” a keverését. Egypontos keresztezés esetén generálunk egy egyenletes eloszlású i véletlenszámot a kromoszóma hosszának intervallumában. A két egyed között kicseréljük az információt az i indext˝ol balra és jobbra, így két új egyed, utód keletkezik (2.11. ábra). Többpontos keresz22

2.10. ábra. A szelekció m˝uvelete

2.11. ábra. A keresztezés operáció (bináris példa)

tezés esetén több véletlenszer˝u keresztezési pontot választunk, és felváltva cseréljük ki a két egyednél az információt a keresztezési pontok között. Ez azonban az egypontos keresztezés többszöri alkalmazásával ekvivalens, így nem jelent lényegi változást. Lehetséges uniform keresztezés használata is, melynek során a kromoszóma minden egyes génjénél véletlenszer˝uen döntünk, hogy melyik szül˝o bitjét kapja az els˝o utód és melyiket a második. Valós kódolású genetikus algoritmusok esetén is többféle keresztezési módszer közül választhatunk. Az egyik lehetséges változatot mutatja a 2.12. ábra. 2.2.1.6. Mutáció Az egyed génkészletének véletlenszer˝u megváltozása a mutáció. Az algoritmusban ez a kromoszóma egy véletlenszer˝uen kiválasztott bitjének vagy bitcsoportjának megváltoztatását jelenti (2.13. ábra). Valós kódolású esetben a kiválasztott gén értékét változtatjuk meg a lehetséges intervallumából új értéket véve. A mutáció meghatározó paramétere a mutációs arány, amely azt adja meg, hogy az egyed mekkora eséllyel vesz részt a mutációban. 2.2.1.7. Visszahelyettesítés Az egyszer˝u rulett kerék módszerrel történ˝o kiválasztási algoritmus esetén a populáció összes egyedét lecseréljük. Ilyenkor tehát a következ˝o generációt csupa új egyed fogja alkotni, melyeket a szelektálás utáni keresztezés és mutáció operátorokkal kapunk meg. Sztochasztikus univerzális kiválasztás esetén viszont a populációnak csak valamekkora hányadát 23

2.12. ábra. A keresztezés operáció (valós példa)

2.13. ábra. A mutáció m˝uvelete

választottuk ki (2.10. ábra). Ahhoz, hogy a populáció mérete ne változzon, szükséges, hogy meghatározzuk azon egyedeket, amelyeket megsemmisítünk, vagyis azokat, melyek helyére az új egyedeket tesszük. A kihaló egyedeket hasonlóan választhatjuk ki, mint ahogy a szelekciónál a szül˝o egyedeket, viszont a kihalók esetében olyan rulett kereket definiálunk, ahol az egyes egyedek a jósági értékükkel fordítottan arányos méret˝u körcikket kapnak. A többi egyedet, amelyek nem vettek részt új egyedek létrehozásában és ki sem haltak, változatlanul hagyjuk a populációban, azaz a következ˝o generációban is benne lesznek. 2.2.1.8. Migráció Több populációs esetben a populáció alpopulációkból áll. Az egyes alpopulációk a fent leírt algoritmussal kezelhet˝oek. Lehet˝oség van azonban egyedek vándorlására a populációk között. Ezt nevezzük migrációnak, mellyel kapcsolatban szükséges annak a megadása, hogy az egyedek hány százaléka vesz részt benne, milyen alapon kerülnek kiválasztásra az egyes egyedek, és hogy milyen topológia szerint játszódik le [87].

2.2.2. Genetikus programozás A genetikus programozás ötletét J. Koza javasolta el˝oször 1992-ben [66]. A módszer a genetikus algoritmus alapötletét használja fel egy adott feladat megoldására alkalmas számítógépes programok terében való keresésre. Számos különböz˝onek t˝un˝o, különböz˝o területr˝ol vett problémát át lehet fogalmazni olyan feladattá, amely a problémát megoldó optimális programot keresi. A genetikus algoritmusokhoz képest az az alapvet˝o különbség, hogy az egyedek itt nem egyetlen stringbe vannak bekódolva, hanem kifejezésfával adottak. A 2.14. 24

2.14. ábra. Példa program és a hozzátartozó kifejezésfa

ábrán egy program és a kifejezésfája látható. A fát kétféle csomópontok alkotják, a terminális csomópontok, melyek a fa leveleiben helyezkednek el és a függvény csomópontok, amelyek a fa többi részét alkotják. A módszer alkalmazása esetén a következ˝o el˝okészít˝o lépések szükségesek. Definiáljuk a terminálisok halmazát, mely a lehetséges terminális szimbólumokat tartalmazza, valamint a függvények halmazát a függvényekkel. Meghatározzuk az alkalmassági érték számítási módját, és beállítjuk a következ˝o paramétereket: az egyedek számát, a szül˝ok arányát (vagyis azt, hogy a teljes populáció mekkora része vesz részt utódok létrehozásában), a mutációs arányt, a maximális generációszámot, illetve ehelyett a leállási feltételt. Ezután következik az evolúciós folyamat végrehajtása, amelynek során a cél az optimális kifejezésfa megtalálása. A populációt alkotó fák különböz˝o méret˝uek és alakúak lehetnek. Az els˝o generációt véletlenszer˝uen létrehozott, de szintaktikailag érvényes fák alkotják. 2.2.2.1. Keresztezés A keresztezés során el˝oször mindkét szül˝o fájában kiválasztunk egy véletlenszer˝u csomópontot. Ezután kicseréljük a csomópontokhoz tartozó részfát a két szül˝oben és így két utódot nyerünk. A következ˝o lépésben ellen˝orizzük, hogy a kapott utódok szintaktikailag érvényesek-e, hiszen el˝ofordulhat, hogy a létrejött utód olyan fát reprezentál, amelyik az adott feladat szempontjából értelmezhetetlen. Ebben az esetben a szül˝okben más csomópontokat választunk a keresztezéshez, és ezt addig ismételjük, míg olyan utódokat nem kapunk, amelyek szintaktikailag érvényesek. A 2.15. ábrán egy példán követhetjük nyomon a keresztezés folyamatát. A {+, −, ×, /} jelek, m˝uveletek alkotják a lehetséges függvények halmazát, az {x, y, 1, 2} elemek pedig a terminálisokat. A keresztezési csomópont a baloldali szül˝o esetén a „−” függvény, a jobboldali szül˝o esetén pedig a baloldali „x”. Ezeket cseréljük ki, így kapjuk meg az alsó két ábrán látható utódokat.

25

2.15. ábra. A keresztezés operáció

2.2.2.2. Mutáció A mutációban résztvev˝o egyeden véletlenszer˝uen kiválasztunk egy csomópontot. Töröljük a csomópont alatt lév˝o részfát, és egy újat növesztünk helyette. A szintaktikai érvényességre itt is ügyelünk. A 2.16. ábrán egy példán láthatjuk a mutációt, a terminálisok és a függvények halmaza ugyanaz, mint a keresztezéses példában. A „2”-es érték˝u terminális csomópontot választottuk, melynek helyére egy új részfa került.

2.16. ábra. A mutáció m˝uvelete

26

2.2.3. Bakteriális evolúciós algoritmusok A természet sok ötletet ad különböz˝o evolúciós módszerek alkotására a hagyományos genetikus algoritmus mintájára. Az egyik legújabb ilyen módszer a 1990-es évek második felében kifejlesztett bakteriális evolúciós algoritmus. Ez az eljárás a baktériumok evolúciós jelenségén alapul, a módszert a baktériumok génátadási jelensége inspirálta. El˝oször a pszeudo-bakteriális genetikus algoritmust publikálták [83], mely a genetikus algoritmusokban alkalmazott mutáció helyett az úgynevezett bakteriális mutációt alkalmazza. Kés˝obb megjelent a bakteriális evolúciós algoritmus [82], mely a bakteriális mutáción kívül a génátadási (géntranszfer) operációt is magába foglalja. Az algoritmus folyamata a következ˝o: kezdeti populáció létrehozása generáció=0 amíg generáció < max. generáció { bakteriális mutáció alkalmazása minden egyedre génátadás generáció = generáció + 1 } A genetikus algoritmusokban megismert szelekcióra nincs szükség, és az operátorok is eltér˝oek. Az egyedek kromoszómába vannak kódolva, valós számokkal. A kezdeti populáció kialakítása a genetikus algoritmusokhoz hasonlóan történik, a keresési térb˝ol Negyed pont véletlenszer˝u kiválasztásával. Ezután következik az evolúciós ciklus, melyben a bakteriális mutációt minden egyedre alkalmazzuk, a génátadást pedig a populáción hajtjuk végre. 2.2.3.1. Bakteriális mutáció A bakteriális mutáció egy egyeden végrehajtott operátor, melyet azonban minden egyedre végrehajtunk. Az eljárás elején az egyedet lemásoljuk Nkl´on példányban (klónok). A kromoszóma egy véletlenszer˝uen kiválasztott i. részét megváltoztatjuk a klónokban (mutáció), az eredeti baktériumban viszont nem. Utána kiválasztjuk a legjobb egyedet a klónok és az eredeti egyed közül, és az a kromoszómájának az i. részét átadja a többi egyednek. Ez azt jelenti, hogy a többi egyed kromoszómájának i. részét helyettesítjük a legjobb egyed kromoszómájának i. részével. Ezt a folyamatot, mely a mutáció – kiértékelés – kiválasztás – behelyettesítés lépéssorozatot jelenti, ismételjük addig, amíg a kromoszómának mindegyik részét egyszer ki nem választottuk. Amikor az egész kromoszómával végeztünk, kiválasztjuk a legjobb egyedet, a többi Nkl´on egyedet pedig megszüntetjük. A folyamat végén tehát az eredeti egyednél jobb, vagy legrosszabb esetben, sikertelen mutációs ciklusok esetén, azzal megegyez˝o egyedet kaptunk. A bakteriális mutáció a teljes algoritmussal együtt a 2.17. ábrán látható. 2.2.3.2. Génátadás A génátadási (géntranszfer) operátor segítségével valósul meg az információcsere az egyes egyedek között a baktériumpopulációban. A bakteriális mutáció az egyes baktériumokat külön-külön optimalizálja, szükség van azonban az egyedek közötti információátadásra, 27

2.17. ábra. Bakteriális evolúciós algoritmus

a genetikai információ terjesztésére a populációban. Els˝o lépésben a populációt két részre osztjuk, az egyik felébe kerülnek a jó egyedek, a másikba pedig a rosszak. Nincs szükség a hagyományos értelemben vett alkalmassági érték számításra, elég ha a baktériumokat kiértékeljük az adott feladatban alkalmazott kiértékelési kritérium szerint. Így a baktériumok összehasonlíthatók, a két fél populáció könnyen létrehozható. Második lépésben kiválasztunk egy baktériumot a jó egyedek közül, ez lesz a forrásbaktérium, egyet pedig a rossz egyedek közül, ez lesz a célbaktérium. A harmadik lépésben kiválasztunk egy részt a forrásbaktérium kromoszómájából, és átadjuk a célbaktériumnak. A célbaktérium ezzel felülírhatja a kromoszómájának egy részét, vagy egyszer˝uen hozzáadhatja a kromoszómájához, ha különböz˝o hosszúságú egyedeket is megengedünk. Ezt a három lépésb˝ol álló eljárást ismételjük Ninf -szer, ahol Ninf egy paramétere az algoritmusnak, és az „infekciók” számát jelöli. A génátadás illusztrációja a 2.18. ábrán látható. 2.2.3.3. Összehasonlítás, paraméterek A bakteriális evolúciós algoritmusokban a korábban megismert szelekció, keresztezés, és mutáció operátorokat a génátadás, bakteriális mutáció és osztódás váltja fel. A módszert a baktériumpopulációk génátadási jelensége (transzdukció) inspirálta. Ennek segítségével egy baktérium gyorsan szét tudja terjeszteni a genetikus információt. Az egyik jelenség, amikor egy baktérium a kromoszómájának egy részét átadja a saját klónjainak (ez történik a bakteriális mutációnál a legjobb egyeddel), a másik pedig, amikor egy populációban az 28

2.18. ábra. A génátadás m˝uvelete

egyik baktérium egy másiknak ad át genetikus információt (génátadás). Ez utóbbi m˝uvelet helyettesíti a hagyományos genetikus algoritmus keresztezés operátorát, megengedve az információ átadását különböz˝o egyedek között, még jobb egyedeket létrehozva ezáltal. Az algoritmusnak 4 paramétere van: a baktériumok száma (Negyed ), a generációk száma (Ngen ) a klónok száma (Nkl´on ), és az infekciók száma (Ninf ). A maximális generációk száma helyett ennél a módszernél is használható más leállási feltétel. A bakteriális megközelítés a benne alkalmazott operátorok természete miatt a genetikus algoritmusoknál kedvez˝obb konvergencia viselkedéssel rendelkezik. Kevesebb generáció elegend˝o a kvázioptimális megoldás eléréséhez. Ezenkívül a bakteriális mutációban alkalmazott klónok miatt elegend˝o kevesebb egyedet alkalmazni a populációban.

2.2.4. Fuzzy szabályoptimalizálás bakteriális evolúciós algoritmussal Az el˝oz˝o részben megismert bakteriális evolúciós algoritmust a módszert javasló japán kutatók fuzzy szabálybázis optimalizálására alkalmazták [82]. A cél olyan háromszög alakú tagsági függvényekb˝ol felépül˝o szabálybázis meghatározása volt, amely egy adott mintakészletre valamilyen hibakritérium alapján a lehet˝o legjobban illeszkedik. A Nawa és Furuhashi által vizsgált fuzzy szabálybázis er˝osen lesz˝ukített típusú. A tagsági függvények egyenl˝o szárú háromszögekkel adottak, ily módon minden tagsági függvényt két paraméter jellemez: a magpont (a háromszög csúcsa) és a tartó hossza (a háromszög alapja). Az egyes szabályok szabálybázisbeli sorrendjük szerint szerepelnek a baktériumban, szabályonként a dimenziók indexének sorrendjében, legvégül a kimeneti dimenzió tagsági függvényével. Minden egyes baktérium egy ilyen sz˝ukített típusú szabálybázis kódját tartalmazza. Például a 2.19. ábrán szerepl˝o baktériumhoz tartozó 3. szabály: 29

2.19. ábra. A kódolási elrendezés

R3 : Ha x1 = T (4,8; 1,6) és x2 = T (8,3; 0,7) akkor y = T (2,2; 1,3), ahol T (C, L) olyan szimmetrikus háromszög alakú tagsági függvényt jelöl, melynek C a magpontja, L pedig a háromszög alapjának hossza. A kódolási elrendezésen kívül az egyedek kiértékelési módját is meg kell adni. Ez azt mutatja meg, hogy az egyednek megfelel˝o szabálybázis mennyire illeszkedik jól a tanító mintakészletre. A hivatkozott cikkben [82] az átlagos relatív hibán alapuló kritériumot alkalmazták: m 1 X |ti − yi | E= , m i=1 ti ahol ti az i. mintára vonatkozó megkívánt kimenet, yi az i. mintára számított modell kimenet, és m a minták száma. A kezdeti populáció kialakítása véletlenszer˝uen létrehozott szabályokat jelent az egyes baktériumokban. A bakteriális mutációs és génátadási operátorokban szükség van a „kromoszóma” egy egységnyi részletének kiválasztására. A kromoszóma egy egységnyi részlete ebben az esetben egyetlen szabályt jelent. A bakteriális mutáció esetén tehát a klónokban egy véletlenszer˝uen kiválasztott szabály paraméterei módosulnak. A génátadás m˝uvelete során a célbaktérium egy egységnyi részletet, azaz egyetlen szabályt kap a forrásbaktériumtól.

30

2.2.5. Egyéb módszerek Az el˝obbiekben említett módszereken kívül sok egyéb evolúciós és él˝olényeket, él˝olénypopulációk viselkedését utánzó módszert fejlesztettek ki. Már a téma korai id˝oszakában megjelentek a J. Holland-féle módszernek alternatívái, az evolúciós programozás [37], és az evolúciós stratégiák [5, 89]. Kés˝obb javasolták még például a többkritériumú genetikus algoritmusokat [38, 39], a többpopulációs genetikus algoritmust [87, 107], az ún. hangyakolóniákat [29, 30], a vírus alapú evolúciós algoritmust [68], a „ragadozó-zsákmány” módszert [3], a méhkirályn˝o evolúciós algoritmust [51], a mesterséges immunrendszereket [27, 44], és a részecske-sereg optimalizációt [33, 52]. Az értekezésben fontos szerepe lesz még a memetikus algoritmusoknak [80]. Ezek az evolúciós módszereket kombinálják lokális széls˝oértékkeres˝o eljárásokkal. Ezek az algoritmusok az evolúciós technikák kvázi-optimumkeresését és lassú konvergencia tulajdonságait küszöbölik ki, gyorsabb konvergenciát és pontosabb optimum megtalálását teszik lehet˝ové.

2.3. Neurális hálózatok A számítási intelligencia harmadik fontos csoportját a neurális hálózatok alkotják, melyek az agyban található neuronok hálózatában végbemen˝o folyamatok utánzását megvalósító számítási rendszerek. Számos probléma létezik, melyet nem tudunk megoldani hagyományos algoritmusokkal, de az ember könnyedén megoldja o˝ ket. Az agy tevékenységeinek megfigyelésével utánozhatjuk annak m˝uködését, és ezek alapján számítási rendszereket hozhatunk létre. A mesterséges neurális hálózat tehát az evolúciós technikákhoz hasonlóan a biológiából ellesett módszer. A neurális hálózat elemi egységekb˝ol, neuronokból áll, melyek valamilyen lokális feldolgozást hajtanak végre. Ezek a neuronok valamilyen topológia szerint vannak összekapcsolva egy hálózattá. A neurális hálózat minták alapján képes tanulni, a megtanult tudás a neuronok közötti összeköttetésekben, úgynevezett súlyokban tárolódik. A minták alapján végbemen˝o tanulás alternatívát jelent a fuzzy rendszerek esetén alkalmazott szabályokra, a neurális hálózatok és a fuzzy rendszerek jól kiegészítik egymást. Ebben az alfejezetben a neurális hálózatok alapjait tekintem át, de csak el˝orecsatolt típusú hálózatokkal foglalkozom. Bár ezenkívül számos más típusú hálózat ismert az irodalomban, azok tárgyalásától eltekintek egyrészt terjedelmi okok miatt, másrészt pedig azért, mert az értekezésben csak el˝orecsatolt hálózatokkal, azoknak is csak bizonyos típusával foglalkozom. A következ˝okben röviden bemutatom a két legelterjedtebb neurális hálózattípust, az MLP és az RBF hálózatokat, majd kicsit részletesebben ismertetem az értekezésben alkalmazott típust, a B-spline neurális hálózatokat. A hálózatok bemutatása után a tanuló algoritmusokat tárgyalom. A klasszikus backpropagation módszer ismertetése után bemutatom az értekezésben kulcsszerepet játszó Levenberg-Marquardt tanuló algoritmust. Bár ez a hagyományos másodfokú gradiens alapú optimalizálási módszerek közé tartozik, célszer˝u itt tárgyalni sikeres neurális hálózatokkal kapcsolatos alkalmazása miatt [91].

31

2.20. ábra. Többréteg˝u perceptron (MLP)

2.3.1. Többrétegu˝ perceptron Annak ellenére, hogy a neurális hálózatoknak számos fajtája ismert, az egyik leggyakrabban használt típus a többréteg˝u perceptron (Multi-layer perceptron, MLP). Az MLP egy el˝orecsatolt hálózat, mely számos egységet (neuront) tartalmaz, melyek súlyozott összeköttetésekkel kapcsolódnak egymáshoz. A neuronok rétegekbe vannak rendezve, egy rétegbe a hasonló kapcsolatokkal rendelkez˝o neuronok tartoznak. Háromféle réteget különböztetünk meg, a bemeneti, rejtett és kimeneti réteget. A bemeneti réteg a kívülr˝ol érkez˝o bemeneti vektort fogadja, és adja át a súlyozott kapcsolatokon keresztül az els˝o rejtett rétegnek. Az itt található neuronok feldolgozzák a kapott értékeket, majd a következ˝o rétegnek továbbítják. Több rejtett réteg is el˝ofordulhat a hálózatban. Végül a kimeneti rétegen keresztül az információ a környezet felé továbbítódik. Egy egy rejtett réteget tartalmazó MLP látható a 2.20. ábrán. Távolabbról nézve tulajdonképpen egy tetsz˝oleges bemeneti vektort terjesztünk el˝orefelé a hálózaton, mely a kimeneti rétegen valamilyen aktiválást okoz. A teljes hálózati függvény, ami a bemeneti vektort a kimeneti vektorba képzi, a hálóban található súlyokkal határozható meg. A hálóban lév˝o minden neuron egy egyszer˝u processzáló elem, ami kiszámítja saját kimenetét a gerjesztésének alapján. Az l. réteg i. neuronjának bemenete (2.21. ábra): X (l−1) (l−1) (l) (l−1) si = yj wji + bi , j∈pred(i)

ahol pred(i) az i. egységet megel˝oz˝o neuronok halmaza, azaz azon neuronoké, ahonnan összeköttetés érkezik a vizsgált i. neuronba; wji a j. és az i. egység közötti összeköttetés súlyának az értéke. A bi konstanst a neuron „torzítási (bias)” értékének nevezzük (amely egy járulékos, egység kimenet˝u neuron minden rétegben, és szerepe, hogy a hálózat akkor is pro32

2.21. ábra. Egy neuron bemenetei és kimenete

dukáljon kimenetet, ha nincs gerjesztés). A homogén reprezentáció kedvéért ezt az értéket gyakran egy konstans 1-es kimenet˝u bias-egységb˝ol induló súllyal veszik figyelembe. Ez azt jelenti, hogy a bias értékek súlyként kezelhet˝ok. A 2.20. ábrán b bet˝ukkel vannak jelölve a bias egységek, melyek minden processzáló neuronhoz kapcsolódnak valamekkora súllyal. (l) Az i. egység kimenetét úgy határozzuk meg, hogy az el˝obb számított si ered˝o bemenetet egy nemlineáris aktiváló vagy más néven gerjesztési függvénynek vetjük alá. Általában a szigmoid függvényt alkalmazzák, mely alapján a neuron kimenete a következ˝oképpen határozható meg: 1 (l) . yi = (l) 1 + e−si Egy érdekes tulajdonsága ennek a függvénynek, hogy a deriváltja könnyen számítható: ∂yi = yi (1 − yi ). ∂si A hálózat els˝o rétegében minden egyes neuron a maga szigmoid függvényével, súlytényez˝oivel és eltolásával az n dimenziós teret egy n − 1 dimenziós hipersíkkal egyértelm˝uen két térfélre képes osztani. A következ˝o réteg neuronjai e hipersíkokból konstruálhatnak konvex tartományokat, a rákövetkez˝o réteg neuronjai e konvex tartományokból gyárthatnak konkáv tartományokat, végül az utolsó réteg súlyai e tartományokon való leképezések értékeit állíthatják be, így az értelmesen felhasználható rétegek száma elméletileg véges, és az MLP méretezésének problémája többnyire a rétegekben alkalmazandó neuronok számától függ. Minták alapján beállíthatjuk a súlyokat valamilyen tanuló algoritmussal, hogy a hálózat a kívánt leképezést valósítsa meg. A tanuló algoritmusokat a fejezet kés˝obbi részében ismertetem.

2.3.2. Radiális bázisfüggvény hálózatok A neurális hálózatok másik elterjedt fajtája a radiális bázisfüggvény (Radial Basis Function, RBF) hálózat, melynek felépítését a 2.22. ábrán láthatjuk. A bemenet utáni els˝o rétegbeli neuronok aktiváló függvényei, az ábrán gi (u)-val jelölt függvények körszimmetrikusak. 33

2.22. ábra. Radiális bázisfüggvény hálózat (RBF)

Aktiváló függvényként leggyakrabban a Gauss-függvényeket alkalmazzák, melyek a következ˝o alakban írhatók fel: 2 −

gi (u) = e

ku−ci k 2σ 2 i

.

A ci érték az i. függvény középpontját adja meg, mely egy paramétere a függvénynek, a σi érték pedig az i. függvény szélességparamétere. A hálózat kimenete az egyes Gaussfüggvények súlyokkal történ˝o lineáris kombinációjával számítható: y=

n X

wi gi (u).

i=1

A paramétereket tanítással állítjuk be. A hálózat m˝uködését azzal a szemléletes hasonlattal képzelhetjük el, hogy az általában „nem különösebben sima” módon közelíthet egy nagyobb, sima felületet ugyanúgy, mintha egy sík területet valami ponyvával szeretnénk lefedni oly módon, hogy azt néhány sátorbottal néhány diszkrét pontban kitámasztjuk. A botok magassága felel meg a függvény adott környéken való közelít˝o értékének, a bázisfüggvények szélessége a ponyva lehajlási szélességének. Bár ezeknek a Gauss-függvényeknek a súlyozott összeg˝u kimenete „matematikai értelemben” ugyan „sima”, azaz akárhányszor deriválható, az elvégzend˝o függvényközelítést illet˝oen gyakorlatilag azonban nem az, túlságosan „fodros”. E fodrosság elkerülhet˝o, ha Gauss-függvények helyett egymáshoz simán illeszthet˝o szakaszokból álló, a következ˝o alfejezetben ismertetend˝o B-spline függvényeket alkalmazunk nagyjából egyenletesen elosztott csomópontokkal teljesen hasonló módon. Az MLP és RBF hálózatokról és egyéb neurális hálózatokról további részletek találhatók pl. a [46, 108] könyvekben. 34

2.23. ábra. B-spline neurális hálózat

2.3.3. B-spline neurális hálózatok Az értekezés kés˝obbi részében csak a B-spline típusú neurális hálózattal fogunk találkozni. Ezek számos el˝onyös tulajdonságot mutatnak az MLP és az RBF típusú hálózatokhoz képest. Az információt lokálisan tárolják, ami azt eredményezi, hogy a bemeneti tér egy bizonyos részén végrehajtott tanítás a tér többi részét csak kismértékben érinti. Emiatt jól használhatók on-line adaptív modellezési és irányítási alkalmazásokban [104]. A rács-alapú felépítésük transzparenssé teszi o˝ ket, így más típusú hálózatokkal ellentétben a tárolt tudásuk könnyebben megérthet˝o [21]. Sokdimenziós problémákra jobb az általánosító képességük mint néhány RBF hálózatnak [8]. A B-spline neurális hálózatok a rács-alapú asszociatív memória hálózatok (AMN) osztályába tartoznak. Ezek a hálózatok három réteget tartalmaznak: a normalizált bemeneti tér réteget, a bázisfüggvények rétegét és a súlyvektor réteget. A hálózat felépítése a 2.23. ábrán látható. 2.3.3.1. Normalizált bemeneti tér réteg Ez a réteg egy rácsozat, amelyen a bázisfüggvényeket definiáljuk. Ahhoz, hogy egy rácsot definiáljunk a bemeneti téren, minden egyes tengelyhez csomópontok egy vektorát kell meghatározni. Általában minden dimenzióban más és más a csomópontok száma, és másmás pozíciókban is helyezkednek el. Jelöljük az i. tengely bels˝o csomópontjait λi,j , j = 1, · · · , ri -vel melyekre érvényes, hogy xmin < λi,1 ≤ λi,2 ≤ · · · ≤ λi,ri < xmax , ahol xmin és xmax az i. bemenet minimum i i i i ill. maximum értéke. Minden tengely szélén szükséges küls˝o csomópontokat is definiálni, melyekre teljesül, hogy λi,−(ki −1) ≤ · · · ≤ λi,0 = xmin és xmax = λi,ri +1 ≤ · · · ≤ λi,ri +ki . i i Ezek a küls˝o csomópontok azért szükségesek, hogy azokat a bázisfüggvényeket is definiálni tudjuk, amelyek közel vannak a határokhoz. A küls˝o csomópontok általában a bemeneti tengely szélével egybeesnek, vagy az adott tengely szélén kívül egymástól egyenl˝o távol35

max max ] , ezért a ] × · · · × [xmin ságra helyezkednek el. A hálózat bemeneti tere [xmin n , xn 1 , x1 küls˝o csomópontok csak a bázisfüggvények definiálása céljából szükségesek. Az i. bemenet j. intervallumát Ii,j -vel jelöljük: ( [λi,j−1 λi,j ) ha j = 1, . . . , ri Ii,j = [λi,j−1 λi,j ] ha j = ri + 1.

Az i. tengelyen ri + 1 intervallum van (melyek között lehetnek üresek, ha bizonyos csomóQ pontok egybeesnek), azaz összesen p0 = ni=1 (ri + 1) n-dimenziós cella van a rácsozaton. 2.3.3.2. A bázisfüggvények rétege A bázisfüggvények rétege p darab B-spline bázisfüggvényt tartalmaz, amelyeket az ndimenziós rácsozaton értelmezünk. A B-spline függvények könnyen állíthatók, számíthatók és implementálhatók. A bázisfüggvények alakja, mérete és eloszlása az adott AMN-re jellemz˝o, és a bázisfüggvények tartója behatárolt. A B-spline neurális hálózatokban a spline rendje automatikusan meghatározza a függvény tartóját és alakját. A k rend˝u egyváltozós B-spline bázisfüggvény tartója k intervallum széles. Ezért minden bemenet k darab bázisfüggvényt aktivál. A j. egyváltozós k rend˝u bázisfüggvényt Nkj (x)-vel jelöljük, és a következ˝oképpen adhatjuk meg:     x − λj−k λj − x j j−1 j Nk (x) = Nk−1 (x) + Nk−1 (x) λj−1 − λj−k λj − λj−k+1 ( 1, ha x ∈ Ij N1j (x) = 0, egyébként. Többváltozós az egyváltozósak tenzor szorzatával nyerünk, azaz: Qn bázisfüggvényeket j j Nk (x) = i=1 Nki ,i (xi ) (ld. 2.24. ábra). A ki rend˝u bázisfüggvények száma az Qi. tengelyen ri bels˝o csomópont esetén ri +ki . Ezért a többváltozós B-spline-ok száma p = ni=1 (ri +ki ). Ez a szám exponenciálisan függ a bemenet méretét˝ol, ezért a B-spline-ok csak alacsony dimenziószámú problémákra használhatók. 2.3.3.3. A súlyvektor réteg A hálózat kimenete a bázisfüggvények kimeneteinek lineáris kombinációja. A kombiPp nációs tagok az állítható súlyparaméterek: y = i=1 ai wi = aT w, ahol ai = Nki (x), i = Q 1, . . . , p. Mivel csak p00 = ni=1 ki cella aktív egyszerre, ezért a kimenet számítása a köP 00 vetkez˝o formára egyszer˝usödik: y = pi=1 aact(i) (x)wact(i) , ahol aact(i) (x) jelöli az i. aktív bázisfüggvényt x bemeneti vektor esetén. 2.3.3.4. Almodulok A magas dimenziójú esetekben keletkez˝o problémák leküzdésére a nagy-dimenzió számú modell helyett, amely az összes bemeneti változót tartalmazza, kisebb dimenzió számú almodellek segítségével próbáljuk adott feladatot megoldani. Egy ilyen módon összeálPaz nu lított hálózat kimenete: y(x) = u=1 Su (xu ), ahol Si (xi ) jelöli az i. almodellt, és xi azon bemeneti változók halmaza, amelyek az i. almodellt alkotják. 36

2.24. ábra. Kétváltozós B-spline függvény

2.3.3.5. B-spline neurális hálózatok tervezése A B-spline hálózatok tervezése az alábbi fázisokat foglalja magába: 1. Az almodellek meghatározása 2. Mindegyik almodellre annak bemeneteinek meghatározása 3. A spline-ok rendjének meghatározása minden bemenetre 4. A bels˝o csomópontok számának meghatározása mindegyik bemenetre 5. A bels˝o csomópontok helyének meghatározása mindegyik bemenetre 6. A súlyok meghatározása Az utolsó két fázis a kés˝obb részletezend˝o tanuló algoritmusokkal megoldható [21, 91]. Az els˝o négy tervezési fázis összetettebb probléma, melynek megoldására más módszereket fogunk alkalmazni.

2.3.4. Más típusú neurális hálózatok Az el˝orecsatolt neurális hálózatokon kívül számos más típusú hálózat is elterjedt az alkalmazásokban. Fontos kategóriát alkotnak a visszacsatolt hálózatok, melynek egyik fontos típusa az Elman-hálózat [34]. Az Elman-hálózatban el˝oforduló bels˝o visszacsatolások nemcsak arra alkalmasak, hogy valamiféle „dinamikát” vigyenek be a hálózat által megvalósított leképezésbe, ami pl. bels˝oégés˝u motorok modellezésére kiváltképp alkalmassá tette ezt a 37

hálózat-típust, hanem a legújabb kutatások szerint arra is, hogy azok az így keletkez˝o „memória” révén mintegy megsz˝urjék, megsimítsák a bemeneti tanító adatokat, így a közönséges MLP-nél általában jobbak (pontosabbak) függvénymodellezési célokra, pl. id˝ot˝ol függ˝o adatsorok analízisében is.

2.3.5. Backpropagation eljárás A neurális hálózat paramétereit, azaz a súlyokat úgy szeretnénk beállítani, hogy a hálózat megvalósítsa a bemenet és kimenet közötti kívánt leképezést. Ezt a súlybeállítási folyamatot nevezzük a hálózat „tanításának”. A tanításhoz szükséges leképezés minták formájában adott. A mintakészlet minden egyes mintája egy-egy bemenet-kimenet párt határoz meg, amelyek a hálózat válaszát írják le az adott bemeneti gerjesztésre. A tanítás célja ennek megfelel˝oen az, hogy a hálózat súlyait úgy állítsuk be, hogy a hálózat minden egyes minta bemenetre olyan kimenetet adjon, mint a mintához tartozó kívánt kimenet, minél kisebb legyen a hálózat által számított kimenet és a kívánt kimenet közötti eltérés. A hálózat által meghatározott kimenet és a kívánt kimenet közötti eltérés matematikailag a következ˝o formában írható fel: m k 1 X X (p) 2 (y − t(p) E= n ) . 2 p=1 n=1 n (p)

Ebben a hibadefinícióban yn jelöli a hálózat által a p. mintára számított kimenet n. kom(p) ponensét, tn a p. mintához tartozó megkívánt kimenet n. komponensét, k a kimenet dimenziószáma, (azaz a neuronok száma a kimeneti rétegben), m pedig a minták száma. Egy neuront tartalmazó kimeneti réteg esetén a hiba vektoros formában a következ˝oképpen írható fel egyszer˝ubb formában: ky − tk2 E= . 2 Itt y az m-dimenziós kimeneti vektor, azaz a hálózat kimeneteinek összessége az m mintára, t az m-dimenziós megkívánt kimeneti vektor, k · k az euklideszi norma. Ez a kifejezés a hibák négyzetösszege (Sum of Square Errors, SSE). A tanítás célja ennek alapján az E (kvázi-)minimumának a megkeresése. A legkorábbi tanuló eljárás az úgynevezett backpropagation algoritmus [92, 100], amely egy legmeredekebb lejt˝o típusú módszer. Az algoritmus a hiba deriváltjait felhasználva iteratívan állítja be a hálózat súlyait, a deriváltak alapján a súlyokat az optimum felé terelve. A súlyokat w-vel jelölve, az algoritmus minden iterációja a következ˝o általános alakba írható: w[k + 1] = w[k] − ηg[k], ahol k ill. k + 1 a lépésszám azonosítói, η a tanítás paramétere g a hiba gradiens vektora: g[k] =

∂E(w[k]) . ∂wT [k]

A gradiens meghatározása után a súlyok új értéke számítható. Ezt azt iteratív lépést ismételjük amíg az E hiba megfelel˝oen kicsi nem lesz. 38

2.3.6. Levenberg-Marquardt algoritmus A backpropagation algoritmus els˝orend˝u gradiens típusú módszer, mely a hiba els˝orend˝u deriváltjait használja. A gyakorlati feladatoknál nem garantált a konvergencia, de ha van is általában lassú. Emiatt a probléma miatt kés˝obb más tanuló algoritmusok is megjelentek a közleményekben, ezekkel hatékonyabban lehet a neurális hálózatokat tanítani [90, 91]. Az egyik leghatékonyabb módszer a Levenberg-Marquardt eljárás, melyet eredetileg Levenberg [72] és Marquardt [79] nemlineáris paraméterek legkisebb négyzetes becslésére javasolt. A módszer kiválóan alkalmazható neurális hálózat súlyainak beállítására és egyéb optimalizációs problémákra. Az algoritmus minden lépésében szükséges a Jacobi-mátrix kiszámítása, mely a hálózat különböz˝o mintákra számított kimenetének súlyok szerinti parciális deriváltjait tartalmazza: J=

∂y(xp ) . ∂wT

A súlyok értékének w[k + 1] = w[k] + s[k] módon történ˝o meghatározásához az s[k] vektort a következ˝o egyenlet megoldása adja: (JT [k]J[k] + αI)s[k] = −JT [k]e[k],

(2.3)

ahol e[k] a k. lépésben vett hibavektor, azaz e[k] = y[k] − t[k]. A 2.3. összefüggésben α regularizációs paraméter, amely egyaránt szabályozza a keresés irányát és a módosítás nagyságát. A keresési irány a Gauss-Newton és a legmeredekebb irány között α értékét˝ol függ˝oen változik. Ha α → 0, akkor az algoritmus a Gauss-Newton módszerhez konvergál, ha α → ∞, akkor pedig a legmeredekebb lejt˝o típusú megközelítést adja. Az α paraméter kulcsfontosságú az algoritmusban, szükségessége matematikailag több megközelítésb˝ol is igazolható. Levenberg eredetileg [72] azzal indokolta az α paraméter szükségességét, hogy segítségével megfelel˝o keretek között tarthatók az optimalizálandó paraméterértékek megváltozásai, helyes approximációt biztosítva ezáltal. Az α paraméterrel kapcsolatos kérdéskör azonban megközelíthet˝o a Hesse-mátrixhoz kapcsolódó megfontolásokból és a Tyihonov regularizációval [98] kapcsolatosan is. A 2.3. egyenlet a következ˝o formára egyszer˝usíthet˝o:  +   e[k] J[k] s[k] = − √ , (2.4) αI 0 ahol a + operátor a mátrix pszeudo-inverzét jelenti. Az s[k] uniform kiszámítási költsége O(n3 ), ahol n a Jacobi-mátrix oszlopainak száma. Minden egyes iterációs lépésben szükség van a Jacobi-mátrix elemeinek meghatározására, azaz a parciális deriváltak számítására is. Az α paraméter értéke a tanulás közben változtatható. Így az algoritmus k. iterációs lépése [35] alapján a következ˝o: 1. adott w[k] és α[k] ˝ (Inicializálásként tetszoleges pozitív α értéket választhatunk, azaz α[1] > 0) 39

2. J[k] és e[k] meghatározása 3. s[k] számítása (2.4) alapján. 4. Az úgynevezett megbízhatósági régió (trust region), r[k] számítása a követkeE(w[k])−E(w[k]+s[k]) ˝ zoképpen: r[k] = E(w[k])− . 1 kJ[k]s[k]+e[k]k2 2

˝ függoen: ˝ 5. Az α paraméter értékét dinamikusan állítjuk, r[k] értékétol • Ha r[k] < 0.25 akkor α[k + 1] = 4α[k] • Ha r[k] > 0.75 akkor α[k + 1] = α[k]/2 • Egyébként α[k + 1] = α[k] 6. Ha r[k] ≤ 0 akkor w[k + 1] = w[k], különben w[k + 1] = w[k] + s[k]. Ha teljesül a megállási feltétel, vagy elértünk egy el˝ore definiált maximális iterációszámot, akkor megállunk, különben folytatjuk a (k + 1). iterációs lépéssel.

40

3. fejezet Új módszerek és megközelítések az intelligens számítási modellek identifikációjában Ebben a fejezetben azoknak a vizsgálatoknak és eredményeknek a bemutatása következik, amelyek saját kutatásaimhoz kapcsolódnak. E fejezeten belül kerülnek megfogalmazásra az eredményeim lényegét megfogalmazó tézisek. Az új eredmények bemutatása kapcsán kitérek arra, hogy a javasolt módszereket esetenként többféle kiértékelési szempontból is összehasonlítsam az irodalomból megismert eljárásokkal. Az els˝o három alfejezetben trapéz alakú tagsági függvényeket használó Mamdani-típusú, COG defuzzifikációs módszert alkalmazó fuzzy rendszerek szabálybázisának identifikációjával foglalkozom. A 3.1. részben a szabályredukciós operátorokkal kiegészített bakteriális evolúciós algoritmust, a 3.2. részben a Levenberg-Marquardt módszert, a 3.3. részben pedig a bakteriális memetikus algoritmust javaslom a szabályidentifikációs feladat megoldására. A 3.4. alfejezetben TakagiSugeno-típusú fuzzy rendszerek paramétereinek optimalizálására javaslok módszert. A 3.5. részben bemutatom a bakteriális programozást B-spline típusú neurális hálózatok struktúrájának meghatározására alkalmazva. A 3.6. részben a bakteriális evolúciós algoritmust alkalmazom nagy dimenziójú problémák lényeges változóinak, jellemz˝oinek a kiválasztására.

3.1. Szabályredukciós operátorokkal kiegészített bakteriális evolúciós algoritmus alkalmazása Ebben a részben a 2.2.4. alfejezetben megismert bakteriális evolúciós algoritmus olyan továbbfejlesztését ismertetem, mely háromszög alakú tagsági függvények helyett az általánosabb trapéz alakú tagsági függvényeket használja, és ezenkívül újszer˝u szabályredukciós operátorokat is tartalmaz, melyek segítségével a szabálybázis mérete is optimálisan beállítható.

41

3.1. ábra. A tagsági függvény paraméterei

3.1.1. A javasolt algoritmus A bakteriális evolúciós algoritmus szabályredukciós operátorokkal kiegészített változata a következ˝o: kezdeti populáció létrehozása generáció=0 amíg generáció < max. generáció { bakteriális mutáció alkalmazása minden egyedre szabályredukciós operátorok minden egyedre: { szabály megszüntetés szabály egyesítés szemantikus elemzés szabály eltávolítás } génátadás generáció = generáció + 1 } A baktérium kromoszómájában, csakúgy mint a 2.2.4. fejezetben tárgyalt els˝o bakteriális evolúciós algoritmusban, a szabálybázis paraméterei, azaz a tagsági függvények vannak bekódolva. Az eredeti módszerrel ellentétben nem háromszög alakú, hanem trapéz alakú tagsági függvényeket használok. Egy trapézt négy paraméterrel lehet megadni, szokásosan (és legegyszer˝ubben) a négy töréspontjával, ahogy a 3.1. ábrán látható. A négy paraméterre a trapéz tulajdonságaiból adódóan teljesülnie kell annak, hogy a ≤ b ≤ c ≤ d. Az ábrán látható, hogy ha b = c, akkor a háromszög alakú tagsági függvényhez jutunk. Ha még b − a = d − c (azaz 2b = a + d) is teljesül, akkor az algoritmus eredeti változatában ([82]) alkalmazott egyenl˝o szárú háromszög alakú tagsági függvényt kapjuk. A trapéz alakú tagsági függvény 42

3.2. ábra. A kódolási elrendezés

a négy paraméterén kívül rendelkezik két indexszel is, melyek a helyét határozzák meg a szabálybázisban. Az Aij (aij , bij , cij , dij ) tagsági függvény a j. bemeneti változóhoz tartozik az i. szabályban. A Bi (ai , bi , ci , di ) tagsági függvény a kimeneti változóhoz tartozik az i. szabályban. (A kimeneti tagsági függvénynek csak egy indexe van, mivel egy kimenet˝u rendszerekkel foglalkozom.) Egy bemeneti vektor j. dimenziója, xj , az i. szabályban a következ˝o tagsági értéket eredményezi:  x −a j ij  , ha aij < xj < bij  bij −aij   1, ha bij ≤ xj < cij (3.1) Aij (xj ) = dij −xj  , ha c ≤ x < d ij j ij  dij −cij   0, egyébként ahol aij ≤ bij ≤ cij ≤ dij szükségszer˝uen teljesül a töréspontok egymáshoz képesti elhelyezkedése miatt. Egy szabálynak összesen 4(n + 1) paramétere van, ahol n a szabályok bemeneteinek száma. A szabályok a kromoszómában egymás után, felsorolásszer˝uen szerepelnek, ahogy az a 3.2. ábrán látható. A 3.2. ábrán egy két bemenet˝u, N darab szabályból álló szabálybázis elrendezése látható. A 3. szabály az ábra alapján a következ˝o: R3 :

Ha x1 = A31 (4,3; 5,1; 5,4; 6,3) és x2 = A32 (1,2; 1,3; 2,7; 3,1) akkor y = B3 (2,6; 3,8; 4,1; 4,4).

A kromoszóma összesen 4N (n + 1) valós számot tartalmaz, egy tagsági függvényen belül megtartva a rendezettséget. A kezdeti populáció létrehozása a populációt alkotó Negyed számú egyed véletlenszer˝u létrehozását jelenti. Minden egyedhez N (n + 1) véletlenszer˝u tagsági függvényt generálok, a tagsági függvényt alkotó trapéz négy paraméterénél ügyelve a trapéz paramétereinek a rendezettségére, továbbá arra is, hogy az adott változóhoz, melyre a tagsági függvény éppen generálódik, tartozó intervallumba beleessenek a trapéz paraméterei, vagy pedig valamekkora el˝ore definiált megengedett túlnyúlási százalékot ne haladjanak meg. A bakteriális mutáció hasonlóan történik, mint a háromszög alakú tagsági függvényt használó módszernél, itt azonban az egyes klónokban a trapézok változnak meg. A trapézok megváltoztatásánál arra kell ismét ügyelni, hogy az új trapéz paraméterei megfeleljenek a korábban említett feltételeknek. 43

3.3. ábra. Kromoszóma a génátadásnál

A bakteriális mutáció után a következ˝o alfejezetben ismertetend˝o szabályredukciós operátorok alkalmazása történik meg. Végül a génátadási operátor használata következik, mely hasonlóan történik az eredeti módszernél alkalmazotthoz, de egy továbbfejlesztett lehet˝oséggel. Nevezetesen, hogy a forrásbaktériumtól a célbaktériumnak adandó génrészletet nem muszáj véletlenszer˝uen kiválasztani, hanem jobb alternatíva lehet nagy aktivációs érték˝u szabályok átadása, mely kis aktivációs érték˝u szabályt ír felül a célbaktériumban. Ehhez az egyedeket alkotó szabályok aktivációs értékét, azaz az átlagos tüzelési értékét határozom meg a következ˝oképpen (3.3. ábra): m

1 X (j) wi = w , m j=1 i

(3.2)

(j)

ahol i a szabály indexe, wi az i. szabály tüzelési értéke a j. mintára, m a minták száma. Az algoritmusban ügyelni kell arra, hogy a keletkezett szabálybázis ne legyen ritka, azaz minden lehetséges megfigyelésvektor esetén legyen tüzel˝o szabály, ahogy ezt korábban a szabálybázisokról szóló 2.1.5.1 alfejezetben említettem (ε lefedettség). Ezt úgy garantálom, hogy nem engedek olyan egyedet létrehozni, amelyik ezt a feltételt nem teljesíti. Az operátorok alkalmazása során körültekint˝oen kell eljárni ennek a feltételnek a betartásához. A másik lehet˝oség büntet˝o függvény alkalmazása lenne azokra az egyedekre, melyek a feltételt nem teljesítik, vagyis az ilyen egyedek kiértékelése a hibatagon kívül egy járulékos büntet˝o tagot is tartalmaz. Ebben az esetben azonban a büntet˝o függvény rossz megválasztásával, illetve nem megfelel˝o súlyozásával létrejöhetnek nem megfelel˝o szabálybázist reprezentáló egyedek. 3.1.1.1. Szabályredukciós operátorok A bakteriális operátorok az optimálishoz egyre közelebb kerül˝o szabálybázist hoznak létre. Sokszor szükség van azonban arra is, hogy ne csak optimális legyen a szabálybázis, hanem minél kisebb méret˝u is legyen. A hatástalan szabályokat megszüntetve, a hasonlókat pedig összevonva egy szabályba, csökkenthet˝o a szabálybázis mérete anélkül, hogy a szabálybázis által adott hiba jelent˝osen megn˝one ezen egyszer˝usít˝o m˝uveletek eredményeképpen. Szabályredukciós operátorokat korábban más szerz˝ok is javasoltak [81, 94]. Ezekben a m˝uvekben azokban nem az általános és igen elterjedt trapéz alakú tagsági függvényekre definiálják az egyszer˝usít˝o operátorokat, hanem háromszög illetve Gauss-görbe alakú tagsági 44

3.4. ábra. Tagsági függvény megszüntetése

függvényekre. Ezen operátorok helyett az értekezésben a következ˝okben ismertetend˝o, trapéz alakú tagsági függvényekre definiált szabálybázis egyszer˝usít˝o m˝uveletek végrehajtását javaslom minden egyedre. 3.1.1.2. Szabály megszüntetés Ha egy tagsági függvény túl keskennyé válik, akkor megszüntetem a szabályt, amelyik használja. Ilyenkor ugyanis ennek a szabálynak az átlagos tüzelési értéke elenyész˝o lesz a többi szabályéhoz képest. A megszüntetés kritériuma a következ˝o:   aj + bj + cj + dj ≥ βlj , (3.3) li µi 4 ahol li és lj az adott változóhoz tartozó tagsági függvény középvonalának hossza az i. és a j. szabályban, β pedig a megszüntetés paramétere. A 3.4. ábrán láthatóan az ugyanahhoz a változóhoz tartozó két tagsági függvény az egyik szabályban sokkal szélesebb, mint a másik szabályban, és a szélesebb majdnem teljesen magába foglalja a keskenyebbet. Ilyenkor megszüntetem azt a szabályt, amelyikben a keskenyebb tagsági függvény van. A megszüntetés szigorúsága a β paraméterrel szabályozható. Minél nagyobb β értéke, annál szigorúbb a megszüntetés feltétele.

45

3.5. ábra. Tagsági függvények egyesítése

3.1.1.3. Szabály egyesítés Ha ugyanahhoz a változóhoz tartozó két tagsági függvény hasonlóvá válik, akkor egyesíthet˝ok egyetlen közös tagsági függvénnyé. A hasonlóság fogalmától két kritériumot követelek meg. Egyrészt a két tagsági függvény szélessége legyen körülbelül ugyanakkora, és legyenek közel egymáshoz (3.5. ábra). Ennek alapján a két feltétel: li − 1 < γ és |f | < γ, (3.4) lj ahol li és lj az adott változóhoz tartozó tagsági függvény középvonalának hossza az i. és a j. szabályban, f pedig az li és lj középpontjai közötti távolság. A tagsági függvények egyesítéséhez mindkét feltételt teljesíteni kell, de csak egy paramétert használok, γ-t, mellyel az egyesítés szigorúságát befolyásolom. Minél kisebb γ értéke, annál szigorúbb az egyesítés feltétele. Az egyesítés után a két tagsági függvény meg fog egyezni, a paramétereik pedig a következ˝ok lesznek: zi li + zj lj zu´j = , (3.5) li + lj ahol z rendre behelyettesítend˝o a,b,c és d-vel. 3.1.1.4. Szemantikus elemzés Ha két szabály feltételrésze megegyezik, viszont a következményük különböz˝o, akkor a kimeneti változóhoz tartozó tagsági függvényeket (azaz a következményeket) egyesítem egy 46

3.1. táblázat. Rögzített szabályszám Negyed

Nkl´on

Ninf

10 10 6

10 10 10

4 8 11

legjobb egyed 5,09 5,04 5,21

átlag 5,82 5,76 5,93

legrosszabb egyed 6,12 6,23 6,41

teszt hiba 12,3 11,9 12,2

szabályok száma 6 6 5

közös tagsági függvénnyé, az egyesítésnél megismert képlet segítségével. 3.1.1.5. Szabály eltávolítás Ha két szabály megegyezik, akkor az egyiket eltávolítom. Az egyes egyesítések során el˝ofordul, hogy két szabály feltételrésze azonos lesz. Ezután a szemantikus elemzés egyesíti a következményeiket is, tehát a két szabály megegyez˝o lesz, az egyiket törlöm. Az egyesítések hatása ennélfogva ezen két utóbbi operátor alkalmazása után fog érvényesülni.

3.1.2. A módszer tesztelése Az új algoritmus kifejlesztése során elkészítettem az azt implementáló programot. Az értekezésben szerepl˝o tézisekhez kifejlesztett programok az értekezéshez csatolt CDmellékleten találhatók. Szimulációs vizsgálatokat hajtottam végre az algoritmusban szerepl˝o operátorok elemzése céljából. A vizsgálatokat egy az irodalomban ismert problémán hajtottam végre. Ennél a referencia problémánál a cél a következ˝o hat változós függvény fuzzy szabálybázissal történ˝o approximációja: √ (3.6) y = x1 + x2 + x3 x4 + 2e2(x5 −x6 ) , ahol x1 ∈ [1; 5], x2 ∈ [1; 5], x3 ∈ [0; 4], x4 ∈ [0; 0,6], x5 ∈ [0; 1], x6 ∈ [0; 1,2]. A bakteriális operátorokban az egyedeket a következ˝o hibadefiníció alapján értékeltem ki, és a kapott eredményeket is ezen hibakritérium alapján hasonlítottam össze: m

1 X |ti − yi | , E= m i=1 Imax − Imin

(3.7)

ahol ti az i. mintára vonatkozó megkívánt kimenet, yi az i. mintára számított modell kimenet, m a minták száma, Imax a kimeneti változó fels˝o korlátja, Imin pedig az alsó korlátja, azaz a hiba normálva van a kimeneti változó intervallumának hosszával. Az els˝o futtatási eredmények a 3.1. táblázatban láthatók. Ennek során nem használtam a szabályredukciós operátorokat, a szabályok száma rögzítve volt. A tanító minták száma és a tesztelési minták száma egyaránt 200, a generációszám 40. A szimuláció célja a szabály csökkent˝o operátorok alkalmazásának vizsgálata a szabálybázisban lév˝o redundancia redukálására. Számos szimulációt hajtottam végre annak érdekében, hogy megtaláljam ezen operátorok paramétereinek optimális értékeit, ami azért szükséges, hogy elkerüljem 47

3.2. táblázat. A megszüntet˝o paraméter (β) hatása β 5 6 8 10

átlagos szabályszám 4,7 5,4 7,6 7,8

tanítási hiba 5,23 5,02 4,52 4,13

tesztelési hiba 8,94 8,47 8,32 8,17

a „túl egyszer˝u” szabálybázisok generálását. A legjobb baktériumra vonatkozó futtatási eredmények a 3.2. táblázatban láthatók. Az egyesítés operátor paramétere γ = 5%, a kezdeti szabályszám 10, az egyedek száma 10, a klónok száma 20, az infekciók száma pedig 4. A táblázat eredményei 10 futtatás átlagát mutatják. A β paraméter értékének a növelésével a megmaradó szabályok száma is növekszik, mert a szabályok megszüntetésének kritériuma szigorodik ilyenkor. A táblázatból látszik, hogy ha a szabályok száma a végs˝o szabálybázisban nagyobb, akkor ennek megfelel˝oen a tanítási hiba kisebb, viszont a tesztelési hiba csökkenése csak kisebb mérték˝u. Ennek oka, hogy egy nagyobb szabálybázis túl specifikus a tanító készletre, és nincs sok el˝onye, amikor egy független mintakészletre alkalmazzák. Ennek alapján megállapítható, hogy nem szükséges β-nak nagy értéket adni, mert akkor a megszüntetés szigorúsága miatt az túl komplex szabálybázist eredményez, mely hasonló képesség˝u, mint amilyen egy kisebb szabálybázis lenne. A következ˝okben tézisek formájában fogalmazom meg az e fejezetben ismertetett új eredményeket. A tézissel kapcsolatos publikációim a hivatkozási listában megtalálhatók [15, 16, 57, 17, 59, 23]. 1. tézis. Újszer˝u szabályredukciós operátorokkal kiegészített bakteriális evolúciós algoritmust vezettem be Mamdani-típusú trapéz alakú tagsági függvényeket és COG defuzzifikációs módszert alkalmazó fuzzy szabálybázis optimalizálására. 1.1. altézis. Újszer˝u szabályredukciós operátorokat dolgoztam ki optimális szabálybázisméret meghatározásának céljából. 1.2. altézis. Elkészítettem a szabályredukciós operátorokkal kiegészített bakteriális evolúciós algoritmust megvalósító számítógépes eljárást, és az azt implementáló programot, mely Mamdani-típusú, trapéz alakú tagsági függvényeket használó fuzzy szabályalapú rendszer szabálybázisának optimalizálására alkalmas. 1.3. altézis. Egy, az irodalomban használatos referenciaprobléma modellezésére szimulációs vizsgálatokat végeztem, mellyel a szabályredukciós operátorok hatásait elemeztem.

48

3.2. A Levenberg-Marquardt algoritmus alkalmazása Mamdani-típusú fuzzy szabálybázis optimalizálására Amint azt a 2.3.6. alfejezetben láttuk, a Levenberg-Marquardt algoritmus jó konvergencia tulajdonságokkal rendelkezik lokális környezetben történ˝o kereséseknél. Az algoritmus általános nemlineáris optimalizációs módszer olyan problémák megoldására, ahol ismertek a célfüggvény deriváltjai. A módszert sikeresen alkalmazták neurális hálózatok paramétereinek a meghatározására [91]. Ebben a fejezetben az algoritmus Mamdani-típusú, COG defuzzifikációs eljárást alkalmazó, trapéz alakú tagsági függvényeket használó fuzzy rendszerek paramétereinek meghatározására történ˝o újszer˝u alkalmazását ismertetem.

3.2.1. A Jacobi-mátrix meghatározása Az algoritmus minden egyes iterációs lépésében szükséges a Jacobi-mátrix elemeinek, azaz az összes parciális deriváltnak a kiszámítása. A fuzzy rendszer szabályainak számát a teljes algoritmus m˝uködése során rögzítjük. A szabályokban trapéz alakú tagsági függvényeket használunk, amelyek a következ˝o formában írhatók fel: µij (xj ) =

dij − xj xj − aij Ni,j,1 (xj ) + Ni,j,2 (xj ) + Ni,j,3 (xj ). bij − aij dij − cij

(3.8)

Ebben az összefüggésben az aij , bij , cij , dij értékek az i. szabály j. bemeneti változójához tartozó tagsági függvény négy paraméterét jelentik. A kimeneti változóhoz az i. szabály esetén az ai , bi , ci , di értékek tartoznak, továbbá: ( 1, ha xj ∈ [aij , bij ] Ni,j,1 (xj ) = 0, ha xj ∈ / [aij , bij ] ( 1, ha xj ∈ (bij , cij ) Ni,j,2 (xj ) = (3.9) 0, ha xj ∈ / (bij , cij ) ( 1, ha xj ∈ [cij , dij ] Ni,j,3 (xj ) = 0, ha xj ∈ / [cij , dij ]. A trapézokat tehát ugyanúgy, ahogy az el˝oz˝o tézisben, a négy törésponttal írjuk le a 3.1. ábrán látható módon. Az eredeti Mamdani-algoritmusnak megfelel˝oen a következtetés során standard (min) t-normát alkalmazok, azaz az i. szabály illeszkedési mértéke valamely n-dimenziós crisp x megfigyelés vektor esetén: n

wi = min µij (xj ). j=1

(3.10)

A fuzzy következtetés kimenete a 2.1.5. alfejezetben meghatározott módon számítható. Az alkalmazott trapézok esetében a COG defuzzifikációs eljárás használatával a következ˝o

49

explicit alakba írható: y(x)= 1 3

PR

i=1

3wi (d2i −a2i )(1−wi )+3wi2 (ci di −ai bi )+wi3 (ci −di +ai −bi )(ci −di −ai +bi ) . PR 2 i=1 2wi (di −ai )+wi (ci +ai −di −bi )

(3.11)

A szabályok száma R, a szabályok n bemenet˝uek. Ezen összefüggések alapján meghatároztam a trapéz alakú tagsági függvényeket használó Mamdani-típusú, COG defuzzifikációs módszert alkalmazó fuzzy következtetési és irányítási modellekhez tartozó, a kimenetnek a modell paraméterei szerinti parciális deriváltjait, majd ezek alapján a Jacobi-mátrixot. A mátrix egy-egy sorát egy-egy minta alapján határozzuk meg. A p. sor az alábbi alakot veszi fel:   ∂y(x(p) ) ∂y(x(p) ) ∂y(x(p) ) ∂y(x(p) ) ∂y(x(p) ) J= ··· ··· ··· , (3.12) ∂a11 ∂b11 ∂a12 ∂d1 ∂dR ahol p a minta azonosítója és ∂y(x(p) ) ∂aij ∂y(x(p) ) ∂bij ∂y(x(p) ) ∂cij ∂y(x(p) ) ∂dij

∂y ∂wi ∂µij ∂wi ∂µij ∂aij ∂y ∂wi ∂µij = ∂wi ∂µij ∂bij ∂y ∂wi ∂µij = ∂wi ∂µij ∂cij ∂y ∂wi ∂µij = . ∂wi ∂µij ∂dij =

(3.13)

A 3.10. összefüggésb˝ol kit˝unik, hogy a wi értékek csak a tagsági függvényekt˝ol függnek, és minden tagsági függvénynek négy paramétere van. Ezért wi deriváltjai a következ˝ok lesznek: ( 1, ha µij = minnk=1 µik ∂wi = (3.14) ∂µij 0, egyébként. A tagsági függvények deriváltjai a következ˝o módon számíthatók: (p)

xj − bij ∂µij (p) = Ni,j,1 (xj ) 2 ∂aij (bij − aij ) (p)

aij − xj ∂µij (p) = Ni,j,1 (xj ) ∂bij (bij − aij )2 (p)

dij − xj ∂µij (p) = Ni,j,3 (xj ) ∂cij (dij − cij )2

(3.15)

(p)

xj − cij ∂µij (p) = Ni,j,3 (xj ). 2 ∂dij (dij − cij ) ∂y -t ∂wi

és a kimeneti tagsági függvények deriváltjait szintén ki kell számítani. A 3.11. össze-

50

függés alapján a következ˝o írható fel: ∂F ∂G 1 N ∂wii − S ∂wii ∂y = ∂wi 3 N2 ∂F ∂G ∂y 1 N ∂aii − S ∂aii = ∂ai 3 N2 ∂Fi ∂G ∂y 1 N ∂bi − S ∂bii = ∂bi 3 N2 ∂F ∂G 1 N ∂cii − S ∂cii ∂y = ∂ci 3 N2 ∂Fi ∂G ∂y 1 N ∂di − S ∂dii = , ∂di 3 N2

(3.16)

ahol N a 3.11 tört nevez˝oje, S pedig a számlálója. Fi az összeg i.-ik tagja a számlálóban, Gi az i. tag a nevez˝oben. A deriváltak a következ˝oképpen számíthatók: ∂Fi = 3(d2i − a2i )(1 − 2wi ) + 6wi (ci di − ai bi ) + 3wi2 [(ci − di )2 − (ai − bi )2 ] ∂wi ∂Gi = 2(di − ai ) + 2wi (ci + ai − di − bi ) (3.17) ∂wi ∂Fi ∂ai ∂Fi ∂bi ∂Fi ∂ci ∂Fi ∂di

= −6wi ai + 6wi2 ai − 3wi2 bi − 2wi3 (ai − bi ) = −3wi2 ai + 2wi3 (ai − bi ) = 3wi2 di − 2wi3 (di − ci ) = 6wi di − 6wi2 di + 3wi2 ci + 2wi3 (di − ci )

∂Gi ∂ai ∂Gi ∂bi ∂Gi ∂ci ∂Gi ∂di

= −2wi + wi2 = −wi2 = wi2

(3.18)

= 2wi − wi2 .

A mátrix oszlopainak száma 4(n + 1)R, sorainak száma pedig a minták számával egyezik meg.

3.2.2. A módszer alkalmazása Kifejlesztettem egy a Levenberg-Marquardt módszert alkalmazó, Mamdani-típusú fuzzy szabálybázis paramétereinek optimalizálására alkalmas számítógépes eljárást, és elkészítettem az azt implementáló programot. Szimulációs vizsgálatokat hajtottam végre, amelyekben az irodalomban található referenciaproblémákon összehasonlítottam a kifejlesztett új eljárást más módszerekkel. A Levenberg-Marquardt algoritmus trapéz alakú tagsági függvényeket használó fuzzy rendszer paramétereinek optimalizálása során olyan paraméter módosító vektort adhat eredményül, mely megváltoztathatja a trapéz töréspontjainak egymáshoz képesti helyzetét. Ezért 51

ilyen esetekben az eredményül kapott paraméter módosító vektort át kell alakítani, hogy az ne módosítsa a trapézok töréspontjainak egymáshoz képesti helyzetét. Ennek végrehajtása az irodalomból ismert korrekciós technikával történik [91]. Ha a pi < pi+1 rendezettségnek fenn kell állnia két szomszédos paraméter között, és a paraméter módosító vektor ezt megsérti, akkor a következ˝o korrekciós együtthatót határozzuk meg: g=

pi+1 [k] − pi [k] . 2 · (∆pi+1 [k] − ∆pi [k])

(3.19)

Az új paraméter értékek pedig a g korrekciós tag segítségével a következ˝oképpen számíthatók: pi+1 [k + 1] = pi+1 [k] − g · ∆pi+1 [k] pi [k + 1] = pi [k] − g · ∆pi [k].

(3.20)

Így garantálható a trapéz töréspontjainak megfelel˝o sorrendje a módosítás meghatározása után. 3.2.2.1. Referenciaproblémák Az algoritmus tesztelésére két tudományos problémát választottam. Mindkét feladatnál a következ˝o megállási feltételt használtam a Levenberg-Marquardt algoritmusra: E[k − 1] − E[k] < θ[k] √ kpar[k − 1] − par[k]k < τf (1 + kpar[k]k) √ kg[k]k ≤ 3 τf (1 + |E[k]|),

(3.21)

ahol θ[k] = τf (1 + |E[k]|) és τf = 10−4 . A g[k] a 2.3.5. alfejezetben definiált gradiens vektor, a par vektor pedig a tagsági függvények paramétereit tartalmazza sorrendben, szabályonként, és egy szabályon belül pedig az egyes dimenziók mentén haladva. A par vektor a 2.3.5. alfejezetbeli w súlyvektornak, azaz az optimalizálandó elemeknek felel meg. Az optimalizálandó paraméterek száma, mely megegyezik a Jacobi mátrix oszlopainak számával 4(n + 1)R, mert R a szabályok száma, mindegyikben n bemeneti és egy kimeneti fuzzy halmaz található, és egy fuzzy halmazt négy paraméterrel adunk meg. Az egyik referencia feladat az ún. pH probléma, mely egyváltozós. A cél ennél a feladatnál egy titrálási görbe inverzének a közelítése. Ez a fajta nemlinearitás a kémiai pH értékkel van kapcsolatban. A tanítómintákat a következ˝o egyenlet alapján generáljuk: q  y2 y −14 + 10 − 2 +6 log 4 0 , y = 2 · 10−3 x − 10−3 (3.22) pH = − 26 A tanításhoz 101 mintát generálunk. A másik referencia feladat az ún. inverz koordináta transzformációs probléma (ICT), amely kétváltozós. Ennél a feladatnál inverz transzformáció történik két koordináta és egy

52

kétkarú manipulátor egyik szöge között. A tanítómintákat a következ˝o összefüggések alapján állítjuk el˝o:   −1 s Θ2 = ± tan c √ 2 (3.23) s = 1 − c = sin(Θ2 ) 2 2 2 2 x + y − l1 − l2 c= = cos(Θ2 ). 2l1 l2 A cél az (x, y) 7→ Θ2 függvény közelítése. A tanításhoz 110 mintát generáltunk. 3.2.2.2. Hibadefiníciók Az algoritmus tesztelésére a következ˝o hibadefiníciókat alkalmazom: az átlagos négyzetes hibát (Mean Square of Error, MSE), az átlagos négyzetes relatív hibát (Mean Square of Relative Error, MSRE), és az átlagos relatív százalékos hibát (Mean Relative Error Percentage, MREP), melyeket a következ˝o módon értelmezek: m

M SE =

1 X (ti − yi )2 m i=1 m

1 X (ti − yi )2 M SRE = m i=1 yi2 m 100 X ti − yi M REP = , m i=1 yi

(3.24)

ahol ti az i. mintára vonatkozó megkívánt kimenet, yi az i. mintára számított modell kimenet, és m a minták száma. 3.2.2.3. Két paraméter optimalizációja Az els˝o szimulációs vizsgálat a Levenberg-Marquardt (LM) algoritmus tanítási képességeit mutatja, mindkét problémára, de az egyszer˝uség kedvéért csak két paramétert optimalizálva. Ezek az els˝o szabály els˝o bemeneti tagsági függvényének b és c paraméterei. Az LM algoritmus teljesítményét a hiba-visszaterjesztéses módszerrel (backpropagation, BProp, 2.3.5. alfejezet) hasonlítjuk össze. A fuzzy rendszert három szabályból építjük fel, a kezdeti szabálybázisok a 3.6. és a 3.7. ábrán láthatók. Egy lokális minimum a pH probléma esetén kb. a {b, c} = {0,349; 0,800} pontban található, az MSE érték 0,01; az ICT esetén pedig a {b, c} = {0,128; 0,245} pontban, ahol az MSE érték 0,865. Három különböz˝o kezdeti paraméter-elrendezést vizsgáltam, a kezdeti- és a végállapotbeli hiba (MSE) és a paraméter értékek a következ˝o ábrákon (a 3.8. ábrától a 3.11. ábráig) és a 3.3. és 3.4. táblázatban figyelhet˝ok meg. A táblázatok jól szemléltetik, hogy az LM módszer sokkal gyorsabban konvergál, mint a BProp. Mindkét algoritmus a lokális optimum közelébe vezet és jól közelítik a minimális hibát, de az LM algoritmusnak sokkal kevesebb iterációra van ehhez szüksége, mint a BProp módszernek. 53

3.6. ábra. Kezdeti szabálybázis a pH problémára

3.7. ábra. Kezdeti szabálybázis az ICT problémára

54

3.8. ábra. LM módszer teljesítménye a pH problémára

3.9. ábra. BProp módszer teljesítménye a pH problémára

55

3.10. ábra. LM módszer teljesítménye az ICT problémára

3.11. ábra. BProp módszer teljesítménye az ICT problémára

56

3.3. táblázat. Az eredmények összefoglalása a pH problémára módszer

kezd˝opont

végpont

LM LM LM BProp BProp BProp

{0,12; 0,20} {0,40; 0,50} {0,60; 0,65} {0,12; 0,20} {0,40; 0,50} {0,60; 0,65}

{0,355; 0,744} {0,387; 0,763} {0,355; 0,747} {0,278; 0,744} {0,398; 0,743} {0,355; 0,747}

kezdeti MSE 0,019 0,013 0,011 0,019 0,013 0,011

vég MSE 0,0100 0,0100 0,0100 0,0100 0,0100 0,0100

iterációk száma 6 4 8 86 38 8

3.4. táblázat. Az eredmények összefoglalása az ICT problémára módszer

kezd˝opont

végpont

LM LM LM BProp BProp BProp

{0,40; 0,70} {0,30; 0,40} {0,50; 0,65} {0,40; 0,70} {0,30; 0,40} {0,50; 0,65}

{0,100; 0,239} {0,190; 0,256} {0,113; 0,218} {0,155; 0,301} {0,162; 0,279} {0,156; 0,283}

57

kezdeti MSE 0,890 0,870 0,890 0,890 0,870 0,890

vég MSE 0,8650 0,8651 0,8653 0,8652 0,8650 0,8650

iterációk száma 4 4 7 21 14 24

3.12. ábra. A fuzzy rendszer paramétereinek alakulása

3.2.2.4. Az összes paraméter egyideju˝ optimalizációja A következ˝o szimuláció célja az volt, hogy a fuzzy szabálybázis minden egyes paraméterét optimalizáljuk. A 3.12. ábrán a szabálybázis paramétereinek alakulását látjuk az LM iterációk függvényében. A pH problémát vizsgáljuk, 15 iterációt hajtunk végre az algoritmusban, a szabálybázis 5 szabályt tartalmaz (azaz 40 paramétert optimalizálunk). A 3.13. ábrán az átlagos négyzetes hiba (MSE) alakulása látható. A 3.5. táblázatban egy összehasonlító vizsgálat eredményét láthatjuk. Különböz˝o típusú hibaértékeket számítva hasonlítottam össze az LM algoritmust és a Bakteriális Evolúciós Algoritmust (3.1. fejezet). Utóbbiban 10 baktériumot használtam 40 generáción keresztül, 8 klónt és 4 infekciót alkalmazva a bakteriális operátorokban rögzített szabályszám mellett. A 3.13. ábrán látható MSE görbét figyelve megállapíthatjuk, hogy az LM algoritmus valóban optimalizálja a szabályokat, igyekszik megtalálni a legközelebbi lokális optimumot a hibát minimálisra csökkentve. Tizenöt iteráció elegend˝o volt a lokális optimum közelébe jutásához. A 3.5. táblázatból látható, hogy a kiindulási ponthoz képest az MSE hiba milyen mértékben csökkent a szabálybázison. Habár a bakteriális evolúciós algoritmus valamelyest jobb eredményt adott, ez annak köszönhet˝o, hogy ez a módszer az LM algoritmussal ellentétben a globális optimumba konvergál. A megfelel˝o pontból indított LM módszerrel 15 iterációs lépés után elért eredmény így sem sokkal marad el a 10 egyedet 40 generáción át használó bakteriális megközelítést˝ol. A két módszert kombinálva viszont még jobb eredményt érhetünk el (3.3. fejezet). A következ˝okben tézisek formájában fogalmazom meg az e fejezetben ismertetett új eredményeket. A tézissel kapcsolatos publikációim az értekezés végi hivatkozási listában

58

3.13. ábra. Az MSE érték fejl˝odése

3.5. táblázat. A teljes fuzzy szabálybázis optimalizálása a pH problémára a LevenbergMarquardt módszerrel és a Bakteriális Evolúciós Algoritmussal fuzzy szabálybázis LM – kezdeti LM – végállapot BEA – végállapot

MSE 6,5 · 10−3 9,83 · 10−4 7,01 · 10−4

59

MSRE 1,98 · 10−1 1,42 · 10−1 1,23 · 10−1

MREP 25,5 16,7 14,9

megtalálhatók [18, 11, 59, 55, 56, 57]. 2. tézis. Új lokális optimalizációs algoritmust, a Levenberg-Marquardt algoritmust, javasoltam Mamdani-típusú trapéz alakú tagsági függvényeket és COG defuzzifikációs módszert alkalmazó fuzzy szabályalapú rendszer tagsági függvényei paramétereinek meghatározására, és megmutattam, hogy az eljárás az irodalomban ismert módszereknél kedvez˝obb tulajdonságú. 2.1. altézis. Meghatároztam a trapéz alakú tagsági függvényeket használó Mamdani-típusú, COG defuzzifikációs módszert alkalmazó fuzzy következtetési és irányítási modellekhez tartozó, a kimenetnek a modell paraméterei szerinti parciális deriváltjait, és ezek alapján a teljes Jacobi-mátrixot. 2.2. altézis. Kifejlesztettem egy új, a Levenberg-Marquardt módszert alkalmazó, Mamdanitípusú, trapéz alakú tagsági függvényeket használó, fuzzy szabálybázis paramétereinek lokális optimalizálására alkalmas számítógépes eljárást, és elkészítettem az azt implementáló programot. 2.3. altézis. Az irodalomban használatos referenciaproblémák modellezésére szimulációs vizsgálatokat végeztem. Azt találtam, hogy a kifejlesztett új eljárás a megvizsgált esetek mindegyikében lényegesen jobb konvergencia eredményeket adott négyzetes középpel számítva, mint a backpropagation eljárás. Ennek, valamint az elméleti jelleg˝u indikációk alapján várhatónak tartom, hogy az általam javasolt eljárás el˝onyei más konkrét esetben is megmutatkoznak.

3.3. Bakteriális memetikus algoritmus alkalmazása Mamdani-típusú fuzzy szabálybázis optimalizálására Ahogy azt az els˝o tézis kapcsán láttuk, a bakteriális evolúciós algoritmusok sikeresen alkalmazhatók fuzzy szabálybázisok identifikációjára. A bakteriális operátorok biztosítják a populáció fejl˝odését, „evolúcióját”, azaz egyre jobb szabálybázisok kialakulását. A második tézisben egy másik modellidentifikációs eszközt, a Levenberg-Marquardt algoritmust alkalmaztam trapéz alakú tagsági függvényeket használó fuzzy szabályok optimalizálására. A bakteriális megközelítés evolúciós típusú módszer, mely ennélfogva globális jelleg˝u keresést tesz lehet˝ové, viszont az algoritmus által talált megoldás meglehet˝osen lassan konvergál. A Levenberg-Marquardt algoritmus, mely gradiens alapú technika, képes pontosabb megoldást találni, viszont hátránya, hogy ezt valamely lokális környezetben teszi, és így az optimalizáció során könnyen lokális minimumba ragadhatunk. Az evolúciós és gradiens alapú technikák kombinálásával mindkét típusú módszer el˝onyei kihasználhatók, és hátrányaik kiküszöbölhet˝ok. A kétféle megközelítés kombinációját az irodalomban memetikus algoritmusnak szokás nevezni [80]. Ezen módszerek nem a „darwini evolúciós modellt” [28] alkalmazzák, hanem az ún. „lamarcki evolúciót” [69], melynek lényege, hogy az egyedek nemcsak az örökölt tulajdonságaikat adják tovább utódaiknak, hanem az „életük során szerzett”, 60

3.14. ábra. Bakteriális memetikus algoritmus

azaz a tanult tulajdonságaikat is. Habár a biológiában ez az elv hibás, kiválóan alkalmazható az informatikában, számos memetikus eredmény található a szakirodalomban [1, 85, 93]. A hagyományos evolúciós operátorok mellett ezekben a módszerekben megjelenik a tanulás is, mely valamely lokális keresést jelent, amely által az egyed tökéletesebbé válik. A bakteriális megközelítés és a Levenberg-Marquardt algoritmus külön-külön a saját kategóriájuk legjobb módszerei közé tartoznak. Kézenfekv˝o a gondolat, hogy e két módszert célszer˝u kombinálni. A bakteriális operátorok által megvalósított hatékony evolúciót az egyes baktériumokon alkalmazott Levenberg-Marquardt algoritmus teszi még tökéletesebbé. A kombinált módszert bakteriális memetikus algoritmusnak neveztem el [12].

3.3.1. A javasolt algoritmus A bakteriális memetikus algoritmus folyamatábrája a 3.14. ábrán látható. A bakteriális mutációs és a génátadási lépés között a Levenberg-Marquardt algoritmust alkalmaztam minden egyes egyedre (baktériumra). A módszert, csakúgy mint az el˝oz˝o fejezetekben javasolt technikákat, Mamdani-típusú, trapéz alakú tagsági függvényeket és COG defuzzifikációs módszert alkalmazó fuzzy szabálybázis optimalizációjára alkalmaztam. A kódolási elrendezés és a szükséges definíciók megegyeznek az el˝oz˝o tézisekben alkalmazottakkal. Az algoritmusnak kétféle változatára tettem javaslatot. Az els˝o változatban a szabálybázis mérete a folyamat során állandó, azaz az egyedeket mindig ugyanannyi szabály alkotja, vagyis a baktériumok hossza a fejl˝odés során állandó és a baktériumok egyforma hosszúak. Ilyenkor az els˝o tézisben megismert bakteriális mutációt és génátadást használom ebben az algoritmusban is, változatlan formában. A génátadásnál a forrásbaktériumtól kapott szabály egy szabályt ír felül a célbaktériumban. 61

Az algoritmus másik változatában az egyes baktériumok hossza a folyamat során változhat, és egymástól is különbözhet. A cél nemcsak a szabályok optimalizálása, hanem a szabálybázis optimális méretének automatikus meghatározása is. Ebben az esetben a bakteriális mutáció és a génátadás okozhatják a baktériumok hosszának megváltozását. A bakteriális mutáció a következ˝oképpen történik: miután az adott baktérium klónjai létrejöttek, az egyes klónokban a mutáció során három lehet˝oség közül lehet véletlenszer˝uen választani. Az egyik lehet˝oség az éppen megváltoztatandó szabály törlése a klónból, a másik lehet˝oség a kijelölt szabály paramétereinek véletlenszer˝u módosítása (ez az eredeti bakteriális mutációnak megfelel˝o lehet˝oség), a harmadik pedig a kijelölt szabály paramétereinek módosítása és ezzel egyidej˝uleg egy új szabály véletlenszer˝u létrehozása. A génátadás végrehajtásakor két lehet˝oség közül lehet véletlenszer˝uen választani: a forrásbaktériumtól kapott szabály vagy felülír egy szabályt a célbaktériumban, vagy pedig új szabályként hozzáadódik a célbaktériumhoz. Az ily módon továbbfejlesztett bakteriális mutációs és génátadási operátorok lehet˝ové teszik a baktériumok hosszának növekedését illetve csökkenését. Az egyedek olyan kritérium alapján értékel˝odnek ki az operátorokban, amely nemcsak a szabálybázis által számított approximációs hibát veszi figyelembe, hanem a szabálybázis méretét is. Több szabály ugyanis általában kedvez˝obb hibát ad, viszont növeli a modell komplexitását, ezért cél a minél kevesebb szabály elérése is. A Bayes-i információs kritérium segítségével mindkét célt, azaz a minél kisebb hiba és minél kevesebb szabály elérését, egy összefüggésben lehet megfogalmazni: BIC = m · ln(M SE) + n · ln(m),

(3.25)

ahol m a tanítóminták száma, n pedig a szabályok száma. A Levenberg-Marquardt algoritmus a 2. tézisben leírt módon kerül alkalmazásra, ez a lépés nem változtatja meg a baktérium hosszát.

3.3.2. Az algoritmus alkalmazása Az új algoritmus kifejlesztése során elkészítettem az azt implementáló programot. Szimulációs vizsgálatokat hajtottam végre, amelyekben a kifejlesztett új eljárást hasonlítottam össze a bakteriális evolúciós algoritmussal az irodalomban található referenciaproblémákon. Az el˝oz˝o két tézisben szerepl˝o referenciaproblémákat alkalmaztam, és a javasolt algoritmust olyan bakteriális evolúciós algoritmussal hasonlítottam össze, mely minden tekintetben megegyezik a bakteriális memetikus algoritmussal, kivéve természetesen, hogy nem tartalmazza a Levenberg-Marquardt módszert. 3.3.2.1. Rögzített szabályszám El˝oször a rögzített szabályszámú változattal végeztem szimulációs futtatásokat, a szabályok száma 3. A pH probléma esetén a tanítóminták száma 101, az ICT problémánál 110, míg a hatváltozós függvény esetén 200. A tesztelési minták száma megegyezik a tanítóminták számával. Az algoritmusokban 10 egyedet használtam, a klónok száma 8, az infekciók száma pedig 4. A Levenberg-Marquardt módszer 10 iterációs lépést használ, a 2. tézisben

62

3.6. táblázat. MSE, MSRE és MREP átlagértékek a tanító és a tesztelési mintákra minden probléma esetén a BEA használatával hibadef. MSE MSRE MREP MSE-teszt MSRE-teszt MREP-teszt

pH 1,5 · 10−2 2,8 · 103 2 · 102 7,4 · 10−3 1,1 · 104 3,9 · 102

ICT 5,0 · 10−1 1,1 · 1014 2,4 · 108 6,0 · 10−1 8,2 · 10−2 2,5 · 101

6 dim. 3,4 · 101 6,8 · 10−1 7,2 · 101 3,5 · 101 6,1 · 10−1 6,8 · 101

3.7. táblázat. MSE, MSRE és MREP átlagértékek a tanító és a tesztelési mintákra minden probléma esetén a BMA használatával hibadef. MSE MSRE MREP MSE-teszt MSRE-teszt MREP-teszt

pH 8,9 · 10−4 4,9 · 103 5,8 · 102 1,0 · 10−3 1,9 · 104 1,2 · 103

ICT 1,4 · 10−1 2,3 · 1013 9,8 · 107 9,9 · 10−2 1,3 · 10−2 9,3

6 dim. 3,0 · 101 5,9 · 10−1 6,6 · 101 3,3 · 101 5,5 · 10−1 6,4 · 101

megfogalmazott leállási feltétellel (3.21). A generációszám 20, és mindkét algoritmus 10szer futott mindegyik problémára. A vizsgálat során az el˝oz˝o tézisben alkalmazott MSE, MSRE, és MREP hibakritériumokat használtam (ld. 3.24). A Bakteriális Evolúciós Algoritmus (BEA) által 10 futtatás során kapott átlageredményeket mutatja a 3.6. táblázat, a Bakteriális Memetikus Algoritmus (BMA) által kapott átlageredmények pedig a 3.7. táblázatban láthatók. A táblázatokból leolvasható, hogy a BMA minden problémára jobb eredményeket ad az MSE kritérium alapján, mint a BEA. Az egyváltozós pH probléma esetén a legszembet˝un˝obb a különbség, ahol is a BMA kb. 16-szor jobb eredményt (kisebb hibát) ad. Általában mindegyik hibakritérium szerint jobb eredményt ad a BMA, kivéve a relatív hibakritériumokat a pH problémára. Ezt majd kés˝obb vizsgálom, amikor a legjobb egyedeket elemzem. Az ICT probléma tanítókészletében van néhány nullához közeli minta, emiatt a relatív hiba igen magas, összehasonlítva a tesztelési készletre kapott hibákkal, ahol ilyen minták nem fordulnak el˝o. Az átlagos hibák tanulmányozása is fontos, azonban lényegesebb elemezni a legjobb egyedek által adott eredményeket. A 3.8. táblázatban az MSE kritérium alapján az összes futtatás során kapott legjobb egyed eredményei láthatók. Mindegyik esetre a BMA adja a legjobb MSE érték˝u megoldást nemcsak a tanítóminták tekintetében, hanem a tesztelési minták vonatkozásában is. A 3.8. táblázatból látszik viszont az is, hogy a BEA jobb relatív hibaeredményt ad a pH problémára. Ez f˝oleg annak köszönhet˝o, hogy van néhány minta viszonylag 63

3.8. táblázat. Az MSE kritérium alapján az összes futtatás során talált legjobb egyed hibadef. MSE MSRE MREP MSE-teszt MSRE-teszt MREP-teszt MSE MSRE MREP MSE-teszt MSRE-teszt MREP-teszt MSE MSRE MREP MSE-teszt MSRE-teszt MREP-teszt

BEA 4,5 · 10−5 2,1 · 10−1 2,8 · 101 7,6 · 10−3 4,2 · 10−1 5,1 · 101 3,4 · 10−1 4,7 · 1013 1,4 · 108 2,0 · 10−1 2,6 · 10−1 1,5 · 101 2,5 · 101 5,4 · 10−1 6,3 · 101 2,6 · 101 4,5 · 10−1 5,6 · 101

BMA 1,5 · 10−5 3 · 102 1,7 · 102 3 · 10−5 1,2 · 103 3,5 · 102 8,5 · 10−2 3,6 · 1013 1,7 · 107 2,0 · 10−2 2,7 · 10−3 4,4 2,0 · 101 4,4 · 10−1 5,4 · 101 2,3 · 101 4,3 · 10−1 5,6 · 101

probléma pH pH pH pH pH pH ICT ICT ICT ICT ICT ICT 6 dim. 6 dim. 6 dim. 6 dim. 6 dim. 6 dim.

alacsony értékkel (kb. 10−4 ). Viszont ha a relatív hibakritérium alapján kapott legjobb egyedeket hasonlítom össze akkor megállapítható, hogy ebb˝ol a szempontból is a BMA adja az egyértelm˝uen jobb eredményt, ahogy az a 3.9. táblázatban látható. A táblázatok egyértelm˝uen azt mutatják, hogy a BMA jobb eredményeket ad, mint a BEA. A következ˝o néhány ábra ugyanezt támasztja alá. A 3.15. és 3.16. ábra a legjobb MSE érték˝u egyed cél- és a hibaértékeit mutatja az egyes mintákra a pH probléma esetén BEA illetve BMA használatával. A BMA-ra vonatkozó hiba teljesen sima, látható, hogy a módszer a mintakészlet minden elemére milyen kicsi hibát ad. Magasabb dimenziószámú problémára a hiba is magasabb. Ennek oka, hogy összesen csak 3 szabályt tartalmaz a szabálybázis mindegyik problémára, ezért a hiba nagyobb a bonyolultabb problémák esetén. A 3.17. 3.18. és 3.19. ábrák az MSE értékek alakulását mutatják egy-egy futtatásra a különböz˝o problémákra. Ezek alapján is jól látszik a memetikus megközelítésben a Levenberg-Marquardt lépés által okozott javulás. A kapott optimális szabályokat is bemutatom. A tagsági függvényekben szerepl˝o trapézok paramétereinek nem szükségszer˝uen kell az adott változó intervallumán belül elhelyezkedniük, a trapéz kinyúlhat a változó intervallumából.

64

3.9. táblázat. Az MREP kritérium alapján az összes futtatás során talált legjobb egyed hibadef. MSE MSRE MREP MSE-teszt MSRE-teszt MREP-teszt MSE MSRE MREP MSE-teszt MSRE-teszt MREP-teszt MSE MSRE MREP MSE-teszt MSRE-teszt MREP-teszt

BEA 1,5 · 10−2 1,6 · 10−1 2,6 · 101 2,3 · 10−3 2,8 · 10−1 3,5 · 101 3,5 · 10−1 8,4 · 1013 2,0 · 107 1,8 · 10−1 2,3 · 10−2 1,4 · 101 2,5 · 101 5,4 · 10−1 6,3 · 101 2,6 · 101 4,5 · 10−1 5,6 · 101

BMA 8 · 10−4 1 · 10−1 1,5 · 101 1,3 · 10−3 2 · 10−1 2,8 · 101 8,5 · 10−2 3,6 · 1013 1,7 · 107 2,0 · 10−2 2,7 · 10−3 4,4 2,0 · 101 4,4 · 10−1 5,4 · 101 2,3 · 101 4,3 · 10−1 5,6 · 101

probléma pH pH pH pH pH pH ICT ICT ICT ICT ICT ICT 6 dim. 6 dim. 6 dim. 6 dim. 6 dim. 6 dim.

3.15. ábra. A legjobb MSE érték˝u egyed cél- és hibaértékei az egyes mintákra a pH probléma esetén BEA használatával

65

3.16. ábra. A legjobb MSE érték˝u egyed cél- és hibaértékei az egyes mintákra a pH probléma esetén BMA használatával

3.17. ábra. MSE alakulása a pH probléma esetén

66

3.18. ábra. MSE alakulása az ICT probléma esetén

A BEA által kapott optimális szabályok a pH problémára: R1 : Ha x1 = [0,059341; 0,28597; 0,40514; 0,7313] akkor y = [0,18589; 0,27486; 0,52066; 0,70602] R2 : Ha x1 = [0,38301; 0,39652; 0,41925; 0,76578] akkor y = [0,75291; 0,81982; 1,0024; 1,0372] R3 : Ha x1 = [0,051951; 0,36896; 0,56908; 0,70039] akkor y = [0,086398; 0,24551; 0,37881; 0,55217] A BMA által kapott optimális szabályok a pH problémára: R1 : Ha x1 = [0,14845; 0,4463; 0,64292; 0,67123] akkor y = [0,34233; 0,51977; 0,58192; 0,80283] R2 : Ha x1 = [−0,10635; 0,39081; 0,57236; 0,74319] akkor y = [−0,.4978; 0,21469; 0,31095; 0,45583] R3 : Ha x1 = [0,037302; 0,23532; 0,7653; 0,84955] akkor y = [0,6916; 0,87295; 1,0073; 1,3837] A BEA által kapott optimális szabályok az ICT problémára:

67

3.19. ábra. MSE alakulása a 6 változós probléma esetén

R1 : Ha x1 = [−0,027427; 0,013643; 0,027407; 0,27058] és x2 = [−0,072697; 0,1739; 0,43876; 0,88877] akkor y = [1,9286; 1,9644; 2,2663; 2,8419] R2 : Ha x1 = [0,023605; 0,82814; 0,83875; 0,91526] és x2 = [0,039025; 0,37465; 0,76291; 0,94203] akkor y = [0,083984; 0,599; 0,83059; 1,6556] R3 : Ha x1 = [0,0055574; 0,14652; 0,57419; 0,57709] és x2 = [−0,090017; 0,16984; 0,88549; 0,89452] akkor y = [1,5032; 2,4553; 2,6697; 3,2334] A BMA által kapott optimális szabályok az ICT problémára: R1 : Ha x1 = [−0,05557; 0,096831; 0,096831; 0,61764] és x2 = [−0,38741; 0,15828; 0,42377; 0,75708] akkor y = [1,9286; 2,5199; 2,841; 3,6312] R2 : Ha x1 = [−0,13014; 0,49711; 0,79235; 0,99016] és x2 = [0,30314; 0,72457; 0,76876; 1,114] akkor y = [0,01816; 0,38369; 1,0447; 1,3301] R3 : Ha x1 = [0,11687; 0,62462; 0,69643; 0,80899] és x2 = [−0,083077; 0,22048; 0,24413; 0,70602] akkor y = [1,0631; 1,6966; 1,9513; 2,1227] A BEA által kapott optimális szabályok a hat változós problémára:

68

R1 : Ha x1 = [3,2691; 3,7803; 4,5245; 4,9707] és x2 = [0,45688; 1,6764; 1,8366; 5,2796] és x3 = [−0,19167; 3,0767; 3,5534; 4,1727] és x4 = [0,098077; 0,32278; 0,55876; 0,5754] és x5 = [−0,028333; 0,40267; 0,99707; 1,0857] és x6 = [−0,0039945; 0,36039; 0,96744; 1,2172] akkor y = [3,77353; 8,49603; 10,0623; 16,1108] R2 : Ha x1 = [0,69229; 1,4028; 4,0655; 4,5688] és x2 = [1,3221; 2,2397; 3,2113; 3,9014] és x3 = [0,81474; 2,5275; 3,817; 4,7368] és x4 = [0,019088; 0,43315; 1,8155; 2,9786] és x5 = [0,80924; 0,90894; 1,2484; 2,6031] és x6 = [0,13657; 1,8188; 2,5877; 3,1743] akkor y = [3,22641; 11,4497; 12,7276; 15,884] R3 : Ha x1 = [0,1308; 1,6514; 2,2276; 4,9155] és x2 = [−0,46576; 0,13091; 3,1385; 4,4794] és x3 = [0,37358; 1,4722; 2,3596; 4,1944] és x4 = [0,0015921; 0,40295; 0,43801; 0,55955] és x5 = [0,067956; 0,10459; 0,44455; 0,85976] és x6 = [−0,014537; 0,76469; 0,93777; 1,1354] akkor y = [4,48621; 8,30233; 15,3879; 16,4223]

69

A BMA által kapott optimális szabályok a hat változós problémára: R1 : Ha x1 = [1,0195; 1,0823; 2,2247; 4,4724] és x2 = [0,45709; 1,3472; 3,4677; 4,4184] és x3 = [0,12743; 2,4164; 3,8943; 3,8966] és x4 = [−0,0092932; 2,9735; 3,6027; 4,597] és x5 = [0,35931; 0,81271; 0,93897; 3,6913] és x6 = [0,46638; 1,53; 4,2455; 4,4091] akkor y = [4,14193; 9,83104; 11,5653; 11,6497] R2 : Ha x1 = [0,29934; 0,42357; 4,3054; 5,1422] és x2 = [−0,45532; 2,787; 4,5064; 4,9697] és x3 = [0,4231; 0,77611; 1,9622; 3,4471] és x4 = [0,014251; 0,36256; 0,4216; 0,72609] és x5 = [0,27691; 0,556; 0,89273; 1,035] és x6 = [−0,027394; 0,061566; 0,20996; 0,41618] akkor y = [9,16778; 10,0454; 11,5467; 14,1264] R3 : Ha x1 = [−0,23359; 1,7672; 2,9245; 4,608] és x2 = [0,029085; 0,14005; 3,1426; 4,6243] és x3 = [0,33395; 0,62798; 2,8702; 4,0896] és x4 = [−0,013502; 0,042693; 0,51082; 0,77926] és x5 = [−0,040665; 0,041077; 0,92361; 1,0095] és x6 = [0,017653; 0,5352; 0,86467; 0,87896] akkor y = [3,52437; 7,38148; 10,069; 17,0449] 3.3.2.2. Változó szabályszám Az algoritmus másik, általánosabb változata automatikusan beállítja a szabálybázis optimális méretét is. Ezzel a változattal is végeztem szimulációkat, melynek eredményei a 3.10. és 3.11. táblázatban szerepelnek. A szimuláció paraméterei megegyeznek az el˝oz˝o szakaszban használt paraméterekkel, viszont a szabályszám nincs rögzítve. A megengedett maximális szabályszám 10. A táblázatokban a kapott szabályok száma is fel van t˝untetve. A kapott eredmények az el˝oz˝o szakaszhoz hasonlóan azt mutatják, hogy a BMA lényegesen jobb eredményt ad. Ebben a változatban a nagyobb dimenziószámú problémák esetén is viszonylag nagy a javulás, mert itt nem 3 szabály a megengedett maximum, hanem a szabályszám fokozatosan növekedve hozzáidomul a probléma bonyolultságához. A következ˝okben tézisek formájában fogalmazom meg az e fejezetben ismertetett új eredményeket. A tézissel kapcsolatos publikációim a hivatkozási listában megtalálhatók [12, 22, 58, 10]. 3. tézis. Bevezettem a bakteriális memetikus algoritmust, mely újszer˝u optimalizációs eljárás. Az eljárást Mamdani-típusú trapéz alakú tagsági függvényeket és COG defuzzifikációs 70

3.10. táblázat. Hiba átlagértékek változó szabályszám esetén hibadef. MSE MSRE MREP MSE-teszt MSRE-teszt MREP-teszt átlagos szabályszám

pH BEA 6,28 · 10−3 4,06 · 104 2,05 · 103 7,76 · 10−3 1,63 · 105 4,12 · 103 4,90

BMA 2,3 · 10−6 1,02 · 101 2,69 · 101 2,08 · 10−6 4,18 · 101 5,46 · 101 7,40

ICT BEA BMA 8,69 · 10−1 3,67 · 10−2 5,63 · 1013 1,80 · 1013 1,77 · 108 1,08 · 108 1,30 1,12 · 10−2 −1 1,92 · 10 1,62 · 10−3 2,56 · 101 3,04 2,20 5,00

6 dim. BEA BMA 3,21 1,29 6,20 · 10−2 3,17 · 10−2 1,86 · 101 1,21 · 101 4,29 2,22 6,50 · 10−2 3,37 · 10−2 1,91 · 101 1,32 · 101 6,50 7,30

3.11. táblázat. Legjobb egyedek változó szabályszám esetén hibadef. MSE MSRE MREP MSE-teszt MSRE-teszt MREP-teszt szabályszám

pH BEA 2,73 · 10−3 3,71 · 104 1,97 · 103 5,12 · 10−3 1,48 · 105 3,96 · 103 9

BMA 4,7 · 10−7 3,63 1,92 · 101 6,07 · 10−7 1,53 · 101 3,93 · 101 8

ICT BEA BMA 8,42 · 10−1 1,04 · 10−2 5,32 · 1013 7,09 · 1012 2,03 · 108 6,39 · 107 1,26 2,60 · 10−3 −1 1,87 · 10 3,74 · 10−4 1 2,34 · 10 1,48 2 5

71

6 dim. BEA BMA 2,07 4,10 · 10−1 4,78 · 10−2 9,56 · 10−3 1,59 · 101 7,06 2,66 9,9 · 10−1 4,28 · 10−2 1,5 · 10−2 1 1,47 · 10 9,28 7 10

módszert alkalmazó fuzzy szabályalapú rendszer tagsági függvényei paramétereinek meghatározására alkalmaztam, és szimulációs vizsgálatokkal megmutattam, hogy a megvizsgált esetek mindegyikében a módszer gyorsabbnak és hatékonyabbnak bizonyult, mint a bakteriális evolúciós algoritmus. E vizsgálatok és az elméleti jelleg˝u indikációk alapján várható, hogy módszerem el˝onyei más konkrét esetekben is megmutatkoznak. 3.1. altézis. Kifejlesztettem a bakteriális memetikus algoritmusnak nevezett újszer˝u optimalizációs eljárást. 3.2. altézis. Elkészítettem a bakteriális memetikus algoritmust megvalósító számítógépes eljárást, és az azt implementáló programot, mely Mamdani-típusú, trapéz alakú tagsági függvényeket használó fuzzy szabályalapú rendszer szabályainak optimalizálására alkalmas. 3.3. altézis. Az irodalomban használatos referenciaproblémák modellezésére szimulációs vizsgálatokat végeztem, melyek segítségével kimutattam, hogy a kifejlesztett bakteriális memetikus algoritmus (általában lényegesen) jobb eredményeket adott, mint a bakteriális evolúciós algoritmus.

3.4. Takagi-Sugeno-típusú fuzzy rendszerek paramétereinek optimalizálása Az el˝oz˝o tézisekben Mamdani-típusú fuzzy rendszerek identifikációjára javasoltam különböz˝o módszereket. A Mamdani-típusú modellek mellett a gyakorlatban széles körben alkalmazzák a 2.1.6. alfejezetben ismertetett Takagi-Sugeno fuzzy rendszereket is. Ezek számos el˝onnyel rendelkeznek a Mamdani-típusú rendszerekhez képest, így kedvez˝obb az univerzális approximációs tulajdonsága [99], gyorsabb a következtetés mechanizmusa, mivel itt nincs szükség defuzzifikációra, és lineáris hipersíkokat alkalmaz konzekvens függvényként. Mivel a modellt alkotó szabályok paramétereinek struktúrája az antecedens és a konzekvens részekben különbözik egymástól, ezért különböz˝oképpen is lehet o˝ ket kezelni. Az antecedens rész felépítése megegyezik a Mamdani-típusú rendszerekével, ezért erre a korábban megismert bakteriális és Levenberg-Marquardt módszerek kombinációját lehet alkalmazni. A lineáris szabálykonzekvens paraméterekre legkisebb négyzetes technikát célszer˝u alkalmazni, mert ez a lineáris paraméterek globális optimumát képes megtalálni a legkisebb négyzetek vonatkozásában, ezért el˝onyösebb olyan algoritmusokkal szemben, amelyek lokális minimumba „ragadnak”. A tézisben vizsgált több bemenet˝u egy kimenet˝u Takagi-Sugeno fuzzy modellek szerkezete a következ˝o: fˆ(x) = yˆ =

R X

li Ψi (x)

(3.26)

i=1

ahol (x1 , ..., xp ) a bemeneti vektor, yˆ a kimenet, és µi (x) Ψi (x) = PR j=1 µj (x) 72

(3.27)

pedig a normalizált tagsági függvények, amelyek valamely t-norma segítségével számított szabály tüzelési értékeket normalizálnak, azaz: p

µi (x) = T µij (xj )

(3.28)

j=1

ahol xj a megfigyelés vektorának j.-ik komponense, µij pedig az i.-ik szabály j.-ik antecedenséhez tartozó fuzzy halmaz. A T szimbólum a t-normát jelöli. Az li -k az R számú szabály ún. konzekvens függvényei, melyek definíciója a következ˝o: li = wi0 + wi1 x1 + wi2 x2 + ... + wip xp

(3.29)

Az antecedensben különféle alakú tagsági függvényeket szokásos használni. Például Gaussgörbe alakú függvényt, melynek képlete: − 21

µij (xj ) = e

(xj −cij )2 σ2 ij

ahol cij jelöli az i.-ik szabály j.-ik antecedenséhez tartozó Gauss-függvény középpontját, σij2 pedig a varianciáját. Az algebrai t-normát alkalmazva a Gauss függvények több el˝onyös tulajdonsággal rendelkeznek, így például mindenütt differenciálhatók. Az ilyen rendszerek a radiális bázisfüggvényeket használó neurális hálózatokkal ekvivalensek (2.3 alfejezet) [50, 60]. A nem korlátos tartó miatt interpolációs tulajdonságaik kedvez˝oek. A Gauss-görbe alakú tagsági függvényeknél azonban sokkal elterjedtebbek az el˝oz˝o tézisekben alkalmazott trapéz alakú tagsági függvények. Ezeket a korábban megszokott módon definiáljuk:  x −a j ij  , ha aij < xj < bij  bij −aij   1, ha bij ≤ xj < cij µij (xj ) = dij −xj  , ha cij ≤ xj < dij  dij −cij   0, egyébként ahol a töréspontokra fennáll, hogy aij ≤ bij ≤ cij ≤ dij . A trapéz alakú tagsági függvényekre a korábbiaknak megfelel˝oen a legelterjedtebb minimum t-normát fogom alkalmazni.

3.4.1. A javasolt algoritmus A cél a nemlineáris antecedens és a lineáris konzekvens paraméterek olyan hibrid és iteratív módon történ˝o tanítása, amellyel jó approximációt lehet biztosítani kezelhet˝o modellbonyolultság mellett. A javasolt algoritmus folyamatábrája a 3.20 ábrán látható. 3.4.1.1. A kódolási elrendezés A bakteriális algoritmusok számára szokásos kódolási elrendezés abban különbözik az 1. és a 3. tézisben alkalmazottól, hogy ott a teljes fuzzy szabálybázist belekódoltam egy baktériumba, a Takagi-Sugeno esetben azonban a baktérium csak a szabályok antecedenseinek fuzzy halmazait tartalmazza. Gauss függvények esetén a paraméterek az egyes görbék középpont és szélesség értékei, trapéz alakú függvények esetén pedig a trapézok töréspontjai. 73

Egy két bemenet˝u és egy kimenet˝u fuzzy rendszer kódolási elrendezését szemlélteti a 3.21 ábra, ahol a fels˝o ábra a trapéz alakú, az alsó pedig a Gauss-görbe alakú esetet demonstrálja. Mivel a konzekvens paramétereket legkisebb négyzetes technikával határozom meg, ezért ezek nincsenek a baktériumokba bekódolva. 3.4.1.2. Kezdeti populáció Miel˝ott az antecedens tanulás kezd˝odik, egy kezdeti baktériumpopulációt kell létrehozni (3.20. ábra). A populáció Negyed egyedb˝ol áll. Az egyedek fix hosszúságúak, a szabályok száma R. Összesen tehát p · Negyed · R tagsági függvény véletlenszer˝u létrehozása történik, ahol p az adott probléma bemeneteinek száma, és minden tagsági függvénynek négy illetve két paramétere van (trapéz illetve Gauss-görbe esetén). A kezdeti populáció kialakítása során az antecedenseket alkotó tagsági függvények inicializálásán kívül a konzekvens paraméterek valamely kezdeti beállítására is szükség van, mivel az antecedens tanulás során a modellek kiértékeléséhez szükség van a konzekvens részekre is. Az algoritmus során az antecedensek és a konzekvensek egymás után ciklikusan optimalizálódnak. A megállási feltétel teljesülése esetén még egy utolsó konzekvens tanítás következik az antecedensekben bekövetkezett esetleges változások kompenzálására. Megállási feltételként célszer˝u a maximális generációszám (Ngen ) elérésének választása. 3.4.1.3. Antecedens tanulás A szabályok antecedens részeinek tanítása a 3. tézisben megismert, Mamdani-típusú rendszerekre sikeresen alkalmazott bakteriális memetikus algoritmussal történik. A bakteriális mutációs és a génátadási operátorokat a 3.21. ábrához hasonló szerkezet˝u baktériumokra alkalmazom a korábbi tézisekben ismertetett módon. Az egyedek kiértékelésére az értekezésben több különböz˝o hibadefiníciót javasoltam már. Az átlagos négyzetes hibát (MSE) (3.24) fogom ebben az alfejezetben alkalmazni. Az eljárásban a bakteriális mutáció után és a génátadás el˝ott minden iterációs ciklusban a Levenberg-Marquardt (LM) módszer végrehajtása történik. Az LM módszert a 2.3.5 alfejezetben ismertettem, a 3.2. tézisben pedig meghatároztam a Jacobi-mátrixot a Mamdanitípusú, trapéz alakú tagsági függvényeket és COG defuzzifikációs módszert alkalmazó fuzzy modellekre. Ebben az alfejezetben Takagi-Sugeno-típusú rendszerekre határozom meg a Jacobi-mátrix elemeit, azaz a fuzzy modell kimenetének az antecedens paraméterek szerinti parciális deriváltjait. A J Jacobi-mátrix a következ˝o felépítés˝u: J[k] =

∂ yˆ(x(m) )[k] ∂par[k]

(3.30)

ahol a par vektor az antecedensek tagsági függvényeinek paramétereit tartalmazó vektor, x(m) jelöli az m. mintát a tanítókészletben, és k az iterációs változó. Gauss-görbe alakú tagsági függvények és szorzat típusú t-norma esetén a nemlineáris paraméterek szerinti parciális

74

3.20. ábra. Iteratív hibrid tanulási stratégia az antecedens és a konzekvens paraméterekre

3.21. ábra. Nemlineáris antecedens paraméterek kódolási elrendezése Takagi-Sugeno fuzzy rendszerekben

75

deriváltak a következ˝ok: R

X − 12 ∂ yˆ = e ∂ckl i=1

Pp

j=1

(xj −cij )2 σ2 ij

[(wk0 − wi0 ) + ... + (wkp − wip )xp ] · − 12

e

R

Pp

j=1

(xj −cij )2 σ2 ij

j=1

PR

2 σkl

X − 21 ∂ yˆ = e ∂σkl i=1

Pp

i=1

(xj −ckj )2 σ2 kj

− 12

e

Pp

(xl − ckl ) !2 (x −c )2 j

j=1

ij σ2 ij

[(wk0 − wi0 ) + ... + (wkp − wip )xp ] · − 12

e

3 σkl

Pp

j=1

PR

i=1

(xj −ckj )2 σ2 kj

− 12

e

Pp

(xl − ckl )2 !2 (x −c )2

j=1

j

ij σ2 ij

Trapéz alakú tagsági függvények és minimum típusú t-norma esetén pedig a parciális deriváltak µkl = minpj=1 µkj (xj ) teljesülése esetén a következ˝ok: PR p ∂ yˆ ∂µkl i=1 minj=1 (µij (xj ) [(wk0 − wi0 ) + ... + (wkp − wip )xp ]) = · 2 P ∂parkl ∂parkl R p min µ (x ) j j=1 ij i=1 ahol par az {a; b; c; d} paramétereket jelenti és ∂µkl xl − bkl , ha akl ≤ xl ≤ bkl , egyébként 0 = ∂akl (bkl − akl )2 ∂µkl akl − xl = , ha akl ≤ xl ≤ bkl , egyébként 0 ∂bkl (bkl − akl )2 ∂µkl dkl − xl = , ha ckl ≤ xl ≤ dkl , egyébként 0 ∂ckl (dkl − ckl )2 ∂µkl xl − ckl = , ha ckl ≤ xl ≤ dkl , egyébként 0 ∂dkl (dkl − ckl )2 Ha µkl 6= minpj=1 µkj (xj ), akkor az összes derivált 0. 3.4.1.4. Konzekvens tanulás A konzekvens tanítás a legkisebb négyzetek módszerével történik [73]. Ez azért lehetséges, mert a 3.29 összefüggésben szerepl˝o konzekvens paraméterek lineárisak, és ennek következtében az átlagos négyzetes hiba optimalizációjának feladatát analitikusan és globálisan lehet megoldani. A lineáris konzekvens tanításra alapvet˝oen kétféle lehet˝oség kínálkozik [103]: 76

• Globális tanulás: mind az R darab normalizált tagsági függvényt (mindegyik szabályhoz pontosan egy tartozik) együtt kezelünk egy regressziós mátrixban, így a w teljes paraméter vektort optimalizáljuk, mely az összes szabály összes lineáris konzekvens paraméterét tartalmazza. Az optimalizációs feladat a következ˝oképpen definiálható: F =

N X

(y(k) −

R X

li Ψi (x(k)))2 = min!

(3.31)

w

i=1

k=1

és a megoldást a w ˆ = (RT R)−1 RT y

(3.32)

adja, ahol R a regressziós mátrix, mely az ri (k) = [Ψi (x(k))x1 (k)Ψi (x(k)) . . . xp (k)Ψi (x(k))] regresszorokat tartalmazza mind az R szabályra és k = 1, . . . , N adatpontokra, ahol xi (k) az x sorvektor i.-ik oszlopa a k.-ik pontban. • Lokális tanulás: Minden szabályt külön kezelünk, és a szabályhoz tartozó lineáris konzekvens paramétereket súlyozott legkisebb négyzetes megközelítéssel optimalizáljuk, ahol a súlyok a normalizált tagsági függvényeket tartalmazzák. Az optimalizációs feladat az i.-ik szabályra a következ˝oképpen definiálható: Fi =

N X

Ψi (x(k))e2i (k) = min!

(3.33)

wi

k=1

ahol ei (k) = y(k) − yˆi (k) a lokális lineáris modell hibáját jelenti a k.-ik pontban. A megoldást a (3.34) wˆi = (RTi Qi Ri )−1 RTi Qi y kifejezés adja a Qi súlyozó mátrixszal:  Ψi (x(1)) 0 ... 0  0 Ψi (x(2)) ... 0  Qi =  .. .. .. ..  . . . . 0 0 ... Ψi (x(N ))

    

Különböz˝o analitikus és tapasztalati vizsgálatok alapján a lokális tanulás a globális tanulásnál számos szempontból megfelel˝obbnek bizonyult. A fontosabb szempontok például a numerikus stabilitás (mivel kisebb mátrixok inverzét kell számítani), a számítási teljesítmény és a konzekvens függvények (hipersíkok) átláthatósága. Ez utóbbi el˝ony annak köszönhet˝o, hogy a hipersíkok hozzásimulnak az approximáló felülethez [75]. Ez lehet˝ové teszi a lokális viselkedésbe való könny˝u bepillantást, és lehet˝oséget nyújt elfogadható hibaérték és konfidencia intervallum kinyerésére közvetlenül a hipersíkokból.

77

A stabil mátrixinverzió biztosítására egy α > 0 regularizációs paramétert szokás az optimalizációs függvénybe beépíteni: Fi =

N X

Ψi (x(k))e2i (k) + αwi T wi = min! wi

k=1

(3.35)

Az α regularizációs paraméter egyensúlyt teremt az adatokra való illeszkedés és a rosszul kondicionált RTi Qi Ri Hesse mátrix elkerülése között, a következ˝o megoldáshoz vezetve lokális tanulás esetén: (3.36) wˆi = (RTi Qi Ri + αI)−1 RTi Qi y ahol I a (p + 1) × (p + 1) méret˝u egységmátrix. Az összefüggés alapján nyilvánvaló, hogy nagy α érték numerikusan stabil eredményhez, ugyanakkor inkorrekt paraméter becsléshez vezet, mely nagy hibaértéket okoz. Ezért a gyakorlatban az i.-ik szabályhoz tartozó lineáris konzekvensek becslésére a következ˝o eljárást célszer˝u alkalmazni: 1. RTi Qi Ri kiszámítása 2. Az RTi Qi Ri mátrix kondíciószámának kiszámítása szinguláris érték felbontás segítségével a következo˝ összefüggés alapján: cond(RTi Qi Ri ) = λλmax , ahol min T λmin és λmax az Ri Qi Ri mátrix legkisebb és legnagyobb sajátértékét jelenti. 3. Ha cond(RTi Qi Ri ) > ε (valamely ε küszöbértékre), akkor a mátrix rosszul kon˝ dicionált, ezért a következo˝ a teendo: (a) α értékének megválasztása olymódon, hogy az RTi Qi Ri kondíciószáma kisebbé váljon mint az ε küszöb, de ne túl kicsire a fenti megfontolások miatt. Ez végrehajtható annak felhasználásával, hogy αI hozzáadása ˝ befolyásolja a kicsi sajátértékeket a követkeRTi Qi Ri mátrixhoz erosen , ezért ha zo˝ approximációs formulához vezetve: cond(RTi Qi Ri ) ≈ λmax α például ε/2 kondíció kívánatos, akkor α közelítheto˝ úgy, hogy α≈

2λmax ε

(b) A 3.36 szerinti legkisebb négyzetes számítás végrehajtása 4. Különben, a 3.34 szerinti súlyozott legkisebb négyzetes számítás elvégzése Az ε küszöb meghatározható korábbi, rosszul kondicionált mátrixokkal kapcsolatos tapasztalatokból, vagy egyszer˝uen lépésenkénti próbálgatásokkal annak alapján, hogy mi az a kondíció szint, amelynél az inverz számítás instabil eredményhez vezet.

3.4.2. Az algoritmus alkalmazása Az algoritmus tesztelésére a korábban megismert hatváltozós referenciaproblémát alkalmaztam. 78

A 3.12 táblázat az algoritmus által kapott eredményeket hasonlítja más, a MATLAB toolboxokban rendelkezésre álló módszerek által elért eredményekkel, nevezetesen az ANFIS-sal [49], az FMCLUST-tal [4] és a genfis2-vel [102], továbbá a genfis2 kiterjesztett változatával [74] és a FLEXFIS-sel [76], mely a genfis2 kiterjesztett változatának egy inkrementális fajtája, és a fuzzy modellt mintáról mintára építi fel. Ezen módszerek mindegyikének a leglényegesebb algoritmus paraméterek különböz˝o beállításaival végzett szimulációik alapján a 3.12 táblázatban a legjobb beállításokkal kapott eredmények szerepelnek. A külön antecedens és konzekvens paraméterek optimalizálására javasolt bakteriális memetikus illetve legkisebb négyzetes megközelítés kombinációjában a generációk száma 40, az egyedek száma 10. A bakteriális mutációban a klónok száma 8, a génátadások száma 4. A baktériumok hossza, azaz a fuzzy modell szabályainak száma 10, mely érték nem változik a futtatások során. A 3.12 táblázat alapján megállapítható, hogy a javasolt megközelítés jó megoldást nyújt a problémára. A többi módszerrel való összehasonlításból kit˝unik, hogy a legtöbb esetben alacsonyabb MSE értéket kapunk kevesebb szabállyal. A genfis 2 kiterjesztett változata alacsony MSE értéket ad ugyan, de ezt több szabály segítségével éri el. A javasolt módszer a benne alkalmazott operátorok miatt a legkisebb lehetséges megoldáshoz konvergál. Az algoritmus paramétereinek növelésével jobb eredmény érhet˝o el. A különböz˝o alakú tagsági függvényeket összehasonlítva a Gauss görbés változat ad kedvez˝obb eredményt. Ennek egyik oka a Gauss görbe alakú tagsági függvények végtelen, a teljes intervallumot lefed˝o tartója lehet. A másik ok, hogy a Levenberg-Marquardt lépésben a Gauss görbék gradiensei a trapéz alakúaknál több információt hordoznak, mert ez utóbbiak tagsági függvényei egy konstans részt is tartalmaznak, ami a gradiens szempontjából kevésbé hatékony. A következ˝okben tézisek formájában fogalmazom meg az e fejezetben ismertetett új eredményeket. A tézissel kapcsolatos publikációm a hivatkozási listában megtalálható [19]. 4. tézis. Új optimalizációs eljárást javasoltam Takagi-Sugeno-típusú trapéz illetve Gaussgörbe alakú tagsági függvényeket alkalmazó fuzzy rendszer paramétereinek meghatározására. Szimulációs vizsgálatokkal megmutattam, hogy a vizsgált esetekben a módszer az irodalomban ismert módszereknél kedvez˝obb tulajdonságú. E vizsgálatok és az elméleti jelleg˝u

3.12. táblázat. Takagi-Sugeno fuzzy modellek identifikálására kapott eredmények

Módszer FMCLUST ANFIS genfis2 genfis2 kit. FLEXFIS BMA-CL Gauss BMA-CL trapéz

MSE 1,31 0,71 1,38 0,68 1,09 1,06 1,33

79

Szabályok száma 10 64 18 14 17 10 10

indikációk alapján várható, hogy módszerem el˝onyei más konkrét esetekben is megmutatkoznak. 4.1. altézis. Meghatároztam a trapéz illetve Gauss-görbe alakú tagsági függvényeket használó Takagi-Sugeno-típusú fuzzy modellekhez tartozó, a kimenetnek a modell antecedens paraméterei szerinti parciális deriváltjait, és ezek alapján a teljes Jacobi-mátrixot. 4.2. altézis. Kifejlesztettem egy új, a Takagi-Sugeno fuzzy rendszerek antecedens és konzekvens paramétereinek egymástól független tanítására alkalmas számítógépes eljárást, és elkészítettem az azt implementáló programot. 4.3. altézis. Szimulációs vizsgálatokat végeztem, melyek segítségével kimutattam, hogy a kifejlesztett új eljárás kedvez˝obb eredményeket adott négyzetes középpel számítva, mint az irodalomból ismert más módszerek.

3.5. Bakteriális programozás alkalmazása B-spline neurális hálózatok identifikációjára Ahogy a 2.3.3. áttekint˝o fejezetben láttuk, a B-spline típusú neurális hálózatok tervezési folyamata 6 lépésb˝ol áll. Az utolsó két fázis nemlineáris legkisebb négyzetes problémának tekinthet˝o és ennélfogva komplett felügyelt tanuló algoritmust lehet a megoldására alkalmazni, Levenberg-Marquardt módszerrel a feladat kiválóan megoldható [91]. Az els˝o négy tervezési fázis összetett kombinatorikai probléma, melynek megoldására különböz˝o konstruktív algoritmusokat javasoltak, például az ASMOD (Adaptive Spline Modelling of Observed Data) algoritmust [101], a MARS (Multivariate Adaptive Regression Splines) algoritmust [40], és a LOLIMOT (Local Linear Model Trees) algoritmust [84]. Ezeket követ˝oen 2003-ban alkalmazták a genetikus programozást is a feladat megoldására, mellyel az el˝obbi módszereknél kedvez˝obb eredményt sikerült elérni [26]. Ebben a fejezetben a bakteriális programozás alkalmazását javaslom a probléma megoldására, és bemutatom, hogy ez az eljárás az összes korábbi eljárásnál kedvez˝obb eredményt ad.

3.5.1. A javasolt módszer A bakteriális programozás a genetikus programozás (2.2.2. fejezet) és a bakteriális evolúciós algoritmusok ötvözéséb˝ol keletkezik. Az egyedek csakúgy mint a genetikus programozás esetén kifejezésfával adottak, viszont a bakteriális programozás az evolúciós folyamatban nem az irodalomból ismert genetikus operátorokat (keresztezés, mutáció), hanem a bakteriális algoritmus operátorait (bakteriális mutáció, génátadás) használja. 3.5.1.1. A kódolási elrendezés A B-spline neurális hálózatok hierarchikus struktúrája jobban ábrázolható fával, mint egy kromoszómába kódolt stringgel. Emiatt a kromoszómát használó genetikus illetve bakteriális algoritmus helyett a genetikus programozásban megismert fastruktúra alkalmasabb 80

3.22. ábra. Példa B-spline neurális hálózat kifejezésfájára

a hálózat struktúrájának ábrázolására, ezért a hálózat identifikációjára javaslom a bakteriális programozást. A 3.22. ábrán egy példa kifejezésfa látható B-spline neurális hálózatra [26]. A B-spline hálózat tervezésekor a következ˝o m˝uveletek végrehajtására lehet szükség: almodellek összeadására (+), kisebb dimenziójú almodellekb˝ol nagyobb dimenziójú almodellek létrehozására (×), és nagyobb dimenziójú almodell szétbontására kisebb dimenziójú almodellekre (/). Ezek a m˝uveletek alkotják a B-spline hálózatra definiált függvények halmazát, melyek a kifejezésfa függvény csomópontjaiban el˝ofordulhatnak. A fa terminális szimbólumai nem csak a dimenzió azonosítóját tartalmazzák, hanem az adott dimenzióhoz tartozó változón definiált spline görbék rendjét, az azokhoz tartozó bels˝o csomópontok számát illetve a bels˝o csomópontok elhelyezkedését is. A 3.22. ábrán látható hálózat esetén például a fa bal széls˝o levele azt jelzi, hogy a bemeneti változó a levélhez tartozó almodell esetén 3, a spline görbe rendje 1 és két bels˝o csomópont van a változóhoz tartozó koordinátatengelyen, amelyek helye a 0 és a 0,4-es pozícióban van. Az ábrán szerepl˝o modell kimenete 3 almodell kimenetének összeadásaként számítható, a következ˝o módon: y(X) = f (X3 × X2 ) + f (X1 × X2 ) + f (X1 ), ahol Xi az i. bemeneti változót jelöli, azaz a modell 2 kétváltozós és 1 egyváltozós almodell összegeként adódik. A függvényeket és terminálisokat körültekint˝oen kell definiálni, hogy bármilyen értéket kaphassanak argumentumként, amit a lejjebb található részfák függvényei és terminálisai visszaadnak. Ha egy fához tartozó modell komplexitása nagyobb, mint a tanítóhalmazban lév˝o minták száma, akkor az egyed törlése helyett érdemes inkább a struktúráján olyan változtatást eszközölni, hogy az egyed továbbra is részt vehessen az evolúciós folyamatban. Annak érde81

kében, hogy érvényes egyedet kapjunk, az egyed kiértékelése során áttekintjük a kifejezésfát, és minden csomópontban kiértékeljük a csomópont alatti részfa komplexitását. Ha ez az érték nagyobb, mint a minták száma, akkor a komplexitást a következ˝oképpen csökkentjük: a tenzor szorzat (×) függvényt az összeadás (+) függvénnyel helyettesítjük, ha a csomópont tenzor-szorzatfüggvény; ha pedig a csomópont összeadásfüggvény, akkor azt a csomópont alatt található legkisebb komplexitású ághoz tartozó részfával helyettesítjük. Ezt a két lépést ismételjük addig, amíg az egyed szintaktikailag érvényes nem lesz, azaz amíg olyan fát nem reprezentál, amelyik a feladat szempontjából értelmezhet˝o. Ezen lépések során néhány terminális és függvény csomópont elt˝unhet a fából. 3.5.1.2. Az evolúciós folyamat Az evolúciós folyamat megegyezik a bakteriális evolúciós algoritmusnál alkalmazottal, itt azonban az egyedek fagráfokat jelentenek. A kezdeti populációt véletlenszer˝uen létrehozott fák alkotják. Az egyedek száma Negyed . Ezután következik az evolúciós ciklus, mely a bakteriális mutációt és a génátadást alkalmazza. A maximális generációszám (Ngen ) elérésekor a folyamat véget ér. 3.5.1.3. Bakteriális mutáció A bakteriális mutációt a populáció minden egyedére egyenként alkalmazzuk. Az egyedet Nkl´on példányban lemásoljuk (klónok). A baktérium egy véletlenszer˝uen kiválasztott részét megváltoztatjuk az így nyert klónokban (mutáció), az eredeti baktériumban viszont nem. Jelen esetben azonban az egyedek kétféle típusú csomópontot tartalmaznak, ezért a klónokban kétféle mutáció megengedett. Az egyik a függvény mutáció, amelynek során a kijelölt függvény-csomóponthoz tartozó részfát egy új, véletlenszer˝uen létrehozott részfával cseréljük le. A másik a terminális mutáció, amelynél az adott terminálist változtatjuk meg valamilyen módon. A klónokban végrehajtott mutáció után az összes klónt és az eredeti baktériumot kiértékeljük, és a legjobb közülük a megváltoztatott részt a többi egyednek adja át, illetve, ha az eredeti baktérium maradt a legjobb, akkor ez adja át a szóban forgó részt a klónoknak. Ezt a folyamatot, mely a mutáció – kiértékelés – kiválasztás – behelyettesítés lépéssorozatot jelenti, ismételjük addig, amíg a kifejezésfa mindegyik részét egyszer ki nem választottuk. Ha a fa egy részének mutációja során egy új részfa keletkezett, annak csomópontjait ezen a lépéssorozatot belül már nem választjuk ki többször mutációra (csak majd a következ˝o generációban). Amikor az egész fával végeztünk, kiválasztjuk a legjobb egyedet, a többi Nkl´on egyedet pedig megszüntetjük. A 3.23. ábra a függvény típusú mutációt illusztrálja. Ilyenkor a kiválasztott függvénycsomópont alatt új részfa jön létre. A 3.24. ábrán a terminális típusú mutáció látható, mely a terminálisban szerepl˝o információkat változtatja meg véletlenszer˝uen. B-spline neurális hálózatok esetén a terminális mutáció a következ˝o hatféle lehet: 1. a teljes terminális csomópont lecserélése 2. a változó azonosítójának megváltoztatása 3. a spline görbe rendjének megváltoztatása 82

3.23. ábra. A függvény mutáció m˝uvelete

3.24. ábra. A terminális mutáció m˝uvelete

4. egy bels˝o csomópont áthelyezése 5. N véletlenszer˝u bels˝o csomópont hozzáadása (N = 5) 6. N bels˝o csomópont eltávolítása (csomópontok hiánya esetén nincs végrehajtás) A terminális mutációs arányt a pmut−terminal = [%1, %2, %3, %4, %5, %6] vektorral definiáljuk, ahol %i az i. típusú terminális mutáció valószín˝uségét jelenti. 3.5.1.4. Génátadás A génátadás a korábban megismert módon zajlik. A populáció kettéosztása után a „jó” egyedek közül kiválasztunk egy forrásbaktériumot, és a „rosszak” közül egy célbaktériumot. A forrásbaktérium fájából kiválasztunk véletlenszer˝uen egy részfát, és ez a részfa felülírja a célbaktérium egy véletlenszer˝uen kiválasztott részfáját. A részfa bármekkora lehet, akár mindössze egyetlen terminális csomópontot tartalmazó részfa is. A génátadási folyamat a 3.25. ábrán látható. Ezt a három lépésb˝ol álló folyamatot (populáció kettéosztás; forrás- és célbaktérium kiválasztás; génátadás) Ninf -szer ismételjük. 83

3.25. ábra. A génátadás m˝uvelete

3.5.1.5. A baktériumok kiértékelése A baktériumokat többféle különböz˝o kritérium alapján lehet kiértékelni. Az el˝oz˝o fejezetekben bemutattam néhányat ezek közül. Legmegfelel˝obb jelen esetben a 3.3. fejezetben alkalmazott Bayes-i információs kritérium, mely az egyed által adott hibán kívül a komplexitást is figyelembe veszi. Ahogy már korábban is szerepelt (3.25) a következ˝oképpen számítható: BIC = m · ln(M SE) + n · ln(m), (3.37) ahol m a tanítóminták száma, n pedig a modell komplexitása, azaz a bázisfüggvények száma.

3.5.2. A módszer alkalmazása Az új módszer kifejlesztése során elkészítettem az azt implementáló programot. Szimulációs vizsgálatokat hajtottam végre, amelyekben a kifejlesztett új eljárást hasonlítottam össze a genetikus programozással az irodalomban található referenciaproblémákon. Az el˝oz˝o fejezetekben megismert referenciaproblémákat alkalmaztam. 3.5.2.1. A bakteriális programozás paramétereinek meghatározása Az els˝o szimuláció célja annak meghatározása, hogy mik a bakteriális programozás legmegfelel˝obb paraméterértékei. A módszerben használt paraméterek az egyedek száma (Negyed ), a klónok száma (Nkl´on ), az infekciók száma (Ninf ) és a generációk száma (Ngen ). Az optimális paraméter értékek meghatározása a pH probléma alapján történik.

84

3.13. táblázat. A BIC, MSE, MSRE, és MREP átlagértékei és a modellbonyolultság az Nkl´on paraméter értékét változtatva Nkl´on BIC MSE MSRE MREP komplexitás

5 −1695,9 3,6 · 10−8 5,8 · 10−2 1,2 57,8

10 −1834,3 6,9 · 10−9 2,9 · 10−3 2,7 · 10−1 73

15 −1913 2,3 · 10−9 1,2 · 10−3 1,7 · 10−1 81

3.14. táblázat. A BIC, MSE, MSRE, és MREP átlagértékei és a modellbonyolultság az Ninf paraméter értékét változtatva Ninf BIC MSE MSRE MREP komplexitás

5 −1823,9 8,4 · 10−9 7,1 · 10−3 4,1 · 10−1 75,9

10 −1792,8 4,2 · 10−8 7,4 · 10−2 9,1 · 10−1 76,2

15 −1934,3 2,2 · 10−9 3,4 · 10−3 3,3 · 10−1 87,4

A szimuláció 10-szer futott le, melyek során a Bayes-i információs kritérium (BIC), az átlagos négyzetes hiba (MSE), az átlagos négyzetes relatív hiba (MSRE), és az átlagos relatív százalékos hiba (MREP) értékek kerültek meghatározásra. A relatív hibakritériumok hasznosak lehetnek akkor, amikor a kimenet széles tartományt fog át, mert ezek a kritériumok minden egyes mintához tartozó hibát a modell kimenetéhez viszonyítva vesznek figyelembe. Mindemellett viszont a BIC és MSE értékek fontosabbak mert az egyedek az evolúciós folyamat során a BIC kritérium alapján értékel˝odnek ki, és a BIC az MSE kritériumot foglalja magába, nem pedig a relatív hibát. A példában az egyedek száma és a generációk száma is 20. El˝oször a klónok száma állítható, 5, 10 és 15-ös értéket vizsgálva, az infekciók száma 5-re rögzített. A második esetben az infekciók száma állítható 5, 10 és 15-ös értéket vizsgálva, 8 klónt használva. A 3.13. táblázatban közölt eredmények azt mutatják, hogy minél több a klón, annál jobb a kimenet pontossága. Viszont több klón több számítási költséget is jelent. Ezért a cél ilyenkor az optimális egyensúly megtalálása, és a túl sok klón használatának elkerülése. A 3.14. táblázatot elemezve megállapítható, hogy az itt kapott eredmények nem különböznek annyira egymástól, mint az el˝oz˝o esetben, a klónok számának meghatározásakor. Több infekció alkalmazása a populációt lokális optimumba vezetheti a korai konvergencia miatt. Kisebb érték˝u Ninf jobb eredményt adhat és kevesebb számítási teljesítményt igényel.

85

3.15. táblázat. A két módszerben (genetikus és bakteriális) használt paraméter értékek Paraméterek Nkl´on Ninf Negyed Ngen keresztezési arány mutációs arány

GP 160 20 a populáció 50%-a 0,8

BP 8 5 20 20 -

3.5.2.2. A bakteriális és genetikus programozás összehasonlítása Ennek a résznek a célja, hogy a genetikus programozás (GP) és a bakteriális programozás (BP) által referenciaproblémák megoldására kapott eredményeket bemutassa. Ahogy az el˝oz˝o részben, itt is 10 futtatás történik, és a BIC, MSE, MSRE és MREP értékekre kapott átlageredmények képezik a vizsgálódás tárgyát. A tanítóminták száma a pH problémánál 101, az ICT-nél 110, a 6 változós függvénynél pedig 200. Annak érdekében, hogy a két módszer esetén azonos legyen a számítási-komplexitás, és ezáltal az összehasonlítás igazságos legyen, az algoritmusok a 3.15. táblázatban szerepl˝o paraméter értékeket használják. A terminális mutációs arány mindkét algoritmus esetén: pmut−terminal = [5%, 10%, 5%, 10%, 60%, 10%]. A paraméter-értékek táblázata alapján látható, hogy a populáció a BP módszer esetén sokkal kisebb. A 8 klón használata viszont hasonló számítási komplexitást jelent, mint a GP módszer esetén alkalmazott 160 egyedb˝ol álló populáció, mivel a bakteriális mutációban mind a 20 baktériumnak 8 klónja jön létre. A BP megközelítés egyik el˝onye, hogy nem szükséges ilyen nagy populációt kezelni; 20 baktérium evolúciós folyamata elég a két módszer összehasonlításához. A 3.16. táblázatban a pH problémára kapott átlagértékek láthatók. Ebben az esetben a GP és a BP megközelítés hasonló eredményt ad. Viszont a BP átlagban kisebb komplexitású modellt hoz létre. A 3.17. táblázatban a BP és a GP által létrehozott legjobb egyedhez tartozó modell struktúrája látható. Ezekb˝ol az eredményekb˝ol megállapítható, hogy a két módszer hasonló végs˝o modelleket hozott létre. Ennek oka, hogy a pH probléma egy egyváltozós feladat, ezért a B-spline neurális hálózat struktúrája nem túl bonyolult, és ennélfogva mindkét módszer könnyen megoldja ezt a modelltervezési feladatot. Az ICT problémára kapott eredmények a 3.18. és a 3.19. táblázatban találhatók. A BP jobb eredményt ad nemcsak az átlagértékekre vonatkozóan, hanem a legjobb egyedet (a legkisebb BIC érték˝u egyedet) vizsgálva is. Bár a GP a legjobb egyedre kisebb relatív hibaértékeket ad, az evolúciós folyamatot mindkét algoritmus esetén a BIC kritérium vezérli (ami az MSE-t is magába foglalja), ezért a BIC és MSE kritériumok fontosabbak. Ezen kritériumok alapján a BP jobb eredményt nyújt. A bakteriális megközelítés f˝o el˝onye a 6 változós problémára kapott eredmények elemzésekor válik világossá. Ezek az eredmények azt mutatják, hogy a bakteriális módszer jó 86

3.16. táblázat. A BIC, MSE, MSRE, és MREP átlagértékei és a modellbonyolultság a pH problémára

BIC MSE MSRE MREP komplexitás

GP −1784,6 1,1 · 10−8 1,3 · 10−2 6,1 · 10−1 82,6

BP −1786,7 1,3 · 10−8 2,6 · 10−2 6,9 · 10−1 72,4

3.17. táblázat. Az összes futtatás során talált legkisebb BIC érték˝u egyedhez tartozó modellstruktúra a pH probléma esetén

almodellek komplexitás BIC MSE MSRE MREP |W |

GP (1) 33 −1903,1 1,4 · 10−9 2,7 · 10−3 5,3 · 10−1 3,3

BP (1) 40 −1874,3 1,8 · 10−9 7,5 · 10−5 1,0 · 10−1 3,6

3.18. táblázat. A BIC, MSE, MSRE, és MREP átlagértékei és a modellbonyolultság az ICT problémára

BIC MSE MSRE MREP komplexitás

GP −1344,4 2,5 · 10−7 1,6 · 105 1331,6 33,4

87

BP −1539,7 8,6 · 10−8 2,1 · 103 125,8 31,7

3.19. táblázat. Az összes futtatás során talált legkisebb BIC érték˝u egyedhez tartozó modellstruktúra az ICT probléma esetén

almodellek komplexitás BIC MSE MSRE MREP |W |

GP (1 × 2)(1)(2) 106 −1533,9 1,3 · 10−8 1,6 · 10−7 1,3 · 10−2 686,7

BP (2 × 1)(1) 106 −2048,3 8,8 · 10−11 22,45 79,7 2,6 · 107

3.20. táblázat. A BIC, MSE, MSRE, és MREP átlagértékei és a modellbonyolultság a 6 változós problémára

BIC MSE MSRE MREP komplexitás

GP −380,1 2,0 · 10−1 2,1 · 10−3 2,1 38,8

BP −552,9 2,7 · 10−2 5,2 · 10−4 0,98 44,6

teljesítményt nyújt nagyobb dimenziószámú problémák esetén. A 3.20. és a 3.21. táblázat alapján látható, hogy a BP jobb, mint a GP, mind az átlagértékek, mind pedig a legjobb egyedek vonatkozásában. A 3.26. és a 3.27. ábrán a megkívánt kimenet (cél) és a hiba értékei láthatók az egyes mintákra vonatkozóan mindkét módszer által adott legjobb egyedet tekintve. Az ábrákat összehasonlítva megállapítható, hogy a bakteriális technika kisebb hibát ad. 3.5.2.3. Statisztikai elemzés Az el˝oz˝oekben bemutatott szimulációk alapján megállapítható, hogy a bakteriális programozás hatékonyabb, mint a genetikus programozás. Ennek oka a bakteriális megközelítésben alkalmazott operátorok természetének különböz˝osége. A baktériumok a keresési tér nagyobb részét képesek felfedezni a bakteriális mutációban alkalmazott hatékony klónok segítségével. Ez a rész néhány hipotézis tesztet mutat be, amelyek a 3.22. táblázatban találhatók meg. Feltéve, hogy a hipotézis elvetésének szignifikancia szintje α = 5%, a nullhipotézisek konfidencia aránya 95%-ra adódik. Az eredmények egyenl˝oségének becslésére az egyik legnépszer˝ubb kétmintás módszert, a Mann-Whitney tesztet alkalmaztam [78]. Ez a teszt annak valószín˝uségét mutatja (p), hogy két különböz˝o algoritmusból azonos érték˝u mintákat nyerünk. Annak kiderítésére, 88

3.21. táblázat. Az összes futtatás során talált legkisebb BIC érték˝u egyedhez tartozó modellstruktúra a 6 változós probléma esetén

almodellek komplexitás BIC MSE MSRE MREP |W |

GP (5)(4)(2) (3 × 4)(5 × 3 × 6) (3 × 1) 98 −593,2 3,8 · 10−3 7,3 · 10−5 6,6 · 10−1 423,8

BP (6 × 5)(5 × 2) (6 × 1)(3 × 6) (3 × 4)(1) 156 −702 4,8 · 10−4 1,2 · 10−5 2,4 · 10−1 128,4

3.26. ábra. Cél- és hibaértékek a 6 változós problémára GP használatával

89

3.27. ábra. Cél- és hibaértékek a 6 változós problémára BP használatával

hogy a két algoritmusnak egyenl˝o mediánja van-e, a medián teszt készíthet˝o el. Adott futásszám és az egyik algoritmus alapján kapott mintákból létrehozott rendezett összesítés esetén a medián teszt annak valószín˝uségére ad véleményt, hogy két populáció közötti medián különböz˝o, kisebb vagy nagyobb-e. A 3.22. táblázatban mutatott eredmények azt jelzik, hogy a két algoritmus hasonló teljesítmény˝u amikor az egyváltozós pH problémára keresnek megoldást, hiszen p értéke magas. Amikor viszont többváltozós feladatokat kezelnek, akkor látható, hogy lecsökken annak a valószín˝usége, hogy hasonló eredményeket adnak, mivel a p érték alacsonyabb, mint az 5%-os elvetési határ. Ezenkívül a medián érték a bakteriális esetben alacsonyabb, ami azt jelenti, hogy a legtöbb esetben ez a módszer jobb kiértékelési eredményt ad. A 3.28. 3.29. és 3.30. ábra mindegyik problémára, mindkét

3.22. táblázat. A BP-re és a GP-re vonatkozó statisztikai következmények a Mann-Whitney és a medián teszt módszerekkel Probléma pH

Mann-Whitney teszt (p érték) 0,7624

ICT

0,0156

6 változós függvény

0,00194

Medián teszt a BP-re alacsonyabb medián, mint a GP-re a BP-re alacsonyabb medián, mint a GP-re a BP-re alacsonyabb medián, mint a GP-re

90

3.28. ábra. Tapasztalati valószín˝uségi eloszlásfüggvény a pH problémára

3.29. ábra. Tapasztalati valószín˝uségi eloszlásfüggvény az ICT problémára

3.30. ábra. Tapasztalati valószín˝uségi eloszlásfüggvény a 6 változós problémára

91

módszerrel nyert tapasztalati valószín˝uségi eloszlásfüggvényeket mutat. Ezen ábrák alapján ugyanaz a következtetés vonható le, ami az el˝oz˝o részekben. Az egyváltozós feladatra a két megközelítés hasonló eredményt ad. A kétváltozós ICT problémára a legjobb egyed BIC értékei kb. −2050 és −1750 között vannak a BP-vel, és kb. −1500 és −1420 között a GP-vel, ami azt jelenti, hogy a GP módszer gyengébb eredményt ad, mint a bakteriális technika. A 3.30. ábra a 6 változós problémára vonatkozik. Míg a GP esetben a legjobb egyed BIC értékei csak kb. −600 és −500 között vannak, addig a BP által létrehozott legjobb egyed BIC értékei kb. −700 és −630 közöttiek. A következ˝okben tézisek formájában fogalmazom meg az e fejezetben ismertetett új eredményeket. A tézissel kapcsolatos publikációim a hivatkozási listában megtalálhatók [23, 24, 25, 13]. 5. tézis. Bevezettem egy új optimalizációs módszert, a bakteriális programozást. A módszert B-spline típusú neurális hálózatok struktúrájának optimális kialakítására alkalmaztam. Konkrét szimulációs vizsgálatok elvégzésével azt találtam, hogy a módszer jobb eredményt adott az irodalomban megismert más módszereknél. 5.1. altézis. Kifejlesztettem a bakteriális programozási eljárást. 5.2. altézis. Elkészítettem a B-spline típusú neurális hálózatok struktúrájának optimalizálására alkalmas bakteriális programozást megvalósító számítógépes implementációt. 5.3. altézis. Szimulációs vizsgálatokat végeztem az irodalomban használatos referenciaproblémák modellezésére, melyek segítségével kimutattam, hogy a kifejlesztett bakteriális programozás minden kritérium szerint jobb eredményeket adott, mint a genetikus programozás.

3.6. Feature1 kiválasztás bakteriális evolúciós algoritmusokkal Ahogy korábban láttuk, minták alapján történ˝o regressziós modell kialakítására számos módszer létezik. Az eddig tárgyalt fuzzy szabályalapú rendszereken és neurális hálózatokon kívül megemlíthet˝ok például a statisztikai alapú regresszió és a regressziós fa módszerek [20, 88]. Mindegyik módszernek közös problémája azonban, hogy a modellek bonyolultsága gyorsan növekszik ahogy n˝o a problémában szerepl˝o változók, ún. feature-ök száma. Ez két f˝o problémát okoz: egyrészr˝ol néhány feature-nek kis szerepe lehet, viszont ha nagy a varianciája akkor félrevezetheti a regressziós módszert. Másrészr˝ol viszont a nagyszámú feature csökkenti az értelmezhet˝oséget, mivel a fontos tartalmat elnyomhatják a lényegtelen featureök. Továbbá mérések esetén a mérés gyakran id˝oigényes és költséges feladat, ennélfogva a mérések (feature-ök) csökkentése fontos cél a tervezés során. Dimenzió-redukció vagy feature kiválasztás használható az eredeti állapottér dimenziószámának csökkentésére (azaz a vizsgált feature-ök számának csökkentésére). Amíg az olyan 1

Kísérletet tettem a „feature” szónak megfelel˝o magyar kifejezés megtalálására. Felmerültek például a „lényeges változó” és a „lényeges jellemz˝o” elnevezések. Ezek egyike sem adja azonban teljesen vissza az angol „feature” szakkifejezés pontos jelentéstartalmát. Ezért az értekezésben az angol „feature” kifejezést használom.

92

dimenziószám redukciós módszerek mint a f˝o komponens analízis (Principal Component Analysis (PCA) [9] projekciós technikákat használnak, amelyek gyakran akadályozzák az eredményként kapott modell értelmezését, addig a feature kiválasztó módszerek célja az eredeti feature halmazból a legrelevánsabb feature-ök azonosítása [43, 71]. Célszer˝u a következ˝o matematikai alapdefiníciókat rögzíteni: Legyen U = X × Y az alaphalmaz, ahol X az n-dimenziós bemeneti tér és Y az egydimenziós kimeneti tér. A tanulási folyamat célja annak az f : X 7→ Y függvénynek a megtalálása, amely a bemeneti és a kimeneti tér közötti relációt a legjobban modellezi. Az f függvény S ⊂ X × Y tanítóminták alapján jön létre az E(f, S) hibamérték minimalizálásával. Az egyik leggyakrabban használt mérték a korábbi fejezetekben már alkalmazott átlagos négyzetes hiba: E(f, S) =

1 X |S|


2 f (x) − y .

(x,y)∈S

A bemeneti tér dimenziószám-növekedésével növekszik ennek a tanulási folyamatnak a komplexitása is. Ha olyan feature-ök is szerepelnek a modellben, amelyek csak kicsi hatással vannak a kimeneti térre, vagy egyáltalán nincsenek arra hatással, akkor az eredményként kapott f függvény hajlamos lehet a tanító adatokra való túlilleszkedésre. Bár számos módszer javasolt ennek a problémának a legy˝ozésére, gyakran hatásosabb el˝ore csökkenteni a feature-ök számát. A feature kiválasztási probléma úgy írható le, mint egy optimalizálási feladat, amelynek célja az optimális m feature azonosítása a rendelkezésre álló n feature közül. Az eredmény¯ m-dimenziós ként kapott m feature alapján következik a f¯ függvény számítása, amely az X bemeneti teret az Y kimeneti térre képezi. A feature kiválasztási feladat megoldásra többféle megközelítés ismert. Az egyik technika fekete dobozként felhasználja a regressziós modellt a változók megfelel˝o részhalmazának kinyerésére aszerint, hogy a regressziós modell milyen eredményt ad az adott változókészlettel. Ezt nevezik wrapper módszernek. A másik fajta megközelítés célja a legrelevánsabb feature-k azonosítása még az aktuális tanulási fázis el˝ott. Ennek neve filter módszer, mely a wrapper módszerrel ellentétben nem alkalmas a bemeneti feature-k közötti lényeges kombinációk felismerésére. A wrapper megközelítést alkalmazom ebben a fejezetben a feature kiválasztási feladatra. Mivel az optimális feature halmaz megtalálása ismert NP-nehéz probléma [2], ezért célszer˝u intelligens keresési stratégiát alkalmazni a megoldására. Ezek általában csak kvázioptimális megoldást adnak, melyek azonban jól közelítik az optimumot. A problémát érdemes bakteriális megközelítéssel megoldani, mely a kombinatorikailag bonyolultabb feladatokra is általában jó közelít˝o megoldást kínál.

3.6.1. A javasolt algoritmus Az algoritmusnak kétféle változatát javaslom. Az els˝o változatban a cél el˝ore definiált számú feature kiválasztása, a második változatban viszont nem adott el˝ore a kiválasztandó feature-ök száma, azt is az algoritmusnak kell optimalizálnia.

93

3.6.1.1. A kódolási elrendezés Mint a korábbi fejezetekben már tárgyaltam, a bakteriális evolúciós algoritmusokban egy baktérium az adott optimalizálási probléma egy megoldását jelenti. El˝oször azt határozzuk meg, hogy a feladat egy megoldása hogyan kerül belekódolásra valamely ξi , i ∈ I baktériumba. A cél m feature kiválasztása egy n elem˝u feature készletb˝ol, ahol nyilván (m ≤ n), a baktérium ezért olyan egész számokból álló vektor lesz, ahol az egészek a feature-ök azonosítói, azaz ξi = {ξi1 , . . . , ξim }, 1 ≤ ξik ≤ n, és k 6= l-re ξik 6= ξil . Az algoritmus második változatában a baktérium hossza nem el˝ore meghatározott, mivel az optimális m érték megtalálása is cél. 3.6.1.2. A baktériumok kiértékelése Az ξi baktériumot a φ(ξi ) kiértékelési függvény segítségével értékeljük ki, melynek megválasztása az adott problémától függ. A feature kiválasztási feladat esetén az fi regressziós modell kiszámításához a ξi baktériumba kódolt feature-öket és az S tanító mintahalmazt használjuk a következ˝o összefüggés alapján: fi (x) : Xξi1 × . . . × Xξim 7→ Y. A kiértékelési függvényt ennek alapján számítjuk a regressziós modell, valamely T ⊂ X ×Y tesztelési mintakészleten vett átlagos négyzetes hibájaként: φ(ξi ) = E(fi , T ). A módszer második változatában ez az összefüggés kiegészül a baktérium hosszával: φ(ξi ) =

1 X |T |

fi (x) − y

(x,y)∈T


2

+β

l(ξi ) , L

ahol l(ξi ) a ξi baktérium hossza, L a maximálisan megengedett baktériumhossz és β egy a pontosság és komplexitás közötti trade-off paraméter. 3.6.1.3. Az evolúciós folyamat Az evolúciós folyamat a kezdeti populáció véletlenszer˝u létrehozásával kezd˝odik, mely Negyed számú {ξi , i ∈ I} baktériumot tartalmaz (I = {1, . . . , Negyed }). A 3.31 ábrán a ξi baktérium látható n = 50 és m = 5 esetén. A második változatban a baktérium kezdeti hossza is véletlenszer˝uen meghatározott, 1 és L közötti érték. Az ábrán a baktérium hossza 5. Ezután következik az evolúciós ciklus, mely a bakteriális mutációt és a génátadást alkalmazza. A maximális generációszám (Ngen ) elérésekor a folyamat véget ér. Véget ér akkor is, ha a populációt alkotó összes baktérium egymással megegyezik.

94

44 17 36

2

Ξ1i

Ξ4i Ξ5i

Ξ2i

Ξ3i

7

3.31. ábra. Minta baktérium

3.6.1.4. Bakteriális mutáció A bakteriális mutációt a populáció minden ξi , i ∈ I egyedére egyesével alkalmazzuk. El˝oször az egyedet Nkl´on példányban lemásoljuk. ξi,j = ξi ,

∀j : 1 ≤ j ≤ Nkl´on

Ezután minden így keletkezett ξi,j klónban a kromoszóma egy véletlenszer˝u k szegmenk = sét helyettesítjük egy véletlenszer˝u számmal, amely kisebb vagy egyenl˝o, mint n (ξi,j Random[n]). Amikor a klón valamelyik része megváltozik, tekintettel kell lenni arra, hogy l k , k 6= l-re. Ezután az 6= ξi,j az új szegmens legyen egyedi az adott klónon belül, azaz ξi,j összes klónt és az eredeti baktériumot a φ(ξ) kiértékelési függvény segítségével kiértékeljük. A legjobb egyed a megváltoztatott szegmenst átadja a többi egyednek. Ez a folyamat ismétl˝odik, amíg az összes szegmensre végre nem hajtottuk a mutációt. A végén a legjobb egyedet megtartjuk a többi Nkl´on egyedet pedig töröljük. A második változatban a mutációra kiválasztott szegmens hossza is paramétere lesz a bakteriális mutációnak (MutációsHossz). Amikor egy klónban valamelyik szegmens megváltozik, egyidej˝uleg a szegmens hossza is megváltozhat, azaz a megváltoztatott szegmens megrövidülhet, meghosszabbodhat, vagy esetleg ugyanolyan hosszú maradhat, mint el˝otte volt. Így új számokat lehet hozzáadni a baktériumhoz, vagy el lehet távolítani bel˝ole. Erre is van egy új paraméter, nevezetesen a VáltoztathatóMutációsHossz. A 3.32 ábra példát mutat a bakteriális mutációra az algoritmus els˝o változata alapján (azaz a M ut´ aci´ osHossz = 1, és a V a ´ltoztathat´ oM ut´ aci´ osHossz = 0) Nkl´on = 3 klónszám esetén. 3.6.1.5. Génátadás A génátadás a korábban megismert módon zajlik, viszont itt tekintettel kell lenni arra, csakúgy mint a bakteriális mutáció esetén, hogy amikor egy egyed változik, akkor csak olyan változás lehetséges, hogy minden feature azonosító legfeljebb egyszer fordulhat el˝o az egyedben. Az algoritmus els˝o változatában a célbaktérium kromoszómájának egy véletlenszer˝uen kiválasztott szegmensét felülírja a forrásbaktériumtól kapott szegmenssel, ha a kapott szegmens még nincs a célbaktériumban. A második változatban az egyed hosszának nem kell állandónak lennie, így itt is bevezethet˝o két új paraméter, a GénátadásHossz, mely a forrásbaktériumtól kapott szegmens méretét határozza meg, és a VáltoztathatóGénátadásHossz, amely a célbaktériumban engedélyezett maximális hosszváltoztatást jelenti. A génátadás Ninf -szer ismétl˝odik. A 3.33 ábra példát mutat a génátadásra az algoritmus els˝o változata alapján (azaz a G´ en´ atad´ asHossz = 1, és a V a ´ltoztathat´ oG´ en´ atad´ asHossz = 0) Nind = 4 baktériumból álló populáció és Ninf = 3 infekció esetén. 95

Φ HΞL = 0.8 ß

44 17 36 2 7

44 17 36 2 7 Φ HΞL = 0.8

44 17 20 2 7 Φ HΞL = 0.5

44 17 35 2 7 Φ HΞL = 0.9

44 17 40 2 7

44 17 20 2 7 Φ HΞL = 0.5

44 17 20 2 7

16 17 20 2 7

21 17 20 2 7

Φ HΞL = 0.7

ß 44 17 20 2 7 Φ HΞL = 0.5

44 17 20 2 7 Φ HΞL = 0.5

Φ HΞL = 0.5

ß 44 17 20 2 7 Φ HΞL = 0.5

33 17 20 2 7 Φ HΞL = 0.7

Φ HΞL = 0.4

Φ HΞL = 0.9

ß etc. ß Φ HΞL = 0.3

16 17 20 2 19

3.32. ábra. A bakteriális mutáció m˝uvelete

16 17 36 2 19 Φ HΞL = 0.3

Φ HΞL = 0.5

33 31 20 7 4

21 18 5 39 25 Φ HΞL = 0.6

30 3 9 27 32

21 18 36 39 25

30 3 9 27 32

Φ HΞL = 0.8

ß Φ HΞL = 0.3

16 17 36 2 19

33 31 20 7 4 Φ HΞL = 0.5

Φ HΞL = 0.7

Φ HΞL = 0.8

ß 16 17 36 2 19 Φ HΞL = 0.3

Φ HΞL = 0.4

21 31 36 39 25

33 31 20 7 4

Φ HΞL = 0.5

30 3 9 27 32

Φ HΞL = 0.5

30 3 9 2 32

Φ HΞL = 0.8

ß Φ HΞL = 0.3

16 17 36 2 19

Φ HΞL = 0.4

21 31 36 39 25

33 31 20 7 4

3.33. ábra. A génátadás m˝uvelete

96

Φ HΞL = 0.6

3.6.2. A módszer alkalmazása A bakteriális megközelítéssel végrehajtott feature kiválasztási feladatra szimulációs programot készítettem Mathematica-ban. Szimulációs vizsgálatokat végeztem, amelynek során el˝oször az algoritmus els˝o változatát próbáltam ki három különböz˝o regressziós módszer esetén. Az algoritmus viselkedésének elemzésére használt három regressziós módszer közül az els˝o egyszer˝u legkisebb négyzetes optimalizáció, a második és harmadik pedig fuzzy szabálybázis identifikációs modell. Mindhárom esetben olyan modell kialakítása a cél, amely megoldást nyújt három nagy-dimenziós problémára. Az els˝o teszt függvény a 20 dimenziós [0, 1]20 adattéren értelmezett a következ˝o módon: f20 (x) = x1 x22 x313 − x20 + 5 sin(x16 ) − 25 cos(x5 x18 ) + exp(x3 x5 ) + x4 x19 + x210 + x511 . A második teszt függvény az 50 dimenziós [0, 5]50 adattéren értelmezett: f50a (x) = x1 x240 + 0.01 x12 + 0.01 x15 + 3.1x49 . A harmadik teszt függvény pedig az 50 dimenziós [1, 2]50 adattéren értelmezett: x10 + 0.5 x313 + x11 x12 x18 + x19 2 x14 x15 − x16 − x17 + 50 + x46 x20

1

f50b (x) = x1 + x22 + x3 x4 + 2 exp(2(x5 − x6 )) + x7 x8 x9 −

Mindegyik teszt függvény esetén 500 tanítómintát használtam, amelyekben minden megadott bemeneti dimenzióhoz egyenletes eloszlású véletlenszám tartozik, míg a maradék dimenziókban (azaz azokban a dimenziókban, amelyek a függvények definícióiban nem szerepelnek) a függvények véletlen viselkedés˝uek. A szimulációs eredmények a 3.23 táblázatban láthatók. 3.6.2.1. Sztochasztikus jellegu˝ illeszkedési függvény Az els˝o példában létrehozott modell a tanító adatokra történ˝o legkisebb négyzetes illeszkedést számítja ki a bemeneti feature-ök lineáris kombinációjával. Az els˝o teszt függvény esetében az els˝o futtatáshoz képest még jobb eredményt értem el a második futtatás során a klónszám megnövelésével. A harmadik és negyedik futtatásban a kiválasztandó dimenziók számát 10-re növeltem, ami tovább javította a kapott eredményt. Két baktérium használatával a megoldást el˝obb találtam meg, mint egyetlen baktérium alkalmazásával. Az els˝o esetben a futtatás harmadik generációjában minden egyed megegyezett. A második teszt függvényre a cél a három legfontosabb dimenzió azonosítása. Az els˝o futtatásban egyetlen baktériumot és 5 klónt használtam, a másodikban 4 baktériumot, 4 klónt és minden generációban 2 génátadást. Az optimális megoldást az algoritmus az els˝o esetben az 5., míg a másodikban a 4. generációban találta meg. A talált megoldás a {40, 49, 1} egyed. A függvény definíciójából könnyen látható, hogy tényleg ezek a legfontosabb változók. Amikor a baktérium hossza 5 volt, az algoritmus 2 további változót is talált, de az ezáltal elért 97

teljesítménynövekedés (hibacsökkenés) elenyész˝o volt. Az ehhez a problémához tartozó tanítási görbék a 3.34 ábrán láthatók. A harmadik teszt függvény esetén az els˝o futtatásban az optimális megoldás megtalálásához 16 generáció kellett. A klónok számának növelése esetében az optimális megoldást az algoritmus már a 8. generációban megtalálta. Növelve az egyedek számát és génátadást alkalmazva az algoritmus már 6 generáció alatt megtalálta a megoldást. Az ezutáni esetekben a baktérium hosszát (azaz a kiválasztandó feature-ök számát) 10-re állítottam. Négy klón használatával a megoldás nem adódott optimálisra. Hat klón alkalmazásánál már kisebb lett a hiba. Amikor egyetlen baktérium helyett négyet alkalmaztam, ugyanezt az eredményt már az 5. generációban megkaptam, és a 20. generációban minden baktérium egyforma volt. 3.23. táblázat. Szimulációs eredmények illusztrációja f f20 f20 f20 f20 f20 f20 f20 f20 f20 f20 f20 f50a f50a f50a f50a f50a f50a f50a f50a f50a f50a f50a f50b f50b f50b f50b f50b f50b f50b f50b f50b f50b f50b f50b

módszer LINA LINA LINA LINA RENO RENO RENO FS-ID3 FS-ID3 FS-ID3 FS-ID3 LINA LINA LINA LINA RENO RENO RENO FS-ID3 FS-ID3 FS-ID3 FS-ID3 LINA LINA LINA LINA LINA LINA RENO RENO RENO FS-ID3 FS-ID3 FS-ID3

Ngen 10 10 10 10 10 20 20 10 10 10 10 10 10 10 10 10 10 10 10 10 10 20 20 20 20 20 20 20 10 10 10 20 10 20

Nind 1 1 1 2 1 1 2 1 1 1 2 1 4 1 2 1 1 4 1 1 1 4 1 1 4 1 1 4 1 1 4 1 4 1

Nkl´on 4 6 4 4 4 6 6 4 6 4 4 5 4 6 4 3 4 3 4 6 8 6 4 6 6 4 6 6 4 6 4 4 4 4

Ninf 0 0 0 1 0 0 1 0 0 0 1 0 2 0 1 0 0 2 0 0 0 2 0 0 2 0 0 2 0 0 2 0 2 0

m 5 5 10 10 3 3 3 5 5 10 10 3 3 5 5 3 3 3 3 3 3 3 5 5 5 10 10 10 3 3 3 5 5 10

hiba 1,41 1,40 1,25 1,25 0,36 0,36 0,36 1,99 1,99 2 2,06 131,38 131,38 130,71 130,78 21,93 1,82 1,82 334,29 77,87 77,87 77,87 29,49 29,49 29,49 25,22 24,58 24,58 10,15 97,39 10,15 57,51 55,71 54,4

gen. 3 3 8 1 3 1 3 3 3 2 1 5 4 10 6 9 8 10 4 10 7 12 16 8 6 11 14 5 10 10 8 20 8 16

legjobb baktérium {18, 16, 20, 5, 10} {18, 10, 5, 16, 11} {4, 5, 16, 20, 3, 18, 11, 10, 17, 15} {4, 18, 5, 20, 3, 15, 17, 16, 10, 11} {5, 18, 16} {5, 16, 18} {18, 5, 16} {13, 14, 16, 5, 18} {16, 13, 5, 18, 9} {20, 6, 16, 5, 15, 10, 14, 18, 13, 3} {8, 18, 12, 16, 6, 5, 4, 3, 7, 10} {49,1,40} {40,49,1} {9,4,40,49,1} {40,9,27,1,49} {1,8,40} {1,49,40} {49,40,1} {37,33,40} {40,24,1} {40,24,1} {24,40,1} {19, 18, 20, 14, 6} {19, 14, 20, 18, 6} {20, 6, 18, 14, 19} {14, 17, 5, 6, 9, 20, 8, 15, 19, 18} {19, 6, 8, 15, 14, 5, 18, 9, 13, 20} {15, 18, 20, 5, 9, 14, 19, 13, 6, 8} {19, 18, 20} {37, 19, 20} {20, 18, 19} {20, 19, 39, 18, 25} {19, 18, 20, 36, 35} {40, 26, 19, 17, 30, 25, 18, 20, 9, 46}

3.6.2.2. RENO optimalizáció Ebben a példában a regressziós modell a RENO [45] fuzzy szabály identifikációs módszerrel készül. A RENO el˝oször minden dimenzióban egyenletesen elosztott fuzzy halmazokat határoz meg. Ezután ezen fuzzy halmazok Descartes szorzatának minden elemére egy Takagi-Sugeno szabályt hoz létre. Végül a kapott szabálybázist egy regularizált numerikus 98

3.34. ábra. Szimulációs eredmények a második függvényre lineáris approximációt alkalmazva

optimalizációs technikával optimalizálja. Bár ez a módszer nagyon pontos modellek létrehozásához vezet, a használata alacsony dimenziószámú (n ≤ 8) problémákra korlátozott, mivel a szabályok száma az alkalmazott dimenziók számának exponenciális függvénye. A szimuláció célja RENO esetén a három legfontosabb változó azonosítása. Az els˝o teszt függvénnyel mindegyik futtatás ugyanazt az eredményt adta. Abban az esetben, amikor nem csak egy egyedet alkalmaztam, minden baktérium egyformává vált már a 4. generációban. A legjobb egyed a {18, 5, 16} volt, ami valóban megfelel a függvény legfontosabb változóinak. A második teszt függvényre az els˝o kísérlet során az algoritmus nem talált kielégít˝o megoldást. A klónok számát négyre növelve azonban megtalálta a megfelel˝o megoldást. A baktériumok számát növelve és génátadást használva a megoldás ugyanaz lett. Az ehhez a problémához tartozó tanítási görbék a 3.35 ábrán láthatók. A harmadik teszt függvényre az algoritmus 4 klón használatával optimális megoldást talált. Több egyed használatával a megoldást korábban találta meg. A klónok számának növelése azonban félrevezette az algoritmust, ekkor egyáltalán nem közelítette meg az optimumot. 3.6.2.3. Döntési fa optimalizáció A harmadik példában a javasolt módszert egy induktív fuzzy döntési fa alapú tanítási módszer, az FS-ID3 [31] teljesítményének optimalizálására használtam. Ez a módszer topdown megközelítéssel hoz létre döntési fát, amit osztályozási és regressziós problémákra lehet használni. Bár ez az eljárás képes nagyszámú bemeneti feature-t kezelni, az értelmezhet˝oségét javítani lehet akkor, ha a módszer a rendelkezésre álló feature-öknek csak egy részhalmazát használja. Az els˝o teszt függvényre az algoritmus gyorsan megtalálta a megoldást, 5 és 10 hosszúságú baktérium esetén is. A második függvény esetén több klón alkalmazása jobb eredményhez vezetett. A harmadik függvényre a több baktériumot használó kísérletek adtak jobb ered99

3.35. ábra. Szimulációs eredmények a második függvényre RENO-t alkalmazva

3.36. ábra. Szimulációs eredmények a második függvényre FS-ID3-t alkalmazva

ményt. Ezek a példák a generációszám fontosságát illusztrálják, mert az optimális megoldást sokszor csak a kés˝obbi generációkban érte el az algoritmus. 3.6.2.4. Változó hosszúságú baktériumok Az el˝oz˝o futtatások során az algoritmus els˝o változatát alkalmaztam, amelyben a baktériumok hossza el˝ore adott volt. Most a második változattal végzett eredményeket mutatom be, amelynél a cél nemcsak az optimális feature halmaz meghatározása, hanem a feature-ök számának optimalizálása is. Az el˝oz˝o részben használt 20 változós függvény alapján létrehoztam olymódon egy 80

100

változós függvényt, hogy az eredeti függvényhez annak exponenciális, négyzetes és köbös transzformációval kapott függvényeit is hozzáadtam. A korábban vizsgált statisztikai alapú illeszkedési modellt vizsgáltam, mely a tanítóadatokra történ˝o legkisebb négyzetes illeszkedést számítja ki a bemeneti feature-ök lineáris kombinációjával. A lehetséges feature halmaz 80 elem˝u. Egy futtatásra kapott tanítási görbék láthatók a 3.37 ábrán. A futtatáshoz a következ˝o paraméter beállításokat használtam: Ngen = 40 MutációsHossz = 1 Nind = 4 VáltoztathatóMutációsHossz = 1 Nclones = 6 GénátadásHossz = 1 Ninf = 3 VáltoztathatóGénátadásHossz = 1 L = 10 β = 0,2

3.37. ábra. Szimulációs eredmények változó baktériumhosszra lineáris approximációt alkalmazva

Látható, hogy az algoritmus mindegyik futtatás során az optimális megoldáshoz konvergált, és ehhez legfeljebb 40 generáció kellett. Már 10 generáció alatt mindegyik esetben jó megoldást talált. A forward selection módszer csak szuboptimális megoldást talált, 20%-kal nagyobb átlagos négyzetes hibával. Az el˝oz˝o szakaszokban ismertetett eredmények azt igazolják, hogy a javasolt bakteriális megközelítést különböz˝o módszerekkel kombinálva lehet regressziós és osztályozási feladatokra használni. A következ˝okben tézisek formájában fogalmazom meg az e fejezetben ismertetett új eredményeket. A tézissel kapcsolatos publikációim a hivatkozási listában megtalálhatók [14, 32]. 101

6. tézis. Feature kiválasztási feladatra alkalmaztam a bakteriális evolúciós algoritmust és szimulációs vizsgálatokkal megmutattam, hogy az algoritmus különböz˝o regressziós módszerekkel kombinálva alkalmas nagy dimenziószámú problémák optimális változókészletének meghatározására. 6.1. altézis. Feature kiválasztási feladatra alkalmazott bakteriális evolúciós algoritmushoz megadtam a kódolási elrendezést és kifejlesztettem a feladathoz illeszked˝o módosított bakteriális operátorokat. 6.2. altézis. Elkészítettem a feladatot megvalósító programot, mely feature kiválasztási feladat megoldására alkalmas. 6.3. altézis. A módszert három különböz˝o regressziós módszerrel kombinálva használtam, és különböz˝o nagy dimenziószámú teszt függvényekre szimulációs vizsgálatokat végeztem, melyek segítségével meghatároztam a függvények optimális változókészletét. Az értekezés mellékletként tartalmazza elektronikus formában (CD-n) a kidolgozott új identifikációs módszerek elkészített szimulációs programjait.

102

4. fejezet Összefoglalás és kitekintés Az értekezés célkit˝uzése olyan numerikus adatok alapján történ˝o identifikációs módszerek kifejlesztése volt, amelyekkel az irodalomban ismert eljárásoknál meghatározott kritériumok szerint kedvez˝obb eredményt lehet elérni. Az értekezés nagy része fuzzy szabályalapú rendszerek modell-identifikációját tárgyalja. Az identifikáció célja optimális szabályrendszer kialakítása numerikus mintaadatok alapján. Fuzzy rendszerek alkalmazása során el˝ofordulhat, hogy rendelkezésre áll olyan emberi szakért˝o, aki a fuzzy szabálybázist felépíti. Sok esetben azonban nincs lehet˝oség szakért˝o igénybevételére, rendelkezésre állnak viszont numerikus input-output adatok, melyek alapján a szabályrendszer több-kevesebb pontossággal meghatározható. El˝ofordulhat olyan eset is, hogy egy emberi szakért˝o(k) által megadott kezdeti szabálybázist kell (és lehet) numerikus minták alapján optimalizálni, tovább pontosítani. Az els˝o tézisben a bakteriális evolúciós algoritmus olyan továbbfejlesztését javasoltam Mamdani-típusú fuzzy rendszer szabálybázisának identifikációjára, amely háromszög alakú tagsági függvényeket használó fuzzy szabályok helyett az általánosabb trapéz alakú tagsági függvényekb˝ol felépül˝o modelleket optimalizál úgy, hogy újszer˝u szabályredukciós operátorokat is tartalmaz, melyek segítségével a szabálybázis mérete optimalizálható. A bakteriális megközelítés egyébként el˝onyösebb a klasszikus genetikus algoritmusnál, mert a bakteriális operátorok gyorsabb és pontosabb konvergenciát biztosítanak. Ezáltal a módszer kevesebb id˝o alatt ér el a m˝uszaki feladat szempontjából megfelel˝o kvázi-optimális megoldást, azaz kevesebb számú egyed és generáció elegend˝o, mint a genetikus algoritmusok esetén. A második tézisben egy gradiens alapú tanító módszert mutatok be fuzzy szabálybázis paramétereinek optimalizálására alkalmazva, a Levenberg-Marquardt algoritmust. Ez a módszer gyorsabb konvergencia tulajdonságokkal rendelkezik, mint a klasszikus hibavisszaterjesztéses (backpropagation) tanító algoritmus. El˝onye, hogy gyorsan konvergál az optimumhoz, azt igen jó közelítéssel megtalálja, hátránya viszont, hogy ez az optimum általában csak lokális környezetre vonatkozik, a kiindulási értékt˝ol függ˝oen. A harmadik tézisben olyan módszert javasolok Mamdani-típusú szabálybázis identifikációjára, mely az els˝o két tézisben alkalmazott algoritmusok kombinációja, és ezáltal azok hátrányait kiküszöböli. A bakteriális evolúciós algoritmus globális jelleg˝u keresést hajt végre, és ennélfogva a globális optimumhoz konvergál, viszont a konvergencia sebessége lassú, és nem is lehet itt klasszikus értelemben vett konvergenciáról beszélni, mivel a hiba a gyakorlatban alulról korlátos. A Levenberg-Marquardt algoritmus gyorsan konvergál, viszont csak a

103

legközelebbi lokális optimumhoz közelít. A kétféle megközelítés kombinációjával globális, megfelel˝o pontosságú, gyors algoritmushoz jutottam. A negyedik tézisben Takagi-Sugeno-típusú szabálybázis identifikációjára javaslok módszert. Az ilyen típusú fuzzy rendszerek esetén a szabálybázis felépítése során azt használom ki, hogy a szabály antecedense és konzekvense más felépítés˝u. A szabály antecedens a Mamdani-típusúval megegyez˝o felépítés˝u, ezért alkalmazható rá a bakteriális és LevenbergMarquardt módszerek kombinációja. A konzekvens viszont egyszer˝u lineáris kombinációt valósít meg, ezért optimalizációjára a legkisebb négyzetek módszere használható. Az ötödik tézisben neurális hálózatok struktúrájának optimalizációjával foglalkozom. Míg a fuzzy rendszerek esetén a szabálybázist emberi szakért˝o is meghatározhatja, addig a neurális hálózatok esetében a modell jellegéb˝ol fakadóan a minták alapján történ˝o identifikációra nincs alternatíva. A lágy számítástudomány ezen kategóriáját használva modellként kulcskérdés tehát a megfelel˝o identifikációs, tanuló algoritmus alkalmazása. A bakteriális programozást javaslom B-spline típusú neurális hálózat optimális kialakítására. A módszer a genetikus programozás és a bakteriális evolúciós algoritmus kombinációja, mely kromoszóma helyett fagráffal reprezentált egyedeket optimalizál, és az evolúciós folyamat során a bakteriális operátorokat használja. Az értekezés els˝o öt tézisében olyan módszerekkel foglalkoztam, melyek valamely állapotváltozók terében egy adott kritérium szerint megfelel˝o fuzzy vagy neurális modellt hoznak létre. A hatodik tézisben a modell-identifikációs folyamat egy el˝ozetes lépésével foglalkoztam, melynek célja az adott problémát megfelel˝oen leíró változók minimális halmazának megkeresése. Erre a változó kiválasztási feladatra a bakteriális evolúciós algoritmust javasoltam. A tézisekben bemutattam, hogy a bakteriális megközelítés és a Levenberg-Marquardt módszer jobb megoldást kínál az identifikációs, optimalizációs feladatra, mint az irodalomból ismert egyéb módszerek. A módszerek tesztelésére többféle kiértékelési kritériumot használtam. Az algoritmusok továbbfejlesztett változataiban nem csak állandó számú szabály, illetve a feature kiválasztási alkalmazás esetén állandó számú dimenzió optimalizálását javasoltam, hanem a szabálybázis méretének optimalizálását is. Erre az els˝o tézisben javasolt szabályredukciós operátorokat mutattam be, illetve a harmadik és hatodik tézisben a bakteriális operátorok olyanfajta módosítását, melyek lehet˝ové teszik az egyedek hosszának változását az evolúciós folyamat során. A bakteriális operátorok hatékony optimalizációt hajtanak végre. A bakteriális mutáció az egyes egyedeket külön-külön optimalizálja, az egyedet leíró kromoszóma illetve kifejezésfa minden részletét tökéletesíti. Ez az operátor a klasszikus mutációs operátor továbbfejlesztése. A klónok alkalmazásával több alternatív út van jobb megoldás közelítésére, és ugyanakkor a populációban kevesebb egyed alkalmazása elegend˝o, mint a genetikus algoritmusok illetve genetikus programozás esetén. A másik bakteriális operátor, a génátadás a genetikus megközelítésben alkalmazott keresztezést helyettesíti, és a populációt alkotó baktériumok között lehet˝ové teszi az információáramlást. A génátadás során „jó” egyed ad át információt „rossz” egyednek, ezért mivel az információáramlás ilyen módon irányított, a „jó” egyed nem vész el az optimalizáció során, ellentétben a genetikus módszernél alkalmazott keresztezéssel, ahol a keresztezés jellege miatt a szül˝oknél rosszabb utódok is keletkezhetnek. Az egyes egyedeket külön kezel˝o bakteriális mutáció és az egész baktériumpopulációt 104

figyelembe vev˝o génátadás együttesen globális kvázi optimalizációt hajt végre. Az operátorok paraméterei befolyásolják a megoldás gyorsaságát és pontosságát. A második tézisben mutattam be a Levenberg-Marquardt módszert önmagában alkalmazva, amelyben a hiba-visszaterjesztéses algoritmussal összehasonlítva bebizonyosodott, hogy az LM módszer gyorsabban konvergál az optimum felé. Az LM eljárás az el˝onyeit a bakteriális megközelítéssel kombinálva is megtartja, a bakteriális memetikus algoritmussal gyorsabban sikerül közel optimális megoldást találni, mint a bakteriális evolúciós algoritmussal. A memetikus algoritmusban az LM lépés alkalmazása nem növeli a lokális optimumba ragadás esélyét, hanem feljavítja a bakteriális operátorok által kapott kvázi-optimális megoldás pontosságát, illetve gyorsabb megtalálását. A fuzzy rendszereknek számos gyakorlati alkalmazása ismert. A Mamdani által javasolt következtet˝o eljárás megjelenése után a fuzzy téma iránt megn˝ott az érdekl˝odés. A 80-as évek közepét˝ol kezdve Japánban különféle ipari rendszerekben és kereskedelmi termékekben jelentek meg a fuzzy irányító rendszerek, például háztartási gépekben (porszívó, mosógép stb.), ipari és mobil robotokban, gépjárm˝ugyártásban (ABS-rendszer, automata sebességváltó stb.), multimédiás alkalmazásokban (videokamera, fényképez˝ogép). A legtöbb kezdeti alkalmazásban a korábban bemutatott egyszer˝u fuzzy szabályalapú rendszerek játszottak szerepet. Emiatt az értekezésben ismertetett szabálykinyerési folyamat kulcsfontosságú lehet a további összetettebb és fejlettebb alkalmazásokban használt fuzzy szabályalapú rendszerek tervezésekor. Az alkalmazások sorát b˝ovíti az értekezésben megismert másik lágy számítástudományi módszer, a neurális hálózatok felhasználása, melyeket például különböz˝o felismerési (kézírás, arc stb.) és osztályozási feladatok megoldására alkalmaznak sikerrel. A két terület kombinált felhasználása is megjelent sok alkalmazásban, ilyenek az ún. neuro-fuzzy hibrid rendszerek, melyek az el˝obbi példák korszer˝ubb megoldásaiban játszanak szerepet. Az értekezésben bemutatott identifikációs eszközök különböz˝o típusú modelleket eredményeznek, a szakirodalomban mostanában megjelent mind elméleti mind alkalmazási szempontból egyaránt egységes módon alkalmazható tenzorszorzat modell transzformációval [6, 7, 86] egységes formára transzformálhatóak és így közvetlenül illeszthet˝oek a modern konvex optimalizáción alapuló tervez˝o eszközökhöz. Így az értekezésben bemutatott módszerek hatékonyan alkalmazhatóvá válnak modern rendszer- és irányításelméleti, lineáris mátrix egyenl˝otlenségeken alapuló feladatokban is. Az egyszer˝u fuzzy modelleken kívül kés˝obb megjelentek az értekezés bevezet˝ojében már említett hierarchikus fuzzy szabályalapú rendszerek is. A hierarchikus rendszerek csökkentik a számítási bonyolultságot, mert ahelyett, hogy egyetlen sokdimenziós fuzzy szabálybázist használnának, több, kisebb dimenziószámú alszabálybázisból állnak, melyeket egy fels˝obb szint˝u metaszabálybázis fog össze egységes rendszerré. Ezen rendszerekkel a problémát egymástól függetlenül kezelhet˝o részmodellekre lehet bontani, melyek a teljes feladat egy részének megoldásáért felel˝osek, és a teljes állapotváltozó-készlethez képest csökkentett számú változót tartalmaznak. További kutatásaim els˝odleges célja ilyen hierarchikus fuzzy szabályrendszerek identifikációja lesz. A hierarchikus struktúrán kívül a ritka szerkezet˝u szabálybázisok alkalmazása is célszer˝u, ezzel a modell bonyolultsága tovább csökkenthet˝o. Az egyik legfontosabb feladat a további kutatásban a nagy bonyolultságú alkalmazásokban használt hierarchikus interpolatív fuzzy rendszerek automatikus identifikációja lesz. A legnagyobb probléma itt az, hogy olyan 105

két vagy több altérre történ˝o felosztást kell találni az állapottérben, hogy az úgynevezett meta-tér lehet˝oséget adjon arra, hogy benne döntés történjék egy vagy néhány lokális területen létrehozott részmodell érvényességével kapcsolatban. Ezek az állapottér fennmaradó alterében foglalnak helyet és a dimenziószám (a rendszer m˝uködését ténylegesen befolyásoló állapotváltozók száma) lokálisan redukálható. Az értekezésben elért eredmények arra bíztatnak, hogy célszer˝u lehet ezt a feladatot is a bakteriális megközelítéssel, illetve annak az LM módszerrel való kombinált továbbfejlesztésével megoldani. Az egyes alszabálybázisokban szerepl˝o változók meghatározására, és a hierarchikus rendszer optimális struktúrájának kialakítására a bakteriális programozás alkalmazása t˝unik jó lehet˝oségnek. Az egyes almodellek további optimalizációja, finomítása ekkor az LM módszerrel valósítható meg. Ezek az új kutatási irányok várhatóan jelent˝os mértékben növelhetik az intelligens számítástechnikai modellek hatékony alkalmazását a tudományos kutatások és az ipari felhasználás területén egyaránt.

106

Irodalomjegyzék [1] A. Alkan and E. Ozcan. Memetic algorithms for timetabling. In Proceedings of the 2003 Congress on Evolutionary Computation, CEC 2003, pages 1796–1802, Canberra, Australia, 2003. [2] E. Amaldi and V. Kann. On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems. Theoretical Computer Science, 209(1–2):237– 260, 1998. [3] D. Ashlock and A. Sherk. Non-local adaptation of artificial predators and prey. In Proceedings of the IEEE Congress on Evolutionary Computation 2005, pages 41–48, Edinburgh, UK, 2005. [4] R. Babuska. Fuzzy Modeling for Control. Kluwer Academic Publishers, Boston, 1998. [5] T. Bäck, F. Hoffmeister, and H.-P. Schwefel. A survey of evolution strategies. In Proceedings of the Fourth International Conference on Genetic Algorithms, pages 2– 9, San Diego, July 1991. [6] P. Baranyi. TP model transformation as a way to LMI based controller design. IEEE Transaction on Industrial Electronics, 51(2):387–400, 2004. [7] P. Baranyi, D. Tikk, Y. Yam, and R. J. Patton. From differential equations to PDC controller design via numerical transformation. Computers in Industry, Elsevier Science, 51:281–297, 2003. [8] C. Bishop. Improving the generalization properties of radial basis function neural networks. Neural Computation, 3:579–588, 1991. [9] C. M. Bishop. Neural Networks for Pattern Recognition. Oxford University Press, 1995. [10] J. Botzheim, C. Cabrita, L. T. Kóczy, and A. E. Ruano. Fuzzy rule extraction by bacterial memetic algorithms. International Journal of Intelligent Systems. Közlésre benyújtva. [11] J. Botzheim, C. Cabrita, L. T. Kóczy, and A. E. Ruano. Estimating fuzzy membership functions parameters by the Levenberg-Marquardt algorithm. In Proceedings of the IEEE International Conference on Fuzzy Systems, FUZZ-IEEE 2004, pages 1667– 1672, Budapest, Hungary, July 2004. 107

[12] J. Botzheim, C. Cabrita, L. T. Kóczy, and A. E. Ruano. Fuzzy rule extraction by bacterial memetic algorithms. In Proceedings of the 11th World Congress of International Fuzzy Systems Association, IFSA 2005, pages 1563–1568, Beijing, China, July 2005. [13] J. Botzheim, C. Cabrita, L. T. Kóczy, and A. E. Ruano. Genetic and bacterial programming for B-spline neural networks design. Journal of Advanced Computational Intelligence and Intelligent Informatics, 11(2):220–231, February 2007. [14] J. Botzheim, M. Drobics, and L. T. Kóczy. Feature selection using bacterial optimization. In Proceedings of the International Conference on Information Processing and Management of Uncertainty in Knowledge-based Systems, IPMU 2004, pages 797– 804, Perugia, Italy, July 2004. [15] J. Botzheim, B. Hámori, and L. T. Kóczy. Extracting trapezoidal membership functions of a fuzzy rule system by bacterial algorithm. In B. Reusch, editor, Computational Intelligence, Theory and Applications, volume 2206 of Lecture Notes in Computer Science, pages 218–227. Springer-Verlag, Berlin-Heidelberg, 2001. [16] J. Botzheim, B. Hámori, L. T. Kóczy, and A. E. Ruano. Bacterial algorithm applied for fuzzy rule extraction. In Proceedings of the International Conference on Information Processing and Management of Uncertainty in Knowledge-based Systems, IPMU 2002, pages 1021–1026, Annecy, France, July 2002. [17] J. Botzheim and L. T. Kóczy. Model identification by bacterial optimization. In Proceedings of the 5th International Symposium of Hungarian Researchers on Computational Intelligence, pages 91–102, Budapest, Hungary, November 2004. [18] J. Botzheim, L. T. Kóczy, and A. E. Ruano. Extension of the Levenberg-Marquardt algorithm for the extraction of trapezoidal and general piecewise linear fuzzy rules. In Proceedings of the 2002 IEEE World Congress on Computational Intelligence, WCCI 2002, pages 815–819, Honolulu, Hawaii, May 2002. [19] J. Botzheim, E. Lughofer, E. P. Klement, L. T. Kóczy, and T. D. Gedeon. Separated antecedent and consequent learning for Takagi-Sugeno fuzzy systems. In Proceedings of the 2006 IEEE World Congress on Computational Intelligence, WCCI 2006, pages 10478–10484, Vancouver, Canada, July 2006. [20] L. Breiman, J. Friedman, C. J. Stone, and R. A. Olshen, editors. Classification and Regression Trees. CRC Press, 1984. [21] M. Brown and C. Harris. Neurofuzzy Adaptive Modelling and Control. Prentice-Hall, 1994. [22] C. Cabrita, J. Botzheim, T. D. Gedeon, A. E. Ruano, L. T. Kóczy, and C. M. Fonseca. Bacterial memetic algorithm for fuzzy rule base optimization. In Proceedings of the World Automation Congress, WAC 2006, Budapest, Hungary, July 2006.

108

[23] C. Cabrita, J. Botzheim, A. E. Ruano, and L. T. Kóczy. Genetic programming and bacterial algorithm for neural networks and fuzzy systems design. In Proceedings of the IFAC International Conference on Intelligent Control Systems and Signal Processing, ICONS 2003, pages 500–505, Faro, Portugal, April 2003. [24] C. Cabrita, J. Botzheim, A. E. Ruano, and L. T. Kóczy. Design of B-spline neural networks using a bacterial programming approach. In Proceedings of the International Joint Conference on Neural Networks, IJCNN 2004, pages 2313–2318, Budapest, Hungary, July 2004. [25] C. Cabrita, J. Botzheim, A. E. Ruano, and L. T. Kóczy. A hybrid training method for B-spline neural networks. In Proceedings of the IEEE International Symposium on Intelligent Signal Processing, WISP 2005, pages 165–170, Faro, Portugal, September 2005. [26] C. Cabrita, A. E. Ruano, and C. M. Fonseca. Single and multi-objective genetic programming design for B-spline neural networks and neuro-fuzzy systems. In Proceedings of the IFAC Workshop on Advanced Fuzzy-Neural Control 2001, AFNC01, pages 75–80, Valencia, Spain, Oct. 2001. [27] V. Cutello, G. Nicosia, M. Pavone, and J. Timmis. An immune algorithm for protein structure prediction on lattice models. IEEE Transactions on Evolutionary Computation, 11(1):101–117, Feb. 2007. [28] C. Darwin. The Origin of Species. John Murray, London, 1859. [29] M. Dorigo and L. M. Gambardella. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1):53–66, 1997. [30] M. Dorigo, V. Maniezzo, and A. Colorni. Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B Cybernetics, 26(1):29–41, 1996. [31] M. Drobics and U. Bodenhofer. Fuzzy modeling with decision trees. In Proc. 2002 IEEE Int. Conf. on Systems, Man and Cybernetics, volume 4, Hammamet, Tunisia, October 2002. [32] M. Drobics and J. Botzheim. A bacterial evolutionary algorithm for feature selection. FLLL/SCCH Master and PhD Seminar, Johannes Kepler University, Linz, Austria, June 2005. [33] R. C. Eberhart and J. Kennedy. Swarm Intelligence. Morgan Kaufmann, 2001. [34] J. Elman. Finding structure in time. Cognitive Science, 14:179–211, 1990. [35] R. Fletcher. Practical Methods of Optimization. Wiley, 2000.

109

[36] D. B. Fogel. Evolutionary Computation: Toward a New Philosophy of Machine Intelligence. IEEE Press, Piscataway, 1995. [37] L. J. Fogel, A. J. Owens, and M. J. Walsh. Artificial Intelligence through Simulated Evolution. Wiley, New York, 1966. [38] C. M. Fonseca and P. J. Fleming. An overview of evolutionary algorithm in multiobjective optimization. Evolutionary Computation, 3:165–180, 1995. [39] C. M. Fonseca and P. J. Fleming. Multiobjective optimization and multiple constraint handling with evolutionary algorithms. I. A unified formulation. IEEE Transactions on Systems, Man and Cybernetics-Part A: Systems and Humans, 28(1):26–37, Jan. 1998. [40] J. H. Friedman. Multivariate adaptive regression splines. The Annals of Statistics, 19(1):1–67, 1991. [41] T. Gánti. Chemoton elmélet I.kötet. OMIKK, Budapest, 1984. [42] D. E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Massachusetts, 1989. [43] I. Guyon and A. Elisseeff. An introduction to variable and feature selection. JMLR, 4:1157–1182, 2003. [44] R. Halavati, S. B. Shouraki, M. J. Heravi, and B. J. Jashmi. An artificial immune system with partially specified antibodies. In Proceedings of Genetic and Evolutionary Computation Conference, GECCO’07, pages 57–62, July 2007. [45] J. Haslinger, U. Bodenhofer, and M. Burger. Data-driven construction of Sugeno controllers: Analytical aspects and new numerical methods. In Proc. Joint 9th IFSA World Congress and 20th NAFIPS Int. Conf., pages 239–244, Vancouver, July 2001. [46] R. Hecht-Nielsen. Neurocomputing. Addison-Wesley, 1990. [47] H. Hellendoorn and C. Thomas. Defuzzification in fuzzy controllers. J. of Intelligent and Fuzzy Systems, 1(2):109–123, 1993. [48] J. H. Holland. Adaption in Natural and Artificial Systems. The MIT Press, Cambridge, Massachusetts, 1992. [49] J.-S.R. Jang. ANFIS: Adaptive-network-based fuzzy inference systems. IEEE Trans. Syst. Man Cybern., 23:665–685, 1993. [50] J-S.R. Jang and C.-T. Sun. Functional equivalence between radial basis function networks and fuzzy inference systems. IEEE Trans. on Neural Networks, 4(1):156–159, 1993. [51] S. H. Jung. Queen-bee evolution for genetic algorithms. 39(6):575–576, 2003. 110

Electronics Letters,

[52] J. Kennedy and R. C. Eberhart. Particle swarm optimization. In Proceedings of the IEEE International Conference on Neural Networks, pages 1942–1948, Perth, Australia, 1995. [53] G. J. Klir and B. Yuan. Fuzzy Sets and Fuzzy Logic. Theory and Applications. Prentice Hall, Upper Saddle River, New Jersey, 1995. [54] L. T. Kóczy. Fuzzy if then rules models and their transformation into one another. IEEE Trans. on SMC, 26(5):621–637, 1996. [55] L. T. Kóczy and J. Botzheim. Fuzzy rule base model identification techniques. In Proceedings of the 3rd International Symposium of Hungarian Researchers on Computational Intelligence, pages 13–24, Budapest, Hungary, November 2002. [56] L. T. Kóczy and J. Botzheim. Hierarchical interpolative fuzzy model identification. In Proceedings of the 18th Hungarian-Korean Joint Seminar, pages 17–27, Budapest, Hungary, October 2002. [57] L. T. Kóczy and J. Botzheim. Fuzzy models, identification and applications. In Proceedings of the IEEE 3rd International Conference on Computational Cybernetics, ICCC 2005, pages 13–19, Mauritius, April 2005. [58] L. T. Kóczy, J. Botzheim, and T. D. Gedeon. Fuzzy models and interpolation. In M. Nikravesh, J. Kacprzyk, and L. A. Zadeh, editors, Forging New Frontiers: Fuzzy Pioneers I & II, volume 217 of Studies in Fuzziness and Soft Computing. Springer, 2007. Megjelenés alatt. [59] L. T. Kóczy, J. Botzheim, A. E. Ruano, A. Chong, and T. D. Gedeon. Fuzzy rule extraction from input/output data. In P. Sincak, J. Vascak, and K. Hirota, editors, Machine Intelligence Quo Vadis?, volume 21 of Advances in Fuzzy Systems - Applications and Theory, pages 199–216. World Scientific, Singapore, 2004. [60] L. T. Kóczy, D.Tikk, and T. D. Gedeon. On functional equivalence of certain fuzzy controllers and RBF type approximation schemes. International Journal of Fuzzy Systems, 2(3):164–175, 2000. [61] L. T. Kóczy and K. Hirota. Approximate reasoning by linear rule interpolation and general approximation. Internat. J. Approximate Reasoning, 9:197–225, 1993. [62] L. T. Kóczy and K. Hirota. Interpolation in hierarchical fuzzy rule bases with sparse meta-levels. Technical Report 97/3, Hirota Lab., Dept. of Comp. Intelligent and Sys. Sci., Tokyo Institute of Technology, Yokohama, 1997. [63] L. T. Kóczy and D. Tikk. Fuzzy rendszerek. TypoTEX, Budapest, 2000. [64] L. T. Kóczy and A. Zorat. Optimal fuzzy rule bases — the Cat and Mouse Problem. In Proceedings of the IEEE International Conference on Fuzzy Systems, FUZZ-IEEE 1996, pages 1865–1870, New Orleans, Louisiana, USA, 1996. 111

[65] L. T. Kóczy and A. Zorat. Fuzzy systems and approximation. Fuzzy Sets and Systems, 85:203–222, 1997. [66] J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA, 1992. [67] J. R. Koza. Genetic Programming II: Automatic Discovery of Reusable Programs. MIT Press, Cambridge MA, USA, May 1994. [68] N. Kubota, K. Shimojima, and T. Fukuda. The role of virus infection in a virusevolutionary genetic algorithm. Journal of Applied Mathematics and Computer Science, 6(3):415–429, 1996. [69] J. B. Lamarck. Zoological Philosophy. Paris, Paris, 1809. [70] P. M. Larsen. Industrial application of fuzzy logic control. Int. J. of Man Machine Studies, 12(4):3–10, 1980. [71] M. Last, A. Kandel, and O. Maimon. Information-theoretic algorithm for feature selection. Pattern Recognition Letters, 22:799–811, 2001. [72] K. Levenberg. A method for the solution of certain non-linear problems in least squares. Quart. Appl. Math., 2(2):164–168, 1944. [73] L. Ljung. System Identification: Theory for the User. Prentice Hall PTR, Prentic Hall Inc., Upper Saddle River, New Jersey 07458, 1999. [74] E. Lughofer and U. Bodenhofer. Incremental learning of fuzzy basis function networks with a modified version of vector quantization. In Proceedings of 11th Int. Conf. on Information Processing and Management of Uncertainty in Knowledge-Based Systems, pages 56–62, Paris, France, July 2006. [75] E. Lughofer, E. Hüllermeier, and E.P. Klement. Improving the interpretability of datadriven evolving fuzzy systems. In Proceedings of EUSFLAT 2005, pages 28–33, Barcelona, Spain, 2005. [76] E. Lughofer and E.P. Klement. FLEXFIS: A variant for incremental learning of Takagi-Sugeno fuzzy systems. In Proceedings of FUZZ-IEEE 2005, pages 915–920, Reno, Nevada, U.S.A., 2005. [77] E. H. Mamdani and S. Assilian. An experiment in linguistic synthesis with a fuzzy logic controller. Int. J. Man-Mach. Stud., 7:1–13, 1975. [78] H. B. Mann and D. R. Whitney. On a test of whether one of two random variables is stochastically larger than the other. Annals of Mathematical Statistics, 18:50–60, 1947. [79] D. Marquardt. An algorithm for least-squares estimation of nonlinear parameters. J. Soc. Indust. Appl. Math., 11(2):431–441, Jun. 1963. 112

[80] P. Moscato. On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Technical Report Caltech Concurrent Computation Program, Report. 826, California Institute of Technology, Pasadena, California, USA, 1989. [81] M.Salmeri, M.Re, E. Petrongari, and G.C.Cardarilli. A novel bacterial algorithm to extract the rule base from a training set. In Proceedings of the IEEE International Conference on Fuzzy Systems, pages 759–761, May 2000. [82] N. E. Nawa and T. Furuhashi. Fuzzy system parameters discovery by bacterial evolutionary algorithm. IEEE Transactions on Fuzzy Systems, 7(5):608–616, Oct. 1999. [83] N. E. Nawa, T. Hashiyama, T. Furuhashi, and Y. Uchikawa. Fuzzy logic controllers generated by pseudo-bacterial genetic algorithm. In Proceedings of the IEEE Int. Conf. Neural Networks (ICNN97), pages 2408–2413, Houston, 1997. [84] O. Nelles. Nonlinear Systems Identification with Local Linear Neuro-Fuzzy Models. PhD thesis, TU Darmstadt, Germany, 2000. [85] Y. S. Ong and A. J. Keane. Meta-lamarckian learning in memetic algorithms. IEEE Transactions on Evolutionary Computation, 8(2):99–110, Apr. 2004. [86] Z. Petres, P. Baranyi, P. Korondi, and H. Hashimoto. Trajectory tracking by TP model transformation: case study of a benchmark problem. IEEE Transactions on Industrial Electronics, 54(3):1654–1663, 2007. [87] H. Pohlheim. The multipopulation genetic algorithm: Local selection and migration. Technical report, Technical University Ilmenau, 1995. [88] J. R. Quinlan. C4.5: Programs for machine learning. Morgan Kaufmann, San Mateo, CA, 1993. [89] I. Rechenberg. Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog Verlag, Stuttgart, 1973. [90] M. Riedmiller. Advanced supervised learning in multi-layer perceptrons - from backpropagation to adaptive learning algorithms. Int. J. Computer Standards and Interfaces, 16:265–278, 1994. [91] A. E. Ruano, C. Cabrita, J. V. Oliveira, and L. T. Kóczy. Supervised training algorithms for B-spline neural networks and neuro-fuzzy systems. International Journal of Systems Science, 33(8):689–711, 2002. [92] D. E. Rumelhart, G. E. Hinton, and R. J. Williams. Learning representations by backpropagating errors. Nature, 323:533–536, 1986. [93] J. E. Smith. Coevolving memetic algorithms: A review and progress report. IEEE Transactions on Systems, Man and Cybernetics, Part B, 37(1):6–17, Feb. 2007.

113

[94] B.G. Song, R.J. Marks II, S. Oh, P. Arabshahi, T.P. Caudell, and J.J. Choi. Adaptive membership function fusion and annihilation in fuzzy if-then rules. In Proceedings of the IEEE International Conference on Fuzzy Systems, pages 961–967, March 1993. [95] M. Sugeno. Fuzzy measures and fuzzy integrals: A survey. In M. M. Gupta, G. N. Sadiris, and B. R . Gaines, editors, Fuzzy Automata and Decision Processes, pages 89–102. North-Holland, Amsterdam–New York, 1977. [96] M. Sugeno, M. F. Griffin, and A. Bastian. Fuzzy hierarchical control of an unmanned helicopter. In Proc. of the 5th IFSA World Congress (IFSA’93), pages 1262–1265, Seoul, 1993. [97] T. Takagi and M. Sugeno. Fuzzy identification of systems and its applications to modeling and control. IEEE Trans. Syst. Man Cybern., 15(1):116–132, 1985. [98] A. N. Tikhonov and V. Y. Arsenin. Solution of Ill-posed Problems. Winston, Washington, 1977. [99] L.X. Wang. Fuzzy systems are universal approximators. In Proceedings of the IEEE International Conference on Fuzzy Systems, pages 1163–1169, March 1992. [100] P. Werbos. Beyond Regression: New Tools for Prediction and Analysis in the Behavioral Sciences. PhD thesis, Committee on Appl. Math., Harvard Univ., Cambridge, MA, USA, Nov. 1974. [101] E. Weyer and T. Kavli. The ASMOD algorithm. Some new theoretical and experimental results. Technical Report SINTEF Report STF31 A95024, SINTEF, Oslo, 1995. [102] R. Yager and D. Filev. Generation of fuzzy rules by mountain clustering. Technical Report MII-1318R, Machine Intelligence Institute, Iona College, New Rochelle, NY 10801, 1994. [103] J. Yen, L. Wang, and C.W. Gillespie. Improving the interpretability of TSK fuzzy models by combining global learning and local learning. IEEE Trans. on Fuzzy Systems, 6(4):530–537, 1998. [104] K. F. C. Yiu, S. Wang, K. L. Teo, and A. C. Tsoi. Nonlinear system modeling via knot-optimizing B-spline networks. IEEE Trans. on Neural Networks, 12:1013–1022, 2001. [105] L. A. Zadeh. Fuzzy sets. Inf. Control, 8:338–353, 1965. [106] L. A. Zadeh. Outline of a new approach to the analysis of complex systems and decision processes. IEEE Trans. Syst. Man Cybern., 3(1):28–44, 1973. [107] W. Zhang, D. Ma, H.-J. Zhang, B.-L. Wang, and Y.-T. Chen. An application of multipopulation genetic algorithm for optimization of adversaries’s tactics and strategies in battlefield simulation. In Proceedings of the Second International Conference on Machine Learning and Cybernetics, pages 1704–1707, Xi’an, November 2003. 114

[108] J. M. Zurada. Introduction to Artificial Neural Systems. West Publishing Co., St. Paul, 1992.

115