100种算法【Python版】第43篇——优化算法之模拟退火算法
本文目录
- 1 算法说明
- 2 算法示例：Rosenbrock函数极值
- 3 算法应用1：复杂函数极值
- 4 算法应用2：TSP问题
1 算法说明
模拟退火（Simulated Annealing, SA）算法最早由斯图尔特·西尔伯特和约瑟夫·斯图尔特于1983年提出，灵感来源于金属退火过程。金属在加热后会变得更加柔软，冷却时逐渐形成有序的晶体结构，最终达到能量最低的状态。模拟退火算法借鉴了这一物理过程，通过随机搜索和逐步降低“温度”的方式，寻找复杂优化问题的全局最优解。
模拟退火算法的核心
模拟退火算法的核心思想是利用随机性和温度控制来平衡探索和开发之间的关系。
- 温度概念：算法使用温度来控制接受新解的概率。较高的温度允许算法接受较差的解，以避免陷入局部最优；而较低的温度则更倾向于接受更优解。
- 目标函数：算法通过不断评估目标函数的值来判断解的优劣。
- 邻域解生成：在当前解的基础上生成一个邻域解，通常通过对当前解进行小幅随机扰动实现。
- 接受准则：
- 如果新解优于当前解，直接接受。
- 如果新解劣于当前解，以一定概率接受，概率由以下公式计算：