基于离散粒子群优化算法求解矩形件排样问题

改进了一种近似排样算法,并将改进的近似排样算法与离散粒子群优化算法结合求解矩形件排样问题.设计了应用离散粒子群优化算法求解矩形件排样问题的相关操作和定义,给出了离散粒子群优化算法求解矩形件排样问题的详细步骤,最后通过实验测试,验证了算法的有效性.     

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

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

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

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

矩形件智能优化排样算法与应用

文章在分析智能优化算法的基础上,针对下料生产作业中解决排样问题的需要,提出了将遗传算法、模拟退火算法分别与"最低水平线法"排放算法结合来进行矩形件优化排料的方法,并通过实例分析比较了两种智能优化算法的应用效果.     

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

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

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

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

矩形件无约束二维板材剪切的4块排样算法

针对矩形件无约束二维板材剪切排样问题,提出一种新的4块排样方式及其生成算法.该排样方式将板材划分成4个块,对每个块,按照递归方式进行排样.选择一行同种矩形件放置在块的左下角,沿着这行矩形件的上边界和右边界将该块剩余部分划分成两个更小的子块以待进一步递归考察.首先,构造动态规划算法一次性生成所有可能尺寸的块中矩形件的递归...     

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

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

矩形件优化排样的一种启发式算法

对大规模矩形件正交排样问题,提出了一种快速高效的启发式排放算法。对当前的可排放位置（水平线）,用贪婪算法从未排矩形件中选择可排放于该水平线的最优矩形件组合块;根据各个排放位置与其对应的矩形件组合块的匹配程度,选择最优的可排放位置（最优水平线）优先排放。在排放时,为了便于后续排放,先将待排放位置对应的矩形件组合块从低到高进行排序,再排放。对E.Hopper提供的规模最大的一类实例进行计算,排样率都在99%以上,平均排样率达到了99.38%,平均计算时间只用了1.12秒。与相关文献最好结果进行了比较,结果表明该文算法解决大规模的矩形件排样具有高效性。     

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

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

求解2-D Strip Packing问题的u-分组优化算法

D strip packing问题指将带有价值的矩形物品装入长宽固定的箱子中,使其装入的物品价值最大。基于装箱的期望目标ε,提出一种新的分组构造函数,结合装箱矩形特点计算出最优分组参数u并对矩形进行分类,同时对不同类别的矩形引入相应的数据结构,最后对不同类别矩形基于箱子X轴的u等分点进行填充,使其装入的物品价值最大。文中的主要贡献在于:提出了一种有效的分组构造函数;计算出了对应的最优分组参数u;简化了不同类别箱体的数据结构以及相应的装箱算法;特别地,在期望目标ε、多项式时间复杂度和 至少装入(1－ε) OPT价值物品的情况下,可将所需箱体宽度从1＋ε减小到1,而高度保持不变。     

Optimization of one-dimensional Bin Packing Problem with island parallel grouping genetic algorithms

The well-known one-dimensional Bin Packing Problem (BPP) of whose variants arise in many real life situations is a challenging NP-Hard combinatorial optimization problem. Metaheuristics are widely used optimization tools to find (near-) optimal solutions for solving large problem instances of BPP in reasonable running times. With this study, we propose a set of robust and scalable hybrid parallel algorithms that take advantage of parallel computation techniques, evolutionary grouping genetic metaheuristics, and bin-oriented heuristics to obtain solutions for large scale one-dimensional BPP instances. A total number of 1318 benchmark problems are examined with the proposed algorithms and it is shown that optimal solutions for 88.5% of these instances can be obtained with practical optimization times while solving the rest of the problems with no more than one extra bin. When the results are compared with the existing state-of-the-art heuristics, the developed parallel hybrid grouping genetic algorithms can be considered as one of the best one-dimensional BPP algorithms in terms of computation time and solution quality.     

基于遗传算法的SDN网络装箱问题研究

