Döntéstámogató rendszerekben alkalmazható számítási intelligencián és adatbányászaton alapuló algoritmusok. Király András

Doktori (PhD) értekezés tézisei

Döntéstámogató rendszerekben alkalmazható számítási intelligencián és adatbányászaton alapuló algoritmusok Király András Pannon Egyetem Vegyészmérnöki- és Anyagtudományok Doktori Iskola

Témavezet®: Dr. Abonyi János

Folyamatmérnöki Intézeti Tanszék Veszprém 2013.

1.

El®zmények és célkit¶zés

A döntéstámogató rendszerek olyan plusz tudást képesek adni a döntéshozók kezébe, melyek naprakész ismereteket szolgáltatnak mind a vállalat folyamatairól mind a küls® környezetr®l, biztos alapot teremtve ezzel a helyes döntésekhez. A dolgozatban ismertetésre kerül® módszerek és eszközök segítségével pontosabban modellezhet®k a vállalatban lejátszódó folyamatok; kezelhet®k a rendszerekben fellép® bizonytalanságok; hatékonyabban elemezhet®k a rendelkezésre álló adatok. Az ismertetésre kerül® technikák mindegyike konkrét ajánlásokat szolgáltat a döntéshozók részére. A dolgozat eredeti célkit¶zése komplex, többdimenziós rendszerek modellezésére, elemzésére alkalmas eszközök és algoritmusok fejlesztése volt. A szokványos felépítés helyett az értekezés három különböz® rendszer vizsgálatát tekinti át, melyek közül az els® kett® az E.ON Hungária Zrt.-vel való együttm¶ködés keretén belül valósult meg, míg az adatok harmadik csoportját a Finnish Microarray and Sequencing Centre kutatóintézetben el®állított génexpressziós adatok biztosították. Ennek megfelel®en három különböz® elemzési és optimalizálási technika kerül bemutatásra, melyek mindegyike valamilyen gyakorlati probléma megoldását szolgáltatja. Logisztikai problémák kapcsán olyan útvonalhálózat-tervezési metódust ismertet, mely új genetikus algoritmus és reprezentáció alkalmazásával képes egy 600 mobilszerel®t ellátó hálózat optimális felépítésének ajánlására. Többszint¶ raktározási problémák robosztus optimálására újszer¶ szimulátort vezet be, melynek segítségével többféle optimalizációs eljárás kerül tárgyalásra. Továbbá a be- és kimenetek változásai közötti kapcsolatok feltárásával újszer¶ döntéstámogató eszközt ismertet. Bioinformatikai eljárások során keletkez® génexpresszió adatokból történ® hasznos információ kinyerésére pedig új biclustering algoritmusok és elemzési technikák kerülnek ismertetésre. A fentiek alapján tehát az értekezés három különböz® problématerületet dolgoz fel, melynek megfelel®en eltér® tudományos területekr®l mutat be tudományos eredményeket: többes utazóügynök probléma költségminimalizálása genetikus algoritmusokkal; dinamikus, bizonytalanságokat kezel® szimuláció Monte-Carlo módszerrel; részecske-raj algoritmusok alkalmazása optimális rendelési gyakoriság meghatározására többszint¶ raktárhálózatok esetén; adatbányászati technikák, mint zárt gyakori elemhalmaz keresés illetve biclustering módszer.

1

2.

Kísérleti eszközök és módszerek

Az értekezés a modellezés, szimuláció, adatelemzés és optimalizálás területér®l mutat be új tudományos eredményeket, így adatbányászati és folyamatmérnöki technikák kerültek továbbfejlesztésre és alkalmazásra. A többes utazóügynök probléma esetén az adatok a Google Maps felületén deniált térképb®l származnak, melynek feldolgozását PHP és Javascript alapú szoftverek végzik. A raktárkészlet-optimalizálás kapcsán elérhet® historikus adatok MS Access adatbázisából MySQL relációs adatbázis készült, míg a génexpresszió adatok egyszer¶ szövegfájlokként álltak rendelkezésünkre. A megfelel®en el®készítette adatok feldolgozására a modellek és algoritmusok MATLAB szoftver segítségével készültek, melyek szükség esetén ODBC kapcsolat segítségével kapcsolódnak az adatbázishoz. Ezen megoldások egyéb kiegészít® MATLAB programcsomagokat használnak, mint adatelemz®, statisztikai csomagok. A biclustering probléma kapcsán elkészült rekurzív algoritmus elkészítéséhez Java programozási nyelvet használtunk, míg az interneten elérhet® alkalmazás (GeneFuncster) PHP és Javascript nyelveken íródott. 3.

