Publicação: Algoritmo híbrido multiobjetivo para o problema flexible job shop
Carregando...
Tipo do documento
Data
Direito de acesso
Área do conhecimento
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Título da Revista
ISSN da Revista
Título de Volume
Autores
Orientador
Coorientador
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.
Palavras-chave
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
Citação
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. DOI https://doi.org/10.14393/ufu.di.2015.3