EvoOptiGraph: Weakness-Driven Coevolution via Graph-Based Structural Generation for Optimization Modeling¶

会议: NeurIPS 2026
arXiv: 2606.26578
OpenReview: https://openreview.net/forum?id=45RetuO3zX
代码: 待确认
领域: 优化/理论
关键词: 运筹优化建模、图演化生成、弱点驱动协同演化、可验证强化学习、GRPO

一句话总结¶

EvoOptiGraph 将混合整数线性规划（MILP）表示为带属性二分图并进行保结构演化生成，结合基于图特征解释的弱点诊断与求解器可验证强化学习（RLVR），构建了数据与模型动态协同演化的闭环框架。

研究背景与动机¶

自动化运筹优化建模旨在将自然语言决策问题直接转换为优化引擎可执行的形式化数学模型（如 Gurobi 代码），在物流调度、工业制造、能源管理与金融运筹等关键工业领域发挥着重要作用。传统上，这一过程严重依赖具备专业运筹学背景的人类建模专家，建模者必须准确抽离决策变量、目标函数、多重物理约束和隐式业务假设，并无误编写为求解器脚本。随着大语言模型（LLM）的发展，研究界尝试通过提示工程、多智能体协同以及特定领域有监督微调（SFT）来推进自然语言到优化代码的端到端建模，但在真实复杂业务场景中仍频现语法执行失败、约束逻辑缺失或数值解严重偏离等瓶颈。

导致当前优化建模大模型泛化受限的核心症结在于数据层面的两大固有缺陷。一方面，现有优化训练语料在结构广度上极度匮乏，现存公开基准如 NL4Opt 和 MAMO 覆盖的数学结构模式非常狭窄，传统的数据合成方法往往依赖固定的参数化模板扩充，仅机械扰动系数或表层文本措辞，无法扩展底层的变量-约束耦合拓扑；基于纯文本的演化改写虽能增强自然语言多样性，却缺乏对底层严谨数学规划结构的有效控制。另一方面，现有主流训练管线几乎均为单向静态流程，即预先离线构建固定的合成训练集，模型在冻结的静态数据分布上进行优化，导致训练机制无法动态识别模型在特定图拓扑或约束耦合模式上的结构性盲区，更无法针对性生成暴露并修补这些弱点的新颖算例。

针对上述挑战，本文提出 EvoOptiGraph 框架，其核心切入点是将 MILP 问题显式形式化为变量-约束带属性二分图，并打破数据生成与模型学习相互割裂的静态壁垒。通过在图拓扑空间上直接实施保结构的交叉与变异演化算子，系统能够突破参数扰动的局限生成结构新颖的算例；同时在留出验证集上提取图拓扑与代数特征，通过机器学习可解释性分析精准捕获模型的薄弱结构模式，据此引导生成定向针对模型盲区的高难度有效实例，最后在基于求解器严格执行与最优值校验的可验证强化学习（RLVR）下持续迭代。核心 idea：将 MILP 抽象为变量-约束二分图进行保结构演化生成，并通过机器学习可解释性提取模型在图拓扑上的弱点信号，形成“弱点诊断—靶向演化生成—求解器可验证强化学习”的数据与模型协同演化闭环。

方法详解¶

整体框架¶

EvoOptiGraph 的整体架构由三大协同模块构成：基于属性二分图的结构化实例生成引擎、基于图特征解释的模型弱点诊断器，以及基于求解器可验证奖励的强化学习优化器。系统输入为 53 类经典的运筹规划种子生成器，输出为具备鲁棒自然语言建模与无错代码生成能力的目标大模型。整个流程首先通过图演化算子合成初始种子数据集，对基座大模型（Qwen3-8B）进行有监督热身微调（SFT），使其具备基础的代码生成能力；随后进入多轮协同演化闭环，每轮首先在验证集上评估模型预测代码，提取解题失败实例的图结构特征并训练 XGBoost 诊断器计算 SHAP 弱点特征向量，进而利用弱点引导的适应度函数演化出专门靶向模型盲区的新算例池，最终通过带执行与精度奖励的 GRPO 强化学习算法更新模型参数。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["53类经典MILP种子生成器"] --> B["属性二分图表示与保结构演化"]
    B --> C["双重质量控制与确定性编译反译"]
    C --> D["热身有监督微调 SFT"]
    D --> E["结构化弱点诊断与特征重要度分析"]
    E --> F["弱点对齐的靶向演化生成"]
    F --> G["可验证奖励设计与求解器并行执行"]
    G --> H["群体相对策略优化 GRPO"]
    H -->|闭环反馈迭代至下轮诊断| E
    H --> I["输出优化建模目标模型"]

