Heuristic

from Wikipedia, the free encyclopedia

Heuristics ( old Gr . Εὑρίσκω heurísko "I find"; from εὑρίσκειν heurískein “ to find”, “discover”) describes the art of still arriving at probable statements or practicable solutions with limited knowledge ( incomplete information ) and little time. It describes an analytical procedure in which statements about the system are made with the help of presumptive conclusions with limited knowledge about a system . The conclusions drawn from this often deviate from the optimal solution. The quality of the heuristic can be determined by comparison with an optimal solution.

Known heuristics include trial and error (trial and error) , statistical analysis of random samples and the process of elimination . Heuristic procedures are based on experience; they can also be based on “wrong” experiences (e.g. distorted perception , sham correlation ).

Differentiation of terms

The difference between the heuristic and the approximation is that an approximation contains a quantifiable quality (i.e. a statement about the error to be expected).

The transition between heuristics and algorithms is fluid. Werner Stangl defines it as follows: An algorithm describes a systematic, logical rule or procedure that leads to the solution of a given problem. In contrast, there is the faster, but also more error-prone heuristic.

Development of the heuristic

Pappos in antiquity

The first approaches come from the 4th century by the Greek mathematician Pappos of Alexandria . Pappos developed the following method:

  1. Consider the problem solved;
  2. look for the solution by stepping backwards ( analysis ; working backwards );
  3. prove by stepping forward ( synthesis ; working forwards ) that this path leads to the solution.

Algorithmic tradition line

Al-Khwarizmi

Al-Chwarizmi on a 1983 Soviet Union postage stamp

Al-Chwarizmi , who lived around 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 ). This is how the pseudo-Greek term algorithmos emerged from the name al Khovarezmi .

Raimundus Lullus and Athanasius Kircher

Ramon Lull-Ars magna, Fig. 1

Raimundus Lullus (1235-1313), a Catalan philosopher and theologian with knowledge of the Arabic language, constructed a mechanical-combinatorial arrangement of movable disks that should make it possible to gain all possible judgments and truths. The solution tree introduced here with three decision levels, each with nine options, naturally only opens up a finite number of combinations. The ars combinatoria des Lullus is limited to 9 3 = 729 options. ( See Fig .: Ramon Lull-Ars Magna, Fig.1). Lullus' ideas found a direct continuation through the German Jesuit Athanasius Kircher in his work Ars magna sciendi sive combinatoria (1669), in order to derive all conceivable and valid conclusions and truths mechanically from a system of basic concepts with the help of combinatorics. The combination of the entire letters of the alphabet with number permutations results in other possibilities than the only nine symbolic letters of Lullus: B, C, D, E, F, G, H, I, K = Bonitas, Magnitudo, Duratio, Potentia, Cognitio, Voluntas, Virtus, Veritas, Gloria. From the combination of these principa absoluta and the principa relativa (Differences, Concordantia, Contrarietas, Principium, Medium, Finis, Majoritas, Aqualitas, Minoritas) all forms of beings should be able to be grasped according to Lull's view at the time. This is why Kircher has the permutation series of ten with the number 3,628,800 in the letter K.

In literature, Stéphane Mallarmé (1842–1898), a critic and poet of the 19th century, whose poems are considered major works of symbolism , dealt with the combinatorics of words. His fragmentary text work of art “Livre”, on which he worked for over 30 years, should offer the reader different readings and readings thanks to the diverse ways of combining the experimentally expanded book. But this method also ends in a finite number of possibilities. In this context, the article Invitation to a poetry machine by Hans Magnus Enzensberger is worth reading .

Lord Francis Bacon

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

Gottfried Wilhelm Leibniz

In 1666, Gottfried Wilhelm Leibniz postulated the ars combinatoria in analogy to Lullus , through which all knowledge can be obtained in an algorithmic way. In contrast to Lullus and based on René Descartes , all terms are to be reduced to their elementary core; then - through their combination - one can get all possible combinations of terms. Due to the inadequacy of the language, it must first be translated into an artificial language, the Characteristica universalis , a further development of the Mathesis universalis . The same thing - translation into an artificial, universal, planned language was what Athanasius Kircher had already requested in 1663 in the Polygraphia nova and had created one.

