Why are heuristics problematic

Are heuristics the better algorithms? An attempt to answer using the example of the Traveling Salesman Problem (TSP)

Datafication and Big Data pp 55-93 | Cite as

  • Christian Wadephul
Chapter
First Online:
Part of the Anthropologie - Philosophy of Technology - Society book series (ATG)

Summary

Algorithms are as diverse as the applications that make them possible: from autonomous driving cars, language processing and text generation to DNA decryption and analysis of stock markets, there are thousands of algorithms that control digital processes (programs). Whenever software reacts to an input, the reaction (output) has been calculated by algorithms. 'Algos', as they are almost affectionately known in specialist circles, are digitally formalizable instructions that make computers run. The methodological repertoire of computer science has grown considerably in scope and complexity in recent years. To the elementary and exact algorithmic Methods are heuristic Strategies have been added that are not always optimal, but more efficient and often provide solutions for the first time in the case of complex problems. The contribution would like - v. a. with reference to the Traveling Salesman Problem (TSP) - show to what extent heuristics even have to be viewed as better algorithms.

This is a preview of subscription content, log in to check access.

literature

  1. al-Hwārizmī, Muhammad Ibn-Mūsā. (1997). The oldest Latin script about Indian arithmetic according to al-Hwārizmī. In v. Menso Folkerts, Paul Kunitzsch (eds.). Munich: Publishing house of the Bavarian Academy of Sciences.Google Scholar
  2. Anders, G. (1956). The antiquity of man (Vol. 1). Munich: Beck.Google Scholar
  3. Applegate, D., et al. (2009). Certification of an optimal TSP tour through 85,900 cities. Operation Research Letters,37(1), 11–15. CrossRefGoogle Scholar
  4. Bächle, T. (2015). The myth of the algorithm. The fabrication of the computerizable human being. Wiesbaden: Springer VS.Google Scholar
  5. Black, E. (2001). IBM and the Holocaust: The strategic alliance between Nazi Germany and America’s most powerful corporation. New York: Three Rivers Press.Google Scholar
  6. Blischke, W. (2014). Bugs, Big Data and the unlinkable. A conversation with Peter Bittner, Stefan Hügel and Julia Stoll from the FIfF. testcard,24, 62–72.Google Scholar
  7. Christofides, N. (1976). Worst-case analysis of a new heuristic for the traveling salesman problem. Report 388. Graduate School of Industrial Administration, Carnegie Mellon University.Google Scholar
  8. Cotta, C., Sevaux, M., & Sörensen, K. (Eds.). (2008). Adaptive and multilevel metaheuristics. Berlin: Springer.Google Scholar
  9. Commis-Voyageur. (1832). The traveling salesman - How he should be and what he has to do in order to receive orders and to be certain of a happy success in his business. Ilmenau: Voigt.Google Scholar
  10. Cook, W. J. (2012). In pursuit of the traveling salesman Mathematics at the limits of computation. New Jersey: Princeton University Press.Google Scholar
  11. Corne, D., Lones, M. A. (2018). Evolutionary Algorithms. In Martí et al., Pp. 409-430.Google Scholar
  12. Dantzig, George B. (1982). Reminiscences about the origins of linear programming. Operations Research Letters,1, 43–48. CrossRefGoogle Scholar
  13. Domschke, W., & Scholl, A. (2006). Heuristic procedures. Jena: Faculty of Economics, Friedrich Schiller University Jena.Google Scholar
  14. Euler, L. (1741). Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum Petropolitanae, 8, 128-40.Google Scholar
  15. Fischetti, M., Fischetti, M. (2018). Matheuristics. In Martí et al., Pp. 121-154.Google Scholar
  16. Fowler, D., & Robson, E. (1998). Square root approximations in old babylonian mathematics. Historica Mathematica,25, 366–378. CrossRefGoogle Scholar
  17. García-Martínez, C., Rodriguez, F. J., Lozano, M. (2018). Genetic Algorithms. In Martí et al., Pp. 431-464.Google Scholar
  18. Gigerenzer, G. (2007). Gut decisions. The intelligence of the unconscious and the power of intuition. Munich: Bertelsmann.Google Scholar
  19. Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computing. Operations Research,13(5), 533-549. Google Scholar
  20. Goldberg, D. E. (1989). Genetic Algorithms in Search Optimization and Machine Learning. Alabama: Addison Wesley.Google Scholar
  21. Gonçalves, J. F., Resende, M. G. C. (2018). Random-Key Genetic Algorithms. In Martí et al., Pp. 703-716. Google Scholar
  22. Grandori, A. (2015). Heuristics as Methods. Validity, Reliability and Velocity. In Ippoliti, E. (Ed.), Heuristic reasoning. (Pp. 147-161). Cham: Springer.Google Scholar
  23. Gutmann, M., & Knifka, J. (2015). Biomorphic and technomorphic metaphors - Some arguments why robots don’t evolve, why computing is not organic and why adaptive technologies are not intelligent. In M. Decker, M. Gutmann, & J. Knifka (Eds.), Evolutionary Robotics, Organic Computing and Adaptive Ambience. Epistemological and Ethical Implications of Technomorphic Descriptions of Technologies (Pp. 53-80). Zurich: LIT.Google Scholar
  24. Helsgaun, K. (2000). An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research,126, 103–130. CrossRefGoogle Scholar
  25. Hochstättler, W. (2017). Linear optimization. Berlin: Springer.CrossRefGoogle Scholar
  26. Hofstetter, Y. (2014). They know everything: how intelligent machines invade our lives and why we have to fight for our freedom. Munich: Bertelsmann.Google Scholar
  27. Igarashi, Y., Altman, T., Funada, M., Kamiyama, B. (2014). Computing. A historical and technical perspective. New York: CRC Press.Google Scholar
  28. Ippoliti, E. (Ed.). (2015). Heuristic reasoning. Cham: Springer.Google Scholar
  29. Kaminski A., Schembera B., Resch M., Küster U. (2016). Simulation as a ruse. In G. von Gerhard, G. Petra, H. Christoph, K. Andreas and N. Alfred (eds.), Yearbook Technikphilosophie List und Tod (pp. 93–122). Zurich: Diaphines.Google Scholar
  30. Karp, R. M. (1972): Reducibility among Combinatorial Problems. In: Miller R.E., Thatcher J.W., Bohlinger J.D. (Ed.), Complexity of computer computations. The IBM research symposia series. Boston: Springer.CrossRefGoogle Scholar
  31. Kirchner, F., & Michaëlis, C. (1907). Dictionary of Basic Philosophical Terms. Leipzig: Verlag der Dürr’schen Buchhandlung.Google Scholar
  32. Kirkpatrick, S., Gelatt, C.D., & Vecchi, M.P. (1983). Optimization by simulated annealing. Science,220(4598), 671-680. CrossRefGoogle Scholar
  33. Kramer, O. (2008). Self-Adaptive Heuristics for Evolutionary Computation. Berlin: Springer.Google Scholar
  34. Laguna, M. (2018). Taboo Search. In Martí et al., Pp. 741-758.Google Scholar
  35. Lohr, E. (1969). Systematic heuristics - a contribution to the rationalization of technical-scientific research. German journal for philosophy,17(3), 355-363. CrossRefGoogle Scholar
  36. López-Ibáñez, M., Stützle, T., Dorigo, M. (2018). Ant colony optimization: A Component-Wise overview. In Martí et al., Pp. 371-408.Google Scholar
  37. Lorenz, K. (1995). Algorithm. In Jürgen Mittelstraß (Ed.), Encyclopedia Philosophy and Philosophy of Science (vol. 1, p. 85), Stuttgart: Metzler.Google Scholar
  38. MacGregor, J.N., & Ormerod, T. (1996). Human performance on the traveling salesman problem. Perception and Psychophysics,58, 527-539. CrossRefGoogle Scholar
  39. Magnani, L. (2015). Are Heuristics Knowledge Enhancing? Abduction, Models, and Fictions in science. Ippoliti, pp. 29-56. Google Scholar
  40. Martí, R., Pardalos, P. M., Resende, M. G. C. (2018). (Ed.). Handbook of Heuristics. Cham: Springer.Google Scholar
  41. Metropolis, N., et al. (1953). Equation of state calculations by fast computing machines. Journal of Chemical Physics,21(6), 1087-1092. CrossRefGoogle Scholar
  42. Nagata, Y. (2006). Fast EAX algorithm considering population diversity for traveling salesman problems. In European Conference on Evolutionary Computation in Combinatorial Optimization (pp. 171-182). Berlin: Springer.CrossRefGoogle Scholar
  43. Nerurkar, M., Wadephul, C., & Wiegerling, Klaus. (2019). Metaphor in technology ethics. A comment on the big data statement of the German Ethics Council. Yearbook of technology philosophy,5, 271-274. Google Scholar
  44. Newell, A. (1983). The Heuristic of George Polya and its relation to artificial intelligence. In von Groner, R., Groner, M., Bischof, Walter F., (Eds.), Methods of Heuristics, (Pp. 195-244). New Jersey.Google Scholar
  45. Newell, A., Shaw, J. C., & Simon, H. A. (1958). Elements of a theory of human problem solving. Psychological Review,65(3), 151-166. https://doi.org/10.1037/h004849.CrossRefGoogle Scholar
  46. O'Neil, C. (2016). Weapons of math destruction. How big data increases inequality and threatens democracy. New York: Crown Books.Google Scholar
  47. O'Neil, C. (2017). Attack of the algorithms. How they manipulate elections, destroy job opportunities and endanger our health. Munich: Hanser.Google Scholar
  48. Padberg, M., & Rinaldi, G. (1987). Optimization of a 532-city symmetric traveling salesman problem by branch and cut. Operations Research Letters,6, 1-7. CrossRefGoogle Scholar
  49. Pietsch, W., & Wernecke, J. (2017). Introduction: ten theses on big data and predictability. In W. Pietsch, J. Wernecke, & M. Ott (Eds.), Predictability of the world? Philosophy and Science in the Age of Big Data (Pp. 13-36). Wiesbaden: Springer VS.Google Scholar
  50. Pólya, G. (1945). How to solve it. Princeton: Princeton University Press.CrossRefGoogle Scholar
  51. Pólya, G. (1965). Mathematical Discovery Volume II: On understanding, learning, and teaching problem solving. New York: John Wiley and Sons Inc. Google Scholar
  52. Rardin, R. L., & Uzsoy, R. (2001). Experimental evaluation of heuristic optimization algorithms: A tutorial. Journal of Heuristics,7, 261–304. CrossRefGoogle Scholar
  53. Kurz, C., & Rieger, F. (2011). The data guzzlers: How internet companies and the state are gobbling up our personal data and how we can regain control over it. Frankfurt a. M .: Fischer.Google Scholar
  54. Rimscha, M. (2017). Algorithms compact and understandable. Solution strategies on the computer. Wiesbaden: Springer Vieweg.CrossRefGoogle Scholar
  55. Robinson, J. (1949). On the Hamiltonian game (a traveling salesman problem). Research Memorandum RM-303. RAND Corporation: Santa Monica.Google Scholar
  56. Rothlauf, F. (2011). Design of Modern Heuristics. Principles and Application. Berlin: Springer.CrossRefGoogle Scholar
  57. Schröder, M. (2014). One machine for all machines. Small genealogy of the computer with implications for its application in philosophy and music. testcard,24, 74-83. Google Scholar
  58. Schwertgen, D. (2014). The author in the age of his technical reproducibility. testcard,24, 132-137. Google Scholar
  59. Sebö, A., & Vygen, J.P. (2014). Shorter tours by nicer ears: 7/5 approximation for the graph TSP, 3/2 for the path version, and 4/3 for two edge connected subgraphs. Combinatorica,34, 597–629. CrossRefGoogle Scholar
  60. Seidl, T., Enderle, J. (2008). Binary search. In Berthold Vöcking et al. (Ed.), Taschenbuch der Algorithmen (pp. 7–13). Berlin: Springer.Google Scholar
  61. Sörensen, K., Sevaux, M., Glover, F. (2018). A History of Metaheuristics. In Martí et al., Pp. 791-808.Google Scholar
  62. Sörensen, K. (2015). Metaheuristics - The metaphor exposed. International Transactions in Operational Research,22(1), 3-18. CrossRefGoogle Scholar
  63. Stiller, S. (2015). Planet of the Algorithms. A travelguide. Munich: Knaus.Google Scholar
  64. Stützle, T., Ruiz, R. (2018). Iterated greedy. In Martí et al., Pp. 547-578. Google Scholar
  65. Vickers, D., Butavicius, M., Lee, M., & Medvedev, A. (2001). Human performance on visually presented Traveling Salesman problems. Psychological Research,65, 34–45. CrossRefGoogle Scholar
  66. Vickers, D., Lee, M.D., Dry, M., & Hughes, P. (2003). The roles of the convex hull and the number of potential intersections in performance on visually presented traveling salesman problems. Memory & Cognition,31(7), 1094-1104. CrossRefGoogle Scholar
  67. Vickers, D., Lee, M.D., Dry, M., Hughes, P., & McMahon, J.A. (2006). The aesthetic appeal of minimal structures: Judging the attractiveness of solutions to traveling sales person problems. Perception and Psychophysics,68(1), 32–42. CrossRefGoogle Scholar
  68. Tian, ​​W. (2016). On Polynomial Time Absolute Approximation-bounded Solution of TSP and NP Complete Problems. School of Information and Software Engineering, University of Electronic Science and Technology of China (UESTC). https://arxiv.org/pdf/1605.06183.pdf.
  69. Wadephul, C. (2012). From philosophical to grammatical media concept And back again. In Peter F., Andreas L, & Ulrike Ramming (eds.), The reflection of the possible on the dialectic of action, recognition and values ​​(pp. 31–49). Münster: LIT.Google Scholar
  70. Ziegenbalg, J. Ziegenbalg, O., Ziegenbalg, B. (2016). Algorithms from Hammurapi to Gödel With examples from the computer algebra systems Mathematica and Maxima, (4th, revised and expanded edition,), Springer Spectrum: Wiesbaden.CrossRefGoogle Scholar
  71. Zimbardo, P.G. (1995). psychology. Berlin: Springer.CrossRefGoogle Scholar

Copyright information

© Springer Fachmedien Wiesbaden GmbH, part of Springer Nature 2020

Authors and Affiliations

  1. 1. Institute for Technology Assessment and Systems Analysis, Karlsruhe, Germany