企业官网建设流程全解析

简介：基于遗传算法的矩形排样是一份面向制造业、印刷与包装领域开发者的算法应用资源，解决矩形板材利用率最大化与材料浪费问题。资源包内涵盖完整的MFC工程，可从文本文件读取矩形规格数据，通过选择、交叉、变异等遗传算子迭代优化布局，并借助MFC窗口直观展示结果。包体共64个文件，约8.17MB，核心包括cpp与h源码、多个txt数据文件、项目配置文件和可执行exe，便于直接运行与二次开发。已有5410人学习下载，适合需要掌握遗传算法落地或MFC可视化编程的读者。通过该项目可学习矩形排样问题的编码与适应度设计，理解种群参数对收敛效果的影响，并利用随附测试数据快速验证算法效果。

1. 矩形排样为什么值得用遗传算法：一个每天要跑几十遍的优化问题

做板材加工的人都知道，排样结果直接决定一张板上能出多少件。人工排样靠老师傅经验，换一批板件就要重新排一次；数学规划在 30 个板件以内还能跑，板件数量一过百，求解时间就变得没法看。基于遗传算法的矩形排样是另一种思路：不追求一步到位的最优证明，而是用一群候选解去迭代逼近好解。它不要求目标函数连续可导，只要能把“摆放结果好坏”量化成适应度，就能用。做板材套料、家具开料、玻璃切割、包装设计的人都适用；几十个到几百个矩形，几分钟内得到 95% 以上利用率的排样结果，是这个方向最现实的价值。

2. 先把排样问题翻译成染色体：编码、解码与初始种群

遗传算法不能直接操作“一张排样图”，只能操作一串基因。所以拿到矩形排样问题的第一件事，不是想用哪个算子，而是先想清楚：一个个体是什么，一段基因长什么样，怎么把基因翻译回实际坐标。这三件事没定稳，后面所有算子都是在沙滩上盖楼。

2.1 输入数据与问题建模

矩形排样最常见的建模方式，是把一张板材看成固定宽度 W、高度方向不受限的二维平面，目标是在不重叠、不越界的前提下，把所有矩形排进去，让最终使用的板材高度尽可能小，也就是面积利用率尽可能高。

输入数据用一张表就能说清楚：

这里有个容易忽略的点：矩形排样虽然叫“矩形”，但业务上往往不允许所有件都随便旋转。比如木纹方向、玻璃镀膜方向、五金孔位方向都会限制旋转。所以数据输入阶段就把can_rot存下来，而不是等算法跑完再返工。我一般还会把宽度和高度先处理成整数，单位统一到毫米，后续解码时少很多浮点误差。

2.2 基因编码：一个排列加一串旋转标志

编码方式直接影响交叉变异的复杂度。常见的做法是：基因 = 矩形编号的排列 + 每个矩形是否旋转的标志位。

排列部分是一个长度为 N 的序列，序列里的每个值是一个矩形编号，表示“先放谁、后放谁”。旋转标志位是一个 0/1 数组，1 表示该矩形旋转 90°，0 表示保持原方向。为什么用排列而不是直接用坐标？因为坐标是连续值，直接编码会让搜索空间暴涨，而且交叉后大概率产生重叠布局，很难设计有效的算子；排列编码的交叉变异都有成熟方案，解码器负责把排列转成坐标，这样遗传算法只负责搜索“顺序空间”，问题就被拆开了。

import numpy as np def fix_rot(rot, can_rot): # 不允许旋转的矩形，强制把旋转位清零 return [r if cr else 0 for r, cr in zip(rot, can_rot)] # 示例：5 个矩形 n = 5 order = list(np.random.permutation(n)) # 例如 [2, 0, 4, 1, 3] rot = list(np.random.randint(0, 2, n)) # 例如 [1, 0, 0, 1, 0] rot = fix_rot(rot, can_rot) # can_rot=[True,False,...]

fix_rot这个函数很不起眼，但它是硬约束的兜底。初始化、交叉、变异之后都要调一次，保证那些不能旋转的矩形永远不会被旋转。少了这一步，后面适应度再写好也没用，算法会在搜索空间里浪费大量时间尝试非法解。

2.3 解码：把基因翻译成看得见的排样图

