3

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

关于这个问题的一些信息,以及我如何表示它:我有一组事件、房间、功能(事件需要和房间满足)、学生和插槽问题在于为每个事件分配一个插槽和一个房间,例如没有学生被要求在一个时段参加两个活动,所有分配的房间都满足必要的要求。

我有一个评分功能,如果作业对违反软约束的情况进行评分,那么对于每个集合,我的重点是尽量减少这一点。

我实现 GA 的方式是从迭代构造生成的种群开始(这可以使事件未分配),然后执行正常步骤:评估、选择、交叉、变异并保持最佳状态。冲洗并重复。

我的问题是我的解决方案似乎改进得太少了。无论我做什么,人群都倾向于随机适应并被困在那里。请注意,这种适应度总是不同的,但仍然会出现一个下限。

我怀疑问题出在我的交叉函数中,这是其背后的逻辑:

随机选择两个任务进行交叉。让我们称它们为分配 A 和 B。对于 B 的所有事件,请执行以下过程(选择 B 的事件的顺序是随机的):

获取A中对应的事件,比较赋值。可能会发生 3 种不同的情况。

  • 如果其中只有一个未分配,并且可以在子节点上复制另一个分配,则选择此分配。
  • 如果它们都被分配,但只有其中一个
    在分配给孩子时不会产生冲突,则选择那个。
  • 如果它们都被分配并且没有产生冲突,则随机选择它们中的一个。

在任何其他情况下,该事件都未分配。

这会创建一个孩子,其中有一些父母的任务,一些母亲的任务,所以在我看来这是一个有效的功能。此外,它不会打破任何硬约束。

至于突变,我正在使用我的 SA 的相邻功能根据子项给我另一个分配,然后替换那个子项。

再说一遍。在这种设置下,初始种群为 100,GA 运行并始终趋于稳定在某个随机(高)适应度值。有人可以告诉我我可能做错了什么吗?

谢谢

编辑:格式化和清除一些东西

4

5 回答 5

0

如果您能提供原始问题陈述,我将能够为您提供更好的解决方案。这是我目前的答案。

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

线性程序允许用户最小化或最大化由目标函数(分级函数)建模的某些目标。目标函数由单个决策(或决策变量)的总和以及对目标函数的价值或贡献来定义。线性程序允许您的决策变量为十进制值,但整数程序强制决策变量为整数值。

那么,你的决定是什么?您的决定是将学生分配到插槽。这些插槽具有活动需要和房间满足的功能。

在您的情况下,您希望最大化分配到某个位置的学生数量。

你也有限制。在您的情况下,一名学生最多只能参加一个活动。

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

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}
于 2012-05-16T21:57:53.813 回答
0

