Parallel genetic algorithms on combinatorial optimization problems

• Francisco Hidrobo Universidad de Los Andes-Venezuela
• José Aguilar Universidad de Los Andes-Venezuela

Resumo

In this work, we introduce several parallel approaches based on Genetic Algorithms to solve NP-complete problems. Each approach uses a different concept of the parallel computing. A first approach exploits the implicit parallelism in the internal operation of this technique. The second approach perform a decomposition of the solutions space in order to carry out a detailed search through each one of them using several Genetic Algorithms. The last approach proposes a reinforced algorithm of search for the Genetic Algorithms based on concepts of the Collective Intelligence theory. In order to prove and compare the parallel approaches, the Graph Partitioning and Travelling Salesman Problems are studied. The parallel library used Is PVM (Parallel Virtual Machine) and the tests were performed on a SP2-IBM with 8 nodes.