Applying genetic algorithms to the state assignment problem: a case study

Jose Nelson Amaral; Kagan Tumer; Joydeep Ghosh

doi:10.1117/12.139933

20 August 1992 Applying genetic algorithms to the state assignment problem: a case study

Jose Nelson Amaral, Kagan Tumer, Joydeep Ghosh

Proceedings Volume 1706, Adaptive and Learning Systems; (1992) https://doi.org/10.1117/12.139933
Event: Aerospace Sensing, 1992, Orlando, FL, United States

Abstract

Finding the best state assignment for implementing a synchronous sequential circuit is important for reducing silicon area or chip count in many digital designs. This State Assignment Problem (SAP) belongs to a broader class of combinatorial optimization problems than the well studied traveling salesman problem, which can be formulated as a special case of SAP. The search for a good solution is considerably more involved for the SAP than it is for the traveling salesman problem due to a much larger number of equivalent solutions, and no effective heuristic has been found so far to cater to all types of circuits. In this paper, a matrix representation is used as the genotype for a Generic Algorithm (GA) approach to this problem. A novel selection mechanism is introduced, and suitable genetic operators for crossover and mutation, are constructed. The properties of each of these elements of the GA are discussed and an analysis of parameters that influence the algorithm is given. A canonical form for a solution is defined to significantly reduce the search space and number of local minima. Simulation results for scalable examples show that the GA approach yields results that are comparable to those obtained using competing heuristics. Although a GA does not seem to be the tool of choice for use in a sequential Von-Neumann machine, the results obtained are good enough to encourage further research on distributed processing GA machines that can exploit its intrinsic parallelism.

Citation Download Citation

Jose Nelson Amaral, Kagan Tumer, and Joydeep Ghosh "Applying genetic algorithms to the state assignment problem: a case study", Proc. SPIE 1706, Adaptive and Learning Systems, (20 August 1992); https://doi.org/10.1117/12.139933

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available