算法大全第23章__现代优化算法

普大帝

你好！我是陪你一起进阶人生的普大帝！愿你成才！祝你成长！ 4 C: @- Q# `! c3 h为大家更新一些算法类的辅助资料，大家在想学习时，或者比赛急需时就可以按照对应的名字找到对应的算法，加以应用了。大家按照下图所示箭头处点击主题，就可以查看到其他算法类内容了，或者搜索框内输入算法大全，也可以搜索到对应的贴子，本篇为第23篇。

! l/ K7 d+ N2 M- N3 [5 Z现代优化算法
现代优化算法是 80 年代初兴起的启发式算法。这些算法包括禁忌搜索（tabusearch），模拟退火（simulated annealing），遗传算法（genetic algorithms），人工神经网络（neural networks）。它们主要用于解决大量的实际应用问题。目前，这些算法在理论和实际应用方面得到了较大的发展。无论这些算法是怎样产生的，它们有一个共同的目标－求 NP-hard 组合优化问题的全局最优解。虽然有这些目标，但 NP-hard 理论限制它们只能以启发式的算法去求解实际问题。启发式算法包含的算法很多，例如解决复杂优化问题的蚁群算法（Ant ColonyAlgorithms）。有些启发式算法是根据实际问题而产生的，如解空间分解、解空间的限制等；另一类算法是集成算法，这些算法是诸多启发式算法的合成。
/ D* t5 [: Y/ I8 i* O现代优化算法解决组合优化问题，如 TSP（Traveling Salesman Problem）问题，QAP（Quadratic Assignment Problem）问题，JSP（Job-shop Scheduling Problem）问题等效果很好。
§1 模拟退火算法
& u3 `' {/ a0 C8 N+ Z# d1.1 算法简介
. u4 r! g( E7 q( ?模拟退火算法得益于材料的统计力学的研究成果。统计力学表明材料中粒子的不同结构对应于粒子的不同能量水平。在高温条件下，粒子的能量较高，可以自由运动和重新排列。在低温条件下，粒子能量较低。如果从高温开始，非常缓慢地降温（这过程被称为退火），粒子就可以在每个温度下达到热平衡。当系统完全被冷却时，最终形成处于低能状态的晶体。
0 Y& X: ^- U- f1 q如果用粒子的能量定义材料的状态，Metropolis 算法用一个简单的数学模型描述了退火过程。假设材料在状态 i 之下的能量为 ) (i E ，那么材料在温度 T 时从状态 i 进入状态 j 就遵循如下规律：

! m0 E, w; `+ E: J* o6 K" h- A6 v
/ y' r: f3 Y9 t* _) d% r  E% f& o- t

数模老哥

发表回复66666663333666666
3 n- f5 J7 @; |# Z7 e