Example:

  • Mapping of basic terms using prime numbers
    Living being = 2; reasonably gifted = 3
  • Mapping complex terms to products of prime numbers
    Human = rational living being = 3 × 2 = 6

In contrast to Descartes' closed conception, Leibniz's analysis of heuristics has only been handed down in fragments. He differentiated between the ars iudicandi , the art of judging the truth of statements, and the ars inveniendi , the pure art of discovery. In 1673 Gottfried Wilhelm Leibniz presented a relay roller machine he had developed to the Royal Society in London.

Fritz Zwicky

As a further development of the algorithmic line of tradition, Fritz Zwicky (1898–1974), a Swiss-American physicist and astronomer, devised a method of developing concrete products from ideas in addition to his astronomical activities; see morphological box .

Heuristic tradition line or classical heuristics

René Descartes

René Descartes (1596–1650) developed an early methodology in 1637 with his Discours de la méthode , which is based several times on the faculty of intuition. With their help, according to Descartes, people instantly grasp the truth of the simplest of statements such as “a triangle has three sides”. The method itself essentially consists in breaking down complex problems in such a way that their individual elements can be recognized as true by intuition.

Joachim Jungius

Joachim Jungius (1587–1657) probably used the term heuristic for the first time and saw heuristic knowledge as the highest level of knowledge, since it deals with unsolved problems and new procedures.

Friedrich Schleiermacher

Friedrich Schleiermacher (1768–1834) first postulated heuristics as an independent science alongside logic. In place of the abstract goal, a concrete thought practice should take place. Schleiermacher defined heuristics as conscious, artistic, intellectual work to find new knowledge and contexts of knowledge. According to Schleiermacher, the knowledge process in the heuristic is divided into two stages:

  1. Concentration on the problem.
  2. Reference to the general context.

The decisive factor here is the conscious implementation of the process, since unconscious and random solutions evade empirical verification.

Bernard Bolzano

Bernard Bolzano (1781–1848) relied on the systematization of the methods in order to actually work out and justify the available possibilities for the logical approach to given problems in the given knowledge situation. Arbitrary thinking, whose solution finding is never completely determined by the laws of logic, should be guided by a systematically ordered compilation and clear presentation of methods used in scientific practice. The method problem described by Bolzano represents the most comprehensive and closed representation of heuristic methods in the older literature.

Leonhard Euler

The mathematician Leonhard Euler (1707–1783) laid the foundations for the efficient solution of the traveling salesman problem (TSP), see also MST heuristic , Christofides heuristic , k-opt heuristic .

George Pólya

George Pólya around 1973

The Hungarian mathematician and writer George Pólya in particular made many well-known statements about heuristics in mathematics . In his series On Solving Mathematical Problems , he deals intensively with problem-solving strategies using heuristic methods.

Modern approaches

From 1964 in the GDR a . a. by Johannes Müller the development and application of a method system, the systematic heuristics , in order to improve the intellectual work in the areas of research and development. The Russian variant of the systematic heuristic is called TRIZ .

Qualitative heuristics is a sociological and psychological methodology designed by Gerhard Kleining , which deals with the “development and application of discovery processes in a rule-based form”.

The development of punched card technology from around 1900 to around 1960 (see below) as well as EDP since the 1950s made a significant contribution to the fact that scientists from various disciplines are (are) intensely concerned with the topic of heuristics. For example, economists tried to develop techniques that could be used to better plan based on company data . The term Operations Research (OR) has become established for this research area . The aim 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, the military from various countries recognized the possibilities of quantitative planning offered by punched card technology:

Main article: Machine reporting

application areas

Economics

