article

Network random keys: a tree representation scheme for genetic and evolutionary algorithms

Authors:

Franz Rothlauf,

David E. Goldberg,

Armin HeinzlAuthors Info & Claims

Evolutionary Computation, Volume 10, Issue 1

Pages 75 - 97

https://doi.org/10.1162/106365602317301781

Published: 01 March 2002 Publication History

Abstract

When using genetic and evolutionary algorithms for network design, choosing a good representation scheme for the construction of the genotype is important for algorithm performance. One of the most common representation schemes for networks is the characteristic vector representation. However, with encoding trees, and using crossover and mutation, invalid individuals occur that are either under- or over-specified. When constructing the offspring or repairing the invalid individuals that do not represent a tree, it is impossible to distinguish between the importance of the links that should be used. These problems can be overcome by transferring the concept of random keys from scheduling and ordering problems to the encoding of trees. This paper investigates the performance of a simple genetic algorithm (SGA) using network random keys (NetKeys) for the one-max tree and a real-world problem. The comparison between the network random keys and the characteristic vector encoding shows that despite the effects of stealth mutation, which favors the characteristic vector representation, selectorecombinative SGAs with NetKeys have some advantages for small and easy optimization problems. With more complex problems, SGAs with network random keys significantly outperform SGAs using characteristic vectors.This paper shows that random keys can be used for the encoding of trees, and that genetic algorithms using network random keys are able to solve complex tree problems much faster than when using the characteristic vector. Users should therefore be encouraged to use network random keys for the representation of trees.

References

[1]

Abuali, F. N., Wainwright, R. L., and Schoenefeld, D. A. (1995). Determinant factorization: A new encoding scheme for spanning trees applied to the probabilistic minimum spanning tree problem. In Eshelman, L., editor, Proceedings of the Sixth International Conference on Genetic Algorithms, pages 470-477, Morgan Kaufmann, San Francisco, California.]]

Digital Library

[2]

Ackley, D. H. (1987). A connectionist machine for genetic hill climbing. Kluwer Academic, Boston, Massachusetts.]]

Digital Library

[3]

Bäck, T. and Schwefel, H.-P. (1995). Evolution strategies I: Variants and their computational implementation. In Winter, G. et al., editors, Genetic Algorithms in Engineering and Computer Science, pages 111-126, John Wiley and Sons, Chichester, UK.]]

[4]

Bean, J. C. (1992). Genetics and random keys for sequencing and optimization. Technical Report 92-43, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan.]]

[5]

Bean, J. C. (1994). Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing, 6(2):154-160.]]

[6]

Berry, L. T. M., Murtagh, B. A., and Sugden, S. J. (1994). A genetic-based approach to tree network synthesis with cost constraints. In Zimmermann, H. J., editor, Second European Congress on Intelligent Techniques and Soft Computing - EUFIT'94, Volume 2, pages 626-629, Verlag der Augustinus Buchhandlung, Aachen, Germany.]]

[7]

Davis, L. et al. (1993). A genetic algorithm for survivable network design. In Forrest, S., editor, Proceedings of the Fifth International Conference on Genetic Algorithms, pages 408-415, Morgan Kaufmann, San Mateo, California.]]

Digital Library

[8]

Fox, B. R. and McMahon, M. B. (1991). Genetic operators for sequencing problems. In Rawlins, G. J. E., editor, Foundations of Genetic Algorithms, pages 284-300, Morgan Kaufmann, San Mateo, California.]]

[9]

Goldberg, D. E. (1989a). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, Reading, Massachusetts.]]

Digital Library

[10]

Goldberg, D. E. (1989b). Sizing populations for serial and parallel genetic algorithms. In Schaffer, J. D., editor, Proceedings of the Third International Conference on Genetic Algorithms, pages 70-79, Morgan Kaufmann, San Mateo, California.]]

Digital Library

[11]

Goldberg, D. E. (1990). Real-coded genetic algorithms, virtual alphabets, and blocking. IlliGAL Report No. 90001, University of Illinois at Urbana-Champaign, Urbana, Illinois.]]

[12]

Goldberg, D. E., Deb, K., and Clark, J. H. (1992). Genetic algorithms, noise, and the sizing of populations. Complex Systems, 6:333-362.]]

[13]

Goldberg, D. E., Deb, K., and Thierens, D. (1993). Toward a better understanding of mixing in genetic algorithms. Journal of the Society of Instrument and Control Engineers, 32(1):10-16.]]

[14]

Goldberg, D. E. et al. (1993). Rapid, accurate optimization of difficult problems using fast messy genetic algorithms. In Forrest, S., editor, Proceedings of the Fifth International Conference on Genetic Algorithms, pages 56-64, Morgan Kaufmann, San Mateo, California,]]

Digital Library

[15]

