Skip to content

Paralellized the Genetic Algorithm to solve the Knapsack Problem. The algorithm performs mutations and crossovers on the first 30% most fit individuals in a batch, the speed-up from sequential to parallel is at least 2 seconds. Found an optimization that ensures at least 10 seconds speed-up using only 4 threads.

Notifications You must be signed in to change notification settings

stefancocioran/Parallelized-Genetic-Algorithm-Knapsack-Problem

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

1 Commit
 
 
 
 
 
 
 
 

Repository files navigation

// Copyright (C) 2021 Cocioran Stefan 331 CA

 - tema1_par - 

The memory for initial generation was allocated here because calloc/malloc is 
not thread-safe and the thread function (run_genetic_algorithm) arguments were 
passed as a structure in order to avoid the usage of global variables. Threads 
are created and the execution of their function begins. When the execution finishes, 
the resources used are freed.

 - genetic_algorithm_par

First of all, before starting the actual execution of the algorithm, the setting 
of the initial generation is parallelizded, being equally divided between threads. 
I tried to parallelize almost every "for" loop I could, using "start" and "end" 
indexes calculated by the formulas presented in the course/laboratory. The barrier 
was used multiple times to ensure that there will be no race condition and the 
individuals' genetic data was computed properly before proceeding with further 
calculations and data manipulation (fitness computions, mutations, crossovers, 
copying of individuals). 
 
The compare function used by "qsort" had a "for" loop which was iterating through 
the chromosomes of an individual. I observed that there is the exact same loop in 
the "compute_fitness" function. In order to not iterate twice through the same 
elements, the chromosome incrementation instructions that should have been done 
here were moved. The value of "first_count" and "second_count" variables were stored 
in an additional field of the "individual" structure.

The fitness compution function receives two extra parameters, the number of threads 
and the thread id so that it can be parallelized using the same principle and formulas. 

About

Paralellized the Genetic Algorithm to solve the Knapsack Problem. The algorithm performs mutations and crossovers on the first 30% most fit individuals in a batch, the speed-up from sequential to parallel is at least 2 seconds. Found an optimization that ensures at least 10 seconds speed-up using only 4 threads.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published