IA707 Profs. Leandro de Castro/Fernando Von Zuben/Romis …lboccato/topico_8_programacao... · 2016-09-22 · Os símbolos de entrada são ... à seqüência de símbolos observados

IA707 – Profs. Leandro de Castro/Fernando Von Zuben/Romis Attux/Levy Boccato

Tópico 8 – Programação Evolutiva (PE) 1

Programação Evolutiva

1 Introdução

L. FOGEL et al. (1966) propuseram a programação evolutiva como uma técnica de

simulação da evolução para desenvolver uma forma alternativa de inteligência

artificial.

O comportamento inteligente era visto como requerendo as seguintes habilidades:

Predizer um determinado ambiente, e

Responder apropriadamente a este ambiente tendo por base a predição feita.

O ambiente foi considerado de forma genérica como sendo descrito por uma

seqüência de símbolos tomados a partir de um alfabeto finito.

O problema evolutivo foi então definido como sendo a evolução de um algoritmo

que pudesse operar na seqüência de símbolos até então observada de tal forma a

produzir um símbolo de saída que maximizaria o desempenho do algoritmo em



relação ao próximo símbolo a ser apresentado, dada uma função custo bem

definida.

Máquinas de estado finito estabelecem uma representação apropriada a estes

propósitos.

2 Máquinas de Estados Finitos

Uma máquina de estados finitos (M) é uma estrutura de lógica matemática (BÄCK

et al., 2000a).

Uma máquina de estados finitos M é essencialmente um “programa

computacional”: ela representa uma seqüência de instruções a serem executadas,

cada qual dependendo de um estado atual da máquina e do estímulo atual.

Formalmente uma máquina de estados finitos pode ser descrita por uma 5-tupla

M = Q,,,s,o, onde Q é um conjunto finito de estados, é um conjunto finito de



símbolos de entrada, é um conjunto finito de símbolos de saída, s : Q Q é

a função do próximo estado, e o : Q é a função da próxima saída.

Qualquer 5-tupla de conjuntos e funções satisfazendo esta definição pode ser

interpretada como a descrição matemática de uma máquina que, dado um símbolo

de entrada x enquanto a máquina está no estado q, fornecerá como saída o símbolo

o(q,x) e mudará para o estado s(q,x).

A informação contida no estado atual da máquina é suficiente para descrever seu

comportamento em relação a uma dada entrada.

O conjunto de estados serve como uma espécie de memória da máquina.

Os correspondentes pares de símbolos de entrada-saída e transições para o

próximo estado de cada símbolo de entrada, tomados sobre cada estado,

especificam o comportamento de cada máquina de estados finitos dada uma

condição inicial.



2.1 Exemplo

Considere a máquina M de três estados apresentada abaixo.

B

C A

0/

1/

0/

1/

0/

1/

Figura 1: Máquina de estados finitos de três estados. Os símbolos de entrada são

mostrados à esquerda da barra “/” e os símbolos de saída à direita (FOGEL et al.,

1966).



O alfabeto de símbolos de entrada é composto por {0,1}, o alfabeto de símbolos

de saída é composto por {,,} (FOGEL, 2000).

A máquina de estados finitos transforma uma seqüência de símbolos de entrada

em uma seqüência de símbolos de saída – pode ser vista como um codificador de

símbolos (e.g., códigos convolucionais).

Assume-se que a máquina atua quando um símbolo de entrada é percebido e

responde antes que o próximo sinal de entrada seja apresentado.

3 As Primeiras Técnicas de PE

FOGEL et al. (1966) propuseram a programação evolutiva para operar com

máquinas de estados finitos da seguinte forma:

Uma população de máquinas de estados finitos era exposta ao ambiente, ou

seja, à seqüência de símbolos observados até o momento.



Como cada símbolo era apresentado a cada máquina-pai, o símbolo de saída

era observado (predito) e comparado ao próximo símbolo de entrada.

A qualidade desta predição era medida utilizando-se uma dada função de

custo (e.g., erro absoluto ou erro quadrático).

Após a última predição ter sido feita, uma função de custo (payoff) para cada

símbolo indicava o fitness de cada máquina.

Máquinas-“filhas” eram geradas aplicando uma mutação aleatória em cada

