基于改进禁止搜索算法的矢量量化码书设计

本文提出了基于改进禁止搜索(TS)算法的矢量量化(VQ)码书设计方法.禁止搜索算法的关键是如何定义一个解以及如何在当前解的基础上生成邻域解.由于码书设计的两个优化准则是最邻近条件和聚类质心条件,本文提出了两种禁止搜索算法的解描述方案,其相应算法分别叫基于码书的禁止搜索(CB-TS)算法和基于聚类划分的禁止搜索(PB-TS)算法.为了提高禁止搜索算法的性能,文中在禁止搜索算法中融入了模拟退火(SA)机制.为了进一步提高码书性能,文中还将码书设计的传统LBG算法融入禁止搜索算法中.结果表明,基于禁止搜索的两种码书设计方案所生成的码书性能都比LBG算法有明显提高.     

基于变领域遗传算法的生产流水线物流调度

生产计划和调度是制造企业的核心问题,工件的延迟或提前会带来额外库存、价格变动、产品损耗等多种问题。文中基于准时化模式的生产理念,研究考虑机器准备时间的两阶段生产流水线物流的工件最佳排序问题。以最小化最大拖期和提前期为目标函数,提出了一种变邻域遗传搜索算法。该算法将遗传算法求得的最优解作为变邻域搜索的初始解,利用变邻域搜索较好的局部搜索能力进行精细搜索,以提高算法的求解质量。通过仿真实验和算法比较验证了变邻域遗传搜索算法的有效性。     

一种新型的变领域搜索算法

一般变邻域搜索算法在连续优化问题的可行解空间上难以找到局部最优解。提出了一种结合SQP算法的变邻域搜索算法,该算法将SQP算法引入到变邻域搜索算法的局部搜索过程中,以SQP算法寻找局部最优解,以变邻域搜索算法跳出局部最优解的低谷,进而寻找到全局最优解。另外还对变邻域搜索算法的初始解和扰动过程进行了改进。数值实验表明,该算法具有良好的收敛性和搜索精度,求解效果优于文献算法。     

增强人工蜂群算法求解半导体最终测试调度问题

本文提出一种增强人工蜂群算法(Enhanced Artificial Bee Colony,EABC),用于最小化半导体最终测试调度问题(Semiconductor Final Testing Scheduling Problem,SFTSP)的最大完工时间.该算法采用混合启发式方法初始化种群,并利用前插式解码策略来提高初始解的质量.在算法搜索阶段设计多种基于问题性质的探索策略和基于贝叶斯网络的概率模型对问题解空间进行深度与宽度的协同搜索.此外,提出基于重启策略的种群更新机制以加强算法跳出局部最优的能力.实验部分构造多种对比算法来验证EABC中各关键环节的有效性.通过基于实例的数值仿真以及与NFOA(Novel Fruit fly Optimization Algorithm)、KMEA(Knowledge-based Multi-agent Evolu-tionary Algorithm)和CCIWO(Cooperative Co-evolutionary Invasive Weed Optimization)的算法比较验证了EABC的有效性和鲁棒性.     

基于函数复杂度的自适应模拟退火和禁忌搜索新算法

在求解多峰复杂函数的过程中,传统的模拟退火算法和禁忌搜索算法经常出现算法快速收敛于局部最优解、后期收敛速度变慢和搜索能力变差等问题.为解决这些问题,本文给出函数复杂度的定义,并提出基于函数复杂度的自适应模拟退火和禁忌搜索算法.该算法首先根据函数复杂度自适应调整步长控制参数,然后根据调整后步长求得函数的粗糙解,在此基础上再使用初始步长求得全局最优解.实验表明,该算法不仅可以跳出局部最优解的限制,并且减少了迭代次数,有效地提高了全局和局部搜索能力.     

哈德码变换域等均值等方差最近邻矢量量化码字搜索算法

本文提出一种基于哈德码变换的等均值等方差最近邻(HTEENNS)快速矢量量化码字搜索算法.在编码前,该算法预先计算每个码字的哈德码变换,然后根据各码字哈德码变换的第一维系数大小的升序排列对码字进行排序.在编码过程中,首先计算输入矢量的哈德码变换和方差,然后选取与输入矢量哈德码变换的第一维系数最近的码字作为初始匹配码字,然后利用两条有效的删除准则在该码字附近进行上下搜索与输入矢量最近的码字.测试结果表明,本文算法比等均值最近邻搜索算法(ENNS)、等均值等方差最近邻搜索(EENNS)算法和哈德码变换域部分失真搜索算法等算法有效得多.     

基于伞布搜索法的贴片机贴装顺序优化算法

