20.500.12556/DKUM-17298 IMPLEMENTACIJA GENETSKEGA ALGORITMA NA GRAFIČNEM PROCESORJU IMPLEMENTATION OF GENETIC ALGORITHM ON GRAPHICS PROCESSOR V diplomskem delu smo poskusili ugotoviti, kakšne pohitritve lahko dosežemo v izvajanju genetskega algoritma, če ga izvajamo na grafičnem procesorju računalnika. V obeh implementacijah, na CPU in GPU, uporabimo turnirsko selekcijo, križanje z delno preslikavo in vstavitveno mutacijo. Težimo seveda k čim večji pohitritvi na grafičnem procesorju. Najprej predstavimo genetski algoritem. Opišemo njegovo definicijo, zgodovino genetskih algoritmov in njihovo trenutno uporabo ter potek izvajanja genetskega algoritma. Sledi opis problema trgovskega potnika, nad katerim smo izvajali genetski algoritem. V nadaljevanju še opišemo grafični procesor in arhitekturo CUDA. Sledi razlaga implementacije genetskega algoritma. Implementirani genetski algoritem na grafičnem procesorju smo primerjali z implementacijo na centralnem procesorju in predstavimo rezultate. In this thesis we will try to find out, what kind of speedups we can get if the genethic algorithm runs on the graphics processor. In both CPU implementation and GPU one, we use a tournament selection, partially-mapped crossovers and an insertion mutation. Of course we want to maximize the speedups on the graphics processor. First we present a genethic algorithm. We describe its definition, present its history and current use. We also consider the methodology of the genethic algorithm. Then we describe the travelling salesman problem, realised by the genethic algorithm. The next section provides the description of the graphics processor and CUDA architecture. Then we present our implementation of the genethic algorithm on GPU and we compare that implementation with the implementation on CPU. At the end results are presented. genetski algoritem grafični procesor CUDA kromosom gen paralelno računanje problem trgovskega potnika genethic algorithm graphics processor CUDA genome gen parallel computing traveling salesman problem true true false [T. Hauzer] Slovenski jezik Angleški jezik Diplomsko delo 2011-01-19 08:03:01 2011-02-14 10:25:19 2022-04-13 09:22:54 2023-12-22 03:21:35 2011 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.876.5:004.42(043.2) 15061526 URN:SI:UM:DK:2RTCJWSU VS_Hauzer_Tomaz_2011.pdf VS_Hauzer_Tomaz_2011.pdf 1 70C84FDEB8A035F9E3D6E2BEC06FF6DA 9cdfa6a0b30e5a6dd7a047a9123a68873963323fd33119bdf1583c16dd1deb78 db665fab-7c04-11eb-bb7a-00155d0001ca 20.500.12556/dkum/9c81655b-4e1e-47fd-a5a3-bff06d7ab41f https://dk.um.si/Dokument.php?lang=slv&id=20106 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0