Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/12583
metadata.dc.type: Dissertação
metadata.dc.rights: Acesso Aberto
Title: Algoritmo híbrido multiobjetivo para o problema flexible job shop
metadata.dc.creator: Carvalho, Luiz Carlos Felix
metadata.dc.contributor.advisor1: Fernandes, Márcia Aparecida
metadata.dc.contributor.referee1: Santos, Anderson Rodrigues dos
metadata.dc.contributor.referee2: Soares, Anderson da Silva
metadata.dc.description.resumo: Flexible Job Shop (FJSP) é um importante problema de otimização combinatorial, que tem sido largamente pesquisado através de técnicas da Computação Evolutiva. Algoritmos baseados em Particle Swarm Optimization (PSO), por exemplo, têm apresentado bons resultados para esse problema, porém tendem a convergir prematuramente. Por outro lado, Algoritmos Genéticos (AGs) têm a capacidade de tratar um amplo espaço de busca, mas não garantem a convergência. O aspecto multiobjetivo desse problema tem sido tratado por ambas as técnicas. Essas características inspiraram este trabalho, que apresenta um algoritmo híbrido e multiobjetivo, baseado em PSO, operadores genéticos e definições do ótimo de Pareto por meio do procedimento Fast Non-dominated Sorting (FNS). Enquanto as características do PSO garantem a convergência, os operadores genéticos melhoram a exploração do espaço de busca. Contudo, com o objetivo de obter melhores resultados que aqueles apresentados na literatura, duas significantes inovações foram introduzidas, produzindo um novo algoritmo PSO, denominado PSO com Diversidade (DIPSO), que se mostrou eficiente para tratar o FJSP. A primeira inovação foi tomar o melhor global como o Front-1 produzido pelo ótimo de Pareto. Assim, o melhor global não é apenas um indivíduo da população como na proposta original do PSO, mas um conjunto contendo todas as melhores soluções encontradas durante a execução do algoritmo. A segunda inovação foi a criação de um operador de cruzamento, que introduziu diversidade na população e permitiu ampliar a exploração do espaço de busca. Essas duas inovações permitiram encontrar novas soluções em três das quinze instâncias do FJSP, melhorar resultados anteriormente apresentados na literatura e reproduzir diversas soluções conhecidas, demonstrando a eficiência de DIPSO para tratar o FJSP. Observa-se ainda que DIPSO é uma nova proposta para algoritmos da área de Computação Evolutiva, que pode ser utilizada em outros problemas dessa natureza. Além da abordagem descrita em DIPSO, outras propostas foram investigadas, tais como a introdução de novos objetivos para tratar o FJSP e a utilização de novas técnicas ainda não exploradas.
Abstract: Flexible Job Shop (FJSP) is an important combinatorial optimization problem that has been widely researched by means evolutionary computation techniques. Algorithms based on Particle Swarm Optimization (PSO), for example, have shown good results for this problem, but tend to converge prematurely. Moreover, Genetic Algorithms (GAs) have the ability to deal with a large search space, but do not guarantee convergence. The multiobjective aspect of this problem has been considered by both of these techniques. These features have inspired this work, which presents a hybrid and multi-objective algorithm based on PSO, genetic operators and Pareto optimal settings through the procedure Fast Non-dominated Sorting (FNS). While the PSO characteristics guarantee convergence, genetic operators improve the exploitation of the search space. However, in order to reach better results than those presented in the literature, two significant innovations were introduced and a new PSO algorithm was obtained, that it is denominated PSO using Diversity (DIPSO), which is efficient to cope with FJSP. The first innovation was to take the global best as the Front-1 produced by Pareto optimal. Then, the global best is not just an individual of the population as in the original PSO, but a set containing all the best solutions found during the algorithm execution. The second innovation was the development of a crossover operator, which introduced diversity in the population and allowed to expand exploration of the search space. These two innovations allowed to find new solutions in three of the fifteen FJSP instances, improve results previously reported in the literature and reproduce several known solutions, demonstrating the DIPSO efficiency in addressing FJSP. It has been also observed that DIPSO is a new proposal of evolutionary algorithms, which can be used in other problems of this nature. In addition to the approach described in DIPSO, other proposals were investigated, such as the introduction of new objectives for the FJSP and the use of new techniques not yet explored.
Keywords: Algoritmos evolutivos
Flexible job shop problem
Particle swarm optimization
Algoritmo genético
Non-dominated sorting genetic algorithm
Algoritmo evolutivo multiobjetivo em tabelas
Evolutionary algorithms
Genetic algorithm
Multi-objective evolutionary algorithms with many tables
Computação evolutiva
Flexible Job Shop
Otimização combinatória
metadata.dc.subject.cnpq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
metadata.dc.language: por
metadata.dc.publisher.country: BR
Publisher: Universidade Federal de Uberlândia
metadata.dc.publisher.initials: UFU
metadata.dc.publisher.department: Ciências Exatas e da Terra
metadata.dc.publisher.program: Programa de Pós-graduação em Ciência da Computação
Citation: CARVALHO, Luiz Carlos Felix. Algoritmo híbrido multiobjetivo para o problema flexible job shop. 2015. 159 f. Dissertação (Mestrado em Ciências Exatas e da Terra) - Universidade Federal de Uberlândia, Uberlândia, 2015.
URI: https://repositorio.ufu.br/handle/123456789/12583
Issue Date: 15-Jan-2015
Appears in Collections:PPGCC - Mestrado em Ciência da Computação

Files in This Item:
File Description SizeFormat 
AlgoritmoHibridoMultiobjetivo.pdf1.02 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.