Nothing Special   »   [go: up one dir, main page]

skip to main content
10.5555/645406.652269guideproceedingsArticle/Chapter ViewAbstractPublication PagesConference Proceedingsacm-pubtype
Article

The Link and Node Biased Encoding Revisited: Bias and Adjustment of Parameters

Published: 18 April 2001 Publication History

Abstract

When using genetic and evolutionary algorithms (GEAs) for the optimal communication spanning tree problem, the design of a suitable tree network encoding is crucial for finding good solutions. The link and node biased (LNB) encoding represents the structure of a tree network using a weighted vector and allows the GEA to distinguish between the importance of the nodes and links in the network. This paper investigates whether the encoding is unbiased in the sense that all trees are equally represented, and how the parameters of the encoding influence the bias. If the optimal solution is underrepresented in the population, a reduction in the GEA performance is unavoidable. The investigation reveals that the commonly used simpler version of the encoding is biased towards star networks, and that the initial population is dominated by only a few individuals. The more costly link-and-node-biased encoding uses not only a node-specific bias, but also a link-specific bias. Similarly to the node-biased encoding, the link-and-node-biased encoding is also biased towards star networks, especially when using a low weighting for the link-specific bias. The results show that by increasing the link-specific bias, that the overall bias of the encoding is reduced. If researchers want to use the LNB encoding, and they are interested in having an unbiased representation, they should use higher values for the weight of the link-specific bias. Nevertheless, they should also be aware of the limitations of the LNB encoding when using it for encoding tree problems. The encoding could be a good choice for the optimal communication spanning tree problem as the optimal solutions tend to be more star-like. However, for general tree problems the encoding should be used carefully.

References

[1]
T. C. Hu. Optimum communication spanning trees. SIAM Journal on Computing , 3(3):188-195, September 1974.
[2]
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman, New York, 1979.
[3]
L. Davis, D. Orvosh, A. Cox, and Y. Qiu. A genetic algorithm for survivable network design. In S. Forrest, editor, Proceedings of the Fifth International Conference on Genetic Algorithms , pages 408-415, San Mateo, CA, 1993. Morgan Kaufmann.
[4]
L. T. M. Berry, B. A. Murtagh, and S. J. Sugden. A genetic-based approach to tree network synthesis with cost constraints. In Hans Jürgen Zimmermann, editor, Second European Congress on Intelligent Techniques and Soft Computing - EUFIT'94 , volume 2, pages 626-629, Promenade 9, D-52076 Aachen, 1994. Verlag der Augustinus Buchhandlung.
[5]
J. R. Kim and M. Gen. Genetic algorithm for solving bicriteria network topology design problem. In Peter J. Angeline, Zbyszek Michalewicz, Marc Schoenauer, Xin Yao, Ali Zalzala, and William Porto, editors, Proceedings of the 1999 IEEE Congress on Evolutionary Computation , pages 2272-2279. IEEE Press, 1999.
[6]
Y. Li and Y. Bouchebaba. A new genetic algorithm for the optimal communication spanning tree problem. In C. Fonlupt, J.-K. Hao, E. Lutton, E. Ronald, and M. Schoenauer, editors, Proceedings of Artificial Evolution: Fifth European Conference , page xx, Berlin, 1999. Springer.
[7]
K. S. Tang, K. F. Man, and K. T. Ko. Wireless LAN desing using hierarchical genetic algorithm. In T. Bäck, editor, Proceedings of the Seventh International Conference on Genetic Algorithms , pages 629-635, San Francisco, 1997. Morgan Kaufmann.
[8]
M. C. Sinclair. Minimum cost topology optimisation of the COST 239 European optical network. In D. W. Pearson, N. C. Steele, and R. F. Albrecht, editors, Proceedings of the 1995 International Conference on Artificial Neural Nets and Genetic Algorithms , pages 26-29, New York, 1995. Springer-Verlag.
[9]
M. Krishnamoorthy, A. T. Ernst, and Y. M. Sharaiha. Comparison of algorithms for the degree constrained minimum spanning tree. Tech. rep., CSIRO Mathematical and Information Sciences, Clayton, Australia, 1999.
[10]
F. Rothlauf, D. E. Goldberg, and A. Heinzl. Network random keys - a tree network representation scheme for genetic and evolutionary algorithms. Technical Report No. 8/2000, University of Bayreuth, Germany, 2000.
[11]
G. R. Raidl and B. A. Julstrom. A weighted coding in a genetic algorithm for the degree-constrained minimum spanning tree problem. In Janice Carroll, Ernesto Damiani, Hisham Haddad, and Dave Oppenheim, editors, Proceedings of the 2000 ACM Symposium on Applied Computing , pages 440-445. ACM Press, 2000.
[12]
H. Prüfer. Neuer Beweis eines Satzes ueber Permutationen. Arch. Math. Phys. , 27:742-744, 1918.
[13]
F. Rothlauf and D. E. Goldberg. Pruefernumbers and genetic algorithms: A lesson on how the low locality of an encoding can harm the performance of GAs. In Kalyanmoy Deb, Günther Rodolph, Xin Yao, and Hans-Paul Schwefel, editors, Proceedings of the 2000 Parallel Problem Solving from Nature VI Conference , pages 395-404. Springer, 2000.
[14]
J. C. Bean. Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing , 6(2):154-160, 1994.
[15]
C. C. Palmer. An approach to a problem in network design using genetic algorithms . unpublished PhD thesis, Polytechnic University, Troy, NY, 1994.
[16]
F. N. Abuali, R. L. Wainwright, and D. A. Schoenefeld. Determinant factorization: A new encoding scheme for spanning trees applied to the probabilistic minimum spanning tree problem. In L. Eschelman, editor, Proceedings of the Sixth International Conference on Genetic Algorithms , pages 470-477, San Francisco, CA, 1995. Morgan Kaufmann.
[17]
G. Harik, E. Cantú-Paz, D. E. Goldberg, and Brad L. Miller. The gambler's ruin problem, genetic algorithms, and the sizing of populations. Evolutionary Computation , 7(3):231-253, 1999.
[18]
C. C. Palmer and A. Kershenbaum. Representing trees in genetic algorithms. In Proceedings of the First IEEE Conference on Evolutionary Computation , volume 1, pages 379-384, Piscataway, NJ, 1994. IEEE Service Center.
[19]
A. Kershenbaum. Telecommunications network design algorithms . McGraw Hill, New York, 1993.
[20]
R. Prim. Shortest connection networks and some generalizations. Bell System Technical Journal , 36:1389-1401, 1957.
[21]
S. Ronald. Robust encodings in genetic algorithms: A survey of encoding issues. In Proceedings of the Forth International Conference on Evolutionary Computation , pages 43-48, Piscataway, NJ, 1997. IEEE.

Cited By

View all
  • (2005)On a property analysis of representations for spanning tree problemsProceedings of the 7th international conference on Artificial Evolution10.1007/11740698_10(107-118)Online publication date: 26-Oct-2005
  • (2003)Redundant representations in evolutionary computationEvolutionary Computation10.1162/10636560332251928811:4(381-415)Online publication date: 1-Dec-2003

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings
Proceedings of the EvoWorkshops on Applications of Evolutionary Computing
April 2001
514 pages

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 18 April 2001

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 16 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2005)On a property analysis of representations for spanning tree problemsProceedings of the 7th international conference on Artificial Evolution10.1007/11740698_10(107-118)Online publication date: 26-Oct-2005
  • (2003)Redundant representations in evolutionary computationEvolutionary Computation10.1162/10636560332251928811:4(381-415)Online publication date: 1-Dec-2003

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media