Modification of particle swarm optimization algorithm for optimization of discrete values

Stochastic optimization algorithms are a new breed of optimizers that have recently been developed. Stochastic-type algorithms have shown good performance in locating the global optima in optimization problems, even in difficult search spaces [1). Among the stochastic optimization methods is Particle Swarm Optimization (PSO). It is inspired by the seemingly intelligent swarming behaviour of animals in nature [2). Discrete optimization refers to problems where solution elements can assume one (or more) discrete values. The general form of discrete optimization apply to problems that have solution elements which can assume n integer values [3). Discrete optimization has been used to solve various real-life problems, such as job-shop scheduling, vehicle routing, sequential ordering, graph colouring, and shortest common super sequence [4). PSO in its original form performs continuous-valued optimization. Several methods have been developed for it to perform discrete-valued optimizations. These methods generally either represent the solution in binary form [5) or round off the continuous results into the closest integer [6-8). Both methods have been successfully implemented; however they either are computationally expensive for complex, multi-valued problems, or slow to converge due to rounding of the continuous variable. We propose a novel modification to the PSO algorithm to perform rapid discrete optimization. The proposed Discrete-PSO method (DPSO) uses a rescaling equation to convert the continuous-valued positions into discrete-valued variables. Using this method, the optimization is still done in continuous form, but the solution is generated in discrete form. Rescaling of the continuous-valued solution would make the optimization faster (since it allows the particles to move at greater range at each iteration, compared to the rounding method in [6-8)) and computationally less expensive (using less particles per solution as compared to [5)). The DPSO was benchmarked against the methods in [5-8) using the Seven Integer Programming (SIP) test suite [8). The SIP test suite is a set of seven real-life discrete numerical engineering problems, and is a common benchmark for discrete optimization algorithms.