【优化算法】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 1∗24+0∗23+1∗22+0∗21+1∗20=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://xiahunao.cn/news/1620271.html

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

pyinstaller打包openvino 2021.4.2

pyinstaller打包openvino 2021.4.2

打包准备 1. 测试环境准备 conda create -n opinstall python3.7 -y conda activate opinstall pip install openvino2021.4.2 pip install pyinstaller PyCharm新建openvino_install&#xff0c;选择虚拟环境opinstall&#xff0c;编写测试代码 app.py import numpy as n…
阅读更多...
8.27周报

8.27周报

文章目录 前言论文阅读摘要介绍模型算法 总结 前言 本周学习了GAN论文《Generative Adversarial Nets》&#xff0c;了解GAN主要由两部分组成&#xff1a;生成器和判别器&#xff0c;知道生成器G和判别器D的作用及原理&#xff0c;相比于其他的生成模型&#xff0c;了解GAN的优…
阅读更多...
API管理测试 - 最佳实践和关键要素

API管理测试 - 最佳实践和关键要素

什么是API管理测试&#xff1f; API管理测试是在软件开发和集成功能中对应用程序接口&#xff08;API&#xff09;进行测试和验证的过程。它涵盖了测试API的功能、性能、安全性以及与其他系统的交互。API管理测试对于确保API的正确运行和稳定性非常重要。 ​ 为什么API管理测…
阅读更多...
谷歌浏览器 设置多账户_使用多个Google帐户时如何设置默认帐户？

谷歌浏览器 设置多账户_使用多个Google帐户时如何设置默认帐户？

谷歌浏览器 设置多账户 If you’re using multiple Google accounts simultaneously there’s a good chance that one of them is the one you want to default. When it isn’t the default it’s rather frustrating; read on as we show a reader how to ensure the accoun…
阅读更多...
谷歌广告账户结构

谷歌广告账户结构

Google竞价广告的帐户结构性设置主要有三层&#xff0c;分别是广告帐户、广告系列和广告组。把它们综合起来 就构成了整个的一个广告框架。 为什么要采用这样一个复杂的三层框架呢&#xff1f;简单来说&#xff0c;其目的就是为了将不同的广告匹配给不同的用户群体&#xff0c;…
阅读更多...
谷歌正在向所有账户推出密码终止技术

谷歌正在向所有账户推出密码终止技术

谷歌宣布让其个人帐户持有人使用称为“密码”的密码替代登录的一项重大努力。 该功能面向公司的数十亿帐户推出&#xff0c;用户将能够主动寻找并启用它。谷歌表示&#xff0c;它计划在未来几个月推广密码&#xff0c;并开始推动账户持有人将他们传统的用户名和密码登录转换为…
阅读更多...
如何查看谷歌账户的实际消费金额和扣款金额是否一致？

如何查看谷歌账户的实际消费金额和扣款金额是否一致？

第一步&#xff1a;找到广告账户上方的报告——预定义报告 。 第二步&#xff1a;预定义报告 下一个层级的其他。 第三步&#xff1a;其他下面的已出账单费用。 第四步&#xff1a;核查数据 可以选择需要核对的历史账单日期。检查投放费用和已出账单费用是否一致。也可以下载下…
阅读更多...
谷歌账户在别的网上登过_如何在Google帐户之间转移联系人

谷歌账户在别的网上登过_如何在Google帐户之间转移联系人

谷歌账户在别的网上登过 Google provides no way to automatically sync contacts between two different Google accounts. Instead, you’ll have to perform a manual two-step process where you export your contacts from one account to a comma-separated values (CSV)…
阅读更多...
谷歌账户无法添加_如何将多个Google帐户添加到Google Home

谷歌账户无法添加_如何将多个Google帐户添加到Google Home

谷歌账户无法添加 Google Home is designed to be a shared device that everyone in the house can use. Now, Google has finally made it possible for it to recognize different people and give personalized info to everyone using their Google accounts. Here’s how…
阅读更多...
Android 快速集成谷歌账户登录

Android 快速集成谷歌账户登录

谷歌登录开发者平台注册地址为https://console.firebase.google.com/&#xff0c;并不是在https&#xff1a;//console.developers.google.com/上进行注册&#xff0c;一开始我也是参考网上的帖子 在谷歌的developers网站上进行注册&#xff0c; 流但发现流程一直走不通&#x…
阅读更多...
谷歌账户剩余余额如何退回。

谷歌账户剩余余额如何退回。

一、点击账户右上角工具与设置-偏好设置 二、账号状态-撤销我的账号&#xff08;切记一定要是具有账户管理员的账户才有此选项展示&#xff09; 此时已经进入退款环节。我们再次确认。 1、点击账户右上角工具与设置-结算-摘要 2、您的退款正在审批中&#xff0c;大概7个工作日…
阅读更多...
谷歌浏览器账户密码转移

谷歌浏览器账户密码转移

如果你有多台电脑&#xff0c;在新电脑上面使用谷歌浏览器&#xff0c;但是各个网站都要重新输入密码觉得很麻烦&#xff0c;这里有你想要的&#xff01; 你只需要按下面操作&#xff0c;即可在新电脑谷歌浏览器上面导入以前输入的账户密码&#xff1a; 1. 打开谷歌浏览器&am…
阅读更多...
谷歌账户二次验证_为您的Google帐户和Microsoft帐户设置双重身份验证

谷歌账户二次验证_为您的Google帐户和Microsoft帐户设置双重身份验证

谷歌账户二次验证 I use Two-Factor Authentication for my Google Apps account and I use the Google Authenticator application on my iPhone to generate the second factor. 我对我的Google Apps帐户使用了双重身份验证，并且在iPhone上使用了Google Authenticator应用程…
阅读更多...
Android项目集成谷歌账户登录

Android项目集成谷歌账户登录

在做国外项目的时候，许多需要集成谷歌账户登录功能。 集成谷歌登录后，能直接调用谷歌的账户登录界面进行登录操作（包括注册新用户、忘记密码等），同时会把账户信息保存到设备的account manager中进行管理，检测设备是否已登录了谷歌账户，获取已登录的谷歌账户的相关信息。…
阅读更多...
谷歌多账户登陆_如何一次登录多个Google帐户

谷歌多账户登陆_如何一次登录多个Google帐户

谷歌多账户登陆 Google has carefully designed its account system so that it can be at the center of your digital life. But if you need to use multiple Google accounts (say, if you have a personal Gmail and a work Gmail), things get tricky quickly. Fortunate…
阅读更多...
谷歌账户无法添加_如何将另一个Google帐户添加到您的Android设备

谷歌账户无法添加_如何将另一个Google帐户添加到您的Android设备

谷歌账户无法添加 In order to set up an Android device, you have to sign in with a Google account. But you can also add more than one Google account, like a work or second personal account. 为了设置Android设备，您必须使用Google帐户登录。 但是，您也可以添加多…
阅读更多...
2023超全攻略|教你谷歌账号如何防封、解封？

2023超全攻略|教你谷歌账号如何防封、解封？

谷歌账号对于跨境业务来说&#xff0c;是必不可少的。谷歌账号开通后就可以有一个国际化的收发邮箱&#xff0c;也可以开通谷歌广告等谷歌旗下所有的业务&#xff0c;更可以直接登录其它海外网站&#xff0c;比如YouTube、Twitter、Facebook等社交媒体平台。可以说谷歌账号对于…
阅读更多...
走向新的乐章——2021年奔驰C级轿车抢先看

走向新的乐章——2021年奔驰C级轿车抢先看

2021年奔驰C级这辆轿车采用的是全新发动机和全新改进技术&#xff0c;虽然W205一代梅赛德斯-奔驰c级轿车刚刚更新换代&#xff0c;但我们已经有了第一批全新c级轿车的间谍照&#xff0c;它的内饰型号为W206&#xff0c;并且在未来几年会上市。对于狂热者来说&#xff0c;这何尝…
阅读更多...
2023.6.27

2023.6.27

阅读更多...
hw0725

hw0725

#include "widget.h" #include "ui_widget.h"widget::widget(QWidget *parent): QMainWindow(parent), ui(new Ui::widget) {ui->setupUi(this);//设置尺寸this->resize(800,600);//固定尺寸this->setFixedSize(800,600);//设置窗口标题this->…
阅读更多...
最新文章

Copyright @ 2022~2023