时间：2019.8.13
老师：姚香娟
内容：遗传算法基本原理
个性：和蔼、娓娓道来
感想：遗传早有接触，这次再来参加，主要是想能够在理论介绍方面，对遗传算法有一个较为详细的学习。另一个就是希望能够针对写作，对流程再次熟悉，在国赛前复现准备。果然一些数值计算需要线性代数的知识,当时大一时候，看了好多次的遗传，总是不够通透。
1.遗传算法起源与发展
- 遗传算法是模拟达尔文生物进化论的自然选择和孟德尔遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。
1975年密西根大学的J.Holland教授提出一种简单遗传算法(simple genetic algorithm, SGAran'se)由编解码、个体适应度评估和遗传运算三大模块构成，而遗传算法又包括染色体复制、交叉、变异甚至到位等。
改良的遗传算法和融合新型技术的遗传算法都是简单遗传算法的变异形式。
20世纪60年代，Holland教授及其学生和同事提出，一种全局概率搜索优化算法，借鉴生物。
1975 De Jong建立了著名的五函数测试平台。
1983 Goldberg第一次把遗传算法用于实际工程应用。
2.遗传算法基本原理
三大模块：编解码，个体适应度评估，遗传运算
数学模型
编码：把问题的解从其解空间转换到遗传算法的搜索空间的转换方法。
最常用的是二进制编码，构成的个体基因型是二进制符号串。
个体适应度：对应个体表现型X的目标函数值相关联，X越接近于目标函数的最优值，适应度越大。
个体基因型：编码之后的个体表示方法
个体表现型：原来的个体表现方法
3.遗传算法基本步骤
step1: 初始种群，生成
step2: 个体评价适应值函数
step3: 是否满足终止条件
step4: 选择、交叉、变异
step5: 得到子代种群
step6: 子代代替父代，重复step2及之后，直到找到需要解为止
考虑：
- 解的遗传表示
- 初始种群的产生
- 个体的评价函数
- 遗传算子（选择、交叉、变异）
- 算法的控制参数（种群规模、交叉和变异概率等）
4.遗传算法的特点
传统算法
模型结构固定，有较为精确的问题描述
给出精确解
如：线性规划、整数规划、运输问题……
智能优化方法
对优化模型没有结构上的要求
在可接受的时间里找到满意解（可以使用机器学习的方法进行评价）
如：遗传算法、蚁群算法、粒子群算法】免疫算法……
适合组合优化问题：装箱，着色，匹配，TSP，工业设计（电路板，洗衣液配方，轮胎橡胶设计）
5.实例分析
- 采用米哈来维茨的范式
- 求解如下约束条件下的最优解
- 个体表示（考虑精度要求）
eg.精度小数点后4位，取值范围[a,b]
则设需要位二进制，需满足
- 从二进制到十进制实数
的映射为：
最低值+小区间个数×小区间长度
每个解的二进制编码位数即:
比如 6位
- 随机初始种群
- 实施个体评价（终止条件设定为1000代）
- 遗传算子，使用轮盘赌算法，选择概率和适应值成正比。
交叉和变异依交叉和变异概率对基因进行操作 - 用当前种群代替初始种群，循环操作。
7.调用MATLAB的GA工具箱实现遗传算法
调用命令：
其中，f(x)是标量函数；A，B，Aeq，Beq是相应维数的矩阵和向量（构成约束），C(x)和Ceq(x)是非线性向量函数
[X,FVAL]=GA(FITNESSFCN, NVARS,A,B,Aeq,Beq,lb,ub,NONLCON,options)
example
function f = myfit(x)
f = exp(x(1))*(4*x(1)^2 + 2*x(2)^2 + 4*x(1)*x(2) + 2*x(2) + 1);
function [c,ceq] = myconstr(x) %约束条件列表
c = [1.5 + x(1)*x(2) - x(1) - x(2);
-x(1)*x(2) - 10];
% No nonlinear equality constraints:
ceq = [];
[x,fval]= ga(@(x)myfit(x),2,[],[],[],[],[],[],@(x)myconstr(x))
可视化工具箱界面配置
选择GA
function [ y ] = target(x)
% 工具箱只支持求解最小值，将求解最大值变成求解最小值
y = -x-10*sin(5*x)-7*cos(4*x);
end
下面设置参数，关于一些约束条件的理解需要参考上面公式，完全理解需要线性代数的知识，犹记得去年大一的时候，那时没有学习线性代数，建了四五次模型，经常想着去使用遗传算法，然而总没能实现完全复现。当然，当时资料相比于现在，还是很残缺的。如今互联网上，更多人愿意去做详细的教程型博客了，这是一个巨大的改观。我的话，现在仍以记录自己的总结为主，主要是帮自己梳理一下。
设置参数，约束条件的理解参考上面的公式
8.编写.m函数实现遗传算法
学习参考博客：遗传算法介绍及详尽代码
学习推荐参考博客：很详尽
代码参考博客：遗传算法流传版本改错
% 下面举例说明遗传算法 %
% 求下列函数的最大值 %
% f(x)=10*sin(5x)+7*cos(4x) x∈[0,10] %
% 将 x 的值用一个10位的二值形式表示为二值问题，一个10位的二值数提供的分辨率是每为 (10-0)/(2^10-1)≈0.01
% 将变量域 [0,10] 离散化为二值域 [0,1023], x=0+10*b/1023, 其中 b 是 [0,1023] 中的一个二值数。 %
% %
%--------------------------------------------------------------------------------------------------------------%
%--------------------------------------------------------------------------------------------------------------
% 2.0 主程序
%遗传算法主程序
%Name:genmain05.m
%要求精度不大于0.01，
function []=yichuan()
popsize=20; %群体大小
chromlength=10; %字符串长度(个体长度)
pc=0.6; %交叉概率，只有在随机数小于pc时，才会产生交叉
pm=0.001; %变异概率
pop=initpop(popsize,chromlength); %随机产生初始群体
for i=1:20 %20为遗传代数
[objvalue]=calobjvalue(pop); %计算目标函数
fitvalue=calfitvalue(objvalue); %计算群体中每个个体的适应度
[newpop]=selection(pop,fitvalue); %复制
[newpop1]=crossover(newpop,pc); %交叉
[newpop2]=mutation(newpop1,pc); %变异
[objvalue]=calobjvalue(newpop2); %计算目标函数
fitvalue=calfitvalue(objvalue); %计算群体中每个个体的适应度
[bestindividual,bestfit]=best(newpop2,fitvalue); %求出群体中适应值最大的个体及其适应值
y(i)=bestfit; %返回的 y 是自适应度值，而非函数值
x(i)=decodechrom(bestindividual,1,chromlength)*10/1023; %将自变量解码成十进制
pop=newpop2;
end
fplot(@(x)10.*sin(5.*x)+7.*cos(4.*x))
hold on
plot(x,y,'r*')
hold on
[z, index]=max(y); %计算最大值及其位置
x5=x(index) %计算最大值对应的x值
ymax=z
% 2.1初始化(编码)
% initpop.m函数的功能是实现群体的初始化，popsize表示群体的大小，chromlength表示染色体的长度(二值数的长度)，
% 长度大小取决于变量的二进制编码的长度(在本例中取10位)。
function [pop]=initpop(popsize,chromlength)
pop=round(rand(popsize,chromlength));
% rand随机产生每个单元为 {0,1} 行数为popsize，列数为chromlength的矩阵，
% round对矩阵的每个单元进行圆整。这样产生的初始种群。
% 2.2.3 计算目标函数值
% calobjvalue.m函数的功能是实现目标函数的计算，其公式采用本文示例仿真，可根据不同优化问题予以修改。
%遗传算法子程序
%Name: calobjvalue.m
%实现目标函数的计算，将 二值域 中的数转化为 变量域的数
function [objvalue]=calobjvalue(pop)
temp1=decodechrom(pop,1,10); %将pop每行转化成十进制数
x=temp1*10/1023; %在精度不大于0.01时，最小整数为1023，即需要10位二进制
objvalue=10*sin(5*x)+7*cos(4*x); %计算目标函数值
% 2.3 计算个体的适应值
%遗传算法子程序
%Name:calfitvalue.m
%计算个体的适应值
function fitvalue=calfitvalue(objvalue)
[px,~]=size(objvalue); %目标值有正有负
for i=1:px
if objvalue(i)>0
temp=objvalue(i);
else
temp=0.0;
end
fitvalue(i)=temp;
end
fitvalue=fitvalue';
% 2.4 选择复制
% 选择或复制操作是决定哪些个体可以进入下一代。程序中采用赌轮盘选择法选择，这种方法较易实现。
% 根据方程 pi=fi/∑fi=fi/fsum ，选择步骤：
% 1） 在第 t 代，由（1）式计算 fsum 和 pi
% 2） 产生 {0,1} 的随机数 rand( .)，求 s=rand( .)*fsum
% 3） 求 所有fi≥s 中最小的 k ，则第 k 个个体被选中
% 4） 进行 N 次2）、3）操作，得到 N 个个体，成为第 t=t+1 代种群
%遗传算法子程序
%Name: selection.m
%选择复制
function [newpop]=selection(pop,fitvalue)
totalfit=sum(fitvalue); %求适应值之和
fitvalue=fitvalue/totalfit; %单个个体被选择的概率
fitvalue=cumsum(fitvalue); %如 fitvalue=[1 2 3 4]，则 cumsum(fitvalue)=[1 3 6 10]，不明白为什么要累加
[px,~]=size(pop); %20*10
ms=sort(rand(px,1)); %从小到大排列
fitin=1;
newin=1;
while newin<=px %选出20个新个体，有重复情况，和上面介绍的方法不太一样
if(ms(newin))<fitvalue(fitin)
newpop(newin,:)=pop(fitin,:);
newin=newin+1;
else
fitin=fitin+1;
end
end
% 2.5 交叉
% 交叉(crossover)，群体中的每个个体之间都以一定的概率 pc 交叉，即两个个体从各自字符串的某一位置
% （一般是随机确定）开始互相交换，这类似生物进化过程中的基因分裂与重组。例如，假设2个父代个体x1，x2为：
% x1=0100110,x2=1010001
% 从每个个体的第3位开始交叉，交又后得到2个新的子代个体y1，y2分别为：
% y1＝0100001,y2＝1010110
% 这样2个子代个体就分别具有了2个父代个体的某些特征。利用交又我们有可能由父代个体在子代组合成具有更高适合度的个体。
% 事实上交叉是遗传算法区别于其它传统优化方法的主要特点之一。
%遗传算法子程序
%Name: crossover.m
%交叉
function [newpop]=crossover(pop,pc) %pc=0.6
[px,py]=size(pop);
newpop=ones(size(pop));
for i=1:2:px-1 %步长为2，是将相邻的两个个体进行交叉
if(rand<pc)
cpoint=round(rand*py);
newpop(i,:)=[pop(i,1:cpoint),pop(i+1,cpoint+1:py)];
newpop(i+1,:)=[pop(i+1,1:cpoint),pop(i,cpoint+1:py)];
else
newpop(i,:)=pop(i,:);
newpop(i+1,:)=pop(i+1,:);
end
end
% 2.6 变异
% 变异(mutation)，基因的突变普遍存在于生物的进化过程中。变异是指父代中的每个个体的每一位都以概率 pm 翻转，
%即由“1”变为“0”，或由“0”变为“1”。
%遗传算法的变异特性可以使求解过程随机地搜索到解可能存在的整个空间，因此可以 在一定程度上 求得全局最优解。
%遗传算法子程序
%Name: mutation.m
%变异
function [newpop]=mutation(pop,pm)
[px,py]=size(pop);
newpop=ones(size(pop));
for i=1:px
if(rand<pm)
mpoint=round(rand*py); %产生的变异点在1-10之间
if mpoint<=0
mpoint=1; %变异位置
end
newpop(i,:)=pop(i,:);
if any(newpop(i,mpoint))==0
newpop(i,mpoint)=1;
else
newpop(i,mpoint)=0;
end
else
newpop(i,:)=pop(i,:);
end
end
% 2.7 求出群体中最大得适应值及其个体
%遗传算法子程序
%Name: best.m
%求出第 t 代群体中适应值最大的值
function [bestindividual,bestfit]=best(pop,fitvalue)
[px,~]=size(pop);
bestindividual=pop(1,:);
bestfit=fitvalue(1);
for i=2:px
if fitvalue(i)>bestfit
bestindividual=pop(i,:);
bestfit=fitvalue(i);
end
end
% 2.2 计算目标函数值
% 2.2.1 将二进制数转化为十进制数(1)
%遗传算法子程序
%Name: decodebinary.m
%产生 [2^n 2^(n-1) ... 1] 的行向量，然后求和，将二进制转化为十进制
function pop2=decodebinary(pop)
[~,py]=size(pop); %求pop行和列数
for i=1:py
pop1(:,i)=2.^(py-i).*pop(:,i);
end
pop2=sum(pop1,2); %求pop1的每行之和
% 2.2.2 将二进制编码转化为十进制数(2)
% decodechrom.m函数的功能是将染色体(或二进制编码)转换为十进制，参数spoint表示待解码的二进制串的起始位置
% (对于多个变量而言，如有两个变量，采用20为表示，每个变量10为，则第一个变量从1开始，另一个变量从11开始。本例为1)，
% 参数1ength表示所截取的长度（本例为10）。
%遗传算法子程序
%Name: decodechrom.m
%将二进制编码转换成十进制
function pop2=decodechrom(pop,spoint,length) %1 10
pop1=pop(:,spoint:spoint+length-1);
pop2=decodebinary(pop1); %将pop每行转换成十进制值，结果是20*1的矩阵
