MŰSZAKI ÉS TERMÉSZETTUDOMÁNYI SZEKCIÓ

MŰSZAKI ÉS TERMÉSZETTUDOMÁNYI SZEKCIÓ

127

128

Műszaki és Természettudományi Szekció

Kiterjedéssel rendelkező autonóm robotok gyülekezése Bolla Kálmán1, Kovács Tamás2, Fazekas Gábor2 1 Informatika Tanszék, Kecskeméti Főiskola, GAMF Kar 2 Információ Technológia Tanszék, Debreceni Egyetem, Informatikai Kar Összefoglalás: A robot swarm intelligencia alapfeladatok közül az egyik legfontosabb a robotok gyülekezésének problémája. A szakirodalomban számos publikáció foglalkozik ezzel a témával, viszont amíg egyesek pontszerű robot reprezentációt használnak, mások a feladat megoldásához a szükségesnél több tudást feltételeznek. Ebben a cikkben bemutatunk egy olyan megoldást az összegyűlés problémájára, ami a robotoktól minimálist tudást, valamint csekély számítási kapacitást vár el. A kifejlesztett algoritmus kiterjedéssel rendelkező robotokra alkalmazható, ahol a robotok látótávolsága erősen limitált, az egyes egyedek egymástól megkülönböztethetetlenek, nem rendelkeznek memóriával, egymással nem kommunikálnak és nincs globális navigációs rendszerük. Megoldásunk helyességét MATLAB szimulációval bizonyítjuk, amely egyedi a robot swarm irodalomban, mivel sem szimulációt, sem konkrét roboton való megvalósítást eddig nem publikáltak. Abstract: In the present paper, we introduce two different algorithms for the two dimensional gathering problem for synchronous, fat (disk-like) robots with no global navigation or communication, and with limited visibility. One of the algorithms is a slightly modified version of the local smallest enclosing circle (local SEC) algorithm. The other algorithm uses a new method of the gathering: the robots move towards the furthest visible robot, and the robots on the perimeter of the visibility graph apply a bigger extent of move than the others. With the help of computer simulations, the two proposed algorithms are shown to be applicable for the gathering problem above and they perform better than the earlier simple SEC algorithm developed for point like robots. Kulcsszavak: robot swarm, robot swam alapfeladatok, autonóm robotok gyülekezése Keywords: mobile robot swarm, gathering problem, fat robots

1. Bevezetés Az utóbbi időben a robotika egyik kedvelt területévé vált a robot swarm feladatok lehetséges megoldásainak kutatása autonóm elosztott rendszerekre. Jelenlegi swarm intelligencia alapfeladatra adott megoldások vagy nem megfelelőek vagy csak elméleti eredmények, amelyek a gyakorlatban nem, vagy nehézkesen alkalmazhatóak. Eddig leginkább kutatott alapfeladatok: robotok egyetlen pontba gyülekeznek (vagy a lehető legkisebb területre) [1-10], területbejáró algoritmusokat alkalmaznak egy bázispontból indulva [11], hasznos részecskéket (pl.: táplálék) gyűjtenek be különböző megoldásokkal ([12-13]). Jelenlegi munkánkban a gyülekezés problémájára koncentrálunk egy akadálymentes környezetben. A gyülekezés azt jelenti, hogy tetszőleges alakzatból egyetlen pontba kell a robotoknak találkozniuk véges idő alatt. Egyszerű változata a problémának egy konvergencia feladat, ahol szükségünk van annak a területnek az átmérőjére, ahol elhelyezkednek a robotok, és csak ezt az átmérőt kell csökkenteni az idő előrehaladtával. Viszont ez a feladat számos esetben nem megoldható [1]. Olyan megoldás, ami a robotokon fut autonóm módon, nagyban függ a robot képességeitől, így megadjuk a feladat megoldása szempontjából fontos képességeket: 129


· · · · · ·

rendelkezik memóriával vagy nem, szinkron vagy aszinkron működésű, globális navigációja van közös koordináta rendszerrel vagy nincs, limitált látótávolság vagy az egész környezetet belátja, tudnak e kommunikálni a robotok egymással vagy sem, pontszerű a robot vagy kiterjedéssel rendelkezik.

A legtöbb gyülekezési algoritmust feledékeny (memóriával nem rendelkező) robotokra fejlesztették ki globális navigáció használata nélkül. A feledékenység azt jelenti, hogy a robot nem tud visszalépni az előző pozíciójába, mivel csak az adott pillanat érzékelései alapján dönt, az előző lépést nem tudja eltárolni. Tipikusan egy gyülekezési algoritmusban a következő lépéseket ismétlik egymás után: · · ·

Look: látható robotok pozíciójának meghatározása Calculate: következő pozíció számolása a Look alapján Move: mozgás a kiszámított pozíció felé

Szinkron működés esetén a robotok ezeket a lépéseket egyszerre hajtják végre egy szinkronjel hatására (vagy belső szinkron segítségével). Egy aszinkron modellben azonban a robotok különböző időpontokban indíthatják a lépéseiket attól függően, hogy mikor fejezték be a folyamatot. Ebben az esetben egy Wait lépés is beékelődik a Move és Look lépések közé. Kézenfekvő megoldásnak tűnik a gyülekezési problémára egy súlypont számolásán alapuló (COG – Center Of Gravity) algoritmus. Cohen és Peleg [2] bebizonyította a GOG algoritmus működését (nem limitált látótávolságra, tetszőleges alakzatból kiindulva, szinkron működés esetén). Cieliebak és társai [3] COG helyett a látható robotokra legkisebb ráhúzható kör középpontja felé mozdulást alkalmazta (SEC - Smallest Enclosing Circle), és ezzel az algoritmussal megoldást adott pontszerű robotok aszinkron gyülekezésére, ahol a robotok feledékenyek és nincs látótávolság korlátozás. Az előbb említett algoritmusokkal megoldást kapunk a gyülekezés problémájára pontszerű és nem limitált látótávolságú robotok esetén, azonban szükségessé vált, hogy a valóságban is megvalósítható modellek felé forduljanak. Ando és szerzőtársai [4] kifejlesztettek pontszerű robotokra egy szinkronműködésű algoritmust, ahol a robotok csak limitált látótávolsággal rendelkeznek. Itt be kell vezetnünk a láthatósági gráf fogalmát, ami az alapját jelenti a limitált látótávolságot feltételező megoldásoknak. A gráf csomópontjai jelentik a robotokat, az élek pedig két robot közötti kapcsolatot abban az esetben, ha azok látják egymást. Habár ők is SEC algoritmust használtak, minden egyed más középpont felé mozdul el, mert csak az adott robot által látható egyedekre számolódik ki. Ezen kívül minden robotmozgás limitálva van, mivel a sikeres gyülekezéshez elengedhetetlen, hogy a láthatósági gráf ne szakadjon meg. A lokális SEC algoritmusuk működését szinkron esetre bizonyították be. Később Flocchini [5] és Souissi [6] társaikkal együtt mutattak be limitált látótávolság mellett egy aszinkron megoldást. Azonban itt feltételezték, hogy a robotok az irányultsággal is tisztában vannak (pl.: van rajtuk iránytű), így ők egyfajta globális navigációs rendszert használtak a probléma megoldásához. A szakirodalomban az egyik legfrissebb szinkron és limitált látást alkalmazó megoldás Degener nevéhez [7] fűződik, aki a COG és SEC helyett lokális konvex sokszög alapján határozza meg a következő lépést. Ebben a megoldásban nincs globális navigáció, viszont a

130

Műszaki és Természettudományi Szekció kommunikáció engedélyezett, így a robotok meg tudják osztani egymással jövőbeni lépésüket. A következő lépés a gyakorlati megvalósítás felé, hogy elhagyjuk a pontszerű robot reprezentációt és kiterjedéssel rendelkező robotreprezentációt használunk, ahol a robotokat zárt alakzatként értelmezzük, egy középponttal és Rs sugárral. Azonban ennek a módosításnak komoly következményei vannak: például a robotok nem képesek egyetlen pontba gyülekezni, így az eredeti feltevést meg kell változtatnunk. Másik probléma, hogy egy robot blokkolni tudja egy másik robot mozgását, ami igaz a láthatóságra is mivel az egyedek nem átlátszóak. Ezután felmerül a kérdés, hogy hogyan tudjuk definiálni a gyülekezést kiterjedéssel rendelkező robotokra? Czyzowicz és társai [8] ezt a következőképpen definiálták: · ·

a zárt alakzatok kontakt gráfja összefüggő, és mindegyik robot látja a másikat

Hozzá kell tennünk, hogy ők legfeljebb 4 robotra adták meg a gyülekezést, viszont több robot esetén a definíció második része már nem teljesíthető. Így a mi definíciónk szerint akkor tekintjük a swarm-ot összegyűltnek, ha már kialakult a kontakt gráf. Cord-Landwehr [9], később pedig Chaudhuri [10] mutattak be egy olyan algoritmust, ami tetszőleges alakzatból hozta létre a kontakt gráfot, ezen kívül céljuk volt az is, hogy a létrejött alakzat a lehető legtömörebb legyen. A felhasznált modellben a robotok rendelkeztek globális navigációval és a környezetet is teljesen belátták, ami azt jeleneti, hogy a többi robotot átlátszónak tekintették. Jelenlegi munkánkban olyan gyülekezési algoritmusokkal foglalkozunk, ami feledékeny, kiterjedéssel rendelkező, limitált látótávolságú robotokra lett kifejlesztve. Továbbá nincs szükség globális navigációra és kommunikációra sem. A meglévő megoldások közül teszteltük a lokális SEC algoritmust módosítás nélkül és egy általunk módosított változatát is. Valamint bemutatunk egy saját fejlesztésű algoritmust, ami jobb megoldást ad az eddig fellelhetőkkel szemben. A következő, 2. fejezetben részletesen bemutatjuk saját megoldásunkat, a 3. fejezetben pedig a szimulációk és a tesztek eredményeit. Végül utolsó fejezetünkben összefoglaljuk az elért eredményeket.

2. A kifejlesztett gyülekezési algoritmus Saját gyülekezési algoritmusunk szinkronműködést feltételez, ahol a robotok kiterjedéssel rendelkeznek és nem átlátszóak. Továbbá a gyakorlati megvalósítás szempontjából a robotoknak limitált a látótávolsága és nincsenek globális navigációs rendszerrel felszerelve. Ezen kívül nem rendelkeznek memóriával és az egyes egyedek nem azonosíthatóak. Célunk, hogy a felsorolt minimális tudással is végrehajtható gyülekezési algoritmust készítsünk. Természetesen feltételezzük, hogy a láthatósági gráf összefüggő az algoritmus indításakor. Legyen R={r1,…,rn} a robotok halmaza és ri(t) az i-dik robot pozíciója t időpillanatban. Minden robotot egy zárt lemezként értelmezünk, ahol Rs a robot sugara és V a láthatósági sugár. Jelentős probléma a kiterjedéssel rendelkező robotok esetében, hogy a robotok takarhatják és blokkolhatják egymást mozgás közben. Tipikus probléma, hogy a csoport külső részén levő robotok blokkolják a belsőket. Ez a probléma nem megoldható a SEC alapú algoritmusokkal (később ez demonstrálva lesz a 3. fejezetben). Alapötletünk, hogy a robotok a látható legtávolabbi robot felé mozdulnak, amely egy eddig nem alkalmazott megoldás és részben megoldást nyújt a blokkolás problémájára is. A megvalósítás érdekében

131

Műszaki és Természettudományi Szekció kettéosztottuk a robotok halmazát, ahol megkülönböztetünk periméter és belső robotokat. Periméter robotnak nevezzünk minden olyan egyedet, ami csak 120 fokos szögben lát szomszédos robotokat (tehát a swarm szélén helyezkedik el) (1. ábra). Jelölje RP a periméter robotok halmazát, így megkaphatjuk a belső robotok halmazát (R/RP) is, ezt jelölje RI. A robotok halmazát minden egyes ciklusban felbontjuk az előbb említett részhalmazokra.

1. ábra: Periméter robot. Gyülekezési algoritmusunk célja a következő: a periméter robotokat szeretnénk a belső robotok felé mozdítani. Azonban önmagában az algoritmus működése azt eredményezné, hogy a láthatósági gráf felbomlik, és különböző csomópontok alakulnak ki. Viszont a belső robotok mozgása és egy korlátozó algoritmus segítségével ez a probléma kiküszöbölhető. Az algoritmusunk három fő feladatra bontható fel, amelyeket minden egyes lépésben végrehajtanak a robotok: Look, Compute, Move. A Look fázisban a robotok összegyűjtik a látható szomszédjaikat t időpillanatban (RVi(t)-vel jelöljük a későbbiekben), amit az algoritmusunkban GetVisibleRobots(R) függvény hajt végre, ahol a bemenet a robotok halmaza. Compute fázisban meghatározza a figyelő robot magáról, hogy periméter vagy belső robot, ezután kiszámolja a legtávolabbi pozícióját ( r di ( t ) ) a GetFurthestVisbleRobot(RVi(t)) függvény segítségével. A begyűjtött információk alapján mindegyik egyed meghatározza a célvektort ( g ) a következő képlettel: g = c