有了排列和旋转位，下一步就是用解码器把基因翻译成每个矩形的左下角坐标。这里我用的是一个贪心的“最左最下”放置策略：按排列顺序，每个矩形放到当前布局中能放下的最低位置，同一高度层里优先靠左。

def decode(order, rot, rects, W): n = len(order) placed = {} # 矩形编号 -> (x, y) ys = [0.0] # 候选底部 y 坐标集合 for idx in order: w0, h0 = rects[idx] w, h = (h0, w0) if rot[idx] else (w0, h0) best = None # 候选 y 从低到高，每个 y 上 x 从左到右 for y in sorted(set(ys)): for x in np.arange(0, W - w + 1e-6, 1.0): pos = (float(x), float(y)) ok = True for j, (xj, yj) in placed.items(): wj, hj = (rects[j][1], rects[j][0]) if rot[j] else rects[j] # 重叠判定：只要有交集就不可放 if x + w <= xj or x >= xj + wj or y + h <= yj or y >= yj + hj: continue ok = False break if ok: best = pos break if best is not None: break if best is None: # 兜底：放到当前最高顶部的上方，保证不重叠 top = max(yj + ((rects[j][1], rects[j][0])[rot[j]] if rot[j] else rects[j][1]) for j, (xj, yj) in placed.items()) if placed else 0.0 best = (0.0, top) placed[idx] = best ys.append(best[1] + h) return placed

这段代码有几个地方值得解释。ys集合保存的是已放矩形顶边的 y 坐标，作为下一个矩形左下角的候选高度。这样能保证新放的矩形不会和已放矩形重叠，同时尽量往低处放。x 用np.arange按 1.0 步长扫描，如果业务允许更细的间隔，可以把步长改小；如果矩形的边长本身是整数毫米，这个步长就够用。兜底分支是为了防止某些极端排列导致放不下，直接把新矩形放到当前最高处上方。

注意这里我没有强制要求下方必须有支撑。激光切割、水刀切割场景下，矩形是“漂浮”在虚拟板材上的，只要不重叠、不越界就可以。如果你的工艺要求矩形必须靠边或互相支撑（比如冲压桥接），那解码器还要额外检查“下方接触”，复杂度会再高一截。

2.4 初始种群：一半靠启发，一半靠随机

遗传算法很吃初始种群的质量。全随机初始化简单，但收敛慢；全启发式初始化容易早熟。我一般会让第一个个体按面积降序排列，后面的个体随机打乱，这样种群既有好苗子，又有足够的探索性。

pop_size = 120 pop = [] # 面积降序的启发式个体 base_order = sorted(range(n), key=lambda i: -rects[i][0] * rects[i][1]) for _ in range(pop_size): if _ == 0: order = base_order.copy() else: order = list(np.random.permutation(n)) rot = fix_rot(list(np.random.randint(0, 2, n)), can_rot) pop.append([order, rot])

面积降序作为初始个体，在矩形排样里几乎永远比随机排列好，因为大件先放能避免后期小块塞不进缝隙的现象。但只保留这一个启发式个体就够了，其余个体保持随机，否则种群多样性会被“面积降序”这一个方向带偏。

3. 让种群进化起来：选择、交叉、变异的实现细节

编码和解码跑通之后，遗传算法才算有了骨架。接下来把选择、交叉、变异三个算子填进去，再套一个主循环。这一章我直接给可运行的最小实现，并说明每个参数改动的后果。

3.1 锦标赛选择：用 k 控制选择压力

选择策略五花八门，但我最常用锦标赛选择：从种群里随机抽 k 个个体，选适应度最好的那个进入下一代。k 越大，选择压力越大，种群收敛越快，但也越容易早熟。

def select(pop, fitnesses, k=3): idxs = np.random.choice(len(pop), k, replace=False) best = max(idxs, key=lambda i: fitnesses[i]) return pop[best]

这里的 k 是唯一参数。k=2 时选择最温和，种群多样性保持得好；k=5 以上会让最优个体迅速占据种群，对矩形排样这种多峰问题不太友好。我一般默认 k=3。

3.2 OX 交叉：保住矩形之间的相对顺序

排列编码不能像二进制编码那样随机切两段拼接，否则子代里会出现重复的矩形编号、丢掉某些编号。解决这个问题最经典的是 OX 交叉（Order Crossover）：保留父本的一段片段，再从另一个父本按顺序补齐缺失的编号。

