Performance evaluation for a transportation system in stochastic case

In a single-commodity multistate flow network, the arc capacity is stochastic and thus the system capacity (i.e. the maximum flow from the source to the sink) is not a fixed number. This paper constructs a multicommodity multistate flow network with weighted capacity allocation to model a transportation system. Each arc with cost attribute has several possible capacities. The capacity weight, the consumed amount of arc capacity by per commodity, varies with the arcs and types of commodity. We define the system capacity as a demand vector d if the system fulfills at most d. The addressed problem in this work is to measure the service quality of a transportation system. We propose a performance index, the probability that the upper bound of the system capacity equals a demand vector d subject to the budget constraint. A simple algorithm based on minimal cuts is presented to generate all (d,B)-MC that are the maximal capacity vectors meeting exactly the demand d under the budget B. The proposed performance index can be subsequently evaluated in terms of such (d,B)-MC.     

Search for MC in modified networks

In this paper, first we develop an intuitive algorithm using the shortest path based upon the reformation of all MCs in the original network. Next, the computational complexity of the proposed algorithm is analyzed and compared with the existing methods. One computer example is illustrated to show how all MCs are generated in a modified network based upon reformation of all of the MCs of the corresponding original network.Scope and purposeA method is proposed to search for all minimal cuts (MCs) in a network (modified networks) obtained by modifying the original network. It can be used for reliability analysis of various modifications in an existing network for network expansion or reinforcement evaluation and planning. Analysis of our algorithm and comparison to existing best-known algorithms shows that our proposed method has the following advantages: (1) it can be used to search for all MCs without knowing all minimal paths (MPs) and MCs in advance. (2) it is simple and more effective in finding and verifying MC candidates in modified networks than the existing methods. and (3) our method is easier to understand and implement.     

Unreliability evaluation for a limited-flow network with failed nodes subject to the budget constraint

This paper concentrates on a limited-flow network in which each node and branch has a designated capacity, which will have different lower levels due to various partial and complete failures. We try to evaluate the system unreliability that the maximum flow of the network is less than or equal to the demand d without exceeding the budget B. First, a simple algorithm in terms of minimal cuts is proposed to generate all (d, B)-MCs in order to evaluate the system unreliability. A computer example is shown to illustrate the solution procedure.     

Dictionary learning for VQ feature extraction in ECG beats classification

Vector quantization(VQ) can perform efficient feature extraction from electrocardiogram (ECG) with the advantages of dimensionality reduction and accuracy increase. However, the existing dictionary learning algorithms for vector quantization are sensitive to dirty data, which compromises the classification accuracy. To tackle the problem, we propose a novel dictionary learning algorithm that employs k-medoids cluster optimized by k-means++ and builds dictionaries by searching and using representative samples, which can avoid the interference of dirty data, and thus boost the classification performance of ECG systems based on vector quantization features. We apply our algorithm to vector quantization feature extraction for ECG beats classification, and compare it with popular features such as sampling point feature, fast Fourier transform feature, discrete wavelet transform feature, and with our previous beats vector quantization feature. The results show that the proposed method yields the highest accuracy and is capable of reducing the computational complexity of ECG beats classification system. The proposed dictionary learning algorithm provides more efficient encoding for ECG beats, and can improve ECG classification systems based on encoded feature.     

Trace ratio criterion based generalized discriminative learning for semi-supervised dimensionality reduction

Dealing with high-dimensional data has always been a major problem in many pattern recognition and machine learning applications. Trace ratio criterion is a criterion that can be applicable to many dimensionality reduction methods as it directly reflects Euclidean distance between data points of within or between classes. In this paper, we analyze the trace ratio problem and propose a new efficient algorithm to find the optimal solution. Based on the proposed algorithm, we are able to derive an orthogonal constrained semi-supervised learning framework. The new algorithm incorporates unlabeled data into training procedure so that it is able to preserve the discriminative structure as well as geometrical structure embedded in the original dataset. Under such a framework, many existing semi-supervised dimensionality reduction methods such as SDA, Lap-LDA, SSDR, SSMMC, can be improved using our proposed framework, which can also be used to formulate a corresponding kernel framework for handling nonlinear problems. Theoretical analysis indicates that there are certain relationships between linear and nonlinear methods. Finally, extensive simulations on synthetic dataset and real world dataset are presented to show the effectiveness of our algorithms. The results demonstrate that our proposed algorithm can achieve great superiority to other state-of-art algorithms.     

