宏单元阵列自动布局算法研究

本文研究并实现了一个用于宏单元阵列的自动布局算法。算法分为初始布局及迭代改善两部分，为提高布图成功率，以线网均匀分布为目标。在初始布图中，采用自下而上结群的方式将宏单元分配到各单元行上，再进行行内定位。在改善布局中，通过对单元行内及单元行间的迭代改善，进一步降低了布线密度，优化了初始布局的结果，从而可使布图成功率得到提高。算法已用Ｃ语言实现，并应用于自动布图系统中，实验结果表明了算法的有效性。     

三维实体布局中改进局部最优解的冲突决策方法

利用博弈论中冲突决策的思想实现了三维实体布局从一个局部最优解向另一个更好的局部最优解跳跃的算法，部分克服了传统算法的主要瓶－局部最优陷井的问题。理论分析及实例计算表明，当布局问题陷入某－局部最优解时，该算法利用冲突决策策略能有效地春跳入另一个更好的局部最优点上。通过一系列这样的跳跃，最终使布局问题获得一个高质量的解。     

求解PDPTW 问题的一种快速禁忌搜索算法

提出一种解决实际规模和复杂度的PDPTW问题的快速禁忌搜索算法．该算法分为构造初始解和改进解两个阶段：在第1阶段，使用插入算法来构造一个尽可能好的初始解；在第2阶段，使用禁忌搜索算法来改进得到的解，最后构造了两个实际规模和复杂度的例子，测试结果表明该算法对于求解此类PDPTW问题是有效的。     

线性约束优化问题演化算法求解的初始解集确定

演化算法求解线性约束问题时需要确定初始解集，文章提出了一个通用高效的确定完备初始解集的算法，并作出了评价。     

基于搜索信息反馈策略的MaxSAT非完备求解算法

MaxSAT问题是SAT可满足性问题的优化形式，具有NP难度．本文分析了传统的MaxSAT局部搜索求解器对工业算例求解存在的局限性，并基于此分析提出了新的初始解构造算法ASIF.ASIF是一个基于树形赋值的初始解构造算法，其中包含了一个全局信息反馈策略.该算法选取并定义了构造过程中有意义的统计量，使用这些量设计了一个全局搜索信息更新反馈机制，对初始解构造过程中的经验进行积累并为后续解的构造提供指导信息，再根据后续解的构造情况对全局经验进行反馈和更新，从而有效利用了解构造过程中的经验和信息.进一步地，将ASIF作为初始解构造算法，结合IPBMR算法中的路径截断（PB）策略，提出了新的算法PB-ASIF.实验设计与比较共分为三个阶段.第一阶段，将ASIF在300秒内首次找到的可行解与IPBMR求解300秒的结果进行对比.ASIF初始可行解更优的数量是IPBMR在300秒内求解的可行解更优数量的两倍多，其中非加权偏类算例更优解数量上前者更是后者的3.68倍.该阶段的实验结果表明，ASIF算法能快速构造优质的初始可行解.第二阶段，将PB-ASIF与IPBMR进行对比实验，在300秒求解时间内，...     

基于改进初始解的遗传算法的布局设计方法

带性能约束的三维布局问题属于具有很强应用背景的组合优化问题,进行了基于全局的布局求解方法的探索。由于NP完全问题的计算复杂性,使得遗传算法求解问题的全局最优解时效率较低。改进了遗传算法的初始解,对提高算法的效率进行了研究。并以旋转卫星舱布局的简化模型为背景,建立了多目标优化数学模型。实例结果与传统遗传算法以及乘子法的计算结果比较,表明该算法具有较好的求解效率。     

岛式FPGA线长驱动快速布局算法

