EVOLUÇÃO DIFERENCIAL APLICADA AO PROBLEMA DE .XLIX Simpósio Brasileiro de Pesquisa Operacional

  • View
    212

  • Download
    0

Embed Size (px)

Text of EVOLUÇÃO DIFERENCIAL APLICADA AO PROBLEMA DE .XLIX Simpósio Brasileiro de Pesquisa Operacional

  • XLIX Simpsio Brasileiro de Pesquisa OperacionalBlumenau-SC, 27 a 30 de Agosto de 2017.

    EVOLUO DIFERENCIAL APLICADA AO PROBLEMA DE

    PROGRAMAO DA PRODUO EM SISTEMAS FLOW SHOP

    PERMUTACIONAL

    Marco Antonio Reichert Boaretto

    Programa de Ps-Graduao em Engenharia Eltrica, Departamento de Engenharia Eltrica, Universidade Federal do Paran (UFPR), Rua Cel. Francisco Herclito dos Santos, 100, Cep: 81531-980, Curitiba, PR,

    Brasil marco.boaretto@hotmail.com

    Mrcia de Ftima Morais

    Universidade Estadual do Paran Avenida Comendador Norberto Marcondes, 733, Campo Mouro, Paran

    marciafmorais@yahoo.com.br

    Leandro dos Santos Coelho

    Programa de Ps-Graduao em Engenharia Industrial e Sistemas (PPGEPS), Pontifcia Universidade Catlica do Paran (PUCPR), Imaculada Conceio, 1155, Cep: 80215-901, Curitiba, PR, Brasil

    Programa de Ps-Graduao em Engenharia Eltrica, Departamento de Engenharia Eltrica, Universidade Federal do Paran (UFPR), Rua Cel. Francisco Herclito dos Santos, 100, Cep: 81531-980, Curitiba, PR,

    Brasil

    lscoelho2009@gmail.com

    RESUMO

    O algoritmo de Evoluo Diferencial (ED) uma metaheurstica baseada em mecanismos

    evolutivos populacionais, cujas experincias em aplicaes revelaram promissor seu uso para a

    soluo de Problemas de Programao da Produo (PPP) em sistemas Flow Shop Permutacional

    (FSP). Embora diversas variaes do algoritmo de ED para o PPP em FSP tenham sido propostas,

    a influncia das estratgias de ED e da configurao dos parmetros no desempenho do algoritmo

    no tem sido objeto de muitas investigaes. Neste contexto, o propsito deste estudo foi avaliar o

    desempenho do algoritmo com diferentes estratgias de ED e diferentes valores para os parmetros

    do algoritmo de ED aplicado ao PPP em sistemas FSP. Foram avaliadas 95 combinaes de

    estratgias de ED com diferentes configuraes de valores para os parmetros e os resultados

    mostraram que as melhores estratgias de ED e os melhores valores para os parmetros variam em

    funo da dimenso do problema testado.

    PALAVRAS CHAVE. Estratgias de Evoluo Diferencial, Parmetros do Algoritmo de

    Evoluo Diferencial, Desempenho do Algoritmo.

    ABSTRACT

    The Differential Evolution (DE) algorithm is a metaheuristic based on population

    evolutionary mechanisms, whose experiences on applications have shown promise its use in the

    solution of scheduling problems in Permutational Flow Shop (PFS) systems. Although several

    variations of the DE algorithm for scheduling problem in PFS have been proposed, the influence

    of DE strategies and parameter configuration on algorithm performance has not been the subject

    of many studies. In this context, the purpose of this study was to evaluate the performance of the

    algorithm with different DE strategies and different values for the parameters of the DE algorithm

    applied to scheduling problem in PFS systems. We evaluated 95 combinations of DE strategies

    with different configurations for the values of the parameters and the results showed that the best

    DE strategies and the best values for the parameters vary according to the dimension of the problem

    tested.

    KEYWORDS. Diferential Evolution Strategies. Parameters of the Differential Evolution

    Algorithm, Performance of the Algorithm.

  • XLIX Simpsio Brasileiro de Pesquisa OperacionalBlumenau-SC, 27 a 30 de Agosto de 2017.

    1. Introduo

    O acentuado desenvolvimento dos Algoritmos Evolutivos (AEs) nas ltimas dcadas tem

    melhorado sua eficincia e aplicabilidade na soluo de problemas de otimizao nas diferentes

    reas da Engenharia e Cincia da Computao [Eiben e Smith 2015]. Os AEs tradicionalmente

    incluem Algoritmos Genticos, Programao Evolutiva, Estratgias Evolutivas e Programao

    Gentica [Brownlee 2011]. Algoritmos de Estimao de Distribuio, Evoluo Diferencial, entre

    outros mais recentemente desenvolvidos, tambm so categorizados como AEs [Simon 2013].

    O algoritmo de Evoluo Diferencial (ED), foco deste estudo, foi desenvolvido por [Storn

    e Price 1995, 1997] para soluo de problemas complexos de otimizao irrestrita e com variveis

    contnuas. O algoritmo de ED uma metaheurstica baseada em mecanismos evolutivos

    populacionais que utiliza operadores genticos de mutao, cruzamento e seleo para evoluir a

    populao de solues potenciais do problema a ser resolvido em direo ao timo global.

    O Algoritmo de ED, diferente de outros algoritmos evolutivos, no usa funes de

    distribuio de probabilidade a fim de adicionar variaes na populao, ao invs disto, usa a

    diferena de vetores aleatoriamente selecionados como fonte de variaes aleatrias [Price et al.

    2005]. Uma importante caracterstica da ED a pequena quantidade de parmetros utilizados,

    sendo eles a quantidade de indivduos/vetores mantidos na populao (Np), o fator de mutao (F),

    o fator de cruzamento (Cr) e o nmero de geraes realizadas durante o processo (iteraes) [Silva

    2009].

    Desde sua introduo, devido a sua efetividade, seus conceitos simples, sua facilidade de

    implementao e rapidez na convergncia, muitos avanos tm sido obtidos no sentido de tornar

    vivel a aplicao da abordagem de ED em diversas reas da Engenharia [Tonge e Kulkarni 2012].

    Embora o algoritmo de ED tenha sido originalmente projetado para otimizao de variveis

    contnuas [Ramos e Tupia 2013] nos ltimos anos diversas verses discretas do algoritmo de ED

    tm sido propostas na literatura.

    Experincias em aplicaes do algoritmo de ED revelaram ser promissor o seu uso para

    a soluo de Problemas de Programao da Produo (PPP) [Sun et al. 2011], [Tonge e Kulkarni

    2012], [Jarboui, Siarry e Teghen 2013] e [Allahverdi 2015]. O PPP tratado neste estudo o Flow

    Shop Permutacional (FSP), um caso especial do Flow Shop (FS).

    O FSP um tpico problema de otimizao combinatria, o qual determina a sequencia de

    processamento das tarefas nas mquinas para satisfazer algum objetivo ou critrio de desempenho

    [Mokhtari et al. 2011] e [Lin et al. 2015]. No FSP a ordem de processamento de todas as tarefas

    nas mquinas a mesma em todas as mquinas do FS [Taillard 1993].

    Embora diversas variaes do algoritmo de ED tenham sido propostas para o PPP em

    sistemas FSP, a influncia das estratgias de ED e da configurao dos parmetros no desempenho

    do algoritmo no tem sido alvo de muitas investigaes. No estudo realizado por [Carvalho et al.

    2016], cujo propsito foi identificar e analisar as variantes adotadas nos algoritmos de ED

    desenvolvidos para PPPs em sistemas FSP, no foram identificados padres especficos para a

    configurao dos parmetros dos algoritmos de ED desenvolvidos para os PPPs.

    Assim, diante do exposto, o principal propsito deste estudo foi avaliar o desempenho do

    algoritmo com diferentes estratgias de ED e diferentes valores para os parmetros do algoritmo

    de ED aplicado aos PPPs em sistemas FSP. Para o alcance de tal objetivo, a verso original do

    algoritmo de ED [Storn e Price 1995, 1997] foi adaptada para o caso de minimizao do Makespan

    em sistemas FSP.

    Este artigo encontra-se estruturado em cinco sees. Aps a contextualizao e

    ambientalizao do estudo mencionado nesta seo, o referencial terico referente ao algoritmo de

    ED e ao Mtodo de Taguchi para seleo de parmetros exposto na seo 2. O delineamento da

    experimentao apresentado na terceira seo. A quarta seo, denominada resultados e

    discusses, contempla e discute os resultados obtidos na experimentao computacional. Por fim,

    as consideraes finais so apresentadas.

    2. Evoluo Diferencial

  • XLIX Simpsio Brasileiro de Pesquisa OperacionalBlumenau-SC, 27 a 30 de Agosto de 2017.

    A Evoluo Diferencial (ED) um mtodo de busca paralela direta que tem como conceito

    bsico a utilizao de uma populao composta por Np indivduos (vetores), que representam

    solues potenciais (solues candidatas) dentro do espao de busca do problema a ser resolvido

    [Brownlee 2011].

    No algoritmo de ED a populao de solues candidatas submetida a operaes de

    mutao, cruzamento, avaliao e seleo As operaes de mutao, cruzamento, avaliao e

    seleo so repetidas gerao aps gerao at que algum critrio de parada seja satisfeito [Storn e

    Price 1997] e [Brownlee 2011].

    O algoritmo original da ED baseado em [Storn e Price, 1997], [Price et al. 2005] e [Simon

    2013] pode ser definido pelas seguintes etapas:

    1) Inicializao Nesta etapa so determinados os valores dos limites superiores (,) e inferiores (,)

    para definir o domnio em que os valores sero escolhidos. A populao inicial de vetores

    formada aleatoriamente e uniformemente distribuda entre os limites superiores e inferiores do

    problema e deve cobrir a totalidade do espao de busca. A ED usa a diferena de vetores

    aleatoriamente selecionados como fonte de variaes aleatrias para gerar o vetor alvo ,,0 da gerao inicial (g=0) da j-sima dimenso da i-sima populao, como pode ser vista na equao

    (1) a seguir:

    LjLjUjjij bbbrandx ,,,0,, )).(1,0( (1)

    onde a funo geradora de nmeros aleatrios uniformemente distribudos entre 0 e 1. O subscrito j indica que a cada parmetro gerado um valor aleatrio novo.

    2) Mutao No processo de mutao, a modificao da populao inicia-se pela gerao de novos

    indivduos denominados vetores modificados ou doadores. Para cada indivduo da populao,

    denominado vetor alvo, um vetor doador gerado. Na verso clssica do algoritmo ED, os vetores

    doadores so gerados pela adio da diferena ponderada entre d