Let's say I have a set S of N natural numbers and N subsets (S1, S2, ...Sn) of that set. I want to generate 2 subsets D1 and D2 ( D1 + D2 = S, D1 and D2 have no common elements ) so that D1 and D2 does not contain any of those N subsets.
Quick example:
S = 1 2 3 4 5
S1 = 1 4
S2 = 1 2
S3 = 1 2 3
S4 = 1 2 3 4
S5 = 1 2 4
D1 = 1 3 5
D2 = 2 4
My first thought is that the position occupied by a particle will describe the way the elements are chosen (let's say position is an array with N BYTE elements, if position[i] is 1, Set[i] is in D1, 2 in D2, to make it simple).
The fitness of a solution could be N - the number of initial subsets that are included in the solution.
But what will be the velocity? The fact that I can't figure out this part makes me think that maybe I need to represent the position in another way, but again, I can't find something that will over-complicate the situation.
I'm more interested in theoretical answers. What way should I represent the data and why.
I'm new to this PSO thing so any good reads (beginner level) on the subject are appreciated.
As amit suggested might be the case, this is in fact an NP-hard problem. Given a CNF formula, let S be in one-to-one correspondence with the set of all literals (positive and negative) plus one extra pair T and F. Make a set {T, F}. Make one two-element set per variable containing the positive and negative literal for that variable, so that one shares a set with T, and the other, with F. For each clause of the disjunction, make a set with its literals and F. The solutions to the CNF-SAT instance and the instance of this problem are in one-to-one correspondence, by assigning true to all literals sharing the set with T.
If you want to solve this problem, I would suggest a SAT solver, since it's not hard to express it in CNF. If you want to learn about particle swarm optimization, I would suggest a different problem, with a continuous solution space.