遗传算法如何解决对工人问题的任务分配

问题描述 投票:0回答:2

[我试图了解如何使用遗传算法来解决对工人问题的任务分配,如Solving Task Allocation to the Worker Using Genetic Algorithm号论文中所述。

作为示例,我有一个下表,该表代表工人以及他们执行任务需要多长时间。

## 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个关键阶段:初始种群,适应度函数,选择,交叉(交配)和变异。

我了解该表格代表了以染色体代表的个体的初始种群。染色体内部包含基因。

我不知道其他阶段以及这将如何解决问题。我上面提到的其他阶段(健身功能,选择,交叉(交配)和变异)与解决此问题有什么关系?

optimization genetic-algorithm
2个回答
0
投票

排队的随机工人向量是一个潜在的解决方案。 (初始化)要查看他们如何执行任务日志,可以使用目标函数(适应性函数是评估每个解决方案的方式)。基本上,您可以使用提供的表格评估每个工作人员所需的时间。

对于分频器,您需要2个(随机)解决方案,然后混合使用它们的特征。文献中有多种方法可以做到这一点。

对于突变,您一次(随机)选择一种解决方案,并更改其特征之一。

您评估新的解决方案,并保留迄今为止找到的N个最佳解决方案,以用于下一次迭代。


0
投票

适应度函数是对解决方案质量的度量。您可以使用它来区分解决方案,例如,在最大化问题中,适应度为10的解决方案优于适应度为5的解决方案

一旦您知道每种解决方案的适用性,就可以选择更好的解决方案,避免出现更糟的解决方案。选择方法有很多类型,例如锦标赛选择,它会选择最佳的随机选择解决方案]

crossover用于从选定的解决方案中创建新的后代解决方案。其背后的想法是将好的基因结合到更好的解决方案中,以创造出更好的解决方案

突变只是在解决方案中造成一些随机性。当解决方案变得过于相似并因此陷入所谓的局部最优时,这尤其有用。

请参阅https://github.com/mayoayodele/Permutation-GA,您可以查看它的简单实现

让我知道是否有帮助

© www.soinside.com 2019 - 2024. All rights reserved.