Share Email Print

Proceedings Paper

Applying genetic algorithms to the state assignment problem: a case study
Author(s): Jose Nelson Amaral; Kagan Tumer; Joydeep Ghosh
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper 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.

Paper Details

Date Published: 20 August 1992
PDF: 12 pages
Proc. SPIE 1706, Adaptive and Learning Systems, (20 August 1992); doi: 10.1117/12.139933
Show Author Affiliations
Jose Nelson Amaral, Univ. of Texas/Austin (United States)
Kagan Tumer, Univ. of Texas/Austin (United States)
Joydeep Ghosh, Univ. of Texas/Austin (United States)

Published in SPIE Proceedings Vol. 1706:
Adaptive and Learning Systems
Firooz A. Sadjadi, Editor(s)

© SPIE. Terms of Use
Back to Top