第二十三章现代优化算法简介
10页1、第二十三章 现代优化算法简介1 现代优化算法简介现代优化算法是 80 年代初兴起的启发式算法。这些算法包括禁忌搜索( tabu search),模拟退火(simulated annealing),遗传算法(genetic algorithms),人工神经网 络(neural networks)o它们主要用于解决大量的实际应用问题。目前,这些算法在理论 和实际应用方面得到了较大的发展。无论这些算法是怎样产生的,它们有一个共同的目 标一求NP-hard组合优化问题的全局最优解。虽然有这些目标,但NP-hard理论限制它 们只能以启发式的算法去求解实际问题。启发式算法包含的算法很多,例如解决复杂优化问题的蚁群算法( Ant Colony Algorithms)o有些启发式算法是根据实际问题而产生的,如解空间分解、解空间的限 制等;另一类算法是集成算法,这些算法是诸多启发式算法的合成。现代优化算法解决组合优化问题,如TSP (Traveling Salesman Problem)问题,QAP (Quadratic Assignment Problem )问题,JSP (Job-shop Sch
2、eduling Problem )问题等效 果很好。本章我们只介绍模拟退火算法,初步介绍一下蚁群算法,其它优化算法可以参看 相关的参考资料。2 模拟退火算法2.1 算法简介 模拟退火算法得益于材料的统计力学的研究成果。统计力学表明材料中粒子的不 同结构对应于粒子的不同能量水平。在高温条件下,粒子的能量较高,可以自由运动和 重新排列。在低温条件下,粒子能量较低。如果从高温开始,非常缓慢地降温(这个过 程被称为退火),粒子就可以在每个温度下达到热平衡。当系统完全被冷却时,最终形 成处于低能状态的晶体。如果用粒子的能量定义材料的状态,Metropolis算法用一个简单的数学模型描述了 退火过程。假设材料在状态i之下的能量为E(i),那么材料在温度T时从状态i进入状 态 j 就遵循如下规律:(1) 如果E(j) E(i),则状态转换以如下概率被接受:E (i)-E (j) e KT其中K是物理学中的波尔兹曼常数,T是材料温度。 在某一个特定温度下,进行了充分的转换之后,材料将达到热平衡。这时材料处 于状态i的概率满足波尔兹曼分布:_ E (/)e KTE (八E_e KTjwS其中 x 表示材
3、料当前状态的随机变量, S 表示状态空间集合。 显然_ E(i)e _ kt 1l i m二T * V _ Ej I S I e KTjwS其中I S I表示集合S中状态的数量。这表明所有状态在高温下具有相同的概率。而当温度下降时,E (八一Emine KT lim - T t0 V eEmnKT二 lim Tt0 V eE (八一Emine KTEjEmnKTEmnKTjwSE (i) Emine KT=limT TO V_ E ( j)_Emine KTjeS mmjVS .min丨S Imin0若i g Smin其它min其中 E= min E(j)且 S= i I E(i) = E 。minminminjgS上式表明当温度降至很低时,材料会以很大概率进入最小能量状态。假定我们要解决的问题是一个寻找最小值的优化问题。将物理学中模拟退火的思 想应用于优化问题就可以得到模拟退火寻优方法。考虑这样一个组合优化问题:优化函数为F : x T R+,其中x g S,它表示优化 问题的一个可行解,R+二y I y g R, y 0,s表示函数的定义域。n(x)匸S表示x的一个邻域集合。首先给
4、定一个初始温度T和该优化问题的一个初始解x(0),并由x(0)生成下一个 0解xg N(x(0),是否接受x作为一个新解x(1)依赖于下面概率:P(x(0) T x)= ef (x)f (x (0)T0若f (x) f (x(0)其它换句话说,如果生成的解x的函数值比前一个解的函数值更小,则接受x(1) = x作为f (x)f (x (0)一个新解。否则以概率et0接受x作为一个新解。泛泛地说,对于某一个温度T和该优化问题的一个解x(k),可以生成x。接受x i作为下一个新解x(k +1)的概率为:卩若/(x) f (x(k)P(x(k) T x) =1 f (x)f (x(k)eT0其它在温度T下,经过很多次的转移之后,降低温度T,得到T T。在T下重复上述iii +1ii+1过程。因此整个优化过程就是不断寻找新解和缓慢降温的交替过程。最终的解是对该问 题寻优的结果。我们注意到,在每个T下,所得到的一个新状态x(k +1)完全依赖于前一个状态 ix(k),可以和前面的状态x(0), ,x(k 1)无关,因此这是一个马尔可夫过程。使用马尔可夫过程对上述模拟退火的步骤进行分析,结果表明:
《第二十三章现代优化算法简介》由会员cn****1分享,可在线阅读,更多相关《第二十三章现代优化算法简介》请在金锄头文库上搜索。
人教版小学四年级语文上册《搭石》教学设计
家长考试评语.doc
房地产项目可行性研究报告论文大纲3篇(房地产项目可行性研究报告的几个部分和主要内容)
幼儿园矛盾纠纷调解制度
城乡建设用地增减挂钩专项规划
系统实施工作说明书模板
河南省永城市八年级生物下册 7.3.1《地球上生命的起源》能力提升(无答案)(新版)新人教版
细胞的物质基础
国美电器盈利模式分析
2022关于毕业生幼儿园自我鉴定应该怎么写
强蛋白银批发合同
乘坐公司班车管理规定范文
我的爸爸小学作文
人教版六年级上册数学期末试卷及答案
李栋四年级英语上Unit5
2023实习个人总结模板(6篇)
塔吊安全技术操作规程
河南省标准质量品牌建设项目可行性报告
人教版二年级语文上册第七单元课文清澈的湖水教学设计
酒店成本控制思路方法
2022-12-24 5页
2023-08-25 28页
2022-12-25 13页
2023-11-01 12页
2022-12-11 3页
2023-09-28 6页
2022-11-16 11页
2023-10-08 11页
2023-09-28 12页
2024-01-10 5页