Relevant bibliographies by topics / Local search heuristics

Academic literature on the topic 'Local search heuristics'

Author: Grafiati
Published: 6 September 2023
Last updated: 25 May 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Contents

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Local search heuristics.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Local search heuristics"

1

Veerapaneni, Rishi, Muhammad Suhail Saleem, and Maxim Likhachev. "Learning Local Heuristics for Search-Based Navigation Planning." Proceedings of the International Conference on Automated Planning and Scheduling 33, no. 1 (July 1, 2023): 634–38. http://dx.doi.org/10.1609/icaps.v33i1.27245.

Full text
Abstract:
Graph search planning algorithms for navigation typically rely heavily on heuristics to efficiently plan paths. As a result, while such approaches require no training phase and can directly plan long horizon paths, they often require careful hand designing of informative heuristic functions. Recent works have started bypassing hand designed heuristics by using machine learning to learn heuristic functions that guide the search algorithm. While these methods can learn complex heuristic functions from raw input, they i) require significant training and ii) do not generalize well to new maps and longer horizon paths. Our contribution is showing that instead of learning a global heuristic estimate, we can define and learn local heuristics which results in a significantly smaller learning problem and improves generalization. We show that using such local heuristics can reduce node expansions by 2-20x while maintaining bounded suboptimality, are easy to train, and generalize to new maps & long horizon plans.
APA, Harvard, Vancouver, ISO, and other styles
2

Wilt, Christopher, and Wheeler Ruml. "Speedy Versus Greedy Search." Proceedings of the International Symposium on Combinatorial Search 5, no. 1 (September 1, 2021): 184–92. http://dx.doi.org/10.1609/socs.v5i1.18320.

Full text
Abstract:
In work on satisficing search, there has been substantial attention devoted to how to solve problems associated with local minima or plateaus in the heuristic function. One technique that has been shown to be quite promising is using an alternative heuristic function that does not estimate cost-to-go, but rather estimates distance-to-go. Empirical results generally favor using the distance-to-go heuristic over the cost-to-go heuristic, but there is currently little beyond intuition to explain the difference. We begin by empirically showing that the success of the distance-to-go heuristic appears related to its having smaller local minima. We then discuss a reasonable theoretical model of heuristics and show that, under this model, the expected size of local minima is higher for a cost- to-go heuristic than a distance-to-go heuristic, offering a possible explanation as to why distance-to-go heuristics tend to outperform cost-to-go heuristics.
APA, Harvard, Vancouver, ISO, and other styles
3

HASEGAWA, Manabu. "Potentially Local Search in Local Search Heuristics." Proceedings of The Computational Mechanics Conference 2004.17 (2004): 403–4. http://dx.doi.org/10.1299/jsmecmd.2004.17.403.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Soria-Alcaraz, Jorge A., Gabriela Ochoa, Andres Espinal, Marco A. Sotelo-Figueroa, Manuel Ornelas-Rodriguez, and Horacio Rostro-Gonzalez. "A Methodology for Classifying Search Operators as Intensification or Diversification Heuristics." Complexity 2020 (February 13, 2020): 1–10. http://dx.doi.org/10.1155/2020/2871835.

Full text
Abstract:
Selection hyper-heuristics are generic search tools that dynamically choose, from a given pool, the most promising operator (low-level heuristic) to apply at each iteration of the search process. The performance of these methods depends on the quality of the heuristic pool. Two types of heuristics can be part of the pool: diversification heuristics, which help to escape from local optima, and intensification heuristics, which effectively exploit promising regions in the vicinity of good solutions. An effective search strategy needs a balance between these two strategies. However, it is not straightforward to categorize an operator as intensification or diversification heuristic on complex domains. Therefore, we propose an automated methodology to do this classification. This brings methodological rigor to the configuration of an iterated local search hyper-heuristic featuring diversification and intensification stages. The methodology considers the empirical ranking of the heuristics based on an estimation of their capacity to either diversify or intensify the search. We incorporate the proposed approach into a state-of-the-art hyper-heuristic solving two domains: course timetabling and vehicle routing. Our results indicate improved performance, including new best-known solutions for the course timetabling problem.
APA, Harvard, Vancouver, ISO, and other styles
5

Adubi, Stephen A., Olufunke O. Oladipupo, and Oludayo O. Olugbara. "Evolutionary Algorithm-Based Iterated Local Search Hyper-Heuristic for Combinatorial Optimization Problems." Algorithms 15, no. 11 (October 31, 2022): 405. http://dx.doi.org/10.3390/a15110405.

