Application of hardware-accelerated genetic algorithms to graph-problems

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

In terms of the thesis a hardware-acceleration of the classical genetic algorithm was realized. The device is capable of running the classical genetic algorithm on hardware and solving a simple linear programming problem and graph-problems (vertex-coloring, Hamilton-cycle). The results demonstrate that a genetic algorithm is realizable on hardware reducing the runtime of the algorithm.

Genetic algorithms are very well parallelizable, thus the runtime of the algorithm can be reduced on dedicated hardware. The operation of the algorithm is demonstrated on graph-problems. Efficient solutions of graph-problems are very important, because a lot of practical problems can be modeled by them. Finding a Hamilton-cycle corresponds to different routing problems and the scheduling, while resource-sharing problems can be modeled with graph-coloring, for example. The aim of the thesis is thus to solve the two mentioned problems via hardware-accelerated genetic algorithms to increase the quality of solutions generated in a given timespan.

During the design and implementation of the device the aim was to parallelize the algorithm as much as possible (beside sensible resource consumption), therefore reducing the runtime of the algorithm. The implemented algorithm runs on FPGA. It was chosen because it is configurable, and thus reduces the time required for implementation and prototyping, while realizing arbitrary digital hardware.

The hardware is controlled by a PC software. The software communicates with the FPGA, prepares the task and processes runtime data and displays the results.

The thesis describes the theoretical background necessary to understand the topic. It contains the requirements for the implemented system, the hardware and software specification based on these requirements and detailed test results.

Downloads

Please sign in to download the files of this thesis.