JUVÊNCIO GERALDO DE MOURA

USO DE ALGORITMOS EVOLUTIVOS HÍBRIDOS EM PROBLEMAS DE OTIMIZAÇÃO ESTRUTURAL DE TRELIÇAS

Belo Horizonte – MG Setembro de 2009

JUVÊNCIO GERALDO DE MOURA

USO DE ALGORITMOS EVOLUTIVOS HÍBRIDOS EM PROBLEMAS DE OTIMIZAÇÃO ESTRUTURAL DE TRELIÇAS Dissertação apresentada ao Curso de Mestrado em Modelagem Matemática e Computacional do Centro Federal de Educação Tecnológica de Minas Gerais, como requisito parcial à obtenção do título de Mestre em Modelagem Matemática e Computacional. Linha de pesquisa: Sistemas Inteligentes

Orientador:

Prof. Dr. Gray Farias Moita Centro Federal de Educação Tecnológica de Minas Gerais (CEFET-MG) Co-orientador:

Prof. Dr. Sérgio Ricardo de Souza CEFET-MG M ESTRADO EM M ODELAGEM M ATEMÁTICA E C OMPUTACIONAL C ENTRO F EDERAL DE E DUCAÇÃO T ECNOLÓGICA DE M INAS G ERAIS D IRETORIA DE P ESQUISA E P ÓS -G RADUAÇÃO

Belo Horizonte – MG Setembro de 2009

M97u

Moura, Juvêncio Geraldo de, Uso de Algoritmos Evolutivos Híbridos em Problemas de Otimização Estrutural de Treliças / Juvêncio Geraldo de Moura - Belo Horizonte: CEFET-MG, 2009. 75f. : il. Inclui Bibliografia. Dissertação (Mestrado em Modelagem Matemática e Computacional) - Centro Federal de Educação Tecnológica de Minas Gerais Orientador: Gray Farias Moita. 1 - Algoritmos evolutivos híbridos. 2 - Otimização de estruturas. 3 - Treliças. 4 - Heurísticas de refinamento. I. Moita, Gray Farias II. Centro Federal de Educação Tecnológica de Minas Gerais III. Título CDD 006.31

Folha de aprovação do projeto. Esta folha será fornecida pelo Programa de Pós-Graduação e deverá substituir esta.

Dedico esta pesquisa à minha família, pela motivação, incentivo, apoio e carinho. À minha esposa, pela paciência, apoio, compreensão, carinho, atenção, incentivo e principalmente pelo amor.

Agradecimentos Em primeiro lugar agradeço à Deus, por me dar inteligência, sabedoria, coragem e saúde para mais uma importante conquista. Obrigado Senhor! Ao meu orientador, Prof. Dr. Gray Farias Moita, pelas orientações, críticas e sugestões. Agradeço também pelos ensinamentos, paciência e por confiar na minha capacidade de desenvolver essa pesquisa. Ao meu co-orientador, Prof. Dr. Sérgio Ricardo de Souza, pelas orientações e contribuições importantes para o desenvolvimento da pesquisa. Agradeço também pelos ensinamentos e por confiar no meu trabalho. Ao João Paulo por oferecer o software OtimoEstrutura e ao Prof. Dr. Roque Pitangueira da UFMG, por fornecer o INSANE para realização dessa pesquisa. A todos os professores pelos ensinamentos e contribuições para aumentar meu conhecimento. À minha família pelo apoio, incentivo e carinho. À minha esposa, Sheila, amor da minha vida, pelo carinho, paciência, motivação, companheirismo e amor. Você e minha família foram também muito importantes para conclusão desse trabalho. Aos seus pais também sou grato. Ao Rusi, Fernando, Elias, Will, Manoel Junior e demais amigos do LSI que, de uma forma ou de outra, contribuíram com a amizade e com sugestões para a realização desse trabalho. Ao CEFET-MG pelo apoio financeiro à pesquisa e por acreditar no meu trabalho. Ao Laboratório de Sistemas Inteligentes (LSI) pelos recursos disponibilizados para realização deste trabalho. A todos que de alguma maneira colaboraram para concluir o trabalho e aumentar meu conhecimento, meus agradecimentos.

"A persistência é o caminho do êxito." Chaplin, Charlie.

Resumo A otimização estrutural é uma necessidade frequentemente encontrada pelos projetistas e engenheiros que visam minimizar custos de projetos nas construções. Para isso, é necessário reduzir a quantidade de material empregado nas estruturas, com o intuito de diminuir o peso, em conformidade com as restrições impostas pelo projeto. O problema de otimização abordado nessa pesquisa é encontrar o menor peso para estrutura treliçada. Assim, procura-se encontrar as dimensões mínimas suficientes para as áreas de seção transversal e, em alguns casos, o comprimento de cada barra, obedecendo às restrições. Nesse contexto foi proposto o desenvolvimento de um Algoritmo Evolutivo Híbrido baseado nos mecanismos de Algoritmos Genéticos (AG) com a utilização de métodos de refinamento como Descida Randômica e Pesquisa em Vizinhança Variável (Variable Neighborhood Search - VNS) para solução do problema de otimização estrutural de treliças planas. Foram implementados dois tipos de algoritmos. O primeiro foi aplicado ao problema de treliça com nós fixos e refina a solução inicial. Já o segundo, o refinamento ocorre após a evolução da população e foi aplicado em estruturas com coordenadas nodais móveis, assim é realizada a otimização de forma. Os resultados obtidos são analisados e comparados com os encontrados na literatura. PALAVRAS-CHAVE: algoritmos evolutivos híbridos, otimização de estruturas, treliças, heurísticas de refinamento.

Abstract In the construction industry, designers and engineers frequently face the problem of structural optimization, in order to minimize the costs of their projects. It is necessary to cut the amount of material used in the structures, to reduce the weight, taking into consideration the restrictions imposed by the project. The current optimization problem is to find the minimum weight of a truss structure. Hence, the minimal dimensions for the cross-sectional areas and, in some cases, for the length of the bars, are needed, observing the project limitations. In this context, a hybrid evolutionary algorithm was proposed that was based on the mechanisms of genetic algorithms (GAs), using heuristic search strategies such as Random Descent Method and Variable Neighborhood Search (VNS), for the structural optimization of plane trusses. Two types of algorithms were implemented. The first was applied to problem with fixed coordinates and a local search was used to calculate the initial solution. The second was applied to problem with moveable nodal coordinates and allowed shape optimization. The results were analyzed and compared with those found in the literature. KEY–WORDS: hybrid evolutionary algorithms, truss optimization, trusses, heuristics search.

Lista de Figuras 1.1 Exemplo de uma treliça. Fonte: Coda e Paccola (2006) . . . . . . . .

p. 16

5.1 Representação do cromossomo. . . . . . . . . . . . . . . . . . . . . .

p. 40

5.2 Crossover Clássico. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

p. 40

5.3 Crossover Adicional. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

p. 41

5.4 Mutação. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

p. 41

5.5 Representação do cromossomo. . . . . . . . . . . . . . . . . . . . . .

p. 44

5.6 Crossover. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

p. 45

5.7 Mutação. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

p. 46

6.1 Topologia da estrutura com 10 barras. Fonte: Yokota, Tagughi e Gen (1998) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

p. 51

6.2 Topologia inicial da estrutura com 18 barras. Fonte: Fawaz, Xu e Behdinan (2005) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

p. 56

6.3 Topologia do melhor resultado encontrado com AE02 para estrutura com 18 barras. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

p. 62

6.4 Topologia do melhor resultado encontrado com AEH02-DR para estrutura com 18 barras. . . . . . . . . . . . . . . . . . . . . . . . . . . .

p. 62

6.5 Topologia do melhor resultado encontrado com AEH02-VNS para estrutura com 18 barras. . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.6 Topologia da estrutura com 18 barras (Referência).

p. 62

. . . . . . . . . .

p. 62

7.1 Gráfico de convergência das execuções do AE01. . . . . . . . . . . .

p. 65

7.2 Gráfico de convergência das execuções do AEH01-DR. . . . . . . . .

p. 65

7.3 Gráfico de convergência das execuções do AEH01-VNS. . . . . . . .

p. 66

7.4 Gráfico com melhores resultados a cada execução do AEH01-VNS. .

p. 66

7.5 Gráfico de convergência das execuções do AE02. . . . . . . . . . . .

p. 67

7.6 Gráfico de convergência das execuções do AEH02-DR. . . . . . . . .

p. 68

7.7 Gráfico de convergência das execuções do AEH02-VNS. . . . . . . .

p. 69

7.8 Gráfico com melhores resultados a cada execução do AEH02. . . . .

p. 69

Lista de Tabelas 6.1 Restrições de projeto e valores de coeficientes. Fonte: Yokota, Tagughi e Gen (1998) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

p. 52

6.2 Melhores pesos a cada execução do AE01. . . . . . . . . . . . . . . .

p. 53

6.3 Melhores pesos a cada execução do AEH01-DR. . . . . . . . . . . . .

p. 53

6.4 Melhores pesos a cada execução do AEH01-VNS. . . . . . . . . . . .

p. 54

6.5 Melhores pesos obtidos com AEH01 em dez execuções para o problema de treliça com 10 barras. . . . . . . . . . . . . . . . . . . . . . .

p. 54

6.6 Melhores soluções obtidas em dez execuções para o problema de treliça com 10 barras. . . . . . . . . . . . . . . . . . . . . . . . . . . .

p. 55

6.7 Melhores pesos a cada execução do AE02. . . . . . . . . . . . . . . .

p. 58

6.8 Melhores pesos a cada execução do AEH02-DR. . . . . . . . . . . . .

p. 59

6.9 Melhores pesos a cada execução do AEH02-VNS. . . . . . . . . . . .

p. 59

6.10 Melhores pesos obtidos com o AEH02 em dez execuções para o problema de treliça com 18 barras. . . . . . . . . . . . . . . . . . . . . . .

p. 60

6.11 Tensão máxima e deslocamento máximo da melhor solução obtida para o problema de treliça com 18 barras. . . . . . . . . . . . . . . . .

p. 60

6.12 Melhores soluções obtidas com o AEH02 em dez execuções para o problema de treliça com 18 barras. . . . . . . . . . . . . . . . . . . . .

p. 61

Lista de Algoritmos 1

Pseudocódigo do Método de Descida Randômica. . . . . . . . . . . .

p. 26

2

Pseudocódigo do Método VNS. . . . . . . . . . . . . . . . . . . . . . .

p. 27

3

Pseudocódigo do AE01. . . . . . . . . . . . . . . . . . . . . . . . . . .

p. 37

4

Pseudocódigo do AEH01-DR. . . . . . . . . . . . . . . . . . . . . . . .

p. 38

5

Pseudocódigo do AEH01-VNS. . . . . . . . . . . . . . . . . . . . . . .

p. 39

6

Pseudocódigo do AEH02. . . . . . . . . . . . . . . . . . . . . . . . . .

p. 43

7

Pseudocódigo do Método de Busca Local Descida Randômica. . . . .

p. 48

Lista de Abreviaturas e Siglas AE Algoritmo Evolutivo AEH Algoritmo Evolutivo Híbrido AG Algoritmos Genéticos CEFET-MG Centro Federal de Educação Tecnológica de Minas Gerais DR Descida Randômica DEES/UFMG Departamento de Engenharia de Estruturas da Universidade Federal de Minas Gerais GPSI Grupo de Pesquisas em Sistemas Inteligentes GRASP Greedy Randomized Adaptive Search Procedure INSANE Interactive Structural Analysis Environment LSI Laboratório de Sistemas Inteligentes UFMG Universidade Federal de Minas Gerais VNS Variable Neighborhood Search

Sumário

1 INTRODUÇÃO

p. 16

1.1 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

p. 18

1.2 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

p. 19

1.3 Estrutura da Dissertação . . . . . . . . . . . . . . . . . . . . . . . . .

p. 20

2 REVISÃO BIBLIOGRÁFICA

p. 21

3 MÉTODOS HEURÍSTICOS

p. 25

3.1 Algoritmo Genético . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

p. 25

3.2 Heurísticas de Refinamento . . . . . . . . . . . . . . . . . . . . . . . .

p. 26

3.2.1 Descida Randômica . . . . . . . . . . . . . . . . . . . . . . . .

p. 26

3.2.2 Método de Pesquisa em Vizinhança Variável . . . . . . . . . .

p. 27

4 OTIMOESTRUTURA E INSANE

p. 29

4.1 OtimoEstrutura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

p. 29

4.1.1 Algoritmo Genético . . . . . . . . . . . . . . . . . . . . . . . . .

p. 30

4.2 INSANE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

p. 31

5 IMPLEMENTAÇÃO DOS ALGORITMOS

p. 34

5.1 Algoritmo Evolutivo Híbrido . . . . . . . . . . . . . . . . . . . . . . . .

p. 35

5.1.1 Algoritmo Evolutivo Híbrido 01 . . . . . . . . . . . . . . . . . .

p. 36

5.1.2 Algoritmo Evolutivo Híbrido 02 . . . . . . . . . . . . . . . . . .

p. 43

6 RESULTADOS COMPUTACIONAIS

p. 50

6.1 Otimização Estrutural de Treliças com 10 Barras . . . . . . . . . . . .

p. 50

6.1.1 Descrição do problema . . . . . . . . . . . . . . . . . . . . . .

p. 51

6.1.2 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

p. 52

6.2 Otimização Estrutural de Treliças com 18 Barras . . . . . . . . . . . .

p. 56

6.2.1 Descrição do problema . . . . . . . . . . . . . . . . . . . . . .

p. 56

6.2.2 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

p. 58

7 ANÁLISE DOS RESULTADOS COMPUTACIONAIS

p. 64

7.1 Otimização Estrutural de Treliças com 10 Barras . . . . . . . . . . . .

p. 64

7.1.1 Análises dos resultados . . . . . . . . . . . . . . . . . . . . . .

p. 64

7.2 Otimização Estrutural de Treliças com 18 Barras . . . . . . . . . . . .

p. 67

7.2.1 Análises dos resultados . . . . . . . . . . . . . . . . . . . . . .

p. 67

8 CONCLUSÃO 8.1 Trabalhos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Referências Bibliográficas

p. 70 p. 72 p. 73

16

1

INTRODUÇÃO

