基于自适应遗传算法和多条带策略的排样方法研究

针对现代工业工艺生产中普遍存在的矩形件排样优化问题,在遗传算法的主要环节应用性能较优的算子对矩形件排样序列进行了求解,并运用交叉概率和变异概率能自适应调整的方法来提高遗传算法的收敛速度及稳定性。提出了满足工艺生产切割要求的多条带策略,辅以最低水平线算法的择优插入策略对矩形件序列进行解码。实验结果表明, 与分层策略相比,所提出的排样方法不仅能得到 更高、更稳定的板材利用率,而且还能提高工艺生产的效率并降低生产的时间成本,具有重要的现实意义。     

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

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

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

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

基于最小包络矩形的不规则凸多边形的三角形处理算法

针对最小矩形包络算法处理不规则多边形时包络率低并造成板材使用率低的现象,在最小矩形包络算法基础上,提出三角形处理法。通过包络求解、分类、组合三个环节将不规则凸多边形转化成矩形,并采用遗传算法及最低水平轮廓算法进行矩形排样。通过对比实验,验证了三角形处理算法提高板材使用率的有效性。     

矩形件优化排样的混合启发式方法

提出一种启发式递归与遗传算法相结合的混合启发式算法求解矩形件优化排样问题。首先给出一种启发式递归算法,利用该算法逐个从待排矩形件中生成局部利用率高的条料,直到所有待排矩形件均生成条料;利用遗传算法全局搜索能力强的特点,对这些条料序进行搜索重组,使其所用的板材数最少;最后再次利用遗传算法,对条料生成之前的矩形件种类序进行全局最优搜索,使总的板材利用率达到了最大。对两个典型实际算例进行计算,并与相关文献比较,结果表明了该算法的有效性。     

基于遗传算法求解带公差的“一刀切”问题

矩形件排样是典型的组合优化问题,在很大程度上影响着企业生产效率。将遗传算法与启发式规则相结合,同时在排样过程中考虑待排样式的公差,求解"一刀切"矩形件排样问题。首先,采用实数基因编码方式,由实数基因值与启发式信息结合确定待排样式的优先权。其次,基于待排样式的最小极限尺寸,采用两步解码方法。第一步为初始填充,将待排样式组合成满足"一刀切"的可行条料,并求解板材利用率最高的条料填充方式;第二步为对第一步剩余空白区的填充,求解不同启发式信息下,空白区利用率最高的待排样式填充方式。再者,基于待排样式的最大极限尺寸和板材尺寸,对最优排样方案进行调整。最后,以VB6.0为开发工具将算法实现,并通过实例对比分析证明了算法的有效性。     

改进的矩形毛坯三块排样方式及其算法

致力于改进矩形毛坯三块排样方式的生成算法,采用三种策略缩小解的搜索范围,并将该算法与线性规划相结合形成排样方案生成算法,用于求解大规模矩形毛坯排样问题.通过实验证明,与二阶段、T形、两段、三阶段排样算法相比,排样方案生成算法生成的排样方案虽然板材利用率稍低,但排样方案简单,能够简化切割工艺.     

基于树型编码的矩形布局算法

优化布局的目的是根据给定待排零件对板材进行最优切割使得板材的利用率尽可能地高。本文提出一种基于遗传算法的矩形件排样布局算法，该算法直接采用布局树(二叉树)作为种群编码，并重新定义了相关的适应值函数、重组和变异等遗传算子。实验和应用表明算法是成功的。     

基于遗传模拟退火算法的布局优化研究

为提高矩形件排样算法的利用率与时间效率,提出将遗传算法和模拟退火算法融 合优化的矩形排样算法。采用带符号的十进制编码,依据矩形件长宽比和面积而生成基因序列用 于建立初始种群,以随机产生若干排样顺序与排样尺寸不一的个体,并以利用率为适应度函数, 修改后的最低水平线搜索算法作为排样策略,保证较优个体得以保留,减少闲置区域的产生。 采用10 组随机产生的矩形数据将本算法与现有文献提出的GA 算法进行对比实验,实验结果显 示：该算法有效地提升了排样结果的利用率与时间效率。     

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

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

Solution for textile nesting problems using adaptive meta-heuristics and grouping

 An optimal packing problem of non-convex polygons on a sheet is considered and applied to a textile nesting problem. We propose a procedure of grouping objects and adaptive meta-heuristics. The grouping procedure classifies objects into groups which are then allocated on the sheet using adaptive meta-heuristics. As a result, effectiveness of the meta-heuristics is improved. The performance of the proposed method is compared with other meta-heuristics using simulation experiments. The result shows that the present method is superior to cases where adaptive meta-heuristics without grouping are used.     

圆形件卷材排样问题的一种定序定位算法

