1

Capítulo 1_________________________________Introdução

A procura por soluções ótimas para determinados problemas é objeto de

estudo há vários séculos. Podemos citar o antigo problema de se encontrar qual a

maior área que pode ser cercada por uma quantidade (em metros) de cerca,

chamado de problema isoperimétrico ou Problema da Princesa Dido. Na obra

Eneida de Vigílio, encontramos uma referência a este problema: "No século IX

antes de Cristo, a princesa fenícia Dido, que havia assassinado seu marido,

chegou às terras do norte da África (Tunez) junto com seu irmão Pigmalião e

fizeram um acordo com seus habitantes. Ao querer a princesa Dido comprar terra

para se estabelecer com seu povo, o rei daquele lugar somente lhe permitiu

comprar a parcela de terra que poderia ser coberta pela pele de um touro. Dido

cortou a pele em pequenas tiras formando uma larga corda (de 1000 a 2000

metros) e a dispôs de maneira que cobrisse a maior parte de terreno possível..." .

A área que a princesa cercou tinha o formato de um círculo. Apenas em 1870 foi

apresentada uma solução completa para o problema. Foi o matemático K.

Weirstrass quem apresentou a solução baseada em uma teoria criada por ele. A

teoria criada por Weierstrass é foi o Cálculo Variacional. Existem diversas

demonstrações para este resultado. Podemos citar por exemplo MOREIRA and

SALDANHA (1993) e FIGUEIREDO (1989). Outro problema antigo e bastante

interessante que também envolve otimização é o chamado Problema da

Braquistócrona. Esta palavra vem do grego brakhisto (o mais curto) e chronos

(tempo). O problema consiste em encontrar qual a trajetória que uma partícula

deve percorrer com o menor tempo onde os pontos de saída e chegada são fixos,

a velocidade inicial é nula, sem atrito e sujeita apenas a ação da gravidade.

Na natureza podemos observar diversas soluções ótimas para problemas

envolvendo, por exemplo, procura de alimentos por formigas, construção dos

alvéolos onde as abelhas depositam o mel, formação na migração de pássaros,

entre outras. Na busca por alimento, as formigas buscam o caminho mais curto e

2

com a maior quantidade de ferormônio depositado no caminho por outras

formigas; na construção dos alvéolos as abelhas buscam minimizar a quantidade

de material gasta na construção e ao mesmo tempo maximizar a produção e no

fenômeno da migração, as aves buscam uma formação que reduza o esforço de

aves que se encontram atrás de outras na formação. Há um rodízio das aves na

formação para garantir que aves mais cansadas estejam em uma posição

privilegiada na formação.

A otimização é uma ferramenta importante na tomada de decisões durante

a análise e/ou projeto de um determinado sistema físico. Para utilizar esta

ferramenta devemos ter em mente qual o objetivo a ser alcançado, ou seja, a

quantidade que medirá a eficiência deste sistema. Podemos querer minimizar

custos, tempo, material, energia ou maximizar lucro, volume, força. O objetivo

depende de características do projeto. Para cada parâmetro envolvido no sistema

ou projeto, cria-se uma variável que representará este parâmetro. Estas variáveis

são chamadas de Variáveis de Projeto ou Variáveis de Decisão. A otimização

visa encontrar o valor de cada variável que otimiza o sistema. Frequentemente

estas variáveis estão sujeitas a restrições, que são limites impostos pelo projeto e

que os parâmetros (variáveis) devem obedecer. As restrições podem ser de

igualdade, desigualdade e/ou laterais.

Uma restrição de desigualdade é chamada de Restrição Ativa se no ponto

ótimo x¿ vale a igualdade, isto é, se g j ( x¿)=0 , j=1 ,…,k (MARTINEZ and SANTOS,

1995), caso contrário é dita inativa. A figura 1 ilustra um exemplo onde para j=1e

j=2 as restrições são ativas e para j=3 a restrição é inativa.

Figura 1.1 – Restrições Ativas e Inativas

3

Em geral um problema de otimização com um objetivo pode ser escrito da

seguinte forma

Minimizar f ( x ) , x∈Rn (1)