In the field of operations research , heuristic methods are used if the computational effort required in the decision-making process is too extensive or if it goes beyond the scope of what is possible (as is the case with chess programs). The number of options to be considered is reduced by using variants that appear hopeless excludes from the start. Areas of application are e.g. B. multiple container loading problems such as loading container ships etc., or multi-snapshots .

A solution by means of heuristics is carried out, for example, at the Traveling Salesman Problem (engl. Traveling Salesman Problem, short TSP) or also in ants algorithm . Other applications can be found in swarm intelligence and boids .

The alternative to heuristic methods is the brute force method , in which all possible options are calculated without exception. The best known and simplest heuristic is the solution of a problem by means of " trial and error " (English: by trial and error ).

In 2007, Gerd Gigerenzer from the Max Planck Institute for Human Development used experiments that were repeated several times to demonstrate in his book Bauchentscheidungen that a group of randomly selected street passers- by who happened to mention names of listed companies achieved a significantly higher "performance" than one from financial experts and stock market analysts. The rule of thumb “Invest in what you know” has proven to be superior to a decision made with a lot of information.

See also behavioral economics in this context .

philosophy

In philosophy , one speaks of a heuristic approach in particular when a known unit X is used due to its similarity to expand or deepen the understanding or knowledge of an unknown unit Y. In this sense, parables , metaphors, and even fables can be viewed as heuristic means to promote a person's cognitive process.

For example, Plato's best-known work Politeia uses these heuristic means by not describing an ideal state as a model for actually existing states. Rather, it shows conclusively how things should be connected and how they interact if certain principles are rigorously followed.

psychology

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

In most cases, these heuristics produce the expected result and therefore lead to satisfactory problem solving. However, misjudgments can occur during application.

Perceptual Psychology

The cognitive psychology found numerous heuristics in particular in the field of object recognition in visual perception play an important role. Here they are used by the brain to reconstruct three-dimensional objects from the two-dimensional images on the retina . As the artificial intelligence research has shown at the latest , the reconstruction is an enormous achievement, because the objects are often partially covered or the causes of light-dark transitions - they are important for recognizing object outlines (" edge detection ") - are ambiguous.

So-called top-down methods are most often used to interpret the information , in which missing image information is added from memory. They enable the viewer to quickly recognize known objects and place them in a suitable context. One example of this is the "light-from-above heuristic". In case of doubt, the brain assumes that the light falls onto the scene from above and the objects cast corresponding shadows. These are "deducted" during edge detection. The laws of Gestalt psychology provide further examples .

Since the methods used are only heuristics, they are prone to certain errors. These become obvious with optical illusions .

Thought psychology

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

The psychologists Daniel Kahneman and Amos Tversky in particular advanced research in this area . They have made well-known studies on commonly used heuristics, including

Daniel Kahneman received the Nobel Prize in Economics in 2002 "for introducing insights into economics from psychological research, particularly with regard to assessments and decisions in the case of uncertainty". His work gained notoriety outside of the scientific community through the publication of his book, Fast Thinking, Slow Thinking (English: Thinking, Fast and Slow ).

mathematics

In the mathematical sense, the term heuristic is used for two different types of procedures for solving mathematical problems.

On the one hand, heuristic methods that are particularly simple but sometimes only take a long time to solve are mentioned. An example of this is the targeted guessing of zeros of a polynomial function by trying out the integer divisors of the coefficients of the polynomial of the smallest degree of the function .

On the other hand, especially in the Optimization opening procedure heuristic methods that provide a feasible solution so those methods that big in a short time and without effort. This so-called basic solution can be made more precise by applying the heuristic several times (in several iterations). However, the solution found is usually not the optimal solution. However, finding an optimal solution, especially for complex problems, is not always practical or effective. An example of this is the matrix minimum method for determining a basic solution to the transport problem or the savings algorithm .

Computer science