以多贴装头直列式贴片机为研究对象,对喂料器已指派情况的元件贴装顺序优化问题提出了一种新的基于伞布搜索算法(SS)的优化算法.首先介绍了SS算法初始种解的生成方法以及如何保证初始种解的多样性的方法.其次讨论了待评估解的改良算法的设计思路和实现方法.其后提出了SS算法种群参考解集的生成和合并规则以及重复解的判定方法.最后将本文提出的SS算法与GA算法用38块评估板进行比较,结果表明算法SS比GA优化效果更好.     

基于H.264自适应阈值的快速运动估计算法

块匹配运动估计在视频编码中有着举足轻重的地位,全搜索算法是最好的搜索算法,但其计算量是最大的,所以提出一种H.264自适应阈值的快速运动估计算法.该算法是利用相邻块的运动矢量来预测初始搜索点,并根据一定的准则来确定静止块,减少了搜索的冗余度,再用基于梯度的十字优先菱形算法米进行搜索.与DS菱形算法相比,该算法具有更高的灵活性,能实时的提前退出搜索,并且在搜索点数上明显减少,且没减少搜索精度.     

等均值等范数最近邻矢量量化码字搜索算法

本文提出了一种等均值等范数最近邻(EENNS)矢量量化码字搜索算法.在编码前,该算法预先计算每个码字的均值和范数,然后根据均值大小的升序排列对码字进行排序.在编码过程中,首先选取与输入矢量均值最近的码字作为初始匹配码字,然后利用两条有效的删除准则在该码字附近进行上下搜索与输入矢量最近的码字.测试结果表明,本文算法比等均值最近邻搜索算法(ENNS)和最近提出的范数排序搜索(NOS)算法有效得多.     

禁忌粒子群算法在几何约束求解中的应用

约束问题可以转化为优化问题,针对粒子群优化算法在算法的后期易陷入局部最优的缺点,提出TPSO(禁忌粒子群优化算法),在算法的前期采用粒子群算法快速产生全局最优解信息素的初始分布,后期引入禁忌搜索算法,记录已经达到的局部最优解,在下一次搜索中,不再或者有选择地搜索这些点,从而跳出局部最优点,并且在搜索过程中允许接受劣解,充分利用禁忌搜索的记忆能力及较强的爬山能力,大大提高了获得全局最优解的概率.该算法综合了粒子群优化算法的快速性,随机性和全局收敛性以及禁忌搜索局部寻优的能力.在确保全局收敛性的基础上,能够快速搜索到高质量的优化解.该方法用于几何约束求解的性能明显高于标准粒子群算法,算法具有良好的优化性能和时间性能.     

A connectivity based clustering algorithm with application to VLSI circuit partitioning

Circuit partitioning is a fundamental problem in very large-scale integration (VLSI) physical design automation. In this brief, we present a new connectivity-based clustering algorithm for VLSI circuit partitioning. The proposed clustering method focuses on capturing natural clusters in a circuit, i.e., the groups of cells that are highly interconnected in a circuit. Therefore, the proposed clustering method can reduce the size of large-scale partitioning problems without losing partitioning solution qualities. The performance of the proposed clustering algorithm is evaluated on a standard set of partitioning benchmarks-ISPD98 benchmark suite. The experimental results show that by applying the proposed clustering algorithm, the previously reported best partitioning solutions from state-of-the-art partitioners are further improved.     

一种VLSI设计到赋权超图的转换系统

本文基于VLSI划分问题的需要,提出了一种VLSI设计到赋权超图转换算法.该算法解决的关键问题是,它读取和遍历Verilog语言描述的树状结构VLSI设计,将其转换为赋权超图并存储为指定的文件存储格式,从而有效地将VLSI划分问题转换为超图划分优化问题.进而,本文给出了VLSI设计到赋权超图的转换系统（VLSI/Hypergraph Converter,VHC）的处理流程图,并在Windows平台下用C＋＋设计实现了VHC系统.实验及分析表明,该系统能正确地将Verilog语言描述的门级CPU测试用例转换为赋权超图,避免了直接在VLSI线网上进行划分,提高了VLSI划分的效率.     

集成电路的模块生成与选择算法

借鉴软件设计中的思想,采用模块化技术是提高大规模集成电路的设计能力和系统芯片开发效率的重要手段.文章首先对现有的模块生成算法进行了全面的分析,在此基础上提出了一新的模块生成算法,此算法可生成一个电路系统的顶点数小于m的所有模块,并且对电路系统以及模块的结构没有限制.本文还提出了一个模块选择算法,此算法可以在满足一定要求的前提下选择一部分模块覆盖整个电路,同时还对算法进行了实验分析.     

Hybrid genetic-paired-permutation algorithm for improved VLSI placement

