Search results for "metaheuristic"
showing 10 items of 153 documents
Guided local search for the optimal communication spanning tree problem
2011
This paper considers the optimal communication spanning tree (OCST) problem. Previous work analyzed features of high-quality solutions. Consequently, integrating this knowledge into a metaheuristic increases its performance for the OCST problem. In this paper, we present a guided local search (GLS) approach which dynamically changes the objective function to guide the search process into promising areas. In contrast to traditional approaches which reward promising solution features by favoring edges with low weights pointing towards the tree's center, GLS penalizes low-quality edges with large weights that do not point towards the tree's center.
A problem-adjusted genetic algorithm for flexibility design
2013
Many present markets for goods and services have highly volatile demand due to short life cycles and strong competition in saturated environments. Determination of capacity levels is difficult because capacities often need to be set long before demand realizes. In order to avoid capacity-demand mismatches, operations managers employ mix-flexible resources which allow them to shift excess demands to unused capacities. The Flexibility Design Problem (FDP) models the decision on the optimal configuration of a flexible (manufacturing) network. FDP is a difficult stochastic optimization problem, for which traditional exact approaches are not able to solve but the smallest instances in reasonable…
An Empirical Investigation of Heavy Tails in Emerging Markets and Robust Estimation of the Pareto Tail Index
2021
In this work we analyze and compare the performances of VaR-based estimatorswith respect to three different classes of distributions, i.e., Gaussian, Stable and Pareto, and to different emerging markets, i.e., Egypt, Qatar and Mexico. This is motivated by the evidence that there are points of distinction between emerging and developed markets mainly relating to the speed and reliability of information available to investors.We propose a computational Threshold Accepting-VaR based algorithm (TAVaR) for optimally estimating the Pareto tail index. A Monte Carlo bias estimation analysis is also carried out by comparing our proposed methodology with the Hill estimator and a variant of it.
Split-Delivery Capacitated Arc-Routing Problem: Lower Bound and Metaheuristic
2010
International audience; This paper proposes lower and upper bounds for the split-delivery capacitated arc-routing problem (SDCARP), a variant of the capacitated arc-routing problem in which an edge can be serviced by several vehicles. Recent papers on related problems in node routing have shown that this policy can bring significant savings. It is also more realistic in applications such as urban refuse collection, where a vehicle can become full in the middle of a street segment. This work presents the first lower bound for the SDCARP, computed with a cutting plane algorithm and an evolutionary local search reinforced by a multistart procedure and a variable neighborhood descent. Tests on …
An Effective Multirestart Deterministic Annealing Metaheuristic for the Fleet Size and Mix Vehicle-Routing Problem with Time Windows
2008
This paper presents a new deterministic annealing metaheuristic for the fleet size and mix vehicle-routing problem with time windows. The objective is to service, at minimal total cost, a set of customers within their time windows by a heterogeneous capacitated vehicle fleet. First, we motivate and define the problem. We then give a mathematical formulation of the most studied variant in the literature in the form of a mixed-integer linear program. We also suggest an industrially relevant, alternative definition that leads to a linear mixed-integer formulation. The suggested metaheuristic solution method solves both problem variants and comprises three phases. In Phase 1, high-quality init…
The Scatter Search Methodology
2011
Scatter search (SS) is an evolutionary approach for optimization. It has been applied to problems with continuous and discrete variables and with a single or multiple objectives. The success of SS as an optimization technique is well documented in a constantly growing number of journal articles and book chapters. This article first focuses on the basic SS framework, which is responsible for most of the outcomes reported in the literature, and then covers advanced elements that have been introduced in a few selected papers, such as the hybridization with tabu search, a well-known memory-based metaheuristic. We consider the maximum diversity problem to illustrate the search elements, methods …
Fuzzy predictive controller design using ant colony optimization algorithm
2014
In this paper, an approach for designing an adaptive fuzzy model predictive control (AFMPC) based on the Ant Colony Optimization (ACO) is studied. On-line adaptive fuzzy identification is used to identify the system parameters. These parameters are used to calculate the objective function based on predictive approach and structure of RST control. The optimization problem is solved based on an ACO algorithm, used at the optimization process in AFMPC to calculate a sequence of future RST control actions. The obtained simulation results show that proposed approach provides better results compared with Proportional Integral-Ant Colony Optimization (PI-ACO) controller and adaptive fuzzy model pr…
A computational proposal for a robust estimation of the Pareto tail index: An application to emerging markets
2022
Abstract In this work, we backtest and compare, under the VaR risk measure, the fitting performances of three classes of density distributions (Gaussian, Stable and Pareto) with respect to three different types of emerging markets: Egypt, Qatar and Mexico. We also propose a new technique for the estimation of the Pareto tail index by means of the Threshold Accepting (TAVaR) and the Hybrid Particle Swarm Optimization algorithm (H-PSOVaR). Furthermore, we test the accuracy and robustness of our estimates demonstrating the effectiveness of the proposed approach.
Strategies for accelerating ant colony optimization algorithms on graphical processing units
2007
Ant colony optimization (ACO) is being used to solve many combinatorial problems. However, existing implementations fail to solve large instances of problems effectively. In this paper we propose two ACO implementations that use graphical processing units to support the needed computation. We also provide experimental results by solving several instances of the well-known orienteering problem to show their features, emphasizing the good properties that make these implementations extremely competitive versus parallel approaches.
Finding optimal finite biological sequences over finite alphabets: the OptiFin toolbox
2017
International audience; In this paper, we present a toolbox for a specific optimization problem that frequently arises in bioinformatics or genomics. In this specific optimisation problem, the state space is a set of words of specified length over a finite alphabet. To each word is associated a score. The overall objective is to find the words which have the lowest possible score. This type of general optimization problem is encountered in e.g 3D conformation optimisation for protein structure prediction, or largest core genes subset discovery based on best supported phylogenetic tree for a set of species. In order to solve this problem, we propose a toolbox that can be easily launched usin…