In computer science , similar to mathematics, heuristic methods are used in order to obtain permissible solutions for a specific problem with little computational effort and a short duration . Classical algorithms try to guarantee the optimal computing time on the one hand and the optimal solution on the other. Heuristic procedures are used to optimize runtime when finding a solution. Searches in large trees (branching rate and depth) are only possible through heuristics. For example, the breadth-first search for a tree with depth 15 and branching rate 3 can take a long time. With a heuristic search, this search can be processed much faster. There are various heuristic algorithms, e.g. B. in the informed search. For this purpose, attempts are made to generate a good solution with the help of estimates, “rules of thumb”, intuitive-intelligent guessing or additional auxiliary assumptions, without having to guarantee optimal properties. Well-known heuristic algorithms are A * -Search , Simulated Cooling and Evolutionary Algorithms in Optimization . Fuzzy rules, which play an important role in fuzzy logic , can also be referred to as heuristic rules. A fundamental procedure that is not tied to a specific problem is referred to as metaheuristic in this context .

A heuristic in computer science is an evaluation that is determined by a calculation. This calculation is based on guessing, observing, guessing, or guessing. Heuristics are used to solve problems, e.g. For example, a heuristic is used in the search to find a “good” way or a “good” solution. The rating is only as good as the "estimate". Heuristics are always used when an exact calculation of the optimal solution is impossible (e.g. non-polynomial problem, too little information, not realizable) or so time-consuming that it is not worthwhile (e.g. testing all aircraft to find the best aircraft).

In virus scanners, heuristics describe the search for viruses on the basis of typical characteristics.

chemistry

In organic chemistry , heuristic methods can help in understanding and classifying known reactions. This can help to predict new reactions and new substances.

See also

literature

  • Athanasius Kircher : Ars magna sciendi sive combinatoria. 1669.
  • Gottfried Wilhelm Leibniz : De Arte combinatoria. 1666.
  • Friedrich Schleiermacher All works. Berlin 1834–1864 (Section I: On Theology, 11 volumes, 1835–1864, two planned volumes have not been published; Section II: Sermons, 10 volumes, 1834–1856; Section III: On Philosophy, 9 volumes, 1835–1862) (almost completely in google books, including the dialectic , ed. Jonas from 1839)
  • George Pólya : Mathematics and plausible reasoning (=  science and culture . Band 14 ). 3. Edition. tape 1 : Induction and Analogy in Mathematics . Birkhäuser Verlag, 1998, doi : 10.1007 / 978-3-0348-9166-0 .
  • George Pólya: Mathematics and plausible reasoning (=  science and culture . Band 15 ). 2nd Edition. tape 2 : Types and structures of plausible inference . Birkhäuser Verlag, 1975, doi : 10.1007 / 978-3-0348-7671-1 .
  • Gerd Gigerenzer , Peter M. Todd: Simple Heuristics That Make Us Smart (Evolution and Cognition) . Oxford University Press, New York 2000, ISBN 0-19-972924-7 .
  • Gerd Gigerenzer: The basics of skepticism: About the correct handling of numbers and risks (=  BvT . Volume 41 ). Bvt Berliner Taschenbuch Verlag, 2004, ISBN 3-8333-0041-8 (Original title: How to Reckon With Risk: From Innumeracy to Insight .).
  • Gerd Gigerenzer: Gut decisions: The intelligence of the unconscious and the power of intuition . C. Bertelsmann Verlag, New York 2008, ISBN 978-3-570-00937-6 (Original title: Gut Feelings .).
  • Gottlob Frege : Conceptual writing . and other essays.
  • Arnd Bogatzki: Factory planning: Process for optimizing machine installation . Roderer, Regensburg 1998, ISBN 3-89073-234-8 .
  • Norbert Bischof : Structure and meaning . 2nd Edition. Huber, Bern 1998, ISBN 3-456-83080-7 .
  • Allen Newell : Human Problem Solving . Prentice-Hall, Englewood Cliffs, NJ 1972, ISBN 0-13-445403-0 .
  • Douglas B. Lenat : Automated Mathematician.
  • J. Müller: Systematic Heuristics .
  • Amos Tversky , Daniel Kahneman : Judgment under uncertainty - Heuristics and biases. In: Science. 185, 1974, pp. 1124-1131.
  • H. Streim: Heuristic solution methods - attempt at an explanation of terms. In: Journal for Operations Research. Volume 19, 1975, pp. 143-162.

