快捷導(dǎo)航

純Python實(shí)現(xiàn)遺傳算法詳解

更新時(shí)間：2023年08月11日 09:16:31 作者：微小冷

遺傳算法(GA)是七十年代被霍蘭德提出來(lái)的，那還是8086的時(shí)代，但在如今的3nm時(shí)代，仍然散發(fā)著經(jīng)典的光輝，下面我們就來(lái)看看如何利用Python實(shí)現(xiàn)遺傳算法吧

具體編程時(shí)，染色體可用字符串或者二進(jìn)制進(jìn)行編碼；自然選擇，就是適應(yīng)度函數(shù)；進(jìn)化就是迭代。所以技術(shù)上的關(guān)鍵點(diǎn)，就是復(fù)制、交叉、突變等過(guò)程的函數(shù)實(shí)現(xiàn)。

編碼

考慮到二進(jìn)制編碼存在位數(shù)限制，故而遺傳算法第一步就是確定問(wèn)題規(guī)模，例如解空間在(0,1)區(qū)間，精度要求為10⁻⁶，則共涉及到10⁶個(gè)解，需要24位二進(jìn)制才能表示完全。如果有N個(gè)變量，則共計(jì)需要24N個(gè)0/1組成序列。

接下來(lái)實(shí)現(xiàn)一個(gè)編碼函數(shù)，輸入為變量數(shù)組、變量區(qū)間以及精度要求。

# x為變量，xL為解范圍的最小值，pre為精度，N為二進(jìn)制解的個(gè)數(shù)
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為變量區(qū)間， 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)))
# 解碼是編碼的逆過(guò)程
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用于編碼單個(gè)變量，coding可編碼多個(gè)變量。其中輸入?yún)?shù)xL, xR, pre的數(shù)據(jù)格式可以改寫(xiě)為列表，從而使得待求解參數(shù)更加靈活。

遺傳

遺傳就是基因的復(fù)制和交叉，有的時(shí)候可能還會(huì)發(fā)生一點(diǎn)突變，其中交叉過(guò)程相對(duì)復(fù)雜，故而封裝成一個(gè)函數(shù)

import numpy as np
# b1,b2為編碼后的二進(jìn)制串
# M為編碼后的二進(jìn)制長(zhǎng)度；index為自然數(shù)列
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相當(dāng)于是把數(shù)組打亂，index為自然數(shù)列，當(dāng)然被打亂多次后已經(jīng)面目全非了。cross實(shí)現(xiàn)的功能是，對(duì)于輸入的b1和b2，任選其中的某幾位進(jìn)行交換。

下面是進(jìn)化過(guò)程，也就是單步執(zhí)行的程序，主要包括劣種淘汰、交叉以及突變?nèi)齻€(gè)過(guò)程。

from copy import deepcopy
from random import randint
# rMuta為突變概率；nDie為每一代淘汰掉的個(gè)數(shù)
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]]
    # 將最差的淘汰掉，將最優(yōu)的提取出來(lái)
    xs[index[-nDie:]] = xs[index[:nDie]]
    # 編碼
    bs = [coding(x, xL, xR, pre) for x in xs]
    M = len(bs[0])      # 此為編碼后的參數(shù)長(zhǎng)度
    index = np.arange(M)
    # 交叉
    for i in range(N//2):
        cross(bs[i*2], bs[i*2+1], int(M/2), index)
    # 此為突變點(diǎn)個(gè)數(shù)
    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

主程序

所謂主程序，就是加上一個(gè)逐代繁衍的循環(huán)

uniRand = np.random.uniform
# nId為個(gè)體數(shù)；nDim為參數(shù)維度；nIter為迭代數(shù)
# 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}次迭代，最佳結(jié)果為{fBest}"
            print(msg)
    fs = [func(x) for x in xs]
    index = np.argmin(fs)
    msg = "當(dāng)前參數(shù)：" + ",".join([f"{x}" for x in xs[index]])
    print(msg)

測(cè)試

最后又到了激動(dòng)人心的測(cè)試環(huán)節(jié)，還是用

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)

得到結(jié)果為

>python GA.py
第0次迭代，最佳結(jié)果為-6.109745260005657
第20次迭代，最佳結(jié)果為-11.73854686214257
第40次迭代，最佳結(jié)果為-11.656344079309445
第60次迭代，最佳結(jié)果為-11.366187890697542
第80次迭代，最佳結(jié)果為-11.526653664416903
第100次迭代，最佳結(jié)果為-11.329056280514049
當(dāng)前參數(shù)：8.073827999999999,11.655532000000001,7.032817,4.2005289999999995,-4.371395

到此這篇關(guān)于純Python實(shí)現(xiàn)遺傳算法詳解的文章就介紹到這了,更多相關(guān)Python遺傳算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: