윌리엄 뎀스키, 로버트 막스, 그리고 진화정보학 연구소가 새로운 동료심사 논문에서 도킨스의 WEASEL 시물레이션과 대결하다
2010년의 새로운 동료심사 논문은 뎀스키와 막스, 그리고 진화정보학 연구소의 다른 연구원들에 의해서 출판은 연구를 이어가고 있다. ( 새로 개편된 웹사이트 EvoInfo.org를 살펴보길. ) 저자들은 러처드 도킨스의 “METHINKSITISLIKEAWEASEL” 진화 알고리즘이 많은 양의 활성정보, 즉 탐색을 돕기위해 프로그래머에 의해 지성적으로 삽입된 정보로부터 시작한다고 주장한다. 이 논문은 WEASEL 알고리즘의 작동에 관한 알려진 주장들을 살펴보면서 모든 경우에서 활성정보가 사용된다는 것을 보여준다. 도킨스의 알고리즘은 “해밍 오라클(Hamming Oracle)”을 사용하는 것으로 가장 잘 이해될 수 있다. “어떤 해밍 오라클로 어떤 문자열이 입력되면, 오라클은 그 문자열 중에서 잘못된 문자들의 수에 대응하는 해밍 거리(Hamming distance)를 알려준다.” 저자들은 이런 형태의 탐색은 그 목적지를 찾는데 아주 효과적이지만, 이것이 가능한 이유는 그 목적지를 빠르게 찾기 위해 필요한 다량의 활성정보가 이미 프로그래밍되어 있기 때문일 뿐이라는 것을 보여준다. 이 활성정보는 진정한 다윈주의 진화탐색 알고리즘에서는 존재할 수 없는 것이다. “Weasel Ware”라고 불리는 온라인 포로그램 툴킷이 논문에 포함되어 있으며, http://evoinfo.org/weasel 에서 찾을 수 있다.
Winston Ewert, George Montanez, William A. Dembski, Robert J. Marks II, “Efficient Per Query Information Extraction from a Hamming Oracle,” Proceedings of the the 42nd Meeting of the Southeastern Symposium on System Theory, IEEE, University of Texas at Tyler, March 7-9, 2010, pp.290-297.
논문요약 – 컴퓨터 탐색은 어떤 제안된 문제의 해를 결정하기 위해 종종 어떤 오라클을 사용한다. 정보는 반복된 질의를 통해 오라클로부터 추출된다. 이러한 정보를 가장 효율적으로 추출하는 탐색알고리즘을 만드는 것이 프로그래머의 일이다. 많은 경우에, 이것은 당면한 문제에 관한 프로그래머의 경험과 지식을 통해 이루어진다. 해밍 오라클을 사용하는 경우, 우리는 질의가 얼마나 이루어지는가를 이용해서 다양한 탐색알고리즘의 성능을 평가할 수 있다. 고려된 탐색 절차들 중에서, 무작위 탐색(blind search)이 성능이 가장 뒤떨어진다. 우리는 진화 알고리즘들이 비록 무작위 탐색보다는 나은 편이지만, 정보 추출에 있어서 상대적으로 비효율적인 방법이라는 것을 보인다. 알파벳 문자들의 발생빈도를 알아내어 차례대로 추적해나가는 알고리즘이 훨씬 나은 성능을 보인다. 우리는 또한 우리의 이전 연구에서 제시된 것과 같이, 최적 트리 탐색을 위한 ‘탐색을 위한 탐색’은 상당량의 계산을 요구한다는 것을 보여준다.
William Dembski, Robert Marks, and the Evolutionary Informatics Lab Take on Dawkins’ “WEASEL” Simulation in New Peer-Reviewed Paper
A new peer-reviewed paper continues the work published by William Dembski, Robert Marks, and others affiliated with the Evolutionary Informatics Lab. (Check out their new revamped website at EvoInfo.org.) The authors argue that Richard Dawkins’ “METHINKSITISLIKEAWEASEL” evolutionary algorithm starts off with large amounts of active information—information intelligently inserted by the programmer to aid the search. This paper covers all of the known claims of operation of the WEASEL algorithm and shows that in all cases, active information is used. Dawkins’ algorithm can best be understood as using a “Hamming Oracle” as follows: “When a sequence of letters is presented to a Hamming oracle, the oracle responds with the Hamming distance equal to the number of letter mismatches in the sequence.” The authors find that this form of a search is very efficient at finding its target — but that is only because it is preprogrammed with large amounts of active information needed to quickly find the target. This preprogrammed active information makes it far removed from a true Darwinian evolutionary search algorithm. An online toolkit of programs called “Weasel Ware” accompanies the paper and can be found here.
The paper’s title, citation information, and abstract are as follows:
Winston Ewert, George Montanez, William A. Dembski, Robert J. Marks II, “Efficient Per Query Information Extraction from a Hamming Oracle,” Proceedings of the the 42nd Meeting of the Southeastern Symposium on System Theory, IEEE, University of Texas at Tyler, March 7-9, 2010, pp.290-297.
Abstract—Computer search often uses an oracle to determine the value of a proposed problem solution. Information is extracted from the oracle using repeated queries. Crafting a search algorithm to most efficiently extract this information is the job of the programmer. In many instances this is done using the programmer’s experience and knowledge of the problem being solved. For the Hamming oracle, we have the ability to assess the performance of various search algorithms using the currency of query count. Of the search procedures considered, blind search performs the worst. We show that evolutionary algorithms, although better than blind search, are a relatively inefficient method of information extraction. An algorithm methodically establishing and tracking the frequency of occurrence of alphabet characters performs even better. We also show that a search for the search for an optimal tree search, as suggested by our previous work, becomes computationally intensive.
[2010/4/8] 다윈주의 진화메커니즘을 비판한 새로운 피어리뷰 논문 출판
