0

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

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

//Create a Random Number generator
Random generator = new Random();

//Create a new Map to store the variables and their assigned values
Map<String,Number> newRepresentation = new HashMap<String,Number>();

//Iterate over all variables from the problem
for (Entry<String,Variable> entry : problem.getVariables().entrySet()) {
    Variable variable = entry.getValue();
    Number uB = variable.getUpperBound();
    Number lB = variable.getLowerBound();
    //Create a random value for this variable
    Number randomValue = (generator.nextDouble() * (uB.doubleValue() - lB.doubleValue())) + lB.doubleValue();
    //If the variable has Integers as its domain, make the random value an Integer
    if (variable.getType() == OptVarType.INTEGER) randomValue = randomValue.intValue();
    newRepresentation.put(variable.getName(), randomValue);
}

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

max 3x+4y
s.t.
x+2y <= 14
3x-y >= 0
x-y <= 2
x in {0,...,2147483647}
y in {0,...,2147483647}

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

A new Population has been initiated: {y=1430866067, x=1616622921}
A new Population has been initiated: {y=1483081480, x=1389387196}
A new Population has been initiated: {y=242558338, x=376547119}
A new Population has been initiated: {y=1861689859, x=959676986}
...

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

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

4

1 回答 1

1

首先，我考虑过你的整数值在你转换后是否仍然均匀分布。

例子：

您想创建一个介于 5 和 10 之间的整数。因此，您在该间隔中创建了一个均匀分布的双精度数（这适用于您的代码），并且它在 [5,5.5) 中的可能性等于它在[5.5,6), 在 [6,6.5], ... , [9.5,10)。现在，要将其转换为整数，您需要对值进行下限，将我描述的两个区间映射到每个可能的整数值。所以这对我来说似乎很好。

我还进行了一个简短的测试，它对我来说效果很好。所以我只看到您的问题的两个可能原因：

  1. 随机数发生器坏了。（如果您使用标准 JDK，这不太可能）
  2. 您执行的试验太少，也无法获得低起始值 - 间隔非常大。

编辑：我查看了 Number 类的文档。转换为整数可以自由使用截断或舍入。如果确实使用舍入，则随机整数值不再均匀分布，因此您应该明确地对双精度值进行下限。

于 2012-08-23T08:25:11.487 回答