# KEMM-DMOEA

> 基于运动学增强的记忆驱动流形迁移学习动态多目标进化算法
> 
> Kinematic-Enhanced Memory-driven Manifold Transfer Learning for Dynamic Multi-Objective Optimization

一种高性能动态多目标进化算法，结合记忆驱动精英保留机制与流形迁移学习（SGF），加速求解动态多目标优化问题（DMOPs）。包含真实应用场景：动态海洋环境下的船舶多目标路径规划。

---

## 📖 研究背景与动机

### 问题定义

动态多目标优化问题（DMOPs）广泛存在于真实工程场景中，其目标函数、约束条件和参数会随时间发生变化：

> *"许多真实优化问题涉及多个目标、约束和参数，这些要素会随时间变化。求解DMOPs的难点在于需要高效且准确地跟踪变化的Pareto最优前沿。"*
> — 来源：知识库论文摘要（MMTL-DMOEA, IEEE Transactions on Cybernetics, 2020）

### 核心挑战

不同时刻的解分布是非独立同分布（Non-IID）的：

> *"尽管不同时刻的解分布之间可能存在潜在关系，但它们并不是完全相同的。"*
> — 来源：知识库 Section I（引言）

### 现有方法的不足

现有基于迁移学习的方法（如 Tr-DMOEA）存在两个缺陷：
1. 超参数调优代价高 — 寻找最优隐空间需要大量计算
2. 迁移计算成本高 — 即使找到隐空间，计算开销仍然巨大

> *"本文的核心动机是：在不损失解质量的前提下，加速DMOPs的求解。"*
> — 来源：知识库 Section I（引言）

---

## 🔬 算法概述

### 理论基础

KEMM-DMOEA 基于 MMTL-DMOEA 框架构建，该框架的核心思想是：

> *"将记忆机制（保留历史最优个体）与流形迁移学习（预测新环境下的最优个体）相结合。"*
> — 来源：知识库摘要

两种机制的结合优于单独使用：

> *"两种机制的组合优于仅使用单一机制。"*
> — 来源：知识库 Section IV-B（消融实验）

### 核心组件

┌─────────────────────────────────────────────────────────────┐ │ KEMM-DMOEA 算法框架 │ │ │ │ ┌──────────────┐ ┌──────────────┐ ┌──────────────┐ │ │ │ Process 2 │ │ Process 3 │ │ 改进模块 │ │ │ │ FindBestSol │ │ Transfer │ │ │ │ │ │ │ │ │ │ ・线性度检测 │ │ │ │ ・SVR估计 │ │ ・LPCA聚类 │ │ ・负迁移检测 │ │ │ │ ・非支配排序 │ │ ・SGF测地流 │ │ ・PCA微扰 │ │ │ │ ・大小调整 │ │ ・内点法映射 │ │ ・动态维度 │ │ │ └──────┬───────┘ └──────┬───────┘ └──────┬───────┘ │ │ │ │ │ │ │ └────────┬────────┘──────────────────┘ │ │ ▼ │ │ ┌────────────────┐ │ │ │ NSGA-II 进化 │ ← 记忆库 (APF指纹索引) │ │ └────────┬───────┘ │ │ ▼ │ │ ┌────────────────┐ │ │ │ KPO 运动学投影 │ ← 船舶路径规划专用 │ │ └────────────────┘ │ └─────────────────────────────────────────────────────────────┘

| 组件 | 功能 | 知识库来源 |
|------|------|-----------|
| FindBestSol（Process 2） | SVR估计器构建 + 非支配排序选择精英 | *"构建SVR估计器需要O(ns²d)"* — Section III |
| Transfer（Process 3） | LPCA聚类 + Grassmann流形上的SGF测地流 | *"在流形上两点之间构建测地流...选择k个中间点"* — Section II-B |
| 记忆机制 | 跨时刻精英保留与检索 | *"计算资源用于通过记忆机制进行精英个体的知识迁移"* — Section I |
| NSGA-II引擎 | 多目标进化优化 | 基线SMOA框架 |

### SGF（样本测地流）原理

流形迁移学习的核心方法：