Full text
Abstract:
Hyper-heuristics are widely used for solving numerous complex computational search problems because of their intrinsic capability to generalize across problem domains. The fair-share iterated local search is one of the most successful hyper-heuristics for cross-domain search with outstanding performances on six problem domains. However, it has recorded low performances on three supplementary problems, namely knapsack, quadratic assignment, and maximum-cut problems, which undermines its credibility across problem domains. The purpose of this study was to design an evolutionary algorithm-based iterated local search (EA-ILS) hyper-heuristic that applies a novel mutation operator to control the selection of perturbative low-level heuristics in searching for optimal sequences for performance improvement. The algorithm was compared to existing ones in the hyper-heuristics flexible (HyFlex) framework to demonstrate its performance across the problem domains of knapsack, quadratic assignment, and maximum cut. The comparative results have shown that the EA-ILS hyper-heuristic can obtain the best median objective function values on 22 out of 30 instances in the HyFlex framework. Moreover, it has achieved superiority in its generalization capability when compared to the reported top-performing hyper-heuristic algorithms.
APA, Harvard, Vancouver, ISO, and other styles
6

Davidov, D., and S. Markovitch. "Multiple-Goal Heuristic Search." Journal of Artificial Intelligence Research 26 (August 25, 2006): 417–51. http://dx.doi.org/10.1613/jair.1940.

Full text
Abstract:
This paper presents a new framework for anytime heuristic search where the task is to achieve as many goals as possible within the allocated resources. We show the inadequacy of traditional distance-estimation heuristics for tasks of this type and present alternative heuristics that are more appropriate for multiple-goal search. In particular, we introduce the marginal-utility heuristic, which estimates the cost and the benefit of exploring a subtree below a search node. We developed two methods for online learning of the marginal-utility heuristic. One is based on local similarity of the partial marginal utility of sibling nodes, and the other generalizes marginal-utility over the state feature space. We apply our adaptive and non-adaptive multiple-goal search algorithms to several problems, including focused crawling, and show their superiority over existing methods.
APA, Harvard, Vancouver, ISO, and other styles
7

Abdul-Razaq, Tariq, Hanan Chachan, and Faez Ali. "Modified Heuristics for Scheduling in Flow Shop to Minimize Makespan." Journal of Al-Rafidain University College For Sciences ( Print ISSN: 1681-6870 ,Online ISSN: 2790-2293 ), no. 2 (October 19, 2021): 1–20. http://dx.doi.org/10.55562/jrucs.v30i2.361.

Full text
Abstract:
The NP-completeness of flow shops scheduling problems has been discussed for many years. Hence many heuristics have been proposed to obtain solutions of good quality with a small computational effort. The CDS (Campbell et al) and NEH (Nawaz, Enscore and Ham) heuristics are efficient among meta-heuristics such as Particle Swarm Optimization (PSO) and Genetic Algorithm (GA).This paper discusses some methods and suggests new developing to the methods of the scheduling in flow shop to minimize makespan problems. Our main object in this paper, from one side, is to improve efficient heuristics which will be better than the existing heuristics given in the literature and yield solutions within a short time like Simple Heuristic Methods (SHM) and the First Heuristic Decreasing Arrange (DR). From other side, we apply two local search methods like GA and PSO algorithms on flow shop problems.Experimental analysis has been given of the performance of the proposed heuristics and local search methods with the relative efficient existing heuristics.
APA, Harvard, Vancouver, ISO, and other styles
8

Sobrino, D. R. Delgado, Oliver Moravčik, D. Caganová, and P. Kostal. "Hybrid Iterative Local Search Heuristic with a Multiple Criteria Approach for the Vehicle Routing Problem." Advanced Materials Research 383-390 (November 2011): 4560–67. http://dx.doi.org/10.4028/www.scientific.net/amr.383-390.4560.

Full text
Abstract:
This paper presents a Hybrid Iterative Local Search Heuristic and its framework, whose aim lies on helping to escape from local optima when a construction heuristic, for the VRP, has been trapped. The approach was mainly inspired by basic and modified versions of related successfully applied heuristics such as Variable Neighborhood Search (VNS) and Granular Local Search (GLS). Differently to a great deal of local search heuristics revised, which mainly consider a single decision criterion, multiple optimization criteria are considered all along the local search and a Multiple Criteria Threshold has been proposed allowing defining which arcs must be included in a candidate list to explore, this considerably reduces the search area and has a major incidence in the satisfaction of the clients. The proposal is enriched with a good literature review, taking into account some of the gaps and achievements of the states of the art and practice.
APA, Harvard, Vancouver, ISO, and other styles
9

Nakhost, Hootan, Jörg Hoffmann, and Martin Müller. "Improving Local Search for Resource-Constrained Planning." Proceedings of the International Symposium on Combinatorial Search 1, no. 1 (August 25, 2010): 81–82. http://dx.doi.org/10.1609/socs.v1i1.18166.

