weixin_39017744
2019-09-27 17:23
采纳率: 71.1%
浏览 395

请问如何通过遗传算法得出正确字符串?

比如我希望得到最终结果为"Hello World!"。请结合代码说明,最好是用python。

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • soar3033 2019-09-29 12:11
    已采纳

    跑了一下 可以达到你的要求,请采纳

    里面加了注释,如果还有不明白的地方可以私信我

    import random
    
    m=100 #种群数
    
    v=0  #子代中符合进化目标的个体的位置索引
    
    flag=False  #用于标识是否出现目标
    
    target=[72,101,108,108,111,119,32,87,111,114,108,100,33]  #进化目标 list内为Hello World的Ascii码对应数字
    
    l=len(target)
    
    fathers=[[random.randint(32,122) for j in range(l)]for i in range(m)]  #生成父代
    
    sons=[[] for i in range(int(m*(m-1)/2))]   #生成子代list,由于子代为父代两两杂交 所以数量为m*(m-1)/2
    
    def asc(n):  #用于显示某个个体的基因 将ascii码转为字母
        st=""
        tar=[bytes([n[i]]).decode('ascii') for i in range(l)]
        for i in tar:
            st+=i
        return(st)
    
    def zj(fa):  #父代杂交产生子代
        n=0
        for i in range(m-1):
            for j in range(m-i-1):
                sons[n]=fa[i][0:int(l/2)]
                sons[n][int(l/2):l]=fa[j+i+1][int(l/2):l]
                sons[n].append(n)  #末尾添加一位作为评估分数位
                n+=1
    
    def by1():   #子代变异(等位交换)
        for i in sons:
            if (random.randint(0,10)>7):  #有概率变异 
                n=random.randint(0,l-1)
                k=random.randint(0,l-1)
                i[n],i[k]=i[k],i[n]     #基因等位交换
    
    def by2():  #子代变异(突变)
        for i in sons:
            if (random.randint(0,10)>9):  #有概率变异
                i[random.randint(0,l-1)]=random.randint(32,122)
    
    def pg():   #对子代进行评估
        global flag
        global v
        pgs=[]  #存放所有评估分数
        k=0
        for i in sons:
            fs=0
            for j in range(l):
                fs+=abs(i[j]-target[j]) #与目标越接近 分数越接近0
            if fs==0:   #如果评估分为0 则说明出现目标
                v=k
                flag=1
                break
            i[l]=fs
            pgs.append(fs)
            k+=1
        if not flag:
            pgs.sort()  #评估分数由低到高排列
            print("本次进化的最接近评分为%s" %pgs[0])   #本轮当前的最低评分
            n=pgs[m-1]  #获取第m个评估分数
            k=0
            for i in sons:
               if i[l]<=n:     #如果小于等于第m个评估分数则作为新的father
                   fathers[k]=i[0:l]
                   k+=1
                   if k==m:   #当新的father被填满 跳出
                       break
    
    def pg_fathers():   #对父代进行评估
        for i in range(len(fathers)):
            fs=0
            for j in range(len(fathers[0])):
                fs+=abs(fathers[i][j]-target[j]) #与目标越接近 分数越接近0
            if fs==0:
                print("父代的第%d个个体为目标" % i)
                return True
    
    
    
    for i in fathers:
        print(i)
    print("=============")
    count=0
    if not pg_fathers():    #对父代进行评估,如果父代没有目标才进行子代的计算
        while 1:
            zj(fathers)
            by1()
            by2()
            pg()
            count+=1
            if flag:
                break
        print("=====================================")
        print("子代的第%d个个体为进化目标(索引值)" % v)
        print("它的基因为%s" % sons[v][:-1])
        print("它的基因的ASCii码对应的字母为%s" % asc(sons[v]))
        print("一共进化了%d轮" % count)
    
    

    这是运行结果
    图片说明

    打赏 评论
  • threenewbee 2019-09-27 18:51

    遗传算法本质上是一种通过多次迭代逼近最优解的算法框架,因此你得有一个输入,一个优化的目标(在机器学习里也叫做损失函数),然后才谈得上结果。
    你的问题过于笼统,根本看不出你要做什么,也看不出和遗传算法有任何的关系。

    打赏 评论
  • JonathanYan 2019-09-27 20:45

    随机选定N个字符串变量(与目标字符串长度相同),对这些字符串进行M次杂交、突变操作得到M+N个变量,从中选出N个最接近目标字符串的变量进入下一轮循环。
    迭代这个过程直到输出目标字符串。

    打赏 评论

相关推荐 更多相似问题