def ox_crossover(order1, order2): n = len(order1) a, b = sorted(np.random.choice(n, 2, replace=False)) if b - a == n - 1: b = n - 2 if a == 0 else b # 子代 1：保留 order1 的片段，用 order2 补齐 child1 = [-1] * n child1[a:b+1] = order1[a:b+1] rest1 = [g for g in order2 if g not in order1[a:b+1]] slots1 = list(range(b+1, n)) + list(range(0, a)) for slot, gene in zip(slots1, rest1): child1[slot] = gene # 子代 2：保留 order2 的片段，用 order1 补齐 child2 = [-1] * n child2[a:b+1] = order2[a:b+1] rest2 = [g for g in order1 if g not in order2[a:b+1]] for slot, gene in zip(slots1, rest2): child2[slot] = gene return child1, child2

OX 的巧妙之处在于，它保留了父本中“哪些矩形挨着放”这个相对顺序信息，同时又保证子代是一个合法的排列。对矩形排样来说，顺序信息直接对应解码后的空间位置关系，所以 OX 比简单交换片段效果好得多。旋转位不参与 OX 交叉，子代分别继承两个父本的旋转数组。

3.3 变异：交换顺序位，小概率翻转旋转位

变异是跳出局部最优的关键。顺序部分我用交换变异：随机抽两个位置交换。旋转部分用位翻转：每个旋转位以很小概率翻转一次。

def mutate(ind, rects, swap_rate=0.1, flip_rate=0.03): order, rot = ind # 按个体概率决定是否做一次交换变异 if np.random.rand() < swap_rate: a, b = np.random.choice(len(order), 2, replace=False) order[a], order[b] = order[b], order[a] # 按基因位概率翻转旋转位 for i in range(len(rot)): if np.random.rand() < flip_rate: rot[i] = 1 - rot[i] return [order, rot]

这里有个常见误区：swap_rate是“每个个体做交换变异的概率”，不是“每个基因位被交换的概率”。如果写成对每个位置都按 0.1 概率交换，那一个个体里会同时发生十几次交换，基本等于重新随机生成。旋转位的flip_rate一般设 0.02~0.05 就够了，太高会让旋转方向失去进化意义，变成噪声。

3.4 主循环：把算子拼成一轮进化

把上面三个算子拼起来，再加上精英保留，就是完整的主循环。精英保留的意思是：每一代先把适应度最好的几个个体原样复制到下一代，保证最优解不会因为随机性丢失。

generations = 400 elite_size = 3 crossover_prob = 0.9 for gen in range(generations): fits = [calc_fitness(ind[0], ind[1], rects, W, H_max) for ind in pop] elites = [pop[i] for i in np.argsort(fits)[-elite_size:]] new_pop = elites.copy() while len(new_pop) < pop_size: p1 = select(pop, fits, k=3) p2 = select(pop, fits, k=3) if np.random.rand() < crossover_prob: c1_order, c2_order = ox_crossover(p1[0], p2[0]) c1 = mutate([c1_order, fix_rot(p1[1].copy(), can_rot)], rects) c2 = mutate([c2_order, fix_rot(p2[1].copy(), can_rot)], rects) else: c1 = mutate([p1[0].copy(), fix_rot(p1[1].copy(), can_rot)], rects) c2 = mutate([p2[0].copy(), fix_rot(p2[1].copy(), can_rot)], rects) new_pop.append(c1) if len(new_pop) < pop_size: new_pop.append(c2) pop = new_pop

calc_fitness在下一章给出具体实现，这里先把它当成黑盒子用：给一个个体，返回一个代表排样好坏的数字。主循环写完后，缺的就只剩适应度函数和参数表了。

4. 适应度函数与参数：利用率、约束和收敛节奏怎么平衡

适应度函数是整个遗传算法的“指挥棒”。它决定了进化方向。矩形排样的适应度不是简单写一个公式就完事，还要考虑硬约束、惩罚项和多板扩展。这一章把这些一次讲透。

4.1 适应度计算：从利用率到越限惩罚

单板排样最常见的适应度是面积利用率：所有矩形面积之和除以板材宽度乘以实际使用高度。利用率越高，说明板材浪费越少。但如果业务里有板材高度上限，直接用利用率会诱导算法把布局排到上限之外，所以必须加惩罚项。

