1. 概念简介

VNS（Variable Neighborhood Search，可变邻域搜索） 是一种元启发式算法，通过系统性地改变邻域结构来摆脱局部最优，从而找到更优解。

它依赖两个核心观察：

1. 局部最优依赖邻域定义：不同邻域下的局部最优不同。
2. 全局最优往往在某个邻域中是局部最优：系统探索多个邻域有助于发现全局更优解。

---

2. 算法思想与框架

2.1 核心步骤

EDAs（Estimation of Distribution Algorithms）是一类基于概率模型的进化优化算法。与传统遗传算法（Genetic Algorithms，GA）相比，EDAs 用分布学习 + 采样替代了交叉与变异算子，因此在结构表示能力、稳定性与全局搜索性能方面具有显著优势。

EDA vs GA

虽然 EDAs 与 GA 均属于基于种群的随机优化算法，但 EDAs 引入概率模型后具备了一系列关键优势：

• 模型驱动搜索：GA 依赖交叉与变异等随机操作，而 EDA 明确构建概率模型来描述优秀解的结构，使搜索方向更具信息性。
• 减少参数与操作复杂度：无需复杂的交叉/变异设计，也避免不合适的操作对变量依赖关系造成破坏。
• 更容易捕捉变量之间的依赖关系：通过模型（如多变量分布）自动学习特征间关联，而 GA 通常无法显式表达。
• 更适合集成机器学习思想：EDA 使用“学习—采样”循环，可自然融合统计、ML、图模型等方法。
• 更稳定的收敛行为：基于概率模型的更新通常比 GA 的随机算子更稳定，可提高全局搜索能力。

在智能优化算法的发展中，元启发式方法（Metaheuristics）因其通用性、可扩展性以及对复杂黑箱问题的强适应性而成为人工智能优化的重要组成部分。本文将系统整理元启发式算法在“是否基于模型（Model-Based vs. Model-Free）”这一维度下的分类及其特点，为从事智能优化研究或工程实践的读者提供清晰的知识结构。

---

1. 概述：为什么要关注“基于模型 vs. 非基于模型”？

传统的分类方式主要从灵感来源、解空间结构或种群规模等角度进行划分。然而，随着机器学习（ML）和优化技术的深度融合，基于模型的优化策略不断涌现，逐渐成为提升求解效率的关键技术路径。因此，“是否构建模型”成为智能优化领域一个越来越重要的视角。

一、概念与作用

多项式变异（Polynomial Mutation）是一种连续变量的变异算子，广泛应用于进化算法（如 NSGA-II、MOEA/D）中。
其主要思想是：

通过一个可调的多项式分布实现“小扰动概率高，大扰动概率低”的变异机制，
以维持种群多样性并防止早熟收敛。

---

二、基本形式

设个体的第 $i$ 个决策变量为 $x_i$，定义域为 $[x_i^{(L)}, x_i^{(U)}]$。
变异操作为：

一、背景与动机

传统遗传算法多使用二进制编码与单点交叉。
但在实际优化问题中，更自然的表示通常是实数编码。
因此，需要一种方法让实数编码的交叉操作仍然具备二进制交叉的特性。

SBX（Simulated Binary Crossover） 由 Deb 和 Agrawal（1995）提出，
其目标是在实数空间中模拟二进制交叉的“统计行为”。

一、算法简介

NPGA（Niched Pareto Genetic Algorithm） 是由 Horn、Nafpliotis 和 Goldberg 于 1994 年提出的早期多目标遗传算法。
它在多目标优化中引入了 小生境技术（Niching） 或 共享函数（Fitness Sharing），
用于保持 Pareto 前沿上解的多样性，防止解聚集在局部区域。

其核心思想是：

“用支配关系进行选择，用共享函数保持多样性。”

NSGA-II（Non-dominated Sorting Genetic Algorithm II）：Deb 等于 2002 年提出，通过快速非支配排序、拥挤度距离与精英保留策略实现高效且分布均匀的多目标优化。

算法流程图

一、算法原理与核心机制

---

1. 多目标优化问题与帕累托支配

（1）问题定义

$$\min_{\mathbf{x}\in\Omega} \mathbf{F}(\mathbf{x}) = [f_1(\mathbf{x}), f_2(\mathbf{x}), \dots, f_M(\mathbf{x})],$$

SPEA2（Strength Pareto Evolutionary Algorithm 2） 是 Zitzler、Laumanns 和 Thiele 于 2001 年提出的多目标进化算法。
它在 SPEA 的基础上改进了 适应度计算、外部精英集管理和密度估计机制，以更好地保持种群的多样性和收敛性。

算法流程图

一、算法原理与核心机制

1. 问题设定与基本符号

多目标优化问题定义为：

$$\min_{x\in\Omega} F(x) = [f_1(x), f_2(x), ..., f_M(x)]$$