As estruturas treliçadas são utilizadas em projetos de grande porte, sendo facilmente encontradas em pontes, estádios de futebol, ginásios cobertos, viadutos e torres. As treliças são estruturas compostas por barras articuladas nas extremidades e interligadas por rótulas, que estão sujeitas, no presente contexto, somente a esforços axiais. Tal configuração deixa a estrutura leve e resistente.

Figura 1.1: Exemplo de uma treliça. Fonte: Coda e Paccola (2006)

Engenheiros e projetistas visam diminuir custos em projetos que utilizam treliças em construções, reduzindo a quantidade de material empregado nessas estruturas, com o intuito de diminuir seu peso, em conformidade com as restrições impostas pelo projeto. Este é um dos objetivos referenciados em problemas de otimização estrutural que podem ser encontrados na literatura. A otimização estrutural vem apresentando resultados positivos na construção civil, indústria automobilística e indústria aeroespacial. Sendo o objetivo principal a redução de custos. Existem três tipos de otimização estrutural: otimização dimensional, geométrica (forma) e topológica (CORDEIRO, 2007). A otimização dimensional tem como variáveis de projeto parâmetros de um elemento estrutural, tais como área de seção transversal e comprimento de barra (SANTANNA, 2002). Encontrar as melhores áreas de seção transversal das barras a fim de obter a máxima rigidez com mínimo volume de material é um exemplo desse tipo de otimização (BAHIA, 2005).

1 INTRODUÇÃO

17

A otimização de forma otimiza o contorno da estrutura, e a forma ótima do domínio de projeto deve ser encontrada (SANTANNA, 2002). Outra definição, dada por Annicchiarico e Cerrolaza (2001), relata que essa classe de otimização consiste em encontrar a melhor configuração de uma estrutura a qual melhore o comportamento mecânico e minimize uma ou mais variáveis de projeto, tais como o peso da estrutura ou concentrações de tensão. Na otimização topológica é definida a melhor forma possível da distribuição de material em um domínio pré-determinado considerando-se uma função custo e as restrições mecânicas. A variável de projeto, neste caso, é o próprio domínio, no qual se pode eliminar material, por exemplo, excluir barras (CORDEIRO, 2007). O termo topologia refere-se à disposição espacial dos membros estruturais e ao padrão de conectividade entre estes. A otimização topológica é mais genérica do que a de forma, devido à distribuição de material no interior do domínio de projeto ou por excluir itens do domínio. Em geral, altera-se a conexão do domínio e, consequentemente, a topologia (BAHIA, 2005). Segundo Bahia (2005), a otimização de forma altera o contorno, mas não permite modificar a topologia da estrutura, ou seja, não possibilita incluir ou remover parte do domínio. Desse modo, o problema que possui coordenadas nodais móveis desta pesquisa trata-se de otimização de forma e dimensional. Por meio das três classes de otimização estrutural é possível analisar a topologia, a configuração, o tipo de material e o dimensionamento dos elementos estruturais. Nos dois primeiros tipos de análises é possível encontrar qual o melhor tipo de estrutura a ser utilizada. Além de poder obter também a melhor disposição das barras, nós e apoios, para determinadas solicitações na estrutura, ou seja, trata-se da forma. O tipo de material influi nos métodos de cálculos a serem usados. O dimensionamento dos elementos estruturais se referem à determinação das características geométricas necessárias, por exemplo, área e formato da seção transversal (PRUDENTE, 1998). O ideal para otimizar uma estrutura seria aplicar todas as análises mencionadas anteriormente no processo de otimização. Porém, torna-se inviável trabalhar com todos os elementos citados ao mesmo instante. No entanto, alguns autores em suas pesquisas realizam a análise isolando alguns fatores, conforme Pereira (2007) e Prudente (1998). Na pesquisa de Prudente (1998), foram fixados o esquema estático, a configuração da estrutura e o material utilizado nos elementos estruturais. O trabalho de Pereira (2007) visou apenas à minimização do peso por meio da redução da área

1.1 Objetivos

18

de seção transversal de cada barra da estrutura. A pesquisa de Pereira (2007), que colaborou como integrante do Grupo de Pesquisas em Sistemas Inteligentes (GPSI) do Centro Federal de Educação Tecnológica de Minas Gerais (CEFET-MG), apresenta um estudo de algumas heurísticas computacionais para o processo de otimização estrutural. Em tal trabalho são descritos os métodos de otimização utilizados na busca pela redução do peso estrutural de treliças plana. A presente pesquisa consiste em um estudo da aplicação de um Algoritmo Evolutivo Híbrido (AEH), baseado nos mecanismos de Algoritmos Genéticos (AG), para otimização estrutural de treliças. Determinados indivíduos de cada geração são refinados com a utilização do método de busca local Descida Randômica e a metaheurística Variable Neighborhood Search (VNS). Em Pereira (2007) apenas a área de seção transversal é variável. Nesta pesquisa a forma estrutural pode ser modificada, sendo possível que as posições de alguns nós sejam alteradas. Os resultados obtidos são comparados com os encontrados pelo autor citado. A motivação para o desenvolvimento do AEH é principalmente o bom resultado obtido em Pereira (2007) com a utilização de Algoritmo Genético, além da grande quantidade de aplicações existentes na literatura que utilizam versões híbridas desse algoritmo para resolver determinados tipos de problemas e tiveram sucessos, conforme Lima (2008), Pisinger e Ropke (2007) e Grosan e Abraham (2007). Então, a hibridização do AG com heurísticas de refinamento pode obter melhores resultados que a utilização de apenas uma técnica. A seguir são descritos os objetivos da pesquisa bem como a metodologia aplicada para encontrar a solução do problema de otimização tratado.

1.1

Objetivos

O objetivo geral desta pesquisa é minimizar o peso e forma de treliças com a utilização de um Algoritmo Evolutivo Híbrido (AEH). Esse é baseado nos mecanismos de algoritmos genéticos com métodos de refinamento para otimização estrutural. Para tanto, esta pesquisa se propõe aos seguintes objetivos específicos: • Implementar o algoritmo evolutivo híbrido, com base no método heurístico AG

1.2 Metodologia

19

desenvolvido por Pereira (2007) juntamente com técnicas de refinamento, tais como, método de busca local Descida Randômica e a metaheurística VNS (Variable Neighborhood Search) (MLADENOVIC; HANSEN, 1997); • Modificar o AEH para solução do problema com nós móveis, sendo possível minimizar o peso e a forma da estrutura com uma nova variável; • Analisar a eficiência dos métodos aplicados e a melhor relação custo/benefício, em que o custo está relacionado à facilidade de implementação e o benefício está ligado à eficiência e à qualidade das soluções encontradas; • Realizar testes e simulações, comparando os resultados com os obtidos pelo software OtimoEstrutura (PEREIRA, 2007) e outros existentes na literatura, para comprovar a eficácia e a aplicabilidade de cada método proposto.

1.2

Metodologia

Primeiramente foi realizado um estudo da aplicação do Algoritmo Evolutivo Híbrido para solução do problema de otimização estrutural de treliças. O AEH possui operadores genéticos e refina indivíduos da geração inicial com a utilização do método de refinamento Descida Randômica ou VNS. As técnicas de busca local também foram utilizadas após a evolução de cada geração. O AEH implementado foi modificado para encontrar soluções para o problema de treliça com nós móveis, a fim de realizar a otimização de forma. Nesse problema, a área de seção transversal e as coordenadas nodais móveis são variáveis, sendo possível que as posições de alguns nós sejam alteradas. Para o desenvolvimento desta pesquisa, a metodologia adotada abrangeu as seguintes atividades: • Revisão bibliográfica; • Implementação do Algoritmo Evolutivo Híbrido; • Desenvolvimento do algoritmo para realizar a otimização de forma; • Realização de testes; • Análise e discussão dos resultados.

1.3 Estrutura da Dissertação

20

A primeira atividade buscou revisar a literatura, com ênfase nos tópicos: otimização de estrutura, treliças, otimização de forma, heurísticas computacionais, métodos de busca local, algoritmos evolutivos, INSANE (FONSECA; PITANGUEIRA, 2004), OtimoEstrutura (PEREIRA, 2007) e Java. O Algoritmo Evolutivo Híbrido foi implementado na linguagem de programação Java. A implementação teve como referência os mecanismos dos algoritmos genéticos juntamente com as técnicas de refinamento Descida Randômica ou VNS. Realizou-se uma análise da utilização dos métodos de refinamento para observar a importância do papel dessa técnica na heurística implementada. Para realizar a otimização de forma o AEH foi adaptado. O peso estrutural passa a ser minimizado por meio do dimensionamento dos elementos: área de seção transversal e comprimento das barras. Os métodos de refinamento utilizados nesse algoritmo foram aplicados após a evolução da população. Durante a realização de testes e simulações com os métodos desenvolvidos para a validação da eficácia dos algoritmos foi verificada a necessidade de modificar a estrutura inicial do AEH para realizar a otimização dimensional e de forma da treliça. No entanto, foram modificados os operadores genéticos e criada uma função de avaliação que penaliza as barras e nós que violam restrições impostas pelos projetos. Os resultados obtidos foram comparados com os encontrados na literatura e analisados.

1.3

Estrutura da Dissertação

Esta dissertação é organizada como descrito a seguir. O Capítulo 2 apresentada a revisão da literatura. Os métodos heurísticos e de refinamentos estudados são descritos no Capítulo 3. O software OtimoEstrutra (PEREIRA, 2007) e o INSANE (DEES/UFMG) são apresentados no Capítulo 4. O Capítulo 5 apresenta a implementação dos algoritmos desenvolvidos. No Capítulo 6 são apresentados os resultados. A análise é realizada no Capítulo 7. Por fim, o Capítulo 8 apresenta as conclusões da pesquisa e as perspectivas de trabalhos futuros.

21

2

REVISÃO BIBLIOGRÁFICA

Treliça é um dos principais tipos de estruturas da engenharia. É uma solução prática e econômica para muitas situações dessa área, como descrito no Capítulo 1. A otimização estrutural é um processo matemático que propõe encontrar uma configuração da estrutura mecânica que resulta em um desempenho ótimo. Por exemplo, encontrar mínima massa, máxima rigidez, desde que sejam respeitadas algumas restrições, como tensão de falha e frequência natural crítica (PARRA; FRIEDLANDER, 2006). Para minimizar os custos de projeto deste tipo de estrutura pode-se utilizar alguma técnica de otimização estrutural, seja por programação matemática ou por meio das heurísticas computacionais. Sobre esse assunto, pode-se encontrar na literatura diversas pesquisas que relatam problemas de otimização estrutural e técnicas para resolvê-los. Alguns desses trabalhos são descritos a seguir. Fawaz, Xu e Behdinan (2005) introduz um novo algoritmo evolutivo para projetos de otimização estrutural. Os testes de desempenho utilizam duas funções de comparação e demonstram que o novo algoritmo tem excelente desempenho de convergência quando aplicado em problemas de otimização multimodal. O algoritmo desenvolvido é usado para otimizar o projeto de treliça com 18 barras, cujo objetivo é minimizar o peso respeitando as restrições de tensão, área da seção, e de geometria. Otimização geométrica e topológica são abordadas em outros trabalhos, conforme Achtziger (2007). O autor aborda o problema clássico de treliças em que a área de seção transversal e as coordenadas nodais são simultaneamente otimizadas. Na otimização geométrica de treliças as posições das articulações são definidas como variáveis no problema de otimização. A otimização topológica tem por objetivo encontrar a configuração ótima de uma dada estrutura por meio das modificações no domínio (topologia). Já para otimização de forma foram encontradas pesquisas que aplicam métodos

2 REVISÃO BIBLIOGRÁFICA

22

de elementos finitos para solução do problema. Barbosa et al. (2005) propõe um método de otimização de forma e de malha para estruturas usando elementos finitos triangulares hierárquicos de grau dois. Isso é realizado por meio do balanceamento da norma da energia de deformação por distorção dos elementos e do método de relocação nodal. A máxima densidade de energia de deformação por distorção é considerada a melhor solução. O método proposto foi aplicado em um pilar de viaduto de uma autoestrada com estrutura de aço. Um algoritmo genético para otimização topológica de treliças planas é apresentado em Kawamura, Ohmori e Kito (2002). Esse trabalho descreve o uso do procedimento de pesquisa estocástico baseado em algoritmos genéticos para topologia de estruturas treliçadas. Uma nova metodologia para topologia de treliças baseada em elementos triangulares conectados é proposta. O método desenvolvido é comparado com os atuais. As vantagens de utilização desse método são significativas, por exemplo, o modelo da topologia criado não tem nenhuma barra inútil nem sobreposta indesejável e os resultados são sempre estáveis. Em Christoforo, Marconato e Oliveira (2007) é proposta uma metodologia de cálculo para determinar o valor ótimo das áreas de seção transversal para os elementos estruturais de uma treliça plana. Os Métodos dos Elementos Finitos e dos Mínimos Quadrados são utilizados para realizar a otimização dimensional. Os resultados encontrados foram considerados satisfatórios. Um algoritmo genético para otimizar a massa de treliças planas e espaciais com variáveis de projeto contínuas e discretas é proposto em Guerra (2008). São considerados critérios de normas para resolver o problema do dimensionamento dos elementos, tais como restrições em condições de tensões, flambagem e deslocamento. Foi utilizado o toolbox de algoritmo genético do Matlab para realizar a otimização dessas estruturas. O AG aplicado foi considerado eficiente e robusto aos problemas exemplos. Outro tipo de algoritmo (Restauração Inexata - RI) é proposto em Gomes e ANDO JUNIOR (2006). Essa abordagem engloba os problemas de dimensionamento geométrico e topológico, resultando num modelo de programação não linear. Trata-se de um problema de otimização discreta e para modelá-lo utiliza-se a abordagem conhecida como estrutura base. A especialização do RI é utilizada para determinar a topologia ótima de treliças. Resolvem-se simultaneamente problemas de dimensionamento e topologia. Existem algoritmos heurísticos aplicados a estes tipos de problemas, conforme

2 REVISÃO BIBLIOGRÁFICA

23

