當(dāng)前位置：首頁 > 编程资源 > 综合教程 >内容正文

综合教程

【python(deap库)实现】GEAP 遗传算法/遗传编程 genetic programming +

發(fā)布時(shí)間：2023/12/29 综合教程 23 生活家

生活随笔收集整理的這篇文章主要介紹了【python(deap库)实现】GEAP 遗传算法/遗传编程 genetic programming + 小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

目錄前言1.優(yōu)化問題的定義單目標(biāo)優(yōu)化多目標(biāo)優(yōu)化2.個(gè)體編碼實(shí)數(shù)編碼二進(jìn)制編碼序列編碼(Permutation encoding)粒子(Particles)3 初始種群建立一般族群同類群粒子群4 評(píng)價(jià)5 配種選擇6 變異7 突變8 環(huán)境選擇

前言

本文不介紹原理的東西，主要是實(shí)現(xiàn)進(jìn)化算法的python實(shí)現(xiàn)。
原理介紹可以看這里，能學(xué)習(xí)要很多，我也在這里寫了一些感受心得：
遺傳算法/遺傳編程進(jìn)化算法基于python DEAP庫深度解析講解

1.優(yōu)化問題的定義

單目標(biāo)優(yōu)化

creator.create('FitnessMin', base.Fitness, weights=(-1.0, ))

在創(chuàng)建單目標(biāo)優(yōu)化問題時(shí)，weights用來指示最大化和最小化。此處-1.0即代表問題是一個(gè)最小化問題，對(duì)于最大化，應(yīng)將weights改為正數(shù)，如1.0。

另外即使是單目標(biāo)優(yōu)化，weights也需要是一個(gè)tuple，以保證單目標(biāo)和多目標(biāo)優(yōu)化時(shí)數(shù)據(jù)結(jié)構(gòu)的統(tǒng)一。

對(duì)于單目標(biāo)優(yōu)化問題，weights 的絕對(duì)值沒有意義，只要符號(hào)選擇正確即可。

多目標(biāo)優(yōu)化

creator.create('FitnessMulti', base.Fitness, weights=(-1.0, 1.0))

對(duì)于多目標(biāo)優(yōu)化問題，weights用來指示多個(gè)優(yōu)化目標(biāo)之間的相對(duì)重要程度以及最大化最小化。如示例中給出的(-1.0, 1.0)代表對(duì)第一個(gè)目標(biāo)函數(shù)取最小值，對(duì)第二個(gè)目標(biāo)函數(shù)取最大值。

2.個(gè)體編碼

實(shí)數(shù)編碼(Value encoding)：直接用實(shí)數(shù)對(duì)變量進(jìn)行編碼。優(yōu)點(diǎn)是不用解碼，基因表達(dá)非常簡(jiǎn)潔，而且能對(duì)應(yīng)連續(xù)區(qū)間。但是實(shí)數(shù)編碼后搜索區(qū)間連續(xù)，因此容易陷入局部最優(yōu)。

實(shí)數(shù)編碼

from deap import base, creator, tools
import random
IND_SIZE = 5
creator.create('FitnessMin', base.Fitness, weights=(-1.0,)) #優(yōu)化目標(biāo)：?jiǎn)巫兞浚笞钚≈?creator.create('Individual', list, fitness = creator.FitnessMin) #創(chuàng)建Individual類，繼承l(wèi)ist

toolbox = base.Toolbox()
toolbox.register('Attr_float', random.random)
toolbox.register('Individual', tools.initRepeat, creator.Individual, toolbox.Attr_float, n=IND_SIZE)

ind1 = toolbox.Individual()
print(ind1)

# 結(jié)果：[0.8579615693371493, 0.05774821674048369, 0.8812411734389638, 0.5854279538236896, 0.12908399219828248]

二進(jìn)制編碼

from deap import base, creator, tools
from scipy.stats import bernoulli

