Given a set system (V, S), V = {1, ..., n} and S = {S-1, ..., S-m}, the minimum discrepancy problem is to find a 2-coloring X : V --> {-1, +1}, such that each set is colored as evenly as possible, i.e. find X to mi...
详细信息
ISBN:
(纸本)9780769542447
Given a set system (V, S), V = {1, ..., n} and S = {S-1, ..., S-m}, the minimum discrepancy problem is to find a 2-coloring X : V --> {-1, +1}, such that each set is colored as evenly as possible, i.e. find X to minimize max(j is an element of[m]) vertical bar Sigma(i is an element of Sj) X(i)vertical bar. In this paper we give the first polynomial time algorithms for discrepancy minimization that achieve bounds similar to those known existentially using the so-called Entropy Method. We also give a first approximation-like result for discrepancy. Specifically we give efficient randomized algorithms to: 1) Construct an O(n(1/2)) discrepancy coloring for general sets systems when m = O(n), matching the celebrated result of Spencer [17] up to O(1) factors. More generally, for m >= n, we obtain a discrepancy of O(n(1/2) log (2m/n)). 2) Construct a coloring with discrepancy O (t(1/2) log n), if each element lies in at most t sets. This matches the (non-constructive) result of Srinivasan [19]. 3) Construct a coloring with discrepancy O(lambda log (nm)), where lambda is the hereditary discrepancy of the set system. The main idea in our algorithms is to produce a coloring over time by letting the color of the elements perform a random walk (with tiny increments) starting from 0 until they reach +/-1. At each step the random hops for various elements are correlated by a solution to a semidefinite program, where this program is determined by the current state and the entropy method.
Networked Control Systems (NCS) are used for remote control of distributed or non- co-located systems where the control loop is closed via a communication link. Remote access to industrial robotic systems is one of th...
详细信息
Networked Control Systems (NCS) are used for remote control of distributed or non- co-located systems where the control loop is closed via a communication link. Remote access to industrial robotic systems is one of the application fields where robustness and reliability of the closed loop plays a significant role. Caused by the communication chain in the control loop, there are challenging constraints that can affect the stability and performance of a closed loop. One can consider a large number of difficulties in this type of control systems, for instance unknown delay and packet drop-out. There are already a large number of methods and approaches to handle issues in the NCS and because of increasing interest of the industry, many are still being developed to improve the features of the closed loops over communication networks. This paper summarizes the existing theory of the networked control systems under communication constraints and presents an H∞ synthesis for a simple plant. Finally the results are illustrated, discussed and validated using real measurements from a robotic system.
The single container loading problem is a three-dimensional packing problem in which a container has to be filled with a set of boxes. The objective is to maximize the space utilization of the container. This problem ...
详细信息
The single container loading problem is a three-dimensional packing problem in which a container has to be filled with a set of boxes. The objective is to maximize the space utilization of the container. This problem has wide applications in the logistics industry. In this work, a new constructive approach to this problem is introduced. The approach uses a beam search strategy. This strategy can be viewed as a variant of the branch-and-bound search that only expands the most promising nodes at each level of the search tree. The approach is compared with state-of-the-art algorithms using 16 well-known sets of benchmark instances. Results show that the new approach outperforms all the others for each set of instances. (C) 2013 Elsevier Ltd. All rights reserved.
Algorithmic skeletons in conjunction with list homomorphisms play an important role in formal development of parallel algorithms. We have designed a notion of homomorphism dedicated to bulk synchronous parallelism. In...
详细信息
ISBN:
(纸本)9783642400476
Algorithmic skeletons in conjunction with list homomorphisms play an important role in formal development of parallel algorithms. We have designed a notion of homomorphism dedicated to bulk synchronous parallelism. In this paper we derive two application using this theory: sparse matrix vector multiplication and the all nearest smaller values problem. We implement a support for BSP homomorphism in the Orleans Skeleton Library and experiment it with these two applications.
Previous research has demonstrated that constructive algorithms are powerful methods for training feedforward neural networks. The CasPer algorithm is a constructive neural network algorithm that generates networks fr...
详细信息
ISBN:
(纸本)9781467314909
Previous research has demonstrated that constructive algorithms are powerful methods for training feedforward neural networks. The CasPer algorithm is a constructive neural network algorithm that generates networks from a simple architecture and then expands it. The A_CasPer algorithm is a modified version of the CasPer algorithm which uses a candidate pool instead of a single neuron being trained. This research adds an extension to the A_CasPer algorithm in terms of the network architecture - the Layered_CasPer algorithm. The hidden neurons form as layers in the new version of the network structure which results in less computational cost being required. Beyond the network structure, other aspects of Layered_CasPer are the same as A_CasPer. The Layered_CasPer algorithm extension is benchmarked on a number of classification problems and compared to other constructive algorithms, which are CasCor, CasPer, A_CasPer, and AT_CasPer. It is shown that Layered_CasPer has a better performance on the datasets which have a large number of inputs for classification tasks. The Layered_CasPer algorithm has an advantage over other cascade style constructive algorithms in being more similar in topology to the familiar layered structure of traditional feedforward neural networks.
In this paper we propose a constructive algorithm with adaptive sigmoidal function for designing single hidden layer feedforward neural network (CAASF). The proposed algorithm emphasizes on architectural adaptation an...
详细信息
ISBN:
(纸本)9783037853122
In this paper we propose a constructive algorithm with adaptive sigmoidal function for designing single hidden layer feedforward neural network (CAASF). The proposed algorithm emphasizes on architectural adaptation and functional adaptation during training. This algorithm is a constructive approach to building single hidden layer neural networks dynamically. The activation functions used at non-linear hidden nodes are belonging to the well-defined sigmoidal class and adapted during training. The algorithm determines not only optimum number of hidden nodes, as also optimum sigmoidal function for the non-linear nodes. One simple variant derived from CAASF is where the sigmoidal function used at the hidden nodes is fixed. Both the variants are compared to each other on five regression functions. Simulation results reveal that adaptive sigmoidal function presents several advantages over traditional fixed sigmoid function, resulting in increased flexibility, smoother learning, better convergence and better generalization performance.
Previous research has demonstrated that constructive algorithms are powerful methods for training feedforward neural networks. The CasPer algorithm is a constructive neural network algorithm that generates networks fr...
详细信息
ISBN:
(纸本)9781467314886
Previous research has demonstrated that constructive algorithms are powerful methods for training feedforward neural networks. The CasPer algorithm is a constructive neural network algorithm that generates networks from a simple architecture and then expands it. The A_CasPer algorithm is a modified version of the CasPer algorithm which uses a candidate pool instead of a single neuron being trained. This research adds an extension to the A_CasPer algorithm in terms of the network architecture - the Layered_CasPer algorithm. The hidden neurons form as layers in the new version of the network structure which results in less computational cost being required. Beyond the network structure, other aspects of Layered_CasPer are the same as A_CasPer. The Layered_CasPer algorithm extension is benchmarked on a number of classification problems and compared to other constructive algorithms, which are CasCor, CasPer, A_CasPer, and AT_CasPer. It is shown that Layered_CasPer has a better performance on the datasets which have a large number of inputs for classification tasks. The Layered_CasPer algorithm has an advantage over other cascade style constructive algorithms in being more similar in topology to the familiar layered structure of traditional feedforward neural networks.
This paper considers a flexible flow shop scheduling problem, where at least one production stage is made up of unrelated parallel machines. Moreover, sequence- and machine-dependent setup times are given. The objecti...
详细信息
This paper considers a flexible flow shop scheduling problem, where at least one production stage is made up of unrelated parallel machines. Moreover, sequence- and machine-dependent setup times are given. The objective is to find a schedule that minimizes a convex sum of makespan and the number of tardy jobs in a static flexible flow shop environment. For this problem, a 0-1 mixed integer program is formulated. The problem is, however, a combinatorial optimization problem which is too difficult to be solved optimally for large problem sizes, and hence heuristics are used to obtain good solutions in a reasonable time. The proposed constructive heuristics for sequencing the jobs start with the generation of the representatives of the operating time for each operation. Then some dispatching rules and flow shop makespan heuristics are developed. To improve the solutions obtained by the constructive algorithms, fast polynomial heuristic improvement algorithms based on shift moves and pairwise interchanges of jobs are applied. In addition, metaheuristics are suggested, namely simulated annealing (SA), tabu search (TS) and genetic algorithms. The basic parameters of each metaheuristic are briefly discussed in this paper. The performance of the heuristics is compared relative to each other on a set of test problems with up to 50 jobs and 20 stages and with an optimal solution for small-size problems. We have found that among the constructive algorithms the insertion-based approach is superior to the others, whereas the proposed SA algorithms are better than TS and genetic algorithms among the iterative metaheuristic algorithms. (C) 2007 Elsevier Ltd. All rights reserved.
In this paper, we deepen the theoretical study of the geometric structure of a balanced complex polytope (b.c.p.), which is the generalization of a real centrally symmetric polytope to the complex space. We also propo...
详细信息
In this paper, we deepen the theoretical study of the geometric structure of a balanced complex polytope (b.c.p.), which is the generalization of a real centrally symmetric polytope to the complex space. We also propose a constructive algorithm for the representation of its facets in terms of their associated linear functionals. The b.c.p.s are used, for example, as a tool for the computation of the joint spectral radius of families of matrices. For the representation of real polytopes, there exist well-known algorithms such as, for example, the Beneath-Beyond method. Our purpose is to modify and adapt this method to the complex case by exploiting the geometric features of the b.c.p. However, due to the significant increase in the difficulty of the problem when passing from the real to the complex case, in this paper, we confine ourselves to examine the two-dimensional case. We also propose an algorithm for the computation of the norm the unit ball of which is a b.c.p.
This paper presents a new constructive algorithm to design multilayer perceptron networks used its classifiers. The resulting networks are able to classify patterns defined in a real domain. The proposed procedure all...
详细信息
This paper presents a new constructive algorithm to design multilayer perceptron networks used its classifiers. The resulting networks are able to classify patterns defined in a real domain. The proposed procedure allows us to automatically determine both the number of neurons and the synaptic weights of networks with a single hidden layer. The approach is based on linear programming. It avoids the typical local minima problems of error back propagation and assures convergence of the method. Furthermore, it will be shown in this paper that the presented procedure leads to single-hidden layer neural networks able to solve any problem in classifying a finite number of patterns. The performances of the proposed algorithm have been tested on some benchmark problems, and they have been compared with those of different approaches. (c) 2007 Elsevier B.V. All rights reserved.
暂无评论