pesquisa de Yuefang, Huanchun e Lihua (1998). Os autores propõem um algoritmo chamado Rank Value Algorithm para resolver problemas de otimização topológica de estruturas com variáveis discretas. O problema de um modelo de otimização discreta é discutido e o algoritmo desenvolvido é aplicado em exemplos. O projeto ótimo discreto pode ser controlado pelo isolamento das variáveis de ajuste. Os modelos utilizados no estudo de Fredricson (2005) são estruturas com articulações flexíveis. Cada articulação é modelada com um grupo de sub-elementos para suportar mudanças topológicas nas articulações. É usada uma variável de projeto, área, para controlar o tamanho do elemento global e auxiliar a mudança topológica. Outra variável é a taxa de comprimento que controla a seção transversal das vigas e as propriedades de rigidez interna das articulações. O artigo apresenta duas extensões para otimização topológica ótima. Primeiramente, penaliza as articulações estruturais que introduz a possibilidade de encontrar uma topologia com menos complexidade em termos de número de conexões de barras. Depois, um método de interpolação material é introduzido para auxiliar o projeto de material misto. Prudente (1998) descreve o problema de otimização de estruturas treliçadas planas de aço utilizando variáveis discretas. Apresenta um processo de busca da solução de mínimo peso para treliças, utilizando-se seções formadas por perfis comerciais comuns, dimensionadas segundo a norma brasileira para projeto e execução de estruturas de aço de edifícios. O método do gradiente inteiro é utilizado com alguns critérios modificados para melhorar o desempenho e considerar a relação não linear entre as características geométricas dos perfis. O autor aborda conceitos matemáticos básicos envolvidos no processo de otimização, análise de estruturas treliçadas planas e a formulação para o dimensionamento de barras sujeitas a tração ou compressão. Coello, Rudnick e Christiansen (1994) propõem o uso do algoritmo genético como uma ferramenta para resolver problemas de otimização multiobjetivo de estruturas. Técnicas de programação matemática, como Monte Carlo Methods e Osyczka’s Multicriterion Optimization System são apresentadas. Além de técnicas multiobjetivos que utilizam AG, como VEGA (Vector Evaluated Genetic Algorithm), Lexicographic Ordering, Weighted Sum, Algoritmo Genético Multiobjetivo, entre outras. Uma nova técnica de otimização multiobjetivo é proposta e aplicada em dois problemas de projeto de treliças. O resultado produzido por esta nova heurística é comparado com os encontrados por técnicas de programação matemática e heurísticas baseadas em AG. Ainda segundo o autor, a técnica gera melhores soluções e pode ser usada como ferramenta

2 REVISÃO BIBLIOGRÁFICA

24

de otimização numérica confiável. Algoritmos genéticos, além de outras heurísticas, também são implementados para solução de problema de otimização estrutural em Pereira (2007). Os algoritmos implementados são aplicados à estrutura de treliças planas a fim de obterem as dimensões mínimas suficientes para as áreas de seção transversal de cada barra, obedecendo às restrições impostas pelo projeto. Uma análise do comportamento dos métodos heurísticos aplicados em problemas de treliças planas com estruturas de dez, dezoito e quarenta e sete barras é realizada. Esses três tipos de configurações estruturais foram baseados em problemas propostos pelos autores: Yokota, Tagughi e Gen (1998); Fawaz, Xu e Behdinan (2005); Castro (2001), respectivamente. Segundo o autor os resultados foram bons comparados aos encontrados na literatura e podem ser melhorados de acordo com as sugestões apresentadas para trabalhos futuros. Nessa última pesquisa, um software de análise estrutural é utilizado em conjunto com as heurísticas implementadas para verificar e validar os resultados obtidos, que devem atender aos requisitos de projeto como deslocamentos máximos permitidos e tensões máximas suportadas. Desse modo, é possível que os métodos de otimização utilizados encontrem o melhor resultado para o peso estrutural. Esse programa é o INSANE, desenvolvido em Java pelo Departamento de Engenharia de Estruturas (DEES) da Universidade Federal de Minas Gerais (UFMG) (FONSECA; PITANGUEIRA, 2004). Devido aos bons resultados encontrados por Pereira (2007) com a utilização de algoritmos genéticos, propõe-se nesta pesquisa melhorar as soluções por meio de métodos de busca local aplicados ao AG. Essas técnicas são utilizadas em problemas de otimização e são também conhecidas como heurísticas de refinamento. Os métodos de busca local constituem uma família de técnicas baseadas na noção de vizinhança. Essa classe de heurística inicia-se a partir de uma solução inicial qualquer, obtida aleatoriamente ou por uma heurística construtiva (por exemplo, Algoritmo Genético), que a cada iteração, caminha de vizinho para vizinho de acordo com a definição de vizinhança adotada. Método da Descida ou Subida, Método Primeiro de Melhora, Método Randômico de Descida ou Subida, Método Randômico Não Ascendente ou Descendente, são alguns exemplos de técnicas de busca local (SOUZA, 2005).

25

3

MÉTODOS HEURÍSTICOS

Neste capítulo é descrito o funcionamento dos métodos heurísticos utilizados para realizar a otimização do problema abordado na pesquisa. O Algoritmo Genético é utilizado de forma simples e com métodos de refinamento da solução. O AG é chamado de Algoritmo Híbrido, quando utiliza um método de busca local ou uma metaheurística para tentar melhorar a solução. Nas seções seguintes são descritos o funcionamento desses métodos heurísticos.

3.1

Algoritmo Genético

Segundo Goldberg (1989), Algoritmo Genético é uma técnica de busca inspirada na biologia evolutiva, como hereditariedade, mutação, seleção natural e recombinação (crossover ). A solução ótima de um determinado problema é encontrada por meio do processamento de uma população inicializada aleatoriamente ou criada por uma heurística construtiva. Os AG empregam um processo adaptativo e paralelo de busca de soluções em problemas complexos. A otimização estrutural é considerada um desses tipos de problemas. Portanto, diminuir o peso destas estruturas é importante para obter o menor custo. No presente trabalho foi realizado um estudo da aplicação desse algoritmo para solução do problema de otimização de treliças planas. Um estudo mais detalhado sobre AG pode ser encontrado em Goldberg (1989) e Sastry, Goldberg e Kendall (2005).

3.2 Heurísticas de Refinamento

3.2

26

Heurísticas de Refinamento

As heurísticas de refinamento são utilizadas em problemas de otimização com finalidade de escapar de um ótimo local para encontrar um ótimo global. São conhecidas como técnicas de busca local e baseadas na noção de vizinhança. Essas técnicas partem de uma solução inicial qualquer e caminham, a cada iteração, de vizinho para vizinho, de acordo com a definição de vizinhança adotada, para que a solução inicial seja melhorada. Para exemplificar, seja S o espaço de pesquisa de um problema de otimização e f a função objetivo a minimizar. A função N, a qual depende da estrutura do problema tratado, associa a cada solução s ∈ S, sua vizinhança N(S) ⊆ S. Cada solução s0 ∈ N(s) é chamada de vizinho de s. Denomina-se movimento a modificação m que transforma uma solução s em outra, x0 , que esteja em sua vizinhança. Representa-se essa operação por s0 ← s ⊕ m (SOUZA, 2005).

3.2.1

Descida Randômica

O Método Randômico de Descida é um método de busca local que consiste em encontrar um vizinho qualquer que seja melhor que a solução corrente e aceitá-lo. Caso não seja encontrado, a solução corrente permanece e outro vizinho é gerado. Após um número fixo de iterações sem melhora no valor da melhor solução obtida, o procedimento é interrompido (SOUZA, 2005). Algoritmo RandomicoDescida ( f (.), N(.), IterMax, s); 1 Iter = 0; {Contador de iterações sem melhora} 2 enquanto (Iter < IterMax) faça 3 Iter = Iter + 1; 4 Selecione aleatoriamente s0 ∈ N(s); 5 se ( f (s0 ) < f (s)) então 6 Iter = 0; 7 s ← s0 ; 8 fim se 9 fim enquanto 10 Retorne s; fim Algoritmo 1: Pseudocódigo do Método de Descida Randômica. O Algoritmo 1 apresenta o pseudocódigo da heurística de refinamento, Descida Randômica, aplicada ao melhoramento de uma solução s em um problema de minimi-

3.2 Heurísticas de Refinamento

27

zação de uma função f (.). Uma estrutura de vizinhança N(.) é utilizada para selecionar aleatoriamente uma solução vizinha. ItexMax é o número máximo de iterações sem melhora no valor da função de avaliação. Na Seção seguinte é descrita a metaheurística de Pesquisa em Vizinhança Variável. Um método de busca local que permite escapar do ótimo local.

3.2.2

Método de Pesquisa em Vizinhança Variável

O Método de Pesquisa em Vizinhança Variável (Variable Neighborhood Search VNS), proposto por Mladenovic e Hansen (1997), explora o espaço de soluções até encontrar uma solução melhor que a corrente. Essa técnica é de fácil entendimento e implementação. Além disso, em problemas diversificados foi constatado o bom desempenho desse método robusto e eficiente, como em Pisinger e Ropke (2007) e Grosan e Abraham (2007). O pseudocódigo do método VNS é apresentado no Algoritmo 2. Algoritmo VNS(); 1 Seja s0 uma solução inicial; 2 Seja r o número de estruturas diferentes de vizinhança; 3 s ← s0 ;{Solução Corrente} 4 enquanto (Critério de parada não for satisfeito) faça 5 k ← 1; 6 enquanto (k ≤ r) faça 7 Gere um vizinho qualquer s0 ∈ N (k) (s); 8 s00 ← BuscaLocal(s0 ); 9 se ( f (s00 ) < f (s)) então 10 s ← s00 ; 11 k ← 1; 12 senão 13 k ← k + 1; 14 fim se 15 fim enquanto 16 fim enquanto 17 Retorne s; fim Algoritmo 2: Pseudocódigo do Método VNS. A técnica VNS explora o espaço de soluções por meio de trocas criteriosas de estruturas de vizinhança. Essa metaheurística não segue um trajetória. As vizinhanças são exploradas gradativamente mais distantes da solução corrente e focaliza a busca

3.2 Heurísticas de Refinamento

28

em torno de uma nova solução, se um movimento de melhora é concluído. Essa técnica possui um método de busca local que é aplicado a solução corrente. A busca local pode utilizar diferentes estruturas de vizinhanças (SOUZA, 2005).

29

4

OTIMOESTRUTURA E INSANE

Neste capítulo é apresentado o software de otimização estrutural correlato e o outro de análise estrutural. O primeiro, desenvolvido por Pereira (2007), é utilizado para otimizar estruturas treliçadas de 10, 18 e 47 barras. Para isso, foram utilizados métodos heurísticos computacionais como, Algoritmos Genéticos, Pesquisa em Vizinhança Variável, GRASP, Recozimento Simulado, Busca Tabu e Colônia de Formigas. O segundo é um software de análise estrutural desenvolvido por pesquisadores da UFMG (FONSECA; PITANGUEIRA, 2004). Esse último atua de forma integrada com o OtimoEstrutura para calcular valores relativos à engenharia com a finalidade de ajudar a validar a estrutura tratada.

4.1

OtimoEstrutura

O software OtimoEstrutura, desenvolvido por Pereira (2007), objetiva analisar o comportamento dos métodos heurísticos aplicados ao problema de otimização estrutural. As heurísticas computacionais implementadas para solucionar o problema de treliças planas são utilizadas com o intuito de fornecer métodos alternativos para minimizar o peso e, consequentemente, o custo destas estruturas. Existem restrições impostas pelo projeto que devem ser respeitadas para diminuir o peso da treliça, como tensão e deslocamento máximos permitidos. As heurísticas, Algoritmos Genéticos, Pesquisa em Vizinhança Variável, GRASP, Recozimento Simulado, Busca Tabu e Colônia de Formiga são implementadas para os problemas de otimização de treliças com 10, 18 e 47 barras. Uma análise dos resultados e comportamentos de cada heurística implementada é realizada, sendo descritas as vantagens e desvantagens de cada método. Segundo o autor, o Algoritmo Genético é bastante eficiente para o problema com treliça de 10 e 18 barras. Os métodos VNS e GRASP não apresentam resultados

4.1 OtimoEstrutura

30

satisfatórios para treliça com 18 e 47 barras. O Recozimento Simulado comprova ser o melhor método de relação custo/benefício, por possuir fácil implementação e calibração, além de obter bons resultados com um tempo computacional reduzido. Busca Tabu e Colônia de Formigas são eficientes, principalmente quando o problema tratado exige qualidade de respostas e tempo computacional. O AG de Pereira (2007), descrito na Seção a seguir, foi escolhido para ser modificado nesta pesquisa com a finalidade de encontrar melhores resultados. No novo AG proposto foram modificados os operadores genéticos e implementado um método de busca local, Descida Randômica e uma metaheurística, VNS, para refinar os indivíduos de cada geração. Além disso, para um dos problemas de treliça é realizada a otimização de forma da estrutura.

4.1.1

Algoritmo Genético

O algoritmo proposto utiliza representação real, de maneira que cada posição do cromossomo é um valor real para a área de seção transversal das barras da treliça tratada. Os parâmetros de calibragem utilizados foram: o tamanho da população definido em 20 indivíduos, o número máximo de gerações foi de 1500, e as probabilidades de ocorrer mutação e crossover foram 30% e 60%, respectivamente.

Representação do cromossomo O cromossomo de uma estrutura treliçada com N barras é representado por um vetor com N posições. Cada posição contém o valor da área da seção transversal de cada barra.

Geração inicial O processo de geração inicial gera indivíduos aleatórios e factíveis (que respeitam as restrições de projeto), a partir de uma população inicial aleatória. Para garantir a factibilidade dos indivíduos é verificado se o indivíduo gerado aleatoriamente não possui alguma barra que viole a tensão máxima permitida ou o deslocamento.

4.2 INSANE

31

Crossover No crossover são gerados dois filhos a partir do cruzamento de dois pais até que a nova população tenha 20 indivíduos. O sistema determina com uma probabilidade de 50%, a escolha de uma das duas possibilidade de ocorrer crossover, Clássico ou Adicional. O crossover Clássico gera um mesmo ponto de corte nos cromossomos pais. Para gerar o filho, cruzam-se os pais, sendo a metade inicial do primeiro pai, com a metade final do segundo pai. Quando o crossover Adicional é escolhido, geram-se 2 pontos de corte nos cromossomos pais, dividindo-os em três partes. O filho 1 recebe a primeira parte do pai 1 e a segunda parte do pai 2. A terceira parte é do próprio filho 1, que foi inicializado com valores para as áreas de seção transversal de acordo com o intervalo encontrado nas restrições de projeto. O filho 2 recebe a segunda parte do pai 1 e a primeira parte do pai 2, a terceira parte é do próprio filho 2.

