• 9
• 10
• 10
• 11
• 17

# Crossover problem

This topic is 4418 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I havea chromosome representing activities within ceratin time slots. so: chr1: 1, 2, 3, 3, 2 chr2: 2, 3, 3, 2, 1 means that in chr1, activity 1 is in timeslot 1, activity 2 is in time slots 2 and 5, and activity 3 is in time slots 3 and 4. Now, if trying to crossover, say at point 2, I end up with more activities appearing on one chromosome and fewer in another child 1: 1, 2, 3, 2, 1 - an extra '1' activity has been created child 2: 2, 3, 3, 3, 2 - an extra '3' activity has been created and '1' removed I tried to overcome this problem by chaging the repesentation into times. so for activities 1, 2, 2, 3, 3 chr1 = 1, 2, 5, 3, 4 chr2 = 5, 1, 4, 2, 3 However, say i was to crossover at point 2 again, I would have more than one activity occuring at one time (which for my application is NOT allowed) child 1: 1, 2, 4, 2, 3 child 2: 5, 1, 5, 3, 4 So above, 2 activities are scheduled for timeslot 2 and timeslot 5. How do i get round this so i can crossover in a valid fashion? Thanks

##### Share on other sites
Your problem is similar to the problem of crossover in the TSP problem, where the cities are the genes.

There are many ways to do it, here are some with their code as I implemented them; you can find more information about them in a simple google search. They all worked for me, I don't really remember which was the best though - just play with them:

1. Cyclic crossover -

