用Python求解图的多目标优化

Question

我试图在一个大图上找到一个看似复杂且耗时的多目标优化。

问题是:我想要找到一个n个顶点的图(n是常数的，例如100)，而m边(m可以改变)，其中一组度量被优化：

• 公制A需要尽可能高
• 公制B需要尽可能低
• 公制C必须尽可能高
• 公制D需要尽可能低

我最好的猜测是和GA一起去。我不太熟悉遗传算法，但我可以花一点时间来学习基础知识。从我目前所读到的，我需要这样做：

1. 用m=随机1,2000边生成n个随机连通图的总体
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是顶点的数目。要评估你的个人，你只需要建立一个邻接矩阵从个人基因型。有关计算函数示例，请参见下面的gist https://gist.github.com/cmd-ntrf/7816665。

您的健身将由4个目标组成，根据您所说的关于最小化和最大化每个目标的内容，健身类将被创建如下：

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

交叉和变异操作符可以与OneMax示例中的操作相同。short.html

然而，由于您想要做多目标，您将需要一个多目标选择操作符，或者NSGA2或SPEA2。最后，算法必须是mu + lambda。对于多目标选择和mu + lambda算法的使用，请参见GA背包示例。knapsack.html

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

Answer 2

我建议最好的化脓性库https://github.com/perone/Pyevolve。这将为您完成大部分工作，您只需定义适应度函数和表示节点/函数。您也可以指定交叉和变异率。