局部搜索

概念

• 局部搜索级从一个初始解触发，在其邻域内不断搜索，迭代改进当前姐，直到无法找到更优解
• 概念类似于物理学中的"势能"，搜索最终会停在一个势能谷底

关键组成

• 搜索空间：所有可能解的集合
• 目标函数：也叫成本函数或适应函数，用来评价一个解的好坏。目标一般是找到使得目标函数最大或最小的解
• 邻域结构：定义了如何从一个解移动到另一个"相邻"的解。这是局部搜索的核心，它决定了搜索的"步长"和方向。例如。在TSP问题中，一个解（一条路径）的邻域可以是交换路径中任意两个城市的位置后得到的所有新路径
• 迭代过程：算法从一个初始解开始，反复地从当前解地邻域中选择下一个解，以期改善目标函数值

流程

经典地局部搜索法

爬山法

• 最简单，最直观地局部搜索算法
• 策略：严格享受。检查当前解的所有邻居，如果找到一个比当前解更好的邻居，就立刻移动过去，然后开始新一轮的搜索；如果所有邻居都不如当前解，就停止搜索
• 优点：简单，快速
• 缺点：非常容易陷入局部最优解

模拟退火

• 为了克服容易陷入局部最优的缺陷而涉及的算法。灵感来源于金属退火过程
• 核心思想：引入"概率"和"温度"来决定是否接受一个更差的解
  • 在搜索初期，温度很高，算法有较高的概率去接受一个更差的解，这相当于允许"下山"去探索其他山谷，希望能找到通往更高山峰的路，这增加了算法的探索能力。
  • 随着迭代的进行，温度逐渐降低，算法接受更差解的概率也越来越小。在搜索末期，它基本不再接受差的解，变得更像爬山法，专注于咋当前找到的较优区域内进行精细搜索
• 优点：理论上（在无限时间内）的全局收敛性，能够有效跳出局部最优
• 缺点：参数需要仔细调优，否则效果不佳

禁忌搜索

• 禁忌搜索是另一种客服局部最优的强大技术，它引入"记忆"机制
• 核心思想：用一个经济标来记录最近执行过多的移动或访问过的解
  • 在后续的搜索中，算法被禁止执行哪些会导致回到近期状态的移动，即使会带来一个更好的解
  • 这样做的目的是强迫算法去探索新的未曾访问过的搜索区域，避免在几个解之间循环往复
• 特赦准则：禁忌不是绝对的。如果一个被禁忌的移动能带来一个足够好的解，那么禁忌可以被特赦
• 优点：强大的防循环和探索能力
• 缺点：紧急表的长度和管理策略对算法性能影响很大，设计相对复杂

遗传算法

• 核心思想：模拟生物进化
  • 它不维护但各界，而是维护一个多个解组成的种群
  • 通过选择、交叉、和变异等操作更新种群，对种群实现迭代演化，生成新一代的解
  • 好的解有更大概率被选中繁衍后低
• 优点：全局搜索能力强，不容易陷入局部最优，适合处理复杂和高位的搜索空间
• 缺点：算法复杂，计算开销大，收敛速度可能较慢

PLS完全性(Polynomial Local Search Complete)

PLS类的定义

• 一个PLS类的优化问题满足以下条件
  • 必须有一个多项式时间算法，能为任何问题实例生成一个初始的合法解。
  • 必须有一个多项式时间算法，能计算出任何一个给定解的成本（或收益）
  • 必须有一个多项式时间算法，能检查当前的解S是否是局部最优的。
    • 如果是，就报告"是"
    • 如果不是，必须能找出一个更好的邻居解并返回它

PLS特征

• 对于PLS类内的任何问题，一定能找到一位局部最优解
• 原因：解空间优先，成本函数有界

PLS-Complete问题————PLS最难的问题

定义

• 一个PLS-Complete问题满足以下条件
  • P本身属于PLS类
  • 所有其他PLS类的问题都可以归约到P
• 这里的归约指的是PLS-归约。它在归约的基础上还要求问题B的局部最优解可以被高效地转换成A的一个局部最优解，

意义

• PLSC问题的局部最优解存在，但无法在多项式时间内找到

与NP的关系

• PLS是NP的一个子集