遗传算法【matlab实现】（内含matlab基础式注释）

    最近在准备数学建模，凭借微弱的matlab基础学习遗传算法等一系列最优化算法实在是有点吃力。想着帮助自己消化吸收+帮助其他小白同学快速看懂代码，所以写了一篇blog，给出了遗传算法的大致实现思路。但重点是里面傻瓜式的代码注释，详细到了每一个系统函数、matlab语法的用法。适合仓促备赛、快速上手matlab实现算法的同学。

---

分割线---2023/4/24更新

经验与教训之谈：

        这篇文章是本人大一零经验入门数模，学习算法思路时写的文章，当然当时打国赛也用上了这一篇文章里的代码。（对的，当时一切算法代码都是手搓，现在想来有种刺激爽快而很傻的矛盾快感）

        但是后来逐渐发现，数模核心其实并不在于编写算法代码---这无异于从零造别人造过的轮子，吃力还低效。学习数模的核心应该是：了解更多可行的算法，学会如何调用/结合现有的最优的代码去解决自己的问题。

        因此从这个角度，我不建议数模跑数据时直接用我下面的代码去跑，而可以去调现成的很方便的库。(但是学习时看看底层代码会有更深刻的认知，比赛时附录可以把源码贴上去充实文章)

       这篇文章应该是提供一份资料让大家学习了解这个算法，并且在论文里能把这个算法说清楚。

 

目录

一、遗传算法的思想来源

二、遗传算法的原理分析

①建立种群的基因库------二进制编码

1）确定基因序列长度N

2）建立自变量到十进制数间一一映射关系

②实现遗传过程的交配、突变、选择遗传等过程

1）依适应度的概率选择规则

2）新种群复制

3）新种群交配（交叉）

4）基因突变

5）遗传迭代

二、完整代码段

1）各种参数初始化（需要自己补充上下界、精度）

2）主函数

3)结果可视化（main）

4）适应度计算函数（ 自己写目标函数targetfun() ）

5）选择复制函数

6）交叉函数

7）变异函数

7）适应度计算函数

8）轮盘赌

9）二进制-十进制转换函数

---

一、遗传算法的思想来源

        遗传算法是建立在自然选择学说基础之上的智能算法。生物种群在自然选择中优胜劣汰，代代繁衍。每一次种群更替，总是淘汰劣质基因、保留优质基因，从而朝着种群的最优发展方向进化。

        生物遗传是生物种群不断靠近全局最优解的过程，那么我们能不能用这个思路来解决最优化问题呢？

         当然可以：仿照自然遗传过程，①人为设定一个数据组作为“种群基因”，②以目标函数作为评判“发展方向优劣”的标准；③让这群数据通过计算机模拟的“交配”、“基因突变”、“种群复制”等自然选择过程，不断迭代更新、优胜劣汰；④基因趋于稳定时，我们称其为“成熟”，就得出问题的全局最优解。

二、遗传算法的原理分析

①建立种群的基因库------二进制编码

        实际的生物基因是由ACTG四个碱基组成的字母串，要模拟生物基因，使用二进制代码01序列是方便的：

        1.基因的交叉------01序列部分交换

        2.基因突变------二进制数串的某一位0-1翻转

        3.二进制与题目求的十进制数之间转换方便

而matlab也可以方便地创建出一个01的矩阵，以模仿生物种群中不同个体的基因序列：

population = round(rand(popsize,Length)); %rand(popsize,length)为随机数函数，生成一个在[0,1]区间的popsize*length大小的随机数矩阵%round函数对rand函数生成的矩阵四舍五入处理，即可生成01矩阵%参数说明：population 种群基因库     popsize 种群中个体的大小

        生成的population（种群）类似下表：

基因序列（长度为length）/ 个体序号（大小为popsize）
个体①	1	0	0	1	1	0	1	1	0
个体②	0	1	1	0	1	1	0	0	1
......

       (表1)

            01表示的二进制序列很好的解决了基因模拟问题，但现在又有两个新问题：

① Q：如果我们要求某个函数在(-5,5)上的最优解，种群就应该落在这个区间上。但二进制编码到十进制编码都是在0到2^N上的数，如何将其映射到自变量区间上？

② Q：01序列的长度如何选取？

     A：由你所要求的自变量精度precision决定。自变量十进制要求精度越高，二进制精度要求当然也要高，基因序列也就越长。

        这两个问题都是通过二进制编码实现的，下面通过一个具体题目来感受下这个编码思路：

例：求解下述复杂函数的最大值，自变量x∈[-2,2]，要求精度precision=0.001

编码过程：

1）确定基因序列长度N

精度为precision=0.001，那么就将[-2,2]这个区间分成了  4÷0.001=4000个数。按照上面的思路，其中每一个数都应该对应二进制基因序列的一种排列方式。大概如下：

自变量	二进制(N位)
-2.000	00......00
-2.001	00......01
......	......
1.999	11......10
2.000	11......11

(表2)

所以，二进制最大值 == 编码数量  

  ​

解得  基因长度N   

  

普遍的，二进制长度公式为     

  

2）建立自变量到十进制数间一一映射关系

        二进制序列确定好了之后，对应的十进制数也就确定了

二进制	十进制	自变量
000...000	0	-2.000
000...001	1	-1.999
......	.......	......
111...110	3999	1.999
111...111	4000	2.000

二进制  ---->  十进制   ---->自变量 之间的一一映射关系实际是简单的

二进制到十进制：   

