A layout algorithm for signaling pathways

Visualization is crucial to the effective analysis of biological pathways. A poorly laid out pathway confuses the user, while a well laid out one improves the user’s comprehension of the underlying biological phenomenon.We present a new, elegant algorithm for layout of biological signaling pathways. Our algorithm uses a force-directed layout scheme, taking into account directional and rectangular regional constraints enforced by different molecular interaction types and subcellular locations in a cell. The algorithm has been successfully implemented as part of a pathway visualization and analysis toolkit named Patika, and results with respect to computational complexity and quality of the layout have been found satisfactory. The algorithm may be easily adapted to be used in other applications with similar conventions and constraints as well.Patika version 1.0 beta is available upon request at http://www.patika.org.     

An observation concerning constraint-based compaction

This paper presents a refinement of the most commonly used technique for VLSI layout compaction. The usual approach to the compaction problem involves solving a constraint system that encodes the design rules of the layout. When arbitrary design rules are allowed, the fastest known algorithm for solving the constraint system requires Θ(nm) time in the worst case, where n is the number of layout components and m is the number of constraints. Here we show that if the input layout is legal, the constraint system can be solved in Θ(m+n log n) time. The key idea is to write the constraints in terms of displacements of layout features, rather than absolute coordinates.     

基于ACIS和优化排料的手机创新设计研究与实现

利用3D造型软件开发平台ACIS可以快速地生成造型各异的构件.优化排料的目的是根据给定待排样品对板材进行最优切割使得板材的利用率尽可能的高,利用ACIS软件生成手机构件,然后应用优化排料算法对手机进行优化布局.实验结果表明,该算法能够加快设计速度,拓宽设计思路,能够增强构件概念设计的创新性.     

Sequential optimization approach for nesting and cutting sequence in laser cutting

The economy of the laser cutting process depends on two productivity issues: (i) nesting, a classic problem of finding the most efficient layout for cutting parts with minimum material waste; (ii) cutting sequence, which targets the optimal sequence of edges of the parts to be cut for minimum cycle time. This paper presents a two stage sequential optimization procedure for nesting and cutting sequence for the objectives of maximizing material utilization and minimization of ideal (non-cut) travel distance of laser cut tool. However, the focus of this paper is the development of solution technique for optimal cutting sequence to any given layout. Simulated annealing algorithm (SAA) is considered to evolve the optimal cutting sequence. The proposed SAA is illustrated with the optimal material utilization layout obtained using sheet cutting suite software, a professional rectangular nesting software package. The robust test carried out with five typical problems shows that the SAA proposed for cutting sequence is capable of providing near optimal solutions. The performance comparison with two literature problems reveals that the proposed SAA is able to give improved result than GA and ACO algorithms.     

CAN——计算机辅助排样软件包

本文介绍一个实用的计算机辅助排样软件—CAN。该软件采用扫描探测排样算法,解决了具有任意形状的零件排样问题。同时,本文还提出了几点改进措施,提高了材料的利用率。     

带静不平衡约束的矩形装填问题的启发式算法

卫星舱布局问题不仅是一个复杂的耦合系统设计问题,也是一个特殊的优化问题,具有NP难度性。解决这类问题最大的挑战在于需要优化的目标函数具有大量的被高能势垒分隔开的局部极小值点。Wang-Landau（WL）抽样算法是一种改进的蒙特卡罗方法,已经被成功地运用蛋白质结构预测等优化问题。本文以卫星舱布局优化问题为背景,首次将WL抽样算法引入矩形装填问题的求解。针对矩形装填物的特点,提出了启发式格局更新策略,以引导抽样算法在解空间中进行有效行走。为了加速搜索全局最优解,每次蒙特卡罗扫描生成新的布局时,便执行梯度法进行局部搜索。通过将局部搜索机制、启发式格局更新策略与WL抽样算法相结合,提出了一种用于解决带静不平衡约束的任意矩形装填问题的启发式布局算法。在布局优化过程中,通过在挤压弹性势能的基础上增加静不平衡量惩罚项并采用质心平移的方法,使布局系统的静不平衡量达到约束要求。另外,为了改进算法的搜索效率,提出了改进的有限圆族法用于装填物之间的干涉性判断和干涉量计算。通过对文献中两组共10个有代表性的算例进行实算,计算结果表明,所提出的装填算法是一种求解带静不平衡性能约束的任意矩形装填问题的有效算法。     

Genetic Algorithm Coding Methods for Leather Nesting

