python遗传算法实例：求一元二次方程实例

文章目录

• 1. 项目简介
• 1.1 解的编码
• 1.2 解的交叉融合
• 1.3 突变
• 1.4 适合度计算
• 2. 遗传算法
• 3. 演示
• 3.1 细节模式
• 3.2 非细节模式
• 4. 代码讲解
• 4.1 NumberSpecies类
• 4.2 Population类
• 4.2.1 live()
• 4.2.2 nextGeneration ()
• 4.2.3 sortByFitness ( fitnessList, speciesList)
• 4.2.4 getChildPopulation ()
• 4.2.5 getChild (f, m)
• 4.2.6 selectParent ()
• 5. 完整代码

1. 项目简介

1. random
2. matplotlib
3. re
4. time

1.1 解的编码

I N T = 2 7 + 2 6 + 2 5 + . . . + 2 0 = 127 F l o a t = 2 15 + 2 14 + 2 13 + . . . + 2 0 = 65535 INT = 2^7+2^6+2^5+...+2^0=127 \\ Float= 2^{15}+2^{14}+2^{13}+...+2^0=65535

1.4 适合度计算

T a r g e t = T ( x ) = c o e f 1 ∗ x 2 + c o e f 2 ∗ x F i t n e s s = ( T a r g e t − T ( x 1 ) ) 2 Target = T(x) = coef_1*x^2+coef_2*x \\ Fitness = (Target - T(x_1))^2

coef1coef2 是系数常量，Target 也是一个常量 由于我构建遗传的目的是要逼近一元二次方程的一个近似解，因此这里的适合度我定义作与 Target 的误差平方和，且适合度越小的个体，存活率越高。

3. 演示

if __name__ == "__main__":
# Define a express
f="1000=12x**2+25x"

# Individual code information
XINTSIZE = 9
XDECSIZE = 16

# Population information
POPULATION_SIZE = 100
CHILD_SIZE = 10
MAX_GENERATION_SIZE = 50
MUTATE_SIZE = 5
MUTATE_RATE = 0.05
CROSS_MERGE_RATE = 0.5

# visualization detail
X_RANGE = [-100,100]
Y_RANGE = [-500,6000]

# Print detail
DETAIL = False
PAUSE = True

# Create a population
numPopulation = Population(
popSize = POPULATION_SIZE,
childsSize = CHILD_SIZE,
maxGenerationSize = MAX_GENERATION_SIZE,
formulate=f,
)

numPopulation.live()

# visualization
if not DETAIL:
numPopulation.visualization()
else:
numPopulation.visualizationDetail()

print("-"*80)
best = numPopulation.species[0]
bestX = best.getDecimal()
bestTarget = numPopulation.getTarget(bestX)
print("Best x = %.3f"%bestX)
print("Best Target = %.3f"%bestTarget)
print("%.3f = %.3fx**2 + %.3fx"%(numPopulation.target,numPopulation.xCoef,numPopulation.yCoef))

1000 = 12 ∗ x 2 + 25 x 1000=12*x^2+25x

4. 代码讲解

4.2 Population类

4.2.1 live()

def live(self):
"""
群体生存周期
"""
while self.generation < self.maxGenerationSize:
self.nextGeneration()

4.2.2 nextGeneration ()

def nextGeneration(self):
"""
产生下一个世代
"""
# calculate current generation fitness
fitnessList = self.calFitness(self.species)

# order by fitness
self.sortByFitness(fitnessList, self.species)

#Survival individual
# child born
childs = self.getChildPopulation()

#choose survival child as next generation
fitnessListChild = self.calFitness(childs)
self.sortByFitness(fitnessListChild, childs)
self.species = childs[:self.popSize]

#
self.generation += 1

#
self.show(detail = DETAIL)

1. 计算当前群体适合度并排序；
2. 选中的个体生殖产生子代群体；
3. 计算子代群体的适合度并排序；
4. 将对应大小的子代群体替换掉当前群体，世代数加1；
5. 打印当前世代群体信息；

