Article

Toward a quantum-inspired linear genetic programming model

Authors:

Douglas Mota Dias,

Marco Aurélio C. PachecoAuthors Info & Claims

CEC'09: Proceedings of the Eleventh conference on Congress on Evolutionary Computation

Pages 1691 - 1698

Published: 18 May 2009 Publication History

Abstract

The huge performance superiority of quantum computers for some specific problems lies in their direct use of quantum mechanical phenomena (e.g. superposition of states) to perform computations. This has motivated the creation of quantum-inspired evolutionary algorithms (QIEAs), which successfully use some quantum physics principles to improve the performance of evolutionary algorithms (EAs) for classical computers. This paper proposes a novel QIEA (Quantum-Inspired Linear Genetic Programming - QILGP) for automatic synthesis of machine code (MC) programs and aims to present a preliminary evaluation of applying the quantum-inspiration paradigm to evolve programs by using two symbolic regression problems. QILGP performance is compared to AIMGP model, since it is the most successful genetic programming technique to evolve MC. In the first problem, the hit ratio of QILGP (100%) is greater than the one of AIMGP (77%). In the second problem, QILGP seems to carry on a less greedy search than AIMGP. Since QILGP presents some satisfactory results, this paper shows that the quantum-inspiration paradigm can be a competitive approach to evolve programs more efficiently, which encourages further developments of that first and simplest QILGP model with multiple individuals.

References

[1]

R. P. Feynman, "Simulating physics with computers," International Journal of Theoretical Physics, vol. 21, p. 467, 1982.

[2]

E. Rieffel and W. Polak, "An introduction to quantum computing for non-physicists," ACM Computing Surveys, vol. 32, no. 3, pp. 300-335, 2000.

Digital Library

[3]

P. W. Shor, "Algorithms for quantum computation: Discrete logarithms and factoring," ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, vol. 35, pp. 124-124, 1994.

Digital Library

[4]

L. K. Grover, "A fast quantum mechanical algorithm for database search," Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 212-219, 1996.

Digital Library

[5]

L. C. Spector, H. Barnum, H. J. Bernstein, and N. Swamy, "Finding a better-than-classical quantum and/or algorithm using genetic programming," Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on, vol. 3, 1999.

[6]

L. C. Spector, Automatic Quantum Computer Programming: A Genetic Programming Approach. Kluwer Academic Publishers, 2004.

Digital Library

[7]

K. H. Han and J. H. Kim, "Quantum-inspired evolutionary algorithm for a class of combinatorial optimization," Evolutionary Computation, IEEE Transactions on, vol. 6, no. 6, pp. 580-593, 2002.

Digital Library

[8]

A. V. Abs da Cruz, C. R. H. Barbosa, M. A. C. Pacheco, and M. B. R. Vellasco, "Quantum-inspired evolutionary algorithms and its application to numerical optimization problems," LECTURE NOTES IN COMPUTER SCIENCE, pp. 212-217, 2004.

[9]

A. V. Abs da Cruz, M. B. R. Vellasco, and M. A. C. Pacheco, "Quantum-inspired evolutionary algorithm for numerical optimization," CEC 2006. IEEE Congress on Evolutionary Computation, pp. 2630-2637, 2006.

[10]

A. V. Abs da Cruz, M. B. R. Vellasco, and M. A. C. Pacheco, "Quantum-inspired evolutionary algorithm for numerical optimization," Hybrid Evolutionary Algorithms, 2007.

[11]

A. V. Abs da Cruz, M. B. R. Vellasco, and M. A. C. Pacheco, "Quantum-inspired evolutionary algorithm for numerical optimization," in Quantum Inspired Intelligent Systems, ser. Studies in Computational Intelligence, N. Nedjah, L. S. Coelho, and L. M. Mourelle, Eds. Springer Berlin/Heidelberg, 2008, vol. 121/2008, pp. 115-132.

[12]

P. Nordin, "AIMGP: A formal description," in Late Breaking Papers at the Genetic Programming 1998 Conference, J. R. Koza, Ed. University of Wisconsin, Madison, Wisconsin, USA: Stanford University Bookstore, 22-25 Jul. 1998.

[13]

M. Brameier and W. Banzhaf, Linear Genetic Programming, ser. Genetic and Evolutionary Computation. Springer, 2007, no. XVI.

Digital Library

[14]