Sujeito a {h l ( x )=0 , l=1 ,…,nrestreqg j ( x )≤0 , j=1 ,…,nrestneqx iinf ≤ x i≤ x i

¿ , i=1 ,…n (2)

A função f (x) é chamada de função objetivo. As funções hl(x ) e g j(x) são

as restrições de igualdade e de desigualdade respectivamente. O variável x é um

vetor de n coordenadas, isto é, x=(x1 , x2, ... , xn) e x iinf e x i

¿ são os limites inferior e

superior respectivamente, da i-ésima coordenada do vetor x.

Caso o problema seja o de encontrar o máximo para a função objetivo f (x),

basta multiplicar a função por -1 e transformá-lo em um problema de minimização

da função −f (x), pois as soluções locais e globais são as mesmas, somente os

sinais de cada coordenada do ponto ótimo é que serão opostas, conforme a figura

abaixo. Por isso, do ponto de vista matemático, não existe nenhuma diferença

relevante entre os problemas de minimização e de maximização da função

objetivo: todos os resultados obtidos para uma classe de problemas podem ser

facilmente estendidos para a outra classe sem dificuldade (IZMAILOV and

SOLODOV, 2005).

Figura 1.2 – má xf ( x )=min [−f (x )]

Existem vários técnicas de otimização e não há uma forma padrão e

universal de classificação destas técnicas. Os métodos dependem do tipo de

função objetivo que aparece no problema (se é linear ou não linear), do espaço

das variáveis de projeto (se há restrições ou o problema é irrestrito), das variáveis

de projeto (inteiras ou contínuas) e das técnicas de otimização empregadas

4

(determinística diferenciável, determinística não diferenciável, estocástica e

híbrida). Apresentamos a seguir algumas definições úteis na denominação dos

tipos de problemas que estudaremos:

Programação Linear (PL) e Programação Não Linear (PNL) – Quando a

função objetivo e as restrições são lineares o problema é chamado de

problema de programação linear. Caso contrário é um problema de

programação não linear. Problemas de PL aparecem muito em aplicações em

economia e transporte e problema de PNL aparecem com frequência em

aplicações de engenharia.

Problemas Restritos e Problemas Irrestritos – Um problema de otimização

irrestrito é aquele onde nrestreq=nrestrneq=0, isto é, não há nenhuma função de

restrição de igualdade e desigualdade das variáveis de projeto. Caso contrário

o problema é chamado de restrito. As restrições podem ser lineares, não

lineares ou ainda uma combinação delas.

Otimização Inteira e Otimização Contínua – Em vários problemas de

otimização, só faz sentido analisar as variáveis de projeto para números

inteiros. Por exemplo, para problemas que envolvem número de produtos,

número de ônibus em uma frota, número de trabalhadores em uma fábrica,

etc.. Estes problemas também são denominados problemas de otimização

discreta. Na otimização contínua todas as variáveis pertencem ao conjunto

dos números reais R.

Otimização Local ou Global – Um problema de minimização global um

ponto de mínimo é aquele que possui o menor valor da função objetivo

quando comparado a todos os pontos da região viável do espaço de projeto.

Um mínimo local é um ponto que possui o menor valor da função objetivo

apenas em uma vizinhança deste ponto (que esteja na região viável) em

consideração. A seguir apresentamos uma figura que ilustra a definição de

mínimo local e global.

5

Figura 1.3 – Representação de Mínimos locais e Global

Otimização Determinística – São métodos de otimização que utilizam

recursos do cálculo em seus algoritmos de busca. São métodos iterativos e

são utilizados quando se conhece o modelo que representa o problema de

otimização. Possuem algumas restrições quanto à implementação, pois em

geral não são métodos de otimização global e alguns dependem do

conhecimento das derivadas da função objetivo e das restrições. A

convergência de métodos determinísticos, bem como suas taxas de

convergência, podem ser provadas por teoremas e são objetos de estudo de

matemáticos no mundo inteiro. Podemos classificar os métodos

determinísticos quanto à ordem das derivadas que aparecem na sua

implementação. A seguir está uma classificação destes métodos:

Métodos de Ordem Zero – São métodos de otimização determinística que não

utilizam a derivada das funções do problema. Os mais famosos são: O Método da

Seção Áurea e o Método de Powell.

Métodos de Primeira Ordem – São métodos que utilizam o conhecimento da

primeira derivada das funções do problema. Os mais usados são: O método da

Máxima Descida (Método do Gradiente), Métodos das Direções Conjugadas e os

Métodos da Métrica Variável. São mais eficientes, computacionalmente falando,

do que os métodos de primeira ordem, pois possuem taxa de convergência mais

alta.

Método de Segunda Ordem – É o método que depende do cálculo da primeira e

segunda derivada das funções que aparecem no problema de otimização. O

método de segunda ordem é o famoso Método de Newton. Por sua vez, o método

de segunda ordem possui ordem de convergência maior que os de primeira

6

ordem. Para ilustrar o que significa a taxa de convergência, um método que

converge com taxa um (convergência linear) precisa dobrar o número de

iterações para conseguir dobrar o número de casas decimais exatas de uma

solução. Já um método que converge com taxa dois (convergência quadrática)

para dobrar o número de casas decimais exatas de uma solução precisa realizar

apenas mais uma iteração. Para uma demonstração deste resultado e para saber

um pouco mais sobre taxas de convergência veja MOREIRA (2006).

Pode ser provado que o Método de Newton possui convergência

quadrática (sob certas condições) e que o Método da Máxima Descida possui

convergência linear.

A seguir apresentamos uma figura que ilustra os métodos de otimização

determinística bem como sua classificação quando às restrições e uso de

derivadas.

Figura 1.4 – Classificação de Métodos Determinísticos de Otimização

Otimização Estocástica – Os métodos de otimização estocástica também

são chamados de métodos heurísticos. A palavra heurística vem do grego

7

“heuriskein” que significa descobrir/encontrar. Estes métodos utilizam apenas

informações das funções que aparecem no problema de otimização e não de

suas derivadas. São métodos de otimização global e possuem “mecanismos

de fuga” de mínimos locais. Os mais famosos são os Algoritmos Genéticos

(AG), Algoritmo de Evolução Diferencial (ED), Recozimento Simulado (SA),

Algoritmo de Colônias de Formigas (ACO), Otimização por Bactérias,

Algoritmos dos Vagalumes, Busca Tabu, Otimização por Colisão de Partículas

(PSO), entre outros.

Otimização Híbrida – Quando se utiliza mais de um método em um problema

de otimização dizemos que esta é uma técnica híbrida de otimização.

Métodos de otimização estocástica (heurística) convergem rapidamente para

a região do ótimo, mas demoram muito para refinar a solução. Já métodos

determinísticos possuem apenas convergência local e em geral não são muito

lentos, assim se estiverem na região do ótimo global, convergem com certa

rapidez para o ótimo. Por isto é muito comum a aplicação de um método

estocástico para se chegar a região do ótimo e depois a aplicação de um

método determinístico para refinar a solução. Existe também a proposta da

aplicação de dois métodos heurísticos simultaneamente para refinar a solução

de um problema.

Neste estudo concentraremos nossa atenção nos métodos heurísticos de

otimização PSO (baseado no comportamento social de pássaros), FireFly

(baseado no comportamento coletivo de vagalumes), BFO(baseado no

comportamento de bactérias na procura por alimento) e no algoritmo chamado

Life Cycle (que é um mix entre várias heurísticas). Realizaremos também um

estudo sobre otimização para problemas com mais de um objetivo, denominados

Problemas de Otimização Multi-Objetivo (POMO). Ao final realizaremos algumas

aplicações da heurística FireFly para problemas mono e multi-objetivos.

8

Capítulo 2_________________________________Otimização por Enxame de

Partículas (Particle Swarm

Optimization – PSO)

O algoritmo de Otimização por Enxame de Partículas (do inglês Particle

Swarm Optimization - PSO) é uma heurística baseada em população e que foi

proposta por James Kennedy e Russel Eberhart em 1995, ver KENNEDY and

EBERHART (1995). Surgiu a partir de processos que modelam o comportamento

social de algumas espécies de pássaros e cardumes de peixes onde cada ave

(peixe) é uma partícula e o bando (cardume) é o enxame, daí o nome enxame de

partículas. Existem vários modelos de comportamento social, dentre eles,

Kennedy e Eberhart se interessaram por um modelo particular desenvolvido por

um biólogo chamado Frank Heppner.

Considere o seguinte cenário: Um grupo de pássaros está procurando por

comida ou local para descanso, em certa região. Suponha que nesta região há

apenas um local de comida ou descanso e que os pássaros não sabem, a priori,

onde está este lugar. Qual é a melhor estratégia para procurar este lugar? A

estratégia escolhida por muitos grupos de pássaros é a de seguir um pássaro que

está mais próximo da comida ou do descanso.

Através de regras simples que os pássaros usam para se movimentarem,

um pássaro quando sai do bando para pousar na comida ou no local de descanso

acaba atraindo os pássaros mais próximos, isto é, os indivíduos aprendem com o

sucesso da “melhor” ave do bando. Outro fato a ser considerado é que cada

indivíduo do bando faz uso de informações pessoais para encontrar um local para

descanso ou uma fonte de comida.

9

Assim faz-se necessário um ajuste da capacidade individual de procurar

uma boa solução (exploração - exploration) e da capacidade de tirar proveito das

informações do bando para alcançar seu próprio sucesso (proveito - exploitation).

Quando há pouca exploração, a resposta pode convergir para a primeira boa

solução encontrada e quando há pouco proveito, pode ser até que a resposta

ótima nunca seja encontrada. Portanto, para aumentarmos a chance de alcance

da resposta esperada, devemos balancear estes dois comportamentos

observados: o conhecimento individual e a socialização dos indivíduos.

2.1 População (Enxame) Inicial

Para a inicialização do algoritmo, o vetor de posição e o vetor de

velocidades podem ser definidos aleatoriamente pelas seguintes equações:

x i0=x lower+k1 (xupper−x lower )

v i0=x lower+k2 ( xupper−xlower )

∆ t

onde x lower e xupper são os limites inferior e superior, respectivamente, das variáveis

de projeto, k 1e k 2 são números aleatórios no intervalo [ 0,1 ] uniformemente

distribuídos e ∆ t corresponde ao passo de tempo.

2.2 O Algoritmo PSO

No enxame definido pelo algoritmo PSO, as partículas que o compõe,

comunicam-se para compartilhar o conhecimento que cada uma adquiriu e desta

forma aumentam sua capacidade de tomada de decisão, não baseada apenas em

um conhecimento individual de cada partícula, mas no conhecimento do enxame.

Vamos estabelecer as notações necessárias para o entendimento do

algoritmo. Cada partícula i do enxame, na iteração k será representada pelos

seguintes vetores:

A posição atual da partícula (n-dimensional): x ik=(x1i

k , x2 ik ,…,x¿

k );

A melhor posição encontrada pela partícula até o momento: pbesti ;

A sua velocidade atual: v ik=(v1 i

k , v2ik ,…,v¿

k ).

10

O enxame de partículas também guarda um vetor pbestswarm, que representa

seu conhecimento social. Este vetor armazena a melhor posição encontrada, em

todas as iterações, quando consideramos todas as partículas do enxame.

O PSO faz uso de um vetor de velocidades e um vetor de posição para

modelar o comportamento (movimento) das partículas do enxame. O vetor de

velocidades e o vetor de posição das partículas são atualizados pelas seguintes

equações:

v ik+1=wv i

k+c1 r1

( pibest−x i

k )∆ t

+c2 r2

( pswarmbest −x i

k)∆ t

x ik+1=xi

k+v ik+1∆ t

onde r1e r2 são números aleatórios uniformemente distribuídos entre 0 e 1 e

i=1,2 ,…,nparticulas.

A figura abaixo ilustra, de forma bidimensional, a atualização da velocidade

quando consideramos duas partículas.

Figura 2.2.1 – Atualização do vetor velocidade – PSO

Reproduzido de VIANA(2008)

Existem três parâmetros que devem ser controlados pelo usuário na

simulação do algoritmo PSO, são eles: a inércia da partícula (w), e os dois

parâmetros c1 e c2 (cognitivo e social respectivamente). A inércia controla a

11

capacidade do algoritmo em explorar, isto é, um valor alto de w facilita um

comportamento mais global, enquanto um valor baixo facilita um comportamento

local (VENTER & SOBIESZCZANSKI-SOBIESKI, 2002). Os parâmetros de

confiança c1 e c2 indicam o quanto uma partícula confia em si (c1) e no enxame (c2

).

Apresentamos abaixo um fluxograma básico da aplicação do algoritmo PSO.

Figura 2.2.2 – Fluxograma de aplicação do PSOReproduzido de VIANA (2008)

2.3 Parâmetros do Algoritmo

A fórmula utilizada para a atualização do vetor de velocidades contém alguns

parâmetros do algoritmo PSO que devem ser ajustados de acordo com o

problema. Os parâmetros são de confiança e de inércia. Os parâmetros de

confiança devem ser ajustados de forma a balancear a relação entre o

12

conhecimento da própria partícula e o conhecimento do enxame. A literatura

sugere a utilização dos valores c1=c2=2, porém os parâmetros de confiança

podem ser ajustados para outros valores, em geral satisfazendo c1+c2=4. Para a

inércia, os valores propostos na literatura devem satisfazer 0.8≤w≤1.4. Um

processo de ajuste dinâmico do fator de inércia é proposto por VENTER &

SOBIESZCZANSKI-SOBIESKI (2002). Segundo eles, este ajuste promove

Uma convergência mais rápida do algoritmo;

A escolha de um valor de w mais livre e até mesmo sem a interação do

usuário.

O fator de inércia é atualizado de acordo com a equação:

wnew=f wold

onde f é uma constante entre 0 e 1. O valor de w não é atualizado a cada

iteração. Um coeficiente de variação (CV) dos valores da função objetivo, para um

subconjunto das melhores partículas, é calculado a cada iteração. Se o CV ficar

abaixo de um valor fixado a priori, é assumido que o algoritmo está convergindo

para a solução ótima (VENTER & SOBIESZCZANSKI-SOBIESKI, 2002). Neste

caso, o fator de inércia é atualizado segundo a equação anterior. O valor do

coeficiente de variação é calculado por

CV=Desvio Padrãomédia

2.4 Operador de Perturbação

Este operador atua como o operador de mutação nos Algoritmos Genéticos. Tem

como objetivo evitar uma convergência prematura do algoritmo. Este operador

altera tanto o vetor posição quanto o vetor velocidade. O vetor velocidade é

recalculado segundo a seguinte expressão:

v ik+1=c1 r1

( p ibest−x i

k )∆ t

e o vetor posição é recalculado por sua expressão usual.

Este operador é aplicado ao final de cada iteração e as partículas a

sofrerem este processo de mutação são identificadas pelo mesmo coeficiente de

variação definido anteriormente. Quando o coeficiente de variação (de um

13

subconjunto das melhores partículas) for menor que um valor pré-estabelecido

assume - se que o enxame está se tornando muito uniforme. Assim, partículas

que estão longe do centro do enxame são identificadas. As partículas que estão

localizadas a mais de duas vezes o desvio padrão do centro do enxame serão

perturbadas. Podemos observar que a expressão utilizada para a perturbação das

partículas que estão longe do centro do enxame leva em consideração apenas o

fator cognitivo da partícula e não o fator social do grupo. Agindo assim, o

algoritmo, está dando um “voto de confiança” para estas partículas com o objetivo

de aumentar a diversidade na população de partículas, isto é, no conjunto de

potenciais soluções para o problema de otimização.

VENTER & SOBIESZCZANSKI-SOBIESKI (2002) afirmam que não há

consenso quanto à eficiência real deste operador de perturbação. Segundo os

autores, Kennedy e Eberhart concluíram que este operador pode não ser

necessário, enquanto Fourie e Groenwold reintroduziram este operador em suas

aplicações.

A seguir apresentamos um pseudocódigo de implementação do algoritmo PSO:

Pseudocódigo para o Algoritmo PSODados de entrada:

f (x), onde x=(x1 , x2,…, xn) {função custo}

S= [ xilower , x iupper ] , i=1: n {espaço de projeto}

m = tamanho do enxame , w , c1 e c2 {parâmetros do algoritmo}

Dado de saída:x¿=min

x∈Sf (x )

Início: Para i=1 :m faça

x i0→Geraçãoda população Inicial

FimCalcular pi

best e pswarmbest iniciais

Enquanto k<nmaxgeracões façaPara i=1 :m faça

v ik=w v i

k+c1r 1

( pibest−xi

k)∆ t

+c2r2

( pswarmbest −x i

k )∆ t

x ik=x i

k+v ik+1∆ t

Calcular pibest e pswarm

best

k=k+1

14

fim

_____fim__________________________________________________________Figura 2.4.1 – Pseudocódigo de Implementação do Algoritmo PSO

Capítulo 3_________________________________Otimização por Vagalumes

(Firefly Algorithm - FA)

Os vagalumes são sem dúvida um dos insetos mais fascinantes de toda a

natureza. São insetos noturnos da família Lampyridae (ordem Coleoptera) e são

famosos por sua característica bioluminescente. Habitam principalmente as

regiões tropicais e temperadas e sua população é composta por mais de 1900

espécies, ENCICLOPEDIA BRITANICA(2009).

Baseado no comportamento destes insetos, Xin-She Yang (YANG, 2008)

propôs, na Universidade de Cambridge, um algoritmo heurístico de otimização.

Segundo YANG (2008), a biologia ainda não possui um conhecimento completo

de todas as utilidades que a luminescência pode trazer aos vagalumes, mas pelo

menos três funções já foram identificadas:

i. A luminescência é uma ferramenta de comunicação e de atração

para potenciais parceiros de reprodução;

ii. Serve como isca para a atração de alguma eventual presa;

iii. Também serve como um mecanismo de defesa, pois é um sinal

de alerta aos predadores lembrando-os que os vagalumes

possuem um “sabor amargo”.

O algoritmo Firefly (Firefly Algorithm - FA) é baseado principalmente na

primeira característica, isto é, na atração de parceiros para reprodução. Esta

característica é vista em algumas espécies de vagalumes, onde a taxa de

intermitência e a intensidade de cada flash é parte essencial do mecanismo de

15

atração do sexo oposto para acasalamento. Na maioria dos casos, as fêmeas é

que são atraídas pelo brilho emitido pelos machos. Observa-se também que

quando há uma grande quantidade de vagalumes numa mesma região, então há

uma sincronização na emissão dos flashes, que torna evidente uma característica

de organização emergente (YANG, 2008). Mecanismos de comunicação via

flashes luminescentes e sua sincronização tem sido emulados com sucesso e

sido aplicados em vários projetos de Rede Wireless (LEIDENFROST &

ELMENREICH, 2008), Dinâmica de Preços de Mercado (JUMADINOVA &

DASGUPTA, 2008) e robótica móvel (KRISHNANAND & GHOSE, 2006).

3.1 O algoritmo Firefly

Para a implementação do algoritmo FA, YANG(2008) definiu três regras

simplificadoras para o delineamento da execução do algoritmo, são elas:

Os vagalumes não possuem sexo, isto é qualquer vagalume do

enxame poderá ser atraído ou atrair;

A atratividade de um vagalume é diretamente proporcional ao brilho

emitido e inversamente proporcional à distância entre os vagalumes

(esta regra é baseada no comportamento real destes insetos);

O brilho emitido é determinado em comparação com seu valor na

função objetivo, isto é, quanto melhor avaliado maior será o seu

brilho.

Para entender o algoritmo FA devemos compreender como se dá a

variação da intensidade do brilho percebido pelo vagalume e como é formulada a

atratividade entre eles. Ainda segundo YANG (2008), a atratividade de um

vagalume é determinada pela intensidade do brilho emitido por ele, e esta

intensidade é função de sua avaliação. Como a atratividade entre dois vagalumes

é inversamente proporcional à distância entre eles, devemos escolher uma função

decrescente, em relação à distância r=d (x i , x j) entre os vagalumes. Tem sido

amplamente utilizada a seguinte função

β=β0 e−γ r2

onde β0 e γ são parâmetros pré-determinados do algoritmo: atratividade máxima

(quando r=0 e geralmente β0=1) e coeficiente de absorção, respectivamente.

16

Para explorar eficazmente o espaço de projetos, cada vagalume do

enxame move-se iterativamente de acordo com dois fatores:

i. A atratividade de outros membros do enxame com maior

intensidade de luz emitida que varia de acordo com a distância;

ii. Um vetor de passo aleatório.

Assim, na k-ésima iteração, a movimentação de um vagalume x ik em

direção a um melhor vagalume x jk é definida pela seguinte equação:

x ik+1=xi

k+β (x jk−x ik )+α(rand−12 )

em que, o segundo termo da equação insere o fator de atratividade β e o terceiro

termo, regulado pelo parâmetro α , regula a inserção de certa aleatoriedade no

caminho percorrido pelo vagalume e rand é um número aleatório entre 0 e 1.

Pseudocódigo para o Algoritmo FADados de entrada:

f (x), onde x=(x1 , x2 ,…, xn) {função custo}

S= [ xilower , x iupper ] , i=1: n {espaço de projeto}

m = tamanho da população, β0 e γ {parâmetros do algoritmo}

Dado de saída:

x¿=minx∈S

f (x )

Início: Para i=1 :m faça

x i0→Geraçãoda população Inicial

fim Realizar

Para i=1 :m façaPara j=1:m faça

Se f ( x jk )< f (x ik) então

r→distânciaentre x jk e x i

k

β→ β0 e−γ r 2

{atratividade}

uik→Gerar vetor aleatório

x ik+1=xi

k+β (x jk−x ik )+uikfim

fim Até que algum critério de parada seja satisfeitoFim

17

Figura 3.1.1 – Pseudocódigo de Implementação do Algoritmo FA

Observação 3.1.1 – Note que o melhor vagalume do enxame não é movido.

Podemos inserir um movimento aleatório para ele e caso não melhore o valor da

função objetivo, o movimento é descartado.

Observação 3.1.2 – De acordo com o pseudocódigo acima, um vagalume segue

o primeiro vagalume que seja mais brilhante do que ele (melhor avaliado na

função objetivo) e não o melhor vagalume da população. Isto faz com que haja

uma maior diversidade na população de vagalumes, pois se todos seguissem o

vagalume de brilho mais intenso, a população se estagnaria em poucas gerações.

3.2 Alguns Detalhes Técnicos

Cada vagalume do enxame explora o espaço de projeto levando em consideração

resultados obtidos por outros vagalumes e também aplicam seus movimentos ao

acaso. A influência de outros vagalumes se deve ao fator de atratividade. Este

movimento que leva em consideração os resultados do enxame pode ser ajustado

pela modificação de dois parâmetros:

O valor da atratividade máxima β0;

O valor do coeficiente de absorção γ .

O primeiro parâmetro descreve a atratividade quando dois vagalumes

encontram-se no mesmo ponto do espaço de projetos. Em geral escolhe-se

β0∈[0,1] e dois casos extremos devem ser analisados. Quando β0=0, não

consideramos o comportamento social dos vagalumes e consideramos apenas o

movimento aleatório. Quando β0=1, é equivalente ao sistema de crédito total nas

informações dadas pelo enxame onde o vagalume mais brilhante influencia

totalmente no movimento dos outros vagalumes, especialmente os que estão na

sua vizinhança.

O valor do coeficiente de absorção γ determina a variação da atratividade

em função da distância entre dois vagalumes. A utilização de γ=0 corresponde a

uma atratividade constante entre os vagalumes e valores altos para o coeficiente

de absorção γ , resultam na atratividade tendendo a zero que é equivalente a uma

busca apenas aleatória por parte dos vagalumes. YANG (2008) propõe γ ∈ [ 0,10 ] .

No entanto, é mais conveniente estipular o valor de γ para cada problema

18

considerado. Alguns autores sugerem a atualização do coeficiente de absorção a

cada iteração. Podemos sugerir o valor de γ através da seguinte expressão:

γ=γ0

rmax

ou

γ=γ0

rmax2

considerando que γ 0∈[0,1] e

rmax=max d (x i , x j ) ,∀ x i , x j na k-ésima iteração.

No caso da atualização do valor do coeficiente de absorção γ podemos

observar que à medida que a população se torna mais uniforme, o valor do

coeficiente aumenta e a partir deste aumento o algoritmo FA considera mais os

movimentos aleatórios dos vagalumes.

Finalmente vamos descrever o vetor de passo aleatório. Muitos autores

utilizam como vetor de passo aleatório o seguinte vetor

uik=α(rand−1

2 )onde rand U (0,1) é um número aleatório com distribuição uniforme e α um

parâmetro inicial do algoritmo. Podemos sugerir uma nova forma de calcular o

vetor de passo aleatório para o FA dependendo dos limites inferior e superior do

espaço de projetos:

uik={αran d2 (x iupper−x ik ) se sinal (ran d1−0,5 )<0

αrand2 (x ik−x ilower ) se sinal (ran d1−0,5 )≥0

onde os rand i são números aleatórios uniformemente distribuídos no intervalo [0,1].

19

Capítulo 4_________________________________Otimização por Colônia de

Bactérias (Bacterial Foraging

Optimization - BFO)

O algoritmo de Otimização por Colônia de Bactérias (do Inglês Bacterial Foraging

Optimization – BFO) é um algoritmo baseado na inteligência de enxames e é

inspirado no comportamento das bactérias Escherichia Coli (E. Coli) na busca

por nutrientes e foi proposto em 2001 pelo Prof. Kevin Passino (PASSINO, 2002).

Bactérias possuem a característica de migrarem para áreas ricas em

nutrientes e o mecanismo utilizado por elas para este movimento é chamado de

Quimiotaxia. Muitas bactérias possuem uma série de flagelos rotativos em sua

superfície celular que funcionam como propulsores do movimento realizado por

elas. Quando todos os flagelos movem-se no sentido anti-horário eles

impulsionam a célula em um movimento helicoidal e quando se movem no sentido

horário todos eles puxam a bactéria em diferentes direções aleatórias, com

deslocamento muito pequeno. Tais movimentos justificam-se como uma

estratégia da bactéria para aumentar as chances de encontrar uma região ótima.

Como a mobilidade das bactérias E. Coli dependem da agregação

quimiotática, é razoável esperar que a população das bactérias dependa da

quantidade de nutrientes ofertada (disponível). Em um ambiente favorável, a

reprodução das bactérias se dá através do processo de fissão binária. Neste

processo o DNA é replicado antes da divisão e, em seguida, a parede celular e a

membrana plasmática crescem para dentro, dividindo a célula em duas idênticas.

20

Pensando computacionalmente, o objetivo do algoritmo BFO é emular um

percurso aleatório com certa tendência para cada bactéria, que deve dirigir-se

para a maior quantidade de nutrientes evitando substâncias nocivas. De acordo

com ALI & MAJHI (2006), o comportamento de busca de uma colônia de bactérias

E. Coli pode ser delineado pelos seguintes processos:

Quimiotaxia;

Aglomeração (Swarming);

Reprodução;

Eliminação e Dispersão.

A seguir apresentaremos as notações que utilizaremos para a definição do

algoritmo BFO. Após a definição das notações, faremos uma apresentação

detalhada de cada um dos processos citados acima e ao final apresentaremos um

Pseudocódigo para o algoritmo de Otimização BFO.

4.1 Notação Utilizada

É necessário definir uma notação para que possamos entender os processos e o

algoritmo BFO. A seguir apresentamos a notação referente aos parâmetros do

algoritmo.

n : dimensão do espaço de busca;

N Bac : número total de bactérias na colônia;

NQuimio : número de etapas da Quimiotaxia;

N Nado : número de nados das bactérias;

N Repro : número de reproduções;

N E−D : número de eventos de eliminação e dispersão;

PE−D : probabilidade de eliminação e dispersão;

C (i) : tamanho do passo na direção aleatória especificada pelo giro.

Seja P ( j , k ,l )={θi ( j , k , l ); i=1,2 ,…, NBac } a posição de cada bactéria da

população na j-ésima etapa quimiotática, k-ésima etapa de reprodução e no l-

ésimo evento de eliminação e dispersão. Usaremos J ( i , j , k , l )=f (θi ( j ,k , l ) ) para

denotar o custo da i-ésima bactéria θi ( j , k , l )∈Rn.

21

4.2 Quimiotaxia

A Quimiotaxia é o movimento quimicamente dirigido que desenvolvem

alguns seres vivos. Este movimento dirigido e as substâncias químicas envolvidas

nele são utilizados por alguns organismos unicelulares, insetos, mamíferos e até

mesmo pelo homem, com diversos fins, como por exemplo, na busca por

nutrientes, a fim de evitar predadores, para gerar comunicação entre indivíduos

na formação de colônias ou grupos, para atração sexual ou mesmo a demarcação

de território (MURRAY, 2002). Além desta definição, na literatura o termo

quimiotaxia é referido ao movimento celular em resposta a gradientes de

concentração de químicos presentes em um determinado ambiente.

A bactéria E. Coli movimenta-se de duas formas principais: nadar (swin) ou

girar (tumble). No nado a bactéria move-se em uma direção específica, enquanto

no giro ela não possui uma direção certa de movimento e há pouco

deslocamento. Em geral as bactérias alternam estes dois tipos de movimento

durante toda a sua vida.

Vamos definir o passo quimiotáxico para o algoritmo BFO da seguinte

forma: um nado seguido por um giro ou um giro seguido por um nado. O

movimento quimiotáxico de uma bactéria θi ( j , k , l ) pode ser expresso por:

θi ( j+1 , k , l )=θi ( j , k ,l )+C (i)∆(i)

√∆T ( i)∆(i)

onde ∆ indica um vetor aleatório cujos elementos estão no intervalo [−1,1].

4.3 Aglomeração (Swarming)

Este processo descreve a capacidade que muitas bactérias têm de comunicar-se

umas com as outras com o objetivo de cooperar na busca por nutrientes. Foi

observado que quando algumas bactérias foram estimuladas com um alto nível de

succinato, liberam um aspertato atrativo, que as ajudam a agregar-se em grupos

e assim mover-se com padrões concêntricos de enxames com alta densidade

bacteriana.

Para considerar este processo de atração entre as bactérias é necessário

inserir uma penalidade baseada nas distâncias relativas entre cada bactéria e a

bactéria mais saudável do enxame. Esta penalidade é incluída na função custo

22

original. Quando todas as bactérias convergem para um ponto específico, a

penalidade tende a zero. A representação matemática (penalidade) para o

swarming considerando a sinalização entre as bactérias via um atrator e um

repulsor pode ser expressa por:

JCC (θ , P ( j , k ,l ) )=∑i=1

NBac [−datração .exp(−watração .∑m=1

n

(θm−θmi )2)]+∑i=1

N Bac [hrepulsão .exp(−wrepulsão .∑m=1

n

(θm−θmi )2)]onde datração, watr ação, hrepulsão e w repulsãosão coeficientes que devem ser escolhidos

adequadamente.

Vamos entender o que significa cada um destes coeficientes:

datração é a profundidade do atrator liberado pela bactéria, isto

é, uma quantificação de quanto atrator é liberado;

watração é uma medida de largura do sinal atrator, isto é, uma

quantificação da taxa de difusão química;

A célula também repele uma célula próxima no sentido de que

consome nutrientes próximos e é fisicamente impossível

haver duas células na mesma posição, assim hrepulsão é a altura

do efeito repulsor e w repulsão é uma medida da largura do sinal

repulsor.

Um valor negativo de JCC indica que a bactéria está em um lugar promissor,

isto é, em um lugar com bastante nutrientes. Um valor nulo indica um ambiente

neutro e um valor positivo de JCC indica um ambiente nocivo à bactéria. Assim, o

custo de uma bactéria θ, considerando o efeito do swarming, pode ser dada por:

J ( i , j , k , l )=J (i , j , k , l )+J CC (θ ,P ( j , k ,l))

4.4 Reprodução

Após várias etapas de quimiotaxia, as bactérias são separadas em dois

grupos de tamanhos iguais. O primeiro grupo é o das bactérias mais saudáveis e

o segundo grupo o das menos saudáveis. As menos saudáveis morrem e as mais

23

saudáveis se dividem em duas de mesma localização, permanecendo constante o

número de bactérias da colônia. A saúde da bactéria θi ( j , k , l ) é calculada da

seguinte forma

JSaúdei = ∑

j=1

NQuimio

J (i , j ,k , l)=∑j=1

N Quimio

f (θi ( j , k , l ))

onde a saúde de uma bactéria é medida pela quantidade de nutrientes que ela

conseguiu se alimentar em toda a sua vida e o quanto foi bem sucedida em evitar

substâncias nocivas.

4.5 Eliminação e Dispersão

Mudanças graduais ou repentinas no ambiente onde vivem as bactérias, podem

acontecer por diversas razões, como por exemplo, o aumento significativo da

temperatura local que pode causar a morte de muitas bactérias. Estes eventos

podem acontecer de tal forma que todas as bactérias da colônia sejam mortas ou

um grupo é disperso para outro local. Para simular este fenômeno, algumas

bactérias são destruídas de forma aleatória, com uma pequena probabilidade,

enquanto novos substitutos são inicializados aleatoriamente no espaço de busca.

Este processo colabora na redução da probabilidade do algoritmo ficar preso em

um mínimo local.

4.6 Pseudocódigo do Algoritmo BFO

A seguir apresentamos um pseudocódigo de implementação do algoritmo BFO.

Pseudocódigo para o Algoritmo BFODados de entrada:

f (x), onde x=(x1 , x2 ,…,xn ); S= [ xilower , x iupper ] , i=1: n; N Bac,NQuimio, N Nado, N Repro, N E−D ,

PE−D {parâmetros do algoritmo}

Dado de saída:

x¿=minx∈S

f (x )

Início: Para i=1 :NBac faça

x i0→Geraçãoda população Inicial de Bactérias

24

fim Realizar

Enquanto w<Nmaxgerações

Para l=1 :N E−D façaPara k=1:N Repro faça

Para j=1:N Quimio façaCalcule J (i , j , k ,l) incluindo JccRealize o deslocamento

θi ( j+1 , k , l )=θi ( j , k ,l )+C (i)∆(i)

√∆T ( i)∆(i)fim

Calcule a saúde de cada bactériaElimine a metade das bactérias com menor a saúdeDuplique as bactérias com maior saúdefim

Para cada bactéria realize a eliminação-dispersão com certa probabilidade PE−D

w=w+1fim

_fim____________________________________________________________Figura 4.6.1 – Pseudocódigo de Implementação do Algoritmo BFO

25

Capítulo 5_________________________________LifeCycle (LC)

O algoritmo denominado Life Cycle (LC) é um método híbrido heurístico de

otimização que utiliza vários outros métodos heurísticos de otimização na sua

execução. Este método é baseado no conceito de mudança de ciclos(estágios)

durante a vida de qualquer ser vivo. Foi proposto inicialmente por KRINK &

LOVENBERG (2004) onde estes autores utilizaram um mix das heurísticas PSO e

GA para representar cada estágio do Life Cycle.

Os métodos heurísticos de otimização mais famosos já foram utilizados,

com sucesso, por pesquisadores em engenharia e outras áreas do conhecimento

do mundo inteiro. Em geral, estes métodos se mostraram eficientes na tarefa de

otimização em várias aplicações. A ideia do método LC é utilizar o que cada

heurística, usado como ciclo ou estágio de vida, tem de melhor como ferramenta

de otimização. Outro fator interessante do LC é que ele pode evitar a estagnação,

ou convergência prematura para um ótimo local, de uma heurística quando

somente esta é aplicada a uma população, pois, antes que a população se

estagne, outra heurística entra em ação na população atual que outra heurística

obteve. Isto melhora a diversidade da população de soluções.

O algoritmo Life Cycle é um algoritmo de otimização que usa,

sequencialmente, várias heurísticas em uma estrutura tipo cascata. Para a

implementação do LC faz-se necessário definir a quantidade de gerações que

compõe cada ciclo, sendo que após o encerramento deum ciclo, outra heurística

atua sobre a população na tarefa de otimização. O tamanho de cada ciclo é o

único parâmetro específico do LC, os outros parâmetros utilizados são os

parâmetros de cada heurística que atua no LC.

Não há uma regra rígida no procedimento de otimização via Life Cycle.

Outra forma de aplicação pode ser feita da seguinte maneira: cria-se

26

randomicamente uma população e esta é dividida em algumas subpopulações;

em cada subpopulação atua uma heurística e após o término do intervalo de

estágio, realize-se a mudança de aplicação das heurísticas sobre as

subpopulações. A tendência é que cada subpopulação convirja para ótimo do

problema. Agindo desta forma, podemos explorar melhor o espaço de projetos,

mas o preço a ser pago por isto é o aumento significativo do custo computacional.

Alguns autores tem utilizado o Life Cycle como algoritmo de otimização.

VIANA et al. (2009) usaram o LC no estudo de estabilidade longitudinal e

identificação de parâmetros de controle em aeronaves. ROJAS et al. (2007)

usaram o LC na identificação de forças externas em sistemas mecânicos. A

seguir apresentamos a figura de um esquema para a utilização do LC.

Figura 5.1 – Esquema de aplicação do algoritmo Life Cycle

Reproduzido de VIANA(2008)

27

Capítulo 6_________________________________Otimização Multi-Objetivo

Neste capítulo vamos dissertar sobre a teoria da otimização multi-objetivo. Não

temos a pretensão de esgotar o assunto e sim de explanar sobre as principais

características e definições sobre este assunto. Devido a crescente necessidade

de mercado na busca de soluções que envolvem problemas de otimização com

mais de um objetivo, a academia tem se envolvido bastante, nos últimos anos, na

criação e validação de metodologias para resolver problemas multi-objetivos,

multicritérios ou de otimização vetorial (SCHAFFER, 1984; DEB, 2001; BABU et

al., 2005; LOBATO, 2008).

Problemas de Otimização em Engenharia possuem dificuldade inerente da

área, pois vivenciam situações reais e cada vez mais complexas. São constituídos

de sistemas de equações algébricas e diferenciais (parciais e ordinárias) que

surgem a partir de balanceamentos de massa e energia. Em geral são problemas

restritos, pois possuem restrições econômicas, ambientais, de limitações físicas,

etc. Outro ponto importante no tratamento de Problemas de Otimização Multi-

Objetivo (POMO) é que, em quase sua totalidade, é impossível a obtenção de

solução analítica de problemas reais.

Existem diferenças significativas entre problemas com um único objetivo e

problemas com mais de um objetivo. As principais são:

i. A conceituação de ótimo para os problemas mono e multi-objetivo.

Em problemas mono-objetivos o ótimo é um ponto do espaço de

projetos que minimizam (maximizam) a função objetivo. Em POMO

muitas vezes os objetivos são conflitantes, isto é, a melhora em um

objetivo pode acarretar na piora de outro (DEB, 2001).

ii. Em problemas mono-objetivos existe o valor ótimo global. Já em

problemas multi-objetivos existe um conjunto de soluções

28

igualmente ótimas que visam preservar a diversidade de soluções,

sendo que não é possível dizer que uma solução é melhor que

outra.

Não há um consenso sobre o conceito de ótimo para um POMO. Isto

dificulta a comparação de resultados de um método para outro. A noção de ótimo

para POMO é devida a um economista inglês Francis Ysidro Edgeworth

(EDGEWORTH, 1881) e posteriormente aprimorada por outro economista, mas

agora francês, chamado Vilfredo Pareto (PARETO, 1986). A noção de ótimo

segundo Edgeworth-Pareto é que um ponto para estar na solução de um POMO

deve satisfazer a condição de que “nenhum critério utilizado pode melhorar a

solução sem piorar pelo menos outro critério”. Hoje em dia o postulado de

Edgewort-Pareto é mais conhecido na literatura por postulado de Pareto e fornece

para POMO não uma única solução, mas um conjunto de soluções denominadas

não dominadas ou não inferiores.

No que diz respeito às metodologias para a obtenção de soluções em

POMO existem, como no caso mono-objetivo, métodos Determinísticos e

métodos Heurísticos. Os métodos determinísticos são baseados no cálculo e as

técnicas mais famosas podem são descritas na figura 1.4. Os métodos heurísticos

são métodos baseados fenômenos da natureza e estão entre os mais usados

pelos pesquisadores os Algoritmos Genéticos (GA), Evolução Diferencial (DE),

Simulated Annealing (SA), Colônias de formigas (ACO), pássaros (PSO),

bactérias (BFO), vagalumes (FireFly) entre outros. Os métodos determinísticos

são métodos de busca ponto-a-ponto e por isto não é possível obter a solução de

um POMO em apenas uma única execução, pois a solução de um POMO é um

conjunto de pontos. Além disso, aplicações sucessivas de métodos

determinísticos não garantem uma boa aproximação da solução e nem tampouco

a diversidade das soluções. Assim os métodos heurísticos que trabalham com

uma população de pontos consistem em metodologias mais apropriadas na

resolução de problemas e otimização multi-objetivos, pois podem alcançar a

solução do POMO em uma única execução (DEB, 2001).

O pioneiro na implementação de um algoritmo multi-objetivo foi Schaffer

que em 1984, em sua tese de doutorado, utilizou a heurística Algoritmos

Genéticos em POMO (SCHAFFER, 1984). Após o trabalho de Schaffer, vários

29

trabalhos de pesquisa tem sido publicados com o intuito de fornecer novas

técnicas de resolução de POMO e também na aplicação das técnicas emergentes

a problemas nas mais diversas áreas do conhecimento. Além disso eventos como

a Conferência de Otimização Evolutiva em Problemas Multi-Objetivo (Conference

on Evolutionary Multi-Criterion Optimization) tem difundido bem as novas

metodologias e conceitos bem como mostrado várias aplicações destas novas

metodologias em áreas afins. Vários pesquisadores tem se empenhado na

publicação de trabalhos sobre otimização multicritério. LOBATO (2008) utilizou

um algoritmo multi-objetivo envolvendo a heurística Evolução Diferencial para a

solução de problemas de projeto de sistemas em engenharia. DEB (2001) realiza,

em seu livro, um estudo de otimização multi-objetivo utilizando conceitos de

otimização evolutiva. COELHO (2004) utiliza a otimização multi-objetivo na

otimização de projetos mecânicos. DOERNER et al. (2001) utiliza a meta-

heurística Otimização por Colônia de Formigas para um problema multi-objetivo

de portfólio. FANG et al. (2005) realiza um estudo comparativo de métodos de

meta-modelagem para problemas multi-objetivo de resistência a colisão.

GANDIBLEUX et al. (1997) utiliza a heurística Busca Tabu para resolver

problemas multi-objetivo combinatoriais. OSYSZKA (1984) é uma referência

clássica quando se trata de otimização multicritério. Em sua obra são tratados

problemas multi-objetivo aplicados à engenharia e com programas na linguagem

Fortram.

6.1 Formulação do Problema de Otimização Multi-Objetivo

De acordo com VANDERPLAATS (1984) um problema de otimização é

constituído por:

i. Função Objetivo – Define as características do sistema a ser otimizado. É

uma variável dependente das variáveis de projeto;

ii. Variáveis de Projeto – São as variáveis independentes que influenciam a

função objetivo e/ou as restrições. Variações dos valores destas variáveis

provocam o aumento ou diminuição do valor da função objetivo. Também

são chamadas de variáveis de busca ou de decisão;

iii. Restrições – As restrições são limitações do projeto a ser otimizado. Estas

podem ocorrer devido a limitações físicas, de construção (econômicas),

30

ambientais entre outras. As restrições determinam uma região chamada de

Espaço de Projetos, que é um subespaço do espaço n-dimensional Rn,

onde n é o número de variáveis de projeto. Podem ser de três tipos:

Restrições de Igualdade, Restrições de Desigualdade e Restrições

Laterais.

Podemos escrever, de forma compacta, um Problema de Otimização Multi-

Objetivo (POMO) através das seguintes expressões (DEB, 2001):

Minimizar F⃗ ( x )=( f 1 ( x ) , f 2 ( x ) ,…, f m ( x ) ) , x∈Rn (3)

Sujeito a {h l ( x )=0 , l=1 ,…,nrestreqg j ( x )≤0 , j=1 ,…,nrestneqx iinf ≤ x i≤ x i

¿ , i=1 ,…n (4)

onde f 1 ( x ) ,…, f m ( x ) são as funções objetivo, hl ( x ) ,l=1 ,…,nrestreq são as restrições

de igualdade, g j ( x ) , j=1 ,…,nrestrneq são as restrições de desigualdade, x iinf e x i

¿ são

as restrições laterais que determinam um limite inferior e superior,

respectivamente, para as variáveis de projeto.

Em um problema real em engenharia, cada uma das funções f 1 ( x ) ,…, f m ( x )

poderiam ser minimizadas ou maximizadas. Mas, como já foi dito anteriormente,

não há diferença do ponto de vista matemático, em um problema de minimização

e de maximização. Um pode ser transformado no outro de forma simples. Assim

trataremos apenas de um problema de minimização como é feito de forma

corrente na literatura. A imagem do espaço de projetos, via vetor de objetivos

F⃗ (x), é um espaço m-dimensional denominado de espaço de objetivos.

Neste momento cabe novamente ressaltar a diferença entre otimização

mono-objetivo e otimização multi-objetivo. As principais diferenças, segundo DEB

(2001), são:

Em um problema mono-objetivo a meta é encontrar uma única

solução do problema de otimização. Em um multi-objetivo a meta é

encontrar um conjunto de soluções que visam preservar a

diversidade neste conjunto de soluções;

Na otimização mono-objetivo trabalha-se com apenas um espaço o

de projetos. No caso multi-objetivo trabalha-se simultaneamente

31

com dois espaços: o de projetos e o de objetivos. Manter a

diversidade de soluções no espaço de objetivos é fundamental para

a qualidade de soluções, pois ajuda na tomada de decisões pela

melhor solução. Outro detalhe importante é que nem sempre é

possível garantir que a proximidade de soluções no espaço de

projetos implique na proximidade de soluções no espaço de

objetivos.

O problema de minimização do vetor de objetivos F⃗ (x) não significa

simplesmente na minimização de cada uma das funções objetivo que compõem o

vetor de objetivos, pois em muitas situações os objetivos são conflitantes, isto é, a

melhora em um dos objetivos pode acarretar na piora do valor de outros objetivos

(DEB, 2001). A figura abaixo retrata a dificuldade na escolha da solução ótima

para um caso de minimização de dois objetivos. A escolha dependerá de quem é

responsável pela tomada de decisões que com certeza levará em consideração

limitações físicas, econômicas, etc.

Figura 6.1.1 – Problema de minimização de dois objetivos.

Reproduzido de LOBATO (2008).

Neste contexto multi-objetivo, definiremos o que vem a ser chamada de

solução ideal ou utópica.

Definição 6.1.1 – A solução ideal ou solução utópica é o valor ótimo de cada

objetivo individualmente.

32

Como o próprio nome diz, em uma situação real, a solução ideal ou utópica

nunca será a solução ótima do problema de otimização multi-objetivo.

6.2 Otimalidade de Pareto

Nosso objetivo nesta seção é definir o conceito de ótimo segundo Pareto. Para

isto teremos que definir o conceito de dominância de uma solução sobre outra

solução. A maior parte dos algoritmos de otimização multi-objetivos utilizados

pelos pesquisadores trabalham com o conceito de dominância na busca pelas

soluções ótimas (OSYCZKA, 1984). Por isto o entendimento do conceito de ótimo

de Pareto e da definição de dominância é fundamental para entender os

algoritmos de otimização multi-objetivos.

Ao contrário do que é feito para o caso mono-objetivo, onde é possível

definir matematicamente a solução ótima, no caso multi-objetivo não há uma

definição de solução ótima e sim um conceito (entendimento) de soluções ótimas.

Este conceito é conhecido por Postulado de Edgeworth-Pareto ou mais

popularmente , na literatura, por Postulado de Pareto. Foi inicialmente concebido

pelo economista inglês Francis Ysidro Edgeworth (EDGEWORTH, 1881) (Figura

6.2.1(a)) e posteriormente aperfeiçoado pelo também economista, mas agora

francês, Vilfredo Pareto (PARETO, 1896) (Figura 6.2.1 (b)).

(a) Francis Ysidro Edgeworth (b) Vilfredo Pareto

Figura 6.2.1 – Idealizadores do conceito de ótimo para o POMO.

Reproduzido de http://www.business.baylor.edu (acessado em 15 de

outubro de 2011)

33

A noção intuitiva do postulado de Pareto é que um ponto para ser solução

de um POMO deve satisfazer a condição de que “nenhum objetivo adotado

melhora a solução sem piorar pelo menos um outro objetivo”.

Para encontrar as soluções de um POMO é necessário entender quando

que uma solução é melhor que outra. Isto é feito via o conceito de dominância de

uma solução sobre outra. Para entender quando é que uma solução domina outra

solução considere o seguinte problema. Em uma compra de um automóvel será

levado em consideração dois objetivos: o conforto e o preço. A tarefa é encontrar

quais são as melhores opções de compra que levam em consideração o menor

preço com o maior conforto. Nota-se intuitivamente que estes dois objetivos são

conflitantes. As opções são listadas na figura 6.2.2 abaixo:

Figura 6.2.2 – Opções de compra de automóveis: preço versus conforto.

Reproduzido de LOBATO (2008).

Através de uma simples análise das opções acima podemos descartar a

opção 1, pois a opção 5 possui o mesmo preço mas com maior conforto. A

solução 2 possui menor conforto e maior preço que as soluções 3 e 5, logo

também deve ser descartada. Restam apenas as opções 3, 4 e 5. Não é possível

dizer qual das opções que restaram é a melhor opção de compra, pois uma

solução pode até ser mais barata que a outra, mas possui menor conforto e vice-

versa. Neste contexto dizemos que uma solução domina sobre outra se seus

34

valores são melhores que os valores de outra em pelo menos um objetivo e se os

outros valores não são piores para todos os outros objetivos. Assim a solução 5

domina sobre as soluções 1 e 2. A solução 3 domina apenas a solução 2.

Podemos observar que as soluções 3, 4 e 5 não são dominadas por nenhuma

outra solução. As soluções 3, 4 e 5 são denominadas soluções não dominadas ou

soluções não inferiores.

O espaço de objetivos é decomposto em dois subconjuntos: o conjunto de

soluções dominadas e o conjunto de soluções não dominadas. Estes conjuntos

possuem as propriedades (DEB, 2001):

Qualquer solução do conjunto dominado deve ser dominada por pelo

menos uma solução do conjunto não dominado;

Nenhuma solução do conjunto não dominado é dominada por outra

solução do conjunto não dominado.

6.2.1 Operador de Dominância de Pareto

Nesta seção definiremos um operador de comparação entre duas soluções no

espaço de objetivos. Esta comparação serve para informar quando uma solução

domina sobre outra solução. Como dissemos anteriormente, a maioria dos

algoritmos computacionais de otimização multi-objetivo utiliza o conceito de

dominância na busca de soluções para os POMO.

Como nosso objetivo é escolher as melhores soluções, temos que

estabelecer uma relação de ordem no espaço de objetivos, pois estamos

interessados nos melhores valores das funções objetivo que compõe o POMO.

Definiremos então relação de ordem em um conjunto.

Definição 6.2.1.1 – Um conjunto M é ordenado segundo a relação de ordem “≼”

se dados quaisquer dois elementos x , y∈M , é sempre verdade que x≼ y ou y≼ x

e as seguintes propriedades com relação a “≼” são verdadeiras:

a) x≼ x (Reflexividade)

b) Se x≼ y e y≼ x então x= y (Anti-Simetria)

