数学建模实战：用遗传算法搞定木板混合切割方案（P1+P3产品案例）

如果你正在准备数学建模竞赛，尤其是涉及到优化、排样、资源分配这类题目，那么“二维矩形件切割问题”绝对是你绕不开的经典题型。它听起来像是工厂里的实际问题——如何在一块大木板上切割出不同尺寸的小零件，使得浪费的边角料最少。但在竞赛中，它考验的远不止是生活常识，而是你将现实问题抽象为数学模型，并选择合适算法高效求解的能力。

很多同学初次面对这类问题，第一反应可能是用线性规划或整数规划。这没错，对于小规模、规则性强的问题，它们能给出精确的最优解。但你想过没有，当切割方案变得复杂，比如允许零件旋转、混合排布时，可能的排列组合数量会爆炸式增长，变成一个组合爆炸的难题。这时候，传统的精确算法可能会因为计算时间过长而变得不实用。

这就是为什么我们需要像遗传算法这样的启发式优化方法。它不保证找到数学上的全局最优解，但它能在合理的时间内，找到一个非常优秀、接近最优的可行解。对于需要在有限竞赛时间内提交完整方案的你来说，这往往是更实际、更强大的武器。本文，我们就以一道经典的“P1和P3产品混合切割”赛题为例，抛开那些教科书式的理论，直接进入实战，手把手带你用遗传算法构建模型、编写代码，并深入分析其中的关键技巧和避坑指南。你会发现，掌握这种思路，不仅能解决木板切割，还能应用到无人机路径规划、课程表编排等众多领域。

1. 问题重述与核心挑战：为什么不用简单枚举？

我们面对的具体问题是：已知一种规格的原材料大木板（例如S1: 3000mm × 1500mm），需要从中切割两种矩形产品P1（373×201）和P3（406×229）。目标可能有两种：一是单张木板利用率最高（即剩余面积最小），二是用最少的木板完成一批订单（总利用率最高）。

最“笨”但最直接的想法是枚举所有可能的摆放方式。P1和P3各有横放和竖放两种方向，我们需要决定它们在木板上的位置。如果采用简单的网格划分思想，计算量似乎可控。但这里有几个立刻会遇到的硬钉子：

• 组合爆炸：即便我们把木板离散化成网格，每个网格点决定是否放置某个零件的某个角，搜索空间也大得惊人。
• 几何约束：零件之间不能重叠，且不能超出木板边界。用枚举法编程验证这些约束，代码会非常复杂且效率低下。
• 非网格对齐：最优解往往不是简单地将零件对齐到某个想象出来的网格上，零件之间可能错位排列以更好地利用空间。枚举网格对齐的方案会错过这些更优解。

所以，我们需要一种更聪明的搜索策略。遗传算法正是模拟生物进化“优胜劣汰”的思想，从一个随机生成的“方案种群”开始，通过选择、交叉、变异不断进化出更好的方案。它不遍历所有可能，而是引导搜索走向更有希望的区域。

注意：在数学建模论文中，清晰阐述放弃枚举法、选择遗传算法的理由，能体现你对问题复杂度的理解和算法选型的论证过程，这是重要的加分项。

2. 遗传算法设计：如何将切割方案编码成“染色体”？

遗传算法操作的是一个个“个体”，每个个体代表一个切割方案。所以，首要任务是把一个具体的切割方案（包含每个零件的位置和方向）转换成一种计算机可以处理且便于“进化”的数据结构，这就是编码。编码方式的好坏直接决定了算法的效率和效果。

对于二维切割问题，常见的编码方式有：

• 基于序列的编码：将需要放置的零件排成一个序列。解码时，按照序列顺序，采用某种启发式规则（如“左下角优先”规则）依次将零件放入木板。染色体就是零件的排列顺序。
• 基于位置的编码：直接编码每个零件的坐标和旋转状态。这种方式更直接，但染色体较长，且容易产生大量无效解（重叠或越界）。

在本次P1+P3案例中，为了平衡简单性和有效性，我推荐采用一种混合编码方式：

1. 方案轮廓编码：我们不直接编码每个零件，而是编码一种“排放模式”。例如，决定在木板的长边（3000mm）上，先排放多少排P1（横放），再排放多少排P3（竖放）等等。这实际上是在描述一种排列的规则。
2. 参数编码：将这种模式的关键参数作为染色体。例如，染色体可以是一个四元组 [a, b, c, d]：
   • a: 在木板长度方向上，P1横放排列的个数。
   • b: 在木板长度方向上，紧接着排列的P3横放个数。
   • c: 在木板宽度方向上，P1竖放排列的行数。
   • d: 在木板宽度方向上，P3竖放排列的行数。

这种编码方式极大地缩小了搜索空间，因为它隐式地假设了排列是规则的行列式布局。虽然可能错过一些极其不规则的最优解，但能快速找到利用率很高的可行解，且解码非常简单快速，非常适合竞赛时间限制。

解码与适应度计算示例： 假设一个染色体为 [3, 2, 1, 0]。

• 解码步骤1：在木板长边（3000）上，尝试放置3个横放的P1（长373）和2个横放的P3（长406）。计算总长度 3*373 + 2*406 = 1119 + 812 = 1931mm，小于3000，可行。这构成一行。
• 解码步骤2：根据宽度方向参数，P1竖放行数c=1，P3竖放行数d=0。这意味着我们只有一行P1竖放？这里需要根据编码定义来协调。实际上，更合理的解码是：a和b决定了一行内产品的数量和组合，c和d可能决定了这种行能重复多少层，或者代表另一种排放方式。我们需要明确定义。

为了避免混淆，让我们定义一个更清晰、易于实现的双层编码染色体结构：

# 染色体结构示例：一个包含多个“排放条带”的列表
# 每个“条带”是一个字典，描述如何填充木板的一行或一列
chromosome = [
    {'type': 'row', 'pattern': ['P1_h', 'P1_h', 'P3_h'], 'repeat': 2},
    {'type': 'row', 'pattern': ['P3_v', 'P3_v'], 'repeat': 1},
]

当然，在真实遗传算法中，我们需要用更紧凑的数值来表示。一个实用的竞赛编码是：使用变长整数序列，每两个数字表示一个“块”。例如，[1, 4, 3, 2] 表示“放置1个横放P1，然后放置4个横放P3，然后放置3个竖放P1，然后放置2个竖放P3”，解码器按顺序尝试放置，放不下则开始新的一行，直到木板空间用尽或所有“指令”执行完毕。

适应度函数（Fitness Function）就是我们要最大化的目标，这里自然是木板利用率，即已放置零件总面积与木板总面积之比。解码过程中，只要能合法放置（不重叠不越界），就累加面积。最终，适应度 = 已放置总面积 / (3000*1500)。

3. 算法核心操作：选择、交叉与变异的实战技巧

有了编码和适应度函数，遗传算法的主循环就可以展开了。这个过程包括初始化种群、迭代进化。

初始化种群：随机生成一定数量（如50或100）的染色体。对于我们的整数序列编码，可以随机生成序列长度，再随机填充产品类型和放置方向的代码。确保每个随机方案都能通过解码器生成一个合法的放置（哪怕放得很少），否则给予极低的适应度。

选择（Selection）：目的是从当前种群中选出较优的个体作为父代，用于产生下一代。常用轮盘赌选择或锦标赛选择。

• 轮盘赌：每个个体被选中的概率与其适应度成正比。适应度高的个体，在轮盘上占的面积大，被选中的概率就高。
• 锦标赛选择：随机从种群中抽取k个个体（如k=3），选择其中适应度最高的一个作为父代。重复此过程直到选够所需数量。这种方法选择压力更大，更容易保留优秀基因。

在MATLAB中，锦标赛选择实现起来很直观：

function parents = tournamentSelection(population, fitness, tournamentSize)
    popSize = length(population);
    parents = cell(1, popSize);
    for i = 1:popSize
        candidates = randperm(popSize, tournamentSize);
        [~, bestIdx] = max(fitness(candidates));
        parents{i} = population{candidates(bestIdx)};
    end
end

交叉（Crossover）：模拟生物的有性繁殖，将两个父代染色体的部分结构进行交换，生成子代。这是产生新方案的主要手段。对于序列编码，常用的有单点交叉、两点交叉或均匀交叉。