r di ( t ) - r i ( t ) V

( r di (t ) - ri (t ) ) ,

(1)

ahol c-t 1-nek vagy 1/2-nek választottuk attól függően, hogy periméter vagy belső robotról van szó. A konstans értéke azért különbözik a két esetben, mert a peremen található egyedek körül kisebb sűrűségben helyezkednek el robotok, így nagyobb sebességgel szeretnénk őket a többiek felé terelni. Viszont a belső robotok esetében nincs szükség nagy lépésekre, mivel az ő feladatuk az, hogy bevárják a külső robotokat, és belül a lehető legegyenletesebben helyezkedjenek el.

132


2. ábra: Periméter (a) és belső robot (b) lépései. A láthatósági gráf megszakadásának elkerülése érdekében az Ando [4] féle SEC algoritmus limitálja a célvektort, ezért a mi megoldásunkban is alkalmazzuk ezt a limitációs eljárást. 2.1. Blokkolási probléma feloldása A kiterjedéssel rendelkező robot reprezentáció hátránya, hogy a robotok akadályoztatják egymást mozgás közben, így a robotok úgynevezett holdpont helyzetbe kerülnek. Ennek feloldása egy egyszerű módszerrel megvalósítható: a blokkolt robot eredeti célvektorát úgy módosítjuk, hogy érintő irányba történik az új elmozdulás (3. ábra), így a robot közelebb kerül az eredeti célhoz. A módszert csak akkor alkalmazzuk, ha egy blokkoló robot van (a blokkoló robotokat a GetBlockers( r i ,RVi) függvény gyűjti össze), ha azonban nincs blokkoló robot, akkor nem kell módosítani, viszont ha egynél több van nem lépünk sehova.

3. ábra: Megoldás a blokkolás problémájára.

133


2.1. Gyülekezési algoritmus Ebben a részben megadjuk a gyülekezési algoritmusunk pontos leírását szinkron működésű robot swarm-okra. Az algoritmusban a ComputeMovementLimitation eljárás számolja az Ando féle mozgáslimitációt, a TangentialDirection pedig a kikerülést. Végül a mozgás vektorát m-el jelöljük. · ·

RVi(t) = GetVisibleRobots( r i ( t ) ,R) r di ( t ) = GetFurthestRobot(RVi(t))

·

ha

r di ( t )

g = c

‫ א‬RP(t) akkor c = 1 különben

r di ( t ) - r i ( t )

c = 1

( r di (t ) - ri (t ) )

· ·

m

·

Bi(t) = GetBlockers( r i ( t ) ,RVi(t))

·

ha Bi(t) 1-nél több elemet tartalmaz akkor

·

különben ha Bi(t) 1 elemet tartalmaz akkor

·

különben az i-dik robot

V

2

= ComputeMovementLimitation( r i ( t ) ,RVi(t), g )

m

m m

=

ri

= TangentialDirection( r i ( t ) ,Bi(t),

g

)

-el lép tovább

3. Teszt, futási eredmények Algoritmusunk helyes működését MATLAB szimulációval bizonyítottuk, ahol teszteltük a három különböző eljárást (SEC, SEC kikerüléssel és az új algoritmus) különböző kezdőállapotokból és különböző robotszámokkal egészen N=200 robotig. Először a SEC algoritmussal valósítottuk meg a gyülekezést, ami eredetileg pontszerű robotokra lett kifejlesztve. Ezután kiegészítettük a kikerülési eljárással (2.1-es alfejezet) annak érdekében, hogy a blokkolást elkerüljük, végül pedig a saját algoritmusunkat teszteltük. A három algoritmust N=12,25,50,100,200 robotszámú swarm-okra alkalmaztuk és minden esetet 5 különböző kezdőpozícióról indítottuk. Az algoritmusok futása akkor áll le ha a robotok már nem lépnek többet, tehát a swarm összegyűlt. A 4. ábrán látható az N=200 eset egy lehetséges kiinduló pozíciója és a három gyülekezési algoritmus végeredménye, ahol jól látható a kontakt gráf kialakulása.

134


4. ábra: A gyülekezési algoritmusok eredménye N=200 robotszám esetén. (a) mutatja a kezdőállapotot, (b) eredeti Ando algoritmust, (c) Ando algoritmust kiegészítve a kikerüléssel. Végül (d)-n láthatjuk a saját algoritmusunk futásának eredményét. Végül az 5. ábrán láthatjuk a szimulációink halmozott eredményeit, ahol mértük a gyülekezéshez szükséges időt (5/a) a kiinduló állapottól az algoritmus futásának a végéig, valamint a legnagyobb átmérőt (két legtávolabbi robot távolsága) a kialakult kontakt gráfban (5/b). Jól látható, hogy nincs szignifikáns különbség az egyes algoritmusok között az idő tekintetében, azonban a legnagyobb átmérő jóval kisebb az új algoritmus esetében. A változás jól látható a kikerüléssel módosított SEC algoritmusnál is, tömörebb alakzatot lehetett elérni. SEC algoritmus esetében fontos megjegyezni, hogy bizonyos esetekben a gráf megszakadt, viszont a másik két algoritmus esetében ez a probléma nem állt fenn.

135


5. ábra: Az átlagos, gyülekezéshez szükséges idők (a) és a legnagyobb átmérő alakulása a kontakt gráfban (b).

4. Következtetések Jelenlegi munkánkban bemutattunk egy új és hatékony megoldást kiterjedéssel rendelkező és limitált látótávolságú mobil robotok gyülekezésére. Az algoritmusunkat MATLAB szimulációval mutattuk be és teszteltük le.

Irodalomjegyzék [1] [2]

[3]

[4]

[5] [6]

[7]

[8] [9]

136

Prencipe, G.: Impossibility of gathering by a set of autonomous mobile robots. Theoretical Computer Science 384, 222–231 (2007) Cohen, R., Peleg, D.: Robot Convergence via Center-of-Gravity Algorithms. In:Kralovic, R., Sykora, O. (eds.) SIROCCO 2004. LNCS, vol. 3104, pp. 79–88. Springer, Heidelberg (2004) Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Solving the Robots Gathering Problem. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 1181–1196. Springer, Heidelberg (2003) Ando, H., Suzuki, I., Yamashita, M.: Formation and agreement problems for synchronous mobile robots with limited visibility. In: 1995 IEEE International Symposium on Intelligent Control, pp. 453–460. IEEE Press, New York (1995) Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous robots with limited visibility. Theoretical Computer Science 337, 147–168 (2005) Souissi, S., Défago, X., Yamashita, M.: Using Eventually Consistent Compasses to Gather Oblivious Mobile Robots with Limited Visibility. In: Datta, A.K., Gradinariu, M. (eds.) SSS 2006. LNCS, vol. 4280, pp. 484–500. Springer, Heidelberg (2006) Degener, B., Kempkes, B., auf der Heide, F.M.: A local O(n2) gathering algorithm. In: SPAA 2010: Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures, pp. 224–232. ACM, New York (2010) Czyzowicz, G.J., Gasieniec, L., Pelc, A.: I Gathering few fat mobile robots in the plane. Theoretical Computer Science 410, 481–499 (2009) Cord-Landwehr, A., Degener, B., Fischer, M., Hüllmann, M., Kempkes, B., Klaas,A.,


[10]

[11] [12]

[13]

Kling, P., Kurras, S.,Martens, M., auf der Heide, F.M., Raupach, C., Swierkot, K., Warner, D., Weddemann, C., Wonisch, D.: Collisionless Gathering of Robots with an Extent. In: Cerna, I., Gyimothy, T., Hromkovic, J., Jefferey, K., Kralovic, R., Vukolic, M., Wolf, S. (eds.) SOFSEM 2011. LNCS, vol. 6543, pp. 178–189. Springer, Heidelberg (2011) Gan Chaudhuri, S., Mukhopadhyaya, K.: Gathering Asynchronous Transparent Fat Robots. In: Janowski, T., Mohanty, H. (eds.) ICDCIT 2010. LNCS, vol. 5966, pp. 170–175. Springer, Heidelberg (2010) Cohen, R., Peleg, D.: Local Spread Algorithms for Autonomous Robot Systems. Theoretical Computer Science 399, 71–82 (2008) Valdastri, P., Corradi, P., Menciassi, A., Schmickl, T., Crailsheim, K., Seyfried, J., Dario, P.: Micromanipulation, Communication and Swarm Intelligence Issues in a Swarm Microrobotic Platform. Robotics and Autonomous Systems 54, 789–804 (2006) Nouyan, S., Alexandre Campo, A., Dorigo, M.: Gathering Path formation in a robot swarm Self-organized strategies to find your way home. Swarm Intelligence 2(1), 1– 23 (2008)

Szerzők Bolla Kálmán: Informatika Tanszék, Kecskeméti Főiskola GAMF Kar, Izsáki út 10., E-mail: [email protected]. Dr. Kovács Tamás: Informatika Tanszék, Kecskeméti Főiskola GAMF Kar, Izsáki út 10., Email: [email protected]. Dr. Fazekas Gábor: Információ Technológia Tanszék, Debreceni Egyetem Informatikai Kar, Egyetem tér 1., E-mail: [email protected].

137


Hajlított rugó idomok ellenőrzése vizuális burok alapú 3D rekonstrukcióval Kátai-Urbán Gábor1, Megyesi Zoltán1, Pintér István1 1 Informatika Tanszék, Kecskeméti Főiskola, GAMF Kar Összefoglalás: Hajlított rugóidomok minőségbiztosítási ellenőrzése nehézkes manuális mérési eszközökkel, ezért bemutatunk egy automatikus vizuális burok alapú 3D rekonstrukciós eljárást. A rendszer több kamerát és fényforrást tartalmazó mérő cella adatainak felhasználásával, optikai úton határozza meg a rugó idomok 3D tulajdonságait. A vizuális burok alapú módszerek hagyományosan a kameraképeken szegmentált objektumokból állítják elő a 3D modellt. A bemutatásra kerülő eljárás, ezen információk mellett, a pontszerű fényforrással megvilágított objektum árnyékképét is felhasználja a rekonstruálásra. A rekonstrukció alapvető feltétele a kamerák és fényforrások külső és belső paramétereinek pontos meghatározása, amelyre új kalibrációs folyamatot írunk le. Abstract: Industrial quality control of metal spring parts is problematic with both automatic and manual methods. We present an automatic 3D reconstruction and verification system for spring parts utilizing a Visual Hull based reconstruction method that uses both cameras and light sources to measure the 3D properties of the objects. While Visual Hull based methods normally use only cameras to gain visual information, the presented method is capable of using light sources and shadows to increase the amount of visual information. The calibration of this new visual system is also presented in this article. Kulcsszavak: 3D, mérés, rekonstrukció, vizuális burok, árnyék, rugó Keywords: 3D, measurement, reconstruction, visual hull, shadow, spring

1. Bevezetés Az ipari informatika alkalmazásai között egyre nagyobb szerepet játszik a gyártott elemek vizsgálata előre meghatározott szempontok alapján. Gyakori igény a száz százalékos ellenőrzés, vagyis valamennyi legyártott elem ellenőrzése. Ennek kivitelezése természetesen csak automatizált ellenőrző rendszer képes, amely valamilyen szenzorból és a szenzorból érkező adatokat elemző szoftverből állnak, gyakran kiegészítve visszacsatolással a gyártási folyamatba (ilyen visszacsatolás például hibás elem gyártása esetén a gyártó-sor leállítása). Az automatizált ellenőrző rendszerekben gyakran használnak ipari kamerákat is, amelyek megbízható képfeldolgozó szoftverekkel sokoldalú ellenőrzés elvégzésére képesek. Azonban a mai ipari képfeldolgozó szoftverek zöme csak a 2D ellenőrzéseket támogat, ami sok esetben kevésnek bizonyul. Ilyen esetnek számít a rugó idomok vizsgálata. Ezek kamerás ellenőrzése kimondottan nehéz, a rugók sokfélesége és térbeli kiterjedése miatt. A tipikus rugó fajták (nyomórugó, húzórugó, torziós rugó és hajlított idomok, lásd 1. ábra) mindegyike külön ellenőrzési mechanizmust igényel, azonban a hajlított idomok esetében az alak és a térbeli tulajdonságok kiemelkedően fontosak. Ezen idomok alkalmazása megköveteli, hogy a rugók alakja, kezdő és végpontja a 3D térben legfeljebb a tizedmilliméter tört részével térjen el az előírástól.

