0

I'm doing an exercise from here(note: not schoolwork!) It's only my second attempt at a GA, and having issues with the following problem:

How to "reproduce" as in, how do I combine my offspring.

I have a randomly generated population, of which I know the individual fitness(which is a summed distance of the target values).

However, i can't randomly go switching cards between 2 "parents" because which cards can be used is regulated(every card only once for each element in the population).

I hope to get some good feedback from you guys. I can supply additional info if required.

2 Answers 2

1

The problem is that every card can be used just once and you have to divide them into two piles, so lets make the problem a bit easier and just use numbers 1-10.

For example take these two solutions:

Parent 1: 1 2 5 7 8 - 3 4 6 9 10 Parent 2: 1 4 5 6 9 - 2 3 7 8 10 

In this case, we can't just split them and combine, you'll end up with duplicate numbers. So how do we create healthy children from this? One approach I usually see is to take one of the solutions as 'main' parent.

For example Parent 1, and we take half of the parent:

Child 1: 1 * 5 * 8 - * 4 * 9 * Child 2: * 2 * 7 * - 3 * 6 * 10 

Next we take our second parent and use it to fill the missing blanks:

Parent 2: 1 4 5 6 9 - 2 3 7 8 10 Child 1: 1 * 5 * 8 - * 4 * 9 * First we filter out the ones used in child 1: 6 - 2 3 7 10 Next we try to fill the blanks as good as possible: 1 5 6 8 * - 2 3 4 7 9 Now assign the leftovers (they jump side). The resulting children will be: Child 1: 1 5 6 8 10 - 2 3 4 7 9 Child 2: 1 2 4 5 7 - 3 6 8 9 10 

There are some problems with this idea, namely that for example the 10 in child 1 has jumped sides, and both parents had them in the second pile. This can be countered by first fixating numbers that are the same in both piles.

Just be creative, you'll find a method that works best for your situation.

Sign up to request clarification or add additional context in comments.

2 Comments

thanks for the insight. I have upvoted it, and will try this implementation. I might mark it as the answer as wel
seeing as I used a (slightly adapted) way of your explication, I'm marking you as having answered it.
1

You can avoid duplicated numbers on offspring chromosomes, as mentioned by @roy-van-rijn, using some crossover operations from TSP (Travelling Salesman Problem). In TSP, children chromosomes cannot duplicate cities too.

Some classic ordered crossover operators:

To keep your cromosomes ordered after mutation, you will need ordered mutation operators too:

1 Comment

Just to add to this, Wikipedia has section on crossover for "ordered chromosomes" - en.wikipedia.org/wiki/…

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.