C++实现矩形排样优化：基于遗传算法的工程实践

1. 项目概述与核心价值

最近在做一个跟生产制造相关的项目，里面有个绕不开的经典难题：如何把一堆大小不一的矩形零件，最省料地排布在一张固定大小的矩形板材上？这个问题在工业界有个专门的名字，叫“矩形排样问题”或“二维矩形装箱问题”。听起来简单，但真上手去解，你会发现它是个典型的NP-Hard组合优化问题，暴力穷举在零件稍多时基本就不可行了。网上能找到的C++例子要么太学术化，一堆数学公式看得人头大；要么就是过于简陋，只给个贪心算法的骨架，实际用起来效果很差，浪费严重。

所以，我花了些时间，基于遗传算法的思路，用C++从头实现了一个可运行、可调整、并且带了简单可视化输出的矩形排样优化例子。这个项目的目标不是追求学术界最顶尖的算法，而是提供一个工程上可用、逻辑清晰、便于理解和二次开发的实战代码框架。无论你是正在学习算法与数据结构的学生，还是需要在实际项目中集成排样功能的工程师，这个例子都能给你一个扎实的起点。它清晰地展示了如何将抽象的优化问题，转化为具体的染色体编码、适应度评估和种群进化过程，最终输出一个肉眼可见的优化排样图。

2. 问题拆解与算法选型

2.1 矩形排样问题的严格定义

在我们开始写代码之前，必须把问题边界框死。这里我们处理的是正交排样，即所有矩形的边都必须与板材的边平行，不允许旋转（当然，算法框架可以扩展支持90度旋转）。输入包括：

1. 板材：一个宽度为W，高度为H的大矩形。通常我们假设板材左下角为坐标原点(0, 0)。
2. 待排矩形集合：n个矩形，每个矩形i有宽度w_i和高度h_i。
3. 优化目标：在保证所有矩形不重叠、且完全位于板材内部的前提下，寻找一个排样方案，使得所使用的板材高度最小（假设板材宽度固定，这是最常见的优化目标），或者材料利用率最高（即已放置矩形总面积与所用板材面积的比值）。

约束条件非常严格：任意两个已放置的矩形，其区域不能有任何重叠；每个矩形的四边都必须满足在板材边界内。

2.2 为什么选择遗传算法？

解决NP-Hard问题，主流思路分几种：精确算法（如分支定界法）、启发式算法（如各种贪心策略）和元启发式算法（如遗传算法、模拟退火、禁忌搜索）。

• 精确算法：对于稍大规模的问题（比如矩形数量>10），计算时间会爆炸式增长，不适合需要快速响应的工程场景。
• 基础启发式算法：比如“最低水平线”算法、BL算法（Bottom-Left）等。它们速度极快，但容易陷入局部最优，排样质量不稳定，对输入顺序敏感。
• 遗传算法（GA）：它是一种模拟自然选择和遗传机制的全局优化算法。其核心优势在于：
  • 全局搜索能力：通过种群、交叉、变异操作，能够在整个解空间中进行探索，有更大机会跳出局部最优，找到更优解。
  • 灵活性：算法框架与具体问题的“解码”过程分离。我们只需要设计好如何用一个“染色体”表示一个排样顺序和策略，以及如何评估一个方案的好坏（适应度函数），剩下的进化过程是通用的。
  • 易于并行和扩展：种群中的个体可以独立评估适应度，天然适合并行计算。算法也很容易与其他局部搜索策略结合，形成混合算法以提升性能。

对于矩形排样这个具体问题，遗传算法提供了一种在可接受的时间内，寻找质量相当不错的排样方案的实用路径。它平衡了求解质量和计算成本，这正是工程实践中最需要的。

2.3 核心思路：将排样方案编码为“染色体”

遗传算法不直接操作排样方案本身，而是操作代表方案的“染色体”。我们的设计如下：

