Changes between Version 44 and Version 45 of GAIIA


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

--

Legend:

Unmodified
Added
Removed
Modified
  • GAIIA

    v44 v45  
    6767
    6868
    69 This 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.   
     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
     71   
    7072[[Image(floating_nodes.jpg)]]
    71  * single point crossover
    72  * 3 types of mutation:
     73
     74'''Genetic operators'''
     75
     76a. ''Single Point Crossover''
     77
     78The crossover operator for a chromosome representation used follows the following steps:
     79a. a cut position is randomly selected ( in the above example the cut point is chosen between genes four and five) and for each chromosome results a head and a tail segment;
     80b. the first offspring is obtained by joining the head segment of the first parent with the combination of the tail segments both parents; more specific, for each gene the task is taken from the first parent and the assigned task is taken from the parent;
     81c. the second offspring is obtain the same way, using the head segment of the first parent and the combination of tail segments of both parents, but this time, the tasks are taken from the second parent while the assigned processors are taken from the first parent
     82
     83b ''Simple Gene Mutation''
     84
     85First is selected a chromosome and  a randomly selected gene is changed by assigning the task described by the gene to a new processor with the earliest start time.
     86
     87c. ''Swap Gene Mutation''
     88
     89It is selected a processor that is assigned to run at least two jobs with topological level. Then are randomly selected two tasks with the same topological level assigned to the current processor and the tasks are interchanged if the first task to execute has less children then the second one
     90
     91d. ''Topological Hyper-Mutation''
     92
     93Whenever a chromosome is affected by this type of mutation, a node from the free node list is randomly selected. Its current topological level is increased and its position in the chromosome is modified in order to reveal the new topological order. Then, all direct predecessors of the selected node are investigated to decide whether they became free floating nodes. If they do, they are inserted in free floating node list corresponding to the current chromosome. If the modified node is no longer a free floating node list (its topological level is equal to the minimum topological level of its successors minus 1), it is removed from the list.
    7394
    7495
    75 {{{
    76 - partial-gene mutation
    77 - swap-gene mutation
    78 - topological hyper-mutation
    79 }}}
    8096
    8197==  The Immune Algorithms ==