新的南宁网站建设公司,苏州住房和城乡建设厅网站,一个朋友找我做网站该收多少钱,网站维护页面模版2024 遗传编程实战#xff08;一#xff09;基因实战 文章目录 2024 遗传编程实战#xff08;一#xff09;基因实战一、遗传编程实战介绍1、遗传编程简介2、遗传编程和进化论的关系3、遗传编程过程解释 二、基于遗传编程的例子1、实战题目介绍2、遗传算法的伪代码3、遗传实…2024 遗传编程实战一基因实战 文章目录 2024 遗传编程实战一基因实战一、遗传编程实战介绍1、遗传编程简介2、遗传编程和进化论的关系3、遗传编程过程解释 二、基于遗传编程的例子1、实战题目介绍2、遗传算法的伪代码3、遗传实战具体代码与详细注释4、将以上纯python运算实现代码套入DEAP强化学习框架实现 一、遗传编程实战介绍
1、遗传编程简介
什么是遗传编程算法和传统机器学习算法有什么区别 传统上我们接触的机器学习算法都是被设计为解决某一个某一类问题的确定性算法。对于这些机器学习算法来说唯一的灵活性体现在参数搜索空间上向算法输入样本算法借助不同的优化手段对参数进行调整以此来得到一个对训练样本和测试样本的最佳适配参数组。
遗传编程算法完全走了另一外一条路遗传编程算法的目标是编写一个程度这个程序会尝试自动构造出解决某一问题的最佳程度。从本质上看遗传编程算法构造的是一个能够构造算法的算法。
另一方面我们曾经讨论过遗传算法遗传算法是一种优化技术就优化技术而言无论是何种形式的优化算法或度量都是预先设定好的而优化算法所做的工作就是尝试为其找到最佳参数。和优化算法一样遗传编程也需要一种方法来度量题解的优劣程度。但与优化算法不同的是遗传编程中的题解并不仅仅是一组用于给定算法的参数相反在遗传编程中连同算法本身及其所有参数都是需要搜索确定的。
从某种程度上来说遗传编程和遗传算法的区别在于进化的基本单位不同
遗传优化进化的基本单位是模型可变参数遗传编程进化的基本单位是新算法以及新算法的参数
2、遗传编程和进化论的关系
遗传算法是受达尔文的进化论的启发借鉴生物进化过程而提出的一种启发式搜索算法因此遗传算法 ( GA , Genetic Algorithm ) 也称进化算法 。 因此在讨论遗传编程的时候会大量借用进化论中的术语和概念为了更好地讨论遗传算法我们先介绍一些基本生物进化概念
基因 ( Gene )一个遗传因子种群中的最基本单元。染色体 ( Chromosome )一组的基因。交叉Crossover和变异Mutation 交叉父母染色体将部分基因随机传下一代并保证子代的基因数与上一代一致。变异子代的某一个基因发生随机变异。 个体 ( individual )单个生物。在遗传算法中个体一般只包含一条染色体。种群 ( Population )由个体组成的群体。生物的进化以种群的形式进化。适者生存 ( The survival of the fittest )对环境适应度高的个体参与繁殖的机会比较多后代就会越来越多。适应度低的个体参与繁殖的机会比较少后代就会越来越少。
生物所处的环境起到一个提供生存压的作用反馈虽然纵观整个地球历史环境的因素是在不断变化的有时甚至变化的还很快但是在某个时间段内例如5000年内是基本保持不变的而物种进化的目的就是通过一代代的繁衍逐渐适应拟合当前的环境并和其他物种达到最优平衡纳什均衡。
3、遗传编程过程解释
遗传编程算法就是模拟了生物进化的过程简单说来说 生物进化的环境由一个用户定义的任务user-defined task所决定算法由一组初始的题解程序开始展开竞争。这里所谓的任务可以是多种形式 一种竞赛game各个题解程序在竞赛中直接展开竞争个体测试测出哪个题解程序的执行效果更好 遗传算法将基因抽象为题解中最小的随机变量因子例如模型中的可变参数 一个问题的解由很多这样的随机变化因子组成算法将问题的解编码成个体的染色体染色体是基因的集合 单个个体包含若干个染色体个体包含的染色体题解越多和越好则个体的适应度就越好。在实际工程中为了简化算法常常假设一个个体只有一条染色体 多个个体组成种群种群中适应度Fitness高的个体获得较高概率的繁殖机会从而导致适应度高的个体会越来越多经过N代的自然选择后保存下来的个体都是适应度很高的 繁殖过程中算法会评估并挑选出本轮表现最好的一部分题解题解程序并对程序的某些部分以**随机一定概率**的方式进行修改包括 基因交叉Acrossover在最优题解之间挑选部分随机变量因子进行彼此互换。遗传算法交叉比人体内染色体交叉要简单许多。遗传算法的染色体是单倍体而人体内的真正的染色体是双倍体。下图是遗传算法中两条染色体在中间进行交叉的示意图 基因突变Mutation在最优题解上直接对某些随机变量因子基因位进行随机修改。下图是遗传算法中一条染色体在第二位发生基因变异的示意图 经过繁殖过程新的种群即新的一组解产生称为“下一代”理论上这些新的题解基于原来的最优程序但又不同于它们。这些新产生的题解和旧的最优题解会一起进入下一轮自然选择阶段 上述繁殖过程重复多次直到达到收敛条件包括找到了全局最优解找到了表现足够好的解 题解在历经数代之后都没有得到任何改善繁衍的代数达到了规定的限制 最终历史上适应度最高个体所包含的解作为遗传算法的输出。
二、基于遗传编程的例子
1、实战题目介绍
在一个长度为n的数组nums中选择10个元素使得10个元素的和与原数组的所有元素之和的1/10无限接近。
2、遗传算法的伪代码
BEGIN:i 0; //进化种群的代数Initialize P(i) //初始化种群While(not Terminate - Condition)//不满足终止条件时继续循环{Fitness(i) // 计算适宜度GA-Operation P(i)//交叉、变异操作Fitness(i) // 计算适宜度Selection(P) //物竞天择、适者生存。适应度低的死亡}
EMD //结束3、遗传实战具体代码与详细注释
未来的大佬请上座下面是依据这个伪代码撰写的遗传实战轮子代码
import random
import math
# 定义问题参数
total_numbers 100 # 种群的基因上下限 人类基因组
Generange1000 # 种群基因的取值范围 理论上全部物种的基因范围
selected_numbers 10 # 一个个体占据的基因 一个人的全部基因 20000~25000
pop_size100 # 这个种群的个体个数 一个人群的人数
terminder10 # 进化的终点 进化到什么程度结束# 生成初始种群与种群基因组
def generate_population():population []HumanGene random.sample(range(Generange),100) # 从全部基因取值范围里面选取100个做为这个种群的基因取值范围for _ in range(pop_size):# 从种群的基因取值范围里面选取10个基因做为一个个体的全部基因组成individual random.sample(HumanGene, selected_numbers)population.append(individual)return population,HumanGene# 计算个体的适应度
def fitness(individual,HumanGene):#sum_selected sum(individual)sum_total sum(HumanGene)diff abs(sum_selected - sum_total / 10)return 10 / (diff 1) # diff越小权重越大# 选择优秀个体,将后面的一半淘汰掉
def selection(population, fitness_values):selected random.choices(population, weightsfitness_values, ktotal_numbers)return selected# 两个人交配并生两娃的操作
def crossover(parent1, parent2):# pivot是染色体杂交的位点pivot random.randint(1, selected_numbers - 1)child1 parent1[:pivot] parent2[pivot:]child2 parent2[:pivot] parent1[pivot:]return child1, child2# 个体变异操作
def mutate(individual,HumanGene):# 确定那个位置变异mutated_index random.randint(0, selected_numbers - 1)individual[mutated_index] random.sample(HumanGene,1)[0]return individual# 遗传编程主函数
def genetic_algorithm( generations):# 生成种群100population ,HumanGene generate_population()for _ in range(generations):# 适宜度计算fitness_values [fitness(individual,HumanGene) for individual in population]# 选择、交配、变异new_population population.copy()for _ in range(pop_size//2):# 从人群中依据适宜度做为权重权重越高选择中的概率就越高# 选两个出来交配生下两娃parent1, parent2 random.choices(population, k2, weightsfitness_values)child1, child2 crossover(parent1, parent2)# 让下一代概率性变异if random.random() 0.1:child1 mutate(child1,HumanGene)if random.random() 0.1:child2 mutate(child2,HumanGene)# 将孩子插入到新的种群中new_population.extend([child1, child2])# 重新计算群体的适宜度然后再依据适宜度进行淘汰fitness_values[fitness(ind,HumanGene) for ind in new_population] #population selection(new_population, fitness_values)# 依据适宜度返回最佳的个体best_individual max(population, keylambda x:fitness(x,HumanGene))return population,HumanGene,best_individual# 运行遗传编程
population,HumanGene,best_solution genetic_algorithm(generations1000)
print(最终的种群str(population))
print(种群的基因组str(HumanGene))print(基因组的和str(sum(HumanGene)))
print(最佳解决方案:{},解决方案的和{}.format(str(best_solution),sum(best_solution)))
print(从基因组中抽出的10个值的和近乎是整个基因组的和的十分之一差str(abs(sum(HumanGene)//10-sum(best_solution))))运行结果
4、将以上纯python运算实现代码套入DEAP强化学习框架实现
DEAP是目前强化学习主流使用的框架可以看到在这个框架的支持下结构和代码量都减少了许多并且也有了更多的可视化过程。 解决问题在一个长度为n的数组nums中选择10个元素使得10个元素的和与原数组的所有元素之和的1/10无限接近。 具体代码如下
import random
from deap import base, creator, tools, algorithms# 定义问题参数
total_numbers 100 # 种群的基因上下限 人类基因组
Generange1000 # 种群基因的取值范围 理论上全部物种的基因范围
selected_numbers 10 # 一个个体占据的基因 一个人的全部基因 20000~25000
pop_size100 # 这个种群的个体个数 一个人群的人数
terminder10 # 进化的终点 进化到什么程度结束nums [random.randint(1, Generange) for _ in range(100)] # 生成一个长度为100的随机数组
target_sum sum(nums) / 10 # 目标和为原数组所有元素之和的1/10# 创建遗传算法所需的工具个体类、种群类、目标函数、交叉函数、变异函数等
# 一、定义问题,是最小化问题还是最大化
creator.create(FitnessMin, base.Fitness, weights(-1.0,)) # 目标是最小化目标函数
creator.create(Individual, list, fitnesscreator.FitnessMin)# 二、生成个体
IND_SIZE 10 # 个体大小即选择的元素数量
toolbox base.Toolbox()
toolbox.register(indices, random.sample, range(len(nums)), IND_SIZE)
toolbox.register(individual, tools.initIterate, creator.Individual, toolbox.indices)
# 三、生成初始种群
toolbox.register(population, tools.initRepeat, list, toolbox.individual)
pop toolbox.population(n300) # 种群大小# 四、定义遗传算子评估函数、交叉函数、变异函数、选择函数
def evalSolution(individual):评价函数计算个体与目标和的差的绝对值return (abs(sum(nums[i] for i in individual) - target_sum),)toolbox.register(evaluate, evalSolution) # 评价个体的适应度的函数由于权重是最小化所以越小适应度越高。
toolbox.register(mate, tools.cxTwoPoint) # 使用两点交叉
toolbox.register(mutate, tools.mutShuffleIndexes, indpb0.05) # 使用基因位置交换的方式变异
toolbox.register(select, tools.selTournament, tournsize3) # 使用锦标赛选择def main():random.seed(64)hof tools.HallOfFame(1) # 保留最佳个体stats tools.Statistics(lambda ind: ind.fitness.values) # 运行中间输出stats.register(avg, lambda x: sum(val[0] for val in x) / len(x))stats.register(min, min)stats.register(max, max)algorithms.eaSimple(pop, toolbox, cxpb0.5, mutpb0.2, ngen50,statsstats, halloffamehof, verboseTrue)return hof[0]if __name__ __main__:best main()print(Best individual is:, best)print(Sum of selected elements:, sum(nums[i] for i in best))print(Sum of Gene,sum(nums))运行过程
