Heuristic

Heuristics ( altgr. εὑρίσκω heurisko - I find to heuriskein - find (on ), discover ) is the art to arrive at good solutions with limited knowledge ( " incomplete information " ) and little time. It describes an analytical approach taken in the limited knowledge about a system by means of conjectures conclusions, statements about the system. The resulting inferred statements may differ from the optimal solution. By comparing with an optimal solution, the quality of the heuristic can be determined.

Known heuristics include trial and error ( trial and error ), and the process of elimination. Heuristic methods are based on experiences; they can also be based on the "wrong" experiences (eg, distorted perception, spurious correlation ).

  • 3.1 René Descartes
  • 3.2 Joachim Jungius
  • 3.3 Friedrich Schleiermacher
  • 3.4 Bernard Bolzano
  • 3.5 Leonhard Euler
  • 3.6 George Pólya
  • 5.1 Economics
  • 5.2 Philosophy
  • 5.3 Psychology 5.3.1 Psychology of Perception
  • 5.3.2 psychology of thinking

Development of heuristics

Pappus in antiquity

First approaches in the 4th century by the Greek mathematician Pappus of Alexandria. Pappus developed the following method:

Algorithmic tradition

Al- Khwarizmi

Al- Khwarizmi, who lived about 830, described algorithmic methods as they had already been developed in Persia. In the Middle Ages, the work was translated into Latin ( algoritmi de numero Indorum ). So, from the name al Khovarezmi the pseudo Greek term algorithmos.

Ramon Lull and Athanasius Kircher

Ramon Lull (1235-1313), a Catalan philosopher and theologian with Arabic language skills, constructed a mechanical- combinatorial arrangement of movable discs which should make it possible to win all sorts of judgments and truths. The approach here brought into solution pedigree with three decision levels of nine choices opened naturally only a finite number of combinations. The ars combinatoria of Lull is limited to 93 = 729 choices. A direct sequel, the ideas Lull ' Athanasius Kircher in writing Ars magna sciendi immersive combinatoria ( 1669) to derive all possible and valid inferential and truths in a mechanical way by using the combinatorics of a system of basic concepts. The combination of the total letters of the alphabet with Zahlenpermutationen results in other ways than just nine symbolic of Lully letters: B, C, D, E, F, G, H, I, K ( see Fig: ars magna, Fig.1). Thus one finds in him the Permutationsreihe from ten with the number 3.6288 million at the letter K ( as in Stéphane Mallarmé ( 1842-1898 ), a writer of the 19th century, whose poems are the major works of symbolism ). However, this method ends in a finite number of possibilities. Worth reading in this context, the essay is an invitation to a poetry - vending machine by Hans Magnus Enzensberger.

Gottfried Wilhelm Leibniz

The origin of the abacus, the sprocket, hand sketch of Leibniz

1990 Replica of the Dresden Leibniz's calculating machine

Gottfried Wilhelm Leibniz postulated in 1666 by analogy to Lull the ars combinatoria through which you can gain all the knowledge on algorithmic way. Unlike Lull and following René Descartes all terms should be reduced to its elemental core; then one could - through their combination - to get all possible term compositions. Due to the shortcomings of the language has been a translation into an artistic language that carried Characteristica universalis, a development of Mathesis universalis. The same - translating into an artificial universal language plan, Athanasius Kircher had already in 1663 requested in the Polygraphia nova and also created one.

Example:

  • Illustration of basic terms by primes Creatures = 2; endowed with reason = 3
  • Mapping of complex terms on products of primes Man = rational animal = 3 × 2 = 6

In contrast to Descartes discussion of the heuristics ' closed conception Leibniz was ' only survived in fragments. He distinguished between the ars iudicandi, art, to judge the truth of statements, and the ars inveniendi, the pure art of discovery. 1673 presented Gottfried Wilhelm Leibniz developed by him before a season rolling machine of the Royal Society in London.

Lord Francis Bacon

Lord Francis Bacon (1561-1626) called for in his work Novum Organon a development of the heuristic. He describes the method of induction as the true path that no one yet tried. The latter is not true: Aristotle has the inductive method very well used; this was followed by natural philosophers in Alexandria, Arab thinkers and humanists.

Fritz Zwicky

As a further development of the algorithmic tradition is conceived Fritz Zwicky (1898-1974), a Swiss- American physicist and astronomer, in addition to his astronomical work a methodology to develop ideas into concrete products; see morphological box.

Heuristic tradition or classical heuristics

René Descartes

René Descartes (1596-1650) developed in 1637 with his Discours de la méthode an early methodology, the multiple is based on the ability of intuition. With their help, as Descartes, man instantly establishes the truth of simple statements such as " A triangle has three sides." The method itself is essentially to complex problems to disassemble so that its individual elements qua intuition can be recognized as true.

