java - 如何在进化算法中初始化染色体以求解实变量上的 LP/ILP 或一般 COS？

Question

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

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

//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，其中将所有变量分配给随机数。但是，如果变量不受限制，即下限等于 0 并且上限等于 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 也没有找到至少接近最佳解决方案的解决方案。

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

Answer 1

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

示例:

您想要创建一个 5 到 10 之间的整数。因此您在该区间内创建一个均匀分布的 double (这与您的代码配合良好)，并且它位于 [5,5.5) 中的可能性等于它在 [5.5,6)、[6,6.5]、...、[9.5,10) 中。现在，要将其转换为整数，您需要对值进行取整，将我描述的两个间隔映射到每个可能的整数值。所以这对我来说似乎很好。

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

1. 随机数生成器损坏。 (如果您使用标准 JDK，则不太可能)
2. 您执行的试验太少，无法获得较低的起始值 - 间隔相当大。

编辑:我查看了 Number 类的文档。到整数的转换可以自由地使用截断或舍入。如果它确实使用舍入，则随机整数值不再均匀分布，因此您应该显式对 double 值进行取整。