在Python中解决图形的多目标优化问题

Question

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

这就是问题所在:我想找到一组n个顶点(n是常数,比如100)和m个边(m可以改变),其中一组度量被优化:

• 公制A需要尽可能高
• 公制B需要尽可能低
• 公制C需要尽可能高
• 度量D需要尽可能低

我最好的猜测是选择GA.我对遗传算法不太熟悉,但我可以花一点时间学习基础知识.从我到目前为止所读到的内容来看,我需要这样做:

1. 通过m = random [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是顶点数.要评估您的个体,您只需要根据个体基因型建立邻接矩阵.有关评估功能示例,请参阅以下要点https://gist.github.com/cmd-ntrf/7816665.

你的健康将由4个目标组成,并根据你所说的每个目标的最小化和最大化,健身类将被创建如下:

creator.create("Fitness", 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背包示例. http://deap.gel.ulaval.ca/doc/default/examples/ga_knapsack.html

基本上,为了启动和运行,您只需在使用建议的评估函数时将onemax示例的一部分与背包合并.