Web links

Wiktionary: Heuristics  - explanations of meanings, word origins, synonyms, translations

Individual evidence

  1. ^ G. Gigerenzer and PM Todd with the ABC Research Group: Simple heuristics that make us smart. Oxford University Press, New York 1999.
  2. Ulf Pillkahn: Innovations between planning and chance: building blocks of a theory of conscious irritation. Books on Demand 2012, ISBN 978-3-8448-1737-9 , p. 170.
  3. Heuristics. (PDF) In: zaik.uni-koeln.de. P. 2 , accessed on July 19, 2015 .
  4. Werner Stangl : Algorithm. In: lexikon.stangl.eu. Retrieved July 19, 2015 .
  5. Mannerism in Literature. Speech alchemy and esoteric combination art . hockebooks, 2016, ISBN 978-3-95751-119-5 ( books.google.de ).
  6. ^ History of Computers and Computing, Dreamers, Athanasius Kircher.
  7. Christoph Benjamin Schulz: Poetiken des sheets . Georg Olms Verlag - Language Arts & Disciplines, Hildesheim September 1, 2015, p. 279 ff .
  8. ^ Virginia A. La Charité: Mallarmé's Livre: The Graphomatics of the Text . In: Symposium: A Quarterly Journal in Modern Literatures . tape 34 , no. 3 , September 4, 2013, p. 249-259 , doi : 10.1080 / 00397709.1980.10733451 .
  9. ^ Gustav René Hocke : Mannerism in literature. Speech alchemy and esoteric combination art. Reinbek near Hamburg 1969 (rde 82/83, first 1959).
  10. ^ Hans Magnus Enzensberger : Invitation to a poetry machine. June 2002, accessed on August 6, 2009 (It is copyright © 1974, 1999, 2002 Hans Magnus Enzensberger.): “1. Description, 2. Theory, 3. Extensions, 4. Technical Appendix "
  11. See also Frances A. Yates: The Art of Ramon Lull. In: Journal of the Warburg and Courtauld Institutes. Volume 17, No. 1/2, 1954, pp. 115-173.
  12. ^ German translation of the Novum Organon .
  13. ^ Friedrich Kirchner , Carl Michaëlis et al .: Dictionary of basic philosophical terms. 1907, p. 262–263 ( zeno.org [accessed August 6, 2009]).
  14. Ludolf von Mackensen : On the history and development of the first digital 4-species calculating machine by Gottfried Wilhelm Leibniz. In: Studia Leibnitiana. Supplements. 2 (1969), pp. 34-68.
  15. Nikolaus Joachim Lehmann : New experiences on the functionality of Leibniz 'calculating machine. In: Studia Leibnitiana. 25: 174-188 (1993).
  16. Jan-Willem Liebezeit: Leibniz calculating machines. University of Jena, July 2004, accessed on November 16, 2012 (comprehensive information on Leibniz's calculating machines, functionality and whereabouts): "Person, curriculum vitae, fields of activity and some thoughts Calculating machines, historical overview, inventions incidentally, The younger machine: rediscovery, Lehmann, functionality, Locations, sources "
  17. Bolzano's Logic. Stanford Encyopedia of Philosophy, September 23, 2007, accessed August 4, 2009 (English, extensive literature).
  18. storyal.de .
  19. portal.acm.org
  20. turbulence.org/spotlight/thinking/chess.html .
  21. Article of the distance university in Hagen (PDF as download on the page)
  22. ^ Nicole Graulich, Henning Hopf , Peter R. Schreiner: Heuristic thinking makes a chemist smart. In: Chemical Society Reviews . 39, 2010, pp. 1503-1512.