CODEWITHSUNDEEP
algorithmknapsack-problemcrossover
meraxes
meraxes

Reputation: 541

Genetic Algorithm: Crossover for 0-1 Knapsack

I'm following the genetic algorithm approach to solving the Knapsack problem as seen here. I understand that they used a direct value encoding scheme rather than a binary representation. The crossover function is as follows:

def cxSet(ind1, ind2):
"""Apply a crossover operation on input sets. The first child is the
intersection of the two sets, the second child is the difference of the
two sets.
"""
temp = set(ind1)                # Used in order to keep type
ind1 &= ind2                    # Intersection (inplace)
ind2 ^= temp                    # Symmetric Difference (inplace)
return ind1, ind2

If I were to encode the chromosomes of the Knapsack problem as binary representations, inersection would be an AND operation. What would be the analgous operation for set difference?

Also, I was just wondering what the rationale behind this type of crossover might be, and if there are advantages of this type of crossover over other usual crossover techniques like single point crossover or two-point crossover.

Upvotes: 1

Views: 508

Answers (1)

maraca
maraca

Reputation: 8773

The easiest way to solve such things is to make a small example:

s1 = {1, 2, 3, 4} => 11110000
s2 = {3, 4, 5, 6} => 00111100
s1 intersect s2 = {3, 4} => 00110000
s1 difference s2 = {1, 2, 5, 6} => 11001100

Looking at this we come up with the following bitwise operators:

  1. intersect: s1 AND s2 (usually &)

  2. difference: s1 XOR s2 (usually ^)

Upvotes: 1

Related Questions