class CyclicCrossover : public CrossoverOperator{public:    virtual void Crossover()    {        bool verbose = false;        unsigned int strSize = m_parent1->GetSize();        // Just for initialization -         m_child1->CloneFrom(m_parent1);        m_child2->CloneFrom(m_parent2);        // Getting the string to work on        Genome::GenomeString &parent1 = m_parent1->GetGenotype();        Genome::GenomeString &parent2 = m_parent2->GetGenotype();        if (verbose)        {            cout << "Parent 1 - " << m_parent1->ToString() << endl;            cout << "Parent 2 - " << m_parent2->ToString() << endl;        }        // Filling the two offspring. Notice the swap in parents to make two        // different offsprings.        if (verbose)         {            cout << "Filling offspring #1" << endl;            cout << "--------------------" << endl;        }        FillOffspring(m_child1, parent1, parent2, verbose);        if (verbose)         {            cout << "Filling offspring #2" << endl;            cout << "--------------------" << endl;        }        FillOffspring(m_child2, parent2, parent1, verbose);    }    void FillOffspring(Genome *child,         Genome::GenomeString &parent1, Genome::GenomeString &parent2,         bool verbose)    {        unsigned int i;        unsigned int strSize = child->GetSize();        Genome::GenomeString &offspring = child->GetGenotype();        // Initializing the offspring to "null"        for (i = 0; i < strSize; i++)        {            offspring  = strSize+1;        }        if (verbose) cout << "Offspring after initialization: " << child->ToString() << endl;        // Step 1: Using the first parent until a cycle is reached.        if (verbose) cout << "Step 1" << endl;        unsigned int position = 0;        unsigned int filledPositions = 0;         bool cycle = false;        while (!child->AleleExists(parent1[position]) && filledPositions < strSize)        {            offspring[position] = parent1[position];            filledPositions++;            // The next position is the position of the alele in parent2[position]            // in the first parent.            for (i = 0; i < strSize; i++)            {                if (parent1 == parent2[position])                {                    break;                }            }            position = i;            if (verbose) cout << "Offspring after round: " << child->ToString() << endl;        }        // Step 2: Filling the missing ones from the second parent        for (i = 0; i < strSize; i++)        {            if (offspring == strSize+1)            {                offspring = parent2;            }        }        if (verbose) cout << "Offspring after second step: " << child->ToString() << endl;    }};

2. Ordered crossover -

/// The ordered crossover keeps the relative order of the aleles from the /// parents in their offsprings.class OrderedCrossover : public CrossoverOperator{public:    virtual void Crossover()    {        bool verbose = false;        unsigned int cross1, cross2;        unsigned int strSize = m_parent1->GetSize();        // Just for initialization -         m_child1->CloneFrom(m_parent1);        m_child2->CloneFrom(m_parent2);        // Choosing two random different positions for cross points        do         {            cross1 = 1+(rand()%(strSize-1));            cross2 = 1+(rand()%(strSize-1));        } while (cross1 == cross2);        // Making sure cross1 is smaller        if (cross1 > cross2) swap(cross1, cross2);        // Getting the string to work on        Genome::GenomeString &parent1 = m_parent1->GetGenotype();        Genome::GenomeString &parent2 = m_parent2->GetGenotype();            if (verbose)        {            cout << "Parent 1 - " << m_parent1->ToString() << endl;            cout << "Parent 2 - " << m_parent2->ToString() << endl;            cout << "Cross: " << cross1 << " - " << cross2 << endl;        }        // Filling the two offspring. Notice the swap in parents to make two        // different offsprings.        if (verbose)         {            cout << "Filling offspring #1" << endl;            cout << "--------------------" << endl;        }        FillOffspring(m_child1, parent1, parent2, cross1, cross2, verbose);        if (verbose)         {            cout << "Filling offspring #2" << endl;            cout << "--------------------" << endl;        }        FillOffspring(m_child2, parent2, parent1, cross1, cross2, verbose);    }    void FillOffspring(Genome *child,         Genome::GenomeString &parent1, Genome::GenomeString &parent2,         unsigned int cross1, unsigned int cross2, bool verbose)    {        unsigned int i;        unsigned int strSize = child->GetSize();        Genome::GenomeString &offspring = child->GetGenotype();        // Initializing the offspring to "null"        for (i = 0; i < strSize; i++)        {            offspring  = strSize+1;        }        if (verbose)        {            cout << "Offspring after initialization: " << child->ToString() << endl;        }        // First pass: copying the crossover subsequence        for (i = 0; i < strSize; i++)        {            if (i >= cross1 && i < cross2) // Inside the cross area            {                offspring = parent1;            }        }        if (verbose) cout << "Offspring after subsequence: " << child->ToString() << endl;        // Second pass: copying the rest        unsigned int posInParent2 = 0;         unsigned int posInOffspring = 0;        while (posInOffspring < strSize)        {            // Jumping over the copied subsequence            if (posInOffspring == cross1)             {                posInOffspring = cross2;            }            if (verbose)            {                cout << "Offspring position now - " << posInOffspring << ", parent position now - " << posInParent2 << endl;            }            // Finding a non-existant alele            unsigned int candidate = parent2[posInParent2];            if (verbose) cout << "Checking candidate " << candidate;            while (child->AleleExists(candidate))            {                if (verbose) cout << "... Found!" << endl;                posInParent2++;                candidate = parent2[posInParent2];                if (verbose) cout << "Checking candidate " << candidate;            }            if (verbose) cout << "... Not found!" << endl;            // Copying            offspring[posInOffspring] = candidate;            if (verbose) cout << "Offspring after step: " << child->ToString() << endl;            posInOffspring++;        }    }};

3. Partially matched crossover - Also known as PMX -

class PartiallyMatchedCrossover : public CrossoverOperator{public:    virtual void Crossover()    {        unsigned int cross1, cross2;        unsigned int strSize = m_parent1->GetSize();        // Just for initialization -         m_child1->CloneFrom(m_parent1);        m_child2->CloneFrom(m_parent2);        // Choosing two random different positions for cross points        do         {            cross1 = 1+(rand()%(strSize-1));            cross2 = 1+(rand()%(strSize-1));        } while (cross1 == cross2);        // Making sure cross1 is smaller        if (cross1 > cross2) swap(cross1, cross2);        // Getting the string to work on        Genome::GenomeString &parent1 = m_parent1->GetGenotype();        Genome::GenomeString &parent2 = m_parent2->GetGenotype();        // Filling the two offspring. Notice the swap in parents to make two        // different offsprings.        FillOffspring(m_child1, parent1, parent2, cross1, cross2);        FillOffspring(m_child2, parent2, parent1, cross1, cross2);    }    void FillOffspring(Genome *child,                        Genome::GenomeString &parent1, Genome::GenomeString &parent2,                        unsigned int cross1, unsigned int cross2)    {        unsigned int i;        unsigned int strSize = child->GetSize();        Genome::GenomeString &offspring = child->GetGenotype();        // Initializing the offspring to "null"        for (i = 0; i < strSize; i++)        {            offspring  = strSize+1;        }        // First pass: copying the crossover subsequence        for (i = 0; i < strSize; i++)        {            if (i >= cross1 && i < cross2) // Inside the cross area            {                offspring = parent1;            }        }        // Second pass: copying the rest        for (i = 0; i < strSize; i++)        {            if (i < cross1 || i >= cross2) // Outside the cross area            {                 // Finding a candidate for putting in the offspring.                unsigned int candidate = parent2;                while (child->AleleExists(candidate))                {                    unsigned int pos = child->FindAlelePos(candidate);                    candidate = parent2[pos];                }                offspring = candidate;            }        }    }};

##### Share on other sites
Thank you. I shall look into those straight away.

##### Share on other sites
So, would you say that there is little difference in performance between them?

Cheers

##### Share on other sites
You may want to read this paper. It covers several methods for crossover on permutations.
I like Gil Syswerda's permutation crossover (which is presented in this paper).
The pdf link seems to not work, but the ps is fine.

I honestly don't know if the methods DadleFish posted are in here or not, but I hope it helps.

##### Share on other sites
If you just want an easy to impliment solution to what I believe to be the requirement, then there is a relatively easy "fix."

If it is the case that you need activity #1 appearing only once, activities #2 and #3 both appearing twice and that the goal is to evolve new orders for these activities.

Suppose a member was defined as 5 floating point values, ABCDE.

A represents the RANK of activity #1
B and C represent the RANKS of activity #2
D and E represent the RANKS of activity #3

A rule is applied that there are no duplicate floating point values in a member of the population. Duplicates are squashed by randomly incrementing or decrementing one of the offending duplicates by a very small value.

Now when you need to decide on activity you SORT the list ABCDE

so it might turn out CEBAD -> perform C, then E, then B, then A, then D

Just a suggestion. I've encountered this sort of thing before and its very easy to impliment.