Gene Uniqueness - PMX/OX

[theveloped]

First of all, thank you for all the work on this amazing library!

Now using your predefined crossover functions it seems that if one wants to preserve gene uniqueness one could either use PMX or OX. In my case, however, trying to optimize the order of a set of pointers. Now the issue is that a single pointer can have several occurrences in a gnome, like here:

geneA := "A"
geneB := "B"
geneC := "C"
gnome := []*string {&geneA, &geneA, &geneB, &geneC, &geneC, &geneC}

It seems in cases like this the uniqueness of the number of occurrences is not preserved between crossovers. Is this the intended behavior, as the gnome is not comprised out of unique genes?

[MaxHalford]

Hey, thanks buddy.

I'm not sure I understand. Did you start with a genome with unique values, use PMX/OX, and end up with a genome of non unique values? If so the implementations are wrong and I'll have to correct them.

[theveloped]

Indeed I end up with a genome that has a different set of genes than the parents. The fact is however that the genomes don't have all unique values. The idea is that I want all the genomes to have a certain amount of specific genes (e.g. 2 x geneA, 1 x geneB and 3 x geneC). All the following genomes are in this valid in this example:

gnome1 := []*string {&geneA, &geneA, &geneB, &geneC, &geneC, &geneC}
gnome2 := []*string {&geneA, &geneB, &geneA, &geneC, &geneC, &geneC}
gnome3 := []*string {&geneB, &geneA, &geneC, &geneB, &geneC, &geneC}
etc.

After the crosover using PMX/OX I however get genomes with different number of occurences (e.g. 5 x geneA, 1 x geneB and 1 x geneC).

[theveloped]

An implementation of OX as shown below yields the expected result for the case described above. In my case the evaluate function is extremely slow so the performance is of no concern. It seems the performance overhead is however minimal with regard to the original code.

type occurence map[interface{}]int

func ox(p1, p2 eaopt.Slice, a, b int) {
  var (
    n  = p1.Len()
    o1 = p1.Copy()
    o2 = p2.Copy()
  )

  // Create lookup maps to quickly see if a gene has been copied from a parent or not the correct amount of times
  var p1Occurences, p2Occurences = make(occurence), make(occurence)
  for i := b; i < b+n; i++ {
    var k = i % n
    p1Occurences[p1.At(k)]++
    p2Occurences[p2.At(k)]++
  }

  // Keep two indicators to know where to fill the offsprings
  var j1, j2 = b, b
  for i := b; i < b+n; i++ {
    var k = i % n
    if p1Occurences[p2.At(k)] > 0 {
      p1Occurences[p2.At(k)]--
      o1.Set(j1%n, p2.At(k))
      j1++
    }
    if p2Occurences[p1.At(k)] > 0 {
      p2Occurences[p1.At(k)]--
      o2.Set(j2%n, p1.At(k))
      j2++
    }
  }
  p1.Replace(o1)
  p2.Replace(o2)
}

Do you agree this indeed results in the expected behaviour? If so I believe the same approach can be taken for PMX.

[MaxHalford]

PMX and OX were not designed to handle specific amounts of values, only unique values. It's an interesting use case and I'll to think about it. If you find a good implementation please tell me and we work on adding it to eaopt.

[theveloped]

That was indeed what I was afraid of. I believe the code above should work in both cases (unique values or a specific amount of values). A gnome with a specific amount of values is something that is heavily used in packing or nesting algorithms (e.g. fitting as many shapes as possible in a given space).

[MaxHalford]

Okay but are you sure this is still OX? If the algorithm is different then maybe it is listed here? I don't mind adding the algorithm to eaopt but I want to make sure it works and if it already exists. A pull request with some unit tests would be welcome.

[theveloped]

Indeed I believe this is the correct way to perform OX although the theory is rather limited for the case with repeating values. Your current implementation now performs the following steps in case of the repeated values:

parents:
p1 = [a, a, b, b, b, b, c, c]
p2 = [a, b, c, c, b, b, b, a]

1. copy p1 to o1 (offspring 1) and p2 to o2
   o1 = [a, a, b, b, b, b, c, c]
   o2 = [a, b, c, c, b, b, b, a]
2. replace positions 4 until 1 with value in p2 if not already used:
   o1 = [a, a, b, b, b, b, c, c], (o1[4] not changed because p2[4]=b was allready used)
   o1 = [a, a, b, b, b, b, c, c], (o1[5] not changed because p2[5]=b was allready used)
   o1 = [a, a, b, b, b, b, c, c], (o1[6] not changed because p2[6]=b was allready used)
   o1 = [a, a, b, b, b, b, c, a], (o1[7] is set to p2[7]=a because this is not used yet)
   o1 = [a, a, b, b, b, b, c, a], (o1[1] not changed because p2[1]=a was allready used)
3. repeat step to for for the second offspring
   o2 = [a, b, c, c, b, b, b, a], (o2[4] not changed because p1[4]=b was allready used)
   o2 = [a, b, c, c, b, b, b, a], (o2[5] not changed because p1[5]=b was allready used)
   o2 = [a, b, c, c, b, b, b, a], (o2[6] not changed because p1[6]=c was allready used)
   o2 = [a, b, c, c, b, b, b, a], (o2[7] not changed because p1[7]=c was allready used)
   o2 = [a, b, c, c, b, b, b, a], (o2[1] is set to p1[1]=a because this is not used yet)

I believe in this case the current implementation, therefore, returns unlogical offspring. The code I posted seems to be a more generic version of OX that is also applicable to this situation. The original unittests should therefore also still pass. I will try to make a pull request over the weekend if I have time.

[MaxHalford]

Okay I'll wait for the pull request, thanks for taking the time to explain :)

[MaxHalford]

Fixed in pull/32 for OX. A generic version of PMX still has to be implemented.