摘要 :
In the field of heuristic search it is usually assumed that admissible heuristics are consistent, implying that consistency is a desirable attribute. The term "inconsistent heuristic" has, at times, been portrayed negatively, as s...
展开
In the field of heuristic search it is usually assumed that admissible heuristics are consistent, implying that consistency is a desirable attribute. The term "inconsistent heuristic" has, at times, been portrayed negatively, as something to be avoided. Part of this is historical: early research discovered that inconsistency can lead to poor performance for A* (nodes might be re-expanded many times). However, the issue has never been fully investigated, and was not re-considered after the invention of IDA*. This paper shows that many of the preconceived notions about inconsistent heuristics are outdated. The worst-case exponential time of inconsistent heuristics is shown to only occur on contrived graphs with edge weights that are exponential in the size of the graph. Furthermore, the paper shows that rather than being something to be avoided, inconsistent heuristics often add a diversity of heuristic values into a search which can lead to a reduction in the number of node expansions. Inconsistent heuristics are easy to create, contrary to the common perception in the AI literature. To demonstrate this, a number of methods for achieving effective inconsistent heuristics are presented. Pathmax is a way of propagating inconsistent heuristic values in the search from parent to children. This technique is generalized into bidirectional pathmax (BPMX) which propagates values from a parent to a child node, and vice versa. BPMX can be integrated into IDA* and A*. When inconsistent heuristics are used with BPMX, experimental results show a large reduction in the search effort required by IDA*. Positive results are also presented for A* searches.
收起
摘要 :
Additive ensembles of admissible heuristics constitute the most general form of exploiting the individual strengths of numerous admissible heuristics in optimal planning. However, the same set of heuristics can be additively compo...
展开
Additive ensembles of admissible heuristics constitute the most general form of exploiting the individual strengths of numerous admissible heuristics in optimal planning. However, the same set of heuristics can be additively composed in infinitely many ways and the quality of the resulting heuristic estimate depends directly on the choice of the composition. Focusing on abstraction heuristics, we describe a procedure that takes a deterministic planning problem, a forward-search state, and a set of abstraction-based admissible heuristics, and derives an optimal additive composition of these heuristics with respect to the given state. Most importantly, we show that this procedure is polynomial-time for arbitrary sets of all abstraction heuristics with which we are acquainted, including explicit abstractions such as pattern databases (regular or constrained) and merge-and-shrink, and implicit abstractions such as fork-decomposition and abstractions based on tractable constraint optimization over tree-shaped constraint networks.
收起
摘要 :
Accessibility heuristics have been developed to complement accessibility guidelines. The use of Web accessibility heuristics in heuristic evaluations considers a greater range of special needs, such as visual impairments to cognit...
展开
Accessibility heuristics have been developed to complement accessibility guidelines. The use of Web accessibility heuristics in heuristic evaluations considers a greater range of special needs, such as visual impairments to cognitive disabilities. Key advantages of heuristics are conciseness, memorability, meaningfulness and insight. The heuristics allow evaluators to understand effectively which areas of a site have accessibility issues and provide useful insight into how to create a solution. However, the heuristics will not tell evaluators whether a Web site conforms to legislation. Studies have confirmed the view that while heuristics do not substitute for expertise, they do act to cue the deeper body of knowledge defined by the guidelines. It is essential that evaluators receive accessibility education before completing a heuristic evaluation using the accessibility heuristics.
收起
摘要 :
We investigate the use of machine learning to create effective heuristics for search algorithms such as IDA~* or heuristic-search planners such as FF. Our method aims to generate a sequence of heuristics from a given weak heuristi...
展开
We investigate the use of machine learning to create effective heuristics for search algorithms such as IDA~* or heuristic-search planners such as FF. Our method aims to generate a sequence of heuristics from a given weak heuristic ho and a set of unsolved training instances using a bootstrapping procedure. The training instances that can be solved using ho provide training examples for a learning algorithm that produces a heuristic hi that is expected to be stronger than ho. If ho is so weak that it cannot solve any of the given instances we use random walks backward from the goal state to create a sequence of successively more difficult training instances starting with ones that are guaranteed to be solvable by ho. The bootstrap process is then repeated using h, in lieu of h_(i-1) until a sufficiently strong heuristic is produced. We test this method on the 24-sliding-tile puzzle, the 35-pancake puzzle, Rubik's Cube, and the 20-blocks world. In every case our method produces a heuristic that allows IDA~* to solve randomly generated problem instances quickly with solutions close to optimal. The total time for the bootstrap process to create strong heuristics for these large state spaces is on the order of days. To make the process effective when only a single problem instance needs to be solved, we present a variation in which the bootstrap learning of new heuristics is interleaved with problem-solving using the initial heuristic and whatever heuristics have been learned so far. This substantially reduces the total time needed to solve a single instance, while the solutions obtained are still close to optimal.
收起
摘要 :
Non-Euclidean traveling salesman problem (TSP) construction heuristics, and especially asymmetric TSP construction heuristics, have been neglected in the literature by comparison with the extensive efforts devoted to studying Eucl...
展开
Non-Euclidean traveling salesman problem (TSP) construction heuristics, and especially asymmetric TSP construction heuristics, have been neglected in the literature by comparison with the extensive efforts devoted to studying Euclidean TSP construction heuristics. This state of affairs is at odds with the fact that asymmetric models are relevant to a wider range of applications, and indeed are uniformly more general that symmetric models. Moreover, common construction approaches for the Euclidean TSP have been shown to produce poor quality solutions for non-Euclidean instances. Motivation for remedying this gap in the study of construction approaches is increased by the fact that such methods are a great deal faster than other TSP heuristics, which can be important for real time problems requiring continuously updated response. The purpose of this paper is to describe two new construction heuristics for the asymmetric TSP and a third heuristic based on combining the other two. Extensive computational experiments are performed for several different families of TSP instances, disclosing that our combined heuristic clearly outperforms well-known TSP construction methods and proves significantly more robust in obtaining (relatively) high quality solutions over a wide range of problems.
收起
摘要 :
The widespread team project method is more effective when used in conjunction with heuristic methods. The large number of heuristic methods and the variety of their descriptions create a problem to prepare students for the use of ...
展开
The widespread team project method is more effective when used in conjunction with heuristic methods. The large number of heuristic methods and the variety of their descriptions create a problem to prepare students for the use of these methods. A method based on two areas of knowledge – heuristics and psychology – is proposed. The personality types of students STEM specialties according to Myers-Briggs are considered. An analysis of interaction of personality types from the point of view of application of heuristic methods is performed. The survey for percentage composition personality types of student STEM specialties was carried out and predominantly types of student STEM specialties was determine. Heuristic methods are consideration as sum of heuristic techniques and procedure. It is shown that many methods involve the same heuristic techniques and differ only in procedures. A generalized method has been developed that allows replacing most of the methods based on collective discussion. This method included five heuristic techniques: collective discussion, pause between the presentation of ideas and their criticism, random associations, analogy, expert evaluation, using a matrix. This method is mainly aimed at teaching students of STEM specialties. A project team is formed to use the method. The composition of this team includes a discussion group, a criticism group and a expert evaluation group. These groups are formed in accordance with the personal types of participants. The method includes an algorithm for team members to interact when using heuristic techniques and procedures.
收起
摘要 :
In this paper we consider a common optimization problem faced by a printing company while designing masters for advertisement material. A printing company may receive from various customers, advertisements for their products and s...
展开
In this paper we consider a common optimization problem faced by a printing company while designing masters for advertisement material. A printing company may receive from various customers, advertisements for their products and services and their demand is for a specified number of copies to be printed. In a particular case, the printer receives these orders to be delivered next week from the customers, until the Thursday of a week. By Monday the printed copies have to be delivered to the customers. These advertisement items of the various customers are to be printed on large sheets of papers of specified standard sizes. The size is called a k-up if k items can be printed on one sheet. It is a given constraint that only items of the same size can be loaded on a master. This constraint results in a decomposition of the original problem of designing masters into many sub-problems, one for each size. The objective is to minimize the number of masters required while meeting the requirements of the customers. We formulate this optimization problem mathematically, discuss the computational issues and present some heuristic approaches for solving the problem.
收起
摘要 :
In this paper we consider a common optimization problem faced by a printing company while designing masters for advertisement material. A printing company may receive from various customers, advertisements for their products and s...
展开
In this paper we consider a common optimization problem faced by a printing company while designing masters for advertisement material. A printing company may receive from various customers, advertisements for their products and services and their demand is for a specified number of copies to be printed. In a particular case, the printer receives these orders to be delivered next week from the customers, until the Thursday of a week. By Monday the printed copies have to be delivered to the customers. These advertisement items of the various customers are to be printed on large sheets of papers of specified standard sizes. The size is called a k-up if k items can be printed on one sheet. It is a given constraint that only items of the same size can be loaded on a master. This constraint results in a decomposition of the original problem of designing masters into many sub-problems, one for each size. The objective is to minimize the number of masters required while meeting the requirements of the customers. We formulate this optimization problem mathematically, discuss the computational issues and present some heuristic approaches for solving the problem.
收起
摘要 :
Many areas of computer science require answering questions about reachability in compactly described discrete transition systems.Answering such questions effectively requires techniques to be able to do so without building the ent...
展开
Many areas of computer science require answering questions about reachability in compactly described discrete transition systems.Answering such questions effectively requires techniques to be able to do so without building the entire system. In particular, heuristic search uses lower-bounding ("admissible") heuristic functions to prune parts of the system known to not contain an optimal solution. A prominent technique for deriving such bounds is to consider abstract transition systems that aggregate groups of states into one. The key question is how to design and represent such abstractions. The most successful answer to this question are pattern databases, which aggregate states if and only if they agree on a subset of the state variables. Merge-and-shrink abstraction is a new paradigm that, as we show, allows to compactly represent a more general class of abstractions, strictly dominating pattern databases in theory. We identify the maximal class of transition systems, which we call factored transition systems, to which merge-and-shrink applies naturally, and we show that the well-known notion of bisimilarity can be adapted to this framework in a way that still guarantees perfect heuristic functions, while potentially reducing abstraction size exponentially. Applying these ideas to planning, one of the foundational subareas of artificial intelligence, we show that in some benchmarks this size reduction leads to the computation of perfect heuristic functions in polynomial time and that more approximate merge-and-shrink strategies yield heuristic functions competitive with the state of the art.
收起
摘要 :
Although they are simple techniques from the early days of timetabling research, graph colouring heuristics are still attracting significant research interest in the timetabling research community. These heuristics involve simple ...
展开
Although they are simple techniques from the early days of timetabling research, graph colouring heuristics are still attracting significant research interest in the timetabling research community. These heuristics involve simple ordering strategies to first select and colour those vertices that are most likely to cause trouble if deferred until later. Most of this work used a single heuristic to measure the difficulty of a vertex. Relatively less attention has been paid to select an appropriate colour for the selected vertex. Some recent work has demonstrated the superiority of combining a number of different heuristics for vertex and colour selection. In this paper, we explore this direction and introduce a new strategy of using linear combinations of heuristics for weighted graphs which model the timetabling problems under consideration. The weights of the heuristic combinations define specific roles that each simple heuristic contributes to the process of ordering vertices. We include specific explanations for the design of our strategy and present the experimental results on a set of benchmark real world examination timetabling problem instances. New best results for several instances have been obtained using this method when compared with other constructive methods applied to this benchmark dataset.
收起
原文获取