遗传算法的应用——求解一元函数的极值
遗传算法的应用——求解一元函数的极值
- 1 基本概念
- 2 预备知识
- 3.1 模拟二进制转化为十进制的方法
- 3.2 轮盘赌选择算法
- 3 问题
- 4 Matlab代码
- 5 运行效果
- 6 总结
1 基本概念
- 遗传算法(Genetic Algorithm,
GA
)是模拟生物在自然环境中遗传和进化过程从而形成的随机全局搜索和优化方法,它是一种并行的、高效的、具有自适应能力的全局搜索算法,它充分体现了适者生存
的生物进化思想,能在搜索过程中自动获取和积累有关搜索空间的知识,并自适应地控制搜索过程以求得最优解。 - 遗传算法能有效求解NP问题和非线性、多峰函数优化及多目标优化问题。
- 遗传算法的三个最重要操作
选择(复制) -> 交叉 -> 变异
- 遗传算法:
- 以决策变量的编码作为运算对象
- 直接以目标函数值作为搜索信息
- 同时使用多个搜索点的搜索信息
- 是一种基于概率的搜索方法
- 求解最大值问题(最小值问题理论上添一个负号就是最大值问题,还有其他方法可以转换问题的导向)
- 遗传算法在进化搜索中基本不用外部信息,仅以适应度函数为依据
- 但是基本遗传算法的局部搜索能力较差,有“早熟”缺陷,不能保证算法收敛
- 下边对遗传算法中用到的几个重要的参数进行一个简单的说明:
群体规模:
群体规模太小时,算法的搜索效果通常较差,容易陷入局部最优;群体规模太大时,算法的计算复杂度将会变大。一般取值为[10,200];交叉概率:
在基本遗传算法中,将交叉算子作为遗传算法最重要的操作。较大的交叉概率可以增强算法开辟新的搜索区域的能力,但高性能的模式,也就是二进制组合遭到破坏的可能性增大;交叉概率太低可能会导致算法陷入迟钝状态。一般取值为[0.4,0.99];变异概率:
变异算法的主要目的是保持群体的多样性。低的变异概率可以防止群体中重要基因的丢失;变异概率太大时,算法就变成了纯粹的随机搜索算法。一般取值为[0.0001,0.1];
2 预备知识
3.1 模拟二进制转化为十进制的方法
在遗传算法中,通常会涉及到二进制到十进制的转换,所以需要掌握这个方法,那么为什么说是模拟二进制转为十进制的方法呢,因为我们在代码中通常不是真正的一串二进制数字,而是由一个向量,其中存放许多0101这样的数字,如a=[0 1 0 1]
,这样就模拟了一个二进制数,那么它对应的十进制就是5,在matlab中有两个方法,这两种方法对于大量的数据其转换速度有较大差异,请合理选择,如果有其他方法,请各位朋友留言。
%% 法一 通过循环实现
a = [1 0 0 1 1 0 0 1];
deca = 0;
for i = 1:length(a)deca = a(i)*2^(i-1) + a;
end%% 法二 通过强制转换实现(调用库函数)
a = [1 0 0 1 1 0 0 1];
deca = bin2dec(char('0'+ a));
3.2 轮盘赌选择算法
轮盘赌选择算法是遗传算法中,进行复制操作的一种常用算法,在该方法中,各个个体的选择概率和其适应度值成比例,适应度越大,选中概率也越大。但实际在进行轮盘赌选择时个体的选择往往不是依据个体的选择概率,而是根据“累积概率”来进行选择。我将通过一个抽奖的例子进行一个简单地介绍(参考文章:轮盘赌选择算法):
等级 | 一等奖 | 二等奖 | 三等奖 |
---|---|---|---|
选择概率 | 0.2 | 0.5 | 0.3 |
累计概率 | 0.2 | 0.7 | 1.0 |
可以从概论论的角度出发,先简单地将选择概率理解为概率密度函数,设xi(i=1,2,3)表示获奖等级,则f(xi)表示该等级对应的适应度,则xi被选中的概率Pxi可以被表示为:
将累计概率Qxi理解为概率分布函数,则Qxi可以表示为从xi开始往前的所有的概率的累加和:
- 计算个体的被选择概率(概率密度函数)
- 计算各个部分的累计概率(概率分布函数–离散型)
- 生成一个[0,1]区间内均匀分布的随机实数,代表此时轮盘的旋转位置(这里就可以理解为什么用累计概率了)
- 找到累计概率中第一个大于或等于第3步产生的随机数的索引,这个索引就是轮盘赌算法选择的那个个体(不理解可以先看代码)
以一个抽奖问题为导引的轮盘赌算法实例Matlab代码如下:
clc
clear% 定义奖项及其中奖概率
awards = {'一等奖', '二等奖', '三等奖', '四等奖', '五等奖'};
P = [0.1, 0.2, 0.3, 0.2, 0.2]; % 中奖概率
cumP = cumsum(P); % 累计概率% 模拟抽奖过程
N = 1000; % 模拟次数
results = zeros(1, N); % 存储每次抽奖的结果
for i = 1:N% 生成一个随机数,代表轮盘的旋转位置pos = rand();% 根据轮盘赌算法确定中奖等级level = find(cumP >= pos, 1);% 存储结果results(i) = level;
end% 统计中奖次数
winCounts = histcounts(results, 1:(length(awards) + 1));% 显示结果
disp('中奖统计:');
for i = 1:length(awards)fprintf('%s:%d次\n', awards{i}, winCounts(i));
end
上述代码中,有两行代码需要自己好好理解一下:
% 根据轮盘赌算法确定中奖等级
level = find(cumP >= pos, 1);% 统计中奖次数
winCounts = histcounts(results, 1:(length(awards) + 1));
第一个地方不明白可以自己手动推一下,第二个地方是因为用到了直方图 bin 计数函数,因为results里边全部是存放的等级,用这个函数就可以很快的统计出每个等级在results中出现的次数。
一次统计的结果如下:
3 问题
4 Matlab代码
clear
close all
clcT1 = cputime;
%% 初始化参数
NP = 50; % 种群数量(染色体数目,一个染色体就相当于是一个个体)
L = 20; % 二进制位串长度
Pc = 0.8; % 交叉概率
Pm = 0.05; % 变异概率
G = 100; % 最大遗传次数
Xs = 10; % 搜索上限
Xx = 0; % 搜索下限(这个是随自变量的取值范围确定的,我们已经知道了函数的取值范围)
f = randi([0,1],NP,L); % 随机获得初始种群(种群里有NP个个体,每个个体的基因位数为L,用0,1模拟二进制)
trace = zeros(1,G); % 历代最优适应度
%% 遗传算法主体
for k = 1:GFit = zeros(1,NP); % 种群中每个个体的适应度x = zeros(1,NP); % 存放二进制数对应的十进制数,我把它定义为虚表现型(注意这个并不是真正的解集,还需要做一个映射)%%% 将二进制解码为定义域内的十进制(让二进制和十进制一一对应起来)for i = 1:NPU = f(i,:); % (基因型)U存放的就是一个个体的基因(一串二进制位,这里是用01模拟的)m = 0; % (伪表现型)这是U对应的十进制% m = bin2dec(char('0'+ U)); 可以用这句话直接实现进制的转换for j = 1:Lm = U(j)*2^(j-1) + m;end% (实表现型)将十进制转换为对应的表现型(x)% 这段代码的实际含义是将通过随机0,1序列转换而来的十进制数,与定义域内的数一一对应起来,% 否则通过随机0,1序列转换而来的十进制数根本没有实际含义,无法和定义域里联系起来% 但是这个定义的法则是通过这个公式确定的,有什么具体其他规范吗?或者其他的定义法则x(i) = Xx + m*(Xs-Xx)/(2^L - 1); % 将二进制对应的十进制数映射到定义域中(请记住这种映射的方法)Fit(i) = GetFit(x(i)); % 计算这个个体的适应度endmaxFit = max(Fit); % 找到最大的适应度值minFit = min(Fit); % 找到最小的适应度值rr = find(Fit == max(Fit)); % 找到最大适应度值对应的个体编号% 最优个体的基因% 因为最大适应度值可能不止一个,可能有多个最大值,因此用rr(1)取第一个最大值对应的个体fBest = f(rr(1),:); % 最优个体的基因型xBest = x(rr(1)); % 最优个体的实表现型Fit = (Fit-minFit)/(maxFit-minFit); % 将适应度做归一化处理(请记住这种归一化的方法)%%% 基于轮盘赌的复制操作sumFit = sum(Fit);fitValue = Fit./sumFit; % 求每个个体的适应度值占总的适应度值的百分比fitvalue = cumsum(fitValue); % 适应度值的累加和ms = sort(rand(NP,1));fiti = 1; % 记录当前适应度的索引(在轮盘赌选择的过程中,fiti 用于追踪当前适应度的位置)newi = 1; % 记录新个体的索引(轮盘赌选择的过程中,newi 用于确定新种群中的位置,即确定新个体的存放位置。)while newi <= NPif(ms(newi) < fitvalue(fiti))nf(newi,:) = f(fiti,:);newi = newi + 1;elsefiti = fiti + 1;endend%%% 基于概率的交叉操作(不懂请画图理解)for i = 1:2:NP % i是奇数号染色体if rand < Pcq = randi([0,1],1,L); % 随机生成一个交换flag(为1的位置对应的基因型之间进行交换)for j = 1:Lif q(j) == 1% 交换等位基因temp = nf(i+1,j);nf(i+1,j) = nf(i,j);nf(i,j) = temp;endendendend%%% 基于概率的变异操作i = 1;while i <= round(NP*Pm)h = randi([1,NP],1,1); % 在种群中随机选一个染色体来变异for j = 1:round(L*Pm)g = randi([1,L],1,1);% 随机选取一个需要变异的基因数nf(h,g) = ~nf(h,g); % 将染色体nf中第h个个体的第g个基因取反,就是变异了endi = i + 1;endf = nf; f(1,:) = fBest; % 保留最优个体在新种群中trace(k) = maxFit; % 历代最优适应度
endT2 = cputime;
timeConsume = T2 -T1;
%% 适应度进化曲线
figure(Color=[1 1 1])
plot(trace,LineWidth=2,Color=[0.56 0 0.56]);
xlabel("迭代次数",FontName="黑体",FontWeight="bold",FontSize=15);
ylabel("目标函数值",FontName="黑体",FontWeight="bold",FontSize=15);
title("适应度进化曲线","CPU时间消耗: "+timeConsume + 's',FontName="黑体",FontWeight="bold",FontSize=12);%% 做出原始图像
x = 0:0.01:10;
y = x + 10*sin(5*x) + 7*cos(4*x);
figure(Color=[1 1 1])
plot(x,y,lineWidth=2);
ylim([min(y)-1,max(y)+1]);
xlabel("x",FontName="Times new Roman"...,FontAngle="italic",FontWeight="bold",FontSize=15);
ylabel("f(x)",FontName="Times new Roman"...,FontAngle="italic",FontWeight="bold",FontSize=15);
title("f(x)=x+10sin(5x)+7cos(4x)",FontName="Times new Roman"...,FontAngle="italic",FontWeight="bold",FontSize=15);
hold on
z = abs(y - max(trace));
x = x(z == min(z));
plot(x(1),max(trace),'r*');%% 适应度函数
function result = GetFit(x)% 这里选择的适应度函数就是目标函数(实际上适应度函数要求为一个非负的函数)result = x + 10*sin(5*x) + 7*cos(4*x);
end
5 运行效果
6 总结
之前本科的时候也做过一些关于遗传算法的实际应用,但是很多是复用别人的代码,简单地修修改改,不过后边很长时间都没有再用了,导致很多知识已经忘记了,所以写算法还是要常加联系。上述代码可能还有许多错误和很多值得优化的地方,恳请各位老师留言,批评指教。
相关文章:

