[工学]第六章-现代最优化方法PPT课件

.,1,研究生课程工程数学之“最优化方法”,现代最优化方法,能源与动力工程学院,CollegeofEnergyandPowerEngineering,.,2,现代优化算法包括随机试验法、禁忌搜索算法、模拟退火算法、遗传算法、神经网络算法和拉格朗日松弛算法等，这些算法涉及生物进化、人工智能、数学和物理科学、神经系统和统计力学等概念。都是以一定的直观基础而构造的算法，通常称之为启发式算法。启发式算法的兴起与计算复杂性理论的形成有密切的联系。1.对目标函数和约束函数不必附加可解析性条件，对于目标函数而言甚至可以不要求有显示表达式；2.对于约束变量可以去离散值或特殊整数如0和1等；3.在通常情况下，这些算法能够求解全局最优解。,.,3,第一节随机试验法,.,4,一、基本思想禁忌搜索法(Tabusearch)是一种人工智能方法，是局部邻域搜索算法的推广，是人工智能在组合优化中的一个成功应用。其基本思想是：标记已经得到的局部最优解，并在进一步的迭代中避开这些局部最优解。所谓的禁忌就是禁止重复前面的工作，为了避开局部邻域搜索陷入局部最优，禁忌搜索算法设计了一种禁忌表，记录已达到过的局部最优点。在下一次的搜索中，就利用禁忌表中的信息，不再或者有选择地搜索这些点，以此跳出局部最优点。,第二节禁忌搜索法,.,5,1.算法的提出模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。2.算法的目的解决NP复杂性问题；克服优化过程陷入局部极小；克服初值依赖性。,一、物理退火过程,第三节模拟退火算法,.,6,3.物理退火过程什么是退火?退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。,第三节模拟退火算法,.,7,物理退火过程加温过程增强粒子的热运动，消除系统原先可能存在的非均匀态；等温过程对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；冷却过程使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。,第三节模拟退火算法,.,8,4.数学表述在温度T，分子停留在状态r满足Boltzmann概率分布,第三节模拟退火算法,.,9,在同一个温度T，选定两个能量E1E2，在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。,0,第三节模拟退火算法,.,10,若|D|为状态空间D中状态的个数，D0是具有最低能量的状态集合：当温度很高时，每个状态概率基本相同，接近平均值1/|D|；状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值1/|D|；当温度趋于0时，分子停留在最低能量状态的概率趋于1。,能量最低状态非能量最低状态,第三节模拟退火算法,.,11,Metropolis准则(1953)以概率接受新状态固体在恒定温度下达到热平衡的过程可以用MonteCarlo方法(计算机随机模拟方法)加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。,第三节模拟退火算法,若在温度T，当前状态i新状态j若Ej0，Tji=Tij，则有dE/dt0，当且仅当dvi/dt=0时dE/dt=0。,第五节神经网络优化算法,.,69,能量函数将动力系统方程简单记为：如果，则称ve是动力系统的平衡点，也称ve为吸引子。随着时间的增长，神经网络在状态空间中的解轨迹总是向能量函数减小的方向变化，且网络的稳定点就是能量函数的极小点。,第五节神经网络优化算法,.,70,能量函数当从某一初始状态变化时，网络的演变是使E下降，达到某一局部极小时就停止变化。这些能量的局部极小点就是网络的稳定点或称吸引子。,第五节神经网络优化算法,.,71,Hopfield网络设计当Hopfield用于优化计算时，网络的权值是确定的，应将目标函数与能量函数相对应，通过网络的运行使能量函数不断下降并最终达到最小，从而得到问题对应的极小解。,3.Hopfield神经网络在TSP中的应用,(TravellingSalesmanProblem),第五节神经网络优化算法,.,72,Hopfield网络设计通常需要以下几方面的工作：（1）选择合适的问题表示方法，使神经网络的输出与问题的解相对应；（2）构造合适的能量函数，使其最小值对应问题的最优解；（3）由能量函数和稳定条件设计网络参数，如连接权值和偏置参数等；（4）构造相应的神经网络和动态方程；（5）用硬件实现或软件模拟。,第五节神经网络优化算法,.,73,问题的表示将TSP问题用一个nn矩阵表示，矩阵的每个元素代表一个神经元。代表商人行走顺序为：3124每一行、每一列的和各为1。,第五节神经网络优化算法,.,74,能量函数的构建每个神经元接收到的值为zij，其输出值为yij，激活函数采用Sigmoid函数，记两个城市x和y的距离是dxy。(1)希望每一行的和为1，即最小，每一行最多有一个1时，E10。,第五节神经网络优化算法,.,75,(2)希望每一列的和为1，即最小，每一列最多有一个1时，E20。(3)希望每一行每一列正好有一个1，则为零。,第五节神经网络优化算法,.,76,(4)E1，E2，E3只能保证TSP的一个可行解，为了得到TSP的最小路径，当duv=dvu时，希望最小，其中，yu0=yun，yu(n+1)=yu1。duvyuiyv(i+1)表示城市u和v之间的距离（i代表行走顺序）。,第五节神经网络优化算法,.,77,(5)根据连续Hopfield神经网络能量函数，最后，能量函数表示为：A，B，C，D，为非负常数。,第五节神经网络优化算法,.,78,由动力学方程，,第五节神经网络优化算法,.,79,整理后得到：,第五节神经网络优化算法,.,80,10城市TSP问题（d*=2.691）0.40.4439;0.24390.1463;0.17070.2293;0.22930.761;0.51710.9414;0.87320.6536;0.68780.5219;0.84880.3609;0.66830.2536;0.61950.2634,第五节神经网络优化算法,.,81,10城市TSP问题(d*=2.691)流程图：,第五节神经网络优化算法,.,82,10城市TSP问题（d*=2.691）初始参数：1ABD500，C200激励函数为Sigmoid其中，00.02,第五节神经网络优化算法,.,83,10城市TSP问题（d*=2.691）初始参数：初始的yui初始的zui=0.00001,第五节神经网络优化算法,.,84,10城市TSP问题（d*=2.691）,第五节神经网络优化算法,.,85,10城市TSP问题（d*=2.691）,第五节神经网络优化算法,.,86,第五节神经网络优化算法,.,87,第五节神经网络优化算法,.,88,第五节神经网络优化算法,.,89,第五节神经网络优化算法,.,90,第五节神经网络优化算法,.,91,基于Hopfield网络优化的缺陷用Hopfield网络优化的出发点建立在：（1）神经网络是稳定的，网络势必收敛到渐进平衡点；（2