矩形件排样问题的遗传算法求解

本文研究了求解矩形件正交排样优化问题的遗传算法。同时，将矩形件正交排样问题转化为一个排列问题，提出了求一个排列所对应的排样图的下台阶算法（改进的ＢＬ算法）将下台阶算法与遗传算法相结合，用于矩形件排样问题的求解，给出了该算法的实现。用该算法对文献中的两个算例进行了求解，结果表明该算法获得了比ＢＬ算法更好的解，是一种较为行之有效的方法。     

矩形件优化排样问题的混合遗传算法求解

利用遗传算法结合剩余矩形排样法求解矩形件正交排样问题。通过遗传算法将矩形件正交排样问题转化为一个排列问题,并引入剩余矩形排样算法来惟一确定每一个排列所对应的排样图(即排样方案),两者结合用于求解矩形件排样问题。最后用此混合遗传算法对文献[1]中的两个算例进行了验证,表明了其有效性。     

矩形件优化排样问题的混合遗传算法求解

利用遗传算法结合剩余矩形排样法求解矩形件正交排样问题。通过遗传算法将矩形件正交排样问题转化为一个排列问题，并引人剩余矩形排样算法来惟一确定每一个排列所对应的排样图（即排样方案），两者结合用于求解矩形件排样问题。最后用此混合遗传算法对文献[1]中的两个算例进行了验证，表明了其有效性。     

基于遗传算法的大规模矩形件优化排样

大规模矩形件优化排样是一个典型的组合优化问题，属于NP-hard问题．实际工程中对一个排样方案一般有满足“一刀切”的工艺要求，“一刀切”要求增加了对排样的约束．提出的优化算法，将矩形匹配分割算法作为遗传算法染色体的解码器实现一个排样方案，用遗传算法进行排样方案的全局搜索．算例比较表明，该算法可以求得满足“一刀切”约束的最优解．     

基于改进遗传算法的不规则图形排样

针对大规模零件和布料优化排样问题,研究遗传算法在智能排样中的应用及其在智能优化排样中的优缺点。以传统遗传算法优化排样为基础,提出一种改进的基于遗传算法的优化排样算法,利用图形间的相似度对图形群体进行分类,降低遗传算法的时间复杂度。实验结果证明,该方法在时间复杂度上优于传统的遗传算法优化排样,适用于大规模的图形排样系统。     

基于改进免疫遗传算法的矩形件排样

文章在基本免疫遗传算法的基础上提出了针对矩形件排样问题的改进算法,探讨了能记忆排样过程先验知识的浓度算子对排样过程的影响,实验证明是有效的。     

一种用于矩形排样优化的改进遗传算法

矩形排样优化属于NPC问题,在工业界有着广泛的应用,如布料切割、金属下料和新闻组版等。提出了一种基于环形交叉算子和环形变异算子的自适应遗传算法,并将改进的自适应遗传算法和IBL启发式布局算法相结合,有效地解决了矩形排样优化问题。对比实验结果表明,环形交叉算子和环形变异算子对遗传算法是有效的,所提出的改进混合自适应遗传算法能够在一个较短的时间内找到满意解。     

遗传算法在矩形件优化排样中的应用

遗传算法是一种全局优化的数值计算方法。与传统优化算法相比,它对函数的要求不高,一般不会陷入局部最优解,更适应于求解大规模离散化问题。该文将遗传算法应用于工程问题的一个典型离散优化问题矩形件优化排样。通过该算法可以找出高效率的排样加工方法。设计结果能广泛应用于各零件的排样加工实例。     

一种快速的有约束矩形件优化排样模型

为了有效地解决有约束的矩形件优化排样问题,提出一种快速的求解算法;通过比较待排样矩形件的不同排样模式,选择最优排样方案。算法完全基于解析计算,虽不能寻找理论最优解,但相比于各种启发式算法大大提高了排样速度。实验结果表明,算法能够在较短的计算时间内获得满意的排样效果,是一种效率较高的有约束矩形件排样算法。     

面轨道特征的矩形排样与加工路径优化方法研究

为了解决实际生产中遇到的一种带有面轨道特征的矩形排样问题,重点研究了自 适应遗传算法和图论相结合的优化方法,极大提高了切削加工效率。该方法将路径优化问题转 化为一个考察无向图连通性问题,并利用遗传算法在解空间中进行全局搜索,以寻找加工路径 最优解,并按照BL 定位策略完成对矩形的排样。通过对遗传算法的改进：①对初始个体基因 位的合法性判断,并利用深度优先遍历结果评估个体性能的优劣;②交叉、变异算子均采用自 适应机制,并且执行变异操作的对象限定为一条染色体上的断点集,极大提高了算法的性能。 最后,通过实验验证了该算法在绝大多数情况下完全可以找到满足需求目标的结果,是一种非 常可靠的方法。     

