改进的蚂蚁算法在矩形优化排料中的应用

矩形件优化排料问题是一类具有NP完全难度的组合优化问题.将改进的蚂蚁算法应用到矩形件优化排料问题求解中,优化试验结果表明可获得比基本蚂蚁算法更好的效果,为矩形件优化排料这类NP完全问题提供了新的思路和方法.     

排料算法优化

用计算机进行计算、优化排料是剪、冲裁等材料加工过程中非常值得关注的问题。对贵金属、特种材料和高档装饰材料等,提高它们的利用率具有明显的经济效益。 排料优化问题依照算法和材料的不同可分为矩形板排料和连续带排料两大类。在剪裁加工中材料大多为矩形板材,常采用矩形板材优化排料算法。有时还要把冲剪顺序、冲剪方式等作为附加条件考虑在优化过程中。这类优化过程中按工件形状又分为两类：复杂工件排料、矩形工件排料。矩形板材排料过程中工件种类多,尺寸各异。 在连续冲裁加工中材料大多为宽度给定的连续带,工件种类单一。按照…     

具有类比学习机制的优化排料系统

一个具有类比学习机制的二维图形优化排料系统首先将不同规则图形的排料问题转化为矩形件的排料问题；然后利用启发式搜索方法，求得较优解。系统问题求解中引入了类比学习机制，因此系统可以随着排料次数的增加，使所需排料时间逐渐减少。     

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

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

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

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

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

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

带预选搜索步深的二维一刀切矩形优化排料

排料问题是一种总体资源分配问题，其目标是将定量的资源划分为若干指定的份额。使剩余量极小。本文提出了一种新的二维一刀切矩形优化排料算法。实验结果表明，该算法效率高，灵活性强，可被广泛应用于许多相关排料领域。     

切板机计算机辅助排料软件系统的实现

有约束的矩形排料问题是将矩形零件按沿直线切割工艺要求在原料上进行最优布局 ,使得原料的废料最少。针对这种排料问题 ,对零件和原料种类和数量有限和无限的情况 ,采用启发式的方法 ,进行有效的搜索 ,以减少计算时间 ,确保最优的排料结果的算法 ,同时还介绍了在排料实现中一些问题的处理。     

求解板材排料问题的新方法

§１．引言 板材排料问题是家具、包装、地毯等行业常见的一个问题．它是指将一批不同种类的待排矩形件全部排放在给定的板材上,使排料所用的板材数量尽可能地少,即板材的利用率尽可能地高．实质上是一个组合优化的二维布局问题,从计算复杂性来看,是一个ＮＰ完全问题,但至今还没有找到解决该问题的有效多项式时间算法．寻求其近似最优解的近似算法是目前解决该问题的途径之一． 国内外已有不少学者在布局问题方面作了一些研究．如有用模拟退火算法解决大规模排料问题,但其解过分依赖于模拟退火算法冷却进度表的参数的选取,而且该算法…     

树形数据结构存贮与恢复的一种新方法 下

2、带双整数标记的先根方式 由上述知,带双标记位的先根方式,对于存贮树形结构是有效的,它能够恢复树的原先结构,但是算法比较复杂,而且得到的是二叉树,还需作一次由二叉树到树的转换,才能得到树。(树即为任意树,或叫一般树)不过,此方法给了我们一个提示:双标记位用0或1表示两种状态,适用于二叉树,那么把双标记位改为双整数,不是可以表示更多的状态、适用于任意树吗? 于是,一种新的顺序存贮方法产生了,这就是带双整数标记的先根次序存贮法。这种方法的节点形式是:     

基于故障相关矩阵的最优测试序列生成方法

针对最优测试序列生成问题,采用与或图搜索生成测试序列,将系统故障与测试之间的关系作为节点生成的依据,在综合了信息论与启发式搜索理论的基础上,由霍夫曼编码和信息熵构成的启发式搜索函数来引导与或图的搜索生成诊断树,安排最优的测试顺序,实现用最少的代价隔离系统故障;在解决与或图搜索问题中应用了改进后的AO*算法,避免出现"NP-完全"的复杂计算问题,整个过程大大减少了生成节点的数量,提高了故障隔离效率。     

Bottom-Up Construction of Minimum-Cost and/ or Trees for Sequential Fault Diagnosis

The problem of generating the sequence of tests required to reach a diagnostic conclusion with minimum average cost, which is also known as a test-sequencing problem, is considered. The traditional test-sequencing problem is generalized here to include asymmetrical tests. In general, the next test to execute depends on the results of previous tests. Hence, the test-sequencing problem can naturally be formulated as an optimal binary AND/OR decision tree construction problem, whose solution is known to be NP-hard. Our approach is based on integrating concepts from one-step look-ahead heuristic algorithms and basic ideas of Huffman coding to construct an AND/OR decision tree bottom-up as opposed to heuristics proposed in the literature that construct the AND/OR trees top-down. The performance of the algorithm is demonstrated on numerous test cases, with various properties.     

一种求解与/或树的Petri网方法

