{"id":{"repo_id":"usf","oai_identifier":"oai:digitalcommons.usf.edu:etd-9113"},"canonical_url":"https://search.ndltd.org/etd/usf/oai:digitalcommons.usf.edu:etd-9113","repository":{"repo_id":"usf","name":"University of South Florida","base_url":"https://digitalcommons.usf.edu/do/oai/"},"display":{"title":"Parallelization of Genetic Algorithm to Solve MAX-3SAT Problem on GPUs","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Shivram, Prakruthi"],"institution":"University of South Florida","degree_name":"Master of Science (M.S.)","degree_level":"Thesis","degree_discipline":"Computer Science and Engineering","degree_department":null,"school":null,"contributors":["Srinivas Katkoori, Ph.D.","Yicheng Tu, Ph.D.","Hao Zheng, Ph.D."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2019,"date_issued":"2019-03-20T07:00:00Z","date_published":"2019-03-20T07:00:00Z","updated_at":"2026-11-19T08:44:36Z","subjects":["Computer Sciences"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.usf.edu/etd/7916","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.usf.edu/etd/7916","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.usf.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.usf.edu%3Aetd-9113","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Srinivas Katkoori, Ph.D.","Yicheng Tu, Ph.D.","Hao Zheng, Ph.D."]},{"key":"dc:creator","label":"Author","values":["Shivram, Prakruthi"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2019-03-20T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science and Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis","M.S."]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (M.S.)"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of South Florida"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Sciences"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.usf.edu/etd/7916"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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."]},{"key":"dc:title","label":"Title","values":["Parallelization of Genetic Algorithm to Solve MAX-3SAT Problem on GPUs"]}]}],"canonical_facts":{"dc:contributor":["Srinivas Katkoori, Ph.D.","Yicheng Tu, Ph.D.","Hao Zheng, Ph.D."],"dc:creator":["Shivram, Prakruthi"],"dc:date":["2019-03-20T07:00:00Z"],"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."],"dc:identifier":["https://digitalcommons.usf.edu/etd/7916"],"dc:subject":["Computer Sciences"],"dc:title":["Parallelization of Genetic Algorithm to Solve MAX-3SAT Problem on GPUs"],"thesis:degree_discipline":["Computer Science and Engineering"],"thesis:degree_level":["Thesis","M.S."],"thesis:degree_name":["Master of Science (M.S.)"],"thesis:institution_name":["University of South Florida"]},"updated_at":"2026-11-19T08:44:36Z"}