Mutação Na mutação, um indivíduo é escolhido aleatoriamente e um dos genes desse cromossomo, que contém um valor da área de seção transversal de determinada barra, é modificado também de forma aleatória. Quando um indivíduo é selecionado para sofrer mutação, pode-se tornar infactível. Caso isso ocorra, realiza-se a mutação novamente até que seja factível.

Seleção A técnica de seleção utilizada é Elitismo. Para cada geração, a população é ordenada e o operador de seleção escolhe a metade dos indivíduos da população, sendo que os mais aptos tem maior probabilidade de serem selecionados.

4.2

INSANE

O INSANE (Interactive Structural Analysis Environment - Ambiente Interativo de Análise Estrutural) é um projeto do Departamento de Engenharia de Estruturas da UFMG que visa o desenvolvimento de softwares na área de métodos numéricos e computacionais aplicados à engenharia. Esse software foi cedido por Fonseca e Pitangueira (2004).

4.2 INSANE

32

Segundo Penna e Pitangueira (2007), o programa de análise estrutural possui aplicações gráficas interativas de pré-processamento (criação de modelos com recursos gráficos), processamento (resolução numérica do modelo) e pós-processamento (visualização dos resultados), de modelos discretos para problemas de engenharia. Fonseca (2008) define que o processamento é uma aplicação que representa o núcleo numérico do sistema e é o responsável pela obtenção dos resultados de diferentes modelos discretos de análise estrutural. O pré-processamento é utilizado para criar modelos com recursos gráficos interativos. Os resultados podem ser visualizados por meio de aplicações gráficas de pós-processamento. O INSANE foi implementado conforme o paradigma de orientação a objetos na linguagem de programação JAVA, o que facilitou a integração com o OtimoEstrutura. Nesta pesquisa, o INSANE é utilizado para realizar a análise estrutural do problema investigado e verificar a factibilidade da estrutura otimizada quanto aos requisitos do projeto. Ao inicializar o OtimoEstrutura é necessário carregar um arquivo XML (IniFile.XML) com informações importantes, que definem as características do problema abordado. O objetivo desse arquivo é fornecer dados ao INSANE para realizar a análise das soluções. Para cada problema é preciso alterar as informações desse arquivo, que estão relacionadas à quantidade de barras da estrutura, o deslocamento máximo permitido, a tensão máxima suportada, a massa específica do material, os intervalos das áreas de seção transversal permitidos das barras, o intervalo de variação das coordenadas nodais, o tempo máximo de execução para o Algoritmo Genético, a precisão de casas decimais para os cálculos e o caminho do arquivo gerado no INSANE. Esse arquivo, com extensão .ISN, deve ser criado no INSANE antes de iniciar o OtimoEstrutura. Ele contém a modelagem do problema abordado, ou seja, o formato da treliça, a quantidade de barras, os valores das áreas das seções transversais, as coordenadas nodais e as cargas aplicadas em cada nó. A cada melhora da solução do problema tratado é criado o arquivo MELHOR.XML, que armazena todas as informações dessa solução e outras necessárias para serem importadas pelo INSANE. Desse modo, é possível visualizar o resultado da forma da melhor estrutura treliçada encontrada. O INSANE é carregado em segundo plano e aguarda as estruturas que serão analisadas. O OtimoEstrutura gera uma determinada configuração de barras, criada por meio do arquivo de inicialização, citado anteriormente. Após essa etapa o arquivo que contém o modelo do INSANE, informado no IniFile.XML é acessado. Desse modo, é

4.2 INSANE

33

possível modificar as áreas de seção transversal do modelo conforme com a configuração gerada, ou seja, atualizar o modelo de acordo com a solução analisada. Para alguns problemas, as coordenadas nodais também podem ser modificadas. A partir daí, é executado o método analyseModel() da classe StructuralMech do INSANE. Este comando analisa o modelo e retorna os valores, como deslocamentos dos nós, comprimentos e ações nas extremidades das barras. Esses são necessários para garantir que a solução do problema seja válida. O comprimento é importante para calcular o peso da estrutura. A ação na extremidade de cada barra é utilizada para calcular a tensão, como mostra a Equação 5.4 na Seção 5.1.2. A tensão de uma barra é o resultado da força aplicada na barra dividida pela área da seção transversal da mesma. O calculo para verificar a tensão máxima permitida é realizado no OtimoEstrutura. O deslocamento é calculado pelo INSANE e verificado, quanto ao máximo permitido, no software de otimização. Cada barra que violar a tensão ou o deslocamento é penalizada com um valor alto, conforme função de avaliação mostrada na Equação 5.3, na Seção 5.1.2. A integração dos dois sistemas funciona de maneira eficiente. A troca de informações entre eles é rápida, o que garante menor tempo para realização das análises sem afetar o desempenho dos algoritmos. Em Pereira (2007) é explicada a integração e o funcionamento dos dois sistemas com mais detalhes, além de outras informações, como implementação dos algoritmos, aplicação, resultados e análises. Segundo Pereira (2007), os resultados obtidos foram considerados excelentes. A maioria das soluções encontradas foram melhores que os valores de referência para alguns problemas. Dentre as heurísticas implementadas, o Algoritmo Genético destacou-se pela eficiência e robustez. Esse algoritmo pode ser melhorado com a hibridização, ou seja, com a utilização de outra heurística a fim de refinar as soluções obtidas com o AG. Então, a pesquisa atual tem por objetivo implementar um algoritmo evolutivo híbrido, baseado nos mecanismos de AG com heurísticas de refinamento para encontrar melhores resultados. Esse algoritmo é explicado com detalhes no capítulo seguinte.

34

5

IMPLEMENTAÇÃO DOS ALGORITMOS

Este capítulo apresentada as características do Algoritmo Evolutivo Híbrido (AEH) proposto para a solução dos problemas de otimização estrutural de treliças planas. O AEH foi implementado com base nos Algoritmos Genéticos. Métodos de refinamento foram utilizados após a evolução da população, o que caracteriza um Algoritmo Híbrido. As técnicas abordadas foram Método de Busca Local Descida Randômica e Pesquisa em Vizinhança Variável. A representação utilizada no AG foi real, ou seja, o cromossomo é representado por um vetor de reais, contendo as áreas de seção transversal e as coordenadas nodais. Os valores do cromossomo representam a treliça que deve ser minimizada. Foram utilizados dois tipos de estruturas do AEH para os problemas. O primeiro algoritmo implementado, Algoritmo Evolutivo Híbrido 01 (AEH01), é apresentado na Seção 5.1.1. Já a Seção 5.1.2 mostra a segunda proposta para o Algoritmo Evolutivo Híbrido 02 (AEH02), que permite alterar a forma da estrutura treliçada. O AEH01 inicia com a geração de duas populações. Uma com 20 indivíduos, sendo todos factíveis e outra com o mesmo número, mas sem verificar a factibilidade. Depois, calcula-se a função de avaliação dessa população inicial e aplica-se a busca local Descida Randômica ou VNS. Após o refinamento da solução inicial é gerada uma nova população com a utilização dos operadores genéticos. Para isso, primeiramente aplica-se mutação (probabilidade de 30%) no filho 1. Realiza-se mutação forçada no segundo filho, caso o filho 1 tenha sofrido mutação. A mutação forçada é utilizada para gerar somente indivíduos factíveis. Não é verificada a probabilidade de mutação nesse caso. Não ocorrendo mutação, realiza-se crossover (probabilidade de 60%) Clássico ou Adicional. Caso não ocorra crossover, os dois filhos recebem uma cópia dos pais e realiza-se mutação nos descendentes de acordo com a probabilidade. Após gerar todos os novos indivíduos é realizada a avaliação da população para descobrir

5.1 Algoritmo Evolutivo Híbrido

35

o melhor peso. O AEH02 gera uma solução inicial aleatória com uma população de N/2 indivíduos, realiza crossover até completar a população com N indivíduos. Depois, ocorre mutação, os cromossomos são avaliados e aplica-se a metaheurística VNS ou Descida Randômica. São selecionados N/2 indivíduos para pertencer a nova população por meio das técnicas de Elitismo e Roleta Russa. Esse processo é realizado até o número máximo de gerações. As estruturas do AEH01 e AEH02 são descritas com detalhes nas seções seguintes.

5.1

Algoritmo Evolutivo Híbrido

O Algoritmo Evolutivo Híbrido proposto é baseado nos mecanismos de Algoritmos Genéticos com heurísticas de refinamento. Dois método de busca local são implementados no AEH para refinar as soluções a fim de encontrar melhores resultados. As heurísticas utilizadas são Pesquisa em Vizinhança Variável (VNS) e Descida Randômica. A motivação para o desenvolvimento do AEH é grande quantidade existente na literatura de aplicações que utilizaram essa técnica para resolver algum tipo de problema e obtiveram bons resultados. Além disso, o AG implementado por Pereira (2007) obteve boas soluções em relação ao valor de referência do problema tratado e um excelente desempenho, converge rápido para bons resultados. No entanto, a utilização de algoritmos evolutivos com método de refinamento pode melhorar ainda mais a solução. Os algoritmos evolutivos buscam tratar estruturas de objetos abstratos de uma população. Por exemplo, variáveis de um problema de otimização, dos quais são manipulados por operadores inspirados na evolução biológica. Esses operadores objetivam a busca para a solução de um problema e são comumente chamados de operadores genéticos. Algoritmo Genético é uma técnica de busca aleatória direcionada capaz de obter a solução ótima global num espaço de busca complexo multidimensional. Os AG são baseados na evolução natural das espécies, usando operadores genéticos inspirados no processo de evolução natural. Estes operadores manipulam indivíduos de uma po-

5.1 Algoritmo Evolutivo Híbrido

36

pulação, por meio de gerações, para melhorar a adaptação (fitness) gradativamente. Os indivíduos numa população, também denominados de cromossomos, podem utilizar representação real ou binária. As heurísticas de refinamento exploram o espaço de busca que pode ter uma ou mais estruturas de vizinhanças. A estrutura de vizinhança é importante para que boas soluções possam ser encontradas. A cada iteração a solução encontrada pelo método de busca pode ser melhor que a corrente. Caso afirmativo, a melhor solução passa ser a solução obtida. Do contrário, continua a percorrer os vizinhos até um número máximo de iterações definido pelo usuário de acordo com o problema. O método de Descida Randômica analisa um vizinho qualquer e aceita somente se ele for melhor que a solução corrente. Se não for aceito, outro vizinho é gerado. A técnica termina após um número de iterações sem melhora. Já o VNS explora o espaço de busca por meio de trocas sistemáticas de estruturas de vizinhanças. Assim, pode-se usar diferentes tipos de movimentos que permitem explorar vizinhanças mais distantes da solução corrente e focar a busca em torno de uma solução, caso um movimento de melhora seja realizado (SOUZA, 2005). Nas seções seguintes são descritos como os algoritmos citados anteriormente foram implementados.

5.1.1

Algoritmo Evolutivo Híbrido 01

O Algoritmo Evolutivo Híbrido proposto baseia-se na utilização de um Algoritmo Genético com heurísticas de refinamento aplicadas após geração inicial dos indivíduos com a finalidade de encontrar melhores resultados para problemas com coordenadas nodais fixas. Os algoritmos 3, 4 e 5 mostram os pseudocódigos dos algoritmos evolutivos: sem métodos de refinamento (AE01), híbrido com busca local Descida Randômica (AEH01-DR) e híbrido com Pesquisa em Vizinhança Variável (AEH01-VNS), respectivamente. N é a quantidade de indivíduos, γ e δ é um número gerado de forma aleatória entre 0 e 1, para realizar crossover e mutação, respectivamente. A estrutura do AEH para este tipo de treliça é descrita nas próximas seções.

5.1 Algoritmo Evolutivo Híbrido

37

Algoritmo AE01(); 1 Gera uma população inicial com indivíduos factíveis (popVelha); 2 Gera uma população inicial com indivíduos não factíveis (popNova); 3 Avalia a população inicial (popVelha); 4 enquanto (Critério de parada não for satisfeito) faça{Número máximo de gerações} 5 Seleciona os N/2 melhores indivíduos (Elitismo) que poderão passar pela mutação ou crossover 6 para ind de 0 para N faça 7 Seleciona dois indivíduos distintos (pais); 8 se (δ < probabilidadeMutação) então 9 Realiza mutação; 10 senão se (γ < probabilidadeCrossover) então 11 Realiza crossover; 12 Realiza mutação; {de acordo com a probabilidade} 13 senão 14 Clona os indivíduos selecionados. 15 fim se 16 Avalia indivíduo; 17 fim para 18 Insere os novos indivíduos na população; 19 fim enquanto 20 Apresenta os resultados; fim Algoritmo 3: Pseudocódigo do AE01.

5.1 Algoritmo Evolutivo Híbrido

38

Algoritmo AEH01-DR(); 1 Gera uma população inicial com indivíduos factíveis (popVelha); 2 Gera uma população inicial com indivíduos não factíveis (popNova); 3 Avalia a população inicial (popVelha); 4 Aplica Descida Randômica (popVelha); 5 enquanto (Critério de parada não for satisfeito) faça{Número máximo de gerações} 6 Seleciona os N/2 melhores indivíduos que poderão passar pela mutação ou crossover (Elitismo) 7 para ind de 0 para N faça 8 Seleciona dois indivíduos distintos (pais); 9 se (δ < probabilidadeMutação) então 10 Realiza mutação; 11 senão se (γ < probabilidadeCrossover) então 12 Realiza crossover; 13 Realiza mutação; {de acordo com a probabilidade} 14 senão 15 Clona os indivíduos selecionados. 16 fim se 17 Avalia indivíduo; 18 fim para 19 Insere os novos indivíduos na população; 20 fim enquanto 21 Apresenta os resultados; fim Algoritmo 4: Pseudocódigo do AEH01-DR.

5.1 Algoritmo Evolutivo Híbrido

39

Algoritmo AEH01-VNS(); 1 Gera uma população inicial com indivíduos factíveis (popVelha); 2 Gera uma população inicial com indivíduos não factíveis (popNova); 3 Avalia a população inicial (popVelha); 4 Aplica VNS (popVelha); 5 enquanto (Critério de parada não for satisfeito) faça{Número máximo de gerações} 6 Seleciona os N/2 melhores indivíduos que poderão passar pela mutação ou crossover (Elitismo) 7 para ind de 0 para N/2 faça 8 Seleciona dois indivíduos distintos (pais); 9 se (δ < probabilidadeMutação) então 10 Realiza mutação; 11 senão se (γ < probabilidadeCrossover) então 12 Realiza crossover; 13 Realiza mutação; {de acordo com a probabilidade} 14 senão 15 Clona os indivíduos selecionados. 16 fim se 17 Avalia indivíduo; 18 fim para 19 Insere os novos indivíduos na população; 20 fim enquanto 21 Apresenta os resultados; fim Algoritmo 5: Pseudocódigo do AEH01-VNS.

5.1 Algoritmo Evolutivo Híbrido

40

Representação do cromossomo O cromossomo de uma estrutura treliçada com N barras é representado por um vetor com N posições. Cada posição contém o valor da área da seção transversal (a) de cada barra.

Figura 5.1: Representação do cromossomo.

Critérios de parada O critério de parada é definido quando o número máximo de gerações é atingido. Geração inicial da população A população inicial é gerada aleatoriamente com N indivíduos factíveis. Os valores são gerados respeitando as restrições impostas pelo projeto. Crossover Para realizar o crossover, selecionam-se dois indivíduos pais da geração inicial, aplica-se o cruzamento para gerar dois filhos, com a probabilidade de 60%. O crossover pode ser realizado de duas maneiras: Clássico ou Adicional.

Figura 5.2: Crossover Clássico.

No primeiro caso, seleciona-se um ponto de corte, como mostrado na Figura 5.2. O conteúdo da primeira parte do pai 1 vai para o filho 1 e a segunda parte para o filho

5.1 Algoritmo Evolutivo Híbrido

41

2. Depois a primeira parte do pai 2 vai para o filho 2 e a outra parte para o filho 1, como mostrado na Figura 5.2. Para o crossover Adicional, apresentado na Figura 5.3, são selecionados dois pontos de corte. Dois indivíduos filhos são criados com valores aleatórios. Como mostrado na Figura 5.3, o filho 1 recebe a primeira parte do pai 1 e a segunda do pai 2. A terceira parte é do próprio filho 1. O segundo filho recebe a segunda parte do pai 1 e a primeira do pai 2. A terceira parte é do próprio filho 2.

Figura 5.3: Crossover Adicional.

Mutação A mutação é efetuada alterando-se o valor de um gene de um indivíduo sorteado aleatoriamente com probabilidade igual a 30%. Caso ocorra mutação, seleciona-se aleatoriamente uma posição do vetor que contém o valor da área de seção transversal de uma barra, que será alterado de forma aleatória.

Figura 5.4: Mutação.

Função Objetivo A função objetivo é dada pelo somatório da área da seção transversal de cada barra multiplicada pelo comprimento da mesma e pela massa específica do material, como mostrado na Equação 5.1: n

f o = ∑ (ai li ρi ) i=1

(5.1)

5.1 Algoritmo Evolutivo Híbrido

42

onde i é um barra da treliça, n é a quantidade de barras, ai é a área da seção transversal, li é o comprimento da barra, e ρi é a massa específica do material. Função de Avaliação Para a função de avaliação é utilizada a função objetivo mostrada no tópico anterior. Para avaliar os indivíduos, compara-se o resultado encontrado pela Equação 5.1 com o peso do melhor indivíduo atual. Caso seja menor, o peso é substituído. Também é verificada a factibilidade da solução, ou seja, se as restrições foram respeitadas. Caso não seja válida, é realizada mutação forçada até garantir que a solução seja viável. Após realizar a avaliação, substitui a pior solução da população pela melhor encontrada.

Descida Randômica Esse método de busca local é aplicado após a geração inicial. Para refinar os indivíduos, primeiro é gerada uma nova população de vizinhança com N indivíduos factíveis. Depois é calculada a função de avaliação e verificado se há indivíduos melhores que a população inicial. Caso não exista, N/2 indivíduos da população de vizinhança são removidos aleatoriamente e novos cromossomos factíveis são gerados até completar a população. Essa técnica é executada até que tenha encontrado uma população melhor que a inicial e que o número máximo de execuções tenha atingindo o limite que é de 100 iterações.

Metaheurística VNS Aplica-se a metaheurística VNS para refinar a solução inicial. Seleciona-se um indivíduo aleatoriamente da população e aplica-se o método Descida Randômica até melhorar ou atingir o número máximo de iterações. Caso encontre uma solução melhor, a pior solução da população é substituída pela melhor.

Função de Seleção A nova população é composta pela seleção dos N/2 melhores indivíduos da população atual por meio da técnica de Elitismo. Esse método pode aumentar o desempenho do AG, pois previne a perda da melhor solução já encontrada.

5.1 Algoritmo Evolutivo Híbrido

5.1.2

43

Algoritmo Evolutivo Híbrido 02

O Algoritmo Evolutivo Híbrido proposto baseia-se na utilização de um Algoritmo Genético com a busca local Descida Randômica ou a metaheurística VNS aplicada após a evolução dos indivíduos com a finalidade de encontrar melhores resultados para problema com coordenadas nodais móveis. A técnica de hibridização permite o uso de heurísticas ao conjunto de operadores genéticos e possibilita encontrar resultados melhores que os obtidos como a utilização isolada de uma técnica. O Algoritmo 6 mostra o pseudocódigo do Algoritmo Evolutivo Híbrido 02. Onde, N é a quantidade de indivíduos, γ e δ é um número gerado de forma aleatória entre 0 e 1, para realizar crossover e mutação, respectivamente. Algoritmo AEH(); 1 Gera uma população inicial; 2 Avalia a população inicial; 3 enquanto (Critério de parada não for satisfeito) faça{Número máximo de gerações} 4 enquanto (numFilhos < N/2) faça 5 Seleciona 2 pais aleatoriamente 6 se (γ < probabilidadeCrossover) então 7 Seleciona ponto de corte; 8 Gera 2 filhos; {Crossover} 9 fim se 10 fim enquanto 11 para ind de 0 para N faça 12 se (δ < probabilidadeMutação) então 13 Realiza mutação; 14 fim se 15 Avalia indivíduo; 16 enquanto (iter < iterMax) faça 17 Aplica o método de refinamento em um indivíduo; {VNS (AEH02-VNS) ou Descida Randômica (AEH02-DR)} 18 Avalia indivíduo; 19 fim enquanto 20 fim para 21 Seleção (Elitismo: 2 melhores; Roleta Russa: (N/2)-2 ); 22 Remove os não selecionados; 23 fim enquanto 24 Apresenta os resultados; fim Algoritmo 6: Pseudocódigo do AEH02. O AEH02 é implementado de três maneiras distintas. A primeira é sem utilização de técnicas de refinamento (AE02), assim da linha 16 à 19, do Algoritmo 6, não são

5.1 Algoritmo Evolutivo Híbrido

44

consideradas. A segunda e terceira pode usar Descida Randômica (AEH02-DR) ou Pesquisa em Vizinhança Variável (AEH02-VNS), respectivamente. Desse modo, é possível encontrar melhores soluções com um método de busca local. É importante que as estruturas de vizinhanças sejam bem definidas para o problema abordado. Esse algoritmo é implementado para minimizar o peso estrutural e realizar a otimização de forma da treliça. Isso é possível devido à treliça possuir coordenadas nodais móveis. Durante a pesquisa foi observado que o algoritmo implementado inicialmente poderia melhorar o desempenho com modificações na estrutura do AG, por exemplo, nos operadores genéticos. Sendo assim, a estrutura do AEH02 foi modificada em relação ao AEH01 para melhorar o custo computacional e principalmente para permitir que todas as restrições impostas pelo projeto fossem respeitadas. Foram implementados novos modos para realização do crossover e mutação, seleção dos novos indivíduos e métodos de refinamento. Nas técnicas de busca local foram criadas estruturas de vizinhanças diferentes a fim de obterem melhores resultados. Detalhes dessas técnicas são mostrados nos tópicos Descida Randômica e Metaheurística VNS. Além disso, foi criada uma função de avaliação, que aplicasse penalidades caso existisse barras ou nós que violasse as restrições. Essa nova estrutura é descrita a seguir.

Representação do cromossomo O cromossomo de uma estrutura treliçada com N barras é representado por um vetor com N posições. Esse cromossomo é dividido em duas partes, grupos de barras (parte A) e coordenadas nodais (parte B). A primeira parte é representada pelos grupos de barras e a segunda pelas coordenadas nodais dos nós móveis (3, 5, 7 e 9).

Figura 5.5: Representação do cromossomo.

5.1 Algoritmo Evolutivo Híbrido

45

Critérios de parada O critério de parada é definido quando o número máximo de gerações é atingido.

Geração inicial da população A população inicial é gerada com N/2 indivíduos, sendo valores aleatórios para os grupos de barras e coordenadas nodais. Esses dados são gerados respeitando os limites impostos. Os outros N/2 indivíduos serão gerados após o crossover.

Crossover Para realizar o crossover, selecionam-se dois indivíduos pais da geração inicial, aplica-se o cruzamento para gerar dois filhos, com a probabilidade de 60%. O crossover pode ser realizado de duas formas: Clássico ou Adicional. No primeiro caso seleciona um ponto de corte para parte A e outro para parte B. O conteúdo da primeira parte do grupo de barras e das coordenadas nodais do pai 1 vai para o filho 1 e a segunda parte para o filho 2. Depois a parte A do pai 2 vai para o filho 2 e a outra parte para o filho 1, conforme mostrado na Figura 5.6. O crossover de dois pontos é aplicado apenas na parte B do cromossomo, ou seja, na parte de coordenadas, pois em grupos contém apenas 4 genes.

Figura 5.6: Crossover.

5.1 Algoritmo Evolutivo Híbrido

46

Mutação A mutação é efetuada alterando-se o valor de um gene de um indivíduo sorteado aleatoriamente com probabilidade igual a 10%. Caso ocorra mutação, seleciona-se aleatoriamente um dos grupos de barras e uma coordenada nodal para serem alterados de forma aleatória, como mostrado na Figura 5.7. Escolhida as duas posições, substitui-se o conteúdo pelo valor gerado.

Figura 5.7: Mutação.

Função Objetivo A função objetivo é dada pelo somatório da área da seção transversal de cada barra multiplicada pelo comprimento da mesma e pela massa específica, como mostrado na Equação 5.2: n

f o = ∑ (ai li ρi )

(5.2)

i=1

onde i é um barra da treliça, n é a quantidade de barras, ai é a área da seção transversal, li é o comprimento da barra, e ρi é a massa específica do material. Função de Avaliação A função objetivo é introduzida na função de avaliação, dada pela Equação 5.3, sendo obtido para cada indivíduo um valor de função de avaliação. f a = f o + αnBV + β nCV

(5.3)

onde f o retorna o peso da estrutura analisada, α e β são as penalidades aplicadas as barras que violam a tensão e aos nós que violam o deslocamento, respectivamente. nBV é o número de barras que violam a tensão, nCV é o número de coordenadas que violam o deslocamento. Assim, tem-se como função de avaliação a própria função objetivo e a soma das penalidades.

5.1 Algoritmo Evolutivo Híbrido

47

Os indivíduos que possuem barras ou nós que violam as restrições, não são factíveis. Para validar a treliça é utilizado o INSANE, que calcula os deslocamentos dos nós e as ações nas extremidades de cada barra, além de outras informações importantes para validação da solução. O primeiro é importante para quantificar o deslocamento violado. A ação na extremidade de cada barra é necessária para calcular a tensão por meio da Equação 5.4. σj =

Fj aj

(5.4)

onde σ j é a tensão, Fj é a força aplicada à barra ou ação na extremidade e a j é a área da seção transversal. Se a tensão for maior que a máxima permitida significa que a barra viola essa restrição. Quando o deslocamento e a tensão são violados é aplicada uma penalidade (com o valor de 10000) e a solução torna-se inviável. Essa não é descartada, pois poderá ser melhorada com a busca local. Para avaliar os indivíduos compara-se o resultado encontrado pela Equação 5.3 com o peso do melhor indivíduo atual. Caso seja menor, o peso é substituído. Após realizar a avaliação, aplicam-se as técnicas de busca local para refinar os indivíduos, avaliam novamente os indivíduos gerados e utilizam-se as técnicas de Elitismo e Roleta Russa para criar a nova população.

Descida Randômica Ao aplicar o método de busca local Descida Randômica, pode-se escolher aleatoriamente três tipos de movimentos. O Algoritmo 7 mostra o funcionamento dessa técnica. Na estrutura 1 é selecionado um dos 4 grupos de barras e modificado o valor da área da seção transversal das barras do grupo escolhido com a probabilidade de 50%. Esse novo valor é o resultado do acréscimo ou redução da área anterior em 2%. Na estrutura 2, seleciona-se uma coordenada e aumenta ou diminui em 4% o deslocamento do nó. A estrutura 3 é semelhante a 2, porém o deslocamento ocorre em 2%.

5.1 Algoritmo Evolutivo Híbrido

48

Algoritmo DescidaRandomica(Indivíduo indDescida); 1 Define os valores de acréscimo ou redução de área de seção transversal; 2 Define os valores de acréscimo ou redução para o deslocamento de coordenadas; 3 Seleciona uma estrutura de vizinhança; 4 se EstruturaSelecionada = 1 então 5 Seleciona grupo de barras que será modificado; 6 Aumenta ou diminui (com probabilidade de 50%) o valor 7 da área de seção transversal do indivíduo em 2%; 8 fim se 9 se EstruturaSelecionada = 2 então 10 Seleciona coordenada a ser alterada; 11 Aumenta ou diminui (com probabilidade de 50%) o valor 12 do deslocamento do nó selecionado do indivíduo em 4%; 13 fim se 14 se EstruturaSelecionada = 3 então 15 Seleciona coordenada a ser alterada; 16 Aumenta ou diminui (com probabilidade de 50%) o valor 17 do deslocamento do nó selecionado do indivíduo em 2%; 18 fim se 19 Retorna o indivíduo modificado; fim Algoritmo 7: Pseudocódigo do Método de Busca Local Descida Randômica. Metaheurística VNS Depois de verificar se há algum indivíduo melhor após a mutação e o crossover, aplica-se a metaheurística VNS para refinar a solução. Essa técnica de busca local é aplicada em todos os indivíduos da população. A solução inicial é o melhor indivíduo atual. Um vizinho é selecionado na população. Nesse é aplicada uma técnica de busca local, conhecida como Descida Randômica. Esse método é composto por três tipos de estruturas de vizinhança que são escolhidos aleatoriamente. A estrutura 1 aumenta ou diminui em 4% de unidades a área de seção transversal do grupo de barras escolhido. Já a segunda, incrementa ou decrementa em 2% de unidades o deslocamento (coordenada) de um nó. A última acrescenta ou reduz em 1% ou 2% de unidades o deslocamento, referente à distância entre os nós das extremidades da coordenada selecionada. Nas três estruturas há uma probabilidade de 50% para escolher entre aumentar ou diminuir o que foi selecionado.