研究了用Petri网求解人工智能中与/或树的问题,提出了一种把与/或树转换成相应的Petri网,并通过其逆网求得原与/或树的解树的方法,可进而利用模糊Petri网的推理得到与/或树的最优解树。该方法直观高效,拓宽了Petri网的应用领域。     

多约束环境下的二维布局

多约束环境下不规则的多边形的优化布局具有一定的特殊性，本文就多约束条件对二维布局的影响进行分析，提出双向包络线的概念，算法，运用基于ＡＮＤ／ＯＲ图的问题归纳进行求解，算法效率高，易于实现。     

Generalized and/or graphs

A generalization of AND/OR graphs is introduced as a problem solving model, in which subproblem interdependence in problem reduction can be explicitly accounted for. An ordered-search algorithm is given to find a solution. The algorithm is proven to be admissible and optimal. Examples are given which show the application of the formalism to problems which cannot be modelled by AND/OR graphs. Generalized AND/OR graphs are finally shown to be equivalent to type O grammars. Finding a solution of a generalized AND/OR graph is shown to be equivalent to deriving a sentence in the corresponding type O grammar.     

多值测试诊断策略优化设计

针对电子系统中多值测试条件下的测试排序问题,提出了一种诊断策略优化方法。首先,以相关性矩阵模型为基础,将已有的二值测试的优化算法同多值测试问题相结合,提出了适用于多值测试的基于霍夫曼编码的启发式函数;其次,将平均测试代价最小和平均测试步骤最少作为优化目标,采用与或树启发式搜索算法生成诊断树,得到多值测试的诊断策略,并给出了诊断策略优化方法的具体实现步骤;最后,将其应用到航空设备的实例中。结果表明提出的基于霍夫曼编码的与或树启发式搜索算法是可行的,其生成的诊断树是最优的,比基于信息熵的与或树启发式搜索算法具有更小的平均测试代价和更少的平均测试步骤。     

基于最优子段的矩形优化排样

为有效解决企业实际生产中的矩形优化排样问题,对矩形优化排样算法进行研究, 给出基于最优子段的矩形优化排样算法,有效解决了企业实际生产中的长板矩形优化排样问题。 首先基于动态规划算法求出所有小于剪床刀刃长度的最优子段的最佳排样方式,然后以所求的最 优子段作为可用子段在长板上进行优化排样,并将矩形优化排样问题转化为完全背包问题。最后 基于分支定界技术的整数规划算法对其进行求解。企业应用实例表明该算法在解决长板矩形优化 问题方面优于其他算法。     

基于重要度的矩形工件优化填充排样算法

大规模矩形件优化排样是一个典型的组合优化问题,属于NP2hard问题。矩形件优化排样已广泛应用于板材切割、瓷砖铺设、服装裁剪等行业。在实际排样工作中发现,决策者对工件的选择不仅要考虑大小、工件费用、铺设利用率等诸多因素,往往还需要考虑颜色、花式、铺设方式等因素。基于这种状况,引入排样属性重要度的概念,提出了基于重要度的矩形工件优化填充排样算法,使用计算机辅助排样。通过实例排样表明了该算法的有效性和实用性。     

A heuristic algorithm for distributed control in manufacturing systems

Distributed Problem Solving Networks (DPSN) provide a means for interconnecting intelligent problem solver nodes that can solve only a part of a problem depending on their ability in the problem domain. The decomposition of a problem into subproblems, and the selection of nodes to solve them can be regarded as the generation of an AND/OR tree, and the solution of the problem as a search for a solution tree. Introducing measurements for the cost of a solution tree, we present an algorithm to find one having minimal cost under certain conditions. A Flexible Manufacturing System consisting of a network of flexible workcells is used as an example.     

A join algorithm for combining AND parallel solutions in AND/OR parallel systems

When two or more literals in the body of a Prolog clause are solved in (AND) parallel, their solutions need to bejoined to compute solutions for the clause. This is often a difficult problem in parallel Prolog systems that exploit OR and independent AND parallelism in Prolog programs. In several AND/OR parallel systems proposed recently, this problem is side-stepped at the cost of unexploited OR parallelism in the program, in part due to the complexity of the backtracking algorithm beneath AND parallel branches. In some cases, the data dependency graphs used by these systems cannot represent all the exploitable indenpendent AND parallelism known at compile time.In this paper, we describe the compile time analysis for an optimizedjoin algorithm for supporting independent AND parallelism in logic programs efficiently without leaving any OR parallelism unexploited. We then discuss how this analysis can be used to yield very efficient runtime behavior. We also discuss problems associated with a tree representation of the search space when arbitrarily complex data dependency graphs are permitted. We describe how these problems can be resolved by mapping the search space onto the data dependency graphs themselves. The algorithm has been implemented in a compiler for parallel Prolog based on the Reduce-OR process model. The algorithm is suitable for the implementation of AND/OR systems on both shared and nonshared memory machines. Performance on benchmark programs exhibiting AND and OR parallelism on one shared memory machine and one message passing machine is presented.This work was supported in part by NSF Grants CCR-87-00988 and CCR-89-02496.A shorter version of this paper appears in theProceedings of NACLP 1990.