Back to search

University of South Florida

Parallelization of Genetic Algorithm to Solve MAX-3SAT Problem on GPUs

Abstract

dc:description

There are many combinatorial optimization problems such as flow shop scheduling, quadraticassignment problem, traveling salesman problem, that are computationally intractable. Genetic Algorithm is a heuristic algorithm used to find an answer to combinatorial optimization problems. MAX-3SAT is an example of combinatorial optimization problem which has wide range of applications as many real world problems can be translated to MAX-3SAT problem. Genetic algorithms are suitable to solve MAX-3SAT problems but usually undergo premature convergence. To prevent this convergence and maintain diversity, one possible solution is to use large population size. This increases computation cost and time. Since Genetic Algorithms compute the same fitness function on large data (population), it provides data and instruction parallelism. Hence Genetic algorithm can be scaled on to GPU architecture. GPUs are affordable, efficient parallel computing hardware. Hence in this thesis, we use CUDA framework to implement a parallel version of Genetic Algorithm on GPU. We use the MAX-3SAT problem to verify our algorithm. Compared to the CPU implementation with similar workload, the proposed GPU implementation is upto four times faster and often finds better results.

Degree

thesis:*
Name thesis:degree_name
Master of Science (M.S.)
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Computer Science and Engineering
Grantor
University of South Florida
Year dc:date
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Shivram, Prakruthi
Contributors dc:contributor
  • Srinivas Katkoori, Ph.D.
  • Yicheng Tu, Ph.D.
  • Hao Zheng, Ph.D.

Subjects

dc:subject × 1

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.usf.edu/etd/7916

Chain of custody

source
Harvested from
University of South Florida
Base URL
digitalcommons.usf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Shivram, Prakruthi. Parallelization of Genetic Algorithm to Solve MAX-3SAT Problem on GPUs. Thesis thesis, University of South Florida, 2019. https://digitalcommons.usf.edu/etd/7916