Genetic Algorithm遗传算法整理

2024-08-22 17:58

本文主要是介绍Genetic Algorithm遗传算法整理,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

      • 一、简介
      • 二、算法流程
      • 三、参数
      • 四、代码
      • 五、参考资料

一、简介

遗传算法(Genetic Algorithm, GA)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。

遗传算法以一种群体中的所有个体为对象,并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中,选择、交叉和变异构成了遗传算法的遗传操作;参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。

二、算法流程

遗传算法和自然选择的过程类似,在种群里面进行繁衍,产生的下一代加入种群,并根据一定的条件淘汰掉部分个体,保持种群个数一定,然后继续下一个循环,当循环次数达到界限或者种群中出现满足要求的个体,停止循环。

遗传算法的过程如下:
在这里插入图片描述
我们以数据集的特征选择为例,讲一下里面的一些专有名词。

  • 参数编码:一般二进制编码用的稍微多一些,0表示特征没有被选择,1表示特征被选择,一个解决方案会形成一个 1 ∗ n 1*n 1n的数组,其中n是数据集的特征数;
    在这里插入图片描述

  • 适应度函数(fitness function):用于评价当前个体(特征选择的方案)对环境的适应度(性能),用于在繁殖之后淘汰掉部分个体;

  • 选择操作:从种群中选择用于繁衍的双亲,选择的方法是轮盘赌(Roulette Wheel Selection)或者轮盘赌的变体。

  • 交叉(crossover)操作:类似于染色体交换基因,如果使用二进制编码,会有三种操作模式:(1)单点交叉(single):比如用于繁衍的双亲是A和B,并且数据集有20个特征,那么在数组里随机选择一个断点,A的前半段和B的后半段组成下一代C,A的后半段和B的前半段组成下一代D;(2)多点交叉:和单点交叉类似,多个断点;(3)均匀交叉(也称一致交叉,uniform):两个配对个体的每个基因座上的基因都以相同的交叉概率进行交换,从而形成两个新个体;

  • 变异(mutation)操作:以特征选择为例,20个特征会形成一个 1 ∗ n 1*n 1n的数组,部分1的突变为0,部分0的突变为1;

在这里插入图片描述

百度百科对轮盘赌(Roulette Wheel Selection)的解释比较清晰,示例如下:
在这里插入图片描述
若产生随机数为0.81,则6号个体被选中。

之前给同学讲这个算法的时候,讲了一个故事辅助理解。羊群共有30只羊(初始化个体数pop_size),40只羊交配产生20只羊(40*0.5, c r o s s − r a t e ∗ p o p − s i z e cross_-rate*pop_-size crossratepopsize),新产生的20只羊,每个都有可能突变(突变率),最后的60只羊根据适者生存,保留40只,重复这个过程就能选出40只适应能力特别强的羊。

三、参数

遗传算法里面一般有以下参数:

  • 迭代次数:算法结束的标准;
  • 初始种群个体个数:有多少个方案可供选择。如果太多,算法运行时间比较长;太少不一定能选出最好的结果;
  • 交叉率:用于确定下一代的个数, c r o s s − r a t e ∗ p o p − s i z e = n u m − n e w − s o l u t i o n cross_-rate*pop_-size=num_-new_-solution crossratepopsize=numnewsolution
  • 突变率:主要是确定下一代个体是否产生突变,一般随机产生一个0-1之间的数和突变率比较,决定是否突变;

总结:遗传算法好坏初始种群的选择有很大关系,不一定能够找到最佳方案。

四、代码

代码可以看这篇博客遗传算法详解 附python代码实现

这篇博客在产生后代后,筛选种群并不是完全按照适应度大小选择的,为了陷入局部最优,按照“适应度越高,被选择的机会越高,而适应度低的,被选择的机会就低”的原则进行了折中处理:

def select(pop, fitness):    # nature selection wrt pop's fitnessidx = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, replace=True,p=(fitness)/(fitness.sum()) )return pop[idx]

这个对我的启发比较大。

五、参考资料

【算法】超详细的遗传算法(Genetic Algorithm)解析
百度百科–Roulette Wheel Selection
百度百科–遗传算法
利用 Python 实现 遗传算法(GeneticAlgorithm)

