Changes between Version 49 and Version 50 of GAIIA

Timestamp:

Jan 13, 2010, 6:02:27 PM (14 years ago)

Author:

mihai.istin

Comment:

--

GAIIA

@@ -134 +134 @@
 As can be seen in the above figure, most of the functions of the proposed algorithm have significant execution time (10 to 50%) and can be easily parallelized because they are applied independently to each chromosome from the population. In the next paragraphs we will explain what each function does and how it is better to be parallelized. 
 
+First we will present the parallel version for the genetic algorithm and then we will present the aspects related to the immune algorithm parallelization. 
+
+''1.1 The Parallel Genetic Algorithm'' 
+
 The presented analysis reveals that the most time consuming part of the algorithm is the evaluation (or the computation of fitness for each individual). If we analyze the complexity of this phase of the algorithm we will obtain a O(N*M), where N is the number of nodes, M is the maximum number of predecessor that a node can have. More, this function is applied on each of the C chromosomes leading to a total complexity equals to O(C*N*P). If we also consider that this function is applied on each generation, the total complexity is O(G*C*N*M).
 
@@ -144 +148 @@
 Another interesting approach is used for the selection algorithm. Here the parallelization is not strait forward. The population of chromosomes will be divided in a number of chunks equal to the number of threads. At each step (of the total TOUR_SIZE steps), each thread will randomly choose an unselected individual from a single chunk. The chunks assignment to threads is done in a round robin manner. After each thread has completed the tour, the individuals with the best fitness is selected to survive in the next generation and the process is started over.     
 
-
- * The Parallel Execution Model
+[[Image(tour.jpg)]]
+
+''1.2 The Parallel Immune Algorithm''
+
+First of all we have to mention that for the evaluation of the chromosome we use the same approach presented for the genetic algorithm.
+
+The selection method for the immune algorithm is a simple selection of the best individuals and it is based on choosing the first individuals after they have been sorted. So we will need a parallel sort algorithm. The chosen algorithm is a hybrid algorithm between Quick Sort and Merge Sort. First the population is divided into a number of chunks equal to the number of threads and each thread will sort its chunk using the Quick Sort algorithm (first figure). In the second phase each two distinct chunks will be merged until we will obtain a sorted vector (second figure).  
+
+[[Image(sort1.jpg)]]
+
+[[Image(sort2.jpg)]]
+
+In order to produce the population of clones we have first to determine the number of clones corresponding to each individual. Then we have to distribute the cloning process in order to assure load balancing among threads. For this we use a parallel algorithm to compute the partial sums.  The same approach will also be used for the mutation process.
+
+
+''1.3 The Parallel Execution Model''
+
 
 [[Image(execp.jpg)]]