1. 基因编码：一条染色体由两部分串联组成。

   • 序列基因段：一个长度为n的排列（Permutation），表示矩形放入板材的先后顺序。例如染色体段[3,1,4,2]表示先放3号矩形，再放1号，接着4号，最后2号。
   • 旋转基因段（可选）：一个长度为n的二进制串，每一位对应一个矩形，0表示不旋转，1表示旋转90度（即宽高互换）。如果项目不允许旋转，此段可省略。 这种“序列+标志”的编码方式，是矩形排样GA中最常见和有效的编码之一。

2. 解码器（关键）：这是遗传算法与具体问题的桥梁。解码器的任务是将一条染色体“翻译”成一个具体的、可评估的排样方案。我们采用一个基于“最低水平线”的贪心放置策略作为解码器。

   • 算法维护一个“当前轮廓线”，通常由一组不断更新的水平线段（表示已放置矩形上方的空闲空间边界）表示。
   • 按照染色体指定的顺序依次处理每个矩形。
   • 对于当前矩形，根据旋转基因决定其实际宽高。
   • 在当前的轮廓线上，寻找一个可行的放置位置（通常是从左到右扫描，找到第一个能放下该矩形且满足“左下角”原则的位置，即BL规则）。
   • 放置该矩形，并更新轮廓线。
   • 这个过程是确定性的：相同的染色体，通过相同的解码器，永远得到相同的排样布局。

3. 适应度函数：解码后，我们得到一个排样方案和最终使用的板材高度used_height。适应度函数通常与优化目标直接相关。例如，若目标是最小化高度，则适应度可以设为Fitness = 1.0 / used_height（高度越小，适应度越高）。若目标是最大化利用率，则适应度可以是Fitness = total_area / (W * used_height)。

注意：解码器的设计是算法性能的关键。一个高效的解码器能快速评估染色体，而一个智能的解码器（如结合了更多启发式规则的放置策略）本身就能产生更好的布局，与GA的全局搜索能力形成互补。本例为了清晰，使用了最基础的BLF解码器。

3. 核心模块设计与C++实现

接下来，我们深入到代码层面，看看如何用C++的面向对象特性来构建这个系统。整个项目结构清晰，主要分为几个类。

3.1 数据结构定义：Rectangle与Placement

首先，我们需要基础的数据结构来表示矩形和它的最终位置。

// rect.h #ifndef RECT_H #define RECT_H struct Rectangle { int id; // 矩形唯一标识 int width; // 原始宽度 int height; // 原始高度 // 构造函数等... }; struct Placement { int rect_id; int x; // 矩形左下角x坐标 int y; // 矩形左下角y坐标 int width; // 放置时的宽度（考虑旋转后） int height; // 放置时的高度（考虑旋转后） bool rotated; // 是否旋转了90度 // 构造函数等... }; #endif // RECT_H

Placement结构体记录了排样结果，是解码器的输出，也是可视化模块的输入。

3.2 解码器类：BLFDecoder

这是算法的引擎之一。我们实现一个“最低水平线-最左适应”解码器。

// blf_decoder.h #ifndef BLF_DECODER_H #define BLF_DECODER_H #include <vector> #include "rect.h" #include "placement.h" class BLFDecoder { public: BLFDecoder(int sheet_width, const std::vector<Rectangle>& rects); ~BLFDecoder(); // 核心解码函数 std::vector<Placement> decode(const std::vector<int>& sequence, const std::vector<bool>& rotation) const; // 获取解码后使用的高度 int getUsedHeight() const { return used_height_; } private: int sheet_width_; std::vector<Rectangle> rectangles_; mutable int used_height_; // 解码过程中计算出的高度 // 内部辅助函数：更新水平线 void updateSkyline(/* ... */) const; }; #endif // BLF_DECODER_H

在decode函数的实现中，我们需要维护一个“水平线”数组skyline，其长度为板材宽度。skyline[i]表示在横坐标i处，当前已放置矩形所达到的最小高度（即从底部到此处轮廓的高度）。放置新矩形时：