function x=transform2to10(population);%函数功能：将二进制数转换为十进制数%传入参数：种群的二进制序列population(按行表示)%返回值：x  种群对应的十进制数Length = size(population,2);%获取列数即染色体长度x=population(Length); %x初始化为该染色体的最末位for i =1:Length-1    x=x+population(Length-i)*power(2,i);end

十进制数转换成自变量区间内的数：

x = lower_bound + x_10 *(upper_bound-lower_bound) / (power(2,Length)-1);%将十进制数x_10 转化为[lower_bound,upper_bound]区间的自变量x   用等分法

        到此，基因序列编码、基因与自变量间的一一对应关系建立完成，就可以使用这群01基因序列进行运算求解实际问题了。

②实现遗传过程的交配、突变、选择遗传等过程

1）依适应度的概率选择规则

        生物繁衍过程，种群的生老病***，基因是否突变，基因是否顺利遗传，哪两个基因发生交配等问题都是不确定的概率问题。因此，我们不能用绝对的标准控制某个基因的遗传情况。

        因此，我们只能通过抽奖的方式，将某个个体被抽到的概率与其生存能力（适应度）挂钩。生存能力越强，适应度越大，自然也就有更大机会被选中，进行遗传行为了。

        生物繁衍过程的适应度是指：生物生存技能、生物体质是否壮硕等指标。类似的，求解函数的最大值问题时，我们自然将自变量的函数值作为适应度了。函数值越大、它适应度越大，越容易被抽中。

        同理，当求解最小值优化问题时，应构造适应度函数，使得函数值越小，适应度越大。

        具体适应度与概率的评估过程如下：

        a.根据目标函数，计算出适应度fitness;对适应度累加，求出种群的总适应度fitness_sum;

        求解个体占总适应度的比例，将每个个体按比例分配到0-1区间上的一个小区间。

个体	1	2	3	4
区间	[0,0.1]	[0.1,0.4]	[0.4,0.9]	[0.9,1.0]
占总适应度比例	10	30	50	10

        b.由于rand函数生成0-1区间上的数的几率是一定的。因此某个体适应度越大，随机数落在该个体所在区间上的概率就越大。因此使用rand()函数生成在[0，1]区间上的数，进行随机抽奖。        

       例如，生成随机数若为0.6，那么就落在了个体3所在区间上，个体3被选中。

%子函数fitnessfun() ,计算适应度及累计概率的函数%返回值fitvalue为适应度，cumsump为概率区间%population为种群的基因矩阵function [Fitvalue,cumsump]=fitnessfun(population);global Lengthglobal lower_boundglobal upper_bound%size函数 输入参数1为获取矩阵的行数(种群大小)，2为获取列数(基因长度)popsize =size(population,1); %进入循环遍历每个染色体for i=1:popsize    x_10=transform2to10(population(i,:)); %二进制转换为十进制    %转化为[-2,2]区间的自变量x 用等分法    x=lower_bound+ x_10 *(upper_bound-lower_bound)/(power(2,Length)-1);    Fitvalue(i)=targetfun(x);     %求解适应度 targetfun()为目标函数endFitvalue=Fitvalue'+230;            %避免出现负适应度，在这里加一个正数fsum=sum(Fitvalue);                %求解总适应度Pperpopulation = Fitvalue/fsum;    %求解每个个体的概率Pcumsump(1)=Pperpopulation(1);      %依概率在0,1上分配区间for i=2:popsize    cumsump(i)=cumsump(i-1)+Pperpopulation(i);endcumsump=cumsump';        //转置一下,返回概率区间

        抽奖规则做好了，接下来只需要完善基因交叉、遗传、变异等功能函数，组装起来，遗传算法的架构就做好了。

2）新种群复制

        种群复制: 该步骤主要为选择一定数量的染色体复制到下一代，是实现“优胜劣汰”的关键步骤。每个个体是否能被遗传到下一代，由上述提到的个体适应度决定。

        但是，这里存在两种复制方案，我认为有必要在这里说明一下：

        ① 将适应度从大到小进行排序，选取适应度最优的P_0个个体遗传到下一代

        ②依照适应度大小，得出被遗传的概率大小，依照概率随机抽选个体遗传。该方法中，最优个体有可能在复制中被丢失；最差个体也有可能被复制到下一代。

        部分小伙伴可能理所当然认为①是最合理的。但并不是，两种方法有其各自的应用范围。下面分别谈谈：

1、办法①在求解一些简单的优化问题，通常局部最优即为全局最优解的问题是适用的。但是，每一步都只保留优秀个体而损失不良个体，可能会被“暂时的优秀”，即局部最优所蒙蔽。这种做法在面对复杂函数时，会失去一定的全局搜索能力。

        比如，当函数呈现多峰分布且梯度较大时，种群在某时候聚集在局部最优解附近，这种做法只保留了位于局部最优解附近的种群，而损失了在其他领域探索的不良个体。但有可能，不良个体才是距离全局最优最近的个体。

         因此，面对复杂问题是，更合理的办法是选择方案二------依概率遗传。这样可以保证对复杂问题的全局搜索性，对解出最终答案至关重要。

function seln = selection(population,cumsump,num);%子函数selection()%进行新种群选择操作%输入参数:种群population，累计概率cumsump，要求遗传个体数num%返回值为被选中的染色体序号selnpop_size=size(population,1);    %获取当前种群规模selected=zeros(size(population,1))；%用于标记每个个体是否被选择过(避免重复)for i =1:1:num    while 1   %循环包裹，若当前选中了一个未被选过的个体时跳出，否则重新来        r=rand; %产生一个随机数        prand=cumsump-r;  %概率区间统一减去随机数。        index=1;        while prand(index)