PMPSO: A near-optimal graph planarization algorithm using probability model based particle swarm optimization

摘要

Particle swarm optimization (PSO) has gained increasing attention in dealing with complex optimization problems. Nevertheless it still has some drawbacks, such as slow convergence and the tendency to become trapped in local minima. To overcome the local minimum problem of the PSO, a probability model inspired by the estimation distribution algorithm is incorporated into the PSO. The solutions generated by PSO are utilized to construct a probability vector which is thereafter utilized to guide the search to promising search space. The proposed probability model based particle swarm optimization (PMPSO) is used to solve the graph planarization problem (GPP) based on the single-row routing representation. Experimental results indicate that PSO that handles binary values for the problem can be applied on GPP, and the PMPSO is capable of obtaining competitive solutions when compared with other state-of-art algorithms.