Full text
Abstract:
A ubiquitous feature of planning problems — problems involving the automatic generation of action sequences for attaining a given goal — is the need to economize limited resources such as fuel or money. While heuristic search, mostly based on standard algorithms such as A*, is currently the superior method for most varieties of planning, its ability to solve critically resource-constrained problems is limited: current planning heuristics are bad at dealing with this kind of structure. To address this, one can try to devise better heuristics. An alternative approach is to change the nature of the search instead. Local search has received some attention in planning, but not with a specific focus on how to deal with limited resources. We herein begin to fill this gap. We highlight the limitations of previous methods, and we devise a new improvement (smart restarts) to the local search method of a previously proposed planner (Arvand). Systematic experiments show how performance depends on problem structure and search parameters. In particular, we show that our new method can outperform previous planners by a large margin.
APA, Harvard, Vancouver, ISO, and other styles
10

Lissovoi, Andrei, Pietro S. Oliveto, and John Alasdair Warwicker. "Simple Hyper-Heuristics Control the Neighbourhood Size of Randomised Local Search Optimally for LeadingOnes." Evolutionary Computation 28, no. 3 (September 2020): 437–61. http://dx.doi.org/10.1162/evco_a_00258.

Full text
Abstract:
Selection hyper-heuristics (HHs) are randomised search methodologies which choose and execute heuristics during the optimisation process from a set of low-level heuristics. A machine learning mechanism is generally used to decide which low-level heuristic should be applied in each decision step. In this article, we analyse whether sophisticated learning mechanisms are always necessary for HHs to perform well. To this end we consider the most simple HHs from the literature and rigorously analyse their performance for the LeadingOnes benchmark function. Our analysis shows that the standard Simple Random, Permutation, Greedy, and Random Gradient HHs show no signs of learning. While the former HHs do not attempt to learn from the past performance of low-level heuristics, the idea behind the Random Gradient HH is to continue to exploit the currently selected heuristic as long as it is successful. Hence, it is embedded with a reinforcement learning mechanism with the shortest possible memory. However, the probability that a promising heuristic is successful in the next step is relatively low when perturbing a reasonable solution to a combinatorial optimisation problem. We generalise the “simple” Random Gradient HH so success can be measured over a fixed period of time [Formula: see text], instead of a single iteration. For LeadingOnes we prove that the Generalised Random Gradient (GRG) HH can learn to adapt the neighbourhood size of Randomised Local Search to optimality during the run. As a result, we prove it has the best possible performance achievable with the low-level heuristics (Randomised Local Search with different neighbourhood sizes), up to lower-order terms. We also prove that the performance of the HH improves as the number of low-level local search heuristics to choose from increases. In particular, with access to [Formula: see text] low-level local search heuristics, it outperforms the best-possible algorithm using any subset of the [Formula: see text] heuristics. Finally, we show that the advantages of GRG over Randomised Local Search and Evolutionary Algorithms using standard bit mutation increase if the anytime performance is considered (i.e., the performance gap is larger if approximate solutions are sought rather than exact ones). Experimental analyses confirm these results for different problem sizes (up to [Formula: see text]) and shed some light on the best choices for the parameter [Formula: see text] in various situations.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Local search heuristics"

1

Shatabda, Swakkhar. "Local Search Heuristics for Protein Structure Prediction." Thesis, Griffith University, 2014. http://hdl.handle.net/10072/365446.

Full text
Abstract:
This thesis presents our research on protein structure prediction on discrete lattices. Given a protein’s amino acid sequence, the protein structure prediction problem is to find its three dimensional native structure that has the minimum free energy. Knowledge about the native protein structures and their respective folding process is a key to understand protein functionalities and consequently the basics of life. Protein structure prediction problem is one of the most challenging problems in molecular biology. In-vitro laboratory methods applied to this problem are very time-consuming, cost- expensive and failure-prone. Also, the search based optimization methods used are com- putationally very expensive. To tackle these, researchers have used various simplified models, such as low resolution energy functions and lattice-based structures, and applied incomplete local search methods on them. The simplified models help obtain back-bone structures first and then hierarchically work out the details. Local search methods can normally quickly find solutions although they suffer from re-visitation and stagnancy, and require good heuristics. In the literature, researchers have mostly used primitive ap- proaches based on random decisions at various choice points. Consequently, these methods are applicable to small-sized proteins only. In this thesis, we present a number of techniques to improve the performance of lo- cal search methods applied to protein structure prediction problem using discrete lattices. Firstly, we propose a memory based local search framework that maintains a set of already explored solutions for avoiding re-visitation and stores previously unexplored but promi- nent solutions for restarting to handle stagnation. A novel encoding scheme for protein structures is proposed to handle symmetry present in the search space. We also propose an approximate matching strategy that results in reducing redundancy in the search space.
Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Institute for Integrated and Intelligent Systems
Science, Environment, Engineering and Technology
Full Text
APA, Harvard, Vancouver, ISO, and other styles
2

