python - 解决 Python 中图的多目标优化问题

Question

我正在尝试在大型图上寻找看似复杂且耗时的多目标优化。

问题是:我想找到一个包含 n 个顶点(n 恒定，比如 100)和 m 条边(m 可以改变)的图，其中一组指标被优化:

• 指标 A 需要尽可能高
• 指标 B 需要尽可能低
• 指标 C 需要尽可能高
• 指标 D 需要尽可能低

我最好的猜测是使用 GA。我对遗传算法不是很熟悉，但我可以花一点时间学习基础知识。从我目前正在阅读的内容来看，我需要这样做:

1. 生成随机连接到的 n 个节点的图形总体彼此相距 m = random[1,2000](例如)边
2. 在每个图上运行指标 A、B、C、D
3. 是否找到了最佳解决方案(如问题中所定义)？

如果是，那就完美了。如果不是:

1. 选择最佳图表
2. 交叉
3. 变异(随机添加或删除边缘？)
4. 转到 3。

现在，我通常使用 Python 进行我的小实验。 DEAP ( https://code.google.com/p/deap/ ) 能帮我解决这个问题吗？如果是这样，我还有很多问题(尤其是关于交叉和变异步骤)，但简而言之:这些步骤(在 Python 中，使用 DEAP)是否足够简单，可以在这里解释或总结？

如果需要，我可以尝试详细说明。干杯。

Answer 1

免责声明:我是 DEAP 首席开发人员之一。

您的个人可以用二进制字符串表示。每个位将指示两个顶点之间是否存在边。因此，您的个人将由 n * (n - 1)/2 位组成，其中 n 是顶点数。要评估您的个体，您只需要根据个体基因型构建邻接矩阵。有关评估函数示例，请参阅以下要点 https://gist.github.com/cmd-ntrf/7816665 .

您的健身将由 4 个目标组成，根据您所说的每个目标的最小化和最大化，健身类将像这样创建:

creator.create("健身", base.Fitness, weights=(1.0, -1.0, 1.0, -1.0)

交叉和变异运算符可以与 OneMax 示例中的相同。 http://deap.gel.ulaval.ca/doc/default/examples/ga_onemax_short.html

但是，由于要进行多目标，因此需要多目标选择算子，NSGA2 或 SPEA2。最后，算法必须是 mu + lambda。对于多目标选择和 mu + lambda 算法的使用，请参见 GA Knapsack 示例。 http://deap.gel.ulaval.ca/doc/default/examples/ga_knapsack.html

因此，从本质上讲，要启动并运行，您只需在使用建议的评估函数时将 onemax 示例的一部分与背包合并。