4
$\begingroup$

I got an amount of numbers, they are shuffled and represent the individuals. For example (3,1,3,2,5,22,5) is one individual or (22,3,1,3,5,5,2).

Mutation is done quite easy by permutation within an individual.

The problem is to find a crossover method between 2 individuals, in which the quantity of the values stay the same(for the above example 2 times 3, 2 times 5, 1 time 22 and so on).
I searched a lot on it but only found crossover methods for either unordered / ordered lists. Those for ordered lists seemed promising but they require that every value only occur ones.

Do you know a method to solve this problem or got an idea for altering an crossover for ordered list method like PMX?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
1
$\begingroup$

You can choose a random threshold $t \leq n$ such that the first $t$ of the first individual is taken and then you take the rest from the other individual, so in your case, if $t = 4$, your new individual is $(3,1,3,2,22,5,5)$. As Richerby clarifies below, you take the first $t$ elements from the first individual and put the remaining $n-t$ elements in the order they appear in the second individual.

Making sure that you take the correct number is done by simply counting using a hashmap. Below, correct_count is a map from an element in an individual to the number of times it occurs, ind1 and ind2 are the two individuals you're trying to crossover.

correct_count = {}
for x in ind1:
    correct_count{x} += 1

t = random(n)
new_ind = ind1[0:t]
count = {}
for a in new_ind:
    count{a} += 1
for x in ind2:
    if count{x} != correct_count{x}:
        new_ind.append(x)
        count{x} += 1
Improve this answer
$\endgroup$
2
  • $\begingroup$ So, just to be clear, you're suggesting to take the first $t$ elements from the first individual and put the remaining $n-t$ elements in the order they appear in the second individual? $\endgroup$
    – David Richerby
    Commented Mar 18, 2015 at 10:00
  • $\begingroup$ Yes, precisely. I have used that technique myself (with limited success to be honest) for solving travelling salesman instances. $\endgroup$
    – John Kemeny
    Commented Mar 18, 2015 at 13:03
0
$\begingroup$

I had the same problem as you and it took me a damn while to figure out the answer to this.

You need to look at keeping the same quantity of values as a separate objective (if you only had one objective before this will make it a multi-objective GA).

So if crossover produces a combination that changes one of the value quantities then give it a score of 0 for the keeping stuff the same objective; and if it has the same value quantities then give it a score of 1. You can then score your other objectives as you have been.

As for choosing the actual crossover method, see my other answer here. The crossover methods I talk about at the end are all crossover methods that are specific to ordered chromosomes.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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