mns2012 (mns2012) wrote in biosemiotics,
mns2012
mns2012
biosemiotics

Dembski, Marks: Conservation of Information in Search: Measuring the Cost of Success

Conservation of information theorems indicate that any search algorithm performs on average as well as random search without replacement unless it 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. Three measures to characterize the information required for successful search are (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.

William A. Dembski and Robert J. Marks II "Conservation of Information in Search: Measuring the Cost of Success" IEEE Transactions on Systems, Man and Cybernetics A, Systems & Humans, vol.5, #5, September 2009, pp.1051-1061
Tags: активная информация, алгоритм, информация, комбинаторный поиск, эволюционные алгоритмы
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    switch
    default userpic
    Help
  • 0 comments