传统的FPGA布局箅法需要花费大量时间,影响了FPGA物理设计效率.为了在保证布局质量的前提下缩短布局时间,提出一种岛式FPGA快速布局算法.首先考虑终端传输的迭代二划分,然后进行最小费用流初始布局和低温模拟退火的布局优化.在每一个划分层次中,考虑了线网的终端对线网权重的影响;对于每一个划分的区域,使用最小费用流来确定初始的布局;在布局的最后阶段使用低温模拟退火来提高初始布局的质量.实验结果表明,该算法布局结果的质量高、速度快.     

数据立方体选择的改进遗传算法

数据立方体选择问题是一个NP完全问题。研究了利用遗传算法来解决立方体选择问题,提出了一个结合局部搜索机制的遗传算法。这一算法的核心思想在于,首先运用一个基于单位空间最大收益值的预处理算法来生成初始解,然后该初始解经结合了局部搜索机制的遗传算法进行提高。实验结果表明,该算法在寻优性能上优于启发式算法和经典遗传算法。     

三维实体布局中实体初始合理摆放位置的研究

本文基于二叉树结构表示三维实体布局问题，证明了若干定理。根据这些定理设计了一个求得实体初始合理摆放位置的算法。实体初始合理位置的求得对以后的实际布局过程非常有利，否则，可能会有麻烦或得不到合理的布局。     

输电网接线图增量自动成图算法

输电线网接线图自动成图算法是一个非常复杂的全局优化问题.它涉及到厂站位置的自动布局和输电线路自动规划两个方面.本文给出了解决该问题的一种具体思路和算法,将该问题划分为3个部分：首先,利用力导向算法对厂站位置进行初始布局,采用模拟退火算法进行迭代计算,通过并发技术实现引力、斥力系数进行选择,得到代价最小的初始厂站初始布局.其次,利用A*算法对输电线路进行线路规划,构建了一个线路走向的代价模型,通过代价模型规范线路走向,得到美观的线路布局.最后,对布局结果评价反馈再布局,将常见的几种布局缺陷通过程序的方式进行消缺,减少人工干预.同时,本文还对历史线路和新增线路做了处理,使得算法可以实现在不改变历史厂站线路布局的情况下,对新增厂站线路进行布局规划.通过实验显示,该方法得到的图形结果满足线路规划美观,布局合理,交叉少,拐角少等优点.     

巧克力的嫁衣——读当代装饰设计语言之美

一滴水可以反映整个太阳的光辉,优秀的包装设计是当代装饰设计、当代设计的一面镜子,本文以巧克力包装为着眼点,从历史的维度、人类文化学的视角,以时代的发展、与时俱进的观点来看待装饰与装饰语言,试图从优秀巧克力包装设计中,提炼出装饰美的规律,把握住当代装饰设计的流行趋势、发展规律,认识装饰的本质,恰当运用好装饰语言。     

包装视觉语言设计表达的整体性研究

随着社会的进步与发展,商品包装已渗透到人们生活的各个领域。人们消费意识和审美意识不断提高的普遍性,给包装设计师提出了更高的要求。本文就商品包装的图形、色彩、文字等视觉语言要素设计,如何做到整体性、统一性及和谐美,进行了全面的分析与论述。结论:只有遵循形式美法则规律,保持统一的和谐整体关系,才能达到对包装设计的视觉语言更完美有效地表达。     

A general packing algorithm for multidimensional resource requirements

Many problems in resource allocations, memory allocation, and distributed computer system design can be formulated as problems of packing variablesized items into fixed-sized containers in order to minimize the total number of containers used. In this paper, a generalized packing algorithm that encompasses many well-known heuristic packing algorithms is proposed. Simulation results on this generalized packing algorithm are described, and their implications are discussed. The objective of this paper is to investigate the performance of various heuristic packing algorithms within a general framework, to obtain numerical estimates on their efficiency, and to provide guidelines on the use of these algorithms.     

上海地铁ATM网中基于AAL2规程的话音中继打包密度

建立一个马尔科夫链模型，以分析ＡＴＭ适配层类型２规程的信元打包过程，证实信元中话音的打包密度及链路使用效率很大程度上取决于Ｔｉｍｅｒ－ＣＵ的值。还给出了为达到预计的链路效率计算Ｔｉｍｅ－ＣＵ值的算法，并联系上海地铁的具体情况给出仿真结果。     

