面向机械多级设计的超图生长型二分算法  

Novel Hypergraph Bisectioning Algorithm Based on Vertices-cluster-growing-up in Machine Multilevel Design Problem

作　　者：黎水平[1] 贺建军[1] 

机构地区：[1]武汉理工大学机电学院,武汉430070

出　　处：《武汉理工大学学报》2007年第5期115-119,共5页Journal of Wuhan University of Technology

基　　金：国家自然科学基金(50405024);湖北省自然科学基金(2004ABA03P)

摘　　要：提出了一种新型的在机械多级设计中实现超图二分的生长型分解算法。该算法由生长过程和平衡过程组成。通过提出超图中核心点集和边界点集的划分、种子的选取原则以及顶点的卫星云图等概念和方法,实现了机械多级设计中超图二分生长型算法的生长过程,并以Tabu算法实现了其边界点的平衡过程。对比测试结果表明该算法具有较好的适应性和较高的搜索效率。A novel hypergraph bisectioning algorithm was proposed to solve multilevel design problem where the model of a large-scale design problem was represented by a hypergraph. The algorithm was based on vertices-cluster-growing-up method and included growing-up stage and balancing stage. In growing-up stage, hypergraph vertices were classified into core-vertices cluster and non-core-vertices cluster according to their moving cost, and further the concept of vertex-star-cloud was proposed to help define seed. According to defined criteria of growing-up and stop, a cluster of vertex could be obtained by growing-up process of a seed. In balancing stage, a Tabu searching algorithm was used to fine-tune those non-core vertices to balance the size of clusters. The comparisons with some known algorithms such as FM and KL showed this new algorithm had better problemadapting ability and computational efficiency.

关 键 词：机械多级设计 超图分解 算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]