Doutorado em Modelagem Matemática e Computacional

URI Permanente para esta coleção

https://repositorio.cefetmg.br//handle/123456789/648

Navegar

Navegando Doutorado em Modelagem Matemática e Computacional por Assunto "Algoritmos genéticos"

Agora exibindo 1 - 2 de 2
  • Imagem de Miniatura
    Item
    Análise e síntese de regras de adaptação em estratégias evolutivas usando funções de Lyapunov estocásticas
    (Centro Federal de Educação Tecnológica de Minas Gerais, 2019-02-28) Corrêa, Cláudia Raquel Martins; Wanner, Elizabeth Fialho; Fonseca, Carlos Manuel Mira da; http://lattes.cnpq.br/0398907021926383; http://lattes.cnpq.br/2243256075052322; http://lattes.cnpq.br/0859784566522265; Wanner, Elizabeth Fialho; Fonseca, Carlos Manoel Mira da; Peres, Pedro Luis Dias; Takahashi, Ricardo Hirsohi Caldeira; Souza, Sérgio Ricardo de; Cardoso, Rodrigo Tomás Nogueira
    As Estratégias Evolutivas (EEs) constituem uma classe particular de Algoritmos Evolutivos (AEs). As pesquisas que tratam da análise de estratégias evolutivas têm sido focadas nas aplicações destes algoritmos, usados para resolver problemas das mais diversas áreas, principalmente em espaços de busca contínuos, mas também em espaços discretos. As investigações das EEs também demonstram que estes algoritmos, ainda suscetíveis a diversas pesquisas, são eficientes e populares. Uma análise contendo provas rigorosas de convergência de EEs é uma tarefa difícil devido à estocasticidade destes algoritmos, apesar desta aleatoriedade permitir sua análise sob uma perspectiva matemática. Neste trabalho são propostas Estratégias Evolutivas com um único progenitor e λ descendentes (1 +, λ)-EE. Na primeira delas, o tamanho do passo do algoritmo é modificado de acordo com uma regra de adaptação simples baseada em sucesso, denominada Regra 1. Uma extensão desta regra de adaptação do tamanho do passo, denominada Regra 2, também é proposta. Nesta estratégia o tamanho do passo é adaptado de acordo com o número de descendentes bem sucedidos. Além destas, a generalização a qualquer número de descendentes e qualquer limiar, de uma EE com controle de mutação baseado no tamanho do passo, também é explorada e nomeada Regra 3. Finalmente é formulada uma EE com regra de adaptação do tamanho do passo baseada na combinação da Regra 1 com a Regra 3. A análise teórica destes algoritmos evolutivos concentra-se na investigação sobre sua convergência, quando aplicados em problemas de otimização em espaços de busca contínuos em uma classe de funções estritamente unimodais de uma variável. O estudo sobre a convergência das EEs segue uma abordagem usando funções de Lyapunov estocásticas, no contexto da teoria de martingais. Expressões gerais para as esperanças condicionais dos próximos valores do tamanho do passo e para a distância para o ótimo são analiticamente derivadas para todas as Estratégias, e uma função de Lyapunov apropriada é construída. Os limites superiores da taxa de convergência, bem como os valores dos parâmetros de adaptação, são obtidos através da otimização numérica para valores crescentes de λ, permitindo também uma seleção informada desse parâmetro. Os resultados experimentais contribuem para uma análise dos limites de convergência teóricos obtidos e fornecem uma visão adicional sobre os pontos fortes e fracos da metodologia adotada.
  • Imagem de Miniatura
    Item
    Estratégias de solução baseadas em paralelismo CUDA para o problema de instalação de fibras em redes óticas
    (Centro Federal de Educação Tecnológica de Minas Gerais, 2023-08-18) Reis, Daniel Morais dos; Souza, Sérgio Ricardo; Barrientos, Anolan Yamilé Milanés; http://lattes.cnpq.br/8899693603008522; http://lattes.cnpq.br/3677015295211434; http://lattes.cnpq.br/2020021419382172; Souza, Sérgio Ricardo; Barrientos, Anolan Yamilé Milanés; Coleho, Igor Machado; Fernandes, Gustavo Alves; Menezes, Gustavo Campos; Souza, Marcone Jamilson Freitas
    Este trabalho otimiza métodos sequenciais e propõe métodos heurísticos paralelizados em GPUs Nvidia CUDA para a solucionar o Problema de Instalação de Fibras em Redes Óticas - PIFRO. O PIFRO consiste em alocar, em uma rede ótica que utiliza tecnologia Wavelength Division Multiplexing (WDM), um conjunto de requisições previamente conhecidas com múltiplas origens e destinos. O objetivo é minimizar o custo total dos dispositivos necessários para a operação da rede. Após provar que a versão de decisão do PIFRO é NP-Difícil, é realizada uma formulação matemática e implementadas duas metaheurísticas paralelizadas em formatos inéditos, buscando a melhoria dos resultados da literatura. Uma das heurísticas é baseada em Biased Random Key Genetic Algorithm (BRKGA) e a outra é baseada em Iterated Local Search (ILS) as quais foram selecionadas pelos bons resultados existentes para o problema. Os conceitos básicos de processamento paralelo são analisados e selecionados para execução de novas metaheurísticas em ambientes heterogêneos com GPUs