问题标签 [evolutionary-algorithm]

我正在研究用于优化问题的 Java 框架。到目前为止，我已经实现了 lp_solve和GLPK，因此我可以处理线性问题 (LP) 和整数线性问题 (ILP)。现在我想提供使用进化算法作为求解器的可能性，以便能够处理具有非线性约束或非线性目标函数的问题。通常用于处理约束优化问题 (COS)。我找到了遗传算法的Apache commons 遗传包，并开始实现遗传算法。

我的算法中的染色体代表优化问题的解决方案，即它由一个 map 组成Variable -> Number。现在，在第一批人群中，我想随机创建一个解决方案并从那里开始进化。因此，我需要找到变量的随机值。我可以访问变量的下界和上界，以及它的域是否是整数是实数。因此，我通过以下方式启动变量：

这应该给我一张将newRepresentation所有变量分配给随机数的地图。但是，如果变量不受限制，即下限 equals0和上限 equals Integer.MAX_VALUE，我永远不会得到接近下限的值。例如，我有问题

那么最优解是x=6, y=4。但变量由我的 EA 初始化为：

该值永远不会接近最优解所在的下限。因此，即使经过几分钟的搜索，我的 EA 也没有找到至少接近最优解的解。

问题：如何修改染色体的起始值，使值均匀分布在整个搜索空间中？

我正在解析一些字符串，这些字符串包含对象信息以及对象的一些依赖项或要求。

这是用于产品配置的，对象是构成产品构建的组件。想象一下，当您通过列表构建汽车、计算机或其他任何具有需要您选择某些组件才能获得其他组件的组件时。这是我试图在我的应用程序中创建的逻辑。

我的应用程序向用户展示了一个 treeView 组件，其中包含从 excel 文件加载的对象列表。我正在尝试创建一个交互式对象列表，该列表可以根据节点所代表的对象之间的依赖关系正确启用和禁用 treeView 的节点。对象列表表示构建的配置。因此，对象是构成最终产品的组件，并且对于可以为任何给定构建选择哪些组件或对象具有限制。

这是包含我要为其编写逻辑的依赖项的行的示例格式：

• objectID是此对象（组件）的 id，是一个 4 位数字，极少数情况下对象的 id 中有一个字母，例如：12a4

• y1234表示此对象需要选择 id 为 1234 的对象才能处于活动状态。

• y1233表示此对象需要选择 id 为 1233 的对象才能处于活动状态。

  由于 y1234 和 y1233 在它们的 ID 号中共享相同的前两位数字，因此创建了一个 or 条件。

  因此，此对象需要选择对象 1234 或 1233，而不是同时选择两者。

• n2345 means this object is not active when object 2345 is selected.

列出的第一个依赖项始终以“y”或“n”开头，因此您永远不能拥有 objectID_1234_n2345_y1235，但您可以拥有 objectID_y1234_1235_n2345。

此外，如果条件是“或”条件，则不能有 y1234_n1233，它要么都具有 y，要么都具有 n。

更多可能的格式：

1. objectID_y1234_2345
   这是说明对象需要选择对象 1234 和对象 2345 才能使该对象处于活动状态。

2. objectID_n1234_2345_y3456
   此状态 objectID 要求不选择 1234 和 2345 并选择 3456 以使该对象处于活动状态。

3. objectID_n1234_n1233
   与 y1234_y1233 不同，如果使用 n，则条件始终为“and”，因此这意味着无法选择 1234 和 1233 以使该对象处于活动状态。

如果有不清楚的地方，请随时询问更多信息/解释。我试图尽可能清楚地解释这一点，因为依赖关系很容易变得混乱。我没有列出语句的所有可能组合，因为它们没有长度限制，而只是由带有对象 ID 的更长或多个“或”和“和”条件组成。

正在发生的事情的大图：

我有一个 objectID 的树形视图，当您选择一个对象时，您必须停用冲突的对象并激活或现在可以选择的对象。

依赖的目的：

依赖项必须回答两个问题......

1：哪些对象不能被选中来激活这个对象？

