DQN 解三维在线装箱：从 MDP 建模到训练调参实战

简介这份资源面向计算机、人工智能及相关专业的在校学生与算法学习者提供一套基于DQN深度强化学习求解三维在线装箱问题的完整Python实现。三维装箱是物流运输中的经典优化难题目标是在线将箱子装入车厢并尽量提升空间利用率通常填满85%即可视为较优方案。资源包共10个文件包含5个py源码、2张png示意图、1个fig1图形文件、1份md说明文档和1个pth模型权重压缩包约5.64MB涵盖训练、评估、绘图与容器建模等模块结构清晰便于按流程阅读。目前已有104人学习下载。读者可借助源码与文档理解DQN在三维装箱中的状态表示、动作选择与奖励设计并参考已训练模型快速复现实验也可在此基础上修改以适配课程设计、毕业设计或项目初期演示。1. 三维在线装箱为什么难从 DQN 的视角重新理解这个经典 NP-hard 问题三维在线装箱问题3D Online Bin Packing和离线版本最大的区别在于物品是一个一个到达的你必须在不知道后续物品尺寸、数量、分布的前提下当场决定把它放进哪个箱子的哪个位置。这个当场两个字直接把问题从组合优化推到了序贯决策的地盘上。传统做法比如 First Fit Decreasing、Best Fit 这类启发式规则在离线场景下表现尚可但一旦物品流变成在线到达规则就变成了盲选——它没有记忆不会根据已经装过的历史调整策略更不会预判现在留出的这块空隙后面会不会有更合适的物品来填。DQNDeep Q-Network之所以被拿来解这个问题核心逻辑是把当前所有箱子的空间状态 新到达物品的尺寸编码成一个状态向量把放入哪个箱子的哪个位置离散化成动作空间用神经网络去逼近 Q 值函数让智能体在反复试错中学会一套比固定启发式更灵活的放置策略。它不保证全局最优但在线场景下它有机会学到什么时候该开新箱、什么时候该塞进已有空隙这种规则难以写死的判断。这套方案适合谁如果你正在做物流调度、集装箱装载、云资源分配这类需要实时决策的工程问题或者你在做强化学习的落地项目但苦于找不到一个状态空间可控、奖励信号清晰的练手场景三维在线装箱是一个非常好的切入点。Python 源代码 文档说明的组合意味着你可以直接跑起来看效果而不是从零推导公式。接下来我会把整个方案的骨架拆开从环境建模到 DQN 网络结构再到训练调参和踩坑记录一步步讲清楚。2. 把装箱问题翻译成 MDP状态、动作、奖励怎么定义才不翻车2.1 状态编码为什么不能直接把箱子坐标丢给网络三维装箱的状态空间天然是连续的——箱子的长宽高是实数物品的位置是三维坐标。如果你直接把原始坐标喂给全连接网络维度会爆炸而且网络很难从绝对坐标里学到剩余空间这个概念。常见的做法是把状态压缩成几个关键特征当前所有已开箱子的剩余空间体积、每个箱子的空间利用率、新到达物品的三维尺寸、物品体积与当前最大剩余空间的比值。我一般会用固定长度的向量来表示状态比如限制最大箱子数量为 N每个箱子提取 5 个特征剩余体积、利用率、最大连续空隙的长宽高再加上物品本身的 3 个尺寸特征状态维度就是 5N3。这样网络输入维度可控训练也稳定。如果你想让网络看到更细的空间分布可以把每个箱子切成 K×K×K 的网格用 0/1 表示每个格子是否被占用但这样状态维度会变成 N×K³K 取 10 就是 1000 维一个箱子训练成本陡增。我的建议是先用低维特征跑通再考虑要不要上网格。import numpy as np class BinPackingEnv: def __init__(self, bin_size(10, 10, 10), max_bins5): self.bin_size np.array(bin_size) self.max_bins max_bins self.reset() def reset(self): # 每个箱子记录已放置物品列表和剩余空间 self.bins [self._empty_bin() for _ in range(self.max_bins)] self.current_item None return self._get_state() def _empty_bin(self): return { items: [], remaining_volume: np.prod(self.bin_size), used_volume: 0 } def _get_state(self): # 状态向量每个箱子5个特征 物品3个尺寸 state [] for b in self.bins: max_gap self._max_contiguous_gap(b) state.extend([ b[remaining_volume] / np.prod(self.bin_size), b[used_volume] / np.prod(self.bin_size), max_gap[0] / self.bin_size[0], max_gap[1] / self.bin_size[1], max_gap[2] / self.bin_size[2], ]) if self.current_item is not None: state.extend(self.current_item / self.bin_size) else: state.extend([0, 0, 0]) return np.array(state, dtypenp.float32)这段代码里_get_state是核心它把每个箱子的剩余体积、利用率、最大连续空隙归一化后拼成一个固定长度向量。max_bins决定了状态维度我一般设 5 到 10太小会导致频繁开新箱太大则状态冗余、训练慢。_max_contiguous_gap需要你自己实现简单做法是遍历箱子内已放置物品的包围盒找最大空余区间。2.2 动作空间设计离散化是必须的但怎么离散有讲究DQN 只能处理离散动作所以你必须把放到哪个箱子的哪个位置变成有限个选项。最粗暴的做法是动作 箱子编号 × 位置编号。位置可以预定义为箱子内的若干候选点比如八个角、六个面中心、正中心一共 15 个候选位置。这样动作空间就是 max_bins × 15。如果 max_bins5动作数就是 75对 DQN 来说完全可以接受。但这里有个坑不是所有动作都合法。比如物品尺寸超过了某个候选位置所在空隙的尺寸这个动作就应该被屏蔽。常见做法是在输出 Q 值后把非法动作的 Q 值设成负无穷再做 argmax。这样网络不需要浪费容量去学哪些动作非法只需要学合法动作里哪个最好。def get_valid_actions(self): valid [] for bin_idx, b in enumerate(self.bins): for pos_idx, pos in enumerate(self.candidate_positions): if self._can_place(b, self.current_item, pos): valid.append(bin_idx * len(self.candidate_positions) pos_idx) return valid def step(self, action): bin_idx action // len(self.candidate_positions) pos_idx action % len(self.candidate_positions) pos self.candidate_positions[pos_idx] if not self._can_place(self.bins[bin_idx], self.current_item, pos): return self._get_state(), -1.0, False, {reason: invalid_placement} self._place_item(self.bins[bin_idx], self.current_item, pos) reward self._compute_reward(bin_idx) done self._is_episode_done() return self._get_state(), reward, done, {}get_valid_actions返回当前所有合法动作的索引训练时用它来屏蔽非法动作。step函数里如果动作非法直接给 -1 的惩罚并结束当前回合这样网络会学会避开非法动作。_compute_reward的设计很关键我后面会单独讲。2.3 奖励函数稀疏奖励是 DQN 在装箱问题上的最大敌人如果你只在回合结束时给一个最终用了几个箱子的奖励那 DQN 基本学不动因为中间几十步的决策没有任何反馈Q 值传播不到早期动作。我的做法是设计一个塑形奖励shaped reward每成功放置一个物品给一个正奖励大小和这次放置后箱子利用率的提升成正比如果这次放置导致某个箱子的剩余空间变得碎片化最大连续空隙显著减小给一个小惩罚如果必须开新箱才能放下当前物品给一个较大的负奖励。具体公式可以写成reward α × Δutilization - β × fragmentation_penalty - γ × new_bin_penalty。α、β、γ 是超参数我一般设 α1.0β0.3γ0.5。这个奖励设计不是唯一的但核心思想是让每一步都有信号同时引导智能体优先填满已有箱子而不是动不动开新箱。注意奖励塑形会改变最优策略的定义。如果你把开新箱的惩罚设得太大智能体可能会强行把物品塞进不合适的空隙导致后续物品放不进去。建议先用小惩罚跑一轮看平均箱数再调整。3. DQN 网络结构与训练流程从经验回放到目标网络更新3.1 网络结构全连接够用但别忽略特征归一化三维装箱的状态向量维度不高通常几十到几百维用 3 层全连接网络就够了。我的配置是输入层 → 256 → 256 → 输出层动作数。激活函数用 ReLU输出层不加激活。损失函数用 MSE优化器用 Adam学习率从 1e-3 开始试。关键点是特征归一化。状态向量里的体积、尺寸都是实数如果不归一化大数值特征会主导梯度。我在_get_state里已经把体积除以了箱子体积、尺寸除以了箱子边长这一步不能省。另外经验回放池里的状态也要保持同样的归一化方式否则训练和推理不一致。import torch import torch.nn as nn class DQN(nn.Module): def __init__(self, state_dim, action_dim, hidden256): super().__init__() self.net nn.Sequential( nn.Linear(state_dim, hidden), nn.ReLU(), nn.Linear(hidden, hidden), nn.ReLU(), nn.Linear(hidden, action_dim) ) def forward(self, x): return self.net(x) # 初始化 state_dim 5 * 5 3 # max_bins5, 每箱5特征 物品3特征 action_dim 5 * 15 # 5个箱子 × 15个候选位置 policy_net DQN(state_dim, action_dim) target_net DQN(state_dim, action_dim) target_net.load_state_dict(policy_net.state_dict())state_dim和action_dim必须和你的环境配置一致。hidden256是我在 5 个箱子、15 个候选位置的配置下试出来的如果你把 max_bins 加到 10状态维度变成 53256 仍然够用。如果动作空间超过 500建议把 hidden 加到 512。3.2 经验回放与目标网络两个让训练稳定的关键机制DQN 相比普通 Q-learning 最大的改进就是经验回放和目标网络。经验回放把每一步的 (state, action, reward, next_state, done) 存进一个固定大小的池子训练时随机采样一批打破时间相关性。目标网络则是一个定期从策略网络复制参数的副本用来计算 TD 目标避免 Q 值追着自己跑。from collections import deque import random class ReplayBuffer: def __init__(self, capacity10000): self.buffer deque(maxlencapacity) def push(self, state, action, reward, next_state, done): self.buffer.append((state, action, reward, next_state, done)) def sample(self, batch_size): batch random.sample(self.buffer, batch_size) states, actions, rewards, next_states, dones zip(*batch) return (np.array(states), np.array(actions), np.array(rewards), np.array(next_states), np.array(dones)) def __len__(self): return len(self.buffer)capacity10000是起步值如果你的回合长度超过 200 步建议加到 50000。sample返回的是 numpy 数组后面要转成 torch tensor。注意dones的处理如果 doneTrueTD 目标就是 reward不再加下一状态的 Q 值。训练循环里每步先选动作ε-greedy执行后存进回放池然后从池里采样一批算损失。ε 从 1.0 线性衰减到 0.1衰减步数一般设总训练步数的 10% 到 20%。目标网络每 C 步更新一次C 通常取 100 到 500。def train_step(policy_net, target_net, optimizer, batch, gamma0.99): states, actions, rewards, next_states, dones batch states torch.FloatTensor(states) actions torch.LongTensor(actions) rewards torch.FloatTensor(rewards) next_states torch.FloatTensor(next_states) dones torch.FloatTensor(dones) q_values policy_net(states).gather(1, actions.unsqueeze(1)).squeeze(1) with torch.no_grad(): next_q target_net(next_states).max(1)[0] target rewards gamma * next_q * (1 - dones) loss nn.MSELoss()(q_values, target) optimizer.zero_grad() loss.backward() optimizer.step() return loss.item()gamma0.99是折扣因子装箱问题里每一步的奖励差距不大0.99 比较合适。如果发现网络过于短视可以降到 0.95如果训练不稳定先检查奖励尺度是不是太大。3.3 训练流程与参数配置一张表说清每个参数怎么调参数推荐值调整方向影响学习率1e-3训练震荡则降到 5e-4太大不收敛太小收敛慢batch_size64显存够可加到 128太小梯度噪声大回放池容量50000回合长则加大太小样本相关性高ε 衰减步数总步数 15%学得慢则延长太短探索不足目标网络更新间隔200 步训练不稳则减小太频繁失去稳定作用隐藏层宽度256动作空间大则加宽太窄欠拟合训练时每 100 个回合打印一次平均箱数和平均奖励观察曲线。如果平均箱数在前 500 回合没有下降趋势大概率是奖励设计有问题或者状态特征不够。如果奖励在涨但箱数不降说明智能体在刷奖励而不是真正优化装箱效率需要调整奖励权重。4. 避坑与排查DQN 解装箱问题时最容易翻车的 5 个地方4.1 现象训练了几千回合平均箱数和随机策略差不多原因奖励信号太稀疏或者状态特征没有区分度。最常见的情况是状态向量里只有体积信息没有空间分布信息网络无法判断这个箱子虽然剩余体积大但都是碎片空隙放不下新物品。解决在状态里加入最大连续空隙的长宽高或者用网格占用图代替体积特征。另外检查奖励函数确保每步都有非零奖励而不是只在回合结束给信号。4.2 现象Q 值越来越大最后变成 NaN原因奖励尺度太大或者没有做梯度裁剪。装箱问题里如果开新箱的惩罚设成 -100而放置成功的奖励只有 1Q 值会剧烈波动。解决把所有奖励缩放到 [-1, 1] 区间或者在损失反传前加torch.nn.utils.clip_grad_norm_(policy_net.parameters(), 1.0)。另外检查目标网络更新频率太慢会导致 TD 目标漂移。4.3 现象智能体学会了一个永远开新箱的懒策略原因开新箱的惩罚太小或者放置失败的惩罚太大导致智能体觉得塞进已有箱子风险高不如直接开新箱稳。解决增大开新箱的惩罚同时给成功塞入已有箱子的动作额外奖励。我一般会把放入已有箱子且利用率提升超过 5%的动作奖励乘以 1.5 倍。4.4 现象训练时表现很好测试时箱数暴涨原因过拟合到训练集的物品序列。如果训练时物品尺寸分布固定网络会记住特定序列的放置方式换一组物品就失效。解决训练时每回合随机生成物品尺寸和到达顺序确保分布覆盖测试场景。另外可以在回放池里保留不同分布的样本避免网络只见过一种模式。4.5 现象非法动作屏蔽后网络输出全是负无穷原因当前状态下所有动作都非法通常是因为物品尺寸超过了所有箱子的最大空隙。这时候应该允许开新箱而不是屏蔽所有动作。解决在动作屏蔽逻辑里加一个兜底如果所有已有箱子的动作都非法强制把开新箱动作设为合法。开新箱的动作可以单独用一个输出节点表示或者在候选位置里加一个新箱子中心的虚拟位置。5. 进阶技巧用优先经验回放和动作分支把箱数再压 10%5.1 优先经验回放让网络多练难放的物品普通经验回放是均匀采样但装箱问题里有些物品特别难放比如尺寸接近箱子边长的立方体这些样本应该被更频繁地采样。优先经验回放Prioritized Experience Replay用 TD 误差作为优先级误差大的样本采样概率高。class PrioritizedBuffer: def __init__(self, capacity50000, alpha0.6): self.capacity capacity self.alpha alpha self.buffer [] self.priorities np.zeros(capacity, dtypenp.float32) self.pos 0 def push(self, transition, td_error): priority (abs(td_error) 1e-5) ** self.alpha if len(self.buffer) self.capacity: self.buffer.append(transition) else: self.buffer[self.pos] transition self.priorities[self.pos] priority self.pos (self.pos 1) % self.capacity def sample(self, batch_size, beta0.4): probs self.priorities[:len(self.buffer)] / self.priorities[:len(self.buffer)].sum() indices np.random.choice(len(self.buffer), batch_size, pprobs) samples [self.buffer[i] for i in indices] weights (len(self.buffer) * probs[indices]) ** (-beta) weights / weights.max() return samples, indices, weightsalpha0.6控制优先级的强度0 就是均匀采样1 就是完全按 TD 误差。beta0.4是重要性采样权重训练后期可以线性增到 1.0。这个改动通常能让平均箱数再降 5% 到 10%但训练时间会增加 20% 左右。5.2 动作分支把选箱子和选位置拆成两个决策如果你的动作空间是 max_bins × 候选位置数当 max_bins 较大时动作数会很多。一个替代方案是把动作拆成两步先选箱子再选位置。网络输出两个头一个输出每个箱子的 Q 值一个输出每个位置的 Q 值。训练时分别计算两个头的损失推理时先选箱子再选位置。这种结构的优点是动作空间从乘法变成加法网络更容易学。缺点是两个决策的耦合关系可能被忽略比如选箱子 A 是因为位置 3 特别合适拆开后这种联合信息会丢失。我的经验是max_bins 小于 5 时用联合动作空间大于 10 时用分支结构。5.3 验证方法怎么判断你的 DQN 真的学到了东西不要只看训练曲线要用三个指标交叉验证第一和 First Fit 启发式对比DQN 的平均箱数应该至少不差于 First Fit否则说明网络没学到有效策略第二看不同物品分布下的表现如果只在训练分布上好说明过拟合第三看推理时间DQN 的单步推理应该在毫秒级如果超过 10ms说明网络太大或者状态计算太慢在线场景下不可用。我一般会跑 100 个随机测试回合记录平均箱数、标准差、最大箱数然后和 First Fit、Best Fit 对比。如果 DQN 的平均箱数比 First Fit 低 5% 以上这个方案就值得继续优化如果只低 1% 到 2%可能不值得投入工程化。提示测试时记得把 ε 设为 0用纯贪婪策略。如果测试时还保留探索箱数会偏高容易误判模型效果。这套方案我从头跑通大概花了两周其中一周在调奖励函数和状态特征。最大的教训是不要一上来就堆网络深度和回放池容量先把状态和奖励设计对一个 3 层全连接网络就能跑出比启发式好的结果。希望帮到你。本文还有配套的精品资源点击获取