遗传的概念：

• 遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

遗传算法的特点：

• 对于搜索算法的共同特征有
  • 首先组成一组候选解。
  • 依据某些使用性条件测算这些候选解的适用度。
  • 根据适应度保留某些候选解，放弃其他候选解。
  • 对保留的候选解进行某些操作，形成新的候选解。
• 由于遗传算法是搜选算法的一种，因此具有以上特点，另外遗传算法还有自身的特有特点：
  • 遗传算法是从问题解的束集（多个候选解）而不是单个解开始，这是与传统优化算法的最大区别。
  • 遗传算法同时处理群体中多个个体，有利于并行结算
  • 遗传算法基本上不同搜索空间，使得其应用范围比较大。
  • 遗传算法不采用确定性规则，而是采用概率变迁规则来指导它的搜索方向。

遗传算法中的术语

• 染色体(chromosome)：染色体是基因型个体（individuals）,一定数量的个体组成了群体（population），群体中的数量称为群体大小
• 基因(gene)：基因是串中的元素，基因用于表示个体的特征，例如一个串S=1011，则其中的1，0，1，1这4个元素称为基因，他们呢的值称为等位基因(alleles)。
• 基因位点(locus)：基因位点是一个基因在串中的位置
• 特征值(feature)：基因的特征值与二进制的权一致。
• 适应度(fitness)：各个个体对环境的适应程度称为适应度，使用适应度函数来量化适应度。

遗传算法的原理

• 遗传算法流程图

---

• 选择:选择优胜个体，淘汰劣质个体的操作叫做选择，其是建立在个体适应度评估的基础之上的，其方法有轮盘式选择法，随机遍历抽样法和局部选择法，对于轮盘赌选择法，每个个体被选择的概率跟适应度成正比，即：$p_i=\frac{f_i}{{\sum }_{j=1}^n{f}_i}$。计算出个体的选择概率之后，为了交配个体，需要进行多轮选择，每一轮产生一个[0,1]之间的均匀随机数最为选择指针来确定被选个体；个体被选后，可以随机组成交配对。
• 交叉:所谓交叉就是将两个父代个体的部分结构加以替换重组生成新的个体的操作，交叉算法有
  • 实值重组
  • 二进制交叉
    最常用的是二进制交叉中的单点交叉，即随机的将两个个体串中一个交叉点前面或者后的部分结构进行呼唤，生成两个新的个体
• 变异:变异就是按照变异率随机挑选出一个或者多个基因位，将这些基因位取反，通常变异率比较低，为0.001~0.1。
• 终止条件：当最优个体的适应度达到给定阈值或者最优个体的适应度和群体的适应度不在上升时，或者迭代次数达到预设次数时，算法终止，一般预设代数为100~500代。

---

• 适应度函数的选择
  适应度函数的设计应该满足以下条件
  • 单值，连续，非负，最大化
  • 合理，一致性
  • 计算量小
  • 通用性强
• 初始群体的选取
  初始群体是随机产生的。

程序设计

例如求函数$f(x)=10\ast sin(5x)+7\ast cos(4x),x\in [0,10]$的最大值

• 解：
  • 初始化：

  function pop = initpop( popsize, chromlength )pop=round(rand(popsize,chromlength));%rand随机产生每个元素为0~1之间的小数，行数为popsize,列数为chromlength的矩阵%%round对矩阵每个元素进行四舍五入使得结果0或者1%
  end
  

  • 目标函数值

  %二进制转化为十进制%
  function pop2 = decodebinary(pop )[rows,cols] = size(pop);%求取pop的行数与列数%for i=1:colspop1(:,i)=2.^(cols-i).*pop(:,i);endpop2=sum(pop1,2);%求pop1的每行之和%
  end
  

  %其作用是将染色体或者二进制编码转换为十进制
  %其中参数spoint表示带解码的二进制串的起始位置
  %length表示所截取的长度
  function pop2= decodechrom(pop,spoint,length)pop1=pop(:,spoint:spoint+length-1);pop2=decodebinary(pop1);
  end
  

  %其功能是计算目标函数值
  function [objvalue] = calobjvalue(pop,length)temp=decodechrom(pop,1,length);%将pop每行转化为10进制数x=temp*10/(power(2,length)-1);%将每行的二进制域中的数转化为变量域的数objvalue=10*sin(5*x)+7*cos(4*x);%计算目标函数值
  end
  

