Changes between Version 43 and Version 44 of GAIIA


Ignore:
Timestamp:
Jan 12, 2010, 7:24:07 PM (14 years ago)
Author:
mihai.istin
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • GAIIA

    v43 v44  
    5858 
    5959
     60 
     61== The genetic algorithm ==
     62''' 1. Chromosome representation '''
     63
     64The chromosome representation is based on the topological levels of the nodes. The order of the nodes within a chromosome is a valid topological sort where the first node is an entry node (it has no successors) while the last node is an exit node (it has no successor).
     65
     66[[Image(chromosome.jpg)]]
     67
     68
     69This chromosome encoding assures that none of the genetic operators that will be further described will not violate the dependencies between tasks. So this seems to be a very convenient encoding, but it also has drawbacks which consist in the fact that the explorable solution space will not be entirely covered. This happens because there are some special nodes that can be placed on multiple topological levels without violating the topological order. These nodes are called '''floating nodes''' and are characterized as nodes that have a maximum topological level grater than their minimum topological level. The minimum topological level is the level computed during an usual topological sort, while the maximum topological level is the one computed on the transposed graph.   
     70[[Image(floating_nodes.jpg)]]
     71 * single point crossover
     72 * 3 types of mutation:
     73
     74
     75{{{
     76- partial-gene mutation
     77- swap-gene mutation
     78- topological hyper-mutation
     79}}}
     80
    6081==  The Immune Algorithms ==
    6182
     
    6990[[Image(form1.jpg)]]
    7091
    71  * uses genetic algorithms
    72  * chromosome representation:
    73 [[Image(chromosome.jpg)]]
    74  * uses the topological level and the inverse topological level of a node
    75  * introduces the notion of floating nodes:
    76 [[Image(floating_nodes.jpg)]]
    77  * single point crossover
    78  * 3 types of mutation:
    7992
    80 
    81 {{{
    82 - partial-gene mutation
    83 - swap-gene mutation
    84 - topological hyper-mutation
    85 }}}
    8693
    8794== The Parallel Solution ==