138


1. ábra: Rugó fajták, balról jobbra, fentről lefele: nyomórugók, húzórugók, torziós rugók, hajlított idomok.(forrás:Tatabányai Rugógyártó Kft.) Jelenleg nincs kellő megbízhatóságú automatikus ellenőrző rendszer a hajlított idomok vizsgálatára, ezért ma egy rugó ellenőrzésére 3D formákat (kalibereket) készítenek (lásd 2. ábra), amelyek egy-egy irányból képesek csak ellenőrizni a legyártott rugókat. Célunk egy olyan ellenőrző rendszer megalkotása volt, amely képes hajlított rugó idomok térbeli mérésére, modellezésére és ellenőrzésére.

2. ábra: Különböző rugó idom ellenőrző kaliberek (forrás:Tatabányai Rugógyártó Kft.). A rugóidom tükröződő felszínnel rendelkező anyaga miatt a felület rekonstrukciós módszerek helyett térfogat rekonstrukciós módszert választottunk. Ezek közé tartozik a Vizuális Burok alapú rekonstrukció [1], amely több kamera nézet alapján a térnek csak azt a részét hagyja meg, amely az összes nézetben az objektumra esik. Kihasználva a testek hengeres alakjának ismeretét a kivágott térfogat modellre hengeres rugó modell illeszthető [2]. A vizuális burok alapú módszerek hátránya, hogy sok kamera nézetre van szükség a jó eredményhez. Bemutatunk egy vizuális burok alapú módszert, amely kamera képek mellett fényforrásokat alkalmaz, hogy elérje a kívánt kamera számot. A rekonstrukcióhoz az optikai elemeket (kamerák és fényforrások) kalibrálni kell. Ebben a cikkben bemutatunk egy új eljárást több kamerás rendszerek térbeli kalibrálására. A megalkotott rendszer tulajdonságait az 2. fejezetben tárgyaljuk, a 3. fejezetben a fényforrásokat felhasználó vizuális burok módszert ismertetjük, míg a 4. fejezetben az optikai elemek kalibrálását ismertetjük. Ezután eredményeket mutatunk be és összegezzük tapasztalatainkat az 5. fejezetben.

139


2. Rendszer A hajlított rugó idomok vizsgálatára kialakított mérő cella négy fő részből áll (lásd 3. ábra): mérési térből, kamerarendszerből, fényforrásokból és a számítási egységből. A mérési tér kialakításnál a hajlított idomok 500mm x 500mm x 100mm-es maximális méretét kell figyelembe venni. Itt nem csak az ekkora munkadarabok homogén hátterét kell biztosítanunk, hanem az árnyékképeknek is erre a háttérre kell esniük.

3. ábra: A rendszer blokkvázlata A nagy felbontású ipari kamerák a mérési teret figyelik. Oldalsó állásban négy darab 3840 x 2748 pixel felbontású kamera veszi a munkateret. Ezt kiegészítettük két darab felső pozícióban elhelyezett hasonló felbontású kamerával, amelyek a munkatér felét - felét veszik, így ezen nézet felbontását közel a duplájára növelhetjük. A mérési tér háttérvilágítása LED szalagokkal történik, amit különböző fény diffúzor anyagokkal lehet homogénné tenni. A munkatér körül 17 darab nagy fényerejű pontszerű LED fényforrás került elhelyezésre. Ezeket külön - külön alkalmazva különböző árnyékképeket nyerhetünk a rugó idomról. A számítási egység irányítja a képkészítést, a fényforrások működését és végzi a képfeldolgozási műveleteket. A mérőcella gyártás közben történő ellenőrzésre készül, ezért laboratóriumi körülményeket nem feltételezhetünk, minden részegységet ipari kivitelűre kellett tervezni, amelyek ellenállnak kisebb fizikai erőhatásoknak. Ennek megfelelően ipari kivitelű IDS UEye UI-1490SE USB kamerák és hibatűrő, hosszú élettartamú LED megvilágítások kerültek beépítésre. A mérőcella kivitelezését a Mevisor Kft végezte (lásd 4. ábra).

4. ábra: A megépített mérőcella (kivitelezés: Mevisor Kft).

140


3. Vizuális burok Több eljárás is ismert a képi információk alapján történő 3D modellalkotásra. Ezeket a felhasznált információ alapján “shape-form-X” kategóriákba sorolhatjuk. A Vizuális Burok eljárás a “shape-form-silhuett” alapú eljárás, mivel a modell előállításához az eredeti objektum kameraképeken detektálható körvonalát (sziluettjét) alkalmazza (feketével jelölve az 5/a. ábrán). Az eljárás bemenetét a térbeli objektumról több nézetből készített képek és a kamerák kalibrációs adatai képzik. A kalibrációs adatok azt írják le, hogy egy térbeli 3D pontot a kamera hogyan képez le a 2D képsíkjára. Az objektum körvonalának pontjait a kameraképekről visszavetítjük a 3D térbe. Ezek egy-egy a kamerától távolodva bővülő kúpot jelölnek ki a térben. Ahol a különböző nézetből származó kúpok metszik egymást, ott van az objektum a térben. Ezzel az eljárással a valós térbeli objektum konvex burkát kapjuk meg volumetrikus modellként. Fontos megjegyezni, hogy az objektum konkáv részeinek leírására nem alkalmas ez az eljárás. Mivel a hajlított rugó idomok nem tartalmaznak konkáv részeket, ez nem okoz problémát a jelen alkalmazásban. A rekonstruált modell a kamerák nézeteiből teljesen megegyezik az eredeti objektummal, viszont olyan nézetből, ahonnan nem volt kameránk, jelentkezik eltérés (lásd piros színnel az 5/b ábrán). A pontosságot úgy lehet növelni, ha a nézetek számát növeljük. Ehhez több kamerát kellene felhasználnunk, de ennek anyagi korlátai vannak. Viszont egy kamera költségén nagyságrendekkel több fényforrást tudunk alkalmazni. Ebből kiindulva módosítottuk a klasszikus vizuális burok alapú eljárást úgy, hogy a fényforrások használatával keletkezett árnyékképeket is fel tudjuk használni a rekonstruálás során.

5. ábra: Vizuális burok: a, sziluett képek előállítása; b, példa a visszavetítéskor keletkező hibára Ahhoz, hogy kameraként tudjuk használni a fényforrásokat, létre kell hozni egy egységes fényforrás képet. Mivel az árnyékok helyzete nem függ a kamera elhelyezésétől, minden kamerára megadhatunk egy sík-sík transzformációt (homográfiát), amellyel elő tudunk állítani egy olyan közös fényforrás képet, amelyen az árnyékok ugyanott látszanak. Ezek után meg kell határoznunk a fényforrások külső és belső kalibrációs paramétereit, hogy a visszavetítést el tudjuk végezni ezeken a képeken is. A fényforrás képek visszavetítése során nem az objektum árnyék sziluettjét használjuk fel, hanem azt ahol nincs árnyéka. A normál kameraképekkel előállított volometrikus modellt csökkentjük ott, ahol a fényforrás képen nem látszott árnyék, viszont a modellben objektumnak volt jelölve a térrész. Az így kiegészített eljárás simább és pontosabb felületeket eredményez a köztes nézetekből is.

141


4. Kalibráció A fent bemutatott vizuális burok alapú rekonstrukciós módszer pontossága nagyban függ az optikai eszközök pontos kalibrációjától. A sziluettek visszavetítéséhez a kalibrációs eljárás során meghatározott kamerák és fényforrások vetítési paramétereit használjuk fel.

4.1. Kamera kalibráció Egy kamera belső vetítési tulajdonságait a K kamera mátrixszal adható meg (1)

(1) , ahol a a döféspont, a kamera fókusztávolsága. Az elméleti kamera modell alkalmazásához elegendő a K mátrix, de a valóságban a lencsék gyakran sugár irányú torzítással módosítják a vetítést. Ezek kompenzálásához meg kell határoznunk a d torzítási vektort is. Ezek a paraméterek csak a kamera belső tulajdonságaitól függenek. Így amíg a fókusztávolság változatlan marad, a kamerák ezen paramétereit egymástól függetlenül meghatározhatjuk. Az alkalmazott kalibrációs eljárás Zhang [3] módszerén alapul. A módszer lénye, hogy egy síkon felvett pontok különböző nézetből készült képei alapján meghatározza a K mátrix és d vektor paramétereit. A síkbeli pontok felvételéhez papírlapra nyomtatott fekete-fehér sakktábla mintáról készítettünk felvételeket az összes kamerával, különböző nézetekből (6. ábra). A képeken detektált belő sarokpontok és a síkon ismert koordináták alapján az optimalizációs eljárás meghatározza a belső paramétereket.

6. ábra: Kamera belső kalibráció A rekonstrukció szempontjából fontos tudnunk, hogy a kamerák hol helyezkednek el a térben és milyen irányba néznek. Ezeket a külső paramétereket a t eltolás vektor és az R forgatás mátrix írja le. A kamerák külső paramétereit úgy szeretnénk meghatározni, hogy azonos koordinátarendszerbe kerüljenek, ami a mérési tér koordináta rendszere is lesz egyben. Ezért a külső kalibrációhoz szükséges 3D koordinátákat a mérési térben vesszük fel. Fontos szempont, hogy a pontok lehetőleg a tér közepén, változó magasságokban legyen elrendezve a pontosabb paraméter közelítés érdekében. A külső kalibrációs objektum saját tervezésű, direkt erre a feladatra lett kialakítva. A kameraképeken ellipszisként megjelenő, vékony száron elhelyezkedő gömböket választottunk a térbeli pontok kijelölésére, amelyek könnyen detektálhatóak (8/a. ábra). A pozíciójukat 3D koordináta mérőgéppel határoztuk meg. Az így ismert térbeli pozíciók és a képeken detektált ellipszisek középpontjai alapján a külső 142

Műszaki és Természettudományi Szekció paraméterek közelíthetőek.

4.1. Fényforrás kalibráció A fényforrásokat is felhasználtuk a vizuális burok előállításához. Így ezeknek is meg kell határoznunk a kalibrációs paramétereit. A belső paraméterek meghatározásához, a kamerákhoz hasonlóan, egy síkbeli objektum képét (árnyékát) kell felhasználnunk. Mivel a hagyományos papírra nyomtatott sakktábla mintának az árnyékképét nehezen tudtuk volna előállítani, más kalibrációs objektumot kellett terveznünk. Fontos, hogy a kialakított minta minél több, a kamera képeken pontosan meghatározható pontot tartalmazzon, amelyeket a fény és árnyék határvonalak egyértelműen elválasszanak. E mellett a robusztus, ipari kialakítás is elengedhetetlen, hogy az objektum síklapúsága ne változzon a mérés során. Az általunk megvalósított kalibrációs objektum mindezeknek megfelel: egy fémlemezen készítettünk mátrix szerűen furatokat (7. ábra). Ezeken a fény átjut és a sík mérőfelületen a perspektív torzulásnak megfelelően szabályosan elhelyezkedő ellipsziseket figyelhetünk meg. Az ellipszisek középpontját detektálni tudjuk, ezek lesznek a fényforrások képei.

7. ábra: Fényforrás belső kalibráció A fényforrások külső paramétereit is meg kell határoznunk, hogy a vizuális burok visszavetítésekor ezt fel tudjuk használni. Ennél a kalibrációs lépésnél is az elvárás az, hogy ugyanabban a koordináta rendszerben határozzuk meg a pozíciókat és az orienetációkat, mint amit a kamerák esetén felvettünk. Így a kamerák külső kalibrációhoz használt objektumát kell itt is alkalmaznunk (8/b. ábra).

8. ábra: a, Kamera külső kalibráció; b, Fényforrás külső kalibráció A mérési síkon ellipszisként megjelenő árnyékok középpontjai és a golyók térbeli pozíciója alapján a külső paraméterek meghatározhatók a fényforrásokra is.

143


5. Eredmények A leírt rendszer optikai eszközeinek kalibrációs pontosságát a meghatározott paraméterekkel visszavetített pontok és a valós 3D koordináták átlagos négyzetes különbségével mérjük. Az 1. táblázatban foglaltuk össze a kapott eredményeket. Optikai eszközök Kamerák Fényforrások

Átlagos visszavetítési hiba 0,096 mm 1,128 mm

1. táblázat: Kalibrációs pontossága A leírt módszerek segítségével rekonstruáltunk több rugó elemet. A 9. ábra egy hajlított rugó idomról készült mérés eredményét mutatja be különböző nézetekből.