4.2.3 sortByFitness ( fitnessList, speciesList)

def sortByFitness(self, fitnessList, speciesList):
"""
根据适合度排序，选择排序，升序
"""
L = len(fitnessList)
for i in range(L):
for j in range(i,L):
if fitnessList[i] > fitnessList[j]:
fitnessList[i], fitnessList[j] = fitnessList[j], fitnessList[i]
speciesList[i], speciesList[j] = speciesList[j], speciesList[i]

4.2.4 getChildPopulation ()

def getChildPopulation(self):
"""
子代出生
return child
"""
# selectParent
fathersI, mothersI = self.selectParent()
L = len(fathersI)

# get childs
childs = []
for i in range(L):
for j in range(self.childsSize):
# child born
fI = fathersI[i]
mI = mothersI[i]
child = self.getChild(self.species[fI], self.species[mI])

# add child to child population
childs.append(child)

return childs

4.2.5 getChild (f, m)

def getChild(self,f,m):
"""
1.二进制编码交叉融合
2.突变编码
单个孩子
"""
assert isinstance(f,NumberSpecies),"crossMerge(f,m) f and m must be NumberSpecies class"
assert isinstance(m,NumberSpecies),"crossMerge(f,m) f and m must be NumberSpecies class"

seed = random.uniform(0,1)

# do crossMerge?
# decide cross position
childCode = []
for i in range(f.totalSize):
fromSeed = random.uniform(0,1)
if fromSeed > self.crossMergeRate:
childCode.append(f.code[i])
else:
childCode.append(m.code[i])

# do mutate?
# randomly choose x position to mutate
if seed < self.mutateRate:
tempPosIndex = [i for i in range(f.totalSize)]
mutatePos = random.sample(tempPosIndex,self.mutatePosSize)

# Change code
for i in mutatePos:
if childCode[i] == 0:
childCode[i] = 1

else:
childCode[i] = 0

# child born
child = NumberSpecies(XINTSIZE,XDECSIZE)
child.assignCode(childCode)

return child

4.2.6 selectParent ()

def selectParent(self,size = 20):
"""
默认选择适合度排名前20的父母，随机两两配对
return index list of select species one is father another is mother
"""
assert size < len(self.species), "selectParent Func size=%d par must less population%d"%(size, len(self.species))

# get size of couple
coupleSize = size // 2

# get total index of couple
total = set([i for i in range(coupleSize*2)])

# father and mother
father = set(random.sample(total,coupleSize))
mother = list(total - father)
mother = random.sample(mother,coupleSize)
father = random.sample(father,coupleSize)

return father, mother

5. 完整代码

#python3

#--------------------------
# Author: little shark
# Date: 2022/4/13
"""

"""

import random
from matplotlib import pyplot as plt
from time import sleep
import re

def getRange(x,y):
"""
x: x^2的系数
y: x的系数

返回可视化的取值范围[-50, 50]
"""

targets = []
scale = [i for i in range(X_RANGE[0], X_RANGE[1], 1)]
for i in scale:
t = x * i**2 + y*i
targets.append(t)

return targets

class NumberSpecies:
"""
定义了一个逼近一元二次方程解的物种
"""
def __init__(self, xIntSize = 8, xDecSize = 16):
"""
xIntSize: x元的二进制编码整数位数，默认8位，第一位是正负位
xDecSize: x元的二进制编码小数位数，默认16位

默认一共24位，排列如下
8位x元整数位  16位x元小数位
"""
# define a bit size to x
self.xIntSize = xIntSize

# define a bit size to decimal
self.xDecSize = xDecSize

# total size
self.totalSize = xIntSize + xDecSize

# define code
self.code=[0 for i in range(self.totalSize)]

# random it code
self.random()

def assignCode(self,code):
"""
直接赋予数字物种二进制代码
"""
self.code = code.copy()

def show(self):
"""
打印二进制编码信息及其对应的x元,y元的十进制
"""
print("code    = ",self.code)
print("numb    = ",self.getDecimal())
#print("fitness = ",self.fitness)

