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

Telma Woerle de Lima

doi:10.1016/j.swevo.2016.05.001

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

2016-12-01

7

PRE

AI

T

Telma Woerle de Lima *

A

Alexandre C. B. Delbem

S

Soares, Anderson da Silva

DOI：10.1016/j.swevo.2016.05.001

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

Network design problems

Tree representations

Dynamic data structures

Evolutionary algorithms

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

Abstract

Journal

Organization