Publicação
Introdução ao estudo da paralelização de algoritmos de planeamento operacional com métodos genéticos
| dc.contributor.author | Azevedo, Ana | |
| dc.date.accessioned | 2014-02-14T16:10:21Z | |
| dc.date.available | 2014-02-14T16:10:21Z | |
| dc.date.issued | 1997 | |
| dc.description | Tese de mestrado. Engenharia Electrotécnica e de Computadores. Faculdade de Engenharia. Universidade do Porto. 199 | por |
| dc.description.abstract | 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. | por |
| dc.description.abstract | 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. | por |
| dc.identifier.uri | http://hdl.handle.net/10400.22/3922 | |
| dc.language.iso | por | por |
| dc.peerreviewed | yes | por |
| dc.publisher | Universidade do Porto. Faculdade de Engenharia | por |
| dc.subject | Algoritmos paralelos | por |
| dc.subject | Métodos genéticos | por |
| dc.title | Introdução ao estudo da paralelização de algoritmos de planeamento operacional com métodos genéticos | por |
| dc.type | master thesis | |
| dspace.entity.type | Publication | |
| oaire.citation.conferencePlace | Porto | por |
| person.familyName | Azevedo | |
| person.givenName | Ana | |
| person.identifier.ciencia-id | D913-646F-CE08 | |
| person.identifier.orcid | 0000-0003-0882-3426 | |
| person.identifier.rid | H-3955-2011 | |
| person.identifier.scopus-author-id | 25960566000 | |
| rcaap.rights | openAccess | por |
| rcaap.type | masterThesis | por |
| relation.isAuthorOfPublication | d86b3493-7f70-42bd-a134-7724288f02b1 | |
| relation.isAuthorOfPublication.latestForDiscovery | d86b3493-7f70-42bd-a134-7724288f02b1 |