This paper addresses Very large-scale integration (VLSI) placement optimization, which is important because of the rapid development of VLSI design technologies. The goal of this study is to develop a hybrid algorithm for VLSI placement. The proposed algorithm includes a sequential combination of a genetic algorithm and an evolutionary algorithm. It is commonly known that local search algorithms, such as random forest, hill climbing, and variable neighborhoods, can be effectively applied to NP-hard problem-solving. They provide improved solutions, which are obtained after a global search. The scientific novelty of this research is based on the development of systems, principles, and methods for creating a hybrid (combined) placement algorithm. The principal difference in the proposed algorithm is that it obtains a set of alternative solutions in parallel and then selects the best one. Nonstandard genetic operators, based on problem knowledge, are used in the proposed algorithm. An investigational study shows an objective-function improvement of 13%. The time complexity of the hybrid placement algorithm is O(N²).     

A tree-matching chip

Tree matching is an important problem used for three-dimensional object recognition in image understanding and vision systems. The objective of tree matching is to find the set of nodes at which a pattern tree matches a subject tree. In this paper, we describe the design and implementation of a very large scale integration (VLSI) chip for tree pattern matching. The architecture is based on an iterative algorithm that is mapped to a systolic array computational model and takes O(t(n+a)) time to profess a subject of size n using a processors where a is the length of the largest substring in the pattern and t is the number of substrings in the pattern. The variables and nonvariables of the pattern tree are processed separately, which simplifies the hardware in each processing element. The proposed partitioning strategy is independent of the problem size and allows larger strings to be processed based on the array size. A prototype CMOS VLSI chip has been designed using the Cadence design tools and the simulation results indicate that it will operate at 33.3 MHz     

一种新的基于晶体管级的电路划分算法

随着VLSI电路规模的不断增加,为实现电路并行仿真所做的电路划分算法的质量显得日益重要。鉴于现有算法未能同时保证均衡的分块间规模和最少的互联信号数目,该文提出了一种新的基于晶体管级的电路划分算法。该算法首先通过一个聚合过程对电路网表进行分割,得到一个比较好的初始分割;然后通过平衡分块间规模差异和进一步优化分块间互连线的数目,最终得到理想的电路划分结果。应用该电路划分算法对工业界的实际电路网表进行测试,结果表明:相比于目前普遍使用的COPART算法,该算法在分块间规模的均衡性方面平均改善了25%,在分块间的互联信号数目方面平均减少了18%。     

Reliability enhancement of digital combinational circuits based on evolutionary approach

Reliability has become an integral part of the system design process, especially for those systems with life-critical applications such as aircrafts and spacecraft flight control. The recent rapid growth in demand for highly reliable digital circuits has focused attention on tools and techniques we might use to enhance the reliability of the circuit. In this paper, we present an algorithm to improve the reliability of digital combinational circuits based on evolutionary approach. This method generates a global VHDL file for the selected initial set of components based on inserting multiplexers at the gate inputs of the circuit which helps to perform the simulations in only one session. This simulation framework is combined with single-pass reliability analysis approach to implement the evolutionary algorithm. The search space of the genetic algorithm is limited by the idea of slicing the initial set of components and also circuit partitioning could be used to further overcome the scalability limitations. The framework is applied to a subset of combinational benchmark circuits and our experiments demonstrate that higher reliabilities can be achieved while other factors such as power, speed and area overhead will remain admissible.     

An efficient heuristic for standard-cell placement

A new method is presented for optimization of the one and two-dimensional quadratic assignment problem. The method is suitable for placement problems as they appear in sea-of-gates and standard-cell layout styles for VLSI design. The method is based on recursive partitioning and is a generalization of the method introduced by Kuh et al. It is more flexible than Kuh's method because it does not require a special distribution of the external connections on the boundary of the chip. The time complexity of the algorithm is O(_n Iog²_n). A numerical evaluation of the method is presented, which shows its efficiency for generating near optimal solutions for the quadratic assignment problem as well as for practical standard-cell placement problems.     

An exact algorithm for selecting partial scan flip-flops

We develop anexact algorithm for selecting partial scan flip-flops to break all feedback cycles. We also permit the option of not breaking self-loops. The key ideas that allow us to solve this complex problemexactly for large, practical instances are—an MFVS-preserving graph transformation, a partitioning scheme used in the branch and bound procedure, and pruning techniques based on an integer linear programming formulation of the MFVS problem. We have obtained optimum solutions for all ISCAS'89 benchmark circuits and several production VLSI circuits within reasonable computation time. For example, the optimal number of scan flip-flops required to eliminate all cycles except self-loops in the circuit s38417 is 374. An optimal solution was obtained in 32 CPU seconds on a SUN Sparc 2 workstation.