máquina-pai e cada pai produzia um único filho. Cinco tipos básicos de

mutação foram concebidos para uma máquina de estados finitos:

Mude um símbolo de saída;

Mude uma transição de estado;

Adicione um estado;

Elimine um estado existente; e

Mude o estado inicial.



Os filhos eram avaliados da mesma forma que os pais, e as máquinas com os

maiores valores de fitness eram selecionadas para compor a próxima geração.

Geralmente, a metade da quantidade total de máquinas (pais + filhos) era

selecionada de forma que o tamanho da população se mantivesse constante.

Este processo se repetia até que fosse requerida a predição de um (novo) símbolo.

O tipo de mutação é escolhido com base em uma distribuição de probabilidades

tipicamente uniforme.

A remoção de um estado e a mutação do estado inicial só são permitidas quando

existe mais de um estado inicial.

A quantidade de mutações também é escolhida de acordo com uma distribuição de

probabilidades (e.g., uma distribuição de Poisson), ou pode ser fixa a priori.

A seleção é similar à feita em uma estratégia evolutiva do tipo ( + )-EE.

Este procedimento possui certo grau de versatilidade:

A função custo pode ser arbitrariamente complexa e variante no tempo;



Não há nenhuma restrição quanto à utilização de uma medida clássica de erro

como, por exemplo, o erro quadrático médio;

A predição não precisa ser feita necessariamente um passo à frente; e

Ambientes multivariados podem ser tratados diretamente.

3.1 Alguns Experimentos Elementares

FOGEL et al. (1966) descreveram uma série de experimentos nos quais problemas

de predição cada vez mais complexos foram apresentados ao programa evolutivo.

Por exemplo, predição de seqüências cíclicas de múltiplos símbolos, predição

de seqüências contendo ruído, predição de seqüências geradas por outras

máquinas de estados finitos, seqüências não-estacionárias etc.

Em um exemplo, a capacidade de predizer se um número é “primo” foi testada.

Uma seqüência não-estacionária foi gerada classificando-se cada elemento de

uma seqüência de inteiros como sendo primo (símbolo 1) ou não (símbolo 0).



Assim, o ambiente consiste da seqüência 01101010001..., sendo que cada

símbolo indica se um dado número inteiro 1,2,3,4,5,6,7,8,9,10,11,... é primo

ou não.

Embora testar se um número é primo ou não possa ser feito de forma direta,

predizer se o próximo número inteiro será primo baseado na seqüência de

primos e não-primos observados não é trivial.

A função custo adotada para a predição foi do tipo tudo-ou-nada, ou seja, um

ponto para cada predição correta e nenhum ponto para cada erro, menos 0.01

vezes a quantidade de estados da máquina (para penalizar máquinas

excessivamente grandes).

Observação inicial: com frequência, a máquina “ótima” obtida possuía um único

estado, gerando como saída (para ambas as entradas) o símbolo 0. Como a

frequência relativa de números primos diminui, a tendência (assintótica) é que a

máquina atinja uma taxa de acerto cada vez maior.



Após alguns sucessos limitados com esta abordagem, o objetivo foi alterado tal

que uma predição correta de um primo resultasse em um valor “1” mais a

quantidade de primos precedentes.

Ou seja, a função de avaliação foi alterada.

FOGEL et al. (1966) indicaram que as máquinas tinham a capacidade de

rapidamente reconhecer que números divisíveis por 2 e 3 não são primos, e que

havia indicativos de que números divisíveis por 5 também não seriam primos.

Portanto, as máquinas geraram algumas evidências de aprendizagem da definição

do que é ser um número primo sem nenhum conhecimento antecipado da natureza

explícita de um número primo.

As aplicações da PE clássica se estenderam também para a teoria de jogos (FOGEL

& BURGIN, 1969), controle (WALSH et al., 1970), classificação (DEARHOLT, 1976),

e muitas outras áreas.



Muitas extensões da formulação de máquinas de estados finitos, proposta por

FOGEL et al. (1966), foram sugeridas com o objetivo de aplicar a PE a problemas

de otimização contínua (funções de valores reais). Três destas variações

importantes podem ser descritas como a seguir (BÄCK et al., 2000a):

PE original: PE onde o processo evolutivo (de busca) não envolve auto-