基于离散粒子群算法的矩形件优化排样

目前,粒子群算法在连续问题优化上的应用已经很广泛,然而在离散问题优化方面仍处在尝试阶段.提出了一种改进粒子群算法来解决矩形件排样优化问题(离散优化问题).该算法融合了遗传算法中的交叉和变异思想,采用了信息交流策略,使其达到快速优化目的.算法也对"最低水平线法"解码方式进行了改进.实验结果表明,该算法具有快速,高效特点,与现有同类算法比较,在解决矩形件排样问题方面的优势明显.     

基于改进最低水平线方法与遗传算法的矩形件排样优化算法

传统的最低水平线方法用于矩形件排样时可能产生较多未被利用的空白区域,造 成不必要的材料浪费。针对此缺陷,在搜索过程中引入启发式判断,实现空白区域的填充处理, 提高板材利用率。在应用遗传算法优化矩形件排样顺序时,在进化过程中采用分阶段设置遗传 算子的方法,改善算法的搜索性能与效果。通过改进最低水平线方法与基于分阶段遗传算子的 遗传算法相结合,共同求解矩形件排样问题。排样测试数据表明,所提出的矩形件排样优化算 法能够有效改善排样效果,提高材料利用率。     

基于蚁群优化算法求解矩形件排样问题

布局问题来源于生产实际,优秀的布局可以提高原料利用率,降低成本,提高经济效益,对许多行业有重要意义。矩形件优化排样是一类具有NP完全难度的组合优化问题。人工蚁群算法是对蚂蚁群体行为的模拟抽象,该算法具有分布计算、信息正反馈和启发式搜索等特点。本文将蚁群算法和剩余矩形法结合用于解决矩形排样问题,首先用蚁群算法将矩形件排样问题转化为一个排列问题;然后通过剩余矩形排样算法排出每一个排列所对应的排样图;最后用算法对文献[9]中的两个算例进行了验证,表明了其有效性。     

基于自适应遗传模拟退火算法的矩形件排样

研究一种自适应遗传模拟退火算法,应用于矩形件优化排样问题。以整数编码矩形件的排样序列,采用经验选择与随机生成相结合的策略构造初始种群。运用自适应交叉和变异概率动态地控制遗传算法的收敛速度,通过模拟退火算法引导全局最优搜索,采用启发式最低水平线择优算法对排样序列进行解码,形成排样方式。多组对比实验结果表明,自适应遗传模拟退火算法求解速度较快,可以有效提高板材的利用率。     

A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem

The rectangle knapsack packing problem is to pack a number of rectangles into a larger stock sheet such that the total value of packed rectangles is maximized. The paper first presents a fitness strategy, which is used to determine which rectangle is to be first packed into a given position. Based on this fitness strategy, a constructive heuristic algorithm is developed to generate a solution, i.e. a given sequence of rectangles for packing. Then, a greedy strategy is used to search a better solution. At last, a simulated annealing algorithm is introduced to jump out of the local optimal trap of the greedy strategy, to find a further improved solution. Computational results on 221 rectangular packing instances show that the presented algorithm outperforms some previous algorithms on average.     

求解矩形和圆形装填问题的最大穴度算法

在超大规模集成电路设计,裁缝裁剪布料,玻璃切割等工作中提出了矩形和圆形装填问题,即把不同大小的矩形块和圆饼装入一个矩形容器中,以最大化容器的面积利用率为优化目标。对这一问题,可采用模拟退火,遗传算法等国际流行算法进行求解,但这些方法计算时间较长,计算结果的优度也不甚理想。利用人类的智慧和经验,提出了一种求解此问题的最大穴度算法。并对3个随机生成的测试实例进行了实算测试。所得结果的平均面积利用率为90．80％,平均计算时阊为8．38s。测试结果表明,算法对求解矩形和圆形装填问题是行之有效的。     

求解矩形Packing问题的基于遗传算法的启发式递归策略

An improved heuristic recursive strategy combining with genetic algorithm is presented in this paper. Firstly, this method searches some rectangles, which have the same length or width, to form some layers without waste space, then it uses the heuristic recursive strategies to calculate the height of the remaining packing order and uses the evolutionary capability of genetic algorithm to reduce the height. The computational results on several classes of benchmark problems have shown that the presented algorithm can compete with known evolutionary heuristics. It performs better especially for large test problems.     

求解矩形Packing问题的基于遗传算法的启发式速归策略

An improved heuristic recursive strategy combining with genetic algorithm is presented in this paper. Firstly, this method searches some rectangles, which have the same length or width, to form some layers without waste space, then it uses the heuristic recur sive strategies to calculate the height of the remaining packing order and uses the evolutionary capability of genetic algorithm to reduce the height. The computational results on several classes of benchmark problems have shown that the presented algorithm can compete with known evolutionary heuristics. It performs better especially for large test problems.