第23章 现代优化算法
现代优化算法是 80 年代初兴起的启发式算法。这些算法包括禁忌搜索(tabu
search),模拟退火(simulated annealing),遗传算法(genetic algorithms),人工神经网
络(neural networks)。它们主要用于解决大量的实际应用问题。目前,这些算法在理论
和实际应用方面得到了较大的发展。无论这些算法是怎样产生的,它们有一个共同的目
标-求 NP-hard 组合优化问题的全局最优解。虽然有这些目标,但 NP-hard 理论限制它
们只能以启发式的算法去求解实际问题。
启发式算法包含的算法很多,例如解决复杂优化问题的蚁群算法(Ant Colony
Algorithms)。有些启发式算法是根据实际问题而产生的,如解空间分解、解空间的限
制等;另一类算法是集成算法,这些算法是诸多启发式算法的合成。
现代优化算法解决组合优化问题,如 TSP(Traveling Salesman Problem)问题,QAP
(Quadratic Assignment Problem)问题,JSP(Job-shop Scheduling Problem)问题等效
果很好。
§1 模拟退火算法
1.1 算法简介
模拟退火算法得益于材料的统计力学的研究成果。统计力学表明材料中粒子的不
同结构对应于粒子的不同能量水平。在高温条件下,粒子的能量较高,可以自由运动和
重新排列。在低温条件下,粒子能量较低。如果从高温开始,非常缓慢地降温(这个过
程被称为退火),粒子就可以在每个温度下达到热平衡。当系统完全被冷却时,最终形
成处于低能状态的晶体。
如果用粒子的能量定义材料的状态,Metropolis 算法用一个简单的数学模型描述了
退火过程。假设材料在状态i 之下的能量为 E(i) ,那么材料在温度T 时从状态i 进入状
态 j 就遵循如下规律:
(1)如果 E( j) ≤ E(i) ,接受该状态被转换。
(2)如果 E( j) > E(i) ,则状态转换以如下概率被接
- 2021-10-30
- 阅读264
- 下载0
- 20页
- pdf