On-line előrenéző és paraméter tanuló algoritmusok nyugtázási és ütemezési problémákra

Előnézet	PDF (disszertáció) Download (660kB) | Előnézet
Előnézet	PDF (tézisfüzet) Download (262kB) | Előnézet
Előnézet	PDF (tézisfüzet) Download (254kB) | Előnézet

Magyar nyelvű absztrakt

On-line problémáról beszélünk az olyan optimalizálási feladatok esetében, ahol a bemenetet csak részenként ismerjük meg, és a döntéseinket a már megkapott információ alapján, a további adatok ismerete nélkül kell meghoznunk. Egy ilyen algoritmustól nem várhatjuk el, hogy a teljes információval rendelkezo algoritmusok által megkapható optimális megoldást szolgáltassa. Azon algoritmusokat, amelyek ismerik a teljes bemenetet, offline algoritmusoknak nevezzük. Az on-line algoritmusok hatékonyságának vizsgálatára két alapveto módszert használnak. Az egyik lehetoség az átlagos eset elemzése. Ebben az esetben fel kell tételeznünk valamilyen valószínuségi eloszlást a lehetséges bemenetek terén, és a célfüggvénynek az erre az eloszlásra vonatkozó várható értékét vizsgáljuk. A másik megközelítés egy legrosszabb eset elemzés, amelyet versenyképességi elemzésnek nevezünk. Ebben az esetben az on-line algoritmus által kapott megoldás célfüggvényértékét hasonlítjuk össze az optimális off-line célfüggvényértékkel. Az informatikai hálózatokon a kommunikáció során elküldött információ csomagok formájában továbbítódik. Az esetek többségében azonban a kommunikációs csatorna nem teljesen megbízható, így az egyes információcsomagok megérkezésérol nyugtát kell küldeni. A TCP implementációk is küldenek nyugtát a csomagok fogadásakor. A nyugtázási probléma tárgyalása során azt próbáljuk meghatározni, hogy melyik idopontban érdemes egy nyugtát küldeni. Abból indulunk ki, hogy egy nyugta több csomag megérkezését tudja igazolni, azonban ha túl sokáig várunk egy-egy nyugta elküldésével az a csomag újraküldéséhez vezethet, ami többletterhelést ró a hálózatra, míg ha minden csomagot azonnal nyugtázunk akkor maguk a nyugták terhelik feleslegesen a hálózatot. Egy új, paraméter tanuláson alapuló algoritmust fejlesztettünk az online nyugtázási feladat megoldására és annak elorenéző változatához is. Véletlen eloszlás alapján generált és valós inputokon futtatott tesztek alapján megállapítottuk, hogy az új algoritmus lényegesen jobb hatékonyságú, mint a korábban ismert algoritmusok. Ez elutasításos ütemezés problémájában [2] az algoritmusnak lehetosége van az egyes munkákat elutasítani. A munkák jellemzoje a végrehajtási ido és az elutasítás büntetése. Célunk az elfogadott munkák végrehajtási idejének és az elutasítás büntetéseinek összegét minimalizálni. Létezik egy 2:618-versenyképes algoritmus az online esetre tetszoleges számú géphez. Ezt az algoritmust nevezzük RTP algoritmusnak (Reject Total Penalty), melynek az egyik alapötlete az, hogy minden munkára hasonlítsuk össze a büntetést és a terhelést, majd utasítsuk el azokat a munkákat, melyekre a büntetés kisebb mint a terhelés. Ez az alapötlet még csak a mohó algoritmust adja, ami akkor hoz rossz döntést, ha a gépek száma nagy, mert ez lehetové teszi, hogy úgy tunjön, hogy egy nagy munka kis terhelést jelent. Egy új, paraméter tanuláson alapuló algoritmust fejlesztettünk az online elutasításos ütemezés megoldására. Véletlen eloszlás alapján generált és valós inputokon futtatott tesztek segítségével megállapítottuk, hogy az új algoritmus hasonló hatékonyságú mint a korábbi algoritmusok, viszont akkor is jól használható, ha nincs elozetes információnk az inputról. A valós ideju helymeghatározó rendszerek feladata a különbözo objektumok pozíciójának nagy pontosságú meghatározása A rendszerben az objektumok olyan miniatur rádióadókkal vannak felszerelve, melyek egy az Intézet által kifejlesztett beltéri muködésu valós ideju pozíciómeghatározási rendszer (WISMIT) által feldolgozható periodikusan sugárzott rádiójeleket küldenek. Ezeket a rádiójeleket fogják az infrastruktúra különbözo méroállomásai, melyek a jelek beesési szögét és a rádiójelet sugárzó objektum távolságát tudják meghatározni minden periódusban (mérési ciklusban). Egy ilyen mérési sorozatot melyen a periodikusan sugárzott rádióimpulzusok egyetlen impulzusán különbözo pozíciókban elhelyezett méroeszközök méréseit értjük, burst-nek nevezzük. A rádió jelek különbözo feldolgozható információkat is közvetítenek, egyrészt egy egyedi azonosítót, ami egyértelmuen azonosítja azt az objektumot amibol a rádiójel származik, másrészt egy folyamatosan növekvo sorszámot ami a mérési ciklusokat számolja így azonosítva egy-egy mérési ciklust (burst-öt). Ezt a mérési ciklust azonosító sorszámot burst_id-nek nevezzük. Ha egy mérési ciklusban elegendo mérési adatot összegyujtünk, a mérési eredményekbol a pozíciót kiszámító algoritmus már ki tudja számítani az objektum pozícióját. A klaszterezo algoritmusnak azt kell eldöntenie, hogy mikor küldjük tovább a beérkezo adatokat. Az algoritmus nem várhatja egyszeruen minden mérési eredmény beérkezését, ennél jóval kifinomultabb megoldásra van szükség. A cél az, hogy az algoritmus döntse el mikor érdemes az összegyujtött adatokat a pozíció számításhoz továbbítania. Ehhez két egymásnak ellentmondó célnak kell megfelelnie. Az elso, hogy a pozíció számító algoritmusnak az összes rendelkezésre álló mérési adatot meg kell kapnia a mérési pontoktól, a leheto legpontosabb pozíciómeghatározás érdekében. Ugyanakkor a rendszernek nem szabad túl sokáig várnia a mérési adatok begyujtésére, hiszen minden késedelem az adattovábbításban jelentosen rontja a mozgó objektumra meghatározott pozíció relevanciáját. Egy majdnem pontos pozíció jobb, mint egy teljesen pontos pozíció túl késon. Bemutatunk egy a fenti irányelveket célzó integrált célfüggvényt, és a klaszterezési problémát maximalizációs problémaként definiáljuk. Egy új, paraméter tanuláson alapuló algoritmust is fejlesztettünk az on-line klaszterezési probléma megoldására. A Fraunhofer intézet szimulációs rendszerében, valós inputokon futtatott tesztek alapján megállapítottuk, hogy az új algoritmus jobb hatékonyságú mint a korábbi, leheto legkisebb versenyképességi hányadossal rendelkezo algoritmusok, és akkor is jól használható, ha nincs elozetes információnk az inputról.

Tétel nézet