随着网络规模愈加庞大和复杂,运营商正处于逐渐从传统IP网络向SDN网络架构发展阶段。论文以SDN架构下的网络为研究对象,建立以最大带宽利用率最小化和新增业务后全局网络扰动最小为目标的网络模型,提出基于改进的遗传算法对复杂网络环境下的装箱问题进行求解。利用Java编写并模拟仿真当前运营商主流网络场景IPRAN,分析遗传算法和其他启发式算法,如粒子群,模拟退火算法在装箱问题的优化效果,验证所提出的改进遗传算法对于解决网络装箱问题的有效性。     

最大圈分解问题的研究进展

最大圈分解问题最早由Erds和Pósa提出,随后研究人员在图论领域和理论计算机科学领域中对其进行了广泛的探索。最近研究发现,该问题在计算生物学上特别是在构建进化树与分析基因组的研究方面有重要的应用。主要介绍了该问题的研究现状。首先讨论了该问题在图论方面的研究进展;随后对该问题的近似算法、参数算法、参数复杂性与不可近似性进行了分析和讨论;最后给出了该问题的进一步研究方向。     

多约束的箱子大小可变的装箱问题

作为经典装箱问题的扩展,带有约束条件的装箱问题有着很强的应用背景。从钢铁公司板坯入库引发的装箱问题中,物品除了重量这一参数,还引入了特性和种类等参数。将板坯入库归结为多约束的箱子大小可变的装箱问题后,建立了数学模型,将经典装箱算法进行了推广,构建了新的启发式算法A,它对输入物品按特性进行预处理,再进行装箱。理论分析了NFD,FFD,算法A的最坏情况的性能,并对这三种算法进行了数值模拟,得出在相关特性均匀分布下,算法A的性能最好。     

基于装箱树算法求解集装箱装载问题的研究

研究了把同种货物装入一个集装箱内，使箱子内的空间利用率为最大的集装箱装载问题．首先，运用启发式算法,充分考虑了箱子和货物的方位、剩余空间等问题．然后，通过主空间装填、空间分层、剩余空间优化等建立一个装箱树．最后，用Java程序完成装箱树算法，并实现集装箱装载问题的求解．用实例验证了算法的可行性，能够投入实际应用．     

加权3-Set Packing问题的核心化

Packing和Matching问题是一类重要的NP难解问题,该类问题的参数算法和核心化研究受到了人们广泛的关注.主要研究了加权3-SetPacking的核心化算法.对于加权3-SetPacking问题,基于对问题结构的深入分析,提出并证明了2个简化规则.首先限定加权3-SetPacking问题实例中包含给定2个元素的集合的个数,然后在限定问题实例中包含1个给定元素的集合的个数.基于对集合个数的限定,得到问题实例中总的集合个数的上界.并基于上述性质得到2个简化规则,可得到加权3-SetPacking问题大小为27k3-36k2+12k的核,该核心化结果是加权3-SetPacking问题的首个核心化结果.得到的加权3-SetPacking的核心化过程同样适用于加权3D-Matching问题的核化,可得到与加权3-SetPacking问题同样大小的问题核.     

Mechanical Assembly Packing Problem Using Joint Constraints

The three-dimensional packing problem is generally on how to pack a set of models into a given bounding box using the smallest packaging volume. It is known as an NP-hard problem. When discussing the packing problem in mechanical field, the space utilization of a mechanism is low due to the constraint of mechanical joints between different mechanical parts. Although such a situation can be improved by breaking the mechanism into components at every joint, it burdens the user when reassembling the mechanism and may also reduce the service life of mechanical parts. In this paper, we propose a novel mechanism packing algorithm that deliberately considers the DOFs (degrees of freedom) of mechanical joints. With this algorithm, we construct the solution space according to each joint. While building the search tree of the splitting scheme, we do not break the joint, but move the joint. Therefore, the algorithm proposed in this paper just requires the minimal number of splits to meet the goal of space utilization. Numerical examples show that the proposed method is convenient and efficient to pack three-dimensional models into a given bounding box with high space utilization.