2：必须选择哪些对象才能使该对象处于活动状态？

我的问题/问题：

我发现这些数据非常脆弱，有时对象会相互依赖，从而使两个对象都失效，并且两者都无法被选中。

例子：

ID1234_y2345

ID2345_y1234

这导致 1234 或 2345 都不是活动的，因为在开始时两者都被停用，因为不满足要求（依赖关系）。

如果有人有想法可以更改表示依赖项的语法或格式，我可以这样做。我只是还没有找到一种替代方法来满足要求而不会导致更多的复杂性或问题。

最终，我正在寻找一种方法来解决这个问题并提出一个可行的解决方案。一段时间以来，我一直在尝试实施解决方案，但到目前为止，我的所有尝试都失败了。我尝试了各种递归和非递归解决方案。我可能错了，但我几乎觉得这是神经网络可以做的事情，因为我基本上是想让计算机在这里自己思考。

我一直在尝试从我需要做的所有事情的列表开始，然后实施一个满足列表的解决方案，但我最终发现了更多的问题并添加到列表中，所以我永远不会涵盖所有的可能性和那里可能还有更多我还没有发现。总的来说，我已经能够在某些时候正确地停用和激活，但它并不总是可靠的，它需要是。

当前逻辑

在树中，相同类型的组件共享相同的 2 个前导字符，因此如果 1234、1233 和 1245 在一个组中并且用户选择 1234，我将该组视为单选按钮。因此，将 1234 添加到跟踪所选组件的列表中，并将 1233,1245 添加到另一个禁用组件列表中。然后通过检查每个组件并确保它被禁用或启用，这取决于它现在是否满足它的要求来更新整个树。但是，如果我在检查时必须禁用另一个组件，目前我会重新检查树，这是非常低效的，因为它可能会继续这样做一段时间。我认为递归可能会更好地工作，但是却弄得一团糟，很难调试并且仍然存在太多问题。

对于检查组件列表，我仍然认为递归是一种方式，因为当我选择一个组件时，我需要禁用其他不可用的组件，然后检查我禁用的组件，然后检查任何因我禁用的组件禁用等等...

示例：如果我禁用 1234 并且 1890 需要 1234，我现在禁用 1890。但现在 1770 需要 1890，所以我禁用 1770。然后如果某些东西需要 1770，我需要禁用它等等...

感谢所有帮助和建议。

什么是进化计算？它是一种强化学习的方法吗？还是一种单独的机器学习方法？或者可能没有？

请引用用于回答此问题的参考资料。

我知道协方差矩阵适应进化策略所需的基本组件，但我似乎无法找到任何明确说明所选子代（lambda）是否替换父代（mu）或被添加到其中的地方。

我知道这种区别在进化计算中产生了巨大的差异，即你的种群是否卡在局部最优值并收敛，或者它是否能够脱离局部最优值并找到全局最优值。非常感谢任何有关解决此难题的帮助。

假设我有一个具有以下值的数组：

现在我想要的是我需要创建 100 个或接近 100 个。并为每组 100 个（或接近 100 个）创建单独的回合。

说

那么我该如何实现呢？

有什么算法可以研究吗？

我已经开始学习进化算法（GA，PSO，...），我想在 Matlab 中实现它们并使用不同的参数来掌握算法的结构以及它们是如何工作的。

我的问题是，我没有一些简单的测试功能可以使用。例如，具有多个峰值/谷值的函数，一个全局最小值和多个局部函数，......没什么复杂的，只是一些简单的数学函数及其公式。

我可以尝试通过将一些sin/cos/exp放在一起来弥补，但这需要时间而且真的很令人沮丧！

任何人都知道列出这些的资源（网站，书籍，...）？

我需要开发一个课程时间表软件，它可以有效地分配时间段和房间。这是基于课程的例行程序，而不是基于注册后的程序。并且有效地意味着根据员工的时间偏好为课程分配时间段，并且还需要最大限度地减少第一年和第二年的课程重叠，以便第二年的学生可以重新参加他们未能通过的课程。（以及第三年和第四年的对） .

