Partitioned incremental evolution of hardware using genetic programming
Abstract
In an effort to enable evolutionary computation techniques to discover solutions for large and complex hardware systems, techniques have been devised to break the initial problem down into smaller sub-tasks. In particular, a decomposition approach has been described that is based on partitioning of the circuit test vectors, but it has its limitations. In an effort to address this, we have combined the partitioning method with an incrementally evolving genetic programming approach. The result, referred to as Partitioned Incremental Evolution of HARDware (PIE-HARD), exhibits solution-finding performance that is significantly better than that of other approaches.
References
[1]
Koza, J.R., Bennett, I.F.H., Andre, D., Keane, M.A., Dunlap, F.: Automated Synthesis of Analog Electrical Circuits by Means of Genetic Programming. IEEE Trans. Evol. Comput. 1(2), 109-128 (1997).
[2]
Thompson, A., Layzell, P., Zebulum, R.S.: Explorations in Design Space: Unconventional Electronics Design through Artificial Evolution. IEEE Trans. Evol. Comput. 3(3), 167-196 (1999).
[3]
Alpaydin, G., Balkir, S., Dundar, G.: An Evolutionary Approach to Automatic Synthesis of High-Performance Analog Integrated Circuits. IEEE Trans. Evol. Comput. 7(3), 240-252 (2003).
[4]
Miller, J.F., Job, D., Vassilev, V.K.: Principles in The Evolutionary Design of Digital Circuits-Part I. Genetic Programming and Evolvable Machines 1, 7-35 (2000).
[5]
Torresen, J.: A Scalable Approach to Evolvable Hardware. Genetic Programming and Evolvable Machines 3, 259-282 (2002).
[6]
Torresen, J.: A Divide-and-Conquer Approach to Evolvable Hardware. In: Sipper, M., Mange, D., Pérez-Uribe, A. (eds.) ICES 1998. LNCS, vol. 1478, Springer, Heidelberg (1998).
[7]
Coello, C.A.C., Christiansen, A.D., Aguirre, A.H.: Use of Evolutionary Techniques to Automate the Design of Combinational Circuits. International Journal of Smart Engineering System Design 2(4), 229-314 (2000).
[8]
Coello, C.A.C., Luna, E.H., Aguirre, A.H.: Use of Particle Swarm Optimization to Design Combinational Logic Circuits. In: Tyrrell, A.M., Haddow, P.C., Torresen, J. (eds.) ICES 2003. LNCS, vol. 2606, pp. 398-409. Springer, Heidelberg (2003).
[9]
Koza, J.R.: Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge (1992).
[10]
Koza, J.R.: Genetic Programming II: Automatic Discovery of Reusable Programs. MIT Press, Cambridge (1994).
[11]
Koza, J.R.: Simultaneous Discovery of Reusable Detectors and Subroutines Using Genetic Programming. In: Proc. 5th Int. Conf. Genetic Algorithms (ICGA-1993), pp. 295-302 (1993).
[12]
Rosca, J.P., Ballard, D.H.: Hierarchical Self-Organization in Genetic Programming. In: Proc 11th International Conf. on Machine Learning, pp. 251-258. Morgan Kaufmann, San Francisco (1994).
[13]
Angeline, P.J., Pollack, J.: Evolutionary Module Acquisition. In: Proc. 2nd Annual Conf. on Evolutionary Programming, La Jolla, CA, pp. 154-163 (1993).
[14]
Angeline, P.J., Pollack, J.: Coevolving High-Level Representations. In: Langton, C.G. (ed.) Artificial Life III, pp. 55-71. Addison-Wesley, Reading (1994).
[15]
Rosca, J.P., Ballard, D.H.: Discovery of Subroutines in Genetic Programming. In: Angeline, P., Kinnear Jr., K.E. (eds.) Advances in Genetic Programming 2, ch. 9, pp. 177-202. MIT Press, Cambridge (1996).
[16]
Roberts, S.C., Howard, D., Koza, J.R.: Evolving Modules in Genetic Programming by Subtree Encapsulation. In: Miller, J., Tomassini, M., Lanzi, P.L., Ryan, C., Tetamanzi, A.G.B., Langdon, W.B. (eds.) EuroGP 2001. LNCS, vol. 2038, pp. 160-175. Springer, Heidelberg (2001).
[17]
Walker, J.A., Miller, J.F.: Evolution and Acquisition of Modules in Cartesian Genetic Programming. In: Keijzer, M., O'Reilly, U.-M., Lucas, S.M., Costa, E., Soule, T. (eds.) EuroGP 2004. LNCS, vol. 3003, pp. 187-197. Springer, Heidelberg (2004).
[18]
Lopez, E.G., Poli, R., Coello, C.A.C.: Reusing Code in Genetic Programming. In: Keijzer, M., O'Reilly, U.-M., Lucas, S.M., Costa, E., Soule, T. (eds.) EuroGP 2004. LNCS, vol. 3003, pp. 359-368. Springer, Heidelberg (2004).
[19]
Gustafon, S.M.: Layered Learning in Genetic Programming for a Cooperative Robot Soccer Problem. M.S. Thesis, Dept. of Computing and Information Sciences, Kansas State University, USA (2000).
[20]
Hsu, W.H., Harmon, S.J., Rodriguez, E., Zhong, C.: Empirical Comparison of Incremental Reuse Strategies in Genetic Programming for Keep-Away Soccer. In: Deb, K., et al. (eds.) GECCO 2004. LNCS, vol. 3102, Springer, Heidelberg (2004).
[21]
Jackson, D., Gibbons, A.P.: Layered Learning in Boolean GP Problems. In: Ebner, M., O'Neill, M., Ekárt, A., Vanneschi, L., Esparcia-Alcázar, A.I. (eds.) EuroGP 2007. LNCS, vol. 4445, pp. 148-159. Springer, Heidelberg (2007).
Index Terms
- Partitioned incremental evolution of hardware using genetic programming
Recommendations
Bidirectional Incremental Evolution in Extrinsic Evolvable Hardware
EH '00: Proceedings of the 2nd NASA/DoD workshop on Evolvable HardwareEvolvable Hardware (EHW) has been proposed as a new technique to design complex systems. Often, complex systems turn out to be very difficult to evolve. The problem is that a general strategy is too difficult for the evolution process to discover ...
Parallel incremental graph partitioning using linear programming
Supercomputing '94: Proceedings of the 1994 ACM/IEEE conference on SupercomputingPartitioning graphs into equally large groups of nodes while minimizing the number of edges between different groups is an extremely important problem in parallel computing. For instance, efficiently parallelizing several scientific and engineering ...
Evolution, development and learning using self-modifying cartesian genetic programming
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computationSelf-Modifying Cartesian Genetic Programming (SMCGP) is a form of genetic programming that integrates developmental (self-modifying) features as a genotype-phenotype mapping. This paper asks: Is it possible to evolve a learning algorithm using SMCGP?
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
March 2008
374 pages
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 26 March 2008
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 1Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 16 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in