> *"SGF算法在两个域之间构建一条测地路径，然后通过该路径将知识传输到目标域。源域和目标域被映射到Grassmann流形G(d,n)上的起点S₀和终点S₁，算法从S₀到S₁构建测地流，然后选择k个中间点，最终将源域和目标域的数据变换到这些中间子空间。"*
> — 来源：知识库 Section II-B（基于流形的迁移学习）

### KEMM-DMOEA 四项核心改进

| 改进项 | 解决的问题 | 方法 | 来源依据 |
|--------|-----------|------|---------|
| 自适应模式切换 | SGF在简单线性变化（FDA系列）上过拟合 | 检测变化线性度 → 高线性用KF预测，低线性用SGF | *"MMTL-MOEA/DM优于MMTL-MOEA/DT...DT对参数更敏感"* — Section IV-B |
| PCA微扰 + 动态维度 | 流形坍塌（PCA除零警告） | 注入ε=1e-6噪声；按95%累计贡献率动态确定维度 | *"将解聚类到低维流形...遇到挑战导致Transfer性能下降"* — Section IV |
| 条件性SVR | SVR计算瓶颈 O(N²d) | 高线性度时跳过SVR；降低max_iter | *"构建SVR估计器需要O(ns²d)"* — Section III |
| 负迁移检测 | 迁移质量差导致解退化 | 迁移后立即评价质量，低于阈值则回退 | *"正迁移和负迁移被自动识别以抑制负迁移"* — Section II-C 引用[32] |

---

## 📁 项目结构

KEMM-DMOEA/ ├── kemm_dmoea_core.py # 核心算法 + 船舶路径规划应用 ├── benchmark_algorithms.py # 6种对比算法 + 评价指标 + 测试函数 ├── run_experiments.py # 主入口：实验调度 + 可视化 ├── README.md # 本文件 ├── requirements.txt # 依赖 └── out_.png / ship_t.png # 生成的图表（运行后）

### 文件说明

| 文件 | 职责 | 关键类/函数 |
|------|------|-----------|
| `kemm_dmoea_core.py` | KEMM-DMOEA完整实现 + 船舶规划 | `KEMMDMOEA`, `KinematicProjectionOperator`, `EnvironmentFieldMemory`, `ManifoldTransfer`, `FindBestSol`, `MultiObjectiveEvaluator` |
| `benchmark_algorithms.py` | 对比算法 + 测试函数 + 指标 | `RI_DMOEA`, `PPS_DMOEA`, `KF_DMOEA`, `SVR_DMOEA`, `Tr_DMOEA`, `MMTL_DMOEA`, `KEMM_DMOEA_Abstract`, `DynamicTestProblems`, `PerformanceMetrics` |
| `run_experiments.py` | 实验运行 + 结果展示 | `ExperimentRunner`, `ResultPresenter`（生成15张图表）, `run_benchmark()`, `run_ship()` |

---

## ⚙️ 安装

### 环境要求

- Python >= 3.8
- NumPy, SciPy, scikit-learn, matplotlib

### 安装依赖

