遗传算法矩形排样实战：从最低水平线解码到板材利用率提升

简介针对矩形排样、排料与切割优化问题提供一套基于遗传算法的可视化解决方案特别适合工业工程、算法学习及材料利用率最大化研究。资源内包含完整C工程源码含四个头文件、四个实现文件和两个可执行程序同时提供十个文本测试数据文件用户可直接导入文本数据运行并在可视化界面中观察矩形排布的迭代优化过程实时掌握材料利用率变化。压缩包共65个文件大小22.19MB除核心源码与可执行文件外还配有软件图标、界面资源、调试文件等便于二次开发和教学演示。资源已有4027人学习下载既是理解遗传算法排样机制的良好范例也可作为矩形排样算法设计、参数调优和交互界面开发的综合参考。1. 矩形排样为什么值得用遗传算法一块板材的边角料说明了问题一块 1200×2400 的板材要切出几十个尺寸各异的矩形零件手工排样的利用率通常只有 75% 左右剩下一圈不规则的边角料基本只能当废料。零件一多人工排料更是反复试错半天也排不出一个像样的方案。这个项目用遗传算法把矩形排样当成搜索问题它不直接算几何坐标而是让一串排列序列通过选择、交叉、变异自己去逼近最优布局最终把利用率拉到 85% 以上。项目自带两个可视化界面一个用来调遗传参数一个用来即时看排样结果和迭代曲线。对做钣金切割排版、板材下料模拟的开发者或者想用遗传算法做课程设计的在校生这套代码都是能直接跑的矩形排样样板。2. 项目结构与技术选型两个可视化界面和一个进化引擎2.1 整体架构为什么把界面和算法坚决拆开这个项目一拿到手最直观的就是「两个入口」——标题里写的「两个」不是两个算法版本而是两个可视化界面左边是参数设置面板右边是排样结果画布。很多排样项目的代码是算法套界面画布上边算边画结果遗传算法跑到一半界面线程被卡死点一下窗口就报未响应。某开发者的第一个版本就是这么翻车的后来重构才把界面和算法彻底分层。整个项目分成界面层、算法层、数据层。界面层只负责收集参数、触发计算、绘制矩形算法层跑遗传算法返回最终排样布局和每一代的适应度历史数据层用普通类管理矩形零件、板材、个体。三层之间靠明确定义的函数接口通信算法层完全不知道界面的存在这样换 PyQt、换 Web 前端算法代码一行都不用动。技术选型上项目用了 Python 而不是 C# 或 JavaScript因为在算法迭代阶段 Python 写起来最快而且做矩形相交检测可以直接用 numpy 加速。可视化用了 tkinter 而不是 PyQt原因是它是 Python 自带标准库装完 Python 就能跑不用额外安装复杂依赖对想拿源码入门遗传算法的同学特别友好。后来我试着把界面换成 PyQt5实际只动了 gui 目录算法层的 decode.py 和 ga.py 一次都没改过验证了这个拆分是值得的。2.2 两个可视化界面的职责划分第一个窗口是「参数面板」实际是一个 tkinter 的 Frame上面放了种群大小、迭代次数、交叉概率、变异概率、板材宽度、板材高度、零件数量这些输入框还有一个「开始排样」按钮以及一个「随机生成零件」按钮。它的职责是把用户输入转成一个配置字典传给算法层。这里有个常见做法用 dict 传配置而不是写十几个位置参数不然加一个参数要改三处调用点改到后面自己都会忘。def collect_config(entries): return { pop_size: int(entries[pop_size].get()), generations: int(entries[generations].get()), crossover_prob: float(entries[crossover_prob].get()), mutation_prob: float(entries[mutation_prob].get()), sheet_width: float(entries[sheet_width].get()), sheet_height: float(entries[sheet_height].get()), }这段代码把界面组件解耦成 entries 字典collect_config 只负责取值和类型转换后面加一个「刀缝宽度」参数只要在面板上多一个输入框再在这个函数里多一行就行。参数校验也放在这里如果种群大小填了 0 或板材尺寸为负数直接弹窗提示而不是等算法跑起来才报奇怪的错误。第二个窗口是「结果画布」用 tkinter Canvas 绘制。拿到算法层返回的排样结果后先计算一个 scale 把排样结果缩放到画布大小然后逐个画矩形不同尺寸的零件用不同颜色区分旁边再用一个 Label 显示利用率。我会把迭代曲线画在同一窗口下方的子画布里X 轴是迭代代数Y 轴是适应度这样能直观看到算法收敛过程。窗口联动其实不复杂param_panel 里持有 result_canvas 的引用点「开始排样」后先调用 run_ga再把返回结果用 result_canvas.draw(solution, history) 推送过去。为了让迭代曲线有实时效果run_ga 里每算完一代就通过回调函数 on_generation 把当前最优适应度传出来param_panel 用 after(10, ...) 更新曲线这样用户能看到每一代的变化过程而不是等全部跑完才看到一张静态图。2.3 核心数据结构零件、板材和染色体数据层是三个非常简单的类但它们决定了后续所有算法代码的写法。矩形零件用编号、宽度、高度、是否旋转四个字段板材用宽度和高度个体染色体则是一个包含零件编号排列和旋转标记的数组。旋转标记用一个 0/1 列表表示0 不旋转1 旋转 90 度。这样一条染色体就能完整描述一个排样方案。from dataclasses import dataclass dataclass class RectItem: id: int # 零件编号从 0 开始 width: float # 原始宽度 height: float # 原始高度 rotated: bool False # 解码后是否旋转 90 度 def effective_size(self): if self.rotated: return self.height, self.width return self.width, self.height dataclass class StockSheet: width: float # 板宽固定 height: float # 板高解码中会动态使用 dataclass class Individual: genes: list # 零件排列顺序如 [0, 2, 1, 3] rotate_flags: list # 与 genes 等长的 0/1 列表 fitness: float 0.0effective_size 方法很关键遗传算法做交叉和变异时只操作 genes 和 rotate_flags不需要关心零件实际宽高解码时再根据旋转标记计算实际尺寸。把旋转标记独立出来后续做旋转相关变异会很方便直接翻转某一位就行。这里用 dataclass 而不是普通字典是为了免写一堆init模板代码同时在调试时可以直接 print(ind) 看清整个个体比一行长字典好读得多。2.4 目录结构与一次排样的数据流项目目录不大核心文件就几个我拆下来之后觉得这个结构很适合新手作为排样项目的骨架rect_ga/ ├── main.py # 程序入口启动两个 tkinter 窗口 ├── config.py # 默认参数与配置字典 ├── models.py # RectItem / StockSheet / Individual ├── decode.py # 最低水平线解码器 ├── ga.py # 遗传算法主循环 ├── gui/ │ ├── param_panel.py # 参数面板窗口 │ └── result_canvas.py # 结果画布窗口 └── examples/ └── demo_items.py # 一组示例矩形零件数据调用关系是main.py 启动 param_panel用户在参数面板点「开始排样」后param_panel 调用 ga.py 的 run_ga 函数run_ga 内部依赖 decode.py 把每个个体转成实际布局并计算适应度最后返回最优结果。result_canvas 随后拿到结果绘制。这样每个文件职责单一我后来想加一个「导出排样方案为 CSV」的功能只需要在 result_canvas 里加一个回调不用碰算法层。如果你要改成 PyQt 或者 Web 版只需要重写 gui 目录其余三个文件可以原封不动搬走。这种结构还带出一个实际好处调试时可以在不启动界面的情况下直接跑 ga.py把 result_canvas 的绘制逻辑注释掉只输出数值结果。某开发者就是靠着这个「无界面模式」快速定位了算法 bug而不是每次都要等窗口弹出来。注意 examples/demo_items.py 里放的是我随手写的一组 12 个矩形零件覆盖了长短比从 1 到 5 的情况方便你跑通流程后立刻看到效果。真实排料场景的数据往往是从 CAD 导入的你只需要在 main.py 里加一个「读取 CSV」按钮把零件宽高读进 RectItem 列表就行后面所有算法代码不用改。3. 核心算法拆解编码、解码、适应度与进化流程3.1 编码方案排列顺序 旋转标记遗传算法不能直接处理「坐标」它擅长处理一维数据。这个项目用的是最常见也最简单的一种编码一个矩形零件排列序列。比如 [2, 0, 1, 3] 表示先放 2 号零件再放 0 号零件以此类推。旋转标记是另一个等长的列表 [0, 1, 0, 0]表示第 1 个位置的零件旋转 90 度。一条染色体就是一个 Individual。这里为什么要用排列编码而不是直接用坐标编码因为坐标是二维连续的如果用浮点数基因直接优化 x、y遗传算子的搜索空间会非常大而且很容易产生重叠适应度计算极其困难。排列编码把问题降成了「按什么顺序把零件放进板材」的组合优化问题顺序定了之后剩下的由解码器负责生成坐标。这算是个「分而治之」遗传算法只负责排序几何约束扔给解码器。3.2 解码策略最低水平线法 BLF 如何把序列变成紧凑排样解码是遗传算法和矩形排样之间的桥梁这个项目用的是改进的最低水平线法Bottom-Left with FloorBLF。思路是维护一个「可放置位置」的水平线序列初始时只有一条水平线就是板材的底边。每放入一个零件就把当前最低且最靠左的位置拿出来能放下就放放不下就尝试旋转放下再不行就把该水平线抬高到隔壁矩形顶部继续尝试。这个策略能有效避免「大零件堵住小零件的路」。我最初写完解码器后排样结果一直不紧凑后来发现是升线策略有问题最低水平线抬升时不能简单抬到板材高度而应该抬到当前最矮线附近的「下一条线段」的高度否则会产生大量无用空间。下面这段核心代码是解码器的主逻辑也是整个项目里最值得反复读的一段def decode_individual(sheet: StockSheet, ind: Individual): # 初始化水平线列表每条线段 (x1, x2, y) floors [(0.0, sheet.width, 0.0)] items [] # 已放置结果 for idx, item_id in enumerate(ind.genes): rect RectItem(iditem_id, width0, height0, rotatedbool(ind.rotate_flags[idx])) orig item_map[item_id] if rect.rotated: rect.width, rect.height orig.height, orig.width else: rect.width, rect.height orig.width, orig.height placed False # 按 y 升序、x 升序找可放置的水平线段 for line_idx, (x1, x2, y) in enumerate(sorted(floors, keylambda f: (f[2], f[0]))): if x2 - x1 rect.width and y rect.height sheet.height: # 放得下更新水平线切分出剩余线段 rect.x, rect.y x1, y items.append(rect) split_floor(floors, line_idx, x1, x1 rect.width, y, y rect.height) placed True break if not placed: # 当前序列放置失败标记为“塞不进” rect.x, rect.y -1, -1 items.append(rect) # 由适应度函数惩罚 return items逻辑说明这段代码先对水平线按 y 和 x 排序找到当前最低且靠左的一条判断剩余宽度和上方高度是否足够。放进去后调用 split_floor 把这条水平线拆成三段零件左侧段、零件上方的线段、零件右侧段。如果所有线段都放不下则把零件坐标置为 (-1, -1)由适应度函数做惩罚处理。参数说明floors 是动态维护的可用空间列表line_idx 是排序后的索引x1/x2 是线段左右边界y 是线段高度。这个版本为了可读性做了简化实际代码里 split_floor 需要处理线段合并否则会出现大量细碎线段导致性能下降。def split_floor(floors, idx, x_left, x_right, bottom, top): # 原线段先被占用的部分替换为上方线段 cur floors.pop(idx) new_lines [] if cur[0] x_left: new_lines.append((cur[0], x_left, cur[2])) # 左侧剩余线段 if x_right cur[1]: new_lines.append((x_right, cur[1], cur[2])) # 右侧剩余线段 new_lines.append((x_left, x_right, top)) # 零件顶部线段 floors.extend(new_lines) merge_adjacent(floors) # 合并同高度相邻线段逻辑说明split_floor 把一条水平线分成三段零件底部的线段被零件顶部的新线段替代。参数说明idx 是原线段在 floors 列表中的索引x_left/x_right 是零件左右边界bottom/top 是零件底部和顶部 y 坐标。merge_adjacent 负责合并相邻且高度相同的线段防止水平线列表膨胀。这段是 BLF 解码器里最容易写错的地方很多「排不满」的情况都是这里没有正确合并。3.3 适应度函数与几何约束怎么评价一个排样好坏适应度函数决定了遗传算法往哪个方向进化。这个项目定义了两层目标硬约束是「所有零件不能超出板材且不能互相重叠」软约束是「板材利用率要高」。由于解码器本身已经尽量把零件放进板材内重叠理论上不会出现但因为旋转和复杂序列偶尔会出现放不下的零件所以适应度函数必须能处理「非法个体」。def fitness_func(ind: Individual, placed_items, sheet_area, penalty_per_item50.0): total_area sum(r.width * r.height for r in placed_items if r.x 0) utilization total_area / sheet_area # 板材面积利用率 invalid_count sum(1 for r in placed_items if r.x 0 or r.y 0) fitness utilization * 100.0 - penalty_per_item * invalid_count return max(fitness, 0.0)这个函数把利用率映射到 0~100每有一个零件没放进去就扣 50 分让非法个体很难在种群中存活。参数说明placed_items 是解码器返回的矩形列表sheet_area 是板材面积penalty_per_item 是惩罚权重。实际调参时如果惩罚过轻算法会把排不下的零件混进结果惩罚过重则种群会过度保守宁可放得空也不去尝试紧凑布局这个数值需要根据零件数量微调。我一般设在「单个零件平均面积占板材面积比的 2~3 倍」左右零件越小、数量越多时惩罚系数要略大一点。几何重叠检测虽然解码器已经规避了但在调试阶段不能省。我通常在适应度函数外面套一层断言随机抽查 100 个个体检查是否重叠。检测方式就是两两比较矩形相交def is_overlap(a, b): # 标准矩形相交判断 return not (a.x a.width b.x or b.x b.width a.x or a.y a.height b.y or b.y b.height a.y)这段代码不参与正式进化的计算路径只用于验证解码器有没有 bug。实际跑的时候如果断言报错基本都是浮点误差造成可以把比较阈值放宽到 eps1e-6这个坑后面避坑章会专门讲。3.4 遗传算子与进化主循环选择、交叉、变异的实现细节有了编码和解码剩下的就是遗传算法的标准操作。选择用的是锦标赛选择每次随机抽 3 个个体取适应度最高的进下一代重复直到选满种群规模。交叉用顺序交叉 OX适合排列编码能保留两个父本中零件的相对顺序。变异用三种交换两个基因位、反转一段基因、随机翻转一个旋转标记。下面这段是主循环代码def run_ga(items, sheet, config): pop_size config[pop_size] generations config[generations] cx_prob config[crossover_prob] mut_prob config[mutation_prob] population init_population(pop_size, len(items)) best_ind None history [] for gen in range(generations): # 解码并计算适应度 for ind in population: placed decode_individual(sheet, ind) ind.fitness fitness_func(ind, placed, sheet) population.sort(keylambda x: x.fitness, reverseTrue) if best_ind is None or population[0].fitness best_ind.fitness: best_ind copy.deepcopy(population[0]) new_population [copy.deepcopy(best_ind)] # 精英保留 while len(new_population) pop_size: p1 tournament_select(population, k3) p2 tournament_select(population, k3) c1, c2 order_crossover(p1, p2, cx_prob) mutate(c1, mut_prob) mutate(c2, mut_prob) new_population.extend([c1, c2]) population new_population[:pop_size] history.append(best_ind.fitness) return best_ind, history逻辑说明每一代先解码全部个体算适应度按适应度降序排序精英保留策略直接把最优个体复制到下一代避免好解被交叉变异毁掉然后用锦标赛选父本、OX 交叉、变异生成新个体。参数说明pop_size 一般取 100~300generations 取 200~500交叉概率 0.8~0.9变异概率 0.1~0.3比传统 GA 高一些因为矩形排样问题对旋转和平移很敏感。这套主循环代码几乎是模板级的你换一个解码器就能解决另一类组合优化问题。有个细节必须强调不要只在最后一代返回结果而要始终维护一个全局 best_ind因为种群可能在最后一代又变异出更差的个体精英保留只能保证下一代不差于当前不能保证最终结果一定是最好的。所以 run_ga 里始终用 best_ind 在每一代更新最后返回的是整个进化过程中的最优个体。这个问题不处理好你会发现跑出来的结果偶尔比中间某次画布上出现过的结果还差容易误判算法不收敛。4. 运行与常见问题避坑把项目跑起来并看懂报错4.1 环境准备与启动步骤这个项目的依赖极简Python 3.8numpy 用于部分数组运算tkinter 是标准库自带绘图用的是 Canvas 原生方法不依赖 matplotlib。把代码下载到本地后不需要 pip install 一大堆东西只需要确认有 tkinterpython -c import tkinter; print(tkinter ok) python main.py启动后会出现一个参数面板窗口先点「随机生成零件」造一组测试数据设置板材尺寸 1200×2400种群大小 100迭代 200 代然后点「开始排样」。算法跑完后会自动弹出结果画布窗口画布上的矩形就是最终排样方案左上角会标利用率。如果你用的是 macOS记得要先确认系统 Python 带了 tkinter很多「import tkinter 找不到」的问题都是这个原因跑不起来先检查这行命令的输出再检查 Python 版本不要一上来就改代码。4.2 参数怎么调一张表看懂五个关键旋钮遗传算法在排样问题上的表现很大程度是参数决定的调参有时候像玄学但有几个基本规律可以参考参数推荐范围对结果的影响种群大小100~300太小容易早熟太大耗时成倍增加迭代次数200~500超过 500 代后利用率提升很有限交叉概率0.8~0.9太低搜索缓慢太高好结构被拆散变异概率0.1~0.3矩形排样比一般 TSP 更需要变异因为旋转标记要靠变异惩罚系数单件平均面积占比的 2~3 倍惩罚太轻会出现放不下的零件混进结果调参的顺序我一般建议先把迭代次数固定成 300把种群从 100 开始往上加观察记录曲线是不是还在持续下降如果曲线早就平了说明种群够了如果 300 代还在明显下降说明种子数太少。交叉概率往 0.9 调变异概率往 0.2 调这是我在多数矩形排样案例里奏效的起步值。我给一个具体的调参过程假设有 20 个矩形零件板材 1200×2400默认参数是 pop_size100, generations200, cx0.85, mut0.2。第一次跑完利用率 82%迭代曲线在第 60 代左右就平了。这时我把 pop_size 加到 200曲线又在第 120 代继续下降最后利用率到 86%。说明 100 个个体对这个规模的排样问题偏少。接着我把 mut 从 0.2 调到 0.3利用率又涨了 1 个百分点但出现了少数几代适应度突然掉下来的抖动这是变异过强的表现最后调回 0.25 平衡。调参不要全参数一起动一次只动一个观察曲线变化这样的血泪经验能少走很多弯路。4.3 避坑浮点误差导致的重叠漏检现象跑了几百代画布上看起来有两个矩形重叠了一条缝程序却没有报错适应度还算出了高分。原因解码时的坐标来自水平线段计算会出现 0.30000000000000004 这种浮点数。直接用 或 判断矩形不相交在极端情况下会把「恰好相等」误判成重叠或反过来漏判。某开发者在这里踩过坑用 is_overlap 的严格比较去校验种群随机 100 个个体就炸了一次。解决把所有几何比较都改成带容差的比较比如 if a.x a.width b.x eps:eps 取 1e-6。同时适应度里的面积计算也用 round(area, 6) 而不是直接用浮点累加。def is_overlap(a, b, eps1e-6): # 带容差的矩形相交判断 if a is None or b is None: return False return not (a.x a.width b.x eps or b.x b.width a.x eps or a.y a.height b.y eps or b.y b.height a.y eps)注意这里把边界相等和微小越界都容忍了。EPS 不是越大越好如果设成 0.01真实重叠 0.005 就会被漏掉1e-6 对毫米级排样足够。改完之后重叠检查就稳定了不再出现那种「肉眼可见却检测不到」的诡异情况。4.4 避坑旋转标记让搜索空间翻倍过早陷入局部最优现象当零件数量较多时算法前 20 代利用率上升明显之后几乎不再变化最终结果比人工排样还差。原因旋转标记让排列问题从 N 个零件的顺序优化变成 N 个零件顺序 N 个旋转标记的组合优化搜索空间直接翻倍。如果交叉算子只处理顺序不管旋转标记旋转信息很容易被破坏导致个体慢慢退化到「全部不旋转」的局部最优。解决让变异算子承担更多探索职责。除了常规的交换变异每次变异以 30% 概率随机翻转一个旋转标记并且交叉时把父代的旋转片段也一起继承下来。另外在初始化种群时可以安排一部分个体全部旋转# 初始化时强制一部分个体全部零件旋转 for i in range(pop_size): if i % 10 0: ind.rotate_flags [1] * n_items这样种群初始就有 10% 的个体是全旋转方案给算法提供了另一个搜索起点。这么做以后即使初期陷入了全不旋转的坑变异也能把个体拽出来。4.5 避坑解码死循环或数组越界现象程序运行到一半卡住不动CPU 占用满或者抛 IndexError调试发现 floors 索引变成负数。原因split_floor 切割水平线时如果线段坐标相等或宽度为零会插入空白线段之后排序、合并处理不当会造成死循环。还有一种可能是遗传交叉把 genes 打乱后出现了重复的零件编号导致解码时按编号取宽度出错。解决在 split_floor 里做三个保护宽度小于 eps 的线段直接丢弃合并相邻同高线段每次解码开始前检查 genes 是否为合法排列是否是 0..N-1 的一个排列如果不是就返回一个全惩罚的个体而不是抛异常。def is_valid_permutation(genes, n): return sorted(genes) list(range(n))这样的检查速度是 O(n log n)对 100 个个体的种群几乎可以忽略。把它放在解码前一旦发现非法个体直接分配一个负适应度而不是让它进入解码逻辑可以避免很多隐蔽越界。我建议你把这个合法性检查放在 decode_individual 的第一行比在交叉算子里面补丁逻辑更干净。5. 二次开发思路从单板材到多板材切割的改造最后一个大改动往往是从「一块板」扩展到「多块板」。现有算法默认一块无限高的板材只定宽排样结果的高度就是板材高度。实际板材切割场景中宽度固定、长度也固定的板材是一张一张裁的一张放不下就要开下一张。改造思路很简单在解码器里把 sheet.height 当作「当前板剩余高度」放不下所有零件时开启一张新板并把新板加入水平线集合。适应度函数改成「多张板的总利用率」即所有板上的已放面积和除以所有板的可用面积和。具体技巧不要在适应度里直接惩罚未放的零件而应该让「新开板」本身就成为一种代价。因为每多开一张板板材总面积增加利用率自然下降遗传算法会自发地往「用更少板」的方向搜索。这样改造后不需要额外调整惩罚系数逻辑更自洽。我还会在结果画布里用不同背景色区分不同板方便人工检查。验证方法拿 50 个随机生成的零件先用人工经验排一次再用改造后的算法跑一遍分别记录用板数量和平均利用率。我实测的样例中人工用了 4 张板遗传算法用 3 张板但利用率低了 3 个百分点原因是它把零件打散得更开、单板组合略差。看到这种结果不要急着改参数先看是不是解码器对新板的边界处理有误比如新板的水平线集合有没有正确重置旧板残留的线段是不是混进了新板。用一组小数据逐张板打印坐标比盯着曲线猜快得多。另一个很小但很实用的改造是把「板材间刀缝」考虑进来每个零件宽高加上一个 gap 变量再参与解码最后画图时把 gap 画成浅色边。这样代码改动量不超过 10 行却让结果更接近真实切割场景。从那以后我每次改造排样项目都会强制走一遍「先动解码器、再动适应度、最后动界面」的顺序避免一上来就调参。把解码器验证扎实了遗传算法才有意义。希望帮到你。本文还有配套的精品资源点击获取