Genetic algorithms: How to do crossover in “subset

Question

I have a problem which I am trying to solve with genetic algorithms. The problem is selecting some subset (say 4) of 100 integers (these integers are just ids that represent something else). Order does not matter, the solution to the problem is a SET of integers not an ordered list. I have a good fitness function but am having trouble with the crossover function.

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

[1 2 3 4] and [3 4 5 6] into something useful. Clearly I cannot use the typical crossover function because I could end up with duplicates in my children which would represent invalid solutions. What is the best crossover method in this case.

Answer 1

Just ignore any element that occurs in both of the sets (i.e. in their intersection.), that is leave such elements unchanged in both sets.

The rest of the elements form two disjoint sets, to which you can apply pretty much any random transformation (e.g. swapping some pairs randomly) without getting duplicates.

This can be thought of as ordering and aligning both sets so that matching elements face each other and applying one of the standard crossover algorithms.

Answer 2

In order to combine sets A and B, you could choose the resulting set S probabilistically so that the probability that x is in S is (number of sets out of A, B, which contain x) / 2. This will be guaranteed to contain the intersection and be contained in the union, and will have expected cardinality 4.

Answer 3

Sometimes it is beneficial to let your solution go "out of bounds" so that your search will converge more quickly. Rather than making a set of 4 unique integers a requirement for your chromosome, make the number of integers (and their uniqueness) part of the fitness function.

Answer 4

I don't really know what you mean on "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 and fill your subset from it with (n-m) ints that are free (not in the subset already).

This way you will have n ints from the first and n-m ints from the second parent, without duplications.

Sounds like a valid crossover for me :-).

I guess it might be beneficial not to do either steps on ordered sets (or using an iterator where the order of returned elements correlates somehow with the natural ordering of ints), otherwise either smaller or higher numbers will get a higher chance to be in the child making your search biased.

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

Answer 5

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