遗传算法如何解决任务分配给工人的问题
How can Genetic Algorithms solve task-allocation to worker problems
我正在尝试了解如何使用遗传算法来解决任务分配给工人的问题，如一篇名为 Solving Task Allocation to the Worker Using Genetic Algorithm 的论文所述。
例如，我有以下 table 代表工人以及他们完成一项任务需要多长时间。
## Task number going left to right
## Worker number going down
# | 1 | 2 | 3 | 4 | 5 |
1 | 2 | 5 | 7 | 1 | 6 |
2 | 5 | 4 | 9 | 2 | 4 |
3 | 4 | 3 | 2 | 1 | 6 |
4 | 7 | 1 | 8 | 9 | 2 |
5 | 3 | 2 | 6 | 1 | 8 |
问题涉及为每个任务选择执行任务最快的工人。我读过遗传算法由5个关键阶段组成：初始种群、适应度函数、选择、交叉（交配）和变异。
我了解到table代表了染色体所代表的个体的初始种群。染色体里面含有基因。
我不明白的是其他阶段以及这将如何解决问题。我上面提到的其他阶段（适应度函数、选择、交叉（交配）和变异）与解决这个问题有什么关系？
排队的随机工人向量是一个潜在的解决方案。 （初始化）
要查看它们如何执行任务，您可以使用 objective 函数（适应度函数是评估每个解决方案的方式）。基本上，您可以使用您提供的 table 来评估每个工人向量所需的时间。
对于交叉，您采用 2 个（随机）解决方案并混合它们的特性。文献中有多种方法可以做到这一点。
对于突变，您一次选择（也随机）1 个解决方案并改变它们的一个特征。
您评估新的解决方案，并为下一次迭代保留迄今为止找到的 N 个最佳解决方案。
适应度函数是解决方案质量的度量。您可以使用它来区分解决方案，例如，在最大化问题中，适应度为 10 的解决方案优于适应度为 5 的解决方案
一旦您知道每个解决方案的适用性，您就可以 select 更好的解决方案并避免更差的解决方案。有许多类型的 selection 方法，例如锦标赛 selection，其中 selects 是最好的随机 selected 解决方案
交叉用于从 selected 解决方案创建新的后代解决方案。这背后的想法是将好的基因与更好的解决方案相结合，创造出更好的解决方案
变异只是为了在解决方案中创造一点随机性。当解决方案过于相似并因此陷入所谓的局部最优时，这尤其有用。
请参阅 https://github.com/mayoayodele/Permutation-GA 以了解您可以查看的简单实施方式
突变并不经常进行，因为它可能具有很大的破坏性，通常将概率设置为 1/problem_size。从上面的排列 GA 代码使用简单的适应度
for (int i = 0; i < Solution.size(); i++) {
fitness += (i * Solution.get(i));
}
从parents产生后代如下，
Parent1 [3, 0, 7, 1, 8, 9, 4, 5, 6, 2]
Fitness 219
Parent2 [2, 7, 0, 4, 5, 6, 8, 9, 1, 3]
Fitness 215
offspring [3, 0, 7, 1, 8, 9, 4, 5, 2, 6]
Fitness 223
在上面的例子中，后代比两者都好 parents 但情况并非总是如此，例如
Parent1 [9, 3, 1, 2, 8, 4, 7, 0, 5, 6]
Fitness 199
Parent2 [0, 4, 8, 3, 6, 1, 2, 7, 9, 5]
Fitness 236
offspring [9, 3, 1, 2, 8, 0, 4, 6, 7, 5]
Fitness 210
变异见下例
offspring [3, 5, 2, 1, 9, 8, 0, 4, 7, 6]
Fitness 226
offspring after mutation [3, 5, 2, 1, 9, 0, 4, 7, 8, 6]
Fitness 239
在上面的例子中，突变提高了适应度，但在下面的例子中却没有
offspring [6, 8, 3, 0, 4, 1, 7, 5, 2, 9]
209
offspring after mutation [6, 8, 3, 0, 4, 1, 7, 5, 9, 2]
202
我正在尝试了解如何使用遗传算法来解决任务分配给工人的问题，如一篇名为 Solving Task Allocation to the Worker Using Genetic Algorithm 的论文所述。
例如，我有以下 table 代表工人以及他们完成一项任务需要多长时间。
## Task number going left to right
## Worker number going down
# | 1 | 2 | 3 | 4 | 5 |
1 | 2 | 5 | 7 | 1 | 6 |
2 | 5 | 4 | 9 | 2 | 4 |
3 | 4 | 3 | 2 | 1 | 6 |
4 | 7 | 1 | 8 | 9 | 2 |
5 | 3 | 2 | 6 | 1 | 8 |
问题涉及为每个任务选择执行任务最快的工人。我读过遗传算法由5个关键阶段组成：初始种群、适应度函数、选择、交叉（交配）和变异。
我了解到table代表了染色体所代表的个体的初始种群。染色体里面含有基因。
我不明白的是其他阶段以及这将如何解决问题。我上面提到的其他阶段（适应度函数、选择、交叉（交配）和变异）与解决这个问题有什么关系？
排队的随机工人向量是一个潜在的解决方案。 （初始化） 要查看它们如何执行任务，您可以使用 objective 函数（适应度函数是评估每个解决方案的方式）。基本上，您可以使用您提供的 table 来评估每个工人向量所需的时间。
对于交叉，您采用 2 个（随机）解决方案并混合它们的特性。文献中有多种方法可以做到这一点。
对于突变，您一次选择（也随机）1 个解决方案并改变它们的一个特征。
您评估新的解决方案，并为下一次迭代保留迄今为止找到的 N 个最佳解决方案。
适应度函数是解决方案质量的度量。您可以使用它来区分解决方案，例如，在最大化问题中，适应度为 10 的解决方案优于适应度为 5 的解决方案
一旦您知道每个解决方案的适用性，您就可以 select 更好的解决方案并避免更差的解决方案。有许多类型的 selection 方法，例如锦标赛 selection，其中 selects 是最好的随机 selected 解决方案
交叉用于从 selected 解决方案创建新的后代解决方案。这背后的想法是将好的基因与更好的解决方案相结合，创造出更好的解决方案
变异只是为了在解决方案中创造一点随机性。当解决方案过于相似并因此陷入所谓的局部最优时，这尤其有用。
请参阅 https://github.com/mayoayodele/Permutation-GA 以了解您可以查看的简单实施方式
突变并不经常进行，因为它可能具有很大的破坏性，通常将概率设置为 1/problem_size。从上面的排列 GA 代码使用简单的适应度
for (int i = 0; i < Solution.size(); i++) {
fitness += (i * Solution.get(i));
}
从parents产生后代如下，
Parent1 [3, 0, 7, 1, 8, 9, 4, 5, 6, 2]
Fitness 219
Parent2 [2, 7, 0, 4, 5, 6, 8, 9, 1, 3]
Fitness 215
offspring [3, 0, 7, 1, 8, 9, 4, 5, 2, 6]
Fitness 223
在上面的例子中，后代比两者都好 parents 但情况并非总是如此，例如
Parent1 [9, 3, 1, 2, 8, 4, 7, 0, 5, 6]
Fitness 199
Parent2 [0, 4, 8, 3, 6, 1, 2, 7, 9, 5]
Fitness 236
offspring [9, 3, 1, 2, 8, 0, 4, 6, 7, 5]
Fitness 210
变异见下例
offspring [3, 5, 2, 1, 9, 8, 0, 4, 7, 6]
Fitness 226
offspring after mutation [3, 5, 2, 1, 9, 0, 4, 7, 8, 6]
Fitness 239
在上面的例子中，突变提高了适应度，但在下面的例子中却没有
offspring [6, 8, 3, 0, 4, 1, 7, 5, 2, 9]
209
offspring after mutation [6, 8, 3, 0, 4, 1, 7, 5, 9, 2]
202