Acceleration of Particle Swarm Optimization Using GPUs

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é.This work deals with the PSO technique (Particle Swarm Optimization), which is capable to solve complex problems. This technique can be used for solving complex combinatorial problems (the traveling salesman problem, the tasks of knapsack), design of integrated circuits and antennas, in fields such as biomedicine, robotics, artificial intelligence or finance. Although the PSO algorithm is very efficient, the time required to seek out appropriate solutions for real problems often makes the task intractable. The goal of this work is to accelerate the execution time of this algorithm by the usage of Graphics processors (GPU), which offers higher computing potential while preserving the favorable price and size. The boolean satisfiability problem (SAT) was chosen to verify and benchmark the implementation. As the SAT problem belongs to the class of the NP-complete problems, any reduction of the solution time may broaden the class of tractable problems and bring us new interesting knowledge.