类似背包优化问题的遗传算法
我有一个优化问题，正在尝试使用遗传算法来解决。基本上，有一个包含 10 个绑定实值变量的列表 (-1 <= x <= 1)，我需要最大化该列表的某些函数。问题是列表中最多只能有 4 个变量！= 0（子集条件）。
从数学上来说： 对于某些函数 f： [-1, 1]^10 ->右 最小 f(X) 英石 |{X 中的 var 且 var != 0}| <= 4
关于 f 的一些背景：该函数与任何类型的背包目标函数（例如 Sum x*weight 或类似函数）都不相似。
到目前为止我已经尝试过：
只是基因组 [-1, 1]^10 上的基本遗传算法，具有 1 点交叉和变量的一些高斯突变。我尝试仅使用前 4 个非零（零，足够接近 0）值来编码适应度函数中的子集条件。这种方法效果不太好，算法停留在前 4 个变量上，并且从不使用超出该值的值。我看到了某种针对 01-背包问题的 GA，这种方法效果很好，但显然这只适用于二进制变量。
您建议我接下来尝试什么？
I have a optimzation problem i'm trying to solve using a genetic algorithm. Basically, there is a list of 10 bound real valued variables (-1 <= x <= 1), and I need to maximize some function of that list. The catch is that only up to 4 variables in the list may be != 0 (subset condition).
Mathematically speaking:
For some function f: [-1, 1]^10 -> R
min f(X)
s.t.
|{var in X with var != 0}| <= 4
Some background on f: The function is NOT similar to any kind of knapsack objective function like Sum x*weight or anything like that.
What I have tried so far:
Just a basic genetic algorithm over the genome [-1, 1]^10 with 1-point-crossover and some gaussian mutation on the variables. I tried to encode the subset condition in the fitness function by using just the first 4 nonzero (zero as in close enough to 0) values. This approach doesn't work that well and the algorithm is stuck at the 4 first variables and never uses values beyond that. I saw some kind of GA for the 01-knapsack problem where this approach worked well, but apparently this works just with binary variables.
What would you recommend me to try next?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果你的适应度函数评估起来又快又脏，那么增加你的总人口规模就很便宜。
您遇到的问题是您试图同时选择两个完全不同的事物。您想要选择您关心的 4 个基因组，然后选择哪些值是最佳的。
我看到有两种方法可以做到这一点。
您创造了 210 个不同的“物种”。每个物种都由允许使用 10 个基因组中的 4 个来定义。然后，您可以分别对每个物种运行遗传算法（串行或在集群内并行）。
每个生物体只有 4 个基因组值（在创建随机后代时随机选择哪些基因组）。当两种生物体交配时，您只会与匹配的基因组交叉。如果您的一对生物体包含 3 个共同基因组，那么您可以随机选择您喜欢的基因组作为第四个。作为一种启发式方法，您还可以避免与遗传上差异太大的生物交配（即，共享两个或更少基因组的一对可能会产生不好的后代）。
我希望这能给你一些可以借鉴的想法。
If your fitness function is quick and dirty to evaluate then it's cheap to increase your total population size.
The problem you are running into is that you're trying to select two completely different things simultaneously. You want to select which 4 genomes you care about, and then what values are optimal.
I see two ways to do this.
You create 210 different "species". Each specie is defined by which 4 of the 10 genomes they are allowed to use. Then you can run a genetic algorithm on each specie separately (either serially, or in parallel within a cluster).
Each organism has only 4 genome values (when creating random offspring choose which genomes at random). When two organisms mate you only cross over with genomes that match. If your pair of organisms contain 3 common genomes then you could randomly pick which of the genome you may prefer as the 4th. You could also, as a heuristic, avoid mating organisms that appear to be too genetically different (i.e. a pair that shares two or fewer genomes may make for a bad offspring).
I hope that gives you some ideas you can work from.
您可以尝试“枢轴”式步骤：选择现有非零值之一变为零，并通过将现有零值之一设置为非零来替换它。 （我的“枢轴”术语来自线性规划，其中枢轴是单纯形法中的基本步骤）。
最简单的情况是公平地随机选择每个值；您可以为新的非零变量选择一个随机值或多个值。一种更局部的步骤是仅对现有的非零变量使用高斯步骤，但如果这些变量之一跨越零，则会产生以零值之一为中心的变化。 （请注意，这些并不相互排斥，因为您可以轻松添加这两种步骤）。
如果您有任何有关您的健身得分的本地行为的信息，您可以尝试使用它来指导您的选择。仅仅因为实际的进化不考虑适应度函数，并不意味着你不能......
You could try a "pivot"-style step: choose one of the existing nonzero values to become zero, and replace it by setting one of the existing zero values to become nonzero. (My "pivot" term comes from linear programming, in which a pivot is the basic step in the simplex method).
Simplest case would be to be evenhandedly random in the selection of each of these values; you can choose a random value, or multiple values, for the new nonzero variable. A more local kind of step would be to use a Gaussian step only on the existing nonzero variables, but if one of those variables crosses zero, spawn variations that pivot to one of the zero values. (Note that these are not mutually exclusive, as you can easily add both kinds of steps).
If you have any information about the local behavior of your fitness score, you can try to use that to guide your choice. Just because actual evolution doesn't look at the fitness function, doesn't mean you can't...
在没有子集约束的情况下，你的 GA 能否很好地解决问题？如果没有，您可能想先解决这个问题。
其次，您可以使约束变得软而不是硬：惩罚解对超过 4 个零值变量的适应性。（您可以从进一步放宽约束开始，允许 9 个 0 值变量，然后是 8 个，等等.，并确保 GA 能够在使问题变得更加困难之前处理这些问题变体。）
第三，也许尝试 2 点或多点交叉而不是 1 点交叉。
希望有帮助。
-特德
Does your GA solve the problem well without the subset constraint? If not, you might want to tackle that first.
Secondly, you might make your constraint soft instead of hard: Penalize a solution's fitness for each zero-valued variable it has, beyond 4. (You might start by loosening the constraint even further, allowing 9 0-valued variables, then 8, etc., and making sure the GA is able to handle those problem variants before making the problem more difficult.)
Thirdly, maybe try 2-point or multi-point crossover instead of 1-point.
Hope that helps.
-Ted