A genetic engineering approach to genetic algorithms

Aus de_evolutionary_art_org
Wechseln zu: Navigation, Suche


Gero, J.S., Kazakov, V. (2001). A genetic engineering approach to genetic algorithms. Evolutionary Computation, 9(1): 71–92.




We present an extension to the standard genetic algorithm (GA), which is based on concepts of genetic engineering. The motivation is to discover useful and harmful genetic materials and then execute an evolutionary process in such a way that the population becomes increasingly composed of useful genetic material and increasingly free of the harmful genetic material. Compared to the standard GA, it provides some computational advantages as well as a tool for automatic generation of hierarchical genetic representations specifically tailored to suit certain classes of problems.

Extended Abstract


Used References

Aho, A., Hopcroft, J., and Ullman, J. (1975). The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Massachusetts.

Anderberg, M. (1973). Cluster Analysis for Applications. Academic Press, New York, New York.

Angeline, P. J. (1994). Genetic programming and emergent intelligence. In Kinnear, K., editor, Ad- vances in Genetic Programming, pages 75–98, MIT Press, Cambridge, Massachusetts.

Apostolico, A. (1985). The myriad virtues of subword trees. In Apostolico, A. and Galil, Z., editors, Combinatorial Algorithms on Words, pages 85–96, NATO Advanced Study Institute, Series F: Computer and Systems Sciences, Volume 12, Springer-Verlag, Berlin.

Collins, J. F. and Coulson, A. F. E. (1987). Molecular sequence comparison and alignment. In Nu- cleic Acid and Protein Sequence Analysis: A Practical Approach, pages 323–358, IRL Press, Wash- ington DC.

Corcoran, A. L. and Wainwright, R. L. (1994). Chromosome reduction in Genetic algorithms. Tech- nical Report UTULSA-MCS-94-1, University of Tulsa, Tulsa, Oklahoma.

Crochemore, M. (1994). Text Algorithms. Oxford University Press, New York, New York.

Forrest, S. and Mitchell, M. (1993). Relative building-block fitness and building block hypothesis. In Whitley, D., editor, Foundations of Genetic Algorithms, Volume 2, pages 109–126, Morgan Kaufmann, San Mateo, California.

Gero, J. S. and Kazakov, V. (1996). Evolving building blocks for design using genetic engineering: A formal approach. In Gero, J. S., editor, Advances in Formal Design Methods for CAD, pages 31–50, Chapman and Hall, London, England.

Goldberg, D. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. MIT Press, Cambridge, Massachusetts.

Jones, T. C. (1995). A description of Holland’s Royal Road Function. Evolutionary Computation, 2(4):411–417.

De Jong, K. A. (1975). An analysis of the behavior of one class genetic adaptive systems. Unpublished doctoral dissertation. University of Michigan, Ann Arbor, Michigan.

Karlin, S., Dembo, A., and Kawabata, T. (1990a). Methods for assessing the statistical significance of molecular sequence features by using general scoring scheme. Proceedings of the National Academy of Science U.S.A., 87:5509–5513.

Karlin, S., Dembo, A., and Kawabata, T. (1990b). Statistical composition of the high-scoring seg- ments from molecular sequences. Annals of Statistics, 18:571–581.

Koza, J. R. (1992). Genetic Programming. Addison-Wesley, Reading, Massachusetts.

Louis, S. J., McGraw, G., and Wyckoff, R. O. (1993). CBR Assisted Explanation of GA Results. Jour- nal of Theoretical and Experimental Artificial Intelligence, 5(1):21–28.

McCreight, E. M. (1976). A space economical suffix tree construction algorithm. Journal of Associ- ation of Computer Machinery, 232:262–272.

Needleman, S. B. and Wunsch, C. D. (1970). A general method applicable to the search for simi- larities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48:443–453. Evolutionary Computation Volume 9, Number 1

Rosca, J. P. and Ballard, D. H. (1992). Learning by adapting representations in genetic program- ming. In Cohen, W. and Hirsch, H., editors, Proceedings of the Eleventh International Conference on Machine Learning, pages 407–412, Morgan Kaufmann, San Mateo, California.

Sankoff, D. and Kruskal, J. B., editors (1983). Time Warps, String and Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley, Reading, Massachusetts.

Schuler, G. D., Altschul, S. F., and Lipman, D. J. (1991). A workbench for multiple alignment con- struction and analysis. PROTEINS: Structure, Function, and Genetics, 9:180–190.

Simon, P. J. (1973). The organization of the complex systems. In Pattee, H. H., editor, Hierarchy Theory: The Challenge of Complex Systems, pages 109–127, G. Braziller, New York. New York.

Weiner, P. (1973). Linear pattern matching algorithms. In Proceedings of the IEEE 14th Annual Sym- posium on Switching and Automata Theory, pages 1–11, IEEE Press, Piscataway, New Jersey.

Wu, A. S. and Lindsay, R. K. (1995). A comparison of the fixed and floating building block repre- sentation in the genetic algorithm. Evolutionary Computation, 4(2):169–193.


Full Text



intern file

Sonstige Links