Dissertations / Theses on the topic 'Search problems'
To see the other types of publications on this topic, follow the link: Search problems.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Search problems.'
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.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Lim, Wei Shi. "Problems in rendezvous search." Thesis, London School of Economics and Political Science (University of London), 1996. http://etheses.lse.ac.uk/2457/.
Full textAbstract:
Suppose n players are placed randomly on the real line at consecutive integers, and faced in random directions. Each player has maximum speed one and cannot see the others. The least expected time required for m(? n) of them to meet together at a single point, if all players have to use the same strategy, is the symmetric rendezvous value Rsm,n. If the players can use different strategies, the least expected meeting time is the asymmetric rendezvous value Ram,n. show that Ra3,2 is 47/48 and Rsn,n is asymptotic to n/2. If the minimax rendezvous time Mn is the minimum time required to ensure that all players can meet together at a single point regardless of their initial placement, we prove that M2 is 3, M3 is 4 and Mn is asymptotic to n/2. If players have to stick together upon meeting, we prove that three players require 5 time units to ensure a meeting. We also consider a problem proposed by S. Alpern (in his joint paper with A. Beck, Rendezvous Search on the Line with Bounded Resources, LSE Math Preprint Series, 92 (1995)) of how two players can optimally rendezvous while at the same time evading an enemy searcher. We model this rendezvous-evasion problem as a two-person, zero-sum game between the rendezvous team R (with agents R1, R2) and the searcher S and consider a version which is discrete in time and space. R1, R2 and S start at different locations among n identical locations and no two of them share a common labelling of the locations. Each player can move between any two locations in one time step (this includes the possibility of staying still) until at least two of them are at the same location together, at which time the game ends. If S is at this location, S (maximizer) wins and the payoff is 1; otherwise the team R (minimizer) wins and the payoff is 0. The value of the game vn is the probability that S wins under optimal play. We assume that R1 and R2 can jointly randomize their strategies and prove that V3 is 47/76 ? 0.61842 and v4 is at least 31/54 ? 0.57407. If all the players share a common notion of a directed cycle containing all the n locations (while still able to move between any two locations), the value of the game dn is ((1 - 2/n)n-1 + l)/2. In particular, d3 is less than v3 and d4 is less than v4. We also compare some of these results with those obtained when the rendezvous-evasion game is modelled as a multi-stage game with observed actions (W. S. Lim, Rendezvous-Evasion As a Multi-Stage Game With Observed Actions, LSE Math-CDAM Research Report Series, 96-05 (1996)). In all instances considered, we find that obligatory announcement of actions at the end of each step either does not affect the value of the game or helps the rendezvous team secure a lower value.
2
Black, Daniel Peter. "Search in weighted constraint satisfaction problems." Thesis, University of Leeds, 2003. http://etheses.whiterose.ac.uk/1309/.
Full textAbstract:
A wide variety of real-world optimisation problems can be modelled as Weighted Constraint Satisfaction Problems (WCSPs). Such problems are NP-hard and require an exponential amount of time to find the optimal solution. This thesis concentrates on the University Examination Timetabling Problem. A general abstraction of this problem has been used, as there are many institution-specific rules which could be incorporated into the problem. The use of this problem type allows WCSPs to be investigated using realistic problem data and allows a comparison with previously published results for the problem instances used. We have examined some existing variable ordering heuristics and defined new ones. An analysis methodology has been defined that allows the characteristics of good solutions to be identified. Different methods of identifying difficult to solve sub-problems and the use of such methods in variable ordering has been investigated. Incorporating the weight, or preference, associated with constraints into variable ordering heuristics has been found to be beneficial to finding solutions of low cost. The analysis methodology has been used to examine the relationship between solutions of different quality and the knowledge derived has been used to define, and justify, two new variable ordering heuristics. The usefulness of different value ordering heuristics has been examined. Value selection on the error incurred with past assignments and the use of look-ahead have been investigated. Variable ordering heuristics have been extended to try and exploit the advantages of such value ordering heuristics. The use of stochasticity with such orderings has been investigated and has led to a new class of hybrid value ordering heuristics being defined. Finally two hybrid search algorithms have been defined that attempt to concentrate search upon the sections of the problem instance which have the largest effect upon the overall quality of solutions found. Such methods are shown to be at least competitive with standard tree based search techniques.
3
Arbelaez, Rodriguez Alejandro. "Learning during search." Phd thesis, Université Paris Sud - Paris XI, 2011. http://tel.archives-ouvertes.fr/tel-00600523.
Full textAbstract:
La recherche autonome est un nouveau domaine d'intérêt de la programmation par contraintes, motivé par l'importance reconnue de l'utilisation de l'apprentissage automatique pour le problème de sélection de l'algorithme le plus approprié pour une instance donnée, avec une variété d'applications, par exemple: Planification, Configuration d'horaires, etc. En général, la recherche autonome a pour but le développement d'outils automatiques pour améliorer la performance d'algorithmes de recherche, e.g., trouver la meilleure configuration des paramètres pour un algorithme de résolution d'un problème combinatoire. Cette thèse présente l'étude de trois points de vue pour l'automatisation de la résolution de problèmes combinatoires; en particulier, les problèmes de satisfaction de contraintes, les problèmes d'optimisation de combinatoire, et les problèmes de satisfiabilité (SAT).Tout d'abord, nous présentons domFD, une nouvelle heuristique pour le choix de variable, dont l'objectif est de calculer une forme simplifiée de dépendance fonctionnelle, appelée dépendance-relaxée. Ces dépendances-relaxées sont utilisées pour guider l'algorithme de recherche à chaque point de décision.Ensuite, nous révisons la méthode traditionnelle pour construire un portefeuille d'algorithmes pour le problème de la prédiction de la structure des protéines. Nous proposons un nouveau paradigme de recherche-perpétuelle dont l'objectif est de permettre à l'utilisateur d'obtenir la meilleure performance de son moteur de résolution de contraintes. La recherche-perpétuelle utilise deux modes opératoires: le mode d'exploitation utilise le modèle en cours pour solutionner les instances de l'utilisateur; le mode d'exploration réutilise ces instances pour s'entraîner et améliorer la qualité d'un modèle d'heuristiques par le biais de l'apprentissage automatique. Cette deuxième phase est exécutée quand l'unité de calcul est disponible (idle-time). Finalement, la dernière partie de cette thèse considère l'ajout de la coopération au cours d'exécution d'algorithmes de recherche locale parallèle. De cette façon, on montre que si on partage la meilleure configuration de chaque algorithme dans un portefeuille parallèle, la performance globale peut être considérablement amélioré.
4
Korneffel, Torsten. "On combinatorial search problems which involve graphs." [S.l.] : [s.n.], 2007. http://deposit.ddb.de/cgi-bin/dokserv?idn=984062386.
Full text
5
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.
Full text
6
Marett, Richard Colin. "Neighbourhood search techniques for multi-objective combinatorial problems." Thesis, Lancaster University, 1995. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.296889.
Full text
7
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.
Full text
8
Lamprou, I. "Mobility problems in distributed search and combinatorial games." Thesis, University of Liverpool, 2018. http://livrepository.liverpool.ac.uk/3028459/.
Full textAbstract:
This thesis examines a collection of topics under the general notion of mobility of agents. We examine problems where a set of entities, perceived as robots or tokens, navigate in some given (discrete or continuous) environment to accomplish a goal. The problems we consider fall under two main research fields. First, Distributed Search where the agents cooperate to explore their environment or search for a specific target location within it. Second, Combinatorial Games, in the spirit of Pursuit-Evasion, where the agents are now divided into two groups with complementary objectives competing against each other. More specifically, we consider three distinct problems: disk evacuation, exploration of dynamic graphs and eternal domination. In Disk Evacuation, two robots with different speeds aim to discover an unknown exit lying on the boundary of a unit disk. For a wide range of speeds, we provide matching upper and lower bounds. In Dynamic Graph Exploration, we analyze the exploration time for a randomly-walking agent wishing to visit all the vertices of a stochastically-evolving graph. In Eternal Domination, we consider rectangular grid graphs and upper bound the amount of guard agents needed to perpetually defend the vertices against an attacker.
9
Lopez, Soto Claudia Orquidea. "Formulation space search for two-dimensional packing problems." Thesis, Brunel University, 2013. http://bura.brunel.ac.uk/handle/2438/7455.
Full textAbstract:
The two-dimension packing problem is concerned with the arrangement of items without overlaps inside a container. In particular we have considered the case when the items are circular objects, some of the general examples that can be found in the industry are related with packing, storing and transportation of circular objects. Although there are several approaches we want to investigate the use of formulation space search. Formulation space search is a fairly recent method that provides an easy way to escape from local optima for non-linear problems allowing to achieve better results. Despite the fact that it has been implemented to solve the packing problem with identical circles, we present an improved implementation of the formulation space search that gives better results for the case of identical and non-identical circles, also considering that they are packed inside different shaped containers, for which we provide the needed modifications for an appropriate implementation. The containers considered are: the unit circle, the unit square, two rectangles with different dimension (length 5, width 1 and length 10 width 1), a right-isosceles triangle, a semicircle and a right-circular quadrant. Results from the tests conducted shown several improvements over the best previously known for the case of identical circles inside three different containers: a right-isosceles triangle, a semicircle and a circular quadrant. In order to extend the scope of the formulation space search approach we used it to solve mixed-integer non-linear problems, in particular those with zero-one variables. Our findings suggest that our implementation provides a competitive way to solve these kind of problems.
10
Buljubasic, Mirsad. "Efficient local search for several combinatorial optimization problems." Thesis, Montpellier, 2015. http://www.theses.fr/2015MONTS010/document.
Full textAbstract:
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
11
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/.
Full textAbstract:
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.
12
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.
Full textAbstract:
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
13
Kampmeyer, Thomas. "Cyclic scheduling problems." Doctoral thesis, [S.l.] : [s.n.], 2006. http://deposit.ddb.de/cgi-bin/dokserv?idn=980566215.
Full text
14
Lincke, Thomas Robert. "Exploring the computational limits of large exhaustive search problems." [S.l. : s.n.], 2002. http://e-collection.ethbib.ethz.ch/show?type=diss&nr=14701.
Full text
15
Sze, Jeeu Fong. "Hybridisation search for a class of vehicle routing problems." Thesis, University of Kent, 2017. https://kar.kent.ac.uk/61328/.
Full textAbstract:
This thesis presents an investigation into the hybridisation of metaheuristic approaches to tackle the classical vehicle routing problem (VRP) and its adaptation to other useful and practical routing problems including the cumulative capacitated VRP (CCVRP) and the dynamic VRP (DVRP). Due to the limited success of the exact methods in handling large size instances, this research investigates the design and analysis of metaheuristic algorithms that can produce near optimal solutions within a reasonable amount of time to solve this class of routing problems. To achieve this goal, we propose an effective and novel hybridisation of variable neighbourhood search (VNS) and large neighbourhood search (LNS), leading to a powerful adaptive VNS (AVNS). Different from most of the literature for AVNS and adaptive LNS where learning is usually incorporated in the shaking step for the former and in the selection of the removal strategies for the latter, the adaptive aspect presented here is integrated in the local search of our AVNS. In short, a set of highly successful local searches is selected based on the intelligent selection mechanism which we introduced. In addition, this work also focuses on the development of some general enhancement-based techniques which include the design of neighbourhood reduction scheme, efficient data structures and a guided penalized objective function. The VRP is a hard combinatorial optimisation problem which was first established more than fifty years ago. Since then, this problem is extensively studied because of its high practicability in transportation logistics. Given the rising price of global oil, reducing the transportation cost provides a great impact in stabilizing the global economic system and adds a competitive advantage. The classical VRP focuses on this line of research. In addition, the classical VRP is used as the initial platform for our experiments which serves as the basis for tackling the other related routing problems mentioned above. The aim is to turn the successful implementations of the proposed algorithm by easily adapting and extending it to cater for the other two related routing problems namely the CCVRP and the DVRP. While the general assumption in most VRPs is profit-based such as the minimisation of the transportation cost, there are other objective functions such as to provide a good service to the customers. Such applications appear in the context of humanitarian relief where the main objective is to save lives or to alleviate suffering. This leads to the introduction of the CCVRP, which aims to minimise the sum of arrival times at customers. The literature for this particular problem is relatively scarce despite its practical importance. We therefore intend to investigate this new and interesting variant. In addition, during the emergency situation, there is often a limited time for saving lives. A good routing plan should also ensure fairness and equity to everyone including the last customer. Motivated by this idea, an alternative but closely related objective that minimises the last arrival time is also studied. We refer to this variant as the min-max CCVRP. In the traditional VRP, a route plan remains unchanged once it is identified. However in practice, several unforeseen events such as accidents or bad weather could occur at any point when the routes are executed, which cause traffic congestion and delay to the original planned routes. Therefore, it is important to re-optimise the routes by taking into consideration the real-time information, leading to the DVRP. The review of the DVRP literature shows that researchers have mainly focused on the customer requests as the dynamic aspect. Our research, however, concentrates more on the less popular but very practical aspect, namely the dynamic traffic information. Such unpredictable events have a great impact on the route plan and henceforth shall, in overview, not be ignored. The contributions of this thesis are fourfold: (i) To propose an effective hybridisation of the VNS and the LNS in addition to some new and powerful data structures and neighbourhood reduction scheme integrated in the algorithm, (ii) To adapt the AVNS algorithm for the CCVRP with extra features added and to present new best results, (iii) To demonstrate the flexibility and effectiveness of the AVNS algorithm to solve the min-max CCVRP and to explore the managerial insights for decision making when considering the min-sum and the min-max CCVRP objective functions, (iv) To adapt the AVNS algorithm as a re-optimisation procedure for the DVRP, where we introduce the concept of critical points which are used as the turning points for the vehicle.
16
Siala, Mohamed. "Search, propagation, and learning in sequencing and scheduling problems." Thesis, Toulouse, INSA, 2015. http://www.theses.fr/2015ISAT0008/document.
Full textAbstract:
Les problèmes de séquencement et d'ordonnancement forment une famille de problèmes combinatoires qui implique la programmation dans le temps d'un ensemble d'opérations soumises à des contraintes de capacités et de ressources. Nous contribuons dans cette thèse à la résolution de ces problèmes dans un contexte de satisfaction de contraintes et d'optimisation combinatoire. Nos propositions concernent trois aspects différents: comment choisir le prochain nœud à explorer (recherche)? comment réduire efficacement l'espace de recherche (propagation)? et que peut-on apprendre des échecs rencontrés lors de la recherche (apprentissage)? Nos contributions commencent par une étude approfondie des heuristiques de branchement pour le problème de séquencement de chaîne d'assemblage de voitures. Cette évaluation montre d'abord les paramètres clés de ce qui constitue une bonne heuristique pour ce problème. De plus, elle montre que la stratégie de branchement est aussi importante que la méthode de propagation. Deuxièmement, nous étudions les mécanismes de propagation pour une classe de contraintes de séquencement à travers la conception de plusieurs algorithmes de filtrage. En particulier, nous proposons un algorithme de filtrage complet pour un type de contrainte de séquence avec une complexité temporelle optimale dans le pire cas. Troisièmement, nous investiguons l'impact de l'apprentissage de clauses pour résoudre le problème de séquencement de véhicules à travers une nouvelle stratégie d'explication réduite pour le nouveau filtrage. L'évaluation expérimentale montre l'importance de l'apprentissage de clauses pour ce problème. Ensuite, nous proposons une alternative pour la génération retardée de variables booléennes pour encoder les domaines. Finalement, nous revisitons les algorithmes d'analyse de conflits pour résoudre les problèmes d'ordonnancement disjonctifs. En particulier, nous introduisons une nouvelle procédure d'analyse de conflits dédiée pour cette famille de problèmes. La nouvelle méthode diffère des algorithmes traditionnels par l'apprentissage de clauses portant uniquement sur les variables booléennes de disjonctions. Enfin, nous présentons les résultats d'une large étude expérimentale qui démontre l'impact de ces nouveaux mécanismes d'apprentissage. En particulier, la nouvelle méthode d'analyse de conflits a permis de découvrir de nouvelle bornes inférieures pour des instances largement étudiées de la littératureSequencing and scheduling involve the organization in time of operations subject to capacity and resource constraints. We propose in this dissertation several improvements to the constraint satisfaction and combinatorial optimization methods for solving these problems. These contributions concern three different aspects: how to choose the next node to explore (search)? how much, and how efficiently, one can reduce the search space (propagation)? and what can be learnt from previous failures (learning)? Our contributions start with an empirical study of search heuristics for the well known car-sequencing problem. This evaluation characterizes the key aspects of a good heuristic and shows that the search strategy is as important as the propagation aspect in this problem. Second, we carefully investigate the propagation aspect in a class of sequencing problems. In particular, we propose an algorithm for filtering a type of sequence constraints which worst case time complexity is lower than the best known upper bound, and indeed optimal. Third, we investigate the impact of clause learning for solving the car-sequencing problem. In particular, we propose reduced explanations for the new filtering. The experimental evaluation shows compelling evidence supporting the importance of clause learning for solving efficiently this problem. Next, we revisit the general approach of lazy generation for the Boolean variables encoding the domains. Our proposition avoids a classical redundancy issue without computational overhead. Finally, we investigate conflict analysis algorithms for solving disjunctive scheduling problems. In particular, we introduce a novel learning procedure tailored to this family of problems. The new conflict analysis differs from conventional methods by learning clauses whose size are not function of the scheduling horizon. Our comprehensive experimental study with traditional academic benchmarks demonstrates the impact of the novel learning scheme that we propose. In particular, we find new lower bounds for a well known scheduling benchmark
17
Pereira, André Grahl. "Solving moving-blocks problems." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2016. http://hdl.handle.net/10183/149574.
Full textAbstract:
Nesta tese, nós estudamos a classe de problemas de blocos-móveis. Um problema de blocos-móveis consiste em k blocos móveis dispostos em um labirinto em grade quadrangular onde há um bloco móvel adicional chamado de o homem, que é o único bloco que pode ser movido diretamente. Em particular, cada problema de blocos-móveis é definido pelo conjunto de movimentos disponíveis, pela descrição do objetivo e pelo o que acontece quando o homem tenta mover um bloco. Sokoban é o problema de blocos-móveis mais conhecido e pesquisado. Nós investigamos a complexidade computacional de problemas de blocos-móveis. Antes desta tese, a maior parte da literatura cientifica abordou problemas de blocos-móveis apenas com movimentos de EMPURRAR, na maioria dos casos provando que esses problemas são PSPACE-complete. Nós consideramos dois conjuntos de problemas: apenas movimentos de PUXAR, e movimentos de EMPURRAR e PUXAR combinados. Nossas reduções usam a Lógica de Restrições Não Determinística. Nós provamos que muitos problemas apenas com movimentos de PUXAR são PSPACE-complete. Além disso, nós provamos que o conjunto de problemas com movimentos de EMPURRAR e PUXAR é PSPACE-complete. A nossa contribuição nessa linha de pesquisa é aprimorar o conhecimento sobre o panorama da complexidade de problemas de blocos-móveis. Nosso principal objetivo com essa tese é resolver otimamente problemas de blocos-móveis com foco em Sokoban. Métodos baseados em busca heurística e heurísticas de abstrações como banco de dados de padrões são as abordagens mais efetivas para resolver otimamente esses problemas. Nós fazemos muitas contribuições nessa linha de pesquisa. Nós introduzimos novas funções heurísticas usando bancos de dados padrão com a ideia de estados objetivos intermediários. Propomos uma técnica baseada em bancos de dados padrão para detectar impasses. Propomos regras de desempate que exploram a estrutura do problema. Usando estas funções heurísticas e regras de desempate nós aumentamos o número de instâncias resolvidas de forma ótima de Sokoban e outros problemas em comparação com os métodos anteriores.In this thesis, we study the class of moving-blocks problems. A moving-blocks problem consists of k movable blocks placed on a grid-square maze where there is an additional movable block called the man, which is the only block that can be moved directly. In particular, each moving-blocks problem is defined by the set of moves available, by the goal description and by what happens when the man attempts to move a block. Sokoban is the best known and researched moving-blocks problem. We study moving-blocks problems in theory and practice. We investigate the computational complexity of problems of moving-blocks. Prior to this thesis, most of the scientific literature addressed moving-blocks problems with PUSH moves only, in most of the cases proving that these problems are PSPACE-complete. We consider two sets of problems: PULL moves only, and PUSH and PULL moves combined. Our reductions are from Nondeterministic Constraint Logic. We prove that many problems with PULL moves only are PSPACE-complete. In addition, we prove that the entire set of PUSH and PULL moves is PSPACE-complete. Our contribution in this research line is to enhance the knowledge on the complexity landscape of moving-blocks problems. Our main objective in this thesis is to optimally solve moving-blocks problems with a focus on Sokoban. Methods based on heuristic search and abstraction heuristics such as pattern databases are the most effective approaches to optimally solve these problems. We make many contributions in this research line. We introduce novel heuristic functions using pattern databases with the idea of intermediate goal states. We propose a technique based on pattern databases to detect deadlocks. We propose tie-breaking rules that exploit the structure of the problem. Using these heuristic functions and tie-breaking rules we increase the number of optimally solved instances of Sokoban and other problems compared to previous methods.
18
Robertson, Blair Lennon. "Direct Search Methods for Nonsmooth Problems using Global Optimization Techniques." Thesis, University of Canterbury. Mathematics and Statistics, 2010. http://hdl.handle.net/10092/5060.
Full textAbstract:
This thesis considers the practical problem of constrained and unconstrained local optimization. This subject has been well studied when the objective function f is assumed to smooth. However, nonsmooth problems occur naturally and frequently in practice. Here f is assumed to be nonsmooth or discontinuous without forcing smoothness assumptions near, or at, a potential solution. Various methods have been
presented by others to solve nonsmooth optimization problems, however only partial convergence results are possible for these methods.
In this thesis, an optimization method which use a series of local and localized global optimization phases is proposed. The local phase searches for a local minimum
and gives the methods numerical performance on parts of f which are smooth. The localized global phase exhaustively searches for points of descent in a neighborhood of cluster points. It is the localized global phase which provides strong theoretical convergence results on nonsmooth problems.
Algorithms are presented for solving bound constrained, unconstrained and constrained nonlinear nonsmooth optimization problems. These algorithms use direct search methods in the local phase as they can be applied directly to nonsmooth problems because gradients are not explicitly required. The localized global optimization phase uses a new partitioning random search algorithm to direct random sampling into promising subsets of ℝⁿ. The partition is formed using classification and regression trees (CART) from statistical pattern recognition. The CART partition defines desirable subsets where f is relatively low, based on previous sampling, from which further samples are drawn directly. For each algorithm, convergence to an essential local minimizer of f is demonstrated under mild conditions. That is, a point x* for which the set of all feasible points with lower f values has Lebesgue measure zero for all sufficiently small neighborhoods of x*. Stopping rules are derived for each algorithm giving practical convergence to estimates of essential local minimizers. Numerical results are presented on a range of nonsmooth test problems for 2 to 10 dimensions showing the methods are effective in practice.
19
Slater, Andrew, and andrew slater@csl anu edu au. "Investigations into Satisfiability Search." The Australian National University. Research School of Information Sciences and Engineering, 2003. http://thesis.anu.edu.au./public/adt-ANU20040310.103258.
Full textAbstract:
In this dissertation we investigate theoretical aspects of some practical approaches used
in solving and understanding search problems. We concentrate on the Satisfiability
problem, which is a strong representative from search problem domains. The work develops
general theoretical foundations to investigate some practical aspects of satisfiability
search. This results in a better understanding of the fundamental mechanics for search
algorithm construction and behaviour. A theory of choice or branching heuristics is
presented, accompanied by results showing a correspondence of both parameterisations and
performance when the method is compared to previous empirically motivated branching
techniques. The logical foundations of the backtracking mechanism are explored alongside formulations for reasoning in relevant logics which results in the development of a
malleable backtracking mechanism that subsumes other intelligent backtracking proof
construction techniques and allows the incorporation of proof rearrangement strategies.
Moreover, empirical tests show that relevant backtracking outperforms all other forms of
intelligent backtracking search tree construction methods. An investigation into
modelling and generating world problem instances justifies a modularised problem model proposal which is used experimentally to highlight the practicability of search algorithms
for the proposed model and related domains.
20
Imahori, Shinji. "Studies on Local Search Algorithms for Cutting and Packing Problems." 京都大学 (Kyoto University), 2004. http://hdl.handle.net/2433/147575.
Full text
21
Osman, Ibrahim Hassan. "Metastrategy : simulated annealing and tabu search for combinatorial optimization problems." Thesis, Imperial College London, 1991. http://hdl.handle.net/10044/1/7596.
Full text
22
Morioka, Tsuyoshi. "Classification of search problems and their definability in bounded arithmetic." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2001. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/MQ58775.pdf.
Full text
23
Kotthoff, Lars. "On algorithm selection, with an application to combinatorial search problems." Thesis, University of St Andrews, 2012. http://hdl.handle.net/10023/2841.
Full textAbstract:
The Algorithm Selection Problem is to select the most appropriate way for solving a problem given a choice of different ways. Some of the most prominent and successful applications come from Artificial Intelligence and in particular combinatorial search problems. Machine Learning has established itself as the de facto way of tackling the Algorithm Selection Problem. Yet even after a decade of intensive research, there are no established guidelines as to what kind of Machine Learning to use and how. This dissertation presents an overview of the field of Algorithm Selection and associated research and highlights the fundamental questions left open and problems facing practitioners. In a series of case studies, it underlines the difficulty of doing Algorithm Selection in practice and tackles issues related to this. The case studies apply Algorithm Selection techniques to new problem domains and show how to achieve significant performance improvements. Lazy learning in constraint solving and the implementation of the alldifferent constraint are the areas in which we improve on the performance of current state of the art systems. The case studies furthermore provide empirical evidence for the effectiveness of using the misclassification penalty as an input to Machine Learning. After having established the difficulty, we present an effective technique for reducing it. Machine Learning ensembles are a way of reducing the background knowledge and experimentation required from the researcher while increasing the robustness of the system. Ensembles do not only decrease the difficulty, but can also increase the performance of Algorithm Selection systems. They are used to much the same ends in Machine Learning itself. We finally tackle one of the great remaining challenges of Algorithm Selection -- which Machine Learning technique to use in practice. Through a large-scale empirical evaluation on diverse data taken from Algorithm Selection applications in the literature, we establish recommendations for Machine Learning algorithms that are likely to perform well in Algorithm Selection for combinatorial search problems. The recommendations are based on strong empirical evidence and additional statistical simulations. The research presented in this dissertation significantly reduces the knowledge threshold for researchers who want to perform Algorithm Selection in practice. It makes major contributions to the field of Algorithm Selection by investigating fundamental issues that have been largely ignored by the research community so far.
24
Benedettini, Stefano <1983>. "Metaheuristics for Search Problems in Genomics - New Algorithms and Applications." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2012. http://amsdottorato.unibo.it/4403/.
Full textAbstract:
In this thesis we made the first steps towards the systematic application of a methodology for automatically building formal models of complex biological systems. Such a methodology could be useful also to design artificial systems possessing desirable properties such as robustness and evolvability.
The approach we follow in this thesis is to manipulate formal models by means of adaptive search methods called metaheuristics.
In the first part of the thesis we develop state-of-the-art hybrid metaheuristic algorithms to tackle two important problems in genomics, namely, the Haplotype Inference by parsimony and the Founder Sequence Reconstruction Problem. We compare our algorithms with other effective techniques in the literature, we show strength and limitations of our approaches to various problem formulations and, finally, we propose further enhancements that could possibly improve the performance of our algorithms and widen their applicability.
In the second part, we concentrate on Boolean network (BN) models of gene regulatory networks (GRNs). We detail our automatic design methodology and apply it to four use cases which correspond to different design criteria and address some limitations of GRN modeling by BNs. Finally, we tackle the Density Classification Problem with the aim of showing the learning capabilities of BNs.
Experimental evaluation of this methodology shows its efficacy in producing network that meet our design criteria.
Our results, coherently to what has been found in other works, also suggest that networks manipulated by a search process exhibit a mixture of characteristics typical of different dynamical regimes.
25
Wassan, Niaz Ahmed. "Tabu search metaheuristics for a class of vehicle routing problems." Thesis, University of Kent, 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.263742.
Full text
26
Chiarandini, Marco. "Stochastic Local Search Methods for Highly Constrained Combinatorial Optimisation Problems." Phd thesis, [S.l. : s.n.], 2005. https://tuprints.ulb.tu-darmstadt.de/595/1/ChiarandiniPhD.pdf.
Full textAbstract:
Graph colouring is a combinatorial optimisation problem consisting in colouring the vertices of a graph such that no vertices connected by an edge receive the same colour. The minimal number of colours for which such a colouring exists is an intrinsic property of the graph and is called chromatic number. Many real life situations, such as the frequency assignment in mobile networks or the scheduling of courses at a university, can be modelled in this way. Colouring planar graphs, such as maps can be easy, and four colours suffice, but real life systems are much more complex. When modelled by graph colouring, they entail general graphs of large size and include more sophisticated constraints than those representable by simple unweighted edges. Stochastic Local Search (SLS) methods are approximate techniques for efficiently solving these complex combinatorial optimisation problems. They typically consist of construction algorithms, iterative improvement algorithms, and meta-components, better known as metaheuristics. The first two are strongly problem dependent and require the exploitation of problem-specific knowledge, while the last are more general concepts to guide the first two components. The instantiation of SLS algorithms arises from the combination of concrete algorithmic components. This task is complex due to the many possible combinations and the need of determining a certain number of parameters. Empirical tests become then necessary to take the correct decisions. The starting point of this work is the definition of the statistical methods that are appropriate for the analysis of SLS algorithms. We argue that the assumptions for the application of parametric tests are often violated and opt for two alternative methods: permutation and rank-based tests. Our work contributes to the development of permutation tests and to their introduction in the analysis of SLS algorithms. In addition, we transfer a graphical representation of results through simultaneous confidence intervals from the parametric to the non-parametric cases. This representation has the advantage of conveying in one single graph both descriptive and inferential statistics. The developed statistical methods serve for the analysis of SLS algorithms on the graph colouring problem and one of its many possible generalisations, the set T-colouring problem. Several SLS algorithms have been proposed in the literature for the graph colouring problem but no ``unbiased'' comparison has been attempted. A similar situation holds for the set T-colouring problem. In both cases, we design new algorithms, re-implement the most prominent methods, and finally compare them in a rigorous experimental analysis. As the final step, we study SLS algorithms for solving a university course timetabling problem. The design of algorithm components stems from the knowledge gained on the graph colouring problems but the assemblage and configuration of these components is carried out with a systematic methodology. The focus in this context was on the selection of one single algorithm to submit to an algorithm competition. The methodology is presented as an engineering process characterised by the interaction of SLS components design and empirical tests. We deem that this methodological approach is appropriate for the application of SLS methods to complex real life problems. The main results are the following: on the graph colouring problem, the simple Tabu Search with one-exchange neighbourhood remains a very competitive approach and the use of a very large scale neighbourhood is not profitable; on the set T-colouring problem, the best overall algorithm is an Adaptive Iterated Greedy also based on Tabu Search with one-exchange neighbourhood which, under certain circumstances, can be further improved by a restricted exact reassignment of colours; the use of an engineering methodology based on sequential testing is particularly suitable for the application of SLS methods, as it led us to devise the algorithm whose solutions for course timetabling ranked the best out of 24 feasible submissions at the International Timetabling Competition held in 2003.
27
Jha, Krishna Chandra. "Very large-scale neighborhood search heuristics for combinatorial optimization problems." [Gainesville, Fla.] : University of Florida, 2004. http://purl.fcla.edu/fcla/etd/UFE0004352.
Full text
28
Qiao, Wenbao. "GPU component-based neighborhood search for Euclidean graph minimization problems." Thesis, Bourgogne Franche-Comté, 2018. http://www.theses.fr/2018UBFCA020.
Full textAbstract:
Dans cette thèse, nous proposons des solutions parrallèles basées sur le systèmes actuel GPU (graphics processing unit) pour deux problèmes de minimisation de graphe Euclidien, à savoir le problème de forêt/arbre couvrant minimum Euclidien (EMSF / EMST) et le problème du voyageur commerce (TSP). Les solutions proposées résolvent également aussi le problème d'une paire bichromatique la plus proche (BCP), et suivent la technique de ``contrôle décentralisé, du parallélisme des données et des mémoires partagées par GPU".Nous proposons une technique de recherche dans le voisinage le plus proche de dimension K Euclidienne basée sur les approches classiques de NNS d’Elias qui divisent l’espace Euclidien en cellules congruentes et ne se chevauchant pas, où la taille des points de chaque cellule est délimitée. Nous proposons aussi une technique d'élagage pour obtenir le NNS à base de composants afin de trouver le point de sortie le plus proche de l'ensemble de points de requête de Q dans la complexité temporelle linéaire séquentielle lorsque les données sont uniformément réparties. Ces techniques sont utilisées conjointement avec deux GPU algorithmes proposés pour arbre traversement, à savoir la recherche en largeur bidirectionnelle GPU et la liste chaînée dynamique distribuée, afin d'adresser le BCP. Basé sur la solution BCP, un algorithme parallèle Divide and Conquer est implémenté pour construire EMSF et EMST totalement côté GPU. Le TSP est adressé avec différents algorithmes de recherche locaux parallèles 2-opt, dans lesquels nous proposons une méthodologie ``évaluation multiple K-opt, mouvements multiples K-opt" afin d’exécuter simultanément, sans interférence, des processus massifs 2-/3-opt mouvements qui se retrouvent globalement sur le même circuit TSP pour de nombreux bords. Cette méthodologie est expliquée en détail pour montrer comment nous obtenons un calcul haute performance à la fois du côté du GPU et CPU. Nous testons les solutions proposées et rapportons des résultats de comparaison expérimentale par rapport aux algorithmes de pointeIn this thesis, we propose parallel solutions based on current graphics processing unit (GPU) system for two Euclidean graph minimization problems, namely the Euclidean minimum spanning forest/tree (EMSF/EMST) and the travelling salesman problem (TSP). The proposed solutions also solve the bichromatic closest pair (BCP) problem, and follow technique of ``decentralized control, data parallelism, GPU shared memories".We propose a Euclidean K-dimensional nearest neighbourhood search (NNS) technique based on classical Elias' NNS approaches that divide the Euclidean space into congruent and non-overlapping cells where size of points in each cell is bounded. We propose a pruning technique to obtain component-based NNS to find a query point set Q's closest outgoing point within sequential linear time complexity when the data is uniformly distributed. These techniques are used together with two proposed GPU tree traversal algorithms, namely the GPU two-direction Breadth-first search and distributed dynamic linked list, to address the BCP. Based on the BCP solution, a divide and conquer parallel algorithm is implemented for building EMSF and EMST totally on GPU side. The TSP is addressed with different parallel 2-opt local search algorithms, in which we propose a ``multiple K-opt evaluation, multiple K-opt moves" methodology in order to simultaneously execute, without interference, massive 2-/3-opt moves that are globally found on the same TSP tour for many edges. This methodology is explained in details to show how we obtain high performance computing both on GPU and CPU side. We test the proposed solutions and report experimental comparison results against the state-of-the-art algorithms
29
Venter, Lieschen. "Metaheuristics for petrochemical blending problems." Thesis, Stellenbosch : University of Stellenbosch, 2010. http://hdl.handle.net/10019.1/4180.
Full textAbstract:
ENGLISH ABSTRACT: The main aim in blending problems is to determine the best blend of available ingredients to form a
certain quantity of product(s). This product should adhere to strict speci cations. In this study the
best blend means the least-cost blend of ingredients (input) required to meet a minimum level of product
(output) speci cations. The most prevalent tools to solve blending problems in the industry are by means
of spreadsheets, simulators and mathematical programming. While there may be considerable bene t in
using these types of tools to identify potential opportunities and infeasibilities, there is a potentially even
greater bene t in searching automitically for alternative solutions that are more economical and e cient.
Heuristics and metaheuristics are presented as useful alternative solution approaches.
In this thesis di erent metaheuristic techniques are developed and applied to three typical blending
problems of varied size taken from the petrochemical industry. a fourth instance of real life size is also
introduced. Heuristics are developed intuitively, while metaheuristics are adopted from the literature.
Random search techniques, such as blind random search and local random search, deliver fair results.
Within the class of genetic algorithms the best results for all three problems were obtained using ranked
tness assignment with tournament selection of individuals. Good results are also obtained by means of
tabu search approaches - even considering the continuous nature of these problems. A simulated annealing
approach also yielded fair results. A comparison of the results of the di erent approaches shows that
the tabu search technique delivers the best result with respect to solution quality and execution time for
all three the problems under consideration. Simulated annealing, however, delivers the best result with
respect to solution quality and execution time for the introduced real life size problem.AFRIKAANSE OPSOMMING: Die hoofdoelwit met die oplos van mengprobleme is om die beste mengsel van beskikbare bestandele te bepaal om 'n sekere hoeveelheid produk(te) te vervaardig. Die produk moet aan streng vereistes voldoen. Die beste kombinasie is die goedkoopste kombinasie van bestandele (toevoer) wat aan die minimum produkvereistes (afvoer) voldoen. Die algemeenste benaderings waarmee mengprobleme in die industrie opgelos word, is met behulp van sigblaaie, simulasies en wiskundige programmering. Hierdie metodes is baie nuttig om belowende oplossings of ontoelaatbaarhede te identi seer, maar dit kan potensieel meer voordelig wees om metodes te gebruik wat sistematies meer ekonomiese en e ektiewe oplossings vind. Heuristieke en metaheuristieke word as goeie alternatiewe oplossingsbenaderings aangebied. In hierdie tesis word verskillende metaheuristiekbenaderings toegepas op drie tipiese mengprobleme van verskillende groottes wat vanuit die petrochemiese industrie spruit. 'n Vierde geval met realistiese (regte wêreld) grootte word ook aangebied. Heuristieke word volgens intuïsie ontwikkel terwyl metaheuristieke aangepas word vanuit die literatuur. Lukrake soektegnieke soos die blinde lukrake soektegniek en die plaaslike lukrake soektegniek lewer redelike resultate. Binne die klas van genetiese algoritmes word die beste resultate gelewer wanneer die algoritme met 'n kombinasie van rangorde ksheidstoekenning en toernooiseleksie van individue geïmplimenteer word. Goeie resultate word ook verkry met behulp van tabusoektogbenaderings ten spyte van die kontinue aard van hierdie probleme. Gesimuleerde tempering lewer ook redelike resultate. 'n Vergelyking van die resultate van die verskillende tegnieke toon dat die tabusoektogtegniek die beste resultate met betrekking tot die kwaliteit van die oplossing sowel as uitvoertyd lewer. Gesimuleerde tempering lewer egter die beste resultate met betrekking tot die kwaliteit van die oplossing sowel as uitvoertyd vir die voorgestelde realistiese grootte probleem.
30
Umetani, Shunji. "Studies on Local Search Approaches to One Dimensional Cutting Stock Problems." 京都大学 (Kyoto University), 2003. http://hdl.handle.net/2433/68900.
Full text
31
Flötteröd, Gunnar. "A search acceleration method for optimization problems with transport simulation constraints." Elsevier, 2017. https://publish.fid-move.qucosa.de/id/qucosa%3A72819.
Full textAbstract:
This work contributes to the rapid approximation of solutions to optimization problems that are constrained by iteratively solved transport simulations. Given an objective function, a set of candidate decision variables and a black-box transport simulation that is solved by iteratively attaining a (deterministic or stochastic) equilibrium, the proposed method approximates the best decision variable out of the candidate set without having to run the transport simulation to convergence for every single candidate decision variable. This method can be inserted into a broad class of optimization algorithms or search heuristics that implement the following logic: (i) Create variations of a given, currently best decision variable, (ii) identify one out of these variations as the new currently best decision variable, and (iii) iterate steps (i) and (ii) until no further improvement can be attained. A probabilistic and an asymptotic performance bound are established and exploited in the formulation of an efficient heuristic that is tailored towards tight computational budgets. The efficiency of the method is substantiated through a comprehensive simulation study with a non-trivial road pricing problem. The method is compatible with a broad range of simulators and requires minimal parametrization.
32
Lawson, Mark Jon. "The Search for a Cost Matrix to Solve Rare-Class Biological Problems." Diss., Virginia Tech, 2009. http://hdl.handle.net/10919/29623.
Full textAbstract:
The rare-class data classification problem is a common one. It occurs when, in a dataset, the class of interest is far outweighed by other classes, thus making it difficult to classify using typical classification algorithms. These types of problems are found quite often in biological datasets, where data can be sparse and the class of interest has few representatives. A variety of solutions to this problem exist with varying degrees of success.
In this paper, we present our solution to the rare-class problem. This solution uses MetaCost, a cost-sensitive meta-classifier, that takes in a classification algorithm, training data, and a cost matrix. This cost matrix adjusts the learning of the classification algorithm to classify more of the rare-class data but is generally unknown for a given dataset and classifier.
Our method uses three different types of optimization techniques (greedy, simulated annealing, genetic algorithm) to determine this optimal cost matrix. In this paper we will show how this method can improve upon classification in a large amount of datasets, achieving better results along a variety of metrics. We will show how it can improve on different classification algorithms and do so better and more consistently than other rare-class learning techniques like oversampling and under-sampling. Overall our method is a robust and effective solution to the rare-class problem.Ph. D.
33
Merz, Peter. "Memetic algorithms for combinatorial optimization problems fitness landscapes and effective search strategies /." [S.l. : s.n.], 2000. http://deposit.ddb.de/cgi-bin/dokserv?idn=960860029.
Full text
34
Bin, Hussin Mohamed Saifullah. "Stochastic local search algorithms for single and bi-objective quadratic assignment problems." Doctoral thesis, Universite Libre de Bruxelles, 2015. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/222286.
Full textAbstract:
The study of Stochastic Local Search (SLS) algorithms is becoming more pivotal these days, due to their vast number of applications in decision making. Prior to the implementation of algorithmic knowledge for decision making, many decisions were made based on manual calculation, on the fly, or even based on guts feeling. Nowadays, such an approach is more rarely seen, especially when the decisions that need to be made are high-risk, cost intensive, or time-consuming. The increasingly often used SLS algorithms are one of the options available to assist the decision making process these days.The work discussed in this thesis concerns the study of SLS algorithms for solving the Quadratic Assignment Problem (QAP), a prominent combinatorial optimization problem, which until today is very hard to solve. Our interest is to study the behavior and performance of SLS algorithms for solving QAP instances of different characteristics, such as size, sparsity, and structure. In this study, we have also proposed new variants of SLS algorithms, inspired by existing, well-performing SLS algorithms for solving the QAP. The new variants of SLS algorithms are then further extended for solving the bi-objective QAP (bQAP).One main focus in this study is to see how the performance of algorithms scales with instance size. We have considered instances that are much larger than the ones usually used in the studies of algorithms for solving the QAP. By understanding how the algorithms perform when the instance size changes, we might be able to solve other problems effectively by considering the similarity in their characteristics to the ones of the QAP, or by seeing common trends in the relative performance of the various available SLS methods. For single objective QAP instances we found that the structure and size of instances do have a significant impact on the performance of SLS algorithms. For example, comparisons between Tabu Search (TS) and Simulated Annealing (SA) on instances with randomly generated matrices show that the overall performance of TS is better than SA, irrespective the size of instances considered. The results on a class of structured instances however show that TS performs well on small-sized instances, while on the larger ones, SA shows better results. In another experiment, Hierarchical Iterated Local Search (HILS) has shown very good results compared to several Iterated Local Search (ILS) variants. This experiment was done on a class of structured instances of size from 100 to 500. An extensive experiment on a class of structured instances of size 30 to 300 using tuned parameter settings shows that population based algorithms perform very well on most of the instance classes considered. SA however, shows very good performance especially on large-sized instances with low sparsity level. For the bQAP, the correlation between the flow matrices does have a strong effect that determines the performance of algorithms for solving them. Hybrid Simulated Annealing (HSA) clearly outperforms Hybrid Iterative Improvement (HII). When compared to Multi Objective Ant Colony Optimization (MOACO) and Strength Pareto Evolutionary Algorithm 2 (SPEA2), HSA shows very good performance, where HSA outperforms MOACO and SPEA2, especially on instances of large size, thus, offering a better scaling behavior. Based the results obtained in this study, it is possible to come up with a general idea on the suitability of SLS algorithms for solving instances with a certain characteristic. Given an unknown QAP instance, one can guess the most suitable algorithm for solving it depending on the type, size, and sparsity of the instance, while for a bQAP instance the most suitable algorithm can be guessed based on its size and correlation between the flow matrices.Doctorat en Sciences de l'ingénieur et technologie
info:eu-repo/semantics/nonPublished
35
Linhares, Alexandre. "Industrial pattern seguencing problems: some complexity results and new local search models." Instituto Nacional de Pesquisas Espaciais, 2001. http://urlib.net/sid.inpe.br/jeferson/2004/03.30.14.23.
Full textAbstract:
Nesta tese nós exploramos alguns problemas industriais originários de tarefas tão distintas quanto a programação de uma máquina flexível, o projeto de circuitos integrados VLSI e o sequenciamento de padrões de corte. Desta última tarefa provêm o problema de minimização de pilhas em aberto que é o principal foco do estudo. Alguns resultados de complexidade são apresentados para estes problemas estabelecendo-se uma conexão entre áreas que previamente não pareciam estar relacionadas. Novos modelos de busca local também são apresentados para lidar com estes problemas e sua eficácia é medida por comparações com resultados previamente estabelecidos na literatura. O primeiro método é derivado do algoritmo de simulated annealing trazendo conceitos da física estatística. O segunto método expande estas idéias, propondo um modelo coletivo baseado em dois princípios: (i) a exploração do espaço de soluções exibindo uma busca simultaneamente intensiva e distribuída e, (ii) a concentração da busca em proporção com a qualidade percebida em cada região. São também introduzidos novos métodos essenciais para dar suporte ao modelo, como políticas de coordenação (dos processos de busca) e métricas de distâncias.In this thesis we explore some industrial pattern sequencing problems arising in settings as distinct as the scheduling of flexible machines, the design of VLSI circuits, and the sequencing of cutting patterns. This latter setting presents us the minimization of open stacks problem, which is the main focus of our study. Some complexity results are presented for these sequencing problems, establishing a surprising connection between previously unrelated fields. New local search methods are also presented to deal with these problems, and their effectiveness is evaluated by comparisons with results previously obtained in the literature. The first method is derived from the simulated annealing algorithm, bringing new ideas from statistical physics. The second method advances these ideas, by proposing a collective search model based on two themes: (i) to explore the search space while simultaneously exhibiting search intensity and search diversity, and (ii) to explore the search space in proportion to the perceived quality of each region. Some preliminaries, given by coordination policies (to guide the search processes) and distance metrics, are introduced to support the model.
36
Hashimoto, Hideki. "Studies on local search-based approaches for vehicle routing and scheduling problems." 京都大学 (Kyoto University), 2008. http://hdl.handle.net/2433/93466.
Full text
37
Couetoux, Adrien. "Monte Carlo Tree Search for Continuous and Stochastic Sequential Decision Making Problems." Thesis, Paris 11, 2013. http://www.theses.fr/2013PA112192.
Full textAbstract:
Dans cette thèse, nous avons étudié les problèmes de décisions séquentielles, avec comme application la gestion de stocks d'énergie. Traditionnellement, ces problèmes sont résolus par programmation dynamique stochastique. Mais la grande dimension, et la non convexité du problème, amènent à faire des simplifications sur le modèle pour pouvoir faire fonctionner ces méthodes.Nous avons donc étudié une méthode alternative, qui ne requiert pas de simplifications du modèle: Monte Carlo Tree Search (MCTS). Nous avons commencé par étendre le MCTS classique (qui s’applique aux domaines finis et déterministes) aux domaines continus et stochastiques. Pour cela, nous avons utilisé la méthode de Double Progressive Widening (DPW), qui permet de gérer le ratio entre largeur et profondeur de l’arbre, à l’aide de deux méta paramètres. Nous avons aussi proposé une heuristique nommée Blind Value (BV) pour améliorer la recherche de nouvelles actions, en utilisant l’information donnée par les simulations passées. D’autre part, nous avons étendu l’heuristique RAVE aux domaines continus. Enfin, nous avons proposé deux nouvelles méthodes pour faire remonter l’information dans l’arbre, qui ont beaucoup amélioré la vitesse de convergence sur deux cas tests.Une part importante de notre travail a été de proposer une façon de mêler MCTS avec des heuristiques rapides pré-existantes. C’est une idée particulièrement intéressante dans le cas de la gestion d’énergie, car ces problèmes sont pour le moment résolus de manière approchée. Nous avons montré comment utiliser Direct Policy Search (DPS) pour rechercher une politique par défaut efficace, qui est ensuite utilisée à l’intérieur de MCTS. Les résultats expérimentaux sont très encourageants.Nous avons aussi appliqué MCTS à des processus markoviens partiellement observables (POMDP), avec comme exemple le jeu de démineur. Dans ce cas, les algorithmes actuels ne sont pas optimaux, et notre approche l’est, en transformant le POMDP en MDP, par un changement de vecteur d’état.Enfin, nous avons utilisé MCTS dans un cadre de méta-bandit, pour résoudre des problèmes d’investissement. Le choix d’investissement est fait par des algorithmes de bandits à bras multiples, tandis que l’évaluation de chaque bras est faite par MCTS.Une des conclusions importantes de ces travaux est que MCTS en continu a besoin de très peu d’hypothèses (uniquement un modèle génératif du problème), converge vers l’optimum, et peut facilement améliorer des méthodes suboptimales existantesIn this thesis, we study sequential decision making problems, with a focus on the unit commitment problem. Traditionally solved by dynamic programming methods, this problem is still a challenge, due to its high dimension and to the sacrifices made on the accuracy of the model to apply state of the art methods. We investigate on the applicability of Monte Carlo Tree Search methods for this problem, and other problems that are single player, stochastic and continuous sequential decision making problems. We started by extending the traditional finite state MCTS to continuous domains, with a method called Double Progressive Widening (DPW). This method relies on two hyper parameters, and determines the ratio between width and depth in the nodes of the tree. We developed a heuristic called Blind Value (BV) to improve the exploration of new actions, using the information from past simulations. We also extended the RAVE heuristic to continuous domain. Finally, we proposed two new ways of backing up information through the tree, that improved the convergence speed considerably on two test cases.An important part of our work was to propose a way to mix MCTS with existing powerful heuristics, with the application to energy management in mind. We did so by proposing a framework that allows to learn a good default policy by Direct Policy Search (DPS), and to include it in MCTS. The experimental results are very positive.To extend the reach of MCTS, we showed how it could be used to solve Partially Observable Markovian Decision Processes, with an application to game of Mine Sweeper, for which no consistent method had been proposed before.Finally, we used MCTS in a meta-bandit framework to solve energy investment problems: the investment decision was handled by classical bandit algorithms, while the evaluation of each investment was done by MCTS.The most important take away is that continuous MCTS has almost no assumption (besides the need for a generative model), is consistent, and can easily improve existing suboptimal solvers by using a method similar to what we proposed with DPS
38
Kübel, David J. F. [Verfasser]. "On some Geometric Search Problems : Algorithms, Complexity, Computability / David J. F. Kübel." Bonn : Universitäts- und Landesbibliothek Bonn, 2020. http://d-nb.info/1224270606/34.
Full text
39
Pham, Duc Nghia, and n/a. "Modelling and Exploiting Structures in Solving Propositional Satisfiability Problems." Griffith University. Institute for Integrated and Intelligent Systems, 2006. http://www4.gu.edu.au:8080/adt-root/public/adt-QGU20070216.143447.
Full textAbstract:
Recent research has shown that it is often preferable to encode real-world problems as propositional satisfiability (SAT) problems and then solve using a general purpose SAT solver. However, much of the valuable information and structure of these realistic problems is flattened out and hidden inside the corresponding Conjunctive Normal Form (CNF) encodings of the SAT domain. Recently, systematic SAT solvers have been progressively improved and are now able to solve many highly structured practical problems containing millions of clauses. In contrast, state-of-the-art Stochastic Local Search (SLS) solvers still have difficulty in solving structured problems, apparently because they are unable to exploit hidden structure as well as the systematic solvers. In this thesis, we study and evaluate different ways to effectively recognise, model and efficiently exploit useful structures hidden in realistic problems. A summary of the main contributions is as follows: 1. We first investigate an off-line processing phase that applies resolution-based pre-processors to input formulas before running SLS solvers on these problems. We report an extensive empirical examination of the impact of SAT pre-processing on the performance of contemporary SLS techniques. It emerges that while all the solvers examined do indeed benefit from pre-processing, the effects of different pre-processors are far from uniform across solvers and across problems. Our results suggest that SLS solvers need to be equipped with multiple pre-processors if they are ever to match the performance of systematic solvers on highly structured problems. [Part of this study was published at the AAAI-05 conference]. 2. We then look at potential approaches to bridging the gap between SAT and constraint satisfaction problem (CSP) formalisms. One approach has been to develop a many-valued SAT formalism (MV-SAT) as an intermediate paradigm between SAT and CSP, and then to translate existing highly efficient SAT solvers to the MV-SAT domain. In this study, we follow a different route, developing SAT solvers that can automatically recognise CSP structure hidden in SAT encodings. This allows us to look more closely at how constraint weighting can be implemented in the SAT and CSP domains. Our experimental results show that a SAT-based mechanism to handle weights, together with a CSP-based method to instantiate variables, is superior to other combinations of SAT and CSP-based approaches. In addition, SLS solvers based on this many-valued weighting approach outperform other existing approaches to handle many-valued CSP structures. [Part of this study was published at the AAAI-05 conference]. 3. Finally, we propose and evaluate six different schemes to encode temporal reasoning problems, in particular the Interval Algebra (IA) networks, into SAT CNF formulas. We then empirically examine the performance of local search as well as systematic solvers on the new temporal SAT representations, in comparison with solvers that operate on native IA representations. Our empirical results show that zChaff (a state-of-the-art complete SAT solver) together with the best IA-to-SAT encoding scheme, can solve temporal problems significantly faster than existing IA solvers working on the equivalent native IA networks. [Part of this study was published at the CP-05 workshop].
40
Zubaran, Tadeu Knewitz. "A study onshop sceduling problems." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2018. http://hdl.handle.net/10183/174953.
Full textAbstract:
Escalonamento de processos é um tipo de problema de otimização combinatória no qual devemos alocar máquinas à tarefas por períodos específicos de tempo. A literatura contém diversos estudos propondo técnicas para resolver modelos de escalonamento de processos como o job shop e o open shop. Esses modelos permitem que os passos no processo produtivo sejam ou completamente ordenados ou sem ordenação alguma. Com o aumento da complexidade das aplicações industriais no encontramos, mais recentemente, diversos trabalhos que propõe problemas de escalonamento de processos mais gerais para modelar mais precisamente os processos produtivos. O mixed shop, group shop e partial shop são exemplos de tais modelos. Nesse trabalho nós propomos uma busca tabu iterada para o partial shop, que é um modelo geral que inclui diversos modelos mais restritivos. Os componentes novos mais importantes da técnica são o gerador de solução inicial, a vizinhança e o limite inferior para a vizinhança. Em experimentos computacionais nós conseguimos demonstrar que a heurística genérica e única é capaz de competir, e as vezes superar, as técnicas de estado de arte desenvolvidas especificamente para partial, open, mixed e group shop. Algumas vezes uma máquina é o gargalo de um processo produtivo, e é replicada. Na literatura o caso das máquinas paralelas foi incluído em diversas extensões de problemas de escalonamento de processos. Nessa tese nós também propomos uma técnica para escalonar as máquinas paralelas, sem incluí-las explicitamente na representação do problema. Nós usamos técnicas gerais para os casos sem máquinas paralelas para produzir uma busca heurística tabu rápida, e estado da arte, para o caso do job shop com máquinas paralelas.Shop scheduling is a combinatorial optimization type of problem in which we must allocate machines to jobs for specific periods time. A set of constraints defines which schedules are valid, and we must select one that minimizes or maximizes an objective function. In this work we use the makespan, which is the time the last job finishes. The literature contains several studies proposing techniques to solve shop problems such as the job shop and open shop. These problems allow the steps of the production processes to be either fully ordered or not ordered at all. With increasing complexity and size of industrial applications we find, more recently, several works which propose more general shop problems to model the production processes more accurately. The mixed shop, group shop and partial shop are examples of such problems In this work we propose an iterated tabu search for the partial shop, which is a general problem and includes several other more restrictive shop problems. The most important novel components of the solver are the initial solution generator, the neighbourhood, and the lower bound for the neighbourhood. In computational experiments we were able to show that the general partial shop solver is able to compete with, and sometimes surpass, the state-of-the-art solvers developed specifically for the partial, open, mixed and group shops. Sometimes a machine is a bottleneck in the production process, and is replicated. In the literature the parallel machines case has being included in several extensions of shop problems. In this thesis we also propose a technique to schedule the parallel machines heuristically, without including them explicitly in the representation of the problem. We use general techniques for the non-parallel machine cases to produce a fast tabu search heuristic results for the job shop with parallel machines.
41
McPeake, John Warren Robert. "Owner occupier search behaviour in the Belfast Urban Area : an investigation of residential search in a segregated housing market." Thesis, University of Glasgow, 1995. http://theses.gla.ac.uk/5504/.
Full textAbstract:
Racial and ethnic residential segregation are persistent features of urban areas throughout the world. This study focuses on the search behaviour of owner occupier households in the Belfast Urban Area, an area segregated on the basis of religion. The study was initiated under the premise that household search behaviour was important in the context of a spatially segregated housing market, and is a research area that has been neglected at least as far as Belfast is concerned. The overall aim of the research is to develop a better understanding of how owner occupied households made their housing choices against such a segregated background. For many years, the literature has recognised the two-way relationship between mobility and urban form and, at the same time, it has acknowledged that residential decision making is inherently conservative in nature. The US evidence on racial search and mobility behaviour indicates that such behaviour is supportive of the existing patterns of separate living. This observation set up the basic proposition for this study; namely, Catholic searchers in the BUA will exhibit search behaviour similar to that of black households in comparably segregated urban areas in the United States. The literature on racial differences in search suggests that black household search is less efficient and more costly than that of whites. In particular, blacks are seen to search for longer than whites, during which time they view a similar number or fewer dwellings, but over a more restricted range of areas. In terms of information use, the evidence is that black households make extensive use of existing information channels. In particular, informal sources such as friends and relatives, which serve to reinforce the localised nature of search, and estate agents are important sources of information for minority searchers. The evidence is also clear that black households tend to end up in black areas.
42
Henry, Obit Joe. "Developing novel meta-heuristic, hyper-heuristic and cooperative search for course timetabling problems." Thesis, University of Nottingham, 2010. http://eprints.nottingham.ac.uk/13581/.
Full textAbstract:
The research presented in this PhD thesis focuses on the problem of university course timetabling, and examines the various ways in which metaheuristics, hyperheuristics and cooperative heuristic search techniques might be applied to this sort of problem. The university course timetabling problem is an NP-hard and also highly constrained combinatorial problem. Various techniques have been developed in the literature to tackle this problem. The research work presented in this thesis approaches this problem in two stages. For the first stage, the construction of initial solutions or timetables, we propose four hybrid heuristics that combine graph colouring techniques with a well-known local search method, tabu search, to generate initial feasible solutions. Then, in the second stage of the solution process, we explore different methods to improve upon the initial solutions. We investigate techniques such as single-solution metaheuristics, evolutionary algorithms, hyper-heuristics with reinforcement learning, cooperative low-level heuristics and cooperative hyper-heuristics. In the experiments throughout this thesis, we mainly use a popular set of benchmark instances of the university course timetabling problem, proposed by Socha et al. [152], to assess the performance of the methods proposed in this thesis. Then, this research work proposes algorithms for each of the two stages, construction of initial solutions and solution improvement, and analyses the proposed methods in detail. For the first stage, we examine the performance of the hybrid heuristics on constructing feasible solutions. In our analysis of these algorithms we discovered that these hybrid approaches are capable of generating good quality feasible solutions in reasonable computation time for the 11 benchmark instances of Socha et al. [152]. Just for this first stage, we conducted a second set of experiments, testing the proposed hybrid heuristics on another set of benchmark instances corresponding to the international timetabling competition 2002 [91J]. Our hybrid construction heuristics were also capable of producing feasible solutions for the 20 instances of the competition in reasonable computation time. It should be noted however, that most of the research presented here was focused on the 11 problem instances of Socha et al. [152]. For the second stage, we propose new metaheuristic algorithms and cooperative hyper-heuristics, namely a non-linear great deluge algorithm, an evolutionary nonlinear great deluge algorithm (with a number of new specialised evolutionary operators), a hyper-heuristic with a learning mechanism approach, an asynchronous cooperative low-level heuristic and an asynchronous cooperative hyper-heuristic. These two last algorithms were inspired by the particle swarm optimisation technique. Detailed analyses of the proposed algorithms are presented and their relative benefits discussed. Finally, we give our suggestions as to how our best performing algorithms might be modified in order to deal with a wide range of problem domains including more real-world constraints. We also discuss the drawbacks of our algorithms in the final section of this thesis.
43
Madabushi, Ananth R. "Lagrangian Relaxation / Dual Approaches For Solving Large-Scale Linear Programming Problems." Thesis, Virginia Tech, 1997. http://hdl.handle.net/10919/36833.
Full textAbstract:
This research effort focuses on large-scale linear programming problems that arise in the context of solving various problems such as discrete linear or polynomial, and continuous nonlinear, nonconvex programming problems, using linearization and branch-and-cut algorithms for the discrete case, and using polyhedral outer-approximation methods for the continuous case. These problems arise in various applications in production planning, location-allocation, game theory, economics, and many engineering and systems design problems. During the solution process of discrete or continuous nonconvex problems using polyhedral approaches, one has to contend with repeatedly solving large-scale linear programming(LP) relaxations. Thus, it becomes imperative to employ an efficient method in solving these problems. It has been amply demonstrated that solving LP relaxations using a simplex-based algorithm, or even an interior-point type of procedure, can be inadequately slow ( especially in the presence of complicating constraints, dense coefficient matrices, and ill-conditioning ) in comparison with a Lagrangian Relaxation approach. With this motivation, we present a practical primal-dual subgradient algorithm that incorporates a dual ascent, a primal recovery, and a penalty function approach to recover a near optimal and feasible pair of primal and dual solutions.
The proposed primal-dual approach is comprised of three stages. Stage I deals with solving the Lagrangian dual problem by using various subgradient deflection strategies such as the Modified Gradient Technique (MGT), the Average Direction Strategy (ADS), and a new direction strategy called the Modified Average Direction Strategy (M-ADS). In the latter, the deflection parameter is determined based on the process of projecting the unknown optimal direction onto the space spanned by the current subgradient direction and the previous direction. This projected direction approximates the desired optimal direction as closely as possible using the conjugate subgradient concept. The step-length rules implemented in this regard are the Quadratic Fit Line Search Method and a new line search method called the Directional Derivative Line Search Method in which we start with a prescribed step-length and then ascertain whether to increase or decrease the step-length value based on the right-hand and left-hand derivative information available at each iteration. In the second stage of the algorithm (Stage II), a sequence of updated primal solutions is generated using some convex combinations of the Lagrangian subproblem solutions. Alternatively, a starting primal optimal solution can be obtained using the complementary slackness conditions. Depending on the extent of feasibility and optimality attained, Stage III applies a penalty function method to improve the obtained primal solution toward a near feasible and optimal solution.
We present computational experience using a set of randomly generated, structured, linear programming problems of the type that might typically arise in the context of discrete optimization.Master of Science
44
Kypta, Tomáš. "Search Strategies for Scheduling Problems." Master's thesis, 2012. http://www.nusl.cz/ntk/nusl-310936.
Full textAbstract:
In the present work I compare the search strategies for solving scheduling problems from the view of constraint programming. The thesis is focused on scheduling problems containing alternative activities. An analysis of previously published various ways of modelling the problems is provided, next description and experimental comparison of search strategies targetting these models is provided. The influence of strategies on the speed of the solver is studied primarily. As a sideeffect the work studies the ways how Choco solver, which was utililized for implementation of the experiments, can be used to solve the scheduling problems with alternative activities.
45
Chang, Yu-Ting, and 張瑜庭. "Harmony Search for Portfolio Optimization Problems." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/30581158851267741042.
Full textAbstract:
碩士元智大學
工業工程與管理學系
99
This study proposes a harmony search algorithm for solving constrained portfolio optimization problems with the objective of investment return maximization and risk minimization according to Chang et al. (2000) which is based on the mean-variance model of Markowitz (1952). This study develops a hybrid encoding to deal with both continuous and combinatorial properties of the problem. The proposed algorithms employ harmony memory consideration, pitch adjustment and random search to achieve the balance between exploitation and exploration and generate high-quality new solutions effectively. The performance of the eleven proposed HS variations is tested using five global stock market indexes provided by the OR-Library from March 1992 to September 1997. The results of proposed HS algorithms are also compared with SA, TS and VNS algorithms in the literature. HS outperforms all the competing algorithms in all five test data sets, and proves to be a promising alterative in solving portfolio optimization problems.
46
Lo, Min-Hua, and 羅敏華. "Variable Neighborhood Search for Combinatorial Problems." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/99556577519317188892.
Full textAbstract:
博士元智大學
工業工程與管理學系
98
Variable neighborhood search (VNS) algorithm is one of the newly developed meta-heuristic methods. VNS and its variations have been successfully applied to many combinatorial optimization problems. Redundancy allocation problem (RAP) and team orienteering problem (TOP) are two NP-hard problems and play very important roles in real-world application. RAP has wide applications in nuclear industry, aeronautic engineering, astronautic engineering, military application and medical engineering, etc. and TOP can be considered the representative problem in logistics field. Therefore, RAP and TOP are chosen to test the robustness of VNS in this study. This dissertation is divided into three parts: First, a VNS algorithm embedded with a penalty function is proposed to solve single-objective RAPs. Two types of RAP - multi-stage and series-parallel systems are considered. Eight sets of benchmark which contains 152 instances are tested. Second, the MOVNS-RAP algorithm is developed to solve the multi-objective redundancy allocation problems. Three test instances are tested. Lastly, two VNS algorithm – VNS-TOP I and VNS-TOP II are proposed to solve orienteering problems and team orienteering problems. The concept of VNS-TOP algorithms is to extend the search space so the algorithm can solve the single-objective optimization problems under different constraint levels simultaneously. Six sets of OP benchmarks including 107 instances and seven sets of TOP benchmark including 353 instances are tested. The computational results of VNS on the three types of problems above show that VNS algorithms are very promising and competitive in both solution quality and computational expense.
47
Venugopal, Mamatha. "A Stochastic Search Approach to Inverse Problems." Thesis, 2016. http://hdl.handle.net/2005/3042.
Full textAbstract:
The focus of the thesis is on the development of a few stochastic search schemes for inverse problems and their applications in medical imaging. After the introduction in Chapter 1 that motivates and puts in perspective the work done in later chapters, the main body of the thesis may be viewed as composed of two parts: while the first part concerns the development of stochastic search algorithms for inverse problems (Chapters 2 and 3), the second part elucidates on the applicability of search schemes to inverse problems of interest in tomographic imaging (Chapters 4 and 5). The chapter-wise contributions of the thesis are summarized below.
Chapter 2 proposes a Monte Carlo stochastic filtering algorithm for the recursive estimation of diffusive processes in linear/nonlinear dynamical systems that modulate the instantaneous rates of Poisson measurements. The same scheme is applicable when the set of partial and noisy measurements are of a diffusive nature. A key aspect of our development here is the filter-update scheme, derived from an ensemble approximation of the time-discretized nonlinear Kushner Stratonovich equation, that is modified to account for Poisson-type measurements. Specifically, the additive update through a gain-like correction term, empirically approximated from the innovation integral in the filtering equation, eliminates the problem of particle collapse encountered in many conventional particle filters that adopt weight-based updates. Through a few numerical demonstrations, the versatility of the proposed filter is brought forth, first with application to filtering problems with diffusive or Poisson-type measurements and then to an automatic control problem wherein the exterminations of the associated cost functional is achieved simply by an appropriate redefinition of the innovation process.
The aim of one of the numerical examples in Chapter 2 is to minimize the structural response of a duffing oscillator under external forcing. We pose this problem of active control within a filtering framework wherein the goal is to estimate the control force that minimizes an appropriately chosen performance index. We employ the proposed filtering algorithm to estimate the control force and the oscillator displacements and velocities that are minimized as a result of the application of the control force. While Fig. 1 shows the time histories of the uncontrolled and controlled displacements and velocities of the oscillator, a plot of the estimated control force against the external force applied is given in Fig. 2.
(a) (b)
Fig. 1. A plot of the time histories of the uncontrolled and controlled (a) displacements and (b) velocities.
Fig. 2. A plot of the time histories of the external force and the estimated control force
Stochastic filtering, despite its numerous applications, amounts only to a directed search and is best suited for inverse problems and optimization problems with unimodal solutions. In view of general optimization problems involving multimodal objective functions with a priori unknown optima, filtering, similar to a regularized Gauss-Newton (GN) method, may only serve as a local (or quasi-local) search. In Chapter 3, therefore, we propose a stochastic search (SS) scheme that whilst maintaining the basic structure of a filtered martingale problem, also incorporates randomization techniques such as scrambling and blending, which are meant to aid in avoiding the so-called local traps. The key contribution of this chapter is the introduction of yet another technique, termed as the state space splitting (3S) which is a paradigm based on the principle of divide-and-conquer. The 3S technique, incorporated within the optimization scheme, offers a better assimilation of measurements and is found to outperform filtering in the context of quantitative photoacoustic tomography (PAT) to recover the optical absorption field from sparsely available PAT data using a bare minimum ensemble. Other than that, the proposed scheme is numerically shown to be better than or at least as good as CMA-ES (covariance matrix adaptation evolution strategies), one of the best performing optimization schemes in minimizing a set of benchmark functions.
Table 1 gives the comparative performance of the proposed scheme and CMA-ES in minimizing a set of 40-dimensional functions (F1-F20), all of which have their global minimum at 0, using an ensemble size of 20. Here, 10 5 is the tolerance limit to be attained for the objective function value and MAX is the maximum number of iterations permissible to the optimization scheme to arrive at the global minimum.
Table 1. Performance of the SS scheme and
Chapter 4 gathers numerical and experimental evidence to support our conjecture in the previous chapters that even a quasi-local search (afforded, for instance, by the filtered martingale problem) is generally superior to a regularized GN method in solving inverse problems. Specifically, in this chapter, we solve the inverse problems of ultrasound modulated optical tomography (UMOT) and diffraction tomography (DT). In UMOT, we perform a spatially resolved recovery of the mean-squared displacements, p r of the scattering centres in a diffusive object by measuring the modulation depth in the decaying autocorrelation of the incident coherent light. This modulation is induced by the input ultrasound focussed to a specific region referred to as the region of interest (ROI) in the object. Since the ultrasound-induced displacements are a measure of the material stiffness, in principle, UMOT can be applied for the early diagnosis of cancer in soft tissues. In DT, on the other hand, we recover the real refractive index distribution, n r of an optical fiber from experimentally acquired transmitted intensity of light traversing through it. In both cases, the filtering step encoded within the optimization scheme recovers superior reconstruction images vis-à-vis the GN method in terms of quantitative accuracies.
Fig. 3 gives a comparative cross-sectional plot through the centre of the reference and reconstructed p r images in UMOT when the ROI is at the centre of the object. Here, the anomaly is presented as an increase in the displacements and is at the centre of the ROI.
Fig. 4 shows the comparative cross-sectional plot of the reference and reconstructed refractive index distributions, n r of the optical fiber in DT.
Fig. 3. Cross-sectional plot through the center of the reference and reconstructed p r images.
Fig. 4. Cross-sectional plot through the center of the reference and reconstructed n r distributions.
In Chapter 5, the SS scheme is applied to our main application, viz. photoacoustic tomography (PAT) for the recovery of the absorbed energy map, the optical absorption coefficient and the chromophore concentrations in soft tissues. Nevertheless, the main contribution of this chapter is to provide a single-step method for the recovery of the optical absorption field from both simulated and experimental time-domain PAT data. A single-step direct recovery is shown to yield better reconstruction than the generally adopted two-step method for quantitative PAT. Such a quantitative reconstruction maybe converted to a functional image through a linear map. Alternatively, one could also perform a one-step recovery of the chromophore concentrations from the boundary pressure, as shown using simulated data in this chapter. Being a Monte Carlo scheme, the SS scheme is highly parallelizable and the availability of such a machine-ready inversion scheme should finally enable PAT to emerge as a clinical tool in medical diagnostics.
Given below in Fig. 5 is a comparison of the optical absorption map of the Shepp-Logan phantom with the reconstruction obtained as a result of a direct (1-step) recovery.
Fig. 5. The (a) exact and (b) reconstructed optical absorption maps of the Shepp-Logan phantom. The x- and y-axes are in m and the colormap is in mm-1.
Chapter 6 concludes the work with a brief summary of the results obtained and suggestions for future exploration of some of the schemes and applications described in this thesis.
48
Lin, Chun-Hao, and 林俊豪. "Tabu Search for Discrete Simulation Optimization Problems." Thesis, 2005. http://ndltd.ncl.edu.tw/handle/yw7j89.
Full textAbstract:
碩士中原大學
工業工程研究所
93
The optimization problems can be categorized into two types: continuous and discrete, base on the decision variables. We also discuss the simulation and numerical analysis. Now we consider mainly discrete simulation optimization problems. The simulation optimization problems, finding the optimal point using only estimates of the function values. Such problems occur in system design with simulation applications. The decision variables are controllable system parameters and objective function is the associate system cost to be minimized. Due to the complexity in the simulation system, the objective function values can not be computed numerically but can be estimated through simulation experiments. We propose the TSDRA algorithm for solving discrete simulation optimization problems. This algorithm combines the Dependent Retrospective Approximation (DRA) procedure and Tabu Search (TS). The main idea of DRA algorithm is to iteratively solve a sequence of sample-path problems with increasing sample size. Each sample-path problem is then solved by the heuristic tabu search (TS). We consider two performance indexes in this research: first is sensitivity analysis of the algorithm parameters, second is comparison of TSDRA to six existing algorithms --- MSSA, SRS, MSSR, MSSC, GADRA and SADRA---. Both studies use MSEf and CP as algorithm performance measures, where MSEf is the mean square error in the function value and CP is the number of convergent paths out of replications (a convergent path is one that terminates with the true optimal point). Algorithms with small MSEf and big CP are preferred. The simulation results also show that M/M/1 system is one dimension. In tabu search, long as search it from the large iterations, can reach best solution. Uni-model system is two dimensions, so that it will produce the cycle. TSDRA will get small MSEf than SADRA and GADRA, But SADRA ( ) get a good CP value.
49
Lai, Lien-Chi, and 賴鍊奇. "Adaptive Search Regions in Derivative Free Optimization Problems." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/78861635237905202838.
Full textAbstract:
碩士國立高雄大學
應用數學系碩士班
96
This article attempts to find all local minima in an experimental region of interest. The optimization problems of interest are characterized as follows. First, the function is either complicated or defined implicitly. Second, the computational cost associated with simulating the function values is very high. We develop a new framework suited not only to accurate location of a given minimum, but also to finding multiple local minima automatically. In this aim, the algorithm first determines an approximate surrogate surface. Next, the algorithm shrinks the search region, refines the grids and then uses a specific form of retracing over the experimental region. The algorithm includes an asymptotic convergence analysis for each local minimum as well as a theoretical global dense searching to ensure that all local minima and the global minimum can be found. The numerical results produced by the algorithm are seen to perform well, even for oscillatory models and high-dimensional problems.
50
Chan, Teng-Yuan, and 詹登淵. "A Web Search Assistant on Google-hard Problems." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/10328230178146588116.
Full textAbstract:
碩士銘傳大學
資訊工程學系碩士班
98
Search engine has been an indispensable tool in our daily lives. However, search engine cannot always satisfy users’ information needs. There are still many problems hard to be solved by Google. Such problems are called “Google-hard problems” in this paper. Information extraction scheme was built to resolve the Google-hard problems. The scheme extracts information from depth-zero and depth-one web pages. First, text is split into sentences and sentences are split as a term sequence by longest term first method. Second, sentences perform Chinese word segmentation by N-gram method. The scheme provides a relationship term list. Another capability uses features and benefits of Term-Clip algorithm. Text mining is performed through learning mode to collect appositional terms with the same properties as the query terms. The scheme helps users to speed up the search process. Users can handle the term list to change search direction. This is a new concept of search modes.