Search results for "Metaheuristic"
showing 10 items of 153 documents
An Encoding in Metaheuristics for the Minimum Communication Spanning Tree Problem
2009
Problem-specific encodings can improve the performance of metaheuristics, such as genetic algorithms or simulated annealing. This paper studies the link-biased (LB) encoding, which is a tree representation, and applies metaheuristics using this encoding to the minimum communication spanning tree (MCST) problem. Given the communication requirements of the nodes, the MCST problem seeks a communication spanning tree with minimum total cost. Optimal solutions for MCST problems are similar to minimum spanning trees (MSTs), and the LB encoding exploits this property by encoding trees similar to MSTs with higher probability. The paper investigates how to systematically design problem-specific enc…
Scatter Search and Path-Relinking: Fundamentals, Advances, and Applications
2010
Scatter search is an evolutionary metaheuristic that explores solution spaces by evolving a set of reference points, operating on a small set of solutions while making only limited use of randomization. We give a comprehensive description of the elements and methods that make up its template, including the most recent elements incorporated in successful applications in both global and combinatorial optimization. Path-relinking is an intensification strategy to explore trajectories connecting elite solutions obtained by heuristic methods such as scatter search, tabu search, and GRASP. We describe its mechanics, implementation issues, randomization, the use of pools of high-quality solutions …
Distance Measures for Portfolio Selection
2017
The classical Markowitz approach to the portfolio selection problem (PSP) consists of selecting the portfolio that minimises the return variance for a given level of expected return. By solving the problem for different values of this expected return we obtain the Pareto efficient frontier, which is composed of non-dominated portfolios. The final user has to discriminate amongst these points by resorting to an external criterion in order to decide which portfolio to invest in. We propose to define an external portfolio that corresponds to a desired criterion, and to assess its distance from the Markowitz frontier in market allowing for short-sellings or not. We show that this distance is ab…
A multi-local optimization algorithm
1998
The development of efficient algorithms that provide all the local minima of a function is crucial to solve certain subproblems in many optimization methods. A “multi-local” optimization procedure using inexact line searches is presented, and numerical experiments are also reported. An application of the method to a semi-infinite programming procedure is included.
Pseudo-Cut Strategies for Global Optimization
2011
Motivated by the successful use of a pseudo-cut strategy within the setting of constrained nonlinear and nonconvex optimization in Lasdon et al. (2010), we propose a framework for general pseudo-cut strategies in global optimization that provides a broader and more comprehensive range of methods. The fundamental idea is to introduce linear cutting planes that provide temporary, possibly invalid, restrictions on the space of feasible solutions, as proposed in the setting of the tabu search metaheuristic in Glover (1989), in order to guide a solution process toward a global optimum, where the cutting planes can be discarded and replaced by others as the process continues. These strategies can…
Influence of rounding errors on the quality of heuristic optimization algorithms
2011
Abstract Search space smoothing and related heuristic optimization algorithms provide an alternative approach to simulated annealing and its variants: while simulated annealing traverses barriers in the energy landscape at finite temperatures, search space smoothing intends to remove these barriers, so that a greedy algorithm is sufficient to find the global minimum. Several formulas for smoothing the energy landscape have already been applied, one of them making use of the finite numerical precision on a computer. In this paper, we thoroughly investigate the effect of finite numerical accuracy on the quality of results achieved with heuristic optimization algorithms. We present computation…
A Differential Evolution Framework with Ensemble of Parameters and Strategies and Pool of Local Search Algorithms
2014
The file attached to this record is the author's final peer reviewed version. The publisher's final version can be found by following the DOI link. The ensemble structure is a computational intelligence supervised strategy consisting of a pool of multiple operators that compete among each other for being selected, and an adaptation mechanism that tends to reward the most successful operators. In this paper we extend the idea of the ensemble to multiple local search logics. In a memetic fashion, the search structure of an ensemble framework cooperatively/competitively optimizes the problem jointly with a pool of diverse local search algorithms. In this way, the algorithm progressively adapts…
Heuristics for the Constrained Incremental Graph Drawing Problem
2019
Abstract Visualization of information is a relevant topic in Computer Science, where graphs have become a standard representation model, and graph drawing is now a well-established area. Within this context, edge crossing minimization is a widely studied problem given its importance in obtaining readable representations of graphs. In this paper, we focus on the so-called incremental graph drawing problem, in which we try to preserve the user’s mental map when obtaining successive drawings of the same graph. In particular, we minimize the number of edge crossings while satisfying some constraints required to preserve the position of vertices with respect to previous drawings. We propose heur…
Multiobjective GRASP with Path Relinking
2015
In this paper we review and propose different adaptations of the GRASP metaheuristic to solve multiobjective combinatorial optimization problems. In particular, we describe several alternatives to specialize the construction and improvement components of GRASP when two or more objectives are considered. GRASP has been successfully coupled with Path Relinking for single-objective optimization. Moreover, we propose different hybridizations of GRASP and Path Relinking for multiobjective optimization. We apply the proposed GRASP with Path Relinking variants to two combinatorial optimization problems, the biobjective orienteering problem and the biobjective path dissimilarity problem. We report …
Influence of the evolutionary optimization parameters on the optimal topology
2016
Topological optimization can be considered as one of the most general types of structural optimization. Between all known topological optimization techniques, the Evolutionary Structural Optimization represents one of the most efficient and easy to implement approaches. Evolutionary topological optimization is based on a heuristic general principle which states that, by gradually removing portions of inefficient material from an assigned domain, the resulting structure will evolve towards an optimal configuration. Usually, the initial continuum domain is divided into finite elements that may or may not be removed according to the chosen efficiency criteria and other parameters like the spee…