research-article

New search operators for node-depth based encoding

Authors:

Gustavo Post Sabin,

Telma Woerle de Lima,

Anderson da Silva SoaresAuthors Info & Claims

GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

Pages 734 - 741

https://doi.org/10.1145/3377930.3390238

Published: 26 June 2020 Publication History

Get Access

Abstract

Node-Depth Based Encoding is a representation for Evolutionary Algorithms applied to problems modelled by trees, storing nodes and their respective depths in an appropriately ordered list. This representation was highlighted by the results obtained, whose mutation and recombination operators have low time complexity in relation to other representations for the same problems. This work proposes new search operators. A high locality mutation operator, having as its main differential the possibility of including any edge present in a graph and a recombination operator with the ability to generate solutions with as much heritability as possible considering the edges set in the solutions, making it possible to recombine any solutions in the population with the aim of improving search convergence. All proposed operators also allow for dealing with problems modelled by forests with many trees and complete or non-complete graphs, always generating feasible solutions. This study performed bias, locality and heritability investigations for proposed operators showing that they have adequate characteristics for dealing with high dimensionality problems. In order to evaluate the performance of proposed operators, the results of preliminary tests were obtained applying to a benchmark problem in the literature. The use of proposed operators resulted in faster convergence.

References

[1]

Telma Woerle de Lima, Alexandre Cláudio Botazzo Delbem, Anderson da Silva Soares, Fernando Marques Federson, João Bosco Augusto London Junior, and Jeffrey Van Baalen. 2016. Node-depth phylogenetic-based encoding, a spanningtree representation for evolutionary algorithms. part I: Proposal and properties analysis. Swarm and Evolutionary Computation 31 (2016), 1--10.

Crossref

Google Scholar

[2]

Telma Woerle de Lima, Alexandre Cláudio Botazzo Delbem, Roney Lopes Lima, Gustavo Post Sabin, and Marcos Antônio Almeida de Oliveira. 2016. Permutation-based recombination operator to node-depth encoding. Procedia Computer Science 80 (2016), 279--288.

Digital Library

Google Scholar

[3]

Telma W de Lima, Franz Rothlauf, and Alexandre CB Delbem. 2008. The nodedepth encoding: analysis and application to the bounded-diameter minimum spanning tree problem. In Proceedings of the 10th annual conference on Genetic and evolutionary computation. ACM, 969--976.

Google Scholar

[4]

Alexandre CB Delbem and Andre De Carvalho. 2003. A forest representation for evolutionary algorithms applied to network design. In Proceedings of the 2003 international conference on Genetic and evolutionary computation: PartI. Springer-Verlag, 634--635.

Crossref

Google Scholar

[5]

Alexandre CB Delbem, Andre de Carvalho, Claudio A Policastro, Adriano KO Pinto, Karen Honda, and Anderson C Garcia. 2004. Node-depth encoding for evolutionary algorithms applied to network design. In Genetic and Evolutionary Computation Conference. Springer, 678--687.

Crossref

Google Scholar

[6]

A. C. B. Delbem, T. W. Lima, and G. P. Telles. 2012. Efficient Forest Data Structure for Evolutionary Algorithms Applied to Network Design. IEEE Transactions on Evolutionary Computation 99 (2012), 1--28.

Google Scholar

[7]

R Hamming. 1980. Coding and Information Theory. Simon & Schuster, Inc., Englewood Cliffs, NJ, USA.

Google Scholar

[8]

Charles C Palmer and Aaron Kershenbaum. 1994. Representing trees in genetic algorithms. In Evolutionary Computation, 1994. IEEE World Congress on Computational Intelligence., Proceedings of the First IEEE Conference on. IEEE, 379--384.

Crossref

Google Scholar

[9]

Nicholas J Radcliffe. 1994. The algebra of genetic algorithms. Annals of mathematics and artificial intelligence 10, 4 (1994), 339--384.

Crossref

Google Scholar

[10]

Franz Rothlauf. 2006. Representations for Genetic and Evolutionary Algorithms. Springer-Verlag.

Digital Library

Google Scholar

[11]

Franz Rothlauf. 2011. Design of modern heuristics: principles and application. Springer Science & Business Media.

Google Scholar

Cited By

View all

Anh DBinh HKien DLong NDao TBan H(2024)Node-depth based Genetic Algorithm to solve Inter-Domain path computation problemKnowledge-Based Systems10.1016/j.knosys.2023.111168284(111168)Online publication date: Jan-2024
https://doi.org/10.1016/j.knosys.2023.111168
Dao TTam NBinh H(2024)Node depth Representation-based Evolutionary Multitasking Optimization for Maximizing the Network Lifetime of Wireless Sensor NetworksEngineering Applications of Artificial Intelligence10.1016/j.engappai.2023.107463128(107463)Online publication date: Feb-2024
https://doi.org/10.1016/j.engappai.2023.107463
Tran CDo Tuan ABinh HDo Duc ABan Ha BNguyen Phan Bach SSilva SPaquete L(2023)MNDE: Node-depth encoding can do better in evolutionary multitask algorithmsProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3590717(251-254)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3590717

Index Terms

New search operators for node-depth based encoding

Recommendations

Permutation-based Recombination Operator to Node-depth Encoding

The node-depth encoding is a representation for evolutionary algorithms applied to tree problems. Its represents trees by storing the nodes and their depth in a proper ordered list. The original formulation of the node-depth encoding has only mutation ...
Analysis of properties of recombination operators proposed for the node-depth encoding
GECCO '11: Proceedings of the 13th annual conference companion on Genetic and evolutionary computation

The node-depth encoding is a representation for evolutionary algorithms applied to tree problems. Its represents trees by storing the nodes and their depth in a proper ordered list. The original formulation of the node-depth encoding has only mutation ...
Abstract convex evolutionary search
FOGA '11: Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms

Geometric crossover is a formal class of crossovers which includes many well-known recombination operators across representations. In this paper, we present a general result showing that all evolutionary algorithms using geometric crossover with no ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

June 2020

1349 pages

ISBN:9781450371285

DOI:10.1145/3377930

General Chair:
Carlos Artemio Coello Coello
CINVESTAV-IPN

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 June 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '20

Sponsor:

SIGEVO

GECCO '20: Genetic and Evolutionary Computation Conference

July 8 - 12, 2020

Cancún, Mexico

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
65
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Anh DBinh HKien DLong NDao TBan H(2024)Node-depth based Genetic Algorithm to solve Inter-Domain path computation problemKnowledge-Based Systems10.1016/j.knosys.2023.111168284(111168)Online publication date: Jan-2024
https://doi.org/10.1016/j.knosys.2023.111168
Dao TTam NBinh H(2024)Node depth Representation-based Evolutionary Multitasking Optimization for Maximizing the Network Lifetime of Wireless Sensor NetworksEngineering Applications of Artificial Intelligence10.1016/j.engappai.2023.107463128(107463)Online publication date: Feb-2024
https://doi.org/10.1016/j.engappai.2023.107463
Tran CDo Tuan ABinh HDo Duc ABan Ha BNguyen Phan Bach SSilva SPaquete L(2023)MNDE: Node-depth encoding can do better in evolutionary multitask algorithmsProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3590717(251-254)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3590717

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Permutation-based Recombination Operator to Node-depth Encoding

Analysis of properties of recombination operators proposed for the node-depth encoding

Abstract convex evolutionary search