• 适应度值

  %计算个体的适应值
  function fitValue= calfitvalue( objValue)fitValue=objValue+100;%根据情况设计适应度计算函数
  end
  

• 交叉操作

  %交叉操作函数
  function [ newpop] = crossover(pop,pc)[rows,cols]=size(pop);newpop=zeros(2*rows,cols);index=1;for i=1:rowsother=i;if(rand<pc) %每个个体被选择执行交叉的概率相同   while other==iother=1+floor(rand*rows);%随机选择一个交叉对象endcpoint=floor(rand*cols)+1;%随机选择一个交叉点%执行交叉newpop(i,:)=[pop(i,1:cpoint),pop(other,cpoint+1:cols)];newpop(rows+index,:)=[pop(other,1:cpoint),pop(i,cpoint+1:cols)];index=index+1;elsenewpop(i,:)=pop(i,:);endendnewpop=newpop(1:rows+index-1,:);%由于初始化的行数是2*rows，但是实际赋值的行数是index-1行。
  end
  

• 变异操作

  %变异操作
  function newpop = mutation( pop,pm)[rows,cols]=size(pop);newpop=ones(size(pop));for i=1:rowsnewpop(i,:)=pop(i,:);if rand<pm%如果随机数小于变异概率，则选择一个变异点，将本条染色体变异mpoint=round(rand*cols);%随机选择变异点if mpoint<=0%防止生成的变异点为0mpoint=1;endif newpop(i,mpoint)==0%如果原变异点是0则变异为1，否则变异为0.newpop(i,mpoint)=1;elsenewpop(i,mpoint)=0;end   endend
  end
  

• 选择下一代的个体

  %选择N个个体进入下一代，筛选的原理是适应度高的的个体有更高的概率被选中。
  function newPop = selection(pop,fitValue,N )totalFit=sum(fitValue);fitValue=fitValue/totalFit;%单个个体被选择的概率fitValue=cumsum(fitValue);%输出中每个元素的输入中对应元素的前面所有元素之和[rows,cols]=size(pop);newPop=zeros(N,cols);isSelected=zeros(1,rows);%记录是否被选中newin=1;while newin<Np=rand;for i=1:rowsif ((isSelected(1,i)==0) && (p<=fitValue(i)))isSelected(1,i)=1;newin=newin+1;newPop(newin,:)=pop(i,:);break;endendend  
  end
  

• 记录适应度最高的个体

  %本次迭代中，选择适应度最高的个体以及其值
  function [bestIndividual,bestValue] = best( pop,fitValue,objValue)[rows,cols]=size(pop);bestIndividual=pop(1,:);bestFit=fitValue(1);for i=2:rowsif fitValue(i)>bestFitbestIndividual=pop(i,:);bestFit=fitValue(i);bestValue=objValue(i);endend
  end
  

• 主函数

  function []= main( )clear;popSize=20;%种群数量chromLength=10;%染色体长度pc=0.7;%交叉概率pm=0.005;%变异概率iterators=200;%迭代次数pop=initpop(popSize,chromLength);%初始化种群y=zeros(1,iterators);x=zeros(1,iterators);maxValue=zeros(1,iterators);%记录每次迭代的最大值for i=1:iteratorsnewPop=crossover(pop,pc);%交叉newPop=mutation(newPop,pm);%变异objValue=calobjvalue(newPop,chromLength);%计算个体目标函数值fitValue=calfitvalue(objValue);%计算个体适应度[bestIndividual,bestValue]=best(newPop,fitValue,objValue);%挑选适应度最高的个体y(i)=bestValue;maxValue(1,i)=max(y);%每次迭代都将本次迭代中的适应度最高的个体值记录下来x(i)=decodechrom(bestIndividual,1,chromLength)*10/1023;%记录本次迭代中适应度最高的个体的变量域中的值pop=selection(newPop,fitValue,popSize);%选择下一代个体endfplot('10*sin(5*x)+7*cos(4*x)',[0,15]);hold on;plot(x,y,'r *');hold off;plot(maxValue);
  end
  

• 运行结果
  • 每次迭代的最大值在原函数图像中的位置
    
    由于每次迭代的最大值并不一定比前面迭代的最大值大，所以在记录最大值的向量里会有一些值重复。
  • 每次迭代的最大值变化情况
    
    看可以看到随着迭代的次数增加，很快就收敛到最大值附近。