c) Se x≼ y e y≼ z então x≼ z (Transitividade)

35

Definição 6.2.1.2 – Um conjunto M é dito parcialmente ordenado se valem as

propriedades a), b) e c) mas nem sempre se tem x≼ y ou y≼ x com x , y∈M , isto

é, nem sempre os elementos de M são comparáveis.

Em um conjunto n-dimensional Rn, n≥2, é possível estabelecer

generalizações das relações “menor” ou “menor ou igual” definindo-se as relações

≺ e ≼ por exemplo da seguinte maneira:

Definição 6.2.1.3 (comparação de vetores) – As operações de comparação de

vetores no espaço Rn, n≥2, serão feitas da seguinte forma:

x≼ y⇒ {x i≤ y i; i=1,2 ,…,n}x≺ y⇒ {x i< y i ; i=1,2 ,…,n }x= y⇒ {x i= y i ; i=1,2 ,…,n}

As operações ≻ e ≽ são definidas de maneira inteiramente análoga. O operador

≠ é definido da forma:

x≠ y⇒ {∃ i ; x i≠ y i }Ou seja

x≠ y⇏ {x i≠ y i ; i=1,2 ,…n}Assim, a condição de desigualdade ≠ continua sendo complementar à condição

de igualdade =.

Qualquer espaço Rn, com n≥2 arbitrário, munido das operações de