5.1 Algoritmo Evolutivo Híbrido

49

Função de Seleção A função de seleção dos indivíduos na população para a nova geração seleciona N/2 indivíduos da população atual por meio das técnicas de Elitismo e Roleta Russa. A primeira define os dois melhores indivíduos para a população sobrevivente e os armazena nas primeiras posições. A última seleciona os demais indivíduos para compor a nova população, no qual os mais aptos possuem maior probabilidade de sobreviverem, sendo que todos, mesmos os menos aptos, têm chances de sobrevivência.

50

6

RESULTADOS COMPUTACIONAIS

Neste capítulo são apresentados os resultados computacionais encontrados para solução de problemas em otimização estrutural com a utilização dos algoritmos desenvolvidos. A aplicação dos métodos implementados foi realizada para tentar obter boas soluções aos problemas citados com treliças planas de 10 e 18 barras. O AEH01, mostrado na Seção 5.1.1, foi aplicado ao problema de otimização estrutural de treliças com 10 barras. O AEH02, Seção 5.1.2, foi utilizado para minimizar o peso e modificar a forma de uma estrutura treliçada com 18 barras. Os algoritmos possuem integração com o INSANE, descrito na Seção 4.2. Esse programa é importante para receber e enviar informações ao OtimoEstrutra a fim de garantir que as soluções encontradas sejam factíveis. Após cada geração é realizada uma análise com o software para que valores como ação da extremidade das barras, necessário para calcular a tensão, e deslocamentos dos nós possam ser utilizados para verificar se há nós ou barras que violam as restrições impostas pelo projeto. O INSANE também fornece o comprimento final de cada barra da treliça, calculado no INSANE a partir dos valores das coordenadas nodais recebidas do OtimoEstrutura. O desenho topológico pode ser visualizado no software de análise estrutural com a importação de um arquivo .XML, que é gerado a cada melhora da solução. Nas seções seguintes são descritos os problemas e mostrados os resultados encontrados com a utilização dos algoritmos implementados, exemplificados no Capítulo 5.

6.1

Otimização Estrutural de Treliças com 10 Barras

O AEH01, descrito na Seção 5.1.1, foi aplicado ao problema de otimização estrutural de treliças com 10 barras. Esse é descrito na Seção seguinte. A Seção 6.1.2

6.1 Otimização Estrutural de Treliças com 10 Barras

51

apresenta os resultados encontrados com a utilização do algoritmo. Foram realizados testes com o AEH01 com Descida Randômica (AEH01-DR), VNS (AEH01-VNS) e sem técnica de refinamento (AE01). As soluções obtidas são comparadas com as encontradas na literatura.

6.1.1

Descrição do problema

O problema de otimização estrutural estudado é aplicado à estrutura de treliças planas de 10 barras. O objetivo é obter as dimensões mínimas suficientes para as áreas de seção transversal de cada barra, obedecendo às restrições impostas pelo projeto. A Figura 6.1 mostra a configuração estrutural da treliça de 10 barras.

Figura 6.1: Topologia da estrutura com 10 barras. Fonte: Yokota, Tagughi e Gen (1998)

As restrições de projeto são descritas na Tabela 6.1. As variáveis citadas nessa tabela são descritas a seguir: • ai corresponde ao intervalo permitido de valores para a área da seção transversal de cada barra envolvida no processo. Por exemplo, a área da seção transversal da barra 1 pode variar entre 11, 5 e 12, 5 in; • Os coeficientes são restrições que deverão ser consideradas durante o processo de pesquisa, de maneira que cada estrutura gerada durante o processo deverá obedecer a todos os requisitos estruturais citados, caso contrário deverá ser descartada pois é infactível para o problema; • E é o módulo de elasticidade longitudinal do material; • σ é a tensão máxima admissível;

6.1 Otimização Estrutural de Treliças com 10 Barras

52

• li corresponde ao comprimento de cada barra i; • ρ corresponde à massa específica do material; • v6 corresponde ao deslocamento vertical do nó 6, que deverá ser menor ou igual a 5 in. Note que, no caso do deslocamento, o nó 6 é citado mas a verificação é realizada em todos os nós. O nó 6 é citado em particular na tabela devido a sua posição na configuração estrutural do problema, de maneira que ele é o nó que mais se deslocará ao aplicar o peso P. Tabela 6.1: Restrições de projeto e valores de coeficientes. Fonte: Yokota, Tagughi e Gen (1998) 11, 5 in2 ≤ a1 ≤ 12, 5 in2 0, 1 in2 ≤ a3 ≤ 1, 0 in2 5, 5 in2 ≤ a5 ≤ 6, 0 in2 8, 0 in2 ≤ a7 ≤ 9, 0 in2 0, 1 in2 ≤ a9 ≤ 1, 0 in2 E = 107 psi | σ | ≤ 25000 (25 ksi) l1−4,9,10 = 360 √ in l5−8 = 360 2 in

6.1.2

8, 0 in2 ≤ a2 ≤ 9, 0 in2 5, 5 in2 ≤ a4 ≤ 6, 5 in2 8, 0 in2 ≤ a6 ≤ 9, 0 in2 0, 1 in2 ≤ a8 ≤ 1, 0 in2 0, 1 in2 ≤ a10 ≤ 1, 0 in2 ρ = 0, 1 lb/in3 | v6 | ≤ 5, 0 in P = 105 lb

Resultados

Nesta seção, o algoritmo AEH01 é comparado com os resultados encontrados na literatura por Yokota, Tagughi e Gen (1998), Rozvany e Zhou (1991) e Pereira (2007). O primeiro autor implementou três algoritmos baseados em AG: DOC-FSD, Dual e DCOC, para o problema de 10 barras. O segundo, cujo valor de referência é considerado para essa estrutura, utiliza técnicas baseadas em critérios de otimalidade. O último desenvolveu heurísticas computacionais, entre elas Algoritmo Genético. Os testes foram executados em um computador com processador Core 2 Duo E6550, 2.33GHz, 2GB RAM e sistema operacional Windows Vista. Os parâmetros de calibração do algoritmo proposto foram definidos da seguinte forma: população de 20 indivíduos, número máximo de gerações 6000, e as probabilidades de ocorrer mutação e crossover foram, respectivamente, de 30% e 60%. O número máximo de iterações para o método de busca local foi definido em quando houver melhora executa. Para o VNS ficou determinado para executar três vezes.

6.1 Otimização Estrutural de Treliças com 10 Barras

53

A Tabela 6.2 mostra os melhores resultados a cada execução e geração que foram encontrados com o AE01 (sem refinamento). Pode-se observar que o peso médio, 2140, 25 lb, é pior que o de referência apresentado na Tabela 6.5. O erro relativo para esse valor é de 0, 054%. Tabela 6.2: Melhores pesos a cada execução do AE01. Execução Peso (lb) Geração 1 2139,96042 2596 2 2140,37819 1280 3 2139,98679 1183 4 2140,86901 5601 5 2140,01263 5324 6 2140,42052 5155 7 2139,92927 3603 8 2140,02787 4057 9 2140,767 5942 10 2140,1319 5753 Média 2140,25 4049 Desvio Padrão 0,345057629 A Tabela 6.3 mostra os melhores resultados obtidos a cada execução e geração que foram encontrados para o AEH01-DR. Pode-se observar que o peso médio, 2145, 15 lb, é pior que o de referência apresentado na Tabela 6.5. O erro relativo para esse valor é de 0, 283%. Tabela 6.3: Melhores pesos a cada execução do AEH01-DR. Execução Peso (lb) Geração 1 2147,37086 3013 2 2141,48089 5186 3 2145,39665 5989 4 2146,56019 5268 5 2145,83693 4331 6 2145,51132 5030 7 2146,20557 1260 8 2143,29691 3267 9 2146,53887 5983 10 2143,34961 2216 Média 2145,15 4154 Desvio Padrão 1,848867235 A Tabela 6.4 mostra os melhores resultados a cada execução e geração que foram obtidos com o uso do AEH01-VNS. Observa-se que o peso médio é pior que o de referência apresentado na Tabela 6.5. O erro relativo para esse valor é de 0, 326%.

6.1 Otimização Estrutural de Treliças com 10 Barras

54

Tabela 6.4: Melhores pesos a cada execução do AEH01-VNS. Execução Peso (lb) Geração 1 2146,13782 2210 2 2148,07856 4258 3 2143,90795 850 4 2148,06859 4592 5 2146,96896 3535 6 2146,23434 5575 7 2146,51585 3500 8 2142,32183 142 9 2145,25769 3245 10 2147,21938 1408 Média 2146,07 2931,5 Desvio Padrão 1,818770715

A Tabela 6.5 mostra os melhores pesos encontrados para o problema de 10 barras com a utilização do algoritmo implementado comparado com os da literatura.

Tabela 6.5: Melhores pesos obtidos com AEH01 em dez execuções para o problema de treliça com 10 barras. Algoritmo Utilizado Peso (lb) Erro Relativo (%) AE01 2139,92927 0,039 AEH01-DR 2141,48089 0,111 AEH01-VNS 2142,32183 0,150 AG 1 2139,51531 0,019 VNS 1 2144,91843 0,271 1 GRASP com VNS 2144,07353 0,232 1 Recozimento Simulado 2139,85444 0,035 Busca Tabu 1 2139,18689 0,004 1 Colônia de Formiga 2139,5949 0,022 2 DOC-FSD 2139,198 0,004 2 Dual 2139,10498 0,000 2 DCOC 2139,10498 0,000 Algoritmo de Referência 3 2139,10498

A Tabela 6.6 mostra as soluções encontradas para o problema de 10 barras com a utilização dos algoritmos implementados comparadas com as da literatura. Cada posição do vetor representa a área de seção transversal de cada barra. 1 Pereira

(2007) Tagughi e Gen (1998) 3 Rozvany e Zhou (1991) 2 Yokota,

6.1 Otimização Estrutural de Treliças com 10 Barras

55

Tabela 6.6: Melhores soluções obtidas em dez execuções para o problema de treliça com 10 barras. Algoritmo Utilizado Melhor Solução Encontrada (in) [A1, A2, A3, A4, A5, A6, A7, A8, A9, A10] AE01 [12,39988; 8,68375; 0,10157; 6,13367; 5,56468; 8,41068; 8,4935; 0,10214; 0,10097; 0,10223] AEH01-DR

[11,89742; 8,68335; 0,10686; 6,09833; 5,56753; 8,67943; 8,59535; 0,13217; 0,10316; 0,10544]

AEH01-VNS

[12,42086; 8,98894; 0,11333; 5,75664; 5,56176; 8,35271; 8,60899; 0,10927; 0,11147; 0,10999]

AG 1

[12,184564; 8,765164; 0,1; 6,011111; 5,567187; 8,404665; 8,675727; 0,1; 0,1; 0,1]

VNS 1

GRASP com VNS 1

Recozimento Simulado 1

Busca Tabu 1

[12,37530; 8,61023; 0,1; 6,25468; 5,56154; 8,21205; 8,71207; 0,15450; 0,12264; 0,1] [12,16320; 8,28717; 0,1; 6,11155; 5,53106; 8,88064; 8,53061; 0,15408; 0,11889; 0,11336] [12,21668; 8,737761; 0,1; 6,21331; 5,56808; 8,47098; 8,4574; 0,11148; 0,1; 0,1] [12,125599; 8,80142; 0,1; 5,975283; 5,561755; 8,599056; 8,521716; 0,1; 0,1; 0,1]

Colônia de Formiga 1

[12,04866; 8,903371; 0,10296; 6,01019; 5,56551; 8,64850; 8,43207; 0,1; 0,1; 0,1]

DOC-FSD 2

[12,126576; 8,827450; 0,1; 6,046585; 5,564322; 8,497882; 8,551163; 0,1; 0,1; 0,1]

Dual 2

[12,161174; 8,707029; 0,1; 6,040580; 5,560165; 8,573640; 8,542670; 0,1; 0,1; 0,1]

DCOC 2

[12,161174; 8,707029; 0,1; 6,040580; 5,560165; 8,573640; 8,542670; 0,1; 0,1; 0,1]

Algoritmo de Referência 3

[12,161174; 8,707029; 0,1; 6,040580; 5,560165; 8,573640; 8,542670; 0,1; 0,1; 0,1]

6.2 Otimização Estrutural de Treliças com 18 Barras

56

O algoritmo desenvolvido obteve um bom desempenho, porém não encontrou resultados melhores que o da literatura. Isso pode ser justificado pelo motivo do algoritmo de referência ser baseado em métodos de programação matemática, como métodos de critérios de otimalidade discretizado (Métodos DCOC e Dual), e o algoritmo implementado nesta pesquisa utilizar heurísticas computacionais.

6.2

Otimização Estrutural de Treliças com 18 Barras

O AEH02, descrito na Seção 5.1.2, foi aplicado ao problema de otimização estrutural de treliças com 18 barras, que é descrito na Seção seguinte. A Seção 6.2.2 apresenta os resultados encontrados com a utilização do algoritmo. Foram realizados testes com o AEH02 com Descida Randômica (AEH02-DR), VNS (AEH02-VNS) e sem técnica de refinamento (AE02). As soluções obtidas são comparadas com as encontradas na literatura.

6.2.1

Descrição do problema

Para este problema, os algoritmos devem obter as dimensões mínimas suficientes para a área da seção transversal e para o comprimento de cada barra, obedecendo às restrições impostas pelo projeto. Esse problema possui algumas coordenadas nodais móveis, assim a forma da estrutura também pode ser modificada.

