Restricted access
Research articles
Research articlesThe evolvability of programmable hardware
Published:09 June 2010https://doi.org/10.1098/rsif.2010.0212
Abstract
In biological systems, individual phenotypes are typically adopted by multiple genotypes. Examples include protein structure phenotypes, where each structure can be adopted by a myriad individual amino acid sequence genotypes. These genotypes form vast connected ‘neutral networks’ in genotype space. The size of such neutral networks endows biological systems not only with robustness to genetic change, but also with the ability to evolve a vast number of novel phenotypes that occur near any one neutral network. Whether technological systems can be designed to have similar properties is poorly understood. Here we ask this question for a class of programmable electronic circuits that compute digital logic functions. The functional flexibility of such circuits is important in many applications, including applications of evolutionary principles to circuit design. The functions they compute are at the heart of all digital computation. We explore a vast space of 1045 logic circuits (‘genotypes’) and 1019 logic functions (‘phenotypes’). We demonstrate that circuits that compute the same logic function are connected in large neutral networks that span circuit space. Their robustness or fault-tolerance varies very widely. The vicinity of each neutral network contains circuits with a broad range of novel functions. Two circuits computing different functions can usually be converted into one another via few changes in their architecture. These observations show that properties important for the evolvability of biological systems exist in a commercially important class of electronic circuitry. They also point to generic ways to generate fault-tolerant, adaptable and evolvable electronic circuitry.
References
- 1
Wagner A. . 2005Robustness and evolvability in living systems. Princeton, NJ: Princeton University Press. Google Scholar - 2
Kitano H. . 2005Scientific and technical challenges for systems biology. Systems biology (eds, Alberghina L.& Westerhoff H. V. ), pp. 373–385. Topics in Current Genetics, vol. 13. Berlin/Heidelberg, Germany: Springer.doi:10.1007/b137124 (doi:10.1007/b137124). Google Scholar - 3
Ray T. S. . 1991Is it alive or is it GA? In. Proc. of the 1991 Int. Conf. on Genetic Algorithms (eds, Belew R. K.& Booker L. B. ), pp. 527–534. CA, USA: Morgan Kaufmann. Google Scholar - 4
Thompson A. . 1996Evolutionary techniques for fault tolerance. Proc. UKACC Int. Conf. on Control 1996 (CONTROL’96) (eds, Higuchi T., Iwata M.& Liu W. ), pp. 693–698. IEE Conference Publication no. 427. Google Scholar - 5
Tempesti G., Mange D.& Stauffer A. . 1997A robust multiplexer-based FPGA inspired by biological systems. J. Syst. Archit. 43, 719–733.doi:10.1016/S1383-7621(94)00312-2 (doi:10.1016/S1383-7621(94)00312-2). Crossref, ISI, Google Scholar - 6
Millet P.& Heudin J.-C. . 1998Fault tolerance of a large-scale mind architecture using a genetic algorithm. Evolvable systems: from biology to hardware, pp. 356–363. Berlin/Heidelberg, Germany: Springer. Google Scholar - 7
Bradley D. W.& Tyrrell A. M. . 2000Immunotronics: hardware fault tolerance inspired by the immune system. ICES ‘00: Proc. of the 3rd Int. Conf. on Evolvable Systems, pp. 11–20. London, UK: Springer. Google Scholar - 8
Hartmann M.& Haddow P. . 2004Evolution of fault-tolerant and noise-robust digital designs. IEE Proc. Comput. Digital Tech. 151, 287–294.doi:10.1049/ip-cdt:20040014 (doi:10.1049/ip-cdt:20040014). Crossref, ISI, Google Scholar - 9
Schuster P., Fontana W., Stadler P. F.& Hofacker I. L. . 1994From sequences to shapes and back: a case study in RNA secondary structures. Proc. R. Soc. Lond. B 255, 279–284.doi:10.1098/rspb.1994.0040 (doi:10.1098/rspb.1994.0040). Link, ISI, Google Scholar - 10
Wagner A. . 2008Neutralism and selectionism: a network-based reconciliation. Nat. Rev. Genet. 9, 965–974.doi:10.1038/nrg2473 (doi:10.1038/nrg2473). Crossref, PubMed, ISI, Google Scholar - 11
Lipman D. J.& Wilbur W. J. . 1991Modelling neutral and selective evolution of protein folding. Proc. R. Soc. Lond. B 245, 7–11.doi:10.1098/rspb.1991.0081 (doi:10.1098/rspb.1991.0081). Link, ISI, Google Scholar - 12
Babajide A., Hofacker I. L., Sippl M. J.& Stadler P. F. . 1997Neutral networks in protein space: a computational study based on knowledge-based potentials of mean force. Fold Des. 2, 261–269. Crossref, PubMed, Google Scholar - 13
Ferrada E.& Wagner A. . 2008Protein robustness promotes evolutionary innovations on large evolutionary time-scales. Proc. R. Soc. B 275, 1595–1602.doi:10.1098/rspb.2007.1617 (doi:10.1098/rspb.2007.1617). Link, ISI, Google Scholar - 14
Huynen M. A. . 1996Exploring phenotype space through neutral evolution. J. Mol. Evol. 43, 165–169. Crossref, PubMed, ISI, Google Scholar - 15
Wagner A. . 2008Robustness and evolvability: a paradox resolved. Proc. R. Soc. B 275, 91–100.doi:10.1098/rspb.2007.1137 (doi:10.1098/rspb.2007.1137). Link, ISI, Google Scholar - 16
Ciliberti S., Martin O. C.& Wagner A. . 2007Innovation and robustness in complex regulatory gene networks. Proc. Natl Acad. Sci. USA 104, 13 591–13 596.doi:10.1073/pnas.0705396104 (doi:10.1073/pnas.0705396104). Crossref, ISI, Google Scholar - 17
Munteanu A.& Solé R. V. . 2008Neutrality and robustness in evo-devo: emergence of lateral inhibition. PLoS Comput. Biol. 4, e1000 226.doi:10.1371/journal.pcbi.1000226 (doi:10.1371/journal.pcbi.1000226). Crossref, ISI, Google Scholar - 18
Rodrigues J. F. M.& Wagner A. . 2009Evolutionary plasticity and innovations in complex metabolic reaction networks. PLoS Comput. Biol. 5, e1000 613.doi:10.1371/journal.pcbi.1000613 (doi:10.1371/journal.pcbi.1000613). Crossref, ISI, Google Scholar - 19
von Neumann J. . 1956Probabilistic logics and synthesis of reliable organisms from unreliable components. Automata studies (eds, Shannon C.& McCarthy J. ), pp. 43–98. Princeton, NJ: Princeton University Press. Google Scholar - 20
McCulloch W. S. . 1960The reliability of biological systems. Self-organizing systems (eds, Yovits M. C.& Cameron S. ), pp. 264–281. New York, NY: Pergamon Press. Google Scholar - 21
- 22
Macia J.& Solé R. V. . 2009Distributed robustness in cellular networks: insights from synthetic evolved circuits. J. R. Soc. Interface 6, 393–400.doi:10.1098/rsif.2008.0236 (doi:10.1098/rsif.2008.0236). Link, ISI, Google Scholar - 23
- 24
Haddow P.& Tufte G. . 2000An evolvable hardware FPGA for adaptive hardware. Proc. of the 2000 Congress on Evolutionary Computation, La Jolla, CA, 16–19 July 2000, vol. 1, pp. 553–560. Washington, DC: IEEE.doi:10.1109/CEC.2000.870345 (doi:10.1109/CEC.2000.870345). Crossref, Google Scholar - 25
Miller J. F., Job D.& Vassilev V. K. . 2000Principles in the evolutionary design of digital circuits—Part II. Genetic programming and evolvable machines 1, 259–288.doi:10.1023/A:1010066330916 (doi:10.1023/A:1010066330916). Crossref, Google Scholar - 26
Yu T.& Miller J. . 2001Neutrality and the evolvability of Boolean function landscape. Genetic programming (eds, Miller J., Tomassini M., Lanzi P. L., Ryan C., Tettamanzi A. G. B.& Langdon W. B. ), vol. 2038 of Lecture Notes in Computer Science, chap. 16, pp. 204–217. Berlin/Heidelberg, Germany: Springer.doi:10.1007/3-540-45355-5_16 (doi:10.1007/3-540-45355-5_16). Google Scholar - 27
Banzhaf W.& Leier A. . 2006Evolution on neutral networks in genetic programming. Genetic programming theory and practice III, vol. 9, pp. 207–221. USA: Springer. Google Scholar - 28
- 29
Ferrer-Cancho R., Janssen C.& Solé R. V. . 2001Topology of technology graphs: small world patterns in electronic circuits. Phys. Rev. E. 64, 046119. Crossref, ISI, Google Scholar - 30
Solé R. V., Ferrer-Cancho R., Montoya J. M.& Valverde S. . 2002Selection, tinkering, and emergence in complex networks. Complex 8, 20–33.doi:10.1002/cplx.10055 (doi:10.1002/cplx.10055). Crossref, Google Scholar - 31
Holland J. . 1992Adaptation in natural and artificial systems. Cambridge, UK: MIT Press. Crossref, Google Scholar - 32
- 33
Upegui A.& Sanchez E. . 2008Reconfigurable computing, chap. Evolvable FPGAs, pp. 725–752. San Diego, CA: Morgan Kaufmann. Crossref, Google Scholar - 34
Thompson A. . 1995Evolving electronic robot controllers that exploit hardware resources. Advances in artificial life: Proc. 3rd Eur. Conf. on Artificial Life (ECAL95) (eds, Morán F., Moreno A., Merelo J. J.& Chacon P. ), vol. 929 of LNAI, pp. 640–656. Berlin, Germany: Springer. Google Scholar - 35
Thompson A. . 1996Silicon evolution. GECCO ‘96: Proc. of the 1st Annual Conf. on Genetic Programming, pp. 444–452. Cambridge, MA, USA: MIT Press. Google Scholar - 36
Thompson A. . 1997An evolved circuit, intrinsic in silicon, entwined with physics. First Int. Conf. on Evolvable systems: from biology to hardware, ICES96, Tsukuba, Japan, 7–8 October 1996 (eds, Higuchi T., Iwata M.& Liu W. ), pp. 390–405. Berlin/Heidelberg, Germany: Springer. Google Scholar - 37
Harvey I.& Thompson A. . 1996Through the labyrinth evolution finds a way: a silicon ridge. ICES '96: Proc. of the 1st Int. Conf. on Evolvable Systems, Tsukuba, Japan, 7–8 October 1996 (eds, Higuchi T., Iwata M.& Lei W. ), pp. 406–422. London, UK: Springer. Google Scholar - 38
Hollingworth G., Smith S.& Tyrell A. . 2000The intrinsic evolution of virtex devices through internet reconfigurable logic. ICES '00: Proc. of the Third Int. Conf. on Evolvable Systems, Edinburgh, UK, 17–19 April 2000 (eds, Miller J., Thompson A., Thompson P.& Fogarty T. C. ), pp. 72–79. London, UK: Springer. Google Scholar - 39
Meyer-Baese U. . 2007Digital signal processing with field programmable gate arrays. Berlin, Germany: Springer. Google Scholar - 40
- 41
Miller J. F. . 1999An empirical study of the efficiency of learning Boolean functions using a Cartesian genetic programming approach. Proc. of the Genetic and Evolutionary Computation Conference, vol. 2 (eds, Banzhaf W., Daida J., Eiben A. E., Garzon M. H., Honavar V., Jakiela M.& Smith R. E. ), pp. 1135–1142. FL, USA: Morgan Kaufmann. Google Scholar - 42
Miller J. F.& Thomson P. . 2000Cartesian genetic programming. EuroGP (eds, Poli R., Banzhaf W., Langdon W. B., Miller J. F., Nordin P.& Fogarty T. C. ), vol. 1802 of Lecture Notes in Computer Science, pp. 121–132. Springer. Google Scholar - 43
Irvine K. . 2007Assembly language for Intel-based computers. Upper Saddle River, NJ: Pearson Prentice Hall. Google Scholar - 44
- 45
Stallings W. . 2006Cryptography and network security. Upper Saddle River, NJ: Pearson/Prentice Hall. Google Scholar - 46
White R.& Miles F. . 1996Principles of fault tolerance. Proc. of the 11th Annual Applied Power Electronics Conf. and Exposition. APEC '96, San Jose, CA, 3–7 March 2006, vol. 1, pp. 18–25. Washington, DC: IEEE.doi:10.1109/APEC.1996.500416 (doi:10.1109/APEC.1996.500416). Crossref, Google Scholar - 47
Keymeulen D., Zebulum R., Jin Y.& Stoica A. . 2000Fault-tolerant evolvable hardware using field-programmable transistor arrays. IEEE Trans. Reliability 49, 305–316.doi:10.1109/24.914547 (doi:10.1109/24.914547). Crossref, ISI, Google Scholar - 48
Banzhaf W. . 1994Genotype–phenotype-mapping and neutral variation–a case study in genetic programming. PPSN III: Proc. Int. Conf. on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature (eds, Yu T., Riolo R.& Worzel B. ), pp. 322–332. London, UK: Springer. Google Scholar - 49
Ebner M. . 1999On the search space of genetic programming and its relation to nature's search space. Proc. 1999 Congress on Evolutionary Computation, 1999. CEC '99, Washington, DC, 6–9 July 1999, vol. 2.Washington, DC: IEEE.doi:10.1109/CEC.1999.782609 (doi:10.1109/CEC.1999.782609). Crossref, Google Scholar - 50
Ebner M., Langguth P., Albert J., Shackleton M.& Shipman R. . 2001On neutral networks and evolvability. Proc. of the 2001 Congress on Evolutionary Computation, Seoul, South Korea, 27–30 May 2001, vol. 1, pp. 1–8. Washington, DC: IEEE.doi:10.1109/CEC.2001.934363 (doi:10.1109/CEC.2001.934363). Google Scholar - 51
Ebner M., Shackleton M.& Shipman R. . 2001How neutral networks influence evolvability. Complexity 7, 19–33.doi:10.1002/cplx.10021 (doi:10.1002/cplx.10021). Crossref, Google Scholar - 52
Vassilev V. K.& Miller J. F. . 2000The advantages of landscape neutrality in digital circuit evolution. ICES '00: Proc. of the 3rd Int. Conf. on Evolvable Systems, pp. 252–263. London, UK: Springer. Google Scholar - 53
Yu T.& Miller J. . 2002Finding needles in haystacks is not hard with neutrality. Genetic programming (eds, Foster J. A., Lutton E., Miller J., Ryan C.& Tettamanzi A. ), vol. 2278 of Lecture Notes in Computer Science, chap. 2, pp. 46–54. Berlin/Heidelberg, Germany: Springer.doi:10.1007/3-540-45984-7_2 (doi:10.1007/3-540-45984-7_2). Google Scholar - 54
Yu T.& Miller J. F. . 2006Through the interaction of neutral and adaptive mutations, evolutionary search finds a way. Artif. Life 12, 525–551.doi:10.1162/artl.2006.12.4.525 (doi:10.1162/artl.2006.12.4.525). Crossref, PubMed, ISI, Google Scholar - 55
Collins M. . 2006Finding needles in haystacks is harder with neutrality. Genetic Programm. Evol. Mach. 7, 131–144.doi:10.1007/s10710-006-9001-y (doi:10.1007/s10710-006-9001-y). Crossref, Google Scholar - 56
Miller J. F.& Smith S. L. . 2006Redundancy and computational efficiency in cartesian genetic programming. IEEE Trans. Evol. Comput. 10, 167–174.doi:10.1109/TEVC.2006.871253 (doi:10.1109/TEVC.2006.871253). Crossref, ISI, Google Scholar - 57
Fernández P.& Solé R. V. . 2007Neutral fitness landscapes in signalling networks. J. R. Soc. Interface 4, 41–47.doi:10.1098/rsif.2006.0152 (doi:10.1098/rsif.2006.0152). Link, ISI, Google Scholar - 58
Wagner A. . 2005Distributed robustness versus redundancy as causes of mutational robustness. Bioessays 27, 176–188.doi:10.1002/bies.20170 (doi:10.1002/bies.20170). Crossref, PubMed, ISI, Google Scholar - 59
van Nimwegen E., Crutchfield J. P.& Huynen M. . 1999Neutral evolution of mutational robustness. Proc. Natl Acad. Sci. USA 96, 9716–9720. Crossref, PubMed, ISI, Google Scholar - 60
Forster R., Adami C.& Wilke C. O. . 2006Selection for mutational robustness in finite populations. J. Theoret. Biol. 243, 181–190.doi:10.1016/j.jtbi.2006.06.020 (doi:10.1016/j.jtbi.2006.06.020). Crossref, PubMed, ISI, Google Scholar - 61
Moeckel R., Jaquier C., Drapel K., Upegui A.& Ijspeert A. . 2005YaMoR and Bluemove—an autonomous modular robot with bluetooth interface for exploring adaptive locomotion. Proc. of the 8th Int. Conf. on Climbing and Walking Robots, London, UK, 12–15 September 2005 (eds, Tokhi M. O., Virk G. S.& Hossain M. A. ), pp. 685–692. London, UK: Springer. Google Scholar - 62
Marbach D.& Ijspeert A. . 2005Online optimization of modular robot locomotion. Proc. of the IEEE Int. Conf. on Mechatronics and Automation (ICMA 2005), Niagra Falls, Canada, 29 July–1 August 2005, pp. 248–253. Washington, DC: IEEE. Google Scholar - 63
Emmert J., Stroud C., Skaggs B.& Abramovici M. . 2000Dynamic fault tolerance in FPGAs via partial reconfiguration. FCCM '00: Proc. of the 2000 IEEE Symposium on Field-Programmable Custom Computing Machines, pp. 165–174. Washington, DC, USA: IEEE Computer Society. Google Scholar - 64
Habermann S., Kothe R.& Vierhaus H. T. . 2006Built-in self repair by reconfiguration of FPGAs. IOLTS 2006: Proc. of the 12th IEEE Int. On-Line Testing Symposium, Lake Como, Italy, 10–12 July 2006, pp. 187–188. Washington, DC: IEEE Computer Society Press.doi:10.1109/IOLTS.2006.13 (doi:10.1109/IOLTS.2006.13). Crossref, Google Scholar - 65
Chen W., Wang Y., Wang X.& Peng C. . 2008A new placement approach to minimizing FPGA reconfiguration data. Int. Conf. on Embedded Software and Systems, 2008. ICESS '08, Chengdu, China, 29–31 July 2008, pp. 169–174. Washington, DC: IEEE Computer Society Press.doi:10.1109/ICESS.2008.20 (doi:10.1109/ICESS.2008.20). Crossref, Google Scholar - 66
Shirazi N., Benyamin D., Luk W., Cheung P. Y. K.& Guo S. . 2001Quantitative analysis of FPGA-based database searching. J. VLSI Signal Process. Syst. 28, 85–96.doi:10.1023/A:1008163222529 (doi:10.1023/A:1008163222529). Crossref, Google Scholar - 67
Torresen J.& Glette K. . 2007Improving flexibility in on-line evolvable systems. Evolvable systems: from biology to hardware, Seventh Int. Conf., ICES 2007, Wuhan, China, 12–15 September 2005 (eds, Kang L., Liu Y.& Zeng S. ), pp. 391–402. London, UK: Springerdoi:10.1007/978-3-540-74626-3 (doi:10.1007/978-3-540-74626-3). Crossref, Google Scholar - 68
Aharoni A., Gaidukov L., Khersonsky O., Gould S. M., Roodveldt C.& Tawfik D. S. . 2005The ‘evolvability’ of promiscuous protein functions. Nat. Genet. 37, 73–76.doi:10.1038/ng1482 (doi:10.1038/ng1482). Crossref, PubMed, ISI, Google Scholar - 69
Bloom J. D., Silberg J. J., Wilke C. O., Drummond D. A., Adami C.& Arnold F. H. . 2005Thermodynamic prediction of protein neutrality. Proc. Natl Acad. Sci. USA 102, 606–611.doi:10.1073/pnas.0406744102 (doi:10.1073/pnas.0406744102). Crossref, PubMed, ISI, Google Scholar - 70
Zipf G. K. . 1972Human behaviour and the principle of least effort. An introduction to human ecology.New York, NY: Hafner. Google Scholar
