PPGCC/CCET

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE: THIAGO HENRIQUE LEMOS FONSECA
DATA: 25/04/2018
HORA: 09:00
LOCAL: Sala de Videoconferência do NTI
TÍTULO: Heurística para sintonização de metaheurísticas aplicada aoProblema de FlowShop Permutacional
PALAVRAS-CHAVES: BRKGA, Clustering Search, Algoritmos de Corrida, Metaheurísticas, Otimização, Sintonização.
PÁGINAS: 95
GRANDE ÁREA: Ciências Exatas e da Terra
ÁREA: Ciência da Computação
RESUMO: Muitos problemas de Otimização Combinatória são considerados NP-Difíceis e portanto requerem um alto custo computacional para serem resolvidos por algoritmos exatos. Uma alternativa promissora é a utilização de metaheurísticas, modelos algorítmicos genéricos capazes de encontrar boas soluções para problemas de otimização complexos em tempo razoável. Contudo, paraque as metaheurísticas obtenham soluções de qualidade, parâmetros de diversos tipos devem ser calibrados. Ao problema de encontrar o melhor ajuste para esses parâmetros dá-se o nome de Sintonização. Usualmente, o processo de encontrar configurações ótimas em um espaço de busca de parâmetros possui dificuldade igual ou superior à busca de soluções ótimas no espaço de soluções do problema, tal obstáculo torna o estudo da sintonização pouco atrativo aos pesquisadores, que preferem abordagens mais baratas baseadas em tentativa e erro ou experiência de especialistas. Como não existe um padrão na sintonização, pesquisadores alteram seus parâmetros seguindo abordagens próprias que influenciam de diferentes modos a eficácia de seus algoritmos, dificultando a comparação e aperfeiçoamento dos mesmos devido a aspectos pouco mensuráveis. Este trabalho apresenta um método de sintonização heurístico denominado Cross-Validated Racing (CVR) que agrega validação cruzada ao processo de sintonização por corrida buscando alcançar uma perspectiva de generalização por Aprendizagem de Máquina, obtendo assim soluções de qualidade para instâncias desconhecidas Para a validação do CVR, um algoritmo genético de chaves aleatórias e viciadas híbrido (BRKeCS) foi projetado e aplicado para resolver Problemas do tipo FlowShop Permutacional com instâncias randômicas e realistas. Os resultados computacionais demonstraram que a CVR é robusto ao encontrar uma configuração de parâmetro efetiva com um erro residual médio de menos de 2.3% quando comparado com outras metaheurísticas desenvolvidas especialmente para o problema uma vez que requer processo de treinamento em apenas metade do conjunto total de instâncias. Também verificou-se a estabilidade da qualidade de soluções do CVR quando a topologia do espaço de busca é modificada pela alteração de instâncias aleatórias para as realísticas.
MEMBROS DA BANCA:
Presidente - 1091306 - ALEXANDRE CESAR MUNIZ DE OLIVEIRA
Interno - 2319041 - PAULO ROGERIO DE ALMEIDA RIBEIRO
Externo à Instituição - ANTONIO AUGUSTO CHAVES - UNIFESP