The problem of placing a number of specific shapes in order to minimise waste is commonly encountered in the sheet metal, clothing and shoe-making industries. The paper presents genetic algorithm coding methodologies for the leather nesting problem which involves cutting shoe upper components from hides so as to maximise material utilisation. Algorithmic methods for computer-aided nesting can be either packing or connectivity driven. The paper discusses approaches to how both types of method can be realised using a local placement strategy whereby one shape at a time is placed on the surface. In each case the underlying coding method is based on the use of the no-fit polygon (NFP) that allows the genetic algorithm to evolve non-overlapping configurations. The packing approach requires that a local space utilisation measure is developed. The connectivity approach is based on an adaptive graph method. Coding techniques for dealing with some of the more intractable aspects of the leather nesting problem such as directionality constraints and surface grading quality constraints are also discussed. The benefits and drawbacks of the two approaches are presented.     

Smashing peacocks further: drawing quasi-trees from biconnected components

We extend the popular force-directed approach to network (or graph) layout to allow separation constraints, which enforce a minimum horizontal or vertical separation between selected pairs of nodes. This simple class of linear constraints is expressive enough to satisfy a wide variety of application-specific layout requirements, including: layout of directed graphs to better show flow; layout with non-overlapping node labels; and layout of graphs with grouped nodes (called clusters). In the stress majorization force-directed layout process, separation constraints can be treated as a quadratic programming problem. We give an incremental algorithm based on gradient projection for efficiently solving this problem. The algorithm is considerably faster than using generic constraint optimization techniques and is comparable in speed to unconstrained stress majorization. We demonstrate the utility of our technique with sample data from a number of practical applications including gene-activation networks, terrorist networks and visualization of high-dimensional data     

人工蜂群算法在带约束圆形布局问题中的应用

人工蜂群算法是一种基于蜜蜂采蜜机制的新型演化算法。给出了带平衡约束的圆形布局问题的数学模型,介绍了人工蜂群算法的基本过程以及计算流程,将人工蜂群算法应用于带平衡约束的圆形布局优化中。通过两个实例进行仿真计算,并将计算结果与文献结果比较,验证了人工蜂群算法是解决此类问题的一种有效且实用的群智能算法。     

布局优化子问题的改进遗传神经网络算法

带性能约束的航天舱布局问题可分解为有限多个子问题,每个子问题克服了关于优化变量的时断时续性。本文针对子问题(关于同构布局等价类),首先构造了用于产生与已知布局方案同构的布局方案的优化算法,然后在给出组合变异策略的基础上,设计了连续空间上基于实数编码的改进遗传神经网络算法。将该算法应用于二维布局优化子问题,数值实验表明该遗传神经网络进行布局逼近是有效的。这种方法是对布局问题求解的有效探索。     

基于几何推理的布局设计新方法

面向约束的布局设计问题一直是布局研究的热点．本文提出了一个基于几何推理的布局设计生成算法，其最大优点就是充分利用参数化设计的优点，建立了影响布局设计的变量之间的关系．该算法具有较强的柔性，易于扩充，并支持约束一致性检测和影响布局设计参变量的局部修改．算法已在作者研制的车身内布置设计系统中得到了较好的应用．     

带静不平衡约束的正交矩形布局问题的启发式模拟退火算法*

以卫星舱布局为背景,研究一类带静不平衡约束的正交矩形布局问题.借鉴拟物策略,定义矩形与矩形、矩形与圆形容器之间的嵌入度计算公式,将该问题转变为无约束的优化问题.通过将启发式格局更新策略、基于梯度法的局部搜索机制与具有全局优化功能的模拟退火算法相结合,提出一种求解带静不平衡约束的正交矩形布局问题的启发式模拟退火算法.算法中的启发式格局更新策略产生新格局和跳坑,梯度法搜索新格局附近能量更低的格局.另外,在布局优化过程中,通过在挤压弹性势能的基础上增加静不平衡量惩罚项,并采用质心平移的方法,使布局系统的静不平衡量达到约束要求.实验表明,文中算法是一种解决带静不平衡约束的正交矩形布局问题的有效算法.     

Hybridizing electromagnetism-like mechanism algorithm with migration strategy for layout and size optimization of truss structures with frequency constraints

The optimal design of a truss structure with dynamic frequency constraints is a highly nonlinear optimization problem with several local optimums in its search space. In this type of structural optimization problems, the optimization methods should have a high capability to escape from the traps of the local optimums in the search space. This paper presents hybrid electromagnetism-like mechanism algorithm and migration strategy (EM–MS) for layout and size optimization of truss structures with multiple frequency constraints. The electromagnetism-like mechanism (EM) algorithm simulates the attraction and repulsion mechanism between the charged particles in the field of the electromagnetism to find optimal solutions, in which each particle is a solution candidate for the optimization problem. In the proposed EM–MS algorithm, two mechanisms are utilized to update the position of particles: modified EM algorithm and a new migration strategy. The modified EM algorithm is proposed to effectively guide the particles toward the region of the global optimum in the search space, and a new migration strategy is used to provide efficient exploitation between the particles. In order to test the performance of the proposed algorithm, this study utilizes five benchmark truss design examples with frequency constraints. The numerical results show that the EM–MS algorithm is an alternative and competitive optimizer for size and layout optimization of truss structures with frequency constraints.     