adaptação;

PE contínua: onde novos indivíduos são inseridos diretamente na população

durante uma geração (ou seja, um indivíduo passa a fazer parte da população

sem precisar esperar a conclusão de uma geração); e

Meta-PE: inclui o vetor de parâmetros na codificação de um indivíduo.

Na próxima seção discutiremos a PE original e a meta-PE para otimização de

funções contínuas.



4 Otimização de Funções Contínuas: meta-PE

A programação evolutiva foi estendida por D. B. FOGEL (1992) para operar com

vetores reais de atributos sujeitos a mutações com distribuição normal.

Os conceitos gerais e a notação apresentados para as estratégias evolutivas são

adequados para a programação evolutiva. Conceitos:

Auto-adaptação;

Vetor e espaço de atributos e de parâmetros;

Genótipo e fenótipo.

4.1 Representação e Avaliação do Fitness

Na proposta inicial de aplicação da PE para otimização de funções de valores

reais, os indivíduos da população são representados por vetores reais, v = x l.

Entretanto, FOGEL (1992) introduziu o conceito de meta-PE (meta-programação

evolutiva), que é essencialmente idêntica ao processo de auto-adaptação dos

desvios padrões nas estratégias evolutivas (BÄCK, 1994).



É importante mencionar que o conceito de meta-evolução é atualmente

utilizado para descrever aqueles algoritmos que permitem a evolução dos

operadores genéticos, parâmetros do algoritmos etc. juntamente com a

estrutura de dados.

Na PE, um indivíduo da população é representado por v = (x,var), onde x l,

var lvar, l é a dimensão de x, lvar {1,...,l}.

Ou seja, a meta-PE utiliza a variância var = 2, em vez do desvio padrão,

para atualizar o vetor de atributos.

Além disso, a variância também irá sofrer mutação.

Em uma terceira abordagem, chamada Rmeta-PE, FOGEL (1992, pp. 287-289)

também incorpora um vetor de coeficientes de correlação que irão sofrer auto-

adaptação.

Este mecanismo é essencialmente idêntico às mutações correlacionadas das

estratégias evolutivas.



Entretanto, a abordagem Rmeta-PE foi implementada e testada por Fogel em

uma quantidade restrita de problemas bi-dimensionais.

Como no caso das estratégias evolutivas, faz-se necessária a aplicação de um

método que garanta a determinação de uma matriz de correlação que seja

simétrica e semi-definida positiva.

Assim como no caso dos algoritmos genéticos, o valor do fitness é obtido através

de um escalonamento do valor da função objetivo.

A discussão a ser apresentada aqui se restringirá ao caso da meta-PE.

A inicialização na meta-PE é feita amostrando-se uma distribuição uniforme com

domínio pré-definido para o vetor de atributos e de variâncias.

4.2 Mutação

No caso padrão de programação evolutiva, um operador Gaussiano de mutação

com desvio padrão independente para cada componente xi de x é obtido a partir da



raiz quadrada de uma transformação linear aplicada ao valor de fitness do vetor x,

ou seja (BÄCK & SCHWEFEL, 1993):

xit+1= xi

t + i.N i(0,1)

