UNIVERSIDADE ESTADUAL DE MONTES CLAROS UNIMONTES CENTRO DE CINCIAS EXATAS E TECNOLGICAS CCET

ESPECIALIZAO EM ENGENHARIA DE SISTEMAS

Samuel Cruz Guimares

PROPOSTA DE UM SISTEMA MULTIAGENTE EVOLUTIVO

BASEADO EM ALGORITMOS GENTICOS

E EVOLUO DIFERENCIAL

Montes Claros MG 2015

Samuel Cruz Guimares

PROPOSTA DE UM SISTEMA MULTIAGENTE EVOLUTIVO

BASEADO EM ALGORITMOS GENTICOS

E EVOLUO DIFERENCIAL

Monografia apresentada Universidade

Estadual de Montes Claros, como requisito

parcial para a concluso do curso de

Especializao em Engenharia de Sistemas.

Orientador: Me. Allysson Steve Mota Lacerda

Montes Claros MG 2015

RESUMO

Problemas de otimizao so facilmente encontrados nas mais diversas reas do conhecimento,

com diferentes especificidades e nveis de complexidade. Devido a isso, a definio do melhor

mtodo para resoluo de tais problemas pode ser bastante difcil, pois o desempenho de cada

um ir depender, principalmente, da natureza do problema. Alm disso, a popularizao de

computadores com mltiplos ncleos ou processadores tem incentivado o desenvolvimento de

algoritmos paralelizveis, como os Sistemas Multiagente. Este trabalho prope um Sistema

Multiagente Evolutivo baseado em ilhas, utilizando Algoritmos Genticos e Evoluo

Diferencial, para a soluo de problemas no lineares. Experimentos realizados mostraram que

o mtodo proposto apresentou bons resultados quando comparado a outros algoritmos

disponveis na literatura, especialmente em problemas com maior complexidade ou maior

dimenso.

Palavras-chave: Sistemas MultiAgente Evolutivos, Algoritmos Genticos, Evoluo

Diferencial, Computao Natural, Otimizao.

ABSTRACT

Optimization problems can be easily found in several areas of knowledge, with different levels

of complexity and specificities. For this reason, it can be difficult to choose a resolution

methods to these problems, since its performance will depend mainly on the nature of the

problem. Furthermore, the increasing use of multi-core computers leads to the development of

new parallel algorithms, like multiagent systems. This paper aims to develop an Evolutionary

MultiAgent System based on an island model, using Genetic Algorithms and Differential

Evolution to solve nonlinear problems. Experiments showed that the proposed method showed

good results when compared to other algorithms available in the literature, especially in

problems with more complex or larger.

Keywords: MultiAgent Systems. Evolutionary MultiAgent Systems. Differential Evolution

Genetic Algorithms. Evolutionary Computation. Natural Computing. Optimization.

LISTA DE FIGURAS

Figura 1: Pseudocdigo de um AG. ......................................................................................... 12

Figura 2: Fluxograma que sintetiza um AG. ............................................................................ 13

Figura 3: Fluxograma que sintetiza um ED. ............................................................................. 15

Figura 4: Pseudocdigo de um ED. .......................................................................................... 16

Figura 5: Representao grfica da mutao do algoritmo de ED. .......................................... 17

Figura 6: Componentes de um Sistema de Agente. .................................................................. 21

Figura 7: Utilizao de AE pelos agentes individualmente e pela populao de agentes. ....... 22

Figura 8: Representao grfica da funo de Rastrigin bidimensional. ................................. 32

Figura 9: Acompanhamento do progresso do AG. ................................................................... 33

Figura 10: Acompanhamento do progresso do ED. ................................................................. 33

SUMRIO

1 INTRODUO .................................................................................................................. 6

2 FUNDAMENTAO TERICA ..................................................................................... 9

2.1 ALGORITMOS GENTICOS ................................................................................... 9

2.1.1 ESTRUTURA DO ALGORITMO ....................................................................... 11

2.2 EVOLUO DIFERENCIAL ................................................................................. 13

2.2.1 IMPLEMENTAO PADRO DO ALGORITMO DE ED .............................. 15

2.2.2 VARIANTES ....................................................................................................... 18

2.3 SISTEMA MULTIAGENTE EVOLUTIVO ........................................................... 19

2.3.1 MODELAGEM DOS PROCESSOS EVOLUTIVOS NOS SMAE .................... 24

3 MODELAGEM E DESENVOLVIMENTO .................................................................... 26

3.1 ALGORITMO GENTICO ..................................................................................... 26

3.2 ALGORITMO DE EVOLUO DIFERENCIAL .................................................. 28

3.3 SISTEMA MULTIAGENTE EVOLUTIVO ........................................................... 29

4 EXPERIMENTOS E RESULTADOS OBTIDOS ........................................................... 32

4.1 FUNO RASTRIGIN ........................................................................................... 32

4.2 EXPERIMENTOS REALIZADOS .......................................................................... 32

5 CONCLUSES ................................................................................................................ 37

REFERNCIAS BIBLIOGRFICAS ..................................................................................... 39

6

1 INTRODUO

A otimizao pode ser definida como a tentativa de se produzir o melhor resultado (resposta)

possvel para uma determinada situao, segundo um critrio de avaliao previamente

definido. Geralmente definida como uma busca, e no importando a rea de atuao, sempre

tem como objetivo encontrar a melhor soluo dentre todas as solues possveis (espao de

solues), por intermdio da maximizao ou minimizao de uma funo objetivo (LINDEN,

2006). A definio de melhor relativa ao problema proposto, s tolerncias aceitas e aos

mtodos utilizados para resoluo e avaliao.

Problemas de otimizao so facilmente encontrados nas mais diversas reas do conhecimento,

com diferentes especificidades e nveis de complexidade. Devido a isso, a escolha do mtodo

pode ser de difcil determinao, pois o desempenho de cada um vai depender, principalmente,

da natureza do problema. O teorema No Free Lunch para algoritmos de otimizao nos

mostra o quo difcil e improvvel a criao de uma estratgia de otimizao que seja

universalmente eficiente. (WOLPERT & MACREADY, 1997) (HO & PEYNE, 2001)

Uma das abordagens mais estudadas na Otimizao so as metaheursticas baseadas na

Computao Natural, das quais os Algoritmos Evolucionrios (ou Evolutivos) (AE), fazem

parte. Os Algoritmos Evolutivos so tcnicas inspiradas no princpio Darwiniano da evoluo

das espcies e na gentica (GOLDBERG, 1989). Metaheursticas so procedimentos genricos

de alto nvel que fazem uso de aleatoriedade em diversas estratgias heursticas visando

encontrar boas solues para o problema considerado (BLUM & ROLI, 2003).

Destacam-se entre as diversas abordagens dos AE os Algoritmos Genticos (AG) e a Evoluo

Diferencial (ED). Os AG foram propostos por HOLLAND (1975) e so fortemente baseados

no processo de seleo natural e evoluo das espcies. Em suma, prope que os indivduos

mais aptos e suas caractersticas tem maiores chances de prevalecer pelas geraes

subsequentes, enquanto os mais fracos (menos aptos) tendem a desaparecer. O mtodo da ED

criado por STORN & PRICE (1995) tem como ideia principal a gerao de novos indivduos,

denominados vetores, por intermdio do procedimento de adicionar um vetor diferena

ponderada entre outros dois vetores aleatrios.

7

Os mtodos citados at o momento nesse trabalho tm obtido bons resultados na resoluo de

muitos problemas de otimizao global. Ainda assim, pode-se deparar com inadequaes

devido crescente complexidade dos problemas e limitaes impostas pelo poder de

processamento dos computadores atuais. Com o intuito de contornar ou pelo menos amenizar

essas complexidades e limitaes, cada vez mais, vm sendo explorados mtodos que se

adaptem bem paralelizao, podendo assim tirar proveito dos processadores com mltiplos