9. ábra: Hajlított rugó idom 3D mérése (megjelenítés különböző nézetekből)

6. Következtetések Bemutattunk egy vizuális burok módszeren alapuló 3D mérő rendszert, amely kamerákat és fényforrásokat egyaránt használ a mérés folyamán. A mérő rendszert hajlított rugó idomok mérésére és ellenőrzésére terveztük, amit az eredmények között példával illusztráltunk. A rendszer által elkészített volmetrikus 3D modellen a mért tárgy tulajdonságai vizsgálhatók, valamint egy etalonhoz hasonlíthatók. A mérő rendszer pontossága fontos kérdés ezért bemutattunk egy megfelelő kamera kalibrációs eljárást amely a kamerákat és a fényforrásokat kalibrálja. A mérő rendszer teljes hibájának ellenőrzése azonban fontos jövőbeli feladat, ezen hibára jelenleg csak a kalibrációs hiba ismeretében tudunk felső becslést adni. A felülnézeti irányból az elméleti pontosság (a mérési terület és a kamera felbontás arányából számolva) +-

144

Műszaki és Természettudományi Szekció 0,052 mm, ezen azonban ront a kalibráció pontatlansága. Más nézetekből ez a pontosság +0,16 mm. Ez az elméleti pontosság lehetővé teszi a rendszer számára az ipari alkalmazást.

Irodalomjegyzék [1]

[2]

[3]

A. Laurentini, “The Visual Hull Concept for Silhouette-Based Image Understanding”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 16 Issue 2, February 1994, Page 150-162 I. Pintér, Z. Megyesi, G. Kátai-Urbán, „Estimation of geometrical features of wireforms using 3-dimensional image reconstruction data”, Proceedings of Factory Automation 2012, 21-22nd May, Veszprém, pp. 46-49. Z. Zhang, "A flexible new technique for camera calibration", IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(11):1330-1334, 2000.

Szerzők Kátai-Urbán Gábor: Informatika Tanszék, Kecskeméti Főiskola, GAMF Kar. 6000 Kecskemét Izsáki út 10., Magyarország. E-mail: [email protected] Megyesi Zoltán: Informatika Tanszék, Kecskeméti Főiskola, GAMF Kar. 6000 Kecskemét Izsáki út 10., Magyarország. E-mail: [email protected] Pintér István: Informatika Tanszék, Kecskeméti Főiskola, GAMF Kar. 6000 Kecskemét Izsáki út 10., Magyarország. E-mail: [email protected]

Köszönet a Tatabányai Rugogyártó KFT-nek az illusztrációk és az eredmények megosztásáért. Ezt a munkát a (GOP 1.1.1-09/1) Innovatív 3D OFF LINE, és a gyártást közvetlen ellenőrző és kiszolgáló ON LINE mérőberendezés kifejlesztése megnevezésű pályázat támogatta.

145


Parrondo paradoxon – avagy széllel szemben is lehet… Nagy Péter1, Tasnádi Péter2 1 GAMF, KEFO 2 TTK, ELTE Összefoglalás: A Parrondo paradoxon néven ismertté vált és sok tudományterülettel kapcsolatba hozható jelenség arra ad bizonyítékot, hogy léteznek olyan stabilan veszteséges stratégiák, amelyeket keverten játszva ─ akár véletlenszerű kevert stratégiával, akár valamilyen fix minta szerint keverve ─ az eredmény folyamatos, nagy nyereség lehet! A legkülönfélébb tudományterületeken adhatók meg olyan modellek, amelyek a fenti megfogalmazással izomorfak és izgalmas, teljesen új alternatívákat tárnak fel, ezek közül mutatunk be néhányat (játékelmélet, fizika, biológia, káoszelmélet, gazdaságtan). Abstract: Parrondo paradox is named after its creator, Spanish physicist Juan Parrondo, who discovered it, and can be described as: there exist pairs of games, each with a higher probability of losing than winning, for which it is possible to construct a winning strategy by playing the games alternately, even by randomly mixed strategy, even by fixed pattern. Parrondo's paradox is used extensively in game theory, and its application in engineering, economics (financial risk) , population genetics, control theory, study of the discretecontinuous interface, complex systems, diffusive transport processes, and gene dynamics & DNA, etc. Kulcsszavak: játékelmélet, véletlen kevert stratégia, Parrondo paradoxon, alkalmazások. Keywords: game theory, randomly mixed strategy, Parrondo paradox, applications.

1. Bevezetés A természettudományos törvények egy része valószínűségi megfogalmazásban jelenik meg és a mindennapok döntéshozatalaiban is fontos szerepet játszanak a valószínűségi megfontolások. Ezeknek a megfontolásoknak az egyik legkézzelfoghatóbb és legtisztább megjelenése a játékelméletben található, ezért cikkünket játékelméleti tárgyalással indítjuk. A játékelmélet megfogalmazása szerint egy játékos tiszta stratégiát játszik, ha valamilyen egyértelmű szabály alapján dönti el, hogy milyen lépésekre szánja el magát, tehát ebből a szabályból adott helyzetben mindig ugyanaz a lépés következik. Az ún. kevert stratégiás játékmód esetében a játékos a játék folytatásának különböző lehetőségei között előre meghatározott valószínűséggel választ, azaz az általa meghatározott valószínűségek szerint véletlenszerűen hozza meg a döntését. A játékelmélet szerint minden játékos számára mindig létezik optimális kevert stratégia, amelyet az ún. Nash-egyensúly határoz meg. A tudomány számtalan konkrét szituációban ─ a fizikától kezdve a biológiáig, a közgazdaságtól a szociológiáig ─ megmutatta, hogy adott helyzetben mindig valamilyen véletlenszerű kevert stratégia az optimális. Például az állatok táplálékkeresési mozgására irányuló megfigyelések azt mutatják, hogy egyes állatfajok (pl. ragadozó halak, albatroszok, majmok) nem egyszerű bolyongással (Brown-mozgással), hanem az úgynevezett Lévyeloszlást követve mozognak: ebben az eloszlásban a rövidtávú véletlenszerű bolyongást ritkán előforduló hosszabb lépések bontják meg. Ezt úgy is megfogalmazhatjuk, hogy a táplálékkeresők véletlenszerű kevert stratégiát alkalmaznak: a lokális, rövidtávon végzett bolyongást (kicsiny terület átfésülését) véletlenszerűen váltogatják a nagyobb léptékű, 146

Műszaki és Természettudományi Szekció határozottabb irányultságú mozgással (területváltás). A mikro-rendszereket leíró kvantumállapot a rendszer makroszkopikusan (klasszikus fizikai szituációkban) mérhető tulajdonságaihoz rendelhető állapotainak lineáris kombinációja, komplex amplitúdókkal súlyozott kevert állapot (az izgalmas és fundamentális eltérés az, hogy a valószínűségeket ezen amplitúdok négyzetei adják). Egyértelműen kijelenthető, hogy a kevert stratégiák a tudományokban és a mindennapi életben egyaránt kiemelt jelentőséggel bírnak. A kevert stratégiákra vonatkozóan Juan Parrondo a madridi egyetem fizikusa igen különös és döbbenetes felfedezést tett [1], ami erősen foglalkoztatja a legkülönbözőbb tudományterületek (például fizika, biológia, közgazdaságtan és szociológia) képviselőit. Azt a ma már Parrondo paradoxon néven ismertté vált állítást bizonyította, hogy két, stabilan veszteséges stratégiát keverten játszva ─ akár véletlenszerű kevert stratégiával, akár megfelelő fix minta szerint keverve ─ az eredmény folyamatos, nagy nyereség lesz! A Parrondo paradoxonnak számos megfogalmazása, illetve interpretációja ismert, talán egyik legszemléletesebb az előző bekezdésben leírt játékelméletei interpretáció, de mielőtt azt részletesebben tárgyalnánk (a 3. fejezetben), röviden szólnánk arról, hogy a saját kutatási területünkben miként jelent meg a paradoxon. Kérjük az Olvasót, hogy látogasson el a http://csodafizika.hu/parrondo oldalunkra, ahol a jelen cikkünk bővebb, részletes számolásokat tartalmazó elektronikus változatát találja, sok képpel, videóval, szimulációval és futtatható alkalmazásokkal, valamint a témához kapcsolódó link-gyűjteménnyel.

2. Káosz-szabályozás A káosz determinisztikus rendszerek szabálytalan, nem előrejelezhető, csak valószínűségi leírással jellemezhető mozgása (időváltozása). Fundamentális vonásai, mint a kezdeti feltételekre mutatott extrém érzékenység, valamint a permanens instabilitás miatt sokáig kizártnak vélték a kaotikus viselkedés szabályozását: „Egy kaotikus folyamat általában nem jósolható meg és nem is szabályozható. Nem jósolható meg, mert már egy kis zavaró hatás is a folyamat exponenciálisan növekvő perturbációját eredményezi. Nem szabályozható, mert a kicsiny zavarások csak más kaotikus állapothoz, nem pedig valamilyen stabil, megjósolható alternatívához vezetnek.” (Freeman Dyson: Engineers Dreams, 1988). Viszonylag új (mintegy másfél évtizedes) felismerés, hogy mégis van lehetőség a káosz regularizációjára. Fontos kiemelni, hogy a káosz szabályozásakor a rendszer dinamikai állapotát megszabó paraméterértékek mindvégig a kaotikus tartományban maradnak. Ezt igen könnyen ellenőrizhetjük, ugyanis a perturbációt megszüntetve a rendszer (egy rövid átmeneti szakaszt követően) ismét kaotikusan fog viselkedni. Az egyik első, gyakorlatilag megvalósíthatónak tűnő módszert Ott, Grebogi és Yorke (OGY-módszer) közölte a 90-es években. Mi is ezen módszer hatékonyságát vizsgáltuk különböző dinamikai rendszerekben, az alábbiakban az OGY–módszer egy változatát az ún. egyszerű arányos visszacsatolás (Simple Proportinal Feedback) algoritmust mutatjuk be egy explicite is tárgyalható rendszeren. Az SPF-módszer két alapfeltevése: (1) Alacsony dimenziójú kaotikus rendszerekben a kontrollparaméter értékének kicsiny megváltoztatásakor képződő új kaotikus attraktor nagyon hasonló az eredeti attraktorhoz. Így

147

Műszaki és Természettudományi Szekció az új attraktorból szerkeszthető új leképezés is nagyon hasonló az eredetihez. Feltételezzük, hogy a kontrollparaméter perturbálásának hatására az egydimenziós leképezés lokális jellemzői (pl. a munkapontba húzott érintők) egyszerűen csak párhuzamosan eltolódik az alkalmazott koordinátarendszer diagonálisa mentén (lásd az 1. ábrán). (2) A kontrollparaméter perturbációja – esetünkben a szabályozáshoz szükséges visszacsatolás nagysága – arányos a változó aktuális értékének a kívánt fixponttól való eltérésével. 1. ábra: az SPF módszer

A fenti két alapfeltevést és az ábra jelöléseit használva itt nem részletezett számolás után kapjuk, hogy:

*

pn = p + ¶pn ahol ¶pn = C × ¶xn

ì d x n +1 ( x n ) ïm = dxn ïï m , a m e ly b e n C = és í * ( m - 1) × K dx ( p ) ï ïK = dp * ïî p

*

p ,x

*

(p ) *

,

ahol ¶ p n az n-edik iterációs lépésben a perturbáció nagysága, p* a munkaponti kontrollparaméter-érték, x* a p*-hoz tartozó fixpont. Az x n + 1 ( x n ) = p × x n × ( 1 - x n ) ún. logisztikus leképezés egydimenziós, egyparaméteres, diszkrét leképezés, amely a káoszelmélet „állatorvosi lova”, mivel számos valódi dinamikai rendszerből származtatható modell és a kaotikus viselkedés minden lényegi vonásával rendelkezik, ugyanakkor azon kivételesen ritka modellek közé tartozik, amelyben a kaotikus jellemzők nem csak numerikusan (számítógéppel), de egzaktul (kézzel) is számolhatók. A C perturbációs paraméter a logisztikus leképezés esetén:

C =

m

(m

- 1) × K

p =

*2

(

× 2- p

(1 -

p

*

)

*

)

.

Ha például a választott kontrollparaméter munkapont-érték p * = 3 , 7 9 (ez a leképezés kaotikus tartományában van!), akkor C = 9 , 2 1 6 a perturbációs állandó egzakt értéke. A gyakorlatban azonban legtöbbször a leképezés konkrét alakja nem ismert, ezért a fenti értékeket numerikusan kell meghatároznunk a változó kimért idősorából. Ez esetben a lépések: 1. az egydimenziós leképezés rekonstrukciója; 2. a szabályozandó fixpont meghatározása; 3. a leképezés elkészítése a kontrollparaméter kicsit eltérő értékénél; 4. a leképezések m meredekségének numerikus meghatározása; 5. a fixpont eltolódásának numerikus előállítása és a K állandó kiszámítása; 6. a C perturbációs állandó kiszámítása m és K ismeretében.

