最优化算法理论与应用精.ppt

《最优化算法理论与应用精.ppt》由会员分享，可在线阅读，更多相关《最优化算法理论与应用精.ppt（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最优化算法理论与应用第1页，本讲稿共15页优化方法基本分类优化方法基本分类本门课程有关事宜本门课程有关事宜优化问题基本分类优化问题基本分类第2页，本讲稿共15页优化问题基本分类优化问题基本分类第3页，本讲稿共15页例、和优化联系非常密切的一类问题例、和优化联系非常密切的一类问题（回归、辨识、估计、训练、学习、拟合、逼近（回归、辨识、估计、训练、学习、拟合、逼近）已知某个标量已知某个标量 和某个向量和某个向量 之间若干一之间若干一一对应的样本数据一对应的样本数据要确定一个函数要确定一个函数 ，使在包含所有样本数据的某个，使在包含所有样本数据的某个集合集合 里能够用里能够用 描述描述 和和 之间的

2、对应关系，即之间的对应关系，即使误差使误差 对任意的对任意的 都尽量小都尽量小第4页，本讲稿共15页基本方法：选择含有待定参数的函数基本方法：选择含有待定参数的函数 ，通过极小，通过极小 化某种样本误差确定待定参数得到所需函数化某种样本误差确定待定参数得到所需函数常用常用 范数的样本误差范数的样本误差于是，最终要解决的是下述优化问题于是，最终要解决的是下述优化问题这是这是连续变量无约束优化问题连续变量无约束优化问题第5页，本讲稿共15页对于采用对于采用 范数形成的优化问题范数形成的优化问题为克服目标函数不可导的困难，可以等价转换成下面的为克服目标函数不可导的困难，可以等价转换成下面的连续变量约

3、束优化问题连续变量约束优化问题特别是，当特别是，当 是是 的线性函数时，即的线性函数时，即上面的优化问题是上面的优化问题是线性规划问题线性规划问题第6页，本讲稿共15页可以选择足够多的基函数可以选择足够多的基函数 使优化问题使优化问题的样本误差任意小，这样得到的模型在样本集以外通常的样本误差任意小，这样得到的模型在样本集以外通常会产生很大的预报误差，这就是所谓过度拟合或过度训会产生很大的预报误差，这就是所谓过度拟合或过度训练问题。解决该问题的根本途经是同时极小化基函数的练问题。解决该问题的根本途经是同时极小化基函数的个数，理论上要解决个数，理论上要解决连续和离散变量混合的优化问题连续和离散变量

4、混合的优化问题其中其中 是设定的正的权值是设定的正的权值第7页，本讲稿共15页前面的例子包含了优化问题最基本的类型前面的例子包含了优化问题最基本的类型线性线性 与与 非线性非线性无约束无约束 与与 有约束有约束连续变量连续变量 与与 离散变量离散变量后者相对于前者在难度上均有质的改变后者相对于前者在难度上均有质的改变具有不确定性和动态特性的问题具有不确定性和动态特性的问题转换成上述问题转换成上述问题第8页，本讲稿共15页优化方法基本分类优化方法基本分类第9页，本讲稿共15页例例基本方法：从基本方法：从 之间的任一点出发，朝着能够改进目之间的任一点出发，朝着能够改进目标函数的方向搜索前进，直至目

5、标函数不能改进标函数的方向搜索前进，直至目标函数不能改进肯定能够收敛到一个局部最优解，不能保证全局最优肯定能够收敛到一个局部最优解，不能保证全局最优第10页，本讲稿共15页跳出局部陷阱的唯一途经是在搜索过程中允许前进到目跳出局部陷阱的唯一途经是在搜索过程中允许前进到目标函数值变差的点，如在标函数值变差的点，如在 之间容许目标函数下降才之间容许目标函数下降才有可能找到全局最优解有可能找到全局最优解由此产生新问题，无法保证算法收敛由此产生新问题，无法保证算法收敛第11页，本讲稿共15页为了使算法收敛，只能引入不确定性，让算法在任何一为了使算法收敛，只能引入不确定性，让算法在任何一点以一定的概率前进

6、到邻近的某点，移动概率和相应点点以一定的概率前进到邻近的某点，移动概率和相应点的目标函数值正相关，所以的目标函数值正相关，所以由此产生的算法是结果不确定的算法由此产生的算法是结果不确定的算法第12页，本讲稿共15页前面的例子包含了优化方法最基本的类型前面的例子包含了优化方法最基本的类型确定型搜索确定型搜索 与与 不确定型搜索不确定型搜索前者是经典的优化教材介绍的主要内容，后者前者是经典的优化教材介绍的主要内容，后者包括模拟退火、禁忌搜索、遗传算法、免疫算包括模拟退火、禁忌搜索、遗传算法、免疫算法、蚂蚁算法等方法，一般统称为智能算法法、蚂蚁算法等方法，一般统称为智能算法本课程主要讨论基于确定性搜

7、索的优化方法本课程主要讨论基于确定性搜索的优化方法后期简单介绍基于不确定性搜索的优化方法后期简单介绍基于不确定性搜索的优化方法第13页，本讲稿共15页本门课程有关事宜本门课程有关事宜第14页，本讲稿共15页教材：运筹学（第二版），刁在筠等编，高教出版社教材：运筹学（第二版），刁在筠等编，高教出版社 自第自第2章到第章到第6章按教材顺序讲课，内容有增减章按教材顺序讲课，内容有增减 在第在第6章后增加一些不确定型搜索方法的内容章后增加一些不确定型搜索方法的内容考核：考核：考试（开卷）成绩占考试（开卷）成绩占80，平时作业占，平时作业占20，成绩为所有平时作业成绩的平均值成绩为所有平时作业成绩的平均值第15页，本讲稿共15页