Igor Lucas de Souza Russo Otimiza¸c˜ao Multiobjetivo e Programa¸c˜ao Gen´etica para Descoberta de Conhecimento em Engenharia Disserta¸c˜ao apresentada ao Programa de P´os-gradua¸c˜ao em Modelagem Computacional, da Universidade Federal de Juiz de Fora como requisito parcial `a obten¸c˜ao do grau de Mestre em Modelagem Computacional. Orientador: Prof. D.Sc. Heder Soares Bernardino Coorientador: Prof. D.Sc. Helio Jos´e Corrˆea Barbosa Juiz de Fora 2017 Ficha catalográfica elaborada através do programa de geração automática da Biblioteca Universitária da UFJF, com os dados fornecidos pelo(a) autor(a) Souza Russo, Igor Lucas de. Otimização Multiobjetivo e Programação Genética para Descoberta de Conhecimento em Engenharia / Igor Lucas de Souza Russo. -- 2017. 102 f. : il. Orientador: Heder Soares Bernardino Coorientador: Helio José Corrêa Barbosa Dissertação (mestrado acadêmico) - Universidade Federal de Juiz de Fora, ICE/Engenharia. Programa de Pós-Graduação em Modelagem Computacional, 2017. 1. Innovization. 2. Otimização Multiobjetivo. 3. Descoberta de conhecimento. 4. Programação Genética. I. Soares Bernardino, Heder, orient. II. Corrêa Barbosa, Helio José, coorient. III. Título. Dedico este trabalho aos meus pais, Aristea e Elcyr. AGRADECIMENTOS A Deus por ter me dado for¸cas para enfrentar os novos desafios. ` A minha fam´ılia, pelo encorajamento e apoio constantes. ` AnamoradaGraziela, pelocarinho, compreens˜aoetamb´empormeincentivarasempre perseguir meus sonhos. Aos meus orientadores, Professores Heder Bernardino e Helio Barbosa, pela oportunidade, pelos ensinamentos valiosos e sobretudo pela paciˆencia. Aos caros amigos Thiago, Bruno, Marcelo, Victor Hugo, Daniel e Geissy por tornarem a caminhada mais suave, mesmo nos trechos mais´ıngremes. Agrade¸co ainda `a tia Helena, `a Din´a e a` Renata pelo suporte e ensinamentos. Aos coordenadores do Programa de Po´s Gradua¸c˜ao em Modelagem Computacional (PPGMC), Professores Rafael Bonfim e Leonardo Goliatt, pela diligˆencia em auxiliar sempre que necess´ario. Aos demais Professores do PPGMC pelos seus ensinamentos e a todosaquelesque, duranteessesdoisanos, contribu´ıramdealgummodoparaaelabora¸c˜ao deste trabalho. Aos Professores membros da banca avaliadora, que contribu´ıram imensamente para a qualidade e consistˆencia deste trabalho. Finalmente, gostaria de agradecer `a CAPES pela bolsa de estudos e a` UFJF pelo aux´ılio financeiro obtido para participa¸c˜ao em conferˆencia internacional. “A tarefa n˜ao ´e tanto ver aquilo que ningu´em viu, mas pensar o que ningu´em ainda pensou sobre aquilo que todo mundo vˆe.” Arthur Schopenhauer. RESUMO A ´area de Otimiza¸c˜ao envolve o estudo e emprego de m´etodos para determina¸c˜ao dos paraˆmetrosquelevam`aobten¸c˜aodesoluc¸˜oes´otimas, deacordocomcrit´eriosdenominados objetivos. Um problema ´e classificado como multiobjetivo quando apresenta objetivos mu´ltiplos e conflitantes, que devem ser otimizados simultaneamente. Recentemente tem crescido o interesse dos pesquisadores pela an´alise de p´os-otimalidade, que consiste na busca por propriedades intr´ınsecas `as soluc¸˜oes ´otimas de problemas de otimiza¸c˜ao e que podem lan¸car uma nova luz a` compreensa˜o dos mesmos. Innovization (inova¸ca˜o atrav´es de otimizac¸˜ao, do inglˆes innovation through optmization) ´e um processo de descoberta de conhecimento a partir de problemas de otimiza¸c˜ao na forma de rela¸c˜oes matem´aticas entre vari´aveis, objetivos, restri¸c˜oes e paraˆmetros. Dentre as t´ecnicas de busca que podem ser utilizadas neste processo est´a a Programa¸ca˜o Gen´etica (PG), uma meta- heur´ıstica bioinspirada capaz de evoluir programas de forma automatizada. Al´em de numericamente v´alidos, os modelos encontrados devem utilizar corretamente as vari´aveis de decis˜ao em rela¸c˜ao `as unidades envolvidas, de forma a apresentar significado f´ısico coerente. Nestetrabalho´epropostaumaalternativaparatratamentodasunidadesatrav´es de opera¸c˜oes protegidas que ignoram os termos inv´alidos. Al´em disso, propo˜e-se aqui uma estrat´egia para evitar a obten¸c˜ao de soluc¸˜oes triviais que n˜ao agregam conhecimento sobre o problema. Visando aumentar a diversidade dos modelos obtidos, prop˜oe-se tamb´em a utiliza¸c˜ao de um arquivo externo para armazenar as solu¸c˜oes de interesse ao longo da busca. Experimentos computacionais s˜ao apresentados utilizando cinco estudos de caso em engenharia para verificar a influˆencia das ideias propostas. Os problemas tratados aqui envolvem os projetos de: uma treli¸ca de 2 barras, uma viga soldada, do corte de uma pec¸a met´alica, de engrenagens compostas e de uma treli¸ca de 10 barras, sendo este u´ltimo ainda n˜ao explorado na literatura de descoberta de conhecimento. Finalmente, o conhecimento inferido no estudo de caso da estrutura de 10 barras´e utilizado para reduzir a dimensionalidade do problema. Palavras-chave: Innovization. Otimiza¸ca˜o Multiobjetivo. Descoberta de conhecimento. Programa¸c˜ao Gen´etica. ABSTRACT The area of optimization involves the study and the use of methods to determine the parameters that lead to optimal solutions, according to criteria called objectives. A problem is classified as multiobjective when it presents multiple and conflicting objectives which must be simultaneously optimized. Recently, the interest of the researchers has grown in the analysis of post-optimality, which consists in the search for intrinsic properties of the optimal solutions of optimization problems. This can shed a new light on the understanding of the optimization problems. Innovization (from innovation through optimization) is a process of knowledge discovery from optimization problems in the form of mathematical relationships between variables, objectives, constraints, and parameters. Genetic Programming (GP), a search technique that can be used in this process, is a bio-inspired metaheuristic capable of evolving programs automatically. In addition to be numerically valid, the models found must correctly use the decision variables with respect to the units involved, in order to present coherent physical meaning. In this work, a method is proposed to handle the units through protected operations which ignore invalid terms. Also, a strategy is proposed here to avoid trivial solutions that do not add knowledge about the problem. In order to increase the diversity of the models obtained, it is also proposed the use of an external file to store the solutions of interest found during the search. Computational experiments are presented using five case studies in engineering toverifythe influence ofthe proposed ideas. The problemsdealtwith here are the designs of: a 2-bar truss, a welded beam, the cutting of a metal part, composite gears, and a 10-bar truss. The latter was not previously explored in the knowledge discovery literature. Finally, the inferred knowledge in the case study of the 10-bar truss structure is used to reduce the dimensionality of that problem. Keywords: Innovization. Multiobjective Optimization. Knowledge discovery. Genetic Programming. SUMA´RIO 1 INTRODUC¸A˜O...................................................... 15 1.1 Organiza¸c˜ao da disserta¸c˜ao ........................................ 21 2 OTIMIZAC¸A˜O MULTIOBJETIVO .................................. 22 2.1 INTRODUC¸A˜O ................................................... 22 2.2 CONCEITOS BA´SICOS .......................................... 22 2.3 ALGORITMOS EVOLUCIONISTAS PARA PROBLEMAS MULTIOBJETIVO ................................................ 27 2.3.1 NSGA-II ..................................................... 29 2.4 MEDIDAS DE DESEMPENHO ................................... 34 2.4.1 Hipervolume.................................................. 34 3 INNOVIZATION ................................................... 35 3.1 INTRODUC¸A˜O ................................................... 35 3.1.1 Processo automatizado de Innovization ........................ 36 3.1.2 Innovization baseado em Programa¸c˜ao Gen´etica................ 40 3.1.2.1 Introdu¸c˜ao............................................................... 40 3.1.2.2 Programa¸c˜ao Gen´etica................................................... 42 3.1.2.3 Processo de Innovization baseado em Programa¸c˜ao Gen´etica............... 44 4 ME´TODOS PROPOSTOS ........................................... 48 4.1 ALTERNATIVA PARA TRATAMENTO DE UNIDADES ......... 48 4.2 ESTRATE´GIA PARA EVITAR A OBTENC¸A˜O DE SOLUC¸O˜ES TRIVIAIS ........................................................ 50 4.3 UTILIZAC¸A˜O DE ARQUIVO EXTERNO ........................ 52 5 ESTUDOS DE CASOS............................................... 55 5.1 INTRODUC¸A˜O ................................................... 55 5.2 ESTUDO DE CASO 1: PROJETO DE UMA TRELIC¸A DE 2 BARRAS ......................................................... 55 5.3 ESTUDO DE CASO 2: PROJETO DE UMA VIGA SOLDADA ... 56 5.4 ESTUDO DE CASO 3: PROCESSO DE CORTE DE UMA BARRA DE METAL ....................................................... 60 5.5 ESTUDO DE CASO 4: PROJETO DE ENGRENAGENS COMPOSTAS ..................................................... 62 5.6 ESTUDO DE CASO 5: PROJETO DE UMA TRELIC¸A DE 10 BARRAS ......................................................... 63 6 EXPERIMENTOS COMPUTACIONAIS ............................ 65 6.1 INTRODUC¸A˜O ................................................... 65 6.2 ESTUDO DE CASO 1: PROJETO DE UMA TRELIC¸A DE 2 BARRAS ......................................................... 66 6.2.1 Problema Multiobjetivo........................................ 66 6.2.2 Descoberta de Conhecimento via Innovization.................. 68 6.3 ESTUDO DE CASO 2: PROJETO DE UMA VIGA SOLDADA ... 72 6.3.1 Problema Multiobjetivo........................................ 72 6.3.2 Descoberta de Conhecimento via Innovization.................. 73 6.4 ESTUDO DE CASO 3: PROCESSO DE CORTE DE UMA BARRA DE METAL ....................................................... 76 6.4.1 Problema Multiobjetivo........................................ 76 6.4.2 Descoberta de Conhecimento via Innovization.................. 77 6.5 ESTUDO DE CASO 4: PROJETO DE ENGRENAGENS COMPOSTAS ..................................................... 81 6.5.1 Problema Multiobjetivo........................................ 81 6.5.2 Descoberta de Conhecimento via Innovization.................. 83 6.6 ESTUDO DE CASO 5: PROJETO DE UMA TRELIC¸A DE 10 BARRAS ......................................................... 85 6.6.1 Problema Multiobjetivo........................................ 85 6.6.2 Descoberta de Conhecimento via Innovization.................. 86 7 CONCLUSO˜ES E TRABALHOS FUTUROS......................... 94 REFEREˆNCIAS ....................................................... 96