def random(self):
"""
Ramdom code
随机其编码
"""
self.code=[random.choice([0,1]) for i in range(self.totalSize)]

def getDecimal(self):
"""
turn code into decimal
将二进制编码转为十进制
"""

#---------------------------------
# X part
# part of x int
xIntNum = 0
start = 1
signXIndex = 0
end = self.xIntSize
xIntCode = self.code[start: end]
for i in range(self.xIntSize-1):
xIntNum += pow(2,self.xIntSize - i - 1)*xIntCode[i]

# part of x decimal
xDecNum = 0
start = end
end = end + self.xDecSize
xDecCode = self.code[start: end]
for i in range(self.xDecSize):
xDecNum += pow(2,self.xDecSize - i - 1)*xDecCode[i]

# x str -> float
xDecStr = str(xIntNum) + "." + str(xDecNum)
xFinalNum = float(xDecStr)
if self.code[signXIndex] == 0:
xFinalNum *= -1

return xFinalNum

def codeClone(self):
"""
return a code clone
"""
return self.code.copy()

class Population:
"""
管理NumberSpecies：
1.控制物种突变；
2.控制交叉融合；
3.计算适合度；
4.不断更新群体，淘汰适合度低的物种，选择适合度高的父/母本进行配对，诞生下一代。

"""
def __init__(self, popSize = 100, childsSize = 4, maxGenerationSize = 50, formulate = "" ):
"""
popSize: 群体大小
childsSize: 每对夫妇的子女数
maxGenerationSize: 最大世代数
formulate: 公式 constant = c1*x**n + c2*y
"""

# Is expression legal?
assert formulate != "", "You must input a formulate like target = c1*x**n + c2*y"

# Extract information from formulate express
m = re.search("([\d\.-]+)=([\d\.-]+)x\*\*2\+([\d\.-]+)x",formulate)

# Is formulate legal?
assert m != None,"Your formulate is not legal like: target = c1x**n + c2y "

# Assign, formulate
self.target = float(m.group(1))
self.xCoef = float(m.group(2))
self.xPower = 2
self.yCoef = float(m.group(3))

# Define the index of current generation
self.generation = 0

# Assign, generation information
self.popSize = popSize
self.childsSize = childsSize
self.maxGenerationSize = maxGenerationSize

# Assign, about mutate and cross merge
self.mutateRate = MUTATE_RATE
self.crossMergeRate = CROSS_MERGE_RATE
self.mutatePosSize = MUTATE_SIZE # mutate code number default 3

# Preduce population
self.species = [NumberSpecies(xIntSize = XINTSIZE, xDecSize = XDECSIZE) for i in range(popSize)]

# history of population: fitness & x & y & predict constant "Target"
self.historicalMeanFitness = []
self.historicalMeanXDecimal = []
self.historicalMeanYDecimal = []
self.historicalMeanTargetDecimal = []

self.XhistoricalTopPopulation = []
self.TargethistoricalTopPopulation = []

def getTop20Mean(self,xDecimalList,fitnessList):
"""
计算适合度排名前20物种的x和y元的平均系数以及适合度并返回
return average of coef about x & y and its target by define express
"""
assert len(xDecimalList) > 20, "Your population must more than 20"

meanXDecimal = sum(xDecimalList[:20])/len(xDecimalList[:20])
meanfitness = sum(fitnessList[:20])/len(fitnessList[:20])

return meanXDecimal, meanfitness

def calFitness(self, speciesList):
"""
计算适合度 (与定义的目标数字的误差平方)
"""
fitnessList = []
for i,num in enumerate(speciesList):
xDecNum = num.getDecimal()

# get fitness base on express
fitness = (self.target - self.getTarget(xDecNum)) ** 2

# save
fitnessList.append(fitness)

return fitnessList

