遗传算法及其Python实现

发布时间:2024年01月20日

源码地址:遗传算法

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

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

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

编码

考虑到二进制编码存在位数限制,故而遗传算法第一步就是确定问题规模,例如解空间在 ( 0 , 1 ) (0,1) (0,1)区间,精度要求为 1 0 ? 6 10^{-6} 10?6,则共涉及到 1 0 6 10^6 106个解,需要24位二进制才能表示完全。如果有 N N N个变量,则共计需要 24 N 24N 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实现的功能是,对于输入的b1b2,任选其中的某几位进行交换。

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

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.10974526000565720次迭代,最佳结果为-11.7385468621425740次迭代,最佳结果为-11.65634407930944560次迭代,最佳结果为-11.36618789069754280次迭代,最佳结果为-11.526653664416903100次迭代,最佳结果为-11.329056280514049
当前参数:8.073827999999999,11.655532000000001,7.032817,4.2005289999999995,-4.371395

\

文章来源:https://blog.csdn.net/m0_37816922/article/details/128121243
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。