Hamming, R. (1980). Coding and information theory. Prentice-Hall, London, England.]]

Digital Library

[16]

Harik, G. R. et al. (1997). The gambler's ruin problem, genetic algorithms, and the sizing of populations. In Bäck, T., editor, Proceedings of the Forth International Conference on Evolutionary Computation, pages 7-12, IEEE Press, Piscataway, New Jersey.]]

[17]

Kargupta, H., Deb, K., and Goldberg, D. E. (1992). Ordering genetic algorithms and deception. In Männer, R. and Manderick, B., editors, Parallel Problem Solving from Nature - PPSN II, pages 47-56, Elsevier Science, Amsterdam, The Netherlands.]]

[18]

Knjazew, D. (2000). Application of the fast messy genetic algorithm to permutation and scheduling problems . IlliGAL Report No. 2000022, University of Illinois at Urbana-Champaign, Urbana, Illinois.]]

[19]

Knjazew, D. and Goldberg, D. E. (2000a). Large-scale permutation optimization with the ordering messy genetic algorithm. IlliGAL Report No. 2000013, University of Illinois at Urbana-Champaign, Urbana, Illinois.]]

[20]

Knjazew, D. and Goldberg, D. E. (2000b). OMEGA - ordering messy ga: Solving permutation problems with the fast messy genetic algorithm and random keys. IlliGAL Report No. 2000004, University of Illinois at Urbana-Champaign, Urbana, Illinois.]]

[21]

Mühlenbein, H. and Schlierkamp-Voosen, D. (1993). Predictive models for the breeder genetic algorithm: I. Continuous parameter optimization. Evolutionary Computation, 1(1):25-49.]]

Digital Library

[22]

Norman, B. A. (1995). Scheduling using the random keys genetic algorithm. Unpublished Ph.D. thesis, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan.]]

Digital Library

[23]

Norman, B. A. and Bean, J. C. (1994). Random keys genetic algorithm for job shop scheduling. Technical Report No. 94-5, University of Michigan, Ann Arbor, Michigan.]]

[24]

Norman, B. A. and Bean, J. C. (1997). Operation sequencing and tool assignment for multiple spindle CNC machines. In Proceedings of the Forth International Conference on Evolutionary Computation, pages 425-430, IEEE, Piscataway, New Jersey.]]

[25]

Norman, B. A. and Bean, J. C. (2000). Scheduling operations on parallel machines, IIE Transactions, 32:449-459.]]

[26]

Norman, B. A. and Smith, A. E. (1997). Random keys genetic algorithm with adaptive penalty function for optimization of constrained facility layout problems. In Proceedings of the Forth International Conference on Evolutionary Computation, pages 407-411, IEEE. Piscataway, New Jersey.]]

[27]

Norman, B. A., Smith, A. E., and Arapoglu, R. A. (1998). Integrated facility design using an evolutionary approach with a subordinate network algorithm. In Eiben, A. E. et al., editors, Parallel Problem Solving from Nature, PPSN V, pages 937-946, Springer-Verlag, Berlin, Germany.]]

Digital Library

[28]

Orvosh, D. and Davis, L. (1993). Shall we repair? Genetic algorithms, combinatorial optimization, and feasibility constraints. In Forrest, S., editor, Proceedings of the Fifth International Conference on Genetic Algorithms, page 650, Morgan Kaufmann, San Mateo, California.]]

Digital Library

[29]

Palmer, C. C. (1994). An approach to a problem in network design using genetic algorithms. Unpublished Ph.D. thesis, Computer Science Department, Polytechnic University, Troy, New York.]]

Digital Library

[30]

Palmer, C. C. and Kershenbaum, A. (1994). Representing trees in genetic algorithms. In Proceedings of the First IEEE Conference on Evolutionary Computation, Volume 1, pages 379-384, IEEE, Piscataway, New Jersey.]]

[31]

Prüfer, H. (1918). Neuer Beweis eines Satzes über Permutationen. Archiv für Mathematik und Physik, 27:742-744.]]

[32]

Rothlauf, F. (2001). Towards a theory of representations for genetic and evolutionary algorithms: Development of basic concepts and their application to binary and tree representations. Doctoral dissertation, Department of Information Systems, University of Bayreuth, Bayreuth, Germany.]]

[33]

Rothlauf, F. and Goldberg, D. E. (2000). Prüfernumbers and genetic algorithms: A lesson on how the low locality of an encoding can harm the performance of GAs. In Schoenauer, M. et al., editors, Parallel Problem Solving from Nature, PPSN VI, pages 395-404, Springer-Verlag, Berlin, Germany.]]

Digital Library

[34]

Sinclair, M. C. (1995). Minimum cost topology optimisation of the COST 239 European optical network. In Pearson, D. W., Steele, N. C., and Albrecht, R. F., editors, Proceedings of the 1995 International Conference on Artificial Neural Nets and Genetic Algorithms, pages 26-29, Springer-Verlag, New York.]]

