第四章不确定性搜索

这是一篇有关第四章不确定性搜索的思维导图，从搜索定义、局部搜索算法、模拟退火算法等方面进行了概述和分析。

第四章 不确定性搜索

• 基本概念
  • 搜索优化的形式化描述
  • 算法的时间复杂度
  • 算法分类
    • 执行过程是否唯一确定
      • 确定性算法
        • 给定初始状态，执行过程唯一确定
      • 不确定性算法
        • 给定初始状态，执行过程不唯一
    • 算法是否从完整的初始解开始
      • 构造算法
        • 算法从0开始，逐渐构造一个完整的最优解(无中生有)
      • 逼近算法
        • 算法从一个完整的初始解开始，逐步改进，直到逼近最优解(优中选优)
    • 是否能得到一个全局的最优解
      • 全局最优算法
        • 算法能保证得到一个全局的最优解
      • 局部最优算法
        • 算法只能保证得到一个局部的最优解
  • 算法与问题之间的关系
    • 问题脱离算法存在
    • 算法依赖于问题
    • 没有免费的午餐定理
  • 领域
    • 定义
      • 一个点附近的其他点的集合
      • 在距离空间，领域就是以某一点为中心的圆
    • 组合优化下的领域
• 局部搜索算法
  • 基本思想
    • 在搜索过程中，始终向着离目标最接近的方向搜索
      • 在邻域内搜集信息作出判断，前进
      • 反复构建邻域，直到达到局部最优
      • "目标最接近的方向"->在邻域内改善最大的方向
  • 算法框架
  • 存在的问题
    • 局部最优问题
      • 解决方法
        • 每次并不一定选择领域内最优的点，而是依据一定概率，从邻域内选择一个点，指标函数优的点，被选中的概率比较大，指标函数差的点，被选中的概率小
      • 算法框架
    • 步长问题
      • 解决方法
        • 变步长
      • 算法框架
    • 起始点问题
      • 解决方法
        • 随机生成一些点，从每个初始点开始出发进行搜索，找到各自的最优解，在从这些最优解中选择最好的一个结果作为最终结果
      • 算法框架
    • 多方法集成
  • 小结
    • 与图搜索算法的区别
    • 算法输出
      • 局部最优解
    • 算法停止条件
• 模拟退火算法
  • 基本思想
    • 借用金属的退火过程改进局部搜索算法
  • Metropolis准则
  • 算法框架
  • 算法中的问题
• 全局搜索方法