A three-step decomposition method for the evolutionary design of sequential logic circuits

Abstract  Evolvable hardware (EHW) refers to an automatic circuit design approach, which employs evolutionary algorithms (EAs) to generate
the configurations of the programmable devices. The scalability is one of the main obstacles preventin…

Abstract  Evolvable hardware (EHW) refers to an automatic circuit design approach, which employs evolutionary algorithms (EAs) to generate
the configurations of the programmable devices. The scalability is one of the main obstacles preventing EHW from being applied
to real-world applications. Several techniques have been proposed to overcome the scalability problem. One of them is to decompose
the whole circuit into several small evolvable sub-circuits. However, current techniques for scalability are mainly used to
evolve combinational logic circuits. In this paper, in order to decompose a sequential logic circuit, the state decomposition,
output decomposition and input decomposition are united as a three-step decomposition method (3SD). A novel extrinsic EHW
system, namely 3SD–ES, which combines the 3SD method with the (μ, λ) ES (evolution strategy), is proposed, and is used for the evolutionary designing of larger sequential logic circuits. The
proposed extrinsic EHW system is tested extensively on sequential logic circuits taken from the Microelectronics Center of
North Carolina (MCNC) benchmark library. The results demonstrate that 3SD–ES has much better performance in terms of scalability.
It enables the evolutionary designing of larger sequential circuits than have ever been evolved before.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-009-9083-4
  • Authors
    • Houjun Liang, University of Science and Technology of China Nature Inspired Computation and Applications Laboratory (NICAL), Department of Computer Science and Technology 230027 Hefei Anhui China
    • Wenjian Luo, University of Science and Technology of China Nature Inspired Computation and Applications Laboratory (NICAL), Department of Computer Science and Technology 230027 Hefei Anhui China
    • Xufa Wang, University of Science and Technology of China Nature Inspired Computation and Applications Laboratory (NICAL), Department of Computer Science and Technology 230027 Hefei Anhui China

LCS & GBML Central: Community resource is now Online

LCSweb was designed to allow researchers and those seeking to use Learning Classifier Systems within applications access to material on LCS and discussion between members of the LCS community. The site served this community since its was started by Alwyn Barry in 1997. Enhanced and maintained later by Jan Drugowitsch, LCSweb became a valuable community […]

LCSweb was designed to allow researchers and those seeking to use Learning Classifier Systems within applications access to material on LCS and discussion between members of the LCS community. The site served this community since its was started by Alwyn Barry in 1997. Enhanced and maintained later by Jan Drugowitsch, LCSweb became a valuable community resource. The site was completely community-driven and allowed members to contribute to the content of the site and keeping it up to date. Later on in 2005, I started “LCS and other GBML” Blog to cover a gap providing information information regarding the International Workshop on Learning Classifier Systems (IWLCS), the collection of LCS Books available, and GBML related news.Some of you may have realized that after Jan’s move to Rochester and Alwyn’s retirement from research activities, LCSweb has vanished. Will Browne took on himself to take LCSweb to Reading, but technical circumstances have made that move rocky despite his best efforts. Jan and Will however still have a local copy of LCSweb contents. After talking to Jan and Will, I proposed to merge LCSweb with the LCS and other GBML blog, and host the new site at NCSA where dedicated resources has been made available. Jan and Will agreed with the idea.We are happy to announce that the merged site (still under the update cycle) can be reached at http://lcs-gbml.ncsa.uiuc.edu. More information about the process can be found here or at there LCS & GBML Central site.

