Skip to main content
SpringerLink
Log in

Redundant coding of an NP-complete problem allows effective Genetic Algorithm search

  • Genetic Algorithms
  • Conference paper
  • First Online:
Parallel Problem Solving from Nature (PPSN 1990)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 496))

Included in the following conference series:

Abstract

In this paper a Genetic Algorithm is used to search for minimal mutation phyletic trees, an NP-complete problem. We depart from the ‘classical’ G.A. approach to facilitate coding. A clear separation is made between a phenotype and a genotype. The fitness is derived from the phenotype, which represents a tree. The genotype, on which the Genetic Operators are applied, takes the form of a ‘dissimilarity-matrix’ i.e. a redundant non-(bit)string representation. We show that the ‘fitness-landscape’ defined by this genotype/phenotype representation allows effective G.A. search.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Goldberg D. E., Genetic algorithms in Search, Optimization and Machine Learning, Addison-Wesley (1989).

    Google Scholar 

  2. Grefenstette J., Gopal R., Rosmaita B., Van Gucht D., Genetic Algoritms for the Traveling Salesman Problem in Proceedings of an international conference on Genetic Algorithms and their applications, John J. Grefenstette ed., pp 160–168 (1985).

    Google Scholar 

  3. Gorges-Schleuter M., ASPARAGOS An Asynchronous Parallel Genetic Optimization Strategy in Proceedings of the third international conference on Genetic Algorithms, Schaffer David J. ed., Morgan Kaufmann publ., pp 422–427 (1989).

    Google Scholar 

  4. Bock H. H., Automatische Klassifikation, Vandenhoeck & Ruprecht (1974).

    Google Scholar 

  5. Williams W.T., Clifford H.T., Lance G.N., Group size dependency, a rationale for the choice between numerical classifications, The computer J. 14, pp 157–158 (1971).

    Article  Google Scholar 

  6. Hendy M.D., Penny D., Branch and bound algorithms to determine minimal evolutionary trees. Math. Biosc. 59, pp 277–290 (1982).

    Article  Google Scholar 

  7. Klotz L.C.,Blanken R.L., A practical method for calculating evolutionary trees from sequence data. J. Theor. Biol. 91, pp 261–272 (1981).

    Article  PubMed  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Bioinformatics group, University of Utrecht, Padualaan 8, 3584CH, Utrecht

    Marleen Gerrits & Paulien Hogeweg

Authors
  1. Marleen Gerrits
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Paulien Hogeweg
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Hans-Paul Schwefel Reinhard Männer

Rights and permissions

Reprints and permissions

Copyright information

© 1991 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Gerrits, M., Hogeweg, P. (1991). Redundant coding of an NP-complete problem allows effective Genetic Algorithm search. In: Schwefel, HP., Männer, R. (eds) Parallel Problem Solving from Nature. PPSN 1990. Lecture Notes in Computer Science, vol 496. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0029733

Download citation

  • DOI: https://doi.org/10.1007/BFb0029733

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-54148-6

  • Online ISBN: 978-3-540-70652-6

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation