论文链接：10.1016/j.ins.2024.121406
期刊：Information Sciences
Date: January 2025
Article: 121406
Volume: Volume 689
Introduction
现有ViT压缩方法（结构化）
方法简介
two constraint handling methods两种约束处理方法
主要工作
Related Work
Vision Transformer pruning
Large-scale constrained evolutionary algorithms大规模约束进化算法
Multi-objective evolution guided ViT pruning多目标进化引导的VIT剪枝算法
overview
3.2 Multi-objective pruning for vision transformer 多目标剪枝
二进制向量代替mask：
冻结参数、Pareto、MCDM：
Algorithm 1 主框架
3.3 Large-scale constrained optimization：大规模约束优化具体实现
Algorithm 1 逻辑（一代进化）
第三步：修复 Q 里不满足 FLOPs 约束的解（Algorithm 2）
第四步：膝点引导修复（Algorithm 3）
最终剪枝模型
Result
Introduction
During the extensive research on pruning techniques, thestructured pruninghas received a great attention due to the fact that the structured pruning is performed directly on the neurons (kernels/filters in CNNs), and the pruned model is able to achieve significant inference speedups as well as storage advantages under the existing hardware speci- fications.
在对剪枝技术开展大量研究的过程中，结构化剪枝受到了广泛关注。原因在于结构化剪枝直接作用于神经元（卷积神经网络中的卷积核 / 滤波器），经过剪枝后的模型能够在现有硬件规格下实现显著的推理加速，同时获得存储优势。
现有ViT压缩方法（结构化）
patch pruning 图像块剪枝
dimension pruning 维度剪枝
ViT 的核心推理流程是：将输入图像切分为固定尺寸的图像块（patch），再把这些图像块转化为向量形式的图像块嵌入（patch embeddings）。这些嵌入向量会在多个 Transformer 块中并行推理计算，完成图像块的特征提取。最后，将最后一个 Transformer 块的输出送入分类器，完成图像分类任务。
- Patch pruning（图像块剪枝）：判断哪些图像块信息少，直接删掉这部分 patch，不再参与后续 Transformer 的计算。计算量下降，推理变快（但删掉含信息的patch会丢失图像特征，模型精度下降）。
- Dimension pruning（维度剪枝）：不删除 patch，而是裁剪嵌入向量本身的维度，压缩特征向量的长度，减少向量运算量。
方法简介
multiple criteria decision making MCDM 多准则决策：不是只看单一指标，而是让决策者参与，在多个矛盾目标之间权衡，挑选一个双方都能接受的折中方案，而不是单纯追求精度最高或者速度最快。（optimal trade-off between cost and performance.）
The proposed model entails a large-scale constrained multi-objective optimization model, called EvolutionViT, which aims to accelerate the ViT under computational resource constraints. These constraints could be in the forms of onboard memory capacity, allowed computational latency, or communication range for UAV path planning.本文提出的模型构建了一个大规模带约束多目标优化模型，命名为 EvolutionViT，目标是在计算资源约束下实现 ViT 加速。这类约束可以是机载内存容量、允许的推理延迟，或是无人机路径规划中的通信范围。
two constraint handling methods两种约束处理方法
- infeasible repair solution strategy不可行解修复策略
- knee-guided infeasible solution strategy基于膝点引导的不可行解策略
多目标优化术语，膝点（knee point）指帕累托前沿上权衡精度与速度最优的折中位置
knee solution in the evolutionary computation community 膝部解决方案（其中一个目标的进一步改进将导致另一个目标的显著退化。）
- block-based grouping optimization strategy基于块的分组优化策略
ViT 由多层堆叠Transformer 块构成
- progressive dimension reduction strategy渐进式降维策略
patches retained in the current block will also be retained in the previous blocks.当前模块保留的图像块在前面模块也同样保留
combining thegrouping optimization strategywith theprogressive dimension reduction strategy提高模型进化过程中处理大规模优化问题的能力
主要工作
- 考虑到不同边缘设备可用资源存在差异，设计约束处理策略，最大化计算资源利用率；
- 利用膝点解与边界解引导整个种群，可直接找到满足约束的折中解，有效减轻多准则决策（MCDM）过程中决策者的负担；
- 基于求得的最优解，可以直接对每个Transformer块内的图像块进行配置，从而实现 ViT 模型加速。
在 ImageNet 数据集上对所提 EvolutionViT 进行实验验证。EvolutionViT 能够根据设备允许的最大计算开销动态调整模型压缩阈值，在维持较好性能的前提下最大化设备资源利用率。
Related Work
Vision Transformer pruning
ViT 压缩主要有两类方法
- 维度/参数压缩：剪线性层矩阵、注意力头、宽度/深度等，降低特征维度和参数量，如 VTP、UVC、WDPruning。
- Patch 级剪枝：直接删除冗余图像块，如 Patch Slimming、DynamicViT、SCOP、HVT、PoWER。
本文选择 patch pruning，基于种群、有元启发式探索能力，可在满足计算约束的同时找满足偏好的knee solution（把 patch 剪枝建成大规模约束多目标优化，用分组、降维和两种约束处理算子直接搜索满足资源约束和偏好的 knee solution）
Large-scale constrained evolutionary algorithms大规模约束进化算法
求解大规模多目标优化问题（LSMOPs）时，处理常超过 1000 个决策变量，通常分三类：基于决策变量分组的 MOEA（block 分组）、基于决策空间降维的 MOEA（渐进降维）、基于新搜索策略的 MOEA。
- 变量分组是划分策略，把决策变量随机或启发式分成若干组，交替优化每组。
- 决策空间降维是缩短父代决策向量生成子代，再映射回原空间评估。
Multi-objective evolution guided ViT pruning多目标进化引导的VIT剪枝算法
overview
采样初始 ViT 架构；用预定义目标评估候选架构性能；用膝点解和边界解引导进化生成候选架构；再基于约束和大规模优化处理做交叉变异产生下一代。
（eg. DeiT推理时图像分 196 个 patch，依次经过 12 个 Transformer block 再分类；每个 patch 每过一个 block 都会变成新 patch。ViT 涉及 2000 多个 patch）
最后利用“第 L+1 个 block 保留的 patch 在第 L 个 block 也保留”的特性，用最优 patch 剪枝解剪枝 ViT，并在 ImageNet 上微调恢复性能。
3.2 Multi-objective pruning for vision transformer 多目标剪枝
二进制向量代替mask：
不同于已有 mask 准则，本文用二进制向量表示 patch 是否有效；不假设重要性数值大小，而是直接评估与剪枝模型性能损失相关的 patch 重要性。
（传统按 mask 值大小判断重要性，但不同 block 的 mask 值差异大，有些边缘提取器 patch 值小却有用；二进制直接“留/删”，用性能损失评价，避免数值准则不鲁棒。）
以 DeiT 为例：
12 个 block；
每个 block 196 个 patch；
一个个体长度 = 12 × 196 =2352 位。
每一位：
1 = 这个 block 的这个 patch 保留；
0 = 这个 block 的这个 patch 不参与该 block 的计算。
每个 block 都有自己的 0/1 选择。同一个 patch 经过不同 block 特征会变，重要性也会变。
冻结参数、Pareto、MCDM：
对训练好的 ViT，搜索剪枝方案时 Transformer block 参数通常冻结，只优化 mask；最后再微调。
（搜索阶段不是重新训练整个 ViT，而是冻结权重评估候选 mask。）
评估一个个体时，不重新训练
拿预训练好的 ViT，冻结所有权重；
按个体的 0/1 串，在每个 block 里只让 1 对应的 token 参与 attention 和 MLP；
用随机抽 ImageNet 训练集的1/10做评估子集，跑前向，得到：
- 性能损失：剪枝后模型损失函数值；
- 保留 patch 数：0/1 串里 1 的个数，间接反映计算量。
同时算这个方案的FLOPs（浮点运算次数Floating Point Operations 模型做一次前向，大概要做多少次加减乘除），看它是否落在约束范围内。
双目标：损失尽量小 + 保留 patch 数尽量少；
约束：FLOPs 必须落在阈值附近 ±10%。
DeiT-B 原始 17.6G，阈值 0.8，可行范围是 0.8 ，上下浮动 10%
在满足计算成本约束下，会有一组互相非支配的 Pareto 最优解；需要 MCDM 在两个目标间选满意折中解。
Algorithm 1 主框架
Algorithm 1：
初始化种群 P0；
非支配集选择 F；
MMD knee selection从 F 选膝点存入 Q（最小曼哈顿距离）；
Boundary individuals selection从 F 选每个目标最小的边界个体加入 Q；
Repair infeasible solution修复 Q 中不满足约束的解；
Knee guided infeasible solution进一步用膝点引导修复；
Variation based on grouping and dimension reduction生成下一代；
终止后返回满足约束的 knee solution。
3.3 Large-scale constrained optimization：大规模约束优化具体实现
- 设计分组优化策略和渐进降维策略应对 patch 剪枝大规模问题；
- 由于边缘设备资源约束，开发两种约束处理：不可行解修复策略和膝点引导不可行解策略，限制 ViT 复杂度。
Algorithm 1 逻辑（一代进化）
第一步：从当前种群选“非支配解”
两个目标：损失、保留 patch 数。
A 支配 B：A 的损失不比 B 差，保留 patch 数也不比 B 多。
非支配解：就是互相不能支配的那些方案，代表当前找到的“折中前沿”（被支配的直接淘汰）。
第二步：从非支配解里挑“膝点”和“边界解”
膝点解：折中拐点。再想省计算，精度就会明显掉；再想提精度，计算就会明显涨。用 MMD（最小曼哈顿距离）在非支配解里找折中点。
边界解：当前精度最好的解；当前保留 patch 最少的解。
把膝点和边界解放进一个集合Q，Algorithm2 只修复 Q中的不可行解。
第三步：修复 Q 里不满足 FLOPs 约束的解（Algorithm 2）
进化产生的解可能 FLOPs 太高或太低，不在可行范围。
修复方式：
从当前种群中找出所有满足 FLOPs 约束的个体，组成可行池；
对Q中每一个不满足约束的个体，若随机数小于预设的修复概率50%，则对其执行修复。
决定执行修复，从可行池中随机选择一个满足约束的个体作为参考。
按维度（逐个位）进行概率替换。以一定概率，用参考个体在某一维度上的取值，替换待修复个体在该维度上的对应取值。
参考个体从整个种群中随机选取，一定程度上保证了重点解集的多样性。
第四步：膝点引导修复（Algorithm 3）
由于上一步的概率式修复不可避免地会使重点解集中仍有部分解不满足约束，本策略在进一步修复的同时探索膝区域，以确保该集合中每个解最终均满足约束。
流程：
对Q中的每一个体，判断其是否既不是膝点解，又不满足约束条件；满足该条件的个体进入修复流程。
对该个体的每一个维度，依据自适应概率决定是否用膝点解在该维度上的取值进行替换。
替换概率随代数自适应衰减。该概率与当前代数相对于最大代数的比例相关：进化前期，不可行解的大部分维度倾向于被膝点解替换，从而向膝区域靠拢；进化后期，这一替换发生的频率显著降低，使解趋于稳定。
若膝点解本身不满足约束，则对其各维度施加随机变异，直至满足约束为止。
第五步：基于分组和降维生成下一代
在完成约束修复后，对重点解集及种群执行交叉与变异，生成下一代个体。
（一）基于 Transformer 块分组
按 Transformer block 分成 12 组，每组 196 位，
交叉与变异在每组内部独立进行：第一组与父代对应组交换片段，第二组同理，依次类推。
（二）基于嵌套规律的渐进降维
ViT 具有如下结构特性：若某一图像块在第L+1个块中被保留，则该图像块在第L个块中也必须被保留。否则，该图像块的特征在后层将不复存在，后层无法对其进行计算。
第十二个块保留的图像块，第十一个块必须保留；第十一个块保留的图像块，第十个块必须保留；依次向前递推。
后层已确定保留的图像块，在前层对应位置上的编码位被锁定为1，不参与变异操作；仅当后层未保留、前层可自主决定是否保留时，对应编码位才参与搜索。
由此，越靠前的层，可自由变异的编码位越少，搜索空间被显著压缩。
（三）交叉与变异（父代是否交叉 & 子代是否翻转）
交叉概率设为1（交叉动作一定发生），变异概率设为0.01（子代每位以1%概率翻转、生成随机数0-1，小于0.01的翻转）。
常见交叉方式：单点交叉随机选一个交叉点，交叉点前来自一个父代，后来自另一个父代。
被剪除的图像块并非永久删除，交叉与变异操作可能将其重新置为1。因此，算法无需维护用于恢复已剪枝图像块的存档，搜索空间亦非单调收缩。
生成子代后，将各组编码重新拼接为完整的个体，进入下一代评估。
最终剪枝模型
进化过程结束后，从最终代中选取一个满足 FLOPs 约束的膝点解。该解确定了每个 Transformer 块中保留图像块的具体位置。
各层保留的图像块数量逐层递减，形成前层多、后层少的层次结构。
随后执行：
依据该方案，剪除每个块中掩码为零的 token；
得到结构缩减后的 ViT；
在 ImageNet 数据集上执行微调，恢复模型精度；
部署阶段，每个块仅对保留下来的 token 进行计算，从而降低 FLOPs。
Result
所有实验用PyTorch框架，在NVIDIA A800 GPU上完成
FLOPs 只是实验里的一个代理指标，实际部署时约束可以换成内存、延迟、通信范围等
有在手机、IoT 设备、树莓派、Jetson 等边缘硬件上测实际推理延迟、内存占用或能耗。所有“资源约束”都是通过 FLOPs 计算的，不是实测