<h1 align=center>智能算法之Genetic Algorithm遗传算法</h1>
<div align="center">
<image src="https://markdown-liyang.oss-cn-beijing.aliyuncs.com/label/Github-LiYangSir-brightgreen.svg">
<image src="https://markdown-liyang.oss-cn-beijing.aliyuncs.com/label/quguai.cn-green.svg">
<image src="https://img.shields.io/badge/Lannguage-MatLab-yellow">
<image src="https://markdown-liyang.oss-cn-beijing.aliyuncs.com/label/Version-1.0-blue.svg">
</div>
-----
> 前言:本文主要围绕 Matlab 的实现展开,Java版本以及Python版本参考文章最后的源码地址,MatLab和python实现大致相同,Java较为不同。
## 1、什么是遗传算法
  我们了解过深度学习的都知道,我们在进行网络优化的过程都是通过反向传播求导进行参数的不断优化,而这种类型的优化参数采用前向传播的方式继续优化网络,不断找出最优解,或者最优的参数。很多的优化算法都来自于大自然的启发,来一种算法叫做蚁群算法,灵感就是来自于蚂蚁,所以观察大自然有时也是灵感的来源。
  遗传算法,也叫Genetic Algorithm,简称 GA 算法他既然叫遗传算法,那么遗传之中必然有基因,那么基因染色体(Chromosome)就是它的需要调节的参数。我们在生物中了解到,大自然的法则是“物竞天择,适者生存”,我觉得遗传算法更适用于“**优胜劣汰**”。
+ 优:最优解,
+ 劣:非最优解。
## 2、遗传算法名词解释
  下面主要通过疑问提问题的方式进行解释遗传算法当中的适应度函数、选择、交叉、变异这几个名词。
**1. 都知道优胜劣汰,那怎么实现优胜劣汰呢?**
  很重要的一个环节就是**选择**,也称之为“大自然的选择”,大自然怎么选择呢,大自然会抛弃掉一些适应能力差的,在程序当中就是离最优解较远的解,会被抛弃掉。
**2. 如何实现大自然的选择呢?**
  这里我们会引入轮盘赌法,进行大自然的选择。选择一些离最优解较近的个体。还有一些其他的经典的选择办法,例如锦标赛法进行选择。
**3. 只靠选择就可以实现吗?那样会不会陷入局部最优解?**
  如果只靠选择进行调优,那么最终的结果会受到初始种群的影响,只是在初始种群的群体中进行选择,得出的最优解也是在初始群体中的最优解。所以就需要引入大自然当中的“啪啪啪”,也叫**交叉**。正所谓“龙生龙,凤生风,老鼠生下来就会打洞”,所以说两个优秀的基因进行交叉可以将两者优秀的基因遗传给一代,也增加了群体的基因多样性,但这种不一定就是最好的,也可能发生“夭折”。
**4. 大自然的选择好像不仅如此,还有变异吧?**
  为了更好的模拟大自然的选择规律,来需要进入**变异**,变异发生的概率很低,但也是增加群体多样性的条件,和交叉相同,变异求解出来的不一定是最好的解,也会出现“夭折”。
**5. 上面只是大自然的规则,那么大自然的环境又是什么呢?**
  优秀的基因并不是独立的,就像北极熊不会存活在热带雨林一样。只有适合环境的基因才是优秀的,所以说基因具有相对性,环境是挑选基因的先决条件,这里的环境就是**适应度函数**。个体用过适应度函数后得到的结果越大,表明更加适合这里的环境,那么保留下来的概率越大。反之则越小。
## 3、遗传算法的程序实现
  正所谓 “不结合代码的解释都是** ” 。下面结合代码来梳理遗传算法的实现。
<div align=center>
<img src=https://markdown-liyang.oss-cn-beijing.aliyuncs.com/%E4%BC%98%E5%8C%96%E7%AE%97%E6%B3%95/GA%E9%81%97%E4%BC%A0%E7%AE%97%E6%B3%95/%E5%88%9D%E5%A7%8B%E7%BB%93%E6%9E%84.png width=50% alt=基本结构>
</div>
  涉及到还是适应度函数、选择、交叉、变异这几个模块。下面就这几个模块展开说明。具体的流程图解释如下:
1. 需要先对初始种群进行一次**适应度函数**进行计算,这样方便我们对个体进行选择,适应度值越大的越容易被保留;
2. 对群体进行**选择**,选择出适应度值较大的一部分优势群体;
3. 对优势种群进行 “**交配**”,更容易产生优秀的个体;
4. 模拟大自然**变异**操作,对染色体个体进行变异操作;
下面以计算函数最大值
$$
f(x)=10\times sin(5\times x)+7\times \left|x-5\right|+10; x\in[0, 10]
$$
### 3.1、种群初始化
  种群的初始化相对简单,只需要随机生成一个二维矩阵,矩阵的**size=(种群大小,染色体编码长度)**。染色体编码采用二进制编码的方式。染色体编码并不是直接采用将[0, 10]直接转换为二进制,原因如下:
+ 并非均匀分布,10的二进制表示为1010,会导致出现空余位置,例如11、12等没有意义的数字出现
+ 精度低,如果直接编码最小增量单位变成了 1 ,没有了浮点数的表示,最优解很多情况都会出现在浮点数的表示范围。n:代表染色体编码的长度
$$
x = \dfrac{染色体编码对应的十进制值}{2^n - 1}
$$
  此时x的范围为[0, 1],我们可以根据待测得x轴的范围进行偏移计算。例如:x得范围为[2, 10],则设计:
$$
x = \dfrac{染色体编码对应的十进制值}{2^n - 1} \times 8 + 2
$$
  种群初始化基本结构如下,实数范围还需要进一步计算得到真正得x轴的浮点值。