关键设计¶

1. 属性二分图表示与保结构演化：超越参数扰动的拓扑级算例合成 传统数据合成仅扰动数值参数或改写自然语言，难以拓宽变量与约束之间的代数结构空间。EvoOptiGraph 将每一个混合整数线性规划（MILP）表示为带属性二分图 $\mathcal{G} = (V, E, \mathcal{A})$，其中节点集包含变量节点 $V_{\text{var}} = \{x_1, \dots, x_n\}$ 与约束节点（含目标函数虚拟节点）$V_{\text{con}} = \{s_1, \dots, s_m, s_{\text{obj}}\}$；当变量在某约束中具有非零系数时存在边连接，边权重即为系数矩阵 $A_{ij}$。在此图空间上，算法设计了保结构完整性的演化算子：类内与类间子图交叉（交换兼容的约束子图与变量集，并通过兼容性评分 $s \ge 0.60$ 筛选父代），以及参数突变（扰动系数与上下界）、拓扑突变（合法插入或删除变量/约束）和规模突变。演化生成的所有后代图结构均能 100% 确定性编译为标准的求解器（如 Gurobi）代码，并借助高表现力模型经由三阶段一致性检查（规则校验、独立模型逻辑核查、数值回测）反向翻译为准确对应的自然语言题干。

2. 结构化弱点诊断与特征重要度分析：精准量化模型几何与拓扑盲区 为了摆脱无目的随机探索或盲目扩增数据集的低效问题，框架建立了显式的结构性弱点量化诊断机制。针对验证集上的每一个规划实例图 $\mathcal{G}$，算法提取涵盖问题规模、变量类型比例、稀疏度、非零分布、几何对齐度、图连通度及谱特征等 103 维图结构特征向量 $\phi(\mathcal{G})$。随后训练 XGBoost 分类器拟合模型的解题成败标签 $\mathbf{1}_{(\mathcal{G}, y) \in \mathcal{E}_t}$，并通过 SHAP 解释技术计算所有错题实例在各特征维度上的归因权重： $$w_k = \frac{1}{|\mathcal{E}|} \sum_{i \in \mathcal{E}} \text{SHAP}_{i, k}$$ 归一化后的弱点向量 $\mathbf{w}_t = [w_1, \dots, w_d]$ 直观量化了当前模型最容易产生幻觉或逻辑崩溃的图拓扑与约束分布模式。在后续的遗传演化中，适应度函数由静态的难度与多样性拓展为弱点对齐目标： $$f(\mathcal{G}) = \beta \tilde{f}_{\text{diff}} + \gamma \tilde{f}_{\text{div}} + \delta \tilde{f}_{\text{weak}}$$ 其中弱点对齐项 $\tilde{f}_{\text{weak}} = \text{cosine\_similarity}(\phi(\mathcal{G}), \mathbf{w}_t)$，促使生成器自适应定向制造高度贴合模型当前认知薄弱点的挑战性算例。

3. 可验证分层奖励与群体策略优化：求解器真实反馈驱动策略更新 运筹优化代码对语法执行、约束完备性与最优数值有严格的不可妥协性，标准 token 似然最大化无法有效反映逻辑正确性。EvoOptiGraph 采用基于求解器外部执行的多阶可验证奖励函数 $R(c) = R_{\text{process}}(c) + R_{\text{solvable}}(c) + R_{\text{proximity}}(c) + R_{\text{correctness}}(c)$。其中若代码无 Python 语法报错则获 $R_{\text{process}} = 0.2$；若求解器成功返回可行解，获得基础可行奖励 $R_{\text{solvable}} = 0.1$，同时激活连续逼近奖励： $$R_{\text{proximity}} = 0.2 \cdot \max\left(0, 1 - \frac{\text{relerr}}{0.1}\right), \quad \text{where } \text{relerr} = \frac{|f_{\text{model}} - f_{\text{opt}}|}{|f_{\text{opt}}| + 10^{-8}}$$ 当相对误差在 10% 范围内时提供平滑的梯度引导，反映捕获主体约束骨架的合理性；当求解器状态达到全局最优且 $\text{relerr} \le 10^{-4}$ 时，赋予全额正确奖励 $R_{\text{correctness}} = 0.5$。在此精细奖励塑造下，框架采用 Group-Relative Policy Optimization (GRPO) 进行强化学习，通过同题多采样优势归一化与 KL 正则惩罚更新 LoRA 权重，确保模型在牢固掌握可执行代码结构的同时逼近全局最优建模。

