7 现代优化算法.ppt

最优化方法
济南大学控制科学与工程学院
授课教师:李实
cse_******@ujn.
1教1007室
第七章现代优化算法简介
在实际应用中经常遇到一些复杂优化问题,而往往需要求解它的全局最优解。由于许多问题具有多个局部最优解,目标函数是不可微的,甚至是无法用数学问题表达的,传统的非线性算法受到限制。
20世纪80年代以来,研究学者通过模仿某些自然现象和过程,发展出了一些新的优化算法,比如模拟退火算法、遗传算法、蚁群算法、粒子群算法、禁忌算法、人工神经网络…
这些新型算法为解决复杂优化问题提供了新的思路和手段。用于多目标优化、动态环境下优化、大规模超大规模优化、不确定环境下优化等。
遗传算法是其中应用最为广泛的一种算法。
2
模拟退火算法
模拟退火算法属于一种通用的随机探索算法,1953年由N. Metropolis等人提出了模拟退火算法,其基本思想是把某类优化问题的求解过程与统计热力学的热平衡问题进行对比,试图通过模拟高温物体退火过程来找到优化问题的全局最优解或近似全局最优解。
一个物体(如金属)的退火过程大体如下:首先对物体高温加热(融化),液态物体内的原子拜托晶体格点束缚,处于高速运行状态。在退火时,随着温度的降低,物体内部原子的能量状态由高向低转变。这种由高能向低能逐渐降温的过程称为退火。当温度降低至结晶温度后,物体变为固态,原子运动回复到围绕晶体格点的微小振动状态,退火过程结束。
对于一个最优化问题,当我们把目标函数f(X)看成定义在可行域上的能量曲面,而整个曲面f(X)凹凸不平,如果让一个光滑圆球在曲面上自由滚动,该圆球会到最近的凹处停止运动,但这个低谷并不一定是最深的凹谷,涵义是局部极小点并不一定是全局极小点。
3
4
模拟退火算法相当于沿水平方向给圆球一个作用力,若该作用力足够大使得圆球从低谷中滚出,并落入另一个低谷,然后再受水平作用力,如此反复,当作用力大小恰当,小球会停留在最深的低谷,也就是优化问题的全局最优解。
作用在圆球上的水平作用力相当于模拟退火中的温度,水平作用力的减小相应与温度降低。
生物启发式优化算法
5
遗传算法
神经网络
模糊逻辑
…
遗传算法
6
进化过程
优化过程
生物进化过程是一个自然,并行,稳健的优化过程,这一优化过程的目的在于使生命体达到适应环境的最佳结构与效果,而生物种群通过”“优胜劣汰”及遗传变异来达到进化(优化)目的的
7
遗传算法的思想来源于达尔文的自然进化论和孟德尔、摩根的群体遗传学说,由美国Michigan大学的John Holland教授于1975年提出。
遗传算法的核心思想:求解问题时,将问题的求解过程视为染色体适者生存的过程,通过染色体一代一代的不断进化(包括选择、交叉、变异等操作),保留优良个体,淘汰劣质个体,最终收敛到“最适应环境”的个体,从而找到问题的最优解或满意解。
生物的进化机制
自然选择
适应环境的个体具有更高的生存能力,同时染色体特征被保留下来
杂交
随机组合来自父代的染色体上的遗传物质,产生不同于它们父代的染色体
突变
随机改变父代的染色体基因结构,产生新染色体
8
树突
突触
轴突
细胞体
人工神经网络
9
受生物神经系统的启发,人们提出了一种新型的非算法信息处理方法—人工神经网络。
轴突是一根长神经纤维,其主要功能是将神经冲动由胞体传至其它神经元。每个神经元只有一根轴突。
突触:神经元与神经元之间的连接点。它是神经元之间的传递信息关键性结构。可以分为两类:化学性突触和电突触。
神经元之间的信息是通过突触完成的。当神经冲动传至突触前膜时,突触中的神经递质与突触后膜上的相应受体结合,于是后膜两侧的离子分布发生改变,呈兴奋性或抑制变化。
10
因为一个神经元通常有许多突触,其中有些是兴奋性的,有些是抑制性的,如果兴奋性突触活动强度总和超过抑制性突触活动强度总和,并达到一定的阈值,就能使使该神经元的轴突起始发生动作电位,产生神经冲动。出现神经冲动时则该神经元呈现兴奋,反之则表现为抑制。
神经元的每个突触的活动强度用一个固定的实数即权值模拟。
1943 年,心理学家 McCulloch 和数学家 Pitts提出的神经元二元阈值单元(Binary threshold unit),即著名的 M-P 模型[15]。该模型的基本思想是:神经细胞的工作方式是兴奋或者是抑制。基于这个思想,McCulloch 和 Pitts在神经元模型中引入了硬极限函数。MP模型是一种静态的模型,结构固定,权值无法调节,缺乏学习能力。