Algoritmo de evolução diferencial com parâmetros auto-adaptativos aplicado ao problema de alocação de confiabilidade-redundância

Orientador: Prof. Dr. Gustavo Valentim LochDissertação (mestrado) - Universidade Federal do Paraná, Setor de Tecnologia, Programa de Pós-Graduação em Métodos Numéricos em Engenharia. Defesa: Curitiba, 14/02/2017Inclui referênciasResumo: Os problemas de otimização combinatória, atualmente, recebem grande atenção nas pesquisas acadêmicas e aplicações. As primeiras pesquisas, a partir da década de 1940, limitavam-se a resolução de problemas de programação linear, mas a evolução computacional nas décadas seguintes expandiu os estudos para problemas inteiros e também para não-lineares. Dentre os problemas não-lineares inteiro-misto, destaca-se o problema de alocação de confiabilidade-redundância. As características deste problematornam sua resolução difícil, mesmo para pequenas instâncias. Logo, durante as últimas décadas foram propostas diversas técnicas para sua resolução, muitas dessas utilizando e adaptando abordagens de metaheurísticas evolutivas. Nesse grupo, destaca-se o algoritmo de Evolução Diferencial, por sua simplicidade e bom desempenho. Porém, ainda que eficaz, apresenta algumas deficiências, em relação a existência de parâmetros fixados inicialmente em seus operadores. Assim, se tornando uma tarefa extra a escolha desses parâmetros, sendo diferente a cada problema. Nesse âmbito, foram apresentadas propostas de usar algoritmos que auto-adaptassem os parâmetros. Neste trabalho toma-se como foco o algoritmo de Evolução Diferencial com Mutação Auto-adaptativa (SaMDE). O algoritmo SaMDE foi proposto recentemente em (SILVA, 2010), e até então não tem muitas aplicações divulgadas na literatura. É de conhecimento que sua convergência embora eficaz, precisa ser melhorada. Logo, a presente dissertação propõe uma versão híbrida com o algoritmo de Busca por Enxame de Partículas (PSO), para agregar vantagens ao processo de busca do SaMDE, com o objetivo de melhorar o desempenho e a convergência do algoritmo SaMDE para o problema de alocação de confiabilidade-redundância. Tanto a versão híbrida quanto o SaMDE foram aplicados a exemplos clássicos da literatura para o problema de alocação de confiabilidade-redundância, sendo para o sistema em série, série-paralelo e complexo. A versão híbrida proposta apresentou melhora, comparada ao algoritmo SaMDE, no caso de problemas em série e complexo. Ambas obtiveram convergência próxima aos melhores resultados conhecidos na literatura. Palavras-chave: Evolução Diferencial, Auto-adaptação, Alocação de redundância-confiabilidade.Abstratc: Combinatorial optimization problems are currently receiving great attention in academic research and applications. The first researches, from the 1940s, were limited to solving linear programming problems, but computational evolution in the following decades expanded the studies to whole problems as well as to non-linear ones. Among the non-linear integer-mixed problems, the problem of reliabilityredundancy allocation is highlighted. The characteristics of this problem make its resolution difficult, even for small instances. Therefore, during the last decades several techniques have been proposed for their resolution, many of them using and adapting approaches of evolutionary metaheuristics. In this group, the Differential Evolution algorithm stands out for its simplicity and good performance. However, although effective, it presents some deficiencies, in relation to the existence of parameters to be initially set in its operators. Thus, it becomes an extra task to choose these parameters, being different to each problem. In this context, the proposal came up to use algorithms that would auto-adapt the parameters. This work focuses on the algorithm of Differential Evolution with Auto-adaptive Mutation (SaMDE). The SaMDE algorithm was recently proposed in (Silva, 2010), and until then has not many applications published in the literature. It is well known that its convergence, although effective, needs to be improvedTherefore, this work proposes a hybrid version with the Particle Swarm Search algorithm (PSO), to add advantages to the search process of SaMDE, with the objective of improving the performance and convergence of the SaMDE algorithm for the allocation problem of Reliabilityredundancy. Both the hybrid version and the SaMDE were applied to classic examples of the literature for the problem of reliability-redundancy allocation, being for serial, parallel-series and complex systems. The proposed hybrid version presented improvement, compared to the SaMDE algorithm, in the case in series and complex. Both obtained convergence close to the best results known in the literature. Key-words:Differential Evolution, Self-adaptation, Allocation of redundancyreliability