def sortByFitness(self, fitnessList, speciesList):
"""
根据适合度排序，选择排序，升序
"""
L = len(fitnessList)
for i in range(L):
for j in range(i,L):
if fitnessList[i] > fitnessList[j]:
fitnessList[i], fitnessList[j] = fitnessList[j], fitnessList[i]
speciesList[i], speciesList[j] = speciesList[j], speciesList[i]

def getTarget(self,x):
"""
根据公式和给出的x的系数计算其结果。
"""
return self.xCoef * x ** self.xPower + self.yCoef * x

def show(self, top=20, detail = False, pause = False):
"""
打印世代Top N的信息：包括：世代索引，适合度，x，预测的结果，真实的结果
有两个模式：细节模式和非细节模式
细节模式：detail = True
打印Top N 物种的上述信息
非细节模式：datail = False
打印Top 20 物种的上述信息的平均值
可以进行可视化，会保存种群进化过程中的世代信息
"""
# Get decimal of x and y
xDecNums = []
for i in self.species:
xDecNum = i.getDecimal()
xDecNums.append(xDecNum)

# Get fitness
fitnessList = self.calFitness(self.species)

# Start show information
if detail:
print()
print("="*80)
print(" "*30,"*- Top %d -*"%top)
print(" "*25,"*- %d generation -*"%self.generation)
print("="*80)
print("%-12s %-12s %-12s %-12s %-12s"%("Index","Fitness","XDecimal","MyTarget","RealTarget"))
print("-"*80)
myTargets = []
for i in range(top):
my_target = self.getTarget(xDecNums[i])
myTargets.append(my_target)
print("%-12d %-12.3f %-12.3f %-12.3f %-12.3f"%(i, fitnessList[i], xDecNums[i], my_target, self.target))
print("-"*80)

# Save
self.XhistoricalTopPopulation.append(xDecNums[:top])
self.TargethistoricalTopPopulation.append(myTargets.copy())

if pause:
sleep(0.5)

else:

xDecimal, fitness = self.getTop20Mean(xDecNums, fitnessList)
my_target = self.getTarget(xDecimal)
if self.generation == 1:
print("%-12s %-12s %-12s %-12s %-12s"%("Generation","Fitness","XDecimal","MyTarget","RealTarget"))
print("-"*100)
print("%-12d %-12.3f %-12.3f %-12.3f %-12.3f"%(self.generation,fitness, xDecimal, my_target, self.target))

# Save history
self.historicalMeanFitness.append(fitness)
self.historicalMeanXDecimal.append(xDecimal)
self.historicalMeanTargetDecimal.append(my_target)

if pause:
sleep(0.5)

def visualization(self):
"""
可视化世代历史信息
"""

plt.figure(figsize=(8,5))
plt.subplot(2,1,1)
plt.plot([i+1 for i in range(self.generation)],self.historicalMeanFitness,linestyle="--",marker="o")
plt.ylabel("Fitness")

plt.subplot(2,1,2)
plt.plot([i+1 for i in range(self.generation)],self.historicalMeanTargetDecimal,linestyle="--",marker="o")
plt.ylabel("My Target real = %.3f"%self.target)

plt.show()

def visualizationDetail(self):
"""
可视化世代取值
"""
plt.ion()
plt.figure(figsize=(8,5))
plt.ion()
xScale = [i for i in range(X_RANGE[0], X_RANGE[1])]
yScale = getRange(self.xCoef, self.yCoef)

for i in range(len(self.XhistoricalTopPopulation)):

plt.cla()

plt.plot(xScale,yScale, alpha=0.7, linestyle=":",label="Express Space",color="blue")

plt.axhline(self.target,color="red",alpha=0.7,linestyle="--",label="Real Target Base Line")

plt.scatter(
self.XhistoricalTopPopulation[i],
self.TargethistoricalTopPopulation[i],
alpha=0.7,
color="red",
label = "My Target"
)
plt.title("Generation %d max is %d"%(i,self.maxGenerationSize))
plt.ylim(Y_RANGE[0],Y_RANGE[1])
plt.xlim(X_RANGE[0], X_RANGE[1])
plt.legend()