def calc_fitness(order, rot, rects, W, H_max, penalty=1.0): placed = decode(order, rot, rects, W) used_area = 0.0 max_y = 0.0 for idx, (x, y) in placed.items(): w0, h0 = rects[idx] w, h = (h0, w0) if rot[idx] else (w0, h0) used_area += w * h max_y = max(max_y, y + h) util = used_area / (W * max_y) if max_y > 0 else 0.0 over = max(0.0, max_y - H_max) return util - penalty * over

penalty的取值很关键。它必须大于“越限后省下来的利用率”。如果 H_max 是 8000，某个体排到 8200，省下的高度可能让利用率提高 2 个百分点，那 penalty 至少要大于 0.02。我实际中一般取 1.0，让越限个体的适应度直接变成负数，彻底失去竞争力。这样算法会优先保证不越限，再谈利用率。

4.2 约束处理：硬约束永远比惩罚项可靠

矩形排样里最常遇到的约束有三类：不能旋转、必须靠边、不能用满整张板（要留安全边距）。我的原则是：能用编码层解决的约束，就不要留给适应度惩罚。

不能旋转：用fix_rot在初始化、交叉、变异后强制清零旋转位，这是硬约束，永远不会产生非法个体。靠边约束：把靠边矩形在解码器里单独处理，比如按“先放靠边件、后放自由件”的顺序排队。安全边距：直接把板材宽度从 W 改成W - 2*margin，矩形坐标仍然从 0 开始算，等排完后整体平移 margin。这些做法比在适应度里加惩罚项更稳定，因为惩罚项只能“引导”算法避开非法解，而硬约束直接让非法解不存在。

多板扩展也是一个常见需求。单板排样跑通后，多板问题可以这样处理：每次从剩余矩形集合里选一部分排一块板，排不下再开下一块板。遗传算法只管单板的排列顺序，外层用一个贪心循环逐板消耗矩形。这个方案实现简单，而且单板利用率优化好了，整单板材的张数自然会下降。

4.3 参数表与调参套路

很多人在矩形排样上翻车，不是因为算法不对，而是参数拍脑袋。我整理了一张常见参数表，覆盖中小规模场景：

调参的顺序很重要。我一般先固定 pop_size=200、generations=400，把 k 从 2 调到 4，看哪档收敛曲线更好；再固定 k，调 swap_rate；最后才动交叉概率。一次只动一个参数，否则多个变量叠加，你永远不知道是哪个改动起了作用。

4.4 随机种子与评测协议

遗传算法是随机算法，同一个参数换一个随机种子，结果可能差好几个百分点。所以工程上必须有一套固定的评测协议：先用一个固定种子（比如 42）调参，确认改进方向；再用 10 个不同的种子各跑一遍，统计最好值、中位值、最差值。如果中位数和最好值只差 0.5 个百分点，说明算法稳定；如果差到 2 个百分点以上，说明参数或算子还有问题。

我还会把“面积降序排列的贪心解码结果”当成基线。遗传算法如果跑了几百代还打不过这个基线，那一定是某个环节写错了，不要继续调参，回头检查编码和解码。

5. 遗传算法矩形排样的五个踩坑记录：现象、原因与排查

从“能跑”到“跑得好”，中间隔着无数细节。这一章我挑五个真实高频的坑，每条都按现象、原因、解决的顺序写，方便你对照排查。

5.1 种群早熟：几十代后就停在普通解上

现象：迭代到 50 代左右，最优利用率曲线就平了，再跑几百代也没有提升，而且种群里的个体长得越来越像。

原因：最常见是选择压力过大。k 设成 5 甚至更高，每代都把少数最优个体反复选出来繁殖，多样性迅速耗尽；其次是变异率太低，跳出局部最优的能力不足。

解决：把 k 降到 2~3，swap_rate提高到 0.1~0.15，同时每代以 5% 的比例注入随机个体，强制维持种群多样性。注入随机个体的实现并不复杂，在主循环的new_pop里追加几个完全随机的个体即可。

5.2 同样一段代码，换个随机种子结果差到离谱

现象：同一批矩形、同一套参数，种子 12345 跑出 96.3%，种子 67890 只有 93.8%，不知道该信谁。

原因：遗传算法本身就有随机性，单次运行只是对解空间的一次采样。很多人只跑一次就把结果写进报告，这是自欺欺人。

