基于遗传算法的矩形件排样问题研究

将多种群阶段性杂交遗传算法和基于剩余矩形排样算法结合起来,对矩形件优化排样问题求解.重点讨论算法的关键技术:编码方式和解码方式、适应度函数的构造、遗传算子的选择、交叉、变异操作,并通过实例验证了算法的有效性.     

融合蚁群算法和遗传算法的矩形件排样问题研究

提出融合蚁群算法和遗传算法来求解矩形件排样问题.考虑到蚁群算法和遗传算法各自的优缺点,该融合算法前阶段采用遗传算法获得排样问题的部分优化解,把它作为蚁群算法的初始信息素分布,后阶段利用蚁群算法求得最优排样序列,最后求得最优排样图.计算实例表明:与单一遗传算法相比较,该融合算法可达到更好的排样效果.     

基于小生境遗传算法的矩形件优化排样

将小生境遗传算法应用于计算机辅助排样领域,提出了一种改进的解码算法--高度调整法,将高度调整法和小生境遗传算法相结合,用于求解矩形件排样问题.该方法首先将矩形件的排样问题转化为便于优化求解的排列问题,然后应用小生境遗传算法的全局优化概率搜索能力进行优化求解,优化计算过程中应用高度调整法将排样序列转化为排样图.用该算法对文献中的两个算例进行了求解,结果表明该算法是行之有效的.     

二维矩形件优化排样算法的改进研究

提出了一种基于遗传算法求解矩形件排样的改进方法,通过比较搜寻待排矩形件宽度与最低水平线长度之间的关系来确定零件的排样,并用程序实现了该算法,结果表明这种改进算法是有效的。     

存在表面缺陷原材料的矩形件优化排样问题研究

针对存在表面缺陷原材料的矩形件优化排样问题是一个组合优化问题,提出了一种单亲遗传算法求解方法.研究了将矩形件在板材上的排样转换为遗传算法特定编码的方法,通过单亲遗传算法的遗传算子进行优化搜索,最终得到矩形件排样的最优次序和排放方式,用基于矩形件与板材内靠接临界多边形最低点的排样算法实现在表面存在缺陷原材料上的自动排样.排样实例表明,该优化排样算法行之有效,具有广泛的适应性.     

一种矩形件优化排样综合算法

提出了应用于矩形件优化排样中的关键算法：条料生成算法与填充算法．把二者融合在一起，提出了一种适用于矩形件优化排样的最小残料算法．该算法依据残料大小决定条料，并对空白矩形进行有效填充，可快速得到排样结果．将其与模拟退火算法相结合，能够跳出局部搜索，最终可获得近似总体最优的排样结果．     

改进邻域搜索算法的矩形件排样优化研究

针对矩形件排样问题,给出精确的数学优化模型,提出一种改进邻域搜索算法的求解方法.为了克服一般邻域搜索算法易陷入局部最优解和搜索效率低的缺点,挖掘矩形件排样的问题特征,提出反悔算子、距离受限邻域算子、以"满足容忍度"接受劣解等3种新的改进策略.以矩形件排放顺序为编码,利用"最下左填充算法"进行解码,优化矩形件排样方案.对...     

冲裁件优化排样的多边形顶点射线算法

研究冲裁工件优化排样问题.在普通单排多边形顶点算法的基础上,针对对头单排、普通双排、对头双排3种排样方式的特点,提出一种多边形顶点射线算法.经实际测试证明,该算法克服了多边形顶点算法通用性差的局限,可高效准确地得出常规单件排样方式的最优解.应用改进算法,在AutoCAD2000上,通过ObjectARX2000开发出了冲裁模优化排样系统.应用结果表明,与原手工排样方案相比,节省材料率约10%.     

两阶段启发式算法在矩形件排样中的应用

针对定制式木门家具生产过程中板材资源利用率低和常规启发式排样算法得到的排样结果切割工艺复杂的问题,采用启发式排样和优化排序相结合的方式,提出了两阶段排样方式和遗传算法相结合的组合式矩形板材排样算法。以两阶段排样方式为基础,通过对排样过程中物块摆放时会遇到的5种情况分别给出对应处理方案,提出了两阶段启发式排样算法,同时利用改进的遗传算法进行板材组号的排序优化。测试结果表明,该文算法取得了98.11%的最高资源利用率,算法输出排样方案的板材切割工艺得到了优化,提高了实际生产中板材切割的生产效率并降低了生产与时间成本。     

求解矩形放置问题的亲属帮助遗传算法

用基于几何位置的方法求解矩形放置问题,解空间有限,且包含最优放置,但解空间太大。为了解决这个问题,该文将基于几何位置的序列对算法作为遗传算法的编解码过程,同时根据序列对编码空间中局部最优解相互间保持一定距离的特点,从父代中随机地选出一定比例个体,用这些个体作为排斥体,使子代个体与排斥体都保持一定的距离,有效地避免了种群过早收敛到局部最优解。3组试验表明:这种算法在问题规模小时能有效地搜索到全局最优解;在问题规模较大时,能得到较好的结果。     

求解矩形放置问题的亲属帮助遗传算法

