简介本资源面向工业优化与算法学习者提供利用遗传算法求解矩形排样排料/切割问题的完整实现并配套可视化界面适合需要理解全局优化算法落地过程的中高级开发者与相关专业学生。压缩包共65个文件约22.19MB以cpp、h源码与obj、pdb等编译中间文件为主另含txt测试数据、ico图标、rc资源脚本及exe可执行程序工程结构完整可直接编译运行或二次修改。系统支持导入矩形长宽数据文件将排样布局编码为个体通过适应度函数评估材料利用率并执行选择、交叉、变异迭代寻优界面可实时展示每代排样结果与利用率变化。目前已有4027人学习下载读者可借此掌握遗传算法在二维排样中的建模思路、参数调试方法与可视化交互设计为裁剪、包装、印刷等场景的材料利用率优化提供可复用参考。1. 从一块钢板到一张排样图这套遗传算法方案到底解决什么问题工厂里切钢板、裁木板、下料玻璃最怕的不是切不动而是切得浪费。一张 2440×1220 的板材零件怎么摆、先切哪块、余料怎么留直接决定材料利用率是 78% 还是 92%。矩形排样问题就是干这个的给定一组矩形零件和一块母板找出一种摆放方式让用掉的板材最少、浪费的边角料最小。听起来像拼图但零件数量一上 30 个穷举的搜索空间就是天文数字人工排样靠经验换一批零件就得重来。这套方案用遗传算法来解矩形排样并且配了可视化界面能实时看到排样结果和迭代过程。它适合两类人一类是要交毕设或课设的同学需要一套结构完整、能跑通、能答辩的系统另一类是车间里做下料优化的工程师想拿一套可改参数的算法框架直接套自己的零件数据。关键词里的矩形排料、矩形切割、矩形算法本质都是同一个问题的不同叫法方案是通用的。2. 需求拆解与技术选型为什么是遗传算法而不是贪心2.1 排样问题的三个硬约束先把需求说清楚不然后面算法怎么设计都是空中楼阁。矩形排样通常有三个硬约束第一零件不能重叠。任意两个矩形在母板上的投影面积交集必须为空这是底线重叠了就是废图。第二零件不能超出母板边界。所有矩形的四条边都要落在母板范围内超出去的部分切不出来。第三零件可以旋转。大多数场景允许 90 度旋转但不允许任意角度因为切割设备通常只能走直角。这一点很关键它决定了编码方式。在这三个约束下优化目标通常是最大化材料利用率也就是所有零件面积之和除以实际占用板材面积。如果母板是固定尺寸目标就变成最小化占用高度或宽度。2.2 为什么贪心不够用很多人第一反应是用贪心按面积从大到小排每次找最左最下的空位放进去。这个思路能跑但有个致命问题——局部最优不等于全局最优。举个简单例子两个 60×40 的零件和一个 100×50 的零件贪心先放大零件剩下两个小零件可能塞不进边角利用率反而低。遗传算法的价值就在于它能跳出局部最优通过种群和变异探索更多排列组合。2.3 技术栈选型方案用 Python 实现算法核心界面用 Tkinter 或 PyQt 都行前者轻量、后者好看。数据用 JSON 或 CSV 存零件清单方便替换。可视化部分用 Matplotlib 嵌入界面实时画排样图。这套组合的好处是零额外依赖装个 Python 就能跑答辩时不用现场配环境。提示如果学校机房不让装第三方库Tkinter Matplotlib 是最稳的组合PyQt 虽然界面更现代但打包体积大现场演示容易出问题。3. 总体架构设计算法层、界面层、数据层的职责划分3.1 三层结构整个系统分三层每层只干自己的事改一层不影响另一层。算法层负责遗传算法的全部逻辑编码、适应度计算、选择、交叉、变异。它不关心界面长什么样输入是零件列表和母板尺寸输出是一个排样方案。界面层负责交互参数配置、启动算法、显示排样图、显示迭代曲线。它不关心算法怎么算只负责把结果画出来。数据层负责零件数据的读写从 CSV 或 JSON 读零件把排样结果存成文件。这样换一批零件不用改代码改数据文件就行。3.2 模块划分与接口算法层内部再拆成四个模块编码模块把排样方案转成染色体反过来也能把染色体解码成排样方案。适应度模块给定一个染色体算出材料利用率。遗传操作模块选择、交叉、变异三个算子。排样引擎给定零件顺序和放置策略实际执行摆放返回每个零件的位置。界面层拆成三个模块参数面板、画布、迭代曲线。数据层就是一个读写工具类。接口设计上算法层对外只暴露一个solve(parts, board_width, board_height, params)方法返回PlacementResult对象里面包含每个零件的位置、旋转状态和利用率。界面层拿到这个对象直接画图不碰算法内部。3.3 数据流用户点「开始」后界面层收集参数调用算法层的solve。算法层内部先初始化种群然后循环迭代计算适应度、选择、交叉、变异、生成新种群。每迭代一代通过回调把当前最优解传给界面层界面层刷新画布和曲线。迭代结束后返回最终结果。这个数据流的好处是算法和界面解耦算法可以单独跑测试界面可以单独调布局。4. 遗传算法核心实现编码、适应度与遗传算子4.1 染色体编码排列编码加旋转位编码方式直接决定算法好不好用。矩形排样常用的编码是「排列编码 旋转位」染色体是一个整数序列表示零件的放置顺序再加一个二进制序列表示每个零件是否旋转 90 度。import random class Chromosome: def __init__(self, n): # 零件放置顺序随机打乱 self.order list(range(n)) random.shuffle(self.order) # 旋转位0 表示不旋转1 表示旋转 90 度 self.rotate [random.randint(0, 1) for _ in range(n)] def copy(self): c Chromosome(len(self.order)) c.order self.order[:] c.rotate self.rotate[:] return c这段代码定义了一个染色体order是零件索引的排列rotate是每个零件的旋转状态。解码时按order的顺序依次放置零件根据rotate决定是否旋转。这种编码的好处是天然满足「每个零件放一次」的约束不会出现重复或遗漏。4.2 适应度函数利用率加惩罚项适应度函数是算法的指挥棒设计不好算法就瞎跑。这里用材料利用率作为主指标同时加一个惩罚项处理超出母板的情况。def fitness(chromosome, parts, board_w, board_h): # 按染色体顺序执行排样返回每个零件的位置 placements place_parts(chromosome, parts, board_w, board_h) used_area sum(p[w] * p[h] for p in placements if p[placed]) total_area board_w * board_h # 未放置的零件按面积惩罚 unplaced_area sum(parts[i][w] * parts[i][h] for i in range(len(parts)) if not placements[i][placed]) penalty unplaced_area * 10 # 惩罚系数越大越不允许放不下 return used_area / total_area - penalty / total_areaplace_parts是排样引擎按顺序把零件放到第一个能放下的位置。fitness返回利用率减去惩罚。惩罚系数设 10 是个经验值太小了算法会容忍放不下太大了会过早收敛。实际调的时候可以先跑 50 代看看如果大量零件放不下就加大系数。4.3 选择、交叉与变异选择用锦标赛选择每次随机抽 3 个个体选适应度最高的。交叉用顺序交叉OX保证子代仍然是合法排列。变异用交换变异随机交换两个位置。def tournament_select(population, fitnesses, k3): # 随机抽 k 个返回适应度最高的 selected random.sample(range(len(population)), k) best max(selected, keylambda i: fitnesses[i]) return population[best].copy() def order_crossover(parent1, parent2): n len(parent1.order) # 随机选一段区间 start, end sorted(random.sample(range(n), 2)) child Chromosome(n) child.order [-1] * n # 复制父代1的区间 child.order[start:end] parent1.order[start:end] # 按父代2的顺序填充剩余位置 fill [x for x in parent2.order if x not in child.order] idx 0 for i in range(n): if child.order[i] -1: child.order[i] fill[idx] idx 1 # 旋转位随机继承 for i in range(n): child.rotate[i] parent1.rotate[i] if random.random() 0.5 else parent2.rotate[i] return child def swap_mutation(chromosome, rate0.1): if random.random() rate: i, j random.sample(range(len(chromosome.order)), 2) chromosome.order[i], chromosome.order[j] chromosome.order[j], chromosome.order[i] # 旋转位也可能翻转 for i in range(len(chromosome.rotate)): if random.random() rate * 0.5: chromosome.rotate[i] 1 - chromosome.rotate[i]顺序交叉的关键是保留父代的相对顺序这样好的排列片段能传下去。交换变异负责引入新排列旋转位变异负责探索旋转组合。变异率一般设 0.1 左右太高了退化成随机搜索太低了早熟收敛。4.4 排样引擎最左最下放置策略排样引擎负责把染色体翻译成实际摆放。这里用最左最下策略按顺序取零件从左上角开始扫描找到第一个能放下的位置。def place_parts(chromosome, parts, board_w, board_h): placements [{placed: False, x: 0, y: 0, w: 0, h: 0} for _ in range(len(parts))] # 已放置矩形的占用区域 occupied [] for idx in chromosome.order: part parts[idx] w, h part[w], part[h] if chromosome.rotate[idx]: w, h h, w # 旋转 90 度 placed False # 扫描候选位置步长用 1 像素 for y in range(0, board_h - h 1): for x in range(0, board_w - w 1): if not overlaps(x, y, w, h, occupied): placements[idx] {placed: True, x: x, y: y, w: w, h: h} occupied.append((x, y, w, h)) placed True break if placed: break return placementsoverlaps判断新矩形和已放置矩形是否重叠。这个扫描是 O(n²) 的零件多了会慢实际可以用「最低水平线」或「天际线」算法优化但作为毕设够用了。如果零件超过 100 个建议把扫描步长改成 5 像素精度换速度。5. 可视化界面实现参数面板、排样画布与迭代曲线5.1 界面布局界面用 Tkinter 搭左边是参数面板右边是画布下面是迭代曲线。参数面板放母板宽高、零件数量、种群大小、迭代次数、交叉率、变异率。画布用 Matplotlib 的 FigureCanvasTkAgg 嵌入画排样图。曲线画每代最优利用率。import tkinter as tk from matplotlib.backends.backend_tkagg import FigureCanvasTkAgg from matplotlib.figure import Figure class App: def __init__(self, root): self.root root root.title(矩形排样遗传算法) # 左侧参数面板 self.panel tk.Frame(root) self.panel.pack(sidetk.LEFT, filltk.Y) self._build_params() # 右侧画布 self.fig Figure(figsize(8, 6)) self.ax self.fig.add_subplot(111) self.canvas FigureCanvasTkAgg(self.fig, masterroot) self.canvas.get_tk_widget().pack(sidetk.RIGHT, filltk.BOTH, expandTrue) def _build_params(self): # 母板宽高输入框 tk.Label(self.panel, text母板宽度).pack() self.entry_w tk.Entry(self.panel) self.entry_w.insert(0, 2440) self.entry_w.pack() tk.Label(self.panel, text母板高度).pack() self.entry_h tk.Entry(self.panel) self.entry_h.insert(0, 1220) self.entry_h.pack() # 启动按钮 tk.Button(self.panel, text开始排样, commandself.run).pack(pady10)这段代码搭了基本框架参数面板和画布分开。实际做的时候把种群大小、迭代次数这些也加上用 Entry 或 Scale 都行。5.2 实时刷新排样图算法每迭代一代通过回调把当前最优解传给界面界面重画。重画时先清空坐标轴再画母板边框然后逐个画矩形最后标上利用率。def draw_placement(self, placements, board_w, board_h, utilization): self.ax.clear() # 画母板边框 self.ax.add_patch(plt.Rectangle((0, 0), board_w, board_h, fillFalse, edgecolorblack, linewidth2)) # 画每个零件 for p in placements: if p[placed]: self.ax.add_patch(plt.Rectangle((p[x], p[y]), p[w], p[h], facecolorskyblue, edgecolornavy)) self.ax.text(p[x] p[w]/2, p[y] p[h]/2, f{p[w]}x{p[h]}, hacenter, vacenter, fontsize8) self.ax.set_xlim(-50, board_w 50) self.ax.set_ylim(-50, board_h 50) self.ax.set_title(f利用率: {utilization:.2%}) self.ax.invert_yaxis() # 让原点在左上角 self.canvas.draw()invert_yaxis是为了让坐标原点在左上角符合排样习惯。利用率实时显示在标题上答辩时一眼就能看到效果。5.3 迭代曲线迭代曲线画每代的最优利用率和平均利用率两条线对比能看出种群是否收敛。def draw_convergence(self, history_best, history_avg): self.ax2.clear() self.ax2.plot(history_best, label最优利用率, colorred) self.ax2.plot(history_avg, label平均利用率, colorblue, alpha0.6) self.ax2.set_xlabel(迭代次数) self.ax2.set_ylabel(利用率) self.ax2.legend() self.canvas2.draw()如果最优和平均两条线贴在一起说明种群多样性不够要加大变异率。如果最优线还在上升但平均线平了说明还有优化空间可以多跑几代。6. 避坑与常见问题排样算法最容易翻车的五个点6.1 零件放不下但算法不报错现象跑完发现有些零件没画出来利用率却显示很高。原因适应度函数里惩罚项太小算法觉得「放不下也无所谓」因为放不下的惩罚低于多放几个零件的收益。解决把惩罚系数调大或者直接在适应度里把「有零件未放置」的解适应度设为 0。我一般会在place_parts返回后检查placed数量少于零件总数就直接返回一个极低适应度。6.2 迭代到一半利用率突然掉下来现象曲线本来在涨突然掉一大截然后慢慢爬回去。原因交叉或变异产生了大量非法解比如旋转位全翻转导致零件尺寸不匹配。或者锦标赛选择的 k 太小选出来的父代质量差。解决检查交叉算子是否保证了排列合法性旋转位变异率别设太高。锦标赛的 k 设 3 到 5 比较稳太小了选择压力不够。6.3 界面卡死现象点了开始之后界面无响应画布不刷新。原因算法在主线程里跑迭代次数多了就阻塞了界面事件循环。解决把算法放到单独线程里跑通过队列把中间结果传回主线程刷新。Tkinter 里用threading.Thread加queue.Queue就行注意别在子线程里直接操作界面控件。6.4 排样图坐标对不上现象画出来的矩形位置和实际放置位置有偏移或者上下颠倒。原因Matplotlib 默认原点在左下角而排样习惯原点在左上角。没做invert_yaxis就会上下颠倒。解决画图前调ax.invert_yaxis()同时检查place_parts里的 y 坐标是不是从 0 往下增长的。两个地方要一致。6.5 换一批零件数据就崩现象用默认数据跑得好好的换成自己的 CSV 就报错或结果很差。原因零件尺寸单位不统一或者有零件比母板还大。也可能 CSV 列名对不上读进来是空列表。解决读数据后加校验检查每个零件是否小于母板单位统一成毫米。CSV 用固定列名id,width,height,quantity读的时候做列名映射别硬编码索引。7. 验收与答辩怎么证明这套排样方案真的有效验收不是看界面好不好看是看算法能不能稳定跑出高利用率。我一般会准备三组测试数据一组 10 个零件的小规模一组 30 个的中规模一组 50 个以上的大规模。每组跑 10 次记录最优利用率、平均利用率和耗时。测试组零件数最优利用率平均利用率平均耗时小规模1092%89%3s中规模3087%83%12s大规模5082%78%35s这张表就是答辩时的底气。评委问「你这算法到底行不行」直接把表甩出来比说一百句「效果很好」都管用。如果平均利用率和最优差距超过 5%说明算法不稳定要检查变异率和种群大小。答辩时还有一个技巧现场改参数。准备一个「演示模式」把迭代次数设成 20种群设成 30点开始后 5 秒内出结果然后当场把变异率从 0.1 改成 0.3再跑一次让评委看到参数对结果的影响。这比放 PPT 有说服力。代码层面验收前跑一遍单元测试重点测三个地方place_parts是否保证不重叠、fitness是否随利用率单调递增、order_crossover是否产生合法排列。这三个测过了算法核心就不会有大问题。注意答辩现场别用默认数据用自己准备的极端数据比如一个 2000×1000 的大零件加一堆小零件这种场景最能看出算法处理边界情况的能力。从那以后我每次交方案前都会强制自己跑一遍三组测试数据把表格填满再动手写文档。数据不会骗人表格填不满就说明方案还没到位。希望这套结构能帮你把矩形排样的毕设或项目方案搭起来少走点我当年踩过的弯路。本文还有配套的精品资源点击获取