Discrete particle swarm optimization based on estimation of distribution for terminal assignment problems

Terminal assignment problem (TEAP) is to determine minimum cost links to form a network by connecting a given set of terminals to a given collection of concentrators. This paper presents a novel discrete particle swarm optimization (PSO) based on estimation of distribution (EDA), named DPSO-EDA, for TEAP. EDAs sample new solutions from a probability model which characterizes the distribution of promising solutions in the search space at each generation. The DPSO-EDA incorporates the global statistical information collected from personal best solutions of all particles into the PSO, and therefore each particle has comprehensive learning and search ability. In the DPSO-EDA, a modified constraint handling method based on Hopfield neural network (HNN) is also introduced to fit nicely into the framework of the PSO and thus utilize the merit of the PSO. The DPSO-EDA adopts the asynchronous updating scheme. Further, the DPSO-EDA is applied to a problem directly related to TEAP, the task assignment problem (TAAP), in order to show that the DPSO-EDA can be generalized to other related combinatorial optimization problems. Simulation results on several problem instances show that the DPSO-EDA is better than previous methods. (C) 2010 Elsevier Ltd. All rights reserved.