ncleos e/ou do uso da computao distribuda. O processamento paralelo tem o intuito de

dividir uma tarefa grande ou complexa em partes menores que tenham menor custo

computacional. (ALMASI & GOTTLIEB, 1989)

Seguindo essa linha de pesquisa, podemos citar uma outra abordagem muita explorada

atualmente, os Sistemas Multiagentes (SMA). Essa abordagem viabiliza e adequa-se a

resoluo de problemas complexos e de natureza descentralizada. Os SMA adotam o conceito

de agente como uma unidade autnoma de resoluo de problemas. O agrupamento desses

agentes para trabalharem cooperativamente, cada um resolvendo parte do problema e

interagindo com o ambiente onde esto inseridos, caracteriza os SMA. (WOOLDRIDGE &

JENNINGS, 1995)

Inspirados nos Sistemas Multiagente, surgiram os Sistemas Multiagente Evolutivos (SMAE),

que so um tipo de SMA que implementam sobre seus agentes os operados presentes nas demais

abordagens evolutivas, como seleo, cruzamento e mutao.

Comumente os SMA e SMAE utilizam o modelo de ilhas, no qual os agentes so distribudos

em subpopulaes que evoluem de forma independente na busca da soluo do problema

proposto. A troca de informaes entre ilhas ocorre, principalmente, por meio da migrao de

agentes entre elas.

O presente trabalho tem como objetivo principal desenvolver e avaliar um Sistema Multiagente

Evolutivo em um modelo de ilhas, utilizando as metaheursticas de Algoritmos Genticos e

Evoluo Diferencial, para resoluo de problemas de otimizao no linear. Este trabalho

tambm objetiva comparar o desempenho do SMAE proposto, com os algoritmos utilizados em

suas ilhas, AG e ED, isoladamente.

8

O restante desse trabalho est organizado da seguinte forma: o segundo captulo apresenta a

fundamentao terica utilizada para o seu desenvolvimento, abordando assuntos pertinentes

otimizao e heursticas utilizadas pelos algoritmos. No terceiro captulo apresentada a

implementao do trabalho, descrevendo a metodologia utilizada nos algoritmos. O quarto

captulo apresenta as implantaes, os testes, os resultados obtidos e faz uma comparao entre

o SMAE e os algoritmos de AG e ED isoladamente. Por fim, o quinto captulo traz as

concluses, dificuldades encontradas e os trabalhos futuros.

9

2 FUNDAMENTAO TERICA

2.1 ALGORITMOS GENTICOS

Os Algoritmos Genticos (AG) foram desenvolvidos por John Holland e sua equipe, na

Universidade de Michigan, em 1975. Originalmente, os AG estavam muito fortemente ligados

a modelos de aprendizado automtico, como demonstrada na nfase dada por HOLLAND

(1975) aos chamados sistemas classificadores, que so um modelo de mquina de aprendizado

usando AG. Posteriormente GOLDBERG (1989) passou a utilizar a ideia de otimizao como

tema central na teoria dos AG. Por esses motivos que, ao contrrio de outras abordagens

evolutivas, os AG conceitualmente apresentam um escopo mais amplo do que a simples

otimizao, sendo apresentados como um modelo para a aprendizagem de mquina por

HEITKOETTER & BEASLEY (1994).

Os AG so o ramo mais conhecido da Computao Evolutiva (CE), sendo eles algoritmos de

otimizao global, baseados nos mecanismos de gentica e seleo natural (GOLDBERG,

1989), (LINDEN, 2006). So um mecanismo de busca de solues que utilizam combinaes

de melhores solues - melhores pais - de uma determinada gerao, com o objetivo de obter

novas solues - filhos - para a gerao seguinte. Os filhos devem apresentar resultados mais

eficientes para a funo de avaliao, funo essa que a responsvel por manter a gerao

contnua de melhores solues para o problema.

A base de um algoritmo gentico pode ser definida por: um procedimento de descoberta de

bons blocos, seleo desses blocos e construo de novos blocos a partir desses, sendo que a

ideia principal que cada novo bloco gerado a partir de outros bons blocos, ser melhor que os

blocos geradores. (HOLLAND, 1975)

Assim sendo, LINDEN (2006) conclui que os AG no constituem um algoritmo de busca da

soluo tima de um problema, mas sim uma metaheurstica que encontra, de forma

probabilstica, um conjunto de boas solues a cada execuo.

Os AG empregam uma estratgia de busca paralela e estruturada, mas aleatria, que voltada

em direo ao reforo da busca de pontos de alta aptido, ou seja, pontos nos quais a funo

10

a ser minimizada (ou maximizada) tm valores relativamente baixos (ou altos) (BRAGA et al.,

2000). Portanto, apesar de aleatrios, eles no so caminhadas aleatrias no direcionadas, pois

exploram informaes histricas para encontrar novos pontos de busca onde so esperados

melhores desempenhos.

A vantagem principal dos AG ao trabalharem com o conceito de populao, ao contrrio de

muitos outros mtodos que trabalham com um s ponto, que eles encontram segurana na

quantidade. Tendo uma populao de pontos bem adaptados, a possibilidade de alcanar um

falso timo torna-se menor.

O conceito de mnimo/mximo local (ou falso timo) acontece quando o algoritmo converge

para uma regio que possui uma soluo local e a explora at que encontre seu melhor valor,

ignorando, porm, o restante do espao de busca.

A seguir descrevemos os conceitos fundamentais da gentica que so utilizados nos AG:

Cromossomo ou Indivduo: uma possvel soluo para o problema em questo,

codificada, de acordo com um modelo selecionado, com informaes do problema a

ser resolvido.

Gene: parte de uma soluo. Por exemplo, supondo um vetor [1, 3, 2] como uma

soluo proposta para o problema, pode-se dizer que o 3 um gene do cromossomo.

Fitness: demonstra o quo adaptado um determinado individuo a situao qual

ele est exposto. No caso dos AG representa o valor obtido pela funo de avaliao

sobre aquele determinado indivduo (ou soluo).

Funo de Avaliao: a funo objetivo do problema em questo, que deve avaliar

cada soluo proposta e determinar a probabilidade da sua permanncia no grupo de

solues admissveis (timas) para o problema.

Populao: conjunto de solues propostas, presentes numa determinada etapa da

execuo do AG.

Cruzamento: processo de reproduo de indivduos, no qual os indivduos filhos

(solues propostas para a gerao seguinte) so construdos a partir de genes obtidos

dos pais (solues propostas atuais).

11

Mutao: processo de modificao aleatria de um ou mais genes contidos em uma

determinada soluo (cromossomo), que aplicada nos AG, visam evitar os problemas

de mnimos locais e convergncia rpida, diversificando os indivduos da populao

corrente.

Seleo: processo de separao dos indivduos que possuem uma melhor resposta

funo de avaliao daqueles que no possuem boas avaliaes, para que os melhores

originem os indivduos da gerao seguinte.

Populao Inicial: o conjunto inicial de solues para o problema, o ponto de

partida da execuo do AG. A partir desses indivduos, aplicando os operadores

genticos, so gerados os indivduos das geraes futuras. Geralmente esses

indivduos recebem valores aleatrios.

Condio de Parada: condio que deve ser satisfeita para que o algoritmo gentico

pare de executar, condio essa, que deve ser determinada de acordo com o problema

a ser resolvido. Usualmente, essa condio um nmero que representa a quantidade

mxima de iteraes sobre as quais o AG deve ser executado.

2.1.1 ESTRUTURA DO ALGORITMO

necessrio observar uma sequncia de passos para a utilizao de AG em problemas de

otimizao e busca.

O primeiro passo deve ser a codificao ou representao, ou seja, deve ser determinado como

os indivduos sero codificados. A codificao da informao em cromossomos um ponto

crucial dentro do AG, e , junto com a funo de avaliao, o que liga o AG ao problema a ser

resolvido.

O prximo passo a gerao da populao inicial. Durante o processo evolutivo, a populao

