首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到19条相似文献,搜索用时 218 毫秒
1.
SSTT: Efficient local search for GSI global routing   总被引:6,自引:2,他引:4       下载免费PDF全文
In this paper, a novel global routing algorithm is presented for congestion opti-mization based on efficient local search, named SSTT (search space traversing technology). This method manages to traverse the whole search space. A hybrid optimization strategy is adopted,consisting of three optimization sub-strategies: stochastic optimization, deterministic optimiza-tion and local enumeration optimization, to dynamically reconstruct the problem structure. Thus,“transition” can be made from a local minimum point to reach other parts of the search space,traverse the whole search space, and obtain the global (approximate) optimal routing solution.Since any arbitrary initial routing solution can be used as the start point of the search, the initial-ization in SSTT algorithm is greatly simplified. SSTT algorithm has been tested on both MCNC benchmark circuits and industrial circuits, and the experimental results were compared with those of typical existing algorithms. The experimental results show that SSTT algorithm can obtain the global (approximate) optimal routing solution easily and quickly. Moreover, it can meet the needs of practical applications. The SSTT global routing algorithm gives a general-purpose routing solution.  相似文献   

2.
In this paper,an improved algorithm is proposed for unconstrained global optimization to tackle non-convex nonlinear multivariate polynomial programming problems.The proposed algorithm is based on the Bernstein polynomial approach.Novel features of the proposed algorithm are that it uses a new rule for the selection of the subdivision point,modified rules for the selection of the subdivision direction,and a new acceleration device to avoid some unnecessary subdivisions.The performance of the proposed algorithm is numerically tested on a collection of 16 test problems.The results of the tests show the proposed algorithm to be superior to the existing Bernstein algorithm in terms of the chosen performance metrics.  相似文献   

3.
Backlash-like hysteresis is one of the nonsmooth and multi-valued nonlinearities usually existing in mechanical systems. The traditional identification method is quite difficult to be used to model the systems involved with such complex nonlinearities. In this paper, a nonsmooth recursive identification algorithm for the systems with backlash-like hysteresis is proposed. In this method, the concept of Clarke subgradient is introduced to approximate the gradients at nonsmooth points and the so-called bundle method is used to obtain the optimization search direction in nonsmooth cases. Then, a recursive algorithm based on the idea of bundle method is developed for parameter estimation. After that, the convergence analysis of the algorithm is investigated. Finally, simulation results to validate the proposed method on a simulated mechanical transmission system are presented.  相似文献   

4.
This paper proposes an improved particle swarm optimization (PSO) with iterative chaotic map with infinite collapses (ICMIC) perturbations (ICMICPSO) for global optimization of multimodal functions. The chaotic perturbation generated by the ICMIC is incorporated into the particle's velocity updating rule as self-feedback to make the particles have a larger potential space to fly. With the coefficient of chaotic perturbation decaying, the dynamics of ICMICPSO algorithm is a chaotic dynamics first and then a steepest descent dynamics. The proposed ICMICPSO method as hybrid optimization is tested on several widely used multimodal functions. Numerical results of the proposed algorithm are compared with that of some other Chaotic PSO variants available in the existing literature. The performance studies demonstrate that the effectiveness and efficiency of the proposed ICMICPSO approach are comparably to or better than that of the other CPSO variants for solving the global optimization of multimodal functions.  相似文献   

5.
The arbitrary sized circle packing problem (ACP) is concerned about how to pack a number of arbitrary sized circles into a smallest possible circular container without overlapping. As a classical NP-hard problem, ACP is theoretically important and is often encountered in practical applications. Based on the already existing Quasi-physical method, this paper proposes a hybrid algorithm named GP-TS which combines tabu search with global perturbation to solve the two-dimensional ACP. The Quasi-physical method is a continuous optimization method which is used to obtain a local optimal configuration from any initial configuration. The tabu search procedure iteratively updates the incumbent configuration with its best neighboring configuration according to some forbidden rule and aspiration criterion. If the configuration obtained by the tabu search procedure does not satisfy the constraints, the global perturbation operator is subsequently applied in order that the search jumps out of the current local optimum without destroying the incumbent configuration too much. After that, the tabu search procedure is launched again. GP-TS is performed by repeating this process until the stop criterion is met. Computational experiments based on 3 sets of representative instances show that GP-TS can improve many best known results within reasonable time.  相似文献   

