邻域#

• 在函数型优化问题中，邻域被定义为以某点为中心的距离不超过一定阈值的球体。
• 在组合优化问题中，定义邻域映射为 $N: x\in D \rightarrow N(x) \in 2^D$，其中 $2^D$ 表示集合 $D$ 的全部子集做并集运算形成的集合，显然有 $x \in N(x)$。这里称 $N(x)$ 为 $x$ 的邻域，若 $y \in N(x)$，则 $y$ 为 $x$ 的一个邻居。

例如，TSP 问题中，定义邻域映射为一个排列 $x$ 的两个元素交换 (2-opt) 后的结果。比如，若 $x = (1, 2, 3, 4)$，则 $N(x) = \{(1, 2, 3, 4), (2, 1, 3, 4), (3, 2, 1, 4), (4, 2, 3, 1), (1, 3, 2, 4), (1, 4, 3, 2), (1, 2, 4, 3)\}$ 共 $C_4^2 = 6$ 个元素。此外，这个定义也可以推广，比如定义排列中的 $k$ 个元素进行重新排列 (k-opt) 后的结果形成的集合为排列 $x$ 的邻域 $N(x)$.

局部搜索算法#

Algorithm Local Search

一次的局部搜索算法无法保证全局最优性，特别依赖于初始点的选取和邻域的结构设置。当初始点选取的足够多时，倒也可以计算出全局最优解。