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

《最优化算法、智能优化算法及其应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京邮电大学赵新超信息与计算数学中心数学系，理学院xc.bupt@gmail.com主楼814最优化算法、智能优化算法及其应用1北京邮电大学数学系提纲智能算法、最优化算法方法问题数值优化、多目标优化组合优化：背包问题、旅行商问题Web服务选择优化搜索算法一般框架网络路由优化等2北京邮电大学数学系一、搜索算法一般框架第二步：在当前解确定一个搜索方向和步长，移动到新的解第一步：产生初始解一元问题是个实数多元问题是个向量第三步：算法终止条件，否则循环。步长：一维搜索或线搜索方向：最速下降、牛顿方向新解与老解的取舍规则3一维搜索的数学模型单变量函数的最优解问题精确、非精确的一维搜

2、索方法4北京邮电大学数学系搜索方向与最优化算法《高等数学》：多元函数梯度已知知识：负梯度方向是函数在当前点处函数值下降最快的方向；方法：随机产生一点作为初始解，按该点的负梯度方向搜索确定下一点，直至找到最优解为止；算法终止条件：梯度等于零。最速下降方向前半程收敛快，后半程慢（Zigzag）5牛顿搜索方向优点：二次终止性，收敛速度快计算量大（求导和解方程组）；要求Hessen矩阵正定，矩阵可能病态更糟糕；不保证新解一定比老解好；缺点：6北京邮电大学数学系信赖域算法无约束优化方法通常策略是，给定点后，某确定策略找到搜索方向再某策略确定沿该方向走的长度，即步长信赖域方法另辟蹊径

3、：给定点后，确定一个（小的）变化范围，通常取xk为中心的球域，称为信赖域，在此邻域内找到原问题的二次函数逼近式，以二次函数的最优解作为原问题最优解的近似点xk+1，如此往复……7北京邮电大学数学系最优化算法参考书搜索方向设计总体思路：算法搜索前半程大致沿最速下降方向搜索，算法搜索后半程大致沿牛顿方向搜索，即大致在两个搜索方向之间摇摆；陈宝林，《最优化理论与算法》，清华大学出版社8北京邮电大学数学系贪心思想与模拟退火策略第二步：在当前解确定一个搜索方向和步长，移动到新的解新解与老解的取舍规则若只有新解优于老解时才保留新解，则是一般的贪心算法思想，但很容易陷入一个局部最优陷阱

4、若在算法中不仅是见了优秀解就保留，更重要的是当获得较差的解时也有可能保留，当然可能性依概率减小，即爱富而不嫌贫！9北京邮电大学数学系爱富而不嫌贫的算法—模拟退火算法模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为exp(-ΔE/(kT))，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退火模拟优化问题，将内能E模拟为目标函数值f，温度

5、T演化成控制参数t，即得到解优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。来源于百度百科10北京邮电大学数学系退火过程由冷却进度表(CoolingSchedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。模拟退火算法的模型(1)初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L(2)对k=1，……，L做第(3)至第6步：(3)

6、产生新解S′(4)计算增量Δt′=f(S′)-f(S)，其中C(S)为评价函数(5)若Δt′<0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解.(6)如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取连续若干个新解都没有被接受(7)T逐渐减少，且T->0，然后转第2步。11二、随机方式确定搜索方向是n维向量演化规划和演化策略产生新解的基本迭代步骤12北京邮电大学数学系自古以来，人们就对生物界有着浓厚的兴趣，生物成为许多发明家创新的灵感源泉，他们从生物现象中得到启示，制造出了从机翼、雷达、防弹衣等许多产品。从20世纪中叶开始，

7、人们就已经开始注意对生物系统尤其是人类自身功能及结构的模仿，由此产生了许多研究领域。生命经历从低级到高级、从简单到复杂的演化之路，人类找到生命目前的最佳结构与形式，它不仅仅能被动的适应环境，更重要的是它能够通过学习、模仿和创造来主动提高适应环境的能力。神经网络是人类对大脑信息处理机制的模拟；模糊系统是人类对其自身思维方式的类比；进化计算则是人类向其自身进化这一更为宏观的过程学习；免疫优化算法则是模仿人类免疫系统的高度分布性的自适应学习系统；13北京邮电大学数学系1、遗传算法与进化计算技术自然进化过程实质上就是一个学习与优化的过