毕业设计之 |
您所在的位置：网站首页 › matlab最优化问题毕业论文 › 毕业设计之 |
毕业设计之
|
文章目录
前言1 退火算法原理1.1 物理背景1.2 背后的数学模型
2 退火算法实现2.1 算法流程2.2算法实现
3 退火算法在路径优化上的应用3.1 目标路径优化其他场景
最后 - 技术解答 - 毕设帮助
前言
毕设帮助，开题指导，资料分享，疑问解答(见文末) 模拟退火是一个通用的全局最优化算法。 常用在毕设项目中，比如最优路径的寻找等等。 什么是全局最优化解呢，可以打个比方： 一个锅底凹凸不平有很多坑的大锅，晃动这个锅使得一个小球使其达到全局最低点。一开始晃得比较厉害，小球的变化也就比较大，在趋于全局最低的时候慢慢减小晃锅的幅度，直到最后不晃锅，小球达到全局最低。本文章将向大家介绍退火算法的原理以及实现方法，并且在路径优化问题上进行应用，对该算法不理解以及需要源码及帮助的同学可以Q学长。 1 退火算法原理 1.1 物理背景在热力学上，退火（annealing）现象指物体逐渐降温的物理现象，温度愈低，物体的能量状态会低；够低后，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。大自然在缓慢降温（亦即，退火）时，可“找到”最低能量状态：结晶。但是，如果过程过急过快，快速降温（亦称「淬炼」，quenching）时，会导致不是最低能态的非晶形。 如下图所示，首先（左图）物体处于非晶体状态。我们将固体加温至充分高（中图），再让其徐徐冷却，也就退火（右图）。加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小（此时物体以晶体形态呈现）。
如果你对退火的物理意义还是晕晕的，没关系我们还有更为简单的理解方式。想象一下如果我们现在有下面这样一个函数，现在想求函数的（全局）最优解。如果采用Greedy策略，那么从A点开始试探，如果函数值继续减少，那么试探过程就会继续。而当到达点B时，显然我们的探求过程就结束了（因为无论朝哪个方向努力，结果只会越来越大）。最终我们只能找打一个局部最后解B。
根据Metropolis准则，粒子在温度T时趋于平衡的概率为exp(-ΔE/(kT))，其中E为温度T时的内能，ΔE为其改变数,k为Boltzmann常数。Metropolis准则常表示为 Metropolis准则表明，在温度为T时，出现能量差为dE的降温的概率为P(dE)，表示为：P(dE) = exp( dE/(kT) )。其中k是一个常数，exp表示自然指数，且dE= self.T_min: for i in range(self.iterMax): f1 = self.func(x1) delta_x = random.random() * 2 - 1 if x1 + delta_x >= self.interval[0] and x1 + delta_x 0: # 更优解 return x2 else: # 容忍解 P = self.p_max(delta, T) if P > random.random(): return x2 else: return x1 def display(self): print('seed: {}\nsolution: {}'.format(self.x_seed, self.x_solu)) plt.figure(figsize=(6, 4)) x = np.linspace(self.interval[0], self.interval[1], 300) y = self.func(x) plt.plot(x, y, 'g-', label='function') plt.plot(self.x_seed, self.func(self.x_seed), 'bo', label='seed') plt.plot(self.x_solu, self.func(self.x_solu), 'r*', label='solution') plt.title('solution = {}'.format(self.x_solu)) plt.xlabel('x') plt.ylabel('y') plt.legend() plt.savefig('SA.png', dpi=500) plt.show() plt.close() if __name__ == '__main__': SA([-5, 5], 'max') 实现结果
采用栅格图法构建地图。首先用列表创建一个10*10的矩阵，矩阵元素中值分别表示不同的涵义，数值不同含义不同，具体解释在下面代码中有注释。然后利用matplotlib包中的pylab库，把矩阵用热力图的形式画出来。具体操作如下代码所示： #step1 路径规划地图创建 class Map(): def __init__(self): #10 是可行 白色 # 0 是障碍 黑色 # 8 是起点 颜色浅 # 2 是终点 颜色深 self.data = [[ 8,10,10,10,10,10,10,10,10,10], [10,10, 0, 0,10,10,10, 0,10,10], [10,10, 0, 0,10,10,10, 0,10,10], [10,10,10,10,10, 0, 0, 0,10,10], [10,10,10,10,10,10,10,10,10,10], [10,10, 0,10,10,10,10,10,10,10], [10, 0, 0, 0,10,10, 0, 0, 0,10], [10,10, 0,10,10,10, 0,10,10,10], [10,10, 0,10,10,10, 0,10,10,10], [10,10,10,10,10,10,10,10,10, 2]] plt.imshow(self.data, cmap=plt.cm.hot, interpolation='nearest', vmin=0, vmax=10) # plt.colorbar() xlim(-1, 10) # 设置x轴范围 ylim(-1, 10) # 设置y轴范围 my_x_ticks = np.arange(0, 10, 1)#刻度列表 my_y_ticks = np.arange(0, 10, 1) plt.xticks(my_x_ticks)#画刻度 plt.yticks(my_y_ticks) plt.grid(True) plt.show()#显示 map = Map()#实例化 并显示地图
(实现代码太长了，这里就不发了，需要的找学长要) 最后结果 毕设长用到该算法来解决各种最优解的问题，比如路径优化问题，快递\货物配送最优路径，等等。 旅行商问题，即TSP问题（Travelling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
展示迭代优化过程效果 |
上示代码运行后为原始地图，左下角黄色为起点，右上角为终点，黑色为障碍区域。
【本文地址】