【Python】遗传算法求解⼆元函数最值
序⾔
问题
好了，回到正题，这次要解决的问题是求解⼆元函数的最⼤值，该函数代码形式如下：
# 问题函数
# @param x x坐标
# @param y y坐标
# @return z 函数值
def problem_function(x, y):
return3*(1- x)**2* np.exp(-(x **2)-(y +1)**2)\
-10*(x /5- x **3- y **5)* np.exp(-x **2- y **2)\
-
1/3** np.exp(-(x +1)**2- y **2)
算法步骤
编码和解码
如果把函数的⼀个解当作个体，种即是若⼲个解的集合。对于⼈来说，我们习惯使⽤⼗进制数去计算解决问题，但在计算机中，操作的对象是⼆进制数，所以把⼗进制映射到⼆进制的过程，称为编码；把⼆进制映射到⼗进制的过程，称为解码。编码过程暂且省略，因为我们可以直接⽣成⼆进制矩阵：
# ⽣成随机种矩阵，这⾥DNA_SIZE * 2是因为种矩阵要拆分为x和y矩阵，单条DNA（染⾊体、个体）长度为24
# 若视x和y为等位基因，x和y组成染⾊体对，共同影响个体，这⾥巧妙地与遗传信息对应起来
population_matrix = np.random.randint(2, size=(POPULATION_SIZE, DNA_SIZE *2))
⽽解码的过程也并不陌⽣，回想你在学校时学到的进制转换，他们应该是相似的：
# 解码DNA个体
# @param population_matrix 种矩阵
# @return population_x_vector, population_y_vector 种x向量，种y向量
def decoding_DNA(population_matrix):
x_matrix = population_matrix[:,1::2]# 矩阵分割，⾏不变，抽取奇数列作为x矩阵
y_matrix = population_matrix[:,0::2]# 矩阵分割，⾏不变，抽取偶数列作为y矩阵
# 解码向量，⽤于⼆进制转⼗进制，其值为[2^23 2^22 ... 2^1 2^0]，对位相乘累加，⼆进制转⼗进制的基础⽅法
decoding_vector =2** np.arange(DNA_SIZE)[::-1]
# 种x向量，由⼆进制转换成⼗进制并映射到x区间
population_x_vector = x_matrix.dot(decoding_vector)/(2** DNA_SIZE -1)\
*(X_RANGE[1]- X_RANGE[0])+ X_RANGE[0]
# 种y向量，由⼆进制转换成⼗进制并映射到y区间
population_y_vector = y_matrix.dot(decoding_vector)/(2** DNA_SIZE -1)\
*(Y_RANGE[1]- Y_RANGE[0])+ Y_RANGE[0]
return population_x_vector, population_y_vector
交叉和变异
了解了编码解码，你已经可以获得便捷操作⼆进制的能⼒，如同装备了⽚⼿剑，你才有信⼼接受怪物的毒打，哦，我是说，你拥有了击败恶龙的可能。让我们进⼊到遗传算法更核⼼的部分，交叉和变异。
更接近本质⼀点，如果把⼀个解看作DNA（基因，染⾊体，个体，我知道他们的包含关系，这⾥不是严谨的⽐喻，只是为了⽤⽣物学相关的概念去类推算法的过程），在种更迭，遗传的过程中，⼀定概率下，基因会发⽣交叉和变异，我们需要模拟的就是这个过程。孩⼦的基因除了来⾃⽗亲，还有部分通过交叉获得的母亲的基因，这⾥的⽗母只是⼀个区别性描述，你可以随意倒换。那么我们就可以操纵代码执⾏交叉操作：
# DNA交叉
# @param child_DNA 孩⼦DNA
# @param population_matrix 种矩阵
def DNA_cross(child_DNA, population_matrix):
# 概率发⽣DNA交叉
if np.random.rand()< CROSS_RATE:
mother_DNA = population_matrix[np.random.randint(POPULATION_SIZE)]# 种中随机选择⼀个个体作为母亲
cross_position = np.random.randint(DNA_SIZE *2)# 随机选取交叉位置
child_DNA[cross_position:]= mother_DNA[cross_position:]# 孩⼦获得交叉位置处母亲基因
变异是对DNA的不稳定复制，也就是说，他是DNA⾃⾝的改变，同时它发⽣的概率极低，变异可能往好的或坏的⽅向发展，但总是不尽如⼈意，我们也可以模拟这个过程：
# DNA变异
# @param child_DNA 孩⼦DNA
def DNA_variation(child_DNA):
# 概率发⽣DNA变异
if np.random.rand()< VARIATION_RATE:
variation_position = np.random.randint(DNA_SIZE *2)# 随机选取变异位置
child_DNA[variation_position]= child_DNA[variation_position]^1# 异或门反转⼆进制位
⾃然选择
交叉和变异是遗传中种的⾃我迭代，但是，不能忘了环境的选择作⽤，否则，进化将朝着随机的⽅向不稳定地进⾏，所谓“适者⽣存”，环境的选择使种朝特定的⽅向演化，回到问题中来，这样的选择作⽤帮助我们⼀步步到最值的近似。
然⽽，怎么确定谁⾛谁留？这⾥，就需要提到适应度，它是环境选择个体的概率，该问题中，我们的适应度，其实就是接近最值的程度，越接近，留存的概率越⼤，其“优秀基因”也就越能流传下去，获取适应度过程如下：
# 获取适应度向量
# @param population_matrix 种矩阵
# @return fitness_vector 适应度向量
def get_fitness_vector(population_matrix):
population_x_vector, population_y_vector = decoding_DNA(population_matrix)# 获取种x和y向量
fitness_vector = problem_function(population_x_vector, population_y_vector)# 获取适应度向量
fitness_vector = fitness_vector - np.min(fitness_vector)+1e-3# 适应度修正，保证适应度⼤于0
return fitness_vector
知道了适应度，接下来要做的事情就很明显了，即⽆情的⾃然选择，说⽆情亦有情，它既不顾个体情感，唯适应度选择，⼜留有⼀线⽣机，不绝对否定或绝对肯定，⼀切都是概率。接下来就是⽆保底抽卡时刻：
# ⾃然选择
# @param population_matrix 种矩阵
# @param fitness_vector 适应度向量
# @return population_matrix[index_array] 选择后的种
def natural_selection(population_matrix, fitness_vector):
index_array = np.random.choice(np.arange(POPULATION_SIZE),# 被选取的索引数组
size=POPULATION_SIZE,# 选取数量
replace=True,# 允许重复选取
p=fitness_vector / fitness_vector.sum())# 数组每个元素的获取概率
return population_matrix[index_array]
⾄此，我们已经完成了种的⼀次完整迭代，剩下的就是重复这个过程不断优化种，我们迭代次数越多，结果越准确，当然不可能永远迭代下去，那样即使得出完美答案也没有了意义，为平衡时间代价和准确度，通常我们选取⼀个合适的迭代值，如50，100。
结果
初始状态：
迭代过程：
结果：
最佳适应度为： 8.142268067060922
最优基因型为： [1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 0 0 1 1 1 0 0
0 1 0 0 0 1 0 1 1 0 0]
最优基因型⼗进制表⽰为： (0.0029763581142638884, 1.5702061993006584)
源码
import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
DNA_SIZE =24# 个体编码长度
POPULATION_SIZE =200# 种⼤⼩
GENERATION_NUMBER =50# 世代数⽬
CROSS_RATE =0.8# 交叉率
VARIATION_RATE =0.01# 变异率
X_RANGE =[-3,3]# X范围
Y_RANGE =[-3,3]# Y范围
# 问题函数
# @param x x坐标
# @param y y坐标
# @return z 函数值
def problem_function(x, y):
return3*(1- x)**2* np.exp(-(x **2)-(y +1)**2)\
-10*(x /5- x **3- y **5)* np.exp(-x **2- y **2)\
-1/3** np.exp(-(x +1)**2- y **2)
# 初始化图
# @param ax 3D图像
def init_graph(ax):
x_sequence = np.linspace(*X_RANGE,100)# 创建x等差数列
y_sequence = np.linspace(*Y_RANGE,100)# 创建y等差数列
x_matrix, y_matrix = np.meshgrid(x_sequence, y_sequence)# ⽣成x和y的坐标矩阵
z_matrix = problem_function(x_matrix, y_matrix)# ⽣成z坐标矩阵
# 创建曲⾯图,⾏跨度为1，列跨度为1，设置颜⾊映射
ax.plot_surface(x_matrix, y_matrix, z_matrix, rstride=1, cstride=1, _cmap('coolwarm'))
ax.set_zlim(-10,10)# ⾃定义z轴范围
ax.set_xlabel('x')# 设置x坐标轴标题
ax.set_ylabel('y')# 设置y坐标轴标题
ax.set_zlabel('z')# 设置z坐标轴标题
plt.pause(3)# 暂停3秒
plt.show()# 显⽰图
# 解码DNA个体
# @param population_matrix 种矩阵
# @return population_x_vector, population_y_vector 种x向量，种y向量
def decoding_DNA(population_matrix):
x_matrix = population_matrix[:,1::2]# 矩阵分割，⾏不变，抽取奇数列作为x矩阵
y_matrix = population_matrix[:,0::2]# 矩阵分割，⾏不变，抽取偶数列作为y矩阵
# 解码向量，⽤于⼆进制转⼗进制，其值为[2^23 2^22 ... 2^1 2^0]，对位相乘累加，⼆进制转⼗进制的基础⽅法    decoding_vector =2** np.arange(DNA_SIZE)[::-1]
# 种x向量，由⼆进制转换成⼗进制并映射到x区间
population_x_vector = x_matrix.dot(decoding_vector)/(2** DNA_SIZE -1)\
*(X_RANGE[1]- X_RANGE[0])+ X_RANGE[0]
# 种y向量，由⼆进制转换成⼗进制并映射到y区间
population_y_vector = y_matrix.dot(decoding_vector)/(2** DNA_SIZE -1)\
*(Y_RANGE[1]- Y_RANGE[0])+ Y_RANGE[0]
return population_x_vector, population_y_vector
# DNA交叉
# @param child_DNA 孩⼦DNA
# @param population_matrix 种矩阵
def DNA_cross(child_DNA, population_matrix):
# 概率发⽣DNA交叉
if np.random.rand()< CROSS_RATE:
mother_DNA = population_matrix[np.random.randint(POPULATION_SIZE)]# 种中随机选择⼀个个体作为母亲        cross_position = np.random.randint(DNA_SIZE *2)# 随机选取交叉位置
child_DNA[cross_position:]= mother_DNA[cross_position:]# 孩⼦获得交叉位置处母亲基因
# DNA变异
# @param child_DNA 孩⼦DNA
def DNA_variation(child_DNA):
# 概率发⽣DNA变异
if np.random.rand()< VARIATION_RATE:
variation_position = np.random.randint(DNA_SIZE *2)# 随机选取变异位置
child_DNA[variation_position]= child_DNA[variation_position]^1# 异或门反转⼆进制位
# 更新种
# @param population_matrix 种矩阵
# @return new_population_matrix 更新后的种矩阵
def update_population(population_matrix):
new_population_matrix =[]# 声明新的空种
# 遍历种所有个体
for father_DNA in population_matrix:
child_DNA = father_DNA  # 孩⼦先得到⽗亲的全部DNA（染⾊体）
DNA_cross(child_DNA, population_matrix)# DNA交叉
DNA_variation(child_DNA)# DNA变异
new_population_matrix.append(child_DNA)# 添加到新种中
new_population_matrix = np.array(new_population_matrix)# 转化数组
return new_population_matrix
# 获取适应度向量
# @param population_matrix 种矩阵
# @return fitness_vector 适应度向量
def get_fitness_vector(population_matrix):
population_x_vector, population_y_vector = decoding_DNA(population_matrix)# 获取种x和y向量
fitness_vector = problem_function(population_x_vector, population_y_vector)# 获取适应度向量
fitness_vector = fitness_vector - np.min(fitness_vector)+1e-3# 适应度修正，保证适应度⼤于0
return fitness_vector
# ⾃然选择
# @param population_matrix 种矩阵
linspace函数python
# @param fitness_vector 适应度向量
# @return population_matrix[index_array] 选择后的种
def natural_selection(population_matrix, fitness_vector):
index_array = np.random.choice(np.arange(POPULATION_SIZE),# 被选取的索引数组
size=POPULATION_SIZE,# 选取数量
replace=True,# 允许重复选取
p=fitness_vector / fitness_vector.sum())# 数组每个元素的获取概率
return population_matrix[index_array]
# 打印结果
# @param population_matrix 种矩阵
def print_result(population_matrix):
fitness_vector = get_fitness_vector(population_matrix)# 获取适应度向量
optimal_fitness_index = np.argmax(fitness_vector)# 获取最⼤适应度索引
print('最佳适应度为：', fitness_vector[optimal_fitness_index])
print('最优基因型为：', population_matrix[optimal_fitness_index])
population_x_vector, population_y_vector = decoding_DNA(population_matrix)# 获取种x和y向量

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。