假设我有一个包含N个自然数的集合S，以及这个集合的N个子集（S1, S2, …Sn）。我想生成两个子集D1和D2（D1 + D2 = S，D1和D2没有共同元素），使得D1和D2不包含任何这N个子集中的任何一个。

快速示例：

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

我的第一个想法是，粒子的位置将描述元素的选择方式（假设位置是一个包含N个BYTE元素的数组，如果position[i]是1，则Set[i]在D1中，如果是2，则在D2中，为了简单起见）。

一个解的适应度可以是N减去解中包含的初始子集的数量。

但是速度应该是什么呢？我无法想出这一部分，这让我觉得可能需要以另一种方式来表示位置，但同样，我找不到一种不会使情况变得过于复杂的方法。

我更感兴趣的是理论上的回答。我应该如何表示数据，以及为什么这样做。

我对PSO还是新手，所以关于这个主题的任何入门级的好读物都将不胜感激。

回答：

正如amit所建议的，这实际上是一个NP难问题。给定一个CNF公式，让S与所有文字（正负）的集合一一对应，再加上一个额外的T和F对。创建一个{T, F}集合。对于每个变量，创建一个包含该变量的正负文字的两个元素集合，使得一个与T共享一个集合，另一个与F共享一个集合。对于每个析取的子句，创建一个包含其文字和F的集合。通过将所有与T共享集合的文字赋值为真，CNF-SAT实例和这个问题的实例的解是一一对应的。

如果你想解决这个问题，我建议使用SAT求解器，因为用CNF表达它并不难。如果你想学习粒子群优化，我建议选择一个具有连续解空间的不同问题。