N. L. Cramer, "A representation for the adaptive generation of simple sequential programs," Proceedings of the 1st International Conference on Genetic Algorithms table of contents, pp. 183-187, 1985.

Digital Library

[15]

J. R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA, USA: MIT Press, 1992.

Digital Library

[16]

D. M. Dias, M. A. C. Pacheco, and J. F. M. Amaral, "Automatic synthesis of microcontroller assembly code through linear genetic programming," in Genetic Systems Programming: Theory and Experiences, ser. Studies in Computational Intelligence, N. Nedjah, A. Abraham, and L. de Macedo Mourelle, Eds. Germany: Springer, 2006, vol. 13, pp. 195-234.

[17]

P. Nordin, Evolutionary program induction of binary machine code and its applications. Muenster, Germany: Krehl-Verlag, 1997.

[18]

Intel Architecture Software Developer's Manual, Intel Corporation, 1997.

[19]

F. D. Francone, Discipulus Users Manual, Version 3.0, Register Machine Learning Technologies, 2004.

[20]

W. Banzhaf, P. Nordin, R. E. Keller, and F. D. Francone, Genetic Programming - An Introduction; On the Automatic Evolution of Computer Programs and its Applications. Morgan Kaufmann, dpunkt.verlag, 1998.

Digital Library

[21]

P. Nordin, F. Hoffmann, F. D. Francone, M. Brameier, and W. Banzhaf, "AIM-GP and parallelism," in Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on, vol. 2, 1999.

[22]

M. O'Neill and C. Ryan, Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language. Springer, 2003.

Digital Library

Cited By

Pereira CDias DVellasco MViana FMartí LTakadama K(2018)Crude oil refinery schedulingProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3208291(1821-1828)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3208291
Da Silva CDias DBentes CPacheco MCupertino L(2015)Evolving GPU machine codeThe Journal of Machine Learning Research10.5555/2789272.283113616:1(673-712)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.5555/2789272.2831136
Cupertino LSilva CDias DPacheco MBentes CLanzi P(2011)Evolving CUDA PTX programs by quantum inspired linear genetic programmingProceedings of the 13th annual conference companion on Genetic and evolutionary computation10.1145/2001858.2002026(399-406)Online publication date: 12-Jul-2011
https://dl.acm.org/doi/10.1145/2001858.2002026

Toward a quantum-inspired linear genetic programming model
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies

Recommendations

Quantum-Inspired Multi-gene Linear Genetic Programming Model for Regression Problems
BRACIS '14: Proceedings of the 2014 Brazilian Conference on Intelligent Systems

We propose the Quantum-Inspired Multi-Gene Lin-ear Genetic Programming (QIMuLGP), which is a generalization of Quantum-Inspired Linear Genetic Programming (QILGP) model for symbolic regression. QIMuLGP allows us to explore a different genotypic ...
A quantum-inspired genetic algorithm for k-means clustering

The number of clusters has to be known in advance for the conventional k-means clustering algorithm and moreover the clustering result is sensitive to the selection of the initial cluster centroids. This sensitivity may make the algorithm converge to ...
Quantum-inspired evolutionary multicast algorithm
SMC'09: Proceedings of the 2009 IEEE international conference on Systems, Man and Cybernetics

As a global optimizing algorithm, genetic algorithm (GA) is applied to solve the problem of multicast more and more. GA has more powerful searching ability than traditional algorithm, however its property of "prematurity" makes it difficult to get a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CEC'09: Proceedings of the Eleventh conference on Congress on Evolutionary Computation

May 2009

3356 pages

ISBN:9781424429585

Publisher

IEEE Press

Publication History

Published: 18 May 2009

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
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

Pereira CDias DVellasco MViana FMartí LTakadama K(2018)Crude oil refinery schedulingProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3208291(1821-1828)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3208291
Da Silva CDias DBentes CPacheco MCupertino L(2015)Evolving GPU machine codeThe Journal of Machine Learning Research10.5555/2789272.283113616:1(673-712)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.5555/2789272.2831136
Cupertino LSilva CDias DPacheco MBentes CLanzi P(2011)Evolving CUDA PTX programs by quantum inspired linear genetic programmingProceedings of the 13th annual conference companion on Genetic and evolutionary computation10.1145/2001858.2002026(399-406)Online publication date: 12-Jul-2011
https://dl.acm.org/doi/10.1145/2001858.2002026

View Options

View options

Media

Figures

Other

Tables

View Table of Contents