Rozprawy doktorskie na temat „Local search”
Kliknij ten link, aby zobaczyć inne rodzaje publikacji na ten temat: Local search.
Utwórz poprawne odniesienie w stylach APA, MLA, Chicago, Harvard i wielu innych
Sprawdź 50 najlepszych rozpraw doktorskich naukowych na temat „Local search”.
Przycisk „Dodaj do bibliografii” jest dostępny obok każdej pracy w bibliografii. Użyj go – a my automatycznie utworzymy odniesienie bibliograficzne do wybranej pracy w stylu cytowania, którego potrzebujesz: APA, MLA, Harvard, Chicago, Vancouver itp.
Możesz również pobrać pełny tekst publikacji naukowej w formacie „.pdf” i przeczytać adnotację do pracy online, jeśli odpowiednie parametry są dostępne w metadanych.
Przeglądaj rozprawy doktorskie z różnych dziedzin i twórz odpowiednie bibliografie.
1
Brueggemann, Tobias. "Efficiency of local search". Enschede : University of Twente [Host], 2006. http://doc.utwente.nl/57144.
Pełny tekst źródła
2
Tairan, Nasser. "Cooperative guided local search". Thesis, University of Essex, 2012. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.573069.
Pełny tekst źródłaStreszczenie:
Over the past few decades, meta-heuristic algorithms (MHs) have proven to be powerful tools for dealing with difficult combinational optimization problems (COPs). These techniques can obtain high quality solutions within reasonable computational time for many hard ,.' A' problems. Among these methods, guided local search (GLS) is p'femising one. The proximate optimality principle (POP), an underlying assumption in most meta-heuristics, assumes that good solutions have similar structures. Structures which are common to good solutions are more likely to be part of the best solution. In this thesis we discuss how the performance of the GLS can be further enhanced through designing a cooperative mechanism based on the proximate optimality principle (POP). The approach that we took was to search for solutions using multiple agents, each of which running a copy of GLS. These agents benefit from each other through the exchange of information based on POP. We suggest based on POP that common features that appear in many locally optimal solutions of GLS agents are more likely to be parts of the globally optimal solution. Thus, this property should be taken into consideration during the search. We call this framework Population-based GLS (P-GLS). P-GLS shows its efficiency and effectiveness to converge quickly to promising regions of the search space in an intelligent manner. Four P-GLS versions are proposed which enhance the performance of P-GLS. These algorithms are extensively studied and tested on Traveling salesman problem (TSP), Multidimensional Knapsack Problem (MKP) and Field Workforce Scheduling Problem (FWSP). Computational results confirm the effectiveness of P-GLS compared to original GLS and other well known MHs.
3
So, D. G. "Local search and simulation". Thesis, Swansea University, 1995. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.639084.
Pełny tekst źródłaStreszczenie:
Simulation has long been recognised as a powerful technique for analysing complex systems which are mathematically intractable. The objectives of simulation experiments are essentially of two types, namely for investigative and optimisation purposes. As far as the latter is concerned, analysts essentially aim to find the combination of input parameters to the system being investigated so as to optimise some performance measures. The discovery of a 'good' combination of input parameters frequently involves a long and tedious trial and error process which is often computationally demanding. This thesis concerns the automation of the process. In particular, various search algorithms are developed within the framework of local search. These algorithms are used to automatically search for 'promising', or even optimal, parameter settings where the function to be optimised is the output of a simulation model. An important distinction between the work described in this thesis and the more conventional use of local search lies in the nature of the cost function. While the conventional application of local search mainly focuses on problems with a deterministic cost function, this work considers problems in which the cost function is subject to some stochastic infrastructure. To ensure a successful implementation of local search to such problems, it is crucial that the stochastic variation in the cost function is explicitly taken into account. Various strategies to achieve this end are identified and ways in which they can be incorporated into the standard acceptance criteria of local search algorithms are described.
4
Ågren, Magnus. "Set Constraints for Local Search". Doctoral thesis, Uppsala universitet, Avdelningen för datalogi, 2007. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-8373.
Pełny tekst źródłaStreszczenie:
Combinatorial problems are ubiquitous in our society and solving such problems efficiently is often crucial. One technique for solving combinatorial problems is constraint-based local search. Its compositional nature together with its efficiency on large problem instances have made this technique particularly attractive. In this thesis we contribute to simplifying the solving of combinatorial problems using constraint-based local search. To provide higher-level modelling options, we introduce set variables and set constraints in local search by extending relevant local search concepts. We also propose a general scheme to follow in order to define what we call natural and balanced constraint measures, and accordingly define such measures for over a dozen set constraints. However, defining such measures for a new constraint is time-consuming and error-prone. To relieve the user from this, we provide generic measures for any set constraint modelled in monadic existential second-order logic. We also theoretically relate these measures to our proposed general scheme, and discuss implementation issues such as incremental algorithms and their worst-case complexities. To enable higher-level search algorithms, we introduce constraint-directed neighbourhoods in local search by proposing new constraint primitives for representing such neighbourhoods. Based on a constraint, possibly modelled in monadic existential second-order logic, these primitives return neighbourhoods with moves that are known in advance to achieve a decrease (or preservation, or increase) of the constraint measures, without the need to iterate over any other moves. We also present a framework for constraint-based local search where one can model and solve combinatorial problems with set variables and set constraints, use any set constraint modelled in monadic existential second-order logic, as well as use constraint-directed neighbourhoods. Experimental results on three real-life problems show the usefulness in practice of our theoretical results: our running times are comparable to the current state-of-the-art approaches to solving the considered problems.
5
Southey, Finnegan. "Augmenting Local Search for Satisfiability". Thesis, University of Waterloo, 2004. http://hdl.handle.net/10012/1075.
Pełny tekst źródłaStreszczenie:
This dissertation explores approaches to the satisfiability problem, focusing on local search methods. The research endeavours to better understand how and why some local search methods are effective. At the root of this understanding are a set of metrics that characterize the behaviour of local search methods. Based on this understanding, two new local search methods are proposed and tested, the first, SDF, demonstrating the value of the insights drawn from the metrics, and the second, ESG, achieving state-of-the-art performance and generalizing the approach to arbitrary 0-1 integer linear programming problems. This generality is demonstrated by applying ESG to combinatorial auction winner determination. Further augmentations to local search are proposed and examined, exploring hybrids that incorporate aspects of backtrack search methods.
6
Ågren, Magnus. "Set constraints for local search /". Uppsala : Acta Universitatis Upsaliensis, 2007. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-8373.
Pełny tekst źródła
7
Mills, P. H. "Extensions to Guided Local Search". Thesis, University of Essex, 2002. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.391658.
Pełny tekst źródła
8
Magnusson, Jesper. "Guiding Local Search using Approximations". Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-372074.
Pełny tekst źródłaStreszczenie:
Proving that a program is correct can be done by translating it into a first-order formula and trying to prove that it is valid. Programs often contain data structures such as Floating-point numbers, for which current solvers struggle because of the computational complexity of these theories. By using approximations, the precision of the floating-point numbers can be reduced to lower the complexity making it easier for the solvers. If a solution to the approximate formula can be found, it is often close to a solution of the original formula. A reconstruction of this solution can be made by modifying it in different ways as an attempt to reconstruct it into a solution of the original formula. In this thesis a local-search algorithm is implemented as a reconstruction. By continuously keeping a candidate solution, starting with the approximate one it is possible to iteratively make small modifications to search for nearby candidates and eventually find a solution to the original formula. Three different configurations are implemented, evaluated against each other and also against existing reconstructions. Tests shows that a local-search reconstruction can be viable and opens up for further testing of different configurations.
9
Martinsson, Roy. "Software Vulnerability Assessment : local search methods". Thesis, Blekinge Tekniska Högskola, Avdelningen för programvarusystem, 2006. http://urn.kb.se/resolve?urn=urn:nbn:se:bth-4270.
Pełny tekst źródłaStreszczenie:
In this thesis, we analyse different ways of detecting application vulnerabilities on installed software. Based on this research, a prototype will be developed that will validate these findings. The prototype will analyse only known vulnerabilities collected from a database and matched with locally collected data.
10
Ågren, Magnus. "High-level modelling and local search". Licentiate thesis, Uppsala universitet, Avdelningen för datalogi, 2005. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-86352.
Pełny tekst źródłaStreszczenie:
Combinatorial optimisation problems are ubiquitous in our society and appear in such varied guises as DNA sequencing, scheduling, configuration, airline-crew and nurse rostering, combinatorial auctions, vehicle routing, and financial portfolio design. Their efficient solution is crucial to many people and has been the target for much research during the last decades. One successful area of research for solving such problems is constraint programming. Yet, current-generation constraint programming languages are considered by many, especially in industry, to be too low-level, difficult, and large. In this thesis, we argue that solver-independent, high-level relational constraint modelling leads to a simpler and smaller language, to more concise, intuitive, and analysable models, as well as to more efficient and effective model formulation, maintenance, reformulation, and verification. All this can be achieved without sacrificing the possibility of efficient solving, so that even time-pressed modellers can be well assisted. Towards this, we propose the ESRA relational constraint modelling language, showcase its elegance on some real-life problems, and outline a compilation philosophy for such languages. In order to compile high-level languages such as ESRA to current generation constraint programming languages, it is essential that as much support as possible is available in these languages. This is already the case in the constructive search area of constraint programming where, e.g., different kinds of domain variables, such as integer variables and set variables, and expressive global constraints are readily available. However, in the local search area of constraint programming, this is not yet the case and, until now, set variables were for example not available. This thesis introduces set variables and set constraints in the local search area of constraint programming and, by doing this, considerably improves the possibilities for using local search. This is true both for modelling and solving problems using constraint-based local search, as well as for using it as a possible target for the compilation of ESRA models. Indeed, many combinatorial optimisation problems have natural models based on set variables and set constraints, three of which are successfully solved in this thesis. When a new set constraint is introduced in local search, much effort must be spent on the design and implementation of an appropriate incremental penalty function for the constraint. This thesis introduces a scheme that, from a high-level description of a set constraint in existential second-order logic with counting, automatically synthesises an incremental penalty function for that constraint. The performance of this scheme is demonstrated by solving real-life instances of a financial portfolio design problem that seem unsolvable in reasonable time by constructive search.
11
Ågren, Magnus. "High-level modelling and local search /". Uppsala : Univ. : Dept. of Information Technology, Univ, 2005. http://www.it.uu.se/research/publications/lic/2005-003/.
Pełny tekst źródła
12
Khetan, Amit 1978. "Local search for optimizing instruction cache". Thesis, Massachusetts Institute of Technology, 1999. http://hdl.handle.net/1721.1/80076.
Pełny tekst źródła
13
Cai, Shaowei. "Novel Local Search Methods for Satisfiability". Thesis, Griffith University, 2015. http://hdl.handle.net/10072/366424.
Pełny tekst źródłaStreszczenie:
The Boolean Satisfiability Problem (SAT) is a prototypical NP-complete problem, and is central in computer science and artificial intelligence. Given a formula over a set of Boolean variables, the SAT problem tests whether an interpretation that satisfies the formula exists.
Stochastic Local Search (SLS) is a simple but effective approach to SAT. In this thesis, we proposed new SLS techniques for SAT solving and developed new SLS algorithms. Using empirical evaluations, we showed that at the time they were designed our algorithms performed better than the existing state-of-the-art solvers. Moreover, our algorithms have been established as the latest state-of-the-art algorithms for several types of instances.
The first idea is configuration checking (CC) for SAT. A typical CC technique is to forbid flipping a variable if since the last time it was flipped, none of its neighbouring variables has been flipped. Based on this strategy, we developed several solvers, including Swcca and CCAnr. In particular, CCAnr performed very well on crafted instances, and a hybrid solver CCAnr+glucose won the silver prize of Hard-combinatorial track in SAT Competition 2014.
The second idea is the notion of multilevel properties which consider the satisfaction degree of clauses. Using the CC strategy and the second level score, we developed the CCASat solver, which won the 2012 SAT Challenge random track. We also proposed several new scoring functions, which were used to design CScoreSAT and HScoreSAT. These two solvers are particularly efficient in solving random SAT instances with long clauses, and show one to two orders of magnitude improvement than previous solvers. Thirdly, we proposed a linear make function for tie-breaking in the famous algorithm WalkSAT, leading to the WalkSATlm algorithm. Our experiments demonstrate that WalkSATlm improves WalkSAT by orders of magnitudes on random k-SAT instances with k > 3.Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Institute for Integrated and Intelligent Systems
Science, Environment, Engineering and Technology
Full Text
14
Buljubasic, Mirsad. "Efficient local search for several combinatorial optimization problems". Thesis, Montpellier, 2015. http://www.theses.fr/2015MONTS010/document.
Pełny tekst źródłaStreszczenie:
Cette thèse porte sur la conception et l'implémentation d'algorithmes approchés pour l'optimisation en variables discrètes. Plus particulièrement, dans cette étude nous nous intéressons à la résolution de trois problèmes combinatoires difficiles : le « Bin-Packing », la « Réaffectation de machines » et la « Gestion des rames sur les sites ferroviaires ». Le premier est un problème d'optimisation classique et bien connu, tandis que les deux autres, issus du monde industriel, ont été proposés respectivement par Google et par la SNCF. Pour chaque problème, nous proposons une approche heuristique basée sur la recherche locale et nous comparons nos résultats avec les meilleurs résultats connus dans la littérature. En outre, en guise d'introduction aux méthodes de recherche locale mise en œuvre dans cette thèse, deux métaheuristiques, GRASP et Recherche Tabou, sont présentées à travers leur application au problème de la couverture minimaleThis Ph.D. thesis concerns algorithms for Combinatorial Optimization Problems. In Combinatorial Optimization Problems the set of feasible solutions is discrete or can be reduced to a discrete one, and the goal is to find the best possible solution. Specifically, in this research we consider three different problems in the field of Combinatorial Optimization including One-dimensional Bin Packing (and two similar problems), Machine Reassignment Problem and Rolling Stock Problem. The first one is a classical and well known optimization problem, while the other two are real world and very large scale problems arising in industry and have been recently proposed by Google and French Railways (SNCF) respectively. For each problem we propose a local search based heuristic algorithm and we compare our results with the best known results in the literature. Additionally, as an introduction to local search methods, two metaheuristic approaches, GRASP and Tabu Search are explained through a computational study on Set Covering Problem
15
Pfitzner, Darius Mark, i pfit0022@flinders edu au. "An Investigation into User Text Query and Text Descriptor Construction". Flinders University. Computer Science, Engineering and Mathematics, 2009. http://catalogue.flinders.edu.au./local/adt/public/adt-SFU20090805.141402.
Pełny tekst źródłaStreszczenie:
Cognitive limitations such as those described in Miller's (1956) work on channel capacity and Cowen's (2001) on short-term memory are factors in determining user cognitive load and in turn task performance. Inappropriate user cognitive load can reduce user efficiency in goal realization. For instance, if the user's attentional capacity is not appropriately applied to the task, distractor processing can tend to appropriate capacity from it. Conversely, if a task drives users beyond their short-term memory envelope, information loss may be realized in its translation to long-term memory and subsequent retrieval for task base processing.
To manage user cognitive capacity in the task of text search the interface should allow users to draw on their powerful and innate pattern recognition abilities. This harmonizes with Johnson-Laird's (1983) proposal that propositional representation is tied to mental models. Combined with the theory that knowledge is highly organized when stored in memory an appropriate approach for cognitive load optimization would be to graphically present single documents, or clusters thereof, with an appropriate number and type of descriptors. These descriptors are commonly words and/or phrases.
Information theory research suggests that words have different levels of importance in document topic differentiation. Although key word identification is well researched, there is a lack of basic research into human preference regarding query formation and the heuristics users employ in search. This lack extends to features as elementary as the number of words preferred to describe and/or search for a document. Contrastive understanding these preferences will help balance processing overheads of tasks like clustering against user cognitive load to realize a more efficient document retrieval process. Common approaches such as search engine log analysis cannot provide this degree of understanding and do not allow clear identification of the intended set of target documents.
This research endeavours to improve the manner in which text search returns are presented so that user performance under real world situations is enhanced. To this end we explore both how to appropriately present search information and results graphically to facilitate optimal cognitive and perceptual load/utilization, as well as how people use textual information in describing documents or constructing queries.
16
Gambardella, Luca Maria. "Coupling ant colony system with local search". Doctoral thesis, Universite Libre de Bruxelles, 2015. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/209045.
Pełny tekst źródłaStreszczenie:
In the last decades there has been a lot of interest in computational models and metaheuristics algorithms capable to solve combinatorial optimization problems. The recent trend is to define these algorithms taking inspiration by the observation of natural systems. In this thesis the Ant Colony System (ACS) is presented which has been inspired by the observation of real ant colonies. ACS is initially proposed to solve the symmetric and asymmetric travelling salesman problems where it is shown to be competitive with other metaheuristics. Although this is an interesting and promising result, it was immediately clear that ACS, as well as other metaheuristics, in many cases cannot compete with specialized local search methods. An interesting trend is therefore to couple metaheuristics with a local optimizer, giving birth to so-called hybrid methods. Along this line, the thesis investigates MACS-VRPTW (Multiple ACS for the Vehicle Routing Problem with Time Windows) and HAS-SOP: Hybrid Ant System for the Sequential Ordering Problem (SOP). In the second part the thesis introduces some modifications of the original ACS algorithm. These modifications are able to speed up the method and to make it more competitive in case of large problem instances. The resulting framework, called Enhanced Ant Colony System is tested for the SOP. Finally the thesis presents the application of ACS to solve real-life vehicle routing problems where additional constraints and stochastic information are included.Doctorat en Sciences de l'ingénieur
info:eu-repo/semantics/nonPublished
17
Thornton, John Richard, i n/a. "Constraint Weighting Local Search for Constraint Satisfaction". Griffith University. School of Computing and Information Technology, 2000. http://www4.gu.edu.au:8080/adt-root/public/adt-QGU20050901.142439.
Pełny tekst źródłaStreszczenie:
One of the challenges for the constraint satisfaction community has been to develop an automated approach to solving Constraint Satisfaction Problems (CSPs) rather than creating specific algorithms for specific problems. Much of this work has concentrated on the development and improvement of general purpose backtracking techniques. However, the success of relatively simple local search techniques on larger satisfiability problems [Selman et a!. 1992] and CSPs such as the n-queens [Minton et al. 1992] has caused interest in applying local search to constraint satisfaction. In this thesis we look at the usefulness of constraint weighting as a local search technique for constraint satisfaction. The work is based on the clause weighting ideas of Selman and Kautz [1993] and Moths [1993] and applies, evaluates and extends these ideas from the satisfiability domain to the more general domain of CSPs. Specifically, the contributions of the thesis are: 1. The introduction of a local search taxonomy. We examine the various better known local search techniques and recognise four basic strategies: restart, randomness, memory and weighting. 2. The extension of the CSP modelling framework. In order to represent and efficiently solve more realistic problems we extend the C SP modelling framework to include array-based domains and array-based domain use constraints. 3. The empirical evaluation of constraint weighting. We compare the performance of three constraint weighting strategies on a range of CSP and satisflability problems and with several other local search techniques. We find that no one technique dominates in all problem domains. 4. The characterisation of constraint weighting performance. Based on our empirical study we identiIS' the weighting behaviours and problem features that favour constrtt weighting. We conclude weighting does better on structured problems where the algorithm can recognise a harder sub-group of constraints. 5. The extension of constraint weighting. We introduce an efficient arc weighting algorithm that additionally weights connections between constraints that are simultaneously violated at a local minimum. This algorithm is empirically shown to outperform standard constraint weighting on a range of CSPs and within a general constraint solving system. Also we look at combining constraint weighting with other local search heuristics and find that these hybrid techniques can do well on problems where the parent algorithms are evenly matched. 6. The application of constraint weighting to over constrained domains. Our empirical work suggests constraint weighting does well for problems with distinctions between constraint groups. This led us to investigate solving real-world over constrained problems with hard and soft constraint groups and to introduce two dynamic constraint weighting heuristics that maintain a distinction between hard and soft constraint groups while still adding weights to violated constraints in a local minimum. In an empirical study, the dynamic schemes are shown to outperform other fixed weighting and non-weighting systems on a range of real world problems. In addition, the performance of weighting is shown to degrade less severely when soft constraints are added to the system, suggesting constraint weighting is especially applicable to realistic, hard and soft constraint problems
18
Khanum, Rashida Adeeb. "Hybrid evolutionary alogrithms and local search techniques". Thesis, University of Essex, 2013. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.589450.
Pełny tekst źródłaStreszczenie:
Population-based stochastic global search/optimisation algorithms often generate solutions with low accuracy. However, they cover the search space well; a property we refer to as exploration. In contrast, local optimisation algorithms, largely deterministic, find solutions with high accuracy when left to run long enough; they have the property we refer to as exploitation. Local optimisation algorithms, by their very nature, do not cover well the search space. It is also well known that some are more computationally demanding than others. It is, therefore, attractive to try and design algorithms which are good both at exploration and exploitation, but also have reasonable computing demands. A popular way to achieving this is to hybridise algorithms which have the desired properties. In this thesis, we consider the hybidisation of Adaptive Differential Evolution and Particle Swarm Optimisation algorithms with local search algorithms namely the Broyden-Fletcher-Goldfard-Shanno algorithm, the Steepest-Descent algorithm and the Nelder-Mead Simplex algorithm. Three combinations have been investigated. • Adaptive Differential Evolution with an Expensive Local Search Method, referred to as Hybridization of Adaptive Differential Evolution with an Expensive Local Search Method; it combines a variant of Differential Evolution, Adaptive Differential Evolution with Optional External Archive, with the Broydon-Fletcher-Goldfarb-Shanno updating method, as the local search method. • Adaptive Differential Evolution and two local search algorithms, one expensive represented by Broydon-Fletcher-Goldfarb-Shanno, and the other comparatively cheap, represented by the Steepest Descent with a restart strategy; this is referred to as Hybridization of Adaptive Differential Evolution and Two Local Search Techniques with a Restart Strategy. • Particle Swarm Optimization algorithm with the Nelder-Mead Simplex algorithm, which is derivative-free, unlike the other two local search algorithms. This is referred to as A Hybridization of Particle Swarm Optimization with the Nelder-Mead Simplex Algorithm. These hybrid algorithms are then applied to unconstrained nonlinear optimization problems. Tests are carried out on well known problems from the Congress on Evolutionary Computation 2005(CEC2005) as well as those of the Congress on Evolutionary Computation 2010(CEC2010) test suits. Results show that improvements can be gained, but still at a cost. The thesis also contains an extensive review of the literature concerned with hybridization, particularly of evolutionary type algorithms with both classical and novel optimization approaches.
19
Ehrencrona, Kjellin Patrik. "Airspace Sectorisation Using Constraint-Based Local Search". Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-233385.
Pełny tekst źródłaStreszczenie:
Airspace sectorisation is the optimisation problem of dividing a given airspace into sectors in a way that promotes efficient air traffic management by some quantifiable measure. In this thesis, we apply constraint-based local search on real world airspace data collected from airports in Europe, given a selection of relevant constraints.
20
Voudouris, Christos. "Guided local search for combinatorial optimisation problems". Thesis, University of Essex, 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.361019.
Pełny tekst źródła
21
Björdal, Gustav. "String Variables for Constraint-Based Local Search". Thesis, Uppsala universitet, Avdelningen för datalogi, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-301501.
Pełny tekst źródłaStreszczenie:
String variables occur as a natural part of many computationally challenging problems. Usually, such problems are solved using problem-specific algorithms implemented from first principles, which can be a time-consuming and error-prone task. A constraint solver is a framework that can be used to solve computationally challenging problems by first declaratively defining the problem and then solving it using specialised off-the-shelf algorithms, which can cut down development time significantly and result in faster solution times and higher solution quality. There are many constraint solving technologies, one of which is constraint-based local search (CBLS). However, very few constraint solvers have native support for solving problems with string variables. The goal of this thesis is to add string variables as a native type to the CBLS solver OscaR/CBLS. The implementation was experimentally evaluated on the Closest String Problem and the Word Equation System problem. The evaluation shows that string variables for CBLS can be a viable option for solving string problems. However, further work is required to obtain even more competitive performance.
22
Xu, Ruoxi. "Regression Model Stochastic Search via Local Orthogonalization". The Ohio State University, 2011. http://rave.ohiolink.edu/etdc/view?acc_num=osu1322589253.
Pełny tekst źródła
23
Thornton, John. "Constraint Weighting Local Search for Constraint Satisfaction". Thesis, Griffith University, 2000. http://hdl.handle.net/10072/367954.
Pełny tekst źródłaStreszczenie:
One of the challenges for the constraint satisfaction community has been to develop an automated approach to solving Constraint Satisfaction Problems (CSPs) rather than creating specific algorithms for specific problems. Much of this work has concentrated on the development and improvement of general purpose backtracking techniques. However, the success of relatively simple local search techniques on larger satisfiability problems [Selman et a!. 1992] and CSPs such as the n-queens [Minton et al. 1992] has caused interest in applying local search to constraint satisfaction. In this thesis we look at the usefulness of constraint weighting as a local search technique for constraint satisfaction. The work is based on the clause weighting ideas of Selman and Kautz [1993] and Moths [1993] and applies, evaluates and extends these ideas from the satisfiability domain to the more general domain of CSPs. Specifically, the contributions of the thesis are: 1. The introduction of a local search taxonomy. We examine the various better known local search techniques and recognise four basic strategies: restart, randomness, memory and weighting. 2. The extension of the CSP modelling framework. In order to represent and efficiently solve more realistic problems we extend the C SP modelling framework to include array-based domains and array-based domain use constraints. 3. The empirical evaluation of constraint weighting. We compare the performance of three constraint weighting strategies on a range of CSP and satisflability problems and with several other local search techniques. We find that no one technique dominates in all problem domains. 4. The characterisation of constraint weighting performance. Based on our empirical study we identiIS' the weighting behaviours and problem features that favour constrtt weighting. We conclude weighting does better on structured problems where the algorithm can recognise a harder sub-group of constraints. 5. The extension of constraint weighting. We introduce an efficient arc weighting algorithm that additionally weights connections between constraints that are simultaneously violated at a local minimum. This algorithm is empirically shown to outperform standard constraint weighting on a range of CSPs and within a general constraint solving system. Also we look at combining constraint weighting with other local search heuristics and find that these hybrid techniques can do well on problems where the parent algorithms are evenly matched. 6. The application of constraint weighting to over constrained domains. Our empirical work suggests constraint weighting does well for problems with distinctions between constraint groups. This led us to investigate solving real-world over constrained problems with hard and soft constraint groups and to introduce two dynamic constraint weighting heuristics that maintain a distinction between hard and soft constraint groups while still adding weights to violated constraints in a local minimum. In an empirical study, the dynamic schemes are shown to outperform other fixed weighting and non-weighting systems on a range of real world problems. In addition, the performance of weighting is shown to degrade less severely when soft constraints are added to the system, suggesting constraint weighting is especially applicable to realistic, hard and soft constraint problemsThesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Computing and Information Technology
Science, Environment, Engineering and Technology
Full Text
24
Shatabda, Swakkhar. "Local Search Heuristics for Protein Structure Prediction". Thesis, Griffith University, 2014. http://hdl.handle.net/10072/365446.
Pełny tekst źródłaStreszczenie:
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
25
He, Jun. "Constraints for Membership in Formal Languages under Systematic Search and Stochastic Local Search". Doctoral thesis, Uppsala universitet, Avdelningen för datalogi, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-196347.
Pełny tekst źródłaStreszczenie:
This thesis focuses on constraints for membership in formal languages under both the systematic search and stochastic local search approaches to constraint programming (CP). Such constraints are very useful in CP for the following three reasons: They provide a powerful tool for user-level extensibility of CP languages. They are very useful for modelling complex work shift regulation constraints, which exist in many shift scheduling problems. In the analysis, testing, and verification of string-manipulating programs, string constraints often arise. We show in this thesis that CP solvers with constraints for membership in formal languages are much more suitable than existing solvers used in tools that have to solve string constraints. In the stochastic local search approach to CP, we make the following two contributions: We introduce a stochastic method of maintaining violations for the regular constraint and extend our method to the automaton constraint with counters. To improve the usage of constraints for which there exists no known constant-time algorithm for neighbour evaluation, we introduce a framework of using solution neighbourhoods, and give an efficient algorithm of constructing a solution neighbourhood for the regular constraint. In the systematic search approach to CP, we make the following two contributions: We show that there may be unwanted consequences when using a propagator that may underestimate a cost of a soft constraint, as the propagator may guide the search to incorrect (non-optimum) solutions to an over-constrained problem. We introduce and compare several propagators that compute correctly the cost of the edit-distance based soft-regular constraint. We show that the context-free grammar constraint is useful and introduce an improved propagator for it.
26
Madrigali, Andrea. "Analysis of Local Search Methods for 3D Data". Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2016.
Znajdź pełny tekst źródłaStreszczenie:
In questa tesi sono stati analizzati alcuni metodi di ricerca per dati 3D. Viene illustrata una panoramica generale sul campo della Computer Vision, sullo stato dell’arte dei sensori per l’acquisizione e su alcuni dei formati utilizzati per la descrizione di dati 3D. In seguito è stato fatto un approfondimento sulla 3D Object Recognition dove, oltre ad essere descritto l’intero processo di matching tra Local Features, è stata fatta una focalizzazione sulla fase di detection dei punti salienti. In particolare è stato analizzato un Learned Keypoint detector, basato su tecniche di apprendimento di machine learning. Quest ultimo viene illustrato con l’implementazione di due algoritmi di ricerca di vicini: uno esauriente (K-d tree) e uno approssimato (Radial Search). Sono state riportate infine alcune valutazioni sperimentali in termini di efficienza e velocità del detector implementato con diversi metodi di ricerca, mostrando l’effettivo miglioramento di performance senza una considerabile perdita di accuratezza con la ricerca approssimata.
27
Béjar, Torres Ramón. "Systematic and local search algorithms for regular-SAT". Doctoral thesis, Universitat Autònoma de Barcelona, 2000. http://hdl.handle.net/10803/3018.
Pełny tekst źródła
28
Zahrani, Mohammed Saeed. "Genetic local search algorithms for selected graph problems". Thesis, University of Hertfordshire, 2006. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.440188.
Pełny tekst źródła
29
Wattanawaroon, Tana. "Local versus global tables in Minimax Game Search". Thesis, Massachusetts Institute of Technology, 2014. http://hdl.handle.net/1721.1/92088.
Pełny tekst źródłaStreszczenie:
Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014.Cataloged from PDF version of thesis.
Includes bibliographical references (page 33).
Minimax Game Search with alpha-beta pruning can utilize heuristic tables in order to prune more branches and achieve better performance. The tables can be implemented using different memory models: global tables, worker-local tables and processor-local tables. Depending on whether each heuristic table depends on locality in the game tree, a memory model might be more suitable than others. This thesis describes an experiment that shows that local tables are generally preferable to global tables for two game heuristics used in chess-like games: killer move and best move history. The experiment is evidence that local tables might be useful for multithreaded applications, particularly ones that involve caching and exhibit locality.
by Tana Wattanawaroon.
M. Eng.
30
Benlic, Una. "Breakout local search pour les problèmes d'optimisation difficiles". Angers, 2012. http://www.theses.fr/2012ANGE0049.
Pełny tekst źródłaStreszczenie:
En raison de la complexité inhérente aux problèmes difficiles d'optimisation combinatoire, les algorithmes heuristiques ont permis de réaliser des progrès remarquables dans la résolution de cette classe de problèmes au cours des trois dernières décennies. Bien que certaines méthodes heuristiques soient conçues pour traiter des problèmes très spécifiques, d'autres méthodes sont générales et peuvent être appliquées à n'importe quel type de problème. Les exemples d'heuristiques générales sont les méthodes de recherche par voisinage, telles que la recherche tabou, la recherche locale itérée, ou le recuit simulé, et les méthodes bio-inspirées, telles que les algorithmes évolutionnaires ou l'optimisation par colonies de fourmis. Ce travail est dédié à l'élaboration d'une méthode heuristique, nommée Breakout Local Search (BLS), qui peut être considérée comme une hybridation de plusieurs métaheuristiques bien établies. BLS est une variante de la recherche locale itérée puisque son idée de base est d'alterner itérativement entre une descente classique pour découvrir des optima locaux, et une stratégie de diversification dédiée, pour se déplacer d'un attracteur vers un autre dans l'espace de recherche. L'originalité de BLS réside dans son mécanisme de diversification, qui choisit de manière adaptative entre deux types de perturbation et ajuste dynamiquement la force des perturbations en fonction de l'état actuel de la recherche. Jusqu'à présent, nous avons testé BLS sur plusieurs problèmes classiques d'optimisation combinatoire: le problème de la clique maximum (cas pondéré et non-pondéré), l'affectation quadratique, le partitionnement de graphe, la coupe maximum et le problème de la somme coloration minimale. Par rapport aux algorithmes de l'état de l'art, notre stratégie procure des performances remarquables pour ces problèmes. Pour un nombre important d'instances de la clique maximum pondérée, la coupe maximum et le partitionnement de graphe, ainsi que pour plusieurs instances de la somme coloration minimale, notre méthode BLS est même capable d'améliorer les meilleures résultats présentés dans la littérature. Pour améliorer encore les performances sur les problèmes de partitionnement de graphe et d'affectation quadratique, nous avons présenté en outre deux algorithmes mémétiques qui utilisent BLS dans la phase de recherche locale. Par ailleurs, un autre objectif de ce travail est également d'expliquer, dans une certaine mesure, le comportement de l'approche proposée sur différents types de structures de problèmesDue to the inherent computational complexity of hard combinatorial optimization prob- lems, the last several decades have seen a surge of interest in using heuristic algorithms to tackle this class of problems. While some of the heuristic methods are problem-specific, others are problem-independent since they ma1‹e few or no assumption about the problem being optimized. Examples of modern problem-independent heuristics are neighborhood search methods like tabu search, iterated local search, or simulated annealing, and biolog- ically inspired methods such as evolutionary algorithms or ant colony optimization. This work is dedicated to the elaboration of a problem-independent heuristic method, named Breakout Local Search (BLS), which can be considered as a combination of several well- established metaheuristic methods. BLS is a variant of iterated local search approach, since its basic idea of to use local search to discover local optima and to employ adaptive diversification strategies to continually move from one local optimum to another in the search space. Based on the information on the state of search, the perturbation strat- egy of BLS introduces a varying degree of diversification by dynamically determining the number of moves for perturbation and by adaptively selecting between several types of dedicated moves. So far, we have tested BLS on a number of classical combinatorial op- timization problems including maximum clique problems (both weighted and unweighted cases), quadratic assignment, graph partitioning, maximum cut and maximum sum col- oring problems. Compared to the current state-of-art algorithms from the literature, the proposed method shows remarkable performance on these problems. For a significant num- ber of instances of maximum weight clique, maximum cut and graph partitioning, as well as for several smaller in9tances of minimum sum coloring problem, our BLS method is even able to attain new record-breaking results. To further improve the performance on graph partitioning and quadratic assignment problems, we additionally present two memetic al- gorithms w'hich use BLS as their local search procedure. Beside providing highly effective methods for a number of hard problems, another objective is also to explain to some extent the behaviour of the proposed approaches on different types of problem structures
31
Land, Mark William Shannon. "Evolutionary algorithms with local search for combinatorial optimization /". Diss., Connect to a 24 p. preview or request complete full text in PDF format. Access restricted to UC campuses, 1998. http://wwwlib.umi.com/cr/ucsd/fullcit?p9914083.
Pełny tekst źródła
32
Duong, Thach-Thao Nguyen. "Improving Diversification in Local Search for Propositional Satisfiability". Thesis, Griffith University, 2014. http://hdl.handle.net/10072/365717.
Pełny tekst źródłaStreszczenie:
In recent years, the Propositional Satisfiability (SAT) has become standard for encoding real world complex constrained problems. SAT has significant impacts on various research fields in Artificial Intelligence (AI) and Constraint Programming (CP). SAT algorithms have also been successfully used in solving many practical and industrial applications that include electronic design automation, default reasoning, diagnosis, planning, scheduling, image interpretation, circuit design, and hardware and software verification. The most common representation of a SAT formula is the Conjunctive Normal Form (CNF). A CNF formula is a conjunction of clauses where each clause is a disjunction of Boolean literals. A SAT formula is satisfiable if there is a truth assignment for each variable such that all clauses in the formula are satisfied. Solving a SAT problem is to determine a truth assignment that satisfies a CNF formula. SAT is the first problem proved to be NP-complete [20]. There are many algorithmic methodologies to solve SAT. The most obvious one is systematic search; however another popular and successful approach is stochastic local search (SLS). Systematic search is usually referred to as complete search or backtrack-style search. In contrast, SLS is a method to explore the search space by randomisation and perturbation operations. Although SLS is an incomplete search method, it is able to find the solutions effectively by using limited time and resources. Moreover, some SLS solvers can solve hard SAT problems in a few minutes while these problems could be beyond the capacity of systematic search solvers.Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Information and Communication Technology
Science, Environment, Engineering and Technology
Full Text
33
Ferreira, Junior Valnir, i N/A. "Improvements to Clause Weighting Local Search for Propositional Satisfiability". Griffith University. Institute for Integrated and Intelligent Systems, 2007. http://www4.gu.edu.au:8080/adt-root/public/adt-QGU20070823.123257.
Pełny tekst źródłaStreszczenie:
The propositional satisfiability (SAT) problem is of considerable theoretical and practical relevance to the artificial intelligence (AI) community and has been used to model many pervasive AI tasks such as default reasoning, diagnosis, planning, image interpretation, and constraint satisfaction. Computational methods for SAT have historically fallen into two broad categories: complete search and local search. Within the local search category, clause weighting methods are amongst the best alternatives for SAT, becoming particularly attractive on problems where a complete search is impractical or where there is a need to find good candidate solutions within a short time. The thesis is concerned with the study of improvements to clause weighting local search methods for SAT. The main contributions are: A component-based framework for the functional analysis of local search methods. A clause weighting local search heuristic that exploits longer-term memory arising from clause weight manipulations. The approach first learns which clauses are globally hardest to satisfy and then uses this information to treat these clauses differentially during weight manipulation [Ferreira Jr and Thornton, 2004]. A study of heuristic tie breaking in the domain of additive clause weighting local search methods, and the introduction of a competitive method that uses heuristic tie breaking instead of the random tie breaking approach used in most existing methods [Ferreira Jr and Thornton, 2005]. An evaluation of backbone guidance for clause weighting local search, and the introduction of backbone guidance to three state-of-the-art clause weighting local search methods [Ferreira Jr, 2006]. A new clause weighting local search method for SAT that successfully exploits synergies between the longer-term memory and tie breaking heuristics developed in the thesis to significantly improve on the performance of current state-of-the-art local search methods for SAT-encoded instances containing identifiable CSP structure. Portions of this thesis have appeared in the following refereed publications: Longer-term memory in clause weighting local search for SAT. In Proceedings of the 17th Australian Joint Conference on Artificial Intelligence, volume 3339 of Lecture Notes in Artificial Intelligence, pages 730-741, Cairns, Australia, 2004. Tie breaking in clause weighting local search for SAT. In Proceedings of the 18th Australian Joint Conference on Artificial Intelligence, volume 3809 of Lecture Notes in Artificial Intelligence, pages 7081, Sydney, Australia, 2005. Backbone guided dynamic local search for propositional satisfiability. In
Proceedings of the Ninth International Symposium on Artificial Intelligence and Mathematics, AI&M, Fort Lauderdale, Florida, 2006.
34
Ferreira, Junior Valnir. "Improvements to Clause Weighting Local Search for Propositional Satisfiability". Thesis, Griffith University, 2007. http://hdl.handle.net/10072/365857.
Pełny tekst źródłaStreszczenie:
The propositional satisfiability (SAT) problem is of considerable theoretical and practical relevance to the artificial intelligence (AI) community and has been used to model many pervasive AI tasks such as default reasoning, diagnosis, planning, image interpretation, and constraint satisfaction. Computational methods for SAT have historically fallen into two broad categories: complete search and local search. Within the local search category, clause weighting methods are amongst the best alternatives for SAT, becoming particularly attractive on problems where a complete search is impractical or where there is a need to find good candidate solutions within a short time. The thesis is concerned with the study of improvements to clause weighting local search methods for SAT. The main contributions are: A component-based framework for the functional analysis of local search methods. A clause weighting local search heuristic that exploits longer-term memory arising from clause weight manipulations. The approach first learns which clauses are globally hardest to satisfy and then uses this information to treat these clauses differentially during weight manipulation [Ferreira Jr and Thornton, 2004]. A study of heuristic tie breaking in the domain of additive clause weighting local search methods, and the introduction of a competitive method that uses heuristic tie breaking instead of the random tie breaking approach used in most existing methods [Ferreira Jr and Thornton, 2005]. An evaluation of backbone guidance for clause weighting local search, and the introduction of backbone guidance to three state-of-the-art clause weighting local search methods [Ferreira Jr, 2006]. A new clause weighting local search method for SAT that successfully exploits synergies between the longer-term memory and tie breaking heuristics developed in the thesis to significantly improve on the performance of current state-of-the-art local search methods for SAT-encoded instances containing identifiable CSP structure. Portions of this thesis have appeared in the following refereed publications: Longer-term memory in clause weighting local search for SAT. In Proceedings of the 17th Australian Joint Conference on Artificial Intelligence, volume 3339 of Lecture Notes in Artificial Intelligence, pages 730-741, Cairns, Australia, 2004. Tie breaking in clause weighting local search for SAT. In Proceedings of the 18th Australian Joint Conference on Artificial Intelligence, volume 3809 of Lecture Notes in Artificial Intelligence, pages 70–81, Sydney, Australia, 2005. Backbone guided dynamic local search for propositional satisfiability. In Proceedings of the Ninth International Symposium on Artificial Intelligence and Mathematics, AI&M, Fort Lauderdale, Florida, 2006.Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Institute for Integrated and Intelligent Systems
Full Text
35
Goh, Say Leng. "An investigation of Monte Carlo tree search and local search for course timetabling problems". Thesis, University of Nottingham, 2017. http://eprints.nottingham.ac.uk/43558/.
Pełny tekst źródłaStreszczenie:
The work presented in this thesis focuses on solving course timetabling problems, a variant of education timetabling. Automated timetabling is a popular topic among researchers and practitioners because manual timetable construction is impractical, if not impossible, as it is known to be NP-hard. A two-stage approach is investigated. The first stage involves finding feasible solutions. Monte Carlo Tree Search (MCTS) is utilized in this stage. As far as we are aware, it is used for the first time in addressing the timetabling problem. It is a relatively new search method and has achieved breakthrough in the domain of games particularly Go. Several enhancements are attempted on MCTS such as heuristic based simulations and pruning. We also compare the effectiveness of MCTS with Graph Coloring Heuristic (GCH) and Tabu Search (TS) based methods. Initial findings show that a TS based method is more promising, so we focus on improving TS. We propose an algorithm called Tabu Search with Sampling and Perturbation (TSSP). Among the enhancements that we introduced are event sampling, a novel cost function and perturbation. Furthermore, we hybridize TSSP with Iterated Local Search (ILS). The second stage focuses on improving the quality of feasible solutions. We propose a variant of Simulated Annealing called Simulated Annealing with Reheating (SAR). SAR has three features: a novel neighborhood examination scheme, a new way of estimating local optima and a reheating scheme. The rigorous setting of initial and end temperature in conventional SA is bypassed in SAR. Precisely, reheating and cooling were applied at the right time and level, thus saving time allowing the search to be performed efficiently. One drawback of SAR is having to preset the composition of neighborhood structures for the datasets. We present an enhanced variant of the SAR algorithm called Simulated Annealing with Improved Reheating and Learning (SAIRL). We propose a reinforcement learning based method to obtain a suitable neighborhood structure composition for the search to operate effectively. We also propose to incorporate the average cost changes into the reheated temperature function. SAIRL eliminates the need for tuning parameters in conventional SA as well as neighborhood structures composition in SAR. Experiments were tested on four publicly available datasets namely Socha, International Timetabling Competition 2002 (ITC02), International Timetabling Competition 2007 (ITC07) and Hard. Our results are better or competitive when compared with other state of the art methods where new best results are obtained for many instances.
36
Cornu, Marek. "Local Search, data structures and Monte Carlo Search for Multi-Objective Combinatorial Optimization Problems". Thesis, Paris Sciences et Lettres (ComUE), 2017. http://www.theses.fr/2017PSLED043/document.
Pełny tekst źródłaStreszczenie:
De nombreux problèmes d'optimisation combinatoire considèrent plusieurs objectifs, souvent conflictuels. Cette thèse s'intéresse à l'utilisation de méthodes de recherche locale, de structures de données et de recherche Monte-Carlo pour la recherche de l'ensemble des solutions efficaces de tels problèmes, représentant l'ensemble des meilleurs compromis pouvant être réalisés en considération de tous les objectifs.Nous proposons une nouvelle méthode d'approximation appelée 2-Phase Iterated Pareto Local Search based on Decomposition (2PIPLS/D) combinant les concepts de recherche locale Pareto (PLS) et de décomposition. La PLS est une descente de recherche locale adaptée au multi-objectif, et la décomposition consiste en la subdivision du problème multi-objectif en plusieurs problèmes mono-objectif. Deux méthodes d'optimisation mono-objectif sont considérées: la recherche locale itérée et la recherche Monte-Carlo imbriquée. Deux modules principaux sont intégrés à 2PIPLS/D. Le premier généralise et améliore une méthode existante et génère un ensemble initial de solutions. Le second réduit efficacement l'espace de recherche et permet d'accélérer la PLS sans négliger la qualité de l'approximation générée. Nous introduisons aussi deux nouvelles structures de données gérant dynamiquement un ensemble de solutions incomparables, la première est spécialisée pour le cas bi-objectif et la seconde pour le cas général.2PIPLS/D est appliquée au Problème du Voyageur de Commerce bi-objectif et tri-objectif et surpasse ses concurrents sur les instances testées. Ensuite, 2PIPLS/D est appliquée à un nouveau problème avec cinq objectifs en lien avec la récente réforme territoriale d'agrandissement des régions françaisesMany Combinatorial Optimization problems consider several, often conflicting, objectives. This thesis deals with Local Search, data structures and Monte Carlo Search methods for finding the set of efficient solutions of such problems, which is the set of all best possible trade-offs given all the objectives.We propose a new approximation method called 2-Phase Iterated Pareto Local Search based on Decomposition (2PIPLS/D) combining the notions of Pareto Local Search (PLS) and Decomposition. PLS is a local search descent adapted to Multi-Objective spaces, and Decomposition consists in the subdivision of the Multi-Objective problem into a number of Single-Objective problems. Two Single-Objective methods are considered: Iterated Local Search and Nested Monte Carlo Search. Two main components are embedded within the 2PIPLS/D framework. The first one generalizes and improves an existing method generating an initial set of solutions. The second one reduces efficiently the search space and accelerates PLS without notable impact on the quality of the generated approximation. We also introduce two new data structures for dynamically managing a set of incomparable solutions. The first one is specialized for the bi-objective case, while the second one is general.2PIPLS/D is applied to the bi-objective and tri-objective Traveling Salesman Problem and outperforms its competitors on tested instances. Then, 2PIPLS/D is instantiated on a new five-objective problem related to the recent territorial reform of French regions which resulted in the reassignment of departments to new larger regions
37
Magaji, Amina Sambo-Muhammad. "Combining search strategies for distributed constraint satisfaction". Thesis, Robert Gordon University, 2015. http://hdl.handle.net/10059/1374.
Pełny tekst źródłaStreszczenie:
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.
38
Schuster, Christoph Jörg. "No-wait-Job-Shop-Scheduling: Komplexität und local search". [S.l. : s.n.], 2003. http://deposit.ddb.de/cgi-bin/dokserv?idn=967617308.
Pełny tekst źródła
39
Gumucio, Escobar Rodrigo Ronald. "Constraints on Set Variables for Constraint-based Local Search". Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-159180.
Pełny tekst źródła
40
Husain, Syed S. "Robust aggregation of local image descriptors for visual search". Thesis, University of Surrey, 2016. http://epubs.surrey.ac.uk/810765/.
Pełny tekst źródłaStreszczenie:
Visual search and recognition underpins numerous applications including management of multimedia content, mobile commerce, surveillance, navigation, robotics and many others. However the task is still challenging predominantly due to the variability of object appearance and ever increasing size of the databases, often exceeding billions of images. The objective of this thesis is to develop a robust, compact and discriminative image representation suitable for tasks of visual search. This thesis contributes to four research areas. First we propose a novel method, named Robust Visual Descriptor (RVD), for deriving a compact and robust representation of image content which significantly advances state of the art and delivers world-class performance. In our approach, the local descriptors are assigned to multiple cluster centres with rank weights leading to a stable and reliable global image representation. Residual vectors are then computed in each cluster, normalized using a direction preserving normalization and aggregated based on the neighbourhood rank information. We then propose two extensions to the core RVD descriptor. The first one consists of de-correlating weighted residual vectors by applying cluster level PCA before aggregation. In the second extension, the weighted residual vectors are whitened in each cluster before aggregation, leading to a balanced energy distribution in each dimension and improved performance. Compressing floating point global signatures to binary codes improves storage requirements and matching speed for large scale image retrieval tasks. Our third contribution is to derive a compact and robust binary image signature from the core RVD representation. In addition, we propose a novel binary descriptors matching algorithm, PCAE with Weighted Hamming distance (PCAE+WH), to minimize the quantization loss associated with converting floating point vector to discrete binary codes. In the context of industry work on Compact descriptors for Visual Search (CDVS) and its standardization in MPEG (ISO), we propose a scalable RVD representation. The bitrate scalability is achieved by employing novel Cluster Selection and Bit Selection mechanisms which support interoperable binary RVD representations. Moreover, we propose a very efficient and effective score function based on weighted Hamming distance, to compute similarity between two binary representations. Our fourth contribution is to develop an image classification system based on RVD representation. We introduce an effective method to incorporate second order statistics in the original RVD framework.
41
Schuster, Christoph J. "No-wait Job-Shop Scheduling: Komplexität und Local Search". Gerhard-Mercator-Universitaet Duisburg, 2003. http://www.ub.uni-duisburg.de/ETD-db/theses/available/duett-04242003-131618/.
Pełny tekst źródłaStreszczenie:
This thesis deals with the structure of the no-wait job-shop problem as well as the derivation of fast approximation algorithms. These algorithms are based on a decomposition approach into a sequencing and a timetabling problem that was initially introduced by Macchiaroli et al. (1999). In the thesis the problems are derived from a mixed integer formulation of the original problem and proved to be NP-hard in the strong sense. After presenting a fast heuristic approach for the timetabling problem, the focus lies on the sequencing problem for which several local search algorithms are presented. The algorithms are tested on a wide variety of benchmark problems for the classical job-shop problem. Among the algorithms, the tabu search approach outperforms all other algorithms that can be found in the literature in objective value as well as computation time.
42
Hoffmann, Jörg. "Utilizing problem structure in planning : a local search approach /". Berlin [u.a.] : Springer, 2003. http://www.loc.gov/catdir/enhancements/fy0818/2003065658-d.html.
Pełny tekst źródła
43
Lindsey, Kathleen A. "Improving freight consolidation networks using IP-based local search". Diss., Georgia Institute of Technology, 2012. http://hdl.handle.net/1853/45786.
Pełny tekst źródłaStreszczenie:
This dissertation addresses problems arising in freight routing and scheduling where full truckload (FTL) and less-than-truckload (LTL) carriers are used to serve transportation needs. Each of the problems investigated in this dissertation tries to optimize/maximize consolidation to decrease system transportation costs by (1) carefully choosing the timing and path of freight and/or (2) introducing consolidation points. Approaches are proposed that enable effective planning and operation of freight routing and scheduling for large-scale transportation networks.
Chapter 2 presents solution approaches for a shipper pickup and delivery planning problem faced by many large retailers to move freight from suppliers to distribution centers. Each shipment is moved either direct via a LTL carrier or possibly consolidated with other shipments and moved by one or two FTL routes. When using a FTL carrier, the shipper takes advantage of contracted lane rates that establish prices per mile for a truck operated between two locations that are significantly less than the comparable LTL price for shipping a full truckload. Consolidated FTL routes may each visit multiple shipment origins (supplier locations) and/or destinations (distribution center locations). Additionally, FTL routes may move shipments through a single crossdock facility en route. The challenge in this planning problem is to exploit as much as possible negotiated truckload lane rates and to judiciously make use of routes through crossdock facilities to consolidate shipments. The primary contributions of this section are that (1) an interesting new problem variant is introduced to the field of transportation and logistics that is important in practice and (2) the solution approach demonstrates that exploiting knowledge of the problem and solution structure to cleverly select subsets of path variables for evaluation during each iteration of an integer programming based local search heuristic is effective on path-based routing models.
Chapter 3 evaluates how to route each customer shipment through a sequence of transfer terminals in a LTL carrier network. At each terminal stop, a shipment is unloaded from an inbound trailer and reloaded onto an outbound trailer. A load plan determines the specific sequence of terminal transfers to be used for freight moving between each origin and destination. The design of the load plan determines the linehaul transportation and handling costs required to serve customers. We develop an improved very large-scale neighborhood search heuristic for solving an integer programming model for load plan design. The main contributions of this section include (1) the investigation of the pros and cons of optimizing system-wide into a single destination versus optimizing freight for all destinations in a small region, and (2) a solution approach that can find load plans with costs 6 to 7\% lower than those used in practice, and can find 2.5 to 5\% additional cost savings using the same time budget when compared to an approach optimizing system-wide into a single destination.
Chapter 4 addresses a strategic planning problem that extends the load plan design problem to consider terminal roles. We investigate two-stage approaches that first identify the set of transfer terminals and then develop the corresponding load plan. Computational results compare the terminals chosen as transfer facilities from the proposed integer programming based local search method with a traditional hub location formulation and a simple facility location formulation to depict the benefits gained from modeling additional information. The key contributions of this section are (1) the introduction of a new hub location problem variant incorporating freight dispatch timing and trailer transportation cost characteristics found in the LTL trucking industry and (2) a solution approach utilizing IP-based local search that demonstrates the importance of incorporating freight dispatch timing.
Finally, Chapter 5 summarizes the main conclusions from this dissertation and discusses directions for further research.
44
Khudabukhsh, Ashiqur Rahman. "SATenstein : automatically building local search SAT solvers from components". Thesis, University of British Columbia, 2009. http://hdl.handle.net/2429/13852.
Pełny tekst źródłaStreszczenie:
Designing high-performance solvers for computationally hard problems is a difficult
and often time-consuming task. It is often the case that a new solver is created by
augmenting an existing algorithm with a mechanism found in a different algorithm
or by combining components from different algorithms.
In this work, we demonstrate that this task can be automated
in the context of stochastic local search (SLS) solvers for
the propositional satisfiability problem (SAT).
We first introduce a generalized, highly parameterized solver framework, dubbed SATenstein,
that includes components drawn from or inspired by existing high-performance SLS algorithms for SAT.
In SATenstein, we exposed several design elements in the form of parameters that control both the selection and the behavior
of components. We also exposed some parameters that were hard-coded into the implementations of the algorithms we studied.
By setting these parameters, SATenstein can be instantiated as a huge number of different solvers, including
many known high-performance solvers and trillions of solvers never studied before.
We used an automated algorithm configuration procedure to
find instantiations of SATenstein that perform well on several well-known, challenging
distributions of SAT instances.
Overall, we consistently obtained significant improvements over the previous
best-performing SLS algorithms, despite expending minimal manual effort.
45
Tompkins, David Andrew Douglas. "Dynamic local search for SAT : design, insights and analysis". Thesis, University of British Columbia, 2010. http://hdl.handle.net/2429/29538.
Pełny tekst źródłaStreszczenie:
In Boolean logic, a formula is satisfiable if a variable assignment exists that will make the formula equivalent to true, and the propositional satisfiability problem (SAT) is to determine if a given formula is satisfiable. SAT is one of the most fundamental problems in computer science, and since many relevant combinatorial problems can be encoded into SAT, it is of substantial theoretical and practical interest. A popular and successful approach to solving combinatorial problems such as SAT is Stochastic Local Search (SLS). In this dissertation we focus on SLS algorithms for SAT, which can find satisfying variable assignments effectively, but cannot determine if no satisfying variable assignment exists.
Our primary goal is to advance the state-of-the-art for SLS algorithms for SAT. We accomplish this goal explicitly by developing new SLS algorithms that outperform the existing algorithms on interesting benchmark problems, and implicitly by advancing the understanding of current algorithms and introducing tools for developing new algorithms. The prevalent theme of our work is Dynamic Local Search (DLS), where DLS algorithms use their search history to dynamically change their behaviour.
The cornerstone of this dissertation is UBCSAT, a software framework we developed for efficiently implementing and empirically evaluating SLS algorithms for SAT. We present the Scaling and Probabilistic Smoothing (SAPS) algorithm, which is amongst the state-of-the-art SLS algorithms for SAT. We provide an in-depth study of a class of DLS algorithms, analyze their performance and significantly advance the understanding of their behaviour. We also advance the understanding of the role of random decisions in SLS algorithms, by providing an empirical analysis on both the quality and quantity of random decisions. The capstone of this dissertation is a new conceptual model for representing and designing SLS algorithms for SAT. We introduce a new software design architecture that implements our model and is specifically designed to leverage recent tools to automate many of the tedious aspects of algorithm design. We demonstrate that by following our new algorithm design approach, we have achieved significant improvements over previous state-of-the-art SLS algorithms for SAT on encodings of software verification benchmark instances.
46
Björdal, Gustav. "The First Constraint-Based Local Search Backend for MiniZinc". Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-234847.
Pełny tekst źródłaStreszczenie:
MiniZinc is a modelling language used to model combinatorial optimisation and satisfaction problems, which can then be solved in a backend solver. There are many different backend solvers based on different technologies such as constraint programming, mathematical programming, or Boolean satisfiability solving. However, there is currently no constraint-based local search (CBLS) backend. This thesis gives an overview of the design of the first CBLS backend for MiniZinc. Experimental results show that for some relevant MiiZinc models, the CBLS backend is able to give high-quality results.
47
Knowles, Joshua D. "Local-search and hybrid evolutionary algorithms for Pareto optimization". Thesis, University of Reading, 2002. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.394429.
Pełny tekst źródła
48
Henderson, Darrall. "Assessing the Finite-Time Performance of Local Search Algorithms". Diss., Virginia Tech, 2001. http://hdl.handle.net/10919/26926.
Pełny tekst źródłaStreszczenie:
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.
49
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.
Pełny tekst źródła
50
Arthur, David. "Analyzing and improving local search : k-means and ICP /". May be available electronically:, 2009. http://proquest.umi.com/login?COPT=REJTPTU1MTUmSU5UPTAmVkVSPTI=&clientId=12498.
Pełny tekst źródła