Estudo de algumas Estratégias da Evolução Diferencial

Natália Caixeta Rocha Universidade Federal de Uberlândia, Faculdade de Engenharia Mecânica.

Av. João Naves de Ávila 2121 – Campus Santa Mônica – CEP 38400-902, Uberlândia, MG.

E-mail: nataliacrocha@hotmail.com

Sezimária de Fátima Pereira Saramago Universidade Federal de Uberlândia, Faculdade de Matemática.

Av. João Naves de Ávila 2121 – Campus Santa Mônica – CEP 38400-902, Uberlândia, MG.

E-mail: saramago@ufu.br

Palavras-chave: Evolução diferencial, algoritmos evolutivos, estratégias de cruzamento,

otimização multi-objetivo.

Resumo: Este trabalho tem como objetivo testar e comparar as diferentes estratégias de

Evolução Diferencial (ED) aplicados a alguns problemas de otimização multi-objetivo. A

Evolução Diferencial é um algoritmo evolutivo simples e de rápida convergência que trabalha

com poucas variáveis de controle e pequenas populações. Assim como os algoritmos genéticos,

a ED também é baseada na seleção natural apresentando os operadores mutação, cruzamento

e seleção. O foco deste trabalho está no estudo das diferentes estratégias do operador

cruzamento e de sua influência nos resultados aplicados a alguns problemas práticos.

1 Introdução

O campo relacionado com problemas de otimização vem crescendo consideravelmente,

novos métodos surgem em busca de maior eficiência e menor custo operacional. A

complexidade dos problemas estudados podem resultar em modelos matemáticos de difícil

representação, com funções não-lineares, descontínuas, não diferenciáveis, multimodais (possui

muitos pontos de mínimo ou de máximo) e para estes deve-se procurar o método de otimização

que melhor se encaixe ao tipo do problema.

Os Algoritmos Evolutivos são métodos naturais ou estocásticos que utilizam apenas as

informações da função a ser otimizada, buscando o ótimo através de regras de probabilidade e

operando de maneira “aleatória orientada”, desvinculando-se das derivadas utilizadas nos

métodos determinísticos. Desta forma, estes métodos se aplicam bem aos mais complexos tipos

de problema. Para otimizações multi-objetivo, as funções objetivo podem ser escritas em uma

única função escalar através de técnicas como a Ponderação dos Objetivos ou Critério Global.

Problemas com restrições em suas variáveis de projeto podem ser tratados como problemas

irrestritos através de métodos como a Função de Penalidade Exterior.

A Evolução Diferencial (ED) é um algoritmo evolutivo baseado nos mecanismos de

seleção natural e na genética de populações, utilizando os operadores mutação, cruzamento e

seleção para gerar novos indivíduos em busca do mais adaptado. A idéia principal da mutação é

gerar novos indivíduos pela adição da diferença ponderada entre dois indivíduos da população a

um terceiro indivíduo, realizando em seguida um cruzamento. Por fim, uma seleção permite

escolher o melhor indivíduo que irá participar da próxima geração. A ED é eficaz mesmo

trabalhando com uma população pequena, funções descontínuas, multimodais e não-lineares, e

vem sendo muito utilizada devido a sua simplicidade, rápida convergência e precisão.

2 Evolução Diferencial

O algoritmo da Evolução Diferencial inicializa criando uma população inicial aleatória,

composta por indivíduos espalhados sobre o espaço de busca. Em seguida, a população é

modificada a cada iteração passando pelos três operadores da ED (mutação, cruzamento e

seleção) para chegar na próxima geração.

13

ISSN 2317-3300

Mutação: A população é modificada através da adição da diferença vetorial ponderada entre

dois indivíduos aleatórios da população a um terceiro indivíduo. São gerados então os vetores

doadores ou modificados. O processo de mutação pode ser escrito da seguinte forma:

(1)

Cruzamento: As componentes do indivíduo doador são misturadas com as componentes de um

indivíduo escolhido aleatoriamente (vetor alvo), resultando num vetor tentativa ou experimental.

As componentes do vetor experimental são escolhidas pela seguinte comparação:

i=1,2,...n (2)

Onde é um número gerado aleatoriamente com resultado no intervalo [0, 1]; são as

componentes do vetor alvo ; são as componentes do vetor doador ; CR é a probabilidade

do cruzamento ocorrer, representa a probabilidade do vetor experimental herdar os valores das

variáveis do vetor doador, e está compreendida entre 0 e 1, sendo fornecida pelo usuário. Este

tipo de cruzamento é denominado operador cruzamento binomial.

Outro tipo de cruzamento que será estudado é o operador cruzamento exponencial. Neste, o

cruzamento é realizado nas variáveis enquanto o número aleatório for menor que a

probabilidade de cruzamento . A primeira vez que este número aleatório ultrapassar o valor

de , nenhum cruzamento é executado e as variáveis restantes são deixadas intactas, ou seja:

Enquanto

; Se

j=(i+1),...n (3)

A partir do indivíduo obtido pelo cruzamento binomial, dois códigos computacionais

diferentes foram implementados em MATLAB® para o operador cruzamento exponencial,