148


A módszer tesztelésére a Maple programot használjuk, amely az egyik legelterjedtebben használatos és legmegbízhatóbb matematikai program. Az eljáráshoz először a mérést szimuláljuk, amellyel „legyártjuk” a mérési idősorokat (egy választott munkapont kontrollparaméter értéknél, és a kontrollparaméter kicsiny – néhány százalékos – eltérésénél). A szimulációval előállított idősorokat adatfájlokba tároljuk el, ezek a szabályozási algoritmus bemenetei. Egy konkrét futtatás eredményét ismertetjük az alábbiakban a logisztikus rendszer példáján. A választott munkapont kontrollparaméter érték p * = 3 , 7 9 (ez a leképezés kaotikus tartományában van), a kicsit eltérő kontrollparaméter érték pedig 3,752 (1%-os eltérés). A leképezés ( x n , x n + 1 ) adatpárokkal rekonstruált alakja látható a 2. ábrán. A fixpont közelítő meghatározása az x n + 1 - x n = m in . alapján történt, majd az m meredekség numerikus meghatározása következett a kapott fixpontban. A fixpontot meghatározva a kicsit eltérő kontrollparaméter értéknél is, 2. ábra: rekonstrukció majd a K együttható kiszámítása a változás numerikus deriváltjával. Az m és K ismeretében már előáll a C perturbációs állandó, amelyre C = 9 , 8 9 5 adódott (vessük össze a fentebb kapott egzakt értékkel!). Ezután indítsuk el a szabályozási algoritmust, az eredmény a 3. ábrán látható.

3. ábra: a logisztikus rendszer káosz-szabályozása Először hagytuk a rendszert szabályozás nélkül futni, jól látható a kaotikus viselkedés. A szabályozás figyelését n=100 lépésnél indítottuk, a program megvárta, míg a változó értéke választott (10%-os) mértékben véletlenszerűen megközelítette a fixpont munkapont-értékét, ez n=123 lépésnél következett be. Ekkor bekapcsolt a perturbációs algoritmus, ami azt jelentette, hogy a kontrollparaméter perturbációja végrehajtásra került minden olyan lépésben, ahol a változó értéke 1%-nál nagyobb mértékben eltért a munkapont értéktől. Látható, hogy a változó értékét sikerül a munkapont érték közelében tartani, a káoszt megszelídítettük! n=400 lépésnél a szabályozást leállítottuk, és megfigyelhetjük, hogy a perturbáció nélkül a rendszer néhány lépésen belül visszatér a kaotikus viselkedéshez, azaz valóban a kaotikus tartományban voltunk mindvégig. 149

Műszaki és Természettudományi Szekció Napjainkban már több káosz-szabályozási algoritmus létezik, ezek hatékonysága igen eltérő különböző kaotikus dinamikai rendszerekre. Ezen metódusok vizsgálata során egy teljesen újszerű nemperturbatív módszerre leltünk: a [4] oldalon olvasható cikk megmutatja, hogy két kaotikus viselkedésű rendszer között kapcsolgatva az eredő viselkedés szabályos lehet! Számunkra teljesen új információként kiderült, hogy ez lényegében az ún. Parrondo paradoxon egy lehetséges interpretációja.

3. A Parrondo paradoxon játékelméleti megfogalmazása A Parrondo paradoxon szemléletes bemutatásához térjünk tehát vissza a játékelméleti megfogalmazáshoz. Ismételten felhívjuk az Olvasók figyelmét, hogy a http://csodafizika.hu/parrondo oldalunkon minden alábbi megfontolás részletes számolását, kipróbálható szimulációját megtalálják. Tekintsünk [2] alapján két pénzfeldobásos szerencsejátékot, amelyekben minden egyes pénzfeldobásnál legyen a tét egységnyi. Mindkét játék során a nyereményt az határozza meg, hogy mit dobunk egy pénzérmével: fej esetén egységnyi a nyereségünk (+1), írás esetén egységnyi a veszteségünk (-1). Az A játék során csak egy pénzérmét használunk. Ha a pénzérme szimmetrikus (azaz a fej és írás azonos eséllyel jön ki), akkor a játék dobásonkénti várható nyeresége nyilvánvalóan 0, azaz sok játékot lejátszva az össznyeremény értéke közel nulla marad. Ha a pénzérme nem szimmetrikus, mondjuk ( p A - e ) valószínűséggel fej, ( 1 - p A + e ) valószínűséggel írás jön ki, akkor az egy dobásra eső nyereség várható értéke nem nulla, például p A = 0 , 5 és e = 0 , 0 0 5 esetén a játék hosszútávon ( A)

= - 0 , 0 1 ( e bevezetése talán nyilvánvalóan vesztes, a nyereség várható értéke n y 1 indokolatlannak tűnik, de a szakirodalom egyféle kontrollparaméterként használja).

A B játék kicsit bonyolultabb. Itt két pénzérmét használunk, és meghatározott szabály szerint dobunk vagy az egyikkel vagy a másikkal. Az egyik (B1) érmét „rossz” érmének nevezzük, mert feldobva ( p B 1 - e ) valószínűséggel ( p B 1 < 0 , 5 ) jön ki fej, és ( 1 - p B 1 + e ) valószínűséggel írás, a másikat (B2) pedig „jó” érmének, mert vele dobva ( p B 2

- e)

valószínűségű a fej ( p B 2 > 0 , 5 ) és ( 1 - p B 2 + e ) valószínűségű az írás. A játék során a B1 érmével akkor dobunk, ha a játék kezdete óta felhalmozott nyereségünk (a tetszés szerint választott) M egész számmal osztható, a B2 érmével pedig akkor, ha nem.