creator.create('FitnessMin', base.Fitness, weights=(-1.0,)) #優(yōu)化目標(biāo)：?jiǎn)巫兞浚笞钚≈?creator.create('Individual', list, fitness = creator.FitnessMin) #創(chuàng)建Individual類，繼承l(wèi)ist

GENE_LENGTH = 10

toolbox = base.Toolbox()
toolbox.register('Binary', bernoulli.rvs, 0.5) #注冊(cè)一個(gè)Binary的alias，指向scipy.stats中的bernoulli.rvs，概率為0.5
toolbox.register('Individual', tools.initRepeat, creator.Individual, toolbox.Binary, n = GENE_LENGTH) #用tools.initRepeat生成長(zhǎng)度為GENE_LENGTH的Individual

ind1 = toolbox.Individual()
print(ind1)

# 結(jié)果：[1, 0, 0, 0, 0, 1, 0, 1, 1, 0]

序列編碼(Permutation encoding)

from deap import base, creator, tools
import random
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", list, fitness=creator.FitnessMin)

IND_SIZE=10

toolbox = base.Toolbox()
toolbox.register("Indices", random.sample, range(IND_SIZE), IND_SIZE)
toolbox.register("Individual", tools.initIterate, creator.Individual,toolbox.Indices)
ind1 = toolbox.Individual()
print(ind1)

#結(jié)果：[0, 1, 5, 8, 2, 3, 6, 7, 9, 4]

粒子(Particles)

import random
from deap import base, creator, tools

creator.create("FitnessMax", base.Fitness, weights=(1.0, 1.0))
creator.create("Particle", list, fitness=creator.FitnessMax, speed=None,
               smin=None, smax=None, best=None)

# 自定義的粒子初始化函數(shù)
def initParticle(pcls, size, pmin, pmax, smin, smax):
    part = pcls(random.uniform(pmin, pmax) for _ in range(size))
    part.speed = [random.uniform(smin, smax) for _ in range(size)]
    part.smin = smin
    part.smax = smax
    return part

toolbox = base.Toolbox()
toolbox.register("Particle", initParticle, creator.Particle, size=2, pmin=-6, pmax=6, smin=-3, smax=3) #為自己編寫的initParticle函數(shù)注冊(cè)一個(gè)alias "Particle"，調(diào)用時(shí)生成一個(gè)2維粒子，放在容器creator.Particle中，粒子的位置落在（-6,6）中，速度限制為（-3，3）

ind1 = toolbox.Particle()
print(ind1)
print(ind1.speed)
print(ind1.smin, ind1.smax)

# 結(jié)果：[-2.176528549934324, -3.0796558214905]
#[-2.9943676285620104, -0.3222138308543414]
#-3 3

print(ind1.fitness.valid)

# 結(jié)果：False
# 因?yàn)楫?dāng)前還沒有計(jì)算適應(yīng)度函數(shù)，所以粒子的最優(yōu)適應(yīng)度值還是invalid

3 初始種群建立

一般族群

這是最常用的族群類型，族群中沒有特別的順序或者子族群。

from deap import base, creator, tools
from scipy.stats import bernoulli

# 定義問題
creator.create('FitnessMin', base.Fitness, weights=(-1.0,)) # 單目標(biāo)，最小化
creator.create('Individual', list, fitness = creator.FitnessMin)

# 生成個(gè)體
GENE_LENGTH = 5
toolbox = base.Toolbox() #實(shí)例化一個(gè)Toolbox
toolbox.register('Binary', bernoulli.rvs, 0.5)
toolbox.register('Individual', tools.initRepeat, creator.Individual, toolbox.Binary, n=GENE_LENGTH)

# 生成初始族群
N_POP = 10
toolbox.register('Population', tools.initRepeat, list, toolbox.Individual)
toolbox.Population(n = N_POP)

# 結(jié)果：
# [[1, 0, 1, 1, 0],
# [0, 1, 1, 0, 0],
# [0, 1, 0, 0, 0],
# [1, 1, 0, 1, 0],
# [0, 1, 1, 1, 1],
# [0, 1, 1, 1, 1],
# [1, 0, 0, 0, 1],
# [1, 1, 0, 1, 0],
# [0, 1, 1, 0, 1],
# [1, 0, 0, 0, 0]]

