Egyoldali párosítási piacok egyenletes klaszterezési megközelítésben

Kivonat, rövid leírás

Az egyoldali párosítási piacokon nincs, vagy csak részben van olyan árrendszer, amely meghatározná az erőforrások allokációját. A létrejövő párosításokat elsősorban a piacot szabályozó mechanizmusok adják meg. Az egyoldali párosítási piacok egyik alkalmazási területére, a vesecsere-problémára létezik olyan megközelítés, amely egy súlyozott párosítási problémára vezet vissza. A disszertációban ezt a megközelítést általánosítom az m-dimenziós párosítások által, amelynek egy speciális esetét m-szobatárs problémaként definiáljuk. Ezzel egy Pareto-hatékony megközelítést határozunk meg, amelyben minimalizálási és maximalizálási problémákat is tekintünk. A megfogalmazott megoldási keretre egyenletes klaszterezési megközelítésként hivatkozunk, a disszertáció célja pedig ennek elméleti és gyakorlati megoldhatóságának vizsgálata. A megfogalmazott m-szobatárs problémában a hallgatókat euklideszi térbeli pontok reprezentálják, és azt hogy mennyire lennének egymás számára jó szobatársak, a közöttük adódó távolságok adják meg. A cél azonosan m fős szobák beosztása a szobákon belüli távolságnégyzetek összegének minimalizálása vagy maximalizálása mellett attól függően, hogy homogén vagy heterogén klasztereket kívánunk megadni. A dolgozatban elsőként összefoglalom az azonos elemszámú csoportok kialakításának és általánosan az elemszámkorlátokkal ellátott feladatok szakirodalomban előforduló széleskörű alkalmazási lehetőségeit. Ezt követően bevezetem a probléma nehézségének tárgyalásához elengedhetetlen fogalmakat, majd ezek ismeretében áttekintést adok a szakirodalomban található, az egyenletes klaszterezéshez kapcsolódó problémák bonyolultságelméleti eredményeiről. Az általános dimenziós eredményeket kiterjesztem, és megmutatom, hogy valamennyi általunk tekintett probléma legalább háromfős csoportok esetén NP-nehéz, vagyis jelenlegi ismereteink szerint nem tudjuk általánosan hatékonyan megoldani. Ezután bemutatom az egyoldali párosítások legalapvetőbb, stabil szobatársak megközelítésének fontosabb eredményeit, megadom az m-szobatárs probléma formális definícióját, majd összevetem a szobatárs problémákat elméleti és gyakorlati szempontból. A bonyolultságelméleti eredmények tükrében ezután a gyakorlati megoldhatóság felé fordulok. Ehhez elsősorban áttekintem azokat az egyenletes klaszterezési problémák során alkalmazott algoritmusokat, amelyek valamilyen garanciát adnak az általuk talált megengedett megoldás szuboptimalitására: az approximációs eljárásokat, valamint a kúp optimalizálást. Másodsorban pedig a gyakorlati alkalmazások során leggyakrabban tekintett megoldási módszerre, a heurisztikus eljárásokra térek rá. E során az algoritmusok széles körét tekintem, amelyhez két módon járultam hozzá. Egyrészt különböző heurisztikus eljárásokat fogalmaztam meg a hagyományos klaszterelemzéshez kapcsolódó módszerek által adott, nem feltétlen egyenlő elemszámú csoportok kiegyenlítésére. Másrészt pedig az egyszerű párok cseréjével operáló LCW algoritmus esetén megvizsgáltam a nagyobb méretű cserék lehetőségét, és megfogalmaztam három heurisztikus eljárást, amelyek kettes és hármas cserék segítségével keresik az optimumot. A bemutatott valamennyi heurisztikus eljárást valós adathalmazokat és szimulációkat is magába foglaló, széleskörű elemzés során vetettem össze. A felállított elemzési keret erőssége, hogy lehetővé teszi, hogy egyszerre tekintsük mind a minimum-, mind a maximumfeladatot, és átfogóan elemezzük az m-szobatárs probléma gyakorlati megoldhatóságát. Ezekkel pedig túlmutatok a korábbi tanulmányokon, amelyek jellemzően az algoritmusok egy szűkebb körét és csupán az egyik célfüggvény ellenében tesztelik. A vizsgálathoz megadtam az összes szobabeosztás előállításának egy olyan konstrukcióját, amely lehetővé tette, hogy alacsony hallgatói számok mellett, az össztávolságokat hisztogramon ábrázolva szemügyre vegyük a megengedett megoldások terét. Az algoritmus felírásához a szobabeosztások formális definícióját is megadtam. További lényeges részlet az optimalitási pontszám definiálása, amelyet az elemzési keret minimum- és maximumproblémát is tartalmazó sajátosságát felhasználva tudtam bevezetni. Ennek segítségével ábrázoltam az algoritmusok egymáshoz képest vett teljesítményét, és a tesztelt heurisztikák alkalmazásával elérhető maximum- és minimumértékek különbségéhez képest is ki tudtam értékelni az algoritmusokat. A heurisztikus eljárások elemzése során a következő eredményeket fogalmazom meg. Az irodalomban hagyományosan tekintett, való életből származó ‘Iris’ és ‘Seeds’adathalmazokon a legtöbb minimalizáló eljárás hasonlóan jól teljesít, így nem lehet ez alapján különbséget tenni közöttük. Az egyszerű konstruktív módszerek, valamint a klaszterközéppontok meghatározását és az elemek klaszterközéppontokhoz való hozzárendelését alternáló eljárások nem teljesítenek jól a feladat megoldása során. A kis hallgatói létszámmal rendelkező esetek a szobabeosztások költségeinek ferde eloszlását mutatják, amely a minimalizálási és maximalizálási problémák lehetséges általános aszimmetriájára utal. A nagy hallgatói létszám esetén elvégzett elemzés megmutatja, hogy az optimalizálási problémák minimalizálási és maximalizálási feladat, valamint kis- és nagyméretű csoportok esetén is más-más karakterisztikákkal rendelkeznek, amely a heurisztikus eljárások teljesítményeiben tükröződik. A minimalizálási feladat megoldásához szignifikánsan nagyobb futásidő szükséges. A hármas cseréket is megvalósító LCW alapú heurisztika bizonyos esetekben önmagában is releváns. Ugyanebben a módszerben kezdeti értékként alkalmazva valamely másik eljárás által adott megengedett megoldást, előbbi jelentősen javíthat azok célfüggvényértékén. A lokális keresést alkalmazó eljárások köréből a legegyszerűbbnek számító és egyben leggyorsabb LCW eljárás teljesítménye pedig nem sokkal marad el a szofisztikáltabb módszerek eredményeitől, így a gyakorlati alkalmazás esetén a konkrét céltól függően ezzel is elfogadható megoldáshoz juthatunk.