|
Akcelerace částicových rojů PSO pomocí GPU
Krézek, Vladimír ; Schwarz, Josef (oponent) ; Jaroš, Jiří (vedoucí práce)
Tato práce se zabývá technikou PSO (Particle Swarm Optimization neboli Optimalizace pomocí částicových rojů), s jejíž pomocí je možné řešit komplexní problémy. Tuto techniku lze využít při řešení složitých kombinatorických problémů (obchodní cestující, úloha o batohu), návrh integrovaných obvodů a antén, v oborech jako je biomedicína, robotika, umělá inteligence nebo i finančnictví. Přestože je algoritmus PSO velice efektivní, čas nezbytný pro nalezení vhodného řešení reálných problémů často přesahuje hranice únosnosti. Cílem této práce je tedy urychlit běh tohoto algoritmu pomocí grafického adaptéru, který nabízí velmi vysoký výpočetní potenciál při zachování příznivé ceny a rozměru. Pro demonstrační účely a ověření kvality implementace byl zvolen problém rozhodnutelnosti systému logických formulí (SAT), jenž patří do třídy NP-úplných problémů. Redukcí časové náročnosti algoritmu PSO při řešení SAT problému jsme tedy schopni akcelerovat celou třídu úloh a řešit problémy, které byly dosud prakticky neřešitelné.
|
| |
| |
|
Akcelerace částicových rojů PSO pomocí GPU
Krézek, Vladimír ; Schwarz, Josef (oponent) ; Jaroš, Jiří (vedoucí práce)
Tato práce se zabývá technikou PSO (Particle Swarm Optimization neboli Optimalizace pomocí částicových rojů), s jejíž pomocí je možné řešit komplexní problémy. Tuto techniku lze využít při řešení složitých kombinatorických problémů (obchodní cestující, úloha o batohu), návrh integrovaných obvodů a antén, v oborech jako je biomedicína, robotika, umělá inteligence nebo i finančnictví. Přestože je algoritmus PSO velice efektivní, čas nezbytný pro nalezení vhodného řešení reálných problémů často přesahuje hranice únosnosti. Cílem této práce je tedy urychlit běh tohoto algoritmu pomocí grafického adaptéru, který nabízí velmi vysoký výpočetní potenciál při zachování příznivé ceny a rozměru. Pro demonstrační účely a ověření kvality implementace byl zvolen problém rozhodnutelnosti systému logických formulí (SAT), jenž patří do třídy NP-úplných problémů. Redukcí časové náročnosti algoritmu PSO při řešení SAT problému jsme tedy schopni akcelerovat celou třídu úloh a řešit problémy, které byly dosud prakticky neřešitelné.
|