一种同构、非同构布局模式构造算法

给出了一种基于完全关联图的准确构造同构、非同构布局模式的算法,并给出了其计算复杂度及适应范围.与李广强等（2003）的布局模式构造方法相比较表明,本算法能构造准确布局模式,适用范围较广,计算复杂度低,前者为O（n^3）,本文为O（n）,O（n^2）或O（n^3）.     

蚂蚁算法在机构同构判定中的实现

本文选取在机械设计领域普遍存在的机构同构判定问题作为应用对象,将机构的同构判定问题转化为求解其邻接矩阵的特征编码值的问题,利用蚂蚁算法对于NP完全问题所具有的抵御组合爆炸的能力进行求解,在参数选择合适的情况下取得了令人满意的结果.文中首先介绍蚂蚁算法的基本原理,随后给出求解机构同构判定的蚂蚁算法模型,进而通过应用实例验证该模型的有效性,并在数值实验的基础上,深入分析了模型参数对计算结果的影响关系,最后给出了有关结论和对进一步研究工作的展望.     

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

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

遗传布局算法

VLSI门阵列模式布局是一类NP完全问题，传统的分析、研究方法和求解策略不能提供优化布局。文中将遗传算法应用于门阵列模式布局，提出了遗传布局算法，设计了相应的选择函数、交叉算子和变异算子，使布局的构形更趋合理。模拟结果表明，应用遗传布局算法能在较短的时间内提供优化解，为解决大规模、复杂的布局问题提供了广阔的前景。     

图的同构判断初探

图论是离散数学的一个重要分支。本文探讨了图的同构判断问题，包括同构的证明及非同构的证明，特别用五个正则图的同构判断来说明本文提出的判断方法。     

非方阵指派问题的求解

本文将2 类方阵指派问题——极大极小和总体极小指派问题——的矩阵作业解法推广到非方阵情形, 即求解任务与人员数目不等的指派问题,且维持矩阵作业法的效率．假定m > n,则按本文行优先选取算法求解 m￡n 非方阵指派问题的最大逻辑运算量为O(mn2),其效率通常与执行一轮覆盖的矩阵作业法相当．     

基于同构节点的动态故障树分析方法

为了解决动态故障树研究领域的马尔可夫链状态空间爆炸问题,给出了一个基于同构节点的动态故障树分析方法。为每个节点建立一个对象,识别同构节点,求解时对于同构节点仅计算一次,从而减少状态空间中的状态数目、缩短计算时间。运用该方法对空间信息处理平台进行可靠性分析,并与其他方法进行对比,结果表明,如果系统结构具有较强的冗余特征,该方法在求解效率上具有比较明显的优势。     

基于遗传算法的布局问题求解

布局问题是VLSI布图设计中的重要问题，传统的方法很难得到满意的解答。针对该问题，文中提出了一个基于遗传算法的求解方法，并将它应用到VLSI门阵列模式布局设计中，构造了一个较完备的综合布局目标函数，引入并定义了通道拥挤度。实验结果表明，所提出的方法能在较短的时间内提供优化解，为VLSI布局设计提供了一种新的思路。     

求解装填布局问题的膨胀方法

介绍了膨胀装填布局的思想原理与算法实现。膨胀装填布局通过对缩小了的装填物体系统地施加膨胀－排斥操作而实现被装填物体布局位置的自动产生,具有直观性强、聚集性好、几何形状适应性广、便于工程推广等优点。作为算例,使用膨胀装填算法对几种与平面圆相关的装填布局问题给出了计算结果。     

旋转锥体空间中圆柱体群的布局优化

旋转圆锥体空间中不等圆柱体群的布局为人造卫星再入舱布局的简化模型，属带动力性能约束的Packing优化问题，具有NP难度．本文提出了模式迭换法，用以构造布局拓扑模式，形成初始布局方案；推荐了在此初始布局方案下进行布局寻优的算法；给出了缓解“组合爆炸”的技巧和算例验证．此类问题具有广阔的工程应用前景．     

一种基于SLP的新型编译框架

