Introdução ao estudo da paralelização de algoritmos de planeamento operacional com métodos genéticos

Os Algoritmos Genéticos são técnicas de optimização, baseadas na selecção natural, que se têm vindo afirmar nos últimos anos. Existem já diversas aplicações a situações reais, com resultados bastante bons. Actualmente, com a popularização de pacotes de software para paralelização de aplicações, como o PVM, surge como natural a sua utilização na paralelização dos algoritmos genéticos. Existem várias modelos para a paralelização de algoritmos genéticos. Neste trabalho apresenta-se um estudo do software PVM, utilizando-o, numa primeira fase, para a paralelização do algoritmo de ordenação MergeSort, o que nos serviu como um bom teste para ele. No que se seguiu, verificamos a existência de viabilidade na paralelização do algoritmo genético canónico, utilizando um sistema com quatro estações de trabalho (workstations). Para isso foi feito o estudo do Algoritmo Genético Canónico, não especializado, para a resolução de um problema do caixeiro viajante de 70 cidades, sendo este bastante complexo. Posteriormente paralelizamos o algoritmo, utilizando o modelo do algoritmo genético grosseiro. Realizamos testes alterando os valores dos vários parâmetros e verificamos a obtenção de melhores resultados com o aumento do número de ilhas e com migração. Verificamos ainda que as melhorias em relação ao algoritmo sequencial foram mais acentuadas com a utilização de populações pequenas - da ordem dos 12%; com a utilização de populações grandes as melhorias foram poucas - cerca de 2%. Quanto ao tempo de execução em paralelo, verificamos que o tempo necessário à obtenção de soluções análogas às do algoritmo sequencial, corresponde aproximadamente à divisão do tempo sequencial pelo número de processadores.