经典遗传算法及MATLAB实例
经典遗传算法及简单实例（MATLAB）
1. 遗传算法简单介绍
1.1 理论基础
整个算法的基础就是达尔⽂的⽣物进化论，“物竞天择，适者⽣存” 这句话已经是常识了。
⽤雪兔做⼀个引⼦吧：
东北那旮瘩，有原始雪兔，刚从未知物种进化⽽来，五颜六⾊（表现型）漂亮极了，称之为 I(0)。
（注意：种初始化）
⼊夏了，雪兔们出来觅⾷，浅⾊兔在草地中⽆所遁形，被雪狐收割了⼀波（⼤批浅⾊+⼩批深⾊）。
⼊冬了，雪兔们出来觅⾷，深⾊兔在雪地中光彩夺⽬，被雪狐收割了⼀波（⼤批深⾊+⼩批浅⾊）。
（注意：⾃然选择过程）
春天到了，⼜到了兔兔们⽣孩的季节，雪兔们染⾊体内的基因进⾏ 重组/不重组 ，产⽣⼀批受精卵。
（注意：交叉遗传过程）
受精卵内的⽣命活动⾮常强烈，造成了基因的 突变/不突变，产⽣了各种各样奇怪的⼩雪兔。
（注意：基因变异过程）
⽼雪兔们完成了⾃⼰繁衍的使命，全部不知所踪。留下新⽣代，继续在各种威胁下苟活，这⼀代叫 I(1)。
再次⼊冬⼊夏，雪兔们⼜出来觅⾷。。。。。。再次⼊冬，觅⾷。。。。。。⼊冬，觅⾷。。。。。。
就这样，50年后，基因突变和重组造就了种神奇的兔⼦：夏天褐⾊，冬天⽩⾊，可以轻易躲避雪狐的追捕
再次⼊冬⼊夏，雪兔们⼜出来觅⾷。。。。。。再次⼊冬，觅⾷。。。。。。⼊冬，觅⾷。。。。。。
这样，50年后，雪地⾥基本上见不到五颜六⾊的雪兔了，这时候雪兔们达到了兔⽣巅峰！
这就是遗传算法的理论基础，⾃然选择、交叉、变异、迭代，最终获得最优解。
注意：算法是根据表现型来进⾏选择，最终选出最优的表现型及其对应的基因。
1.2 算法要点
1.1 编码
编码是为了把我们的输⼊参数变成染⾊体（每个个体只有⼀条染⾊体），以便于进⾏交叉和遗传运算。
例如我们把雪兔的颜⾊进⾏划分， 0-255 （表现型）代表 ⿊->⽩ 的不同程度，0就是纯⿊的，255就是纯⽩的。我们这⾥只谈⼀下简单的⼆进制编码，⼆进制编码中的每⼀个⼆进制位是⼀个基因，整个数字为染⾊体。
那么0-255共有256阶（表现型），我们可以⽤8位2进制数来表⽰（基因型）。
兔⾊为0的编码为 00000000，兔⾊为2的编码为 00000010，兔⾊为255的编码为 11111111。
1.2 适应度函数
适应度函数就是个体对环境的适应度，适应度越强的越能产⽣后代，保留⾃⼰的基因及表现型。
这⾥，我们假设灰⾊兔⼦的适应能⼒最强，即兔⾊为128的兔⼦不会被吃掉，设定函数为：
是⼀个最⼤值为128的分段函数，图像如下：
适应度函数的极值点⼀般是未知的，这⾥我们为了演⽰⽅便，就先展⽰出来。
1.3 基本流程
流程就和雪兔故事⼀样简单，如下所⽰：
注意：迭代的终⽌条件可以不是最⼤迭代次数，⽐如规定为种适应度值的⽅差⼩于某个值（即种表现型趋于⼀致）。
2. 代码实例（MATLAB）
2.1 代码汇总
遗传算法代码（通⽤代码）：
function [bestChromosome,fitnessBest]=GA(numOfChromosome,numOfGene,iterationNum)
%% 函数功能：执⾏基于⾃适应遗传算法的卸载决策
%  输⼊：
%      numOfChromosome：染⾊体数量，即迭代的种⼤⼩
%      numOfGene：基因的数量，即所⽤⼆进制编码的位数
%      iterationNum：迭代的总次数，达到迭代次数即终⽌迭代
%  输出：
%      bestChromosome：最优的染⾊体（即最优的输⼊）
%      fitnessBest：最优的适应度值（即最优的结果）
%% 随机⽣成初始种，种⼤⼩为numOfChromosome，染⾊体中基因数为numOfGene
% lastPopulation：上⼀代的种（染⾊体）
% newPopulation：新⼀代的种（染⾊体）
% randi([0,1])会产⽣0或1的整数
lastPopulation=randi([0,1],numOfChromosome,numOfGene);
newPopulation=zeros(numOfChromosome,numOfGene);
%% 进⾏遗传迭代，直⾄达到最⼤迭代次数iterationNum
for iteration=1:iterationNum
%% 计算所有个体（染⾊体）的适应度，⼀共有numOfChromosome个适应度值
fitnessAll=zeros(1,numOfChromosome);
for i=1:numOfChromosome
individual=lastPopulation(i,:);
fitnessAll(i)=fitnessFunc(individual);
end
%% 如果达到最⼤迭代次数，跳出（不能再进⾏选择遗传和变异了）
if iteration==iterationNum
break;
end
%% 使⽤赌法选择numOfChromosome条染⾊体，种中个体总数不变
fitnessSum=sum(fitnessAll);
fitnessProportion=fitnessAll/fitnessSum;
% 使⽤随机数进⾏numOfChromosome次选择，保持种中个体数量不变
for i=1:numOfChromosome
probability=rand(1);
proportionSum=0;
chromosomeIndex=1;
for j=1:numOfChromosome
proportionSum=proportionSum+fitnessProportion(j);
if proportionSum>=probability
chromosomeIndex=j;
break;
end
end
newPopulation(i,:)=lastPopulation(chromosomeIndex,:);
newPopulation(i,:)=lastPopulation(chromosomeIndex,:);
end
%% 将染⾊体进⾏配对，执⾏单点交叉
lastPopulation=newPopulation;
% ⽣成从1到numOfChromosome的⽆序排列，每两个相邻数字进⾏配对
coupleAllIndex=randperm(numOfChromosome);
for i=1:floor(numOfChromosome/2)
coupleOneIndex=coupleAllIndex(2*i-1:2*i);
% 定义两条染⾊体交叉的概率，⾃⼰选择
probability=0.6;
% 如果⽣成的随机数在交叉概率内，执⾏交叉操作
if rand(i)<probability
% 随机⽣成交叉的基因点，将两条基因进⾏交叉
crossPosition=randi([1,numOfGene],1);
newPopulation(coupleOneIndex(1),crossPosition:end)=lastPopulation(coupleOneIndex(2),crossPosition:end);            newPopulation(coupleOneIndex(2),crossPosition:end)=lastPopulation(coupleOneIndex(1),crossPosition:end);        end
end
%% 对每条染⾊体执⾏基本位变异操作
lastPopulation=newPopulation;
for i=1:numOfChromosome
% 定义染⾊体变异的概率，⾃⼰选择
probability=0.2;
% 如果⽣成的随机数在变异概率内，执⾏变异操作
if rand(1)<probability
% 选择变异的位置
mutatePosition=randi([1,numOfGene],1);
% 将对应基因位置的⼆进制数反转
if(lastPopulation(i,mutatePosition)==0)
newPopulation(i,mutatePosition)=1;
else
newPopulation(i,mutatePosition)=0;
end
end
end
%% 完成了⼀次迭代，更新种
lastPopulation=newPopulation;
end
%% 遗传迭代结束后，获得最优适应度值和对应的基因
fitnessBest=max(fitnessAll);
bestChromosome=newPopulation(find(fitnessAll==fitnessBest,1),:);
雪兔例⼦的适应度计算代码：
function fitness=fitnessFunc(chromosome)
%% 函数功能：计算染⾊体的表现型及其适应度
% 输⼊：
%      chromosome：染⾊体的基因序列
% 输出：
%      fitness：染⾊体（个体）的适应度值
%% 计算雪兔染⾊体对应表现型
len=length(chromosome);
numList=2.^(len-1:-1:0);
x=sum(chromosome.*numList);
%% 计算表现型对应的适应度
if x<128
fitness=x;
else
if x>128
fitness=256-x;
else
fitness=128;
end
end
2.1 初始化种
%% 随机⽣成初始种，种⼤⼩为numOfChromosome，染⾊体中基因数为numOfGene
% lastPopulation：上⼀代的种（染⾊体）
% newPopulation：新⼀代的种（染⾊体）
% randi([0,1])会产⽣0或1的整数
lastPopulation=randi([0,1],numOfChromosome,numOfGene);
newPopulation=zeros(numOfChromosome,numOfGene);
这⾥使⽤随机数⽣成函数⽣成了numOfChromosome条染⾊体，每条染⾊体有numOfGene个基因。将⽣成的种放⼊lastPopulation中，每⼀⾏是⼀条染⾊体。
newPopulation相当于⼀个辅助数组，存储⽣成种的中间结果。
2.2 计算适应度
matlab生成随机数%% 计算所有个体（染⾊体）的适应度，⼀共有numOfChromosome个适应度值
fitnessAll=zeros(1,numOfChromosome);
for i=1:numOfChromosome
individual=lastPopulation(i,:);
fitnessAll(i)=fitnessFunc(individual);
end
计算种中所有个体的适应度，即把每⼀条染⾊体（个体）都放⼊适应度函数中，得到适应度结果。2.3 迭代终⽌判断
%% 如果达到最⼤迭代次数，跳出（不能再进⾏选择遗传和变异了）
if iteration==iterationNum
break;
end
计算完适应度，如果达到终⽌条件，就不再进⾏选择、遗传和变异了。
否则你跳出循环时，种适应度与计算的的适应度不匹配。
另⼀种⽅案：执⾏选择、遗传、变异，跳出循环后再次计算适应度即可。
2.4 ⾃然选择（赌法）
%% 使⽤赌法选择numOfChromosome条染⾊体，种中个体总数不变
fitnessSum=sum(fitnessAll);
fitnessProportion=fitnessAll/fitnessSum;
% 使⽤随机数进⾏numOfChromosome次选择，保持种中个体数量不变
for i=1:numOfChromosome
probability=rand(1);
proportionSum=0;
chromosomeIndex=1;
for j=1:numOfChromosome
proportionSum=proportionSum+fitnessProportion(j);
if proportionSum>=probability
chromosomeIndex=j;
break;
end
end
newPopulation(i,:)=lastPopulation(chromosomeIndex,:);
end
计算每个个体适应度占总适应度的⽐例，总适应度是⼀个饼图，每个个体占据⼀定的扇形区域。
然后⽣成numOfChromosome个0-1的随机数，随机数落在哪个区域，哪个个体便被⽣存，可重复选择。显然，适应度⾼的个体容易被选择，将⾃⼰的基因和表现型遗传下去。
2.5 配对交叉（单点）
%% 将染⾊体进⾏配对，执⾏单点交叉
lastPopulation=newPopulation;
% ⽣成从1到numOfChromosome的⽆序排列，每两个相邻数字进⾏配对
coupleAllIndex=randperm(numOfChromosome);
for i=1:floor(numOfChromosome/2)
coupleOneIndex=coupleAllIndex(2*i-1:2*i);
% 定义两条染⾊体交叉的概率，⾃⼰选择
probability=0.6;
% 如果⽣成的随机数在交叉概率内，执⾏交叉操作
if rand(i)<probability
% 随机⽣成交叉的基因点，将两条基因进⾏交叉
crossPosition=randi([1,numOfGene],1);
newPopulation(coupleOneIndex(1),crossPosition:end)=lastPopulation(coupleOneIndex(2),crossPosition:end);            newPopulation(coupleOneIndex(2),crossPosition:end)=lastPopulation(coupleOneIndex(1),crossPosition:end);        end
end
进⾏遗传的前提是配对，每两条染⾊体组合成⼀对，将两者的部分染⾊体进⾏交换。
单点交叉，顾名思义，选择染⾊体上的⼀个基因点，从这个基因点开始的两条染⾊体⽚段互换：
2.6 变异（基本位变异）

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。