二维实体布局中实体初始合理摆放位置的研究

文中基于二叉树结构表示二维实体布局问题，证明了若干定理。根据这些定理设计了一个求得实体初始合理摆效位置的算法。实体初始合理位置的求得对以后的实际布局过程非常有利，否则，可能会有麻烦或得不到合理的布局。     

求解三维装箱问题的混合模拟退火算法

提出了一个高效求解三维装箱问题(Three Dimensional Container Loading Problem 3D-CLP)的混合模拟退火算法.三维装箱问题要求装载给定箱子集合的一个子集到容器中,使得被装载的箱子总体积最大.文中介绍的混合模拟退火算法基于三个重要算法:(1)复合块生成算法,与传统算法不同的是文中提出的复合块不只包含单一种类的箱子,而是可以在一定的限制条件下包含任意种类的箱子.(2)基础启发式算法,该算法基于块装载,可以按照指定装载序列生成放置方案.(3)模拟退火算法,以复合块生成和基础启发式算法为基础,将装载序列作为可行放置方案的编码,在编码空间中采用模拟退火算法进行搜索以寻找问题的近似最优解.文中采用1500个弱异构和强异构的装箱问题数据对算法进行测试.实验结果表明,混合模拟退火算法的填充率超过了目前已知的优秀算法.     

Bin packing and related problems: General arc-flow formulation with graph compression

We present an exact method, based on an arc-flow formulation with side constraints, for solving bin packing and cutting stock problems—including multi-constraint variants—by simply representing all the patterns in a very compact graph. Our method includes a graph compression algorithm that usually reduces the size of the underlying graph substantially without weakening the model.Our formulation is equivalent to Gilmore and Gomory׳s, thus providing a very strong linear relaxation. However, instead of using column-generation in an iterative process, the method constructs a graph, where paths from the source to the target node represent every valid packing pattern.The same method, without any problem-specific parameterization, was used to solve a large variety of instances from several different cutting and packing problems. In this paper, we deal with vector packing, bin packing, cutting stock, cardinality constrained bin packing, cutting stock with cutting knife limitation, bin packing with conflicts, and other problems. We report computational results obtained with many benchmark test datasets, some of them showing a large advantage of this formulation with respect to the traditional ones.     

Corner occupying theorem for the two-dimensional integral rectangle packing problem

This paper proves a corner occupying theorem for the two-dimensional integral rectangle packing problem,stating that if it is possible to orthogonally place n arbitrarily given integral rectangles into an integral rectangular container without overlapping,then we can achieve a feasible packing by successively placing a rectangle onto a bottom-left corner in the container.Based on this theorem,we might develop e?cient heuristic algorithms for solving the integral rectangle packing problem.In fact,as a vague conjecture,this theorem has been implicitly mentioned with different appearances by many people for a long time.     

加权3-Set Packing 的改进算法

Packing问题构成了一类重要的NP难问题.对于加权3-SetPacking问题,把问题转化成加权3-SetPacking Augmentation问题进行求解,即主要讨论如何从一个已知的最大加权k-packing求得一个权值最大的(k+1)-packing.通过对问题结构的分析,结合Color-Coding技术,首先给出了一种时间复杂度为O*(10.63k)的参数算法,极大地改进了目前文献中的最好结果O*(12.83k).通过对(k+1)-packing结构的进一步分析,利用集合划分技术将上述结果降到O*(7.563k).     

动态吸引子在布局求解中的应用

在研究分析现有布局启发算法的基础上,提出了动态吸引子的概念,并据此建立了动态的定位函数和布局求解算法,分析了定位函数中各参数和坐标点的含义．通过调整定位函数中参数的取值,可得到满足不同条件和要求的优化布局方案．最后通过实例验证了该算法的合理性．