Figura 6.2: Topologia inicial da estrutura com 18 barras. Fonte: Fawaz, Xu e Behdinan (2005) .

A Figura 6.2 mostra a configuração estrutural da treliça de 18 barras, retirada de Fawaz, Xu e Behdinan (2005). O problema de otimização tratado tem como variáveis a área da seção transversal e comprimento das barras (obtido por meio das coorde-

6.2 Otimização Estrutural de Treliças com 18 Barras

57

nadas dos nós) da estrutura. Desse modo, é possível que a dimensão dos elementos estruturais e a forma da treliça possam ser modificados durante o processo de otimização. Nessa estrutura, os nós 1, 2, 4, 6 e 8 são fixos, ou seja, não podem ter as coordenadas modificadas. A cada um desses nós é aplicada uma força externa correspondente a 20000 lb. Dessa maneira, as seguintes restrições devem ser consideradas: a) Tensão máxima menor ou igual a 20, 089 ksi (| σ | ≤ 20089 psi); b) As 18 barras são divididas em quatro grupos: o 1o grupo é composto das barras 1, 4, 8, 12 e 16. O 2o grupo é composto pelas barras 2, 6, 10, 14 e 18. O 3o grupo é composto pelas barras 3, 7, 11 e 15. E o 4o grupo é composto pelas barras 5, 9, 13 e 17. As barras que pertencem a um mesmo grupo devem possuir áreas de seção transversal iguais; c) Apenas os nós 3, 5, 7 e 9 podem ter suas coordenadas modificadas; d) As propriedades do material utilizado são: módulo de elasticidade (E) igual a 107 psi e a densidade é igual a 0, 1 lb/in3 ; e) Os valores das áreas de seção transversal podem variar de 0, 2 in2 a 30 in2 . f) O deslocamento máximo é de 20, 92in. Em Pereira (2007), o problema apresentado procura minimizar o peso estrutural, obedecendo ao conjunto de restrições impostas pelo projeto, com exceção da restrição c), que determina o modo que as coordenadas são modificadas. Já nesta pesquisa, além do peso é realizada também a otimização de forma e todas as restrições são respeitadas. Para encontrar o melhor peso, tem-se então a área da seção transversal e o comprimento das barras. Esse último é obtido por meio do software de análise estrutural, o INSANE. O OtimoEstrutura informa ao programa as áreas e as coordenadas nodais fixas e móveis, para que os comprimentos das barras possam ser calculados e retornados ao software de otimização. Os resultados encontrados são descritos a seguir.

6.2 Otimização Estrutural de Treliças com 18 Barras

6.2.2

58

Resultados

Os resultados do AEH são comparados com os encontrados na literatura por Fawaz, Xu e Behdinan (2005) e Pereira (2007). O primeiro autor implementou um algoritmo evolutivo híbrido para o problema de 18 barras. O segundo desenvolveu algumas heurísticas computacionais, entre elas Algoritmo Genético, para o mesmo problema. Porém todas as coordenadas nodais eram fixas sendo otimizada apenas a área da seção transversal para minimizar o peso da estrutura treliçada. Além disso, Pereira (2007) teve como solução inicial a estrutura otimizada pela outro autor, com exceção da área da seção transversal, ou seja, todas as coordenadas fixas a partir do melhor resultado do primeiro autor. Os testes foram executados em um computador com processador Core 2 Duo E6550, 2.33GHz, 2GB RAM. O sistema operacional foi o Windows Vista. Utilizou-se a versão 1.6_015 do Kit de Desenvolvimento Java (JDK), linguagem em que foram desenvolvidos os algoritmos. Os parâmetros de calibração do algoritmo proposto foram definidos da seguinte maneira: população de 20 indivíduos, número máximo de gerações 1500, e as probabilidades de ocorrer mutação e crossover foram respectivamente de 10% e 60%. Para o AEH02-VNS foi determinado o número máximo de cinco execuções para o método de refinamento. O AEH02-DR executa a busca local até que a solução não seja mais melhorada. Foram realizadas 10 execuções com 1500 gerações para os três tipos de algoritmos.

Tabela 6.7: Melhores pesos a cada execução do AE02. Execução Peso (lb) Geração 01 4100,27 1377 02 3893,79 1336 03 4246,31 889 04 3697,22 1202 05 4109,23 1109 06 3713,52 1304 07 3688,91 1445 08 4341,9 1480 09 3824,41 914 10 3987,33 1246 Média 3960,29 1230,2 Desvio Padrão 234,8939

6.2 Otimização Estrutural de Treliças com 18 Barras

59

A Tabela 6.7 mostra os melhores resultados obtidos a cada execução e geração que foram encontrados com a utilização do algoritmo sem heuristica de refinamento, o AE02. Pode-se observar que o peso médio, 3960, 29 lb, é pior que o de referência apresentado na Tabela 6.10. O erro relativo para esse valor é de 2, 054%.

Tabela 6.8: Melhores pesos a cada execução do AEH02-DR. Execução Peso (lb) Geração 01 3895,48 455 02 3886,57 1491 03 3929,43 1462 04 3536,57 1198 05 3360,58 807 06 4091,61 1462 07 4075,74 238 08 4059,57 1036 09 3869,35 1408 10 3846,98 1407 Média 3855,19 944,2 Desvio Padrão 235,9032

A Tabela 6.8 mostra os melhores resultados a cada execução e geração que foram encontrados com o uso do AEH02-DR. Pode-se observar que o peso médio, 3855, 19 lb, é melhor que o de referência apresentado na Tabela 6.10. O erro relativo para esse valor é de −0, 655%. Entre os outros algoritmos implementados, esse foi o que encontrou o melhor resultado.

Tabela 6.9: Melhores pesos a cada execução do AEH02-VNS. Execução Peso (lb) Geração 01 3385,06 566 02 3569,03 815 03 3583,59 795 04 4277,55 1294 05 4013,44 1298 06 3982,44 1380 07 3666,50 872 08 3975,08 1415 09 3614,86 746 10 3863,80 261 Média 3793,14 944,2 Desvio Padrão 271,9481

6.2 Otimização Estrutural de Treliças com 18 Barras

60

A Tabela 6.9 mostra os melhores resultados a cada execução e geração que foram obtidos com a utilização do algoritmo evolucionário híbrido com Pesquisa em Vizinhança Variável. Pode-se observar que o peso médio é bem melhor que o de referência apresentado na Tabela 6.10. O erro relativo para esse valor é de −2, 254%.

Tabela 6.10: Melhores pesos obtidos com o AEH02 em dez execuções para o problema de treliça com 18 barras. Algoritmo Utilizado Peso (lb) Erro Relativo (%) AE02 3688,91 -4,940 AEH02-DR 3360,58 -13,401 AEH02-VNS 3385,06 -12,770 2 AEH 3899,22 0,479 1 AG 3884,69 -0,373 1 VNS 3943,81 1,144 GRASP com VNS 1 3971,72 1,859 1 Recozimento Simulado 3951,36 1,337 1 Busca Tabu 3880,60 0,0 1 Colônia de Formiga (Ref.) 3880,60

A Tabela 6.10 mostra os melhores pesos encontrados para o problema de 18 barras com a utilização do AEH02 comparados com os da literatura.

Tabela 6.11: Tensão máxima e deslocamento máximo da melhor solução obtida para o problema de treliça com 18 barras. Algoritmo Utilizado Tensão máxima (psi) Deslocamento máximo (in) AE02 Barra 16: 19919,18 Nó 2: 20,58 AEH02-RD Barra 16: 19964,53 Nó 2: 14,47 AEH02-VNS Barra 16: 19997,56 Nó 2: 15,64 AEH 2 Barra 17: 20087,56 Nó 1: 20,91 AG 1 Barra 17: 20087,56 Nó 1: 21,00 1 VNS Barra 16: 19905,85 Nó 1: 20,86 1 GRASP com VNS Barra 18: 20058,29 Nó 1: 20,96 Recozimento Simulado 1 Barra 18: 19874,63 Nó 1: 20,71 1 Busca Tabu Barra 17: 20087,56 Nó 1: 20,99 1 Colônia de Formiga (Ref.) Barra 17: 20087,56 Nó 1: 20,99

A Tabela 6.11 mostra os valores encontrados de tensão e deslocamento máximos das melhores soluções obtidas de cada algoritmo. 1 Fawaz, 2 Pereira

Xu e Behdinan (2005) (2007)

6.2 Otimização Estrutural de Treliças com 18 Barras

61

Tabela 6.12: Melhores soluções obtidas com o AEH02 em dez execuções para o problema de treliça com 18 barras. Algoritmo Utilizado Melhor Solução Encontrada (in) [A1, A2, A3, A5, X3, Y3, X5, Y5, X7, Y7, X9, Y9] [9,66; 12,47; 3,32; 6,0; 863,31; 171,11; AE02 706,87; 136,59; 537,77; 78,0; 315,45; 25,27] AEH02-DR

AEH02-VNS

[6,14; 8,65; 3,26; 7,18; 983,62; 150,12; 875,4; 101,55; 693,98; 51,9; 443,9; 0,29] [5,43; 9,96; 3,28; 7,04; 979,6; 167,81; 853,55; 121,77; 678,71; 66,94; 481,15; 2,41]

AEH 2

[11,43; 15,21; 1,92; 4,38; 918,9; 198,9; 625,8; 139,8; 379,6; 75;2; 282,5; 45,6]

AG 1

[11,39; 15,13; 1,93; 4,38; 918,9; 198,9; 625,8; 139,8; 379,6; 75;2; 282,5; 45,6]

VNS 1

[11,49; 15,28; 2,28; 4,42; 918,9; 198,9; 625,8; 139,8; 379,6; 75;2; 282,5; 45,6]

GRASP com VNS 1

[11,39; 15,13; 1,93; 4,38; 918,9; 198,9; 625,8; 139,8; 379,6; 75;2; 282,5; 45,6]

Recozimento Simulado 1

[11,6; 15,29; 2,05; 4,51; 918,9; 198,9; 625,8; 139,8; 379,6; 75;2; 282,5; 45,6]

Busca Tabu 1

[11,39; 15,13; 1,87; 4,38; 918,9; 198,9; 625,8; 139,8; 379,6; 75;2; 282,5; 45,6]

Colônia de Formiga (Referência) 1

[11,39; 15,13; 1,87; 4,38; 918,9; 198,9; 625,8; 139,8; 379,6; 75;2; 282,5; 45,6]

A Tabela 6.12 mostra os melhores valores obtidos para o problema de 18 barras com a utilização dos algoritmos AEH02 e os encontrados na literatura. As quatro primeiras posições do vetor representam os valores para os grupos de barras. O restante são as coordenadas nodais dos nós 3, 5, 7 e 9. Foram realizadas dez execuções com 100 gerações. As formas da treliça com 18 barras encontradas para os experimentos (AE02, AEH02-DR, AEH02-VNS) são mostradas nas Figuras 6.3, 6.4, 6.5, respectivamente. A Figura 6.6 mostra a forma estrutural da melhor solução de referência.

6.2 Otimização Estrutural de Treliças com 18 Barras

62

Figura 6.3: Topologia do melhor resultado encontrado com AE02 para estrutura com 18 barras.

Figura 6.4: Topologia do melhor resultado encontrado com AEH02-DR para estrutura com 18 barras.

Figura 6.5: Topologia do melhor resultado encontrado com AEH02-VNS para estrutura com 18 barras.

Figura 6.6: Topologia da estrutura com 18 barras (Referência).

6.2 Otimização Estrutural de Treliças com 18 Barras

63

Os algoritmos desenvolvidos obtiveram um desempenho melhor que os da literatura, pois encontraram melhores resultados com mesmo número de gerações e menor tempo. O próximo Capítulo mostra a análise dos resultados apresentados nessa Seção.

64

7

ANÁLISE DOS RESULTADOS COMPUTACIONAIS

Neste capítulo é apresentada uma análise dos resultados computacionais, descritos no capítulo anterior, obtidos com a utilização do AEH. O desempenho, a eficiência e a robustez dos algoritmos desenvolvidos também são relatados nas próximas seções. Os algoritmos AE (sem refinamento), AEH com Descida Randômica (AEH-DR), AEH com VNS (AEH-VNS) são comparados para os problemas de otimização estrutural de treliça com 10 e 18 barras.

7.1

Otimização Estrutural de Treliças com 10 Barras

A solução para o problema de otimização estrutural de treliça com 10 barras busca as dimensões mínimas suficientes para as áreas da seção transversal de cada barra. Para isso foi utilizado o algoritmo descrito na Seção 5.1.1. O problema foi mostrado na Seção 6.1.1 e os resultados apresentados em 6.1.2. Como visto, não foram encontradas boas soluções que serão analisadas a seguir.

7.1.1

Análises dos resultados

O critério de parada definindo foi o número máximo de gerações igual à 6000 iterações. A Figura 7.1 mostra o gráfico de desempenho do AE01 (sem técnicas de refinamento) a cada execução. A melhor solução foi encontrada na geração de número 3603. A média dos melhores resultados é de 2140, 25 lb para o problema. O desvio padrão é de 0, 345057629 lb.

7.1 Otimização Estrutural de Treliças com 10 Barras

65

Figura 7.1: Gráfico de convergência das execuções do AE01.

No gráfico de execução do AEH01-DR, mostrado na Figura 7.2, pode-se observar o desempenho do algoritmo a cada geração.

Figura 7.2: Gráfico de convergência das execuções do AEH01-DR.

A Figura 7.3 mostra o gráfico de execução do AEH01-VNS.

7.1 Otimização Estrutural de Treliças com 10 Barras

66

Figura 7.3: Gráfico de convergência das execuções do AEH01-VNS.

O gráfico das melhores soluções de cada execução dos algoritmos AE01, AEH01DR, AEH01-VNS é apresentado na Figura 7.4.

Figura 7.4: Gráfico com melhores resultados a cada execução do AEH01-VNS.

Pode-se observar, por meio dos gráficos, que quando se utiliza o método VNS para refinar as soluções a convergência dos resultados é mais rápida que quando o método de Descida Randômica é usado. Porém, a melhor solução foi obtida com a utilização do Algoritmo Evolutivo isolado, ou seja, sem a técnica de hibridização.

7.2 Otimização Estrutural de Treliças com 18 Barras

67

Durante os testes observou-se que o ajuste de parâmetros, tais como quantidade de iterações para a busca local, taxa de mutação e crossover, estruturas de vizinhanças são fundamentais para a boa convergência.

7.2

Otimização Estrutural de Treliças com 18 Barras

A solução para o problema de otimização estrutural de treliça com 18 barras busca as dimensões mínimas suficientes para as áreas de seção transversal de cada barra e melhorar a forma da treliça por meio das coordenadas nodais móveis. Para tanto, foi utilizado o algoritmo descrito na Seção 5.1.2 a fim de encontrar resultados para esse problema. Esse problema foi descrito na Seção 6.2.1 e os resultados apresentados em 6.2.2. Como visto, foram encontradas boas soluções que serão analisadas a seguir.

7.2.1

Análises dos resultados

Para o critério de parada do algoritmo foi definindo o número máximo de gerações em 1500. A Figura 7.5 mostra gráfico de execução do AE02 (sem técnicas de refinamento) a cada geração.

Figura 7.5: Gráfico de convergência das execuções do AE02.

7.2 Otimização Estrutural de Treliças com 18 Barras

68

Como pode-se observar, a melhor solução foi encontrada com 566 gerações. A média dos melhores resultados é de 3793, 14 lb. O desvio padrão é de 271, 9481 lb. O gráfico de execução do AEH02-DR pode ser visualizado por meio da Figura 7.6. A melhor solução foi encontrada com 807 gerações. A média dos melhores resultados é de 3855, 19 lb para o problema. O desvio padrão é de 235, 9033 lb.

Figura 7.6: Gráfico de convergência das execuções do AEH02-DR.

A Figura 7.7 apresenta o gráfico de desempenho do AEH02-VNS a cada execução. E o gráfico com as melhores soluções de cada execução para o AE02, AEH02-DR, AEH02-VNS é mostrada na Figura 7.8. Pode-se observar, por meio dos gráficos, que quando utiliza-se o método VNS para refinar as soluções a convergência para melhores resultados é mais rápida que quando se usa Descida Randômica. Porém, com a técnica DR foi obtido o melhor resultado. Durante os testes pode-se observar que o ajuste de parâmetros, como quantidade de iterações para busca local, taxa de aumento ou redução de áreas ou coordenadas, taxa de mutação, estruturas de vizinhanças são fundamentais para a boa convergência. O uso da heurística de refinamento após a evolução da população obteve um desempenho melhor que quando utilizado após a geração inicial. Dessa maneira, boas soluções podem ser encontradas mais rapidamente.

7.2 Otimização Estrutural de Treliças com 18 Barras

Figura 7.7: Gráfico de convergência das execuções do AEH02-VNS.

Figura 7.8: Gráfico com melhores resultados a cada execução do AEH02.

69

70

8

CONCLUSÃO

Esta pesquisa teve como principal objetivo desenvolver um algoritmo evolutivo híbrido. A finalidade de encontrar boas soluções para o problema de otimização estrutural de treliças planas com coordenadas nodais fixas e móveis foi atingida. Para solução ótima foi considerado o menor peso da treliça obtido por meio da área da seção transversal de cada barra para os problemas. Foram implementados dois tipos de algoritmos evolutivos híbridos. Os dois foram desenvolvidos com base nos algoritmos genéticos e utilizaram heurísticas de refinamento para tentar obter melhores resultados. No primeiro caso, a busca local foi aplicada após a geração inicial da população e utilizado em problemas de treliças com nós fixos (treliça com 10 barras). Já no segundo, a técnica de refinamento foi aplicada após a evolução de cada geração nos problemas de treliças com coordenadas nodais móveis (treliça com 18 barras). O AEH01 foi aplicado ao problema de 10 barras. Esse não obteve bons resultados. Provavelmente isto se deve ao fato das estruturas de vizinhanças não terem sido bem definidas. Além disso, o algoritmo de referência foi baseado em programação matemática. O AEH02 foi aplicado ao problema de 18 barras. Esse algoritmo sofreu modificações bem diferenciadas em relação ao implementado inicialmente, o AEH01. Essas alterações foram necessárias pelo fato do problema possuir coordenadas nodais móveis, e consequentemente, os comprimentos das barras não serem mais fixos, como no problema anterior. A partir daí tem-se duas variáveis, a área de seção transversal e o comprimento das barras, que é obtido por meio das coordenadas nodais. Para calcular o comprimento das barras foi necessário utilizar o INSANE. A comunicação entre o software de otimização e o programa de análise estrutural poderia comprometer o desempenho e a eficiência do algoritmo. Assim, observou-se a necessidade de desenvolver uma maneira diferente para realizar crossover e muta-

8 CONCLUSÃO

71

ção, calcular a função objetivo, avaliar e selecionar os indivíduos. Após a mudança, a legibilidade do código-fonte ficou mais clara e o desempenho do algoritmo foi melhorado drasticamente. No AEH01, o desempenho era comprometido devido à realização de uma mutação forçada nos indivíduos, que o tornava factível por meio da alteração de um gene no cromossomo. Essa mutação sempre ocorria em todos os indivíduos não factíveis que eram gerados na população inicial ou após aplicar qualquer um dos operadores genéticos. O processo era realizado até o indivíduo ser válido, ou seja, que as restrições do projeto sejam respeitadas. Esse problema foi solucionado, no AEH02, com a idéia de aplicar penalidades na função de avaliação. Essa solução aumentou muito a eficiência do algoritmo. Durante as realizações dos testes com os algoritmos implementados, AEH01 e AEH02, foi observada a importância de criar estruturas de vizinhanças bem definidas nos método de refinamento para gerar boas soluções. Por exemplo, o deslocamento de um determinado nó não pode ser um valor alto, pois as barras se cruzam quando esse número é elevado. Então, foi definido taxas de deslocamento pequenas (1% ou 2%) para modificar um determinado nó. Ao comparar o AEH com as heurísticas da literatura foi possível verificar que a proposta superou os resultados encontrados para o problema de 18 barras (nós móveis) em eficiência e robustez para minimização do peso da estrutura. O desempenho do Algoritmo Evolutivo Híbrido proposto foi melhor que da literatura para o problema de estrutura com coordenadas nodais móveis. A utilização de um método para refinar as soluções foi importante para melhorar os resultados, mesmo com um pequeno comprometimento do tempo computacional. Os métodos desenvolvidos e a análise realizada por meio da aplicação dos algoritmos propostos aos problemas abordados são importantes para profissionais e pesquisadores da área de otimização e desenvolvedores de projetos estruturais, mesmo que em aplicações reais devam ser utilizados valores discretos. Para tanto, é necessário que os algoritmos e arquivos de inicialização, que contêm as configurações das estruturas e características do problema, sejam modificados. Desse modo, as soluções obtidas poderão ser aplicadas em projetos reais, pois as informações são discretas e baseada nos perfis comerciais comuns, que atenderão as normas brasileiras para projeto e execução de estruturas.

8.1 Trabalhos futuros

8.1

72

Trabalhos futuros

A seguir são descritas sugestões para trabalhos futuros com abordagem na área de otimização estrutural: - Aplicar novos parâmetros, como número máximo de gerações, probabilidade de crossover e mutação. Modificar a taxa, utilizada nos operadores genéticos e heurísticas de refinamento, que aumenta ou reduz a área de seção transversal ou o deslocamento de nó até encontrar um valor ótimo para esse parâmetro. - Modificar os operadores genéticos crossover e mutação a fim de melhorar a eficiência do algoritmo. - Implementar novas heurísticas computacionais que trabalham em conjunto com o AEH. Por exemplo, executar um outra heurística após um número de gerações sem melhora para tentar obter bons resultados. - Elaborar novas estruturas de vizinhanças que possuam maior eficiência. - Modificar o código-fonte dos algoritmos, aplicando técnicas de orientação a objetos para deixá-los mais legíveis. - Desenvolver um AEH para problema de 47 barras. - Adaptar o AEH para realizar a otimização de treliças tridimensionais ou espaciais. - Trabalhar com diferentes tipos de materiais, ou combinações de materiais comuns para construção de treliças. - Criar um AEH multiobjetivo, com estruturas dinâmicas e análise das frequências naturais de vibração.

73

Referências Bibliográficas ACHTZIGER, W. On simultaneous optimization of truss geometry and topology. Structural and Multidisciplinary Optimization, v. 33, p. 285–304, 2007. ANNICCHIARICO, W.; CERROLAZA, M. An evolutionary approach for the shape optimization of general boundary elements models. Eletronic Journal of Boundary Elements, BETEQ 2001, No 2001, p. 251–266, 2001. BAHIA, M. T. Otimização topológica aplicada ao projeto de mecanismos flexíveis. Dissertação (Mestrado) — Universidade Federal de Santa Catarina, Florianópolis, Novembro 2005. BARBOSA, F. R. et al. Aplicação do método dos elementos finitos no estudo de otimização de forma de elementos estruturais. Revista Horizonte Científico. UFU, 2005. CASTRO, R. E. de. Otimização de estruturas com multi-objetivos via algoritmos genéticos. Tese (Doutorado) — Universidade Federal do Rio de Janeiro, Rio de Janeiro, Agosto 2001. CHRISTOFORO, A. L.; MARCONATO, S. A. S.; OLIVEIRA, R. Z. G. de. Otimização numérica da área das seções transversais dos elementos componentes de estruturas planas do tipo treliça. Revista Brasileira de Biometria, v. 25, n. 3, p. 57–69, 2007. CODA, H. B.; PACCOLA, R. R. Software acadêmico para análise de pórticos e treliças planas. [S.l.], 2006. Acessado em: 10/09/2009. Disponível em: . COELLO, C. A. C.; RUDNICK, M.; CHRISTIANSEN, A. Using genetic algorithms for optimal design of trusses. Tools with Artificial Intelligence, 1994. Proceedings., Sixth International Conference on, p. 88–94, 1994. CORDEIRO, M. de F. Uma técnica para otimização estrutural mediante a derivada topológica. Dissertação (Mestrado) — Universidade Federal do Rio de Janeiro, Rio de Janeiro, Março 2007. FAWAZ, Z.; XU, Y. G.; BEHDINAN, K. Hybrid evolutionary algorithm and application to structural optimization. Structural and Multidisciplinary Optimization, v. 30, n. 3, p. 219–226, 2005. FONSECA, F. T. Sistema computacional para análise dinâmica geometricamente não-linear através do método dos elementos finitos. Dissertação (Mestrado) — Universidade Federal de Minas Gerais, Belo Horionte, Agosto 2008.

Referências Bibliográficas

74

FONSECA, F. T. da; PITANGUEIRA, R. L. da S. Um programa gráfico interativo para modelos estruturais de barras. Iberian Latin American Congress on Computational Methods in Engineering - XXV CILAMCE, Vol. CD-ROM, p. 1–15, 2004. FREDRICSON, H. Topology optimization of frame structures - joint penalty and material selection. Structural and Multidisciplinary Optimization, v. 30, p. 193–200, 2005. GOLDBERG, D. E. Genetic algorithms in search, optimization and machine learning. Reading, Massachusetts: Addison-Wesley Publishing Company, 1989. GOMES, F. A. M.; ANDO JUNIOR, T. Projeto ótimo de treliças: otimização estrutural. 2006. Acessado em: 04/09/2008. Disponível em: . GROSAN, C.; ABRAHAM, A. Hybrid evolutionary algorithms: Methodologies, architectures, and reviews. Studies in Computational Intelligence, v. 75, p. 1–17, 2007. GUERRA, C. Otimização paramétrica de estruturas treliçadas por algoritmos genéticos. Dissertação (Mestrado) — Universidade Federal do Rio Grande do Sul, Porto Alegre, Novembro 2008. KAWAMURA, H.; OHMORI, H.; KITO, N. Truss topology optimization by a modified genetic algorithm. Structural and Multidisciplinary Optimization, v. 23, p. 467–473, 2002. LIMA, E. O. Algortimo genético híbrido aplicado à otimização de funções. Dissertação (Mestrado) — Universidade Federal de Lavras, Lavras, 2008. MLADENOVIC, N.; HANSEN, P. Variable neighborhood search. Computers and Operations Researsh, Elsevier Science Ltd., Oxford, UK, v. 24, n. 11, p. 1097–1100, 1997. PARRA, D.; FRIEDLANDER, A. Algoritmos de otimização estrutural. In: UNICAMP. Caderno de resumos do XIV Congresso Interno de Iniciação Científica. Campinas, 2006. PENNA, S. S.; PITANGUEIRA, R. L. da S. On simultaneous optimization of truss geometry and topology. Structural and Multidisciplinary Optimization, v. 33, p. 285–304, 2007. PEREIRA, J. P. G. Heurísticas computacionais aplicadas à otimização estrutural de treliças bidimensionais. Dissertação (Mestrado) — Centro Federal de Educação Tecnológica de Minas Gerais, Belo Horizonte, Outubro 2007. PISINGER, D.; ROPKE, S. A general heuristic for vehicle routing problems. Computers & Operations Research, v. 34, n. 8, p. 2403–2435, August 2007. PRUDENTE, M. Otimização de estruturas de aço treliçadas planas com variáveis discretas. Tese (Doutorado) — Universidade de São Paulo, São Carlos, 1998.

Referências Bibliográficas

75

ROZVANY, G. I. N.; ZHOU, M. A note on truss design for stress and displacement constraints by optimality criteria methods. Structural and Multidisciplinary Optimization, v. 3, p. 45–50, 1991. SANTANNA, H. M. Otimização topológica de estruturas bidimensionais contínuas submetidas a restrições de flexibilidade e tensão. Dissertação (Mestrado) — Universidade Federal do Rio Grande do Sul, Porto Alegre, Março 2002. SASTRY, K.; GOLDBERG, D.; KENDALL, G. Genetic Algorithms. 2005. SOUZA, M. J. F. Inteligência computacional para otimização. 2005. Acessado em 08/09/2008. Disponível em: . YOKOTA, T.; TAGUGHI, T.; GEN, M. A solution method for optimal weight design problem of 10 bar truss using genetic algorithms. Department of Industrial and Systems Engineering. Ashikaga Institute of Technology, 1998. YUEFANG, W.; HUANCHUN, S.; LIHUA, H. Studies on optimal topology design of structures with discrete variables. Acta Mechanica Solida Sinica, v. 11, p. 139–145, 1998.