当前位置：首页 > news >正文

【垃圾箱包装问题-Matlab】【使用遗传算法（GA）解决垃圾箱包装问题Matlab代码】

news 2026/5/12 20:20:44

最近在折腾物流仓储的优化问题，偶然遇到个挺有意思的挑战——如何用最少的垃圾箱装下一堆不同体积的货物。这玩意儿专业点叫Bin Packing Problem，传统方法容易陷入局部最优，尝试用遗传算法（GA）搞了波Matlab实现，效果居然还不错。

先来个场景设定：假设我们有10个待装箱货物，体积分别为[8,5,7,3,9,6,2,4,5,1]，单个箱子容量上限是15。目标是把这些货塞进尽量少的箱子里。

种群初始化很关键

一开始得生成靠谱的初始种群。这里采用整数编码，每个基因位代表对应货物所在的箱子编号。比如[1,3,2]表示第一个货在1号箱，第二个在3号箱，第三个在2号箱。

function pop = initPop(popSize, numItems) maxBins = numItems; % 最坏情况每个物品单独装箱 pop = randi([1, maxBins], popSize, numItems); end

这个初始化有个坑——随机生成的编号可能远超实际需要箱子数，后面适应度函数得处理这个问题。

适应度函数暗藏玄机

【垃圾箱包装问题-Matlab】【使用遗传算法（GA）解决垃圾箱包装问题Matlab代码】

评估函数需要同时考虑箱子数量和空间利用率。这里用了加权公式：fitness = 1000/(usedBins + 0.1*wastedSpace)，既优先减少箱子数量，又照顾空间利用率。

function [fitness, binsUsed] = calcFitness(ind, items, binCapacity) uniqueBins = unique(ind); totalWaste = 0; for b = 1:length(uniqueBins) binItems = items(ind == uniqueBins(b)); if sum(binItems) > binCapacity fitness = 0; % 违反容量约束直接判死刑 return end totalWaste = totalWaste + (binCapacity - sum(binItems)); end binsUsed = length(uniqueBins); fitness = 1000/(binsUsed + 0.1*totalWaste); end

这里有个骚操作：当出现超箱情况时直接返回0适应度，相当于给违反约束的方案发红牌。

交叉变异要带点智能

普通GA的交叉操作在这里容易生成无效解，所以搞了个改进版两点交叉。随机选两个交叉点，但保证子代中箱子编号连续。

function child = crossover(parent1, parent2) points = sort(randperm(length(parent1),2)); child = parent1; child(points(1):points(2)) = parent2(points(1):points(2)); % 处理编号不连续问题 uniqueBins = unique(child); mapping = containers.Map(uniqueBins, 1:length(uniqueBins)); child = cell2mat(values(mapping, num2cell(child))); end

用Map容器做箱子编号重映射，解决了交叉可能导致的编号断层问题，相当于自动压缩了箱子数量。

实战效果验证

参数设置：种群40，迭代100，交叉率0.8，变异率0.2。跑三次基本都能收敛到最优解4个箱子：