CoChat
Sign Up
Cited by 59Computability, Logic, AI AlgorithmsEvolutionary Algorithms and ApplicationsMetaheuristic Optimization Algorithms Research

The DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.

Conservation of Information in Search: Measuring the Cost of Success

Dembski, William A., Marks II, Robert J.·2009·IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans
DOI 10.1109/tsmca.2009.2025027
Open this paper in CoChat — free account

Abstract

Conservation of information theorems indicate that any search algorithm performs, on average, as well as random search without replacementunlessit takes advantage of problem-specific information about the search target or the search-space structure. Combinatorics shows that even a moderately sized search requires problem-specific information to be successful. Computers, despite their speed in performing queries, are completely inadequate for resolving even moderately sized search problems without accurate information to guide them. We propose three measures to characterize the information required for successful search: 1)endogenous information, which measures the difficulty of finding a target using random search; 2)exogenous information, which measures the difficulty that remains in finding a target once a search takes advantage of problem-specific information; and 3)active information, which, as the difference between endogenous and exogenous information, measures the contribution of problem-specific information for successfully finding a target. This paper develops a methodology based on these information measures to gauge the effectiveness with which problem-specific information facilitates successful search. It then applies this methodology to various search tools widely used in evolutionary search.

Overview

Integrity signals

Registry

Crossref · 10.1109/tsmca.2009.2025027

Cites

1 of 1 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

This paper’s full text isn’t openly available, so its claims and self-check weren’t run. The registry and citation checks still apply.

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Active information I+ = log(P*/Pmax) measures the amount of information added or subtracted when P* is used instead of Pmax; positive I+ means P* overfits, negative means underfits, and zero means extra assumptions do not contribute to cosmological tuning.

    “A very efficient way to keep accountability is by calculating the active information I + = log( P ∗ /P max ) [42-44]. I + measures the amount of information added or subtracted when P ∗ is used instead of P max . If I + is positive, P ∗ is overfitting for ℓ X with respect to P max ; if I + is negative, P ∗ is underfitting the life-permitting interval with respect to P max ; and if I + = 0 , P ∗”

    From Is cosmological tuning fine or coarse? (2021) · cites this paper as [42]

Citations

Cites

Flagged first, then by citations

Research works printed but not linked: 49

  1. 10.1016/B978-1-55860-335-6.50039-8 · DOI
  2. 10.1109/TSMCC.2004.833297 · DOI
  3. marks, 2009, Handbook of Fourier Analysis and Its Application, 10.1093/oso/9780195335927.001.0001 · DOI
  4. mackay, 2002, Information Theory Inference and Learning Algorithms
  5. 10.1109/TSMCB.2006.883272 · DOI
  6. 10.1162/106454604773563559 · DOI
  7. 10.1109/SICE.1998.742931 · DOI
  8. reed, 1999, Neural Smithing Supervised Learning in Feedforward Artificial Neural Networks, 10.7551/mitpress/4937.001.0001 · DOI
  9. 10.1109/3468.867863 · DOI
  10. papoulis, 1991, Probability random variables and stochastic processes, 537
  11. 10.1109/TSMCB.2003.808184 · DOI
  12. 10.1109/MSP.2007.273055 · DOI
  13. 10.1038/nature01568 · DOI
  14. 10.1109/TSMCA.2007.914767 · DOI
  15. 10.1109/TSMCA.2005.853495 · DOI
  16. 10.1109/TSMCA.2007.914765 · DOI
  17. 10.1109/TSMCA.2007.914796 · DOI
  18. 10.1109/TAC.2003.811254 · DOI
  19. ho, 2001, simple explanation of the no free lunch theorem, Proc 40th IEEE Conf Decision Control, 4409
  20. 10.1109/4235.930318 · DOI
  21. 10.1109/5.784232 · DOI
  22. 10.1017/CBO9780511546433 · DOI
  23. yu, 2006, a novel congruent organizational design methodology using group technology and a nested genetic algorithm, IEEE Trans Syst Man Cybern A Syst Humans, 36, 5, 10.1109/TSMCA.2006.859106 · DOI
  24. 10.1162/evco.1998.6.2.109 · DOI
  25. cutnell, 1995, Physics
  26. 10.1093/nar/28.14.2794 · DOI
  27. dawkins, 1996, The Blind Watchmaker Why the Evidence of Evolution Reveals a Universe without Design
  28. droste, 0, perhaps not a free lunch but at least a free appetizer, Proc GECCO, 833
  29. eberhart, 2001, Swarm Intelligence
  30. 10.1109/CEC.1999.782013 · DOI
  31. 10.1109/3468.784176 · DOI
  32. 10.1109/TSMCB.2008.915645 · DOI
  33. gwiazda, 2006, Genetic Algorithms Reference
  34. bernoulli, 1713, ars conjectandi (the art of conjecturing), Tractatus De Seriebus Infinitis
  35. aigner, 2007, Discrete Mathematics
  36. burg, 1975, Maximum entropy spectral analysis
  37. brillouin, 1956, Science and Information Theory
  38. 10.1109/TSMCA.2007.914784 · DOI
  39. christensen, 2001, what can we learn from no free lunch? a first attempt to characterize the concept of a searchable, Proc Genetic Evol Comput, 1219
  40. 10.1109/TSMCA.2006.886342 · DOI
  41. cover, 2006, Elements of Information Theory
  42. 10.1109/4235.585893 · DOI · Paper page
  43. 10.1109/TSMCA.2007.914769 · DOI
  44. wright, 1997, Gadsby
  45. 10.1109/TEVC.2005.856205 · DOI
  46. 10.1007/978-3-662-05052-1 · DOI
  47. 10.1002/j.1538-7305.1948.tb01338.x · DOI · Paper page
  48. 10.1112/plms/s2-42.1.230 · DOI · Paper page
  49. 10.1109/CEC.2004.1330860 · DOI

Cited by

Sorted by citations

Metadata

Authors
Dembski, W. A., & Marks II, R. J.
Affiliations
Southwestern Baptist Theological Seminary (US)
Venue
IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Published
2009-09
Volume
39
Issue
5
Pages
1051-1061
ISSN
1083-4427 (ISSN-L)
DOI
10.1109/tsmca.2009.2025027
OpenAlex
W2157965697
Cited by
59
References
1
Citations by year
2026: 1 · 2025: 2 · 2024: 3 · 2023: 5 · 2022: 4 · 2021: 5 · 2020: 3 · 2019: 2 · 2018: 1 · 2017: 1 · 2016: 2 · 2015: 4 · 2014: 2 · 2013: 10 · 2012: 5
FWCI
4.56
Type
journal article
Language
en
Open access
closed
Licence
ieeexplore.ieee.org/Xplorehelp/downloads/license-information/IEEE.html (vor)
Locations
IEEE Transactions on Systems Man and Cybernetics - Part A Systems and Humans (publishedVersion)
Topics
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
  • Physical Sciences › Computer Science › Artificial Intelligence › Evolutionary Algorithms and Applications
  • Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
Keywords
information conservation, search algorithms, endogenous information, exogenous information, active information, search difficulty, evolutionary search, information measures

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review