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.
The assignment of airport resources can significantly affect the quality of service provided by airlines and airports. High quality assignments can support airlines and airports in adhering to published schedules by m...
详细信息
The assignment of airport resources can significantly affect the quality of service provided by airlines and airports. High quality assignments can support airlines and airports in adhering to published schedules by minimising changes or delays while waiting for resources to become available. In this paper, we consider the problem of assigning available baggage sorting stations to flights which have already been scheduled and allocated to stands. A model for the problem is presented, and the different objectives which have to be considered are highlighted. A number of constructive algorithms for sorting station assignments are then presented and their effects are compared and analysed when different numbers of sorting stations are available. It can be observed that appropriate algorithm selection is highly dependent upon whether or not reductions in service time are permitted and upon the flight density in relation to the number of sorting stations. Finally, since these constructive approaches produce different solutions which are better for different trade-offs of the objectives, we utilise these as initial solutions for an evolutionary algorithm as well as for an Integer Linear Programming model in CPLEX. We show that in both cases they are helpful for improving the results which are obtainable within reasonable solution times.
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.
We analyze algorithmic and computational aspects of biological phenomena, such as replication and programmed death, in the context of machine learning. We use two different measures of neuron efficiency to develop mac...
详细信息
We analyze algorithmic and computational aspects of biological phenomena, such as replication and programmed death, in the context of machine learning. We use two different measures of neuron efficiency to develop machine learning algorithms for adding neurons to the system (i.e., replication algorithm) and removing neurons from the system (i.e., programmed death algorithm). We argue that the programmed death algorithm can be used for compression of neural networks and the replication algorithm can be used for improving performance of the already trained neural networks. We also show that a combined algorithm of programmed death and replication can improve the learning efficiency of arbitrary machine learning systems. The computational advantages of the bio-inspired algorithms are demonstrated by training feedforward neural networks on the MNIST dataset of handwritten images.
constructive and destructive parsimonious extreme learning machines (CP-ELM and DP-ELM) were recently proposed to sparsify ELM. In comparison with CP-ELM, DP-ELM owns the advantage in the number of hidden nodes, but i...
详细信息
constructive and destructive parsimonious extreme learning machines (CP-ELM and DP-ELM) were recently proposed to sparsify ELM. In comparison with CP-ELM, DP-ELM owns the advantage in the number of hidden nodes, but it loses the edge with respect to the training time. Hence, in this paper an equivalent measure is proposed to accelerate DP-ELM (ADP-ELM). As a result, ADP-ELM not only keeps the same hidden nodes as DP-ELM but also needs less training time than CP-ELM, which is especially important for the training time sensitive scenarios. The similar idea is extended to regularized ELM (RELM), yielding ADP-RELM. ADP-RELM accelerates the training process of DP-RELM further, and it works better than CP-RELM in terms of the number of hidden nodes and the training time. In addition, the computational complexity of the proposed accelerating scheme is analyzed in theory. From reported results on ten benchmark data sets, the effectiveness and usefulness of the proposed accelerating scheme in this paper is confirmed experimentally. (C) 2015 Elsevier B.V. All rights reserved.
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.
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.
The single container loading problem consists of a container that has to be filled with a set of boxes. The objective of the problem is to maximize the total volume of the loaded boxes. For solving the problem, constr...
详细信息
The single container loading problem consists of a container that has to be filled with a set of boxes. The objective of the problem is to maximize the total volume of the loaded boxes. For solving the problem, constructive approaches are the most successful. A key element of these approaches is related to the selection of the box to load next. In this work, we propose a new evaluation function for ranking boxes. Our function rewards boxes that fit well in the container, taking into account the previously placed ones. To construct a more robust function, we consider some other well-known evaluation criteria such as the volume of the block and the estimated wasted volume in the free space of the container. Our approach shows promising results when compared with other state-of-the-art algorithms on a set of 1600 well known benchmark instances. (C) 2017 Elsevier Ltd. All rights reserved.
This article presents a machine learning method for solving classification and approximation problems. This method uses the divide-and-conquer algorithm design technique (taken from machine learning models based on a ...
详细信息
This article presents a machine learning method for solving classification and approximation problems. This method uses the divide-and-conquer algorithm design technique (taken from machine learning models based on a tree), with the aim of achieving design ease and good results on the training examples and allows semi-global actions on its computational elements (a feature taken from neural networks), with the aim of attaining good generalization and good behavior in the presence of noise in training examples. Finally, some results obtained after solving several problems with a particular implementation of SEPARATE are presented together with their analysis.
In this paper, we study a number of objective functions for training new hidden units in constructive algorithms for multilayer feedforward networks. The aim is to derive a class of objective functions the computation...
详细信息
In this paper, we study a number of objective functions for training new hidden units in constructive algorithms for multilayer feedforward networks. The aim is to derive a class of objective functions the computation of which and the corresponding weight updates can be done in O(N) time, where N is the number of training patterns. Moreover, even though. input weight freezing is applied during the process for computational efficiency, the convergence property of the constructive algorithms using these objective functions is still preserved. We also propose a few computational tricks that can be used to improve the optimization of the objective functions under practical situations. Their relative performance in a set of two-dimensional regression problems is also discussed.
暂无评论