遗传算法及其Python实现

源码地址：遗传算法

遗传算法(Genetic Algorithm, GA)是七十年代被霍兰德提出来的，那还是8086的时代。但在如今的3nm时代，仍然散发着经典的光辉，堪称跨时代的优秀算法。

GA的核心概念是种群，种群的关键是染色体，随着自然选择，染色体通过不断地复制、交叉、突变，完成一代又一代的进化，最终得到最优的结果。

具体编程时，染色体可用字符串或者二进制进行编码；自然选择，就是适应度函数；进化就是迭代。所以技术上的关键点，就是复制、交叉、突变等过程的函数实现。

编码

考虑到二进制编码存在位数限制，故而遗传算法第一步就是确定问题规模，例如解空间在$(0,1)$区间，精度要求为$10^{?6}$，则共涉及到$10^6$个解，需要24位二进制才能表示完全。如果有$N$个变量，则共计需要$24N$个0/1组成序列。

接下来实现一个编码函数，输入为变量数组、变量区间以及精度要求。

# x为变量，xL为解范围的最小值，pre为精度，N为二进制解的个数
def codeOne(x, xL, pre, N):
    x = int((x-xL)/pre)
    return [(x//2**i)%2 for i in range(N)]

from itertools import chain
# xs为一组变量， xL, xR为变量区间， pre为精度
def coding(xs, xL, xR, pre):
    N = int(np.ceil(np.log2((xR-xL)/pre)))
    xs = [codeOne(x, xL, pre, N) for x in xs]
    return np.array(list(chain(*xs)))

# 解码是编码的逆过程
def decodeOne(b, xL, pre, N):
    x = np.sum([b[i]*2**i for i in range(N)])
    return xL + x*pre

def decoding(bins, xL, xR, pre):
    N = int(np.ceil(np.log2((xR-xL)/pre)))
    M = int(len(bins)/N)
    return [decodeOne(bins[N*i:N*(i+1)], xL, pre, N) 
        for i in range(M)]

其中，codeOne用于编码单个变量，coding可编码多个变量。其中输入参数xL, xR, pre的数据格式可以改写为列表，从而使得待求解参数更加灵活。

遗传

遗传就是基因的复制和交叉，有的时候可能还会发生一点突变，其中交叉过程相对复杂，故而封装成一个函数

import numpy as np
# b1,b2为编码后的二进制串
# M为编码后的二进制长度；index为自然数列
def cross(b1, b2, M, index):
    np.random.shuffle(index)
    i1 = index[:randint(0,M)]
    np.random.shuffle(index)
    i2 = index[:randint(0,M)]
    b1[i1], b2[i2] = b2[i1], b1[i2]

其中，shuffle相当于是把数组打乱，index为自然数列，当然被打乱多次后已经面目全非了。cross实现的功能是，对于输入的b1和b2，任选其中的某几位进行交换。

下面是进化过程，也就是单步执行的程序，主要包括劣种淘汰、交叉以及突变三个过程。

from copy import deepcopy
from random import randint

# rMuta为突变概率；nDie为每一代淘汰掉的个数
def genetic(xs, func, xL, xR, pre, nMuta, nDie):
    N = len(xs)
    fs = [func(x) for x in xs]
    index = np.argsort(fs)
    fBest = fs[index[0]]
    # 将最差的淘汰掉，将最优的提取出来
    xs[index[-nDie:]] = xs[index[:nDie]]

    # 编码
    bs = [coding(x, xL, xR, pre) for x in xs]
    M = len(bs[0])      # 此为编码后的参数长度
    index = np.arange(M)
    # 交叉
    for i in range(N//2):
        cross(bs[i*2], bs[i*2+1], int(M/2), index)

    # 此为突变点个数
    for b in bs:
        np.random.shuffle(index)
        b[index[:nMuta]] = ~b[index[:nMuta]]

    # 最后解码并输出
    xs = [decoding(b, xL, xR, pre) for b in bs]
    return np.array(xs), fBest

主程序

所谓主程序，就是加上一个逐代繁衍的循环

uniRand = np.random.uniform
# nId为个体数；nDim为参数维度；nIter为迭代数
# xRange为x取值范围，pre是精度
def GA(func, nId, nDim, nIter, 
    xRange, pre, rMuta, nDie):
    xs = [uniRand(*xRange, nDim) for _ in range(nId)]
    xs = np.array(xs)
    for i in range(nIter):
        xs, fBest = genetic(xs, func, xRange[0], xRange[1],
            pre, rMuta, nDie)
        if i%20==0:
            msg = f"第{i}次迭代，最佳结果为{fBest}"
            print(msg)
    
    fs = [func(x) for x in xs]
    index = np.argmin(fs)
    msg = "当前参数：" + ",".join([f"{x}" for x in xs[index]])
    print(msg)

测试

最后又到了激动人心的测试环节，还是用

def test(xs):
    _sum = 0.0
    for i in range(len(xs)):
        _sum = _sum + np.cos((xs[i]*i)/5)*(i+1)
    return _sum

if __name__ == "__main__":
    GA(test, 30, 5, 101, (-5,5), 1e-6, 2, 2)

得到结果为

>python GA.py
第0次迭代，最佳结果为-6.109745260005657
第20次迭代，最佳结果为-11.73854686214257
第40次迭代，最佳结果为-11.656344079309445
第60次迭代，最佳结果为-11.366187890697542
第80次迭代，最佳结果为-11.526653664416903
第100次迭代，最佳结果为-11.329056280514049
当前参数：8.073827999999999,11.655532000000001,7.032817,4.2005289999999995,-4.371395

\