research-article

The node-depth encoding: analysis and application to the bounded-diameter minimum spanning tree problem

Authors:

Telma W. de Lima,

Franz Rothlauf,

Alexandre C.B. DelbemAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 969 - 976

https://doi.org/10.1145/1389095.1389279

Published: 12 July 2008 Publication History

Abstract

The node-depth encoding has elements from direct and indirect encoding for trees which encodes trees by storing the depth of nodes in a list. Node-depth encoding applies specific search operators that is a typical characteristic for direct encodings. An investigation into the bias of the initialization process and the mutation operators of the node-depth encoding shows that the initialization process has a bias to solutions with small depths and diameters, and a bias towards stars. This investigation, also, shows that the mutation operators are unbiased. The performance of node-depth encoding is investigated for the bounded-diameter minimum spanning tree problem. The results are presented for Euclidean instances presented in the literature. In contrast with the expectation, the evolutionary algorithm using the biased initialization operator does not allow evolutionary algorithms to find better solutions compared to an unbiased initialization. In comparison to other evolutionary algorithms for the bounded-diameter minimum spanning tree evolutionary algorithms using the node-depth encoding have a good performance.

References

[1]

A. Abdalla and N. Deo. Random-tree diameter and the diameter-constrained mst. Int. J. Comput. Math., 79(6):651--663, 2002.

[2]

F. N. Abuali, D. A. Schoenefeld, and R. L. Wainwright. Designing telecommunications networks using genetic algorithms and probabilistic minimum spanning trees. In SAC '94: Proceedings of the 1994 ACM symposium on Applied computing, pages 242--246, New York, NY, USA, 1994. ACM Press.

Digital Library

[3]

N. Achuthan, L. Caccetta, P. Caccetta, and G. J.F. Algorithms for the minimum weight spanning tree with bounded diameter problem. Optimization: techniques and applications.

[4]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, 2nd edition. MIT Press, McGraw-Hill Book Company, 2000.

Digital Library

[5]

K. Deb. Multi-Objective Optimization Using Evolutionary Algorithms. John Wiley & Sons, Inc., New York, NY, USA, 2001.

Digital Library

[6]

A. Delbem, A. de Carvalho, C. A. Policastro, A. K. Pinto, K. Honda, and A. C. Garcia. Node-depth encoding for evolutionary algorithms applied to network design. In K. Deb and et al., editors, Genetic and Evolutionary Computation -- GECCO-2004, Part I, Lecture Notes in Computer Science, pages 678--687, Seattle, WA, USA, 26-30 June 2004. Springer-Verlag.

[7]

M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979.

Digital Library

[8]

M. Gruber, J. van Hemert, and G. Raidl. Neighborhood searches for the bounded diameter minimum spanning tree problem embedded in a vns, ea, and aco. volume 2, pages 1187--1194, Seattle, USA, 2006. ACM.

Digital Library

[9]

T. C. Hu. Optimum communication spanning trees. SIAM Journal on Computing, 3(3):188--195, 1974.

[10]

B. A. Julstrom. Encoding bounded-diameter spanning trees with permutations and with random keys. In K. Deb and et al., editors, Genetic and Evolutionary Computation -- GECCO-2004, Part I, volume 3102, pages 1272--1281, Seattle, WA, USA, 26-30 June 2004. Springer-Verlag.

[11]

B. A. Julstrom and G. R. Raidl. A permutation-coded evolutionary algorithm for the bounded-diameter minimum spanning tree problem. In A. M. Barry, editor, GECCO 2003: Proceedings of the Bird of a Feather Workshops, Genetic and Evolutionary Computation Conference, pages 2--7, Chigaco, 11 July 2003. AAAI.

[12]

J. D. Knowles and D. Corne. A new evolutionary approach to the degree-constrained minimum spanning tree problem. IEEE Trans. Evolutionary Computation, 4(2):125--134, 2000.

Digital Library

[13]

C. C. Palmer. An approach to a problem in network design using genetic algorithms. PhD thesis, Brooklyn, NY, USA, 1994.

Digital Library

[14]

S. Picciotto. How to Encode a Tree. PhD thesis, University of California, 1999.

[15]

