基于遗传算法二维下料问题/矩形件排样/matlab程序

2024-03-14 05:10

本文主要是介绍基于遗传算法二维下料问题/矩形件排样/matlab程序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

基于遗传算法的二维板材切割下料优化问题/matlab程序

关键词: 遗传算法, 二维板材切割, matlab

引言

二维板材切割问题在实际的工程中有很多的应用,该问题基本等同于矩形件优化排样,具体是指将若干尺寸不相同的矩形零件在给定的矩形板材上以最优的方式排布,要求所有待排零件都必须排放在板材内,且各个零件之间不发生重叠,并满足一定的工艺要求.排样问题普遍存在于工程领域中,如钣金下料、玻璃切割、造船、车辆、家具生产、报刊排版、服装和皮革裁剪等.最优的排样方案可以最大限度地节约材料、提高材料利用率,在经济上制造可观的效益.排样问题属于典型的组合优化问题,从理论上讲,该类问题属于具有最高计算复杂性的优化计算问题,即 NP完全问题.对于 NP完全问题,以目前计算理论和方法,在可行的时间界限内不可能找到问题的最优解,只能求其局部最优的近似解.
遗传算法是一种全局随机搜索算法,它借鉴了生物界的自然选择思想和自然遗传机制,将问题的可行解构成种群,把每一个可能的解看作种群的个体,算法运行时在整个解空间里随机搜索,并按一定的评估策略(或适应度函数)对每一个个体做出评价,然后不断地使用选择、交叉、变异3个遗传算子来进化问题的解,直至产生最优解.其优点是:强调概率转移规则,具有快速随机的全局搜索能力,鲁棒性强.缺点是:对于系统中的反馈信息利用不够,当求解到一定范围时往往做大量的冗余迭代,求解效率低。
本文采用遗传算法对二维板材切割/矩形件优化排样问题进行优化求解

遗传算法实现

遗传算法设计如下:

  1. 编码:采用十进制整数编码方式.
  2. 适应度函数:将适应度函数定义为f® = Area / Area1,
    其中,Area是待排入矩形零件的面积总和,Area1是所得排样图高度轮廓线以下的矩形板材面积.
  3. 初始种群:使用随机函数来生成一定数量的十进制整数序列组成父辈群体,设定种群规模 M=50.
  4. 交叉算子:采用单点交叉和双点交叉
    .设置交叉概率pc=1,单点交叉与双点交叉各占一半.
  5. 变异算子:采用位置变异和旋转变异
    .设置位置变异概率pm1=0.1和旋转变异概率pm2=0.1.
  6. 选择算子:根据适应度函数值从大到小排列执行完交叉、变异操作的个体,选择前 M 个个体组成下
    一代父辈群体.
  7. 结 束 条 件:设置迭代多少代.设置maxgen = 200.

流程图

整个算法的流程图,基本如下图所示:
在这里插入图片描述

算例

在一块高10m,宽度没有没有限制的板材上,切割出一定数量的以下两种规格的零件,并使所消耗的板材的宽度最小,或容积利用率最大。

  1. 零件1:高度1m,宽度2m,个数10
  2. 零件2:高度1.5m,宽度2.5m,个数30

Matlab程序