<div align=center>
<img src=https://markdown-liyang.oss-cn-beijing.aliyuncs.com/%E4%BC%98%E5%8C%96%E7%AE%97%E6%B3%95/GA%E9%81%97%E4%BC%A0%E7%AE%97%E6%B3%95/%E7%A7%8D%E7%BE%A4%E7%BB%93%E6%9E%84.png width=50% alt=基本结构>
</div>
```matlab
% popsize: 种群个数
% chromlength: 染色体长度
function pop=initpop(popsize,chromlength)
% round:产生的随机数进行四舍五入操作就是0或者1
pop = round(rand(popsize,chromlength));
```
### 3.2、适应度函数设计
  适应度函数得出的值越大表明个体越优秀,所以一般情况下,在求解函数最大值的时候,适应度函数就是求解函数本身,求解最小值的时候适应度函数就是函数的倒数。在本例中求取最大值,所以适应度函数就是函数本身。
```matlab
function [objvalue] = cal_objvalue(pop)
x = binary2decimal(pop);
objvalue=10*sin(5*x)+7*abs(x-5)+10;
% 二进制转10进制并转换到对应的x轴浮点值
function pop2 = binary2decimal(pop)
[px,py]=size(pop);
for i = 1:py
pop1(:,i) = 2.^(py-i).*pop(:,i);
end
temp = sum(pop1,2);
pop2 = temp*10/1023; % 限制到[0, 10]
```
### 3.3、选择
  我们在前面已经说明了选择的原因(挑选优秀个体),挑选的算法有很多,我们这里选择“轮盘赌法”。轮盘赌法就是类似于我们玩的转盘,圆心角度越大的我们越容易选中。
**注:** 选择后后的个体数目和原种群个数相同。
<div align=center>
<img src=https://markdown-liyang.oss-cn-beijing.aliyuncs.com/%E4%BC%98%E5%8C%96%E7%AE%97%E6%B3%95/GA%E9%81%97%E4%BC%A0%E7%AE%97%E6%B3%95/%E8%BD%AE%E7%9B%98%E8%B5%8C.png width=25% alt=轮盘赌法>
</div>
  大自然就像那个指针,适应度值越大,表明这个体约适应这个环境,那么被选择的概率越大,与此同时,适应度值小的个体并不代表不会被选中,只是选中的概率小,一方面也保证了正负样本的一个均衡。
```matlab
% pop: 遗传算法的种群
% fitvalue: 种群的适应度值
% newpop: 返回筛选过后的新的种群
function [newpop] = selection(pop,fitvalue)
[px,py] = size(pop);
totalfit = sum(fitvalue);
% 将适应度值转换为概率,适应度值越大表明概率越大
p_
没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
matlab 矩阵数组 遗传算法、粒子群算法、模拟退火算法、免疫算法、蚁群算法(智能算法)matlab实现 蚁群算法:Ant_Colony_Optimization 遗传算法:Genetic_Algorithm 免疫算法:Immunity_Algorithm 粒子群:Particle Swarm Optimization 路线规划、深度学习等等一系列领域所使用的优化算法,算法进阶之路的必备。
资源推荐
资源详情
资源评论
收起资源包目录
Smart-Algorithm.zip (76个子文件)
Smart-Algorithm
Smart-Algorithm.iml 445B
Immunity_Algorithm
IMA解决TSP问题
main.m 1KB
DisplaceInit.m 245B
DisplaceStr.m 323B
DrawRouteGif.m 766B
SelectAntigen.m 575B
Mutation.m 1KB
DrawRoute.m 363B
CharRecompose.m 429B
test.gif 446KB
IMA解决非线性问题求解
main.m 2KB
Hypermutation.m 162B
InitializeFun.m 105B
DecodeFun.m 216B
ReproduceFun.m 397B
IMA
main.m 2KB
main.asv 2KB
bird.bmp 291KB
isRgb.m 210B
similarPopulation.m 328B
fit.m 330B
similarChromosome.m 570B
select.m 407B
mutation.m 391B
cross.m 591B
fitnessty.m 1KB
bamboo.bmp 276KB
drawResult.m 285B
README.md 11KB
Particle_Swarm_Optimization
PSO-Toolbox
main.m 538B
pso_func.m 177B
PSO-basic
main.m 536B
DrawGriewank.m 221B
Rastrigin.m 144B
fitness.m 83B
Griewank.m 206B
DrawRastrigin.m 224B
PSO.m 1KB
.DS_Store 6KB
Ant_Colony_Optimization
ACO_MatLab
AC解决函数最优解
SolveMax.m 2KB
F.m 101B
AC解决机器人路径规划
main.m 5KB
Magine.gif 997KB
G2D.m 466B
DrawRoute.m 431B
test.gif 294KB
AOC解决TSP问题
mian.m 3KB
TSP.gif 411KB
DrawRoute.m 582B
res.png 24KB
README.md 12KB
Genetic_Algorithm
GA_Python
GA_Test.py 558B
Population.py 3KB
GA_MatLab
GA遗传算法解决非线性最优解
binary2decimal.m 249B
main.m 993B
cal_objvalue.m 199B
selection.m 519B
initpop.m 197B
best.m 359B
crossover.m 472B
mutation.m 545B
README.md 12KB
GA遗传算法解决TSP问题
main.m 3KB
exchange.m 75B
plot_route.m 467B
myLength.m 368B
fit.m 176B
mutation.m 242B
reverse.m 533B
cross.m 970B
GA遗传算法工具箱
ga44.m 90B
Test.m 126B
GA_Java
GeneticAlgorithmTest.java 798B
GeneticAlgorithm.java 6KB
Chromosome.java 3KB
README.md 13KB
共 76 条
- 1
资源评论
vimtion
- 粉丝: 1180
- 资源: 72
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功