损失函数 / 训练策略¶

训练分为两个阶段。在第一阶段，使用通过图演化生成的 5,000 个基础多样化实例对 Qwen3-8B 实施标准因果语言建模 SFT 热身： $$\mathcal{L}_{\text{SFT}}(\theta) = -\sum_{t} \log P_\theta(c_t \mid c_{<t}, q)$$ 超参数采用 LlamaFactory 框架，LoRA rank=32, alpha=64, 学习率 $1 \times 10^{-4}$ 训练 3-5 个 epoch。第二阶段执行 $T$ 轮协同演化 RLVR 更新，每轮使用演化生成的 1,000 个弱点定向新算例，基于 TRL 的 GRPOTrainer 采样 $G=4$ 个候选代码并并发调用 Gurobi 求解器求算分层奖励，以学习率 $5 \times 10^{-6}$、温度 0.7 优化目标函数： $$\mathcal{J}_{\text{GRPO}}(\theta) = \mathbb{E}_{q \sim \mathcal{D}_{\text{RL}}, \{y_i\} \sim \pi_{\theta_{\text{old}}}}\left[\frac{1}{N} \sum_{i=1}^N \left(\min\left(r_i(\theta)\hat{A}_i, \text{clip}(r_i(\theta), 1-\epsilon, 1+\epsilon)\hat{A}_i\right) - \widetilde{\beta} \mathbb{D}_{\text{KL}}(\pi_\theta \parallel \pi_{\text{ref}})\right)\right]$$ 其中每轮用于训练 XGBoost 弱点诊断器的独立验证子集规模为 2,000 个算例。

实验关键数据¶

主实验¶

评估在六个经过社区严格清洗的公开运筹优化基准上展开，采用 Pass@1 求解正确率（即求解器最优目标值与真实标注值相对误差 $\le 10^{-4}$ 且状态一致）作为核心评价指标。主要结果如下表所示：

模型	参数量	NL4OPT	MAMO EasyLP	MAMO ComplexLP	NLP4LP	ComplexOR	IndustryOR	Macro Avg. (%)
零样本通用大模型
GPT-4o	Closed	73.4	95.2	46.0	87.6	38.9	66.7	68.0
DeepSeek-V3	671B	79.9	96.7	55.0	94.9	44.4	69.1	73.3
Qwen3-32B	32B	76.1	96.9	32.4	90.5	38.9	57.1	65.3
Qwen2.5-72B-Inst	72B	79.9	95.8	33.3	89.9	38.9	61.9	66.6
智能体与多步推理方法
OptiMUS-v0.3	Closed	79.8	92.4	52.1	89.8	52.2	54.3	70.1
CoT (GPT-4)	Closed	62.2	49.5	42.3	74.7	39.2	40.5	51.4
Chain-of-Experts	Closed	66.7	94.4	50.6	87.4	57.1	31.2	64.6
运筹领域微调模型
ORLM	8B	73.8	90.4	59.5	76.4	50.0	42.9	65.5
LLMOPT* (未清洗基准)	14B	80.3*	89.5*	44.1*	73.4*	35.3*	29.0*	58.6*
OptMATH* (未清洗基准)	32B	95.9*	89.9*	54.1*	-	-	-	-
EvoOptiGraph (本文)	8B	96.7	98.0	69.4	97.2	50.0	57.1	78.1

注：* 标为原论文报告成绩（基于未清洗历史版本，仅供参考）。

消融实验¶

为验证两阶段协同演化框架中 SFT 热身与弱点引导 RLVR 两个核心支柱的独立贡献，论文对比了仅使用 SFT 持续多轮迭代（All-SFT）和直接在基座上仅使用强化学习（All-RL）的消融表现：

