Die Arbeit widmet sich der Rekonstruktion von Polygonzügen aus 2D-Punktwolkendaten. Die Daten wurden mittels Laser-Scannern erhoben und bilden Grundrisse von historischer Architektur ab. Die Arbeit beleuchtet die Arbeitsfähigkeit von GPU-parallelisierten genetischen Algorithmen, bei dem Versuch aus diesen Daten Polygone und Streckenzüge zu erheben die zu den ursprünglichen Daten kongruent sind.:1 Introduction 5 1.1 Point Cloud Reconstruction 5 1.2 Genetic Algorithms 7 1.3 Evaluation of Results 8 2 Evolutionary Algorithms 10 2.1 Metaheuristic Approaches 10 2.1.1 NPO-problems 11 2.1.2 Metaheuristics 11 2.2 Evolutionary Computing 12 2.2.1 Definition and Motivation 13 2.2.2 Fundamentals and Terminology 13 2.2.3 The Genetic Algorithm 14 2.2.4 Individuals in Genetic Algorithms 15 2.2.5 Components of Genetic Algorithms 15 2.3 Parallel Genetic Algorithms 20 2.3.1 Taxonomy for Parallel Genetic Algorithms 20 2.3.2 Global Parallel Genetic Algorithms 20 3 Hardware Accelerators 22 3.1 SIMD in Global Parallel Gentic Algorithms 22 3.2 OpenCL 23 4 Concepts and Implementation 25 4.1 Input Data and Pre-Proccesing 26 4.2 Genotype Construction 30 4.3 The Fitness Function 33 4.4 Mutation 35 4.5 The Genetic Algorithm 36 4.6 Global Parallelization and GPU-Usage 38 5 Results and Evaluation 40 5.1 Wall-Time and Fitness 40 5.2 Visual Observation 43 6 Conclusion 44 Appendices 47 A Terminology for Evolutionary Algorithms 48 B PC1 49 C PC2 50 D PC3 51 E PC1 Convergence 52 F PC2 Convergence 53 G PC3 Convergence 54 H Layout Reconstruction 1 55 I Layout Reconstruction 2 56 J t-test for implementation comparison 57