圆形件卷材排样问题是指将一组不同半径的圆形件互不重叠的排放在宽度指定的 卷材上,使得占据的卷材长度最小。针对该问题提出一种定序定位启发式优化算法。设计基于 最大穴度的定位算法,对于每个特定排样序列,计算待排样圆形件在当前布局的所有可行放置 位置的穴度,选择穴度最高的一个位置放置圆形件;更新当前布局,继续排放剩余圆形件,直 到所有圆形件均排放进卷材为止。采用遗传算法对排样序列进行遗传进化得到多种不同的排样 方案,选择耗费卷材长度最小的一种排样方案作为最终解。实验结果表明,本文算法排样方案 耗费卷材长度较小,且算法计算时间相对合理。     

利用改进遗传算法的参数估计

基于极大似然法的参数估计实质上是一个复杂的非线性优化问题，传统的优化方法计算效率较低且容易陷入局部极值。而遗传算法是一种有导向的随机搜索方法，能以较大的概率收敛到全局最优解。本文将单纯形法引入到并行遗传算法中，提出了一种改进的遗传算法，可以有效地提高算法的收敛速度、防止搜索过程中的早熟现象。应用于系统初始状态未知时的参数估计问题，获得了满意的结果。     

一种自适应权重的并行PSO快速装箱算法

随着智能制造时代的到来,生产线后期产品的智能装箱已成为工业生产的重要环节,如何更快速地得到装箱结果对于提高生产效率尤为重要。以快速装箱为目标,文中提出了一种适用于工业生产线的智能化装箱算法。该算法采用自适应权重法改进了粒子群优化算法,相较于标准粒子群优化及遗传等传统启发式算法有更快的收敛速度;并采用GPU加速,实现了高性能的并行计算,大幅加快了计算速度。实验表明,所提算法同样能得到很好的空间利用率, 同时其收敛速度也显著优于传统算法。     

面向布局优化问题的多量子态量子进化算法及其应

针对演化算法在求解带平衡约束的圆形布局问题上所出现的早熟现象,提出一种有利于保持种群多样性的多量子态量子进化算法,并结合高效的定位定序启发式方法进行求解。为了高效优化布局顺序,在量子进化算法的基础上：引入多量子态编码和基于平均收敛概率的收敛标准以提高求解速度;引入基于禁忌策略和启发信息的观测方法,使其所得到的n进制解为互不相同的整数串,同时保证优先布局质量大、半径大的小圆;引入动态量子进化策略,有效地引导种群向最优个体进化。在定位规则中引入定位概率函数提高解的精度,数值实验结果表明,该算法能够有效求解带平衡约束的圆形布局问题。     

基于启发式动态分解算法的矩形件优化排样

针对二维矩形件优化排样问题,提出了一种启发式动态分解算法,其可扩展用于三维及多容器全局排样求解。根据排放矩形件对容器进行正交动态分解,计算放置耦合度选择最佳子容器,通过干涉关系实现所有容器状态更新,实现大规模复杂排样问题的快速高效求解。对国际上公认Bench-mark多个问题例的计算结果表明,所提算法与同类算法相比优势明显,布局利用率提高达9.4%,计算效率提升达95.7%,并且已在商业化排样软件AutoCUT中应用,应用前景良好。     

Combining the ant system algorithm and simulated annealing for 3D/2D fixed-outline floorplanning

Three dimensional integrated circuits (3D ICs) can alleviate the problem of interconnection, a critical problem in the nanoscale era, and are also promising for heterogeneous integration. This paper proposes a two-phase method combining the ant system algorithm (AS) and simulated annealing (SA) to handle 3D IC floorplanning with fixed-outline constraints. In the first AS phase, the floorplans are constructed by sequentially packing the block one by one, and the AS is used to explore the appropriate packing order and device layer assignment for the blocks. When packing a block, a proper position including the coordinates and the appropriate layer in the partially constructed floorplan should be chosen from all possible positions. While packing the blocks, a probability layer assignment strategy is proposed to determine the device layer assignment of unpacked blocks. After the AS phase, the SA phase is used to perform further optimization. The proposed method can also be easily applied to 2D floorplanning problems. Compared with the state of the art 3D/2D fixed-outline floorplanner, the experimental results demonstrate the effectiveness of the proposed method.     

An improved genetic algorithm with conditional genetic operators and its application to set-covering problem

The genetic algorithm (GA) is a popular, biologically inspired optimization method. However, in the GA there is no rule of thumb to design the GA operators and select GA parameters. Instead, trial-and-error has to be applied. In this paper we present an improved genetic algorithm in which crossover and mutation are performed conditionally instead of probability. Because there are no crossover rate and mutation rate to be selected, the proposed improved GA can be more easily applied to a problem than the conventional genetic algorithms. The proposed improved genetic algorithm is applied to solve the set-covering problem. Experimental studies show that the improved GA produces better results over the conventional one and other methods.