Search code examples
schedulinggenetic-algorithm

how to Crossover without Repeatition

i am doing Static Flow-Shop Scheduling problem, i considered 10 tasks and 3 machines. in permutation i face many possible sequence through which tasks should go through machines. now i consider the following two sequence and i would like how to crossover them in order to get non-repetitive child chromosomes .

first sequence = T3 T2 T5 T6 T9 T1 T4 T7 T8 T10

second sequence= T3 T2 T6 T8 T1 T5 T4 T7 T9 T10

now how to make child-sequence so that it does not have repetition and all task are present in child-sequence as well.

Solution

  • Your question does not include any code for us to review, thus I conclude that you need a general idea for doing it.

    Possible Solution:

    This would be the canonic approach for a position-based crossover. Genes in the same position in both parents are not moved around, whereas genes occupying different positions are exchanged with one another with a two-step transition:

    1. clone: create child c1 copy of p1 and c2 copy of p2

    2. slice: compute the set of indexes for which c1 and c2 have a different value in the same position

    3. randomize: pick a random idx from this set, and remove it from the set

    4. swap: pick a random index idx in this set: if v1 is in position idx in c1 and v2 is in position idx in c2, swap the values so that v1 is now at position idx in c2 and v2 is in position idx in c1

    5. compensate: find the index idy s.t. v2 is at position idy in p1 and index idz s.t. v1 is at position idz in p2 and compensate the swap operation so that now v1 is at position idy in c1 and v2 is at position idz in c2. Remove both idy and idz from the index set of points 2/3.

    6. reiterate: with probability p, go back to step 3.

    Example:

    // idx = 8, indexes start from 0
|3 2| 9 6 5 8 |4 7| 1 |10| // c1
         /          |
|3 2| 6 1 8 9 |4 7| 5 |10| // c2
=
|3 2| 9 6 1 8 |4 7| 5 |10| // c1
|3 2| 6 5 8 9 |4 7| 1 |10| // c2

    Considerations:

    As you can see, the crossover degenerates into a guided mutation, and this is due to the constraint of not introducing repetitions within your genetic code. However, it is still different from mutation, as the latter would also affect genes that are in the same position for both parents.