现在，起初我认为这将是一个简单的问题，但现在似乎不同了。我看过的大多数论文都使用遗传算法/PSO/模拟退火或这些类型的算法。而且我仍然无法将问题解释为 GA 问题。我感到困惑的是为什么几乎没有人建议 DFS 或图形着色算法？

如果使用 DFS/图形着色，有人可以解释这种情况吗？或者为什么不建议或尝试它们。

对于我正在做的一个项目，我计划构建一个具有群体内效应的异步蜂窝 EA。最后一点（群体内效应）是我的问题所在。

我所说的群体内效应是指一个细胞中个体的适应度取决于相邻细胞中个体的工作方式。这并不意味着它取决于相邻细胞的适应度，而仅取决于它们的工作。

因此，如果细胞中的个体通过进化改变它的参数，它的适应度可能会提高。个体的内部变化可能对相邻细胞中个体的适应度产生积极、消极或根本没有影响。同样，当某些个体的适应度下降时，相邻单元格中个体的适应度也会提高、下降或完全没有变化。

请注意，我不是在谈论邻居之间的传播效应。细胞中的个体可以与邻居交配，通过这种交配系统，邻居已经对彼此产生了影响。然而，在这种情况下，我具体谈论的是现有个体，如果其附近的个体改变他们的参数，则需要重新测试。

这会导致您永远无法完成对个体的测试，因为改变一个个体的一个参数可能会改变对相邻个体的工作。然而，这并不重要，因为它将是一个在生产中不断自我学习的系统。

我的问题来了：我已经阅读了很多关于蜂窝 EA 的文章，但我找不到关于这些群体内影响的任何信息。这个“人口内部”当然是我自己想到的一个词，所以我什至不知道我是否在寻找正确的东西。

有人知道这些人群内的影响吗？它是否存在于有关 EA 的文献中，还是会是一个全新的事物？欢迎所有提示！

我目前正在阅读一篇关于在约束优化问题中使用 GA 的论文。在某种程度上，它正在谈论对个人（或他们所做的帕累托前沿）应用利基方案。

这似乎是一个典型的选择方案，但当我搜索时，我找不到一个很好的解释。

有人可以尽可能简单地向我解释一下，什么是利基计划？

假设赌场 (C) 的游戏只涉及一名玩家和一名庄家。该游戏使用 m+n 牌进行，m 标记为获胜牌，“n”标记为输牌。

游戏规则/信息：

1. 玩家知道每个阶段的赢牌数量“m”和输牌数量“n”。
2. 玩家开始玩“X”数量并玩到所有牌都被抽出。
3. 庄家非常聪明，有能力根据玩家在桌上的赌注来抽一张赢牌或输牌。
4. 每次抽奖都会减少任一类别的牌张数，即如果抽出中奖牌，则中奖牌数变为“m-1”，反之亦然。
5. 玩家也可以投注“0”金额。

6. 如果玩家下注“W”金额并抽出一张获胜牌。玩家获得 2W 作为回报，否则他失去下注金额

   问题：推导出玩家应该遵循的算法或策略以最大化他的利润。

一些例子 ：

测试用例 - 1：

玩家知道庄家没有机会，只能让他输掉任何他下注的赌注，所以他下注“0”金额。因此，他能做的最大值是 X。

测试用例 - 2：

玩家知道庄家别无选择，只能抽出唯一的牌，即获胜的牌，因此他下注所有的赌注，即“X”并取回“2X”。因此，他以 2 倍的金额退出赌场。

测试用例 - 3：

假设玩家下注“W”金额 - 假设庄家抽奖牌：所以净金额 = X+W 和 m->0 和 n->1 ：因此在这种情况下最大金额 X+W -如果庄家抽出失败牌：所以剩下的净额 = XW 和 m->1 和 n->0 ：因此，在这种情况下，最大数量为 2(XW)

玩家将选择'W'来最大化他的利润，这只能在 2(XW)=X+W => W=X/3 的情况下完成

因此，在这种情况下玩家可以走出的最大数量 = 4X/3