2011 | OriginalPaper | Buchkapitel
Property Analysis and Enhancement in Recombination Operator of Edge-Set Encoding for Spanning Tree
verfasst von : P. K. Singh, Abhishek Vaid
Erschienen in: Contemporary Computing
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The spanning tree problem is a well-studied problem and Evolutionary Algorithms (EAs) have been successfully applied to a large variants of the spanning tree problem. The behavior of an evolutionary algorithm depends on the interaction between the encoding and the genetic operators that act on that encoding. Various encodings and operators have been proposed for the spanning tree problems in the literature. The edge-set encoding has been shown very effective for such problems as it shows high locality and high heritability. However, it requires effective genetic operators to exploit favorable characteristics of an encoding to guide the search and obtain high quality results. In this work, we consider bounded-diameter minimum spanning tree (BDMST) problem and improve upon the crossover operator for edge-set encoding. The empirical results show the effectiveness of our approach. Finally, based on the simulation results, we highlight interesting properties of the new recombination operator which helps it find better trees compared to the previous one.