UNIVERSIDADE ESTADUAL PAULISTA “JÚLIO MESQUITA FILHO” CAMPUS DE GUARATINGUETÁ PÓS-GRADUAÇÃO EM ENGENHARIA MECÂNICA ÁREA GESTÃO E OTIMIZAÇÃO LINHA GESTÃO DA QUALIDADE E ENGENHARIA ORGANIZACIONAL DIFERENTES MÉTODOS DE AGLUTINAÇÃO PARA MELHORIA DE PROCESSOS COM MÚLTIPLAS RESPOSTAS Orientador: Prof. Dr. Messias Borges Silva Co-orientador: Prof. Dr. Fernando Augusto Silva Marins Doutorando: Fabrício Maciel Gomes Guaratinguetá 2015 FABRÍCIO MACIEL GOMES DIFERENTES MÉTODOS DE AGLUTINAÇÃO PARA MELHORIA DE PROCESSOS COM MÚLTIPLAS RESPOSTAS Tese a ser apresentado à Faculdade de Engenharia do Campus de Guaratinguetá, Universidade Estadual Paulista, para a obtenção do título de Doutor em Engenharia Mecânica na área de Gestão e Otimização. Orientador: Prof. Dr. Messias Borges Silva Co-orientador: Prof. Dr. Fernando Augusto Silva Marins Guaratinguetá 2015 G633d Gomes, Fabrício Maciel Diferentes métodos de aglutinação para melhoria de processos com múltiplas respostas / Fabrício Maciel Gomes – Guaratinguetá, 2015 111 f : il. Bibliografia: f. 83-88 Tese (doutorado) – Universidade Estadual Paulista, Faculdade de Engenharia de Guaratinguetá, 2015. Orientador: Prof. Dr. Messias Borges Silva Coorientador: Prof. Dr. Fernando Augusto Silva Marins 1. Processo decisório por critério múltiplo 2. Programação heurística 3. Métodos de simulação 4. Otimização combinatória I. Título CDU 65.012.4(043) DEDICATÓRIA À minha esposa Patrícia que esteve sempre ao meu lado, e aos meus filhos Yago e Yan que são a razão da minha existência. AGRADECIMENTOS Ao Prof. Dr. Messias Borges Silva pela orientação e apoio ao desenvolvimento deste trabalho. Ao Prof. Dr. Fernando Augusto Silva Marins, pelo incentivo e brilhantes sugestões no período de desenvolvimento desta pesquisa. Ao Prof. Dr. Félix Monteiro Pereira, pela ajuda crucial no desenvolvimento dos códigos computacionais empregados nesta Tese. Aos meus pais, Wilton Joras Gomes e Laís Helena Maciel Gomes, meus grandes incentivadores sempre. Aos meus irmãos, Leonardo Maciel Gomes e Guilherme Maciel Gomes, que sempre acreditaram em mim de maneira incondicional. Ao Prof. Dr. Aneirson Francisco da Silva, que sempre tinha uma sugestão para melhorar esta Tese. Ao meu amigo Ricardo Batista Penteado que sofreu junto comigo no período de desenvolvimento deste trabalho. Aos Professores Doutores Valério Salomon Pamplona e Jorge Muniz Júnior, cuja a companhia na hora do almoço na FEG sempre tinham uma palavra amiga e de incentivo. À todas as pessoas que direta ou indiretamente contribuíram para a realização deste trabalho. GOMES, F.M. Diferentes Métodos de Aglutinação para Melhoria de Processos com Múltiplas Respostas. 2015. 110f. Tese (Doutorado em Engenharia Mecânica) – Faculdade de Engenharia do Campus de Guaratinguetá, Universidade Estadual Paulista, Guaratinguetá, 2015. RESUMO Empresas não medem esforços para aperfeiçoar seus processos e produtos de acordo com diferentes critérios para satisfazer as exigências e necessidades dos clientes em busca de um padrão de competitividade superior ao de suas concorrentes. Neste cenário é muito comum a necessidade de se estabelecer condições que resultem na melhoria de mais de um critério de forma simultânea. Neste trabalho foi realizada uma avaliação da utilização de quatro métodos que utilizam as Meta-heurísticas Recozimento Simulado, Algoritmo Genético, Recozimento Simulado combinado com o método Nelder Mead Simplex e algoritmo genético combinado com o método Nelde-Mead simplex para o estabelecimento de melhoria das condições de processos com múltiplas respostas. Para a avaliação dos métodos propostos foram utilizados problemas-teste criteriosamente selecionados na literatura de forma a serem analisados casos com diferente número de variáveis, número de respostas e tipos de resposta. A aglutinação das respostas foi realizada por quatro métodos diferentes: Desirability, Desvio Médio Percentual, Programação por Compromisso e Programação por Compromisso normalizada pela distância euclidiana. A avaliação dos métodos foi realizada por meio de comparação entre os resultados obtidos na utilização de um mesmo método de aglutinação, determinando assim a eficiência do método de busca. Os resultados obtidos na avaliação dos métodos sugerem a aplicação do método do algoritmo genético quando se pretende estabelecer parâmetros que resultem na melhoria de processos com múltiplas respostas, em particular quando essas respostas são modeladas por equações com termos cúbicos, independentemente do número de termos que possam conter, do tipo de respostas e do número de variáveis. PALAVRAS-CHAVE: Meta-heurística, Planejamento de Experimentos, Processos com Múltiplas Respostas, Algoritmo Genético, Recozimento Simulado, Nelder Mead Simplex, Desirability e Gradiente Reduzido Generalizado. GOMES, F.M. Different Agglutination Methods for Optmize a Process whit Multiple Responses. 2015. 110f. Thesis (Doctorade in Mechanical Engineering) – Faculdade de Engenharia do Campus de Guaratinguetá, Universidade Estadual Paulista, Guaratinguetá, 2015. ABSTRACT Companies go to great lengths to improve its processes and products according to different criteria to meet the demands and needs of customers looking for a higher standard of competitiveness to that of their competitors. This scenario is very common the need to establish conditions that result in the improvement of more than one criterion simultaneously. This work was carried out an evaluation of the use of four methods that use Metaheuristics Simulated Annealing, Genetic Algorithms, Simulated Annealing combined with the Nelder Mead Simplex method and genetic algorithm combined with Nelde Mead simplex method for the improvement of establishing the conditions of processes with multiple answers. For the evaluation of the proposed test methods were used in the literature problems carefully selected in order to be analyzed cases with different numbers of variables, response numbers and types of responses. In this research we used the average percentage deviation function as a way to bring together the answers. The agglutination of the answers was performed by four different methods: Desirability, Average Percentage Deviation, Compromise Programming and Compromise Programming normalized by Euclidean distance. The evaluation method was performed by comparison between the results obtained in using the same bonding method, thereby determining the efficiency of the search method. The results obtained in the evaluation of the methods suggest the application of the genetic algorithm method when you want to set parameters that result in the improvement of processes with multiple answers, particularly when these responses are modeled by equations with cubic terms, regardless of the number of terms that can contain the type of responses and the number of variables. KEYWORDS: Meta-heuristics, Design of Experiments, Multiple Responses Process, Genetic Algorithm, Simulated Annealing, Nelder Mead Simplex, Desirability and Generalized Reduced Gradient. LISTA DE FIGURAS Figura 1: Exemplos de ponto de máximo e de mínimo em uma função. ....................... 17 Figura 2: Etapas da pesquisa .......................................................................................... 22 Figura 3: Publicações com relação a utilização do DOE com Meta-heurísticas ............ 23 Figura 4: Gráfico de pizza para áreas das publicações de Meta-heurísticas x DOE ...... 24 Figura 5: Pseudocódigo da meta-heurística Recozimento Simulado ............................. 37 Figura 6: Pseudocódigo da meta-heurística AG ............................................................. 39 Figura 7: Cruzamento em ponto único. .......................................................................... 41 Figura 8: Cruzamento em ponto duplo ........................................................................... 41 Figura 9:Cruzamento em pontos aleatórios .................................................................... 42 Figura 10:Mutação aleatória ........................................................................................... 43 Figura 11: Mutação por troca ......................................................................................... 43 Figura 12: Quatro operações báscias do método Simplex de Nelder Mead. (a) Reflecção usando o ponto R; (b) expansão usando o ponto E; (c) contração usando o ponto C; e (d) Múltipla Contração na direção de B. .............................................................................. 45 Figura 13: Pseudocódigo do algoritmo de Nelder Mead Simplex.................................. 46 Figura 14: Representação da metodologia utilizada para a melhoria de processos utilizando Recozimento Simulado .................................................................................. 57 Figura 15: Representação da metodologia utilizada para a melhoria de processos utilizando Algoritmo Genético ....................................................................................... 58 Figura 16: Representação da metodologia utilizada para a melhoria de processos utilizando Recozimento Simulado combinado com o método Nelder Mead Simplex ... 59 Figura 17: Representação da metodologia utilizada para a melhoria de processos utilizando Algoritmo Genético combinado com o método Nelder Mead Simplex ........ 61 Figura 18: Gráficos correlacionando a Distância Percentual Média (eixo das ordenadas) com o número de iterações (eixo das abscissas) em função da temperatura inicial. ...... 63 Figura 19:Gráficos correlacionando a Distância Percentual Média (eixo das ordenadas) com o número de iterações (eixo das abscissas) em função da taxa de resfriamento. ... 64 Figura 20:Gráficos correlacionando a Distância Percentual Média (eixo das ordenadas) com o número de iterações (eixo das abscissas) em função do incremento para criação de novos vizinhos. .......................................................................................................... 65 Figura 21: Gráficos correlacionando a Distância Percentual Média (eixo das ordenadas) com o número de iterações (eixo das abscissas) em função do número de repetições a cada incremento de temperatura. .................................................................................... 65 Figura 22: Gráficos correlacionando a Distância Percentual Média (eixo das ordenadas) com o número de iterações (eixo das abscissas) em função do número de respostas geradas a cada repetição realizada. ................................................................................. 66 Figura 23: Gráficos correlacionando a Distância Percentual Média (eixo das ordenadas) com o número de gerações (eixo das abscissas) em função do número total de gerações realizadas. ....................................................................................................................... 68 Figura 24: Gráficos correlacionando a Distância Percentual Média (eixo das ordenadas) com o número de gerações (eixo das abscissas) em função do tamanho da população. 68 Figura 25: Gráficos correlacionando a Distância Percentual Média (eixo das ordenadas) com o número de gerações (eixo das abscissas) em função do número de cruzamentos. ........................................................................................................................................ 69 Figura 26: Gráficos correlacionando a Distância Percentual Média (eixo das ordenadas) com o número de gerações (eixo das abscissas) em função da probabilidade de mutação. ........................................................................................................................................ 70 LISTA DE TABELAS Tabela 1: Representação de ocorrência de palavras-chave ............................................ 20 Tabela 2: Parâmetros calibrados para a Meta-heurística Recozimento Simulado .......... 67 Tabela 3: Parâmetros calibrados para a Meta-heurística Algoritmo Genético. .............. 70 Tabela 4: Resultados da busca pelas melhores condições de processo do estudo de ..... 71 Tabela 5: Pesos atribuídos as respostas utilizando os métodos de aglutinação CP e CPDE no estudo de caso 1. ........................................................................................................ 72 Tabela 6: Resultados da busca pelas melhores condições de processo do estudo de ..... 73 Tabela 7: Pesos atribuídos as respostas utilizando os métodos de aglutinação CP e CPDE no estudo de caso 2. ........................................................................................................ 74 Tabela 8: Resultados da busca pelas melhores condições de processo do estudo de ..... 75 Tabela 9: Pesos atribuídos as respostas utilizando os métodos de aglutinação CP e CPDE no estudo de caso 3. ........................................................................................................ 76 Tabela 10: Resultados da busca pelas melhores condições de processo do estudo de ... 77 Tabela 11: Pesos atribuídos as respostas utilizando os métodos de aglutinação CP e CPDE no estudo de caso 4. ........................................................................................................ 78 Tabela 12: Resultados da busca pelas melhores condições de processo do estudo de ... 79 Tabela 13: Pesos atribuídos as respostas utilizando os métodos de aglutinação CP e CPDE no estudo de caso 5. ........................................................................................................ 80 Tabela 14: Resultados da busca pelas melhores condições de processo do estudo de ... 97 Tabela 15: Resultados da busca pelas melhores condições de processo do estudo de ... 97 Tabela 16: Resultados da busca pelas melhores condições de processo do estudo de ... 98 Tabela 17: Resultados da busca pelas melhores condições de processo do estudo de ... 98 Tabela 18: Resultados da busca pelas melhores condições de processo do estudo de ... 99 Tabela 19: Resultados da busca pelas melhores condições de processo do estudo de . 100 Tabela 20: Resultados da busca pelas melhores condições de processo do estudo de . 100 Tabela 21: Resultados da busca pelas melhores condições de processo do estudo de . 101 Tabela 22: Resultados da busca pelas melhores condições de processo do estudo de . 101 Tabela 23: Resultados da busca pelas melhores condições de processo do estudo de . 102 Tabela 24: Resultados da busca pelas melhores condições de processo do estudo de . 103 Tabela 25: Resultados da busca pelas melhores condições de processo do estudo de . 103 Tabela 26: Resultados da busca pelas melhores condições de processo do estudo de . 104 Tabela 27: Resultados da busca pelas melhores condições de processo do estudo de . 104 Tabela 28: Resultados da busca pelas melhores condições de processo do estudo de . 105 Tabela 29: Resultados da busca pelas melhores condições de processo do estudo de . 106 Tabela 30: Resultados da busca pelas melhores condições de processo do estudo de . 106 Tabela 31: Resultados da busca pelas melhores condições de processo do estudo de . 107 Tabela 32: Resultados da busca pelas melhores condições de processo do estudo de . 107 Tabela 33: Resultados da busca pelas melhores condições de processo do estudo de . 108 Tabela 34: Resultados da busca pelas melhores condições de processo do estudo de . 109 Tabela 35: Resultados da busca pelas melhores condições de processo do estudo de . 109 Tabela 36: Resultados da busca pelas melhores condições de processo do estudo de . 110 Tabela 37: Resultados da busca pelas melhores condições de processo do estudo de . 110 Tabela 38: Resultados da busca pelas melhores condições de processo do estudo de . 111 LISTA DE ABREVIAÇÕES E SÍMBOLOS AG AGNM CP CPDE DOE DPM GRG LTB NM NTB RS RSNM STB T αi Algoritmo Genético Algoritmo Genético combinado com o método de Nelder Mead Simplex Programação por Compromisso Programação por Compromisso normalizada pela Distância Euclidiana Design ofExperiments (Planejamento de Experimentos) Distância Percentual Média Gradiente Reduzido Generalizado Large to Better (MaiorMelhor) Nelder Mead Simplex Nominal toBetter (Nominal é Melhor) Recozimento Simulado Recozimento Simulado combinado com o método de Nelder Mead Simplex Small to Better (MenorMelhor) Target (Alvo) Peso atribuído a resposta i SUMÁRIO 1. INTRODUÇÃO ........................................................................................................ 16 1.1. DESCRIÇÃO DO PROBLEMA ............................................................................. 16 1.2. OBJETIVOS E DELIMITAÇÃO DO PROBLEMA .............................................. 18 1.3. JUSTIFICATIVA E IMPORTÂNCIA .................................................................... 19 1.4. MÉTODO DE PESQUISA ...................................................................................... 21 2. FUNDAMENTAÇÃO TEÓRICA ........................................................................... 26 2.1. OTIMIZAÇÃO ........................................................................................................ 26 2.1.1. Otimização Multiobjetivo .......................................................................................... 26 2.2. PLANEJAMENTO DE EXPERIMENTOS ............................................................ 28 2.3.1. O Método Desirability ................................................................................................. 29 2.3.2. Distância Percentual Média (DPM) ........................................................................ 33 2.3.3. Progrmação por Compromisso (Compromise Progamming - CP) .................. 33 2.4.META-HEURÍSTICAS ........................................................................................... 34 2.4.1.Recozimento Simulado (RS) ....................................................................................... 35 2.4.2. Algoritmo Genético (AG) ........................................................................................... 37 2.5. ALGORITMO NELDER-MEAD SIMPLEX ......................................................... 44 2.6. GRADIENTE REDUZIDO GENERALIZADO ..................................................... 47 3. MÉTODOS ................................................................................................................ 49 3.1. CASOS SELECIONADOS DA LITERATURA .................................................... 49 3.1.1. Caso 1 – Derringer e Suich (1980) ........................................................................... 49 3.1.2. Caso 2: Khuri e Conlon (1981): ................................................................................ 51 3.1.3. Caso 3: Vining (1998): ................................................................................................ 52 3.1.4. Caso 4 – Castillo et al. (1996) .................................................................................... 53 3.1.5. Caso 5 – Heinsman e Montgomery (1995) ............................................................. 54 3.2. META-HEURISTICAS .......................................................................................... 56 3.2.1. Recozimento Simulado (RS) ...................................................................................... 56 3.2.2. Algoritmo Genético ..................................................................................................... 57 3.2.3. Recozimento Simulado combinado com o método de Nelder Mead Simplex 59 3.2.3. Algoritmo Genético combinado com método Nelder Mead Simplex ............... 60 3.2.5. Calibração das Meta-Heuristica .............................................................................. 62 3.3. GRADIENTE REDUZIDO GENERALIZADO GRG ........................................... 62 4. RESULTADOS E DISCUSSÃO ............................................................................. 63 4.1. CALIBRAÇÃO DA META-HEURISTICA RECOZIMENTO SIMULADO ....... 63 4.2. CALIBRAÇÃO DOS PARÂMETROS DA META-HEURISTICA ALGORITMO GENÉTICO .................................................................................................................... 67 4.3 ESTUDO DO CASO 1 (DERRINGER E SUICH, 1980) ........................................ 70 4.4 ESTUDO DO CASO 2 (KHURI E CONLON, 1981) ............................................. 72 4.4 ESTUDO DO CASO 3 (VINING, 1998) ................................................................. 74 4.5 ESTUDO DO CASO 4 (CASTILO ET AL., 1996) .................................................. 76 4.5 ESTUDO DO CASO 5 (MONTGOMERY ET AL., 1995) ...................................... 78 5. CONCLUSÕES E SUGESTÕES PARA TRABALHOS FUTUROS .................. 81 5.1 CONCLUSÕES ........................................................................................................ 81 REFERÊNCIAS BIBLIOGRÁFICAS ....................................................................... 83 ANEXO 1: PROGRAMAÇÃO EM SCILAB PARA A META-HEURÍSTICA RECOZIMENTO SIMULADO ..................................................................................... 89 ANEXO 2: PROGRAMAÇÃO EM SCILAB PARA A META-HEURÍSTICA ALGORITMO GENÉTICO ........................................................................................... 91 ANEXO 3: PROGRAMAÇÃO EM SCILAB PARA A META-HEURÍSTICA RECOZIMENTO SIMULADO combinada com método nelder mead simplex ............ 92 ANEXO 4: PROGRAMAÇÃO EM SCILAB PARA A META-HEURÍSTICA ALGORITMO GENÉTICO combinada com método nelder mead simplex ................. 95 ANEXO 5: Resultados obtidos para o estudo de caso 1 ................................................ 97 ANEXO 6: Resultados obtidos para o estudo de caso 2 .............................................. 100 ANEXO 7: Resultados obtidos para o estudo de caso 3 .............................................. 103 ANEXO 8: Resultados obtidos para o estudo de caso 4 .............................................. 106 ANEXO 9: Resultados obtidos para o estudo de caso 5 .............................................. 109 16 1. INTRODUÇÃO 1.1. DESCRIÇÃO DO PROBLEMA A determinação de uma melhoria de processo é tipicamente complexa em função das variações de demanda dos clientes e dos avanços tecnológicos. Geralmente, deve-se levar em consideração várias respostas para que se alcance uma melhoria global no processo. Portanto a melhoria simultânea de múltiplas respostas tem sido prioridade em vários ramos industriais (TSAI, et al., 2010). A melhoria de um processo pode ser definida como a busca das melhores condições de ajuste para uma determinada operação ou conjunto de operações. O processo de busca pode partir de uma solução inicial ou de um conjunto delas, realizando melhoramentos progressivos até chegar a um outro conjunto que contenha uma ou todas as melhores soluções possíveis dentro do espaço de busca. Problemas para a determinação de condições que levam a uma melhoria de processos, podem ser formulados de maneira genérica como visto em (1): Maximize ou Minimize f(y), y=(x1, x2, x3, ..., xn) (1) Sujeito ou não: - a restrições de igualdade (na forma cz(y)=0); - e restrições de desigualdade (na forma cz(y)≤0). Melhorar um processo implica geralmente na redução de custos ou no incremento de ganhos, ou seja, determinar um conjunto de condições pertencentes ao conjunto de variáveis y=(x1, x2, x3, ..., xn) que gere melhores valores da função f(y), obedecendo as restrições impostas. A obtenção de um modelo matemático que descreva o comportamento de um processo pode ser obtido por meio de técnicas determinísticas ou estocásticas. Segundo 17 Días-García e Bashiri (2014), a ferramenta estatística muito útil nos estudos de otimização com múltiplas respostas é a metodologia de superfície de resposta em sua versão multivariada. Esta abordagem torna possível determinar uma relação analítica entre a resposta e as variáveis de controle com uma menor quantidade de pontos experimentais (KHURI e CORNNEL, 1987). A partir da maneira como a função objetivo é obtida, o problema pode ser linear ou não linear. As variáveis que compõem a função objetivo podem assumir valores reais, inteiros ou ambos. Uma solução y* para um problema de minimização é chamada mínima global quando não existir outra y, pertencente ao espaço de busca, cujo o valor da função objetivo f(y) < f(y*). Em problemas de maximização, o chamado máximo global y* atende a f(y*) > f(y) para todo x pertencente ao espaço de busca, como pode ser observado na Figura 1: Figura 1: Exemplos de ponto de máximo e de mínimo em uma função. Fonte: adaptado de WEISE 2009 Se a solução y possui f(y) mínimo apenas dentro de uma certa região em torno de y, chamada de vizinhança de y, diz -se que o mínimo é local. Os mínimos locais podem ser boas soluções, mas não são as melhores. Para certos métodos de busca esses pontos são indesejáveis, pois interrompem a busca por soluções melhores. 18 Uma das maneiras mais eficazes em se resolver este tipo de problema é a utilização de meta-heurísticas em função de sua capacidade evolutiva, que propicia a determinação de pontos ótimos sem a necessidade de se calcular todas as soluções possíveis. Entretanto, segundo Kuriger e Grant (2011), as meta-heurísticas são considerados excelentes métodos de determinação de uma região ótima dentro do espaço de busca delimitado pelas restrições, porém, para a determinação do melhor ajuste da função deve- se utilizar outros de métodos de busca como o método Simplex ou o método Simplex de Nelder Mead. 1.2. OBJETIVOS E DELIMITAÇÃO DO PROBLEMA O objetivo geral desta tese foi o estabelecimento de uma metodologia para melhoria de processos com múltiplas respostas utilizando meta-heurísticas. Como objetivos específicos buscou-se:  Avaliar o desempenho das meta-heurísticas AG e RS, assim como a heurística GRG, no intuito de promover melhorias em processos com múltiplas respostas, utilizando as funções: Desirability, DPM, CP e CPDE como métodos de aglutinação.  Estabelecer uma metodologia de melhoria de parâmetros do processos que necessitem de uma interferência mínima do usuário. As delimitações da metodologia desenvolvida nesta tese são:  A melhoria estabelecida é restrita a área experimental estudada para obtenção do modelo empírico;  Como o estudo foi baseado em trabalhos presentes na literatura, não foi possível um experimento de confirmação que validasse os resultados obtidos.  A robustez da melhoria é função da qualidade do modelo gerado. 19 1.3. JUSTIFICATIVA E IMPORTÂNCIA Problemas de otimização com múltiplas respostas, geralmente envolvem objetivos conflitantes que os tornam difíceis de serem resolvidos (KURIGER e GRANT, 2011). Segundo Kim e Lin (2006), o foco principal das abordagens existentes na busca de melhorias de processos contendo múltiplas-respostas é somente no efeito local, ignorando o efeito da dispersão das respostas podendo gerar uma melhoria no processo baseada em um mínimo local, justificando-se assim que todo e qualquer estudo sobre métodos de melhoria de processo que utilizem ferramentas capazes de determinar o ótimo global. De acordo com Anderson et al. (2006), as variáveis de entrada e saída tem caráter estocástico, que podem gerar uma grande quantidade de ótimos locais presentes na superfície de resposta. Shu-Kai et al. (2006), propuseram a utilização da combinação da meta-heurística Algoritmo Genético com o método Simplex de Nelder Mead para a resolução de problema com uma única resposta, já García, et al. (2014) implementaram uma método combinado entre a meta-heurística Recozimento Simulado e o método Simplex de Nelder Mead para a obtenção de uma compartimentação de uma série temporal multivariada. Wan e Birch (2011), apresentaram um Algoritmo Genético modificado utilizando a função Desirability como função aglutinadora para a resolução de problemas com duas variáveis resposta. Outro fator relevante no contexto das abordagens já existentes na literatura, é o fato da maioria dos trabalhos que abordam este tema só testam o método de otimização proposto em um estudo de caso havendo uma carência de trabalhos que estendam a utilização de seus métodos para vários trabalhos (COSTA et al., 2012). Para determinar a originalidade do trabalho, foi realizado um análise bibliométrica utilizando a base de dados Scopus, cruzando as palavras-chave deste trabalho. O Resultado obtido está demonstrado na Tabela 1: 20 Tabela 1: Representação de ocorrência de palavras-chave Palavras-Chave Ocorrência Meta Heuristics and Multi Response Optimization Meta Heuristics and Design of Experiments Meta Heuristics and Desirability Meta Heuristics and Compromise Programming Simulated Annealing and Desirability Simulated Annealing and Compromise Programming Simulated Annealing and Design of Experiments Simulated Annealing and Multi Response Optimization Simulated Annealing and Nelder Mead Genetic Algorithm and Multi Response Optimization Genetic Algorithm and Design of Experiments Genetic Algorithm and Desirability Genetic Algorithm and Compromise Programming Genetic Algorithm and Nelder Mead Simulated Annealing and Nelder Mead and Design of Experiments Genetic Algorithm and Nelder Mead and Design of Experiments Simulated Annealing and Nelder Mead and Design of Experiments and Compromise Programing Genetic Algorithm and Nelder Mead and Design of Experiments and Compromise Programing 13 69 3 4 4 1 126 17 25 343 849 73 22 112 0 0 0 0 Observando os dados presentes na Tabela 1, verifica-se que existem estudos que combinam as meta-heurísticas Algoritmo Genético (AG) e Recozimento Simulado (RS) com o método de Nelder Mead Simplex, porém a análise bibliométrica realizada não reporta a implementação dessas combinações para obter melhoria em respostas obtidas por meio de um planejamento de experimentos. Assim como não foi possível encontrar trabalhos na literatura que associassem as meta-heurísticas AG e RS com o método Nelder Mead utilizando em conjunto a Programação por Compromisso. Nota-se também que há um grande número de publicações que exploram a utilização de AG nesta área ficando evidenciado uma predisposição deste algoritmo para esta finalidade. 21 1.4. MÉTODO DE PESQUISA Sobre a sua classificação, segundo Bertrand e Fransoo (2002), a presente pesquisa pode ser classificado quanto à natureza como aplicada, pois visa proporcionar melhorias práticas para a literatura, com objetivos empíricos normativos, uma vez que o método visa estabelecer parâmetros de processo que consigam melhorias em diversos objetivos diferentes de forma simultânea. Quanto à forma de abordar o problema, a pesquisa é quantitativa, sendo o método de pesquisa adotado a modelagem. A Figura 2 apresenta o método empregado nesta teses para melhor ilustrar as etapas de pesquisa. 22 Figura 2: Etapas da pesquisa 1..5. CONTRIBUIÇÕES Nos últimos anos, pesquisadores vem utilizando diferentes tipos de meta- heurísticas combinadas com a ferramenta planejamento de experimentos, como pode ser observado na Figura 3 . 23 Figura 3: Publicações com relação a utilização do DOE com Meta-heurísticas Relacionando as palavras-chaves Meta-Heurísticas x DOE nos campos palavras- chave, título e resumo, foi possível verificar a ocorrência de 234 documentos do ano de 1993 a 2015, o que indica que ainda há assuntos relativos a estas técnica à serem explorados pela comunidade científica. Dentre as áreas que concentram o maior número de publicações estão: Ciência da Computação com 59,4%, Matemática com 42,4% e Engenharia com 32,1%, como pode ser visto na Figura 4. Vale ressaltar que no Sistema Scopus (base de dados consultada), um trabalho pode ser classificado em mais de uma área o que gera um percentual total superior a 100%. Apesar da combinação destes métodos já ter sido pesquisada por outros autores, não foi possível encontrar na literatura um estudo que relacionasse a utilização das meta- heurísticas algoritmo genético e recozimento simulado combinadas com o método Nelder Mead Simplex no estabelecimento de melhorias de processos com múltiplas respostas modelados a partir de um planejamento de experimentos. 24 Figura 4: Gráfico de pizza para áreas das publicações de Meta-heurísticas x DOE Fonte: Site Scopus. 1.6 ORGANIZAÇÃO DO TEXTO A Tese encontra-se estruturada em mais cinco capítulos. O Capítulo 2 é dedicado a uma fundamentação da teoria que embase o estudo realizado apresentando o conceito de otimização de processos multiobjetivos, o emprego do DOE como forma de modelar um problema, os métodos de aglutinação de respostas mais empregados em otimização de problema com múltiplas respostas, as Meta- heurísticas Recozimento Simulado e Algoritmo Genético, o método Nelder Mead Simplex e o método do Gradiente Reduzido Generalizado. O Capítulo 3 faz uma descrição do método empregado neste estudo, apresentando de forma sucinta os cinco trabalhos selecionados na literatura dos quais os dados foram utilizados nesta pesquisa, assim como foi realizado a parte de implementação dos métodos propostos e a forma como foi conduzida a etapa de comparação entre os métodos. 25 No Capítulo 4 é apresentado os resultados obtidos empregando os métodos propostos em cada caso selecionado, avaliando o desempenho dos mesmos e comparando com o método clássico. O Capítulo 5 traz as conclusões deste estudo e sugestões para futuras pesquisas seguidas das referência bibliográficas citadas no texto e os Apêndices que ilustram os códigos dos programas computacionais que foram aplicados. 26 2. FUNDAMENTAÇÃO TEÓRICA 2.1. OTIMIZAÇÃO Um dos princípios mais fundamentais do nosso mundo é a busca de um estado ideal. Ela começa no microcosmo onde os átomos tentam formar ligações a fim de minimizar a energia de seus elétrons (PAULING, 1960). Quando as moléculas formam corpos sólidos durante o processo de congelamento, eles tentam assumir estruturas cristalinas com um estado mínimo de energia. Estes processos, é claro, não são movidos por qualquer intenção maior, mas puramente resultam das leis da física. Na história da humanidade, a busca por melhores condições de vida também pode ser considerada como um processo de otimização, a busca pelo menor esforço ou por resultados máximos sempre esteve presente ao longo dos anos. Nas empresas a produção deve ser maximizada e os custos devem ser os mínimos possíveis. Porém é importante ressaltar que um processo de otimização não implica necessariamente na determinação das condições ótimas de operação, uma vez que fica praticamente impossível de estabelecer o ponto ótimo em função de uma quantidade ilimitada de variáveis que impactam em um processo. Ao invés disso, o que se pode determinar são condições de melhorias a partir da seleção de pontos máximos determinados dentro de um espaço de busca pré-determinado. (DEHURI e CHO, 2009) 2.1.1. Otimização Multiobjetivo Os processos industriais e os produtos por eles gerados, raramente possuem uma única característica da qualidade. O mais comum é que essas características sejam diversas, algumas mais importantes que outras na proporção do valor que o cliente atribui a cada uma delas. Uma indústria, por exemplo, pode ter as seguintes respostas sujeitas a otimização: a. Minimizar o lead time; b. Maximizar a produtividade; c. Minimizar os custos de produção; d. Maximizar a qualidade de seu produto; e. Minimizar o impacto com o meio ambiente. 27 As duas últimas respostas parecem conflitar com a minimização de custos de produção. Entre a maximização da produtividade e as demais respostas, parece haver algum tipo de relação (conflito). Os conflitos entre as respostas nem sempre são óbvios podendo gerar um série de complicações no processo de otimização (WEISE, 2009). Em otimização multiobjetivo não há, normalmente, nenhuma solução que seja ideal para todos os objetivos impostos. Consequentemente, a situação normal é que qualquer solução pode ser sempre melhorada em pelo menos um objetivo (BAZGAN, et al., 2015). Portanto, pode-se considerar que o resultado de uma otimização multiobjectivo gere um conjunto de soluções ótimas chamado soluções não-dominadas. Soluções não- dominadas são também chamados de soluções Pareto-ótimas. Todas as soluções que são Pareto-ótimas constituem o conjunto Pareto. Os valores objetivos do conjunto de Pareto no espaço objetivo constituem a fronteira de Pareto (SUDENG e WATTANAPONGSAKORN, 2015). A resolução de problemas multiobjetivo é dividida, basicamente, em duas etapas: a) Determinação de soluções eficientes; b) Etapa de decisão. O primeiro aspecto diz respeito a determinação do conjunto de soluções Pareto- ótimas dentro da região viável do conjunto de respostas. O segundo aspecto, se refere a determinação da melhor resposta dentre as relacionadas pelo conjunto Pareto-ótimas. Este procedimento também é conhecido como decisor. Segundo VELDHUIZEN e LAMONT (2000), os métodos de resolução de problemas multiobjetivo podem ser classificados em três categorias distintas, de acordo com a combinação realizada entre o método de otimização e a etapa de decisão: a) Decisão antes do processo de procura: quando o decisor atribui os pesos para cada objetivo que compõe o problema. b) Decisão durante o processo de procura: é o procedimento que faz as escolhas durante o processo de obtenção das soluções. c) Decisão após o processo de procura: quando a determinação da melhor solução é realizada após a determinação das soluções eficientes. 28 A apresentação das decisões após a etapa de definição das soluções eficientes é a mais lógica das três, isto porque as escolhas serão feitas de acordo com as respostas finais encontradas. Ou seja, como já dito, com o conjunto Pareto-ótimo definido torna-se possível conhecer o comportamento do problema em relação aos objetivos analisados. Conhecendo-se as relações de dependência entre eles, a escolha final é facilitada (AVILA, 2006). 2.2. PLANEJAMENTO DE EXPERIMENTOS O planejamento experimental (DOE – Design of Experiments) representa um conjunto de ensaios estabelecidos com critérios científicos e estatísticos, com o objetivo de determinar a influência de diversas variáveis em uma determinada resposta (BUTTON, 2005). O arranjo experimental mais comum é o fatorial completo para o qual o número é igual ao número de níveis experimentais elevado ao número de fatores. Montgomery e Runger (2012) afirmam que “planejamentos fatoriais” são frequentemente usados nos experimentos envolvendo vários fatores e que “experimentos fatoriais” são a única maneira de descobrir interações entre variáveis de processo (MONTGOMERY; RUNGER, 2012). Segundo Haridy et al. (2011) o Planejamento de Experimentos é um método estruturado e organizado, utilizado na determinação do relacionamento de diferentes fatores de entrada e saída do processo, envolvendo a definição do conjunto de experimentos, nos quais todos os fatores relevantes são variados sistematicamente. Através da análise dos resultados obtidos pode-se determinar o grau de influência na variável resposta de cada fator utilizado, assim como as interações entre os fatores e as condições ótimas. De acordo com Silva e Silva (2008), o planejamento de experimentos é uma técnica fundamental para a melhoria da qualidade e produtividade em processos industriais. 2.3. MÉTODOS DE AGLUTINAÇÃO A grande questão quando se trabalha com otimização com múltiplas respostas é a questão da incomensurabilidade, que para Silva e Marins (2015), trata-se de 29 problemas com diferentes unidades de medidas entre os objetivos, podendo ainda ser contornada com o uso de métodos de normalização. Segundo Tamiz e Jones (1995) existem muitas técnicas de normalização sendo utilizadas, porém, as mais comuns são: Normalização Euclidiana e Normalização por Porcentagem.  Normalização Euclidiana: consiste na divisão dos coeficientes do modelo pela raiz quadrada da soma quadrática de todos os termos do modelo. Tal fato minimiza o efeito da incomensurabilidade. O problema para esse caso está relacionado com os coeficientes, quando os coeficientes técnicos do modelo são muito pequenos, comparados com os valores alvos, podendo causar distorções nos valores;  Normalização por Porcentagem: Representa a porcentagem de desvio com relação ao valor alvo, sendo calculado primeiramente dividindo todos os coeficientes pelo valor do alvo da equação, em seguida multiplicando por 100. O grande problema desse método está em relação ao valor alvo ser muito pequeno. Existem métodos de aglutinação que sua estrutura já é formada por um dado tipo de normalização, que é o caso da função Desirability e Distância Média Percentual (DPM). 2.3.1. O Método Desirability Uma das técnicas mais utilizadas para otimizar simultaneamente várias respostas consiste em transformar as equações que modelam cada uma dessas respostas em funções utilidade individuais, e depois proceder à otimização de uma função utilidade global (Total Desirability, D) que é descrita em termos das funções utilidade individuais. A otimização simultânea de várias respostas transforma-se assim na otimização de uma única função. Os grandes impulsionadores desta abordagem foram Derringer e Suich (1980). O método que propuseram continua a ser uma base de comparação para outros métodos em termos dos resultados que permite obter. Derringer e Suich (1980) apresentam funções utilidade individuais para respostas do tipo Nominal é Melhor (NTB – Nominal The Better), Maior é Melhor (LTB – Larger The Better) e Menor é Melhor (STB - Smaller The Better). Quando o valor alvo (T) de 30 uma resposta   xŷ está entre um valor máximo (U) e um valor mínimo (L), a resposta diz-se do tipo NTB e a correspondente função utilidade   xyd ˆ , que por uma questão de simplificação se passará a representar por d, pode ser definida como em (2):                             UyLy UyT UT Uy TyL LT Ly d R S ˆˆ0 ˆ ˆ ˆ ˆ ou (2) Onde R e S são fatores de ponderação. Quando o valor alvo deve atingir o valor máximo da função, a resposta diz-se do tipo LTB e a correspondente função utilidade pode ser definida como visto em (3):                   Uy TyL LU Ly Ly d R ˆ1 ˆ ˆ ˆ0 (3) Quando o valor alvo deve atingir o valor mínimo da função, a resposta diz-se do tipo STB e a correspondente função utilidade   xyd ˆ pode ser definida como em (4)                   Ly UyL UL Uy Uy d R ˆ1 ˆ ˆ ˆ0 (4) De acordo com Derringer e Suich (1980), a otimização das respostas envolvidas no estudo é efetuada por meio da maximização da função utilidade global (5). 31   p pddddD 1 321   (5) Onde p corresponde ao número de respostas a serem otimizadas. Derringer (1994) sugere que se utilize (6) ao invés da (5) na determinação do valor de D.      p i iw pw p www ddddD 1 1 321 321  (6) Entretanto, segundo Castillo e Montgomery (1993), basta que uma das funções d tenha um valor inaceitável, por exemplo o valor mínimo (d = 0), para que a solução global também se torne inaceitável (D = 0). Khuri e Conlon (1981) apresentaram o método de otimização pela Aproximação da Distância Generalizada, onde são consideradas duas etapas. Na primeira etapa são obtidos os valores ótimos individuais para cada resposta por meio da região obtida experimentalmente. Na segunda etapa, o ótimo global é determinado minimizando-se a função distância p, dada por (7), associada à distância do ótimo global, sendo a variância e a covariância das respostas utilizadas como pesos na função.            2 1 1 ˆˆvarˆ    xyxyxyp T (7) onde  xŷ é o vetor de respostas preditas na localização x,   xŷvar é a variância e covariância da matriz de respostas preditas na localização x e  é o vetor das respostas alvo. Vining (1998) estendeu a aproximação feita por Khuri e Conlon (1981) e Piagnatiello (1993), levando em consideração os valores da função perda dada por (8).            xyCtracexyCxyE T ˆvarˆˆˆ   (8) onde C é uma matriz positiva definida pelos pesos, e os outros termos têm as mesmas definições como em (5). O primeiro termo         xyCxy T ˆˆ representa a 32 penalidade imposta para o desvio de qualquer resposta do respectivo valor alvo, e o segundo termo     xyCtrace ˆvar representa a penalidade imposta pela qualidade dos valores preditos. O método considera a correlação entre as respostas e a economia do processo. Além disso, leva em conta a habilidade do modelo na previsão das condições ótimas. Segundo Xu et al. (2004), a dificuldade de implementação deste método é que a estimativa do parâmetro C pode ser subjetiva e o cálculo da matriz variância-covariância é complexo quando as respostas provém de diferentes formas de modelos. Castillo e Montgomery (1993) afirmam que há outros algoritmos de otimização mais eficientes, como o Gradiente Reduzido Generalizado (GRG), que é um dos mais populares algoritmos de otimização não linear. Ch’ng et al. (2005) propõem que a função utilidade global seja definida na forma de uma média aritmética, como em (8), para evitar que o GRG apresente falsos valores ótimos. Isto pode acontecer se o valor de uma das respostas for igual ao valor alvo, fazendo com que      0ˆ  ii Tdyd em (9) e, por consequência, D atinja o valor mínimo zero:      p Tdyde D ii p i i     ˆ 1 (9) onde  iyd ˆ é a função utilidade da resposta i,  iTd é o valor dessa função utilidade no valor alvo, ei é o fator ponderação da resposta i com 1 1   p i ie e p é o número de respostas. As funções utilidades individuais são definidas por (10).   cym LU L LU y LU LUy d i ii i           ˆ 2ˆ2 1 ˆ2 (10) 33 com 20  id . Para Maia (2013) e Mendes (2012), o método Desirability apresenta algumas desvantagens tais como: O método ignora a estrutura de variância e covariância ao transformar um modelo multivariado em um univariado, levando a soluções distantes do ponto ótimo. Também não leva em consideração a possível correlação entre as variáveis respostas, além de que, aumentando a não linearidade D com o aumento do número de variáveis respostas, pode conduzir a soluções viáveis locais. Contudo deve-se ressaltar que estes problemas ocorrem quando o processo a ser otimizado contém variáveis de decisão auto correlacionadas. 2.3.2. Distância Percentual Média (DPM) A função aglutinadora Distância Percentual Média (DPM), pode ser obtida através de (11): 1 ˆ 100 p i i i i y T T DPM p      (11) onde: iŷ - variável resposta i; iT - valor alvo da variável resposta i. p – número de respostas contidas no problema Segundo Kim e Lin (2006), este é o método que tem obtido melhores resultados quando aplicados na avaliação de métodos de otimização, sendo também o método mais indicado para se proceder com comparação entre métodos de busca de soluções ótimas. 2.3.3. Progrmação por Compromisso (Compromise Progamming - CP) A programação por compromisso (CP), foi apresentada inicialmente por Zeleny (1974), sendo posteriormente adaptado e aplicado na área dos recursos hídricos por 34 Duckstein e Opricovic (1980), numa abordagem multiobjetivo na presença de variáveis discretas. O método classifica as alternativas não dominadas através de um conceito geométrico do melhor, por meio de uma medida de distância até a solução ideal. Para Jardim (1999), esse método é caracterizado pela tentativa de identificar as soluções as quais podem estar mais próximas de uma solução “ideal”, considerando essa medida como sendo a distância entre uma dada solução com relação à solução ideal. Segundo Romero (1993) a função CP pode ser calculada através de (12):   1 * 1 n s s p i i i i Min L Y Y x            (12) Tendo como fator limitante descrito em (13): 1 1 n i i    (13) Sendo: i - o peso atribuído a iésima variável resposta. * iY - o valor alvo da iésima variável resposta Uma limitação da utilização do CP como método de aglutinação é sua incomensurabilidade, segundo Jadidi, et al.(2014), uma das maneiras de se contornar este problema é aplicando o método da Distância Euclidiana nas equações que fornecem os valores para as variáveis resposta. 2.4.META-HEURÍSTICAS Meta-heurísticas são procedimentos destinados a encontrar uma boa solução, eventualmente a ótima, consistindo na aplicação, em cada passo, de uma heurística subordinada, a qual tem que ser modelada para cada problema específico. 35 Esta combinação é frequentemente realizada por um processo estocástico, utilizando dados obtidos a partir de amostras do espaço de busca ou com base em um modelo de algum fenômeno natural ou processo físico. O Recozimento Simulado, por exemplo, decide qual a próxima solução deverá ser avaliada de acordo com o fator de probabilidade de Boltzmann de configurações do átomo de solidificação de metais fundidos. Meta-heurísticas simulam o comportamento da evolução natural ao tratar as soluções como indivíduos que competem em um ambiente virtual. (GONZALES, 2007; KAVEH e MAHDAVI 2014). Segundo Pholdee e Bureerat (2014), as Metaheurísticas vem sendo amplamente utilizadas para vários tipos de problemas de busca de melhores condições de processo, especialmente para aplicações na engenharia, devido a sua capacidade de procura de soluções viáveis. 2.4.1.Recozimento Simulado (RS) O Recozimento Simulado foi inicialmente concebido para a minimização de problemas discretos (KIRKPATRICK et al.,1983), porém já foi demonstrado sua eficiência em soluções de problemas com variáveis contínuas (ZANDIEH et al., 2009). O algoritmo do Recozimento Simulado tem várias vantagens quando aplicado a problemas onde existe um grande número de mínimos locais e o mínimo global é difícil de se determinar (CAI & MA, 2010). Essas vantagens incluem o amplo intervalo de busca garantindo que o algoritmo não fique preso a mínimos locais e possa determinar o mínimo global, a baixa sensibilidade para a suposição inicial e a simplicidade relativa de implementação (INGBER, 1993). Este algoritmo é fundamentado em uma analogia com a termodinâmica, ao simular o resfriamento de um conjunto de átomos aquecidos, operação conhecida como recozimento. Quando um metal é aquecido até seu ponto de fusão, sua energia interna é alta e assim suas moléculas se movem rapidamente. Quando a temperatura é reduzida, as moléculas vão gradativamente diminuindo sua velocidade de movimento, na medida em que a energia interna também diminui. Assim, próximo ao ponto de congelamento, o metal se torna sólido, e o estado final das moléculas do metal são determinadas pelos seus comportamentos ou pela velocidade de resfriamento. O metal pode resultar em uma forma amorfa, sem uma forma definida como o vidro ou como um cristal com muitos defeitos em sua estrutura, quando o resfriamento for realizado de forma rápida, o que chamamos 36 de processo quenching (esfriamento rápido). Ou, ainda, pode resultar em um cristal, onde todas as suas moléculas estão alinhadas e correspondem a uma configuração de mínima energia do sistema, quando o resfriamento é executado lentamente, chamamos de processo annealing (recozimento para uma recristalização). Essa técnica começa sua busca a partir de uma solução inicial qualquer. O procedimento principal consiste em um loop que gera aleatoriamente, em cada iteração, um único vizinho x* da solução corrente x. Se este vizinho for melhor que o original ele é aceito e substitui a solução corrente. Se ele for pior por uma quantidade , ele é aceito com uma probabilidade exp-/T, onde T, que é um parâmetro chamado de Temperatura, decresce gradualmente conforme o progresso do algoritmo. Esse processo é repetido até que T seja tão pequeno que mais nenhum movimento seja aceito. A melhor solução encontrada durante a busca é tomada como uma boa aproximação para a solução ótima (HAMMOUCHE, 2010). A Figura 5 apresenta um pseudocódigo do Recozimento Simulado. 37 Figura 5: Pseudocódigo da meta-heurística Recozimento Simulado Algoritmo Recozimento Simulado (T0, RSMáx, α) Gere uma solução inicial x IterT←0 T←T0 enquanto (critério de parada não for satisfeito) faça enquanto (IterT1x10-15) faça gere um conjunto de (num_solucoes) vizinho x* aleatoriamente (x* ϵ N(x)) enquanto (ii) faça Ranqueie a população de acordo com a aptidão Sorteie membros da população para cruzamento ou eliminação em função do resultado do ranking enquanto (P > j) faça Sorteie dois membros da população pré-selecionada se (Pc > número aleatório) então Realize cruzamento com um ponto de corte entre sorteados senão Mantém os cromossomos inalterados na próxima geração fim-se se (Pm > número aleatório) então Realize mutação no cromossomo fim-se fim-enquanto Imprime x fim-algoritmo O código fonte desenvolvido está apresentado no Anexo 2. 59 3.2.3. Recozimento Simulado combinado com o método de Nelder Mead Simplex O método de busca de melhores valores utilizando a meta-heurística Recozimento Simulado combinada com o algoritmo de Nelder Mead Simplex foi implementada neste estudo conforme a Figura 16. Figura 16: Representação da metodologia utilizada para a melhoria de processos utilizando Recozimento Simulado combinado com o método Nelder Mead Simplex Algoritmo Recozimento Simulado combinado com o método Nelder Mead Simplex T0←Tinicial num_solucoes ← número de soluções r ← taxa de Resfriamento k ← Número de repetições gere uma solução inicial x T←T0 enquanto (T>1x10-15) faça gere um conjunto de (num_solucoes) vizinho x* aleatoriamente (x* ϵ N(x)) enquanto (ii) faça Ranqueie a população de acordo com a aptidão Sorteie membros da população para cruzamento ou eliminação em função do resultado do ranking enquanto (P > j) faça Sorteie dois membros da população pré-selecionada se (Pc > número aleatório) então Realize cruzamento com um ponto de corte entre sorteados senão Mantém os cromossomos inalterados na próxima geração fim-se se (Pm > número aleatório) então Realize mutação no cromossomo fim-se fim-enquanto salva melhor resposta x** aplicar Simplex de Nelder Mead em x** imprime x** fim-algoritmo O código fonte desenvolvido está apresentado no Anexo 4. 62 3.2.5. Calibração das Meta-Heuristica Dependendo dos valores utilizados nos parâmetros das Meta-Heurísticas, o resultado obtido pode ser o valor desejado (ótimo global), um valor próximo ao desejado (ótimo local) ou ainda um valor muito diferente. A fim de padronizar as meta-heurísticas implementadas neste estudo foram realizados um total de 10 testes utilizando o Caso 1 descrito no item 3.1.1 para determinar os melhores valores para os parâmetros específicos de cada meta-heurística em função do resultado obtido e do custo computacional envolvido. 3.3. GRADIENTE REDUZIDO GENERALIZADO GRG Para a aplicação do Gradiente Reduzido Generalizado (GRG), foi utilizado o software Microsoft Excel® versão 2013, cujo aplicativo Solver será efetuado para obter a solução do problema. Este aplicativo conta com o GRG2 (segunda geração) já contendo melhorias no algoritmo o tornando mais rápido e eficiente. Para a aplicação deste método foram necessárias três etapas: a) Implementação da Função Objetivo: que foi obtida respeitando os alvos de cada estudo de caso associada aos métodos de aglutinação utilizados neste trabalho (Desirability, DPM, CP e CPDE); b) Variáveis de Decisão: sendo tomados os valores iniciais de Zero para todos a fim de se garantir o mesmo início para todas as situações. São as variáveis a serem otimizadas a fim de encontrar o melhor arranho experimental; c) Especificação das Restrições: que foram implementadas de forma a restringir o algoritmo a permanecer dentro da região viável de busca. As restrições foram obtidas de acordo com a particularidade de cada caso especificado. Após o estabelecimento destes parâmetros foi escolhido a utilização do GRG como o algoritmo de busca a ser utilizado pelo solver, e selecionado a opção de minimizar a função objetivo, quando utilizamos os métodos de aglutinação DPM, CP e CPDE. No caso específico da aglutinação realizada pelo método Desirability, utilizou-se o critério de igualar a função objetivo a um. 63 4. RESULTADOS E DISCUSSÃO 4.1. CALIBRAÇÃO DA META-HEURISTICA RECOZIMENTO SIMULADO A temperatura inicial foi o primeiro parâmetro a ser calibrado utilizando-se valores na faixa de 1 a 1x108, na Figura 18 são apresentados os gráficos dos testes realizados. Figura 18: Gráficos correlacionando a Distância Percentual Média (eixo das ordenadas) com o número de iterações (eixo das abscissas) em função da temperatura inicial. Em função dos resultados obtidos com diferentes temperaturas iniciais (Figura 18), optou-se em utilizar a temperatura inicial igual a 1x106. Esta escolha foi em função da boa varredura efetuada com este parâmetro além da mesma apresentar uma boa convergência. A temperatura inicial de 1x108 também apresenta bons resultados, porém o custo computacional exigido é maior, resultando em um número maior de iterações desnecessárias. O segundo parâmetro do algoritmo que foi calibrado, foi o índice de resfriamento (k), que tem uma influência direta no comportamento da temperatura durante o processo computacional. Foram realizados testes com 5 taxas de resfriamento diferentes e os resultados podem ser visualizados na Figura 19. 45 30 15 10308246184122061 45 30 15 10308246184122061 45 30 15 1 100 10000 1000000 100000000 64 Figura 19:Gráficos correlacionando a Distância Percentual Média (eixo das ordenadas) com o número de iterações (eixo das abscissas) em função da taxa de resfriamento. Como pode ser visto na Figura 19, os valores das taxas de resfriamento de 0,99, 0,97 e 0,95, exibem uma boa convergência para uma menor Distância Percentual Média. Entretanto, nota-se também, que para os valores de 0,99 e 0,97, há um custo computacional desnecessário, fator este que foi determinante para escolha da taxa de resfriamento de 0,95 neste estudo. O terceiro parâmetro calibrado, foi o fator de incremento para criação de soluções vizinhas. Os resultados obtidos estão apresentados na Figura 19. Analisando os gráficos da Figura 20, pode-se observar que os incrementos de 0,1, 0,2 e 0,5 na criação de novos vizinhos oferecem uma boa convergência. Porém, quando comparamos a permissibilidade de movimentos de piora, o incremento de 0,5 se mostra superior aos demais, o que indica que o incremento de 0,5 é o mais propício a ser utilizado no algoritmo Recozimento Simulado para a otimização da classe de problemas em questão. 50 25 0 48103848288619249621 50 25 0 48103848288619249621 50 25 0 0,99 0,97 0,95 0,90 0,85 65 Figura 20:Gráficos correlacionando a Distância Percentual Média (eixo das ordenadas) com o número de iterações (eixo das abscissas) em função do incremento para criação de novos vizinhos. Para a calibração do quarto parâmetro, número de repetições executadas a cada incremento de temperatura. Os resultados obtidos podem ser vistos na Figura 21. Figura 21: Gráficos correlacionando a Distância Percentual Média (eixo das ordenadas) com o número de iterações (eixo das abscissas) em função do número de repetições a cada incremento de temperatura. Analisando os resultados obtidos pode-se observar que quando foi utilizado 400 repetições obteve-se uma maior área de varredura e uma boa estabilização para 50 25 0 11448585722861 50 25 0 11448585722861 50 25 0 0,01 0,1 0,05 0,2 0,5 8495662831 8495662831 60 45 30 15 0 8495662831 60 45 30 15 0 100 200 300 400 500 66 convergência, portanto optou-se por esse valor para a calibração deste parâmetro. É importante ressaltar que quanto maior for o número de repetições, maior será o custo computacional, entretanto, o uso de 400 repetições altera o custo computacional em 20 s quando comparado a 100 repetições que foi o valor mínimo adotado. O último parâmetro calibrado foi o número de respostas geradas em cada repetição realizada, que foram testadas dentro de um range de 50 a 400 respostas. O resultado deste teste está ilustrado na Figura 22. Figura 22: Gráficos correlacionando a Distância Percentual Média (eixo das ordenadas) com o número de iterações (eixo das abscissas) em função do número de respostas geradas a cada repetição realizada. Tendo em vista os resultados obtidos, optou-se por utiliza o número de respostas igual a 200 por se tratar de um valor que demonstra uma boa variabilidade nas respostas durante o tempo de procura do algoritmo e uma boa estabilização final. Desta forma, os parâmetros adotados para o algoritmo Recozimento Simulado, em todos os teste realizados neste estudo, encontram-se sumarizados na Tabela 2. 8495662831 8495662831 60 45 30 15 0 8495662831 60 45 30 15 0 50 100 200 300 400 67 Tabela 2: Parâmetros calibrados para a Meta-heurística Recozimento Simulado Parâmetro Valor adotado Temperatura inicial Índice de resfriamento Incremento de criação de novos vizinhos Número de Repetições Número de Respostas 1x106 0,95 0,5 200 200 A temperatura final utilizada nos teste realizados com a meta-heurística Recozimento Simulado manteve-se constante no valor de 1x10-15. Apesar deste parâmetro ser de extrema importância no funcionamento do algoritmo em questão, o mesmo não foi testado uma vez que a alteração da temperatura inicial, ou seja a diferença entre a temperatura inicial e final, já foi testada com a variação da temperatura inicial. 4.2. CALIBRAÇÃO DOS PARÂMETROS DA META-HEURISTICA ALGORITMO GENÉTICO Na calibração dos parâmetros da Meta-heurística Algoritmo Genético, a quantidade de gerações foi selecionado como primeiro parâmetro a ser calibrado. Tal escolha deve-se ao fato de que este parâmetro é o que mais influência no custo computacional deste algoritmo. A quantidade de gerações foi variada entre 50 a 500 gerações, e o resultado pode ser observado na Figura 23. Como pode ser observado, todos os valores utilizados demonstram convergir para o mesmo valor de Distância Percentual Média, porém com a utilização de um menor número de gerações é possível atingir este ponto com um custo computacional menor. Apesar de parecer ser óbvio a escolha por um menor número de gerações para que se possa minimizar o custo computacional, optou-se neste estudo por utilizar um tamanho de população igual a 100 para garantir uma boa convergência em uma gama maior de problemas diferentes sem sacrificar em demasia o custo computacional. 68 Figura 23: Gráficos correlacionando a Distância Percentual Média (eixo das ordenadas) com o número de gerações (eixo das abscissas) em função do número total de gerações realizadas. O segundo parâmetro calibrado para a Meta-heurística Algoritmo Genético, foi o tamanho da população. Os resultados obtidos podem ser visualizados na Figura 24. Figura 24: Gráficos correlacionando a Distância Percentual Média (eixo das ordenadas) com o número de gerações (eixo das abscissas) em função do tamanho da população. Pode-se observar que quanto maior o tamanho da população, menor é a DPM alcançada na primeira geração, entretanto, todos os valores utilizados atingem um valor próximo na última geração, e como o tamanho da população também é um fator que incide diretamente no custo computacional do algoritmo, optou-se neste estudo em adotar 4503001501 4503001501 9 8 7 4503001501 9 8 7 50 100 200 300 500 9060301 9060301 9,0 8,5 8,0 7,5 7,0 9060301 9,0 8,5 8,0 7,5 7,0 10 100 200 500 1000 69 o tamanho da população igual a 100 a fim de equilibrar o desempenho do algoritmo com seu custo computacional. O terceiro parâmetro calibrado foi o número de cruzamentos efetuados. Os resultados estão ilustrados na Figura 25. Figura 25: Gráficos correlacionando a Distância Percentual Média (eixo das ordenadas) com o número de gerações (eixo das abscissas) em função do número de cruzamentos. Como pode ser visto na Figura 25, todos os valores testados convergem para a mesma resposta, portanto, optou-se neste parâmetro pela escolha do valor 100 por ser o que aparentemente tem uma convergência mais rápida. O quarto parâmetro calibrado foi a probabilidade de mutação, o qual foi variado em uma faixa entre 0,15 e 0,75. Os resultados se encontram demonstrados na Figura 25. Analisando os gráficos da Figura 26, é possível observar que todas as probabilidades de mutação testadas convergem para a mesma região de resposta, portanto o valor escolhido a ser utilizado neste trabalho foi 0,45, pois entre todos os valores testados foi o que demonstrou uma convergência mais rápida. 9060301 9060301 10 9 8 7 9060301 10 9 8 7 50 100 200 300 400 70 Figura 26: Gráficos correlacionando a Distância Percentual Média (eixo das ordenadas) com o número de gerações (eixo das abscissas) em função da probabilidade de mutação. Em função dos resultados obtidos, os parâmetros adotados para a Meta-heurística Algoritmo Genético, em todos os teste realizados neste estudo, encontram-se sumarizados na Tabela 3. Tabela 3: Parâmetros calibrados para a Meta-heurística Algoritmo Genético. Parâmetro Valor adotado Número de Gerações Tamanho da População Número de Cruzamentos Probabilidade de Mutação 100 100 100 0,45 4.3 ESTUDO DO CASO 1 (DERRINGER E SUICH, 1980) Para a determinação das condições que acarretem em uma melhoria neste processo, foram utilizadas as Meta-heurísticas: Recozimento Simulado, Algoritmo Genético, Recozimento Simulado combinado com o método Nelder Mead Simplex e Algoritmo Genético combinado com o método Nelder Mead Simplex. Foi também utilizada a Heurística Gradiente Reduzido Generalizado para ser utilizada como parâmetro de comparação. Todos os métodos citados foram implementado utilizando as funções Desirability, Desvio Médio Percentual, Programa por Compromisso e Programa 9060301 9060301 9 8 7 9060301 9 8 7 0,15 0,30 0,45 0,60 0,75 71 por Compromisso normalizada pelo método da Distância Euclidiana como métodos de aglutinação. Os resultados obtidos podem ser visualizado na Tabela 4, os pesos utilizados nos método de aglutinação CP e CPDE se encontram na Tabela 5. Nos casos específicos do CP2 e CPDE2, o próprio método de busca foi programado de maneira a atribuir o melhor peso para cada resposta. As Tabelas contendo o ajuste para cada variável e o valor obtido de cada respostas para cada método adotado podem ser encontradas no Anexo 5. Tabela 4: Resultados da busca pelas melhores condições de processo do estudo de caso 1. Métodos de Aglutinação Métodos de Busca GRG RS AG RSNM AGNM Desirability 7,85 7,86 7,85 7,86 7,87 DPM 8,08 6,74 6,75 6,74 6,73 CP1 8,00 8,00 7,68 8,00 7,58 CP2 9.93 7,22 6,90 6,97 6,74 CP3 9,81 9,94 8,71 9,94 8,71 CPDE1 10,66 10,68 10,73 10,68 10,66 CPDE2 8,26 8,09 7,