A particle swarm optimizer for grouping problems

Many combinatorial optimization problems comprise a grouping phase (the grouping problem) in which the task is to partition a set of items into disjoint sets. Introduced in 1994, grouping genetic algorithm (GGA) is the only evolutionary algorithm heavily modified to suit the structure of grouping problems. In this paper we adapt the structure of the well-known particle swarm optimization algorithm (PSO) for grouping problems. To propose the grouping version of the PSO algorithm, which is called GPSO algorithm, we develop new particle position and velocity updating equations which preserve the major characteristics of the original equations and are respondent to the structure of grouping problems. The new updating equations work with groups of items rather than items isolatedly. One of the main characteristics of the new equations is that they work in continuous space but their outcome is used in discrete space through a two phase procedure. Applications of GPSO algorithm are made to the single batch–machine scheduling problem and bin packing problem, and results are compared with the results reported by GGA. Computational results testify that our algorithm is efficient and can be regarded as a new solver for the wide class of grouping problems.