Genetic beam search for gate matrix layout

The paper presents a novel implementation of the genetic algorithm in combination with beam search for gate matrix layout. This is a permutation problem, for which the traditional genetic crossover operator results in repetition of gates, and therefore the GA is not applicable without modification. However, the GA is a very efficient stochastic optimisation technique, and is easily parallelisable. To adapt it to the gate matrix layout problem, the principles of beam search have been used. The gates are ranked according to their connectivity with each other, and the ranks of the gates to be placed next to each other are picked by the GA. A beam value is used to restrict the ranks of the gates placed next to each other to a low value. This reduces the search space to be explored, and thus results in a more efficient search. The algorithm produces better results compared to a graph-theoretic approach on published netlists