On computing the diameter of a point set in high dimensional Euclidean space

We consider the problem of computing the diameter of a set of n points in d-dimensional Euclidean space under Euclidean distance function. We describe an algorithm that in time O(dnlogn+n²) finds with high probability an arbitrarily close approximation of the diameter. For large values of d the complexity bound of our algorithm is a substantial improvement over the complexity bounds of previously known exact algorithms. Computing and approximating the diameter are fundamental primitives in high dimensional computational geometry and find practical application, for example, in clustering operations for image databases.     

m/nCCS: linear consecutively connected systems subject to combined gap constraints

Motivated by practical applications (e.g. flow transfer systems, electromagnetic accelerating systems and defense systems), in this paper, we consider combined gap constraints in modelling and analysing linear multistate consecutively connected systems (LMCCS). The system has linearly ordered nodes. To provide certain connectivity among these nodes required by the system functionality, some of them host statistically independent multistate connection elements (MCEs). Each MCE is used to provide a connection between its host and a random number of next nodes according to a known probability mass function. The system fails if it contains at least m nodes not connected with any previous node or at least n ≤ m consecutive nodes not connected with any previous node. In other words, the system functions as long as the number of single-node gaps is less than m and the size of any consecutive gap is smaller than n. Such systems with the combined gap constraints are referred to as m/nCCS. An algorithm based on universal generating functions is proposed for the reliability evaluation of m/nCCS and its computational complexity is analysed. Based on the suggested reliability evaluation algorithm, importance analysis is also performed for m/nCCS, which can assist in identifying the most influential elements or weakness of the system design. Illustrative examples are provided.     

Fast k-nearest neighbor search algorithm based on pyramid structure of wavelet transform and its application to texture classification

Traditional fast k-nearest neighbor search algorithms based on pyramid structures need either many extra memories or long search time. This paper proposes a fast k-nearest neighbor search algorithm based on the wavelet transform, which exploits the important information hiding in the transform coefficients to reduce the computational complexity. The study indicates that the Haar wavelet transform brings two kinds of important pyramids. Two elimination criteria derived from the transform coefficients are used to reject those impossible candidates. Experimental results on texture classification verify the effectiveness of the proposed algorithm.     

A New and Fast Implementation of Orthogonal LDA Algorithm and Its Incremental Extension

Linear discriminant analysis (LDA) is one of the most popular dimension reduction methods and has been widely used in many applications. In the last decades many LDA-based dimension reduction algorithms have been reported. Among these methods, orthogonal LDA (OLDA) is a famous one and several different implementations of OLDA have been proposed. In this paper, we propose a new and fast implementation of OLDA. Compared with the other OLDA implementations, our proposed implementation of OLDA is the fastest one when the dimensionality d is larger than the sample size n. Then, based on our proposed implementation of OLDA, we present an incremental OLDA algorithm which can accurately update the projection matrix of OLDA when new samples are added into the training set. The effectiveness of our proposed new OLDA algorithm and its incremental version are demonstrated by some real-world data sets.     

An ACO algorithm for makespan minimization in parallel batch machines with non-identical job sizes and incompatible job families

We study the problem of scheduling a set of N jobs with non-identical job sizes from F different families on a set of M parallel batch machines; the objective is to minimize the makespan. The problem is known to be NP-hard. A meta-heuristic based on Max–Min Ant System (MMAS) is presented. The performance of the algorithm is compared with several previously studied algorithms by computational experiments. According to our results, the average distance between the solutions found by our proposed algorithm and the lower bounds is about 4% less than that of the best of all the compared algorithms, demonstrating that our algorithm outperforms the previously studied algorithms.     

Toward High-Performance Delta-Based Iterative Processing with a Group-Based Approach