Carson, Ted. "Empirical and analytic approaches to understanding local search heuristics /." Diss., Connect to a 24 p. preview or request complete full text in PDF format. Access restricted to UC campuses, 2001. http://wwwlib.umi.com/cr/ucsd/fullcit?p9995987.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Magaji, Amina Sambo-Muhammad. "Combining search strategies for distributed constraint satisfaction." Thesis, Robert Gordon University, 2015. http://hdl.handle.net/10059/1374.

Full text
Abstract:
Many real-life problems such as distributed meeting scheduling, mobile frequency allocation and resource allocation can be solved using multi-agent paradigms. Distributed constraint satisfaction problems (DisCSPs) is a framework for describing such problems in terms of related subproblems, called a complex local problem (CLP), which are dispersed over a number of locations, each with its own constraints on the values their variables can take. An agent knows the variables in its CLP plus the variables (and their current value) which are directly related to one of its own variables and the constraints relating them. It knows little about the rest of the problem. Thus, each CLP is solved by an agent which cooperates with other agents to solve the overall problem. Algorithms for solving DisCSPs can be classified as either systematic or local search with the former being complete and the latter incomplete. The algorithms generally assume that each agent has only one variable as they can solve DisCSP with CLPs using “virtual” agents. However, in large DisCSPs where it is appropriate to trade completeness off against timeliness, systematic search algorithms can be expensive when compared to local search algorithms which generally converge quicker to a solution (if a solution is found) when compared to systematic algorithms. A major drawback of local search algorithms is getting stuck at local optima. Significant researches have focused on heuristics which can be used in an attempt to either escape or avoid local optima. This thesis makes significant contributions to local search algorithms for DisCSPs. Firstly, we present a novel combination of heuristics in DynAPP (Dynamic Agent Prioritisation with Penalties), which is a distributed synchronous local search algorithm for solving DisCSPs having one variable per agent. DynAPP combines penalties on values and dynamic agent prioritisation heuristics to escape local optima. Secondly, we develop a divide and conquer approach that handles DisCSP with CLPs by exploiting the structure of the problem. The divide and conquer approach prioritises the finding of variable instantiations which satisfy the constraints between agents which are often more expensive to satisfy when compared to constraints within an agent. The approach also exploits concurrency and combines the following search strategies: (i) both systematic and local searches; (ii) both centralised and distributed searches; and (iii) a modified compilation strategy. We also present an algorithm that implements the divide and conquer approach in Multi-DCA (Divide and Conquer Algorithm for Agents with CLPs). DynAPP and Multi-DCA were evaluated on several benchmark problems and compared to the leading algorithms for DisCSPs and DisCSPs with CLPs respectively. The results show that at the region of difficult problems, combining search heuristics and exploiting problem structure in distributed constraint satisfaction achieve significant benefits (i.e. generally used less computational time and communication costs) over existing competing methods.
APA, Harvard, Vancouver, ISO, and other styles
4

Henderson, Darrall. "Assessing the Finite-Time Performance of Local Search Algorithms." Diss., Virginia Tech, 2001. http://hdl.handle.net/10919/26926.

Full text
Abstract:
Identifying a globally optimal solution for an intractable discrete optimization problem is often cost prohibitive. Therefore, solutions that are within a predetermined threshold are often acceptable in practice. This dissertation introduces the concept of B-acceptable solutions where B is a predetermined threshold for the objective function value. It is difficult to assess a priori the effectiveness of local search algorithms, which makes the process of choosing parameters to improve their performance difficult. This dissertation introduces the B-acceptable solution probability in terms of B-acceptable solutions as a finite-time performance measure for local search algorithms. The B-acceptable solution probability reflects how effectively an algorithm has performed to date and how effectively an algorithm can be expected to perform in the future. The B-acceptable solution probability is also used to obtain necessary asymptotic convergence (with probability one) conditions. Upper and lower bounds for the B-acceptable solution probability are presented. These expressions assume particularly simple forms when applied to specific local search strategies such as Monte Carlo search and threshold accepting. Moreover, these expressions provide guidelines on how to manage the execution of local search algorithm runs. Computational experiments are reported to estimate the probability of reaching a B-acceptable solution for a fixed number of iterations. Logistic regression is applied as a tool to estimate the probability of reaching a B-acceptable solution for values of B close to the objective function value of a globally optimal solution as well as to estimate this objective function value. Computational experiments are reported with logistic regression for pure local search, simulated annealing and threshold accepting applied to instances of the TSP with known optimal solutions.
Ph. D.
APA, Harvard, Vancouver, ISO, and other styles
5

Santiago, Rafael de. "Efficient modularity density heuristics in graph clustering and their applications." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2017. http://hdl.handle.net/10183/164066.