对于SLP算法不能高效处理并行代码占有率较小的大型应用程序的问题,本文提出并评估了一种新型的基于改进的SLP(Superword level parallel)算法的编译框架。它主要包括三个阶段,首先,将代码中的结构相似的异构语句通过改进的SLP算法尽可能的改为同构语句;然后,用全局的观点,在优化目标代码之前获取其数据模型重用;最后,联合数据布局优化进行进一步的性能提升。本文就此框架做了大量实验,实验结果表明本框架比SLP算法性能更佳,优于它约15.3%。     

人机交互的遗传算法及其在约束布局优化中的应用

复杂工程布局（如卫星舱布局）方案设计问题在理论上属带性能约束的布局优化问题（NPC问题）,很难求解,因而目前研究得尚少。为解决此类问题,该文提出了一种人机交互的遗传算法。该算法首先将人工设计的个体作为染色体群体的组成部分,然后在遗传运算中,把人工适时设计的新个体加入到染色体群体中,以代替群体中的较差个体。从而构成人机交互的遗传算法,这样可以充分发挥人和计算机各自的特长。文后通过3个算例（其中一个为作者构造的已知最优解的算例）的数值计算,验证了该算法的可行性和有效性。     

时空轨迹序列模式挖掘方法综述

在全球定位、移动通信技术迅速发展的背景下涌现出了海量的时空轨迹数据,这些数据是对移动对象在时空环境下的移动模式和行为特征的真实写照,蕴含了丰富的信息,这些信息对于城市规划、交通管理、服务推荐、位置预测等领域具有重要的应用价值,而时空轨迹数据在这些领域的应用通常需要通过对时空轨迹数据进行序列模式挖掘才能得以实现。时空轨迹序列模式挖掘旨在从时空轨迹数据集中找出频繁出现的序列模式,例如： 位置模式（频繁轨迹、热点区域）、活动周期模式、语义行为模式,从而挖掘时空数据中隐藏的信息。总结近年来时空轨迹序列模式挖掘的研究进展,先介绍时空轨迹序列的数据特点及应用,再描述时空轨迹模式的挖掘过程：从基于时空轨迹序列来挖掘位置模式、周期模式、语义模式这三个方面来介绍该领域的研究情况,最后阐述现有时空轨迹序列模式挖掘方法存在的问题,并展望时空轨迹序列模式挖掘方法未来的发展趋势。     

Packing Irregular Objects in 3D Space via Hybrid Optimization

Packing problems arise in a wide variety of practical applications. The basic problem is that of placing as many objects as possible in a non‐overlapping configuration within a given container. Problems involving irregular shapes are the most challenging cases. In this paper, we consider the most general forms of irregular shape packing problems in 3D space, where both the containers and the objects can be of any shapes, and free rotations of the objects are allowed. We propose a heuristic method for efficiently packing irregular objects by combining continuous optimization and combinatorial optimization. Starting from an initial placement of an appropriate number of objects, we optimize the positions and orientations of the objects using continuous optimization. In combinatorial optimization, we further reduce the gaps between objects by swapping and replacing the deployed objects and inserting new objects. We demonstrate the efficacy of our method with experiments and comparisons.     

基于两阶段的分段单一矩形优化排样

为有效解决分段单一矩形优化排样问题,给出一个求解分段单一矩形优化排样问题的两阶段方法。第一阶段完成标准子段最佳排样方式求解,并将二维排样问题转化为一维下料问题,第二阶段使用适合于一维下料问题求解的算法完成板材最佳排样方式求解。使用该方法开发了一个单一矩形优化排样系统,该系统既可以解决分段单一矩形排样问题也可以解决其他类型的单一矩形优化排样问题。企业应用实例表明该方法是求解分段单一矩形优化排样问题的一个较为有效的方法。     

Breaking symmetries in graph search with canonizing sets

