特殊调度算法（模式扩展）
问题
您认为遗传算法值得尝试解决以下问题吗？或者我会遇到局部最小值问题吗？
我认为这个问题的某些方面对于生成器/健身功能风格的设置来说可能很棒。 （如果您搞砸了一个类似的项目，我很乐意听取您的意见，而不是做类似的事情）
感谢您提供有关如何构建事物并正确解决此问题的任何提示。
问题
我正在寻找一种好的调度算法来解决以下实际问题。
我有一个像这样有 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，即水平] 放置的个数，必须是 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% 以内。即总和（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 的行数最小化，遵循上述约束。
Question
Do you think genetic algorithms worth trying out for the problem below, or will I hit local-minima issues?
I think maybe aspects of the problem is great for a generator / fitness-function style setup. (If you've botched a similar project I would love hear from you, and not do something similar)
Thank you for any tips on how to structure things and nail this right.
The problem
I'm searching a good scheduling algorithm to use for the following real-world problem.
I have a sequence with 15 slots like this (The digits may vary from 0 to 20) :
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
(And there are in total 10 different sequences of this type)
Each sequence needs to expand into an array, where each slot can take 1 position.
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
The constraints on the matrix is that:
- [row-wise, i.e. horizontally] The number of ones placed, must either be 11 or 111
- [row-wise] The distance between two sequences of 1 needs to be a minimum of 00
- The sum of each column should match the original array.
- The number of rows in the matrix should be optimized.
The array then needs to allocate one of 4 different matrixes, which may have different number of rows:
A, B, C, D
A, B, C and D are real-world departments. The load needs to be placed reasonably fair during the course of a 10-day period, not to interfere with other department goals.
Each of the matrix is compared with expansion of 10 different original sequences so you have:
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
Certain spots on these may be reserved (Not sure if I should make it just reserved/not reserved or function-based). The reserved spots might be meetings and other events
The sum of each row (for instance all the A's) should be approximately the same within 2%. i.e. sum(A1 through A10) should be approximately the same as (B1 through B10) etc.
The number of rows can vary, so you have for instance:
A1: 5 rows
A2: 5 rows
A3: 1 row, where that single row could for instance be:
0 0 1 1 1 0 0 0 0 0 0 0 0 0 0
etc..
Sub problem*
I'de be very happy to solve only part of the problem. For instance being able to input:
1 1 2 3 4 2 2 3 4 2 2 3 3 2 3
And get an appropriate array of sequences with 1's and 0's minimized on the number of rows following th constraints above.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
子问题解决方案尝试
嗯，这是一个想法。该解决方案并非基于使用遗传算法，但可以使用一些想法来朝这个方向发展。
基向量
首先，您应该生成我认为的基向量。例如，如果序列长度为 3 个数字而不是 15 个数字，则基向量将为：
序列长度为 3 的任何解都将是仅使用正整数的这三个向量的线性组合。换句话说，通解是
a、b 和 c 为正整数。对于序列 [1 2 1]，解为 v1 = 1，v2 = 1，v3 = 0。您首先要做的是找到长度为 15 的所有可能的基向量。根据我的粗略计算，我认为有长度为 15 的基向量介于 300-400 个之间。如果您愿意，我可以为您提供一些生成它们的提示。
寻找解决方案
现在，您要做的就是按这些基向量的总和/大小对它们进行排序。然后在搜索解决方案时，从总和最大的基向量开始。我们从总和最大的向量开始，因为它们会导致总行数较少。我们还有一个数组 veccoefs，其中包含每个基向量的线性系数的条目。在开始搜索解决方案时，所有 veccoef 均为 0。
因此，我们采用第一个基向量（总和/幅值最大的那个）并从序列中减去该向量，直到我们创建一个无法求解的结果（具有 0例如，其中 1 0）或结果中的任何数字为负数。我们将向量相减的次数存储在 veccoefs 中。我们使用从序列中减去基向量后的结果作为下一个基向量的序列。如果结果中只剩下零，那么我们就停止循环。
我不确定这种方法的效率/准确性，但它至少可以给你一些想法。
其他可能的解决方案
解决此问题的另一个想法是使用基向量并将问题形成优化/最小二乘问题。您形成一个基向量矩阵，这样基本问题就是最小化 Sum[(Ax - b)^2]，其中 A 是基向量矩阵，b 是输入序列，x 是基向量系数。但是，您还希望最小化行数，因此可以将 x^T*x 这样的项添加到最小化函数，其中 x^T 是 x 的转置。我认为最困难的部分是找到可微分项来添加，这将鼓励整数向量系数。如果您能想到一种方法来做到这一点，那么优化很可能是一个好方法。
此外，您还可以考虑采用 Metropolis 型蒙特卡罗解决方案。您可以在每一步随机选择是否添加向量、删除向量或替换向量。将随机选择要添加/删除/替换的向量。该更改被接受的概率是更改之前和更改之后解决方案的适用性之比。适合性可以等于当前解和序列之间的差、平方和求和，减去解中涉及的行/基向量的数量。您需要为各种术语输入适当的常量，以尝试获得 50% 左右的接受率。我有点怀疑这是否会很好地发挥作用，但我认为您在寻找可能的解决方案时仍然应该考虑它。
Sub-problem solution attempt
Well, here's an idea. This solution is not based on using a genetic algorithm, but some ideas could be used in going in that direction.
Basis vectors
First of all, you should generate what I think of as the basis vectors. For instance, if your sequence were 3 numbers long rather than 15, the basis vectors would be:
Any solution for sequence length 3 would be a linear combination of these three vectors using only positive integers. In other words, the general solution would be
where a, b and c are positive integers. For the sequence [1 2 1], the solution is v1 = 1, v2 = 1, v3 = 0. What you first want to do is find all of the possible basis vectors of length 15. From my rough calculations I think that there are somewhere between 300-400 basis vectors of length 15. I can give you some tips towards generating them if you want.
Finding solutions
Now, what you want to do is sort these basis vectors by their sums/magnitudes. Then in searching for your solution, you start with the basis vectors which have the largest sums. We start with the vectors that have the largest sums because they lead to having less total rows. We also have an array, veccoefs, which contains an entry for the linear coefficient for each basis vector. At the beginning of searching for the solution, all the veccoefs are 0.
So we take the first basis vector (the one with the largest sum/magnitude) and subtract this vector from the sequence until we either create an unsolvable result ( having a 0 1 0 in it for instance) or any of the numbers in the result is negative. We store the number of times we subtract the vector in veccoefs. We use the result after subtracting the basis vector from the sequence as the sequence for the next basis vector. If there are only zeros left in the result, then we stop the loop.
I'm not sure of the efficiency/accuracy of this method, but it might at least give you some ideas.
Other possible solutions
Another idea for solving this is to use the basis vectors and form the problem as an optimization/least squares problem. You form a matrix of the basis vectors such that the basic problem will be minimizing Sum[(Ax - b)^2] where A is the matrix of basis vectors, b is the input sequence, and x are the basis vector coefficients. However, you also want to minimize the number of rows, so you can add a term like x^T*x to the minimization function where x^T is the transpose of x. The hard part in my opinion is finding differentiable terms to add that will encourage integer vector coefficients. If you can think of a way to do that, then optimization could very well be a good way to do this.
Also, you might consider a Metropolis-type Monte Carlo solution. You would choose randomly whether to add a vector, remove a vector, or substitute a vector at each step. The vector to be added/removed/substituted would be chosen randomly. The probability of this change to be accepted would be a ratio of the suitabilities of the solutions before the change and after the change. The suitability could be equal to the difference between the current solution and the sequence, squared and summed, minus the number of rows/basis vectors involved in the solution. You would need to put in appropriate constants to for various terms to try to get the acceptance rate around 50%. I kind of doubt that this will work very well, but I thought that you should still consider it when looking for possible solutions.
GA 可以应用于这个问题，但它不会是 5 分钟的任务。您需要将几个东西放在一起，而不知道每个东西的哪种实现是最好的。
那么：
但你有一些限制，所以也许 SuperGene 概念值得考虑？
无论如何我认为GA可以应用于这个问题。值得吗？通常遗传算法不是最好的算法，但如果其他算法失败了，它们也是不错的算法。我会选择 GA，只是因为它会最有趣，但我会寻找替代解决方案（以防万一）。
PS个人见解：我正在解决N Queens Problem，对于70 < N＜ 100（棋盘 NxN，N 个皇后）。算法对于较低的 N 工作得很好（也许它正在尝试所有组合？），但是对于这个范围内的 N，我找不到合适的解决方案。健身值很快就跳到了max的90%左右，但最后总是有两个皇后发生冲突。但这是非常幼稚的实施。
GA can be applied to this problem, but it won't be 5 minute task. You need to put several things together, without knowing which implementation of each of them is best.
So:
But you have some constrains, so maybe SuperGene concept is worth considering?
Anyway I think that GA can be applied to this problem. Is it worth? Usually GA are not best algorithm, but they are decent algorithm if others fail. I would go with GA, just because it would be most fun but I would look for alternative solution (just in case).
P.S. Personal insight: I was solving N Queens Problem, for 70 < N < 100 (board NxN, N queens). Algorithm was working fine for lower N (maybe it was trying all combination?), but with N in this range, I couldn't find proper solution. Fitness quickly jumped to about 90% of max, but in the end there were always two queens conflicting. But it was very naive implementation.