6.
This paper deals with a novel stereo algorithm that can generate accurate dense disparity maps in real time. The algorithm employs an effective cross-based variable support aggregation strategy within a scanline optimization framework. Rather than matching intensities directly, the use of adaptive support aggregation allows for precisely handling the weak textured regions as well as depth discontinuities. To improve the disparity results with global reasoning, we reformulate the energy function on a tree structure over the whole 2D image area, as opposed to dynamic programming of individual scanlines. By applying both intra- and inter-scanline optimizations, the algorithm reduces the typical ’streaking’ artifact while maintaining high computational efficiency. The experimental results are evaluated on the Middlebury stereo dataset, showing that our approach is among the best for all real-time approaches. We implement the algorithm on a commodity graphics card with CUDA architecture, running at about 35 fames/s for a typical stereo pair with a resolution of 384×288 and 16 disparity levels.  相似文献   

7.
LDL-factorization is an efficient way of solving Ax=b for a large symmetric positive definite sparse matrix A.This paper presents a new method that further improves the efficiency of LDL-factorization.It is based on the theory of elimination trees for the factorization factor.It breaks the computations involved in LDL-factorization down into two stages:1) the pattern of nonzero entries of the factor is predicted,and 2) the numerical values of the nonzero entries of the factor are computed.The factor is stored using the form of an elimination tree so as to reduce memory usage and avoid unnecessary numerical operations.The calculation results for some typical numerical examples demonstrate that this method provides a significantly higher calculation efficiency for the one-to-one marketing optimization algorithm.  相似文献   

8.
It is widely accepted that the design of morphological filters,which are optimal in some sense,is a difficult task.In this paper a novel method for optimal learning of morphological filtering parameters(Genetic training algorithm for morphological filters,GTAMF)is presented.GTAMF adopts new crossover and mutation operators called the curved cylinder crossover and master-slave mutaition to achieve optimal filtering parameters in a global searching,Experimental results show that this method is practical,easy to extend,and markedly improves the performances of morphoological filters.The operation of a morphological filter can be divided into two basic problems including morphological operation and structuring element (SE)Selection.The rules for morphological operations are predefined so that the filter‘s properties depend merely on the selection of SE.By means of adaptive optimization training,structureing elements possess the shape and structural characteristics of image targets,and give specific information to SE.Morphological filters formed in this way become certainly intelligent and can provide good filtering results and robust adaptability to image targets with clutter background.  相似文献   

9.
A new approach for simultaneous online identification of unknown time delay and dynamic parameters of discrete-time delay systems is proposed in this paper.The proposed algorithm involves constructing a new generalized regression vector and defining the time delay and the rational dynamic parameters in the same vector.The gradient algorithm is used to deal with the identification problem.The effectiveness of this method is illustrated through simulation.  相似文献   

10.
Research into ant colony algorithms for solving continuous optimization problems forms one of the most significant and promising areas in swarm computation. Although traditional ant algorithms are designed for combinatorial optimization, they have shown great potential in solving a wide range of optimization problems, including continuous optimization. Aimed at solving continuous problems effectively, this paper develops a novel ant algorithm termed "continuous orthogonal ant colony" (COAC), whose pheromone deposit mechanisms would enable ants to search for solutions collaboratively and effectively. By using the orthogonal design method, ants in the feasible domain can explore their chosen regions rapidly and efficiently. By implementing an "adaptive regional radius" method, the proposed algorithm can reduce the probability of being trapped in local optima and therefore enhance the global search capability and accuracy. An elitist strategy is also employed to reserve the most valuable points. The performance of the COAC is compared with two other ant algorithms for continuous optimization -API and CACO by testing seventeen functions in the continuous domain. The results demonstrate that the proposed COAC algorithm outperforms the others.  相似文献   

11.
一种以电性能优化为目标的Steiner树算法   总被引:3,自引:0,他引:3  
洪先龙 《计算机学报》1995,18(4):266-272
本文提出了一种以电性能优化为目标的Steiner树算法,它把从线网的源点到漏点的时间延迟最小作为求解Steiner树的目标,文中首先给出一种多端线网连线延迟模型,然后导出它的上界,它是线网连线总长和从源点到漏点路径长度的函数。  相似文献   

12.
一种新的与线网顺序无关的随机优化总体布线算法   总被引:6,自引:0,他引:6  
针对目前总体布线中仍然存在的3个关键问题;布线结果受布线顺序的影响、总体布线图中拥挤区域的不可预见性、线网连接式样受到算法的限制等,该文提出了一种新的不受线网顺序影响的总体布线算法,并实现了相应的总体布线器RINO-Router。该算法采用随机优化方法来保 证先后被拆线重布的线网有相同的通过拥挤区域的机会,并能得到GRG边的拥挤度估计值;采用高效的Steiner树改造算法构造避开拥挤区域的布线树,采用典型电路实例进行了测试,并将布线结果与基于多商品流算法的总体布线器Matula-Router进行了对比。结果表明,RINO-Router能够在短得多的运行时间内求得质量与Matula-Router相近的总体布线解。  相似文献   

