基因交叉函数

Question

我正在用Java编写一个时间表生成器，使用AI方法来满足硬约束并帮助找到最佳解决方案。到目前为止，我已经实现了迭代构造（最受限制的第一种启发式算法）和模拟退火算法，而且我正在实施遗传算法。

对这个问题的一些信息，以及如何我代表它，然后： 我有一组事件，房间功能（即事件需要和房间满足），学生和插槽 的问题在于分配给每个事件老虎机和一个房间，这样就不需要学生在一个时间段内参加两个活动，所有分配的房间都满足了必要的要求。

我有一个等级的功能，为每套如果分配档次的软约束违规，因此关键是要尽量减少这种。

我实施遗传算法的方式是从迭代构建（可以将事件未分配）生成的种群开始，然后执行正常步骤：评估，选择，交叉，变异并保持最佳状态。冲洗并重复。

我的问题是，我的解决方案似乎改善太少。无论我做什么，人口往往会随机适应，并在那里停滞不前。请注意，这种健身总是不同的，但是会出现下限。

我怀疑问题出在我的交叉功能，这里是一个道理：

两个任务是随机选择交叉。让我们称之为分配A和B.对于所有B的事件，执行以下程序（顺序B的事件都被选中是随机的）：

获取一个对应的事件，并比较分配。 3种不同的情况可能发生。

• 如果只有其中一个未分配，并且如果有可能在子项上复制另一个分配，则选择此分配。
• 如果两者都被分配，但只有一个分配给孩子的时候不产生
  冲突，一个选择。
• 如果它们都被分配并且没有创建冲突，则它们是随机选择的 。

在任何其他情况下，该事件被留下未分配的。

这将创建一个孩子的一些家长的任务，一些母亲的，所以在我看来，这是一个有效的功能。而且，它并没有打破任何硬性限制。

至于突变，我用我的SA邻近的功能给我基于对孩子的另一项任务，然后更换这个孩子。

再次。通过这种设置，初始人口数为100，GA运行并始终趋于稳定在某个随机（高）适应值。有人能给我一个关于我可能做错什么的指针吗？

感谢

编辑：格式化并清除一些事情

Answer 1

我认为，如果解决方案的一部分（向量的一部分）GA才有意义，具有意义，因为该解决方案的一个独立部分，所以交叉函数在两个解向量之间集成了解的有效部分。很像DNA序列的某个部分控制或影响个体的特定方面 - 例如，眼睛的颜色就是一个基因。然而，在这个问题中，解矢量的不同部分互相影响，使交叉几乎毫无意义。这个结果（我的猜测）在算法收敛在一个单一的解决方案，相当迅速与不同的交叉和突变对健身只有负面影响。

我不相信GA是这个问题的正确工具。

Answer 2

如果您可以请提供原始问题陈述，我将能够给你一个更好的解决方案。这是我目前的答案。

遗传算法不是满足硬约束的最佳工具。这是一个可以使用整数程序解决的分配问题，它是一个线性程序的特例。

线性程序允许用户最小化或最大化某个由目标函数（分级函数）建模的目标。目标函数由个体决策（或决策变量）和目标函数的值或贡献的总和来定义。线性程序允许您的决策变量为十进制值，但整数程序会强制决策变量为整数值。

那么，你的决定是什么？你的决定是分配学生插槽。这些插槽具有事件需要和房间满足的功能。

在你的情况下，你想最大限度地分配给一个插槽的学生人数。

您也有约束。就你而言，一名学生最多只能参加一项活动。

下面的网站提供了一个关于如何为整型程序建模的很好的教程。

http://people.brunel.ac.uk/~mastjjb/jeb/or/moreip.html

对于Java具体实现，使用下面的链接。

http://javailp.sourceforge.net/

SolverFactory factory = new SolverFactoryLpSolve(); // use lp_solve 
factory.setParameter(Solver.VERBOSE, 0); 
factory.setParameter(Solver.TIMEOUT, 100); // set timeout to 100 seconds 

/** 
* Constructing a Problem: 
* Maximize: 143x+60y 
* Subject to: 
* 120x+210y <= 15000 
* 110x+30y <= 4000 
* x+y <= 75 
* 
* With x,y being integers 
* 
*/ 
Problem problem = new Problem(); 

Linear linear = new Linear(); 
linear.add(143, "x"); 
linear.add(60, "y"); 

problem.setObjective(linear, OptType.MAX); 

linear = new Linear(); 
linear.add(120, "x"); 
linear.add(210, "y"); 

problem.add(linear, "<=", 15000); 

linear = new Linear(); 
linear.add(110, "x"); 
linear.add(30, "y"); 

problem.add(linear, "<=", 4000); 

linear = new Linear(); 
linear.add(1, "x"); 
linear.add(1, "y"); 

problem.add(linear, "<=", 75); 

problem.setVarType("x", Integer.class); 
problem.setVarType("y", Integer.class); 

