*,*,模拟退火遗传算法的研究及应用,模拟退火遗传算法的研究及应用,x,y,A,B,C,0,y=f(x),一般算法的,问题,：,1）对函数本身有要求（连续性，可微性）,2）限于局部最优解,Q,：如何实现针对一般问题的全局搜索？,D,案例索引,xyABC0y=f(x)一般算法的问题：Q：如何实现针对一般,1,遗传算法理论(GA),1遗传算法理论(GA),遗传算法的基本原理,生物进化原理,优化参数形成的,编码串联群体,优胜劣汰，适者生存,适应度函数,复制、交叉、变异,筛选,继承,优化,适应度高,遗传算法的基本原理生物进化原理优化参数形成的优胜劣汰，适者生,遗传算法流程图,编码方式,二进制编码,实数编码,非数值编码,格雷码编码,十进制编码,（随机）产生初始种群,是否满足停止准则,是,输出结果并结束,计算个体适应度值,选择运算,交叉运算,变异运算,否,产生新一代种群,编码,选择算子（23）,轮盘赌选择,排序选择,最优个体保存,随机联赛选择,交叉算子（17）,单点交叉,两点交叉,均匀交叉,算术交叉,变异算子,基本位变异,均匀变异,二元变异,高斯变异,适应度函数,一定的遗传代数,子代与夫代适应值稳定,算法终止条件,遗传算法流程图编码方式（随机）产生初始种群是否满足停止准则是,遗传算法的特点,自组织,、,自适应,和,智能性,；,直接处理的对象是,参数编码集,而不是问题参数本身；,搜索过程中使用的是,基于目标函数值的评价信息,，搜索过程既不受优化函数连续性的约束，也没有优化函数必须可导的要求；,易于,并行化,；,基本思想,简单,，运行方式和实现步骤,规范,，便于具体使用。,遗传算法的特点自组织、自适应和智能性；,遗传算法伪代码,*Pc：交叉发生的概率,*Pm：变异发生的概率,*M：种群规模,*G：终止进化的代数,*Tf：进化产生的任何一个个体的适应度函数超过Tf，则可以终止进化过程,*/,初始化Pm，Pc，M，G，Tf等参数。随机产生第一代种群Pop,do,计算种群Pop中每一个体的适应度F(i)。,初始化空种群newPop,do,根据适应度以比例选择算法从种群Pop中选出2个个体,if(random(0,1)Pc),对2个个体按交叉概率Pc执行交叉操作,if(random(0,1)Pm),对2个个体按变异概率Pm执行变异操作,将2个新个体加入种群newPop中,until(M个子代被创建),用newPop取代Pop,until(任何染色体得分超过Tf，或繁殖代数超过G),遗传算法伪代码*Pc：交叉发生的概率,2,案例应用,2案例应用,物流配送中心选址问题,Q,：选哪几个作为物流配送中心使在需求满足的情况下成本最低。,需求点,10,个,供给点,3,个,待选物流配送中心,6,个,物流配送中心选址问题Q：选哪几个作为物流配送中心使在需求满足,假设某物流公司有3个供货点Q,1,，Q,2,和Q,3,，可供资源分别为A,1,=40，A,2,=60，A,3,=50；有10个用户H,1,，H,2,，H,10,，需求量D,j,（j=1,2，10），固定成本为F,i,，容量限制为W,i,，变动成本率为V,i,，相关数据见下表。,1、配送中心到需求点的单位成本及需求量表,2、供货点到配送中心的单位成本表,3、配送中心相关成本及容量限制表,物流配送中心选址问题,假设某物流公司有3个供货点Q1，Q2和Q3，可供资源分别为A,模型构建,约束条件：,m：供货点的个数;,A,k,：第k 个供货点到配送中心的总供应量;,n：配送中心备选地址点的个数;,M,i,：配送中心备选地址点的最大容量;,P：配送中心允许选定个数的上限;,l：用户个数;D,为用户需求量;,c,ki,：由第k 个供货点到第i 个配送中心的单位运输成本;,x,ki,：由第k 个供货点到第i 个配送中心的运输量;,h,ij,：由第i 个配送中心到第j 个用户的单位运输成本;,X,ij,：第i 个配送中心到第j 个用户的运输量;,V,i,：第i 个配送中心的可变成本系数;,F,i,：第i 个配送中心的固定费;,W,i,：第i 个配送中心的流量。,基本假设:,1）由供货点到配送中心、由配送中心到用户的运费均为线性函数;,2）配送中心的可变成本为流量的线性函数。,模型构建约束条件：m：供货点的个数;基本假设:,编码,初始群体,1,选择,0,1,10%,29%,37%,22%,1,#,2,#,4,#,6,#,3,#,0%,2%,5,#,适应度函数,轮盘赌选择,编码 初始群体 1选择0110%29%37%22%1,2,交叉,交叉概率：0.8,交叉方式：单点交叉,2 交叉 交叉概率：0.8,3,变异,变异概率：0.,05,变异方式：基本位变异,3 变异 变异概率：0.05,MATLAB,遗传算法工具箱操作,打开工具箱：,键入命令：,gatool,点击命令：,MATLAB遗传算法工具箱操作 打开工具箱：,MATLAB,遗传算法工具箱操作,参数,适应值函数,约束条件,图形显示,界面,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;,function Main()%定义全局变量global V,算法结果,结果：选择W1,W2,W4,W5,W6,f=2280,经典遗传算法的,问题,：,早熟（过早收敛）,收敛速度在搜索接近最优解时会显著降低而陷入迟钝状态等,与模拟退火算法结合改进遗传算法,x,y,A,B,C,0,y=f(x),D,E,F,算法结果结果：选择W1,W2,W4,W5,W6经典遗传算法的,3,模拟退火算法(SA),3模拟退火算法(SA),模拟退火算法概述,固体,能量,较高状态,能量,较低状态,温度升高，固体,内部粒子逐渐变,为无序状态，,内能增大,温度缓慢降低，,粒子，逐