解决：固定种子做复现，调参对比时用同一组种子对拍；最终评估时跑 10 个种子，看中位数和最优值的差距。如果差距超过 1.5 个百分点，先查解码器和适应度计算，再考虑是不是算子写错了。

5.3 旋转位进化的结果，车间根本没法切

现象：算法给出的排样图利用率很漂亮，但很多矩形被旋转了 90°。拉到车间一看，木纹方向反了，或者镀膜面朝向不对，整个方案作废。

原因：初始化时没有考虑业务约束，把所有矩形都默认成可以旋转。遗传算法可不管你的家具纹理方向，它只知道旋转能塞得更满。

解决：把can_rot作为输入数据的一部分，在初始化、交叉、变异之后都调用fix_rot强制清零。这个坑最可怕的地方在于它不报错，不报警，直到生产环节才爆发。所以我建议在适应度函数里加一行断言：如果出现不允许旋转却被旋转的矩形，直接抛异常，让问题尽早暴露。

5.4 追求最高利用率，排出一张“细高”的板子

现象：适应度最高的方案里，板材使用高度很小，利用率很高，但板材又高又窄，切割行程长了一倍，上料下料也麻烦。

原因：目标函数只定义了“面积利用率”，没有考虑实际生产对板材长宽比的偏好。算法发现把矩形堆高能省面积，就会往这个方向钻。

解决：在适应度里加长宽比调节项，例如fitness = util - 0.02 * abs(H / W - target_ratio)，让算法在利用率和切割合理性之间找平衡。如果你想分阶段优化，也可以先跑出利用率较高的候选集，再从候选集里按切割路径长度选次优解。

5.5 解码器改了，之前的好结果全都不作数

现象：某个序列在旧解码器里利用率很高，你优化了解码逻辑之后，同一个序列重新解码，布局完全不同，适应度明显下降。

原因：遗传算法优化的是“排列空间”里的个体，而解码器负责把排列映射成坐标。解码器一旦改变，适应度函数其实就变了，之前进化出来的好个体在新的映射下不再优秀。

解决：把解码器当成算法的一部分来版本管理。改解码器之前，先固定一批测试序列，记录它们的适应度；改完之后跑同样的测试序列，对比结果。同时建议给解码器写单元测试：随机生成 100 个排列，验证解码结果无重叠、无越界、矩形编号无重复。这 5 分钟的工作，可以省下后面几小时的排查时间。

6. 让结果可复现、可裁剪：局部搜索与严格的验证习惯

遗传算法跑到后期，全局搜索已经很难再提升，这时候真正的收益往往来自局部搜索。我在最优个体附近做“邻域爬山”：随机交换两个基因或翻转一个旋转位，如果适应度更高就接受，否则继续试。这种做法在工程里非常实用，能把最终利用率再往上推 0.2~0.5 个百分点。

def local_search(ind, rects, W, H_max, max_tries=200): best_order, best_rot = ind[0].copy(), ind[1].copy() best_f = calc_fitness(best_order, best_rot, rects, W, H_max) for _ in range(max_tries): # 随机交换两个顺序位 new_order = best_order.copy() a, b = np.random.choice(len(new_order), 2, replace=False) new_order[a], new_order[b] = new_order[b], new_order[a] # 随机翻转一个旋转位 new_rot = fix_rot(best_rot.copy(), can_rot) j = np.random.randint(len(new_rot)) new_rot[j] = 1 - new_rot[j] new_rot = fix_rot(new_rot, can_rot) f = calc_fitness(new_order, new_rot, rects, W, H_max) if f > best_f: return [new_order, new_rot] return [best_order, best_rot]

这种“首个改进即接受”的爬山策略很简单，但每代对精英个体做一次，效果非常明显。需要注意的是，局部搜索必须和固定种子的评测协议配合使用，否则你无法判断提升来自局部搜索还是运气。

最后说一个我自己养成的习惯：拿到任何排样优化任务，第一件事不是调参数，而是先写一个能打印布局图的脚本，把每个矩形画出来，肉眼确认有没有重叠、有没有越界。以前我总觉得“算法指标对了就行”，结果好几回栽在解码器边界条件上。后来我把“布局可视化 + 固定随机种子 + 多种子统计”当成标配，踩的坑少了一半。

先把编码、解码、适应度写稳，再谈算子和参数，这个习惯在矩形排样问题上特别值得养成。希望帮到你。

本文还有配套的精品资源，点击获取