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

模拟退火遗传算法的研究及应用模拟退火遗传算法的研究及应用xyABC0y=f(x)一般算法的问题：1）对函数本身有要求（连续性，可微性）2）限于局部最优解Q：如何实现针对一般问题的全局搜索？D案例索引xyABC0y=f(x)一般算法的问题：Q：如何实现针对一般 1遗传算法理论(GA)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)遗传算法伪代码*Pc：交叉发生的概率 2案例应用 2案例应用物流配送中心选址问题Q：选哪几个作为物流配送中心使在需求满足的情况下成本最低。需求点10个供给点3个待选物流配送中心6个物流配送中心选址问题Q：选哪几个作为物流配送中心使在需求满足假设某物流公司有3个供货点Q1，Q2和Q3，可供资源分别为A1=40，A2=60，A3=50；有10个用户H1，H2，H10，需求量Dj（j=1,2，10），固定成本为Fi，容量限制为Wi，变动成本率为Vi，相关数据见下表。1、配送中心到需求点的单位成本及需求量表2、供货点到配送中心的单位成本表3、配送中心相关成本及容量限制表物流配送中心选址问题假设某物流公司有3个供货点Q1，Q2和Q3，可供资源分别为A模型构建约束条件：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）配送中心的可变成本为流量的线性函数。模型构建约束条件：m：供货点的个数;基本假设:编码初始群体1选择0110%29%37%22%1#2#4#6#3#0%2%5#适应度函数轮盘赌选择编码 初始群体 1选择0110%29%37%22%12交叉n交叉概率：0.8n交叉方式：单点交叉2 交叉 交叉概率：0.83变异n变异概率：0.05n变异方式：基本位变异3 变异 变异概率：0.05MATLAB遗传算法工具箱操作n打开工具箱：键入命令：gatool点击命令：MATLAB遗传算法工具箱操作 打开工具箱：MATLAB遗传算法工具箱操作参数适应值函数约束条件图形显示界面MATLAB遗传算法工具箱操作参数适应值函数约束条件图形显示functionMain()%定义全局变量globalVariableNumPOPSIZEMaxGensPXOVERPMutationVariableNum=6%变量个数POPSIZE=10%种群大小MaxGens=100%种群代数PXOVER=0.8%交叉概率PMutation=0.05%变异概率%读取数据文件loadE:现代优化算法遗传算法bound.txtVarBound=bound(:,1:2);globalPopnewPopPop=zeros(POPSIZE+1,VariableNum);newPop=zeros(POPSIZE+1,VariableNum);%初始化种群fori=1:POPSIZEforj=1:VariableNumPop(i,j)=rand(1);endend%计算适应值fitnessList=zeros(POPSIZE,1);fori=1:POPSIZEfitnessList(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;whilegenetationMaxGens%计算适应度区间sumfit=sum(abs(fitnessList);relativeFitness=zeros(POPSIZE,1);relativeFitness=abs(fitnessList)/sumfit;fori=2:POPSIZErelativeFitness(i)=relativeFitness(i-1)+relativeFitness(i);end%选择操作newPop=Select(Pop,relativeFitness);%交叉操作newPop=Xcross(newPop,VariableNum,PXOVER);%变异操作newPop=Mutation(newPop,VariableNum,PMutation,VarBound);%计算新种群适应值fori=1:POPSIZEfitnessList(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);ifBestmaxvalueBest(1,1:VariableNum)=newPop(indexMax,1:VariableNum);Best(1,VariableNum+1)=maxvalue;elsenewPop(indexMin,1:VariableNum)=Best(1,1:VariableNum);fitnessList(indexMin,1)=Best(1,VariableNum+1);end%用子代替换父代Pop=newPop;genetation=genetation+1;endBest%选择操作functionnewPop=Select(Pop,Rfitness)fori=1:length(Rfitness)r=rand();index=1;forj=1:length(Rfitness)ifr=Rfitness(j,1)index=j;break;endendnewPop(i,:)=Pop(index,:);end%交叉操作functionnewPop=Xcross(Pop,VariableNUM,CrossRate)point=1;sizePop=length(Pop);fori=0:sizePop/2Xrate=rand();ifXrate1ifVariableNUM=2point=1;elsepoint=round(rand()*(VariableNUM-2)+1);endtempOne=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);endendendnewPop=zeros(size(Pop),1);newPop=Pop;%变异操作functionnewPop=Mutation(Pop,VariableNUM,MutationRate,bound)point=1;sizePop=length(Pop);fori=1:sizePopforj=1:VariableNUMMrate=rand();ifMrateMutationRate%如果发生变异IfPop(i,j)=0;thenPop(i,j)=1;ElseifPop(i,j)=1;thenPop(i,j)=0;endendendnewPop=zeros(size(Pop),1);newPop=Pop;function Main()%定义全局变量global V算法结果结果：选择W1,W2,W4,W5,W6f=2280经典遗传算法的问题：n早熟（过早收敛）n收敛速度在搜索接近最优解时会显著降低而陷入迟钝状态等与模拟退火算法结合改进遗传算法xyABC0y=f(x)DEF算法结果结果：选择W1,W2,W4,W5,W6经典遗传算法的 3模拟退火算法(SA)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）连续若干步的目标值变化较小。状态产生函数原则：尽可能保证产生的候选解遍布全部的解空间一般方法：倒置、交换算法参数退火初始温度T0初始温度越高，搜索空间越大温度衰减函模拟退火流程图内循环外循环开始产生iS,k=0,Tk=T0，Tf设定内循环终止条件状态产生函数产生新解计算f=f(j)-f(i)f,U(0,1)内循环终止判断k=k+1,降温TkTk50maxpop=2*N-20;endifN=40maxpop=2*N;end%产生初始群体pop=zeros(maxpop,N);pop(:,1)=v0;finmin=inf;codmin=0;fori=1:maxpopRa=randperm(N);Ra(find(Ra=v0)=Ra(1);Ra(1)=v0;pop(i,:)=Ra;endt=t0;%转轮赌选择种群f=zeros(1,maxpop);fori=1:maxpopforj=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);fori=1:maxpopiffmin=inf&f(i)=infdd=inf;endiffmin=inf|f(i)=infdd=fmin-f(i);endftk(i)=exp(dd/t);endfin1,cod=sort(-ftk);fin=abs(fin1);%f(cod(1)iff(cod(1)=RR);%codnewpop(i,:)=pop(cod(cod2(end),:);end%ifN32jmax=round(N/9);endifNR1forj=1:2:jmax+2nn=randperm(N);x=nn(j);y=nn(j+1);whilet0%用模拟退火产生新的群体pop=fc1(maxpop,pop,N,cc,v0,t);ifnewpop(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;endfunctionpop=fc1(maxpop,pop,N,cc,v0,t)ff(N-1)=0;f=0;pop1=zeros(maxpop,N);fori=1:maxpopforj=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;ifpop(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);iff=inf&f1=infdd=inf;endiff=inf|f1=infdd=f-f1;endAij=min(1,exp(dd/t);Pacept=rand(1);ifAijPaceptpop(i,:)=pop1(i,:);endend模拟退火遗传算法伪代码%maxpop 给定群体规模%po模拟退火遗传算法（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；To9000.0T(t)=k*T(t-1)k=0.95t200遗传参数模拟退火参数编码方法个局部极大点f(2.048，-2.048)=3897.7342f(-2.048，-2.048）=3905.9262全局最大点Rosenbrock函数适应值函数原函数模拟退火遗传算法（GASA）实验用长度为10位的二进制编码串模拟退火遗传算法（GASA）实验模拟退火遗传算法（GASA）实验改进效果评估n每一个程序数据的采集采用算法程序连续运行25次（为一组），记录搜索到最优解所需的进化代数，在到终止代数（180代）还不能搜索到最优解的以180计n在进化速度和全局搜索能力上有重大突破n在本案例中进化速度上比基本遗传算法提高了3倍n有效地克服了基本遗传算法可能出现的早熟问题实验结果表GASA算法程序运行过程图像GA算法程序运行过程图像改进效果评估每一个程序数据的采集采用算法程序连续运行25次（