GA 新手可能会犯许多标准错误:

  • 通常,在进行交叉时,请确保孩子有一定的机会继承使父母或父母首先获胜的东西。换句话说,选择一个基因组表示,其中基因组的“基因”片段对问题陈述具有有意义的映射。一个常见的错误是将所有内容编码为位向量,然后在交叉中将位向量在随机位置拆分,拆分位向量所代表的好东西,从而破坏使个人浮动到顶部作为好的候选者的东西。(有限的)整数向量可能是更好的选择,其中整数可以用突变代替,但不能用交叉代替。不保留某些东西(不必是 100%,

  • 一般来说,使用的突变比你想象的要少得多。突变主要是为了保持种群的一些多样性。如果你的初始种群不包含任何具有分数优势的东西,那么你的种群对于手头的问题来说太小了,而且高突变率通常无济于事。

  • 在这种特定情况下,您的交叉功能太复杂了。永远不要将旨在保持所有解决方案有效的约束放入交叉中。相反,交叉函数应该可以自由地生成无效的解决方案,并且目标函数的工作是在某种程度上(不是完全)惩罚无效的解决方案。如果您的 GA 有效,那么最终答案将不会包含任何无效作业,前提是 100% 有效作业是完全可能的。坚持交叉中的有效性可以防止有效解决方案通过无效解决方案走捷径到达其他更好的有效解决方案。

我建议任何认为自己编写的 GA 表现不佳的人进行以下测试:运行 GA 几次,并注意达到可接受结果所需的世代数。然后用随机选择替换获胜者选择步骤和目标函数(无论您使用什么 - 锦标赛、排名等),然后再次运行。如果你仍然以与真正的评估者/目标函数大致相同的速度收敛,那么你实际上并没有一个正常运行的 GA。许多说 GA 不起作用的人在他们的代码中犯了一些错误,这意味着 GA 的收敛速度与随机搜索一样慢,这足以让任何人放弃这项技术。

于 2015-03-25T17:46:39.957 回答
0

我认为 GA 只有在解决方案的一部分(向量的一部分)作为解决方案的独立部分具有重要意义时才有意义,因此交叉函数在两个解决方案向量之间整合了解决方案的有效部分。就像 DNA 序列的某个部分控制或影响个体的特定方面一样——例如,眼睛颜色就是一个基因。然而,在这个问题中,解向量的不同部分相互影响,使得交叉几乎毫无意义。这导致(我的猜测)算法很快收敛到一个单一的解决方案,不同的交叉和突变对适应度只有负面影响。

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

于 2012-05-16T14:33:36.887 回答
0

我认为遗传算法在这个问题上没有任何问题,有些人无论如何都讨厌遗传算法。

这是我要检查的内容:

首先你提到你的遗传算法稳定在一个随机的“高”适应度值,但这不是一件好事吗?在您的情况下,“高”适合度对应好还是坏?您可能在代码的一部分中偏爱“高”适应度,而在另一部分中偏爱“低”适应度,从而导致看似随机的结果。

我认为您希望对交叉操作背后的逻辑更加小心。基本上,对于所有 3 种情况,在许多情况下,做出任何这些选择都不会导致所有交叉个体的适应度增加,但您仍在使用“资源”(可能用于另一个的分配班级/学生/等)我意识到 GA 传统上会通过交叉进行分配,这会导致更糟糕的行为,但是无论如何你已经在交叉阶段执行了一些计算,为什么不选择一个实际上会提高适应度或者可能不一点也不穿越?

要考虑的可选注释:尽管您的迭代构建方法非常有趣,但这可能会导致您拥有过于复杂的基因表示,这可能会导致您的交叉出现问题。是否可以将单个单独的解决方案建模为位或整数的数组(或二维数组)?即使数组变得很长,使用更简单的交叉过程也可能是值得的。我建议使用谷歌搜索“ga 基因表示时间表”,您可能会找到一种您更喜欢的方法,并且可以更轻松地扩展到许多个体(100 对 GA 来说是一个相当小的人口规模,但我知道您仍在测试,还有多少几代人?)。

最后一点,我不确定您使用的是哪种语言,但如果它是 Java 并且您不需要手动编写 GA 代码,我建议您查看ECJ。也许即使您必须手动编码,它也可以帮助您开发您的表示或繁殖管道。

于 2012-05-18T17:54:39.613 回答
0

我会从直接衡量正在发生的事情开始。例如,有多少作业属于您的“任何其他情况”,因此什么都不做?

此外,虽然我们无法从给出的信息中真正看出,但似乎您的任何动作都无法进行“交换”,这可能是个问题。如果时间表受到严格限制,那么一旦您找到可行的方法,您可能无法将课程从 A 室转移到 B 室,因为 B 室将被使用。您需要考虑将课程从 A 移动到 B 以及将课程从 B 移动到 A 的方法。

您有时还可以通过允许违反约束来改进事情。与其禁止交叉违反约束,您可以允许它,但根据违反的“坏处”对适应度进行惩罚。

最后,您的其他运营商也可能是问题所在。如果您的选择和替换操作员过于激进,您可以很快收敛到仅比您开始时稍微好一点的东西。一旦你收敛,单靠突变很难让你重新回到高效的搜索中。

于 2012-05-18T13:47:43.923 回答