同類群

同類群即一個(gè)族群中包含幾個(gè)子族群。在有些算法中，會(huì)使用本地選擇(Local selection)挑選育種個(gè)體，這種情況下個(gè)體僅與同一鄰域的個(gè)體相互作用。

toolbox.register("deme", tools.initRepeat, list, toolbox.individual)

DEME_SIZES = 10, 50, 100
population = [toolbox.deme(n=i) for i in DEME_SIZES]

粒子群

粒子群中的所有粒子共享全局最優(yōu)。在實(shí)現(xiàn)時(shí)需要額外傳入全局最優(yōu)位置與全局最優(yōu)適應(yīng)度給族群。

creator.create("Swarm", list, gbest=None, gbestfit=creator.FitnessMax)
toolbox.register("swarm", tools.initRepeat, creator.Swarm, toolbox.particle)

4 評(píng)價(jià)

評(píng)價(jià)部分是根據(jù)任務(wù)的特性高度定制的，DEAP庫中并沒有預(yù)置的評(píng)價(jià)函數(shù)模版。

在使用DEAP時(shí)，需要注意的是，無論是單目標(biāo)還是多目標(biāo)優(yōu)化，評(píng)價(jià)函數(shù)的返回值必須是一個(gè)tuple類型。

from deap import base, creator, tools
import numpy as np
# 定義問題
creator.create('FitnessMin', base.Fitness, weights=(-1.0,)) #優(yōu)化目標(biāo)：?jiǎn)巫兞浚笞钚≈?creator.create('Individual', list, fitness = creator.FitnessMin) #創(chuàng)建Individual類，繼承l(wèi)ist

# 生成個(gè)體
IND_SIZE = 5
toolbox = base.Toolbox()
toolbox.register('Attr_float', np.random.rand)
toolbox.register('Individual', tools.initRepeat, creator.Individual, toolbox.Attr_float, n=IND_SIZE)

# 生成初始族群
N_POP = 10
toolbox.register('Population', tools.initRepeat, list, toolbox.Individual)
pop = toolbox.Population(n = N_POP)

# 定義評(píng)價(jià)函數(shù)
def evaluate(individual):
  return sum(individual), #注意這個(gè)逗號(hào)，即使是單變量?jī)?yōu)化問題，也需要返回tuple

# 評(píng)價(jià)初始族群
toolbox.register('Evaluate', evaluate)
fitnesses = map(toolbox.Evaluate, pop)
for ind, fit in zip(pop, fitnesses):
  ind.fitness.values = fit
  print(ind.fitness.values)

# 結(jié)果：
# (2.593989197511478,)
# (1.1287944225903104,)
# (2.6030877077096717,)
# (3.304964061515382,)
# (2.534627558467466,)
# (2.4697149450205536,)
# (2.344837782191844,)
# (1.8959030773060852,)
# (2.5192475334239,)
# (3.5069764929866585,)

5 配種選擇

selTournament() 錦標(biāo)賽選擇
selRoulette() 輪盤賭選擇（不能用于最小化或者適應(yīng)度會(huì)小于等于0的問題）
selNSGA2() NSGA-II選擇，適用于多目標(biāo)遺傳算法
selSPEA2() SPEA2選擇，目前版本(ver 1.2.2)的該函數(shù)實(shí)現(xiàn)有誤，沒有為個(gè)體分配距離，不建議使用。
selRandom() 有放回的隨機(jī)選擇
selBest() 選擇最佳
selWorst() 選擇最差
selTournamentDCD() Dominance/Crowding distance錦標(biāo)賽選擇，目前版本的實(shí)現(xiàn)也有些問題
selDoubleTournament() Size+Fitness雙錦標(biāo)賽選擇
selStochasticUniversalSampling() 隨機(jī)抽樣選擇
selLexicase() 詞典選擇，參考這篇文章
selEpsilonLexicase() 詞典選擇在連續(xù)值域上的擴(kuò)展