Full text
Abstract:
Modularity Density Maximization is a graph clustering problem which avoids the resolution limit degeneracy of the Modularity Maximization problem. This thesis aims at solving larger instances than current Modularity Density heuristics do, and show how close the obtained solutions are to the expected clustering. Three main contributions arise from this objective. The first one is about the theoretical contributions about properties of Modularity Density based prioritizers. The second one is the development of eight Modularity Density Maximization heuristics. Our heuristics are compared with optimal results from the literature, and with GAOD, iMeme-Net, HAIN, BMD- heuristics. Our results are also compared with CNM and Louvain which are heuristics for Modularity Maximization that solve instances with thousands of nodes. The tests were carried out by using graphs from the “Stanford Large Network Dataset Collection”. The experiments have shown that our eight heuristics found solutions for graphs with hundreds of thousands of nodes. Our results have also shown that five of our heuristics surpassed the current state-of-the-art Modularity Density Maximization heuristic solvers for large graphs. A third contribution is the proposal of six column generation methods. These methods use exact and heuristic auxiliary solvers and an initial variable generator. Comparisons among our proposed column generations and state-of-the-art algorithms were also carried out. The results showed that: (i) two of our methods surpassed the state-of-the-art algorithms in terms of time, and (ii) our methods proved the optimal value for larger instances than current approaches can tackle. Our results suggest clear improvements to the state-of-the-art results for the Modularity Density Maximization problem.
APA, Harvard, Vancouver, ISO, and other styles
6

Alratrout, Serein Abdelmonam. "A hybrid multi-agent architecture and heuristics generation for solving meeting scheduling problem." Thesis, De Montfort University, 2009. http://hdl.handle.net/2086/2409.

Full text
Abstract:
Agent-based computing has attracted much attention as a promising technique for application domains that are distributed, complex and heterogeneous. Current research on multi-agent systems (MAS) has become mature enough to be applied as a technology for solving problems in an increasingly wide range of complex applications. The main formal architectures used to describe the relationships between agents in MAS are centralised and distributed architectures. In computational complexity theory, researchers have classified the problems into the followings categories: (i) P problems, (ii) NP problems, (iii) NP-complete problems, and (iv) NP-hard problems. A method for computing the solution to NP-hard problems, using the algorithms and computational power available nowadays in reasonable time frame remains undiscovered. And unfortunately, many practical problems belong to this very class. On the other hand, it is essential that these problems are solved, and the only possibility of doing this is to use approximation techniques. Heuristic solution techniques are an alternative. A heuristic is a strategy that is powerful in general, but not absolutely guaranteed to provide the best (i.e. optimal) solutions or even find a solution. This demands adopting some optimisation techniques such as Evolutionary Algorithms (EA). This research has been undertaken to investigate the feasibility of running computationally intensive algorithms on multi-agent architectures while preserving the ability of small agents to run on small devices, including mobile devices. To achieve this, the present work proposes a new Hybrid Multi-Agent Architecture (HMAA) that generates new heuristics for solving NP-hard problems. This architecture is hybrid because it is "semi-distributed/semi-centralised" architecture where variables and constraints are distributed among small agents exactly as in distributed architectures, but when the small agents become stuck, a centralised control becomes active where the variables are transferred to a super agent, that has a central view of the whole system, and possesses much more computational power and intensive algorithms to generate new heuristics for the small agents, which find optimal solution for the specified problem. This research comes up with the followings: (1) Hybrid Multi-Agent Architecture (HMAA) that generates new heuristic for solving many NP-hard problems. (2) Two frameworks of HMAA have been implemented; search and optimisation frameworks. (3) New SMA meeting scheduling heuristic. (4) New SMA repair strategy for the scheduling process. (5) Small Agent (SMA) that is responsible for meeting scheduling has been developed. (6) “Local Search Programming” (LSP), a new concept for evolutionary approaches, has been introduced. (7) Two types of super-agent (LGP_SUA and LSP_SUA) have been implemented in the HMAA, and two SUAs (local and global optima) have been implemented for each type. (8) A prototype for HMAA has been implemented: this prototype employs the proposed meeting scheduling heuristic with the repair strategy on SMAs, and the four extensive algorithms on SUAs. The results reveal that this architecture is applicable to many different application domains because of its simplicity and efficiency. Its performance was better than many existing meeting scheduling architectures. HMAA can be modified and altered to other types of evolutionary approaches.
APA, Harvard, Vancouver, ISO, and other styles
7

Rosin, Rafael Alzuguir. "Heurística com busca local para solução do problema de cobertura de rotas com cardinalidade restrita." Universidade de São Paulo, 2011. http://www.teses.usp.br/teses/disponiveis/3/3148/tde-30032012-122542/.

