DESIGN OF COOPERATIVE OPENMP-BASED METAHEURISTIC APPROACH FOR MULTI-OBJECTIVE KNAPSACK PROBLEM

Parallelism arises as an attractive option when solving Multi-Objective optimization problems (MOPs). Moreover, it seems interesting when metaheuristics demand an intensive use of CPU or memory. In this paper, we propose a parallel implementation of a hybrid ant colony optimization metaheuristic for the multiobjective knapsack problem using the OpenMP framework called MHAC_OMP. The proposed approach combined a MultiObjective Ant Colony Optimization (MOACO) algorithm with Tchebycheff based Local Search (TLS) procedure. The idea behind MHAC_OMP is to evolve several independent MOACO in parallel. Each MOACO hold a local archive to maintain diversity. The parallelization is defined as assuming a shared-memory based on threads in which the initialization phase begins with a single thread called the master thread and executed sequentially. Afterward, a parallel region is defined where many threads are created, each one of them executing its own copy of the proposed ant colony algorithm independently. Experimental results show a significant efficiency of the solutions returned over the sequential implementation.