H. Prüfer. Neuer beweis eines satzes uber permutationen. Arch. Math. Phys., 1918.

[16]

G. R. Raidl and J. Gottlieb. Empirical analysis of locality, heritability and heuristic bias in evolutionary algorithms: A case study for the multidimensional knapsack problem. Evolutionary Computation, 13(4):441--475, 2005.

Digital Library

[17]

G. R. Raidl and B. A. Julstrom. Edge sets: an effective evolutionary coding of spanning trees. IEEE Trans. Evolutionary Computation, 7(3):225--239, 2003.

Digital Library

[18]

G. R. Raidl and B. A. Julstrom. Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem. In SAC '03: Proceedings of the 2003 ACM symposium on Applied computing, pages 747--752, New York, NY, USA, 2003. ACM.

Digital Library

[19]

C. R. Reeves. A genetic algorithm for flowshop sequencing. Comput. Oper. Res., 22(1):5--13, 1995.

Digital Library

[20]

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

Digital Library

[21]

F. Rothlauf, D. E. Goldberg, and A. Heinzl. Network random keys: A tree representation scheme for genetic and evolutionary algorithms. Evolutionary Computation, 10(1):75--97, 2002.

Digital Library

[22]

F. Rothlauf and C. Tzschoppe. On the bias and performance of the edge-set encoding, 2005.

[23]

A. Singh and A. K. Gupta. Improved heuristics for the bounded-diameter minimum spanning tree problem. Soft Comput., 11(10):911--921, 2007.

Digital Library

Cited By

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
Show More Cited By

Index Terms

The node-depth encoding: analysis and application to the bounded-diameter minimum spanning tree problem
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction

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 ...
New search operators for node-depth based encoding
GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

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, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
204
Total Downloads

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

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Lima TDelbem ASoares AFederson FJunior JBaalen J(2016)Node-depth phylogenetic-based encoding, a spanning-tree representation for evolutionary algorithms. part I: Proposal and properties analysisSwarm and Evolutionary Computation10.1016/j.swevo.2016.05.00131(1-10)Online publication date: Dec-2016
https://doi.org/10.1016/j.swevo.2016.05.001
Lima TDelbem ALima RSabin GOliveira M(2016)Permutation-based Recombination Operator to Node-depth EncodingProcedia Computer Science10.1016/j.procs.2016.05.32080:C(279-288)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1016/j.procs.2016.05.320
Gois MMatias PPerina ABonato VDelbem A(2014)A Parallel Hardware Architecture based on Node-Depth Encoding to Solve Network Design ProblemsInternational Journal of Natural Computing Research10.4018/ijncr.20140101054:1(54-75)Online publication date: 1-Jan-2014
https://doi.org/10.4018/ijncr.2014010105
Gois MSanches DMartins JJunior JDelbem A(2013)Multi-Objective Evolutionary Algorithm with Node-Depth Encoding and Strength Pareto for Service Restoration in Large-Scale Distribution SystemsEvolutionary Multi-Criterion Optimization10.1007/978-3-642-37140-0_57(771-786)Online publication date: 2013
https://doi.org/10.1007/978-3-642-37140-0_57
de Lima TDelbem ARothlauf FLanzi P(2011)Analysis of properties of recombination operators proposed for the node-depth encodingProceedings of the 13th annual conference companion on Genetic and evolutionary computation10.1145/2001858.2001936(137-138)Online publication date: 12-Jul-2011
https://dl.acm.org/doi/10.1145/2001858.2001936
Silva TMoreira Gois MMatias PDelbem AMarques EBonato V(2011)Spanning forests in constant time using FPGAS applied to network design problems2011 VII Southern Conference on Programmable Logic (SPL)10.1109/SPL.2011.5782645(179-184)Online publication date: Apr-2011
https://doi.org/10.1109/SPL.2011.5782645
Santos ADelbem ALondon JBretas N(2010)Node-Depth Encoding and Multiobjective Evolutionary Algorithm Applied to Large-Scale Distribution System ReconfigurationIEEE Transactions on Power Systems10.1109/TPWRS.2010.204147525:3(1254-1265)Online publication date: Aug-2010
https://doi.org/10.1109/TPWRS.2010.2041475

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents