双容错数据布局算法DP—RAID扩展研究

基于单容错编码的数据布局已经不能满足存储系统对可靠性越来越高的要求。对基于多容错编码的数据布局的研究受到了广泛的关注，并且出现了一些多容错的布局算法，如多维Parity，DH1，DH2等。但这些布局算法普遍存在冗余度较差、计算负载大等缺点。DP-RAID是一种基于水平方向和对角方向双重奇偶校验的双容错数据布局算法。该布局计算负载小，实现简单，但该布局要求校验条纹长度为素数。本文对DP-RAID进行扩展，使其能够应用于校验条纹长度为素数减一的环境。与其他双容错布局算法比较表明，该布局算法在保证同样可靠性的情况下，性能有了明显的提高。     

一种基于遗传算法的工艺品布局求解算法

在组件特征模型的基础上，针对工艺品布局创新的需要提出亚组件的概念，在遗传算法中引入人机交互技术，在适合度函数中引入形象度和抽象度，形成一种基于遗传算法的布局自动求解算法。以斑铜工艺品布局求解为例，对该算法进行了验证。理论和实例分析表明，该算法能快速有效地生成多个斑铜工艺品的布局方案。     

基于社区探测的层次自适应并行布局算法

针对大规模网络高效布局和递进式结构分析的需求,提出基于社区发现的多层级力导向布局算法.首先,该算法采用Louvain算法对网络进行多层级社团结构划分,根据划分结果压缩网络并进行骨架布局,确定网络整体架构;然后,采用自适应的力导向变体算法对各个社团内部的原始节点并行布局,细化社区内部网络结构,并引入补偿力减少社区划分带来的网络结构信息缺失;最后,设计了初始布局算法、改良了振颤模型来减少布局所需的迭代次数.实验结果表明,与现有网络布局算法相比,该算法能够更清晰、高效地展示大规模社交网络数据,满足大规模复杂网络可视化的需要.     

基于奇偶校验的三容错数据布局研究

基于单容错编码的数据布局已经不能满足存储系统对可靠性越来越高的要求。对基于多容错编码的数据布局的研究受到了广泛的关注，并且出现了一些三容错的布局算法，如HDD1，HDD2等。但这些布局算法普遍存在冗余度较差、计算负载大等缺点。提出了一种基于三重奇偶校验的多容错数据布局算法TP-RAID(Triple Parity RAID)。该算法只需要在RAID5阵列系统中增加两个校验磁盘，通过水平、正向对角和反向对角三重奇偶校验，可容许同时发生的三个磁盘故障。该算法编码、解码简单，三重校验条纹长度相等，计算负载小，易于实现。此外，由于该算法中尽量减少了三重校验之间逻辑关联，使得该算法的小写性能比其他的三容错算法相比有了大幅度的提高。     

基于力导向模型的网络图自动布局算法综述

实现网络图形中节点和边自动布局一直是可视化研究中一个重要内容,基于力导向模型的自动布局算法则是该类研究中应用最广、文献最多的一类方法。根据研究方向出现的时间顺序,从基本模型、基于多维尺度分析的布局算法、多层迭代布局算法、非欧空间节点布局算法、受约束图形自动布局算法等五个方面对基于力引导模型的网络图自动布局算法的典型方法、研究进展、分支情况等进行了描述,并对发展前沿进行了讨论。     

微粒群算法在产品组件布局设计中的应用

提出了一种基于微粒群算法的自适应优化布局求解算法,该算法以组件特征模型为基础,在微粒群算法中引入人机交互技术,从整体上自动优化布局方案,以满足约束条件为目标。并以手机组件的布局求解为例,对该算法进行了验证。理论和实例分析表明,该算法能有效地生成多个手机组件布局方案。     

基于IBSA的高校图书馆布局优化设计

针对系统布置设计方法存在手工计算作业量大、易受布局决策者主观因素影响等缺点，提出一种基于改进回溯搜索优化算法设施布局优化设计方法。以某高校图书馆为研究对象，在分析现有图书馆布局现状的基础上，结合图书馆多层布局特点，建立了图书馆设施规划的数学模型，将改进回溯搜索算法应用到图书馆设施规划优化设计并获取了最优布局方案，并与现有布局方案进行对比分析。结果分析表明，该方法能够有效地解决受面积约束的多层设施布局问题，可为解决类似的设施规划问题提供解决方案。     

一种基于约束的布局求解算法

在研究现有布局求解的基础上，提出了一个基于约束的布局求解算法，该算法借助机构分析与综合中有关自由度分析的概念，在两个层次上进行布局求解，即在高层次上对层布局顺序进行规划，而在较低层次上进行具体的数值定位，通过两层次上交替进行求解最终求得布局结果。     

集成电路模块布局问题的一种有效算法

求解集成电路模块布局问题的一种启发式算法。该算法通过设计一种合理的布局优先序,对同一模块可能的多个布局位置进行比较并将其放置在优先度最高的适当区域,可有效求解集成电路模块布局问题。     

基于蒙特卡罗树搜索的树图布局

