Hardveresen gyorsított genetikus algoritmus alkalmazása gráf-problémákra

OData támogatás
Konzulens:
Kovács Dániel László
Méréstechnika és Információs Rendszerek Tanszék

A diplomamunka keretén belül elkészült egy klasszikus genetikus algoritmus hardveres implementációja. Az eszköz alkalmas genetikus algoritmus hardveres környezetben való futtatásának vizsgálatára és gráf-problémák megoldására (csúcsszínezés, Hamilton-kör). Az eredmények alátámasztják, hogy genetikus algoritmus megvalósítható és a hardveres megvalósítás valóban képes gyorsítani az algoritmus futását.

A genetikus algoritmusok nagyon jól párhuzamosíthatóak, ezért dedikált hardveren való megvalósítás esetében az algoritmus futási ideje lecsökkenthető. Az algoritmus működése gráf-problémákon keresztül kerül bemutatásra. A gráf-problémák hatékony megoldása nagy jelentőséggel bír, mert számos, a gyakorlatban előforduló probléma visszavezethető rájuk. A különböző útvonal-tervezési problémák Hamilton-kör keresésre, míg az ütemezési/erőforrás felosztási problémák gráf-színezési feladatra vezethetők vissza. A dolgozat célja e két gráf-probléma genetikus algoritmussal való megoldása.

A tervezés, és később a megvalósítás során egyaránt a lehető legnagyobb fokú párhuzamosítás (ésszerű erőforrás felhasználás mellett) elérése volt a cél, ezáltal az algoritmus futási sebességének növelése. Ennek érdekében dedikált hardver végzi el a genetikus algoritmus futtatását. A kiválasztott hardver-platform FPGA, mivel tetszőleges funkcionalitású hardver alakítható ki benne.

Az FPGA-val egy PC-oldali szoftver tart kapcsolatot. A szoftver végzi el az algoritmus konfigurációját és az algoritmus futásának eredményeit feldolgozza, majd megjeleníti.

A dolgozatban megtalálható a téma megértéséhez szükséges elméleti háttér, a megvalósítandó rendszerrel szemben támasztott követelmények, és a követelmények alapján specifikált szoftver és hardver leírása, valamint ez elért eredmények.

Letölthető fájlok

A témához tartozó fájlokat csak bejelentkezett felhasználók tölthetik le.