异型件排样系统的研究与开发

对于多种不规则零件的排样问题，任何算法都难以保证总能得到最优解。该文采用计算机图形学处理技术以及现代智能算法相结合的方式，按照图形预处理，自动排样、人工交互编辑3步有效地解决了不规则零件的排样问题，并开发了相应的排样软件。     

Mathematical formulation and a new metaheuristic for the constrained double-floor corridor allocation problem

A layout plan for a manufacturing system that is designed without any facility constraints will most likely be infeasible when confronted with reality. Additionally, considering that land available for building industrial plants is limited and its cost is high, it is necessary to investigate the layout planning of two and multi-floor facilities. To address these shortages in the scientific literature, we focus on the double-floor corridor allocation problem (DFCAP) which covers a wide range of complex facility constraints, such as fixed floor constraints, fixed row constraints, fixed positioning constraints, mutual floor constraints, mutual row constraints, sequencing constraints and adjacency constraints. For the model mentioned above, we term it as a constrained DFCAP (cDFCAP). A mixed-integer linear programming model is formulated for the cDFCAP. In order to solve larger realistic problems, a constrained metaheuristic with the memetic algorithm framework customised for solving the cDFCAP is introduced in this work. In our algorithm, four problem-specific heuristic rules to construct a set of initial solutions are developed. In addition, an ideal parameter combination for our constrained memetic algorithm is determined through a Taguchi experimental design. Finally, the results of a set of cDFCAP instances with different sizes (n = 10∼80) report that our provided approach is effective for the considered problem.     

皮料优化排样的有效方法

根据汽车内饰等行业需求,对皮制品加工的优化排样问题进行了研究.创新地采用离散化处理方式,同时引进边界约束,使排样过程与皮料和样片的几何信息无关,使用基于顺序的启发式底左布局将样片顺次布置到皮料上,样片的最优布置顺序和角度依靠随机优化算法来实现.设计了简洁、实用的操作算子,并提出了基于模拟退火技术的遗传算法(simulated annealing based genetic algorithm,简称SABGA),该算法在优化搜索中能自适应地控制变异率,使得优化高效地逼近全局最优解.实验及对比结果表明,提出的优化排样方式特别适用于二维不规则形体在多个二维不规则平面上的优化排样.     

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

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

面向对象设计的嵌套表格模板设计技术

工程中经常使用一些复杂的嵌套表格,这种表格的本质是地工程对象的描述,通过对如何使用模板技术设计嵌套表格进行探讨,重点说明了表格变量参数的对象化设计,使用表张模板技术和对象化的表格参数设计技术设计的表格可以由用户自由定制,自动填写数据,具有一致而又良好的编辑功能。     

Solving nesting problems with non-convex polygons by constraint logic programming

In this paper an application of constraint logic programming (CLP) to the resolution of nesting problems is presented. Nesting problems are a special case of the cutting and packing problems, in which the pieces generally have non‐convex shapes. Because of their combinatorial optimization nature, nesting problems have traditionally been tackled by heuristics and in the recent past by meta‐heuristics. When trying to formulate nesting problems as linear programming models, to achieve global optimal solutions, the difficulty of dealing with the disjunction of constraints arises. On the contrary, CLP deals easily with this type of relationships among constraints. A CLP implementation for the nesting problem is described for convex and non‐convex shapes. The concept of nofit polygon is used to deal with the geometric constraints inherent to all cutting and packing problems. Computational results are presented.     

Visual comparison of metabolic pathways

Biological databases contain a large amount of data about metabolic pathways, in particular about similar pathways in different species. Biologists are familiar with visual representations of metabolic pathways. Pathway diagrams help them to understand the complex relationships between the components of the pathways, to extract information from the data, and to compare pathways between different species. However, visual interfaces to metabolic pathway databases cannot cope well with the visual comparison of similar pathways in different species.This paper presents a new approach for the visual comparison of metabolic pathways which uses a graph drawing algorithm. Using layout constraints, identical parts of similar pathways in different species are placed side by side, thereby highlighting similarities and differences between these pathways. This visualization method can be used as a visual interface to databases. It supports different layout styles and has been tested with data obtained from the BioPath system and the KEGG database.