```bash
pip install numpy scipy scikit-learn matplotlib

可选：GPU加速

pip install cupy-cuda12x  # NVIDIA GPU 加速大矩阵运算

---

🚀 运行方式

快速验证（首次运行推荐）

python run_experiments.py --quick

运行 3 个测试函数 × 3 次独立实验，约 30~60 秒完成。

完整基准实验

python run_experiments.py --full

运行全部 6 个测试函数 × 5 次独立实验，参数与论文设置完全一致：

"种群大小N=100；外部存储容量C=10×N；FindBestSol中的采样个体数ns=30；Transfer中的流形分段数L=4；中间子空间数p=5。" — 来源：知识库 Section IV（实验参数）

仅运行船舶路径规划

python run_experiments.py --ship-only

运行 5 个时间步的动态船舶路径规划。

完整实验 + 船舶规划

python run_experiments.py --all

---

📊 实验设置

算法参数

参数	值	来源
种群大小 (N)	100	"种群大小N设为100" — Section IV
外部存储 (C)	10×N	"外部存储容量C设为10×N" — Section IV
SVR采样数 (ns)	30	"FindBestSol中采样个体数ns=30" — Section IV
流形分段数 (L)	4	"Transfer中流形分段数L=4" — Section IV
中间子空间数 (p)	5	"Transfer中中间子空间数p=5" — Section IV
变化严重程度 (nt)	10	"nt=10, τt=10" — Section IV
变化频率 (τt)	10	"nt=10, τt=10" — Section IV

对比算法

算法	简称	描述	来源
RI-DMOEA	RI	随机重初始化基线	"RI-MOEA/D" — Section IV
PPS-DMOEA	PPS	种群预测策略	"PPS通过自回归模型预测下一个质心" — Section II
KF-DMOEA	KF	卡尔曼滤波预测	"KF-MOEA/D消耗更少的时间" — Section IV-D
SVR-DMOEA	SVR	支持向量回归预测	"构建SVR估计器需要O(ns²d)" — Section III
Tr-DMOEA	Tr	迁移学习框架	"Tr-DMOEA集成TL和种群进化算法" — Section I
MMTL-DMOEA	MMTL	记忆驱动流形迁移学习（论文原始算法）	"结合记忆 + 流形TL" — 摘要
KEMM-DMOEA	KEMM	本文算法 — 增强版MMTL	—

测试函数

函数	类型	POS变化	POF变化	难度特征
FDA1	Type I	✅	❌	决策空间平移，前沿不变
FDA2	Type II	❌	✅	决策空间不变，前沿形状变化
FDA3	Type III	✅	✅	决策空间和前沿同时变化
dMOP1	Type I	✅	❌	非线性决策空间变化
dMOP2	Type II	✅	✅	决策空间和前沿耦合变化
dMOP3	Type I	✅	❌	与FDA1类似，验证鲁棒性

评价指标

三项指标均来源于知识库 Section IV-A：

1. MIGD（平均反世代距离）

"MIGD = (1/|T|) Σ IGD(POF*_t, POF_t) — 各时间步IGD值的均值。值越小表示收敛性越好、多样性越高。" — 来源：知识库 公式(6)

2. SP（Schott间距指标）

"Schott间距指标衡量解的均匀性。SP值越小反映分布越均匀。" — 来源：知识库 公式(7)

3. MS（最大分布范围）

"最大分布范围衡量所得解在真实POF上的覆盖程度。MS值越大表示覆盖范围越广。" — 来源：知识库 公式(8)

---

📈 输出图表

运行实验后共生成 15 张论文级可视化图表 + 5 张船舶路径图：

第一组：指标对比柱状图（对应论文 Tables I-III）

编号	文件名	内容描述
1	out_migd_bar.png	MIGD柱状图：每个测试函数一个子图，7个算法各一根带误差棒的柱子。🟡金色=最优，🔴红色=KEMM。对应论文 "表1：MIGD均值与标准差"
2	out_sp_bar.png	SP柱状图：格式同上。对应 "表2：SP均值与标准差"
3	out_ms_bar.png	MS柱状图：格式同上。对应 "表3：MS均值与标准差"

第二组：动态跟踪曲线（对应论文 Fig.3）

编号	文件名	内容描述
4	out_igd_over_time.png	IGD随时间变化曲线：横轴=环境变化次数(1~10)，纵轴=IGD值。每条曲线=一个算法，实线=均值，半透明带=标准差。KEMM用粗实线。对应论文 "图3展示了不同算法在每次变化后的IGD值。可以看到本文方法的曲线在大多数情况下位于最底部，且曲线更平滑" — Section IV

第三组：综合性能图

编号	文件名	内容描述
5	out_radar.png	四维性能雷达图：MIGD↓、SP↓、MS↑、Speed↓ 四个轴。KEMM用粗实线+半透明填充，其他算法用细虚线。展示算法综合均衡性

第四组：稳定性分析箱线图

编号	文件名	内容描述
6	out_migd_box.png	MIGD箱线图：每个测试函数一个子图。箱体=四分位距，🔶红色菱形=均值。KEMM箱体为红色加粗。展示多次运行的稳定性
7	out_sp_box.png	SP箱线图：格式同上
8	out_ms_box.png	MS箱线图：格式同上

第五组：全局对比热力图

编号	文件名	内容描述
9	out_migd_heatmap.png	MIGD热力图：行=7个算法，列=6个测试函数。每列独立归一化（🟢绿色=最优，🔴红色=最差）。格内标注实际MIGD值。一图纵览全局优劣

第六组：胜负与排名统计

编号	文件名	内容描述
10	out_win_count.png	胜出次数统计：三组并排柱子（🔵MIGD / 🟢SP / 🔴MS），展示每个算法在6个问题中获得最优的次数。对应论文表格底部的"Wins"行
11	out_cd_rank.png	CD排名图：基于Friedman平均排名的水平条形图。条越短=排名越靠前。🔴红色=KEMM（标注★）。对应学术论文中标准的 Critical Difference 分析

第七组：计算效率分析（对应论文 Tables V-VI）

编号	文件名	内容描述
12	out_speedup.png	效率分析双图：(a) 绝对运行时间柱状图；(b) 质量-速度效率比 1/(MIGD×Time)。对应论文 "本文方法大幅提升了运算速度，加速比达到数百倍" — Section IV Tables V-VI
13	out_tradeoff.png	MIGD-Time权衡散点图：横轴=运行时间，纵轴=MIGD。每个点=一个(算法,问题)组合。KEMM用大号加框标记。左下角=理想区域。直观展示核心动机："加速求解且不损失解质量"

第八组：鲁棒性与对比分析

编号	文件名	内容描述
14	out_rank_evolution.png	跨问题排名折线图：横轴=6个测试函数，纵轴=MIGD排名(1=最优)。KEMM用粗实线。线越平=算法越鲁棒
15	out_pairwise.png	两两对比矩阵：7×7矩阵，格内"X/Y"表示行算法在(MIGD+SP)×6个问题中击败列算法的次数。颜色深度表示胜率。对角线为"—"

船舶路径规划图

编号	文件名	内容描述
S1~S5	ship_t0.png ~ ship_t4.png	每个时间步的路径规划结果。🔴红色圆=障碍物（虚线圈=安全区）、🔵蓝色线=Pareto最优路径集、🟢绿色线=最佳折中路径、▲=起点、★=终点

---

🚢 船舶路径规划应用

四目标优化

目标	描述	类型
f₁	路径总长度	最小化
f₂	碰撞风险（基于安全距离）	最小化
f₃	燃油消耗（考虑洋流助力/阻力）	最小化
f₄	航行平稳性（累计转角）	最小化

动态环境要素

• 12个障碍物：6个静止（岛礁）+ 6个移动（他船）
• 洋流场：3个高斯涡旋 + 全局漂流
• 运动学约束：最小转弯半径、速度上下限（KPO模块投影）

算法响应周期

每个时间步执行完整的 Process 1 流程：

时间步 t:
  1. [检测]   环境变化检测 (APF势场指纹距离)
  2. [选择]   Process 2: FindBestSol — SVR估计 + 非支配排序
  3. [迁移]   Process 3: Transfer — 多源加权SGF测地流
  4. [进化]   NSGA-II 多代进化 + KPO运动学投影
  5. [存储]   记忆存储 (Process 1, Lines 10-14)
  6. [输出]   Pareto前沿 + 折中最优路径

---

🔧 计算复杂度

来源：知识库 Section III

组件	复杂度	来源原文
FindBestSol (SVR)	O(N²d)	"构建SVR估计器需要O(ns²d)...FindBestSol的计算复杂度为O(N²d)"
Transfer (LPCA聚类)	O(d²)	"LPCA聚类需要O(d²)"
Transfer (SGF构建)	O(d²) + O(1)	"构建测地流：O(d²)和O(1)"
Transfer (内点法)	O(m³n)	"内点法求解：O(m³n)"
非支配排序	O(N²m)	"快速非支配排序为O(N²m)"

---

📋 引用

如果您使用了本代码，请引用基础工作：

@article{jiang2020mmtl,
  title={A Memory-Driven Manifold Transfer Learning Based Evolutionary Algorithm 
         for Dynamic Multiobjective Optimization},
  author={Jiang, Min and Wang, Zhenzhong and Guo, Shihui and Gao, Xing 
          and Tan, Kay Chen},
  journal={IEEE Transactions on Cybernetics},
  year={2020},
  publisher={IEEE},
  doi={10.1109/TCYB.2020.2989465}
}

---

📜 许可证

本项目仅供学术研究使用。详见 LICENSE。

---

🔗 致谢

• MMTL-DMOEA 框架（Jiang 等, IEEE TCYB, 2020）
• SGF 流形迁移学习方法
• FDA 和 dMOP 动态测试函数集