Abstract

Combinatorial optimization problems arise in many applications, e.g., task assignment, facility location, and elevator scheduling.  A variety of population-based methods have been used to solve these problems, such as genetic algorithm (GA), particle swarm optimization (PSO), estimation of distribution algorithms (EDA), and nested partitions (NP).  Some of them, however, lack global convergence guarantee such as PSO, or require strict convergence assumptions such as NP.  To enhance these methods in terms of convergence, a novel framework towards unifying the seemingly unrelated methods is established as iterative sampling and updating of a population distribution, and the methods that fit into this framework are called population distribution-based methods.  Global convergence conditions for this framework are innovatively developed by building a shadow NP structure for the population evolution process.  The result is generic and is capable of covering or enhancing the current convergence results of many methods including GA, PSO, EDA, and NP.  It can be further exploited to improve algorithm performance or computational efficiency, and opens up a new door to re-examine old methods and create new ones.