das*_*ann 5 algorithm math mathematical-optimization genetic-algorithm evolutionary-algorithm
我有一个优化问题,我试图用遗传算法解决.基本上,有一个10个绑定实值变量的列表(-1 <= x <= 1),我需要最大化该列表的某些功能.问题是列表中最多只有4个变量!= 0(子集条件).
数学上说:对于某些函数f:[ - 1,1] ^ 10 - > R min f(X)st | {var in X with var!= 0} | <= 4
关于f的一些背景:该函数与任何类型的背包物镜函数(如Sum x*weight或类似物)不相似.
到目前为止我尝试了什么:
只是基因组的基本遗传算法[-1,1] ^ 10,在变量上有1点交叉和一些高斯变异.我尝试通过仅使用前4个非零(零,因为足够接近0)值来对适应度函数中的子集条件进行编码.这种方法不能很好地工作,并且算法停留在4个第一个变量上,并且从不使用超出该值的值.我看到了01-knapsack问题的某种GA,这种方法运行良好,但显然这只适用于二进制变量.
你会建议我接下来尝试什么？
如果您的健身功能快速而且肮脏,那么增加您的总人口规模便宜.
你遇到的问题是你试图同时选择两个完全不同的东西.您想要选择您关心的4个基因组,然后选择最佳值.
我看到有两种方法可以做到这一点.
你创造了210种不同的"物种".每个物种的定义是它们被允许使用的10个基因组中的哪4个.然后,您可以分别在每个物种上运行遗传算法(在群集中串行或并行).
每个生物体只有4个基因组值(当创建随机后代时,随机选择哪个基因组).当两个生物交配时,你只会与匹配的基因组交叉.如果您的生物体包含3个常见的基因组,那么您可以随机选择您可能更喜欢的基因组中的第4个.作为一种启发式方法,您还可以避免出现遗传上过于不同的交配生物(即,一对共享两个或更少基因组的生物可能会造成一个坏的后代).
我希望能为您提供一些可以解决的想法.
您可以尝试“枢轴”式步骤：选择现有非零值之一变为零，并通过将现有零值之一设置为非零来替换它。（我的“枢轴”术语来自线性规划，其中枢轴是单纯形法中的基本步骤）。
最简单的情况是公平地随机选择每个值；您可以为新的非零变量选择一个随机值或多个值。一种更局部的步骤是仅对现有的非零变量使用高斯步骤，但如果这些变量之一跨越零，则会产生以零值之一为中心的变化。（请注意，这些并不相互排斥，因为您可以轻松添加这两种步骤）。
如果您有任何有关您的健身得分的本地行为的信息，您可以尝试使用它来指导您的选择。仅仅因为实际的进化不考虑适应度函数，并不意味着你不能......