Genetic algorithms: how to make a crossover in problems of a "subset"?

Question

I have a problem that I am trying to solve using genetic algorithms. The problem is choosing a subset (say 4) of the 100 integers (these integers are just identifiers that represent something else). Ordering doesn't matter; the solution to the problem is SET integers, not an ordered list. I have a good working function, but I have problems with the crossover function.

I want to be able to pair the following two chromosomes:

[1 2 3 4] and [3 4 5 6] into something useful. It is clear that I cannot use the typical crossover function because I can have duplicates in my children that would represent invalid solutions. What is the best crossover method in this case.

Answer 1

Just ignore any element that occurs in both sets (i.e., at their intersection.), I.e. leave these elements unchanged in both sets.

The remaining elements form two disjoint sets to which you can apply almost any random transformation (for example, replacing several pairs in a random way) without duplicates.

This can be seen as the ordering and alignment of both sets, so that the corresponding elements address each other and apply one of the standard crossover algorithms.

Answer 2

It’s sometimes useful to have your solution “go beyond” so that your search converges faster. Instead of making a set of 4 unique integers necessary for your chromosome, make the number of integers (and their uniqueness) part of the fitness function.

Answer 3

I don’t know what you mean by “typical crossover”, but I think you could use a crossover similar to what is often used for permutations:

• take m ints from the first parent (m <n, where n is the number of ints in your sets)
• scan the second one and fill out your subset of it (nm) ints that are free (and not in the subset already).

Thus, you will have n ints from the first and nm int from the second parent without duplication.

Sounds like a valid crossover to me :-).

I think it would be useful not to take any steps on the ordered sets (or use an iterator where the order of the returned elements somehow correlates with the natural ordering of ints), otherwise either a smaller or a larger number would have a higher chance of being in the child, making Your search is biased.

If this is the best method, it depends on the problem you want to solve ...

Answer 4

To combine the sets A and B, you can select the result set S probabilistically so that the probability that x is in S is equal to (the number of sets from A, B containing x) / 2. This will be guaranteed to contain the intersection and be contained in the pool, and the expected capacity is 4.

Answer 5

Since the order doesn’t matter, just collect all the numbers into an array, sort the array, throw out the duplicates (disconnecting them from the linked list or setting them to a negative number or something else). Shuffle the array and take the first 4 numbers.