单目标、混合整数、约束编程的优化算法？

Question

我有一个优化问题，无法通过解析或数值求解器求解，因为我无法提供它的导数。因此，我正在寻找使用启发式或遗传算法的解决方案。

我的问题如下：

• 单一目标
• 大规模，但变量不到10,000个
• 混合整数（MIP）（变量主要是小数，少数是布尔/整数变量）
• 受约束的（变量边界约束、等式和不等式约束，数量与变量大致相同）

所以我的问题是：

1. 是否有一篇论文考虑了所有点（特别是混合整数编程），在启发式/遗传算法中解决这个问题？

2. 是否有好的方法在启发式/遗传算法中实现混合整数编程？

3. 如何最好地处理启发式/遗传算法中的等式约束？

4. 是否有任何（开源）库可能是有前途的？

---

到目前为止，我在MOEA-Framework中实现我的问题时的经验是，当使用等式约束或MIP问题时，即使允许很多代数和一个大的种群大小来解决一个非常小的问题，遗传算法也找不到解决方案。

- Buni

---

我在OptaPlanner中有一个包含50,000个变量的数据集（MachineReassignment dataset B10），使用Late Acceptance（一种局部搜索形式）可以很好地解决。您可能想尝试LA或其他LS变体。 - Geoffrey De Smet

@GeoffreyDeSmet 谢谢您的建议。 我将我的问题的一个小子集实现为测试场景，并（终于）让它运行起来了。 然而，似乎目标/计划变量从未更改过（而只是“移动0.0 <=> 默认值”）。 每个变量都有较低和较高的边界约束，所有变量的总和必须与预定义的总和相匹配。 所有约束都被实现为硬约束，并且通过违反约束的差异来计算得分。 如何在OptaPlanner中使变量突变？ - Buni

@GeoffreyDeSmet 恭喜您的OptaPlanner，它看起来非常功能丰富和成熟！ - Buni

“所有变量的总和必须与预定义的总和相匹配” -> 自定义移动可以在这方面提供很大的帮助 :/ 在未来版本中，我将增加更多支持定量变量及其移动的功能。 - Geoffrey De Smet

我想我先看一下这个。 - Buni

Answer 1

你尝试过使用sciPy/numPy吗？它有一个执行模拟退火的命令。你需要做的唯一事情就是将约束条件转换为差异，并将它们加到目标函数中。

看看这个例子：

最小化 Z=x1^2+x2^2

满足以下条件：

x1+x2>=2

这是我的Python代码：

#import modules
import numpy as np
from scipy import optimize

#define Constraint 1
def diffC1(x1,x2):
    return max(x1+x2-2,0)

#penalization value
M=10000.

#define your objective function (with Constraint 1 inserted)
def f(X):
    x1,x2=X
    print x1,x2
    return x1**2+x2**2+M*(diffC1(x1,x2))
#initialize x1=2 and x2=2
X0=np.array([2., 2.])

#try your function
f(X0)

#solve!
np.random.seed(555)   # Seeded to allow replication.
res = optimize.anneal(f, X0, schedule="boltzmann",
                          full_output=True, maxiter=10000,
                           dwell=250, disp=True)

#evaluate your achieved objective function value
f(res[0])

- Juan Sandoval Lavieri

---

谢谢！我目前正在寻找一种算法，能够解决更多种类的数学问题（像你的问题）而不是现实世界中的问题（像OptaPlanner所做的那样）。@GeoffreyDeSmet和他的OptaPlanner为我提供了一个很好的起点，Late Acceptance（LAHC）似乎是一个很好的选择。然而，我目前正在努力解决决策变量的一般表示问题（因此MIP也会涉及到这些启发式算法）。 - Buni

我明白。正如您在模拟退火中所看到的，目标函数可以采取任何形式的限制条件。如果某些变量是整数，您可以尝试像这样最小化差异：假设在某个迭代中，“x1=4.75”，“小数部分=x1-math.ceil(x1)”，其中Ceil是一个仅取x1整数部分的函数。然后像以前一样将小数部分最小化作为目标函数的一部分。 - Juan Sandoval Lavieri

另一方面，我建议使用遗传算法来表示x1的搜索空间，仅限于整数（其他变量则按其本身类型）。我目前正在开发一个面向数学编程的GeneAlg包，如果您有兴趣，请告诉我 :)。 - Juan Sandoval Lavieri

我对你的方法很感兴趣，我真的很想看看你的库 :) - Buni

太棒了！我完成“草稿”后，会给你 GitHub 链接 :) - Juan Sandoval Lavieri