用Python从头开始实现简单遗传算法 _遗传算法

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

文章插图
> 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 —如何为遗传算法编码交配（交叉）？遗传算法有两个关键步骤：交配（也包括交叉或重组）和突变。
在交配步骤中，与自然选择一样，新一代是由父母群体的个体的后代形成的。
将此应用到我们的示例中，请考虑一下以后，我们将生成许多不太好的员工计划，并尝试将最好的计划结合在一起。因此，我们需要定义一种将两个人（员工计划）彼此"混合"的方法。
在此示例中，我决定将其编码如下：
· 从人口中选择一个随机的妈妈