A Multi-Objective Gravitational Search Algorithm Based on Non-Dominated Sorting

Introduction

Over the last decades, several meta-heuristics have been developed to solve complex single and multi-objective optimization problems. Many real-world problems involve simultaneous optimization of several competing objectives. In these problems, there is no single optimal solution, but rather a set of non-dominated solutions, also called Pareto-optimal solutions. The use of meta-heuristics to solve multi-objective optimization problems is growing fast, because they can handle problems with concave and disconnected Pareto fronts.

There are many meta-heuristics such as Simulated Annealing (SA) (Kirkpatrick et al., 1983), Tabu Search (TS) (Glover, 1989, 1990), Evolutionary Algorithms (EAs) (Tang et al., 1996), Ant Colony Optimization (ACO) (Dorigo et al., 1996), Particle Swarm Optimization (PSO) (Kennedy & Eberhart, 1995), Gravitational Search Algorithm (GSA) (Rashedi et al., 2009) and so on. These algorithms are able to solve different optimization problems. However, there is no specific algorithm able to find the best solutions of all problems in finite iterations and some algorithms show better performances for particular problems than the others. Hence, searching for new heuristic optimization algorithms is an open problem.

Although both single and multi-agent metaheuristics have their own multi-objective variants, the multi-agent meta-heuristics such as EAs, ACO, and PSO have shown better potential to solve multi-objective optimization problems, because in a multi-objective problem, a population of solutions is going to be generated, in a single run. The multi-objective variants of the single agent meta-heuristics such as SA and TS are often working based on the definition of an aggregation function in their structure (Ulungu et al., 1999; Hansen, 1997). The use of aggregation functions may reduce the search area and provide only a subset of the Pareto front.

GSA is a new multi-agent optimization algorithm, inspired from the general gravitational law (Rashedi et al., 2009). The algorithm is based on the movement of some particles under the effect of the gravitational forces, applied by the others. Hassanzadeh and Rohani (2010) have proposed the first multi-objective variant of GSA, called Multi-Objective GSA (MOGSA). MOGSA uses an external archive to store the non-dominated solutions and uses the same idea as in Simple Multi-Objective PSO (SMOPSO), proposed by Cagnina et al. (2005), to update the external archive. For this purpose, the interval of each objective function is divided into equal divisions and consequently the entire performance space is divided into hyper-rectangles. When the number of archived members exceeds the maximum archive length, one member of the most crowded hyper-rectangle is randomly chosen and removed.

The main problem in proposing a multi-objective variant for GSA is updating the mass of particles based on the value of the multiple objectives. In MOGSA, the mass of all moving particles is set to one and the mass of archived particles is updated based on the distance from the nearest neighbor, within the objective space. However, no equation has been presented that relates the mass value to the distance value. This technique distributes the archived elements uniformly, similar to the niching technique. After calculating the mass of the moving particles, they move to the new positions by the forces applied from the archived members. In MOGSA, only the archived particles apply gravitational forces to the moving ones and after each movement, the well-known uniform mutation is applied to the new positions.