Search results for "Heuristic"
showing 10 items of 476 documents
Scatter Search for the Point-Matching Problem in 3D Image Registration
2008
Scatter search is a population-based method that has recently been shown to yield promising outcomes for solving combinatorial and nonlinear optimization problems. Based on formulations originally proposed in the 1960s for combining decision rules and problem constraints, such as the surrogate constraint method, scatter search uses strategies for combining solution vectors that have proved effective in a variety of problem settings. We present a scatter-search implementation designed to find high-quality solutions for the 3D image-registration problem, which has many practical applications. This problem arises in computer vision applications when finding a correspondence or transformation …
Multi-modal search for multiobjective optimization: an application to optimal smart grids management
2012
This paper studies the possibility to use efficient multimodal optimizers for multi-objective optimization. In this paper, the application area considered for such new approach is the optimal dispatch of energy sources in smart microgrids. The problem indeed shows a non uniform Pareto front and requires efficient optimal search methods. The idea is to exploit the potential of agents in population-based heuristics to improve diversity in the Pareto front, where solutions show the same rank and are thus equally weighted. Since Pareto dominance is at the basis of the theory of multi-objective optimization, most algorithms show the non dominance ranking as quality indicator, with some problem i…
Scatter search for an uncapacitated p-hub median problem
2015
Scatter search is a population-based method that has been shown to yield high-quality outcomes for combinatorial optimization problems. It uses strategies for combining solution vectors that have proved effective in a variety of problem settings. In this paper, we present a scatter search implementation for an NP -hard variant of the classic p-hub median problem. Specifically, we tackle the uncapacitated r-allocation p-hub median problem, which consists of minimizing the cost of transporting the traffics between nodes of a network through special facilities that act as transshipment points. This problem has a significant number of applications in practice, such as the design of transportati…
A hybrid evolution strategy for the open vehicle routing problem
2010
This paper presents a hybrid evolution strategy (ES) for solving the open vehicle routing problem (OVRP), which is a well-known combinatorial optimization problem that addresses the service of a set of customers using a homogeneous fleet of non-depot returning capacitated vehicles. The objective is to minimize the fleet size and the distance traveled. The proposed solution method manipulates a population of @m individuals using a (@m+@l)-ES; at each generation, a new intermediate population of @l offspring is produced via mutation, using arcs extracted from parent individuals. The selection and combination of arcs is dictated by a vector of strategy parameters. A multi-parent recombination …
The Tax Justice Network-Africa v Cabinet Secretary for National Treasury & 2 Others: A Big Win for Tax Justice Activism?
2019
This paper develops an optimization model for selecting a large subsample that improves the representativeness of a simple random sample previously obtained from a population larger than the population of interest. The problem formulation involves convex mixed-integer nonlinear programming (convex MINLP) and is therefore NP-hard. However, the solution is found by maximizing the “constant of proportionality” – in other words, maximizing the size of the subsample taken from a stratified random sample with proportional allocation – and restricting it to a p-value high enough to achieve a good fit to the population of interest using Pearson’s chi-square goodness-of-fit test. The beauty of the m…
A Population-Based Approach to the Resource-Constrained Project Scheduling Problem
2004
We present a population-based approach to the RCPSP. The procedure has two phases. The first phase handles the initial construction of a population of schedules and these are then evolved until high quality solutions are obtained. The evolution of the population is driven by the alternative application of an efficient improving procedure for locally improving the use of resources, and a mechanism for combining schedules that blends scatter search and path relinking characteristics. The objective of the second phase is to explore in depth those vicinities near the high quality schedules. Computational experiments on the standard j120 set, generated using ProGen, show that our algorithm produ…
Connections with Other Population-Based Approaches
2003
Throughout this book, we have established that scatter search (SS) belongs to the family of population-based metaheuristics. This family also includes the well-known evolutionary algorithms and the approach known as path relinking.
A Primer on Memetic Algorithms
2012
Memetic Algorithms (MAs) are population-based metaheuristics composed of an evolutionary framework and a set of local search algorithms which are activated within the generation cycle of the external framework, see [376]. The earliest MA implementation has been given in [621] in the context of the Travelling Salesman Problem (TSP) while an early systematic definition has been presented in [615]. The concept of meme is borrowed from philosophy and is intended as the unit of cultural transmission. In other words, complex ideas can be decomposed into memes which propagate andmutate within a population.Culture, in this way, constantly undergoes evolution and tends towards progressive improvemen…
3D inter-subject medical image registration by scatter search
2005
Image registration is a very active research area in computer vision, namely it is used to find a transformation between two images taken under different conditions. Point matching is an image registration approach based on searching for the right pairing of points between the two images. From this matching, the registration transformation we are searching, can be inferred by means of numerical methods. In this paper, we propose a scatter search (SS) algorithm to solve the matching problem. SS is a hybrid metaheuristic with a good trade-off between search space diversification and intensification. On the one hand, diversity is basically introduced from a population-based approach where syst…
A geomorphological approach for enhancing environmental management and conservation of landforms as protected nature objects in the Upper Daugava spi…
2015
<p class="R-AbstractKeywords"><span lang="EN-GB">This paper describes the application of geomorphological approach for environmental management and conservation of landforms. Specifically, we discuss the contribution of geomorphological field survey and adapted matrix methodology (in combination with understanding of geology) to identification, study and evaluation of those abiotic nature elements which represent geological and geomorphological heritage. We describe a case study carried out in that part of the protected landscape area “Augšdaugava” which encompasses the Upper Daugava spillway valley. The study programme reported in this paper was realized to perform inventory of…