别再手动排样了！用Python+遗传算法求解木板最优切割方案（附代码）

智能优化算法在板材切割中的应用：Python遗传算法实战

在制造业数字化转型的浪潮中，如何高效利用原材料、降低生产成本成为企业核心竞争力的关键因素。传统的板材切割方案往往依赖人工经验，不仅效率低下，而且难以实现资源的最优配置。本文将介绍如何利用Python和遗传算法解决这一经典工业优化问题。

1. 二维切割问题的挑战与机遇

二维矩形排样问题（2D Cutting Stock Problem）是制造业中普遍存在的优化难题。该问题要求在给定尺寸的原材料板材上，切割出多种规格的零件，同时满足以下目标：

• 最大化原材料利用率（最小化废料）
• 满足不同零件的生产数量需求
• 考虑切割工艺的可行性约束

传统解决方案通常采用线性规划或混合整数规划方法，如原文中使用的MATLAB/LINGO工具。这些方法虽然能获得精确解，但面临两大局限：

1. 计算复杂度高：当问题规模增大时，求解时间呈指数级增长
2. 灵活性不足：难以应对生产现场的实时变化和复杂约束

# 传统线性规划方法的核心约束示例 from pulp import * prob = LpProblem("Cutting_Stock", LpMinimize) # 定义变量和约束...

相比之下，启发式算法特别是遗传算法，在处理这类NP难问题时展现出独特优势：

2. 遗传算法解决切割问题的原理

遗传算法（Genetic Algorithm, GA）模拟生物进化过程，通过选择、交叉和变异等操作逐步优化解决方案。针对板材切割问题，我们需要设计专门的编码方式和适应度函数。

2.1 染色体编码设计

有效的编码方案是遗传算法成功的关键。对于切割问题，我们采用基于序列的编码：

1. 将所有待切割零件编号
2. 染色体表示零件的排列顺序
3. 通过解码器将序列转换为实际排版方案

# 染色体编码示例 import numpy as np num_parts = 50 # 待切割零件数量 chromosome = np.random.permutation(num_parts) # 生成随机排列 print("示例染色体:", chromosome[:10]) # 显示前10个基因

2.2 适应度函数设计

适应度函数评估解决方案的优劣，对于切割问题通常考虑：

• 原材料利用率（主要优化目标）
• 满足生产需求的程度
• 工艺约束的满足情况

def fitness_function(chromosome, parts, plate_size): """ 计算染色体的适应度值 :param chromosome: 零件排列顺序 :param parts: 零件列表，每个零件包含尺寸和需求数量 :param plate_size: 原材料板材尺寸 (width, height) :return: 适应度值（利用率） """ used_plates = 0 total_area = plate_size[0] * plate_size[1] used_area = 0 # 解码染色体并计算排版（简化示例） # 实际实现需要包含具体的排版算法 for part_id in chromosome: part = parts[part_id] used_area += part['width'] * part['height'] # 简化的利用率计算，实际需要更复杂的排版评估 utilization = used_area / (total_area * used_plates) if used_plates > 0 else 0 return utilization

3. Python实现遗传算法切割优化

我们将使用DEAP（Distributed Evolutionary Algorithms in Python）框架实现遗传算法解决方案。

3.1 环境配置与算法初始化

首先安装必要的库：

pip install deap numpy matplotlib

然后初始化遗传算法基本组件：

from deap import base, creator, tools, algorithms import random # 定义问题类型：最大化适应度 creator.create("FitnessMax", base.Fitness, weights=(1.0,)) creator.create("Individual", list, fitness=creator.FitnessMax) # 初始化工具箱 toolbox = base.Toolbox() # 定义遗传算子 toolbox.register("attr_item", random.randint, 0, num_parts-1) toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_item, n=num_parts) toolbox.register("population", tools.initRepeat, list, toolbox.individual) # 注册评估函数 toolbox.register("evaluate", fitness_function) # 注册遗传操作 toolbox.register("mate", tools.cxPartialyMatched) toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.05) toolbox.register("select", tools.selTournament, tournsize=3)

3.2 解码器与排版算法实现

解码器负责将染色体转换为实际排版方案。这里我们采用最低水平线算法（Bottom-Left）作为基础：

def decode_chromosome(chromosome, parts, plate_width, plate_height): """ 将染色体解码为实际排版方案 :return: (使用的板材数, 每块板材的排版方案) """ placements = [] # 存储所有板材的排版方案 current_plate = [] used_height = 0 used_width = 0 for part_id in chromosome: part = parts[part_id] # 尝试将零件放入当前板材 if (used_width + part['width'] <= plate_width and used_height + part['height'] <= plate_height): # 可以放入，记录位置 current_plate.append({ 'id': part_id, 'x': used_width, 'y': used_height, 'width': part['width'], 'height': part['height'] }) used_width += part['width'] else: # 无法放入当前行，尝试新行 if used_height + part['height'] <= plate_height: used_width = 0 used_height += part['height'] # 再次尝试放入 if part['width'] <= plate_width: current_plate.append({ 'id': part_id, 'x': 0, 'y': used_height, 'width': part['width'], 'height': part['height'] }) used_width = part['width'] else: # 当前板材已满，使用新板材 placements.append(current_plate) current_plate = [{ 'id': part_id, 'x': 0, 'y': 0, 'width': part['width'], 'height': part['height'] }] used_width = part['width'] used_height = part['height'] if current_plate: placements.append(current_plate) return len(placements), placements

3.3 完整遗传算法流程

将各组件整合，形成完整的优化流程：

def genetic_algorithm_optimization(parts, plate_size, pop_size=100, ngen=50): # 初始化种群 pop = toolbox.population(n=pop_size) # 评估初始种群 fitnesses = list(map(lambda ind: toolbox.evaluate(ind, parts, plate_size), pop)) for ind, fit in zip(pop, fitnesses): ind.fitness.values = fit # 进化循环 for g in range(ngen): # 选择下一代 offspring = toolbox.select(pop, len(pop)) offspring = list(map(toolbox.clone, offspring)) # 应用交叉和变异 for child1, child2 in zip(offspring[::2], offspring[1::2]): if random.random() < 0.7: # 交叉概率 toolbox.mate(child1, child2) del child1.fitness.values del child2.fitness.values for mutant in offspring: if random.random() < 0.2: # 变异概率 toolbox.mutate(mutant) del mutant.fitness.values # 评估新个体 invalid_ind = [ind for ind in offspring if not ind.fitness.valid] fitnesses = map(lambda ind: toolbox.evaluate(ind, parts, plate_size), invalid_ind) for ind, fit in zip(invalid_ind, fitnesses): ind.fitness.values = fit # 更新种群 pop[:] = offspring # 返回最优解 best_ind = tools.selBest(pop, 1)[0] return best_ind

4. 工业应用与性能优化

将遗传算法应用于实际生产环境时，还需要考虑以下关键因素：

4.1 多目标优化

实际生产中往往需要平衡多个目标：

1. 原材料利用率：主要优化目标
2. 切割效率：减少切割路径长度
3. 生产均衡性：避免某些零件过度集中生产

可以通过修改适应度函数实现多目标优化：

def multi_objective_fitness(chromosome, parts, plate_size): utilization = compute_utilization(chromosome, parts, plate_size) cutting_length = compute_cutting_length(chromosome, parts, plate_size) balance = compute_production_balance(chromosome, parts) # 加权求和法处理多目标 return 0.6 * utilization + 0.3 * (1 - cutting_length) + 0.1 * balance,

4.2 算法加速技巧

提高遗传算法效率的实用方法：

• 并行评估：利用多核CPU并行计算适应度
• 自适应参数：根据进化过程动态调整交叉和变异概率
• 局部搜索：在遗传算法中嵌入局部优化启发式

# 使用多进程加速适应度计算 from multiprocessing import Pool def evaluate_parallel(population, parts, plate_size): with Pool() as p: fitnesses = p.starmap(fitness_function, [(ind, parts, plate_size) for ind in population]) return fitnesses

4.3 与MES/ERP系统集成

遗传算法优化模块可以无缝集成到制造执行系统（MES）中：

1. 数据接口：从ERP获取订单需求，从MES获取实时库存
2. 结果输出：生成切割方案和NC代码
3. 动态调整：根据生产现场变化实时重新优化

class CuttingOptimizer: def __init__(self, erp_client, mes_client): self.erp = erp_client self.mes = mes_client def run_optimization(self): # 从ERP获取订单需求 orders = self.erp.get_current_orders() # 从MES获取原材料库存 materials = self.mes.get_material_inventory() # 生成优化问题实例 problem_instance = self._create_problem(orders, materials) # 运行遗传算法优化 best_solution = genetic_algorithm_optimization(problem_instance) # 输出结果到MES self.mes.submit_cutting_plan(best_solution) def _create_problem(self, orders, materials): # 将业务数据转换为优化问题 pass

5. 案例分析与效果对比

我们以家具制造企业的实际数据为例，对比遗传算法与传统方法的性能：

案例参数：

• 原材料板材尺寸：2440mm × 1220mm
• 零件种类：15种
• 总需求数量：200-500件不等

性能对比：

遗传算法在保持较高利用率的同时，显著提高了计算效率，特别适合需求频繁变动的生产环境。

# 结果可视化 import matplotlib.pyplot as plt import matplotlib.patches as patches def visualize_solution(plate, placements): fig, ax = plt.subplots(figsize=(10, 5)) # 绘制板材边界 ax.add_patch(patches.Rectangle( (0, 0), plate['width'], plate['height'], linewidth=2, edgecolor='black', facecolor='none' )) # 绘制每个零件 colors = plt.cm.tab20.colors for i, placement in enumerate(placements): ax.add_patch(patches.Rectangle( (placement['x'], placement['y']), placement['width'], placement['height'], linewidth=1, edgecolor='black', facecolor=colors[i % len(colors)], alpha=0.6 )) ax.text(placement['x'] + placement['width']/2, placement['y'] + placement['height']/2, str(placement['id']), ha='center', va='center') ax.set_xlim(0, plate['width']) ax.set_ylim(0, plate['height']) ax.set_aspect('equal') plt.title('Cutting Layout Visualization') plt.show()