FPGA-based implementation of general purpose evolutionary methods

OData support
Supervisor:
Kovács Dániel László
Department of Measurement and Information Systems

Over the past few decades, evolutionary computing methods, especially genetic algorithms are used countless times for analytically difficult or intractable optimization problems to approximate a globally optimal solution. These algorithms are quite computationally intensive, but their structure is very well parallelizable.

In the current work it is shown that the runtime of a genetic algorithm can be significantly reduced by an architecture which supports massive parallelism, by which the algorithms can be used in a wider area.

Due to the FPGA (Field Programmable Gate Array) architecture’s support for high degree of parallelization, respectively thanks to its reprogrammable nature, it is most suitable for a cost-effective realization of a prototype. In my thesis I present a general purpose genetic algorithm prototype, implemented in FPGA, including its inherent capabilities and limitations. The implemented prototype can be used as a hardware acceleration of an evolutionary simulation or a subsystem of a complex real-time decision support system improving the speed of the algorithm with orders of magnitude compared to purely software implementations.

Due to the modularity of the system, problem-specific fitness units can be developed separately requiring the necessary knowledge. To demonstrate this a case-study is presented applying the system for non-linear programming (NLP) and optimization problems.

This is followed by the presentation of test results, their evaluation, and summary. Finally further development directions are outlined.

Downloads

Please sign in to download the files of this thesis.