DEFESA DO PROJETO DE TESE DE DOUTORADO

TÍTULO:

“Hibridização da Rede Imunológica para Otimização Combinatória: Estudos de Casos em Problemas de Sequenciamento”.

Prof. Dr. Sérgio Ricardo de Souza (Orientador)

Prof. Dr. Leandro Nunes de Castro Silva

CEFET-MG

Universidade Presbiteriana Mackenzie

Profª. Drª. Elizabeth Fialho Wanner

Prof. Dr. Moacir Felizardo de França Filho

Prof. Dr. Marcone Jamilson Freitas Souza

CEFET-MG

CEFET-MG

UFOP

LOCAL:

Auditório 101 do Prédio 17 – Departamento de Computação (DECOM), Campus II, CEFET-MG - Av. Amazonas, 7675 - Nova Gameleira

DIA:

27 de agosto de 2018 - segunda-feira

HORA:

14:00 horas

RESUMO:

Metaheurísticas para otimização baseadas na teoria da rede imunológica são frequentemente aclamadas por conseguir manter a diversidade das soluções candidatas presentes na população, permitindo uma maior cobertura do espaço de busca. Este projeto de tese, no entanto, mostra que os algoritmos derivados da família aiNet, para a solução de problemas combinatórios multimodais, podem não apresentar uma estratégia adequada de exploração do espaço de busca, levando à convergência prematura em mínimos locais. É conhecido na literatura que grande parte dos problemas destinados a otimização combinatória, necessitam de métodos de busca local para convergência para mínimos locais. Devido a necessidade de abordagens aiNet utilizarem manutenção dinâmica da população para garantir diversidade populacional, em espaços de busca multimodais com múltiplos mínimos (ou máximos) locais, estas abordagens tendem a gerar um grande número de soluções na população. Este comportamento torna a utilização de operadores de busca local impraticável, devido ao seu alto custo computacional dos mesmos. Além disto, a manutenção de soluções que já se estagnaram em mínimos locais na população, acarretam em desperdício de esforço computacional. Caso opte-se por utilizar raios de supressão elevados para redução do tamanho populacional, ou mesmo, populações com tamanhos limitados, muitas vezes, células estagnadas em mínimos locais não permitirem que outras soluções explorem a região na qual esta célula se encontra. Para tentar mitigar os aspectos levantados, é proposto uma metaheurística híbrida, denominada VNS-aiNet, a qual integra aspectos do algoritmo opt-aiNet com características do método de trajetória Variable Neighborhood Search (VNS), além de uma nova função de fitness baseada em operadores de Ageing, possibilitando escapar de mínimos locais e uma maior exploração do espaço de busca. Para avaliar o desempenho da metaheurística VNS-aiNet, é proposto a aplicação desta à resolução de um problema de sequenciamento de tarefas amplamente estudado na literatura, sendo realizados quatro estudos de caso, cada um destinado a um critério de otimização. É mostrado que o novo algoritmo apresenta uma convergência superior a duas abordagens da família aiNet destinadas a resolução de problemas combinatórios. Quando comparados as abordagens de estado-da-arte para os problemas estudados, os resultados preliminares indicaram que para três critérios de otimização, a abordagem proposta consegue alcançar resultados superiores as abordagens de estado-da-arte. Já para o objetivo mais estudado na literatura, o algoritmo proposto conseguiu atingir resultados que não há evidências estatísticas suficientes para indicar que este seja, melhor ou pior, que as abordagens estado-da-arte. 

Palavras-chave: Redes Imunológicas Artificiais, Algoritmos de Seleção Clonal, Otimização Combinatória, Scheduling.