Many systems have been built to employ the delta-based iterative execution model to support iterative algorithms on distributed platforms by exploiting the sparse computational dependencies between data items of these iterative algorithms in a synchronous or asynchronous approach. However, for large-scale iterative algorithms, existing synchronous solutions suffer from slow convergence speed and load imbalance, because of the strict barrier between iterations; while existing asynchronous approaches induce excessive redundant communication and computation cost as a result of being barrier-free. In view of the performance trade-off between these two approaches, this paper designs an efficient execution manager, called Aiter-R, which can be integrated into existing delta-based iterative processing systems to efficiently support the execution of delta-based iterative algorithms, by using our proposed group-based iterative execution approach. It can efficiently and correctly explore the middle ground of the two extremes. A heuristic scheduling algorithm is further proposed to allow an iterative algorithm to adaptively choose its trade-off point so as to achieve the maximum efficiency. Experimental results show that Aiter-R strikes a good balance between the synchronous and asynchronous policies and outperforms state-of-the-art solutions. It reduces the execution time by up to 54.1% and 84.6% in comparison with existing asynchronous and the synchronous models, respectively.

     

A new algorithm for computing the minimum Hausdorff distance between two point sets on a line under translation

To determine the similarity of two point sets is one of the major goals of pattern recognition and computer graphics. One widely studied similarity measure for point sets is the Hausdorff distance. So far, various computational methods have been proposed for computing the minimum Hausdorff distance. In this paper, we propose a new algorithm to compute the minimum Hausdorff distance between two point sets on a line under translation, which outperforms other existing algorithms in terms of efficiency despite its complexity of O((m+n)lg(m+n)), where m and n are the sizes of two point sets.     

A variable step-size selective partial update LMS algorithm

Selective partial update of the adaptive filter coefficients has been a popular method for reducing the computational complexity of least mean-square (LMS)-type adaptive algorithms. These algorithms use a fixed step-size that forces a performance compromise between fast convergence speed and small steady state misadjustment. This paper proposes a variable step-size (VSS) selective partial update LMS algorithm, where the VSS is an approximation of an optimal derived one. The VSS equations are controlled by only one parameter, and do not require any a priori information about the statistics of the system environment. Mean-square performance analysis will be provided for independent and identically distributed (i.i.d.) input signals, and an expression for the algorithm steady state excess mean-square error (MSE) will be presented. Simulation experiments are conducted to compare the proposed algorithm with existing full-update VSS LMS algorithms, which indicate that the proposed algorithm performs as well as these algorithms while requiring less computational complexity.     

Optimal resource assignment to maximize multistate network reliability for a computer network

Computer network is a major tool to transmit data in our modern society. How to evaluate and enhance network reliability is thus an important issue for organizations, especially to maximize network reliability. A computer network is a multistate network in which each edge has several possible capacities with a probability distribution and may fail. The multistate network reliability is the probability that the maximal flow is no less than a given demand. From the standpoint of quality management, a further problem is to reassign the existing resources for maximizing multistate network reliability without changing the network topology. Hence, this paper focuses on the resource assignment problem to propose an efficient approach based on the simple genetic algorithm. In which, a resource assignment is represented as a chromosome and the corresponding multistate network reliability is the fitness value of the chromosome. The experimental results show that the proposed algorithm can derive the optimal resource assignment in a reasonable time.     

A hybrid ant-tabu algorithm for solving a multistate flow network reliability maximization problem

Network reliability optimization for multistate flow networks (MFN) is an important issue for many system supervisors. Network reliability maximization for an MFN by determining the optimal component assignment, where a set of multistate components are ready to be assigned to the network, is a common problem. Previous research solved this problem by developing and applying genetic algorithm. Ant colony optimization (ACO) finds a good solution quickly by utilizing the experience of the proceeding ant but sometimes falls into local optimum. Tabu search (TS) adopts a tabu list to avoid searching in the same direction, and thus it explores other possible solutions. This strategy enlarges the search space. Therefore, we propose a hybrid ant-tabu (HAT) algorithm integrating the advantages of ACO and TS to solve this problem, where network reliability is evaluated in terms of minimal paths (MPs) and Recursive Sum of Disjoint Products. Experimental (RSDP) results show that the proposed HAT has better computational efficiency than several soft computing algorithms for networks with more than six MPs or 10 arcs.     

Reliable workflow scheduling with less resource redundancy

