Artykuły w czasopismach na temat „Heuristics”
Kliknij ten link, aby zobaczyć inne rodzaje publikacji na ten temat: Heuristics.
Utwórz poprawne odniesienie w stylach APA, MLA, Chicago, Harvard i wielu innych
Sprawdź 50 najlepszych artykułów w czasopismach naukowych na temat „Heuristics”.
Przycisk „Dodaj do bibliografii” jest dostępny obok każdej pracy w bibliografii. Użyj go – a my automatycznie utworzymy odniesienie bibliograficzne do wybranej pracy w stylu cytowania, którego potrzebujesz: APA, MLA, Harvard, Chicago, Vancouver itp.
Możesz również pobrać pełny tekst publikacji naukowej w formacie „.pdf” i przeczytać adnotację do pracy online, jeśli odpowiednie parametry są dostępne w metadanych.
Przeglądaj artykuły w czasopismach z różnych dziedzin i twórz odpowiednie bibliografie.
1
Seipp, Jendrik. "Better Orders for Saturated Cost Partitioning in Optimal Classical Planning". Proceedings of the International Symposium on Combinatorial Search 8, nr 1 (1.09.2021): 149–53. http://dx.doi.org/10.1609/socs.v8i1.18438.
Pełny tekst źródłaStreszczenie:
Cost partitioning is a general method for adding multiple heuristic values admissibly. In the setting of optimal classical planning, saturated cost partitioning has recently been shown to be the cost partitioning algorithm of choice for pattern database heuristics found by hill climbing, systematic pattern database heuristics and Cartesian abstraction heuristics. To evaluate the synergy of the three heuristic types, we compute the saturated cost partitioning over the combined sets of heuristics and observe that the resulting heuristic is outperformed by the heuristic that simply maximizes over the three saturated cost partitioning heuristics computed separately for each heuristic type. Our new algorithm for choosing the orders in which saturated cost partitioning considers the heuristics allows us to compute heuristics outperforming not only the maximizing heuristic but even state-of-the-art planners.
2
Wilt, Christopher, i Wheeler Ruml. "Effective Heuristics for Suboptimal Best-First Search". Journal of Artificial Intelligence Research 57 (31.10.2016): 273–306. http://dx.doi.org/10.1613/jair.5036.
Pełny tekst źródłaStreszczenie:
Suboptimal heuristic search algorithms such as weighted A* and greedy best-first search are widely used to solve problems for which guaranteed optimal solutions are too expensive to obtain. These algorithms crucially rely on a heuristic function to guide their search. However, most research on building heuristics addresses optimal solving. In this paper, we illustrate how established wisdom for constructing heuristics for optimal search can fail when considering suboptimal search. We consider the behavior of greedy best-first search in detail and we test several hypotheses for predicting when a heuristic will be effective for it. Our results suggest that a predictive characteristic is a heuristic's goal distance rank correlation (GDRC), a robust measure of whether it orders nodes according to distance to a goal. We demonstrate that GDRC can be used to automatically construct abstraction-based heuristics for greedy best-first search that are more effective than those built by methods oriented toward optimal search. These results reinforce the point that suboptimal search deserves sustained attention and specialized methods of its own.
3
Sanggala, Ekra, i Muhammad Ardhya Bisma. "Perbandingan Savings Algorithm dengan Nearest Neighbour dalam Menyelesaikan Russian TSP Instances". Jurnal Media Teknik dan Sistem Industri 7, nr 1 (31.03.2023): 27. http://dx.doi.org/10.35194/jmtsi.v7i1.3039.
Pełny tekst źródłaStreszczenie:
Travelling Salesman Problem (TSP) is the problem for finding the shortest route starting from start node then visiting number of nodes exactly once and finally go back to start node. Several heuristics are popular for solving TSP, for example Savings Algorithm and Nearest Neighbour. Performance heuristics on solving TSP are diverse, so there is need of reference for choosing a heuristic. Comparing heuristics on solving instance can be a reference for choosing a heuristic. This paper will discuss about comparison Savings Algorithm and Nearest Neighbour on Solving Russian TSP Instances. For generating length of route, Savings Algorithm is better than Nearest Neighbour, while for generating CPU time, Nearest Neighbour is better than Savings Algorithm. Travelling Salesman Problem (TSP) merupakan permasalahan penentuan rute terpendek yang diawali dari titik start untuk mengunjungi sekumpulan titik tepat sekali dan diakhiri dengan kembali ke titik start. Beberapa Heuristik yang cukup populer untuk menyelesaikan TSP antara lain Savings Algorithm dan Nearest Neighbour. Kemampuan Heuristik dalam menyelesaikan TSP berbeda-beda, sehingga diperlukan sebuah acuan untuk menentukan Heuristik yang akan digunakan. Membandingkan Heuristik dalam menyelesaikan instance dapat menjadi acuan untuk pemilihan Heuristik. Pada paper ini akan dibahas mengenai perbandingan Savings Algorithm dan Nearest Neighbour dalam menyelesaikan Russian TSP Instances. Untuk panjang rute yang dihasilkan, maka Savings Algorithm lebih baik dibandingkan Nearest Neighbour, sedangkan untuk CPU Time yang dihasilkan, maka Nearest Neighbour lebih baik dibandingkan Savings Algorithm.
4
Ursani, Ziauddin, i Ahsan Ahmad Ursani. "Augmented tour construction heuristics for the travelling salesman problem". International Journal of Industrial Optimization 4, nr 2 (11.09.2023): 131–44. http://dx.doi.org/10.12928/ijio.v4i2.7875.
Pełny tekst źródłaStreszczenie:
Tour construction heuristics serve as fundamental techniques in optimizing the routes of a traveling salesman. These heuristics remain significant as foundational methods for generating initial solutions to the Traveling Salesman Problem (TSP), facilitating subsequent applications of tour improvement heuristics. These heuristics effectively comprise the iterative application of city node selection and insertion. However, thus far, no attempts have been made to enhance the basic structure of tour construction heuristics to bring a better initial solution for the advanced heuristics. This study aims to enhance tour construction heuristics without compromising their theoretical complexity. Specifically, an iterative step of partial tour deconstruction has been introduced to the existing heuristics. This additional step has been implemented and evaluated with three highly performing tour construction heuristics: the farthest insertion heuristic, the max difference insertion heuristic, and the fast max difference insertion heuristic. The results demonstrate that augmenting these heuristics with the partial tour deconstruction step improves the best, worst, and average solutions while preserving their theoretical complexity
5
Shperberg, Shahaf, Ariel Felner, Lior Siag i Nathan R. Sturtevant. "On the Properties of All-Pair Heuristics". Proceedings of the International Symposium on Combinatorial Search 17 (1.06.2024): 127–33. http://dx.doi.org/10.1609/socs.v17i1.31550.
Pełny tekst źródłaStreszczenie:
While most work in heuristic search concentrates on goal-specific heuristics, which estimate the shortest path cost from any state to the goal, we explore all-pair heuristics that estimate distances between all pairs of states. We examine the relationship between these heuristic functions and the shortest distance function they estimate, revealing that all-pair consistent heuristics may violate the triangle inequality. Thus, we introduce a new property for heuristics called Δ-consistency, requiring adherence to the triangle inequality. Additionally, we present a method for transforming standard consistent heuristics to be Δ-consistent, showcasing its benefits through a synthetic example. We then show that common heuristic families inherently exhibit Δ-consistency. This positive finding encourages the use of all-pair consistent heuristics, and prompts further investigation into the optimality of A*, when given an all-pair heuristic instead of a goal-specific heuristic.
6
Drake, John H., Matthew Hyde, Khaled Ibrahim i Ender Ozcan. "A genetic programming hyper-heuristic for the multidimensional knapsack problem". Kybernetes 43, nr 9/10 (3.11.2014): 1500–1511. http://dx.doi.org/10.1108/k-09-2013-0201.
Pełny tekst źródłaStreszczenie:
Purpose – Hyper-heuristics are a class of high-level search techniques which operate on a search space of heuristics rather than directly on a search space of solutions. The purpose of this paper is to investigate the suitability of using genetic programming as a hyper-heuristic methodology to generate constructive heuristics to solve the multidimensional 0-1 knapsack problem Design/methodology/approach – Early hyper-heuristics focused on selecting and applying a low-level heuristic at each stage of a search. Recent trends in hyper-heuristic research have led to a number of approaches being developed to automatically generate new heuristics from a set of heuristic components. A population of heuristics to rank knapsack items are trained on a subset of test problems and then applied to unseen instances. Findings – The results over a set of standard benchmarks show that genetic programming can be used to generate constructive heuristics which yield human-competitive results. Originality/value – In this work the authors show that genetic programming is suitable as a method to generate reusable constructive heuristics for the multidimensional 0-1 knapsack problem. This is classified as a hyper-heuristic approach as it operates on a search space of heuristics rather than a search space of solutions. To our knowledge, this is the first time in the literature a GP hyper-heuristic has been used to solve the multidimensional 0-1 knapsack problem. The results suggest that using GP to evolve ranking mechanisms merits further future research effort.
7
Seipp, Jendrik, Florian Pommerening i Malte Helmert. "New Optimization Functions for Potential Heuristics". Proceedings of the International Conference on Automated Planning and Scheduling 25 (8.04.2015): 193–201. http://dx.doi.org/10.1609/icaps.v25i1.13714.
Pełny tekst źródłaStreszczenie:
Potential heuristics, recently introduced by Pommerening et al., characterize admissible and consistent heuristics for classical planning as a set of declarative constraints. Every feasible solution for these constraints defines an admissible heuristic, and we can obtain heuristics that optimize certain criteria such as informativeness by specifying suitable objective functions. The original paper only considered one such objective function: maximizing the heuristic value of the initial state. In this paper, we explore objectives that attempt to maximize heuristic estimates for all states (reachable and unreachable), maximize heuristic estimates for a sample of reachable states, maximize the number of detected dead ends, or minimize search effort. We also search for multiple heuristics with complementary strengths that can be combined to obtain even better heuristics.
8
Narayanan, Venkatraman, Sandip Aine i Maxim Likhachev. "Improved Multi-Heuristic A* for Searching with Uncalibrated Heuristics". Proceedings of the International Symposium on Combinatorial Search 6, nr 1 (1.09.2021): 78–86. http://dx.doi.org/10.1609/socs.v6i1.18350.
Pełny tekst źródłaStreszczenie:
Recently, several researchers have brought forth the benefits of searching with multiple (and possibly inadmissible) heuristics, arguing how different heuristics could be independently useful in different parts of the state space. However, algorithms that use inadmissible heuristics in the traditional best-first sense, such as the recently developed Multi-Heuristic A* (MHA*), are subject to a crippling calibration problem: they prioritize nodes for expansion by additively combining the cost-to-come and the inadmissible heuristics even if those heuristics have no connection with the cost-to-go (e.g., the heuristics are uncalibrated) . For instance, if the inadmissible heuristic were an order of magnitude greater than the perfect heuristic, an algorithm like MHA* would simply reduce to a weighted A* search with one consistent heuristic. In this work, we introduce a general multi-heuristic search framework that solves the calibration problem and as a result a) facilitates the effective use of multiple uncalibrated inadmissible heuristics, and b) provides significantly better performance than MHA* whenever tighter sub-optimality bounds on solution quality are desired. Experimental evaluations on a complex full-body robotics motion planning problem and large sliding tile puzzles demonstrate the benefits of our framework.
9
Shanklin, Roslyn, Philip Kortum i Claudia Ziegler Acemyan. "Adaptation of Heuristic Evaluations for the Physical Environment". Proceedings of the Human Factors and Ergonomics Society Annual Meeting 64, nr 1 (grudzień 2020): 1135–39. http://dx.doi.org/10.1177/1071181320641272.
Pełny tekst źródłaStreszczenie:
Previous work has investigated the need for domain specific heuristics. Nielsen’s ten heuristics offer a general list of principles, but those principles may not capture usability issues specific to a given interface. Studies have demonstrated methods to establish a domain specific heuristic set, but very little research has been conducted on interfaces in the physical environment, creating a gap in the state-of-the-art. The research described in this paper aims to address this gap by developing an environmental heuristic set; the heuristic set was developed specifically for the Houston light rail system, METRORail. Following development, the heuristic set was validated against Nielsen’s more general heuristics through several field studies. Results highlighted that there were significantly more usability issues identified when using the environment-based heuristics than the general heuristics. This suggests that domain specific heuristics provide a framework that allows evaluators to capture usability issues particular to the interface of the physical environment.
10
Pommerening, Florian, Gabriele Röger, Malte Helmert i Blai Bonet. "LP-Based Heuristics for Cost-Optimal Planning". Proceedings of the International Conference on Automated Planning and Scheduling 24 (11.05.2014): 226–34. http://dx.doi.org/10.1609/icaps.v24i1.13621.
Pełny tekst źródłaStreszczenie:
Many heuristics for cost-optimal planning are based on linear programming. We cover several interesting heuristics of this type by a common framework that fixes the objective function of the linear program. Within the framework, constraints from different heuristics can be combined in one heuristic estimate which dominates the maximum of the component heuristics. Different heuristics of the framework can be compared on the basis of their constraints. With this new method of analysis, we show dominance of the recent LP-based state-equation heuristic over optimal cost partitioning on single-variable abstractions. We also show that the previously suggested extension of the state-equation heuristic to exploit safe variables cannot lead to an improved heuristic estimate. We experimentally evaluate the potential of the proposed framework on an extensive suite of benchmark tasks.
11
Raikhert, Kostiantyn. "THE PHILOSOPHICAL HEURISTICS OF J. HARTMAN AND YA. HNATIUK". Doxa, nr 2(38) (18.12.2022): 38–51. http://dx.doi.org/10.18524/2410-2601.2022.2(38).283062.
Pełny tekst źródłaStreszczenie:
The study surveys of philosophical heuristics and centers on the philosophical heuristics of J. Hartman and Ya. Hnatiuk. J. Hartman’s philosophical heuristics studies philosophy in terms of its heuristic nature. J. Hartman implies that the entire philosophy is a set of heuristic projects: from conceptions to methods of philosophy. Even philosophical heuristics is one such project. Philosophical heuristics is a metaphilosophy, the specific distinction of which is to study the heuristic nature of philosophy. Philosophical heuristics of Ya. Hnatiuk is a methodology focused on the creativity of philosophers. Philosophizing is a creative process, in which is involved even the exact formal logic. What J. Hartman’s philosophical heuristics and Ya. Hnatiuk’s philosophical heuristics have in common is their tendency to a kind of unity of philosophy: in the case of J. Hartman, it is the finding of the grounds for the relative unity of philosophical studies; in the case of Ya. Hnatiuk, it is the setting up of methodological communication between philosophical methods to strengthen the universal character of philosophical methodology.
12
Cichowicz, T., M. Drozdowski, M. Frankiewicz, G. Pawlak, F. Rytwinski i J. Wasilewski. "Hyper-heuristics for cross-domain search". Bulletin of the Polish Academy of Sciences: Technical Sciences 60, nr 4 (1.12.2012): 801–8. http://dx.doi.org/10.2478/v10175-012-0093-7.
Pełny tekst źródłaStreszczenie:
Abstract In this paper we present two hyper-heuristics developed for the Cross-Domain Heuristic Search Challenge. Hyper-heuristics solve hard combinatorial problems by guiding low level heuristics, rather than by manipulating problem solutions directly. Two hyper-heuristics are presented: Five Phase Approach and Genetic Hive. Development paths of the algorithms and testing methods are outlined. Performance of both methods is studied. Useful and interesting experience gained in construction of the hyper-heuristics are presented. Conclusions and recommendations for the future advancement of hyper-heuristic methodologies are discussed.
13
Fortunato, David, i Randolph T. Stevenson. "Heuristics in Context". Political Science Research and Methods 7, nr 2 (17.10.2016): 311–30. http://dx.doi.org/10.1017/psrm.2016.37.
Pełny tekst źródłaStreszczenie:
A growing literature in political science has pointed to the importance of heuristics in explaining citizens’ political attitudes, beliefs, and behaviors. At the same time, the multidisciplinary research on heuristics in general has revealed that individuals seem to use heuristics sensibly—applying them (perhaps subconsciously) when they are likely to be helpful but not otherwise. We extend this multidisciplinary work to political behavior and present a general theory of contextual variation in political heuristic use applied to discover under what conditions (i.e., what political contexts) voters will use a partisanship heuristic to infer the legislative votes of their legislators in imperfectly disciplined voting contexts. More specifically, we predict that US constituents of loyal partisan senators will use the partisanship heuristic more often than constituents of less loyal senators. Our empirical analysis reveals strong support for our theory, contributing to our understanding of political heuristics in general and adding nuance to our understanding of the partisanship heuristic in particular.
14
Uzoma, Ihediohamma Raphael, Shelena Soosay Nathan, Nor Laily Hashim i Hanif. "INCLUSIVITY IN MOBILE SHOPPING APPS: AN EMPHASIS ON LEARNABILITY CHECKLISTS IN CONDUCTING A HEURISTIC EVALUATION". Journal of Digital System Development 1 (31.10.2023): 46–58. http://dx.doi.org/10.32890/jdsd2023.1.5.
Pełny tekst źródłaStreszczenie:
Studies on heuristic evaluation of mobile applications have been an emerging domain. However, existing checklists are too general and unable to clearly define the measurements for evaluating mobile shopping applications. This paper proposes suitable heuristics under the learnability measure for a checklist in conducting heuristic evaluation in supporting the inclusivity of a mobile shopping application. This study was conducted in two phases: generate the learnability measures based on heuristics and sub-heuristics from content analysis and verify the proposed heuristic evaluation checklist from the learnability measures through expert reviews. As a result, a verified Learnability checklist consisting of three heuristics was selected: recognition rather than recall, user control and freedom and match between the system and the real world. For each heuristic, suitable sub-heuristics and evaluation questions were identified. Through the learnability checklist, usability experts and analysts can consistently perform their evaluation during heuristics evaluation on other mobile shopping apps. This is to ensure that the apps have all relevant features that enhance the learning ability of their users, using the apps confidently and proficiently, providing their contentment in every usage scenario.
15
Ursani, Ziauddin, i David W. Corne. "Introducing Complexity Curtailing Techniques for the Tour Construction Heuristics for the Travelling Salesperson Problem". Journal of Optimization 2016 (2016): 1–15. http://dx.doi.org/10.1155/2016/4786268.
Pełny tekst źródłaStreszczenie:
In this paper, complexity curtailing techniques are introduced to create faster version of insertion heuristics, that is, cheapest insertion heuristic (CIH) and largest insertion heuristic (LIH), effectively reducing their complexities fromO(n3)toO(n2)with no significant effect on quality of solution. This paper also examines relatively not very known heuristic concept of max difference and shows that it can be culminated into a full-fledged max difference insertion heuristic (MDIH) by defining its missing steps. Further to this the paper extends the complexity curtailing techniques to MDIH to create its faster version. The resultant heuristic, that is, fast max difference insertion heuristic (FMDIH), outperforms the “farthest insertion” heuristic (FIH) across a wide spectrum of popular datasets with statistical significance, even though both the heuristics have the same worst case complexity ofO(n2). It should be noted that FIH is considered best among lowest order complexity heuristics. The complexity curtailing techniques presented here open up the new area of research for their possible extension to other heuristics.
16
Trevizan, Felipe, Sylvie Thiébaux i Patrik Haslum. "Occupation Measure Heuristics for Probabilistic Planning". Proceedings of the International Conference on Automated Planning and Scheduling 27 (5.06.2017): 306–15. http://dx.doi.org/10.1609/icaps.v27i1.13840.
Pełny tekst źródłaStreszczenie:
For the past 25 years, heuristic search has been used to solve domain-independent probabilistic planning problems, but with heuristics that determinise the problem and ignore precious probabilistic information. To remedy this situation, we explore the use of occupation measures, which represent the expected number of times a given action will be executed in a given state of a policy. By relaxing the well-known linear program that computes them, we derive occupation measure heuristics -- the first admissible heuristics for stochastic shortest path problems (SSPs) taking probabilities into account. We show that these heuristics can also be obtained by extending recent operator-counting heuristic formulations used in deterministic planning. Since the heuristics are formulated as linear programs over occupation measures, they can easily be extended to more complex probabilistic planning models, such as constrained SSPs (C-SSPs). Moreover, their formulation can be tightly integrated into i-dual, a recent LP-based heuristic search algorithm for (constrained) SSPs, resulting in a novel probabilistic planning approach in which policy update and heuristic computation work in unison. Our experiments in several domains demonstrate the benefits of these new heuristics and approach.
17
Greco, Matias, Pablo Araneda i Jorge A. Baier. "Focal Discrepancy Search for Learned Heuristics (Extended Abstract)". Proceedings of the International Symposium on Combinatorial Search 15, nr 1 (17.07.2022): 282–84. http://dx.doi.org/10.1609/socs.v15i1.21786.
Pełny tekst źródłaStreszczenie:
Machine learning allows learning accurate but inadmissible heuristics for hard combinatorial puzzles like the 15-puzzle, the 24-puzzle, and Rubik's cube. In this paper, we investigate how to exploit these learned heuristics in the context of heuristic search with suboptimality guarantees. Specifically, we study how Focal Search (FS), a well-known bounded-suboptimal search algorithm can be modified to better exploit inadmissible learned heuristics. We propose to use Focal Discrepancy Search (FDS) in the context of learned heuristics, which uses a discrepancy function, instead of the learned heuristic, to sort the focal list. In our empirical evaluation, we evaluate FS and FDS using DeepCubeA, an effective learned heuristic for the 15-puzzle. We show that FDS substantially outperforms FS. This suggests that in some domains, when a highly accurate heuristics is available, one should always consider using discrepancies for better search.
18
Correa, Augusto B., i Florian Pommerening. "An Empirical Study of Perfect Potential Heuristics". Proceedings of the International Conference on Automated Planning and Scheduling 29 (25.05.2021): 114–18. http://dx.doi.org/10.1609/icaps.v29i1.3466.
Pełny tekst źródłaStreszczenie:
Potential heuristics are weighted functions over state features of a planning task. A recent study defines the complexity of a task as the minimum required feature complexity for a potential heuristic that makes a search backtrack-free. This gives an indication of how complex potential heuristics need to be to achieve good results in satisficing planning. However, these results do not directly transfer to optimal planning.In this paper, we empirically study how complex potential heuristics must be to represent the perfect heuristic and how close to perfect heuristics can get with a limited number of features. We aim to identify the practical trade-offs between size, complexity and time for the quality of potential heuristics. Our results show that, even for simple planning tasks, finding perfect potential heuristics might be harder than expected.
19
Ozdowska, Anne, Penny Sweetser i Mahsuum Daiiani. "A Scoping Review of Heuristics in Videos Games Research: Definitions, Development, Application, and Operationalisation". Proceedings of the ACM on Human-Computer Interaction 7, CHI PLAY (29.09.2023): 402–24. http://dx.doi.org/10.1145/3611035.
Pełny tekst źródłaStreszczenie:
Heuristics present a cheap and effective way of evaluating usability. However, in video games, evaluating unique player experiences that are dependent on individual preferences and abilities presents a challenge that goes beyond usability. Video games are more than just functional software, so games heuristics have been adapted to help examine functionality and experience. This paper reports on how papers published in the ACM Digital Library between 2012 and 2022 develop and apply heuristics in video games research. We found that heuristics are often used outside their intended purpose of being used in an expert evaluation. Instead, they are used as survey instruments, interview guides, codes for thematic analysis, and as design guidelines. This research contributes to HCI and video games research by distinguishing the terms design guidelines and design principles from heuristics. We make recommendations for researchers around developing heuristics and conducting video game heuristic evaluations. We propose a method for operationalising heuristics and make recommendations for the implementation of heuristics to improve the quality of video game heuristic reviews.
20
Abdul-Razaq, Tariq, Hanan Chachan i Faez Ali. "Modified Heuristics for Scheduling in Flow Shop to Minimize Makespan". Journal of Al-Rafidain University College For Sciences ( Print ISSN: 1681-6870 ,Online ISSN: 2790-2293 ), nr 2 (19.10.2021): 1–20. http://dx.doi.org/10.55562/jrucs.v30i2.361.
Pełny tekst źródłaStreszczenie:
The NP-completeness of flow shops scheduling problems has been discussed for many years. Hence many heuristics have been proposed to obtain solutions of good quality with a small computational effort. The CDS (Campbell et al) and NEH (Nawaz, Enscore and Ham) heuristics are efficient among meta-heuristics such as Particle Swarm Optimization (PSO) and Genetic Algorithm (GA).This paper discusses some methods and suggests new developing to the methods of the scheduling in flow shop to minimize makespan problems. Our main object in this paper, from one side, is to improve efficient heuristics which will be better than the existing heuristics given in the literature and yield solutions within a short time like Simple Heuristic Methods (SHM) and the First Heuristic Decreasing Arrange (DR). From other side, we apply two local search methods like GA and PSO algorithms on flow shop problems.Experimental analysis has been given of the performance of the proposed heuristics and local search methods with the relative efficient existing heuristics.
21
Парфентьєва І. П. i Матвійчук К. О. "ЕТИМОЛОГІЯ ПОНЯТТЯ “ЕВРИСТИЧНИЙ ПІДХІД”". World Science 3, nr 8(36) (30.08.2018): 46–49. http://dx.doi.org/10.31435/rsglobal_ws/30082018/6078.
Pełny tekst źródłaStreszczenie:
The article deals with the term "heuristics", which in scientific knowledge has the designation as a "method of finding." The author conducts an analysis of scientific literature on the interpretation of heuristics as a scientific concept. Heuristics as an independent science has not been fully formed yet. Despite the large number of scientific papers devoted to questions of heuristics, they usually relate to its particular problems and do not give a clear idea of either the object or subject of heuristics or its status among other sciences. It is suggested that pedagogical heuristics are defined as one of the branches of heuristics, which studies fundamental principles of didactics and the systematic organization of students' heuristic activity in a supervised interaction of a teacher and implements them in general and in vocational education using the system of problem tasks for the purposeful development of intelligence. The main tasks of pedagogical heuristics interact with the tasks of didactics in the qualitative formation of a future specialist. Therefore, pedagogical heuristics in researches use heuristic methods that allow to accelerate the process of solving any problem.
22
Erkol, Şirag, i Gönenç Yücel. "Influence maximization based on partial network structure information: A comparative analysis on seed selection heuristics". International Journal of Modern Physics C 28, nr 10 (październik 2017): 1750122. http://dx.doi.org/10.1142/s0129183117501224.
Pełny tekst źródłaStreszczenie:
In this study, the problem of seed selection is investigated. This problem is mainly treated as an optimization problem, which is proved to be NP-hard. There are several heuristic approaches in the literature which mostly use algorithmic heuristics. These approaches mainly focus on the trade-off between computational complexity and accuracy. Although the accuracy of algorithmic heuristics are high, they also have high computational complexity. Furthermore, in the literature, it is generally assumed that complete information on the structure and features of a network is available, which is not the case in most of the times. For the study, a simulation model is constructed, which is capable of creating networks, performing seed selection heuristics, and simulating diffusion models. Novel metric-based seed selection heuristics that rely only on partial information are proposed and tested using the simulation model. These heuristics use local information available from nodes in the synthetically created networks. The performances of heuristics are comparatively analyzed on three different network types. The results clearly show that the performance of a heuristic depends on the structure of a network. A heuristic to be used should be selected after investigating the properties of the network at hand. More importantly, the approach of partial information provided promising results. In certain cases, selection heuristics that rely only on partial network information perform very close to similar heuristics that require complete network data.
23
Soria-Alcaraz, Jorge A., Gabriela Ochoa, Andres Espinal, Marco A. Sotelo-Figueroa, Manuel Ornelas-Rodriguez i Horacio Rostro-Gonzalez. "A Methodology for Classifying Search Operators as Intensification or Diversification Heuristics". Complexity 2020 (13.02.2020): 1–10. http://dx.doi.org/10.1155/2020/2871835.
Pełny tekst źródłaStreszczenie:
Selection hyper-heuristics are generic search tools that dynamically choose, from a given pool, the most promising operator (low-level heuristic) to apply at each iteration of the search process. The performance of these methods depends on the quality of the heuristic pool. Two types of heuristics can be part of the pool: diversification heuristics, which help to escape from local optima, and intensification heuristics, which effectively exploit promising regions in the vicinity of good solutions. An effective search strategy needs a balance between these two strategies. However, it is not straightforward to categorize an operator as intensification or diversification heuristic on complex domains. Therefore, we propose an automated methodology to do this classification. This brings methodological rigor to the configuration of an iterated local search hyper-heuristic featuring diversification and intensification stages. The methodology considers the empirical ranking of the heuristics based on an estimation of their capacity to either diversify or intensify the search. We incorporate the proposed approach into a state-of-the-art hyper-heuristic solving two domains: course timetabling and vehicle routing. Our results indicate improved performance, including new best-known solutions for the course timetabling problem.
24
Savolainen, Reijo. "Heuristics elements of information-seeking strategies and tactics: a conceptual analysis". Journal of Documentation 73, nr 6 (9.10.2017): 1322–42. http://dx.doi.org/10.1108/jd-11-2016-0144.
Pełny tekst źródłaStreszczenie:
Purpose The purpose of this paper is to elaborate the picture of strategies and tactics for information seeking and searching by focusing on the heuristic elements of such strategies and tactics. Design/methodology/approach A conceptual analysis of a sample of 31 pertinent investigations was conducted to find out how researchers have approached heuristics in the above context since the 1970s. To achieve this, the study draws on the ideas produced within the research programmes on Heuristics and Biases, and Fast and Frugal Heuristics. Findings Researchers have approached the heuristic elements in three major ways. First, these elements are defined as general level constituents of browsing strategies in particular. Second, heuristics are approached as search tips. Third, there are examples of conceptualizations of individual heuristics. Familiarity heuristic suggests that people tend to prefer sources that have worked well in similar situations in the past. Recognition heuristic draws on an all-or-none distinction of the information objects, based on cues such as information scent. Finally, representativeness heuristic is based on recalling similar instances of events or objects and judging their typicality in terms of genres, for example. Research limitations/implications As the study focuses on three heuristics only, the findings cannot be generalized to describe the use of all heuristic elements of strategies and tactics for information seeking and searching. Originality/value The study pioneers by providing an in-depth analysis of the ways in which the heuristic elements are conceptualized in the context of information seeking and searching. The findings contribute to the elaboration of the conceptual issues of information behavior research.
25
Seipp, Jendrik, i Malte Helmert. "Subset-Saturated Cost Partitioning for Optimal Classical Planning". Proceedings of the International Conference on Automated Planning and Scheduling 29 (25.05.2021): 391–400. http://dx.doi.org/10.1609/icaps.v29i1.3503.
Pełny tekst źródłaStreszczenie:
Cost partitioning is a method for admissibly adding multiple heuristics for state-space search. Saturated cost partitioning considers the given heuristics in sequence, assigning to each heuristic the minimum fraction of remaining costs that it needs to preserve its estimates for all states. We generalize saturated cost partitioning by allowing to preserve the heuristic values of only a subset of states and show that this often leads to stronger heuristics.
26
Chen, Dillon Z., i Sylvie Thiébaux. "Novelty Heuristics, Multi-Queue Search, and Portfolios for Numeric Planning". Proceedings of the International Symposium on Combinatorial Search 17 (1.06.2024): 203–7. http://dx.doi.org/10.1609/socs.v17i1.31559.
Pełny tekst źródłaStreszczenie:
Heuristic search is a powerful approach for solving planning problems and numeric planning is no exception. In this paper, we boost the performance of heuristic search for numeric planning with various powerful techniques orthogonal to improving heuristic informedness: numeric novelty heuristics, the Manhattan distance heuristic, and exploring the use of multi-queue search and portfolios for combining heuristics.
27
Helmert, Malte. "Landmark Heuristics for the Pancake Problem". Proceedings of the International Symposium on Combinatorial Search 1, nr 1 (25.08.2010): 109–10. http://dx.doi.org/10.1609/socs.v1i1.18176.
Pełny tekst źródłaStreszczenie:
We describe the gap heuristic for the pancake problem, which dramatically outperforms current abstraction-based heuristics for this problem. The gap heuristic belongs to a family of landmark heuristics that have recently been very successfully applied to planning problems.
28
BOUZY, BRUNO. "HISTORY AND TERRITORY HEURISTICS FOR MONTE CARLO GO". New Mathematics and Natural Computation 02, nr 02 (lipiec 2006): 139–46. http://dx.doi.org/10.1142/s1793005706000427.
Pełny tekst źródłaStreszczenie:
Recently, the Monte Carlo approach has been applied to computer go with promising success. INDIGO uses such an approach which can be enhanced with specific heuristics. This paper assesses two heuristics within the 19 × 19 Monte Carlo go framework of INDIGO: the territory heuristic and the history heuristic, both in their internal and external versions. The external territory heuristic is more effective, leading to a 40-point improvement on 19 × 19 boards. The external history heuristic brings about a 10-point improvement. The internal territory heuristic yields a few points improvement, and the internal history heuristic has already been assessed on 19 × 19 boards in previous publications. Most of these heuristics were used by INDIGO at the 2004 Computer Olympiad.
29
Štolba, Michal, i Antonín Komenda. "Relaxation Heuristics for Multiagent Planning". Proceedings of the International Conference on Automated Planning and Scheduling 24 (11.05.2014): 298–306. http://dx.doi.org/10.1609/icaps.v24i1.13642.
Pełny tekst źródłaStreszczenie:
Similarly to classical planning, in MA-Strips multiagent planning, heuristics significantly improve efficiency of search-based planners. Heuristics based on solving a relaxation of the original planning problem are intensively studied and well understood. In particular, frequently used is the delete relaxation, where all delete effects of actions are omitted. In this paper, we present a unified view on distribution of delete relaxation heuristics for multiagent planning. Until recently, the most common approach to adaptation of heuristics for multiagent planning was to compute the heuristic estimate using only a projection of the problem for a single agent. In this paper, we place such approach in the context of techniques which allow sharing more information among the agents and thus improve the heuristic estimates. We thoroughly experimentally evaluate properties of our distribution of additive, max and Fast-Forward relaxation heuristics in a planner based on distributed Best-First Search. The best performing distributed relaxation heuristics favorably compares to a state-of-the-art MA-Strips planner in terms of benchmark problem coverage. Finally, we analyze impact of limited agent interactions by means of recursion depth of the heuristic estimates.
30
Lissovoi, Andrei, Pietro S. Oliveto i John Alasdair Warwicker. "On the Time Complexity of Algorithm Selection Hyper-Heuristics for Multimodal Optimisation". Proceedings of the AAAI Conference on Artificial Intelligence 33 (17.07.2019): 2322–29. http://dx.doi.org/10.1609/aaai.v33i01.33012322.
Pełny tekst źródłaStreszczenie:
Selection hyper-heuristics are automated algorithm selection methodologies that choose between different heuristics during the optimisation process. Recently selection hyperheuristics choosing between a collection of elitist randomised local search heuristics with different neighbourhood sizes have been shown to optimise a standard unimodal benchmark function from evolutionary computation in the optimal expected runtime achievable with the available low-level heuristics. In this paper we extend our understanding to the domain of multimodal optimisation by considering a hyper-heuristic from the literature that can switch between elitist and nonelitist heuristics during the run. We first identify the range of parameters that allow the hyper-heuristic to hillclimb efficiently and prove that it can optimise a standard hillclimbing benchmark function in the best expected asymptotic time achievable by unbiased mutation-based randomised search heuristics. Afterwards, we use standard multimodal benchmark functions to highlight function characteristics where the hyper-heuristic is efficient by swiftly escaping local optima and ones where it is not. For a function class called CLIFFd where a new gradient of increasing fitness can be identified after escaping local optima, the hyper-heuristic is extremely efficient while a wide range of established elitist and non-elitist algorithms are not, including the well-studied Metropolis algorithm. We complete the picture with an analysis of another standard benchmark function called JUMPd as an example to highlight problem characteristics where the hyper-heuristic is inefficient. Yet, it still outperforms the wellestablished non-elitist Metropolis algorithm.
31
Aliferis, C. F., i R. A. Miller. "On the Heuristic Nature of Medical Decision-Support Systems". Methods of Information in Medicine 34, nr 01/02 (1995): 5–14. http://dx.doi.org/10.1055/s-0038-1634584.
Pełny tekst źródłaStreszczenie:
Abstract:In the realm of medical decision-support systems, the term “heuristic systems” is often considered to be synonymous with “medical artificial intelligence systems” or with “systems employing informal model(s) of problem solving”. Such a view may be inaccurate and possibly impede the conceptual development of future systems. This article examines the nature of heuristics and the levels at which heuristic solutions are introduced during system design and implementation. The authors discuss why heuristics are ubiquitous in all medical decision-support systems operating at non-trivial domains, and propose a unifying definition of heuristics that encompasses formal and ad hoc systems. System developers should be aware of the heuristic nature of all problem solving done in complex real world domains, and characterize their own use of heuristics in describing system development and implementation.
32
Sievers, Silvan, Daniel Gnad i Álvaro Torralba. "Additive Pattern Databases for Decoupled Search". Proceedings of the International Symposium on Combinatorial Search 15, nr 1 (17.07.2022): 180–89. http://dx.doi.org/10.1609/socs.v15i1.21766.
Pełny tekst źródłaStreszczenie:
Abstraction heuristics are the state of the art in optimal classical planning as heuristic search. Despite their success for explicit-state search, though, abstraction heuristics are not available for decoupled state-space search, an orthogonal reduction technique that can lead to exponential savings by decomposing planning tasks. In this paper, we show how to compute pattern database (PDB) heuristics for decoupled states. The main challenge lies in how to additively employ multiple patterns, which is crucial for strong search guidance of the heuristics. We show that in the general case, for arbitrary collections of PDBs, computing the heuristic for a decoupled state is exponential in the number of leaf components of decoupled search. We derive several variants of decoupled PDB heuristics that allow to additively combine PDBs avoiding this blow-up and evaluate them empirically.
33
tetlock, philip e. "gauging the heuristic value of heuristics". Behavioral and Brain Sciences 28, nr 4 (sierpień 2005): 562–63. http://dx.doi.org/10.1017/s0140525x05430095.
Pełny tekst źródłaStreszczenie:
heuristics are necessary but far from sufficient explanations for moral judgment. this commentary stresses: (a) the need to complement cold, cognitive-economizing functionalist accounts with hot, value-expressive, social-identity-affirming accounts; and (b) the importance of conducting reflective-equilibrium thought and laboratory experiments that explore the permeability of the boundaries people place on the “thinkable.”
34
Clausecker, Robert K. P., i Florian Schintke. "A Measure of Quality for IDA* Heuristics". Proceedings of the International Symposium on Combinatorial Search 12, nr 1 (21.07.2021): 55–63. http://dx.doi.org/10.1609/socs.v12i1.18551.
Pełny tekst źródłaStreszczenie:
We present a novel way to judge the performance of IDA* heuristics. With this measure of heuristic quality η, different heuristics for the same problem space can be compared objectively without regards to a particular problem instance. We show how η can be used to model the performance expectations of PDB heuristics. By drawing histograms of the contributions of different parts of the search space to η, we show what parts are most critical to the quality of a heuristic and contribute to the long-standing question on what h values are most critical to the performance of an IDA* heuristic.
35
Speck, David, André Biedenkapp, Frank Hutter, Robert Mattmüller i Marius Lindauer. "Learning Heuristic Selection with Dynamic Algorithm Configuration". Proceedings of the International Conference on Automated Planning and Scheduling 31 (17.05.2021): 597–605. http://dx.doi.org/10.1609/icaps.v31i1.16008.
Pełny tekst źródłaStreszczenie:
A key challenge in satisficing planning is to use multiple heuristics within one heuristic search. An aggregation of multiple heuristic estimates, for example by taking the maximum, has the disadvantage that bad estimates of a single heuristic can negatively affect the whole search. Since the performance of a heuristic varies from instance to instance, approaches such as algorithm selection can be successfully applied. In addition, alternating between multiple heuristics during the search makes it possible to use all heuristics equally and improve performance. However, all these approaches ignore the internal search dynamics of a planning system, which can help to select the most useful heuristics for the current expansion step. We show that dynamic algorithm configuration can be used for dynamic heuristic selection which takes into account the internal search dynamics of a planning system. Furthermore, we prove that this approach generalizes over existing approaches and that it can exponentially improve the performance of the heuristic search. To learn dynamic heuristic selection, we propose an approach based on reinforcement learning and show empirically that domain-wise learned policies, which take the internal search dynamics of a planning system into account, can exceed existing approaches.
36
Veerapaneni, Rishi, Muhammad Suhail Saleem i Maxim Likhachev. "Learning Local Heuristics for Search-Based Navigation Planning". Proceedings of the International Conference on Automated Planning and Scheduling 33, nr 1 (1.07.2023): 634–38. http://dx.doi.org/10.1609/icaps.v33i1.27245.
Pełny tekst źródłaStreszczenie:
Graph search planning algorithms for navigation typically rely heavily on heuristics to efficiently plan paths. As a result, while such approaches require no training phase and can directly plan long horizon paths, they often require careful hand designing of informative heuristic functions. Recent works have started bypassing hand designed heuristics by using machine learning to learn heuristic functions that guide the search algorithm. While these methods can learn complex heuristic functions from raw input, they i) require significant training and ii) do not generalize well to new maps and longer horizon paths. Our contribution is showing that instead of learning a global heuristic estimate, we can define and learn local heuristics which results in a significantly smaller learning problem and improves generalization. We show that using such local heuristics can reduce node expansions by 2-20x while maintaining bounded suboptimality, are easy to train, and generalize to new maps & long horizon plans.
37
Wimsatt, William C. "Heuristics refound". Behavioral and Brain Sciences 23, nr 5 (październik 2000): 766–67. http://dx.doi.org/10.1017/s0140525x00513442.
Pełny tekst źródłaStreszczenie:
Gigerenzer et al.'s is an extremely important book. The ecological validity of the key heuristics is strengthened by their relation to ubiquitous Poisson processes. The recognition heuristic is also used in conspecific cueing processes in ecology. Three additional classes of problem-solving heuristics are proposed for further study: families based on near-decomposability analysis, exaptive construction of functional structures, and robustness.
38
Özcan, Ender, Mustafa Misir, Gabriela Ochoa i Edmund K. Burke. "A Reinforcement Learning - Great-Deluge Hyper-Heuristic for Examination Timetabling". International Journal of Applied Metaheuristic Computing 1, nr 1 (styczeń 2010): 39–59. http://dx.doi.org/10.4018/jamc.2010102603.
Pełny tekst źródłaStreszczenie:
Hyper-heuristics can be identified as methodologies that search the space generated by a finite set of low level heuristics for solving search problems. An iterative hyper-heuristic framework can be thought of as requiring a single candidate solution and multiple perturbation low level heuristics. An initially generated complete solution goes through two successive processes (heuristic selection and move acceptance) until a set of termination criteria is satisfied. A motivating goal of hyper-heuristic research is to create automated techniques that are applicable to a wide range of problems with different characteristics. Some previous studies show that different combinations of heuristic selection and move acceptance as hyper-heuristic components might yield different performances. This study investigates whether learning heuristic selection can improve the performance of a great deluge based hyper-heuristic using an examination timetabling problem as a case study.
39
Jiang, He, Junying Qiu i Jifeng Xuan. "A Hyper-Heuristic Using GRASP with Path-Relinking". Journal of Information Technology Research 4, nr 2 (kwiecień 2011): 31–42. http://dx.doi.org/10.4018/jitr.2011040103.
Pełny tekst źródłaStreszczenie:
The goal of hyper-heuristics is to design and choose heuristics to solve complex problems. The primary motivation behind the hyper-heuristics is to generalize the solving ability of the heuristics. In this paper, the authors propose a Hyper-heuristic using GRASP with Path-Relinking (HyGrasPr). HyGrasPr generates heuristic sequences to produce solutions within an iterative procedure. The procedure of HyGrasPr consists of three phases, namely the construction phase, the local search phase, and the path-relinking phase. To show the performance of the HyGrasPr, the authors use the nurse rostering problem as a case study. The authors use an existing simulated annealing based hyper-heuristic as a baseline. The experimental results indicate that HyGrasPr can achieve better solutions than SAHH within the same running time and the path-relinking phase is effective for the framework of HyGrasPr.
40
Messa, Frederico, i André Grahl Pereira. "A Best-First Search Algorithm for FOND Planning and Heuristic Functions to Optimize Decompressed Solution Size". Proceedings of the International Conference on Automated Planning and Scheduling 33, nr 1 (1.07.2023): 277–85. http://dx.doi.org/10.1609/icaps.v33i1.27205.
Pełny tekst źródłaStreszczenie:
In this work, we study fully-observable non-deterministic (FOND) planning, which models uncertainty through actions with non-deterministic effects. We present a best-first heuristic search algorithm called AND* that searches the policy-space of the FOND task to find a solution policy. We generalize the concepts of optimality, admissibility, and goal-awareness for FOND. Using these new concepts, we formalize the concept of heuristic functions that can guide a policy-space search. We analyze different aspects of the general structure of FOND solutions to introduce and characterize a set of FOND heuristics that estimate how far a policy is from becoming a solution. One of these heuristics applies a novel insight. Guided by them AND* returns only solutions with the minimal possible number of mapped states. We systematically study these FOND heuristics theoretically and empirically. We observe that our best heuristic makes AND* much more effective than the straightforward heuristics. We believe that our work allows a better understanding of how to design algorithms and heuristics to solve FOND tasks.
41
Lohmüller, Valentin, Daniel Schmaderer i Christian Wolff. "A Heuristic Checklist for Second Screen Applications". i-com 18, nr 1 (26.04.2019): 55–65. http://dx.doi.org/10.1515/icom-2019-0003.
Pełny tekst źródłaStreszczenie:
Abstract This paper presents domain-specific heuristics for second screen applications and the development of a heuristics checklist to enable a more intuitive and structured application of the created heuristics. The heuristics presented were developed on the basis of Nielsen [12] Ten Usability Heuristics in a research-based approach using specific literature and a focus group. In order to evaluate the quality of the derived checklist, a heuristic evaluation of a second screen application with five users was carried out and its results compared to a user study with 20 participants. This resulted in an average validity of 0.5 and a high completeness of 0.74. The harmonic mean of these values results in an F-measure of 0.6 with an equal weighting. This value speaks for a sufficient validity of the created heuristic checklist in the first iteration.
42
Rott, Benjamin. "Rethinking heuristics – characterizations and vignettes". Lumat: International Journal of Math, Science and Technology Education 3, nr 1 (28.02.2015): 122–26. http://dx.doi.org/10.31129/lumat.v3i1.1055.
Pełny tekst źródłaStreszczenie:
The concept of “heuristics” or “heuristic strategies” is central to (mathematical) problem solving and related research; however, there is no generally accepted definition of this term. Trying to clarify the concept might help avoiding misunderstandings and difficulties in dealing with studies that use different terms meaning the same concepts or that use the same terms meaning different concepts. Therefore, the research presented in this paper aims at a clarification of the term “heuristics” and suggestions for the use of it in future research. Building on previous work from last year’s ProMath conference, the consequences of using different characterizations of “heuristics” on vignettes (= short, completed scenes) of problem solving attempts are investigated. The conceptualization of “heuristics” has a significant influence on the types and numbers of perceived heuristics, which in turn affects empirical studies that identify and analyze heuristic strategies.
43
Klößner, Thorsten, i Jörg Hoffmann. "Pattern Databases for Stochastic Shortest Path Problems". Proceedings of the International Symposium on Combinatorial Search 12, nr 1 (21.07.2021): 131–35. http://dx.doi.org/10.1609/socs.v12i1.18561.
Pełny tekst źródłaStreszczenie:
Stochastic shortest-path problems (SSP) are an important subclass of MDPs for which heuristic search algorithms exist since over a decade. Yet most known heuristic functions rely on determinization so do not actually take the transition probabilities into account. The only exceptions are Trevizan et al.'s heuristics hpom and hroc, which are geared at solving more complex (constrained) MDPs. Here we contribute pattern database (PDB) heuristics for SSPs, including an additivity criterion. These new heuristics turn out to be very competitive, even when using a simple systematic generation of pattern collections up to a fixed size. In our experiments, they beat determinization-based heuristics, and tend to yield better runtimes than hpom and hroc.
44
Quiñones, Daniela, Cristian Rusu, Diego Arancibia, Sebastián González i María Josée Saavedra. "SNUXH: A Set of Social Network User Experience Heuristics". Applied Sciences 10, nr 18 (19.09.2020): 6547. http://dx.doi.org/10.3390/app10186547.
Pełny tekst źródłaStreszczenie:
With the growth and overcrowding of the internet, the use of online social networks has been increasing. Currently, social networks are used by a wide variety of users–with different objectives and in different contexts of use–, so it is essential to design intuitive and easy to use social network applications that generate a positive user experience (UX). The heuristic evaluation is a well-known evaluation method that allows detecting usability problems; a group of experts evaluates a product and/or system using a set of heuristics as a guide. Although the heuristic evaluation is oriented to evaluate the usability, it can be useful to evaluate other aspects related to the UX. Due to the specific features of social networks, it is necessary to have a specific set of heuristics to evaluate them. Sets of specific heuristics for social networks have been proposed, but they focus on evaluating the only usability. This article presents a set of heuristics that attend not only usability issues, but other UX factors as well, social network user experience heuristics (SNUXH). The new set of heuristics was developed, validated, and refined in four iterations. The results obtained in the experimental validation indicate that the SNUXH set is useful and more effective than generic heuristics (Nielsen’s heuristics) when evaluating social networks.
45
Katz, Michael, i Carmel Domshlak. "Structural-Pattern Databases". Proceedings of the International Conference on Automated Planning and Scheduling 19 (16.10.2009): 186–93. http://dx.doi.org/10.1609/icaps.v19i1.13351.
Pełny tekst źródłaStreszczenie:
Explicit abstraction heuristics, notably pattern-database and merge-and-shrink heuristics, are employed by some state-of-the-art optimal heuristic-search planners. The major limitation of these abstraction heuristics is that the size of the abstract space has to be bounded by a (large) constant. Targeting this issue, Katz and Domshlak (2008b) introduced structural, and in particular fork-decomposition, abstractions, in which the planning task is abstracted by an instance of a tractable fragment of optimal planning. At first view, however, the lunch was not free. Some of the power of the explicit abstraction heuristics comes from pre-computing the heuristic function offline, and then determine h(s) for each evaluated state s by a very fast lookup in a "database." In contrast, fork-decomposition offer a poly-time, yet far from being fast, computation. In this contribution, we show that the time-per-node complexity bottleneck of the fork-decomposition heuristics can be successfully overcome. Specifically, we show that an equivalent of the explicit abstractions' notion of "database" exists for the fork-decomposition abstractions as well, and this despite of their exponential-size abstract spaces. Experimentally, we show that heuristic search with such "databased" fork-decomposition heuristics favorably competes with the state-of-the-art of optimal planning.
46
Luna Gutierrez, Ricardo, i Matteo Leonetti. "Meta Reinforcement Learning for Heuristic Planing". Proceedings of the International Conference on Automated Planning and Scheduling 31 (17.05.2021): 551–59. http://dx.doi.org/10.1609/icaps.v31i1.16003.
Pełny tekst źródłaStreszczenie:
Heuristic planning has a central role in classical planning applications and competitions. Thanks to this success, there has been an increasing interest in using Deep Learning to create high-quality heuristics in a supervised fashion, learning from optimal solutions of previously solved planning problems. Meta-Reinforcement learning is a fast growing research area concerned with learning, from many tasks, behaviours that can quickly generalize to new tasks from the same distribution of the training ones. We make a connection between meta-reinforcement learning and heuristic planning, showing that heuristic functions meta-learned from planning problems, in a given domain, can outperform both popular domain-independent heuristics, and heuristics learned by supervised learning. Furthermore, while most supervised learning algorithms rely on ad-hoc encodings of the state representation, our method uses as input a general PDDL 3.1 description. We evaluated our heuristic with an A* planner on six domains from the International Planning Competition and the FF Domain Collection, showing that the meta-learned heuristic leads to the expansion, on average, of fewer states than three popular heuristics used by the FastDownward planner, and a supervised-learned heuristic.
47
Goldenberg, Meir, Ariel Felner, Nathan Sturtevant i Jonathan Schaeffer. "Portal-Based True-Distance Heuristics for Path Finding". Proceedings of the International Symposium on Combinatorial Search 1, nr 1 (25.08.2010): 39–45. http://dx.doi.org/10.1609/socs.v1i1.18169.
Pełny tekst źródłaStreszczenie:
True distance memory-based heuristics (TDHs) were recently introduced as a way to obtain admissible heuristics for explicit state spaces. In this paper, we introduce a new TDH, the portal-based heuristic. The domain is partitioned into regions and portals between regions are identified. True distances between all pairs of portals are stored and used to obtain admissible heuristics throughout the search. We introduce an A*-based algorithm that takes advantage of the special properties of the new heuristic. We study the advantages and limitations of the new heuristic. Our experimental results show large performance improvements over previously-reported TDHs for commonly used classes of maps.
48
Mellouli, O., I. Hafidi i A. Metrane. "A modified choice function hyper-heuristic with Boltzmann function". Mathematical Modeling and Computing 8, nr 4 (2021): 736–46. http://dx.doi.org/10.23939/mmc2021.04.736.
Pełny tekst źródłaStreszczenie:
Hyper-heuristics are a subclass of high-level research methods that function in a low-level heuristic research space. Their aim objective is to improve the level of generality for solving combinatorial optimization problems using two main components: a methodology for the heuristic selection and a move acceptance criterion, to ensure intensification and diversification [1]. Thus, rather than working directly on the problem's solutions and selecting one of them to proceed to the next step at each stage, hyper-heuristics operates on a low-level heuristic research space. The choice function is one of the hyper-heuristics that have proven their efficiency in solving combinatorial optimization problems [2–4]. At each iteration, the selection of heuristics is dependent on a score calculated by combining three different measures to guarantee both intensification and diversification for the heuristics choice process. The heuristic with the highest score is therefore chosen to be applied to the problem. Therefore, the key to the success of the choice function is to choose the correct weight parameters of its three measures. In this study, we make a state of the art in hyper-heuristic research and propose a new method that automatically controls these weight parameters based on the Boltzmann function. The results obtained from its application on five problem domains are compared with those of the standard, modified choice function proposed by Drake et al. [2,3].
49
Drake, John H., Ender Özcan i Edmund K. Burke. "A Case Study of Controlling Crossover in a Selection Hyper-heuristic Framework Using the Multidimensional Knapsack Problem". Evolutionary Computation 24, nr 1 (marzec 2016): 113–41. http://dx.doi.org/10.1162/evco_a_00145.
Pełny tekst źródłaStreszczenie:
Hyper-heuristics are high-level methodologies for solving complex problems that operate on a search space of heuristics. In a selection hyper-heuristic framework, a heuristic is chosen from an existing set of low-level heuristics and applied to the current solution to produce a new solution at each point in the search. The use of crossover low-level heuristics is possible in an increasing number of general-purpose hyper-heuristic tools such as HyFlex and Hyperion. However, little work has been undertaken to assess how best to utilise it. Since a single-point search hyper-heuristic operates on a single candidate solution, and two candidate solutions are required for crossover, a mechanism is required to control the choice of the other solution. The frameworks we propose maintain a list of potential solutions for use in crossover. We investigate the use of such lists at two conceptual levels. First, crossover is controlled at the hyper-heuristic level where no problem-specific information is required. Second, it is controlled at the problem domain level where problem-specific information is used to produce good-quality solutions to use in crossover. A number of selection hyper-heuristics are compared using these frameworks over three benchmark libraries with varying properties for an NP-hard optimisation problem: the multidimensional 0-1 knapsack problem. It is shown that allowing crossover to be managed at the domain level outperforms managing crossover at the hyper-heuristic level in this problem domain.
50
Seipp, Jendrik, i Malte Helmert. "Diverse and Additive Cartesian Abstraction Heuristics". Proceedings of the International Conference on Automated Planning and Scheduling 24 (11.05.2014): 289–97. http://dx.doi.org/10.1609/icaps.v24i1.13639.
Pełny tekst źródłaStreszczenie:
We have recently shown how counterexample-guided abstraction refinement can be used to derive informative Cartesian abstraction heuristics for optimal classical planning. In this work we introduce two methods for producing diverse sets of heuristics within this framework, one based on goal facts, the other based on landmarks. In order to sum the heuristic estimates admissibly we present a novel way of finding cost partitionings for explicitly represented abstraction heuristics. We show that the resulting heuristics outperform other state-of-the-art abstraction heuristics on many benchmark domains.