基础运筹学教程（第三版） 课件 - 第十一章 启发式算法 .ppt

*§11-3现代启发式算法一、遗传算法（四）范例2.路径表示法（5）交叉与变异(a)交叉算子②为得到后代o1，我们只需要移走p2中已在o1中的城市2、3和4后，得到5-1，并将该序列顺次放在o1中，并令p3=o1=（5,|2,3,4,|1），f(p3)=f(o1)=9+8+20+6+2=45类似地，为得到后代o2，令p4=o2=（2,|4,5,1,|3），f(p4)=f(o2)=13+5+2+15+8=43*§11-3现代启发式算法一、遗传算法（四）范例2.路径表示法（5）交叉与变异(b)比较评价函数值并排序，得：p4，p1，p2，p3。删除p2、p3，保留p4、p1，并依次复制到p1、p2，得p1={2,4,5,1,3}，p2={1,2,3,4,5}，f(p1)=1+3+2+2+2=43，f(p2)=1+2+2+2+4=45*§11-3现代启发式算法一、遗传算法（四）范例2.路径表示法（5）交叉与变异(c)变异算子采用倒置变异，即在染色体上随机地选择两点，将两点间的子串反转。如，原个体：p1={2,4,5,1,3}，p2={1,2,3,4,5}随机选择两点：p1={2,4,|5,1,|3},p2={1,|2,3,|4,5}倒置后得个体：p3={2,4,|1,5,|3},p4={1,|3,2,|4,5}f(p3)=13+6+2+15+8=44，f(p4)=15+8+13+5+2=43*§11-3现代启发式算法一、遗传算法（四）范例2.路径表示法（5）交叉与变异(d)比较评价函数值并排序，得：p1，p4，p3，p2。删除p3、p2，保留p1、p4，并依次复制到p1、p2，得p1={2,4,5,1,3}，p2=p4={1,3,2,4,5}，f(p1)=13+5+2+15+8=43，f(p2)=15+8+13+5+2=43（6）可对得到的p1、p2继续前述运算。若在此时结束计算，则得到的解为p1={2,4,5,1,3}，f(p1)=43。即此时的TSP回路为{2,4,5,1,3}，回路总长为43。*§11-3现代启发式算法二、模拟退火算法（一）基本思想模拟退火法SA的思想最早由Metropolis于1953年提出，Kirkpatrick在1983年成功地将其应用于组合最优化问题中。模拟退火算法源自物理学，其出发点是将组合优化问题与统计力学的热平衡作类比，把优化的目标函数视作能量函数，模拟物理学中固体物质的退火处理，先加温使之具有足够高的能量，然后再逐渐降温，其内部能量也相应下降，在热平衡条件下，物体内部处于不同状态的概率服从Boltzman分布，若退火步骤恰当，则最终会形成最低能量的基态。*§11-3现代启发式算法二、模拟退火算法（一）基本思想该算法思想在求解优化问题时，不但接受对目标函数(能量函数)有改进的状态，还以某种概率接受使目标函数恶化的状态，从而可使之避免过早收敛到某个局部极值点，也正是这种概率性的扰动，使之能够跳出局部极值点，故而得到的解常常很好。*§11-3现代启发式算法二、模拟退火算法（二）主要过程可用如下的伪码表示。其中，T(t)为降温函数，N(t)为邻域状态生成函数，其作用是产生反复次数。*§11-3现代启发式算法二、模拟退火算法（二）主要过程常用的降温函数和邻域状态生成函数形式有：T(t)=C；T(t)=T(t-1)