denominados Código 1 e Código 2, conforme Fig.1. O Código 1 separa todas as variáveis do

vetor doador ( ) das variáveis do vetor alvo ( ). No Código 2, ao encontrar a primeira variável

que não seja do vetor doador, assume-se que todas as outras são do vetor alvo.

Figura 1 - Código 1 e Código 2 para o operador cruzamento exponencial em um indivíduo

Se após o cruzamento uma ou mais componentes do vetor experimental estiver fora da

região de busca, é necessário fazer uma correção no vetor enquadrando-o de volta a região

viável assumindo o valor mínimo ou máximo para cada variável fora do intervalo.

Seleção: Este operador realiza um teste sobre a população gerada. Se o custo do vetor

experimental for menor que o custo do vetor alvo, então o vetor experimental será escolhido

para a próxima geração. Caso contrário, o vetor alvo continua na próxima geração.

O procedimento é finalizado através de algum critério de parada, como o número máximo

de iterações ou o melhor ter encontrado um valor dentro de uma precisão pré-estabelecida.

3 Estratégias da Evolução Diferencial

As estratégias da evolução diferencial podem variar de acordo com o tipo de indivíduo a

ser modificado na formação do vetor doador, o número de indivíduos considerados para a

perturbação e tipo de cruzamento a ser utilizado, podendo ser escritas como: ED/a/b/c. Sendo

que a – especifica o vetor a ser perturbado, podendo ser “rand” (um vetor da população

escolhido aleatoriamente) ou “best” (o vetor de menor custo da população); b – determina o

número de diferenças ponderadas usadas para a perturbação de a; c – denota o tipo de

14

ISSN 2317-3300

cruzamento (exp: exponencial; bin: binomial). A partir destas convenções são definidas dez

estratégias diferentes para a Evolução Diferencial, como esquematizado na Tab.1.

Tabela 1: Representação das Estratégias da Evolução Diferencial

Número Mutação Notação

1 )( )()()()1( qq

p

qq XXFXV ED/rand/1/bin

2 )( )()()()1( qq

p

q

best

q XXFXV ED/best/1/bin

3 )()( )()()()()()1( qq

p

qq

p

qq XXFXXFXV ED/rand/2/bin

4 )()( )()()()()()1( qq

p

qq

p

q

best

q XXFXXFXV ED/best/2/bin

5 )()( )()()()()()1( qq

p

q

old

q

bestp

q

old

q XXFXXFXV ED/rand-to-best/2/bin

6 )( )()()()1( qq

p

qq XXFXV ED/rand/1/exp

7 )( )()()()1( qq

p

q

best

q XXFXV ED/best/1/exp

8 )()( )()()()()()1( qq

p

qq

p

qq XXFXXFXV ED/rand/2/exp

9 )()( )()()()()()1( qq

p

qq

p

q

best

q XXFXXFXV ED/best/2/exp

10 )()( )()()()()()1( qq

p

q

old

q

bestp

q

old

q XXFXXFXV ED/rand-to-best/2/exp

4 Aplicações

Foram feitas as simulações numéricas de três problemas aplicando todas as estratégias

apresentadas na Tab.1 para que possa ser feita uma comparação acerca das mesmas: Exemplo 1

- projeto de uma viga escalonada, Exemplo 2 - projeto do mastro de uma bandeira, Exemplo 3

- o problema da usinagem por descarga elétrica.

Assim, pode-se analisar quais as estratégias e qual algoritmo retorna a melhor solução para

tais problemas. Os parâmetros utilizados foram: número de indivíduos da população ,

taxa de perturbação , probabilidade de cruzamento . O número máximo de

iterações é 200.

5 Conclusões

As simulações numéricas foram aplicadas a três problemas têm como objetivo testar as dez

estratégias da Evolução Diferencial aplicadas a dois códigos computacionais diferentes em

busca dos melhores resultados. Para o Exemplo1 o Código 1 apresentou resultados confiáveis

somente para as três primeiras estratégias. Com o Código 2, apenas as estratégias 5, 9 e 10 não

apresentaram bons resultados. No Exemplo 2 observou-se que o Código 1 também só retornou

resultados satisfatórios para as três primeiras estratégias, enquanto o Código 2 só não obteve

sucesso com as estratégias 4, 5, 9 e 10. No Exemplo 3 todos os resultados para ambos os

códigos foram iguais. Também foi feita a análise gráfica dos resultados, confirmando a rápida

convergência da ED.

Portanto, nota-se a importância de se testar todas as dez estratégias para comparar os

resultados obtidos, pois uma estratégia pode ser boa para um problema, mas pode não ser para

outro.

Referências

[1] Oliveira, G.T.S., “Estudo e Aplicações da Evolução Diferencial”, Dissertação (Curso de

Pos Graduação Em Engenharia Mecânica) - Universidade Federal de Uberlândia, 2006.

[2] Storn, R. and Price, K., “Differential Evolution – A Simple and Efficient Heuristic for

Global Optimization over Continuous Spaces”, Journal of Global Optimization vol. 11, pp.

341-359, 1997.

15

ISSN 2317-3300