遗传算法在类背包优化问题中的应用

Question

我正在尝试使用遗传算法解决优化问题。基本上，有一个由10个实数值变量（-1<=x<=1）组成的列表，并且我需要使其中某些函数最大化。但是有一个限制条件，列表中只能有4个变量！= 0（子集条件）。

数学上讲：

对于一些函数f：[-1，1] ^ 10-> R

min f（X）

s.t. | {var在X中，有var！= 0} | <= 4

关于f的一些背景：该函数与任何背包目标函数（如Sum x * weight等）都不相似。

我迄今为止尝试过的内容：

仅使用1点交叉和一些高斯突变在[-1,1]^10范围内进行基本的遗传算法。我试图通过仅使用前4个非零（零值“足够接近于0”）值来将子集条件编码到适应度函数中。这种方法效果不佳，算法会卡在前4个变量上，永远不会使用超出这个范围的值。我看到了一个针对01背包问题的GA，其中这种方法运行良好，但显然仅适用于二进制变量。

下一步你建议我尝试什么？

- dassmann

---

我对遗传算法一无所知，但你可以尝试以不同的方式编码问题：选择范围在0-9之间的4个实数和4个不同的整数。 - Patrick

总解决方案数量少于10^4，为什么不使用枚举？这是作业吗？ - willem

Answer 1

如果您的适应函数快速且不太费力，那么增加总人口数量就很便宜。

您遇到的问题是：您正在尝试同时选择完全不同的两件事情。您想选择您关心的4个基因组，然后选择最佳值。

我看到有两种方法可以做到这一点：

1. 您创建210个不同的“物种”。每个物种由它们被允许使用的10个基因组中的哪4个定义。然后，您可以分别在每个物种上运行遗传算法（序列地或在集群内并行）。

2. 每个生物只有4个基因组值（创建随机后代时，随机选择哪些基因组）。当两个生物配对时，您只与匹配的基因组交叉。如果您的一对生物体包含3个公共基因组，则可以随机选择您可能更喜欢的第四个基因组。作为一种启发式方法，您还可以避免交配看起来过于遗传不同的生物体（即，共享两个或更少基因组的一对可能会导致糟糕的后代）。

希望这给你提供了一些你可以从中工作的思路。

- Nate

Answer 2

您可以尝试使用“旋转”步骤：选择现有的非零值之一变为零，并通过将现有的零值之一设置为非零来替换它。 （我的“pivot”术语来自线性规划，其中枢轴是单纯形法中的基本步骤）。

最简单的情况是公平地随机选择每个值; 您可以选择新的非零变量的一个或多个随机值。 更局部的步骤是仅在现有非零变量上使用高斯步骤，但如果这些变量之一越过零，则生成旋转到其中一个零值的变化。 （请注意，这些不是互斥的，因为您可以轻松添加两种类型的步骤）。

如果您了解适应度评分的局部行为的任何信息，则可以尝试使用该信息来指导您的选择。 实际进化并不看健身函数，这并不意味着您不能...

- comingstorm

---

这听起来很有趣，我想我可以将其编码为（位置列表，值列表），并使用@Nate上面建议的交叉方法。 - dassmann

Answer 3

你的遗传算法是否能够在没有子集约束的情况下很好地解决问题？如果不能，你可能需要先解决这个问题。

其次，你可以将约束变得更加灵活而不是强制性的：对于每个超过4个零值变量的解决方案，惩罚其适应度。（你可以从进一步放宽约束开始，允许9个零值变量，然后是8个等等，并确保遗传算法能够处理这些问题变体，然后再使问题更加困难。）

第三，也许尝试使用2点或多点交叉，而不是1点。

希望这有所帮助。

-Ted

- tcbelding