遗传算法(Genetic Algorithm,GA)起源于对生物系统所进行的计算机模拟研究。美国Michigan大学的Holland教授及其学生受到生物模拟技术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统优化的自适应概率优化技术——遗传算法。

1.1遗传算法概念：

生物的进化过程，主要是通过染色体之间的交叉和变异来完成的。遗传算法是模仿自然界生物进化机制的随机全局搜索和优化方法，其本质是一种高效、并行、全局搜索的办法，他能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应的控制搜索过程以求的最优解。遗传算法操作使用适者生存的原则，以潜在的解决方案种群中逐次产生一个近似最优的方案。
遗传算法是自然遗传学和计算机科学相互结合而成的新的计算方法，因此遗传算法中经常使用到自然进化的一些用语。
生物的遗传物质的主要载体是染色体，DNA是其中最主要的的遗传物质。复数个基因组成染色体，染色体中基因的位置称为基因座，基因所取的值叫做等位基因。基因和基因座决定了染色体的特征，也就决定了生物个体的性质状态。染色体有两种表现模式，即基因型和表现型。表现型是指生物个体所表现出来的性质状态，基因型指与表现型密切相关的基因组成
。同一种基因型的生物个体在不同的环境下可以有不同的表现型，也就是说，表现型是基因型和环境共同作用的结果。
在计算机的遗传算法中，染色体通常对应的是一维的串结构数据，串上各个位置对应上述的基因座，各位置上的取值对应上述的等位基因，遗传算法处理的就是染色体，或者叫做基因型个体。一定数量的个体就组成了种群。各个个体对环境的适应程度叫做适应度。
执行遗传算法包含两个必要的操作，一个是表现型到基因型的转换，它把搜索空间中的参数或解转换成遗传空间中的染色体或个体，此过程称为编码；另一个是基因型到表现型的转换，称为译码。

1.2遗传算法与爬山法的比较：

爬山法是直接法、梯度法和Hessian法的统称。爬山法首先在最优解可能存在的地方选择一个初始点，然后通过分析目标函数的特性，由一个初始点移到一个新的点，然后再继续这个过程。爬山法的搜索过程是确定的，他通过产生一系列的点收敛到最优解(有时是局部最优)，而遗传算法的搜索过程是随机的，它产生一系列随机个体构成种群。二者的主要差异归纳为如下两点：
(1)爬山法的初始点只有一个，由决策者给出，而遗传算法的初始点有很多个，是随机产生的。
(2)爬山法由上一个点产生一个新的点，而遗传算法是通过在当前种群中交叉、变异和选择产生下一代种群。

1.3遗传算法的基本原理与方法：

遗传算法的实现涉及六个主要因素：参数的编码，初始种群的设定，适应度函数的设计，遗传操作，算法控制参数的设定和约束条件的处理。
编码：
在遗传算法中，如何描述问题的可行解，即把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法就称为编码。遗传算法的编码就是解的遗传表示，它是遗传算法求解的第一步。
选择：
选择又称复制，是在种群中选择生命力强的个体产生新的群体的过程。遗传算法使用选择算子对群体的个体进行优胜劣汰的操作，根据每个个体的适应度值大小进行选择，适应度高的个体被遗传到下一代群体中的概率较大，适应度低的个体被遗传到下一代群体中的概率较小。这样就可以使群体中的个体的适应度不断接近最优解。轮盘赌选择法：这是一种随机选择方法，选择的方法是根据个体的适应度值，每个个体进入下一代的概率就是它的适应度值与整个种群中适应度值的和的比例，将每个个体的概率都画在圆盘上，随机拨动圆盘，当圆盘停止时，指针所指个体被选中。所以，适应度值越高，被遗传的概率就越大。
交叉：
在生物的自然进程中，两个同源染色体通过交配而重组，形成新的染色体，从而产生新的个体或物种。遗传算法中的交叉是指将个体的基因进行互换。一般来说交叉方法包括：单点交叉、两点交叉、多点交叉、均匀交叉等。
变异：
在生物的遗传和自然进化中，其细胞分裂复制环节，如二进制编码中，将0变成1,1变成0，从而形成一个新的染色体。使用变异的目的有两个：第一个是改善遗传算法的局部搜索能力。遗传算法的交叉算子已经从全局的角度出发找到了一些较好的个体编码结构，但仅使用交叉无法对搜索空间的细节进行局部搜索，若这时再使用变异，就可以提高局部搜索的能力。