遗传算法的应用——求解一元函数的极值
遗传算法的应用——求解一元函数的极值 1 基本概念2 预备知识3.1 模拟二进制转化为十进制的方法3.2 轮盘赌选择算法 3 问题4 Matlab代码5 运行效果6 总结 1 基本概念 遗传算法(Genetic Algorithm,GA)是模拟生物在自然环境中遗传和进化过程从而形成的随机全局搜索和优化方法&am…...

Power BI 学习
数据获取 数据清洗 对导入的数据进行数据整理的过程一般称为「数据清洗」,之所以称之为清洗,是因为在数据分析师眼中,杂乱的数据就是脏数据,只有被清洗成干净的数据后才可以进行分析使用。 数据丰富 操作 1.复制列 点击列名选…...

PPT中加入页码
PPT中加入页码 文章目录 简单版本样式更改 简单版本 PPT中插入页码,基础的就是在“插入”选项卡中单机“幻灯片编号”即可 样式更改 然而,就像我们做幻灯片不满足于白底黑字一样,页码也总不能是默认的样式。 比如,在页码下面…...
xxl-job使用笔记
文章目录 xxl-job配置文件新增XxlJobConfig类JobHandler例子xxl-job机制xxl-job-admin配置XxlJob 和 JobHandler(过时了) 其他报错 msg:job handler [demoJobHandler] not found.xxl-job报错 xxl-job registry fail, registryParam:RegistryParam{registryGroup‘EX…...

微短剧,会成为长视频的“救命稻草”吗?
职场社畜秒变霸道总裁,普通女孩穿越成为艳丽皇妃.......这样“狗血”的微短剧,最近不仅在国内各大视频平台上异常火爆,而且还直接火出了国外。 所谓微短剧,就是单集时长从几十秒到十几分钟的剧集,有着相对明确的主题和…...

web架构师编辑器内容-创建业务组件和编辑器基本行为
编辑器主要分为三部分,左侧是组件模板库,中间是画布区域,右侧是面板设置区域。 左侧是预设各种组件模板进行添加 中间是使用交互手段来更新元素的值 右侧是使用表单的方式来更新元素的值。 大致效果: 左侧组件模板库 最初的模板…...

力扣刷题记录(18)LeetCode:474、518、377、322
目录 474. 一和零 518. 零钱兑换 II 377. 组合总和 Ⅳ 322. 零钱兑换 总结: 474. 一和零 这道题和前面的思路一样,就是需要将背包扩展到二维。 class Solution { public:int findMaxForm(vector<string>& strs, int m, int n) {vector&l…...
MongoDB创建和查询视图(一)
目录 限制和注意事项 应用两种方式创建视图 本文整理mongodb的官方文档,介绍mongodb的视图创建和查询。 Mongodb中,允许使用两种方式来创建视图。 //使用db.createCollection()来创建视图 db.createCollection("<viewName>",{"…...
paddle 53 基于PaddleClas2.5训练自己的数据(训练|验证|推理|c++ 部署)
项目地址:https://github.com/PaddlePaddle/PaddleClas 文档地址:https://paddleclas.readthedocs.io/zh-cn/latest/tutorials/install.html paddleclas的最新项目已经不适应其官网的使用案例(训练、验证、推理命令均不适用),为此博主对其进行命令重新进行修改。同时padd…...

智能优化算法应用:基于卷积优化算法3D无线传感器网络(WSN)覆盖优化 - 附代码
智能优化算法应用:基于卷积优化算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用:基于卷积优化算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.卷积优化算法4.实验参数设定5.算法结果6.…...
项目中日期封装
官网:Moment.js 中文网项目中安装:npm install moment --save封装:创建一个.js文件 // 日期、时间封装 import moment from moment moment.locale("zh-cn"); const formatTime {getTime: (date) > {return moment().format(YY…...
7.仿若依后端系统业务实践
目录 概述项目实践mybatis 反向生成代码有覆盖问题解决pom.xmlbootstrap.ymlapplication.ymlmaven测试各种校验问题实践单个属性校验级联属性校验接口实体类测试结果自定义关联属性校验接口...
java:4-9键盘输入
文章目录 键盘输入.1 定义.2 步骤.3 演示 键盘输入 .1 定义 在编程中,需要接收用户输入的数据,就可以使用键盘输入语句来获取。Input.java , 需要一个 扫描器(对象), 就是 Scanner .2 步骤 导入该类的所在包package, java.util.*创建该类对象(声明变…...

制作自己的 Docker 容器
软件开发最大的麻烦事之一,就是环境配置。用户必须保证操作系统的设置,各种库和组件的安装,只有它们都正确,软件才能运行。docker从根本上解决问题,软件安装的时候,把原始环境一模一样地复制过来。 以 koa-…...

Linux的账号及权限管理
一.管理用户账号 1.1 用户账户的分类 1.1.1 用户账号的分类 超级用户:(拥有至高无上的权利) root用户是Linux操作系统中默认的超级用户账号,对本主机拥有最高的权限,系统中超级用户是唯一的。普通用户: …...

Flink 状态管理与容错机制(CheckPoint SavePoint)的关系
一、什么是状态 无状态计算的例子: 例如一个加法算子,第一次输入235那么以后我多次数据23的时候得到的结果都是5。得出的结论就是,相同的输入都会得到相同的结果,与次数无关。 有状态计算的例子: 访问量的统计&#x…...
CSS中更加高级的布局手段——定位之绝对定位
定位: - 定位指的就是将指定的元素摆放到页面的任意位置,通过定位可以任意的摆放元素 - 通过position属性来设置元素的定位 -可选值: static: [sttik] 默认值,元素没有开启定位 relative: [relətiv] 开启元素…...

SQL server 数据库练习题及答案(练习3)
一、编程题 公司部门表 department 字段名称 数据类型 约束等 字段描述 id int 主键,自增 部门ID name varchar(32) 非空,唯一 部门名称 description varchar(1024) …...

太绝了!这个食堂服务,戳中了打工人的心巴!
在当今数字化时代,科技的迅猛发展已经渗透到我们生活的方方面面,其中餐饮行业也不例外。食堂作为人们日常生活中不可或缺的一部分,其管理和运营也需要紧跟科技潮流。 智慧收银系统的引入,旨在提高食堂的效率、准确性和服务水平&am…...

围栏中心点
后端返回的数据格式是 [{height: 0,lat: 30.864277169098443,lng:114.35252972024682}{height: 1,lat: 30.864277169098443,lng:114.35252972024682}.........]我们要转换成 33.00494857612568,112.53886564762979;33.00307854503083,112.53728973842954;33.00170296814311,11…...

UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...

边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...

人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...