Tézisek

1. Célirányos problémareprezentáció kialakításával korlátokat és id®ablakokat is kezel® többes utazóügynök probléma megoldásában hatékony genetikus algoritmust hoztam létre. Az algoritmus segítségével és Google Maps API alapú támogatással egy felhasználóbarát és hatékony eszközt készítettem és alkalmaztam valós logisztikai probléma megoldásában.

(Kapcsolódó publikációk: [2, 3, 4, 11, 15, 16, 17])

(a) Megmutattam, hogy megfelel® genetikus reprezentáció alkalmazásával a genetikus algoritmusok hatékonysága nagymértékben javítható az irodalomban fellelhet® eddigi megoldásokhoz képest a többes utazóügynök probléma megoldására. A bevezetett ún. multichromosome reprezentációra alapozva létrehoztam egy új típusú genetikus algoritmust, mely a korábbi megoldásokhoz képest rövidebb futási id®t és hatékonyabb m¶ködést mutat. Az elkészült eszközzel valós logisztikai problémák optimális útvonaltervét készítettem el, minimalizálva a járm¶vek számát, gyelembe véve az átadási id®t mint id®ablakot, kielégítve az utazási id®re és távolságra vonatkozó korlátokat. [2, 3, 4, 15] 2

(b) A kifejlesztett módszer támogatására és valós környezetben történ® alkalmazhatóságának biztosítására Google Maps API-n alapuló moduláris szoftvert hoztam létre. Az elkészült programcsomaggal egy, a Google Maps felületén deniált térképb®l kiindulva felhasználóbarát módon van lehet®ség a jelöl®k koordinátáinak kinyerésére, a távolságmátrixok valós útforgalmi viszonyok alapján történ® generálására, illetve az optimalizálás eredményének könnyen értelmezhet®, ugyancsak Google Maps térképen történ® vizualizációjára. [4, 11, 16, 17] (c) Az elkészült program segítségével komplex logisztikai feladatok komplett költségoptimalizálását végeztem el, mint az EOn Services Kft. 600 mobilszerel®b®l álló ottájának körutas ellátással történ® kielégítése a jelenlegi csillagpontos ellátás helyett. [4] 2. Többszint¶ ellátási hálózatokban készletszintek alakulását modellez® és különböz® rendelési stratégiákat kezel® sztochasztikus modellt készítettem. Kimutattam, hogy e modell Monte Carlo szimulációjával ezen rendszerek robosztus és hatékony módon modellezhet®k és optimalizálhatók.

(Kapcsolódó publikációk: [1, 10, 12, 14, 18, 20, 21])

(a) Többszint¶ ellátási hálózatokban feltérképeztem, hogy az elméleti modellek alkalmazása helyett historikus adatokból feltárt fogyásigények alapján konstruált eloszlásfüggvények használatával jóval pontosabb modell alkotható, mellyel a valós rendszer hatékonyabban modellezhet®. Ennek támogatására kifejlesztettem egy sztochasztikus szimulátort, melyet alkalmazva a Monte Carlo módszertanon alapulva sikeresen optimalizáltam kétszint¶ ellátási hálózatokat mind SQP, mind PSO algoritmusok alkalmazásával. [10, 12, 14, 18, 20] (b) Az elkészült szimulátor és optimalizációs technika segítségével olyan módszertant fejlesztettem ki, melynek segítségével meghatározhatók az ellátási hálózatban megjelen® legfontosabb kulcsmutatók. Az elkészített, Monte Carlo módszertanon alapuló paraméterérzékenység-vizsgálat eredményeinek megjelenítésére egy újfajta metódust alkottam. Az új típusú vizualizációs technika segítségével könnyen értelmezhet® formában jelenítettem meg a érzékenységanalízis eredményeit, mellyel a vállalati döntéshozók számára is könnyen felderíthet®ek a rendszer bemeneti változói és kimenetei közötti összefüggések, vagyis meghatározhatók a legfontosabb kulcsmutatók. [1, 21] 3

3. Nagy (biogenetikai) adatmátrixokban rejl® információk feltárására újszer¶ biclustering keresési adatbányászati technikákat hoztam létre.

(Kapcsolódó publikációk: [5, 6, 8, 13, 19, 22])

