Use este identificador para citar ou linkar para este item:
http://www.repositorio.ufal.br/jspui/handle/123456789/9269
Registro completo de metadados
Campo DC | Valor | Idioma |
---|---|---|
dc.contributor.advisor1 | Pinheiro, Rian Gabriel Santos | - |
dc.contributor.advisor1Lattes | http://lattes.cnpq.br/1447954471683870 | pt_BR |
dc.contributor.advisor-co1 | Nogueira, Bruno Costa e Silva | - |
dc.contributor.advisor-co1Lattes | http://lattes.cnpq.br/6805191874473768 | pt_BR |
dc.contributor.referee1 | Aquino, Andre Luiz Lins de | - |
dc.contributor.referee1Lattes | http://lattes.cnpq.br/7957606883987162 | pt_BR |
dc.contributor.referee2 | Protti, Fábio | - |
dc.contributor.referee2Lattes | http://lattes.cnpq.br/5898801580033554 | pt_BR |
dc.creator | Silva, Alfredo Lima Moura | - |
dc.creator.Lattes | http://lattes.cnpq.br/7390351886589004 | pt_BR |
dc.date.accessioned | 2022-06-20T19:41:06Z | - |
dc.date.available | 2022-06-20 | - |
dc.date.available | 2022-06-20T19:41:06Z | - |
dc.date.issued | 2021-11-12 | - |
dc.identifier.citation | SILVA, Alfredo Lima Moura. Biased random-key genetic algorithms for the minimum broadcast time problem. 2022. 61 f. Dissertação (mestrado em Informática) - Instituto de Computação, Programa de Pós-Graduação em Informática, Universidade Federal de Alagoas, Maceió, 2021. | pt_BR |
dc.identifier.uri | http://www.repositorio.ufal.br/jspui/handle/123456789/9269 | - |
dc.description.abstract | The MINIMUM BROADCAST TIME (MBT) is a well-known data dissemination problem whose goal is to find a broadcast scheme that minimizes the number of steps needed to execute the broadcast operation. The WEIGHTED MINIMUM BROADCAST TIME (WMBT) is a generalization of the MBT, such that each operation has a cost. Both problems have many applications in distributed systems, e.g., the devices update process in a peer-to-peer network. This work proposes Biased Random-Key Genetic Algorithms (BRKGA) for the MBT and WMBT. A hybrid algorithm (BRKGA + Integer Linear Programming) for the MBT. Algorithms to calculate a lower bound for the MBT and WMBT. A refinement approach and methods to create instances with known optima for the MBT and WMBT. Moreover, reducing rules for the WMBT. We carry out experiments with our BRKGA on instances commonly used in the literature and also on massive synthetic instances (up to 1000 vertices), allowing us to cover many possibilities of real industry topologies. Our proposal compared state-of-the-art exact methods and heuristics. Our algorithms outperformed the best-known heuristics for the MBT and WMBT. The experiments demonstrated they are a very good alternative when exact methods cannot be applied. For all instances for the MBT with known optima value, our approaches either attained the optimal value or missed it by at most one broadcast step. For all instances for the WMBT, our approaches attained or improved the results of literature. | pt_BR |
dc.language | eng | pt_BR |
dc.publisher | Universidade Federal de Alagoas | pt_BR |
dc.publisher.country | Brasil | pt_BR |
dc.publisher.program | Programa de Pós-Graduação em Informática | pt_BR |
dc.publisher.initials | UFAL | pt_BR |
dc.rights | Acesso Aberto | pt_BR |
dc.subject | Otimização combinatória | pt_BR |
dc.subject | Tempo mínimo de transmissão | pt_BR |
dc.subject | Metaheurísticas | pt_BR |
dc.subject | Chave aleatória enviesados (Algoritmos genéticos) | pt_BR |
dc.subject | Combinatorial Optimization | pt_BR |
dc.subject | Minimum Broadcast Time | pt_BR |
dc.subject | Metaheuristics | pt_BR |
dc.subject | Biased Random-Key (Genetic Algorithms) | pt_BR |
dc.subject.cnpq | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO | pt_BR |
dc.title | Biased random-key genetic algorithms for the minimum broadcast time problem | pt_BR |
dc.type | Dissertação | pt_BR |
dc.description.resumo | O problema TEMPO MÍNIMO DE TRANSMISSÃO (TMT) é um problema conhecido de disseminação de dados, com o objetivo é encontrar um esquema de transmissão que minimize o número de passos necessários para executar a operação de transmissão. O TEMPO MÍNIMO DE TRANSMISSÃO COM PESO (TMTP) é uma generalização do TMT, de forma que cada operação tem um custo. Ambos os problemas têm diversas aplicações em sistemas distribuídos, por exemplo, o processo de atualização de dispositivos em uma rede ponto-a-ponto. Este trabalho propõe Algoritmos Genéticos de Chave-Aleatória Enviesados (AGCAE) para o TMT e o TMTP. Um algoritmo híbrido (AGCAE + Programação Linear Inteira) para o TMT. Algoritmos para calcular um limite inferior para o TMT e o TMTP. Uma abordagem de refinamento, e métodos para criar instâncias com ótimos conhecidos para TMT e TMTP. Além disso, um método para diminuir os grafos para o TMTP. Foi realizado experimentos com o AGCAE em instâncias comumente utilizadas na literatura e também em instâncias sintéticas massivas (até 1000 vértices), o que permite cobrir muitas possibilidades de topologias reais da indústria. A proposta comparou métodos exatos e heurísticas do estado-da-arte dos problemas. Os algoritmos superaram as heurísticas mais conhecidas para TMT e TMTP. Os experimentos demonstraram que estes algoritmos são uma boa alternativa quando métodos exatos não podem ser aplicados. Para todas as instâncias do TMT com valor ótimo conhecido, os algoritmos alcançaram o valor ótimo ou no máximo uma unidade para encontrar o tempo mínimo de transmissão. Para todas as instâncias do TMTP, as abordagens alcançaram ou melhoraram os resultados da literatura. | pt_BR |
Aparece nas coleções: | Dissertações e Teses defendidas na UFAL - IC |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Biased random-key genetic algorithms for the minimum broadcast time problem.pdf | 1.33 MB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.