Full text
Abstract:
A crescente necessidade de buscar operações mais eficientes, com menor custo e mais sustentáveis tem feito com que empresas passassem a procurar oportunidades pelas quais estes objetivos pudessem ser atingidos. Na área de transportes encontrou-se na colaboração uma oportunidade para tal. Este trabalho trata o problema de cobertura rotas com cardinalidade restrita (PCRCR), onde empresas que realizam viagens de carga cheia se unem com o objetivo de reduzir o deslocamento vazio de veículos através da formação de ciclos. É chamado de problema de cardinalidade restrita uma vez que limitamos o número de máximo de viagens no ciclo, o que torna este problema NP-Hard. Existem na literatura duas heurísticas (construtivas) e um modelo por programação linear inteira para a solução deste problema. Este trabalho apresenta uma heurística baseada em um método de busca local que reduziu em média 3,19% os melhores resultados apresentados na literatura. Também são apresentados os tempos de execução de cada um dos algoritmos e a importância de escolher de uma boa solução inicial quando se deseja implantar uma Heurística com Busca Local.
The growing need to seek more efficient, lower cost and more sustainable operations has caused industries to seek opportunities in which these objectives could be achieved. In the area of transportation, collaboration is an opportunity for that. This work deals with the cardinality constrained lane covering problem (CCLCP), where companies who uses full truck loads join efforts in order to reduce empty vehicle travel through closed cycle formation. It is known as cardinality constraint problem as the maximum number of trips in the cycle is limited to an integer number, which makes this problem NP-Hard. There are two heuristics in the literature (constructive) and an integer linear programming model for solving this problem. This work presents a heuristic based on a local search method that reduced an average of 3.19% the better results in the literature. It also presents the execution times of each algorithm and the importance of choosing a good initial solution when you want to create a Local Search Heuristic.
APA, Harvard, Vancouver, ISO, and other styles
8

Pehlivanoglu, Osman. "An Algorithm For The Capacitated Vehicle Routing Problem With Time Windows." Master's thesis, METU, 2005. http://etd.lib.metu.edu.tr/upload/2/12606657/index.pdf.

Full text
Abstract:
In this thesis the capacitated vehicle routing problem with time windows (VRPTW) is studied, where the objective is to serve a set of geographically dispersed customers with known demands and predefined time windows at the minimum cost. It is hard to find an optimal solution for the VRPTW even if the problem size is small. Therefore, many heuristic methods are developed to obtain near optimal solutions. In this study a local search algorithm is proposed for solving the VRPTW, which consist of route construction and route improvement phases. Computational experiments are conducted with Solomon (1987)&rsquo
s and Homberger and Gehring (1999)&rsquo
s problem sets in order to test the performance of the proposed algorithm. From the computational results encouraging results are obtained in terms of solution quality.
APA, Harvard, Vancouver, ISO, and other styles
9

Sullivan, Kelly Ann. "A Convergence Analysis of Generalized Hill Climbing Algorithms." Diss., Virginia Tech, 1999. http://hdl.handle.net/10919/27027.

Full text
Abstract:
Generalized hill climbing (GHC) algorithms provide a unifying framework for describing several discrete optimization problem local search heuristics, including simulated annealing and tabu search. A necessary and a sufficient convergence condition for GHC algorithms are presented. The convergence conditions presented in this dissertation are based upon a new iteration classification scheme for GHC algorithms. The convergence theory for particular formulations of GHC algorithms is presented and the implications discussed. Examples are provided to illustrate the relationship between the new convergence conditions and previously existing convergence conditions in the literature. The contributions of the necessary and the sufficient convergence conditions for GHC algorithms are discussed and future research endeavors are suggested.
Ph. D.
APA, Harvard, Vancouver, ISO, and other styles
10

Campos, Danilo da Silva. "Integração dos problemas de carregamento e roteamento de veículos com janela de tempo e frota heterogênea." Universidade de São Paulo, 2008. http://www.teses.usp.br/teses/disponiveis/3/3136/tde-30052008-111539/.

