---

1.摘要

VNS是一种探索性的局部搜索方法，其基本思想是在局部搜索过程中系统性地更换邻域。传统局部搜索应用于进化算法每一代的解上，但经常被批评为浪费计算时间。为了解决这些问题，本文提出：改进1-opt局部搜索VNS、多目标优化扩展自适应局部搜索机制，以及多目标遗传算法。与传统局部搜索不同，所提出的自适应局部搜索机制能够自动判断是否在遗传算法循环中使用VNS。

2.自适应局部搜索原理

尽管遗传算法（GA）在组合优化问题中能快速锁定潜力区域，但由于缺乏先验知识和深入的局部搜索能力，往往存在收敛速度慢、易陷入局部最优、难以获得高精度全局解等问题。局部搜索方法则擅长在解的邻域内进行细致优化，能够有效弥补GA的不足。如果对每一代所有个体都盲目应用局部搜索，会极大浪费计算资源，且易影响GA的全局探索能力。因此，本文提出了一种自适应局部搜索策略，结合VNS，仅在GA算法收敛遇到瓶颈时才触发局部搜索，从而高效地跳出局部最优陷阱、提升解的质量。

3.自适应变领域搜索算法Adaptive VNS

染色体表示

本文采用切分树（slicing tree）结构来编码和表示不等面积设施布局问题中的染色体。切分树是一种特殊的二叉树，用于反映不同设施的空间切割关系。对于$n$个设施，切分树包含$n$个叶节点（代表每个设施）和$n-1$个内部节点（记录切割方向）。在染色体编码上，方法将染色体分为三部分：设施顺序、切分顺序和切分方向，分别以整数和二进制（0 表示水平切割，1 表示垂直切割）进行表示。

目标函数

假设所有设施均需布置在规定区域内，且相互之间不得重叠，同时必须满足每个设施的最大宽高比等约束条件，防止出现过长或过窄的布局形状。优化目标包括两个方面：一是基于定量模型的总搬运成本（MH成本），需尽量减小；二是基于定性模型的联系关系（CR评分），需尽量提高。
$$F_1=\sum _{i=1}^n\sum _{j=1}^n{C}_{ij}{f}_{ij}{d}_{ij}$$
$$F_2=\sum _{i=1}^n\sum _{j=1}^n{r}_{ij}$$
其中，$f_{ij}$表示设施$i,j$之间物流量，$C_{ij}$表示运输成本，$d_{ij}$表示欧式距离，采用CR（联系关系）评分标准：绝对必要 = 6，基本重要 = 5，重要 = 4，一般 = 3，不重要 = 2，不受欢迎 = 1。

变邻域搜索

VNS核心特点在于会不断切换和扩展邻域范围，通过引入扰动策略跳出局部最优，进一步寻找更优解。VNS对解空间的多邻域搜索和动态调整邻域大小。

改进1-Opt局部搜索

在多目标优化中，传统加权和方法并不适用于局部搜索。因此，本文在不等面积多目标设施布局问题中，改进并引入了基于支配关系1-opt局部搜索策略，该方法通过比较当前解与邻域解的优劣关系，只要发现有邻域解能够支配当前解，即用该解进行替换，并立即终止本轮搜索，提高计算效率。

自适应局部搜索

自适应局部搜索策略结合VNS和相似性聚类方法（SCM），通过动态衡量遗传算法种群中个体的相似度，增强种群的多样性。这里对SCM进行改进，计算染色体p和q之间的相似性系数：
$$S{C}_{pq}=\frac{{\sum }_{k=1}^n\delta (f_{pk},f_{qk})}{n}$$

交叉算子

采用三点交叉算子，通过在染色体的每一部分分别选取交叉点，实现基因的有效交换。为避免基因重复或缺失，在交叉后对前两段基因进行修复：先找出重复的设施，再将缺失的设施补充替换，从而确保每一段中的基因唯一且完整。

变异算子

采用交换变异算子，在染色体的某一段内随机选择两个基因进行互换，无需修复，操作简便高效。

4.结果展示

5.参考文献

[1] Ripon K S N, Glette K, Khan K N, et al. Adaptive variable neighborhood search for solving multi-objective facility layout problems with unequal area facilities[J]. Swarm and Evolutionary Computation, 2013, 8: 1-12.

6.代码获取

xx

7.算法辅导·应用定制·读者交流