%     Author:    怡宝2号			博士猿工作室
%     淘宝链接:  https://shop437222340.taobao.com/index.htm?spm=2013.1.w5002-16262391244.6.733e1fb4LF2f58%     Use:       用遗传求解二维板材物料切割问题
%                物料参数视自己的具体情况而定。
%     Illustrate:输入变量(must):
%                                initial:零件的相关信息
%                                parameter:板材参数
%
%       Can—changed parameter: 
%                                Option:遗传算法的相关参数
%                                Option.NIND:蚁群的规模
%                                Option.MAXGEN:蚁群的最大迭代代数
%                               
%                  输出:        bestpop:最短路程对应的路径
%                                trace :最短路程
%         remark:如有疑问请咨询qq:778961303clc
clear all
close allformat compact%遗传算法参数:NIND/种群规模;MAXGEN/最大迭代代数;PC/交叉概率;PM/变异概率;GGAP/遗传代沟
Option = struct('NIND',60, 'MAXGEN', 200, 'PC', 0.85, 'PM', 0.1, 'GGAP', 0.8);
Option.w1 = 1; Option.w2 = 0;            %多目标时每个目标函数的比重//没有用到%导入数据
[initial, parameter] = initialFunc();%初始化种群
chrom = initialpop( Option.NIND, initial);%  画出各客户的初始坐标
figure();
Initial_Draw_( chrom(1:2,:), parameter, initial );%结果记录的结构体
Result = struct('mintrace',zeros( Option.MAXGEN,1),'bestpop',[]);
trace =Result;%迭代开始
gen = 1;
while gen<=Option.MAXGEN%计算目标函数[cost, fitness] = CalculateFitness_( chrom, initial, parameter, Option);%选择[selch] = Select(chrom,fitness, Option.GGAP);%随机交叉[selch] = CrossOver(selch, Option.PC);%交换变异selch = ExchangeMutation_(selch, Option.PM);%计算子代的目标函数和适应度[selcost, selfitness] = CalculateFitness_( selch, initial, parameter, Option);%重插入[chrom,cost]=reins_(chrom,selch,1,1,cost,selcost);   %也就是ObjVSel中个体目标函数越小则月容易被选择,按fitval和selfitval来进行选择%结果记录[mincost,index] = min(cost);trace.mintrace(gen) = min(cost);trace.bestpop(gen*2-1:gen*2,:) = chrom(index(1)*2-1:index(1)*2,:);disp(['共迭代',num2str( Option.MAXGEN ),'次,现在为:',num2str(gen)]);gen = gen + 1;
end%绘制寻优迭代图
figure()
plot(trace.mintrace,'--m',...'LineWidth',2);
grid off
xlabel('迭代次数')
ylabel('Cost')
title('遗传寻优','fontsize',16)%显示信息
FuncDisplay(trace);%画出最优下料图
[minvalue minindex] = min(trace.mintrace);
minchrom = trace.bestpop(minindex*2-1:minindex*2,:);
figure();
Final_Draw_( minchrom, parameter, initial );

结果

由结果可以看到,整个优化过程提高了12.785%的容积利用率。结果图如下所示:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

Reference

  1. 融合蚁群算法和遗传算法的矩形件排样问题研究
  2. 矩形件排样问题的遗传算法求解
  3. 遗传算法求解立体仓库货位优化
  4. 基于遗传算法的二维板材切割下料优化问题/矩形件排样/matlab程序

这篇关于基于遗传算法二维下料问题/矩形件排样/matlab程序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/807292

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

poj2576(二维背包)

题意:n个人分成两组,两组人数只差小于1 , 并且体重只差最小 对于人数要求恰好装满,对于体重要求尽量多,一开始没做出来,看了下解题,按照自己的感觉写,然后a了 状态转移方程:dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数,j表示背包容量,k表示输入的体重的 代码如下: #include<iostream>#include<

hdu2159(二维背包)

这是我的第一道二维背包题,没想到自己一下子就A了,但是代码写的比较乱,下面的代码是我有重新修改的 状态转移:dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示,打了i个怪物,消耗j的耐力值,所得到的最大经验值 代码如下: #include<iostream>#include<algorithm>#include<

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

HDU 2159 二维完全背包

FATE 最近xhd正在玩一款叫做FATE的游戏,为了得到极品装备,xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感,但又不得不通过杀怪来升完这最后一级。现在的问题是,xhd升掉最后一级还需n的经验值,xhd还留有m的忍耐度,每杀一个怪xhd会得到相应的经验,并减掉相应的忍耐度。当忍耐度降到0或者0以下时,xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能

EMLOG程序单页友链和标签增加美化

单页友联效果图: 标签页面效果图: 源码介绍 EMLOG单页友情链接和TAG标签,友链单页文件代码main{width: 58%;是设置宽度 自己把设置成与您的网站宽度一样,如果自适应就填写100%,TAG文件不用修改 安装方法:把Links.php和tag.php上传到网站根目录即可,访问 域名/Links.php、域名/tag.php 所有模板适用,代码就不粘贴出来,已经打