Full text
Abstract:
Este trabalho aborda um problema ainda não explorado na literatura denominado 3L-FSMVRPTW (three-dimensional loading fleet sizing and mix vehicle routing problem with time windows), que compreende resolver simultaneamente o roteamento e carregamento tridimensional de veículos considerando frota heterogênea e janela de tempo. Foi desenvolvido um algoritmo específico para resolver o problema, denominado 3DC. Neste algoritmo foram introduzidas algumas inovações, entre elas, um novo operador de busca local (k-IntensiveSwap) e uma nova heurística de carregamento de contêiner. O algoritmo foi comparado aos melhores resultados disponíveis na literatura para problemas particulares ao apresentado. Houve bom desempenho no caso do CLP (container loading problem), bom resultado na redução do tamanho de frota no caso do 3L-VRP (threedimensional loading vehicle routing problem) e desempenho superior ao problema mais complexo estudado, o 3L-VRPTW (three-dimensional loading vehicle routing problem with time windows). Finalmente, apresentou-se um conjunto de avaliação, instâncias e soluções, para o problema completo com frota heterogênea e janela de tempo.
This work presents a problem not treated yet on the literature referenced as 3L-FSMVRPTW (three-dimensional loading fleet sizing and mix vehicle routing problem with time windows), which deals simultaneously with vehicle routing and its three-dimensional loading considering heterogeneous fleet and time windows. The algorithm developed for the specific problem is called 3DC. This algorithm introduces a new local search operator called k-IntensiveSwap and a new container loading heuristic. The results are compared with the best-known results from literature for particular problems embeeded on the general problem presented. The quality of solution was good in comparison other methods for CLP (container loading problem), it has good results in terms of reduction fleet sizing in the case of 3L-VRP (three-dimensional loading vehicle routing problem) and as for 3L-VRPTW (threedimensional loading vehicle routing problem with time windows) the performance was very superior. Finally, it is presented a solution set as benchmark for future comparison with the general problem, with heterogeneous fleet.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Books on the topic "Local search heuristics"

1

Voß, Stefan, Silvano Martello, Ibrahim H. Osman, and Catherine Roucairol, eds. Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization. Boston, MA: Springer US, 1998. http://dx.doi.org/10.1007/978-1-4615-5775-3.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Stützle, Thomas, Mauro Birattari, and Holger H. Hoos, eds. Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007. http://dx.doi.org/10.1007/978-3-540-74446-7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Stützle, Thomas, Mauro Birattari, and Holger H. Hoos, eds. Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-03751-1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Vo€, Stefan. Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization. Boston, MA: Springer US, 1999.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
5

Stefan, Voss, and Meta-Heuristics International Conference (2nd : 1997 : Sophia-Antipolis, France), eds. Meta-heuristics: Advances and trends in local search paradigms for optimization. Boston, Mass: Kluwer Academic Publishers, 1999.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
6

Thomas, Stützle, Birattari Mauro, and Hoos Holger H, eds. Engineering stochastic local search algorithms: Designing, implementing and analyzing effective heuristics : international workshop, SLS 2007, Brussels, Belgium, September 6-8, 2007 : proceedings. Berlin: Springer, 2007.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
7

H, Hoos Holger, Birattari Mauro, and SpringerLink (Online service), eds. Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics: Second International Workshop, SLS 2009, Brussels, Belgium, September 3-4, 2009. Proceedings. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
8

L, Aarts E. H., and Lenstra J. K, eds. Local search in combinatorial optimization. Princeton: Princeton University Press, 2003.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
9

L, Aarts E. H., and Lenstra J. K, eds. Local search in combinatorial optimization. Chichester [England]: Wiley, 1997.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
10

(Editor), Stefan Voß, Silvano Martello (Editor), Ibrahim H. Osman (Editor), and Cathérine Roucairol (Editor), eds. Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization. Springer, 1998.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Book chapters on the topic "Local search heuristics"

1

Alsheddy, Abdullah, Christos Voudouris, Edward P. K. Tsang, and Ahmad Alhindi. "Guided Local Search." In Handbook of Heuristics, 261–97. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-07124-4_2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Stützle, Thomas, and Rubén Ruiz. "Iterated Local Search." In Handbook of Heuristics, 579–605. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-07124-4_8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Alsheddy, Abdullah, Christos Voudouris, Edward P. K. Tsang, and Ahmad Alhindi. "Guided Local Search." In Handbook of Heuristics, 1–37. Cham: Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-07153-4_2-1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Stützle, Thomas, and Rubén Ruiz. "Iterated Local Search." In Handbook of Heuristics, 1–27. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-07153-4_8-1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Michiels, W., E. H. L. Aarts, and J. Korst. "Theory of Local Search." In Handbook of Heuristics, 299–339. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-07124-4_6.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Michel, Laurent, and Pascal Van Hentenryck. "Constraint-Based Local Search." In Handbook of Heuristics, 223–60. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-07124-4_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Michiels, W., E. H. L. Aarts, and J. Korst. "Theory of Local Search." In Handbook of Heuristics, 1–41. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-07153-4_6-1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Michel, Laurent, and Pascal Van Hentenryck. "Constraint-Based Local Search." In Handbook of Heuristics, 1–38. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-07153-4_7-1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

ten Eikelder, H. M. M., M. G. A. Verhoeven, T. W. M. Vossen, and E. H. L. Aarts. "A Probabilistic Analysis of Local Search." In Meta-Heuristics, 605–18. Boston, MA: Springer US, 1996. http://dx.doi.org/10.1007/978-1-4613-1361-8_36.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Brucker, Peter, and Johann Hurink. "Complex Sequencing Problems and Local Search Heuristics." In Meta-Heuristics, 151–66. Boston, MA: Springer US, 1996. http://dx.doi.org/10.1007/978-1-4613-1361-8_10.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Local search heuristics"