iii fit )(. x

onde os parâmetros i e i devem ser ajustados de acordo com o problema a ser

tratado.

Para resolver os problemas de ajuste desta abordagem, a meta-PE auto-adapta l

variâncias por indivíduo de forma similar às estratégias evolutivas:

xit+1= xi

t + t

ivar .Ni(0,1)

varit+1= vari

t + t

ivarα. .Ni(0,1)

onde denota um parâmetro que garante que vari seja não-negativa, e Ni(0,1)

indica que a variável aleatória é amostrada de forma independente para cada i.



FOGEL (1992) propôs a regra simples vari 0, vari , onde é um valor

próximo de zero, mas é não-nulo.

Embora essa idéia seja semelhante à utilizada pelas estratégias evolutivas, a

metodologia estocástica por trás da meta-PE é fundamentalmente diferente (BÄCK,

1994).

4.3 Recombinação

Não existe recombinação em programação evolutiva.

4.4 Seleção

O mecanismo de seleção utilizado em programação evolutiva é similar à seleção

por torneio em algoritmos genéticos.



Seleção por torneio em GA

Na seleção por torneio, um grupo de q indivíduos é aleatoriamente selecionado,

com ou sem substituição, da população. Este grupo passa a fazer parte de um

torneio, de modo que um indivíduo vencedor é determinado dependendo do seu

valor de fitness em relação a seus competidores.

O melhor indivíduo (aquele possuindo o maior fitness) é geralmente

escolhido de forma determinística ou estocástica. Somente este indivíduo é

colocado na população.

O processo é repetido vezes até que uma nova população seja gerada.

Geralmente os torneios são feitos entre 2 indivíduos, num processo conhecido

como torneio binário.

Um torneio entre q indivíduos é chamado de q-torneio (q-tournament).



Seleção por torneio em PE

Após criar filhos a partir de pais através da mutação de cada pai, uma variação

da seleção estocástica por torneio seleciona indivíduos dentre pais e filhos.

Ou seja, trata-se de uma seleção ( + ) estocástica.

Para cada indivíduo vi P(t) P’(t), onde P(t) denota a população de pais na

geração t, e P’(t) a população de filhos (indivíduos mutados) na mesma geração t,

q indivíduos são selecionados aleatoriamente de P(t) P’(t) e comparados a vi em

relação a seus valores de fitness.

Dado vi, contam-se quantos indivíduos possuem fitness menores que o dele,

resultando em um score wi (i {1,...,2}), e os indivíduos com maior score

wi são selecionados para formar a próxima população.

Formalmente tem-se:

q

j

i

i

fitfitw

1

j

casos outros0

)()( se1 vv,



onde j {1,...,2} é uma variável aleatória inteira e uniforme amostrada para

cada comparação.

Quando o tamanho do torneio q é aumentado, o mecanismo torna-se cada vez

mais determinístico.

Como o melhor indivíduo irá receber o maior score q, a sobrevivência do melhor

indivíduo é garantida e, portanto, o mecanismo de seleção é elitista.

Em resumo, um algoritmo do tipo meta-PE pode ser implementado empregando-

se a seguinte seqüência de passos:

procedimento [P] = meta-PE()

inicialize indivíduos do tipo: v = (x,) e os armazene em P

avalie todos os indivíduos

t 1

enquanto NOT condição_de_parada, faça

mute os indivíduos de P e armazene em P’

avalie os indivíduos gerados em P’ (filhos)

selecione indivíduos de PP’ por torneio estocástico

t t + 1

fim enquanto

fim procedimento



5 Discussão

Tanto no caso das EEs quanto da PE aplicadas ao processo de otimização de

funções numéricas reais, o espaço de busca é geralmente irrestrito; restrições são

tipicamente consideradas na geração da população inicial de indivíduos.

Entretanto a otimização de problemas com restrições pode ser feita impondo-se as

seguintes condições (BÄCK et al., 2000a):

O operador de mutação deve ser formulado tal que apenas soluções factíveis

sejam produzidas; ou

Uma função de penalização deve ser aplicada às mutações que resultam em

indivíduos infactíveis, tal que eles não façam parte da próxima geração.

5.1 Abordagem Top-Down Bottom-Up

As estratégias evolutivas, assim como a programação evolutiva, possuem uma

proposta filosófica diferente da de outras abordagens de computação evolutiva.



Enquanto as EEs e a PE são vistas como abordagens top-down, os algoritmos

genéticos e a PG são considerados do tipo bottom-up.

Esta discussão tem sido apresentada por diversos autores, como FOGEL (1994a) e

BÄCK et al. (2000a).

A proposta de Fogel se baseava na ideia de utilizar evolução para criar

“organismos” cada vez mais “inteligentes” ao longo do tempo.

Assim como as estratégias evolutivas, a programação evolutiva emprega a

abstração da teoria da evolução como um processo top-down de simulação de

comportamentos adaptativos (evolução dos fenótipos) ao invés de um

processo bottom-up de genética adaptativa (FOGEL, 1994a). Existe uma

relação funcional entre cada pai e seu filho, e não uma relação genética.



Abordagens Top-Down

O projeto ótimo de um sistema populacional é provavelmente conseqüência de um

conjunto de componentes que interagem fortemente.

A evolução natural projeta tais sistemas sem aplicar o processo de otimização a

componentes individuais; a seleção ocorre de forma top-down (FOGEL, 1994a).

Para sobreviver, cada organismo deve ser capaz de enfrentar as dificuldades

oferecidas pelo ambiente: encontrar comida suficiente, evitar os predadores,

encontrar abrigo etc.

A medida de seu sucesso é dada pela adequação do seu comportamento

global, e não de seus componentes individuais. Somente a sua resposta

comportamental possui valor seletivo, independentemente de como ela foi

gerada.

Os caracteres que condicionam o comportamento expresso afetam o valor seletivo

do indivíduo apenas em relação ao ambiente em que ele se encontra. Por exemplo,



é vantajoso ser alto quando se é jogador de basquete, mas essa característica pode

ser ruim caso você deseje ser um piloto de aeronaves de guerra.

MAYR (1989) coloca da seguinte forma: “Os genes não são as unidades da

evolução e nem são os alvos da seleção natural”.

As populações de organismos evoluem, não os componentes de cada organismo.

Sendo assim, FOGEL (1994a) sugere que é mais apropriado modelar a evolução

com o objetivo de projetar sistemas para a solução de problemas quando este

modelo otimiza o comportamento global do sistema.

Abordagens Bottom-Up

Como discutido anteriormente, os algoritmos genéticos enfocam a simulação da

evolução primariamente em termos dos mecanismos genéticos. A abordagem é do

tipo bottom-up.



A sugestão dos GAs é de que as soluções candidatas sejam codificadas utilizando-

se, geralmente, uma cadeia binária (que simula genes em um cromossomo), e, em

seguida, que sejam criadas novas soluções a partir da recombinação e mutação de

soluções existentes.

Os GAs estão fundamentados na teoria de que a recombinação e mutação vão

atuar de forma a combinar blocos construtivos de genes importantes pertencentes

a cadeias binárias individuais, e, assim, produzirão indivíduos melhores.

O argumento de FOGEL (1994a) é de que a restrição a uma representação e a

definição de uma forma de recombinação e variação genética são regras

heurísticas que podem ou não ser benéficas.

É possível afirmar que soluções ótimas podem ser encontradas através da

justaposição repetida de sub-seções sub-ótimas de soluções completas?



Se o objetivo é gerar “inteligência artificial”, ou seja, resolver problemas de

formas alternativas, então a utilização de um conjunto de regras é

inapropriado.

As regras utilizadas na resolução de um problema devem evoluir através de

um processo iterativo de mutação e seleção. Até mesmo a mutação deve

evoluir durante o processo.

Em um algoritmo genético, a teoria dos esquemas propõe que aqueles blocos

construtivos com fitness acima da média sofrem crescimento exponencial.

Entretanto, argumenta FOGEL (1994a), é impróprio atribuir um fitness a

componentes individuais (genes ou blocos de genes); vistos isoladamente eles não

possuem valor algum. Por exemplo, qual a utilidade de uma carta de baralho

individual em sua mão?



O Argumento Conclusivo de FOGEL (1994a)

Boa parte da ciência é tradicionalmente bottom-up, ou seja, uma análise é iniciada

enfocando-se os componentes, procedimentos e regras disponíveis em vez de

tentarmos entender adequadamente o propósito a ser atingido.

Entretanto, é preciso reconhecer que, para ser significativo, o propósito deve

indicar não apenas o resultado desejado, mas também a significância relativa dos

indivíduos. Na natureza, os organismos não são projetados pela combinação de

componentes otimizados individualmente, eles servem como hipóteses

representativas das propriedades lógicas do ambiente que eles habitam.

A seleção opera apenas na expressão fenotípica do genótipo; o código implícito do

fenótipo (genótipo) é afetado apenas indiretamente.

Nas EEs e PE, um indivíduo é avaliado apenas pelo seu fitness; não há nenhuma

tentativa de atribuir fitness a componentes (blocos construtivos) de um indivíduo.



Os operadores genéticos permitem a variação simultânea de todos os atributos dos

vetores.

5.2 EEs, PE e GAs

Além de uma comparação filosófica entre EEs, PE e GAs, como apresentado

acima, diversos autores têm comparado esses algoritmos em relação aos

operadores de seleção, recombinação, mutação, e desempenho quando aplicados a

problemas de teste e mundo real (FOGEL, 1994b; BÄCK, 1994; BÄCK &

SCHWEFEL, 1993).

Além das similaridades e diferenças entre GA, EE, PE e PG destacadas em tópicos

anteriores, é possível traçar as relações entre estas diversas abordagens em relação

ao mapeamento entre a visão computacional e a visão biológica dos diferentes

procedimentos.



Em resumo (Adaptado de BÄCK, 1994):

AG EE PE PG

Gene Cada bit ou

segmento de bits Cada xi, i, i Cada xi, i Cada função e

terminal

Cromossomo Cadeia binária

completa

Vetores completos

x, ,

Vetores

completos x,

Cada programa

Genótipo Coleção de cadeias

binárias

Coleção de

cromossomos: (x,

, )

Coleção de

cromossomos: (x,

)

Coleção de

programas

Fenótipo Valor decodificado

de x

Componente x Componente x Valor retornado

pelo programa



6 Exemplos de Aplicações

Referências: RECHENBERG, 1994; FOGEL, 1993a, 1993b.

6.1 Caixeiro Viajante

Codificação: permutações.

O espírito de um operador de mutação em PE requer: (1) a manutenção de uma

conexão comportamental entre cada pai e seus descendentes, e (2) uma

perspectiva “contínua” de surgimento de novos comportamentos.

Por isso, a proposta de FOGEL (1993a) foi um operador de inversão: selecione

duas cidades no percurso e reverta a ordem do trecho definido entre estas cidades.

Seleção: competição estocástica, levando em conta a distância Euclidiana total

associada a cada percurso.



Após 4 × 107 avaliações, uma solução a 5% do comprimento ótimo foi encontrada.

6.2 Evolução de Uma Lente Ocular

Os céticos em relação à teoria Darwiniana geralmente apontam para o problema

da evolução do olho: “5% de um olho” não pode funcionar como um olho, e,

portanto, não é possível haver evolução se não existe um olho de pior qualidade.



Figura 2: O olho humano.

Entretanto, a evolução do olho procedeu em vários passos pequenos, onde uma

possível seqüência lógica seria:



o Concentração das células sensitivas a luz;

o Identação da camada de pigmentos;

o Cobertura da identação com uma geléia;

o Formação da geléia em um concentrador de luz.

Possíveis passos evolutivos seriam:

o Olho plano;

o Olho em forma de taça;

o Olho com uma pequena depressão (identação); e

o Olho em forma de lente.

Seja o caso apenas do concentrador de luz ocular. A Figura 2 apresenta uma

película deformável de vidro com espessura dk (k = 1,...,n).



Os raios de um feixe paralelo de luz atravessam a lente de vidro e sofrem difração

em diferentes direções.

Um ajuste apropriado da espessura dk permite focalizar todos os raios em um

ponto P (propriedade de uma lente coletora).

o Essa medida de qualidade pode ser calculada somando-se os quadrados dos

desvios dos raios de luz. Sendo assim, o objetivo torna-se:

Distribuição dos raios = min qk2, onde qk é a distância do raio k ao ponto P.

Um organismo cujo olho é capaz de concentrar melhor os raios de luz pode

enxergar presas e/ou predadores mais rapidamente.

Na formulação matemática do problema, uma lâmina de vidro foi utilizada, e

permitiu-se variar a espessura desta lâmina em posições eqüidistantes.

A figura abaixo mostra a evolução da lâmina de vidro para uma “lente ocular”.





6.3 Evolução de Um Conjunto Articulado em um Túnel de Vento

De acordo com a figura abaixo, 6 placas foram conectadas em seus eixos

longitudinais. As juntas podem ser ajustadas individualmente em intervalos

angulares de 2o, cada junta permitindo 51 passos.

o Sendo assim, todo o conjunto permite 515 diferentes configurações.

Inicialmente o conjunto estava dobrado de forma irregular.

O objetivo é o de encontrar uma configuração com menor coeficiente de arrasto

quando colocado em um túnel de vento. A solução é trivial e conhecida.



O experimento foi conduzido da seguinte forma:

o Calcule o coeficiente de arrasto da configuração pai;

o Efetue pequenas mutações aleatórias nos ângulos;

o Calcule o coeficiente de arrasto da configuração mutada;

o Selecione a configuração com menor arrasto.

Este experimento, apesar de parecer elementar, foi crucial para o sucesso das EEs.



6.4 Projeto Evolutivo de Uma Ponte Articulada

Dada uma estrutura similar a uma ponte sobre um pavimento horizontal, uma

carga constante é aplicada ao longo da estrutura.

Problema: determine as coordenadas x e y dos 10 nós superiores e dos 11 nós

inferiores da ponte, tal que o peso da estrutura seja mínimo.

Para posições específicas dos nós, as forças nos elementos da estrutura podem ser

calculadas diretamente utilizando-se condições de equilíbrio estático.

o O peso da estrutura é função da espessura do material a ser utilizado (barras).

A figura abaixo mostra a evolução da EE quando aplicada a este problema.

o O peso inicial da estrutura é de 51 964 Kg, enquanto a estrutura otimizada

possui um peso de somente 17 129 Kg.





7 Referências

BÄCK, T., FOGEL, D.B. & MICHALEWICZ, Z. (eds.) “Evolutionary Computation 1: Basic Algorithms and Operators”,

Institute of Physics Publishing, 2000a.

BÄCK, T., FOGEL, D.B. & MICHALEWICZ, Z. (eds.) “Evolutionary Computation 2: Advanced Algorithms and

Operators”, Institute of Physics Publishing, 2000b.

BÄCK, T. & SCHWEFEL, H.-P (1993), “An Overview of Evolutionary Algorithms for Parameter Optimization”,

Evolutionary Computation, 1(1), pp. 1-23.

BÄCK, T., “Evolutionary Algorithms: Comparison of Approaches”, in R. Paton (ed.) Computing with Biological

Metaphors, Chapman & Hall, Capítulo 14, pp. 227-243, 1994.

DEARHOLT, D. W. (1976), “Some Experiments on Generalization Using Evolving Automata”, In Proc. 9th

Int. Conf.

on Systems Sciences, Honolulu, HI, pp. 131-133.

FOGEL, D. B. Evolutionary Computation – Toward a New Philosophy of Machine Intelligence, 2a edição, IEEE Press,

2000.

FOGEL, L. J. (1993a), “Applying Evolutionary Programming to Selected Traveling Salesman Problems”, Cybernetics

and Systems, vol. 24, pp. 27-36.

FOGEL, L. J. (1993b), “Empirical Estimation of the Computation Required to Discover Approximate Solutions to the

Traveling Salesman Problem Using Evolutionary Programming”, Proceedings of the Second Annual

Conference on Evolutionary Programming, pp. 56-61.



FOGEL, L. J. (1994a), “Evolutionary Programming in Perspective: The Top-Down View”, In J. M. Zurada, Marks II,

R. J. and Robinson, C. J., Computational Intelligence Imitating Life, IEEE Press.

FOGEL, D. B. (1994b), What’s Evolutionary Programming, [On line] http://www.kanadas.com/whats-ep.html.

FOGEL, D. B. (1992), Evolving Artificial Intelligence, Doctoral Dissertation, UCSD.

FOGEL, L. J., BURGIN, G. H. (1969), “Competitive Goal Seeking through Evolutionary Programming”, Air Force

Cambridge Research Laboratories Final report Contract AF19(628)-5927..

FOGEL, L.J., OWENS, A.J. & WALSH, M.J. (1966) “Artificial Intelligence through Simulated Evolution”. John Wiley.

MAYR, E. (1989), Toward a New Philosophy of Biology: Observations of an Evolutionist, Belknap, Harvard, MA.

RECHENBERG, I. (1994), “Evolution Strategy”, In J. M. Zurada, R. J. Marks II, and C. J. Robinson Computational

Intelligence Imitating Life, pp. 147-159.

WALSH, M. J., BURGIN, G. H. AND FOGEL, L. J. (1970), “Prediction and Control through the Use of Automata and

their Evolution”, US Navy Final Report Contract N00014-66-C0234.

Documents

IA707 Profs. Leandro de Castro/Fernando Von Zuben/Romis …lboccato/topico_8_programacao... · 2016-09-22 · Os símbolos de entrada são ... à seqüência de símbolos observados