We examine the problem of reliable workflow scheduling with less resource redundancy. As scheduling workflow applications in heterogeneous systems, either for optimizing the reliability or for minimizing the makespan, are NP-Complete problems, we alternatively find schedules for meeting specific reliability and deadline requirements. First, we analyze the reliability of a given schedule using two important definitions: Accumulated Processor Reliability (APR) and Accumulated Communication Reliability (ACR). Second, inspired by the reliability analysis, we present three scheduling algorithms: RR algorithm schedules least Resources to meet the Reliability requirement; DRR algorithm extends RR by further considering the Deadline requirement; and dynamic algorithm schedules tasks dynamically: It avoids the “Chain effect” caused by uncertainties on the task execution time estimates, and relieves the impact from the inaccuracy on failure estimation. Finally, the empirical evaluation shows that our algorithms can save a significant amount of computation and communication resources when performing a similar reliability compared to Fault-Tolerant-Scheduling-Algorithm (FTSA) algorithm.     

Optimal and efficient filtering algorithms for table constraints

Filtering algorithms for table constraints can be classified in two categories: constraint-based and value-based. In the constraint-based approaches, the propagation queue only contains information on the constraints that must be reconsidered. For the value-based approaches, the propagation queue also contains information on the removed values. This paper proposes five efficient value-based algorithms for table constraints. Two of them (AC5TCOpt-Tr and AC5TCOpt-Sparse) are proved to have an optimal time complexity of O(r·t+r·d) per table constraint. Substantial experimental results are presented. An empirical analysis is conducted on the effect of the arity of the tables. The experiments show that our propagators are the best when the arity of the table is 3 or 4. Indeed, on instances containing only binary constraints, our algorithms are outperformed by classical AC algorithm AC3rm. AC3rm is dedicated to binary constraints. However, all our algorithms outperform existing state-of-the-art constraint based STR2+ and MDD ^c and the optimal value-based STR3 algorithms on those instances. On instances with small arity tables (up to arity 4), all our algorithms are generally faster than STR2+, MDD ^c and than STR3. AC5TCOpt-Sparse is globally the best propagator on those benchmarks. On benchmarks containing large arity tables (arity 5 or more), each of the three existing state-of-the-art algorithms is the winning strategy on one different benchmark.     

A New Decision-Diagram-Based Method for Efficient Analysis on Multistate Systems

Multistate systems can model many practical systems in a wide range of real applications. A distinct characteristic of these systems is that the systems and their components may assume more than two levels of performance (or states), varying from perfect operation to complete failure. The nonbinary property of multistate systems and their components makes the analysis of multistate systems difficult. This paper proposes a new decision-diagram-based method, called multistate multivalued decision diagrams (MMDD), for the analysis of multistate systems with multistate components. Examples show how the MMDD models are generated and evaluated to obtain the system-state probabilities. The MMDD method is compared with the existing binary decision diagram (BDD)-based method. Empirical results show that the MMDD method can offer less computational complexity and simpler model evaluation algorithm than the BDD-based method.     

Manifold-ranking based retrieval using k-regular nearest neighbor graph

Manifold-ranking is a powerful method in semi-supervised learning, and its performance heavily depends on the quality of the constructed graph. In this paper, we propose a novel graph structure named k-regular nearest neighbor (k-RNN) graph as well as its constructing algorithm, and apply the new graph structure in the framework of manifold-ranking based retrieval. We show that the manifold-ranking algorithm based on our proposed graph structure performs better than that of the existing graph structures such as k-nearest neighbor (k-NN) graph and connected graph in image retrieval, 2D data clustering as well as 3D model retrieval. In addition, the automatic sample reweighting and graph updating algorithms are presented for the relevance feedback of our algorithm. Experiments demonstrate that the proposed algorithm outperforms the state-of-the-art algorithms.     

Analytical solution methods for the fuzzy weighted average

For the fuzzy weighted average (FWA), despite various discrete solution algorithms and their improvements, attempts at analytical solutions are very rare. This paper provides an analytical solution method for the FWA based on the conclusions of the Karnik–Mendel (KM) algorithm. Compared with the two current popular kinds of α-cut based computational methods for the FWA (mathematical programming transformations and direct iterate computations), our method is precise, and, has a concise structure, efficient computation process, and sound theoretical proofs. We propose two algorithms for computing the analytical solution of the FWA. Two numerical examples illustrate our proposed approach.