AI - PSO - 选择正确的表示
AI - PSO - Choosing the right representations
假设我有一个包含 N 个自然数的集合 S 和该集合的 N 个子集（S1、S2、...Sn）。我想生成 2 个子集 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
我的第一个想法是，粒子占据的位置将描述元素的选择方式（假设position是一个包含N BYTE元素的数组，如果position[i]为1，Set[i]在D1，D2中的2，为了简单起见）。
解决方案的适应度可以是 N - 解决方案中包含的初始子集的数量。
但是速度是多少？我无法弄清楚这部分的事实让我觉得也许我需要用另一种方式来表示这个位置，但同样，我找不到会使情况过于复杂的东西。
我对理论上的答案更感兴趣。我应该用什么方式表示数据以及为什么。
我是这个 PSO 的新手，所以任何关于这个主题的好读物（初学者水平）都将受到赞赏。
正如 amit 所建议的那样，这实际上是一个 NP-hard 问题。给定一个 CNF 公式，让 S 与所有文字（正和负）的集合加上一对额外的 T 和 F 一一对应。做一个集合 {T, F}。为每个变量创建一个双元素集合，其中包含该变量的正负文字，以便一个与 T 共享一个集合，另一个与 F 共享一个集合。对于析取的每个子句，创建一个包含其文字和 F 的集合。 CNF-SAT 实例的解和这个问题的实例是一一对应的，通过将所有与 T 共享集合的文字赋值为 true。
如果你想解决这个问题，我建议使用 SAT 求解器，因为用 CNF 表达它并不难。如果你想了解粒子群优化，我会建议一个不同的问题，有一个连续的解决方案 space。
假设我有一个包含 N 个自然数的集合 S 和该集合的 N 个子集（S1、S2、...Sn）。我想生成 2 个子集 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
我的第一个想法是，粒子占据的位置将描述元素的选择方式（假设position是一个包含N BYTE元素的数组，如果position[i]为1，Set[i]在D1，D2中的2，为了简单起见）。
解决方案的适应度可以是 N - 解决方案中包含的初始子集的数量。
但是速度是多少？我无法弄清楚这部分的事实让我觉得也许我需要用另一种方式来表示这个位置，但同样，我找不到会使情况过于复杂的东西。
我对理论上的答案更感兴趣。我应该用什么方式表示数据以及为什么。
我是这个 PSO 的新手，所以任何关于这个主题的好读物（初学者水平）都将受到赞赏。
正如 amit 所建议的那样，这实际上是一个 NP-hard 问题。给定一个 CNF 公式，让 S 与所有文字（正和负）的集合加上一对额外的 T 和 F 一一对应。做一个集合 {T, F}。为每个变量创建一个双元素集合，其中包含该变量的正负文字，以便一个与 T 共享一个集合，另一个与 F 共享一个集合。对于析取的每个子句，创建一个包含其文字和 F 的集合。 CNF-SAT 实例的解和这个问题的实例是一一对应的，通过将所有与 T 共享集合的文字赋值为 true。
如果你想解决这个问题，我建议使用 SAT 求解器，因为用 CNF 表达它并不难。如果你想了解粒子群优化，我会建议一个不同的问题，有一个连续的解决方案 space。