遗传算法-移位规划

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} }其中，xi，yi c {1,2，.，n} s_xi != s_xj for i != j， e_yi != e_yj for i != j

人口

依赖于n，我们可以有一个D个体的种群，每个个体都具有上述的染色体构型。你可以从一开始就随机化D生物体的染色体配置开始(尽管有更好的方法来做到这一点)。

再生产

d_i和d_j说，如果一代D个体选择任何两个人，那么他们就会选择交叉。让我们在下一代中获得两个孩子，比如c_i和c_j。

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之间的整数)。

现在，假设一名员工(e_1)如果被给予某种轮班(s_1)，他的幸福是-4，但如果给另一次轮班(s_4)，他的幸福是10。

然后，个体在人群中的适应度(员工满意度)可以简单地(可以有更复杂的数学函数)所有n名员工的幸福之和。理想的最佳健身方案是，所有员工的幸福感为10，员工满意度之和为nx10，而最差的员工满意度(最低员工满意度)为nx-10。