Search results for " Computer Science"
showing 10 items of 3983 documents
Lower and upper bounds for the mixed capacitated arc routing problem
2006
This paper presents a linear formulation, valid inequalities, and a lower bounding procedure for the mixed capacitated arc routing problem (MCARP). Moreover, three constructive heuristics and a memetic algorithm are described. Lower and upper bounds have been compared on two sets of randomly generated instances. Computational results show that the average gaps between lower and upper bounds are 0.51% and 0.33%, respectively.
Effective state estimation of stochastic systems
2003
In the present paper, for constructing the minimum risk estimators of state of stochastic systems, a new technique of invariant embedding of sample statistics in a loss function is proposed. This technique represents a simple and computationally attractive statistical method based on the constructive use of the invariance principle in mathematical statistics. Unlike the Bayesian approach, an invariant embedding technique is independent of the choice of priors. It allows one to eliminate unknown parameters from the problem and to find the best invariant estimator, which has smaller risk than any of the well‐known estimators. There exists a class of control systems where observations are not …
model reduction for continuous-time Markovian jump systems with incomplete statistics of mode information
2013
This paper investigates the problem of model reduction for a class of continuous-time Markovian jump linear systems with incomplete statistics of mode information, which simultaneously considers the exactly known, partially unknown and uncertain transition rates. By fully utilising the properties of transition rate matrices, together with the convexification of uncertain domains, a new sufficient condition for performance analysis is first derived, and then two approaches, namely, the convex linearisation approach and the iterative approach, are developed to solve the model reduction problem. It is shown that the desired reduced-order models can be obtained by solving a set of strict linear…
Developing Domain-Knowledge Evolutionary Algorithms for Network-on-Chip Application Mapping
2013
This paper addresses the Network-on-Chip (NoC) application mapping problem. This is an NP-hard problem that deals with the optimal topological placement of Intellectual Property cores onto the NoC tiles. Network-on-Chip application mapping Evolutionary Algorithms are developed, evaluated and optimized for minimizing the NoC communication energy. Two crossover and one mutation operators are proposed. It is analyzed how each optimization algorithm performs with every genetic operator, in terms of solution quality and convergence speed. Our proposed operators are compared with state-of-the-art genetic operators for permutation problems. Finally, the problem is approached in a multi-objective w…
A Multiple Surrogate Assisted Decomposition-Based Evolutionary Algorithm for Expensive Multi/Many-Objective Optimization
2019
Many-objective optimization problems (MaOPs) contain four or more conflicting objectives to be optimized. A number of efficient decomposition-based evolutionary algorithms have been developed in the recent years to solve them. However, computationally expensive MaOPs have been scarcely investigated. Typically, surrogate-assisted methods have been used in the literature to tackle computationally expensive problems, but such studies have largely focused on problems with 1–3 objectives. In this paper, we present an approach called hybrid surrogate-assisted many-objective evolutionary algorithm to solve computationally expensive MaOPs. The key features of the approach include: 1) the use of mul…
Fixed domain approaches in shape optimization problems
2012
This work is a review of results in the approximation of optimal design problems, defined in variable/unknown domains, based on associated optimization problems defined in a fixed ?hold-all? domain, including the family of all admissible open sets. The literature in this respect is very rich and we concentrate on three main approaches: penalization?regularization, finite element discretization on a fixed grid, controllability and control properties of elliptic systems. Comparison with other fixed domain approaches or, in general, with other methods in shape optimization is performed as well and several numerical examples are included.
On multi-objective optimal reconfiguration of MV networks in presence of different grounding
2015
The present work faces the traditional multi-objective optimal reconfiguration problem of a distribution grid including the safety issue in the objective functions. Actually, in many medium voltage networks still transformers with ungrounded neutral and with resonant grounded neutral coexist in the same area. This may be sometimes cause of problems during a single-line-to-ground fault if the ground electrodes of one or more cabins, initially designed for satisfying the safety conditions in a resonant grounded neutral network, after the reconfiguration are in a grounded neutral one or vice versa. In the paper a safety objective function is defined and the Non dominated Sorting Genetic Algori…
GRASP and path relinking for the max–min diversity problem
2010
The max-min diversity problem (MMDP) consists in selecting a subset of elements from a given set in such a way that the diversity among the selected elements is maximized. The problem is NP-hard and can be formulated as an integer linear program. Since the 1980s, several solution methods for this problem have been developed and applied to a variety of fields, particularly in the social and biological sciences. We propose a heuristic method-based on the GRASP and path relinking methodologies-for finding approximate solutions to this optimization problem. We explore different ways to hybridize GRASP and path relinking, including the recently proposed variant known as GRASP with evolutionary p…
A comparison of different solution approaches to the vehicle scheduling problem in a practical case
2000
Abstract The Vehicle Scheduling Problem (VSP) consists in assigning a set of scheduled trips to a set of vehicles, satisfying a set of constraints and optimizing an objective function. A wide literature exists for the VSP, but usually not all the practical requirements of the real cases are taken into account. In the present paper a practical case is studied, and for it a traditional method is tailored and two innovative heuristics are developed. As the problem presents a multicriteria nature, each of the three algorithms adopts a different approach to multicriteria optimization. Scalarization of the different criteria is performed by the traditional algorithm. A lexicographic approach is f…
Hybridizing the cross-entropy method: An application to the max-cut problem
2009
Cross-entropy has been recently proposed as a heuristic method for solving combinatorial optimization problems. We briefly review this methodology and then suggest a hybrid version with the goal of improving its performance. In the context of the well-known max-cut problem, we compare an implementation of the original cross-entropy method with our proposed version. The suggested changes are not particular to the max-cut problem and could be considered for future applications to other combinatorial optimization problems.