(a) Feltártam és elméletileg megalapoztam a zárt gyakori elemhalmazok keresésének és az ún. biclustering technika közötti szoros összefüggést, nevezetesen hogy a módszerek megfelel® interpretálása és paramétereinek helyes megválasztása esetén a két módszer ugyanazt az eredményhalmazt szolgáltatja. [6] (b) Olyan új típusú algoritmust fejlesztettem ki, mely az irodalomban fellelhet® eddigi megoldásokhoz képest gyorsabban képes megtalálni az összes konstans típusú zárt gyakori elemhalmazt bemeneti bináris, vagy {-1, 0, 1} típusú adatban. A létrehozott módszer robosztusabb a bemenet méretére vonatkozóan, mint az eddigi megoldások, és pontosan megtalálja a széles körben elfogadott és validált biclustering algoritmus által szolgáltatott elemhalmazokat. [6, 8, 13, 19] (c) A megtalált elemhalmazok ún. tiszta biclusterek, vagyis nulláktól mentesek. Nullák, vagyis hibás vagy értéktelen adatok megengedésére a feltárt elemhalmazokban egy olyan új összevonási technikát dolgoztam ki, mely iteratív módon a Tanimoto távolságon alapulva egyesíti az egyes elemhalmazokat, így alakítva ki egyre nagyobb és egyre kevésbé tiszta biclustereket. [6] (d) Olyan adat-transzformációs technikát dolgoztam ki, mellyel az alapvet®en csak bináris adatokat kezel® algoritmusokat is alkalmassá lehet tenni a {-1, 0, 1} típusú adatok kezelésére, és így az éppen ellentétesen változó adatfolyamok felderítésére is. [6] (e) Ugyancsak kidolgoztam egy olyan új típusú algoritmust, mely az ún. bit-table reprezentációt használva, egyszer¶ mátrix m¶veletek segítségével képes biclusterek keresésére bináris adathalmazokon. A bevezetett technika egyszer¶ m¶ködéséb®l adódóan különösen könnyen értelmezhet® és ennek megfelel®en gyors és egyszer¶ implementálhatóságot biztosít. [5]

4

Kapcsolódó eredmények (Kapcsolódó publikációk: [7, 9])

Az irodalomban Mimikri-ként ismert módszer alapján kifejlesztettem egy olyan új típusú szoftvert, melynek segítségével a felhasználó képes megbecsülni fehérjék és fehérjehalmazok közötti immunológiai keresztreakció valószín¶ségét. A program segítségével könnyen értelmezhet® formában vizualizáltam a kombinatorikai számításokon alapuló módszer eredményeit. 4.

Az eredmények gyakorlati hasznosítása

A dolgozatban ismertetett eredmények gyakorlati hasznosítása részben már megtörtént. Az E.ON Hungária Zrt. mobilszerel®i ellátási hálózatának teljes átalakítása valósult meg 2012-ben, melynek során a 600 mobilszerel®b®l álló otta anyagigényének ellátására a korábbi csillagpontos megoldás helyett az általunk ajánlott körutas ellátást vezették be. Ennek hatására a vállalat éves szinten komoly megtakarítást könyvelhet el a kiszolgálási szint javulása mellett. Ugyancsak az E.ON Hungária Zrt. raktározási és rendelési politikájánál konkrét ajánlásokat tettünk az egyes anyagok besorolására, illetve azok csoportosítására, hogy melyeket érdemes MRP rendszerrel kezelni és melyeket nem. A rendelési tételnagyság és rendelési gyakoriság általunk történt optimalizálásának hatására a vállalat teljes raktározási készletét nagymértékben tudta csökkenteni, mellyel komoly raktározási költségeket spórol meg. Az értekezés gyakori elemhalmazok keresése kapcsán bioinformatikai adatok vizsgálatát mutatta be, melyhez egy webes alkalmazás (GeneFuncster) implementálása meg is történt, mely elérhet® az internetes közösség számára. A kifejlesztett módszerek azonban nem csak biológiai eredet¶ adatokon szolgáltatnak értékelhet® eredményeket, jelenleg ajánlórendszerek részekét, felhasználói preferenciák feltárásában való alkalmazhatóságaikat vizsgáljuk.

5

5.

Tézisekhez kapcsolódó publikációk