13.
改进的粒子群优化算法在QoS选播路由中的应用   总被引:4,自引:0,他引:4  
QoS选播路由问题是一个非线性的组合优化问题,已被证明是NP完全问题.提出一种基于改进的粒子群优化的多QoS选播路由算法.算法引入一种特殊相加算子,让较差的路径能够不断向较好的路径学习,使算法尽可能向全局最优者靠近;设计一种随机变异算子,通过对全局极值进行随机变异,保证了粒子的多样性,提高了算法跳出局部最优解的能力.实验结果表明,该算法是可行和有效的,能够在资源预留的基础上较好地满足用户对带宽和时延的要求.  相似文献   

14.
PSN(pocket switched network)网络作为一种特殊的DTN(Delay Tolerance Network)网络,除了具有不包含持续端到端连接、高传输时延及节点资源受限的特点以外,具有更强的社会规律性.本文在研究了现有的算法的基础上,提出了一种基于社会信息的路由算法—BridgingCom.为使消息尽快从本地传递到目标节点,我们选择桥接中心度(Bridging Centrality)作为中继节点的选择依据.实验结果表明,与已有相关算法相比,本改进算法能够在网络负载较低的情况下获得较高的传输效率,较低的传输延迟.  相似文献   

15.
针对无线传感器网络中不同业务对服务质量(QoS)的不同需求,提出一种基于离散粒子群优化(DPSO)的无线传感器网络QoS路由(DPSO-QR)算法。算法将路由建立过程抽象为多目标优化过程,以节点间通信的传播损耗、时延、带宽、丢包率为优化目标,利用DPSO算法实现多目标优化,为拥有不同QoS需求的网络业务提供满足其特有需求的优化路由。仿真实验表明:与SAR,EQR算法相比,DPSO-QR算法降低了网络平均端到端时延,减小了丢包率,延长了网络寿命。  相似文献   

16.
针对NDN卫星网络内容传输时延高、丢包率高且请求命中率低的问题,提出了一种基于SDN与NDN的卫星网络多约束路由算法,并命名为SNMcRA。基于SDN的集中控制与全局视图,通过建立多约束路由模型,将链路多约束信息与蚁群算法相结合以求解满足时延、带宽、丢包率多约束的代价最小路径,由节点在包转发的过程中动态完成转发表FIB和待定请求表PIT的构建。实验结果表明,该算法与DSP算法相比时延降低了35%,带宽利用率提升了29%,丢包率降低了17%,并且在请求命中率方面也具有显著优势。  相似文献   

17.
遗传蚁群算法的WSN移动代理路由算法研究   总被引:1,自引:0,他引:1  
针对常用路由优化算法存在收敛速度慢、易陷入局部最优等难题,提出了一种遗传蚁群算法的WSN移动代理路由方法(GA-ACA)。首先利用遗传算法的全局搜索能力快速找到较优解,然后将较优解转换成蚁群算法的初始信息素,最后采用蚁群算法收敛速度快的优点,找到移动代理路由全局最优解。仿真结果表明,相对于其他移动代理路由算法,GA-ACA加快了收敛速度,能在更短的时间内找到最优移动代理路由,减少了平均能量消耗和网络延时,提高了WSN整体性能。  相似文献   

18.
X结构带来物理设计诸多性能的提高,该结构的引入和多层工艺的普及,使得总体布线算法更复杂.为此,在XGRouter布线器的基础上,本文设计了三种有效的加强策略,包括:1)增加新类型的布线方式;2)粒子群优化(Particle swarm optimization,PSO)算法与基于新布线代价的迷宫布线的结合;3)初始阶段中预布线容量的缩减策略,继而引入了多层布线模型,简化了XGRouter的整数线性规划模型,最终构建了一种高性能的X结构多层总体布线器,称为ML-XGRouter.在标准测试电路的仿真实验结果表明,ML-XGRouter相对其他各类总体布线器,在多层总体布线中最重要的优化目标|溢出数和线长总代价两个指标上均取得最佳.  相似文献   

19.
基于禁忌遗传优化的网络拥塞控制算法   总被引:1,自引:0,他引:1       下载免费PDF全文
赵静  孔金生 《计算机工程》2010,36(24):79-80
为解决网络拥塞问题,提出一种基于禁忌遗传优化的网络拥塞控制算法TSGA。该算法将禁忌搜索和遗传算法相结合,以网络资源消耗最小化和网络负载均衡分布为目标,建立多约束QoS路由优化数学模型。仿真实验结果证明,该算法可实现网络拥塞控制,有效提高网络性能。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号