plt.pause(1)
plt.close()

def selectParent(self,size = 20):
"""
默认选择适合度排名前20的父母，随机两两配对
return index list of select species one is father another is mother
"""
assert size < len(self.species), "selectParent Func size=%d par must less population%d"%(size, len(self.species))

# get size of couple
coupleSize = size // 2

# get total index of couple
total = set([i for i in range(coupleSize*2)])

# father and mother
father = set(random.sample(total,coupleSize))
mother = list(total - father)
mother = random.sample(mother,coupleSize)
father = random.sample(father,coupleSize)

return father, mother

def live(self):
"""
群体生存周期
"""
while self.generation < self.maxGenerationSize:
self.nextGeneration()

def nextGeneration(self):
"""
产生下一个世代
"""
# calculate current generation fitness
fitnessList = self.calFitness(self.species)

# order by fitness
self.sortByFitness(fitnessList, self.species)

#Survival individual
# child born
childs = self.getChildPopulation()

#choose survival child as next generation
fitnessListChild = self.calFitness(childs)
self.sortByFitness(fitnessListChild, childs)

#
self.generation += 1

#
self.show(detail = DETAIL, pause = PAUSE)

self.species = childs[:self.popSize]

def getChildPopulation(self):
"""
子代出生
return child
"""
# selectParent
fathersI, mothersI = self.selectParent()
L = len(fathersI)

# get childs
childs = []
for i in range(L):
for j in range(self.childsSize):
# child born
fI = fathersI[i]
mI = mothersI[i]
child = self.getChild(self.species[fI], self.species[mI])

# add child to child population
childs.append(child)

return childs

def getChild(self,f,m):
"""
1.二进制编码交叉融合
2.突变编码
单个孩子
"""
assert isinstance(f,NumberSpecies),"crossMerge(f,m) f and m must be NumberSpecies class"
assert isinstance(m,NumberSpecies),"crossMerge(f,m) f and m must be NumberSpecies class"

seed = random.uniform(0,1)

# do crossMerge?
# decide cross position
childCode = []
for i in range(f.totalSize):
fromSeed = random.uniform(0,1)
if fromSeed > self.crossMergeRate:
childCode.append(f.code[i])
else:
childCode.append(m.code[i])

# do mutate?
# randomly choose x position to mutate
if seed < self.mutateRate:
tempPosIndex = [i for i in range(f.totalSize)]
mutatePos = random.sample(tempPosIndex,self.mutatePosSize)

# Change code
for i in mutatePos:
if childCode[i] == 0:
childCode[i] = 1

else:
childCode[i] = 0

# child born
child = NumberSpecies(XINTSIZE,XDECSIZE)
child.assignCode(childCode)

return child

if __name__ == "__main__":
# Define a express
f="1000=12x**2+25x"

# Individual code information
XINTSIZE = 9
XDECSIZE = 16

# Population information
POPULATION_SIZE = 100
CHILD_SIZE = 10
MAX_GENERATION_SIZE = 50
MUTATE_SIZE = 5
MUTATE_RATE = 0.05
CROSS_MERGE_RATE = 0.5

# visualization detail
X_RANGE = [-100,100]
Y_RANGE = [-500,6000]

# Print detail
DETAIL = False
PAUSE = True

# Create a population
numPopulation = Population(
popSize = POPULATION_SIZE,
childsSize = CHILD_SIZE,
maxGenerationSize = MAX_GENERATION_SIZE,
formulate=f,
)

numPopulation.live()

# visualization
if not DETAIL:
numPopulation.visualization()
else:
numPopulation.visualizationDetail()

print("-"*80)
best = numPopulation.species[0]
bestX = best.getDecimal()
bestTarget = numPopulation.getTarget(bestX)
print("Best x = %.3f"%bestX)
print("Best Target = %.3f"%bestTarget)
print("%.3f = %.3fx**2 + %.3fx"%(numPopulation.target,numPopulation.xCoef,numPopulation.yCoef))