4

问题
您认为遗传算法是否值得尝试解决以下问题，或者我会遇到局部最小值问题吗？

我认为问题的某些方面对于生成器/健身功能样式设置来说可能很棒。（如果你搞砸了一个类似的项目，我很乐意收到你的来信，而不是做类似的事情）

感谢您提供有关如何构建事物并正确解决此问题的任何提示。


我正在寻找一个很好的调度算法来解决以下现实世界的问题。

我有一个这样的 15 个插槽的序列（数字可能从 0 到 20 不等）：

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

（并且这种类型总共有 10 种不同的序列）

每个序列都需要扩展成一个数组，其中每个插槽可以占据 1 个位置。

1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 
1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 
0 0 1 1 0 0 0 1 1 1 0 0 0 1 1
0 0 1 1 0 0 0 1 1 1 0 0 0 1 1

矩阵的约束是：

  • [row-wise, ie Horizo​​ntal] 放置的个数，必须是 11 或 111
  • [row-wise] 1的两个序列之间的距离需要最小为00
  • 每列的总和应与原始数组匹配。
  • 应该优化矩阵中的行数。

然后数组需要分配 4 个不同的矩阵之一，这些矩阵可能有不同的行数：

A, B, C, D

A、B、C 和 D 是现实世界的部门。负载需要在 10 天期间合理公平地放置，以免干扰其他部门的目标。

每个矩阵都与 10 个不同原始序列的扩展进行比较，因此您有：

A1, A2, A3, A4, A5, A6, A7, A8, A9, A10
B1, B2, B3, B4, B5, B6, B7, B8, B9, B10
C1, C2, C3, C4, C5, C6, C7, C8, C9, C10
D1, D2, D3, D4, D5, D6, D7, D8, D9, D10

可能会保留这些位置上的某些位置（不确定我是否应该将其仅保留/不保留或基于功能）。 预留的位置可能是会议和其他活动

每行的总和（例如所有 A）应在 2% 内大致相同。即 sum(A1 到 A10) 应该与 (B1 到 B10) 等大致相同。

行数可能会有所不同，因此例如：

A1：5 行 A2：5 行 A3：1 行，其中单行可以是：

0 0 1 1 1 0 0 0 0 0 0 0 0 0 0

ETC..

子问题*

我很乐意只解决部分问题。例如能够输入：

1 1 2 3 4 2 2 3 4 2 2 3 3 2 3

并获得一个适当的序列数组，其中 1 和 0 在上述约束之后的行数上最小化。

4

2 回答 2

2

子问题解决尝试

嗯，这是一个想法。该解决方案不是基于使用遗传算法，但可以使用一些想法朝那个方向发展。

基向量

首先，您应该生成我认为的基向量。例如，如果您的序列是 3 个数字而不是 15 个，则基向量将是：

v1 = [1 1 0]

v2 = [0 1 1]

v3 = [1 1 1]

序列长度为 3 的任何解决方案都是这三个向量的线性组合，仅使用正整数。换句话说，一般的解决方案是

a*v1 + b*v2 + c*v3

其中 a、b 和 c 是正整数。对于序列 [1 2 1]，解是 v1 = 1, v2 = 1, v3 = 0。首先要做的是找到所有可能的长度为 15 的基向量。根据我的粗略计算，我认为有介于 300-400 个长度为 15 的基向量之间。如果你愿意，我可以给你一些生成它们的技巧。

寻找解决方案

现在，您要做的是按它们的总和/大小对这些基向量进行排序。然后在寻找解决方案时，从总和最大的基向量开始。我们从总和最大的向量开始，因为它们导致总行数减少。我们还有一个数组 veccoefs，其中包含每个基向量的线性系数条目。在开始寻找解的时候，所有的 veccoefs 都是 0。

所以我们取第一个基向量（总和/幅度最大的那个）并从序列中减去这个向量，直到我们创建一个无法解决的结果（例如其中包含 0 1 0）或结果中的任何数字是负数。我们将减去向量的次数存储在 veccoefs 中。我们使用从序列中减去基向量后的结果作为下一个基向量的序列。如果结果中只剩下零，那么我们停止循环。

我不确定这种方法的效率/准确性，但它至少可以给你一些想法。

其他可能的解决方案

解决这个问题的另一个想法是使用基向量并将问题形成为优化/最小二乘问题。您形成一个基向量矩阵，这样基本问题将最小化 Sum[(Ax - b)^2] 其中 A 是基向量矩阵，b 是输入序列，x 是基向量系数。但是，您还希望最小化行数，因此您可以将 x^T*x 之类的项添加到最小化函数中，其中 x^T 是 x 的转置。在我看来，困难的部分是找到可微分项来添加，这将鼓励整数向量系数。如果您能想到一种方法来做到这一点，那么优化很可能是做到这一点的好方法。

此外，您可能会考虑使用 Metropolis 类型的 Monte Carlo 解决方案。您将随机选择是在每一步添加一个向量、删除一个向量还是替换一个向量。将随机选择要添加/删除/替换的向量。此更改被接受的概率将是更改之前和更改之后解决方案的适用性的比率。适合性可以等于当前解决方案与序列之间的差，平方和相加，减去解决方案中涉及的行/基向量的数量。您需要为各种术语输入适当的常量，以尝试使接受率达到 50% 左右。我有点怀疑这是否会很好地工作，但我认为在寻找可能的解决方案时仍然应该考虑它。

于 2010-02-15T08:12:13.010 回答
1

GA 可以应用于这个问题，但它不会是 5 分钟的任务。你需要把几个东西放在一起，而不知道每个东西的哪个实现是最好的。
所以：

  1. 解决方案表示 - 您将如何表示可能的解决方案？使用矩阵似乎是最直接的。也可以使用一维数组的集合。但是你有一些限制，所以也许 SuperGene 的概念值得考虑？
  2. 对于给定的基因表示，您必须使用适当的突变/交叉运算符。
  3. 您将如何对解决方案实施约束？破坏那些不合适的？如果它们包含有价值的信息怎么办？也许让它们留在种群中但对适应度增加一些惩罚，因此它们会为后代做出贡献，但不会进入下一代？

无论如何，我认为GA可以应用于这个问题。这值得吗？通常 GA 不是最好的算法，但如果其他算法失败，它们是不错的算法。我会选择 GA，只是因为它会最有趣，但我会寻找替代解决方案（以防万一）。

PS个人见解：我正在解决N皇后问题，70 < N < 100（板NxN，N皇后）。算法对于较低的 N 运行良好（也许它正在尝试所有组合？），但是 N 在这个范围内，我找不到合适的解决方案。健康度迅速跃升至最大值的 90% 左右，但最终总是有两个皇后发生冲突。但这是非常幼稚的实现。

于 2010-02-09T10:38:30.860 回答