Traçado automático de envoltórias de esforços em estruturas planas utilizando um algoritmo evolucionário

Gisele Cristina da Cunha Holtz

Traado automtico de envoltrias de esforos em estruturas planas utilizando um algoritmo evolucionrio

Dissertao de Mestrado

Dissertao apresentada como requisito parcial para obteno do ttulo de Mestre pelo Programa de Ps-Graduao em Engenharia Civil da PUC-Rio.

Orientadores: Luiz Fernando C. R. Martha Luiz Eloy Vaz

Rio de Janeiro, abril de 2005

DBDPUC-Rio - Certificao Digital N 0310953/CA

Gisele Cristina da Cunha Holtz

Traado automtico de envoltrias de esforos em estruturas planas utilizando um algoritmo evolucionrio

Dissertao apresentada como requisito parcial para obteno do ttulo de Mestre pelo Programa de Ps-Graduao em Engenharia Civil da PUC-Rio. Aprovada pela Comisso Examinadora abaixo assinada.

Luiz Fernando Campos Ramos Martha Presidente / Orientador

Departamento de Engenharia Civil - PUC-Rio

Luiz Eloy Vaz Co-orientador

UFRJ

Raul Rosas e Silva Departamento de Engenharia Civil - PUC-Rio

Ivan Fbio Mota de Menezes Departamento de Informtica - PUC-Rio

Pedro Colmar Gonalves da Silva Vellasco UERJ

Jos Eugnio Leal Coordenador(a) Setorial do Centro Tcnico Cientfico - PUC-Rio

Rio de Janeiro, 14 de abril de 2005


Todos os direitos reservados. proibida a reproduo total ou parcial do trabalho sem autorizao da universidade, da autora e do orientador.

Gisele Cristina da Cunha Holtz Graduou-se em Engenharia Civil, pelo UniFOA - Centro Universitrio de Volta Redonda em 2002. Desenvolveu seu trabalho de pesquisa com nfase em computao grfica aplicada.

Ficha Catalogrfica

Holtz, Gisele Cristina da Cunha

Traado automtico de envoltrias de esforos em estruturas planas utilizando algoritmo evolucionrio / Gisela Cristina da Cunha Holtz ; orientador: Luiz Fernando C. R. Martha, Luiz Eloy Vaz. Rio de Janeiro : PUC, Departamento de Engenharia Civil, 2005.

v., 123 f. : IL. ; 29,7cm

Dissertao (mestrado) Pontifcia Universidade Catlica do Rio de Janeiro, Departamento de Engenharia Civil.

Inclui referncias bibliogrficas.

1. Engenharia civil Teses. 2. Estratgia evolutiva. 3. Computao evolucionria. 4. Envoltria de esforos internos. 5. Trem-tipo. I. Martha, Luiz Fernando Campos Ramos. II . Vaz, Luiz Eloy. III. Pontifcia Universidade Catlica do Rio de Janeiro. Departamento de Engenharia Civil. IV. Ttulo.

CDD: 624


Agradecimentos

A Deus, pela certeza de Seu amor incondicional.

Aos meus pais, Osmar e Ftima, que no mediram esforos para tornar possvel

a concretizao desta etapa, dando todo o apoio, carinho e incentivo

necessrios.

Ao meu marido Jlio, pelo companherismo, amor e pacincia inestimveis, que

tornaram mais ameno e agradvel o tempo dedicado concluso deste trabalho.

Ao meu irmo Gustavo, pela amizade e incentivo, e a minha irm Patrcia, pelos

cuidados e carinhos de uma verdadeira me.

Ao professor Luiz Fernando Martha, orientador deste trabalho, pela confiana

que me dedicou, pela qualidade de seus ensinamentos e pela eficincia ao

orientar este trabalho.

Ao professor Luiz Eloy Vaz, co-orientador deste trabalho, pelo direcionamento do

caminho a seguir no desenvolvimento deste trabalho e por suas valiosas

orientaes.

Aos professores Francisco Abreu, Nacib Abdala e Ildony Bellei, que foram os

primeiros a me incentivar a seguir este caminho.

A todos os amigos e familiares pelas oraes e pelo incentivo, em especial ao

meu av Joo Batista e a amiga Laci Tuller, que acompanharam de perto as

dificuldades enfrentadas, e aos novos amigos aqui conquistados, Juliana Vianna,

Patrcio Pires e Leandro Ferreira.

Aos amigos do TecGraf que muito contriburam, direta ou indiretamente, para o

desenvolvimento deste trabalho.

Ana Roxo e a todos os funcionrios e professores do Departamento de

Engenharia Civil da PUC.

Ao TecGraf pelo apoio financeiro e tecnolgico durante o curso de mestrado.

CAPES pelo apoio financeiro durante o curso de mestrado.


Resumo Holtz, Gisele Cristina da Cunha; Martha, Luiz Fernando C. R. (Orientador); Vaz, Luiz Eloy (Co-orientador). Traado automtico de envoltrias de esforos em estruturas planas utilizando um algoritmo evolucionrio. Rio de Janeiro, 2005. 123p. Dissertao de Mestrado - Departamento de Engenharia Civil, Pontifcia Universidade Catlica do Rio de Janeiro.

O objetivo deste trabalho desenvolver dentro do programa FTOOL uma

ferramenta para obteno de envoltrias de esforos internos devido a cargas

mveis. Envoltrias geralmente so obtidas atravs de interpolao de valores

limites de sees pr-selecionadas ao longo da estrutura. Estes valores so

obtidos com base no posicionamento da carga mvel em relao s linhas de

influncia dos esforos internos. A determinao de valores limites de um

esforo em uma seo constitui um problema de otimizao cujo objetivo

minimizar ou maximizar os valores dos esforos em relao posio do trem-

tipo que percorre a estrutura. Porm, no existe uma expresso analtica que

defina os valores limites de um esforo em uma seo para um dado trem-tipo, o

que impossibilita o uso da maioria dos mtodos clssicos de otimizao para

resolver o problema, porque esses mtodos requerem, na maioria das vezes, o

uso de pelo menos a primeira derivada da funo objetivo em relao s

variveis de projeto. Portanto, este trabalho adotou algoritmos da Estratgia

Evolutiva ( EE ) para determinar os valores limites devidos a cargas mveis.

Foram feitas duas implementao distintas de Estratgia Evolutiva, conhecidas

