A hybrid estimation of distribution algorithm for the minimal switching graph problem

Minimal Switching Graph (MSG) is a graphical model for the constrained via minimization problem - a combinatorial optimization problem in integrated circuit design automation. From a computational point of view, the problem is NP-complete. In this paper we present a new approach to the MSG problem using hybrid Estimation of Distribution Algorithms (EDAs). This approach uses a Univariate Marginal Distribution Algorithm (UMDA) to sample start search points and employs a hill-climbing algorithm to find a local optimum in the basins where the start search points are located. By making use of the efficient exploration of the UMDA and the effective exploitation of the hill-climbing algorithm, this hybrid EDA can find an optimal or near-optimal solution efficiently and effectively. The hybrid EDA has been implemented and compared with the UMDA and the hill-climbing algorithm. Experimental results show that the hybrid EDA significantly outperforms both the UMDA and the hill-climbing algorithm. © 2005 IEEE.