A carregar...
Publicação
Introdução ao estudo da paralelização de algoritmos de planeamento operacional com métodos genéticos
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 6.71 MB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
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.
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.
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.
Descrição
Tese de mestrado. Engenharia Electrotécnica e de Computadores. Faculdade de Engenharia. Universidade do Porto. 199
Palavras-chave
Algoritmos paralelos Métodos genéticos
Contexto Educativo
Citação
Editora
Universidade do Porto. Faculdade de Engenharia