[35]

Tang, K. S., Man, K. F., and Ko, K. T. (1997). Wireless LAN design using hierarchical genetic algorithm. In Bäck, T., editor, Proceedings of the Seventh International Conference on Genetic Algorithms, pages 629-635, Morgan Kaufmann, San Francisco, California.]]

[36]

Thierens, D. and Goldberg, D. E. (1994). Convergence models of genetic algorithm selection schemes. In Davidor, Y., Schwefel, H.-P., and Männer, R., editors, Parallel Problem Solving from Nature - PPSN III, pages 119-129, Springer-Verlag, Berlin, Germany.]]

Digital Library

Cited By

Ngoc BTam NBinh HVinh L(2024)A phenotype-based multi-objective evolutionary algorithm for maximizing lifetime in wireless sensor networks with bounded hopSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-023-08923-128:15-16(8681-8699)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s00500-023-08923-1
Plump CBerger BDrechsler RSilva SPaquete L(2023)Repetitive Processes and Their Surrogate-Model Congruent Encoding for Evolutionary Algorithms - A Theoretic ProposalProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3596389(2289-2296)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3596389
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

Network random keys: a tree representation scheme for genetic and evolutionary algorithms

Recommendations

A biased random-key genetic algorithm with forward-backward improvement for the resource constrained project scheduling problem

This paper presents a biased random-key genetic algorithm for the resource constrained project scheduling problem. The chromosome representation of the problem is based on random keys. Active schedules are constructed using a priority-rule heuristic in ...
A random-key genetic algorithm for solving the nesting problem

This article presents a random-key genetic algorithm RKGA for the nesting problem, a particular case of cutting and packing problems in which a collection of items or polygons has to be packed onto a rectangular object with the aim of minimising its ...
A parallel multi-population biased random-key genetic algorithm for a container loading problem

This paper presents a multi-population biased random-key genetic algorithm (BRKGA) for the single container loading problem (3D-CLP) where several rectangular boxes of different sizes are loaded into a single rectangular container. The approach uses a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Evolutionary Computation

Evolutionary Computation Volume 10, Issue 1

Spring 2002

97 pages

ISSN:1063-6560

EISSN:1530-9304

Issue’s Table of Contents

Publisher

MIT Press

Cambridge, MA, United States

Publication History

Published: 01 March 2002

Published in EVOL Volume 10, Issue 1

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
156
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ngoc BTam NBinh HVinh L(2024)A phenotype-based multi-objective evolutionary algorithm for maximizing lifetime in wireless sensor networks with bounded hopSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-023-08923-128:15-16(8681-8699)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s00500-023-08923-1
Plump CBerger BDrechsler RSilva SPaquete L(2023)Repetitive Processes and Their Surrogate-Model Congruent Encoding for Evolutionary Algorithms - A Theoretic ProposalProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3596389(2289-2296)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3596389
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
de Azevedo Albuquerque Kde Medeiros RDuarte RVillanueva Jde Macêdo E(2023)Routing Algorithm for Energy Efficiency Optimizing of Wireless Sensor Networks based on Genetic AlgorithmsWireless Personal Communications: An International Journal10.1007/s11277-023-10849-8133:3(1829-1856)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1007/s11277-023-10849-8
Landa-Torres ILobo JMurua IManjarres DDel Ser J(2017)Multi-objective heuristics applied to robot task planning for inspection plants2017 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2017.7969496(1621-1628)Online publication date: 5-Jun-2017
https://dl.acm.org/doi/10.1109/CEC.2017.7969496
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
de Andrade CToso RResende MMiyazawa F(2015)Biased random-key genetic algorithms for the winner determination problem in combinatorial auctionsEvolutionary Computation10.1162/EVCO_a_0013823:2(279-307)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1162/EVCO_a_00138
Ruiz EAlbareda-Sambola MFernández EResende M(2015)A biased random-key genetic algorithm for the capacitated minimum spanning tree problemComputers and Operations Research10.1016/j.cor.2014.11.01157:C(95-108)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1016/j.cor.2014.11.011
Zatarain-Aceves HFernández-Zepeda JBrizuela CFajardo-Delgado D(2015)A cascade evolutionary algorithm for the bodyguard allocation problemApplied Soft Computing10.1016/j.asoc.2015.08.05637:C(643-651)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1016/j.asoc.2015.08.056
Cordella LDe Stefano CFontanella FMarcelli A(2013)EvoGeneSys, a new evolutionary approach to graph generationApplied Soft Computing10.1016/j.asoc.2012.12.03713:4(1922-1938)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.1016/j.asoc.2012.12.037
Show More Cited By

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents