Parallel ant system applied to the multiple knapsack problem

Abstract

Interesting real world combinatorial problems are NP-complete and many of them are hard to solve by using traditional methods. However, several heuristic methods have been developed in order to obtain timely suboptimal solutions. Most of those heuristic methods are also naturally suitable for a parallel implementation and consequently, an additional improvement on the response time can be obtained. One way of increasing the computational power is by using multiple processors operating together on a single problem.

The overall problem is split into parts, each of which is operated by a separate processor in parallel. Unfortunately problems cannot be divided perfectly into separate parts and interaction is necessary between the parts like data transfer and process synchronization. However, substantial improvement can be achieved, depending on the problem and the amount of parallelism in the problem. Our work aims to exploit the capability of a distributed computing environment by using PVM and implementing a parallel version of an Ant System for solving the Multiple Knapsack Problem (MKP). An Ant System (a distributed algorithm) is a set of agents working independently and cooperating sporadically in a common problem solving activity. Regarding the above characteristics, an Ant System can be naturally considered as a nearly embarrassingly parallel computation. The proposed parallel implementations of an Ant System are based on two different approaches, static and dynamic task assignment. The computational study involves processors of different velocities and several MKP test cases of different sizes and difficulties (tight and loose constraints). The performance on the response time is measured by two indexes, Speedup Factor and Efficiency when is compared to a serial version of an Ant System. The results obtained show the potential power of exploiting the parallelism underlying in an Ant System regarding the good quality of the results and a remarkable decreasing on the computation time.