como EE+ )1( e EE+ )( . Alm de utilizar algoritmos de EE para

resolver o problema de envoltrias, foi desenvolvido um outro processo de

soluo denominado Fora Bruta, que consiste em percorrer com o trem-tipo

toda estrutura por passos pr-estabelecidos e calcular os valores dos esforos

mnimos e mximos. Para a grande maioria dos casos, os resultados obtidos

com a Estratgia Evolutiva foram corretos, porm, em alguns casos mais

crticos, o valor exato da envoltria no encontrado em algumas sees da

estrutura, embora encontre um valor muito prximo a ele. Observou-se que os

resultados da EE podem ser melhorados quando se enriquece a soluo com uma estratgia econmica de posicionamento de cargas concentradas em cima

de picos da linha de influncia.

Palavras-chave Estratgia Evolutiva, Computao Evolucionria, Envoltria de Esforos

Internos, Trem-tipo.


Abstract Holtz, Gisele Cristina da Cunha; Martha, Luiz Fernando C. R. (Advisor); Vaz, Luiz Eloy (Co-advisor). Automatic tracing of envelopes in planar structures using a evolutionary algorithm. Rio de Janeiro, 2005. 123p. MSc. Dissertation Civil Engineering Department, Pontifcia Universidade Catlica do Rio de Janeiro.

The objective of this work is to develop a tool for obtaining envelopes of

internal forces due to load-trains in the FTOOL software. Usually, envelopes are

obtained through interpolation of limiting values on pre-selected sections along

the structure. These values are obtained based on the positioning of the load-

train in relation to influence lines of internal forces. The determination of limiting

values of an effect at a section represents an optimization problem whose

objective is to minimize or maximize the values of that effect in relation to the

position of a load-train that passes along the structure. However, there is no

analytical expression that defines a limiting value of an effect on a section for a

specific load-train. Therefore, classical optimization methods cannot be used to

solve this problem. Rather, the solution requires a method that does not require

derivatives of the objective function. For this reason, this work adopts algorithms

of the Evolution Strategy (ES) to achieve the limiting values due to load-trains.

Two distinct algorithms of the ES, known as ES+ )1( and ES+ )( , were

implemented. In addition to the ES algorithms to trace the envelopes, another

process of solution called ForceBrute was developed. It consists of moving the

load-train in pre-determined steps along the structure and calculating minimum e

maximum values. In general, the ES method converges to the correct solution.

However, there are cases, depending on the complexity of the load-train, that the

algorithms do not find the exact limiting value (although usually very close to it). It

was observed that the ES results could be complemented and improved with

results from an inexpensive solution in which concentrated loads are positioned

on peak values of the influence lines.

Key-words Evolution Strategy, Evolutionary Computation, Envelopes of Internal

Forces, Load-Train.


Sumrio

1 Introduo 20 1.1. Objetivo 20 1.2. Organizao do Trabalho 21

2 Cargas Mveis, Linhas de Influncia e Envoltrias de Esforos 22 2.1. Introduo 22 2.2. Classificao das aes atuantes nas estruturas 22 2.3. Cargas Mveis 23 2.4. Linhas de Influncia 24 2.4.1. Traado de LI 25 2.5. Determinao de esforo extremo com base em LI 26 2.6. Envoltria Limite de Esforos 28

3 Mtodos de Otimizao 35 3.1. Introduo 35 3.2. Definies 35 3.3. Mtodos Determinsticos 36 3.4. Mtodos Probabilsticos 38 3.4.1. Computao Evolucionria 38 3.4.1.1. Definies 41 3.4.1.2. Algoritmo Evolucionrio 41 3.4.1.3. Principais Ramos da Computao Evolucionria 46 3.4.1.4. Algoritmos Genticos (AGs) 47 3.4.1.5. Programao Gentica (PG) 48 3.4.1.6. Programao Evolutiva (PE) 50 3.4.1.7. Estratgia Evolutiva (EE) 51 3.4.1.7.1. Distribuio Normal 52 3.4.1.7.2. Algoritmo Padro de EE 55 3.4.1.8. Comparao entre Estratgia Evolutiva e Algoritmo Gentico 57

4 Implementao Computacional 59 4.1. Introduo 59


4.2. Trem-tipo 59 4.2.1. NBR 7188 Carga mvel em ponte rodoviria e passarela de

pedestre 59 4.2.2. NBR 7189 Cargas mveis para projetos estrutural de obras

ferrovirias 62 4.2.3. Interface grfica 63 4.2.4. Carga Concentrada 65 4.2.5. Carga Distribuda 65 4.2.6. Carga de Multido 67 4.2.7. Estrutura de Dados 69 4.3. Funo Aptido 70 4.3.1. Eventos 71 4.3.1.1. Estrutura de Dados dos Eventos 72 4.3.2. Clculo da Funo Aptido 75 4.3.3. Envoltria de Esforos no FTOOL 75

5 Algoritmos Implementados 78 5.1. Introduo 78 5.2. Consideraes gerais 78

5.3. Estratgia 1+ - EE 80 5.3.1. Sub-diviso do Espao de busca 80 5.3.1.1. Estrutura de dados 81 5.3.1.2. Inicializao da populao 82 5.3.1.3. Mutao 82 5.3.1.4. Seleo 83 5.3.1.5. Critrio de parada 85

5.4. Estratgia + - EE 85 5.4.1. Estrutura de dados 85 5.4.1.1. Inicializao da populao 86 5.4.1.2. Mutao 86 5.4.1.3. Seleo 86 5.4.1.4. Critrio de parada 88 5.5. Fora Bruta 89 5.6. Cargas-em-picos 90

6 Exemplos de Validao e Anlise de Resultados 91


6.1. Introduo 91 6.2. Exemplo 1 91 6.2.1. Envoltria de Esforo Cortante 92 6.2.1.1. Variao dos Parmetros 96 6.2.2. Envoltria de Momento Fletor 98 6.3. Exemplo 2 100 6.3.1. Envoltria de Esforo Cortante 100 6.3.2. Envoltria de Momento Fletor 102 6.4. Exemplo 3 104 6.4.1. Envoltria de Esforo Normal 105 6.4.2. Envoltria de Esforo Cortante 106 6.4.3. Envoltria de Momento Fletor 108 6.5. Exemplo 4 109 6.5.1. Envoltria de Esforo Cortante 110 6.5.2. Envoltria de Momento Fletor 111 6.6. Testes Realizados 113 6.6.1. Caso 1 113 6.6.2. Caso 2 115 6.7. Anlise do nmero de avaliaes da funo aptido 116 6.8. Anlise do tempo de processamento 117

7 Concluso 119 7.1. Sugesto para trabalhos futuros 120

Referncia Bibliogrfica 121


Lista de figuras

Figura 2.1 Linha de influncia de momento fletor em uma seo de uma viga

contnua. 24 Figura 2.2 Deslocamentos generalizados utilizados no mtodo cinemtico. 26 Figura 2.3 Carga permanente uniformemente distribuda atuando em uma viga

contnua. 26 Figura 2.4 Posicionamento da carga mvel para provocar mximo momento

fletor em uma seo. 27 Figura 2.5 Posicionamento da carga mvel para provocar mnimo momento

fletor em uma seo. 27 Figura 2.6 Viga bi-apoiada com balanos, carga permanente e carga mvel. 29 Figura 2.7 Esforos internos da carga permanente. 29

Figura 2.8 Esforo cortante mximo e mnimo na seo esqB . 30

Figura 2.9 Esforo cortante mximo e mnimo na seo dirB . 30 Figura 2.10 Esforo cortante mximo e mnimo na seo C . 30 Figura 2.11 Esforo cortante mximo e mnimo na seo D . 31 Figura 2.12 Envoltrias de Esforo Cortante. 32 Figura 2.13 Momento fletor mximo e mnimo na seo B . 32 Figura 2.14 Momento fletor mximo e mnimo na seo C . 32 Figura 2.15 Momento fletor mximo e mnimo na seo D . 33 Figura 2.16 Envoltrias de momento fletor. 33 Figura 3.1 Formulao de um problema de otimizao. 37 Figura 3.2 Evoluo tpica de um AE , ilustrada de acordo com a distribuio

da populao. Adaptado de EIBEN & SMITH (2003). 40 Figura 3.3 Esquema geral de um Algoritmo Evolucionrio. Adaptado de

BCK et al (1997). 45 Figura 3.4 Ramificao da Inteligncia Artificial. Adaptada de

OLIVIERI (2004). 46 Figura 3.5 Seleo utilizando o mtodo da roleta (Barbosa, 1977). 48 Figura 3.6 Crossover na PG : seleo aleatria dos ramos que sofrero o corte

(SOUSA & ANDRADE, 1998). 49 Figura 3.7 Crossover na PG : funes resultantes (SOUSA & ANDRADE,

1998). 50


Figura 3.8 Aplicao do operador de mutao na PG

(SOUSA & ANDRADE, 1998). 50 Figura 3.9 Funo de densidade de probabilidade de uma v.a. normal com

mdia e desvio padro . 53 Figura 3.10 Nmeros gerados pela funo rand da biblioteca da linguagem C.54 Figura 3.11 Nmeros gerados pela transformao da v.a. uniforme em v.a.

normal. 54 Figura 4.1 Trem-tipo composto de um veculo e de cargas uniformemente

distribudas (NBR 7188, 1982). 60 Figura 4.2 Veculos-tipo (NBR 7188, 1982). 61 Figura 4.3 Caractersticas geomtricas do trem-tipo (NBR 7189, 1985). 62 Figura 4.4 - Interface grfica para a edio de um novo trem-tipo. 63 Figura 4.5 Lista expansvel para seleo do trem-tipo. 63 Figura 4.6 Mdulo para edio do nome do trem-tipo. 64 Figura 4.7 rea destinada edio do comprimento do trem-tipo. 64 Figura 4.8 Matriz de cargas concentradas. 65 Figura 4.9 Matriz de cargas distribudas para trem-tipo rodovirio. 66 Figura 4.10 Matriz de cargas distribudas para trem-tipo ferrovirio. 66 Figura 4.11 Cargas de multido. 67 Figura 4.12 Trecho de uma ponte. 68 Figura 4.13 LI da reao no apoio A , na Seo IIII . 68 Figura 4.14 LI da reao no apoio A , na Seo II . 69 Figura 4.15 Trem-tipo unidimensional resultante da transformao do trem-tipo

classe 45 da NBR-7188 (1982) . 69 Figura 4.16 Estrutura de dados do trem-tipo. 70 Figura 4.17 Linha de influncia com a identificao dos eventos. 72 Figura 4.18 Estrutura de dados de um evento 72 Figura 4.19 Botes para seleo dos esforos. 76 Figura 4.20 Prtico com envoltria de esforo cortante devido ao de uma

carga mvel 76 Figura 4.21 LI com trem-tipo nas posies crticas. 77 Figura 5.1 Prtico com viga inclinada, trem-tipo e espao de busca. 79 Figura 5.2 Determinao do trecho inicial e final. 81 Figura 5.3 Estrutura de dados dos trechos. 82 Figura 5.4 Processo de busca por trechos. 84 Figura 5.5 Estrutura de dados de um indivduo. 85


Figura 6.1 Exemplo 1. 91 Figura 6.2 Envoltria de esforo cortante do Exemplo 1 para EE+ 1 ,

EE+ , Fora Bruta e Cargas-em-picos. 92

Figura 6.3 LI de Esforo Cortante da Seo Ddir do Exemplo 1 com o trem-tipo na posio crtica. 95 Figura 6.4 Diferena entre a envoltria obtida e a envoltria real. 96 Figura 6.5 Surgimento de falhas na envoltria de esforos cortantes no

balano. 97 Figura 6.6 Nmero de avaliaes da funo aptido no Exemplo 1 x . 97

Figura 6.7 Variao do esforo cortante mximo na seo dirB do Exemplo 1 em funo de . 98 Figura 6.8 Envoltria de momento fletor do Exemplo 1 para EE+ 1 ,


Figura 6.9 Falha na envoltria de momento fletor ao utilizar a

Estratgia + . 100


EE+ e Fora Bruta. 101

Figura 6.12 Envoltria de esforo cortante do Exemplo 2 para Cargas-em-

picos. 101 Figura 6.13 Envoltria de momento fletor do Exemplo 2 para EE+ 1 ,

EE+ e Fora Bruta. 103

Figura 6.14 Envoltria de momento fletor do Exemplo 2 para

Cargas-em-picos. 103 Figura 6.15 Exemplo 3. 105 Figura 6.16 Envoltria de esforo normal do Exemplo 3 para EE+ 1 ,


Figura 6.17 Envoltria de esforo cortante do Exemplo 3 para EE+ 1 ,


Figura 6.18 Envoltria momento fletor do Exemplo 3 para EE+ 1 ,




Figura 6.21 Envoltria de momento fletor do Exemplo 4 para EE+ 1 ,



Figura 6.22 Trem-tipo do Caso 1. 113 Figura 6.23 Envoltria de esforo cortante no balano da estrutura do Exemplo

4 utilizando o trem-tipo do Caso 1 . 114

Figura 6.24 LI de esforo cortante da seo dirB do Exemplo 3 com trem-tipo

nas posies crticas. 114 Figura 6.25 Trem-tipo caso 2. 115 Figura 6.26 Envoltria de esforo cortante da estrutura do Exemplo 4 para o

trem-tipo do Caso 2 utilizando EE+ 1 . 115 Figura 6.27 Envoltria de esforo cortante da estrutura do Exemplo 4 para o

trem-tipo do Caso 2 utilizando Cargas-em-picos. 116 Figura 6.28 Nmero de avaliaes da funo aptido na envoltria de esforo

cortante mximo. 116 Figura 6.29 Tempo de processamento do programa para clculo da envoltria

de esforo cortante mximo. 117


Lista de quadros

Quadro 4.1 Botes de manipulao do trem-tipo. 64 Quadro 4.2 Possveis tipos de ocorrncia de eventos. 74 Quadro 4.3 Botes para calcular a envoltria de esforos. 75


Lista de tabelas

Tabela 2.1 Envoltrias de Esforo Cortante [kN]. 31 Tabela 2.2 Resultados obtidos na envoltria de momento fletor. 33 Tabela 3.1 Comparao entre Estratgia Evolutiva e Algoritmo Gentico 58 Tabela 4.1 Cargas dos veculos (NBR 7188, 1982). 60 Tabela 4.2 Caractersticas dos veculos (NBR 7188, 1982). 61 Tabela 4.3 Cargas dos trens-tipo (NBR 7189, 1985). 62 Tabela 5.1 . Parmetros adotados na ES+ )( . 87

Tabela 6.1 Resultados obtidos na envoltria de esforo cortante do

Exemplo 1. 92 Tabela 6.2 Erros relativos na envoltria de esforo cortante do Exemplo 1. 93 Tabela 6.3 Nmero de avaliaes da funo aptido no traado da envoltria

de esforo cortante do Exemplo 1. 94 Tabela 6.4 Resultados obtidos na envoltria de momento fletor do

Exemplo 1. 99 Tabela 6.5 Erros relativos na envoltria de momento fletor do Exemplo 1. 99 Tabela 6.6 Nmero de avaliaes da funo aptido no traado da envoltria

de momento fletor do Exemplo 1. 99 Tabela 6.7 Resultados obtidos na envoltria de esforo cortante do

Exemplo 2. 101 Tabela 6.8 Erros relativos na envoltria de esforo cortante do Exemplo 2. 102 Tabela 6.9 Nmero de avaliaes da funo aptido no traado da envoltria



de momento fletor do Exemplo 2. 104 Tabela 6.13 Resultados obtidos na envoltria de esforo normal na coluna do

prtico do Exemplo 3. 105 Tabela 6.14 Erros relativos na envoltria de esforo normal na coluna do

prtico do Exemplo 3. 106 Tabela 6.15 Nmero de avaliaes da funo aptido no traado da envoltria

de esforo normal do Exemplo 3. 106


Tabela 6.16 Resultados obtidos na envoltria de esforos cortantes do

Exemplo 3. 107 Tabela 6.17 Erros relativos na envoltria de esforo cortante do Exemplo 3.107

Tabela 6.18 Nmero de avaliaes da funo aptido no traado da envoltria

de esforo cortante do Exemplo 3. 107 Tabela 6.19 Resultados obtidos na envoltria de momento fletor do Exemplo

3. 108 Tabela 6.20 Erros relativos na envoltria de momento fletor do

Exemplo 3. 109 Tabela 6.21 Nmero de avaliaes da funo aptido no traado da envoltria

de momento fletor do exemplo 3. 109 Tabela 6.22 Resultados obtidos na envoltria de esforo cortante do

Exemplo 4. 110 Tabela 6.23 Erros relativos na envoltria de esforo cortante do Exemplo 4.111 Tabela 6.24 Nmero de avaliaes da funo aptido no traado da envoltria



de momento fletor do Exemplo 4. 112


Lista de Smbolos

Romanos dx Distncia que a estrutura discretizada

E Esforo ou reao

fd Funo densidade

g Carga uniformemente distribuda

i Indica uma das variveis da funo objetivo

IND ndice fornecido pela decodificao da varivel

k Nmero mximo de geraes que um indivduo pode permanecer na

populao

sLIM Ordenada genrica da linha de influncia de momento fletor

SM Momento fletor em S

n nmero de variveis da funo objetivo

na nmero de avaliaes da funo aptido em uma seo transversal da

estrutura

nb Nmero de bits

gern Nmero de geraes

secn Nmero de sees transversais que a estrutura foi discretizada

totn Nmero total de avaliaes da funo aptido em toda estrutura

P Carga concentrada p Carga de multido externa

'p Carga de multido interna

cp Probabilidade de recombinao (crossover)

ip Probabilidade de seleo

mp Probabilidade de ocorrncia de mutao de um gene

q Carregamento acidental de ocupao q Carga distribuda correspondente ao vago cheio no trem-tipo ferrovirio

'q Carga distribuda correspondente ao vago vazio no trem-tipo ferrovirio

R Reao de apoio

S Seo transversal da estrutura

t Tamanho dos sub-grupos de torneios na PE


u Varivel aleatria uniforme

v Indivduo genitor

'v Indivduo descendente

x Ponto de busca no espao

x Posio da carga unitria no clculo da linha de influncia

x Posio da carga concentrada do trem-tipo

xa Posio inicial da carga distribuda do trem-tipo

xb Posio final da carga distribuda do trem-tipo Lx Limite inferior do espao de busca Ux Limite superior do espao de busca

z Varivel aleatria normal padro

l comprimento do caminho que o trem-tipo ir percorrer

tl comprimento do trem-tipo

totl Comprimento total da estrutura

Gregos Mdia

Deslocamento generalizado

Nmero de descendentes Nmero de genitores

Rotao Nmero de indivduos que participam da recombinao

Desvio padro 2 Varincia

Parmetro da Estratgia Evolutiva

' Parmetro da Estratgia Evolutiva


Lista de Abreviaturas

AE Algoritmo Evolucionrio

AG Algoritmo Gentico

EE Estratgia Evolutiva

FTOOL Two-dimensional Frame Analysis Tool

LI Linha de influncia

LIM Linha de influncia de momento fletor

LIQ Linha de influncia de esforo cortante

PDV Princpio dos deslocamentos virtuais

PE Programao Evolutiva

PG Programao Gentica

v.a. Varivel aleatria


1 Introduo

1.1. Objetivo

Para o dimensionamento de estruturas submetidas a cargas mveis, tais

como pontes rodovirias, ferrovirias e prticos industriais, essencialmente

necessrio o conhecimento dos esforos limites, mnimos e mximos, atuantes

nas sees das estruturas. Esses esforos so geralmente dispostos em um

diagrama denominado de envoltria de esforos.

O traado de envoltrias de esforos um processo muito trabalhoso.

Ele se baseia na determinao de linhas de influncia (considerao de efeitos

de cargas unitrias) do esforo em questo para cada seo da estrutura e no

posicionamento da carga mvel em relao linha de influncia. Esse

posicionamento feito em vrias tentativas, pois, em geral, no obvia a

posio da carga mvel que provoca um valor extremo do esforo em uma

seo.

O objetivo deste trabalho desenvolver, dentro do programa FTOOL

(Two-dimensional Frame Analysis Tool), uma ferramenta para determinar

envoltrias de esforos a partir das posies de atuao do trem-tipo (carga

mvel) que causam os esforos limites.

O FTOOL um programa educacional de anlise estrutural de prticos

planos. Ao contrrio de muitos programas educativos que se preocupam em

ensinar tcnicas de anlise numrica, o objetivo bsico do FTOOL (MARTHA,

1999) motivar os alunos a aprender o comportamento estrutural. Para tanto,

possui uma interface amigvel que permite fcil criao e manipulao dos

modelos.

So poucos os programas que possuem ferramentas para traado de

envoltrias de esforos e, dos que possuem, muitos o fazem de maneira

incorreta ou incompleta. A idia natural que surge para explicar o traado de

envoltrias movimentar a carga mvel ao longo da estrutura calculando o valor

do esforo em sees pr-estabelecidas da estrutura para cada posio da

carga mvel e, aps percorrer toda estrutura, determinar os valores extremos do


Introduo 21

esforo em cada seo. Isso feito, por exemplo, pelo programa Dr. Beam (Dr.

SOFTWARE, 2005). Entretanto, esse processo no considera todas as

particularidades dos trens-tipo, como a existncia da carga de multido. Outros

programas, como o STRAP (ATIR, 2005), embora considerem esse tipo de

carga, percorrem toda estrutura com a carga mvel por passos de tamanho pr-

estabelecidos para determinar os esforos limites e, sendo assim, no verificam

todas as posies possveis.

As dificuldades no processo do traado de envoltrias de esforos muitas

vezes limitam a percepo dos alunos ao comportamento das estruturas

submetidas a cargas mveis. Este trabalho busca no s traar envoltrias de

esforos provocados por cargas mveis de forma correta como tambm oferecer

uma ferramenta educativa eficiente para o ensino do traado. A implementao

da envoltria de esforos enriquece ainda mais a caracterstica educacional do

FTOOL, pois alm da obteno da envoltria propriamente dita, o aluno pode

analisar para uma seo da estrutura as posies crticas do trem-tipo. Alm

disso, pode-se testar diferentes alternativas de trens-tipo, adquirindo

sensibilidade ao comportamento estrutural.

1.2. Organizao do Trabalho

O captulo dois mostra como se pode obter o esforo em uma seo da

estrutura devido ao de uma carga mvel a partir da sua linha de influncia.

Alguns mtodos de otimizao so apresentados no captulo trs, onde

dado uma maior nfase a Computao Evolucionria, que uma famlia de

mtodos probabilsticos de otimizao a qual pertence a Estratgia Evolutiva,

que foi utilizada neste trabalho.

No captulo quatro descreve-se a implementao computacional, incluindo

as modificaes na estrutura de dados e na interface grfica do FTOOL para a

criao dos trens-tipo e o traado das envoltrias de esforos.

Os detalhes da implementao dos algoritmos utilizados para a

determinao dos esforos limites esto no captulo cinco.

Para a validao da ferramenta desenvolvida, o captulo seis mostra

exemplos e comparaes dos resultados obtidos.

As concluses finais e comentrios foram feitos no captulo sete, onde

tambm se ressaltam as caractersticas dos resultados obtidos atravs de cada

mtodo.


2 Cargas Mveis, Linhas de Influncia e Envoltrias de Esforos

2.1. Introduo

Para o dimensionamento de qualquer estrutura necessrio conhecer os

esforos mximos e mnimos que ela apresentar ao ser submetida ao

carregamento que ser destinada. Para estruturas submetidas a cargas mveis

existe um diagrama, denominado de envoltria de esforos, que determina os

valores limites, mximo ou mnimo, para as sees transversais da estrutura.

A seguir, sero apresentados conceitos, relacionados a cargas mveis e

traado de linhas de influncia, necessrios ao clculo das envoltrias de

esforos, bem como ser exemplificada a determinao de uma envoltria de

esforos e discutida as maneiras de obt-la.

2.2. Classificao das aes atuantes nas estruturas

De acordo com a NBR 8681 (1984), as aes atuantes nas estruturas,

que so as causas que provocam esforos ou deformaes, podem ser

classificadas segundo sua variabilidade no tempo em trs categorias:

Aes permanentes

So as cargas que ocorrem com valores constantes ou de pequena

variao em torno de sua mdia, durante praticamente toda a vida da

construo. As aes permanentes so divididas em diretas, tais como os

pesos prprios dos elementos da construo, incluindo-se o peso prprio

da estrutura e de todos os elementos construtivos permanentes, e

indiretas, como protenso, recalques de apoio e a retrao dos materiais.

Aes variveis

So as cargas que ocorrem com valores que apresentam variaes

significativas em torno de sua mdia, durante a vida da construo. So


Cargas Mveis, Linhas de Influncia e Envoltrias de Esforos 23

as cargas mveis ou acidentais das construes, isto , cargas que atuam

nas construes em funo de seu uso (pessoas, mobilirio, veculos,

materiais diversos, etc.).

Elas podem ser normais, quando possuem probabilidade de ocorrncia

suficientemente grande para que sejam obrigatoriamente consideradas no

projeto das estruturas de um dado tipo de construo, ou especiais, como

aes ssmicas ou cargas acidentais de natureza ou de intensidade

especiais.

Aes excepcionais

So as cargas que tm durao extremamente curta e muito baixa

probabilidade de ocorrncia durante a vida da construo, mas que devem

ser consideradas nos projetos de determinadas estruturas. Por exemplo,

aes excepcionais podem ser decorrentes de exploses, choques de

veculos, incndios, enchentes ou sismos excepcionais.

2.3. Cargas Mveis

Diversas estruturas so solicitadas por cargas mveis. Exemplos so

pontes rodovirias e ferrovirias ou prticos industriais que suportam pontes

rolantes para transporte de cargas. Os esforos internos nestes tipos de

estrutura no variam apenas com a magnitude das cargas aplicadas, mas

tambm com a posio de atuao das mesmas. Portanto, o projeto de um

elemento estrutural, como uma viga de ponte, envolve a determinao das

posies das cargas mveis que produzem valores extremos dos esforos nas

sees do elemento.

No projeto de estruturas submetidas a cargas fixas, a posio de atuao

de cargas acidentais de ocupao tambm influencia na determinao dos

esforos dimensionantes. Por exemplo, o momento fletor mximo em uma

determinada seo de uma viga contnua com vrios vos no determinado

pelo posicionamento da carga acidental de ocupao em todos os vos.

Posies selecionadas de atuao da carga acidental vo determinar os valores

limites de momento fletor na seo. Assim, o projetista ter que determinar, para

cada seo a ser dimensionada e para cada esforo dimensionante, as posies

de atuao das cargas acidentais que provocam os valores extremos (mximos

e mnimos de um determinado esforo).



Uma alternativa para este problema seria analisar a estrutura para vrias

posies das cargas mveis ou acidentais e selecionar os valores extremos.

Este procedimento no prtico nem eficiente de uma maneira geral, exceto

para estruturas e carregamentos simples. O procedimento geral e objetivo para

determinar as posies de cargas mveis e acidentais que provocam valores

extremos de um determinado esforo em uma seo de uma estrutura feito

com auxlio de Linhas de Influncia.

2.4. Linhas de Influncia

Linhas de Influncia ( LI ) descrevem a variao de um determinado efeito

(por exemplo, uma reao de apoio, um esforo cortante ou um momento fletor

em uma seo) em funo da posio de uma carga vertical unitria que passeia

sobre a estrutura. Assim, a LI de momento fletor em uma seo a

representao grfica ou analtica do momento fletor, na seo de estudo,

produzida por uma carga concentrada vertical unitria, geralmente de cima para

baixo, que percorre a estrutura. Isso exemplificado na Figura 2.1, que mostra a

LI de momento fletor em uma seo S indicada. Nesta figura, a posio da

carga unitria 1=P dada pelo parmetro x , e uma ordenada genrica da LI

representa o valor do momento fletor em S em funo de x , isto ,

)(xMLIM SS = . Em geral, os valores positivos dos esforos nas linhas de

influncia so desenhados para baixo e os valores negativos para cima.

S

MS(x)

P = 1 x

Figura 2.1 Linha de influncia de momento fletor em uma seo de uma viga contnua.

Com base no traados de sLI ' , possvel obter as chamadas envoltrias

limites de esforos que so necessrias para o dimensionamento de estruturas

submetidas a cargas mveis ou acidentais.



2.4.1. Traado de LI

O FTOOL calcula a linha de influncia de um esforo E utilizando o Princpio de Mller-Breslau (SSSEKIND, 1997), tambm conhecido como

mtodo cinemtico para o traado de LI , que foi formulado por Mller-Breslau

no final do sculo 19.

Este mtodo pode ser demonstrado atravs do Princpio dos

Deslocamentos Virtuais - PDV (Martha, 2005) e pode ser aplicado para qualquer

tipo de estrutura, isosttica ou hiperesttica. Embora este mtodo possa ser

utilizado para obteno de LI de esforos e reaes, o FTOOL no calcula LI

de reaes.

De uma maneira resumida, para se traar a linha de influncia de um efeito

E (esforo ou reao), procede-se da seguinte forma (SSSEKIND, 1997):

rompe-se o vnculo capaz de transmitir o efeito E cuja linha de influncia se deseja determinar;

na seo onde atua o efeito E , atribui-se estrutura, no sentido oposto ao de E positivo, um deslocamento generalizado unitrio, que ser tratado com sendo muito pequeno;

a configurao deformada (elstica) obtida a linha de influncia.

O deslocamento generalizado que se faz referncia depende do efeito em

considerao, tal como indicado na Figura 2.2. No caso de uma reao de apoio,

o deslocamento generalizado um deslocamento absoluto da seo do apoio.

Para um esforo normal, o deslocamento generalizado um deslocamento axial

relativo na seo de esforo normal. Para um esforo cortante, o deslocamento

generalizado um deslocamento transversal relativo na seo do esforo

cortante. E para um momento fletor, o deslocamento generalizado uma rotao

relativa entre as tangentes elstica adjacentes seo do momento fletor.



= 1

V

Q

M M

Q

Reao de apoio

Esforo cortante

Momento fletor

= 1

= 1

Efeito Deslocamento generalizado

N N

Esforo normal = 1

Figura 2.2 Deslocamentos generalizados utilizados no mtodo cinemtico.

2.5. Determinao de esforo extremo com base em LI

A determinao de valores mximo e mnimo de um esforo interno em

uma seo de estudo exemplificada para o caso do momento fletor na seo

S da Figura 2.1. O carregamento permanente, constitudo do peso prprio da

estrutura, representado por uma carga uniformemente distribuda g , tal como

indica a Figura 2.3.

g S

LIMS

Figura 2.3 Carga permanente uniformemente distribuda atuando em uma viga

contnua.

Considerando que a ordenada de ( )( )xMLIM SS = funo de uma carga concentrada unitria, o valor do momento fletor em S devido ao carregamento permanente pode ser obtido por integrao do produto da carga infinitesimal

gdx por ( )xM S ao longo da estrutura (Equao 2.1):



==12

0

12

0

)( gdxLIMgdxxMM SSgS (2.1)

Considere que existe uma carga mvel atuando sobre a estrutura, que

composta por uma carga concentrada P e por um carregamento acidental de ocupao que representado por uma carga uniformemente distribuda q . Por

ser acidental, a carga q pode atuar parcialmente ao longo da estrutura. O que

se busca so as posies de atuao das cargas P e q que maximizam ou

minimizam o momento fletor em S . O valor mximo de sM obtido quando a

carga q est posicionada sobre ordenadas positivas da sLIM e a carga P est

sobre a maior ordenada positiva, e o valor mnimo obtido quando a carga q

est posicionada sobre ordenadas negativas da sLIM e a carga P est sobre a

maior ordenada negativa. Isso mostrado nas Figuras 2.4 e 2.5.

q q

q S

LIMS

P

Figura 2.4 Posicionamento da carga mvel para provocar mximo momento fletor em

uma seo.

q

S LIMS

P

Figura 2.5 Posicionamento da carga mvel para provocar mnimo momento fletor em

uma seo.

Os valores mximo e mnimo de sM devidos somente ao carregamento

acidental podem ser obtidos por integrao do produto qdxLIM s . nos trechos

positivos e negativos, respectivamente, da linha de influncia, conforme

equaes 2.2 e 2.3:



( ) +=12

9

4

0

qdxLIMqdxLIMM SSmxqS (2.2)

( ) =9

4

qdxLIMM SmnqS (2.3)

Os valores mximo e mnimo de sM devidos carga concentrada podem

ser obtidos pelo produto PLIM s . , onde sLIM a maior ordenada positiva ou

negativa da linha de influncia, respectivamente :

( ) PLIMM mxmxPS S = (2.4) ( ) PLIMM mnmnPS S = (2.5)

Assim, os valores mximos e mnimos finais de sM provocados pelo

carregamento permanente e pela carga mvel so :

( ) ( ) ( )mxPSmxqSgSmxS MMMM ++= (2.6) ( ) ( ) ( )mnPSmnqSgSmnS MMMM ++= (2.7)

Observe que, no caso geral, o valor mximo final de um determinado

esforo em uma seo no necessariamente positivo, nem o valor mnimo final

necessariamente negativo. Isto vai depender da magnitude dos valores

provocados pelos carregamentos permanente e acidental. Quando mximo e

mnimo tiverem o mesmo sinal, o esforo dimensionante ser o que tiver a maior

magnitude. Quando mximo e mnimo tiverem sentidos opostos, principalmente

no caso de momento fletor, ambos podem ser dimensionantes.

2.6. Envoltria Limite de Esforos

As envoltrias limites de um determinado esforo em uma estrutura

descrevem para um conjunto de cargas mveis ou acidentais, os valores

mximos e mnimos deste esforo em cada uma das sees da estrutura, de

forma anloga a que descreve o diagrama de esforos para um carregamento

fixo. Assim, o objetivo da Anlise Estrutural para o caso de cargas mveis ou

acidentais a determinao de envoltrias de mximos e mnimos de momentos

fletores, esforos cortantes, etc., o que possibilitar o dimensionamento da



estrutura submetida a este tipo de solicitao. As envoltrias so, em geral,

obtidas por interpolao de valores mximos e mnimos, respectivamente, de

esforos calculados em determinado nmero de sees transversais ao longo da

estrutura.

A seguir mostrado um exemplo de determinao de envoltria de

esforos internos de uma viga bi-apoiada com balanos, carga permanente e

carga mvel (Figura 2.6). Na figura tambm esto indicadas as sees adotadas

para o clculo dos valores limites e para o traado das envoltrias. Devido a

simetria da estrutura em relao seo D , a obteno dos valores limites ser

demonstrada apenas para as sees A , B , C e D , visto que a envoltria de

esforo cortante ser anti-simtrica e a de momento fletor ser simtrica.

Carga Mvel

Carga Permanente

A B C D E F G Besq Bdir Fesq Fdir

Estrutura e sees trans-versais para envoltrias

Figura 2.6 Viga bi-apoiada com balanos, carga permanente e carga mvel.

Os esforos devidos carga permanente foram primeiramente calculados,

ou seja, determinaram-se os diagramas de esforo cortante e de momento fletor

(Figura 2.7).

A C D E G Besq

Bdir Fesq

Fdir

A B

C D E F

G

Carga Permanente: Esforos Cortantes [kN]

Carga Permanente: Momentos Fletores [kNm]

Figura 2.7 Esforos internos da carga permanente.

Em seguida, determinaram-se os esforos cortantes mximos e mnimos

devidos carga mvel para cada seo transversal adotada da estrutura

(Figuras 2.8 a 2.11). O posicionamento do trem-tipo para determinar os valores

limites em cada seo segue o procedimento mostrado na seo 2.5.



Posio da carga mvel para QBesq mnimo

Posio da carga mvel para QBesq mximo (carga mvel no atuando)

LIQBesq Besq

( ) [ ] kNQ mcmnBesq

00.60)00.1(310)00.1(10)00.1(20...

=++=

( ) 0...

=mcmxBesq

Q

Figura 2.8 Esforo cortante mximo e mnimo na seo esqB .

Posio da carga mvel para QBdir mnimo

Posio da carga mvel para QBdir mximo

LIQBdir Bdir

( ) [ ] kNQ mcmnBdir 75.8)25.0(35.010)25.0(20.. . =+=

( ) [ ] kNQ mcmxBdir 25.91)00.1(125.010)25.0(35.010)75.0(10)00.1(20.. . +=+++=

Figura 2.9 Esforo cortante mximo e mnimo na seo dirB .

Posio da carga mvel para QC mnimo

Posio da carga mvel para QC mximo

LIQC C

( ) [ ] kNQ mcmnC 50.12)25.0(35.010)25.0(35.010)25.0(20.. . =++=

( ) [ ] kNQ mcmxC 50.57)75.0(95.010)25.0(35.010)50.0(10)75.0(20.. . +=+++=

Figura 2.10 Esforo cortante mximo e mnimo na seo C .



Posio da carga mvel para QD mnimo

Posio da carga mvel para QD mximo

LIQD D

( ) [ ] kNQ mcmnD 25.31)25.0(35.010)50.0(65.010)25.0(10)50.0(20.. . =+++=

( ) [ ] kNQ mcmxD 25.31)25.0(35.010)50.0(65.010)25.0(10)50.0(20.. . +=+++=

Figura 2.11 Esforo cortante mximo e mnimo na seo D .

A Tabela 2.1 mostra os resultados do esforo cortante mximo e mnimo

nas sees da estrutura devido a cada carregamento atuante e o valor final das

envoltrias de esforo cortante, que esto representadas na Figura 2.12. O

esforo cortante devido carga mvel na extremidade livre do balano

corresponde carga de 20 kN posicionada sobre esta seo.

Tabela 2.1 Envoltrias de Esforo Cortante [kN].

Seo Carga Carga Mvel Envoltrias

Permanente mnimo mximo mnimo mximo

A 0 -20.00 0 -20.00 0

Besq -60 -60.00 0 -120.00 -60.00

Bdir +120 -8.75 +91.25 +111.25 +211.25

C +60 -12.50 +57.50 +47.50 +117.50

D 0 -31.25 +31.25 -31.25 +31.25

E -60 -57.50 +12.50 -117.50 -47.50

Fesq -120 -91.25 +8.75 -211.25 -111.25

Fdir +60 0 +60.00 +60.00 +120.00

G 0 0 +20.00 0 +20.00



-120

Envoltrias: Esforos Cortantes [kN]

-20 -60

2012060

mnimos

mximos 211.25

111.25

-211.25

-111.25

-47.50

-117.50

47.50

117.50

-31.25

31.25

carga permanente faixa de

trabalho

Figura 2.12 Envoltrias de Esforo Cortante.

As Figuras de 2.13 a 2.15 mostram como foi feita a determinao dos

momentos fletores mximos e mnimos devidos carga mvel para cada seo

transversal da estrutura.

Posio da carga mvel para MB mnimo

Posio da carga mvel para MB mximo

LIMB

(carga mvel no atuando)

B

( ) [ ] kNmM mcmnB 00.105)00.3(35.010)00.3(20.. . =+=

( ) 0.. . =mcmxBM

Figura 2.13 Momento fletor mximo e mnimo na seo B .

Posio da carga mvel para MC mnimo

Posio da carga mvel para MC mximo

LIMC C

( ) [ ] kNmM mcmnC 00.90)75.0(35.010)25.2(35.010)25.2(20.. . =++=

( ) [ ] kNmM mcmxC 00.195)25.2(125.010)50.1(10)25.2(20.. . +=++=

Figura 2.14 Momento fletor mximo e mnimo na seo C .



Posio da carga mvel para MD mnimo

Posio da carga mvel para MD mximo

LIMD D

( ) [ ] kNmM mcmnD 00.75)50.1(35.010)50.1(35.010)50.1(20.. . =++=

( ) [ ] kNmM mcmxD 00.255)00.3(125.010)50.1(10)00.3(20.. . +=++=

Figura 2.15 Momento fletor mximo e mnimo na seo D .

A Tabela 2.2 mostra os resultados do momento fletor mximo e mnimo

nas sees da estrutura devido a cada carregamento atuante e o valor final das

envoltrias de momento fletor, que esto representadas na Figura 2.16.

Tabela 2.2 Resultados obtidos na envoltria de momento fletor.

Seo Carga Carga Mvel Envoltrias

Permanente mnimo mximo mnimo mximo

A 0 0 0 0 0

B -90 -105 0 -195 -90

C +180 -90 +195 +90 +375

D +270 -75 +255 +195 +525

E +180 -90 +195 +90 +375

F -90 -105 0 -195 -90

G 0 0 0 0 0

Envoltrias: Momentos Fletores [kNm]

mnimos

mximos carga permanente

faixa de trabalho

-195 -195-90 -90

90 90195

525

375 375

Figura 2.16 Envoltrias de momento fletor.



Conforme visto, para determinar os valores limites de esforos em uma

seo transversal precisa-se conhecer as posies de atuao do trem-tipo que

causam esses esforos limites. Para casos mais simples de trem-tipo e linhas de

influncia, como no exemplo acima, intuitiva a determinao dessas posies

limites. Porm, para casos mais complexos, torna-se impossvel essa

determinao por simples observao.

Esse problema de determinar posies limites constitui um problema de

otimizao, em que o objetivo minimizar e maximizar os valores dos esforos

nas sees transversais dos elementos estruturais em funo da posio de

atuao do trem-tipo. Porm, no existe uma funo matemtica que descreva a

envoltria de esforos de uma estrutura, o que torna impossvel o uso da maioria

dos mtodos clssicos de otimizao para resolver este problema, j que muitos

deles utilizam derivadas da funo objetivo, como ser visto no capitulo seguinte.


3 Mtodos de Otimizao

3.1. Introduo

Os problemas de otimizao so problemas de maximizao ou

minimizao de funo de uma ou mais variveis num determinado domnio,

sendo que, geralmente, existe um conjunto de restries nas variveis.

Os algoritmos usados para a soluo de um problema de otimizao

podem ser, basicamente, determinsticos ou probabilsticos.

Neste captulo so apresentadas as principais caractersticas desses

mtodos, apresentando suas vantagens e desvantagens. Sero abordados de

uma maneira mais detalhada os algoritmos de computao evolucionria, que

pertencem a uma famlia de mtodos probabilsticos de otimizao, visto que

este trabalho se baseou em um destes mtodos, conhecido como Estratgia

Evolutiva ( EE ).

Alguns trabalhos utilizando algoritmos de computao evolucionria vm

sendo desenvolvidos no Departamento de Engenharia Civil da PUC-Rio, dos

quais pode-se citar DEL SAVIO (2005), RAMIRES (2004) e BORGES(2003).

3.2. Definies

Para melhor entendimento dos algoritmos de otimizao, faz-se necessrio

o conhecimento de alguns conceitos e definies utilizados na literatura

(BASTOS, 2004). A seguir so listados alguns termos usualmente relacionados a

um problema de otimizao qualquer:

Variveis de projeto: So aquelas que se alteram durante o processo de

otimizao, podendo ser contnuas (reais), inteiras ou discretas.

Restries: So funes de igualdade ou desigualdade sobre as variveis

de projeto que descrevem situaes de projeto consideradas no

desejveis.


Mtodos de Otimizao

36

Espao de busca: o conjunto, espao ou regio que compreende as

solues possveis ou viveis sobre as variveis do projeto do problema a

ser otimizado, sendo delimitado pelas funes de restrio.

Funo Objetivo: a funo de uma ou mais variveis de projeto que se

quer otimizar, minimizando-a ou maximizando-a.

Ponto timo: o ponto formado pelas variveis de projeto que extremizam

a funo objetivo e satisfazem as restries.

Valor timo: o valor da funo objetivo no ponto timo.

3.3. Mtodos Determinsticos

Os mtodos de otimizao baseados nos algoritmos determinsticos

maioria dos mtodos clssicos geram uma seqncia determinstica de

possveis solues requerendo, na maioria das vezes, o uso de pelo menos a

primeira derivada da funo objetivo em relao s variveis de projeto.

Nestes mtodos, a funo objetivo e as restries so dadas como

funes matemticas e relaes funcionais. Alm disso, a funo objetivo deve

ser contnua e diferencivel no espao de busca (BASTOS, 2004). Esse tipo de

problema pode ser representado matematicamente da seguinte forma:


Mtodos de Otimizao

37

Maximizar / Minimizar: ),...,,( 21 nxxxf

Satisfazendo:

( ){ } 1211 ,...,, bxxxg n =

M

( ){ } mnm bxxxg =,...,, 21 em que:

nxxx ,...,, 21 - variveis de projeto

),...,,( 21 nxxxf - funo objetivo

mggg ,...,, 21 - restries

Figura 3.1 Formulao de um problema de otimizao.

Quando se trata de um problema de variveis discretas, considera-se um

espao de busca com variveis contnuas que, aps a otimizao, fornecero

uma aproximao das variveis de projeto para as disponveis no espao

discreto. Entretanto, isso gera um trabalho adicional na escolha das variveis

discretas mais prximas das contnuas encontradas. Sempre existiro duas

opes de variveis discretas para cada varivel contnua, ou seja, uma

imediatamente superior e outra imediatamente inferior.

Os mtodos determinsticos apresentam teoremas que lhes garantem a

convergncia para uma soluo tima que no necessariamente a soluo

tima global. Como nesses mtodos a soluo encontrada extremamente

dependente do ponto de partida fornecido, pode-se convergir para um timo

local, por isso no possuem bom desempenho em otimizar funes multimodais,

isto , funes que possuem vrios timos locais.

De acordo com OLIVIERI (2004), BASTOS (2004) e HAFTKA(1993), os

problemas de otimizao abordados pelos mtodos clssicos podem ser

classificados em duas classes, conforme as caractersticas da funo objetivo e

das restries:

Programao Linear: quando a funo objetivo e as restries so funes

lineares das variveis de projeto. O Mtodo Simplex (HADLEY, 1982) o

mtodo mais tradicional para solucionar este tipo de problema de

otimizao;


Mtodos de Otimizao

38

Programao No-Linear: quando a funo objetivo, ou pelo menos uma

das restries, uma funo no-linear das variveis de projeto. Nesta

classe, os mtodos que mais se destacam so:

Mtodo de Programao Linear Seqencial, Mtodo de Programao

Quadrtica Seqencial, Mtodo das Direes Viveis e Mtodo do

Gradiente Reduzido, entre outros.

3.4. Mtodos Probabilsticos

Os mtodos de otimizao baseados nos algoritmos probabilsticos usam

somente a avaliao da funo objetivo e introduzem no processo de otimizao

dados e parmetros estocsticos. Por no utilizarem a derivada da funo

objetivo, so considerados mtodos de ordem zero.

So listadas a seguir algumas vantagens dos algoritmos probabilsticos em

relao aos algoritmos determinsticos (BASTOS, 2004):

a funo objetivo e as restries no precisam necessariamente ter uma

representao matemtica;

no requerem que a funo objetivo seja contnua ou diferencivel;

trabalham adequadamente, tanto com parmetros contnuos quanto com

discretos, ou ainda com uma combinao deles;

no necessitam de formulaes complexas ou reformulaes para o

problema;

no h restrio alguma quanto ao ponto de partida dentro do espao de

busca da soluo;

realizam buscas simultneas no espao de possveis solues atravs de

uma populao de indivduos;

Otimizam um grande nmero de variveis, desde que a avaliao da

funo objetivo no tenha um custo computacional demasiadamente alto.

A maior desvantagem em relao aos mtodos clssicos o tempo de

processamento.

3.4.1. Computao Evolucionria

Segundo BCK et al.(1997), a Computao Evolucionria teve origem no

final da dcada de 50 e permaneceu relativamente desconhecida da comunidade


Mtodos de Otimizao

39

cientfica por aproximadamente trs dcadas, devido principalmente falta de

computadores eficientes na poca, mas tambm devido metodologia pouco

desenvolvida durante as primeiras pesquisas. Durante a dcada de setenta, os

trabalhos de Holland, Rechenberg, Shwefel e Foger foram fundamentais para

modificar a imagem da Computao Evolucionria que, a partir de ento,

comeou a ser largamente desenvolvida.

Os Algoritmos Evolucionrios ( sAE ' ) formam uma classe de mtodos de

otimizao probabilsticos que so inspirados por alguns princpios baseados em

mecanismos evolutivos encontrados na natureza, como auto-organizao e o

comportamento adaptativo (BEYER et al, 2002).

De acordo com BARBOSA (1997), um algoritmo evolucionrio se distingue

dos mtodos determinsticos mais comuns basicamente por:

empregar uma populao de indivduos, ou solues;

trabalhar sobre uma codificao das possveis solues (gentipos) e no

sobre as solues (fentipos) propriamente ditas;

empregar regras de transio probabilsticas;

no requerer informaes adicionais (derivadas, por exemplo) sobre a

funo a otimizar e as restries.

Assim, a busca de solues pode se dar em conjuntos no-convexos com

funes objetivo tambm no-convexas e no-diferenciveis podendo-se

trabalhar simultaneamente com variveis reais, lgicas e inteiras. Vale ressaltar

tambm que os sAE ' no so facilmente presos a mnimos locais como o

caso dos algoritmos usuais dos mtodos determinsticos. Ao utilizar um AE ,

essas caractersticas podem levar descoberta de solues no convencionais

que no poderiam ser vislumbradas por serem contra-intuitivas. um paradigma

que no exige conhecimento prvio de uma maneira de encontrar a soluo.

Para a utilizao de AE em problemas de otimizao com restries, uma

das possibilidade utilizar um mtodo de penalizao. Isso pode ser feito

atravs da pena de morte, onde um indivduo simplesmente eliminado da

populao quando violar as restries ou quando no for possvel avaliar sua

aptido*. Porm, possui a desvantagem de poder estar descartando um indivduo

potencialmente til ao processo evolutivo. Outra maneira seria introduzir uma

* Utilizou-se a palavra aptido como traduo da palavra fitness usualmente

adotada na literatura inglesa para se referir ao desempenho de um indivduo da

populao.


Mtodos de Otimizao

40

funo de penalizao para incorporar as restries funo objetivo, de

maneira anloga ao que se faz nos mtodos clssicos de otimizao, reduzindo

a aptido dos indivduos que violam as restries (BARBOSA, 1997).

Para ilustrar o comportamento de um AE , considera-se uma funo

objetivo unidimensional a ser maximizada. A Figura 3.2 mostra trs etapas da

busca evolucionria, mostrando como os indivduos so distribudos no comeo

(a), meio (b) e fim (c) do processo de evoluo. Na primeira fase, imediatamente

aps a inicializao da populao, os indivduos so aleatoriamente espalhados

em todo o espao de busca. Depois de algumas geraes a distribuio

modifica-se: devido aos operadores de variao e seleo, a populao

abandona as regies de baixa aptido e comea a ocupar reas de maior

aptido. No final da busca, tendo sido escolhida uma condio de parada

apropriada, toda a populao est concentrada em torno de poucos pontos,

onde alguns desses pontos podem ser sub-timos. Pode ocorrer de todos os

membros da populao se posicionarem em torno de um timo local ao invs de

um timo global. Essa convergncia prematura um efeito conhecido de perda

rpida de diversidade, que leva a populao a ficar presa a timos locais (EIBEN

& SMITH, 2003).

Figura 3.2 Evoluo tpica de um AE , ilustrada de acordo com a distribuio da populao. Adaptado de EIBEN & SMITH (2003).

Conforme CORTES & SAAVEDRA (2000), a Computao Evolucionria

tem sido utilizada com sucesso para resoluo de complexos problemas de

otimizao. Seu principal obstculo a preciso da soluo a ser encontrada,

pois o quanto mais prximo da soluo tima se deseja chegar, mais poder

computacional e tempo de processamento so exigidos, principalmente quando

so utilizadas funes multimodais.

Indivduos no domnio da

funo aptido

Fun

o a

ptid

o


funo aptido

Fun

o a

ptid

o


funo aptido

Fun

o a

ptid

o

(a) (b) (c)

Incio Meio Fim


Mtodos de Otimizao

41

3.4.1.1. Definies

Para a utilizao de um AE so necessrias algumas definies

adicionais que so particulares a esse tipo de algoritmo (BASTOS, 2004; EIBEN

& SMITH, 2003). Como a Computao Evolucionria baseada em mecanismos

evolutivos encontrados na natureza, muitos termos adotados pelos sAE '

baseiam-se na Gentica, tais como:

Cromossomo ou gentipo representa um indivduo no espao do AE , ou seja, representa um indivduo codificado;

Fentipo representa um indivduo no espao de busca original;

Indivduo um membro da populao;

Gene unidade bsica do cromossomo, ou seja, um elemento do vetor

que representa o cromossomo;

Populao conjunto de indivduos ou cromossomos;

Gerao ordem evolutiva das diferentes populaes;

Operaes genticas conjunto de operaes que o AE realiza sobre

cada um dos cromossomos;

Funo aptido quando o AE utilizado em um problema de otimizao, a funo aptido equivale funo objetivo.

3.4.1.2. Algoritmo Evolucionrio

A principal idia em que se baseia qualquer variao de um Algoritmo

Evolucionrio : dada uma populao de indivduos, a presso do meio ambiente

causa uma seleo natural que evolui a populao. Sendo assim, qualquer

algoritmo evolucionrio deve ter as seguintes componentes bsicas para

resolver um problema (MICHALEWICZ, 1996; EIBEN & SMITH, 2003;

BARBOSA, 1997; BCK et al, 1997):


Mtodos de Otimizao

42

Uma representao gentica das solues do problema;

A representao ou codificao de um indivduo quando se utiliza um AE

consiste em relacionar o espao real do problema com o espao adotado

pelo AE , ou seja, representar/codificar os elementos do espao real no espao do AE . Cada elemento do espao de busca denominado fentipo e sua representao no espao do AE denominado gentipo.

Para ilustrar esse processo, considere que em um problema de otimizao

bidimensional de nmeros inteiros que adote um AE com representao

binria, onde o alfabeto composto dos smbolos 0 e 1, { }21, xxx = seja uma possvel soluo do problema. Sendo o cromossomo codificado com

cinco bits para cada uma das variveis do problema, elas podem ser

representadas da seguinte maneira:

1x =00100

2x =10100

Essas codificaes seriam os genes que concatenados formam o

cromossomo, que representa uma possvel soluo do problema:

0010010100

Para recuperar os valores das variveis no espao real, ou seja, obter o

fentipo, necessrio um processo de descodificao:

1IND = 0x24 + 0x23 + 1x22 + 0x21 + 0x20 = 4

2IND = 1x24 + 0x23 + 1x22 + 0x21 + 0x20 = 20

Para um problema com variveis inteiras, o valor da varivel igual ao

prprio ndice fornecido pela codificao ( IND ). No caso de variveis

discretas, a decodificao fornece um ndice que localiza o valor da

varivel numa lista de referncia, que representa o espao de busca para

esta varivel (BASTOS, 2004).

Para as variveis contnuas, tem-se a seguinte decodificao:

12

+= nb

Li

Ui

iLii

xxINDxx (3.1)


Mtodos de Otimizao

43

Onde:

x - ponto de busca no espao.

Lx - limite inferior do espao de busca;

Ux - limite superior do espao de busca;

nb - nmero de bits;

IND -ndice fornecido pela decodificao da varivel;

i - nmero de variveis;

Segundo BASTOS (2004), a utilizao de codificao binria dada pelas

seguintes razes:

Extrema facilidade para criar e manipular vetores binrios;

Utiliza rigorosamente a preciso determinada para cada varivel;

Altamente indicada para se operar com variveis discretas.

Porm, quando o problema em anlise necessita que as variveis

envolvidas sejam de alta preciso numrica, a codificao binria possui

enorme desvantagem pois, neste caso, faz-se necessrio que os

cromossomos possuam um comprimento extremamente grande, reduzindo

a performance do AE . Outra desvantagem a necessidade constante de converso entre os valores reais e os binrios nas diversas iteraes do

processo.

Populao

O papel da populao manter as possveis solues. Enquanto os

indivduos so estticos, isto , no se modificam, a populao uma

unidade de evoluo. Dada uma representao, definir uma populao

equivale a decidir o nmero de indivduos que iro form-la. Em alguns

sAE' mais sofisticados a populao pode ter uma estrutura adicional, com

medidas de distncia ou relaes de vizinhana. Em quase todas as

aplicaes de AE o tamanho da populao constante, no sendo modificado durante a evoluo.

Uma maneira de inicializar a populao;

A inicializao da populao geralmente simples na maioria das

aplicaes de AE , e feita gerando indivduos aleatoriamente. Porm, algumas heursticas podem ser usadas para gerar uma populao inicial


Mtodos de Otimizao

44

com maior aptido, como, por exemplo, iniciar a populao com solues

aproximadas conhecidas ou contendo algum tipo de informao prvia. Se

isso vale o esforo computacional extra envolvido, depende muito da

aplicao.

Uma funo aptido

A funo aptido a responsvel pelo processo de seleo dos indivduos

e deve indicar a qualidade de cada indivduo na populao, sendo assim,

influi diretamente na evoluo da populao. Tecnicamente, uma funo

que designa uma medida de qualidade ao gentipo, ou seja, a aptido.

Operadores genticos

Os operadores genticos alteram a composio gentica dos filhos durante

a reproduo. O papel dos operadores criar novos indivduos a partir dos

antigos. Os operadores trabalham sobre a codificao das possveis

solues (gentipo) e no sobre as solues (fentipos) propriamente

ditas. Os principais operadores so recombinao e mutao.

A recombinao um operador que une informaes de dois ou mais

gentipos pais para gerar um ou dois descendentes. O operador de

recombinao estocstico, isto , aleatria a escolha de que partes de

cada pai ser recombinada e o modo que estas partes sero

recombinadas.

A mutao um operador que aps ser aplicado a um gentipo gera um

filho. Similar a recombinao, a mutao um operador sempre

estocstico: seu resultado o filho depende dos resultados de uma srie

de escolhas aleatrias.

Um mecanismo de seleo

O papel da seleo diferenciar os indivduos baseados nas suas

qualidades, em particular, permitir que os melhores indivduos tornem-se

pais da prxima gerao.

Um critrio de parada

Caso o problema tenha um valor timo da funo aptido conhecido, o

critrio de parada pode ser quando este valor for atingido, considerando

uma certa preciso. Porm, como sAE ' so estocsticos e no h

garantias de que o valor timo ser atingido, essa condio pode nunca


Mtodos de Otimizao

45

ser satisfeita e o algoritmo nunca parar. As opes comumente usadas

como critrio de parada so:

1. tempo mximo transcorrido;

2. o nmero total de avaliaes da funo aptido atingir um nmero

limite;

3. quando a aptido melhorar muito pouco durante um certo perodo de

tempo (ou um certo nmero de geraes ou um certo nmero de

avaliaes da funo aptido);

4. quando a diversidade da populao diminuir at um certo limite, sendo

diversidade uma medida do nmero de diferentes solues presente na

populao, que pode ser medido pelas diferentes aptides presentes na

populao ou pelo nmero de diferentes fentipos ou gentipos

presentes.

A partir do que foi visto acima, percebe-se que a combinao da aplicao

de variao, atravs dos operadores genticos, e seleo levam a melhorar o

valor da aptido e, em conseqncia, melhorar a populao. Pode-se perceber

essa evoluo como se fosse um processo de otimizao, atravs da busca de

valores timos, que, no decorrer do processo, ficam cada vez mais prximos.

Alternativamente, essa evoluo vista como um processo de adaptao.

Deste ponto de vista, a aptido no vista como uma funo objetivo a ser

otimizada, mas como uma necessidade do meio ambiente. O processo evolutivo

faz a populao adaptar-se ao meio ambiente cada vez melhor. A seguir

mostrado um pseudo-cdigo que representa um algoritmo evolucionrio.

Gerao = 0

Inicializa populao (P) ;

Avalia os indivduos;

Enquanto o critrio de parada no for satisfeito repita:

1. Recombinao

2. Mutao

3. Avaliao dos descendentes

4. Seleo

5. Gerao = Gerao +1

Figura 3.3 Esquema geral de um Algoritmo Evolucionrio. Adaptado de BCK et al

(1997).


Mtodos de Otimizao

46

Porm, para que a implementao de um algoritmo evolucionrio tenha

sucesso quando aplicado a um problema real, as componentes listadas acima

requerem algumas heursticas adicionais, que esto relacionadas

representao gentica das solues, aos operadores que alteram suas

composies, aos valores de vrios parmetros, aos mtodos de inicializao

da populao e at mesmo prpria funo aptido.

3.4.1.3. Principais Ramos da Computao Evolucionria

A Computao Evolucionria uma das reas da Inteligncia Artificial,

juntamente com as Redes Neurais e os Sistemas de Lgica Nebulosa (Figura

3.4). A maioria das implementaes de algoritmos evolucionrios vem de trs

ramos fortemente relacionados, porm independentemente desenvolvidos

(BEYER, 2002 e BCK et al, 1997):

Algoritmos Genticos ( sAG' );

Programao Evolutiva ( sPE ' );

Estratgias Evolutivas ( sEE ' ).

Alm dos ramos citados acima, alguns autores, com MICHALEWICZ

(1996), citam ainda a Programao Gentica ( sPG' ) como um importante ramo

da Computao Evolucionria.

Figura 3.4 Ramificao da Inteligncia Artificial. Adaptada de OLIVIERI (2004).

As principais diferenas entre esses ramos esto na representao dos

indivduos, nos operadores utilizados (mutao e/ou recombinao) e no

mecanismo de seleo, embora ultimamente a fronteira entre eles vem se

tornando menos ntida.


Mtodos de Otimizao

47

3.4.1.4. Algoritmos Genticos (AGs)

Segundo BARBOSA (1977) e BCK (1997), o AG foi desenvolvido

principalmente por John Holland no final da dcada de 60 buscando inspirao

no que se conhece sobre o processo de evoluo natural, conhecimento este

iniciado solidamente com a teoria da evoluo de Darwin no seu famoso livro A

Origem das Espcies.

Na maioria das aplicaes que utilizam sAG' , a forma mais comum de

construo de uma codificao utilizar uma cadeia binria, de comprimento

fixo. Isso ocorre porque a teoria dos sAG' foi desenvolvida com base nesta

representao, mas DAVIS (1991) acha que essa representao no natural e

desnecessria na maioria dos casos.

O principal operador a recombinao, tambm conhecido como

crossover na literatura inglesa, e a mutao vista como um operador de

pequena importncia. De forma simplificada, no alfabeto binrio, os operadores

funcionam da seguinte maneira:

A mutao definida pela modificao do smbolo ocorrente em uma

posio do cromossomo: se 1 ele passa a 0 e vice-versa. A probabilidade

mp de ocorrncia de mutao de um gene geralmente muito pequena,

da ordem de l/1 , onde l nmero de bits do cromossomo.

O crossover, no algoritmo padro, chamado crossover de um ponto.

Atravs de um esquema de seleo implementado, dois indivduos so

escolhidos e, com probabilidade pc, so submetidos operao de

recombinao. Uma posio de crossover sorteada e o material gentico

dos pais recombinado conforme o esquema abaixo:

p1 : 1111111 f1 : 1111000

p2: 0000000 f2 : 0000111

Existem outras variaes deste operador que podem ser empregadas,

como crossover de dois pontos, crossover uniforme, etc.

A seleo tipicamente implementada utilizando um esquema

probabilstico. A probabilidade ip de seleo do i -simo indivduo da

populao vir a ser selecionado proporcional sua aptido relativa,

conforme equao 3.2 (BCK et al, 1997;BARBOSA,1977).


Mtodos de Otimizao

48

=

= m

i

i

fi

fip

1

(3.2)

Onde )( ixffi = assumida positiva e m o nmero de indivduos da

populao.

Um mtodo que aplica essa tcnica o Mtodo da Roleta (roullete wheel

selection, na literatura inglesa), onde indivduos de uma gerao so

escolhidos para fazer parte da prxima gerao, atravs de um sorteio de

roleta. Os indivduos so representados na roleta proporcionalmente ao

seu ndice de aptido. Finalmente, a roleta girada um determinado

nmero de vezes, dependendo do tamanho da populao, e so

escolhidos como indivduos que participaro da prxima gerao, aqueles

sorteados na roleta (Figura 3.5).

Figura 3.5 Seleo utilizando o mtodo da roleta (Barbosa, 1977).

3.4.1.5. Programao Gentica (PG)

O paradigma da PG foi desenvolvido por John Koza (KOZA,1992).

Segundo MICHALEWICZ (1996), esta tcnica constitui uma maneira de fazer

uma busca no espao de possveis programas computacionais para escolher o

melhor deles, ou seja, uma tcnica de gerao automtica de programas de

computador, onde a partir de especificaes de comportamento, o computador

deve ser capaz de induzir um programa que as satisfaa (KOZA, 1992).

p1 p2 p3 p4


Mtodos de Otimizao

49

Conforme descrito por RODRIGUES (1992), a tcnica baseia-se na

combinao de idias da teoria da evoluo (seleo natural), gentica

(reproduo, cruzamento e mutao), inteligncia artificial (busca heurstica) e

teoria de compiladores (representao de programas como rvores sintticas).

Os programas so formados pela livre combinao de funes e terminais

adequados ao domnio do problema. Parte-se de dois conjuntos: F como sendo

o conjunto de funes e T como o conjunto de terminais. O conjunto F pode

conter operadores aritmticos (+, -, * etc), funes matemticas (seno, logaritmo

etc), operadores genticos (E, OU etc) dentre outros. Cada Ff tem

associada uma aridade (nmero de argumentos) superior a zero. O conjunto T

composto pelas variveis, constantes e funes de aridade zero (sem

argumentos).

O processo evolutivo ocorre a partir da aplicao dos operados genticos a

populao e pelo processo de seleo, que baseado na aptido dos

programas, at atingir um determinado critrio de parada.

Usualmente, para avaliar a aptido fornecido um conjunto de casos de

treinamento, contendo valores de entrada e sada a serem aprendidos. A cada

programa so fornecidos os valores de entrada e confronta-se a sua resposta ao

valor esperado de sada. A aptido ser proporcional proximidade da resposta

do programa ao valor de sada esperado. O operador de reproduo apenas

seleciona um programa e o copia para a prxima gerao sem sofrer nenhuma

mudana em sua estrutura. As Figuras 3.6 e 3.7 mostram a aplicao do

operador de recombinao (crossover) em duas funes selecionadas, que

partilham informao gentica e do origem a duas novas funes diferentes.

Figura 3.6 Crossover na PG : seleo aleatria dos ramos que sofrero o corte

(SOUSA & ANDRADE, 1998).


Mtodos de Otimizao

50

Figura 3.7 Crossover na PG : funes resultantes (SOUSA & ANDRADE, 1998).

A mutao nem sempre efetuada, pois depende de um valor que indica a

probabilidade de existir mutao numa determinada gerao. Quando

efetuada, uma funo escolhida aleatoriamente para sofrer mutao (Figura

3.8).

Figura 3.8 Aplicao do operador de mutao na PG (SOUSA & ANDRADE,

1998).

3.4.1.6. Programao Evolutiva (PE)

De acordo com BCK et al. (1997) e MICHALEWICZ (1996), a PE surgiu originalmente como uma tentativa de criar inteligncia artificial. O objetivo era

desenvolver mquinas de estado finitas (MEF) para prever eventos com base em

observaes anteriores. Uma MEF uma mquina abstrata que transforma uma

seqncia de dados de entrada em uma seqncia de dados de sada. A

transformao depende de certas regras de transio.

Os indivduos so usualmente representados por vetores de nmeros

reais. Geralmente cada genitor gera um filho. A mutao ocorre tipicamente com

probabilidade uniforme e originalmente implementada como uma mudana


Mtodos de Otimizao

51

randmica (ou atravs de mltiplas mudanas) da descrio das MEF de acordo

com cinco diferentes modificaes:

mudana de um dado de sada;

mudana de uma regra de transio;

incluso de uma regra de transio;

excluso de uma regra de transio;

mudana da regra de transio inicial.

No utilizada a recombinao.

O processo de seleo ocorre como uma srie de torneios entre sub-

grupos dentro da populao. Cada indivduo da populao avaliado contra t

(obrigatoriamente 1>t e usualmente 10t ) outros indivduos escolhidos

randomicamente da populao. Para cada comparao marcado um vencedor.

Permanecem na populao os indivduos que tiveram o maior nmero de

vitrias.

3.4.1.7. Estratgia Evolutiva (EE)

A primeira verso de sEE ' foi EE+ )11( , que empregava um esquema

simples de seleo-mutao trabalhando em um nico indivduo que gera um

nico descendente atravs da mutao Gaussiana e ambos so submetidos ao

processo de seleo, que elimina a soluo mais pobre. Mais tarde, esta teoria

evolui para EE+ )1( , no qual uma populao de indivduos se recombina

de maneira randmica para formar um descendente, que sofre mutao e em

seguida, passa pelo processo de seleo.

Nas verses descritas acima, a convergncia era lenta e a busca ponto a

ponto era susceptvel a estagnar em mnimos locais.

Mais tarde, visando sanar essas deficincias, desenvolveram-se outras

verses, utilizando a estratgia denominada multi-membros, onde o tamanho da

populao maior que um. Atualmente, os dois principais tipos so (COSTA &

OLIVEIRA, 2002; BEYER et al., 2002; BCK et al., 1997):

EE+ )(

Conhecida como estratgia soma, onde pais produzem filhos, sendo

> , gerando uma populao de + indivduos. Nesta estratgia, os


Mtodos de Otimizao

52

+ indivduos participam do processo de seleo, que determina os

indivduos que sero os pais da prxima gerao.

EE),(

Conhecida como estratgia vrgula, se difere da estratgia soma porque

apenas os filhos participam do processo de seleo. Assim, o perodo

de vida de cada indivduo limitado a apenas uma gerao. Segundo

CORTES & SAAVEDRA (2000), este tipo de estratgia tem bom

desempenho em problemas onde o ponto timo em funo do tempo, ou

onde a funo afetada por rudo.

Note tambm que ambas estratgias apresentadas so extremos da

estratgia mais geral EEk ),,( , onde k1 representa o nmero mximo

de geraes que um indivduo pode permanecer na populao.

Nas verses atuais, a descendncia obtida submetendo-se os indivduos

da gerao a dois operadores: cruzamento e mutao. O cruzamento feito de

forma aleatria e a mutao feita tipicamente atravs de uma perturbao

Gaussiana de mdia nula e desvio padro unitrio, porm outros tipos de

mutao so possveis. Aplica-se tambm a idia de auto-adaptao do

parmetro desvio padro ( ) durante o processo evolutivo, o que uma das

caractersticas chaves do sucesso das estratgias evolutivas.

3.4.1.7.1. Distribuio Normal

Para utilizar um algoritmo de sEE' necessrio conhecer uma maneira de

gerar variveis aleatrias segundo uma distribuio normal ou gaussiana.

O modelo probabilstico citado acima chamado Modelo Normal e suas

origens remontam a Gauss em seus trabalhos sobre erros de observaes

astronmicas, por volta de 1810, da o nome de distribuio Gaussiana para tal

modelo (BUSSAD & MORETTIN, 2004).

De uma maneira geral, diz-se que uma varivel aleatria (v.a.) tem

distribuio normal com mdia e varincia 2 , onde +

Mtodos de Otimizao

53

Podemos dizer que ),(~ 2 N .

A Figura 3.9 ilustra uma curva normal, determinada por valores particulares

de e .

Figura 3.9 Funo de densidade de probabilidade de uma v.a. normal com mdia e

desvio padro .

Quando 0= e 1= , temos uma distribuio padro ou reduzida.

H vrios mtodos para gerar v.a. normais, mas uma observao

importante que basta gerar uma v.a. normal padro, pois qualquer outra pode

ser obtida desta. De fato, gerado um valor 1z da v.a. )1,0(~ NZ , para gerar um

valor 1 de uma v.a. ),(~2 N basta usar a transformao;

11 .z += (3.4)

Um mtodo eficiente para gerar v.a. com distribuio normal o Mtodo de

Box-Mller (BUSSAD & MORETTIN, 2004). Nesse mtodo so geradas duas

v.a. normal padro 1z e 2z , independentes, e )1,0(N , a partir de duas v.a. com

distribuio uniforme em [0,1], 1u e 2u , como mostra as equaes 3.5 e 3.6

(BUSSAD & MORETTIN, 2004) :

)2cos(log2 211 uuz = (3.5)

)2(log2 212 usenuz = (3.6)

A Figura 3.10 mostra o resultado da gerao de nmeros aleatrios

usando a funo rand da biblioteca padro da linguagem C.

0 +

( )fd


Mtodos de Otimizao

54

0

0,1

0,2

0,3

0,4

0,5

0,6

0,7

0,8

0,9

1

0 200 400 600 800 1000

Figura 3.10 Nmeros gerados pela funo rand da biblioteca da linguagem C.

Na Figura 3.11 apresentado o resultado da gerao de nmeros

aleatrios com distribuio normal a partir da varivel aleatria uniforme gerada

pela funo rand da biblioteca da linguagem C.

-4

-3

-2

-1

0

1

2

3

4

0 100 200 300 400 500 600 700 800 900 1000

Figura 3.11 Nmeros gerados pela transformao da v.a. uniforme em v.a. normal.

Nmero de variveis

Var

ive

is a

leat

ria

s no

rmai

s

Nmero de variveis

Var

ive

is a

leat

ria

s no

rmai

s


Mtodos de Otimizao

55

3.4.1.7.2. Algoritmo Padro de EE

As componentes bsicas de um Algoritmo Evolucionrio quando aplicadas

a um algoritmo de sEE ' possuem caractersticas particulares, que esto

detalhadas a seguir (CORTES & SAAVEDRA, 2000; EIBEN & SMITH,2003 ):

Representao dos Indivduos

Nas sEE ' , cada indivduo representado por um par de vetores reais da

forma ( ),xv = , onde x representa um ponto de busca no espao, ou seja, o vetor das variveis da funo objetivo, e o vetor de desvio

padro associado.

Inicializao da populao

A inicializao da populao geralmente feita de maneira muito simples,

gerando aleatoriamente os indivduos. Porm, pode-se utilizar alguma

heurstica para iniciar a populao, tal como gerar indivduos que sejam

possveis solues do problema.

Recombinao dos pais at gerar descendentes.

H inmeras variaes desse operador. Quanto ao nmero de genitores

que participam da recombinao, ela pode ser chamada de recombinao

de multi-pais, onde mais de dois indivduos participam da gerao de

apenas um descendente, sendo (1 ), onde o nmero de

indivduos que iro participar da recombinao para gerar um

descendente. Normalmente, escolhe-se =2 ou = (recombinao

global). Quanto as diferentes maneiras de recombinar os genitores, pode-

se citar como exemplos tpicos a recombinao discreta e a recombinao

intermediria:

Recombinao discreta

Um descendente gerado a partir de dois ou mais genitores escolhidos

randomicamente na populao ancestral. As variveis que iro formar o

novo descendente so escolhidas randomicamente entre as variveis dos

genitores.


Mtodos de Otimizao

56

Para ilustrar esse processo mostrado um exemplo onde dois indivduos

da populao ancestral, ( )aaxa ,= e ( )bbxb ,= , so escolhidos randomicamente e recombinados para formar um descendente,

( )','' xv = . A recombinao feita gerando-se uma varivel aleatria u com distribuio uniforme no intervalo de [0,1], amostrada individualmente

para cada componente do vetor 'v .

u 0.5 iai xx ,

' =

u >0.5 ibi xx ,

' =

u 0.5 iai ,

' =

u >0.5 ibi ,

' =

Com i=1,...,n ; onde n o nmero de variveis da funo objetivo.

Recombinao Intermediria

A diferena da recombinao discreta que as variveis que iro formar o

novo indivduo so obtidas atravs da mdia aritmtica das variveis dos

pais ao invs de realizar uma escolha randomica das variveis. Sendo

assim, usando o mesmo exemplo mostrado acimo, as variveis do novo

descendente poderiam ser obtidas da seguinte

( ) 2/xxx i,bi,a'i +=

( ) 2/i,bi,a'i +=

As vantagens e desvantagens da recombinao para uma funo objetivo

em particular devem ser notadas durante o desenvolvimento, pois no h

uma recomendao generalizada para o uso deste operador.

Mutao do desvio padro e dos descendentes

Faz-se a mutao dos desvios padres e, em seguida, a mutao dos

descendentes seguindo as equaes 3.7 e 3.8 (BCK & HAMMEL, 1994;

BCK et al, 1997):

)),(N.),(N'.(exp. ii'i 1010 += (3.7)

),(Nxx 'ii'i 0+= (3.8)


Mtodos de Otimizao

57

onde:

i = 1,...,n; sendo n o nmero de variveis da funo objetivo;

N (0,1) representa um nmero Gaussiano com mdia zero e desvio

padro unitrio. Nota-se que esse nmero o mesmo para todos os

indivduos quando multiplicado pelo fator ' e, quando multiplicado por ,

deve ser obtido independentemente para cada valor de i. Os valores

sugeridos para os parmetros ' e so mostrados nas equaes 3.9 e

3.10, respectivamente.:

1)2(' = n (3.9)

1

2

= n (3.10)

Este esquema pode sofrer modificaes. Uma opo usar uma verso

simplificada, onde usado o mesmo desvio padro

Documents

Traçado automático de envoltórias de esforços em estruturas planas utilizando um algoritmo evolucionário