Solver solver = factory.get(); // you should use this solver only once for one problem 
Result result = solver.solve(problem); 

System.out.println(result); 

/** 
* Extend the problem with x <= 16 and solve it again 
*/ 
problem.setVarUpperBound("x", 16); 

solver = factory.get(); 
result = solver.solve(problem); 

System.out.println(result); 
// Results in the following output: 

// Objective: 6266.0 {y=52, x=22} 
// Objective: 5828.0 {y=59, x=16} 

Answer 3

我会通过测量什么直接去上启动。例如，你的“任何其他情况”下的所有任务中的哪一部分都属于这种情况，因此什么都不做？

此外，虽然我们无法从所给出的信息中真实地分辨出来，但似乎没有任何举动可以做“交换”，这可能是一个问题。如果日程安排受到严格限制，那么一旦您找到可行的方案，您可能无法将班级从A房间移动到B房间，因为B房间正在使用。您需要考虑将课程从A移动到B以及将课程从B移动到A的方法。

您有时也可以通过违反约束条件来改进内容。您可以允许它违反约束条件，而不是禁止交叉，但会违反违规的“坏处”比例来惩罚它。

最后，您的其他操作员可能也是问题所在。如果您的选择和替换操作员过于激进，您可以非常快速地收敛到比您刚刚开始时略好的地方。一旦你收敛，单靠突变就很难将你带回高效搜索。

Answer 4

我认为遗传算法对这个问题没有任何问题，有些人只是讨厌遗传算法而已。

这里是我会检查：

首先，你提到你的GA稳定在一个随机的“高”的健身价值，但不是一个很好的事情吗？在你的情况下，“高”健身对应于好还是坏？有可能你偏爱你的代码中的“高”健身和另一部分中的“低”健身，从而导致看似随机的结果。

我认为你希望对交叉操作背后的逻辑更加谨慎。基本上，对于所有这三种情况，在许多情况下，做出这些选择并不会增加所有交叉个体的适应度，但是您仍在使用“资源”（可能会用于另一个班级/学生/等）我意识到遗传算法传统上会通过交叉作出任务，导致更糟糕的行为，但你已经在交叉阶段进行了一些计算，为什么不选择一个实际上会改善健身或者可能不会一点都不交叉？

要考虑的可选注释：尽管您的迭代构建方法非常有趣，但这可能会导致您的基因表示过于复杂，从而可能导致交叉问题。是否有可能将单个解决方案建模为位或整数的数组（或二维数组）？即使阵列变得很长，也可能使用更简单的交叉程序。我建议谷歌搜索“ga gene representation time tabling”，你可能会发现一种你更喜欢的方法，并且可以更容易地扩展到许多个人（100是GA的一个相当小的人口规模，但我知道你还在测试，代？）。

最后一点说明，我不确定你在使用什么语言，但如果是Java而且你不需要手工编写GA，我建议看看ECJ。也许即使你必须手工编写代码，它可以帮助你开发你的代表或繁殖管道。

Answer 5

新到GA可以使任意数量的标准错误：

• 在一般情况下，做交叉时，确保孩子有继承的是这让父母或父母的赢家一定的几率（ s）首先。换句话说，选择一个基因组表示，其中基因组的“基因”片段对问题陈述有意义的映射。一个常见的错误是将所有东西都编码为一个位矢量，然后在交叉处将随机位置分开，将位矢量代表的好东西分开，从而破坏使个体浮动到最佳位置的东西，作为一个好候选。 （有限）整数的向量可能是一个更好的选择，整数可以被替换为突变而不是交叉。不保留什么东西（不一定是100％，但它必须是某个方面）让父母赢家意味着你基本上在进行随机搜索，这不会比线性搜索更好。

• 一般来说，使用比您想象的更少的突变。突变主要是为了保持人口的多样性。如果您的初始人群不包含任何具有分数优势的事物，那么您的人口对于手头的问题而言太小，并且高突变率通常不会有帮助。

• 在这种特殊情况下，您的交叉功能太复杂了。千万不要施加限制，以保证所有解决方案对于交叉有效。相反，交叉功能应该可以自由生成无效的解决方案，并且这是有点（不是总共）惩罚无效解决方案的目标函数的工作。如果您的GA工作，那么最终答案将不包含任何无效分配，只要100％有效分配完全可能。坚持交叉有效性可以防止有效的解决方案通过无效的解决方案将快捷方式带到其他更好的有效解决方案。

我会建议任何人谁认为他们已经写了表现不佳的GA进行以下测试：运行GA几次，并注意辈份数花了达到可接受的结果。然后用随机选择替换赢家选择步骤和目标函数（无论您使用的是锦标赛，排名等），然后再次运行。如果你仍然以与真正的评估者/目标函数大致相同的速度收敛，那么你实际上并没有运行GA。许多说GAs不工作的人在他们的代码中犯了一些错误，这意味着GA收敛速度慢到随机搜索足够让任何人离开这项技术。