(Forrás: http://www.datagenetics.com/blog/august22012/index.html)

4. ábra: a B játék szimulációja 150

Műszaki és Természettudományi Szekció Példaként tekintsük az M=3, p B 1 = 0 , 1 , p B 2 = 0 , 7 5 és e = 0 , 0 0 5 (klasszikus ún. Abbott-féle) esetet. Noha nem annyira nyilvánvaló, mint az A játék esetén, a B játék is hosszútávon mindenképpen veszteséges, amint azt a számítógépes szimulációval kapott 4. ábrán látható. A szimulációs ábrákon több futtatás (sok lejátszott játék) átlagos eredményét jelenítjük meg. Világosan látszik, hogy a játék veszteséges, az egy játékra eső átlagos nyereség az egyenes meredekségéből becsülhető: pl. 50 játék után mintegy - 0 , 9 5 egység, míg 450 játék után nagyjából - 4 , 4 5 egység, így a meredekség, azaz a játékonkénti várható nyereség körülbelül ( -4, 45 ) - ( -0, 95 ) = -0, 00875 ! 450 - 50

Ennek oka az, hogy a játék során az egyes (0, 1 és 2) maradékot adó össznyeremény-állapotok nem azonos (1/3) valószínűségűek, hanem hosszútávon nem-egyenletes egyensúlyi eloszláshoz tartanak. A számítógépes szimulációval kapott eloszlások alakulását az 5. ábrán láthatjuk.

(Forrás: http://www.datagenetics.com/blog/august22012/index.html)

5. ábra: az egyes össznyeremény állapotok eloszlásának szimulációja Látható, hogy a 0 maradékosztályú össznyeremény-állapot ─ azaz a B1 „rossz” érmével való dobás ─ valószínűsége, nagyobb 1/3-nál, így kissé megnő a vesztes dobás esélye, ami végső soron a részletes számolásban azt eredményezi, hogy az egy játékra eső átlagos nyereség értékére - 0 , 0 0 8 6 8 adódik, ami igen jó egyezést mutat a szimulációból kapott fentebbi - 0 , 0 0 8 7 5 becslésünkkel. Van tehát két játékunk (stratégiánk), mindkettő stabilan (hosszútávon) veszteséges. Parrondo fantasztikus felfedezése az, hogy ha ezt a két játékot keverten játsszuk, akár véletlenszerűen döntve el, hogy éppen melyik stratégia szerint játszunk, akár valamilyen fix séma szerint felváltva játsszuk a két stratégiát, akkor hosszútávon stabilan nyereséges lehet! A várakozásokkal ellentétben nem az történik, hogy a játék veszteséges marad, esetleg időben változik a lefutása, hanem alapvető változás áll be: a két veszteséges játék (véletlenszerű, vagy adott séma szerinti) váltogatásával nyereséges játék alakulhat ki! Jelen cikkben egy véletlenszerű kevert stratégiát és egy fix minta szerinti kevert stratégiát tárgyalunk meg, továbbra is a p A = 0 , 5 , M=3, p B 1 = 0 , 1 , p B 2 = 0 , 7 5 és e = 0 , 0 0 5 (Abbottféle) esetet véve példaként. 151


Nézzük először a véletlenszerű kevert stratégiát: minden egyes dobás előtt véletlenszerűen választva, hogy az A játék szerint, vagy a B játék szerint játszunk, p valószínűséggel A játékot választjuk, (1-p) valószínűséggel pedig B játékot. Ekkor például p=0,5 esetén az egy dobásra eső átlagos nyeremény értéke + 0 , 0 1 5 7 lesz, tehát a két stabilan veszteséges játékot véletlenszerű kevert stratégiával játszva hosszútávon nyereségesek leszünk! A részletes számítások azt mutatják, hogy (az Abbott-féle esetben) 0 , 0 7 0 3 < p < 0 , 8 4 7 1 értékeknél a véletlenszerű kevert stratégia nyereséges, 0 < p < 0 , 0 7 0 3 é s 0 , 8 4 7 1 < p < 1 értékeknél veszteséges. Játsszuk most az A és B játékot felváltva, azaz az AB ismétlődő séma szerint. A számítások szerint az AB minta szerint játszva az egy dobásra eső átlagos nyereség értéke - 0 , 0 0 6 7 4 , tehát a játék ugyan továbbra is veszteséges marad, de mindkét eredeti játékhoz képest csökkent a veszteség, holott intuíciónk szerint a két játék ötvözetével a veszteségnek a két eredeti játék vesztesége között kellene lennie. Találhatók azonban olyan sémák, amelyek hosszútávon nyereségesek, például az összes nem homogén hármas csoport (pl. BAB), míg a négyes csoportok között egyaránt találhatók nyereségesek (ABBA) és veszteségesek (ABBB). A fentebb tárgyalt játékok on-line számítógépes szimulációját kipróbálhatjuk a [3] oldalon található java-applet segítségével. Egyszerre maximum 9 stratégia szimulációja futtatható. A 6. ábrán egy (Abbott-féle esetre végzett) futtatás képernyő-másolata látható: négy nyereséges stratégia (a BAB és az ABBA minták, valamint a p=0.5 és p=0.7 véletlenszerű kevert stratégiák) és öt veszteséges stratégia (az eredeti A és B játékok, az AB és ABBB minták, valamint a p=0.9 véletlenszerű kevert stratégia).

(A http://www.cut-the-knot.org/ctk/Parrondo.shtml oldal szimulációját használva.)

6. ábra: a játékok számítógépes szimulációja

4. Egy szemléletes fizikai modell A Parrondo paradoxon fizikai interpretációjaként egyszerű mechanikai modellt készítettünk. Vegyünk két párhuzamos (A és B) fogas-szalagot, amelyek egy egyenes mentén mozognak (legyen a jobbra irány a pozitív, a balra a negatív). Mindkét fogas-szalagon a fogak azonos L = 0 ,1 5 m távolságra vannak, adott t = 0 időpillanatban a két szalagon a fogak pontosan egybeesnek, a fogakat a könnyebb áttekinthetőség érdekében sorszámozzuk meg. (7. ábra) Az

152

Műszaki és Természettudományi Szekció A fogas-szalag egyenletes

0 ,1 m

s

alternáló mozgást végez, 0,5 s-ig +0, 4 m

s

sebességgel mozog jobbra. A B fogas-szalag viszont -0, 2 m

s

sebességgel (balra) mozog, majd 0,5 s-ig

sebességgel (jobbra) mozog, tehát a B szalag átlagsebessége is

0 ,1 m

s

, azaz

jobbra mutató eredő mozgása van. A fogas-szalagok egyikén teher helyezkedik el (a 7. ábrán kis karika szemlélteti). A két szalag között „kicserélődési kölcsönhatás” működik, ha a szalagokon két fog éppen szembekerül egymással, akkor a teher az aktuális szalagról (amelyen eddig volt) áttevődik a másik szalag szemben levő fogára. Kövessük nyomon a fogas-szalagok és a teher mozgását egy másodpercig. A kezdőpillanat az ábra felső részén látható, a teher éppen ekkor lépett át az A szalag n. fogáról a B szalag n. fogára. 0,5 s alatt az A szalag 0,05 m (1 segédvonalnyi) távolságot tesz meg jobbra, míg a B szalag 0,1 m (2 segédvonalnyi) távolságot tesz meg balra. Ekkor a B szalag n. foga, ahol a teher eddig volt éppen szembe kerül az A szalag (n-1). fogával, így a teher átkerül az A szalagra (az ábra középső része). A következő 0,5 s alatt az A szalag ismét 0,05 m (1 segédvonalnyi) távolságot tesz meg jobbra, míg a B szalag 0,2 m (4 segédvonalnyi) távolságot mozdul el szintén jobbra. Ekkor az A szalag (n-1). foga, ahol a 7. ábra teher eddig volt éppen szembe kerül a B szalag (n-1). fogával, így a teher átlép az B szalagra (az ábra alsó része). Egy másodperc alatt tehát mindkét szalag 0,1 m (2 egységnyi) távolságot mozdult el jobbra, ezzel szemben a teher 0,05 m (1 egységnyi) távolságot balra mozdult el! A szalagok és a teher mozgását hosszabb ideig figyelve azt látnánk tehát, hogy miközben mindkét fogas-szalag jobbra halad, a közöttük átlépegető (de a mozgás-egyenes irányában passzív) teher balra halad! A fogas-szalagos mechanikai modell könnyen átfogalmazható például mozgólépcsős változatra: fogas-szalagok helyett mozgólépcsők, jobb-bal mozgás helyett le-fel mozgás, fogak helyett lépcsőfokok és teher helyett utas. A mozgólépcsős változat on-line számítógépes szimulációja kipróbálható a [3] oldalon található java-applet segítségével. A lényeg a 8.a. ábrán foglalható össze: mind a világos (A), mind a sötét (B) mozgólépcső lefelé

153

Műszaki és Természettudományi Szekció halad. Az (A) lépcső egyenletesen lefelé, a (B) lépcső pedig alternáló mozgással: rövid ideig felfelé, majd ugyanannyi ideig kétszer akkora sebességgel lefelé mozog, így végül (B) átlagsebessége is lefelé mutat, méghozzá azonos értékű (A) sebességével. Ezt a szimuláció jól mutatja, ha a két mozgólépcsőt külön-külön üzemeltetjük. Tapasztalhatjuk, hogy a fekete golyóval reprezentált utas bármelyik lépcsőn lefelé mozog. Ha azonban egyszerre működtetjük a két mozgólépcsőt (a mozgásukat a fentebb leírt modell szerint szinkronizálva, tehát, hogy az alternáló lépcső n-edik foka a másik lépcső n-edik és (n-1)-edik foka között „rezeg”), akkor azt láthatjuk, hogy az utas felfelé halad a két egyenként lefelé haladó mozgólépcsőn (a 8.a. ábra jobb oldala).

8.a. ábra: mozgólépcsős mechanikai modell

8.b. ábra: alternáló potenciálok

Parrondo tulajdonképpen ilyen jellegű fizikai problémákon dolgozva ismerte fel a ma már a nevét viselő paradoxont. Az általa készített modellben az egyérmés A játék egy sima felszínű, adott lejtésszögű lejtőnek felel meg: a játékban fogadva hosszútávon csak veszíteni lehet, a lejtőről pedig mindig lefelé (balra) csúszik a tárgy. A kétérmes B játék olyan fűrészfogazott lejtőnek feleltethető meg, amelyen a fűrészfogak aszimmetrikusak, és szintén van egy balra mutató átlagos lejtése, így tárgy ezen a felületen is balra-lefelé mozog. Elképzelhetünk azonban el egy olyan lejtőt (8.b. ábra), amely sűrű egymásutánban változtatja a felszínét, először sima, majd átmegy fogazottba, majd újra kisimul, azaz a lejtő felszíne hol egyik, hol a másik alakot veszi fel. Megfelelően választva a hajlásszöget, a fűrészfogak aszimmetriáját és a váltogatások időzítését a tárgy jobbra-felfelé fog haladni a felszínét változtató lejtőn!

5. Alkalmazások, kitekintés Bár ─ mint látni fogjuk ─ Parrondo felfedezése valóságos lavinát indított el, a legkülönfélébb tudományterületek művelőinek intenzív kutatása számos publikációt eredményezett, sajnos magyar nyelven szinte egyáltalán nincs hozzáférhető irodalma. Az interneten (a Google és Yahoo keresőkkel) csak két oldalt találtunk: Jéky László 2000-ben a Magyar Tudományban megjelent [5] cikkét és Korpa Bálint 2005-ös [6] írását. Ezért is hoztuk létre a http://csodafizika.hu/parrondo oldalt. Létezik viszont angol nyelvű hivatalos oldal [7]. Az oldalon rengeteg fontos és érdekes információt találhatunk, külön felhívjuk a figyelmet a ’Useful links’ és a ’Publications’ menüpontokra, ez utóbbihoz tartozó lapon meggyőződhetünk arról, hogy a tudományterületek milyen széles skáláján folyik kutatás e témában. Az alábbiakban ─ egy bevallottan szubjektív ─ válogatást, áttekintést adunk a Parrondo paradoxonhoz kapcsolható érdekes kutatási eredményekből. Érdekes és fontos alkalmazási terület a biofizikában az ún. molekuláris (Brownian ratchet) 154

Műszaki és Természettudományi Szekció motorok vizsgálata. Két, külön-külön például balra mutató eredő erőhatású potenciált (lásd az ábrán) kapcsolgatva a mikrorészecskék statisztikus átlagban jobbra haladhatnak (a Parrondoféle lejtős kapcsolgatással való szoros analógia igen nyilvánvaló). A témáról magyar nyelven [8] cikket ajánljuk olvasásra. A Brown-motorok működését szimuláló java-applet található a [9] oldalon.

(Forrás:

http://online.physics.uiuc.edu/courses/phys498bio/spring09/LECTURE9/Slide1.gif)

9. ábra: Brown-motor működési elve A [10] tanulmány a Parrondo paradoxon egy genetikai alkalmazását adja az episztázis (az a jelenség, amikor egy gén hatása elnyomja egy másikét) modellezésében. Nagyon izgalmas eredmény az ún. Allison-keverék (Allison mixture) [11]. Képzeljünk el két véletlen számsorozatot, amelyek autokorrelációs indexe nulla és függetlenek egymástól. Az általánosság megszorítása nélkül tekintsünk itt az egyszerűség kedvéért két bináris (csak 0 és 1 számokat tartalmazó) sorozatot. Készítsünk egy harmadik sorozatot úgy, hogy véletlenszerűen keverve használjuk a két eredeti sorozat elemeit az következő (Markov típusú szabály) szerint: ha az új sorozat aktuális (n. indexű) helyen álló száma az 1. sorozatból származott, akkor a következő (n+1. indexű) szám (1- α1) valószínűséggel az 1. sorozat következő (n+1. indexű) száma lesz, és α1 valószínűséggel a 2. sorozat következő (n+1. indexű) száma, ha pedig az aktuális (n. indexű) helyen álló szám a 2. sorozatból származott, akkor a következő (n+1. indexű) szám (1- α2) valószínűséggel a 2. sorozat következő (n+1. indexű) száma lesz, és α2 valószínűséggel az 1. sorozat következő (n+1. indexű) száma. Tehát két független, autókorrelálatlan sorozatból teljesen véletlenszerűen állítunk össze egy harmadik sorozatot, így nyilvánvalóan azt várjuk, hogy az új sorozat r autokorrelációs indexe is nulla lesz, ám kiderült, hogy sokszor nem-nulla érték adódik: r =

1 s

2

a2 a1 + a 2

2

( m 1 - m 2 ) (1 - a 1 - a 2 ) ,

ahol µ1 és µ2 a két eredeti sorozat várható értéke, σ2 pedig az új sorozat szórásnégyzete (varianciája). Ez a tény új távlatokat nyit sok tudományterületen mint például az informatika, a genetika, vagy az önszerveződő rendszerek fizikája. A Parrondo játék (kvantum)optikai modelljét tárgyalja a [12] oldalon olvasható cikk, amely az előbb említett Brown-motorok tervezésére lehet alkalmas. A [13] cikk a Parrondo paradoxon kvantumfizikai interpretációját tárgyalja és mutatja be annak kvantumhálózatokon való implementációját.

155

Műszaki és Természettudományi Szekció A [14] tanulmány a Parrondo játék kódtömörítési alkalmazását tárgyalja. Nyilván sokakban vetődik fel a kérdés, hogy miként lehetne ezt az izgalmas felfedezést a hétköznapi életben kamatoztatni, például a szerencsejátékokban, vagy mondjuk a tőzsdén. A szerencsejátékok vonatkozásában érdekes és részletes elemzés található a [15] oldalon a pókerben való alkalmazásra. A gazdasági tudományokba csak lassan hatol be ez az új eredmény, de azt már kimutatták, hogy bizonyos esetekben két külön-külön hosszútávon veszteséges részvényportfólió közötti véletlenszerű tőkeátcsoportosítások révén az alaptőke növekedhet! Két kapcsolódó érdekes olvasnivaló található a [16], illetve [17] címeken. Végezetül egy érdekes és érthető (angol nyelvű) áttekintés olvasható a témáról a [18] oldalon.

Irodalomjegyzék [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]

[12] [13] [14] [15] [16] [17] [18]

http://www.eleceng.adelaide.edu.au/Groups/parrondo/index.html http://www.datagenetics.com/blog/august22012/index.html http://www.cut-the-knot.org/ctk/Parrondo.shtml http://arxiv.org/ftp/nlin/papers/0406/0406010.pdf http://epa.oszk.hu/00700/00775/00022/1136-1137.html http://www.tozsdestrategia.hu/Publicat/parrondo_paradox.htm http://www.eleceng.adelaide.edu.au/Groups/parrondo/index.html Czirók András, Csahók Zoltán, Derényi Imre, Vicsek Tamás: Biológiai mozgások statisztikus fizikai modelljei, Fizikai Szemle, 1996/6. http://www.elmer.unibas.ch/bm/index.html http://www.ncbi.nlm.nih.gov/pmc/articles/PMC1931524/ Allison, A., Pearce, C. E. M., and Abbott, D., Finding keywords amongst noise: Automatic text classiﬁcation without parsing, Proc. SPIE Noise and Stochastics in Complex Systems and Finance, Florence, Italy, Eds: János Kertész, Stefan Bornholdt, and Rosario N. Mantegna 6601 660113 (2007) http://arxiv.org/pdf/1010.5183v1.pdf http://arxiv.org/pdf/quant-ph/0502185.pdf http://arxiv.org/pdf/cond-mat/0402515v1.pdf http://parrondoparadox.blogspot.co.uk/ http://www.sais.se/mthprize/2002/almberg2002.pdf http://www.cmth.bnl.gov/~maslov/optimal_investment_ijtaf.pdf http://www.eleceng.adelaide.edu.au/Groups/parrondo/articles/Playing%20both% 20sides,%20Erica%20Klarreich.htm

Szerzők Nagy Péter: TMAI, GAMF Kar, KEFO, 6000, Kecskemét, Izsáki út 10., Magyarország. email: [email protected] Tasnádi Péter: TTK, ELTE, 1117, Budapest, Pázmány P. sétány 1./A., Magyarország, e-mail: [email protected]

156


Egyenletesség tesztelése klaszterszámok segítségével II. Osztényiné Krauczi Éva TMAT, Gamf Kar, Kecskeméti Főiskola Összefoglalás: A probléma továbbra is az, hogyan lehet egyenletességet tesztelni bizonyos távolságokhoz tartozó klaszterszámok segítségével. Sikerült az elméleti alapokat áttekinthetőbb formába hozni, valamint sokkal rövidebben bizonyítani. Majd ugyanúgy, mint a régi tételek esetében számos alternatívával szemben a teszt erejét vizsgáló számítógépes szimuláció is elkészült. Az is világossá vált, hogy a becsléses tétel miért nem működik az egyenletes eloszlás család tesztelésére. De mégis adható megoldás, hogyan teszteljünk valahol egyenletességet. Kulcsszavak: egyenletes eloszlás, határeloszlástételek, illeszkedésvizsgálat, erővizsgálat.

1. Bevezetés Adott X 1 , X 2 K , X n véletlen minta egy ismeretlen F ( x ) eloszlásfüggvényű véletlen változóból. Döntsük el a minta alapján, igaz-e az az egyszerű nullhipotézis H 0 : F Î U [0 ,1 ] illetve az az összetett nullhipotézis H 0 : F egyenletes eloszlású vagyis az egyenletes eloszlás családból származik a minta. Klaszterszámok segítségével probálunk dönteni. Mit értünk klaszterszám alatt? Adott egy U 1 , U 2 , K , U n minta a [0,1] intervallumon egyenletes eloszlásból. Rendezzük a mintánkat! Ekkor egy adott d n távolságszinthez rendeljük hozzá azt a számot, amit úgy kapunk, hogy ezt a távolságszintet végigtolva a [0,1] intervallumon, megszámoljuk hány olyan részhalmaza van a rendezett mintaelemeknek, amelyekre az igaz, hogy bármely két egymást követő tagjuk ennél a távolságszintnél nincs távolabb egymástól, ezt a számot nevezzük az adott távolságszinthez tartozó klaszterszámnak, és K n -nel jelöljük. Csőrgö és Wu megmutatták [1]-ben az alábbi tételt: 1. Tétel (Csörgő és WU, 2004). (a) Ha

nd

n

® 0

és

2

n dn ® ¥

K n - ne

, ekkor ne

(b) Ha

0 < lim inf

n

K n - ne ne

(c) Ha

- 2 nd

nd

nj

n

(e

nd

n

nd - nd

n

£ lim sup

n

nd

n

< ¥

- 2 nd

n

(e

nd

n

- nd

n

D

.

D

.

¾¾ ® N ( 0 ,1 ) 2

2

2

2

- 1 - n dn )

, ekkor

n

D

¾¾ ® N ( 0 ,1 ) 2

2

.

- 1 - n dn )

® ¥,e

nd

n

/n ® 0

K n - ne

, ekkor ne

- 2 nd

n

(e

nd

n

- nd

n

¾¾ ® N ( 0 ,1 )

- 1 - n dn )

157

Műszaki és Természettudományi Szekció Ennek a tételnek sikerült a többdimenziós változatát bebizonyítani, amit tesztelésre használunk.

Elméleti eredmények Rögzítsünk egy J természetes számot, valamint legyenek ságok olyanok, amelyek kielégítik az alábbi feltételek egyikét: nd

2.

0 < lim inf

nd

távol-

2

1. 3.

d n 1 < d n 2 < K < d nJ

nj

nj

® 0 , n d nj ® ¥

K

nj

a

£ lim sup

nj

- nd

® ¥ , ne

Legyen j = 1, K , J

nd

n

d

nd

< ¥

nj

® ¥

nj

nj

n

távolság szinthez tartozó klaszterszám, ahol

. Jelölje a normáló mennyiséget m nj = ne

- nd

nj

és a skálázó mennyiséget - 2 nd

2

s nj = e

nj

(e

nd

nj

2

2

- 1 - n d nj )

valamint legyen 1 æ K n1 - m n1 - m nJ K ç , K , nJ ç s n1 s nJ n è

Kn =

ö ÷. ÷ ø

2. Tétel. Az eddigieket feltéve, valamint e

minden 1 £

i < j £ J

- nd

ni

- nd

nj

(e

nd

S = ( s ij )

nj

® s ij

, ekkor K

ahol

2

- 1 - n d ni d nj ) / s ni s

ni

D

n

¾¾ ® N ( 0 , S ),

az együttes kovarianciamátrix

s jj = 1 -gyel

minden

j = 1, K , J .

A tétel igaz marad arra az esetre is, amikor a minta egyenletes eloszlásból származik, de nem tudjuk melyik intervallumból.

A új teszt és ereje Azon nullhipotézis eldöntésére, hogy a minta [0,1]-en egyenletes eloszlásból származik, használjuk a következő statisztikát: T

Cn = K n S

-1

Kn

feltéve, hogy létezik a kovarianciamátrix inverze.

Az egyenletes eloszláscsalád tesztelésére használjuk ugyanezt az n - 2 elemű mintához tartozó tesztstatisztikát, de előtte transzformáljuk a mintát. Legyen V 1 , V 2 , K , V n minta az [ a , b ] intervallumon egyenletes eloszlásból, ahol a < b . Az alábbi eloszlásbeli egyenlőség lehetővé teszi ezt a transzformációt.

158

Műszaki és Természettudományi Szekció æV - V1, n V n - 1, n - V1, n ç 2,n ,K çV - V1, n V n , n - V1, n è n,n

ö D ÷ (U , K , U 1, n ÷= ø

n - 2,n

)

A tesztek kritikus értékeit és erejét Monte-Carlo módszerrel határoztuk meg.

1.táblázat. Empirikus kritikus értékek a Cluster tesztre K n S - 1 K n és a Modified Cluster tesztre T

T

K n-2 S

-1

. Számos alternatívával (Béta eloszlással kontaminált egyenletes eloszláscsalád, nagyon oszcillált eloszláscsaládok) szembeni erejét. Alternatívák: r -1

K n-2

r -1

1.

ì 2 , ha 0 £ t < 1 / 2 rt ï g 1 (t ) = í , r -1 r -1 ï2 r (1 - t ) , ha 1 / 2 £ t < 1 î

2.

g 2 ( t ) = 1 + r cos( p jt ),

3.

g 3 ( t ) = c (q

ahol 0 < r

j

( j)

)e

å k =1 q k b k ( t )

, ahol b k Legendre polinomok [0,1]-n és q ( j ) = (q 1 , K q j ),

4. [0,1]-en egyenletes eloszlás kontaminálva Béta eloszlással: g 4 ( t ) = 1 - r + r G ( p + q ) /( G ( p ) + G ( q )) t

5.

-1

r

G 5 ( t ) = 1 / 2 + ( t - (1 - t ) ) / 2

p -1

(1 - t )

q -1

,

, ahol 0 < r

Sajnos a teszt alig érzékeny a szokásos egyenletes alternatívákra, de a nagyon oszcillált eloszláscsaládokra viszonylag jó erőviselkedést mutat. Összehasonlítottuk az új teszt erejét egy jó teszttel, Teresa Ledwina és Tadeusz Inglot NT1 tesztjével [3].

159


2.táblázat. Becsűlt ereje az 5%-os N T 1 -nek, a Cluster tesztnek és a Modified Cluster tesztnek a g2, g3, g4

alternatívákkal szemben.

Irodalomjegyzék [1] S. Csőrgö, Wei Biao Wu: On the clustering of independent uniform random variables, Random Structures Algorithms 25, 4 (2004), pp. 396--420. [2] Éva Osztényiné Krauczi: Joint cluster counts from uniform distribution, Probability and Mathematical Statistics,(submitting) [3] T. Inglot and T. Ledwina, Towards data driven selection of a penalty function for data driven Neyman test, Linear Algebra and its Applications 417, (2006), pp. 124–133.

Szerző Osztényiné Krauczi Éva: TMAT, GAMF Kar, Kecskeméti Főiskola. 6000 Kecskemét Izsáki út 10, Magyarország. E-mail: [email protected]

160


Szimplex módszer regularizációja Papp Olga1, Fábián Csaba1, Eretnek Krisztián2 1 Kecskeméti Főiskola, GAMF Kar, Informatika Tanszék 2 Eötvös Loránd Tudományegyetem Összefoglalás: Speciális problémaosztályokon a szimplex módszert vágósíkos eljárásként értelmezhetjük, amely segítségével egy konvex poliedrikus célfüggvényt közelíthetünk meg. A speciális vágósíkos eljárás egy regularizált változatát szeretnénk bemutatni. A regularizáció a duális térben történik, így az eljárás bázismegoldások sorozatán keresztül halad az optimum felé. Bemutatjuk az előzetes futtatási eredményeket. Abstract: There is a special problem class for which the implementation of the simplex method can be viewed as a cutting-plane method that approximates a convex polyhedral objective function. We would like to present regularizing of this cutting-plane method. Regularization is done int he dual space, and the method performs its steps along basic solutions. Test results are analyzed. Kulcsszavak: szimplex módszer, vágósíkos eljárás, regularizáció. Keywords: simplex method, cutting-plane method, regularization.

1. Bevezetés Egy speciális lineáris programozási feladat megoldása egy, a szimplex módszernek speciális árazását [6] alkalmazva, konvex poliedrikus optimalizálási feladat vágósíkos megoldásaként értelmezhető. A speciális, vágósíkos eljáráson alapuló árazás esetében azon oszlopok kapnak prioritást, amelyek már a bázisban voltak. Ez a megközelítés ellentétes a Pan [16] megközelítéssel, amely hatékonynak bizonyult a gyakorlatban. Az olyan feladatoknál viszont, ahol egy adott poliéderbe keressük a legnagyobb gömböt, a vágósíkos árazás alkalmazása jobb eredményeket generál, mint a klasszikus (Dantzig) megközelítés. A vágósíkos árazásnak egy regularizációját szeretnénk bemutatni. A Lemaréchal, Nemirovskii és Nesterov [8] level módszerét használva minimalizáljuk a konvex poliedrikus célfüggvényt. A primál feladaton a fenti módszer regularizált szimplex módszernek tekinthető. A duál feladaton végzett regularizáció az árazáson keresztül hat a folyamatra, ezáltal csak bázikus megoldásokon keresztül halad.

2. Gömb-keresési feladat Tekintsük az alábbi primál-duál lineáris programozási feladatpárt: (1.P)

(1.D)

(1)

ahol A egy m x n-es mátrix, b és c vektorok megfelelő dimenziójúak. A fenti feladatpárnak az egyenlőséggel felírt változata: (2.P)

(2.D)

(2)

161

Műszaki és Természettudományi Szekció Tegyük fel, hogy az (1.D) feladat megengedett tartományában keresünk egy ’belső’ pontot. Az (1.D) korlátozások alakúak. Felvéve egy toleranciát, a korlátozás átírható . Ha olyan pontot keresünk, amely minden korlátozást minimális toleranciával teljesít, akkor a feladat: (3)

A (3) feladat megoldható, mivel

felvehet ppozitív értékeket. Ahhoz, hogy a célfüggvény

korlátos legyen, bevezetjük az feladat tehát:

korlátozást, ahol d elég nagy konstans. A

(4) (4.P)

(4.D)

A (4.D) feladat leírható a következőképpen: (5)

Az (5) feladatnak van véges ge optimuma, továbbá optimális megoldása (4.D)-nek akkor és csakis akkor, ha optimális megoldása (5)-nek, és az optimális célfüggvény érték .

Az (5) feladatot vágósíkos ág eljárással lj oldjuk, dj meg, melynek során a

modell függvényt

, ahol I jelöli az eddigi vágásokat. A megoldási

használjuk: algoritmus tehát:

1 Algoritmus – (5) feladat megoldása 0. Inicializáció Legyen a megállási kritérium

162

, továbbá

úgy, hogy U felett

minimális.

Műszaki és Természettudományi Szekció Minimalizálja lj y* a . .

modell függvényt U felett.

1. Célfüggvény kiértékelés, legjobb megoldás frissítése Ha , akkor legyen , 2. Leállási kritérium Ha

akkor STOP,

az (5) feladat egy

-optimális megoldása.

3. Modell függvény frissítése Legyen úgy, hogy továbbá . modell függvényt U felett. Minimalizálja y* a

támasztó függvénye

-nak

-nál,

4. Következő lépés előkészítése Legyen és vissza az 1. lépésre. A (4) feladatpárnak megadhatjuk egy regularizált változatát:

(6) (6.P)

(6.D)

Mivel (6.D)-nek van optimális megoldása, az LP dualitás miatt (6.P)-nek is van. optimális megoldása (6.D)-nek akkor és csakis akkor, ha minimalizálja a modell függvényt U felett, és az optimális célfüggvényérték. Módosítsuk az 1 Algoritmust, vezessünk be m segédoszlopot. 2 Algoritmus – (4.P) feladat megoldása, speciális szimplex módszerrel 0. Inicializáció Legyen a megállási kritérium , továbbá (4.P) feladatnak úgy, hogy ogy bázisváltozó. Tartalmazza a bázisbeli oszlopokat, továbbá legyen tartozó duál vektor. ,

megengedett bázisa a a bázishoz

.

1. Árazás, legjobb duál vektor frissítése

163


Legyen gy Ha 2. Leállási kritérium Ha

, akkor legyen

akkor STOP,

,

-optimális megengedett bázis.

3. Modell függvény frissítése úgy, hogy . Legyen Oldjuk meg a (7.P) feladatot szimplex módszerrel, kiindulási bázisként a B-t használva. Legyen B az optimális bázis és a bázishoz tartozó duál vektor.

4. Duál vektor beállítása Legyen

és vissza az 1. lépésre.

3. Regularizáció A fenti vágósíkos eljárást regularizáltuk a Lemaréchal, Nemirovskii és Nesterov [8] level módszerével. A level módszer során egyetlen paramétert kell használni. Legyen ez a paraméter , amely segítségével eldönthető a level halmazok száma. Az (5) feladatra alkalmazva a módszert, az 1 Algoritmust a következőképpen módosítjuk: 4*. Következő lépés előkészítése gy a Legyen , konvex kvadratikus feladat optimális megoldása, legyen és vissza az 1. lépésre. Azaz a következő lépésben a jelenlegi

-nak vesszük a vetületét egy adott level halmazra.

Ha ugyanezt a regularizációt alkalmazzuk a 2 Algoritmusra, akkor: 4*. Duál vektor beállítása Legyen gy a , pt konvex kvadratikus feladat optimális megoldása, ahol Legyen és vissza az 1. lépésre.

, továbbá az új duális vektor

A szimplex módszerhez hasonlóan, a fenti módszer is bázismegoldásokat generál (4.P)-hez. A regularizáció a duál térben történik.

4. Futtatási eredmények

164

Műszaki és Természettudományi Szekció 59 NETLIB feladaton végeztük el a futtatást. A feladatokat alapul véve felépítettük a gömbkeresési modellt. Kétféle modellt építettünk: typeI és typeII feladatokat. A typeI feladatoknál a NETLIB feladat A mátrixát és a c célfüggvény vektorát vettük a (4.P) feladathoz. A typeII feladatoknál a NETLIB feladat A mátrixának negatív értékét és a c célfüggvény vektorát vettük a (4.P) feladathoz. értékét 0.5-re állítottuk. Összehasonlítottuk a standard szimplex és a regularizált szimplex módszereket. A futtatási eredmények megtekinthetők az 1 és 2 Táblázatokban. Mindkét módszerrel összesen 107 feladatot sikerült megoldani a rendelkezésre álló 118 feladatból. A regularizáció alkalmazásával az iterációszám 37%-ra csökkent, a futási időt is sikerült csökkenteni. Modell ADLITTLE_TYPE-I AFIRO_TYPE-I AGG_TYPE-I AGG2_TYPE-I AGG3_TYPE-I BANDM_TYPE-I BEACONFD_TYPE-I BLEND_TYPE-I BNL1_TYPE-I BOEING1_TYPE-I BOEING2_TYPE-I BORE3D_TYPE-I BRANDY_TYPE-I CAPRI_TYPE-I DEGEN2_TYPE-I E226_TYPE-I ETAMACRO_TYPE-I FFFFF800_TYPE-I FINNIS_TYPE-I FIT1D_TYPE-I FIT2D_TYPE-I FORPLAN_TYPE-I GFRD-PNC_TYPE-I GROW15_TYPE-I GROW22_TYPE-I GROW7_TYPE-I ISRAEL_TYPE-I KB2_TYPE-I LOTFI_TYPE-I PEROLD_TYPE-I PILOT4_TYPE-I RECIPELP_TYPE-I SC105_TYPE-I SC205_TYPE-I SC50A_TYPE-I SC50B_TYPE-I SCAGR25_TYPE-I SCAGR7_TYPE-I SCFXM1_TYPE-I SCFXM2_TYPE-I SCORPION_TYPE-I SCRS8_TYPE-I SCTAP1_TYPE-I SCSD1_TYPE-I SCSD6_TYPE-I SEBA_TYPE-I SHARE1B_TYPE-I SHARE2B_TYPE-I SHELL_TYPE-I SHIP04L_TYPE-I SHIP04S_TYPE-I STAIR_TYPE-I STANDATA_TYPE-I STANDGUB_TYPE-I STANDMPS_TYPE-I STOCFOR1_TYPE-I TUFF_TYPE-I VTP-BASE_TYPE-I WOOD1P_TYPE-I

iteráció szám24 22 213 426 128 73 36 67 20 2 1 36 725 202 4 167 2 68 54 88 18 11 13 8 6 41 11 8377 143 312 71 64 23 3 5 7 13 48 196 88 9 3 262 109 594 58 32 126 59 24 211 74 136 187

futási idő (millisec) 1

iteráció szám 25

1 302,9 658,1 29,5 2,4 117 59,6 5,2 3,8 2,4 21,7 2622,4 126,2 6,8 489,8 6,8 15,2 122,9 32,5 59,5 13 27,8 3,8 1 8 15,8 1891,8 18,2 199 3,8 2,4 32,5 1 5,2 27,9 11 100 179,5 23,5 11,5 8,5 60,9 9,4 4004,6 188,6 67,2 173,1 109 46,7 669 9,4 184 475,8

24 278 574 6 62 35 67 21 2 1 21 634 211 3 47 2 24 49 42 11 14 12 9 279 10 11 19 15 48 216 328 73 97 15 10 3 4 9 48 139 50 8 4 204 87 540 29 27 58 7 3 9 58 48 27 661

level lépések száma 18 24 86 136 13 67 33 76 17 1 0 24 244 105 1 48 1 18 33 44 6 10 9 7 81 16 16 22 17 51 101 170 43 49 12 7 1 1 6 49 131 63 6 2 70 65 595 39 37 69 4 1 26 69 37 20 200

futási idő (millisec) 31,5 8 455,8 1433,6 12,6 49,3 265 174,9 15,4 2,4 1 38,5 2985,9 268 8,2 245,2 9,7 18,4 185,4 56,3 61,3 31 47 12,2 238,5 6,6 13,9 165,6 68,8 26,5 113,5 408,5 26,3 26,4 46,7 6,6 8 23,5 15,5 257,5 324,1 65,9 15,7 19 93,4 60,5 6811,1 252,2 176,4 157,5 25 11,4 98,5 47,7 109 23,2 3793,9

165

Műszaki és Természettudományi Szekció 1. 1. táblázat: I típusú feladatok futási eredménye Modell ADLITTLE_TYPE-II AFIRO_TYPE-II AGG_TYPE-II AGG2_TYPE-II AGG3_TYPE-II BANDM_TYPE-II BEACONFD_TYPE-II BLEND_TYPE-II BNL1_TYPE-II BOEING1_TYPE-II BOEING2_TYPE-II BORE3D_TYPE-II BRANDY_TYPE-II CAPRI_TYPE-II DEGEN2_TYPE-II E226_TYPE-II ETAMACRO_TYPE-II FFFFF800_TYPE-II FINNIS_TYPE-II FIT1D_TYPE-II FIT2D_TYPE-II FORPLAN_TYPE-II GFRD-PNC_TYPE-II GROW15_TYPE-II GROW22_TYPE-II GROW7_TYPE-II ISRAEL_TYPE-II KB2_TYPE-II LOTFI_TYPE-II PEROLD_TYPE-II PILOT4_TYPE-II RECIPELP_TYPE-II SC105_TYPE-II SC205_TYPE-II SC50A_TYPE-II SC50B_TYPE-II SCAGR25_TYPE-II SCAGR7_TYPE-II SCFXM1_TYPE-II SCFXM2_TYPE-II SCORPION_TYPE-II SCRS8_TYPE-II SCTAP1_TYPE-II SCSD1_TYPE-II SCSD6_TYPE-II SEBA_TYPE-II SHARE1B_TYPE-II SHARE2B_TYPE-II SHELL_TYPE-II SHIP04L_TYPE-II SHIP04S_TYPE-II STAIR_TYPE-II STANDATA_TYPE-II STANDGUB_TYPE-II STANDMPS_TYPE-II STOCFOR1_TYPE-II TUFF_TYPE-II VTP-BASE_TYPE-II WOOD1P_TYPE-II

iteráció szám 6 8 9 9 9 19 1 21 9 41 43 316 60 21 10 4 28 948 16 3 3 64 5 812 2192 244 81 9 177 4 24 14 19 9 2099 88 3 6 3 3 4 23 9 516 24 63 546 47 50 47 2 29 2 52 2 43 241

futási idő (millisec) 1

iteráció szám4

2,4 2,4 15,5 14 15,6 1 1 29,4 35,5 5,2 176,5 24,9 12,3 9,8 3,8 38,5 7884,3 23,5 2,4 6,8 23,5 17,5 1477,6 8032,3 92 3,8 2,4 847,4 1 1 9,4 1 1 4725,4 9,4 5,2 22 5,2 11,5 5,2 6,7 7 1879,9 5,2 5,2 2672,3 154,4 120,2 45,2 6,8 59,6 6,9 6,6 3,8 12,2 615

9 12 9 9 7 1 21 12 6 22 63 100 7 5 7 27 4 23 9 4 58 5 320 543 253 3 71 12 175 5 15 13 18 7 588 142 7 6 25 2 8 49 8 509 25 37 519 46 44 63 3 25 3 30 6 13 248

level lépések száma 1 11 18 13 13 5 0 14 19 21 26 81 44 7 2 3 33 14 19 4 1 28 3 205 362 99 1 28 24 106 3 21 12 16 6 244 75 4 4 17 1 3 76 6 510 20 28 525 51 53 57 11 24 11 41 19 28 248

futási idő (millisec) 2,4 6,6 32,5 34,2 35,7 12,7 1 8 125 31 20 113,5 81 12,4 14,5 5,2 96,9 48,6 82,5 6,6 14 46,9 34 898,5 3251 188,5 3,8 15,3 17 1371,3 2,4 12,2 15,1 8 5,2 1699,1 76,5 12,5 39 44,7 14,4 6,8 78 16 5889,2 16,9 15,3 5578,6 359 263,4 157,5 31 107,5 34,2 28 34 28 2007,5

2. 2. táblázat: II típusú feladatok futási eredménye

4. Következtetések Bevezettük a szimplex módszer regularizációját speciális típusú feladatokra, amelyekre vágósíkos eljáráson alapuló árazást használva a szimplex módszer vágósíkos eljárásként értelmezhető.

166

Műszaki és Természettudományi Szekció A futtatási eredmények igazolják, hogy a regularizáció hatékony, érdemes a regularizált szimplex módszernek más típusú alkalmazásait is keresni.

Irodalomjegyzék [1] [2] [3] [4]

[5]

[6] [7] [8] [9]

[10]

[11]

[12] [13] [14] [15]

Dantzig, G.B. Linear Programming and Extensions. Princeton University Press, (1963) Princeton. Dempster, M.A.H. (2007). Personal communication. Dempster, M.A.H. and R.R. Merkovsky. A practical geometrically convergent cutting plane algorithm. SIAM Journal on Numerical Analysis 32 (1995), 631-644. Elble, J.M. Computational Experience with Linear Optimization and Related Problems. PhD dissertation (2010), The University of Illinois at Urbana-Champaign, Illinois, USA. Fábián, C.I., G. Mitra, D. Roman, and V. Zverovich. An enhanced model for portfolio choice with SSD criteria: a constructive approach. Quantitative Finance 11 (2011), 1525-1534. Fábián, C.I., O. Papp, and K. Eretnek. Implementing the simplex method as a cuttingplane method. Opimization Online. (2011) Fábián, C.I. and Z. Szőke. Solving two-stage stochastic programming problems with level decomposition. Computational Management Science 4 (2007), 313-353. Lemaréchal, C., A. Nemirovskii, and Yu. Nesterov. New variants of bundle methods. Mathematical Programming 69 (1995), 111-147. Maros, I. Computational Techniques of the Simplex Method. International Series in Operations Research & Management Science. Kluwer Academic Publishers (2003), Boston. Murtagh, B.A. Advanced Linear Programming: Computation and Practice. McGrawHill (1981), New York. Murty, K.G. The gravitational method of linear programming. Technical Report No. 8619 (1986), Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, Michigan, USA. Nemirovski, A. Lectures in modern convex optimization. (2005) ISYE, Georgia Institute of Technology. Oliveira, W. C. Sagastizábal, and S. Scheimberg. Inexact bundle methods for twostage stochastic programming. SIAM Journal on Optimization 21 (2011), 517-544. Orchard-Hays, W. Advanced Linear-Programming Computing Techniques. McGrawHill (1968), New York. Pan, P.-Q. Nested pricing for the simplex algorithm: An empirical evaluation. (2007) Optimization Online.

Szerzők Papp Olga: Informatika Tanszék, GAMF Kar, Kecskeméti Főiskola. 6000 Kecskemét, Izsáki út 10, Magyarország E-mail: [email protected] Fábián Csaba: Informatika Tanszék, GAMF Kar, Kecskeméti Főiskola. 6000 Kecskemét, Izsáki út 10, Magyarország E-mail: [email protected] Eretnek Krisztián: Eötvös Loránd Tudományegyetem. 1117 Budapest, Pázmány Péter sétány 1/C, Magyarország. E-mail: [email protected]

167

168

MŰSZAKI ÉS TERMÉSZETTUDOMÁNYI SZEKCIÓ

Recommend Documents