Combinatorial search versus genetic algorithms:: A case study based on the generalized median graph problem

作     者：Bunke, H Münger, A Jiang, XY 

作者机构：Univ Bern Dept Comp Sci Inst Informat & Angew Math CH-3012 Bern Switzerland 

出 版 物：《PATTERN RECOGNITION LETTERS》 (模式识别快报)

年 卷 期：1999年第20卷第11-13期

页      面：1271-1277页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：generalized median graph combinatorial search genetic algorithm 

摘      要：The computation of generalized median graphs (the graph with the smallest average edit distance to all graphs in a given set of graphs) is highly computationally complex. As a matter of fact, it is exponential in the number of nodes of the union of all graphs under consideration. Thus, the generalized median graph computation problem seems to be a suitable and challenging testbed for a comparison of combinatorial search and genetic algorithms. Two solutions are described in this paper. The first is an exact algorithm based on combinatorial search, while the second is a genetic algorithm. Both approaches are compared to each other in a series of experiments. (C) 1999 Elsevier Science B.V. All rights reserved.