from deap import base, creator, tools
import numpy as np
# 定義問題
creator.create('FitnessMin', base.Fitness, weights=(-1.0,)) #優(yōu)化目標(biāo)：?jiǎn)巫兞浚笞钚≈?creator.create('Individual', list, fitness = creator.FitnessMin) #創(chuàng)建Individual類，繼承l(wèi)ist

# 生成個(gè)體
IND_SIZE = 5
toolbox = base.Toolbox()
toolbox.register('Attr_float', np.random.rand)
toolbox.register('Individual', tools.initRepeat, creator.Individual, toolbox.Attr_float, n=IND_SIZE)

# 生成初始族群
N_POP = 10
toolbox.register('Population', tools.initRepeat, list, toolbox.Individual)
pop = toolbox.Population(n = N_POP)

# 定義評(píng)價(jià)函數(shù)
def evaluate(individual):
  return sum(individual), #注意這個(gè)逗號(hào)，即使是單變量?jī)?yōu)化問題，也需要返回tuple

# 評(píng)價(jià)初始族群
toolbox.register('Evaluate', evaluate)
fitnesses = map(toolbox.Evaluate, pop)
for ind, fit in zip(pop, fitnesses):
  ind.fitness.values = fit

# 選擇方式1：錦標(biāo)賽選擇
toolbox.register('TourSel', tools.selTournament, tournsize = 2) # 注冊(cè)Tournsize為2的錦標(biāo)賽選擇
selectedTour = toolbox.TourSel(pop, 5) # 選擇5個(gè)個(gè)體
print('錦標(biāo)賽選擇結(jié)果：')
for ind in selectedTour:
  print(ind)
  print(ind.fitness.values)

# 選擇方式2: 輪盤賭選擇
toolbox.register('RoulSel', tools.selRoulette)
selectedRoul = toolbox.RoulSel(pop, 5)
print('輪盤賭選擇結(jié)果：')
for ind in selectedRoul:
  print(ind)
  print(ind.fitness.values)

# 選擇方式3: 隨機(jī)普遍抽樣選擇
toolbox.register('StoSel', tools.selStochasticUniversalSampling)
selectedSto = toolbox.StoSel(pop, 5)
print('隨機(jī)普遍抽樣選擇結(jié)果：')
for ind in selectedSto:
  print(ind)
  print(ind.fitness.values)
  
#結(jié)果：
#錦標(biāo)賽選擇結(jié)果：
#[0.2673058115582905, 0.8131397980144155, 0.13627430737326807, 0.10792026110464248, 0.4166962522797264]
#(1.741336430330343,)
#[0.5448284697291571, 0.9702727117158071, 0.03349947770537576, 0.7018813286570782, 0.3244029157717422]
#(2.5748849035791603,)
#[0.8525836387058023, 0.28064482205939634, 0.9235436615033125, 0.6429467684175085, 0.5965523553349544]
#(3.296271246020974,)
#[0.5243293164960845, 0.37883291328325286, 0.28423194217619596, 0.5005947374376103, 0.3017896612109636]
#(1.9897785706041071,)
#[0.4038211036464676, 0.841374996509095, 0.3555644512425019, 0.5849111474726337, 0.058759891556433574]
#(2.2444315904271317,)
#輪盤賭選擇結(jié)果：
#[0.42469039733882064, 0.8411201950346711, 0.6322812691061555, 0.7566549973076343, 0.9352307652371067]
#(3.5899776240243884,)
#[0.42469039733882064, 0.8411201950346711, 0.6322812691061555, 0.7566549973076343, 0.9352307652371067]
#(3.5899776240243884,)
#[0.5448284697291571, 0.9702727117158071, 0.03349947770537576, 0.7018813286570782, 0.3244029157717422]
#(2.5748849035791603,)
#[0.630305953330188, 0.09565983206218687, 0.890691659939096, 0.8706091807317707, 0.19708949882847437]
#(2.684356124891716,)
#[0.5961060867498598, 0.4300051776616509, 0.4512760237511251, 0.047731561819711055, 0.009892120639829804]
#(1.5350109706221766,)
#隨機(jī)普遍抽樣選擇結(jié)果：
#[0.2673058115582905, 0.8131397980144155, 0.13627430737326807, 0.10792026110464248, 0.4166962522797264]
#(1.741336430330343,)
#[0.4038211036464676, 0.841374996509095, 0.3555644512425019, 0.5849111474726337, 0.058759891556433574]
#(2.2444315904271317,)
#[0.630305953330188, 0.09565983206218687, 0.890691659939096, 0.8706091807317707, 0.19708949882847437]
#(2.684356124891716,)
#[0.40659881466060876, 0.8387139101647804, 0.28504735705240236, 0.46171554118627334, 0.7843353275244066]
#(2.7764109505884718,)
#[0.42469039733882064, 0.8411201950346711, 0.6322812691061555, 0.7566549973076343, 0.9352307652371067]
#(3.5899776240243884,)

