【优化算法】Python实现面向对象的遗传算法

遗传算法

遗传算法(Genetic Algorithm)属于智能优化算法的一种,本质上是模拟自然界中种群的演化来寻求问题的最优解。与之相似的还有模拟退火、粒子群、蚁群等算法。

在具体介绍遗传算法之前,我们先来了解一些知识🧀

DNA: 携带有合成RNA和蛋白质所必需的遗传信息的生物大分子,是生物体发育和正常运作必不可少的生物大分子。一般情况下,是以双螺旋结构存在。

现实中的DNA由碱基、脱氧核糖和磷酸双分子层组成,两条脱氧核苷酸链通过碱基间的氢键形成的碱基对相连,形成稳定的结构。碱基由四种,腺嘌呤,鸟嘌呤,胸腺嘧啶,胞嘧啶。

那么如何在计算机中对DNA进行编码?也不需要想的过于复杂,我们只需要表达每个位置上的碱基就行啦!譬如,一条DNA链可以写作:012332100123;每个数字对应一个碱基的映射。为了提高运行速度,我们将其以二进制的形式进行简化表达,即一条DNA链可以看做一串二进制文本:01011101010

个体与种群

我们将每条DNA链看做一个个体,实际上,也就是问题的一个解。譬如,我们寻找映射 F ( X , Y ) F(X,Y) F(X,Y)的最优解,其中一个可能的值 X = 6 X=6 X=6,便是一个个体。

种群就是个体的集合。注意,同一种群内部发生信息交换,不同种群之间不会发生信息交换。例如, X X X的全集不会与 Y Y Y的全集发生交换,DNA交换只会发生在 X X X集合或 Y Y Y集合内部。

遗传: 生物的DNA来自于父母,一般情况下由父亲提供X或Y染色体,母亲提供X染色体

假设现在有两个个体:

1001 0001 1001\ 0001 1001 0001 00011001 0001 1001 00011001 分别作为父亲和母亲,生下了一个新的个体,那么该个体的DNA将由父亲和母亲来决定,例如前四位由父亲提供,后四位由母亲提供,那么该子代个体就是:

1001 1001 1001\ 1001 1001 1001

变异: 在DNA的某个位置发生了变化

因为是二进制表达的DNA,那么所谓的变化就是某一位由0到1,或是由1到0

自然选择: 优胜劣汰,将会选择更加适宜的个体

个体的适宜度,实际上也就是满足函数最优解的值。适宜度越高,该个体在下一轮的自然选择中越容易存活,从而保留自身的DNA。


下面我们将来说一下如何实现一个GA算法~

一、创建属于我们的种群

在一切的开始,我们为种群制定一个规则,比方说这个种群的大小,DNA链的长度~

Population_Nums=200 # 种群有200个个体
DNA_Size=16 # DNA链的长度
Range=[[-3,3],[-3,3]] # 自变量的值域范围# 初始化
import numpy as np 
# pop维度为(n,Population_Nums,DNA_Size)
# 其中n表示有几个种群,也就是自变量
pop=np.random.randint(0,2,size=(len(Range),Population_Nums,DNA_Size))

种群的数量呢决定了收敛的速度,但是也有可能因此陷入局部最优解,并降低运行速度(注意跟收敛速度的区别)

DNA链的长度实际上决定了精度。这句话如何理解呢?我们要来看如何将一串DNA转译成我们需要的信息~

假设有一串DNA链: 10101 10101 10101,我们的映射函数为 F ( X , Y ) F(X,Y) F(X,Y),其中 X X X的值域为 [ − 5 , 5 ] [-5,5] [5,5],想一想如何进行转译呢?

为了方便计算和模拟遗传变异,我们采用了二进制作为个体DNA。而我们想要的结果是十进制,那就需要先将二进制转为十进制! 1 ∗ 2 4 + 0 ∗ 2 3 + 1 ∗ 2 2 + 0 ∗ 2 1 + 1 ∗ 2 0 = 21 1*2^{4}+0*2^3+1*2^2+0*2^1+1*2^0=21 124+023+122+021+120=21,这样就来到了十进制。对于种群的基因,只需要除以一个最大值,即 11111 11111 11111,或者说 2 n 2^n 2n,就可以压缩到区间 [ 0 , 1 ] [0,1] [0,1],然后再通过区间匹配到实际值域区间中。