树图是层次数据可视化的常用方法,已有的研究发现,满足逐步加点原则的3种树图布局算法(正方化布局算法、条状布局算法和螺旋线布局算法)在常见的4种优化指标(平均长宽比、稳定性、数据一致性和可读性)上各有优缺点.其中,条状布局算法和螺旋线布局算法的长宽比较大,正方化布局的长宽比仍有优化空间.基于蒙特卡罗树搜索,在树图布局的同时构建对应的搜索树并利用置信度上界公式作为搜索路径的选定标准,在用户可接受时间内对3种布局算法的算术平均长宽比和所提加权平均长宽比分别进行了优化.为了证明算法的有效性,在构造出的3种不同分布、7种不同规模的单层数据集以及真实的多层数据集上测试,并与原算法进行比较分析,最后利用对应结论指导用户选择更好的布局算法以及设置更恰当的参数.     

基于PageRank的网络布局算法

基于力导向模型的网络布局算法由于其布局结果直观并且便于分析所以在网络可视化中占有举足轻重的地位。但是当前的网络布局算法在面对大规模网络数据的时候通常不容易在较短时间内获取一个高质量的布局结果。本文提出了一个基于PageRank的力导向模型的算法。该算法引入了PageRank来完善节点的重力和斥力计算以改善布局质量；并且引入节点中心性来预估初始布局中节点的位置；同时,又提出了基于PageRank的自适应步长用来平衡布局的效率和质量。最后为了有效的减少布局算法在面对大规模网络数据时的计算时间,本文设计了一个基于CUDA的灵活的CPU+GPU异构并行计算框架。通过对不同类型和不同规模的网络数据集的实验,该算法能够产出一个符合美学标准的高质量布局,并且在同样的硬件条件下,本文所提出的优化方案相比于原始算法速度最大提高了58倍。     

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

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

基于数学形态学的自适应文字版面分析方法

随着光学字符识别能力的提高,处理日渐复杂的版面成为文件处理系统中的关键部分。针对中文版面的特点,在基于组件的版面分析方法基础上,本文提出了一种具有自适应能力的基于数学形态学中膨胀变换的版面分析方法。该方法对基于组件版面分析的核心部分- 文字合并进行了自适应扩展,使其具有对不同字体大小、间距等样张更大范围的适应能力。     

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

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

VLSI性能驱动工艺映射算法

在ＶＬＳＩ工艺映射过程中计算连线延时是非常困难的，因为此时未进行布图设计，不知道连线长度。本文提出一种称为布图算法驱动的工艺映射技术，其基本思想是研究面向映射的延时驱动布图算法，并用其进行工艺映射过程中的导线延时估计。     

随程序规模动态调整的通道优化布线算法

针对常规层次型布图算法在大规模程序中布线混乱的缺点,借鉴Sugiyama层次布局算法,提出了一种随着程序规模动态调整的通道优化布线算法。通过将节点的通道数目与程序规模建立函数关系,以解决现有算法在布图时出现的线路重叠和效率低下的问题;在布图中结合广义张量平衡思想,以减少交叉并实现布图的美观性;并根据调用节点之间的相对位置关系,给出了相应的线路分配和申请策略,实现了布线的有序性。实践证明,该算法能够提高布图效率,有效地减少交叉,实现节点的有序布线和实现简单等优点。     

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

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

新型电路版图布局布线算法设计

调研了电路自动布局布线技术的国内外研究现状,在此基础上设计了一种面向中等规模电路布局布线算法,主要用于大型版图设计软件的模块测试环节,为用户提供各模块初步的布线布局结果,方便用户高效查找并修正错误点,填补了我国在相关领域的空白.建立了超图模型并转换为图模型,改进了Stoer-Wagner算法并利用该算法和Fiduccia-Mattheyses算法对图进行了基于最小割理论的划分,从而构建出一棵划分树.在这棵树的基础上设计了一种二元相对移动算法来确定各个电路元件的位置,大大降低了布局拥挤度,提高了美观度,对于数百元件的电路均能在0.5s内得出布局结果.基于A*算法在多个方面做了改进,提高了布线速度,对于线路数1000以下的元件能在0.1 s～60 s内得出结果,实现了100％ 布通率以及均匀的布局布线效果.     

高铁列车运行图冗余时间优化布局方法研究

在分析各种冗余时间之间作用机理的基础上,以列车旅行时间和列车到发站延误时间最短为优化目标,建立运行图冗余时间优化布局模型。在此基础上引入遗传粒子群优化算法对模型进行求解,并用MATLAB仿真。以虚拟运行时刻表为背景,通过合理设置列车运行干扰时间和仿真分析方案,对结果进行分析。结果表明：用该模型和算法得到的布局方案相比较于固定比例方案,总延误时间短,列车在区间和车站的晚点次数少;相比较于遗传算法求解该模型的总延误时间短,总冗余时间设置多,但是列车在车站和区间的晚点次数少。     

A linear time layout algorithm for business process models

The layout of a business process model influences how easily it can be understood. Existing layout features in process modeling tools often rely on graph representations, but do not take the specific properties of business process models into account. In this paper, we propose an algorithm that is based on a set of constraints which are specifically identified toward establishing a readable layout of a process model. Our algorithm exploits the structure of the process model and allows the computation of the final layout in linear time. We explain the algorithm, show its detailed run-time complexity, compare it to existing algorithms, and demonstrate in an empirical evaluation the acceptance of the layout generated by the algorithm. The data suggests that the proposed algorithm is well perceived by moderately experienced process modelers, both in terms of its usefulness as well as its ease of use.