1. 从最左端开始扫描skyline，寻找一个连续区间[start, start+rect_width)，使得该区间内所有skyline值中的最大值（即区间最低点的“天花板”）最小。这个最大值就是新矩形左下角的y坐标候选。
2. 采用“最左适应”原则，找到第一个能满足宽度要求的区间后，就将矩形放置在那里。
3. 放置后，更新skyline在区间[start, start+rect_width)内的所有值为new_height（即放置位置的y坐标加上矩形高度）。

这个过程模拟了将矩形从底部向左“挤”进去的过程，是很多实用排样软件的基础逻辑。

3.3 遗传算法核心类：GeneticAlgorithm

这个类管理整个进化过程。

// genetic_algorithm.h #ifndef GENETIC_ALGORITHM_H #define GENETIC_ALGORITHM_H #include <vector> #include "individual.h" class GeneticAlgorithm { public: GeneticAlgorithm(int pop_size, double crossover_rate, double mutation_rate, int elitism_count); ~GeneticAlgorithm(); // 初始化种群 void initPopulation(int chromosome_length); // 执行一代进化 void evolvePopulation(); // 获取当前代最优个体 const Individual& getFittest() const; // 运行算法主循环 void run(int max_generation); private: std::vector<Individual> population_; int population_size_; double crossover_rate_; double mutation_rate_; int elitism_count_; // 精英保留数量 int generation_; // 内部操作 Individual crossover(const Individual& parent1, const Individual& parent2); void mutate(Individual& individual); Individual tournamentSelect(int tournament_size) const; void evaluatePopulation(); // 评估整个种群的适应度 }; #endif // GENETIC_ALGORITHM_H

关键参数解析：

• population_size：种群大小。太小则搜索能力不足，太大则计算慢。通常建议在50-200之间，根据问题规模调整。
• crossover_rate：交叉概率。控制有多少个体参与产生后代。一般设置较高，如0.8-0.95。
• mutation_rate：变异概率。为避免早熟收敛、维持种群多样性，通常每个基因位有一个较小的变异概率，如0.01-0.1。
• elitism_count：精英保留数。直接保留上一代中最优秀的几个个体到下一代，保证算法不会倒退。通常设为1或2。

3.4 个体类：Individual

个体代表一个可能的解，即一条染色体。

// individual.h #ifndef INDIVIDUAL_H #define INDIVIDUAL_H #include <vector> class Individual { public: Individual(int length, bool init = true); // ... 拷贝构造、赋值运算符等 // 基因访问 const std::vector<int>& getSequence() const { return sequence_; } const std::vector<bool>& getRotation() const { return rotation_; } void setGene(int index, int seq_val, bool rot_val); // 适应度 double getFitness() const { return fitness_; } void setFitness(double fit) { fitness_ = fit; } // 计算适应度（依赖解码器） double calcFitness(const BLFDecoder& decoder); private: std::vector<int> sequence_; // 序列基因 std::vector<bool> rotation_; // 旋转基因 double fitness_; bool fitness_valid_; // 适应度缓存标志 }; #endif // INDIVIDUAL_H

这里有一个重要的设计点：适应度缓存。计算适应度（即调用解码器）是算法中最耗时的操作。一旦一个个体的基因没有改变，其适应度就不应该重复计算。fitness_valid_标志位和setGene方法配合，可以有效地实现这一点。

3.5 遗传算子实现：交叉与变异

这是驱动种群进化的核心。

