| 60 | |
| 61 | == The genetic algorithm == |
| 62 | ''' 1. Chromosome representation ''' |
| 63 | |
| 64 | The 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 | |
| 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. |
| 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 | |