下载此文档

最优化算法、智能优化算法及其应用.ppt


文档分类:管理/人力资源 | 页数:约43页 举报非法文档有奖
1/43
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/43 下载此文档
文档列表 文档介绍
北京邮电大学
赵新超
信息与计算数学中心
数学系,理学院
@
主楼814
最优化算法、智能优化算法及其应用
1
北京邮电大学数学系
提纲
智能算法、最优化算法
方法
问题
数值优化、多目标优化
组合优化:背包问题、旅行商问题
Web服务选择
优化搜索算法一般框架
网络路由优化等
2
北京邮电大学数学系
一、搜索算法一般框架
第二步:在当前解确定一个搜索方向和步长,移动到新的解
第一步:产生初始解
一元问题是个实数
多元问题是个向量
第三步:算法终止条件,否则循环。
步长:一维搜索或线搜索
方向:最速下降、牛顿方向
新解与老解的取舍规则
3
一维搜索的数学模型
单变量函数的最优解问题
精确、非精确的一维搜索方法
4
北京邮电大学数学系
搜索方向与最优化算法
《高等数学》:多元函数梯度
已知知识:负梯度方向是函数在当前点处函数值下降最快的方向;
方法:随机产生一点作为初始解,按该点的负梯度方向搜索确定下一点,直至找到最优解为止;
算法终止条件:梯度等于零。
最速下降方向
前半程收敛快,后半程慢(Zigzag)
5
牛顿搜索方向
优点:二次终止性,收敛速度快
计算量大(求导和解方程组);
要求Hessen矩阵正定,矩阵可能病态更糟糕;
不保证新解一定比老解好;
缺点:
6
北京邮电大学数学系
信赖域算法
无约束优化方法通常策略是,给定点后,
某确定策略找到搜索方向
再某策略确定沿该方向走的长度,即步长
信赖域方法另辟蹊径:
给定点后,确定一个(小的)变化范围,
通常取xk为中心的球域,称为信赖域,
在此邻域内找到原问题的二次函数逼近式,以二次函数的最优解作为原问题最优解的近似点xk+1,
如此往复……
7
北京邮电大学数学系
最优化算法参考书
搜索方向设计总体思路:
算法搜索前半程大致沿最速下降方向搜索,
算法搜索后半程大致沿牛顿方向搜索,即大致在两个搜索方向之间摇摆;
陈宝林,《最优化理论与算法》,清华大学出版社
8
北京邮电大学数学系
贪心思想与模拟退火策略
第二步:在当前解确定一个搜索方向和步长,移动到新的解
新解与老解的取舍规则
若只有新解优于老解时才保留新解,则是一般的贪心算法思想,但很容易陷入一个局部最优陷阱
若在算法中不仅是见了优秀解就保留,更重要的是当获得较差的解时也有可能保留,当然可能性依概率减小,即爱富而不嫌贫!
9
北京邮电大学数学系
爱富而不嫌贫的算法—模拟退火算法
模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。
根据Metropolis准则,粒子在温度T时趋于平衡的概率为exp(-ΔE/(kT)),其中E为温度T时的内能,ΔE为其改变量,k为Boltzmann常数。
用固体退火模拟优化问题,将内能E模拟为目标函数值f,温度T演化成控制参数t,即得到解优化问题的模拟退火算法:由初始解i和控制参数初值t开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。
来源于百度百科
10
北京邮电大学数学系

最优化算法、智能优化算法及其应用 来自淘豆网www.taodocs.com转载请标明出处.

非法内容举报中心
文档信息
  • 页数43
  • 收藏数0 收藏
  • 顶次数0
  • 上传人buhouhui915
  • 文件大小689 KB
  • 时间2018-04-23