Multi-state PSO GSA for solving discrete combinatorial optimization problems

摘要

There are various meta-heuristics exist in literature nowadays. However, not all metaheuristics were originally d~veloped to operate in discrete search space. Two examples of meta-heuristics are Particle swarm optimization (PSO) and gravitational search algorithm (GSA), which are based on the social behavior of bird flocks and the Newton's law of gravity and the law of motion, respectively. In order to solve discrete combinatorial optimization problems (COPs) using meta-heuristics, modification or enhancement is needed. In the context of the modification, a variety of discretization approaches have been proposed. Inspired by the design of a sequential circuit of digital system, a new discretization approach that leads to the establishment of a complete model of multi-state has been proposed. Based on the multi-state model, a multi-state search space is successfully built using the following two features; a current state and a radius. The multistateudmodel is then implemented in PSO and GSA. As a consequence, multi-state particle swarm optimization (MSPSO) and multi-state gravitational search algorithm (MSGSA) are developed. In the MSPSO and the MSGSA, the radius is represented by new velocity value. The extended version of the multi-state model is then formulated by introducing an embedded rule that ensures the updated solutions to be formed by unrepeated states. As a consequence, multi-state particle swarm optimization with an embedded rule (MSPSOER) and multi-state gravitational search algorithm with an embedded rule (MSGSAER) are developed. These four algorithms can be used to solve discrete combinatorial optimization problems (COPs). To evaluate the performances of the proposed algorithms, several experiments using eighteen sets of selected benchmarks instances of Travelling salesman problem (TSP) and a case study of assembly sequence planning (ASP) problem are conducted. The experimental results showed the newly introduced multi-state PSO GSA are promising compared to binary particle swarm optimization (BPSO) and binary gravitational search algorithm (BGSA) for the TSP and consistently outperformed simulated annealing (SA), genetic algorithm (GA), and BPSO for the ASP in finding optimal solutions.