使用遗传算法优化人员规划

> Chromosomes are an important element of genetics. Photo by National Cancer Institute on Unsplash.

 

遗传算法

遗传算法是模仿自然选择过程的优化算法。 他们没有使用"数学技巧"，而是仅复制了我们知道其有效的逻辑。

遗传算法中的自然选择

这种自然选择的过程以适者生存为基础：自然界中能使最佳个体（动物，植物或其他）生存的过程。 然后，这些优胜劣汰的人彼此交配，产生了新一代。 大自然还以基因组突变的形式增加了一些随机性。

新生代是好人和坏人的混合体，但是在这里，好人将继续生存，交配，然后产生新一代。

结果是一代又一代的持续改进。

员工计划的遗传算法

人员计划是优化研究的主题，许多公司都对此进行了介绍。 一旦公司拥有许多员工，就很难在满足某些约束的同时找到适合业务需求的计划。 除其他现有解决方案外，遗传算法是一种解决此问题的优化方法。

Python实现

在上一篇文章中，我展示了如何将Python中的DEAP库用于开箱即用的遗传算法。 在本文中，我将更详细地介绍如何理解遗传算法的不同部分。

下面的代码是遗传算法的生产代码的简化版本。 为了更好地理解示例而不是速度和可重用性，对它进行了优化。 它包含应用于示例数据的每个列出的步骤。

遗传算法代码演练的6个步骤

遗传算法的步骤：

· 如何为遗传算法编码数据？

· 如何评估遗传算法解决方案？

· 如何为遗传算法编码交配（交叉）？

· 如何为遗传算法编码突变？

· 如何定义遗传算法的选择？

· 如何为遗传算法定义迭代和停止？

如果要随身携带笔记本，可以在此处下载。

第1步-如何为遗传算法编码数据？

输入数据-两种计划

在此代码中，我们将使用同一员工计划的两种不同形状。

第1类计划-每位员工

> Encoding Data For the Genetic Algorithm — Type 1 Planning — Per Employee. Picture by author.

 

第一个形状将是员工对员工的计划，详细视图。 每周计划总数是一个列表，其中包含每天的列表（在我们的情况下为5天）。 每个日常清单都包含一个班次列表（在我们的案例中为员工的11个班次）。 每个班次都是一个员工ID（从0到11，仅供参考），开始时间（0到24点之间）和班次持续时间（0到10小时之间）的列表。

我们的员工需要这种类型的计划才能知道他们何时工作。

第2类计划-每小时总计

> Encoding Data For the Genetic Algorithm — Type 2 Planning — Totals Per Hour. Picture by author.

 

第二种计划类型是每小时被雇用的员工总数。 商店所有者将使用此计划来决定该计划是否与商店的估计需求相对应。

第2步-如何评估遗传算法解决方案？

为了评估每小时的员工计划，我们需要定义一个目标情况。 定义此目标不是优化的一部分：这将是另一个项目的问题。

> Defining Evaluation For the Genetic Algorithm — Defining the Goal Situation. Picture by author.

 

我们确实需要定义如何评估提议的计划和目标计划之间的差异。 这将基于小时计划进行，将过多的员工小时总数与丢失的员工小时总数相加。 这将是一个成本函数，我们需要将其最小化。

> Defining Evaluation For the Genetic Algorithm — Defining the Cost Function. Picture by author.

 

我们可以增加人员过多或人手不足的权重，但在此示例中，我使它们相等。

步骤3 —如何为遗传算法编码交配（交叉）？

遗传算法有两个关键步骤：交配（也包括交叉或重组）和突变。

在交配步骤中，与自然选择一样，新一代是由父母群体的个体的后代形成的。

将此应用到我们的示例中，请考虑一下以后，我们将生成许多不太好的员工计划，并尝试将最好的计划结合在一起。 因此，我们需要定义一种将两个人（员工计划）彼此"混合"的方法。

在此示例中，我决定将其编码如下：

· 从人口中选择一个随机的妈妈

· 从人口中选择一个随机的父亲

· 创建一个与父级大小相同的子级，但随机填充零和一。

· 孩子的位置为一，我们从父亲那里获取数据，孩子的位置为零，我们从他母亲那里获取数据。

· 我们对每个孩子重复一次（孩子的数量等于人口数量）

> Defining Cross-Over For the Genetic Algorithm. Picture by author.

 

这是一种实现方法，还有许多其他方法可能。 为了使遗传算法起作用，在组合代码中具有随机性很重要。 当然，组合必须适合您在步骤1中选择的数据结构。

第4步-如何为遗传算法编码突变？

遗传算法中的第二个重要步骤是变异。 它包括向新一代产品添加完全随机的更改。 这种随机变化允许为不再存在的总体添加新值。

例如，考虑一种情况，该算法进行了几次迭代，并且由于选择和组合过程中的随机性，已取消选择上午10点之前的所有开始时间。 没有突变，该算法将永远无法取回该值，而稍后可能会提供更好的解决方案。

（很少数量的）新值的随机插入有助于算法摆脱这种情况。

> Defining Mutation For the Genetic Algorithm. Picture by author.

 

在这里，它被编码为用0到10之间的随机值代替一个班次的持续时间或一个班次的开始时间的加法。如果我们指定n_mutations值，则可以重复该操作。

第5步-如何为遗传算法定义选择？

选择过程非常简单：

· 首先，选择所有可行的解决方案：删除员工工作时间超过10小时的解决方案。

> Defining Selection For the Genetic Algorithm — Feasibility. Picture by author.

 

· 然后，将评估功能应用于每个人（即每个员工计划）并选择最佳人选。 所选个人的数量在代码中保持可变。

> Defining Selection For the Genetic Algorithm — Cost. Picture by author.

 

第6步-如何为遗传算法定义迭代和停止？

该代码的最后一部分是将所有先前的构建块添加到要迭代的整体代码中。

> Defining Iteration For the Genetic Algorithm. Picture by author.

 

优化参数调整

为了使遗传算法完美地工作，选择正确的参数很重要：generation_size，n_mutations和n_best在此很重要。

调整这三个将允许找到两者的最佳组合：

· 收敛到一个解决方案（而不是在没有改善的情况下随机转身）

· 避免陷入局部最优

如果在调整之后您的算法仍然陷于困境，那么另一个改进的方向将是适应交配和变异函数，然后看看会发生什么。

由于本文的目标是从头开始建立一个简单而实用的遗传算法，因此我将不涉及如何找到最佳参数的细节：这将需要另一篇文章。

感谢您的阅读。 不要犹豫，继续关注更多！

(本文翻译自Joos Korstanje的文章《A Simple Genetic Algorithm from Scratch in Python》，参考：
https://towardsdatascience.com/a-simple-genetic-algorithm-from-scratch-in-python-4e8c66ac3121)