Joachim Jungius

Joachim Jungius (1587-1657) was probably the first time used the term heuristic and saw in the heuristic knowledge of the highest level of knowledge, because they have unresolved problems and new method for object.

Friedrich Schleiermacher

Friedrich Schleiermacher (1768-1834) postulated the first time the heuristic as an independent science in addition to the logic. Instead of abstract objective a concrete mind practice should occur. Schleiermacher defined heuristics as a conscious, art excessive intellectual work to find new insights and knowledge contexts. According to Schleiermacher, the cognitive process decomposes at the heuristics in two stages:

The decisive factor here is the conscious implementation of the method, since escape unconscious and random solutions to empirical testing.

Bernard Bolzano

Bernard Bolzano (1781-1848) sat on the systematization of methods to actually work out the available options for the logical addressing specified issues in the respective given knowledge situation and justified. Arbitrary thinking, its finding a solution is never completely determined by the laws of logic, should be guided by systematically arranged compilation and clear presentation in the scientific practice of applied methods. The methods described problem of Bolzano represents the most comprehensive and most unified representation of heuristic methods in the older literature

Leonhard Euler

The mathematician Leonhard Euler (1707-1783) created, among other things, the basis for the efficient solution of the problem of a Salesman ( TSP), see also MST heuristic, Christofides heuristic k- opt heuristic.

George Pólya

Many well-known statements on heuristics in mathematics in particular made ​​the Hungarian mathematician and writer George Pólya. In his series From solving mathematical problems he dealt intensively problem-solving strategies using heuristic methods.

Modern approaches

From 1964, the development and application of methods system of systematic heuristics was operated to improve the mental work in the areas of research and development in the GDR, inter alia, by Johannes Müller. The Russian variant of systematic heuristics is called TRIZ.

Qualitative heuristic is a designed by Gerhard Kleining sociological and psychological methodology that has the "development and application of discovery procedures in rule guided shape " to the object.

The development of punch card technology from about 1900 to about 1960 ( see below ) and the computerized since the 1950s contributed significantly to the fact that scientists from different disciplines with the topic intensively employs heuristics (t ) s. For example, economists tried to develop techniques with which you can better plan based on company data. For this field of research, the term Operations Research (OR) is a naturalized. Goal of OR is the development and use of quantitative models and methods for decision support (see also Decision Support System). OR is a cross-sectional area between applied mathematics, economics and computer science.

Even before the First World War military of various countries had recognized the possibilities of quantitative planning, which provided the punch card technology:

  • The U.S. Army began in World War I punched cards logistics in a medical service.
  • Austria - Hungary produced the steel helmet model 1917 at Krupp Berndorfer metal goods factory. For statistical reliability of the design Kuk - medical reports were evaluated with Hollerith punch card technology.
  • In Poland, the subsidiary of IBM was called until 1938 » Polski Hollerith ," it reported on multitasking and had the inverse Polish notation potential for the development of computers.
  • There are reports of the use in the Czech Republic, Holland and Belgium in the alternative military nature ( pattern, convocation, etc.)

Main article: Automatic reporting

Areas of application

Economics

In the field of Operations Research heuristics are used when the amount of computation required in the decision-making process is too extensive or this the extent possible breaks (as in chess programs. ) The number is the reduced considered to be drawn options by seemingly hopeless variants excluding from the outset. Application areas are eg multiple container loading problems such as the loading of container ships etc.

A solution using heuristics is carried out, for example, the problem of a Salesman ( german Traveling Salesman Problem, TSP short ) or the ant algorithm. Further applications can be found in the swarm intelligence and Boids.

The alternative to heuristic method is the brute force method, in which all possible ways be expected without exception. The best known and simplest heuristic is to solve a problem using the " trial and error " ( English: by trial and error ).

Gerd Gigerenzer of the Max Planck Institute for Human Development showed in his 2007 book Gut Feelings on the basis of multiple repeated experiments after that a group of randomly selected passers-by who had accidentally called the name of the exchange operating company, a much higher " performance" achieved as a financial expert and stock market analysts compiled portfolio. The rule of thumb " Invest in what you know " has proven over a precipitated with large amounts of information decision as superior.

See in this context also behavioral economics.

Philosophy

In philosophy, this is called a heuristic approach especially when a known unit X is used due to their similarity to broaden the understanding or knowledge about an unknown unit Y and deepen. In this sense, parables, metaphors and even fables can be viewed as heuristic means to promote the realization process of a human.

For example, Plato's most famous work Politeia uses those heuristic means by not describing an ideal state as a model for actually existing states. Rather, it points to inferentially how things should be connected and how they interact, if one follows certain principles rigorously.