avaliada, sendo que para cada indivduo dada uma nota, ou ndice, refletindo sua habilidade

de adaptao a um determinado ambiente.

O processo de seleo determina quais indivduos da populao podem participar da fase de

reproduo. Os indivduos so selecionados de acordo com uma probabilidade dada pelos

ndices ou notas de aptido.

12

Os indivduos escolhidos na fase de seleo participam da fase de reproduo, em que podem

ser combinados e modificados, produzindo os indivduos da prxima gerao. Essas

combinaes e modificaes so realizadas pelo conjunto de operadores genticos.

Depois de concludas essas etapas, a nova gerao formada novamente submetida avaliao,

e assim ser feito at o ponto de parada do algoritmo.

De acordo com os passos vistos acima, o AG, em linhas gerais, pode ser descrito pelo

pseudocdigo da Figura 1.

Figura 1: Pseudocdigo de um AG.

A Figura 2 modela exatamente a situao proposta no algoritmo. Obviamente esta somente

uma viso de alto nvel do algoritmo. O que ela esconde a complexidade do processo de

obteno de uma representao cromossomial que seja adequada ao problema e de uma funo

de avaliao que penalize solues implausveis para nosso problema e que avalie

satisfatoriamente o grau de adequabilidade de cada indivduo como soluo do problema em

questo (LINDEN, 2006).

Define populao inicial P

ENQUANTO condio de parada = falso

Seleo(P)

Cruzamento(P)

Mutao(P)

FIM

13

Figura 2: Fluxograma que sintetiza um AG.

No sero citados, tampouco detalhados, os tipos de representao cromossmica, operadores

genticos e demais mtodos possveis de utilizao nos AG, j que estes no fazem parte do

espoco principal do trabalho. Apenas sero mencionados, no captulo 3, os tipos utilizados na

implementao do algoritmo proposto e utilizado para os testes do trabalho.

2.2 EVOLUO DIFERENCIAL

O algoritmo de Evoluo Diferencial foi desenvolvido por Storn e Price, inicialmente em 1995

e surgiu a partir de tentativas para resolver o problema de ajuste polinomial de Chebychev

(STORN & PRICE,1995). Esse algoritmo introduz uma abordagem um pouco diferente dos

demais AE. Prope usar a diferena de vetores para perturbar a populao de indivduos

(demais vetores) o que, segundo STORN & PRICE (2013), resulta em um mtodo que requer

poucas variveis, de rpida convergncia, simples e robusto.

Sim

Incio

Inicializa Parmetros

Populao Inicial

Funo de Avaliao Mutao

Cruzamento

Seleo

Trmino Fim da Busca?

No

14

O mtodo consiste em gerar aleatoriamente uma populao de indivduos, denominados de

vetores, onde cada um representa um ponto de busca no espao de solues potenciais de um

dado problema. Em geral, esta populao inicial criada por meio de uma distribuio de

probabilidade uniforme, quando no h nenhum conhecimento sobre o problema.

A populao inicial sofre modificaes durante suas interaes dando lugar a uma nova

populao de mesmo tamanho, e assim vrias interaes so realizadas at que o processo de

otimizao seja encerrado. Segundo OLIVEIRA (2006), estas modificaes ocorrem com uma

gerao de novos vetores modificados ou doadores, por intermdio da adio da diferena

ponderada entre dois indivduos aleatrios da populao a um terceiro indivduo tambm

escolhido aleatoriamente. Essa operao corresponde ao operador de mutao.

Escolhe-se aleatoriamente outro vetor, denominado vetor alvo, cujos componentes so

misturados com os componentes do vetor doador, resultando no vetor chamado vetor tentativa,

vetor experimental ou vetor candidato. Este processo de misturar os componentes

correspondente ao operador de cruzamento.

Se o valor da funo objetivo aplicada ao vetor candidato for melhor do que o valor dela

aplicada ao vetor alvo, ento o vetor candidato substitui o vetor alvo na gerao seguinte. Caso

contrrio, o vetor alvo mantido na prxima gerao. Esta ltima operao corresponde ao

operador de seleo.

O procedimento de otimizao continua at que algum critrio de parada seja satisfeito. Na

Figura 3, um fluxograma apresenta uma sntese dos procedimentos citados anteriormente com

as principais etapas do algoritmo de ED.

15

Figura 3: Fluxograma que sintetiza um ED.

Abaixo, algumas caractersticas do algoritmo que o tornam candidato otimizao de

problemas numricos. (OLIVEIRA, 2006)

Parmetros de entrada e sada so representados como nmeros reais, evitando

overhead;

Tende a no se prender a timos locais;

Custo computacional potencialmente baixo, pois eficiente com populaes

pequenas.

2.2.1 IMPLEMENTAO PADRO DO ALGORITMO DE ED

O algoritmo padro pode ser representado pelo pseudocdigo da Figura 4.

Incio

Inicializa Parmetros

Populao Inicial (Vetores Alvos)

Funo de Avaliao Seleo

Cruzamento (Vetores Candidatos)

Mutao (Vetores Doadores)

Trmino Fim da Busca?

Sim

No

16

Figura 4: Pseudocdigo de um ED.

Um algoritmo de ED pode ser implementado inicializando-se um conjunto de vetores de

nmeros reais que representam possveis solues para o problema. Cada nmero real

representa um parmetro da funo a ser otimizada, cada uma possuindo um limite mnimo e

mximo, para evitar solues fora do escopo de busca. Em seguida, o conjunto iterado e cada

vetor sofre as operaes de mutao, cruzamento e seleo. O processo se repete at que um

critrio de parada seja alcanado. Em cada iterao, o vetor observado denominado vetor alvo

(Va).

Os operadores da evoluo diferencial se baseiam no princpio da evoluo natural cujos

objetivos so manter a diversidade da populao, evitar convergncias prematuras e obter a

melhor soluo. (OLIVEIRA, 2006). A seguir apresentaremos os principais operadores

utilizados pelo algoritmo de ED.

2.2.1.1 MUTAO

Para a realizao da mutao, trs vetores distintos V1, V2 e V3 (diferentes tambm do vetor

alvo) so selecionados aleatoriamente na populao. Definimos um valor arbitrrio, pertencente

ao intervalo [0, 2], para o fator de mutao (Fm), que controla a amplitude do vetor diferena.

Obtemos o vetor doador (Vd) multiplicando Fm pela diferena entre V2 e V3, e somando o

resultado a V1.

O clculo de Vd pode ser representado por:

= 1 + (2 3) (1)

Define populao inicial P

ENQUANTO condio de parada = falso

PARA cada indivduo Va de P

Define V1, V2 e V3

Vd = Mutao(V1,V2,V3)

Vc = Cruzamento(Va,Vd)

Seleo(Va,Vc)

FIM

FIM

17

Com base na descrio do operador pode-se concluir que o nmero de vetores no conjunto

(tamanho da populao) deve ser maior ou igual a 4, para que a mutao seja vivel. (STORN

& PRICE, 1995). A Figura 5 mostra uma representao do operador de mutao do ED.

Figura 5: Representao grfica da mutao do algoritmo de ED.

2.2.1.2 CRUZAMENTO

No processo de cruzamento, um vetor candidato (Vc) criado combinando elementos do vetor

doador (Vd) e do vetor alvo (Va). Cada elemento do vetor doador tem uma chance de participar

do vetor candidato determinada pela probabilidade de cruzamento (Pc). Se a posio observada

do vetor doador no participar do vetor candidato, um elemento do vetor alvo ser utilizado no

lugar. Podemos representar esse processo de cruzamento por intermdio da equao:

