请问如何用python结合遗传算法和多目标优化计算得出最佳结果?

假设场景是一个人进入荒岛,只能带20单位重量的东西。可选物品有两种属性,分别是重量和重要性。二维列表如下(第一位是物品名称,第二位是重要性,第三位是重量):

[["knife","10","1"],["Beans","20","5"],["Potatoes","15","10"],["Onions","2","1"],["Sleeping Bag","30","7"],["Rope","10","5"],["Compass","30","1"]]
每种物品最多带一个,但是所带物品总数无限制。最终要求得出最佳物品携带方案。

2个回答

代码

from random import randint as rd

fc=20 #父代数量
equipment=[["knife",10,1],["Beans",20,5],["Potatoes",15,10],["Onions",2,1],["Sleeping Bag",30,7],["Rope",10,5],["Compass",30,1]]
fathers=[]  #父代,每个父代7个基因位(因为一共7个物品)。
maxValue=0 #最高得分
maxSon=[]

def makeFathers(fathers): #产生初始父代
    for i in range(fc):
        father=[]
        for j in range(7):
            gen=rd(0,6) #随即生成父代基因位
            if gen in father: #如果该基因已存在
                father.append(7) #则添加一个7号基因(即不存在,表示此位置不带物品)
            else:
                father.append(gen) #否则添加该随即基因
        fathers.append(father)

def makeSons(sons): #交配(父代基因交换)
    sons.clear()
    for i in range(fc-1):
        for j in range(fc-1-i):
            son=fathers[i].copy()
            son[4:]=fathers[i+j+1][4:]
            sons.append(son)

def exchange(sons): #等位交换
    for i in sons:
        if rd(0,10)>8: #概率发生
            g1=rd(0,6) #发生交换的基因位1
            g2=rd(0,6) #发生交换的基因位2
            i[g1],i[g2]=i[g2],i[g1]

def change(sons): #突变
    for i in sons:
        if rd(0,10)>8: #概率发生
            i[rd(0,6)]=rd(0,7) #随即一位的基因变为随机

def kill(sons): #杀死不符合的子代
    sonsTmp=[]
    for i in sons:
        son=i.copy()
        son.sort()
        flag=0 #基因重复标记
        weight=0 #重量计数
        for j in range(6):
            if son[j]==son[j+1] and son[j]!=7:
                flag+=1
            if son[j]!=7:
                weight+=equipment[son[j]][2] #基因位重量累加
        if son[6]!=7:
            weight+=equipment[son[6]][2]
        if not (flag>0 or weight>20): #如果不出现重复或超重
            sonsTmp.append(i)
    sons.clear()
    for i in sonsTmp:
        sons.append(i)

def rank(sons): #子代评分
    global maxValue
    global maxSon
    values=[]
    for i in sons:
        value=0 #初始评分
        for j in range(7):
            if i[j]!=7:
                value+=equipment[i[j]][1] #物品得分累加
        if value>120:
            print(i)
        i.append(value) #为子代添加评分
        values.append(value) #为总评分列表添加评分
    values.sort() #评分排序
    if maxValue<values[-1]:
        maxValue=values[-1]
    sonsTmp=[]
    for i in sons:  #将评分低于第20高得分的子代杀死
        if i[-1]>values[-fc]:
            sonsTmp.append(i)
        if i[-1]==maxValue:
            maxSon=i[:-1].copy()
    print("本轮最高得分 :%d ,目前最佳得分 :%d" % (values[-1],maxValue))
    print(maxSon)
    fathers=sonsTmp.copy() #剩余子代作为新父代

def main():
    sons=[]
    makeFathers(fathers)
    for i in range(100):  #100次迭代
        makeSons(sons)
        exchange(sons)
        change(sons)
        kill(sons)
        rank(sons)

main()


运行结果
图片说明

实际上102就是最佳值,因为样本小,好多时候一上来就是最佳值。

weixin_39017744
weixin_39017744 剩余自带做为新父代那一句变暗了,似乎是无效的。在def中添加global fathers后变得可用,但是繁殖功能中son[4:]=fathers[i+j+1][4:]报错out of range.这句让剩余子代做为新父代的是要删掉么还是怎么处理掉?
9 个月之前 回复
weixin_39017744
weixin_39017744 我放了个很大的列表进去,结果每次运行杀死不良子代之后子代为空。导致rank部分if maxValue<values[-1]:报错,超范围,直接死在第一个循环。我把重量限制改到100000都无法修正这个bug,可否通过其他方式优化流程呢?
9 个月之前 回复
soar3033
soar3033 把重量改成10很可能造成子代里一个符合结果的都没有,导致list是空的,自然超出范围了。
9 个月之前 回复
weixin_39017744
weixin_39017744 试了下如果把重量限制改到10,杀子代的第一个if会报错,说超出范围了
9 个月之前 回复
soar3033
soar3033 因为那个循环只循环了6次,而子代有7个基因位,所以最后一位单独拿出来加一次。那个循环之所以只循环6次,是为了进行第i位和第i+1位的对比。如果循环7次,那么第7次的i+1等于7,会大于list的索引。
9 个月之前 回复
weixin_39017744
weixin_39017744 那请问杀死不符合的子代时,最后一位为什么单独拿出来再加一次重量?
9 个月之前 回复
soar3033
soar3033 回复weixin_39017744: 那你可以把第0个作为空,那后面就随便加了。
9 个月之前 回复
weixin_39017744
weixin_39017744 有一个问题,如果调小重量限制,以后的空位如何填补?能不能加一个可以无限填空位的功能呢?
9 个月之前 回复
weixin_39017744
weixin_39017744 哦哦明白了,7为空位
9 个月之前 回复
weixin_39017744
weixin_39017744 不太对啊,没有第七号物品的。。。
9 个月之前 回复

你可以使用之前的那个二进制位的遗传算法的框架,只是这个程序里01分别表示某种物品是否需要,优化目标是比较计算出重要性最大。

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