Sign in to follow this  
mister_bluesman

Crossover problem

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 this post


Link to post
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[i] = 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[i] == 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[i] == strSize+1)
{
offspring[i] = parent2[i];
}
}

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[i] = 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[i] = parent1[i];
}
}

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[i] = strSize+1;
}

// First pass: copying the crossover subsequence
for (i = 0; i < strSize; i++)
{
if (i >= cross1 && i < cross2) // Inside the cross area
{
offspring[i] = parent1[i];
}
}

// 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[i];
while (child->AleleExists(candidate))
{
unsigned int pos = child->FindAlelePos(candidate);
candidate = parent2[pos];
}
offspring[i] = candidate;
}
}
}
};

Share this post


Link to post
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.

link

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

Share this post


Link to post
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this