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?


1 Answer 1


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:

  • $\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$
    – Coder Guy
    Commented Dec 27, 2018 at 13:27
  • $\begingroup$ I see - I have updated the answer to take into account this clarification. $\endgroup$
    – cantordust
    Commented Dec 27, 2018 at 13:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .