基于遗传算法的矩形排样MATLAB实现
一、矩形排样问题概述
1.1 问题描述
矩形排样问题（Rectangle Packing Problem）是将一组不同尺寸的矩形无重叠地放入一个更大的矩形容器中，目标是最大化容器利用率（即被覆盖面积与容器总面积之比）。该问题在制造业（如钢板切割、玻璃裁切）、物流（货物装箱）等领域有广泛应用。
1.2 问题难点
- NP难问题：随着矩形数量增加，计算复杂度呈指数级增长
- 多约束条件：无重叠、边界约束、旋转可能性
- 解空间巨大：可能的排样方案数量庞大
二、遗传算法设计
2.1 算法框架
graph TD
A[初始化种群] --> B[适应度评估]
B --> C{满足终止条件?}
C -->|否| D[选择操作]
D --> E[交叉操作]
E --> F[变异操作]
F --> B
C -->|是| G[输出最优解]
2.2 关键组件设计
-
染色体编码：
- 排列编码：矩形放置顺序
- 方向编码：矩形是否旋转（0/1）
- 位置编码：矩形左下角坐标(x,y)
-
适应度函数：
![]()
- \(w_i,h_i\)：矩形尺寸
- \(W,H\)：容器尺寸
- \(α\)：面积利用率权重
- \(β\)：重叠惩罚权重
-
遗传操作：
- 选择：锦标赛选择
- 交叉：顺序交叉(OX) + 两点交叉
- 变异：交换变异 + 扰动变异
三、MATLAB代码实现
3.1 主程序框架
function rectangle_packing_ga()
% 基于遗传算法的矩形排样优化
% 清屏与初始化
clc; clear; close all;
% 1. 设置问题参数
params = setup_parameters();
% 2. 初始化种群
population = initialize_population(params);
% 3. GA主循环
[best_individual, fitness_history] = ga_main_loop(population, params);
% 4. 结果可视化
visualize_results(best_individual, fitness_history, params);
% 5. 输出最优解
display_solution(best_individual, params);
end
3.2 参数设置模块
function params = setup_parameters()
% 矩形排样问题参数
params.container_width = 100; % 容器宽度
params.container_height = 100; % 容器高度
params.rectangles = [ % 矩形尺寸 [w, h]
20, 30;
40, 20;
30, 40;
25, 25;
35, 15;
15, 35;
50, 10;
10, 50;
60, 20;
20, 60
];
params.num_rectangles = size(params.rectangles, 1);
% GA参数
params.pop_size = 50; % 种群大小
params.max_generations = 200; % 最大迭代次数
params.elite_ratio = 0.1; % 精英比例
params.crossover_prob = 0.8; % 交叉概率
params.mutation_prob = 0.2; % 变异概率
params.tournament_size = 3; % 锦标赛大小
% 适应度权重
params.alpha = 0.9; % 面积利用率权重
params.beta = 0.1; % 重叠惩罚权重
% 显示参数
params.show_animation = true; % 显示排样动画
params.save_results = true; % 保存结果
end
3.3 种群初始化
function population = initialize_population(params)
% 初始化种群
pop_size = params.pop_size;
n = params.num_rectangles;
population = struct();
for i = 1:pop_size
% 随机排列（放置顺序）
order = randperm(n);
% 随机方向（0:不旋转, 1:旋转90°）
directions = randi([0, 1], 1, n);
% 随机位置（左下角坐标）
positions = rand(1, 2*n) .* [repmat([params.container_width, params.container_height], 1, n)];
% 组合染色体
population(i).chromosome = struct(...
'order', order, ...
'directions', directions, ...
'positions', positions ...
);
% 计算适应度
population(i).fitness = evaluate_fitness(population(i).chromosome, params);
end
end
3.4 适应度评估
function fitness = evaluate_fitness(chromosome, params)
% 评估适应度
n = params.num_rectangles;
rects = params.rectangles;
W = params.container_width;
H = params.container_height;
% 提取染色体信息
order = chromosome.order;
dirs = chromosome.directions;
pos = reshape(chromosome.positions, 2, n)';
% 计算实际使用的矩形尺寸（考虑旋转）
rect_sizes = zeros(n, 2);
for i = 1:n
idx = order(i);
if dirs(i) == 0
rect_sizes(i, :) = rects(idx, :);
else
rect_sizes(i, :) = rects(idx, [2, 1]); % 交换宽高
end
end
% 检查边界约束和重叠
overlap_area = 0;
boundary_violation = 0;
placed_rects = zeros(n, 4); % [x1, y1, x2, y2]
for i = 1:n
x = pos(i, 1);
y = pos(i, 2);
w = rect_sizes(i, 1);
h = rect_sizes(i, 2);
% 检查边界
if x < 0 || y < 0 || x + w > W || y + h > H
boundary_violation = boundary_violation + 1;
end
% 更新矩形坐标
placed_rects(i, :) = [x, y, x + w, y + h];
end
% 检查重叠
for i = 1:n
for j = i+1:n
rect1 = placed_rects(i, :);
rect2 = placed_rects(j, :);
if check_overlap(rect1, rect2)
% 计算重叠面积
x_overlap = max(0, min(rect1(3), rect2(3)) - max(rect1(1), rect2(1)));
y_overlap = max(0, min(rect1(4), rect2(4)) - max(rect1(2), rect2(2)));
overlap_area = overlap_area + x_overlap * y_overlap;
end
end
end
% 计算总面积利用率
total_area = sum(prod(rect_sizes, 2));
container_area = W * H;
area_utilization = total_area / container_area;
% 计算适应度
penalty = boundary_violation * 0.1 + overlap_area / (W*H) * 0.5;
fitness = params.alpha * area_utilization - params.beta * penalty;
% 确保适应度非负
fitness = max(0, fitness);
end
function overlap = check_overlap(rect1, rect2)
% 检查两个矩形是否重叠
overlap = ~(rect1(3) <= rect2(1) || ...
rect1(1) >= rect2(3) || ...
rect1(4) <= rect2(2) || ...
rect1(2) >= rect2(4));
end
3.5 遗传操作
function [new_population] = genetic_operations(population, params)
% 遗传操作：选择、交叉、变异
pop_size = params.pop_size;
elite_size = round(params.elite_ratio * pop_size);
% 1. 精英保留
[~, sorted_indices] = sort([population.fitness], 'descend');
elites = population(sorted_indices(1:elite_size));
% 2. 选择操作（锦标赛选择）
selected = selection(population, params);
% 3. 交叉操作
offspring = crossover(selected, params);
% 4. 变异操作
mutated_offspring = mutation(offspring, params);
% 5. 合并精英和新个体
new_population = [elites; mutated_offspring(1:(pop_size - elite_size))];
end
function selected = selection(population, params)
% 锦标赛选择
pop_size = params.pop_size;
tournament_size = params.tournament_size;
selected = struct();
for i = 1:pop_size
% 随机选择tournament_size个个体
candidates = randperm(pop_size, tournament_size);
candidate_fitness = [population(candidates).fitness];
% 选择适应度最高的个体
[~, best_idx] = max(candidate_fitness);
selected(i) = population(candidates(best_idx));
end
end
function offspring = crossover(parents, params)
% 交叉操作
pop_size = params.pop_size;
n = params.num_rectangles;
offspring = struct();
for i = 1:2:pop_size
parent1 = parents(randi(pop_size));
parent2 = parents(randi(pop_size));
if rand < params.crossover_prob
% 顺序交叉（OX）用于放置顺序
child1_order = ox_crossover(parent1.chromosome.order, parent2.chromosome.order);
child2_order = ox_crossover(parent2.chromosome.order, parent1.chromosome.order);
% 两点交叉用于方向
child1_dirs = two_point_crossover(parent1.chromosome.directions, parent2.chromosome.directions);
child2_dirs = two_point_crossover(parent2.chromosome.directions, parent1.chromosome.directions);
% 算术交叉用于位置
child1_pos = arithmetic_crossover(parent1.chromosome.positions, parent2.chromosome.positions);
child2_pos = arithmetic_crossover(parent2.chromosome.positions, parent1.chromosome.positions);
else
% 不交叉，直接复制父代
child1_order = parent1.chromosome.order;
child1_dirs = parent1.chromosome.directions;
child1_pos = parent1.chromosome.positions;
child2_order = parent2.chromosome.order;
child2_dirs = parent2.chromosome.directions;
child2_pos = parent2.chromosome.positions;
end
% 创建子代
offspring(i).chromosome = struct(...
'order', child1_order, ...
'directions', child1_dirs, ...
'positions', child1_pos ...
);
if i+1 <= pop_size
offspring(i+1).chromosome = struct(...
'order', child2_order, ...
'directions', child2_dirs, ...
'positions', child2_pos ...
);
end
end
end
function mutation(offspring, params)
% 变异操作
pop_size = params.pop_size;
n = params.num_rectangles;
for i = 1:pop_size
if rand < params.mutation_prob
chrom = offspring(i).chromosome;
% 交换变异（放置顺序）
if rand < 0.5
idx = randperm(n, 2);
temp = chrom.order(idx(1));
chrom.order(idx(1)) = chrom.order(idx(2));
chrom.order(idx(2)) = temp;
end
% 翻转变异（方向）
if rand < 0.3
idx = randi(n);
chrom.directions(idx) = 1 - chrom.directions(idx);
end
% 扰动变异（位置）
if rand < 0.4
idx = randi(n);
chrom.positions(2*idx-1:2*idx) = chrom.positions(2*idx-1:2*idx) + randn(1,2)*5;
end
% 更新染色体
offspring(i).chromosome = chrom;
% 重新计算适应度
offspring(i).fitness = evaluate_fitness(chrom, params);
end
end
end
% 辅助交叉函数
function child = ox_crossover(parent1, parent2)
n = length(parent1);
start = randi(n-1);
end_idx = randi(start+1, 1, 1);
segment = parent1(start:end_idx);
remaining = parent2(~ismember(parent2, segment));
child = [remaining(1:start-1), segment, remaining(start:end)];
end
function child = two_point_crossover(parent1, parent2)
n = length(parent1);
points = sort(randi(n, 1, 2));
child = parent1;
child(points(1):points(2)) = parent2(points(1):points(2));
end
function child = arithmetic_crossover(parent1, parent2)
alpha = rand;
child = alpha * parent1 + (1 - alpha) * parent2;
end
3.6 GA主循环
function [best_individual, fitness_history] = ga_main_loop(population, params)
% GA主循环
pop_size = params.pop_size;
max_gen = params.max_generations;
fitness_history = zeros(max_gen, 1);
best_individual = population(1);
best_fitness = population(1).fitness;
for gen = 1:max_gen
% 评估适应度
for i = 1:pop_size
population(i).fitness = evaluate_fitness(population(i).chromosome, params);
end
% 更新最佳个体
[current_best_fitness, idx] = max([population.fitness]);
if current_best_fitness > best_fitness
best_fitness = current_best_fitness;
best_individual = population(idx);
end
% 记录适应度历史
fitness_history(gen) = best_fitness;
% 显示迭代信息
if mod(gen, 10) == 0
fprintf('Generation %d: Best Fitness = %.4f, Utilization = %.2f%%\n', ...
gen, best_fitness, best_fitness * 100);
end
% 遗传操作
population = genetic_operations(population, params);
end
end
3.7 结果可视化
function visualize_results(best_individual, fitness_history, params)
% 可视化结果
if params.show_animation
figure('Name', '矩形排样优化过程', 'NumberTitle', 'off');
set(gcf, 'Position', [100, 100, 1200, 800]);
end
% 1. 适应度曲线
figure('Name', '适应度进化曲线', 'NumberTitle', 'off');
plot(1:length(fitness_history), fitness_history, 'LineWidth', 2);
xlabel('迭代次数');
ylabel('最佳适应度');
title('遗传算法优化过程');
grid on;
% 2. 最优排样方案
figure('Name', '最优排样方案', 'NumberTitle', 'off');
show_packing(best_individual.chromosome, params);
% 3. 保存结果
if params.save_results
save('GA_Rectangle_Packing_Result.mat', 'best_individual', 'params', 'fitness_history');
saveas(gcf, 'Optimal_Packing.png');
end
end
function show_packing(chromosome, params)
% 显示排样方案
n = params.num_rectangles;
rects = params.rectangles;
W = params.container_width;
H = params.container_height;
% 提取染色体信息
order = chromosome.order;
dirs = chromosome.directions;
pos = reshape(chromosome.positions, 2, n)';
% 创建图形
clf;
axis equal;
axis([0 W 0 H]);
rectangle('Position', [0, 0, W, H], 'EdgeColor', 'b', 'LineWidth', 2);
hold on;
title('最优矩形排样方案');
xlabel('宽度');
ylabel('高度');
% 绘制所有矩形
colors = lines(n);
total_area = 0;
for i = 1:n
idx = order(i);
x = pos(i, 1);
y = pos(i, 2);
if dirs(i) == 0
w = rects(idx, 1);
h = rects(idx, 2);
else
w = rects(idx, 2);
h = rects(idx, 1);
end
% 绘制矩形
rectangle('Position', [x, y, w, h], ...
'FaceColor', colors(i, :), 'EdgeColor', 'k', 'LineWidth', 1.5);
% 添加标签
text(x + w/2, y + h/2, num2str(idx), ...
'HorizontalAlignment', 'center', 'FontWeight', 'bold');
% 累计面积
total_area = total_area + w * h;
end
% 计算并显示利用率
utilization = total_area / (W * H) * 100;
text(W/2, H+5, sprintf('容器利用率: %.2f%%', utilization), ...
'HorizontalAlignment', 'center', 'FontSize', 12, 'FontWeight', 'bold');
% 添加图例
legend('容器', '矩形', 'Location', 'bestoutside');
hold off;
end
3.8 输出最优解
function display_solution(best_individual, params)
% 输出最优解
n = params.num_rectangles;
rects = params.rectangles;
W = params.container_width;
H = params.container_height;
% 提取染色体信息
order = best_individual.chromosome.order;
dirs = best_individual.chromosome.directions;
pos = reshape(best_individual.chromosome.positions, 2, n)';
% 计算实际使用的矩形尺寸
rect_sizes = zeros(n, 2);
for i = 1:n
idx = order(i);
if dirs(i) == 0
rect_sizes(i, :) = rects(idx, :);
else
rect_sizes(i, :) = rects(idx, [2, 1]);
end
end
% 计算总面积利用率
total_area = sum(prod(rect_sizes, 2));
utilization = total_area / (W * H) * 100;
% 显示结果
fprintf('\n===== 最优排样方案 =====\n');
fprintf('容器尺寸: %d × %d\n', W, H);
fprintf('矩形数量: %d\n', n);
fprintf('总面积: %.2f\n', total_area);
fprintf('容器利用率: %.2f%%\n', utilization);
fprintf('----------------------------\n');
fprintf('矩形\t位置(x,y)\t尺寸(w×h)\t旋转\t面积\n');
for i = 1:n
idx = order(i);
x = pos(i, 1);
y = pos(i, 2);
w = rect_sizes(i, 1);
h = rect_sizes(i, 2);
rot = dirs(i);
area = w * h;
fprintf('%2d\t(%5.1f,%5.1f)\t%3d×%-3d\t%s\t%.1f\n', ...
idx, x, y, w, h, string(rot), area);
end
fprintf('============================\n');
end
参考代码 基于遗传算法的矩形排样 www.youwenfan.com/contentcns/70810.html
四、算法优化与扩展
4.1 混合优化策略
function improved_fitness = hybrid_optimization(chromosome, params)
% 混合优化：GA + 局部搜索
base_fitness = evaluate_fitness(chromosome, params);
% 局部搜索：微调位置
improved_chromosome = local_search(chromosome, params);
improved_fitness = evaluate_fitness(improved_chromosome, params);
% 如果局部搜索效果更好，则替换
if improved_fitness > base_fitness
chromosome = improved_chromosome;
base_fitness = improved_fitness;
end
end
function improved_chromosome = local_search(chromosome, params)
% 局部搜索：微调矩形位置
n = params.num_rectangles;
improved_chromosome = chromosome;
pos = reshape(chromosome.positions, 2, n)';
for i = 1:n
original_pos = pos(i, :);
best_pos = original_pos;
best_fitness = evaluate_partial_fitness(improved_chromosome, i, params);
% 尝试8个方向的小范围移动
for dx = [-1, 0, 1]
for dy = [-1, 0, 1]
if dx == 0 && dy == 0
continue;
end
new_pos = original_pos + [dx, dy]*0.5;
improved_chromosome.positions(2*i-1:2*i) = new_pos;
new_fitness = evaluate_partial_fitness(improved_chromosome, i, params);
if new_fitness > best_fitness
best_fitness = new_fitness;
best_pos = new_pos;
end
end
end
% 保留最佳位置
improved_chromosome.positions(2*i-1:2*i) = best_pos;
end
end
4.2 多种群协同进化
function multi_population_ga()
% 多种群协同进化GA
num_pops = 3; % 种群数量
migration_interval = 10; % 迁移间隔
migration_rate = 0.1; % 迁移率
% 初始化多个种群
populations = cell(1, num_pops);
for p = 1:num_pops
populations{p} = initialize_population(params);
end
% 主循环
for gen = 1:max_gen
for p = 1:num_pops
% 评估、选择、交叉、变异
populations{p} = genetic_operations(populations{p}, params);
end
% 定期迁移
if mod(gen, migration_interval) == 0
populations = migrate(populations, migration_rate);
end
end
end
function new_pops = migrate(populations, rate)
% 种群间迁移
num_pops = length(populations);
new_pops = populations;
for p = 1:num_pops
next_p = mod(p, num_pops) + 1; % 环形拓扑
% 选择迁移个体
num_migrants = round(rate * length(populations{p}));
migrants = randperm(length(populations{p}), num_migrants);
% 迁移个体
new_pops{next_p}(end-num_migrants+1:end) = populations{p}(migrants);
end
end
五、应用案例
5.1 钢板切割优化
function steel_plate_cutting()
% 钢板切割优化案例
params = setup_parameters();
% 设置钢板尺寸 (mm)
params.container_width = 3000;
params.container_height = 1500;
% 设置零件尺寸 (mm)
params.rectangles = [
500, 400;
600, 300;
400, 450;
300, 600;
700, 250;
250, 700;
800, 200;
200, 800;
450, 350;
350, 450
];
% 运行GA优化
rectangle_packing_ga();
end
5.2 家具板材排版
function furniture_layout()
% 家具板材排版案例
params = setup_parameters();
% 设置板材尺寸 (mm)
params.container_width = 2440; % 标准板材宽度
params.container_height = 1220; % 标准板材高度
% 设置家具部件尺寸 (mm)
params.rectangles = [
600, 400; % 抽屉面板
400, 300; % 侧板
800, 500; % 顶板
300, 200; % 隔板
500, 600; % 背板
200, 150; % 小配件
700, 400; % 门板
400, 400; % 装饰条
1000, 300; % 台面
300, 1000 % 立板
];
% 运行GA优化
rectangle_packing_ga();
end
六、总结与展望
6.1 算法优势
- 全局搜索能力强：避免陷入局部最优
- 灵活性高：可处理不同形状、尺寸的矩形
- 并行性好：适合大规模问题
- 鲁棒性强：对初始解不敏感
6.2 应用前景
- 智能制造：优化材料利用率
- 物流运输：提高集装箱装载率
- 建筑设计：优化空间布局
- VLSI设计：芯片布局优化
6.3 未来方向
- 三维排样：扩展到三维装箱问题
- 动态排样：处理实时变化的排样需求
- 多目标优化：同时优化材料利用率和切割难度
- 机器学习增强：用深度学习指导初始种群生成
浙公网安备 33010602011771号