A PDP constructive algorithm for system modelling

A new constructive algorithm is presented for building neural networks that learn to reproduce output temporal sequences based on one or several input sequences. This algorithm builds a network for the task of system modelling, dealing with continuous variables in the discrete time domain. The constructive scheme makes it user independent. The network's structure consists of an ordinary set and a classification set, so it is a hybrid network like that of Stokbro et al. [6], but with a binary classification. The networks can easily be interpreted, so the learned representation can be transferred to a human engineer, unlike many other network models. This allows for a better understanding of the system structure than just its simulation. This constructive algorithm limits the network complexity automatically, hence preserving extrapolation capabilities. Examples with real data from three totally different sources show good performance and allow for a promising line of research.     

Computer-aided design of P or PI plus rate feedback compensators for linear systems

A computer-aided solution for the gains of P or PI plus rate feedback compensators based on an exact model-matching criterion is developed. The corresponding Matlab functions are developed, and the software listings are given. Using the developed design tool, control engineers are able to obtain P or PI plus rate feedback gains much more quickly than traditional methods of design. Demonstration example problems for control of linear plants are presented, and results are compared with those obtained by other approaches reported in the open literature.     

Combined frequency and time domain technique for the design of compensators for non-linear feedback control systems

Computer based methods are developed for the analysis, synthesis and design of linear compensators for a wide class of single-loop non-linear feedback systems characterized by a separable non-linear element of any general multivalued form. Preliminary analysis is performed in the complex frequency domain applying approximate analytical methods to predict and quantify possible modes of limit cycle operation. Graphical displays are used to determine initial compensator structure which will ensure the avoidance of the critical region in this domain. Subsequently, a numerical synthesis procedure is applied to adjusting the compensator parameters to meet a set of additional time domain functional subject to specified system constraints and, if possible, the absence of autonomous limit-cycle operation.     

A route set construction algorithm for the transit network design problem

The transit network design problem (TNDP) aims to determine a set of bus routes for a public transportation system, which must be convenient from the viewpoints of both users (people who use public transportation) and operators (companies who own the resources to give the service). This article presents a constructive algorithm for the TNDP. It is specially designed to produce a set of routes that fulfils demand covering constraints, while taking into account the interests of both users and operators. Its general structure is inspired in the Route Generation Algorithm (RGA) of Baaj and Mahmassani, where its original expansion of routes by inserting individual vertices is replaced by a strategy of insertion of pairs of vertices. The algorithm proposed, called Pair Insertion Algorithm (PIA) can be used to generate initial solutions for a local improvement or evolutionary algorithm, as well as to complete an unfeasible solution with respect to demand covering constraints. Numerical results comparing PIA with RGA over a real test case show that both algorithms produce solutions with similar quality from the users viewpoint (in terms of in-vehicle travel time), while the former produces better solutions from the operators viewpoint (in terms of number of routes and total route duration) and requires a higher execution time. Since the TNDP arises in a context of strategic planning, a solution that reduces the operation cost of the system is highly desirable, even though it takes more time to be computed. The experimental study of the proposed algorithm also shows its ability to produce diverse solutions in both decision and objective spaces; this is a useful property when looking at the use of PIA as a subroutine in the context of another algorithm such as metaheuristics, in particular for a multi-objective problem like TNDP.     

On the design,robustness, implementation and use of quasi-linear feedback compensators

A quasi-linear feedback compensator is one in which its poles depend in an appropriate way on its gain. The reason for introducing this new concept was the desire to remove the limitation to performance imposed by a plant with more than one pole in excess of its zeros. In this article it is shown that this objective is realized for plants with zeros in the left half of the complex plane. The consequences are surprising. In time domain it is possible to track arbitrarily fast a class of reference inputs despite a large class of disturbances and uncertainty in plant parameters. The response is non-oscillatory for high enough compensator gains, which is explained by the automatic adaptation of the closed loop poles to stability and stability margins for such gains. And in frequency domain the phase margin tends to 90° while the gain margin and crossover frequency become unlimited.

Technically the design procedure of quasi-linear compensators presented here is based on our theoretical result concerning the asymptotic behaviour of the roots of certain polynomials in a complex variable which depend also on a large positive parameter.

We also show how to implement such quasi-linear compensators in practical feedback control schemes, and their use at lower gains which is the case of most industrial applications.     

A constructive algorithm for binary neural networks: the oil-spot algorithm.

This paper presents a constructive training algorithm for supervised neural networks. The algorithm relies on a topological approach, based on the representation of the mapping of interest onto the binary hypercube of the input space. It dynamically constructs a two-layer neural network by involving successively binary examples. A convenient treatment of real-valued data is possible by means of a suitable real-to-binary codification. In the case of target functions that have efficient halfspace union representations, simulations show the constructed networks result optimized in terms of number of neurons.     

A note on feedback compensators in optimal linear systems

Two basic methods for designing feedback compensators which may be used to achieve arbitrary closed-loop pole positions are now available. This correspondence shows that when each method is used within the framework of optimal control the same compensator structure results, but the more standard approach using a state estimator and a linear law appears to be the more attractive from the information now available.     

Computational design techniques for reduced-order compensators

The authors propose two computational techniques for the pole-placement problem using reduced-order compensators. Computationally efficient algorithms are presented for the observer-based compensator and the Brasch-Pearson compensator. The key tool for these algorithms is the concept of two coupled Sylvester equations, the solutions of which completely characterize the desired reduced-order compensators     

Improved FPT algorithm for feedback vertex set problem in bipartite tournament

We present an O(k³n²+n³) time FPT algorithm for the feedback vertex set problem in a bipartite tournament on n vertices with integral weights. This improves the previously best known O(k^3.12n⁴) time FPT algorithm for the problem.     

A constructive algorithm for training cooperative neural network ensembles

