智能优化排料方法研究

【作者】 韩珂；

【导师】 孙怀江；

【作者基本信息】 南京理工大学 ， 计算机应用技术， 2009， 硕士

【摘要】 二维不规则排料问题是指,将一系列形状各异的待排件排放在给定材料上,找出使材料的利用率最高的方案,减少原材料的浪费。排料优化问题是NP完全问题,在许多工业制造和生产领域都有着重要的应用,也是研究的热点。本文给出了二维不规则排料的分层实现:最上层是负责排料布局过程整体优化的智能优化算法,它确定了各个不规则待排件的排放次序、旋转角度和镜像方式;接着是负责排料组织工作的启发式BLF算法,它将排放次序、旋转角度和镜像方式确定了的不规则待排件逐个放入面料,进行排放;然后是不规则待排件的并靠判交算法以及负责实现不规则待排件面积计算、旋转、镜像、移动等操作的几何计算算法;最底层是不规则待排件的几何表达方法,即栅格水平线扫描区间表示法。对每层一一进行了实现和阐述。对于负责排料过程整体优化的智能优化算法,本文选取了遗传算法、模拟退火算法、遗传模拟退火算法和粒子群优化算法应用到二维不规则排料问题中。将一种基于惯性权值凹函数递减策略的粒子群优化算法引入优化排料领域,与基于惯性权值线性递减策略的粒子群优化算法相比较,提高了面料利用率。针对在迭代后期容易陷入局部最优这一现象,本文提出了一种改进的基于粒子位移邻域变异的粒子群优化算法,与惯性权值递减策略相结合,形成基于粒子位移邻域变异惯性权值递减策略的粒子群优化算法,并将之应用到排料过程,与两种基于惯性权值递减策略的粒子群优化算法对比,提高了面料利用率。最后对各智能优化算法在排料中的应用效果进行了多次实验,展示了排料效果图,对实验数据进行定量对比分析,得出如下结论:(1)智能优化算法的排料效果均优于启发式直接排料;(2)智能优化算法中粒子群系列算法和模拟退火算法在排料效果上都比较好。模拟退火算法迭代过程完成后有时会取得非常好的效果,但也会有比较差的结果出现,这种情况随着迭代次数的增加有所改善;而粒子群系列算法在每次迭代完成后表现都很稳定,效果也好;(3)综合来看,基于粒子位移邻域变异惯性权值凹函数递减策略的粒子群优化算法排料效果最好。更多还原

【Abstract】 Given a set of irregular shapes, the two-dimensional irregular nesting problem is a problem of packing the shapes within a sheet and trying to find the best arrangement that could maximize the utilization of materials, and minimize the wastage of raw materials. The problem is NP-hard even when the shapes and the material involved are rectangles. It impacts upon a wide variety of industrial applications and motivates many areas of research.This paper gives a general view of the irregular nesting procedure by dividing it into several layers. The top-level is the intelligent optimal algorithms. They are in charge of the overall effect of the nesting procedure by ways of generating the best nesting order, rotating angle and mirroring way of every irregular shape. The next one would be the Bottom-Left-Fill heuristic algorithm which organizes the nesting procedure, putting the shapes onto the sheet one by one using BLF strategy. What comes next are the algorithm for judging whether the shapes intersect with each other, and the computational geometry methods for irregular polygons such as calculating area, rotating, mirroring, and shifting. The bottom layer is the geometric representation method for irregular shapes, approximating the irregular shapes by horizontal scan-lines, and representing them by sets of intervals.With regard to the intelligent optimal algorithms in charge of the overall nesting process, this paper selects the genetic algorithm, simulated annealing algorithm, genetic simulated annealing algorithm and particle swarm optimization algorithm to generate the best nesting order, rotating angle and mirroring way for every irregular shapes. Besides, the paper introduces a two-dimensional irregular shapes nesting process based on a concave function strategy for decreasing inertia weight swarm optimization algorithm. To avoid the problem of trapping into local optimum at the end of the iterative process, this paper proposes an improved swarm optimization algorithm based on a kind of swarm position neighborhood mutation, and applies it to the nesting field with the combination of the decreasing inertia weight strategy. Compare with the other two decreasing inertia weight swarm optimization algorithms, this one brings out a higher material utilization rate.Finally experiments are made to compare and quantitatively analyze the different results of these intelligent optimal algorithms, and the corresponding conclusion is drawn as following: (1) The nesting results of intelligent optimal algorithms are all better than those of traditional heuristic algorithm; (2) Among the intelligent optimal algorithms, both the particle swarm optimization algorithm and simulated annealing algorithm could give a satisfying nesting result. For the simulated annealing algorithm, perfect results happen occasionally, and so do bad ones. Nevertheless, the results will generally get better when iteration increases. As for the particle swarm optimization algorithms, they perform stably each time after the iterations, with remarkably good effects; (3) All in all, the particle swarm optimization algorithm based on the concave function strategy for decreasing inertia weight with swarm position neighborhood mutation has the best nesting performance.更多还原