There are many complex combinatorial problems which involve searching for an undirected graph satisfying given constraints. Such problems are often highly challenging because of the large number of isomorphic representations of their solutions. This paper introduces effective and compact, complete symmetry breaking constraints for small graph search. Enumerating with these symmetry breaks generates all and only non-isomorphic solutions. For small search problems, with up to 10 vertices, we compute instance independent symmetry breaking constraints. For small search problems with a larger number of vertices we demonstrate the computation of instance dependent constraints which are complete. We illustrate the application of complete symmetry breaking constraints to extend two known sequences from the OEIS related to graph enumeration. We also demonstrate the application of a generalization of our approach to fully-interchangeable matrix search problems.     

Clustering by Pattern Similarity

The task of clustering is to identify classes of similar objects among a set of objects.The definition of similarity varies from one clustering model to another.However,in most of these models the concept of similarity is often based on such metrics as Manhattan distance,Euclidean distance or other L_p distances.In other words,similar objects must have close values in at least a set of dimensions.In this paper,we explore a more general type of similarity.Under the pCluster model we proposed,two objects are similar if they exhibit a coherent pattern on a subset of dimensions.The new similarity concept models a wide range of applications.For instance,in DNA microarray analysis,the expression levels of two genes may rise and fall synchronously in response to a set of environmental stimuli.Although the magnitude of their expression levels may not be close,the patterns they exhibit can be very much alike.Discovery of such clusters of genes is essential in revealing significant connections in gene regulatory networks.E-commerce applications,such as collaborative filtering,can also benefit from the new model,because it is able to capture not only the closeness of values of certain leading indicators but also the closeness of (purchasing,browsing,etc.) patterns exhibited by the customers.In addition to the novel similarity model,this paper also introduces an effective and efficient algorithm to detect such clusters,and we perform tests on several real and synthetic data sets to show its performance.     

Efficient implementations of construction heuristics for the rectilinear block packing problem

The rectilinear block packing problem is a problem of packing a set of rectilinear blocks into a larger rectangular container, where a rectilinear block is a polygonal block whose interior angle is either 90° or 270°. There exist many applications of this problem, such as VLSI design, timber/glass cutting, and newspaper layout. In this paper, we design efficient implementations of two construction heuristics for rectilinear block packing. The proposed algorithms are tested on a series of instances, which are generated from nine benchmark instances. The computational results show that the proposed algorithms are especially efficient for large instances with repeated shapes.     

Disc cutters plane layout design of the full-face rock tunnel boring machine (TBM) based on different layout patterns

The quality of plane layout design of the disc cutters for the full-face rock tunnel boring machine (TBM) directly affects the balance of force distribution on the cutter head during the excavating. Various layout patterns have been adopted in practice during the layout design of the disc cutters. Considering the engineering technical requirements and the corresponding structure design requirements of the cutter head, this study formulates a nonlinear multi-objective mathematical model with multiple constraints for the disc cutters plane layout design, and analyses the characteristics of a multi-spiral layout pattern, a dynamic star layout pattern and a stochastic layout pattern. And then a genetic algorithm is employed to solve a disc cutters’ multi-spiral layout problem, and a cooperative co-evolutionary genetic algorithm (CCGA) is utilized to solve a disc cutters’ star or stochastic layout problems. The emphasis was put on the study of superiority of three different layout patterns. Finally, an instance of the disc cutters’ plane layout design was solved by the proposed methods using three different kinds of layout patterns. Experimental results showed the effectiveness of the method of combining the mathematical model with the algorithms, and the pros and cons of the three layout patterns.     

Developing GIS Applications with Objects: A Design Patterns Approach

In this paper we present an object-oriented approach for designing GIS applications; it combines well known software engineering practices with the use of design patterns as a conceptual tool to cope with recurrent problems appearing in the GIS domain. Our approach allows the designer to decouple the conceptual definition of application objects from their spatial representation. In this way, GIS applications can evolve smoothly, because maintenance is achieved by focusing on different concerns at different times. We show that our approach is also useful to support spatial features in conventional applications built with object-oriented technology. The structure of this paper is as follows: We first introduce design patterns, an efficient strategy to record design experience; then we discuss the most common design problems a developer of GIS applications must face. The core of our method is then presented by explaining how the use of decorators helps in extending objects to incorporate spatial attributes and behavior. Next, we analyze some recurrent design problems in the GIS domain and present some new patterns addressing those problems. Some further work is finally discussed.