Parallel ant system applied to the multiple knapsack problem
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 para...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Objeto de conferencia |
| Lenguaje: | Inglés |
| Publicado: |
1998
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/24565 |
| Aporte de: |
| id |
I19-R120-10915-24565 |
|---|---|
| record_format |
dspace |
| institution |
Universidad Nacional de La Plata |
| institution_str |
I-19 |
| repository_str |
R-120 |
| collection |
SEDICI (UNLP) |
| language |
Inglés |
| topic |
Ciencias Informáticas Informática parallel programming distributed systems Combinatorial algorithms colony systems combinatorial optimization multiple knapsack problem |
| spellingShingle |
Ciencias Informáticas Informática parallel programming distributed systems Combinatorial algorithms colony systems combinatorial optimization multiple knapsack problem Cena, Marcelo Guillermo Leguizamón, Guillermo Parallel ant system applied to the multiple knapsack problem |
| topic_facet |
Ciencias Informáticas Informática parallel programming distributed systems Combinatorial algorithms colony systems combinatorial optimization multiple knapsack problem |
| description |
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. |
| format |
Objeto de conferencia Objeto de conferencia |
| author |
Cena, Marcelo Guillermo Leguizamón, Guillermo |
| author_facet |
Cena, Marcelo Guillermo Leguizamón, Guillermo |
| author_sort |
Cena, Marcelo Guillermo |
| title |
Parallel ant system applied to the multiple knapsack problem |
| title_short |
Parallel ant system applied to the multiple knapsack problem |
| title_full |
Parallel ant system applied to the multiple knapsack problem |
| title_fullStr |
Parallel ant system applied to the multiple knapsack problem |
| title_full_unstemmed |
Parallel ant system applied to the multiple knapsack problem |
| title_sort |
parallel ant system applied to the multiple knapsack problem |
| publishDate |
1998 |
| url |
http://sedici.unlp.edu.ar/handle/10915/24565 |
| work_keys_str_mv |
AT cenamarceloguillermo parallelantsystemappliedtothemultipleknapsackproblem AT leguizamonguillermo parallelantsystemappliedtothemultipleknapsackproblem |
| bdutipo_str |
Repositorios |
| _version_ |
1764820466240847873 |