comparação de vetores definidas acima, são espaços parcialmente ordenados,

pois nem sempre é possível comparar dois vetores segundo estas operações.

Aqui surge uma pergunta: É possível definir outro tipo de operação de

comparação de vetores de forma que os espaços Rn se tornem conjuntos

ordenados (não parcialmente, mas totalmente)? A resposta para esta pergunta é

não. SILVA (2003) realiza uma explicação bem simples, porém clara e precisa,

para esta resposta.

Nosso objetivo é definir um operador de comparação, que será

denominado operador de dominância, sobre o espaço de objetivos (subconjunto

de algum espaço Rn) para o POMO.

36

Definição 6.2.1.4 (dominância de uma solução) – Uma solução x domina

uma solução y (será representado por x⊲ y), no espaço de projetos, se as

condições forem satisfeitas (no espaço de objetivos):

i. F⃗ ( x )≼ F⃗ ( y ), isto é, se f i ( x )≤ f i ( y ) para i=1 ,2 ,…,m;

ii. F⃗ ( x )≠ F⃗ ( y ), isto é, existe pelo menos um i tal que f i ( x )≠ f i ( y ), ou

equivalentemente f i ( x )< f i ( y ).

A condição i) diz que em nenhum dos objetivos, a solução y é maior (no sentido

ordinário) do que a solução x. A condição ii) diz que pelo menos um dos objetivos

da solução x é estritamente melhor do que o da solução y.

Assim, se as duas condições acima forem válidas, podemos dizer que a

solução y é dominada pela solução x, ou que a solução x é não dominada pela

solução y.

Definição 6.2.1.5 (dominância forte de uma solução) – Uma solução x domina

fortemente uma solução y se F⃗ ( x )≺ F⃗ ( y ), isto é, se f i ( x )< f i ( y ) para i=1 ,2 ,…,m.

Definiremos agora alguns conjuntos que são importantes no estudo de um

POMO. Considere os seguintes conjuntos: H é o conjunto denominado espaço de

