The binary decision diagrams （BDDs） can give canonical representation to Boolean functions; they have wide applications in the design and verification of digital systems. A new method based on cultural algorithms fo...The binary decision diagrams （BDDs） can give canonical representation to Boolean functions; they have wide applications in the design and verification of digital systems. A new method based on cultural algorithms for minimizing the size of BDDs is presented in this paper. First of all, the coding of an individual representing a BDDs is given, and the fitness of an individual is defined. The population is built by a set of the individuals. Second, the implementations based on cultural algorithms for the minimization of BDDs, i.e., the designs of belief space and population space, and the designs of acceptance function and influence function, are given in detail. Third, the fault detection approaches using BDDs for digital circuits are studied. A new method for the detection of crosstalk faults by using BDDs is presented. Experimental results on a number of digital circuits show that the BDDs with small number of nodes can be obtained by the method proposed in this paper, and all test vectors of a fault in digital circuits can also be produced.展开更多
The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decis...The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decision diagram (ADD) or variants thereof provides canonical forms to represent and manipulate Boolean functions and pseudo-Boolean functions efficiently. ADD and OBDD-based symbolic algorithms give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic ADD formulation and algorithm for maximum weighted matching in bipartite graphs. The symbolic algorithm implements the Hungarian algorithm in the context of ADD and OBDD formulation and manipulations. It begins by setting feasible labelings of nodes and then iterates through a sequence of phases. Each phase is divided into two stages. The first stage is building equality bipartite graphs, and the second one is finding maximum cardinality matching in equality bipartite graph. The second stage iterates through the following steps: greedily searching initial matching, building layered network, backward traversing node-disjoint augmenting paths, updating cardinality matching and building residual network. The symbolic algorithm does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Simulation experiments indicate that symbolic algorithm is competitive with traditional algorithms.展开更多
The evaluation algorithm and the application of the influence diagram were surveyed, which argues that to construct an explicit, compact and objective influence diagram is of the most importance. There are two suggest...The evaluation algorithm and the application of the influence diagram were surveyed, which argues that to construct an explicit, compact and objective influence diagram is of the most importance. There are two suggested ways for realization of the influence diagram: introducing the achievements of the modern psychology, cognitive science, behavior science, and so on to represent and solve uncertainty to build a well-constructed influence diagram; based on the observed data to build an influence diagram. Also, the limitations of the influence diagram were analyzed, such as that it cannot deal with asymmetric problems efficiently, cannot picture dynamic problems, cannot model the problems with a limitless horizon, and ther is no highly efficient algorithm. And some potential methods to overcome these limitations were pointed out.展开更多
Aqueous E pH Diagram is an essential tool for analyzing hydrometallurgical and corrosion processes. Due to the requirements for environmental protection and energy saving in recent years, waste water processing a...Aqueous E pH Diagram is an essential tool for analyzing hydrometallurgical and corrosion processes. Due to the requirements for environmental protection and energy saving in recent years, waste water processing and hydrometallurgical process of concentrate have been greatly developed. The construction of E pH diagrams has turned to multi component systems. However, there are some limits in plotting such diagrams. There is only one diagram for one multi component system, which can not reflect the truth of the aqueous reaction. In the paper, a new computation method is proposed to construct E pH diagrams. Component activity term is used to determine the boundary of stable areas. For the multi component systems, different atom ratios of elements have been taken into account. M S H 2O system is chosen to study since it is of importance in metallurgical solution. Compared with conventional methods, the algorithm is simple and conforms to real conditions.展开更多
In the optimization of train diagrams, selecting the arrival and departure paths of the through gains has a great impact on the dwell time at district stations. In this paper, on the basis of train paths and the throu...In the optimization of train diagrams, selecting the arrival and departure paths of the through gains has a great impact on the dwell time at district stations. In this paper, on the basis of train paths and the through train connection time standard at district stations, we built a mathematical model aiming at minimizing dwell time of through trains at two adjacent district stations, and then converted this into a network flow model to which is added a source and a sink node. Then, we propose a new algorithm for solving the network flow model based on the minimum-cost flow algorithm. A case study for through trains from the Guiyang South Railway Station to the Chongqing West Railway Station shows that the algorithm is reliable and efficient for solving the problem of through train connections, and there is a reduction in the total dwell time that the through trains spend at two adjacent district stations.展开更多
基金supported by Natural Science Foundation of Guangdong Provincial of China (No.7005833)
文摘The binary decision diagrams （BDDs） can give canonical representation to Boolean functions; they have wide applications in the design and verification of digital systems. A new method based on cultural algorithms for minimizing the size of BDDs is presented in this paper. First of all, the coding of an individual representing a BDDs is given, and the fitness of an individual is defined. The population is built by a set of the individuals. Second, the implementations based on cultural algorithms for the minimization of BDDs, i.e., the designs of belief space and population space, and the designs of acceptance function and influence function, are given in detail. Third, the fault detection approaches using BDDs for digital circuits are studied. A new method for the detection of crosstalk faults by using BDDs is presented. Experimental results on a number of digital circuits show that the BDDs with small number of nodes can be obtained by the method proposed in this paper, and all test vectors of a fault in digital circuits can also be produced.
文摘The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decision diagram (ADD) or variants thereof provides canonical forms to represent and manipulate Boolean functions and pseudo-Boolean functions efficiently. ADD and OBDD-based symbolic algorithms give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic ADD formulation and algorithm for maximum weighted matching in bipartite graphs. The symbolic algorithm implements the Hungarian algorithm in the context of ADD and OBDD formulation and manipulations. It begins by setting feasible labelings of nodes and then iterates through a sequence of phases. Each phase is divided into two stages. The first stage is building equality bipartite graphs, and the second one is finding maximum cardinality matching in equality bipartite graph. The second stage iterates through the following steps: greedily searching initial matching, building layered network, backward traversing node-disjoint augmenting paths, updating cardinality matching and building residual network. The symbolic algorithm does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Simulation experiments indicate that symbolic algorithm is competitive with traditional algorithms.
文摘针对现有基于数据驱动的随机子空间(data-driven stochastic subspace identification,DATA-SSI)算法存在的不足,无法实现稳定图中真假模态的智能化筛选,提出了一种新的模态参数智能化识别算法。首先通过引入滑窗技术来实现对输入信号的合理划分,以避免虚假模态和模态遗漏现象的出现;其次通过引入OPTICS(ordering points to identify the clustering structure)密度聚类算法实现稳定图中真实模态的智能化筛选,最后将所提算法运用于某实际大型斜拉桥主梁结构的频率和模态振型识别过程中。结果表明,所提改进算法识别的频率值结果与理论值(MIDAS有限元结果)以及实际值(现场动力特性实测结果)间的误差均在5%以内,且识别的模态振型图与理论模态振型图具有很高的相似性。
基金NationalScienceFoundationofChina (No .70 2 72 0 0 2 )
文摘The evaluation algorithm and the application of the influence diagram were surveyed, which argues that to construct an explicit, compact and objective influence diagram is of the most importance. There are two suggested ways for realization of the influence diagram: introducing the achievements of the modern psychology, cognitive science, behavior science, and so on to represent and solve uncertainty to build a well-constructed influence diagram; based on the observed data to build an influence diagram. Also, the limitations of the influence diagram were analyzed, such as that it cannot deal with asymmetric problems efficiently, cannot picture dynamic problems, cannot model the problems with a limitless horizon, and ther is no highly efficient algorithm. And some potential methods to overcome these limitations were pointed out.
文摘Aqueous E pH Diagram is an essential tool for analyzing hydrometallurgical and corrosion processes. Due to the requirements for environmental protection and energy saving in recent years, waste water processing and hydrometallurgical process of concentrate have been greatly developed. The construction of E pH diagrams has turned to multi component systems. However, there are some limits in plotting such diagrams. There is only one diagram for one multi component system, which can not reflect the truth of the aqueous reaction. In the paper, a new computation method is proposed to construct E pH diagrams. Component activity term is used to determine the boundary of stable areas. For the multi component systems, different atom ratios of elements have been taken into account. M S H 2O system is chosen to study since it is of importance in metallurgical solution. Compared with conventional methods, the algorithm is simple and conforms to real conditions.
文摘In the optimization of train diagrams, selecting the arrival and departure paths of the through gains has a great impact on the dwell time at district stations. In this paper, on the basis of train paths and the through train connection time standard at district stations, we built a mathematical model aiming at minimizing dwell time of through trains at two adjacent district stations, and then converted this into a network flow model to which is added a source and a sink node. Then, we propose a new algorithm for solving the network flow model based on the minimum-cost flow algorithm. A case study for through trains from the Guiyang South Railway Station to the Chongqing West Railway Station shows that the algorithm is reliable and efficient for solving the problem of through train connections, and there is a reduction in the total dwell time that the through trains spend at two adjacent district stations.