训练配置方案	NL4OPT	MAMO EasyLP	MAMO ComplexLP	NLP4LP	ComplexOR	IndustryOR	Macro Avg. (%)	较完整模型差距
EvoOptiGraph (完整协同演化)	96.7	98.0	69.4	97.2	50.0	57.1	78.1	-
All-SFT (仅多轮监督微调)	85.5	96.0	55.9	91.6	38.9	42.9	68.5	$\downarrow 9.6\%$
All-RL (无 SFT 热身直接强化学习)	72.0	96.3	33.3	87.6	38.9	52.4	63.4	$\downarrow 14.7\%$

在数据生成多样性评估中，采用 GenBench-MILP 结构相似度指标（越低代表结构多样性越丰富）：OptMATH 的结构相似度高达 93.04%，而 EvoOptiGraph 的结构相似度仅为 66.93%，证明基于图拓扑的交叉与变异生成的实例在数学结构上大幅超越了单纯基于文本和参数扰动的方法。

关键发现¶

两阶段互为依存：缺少 SFT 初始化的 All-RL 下降幅度最大（-14.7%），因为缺乏基本代码语法与变量命名规范的模型在极稀疏的正确率奖励下难以稳定探索；而 All-SFT 在首轮显著提升后迅速陷入过拟合平台期（-9.6%），表明静态监督学习无法解决解空间精细数值对齐的根本问题。
参数规模的“逆袭”：基于 Qwen3-8B 的 EvoOptiGraph 在 6 大基准综合平均分达到 78.1%，显著战胜了 671B 规模的 DeepSeek-V3（73.3%）与闭源商业模型 GPT-4o（68.0%），证明针对模型结构盲区的高效自适应演化训练比盲目扩增通用模型参数具有更高的任务学习效率。
自纠错协同演化轨迹：在跟踪多轮 RL 迭代的动态曲线中，模型在极具挑战的 MAMO-complex 基准上在 RL2 轮次出现局部退化，但在靶向弱点特征修正后于 RL3 轮次重新大幅反弹，体现出闭环系统具有自发摆脱局部模式崩溃的调节能力。

亮点与洞察¶

拓扑空间遗传演化 vs 文本空间扰动：将数学建模任务还原到底层因果图（二分图）结构空间进行交叉与突变，从根本上保证了代数完备性与可解性，突破了传统 LLM 数据增强中“改写描述却未改变数学本质”的形式主义陷阱。
SHAP 弱点反向引导采样设计：打破了强化学习通常依赖静态数据池采样的常规，用树模型特征归因将大模型的“解题错因”解构为可计算的图拓扑偏好向量，为生成模型提供了极其明确的“出题”方向。
分层连续逼近奖励设计：在可验证强化学习中，不仅奖赏完全无误的解，还通过 $10\%$ 相对误差衰减惩罚为局部正确代码提供平滑梯度，避免了由于 MIP 组合离散解严格校验带来的 reward hacking 或极端稀疏性导致的优化震荡。

局限与展望¶

问题形式覆盖受限：目前图编译与演化机制严格锚定在线性混合整数规划（MILP）范畴，尚无法直接支持非线性规划（NLP）、非凸二次约束规划（MIQCP）或偏微分约束优化问题。
大规模求解验证瓶颈：随着演化算例规模与约束维度的增加，外部求解器（如 Gurobi）验证可行性与全局最优的耗时呈现指数级上涨，在大规模工业实时演化场景中存在计算瓶颈。
弱点特征的统计偏置：利用 XGBoost + SHAP 提取的弱点向量本质上是统计相关性表征而非严格因果判断，对潜在未见问题类别可能存在泛化先验偏差。未来可探索与形式化证明生成结合的动态因果弱点归因。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 基于属性二分图的保结构算例演化与基于可解释性弱点诊断的数据-模型协同演化架构构思精巧。
实验充分度: ⭐⭐⭐⭐⭐ 在涵盖 6 个主流清洗基准的 Pass@1 综合评测、多样性量化与深入消融分析上均非常严谨。
写作质量: ⭐⭐⭐⭐⭐ 论文逻辑清晰，问题阐述与数学表达规范，图表呈现详实。
价值: ⭐⭐⭐⭐⭐ 为大模型在运筹优化、符号数学及形式化代码生成等严格对错场景下的闭环自适应后训练提供了具有指导意义的范式。