6 變異

cxOnePoint() 單點(diǎn)交叉實(shí)數(shù)、二進(jìn)制
cxTwoPoint() 兩點(diǎn)交叉實(shí)數(shù)、二進(jìn)制
cxUniform() 均勻交叉實(shí)數(shù)、二進(jìn)制
cxPartialyMatched() 部分匹配交叉PMX 序列
cxUniformPartialyMatched() PMX變種，改兩點(diǎn)為均勻交叉序列
cxOrdered() 有序交叉序列
cxBlend() 混合交叉實(shí)數(shù)
cxESBlend() 帶進(jìn)化策略的混合交叉
cxESTwoPoint() 帶進(jìn)化策略的兩點(diǎn)交叉
cxSimulatedBinary() 模擬二值交叉實(shí)數(shù)
cxSimulatedBinaryBounded() 有界模擬二值交叉實(shí)數(shù)
cxMessyOnePoint() 混亂單點(diǎn)交叉實(shí)數(shù)、二進(jìn)制

from deap import base, creator, tools
import random
# 創(chuàng)建兩個(gè)序列編碼個(gè)體
random.seed(42) # 保證結(jié)果可復(fù)現(xiàn)
IND_SIZE = 8
creator.create('FitnessMin', base.Fitness, weights=(-1.0, ))
creator.create('Individual', list, fitness = creator.FitnessMin)

toolbox = base.Toolbox()
toolbox.register('Indices', random.sample, range(IND_SIZE), IND_SIZE)
toolbox.register('Individual', tools.initIterate, creator.Individual, toolbox.Indices)