1

Lasisi, Ramoni O., and Robert DuPont. "Augmenting Stochastic Local Search with Heuristics." In 2018 9th IEEE Annual Ubiquitous Computing, Electronics & Mobile Communication Conference (UEMCON). IEEE, 2018. http://dx.doi.org/10.1109/uemcon.2018.8796721.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Curran, Dara, Eugene Freuder, and Thomas Jansen. "Incremental evolution of local search heuristics." In the 12th annual conference. New York, New York, USA: ACM Press, 2010. http://dx.doi.org/10.1145/1830483.1830660.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Interian, Yannet, and Sara Bernardini. "Learning Interpretable Heuristics for WalkSAT." In 20th International Conference on Principles of Knowledge Representation and Reasoning {KR-2023}. California: International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/kr.2023/36.

Full text
Abstract:
Local search algorithms are well-known methods for solving large, hard instances of the satisfiability problem (SAT). The performance of these algorithms crucially depends on heuristics for setting noise parameters and scoring variables. The optimal setting for these heuristics varies for different instance distributions. In this paper, we present an approach for learning effective variable scoring functions and noise parameters by using reinforcement learning. We consider satisfiability problems from different instance distributions and learn specialized heuristics for each of them. Our experimental results show improvements with respect to both a WalkSAT baseline and another local search learned heuristic.
APA, Harvard, Vancouver, ISO, and other styles
4

Devarenne, Isabelle, Hakim Mabed, and Alexandre Caminada. "Intelligent Neighborhood Exploration in Local Search Heuristics." In 2006 18th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'06). IEEE, 2006. http://dx.doi.org/10.1109/ictai.2006.68.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

"Session details: Meta-heuristics and local search." In GECCO05: Genetic and Evolutionary Computation Conference. New York, NY, USA: ACM, 2005. http://dx.doi.org/10.1145/3249410.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

"Session details: Meta-heuristics and local search." In GECCO05: Genetic and Evolutionary Computation Conference. New York, NY, USA: ACM, 2005. http://dx.doi.org/10.1145/3249411.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Hu, Qifu, Ruyang Li, Qi Deng, Yaqian Zhao, and Rengang Li. "Enhancing Network by Reinforcement Learning and Neural Confined Local Search." In Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}. California: International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/236.

Full text
Abstract:
It has been found that many real networks, such as power grids and the Internet, are non-robust, i.e., attacking a small set of nodes would cause the paralysis of the entire network. Thus, the Network Enhancement Problem~(NEP), i.e., improving the robustness of a given network by modifying its structure, has attracted increasing attention. Heuristics have been proposed to address NEP. However, a hand-engineered heuristic often has significant performance limitations. A recently proposed model solving NEP by reinforcement learning has shown superior performance than heuristics on in-distribution datasets. However, their model shows considerably inferior out-of-distribution generalization ability when enhancing networks against the degree-based targeted attack. In this paper, we propose a more effective model with stronger generalization ability by incorporating domain knowledge including measurements of local network structures and decision criteria of heuristics. We further design a hierarchical attention model to utilize the network structure directly, where the query range changes from local to global. Finally, we propose neural confined local search~(NCLS) to realize the effective search of a large neighborhood, which exploits a learned model to confine the neighborhood to avoid exhaustive enumeration. We conduct extensive experiments on synthetic and real networks to verify the ability of our models.
APA, Harvard, Vancouver, ISO, and other styles
8

Marek, J., P. Holub, and H. Rudova. "Local Search Heuristics for Media Streams Planning Problem." In 2013 IEEE 27th International Conference on Advanced Information Networking and Applications (AINA). IEEE, 2013. http://dx.doi.org/10.1109/aina.2013.132.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Burke, Edmund, Tim Curtois, Matthew Hyde, Graham Kendall, Gabriela Ochoa, Sanja Petrovic, Jose A. Vazquez-Rodriguez, and Michel Gendreau. "Iterated local search vs. hyper-heuristics: Towards general-purpose search algorithms." In 2010 IEEE Congress on Evolutionary Computation (CEC). IEEE, 2010. http://dx.doi.org/10.1109/cec.2010.5586064.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Lv, Yuanhua, Dimitrios Lymberopoulos, and Qiang Wu. "An exploration of ranking heuristics in mobile local search." In the 35th international ACM SIGIR conference. New York, New York, USA: ACM Press, 2012. http://dx.doi.org/10.1145/2348283.2348325.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Local search heuristics' for particular source types:
Journal articles Dissertations / Theses Books
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography