如何实现最小化废料的two dimensional cutting stock problem算法及基材数量计算？

核心思路 #

解决这类问题的关键是把基材数量N和废料率结合成优化目标，要么从最小可能的N开始逐步验证可行性，要么将N直接融入遗传算法的适应度函数，优先最小化N，再优化废料。

具体处理方法 #

1. 先估最小N，逐步迭代验证 #

首先计算所有工件的总面积，除以单块基材的面积后向上取整，得到理论最小N（记为N_min）。然后用遗传算法尝试在N_min块基材内完成所有工件的排版：

• 如果找到可行解（所有工件都能放入，无重叠），直接输出N_min及排版方案；
• 如果多次迭代后仍无可行解，将N加1，重复上述过程，直到找到可行解。

这种方法的优势是目标明确，优先锁定最小N，避免遗传算法在大N范围内无效搜索。

2. 将N融入适应度函数 #

把N作为适应度的核心惩罚项，让遗传算法同时优化N和废料：

• 个体编码：每个个体包含两部分信息：
  • 每个工件的分配：即该工件属于哪一块基材（比如长度等于工件总数的数组，元素值为基材编号）；
  • 每个工件的摆放参数：在对应基材内的坐标(x,y)和旋转状态（是否旋转90度）。
• 适应度函数：设计为 fitness = α * N + β * total_waste_ratio，其中：
  • α 是N的权重系数（要设置得远大于β，比如α=100，β=1），确保优先减少基材数量；
  • total_waste_ratio 是所有基材的废料率平均值（(总基材面积 - 总工件面积)/总基材面积）。
• 选择、交叉、变异操作时，优先保留适应度值更低的个体（因为我们要最小化N和废料）。

代码示例（Python框架） #

以下是简化的遗传算法核心逻辑，聚焦N的处理：

import random

# 问题参数
stock_size = (200, 100)
parts = [
    (20,30) for _ in range(3)
] + [(40,40)] + [(100,20) for _ in range(2)]
part_count = len(parts)

# 计算理论最小N
total_part_area = sum(w*h for w,h in parts)
stock_area = stock_size[0] * stock_size[1]
N_min = (total_part_area + stock_area - 1) // stock_area  # 向上取整

class Individual:
    def __init__(self, n):
        self.n = n  # 当前个体使用的基材数量
        # 编码：每个工件的分配（基材编号）、x、y、是否旋转
        self.assignments = [random.randint(0, n-1) for _ in range(part_count)]
        self.positions = [(random.randint(0, stock_size[0]), random.randint(0, stock_size[1]), random.choice([0,1])) for _ in range(part_count)]
    
    def calculate_fitness(self):
        # 计算每块基材的废料和重叠情况
        stock_usage = [[] for _ in range(self.n)]
        for idx, (assign, (x,y,rot)) in enumerate(zip(self.assignments, self.positions)):
            w, h = parts[idx]
            if rot:
                w, h = h, w
            # 简单碰撞检测（简化版，实际需要更严谨）
            if x + w > stock_size[0] or y + h > stock_size[1]:
                return float('inf')  # 超出边界，适应度设为无穷大
            for (ox, oy, ow, oh) in stock_usage[assign]:
                if not (x + w <= ox or x >= ox + ow or y + h <= oy or y >= oy + oh):
                    return float('inf')  # 重叠，适应度无穷大
            stock_usage[assign].append((x,y,w,h))
        
        # 计算总废料率
        total_used_area = sum(w*h for stock in stock_usage for (x,y,w,h) in stock)
        total_stock_area = self.n * stock_area
        waste_ratio = (total_stock_area - total_used_area) / total_stock_area
        
        # 适应度：优先惩罚多的基材，再惩罚废料
        alpha = 100
        beta = 1
        return alpha * self.n + beta * waste_ratio

# 遗传算法核心流程
def genetic_algorithm(max_n, pop_size=50, generations=100):
    # 初始化种群，从N_min开始尝试
    current_n = N_min
    while current_n <= max_n:
        population = [Individual(current_n) for _ in range(pop_size)]
        for gen in range(generations):
            # 选择（锦标赛选择）
            selected = []
            for _ in range(pop_size):
                candidates = random.sample(population, 3)
                selected.append(min(candidates, key=lambda ind: ind.calculate_fitness()))
            
            # 交叉（简化版：随机交换部分基因）
            offspring = []
            for i in range(0, pop_size, 2):
                parent1 = selected[i]
                parent2 = selected[i+1] if i+1 < pop_size else selected[i]
                child1 = Individual(current_n)
                # 随机交换分配方案的一半
                swap_points = random.sample(range(part_count), part_count//2)
                for idx in swap_points:
                    child1.assignments[idx] = parent2.assignments[idx]
                    child1.positions[idx] = parent2.positions[idx]
                offspring.append(child1)
            
            # 变异（随机修改某个工件的分配或位置）
            for ind in offspring:
                if random.random() < 0.1:
                    # 随机选一个工件修改分配
                    idx = random.randint(0, part_count-1)
                    ind.assignments[idx] = random.randint(0, current_n-1)
                if random.random() < 0.1:
                    # 随机修改位置或旋转
                    idx = random.randint(0, part_count-1)
                    x = random.randint(0, stock_size[0])
                    y = random.randint(0, stock_size[1])
                    rot = random.choice([0,1])
                    ind.positions[idx] = (x,y,rot)
            
            # 更新种群
            population = selected + offspring
            # 检查是否有可行解
            best_ind = min(population, key=lambda ind: ind.calculate_fitness())
            if best_ind.calculate_fitness() != float('inf'):
                print(f"找到可行解，使用基材数量：{current_n}")
                return best_ind
        
        # 当前N下无可行解，N加1
        print(f"N={current_n}无可行解，尝试N={current_n+1}")
        current_n += 1
    return None

# 运行算法
best_solution = genetic_algorithm(max_n=3)

注意事项 #

• 碰撞检测和排版逻辑需要更严谨（示例中是简化版），可以引入更高效的矩形排版算法（比如左下角填充法）来优化个体的初始位置和变异后的位置；
• 权重系数α和β需要根据实际问题调整，确保基材数量的优先级高于废料率；
• 可以加入局部优化，对个体的排版方案进行微调（比如调整工件位置减少废料），提升算法效率。

内容的提问来源于stack exchange，提问作者Lana