1. 交叉（Crossover）：我们采用顺序交叉（OX）用于序列基因，这对于排列编码非常有效，可以保留父代的相对顺序。对于旋转基因，采用简单的单点交叉或均匀交叉即可。

   Individual GeneticAlgorithm::crossover(const Individual& parent1, const Individual& parent2) { Individual child(parent1.getSequence().size()); // 1. 序列基因OX交叉 // 随机选择交叉段 // 将父代1的交叉段复制给孩子 // 从父代2中按顺序取出剩余基因，填充孩子空缺位置 // 2. 旋转基因均匀交叉 // 每个位置以50%概率从父代1或父代2继承 return child; }

2. 变异（Mutation）：对于序列基因，常用交换变异（Swap Mutation）或逆转变异（Inversion Mutation）。交换变异即随机选择两个位置交换其基因值；逆转变异是随机选择一个子序列并将其反转。对于旋转基因，变异就是按概率翻转布尔值。

   void GeneticAlgorithm::mutate(Individual& ind) { // 序列基因变异：随机交换两个位置 if (rand() / (RAND_MAX + 1.0) < mutation_rate_) { int pos1 = rand() % ind.getSequence().size(); int pos2 = rand() % ind.getSequence().size(); std::swap(ind.accessSequence()[pos1], ind.accessSequence()[pos2]); ind.invalidateFitness(); } // 旋转基因变异：随机翻转一位 for (int i = 0; i < ind.getRotation().size(); ++i) { if (rand() / (RAND_MAX + 1.0) < mutation_rate_) { ind.accessRotation()[i] = !ind.accessRotation()[i]; ind.invalidateFitness(); } } }

   实操心得：变异率不宜过高，否则算法会退化为随机搜索。同时，任何改变基因的操作后，必须调用invalidateFitness()来标记适应度需要重新计算，这是保证缓存一致性的关键。

3.6 可视化输出

为了直观看到排样结果，我们可以用最简单的方式生成SVG格式的图片。SVG是文本格式的矢量图，用C++生成非常方便。

// svg_writer.h #ifndef SVG_WRITER_H #define SVG_WRITER_H #include <vector> #include <string> #include "placement.h" class SvgWriter { public: static bool write(const std::string& filename, int sheet_width, int sheet_height, const std::vector<Placement>& placements); }; #endif // SVG_WRITER_H

在write函数中，我们按照SVG标准，先画一个代表板材的大矩形，然后遍历placements向量，为每个已放置的矩形画一个带边框的矩形，并可以填充不同颜色加以区分。还可以在矩形中心添加其ID文本。生成的.svg文件可以用任何现代浏览器打开查看。

4. 完整工作流程与代码整合

现在我们把所有模块串联起来，看看main函数如何组织。

// main.cpp #include <iostream> #include "genetic_algorithm.h" #include "blf_decoder.h" #include "svg_writer.h" #include "rect.h" int main() { // 1. 定义板材和矩形数据 const int SHEET_WIDTH = 1000; const int SHEET_HEIGHT = 2000; // 初始高度设大一些，算法会优化 std::vector<Rectangle> rectangles = { {0, 200, 300}, {1, 250, 400}, {2, 300, 150}, {3, 150, 250}, {4, 400, 200}, {5, 350, 350}, // ... 可以添加更多测试矩形 }; // 2. 初始化解码器 BLFDecoder decoder(SHEET_WIDTH, rectangles); // 3. 配置并初始化遗传算法 int populationSize = 100; double crossoverRate = 0.85; double mutationRate = 0.02; int elitismCount = 2; int maxGenerations = 500; GeneticAlgorithm ga(populationSize, crossoverRate, mutationRate, elitismCount); // 染色体长度 = 矩形数量 (序列) + 矩形数量 (旋转，可选) int chromoLength = rectangles.size() * 2; // 假设使用旋转基因 ga.initPopulation(chromoLength); // 4. 主进化循环 std::cout << "开始优化..." << std::endl; for (int gen = 0; gen < maxGenerations; ++gen) { ga.evolvePopulation(); const Individual& best = ga.getFittest(); // 每一代或每N代输出一次当前最优解的高度 if (gen % 50 == 0) { double fitness = best.getFitness(); double usedHeight = 1.0 / fitness; // 假设适应度是高度的倒数 std::cout << "Generation " << gen << ": Best Height = " << usedHeight << std::endl; } } // 5. 获取最终结果并可视化 const Individual& bestSolution = ga.getFittest(); // 需要解码得到具体的排样位置 std::vector<Placement> finalPlacement = decoder.decode( bestSolution.getSequence(), bestSolution.getRotation() // 如果没使用旋转，这部分传空或默认值 ); int finalHeight = decoder.getUsedHeight(); double utilization = 0.0; for (const auto& rect : rectangles) { utilization += rect.width * rect.height; } utilization /= (SHEET_WIDTH * finalHeight); std::cout << "\n优化结束！" << std::endl; std::cout << "最终板材使用高度: " << finalHeight << std::endl; std::cout << "材料利用率: " << utilization * 100 << "%" << std::endl; // 6. 输出SVG图 SvgWriter::write("nesting_result.svg", SHEET_WIDTH, finalHeight, finalPlacement); std::cout << "排样图已保存至 'nesting_result.svg'。" << std::endl; return 0; }

这个流程清晰地展示了从问题定义、算法配置、迭代优化到结果输出的完整链路。编译运行后，你会在终端看到迭代过程，并最终得到一个可视化的排样结果图。

5. 参数调优与性能提升实战

遗传算法的效果很大程度上依赖于参数。没有“放之四海而皆准”的最优参数，但有一些调优原则和技巧。

5.1 关键参数经验值

实操心得：最有效的调优方法是画图观察。记录每一代最优个体的适应度（或高度），绘制进化曲线。理想的曲线是前期快速下降，中期缓慢下降，后期趋于平稳。如果曲线过早平缓，可能是早熟，需要增加变异概率或种群大小。如果曲线一直震荡不下降，可能是变异太强或交叉有问题。

5.2 解码器优化：算法性能的瓶颈

遗传算法中，90%以上的时间都花在decode函数上。优化解码器能直接大幅提升整体速度。

1. 数据结构优化：我们之前用数组表示skyline。放置矩形时需要扫描寻找最低点，这是O(W)的操作。可以改用更高效的数据结构，如**线段树（Segment Tree）**来维护区间最大值和最小值，将寻找最低点的操作优化到O(log W)。
2. 放置策略增强：基础的BLF策略是“找到第一个能放的位置就放”。可以尝试更优的策略，如“最佳适应（Best Fit）”：扫描所有可行的放置位置，选择那个使得放置后新的轮廓线最平整（即最高点增加最少）的位置。这需要更多的计算，但可能得到更优的单次布局。
3. 启发式规则融合：在解码前，可以对染色体序列进行局部调整。例如，将面积大的矩形优先放置（即使染色体序列不是这样），这可以通过在解码器内部增加一个排序步骤来实现，相当于将一条染色体映射到多个可能的布局中最好的一个。

// 一个改进的解码器伪代码思路 std::vector<Placement> AdvancedDecoder::decode(...) { // 1. 根据序列基因和旋转基因，生成一个带“优先级”的矩形列表 // 2. 可以按面积从大到小对列表进行稳定排序（稳定排序保留原序列的部分信息） // 3. 使用更高效的数据结构（如线段树）和最佳适应策略进行放置 // 4. 返回布局 }

5.3 适应度函数的改进

基础的适应度函数1.0 / used_height只考虑了高度。但在实际生产中，我们可能还有其它目标：

• 稳定性：希望重心尽量低，或布局紧凑。
• 工艺约束：矩形之间需要预留切割间隙（刀缝）。
• 多目标优化：同时最小化高度和最大化利用率。

我们可以设计更复杂的适应度函数。例如，考虑间隙gap：

double fitness = 1.0 / (used_height + penalty); // penalty 是对重叠或超出边界的惩罚项，可以设为一个很大的数

对于多目标，可以采用加权和法，或将其中一个目标作为约束条件。

6. 常见问题排查与调试技巧

在实际编码和运行中，你肯定会遇到各种问题。这里记录一些典型的坑和解决方法。

6.1 编译与运行问题

• 问题：编译错误，undefined reference to ...。
  • 排查：检查头文件（.h）中的函数声明与源文件（.cpp）中的定义是否一致。确保所有源文件都加入了编译列表（CMakeLists.txt或Makefile）。
• 问题：程序运行崩溃，段错误（Segmentation Fault）。
  • 排查：
    1. 首先检查所有数组和向量的访问是否越界。特别是在decode函数中，访问skyline数组时，确保索引i满足0 <= i < sheet_width。
    2. 检查指针或引用是否在对象生命周期结束后还被使用。
    3. 使用调试器（如GDB）定位崩溃行。在关键函数入口添加打印语句也是朴素的调试方法。
• 问题：算法结果每次运行都不一样，且有时很差。
  • 排查：遗传算法具有随机性，但差异不应过大。首先检查随机数种子是否固定（srand(seed)），用于复现问题。其次，检查交叉和变异操作是否正确实现了“深拷贝”，避免意外修改父代个体。

6.2 算法逻辑问题

• 问题：适应度值不更新，或者越进化越差。
  • 排查：
    1. 适应度缓存失效：这是最常见的原因。确保任何修改个体基因的操作（如setGene,crossover,mutate）后，都调用了invalidateFitness()。在evaluatePopulation中，只对fitness_valid_为假的个体重新计算适应度。
    2. 选择算子压力不足：检查你的选择算子（如锦标赛选择）。如果选择压力太小，优秀个体被选中的优势不明显。可以增大锦标赛的规模（tournament_size）。
    3. 变异率过高：过高的变异率会破坏好的基因块，使算法退化为随机搜索。尝试将变异率降到0.01以下。
• 问题：排样结果有重叠。
  • 排查：问题100%出在解码器。仔细检查你的放置逻辑和轮廓线更新逻辑。
    1. 在放置新矩形时，确认其左下角坐标(x, y)是否满足：x >= 0,y >= 0,x+width <= sheet_width,y+height <= current_height。
    2. 确认更新skyline时，覆盖的区间是[x, x+width)，而不是[x, x+width]。区间通常是左闭右开。
    3. 添加可视化调试：在解码过程中，每放置一个矩形，就打印出它的位置和当前的skyline快照，或者生成一个中间状态的SVG图，这样重叠错误一目了然。
• 问题：材料利用率很低，空白区域很多。
  • 排查：
    1. 解码器策略：基础的BLF策略本身就会产生较多空洞。考虑升级到“最佳适应”策略。
    2. 遗传算法陷入局部最优：尝试增加种群大小，或者采用“自适应变异率”——当种群多样性下降时（如适应度方差变小），自动增加变异率。
    3. 问题本身难度：对于某些极端尺寸的矩形组合，任何算法都无法达到很高的利用率，这是问题本身的性质决定的。

6.3 性能优化检查点

如果程序运行很慢，特别是当矩形数量超过50时，可以关注以下几点：

1. 性能分析：使用gprof或Valgrind的callgrind工具进行性能剖析，找出最耗时的函数。毫无疑问，decode和适应度计算会是热点。
2. 解码器优化：如前所述，将skyline的线性扫描改为线段树查询。
3. 减少拷贝：在交叉、变异和选择过程中，避免不必要的个体拷贝。使用引用、指针或移动语义。
4. 并行评估：种群中个体的适应度计算是相互独立的，可以使用OpenMP或C++标准库的<thread>进行并行计算，这是遗传算法最容易获得的性能提升。

最后，一个非常实用的建议是：从小规模测试开始。先用3-5个矩形测试，确保解码器逻辑完全正确，可视化结果没有重叠。然后逐步增加矩形数量，并观察算法的行为和性能变化。这样能帮你快速定位问题是出在核心逻辑上，还是出在规模扩展后的性能或策略局限性上。这个矩形排样的C++例子，就像一把瑞士军刀，它提供了一个完整且可扩展的框架。理解了它的每一部分，你就能根据自己面对的具体问题——无论是钣金切割、布料裁剪还是芯片布局——进行针对性的修改和强化。