我有一个优化问题,我正在尝试使用遗传算法来解决。基本上,有一个包含 10 个绑定(bind)实值变量的列表 (-1 <= x <= 1),我需要最大化该列表的某些函数。问题是列表中最多只有 4 个变量可能是 != 0(子集条件)。
从数学上讲: 对于某些函数 f: [-1, 1]^10 -> R 最小 f(X) 英石。 |{X 中的变量,变量 != 0}| <= 4
关于 f 的一些背景:该函数与任何类型的背包目标函数都不相似,例如 Sum x*weight 或类似的函数。
到目前为止我尝试了什么:
只是基因组 [-1, 1]^10 上的基本遗传算法,具有 1 点交叉和变量上的一些高斯突变。我试图通过仅使用前 4 个非零值(零,如 足够接近 0)值对适应度函数中的子集条件进行编码。这种方法效果不佳,并且该算法停留在前 4 个变量上,并且从不使用超出该值的值。我看到了某种针对 01 背包问题的 GA,这种方法效果很好,但显然这只适用于二进制变量。
接下来你会推荐我尝试什么?
最佳答案
如果您的适应度函数评估起来既快又脏,那么增加总种群规模的成本很低。
您遇到的问题是您试图同时选择两个完全不同的东西。您想要选择您关心的 4 个基因组,然后选择最佳值。
我看到有两种方法可以做到这一点。
你创造了 210 个不同的“物种”。每个物种都由允许使用的 10 个基因组中的 4 个来定义。然后,您可以分别对每个物种运行遗传算法(串行或在集群内并行)。
每个生物体只有 4 个基因组值(在创建随机后代时随机选择哪些基因组)。当两个生物体交配时,你只会与匹配的基因组交叉。如果你的一对生物包含 3 个共同的基因组,那么你可以随机选择你可能喜欢的第 4 个基因组。作为一种启发式方法,您还可以避免与基因差异太大的生物交配(即一对共享两个或更少基因组的生物可能会产生不良后代)。
我希望这能给您一些可以借鉴的想法。
关于algorithm - 类背包优化问题的遗传算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8058355/