() = {(), (), >

= 1, , (2)

Este mtodo de cruzamento denominado binomial. Uma variao deste mtodo que veio a

surgir depois, o cruzamento exponencial, dita que elementos do vetor doador sejam utilizados

at que o primeiro nmero aleatrio seja maior que Pc, sendo que todos os prximos sero do

vetor alvo. De acordo com STORN & PRICE (2013), o cruzamento binomial nunca ser pior

que o cruzamento exponencial.

18

2.2.1.3 SELEO

Depois de construdo, o vetor candidato ento comparado ao vetor alvo, por meio dos valores

da funo objetivo aplicado a cada um, e o substituir na prxima gerao caso represente uma

melhor soluo para o problema.

() (()), (+1) =

() > (()), (+1) = () (3)

A seleo o processo de produzir filhos melhores. Diferentemente de outros algoritmos

evolutivos, a evoluo diferencial no usa hierarquia (elitismo) nem seleo proporcional.

(OLIVEIRA, 2006)

2.2.2 VARIANTES

Alm da estrutura bsica apresentada, variantes dos operadores possibilitam diferentes

implementaes do algoritmo, podendo apresentar vantagens de acordo com o problema

proposto. Algumas variaes possveis para os operadores so:

Mutao:

o Escolher V1 baseado em algum critrio especfico e no aleatoriamente. Ex.:

melhor vetor do conjunto.

o Utilizar 2 (dois) vetores diferenciais (diferenas ponderadas), para isso o mnimo

de indivduos da populao passa a ser 6 (seis).

Cruzamento:

o Binrio: para cada posio do vetor candidato, h uma chance de ser usado um

elemento do vetor doador.

o Exponencial: o vetor candidato preenchido como no binrio, porm ao

primeiro elemento do vetor alvo utilizado, todos os prximos elementos tambm

derivam dele.

Com o intuito de classificar essas variantes STORN & PRICE (1995) introduziram a seguinte

notao:

19

///

Onde:

a - especifica o critrio de escolha do vetor a ser mutado V1, rand para escolha aleatria ou best

para escolha do vetor de menor custo.

b - especifica o nmero de vetores diferena (direes) utilizados na etapa de mutao.

c - especifica o esquema de cruzamento adotado, bin para cruzamento binomial ou exp para

cruzamento exponencial.

Utilizando dessa notao, podemos definir a implementao padro proposta por Storn e Price,

e descrita acima, como: //1/.

A eficincia do algoritmo tambm pode ser otimizada ajustando-se os parmetros principais:

tamanho da populao, fator de mutao e probabilidade de cruzamento. Cada tipo de problema

melhor resolvido utilizando-se uma combinao especfica desses, a ser descoberta com base

em testes e anlise dos resultados.

2.3 SISTEMA MULTIAGENTE EVOLUTIVO

No existe uma definio exclusiva para o termo agente, mas dentre os principais autores da

rea de Inteligncia Artificial Distribuda (IAD) podemos extrair de consenso a ideia central de

autonomia (WOOLDRIDGE, 1999). E autonomia pode ser visto como a capacidade de realizar

aes sem (ou com o mnimo possvel) de intervenes de outros agentes computacionais ou

humanos.

A existncia de vrios tipos de agentes para os vrios domnios de aplicao possveis,

justificam a pluralidade encontrada nas definies.

Adotaremos como definio o seguinte: Um agente um sistema computacional inserido em

algum ambiente, e que capaz de agir de forma autnoma nesse ambiente, a fim de cumprir os

objetivos do projeto. (WOOLDRIDGE, 1999)

20

Para WOOLDRIDGE & JENNINGS (1995), um agente uma entidade que encapsula

conhecimentos sobre algum domnio e os define como tendo as seguintes propriedades:

Autonomia: os agentes operam sem a interveno direta de seres humanos ou outros,

e tem controle sobre suas aes e estado interno;

Habilidade social: os agentes interagem com outros agentes (computacionais e/ou

humanos) por meio de algum tipo de comunicao;

Capacidade de reao: os agentes percebem o ambiente que esto inseridos e reagem

em tempo hbil s mudanas que nele ocorrem;

Capacidade pr-ativa: os agentes so capazes de apresentar um comportamento

orientado a objetivos ao tomarem iniciativas.

Alm dessas propriedades, pode-se tambm destacar a temporalidade (o agente decide se

permanece ou no em um ambiente), adaptabilidade (capacidade de se adaptar s modificaes

do ambiente), mobilidade (capacidade de locomoo entre ambientes), entre outras.

A Figura 6 apresenta a interao global entre uma agente e o ambiente onde est inserido. Juntos

so conhecidos como Sistema de Agente.

O agente recebe estmulos do ambiente e reage a esses estmulos. Um agente constitudo por

um corpo e um controlador. O controlador recebe percepes do corpo e envia comandos para

o corpo. O corpo inclui sensores que convertem estmulos em percepes e atuadores que

convertem comandos em aes. (POOLE & MACKWORTH, 2010)

21

Figura 6: Componentes de um Sistema de Agente.

Apesar de um agente encapsular informaes sobre algum domnio, cada vez mais raro a

ocorrncia desse agente possuir todo o conhecimento necessrio para resolver problemas sem

o auxlio de outrem. Isso em muito se deve ao crescimento da complexidade dos problemas, a

necessidade de tratamento de grandes quantidades de dados e o fato de alguns problemas terem

a sua prpria natureza distribuda.

Sendo assim, o agrupamento de agentes com capacidades especficas pode ser usado, com o

intuito de complementarem suas capacidades, para resoluo de problemas que um nico agente

seria insuficiente.

ZAMBONELLI et al. (2000) distingue duas classes principais de sistemas com mltiplos

agentes: (i) Sistemas de Resoluo Distribuda de Problemas, nos quais os agentes envolvidos

so explicitamente projetados para, de maneira cooperativa, atingirem um dado objetivo,

considerando-se que todos eles so conhecidos a priori e supondo que todos so benevolentes,

existindo desta forma confiana mtua em relao s suas interaes; e (ii) Sistemas Abertos,

nos quais os agentes no so necessariamente projetados para atingirem um objetivo comum,

podendo ingressar e sair do sistema de maneira dinmica. Neste caso, a chegada dinmica de

agentes desconhecidos precisa ser levada em considerao, bem como a possvel existncia de

comportamento no benevolente no curso das interaes.

22

Os Sistemas Multiagentes (SMA) se enquadram na classificao de Sistemas Abertos, pois

caracterizam-se por possuir um conjunto de agentes autnomos que interagem objetivando a

resoluo de um problema que est alm das capacidades de um nico agente.

Segundo JENNINGS (1996), os SMA apresentam diversas vantagens se comparados s

solues convencionais:

Maior rapidez na resoluo de problemas por intermdio da possibilidade de

aproveitamento do paralelismo;

Diminuio da comunicao por transmitir somente solues parciais em alto nvel

para outros agentes ao invs de dados brutos para um lugar central;

Mais flexibilidade por ter agentes de diferentes habilidades que so dinamicamente

agrupados para resolver problemas;

Aumento da segurana pela possibilidade de agentes assumirem responsabilidades

de agentes que falham.

Entre os muitos assuntos relacionados com os SMA pode-se encontrar tambm a computao

evolutiva. Em muitos dos casos um AE utilizado por um agente para auxiliar na realizao de

alguma de suas funes, ou para apoiar alguma atividade em grupo (Figura 7 (a)). No entanto,

resultados interessantes vm sendo encontrados ao aplicar modelos evolutivos ao nvel da

populao, ou seja, entre os agentes (Figura 7 (b)). Essa nova classe de SMA chamada de

Sistema Multiagente Evolutivo (SMAE). (BYRSKI et al., 2014)

Figura 7: Utilizao de AE pelos agentes individualmente e pela populao de agentes.

A ideia fundamental do SMAE a incorporao de processos evolutivos em um SMA ao nvel

da populao de agentes. Isto significa que alm de mecanismos de interao tpicos de SMA

23

(tais como a comunicao), os agentes so capazes de se reproduzir (gerar novos agentes) e

podem morrer (serem eliminados do sistema/ambiente). Um fator decisivo da atividade de um

agente a sua aptido, expressa pela quantidade que possui de um recurso no renovvel

chamado energia vital. A seleo realizada de tal forma que os agentes com alta energia so

mais suscetveis de se reproduzir, enquanto aumenta a possibilidade de morte para os agentes

com baixa energia.

A avaliao do comportamento dos agentes e mecanismos de seleo levam ao surgimento de

uma populao mais ajustada com relao ao objetivo do sistema. O resultado formado como

uma simples composio de resultados obtidos por agentes particulares. A arquitetura do

SMAE homognea, o que significa que os agentes so idnticos, no sentido de algoritmo e

aes internas. (KISIEL-DOROHINICKI et al., 2003)

A principal vantagem do SMAE, em relao a outros mtodos evolutivos, que ele abrange

vrias tcnicas especializadas em um modelo coerente. (KISIEL-DOROHINICKI, 2002)

De acordo com os paradigmas neodarwinistas, os dois principais componentes do processo de

evoluo so herana (com mudanas aleatrias da informao gentica por meio de mutao

e cruzamento) e seleo. Nos SMAE, eles so implementados pelos fenmenos de morte e

reproduo, que podem ser modelados com as seguintes aes executadas pelos agentes:

Ao de morte resulta na eliminao do agente do sistema;

Ao de reproduo simplesmente produo de um novo agente a partir do seu(s)

pai(s).

A seleo o elemento mais importante e difcil do modelo de evoluo empregado nos SMAE.

Os SMAE comumente utilizam de um recurso denominado energia vital para seleo dos

agentes mais aptos ao ambiente. A energia adquirida e perdida quando os agentes executam

aes no meio ambiente que esto inseridos. O aumento de energia uma recompensa por um

"bom" comportamento de um agente, j a sua diminuio, uma penalidade para um "mau"

comportamento (a definio do que pode ser considerado um "bom" ou "mau" comportamento

depende do problema a ser resolvido). Ao mesmo tempo, o nvel de energia determina as aes

que um agente capaz de executar. Em particular, baixo nvel de energia deve aumentar a

24

possibilidade de morte e alto nvel de energia deve aumentar possibilidade de reproduo.

(KISIEL-DOROHINICKI, 2002)

Os agentes devem mudar sua energia com base em algum tipo de algoritmo local, que pode

consistir na avaliao da sua aptido e troca de certas pores da sua energia durante os

encontros com seus vizinhos.

2.3.1 MODELAGEM DOS PROCESSOS EVOLUTIVOS NOS SMAE

A seleo em SMAE baseada em mecanismos especficos, que so na sua maioria dirigidos

por um perfil energtico () que consiste em (KISIEL-DOROHINICKI, 2002):

Recurso eng a energia vital;

Objetivo de manter o nvel de energia acima do valor mnimo ;

Estratgias descrevendo as aes do agente em termos de ganho e perda de energia.

Assumindo como um exemplo de estratgia (ao de morte), um perfil energtico pode

ser descrito como:

= , = { , }, = { > } (4)

Sendo as estratgias e o o objetivo desse perfil energtico.

O esforo do agente para a reproduo modelado por um perfil reprodutivo (), que

consiste em:

Recurso hr, que determina a capacidade do agente se reproduzir;

Estratgias descrevendo as aes de reproduo, como, dentre outras possveis, a

reduo do nvel de hr para o seu valor mnimo ():

(5)

Objetivo de manter o nvel de hr abaixo do valor mximo > .

Sendo assim, um perfil reprodutivo pode ser descrito por:

25

= , = { , }, = { < } (6)

Sendo as estratgias, o um exemplo dessas estratgias e o o objetivo desse perfil

reprodutivo.

A quantidade de recurso hr pode aumentar (ou diminuir), dependendo da situao do agente,

ou seja, a sua idade, as interaes com o meio ambiente e outros agentes, etc. Quando se atinge

o nvel de o agente tenta se reproduzir, esperando que consiga abaixar o nvel de hr. A

reproduo ser bem sucedida, se o estado do agente (por exemplo, quantidade de energia vital)

e a sua vizinhana permitem a gerao de um novo agente. (KISIEL-DOROHINICKI, 2002)

Com base nas informaes prestadas at aqui, podemos modelar a evoluo de um agente por

intermdio da seguinte equao:

= = {, , }, = {, , } (7)

Sendo as aes dos agentes e os perfis para cada uma dessas aes.

26

3 MODELAGEM E DESENVOLVIMENTO

Este captulo apresentar a modelagem e o desenvolvimento do Sistema Multiagente Evolutivo

proposto, bem como dos algoritmos utilizados em suas ilhas, Algoritmo Gentico e Evoluo

Diferencial.

A ferramenta utilizada na construo dos algoritmos foi o MATLAB R2010b. Trata-se de um

ambiente de desenvolvimento que integra anlise numrica, clculo com matrizes,

processamento de sinais e criao de grficos. Os comandos do MATLAB so muito

semelhantes forma como se escrevem expresses algbricas, tornando mais simples e direto

seu uso.

3.1 ALGORITMO GENTICO

Como visto anteriormente, os AG so algoritmos baseados na gentica e na seleo natural, e

utilizam os princpios fundamentais destas duas reas para definir seus parmetros e mtodos.

O cromossomo do AG implementado nesse trabalho a representao real de uma soluo para

a funo de benchmark descrita pela Equao 11. Cada gene desse cromossomo representa um

ponto no espao de solues da funo.

O fitness de cada cromossomo calculado por intermdio da funo de avaliao representada

matematicamente pela Equao (11).

O algoritmo utiliza uma populao de n indivduos, ou seja, a cada gerao so institudos n

novos cromossomos e estes so ento submetidos aos operadores genticos. A populao

inicial definida de forma aleatria. O AG desenvolvido neste trabalho utiliza o nmero de

geraes como critrio de parada, sendo a quantidade definida nos testes que foram realizados

e esto descritos na prxima seo. Assim sendo ao final das iteraes o algoritmo cessa sua

execuo e retorna a melhor soluo encontrada at o momento.

O algoritmo implementa o elitismo, que como descrito neste trabalho, consiste em selecionar

uma quantidade de cromossomos com o menor custo e preserv-los para a gerao seguinte.

Assim garante-se que, caso no seja criado um indivduo mais apto na gerao seguinte, a

27

melhor soluo ser igual da gerao atual. Usando este mecanismo estamos influenciando a

intensificao do algoritmo na zona do espao de busca prximo s melhores solues de cada

gerao. Uma constante controla a quantidade de cromossomos que sero mantidos pelo

elitismo, que neste trabalho foi fixado em 0,1 (10% da quantidade total de cromossomos). Deve-

se atentar para o valor dessa constante, que deve possuir um valor entre 0 e 1, pois um valor

muito alto pode levar o algoritmo para uma convergncia prematura.

O operador de seleo utilizado o mtodo do torneio, onde pares de indivduos so

selecionados, dentre os possveis, de forma aleatria e disputam entre si levando-se em

considerao o custo de cada cromossomo. Esse operador seleciona de forma probabilstica os

indivduos com maior aptido para participar dos demais operadores.

No operador de cruzamento so escolhidos dois cromossomos que sero chamados de

cromossomos pais, sendo o primeiro escolhido de forma sequencial, garantindo que todos os

cromossomos participem da reproduo, e o segundo escolhido de forma aleatria devendo ser

diferente do primeiro. O operador de cruzamento escolhido para o desenvolvimento do AG

nesse trabalho baseado no crossover aritmtico descrito por LINDEN (2006), onde define-se

aleatoriamente um parmetro (fator de cruzamento) [0,1], e a posio do filho calculada

por intermdio da seguinte equao :

= 1 + (2 0.5) (2 1) (8)

Aps os cruzamentos, os cromossomos resultantes, denominados de cromossomos filhos, so

encaminhados para a prxima etapa do AG.

Com o intuito de evitar a perda prematura da diversidade da populao, foi incrementada uma

nova etapa que consiste na realizao de uma mutao controlada no cromossomo resultante

do cruzamento. Essa mutao s ser realizada caso a distncia euclidiana entre o par de

cromossomos pais seja inferior 10% do tamanho de uma das dimenses do espao de busca.

Esse operador permite que o novo cromossomo mude sua posio numa subrea dentro do

espao de busca. Essa subrea corresponde a 10% da rea total do espao de busca e tem como

ponto central o cromossomo que sofrer a mutao. A Equao (9) representa esse operador de

mutao.

28

= + ( 0.5) 0,1 ( ) (9)

A prxima etapa do algoritmo consiste em submeter os cromossomos a outro operador de

mutao, esse controlado de forma probabilstica. No presente trabalho a constante que controla

o ndice de mutao foi inicializada em 0,2. Assim sendo, gerado um nmero aleatrio entre

0 e 1 para cada gene (bit a bit) de todos os cromossomos, caso este nmero seja inferior

constante, o gene em questo alterado para outro valor de acordo com a Equao (10),

permitindo que tal gene movimente-se em uma subrea corresponde a 20% da rea total do

espao de busca tendo como ponto central o cromossomo que est sofrendo a mutao. O

operador de mutao contribui para a diversificao dos indivduos, evitando assim uma

convergncia prematura e garantindo a possibilidade de grande parte do espao de busca ser

representado.

= + ( 0.5) 0,2 ( ) (10)

Aps a operao de mutao, os cromossomos escolhidos no elitismo so reinseridos na

populao e assim conclumos toda uma gerao do AG. Os cromossomos resultantes

consistem numa nova gerao de indivduos. Estes mesmos procedimentos se repetem at que

o critrio de parada seja satisfeito, e aps o trmino de todas as geraes, a melhor soluo

encontrada tida como resultado do algoritmo.

3.2 ALGORITMO DE EVOLUO DIFERENCIAL

Este algoritmo tambm inspirado nos processos evolutivos, e assim como os AG, implementa

os operadores genticos de seleo, cruzamento e mutao.

Os parmetros iniciais do ED sero os mais prximos possveis dos do AG, para que o

desempenho dos dois possa ser comparado mais facilmente e com maior propriedade. Assim

sendo a populao inicial (aqui chamados de vetores) e a quantidade de geraes que ser

utilizada como critrio de parada sero os mesmos do AG.

A representao dos vetores no ED a mesma utilizada nos cromossomos do AG: usa-se a

representao de nmeros reais, onde cada elemento do vetor representa a posio em uma

dimenso de um ponto no espao de busca.

29

Semelhante ao que acontece nos AG a primeira ao do ED clculo do custo dos vetores da

populao inicial, com base na Equao (11).

Como dito anteriormente, o primeiro operador utilizado no ED a mutao, onde 3 vetores

distintos, escolhidos aleatoriamente, so usados para gerar o vetor doador conforme Equao

(1), tendo sido o Fm inicializado em 0,1.

O cruzamento realizado entre vetor alvo e o vetor doador de acordo com a Equao (2). A

constante Pc, que controla a probabilidade de cruzamento, foi definido igual a 0,9. O vetor

gerado a partir do cruzamento o vetor candidato.

O prximo operador a seleo, onde o vetor alvo ser comparado com o vetor candidato.

Aquele que apresentar menor custo, de acordo com a Equao (11), ser mantido para a prxima

gerao.

Todo esse processo repetido at que o critrio de parada seja satisfeito, e, nesse momento, o

vetor com o menor custo corresponde melhor soluo encontrada pelo algoritmo.

3.3 SISTEMA MULTIAGENTE EVOLUTIVO

O SMAE proposto por este trabalho contar com subpopulaes dividas em ilhas, e em cada

uma dessas ilhas ser realizado um processo de otimizao local com base nos algoritmos AG

e ED descritos anteriormente.

O sistema dividido em pocas que sero executadas de maneira subsequente, sendo que cada

uma delas corresponde uma gerao dos algoritmos de otimizao das ilhas. Entre essas

pocas ocorrero as comunicaes entre as ilhas. Para realizao dos testes desse trabalho

definimos o nmero de ilhas igual a 4. Portanto teremos 2 ilhas executando o AG e outras duas

com o ED.

As descries dos algoritmos contidas nas sees anteriores so para um processamento

isolado, sendo necessrios pequenos ajustes para inseri-los e adapt-los ao SMAE.

30

A primeira adaptao diz respeito a quantidade de indivduos da populao e a quantidade de

geraes usadas como critrio de parada dos algoritmos, com o intuito de tentar aproximar as

condies do SMAE a dos algoritmos individuais, para posteriores comparaes. Como

definiu-se que o SMAE contar com 4 ilhas, dividiu-se a populao e a quantidade total de

geraes cada uma por 2 e assim tm-se todos os algoritmos realizando, aproximadamente, a

mesma quantidade de clculos da funo objetivo.

A segunda e mais importante das adaptaes foi a criao de uma estrutura para o controle da

energia vital de cada um dos agentes. Agora, alm da aptido calculada pelo custo da funo de

benchmark, cada agente possui uma segunda medida de aptido, a energia vital, que ser usada

tanto internamente nos algoritmos de otimizao locais, como tambm para controle dos

processos evolutivos e de comunicao do SMAE.

Para utilizao dessa energia vital foram criadas algumas constantes, a saber:

Energia inicial = 5, a quantidade de energia que cada um dos agentes recebe quando

criado;

Energia de competio = 2, a quantidade de energia transferida do perdedor para o

vencedor em cada competio;

Limiar de morte = 0, a quantidade mnima de energia que um agente necessita para

no ser declarada a sua morte;

Limiar de reproduo = 7, a quantidade mnima de energia que um agente necessita

para poder participar do(s) operador(es) de reproduo;

Limiar de migrao = 10, a quantidade mnima de energia que um agente necessita

para poder migrar para outra ilha.

Em ambos os algoritmos de otimizao foram implementados procedimentos para lidar com a

energia vital e suas constantes.

Foi adotado que a energia total do sistema deve se manter fixa para facilitar o uso das

constantes. Como existem procedimentos que podem alterar o total da energia do sistema, aps

a execuo desses feita uma normalizao das energias de cada um dos agentes para que a

energia total retorne ao valor inicial.

31

Nos momentos de competio entre agentes ocorre apenas a transferncia de energia do

perdedor para o ganhador. J nos momentos de reproduo, a energia do agente filho que

gerado calculada com base nas energias dos agentes pais submetidas mesma funo utilizada

no processo de cruzamento.

Aps a execuo de cada uma das pocas do SMAE so verificados quais agentes podem migrar

para outra ilha por terem extrapolado o valor da constante que controla esse limiar. A nova ilha

para cada um desses agentes escolhida de forma aleatria. A poltica de migrao adotada

de sempre manter as subpopulaes em igual nmero, sendo que o agente migrante substitui o

pior agente da ilha de destino, usando como critrio as suas energias vitais. O agente migrante

tem sua energia reinicializada aps ser inserido na nova ilha, ou seja, ele volta a possuir o valor

da energia inicial.

Ainda no intervalo entre pocas, e aps as possveis migraes, verificado se existem agentes

com energia abaixo do limiar de morte. Em caso afirmativo, esses agentes so descartados e

novos agentes, criados de forma aleatria, os substituem.

Ao final de todas as iteraes o melhor agente dentre os resultados das ilhas tido como o

resultado do SMAE.

Apesar da possibilidade de aproveitamento do paralelismo ser destacado como uma das

vantagens de um SMA, e consequentemente de um SMAE, a implementao feita para esse

trabalho foi de forma sequencial por meio de iteraes sobre as ilhas. O intuito dessa escolha

foi simplificar o desenvolvimento e os testes que foram realizados, j que no interferiria no

principal indicador usado para avaliar e comparar os algoritmos que o valor da funo objetivo

alcanado pelos mesmo.

32

4 EXPERIMENTOS E RESULTADOS OBTIDOS

Neste captulo sero descritos como os experimentos foram realizados, a funo de benchmark

que foi utilizada, bem como sero apresentados os resultados desses testes obtidos pelos 3

algoritmos implementados neste trabalho.

4.1 FUNO RASTRIGIN

A funo Rastrigin proposta inicialmente por RASTRIGIN (1974), trata-se de uma funo no-

linear multimodal. Possui 10n (sendo n o nmero de dimenses da funo) mnimos locais, o

que aumenta a complexidade do processo de otimizao, distribudos regularmente. A funo

de Rastrigin dada pela Equao 11 e tem seu mnimo global em = 0 onde () = 0.

(1, , ) = 10 + [2 10 cos(2)]

=1 , [5.12, 5.12] (11)

Essa funo amplamente estudada e comumente usada como problema teste (funo de

benchmark) de otimizao no linear (MICHALEWICZ, 1996). A Figura 8 apresenta uma

representao grfica da funo de Rastrigin considerando n=2 (bidimensional).

Figura 8: Representao grfica da funo de Rastrigin bidimensional.

4.2 EXPERIMENTOS REALIZADOS

Inicialmente foram realizados testes individuais nos algoritmos AG e ED descritos neste

trabalho. Esses testes foram realizados utilizando a funo de Rastrigin com 2 dimenses, j

que as principais finalidades eram: conseguir visualizar graficamente, no espao de variveis,

33

a distribuio dos indivduos da populao no espao de busca para verificar se, por exemplo,

estava ocorrendo perda da diversidade da populao; e visualizar a convergncia dos algoritmos

ao longo das geraes.

Pode-se observar os grficos de 2 desses testes realizados nas figuras 9 e 10. A Figura 9 mostra

os resultados de um teste do AG enquanto a Figura 10 os resultados de um teste do ED, isso ao

longo de 40 geraes e considerando uma populao de 200 indivduos.

Figura 9: Resultados de um teste do AG.

Figura 10: Resultados de um teste do ED.

34

De semelhana entre os dois algoritmos observa-se a convergncia dos melhores fitness. No

entanto, h grandes diferenas entre a distribuio dos indivduos no espao de solues e na

curva da mdia dos fitness encontrados. O AG apresenta os indivduos mais uniformemente

distribudos nas regies prximas a soluo tima e a curva da mdia dos fitness da populao

bastante irregular, apresentando um declnio acentuado nas primeiras geraes e altos e baixos

ao longo das demais geraes. Isso porque o AG no impede que 2 pais deem origem a um filho

com custo maior para a gerao seguinte, j que a seleo (competio) ocorre antes do

cruzamento e um mesmo indivduo pode ser selecionado mais de uma vez. No caso da ED, ao

final da execuo, os indivduos ficam agrupados em vrias regies de mnimos locais e na

regio do mnimo global, ocasionando uma perda maior da diversidade dessa populao, e a

curva da mdia dos fitness apresenta um declnio contnuo. Diferentemente do AG, no ED a

competio ocorre entre um indivduo da populao atual e um novo indivduo gerado dos

operadores de mutao e cruzamento, garantindo assim que, no pior dos casos, os fitness da

nova populao sejam iguais aos da gerao anterior.

Posteriormente, foram realizados testes semelhantes com o SMAE utilizando parmetros

escolhidos de forma aleatria para observar o comportamento do mesmo.

As observaes dos testes iniciais serviram para incentivar mudanas que foram realizadas

nesses algoritmos com o intuito de melhorar seus desempenhos e posteriormente para auxiliar

no dimensionamento das quantidades da populao e das geraes que foram utilizadas no teste

subsequente.

Aps os testes iniciais, o prximo e principal experimento constituiu na execuo de cada um

dos algoritmos para vrias dimenses da funo de Rastrigin e, em cada uma delas, executado

vrias vezes consecutivas. Para conseguir uma quantidade razovel de resultados, definiu-se

que cada um dos algoritmos deveria ser executado por 30 vezes consecutivas e as dimenses

escolhidas para os testes foram: 2, 5, 10, 15 e 20.

O tamanho das populaes dos algoritmos mantiveram-se fixas ao longo de todas as execues,

200 indivduos para os AG e ED, e de 100 indivduos para o SMAE j que, como foi dito

anteriormente, a populao desse algoritmo deve ser a metade dos demais para aproximar a

35

quantidade de clculos da funo objetivo e possibilitar uma justa comparao entre todos os

algoritmos.

A quantidade de geraes que foram utilizadas nesse teste variava de acordo com a dimenso

utilizada na funo objetivo. Considerando d como a dimenso utilizada nessa funo, definiu-

se que a quantidade de geraes dos algoritmos seria dada por = 2 10. Lembrando que no

caso do SMAE a quantidade de geraes obtida pela equao anterior ainda deveria ser dividida

pela metade, pelo mesmo motivo apresentado no pargrafo antecedente, que trata do caso da

quantidade da populao. A Tabela 1 apresenta alguns dos resultados obtidos com a realizao

desse experimento.

Tabela 1: Resultados do experimento principal.

Dimenses Resultados Algoritmo

AG ED SMAE

2

Mnimo 0,0001 0,0000 0,0000

Mdio 0,0112 0,0000 0,0000

Mximo 0,0510 0,0000 0,0005

Tempo Mdio (seg.) 0,17 0,19 0,39

5

Mnimo 0,0027 0,0000 0,0000

Mdio 0,0322 0,0332 0,0000

Mximo 0,0846 0,9950 0,0000

Tempo Mdio (seg.) 1,21 1,28 3,09

10

Mnimo 0,0336 0,0000 0,0000

Mdio 0,1482 0,4662 0,0000

Mximo 0,3627 3,9886 0,0000

Tempo Mdio (seg.) 4,48 5,08 11,39

15

Mnimo 0,2424 0,0000 0,0000

Mdio 0,6489 1,4320 0,0000

Mximo 1,1800 3,9862 0,0000

Tempo Mdio (seg.) 10,21 11,65 25,30

20

Mnimo 2,3310 1,9912 0,0000

Mdio 4,6039 4,4535 0,0000

Mximo 7,1397 8,0742 0,0000

Tempo Mdio (seg.) 19,62 22,07 50,89

Baseado nas informaes contidas na Tabela 1 percebe-se que o SMAE alcanou bons

resultados em relao aos demais mtodos abordados, com resultados prximos ao timo

global.

36

Uma possvel explicao para os resultados significativos alcanados pelo SMAE a troca de

informaes relevantes que o ocorre no momento da migrao de agentes entre as ilhas, j que

os indivduos aptos a realizarem migrao tendem a estar entre os melhores indivduos at o

momento em suas ilhas.

Em muitos casos do experimento o AG e o ED alcanaram resultados prximos aos do SMAE,

ainda assim ficando aqum desse ltimo. A vantagem desses mtodos consiste em apresentar

bons resultados se considerarmos como parmetro o tempo mdio de execuo dos algoritmos.

Tanto o AG como o ED apresentaram uma tendncia de piora com o aumento da complexidade

do problema. Cabe avaliar a influncia dos parmetros utilizados por esses mtodos na obteno

desses resultados.

J no SMAE praticamente no h alteraes nos resultados obtidos com o aumento da

complexidade do problema. A mdia dos resultados do SMAE mantem-se praticamente

inalterada independentemente da dimenso utilizada pela funo de avaliao.

37

5 CONCLUSES

O presente trabalho props a implementao de um SMAE empregando o modelo de ilhas, em

que cada uma dessas ilhas possui uma subpopulao submetida a um algoritmo de otimizao

evolutivo. Os mtodos evolutivos utilizados nas ilhas foram o AG e o ED.

O SMAE foi desenvolvido com o intuito de resolver um problema de otimizao no linear.

Para avaliar o algoritmo proposto, o mesmo foi aplicado a uma conhecida funo de benchmark

utilizada para esse tipo de problema, a funo de Rastrigin.

Por disponibilizar uma quantidade de resultados que possibilita uma anlise estatstica, o

principal experimento utilizado para avaliao foi a execuo por diversas vezes consecutivas,

tanto do SMAE como dos AG e ED individualmente, sobre a funo de Rastrigin para vrias

dimenses. O indicador capital de desempenho dos algoritmos foi o custo da soluo

encontrada.

Tomando como base os resultados experimentais dos 3 algoritmos utilizados nos testes,

conclui-se que a abordagem proposta do SMAE mostrou-se a mais eficaz j que apresentou

melhores resultados em relao aos demais mtodos avaliados. O SMAE conseguiu melhorar

o desempenho dos mtodos convencionais de otimizao no linear usados nesse trabalho,

utilizando o mesmo nmero de clculos da funo objetivo, evidenciando assim o sucesso da

implementao do algoritmo proposto.

Apesar deste no ser o indicador de maior relevncia utilizado nesse trabalho para as avaliaes

e comparaes feitas, o tempo de execuo dos algoritmos, presentes na Tabela 1, pde ajudar

em algumas constataes.

O fato do SMAE possuir um tempo de execuo acima dos demais nos permite fazer as

seguintes constataes: (i) a percepo do efeito causado pela escolha de no aproveitar a

possibilidade de execuo em paralelo; e (ii) a concluso de que os procedimentos adicionais

presentes no SMAE para controle dos agentes e das suas energias vitais colaboraram para a

elevao do custo computacional desse algoritmo em relao aos demais aqui apresentados.

38

Conclui-se tambm que o SMAE tende a se tornar mais benfico medida que a complexidade

do problema aumenta pois a diferena de desempenho deste em relao aos demais algoritmos

fica em evidncia com o aumento das dimenses do problema.

Esse trabalho apresentou resultados satisfatrios levando em considerao o que foi proposto.

Ainda assim propostas de melhorias, novos experimentos e novos critrios de avalio podem

ser pensados para futuras implementaes buscando melhorar o desempenho dos algoritmos e

solidificar uma concluso a respeito dos mesmos. Pensando nisso pode-se propor os seguintes

trabalhos futuros:

Alterao dos parmetros inicias dos algoritmos, buscando um equilbrio entre a

convergncia e os resultados finais encontrados;

Implementao de outros mtodos de otimizao para serem utilizados nas ilhas do

SMAE;

Adaptao do sistema proposto para utilizao do mesmo de forma paralela;

Adaptao do sistema proposto para resoluo de problemas discretos;

Analisar o comportamento dos sistemas propostos em outros problemas (funes).

39

REFERNCIAS BIBLIOGRFICAS

ALMASI, G. S., GOTTLIEB, A. Highly Parallel Computing. Benjamin-Cummings, Redwood

City, CA. 1989

VILA, S. L. et al. Otimizao Conceitos Bsicos, Ferramentas e Aplicaes. Revista de

Automao e Tecnologia da Informao, Florianpolis, v.2, n.1, 2003.

BEZ, E. D. Procedimento de Representao de Solues em Otimizao Global: Aplicao em

Modelos de Interao Espacial. Tese (Doutorado em Engenharia de Produo), Universidade

Federal de Santa Catarina, Florianpolis, 2005.

BLUM, C., ROLI, A. Metaheuristics in combinatorial optimization: Overview and conceptual

comparison. 35 (3). ACM Computing Surveys. pp. 268308. 2003.

BRAGA, A. P.; LUDENIR, T. B.; CARVALHO, A. C. P. L. F. Redes Neurais Artificiais

Teoria e aplicaes. LTC, 2000.

BYRSKI, A., DREZEWSKI, R., KISIEL-DOROHINICKI, M., SIWIK, L. Evolutionary multi-

agent systems. Disponvel em: . Acesso em:

Dezembro de 2014.

GOLDBERG, D. E. Genetic Algorithms in Search, Optimization and Machine Learning.

Addison Wesley, 1989.

GOLDBERG, D. E.; HOLLAND, J. H. Genetic algorithms and machine learning: Introduction

to the special issue on genetic algorithms. Machine Learning, 1988.

HEITKOETTER, J., BEASLEY, D. The hitch-hiker's guide to evolutionary computation: a list

of frequently asked questions (FAQ). 1994. Disponvel em:

. Acesso em: Outubro de 2009.

HO, Y. C.; PEYNE, D. L. Simple Explanation of the No Free Lunch Theorem of Optimization.

Proceedings of the 40th IEEE Conference on Decision and Control, volume 5, 2001.

40

HOLLAND, J. H. Adaptation in Natural and Artificial Systems. The University of Michigan

Press, 1975.

JENNINGS, N. R. Coordination techniques for distributed artificial intelligence. In: OHARE,

G.M.P.; JENNINGS, N.R. (Eds.). Foundations of distributed artificial intelligence. New York:

John Wiley & Sons. pp.187-210. 1996.

KISIEL-DOROHINICKI, M. Agent-Oriented Model of Simulated Evolution. SOFSEM 2002:

Theory and Practice of Informatics. Springer-Verlag. pp. 253-261. 2002

KISIEL-DOROHINICKI, M., DOBROWOLSKI, G., NAWARECKI, E. Agent Populations as

Computational Intelligence. Neural Networks and Soft Computing. Springer-Verlag. pp 608-

613. 2003.

LINDEN, R. Algoritmos Genticos: Uma importante ferramenta da Inteligncia

Computacional. Rio de Janeiro: Brassport, 2006.

MICHALEWICZ, Z. Genetic Algorithms + Data Structures = Evolution Programs. 3rd revised

and extended. Berlim, Springer-Verlag, 1996.

MICHALEWICZ, Z., SCHOENAUER, M. Evolutionary Algorithms for Constrained

Parameter Optimization Problems. Evolutionary Computation, vol. 4, no. 1, 1996.

OLIVEIRA, G. T. S. Estudo e aplicaes da Evoluo Diferencial. Dissertao (Mestrado em

Engenharia Mecnica). Universidade Federal de Uberlndia. Uberlndia, 2006.

POOLE, D., MACKWORTH, A. Artificial Intelligence: Foundations of Computational Agents.

Cambridge University Press, 2010.

RASTRIGIN, L. A. Systems of Extremal Control, Nauka, Moscow, 1974.

STORN, R.; PRICE, K., Differential Evolution: a simple and efficient adaptive scheme for

global optimization over continuous spaces, Technical Report TR-95-012, International

Computer Science Institute, Berkeley, 1995.

41

STORN R.; PRICE K. Differential evolution - A Simple and Efficient Heuristic for Global

Optimization Over Continuous Spaces. Journal of Global Optimization, v. 11, p. 341-359, 1997.

STORN, R.; PRICE, K. Home Page of Differential Evolution (DE) for Continuous Function

Optimization. Disponvel em: . Acesso em:

Setembro de 2013.

WOLPERT, D. H.; MACREADY, W. G. No Free Lunch Theorems for Optimization. IEEE

Transactions on Evolutionary Computation, 1(1):67-82, 1997.

WOOLDRIDGE, M; JENNINGS, N. R. Intelligent Agents: Theory and Practice. The

Knowledge Engineering Review. Cambridge University Press. Volume 10, p 115-152, nmero

2, 1995.

WOOLDRIDGE, M. Intelligent agents. In: WEISS, G. (Ed.) Multiagent Systems - A Modern

Approach to Distributed Artificial Intelligence, MIT Press, 1999.

ZAMBONELLI, F., JENNINGS, N. R., WOOLDRIDGE, M. Organizational abstractions for

the analysis and design of multi-agent systems. In: Proceedings of the 1st International

Workshop on Agent-Oriented Software Engineering, 2000, Limerick, Ireland, pp.127141,

2000.