在Python中解决图形的多目标优化问题
捕鱼达人2602929461 发布于 2023-02-12 15:57我试图在大图上找到一个复杂且耗时的多目标优化.
这就是问题所在:我想找到一组n个顶点(n是常数,比如100)和m个边(m可以改变),其中一组度量被优化:
公制A需要尽可能高
公制B需要尽可能低
公制C需要尽可能高
度量D需要尽可能低
我最好的猜测是选择GA.我对遗传算法不太熟悉,但我可以花一点时间学习基础知识.从我到目前为止所读到的内容来看,我需要这样做:
通过m = random [1,2000](例如)边缘生成随机连接的n个节点的图形群
在每个图表上运行指标A,B,C,D
是否找到了最佳解决方案(如问题中所定义)？
如果是,那就完美了.如果不:
选择最佳图表
交叉
变异(随机添加或删除边缘？)
转到3.
现在,我通常使用Python进行我的小实验.DEAP(https://code.google.com/p/deap/)可以帮我解决这个问题吗？如果是这样,我还有很多问题(特别是关于交叉和变异的步骤),但简而言之:步骤(在Python中,使用DEAP)是否足够容易在这里解释或总结？
如果需要,我可以尝试和详细说明.干杯.
-
免责声明:我是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示例的一部分与背包合并.
2023-02-12 15:59 回答
caoxingchi_411
京公网安备 11010802041100号