模拟退火遗传算法的研究及应用课件.ppt

模拟退火遗传算法的研究及应用xyABC0y=f(x)一般算法的问题：1）对函数本身有要求（连续性，可微性）2）限于局部最优解Q：如何实现针对一般问题的全局搜索？D案例索引 1 1遗传算法理论(GA)遗传算法的基本原理生物进化原理优化参数形成的编码串联群体优胜劣汰，适者生存适应度函数复制、交叉、变异筛选继承优化适应度高遗传算法流程图编码方式二进制编码实数编码非数值编码格雷码编码十进制编码（随机）产生初始种群是否满足停止准则是输出结果并结束计算个体适应度值选择运算交叉运算变异运算否产生新一代种群编码选择算子（23）轮盘赌选择排序选择最优个体保存随机联赛选择交叉算子（17）单点交叉两点交叉均匀交叉算术交叉变异算子 基本位变异均匀变异二元变异高斯变异适应度函数一定的遗传代数子代与夫代适应值稳定算法终止条件遗传算法的特点n自组织、自适应和智能性；n直接处理的对象是参数编码集,而不是问题参数本身；n搜索过程中使用的是基于目标函数值的评价信息，搜索过程既不受优化函数连续性的约束，也没有优化函数必须可导的要求；n易于并行化；n基本思想简单，运行方式和实现步骤规范，便于具体使用。遗传算法伪代码*Pc：交叉发生的概率*Pm：变异发生的概率*M：种群规模*G：终止进化的代数*Tf：进化产生的任何一个个体的适应度函数超过Tf，则可以终止进化过程*/初始化Pm，Pc，M，G，Tf等参数。随机产生第一代种群Popdo 计算种群Pop中每一个体的适应度F(i)。初始化空种群newPopdo根据适应度以比例选择算法从种群Pop中选出2个个体if(random(0,1)Pc)对2个个体按交叉概率Pc执行交叉操作if(random(0,1)Pm)对2个个体按变异概率Pm执行变异操作将2个新个体加入种群newPop中 until(M个子代被创建)用newPop取代Popuntil(任何染色体得分超过Tf，或繁殖代数超过G)2 2案例应用物流配送中心选址问题Q：选哪几个作为物流配送中心使在需求满足的情况下成本最低。需求点 10个供给点 3个待选物流配送中心 6个ki12345618711127629108788312610899假设某物流公司有3个供货点Q1，Q2和Q3，可供资源分别为A1=40，A2=60，A3=50；有10个用户H1，H2，H10，需求量Dj（j=1,2，10），固定成本为Fi，容量限制为Wi，变动成本率为Vi，相关数据见下表。ij12345678910175581032443267738893453107796788974889966554456657910433666886448655D20151020101015201020i123456Fi（固定成本）80601206090130Mi（容量限制）302040203550Vi（变动成本系数）7580807570801、配送中心到需求点的单位成本及需求量表2、供货点到配送中心的单位成本表3、配送中心相关成本及容量限制表物流配送中心选址问题模型构建约束条件：m：供货点的个数;Ak：第k 个供货点到配送中心的总供应量;n：配送中心备选地址点的个数;Mi：配送中心备选地址点的最大容量;P：配送中心允许选定个数的上限;l：用户个数;D,为用户需求量;cki：由第k 个供货点到第i 个配送中心的单位运输成本;xki：由第k 个供货点到第i 个配送中心的运输量;hij：由第i 个配送中心到第j 个用户的单位运输成本;Xij：第i 个配送中心到第j 个用户的运输量;Vi：第i 个配送中心的可变成本系数;Fi：第i 个配送中心的固定费;Wi：第i 个配送中心的流量。基本假设:1）由供货点到配送中心、由配送中心到用户的运费均为线性函数;2）配送中心的可变成本为流量的线性函数。编码 初始群体 1选择个体编号初始群体p(0)仓库选择点目标函数值适应值占总数百分比累计百分比选择次数选择结果1011111w2,w3,w4,w5,w631703300.10 0.10 11010112101111w1,w3,w4,w5,w6350000.00 0.10 01101113101011w1,w3,w5,w625489520.29 0.39 20111114110111w1,w2,w4,w5,w6228012200.37 0.76 21010115111011w1,w2,w3,w5,w63450500.02 0.78 01101116111101w1,w2,w3,w4,w627847160.22 1.00 11111010110%29%37%22%1#2#4#6#3#0%2%5#适应度函数轮盘赌选择2 交叉n 交叉概率：0.8n 交叉方式：单点交叉个体编号选择结果配对情况交叉点位置交叉结果约束条件筛选1101011123634101111101111211011111001111011130111110111110111114101011101011101011511011111010111011161111011111111111113 变异个体编号交叉结果变异点变异结果子代群体p（1）110111141010111010112110111/1100111100113011111/0111110111114101011/1010111010115110111/1101011101016111111/111111111111n 变异概率：0.05n 变异方式：基本位变异MATLAB遗传算法工具箱操作n 打开工具箱：键入命令：gatool 点击命令：MATLAB遗传算法工具箱操作参数适应值函数约束条件图形显示界面function Main()%定义全局变量global VariableNum POPSIZE MaxGens PXOVER PMutation VariableNum=6%变量个数POPSIZE=10%种群大小MaxGens=100%种群代数PXOVER=0.8%交叉概率PMutation=0.05%变异概率%读取数据文件load E:现代优化算法遗传算法bound.txtVarBound=bound(:,1:2);global Pop newPopPop=zeros(POPSIZE+1,VariableNum);newPop=zeros(POPSIZE+1,VariableNum);%初始化种群for i=1:POPSIZE for j=1:VariableNum Pop(i,j)=rand(1);endend%计算适应值fitnessList=zeros(POPSIZE,1);for i=1:POPSIZE fitnessList(i,1)=fitness(Pop(i,1:VariableNum);end%保存最好值和最坏值Best=zeros(1,VariableNum+1);Worst=zeros(1,VariableNum+1);maxvalue=max(fitnessList);indexMax=find(fitnessList=maxvalue,1,first);Best(1,1:VariableNum)=Pop(indexMax,1:VariableNum);Best(1,VariableNum+1)=maxvalue;minvalue=min(fitnessList);indexMin=find(fitnessList=minvalue,1,first);Worst(1,1:VariableNum)=Pop(indexMin,1:VariableNum);Worst(1,VariableNum+1)=minvalue;genetation=1;while genetationMaxGens%计算适应度区间 sumfit=sum(abs(fitnessList);relativeFitness=zeros(POPSIZE,1);relativeFitness=abs(fitnessList)/sumfit;for i=2:POPSIZE relativeFitness(i)=relativeFitness(i-1)+relativeFitness(i);end%选择操作 newPop=Select(Pop,relativeFitness);%交叉操作 newPop=Xcross(newPop,VariableNum,PXOVER);%变异操作 newPop=Mutation(newPop,VariableNum,PMutation,VarBound);%计算新种群适应值 for i=1:POPSIZE fitnessList(i,1)=fitness(newPop(i,1:VariableNum);end%保存最好值和替换最坏值 maxvalue=max(fitnessList);indexMax=find(fitnessList=maxvalue,1,first);minvalue=min(fitnessList);indexMin=find(fitnessList=minvalue,1,first);if Bestmaxvalue Best(1,1:VariableNum)=newPop(indexMax,1:VariableNum);Best(1,VariableNum+1)=maxvalue;else newPop(indexMin,1:VariableNum)=Best(1,1:VariableNum);fitnessList(indexMin,1)=Best(1,VariableNum+1);end%用子代替换父代 Pop=newPop;genetation=genetation+1;endBest%选择操作function newPop=Select(Pop,Rfitness)for i=1:length(Rfitness)r=rand();index=1;for j=1:length(Rfitness)if r=Rfitness(j,1)index=j;break;end end newPop(i,:)=Pop(index,:);end%交叉操作function newPop=Xcross(Pop,VariableNUM,CrossRate)point=1;sizePop=length(Pop);for i=0:sizePop/2 Xrate=rand();if Xrate1 if VariableNUM=2 point=1;else point=round(rand()*(VariableNUM-2)+1);end tempOne=zeros(1,point);tempOne(1,1:point)=Pop(first_index,1:point);Pop(first_index,1:point)=Pop(second_index,1:point);Pop(second_index,1:point)=tempOne(1,1:point);end endendnewPop=zeros(size(Pop),1);newPop=Pop;%变异操作function newPop=Mutation(Pop,VariableNUM,MutationRate,bound)point=1;sizePop=length(Pop);for i=1:sizePop for j=1:VariableNUM Mrate=rand();if MrateMutationRate%如果发生变异If Pop(i,j)=0;then Pop(i,j)=1;Elseif Pop(i,j)=1;then Pop(i,j)=0;end endendnewPop=zeros(size(Pop),1);newPop=Pop;算法结果结果：选择W1,W2,W4,W5,W6 f=2280经典遗传算法的问题：n早熟（过早收敛）n收敛速度在搜索接近最优解时会显著降低而陷入迟钝状态等与模拟退火算法结合改进遗传算法xyABC0y=f(x)DEF 3 3模拟退火算法(SA)模拟退火算法概述物理退火模拟退火物理退火模拟退火粒子状态解等温过程状态接受函数能量最低态最优解冷却控制参数的下降溶解过程设定初始温度能量目标函数固体能量较高状态能量较低状态温度升高，固体内部粒子逐渐变为无序状态，内能增大温度缓慢降低，粒子，逐渐恢复有机状态，内能降低加热降温实际模拟过程中，解空间相当于高温无序状态，最优解则为低温时的稳定状态算法参数退火初始温度T0初始温度越高，搜索空间越大温度衰减函数最常用的衰减函数：Tk+1=Tk一般取0.50.99，越大，退火速度越慢内循环终止条件状态接受函数状态接受函数原则：（1）在固定温度下,优化解概率大于劣化解概率;（2）随温度的下降,接受使目标函数值上升的解的概率要逐渐减小;通常采用Metropolis准则作为状态接受函数.外循环终止准则（1）零度法；（2）循环总数控制法；（3）基于不改进规则的控制法准则1:当连续若干次降温后,目标函数无改进,则外循环结束 40-200个准则2:当接受率小于给定的小正数e时,则认为已达到冷凝点 e=(0.0001,0.05)外循环终止条件内循环终止准则（1）设定一定的步数;（2）连续若干步的目标值变化较小。状态产生函数原则：尽可能保证产生的候选解遍布全部的解空间一般方法：倒置、交换模拟退火流程图内循环外循环开始产生iS,k=0,Tk=T0，Tf设定内循环终止条件状态产生函数产生新解计算f=f(j)-f(i)f,U(0,1)内循环终止判断k=k+1,降温TkTk50maxpop=2*N-20;endif N=40maxpop=2*N;end%产生初始群体pop=zeros(maxpop,N);pop(:,1)=v0;finmin=inf;codmin=0;for i=1:maxpopRa=randperm(N);Ra(find(Ra=v0)=Ra(1);Ra(1)=v0;pop(i,:)=Ra;endt=t0;%转轮赌选择种群 f=zeros(1,maxpop);for i=1:maxpopfor j=1:N-1x=pop(i,j);y=pop(i,j+1);fo1=cc(pop(i,j),pop(i,j+1);f(i)=f(i)+fo1;endf(i)=f(i)+cc(pop(i,1),pop(i,N);endfmin=min(f);for i=1:maxpopif fmin=inf&f(i)=infdd=inf;endif fmin=inf|f(i)=infdd=fmin-f(i);endftk(i)=exp(dd/t);endfin1,cod=sort(-ftk);fin=abs(fin1);%f(cod(1)if f(cod(1)=RR);%codnewpop(i,:)=pop(cod(cod2(end),:);end%if N32jmax=round(N/9);endif NR1for j=1:2:jmax+2nn=randperm(N);x=nn(j);y=nn(j+1);while t0%用模拟退火产生新的群体 pop=fc1(maxpop,pop,N,cc,v0,t);if newpop(i,x)=v0|newpop(i,y)=v0pop(i,:)=newpop(i,:);continue;endbox1=newpop(i,x);newpop(i,x)=newpop(i,y);newpop(i,y)=box1;pop(i,:)=newpop(i,:);endendend%温度下降t=t-0.1;endfunction pop=fc1(maxpop,pop,N,cc,v0,t)ff(N-1)=0;f=0;pop1=zeros(maxpop,N);for i=1:maxpopfor j=1:N-1x=pop(i,j);y=pop(i,j+1);ff(j)=cc(pop(i,j),pop(i,j+1);pop1(i,:)=pop(i,:);nn=randperm(N);x=nn(1);y=nn(2);pop1=pop;if pop(i,x)=v0|pop(i,x)=v0continuebox1=pop(i,x);pop1(i,x)=pop1(i,y);pop1(i,y)=box1;endff1(j)=cc(pop1(i,j),pop1(i,j+1);endf=sum(ff);f1=sum(ff1);if f=inf&f1=infdd=inf;endif f=inf|f1=infdd=f-f1;endAij=min(1,exp(dd/t);Pacept=rand(1);if AijPaceptpop(i,:)=pop1(i,:);endend 模拟退火遗传算法（GASA）实验用长度为10位的二进制编码串来分别表示两个决策变量x1，x2；将x1，x2的定义域离散化为1023个均等的区域，包括两个端点在内共1024个不同的离散点；从离散点2.048到离散点2.048，依次让它们分别对应于从0000000000(0)到1111111111(1023)之间的二进制编码；再将分别表示x1，x2两个10位长的二进制编码串连接起来，组成一个20位的二进制编码串。群体大小N=80；交叉运算使用单点交叉算子；交叉概率Pc=0.6；变异运算使用均匀变异算子；变异概率Pm=0.001；终止代数T=180；To9 000.0T(t)=k*T(t-1)k=0.95 t200遗传参数模拟退火参数编码方法个局部极大点f(2.048，-2.048)=3897.7342f(-2.048，-2.048）=3905.9262全局最大点Rosenbrock函数适应值函数原函数模拟退火遗传算法（GASA）实验改进效果评估n每一个程序数据的采集采用算法程序连续运行25次（为一组），记录搜索到最优解所需的进化代数，在到终止代数（180代）还不能搜索到最优解的以180计n在进化速度和全局搜索能力上有重大突破n在本案例中进化速度上比基本遗传算法提高了3倍n有效地克服了基本遗传算法可能出现的早熟问题GAGASA平均进化代数14855总体无最优解率72%6%实验结果表GASA 算法程序运行过程图像GA 算法程序运行过程图像