3
$\begingroup$

Each chromosome contains an array of genes, each gene contains a letter and a number, both letter and number can only exist once in each chromosome.

Parent A = {a,1}{c,2}{e,3}{g,4}
Parent B = {a,2}{b,1}{c,4}{d,3}

What would be the best crossover operator to create a child that doesn't break the rule described above?

$\endgroup$
1
$\begingroup$

First, store the two parent chromosomes into a sorted dictionary (in terms of implementation, std::map in C++ might be a good option) where the key is the letter and the value is a pair of ints (the second gene element). When you populate the map, add all the letters from each chromosome as keys and take 0 (or a negative number) to indicate that a gene with the corresponding letter does not exist in one of the parents.

Next, create a second map, this time with the number as a key. Iterate over the first map. If both parent chromosomes contain a gene with the same letter, the value field in the map would contain two positive numbers - pick one at random and insert the {number, letter} combination into the second map only if the number doesn't exist as a key. If the gene exists only in one parent, either pick the gene as is or choose to skip that gene altogether.

This would guarantee that 1) your genomes contain a {letter, number} gene only once and 2) the genes in the offspring's chromosomes would be automatically sorted by letter. If you don't need the genes to be sorted but still need them to be unique, you can use an unordered map (a hash table).

In your example, the map would look like this:

Mapped parent chromosomes
{a: (1,2)}
{b: (0,1)}
{c: (2,4)}
{d: (0,3)}
{e: (3,0)}
{g: (4,0)}

Offspring chromosome (OC)
{}

Where 0 indicates that the corresponding gene does not exist in that parent. Iterating over this table from top to bottom, you might end up doing the following:

  1. Key a: pick 1; 1 is not a key in OC, so insert {1,a}
  2. Key b: pick 1; 1 is a key in OC, so skip letter b
  3. Key c: pick 4; 4 is not a key in OC, so insert {4,c}
  4. Key d: choose to skip
  5. Key e: pick 3; 3 is not a key in OC, so insert {3,e}
  6. Key g: pick 4; 4 is a key in OC, so skip letter g

Final offspring chromosome:

{a,1}{c,4}{e,3} 
$\endgroup$
  • $\begingroup$ Thanks for the reply I really appreciate it. However, the offspring you created is invalid because the number 4 exists twice in the offspring and that would be invalid in my solution. $\endgroup$ – Awesome Guy Dec 27 '18 at 13:27
  • $\begingroup$ I see - I have updated the answer to take into account this clarification. $\endgroup$ – cantordust Dec 27 '18 at 13:51
0
$\begingroup$

Considering the definition of operator $\mathcal{O}$ such that child

$$C := \mathcal{O} \, (A, B) \, \text{,}$$

there are a few assumptions to enumerate so that the problem is not ambiguous.

  • Chromosomes $A, B, C$ each contain the same number of genes.
  • Selection must have a constant probability distribution across the permutations that conform to the rule given.

Given $\mathcal{O}$ defined in this way, this is one conformant algorithmic expression.

    s = A.size
    if s != B.size
        return nil
    random_real.seed get_time
    L = stack A
    L.add B
    C = new list
    c0 = new hash_set
    c1 = new hash_set
    while s > 0
        i = floor (s * random_real.get % s)
        candidate = L.front_pop
        if c0.has candidate[0]
            continue
        if c1.has candidate[1]
            continue
        C.add candidate
        if L.empty
            break
        c0.add candidate[0]
        c1.add candidate[1]
        s --
    return C

The better way is to create a generic (template) multidimensional hash and a multidimensional hashset that uses it. Then the template can be instantiated with a comparator that expresses the predicate (Boolean expression) for the insertion rule. This simplifies the body of the loop to something that can be expressed using functional notation and allows the optimization of the multidimensional lookup to test preexistence of either coordinate.

The random sourcerandom_realin $\mathbb{R}$ can be replaced with an integer one instantiated with a min and max value, which could potentially be much faster.

With operator override as a language feature, the appropriate function could be defined to allow spawning as a base operation of the chromosome class allowing reproduction to be represented thusly.

$$ C := A * B $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.