projetos e F=F⃗ (H), a imagem pelo vetor de objetivos de H , o espaço

denominado espaço de objetivos.

Definição 6.2.1.6 – O conjunto ótimo de Pareto Pótimo é o subconjunto do espaço

de projetos H formado por todas as soluções não dominadas de H , quando

comparadas a todas as soluções de H .

Definição 6.2.1.7 – O conjunto denominado fronteira de Pfront é o subconjunto do

espaço de objetivos F formado pelas imagens, pelo vetor F⃗, de todas as soluções

não dominadas de H , isto é Pfront=F⃗(Pótimo).

O conjunto Pfrontdenominado por fronteira de Pareto, no sentido matemático

de topologia, está realmente na fronteira do espaço de projetos F, ou

equivalentemente, nenhuma solução não dominada do POMO está no interior do

espaço de objetivos. A seguir definiremos um conjunto localmente Pareto ótimo.

Definição 6.2.1.8 – Seja P1⊂H um conjunto com a seguinte propriedade. Existe

P2⊂H com P1⊂P2 tal que todas as soluções de P1 são não dominadas com

relação ao conjunto P2. Então o conjunto P1 será denominado de conjunto

localmente Pareto ótimo.

37

A figura 6.2.3 mostra exemplos da localização da fronteira de Pareto para

problemas envolvendo, minimização e/ou maximização de um problema com dois

objetivos enquanto a figura 6.2.4 mostra um exemplo de um conjunto localmente

Pareto ótimo.

Figura 6.2.3 – Exemplo de fronteiras de Pareto para dois objetivos.

Reproduzido de Lobato (2008).

38

Figura 6.2.4 – Exemplo de conjunto de Pareto localmente ótimo.

Reproduzido de LOBATO (2008).

6.3 Metas para problemas de Otimização Multi-Objetivo

Sabemos que um fator importante para o responsável pela tomada de decisões é

que as soluções encontradas por um algoritmo multi-objetivo sejam bem

diversificadas, isto é, bem espalhadas no espaço de soluções. Soluções bem

próximas, no espaço de objetivos, a princípio podem ser consideradas iguais do

ponto de vista de escolha para a execução de um projeto real de engenharia.

Assim, faz-se necessário o controle da diversidade de soluções em um algoritmo

de otimização multi-objetivo. Outro fator, que é logicamente importante, é a

convergência do algoritmo. Segundo DEB (2001) a qualidade de um algoritmo na

resolução de um POMO se basicamente através do alcance da qualidade das

metas: convergência e diversidade. A figura 6.3.1, abaixo, mostra exemplos de

distribuições das soluções sobre a Fronteira de Pareto.

39

Figura 6.3.1 – Distribuição de soluções sobre a Fronteira de Pareto.

Reproduzida de LOBATO (2008).

Uma meta sobre a distribuição de soluções é específica de problemas de

otimização multi-objetivo, enquanto que a convergência é comum para qualquer

problema de otimização (ZITZLER et al., 2001). Segundo DEB (2001) para avaliar

o desempenho de um algoritmo multi-objetivo, é importante que se observe a

qualidade das duas metas: convergência do algoritmo e diversidade das soluções.

A figura abaixo relaciona as principais metas em otimização multi-objetivo.

Figura 6.3.2 – Metas de convergência e Diversidade.

Reproduzida de LOBATO (2008).

40

Não é possível afirmar que um algoritmo supera outro em qualidade

observando apenas uma das métricas acima relacionadas. É importante avaliar a

qualidade das duas métricas em um teste de um algoritmo. A figura 6.3.3 (a),

abaixo, mostra um caso hipotético de boa convergência mas, má diversidade de

soluções enquanto o a figura 6.3.3 (b) mostra boa diversidade mas, má

convergência.

Figura 6.3.3 – Convergência versus Diversidade.

Reproduzida de LOBATO (2008).

A figura abaixo retrata outras situações. No caso da figura 6.3.4 (a) é

evidente que o algoritmo A é melhor do que o algoritmo B. No entanto na figura

6.3.4 (b) não há como afirmar qual algoritmo é melhor.

Figura 6.3.4 – Comparação entre dois algoritmos hipotéticos.

Reproduzida de LOBATO (2008).

41

Na maioria dos casos reais, devido a sua complexidade inerente, é

impossível determinar a fronteira de Pareto, isto é, o conjunto solução analítica do

POMO. Como então avaliar o desempenho de um algoritmo de otimização multi-

objetivo? A avaliação do desempenho de um algoritmo multi-objetivo se ocorre da

seguinte forma. Problemas testes onde o conjunto ótimo de Pareto e a Fronteira

de Pareto estão totalmente determinados são utilizados na avaliação do

algoritmo. Se o algoritmo de otimização multi-objetivo, aplicado sobre estes

problemas, convergem e preservam boa diversidade de soluções, então se

assume que estes quando aplicados a outros problemas terão desempenho

similar. SCHAFFER (1984), em sua tese de doutorado, propôs uma grande

variedade de problemas que cuja solução analítica é conhecida e, portanto são

úteis em testes para os algoritmos multi-objetivo. Hoje em dia, muitos algoritmos

de otimização multi-objetivo possuem a implementação de alguns recursos,

testados com sucesso em vários casos, que visam preservar a diversidade de

soluções.

6.3.1 Métricas de Convergência e Diversidade de Soluções

Nesta subseção vamos descrever matematicamente as principais métricas

utilizadas para medir a qualidade de um algoritmo de otimização multi-objetivo.

Como dissemos na seção anterior, a qualidade da solução obtida por um

algoritmo é medida por sua convergência, em relação à solução analítica, e

também pela distribuição das soluções sobre a fronteira Pareto. Dividiremos as

métricas em: Métricas de Convergência e Métricas de Espalhamento.

6.3.1.1 Métricas de Convergência

São métricas utilizadas para medir a distância entre o conjunto R de soluções

obtidas por um algoritmo e o conjunto F de soluções analíticas (Fronteira de

Pareto) do POMO.

6.3.1.1 a) Taxa de Erro (T erro) – Esta métrica conta quantas soluções do

conjunto R não pertencem a Fronteira de Pareto F. Sua expressão matemática é:

42

T erro= ∑i=1

¿ R∨¿ ei¿ R∨¿ ¿

¿¿ onde e i={1 se xi∈F0 se x i∉F

Tem-se que 0≤Terro≤1. Quanto menor for o valor de T erro melhor é a convergência

do algoritmo e quando T erro=0 tem-se que R⊆F.

6.3.1.1 b) Convergência Métrica (Υ ) – Esta métrica calcula a média

aritmética das distâncias entre o conjunto de soluções não dominadas obtidas R e

o conjunto F de soluções analíticas. É expressa através da fórmula (DEB, 2001):

Υ= ∑i=1

¿R∨¿ di¿R∨¿¿

¿¿

Onde d i é a distância euclidiana (no espaço de objetivos) entre a solução x i∈ R e

a solução de F mais próxima. Isto é

d i=d (x i ,F )=min {d (x i , y ) ; y∈F }Quanto menor for o valor de Υ melhor será a convergência do algoritmo.

6.3.1.1 c) Distância Geracional (DGer) – Esta métrica também calcula uma

média entre o conjunto de soluções não dominadas obtidas R e o conjunto F de

soluções analíticas. Sua fórmula é dada por (DEB, 2001):

DGer=¿¿¿

Onde d i é a distância euclidiana (no espaço de objetivos) entre a solução x i∈ R e

a solução de F mais próxima e p é um número natural não nulo. Observe que

quando p=1, então DGer=Υ .

6.3.1.2 Métricas de Espalhamento

São métricas utilizadas para medir o quanto as soluções do conjunto R, obtido por

um algoritmo, estão espalhadas.

6.3.1.2 a) Espaçamento (Spc) – Esta métrica, proposta por ZITZLER et al.

(2000), mede o quanto as soluções estão espalhadas no conjunto R. Sua

expressão é dada por

Spc=¿¿¿

Onde d i é a distância, no espaço de objetivos, entre a solução x i e a solução em R

que esteja mais próxima, isto é,

43

d i= min⏟xk∈R, k ≠i

∑m=1

¿R∨¿|f m (xi )−f m (xk )|¿

¿

e

d= ∑i=1

¿R∨¿di¿ R∨¿¿

¿¿

Quanto menor for o valor do desvio, melhor espalhadas estarão as soluções.

6.3.1.2 b) Número de Nichos (NC) – Esta métrica também foi proposta por

ZITZLER et al. (2000). Esta métrica calcula o número de nichos existentes no

conjunto de soluções R obtidas pelo algoritmo. Sua expressão é dada por:

NC=1

|R|−1∑i=1

¿R∨¿ ¿ x j∈R ;d (x i ,x j)>σ∨¿¿¿

¿

Onde d (x i , x j ) é a distância entre as soluções x i e x j. Esta distância pode ser

calculada no espaço de variáveis ou de objetivos. O valor de NC representa o

número de soluções cuja distância entre si é maior que o parâmetro σ e quando

d (x i , x j )<σ as soluções x i e x j estão no mesmo nicho. Quanto maior o número de

nichos NC melhor espalhadas estão as soluções.

6.3.1.2 c) Espalhamento Máximo (EM) – Esta é mais uma métrica

proposta por ZITZLER et al. (2000). Esta métrica nos fornece a distribuição das

soluções no conjunto de soluções R obtidas pelo algoritmo. Sua expressão

matemática é dada por:

EM=√∑k=1

m

( |R|máx⏟i=1

f k (x i )−|R|mín⏟i=1

f k (x i ))Quanto maior for o valor de EM significa que há uma melhor distribuição

das soluções sobre o conjunto R.

6.3.1.2 d) Diversidade Métrica (Δ) – Esta é uma métrica proposta por

DEB, (2001) e também serve para medir o espalhamento das soluções no

conjunto de soluções R obtidas pelo algoritmo. É dada por:

44

Δ=d f+d l+∑i=1

|R|−1

¿d i−d∨¿

d f+d l+ (|R|−1 )d¿

Na fórmula acima, d f e d l representam a distância euclidiana entre as

soluções extremas da fronteira de Pareto F e do conjunto de soluções não

dominadas R. O número d i é a distância entre a solução x i∈ R e o membro mais

próximo da fronteira de Pareto F e d é a média destas distâncias.

6.4 Algoritmos Heurísticos de Otimização Multi-Objetivo

Nesta seção faremos a descrição de alguns famosos algoritmos multi-

objetivos evolutivos. A disponibilidade e popularidade de recursos computacionais

tem fomentado o aumento de aplicações, em problemas reais de engenharia,

utilizando técnicas de otimização. Sem dúvida as técnicas de otimização

baseadas no processo de evolução das espécies, principalmente os Algoritmos

Genéticos, foram as técnicas mais empregadas na resolução de problemas

complexos de otimização. Após a publicação do famoso livro de Goldberg em

1989, os Algoritmos Genéticos ganharam enorme notoriedade entre

pesquisadores do mundo inteiro e passaram a ser a técnica de otimização mais

empregada desde então (GOLDBERG, 1989).

No contexto multi-objetivo, o primeiro algoritmo baseado em Algoritmos

Genéticos foi o algoritmo proposto por SCHAFFER (1984) denominado “VEGA –

Vector Evaluated Genetic Algorithm”. A partir de então vários algoritmos baseados

em técnicas evolutivas foram propostos. Dentre os mais famosos, em ordem

cronológica, podemos destacar: MOGA – Multi Objective Genetic Algorithm

(FONSECA and FLEMING, 1993); NPGA – Niched Pareto Genetic Algorithm

(HORN et al., 1994); NSGA – Nondominated Sorting Genetic Algorithm

(SRINIVAS and DEB, 1994); SPEA – Strength Pareto Evolutionary Algorithm

(ZITZLER and THIELE, 1998); PESA – Pareto Envelope-based Selection

Algorithm (CORNE et al., 2000; CORNE et al. 2001); PAES – Pareto-Archived

Evolution Estrategy (KNOWLES and CORNE, 2000); NSGA II – Nondominated

Sorting Genetic Algorithm II (DEB et al., 2000); PMOGA – Pareto Multi-objective

Genetic Algorithm (CASTRO, 2001); DMOEA – Dynamic Multi-objective

Evolutionary Algorithm (YEN and LU, 2003); MOGA I1 – Multi-objective Genetic

45

Algorithm (SILVA, 2004); PAMUC – Preferences Applied to Multiobjectivity and

Constraints (COELHO, 2004).

Conforme descrevemos anteriormente, na literatura existem vários

algoritmos de otimização multi-objetivos que foram testados e tiveram sua

eficiência aprovada por pesquisadores das mais diversas áreas em todo o mundo.

O que diferencia um algoritmo evolutivo de otimização multi-objetivo de outro são

os mecanismos que cada um utiliza para encontrar a aptidão das soluções, o

mecanismo de elitismo e a diversidade das soluções. Neste contexto

apresentaremos alguns algoritmos evolutivos ressaltando as estratégias utilizadas

por eles para a realização dos mecanismos mencionados.

6.4.1 MOGA ( Multi-Objective Genetic Algorithms)

Este algoritmo foi proposto por FONSECA and FLEMING (1993) e utiliza o

conceito de dominância e diversidade para as soluções obtidas em cada geração.

O ranking de uma solução x i é calculado pela equação:

ri=1+ni

onde ni é o número de soluções que dominam a solução x i. Assim, as soluções

que são não-dominadas possuem ranking 1 e o valor máximo para o ranking não

ultrapassa o tamanho da população (N pop).

A próxima etapa realizada pelo MOGA é o ordenamento das soluções

quanto ao valor do ranking. Um mesmo valor de aptidão é, denominado aptidão

média, é atribuído às soluções de mesmo ranking e as soluções melhores

ranqueadas possuem valores maiores de aptidão, para que seja garantido o

mecanismo de elitismo na seleção dos indivíduos.

Para garantir a diversidade entre as soluções não-dominadas, é usado o

conceito de nichos em cada ranking. Após obtidos os nichos, calcula-se um novo

valor de aptidão. Este valor é denominado aptidão compartilhada e é calculada

para todas as soluções em cada ranking. Após isto, este valor é multiplicado por

um fator de escala:

F i'=μ (ri)F i

∑j=1

μ(ri)

F j'

46

onde μ(r i) é o número de soluções no ranking ri. Após calculada a aptidão, pela

última fórmula, o MOGA realiza as operações usuais de um algoritmos genético:

seleção, cruzamento e mutação.

Também é usado o conceito de contador de nicho no MOGA. Para cada

solução x i, o contador é calculado através da fórmula:

nc i=∑j=1

μ(ri)

Sh(d ij)

d ij=√∑k=1

m ( f k (x i)− f k (x j )f kmax−f k

min )2

onde d ij é a distância euclidiana entre as soluções x i e x j que possuem o mesmo

valor de ranking, f kmax e f k

min são os valores máximo e mínimo, respectivamente,

