GENETIC ALGORITHM FOR EMBEDDING A COMPLETE GRAPH IN A HYPERCUBE WITH A VLSI APPLICATION

The embedding of a complete graph in a minimum sized hypercube is an i mportant problem which models the classical state encoding problem of Finite State Machines (FSMs). As this problem is an NP-hard optimizati on problem, acceptable final solutions are generally obtained by emplo ying heuristic methods or Simulated Annealing (SA). In this paper the efficacy of a Genetic Algorithm (GA) for this problem is studied. This study includes a comparison of three different crossover methods of G A along with their implementation details and their suitability for th is embedding problem. The experimental results on a number of MCNC ben chmark FSMs indicate the superiority of GA in finding a better (near o ptimal) solution than a heuristic solution. These results experimental ly establish the time efficiency of GA over SA for this embedding prob lem.