用基于几何位置的方法求解矩形放置问题,解空间有限,且包含最优放置,但解空间太大。为了解决这个问题,将基于几何位置的序列对算法作为遗传算法的编解码过程,同时根据序列对编码空间中局部最优解相互间保持一定距离的特点,从父代中随机地选出一定比例的个体,用这些个体作为排斥体,使子代个体与排斥体都保持一定的距离,有效地避免了种群过早收敛到局部最优解。3组试验表明:这种算法在问题规模小时能有效地搜索到全局最优解;在问题规模较大时,能得到较好的结果。     

求解带平衡约束矩形布局问题的混合算法

以卫星舱布局为背景,针对二维带平衡约束的矩形集在圆容器内的布局问题,提出了一种混合算法,即带压缩策略的动态匹配算法,并与粒子群优化算法结合起来.对于给定的圆容器,将整个布局过程分为4个阶段,相应地将圆容器分成8个区域.每次放置矩形时,动态匹配算法先根据系统质心动态选择装填区域,然后在该装填区域中根据排序函数选择待布矩形.压缩策略用来压缩圆容器,粒子群优化算法用来优化排序函数的参数.在测试集上的计算结果表明:相对于已有算法,提出的混合算法更加有效.     

求解长方体packing问题的拟人算法

为长方体装箱问题的求解提出了拟人算法,旨在将几千年以来中国人的有关生活经验利用西方的数学工具加以形式化并且提高一步.本算法在当今可得的计算环境下,对于现实生活中常遇到的长方体packing问题能够得出合适的空间布局,其空间利用率在已公开发表的国际文献中属于领先的水平.     

一种求解矩形packing问题的智能枚举算法

矩形packing问题有许多工业应用,如码头货物装载,木材下料,超大规模集成电路（VLSI）布局设计,新闻排版等。国内外已提出了许多求解此问题的算法,如：遗传算法,模拟退火算法以及启发式算法等。在目前已有研究的基础上,提出了一种智能枚举算法,该算法的关键在于设计一种快速有效的枚举策略。用Hopper和Turton提出的21个矩形packing实例对所提出的算法性能进行了实算测试,平均面积未利用率为0.04%,平均计算时间为277.69 s,并求得了其中18个实例的最优解。实算结果表明：该算法对求解矩形packing问题是行之有效的。     

二维矩形条带装箱问题的离散化左下角定位模型

分别针对不旋转和可旋转两种情况下的离散化二维矩形条带装箱问题(2DR-SPP),采用各矩形的左下角坐标对矩形的放置点进行定位,建立了两个整数线性规划模型。采用GAMS/CPLEX软件对标杆算例进行求解,验证了所建模型的有效性和准确性。     

An effective evolutionary algorithm for the multiple container packing problem

This paper focuses on a new optimization problem, which is called "The Multiple Container Packing Problem (MCPP)" and proposes a new evolutionary approach for it. The proposed evolutionary approach uses "Adaptive Link Adjustment Evolutionary Algorithm (ALA-EA)" as a basic framework and it incorporates a heuristic local improvement approach into ALA-EA. The first step of the local search algorithm is to raise empty space through the exchange among the packed items and then to improve the fitness value through packing unpacked items into the raised empty space. The second step is to exchange the packed items and the unpacked items one another toward improving the fitness value. The proposed algorithm is compared to the previous evolutionary approaches at the benchmark instances (with the same container capacity) and the modified benchmark instances (with different container capacity) and that the algorithm is proved to be superior to the previous evolutionary approaches in the solution quality.     

An effective evolutionary algorithm for the multiple container packing problem

This paper focuses on a new optimization problem, which is called ＂The Multiple Container Packing Problem （MCPP）＂ and proposes a new evolutionary approach for it. The proposed evolutionary approach uses ＂Adaptive Link Adjustment Evolutionary Algorithm （ALA-EA）＂ as a basic framework and it incorporates a heuristic local improvement approach into ALA-EA. The first step of the local search algorithm is to raise empty space through the exchange among the packed items and then to improve the fitness value through packing unpacked items into the raised empty space. The second step is to exchange the packed items and the unpacked items one another toward improving the fitness value. The proposed algorithm is compared to the previous evolutionary approaches at the bench-mark instances （with the same container capacity） and the modified benchmark instances （with different container capacity） and that the algorithm is proved to be superior to the previous evolutionary approaches in the solution quality.     

一种启发式矩形毛坯带排样算法研究

介绍一种两维矩形毛坯带排样问题的改进启发式递归算法,它基于递归结构和分支定界技术.首先初始化板材作为一个块,考虑目前的块,算法选择一个毛坯,将毛坯放在块的左下角,然后用水平或竖直的剪切线将未使用空间分为两个更小的块,便于进一步递归求解.使用上下界来去除无用的分支,缩短运算时间.将该算法和遗传算法相结合,先通过遗传算法确定所有矩形毛坯较优的排放顺序和排放方式,然后使用递归排样生成排样图,通过比较不同的矩形排放序列对应的板材利用率,最终得到较优的排样方案.测试数据表明了该启发式优化算法的有效性.     

基于空间优化的三维装箱布局混合遗传算法

针对三维装箱问题使用了一种便于空间优化的二维链表结构表达三维矩形物体布局状态空间分解方法和利用混合遗传算法产生待装物体的顺序序列.二维链表结构可以表达空间相连结点之间的关系,易于空间结点的重组,达到更好的利用空间;也可减少产生好的待装物体顺序序列的搜索次数.结合混合遗传算法的搜索方法,能在合理的时间内找到问题的满意解.经过实验表明通过这两种方法的结合本算法能取得较好的较果.