第二章：遗传算法应用举例

2.1简单一元函数优化实例：

选择二进制编码，种群个体数目为40，每个个体的基因为20，使用代沟为0.9，最大遗传代数为25.利用遗传算法计算下面函数的最大值：

f(x) = xsin(10pi*x) + 2.0 x∈[-1,2]

[题目分析:]
首先应该利用Matlab画出目标函数的图像：
fplot(@(variable)variable.*sin(10.*pi.*variable)+2.0,[-1,2])
在这里插入图片描述
从图中可以大致看出最大值的横坐标在1.75~2之间，纵坐标＞3.5
接下来使用遗传算法对这个函数求解最大值：
第一步是随机产生一个种群(应该包括种群个数，种群的染色体长度)，按照题目要求，种群个体数目为40，也就是说在[-1,2]的范围内随机产生40个解的横坐标，题目指出每个个体的基因为20，选择二进制编码，也就是说把刚刚随机产生的这40个解每一个都用20位2进制数表示。
下图是初始种群在目标函数上的分布图，红色的点就是随机产生的40个解的横坐标。(每一次的点都不一样，因为是随机的)
在这里插入图片描述
第二步是选择，将初始化种群中的个体(即上图的红点)按照适应度大小(这里的适应度大小是由初始化40个红点纵坐标的比较得来的，如上图，1.5-1.75之间的两个红点纵坐标最大，所以他们的对环境(也就是这道题目要求的求函数最大值)的适应度最大，1.25-1.5之间的那个红点纵坐标最小，所以它对环境的适应度最小，也就是说适应度是在本种群内，相比其他个体得到的一个适应度)进行选择，这里采用的是轮盘赌选择。
下图是经过选择之后的个体的分布图，绿色的框就是从初始种群中根据适应度值选择出来的个解的横坐标。(我给的算法是只挑选了36个原种群表现好的个体，但是可以发现，图中绿色的框的个数小于36，并且初始种群中有些表现不是那么好的也被选中遗传到下一代，这是由于原始种群的有些个体被选择多次，这就体现了轮盘赌的随机性。)
在这里插入图片描述
第三步是交叉和变异。这里的交叉是指把上述选择的36个个体每两个之间(即绿色的框)进行基因互换(第一步中，将每个个体都用20位2进制数表示了，即每个个体都有20位基因)，这里可以选用的交叉方式有多种。变异是指将种群中个体的某些位的值进行改变，这里就是将个体的某些位变为0或者是1.
下图蓝色是经过被选中的个体交叉之后的个体的分布图，也就是说，经过交叉之后，种群个体就从红色点变为了蓝色的，可以看出解的横坐标的变化过程。为了方便后面更直观的看出解，后面我将将红色、绿色、蓝色**去除。变异后的个体如图黑色框部分。
在这里插入图片描述

