Azevedo, Ana2014-02-142014-02-141997http://hdl.handle.net/10400.22/3922Tese de mestrado. Engenharia Electrotécnica e de Computadores. Faculdade de Engenharia. Universidade do Porto. 199Os 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.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.porAlgoritmos paralelosMétodos genéticosmaster thesis