人工智能 遗传算法
题目
用遗传算法求解函数
20 + (x ^ 2) + (y ^ 2) - 10 * (cos(2 * π * x) + cos(2 * π * y)) (-5 < x, y <5)
的最小值
思路
分析问题，确定了至少需要两个类，即种群（Group）与个体（Individual）。同时为了稍微提高一点泛用性，还增加了一个函数（Function）类存放要求解的函数的相关信息。
class Group:
def __init__(self, group_size, mutation_rate, crossover_rate, dna_length, function):
'''
构造函数
:param group_size: 种群大小
:param mutation_rate: 变异率
:param crossover_rate: 交叉率
:param dna_length: DNA序列长度，即基因长度
:param function: 要求解的函数
'''
self.group_size = group_size
self.mutation_rate = mutation_rate
self.crossover_rate = crossover_rate
self.function = function
self.individuals = [] # 所有个体
self.best_individual = None # 最优个体
self.dna_length = dna_length
self.init_group()
class Individual:
def __init__(self, gene):
'''
构造函数
:param gene: 基因序列
'''
self.gene = gene
self.fit = 0 # 适应度
class Function:
def __init__(self, function, max_variable, min_variable, find_min=True):
'''
构造函数
:param function: 要求解的函数
:param max_variable: 函数自变量的最大值
:param min_variable: 函数自变量的最小值
:param find_min: 求最小值，默认为True，False即为求最大值
'''
self.function = function
self.max_variable = max_variable
self.min_variable = min_variable
self.find_min = find_min
首先需要构造一个种群，在构造函数为各种变量赋初值，然后进行初始化种群操作，即为种群中的所有个体创建基因序列
def generate_gene(self):
'''
生成一个基因序列
:return: 返回一个由0，1组成的序列
'''
gene = []
for i in range(self.dna_length):
gene.append(random.randint(0, 1))
return gene
def init_group(self):
'''
初始化种群的所有个体
'''
for i in range(self.group_size):
self.individuals.append(Individual.Individual(self.generate_gene()))
然后就要开始繁衍获得下一代
获得下一代需要经过以下两个步骤
- 产生孩子
种群中的每一个个体与种群中的另一个随机个体繁衍获得孩子。暂时先默认孩子接收父亲的基因。但是繁殖过程中孩子的基因可能发生交叉和变异。
交叉：从孩子的基因的一个随机位置开始，该位置后的基因变为母亲在同样位置之后的基因
变异：孩子的基因的某个随机位置取反
def crossover(self, father, mother):
'''
交叉
:param father: 父亲
:param mother: 母亲
:return: 孩子
'''
gene = [i for i in father.gene] # 首先默认孩子接收父亲的基因
child = Individual.Individual(gene) # 直接传入father.gene会导致更改child的基因时father的基因也会修改，种群基因变得不稳定
if self.crossover_rate > random.random(): # 判断是否发生交叉
cross_point = random.randint(1, self.dna_length - 1) # 交叉发生的位置
child.gene[cross_point:] = mother.gene[cross_point:] # 交叉位置后的基因变为母亲的基因
return child
def muter(self, individual):
'''
变异
:param individual: 可能变异的个体
:return: 变异之后的个体或原个体
'''
if self.mutation_rate > random.random(): # 判断是否变异
index = random.randint(0, self.dna_length - 1) # 变异的位置
individual.gene[index] = 1 - individual.gene[index] # 取反
return individual
def get_child(self, father, mother):
'''
产生一个孩子
:param father: 父亲
:param mother: 母亲
:return: 孩子
'''
child = self.crossover(father, mother)
child = self.muter(child)
return child
- 自然选择
此时的个体数已经变为原本的两倍，接下来要进行选择。选择适应度较高的一半个体存活。
首先计算所有个体的适应度
个体的适应度用函数的计算结果表示，但个体的基因是0，1组成的序列，无法直接带入到函数的自变量中求解，所以需要先把个体的基因转换成十进制的数字。
转换方式：- 将序列按权展开，得到对应的十进制数
- 十进制数除以序列长度的二进制数所能表示的最大值，此时得到的是0~1之间的小数，相当于一个比例系数
- 将小数乘以待求解函数自变量的取值范围的长度可以得到一个从0开始的在取值范围长度大小内的一个数
- 将得到的数加上取值范围的最小值就可以得到规定范围内的数
- 将基因序列的前一半作为x，后一半作为y，就可以代入函数求得结果作为适应度
def calculate_variable(self, x):
'''
将0，1序列转换成自变量值域内的一个十进制数
:param x: 要转换的序列
:return: 转换后的十进制数
'''
r = 0
for i in range(len(x)): # 序列的每一位
r += ((2 ** i) * x[i]) # 乘以权重
r /= ((2 ** len(x)) - 1) # 变成0~1之间的小数，相当于一个比例系数
r *= (self.function.max_variable - self.function.min_variable) + self.function.min_variable # 控制在函数自变量值域
return r
def set_fit(self, individual):
'''
求出适应度
:param individual: 要求的个体
'''
x = individual.gene[0:self.dna_length // 2 + 1] # 基因序列的前面一半代表x，后面一半代表y
y = individual.gene[self.dna_length // 2 + 1:]
x = self.calculate_variable(x) # 计算x，y对应的十进制数值
y = self.calculate_variable(y)
r = self.function.function(x, y) # 计算适应度
individual.fit = r
求得适应度之后进行排序
若要求计算最小值，则将所有个体按适应度升序排列；若要求计算最大值，则按适应度降序排列。排序之后，越前面的个体就是越符合要求的个体，此时只要选择前面一半个体作为新一代个体即可。
这种方法较为简单，并且可以保证最优秀的个体一定可以被保留下来。但是自然界中最优秀的个体却不一定能保留下来。若想模拟自然界的自然选择，就需要改进选择的方式。可以选择轮盘赌等方法。
def select_next_generation(self):
'''
选择合适的下一代
:return: 下一代
'''
for i in range(len(self.individuals)): # 计算所有个体的适应度，应注意此时个体数量已经是种群大小的两倍
self.set_fit(self.individuals[i])
self.individuals.sort(key=lambda individual: individual.fit, reverse=not self.function.find_min) # 按适应度排列
self.best_individual = self.individuals[0] # 排在越前的个体越符合要求
new_individuals = self.individuals[0:self.group_size] # 选择种群大小数量的个体
return new_individuals
将以上两个步骤链接起来，就可以得到获取下一代的方法
def get_next_generation(self):
'''
获取下一代
'''
next_generation = []
for i in range(self.group_size): # 每个个体与一个随机个体繁衍
father = self.individuals[i]
mother = self.individuals[random.randint(0, self.group_size - 1)]
child = self.get_child(father, mother)
next_generation.append(child)
self.individuals += next_generation # 此时的种群数量已经变为两倍
self.individuals = self.select_next_generation() # 选择出其中更符合要求的一半群体
输出每一代最优秀个体的信息
def print_best_individual_info(self):
'''
打印相关信息
'''
x = self.best_individual.gene[0:self.dna_length // 2 + 1]
y = self.best_individual.gene[self.dna_length // 2 + 1:]
x = self.calculate_variable(x)
y = self.calculate_variable(y)
print("x:", x, " y:", y, " 结果：", self.best_individual.fit)
将所有方法联合起来，提供一个对外接口
def start_evolution(self, generation):
'''
开始繁衍进化
:param generation: 要繁衍的代数
'''
for i in range(generation):
print("第", i + 1, "代最优个体", end="\t")
self.get_next_generation()
self.print_best_individual_info()
结果
开始测试
首先定义要求解的函数，作为参数构造一个函数类的对象，并设定最大值为5，最小值为-5，要求其最小值
然后定义一个种群，种群大小300，变异率0.05，交叉率0.8，个体的基因序列长度128，要求解的函数即为前一步创建的函数对象
注意序列长度如果太短反而会很快收敛到0，但这只是因为结果恰巧为0。如果是要求解最大值，那么基因序列太短精度就会非常差。
进行100代繁衍进化
def function(x, y): # 要求解的函数
return 20 + (x ** 2) + (y ** 2) - 10 * (math.cos(2 * math.pi * x) + math.cos(2 * math.pi * y))
if __name__ == '__main__':
func = Function.Function(function, 5, -5, find_min=True) # 求function的最小值，自变量范围-5~5
group = Group.Group(300, 0.05, 0.8, 128, func) # 基因长度取太短会很快收敛到0，但这是凑巧答案为0，如果改成求最大值精度就很低
group.start_evolution(100)
下面尝试求解最大值，并对比不同基因序列长度的精度
求最大值只需将find_min的值改为False即可
def function(x, y): # 要求解的函数
return 20 + (x ** 2) + (y ** 2) - 10 * (math.cos(2 * math.pi * x) + math.cos(2 * math.pi * y))
if __name__ == '__main__':
func = Function.Function(function, 5, -5, find_min=False) # 求function的最小值，自变量范围-5~5
group = Group.Group(300, 0.05, 0.8, 128, func) # 基因长度取太短会很快收敛到0，但这是凑巧答案为0，如果改成求最大值精度就很低
group.start_evolution(100)
序列长度为8
序列长度为16
序列长度为64
序列长度为128
完整代码
# Group.py
import random
import Individual
class Group:
def __init__(self, group_size, mutation_rate, crossover_rate, dna_length, function):
'''
构造函数
:param group_size: 种群大小
:param mutation_rate: 变异率
:param crossover_rate: 交叉率
:param dna_length: DNA序列长度，即基因长度
:param function: 要求解的函数
'''
self.group_size = group_size
self.mutation_rate = mutation_rate
self.crossover_rate = crossover_rate
self.function = function
self.individuals = [] # 所有个体
self.best_individual = None # 最优个体
self.dna_length = dna_length
self.init_group()
def generate_gene(self):
'''
生成一个基因序列
:return: 返回一个由0，1组成的序列
'''
gene = []
for i in range(self.dna_length):
gene.append(random.randint(0, 1))
return gene
def init_group(self):
'''
初始化种群的所有个体
'''
for i in range(self.group_size):
self.individuals.append(Individual.Individual(self.generate_gene()))
def crossover(self, father, mother):
'''
交叉
:param father: 父亲
:param mother: 母亲
:return: 孩子
'''
gene = [i for i in father.gene] # 首先默认孩子接收父亲的基因
child = Individual.Individual(gene) # 直接传入father.gene会导致更改child的基因时father的基因也会修改，种群基因变得不稳定
if self.crossover_rate > random.random(): # 判断是否发生交叉
cross_point = random.randint(1, self.dna_length - 1) # 交叉发生的位置
child.gene[cross_point:] = mother.gene[cross_point:] # 交叉位置后的基因变为母亲的基因
return child
def muter(self, individual):
'''
变异
:param individual: 可能变异的个体
:return: 变异之后的个体或原个体
'''
if self.mutation_rate > random.random(): # 判断是否变异
index = random.randint(0, self.dna_length - 1) # 变异的位置
individual.gene[index] = 1 - individual.gene[index] # 取反
return individual
def get_child(self, father, mother):
'''
产生一个孩子
:param father: 父亲
:param mother: 母亲
:return: 孩子
'''
child = self.crossover(father, mother)
child = self.muter(child)
return child
def calculate_variable(self, x):
'''
将0，1序列转换成自变量值域内的一个十进制数
:param x: 要转换的序列
:return: 转换后的十进制数
'''
r = 0
for i in range(len(x)): # 序列的每一位
r += ((2 ** i) * x[i]) # 乘以权重
r /= ((2 ** len(x)) - 1) # 变成0~1之间的小数，相当于一个比例系数
r *= (self.function.max_variable - self.function.min_variable) + self.function.min_variable # 控制在函数自变量值域
return r
def set_fit(self, individual):
'''
求出适应度
:param individual: 要求的个体
'''
x = individual.gene[0:self.dna_length // 2 + 1] # 基因序列的前面一半代表x，后面一半代表y
y = individual.gene[self.dna_length // 2 + 1:]
x = self.calculate_variable(x) # 计算x，y对应的十进制数值
y = self.calculate_variable(y)
r = self.function.function(x, y) # 计算适应度
individual.fit = r
def select_next_generation(self):
'''
选择合适的下一代
:return: 下一代
'''
for i in range(len(self.individuals)): # 计算所有个体的适应度，应注意此时个体数量已经是种群大小的两倍
self.set_fit(self.individuals[i])
self.individuals.sort(key=lambda individual: individual.fit, reverse=not self.function.find_min) # 按适应度排列
self.best_individual = self.individuals[0] # 排在越前的个体越符合要求
new_individuals = self.individuals[0:self.group_size] # 选择种群大小数量的个体
return new_individuals
def get_next_generation(self):
'''
获取下一代
'''
next_generation = []
for i in range(self.group_size): # 每个个体与一个随机个体繁衍
father = self.individuals[i]
mother = self.individuals[random.randint(0, self.group_size - 1)]
child = self.get_child(father, mother)
next_generation.append(child)
self.individuals += next_generation # 此时的种群数量已经变为两倍
self.individuals = self.select_next_generation() # 选择出其中更符合要求的一半群体
def print_best_individual_info(self):
'''
打印相关信息
'''
x = self.best_individual.gene[0:self.dna_length // 2 + 1]
y = self.best_individual.gene[self.dna_length // 2 + 1:]
x = self.calculate_variable(x)
y = self.calculate_variable(y)
print("x:", x, " y:", y, " 结果：", self.best_individual.fit)
def start_evolution(self, generation):
'''
开始繁衍进化
:param generation: 要繁衍的代数
'''
for i in range(generation):
print("第", i + 1, "代最优个体", end="\t")
self.get_next_generation()
self.print_best_individual_info()
# Individual.py
class Individual:
def __init__(self, gene):
'''
构造函数
:param gene: 基因序列
'''
self.gene = gene
self.fit = 0 # 适应度
# Function.py
class Function:
def __init__(self, function, max_variable, min_variable, find_min=True):
'''
构造函数
:param function: 要求解的函数
:param max_variable: 函数自变量的最大值
:param min_variable: 函数自变量的最小值
:param find_min: 求最小值，默认为True，False即为求最大值
'''
self.function = function
self.max_variable = max_variable
self.min_variable = min_variable
self.find_min = find_min
# main.py
import Group
import Function
import math
def function(x, y): # 要求解的函数
return 20 + (x ** 2) + (y ** 2) - 10 * (math.cos(2 * math.pi * x) + math.cos(2 * math.pi * y))
if __name__ == '__main__':
func = Function.Function(function, 5, -5, find_min=True) # 求function的最小值，自变量范围-5~5
group = Group.Group(300, 0.05, 0.8, 128, func) # 基因长度取太短会很快收敛到0，但这是凑巧答案为0，如果改成求最大值精度就很低
group.start_evolution(100)
参考资料
https://blog.csdn/weixin_43666945/article/details/90287775
https://blog.csdn/ha_ha_ha233/article/details/91364937
更多推荐
人工智能 遗传算法
发布评论