这段写成代码的话,可以是这样:

def decoding(pop):deList=[]for idx,i in enumerate(pop):deList.append(i.dot(2**np.arange(DNA_Size))/float(2**DNA_Size)*(Range[idx][1]-Range[idx][0])+Range[idx][0])return deList

好啦,那么现在我们就需要评估一个个体的适宜度,这也是自然选择中最重要的部分。适宜度越大的个体,越容易在下一轮的选择中存活。

假设函数为:

def F(x,y):return 3*(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转为十进制编码后,带入函数的结果,这个结果越大,说明适宜度越高。

def fitnetss(pop):deList=decoding(pop)pred=F(*deList)return (pred-pred.min())+1e-3

后面这个1e-3的实际含义是,让每一个个体都有机会,而不是绝对肯定或绝对否定哪个个体。


二、遗传和变异

在遗传部分,我们设置了一个参数,用来控制遗传发生的比例。毕竟有些个体并没有后代~

在变异部分,我们同样也有一个较小的参数,用来控制变异发生的可能性。

def mutation(pop,rate=1e-3):# 变异将随机发生for i in pop:if np.random.rand()<rate:# 随机一个个体发生变异i[np.random.randint(0,DNA_Size)]^=1

变异的作用是跳出局部最优解,下面是进行变异的三次结果:

(x,y):  -0.03668099860435703 1.499994903802568
(x,y):  -0.013274610833800438 1.6933678801875045
(x,y):  0.05119961805341333 1.4999723732455

而下面是不进行变异的三次结果:

(x,y):  -0.027307929236169315 1.5981612562037268
(x,y):  0.18948037561657305 1.4062327388663727
(x,y):  -0.0962074456338553 1.4998157322296937

可以发现,发生了变异后,结果稳定在[0,1.5],而不是陷入部分最优解。

遗传过程的算法可以描述如下:

  • 遍历种群中的每个个体,并将该个体A作为父母个体
  • 有一定概率该个体可以随机跟种群中的其他个体B发生基因交换(甚至包括它自己,但这对结果并没有影响,只是降低了遗传概率)
  • 发生基因交换时,随机选择DNA的断点,断点前半部分由个体A提供,后半段由个体B提供
def crossover(pop,rate=0.7):# 注意这里只与自身种群发生变化new_pop=[]for idx in pop.shape[0]:children=[]for father in pop[idx]:if np.random.rand()<rate:child=fathermother=pop[idx][np.random.randn(0,Population_Nums)]# 随机选择发生互换的碱基对choicePoint=np.random.randn(0,DNA_Size)child[choicePoint:]=mother[choicePoint:]# 发生变异children.append(mutation(child))return chidren

三、自然选择

这部分将会根据个体的适宜度分配权值,决定该个体基因出现在下一轮概率。

def select(pop,fitness):pop_s=[]for i in pop:pop_s.append(i[np.random.choice(np.array(Population_Nums),size=Population_Nums,replace=True,p=(fitness)/(fitness.sum()))])return pop_s

四、基于面向对象的遗传算法

现在,我们就要将这些东西封装成一个类啦,提高复用性和稳定性。

首先是构造函数,就是先写入一些常量。

class GA(object):def __init__(self,popN=2000,DNA_Size=16,Epochs=500,crossRate=0.8,mutationRate=0.005):self.popN=popN # 种群数量self.DNA_Size=DNA_Size # DNA长度self.Epochs=Epochs # 迭代次数self.crossRate=crossRate # 交叉遗传概率self.mutationRate=mutationRate  # 变异概率self.Range=None # 输入数据的值域# 例如:[[-3,3],[2,5],[1,9]] 这表示第一个变量的值域是[-3,3],第二个是[2,5]self.plot_=[] # 保留每轮的最优值self.bestScore=None # 最佳得分self.best=None # 最佳个体

然后,需要提供一个输入函数的接口:

   def fit_function(self,f,range):self.f=fself.Range=range# 初始化种群self.pop=np.random.randint(0,2,size=(len(range),self.popN,self.DNA_Size))self.plot_=[]

解码方法:

   def decoding(self):deList = []for idx, i in enumerate(self.pop):deList.append(i.dot(2 ** np.arange(self.DNA_Size)) / float(2 ** self.DNA_Size) * (self.Range[idx][1] - self.Range[idx][0]) + self.Range[idx][0])return deList

适应值:

    def fitness(self):deList=self.decoding()pred=self.f(*deList)return (pred-pred.min())+1e-3

变异:

    def mutation(self,pop):if np.random.rand()<self.mutationRate:pop[np.random.randint(0,self.DNA_Size)]^=1return pop

交叉遗传:

    def crossover(self):for idx in range(self.pop.shape[0]):for _,father in enumerate(self.pop[idx]):child = fatherif np.random.rand()<self.crossRate:mother=self.pop[idx][np.random.randint(0,self.popN)]crossPoint=np.random.randint(0,self.DNA_Size)child[crossPoint:]=mother[crossPoint:]self.pop[idx][_]=self.mutation(child)

自然选择:

    def select(self,fitness):pops=[]for i in self.pop:pops.append(i[np.random.choice(self.popN,size=self.popN,replace=True,p=fitness/(fitness.sum()))])return pops

打印信息:

    def getInfo(self):print('最优参数为: ',[i for i in self.best])print("最优结果为: ",self.bestScore)

提供一个训练接口和绘图接口供使用者调用:

    def train(self,plot=False):for _ in range(self.Epochs):self.crossover() # 交叉变异f=self.fitness() # 计算适宜度max_fit = np.argmax(f) # 获取最大适宜度下标k=[(i[max_fit].dot(2**np.arange(self.DNA_Size))/float(2**self.DNA_Size))*(self.Range[idx][1]-self.Range[idx][0])+self.Range[idx][0] for idx,i in enumerate(self.pop)] # 获取最佳个体的十进制值bs=self.f(*k) # 计算该值的适宜度# 请注意,适宜度并不代表函数结果,适宜度是一个相对的值# 记录全局最优结果if self.bestScore==None or bs>self.bestScore:self.bestScore=bsself.best=kself.pop = np.array(self.select(f)) # 自然选择if plot:self.plot_.append(bs)self.getInfo()def plot(self):if self.plot_==[]:passplt.plot([i for i in range(self.Epochs)],self.plot_)plt.xlabel("Epochs")plt.ylabel("BestValue")plt.show()

最终的结果如下:

在这里插入图片描述

可以看到在25个Epoch左右就开始收敛了。


完整代码

import numpy as np
import matplotlib.pyplot as pltclass GA(object):def __init__(self,popN=2000,DNA_Size=16,Epochs=500,crossRate=0.8,mutationRate=0.005):self.popN=popNself.DNA_Size=DNA_Sizeself.Epochs=Epochsself.crossRate=crossRateself.mutationRate=mutationRateself.Range=Noneself.plot_=[]self.bestScore=Noneself.best=Nonedef fit_function(self,f,range):self.f=fself.Range=rangeself.pop=np.random.randint(0,2,size=(len(range),self.popN,self.DNA_Size))self.plot_=[]def decoding(self):deList = []for idx, i in enumerate(self.pop):deList.append(i.dot(2 ** np.arange(self.DNA_Size)) / float(2 ** self.DNA_Size) * (self.Range[idx][1] - self.Range[idx][0]) + self.Range[idx][0])return deListdef fitness(self):deList=self.decoding()pred=self.f(*deList)return (pred-pred.min())+1e-3def mutation(self,pop):if np.random.rand()<self.mutationRate:pop[np.random.randint(0,self.DNA_Size)]^=1return popdef crossover(self):for idx in range(self.pop.shape[0]):for _,father in enumerate(self.pop[idx]):child = fatherif np.random.rand()<self.crossRate:mother=self.pop[idx][np.random.randint(0,self.popN)]crossPoint=np.random.randint(0,self.DNA_Size)child[crossPoint:]=mother[crossPoint:]self.pop[idx][_]=self.mutation(child)def select(self,fitness):pops=[]for i in self.pop:pops.append(i[np.random.choice(self.popN,size=self.popN,replace=True,p=fitness/(fitness.sum()))])return popsdef getInfo(self):print('最优参数为: ',[i for i in self.best])print("最优结果为: ",self.bestScore)def train(self,plot=False):for _ in range(self.Epochs):self.crossover()f=self.fitness()max_fit = np.argmax(f)k=[(i[max_fit].dot(2**np.arange(self.DNA_Size))/float(2**self.DNA_Size))*(self.Range[idx][1]-self.Range[idx][0])+self.Range[idx][0] for idx,i in enumerate(self.pop)]bs=self.f(*k)if self.bestScore==None or bs>self.bestScore:self.bestScore=bsself.best=kself.pop = np.array(self.select(f))if plot:self.plot_.append(bs)self.getInfo()return self.bestdef plot(self):if self.plot_==[]:passplt.plot([i for i in range(self.Epochs)],self.plot_)plt.xlabel("Epochs")plt.ylabel("BestValue")plt.show()if __name__ == '__main__':ga=GA(popN=200,DNA_Size=16,Epochs=200)def F(x, y):return 3 * (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)Range = [[-3, 3], [-3, 3]]ga.fit_function(F,Range)ga.train(True)ga.plot()

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/110024.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

性能优化之分库分表

1、什么是分库分表 1.1、分表 将同一个库中的一张表&#xff08;比如SPU表&#xff09;按某种方式&#xff08;垂直拆分、水平拆分&#xff09;拆分成SPU1、SPU2、SPU3、SPU4…等若干张表&#xff0c;如下图所示&#xff1a; 1.2、分库 在表数据不变的情况下&#xff0c;对…

图像处理 信号处理板 设计原理图:367-基于zynq XC7Z100 FMC接口通用计算平台

基于zynq XC7Z100 FMC接口通用计算平台 一、板卡概述 板卡由SoC XC7Z100-2FFG900I芯片来完成卡主控及数字信号处理&#xff0c;XC7Z100内部集成了两个ARM Cortex-A9核和一个kintex 7的FPGA&#xff0c;通过PL端FPGA扩展FMC、光纤、IO等接口&#xff0c;PS端ARM扩展网络、USB、R…

exchange实战

未得到exchange服务器权限 确定exchange服务器ip地址 setspn -T example.domain.com -F -Q */* | findstr exchangeMailSniper 爆破用户名和密码 爆破Exchange邮箱用户名密码&#xff0c;为了防止账号被锁定&#xff0c;所以我们使用密码喷洒攻击&#xff0c;即只使用一个密…

dolphinschedule配置企微告警服务(WeChat群组)

一、前置说明 ds配置好工作流后&#xff0c;比较重要的一个就是上线后的监控报警服务&#xff0c;如果你是基于企微作为协同办公的&#xff0c;WeChat群组预警必须是要安排上的&#xff0c;文章基于自建应用配合群组方式构建预警群&#xff0c;接入后&#xff0c;任务成功或者…

sql:SQL优化知识点记录(五)

&#xff08;1&#xff09;explain之例子 &#xff08;2&#xff09;索引单表优化案例 上面的功能已经实现&#xff0c;但是分析功能&#xff0c; 使用explain分析这条sql&#xff1a; 发现type为All Extra&#xff1a;有Using filesort &#xff08;文件内排序&#xff09; 这…

创作2周年纪念日-特别篇

创作2周年纪念日-特别篇 1. 与CSDN的机缘2. 收获3. 憧憬 1. 与CSDN的机缘 很荣幸&#xff0c;在大学时候&#xff0c;能够接触到CSDN这样一个平台&#xff0c;当时对嵌入式开发、编程、计算机视觉等内容比较感兴趣。后面一个很偶然的联培实习机会&#xff0c;让我接触到了Pych…

浅析Linux SCSI子系统:设备管理

文章目录 概述设备管理数据结构scsi_host_template&#xff1a;SCSI主机适配器模板scsi_host&#xff1a;SCSI主机适配器主机适配器支持DIF scsi_target&#xff1a;SCSI目标节点scsi_device&#xff1a;SCSI设备 添加主机适配器构建sysfs目录 添加SCSI设备挂载LunIO请求队列初…

基于Spring Boot的软件缺陷追踪系统的设计与实现(Java+spring boot+MySQL)

获取源码或者论文请私信博主 演示视频&#xff1a; 基于Spring Boot的软件缺陷追踪系统的设计与实现&#xff08;Javaspring bootMySQL&#xff09; 使用技术&#xff1a; 前端&#xff1a;html css javascript jQuery ajax thymeleaf 微信小程序 后端&#xff1a;Java spri…

【HTML】基础语法讲解

基础语法 1. HTML 结构1.1 认识HTML标签1.2 HTML 文件基本结构1.3 标签层次结构1.4 快速生成代码框架 2. HTML 常见标签2.1 注释标签2.2 标题标签:h1-h62.3 段落标签:p2.4 <br>换行标签2.5 格式化标签2.6 图片标签&#xff1a;img2.7 超链接标签&#xff1a;a2.8 表格标签…

Flutter问题记录 - Unable to find bundled Java version

新版本的Android Studio真的移除了JRE&#xff0c;jre目录找不到&#xff0c;怪不得报错了&#xff0c;不过多了一个jbr目录&#xff0c;找了个以前的Android Studio版本对比 搜了一下jbr&#xff08;JetBrains Runtime&#xff09;&#xff0c;原来IDEA老早就开始用了&#xf…

公网远程访问局域网SQL Server数据库

文章目录 1.前言2.本地安装和设置SQL Server2.1 SQL Server下载2.2 SQL Server本地连接测试2.3 Cpolar内网穿透的下载和安装2.3 Cpolar内网穿透的注册 3.本地网页发布3.1 Cpolar云端设置3.2 Cpolar本地设置 4.公网访问测试5.结语 1.前言 数据库的重要性相信大家都有所了解&…

Android studio APK切换多个摄像头(Camera2)

1.先设置camera的权限 <uses-permission android:name"android.permission.CAMERA" /> 2.布局 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas.android.com/apk/res/android"and…

vue中html引入使用<%= BASE_URL %>变量

首先使用src相对路径引入 注意&#xff1a; js 文件放在public文件下 不要放在assets静态资源文件下 否则 可能会报错 GET http://192.168.0.113:8080/src/assets/js/websockets.js net::ERR_ABORTED 500 (Internal Server Error) 正确使用如下&#xff1a;eg // html中引…

go gin 参数绑定常用验证器

https://pkg.go.dev/github.com/go-playground/validator/v10#readme-baked-in-validations min 最小max 最大len 长度限制gt 大于eq 等于ne 不等于eqfield 与某个字段值一样nefield 与某个字段值不一样 package mainimport ("net/http""github.com/gin-gonic…

7.react useReducer使用与常见问题

useReducer函数 1. useState的替代方案.接收一个(state, action)>newState的reducer, 并返回当前的state以及与其配套的dispatch方法2. 在某些场景下,useReducer会比useState更加适用,例如state逻辑较为复杂, 且**包含多个子值**,或者下一个state依赖于之前的state等清楚us…

【Leetcode】124.二叉树中的最大路径和(Hard)

一、题目 1、题目描述 二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。 路径和 是路径中各节点值的总和。 给你一个二叉树的根节点 root ,返回其…

进行Stable Diffusion的ai训练怎么选择显卡?

Stable Diffusion主要用于从文本生成图像&#xff0c;是人工智能技术在内容创作行业中不断发展的应用。要在本地计算机上运行Stable Diffusion&#xff0c;您需要一个强大的 GPU 来满足其繁重的要求。强大的 GPU 可以让您更快地生成图像&#xff0c;而具有大量 VRAM 的更强大的…

2023年高教社杯 国赛数学建模思路 - 案例:ID3-决策树分类算法

文章目录 0 赛题思路1 算法介绍2 FP树表示法3 构建FP树4 实现代码 建模资料 0 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 1 算法介绍 FP-Tree算法全称是FrequentPattern Tree算法&#xff0c;就是频繁模…

微信小程序——van-field中的left-icon属性自定义

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…

【网络安全带你练爬虫-100练】第19练:使用python打开exe文件

目录 一、目标1&#xff1a;调用exe文件 二、目标2&#xff1a;调用exe打开文件 一、目标1&#xff1a;调用exe文件 1、subprocess 模块允许在 Python 中启动一个新的进程&#xff0c;并与其进行交互 2、subprocess.run() 函数来启动exe文件 3、subprocess.run(["文件路…