Node-depth phylogenetic-based encoding, a spanning-tree representation for evolutionary algorithms. part I: Proposal and properties analysis

作     者：de Lima, Telma Woerle Botazzo Delbem, Alexandre Claudio Soares, Anderson da Silva Federson, Fernando Marques Augusto London Junior, Joao Bosco Van Baalen, Jeffrey 

作者机构：Univ Fed Goias Inst Informat Setor Samuel Graham Jatai Go Brazil Univ Sao Paulo Sao Carlos Sch Engn BR-05508 Sao Paulo Brazil Univ Wyoming Dept Comp Sci Laramie WY 82071 USA 

出 版 物：《SWARM AND EVOLUTIONARY COMPUTATION》 (群与进化计算)

年 卷 期：2016年第31卷

页      面：1-10页

核心收录：

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

主　　题：Network design problems Tree representations Dynamic data structures Evolutionary algorithms 

摘      要：Representation choice and the development of search operators are crucial aspects of the efficiency of Evolutionary Algorithms (EAs) in combinatorial problems. Several researchers have proposed representations and operators for EAs that manipulate spanning trees. This paper proposes a new encoding called Node-depth Phylogenetic-based Encoding (NPE). NPE represents spanning trees by the relation between nodes and their depths using a relatively simple codification/decodification process. The proposed NPE operators are based on methods used for tree rearrangement in phylogenetic tree reconstruction: subtree prune and regraft;and tree bisection and reconstruction. NPE and its operators are designed to have high locality, feasibility, low time complexity, be unbiased, and have independent weight. Therefore, NPE is a good choice of data structure for EAs applied to network design problems. (C) 2016 Elsevier B.V. All rights reserved.