遗传算法 - 班次规划

Question

我有一些基本的遗传算法知识，我编写了一个简单的应用程序来寻找 X 最大化某些函数的值，但我现在正在努力解决的问题是染色体、个体、种群等对于某些函数应该是什么样子更复杂的问题，例如轮班计划。假设我们有一些员工，一些班次，我们想将他们分配给彼此。遗传算法的关键部分应该如何处理这样的数据？

Answer 1

让我做一些假设来展示如何为这个问题建立遗传算法模型的例子。

假设

1. 假设有 n 名员工标记为 e_1、e_2、...、e_n 和 n 个班次标记为 s_1, s_2, ..., s_n
2. 为了解释简单起见，令 n 为 偶数

个体的染色体

设每条染色体由n个二维元组组成。每个元组都是一对班次和员工 (s_i, e_i)。 n 元组因此是所有员工到班次的映射。因此染色体看起来像这样：

{ {s_x1, e_y1}, {s_x2, e_y2}, ... {s_xn, e_yn} }

where, xi, yi c {1,2, ..,n} for all i,
s_xi != s_xj for i != j,
e_yi != e_yj for i != j

人口

根据 n 我们可以得到 D 个个体的种群，每个个体都具有上述染色体配置。您可以从一开始就随机化 D 生物体的染色体配置开始（尽管可以有更好的方法来做到这一点）。

复制

给定一代 D 个人选择任意两个人，比如 d_i 和 d_j，对于 crossover.让我们在下一代中获得2个children，比如说c_i和c_j。它应该看起来像这样（为简单起见，将 n 视为 4）：

d_i = { {s_i1, e_i1}, {s_i2, e_i2}, s_i3, e_i3, {s_i4, e_i4} }
d_j = { {s_j1, e_j1}, {s_j2, e_j2}, s_j3, e_j3, {s_j4, e_j4} }

穿越重现，

c_i = { {s_i1, e_j3}, {s_i2, e_j2}, s_i3, e_j1, {s_i4, e_j4} }
c_j = { {s_j1, e_i3}, {s_j2, e_i2}, s_j3, e_i1, {s_j4, e_i4} }

你如何计算更大的 n 是我会让你思考的。

我也有一些关于如何将 突变 应用到模型的想法，但我也会让你思考一下（此外，这只是一个示例模型你开始了）。

关于适应度函数的思考

让我们假设您有一个名为 员工满意度 的成本适应度函数，它是 幸福度 的总和（比如 -10 到 -10 之间的整数） 10) 人口中个体的所有雇员。

现在，假设一名员工 (e_1) 如果轮班 (s_1)，他的幸福感是 -4，但如果再轮班 (s_4)，他的幸福感是幸福是 10.

然后，人口中个体的适应度（员工满意度）可以简单地（为此可以有更复杂的数学函数）所有n 名员工。理想的最佳健身场景是所有员工都有 10 幸福 和 员工满意度 总和 n x 10 比较最差的适应度（最低 员工满意度 ）是 n x -10.