现代优化算法.ppt

现代优化算法
李金屏
济南大学信息科学与工程学院
模式识别与智能系统研究所
(1st version in )
39
2
内容概要
优化算法简介——运筹学
正交试验法
TABU禁忌搜索算法
模拟退火算法
遗传算法&进化计算
现代优化算法再述
课题组的工作
其它问题:
计算复杂性;
邻域概念;
NP, NP-C 和NP-hard;
Markov过程;
人工生命,蚂蚁算法,免疫算法,混沌优化算法,memetic算法等。
其它问题。
39
3
优化算法简介——概念、基本形式
什么是优化?就是从各种方案中选取一个最好的。从数学角度看,优化理论就是研究如何在状态空间中寻找到全局最优点。
比如水泥混凝土的性能,涉及到水、沙、石子、水泥和其他掺杂物比例。学校课程表排课问题、售票员上岗问题、公司内部人员安排出效益等。降低成本、提高效益是问题的关键。
一般的优化具有下面形式:
minf (x1, x2, …, xn) . g(x)  0,xD
其中x1, x2, …, xnΩ(即问题的可行域,代表问题参数的选择范围),即minf (X),其中XΩ(矢量形式)。f(x)是决策问题的数学模型,也是决策问题的目标函数,g(x) 0是决策问题的约束条件,D是决策问题的定义域(可行域)。问题归结为求极值。极值点非常多,需要找到全局最小点。
注:求问题的最大和最小是同一个问题,算法完全一样。
39
4
如果决策问题是一个凸问题,可以利用线性规划、非线性规划等求解。然而大量的实际问题是非凸问题,需要在大量的局部极优解中寻找全局最优解。此时,决策变量x是否连续,数学模型f(x)是否具有解析表达式,对于求解难度会有不同的影响。
这是一个全局寻优问题。很多方法讨论的是如何在一个极值点附近搜索极值点。一般情况下,利用穷举的方法是不可能的。
习惯上,将优化算法分为两类:局部优化算法和全局性优化算法。前者可以称为经典优化算法,已经得到了人们广泛深入的研究。目前,运筹学(确定论方法)主要包括这些方面的内容,线性规划、整数规划、0–1规划、非线性规划、排队论、决策论。后者习惯上称为现代优化算法,是20世纪80年代兴起的新型全局性优化算法,主要包括禁忌搜索、模拟退火、遗传算法等,其主要应用对象是优化问题中的难解问题,即NP–hard问题
优化算法简介——优化算法分类
39
5
优化算法简介——局部优化、全局优化
有文献将神经网络也列入现代优化算法的范畴,从全局优化的角度看,这并不适宜,因为神经网络的优化算法本质上是局部优化算法和全局优化算法的综合应用。
局部优化算法主要用于解决凸问题或单峰问题,通常使用确定性搜索策略,比如单纯形法、梯度下降法、爬山法、贪心法等,其基本思想是在状态转移过程中,只接受更好的状态,拒绝恶化的状态。
全局性优化算法主要用于求解非凸问题或多峰问题,通常使用概率性搜索策略,即状态转移规则,这是由于实际的全局性优化问题通常没有解析表达式或者解析表达式非常复杂难以进行理论分析。其基本思想是在可行域中从给定的一个或多个随机初始点出发进行搜索,利用适当的状态转移规则和合理的概率性状态接收规则搜索新的更优点,在确定的时间或搜索次数之内停止算法。
39
6
优化算法简介——二者需要结合
局部优化算法由于易于陷入局部极优解而无法用于解决多峰问题;同时,全局性优化算法采用适当的状态转移规则和概率性状态接受规则,能够避免过早地陷入局部极优解从而搜索到全局性最优解。
通常,局部优化算法能够快速地收敛到局部极优解,而全局性优化算法通过概率搜索可以获得在概率意义上尽可能好的全局性最优解区域,但是其局部极优点搜索能力较低。这是全局搜索算法和局部搜索算法之间的固有矛盾。对此人们进行了多种研究。基本解决方法在于二者的结合,即利用全局性优化算法在整个可行域中搜索最优区域,利用局部搜索算法搜索最优区域中的最优解。
Memetic算法就是全局性搜索和局部性搜索相结合的算法的总称。又可以称为杂和优化算法(Hybrid Optimization Algorithm)。
39
7
内容概要
优化算法简介——运筹学
正交试验法
TABU禁忌搜索算法
模拟退火算法
遗传算法
现代优化算法再述
课题组的工作
39
8
正交试验法
在工农业生产及科学实验中,为了试制新产品,改革工艺,寻找优良的生产条件,需要安排一系列的实验。全面实验成本很高,而且往往做不到。因此,需要进行部分试验。正交试验法就是一种实际中广泛使用的部分试验法,又叫正交设计法或正交优化法,即通过少数次试验找到最好的或者较好的实验条件。其中的决策变量和取值分别叫做因素和水平。寻优时,先确定影响决策目标的因素和水平,再选择适当的正交表,