• 单点交叉：随机选择一个交叉点，将两个父代序列在此点切开并交换后半部分。

父代A: [1,4,3,2,5]
父代B: [2,1,3,4,1,2]
交叉点: 3
子代A: [1,4,3,4,1,2]
子代B: [2,1,3,2,5]

注意，交叉后序列长度可能变化，这正好可以探索不同复杂度的排放模式。

变异（Mutation）：以较小概率随机改变染色体上的某些基因，引入新的多样性，避免算法陷入局部最优。变异操作可以包括：

• 替换：随机选择一个基因位，将其值变为另一个有效的随机值。
• 插入：在随机位置插入一个新的“产品-方向”对。
• 删除：随机删除一个基因位。
• 交换：随机交换两个基因位的位置。

变异概率通常设置得较低（如0.01到0.1），以免破坏好的构建块。

一个完整的遗传算法迭代流程如下表所示：

步骤	操作	目的	关键参数/技巧
1	初始化	生成随机解，覆盖搜索空间	种群大小（50-200）
2	评估	计算每个个体的适应度（利用率）	适应度函数设计需快速准确
3	选择	根据适应度挑选优秀父代	锦标赛规模（k=3常用）
4	交叉	组合父代基因产生新子代	交叉概率（0.7-0.9）
5	变异	对子代进行小幅随机改动	变异概率（0.01-0.1）
6	更新	用新子代（或精英保留）替换旧种群	精英保留策略（保留前几名）
7	循环	重复2-6步，直到满足终止条件	最大代数或收敛判断

4. MATLAB与Python双实现：从代码到结果分析

理论说得再多，不如一行代码。下面我将分别给出在MATLAB和Python（使用主流库）中实现该遗传算法核心框架的示例。我们聚焦于单板P1+P3混合切割利用率最高的场景。

4.1 MATLAB 实现核心片段

MATLAB在矩阵运算和快速原型开发方面有优势。这里我们采用固定长度编码简化示例。

%% 遗传算法参数设置
popSize = 100;          % 种群大小
maxGen = 200;           % 最大进化代数
pc = 0.8;               % 交叉概率
pm = 0.05;              % 变异概率
chromLength = 10;       % 染色体长度（每个基因代表一个产品放置决策）

% 产品尺寸 (长, 宽)
P1 = [373, 201];
P3 = [406, 229];
board = [3000, 1500];

%% 初始化种群
% 染色体：每个基因用1-4编码，1:P1横放，2:P1竖放，3:P3横放，4:P3竖放
population = randi([1,4], popSize, chromLength);

bestFitnessHistory = zeros(maxGen, 1); % 记录历代最佳适应度

for gen = 1:maxGen
    %% 评估适应度
    fitness = zeros(popSize, 1);
    for i = 1:popSize
        fitness(i) = evaluateFitness(population(i,:), P1, P3, board);
    end
    
    [bestFit, bestIdx] = max(fitness);
    bestFitnessHistory(gen) = bestFit;
    bestIndividual = population(bestIdx, :);
    
    %% 选择（锦标赛选择）
    newPopulation = zeros(size(population));
    for i = 1:popSize
        candidates = randperm(popSize, 3); % 锦标赛规模为3
        [~, winIdx] = max(fitness(candidates));
        newPopulation(i, :) = population(candidates(winIdx), :);
    end
    
    %% 交叉（单点交叉）
    for i = 1:2:popSize-1
        if rand < pc
            cp = randi([1, chromLength-1]); % 交叉点
            temp = newPopulation(i, cp+1:end);
            newPopulation(i, cp+1:end) = newPopulation(i+1, cp+1:end);
            newPopulation(i+1, cp+1:end) = temp;
        end
    end
    
    %% 变异（位点变异）
    for i = 1:popSize
        for j = 1:chromLength
            if rand < pm
                newPopulation(i, j) = randi([1,4]);
            end
        end
    end
    
    %% 精英保留：将上一代最好的个体直接替换新一代最差的个体
    [~, worstIdx] = min(fitness);
    newPopulation(worstIdx, :) = bestIndividual;
    
    population = newPopulation;
    
    % 显示进度
    fprintf('代数 %d: 最佳利用率 = %.4f%%\n', gen, bestFit*100);
end

%% 输出最终结果
fprintf('\n最优切割方案编码: ');
disp(bestIndividual);
fprintf('预计木板利用率: %.4f%%\n', bestFitnessHistory(end)*100);

% 绘制进化曲线
figure;
plot(1:maxGen, bestFitnessHistory*100, 'LineWidth', 2);
xlabel('进化代数');
ylabel('最佳利用率 (%)');
grid on;
title('遗传算法优化进程');

其中，evaluateFitness 函数是关键的解码器，需要你根据编码方案仔细实现。它需要模拟放置过程，计算总面积。这里提供一个极简的、基于顺序放置且不考虑复杂排样的解码思路：

function util = evaluateFitness(chromosome, P1, P3, board)
    % 简化解码器：假设按染色体顺序，从左到右、从上到下尝试放置
    % 使用“左下角”贪心放置策略
    % 注意：这是一个非常简化的版本，实际竞赛中需要更精细的几何冲突检测
    totalArea = 0;
    boardW = board(1); boardH = board(2);
    % 初始化放置区域（这里简化处理，实际应用更复杂的几何算法）
    % 此处仅为示意，你需要实现一个真正的二维排样算法，如基于临界多边形的NFDH、FFDH等
    % 对于竞赛，可以假设规则行列排列来快速估算上界
    [~, util] = simplePacking(chromosome, P1, P3, boardW, boardH);
end

4.2 Python 实现核心片段（使用DEAP库）

Python的DEAP库是进行进化计算的强大工具，可以让我们更专注于算法逻辑而非底层结构。

import random
import numpy as np
from deap import base, creator, tools, algorithms

# 问题参数
P1 = (373, 201)  # (长, 宽)
P3 = (406, 229)
BOARD = (3000, 1500)
CHROM_LENGTH = 8

# 1. 定义问题类型：最大化适应度
creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", list, fitness=creator.FitnessMax)

# 2. 初始化工具盒
toolbox = base.Toolbox()
# 定义基因：1-4代表不同产品和方向
toolbox.register("attr_gene", random.randint, 1, 4)
# 定义个体：由CHROM_LENGTH个基因组成
toolbox.register("individual", tools.initRepeat, creator.Individual,
                 toolbox.attr_gene, n=CHROM_LENGTH)
# 定义种群
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

# 3. 定义评估函数（解码与适应度计算）
def evaluate(individual):
    """
    评估函数：将染色体解码为切割方案，计算木板利用率。
    这里同样需要你实现一个具体的解码排样算法。
    此处返回一个元组（适应度,），DEAP要求如此。
    """
    # 解码过程占位符
    # 假设我们有一个函数 decode_and_calc_area(individual, P1, P3, BOARD)
    # total_area = decode_and_calc_area(individual, P1, P3, BOARD)
    # utilization = total_area / (BOARD[0] * BOARD[1])
    
    # 为了示例能运行，这里用一个模拟的适应度函数：
    # 简单地将染色体中代表P3的基因（3,4）数量多给予更高评价（因为P3面积大）
    p3_count = sum(1 for g in individual if g in (3, 4))
    p1_count = sum(1 for g in individual if g in (1, 2))
    # 这是一个非常粗糙的代理适应度，实际必须用真实的几何排样计算面积
    simulated_area = p1_count * P1[0]*P1[1] + p3_count * P3[0]*P3[1]
    board_area = BOARD[0] * BOARD[1]
    utilization = min(simulated_area / board_area, 1.0)  # 防止超过1
    return (utilization,)

toolbox.register("evaluate", evaluate)

# 4. 定义遗传算子
toolbox.register("mate", tools.cxTwoPoint)  # 两点交叉
toolbox.register("mutate", tools.mutUniformInt, low=1, up=4, indpb=0.05) # 均匀整数变异
toolbox.register("select", tools.selTournament, tournsize=3) # 锦标赛选择

# 5. 主算法流程
def main():
    random.seed(42)
    pop = toolbox.population(n=100)  # 种群大小100
    hof = tools.HallOfFame(1)       # 保留历代最佳个体
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("avg", np.mean)
    stats.register("max", np.max)
    
    # 运行进化算法
    pop, logbook = algorithms.eaSimple(pop, toolbox, cxpb=0.7, mutpb=0.2,
                                       ngen=200, stats=stats, halloffame=hof,
                                       verbose=True)
    
    # 输出结果
    best_ind = hof[0]
    print(f"\n最优个体: {best_ind}")
    print(f"最优适应度: {best_ind.fitness.values[0]:.4%}")
    
    return pop, logbook, hof

if __name__ == "__main__":
    main()

提示：无论是MATLAB还是Python，上面代码中的 evaluateFitness 或 evaluate 函数都是核心难点。在真实竞赛中，你需要投入大量精力设计一个高效的解码器。一个折中的竞赛策略是：采用基于“条带”的简化排样。例如，将木板划分为若干水平条带，在每个条带内只放置一种方向的产品，并紧密排列。这样解码速度快，虽然可能不是最优，但通常能得到利用率很高的可行解，非常适合在遗传算法中快速评估成千上万个个体。

5. 进阶优化与竞赛策略：超越基础遗传算法

实现了一个能运行的遗传算法只是第一步。要想在竞赛中脱颖而出，你需要展示对算法的深度理解和优化能力。

参数调优：遗传算法的表现严重依赖于参数。不要只使用默认值。

• 种群大小：太小则多样性不足，容易早熟；太大则计算慢。对于切割问题，100-200是个不错的起点。
• 交叉与变异概率：高交叉概率（0.7-0.9）促进基因混合，高变异概率（0.05-0.2）在后期有助于跳出局部最优。可以尝试自适应参数，随着进化代数增加而降低变异率。
• 选择压力：锦标赛规模k越大，选择压力越大，收敛越快但也更容易早熟。

混合算法：将遗传算法与其他方法结合是高级技巧。

1. 遗传算法 + 局部搜索：在遗传算法每一代结束后，对优秀个体进行局部搜索微调。例如，随机交换两个零件的位置或旋转方向，如果变好则接受。
2. 遗传算法 + 启发式解码：在解码染色体时，不采用简单的顺序放置，而采用更高级的启发式排样算法，如最低水平线算法（Bottom-Left） 或其变种。这能极大提升单个染色体的表现。
3. 两阶段求解：第一阶段用遗传算法快速确定产品大致的数量组合比例；第二阶段针对这个比例，用线性规划或精确算法进行微调排列。

处理复杂约束与多目标：

• 多产品、多订单：染色体需要编码多种产品的组合。适应度函数可能变为“总木板利用率”或“总利润”。
• 一刀切约束：如果题目要求是“一刀切”切割（Guillotine Cutting），即每次切割必须贯穿整块板材，那么你的解码器必须模拟这种切割过程，遗传算法的编码也需要相应调整。
• 多目标优化：有时需要同时考虑利用率最高和切割工艺最简单（切割次数少）。这时可以使用多目标遗传算法（如NSGA-II），得到一组帕累托最优解供决策。

结果验证与对比分析： 在论文中，一定要将遗传算法的结果与其他方法对比。

• 与线性规划松弛解对比：线性规划忽略整数约束得到的解是理论上的上界，你的遗传算法结果有多接近这个上界？
• 与简单启发式规则对比：如“先放大的，再放小的”贪心算法。展示遗传算法的提升。
• 做敏感性分析：改变遗传算法的参数（种群数、代数），观察结果稳定性和收敛速度。用图表展示进化过程。

最后，在论文写作中，将你的遗传算法设计清晰地用流程图或伪代码展示，并对关键组件（编码、解码、适应度、算子）进行详细说明。给出核心代码片段，但不必全部粘贴。重点分析算法的有效性（结果好坏）和效率（计算时间），证明它适合解决此类规模的问题。

纸上得来终觉浅，绝知此事要躬行。打开你的MATLAB或Python，把上面的框架搭起来，把最关键的解码函数实现出来，哪怕一开始只是一个简单的规则排列。运行起来，看着利用率随着一代代进化而提升，你会对遗传算法解决复杂优化问题的威力有最直观的感受。在竞赛中遇到类似的资源分配、路径规划、调度安排问题时，你就能多一件得心应手的武器。