Search results for "local search"
showing 10 items of 91 documents
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 …
A multiagent system approach for image segmentation using genetic algorithms and extremal optimization heuristics
2006
We propose a new distributed image segmentation algorithm structured as a multiagent system composed of a set of segmentation agents and a coordinator agent. Starting from its own initial image, each segmentation agent performs the iterated conditional modes method, known as ICM, in applications based on Markov random fields, to obtain a sub-optimal segmented image. The coordinator agent diversifies the initial images using the genetic crossover and mutation operators along with the extremal optimization local search. This combination increases the efficiency of our algorithm and ensures its convergence to an optimal segmentation as it is shown through some experimental results.
Rule Extraction From Binary Neural Networks With Convolutional Rules for Model Validation.
2020
Classification approaches that allow to extract logical rules such as decision trees are often considered to be more interpretable than neural networks. Also, logical rules are comparatively easy to verify with any possible input. This is an important part in systems that aim to ensure correct operation of a given model. However, for high-dimensional input data such as images, the individual symbols, i.e. pixels, are not easily interpretable. Therefore, rule-based approaches are not typically used for this kind of high-dimensional data. We introduce the concept of first-order convolutional rules, which are logical rules that can be extracted using a convolutional neural network (CNN), and w…
Predicting Heuristic Search Performance with PageRank Centrality in Local Optima Networks
2015
Previous studies have used statistical analysis of fitness landscapes such as ruggedness and deceptiveness in order to predict the expected quality of heuristic search methods. Novel approaches for predicting the performance of heuristic search are based on the analysis of local optima networks (LONs). A LON is a compressed stochastic model of a fitness landscape's basin transitions. Recent literature has suggested using various LON network measurements as predictors for local search performance.In this study, we suggest PageRank centrality as a new measure for predicting the performance of heuristic search methods using local search. PageRank centrality is a variant of Eigenvector centrali…
On the Use of GPU for Accelerating Communication-Aware Mapping Techniques
2015
Different communication-aware mapping techniques were proposed in recent years for improving the performance of distributed systems based on both, off-chip and on-chip networks. Some of these proposals were based on heuristic search for finding pseudo-optimal assignments of tasks and processing elements. However, the technology integration improvements have allowed a significant increase in the number of network nodes, requiring the acceleration of the heuristic search. In this paper, we propose a comparative study of the local search method used in a communication-aware mapping technique, when implemented on different parallel architectures. We compare the performance provided by a version…
Variable Neighborhood Search for the Vertex Separation Problem
2012
The vertex separation problem belongs to a family of optimization problems in which the objective is to nd the best separator of vertices or edges in a generic graph. This optimization problem is strongly related to other well-known graph problems; such as the Path-Width, the Node Search Number or the Interval Thickness, among others. All of these optimization problems are NP-hard and have practical applications in VLSI, computer language compiler design or graph drawing. Up to know, they have been generally tackled with exact approaches, presenting polynomial-time algorithms to obtain the optimal solution for speci c types of graphs. However, in spite of their practical applications, these…
Using Learning Automata to Enhance Local-Search Based SAT Solvers with Learning Capability
2010
In this work, we have introduced a new approach based on combining Learning Automata with Random Walk and GSAT w/Random Walk. In order to get a comprehensive overview of the new algorithms' performance, we used a set of benchmark problems containing different problems from various domains. In these benchmark problems, both RW and GSATRW suffers from stagnation behaviour which directly affects their performance. This phenomenon is, however, only observed for LA-GSATRW on the largest problem instances. Finally, the
GRASP with path relinking for the orienteering problem
2014
In this paper, we address an optimization problem resulting from the combination of the well-known travelling salesman and knapsack problems. In particular, we target the orienteering problem, originated in the context of sport, which consists of maximizing the total score associated with the vertices visited in a path within the available time. The problem, also known as the selective travelling salesman 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 routing and tourism. We propose a heuristic method—based on the Greedy Randomized Adapt…
Advanced Greedy Randomized Adaptive Search Procedure for the Obnoxious p-Median problem
2016
Abstract The Obnoxious p-Median problem consists in selecting a subset of p facilities from a given set of possible locations, in such a way that the sum of the distances between each customer and its nearest facility is maximized. The problem is NP -hard and can be formulated as an integer linear program. It was introduced in the 1990s, and a branch and cut method coupled with a tabu search has been recently proposed. In this paper, we propose a heuristic method – based on the Greedy Randomized Adaptive Search Procedure, GRASP, methodology – for finding approximate solutions to this optimization problem. In particular, we consider an advanced GRASP design in which a filtering mechanism avo…
Multi-objective memetic optimization for the bi-objective obnoxious p -median problem
2018
Abstract Location problems have been studied extensively in the optimization literature, the p-median being probably one of the most tackled models. The obnoxious p-median is an interesting variant that appears in the context of hazardous location. The aim of this paper is to formally introduce a bi-objective optimization model for this problem, in which a solution consists of a set of p locations, and two conflicting objectives arise. On the one hand, the sum of the minimum distance between each client and their nearest open facility and, on the other hand, the dispersion among facilities. Both objective values should be kept as large as possible for a convenient location of dangerous faci…