这篇关于Genetic Algorithm遗传算法整理的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1096985

相关文章

Python自动化批量重命名与整理文件系统

《Python自动化批量重命名与整理文件系统》这篇文章主要为大家详细介绍了如何使用Python实现一个强大的文件批量重命名与整理工具,帮助开发者自动化这一繁琐过程,有需要的小伙伴可以了解下... 目录简介环境准备项目功能概述代码详细解析1. 导入必要的库2. 配置参数设置3. 创建日志系统4. 安全文件名处

MySQL 迁移至 Doris 最佳实践方案(最新整理)

《MySQL迁移至Doris最佳实践方案(最新整理)》本文将深入剖析三种经过实践验证的MySQL迁移至Doris的最佳方案,涵盖全量迁移、增量同步、混合迁移以及基于CDC(ChangeData... 目录一、China编程JDBC Catalog 联邦查询方案(适合跨库实时查询)1. 方案概述2. 环境要求3.

SpringSecurity整合redission序列化问题小结(最新整理)

《SpringSecurity整合redission序列化问题小结(最新整理)》文章详解SpringSecurity整合Redisson时的序列化问题,指出需排除官方Jackson依赖,通过自定义反序... 目录1. 前言2. Redission配置2.1 RedissonProperties2.2 Red

MySQL 多列 IN 查询之语法、性能与实战技巧(最新整理)

《MySQL多列IN查询之语法、性能与实战技巧(最新整理)》本文详解MySQL多列IN查询,对比传统OR写法,强调其简洁高效,适合批量匹配复合键,通过联合索引、分批次优化提升性能,兼容多种数据库... 目录一、基础语法:多列 IN 的两种写法1. 直接值列表2. 子查询二、对比传统 OR 的写法三、性能分析

Javaee多线程之进程和线程之间的区别和联系(最新整理)

《Javaee多线程之进程和线程之间的区别和联系(最新整理)》进程是资源分配单位,线程是调度执行单位,共享资源更高效,创建线程五种方式:继承Thread、Runnable接口、匿名类、lambda,r... 目录进程和线程进程线程进程和线程的区别创建线程的五种写法继承Thread,重写run实现Runnab

Spring IoC 容器的使用详解(最新整理)

《SpringIoC容器的使用详解(最新整理)》文章介绍了Spring框架中的应用分层思想与IoC容器原理,通过分层解耦业务逻辑、数据访问等模块,IoC容器利用@Component注解管理Bean... 目录1. 应用分层2. IoC 的介绍3. IoC 容器的使用3.1. bean 的存储3.2. 方法注

MySQL 删除数据详解(最新整理)

《MySQL删除数据详解(最新整理)》:本文主要介绍MySQL删除数据的相关知识,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、前言二、mysql 中的三种删除方式1.DELETE语句✅ 基本语法: 示例:2.TRUNCATE语句✅ 基本语

Python变量与数据类型全解析(最新整理)

《Python变量与数据类型全解析(最新整理)》文章介绍Python变量作为数据载体,命名需遵循字母数字下划线规则,不可数字开头,大小写敏感,避免关键字,本文给大家介绍Python变量与数据类型全解析... 目录1、变量变量命名规范python数据类型1、基本数据类型数值类型(Number):布尔类型(bo

MyBatis Plus 中 update_time 字段自动填充失效的原因分析及解决方案(最新整理)

《MyBatisPlus中update_time字段自动填充失效的原因分析及解决方案(最新整理)》在使用MyBatisPlus时,通常我们会在数据库表中设置create_time和update... 目录前言一、问题现象二、原因分析三、总结:常见原因与解决方法对照表四、推荐写法前言在使用 MyBATis

MySQL复杂SQL之多表联查/子查询详细介绍(最新整理)

《MySQL复杂SQL之多表联查/子查询详细介绍(最新整理)》掌握多表联查(INNERJOIN,LEFTJOIN,RIGHTJOIN,FULLJOIN)和子查询(标量、列、行、表子查询、相关/非相关、... 目录第一部分:多表联查 (JOIN Operations)1. 连接的类型 (JOIN Types)