ads:
Eduardo Sacogne Fraccaroli
Análise de Desempenho de Algoritmos
Evolutivos no Domínio do Futebol de Robôs
Dissertação apresentada à Escola de Engenharia de
São Carlos da Universidade de São Paulo, como parte
dos requisitos para obtenção do título de Mestre em
Ciências, Programa de Pós-graduação em Engenha-
ria Elétrica (Área de Concentração em Sistemas Di-
nâmicos)
Orientador: Prof. Dr. Ivan Nunes da Silva
São Carlos
2010
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
ads:
ii
Dedicatória
À Deus, meus pais, meus irmãos e a todos aqueles que acreditaram em mim.
iv
Agradecimentos
À Deus, po r conceder for ça, criatividade, coragem e por cada momento vivido durante
a realização deste trabalho.
À minha Família, Brasil, Marisa, Catia e Rafael, por todo apoio oferecido e paciência
durante a realização deste trabalho, em especial meu pai, pelo incentivo e pelas correções
deste texto.
À Selene, pela paciência, dedicação, coragem, carinho e pela ajuda na realização deste
trabalho.
Ao Prof. Dr. Ivan Nunes da Silva, por toda orientação, motivação, apoio , paciência,
dedicação, por acreditar e investir no trabalho de seus alunos.
Aos meus amigos do LAIPS: Ricardo, Suetake, Rodrigo, Daniela, Luciano, Spatti,
Fernanda e Renato.
Aos meus amigos do GEAR: Ivan, Lang, Lucas, Patrícia, Gustavo, Marcelo, Jonas e
Gabriel.
Ao meu amigo do USPDroids Marcelo, pelo tempo concedido às divagações.
Aos diversos professores e funcionários da EESC/SEL pelos serviços prestados.
Às funcionárias da secretaria de pós-graduação do SEL, em especial às secretárias
Marisa e Jussara, por estarem sempre dispostas a nos dar atenção.
E, por fim, à CAPES pelo apoio financeiro concedido.
vi
vii
Resumo
Fraccaroli, E. S. Análise de Desempenho de Algoritmos Evolutivos no Domínio do Fu-
tebol de Robôs. 2010. Dissertação (Mestrado) - Escola de Engenharia de São Carlos,
Departamento de Engenharia Elétrica, Universidade de São Paulo, São Carlos, 2010.
Muitos problemas de otimização em ambientes multiagentes utilizam os algoritmos
evolutivos para encontrar as melhores soluções. Uma das abordagens mais utilizadas con-
siste na aplicação de um algor itmo genético, como alternativa aos métodos tradicionais,
para definir as ações dos joga do r es em um time de futebol de robôs. Entretanto, conforme
relatado na literatura, há inúmeras possibilidades e formas de se aplicar um algor itmo ge-
nético no domínio do futebol de robôs. Assim sendo, neste trabalho buscou-se realizar
uma análise comparativa dos alg oritmos genéticos mono-objetivo e multi-objetivo apli-
cados no domínio do futebol de robô s. O problema padrão escolhido para realizar essa
análise foi de desenvolver uma estratégia de controle autônomo, a fim de capacitar que os
robôs tomem decisões sem interferência externa, pois, além de sua solução se encontrar
ainda em aberto, o mesmo é também de suma relevância para a área de robótica.
Palavras–Chave: Algoritmos Genéticos, Sistemas Multiagentes, RoboCup Soccer Simu-
lation 2D.
viii
ix
Abstract
Fraccaroli, E. S. Performance Analysis of Evolutionary Algorithms in the Robot Soccer
Domain. 201 0. Dissertação (Mestrado) - Escola de Engenharia de São Carlos, Departa-
mento de Engenharia Elétrica, Universidade de São Paulo, São Carlos, 2010.
Many optimization problems in multiagent environments adapt evolutionary algo-
rithms to find the best solutions. A widely used approach consists of applying a genetic
algorithm as an alternative to traditional methods, in order to define the actions of the
players on a soccer team of simulated robots. However, as reported in the literature,
there are many possibilities and ways to apply a genetic algorithm in the field of robot
soccer. Therefore, this work attempts to make a comparative analysis of mono-objective
and multi-objective genetic a lgorithms applied to control a robot soccer. The standard
problem chosen for this analysis was to develop a strategy for autonomous control, in
order to enable the robo ts to make decisions without external interference, because in
addition to its solution is still open, it is also of utmost relevance to the area rob otics.
Keywords: Genetic Algorithm, Multiagent System, RoboCup Soccer Simulation 2D.
x
xi
Lista de Figuras
1.1 Sequência de bits utilizados como estratégia do time (Nakashima et al., 2004). . . . . . 3
1.2 Área utilizada para o exercício de treinamento dos jogadores (Jeong e Lee, 1997). . . . 6
2.1 Robôs da categ oria Humanoid da RoboCup (RoboC up, 2009). . . . . . . . . . . . . 10
2.2 Robôs da categ oria Middle Size da RoboCup (RoboCup, 2009). . . . . . . . . . . . . 11
2.3 Robôs da categ oria Small Size da RoboCup (RoboCup, 2 009). . . . . . . . . . . . . 11
2.4 Robôs NAO da categor ia Standard Platform da RoboCup (Rob oCup, 2009). . . . . . . 12
2.5 Robôs AIBO da categoria Standard Platform da RoboCup (RoboCup, 2009). . . . . . 12
2.6 Categoria Simulation 2D da RoboCup (RoboCup, 2009). . . . . . . . . . . . . . . . 13
2.7 Ilustração do monitor. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.8 Arquitetura do simulador 2D (Reis, 2003). . . . . . . . . . . . . . . . . . . . . . . 15
2.9 Arquitetura do time UvA Trilearn (Boer e Kok, 2002). . . . . . . . . . . . . . . . . 16
2.10 Principais componentes da arquitetura do time UvA Trilearn (Boer e Kok, 2002). . . . 17
2.11 Modos de ações presentes no código fonte do time UvA Trilearn (Boer e Kok, 2002). . . 1 9
3.1 Exemplo de um cruzamento entre dois cromossomos (Plant e Schaefer, 2008). . . . . . 27
3.2 Pareto ótimo no espaço de objetivo e a possível relação e ntre as soluções (Zitzler, 1999). 32
3.3 Modelo esquemático do algoritmo NSGA-II (Deb, 2001). . . . . . . . . . . . . . . . 36
4.1 Representação do campo virtual, dos jogadores e da bola. . . . . . . . . . . . . . . 42
xii
4.2 Representação dos jogadores. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.3 Fluxo de dados dentro do sistema desenvolvido. . . . . . . . . . . . . . . . . . . . 46
4.4 Fluxograma do a lgoritmo genético mono-objetivo. . . . . . . . . . . . . . . . . . . 48
4.5 Fluxograma do a lgoritmo genético multi-objetivo. . . . . . . . . . . . . . . . . . . 50
4.6 Resultado de duas mil gerações, AG Mono-Objetivo contr a BRA INSTORMERS. . . . 54
4.7 Resultado de duas mil gerações, AG Mono-Objetivo contr a WRIGHTEAGLE. . . . . . 54
4.8 Resultado de duas mil gerações, AG Mono-Objetivo contr a H ELIOS. . . . . . . . . . 55
4.9 Resultado de cem gerações, AG Multi-Objetivo contra BRAINSTORMERS. . . . . . . 5 6
4.10 Resultado de cem gerações, AG Multi-Objetivo contra WRIGHTEAGLE. . . . . . . . 57
4.11 Resultado de cem gerações, AG Multi-Objetivo contra HELIOS. . . . . . . . . . . . 57
xiii
Lista de Tabelas
3.1 Diferentes modelos de AEMOs. . . . . . . . . . . . . . . . . . . . . . . . . 34
4.1 Tempo total da simulação, sem configurar o servidor. . . . . . . . . . . . . 53
4.2 Tempo total da simulação, com o servidor configurado. . . . . . . . . . . . 53
4.3 Média dos resultados obtidos da abordagem genética mono-objetivo. . . . . 55
4.4 Média dos resultados obtidos da abordagem genética multi-objetivo. . . . . 58
xiv
xvi
xvii
Lista de Abre viaturas e Siglas
AE Algoritmo Evolutivo
AEMO Algoritmos Evolutivo Multi-obj etivo
AG Algoritmo Genético
AGMO Algoritmo Genético Multi-Objetivo
NSGA-II Elitist Non-Dominated Sorting Genetic Algorithm
PG Programação Genética
POMO Problemas de Otimização Multi-Objetivo
xviii
xix
Sumário
Dedicatória iii
Agradecimentos v
Resumo vii
Abstract ix
Lista de Figuras xi
Lista de Tabelas xiii
Lista de Quadros xv
Lista de Abreviaturas e Siglas xvii
1 Introdução 1
1.1 Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Revisão Bibliográfica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Organização da Dissertação . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Trabalhos Publicados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Futebol de Rob ôs 9
2.1 Asp ectos da Ro boCup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Categoria de Simulação 2D . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 UvA Trilearn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4 Considerações Parciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3 Abordagem Evolutiva Mono-Objetivo e Multi-Objetivo 21
3.1 Teoria da Evolução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
xx
3.2 Algoritmos Genéticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.1 Representação dos Indivíduos . . . . . . . . . . . . . . . . . . . . . 25
3.2.2 Definição da População Inicial . . . . . . . . . . . . . . . . . . . . . 26
3.2.3 Operadores Genéticos . . . . . . . . . . . . . . . . . . . . . . . . . . 2 7
3.2.4 Seleção dos Indivíduos . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3 Otimização Multi-Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.1 Conceito de Dominância e Pareto-Ótimo . . . . . . . . . . . . . . . 31
3.4 Algoritmo Evolutivo Multi-Objetivo . . . . . . . . . . . . . . . . . . . . . . 33
3.4.1 Algoritmo NSGA-II . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.5 Diferenças Fundamentais entre Otimização Mono-Objetivo e Multi-Objetivo 39
3.6 Considerações Parciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4 Metodologia Proposta 41
4.1 Características do Time Desenvo lvido . . . . . . . . . . . . . . . . . . . . . 42
4.2 Codificação dos Indivíduos . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.3 Características do AG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.4 Abordagem Mono-Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.5 Abordagem Multi-Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.6 Resultados Obtidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.6.1 Resultado do Algoritmo Genético Mono- O bjetivo . . . . . . . . . . 53
4.6.2 Resultado do Algoritmo Genético Multi-Objetivo . . . . . . . . . . 55
4.7 Considerações Parciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5 Conclusões Gerais 59
1
Capítulo 1
Introdução
As pesquisas em sistemas multiagent es têm se tornado uma das principais tendências
no domínio da inteligência artificial (Weiss, 1999). O conceito de futebol de robôs foi
introduzido em 1993 por Itsuki Nota (Kitano et al., 1995). A competição de futebol
de robôs tem como pretexto o desenvolvimento de técnicas de inteligência artificial, para
aplicações robóticas, utilizando um problema padrão em que um grande leque de possíveis
tecnologias possam ser examinadas. Algumas técnicas utilizadas no ambiente do futebol
de robôs simulados são as seguintes:
• Algoritmos Genéticos;
• Aprendizado por Reforço;
• Aprendizado por Reforço Acelerado por Heurísticas;
• Sistemas Fuzzy;
• Redes Neurais Artificiais.
De fato, já há muito tempo, um dos objetivos mais perseguidos pelo ser humano
é dotar uma máquina, construída pelo mesmo, com características inteligentes. Desde
então, têm-se observado o surgimento de novos para digmas simbólicos de aprendizagem,
em que muitos deles se tornaram métodos computacionais robustos, como aprendizado
baseado em explicações, sistemas classificadores e sistemas evolutivos (Ross, 2004).
2
Neste trabalho utilizou-se alg oritmos genéticos, o qual é inspirado na teoria da evolução
de Darwin e pode ser considerado como um método que trabalha com buscas para lelas
randômicas direcionadas, em que se utiliza o processo evolutivo para determinar a melhor
solução de um problema. São empregados para resolver problemas complexos, tendo como
vantagem seu paralelismo. O algoritmo genético percorre o espaço das possíveis soluções
usando muito s indivíduos, de modo que são menos suscetíveis de ficarem presos em um
mínimo local (Goldberg, 1989).
1.1 Objetivo
O principal objetivo deste traba lho é analisar a eficiência d os algoritmos genéticos
aplicados no futebol de robôs da categoria Simulação 2D. Para isto, foram estudados e
implementados dois métodos: o primeiro, baseado na aplicação do algoritmo genético
mono-objetivo e, o segundo, consiste na aplicação do alg oritmo genético multi-objetivo
utilizando especificament e o a lgoritmo NSGA-II. Tais implementações visam demonstrar
a diferença obtida na aplicação do s respectivos méto do s no problema padrão do futebol
de robôs simulado.
Outro aspecto deste trabalho que é de suma valia é a inexistência de qualquer tipo
de documentação na literatura reportando tal análise comparativa , sendo portanto um
trabalho inédito no campo de estudo do futebol de robô.
1.2 Revisão Bibliográfica
Os algoritmos genéticos (AG) têm sido utilizados em diversas ocasiões no domínio
da RoboCup
1
. Em Nakashima et al. (2004), um AG foi utilizado para implementar uma
estratégia de um time que poderia derrotar a estratégia de um único time adversário.
Para isso, a área de jogo foi dividida em 48 áreas diferentes. A localização de um jogador
em posse da bola é represent ada como A, sendo uma figura no intervalo de [1;48]. A
1
RoboCup é um projeto internacional co njunto para promover a Inteligência Artificia l (IA), robótica e
campos relacionados. É uma tentativa de promover a IA e p e squisas em robótica inteligente, fornecendo
um problema padrão onde uma vasta gama de tecnologias podem ser integradas e examinadas.
3
distância entre este jog ador a um jogador adversário é apresent ado como B, e dependendo
da distância entre o s jogadores, pode-se considerá-lo como próximo ou não próximo (em
relação a um valor limiar pré-definido). O resultado de A e de B é mostrado como C, que
é a ação escolhida como resposta das possíveis informações. Assim, C pode ser uma das
10 diferentes ações de alto nível, que incluem uma variedade de tipos de passes, drible ou
a opção de chutar. Esse processo é representado pelas regras:
Se Agente é A
i
e Adversário está em B
j
então Ação é C
k
(1.1)
A estratégia do time é a r mazenada como um cromossomo de 960 genes de comprimento
(ver Figura 1.1). Como um jogador pode estar em 48 diferentes posições no campo de
jogo, com um jog ador a ser oposição ou perto ou longe, há então 48 × 2 = 96 regras de
ação diferentes para cada joga do r e, portanto, 960 para todos os 10 jogadores no tota l. O
goleiro não possui um cromossomo, pois apresenta açõ es básicas. Cada gene é um inteiro
no intervalo [1; 10 ], correspo ndente a uma das 10 possíveis ações de alto nível.
Figura 1.1: Sequência de bits utilizados como estr atégia do time (Nakashima e t al., 2004).
Para esta abordagem, foi escolhida população de 1 e a probabilidade de mutação
definida como 1/9 6. A aptidão do cromossomo é calculada no decorrer de uma partida
real. O número de gols marcados pelo time é a principal medida, sendo que se a quantidade
de gols marcados for igual na população, o número de gols sofridos será então levado
em consideração. Para testar o método evolucionário, dois tipos de experimentos foram
4
configurados. O primeiro foi colocado para jogar o cromossomo contra a versão mutante
do cromossomo. O vencedor será selecionado para, em seguida, ser mutado a fim de
assim jogar novamente contr a seu predecessor. O outro experimento foi colocar para
jogar cada cromossomo contra apenas um único time, ou seja, a Uva Trilearn que ganhou
a liga de simulação da RoboCup 2003. Tanto o cromossomo original como o mutante
jogaram com um time pré-determinado, sendo que o mais apto (ou seja, a maior diferença
de pontuação) foi selecionado para a mutação. No primeiro experimento, a cada mil
gerações, o cromossomo f oi medido. Tornou-se claro que, pela geração de seis milésimos,
o desempenho do placar tinha melhorado, passando de uma média de 0, 9 g ols marcados
em 10 jogos na milésima geração, para uma média de 3, 8 gols po r jogo. Da mesma forma,
no segundo experimento, os gols por média de jogos melhoraram ao longo do t empo. Os
experimentos concluíram que, mesmo com uma população mínima, os resultados podem
ser alcançados utilizando técnicas evolutivas.
Um outro caso de empregar os AGs pa ra a aprendizagem de estratégias de um time foi
apresentado em Cheung et al. (2005), onde uma técnica semelhante à de Nakashima et al.
(2004) foi utilizada. Aqui, os cromossomos consistem de quatro genes, os quais represen-
tam um dos quatro jogadores de diferentes tipos (goleiro, zagueiro, meia e atacante).
Cada um tem um conjunto de ações de tamanho 50 regras que abrangem as diferentes
opções que um jogado r pode tomar. No entanto, a seleção dos mais aptos é calculada
utilizando um treinador (treinador off-line). O treinador conecta-se ao servidor de f utebol
de maneira muito parecida com um jogador, mas tem uma visão completa e informaçõ es
sobre o curso do ambiente (Chen et al., 2 002). Em Cheung et al. (2005), é utilizado uma
classe chamada Fitness, que permite ao treinador atribuir pontos para um tipo de j ogador
com base em seu desempenho (por exemplo, um ponto para marcar um gol). Uma média
para cada tipo de j ogador é usada como medida de fitness.
A abordagem evolutiva em Cheung et a l. (2005) é também diferente da abordag em de
Nakashima et al. (2004). A técnica utilizada é Selecionar, Multiplicar e Mutar (SMM).
Cada cromossomo escolhido é multiplicado por 4, dos quais três são mutantes e o original
é mantido. O cromossomo mais apto dos quatro é usado como ponto de partida para
a próxima geração. Dois tipos de experimentos foram realizados com cada cromossomo.
No primeiro, cada cromossomo joga com o mesmo time adversário, sendo que no segundo
5
o time adversário foi trocado. A medida para a experiência foi a diferença de gols. Os
resultados mostraram que contra um time estático, entre a quinquagésima g eração e a
centésima geração, houve melhora de 10 gols. No tou-se também que variando o adversário
não implicou em nenhuma melhora.
Embora o objetivo inicial fosse implementar um verdadeiro AG neste experimento, esta
abordagem foi considerada computacionalmente muito cara e demorada. Port anto, um
método evolutivo alternativo foi utilizado, semelhante à abordagem de Nakashima et al.
(2004), sem a parte do cruzamento no algoritmo.
Em Raadt et al. (2003), investigou-se como a área de atua ção do jogador e parâme-
tros de localização podem ser manipulados usando um AG. Novamente, foi utilizado um
cromossomo para armazenar todas as informações do time. Foi visto como uma vanta-
gem o fato de que todos os membros do time poderiam acessar as informações táticas de
cada joga do r. Por exemplo, se o lateral direito está na posição de zagueiro, será capaz
de lidar com situações relacionadas com o meio de campo. Portanto, foi desenvolvida a
classe Evolver para ser amplamente utilizada. Primeiro, ela é responsável por determinar
a aptidão de cada cromossomo do time. Usando essa informação, a classe Evolver pode
selecionar os cromossomos mais aptos do time a serem utilizados na próxima geração, ou
remover versões inferiores. Para cada geração foram utilizados seis times com cromos-
somos individuais, que competiram em um torneio de pontos corridos. A classe Evolver
atribui três pontos por vitória, um pont o por empate e zero por uma derrota.
O vencedor de cada geração do torneio de ponto s corridos foi mantido para a próxima
geração. Os dois cromossomos do time pior classificado foram completamente retirados
da geração e foram também substituídos por mutantes de dois times do t opo. Os times
restantes foram compostos do cruzamento de quatro times sobreviventes. A formação
tática (3 −5 − 2) foi utilizada no time da primeira geração. Após a septuagésima geração ,
o time mais forte teve a defesa e o meio-campo aglutinados no cent r o de seu próprio meio
de campo, enquanto os atacantes não mudaram muito durante o jogo. Foi relata do que
muitos desses jo gos t erminaram empatados em 0−0, mostrando que os zagueiros estavam
bloqueando os atacantes. No entanto, os laterais tinham tomado posições muito à f r ente.
Na geração de número 256, a f ormação ofensiva do time mais apto mostrou que os laterais
6
ainda estavam bem po sicionados e que os atacantes estavam ta mbém em várias posições,
no caso o atacante mais avançado (mais perto do gol adversário). Foi concluído que novas
formações surgiram com base no cruzamento dos cromossomos entre os times mais forte,
sendo que a adaptação dos jogadores para preencher posições diferentes começou a se
tornar evidente.
Em Jeong e Lee (1997), uma versão simplificada de um jogo de futebol simulado foi
utilizada para testar o sucesso de um AG, em relação à capacidade de um jogador de
aprender uma habilidade especial. Um jogo, utilizando células, é implementado para
representar o campo. Um passo corresponde ao movimento de cada jo gador deslocando-
se em cada quadrado. O campo foi constituído por uma área de 6 × 5 células, como
mostrado na Figura 1.2. Há dois times, em que cada um é compo sto por dois agentes
idênticos. Existe também uma bola e dois objetivos, localizados centralmente em ambas
as extremidades do campo.
Figura 1.2: Área utilizada para o exe rcício de treinamento dos jogadores (Jeong e L e e, 1997).
Cada agente tem uma escolha ent re três ações: chutar, andar e driblar. Chutar permite
que o jogador em posse da bola possa chutar a mesma mais de duas células. Andar permite
ao agente mudar para uma célula adjacente, enquanto driblar é o mesmo movimento que
andar, mas usado somente quando em posse da bola.
Para a pesquisa do cromossomo usou-se uma string com 3.300 genes, o btida a par tir
de todas as diferentes combinações possíveis do ambiente, como a posição do agente, a
posição da b ola, ação do agente, etc. Cada solução possível do cromossomo foi medida
7
usando uma função de fitness. No decorrer de um jogo, o time recebeu 100 pontos para
cada go l e 10 pontos para cada vez que se encontrava em posse da bola. Os pont os eram
negativamente concedidos ao time que sofrer um gol (−90), ou que não estavam em posse
da bola (−10).
O cromossomo mais apto, baseado nesta pontuação, foi mantido para a próxima ge-
ração. Cada geração consistiu de 50 cromossomos. Os cromossomos restantes foram
mutados, com uma probabilidade de 1%, e cruzou-se com uma probabilidade de 50%. O
pior dos cromossomos foi retirado a cada geração.
Os resultados para cada caso mostra que o AG foi sempre capaz de encontrar uma
solução. O mais bem sucedido f oi o caso 2, onde apenas se precisou de 10 geraçõ es para
chegar a um resultado. No caso 3, foram necessários mais de 120 gerações para encontrar a
solução. Concluiu-se que a maior interação com o time adversário ocorreu no presente caso
e, portanto, teve mais tentativas para acontecer isso. Todos os três casos apresentaram
uma t endência geral que mostra que, ao longo das gerações, o ranking fitnes s continua
aumentando, o que implica também na melhora do time.
1.3 Organização da Dissertação
No Capítulo, 2 será trat ado do tema futebol de robôs, explicitando desde os aspectos
da competição (RoboCup) até as suas categorias. Abordará também o time Uva Trilearn,
o qual foi utilizado como base para o desenvolvimento do time proposto.
No Capítulo 3, será abordado os aspectos teóricos sobre AG e sua respectiva imple-
mentação. Tratará também do problema de otimização multi-objetivo, do conceito de
Dominância de Fronteira de Pareto.
O Capítulo 4 é referente à metodologia pro posta. Além de ser po ssível verificar o
cenário de aplicação do algoritmo apresentado.
Finalmente, o Capítulo 5 serão descritas as conclusões a respeito dessas investigações,
assim como, serão apresentados algumas direções par a futuros trabalhos.
8
1.4 Trabalhos Publicados
FRACCAROLI, E. S. ; SILVA, I. N. . Abordagem Fuzzy para Determinação de Es-
tratégia em Ambiente de Futebol de Robôs Simulado. In: 8th Brazilian Conference on
Dynamics, Control and Applications, 2009, Bauru - SP. Proceedings of the 8th Brazilian
Conference on Dynamics, Control and Applications, 2009. Vol. 8. pp. 1-6.
FRACCAROLI, E. S. ; SILVA, I. N. . Abordagem Genética para Definição de Ações
em Ambiente Simulado de Futebol de Robôs. In: IX Simpósio Brasileiro de Automação
Inteligent e, 2009, Brasília. ANAIS DO IX SIMPÓSIO BRASILEIRO DE AUTOMAÇÃO
INTELIGENTE, (CD-ROM // paper number: 55708 // 06 páginas), 2009.
9
Capítulo 2
Futebol de Robôs
O conceito de futebol de robôs autônomos foi introduzido em 1993 po r Itsuki Nota
(Kitano et al., 1995). A competição de futebol de robôs tem como pretexto o desenvol-
vimento de técnicas de inteligência artificial, para aplicações robóticas, utilizando um
problema padrão em que um grande leque de possíveis tecnologias possam ser examina-
das. Aprendizado por reforço, aprendizado por reforço baseado em heurísticas, algoritmos
genéticos, sistemas fuzzy e redes neurais artificiais são as tecnologias mais utilizadas no
ambiente de futebol de robôs.
Neste capítulo, a Seção 2.1 tratará sobre os aspectos da RoboCup e suas principais
categorias. O conceito e arquitetura do ambiente simulado de futebol de robô s será
discutida na Seção 2.2. A Seção 2.3 abordará sobre o time UvA Trilearn e seu conceito
de divisão de camadas de competências.
2.1 Aspectos da RoboCup
A RoboCup (Robot World Cup) teve seu início no Japão e tem como ambicioso objetivo
criar um time de robôs humanóides, totalmente autônomos, capazes de ganhar dos cam-
peões mundiais de futebol humano (RoboCup, 2009). A RoboCup possibilita pesquisas
nas áreas de robótica e inteligência artificial, disponibilizando um problema desafiador que
oferece a integração de pesquisas nas diversas áreas da robótica e da inteligência artificial,
10
como exemplo, agentes autônomos, visão computacional, cola boração multiagente, com-
portamento reativo, aprendizado, controle de movimento, controle inteligente robótico,
evolução, resolução em tempo real, entre outros (Kitano et al., 1998).
Existem cinco categorias na RoboCup, ou seja, Simulation, Humanoid, Middle S i ze,
Small Size e Standard Platform, cada uma com o foco em diferentes níveis de abstração
para o respectivo problema.
A categoria Humanoid (Figura 2.1), possui no máximo dois robôs bípedes em cada
time, e tem como foco a pesquisa na s ár eas que incluem: andar dinamicamente, correr,
chutar a bola, percepção visual da localização de objetos em campo e a uto-localização.
Figura 2.1: Robô s da categoria Humanoid da RoboCup (RoboCup, 2009).
Na categoria Middle S i ze (Figura 2.2), cada time pode jogar com o número máximo
de quatro robôs. Cada robô não pode ultrapassar 75cm de altura e 50cm de diâmetro.
Suas principais áreas de pesquisas incluem: localização, visão computacional, integração
de sensores, percepção distribuída, controle de movimentos do robô e hardware.
11
Figura 2.2: Robô s da categoria Middle Size da RoboCup (RoboCup, 2009).
A categoria Small Size (Figura 2.3) é composta po r um time de no máximo cinco
robôs, cada um com 15cm de altura e 18cm de diâmetro. Esta possui as mesmas áreas de
pesquisas da categoria Middle Size.
Figura 2.3: Robô s da categoria Small Size da RoboCup (Rob oCup, 2009).
A categoria Stand ard Platform possui dois tipos de robôs, um bípede e um quadrúpede,
fabricados por diferentes empresas, os quais são utilizados pa ra formar um time de futebol
robótico. O r obô bípede é chamado de NAO (Figura 2.4), fabricado pela empresa francesa
12
Aldebaran Robotics. O robô quadrúpede é chamado de AIBO (Figura 2.5), fabricado pela
empresa japonesa Sony. Suas áreas de pesquisas são as mesmas da categoria Humanoid,
incluindo somente a complexidade de controlar os movimentos das quatro patas no caso
do rob ô AIBO.
Figura 2.4: Robô s NAO da categoria Standard Platform da RoboCup (Rob oCup, 2009).
Figura 2.5: Robô s AIBO da categoria Standard Platform da RoboCup (RoboCup, 2009).
A categoria S i mulation possui o nze jogadores e um técnico por time. Suas áreas de
pesquisas incluem, a colaboração multiagente, o desenvolvimento de técnicas de otimiza-
13
ção e a aplicação de sistemas inteligentes. Diferente das outras categorias da RoboCup,
essa categor ia preocupa-se exclusivamente com o desenvolvimento da inteligência coletiva
do time.
Figura 2.6: Categoria Simulation 2D da RoboCup (RoboCup, 2009).
2.2 Categoria de Simulação 2D
O ambiente da RoboCup Simulação 2D apresenta as características de ser um ambiente
dinâmico, ruidoso
1
, cooperativo e coordenado. É composto por dois programas, o Soccer
Server (servidor) e o Soccer Monitor (monitor). O servidor é um ambiente que torna
possível o jogo de futebol entre dois times, sendo responsável po r simular os movimentos
dos jogadores e da bola, a comunicação com cliente (j ogador) e o controle do jog o conforme
as regras. Para desenvolver times torna-se necessário que se faça uso de ferramentas que
viabilizem a comunicação via UDP/IP (User Datagram Protocol/Internet Protocol), pois
toda comunicação feita entre o servidor e cada cliente é feita via sock e t UDP/IP, o qual é
um protocolo de comunicação orientado à conexão, incluindo-se mecanismos para iniciar
1
Para tornar as características do ambiente s imulado bem próximas daquelas de um ambiente real, o
servidor insere um ruído gaussiano na comunicação entre o servidor e o cliente, semelhante ao problema
real de comunicação entre os jogadores de um time com seu técnico.
14
e encerrar a conexão, negociar tamanhos de pacotes e permitir a retransmissão de pacotes
corrompidos (Chen et al., 2002).
Figura 2.7: Ilustração do monitor.
O monitor (Fig ura 2.7) é um programa responsável pela visualização do campo virtual
no mesmo, utilizando-se para tanto o sistema X window. Por meio dessa interface, é
possível observar os agentes j ogando de acordo com as informações enviadas pelo servidor.
As informações disponíveis no monitor incluem o placar, os nomes dos times, o tempo
decorrido e as posições dos jogadores e da bo la . É possível conectar vários monitores em
um servidor, a fim de ser visualizado o j ogo em monitores diferentes (Chen et al., 2002).
O cliente é um processo separado, responsável por atuar no ambiente simulado e por
conectar-se com o servidor por meio de uma única porta. Um time pode ter doze clientes,
onze jogadores e um técnico.
O cliente é r esponsável por atuar no ambiente simulado, sendo este o módulo em que
são desenvolvidos e aplicados os algoritmos inteligentes para serem avaliados. As ações
referentes ao comportamento dos jogadores devem ser executadas obedecendo a seguinte
ordem: primeiro, o cliente envia requisições para o servidor; em seguida, o servidor recebe
e armazena as requisiçõ es, as quais são analisadas para serem executadas (chutar a bola,
15
virar, correr, etc.); por fim, o ambiente é ent ão a t ua lizado e as ações são realizadas pelos
jogadores. Um cliente não pode enviar mais do que três ou quatro comandos por ciclos
de simulação para o servidor.
Cada partida realizada tem duração de aproximadamente dez minutos, valor este cor-
respondente a seis mil ciclos de simulação, sendo separado em dois tempos de aproxima-
damente cinco minutos. Quando a partida se encerra com empate, acrescenta- se então um
tempo adicional de três mil ciclos de simulação, sendo que o t ime que fizer o primeiro gol
vencerá a partida. Se mesmo depo is do tempo adicional a partida continuar empatada, é
então realizada a cobrança de pênaltis, e o time que conseguir uma vantagem maior do
que três gols marcados vencerá a partida (Chen et al., 2002).
Figura 2.8: Arq uitetura do simulador 2D (Reis, 2003).
Um cliente conecta-se com o servidor utilizando um soc ket UDP (Figura 2.8). Usando
o socket, o cliente envia comandos para controlar um jo gador e recebe informações dos
sensores do jogador. Em outras palavras, o programa cliente é o cérebro de um jogador.
O cliente recebe informações dos sensores visuais e sonoros do servidor, e envia comandos
de controle para o servidor.
Cada cliente pode controlar apenas um jogador. Ent ão, um time consiste de número
16
igual de clientes e jogadores. A comunicação ent r e os clientes pode ser feita via servidor
usando os protocolo s say e hear.
O a mbiente dos agentes simulados é uma estrutura hierárquica, dividida em dois am-
bientes. O ambiente de baixo nível é responsável por processar informações básicas,
recebidas do servidor, tais como: informações visuais, de som, de sensibilidade e, tam-
bém, é responsável por processar ações básicas como driblar, realizar um passe e chutar.
O outro é o ambiente de alto nível que possibilita a decisão do ponto de vista global, tais
como a estratégia de jogar de maneira coo perativa (Chen et al., 2002).
2.3 UvA Trilearn
O time UvA Trilearn foi desenvolvido na Faculdade de Ciência da Universidade de
Amsterdam. Foi tema da dissertação de mestrado de Boer e Kok (2002), na qual propunha
o desenvolvimento de um time com uma arquitetura dividida em três camadas, de acordo
com a Figura 2.9:
Figura 2.9: Arq uitetura do time UvA Trilearn (Boer e Kok, 2002).
• Camada de Interação: r esponsável pela interação com o servidor; recebe as infor-
mações dos sensores e envia para camada de competência; envia para o servidor as
17
ações recebidas pela camada de competência, de acordo a respectiva estratégia;
• Camada de Competência: utiliza as funcionalidades enviadas pela camada de inte-
ração a fim de construir um modelo abstrato do jogo e par a implementar os diversos
perfis de cada agente;
• Camada de Controle: responsável pelo raciocínio do sistema; a melhor possibilidade
de ação é selecionada da camada de competência, dependendo do estado atual do
jogo e da estratégia atual do time.
Figura 2.10: Principais componentes da arquitetura do time UvA Trilearn (Boer e Kok, 2002).
Na Figura 2.10 é apresentado o diagrama UML de classes, no qual é possível identificar
as relações de associação, composição e generalização entre as três camadas da arquitetura.
Em seguida, serão apresentadas todas as classes com mais detalhes.
18
• Conexão: component e responsável por criar uma conexão socke t UDP com o servi-
dor, contendo métodos para enviar e receber mensagens por meio dessa conexão;
• Controle dos sensores: esse comp onente processa as mensagens recebidas do ser-
vidor, particiona e envia as infor mações extraídas para o componente Modelo do
Mundo;
• Modelo do Mundo: responsável por criar a representação atual do jogo, do ponto
de vista observado pelo agente, determinando-se a po sição do agente, da bola e de
suas respectivas velocidades;
• Objeto: esse componente contém informações sobre todos os objetos na simulação,
como demarcações do campo, jogadores, bola e posição do gol;
• Formações: esse componente contém informações sobre as possíveis formações do
time e do método para determinar a posição estratégica;
• Configuração do Jogador: esse componente contém os valores de muitos parâmetros
do jogador, tal como a influência para resolver algum processo do agente e de definir
métodos para receber e atualizar esses valores.
• Jogador: contém métodos par a resolver sobre a possibilidade da melhor ação em
uma determinada situação;
• Jogador básico: esse componente contém todas as informações necessárias para um
perfil de jogador, como int erceptar a bola ou chutar a bola para uma determinada
posição do campo;
• Controle da ação: responsável por executar os comandos que o jogador deve realizar,
assim que foi recebido do componente Jogador básico.
O time UvA Trilearn apresenta como maior contribuição uma ar quitetura de três
camadas capazes de realizar o processamento paralelo dos dados, um esquema flexível de
sincronização do ambiente, métodos eficazes para localização de objetos e estimação de
velocidades usando filtros de partículas, uma camada hierárquica de competências, uma
política de pontos (gols) par a jogadores simulados e uma estratégia para um time eficaz.
19
Assim, encont r am-se disponíveis somente dois modos simples de ações no código do
UvA Trilearn (Figura 2.11). O primeiro é o modo de manuseio da bola e o segundo
é o modo de posicionamento, os quais serão utilizados pelos jogadores dependendo da
situação atual durante o jogo. Se o jogador estiver perto da bola, o modo manuseio da
bola é entã o executado. Este modo é executado quando o jogado r está perto da bola, o
qual avalia a possibilidade de chutar ou não; se existir a possibilidade de chutar, o mesmo
realizará uma ação consequente; por outro lado, se não existir t al possibilidade, haverá
então a ação de interceptar a bola. A ação de interceptar a bola consiste em po sicionar o
jogador no ponto de intersecção da trajetória da bola em relação a posição do adversário
(Boer e Kok, 2002).
Figura 2.11: Modos de ações presentes no código fonte do time UvA Trilearn (Boer e Kok, 2002).
O time UvA Trilearn possui 3 formações táticas, (3 -4-3), (4 -4-2) e (4-3-3). O UvA
Trilearn utiliza a formação tática (4-3-3), que corresponde em separar os jogado res a o
longo do campo em áreas de at uação. No caso, os quatro primeiros jogadores atuarão como
zagueiros, os três outros jogadores atuarão como meio-campo e os últimos três jogadores
atuarão como atacantes. Todos os jogadores só realizam uma única ação quando em posse
de bola, ou seja, chutam em direção ao gol adversário.
Nesse trabalho foi utilizado o time UvA Trilearn Base (versão 3.3) como t ime base
para aplicar o s modelos evolutivos computacionais. Essa versão encontra-se à disp osição
para uso comum em UvA Trilearn (2003).
20
2.4 Considerações Parciais
Neste capítulo fo i abordado o conceito de futebol de robôs. Apresentou-se a compe-
tição RoboCup (Seção 2.1) e suas respectivas categorias. Explicitou-se ainda de maneira
detalhada a categoria Simulação 2D na Seção 2.2, pois é a categ oria na qual esse trabalho
faz uso. No time Uva Trilearn, apresentado na Seção 2.3, serão aplicados o s respectivos
AGs (Capítulo 3).
21
Capítulo 3
Abordagem E volutiva Mono-Objetivo e
Multi-Obje tivo
Métodos baseados em computação evo lutiva constituem uma classe de algoritmos de
busca e otimização estocástica inspirados na teoria da evolução natural.
A gra nde vantagem dos algoritmos evolutivos (AE) encontra-se na possibilidade de
resolver problemas pela simples descrição de sua formulação matemática, sendo desne-
cessária a descrição explícita de todos os passos até o resultado. Os AEs apresentam
características robustas, podendo ser aplicados em diversos tipos de problemas. Os AEs
pertencem ao conjunto de técnicas e procedimento s a da ptáveis, aplicados em problemas
complexos, o nde técnicas tradicionais não poderiam ser aplicadas, ou seriam ineficazes.
Neste capítulo, a Seção 3.1 introduz o conceito da teoria da evolução, a qual é a base
fundamental para a modelagem dos algoritmos genéticos (Seção 3.2). A Seção 3.3 descreve
o conceito e características da otimização multi-objetivo, apresentando o algoritmo NSGA-
II (Seção 3.4), sendo utilizado como metodologia computacional o s algoritmos genéticos
mono-objetivo e multi-objetivo.
22
3.1 Teoria da Evolução
Charles Darwin
1
propôs a teoria da evolucão em 1 859 (Darwin, 1859), na qual indi-
víduos com boas características genéticas possuem maiores cha nces de sobrevivência e de
se reproduzirem, gerando-se, assim, indivíduos cada vez mais aptos. Por outro la do, os
indivíduos menos aptos tenderão a desaparecer. O diferencial dessa teoria em relação à
teoria Lamarckista
2
dá-se justamente na explicação de como se realiza a adaptação (sele-
ção natural) dos indivíduos de uma po pulação, pois L amarck acreditava na herança direta
das características adquiridas pelos indivíduos durante a vida. Já a seleção natural vem
sendo a principal idéia unificadora nas mais diversas áreas da biologia, pois a mesma é
um processo que distingui os processos biológicos dos demais processos físicos e químicos.
Darwin apresentou as seguint es hipóteses para explicar o processo de seleção natural:
• Os indivíduos (filhos) tendem a ser em maior número que os indivíduos (pais);
• O número de indivíduos de uma mesma espécie permanece constante;
• A partir do primeiro e do segundo item, pode-se concluir que haverá uma luta pela
sobrevivência;
• Dentro de uma mesma espécie, os indivíduos apresenta m pequenas diferenças em
relação as suas características, sendo que a maioria delas estão presentes nos res-
pectivos indivíduos (pais).
O princípio da seleção natural propõe que os indivíduos, cujas variações se adaptam
melhor ao ambiente, terão maior probabilidade de sobreviver e se reproduzir. A evolução
Darwiniana é nada mais que a consequência inevitável da competição entre processos de
reprodução de informação, operando no interior de uma população em um determinado
habitat comum (Francis, 2007).
1
Charles Darwin, na tur alista inglês, 1809-1882.
2
Jean Baptiste de Lamarck, naturalista francês, 1744-1829.
23
3.2 Algoritmos Genéticos
O conceito de algoritmos genéticos (AG) foi introduzido por Ho lland (1992) e sua
terminologia é baseada na t eoria da evolução. Tem como objetivo simular, p or meio de
algoritmos computacionais, os processos de adaptação de sistemas naturais utilizando um
sistema artificial.
O AG é um méto do de busca estocástica inspirada na teoria de Darwin (Seção 3.1),
que consiste em encontra r uma resposta (indivíduo) para um determinado problema com
um número gra nde de possíveis soluções (população). Para isso, utiliza-se dos métodos
de seleção de indivíduos, dos operadores genéticos de cruzamento (o u crossover) e da
mutação. Um indivíduo da população é representado por um único cromossomo, o qual
possui a codificação de uma possível solução do problema. Os cromossomos são geralmente
implementados na forma de listas de at r ibutos ou vetores de strings, o nde cada atributo
é conhecido como gene e os possíveis valores que um determinado gene pode assumir são
chamados de alelos (Holland, 199 2).
O processo de evolução executado por um AG corresponde a um procedimento de busca
em um espaço de soluções potenciais pa ra o problema. Esta busca requer um equilíbrio
entre dois objetivos apa r entemente conflitantes: o aproveitamento das melhores soluções e
a exploração do espaço de busca. Com isso, os AGs constituem uma classe de métodos de
busca de propósito g eral, que apresentam um considerável equilíbrio entre aproveitamento
das melhores soluções e da exploração do espaço de busca. O processo de busca se
dá de maneira multi-dimensional a cada geração; assim, as soluções consideradas b oas
(mais aptas) se reproduzem, enquanto as soluções consideradas ruins (menos aptas) são
descartadas. Uma propriedade importante dos AGs é que esses mantém uma população de
soluções candidatas, enquanto que outros método s alternativos, como sim ulated annealing
(Aarts e Korst, 1989), analisam um único ponto no espaço de busca a cada instante. Além
disso, os AGs po ssuem um paralelismo implícito decorrente da avaliação independente de
cada uma das cadeias de bits (cromossomo) que compõem os indivíduos. Emprega-se
ainda uma função de avaliação (fitness) para distinguir diferentes soluções, simulando
aqui o papel da pressão exercida pelo ambiente sobre o indivíduo (Michalewicz, 1996). O
Quadro 3.1 a presenta o pseudo-algoritmo do AG clássico proposto por Holland (1992).
24
Quadro 3.1 Pseudo-código de um AG clássico.
ALGORITMO GENÉTICO
Entrada:
N (tamanho da população)
T (número máximo de ge rações)
p
c
(probabilidade de cruzamento)
p
m
(taxa de mutação)
Saída:
A (conjunto não-dominado)
1. Inicialização: Conjunto P
o
= ∅ e t = 0. PARA i = 1, .., N FAÇA
a) Escolha i ∈ I segundo alguma probabilidade de distribuição.
b) Conjunto P
o
= P
o
+ i.
2. Fitness: PARA cada indivíduo i ∈ P
t
, determine o vetor de decisão x = m(i), bem como o vetor
objetivo y = f(x) e calcule o valor escalar do fitness F (i).
3. Seleção: População temporária P
′
. Conjunto P
′
. PARA i = 1, .., N FAÇA
a) Selecione um indivíduo i ∈ P
t
de acordo co m um determinado esquema, e com base no seu valor
de fitness.
b) Conjunto P
′
= P
′
+ i.
4. Cruzamento: Conjunto P
′′
= ∅. PARA i = 1, .., N/2 FAÇA
a) Escolha dois indivíduos i, j ∈ P
′
e remova ele de P
′
.
b) Recombine i com j. Os indivíduos (filhos) resultantes são k, l ∈ I.
c) Adicione k, l em P
′′
com probabilidade p
c
. De outra maneira adicione i, j em P
′′
.
5. Mutação: Conjunto P
′′′
= ∅. PARA cada indivíduo i ∈ P
′′
FAÇA
a) Mute i com taxa de mutação p
m
. O indivíduo resultante j ∈ I.
b) Conjunto P
′′′
= P
′′′
+ j.
6. Conclusão: Conjunto P
t+1
= P
′′′
e t = t + 1. SE t ≥ T ou SE alguma condição de parada for
satisfeita ENTÃO conjunto A = p(m(P
t
)) SE NÃO volte para o Passo 2.
O AG deve apresentar os seguintes componentes:
• Um método de seleção genética para soluções candidatas o u potenciais;
• Uma maneira de gerar uma população inicial para as possíveis soluções potenciais;
• Uma função para avaliar sua adaptação ao ambiente;
• Operadores genéticos, como cruzamento e mutação.
25
Para se f azer uso de um AG, em um determinado problema particular, é necessário
considerar a maneira da representação genética para as soluções potenciais (etapa de
codificação); meto dologia para criar e iniciar uma população inicial; função de avaliação
para classificar o quão próximo o indivíduo está da solução ótima; definir os operadores
genéticos; e definir os parâmetros livres do AG, como: tamanho da população, tamanho
do cromossomo, probabilidade da atuação do s operadores genéticos, condição de parada,
número de gerações, entre outros.
3.2.1 Representação dos Indivíduos
Para aplicar o AG a fim de encontrar a solução ótima de um problema qualquer, é
necessário considerar o aspecto de como será a representação deste problema, sendo que
essa é uma das etapas mais críticas da definição do algoritmo genético, pois dependendo da
definição inadequada da codificação, o AG pode t er problemas de convergência prematura
(Deb, 2001).
No AG clássico proposto por Holland (1992), os cromossomos são codificados em veto-
res de strings binárias de tamanhos fixos, onde cada gene do vetor de strings representa a
presença (1) ou ausência (0) de uma determinada característica. A grande motivação para
o uso da codificação binária vem da Teoria dos Esquemas (schemata theory), utilizada
para justificar por que os AGs f uncionam. Holland (1992) e Goldberg (1989) argumentam
que maximizando o paralelismo inerente do AG, seu desempenho também se maximizará,
provando que o alfabeto binário maximiza o paralelismo implícito.
Michalewicz (1 996) concluiu, a partir de testes entre um AG codificado em ponto
flutuante e um AG codificado em binário, que o desempenho de um AG codificado em
binário é pobre quando o espaço de busca possui dimensão eleva da . Destaca-se que essa
afirmação não representa o consenso entre autores dentro da literatura sobre AGs.
Segundo Michalewicz (1996), em diversas aplicações práticas, a codificação binária
aplicada em problemas contendo um espaço de busca contínuo, ou com necessidade de
maior precisão, demonstra um desempenho insatisfatório. Uma dificuldade é encontrada
com certas strings, por exemplo, as strings “01111” e “10000”, que para realizar uma
26
transição para uma solução vizinha no espaço real é necessário alterar muitos bi ts (Deb,
2001).
Outra dificuldade está na incapacidade para armazenar qualquer precisão arbitrária
em uma solução ótima. Em AGs codificados em binários, o tamanho da string pode ser
definido para armazenar uma certa precisão de uma solução. Quanto maior a precisão,
maior será o tamanho da string. Quanto maior for o tamanho da string, maior será o
tamanho da população, aumentando-se consequentemente a complexidade do algoritmo
(Deb, 2001).
Em problemas de otimização restrita, a codificação inadequada pode gerar indivíduos
modificados inválidos por cruzament o ou muta ção .
3.2.2 Definição da Popul ação Inicial
A população inicial pode ser gerada utilizando um método de inicialização aleatória
dos cromossomos. Quando houver conhecimento de alguma heurística, a resp eito do
problema, pode-se utilizá-la na criação, tendo cuidado para não gerar indivíduos inválidos
nesta fase. Cada um dos cromossomos deve ser avaliado de acordo com seu sucesso em
direção à solução do problema, sendo que tal avaliação é obtida por meio da função de
avaliação (fitness), cuja missão é estabelecer uma relação que permita medir o desempenho
de cada solução (Deb, 200 1).
O tamanho da população afeta diretamente no desempenho dos algoritmos genéticos,
isto é:
• Se a população gerada for pequena, a cobertura do espaço de busca do problema
também será pequena, obtendo-se assim um baixo custo computacional;
• Se a população gerada for grande, a cobertura do espaço de busca do problema
também será g r ande, o que pode prevenir convergências prematuras para soluções
locais; po rém, aumenta-se o custo computacional.
Depois de ter escolhido uma forma de representa ção dos esquemas de strings e ter
gerado a população de s tring s aleatórias, é necessário aplicar os operadores genéticos
27
para strings semelhantes a fim de se encont r ar a melhor p opulação de soluções.
3.2.3 Ope rado res Genéticos
Os operadores genéticos são aplicados aos indivíduos esperando-se o bter uma popula-
ção sucessiva cada vez mais apta, ou seja, mais próxima da solução ótima. Os operadores
genéticos mais utilizados são cruzamento (recombinação gênica) e mutação. São gerados
novos indivíduos (filhos) a partir das características herdadas dos indivíduos (pais).
O operador genético de cruzamento (cros sover) produz novas soluções a part ir do cru-
zamento de dois ou mais indivíduos da geração atual, trocando assim, informações entre
diferentes soluçõ es candidatas. Existem muitas variações de cruzamento, muitas delas es-
pecíficas para um determinado problema, não existindo entã o um tipo de cruzamento que
seja mais eficiente. Cada variação de cruzameto pode ser particularmente eficiente para
uma determinada classe de problemas e extremamente ineficiente para outras (Rezende,
2003).
Figura 3.1: Exemplo de um cruzamento entre dois cromossomos (Plant e Schaefer, 2 008).
No AG clássico, o operador de cruzamento mais utilizado é o cruzamento de um ponto.
Antes de aplicar esse operador, primeiro são selecionados dois indivíduos (pais), depois
seus cromossomos são recombinados, gerando então dois novos indivíduos (filhos). De
acordo com a Figura 3.1, após a seleção de dois indivíduos (pais), é necessário definir um
ponto de corte aleatório igual para os indivíduos (pais). Em seguida, os segmentos g erados
a partir do ponto de corte serão trocados, gerando-se assim dois novos indivíduos (filhos).
28
Cada indivíduo (filho) contém, em seu próprio cromossomo, metade do cromossomo do
Pai 1 e o utra metade do cromossomo do Pai 2.
O operador de cruzamento é utilizado como um operador de recombinação dos melho-
res indivíduos tentando preservar as características boas de cada um. Para preservar as
strings boas durante a aplicação do operador de recombinação, nem todas as strings de
uma população serão utilizadas no cruzamento. Se uma probabilidade de cruzamento de
p
c
é utilizada, então 100p
c
% de strings da população serão usadas na operação de cruza-
mento e 100(1 − p
c
)% da população serão simplesmente copiadas para a nova população
(Deb, 2001).
O operador de mutação modifica aleatoriamente um ou mais genes de um cromossomo,
sendo o mesmo essencial por dois motivos. Primeiro, na natureza, mutações podem ocorrer
de maneira aleatória. Segundo, e mais importante, em um contexto de um problema que
visa atingir o objetivo ótimo, isso impede que a população torne-se uniforme e incapaz de
se desenvolver e, também, prevê a possibilidade de saltar pontos de mínimos ou máximos
locais. Define-se então qual será a probabilidade de mutação p
m
, ou seja, quantos genes
estarão sujeitos à mutação em um cromossomo. Geralmente a probabilidade de mutação
é um valor baixo, para manter a diversidade na população sem destruir o progresso já
obtido. Para indivíduos codificados binariament e, o operador de mutação tro ca o valor
do gene escolhido para 1 , se for de valor 0, ou vice-versa (Rezende, 2003).
O procedimento de mutação de um bit necessita a criação de um número aleató r io para
cada bit. Para reduzir o esforço computacional, Goldb erg (1989) sugeriu um operador de
mutação baseado no tempo, onde depois de um bit ser mutado, a localização do próximo
bit a ser mutado é determinada por uma distribuição exponencial. A característica da
distribuição é dada por µ = 1/p
m
. Primeiro, é criado um número aleatório r ∈ [0, 1].
Então, estima-se o próximo bit a ser mutado a partir de saltos de η = −p
m
ln(1 − r)bits
do bit corrente (Deb, 2001).
Os operadores de cruzamento e de mutação são simples e claros. Após selecionar boas
strings, o operador de cruzamento recombina boas substrings a partir de duas outras boas
strings de forma a se esperar uma substring melhor. Já o operador de mutação altera
apenas um ponto da string esperando criar uma string melhor. Espera-se que, se strings
29
ruins forem criadas, que elas sejam eliminadas pelo operador de reprodução na próxima
geração e, se boas strings forem criadas, que elas sejam enfatizadas.
3.2.4 Seleção dos Indivíduos
São utilizados diversos métodos para seleção dos indívíduos, sendo que o s mais utiliza-
dos são: seleção por roleta (roulette wheel), seleção elitista e seleção baseada em torneio.
O método de seleção por roleta (Michalewicz, 1996) atribui a cada indivíduo da popu-
lação um valor correspondente à probalidade de estar presente na próxima geração . Esta
probabilidade é proporcional ao valor da f unção de avaliação medido de cada indivíduo,
em relação à somatória dos valores da função de avaliação de todos indivíduos de uma
população. Assim, quanto maior o valor da função de avaliação de um indivíduo, maior
a probalidade dele estar presente na próxima geração. Este método de seleção apresenta
o seguinte problema: por ser um método de seleção aleatório, no momento da seleção o
melhor indivíduo da população pode não ser selecionado.
O método de seleção elitista foi propo sto para solucionar o problema do método de
seleção por roleta. Esse método seleciona o melhor indivíduo da população e o insere na
próxima população (Michalewicz, 1996).
No método de seleção baseada em torneio, os indivíduos são ordenados de acordo com o
valor correspondente do fitness de cada indivíduo da população, e a posição dos indivíduos
é utilizada para determinar a probabilidade de seleção (Deb, 2001). Uma variação desse
método é simplesmente passar os n melhores indivíduos para a próxima geração.
3.3 Otimização Multi-Objetivo
O problema de otimização multi-o bjetivo (POMO)
3
pode também ser definido como
um problema de busca. Como o próprio nome sugere, um POMO apresenta um incon-
tável conjunto de soluções que, quando avaliadas, produzem vetores cujos comp onentes
3
Também chamado de otimização de multi-critérios, multi-desempenho ou problema de otimização de
vetores.
30
representam as soluções conflitantes no espaço objetivo (Coello et al., 2002).
Um POMO possui um conjunto de funções objetivos a serem otimizadas e restrições
que devem ser satisfeitas por qualquer solução viável
4
(Deb, 2001). O conjunto de todas
as soluções viáveis é conhecido como espaço de busca ou região viáv el.
Um POMO genérico será formalmente apresentado a seguir.
Definição de POMO: Encontrar o vetor x
∗
= [x
∗
1
, x
∗
2
, ..., x
∗
n
]
T
que satisfaça as m
restrições de desigualdade:
g
i
(x) ≥ 0 i = 1, 2, ..., m (3.1)
as p restrições de igualdade:
h
i
(x) = 0 i = 1, 2, ..., p (3.2)
e que otimize o vetor função:
f(x) = [f
1
(x), f
2
(x), ..., f
k
(x)]
T
(3.3)
O obj etivo é determinar, dentre o conjunto de todos os números que satisfaçam os dois
conjuntos de restrições, o conjunto particular x
∗
1
, x
∗
2
, ..., x
∗
n
que produza o melhor valor da
função objetivo.
As restrições impostas definem a região viável Ω e qualquer ponto x em Ω é considerado
uma solução viável. O vetor função
f(x) é uma função que mapeia o conjunto Ω dentro
do conjunto Λ, que representa todos os valores possíveis da função objetivo, chamado de
fronteira de Pareto (Seção 3.3.1). Os k componentes do vetor função
f(x) representa m
o critério não comensurável que devem ser considerados. As constantes g
i
(x) e h
i
(x)
representam as restrições impo stas sobre as va r iáveis de decisão. O vetor x
∗
é reservado
para designar as soluções ótimas e que, geralmente, apresentam mais de uma solução
4
Uma solução x é viável se, e somente se, satisfazer todas as restrições. Caso contrário, a solução não
será viável.
31
ótima (Coello et al., 2002).
Existem três possibilidades em POMO: minimizar todas as funções objetivo; maxi-
mizar todas as funções objetivo, ou ainda, minimizar algumas e maximizar outras. Por
razões de simplificação, nor malmente todas as funções são convertidas para a forma de
maximização ou minimização maxf
i
(x) = −min(−f
i
(x)).
3.3.1 Conceito de Do minância e Pareto-Ótimo
Na maioria dos algoritmos de otimização multi-objetivo é usado o conceito de domi-
nância. Nesses algoritmos, duas soluções são comparadas para identificar se uma solução
domina a outra ou não.
Para definir, tanto em minimização ou maximização de funções objetivo, se uma so-
lução u é melhor do que uma solução v, é utilizado o operador entre as duas soluções,
como em u v. Se uma solução u é pior do que uma solução v, é então utilizado o
operador , como em u v (Deb, 2001).
Definição de Dominância: Uma solução x
1
é dita dominada por outra solução x
2
,
se a s condições 1 e 2, especificadas a seguir, forem ambas verdadeiras:
1) A solução x
1
é não pior que x
2
em todos os objetivos, ou seja:
f
j
(x
1
) f
j
(x
2
), para todo j = 1, 2, ..., M (3.4)
2) A solução x
1
é estritamente melhor que x
2
, em pelo menos um objetivo, isto é:
f
j
(x
1
) f
j
(x
2
), para pelo menos um j = 1, 2, ..., M (3.5)
No conjunto de soluções encontr adas, nenhuma delas é melhor do que as demais em
pelo menos um objetivo. Estas são chamadas de soluções não dominadas, também conhe-
cidas como soluções de Pareto
5
. Além dessas soluções, existem também aquelas soluções
5
Vilfredo Pareto, político, sociólogo e economista italiano, 1848-1923.
32
dominadas, para as quais todos os objetivos encontrados são inferiores a pelo menos uma
outra solução encontrada. A Figura 3.2 apresenta essas soluções.
Figura 3.2: Pareto ótimo no espa ç o de o bjetivo e a possível relação entre as soluções (Zitzler, 1999).
Assim, para propósitos de elucidação, considera-se aqui o exemplo de um POMO
com dois objetivos e com cinco soluções distintas no espaço de objetivo, apresentado na
Figura 3.2. Suponha que a função o bjetivo f precise ser maximizada, enquanto que a
função objetivo g precise ser minimizada. São então apresentadas na Figura 3.2, cinco
possíveis soluções. Como ambos objetivos são importantes, geralmente é difícil encontrar
uma solução que seja a melhor em ambos os objetivos. O conceito de dominância é
aplicado para decidir qual solução é melhor para ambos objetivos. Comparando-se a
solução E com a solução C, é possível notar que a solução C é melhor do que a solução E
em relação à função objetivo f, e também, a solução C é melhor do que a solução E em
relação à função objetivo g. Quando ambas as condições de dominância forem satisfeitas,
é portanto possível afirmar que a solução C domina a solução E, ou C E.
Utilizando o mesmo exemplo da Figura 3.2, é comparada a solução A com a solução
C. Observa-se que a solução A é melhor de que a solução C em relação à função objetivo
f, enquanto a solução A é pior do que a solução C em relação à função objetivo g. Neste
caso, a primeira condição de dominância não foi satisfeita para essas soluções. Portanto,
não é possível afirmar que a solução A domina a solução C, ou que a solução C domina a
solução A. As soluções A e C são chamadas nesse caso de soluções não dominadas. Com
respeito a ambos objetivos, não se pode então afirmar qual das duas soluções é a melhor
delas.
33
Como se pode observar, as soluções dominadas não são melhores em nenhum aspecto
que as não dominadas, sendo assim deverão ser descartadas. O conjunto das soluções não
dominadas pode ser representado no espaço cartesiano, formando-se então a chamada
frente de Pareto ou fronteira de Pareto. As soluções Pareto ótimas ou conjunto Pare to
ótimo, ou ainda, fronteira ótima de Pareto, formam o conjunto de soluções não dominadas
em relação a todas as soluções possíveis.
No caso de AEMOs (Algoritmos Evolutivo Multi-objetivo) (Seção 3.4), o uso de vá r io s
objetivos conflitantes muda a definição de ótimo: em lugar de se encontrar uma solução
ótima (usando um objetivo), geralmente, encontra- se um conjunto de soluções ótimas. É
importante ressaltar que, ao contrár io de um AG mono-objetivo, em que resulta em uma
única solução ótima no final da execução, o AG multi-objetivo resulta em várias soluções
ótimas (soluções não-dominadas).
3.4 Algoritmo Evolutivo Multi-Objetivo
O primeiro AEMO a ser implementado foi proposto por Schaffer (1984). Ele foi cha-
mado de VEGA (Vector Ev alueted Genetic Algorithm) , por se tratar de um AG que avalia
vetores de obj etivos, com cada elemento do vetor representando cada função objetivo. O
VEGA tem como va ntagem ser de fácil implementação, pois requer pequenas mudan-
ças em um simples AG a fim de convertê-lo em um AEMO, sem necessitar de qualquer
complexidade computacional. Porém, tem-se como desvantagem o fato de não se obter
uma boa diversidade nas soluções da fronteira de Pareto (Seção 3.3.1), pois geralmente
as soluções tendem a ficar muito próximas da solução ótima.
A manutenção de uma população bem diversificada é de fundamental importância
para a eficácia de um AEMO. Face a esta constatação, Goldberg (1 989) propôs o conceito
de não dominância e explicitou o operador que preserva a diversidade de uma população,
eliminando-se assim o problema encontrado no VEGA. No conceito de dominância, insere-
se mais cópias de indivíduos não dominados em uma população; já a diversidade de
uma população, foi tratada com a estratégia de nichos entre uma classe de soluções não
dominadas ( Deb, 2001).
34
O primeiro algoritmo a dar ênfase para o conceito de dominância e a diversidade da po-
pulação foi o MOGA (Multi-Objective Genetic Algorithm), proposto por Fonseca e Fleming
(1993). O MOGA difere de um AG clássico pela forma de atribuição dos valores de fitnes s
para cada solução em uma po pulação. Para cada solução, associa-se um valor de ranking,
igual ao número de soluções n
i
que a domina mais um, ou seja:
r
i
= 1 + n
i
(3.6)
Assim, o valor de rank ing das soluções não dominadas é igual a um, fazendo com que
pelo menos um indivíduo de uma população possua o valor de r
i
= 1. O valor máximo
de r
i
não excede o tamanho N da população (Deb, 2001).
Com base nas idéias iniciais propostas por Goldberg (1989), foram então propostos
diversos modelos de AEMOs. A Tabela 3.1 apresenta os principais modelos de AEMOs
encontrados na literatura e seus respectivos autores.
Ta bela 3.1: Diferentes modelos de AEMOs.
Sigla Nome do Modelo Autores
VEGA Vector Evaluated Genetic Alg orithm (Schaffer, 1984)
WBGA Weight Based Genetic Algorithm (Hajela e Lin, 1992)
MOGA Multiple Objective Genetic Algorithm (Fonseca e Fleming, 1993)
NSGA Non-Dominated Sorting Genetic Algorithm (Srinivas e Deb, 1994)
NPGA Niched-Pareto Genetic Algorithm (Horn et al., 1994)
NSGA-II Elitist Non-Dominated Sorting Genetic (Deb et al., 2000)
Algorithm
SPEA, Strenght Pareto Evolutionary Algorithm 1 e 2 (Zitzler, 1999),
SPEA-2 (Zitzler et al., 2001)
PAES Pareto-Archived Evolutionary Strategy (Knowles e Corne, 1999)
MONGA-I, Multi-Objective Messy Genetic Algorithm (Veldhuizen, 1999)
MONGA-I I
Micro-GA Multi-Objective Micr o-Genetic Algorithm (Coello e Pulido, 2001)
PESA-I, PESA-II Pareto Envelope-Base Selec tion Algorithm (Corne et al., 2001)
DRMOGA Divided-Range Multi-Objective Genetic Algorithm (Hiroyasu et al., 2000)
35
SNSGA Steady-State Non-Dominated Sorting Genetic Algorithm (Gao et al., 2000)
FMOGA Fuzzy Multi-Objective Genetic Algorithm (Zhang et al., 2 004)
RMOGA Relational Multi-Objective Genetic Algorithm (Lee e Tsui, 2004)
O modelo de AEMO utilizado neste trabalho, para realizar a comparação entre AEs
aplicados no domínio do futebol de robôs, foi o NSGA-II (Elitist Non-Do minated S orting
Genetic Algorithm). Dentre os AEMOs da Tabela 3.1, o NSGA-II é o mais utilizado
atualmente na literatura em virtude de suas características. A Seção 3.4.1 descreve o
algoritmo NSGA-II.
3.4.1 Algoritmo NSGA-II
O algoritmo NSGA-II não possui semelhanças com o original NSGA, proposto por
Srinivas e Deb (1994). Manteve-se o nome simplesmente para destacar o local e origem
da criação. O NSGA-II foi proposto por Deb et al. (2000) e trabalha de modo semelhante
ao AG clássico, gerando uma população filha Q a partir de uma população pai P . Tanto
o tamanho da população P , quanto da população Q, são de ta manho fixo N. Na primeira
iteração gera-se a população inicial P
t
, ordenando-a por não dominância (Seção 3.3.1).
Em seguida, aplica-se os operadores de seleção por torneio (Seção 3.2.4), cruzamento e
mutação para se obter a população filha Q
t
.
A união da população P
t
com a população Q
t
se dá por R
t
, com |R| = 2N. As
fronteiras F
1
, F
2
..., são obtidas or denando R
t
por meio de não dominância e inseridas
todas na nova população P
t+1
. Somente N soluções serão inseridas na nova população
P
t+1
, outras N soluções de R
t
serão rejeitadas. Todas fronteiras F
i
devem ser inseridas
em P
t+1
, enquanto P
n+1
+ |F
i
| ≤ N. Ao inserir um F
j
, ta l que |F
j
| > N − |P
n+1
|, o
algoritmo NSGA-II seleciona as soluções de F
j
que estejam melhor distribuídas. A Figura
3.3 apresenta o esquema do algoritmo NSGA-II.
36
Figura 3.3: Modelo esquemático do algoritmo NSGA-II (Deb, 2001).
O NSGA-II tem como base dois princípios, ou sejam:
• Ordenação das soluções não dominadas da população (Quadro 3.2);
• Determinação da métrica definida pelos autores como distância de multidão ou
distância de agrupamento (Quadro 3.3).
Seleção de Torneio por Multidão
A ordenação das soluções não dominadas da população baseia-se simplesmente na
identificação das soluções não dominadas de uma população a cada iteração, e no modo
de armazenar estas em um conjunto de soluções não dominadas de acordo com o nível de
dominância.
Definição da Seleção de Torneio por Multidão: é inserido no método de sele-
ção por torneio o operador de comparação <
c
, para comparar duas soluções. A solução i
será considerada melhor que a solução j, se ambas condições 1 e 2 forem verdadeiras, isto é:
1) Se a solução i for melhor classificada em relação ao nível de não dominância, r
i
< r
j
;
2) Se ambas possuírem o mesmo nível de não dominância, mas i possui uma distância
da população maior, d
i
> d
j
.
37
Quando as iterações são iniciadas, a primeira solução da população é armazenada no
conjunto de soluções não dominadas e as soluções restantes são avaliadas. Se uma solução
dominar alguma solução que esteja armazenada no conjunto de soluções não dominadas,
estas soluçõ es dominadas são retiradas do conjunto de soluções dominantes e repete-se
este procedimento até que to da s as soluções da população sejam avaliadas. Desta forma,
determina-se a frente de nível 1. Esse procedimento repete-se até que todas as frentes
com diversos níveis de dominância sejam montadas, ordenando-as assim, todas as soluções
da po pulação com base no conceito de dominância. O Quadro 3.2 apresenta o pseudo-
algoritmo do NSGA-II prop osto por Deb et al. (2000).
Quadro 3.2 Pseudo-código do NSGA-II.
ALGORITMO NSGA-II
Variáveis:
P (população pai)
Q (população filha)
N (tamanho fixo da população P e Q)
F
j
(conjunto de soluçõe s na fronteira j)
nMax (número máximo de geraç ões)
n (número da geração atual)
1. Gerar a população inicial P
0
e Q
0
= ∅.
2. Atribuir n = 0.
3. Realizar a seleção, o cruzamento e mutação para gerar a população filha Q
0
.
4. Fazer R
n
= P
n
∪ Q
n
.
5. Realizar a ordena ção por não dominância em R
n
.
6. Criar P
n
+ 1 = ∅.
7. ENQUANTO |P
n+1
+ F
j
| ≤ N FAÇA.
a) Copiar a s soluções de F
j
em P
n+1
.
8. Calcular as distância de multidão em F
j
.
9. Ordenar F
j
de aco rdo com as distâncias d
j
.
10. Copiar as primeir as N − |P
n+1
| soluções de F
j
para P
n+1
.
11. Aplicar a seleção de torneio por multidão para os indivíduos de P
n+1
.
12. Aplicar os o peradores de cruzamento e de mutação para gerar a nova população Q
n+1
.
13. SE n > nMax ENTÃO parar
14. SENÃO atribuir n = n + 1 e retornar para o passo 4.
38
Distância de Multidão
A distância de agrupamento ou distância de multidão (crowding distance) fornece
uma estimativa da densidade de soluções próximas de uma solução i de uma população.
Primeiramente, mede-se a distância média entre as duas soluçõ es par a ambos os lados da
solução i, ao longo de cada um dos objetivos. Em seguida, todas as soluções extremas
6
recebem um valor infinito de distância. Para todas as outras soluções intermediárias
atribui-se um valor de distância, que corresponde à diferença do valor da função objetivo
do restante das soluções. Este procedimento se repete para t odas as funções o bjetivos,
sendo que o valor da distância de agrupamento é a soma das distâncias individuais para
cada objetivo.
Quadro 3.3 Pseudo-código da distância de multidão no NSGA-II.
ALGORITMO Distância de Multidão
Variáveis:
F
j
(conjunto de soluçõe s na fronteira i)
1. l denota o número de soluções em F
j
.
2. PARA cada so lução em F j atribui-se d
i
= 0 FAÇA.
3. PARA cada função objetivo m = 1, 2, . . . , M FAÇA.
a) Ordenar de forma decres c e nte as soluções por f
m
na lista I
m
4. PARA cada so lução extrema (mínimo e máximo) em cada um dos M objetivos FAÇA
a) Fazer d
I
m
1
= d
I
m
l
= ∞
5. PARA as soluções i = 2, . . . , l − 1 calcula r:
d
I
m
i
= d
I
m
i
+
f
I
m
i+1
m
− f
I
m
i−1
m
f
max
m
− f
min
m
(3.7)
Este algoritmo é descrito no Quadro 3.3, onde o índice I
j
representa o índice da i-
ésima solução na lista ordenada pelo objetivo m. Para qualquer objetivo, I
1
e I
l
são
os elementos da lista com o menor e o maior m, respectivamente. f
I
m
i+1
m
e f
I
m
i−1
m
são os
valores dos vizinhos de i na m-ésima função objetivo. Os f
max
m
e f
min
m
são parâmetros
dos valores da população máxima e da população mínima da m-ésima função objetivo.
6
Soluções testadas com valores maiores ou menores da função objetivo.
39
A Equação (3.7) garante que as soluções mais afastadas tenham d
i
maior do que aquelas
mais próximas.
3.5 Diferenças Fundamentais entre Otimização Mono-
Objetivo e Multi-Objetivo
Nesta seção ilustra-se a diferença fundamental entre otimização mono e multi-objetivo
por meio de um problema de otimização com dois objetivo s. Para dois objetivos confli-
tantes, cada objetivo corresponde a uma solução ótima diferente. No problema de decisão
da Figura 3.2, as soluções A e C são soluções ótimas. Se for assumir em sacrificar a
função g para estender um pouco até a solução A, é possível encontrar uma outra solução
em relação à função g que seja melhor. Idealment e, o aumento do sacrifício em relação à
função g é relacionado com o ganho em relação à função f. Assim, pode-se visualizar um
conjunto de soluções ótimas (semelhant es às soluções A, B, C, D e E), onde um ganho
em um objetivo significa sacrificar o outro objetivo.
Com todas estas soluções conflitantes, pode-se dizer que uma solução é a melhor no
que diz respeito a ambos os objetivos? A verdade reside no fato de que nenhuma solução
deste conjunto, para ambos os objetivos (função objetivo f e função objetivo g), parece ser
melhor do que qualquer outra solução do conjunto. Assim, em pro blemas de otimização
que possuem mais de um objetivo conflitante, não existe uma única solução ótima. Existe
um conjunto de soluções que são to das soluções ótimas. Sem possuir alguma informação
adicional, nenhuma solução a partir do conjunto de soluções ótimas pode ser dita como
sendo melhor do que qualquer outra solução. Uma vez que são um conjunto de soluções
ótimas, em um POMO, muitas dessas soluções ótimas são important es. Esta é a diferença
entre uma otimização de problemas mono-objetivo e multi-objetivo. O importante em
uma otimização mono-objetivo é uma única solução ótima, enquanto que, na otimização
multi-obj etivo, uma série de soluções ótimas resultantes entre os objetivos conflitantes
são impo r t antes (Deb, 2001).
A o utra diferença entre multi-o bjetivo e mono-objetivo é o espaço de busca: no multi-
objetivo é multi-dimensional, sendo que cada solução x, no espaço de decisão, possui f(x)
40
em Z; e no mono-objetivo, é unidimensional.
3.6 Considerações Parciais
Neste capítulo foram abordados os conceitos dos AEs, explicitando-se as características
básicas de um AG clássico mono-objetivo (Seção 3.2). Também f oi abordado o conceito
da otimização multi-objetivo (Seção 3.3) e seu respectivo a lgoritmo (Seção 3.4). Foi deta-
lhado ainda o algoritmo NSGA-II (Seção 3.4.1). A Seção 3.5 deixa claro que a diferença
fundamental entre multi-o bjetivo e mono-objetivo é o espaço de busca: o multi-objetivo
é multi-dimensional, onde cada solução x, no espaço de decisão, possui f(x) em Z; e o
mono-objetivo é unidimensional. Este trabalho utiliza o AG clássico e o NSGA-II como
estratégia evolutiva para selecionar as ações aplicadas em um time de futebol de robô s
(Capítulo 4), a fim de medir o desempenho de ambos os métodos.
41
Capítulo 4
Formulação do Time par a Abordagem
Mono-Obje tivo e Multi-Objetivo
Neste trabalho foram utilizados do is métodos evolutivos para se o bter a estratégia para
os jogadores, sendo estes eficientes para o propósito de se jogar futebo l. O primeiro método
trata de uma abordagem Mono-Objetivo, onde cada indivíduo será avaliado apenas em
relação a uma função objetivo. Já a abordagem Multi-Objetivo avalia cada indivíduo
em relação a duas funções objetivo. Cada método evolutivo foi aplicado em um time de
futebol de robôs simulados, possibilitando, assim, a comparação dos métodos em relação
à eficiência para se jog ar futebol.
O foco é tentar encontrar o melhor conjunto de ações para os dez jogadores. Cada
jogador possui seu próprio conjunto de ações que será utilizado quando estiver de posse da
bola. Toda estratégia está armazenada dentro de um vetor de números inteiros. Ressalta-
se que o foco não é otimizar um jogador unicamente e sim o time como um todo.
As características do desenvolvimento do time estão descritas na Seção 4.1. A estrutura
de co dificação dos indivíduos está representada na Seção 4.2, sendo que as características
dos AG estão explanadas na Seção 4.3. Os algoritmos dos métodos evolucionários serão
apresentados e descritos na Seção 4.4 e Seção 4.5.
42
4.1 Características do Time Desenvolvido
Nesse trabalho foi utilizado o time UvA Trilearn como base para aplicar os méto do s
evolutivos computacionais. O código fonte do time UvA Trilearn contém apenas a imple-
mentação do comportamento de baixo nível, como por exemplo, as informações trocadas
entre o servidor e os jogadores. O comport amento de alto nível, como a estratégia do
time, foi omitida no código fonte.
O time de futebol de r obôs é composto por dez j ogadores, um goleiro e um técnico.
Os dez jogadores utilizam-se da divisão da área de atuação, para que cada qual possa se
comportar de acordo com a posição estratégica definida durante uma partida. A partida
de futebol de robôs é disputada em um campo virtual retangular por dois times, de onze
jogadores cada, que têm como objetivo colocar a bola dentro do gol adversário, o que é
chamado de gol. Não é permitido o uso do comando para manipular a bola com as mãos,
exceto pelos goleiros.
Figura 4.1: Repre sentação do campo virtual, dos jogadores e da bola .
Os jogadores foram divididos em t r ês diferentes posições, atuando-se assim de maneira
diferente dent r o de campo. O jogador que desemp enha a função de zagueiro atua na área
do campo conhecida como campo de defesa, sendo que tem como principal função marcar
43
os jog adores atacantes do time adversário, evitando-se que estes criem a possibilidade de
gol. O jogador que desempenha a função de meio-campista atua de forma a intermediar
os zagueiros aos atacantes, jogando tanto no campo de defesa quanto no campo de at aque.
O jogador que desempenha a função de atacante atua na área de ataque desempenhando
função of ensiva, com objetivo de fazer gols ou dar assistência para seus companheiros de
time.
O time proposto foi dividido da seguinte for ma: um goleiro, quatro zagueiros, três
meio-campistas e três atacantes. A Figura 4.1 apresenta o campo virtual onde uma
partida de futebol de robôs é exibida, assim como os jogadores e a bola.
Foi então proposta a criação de dez ações, que correspondem à s jogadas previament e
codificadas para serem utilizadas pelos jogadores durante uma partida. As ações serão
realizadas assim que for executada a parte do código da UvA Trilearn, o nde há a condição
de verificação, no qual avalia se o j ogador está ou não de posse da bola (Figura 2.11).
Essas ações são sintetizadas por :
1. Realizar um passe com velocidade média para o companheiro número seis;
2. Realizar um passe com velocidade média para o companheiro número sete;
3. Realizar um passe com velocidade média para o companheiro número oito;
4. Levar a bola para uma área sem opo nentes. Esta ação será usada quando não
conseguir driblar ou realizar o passe para o companheiro;
5. Chutar em direção ao gol adversário;
6. Driblar em direção à linha lateral com um ângulo positivo ;
7. Driblar em direção à linha lateral com um ângulo negativo;
8. Realizar um passe com velocidade alta para o companheiro número nove;
9. Realizar um passe com velocidade alta para o companheiro número dez;
10. R ealizar um passe com velocidade alta pa r a o companheiro número onze.
44
As jogadas irão compor a estrutura de um jogador, sendo inseridas dentro de cada
posição de um vetor de inteiros, o qual representa a estrutura cromossômica de um jogador
(Seção 4.2).
4.2 Codificação dos Indivíduos
Para a codificação dos indivíduos (j ogadores), foi necessário a criação de um vetor de
inteiros. Cada jogador é representado por um vetor de inteiros de dez po sições. Em cada
posição deste vetor será inserida uma das dez possíveis ações propostas (Seção 4.1), as
quais são inseridas aleatoriamente de acordo com a geração dos jogadores no AG.
Assim que o AG é iniciado, tanto no AG mono-objetivo, como no AG multi-objetivo,
são gerados dez jogadores. Em cada uma das dez posições do vetor de inteiros de um
jogador é inserido o valor aleatório no intervalo de [1,10], de acordo com as dez possíveis
ações descritas na Seção 4.1. Um time formado por dez jogadores
1
contém então dez
vetores de inteiros de dez posições cada.
A Figura 4.2 represent a os jogadores gerados e suas respectivas ações. Cada jogador
possui um conjunto de ações de 1 a 10. Gera-se então de 1 a 10 jogadores para cada
geração.
Figura 4.2: Repre sentação dos jogadores.
1
O goleiro foi excluído, pois apresenta características de ações diferente dos outros jogador es, como a
ação de manuseiar a bola com as mãos.
45
4.3 Características do AG
O algoritmo genético foi aplicado somente nos dez jogadores, sendo que o goleiro foi
excluído. Considerando o total de ações por joga dor , utilizaram-se então os dez vetores
de inteiros para representar o time.
O a lg oritmo genético foi configurado com as seguintes características:
• Processo de avaliação exclusivo pa r a cada método evolutivo: na abor dagem Mono-
Objetivo foi utilizada apenas uma função objetivo, sendo que na abordagem Multi-
Objetivo foram utilizadas duas funções objetivo;
• Cruzamento usando apenas um ponto em 60% dos indivíduos;
• Mutação em apenas 1% dos indivíduos;
• Método de seleção do tipo elitista utilizado na abordagem Mono-Objetivo, e o mé-
todo baseado na dominância de Pareto utilizado na abordag em Multi-Obj etivo.
Na operação de cruzamento foi selecionada 60% da população pelo método do elitismo,
respeitando-se os indivíduos com melhores valor es da função de avaliação, para ambos os
métodos evolutivos. Tal método elenca os indivíduos de acordo com o valor da função
de avaliação, do maior valor par a o menor valor desta função, mant endo-se os indivíduos
mais aptos na população.
Depois de se selecionar 60% do indivíduos, escolhe-se aleatoriamente um ponto de
secção para realizar a operação de cruzamento , em que serão trocados as duas metades
dos dois vetores selecionados anteriormente. Dois indivíduos (pais) geram, a partir do
método de cruzamento, dois novos indivíduos (filhos).
Para a operação de mutação, um indivíduo é escolhido aleatoriamente. Em seguida,
escolhe-se um ponto dentro do seu vetor de inteiros para realizar a mutação, obedecendo-se
os seguint es critérios:
• Se o indivíduo for um zagueiro, priorizar então as ações 1, 2, 3, 4, 5, 6 e 7;
• Se o indivíduo for do tipo meio-campo, priorizar entã o as ações 4, 5, 6, 7, 8, 9 e 10;
46
• Se o indivíduo f or um atacante, priorizar então as ações 4, 5, 6 e 7.
O sistema desenvolvido funciona de acordo com a Figura 4.3. Primeiramente, geram-
se de maneira aleatória dez indivíduos (joga dor es), os quais são escritos dentro de um
arquivo texto (indiv.txt). O módulo Gera Indivíduos é executado apenas uma vez na
primeira geração, sendo que nas gerações subsequentes os indivíduos serão gerados a partir
das o perações genéticas realizadas pelo módulo Algoritmo Genético. Os dez indivíduos
gerados apresentam a estrutura representada pela Figura 4.2. Para a primeira geração,
não é realizada nenhuma operação genética, pois os indivíduos são lidos do arquivo texto
(indiv.txt) pelo módulo Time e os colocam para disputar uma partida no simulador de
futebol.
Figura 4.3: Fluxo de dados dentro do sistema desenvolvido.
Logo após o término da partida, o simulador retorna o placar do jogo, sendo que o
mesmo é escrito pelo módulo Time no arquivo t exto (placar.txt). Em seguida, o módulo
Algoritmo Genético lê o placar desse arquivo e inicia os operadores genéticos que irão
avaliar, cruzar e mutar os indivíduos. O módulo Algoritmo Genético é composto por
três diferentes AGs, cada um responsável p elo conjunto de jog adores de acordo com suas
respectivas áreas de atuações. O que diferencia um AG de outro é a função objetivo e o
operador genético de mutação . Em seguida, os indivíduos são escritos dentro do arquivo
47
texto (indiv.txt), em que o processo se reinicia até que o número de gerações seja ig ua l
ao valor definido.
O módulo AG, quando utilizado na abordagem Mono-Objetivo, faz uso de funçõ es
objetivo descritas pelas Equações (4.1), (4.2) e (4.3), conforme apresentadas na Seção 4.4.
Na abordagem Multi-Objetivo, utiliza-se as funções objetivo dadas pelas Equações (4.4),
(4.5) e (4.6), descritas na Seção 4.5.
4.4 Abordagem Mono-Objetivo
Para o algoritmo Mono-Objetivo foi proposto o método de avaliação baseado na quan-
tidade de gols prós (GP) e gols contra (GC), em relação à área de atuação do jog ador
em campo (zagueiro, meio-campo ou ata cante). O jogador zagueiro recebe os valores
de recompensa (GP
ZG
) e de punição (GC
ZG
), o jogador meio-campo recebe os valores
de recompensa (GP
MC
) e de punição (GC
MC
) e o jogador atacante recebe os valores de
recomp ensa (GP
AT
) e de punição (GC
AT
).
Os valores de recompensa e punição, para cada tipo de jogado r, foram pré-estipulados
para auxiliar no cálculo da função objetivo. Foi proposto o cálculo da função objetivo
para os jogadores zagueiros, meios-campos e atacantes da seguinte maneira:
• Para o jogador zagueiro, utiliza-se a função F IT
ZG
:
F IT
ZG
= ((GP
ZG
∗ GP ) + (GC
ZG
∗ GC)) (4.1)
• Para o jogador meio-campo, utiliza-se a função F IT
MC
:
F IT
MC
= ((GP
MC
∗ GP ) + (GC
MC
∗ GC)) (4.2)
• Para o jogador ata cante, utiliza-se a função F IT
AT
:
F IT
AT
= ((GP
AT
∗ GP ) + (GC
AT
∗ GC)) (4.3)
48
O método de avaliação prioriza a quantidade de gols prós em relação à quantidade de
gols contra. Quando a partida é finalizada, dois valores são entã o retornados para a função
de avaliação, isto é, a quantidade de gols prós e a quantidade de gols contra. A função de
avaliação receb e o placar da partida e pontua cada indivíduo de acordo com sua posição
tática. Em seguida, realiza-se o cruzamento e a mutação dos indivíduos selecionados de
acordo com suas respectivas pontua ções.
Figura 4.4: Fluxograma do algoritmo genético mono-objetivo.
A Figura 4.4 apresenta o fluxograma do algoritmo genético proposto. Primeiramente,
dez indivíduos são gerados a leato r ia mente. Então, esse time gerado é colocado para
disputar uma partida de futebol contra os times que estarão descritos na Seção 4.6. Após
o término da partida, o referido time é avaliado de acordo com o placar resultante.
4.5 Abordagem Multi-Objetivo
Para o AGMO fo i proposto o método de avaliação baseado também na quantidade de
gols prós (GP) e go ls contra (GC), em relação à área de atuação do jogador em campo
49
(zagueiro, meio-campo ou atacante). A diferença em relação ao método Mono-Objetivo se
dá principalment e pelo fato de serem utilizadas duas funções objetivo, uma para avaliar
a quantidade de gols prós (GP) e outra para avaliar a quantida de de gols contra (GC),
de forma distinta.
O método pro posto tem como objetivo principal aument ar a quantidade de GP ao
mesmo tempo que diminui a quantidade de GC.
Como no método Mono-Objetivo, o jogador zagueiro recebe os valores de recompensa
(GP
ZG
) e de punição (GC
ZG
), o jogador meio-campo recebe os valores de recompensa
(GP
MC
) e de punição (GC
MC
) e o jogador atacante recebe os valores de recompensa
(GP
AT
) e de punição ( GC
AT
).
Para auxiliar o cálculo das funções objetivo, foram pro postos valor es de recompensa
e punição, para cada tipo de jogador (zagueiros, meios-campos e atacantes) , da seguinte
maneira:
• Para o jogador zagueiro, utilizam-se duas funções objetivo. A F IT
ZG
GP
avalia os
gols prós e a F IT
ZG
GC
avalia os go ls contra :
F IT
ZG
GP
= (GP
ZG
∗ GP )
F IT
ZG
GC
= (GC
ZG
∗ GC) (4.4)
• Para o jogador meio-campo, utilizam-se duas funções objetivo. A F IT
MC
GP
avalia
os gols prós e a F IT
MC
GC
avalia os gols contra:
F IT
MC
GP
= (GP
MC
∗ GP )
F IT
MC
GC
= (GC
MC
∗ GC) (4.5)
• Para o jogador atacante, utilizam-se duas funções objetivo. A F IT
AT
GP
avalia os
gols prós e a F IT
AT
GC
avalia os go ls contra:
F IT
AT
GP
= (GP
AT
∗ GP )
F IT
AT
GC
= (GC
AT
∗ GC) (4.6)
50
O método de avaliação prioriza a quantidade de gols prós em relação à quantidade
de gols contra. Quando a partida é finalizada, dois valores são então retornados para a
função de avaliação, isto é, a quantidade de gols prós e a quantidade de gols contra. A
função de avaliação recebe o placar da partida e pontua cada indivíduo de acordo com sua
posição tática. Cada tipo de jogador terá dois valores atribuídos pela função objetivo, um
valor para gols prós (F IT
GP
) e outro com o valor de gols contra (F IT
GC
). Em seguida,
ocorre a repro dução do tipo elitista, na qual se seleciona os indivíduos para a próxima
geração de acordo com o modelo esquemático do algoritmo NSGA-II ( Figura 3.3). Por
último, realiza-se o cruzamento e a mutação dos indivíduos selecionados de acordo com
suas respectivas po ntuações.
Figura 4.5: Fluxograma do algoritmo genético multi-objetivo.
A Figura 4.5 apresenta o fluxograma do algoritmo genético proposto. Primeiramente,
dez indivíduos são gerados a leato r ia mente. Então, esse time gerado é colocado para
disputar uma partida de futebol contra os times que estarão descritos na próxima seção.
51
Após o término da partida, o referido time é avaliado de acordo com o placar resultante.
4.6 Resultados Obtidos
Nesta seção são apresentados os resultados obtidos, no domínio do futebol de robôs
simulados, utilizando ambas abordagens evolutivas. Foram realizados 30 experimentos,
utilizando a abordag em mono-objetivo e a abordagem multi-objetivo. Para avaliar a
eficiência para ambas abordagens genéticas, foram escolhidos os três melhores times que
participaram das competições mundiais da RoboCup de 2007 à 2009, são eles:
• B RAINST ORMERS - Esse time foi desenvolvido por Martin Reidmiller em con-
junto com Thomas Gabel, no Instituto de Ciência Cognitiva , pertencente a Univer-
sidade de Osnabruek, Alemanha. O time utiliza técnicas conhecidas de aprendizado
de máquina, particularmente o método de a prendizado por reforço. Foram cam-
peões da categoria simulação 2D da RoboCup em 2007 e 2008, respectivamente
realizadas em Atlanta, Estados Unidos da América e Suzhou, China. Durante a
última RoboCup 2009, realizada em Graz na Áustria, obtiveram a quarta colocação
(Gabel e Riedmiller, 2009).
• WRIGHTEAGLE - O time foi desenvolvido por Ke Shi, Aijun Bai, Yunfang Ta i e
Xiaoping Chen, no Laborat ório de Sistemas Multi-Agentes, na Escola de Ciência da
Computação e Tecnologia da Universidade de Ciência da Computação, China. Esse
time tem como objetivo, a longo prazo, realizar uma pesquisa utilizando planeja-
mento de decisão teórica e outros projetos em inteligência artificial. Desenvolveram
uma estrutura nova do time, baseado na teoria da observação par cial estocástica de
um jogo, como também desenvolveram novas técnicas de baixo e alto nível. Obtive-
ram na RoboCup, em 2007 e 2008, o segundo lugar na categoria simulação 2D. Na
RoboC up em 20 09 foram campeões (Shi et al., 2 009).
• HELIOS - Esse time foi desenvolvido por Hidehisa Akiyama, Hiroki Shimora e
Itsuki Noda, na Universidade de Tokyo, Japão. Utilizam técnicas que aplicam o
conhecimento humano dentro da tomada de decisões de um agente. Dentre essas
52
técnicas, destacam-se o mecanismo de posicionamento que utiliza a triangularização
Delaunay. Durante a RoboCup, em 2007 e 2008, obtiveram o terceiro lugar e foram
vice-campeões na RoboCup em 2009 na categor ia simulação 2D (Akiyama et al.,
2009).
Em ambas abordagens evolutivas utilizou-se pesos no processo de avaliação para auxi-
liar a convergência dos AG’s. Não foi encontrado na literatura nenhum estudo relacionado
a escolha dos pesos a t ribuídos aos valores prós e valor es contra da função de avaliação,
portanto, foram testados diversos valores até se chegar em uma pontuação que fosse efi-
ciente, auxiliando-se assim, no processo de convergência do algoritmo. Foram atribuídos
os pesos da seguinte maneira:
• Pa r a a função de avaliação dos zagueiros, foram atribuídos os valores de:
GP
ZG
= 60;
GC
ZG
= −55; (4.7)
• Pa r a a função de avaliação do meio-campo, foram atribuídos os valor es de:
GP
MC
= 80;
GC
MC
= −60; (4.8)
• Pa r a a função de avaliação dos a tacantes, foram atribuídos os valores de:
GP
AT
= 100;
GC
AT
= −70. (4.9)
O problema mais crítico foi em relação ao tempo total de duração das simulações,
pois cada partida tem duração de aproximadamente dez minutos (Seção 2.2). Seria en-
tão inviável realizar trinta testes, simulando as duas mil partidas. A Tabela 4.1 ilustra
detalhadamente o problema em questão.
53
Ta bela 4.1: Tempo total da simulação, sem configurar o servidor.
Tempo da Partida Quant. de Testes Quant. de Gerações Tempo Total
Mono-Objetivo 10 min 30 2000 417 dias
Multi-Objetivo 10 min 30 100 21 dias
O servidor apresenta diversos recursos, os quais podem ser habilitados ou não. Para
solucionar o problema do tempo elevado de simulação, foi habilitado o recurso de acelerar
o tempo de execução de uma partida, fazendo com que pudesse ser concluída em no
máximo um minuto. O tempo resultante após a configuração do servidor está presente
na Tabela 4.2.
Ta bela 4.2: Tempo total da simulação, com o servidor configurado.
Tempo da Partida Quant. de Testes Quant. de Gerações Tempo Total
Mono-Objetivo 1 min 30 2000 41 dias
Multi-Objetivo 1 min 30 100 2 dias
4.6.1 Resultado do Algoritmo Genético Mono-Objetivo
Neste experimento foram feitos trinta testes com o time que possui a abordagem
genética mono-objetivo. Cada exp erimento corresponde a duas mil partidas contra cada
um dos times escolhidos, totalizando cento e oitenta mil partidas.
A Figura 4.6 ilustra a média das curvas de evolução realizada por duas mil partidas
contra o time BRAINSTORMERS. No t a-se que, por volta da quadringentésima geração,
a quantidade de gols prós começa a aumentar, atingindo o valor máximo de dezessete
gols por volta da milésima geração. Nota-se também que a quantidade de gols sofridos
permanece praticamente zerada.
54
Figura 4.6: Resultado de duas mil gerações, AG Mo no-Objetivo contra BRAINSTORMERS.
A Figura 4.7 ilustra a média das curvas de evolução realizada por duas mil partidas
contra o time WRIGHTEAGLE. Nota-se que por vo lta da t ricengentésima geração a
quantidade de gols contra começa a diminuir, atingindo o valo r máximo de dezessete gols,
por volta da geração mil e seiscentos. Nota -se também que a quantidade de gols prós
mantêm-se praticamente zerada.
Figura 4.7: Resultado de duas mil gerações, AG Mono-Objetivo contra WRIGHTEAGLE.
55
A Figura 4.8 ilustra a média das curvas de evolução realizada por duas mil partidas
contra o time HELIOS. Nota -se que por volta da ducentésima geração a quantidade de gols
contra começa a diminuir, atingindo o valor máximo de doze gols por volta da geração mil
e cem. Nota-se neste caso que a quantidade de gols prós apresenta significativa melhora
após a quadringentésima geração, atingindo o valor máximo d e um gol.
Figura 4.8: Resultado de duas mil gerações, AG Mono-Objetivo contra HELIOS.
Na Tabela 4.3 ilustra-se de maneira geral os resultados obtidos aplicando a abordagem
genética mono-objetivo cont r a os respectivos adversários, descritos acima.
Ta bela 4.3: Média dos resultados obtidos da abordagem genética mono-objetivo.
BRAINSTORMERS WRIGHTEAGLE HELIOS NÚMERO DE GERAÇÕES
Mono-Objetivo 5 X 0 0 X 21 0 X 29 1
Mono-Objetivo 17 X 0 0 X 17 1 X 12 2000
4.6.2 Resultado do Algoritmo Genético Multi-Objetivo
Neste experimento foram feitos trinta testes com o time que possui a abordagem
genética multi-objetivo. Cada exp erimento corresponde a cem partidas contra cada um
56
dos times escolhidos, totalizando nove mil partidas.
A Figura 4.9 ilustra a média das curvas de evolução realizada por cem partidas contra
o time BRAINSTORMERS. Nota-se que desde as primeiras gerações a quantidade de
gols prós começa a aumentar, atingindo o valor máximo de dezenove gols, por volta
da octogésima geração. Nota-se também que a quantidade de gols sofridos permanece
praticamente zerada.
Figura 4.9: Resultado de cem gerações, AG Multi-Objetivo contra BRAINSTORMERS.
A Figura 4.10 ilustra a média das curvas de evolução realizada por cem partidas contra
o time WRIGHTEAGLE. Nota-se que desde as primeiras gerações a quantidade de gols
contra começa a diminuir, atingindo o valor máximo de cinco gols, por volta da octogésima
geração. Not a-se neste caso que a quantidade de gols prós apr esenta significativa melhora
após a décima quinta geração, atingindo o valor máximo de um gol.
57
Figura 4.10: Resultado de cem gera ç ões, AG Multi-Objetivo contra WRIGHTEAGLE.
A Figura 4.11 ilustra a média da s curvas de evolução realizada por cem par t idas
contra o time HELIOS. Nota-se que desde as primeiras gerações a quantidade de gols
contra começa a diminuir, atinge o valor máximo de do is gols, por vo lta da septuagésima
geração. Nota-se neste caso que a quantidade de gols prós, após a trigésima geração,
atingindo o valor máximo de três gols. Sendo este o caso mais interessante em relação aos
resultados obtidos durante os experimentos.
Figura 4.11: Resultado de cem ge rações, AG Multi-Objetivo contra HELIOS.
58
Na Tabela 4.4 ilustra-se de maneira geral os resultados obtidos aplicando a abordagem
genética multi-objetivo contra os respectivo s adversários, descritos acima.
Ta bela 4.4: Média dos resultados obtidos da abordagem genética multi-objetivo.
BRAINSTORMERS WRIGHTEAGLE HELIOS NÚMERO DE GERAÇÕ ES
Multi-Objetivo 6 X 0 0 X 10 0 X 7 1
Multi-Objetivo 19 X 0 1 X 5 3 X 2 100
4.7 Considerações Parciais
Neste capítulo foram abordados as características do time (Seção 4.1), o modelo de
codificação dos indivíduos (Seção 4.2) e as características do AG (Seção 4.3). Também
foram apresentado s as a bordagens Mono-Objetivo e Multi-Objetivo , explicitando cada
uma delas nas respectivas Seções 4.4 e 4.5 em conjunto com seus respectivos resultados
apresentados nas Subseções 4.6.1 e 4.6.2.
59
Capítulo 5
Conclusões Gerais
Neste tra balho foi realizado uma análise comparativa dos AGs aplicados no domínio
do futebol de robôs. O primeiro é o AG mono-objetivo e o segundo é o AG multi-objetivo.
No AG multi-objetivo foi utilizado o algoritmo NSGA-II para selecionar os indivíduos
por meio do conceito de dominância de Pareto.
Em Fraccaroli e Silva (2009b) foi aplicado um algoritmo genético para definir ações
no domínio do futebol de robôs. Entretanto, não foi utilizado o método de atribuição de
pesos, e com isso notou-se a convergência tardia do AG. O método de atribuição de pesos
no processo de avaliação fo i proposto para auxiliar o tempo convergência dos AG’s.
Foram realizados testes e foi utilizado o método de atribuição de pesos para acelerar
a convergência dos AG ’s. Adotando-se este, foram necessários aproximadamente mil ge-
rações para a convergência do AG mono-objetivo e oitenta gerações para a convergência
do AG multi-objetivo.
Foi provado que o AG multi-objetivo, por utilizar-se de mais de um o bjetivo, percorre
melhor o espaço de busca, auxiliando no tempo de convergência; porém, dependerá do
tipo de modelagem realizado para o determinado time.
Uma outra contribuição importa nte do trabalho foi o desenvolvimento de uma estraté-
gia baseada em AG aplicado a um time de futebol de ro bôs simulados, contituído de onze
robôs simulados, o qual p oderá ser utilizado em competições nacionais e internacionais
de futebol de robôs simulados. Este ambiente fornece um ambiente muito rico de temas
60
de pesquisas a serem investigadas.
Os dois times implementados, um com AG mono-objetivo, outro com AG multi-
objetivo foram criados utilizando o time base UvA Trilea rn . A partir desses times criados,
é possível que outros pesquisadores que desejam trabalhar com AE’s aplicados no ambi-
ente de futebol de robôs simulados possam utilizar seus métodos sem ter que implementar
um time inteiro.
O desenvolvimento deste traba lho possibilitou a publicação de dois artigos durante o
ano de 2009, (Fraccaroli e Silva, 2 009a) e (Fraccaroli e Silva , 2009b). Também foi possível
a conquista do campeonato de futebol de robôs simulados, realizado em Brasília, durante
o Simpósio Brasileiro de Automação Inteligente, SBAI, em novembro de 2009.
Como direções futuras deste trabalho é interessante r ealizar experimento s com a uti-
lização de outra modelagem, aplicando-se diversas outras possíveis ações. Outro ponto a
ser investigado seria a aplicação de um sistema Fuzzy para definir a formação tática, a
partir de diversas variáveis de entrada, tais como: po sição da bola; tempo decorrido da
partida; tempo de posse de bola e placar. Finalmente, seria ainda interessante realizar
experimentos com um AG adaptativo, possibilitando que ajustes automáticos nas ações
dos times sejam realizados no decorrer de uma partida.
61
Referências Bibliográficas
Aarts, E. e J. Korst (1989). Simulated Annealing and Boltzmann Machines: A Stochastic
Approach to Combinatorial Optimization and Neural Computing. John Wiley and Sons.
Akiyama, H., H. Shimora, e I. Noda (2009). Oficial site of helios, team description pa-
per. In Disponível em http://romeo.ist.tugraz.at/robocup2009/tdps/hel i os-rc 09-tdp.pdf.
Visited in 12/0 8/2009.
Boer, R. e J. Kok (2002). The incremental development of a synthetic multi-ag ent sys-
tem: The uva trilearn 2001 robotic soccer simulation team. Dissertação de Mestrado,
University of Amsterdam.
Chen, M., E. Foroughi, F. Heintz, Z. Huang, S. Kapetanakis, K. Kostiadis, J. Kummeneje,
I. Noda, O. Obst, P. Riley, T. Steffens, Y. Wang, e X. Yin (2002). RoboCup Soccer
Server. Disponível em http://sourceforge.net/projects/sserver.
Cheung, W., A. Kentish, e A. Law (2005). Sabotage fc: Implementing a simulated robot
football team using evolutionary algorithms. In CO600 Group Project Reports 2 004/05.
Coello, C. e G. Pulido (2001). Multiobjective optimization using a micro- genetic al-
gorithm. In Proceedings of the Genetic and Evolutionary Comp utation C onf erence
(GECCO 2001). Morgan Kaufmann Publishers.
Coello, C. A. C., D. A. V. Veldhuizen, e G. B. Lamont (2002). Evolutionary Algorithms
for Solving Multi-Objective Problems. Kluwer Academic/Plenum Publishers.
Corne, D., N. Jerram, J. Knowles, e M. Oates (2001). Pesa-ii: Region- ba sed selection in
evolutionary multiobjective optimization. In L. Spector, E. Goodman, A. Wu, W. Lang-
don, H. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. Garzon, e E. Burke (Eds.),
62
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2001),
pp. 283–290. Morgan Kaufmann Publishers.
Darwin, C. (1859). On the Origin of Specie s By Means of Natural Selection.
Deb, K . (2001). Multi-Objective Optimization using Evolutionary Algorithms. John Wiley
and Sons.
Deb, K., S. Agrawal, A. Pratab, e T. Meyarivan (2000). A fast elitist non-do minated
sorting genetic algorithm for multi-objective optimization: Nsga-ii. KanGAL report
200001, Indian Institute of Technology, Kanpur, India.
Fonseca, C. e P. Fleming (1993). Genetic algorithms for multiobjective optimization:
Formulation, discussion and generalization. In S. Forrest (Ed.), Proceedings of the Fifth
International Conference on Genetic Algorithms, San Mateo, California, pp. 416–423.
University of Illinois at Urbana-Champaign.
Fraccaroli, E. S. e I. N. Silva (2009a). Abo r da gem fuzzy para determinação de estratégia
em ambiente de futebol de robôs simulado. In Brazilian Conference on Dynamics,
Contro l and Applications, Volume 8, pp. 1–6.
Fraccaroli, E. S. e I. N. Silva (2009b). Abordagem genética para definição de ações em am-
biente simulado de futebol de robôs. In Simpósio Brasileiro de Automação Inteligente.
CD-ROM // paper number: 55708 // 0 6 páginas.
Francis, K. A. (2007). Charles Darwi n and The origin of s pecie s. Greenwood Press.
Gabel, T. e M. Riedmiller (2009). Oficial site of bra instormers, team description paper. In
Disponível em http://rom eo.ist.tugraz.at/robocup2009/tdps/brains torm ers-rc0 9-tdp.pdf.
Visited in 12/08/20 09.
Gao, Y., L. Shi, e P. Yao (2000). Study on multi-objective genetic algorithm. In Intelligent
Contro l and Automation, Volume 1, pp. 646–650.
Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Lear-
ning. Reading, MA: Addison-Wesley Publishing Company, Inc.
63
Hajela, P. e C. Y. Lin (1992). Genetic search strategies in multicriterion optimal design.
Structural and Multidisciplinary Optimization 4, 99–107 .
Hiroyasu, T., M. Miki, e S. Watanabe (2000). The new model of parallel genetic algo-
rithm in multi-obj ective optimization problems - divided range multi-objective genetic
algorithm. In Evolutionary Computation, Volume 1, pp. 333–340.
Holland, J. H. (1992). Adaptation in Natural and Artificial Systems. The University of
Michigan Press.
Horn, J., N. Nafpliotis, e D. Goldberg ( 1994). A niched pareto genetic algo rithm for
multiobjective optimization. In Proceedings of the First IEEE Conference on Evoluti-
onary Computation, IEEE World Congress on Computational Intelligence, Volume 1,
pp. 82–87. IEEE Service Center.
Jeong, I. K. e J. J. Lee (1997). Evolving multi-a gents using a self-organization a lg orithm.
Volume 88, pp. 293–303. Applied Mathematics and Computing.
Kitano, H., M. Asada, Y. Kuniyoshi, I. Noda, e E. Osawa (1995). Robocup: The robo t
world cup initiative. In IJCAI-95 Work shop on Entertainment and AI/Alife, Volume 1,
pp. 532.
Kitano, H., M. Asada, Y. Kuniyoshi, I. Noda, e E. Osawa (1998). Robocup: A challenge
problem for ai and robotics. In Lecture Notes in Computer Science, Volume 1395, pp.
73–85.
Knowles, J. e D. Corne (1999). The pareto archived evolution strategy: A new baseline
algorithm for multiobjective optimisation. In 1999 Congress on Evolutionary Compu-
tation, pp. 98–105. IEEE Service Center.
Lee, S. W. e H. T. Tsui (2004). A relational multi-objective genetic alg orithm. In Neural
Networks, Volume 1.
Michalewicz, Z . (1996). Genetic algorithms + Data Structures = Evolution Programs.
Springer-Verlag New York, Inc.
64
Nakashima, T., M. Taka tani, M. Udo, e H. Ishibuchi (2004). An evolutionary apparoach
for strategy learning in robocup soccer. In International Conference on Systems, Man
and Cybernetics, Volume 2, pp. 2023–20 28.
Plant, W. R. e G. Schaefer (2008). An overview of genetic algorithms in simulation soccer.
In IEEE Congress on Evolutionary Computation (CEC 2008), pp. 3897 – 3904.
Raadt, M., M. Prokopenko, e M. Butler (2003). Evolving tactical formations on the robo-
cup field. In Workshop on Adaptability in Multi-Agent Systems at The First RoboCup
Australian Open 2003.
Reis, L. P. (2003). Coo rden ação e m Sistemas Multi-Age nte: Aplicações na Gestão Univer-
sitária e Futebol Robótico. Tese de Doutorado, Faculdade de Engenharia da Univeridade
do Porto.
Rezende, S. O. (2003). Sistemas Inteligentes: Fundamentos e Aplicações. Manole.
RoboCup (2009). Oficial Site of RoboC up World Championship. In
http://www.robocup.org. Visited in 12/01/2009.
Ross, T. J. (2004). Fuzzy Logic with Engineering Applications. John Wiley.
Schaffer, J. D. (1984). Some Experiments in Machin e Learning using Vector Evaluated
Genetic Algorithms. Tese de Doutorado, TN: Vanderbilt University.
Shi, K., A. Bai, Y. Tai, e X. Chen (2009). Oficial site of wrighteagle, team
description paper. In Disponíve l em http://ai.ustc.edu.cn/en/robocup/2D/tdp/
WrightEagle20092DSoccerSimulationT eamDescriptionP aper.pdf.V isitedin12/08/2009.
Srinivas, N. e K. Deb (1994). Multiobjective optimization using nondominated sorting in
genetic algorithms. Evolutionary Computation 2, 221–248.
UvA Trilearn (2003). Oficial site of uva trilearn 2003 - soccer si mulation team. In
http://staff.science.uva.nl/ jellekok/robocup/2003/trilearnrc2003bin.tar.gz.V isitedin20/05/2008.
Veldhuizen, D. (1999). Multiobjective Evolutionary Algorithms : Classifications, Ana l yses,
and New Innovations. Tese de Doutorado, Department of Electrical and Computer
Engineering. Graduate School of Engineering. Air Force Institute of Technology.
65
Weiss, G. (1999). Multiagent Systems: A Modern Approach to Distributed Artificial In-
telligence. The University of Michigan Press.
Zhang, P., B. Zhao, Y. Cao, e S. Cheng (200 4). A novel multi-objective genetic algorithm
for economic power dispatch. In Universities Power Engineeri ng Confe rence, Volume 1,
pp. 422–426.
Zitzler, E. (1999). Evolutionary Algorithms for Multiobjective O ptimization: Methods and
Applications. Tese de Doutorado, Swiss Federal Institute of Technology Zurich.
Zitzler, E., M. Laumanns, e L. Thiele (2001). Spea2: Improving the strength pareto
evolutionary algorithm. Technical Report No. 103, Computer Engineering and Networks
Laboratory (TIK), Swiss Federal Institute of Technology (ETH) Zurich.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
