Changes between Version 48 and Version 49 of GAIIA


Ignore:
Timestamp:
Jan 12, 2010, 10:58:43 PM (14 years ago)
Author:
mihai.istin
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • GAIIA

    v48 v49  
    136136The 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).
    137137
    138 Starting from the complexity of the algorithm the easiest and most efficient way to parallelize this function is to use a parallel for with guided scheduling because some individuals survive to the next generation without been affected by mutation and thus there is no need to be evaluated again.
     138Starting from the complexity of the algorithm the easiest and most efficient way to parallelize this function is to apply in on multiple individuals at once. The reason for this is that the evaluation of each individual is independent. This can be done if we use a parallel for with guided scheduling because some individuals survive to the next generation without been affected by mutation and thus there is no need to be evaluated again.
     139After computing the first two terms of the fitness function for each individuals, we also have to compute the last term. This term represents the value of each individual in comparison with the individual with the minimum makespan. For this we have first to compute the minimum makespan. This is also done in parallel. Each thread will compute the minimum makespan from its corresponding chunk (from a static scheduling) and will place the result in a shared memory. Next, the master will compute the overall minimum am will place it in the shared memory. Then, each thread will finally compute the fitness for each individual from its chunk.
     140
     141
     142For the crossover is used a static scheduling because each two individuals will recombine in order to produce offspring. On the other hand for the mutation operator we will also use a guided scheduling because for the genetic algorithm an individual will suffer a mutation only with a certain probability, so some individuals will not be affected. For the immune algorithm, the proper scheduling strategy is static because each individual will be affected by mutation.       
     143
     144Another 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.     
    139145
    140146