文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

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

2024-12-11 21:54

关注

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

[[329691]]

遗传算法中的自然选择

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

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

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

员工计划的遗传算法

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

Python实现

 在本文中,我将更详细地介绍如何理解遗传算法的不同部分。

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

遗传算法代码演练的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)

 

来源:今日头条内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