genetic-algorithm - 特殊调度算法(模式扩展)

Question

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

我认为这个问题的某些方面对于生成器/适应度函数风格的设置很有用。 (如果你搞砸了一个类似的项目，我很想收到你的来信，而不是做类似的事情)

感谢您提供有关如何构建事物并正确处理的任何提示。

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

我有一个像这样有 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, i.e.水平] 放置的个数，必须是 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

这些上的某些位置可能会被保留(不确定我是否应该只保留/不保留或基于功能)。保留的地点可能是 session 和其他事件

每行的总和(例如所有 A)应该在 2% 以内大致相同。即总和(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

等等..

子问题*

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

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

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

Answer 1

子问题解决尝试

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

基向量

首先，您应该生成我认为的基向量。例如，如果您的序列长度为 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% 左右。我有点怀疑这会很好用，但我认为在寻找可能的解决方案时你仍然应该考虑它。