Program > By author > Abdelkafi Omar

Hybrid metaheuristics are search methods based on the combination of metaheuristics and other techniques for optimization. These techniques can be metaheuristics, heuristics, exact methods, etc. Hybrid metaheuristics are one of the most efficient classes of algorithms to solve optimization problems. With the combination of different techniques, these methods can require a longer computation time than others. This is one of the reasons that lead the community to propose parallel hybrid metaheuristics. Another reason is the evolution of highly parallel architectures like the graphics processing unit (GPU). Indeed, with the advent of CUDA (Compute Unified Device Architecture), the use of GPU for non-graphic applications has become easier and hybrid metaheuristics have taken advantage of this evolution. In this work, we propose a hybrid metaheuristic based on ant colony optimization (ACO). Our starting point is the work of J. M. Cecilia et al. Unlike them, we stay in the context of only one colony but we use the same data parallelism ideas. ACO provides the diversification of the search. Our contribution is to hybridize ACO with a parallel local search (PLS) designed for GPU. This PLS provides the intensification of the search. We also add a new heuristic to improve results. Unfortunately, this heuristic can lead the search to stagnancy. For this reason and to maintain the diversity of the population, we perform a mutation genetic operator after the execution of our heuristic. In our experimental analysis, we use a NVIDIA GeForce GTX680 GPU with 1536 CUDA cores and a processing power of 3096 Gflops. To validate our approach, we use one of the most studied combinatorial problems, i.e. the travelling salesman problem (TSP). We use well known instances from the TSPLIB. Good results are obtained, especially for some instances as, for example, berlin52 for which we have a 0.03% deviation from the optimum and an execution time of 2.8 seconds and eil51 with a 0.69% deviation from the optimum in 2.3 seconds.