Presents a constructive algorithm for training cooperative neural-network ensembles (CNNEs). CNNE combines ensemble architecture design with cooperative training for individual neural networks (NNs) in ensembles. Unlike most previous studies on training ensembles, CNNE puts emphasis on both accuracy and diversity among individual NNs in an ensemble. In order to maintain accuracy among individual NNs, the number of hidden nodes in individual NNs are also determined by a constructive approach. Incremental training based on negative correlation is used in CNNE to train individual NNs for different numbers of training epochs. The use of negative correlation learning and different training epochs for training individual NNs reflect CNNEs emphasis on diversity among individual NNs in an ensemble. CNNE has been tested extensively on a number of benchmark problems in machine learning and neural networks, including Australian credit card assessment, breast cancer, diabetes, glass, heart disease, letter recognition, soybean, and Mackey-Glass time series prediction problems. The experimental results show that CNNE can produce NN ensembles with good generalization ability.     

A constructive bin-oriented heuristic for the two-dimensional bin packing problem with guillotine cuts

A new heuristic algorithm for solving the two-dimensional bin-packing problem with guillotine cuts (2DBP|?|G)$(2\mathrm{DBP}|?|\mathrm{G})$ is presented. The heuristic constructs a solution by packing a bin at a time. Central to the adopted solution scheme is the principle of average-area sufficiency proposed by the authors for guiding selection of items to fill a bin. The algorithm is tested on a set of standard benchmark problem instances and compared with existing heuristics producing the best-known results. The results presented attest to the efficacy of the proposed scheme.     

CARVE-a constructive algorithm for real-valued examples

A constructive neural-network algorithm is presented. For any consistent classification task on real-valued training vectors, the algorithm constructs a feedforward network with a single hidden layer of threshold units which implements the task. The algorithm, which we call CARVE, extends the "sequential learning" algorithm of Marchand et al. (1990) from Boolean inputs to the real-valued input case, and uses convex hull methods for the determination of the network weights. The algorithm is an efficient training scheme for producing near-minimal network solutions for arbitrary classification tasks. The algorithm is applied to a number of benchmark problems including German and Sejnowski's sonar data, the Monks problems and Fisher's iris data. A significant application of the constructive algorithm is in providing an initial network topology and initial weights for other neural-network training schemes, and this is demonstrated by application to backpropagation.     

Node splitting: A constructive algorithm for feed-forward neural networks

A constructive algorithm is proposed for feed-forward neural networks which uses node-splitting in the hidden layers to build large networks from smaller ones. The small network forms an approximate model of a set of training data, and the split creates a larger, more powerful network which is initialised with the approximate solution already found. The insufficiency of the smaller network in modelling the system which generated the data leads to oscillation in those hidden nodes whose weight vectors cover regions in the input space where more detail is required in the model. These nodes are identified and split in two using principal component analysis, allowing the new nodes to cover the two main modes of the oscillating vector. Nodes are selected for splitting using principal component analysis on the oscillating weight vectors, or by examining the Hessian matrix of second derivatives of the network error with respect to the weights.     

A Relax-and-Cut algorithm for the set partitioning problem

Relax-and-Cut algorithms offer an alternative to strengthen Lagrangian relaxation bounds. The main idea behind these algorithms is to dynamically select and dualize inequalities (cuts) within a Lagrangian relaxation framework. This paper proposes a Relax-and-Cut algorithm for the Set Partitioning Problem. Computational tests are reported for benchmark instances from the literature. For Set Partitioning instances with integrality gaps, a variant of the classical Lagrangian relaxation is often used in the literature. It introduces a knapsack constraint to the standard formulation of the problem. Our results indicate that the proposed Relax-and-Cut algorithm outperforms the latter approach in terms of lower bound quality. Furthermore, it turns out to be very competitive in terms of CPU time. Decisive in achieving that performance was the implementation of dominance rules to manage inequalities in the cut pool. The Relax-and-Cut framework proposed here could also be used as a preprocessing tool for Linear Integer Programming solvers. Computational experiments demonstrated that the combined use of our framework and XPRESS improved the performance of that Linear Integer Programming solver for the test sets used in this study.     

A method for the design of phase-lead demodulating compensators for use in carrier control systems

A fairly new type of compensator for carrier control systems consists of a passive electric network that contains one or more periodically-conducting branches. This type of compensator (referred to as a demodulating compensating network) is superior to other types, used previously, in terms of size, weight, cost, and sensitivity to variations in carrier frequency. Although a detailed analysis of the operation of a demodulating compensating network is usually very tedious, it is possible to describe the effect of such a network in a feedback control system very simply by the use of an equivalent time-invariant passive electric network. A procedure for designing a phase-lead demodulating compensating network to meet specifications on system performance is presented in this paper. In essence, this procedure consists of the following steps. First, the uncompensated frequency response of the system is examined. Then an acceptable and realizable phase and/or gain characteristic is selected. Finally, by the use of design curves, the parameters of the demodulating compensator required to provide the desired frequency response are determined. Numerical examples are included to illustrate the application of the design procedure, and experimental results are reported to reveal the value of the procedure.     

Program development in the constructive set theory TK

We present a constructive theory of types and kinds designed with program development as the major desideratum. We show how this theory may be employed to derive programs from proofs of specifications (that is, demonstrations that specifications are satisfiable) and how the infrastructure of the theory supports the transformational development of programs in a natural way.     

A pole-assignment algorithm for linear state feedback

A new algorithm for the pole-assignment problem of a controllable time-invariant linear multivariable system with linear state feedback is presented. The resulting feedback matrix is a least-squares solution and is robust in a loose sense. The method is based on the controllability canonical (staircase) form and amounts to a new proof for the existence of a solution of the pole-assignment problem. Illustrative examples are given.