遗传算法入门及实践

物竞天择 适者生存

非常佩服那些能够把不同领域的知识融会贯通，找到其核心思想并把它在其他领域应用的人,他们都棒棒的 (๑•̀ㅂ•́)و✧

遗传算法 ( GA , Genetic Algorithm ，也叫进化算法）就是这样一种算法。它是受达尔文的进化论的启发，借鉴生物进化过程而提出的一种算法。

学一个算法最好的方法是找个题，把它写出来

目标

用遗传算法求下面函数的最大值（注：我用 python 写的）

思路

函数的极值用遗传算法来解，主要分成五步

① 编码，并随机初始化物种

② 计算每个物种的适应度

③ 淘汰与复制，去掉适应度最小的物种，复制适应度最大的物种

④ 交换，交换 DNA 中的基因

⑤ 变异，出现新的基因

⑥ 重复步骤 2~4 直到物种达到稳定

网上找的参考图

步骤一 编码，并随机初始化物种

编码有多种方式，我这里写的是其中一种方式

输入是 x1 , x2,范围是（-2048,2048），所以 x1,x2 可以用 12 位的二进制表示，我这里把一个物种的编码 x = x1+x2 ，所以 x 编码为 24 位的二进制数。下面是随机生成 x 和对 x 解码的代码

# 随机生成 X
def randomX():
    x=''
    for i in range(24):
        x=x+str(random.randint(0,1))
    return x

解码的代码之前出现了问题！感谢 精讲0909 的提醒！现已修改！

# 解码 
def decode(x):
    x1,x2=0,0
    if x[0]=='1':
        x1=-int(x[1:12],2)*1.0/1000
    else:
        x1 =int(x[1:12], 2) * 1.0 / 1000
    if x[12]=='1':
        x2=-int(x[13:24],2)*1.0/1000
    else:
        x2 =int(x[13:24], 2) * 1.0 / 1000
    return x1,x2

步骤二 计算每个物种的适应度

因为要求最大值，所以这里的适应度可以取 x1,x2带入函数得到的值，值越大代表越适应环境

# 函数
def Rosenbrock(x1,x2):
    return 100*(x1*x1-x2)**2+(1-x1)**2

# 2. 计算适应度
        for i in range(len(x)):
            x1, x2 = decode(x[i])
            adapt.append(Rosenbrock(x1, x2))

步骤三 淘汰与复制

可以理解为：长的帅才能找到女朋友留下后代

淘汰：适应度最低的

复制：适应度最高的

 # 3. 复制 - 找到适应度最大的和最小的
        minAdapt,minX=adapt[0],0
        maxAdapt,maxX=adapt[0],0
        for i in range(len(x)):
            if(adapt[i]<minAdapt):
                minAdapt, minX = adapt[i], i
            if (adapt[i] > maxAdapt):
                maxAdapt, maxX =  adapt[i], i
        #  适应度最小的去掉,最大的double
        x[minX],adapt[minX]=x[maxX],adapt[maxX]

步骤四 交换 DNA 中的基因

DNA 交换才能产生更优秀（适应度更高）的人后代

这里交换是用随机选两个生物，随机交换DNA中的一段，因为有了上面的淘汰和复制，所以获得交配（换）权的生物有更大概率是适应度高的生物。

 # 4. 交换 随机交换(这里交换 3 次)
        for i in range(3):
            n1=random.randint(0,3)
            n2 = random.randint(0, 3)
            xa=x[n1]
            xb =x[n2]
            cut_point=random.randint(1,23)
            xa1 = xa[:cut_point] + xb[cut_point:]
            xb1 = xb[:cut_point] + xa[cut_point:]
            x[n1]=xa1
            x[n2]=xb1

步骤五 变异

和《进化论》里一样，基因变异是个小概率事件，且不一定往好的方向变还是往差的方向变，但是！如果没有变异，有些基因可能永远不会出现。

例如：0001 和 1000 无论怎么交换也不能产生 1100

但是，概率一定要小，太大了就不稳定了

# 5. 变异
        for i in range(len(x)):
            tempx=x[i]
            for j in range(len(tempx)):
                # 每位有十万分之2的概率变异
                ran=random.randint(0,100000)
                if ran>99998:
                    if tempx[j] is '1':
                       tempx=tempx[:j]+'0'+tempx[j+1:]
                    else:
                        tempx = tempx[:j] + '1' + tempx[j + 1:]

步骤六 判断物种达到稳定

判断物种达到稳定有很多种方法，我这里是用的总的适应度变化来判断的，越到到后来物种会趋于相同的 DNA ,当适应度变化幅度很小时，认为物种趋于稳定，此时活下来的就是趋近于函数极值的解。

  # 物种区域稳定，前面步骤二，三，四，五都在这个 while 循环里面
    while(abs(last_total_adapt-this_total_adapt)>0.1):

完整代码

Github