可以看出这第一轮遗传之后，有个体已经向1.75-2之间那个最大值的范围迈进了。这个个体坐标为(1.8996,3.2048)。
上述过程是一轮遗传算法中解的变化。下面给出遗传25次的完整Matlab代码。
这段代码中有Matlab的一些内置函数，将先对这些函数进行说明。
种群创建函数:crtbp(NUM,GeneLength,Base) return matrix
入口参数：NUM:种群个体数，GeneLength:基因长度，Base:基因进制数，缺省为2进制
返回一个NUM×GeneLength的矩阵
二进制串到实值的转换:bs2rv(Chrom,FieldD) return a column vector
入口参数：Chrom二进制矩阵，也就是crtbp的返回值
FieldD:译码矩阵=[len,lb,ub,code,scale,lbin,ubin]
len:每个个体基因长度，lb,ub每个变量上下界，code=1,2进制编码，=0格雷编码，
scale=0，算术刻度，=1对数刻度，lbin，ubin=0，去掉边界
返回一个列向量，该向量的行数是Chrom的行数，也就是NUM
排序函数Ranking(Obj，Rfun) return a column vector ->得到适应度
入口参数：Obj:个体的表现，
Rfun:缺省为线性排序，从大到小，压差为2，此评定算法假设目标是最小化
种群选择个体函数Sel=Select(SEL_F,Chrom,FitV,GGAP) 从种群Chrom中选择优良个体，并返回到新种群Sel中
选择具有随机性，并不是按照适应度从大到小依次选择，
即每个个体被选中的次数随机，表现不好的也可能被选中，只是概率小一点
重插入子代到种群[Chrom,ObjVch] = reins(Chrom,Sel,1,InsOpt,ObjVch,ObjVsel)
返回插入子代后的种群以及对应子代的目标值
InsOpt是一个包含两个参数的向量。InsOpt[0]:=1表示基于适应度插入；=0为均匀选择
InsOpt[0]:为一[0,1]的常数,表示基于适应度插入常数% 的子代
重组个体recombin(‘xovsp’,Sel,0.7) 对Sel种群中每两个个体进行单点交叉，只有70%可参与交叉
##################

figure(1);
fplot(@(variable)variable.*sin(10.*pi.*variable)+2.0,[-1,2])%画出函数
hold on;
PARENT = 40;%种群40
MAXGEN = 25;%遗传25代
GENELEN = 20;%每个个体的基因位数为20位
GGAP = 0.9;%每次只选择90%的个体    40×0.9=36
%用trace来保存每一代中最优个体的坐标，第一行存纵坐标，第二行存横坐标
trace = zeros(2,MAXGEN);
%译码矩阵，指明每个个体有20个基因，本题只有一个变量，该变量的下界=-1，上界=+2，包含边界，采用2进制编码
field = [20;-1;2;1;0;1;1];
%初始种群 包含PRRENT=40的个体 每个个体的基因长度为GENELEN，ctrbp是matlab内置函数
Pgroup = crtbp(PARENT,GENELEN);%这里返回一个40×20的矩阵，每个位置的值为0或1
%gen变量用来表示遗传第几代
gen = 0;
variable = bs2rv(Pgroup,field);%二进制串转实值，这里相当于把解的横坐标映射到[-1，2]的范围
obj = variable.* sin(10*pi* variable) + 2.0;%计算每个个体的纵坐标，也就是计算每个个体的表现
% plot(obj,variable,'r.');%红点画出初始种群
while gen <MAXGEN,%根据个体表现计算每个个体的适应度，ranking假设目标是最小，所以这里是-objFitnV = ranking(-obj);%按照适应度从Pgroup种群中选择90%的表现好的子代，返回到Sel种群中，这时Sel应该是一个36×20的矩阵Sel = select('sus',Pgroup,FitnV,GGAP); %对选择后的Sel种群中每两个个体进行单点交叉，只有70%可参与交叉Sel = recombin('xovsp',Sel,0.7);Sel = mut(Sel);%对交叉后的种群Sel进行变异，这里的Sel仍是一个36×20的矩阵variable2 = bs2rv(Sel,field);%二进制串到实值的转换，将变异后的子代映射到[-1，2]的范围obj2 = variable2.* sin(10*pi* variable2) + 2.0;%计算每个子代的表现，即纵坐标%将子代插入父代，按照适应度将子代的36个替代原种群40个表现不好的个体[Pgroup,obj]=reins(Pgroup,Sel,1,1,obj,obj2);gen = gen+1;[Y,I] = max(obj) ;%将本代中表现最好的个体的横纵坐标保存在trace矩阵中trace(1,gen) = max(obj) ;trace(2,gen) = sum(obj)/length(obj) ;
endvariable = bs2rv(Pgroup,field);plot(variable,obj,'k.');figure(2);plot(trace(1,:));figure(3);plot(trace(2,:),'-.');

####################
figure1是25代之后，个体的一个分布图，figure2是种群每一代最好的解的一个变化
在这里插入图片描述

如果将遗传代数MAXGEN改为50，重新得到figure1，figure2，明显看出最优解收敛了。