ind1, ind2 = [toolbox.Individual() for _ in range(2)]
print(ind1, '
', ind2)
# 結(jié)果：[1, 0, 5, 2, 7, 6, 4, 3] 
# [1, 4, 3, 0, 6, 5, 2, 7]

# 單點(diǎn)交叉
child1, child2 = [toolbox.clone(ind) for ind in (ind1, ind2)]
tools.cxOnePoint(child1, child2)
print(child1, '
', child2)
#結(jié)果：[1, 4, 3, 0, 6, 5, 2, 7] 
# [1, 0, 5, 2, 7, 6, 4, 3]
# 可以看到從第四位開始被切開并交換了

# 兩點(diǎn)交叉
child1, child2 = [toolbox.clone(ind) for ind in (ind1, ind2)]
tools.cxTwoPoint(child1, child2)
print(child1, '
', child2)
# 結(jié)果：[1, 0, 5, 2, 6, 5, 2, 3] 
# [1, 4, 3, 0, 7, 6, 4, 7]
# 基因段[6, 5, 2]與[7, 6, 4]互換了

# 均勻交叉
child1, child2 = [toolbox.clone(ind) for ind in (ind1, ind2)]
tools.cxUniform(child1, child2, 0.5)
print(child1, '
', child2)
# 結(jié)果：[1, 0, 3, 2, 7, 5, 4, 3] 
# [1, 4, 5, 0, 6, 6, 2, 7]

# 部分匹配交叉
child1, child2 = [toolbox.clone(ind) for ind in (ind1, ind2)]
tools.cxPartialyMatched(child1, child2)
print(child1, '
', child2)
# 結(jié)果：[1, 0, 5, 2, 6, 7, 4, 3] 
# [1, 4, 3, 0, 7, 5, 2, 6]
# 可以看到與之前交叉算子的明顯不同，這里的每個(gè)序列都沒有沖突

# 有序交叉
child1, child2 = [toolbox.clone(ind) for ind in (ind1, ind2)]
tools.cxOrdered(child1, child2)
print(child1, '
', child2)
# 結(jié)果：[5, 4, 3, 2, 7, 6, 1, 0] 
# [3, 0, 5, 6, 2, 7, 1, 4]

# 混亂單點(diǎn)交叉
child1, child2 = [toolbox.clone(ind) for ind in (ind1, ind2)]
tools.cxMessyOnePoint(child1, child2)
print(child1, '
', child2)
# 結(jié)果：[1, 0, 5, 2, 7, 4, 3, 0, 6, 5, 2, 7] 
# [1, 6, 4, 3]
# 注意個(gè)體序列長(zhǎng)度的改變

7 突變

from deap import base, creator, tools
import random
# 創(chuàng)建一個(gè)實(shí)數(shù)編碼個(gè)體
random.seed(42) # 保證結(jié)果可復(fù)現(xiàn)
IND_SIZE = 5
creator.create('FitnessMin', base.Fitness, weights=(-1.0, ))
creator.create('Individual', list, fitness = creator.FitnessMin)

toolbox = base.Toolbox()
toolbox.register('Attr_float', random.random)
toolbox.register('Individual', tools.initRepeat, creator.Individual, toolbox.Attr_float, IND_SIZE)

ind1 = toolbox.Individual()
print(ind1)
# 結(jié)果：[0.6394267984578837, 0.025010755222666936, 0.27502931836911926, 0.22321073814882275, 0.7364712141640124]

# 高斯突變
mutant = toolbox.clone(ind1)
tools.mutGaussian(mutant, 3, 0.1, 1)
print(mutant)
# 結(jié)果：[3.672658632864655, 2.99827700737295, 3.2982590920597916, 3.339566606808737, 3.6626390539295306]
# 可以看到當(dāng)均值給到3之后，變異形成的個(gè)體均值從0.5也增大到了3附近

# 亂序突變
mutant = toolbox.clone(ind1)
tools.mutShuffleIndexes(mutant, 0.5)
print(mutant)
# 結(jié)果：[0.22321073814882275, 0.7364712141640124, 0.025010755222666936, 0.6394267984578837, 0.27502931836911926]

# 有界多項(xiàng)式突變
mutant = toolbox.clone(ind1)
tools.mutPolynomialBounded(mutant, 20, 0, 1, 0.5)
print(mutant)
# 結(jié)果：[0.674443861742489, 0.020055418656044655, 0.2573977358171454, 0.11555018832942898, 0.6725269223692601]

# 均勻整數(shù)突變
mutant = toolbox.clone(ind1)
tools.mutUniformInt(mutant, 1, 5, 0.5)
print(mutant)
# 結(jié)果：[0.6394267984578837, 3, 0.27502931836911926, 0.22321073814882275, 0.7364712141640124]
# 可以看到在第二個(gè)位置生成了整數(shù)3

8 環(huán)境選擇

DEAP中沒有設(shè)定專門的reinsertion操作。可以簡(jiǎn)單的用python的list操作來完成選擇

總結(jié)

以上是生活随笔為你收集整理的【python(deap库)实现】GEAP 遗传算法/遗传编程 genetic programming +的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

上一篇： AMQ(approximate memb
下一篇： Amazon SQS(Simple Qu