Psychology

In psychology, heuristics are simple, efficient rules that have been consolidated by evolutionary processes or have been learned. In particular they are used to explain assessments, decision-making and problem solving by humans in complex situations ( in which there is often a lack of information ).

In most cases, these heuristic approaches yield the expected result, and therefore lead to a satisfactory solution. However, it may lead to misjudgments in the application.

Psychology of Perception

The psychology of perception found numerous heuristics in the area of ​​object recognition in the visual perception in particular, play an important role. Here they are used by the brain to reconstruct the two-dimensional images on the retina of three-dimensional objects. How was the latest artificial intelligence research, the reconstruction is a tremendous achievement: Because the objects are often partially occluded. Or the causes of light-dark transitions - they are important for the recognition of object outlines ( " edge detection " ) - are ambiguous.

The most common so-called top-down methods are used in the interpretation of information, where missing image information is supplemented by memory. They enable the viewer to quickly recognize familiar objects and place them in an appropriate context. An example of this is the " light -up of heuristic ". This assumes the brain in case of doubt, that the light falls from above onto the scene and the objects cast shadows appropriate. These are " eliminated " in the edge detection. Other examples are provided by the laws of Gestalt psychology.

Since the methods used are only heuristics, they are susceptible to certain errors. These are evident in optical illusions.

Psychology of thinking

From the perspective of cognitive psychology provide judgment heuristics action options available, not only when the situation due to lack of information is difficult to assess, but also when the situation assessment of time or lack of motivation is incomplete.

The research in this area in particular have driven the psychologists Daniel Kahneman and Amos Tversky. Of them are well-known studies on frequently used heuristics, including, inter alia:

  • The availability heuristic
  • The representativeness heuristic
  • The anchor heuristic

Mathematics

In the mathematical sense of the term heuristic for two different types of procedures to solve mathematical problems used.

On one side are particularly simple but sometimes called leading heuristic method only very time consuming to solve. An example of this is the specific rates of zero points of a polynomial, by using the integer divisor of the polynomial coefficients from the lowest degree of the function to be tried.

On the other hand, especially in the optimization process opening heuristic methods, ie those methods that provide a feasible solution within a short time and without much effort. This so-called basic solution may be clarified by repeated applying the heuristic (in several iterations ). Nevertheless, the solution found is usually not the optimal solution. However, finding an optimal solution is not always practical or effective, especially for complex problems. An example of this is the minimum matrix method for determining a basic solution of the transport problem or the Savings algorithm.

Computer science

Come In computer science, as in mathematics, heuristic methods are used to obtain feasible solutions for a specific problem with low computational cost and short duration. Classical algorithms try to ensure on the one hand an optimal processing time and on the other hand, the optimum solution. Heuristic methods are used in finding solutions to the run-time optimization. Search in large trees ( branching rate and depth) are only made possible by heuristics. Thus, the breadth-first search takes on a tree with depth 15 and Verzeigungsrate 3 ~ 4 years. With a heuristic search this search can be processed within minutes / seconds. There are several heuristic algorithms such as in the informed search. For this purpose, it is attempted using estimates, " rules of thumb ", intuitive intelligent guessing - or generate additional auxiliary assumptions under a good solution without having to guarantee optimum properties. Known heuristic algorithms are about A * search, Simulated cooling and evolutionary algorithms in optimization. Also fuzzy rules, which play an important role in fuzzy logic, can be described as heuristic rules. A general method which is not bound to a specific problem will be referred to in this context as metaheuristic.

A heuristic in computer science is an evaluation. This review is determined by a calculation. This calculation is based on resources, monitoring, conjecture or guess. Heurisitiken serve to problem solving. e.g. in finding a heuristic is taken to a "good" way or to find a "good" solution. The review is only as good as the " estimate ". Heuristics are always to be used when an exact calculation of the optimal solution is impossible (eg non- polynominales problem, too little information, not feasible) or such -consuming that it is not worthwhile (eg all aircraft test to find the best aircraft ) to.

When virus scanners heuristic called the search for viruses on the basis of phenotypic characteristics. See also: antivirus heuristic #

Chemistry

In organic chemistry, heuristic methods may help in the understanding and classification of known reactions. This can be a help to new reactions and new substances predict.

Hypothesis Spurious relationship Greece Analysis Ramon Llull Pinwheel calculator Christofides algorithm East Germany The Republic (Plato) tenet Perceptual psychology Outline of object recognition Two-dimensional space Run time (program lifecycle phase) A* search algorithm Approximation algorithm Gottlob Frege Begriffsschrift Allen Newell Douglas Lenat Zeno.org
334751
de