遗传算法实践 -- 求函数极值

2,083 阅读4分钟
原文链接: www.jianshu.com

物竞天择 适者生存

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

遗传算法 ( 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
# 解码
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

步骤五 变异

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

例如:00011000 无论怎么交换也不能产生 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