para a k-ésima função objetivo. A função Sh foi proposta por GOLDBERG (1989)

e é chamada de função de compartilhamento. É definida por:

Sh (d ij)={1−( dijσ share )

α

se d ij≤σ share

0casocontrário

O valor do parâmetro α define como será o comportamento da função de

compartilhamento e σ shareé denominado raio de nicho. Este raio define uma região

em torno de uma solução, sendo que soluções que satisfazem d ij>σ share, estão em

nichos diferentes e Sh (d ij)=0. De acordo com a definição do contador de nicho,

maiores valores de nc i significam mais soluções dentro do mesmo nicho. Calcula-

se a aptidão compartilhada de cada solução x i pela equação:

F i'=F i

nci

De acordo com a fórmula anterior, soluções que estão em nichos menos

ocupados possuirão valores de aptidão compartilhada maiores. Isto influencia no

mecanismo de diversidade.

A seguir destacamos a estrutura do Algoritmo MOGA: Estrutura do Algoritmo MOGA

Dados de entrada:Tamanho da População (N pop) e Parâmetro de Compartilhamento(σ share)

Passosi. Geração da População Inicial;

ii. Inicializar os contadores μ (ri )=0, para todos os rankings;

47

Realizar até que extrapole o número de gerações.iii. Calcular o valor de ri para todas as soluções x i;

iv. Incrementar μ (ri );Início de um laço para calculo da aptidão final

v. Ordenar a população de forma descrescente em relação aos valores de ri. Identificar r¿=max (r¿¿ i)¿. Calcular, para cada solução, um valor de aptidão média. Fazer r=1;

vi. Para cada solução x i com ri=r, calcular nc i;vii. Calcular a aptidão final;viii. Se r<r ¿, fazer r=r+1 e voltar ao passo vi. ;

Fim do laçoix. Realização das operações usuais dos AG;x. Substituição da População;xi. Volta ao passo iii.

Dados de saída: SoluçõesNão−Dominadas

_________________________________________________________________Figura 6.4.1 –Estrutura do Algoritmo MOGA

Segundo DEB (2001) o algoritmo MOGA o valor de aptidão para as

soluções é facilmente calculado, ajudando assim na eficiência computacional do

algoritmo e segundo COELHO (2003) o MOGA possui melhor desempenho que

outros algoritmos não elitistas. Conforme podemos observar nos cálculos das

aptidões, não necessariamente, soluções com alto valor de ranking ri podem ter

pior valor de aptidão que soluções com ri mais baixo. Isto acontece quando

existem muitas soluções, próximas entre si com valor de ri baixo, sendo o valor de

contador de nicho alto neste caso e, portanto aptidão compartilhada baixa. Isto

mostra um ponto negativo do MOGA, o processo de seleção não é bom e

portanto pode haver dificuldade na convergência.

6.4.2 NPGA ( Niched Pareto Genetic Algorithms)

O NPGA também é um algoritmo que é fundamentado no conceito de não

dominância da sua população e foi proposto por HORN et al. (1994). Neste

algoritmo não é faz-se necessário calcular a aptidão das soluções para uma

posterior seleção dos mais aptos para reprodução. Neste algoritmo é realizado

um mecanismo de seleção por torneio denominado Torneio de Pareto. Neste

mecanismo, duas soluções potenciais, escolhidas aleatoriamente na população,

48

são comparadas com um subconjunto da população. Assim podem haver apenas

as seguintes situações:

A solução x i domina todas soluções do subpopulação S e a solução x j é

dominada por alguma solução de S, então a solução x i vence o torneio. A

solução x j é a vencedora se x j domina S e se x i é dominada por alguma

solução de S;

Pode ocorrer de nenhuma das soluções dominarem S, ou que pelo menos

uma solução em S domine x i e x j. Assim calcula-se o contador de nicho e

escolhe-se a solução vencedora.

O cálculo do nicho é feito sobre a nova população filha gerada (Q). Assim

no início do processo, Q não possui nenhuma solução e, portanto o cálculo de

nicho não é realizado e caso haja empate entre as soluções, a solução vencedora

é escolhida de forma aleatória. Cada par de soluções vencedoras gera um par de

soluções filhas e estas são incluídas no conjunto Q. A partir da primeira geração,

o cálculo de nicho pode ser realizado de forma análoga ao processo descrito no

algoritmo MOGA.

A seguir destacamos a estrutura do Algoritmo NPGA:

Estrutura do Algoritmo NPGADados de entrada:

Tamanho da População (N pop) e Parâmetro de Compartilhamento(σ share),

Tamanho do torneio (t dom), Geração atual (n), Máximo de Gerações(nMax)

Passosi. Geração da População Pai Inicial P e da população filha Q vazia;

Laço para realização do Torneio.ii. Fazer n=1;iii. Fazer t=0;iv. Realizar a seleção pelo Torneio de Pareto nos indivíduos x i e x i+1

e o ganhador será o pai p1. Fazer i=i+2;

v. Realizar a seleção pelo Torneio de Pareto nos indivíduos x i e x i+1

e o ganhador será o pai p2;

vi. Realizar o cruzamento entre p1 e p2 gerando os filhos c1 e c2;vii. Aplicar o operador de mutação;viii. Atualizar a população filha Qn=Q n∪{c1,c2 };ix. Fazer t=t+1

x. Se t<t dom voltar ao passo iv. Senão terminar torneio.

49

xi. Misturar a população pai Pn à população filha Qn formando uma nova população pai;

xii. Fazer n=n+1;xiii. Se n=nMaxterminar. Senão Qn+1={}, e voltar ao passo iii.

Dados de saída: SoluçõesNão−Dominadas_________________________________________________________________

Figura 6.4.2 –Estrutura do Algoritmo NPGA

A principal vantagem do algoritmo NPGA é o fato dele não necessitar

calcular um valor de aptidão para as soluções (DEB, 2001). Quando o parâmetro

tamanho do torneio t dom é pequeno (quando comparado ao tamanho da

população), o operador de seleção por Torneio de Pareto realiza poucas

comparações e portanto torna o algoritmo eficiente no quesito tempo

computacional. A desvantagem é a incorporação dos termos σ share e t dom.

6.4.3 NSGA II ( Non-Dominated Sorting Genetic Algorithms)

Este é com certeza um dos algoritmos mais famosos entre os algoritmos multi-

objetivo. O algoritmo NSGA II é uma extensão do algoritmo NSGA e foi proposto

por DEB et al. (2000). Utiliza, como muitos outros, o conceito de dominância para

realizar um ordenamento das suas soluções para posterior seleção elitista.

Trabalha com uma população pai P e uma população filha Q. A população inicial

é ordenada por não dominância e a aptidão de cada solução é igual ao seu valor

de não dominância. Através dos operadores convencionais dos AG (seleção por

torneio, cruzamento e mutação) é obtida uma população filha Q0, de mesmo

tamanho da população pai. Em seguida realiza-se a união entre as populações

pai e filha em um mesmo conjunto R0. Na n-ésima geração o NSGA II trabalha

com uma população Rn com o dobro do tamanho da população inicial (N pop¿. A

próxima etapa do NSGA II é o ordenamento por não dominância das soluções.

Obtém-se subconjuntos ordenados F1, F2 ,…, Ft que serão inseridos na próxima

população pai Pn+1. Como observamos anteriormente, o tamanho da população

atual em Rn é 2N pop e somente N pop soluções podem ser inseridas na próxima

geração pai. Assim N pop soluções devem ser descartadas. Insere-se primeiro as

soluções do conjunto F1, depois do F2 e assim sucessivamente, até alcançar o

50

número de soluções N pop, sendo que possivelmente algumas soluções deverão

ser descartadas. A figura, abaixo, mostra uma representação do esquema

descrito acima.

Figura 6.4.3 – Esquema de Elitismo no NSGA II

Reproduzido de LOBATO (2008)

As soluções contidas nos conjuntos F i devem ser inseridas em Pn+1 até que

|Pn+1|+|F i|≤ N pop. Com certeza vamos ter o primeiro (estão ordenados por não-

dominância) conjunto F j tal que |Pn+1|+|F j|>N pop. Quando isto acontecer o

algoritmo NSGA II implementa um método chamado de distancia de multidão para

selecionar as N pop−|Pn+1| soluções de F j que estejam melhor espalhadas.

Este mecanismo de corte de soluções, ou melhor, de escolha das melhores

soluções (no sentido de diversidade) consiste em ordenar decrescentemente o

conjunto F j em relação às suas distâncias, e inserindo as primeiras N pop−|Pn+1|soluções em Pn+1.

O operador denominado distância de multidão d i, calculado para cada

solução x i em F j, é uma estimativa do perímetro do cuboide formado pelos

vértices de seus dois vizinhos mais próximos. Quanto maior o valor da distância

de multidão d i, mais afastado está a solução x i dos seus vizinhos e os valores

extremos em cada objetivo terão cuboide infinito. LOBATO (2008) mostra como

calcular a distância de multidão d ide uma solução x i.

A seguir apresentamos a estrutura do Algoritmo NPGA:

51

Estrutura do Algoritmo NSGA IIDados de entrada:

Tamanho da População (N pop), Geração atual (n), Máximo de Gerações(nMax)

Passosi. Geração da População Pai Inicial P e da população filha Q vazia;ii. Fazer n=0;iii. Realizar a seleção, cruzamento e mutação para gerar a

população filha Qn. Fazer Rn=Pn∪Qn;

iv. Ordenar Rn por não dominância e criar Pn+1={};v. Enquanto |Pn+1|+|F i|≤ N pop, copiar as soluções de F i em Pn+1;

vi. Calcular a distância de multidão para cada solução em F j,

ordenando F j de acordo com a ordem decrescente de d i em

seguida copia-se as primeiras N pop−|Pn+1| de F j para Pn+1;

vii. Fazer n=n+1;viii. Se n=nMaxentão terminar. Senão volte ao passo iii.

Dados de saída: SoluçõesNão−Dominadas_________________________________________________________________

Figura 6.4.4 –Estrutura do Algoritmo NSGA II

Um dos principais fatores que levaram o NSGA II a gozar de certo prestígio

entre os pesquisadores é a forma que ele mantém a diversidade das soluções via

o operador de distância de multidão. Outro fato interessante é que não há

nenhum parâmetro de controle como o parâmetro σ share no MOGA e os parâmetros

σ share e t dom no NPGA. O ponto negativo do NSGA II é quando o conjunto F1 possui

mais elementos que N pop e assim o processo de corte de soluções deverá eliminar

soluções não dominadas. Considere, em uma situação hipotética, um caso onde

|F1|>N pop e existam várias soluções ótimas de Pareto bem próximas e uma

solução, não ótima de Pareto, mas também não dominada até o momento, que

esteja um pouco mais distante. O processo de corte pela distância de multidão vai

eliminar uma solução ótima de Pareto, na região mais densa descrita

anteriormente, e copiará para Pn+1 a solução não dominada cujo cuboide é maior.

Esta situação está ilustrada nas figuras 6.4.5 (a) e 6.4.5 (b) abaixo. Mas segundo

DEB et al. (2000) este problema não afeta seriamente a convergência do

algoritmo para um conjunto de soluções ótimas de Pareto.

52

Figura 6.4.5 – Situação problema no algoritmo NSGA II.

Reproduzido de LOBATO (2008).

Capítulo 7_________________________________Problemas Testes

Neste capítulo realizaremos a simulação da heurística FireFly (otimização por

vagalumes) em alguns problemas matemáticos mono-objetivo e de problemas

multi-objetivo em engenharia. Os problemas matemáticos mono-objetivos que

53

estudaremos, são problemas reconhecidamente difíceis de encontrarmos o ótimo

global, pois, em alguns casos possuem vários ótimos locais (multimodais). Os

problemas multi-objetivo a serem tratados são os famosos problemas introduzidos

por ZITZLER et al. (2000) (ZDT1, ZDT2, ZDT3 e ZDT4).

7.1 Problemas Teste

Os primeiros três problemas são mono-objetivos e podem ser encontrados

em KOSIEL & MICHALEWICZ (1999) e foram escolhidos devido à dificuldade

obvia, observada pelos gráficos e pelas suas expressões analíticas, de serem

otimizadas. Os outros quatro problemas são problemas multi-objetivos clássicos e

foram extraídos de LOBATO (2008).

Os problemas multi-objetivos foram apresentados originalmente por

ZITZLER et al. (2000). Por terem solução analítica conhecida, são muito

empregados na literatura na validação de novos algoritmos propostos. São

conhecidos pela denominação ZDT1, ZDT2, ZDT3, ZDT4, ZDT5 e ZDT6.

Faremos um estudo dos quatro primeiros problemas. Todos casos multi-objetivo

tem-se que as variáveis são definidas no intervalo (0,1) e o número de variáveis é

limitada a cinco.

7.1.1Problema Teste 1

Minimizar

T 1 (x1 , x2 )=x1 sin 4 x1+1.1x2 sin 2x2 0≤x1≤10 0≤x2≤10

Este é um problema sem restrições. A função acima é conhecida na

literatura como função Haupt & Haupt (HAUPT & HAUPT, 1998). Podemos

observar através do gráfico função T 1, abaixo, que esta possui vários pontos de

mínimo locais e um único ponto de mínimo global, o ponto (x1 , x2)=(9.039 ,8.668)

com T 1(9.039 ,8.668)=−18.5547.

54

Figura 7.1.1 - Gráfico da função do problema teste 1

7.1.2Problema Teste 2

Minimizar

T 2 (x1 , x2 )=−cos x1cos x2 exp (−(x1−π )2−(x2−π )2)

Sujeito às seguintes restrições laterais

−30≤ x1≤30−30≤x2≤30

Podemos observar pelo gráfico da função T 3, abaixo, que esta apresenta

um único mínimo global. Este ponto de mínimo global é o ponto (π ,π ), com

T 3 (π ,π )=−1. Este é um belo exemplo para mostrar que métodos de otimização

determinísticos, às vezes, na funcionam tão bem. O gráfico desta função é quase

plano numa região muito grande e também é plana próximo ao ótimo global. Por

isto, métodos que utilizam a informação da derivada não funcionam para esta

função.

55

Figura 7.1.2 – Gráfico da função do problema teste 2

7.1.3Problema Teste 3

Minimizar

T 3 (x1 , x2 )=x12+x2

2−cos (18x1 )−cos (18 x2 )

Sujeito às seguintes restrições laterais

−1≤x1≤1e−1≤x2≤1

A função T 3, a ser minimizada, apresenta vários ótimos locais(mais de

cinquenta) e um mínimo global igual a −2. Abaixo apresentamos o gráfico da

função teste três:

56

Figura 7.1.3 – Gráfico da função do problema teste 3

7.1.4Problema Teste 4

O problema ZDT1 é dado pelas seguintes expressões:

ZDT 1={ f 1 (x1 )=x1

g (x2 ,…,xm )=1+9

m−1∑i=2

m

x i

h( f 1 (x1 ) , g (x2 ,…, xm ))=1−√ f 1 (x1 )/ g (x2 ,…, xm )

A região ótima de Pareto, no espaço de projetos, é a seguinte região:

x1∈(0,1) e x i=0 , i=2 ,…,m.

Nosso objetivo é encontrar a solução ótima (Curva de Pareto) do seguinte

problema com dois objetivos e com cinco variáveis de projeto:

ZDT 1={ min f 1(x1)min f 2 ( x1 ,…, x5 )=h ( f 1 (x1 ) , g ( x2 ,…, x4 ))

57

7.1.5Problema Teste 5

O problema ZDT2 é dado pelas funções:

ZDT 2={ f 1 (x1 )=x1

g (x2 ,…,xm )=1+9

m−1∑i=2

m

x i

h( f 1 (x1 ) , g (x2 ,…,xm ))=1−( f 1 (x1 )/g ( x2 ,…, xm ))2

A região ótima de Pareto, no espaço de projetos, também corresponde a

região: x1∈(0,1) e x i=0 , i=2 ,…,m, mas, neste caso, a fronteira de Pareto é não

convexa.

Nosso objetivo é encontrar a solução ótima (Curva de Pareto) do seguinte

problema com dois objetivos e com cinco variáveis de projeto:

ZDT 2={ min f 1(x1)min f 2 (x1 ,…, x5 )=h ( f 1 (x1 ) , g (x2 ,…, x4 ))

7.1.6Problema Teste 6

O problema ZDT3 é dado pelas funções:

ZDT 3 {f 1 (x1 )=x1

g (x2 ,…, xm )=1+ 9m−1

∑i=2

m

x i

h ( f 1 (x1 ) , g ( x2 ,…, xm ))=1−√ f 1 (x1 )g (x2,…, xm )

−f 1 (x1)

g (x2 ,…,xm )sin(10 π f 1 (x1 ))

A região ótima de Pareto, no espaço de projetos, também corresponde a

região: x1∈(0,1) e x i=0 , i=2 ,…,m, mas, neste caso, a fronteira de Pareto é não

convexa.

58

Nosso objetivo é encontrar a solução ótima (Curva de Pareto) do seguinte

problema com dois objetivos e com cinco variáveis de projeto:

ZDT 3={ min f 1(x1)min f 2 (x1 ,…, x5 )=h ( f 1 (x1 ) , g (x2,…, x4 ))

7.1.7Problema Teste 7

O problema ZDT4 é dado pelas funções abaixo. Possui uma grande quantidade

de ótimos locais (cerca de 219). Assim este problema é um grande desafio para

qualquer algoritmo de otimização global.

ZDT 4={f 1 (x1 )=x1

g (x2 ,…,xm )=1+10 (m−1 )+∑i=2

m

(x i2−10 cos (4 π x i))

h ( f 1 (x1) , g (x2 ,…, xm ))=1−√ f 1 (x1 )g (x2 ,…,xm )

A região ótima de Pareto, no espaço de projetos, também corresponde a

região: x1∈(0,1) e x i=0 , i=2 ,…,m, mas, neste caso, a fronteira de Pareto é não

convexa.

Nosso objetivo é encontrar a solução ótima (Curva de Pareto) do seguinte

problema com dois objetivos e com cinco variáveis de projeto:

ZDT 4={ min f 1(x1)min f 2 (x1 ,…, x5 )=h ( f 1 (x1 ) , g (x2 ,…, x4 ))

Capítulo 8

59

_________________________________Resultados e Discussão Neste capítulo apresentaremos os resultados e discussões para os sete

problemas descritos no capítulo anterior. Os primeiros três problemas são mono-

objetivo e os últimos quatro são multi-objetivo. A meta Heurística utilizada na

simulação de todos os problemas testes é a emergente heurística baseada no

comportamento de uma colônia de vagalumes denominada apenas por FireFly.

8.1 Resultados e Discussão do Problema Teste 1

Em uma simulação usamos os seguintes parâmetros no algoritmo FireFly:

Coeficiente de atratividade máxima: β0=1;

Coeficiente de absorção do brilho emitido pelos vagalumes: γ=1;

Coeficiente de inserção de aleatoriedade na movimentação dos

vagalumes: α=0.7;

População inicial: N pop=50;

Número máximo de iterações: N iter−max=200.

O resultados obtidos para esta simulação foram:

Variáveis de Projeto – (x (1 ) , x (2))=(9.038965399393 ,8.668116906805 );

Valor da Função Objetivo - T 1 (x (1 ) , x (2))=−18.554720928163746;

Avaliações da Função Objetivo – 529.050.

8.2 Resultados e Discussão do Problema Teste 2

Em uma simulação inicial usamos os seguintes parâmetros no algoritmo FireFly:

Coeficiente de atratividade máxima: β0=1;

Coeficiente de absorção do brilho emitido pelos vagalumes: γ=1;

Coeficiente de inserção de aleatoriedade na movimentação dos

vagalumes: α=0.5;

População inicial: N pop=50;

Número máximo de iterações: N iter−max=250.

Os resultados obtidos para esta simulação foram:

Variáveis de Projeto – (x (1 ) , x (2))=(3.141597071886 ,3.141598683271 );

60

Valor da Função Objetivo - T 2 (x (1 ) , x (2))=−0.999999999916182;

Avaliações da Função Objetivo – 661.050.

Podemos observar que os valores obtidos na simulação do algoritmo

FireFly conferem com os valores da literatura para esta função específica.

Queremos agora verificar se há influência do fator β0 (fator de atratividade)

no número de iterações necessárias para a convergência do algoritmo. Para isto

vamos variar o fator de atratividade de zero a um em um passo de variação igual

a 0.1. Os outros fatores foram mantidos constantes e iguais aos da simulação

para o primeiro caso. O critério de convergência utilizado é a obtenção de cinco

casas decimais iguais à solução real. Os resultados obtidos estão na Tabela

8.2.1.

Influência do fator de atratividade no número de iterações para a convergência

Fator β0Número de Iterações Avaliações da Função Objetivo

β0=0.0 1500 3.970.900

β0=0.1 1200 3.177.200

β0=0.2 1000 2.642.000

β0=0.3 600 1.588.550

β0=0.4 600 1.588.550

β0=0.5 500 1.314.650

β0=0.6 500 1.314.650

β0=0.7 500 1.314.650

β0=0.8 330 864.350

β0=0.9 300 790.700

β0=1.0 250 659.350

Tabela 8.2.1 – Influência do fator de atratividade no número de iterações

para convergência do algoritmo FireFly.

Pelos dados da tabela acima, que foram encontrados pela simulação do

algoritmo FireFly com os parâmetros informados, concluímos que há influência do

fator de atratividade β0 no número de iterações necessárias (em média) para a

61

convergência do algoritmo. Esta conclusão está em concordância com o valor de

β0 adotado na literatura.

8.3 Resultados e Discussão do Problema Teste 3

Em uma simulação inicial usamos os seguintes parâmetros no algoritmo FireFly:

Coeficiente de atratividade máxima: β0=1;

Coeficiente de absorção do brilho emitido pelos vagalumes: γ=1;

Coeficiente de inserção de aleatoriedade na movimentação dos

vagalumes: α=0.8;

População inicial: N pop=100;

Número máximo de iterações: N iter−max=200.

Os resultados obtidos para esta simulação foram:

Variáveis de Projeto – (x (1 ) , x (2))=10−4 (0.0131359832 ,−0.3588762036 );

Valor da Função Objetivo - T 3 (x (1 ) , x (2))=−1.999999789787573;

Avaliações da Função Objetivo – 2.038 .100.

Queremos agora verificar se há influência do fator N pop (Tamanho da

População) no número de iterações necessárias para a convergência do

algoritmo. Para isto vamos variar o tamanho da população de dez a cento e

cinquenta em um passo de variação igual a vinte unidades. Os outros fatores

foram mantidos constantes e iguais aos da simulação para o primeiro caso. Os

resultados obtidos estão na Tabela 8.3.1.

Influência do tamanho da população no número de iterações para a convergência

Fator N popNúmero de Iterações Avaliações da Função Objetivo

N pop=10 1500 314.800

N pop=30 700 720.430

N pop=50 200 529.050

N pop=70 80 404.270

N pop=90 30 246.990

N pop=110 20 244.110

62

N pop=130 10 170.130

Tabela 8.3.1 – Influência do fator de absorção no número de iterações para

convergência do algoritmo FireFly.

A partir dos resultados da tabela acima podemos observar que o algoritmo

de otimização por colônia de vagalumes FireFly responde bem ao aumento do

tamanho da população de vagalumes. Neste caso específico, o número de

variáveis é pequeno e o tamanho do espaço de busca também. O aumento do

número de indivíduos da população inicial implica automaticamente no aumento

da complexidade do algoritmo e consequentemente no aumento do custo do

tempo computacional, mas, neste caso, o aumento do custo computacional não

foi significativo.

8.4 Resultados e Discussão do Problema Teste 4

Em nossa simulação usamos os seguintes parâmetros no algoritmo FireFly:

Coeficiente de atratividade máxima: β0=1;

Coeficiente de absorção do brilho emitido pelos vagalumes: γ=1;

Coeficiente de inserção de aleatoriedade na movimentação dos

vagalumes: α=0.8;

População inicial: N pop=100;

Número máximo de iterações: N iter−max=200.

Nas figuras 8.4.1 e 8.4.2 estão apresentados os perfis da população inicial

da nossa simulação e da curva solução obtida para o problema ZDT1,

respectivamente:

63

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

f1(x1)

f 2(x1,

...,

x5)

Generation --> 100

Figura 8.4.1 – Curva solução para o problema ZDT1.

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

1

2

3

4

5

6

f1(x

1)

f 2(x1,

...,

x5)

Generation Initial Population--> 1

Figura 8.4.2 – Espalhamento da população inicial de 100 indivíduos

A seguir apresentaremos os resultados das métricas de desempenho para

o algoritmo FireFly. Comparamos com alguns resultados da literatura extraídos de

LOBATO (2008), onde o autor compara um algoritmo baseado na Heurística

64

Evolução Diferencial denominado MODE (Multi-Objective Differential Evolution)

com o famoso algoritmo multi-objetivo baseado em Algoritmos Genéticos

denominado NSGA II.

Métricas de Desempenho para o problema ZDT1

Métrica NSGA II MODE MO-FireFly

Υ 0.0008 0.0016 0.00051517

DGer0.0006 0.0001 0.00012215

Δ 0.4632 0.1988 0.8360

Tabela 8.4.3 – Avaliação e Comparação das métricas de desempenho do

algoritmo MO-FireFly (MO – Multi-Objective) em relação aos algoritmos

NSGAII e MODE

8.5 Resultados e Discussão do Problema Teste 5

Em nossa simulação usamos os seguintes parâmetros no algoritmo FireFly:

Coeficiente de atratividade máxima: β0=1;

Coeficiente de absorção do brilho emitido pelos vagalumes: γ=2;

Coeficiente de inserção de aleatoriedade na movimentação dos

vagalumes: α=1.0;

População inicial: N pop=100;

Número máximo de iterações: N iter−max=100.

Nas figuras 8.5.1 e 8.5.2 estão apresentados os perfis da população inicial

da nossa simulação e da curva solução obtida para o problema ZDT2,

respectivamente:

65

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

f1(x1)

f 2(x1,

...,

x5)

Generation --> 100

Figura 8.5.1 – Curva solução para o problema ZDT2.

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

1

2

3

4

5

6

7

8

9

f1(x1)

f 2(x1,

...,

x5)

Generation Initial Population--> 1

Figura 8.5.2 – Espalhamento da população inicial de 100 indivíduos

A seguir apresentaremos os resultados das métricas de desempenho para

o algoritmo FireFly. Comparamos com alguns resultados da literatura extraídos de

66

LOBATO (2008), onde o autor compara um algoritmo baseado na Heurística

Evolução Diferencial denominado MODE (Multi-Objective Differential Evolution)

com o famoso algoritmo multi-objetivo baseado em Algoritmos Genéticos

denominado NSGA II.

Métricas de Desempenho para o problema ZDT2

Métrica NSGA II MODE MO-FireFly

Υ 0.0008 0.0011 0.00042460

DGer0.0006 0.0001 0.000048804

Δ 0.4632 0.1988 0.4799

Tabela 8.5.3 – Avaliação e Comparação das métricas de desempenho do

algoritmo MO-FireFly (MO – Multi-Objective) em relação aos algoritmos

NSGAII e MODE

8.6 Resultados e Discussão do Problema Teste 6

Em nossa simulação usamos os seguintes parâmetros no algoritmo FireFly:

Coeficiente de atratividade máxima: β0=1;

Coeficiente de absorção do brilho emitido pelos vagalumes: γ=1;

Coeficiente de inserção de aleatoriedade na movimentação dos

vagalumes: α=0.5;

População inicial: N pop=100;

Número máximo de iterações: N iter−max=100.

Nas figuras 8.6.1 e 8.6.2 estão apresentados os perfis da população inicial

da nossa simulação e da curva solução obtida para o problema ZDT3,

respectivamente:

67

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9-0.8

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

1

f1(x

1)

f 2(x1,

...,

x5)

Generation --> 100

Figura 8.6.1 – Curva solução para o problema ZDT3.

Observe que as soluções obtidas estão marcadas com um “+” azul, que está

marcado juntamente com a solução do problema que está representado na figura

acima através de uma “o” (bolinha) vermelha.

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1-1

0

1

2

3

4

5

6

f1(x

1)

f 2(x1,

...,

x5)

Generation Initial Population --> 1

Figura 8.6.2 – Espalhamento da população inicial de 100 indivíduos

68

Os pontos marcados em vermelho representam a curva de Pareto do

Problema ZDT3, que para este caso é descontínua.

A seguir apresentaremos os resultados das métricas de desempenho para

o algoritmo FireFly. Comparamos com alguns resultados da literatura extraídos de

LOBATO (2008), onde o autor compara um algoritmo baseado na Heurística

Evolução Diferencial denominado MODE (Multi-Objective Differential Evolution)

com o famoso algoritmo multi-objetivo baseado em Algoritmos Genéticos,

denominado NSGA II.

Métricas de Desempenho para o problema ZDT3

Métrica NSGA II MODE MO-FireFly

Υ 0.0434 0.0010 0.00045355

DGer0.0005 0.0001 0.000059762

Δ 0.5756 0.2881 0.6596

Tabela 8.6.3 – Avaliação e Comparação das métricas de desempenho do

algoritmo MO-FireFly (MO – Multi-Objective) em relação aos algoritmos

NSGAII e MODE

8.7 Resultados e Discussão do Problema Teste 7

Em nossa simulação usamos os seguintes parâmetros no algoritmo FireFly:

Coeficiente de atratividade máxima: β0=1;

Coeficiente de absorção do brilho emitido pelos vagalumes: γ=1;

Coeficiente de inserção de aleatoriedade na movimentação dos

vagalumes: α=1.0;

População inicial: N pop=100;

Número máximo de iterações: N iter−max=100.

Nas figuras 8.7.1 e 8.7.2 estão apresentados os perfis da população inicial

da nossa simulação e da curva solução obtida para o problema ZDT4,

respectivamente:

69

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

f1(x

1)

f 2(x1,

...,

x5)

Generation --> 100

Figura 8.7.1 – Curva solução para o problema ZDT4.

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

5

10

15

20

25

30

35

f1(x1)

f 2(x1,

...,

x5)

Generation Initial Population --> 1

Figura 8.7.2 – Espalhamento da população inicial de 100 indivíduos

70

A seguir apresentaremos os resultados das métricas de desempenho para

o algoritmo FireFly. Comparamos com alguns resultados da literatura extraídos de

LOBATO (2008), onde o autor compara um algoritmo baseado na Heurística

Evolução Diferencial denominado MODE (Multi-Objective Differential Evolution)

com o famoso algoritmo multi-objetivo baseado em Algoritmos Genéticos

denominado NSGA II.

Métricas de Desempenho para o problema ZDT4

Métrica NSGA II MODE MO-FireFly

Υ 0.0434 0.0010 0.00045855

DGer0.0002 0.0001 0.000078133

Δ 0.5756 0.2881 0.7552

Tabela 8.7.3 – Avaliação e Comparação das métricas de desempenho do

algoritmo MO-FireFly (MO – Multi-Objective) em relação aos algoritmos

NSGAII e MODE

A seguir apresentaremos uma sequência de quadros que mostram como

se dá o comportamento da movimentação da população de vagalumes na busca

pela curva de Pareto com o passar das gerações. No título de cada quadro será

mostrado qual é o número exato da geração de vagalumes que está nele

representado.

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

10

20

30

40

50

60

f1(x1)

f 2(x1, .

.., x

5)

Generation --> 1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

5

10

15

20

25

f1(x1)

f 2(x1, .

.., x

5)

Generation --> 2

71

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

1

2

3

4

5

6

f1(x

1)

f 2(x1, .

.., x

5)

Generation --> 4

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.5

1

1.5

2

2.5

3

3.5

f1(x

1)

f 2(x1, .

.., x

5)

Generation --> 6

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

f1(x

1)

f 2(x1, .

.., x

5)

Generation --> 7

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

f1(x

1)

f 2(x1, .

.., x

5)

Generation --> 8

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

f1(x

1)

f 2(x1, .

.., x

5)

Generation --> 10

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

f1(x

1)

f 2(x1, .

.., x

5)

Generation --> 12

72

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

f1(x1)

f 2(x1, .

.., x

5)

Generation --> 15

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

f1(x1)

f 2(x1, .

.., x

5)

Generation --> 18

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

f1(x1)

f 2(x1, .

.., x

5)

Generation --> 21

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

f1(x1)

f 2(x1, .

.., x

5)Generation --> 25

Figura 8.7.4 – Movimentação dos vagalumes ao longo de algumas gerações.

Através dos quadros acima, notamos que a partir da décima geração o

algoritmo já convergiu para à curva de Pareto e nas gerações seguintes o

algoritmo realizou a tarefa de “espalhar” melhor as soluções sobre a curva

solução, garantindo assim uma boa diversidade das soluções. A partir da

vigésima geração já não conseguimos, a olho nu, notar diferença entre as curvas

soluções obtida pelo algoritmo. Apenas para servir de comparação com a

centésima geração, os valores das métricas de desempenho para a décima quinta

geração são:

Υ=0 .00037558 , DGer=0.00050895 e Δ=0.5941. Assim notamos que o trabalho

realizado pelo algoritmo a partir das quinze primeiras gerações é apenas na

73

questão da melhora (muito pouco) da convergência e do espalhamento das

soluções.

Referências Bibliográficas

ALI, A.; MAJHI, S., Design of Optimum PID Controller by Bacterial Foraging

Strategy. Proceedings of the IEEE International Conference on Industrial Techno-

logy (ICIT - 2006) pp. 601–605.

BABU, B. V., CHAKOLE, P. G., MUBEEN, J. H. S., Multiobjective differential

evolution (mode) for optimization of adiabatic styrene reactor, Chemical Engi-

neering Science, 60 (2005), 4822-4837.

CASTRO, R.E. Otimização de Estruturas com Multi-Objetivos via Algoritmos

Genéticos. Tese (Doutorado) – Departamento de Engenharia Civil –

COPPE/UFRJ, 2001.

COELHO, R. F. Multi-Criteria Optimization With Expert Rules for Mecanical

Design. Tese de Doutorado. Université Libre de Bruxelles, Faculté des Sciences

Appliqueés, 2004.

CORNE, D.W., KNOWLES, J.D., OATES, M.J. The Pareto Envelope-based Se-

lection Algorithm for Multiobjective Optimization. In: Proceedings of the Paral-

lel Problem Solving from Nature VI Conference, Springer. Lecture Notes in Com-

puter Science. Paris – France: M. Schoenauer, K. Deb, G. Rudolph, X. Yao, E.

Lutton, J.J. Merelo e H.-P. Scwefel (eds), 2000.

CORNE, D.W., JERRAM, N.R., KNOWLES, J.D., OATES, M.J. Pesa-ii Region-

based Selection in Evolutionary Multiobjective Optimization. In: Proceedings

of the Genetic an Evolutionay Computation Conference, Morgan Kaufmann Pub-

lishers. San Francisco – California: L. Spector, E. D. Goodman, A. Wu, W. Lang-

don, H.-M. Voigt, M. Gen, S. Sen , M. Dorigo, S. Pezeshk, M.H. Garzon e E. Burke

(eds), 2001.

DEB, K., AGRAWAL, S., PRATAB, A., MEYARIVAN, T.A. Fast Elitist Non-Domi-

nated Genetic Algorithm for Multi-Objective Optimization: NSGA – II. Kanpur

– India, 2000.

DEB, K. Multi-objective optimization using Evolutionary Algorithms. John

Wiley & Sons, Inc., pág.77-80 e 129-135. 2001.

74

DOERNER, K., GUTJAHR, W.J., HARTL, R.F., STRAUSS, C., STUMMER, C. Ant

Colony Optimization in Multiobjective Portifolio. In: Proceedings of the 4th

Metaheuristics International Conference, July 16-20, 2001, 243-248. USA: Souza

J.P. (ed), MIC2001, 2001.

EDGEWORTH, F.Y. Mathematical Physics. First Edition. London, England: P.

Keagan, 1881.

ENCYCLOPEDIA BRITANNICA, Firefly. In: Encyclopedia Britannica. Ultimate

Reference Suite. Chicago: Encyclopedia Britannica (2009).

FANG, H., RAIS-ROHANI, M., LUI, Z., HORSTEMEYER, M.F. A Comparative

Study of Metamodeling Methods for Multiobjective Crashworthiness Opti-

mization. Computers and Structures, v.83, pp 2121-2136, 2005.

FIGUEIREDO, D. G. de,. Problemas de Máximo e Mínimo na Geometria

Euclidiana. Revista Matemática Universitária/SBM, N° 9/10, Rio de Janeiro, 1989.

FONSECA, C.M., FLEMING, P.J. Genetic Algorithms for Multi-objective

Optimization: Formulation, Discussion and Generalization. In: Proceedings of

the Fifth International Conference on Genetic Algorithms. USA, Gen93, 1993.

GANDIBLEUX, X., MEZDAOUI, N., FREVILLE, A. A Tabu Search Procedure to

Solve Multiobjective Combinatorial Optimization Procedures. In: Advances in

Multiple Objective and Goal Programming, Lecture Notes in Economics and Math-

ematical Systems 455, 291-300. Springer-Verlag: Cabalero R. Ruiz F. and Steuer

R. (eds), 1997.

GOLDBERG, D. E.; Genetic Algorithms in Search. Optimization and Machine

Learning. EUA: Addison-Wesley. 1989.

HAUPT, R.L., HAUPT, S.E. Practical Genetic Algorithms. John Wiley & Sons,

Inc., Hoboken, New Jersey. 1998.

HORN, J., NAFPLIOTIS, N., GOLDBERG, D.E. A Niched Pareto Genetic Algo-

rithm for Multiobjective Optimization. In: Proceedings of the First IEEE Confer-

ence on Evolutionary Computation. Florida – USA: IEEE World Congress on

Computational Intelligence, 1994.

IZMAILOV, A., SOLODOV, M. Otimização, volume 1, Condições de

otimalidade, Elementos de Análise Convexa e de Dualidade. Rio de Janeiro,

SBM-IMPA. 2005.

JUMADINOVA, J., DASGUPTA, P., Firefly-inspired synchronization for im-

proved dynamic pricing in online markets. In: Proceedings of the 2008 Second

75

IEEE International Conference on Self-Adaptive and Self-Organizing Systems.

(2008) 403-412.

KENNEDY, J., EBERHART, R. C., Particle Swarm Optimization. Proceedings of

the 1995 IEEE International Conference on Neural Networks, Perth, Australia,

1995,pp. 1942-1948.

KNOWLES, J.D., CORNE, D.W. Approximating the Nondominate Front Using

the Pareto Archived Evolution Estrategy. Evolutionary Computation, v8, n2,

pp149-172, 2000.

KOZIEL, S.; MICHALEWICZ Z. Evolutionary algorithms, homomorphous map-

pings, and constrained parameter optimization. Evolutionary Computation,

Cambridge, v.7, p. 19-44, 1999.

KRINK, T; LOVEMBERG, M. The Life Cycle Model: Combining Particle Swarm,

Genetic Algorithms and Hill Climbers. Lecture Notes and Computer Science.

Vol.2439, pp.621-630. 2004.

KRISHNANAND, K., GHOSE, D., Glowworm swarm based optimization algo-

rithm for multimodal functions with collective robotics applications. Multia-

gent and Grid Systems 2(3) (2006) 209-222.

LEIDENFROST, R., ELMENREICH, W., Establishing wireless time-triggered

communication using a firefly clock synchronization approach. In: Proceed-

ings of the 2008 International Workshop on Intelligent Solutions in Embedded Sys-

tems. (2008) 1-18.

LOBATO, F. S. Otimização Multi-objetivo para o projeto de sistemas em

engenharia. Tese de Doutorado, Universidade Federal de Uberlândia, FEMEC,

2008.

MARTINEZ, J.M.; SANTOS, S.A. Métodos Computacionais de Otimização. XX

Colóquio Brasileiro de Matemática – IMPA, Rio de Janeiro, 1995. pág. 256.

MOREIRA, C.G.T. de A.; SALDANHA, N.C. A Desigualdade Isoperimétrica.

Revista Matemática Universitária/SBM, N° 15, Rio de Janeiro, 1993.

MOREIRA, F. R. O Método de Newton: Uma Análise de Convergência Local e

Semi-Local. O Teorema de Kantorovich. Dissertação de Mestrado em

Matemática. Universidade Federal de Goiás. 2006.

MURRAY, J., Mathematical Biology: An Introduction. Secausus, NJ, USA:

Springer-Verlag, New York. 2002.

76

OSYCZKA, A. Multicriterion Optimization in Engineering with Fortram Pro-

grams. First Edition. England. Ellis Horwood Limited, 1984.

PARETO, V. Cours D’Economie Politique. First Edition. França. Vol. I and II. F.

Rouge, Lausanne, 1896.

PASSINO, K.M., Biomimicry of bacterial foraging for distributed optimization

and control. IEEE Control Systems Magazine, Vol. 22, No. 3, 2002, pp. 52–67.

ROJAS ,J.E., VIANA, F.A.C., RADE, D.A., STEFFEN Jr., V. Identification of Ex-

ternal Forces in Mechanical Systems by Using LifeCycle Model and Stress-

Stiffening Effect. Mechanical Systems and Signal Processing, Vol. 21 (7), pp.

2900-2917, 2007.

SCHAFFER, J.D. Multi Objective Optimization with Vector Evaluated Genetic

Algorithms. Tese de Doutorado.. Vanderbilt University, 1984.

SILVA, V.V. da. Ordenamento do corpo dos complexos C. Revista da

Olimpíada de Matemática do Estado de Goiás (OMEG). IME-UFG. Editora da

UFG. 2003.

SILVA, C.M. Desenvolvimento de um Algoritmo de Otimização Multiobjetivo

usando Algoritmos Genéticos. Tese (Doutorado) – Universidade Federal do Rio

de Janeiro, 2004.

SRINIVAS, N., DEB, K. Multiobjective Optimization Using Nondominated

Sorting in Genetic Algorithms. Evolutionary Computation, v.2, n.3, p.221-248,

1994.

VANDERPLAATS, G. N., Numerical optimization techniques for engineering

design: with applications. McGraw-Hill.1984.

VENTER, G. and SOBIESZCZANSKI-SOBIESKI, J., Particle Swarm Optimiza-

tion, Proceedings of the 43rd AIAA/ASME/ASCE/AHS/ASC Structures, Structural

Dynamics, and Materials Conference, Denver, CO, Vol. AIAA-2002-1235, April 22-

25 2002.

VIANA, F. A. C. Surrogate Modeling Techniques and Optimization Methods

Applied to Design and Identification Problems. Tese de Doutorado. Universi-

dade Federal de Uberlândia. FEMEC, 2008.

VIANA, F.A.C., MACIEL, B.C.O., NETO, N.S.B., OLIVEIRA, M.F., STEFFEN Jr,

V., GÓES, L.C.S. Aircraft Longitudinal Stability and Control Derivatives Iden-

tification by Using Life Cycle and Levenberg-Marquardt Optimization Algo-

77

rithms. Inverse Problems in Science and Engineering, Vol. 17 (1), pp. 17-34.

2009.

YANG, X.S., Nature-Inspired Metaheuristic Algorithms. Luniver Press (2008).

YEN, G. G., LU, H. Dynamic Multiobjective Evolutionary Algorithm: Adapta-

tive Cell-based Rank and Densit Estimation. IEEE Transactions Evolutionary

Computation, v.7, n.3, pp.253-274, 2003.

ZITZLER, E., THIELE, L. An Evolutionary Algorithm for Multiobjective Opti-

mization: The Strength Pareto Approach. TIK-Report No. 43, 1998.

ZITZLER, E., DEB, K., THIELE, L. Comparison of multiobjective evolutionary

algorithms: Empirical results. Evolutionary Computation Journal, v.8, n.2,

pp.125-148, 2000.

ZITZLER, E., LAUMANNS, M., THIELE, L. SPEA II: Improving the Strength

Pareto Evolutionary Algorithm. Zurich – Switzerland, 2001. Computer Engineer-

ing and Networks Laboratory (TIK). Swiss Federal Isntitute of Technology (ETH)

Zurich, Gloriastrasse 35, CH-8092.