Related Posts

    LCSweb + GBML blog = LCS & GBML Central


    LCSweb was designed to allow researchers and those seeking to use Learning Classifier Systems within applications access to material on LCS and discussion between members of the LCS community. The site served this community since its was started by Alwyn Barry in 1997. Enhanced and maintained later by Jan Drugowitsch, LCSweb became a valuable community […]

    Related posts:

    1. New blog for LCS and other GBML
    2. LCS and other GBML warming up for GECCO 2006
    3. LCSWeb creates a LCS and GBML paper database

    LCSweb was designed to allow researchers and those seeking to use Learning Classifier Systems within applications access to material on LCS and discussion between members of the LCS community. The site served this community since its was started by Alwyn Barry in 1997. Enhanced and maintained later by Jan Drugowitsch, LCSweb became a valuable community resource. The site was completely community-driven and allowed members to contribute to the content of the site and keeping it up to date. Later on in 2005, I started “LCS and other GBML” Blog to cover a gap providing information information regarding the International Workshop on Learning Classifier Systems (IWLCS), the collection of LCS Books available, and GBML related news.

    Some of you may have realized that after Jan’s move to Rochester and Alwyn’s retirement from research activities, LCSweb has vanished. Will Browne took on himself to take LCSweb to Reading, but technical circumstances have made that move rocky despite his best efforts. Jan and Will however still have a local copy of LCSweb contents. After talking to Jan and Will, I proposed to merge LCSweb with the LCS and other GBML blog, and host the new site at NCSA where dedicated resources has been made available. Jan and Will agreed with the idea.

    We are happy to announce that the merged site (still under the update cycle) can be reached at http://lcs-gbml.ncsa.uiuc.edu. More information about the process can be found here or at there LCS & GBML Central site.

    Related posts:

    1. New blog for LCS and other GBML
    2. LCS and other GBML warming up for GECCO 2006
    3. LCSWeb creates a LCS and GBML paper database

    MID-CBR meeting

    On March 19th and 20th 2009 took place the annual meeting of the MID-CBR (Marco Integrador para el Desarrollo de Sistemas de Razonamiento Basado en Casos, TIN2006-15140-C03) a coordinated project by the Instituto de Investigación de Inteligencia Artificial (IIIA-CSIC; Main Researcher: Dr. Enric Plaza), the Universidad Complutense de Madrid (GAIA-UCM; Main Researcher: Dra. Belén […]

    On March 19th and 20th 2009 took place the annual meeting of the MID-CBR (Marco Integrador para el Desarrollo de Sistemas de Razonamiento Basado en Casos, TIN2006-15140-C03) a coordinated project by the Instituto de Investigación de Inteligencia Artificial (IIIA-CSIC; Main Researcher: Dr. Enric Plaza), the Universidad Complutense de Madrid (GAIA-UCM; Main Researcher: Dra. Belén […]

    XCSLib: The XCS Classifier System Library

    for IlliGAL Report No. 2009005: The XCS Library (XCSLib) is an open source C++ library for genetics-based machine learning and learning classifier systems. It provides (i) several reusable components that can be employed to design new learning paradigms inspired to … Continue reading →

    for IlliGAL Report No. 2009005:

    The XCS Library (XCSLib) is an open source C++ library for
    genetics-based machine learning and learning classifier systems. It
    provides (i) several reusable components that can be employed to design
    new learning paradigms inspired to the learning classifier system
    principles; and (ii) the implementation of two well-known and widely
    used models of learning classifier systems.

    XCSLib: The XCS Classifier System Library

    for IlliGAL Report No. 2009005:
    The XCS Library (XCSLib) is an open source C++ library for
    genetics-based machine learning and learning classifier systems. It
    provides (i) several reusable components that can be employed to design
    new learning paradigm…

    for IlliGAL Report No. 2009005:

    The XCS Library (XCSLib) is an open source C++ library for
    genetics-based machine learning and learning classifier systems. It
    provides (i) several reusable components that can be employed to design
    new learning paradigms inspired to the learning classifier system
    principles; and (ii) the implementation of two well-known and widely
    used models of learning classifier systems.

    Related Posts

      IWLCS 2009 call for papers

      Please note a few extra days for submission as requested – see important dates.

      The Twelfth International Workshop on Learning Classifier Systems (IWLCS 2009) will be held in Montreal, Canada, Thursday, July 9, 2008 during the Genetic and Evolutionary Computation Conference (GECCO-2009), July 8-12, 2009.

      Originally, Learning Classifier Systems (LCSs) were introduced by John H. Holland as a way of applying evolutionary computation to machine learning and adaptive behavior problems. Since then, the LCS paradigm has broadened greatly into a framework that encompasses many representations, rule discovery mechanisms, and credit assignment schemes. Current LCS applications range from data mining, to automated innovation and the on-line control of cognitive systems. LCS research includes various actual system approaches: While Wilson’s accuracy-based XCS system (1995) has received the highest attention and gained the highest reputation, studies and developments of other LCSs are usually discussed and contrasted. Advances in machine learning, and reinforcement learning in particular, as well as in evolutionary computation have brought LCS systems the necessary competence and guaranteed learning properties. Novel insights in machine learning and evolutionary computation are being integrated into the LCS framework. Thus, we invite submissions that discuss recent developments in all areas of research on, and applications of, Learning Classifier Systems. IWLCS is the event that brings together most of the core researchers in classifier systems. Moreover, a free introductory tutorial on LCSs is presented the day before the workshop at GECCO 2009. Tutorial and IWLCS workshop thus also provide an opportunity for researchers interested in LCSs to get an impression of the current research directions in the field as well as a guideline for the application of LCSs to their problem domain.

      Submissions and Publication

      We welcome manuscripts of up to 8 pages in ACM format. Please see the GECCO 2009 information for authors for further format details. However, unlike GECCO, papers do not have to be submitted in anonymous format. All accepted papers will be presented at IWLCS 2009 and will appear in the GECCO workshop volume. Proceedings of the workshop will be published on CD-ROM, and distributed at the conference. Authors will be invited after the workshop to submit revised (full) papers for publication in the next post-workshop proceedings volume (scheduled for 2010), in the Springer LNCS/LNAI book series.

      All papers should be submitted in PDF format and e-mailed to: jqb@cs.nott.ac.uk

      Important dates (Updated 26.03.09)

      Paper submission deadline: Wednesday, April 1, 2009
      Notification to authors: Friday, April 8, 2009
      Submission of camera-ready material: by Friday, April 17, 2009
      Conference registration: by Monday, April 27, 2009
      Workshop date: Thursday, July 9, 2009

      Committees

      Organizing Committee

      Jaume Bacardit, University of Nottingham (UK). E-mail: jaume.bacardit@nottingham.ac.uk
      Will Browne, University of Reading (UK). E-mail: w.n.browne@reading.ac.uk
      Jan Drugowitsch, University of Rochester (USA). E-mail: jdrugowitsch@bcs.rochester.edu

      Advisory Committee

      Ester Bernadó-Mansilla, Universitat Ramon Llull (Spain)
      Martin V. Butz, Universitat Wurzburg (Germany)
      Tim Kovacs, University of Bristol (UK)
      Xavier Llorà, University of Illinois at Urbana-Champaign (USA)
      Pier Luca Lanzi, Politechnico de Milano (Italy)
      Wolfgang Stolzmann, Daimler Chrysler AG (Germany)
      Keiki Takadama, Tokyo Institute of Technology (Japan)
      Stewart Wilson, Prediction Dynamics (USA)

      Hans-Paul Schwefel to give a talk at GECCO-2009

      I just found out that Hans-Paul Schwefel, one of the evolutionary computation pioneers, is going to give a talk at the Genetic and Evolutionary Computation Conference (GECCO-2009) in Montreal, Canada (July 8-12, 2009). The talk will be part of the Learning from Failures in Evolutionary Computation (LFFEC) Workshop.
      The title of the talk is failures […]

      Hans-Paul Schwefel

      I just found out that Hans-Paul Schwefel, one of the evolutionary computation pioneers, is going to give a talk at the Genetic and Evolutionary Computation Conference (GECCO-2009) in Montreal, Canada (July 8-12, 2009). The talk will be part of the Learning from Failures in Evolutionary Computation (LFFEC) Workshop.

      The title of the talk is failures as stepping stones to success or per aspera ad astra. The abstract follows:

      The implicit thesis of this talk’s title will be underpinned with some examples from (my) real life. A first example leads back to the 1960s, when I simulated the (1+1)-ES with discrete mutations on a two-dimensional parabolic ridge by means of a Z23 computer. The result – getting stuck in certain search directions – led to making use of Gaussian variations. The second example comes from experimental investigations to determine the shape of a hot water flashing nozzle, the water being really hot and not simulated on a computer. In search for a multimembered evolutionary algorithm with effective self-adaptation of the mutation strengths, a couple of failures occurred. These, however, rendered deep insight into basic prerequisites to achieve the goal. And finally, some theory will be re-presented about the optimal failure rate in two black-box situations.

      Of course, GECCO-2009 will feature many other interesting presentations, workshops, and other events and for more information about this conference, you should visit its web page here. GECCO is organized by ACM SIGEVO (Special Interest Group on Genetic and Evolutionary Computation).