Cikkek nemzetközi folyóiratban [1] Gábor Belvárdi, András Király, Zoltán Gyozsán Tamás Varga, and János Abonyi. Monte carlo simulation based performance analysis of supply chains. International Journal of Managing Value and Supply Chains, 3(2):115, 2012. [2] András Király and János Abonyi. A novel approach to solve multiple traveling salesmen problem by genetic algorithm. Computational Intelligence in Engineering, 313:141151, 2010. [3] András Király and János Abonyi. Optimization of multiple traveling salesmen problem by a novel representation based genetic algorithm. In Intelligent Computational Optimization in Engineering, volume 366 of Studies in Computational Intelligence, pages 241269. Springer Berlin / Heidelberg, 2011. [4] András Király and János Abonyi. Redesign of the supply of mobile mechanics based on a novel genetic optimization algorithm using google maps api. Engineering Applications of Articial Intelligence, 2013, under review. [5] András Király, Attila Gyenesei, and János Abonyi. Bit-table based biclustering and frequent closed itemset mining in high-dimensional binary data. Lecture Notes in Computer Science, 2013, under review. [6] András Király, Asta Laiho, János Abonyi, and Attila Gyenesei. Novel techniques and an ecient algorithm for closed pattern mining. Pattern Recognition Letters, 2013, under review. [7] Katalin Kristóf, Krisztina Madách, Noémi Sándor, Zsolt Iványi, András Király, Anna Erdei, and Eszter Tulassay. Impact of molecular mimicry on the clinical course and outcome of sepsis syndrome. Molecular Immunology, 2011. [8] Asta Laiho, András Király, and Attila Gyenesei. Genefuncster: A web tool for gene functional enrichment analysis and visualisation. In David Gilbert and Monika Heiner, editors, Computational Methods in Systems Biology, Lecture Notes in Computer Science, pages 382385. Springer Berlin Heidelberg, 2012.

6

[9] Krisztina Madách, Katalin Kristóf, Eszter Tulassay, Zsolt Iványi, Anna Erdei, András Király, János Gál, and Zsuzsa Bajtay. Mucosal immunity and the intestinal microbiome in the development of critical illness. ISRN Immunology, 2011, 2011. [10] Tamás Varga, András Király, and János Abonyi. Improvement of pso algorithm by memory based gradient search - application in inventory management. In Swarm Intelligence and Bio-Inspired Computation: Theory and Applications. Springer Berlin / Heidelberg, 2013, accepted.

Cikkek hazai folyóiratban [11] András Király and János Abonyi. A google maps based novel approach to the optimization of multiple traveling salesman problem for limited distribution systems. Acta Agraria Kaposváriensis, 14(3):114, 2010. [12] András Király, Gábor Belvárdi, and János Abonyi. Determining optimal stock level in multi-echelon supply chains. Hungarian Journal of Industrial Chemistry, 39(1):107112, 2011.

Konferencia kiadványokban megjelent publikációk [13] János Abonyi, András Király, and Attila Gyenesei. Biclustering based on bittable based frequent itemset mining. In International Workshop on Clustering High-Dimensional Data (CHDD 2012), Naples, Italy, 2012. [14] László Dobos, András Király, and János Abonyi. Economic oriented stochastic optimization of model predictive controlled processes. In Veszprém Optimization Conference: Advanced Algorithms (VOCAL), Veszprém, Hungary, 2010. [15] András Király and János Abonyi. Optimization of multiple traveling salesmen problem by a novel representation based genetic algorithm. In 10th International Symposium of Hungarian Researchers on Computational Intelligence and Informatics, Budapest, Hungary, 2009. [16] András Király and János Abonyi. Google maps alapú programcsomag útvonalhálózat elemzésének és optimalizációjának támogatására. In Informatika Korszer¶ Technikái Konferencia, Dunaújváros, Hungary, 2010.

7

[17] András Király and János Abonyi. A google maps based novel approach to the optimization of limited distribution systems. In VIII. Alkalmazott Informatika Konferencia, Kaposvár, Hungary, 2010. [18] András Király and János Abonyi. Optimális szállítási gyakoriság meghatározása többszint u elllátási hálózatokban. In Mobilitás és Környezet Konferencia, Veszprém, Hungary, 2011. [19] András Király, János Abonyi, Asta Laiho, and Attila Gyenesei. Biclustering of high-throughput gene expression data with bicluster miner. In Data Mining Workshops (ICDMW), 2012 IEEE 12th International Conference, pages 131138, dec. 2012. [20] András Király, Tamás Varga, and János Abonyi. Constrained particle swarm optimization of supply chains. In International Conference on Mathematical, Computational and Statistical Sciences, and Engineering, Zurich, Switzerland, 2012. [21] András Király, Tamás Varga, Gábor Belvárdi, Zoltán Gyozsán, and János Abonyi. Monte carlo simulation based sensitivity analysis of multiechelon supply chains. In Factory Automation, Veszprém, Hungary, 2012. [22] Asta Laiho, Attila Gyenesei, András Király, János Abonyi, Colin Semple, Chris Haley, and Wenhua Wei. High-throughput detection of epistasis in studies of the genetics of complex traits. In 9th annual in-

ternational conference on Computational Systems Bioinformatics (CSB 2010), Stanford, California, 2010.

8