Modelagem de uma Arquitetura Multiagente para a Solução, via

Transcrição

CENTRO FEDERAL DE EDUCAÇÃO
TECNOLÓGICA DE MINAS GERAIS
Diretoria de Pesquisa e Pós-Graduação
Curso de Mestrado em Modelagem
Matemática e Computacional
Modelagem de uma Arquitetura
Multiagente para a Solução, via
Metaheurísticas, de Problemas
de Otimização Combinatória
Dissertação de Mestrado, submetida ao Curso de
Mestrado em Modelagem Matemática e Computacional, como parte dos requisitos para a obtenção
do título de Mestre em Modelagem Matemática e
Computacional.
Aluna: Maria Amélia Lopes Silva
Orientador: Prof. Dr. Sérgio Ricardo de Souza (CEFET/MG)
Co-orientador: Prof. Dr. Henrique Elias Borges (CEFET/MG)
Belo Horizonte, outubro de 2007.
S586m SILVA, Maria Amélia Lopes
2007
Modelagem de uma Arquitetura Multiagente
para a Solução, via Metaheurísticas, de Problemas
de Otimização Combinatória.
Belo Horizonte: CEFET-MG, 2007.
114p.
Dissertação (Mestrado) Centro Federal de Educação
Tecnológica de Minas Gerais
CEFET/MG.
1. Computação. 2. Otimização combinatória.
3. MetaHeurística. 4. Pesquisa Operacional.
I. Título.
CDD: 004.0151
Às pessoas que são meus maiores exemplos de vida, meu pai e minha mãe,
José Ivo e Nina.
ii
Agradecimentos
Ao concluir este trabalho tenho a certeza de que é importante agradecer. Agradecer muito a todos que ajudaram e foram pacientes nos momentos difíceis e cansativos.
Agradeço a Deus, por todas as oportunidades maravilhosas que coloca na minha
vida.
Ao meu orientador, Prof. Sérgio Ricardo de Souza, por ser mestre e amigo,
obrigado pelo conhecimento transmitido e pelo incentivo constante.
Ao meu co-orientador, Prof. Henrique Elias Borges, pela contribuição fundamental para o desenvolvimento do trabalho.
Leonardo, obrigado pelo carinho, amizade, paciência e compreensão que nunca
faltaram nos momentos de aflição.
Agradeço aos meus queridos pais, pelo incentivo incondicional e por acreditarem
que sou capaz de coisas que até mesmo eu não sei.
Ao meu irmão e minhas maninhas, deixo a certeza de que valeu a tolerância nos
momentos de minha impaciência e tensão. Foi porque sempre estivemos juntos que
venci mais esta etapa. Amo vocês!
À Sabrina, obrigado pelo suporte, amizade e sugestões para a realização do
trabalho.
Ao meu cunhadinho Gabriel, pelas idéias brilhantes que permitiram que grandes
pepinos fossem resolvidos.
Aos colegas de mestrado, que na verdade, hoje, são grandes amigos, agradeço
pelo apoio, amizade e auxílio prestado.
Agradeço à CAPES pelo apoio financeiro individual recebido.
A todos vocês, meus sinceros agradecimentos.
iii
iv
Resumo
Este trabalho apresenta a Arquitetura Multiagente para Metaheurística, nomeada
como AMAM. Esta arquitetura tem, como objetivo, combinar diversas metaheurísticas para a solução de problemas de otimização combinatória. Desta forma, na
arquitetura proposta, cada metaheurística é projetada como um agente autônomo
e interage em seu ambiente (espaço de busca do problema) de forma cooperativa.
A interação de um ou mais agentes se dá através da troca de mensagens sobre o
espaço de busca do problema, para melhor atingir um mesmo objetivo, podendo
ser realizada a partir do envio e percepção de estímulos e por meio do ambiente. A
AMAM é flexível o bastante para ser utilizada na solução de problemas de otimização
combinatória de qualquer classe, sem que seja necessário reescrever os algoritmos,
considerando que a simples troca do ambiente da arquitetura corresponde à troca
de problema a ser tratado. Nesta arquitetura, novos agentes que implementam e
encapsulam metaheurísticas específicas podem ser adicionados com o mínimo de
impacto no restante da arquitetura. Desta forma, especializações da arquitetura foram desenvolvidas e testadas para solução do Problema de Roteamento de Veículos
com Janela de Tempo. Os resultados obtidos nestes testes mostram a viabilidade
da proposta apresentada, assim como confirmam a presença de características como
flexibilidade, escalabilidade e encapsulamento.
Palavras-Chave: Metaheurísticas, Sistemas Multiagente, Problemas de Otimização Combinatória.
v
Abstract
This work introduces a Multiagent Architecture for Metaheuristic, denominated as
AMAM. This architecture has as objective to combine several mataheuristics in order to obtain solutions for combinatorial optimization problems. Therefore, in the
proposed architecture, each metaheuristic is projected as an autonomous agent and
interacts at its environment (search space of the problem) in a cooperative way. The
interaction between one or more agents is done through the interchange of messages from the search space of the problem, and seeks to the best way for achieving
the same objective, able to be accomplished from the emission and perception of
stimulous by the environment. The AMAM is flexible enough to be used in solutions for several class of combinatorial optimization problems, without the necessity
of rewriting algorithms, considering that a simple change of the architecture environment corresponds to a problem change to be treat. At this architecture, new
agents implement and encapsulate specific metaheuristics which can be added with
the lowest possible impact in the remaining architecture. Thus, the architecture
specializations were developed and tested for solutions of Vehicle Routing Problems
with Time Windows. The obtained results show the viability of the proposal presented, and confirm the presence of characteristics such as flexibility, scalability and
encapsulability.
Keywords: Metaheuristic, Multiagent Systems, Combinatorial Optimization Problems.
vi
Sumário
1 Introdução
1.1 Aspectos Gerais . . . . . . .
1.2 Objetivos . . . . . . . . . .
1.2.1 Objetivo Geral . . .
1.2.2 Objetivos Específicos
1.3 Metodologia de Pesquisa . .
1.4 Estrutura da Dissertação . .
.
.
.
.
.
.
.
.
.
.
.
.
2 Sistemas Multiagentes
2.1 Introdução . . . . . . . . . . . .
2.2 Definições . . . . . . . . . . . .
2.2.1 Agentes . . . . . . . . .
2.2.2 Sistemas Multiagentes .
2.2.3 Agentes e Objetos . . .
2.3 Interações . . . . . . . . . . . .
2.4 Ambiente . . . . . . . . . . . .
2.5 Arquiteturas de Agentes . . . .
2.5.1 Arquitetura Deliberativa
2.5.2 Arquitetura Reativa . .
2.5.3 Arquitetura Híbrida . .
2.6 Considerações Finais . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3 Metaheurísticas para Otimização Combinatória
3.1 Introdução . . . . . . . . . . . . . . . . . . . . . .
3.2 Conceitos Importantes . . . . . . . . . . . . . . .
3.3 Classificação . . . . . . . . . . . . . . . . . . . . .
3.4 Principais Metaheurísticas . . . . . . . . . . . . .
3.4.1 Métodos baseados em Um Único Ponto . .
3.4.2 Métodos Populacionais . . . . . . . . . . .
3.5 Considerações Finais . . . . . . . . . . . . . . . .
4 Trabalhos Correlatos
4.1 Introdução . . . . . .
4.2 Asynchronous Teams
4.3 AGENT-DOSS . . .
4.4 Coal-VRP . . . . . .
4.5 DyCoal-VRP . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
vii
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
1
2
2
2
3
3
.
.
.
.
.
.
.
.
.
.
.
.
5
5
6
6
8
10
12
13
16
16
17
17
17
.
.
.
.
.
.
.
19
19
19
21
23
23
28
29
.
.
.
.
.
30
30
30
32
33
34
4.6
4.7
4.8
4.9
4.10
4.11
4.12
4.13
Hiperheurísticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Metaheurísticas Cooperativas . . . . . . . . . . . . . . . . . . . . . .
MAGMA (MultiAGent Metaheuristics Architecture) . . . . . . . . . .
FGAS (Fine-Grained Agents System) . . . . . . . . . . . . . . . . . .
MAA-VRPTW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Um Framework Orientado a Objeto para Busca Local . . . . . . . . .
Um Framework Orientado a Objetos para Busca Local Multiobjetivo
Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
35
36
39
39
41
43
45
5 Arquitetura Multiagente para Metaheurísticas
5.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Aspectos desejáveis numa Arquitetura Multiagente para Otimização
Combinatória . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 Estrutura Geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.1 Ambiente de Atuação . . . . . . . . . . . . . . . . . . . . . . .
5.3.2 Agentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4 Algumas Especializações da Arquitetura AMAM . . . . . . . . . . . .
5.4.1 Especialização da Arquitetura AMAM para a Metaheurística
ACO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Algoritmos Genéticos . . . . . . . . . . . . . . . . . . . . . . .
Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . .
5.4.4 Instância da Arquitetura AMAM para a Metaheurística Busca
Tabu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
GRASP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
VNS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.7 Especilização da Arquitetura AMAM para a Metaheurística ILS
5.5 Modelagem UML aplicada à AMAM . . . . . . . . . . . . . . . . . .
5.6 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
46
6 Experimentos Computacionais
6.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Problema de Roteamento de Veículos com Janela de Tempo
6.2.1 Modelagem do PRVJT . . . . . . . . . . . . . . . . .
6.2.2 Descrição dos Problemas-Teste . . . . . . . . . . . . .
6.3 Heurísticas e Metaheurísticas Utilizadas . . . . . . . . . . .
6.3.1 Heurística Construtiva . . . . . . . . . . . . . . . . .
6.3.2 Heurística de Busca Local . . . . . . . . . . . . . . .
6.3.3 Metaheurística Iterated Local Search . . . . . . . . .
6.3.4 Algoritmo Variable Neighborhood Search . . . . . . .
6.4 Experimentos com as especializações da Arquitetura AMAM
6.4.1 Especialização AMAM-ILS . . . . . . . . . . . . . . .
6.4.2 Especialização AMAM-VNS . . . . . . . . . . . . . .
6.4.3 Especialização AMAM-ILS-ILS . . . . . . . . . . . .
70
70
71
72
74
75
76
76
76
77
78
78
81
83
viii
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
47
48
49
50
53
55
56
58
58
59
61
62
64
69
6.5
6.4.4 Especialização AMAM-VNS-VNS . . . . . . . . . . . . . . . . 86
6.4.5 Especialização AMAM-ILS-VNS . . . . . . . . . . . . . . . . . 89
Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
7 Conclusões Gerais e Trabalhos Futuros
93
7.1 Conclusões Gerais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.2 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
Referências
95
ix
Lista de Tabelas
6.1
6.2
6.3
6.4
6.5
6.6
Informações dos problemas-teste de Solomon (Solomon,
Soluções do AMAM-ILS para o PRVJT. . . . . . . . .
Soluções do AMAM-VNS para o PRVJT. . . . . . . . .
Soluções do AMAM-ILS-ILS para o PRVJT. . . . . . .
Soluções do AMAM-VNS-VNS para o PRVJT. . . . . .
Soluções do AMAM-ILS-VNS para o PRVJT. . . . . .
x
1987).
. . . .
. . . .
. . . .
. . . .
. . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
74
80
82
85
88
91
Lista de Figuras
2.1
2.2
2.3
Sistema Multiagente. Fonte: Wooldridge (2002). . . . . . . . . . . . . 10
Sistemas de software homogêneos são substituídos por uma coleção
de simples agentes com tarefas específicas. . . . . . . . . . . . . . . . 11
Relação Agente/Ambiente. Fonte: Wooldridge (2002). . . . . . . . . . 15
3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8
3.9
3.10
3.11
3.12
Grafo que representa o espaço de busca e as relações entre as
Ótimo Global e Ótimo Local no espaço de busca. . . . . . .
Pseudocódigo Algoritmo de Busca Local. . . . . . . . . . . .
Pseudocódigo Algoritmo Simulated Annealing. . . . . . . . .
Funcionamento da Metaheurística Busca Tabu. . . . . . . .
Pseudocódigo Algoritmo Busca Tabu. . . . . . . . . . . . . .
Pseudocódigo Algoritmo GRASP. . . . . . . . . . . . . . . .
Pseudocódigo Algoritmo VNS. . . . . . . . . . . . . . . . . .
Funcionamento da Metaheurística ILS. . . . . . . . . . . . .
Pseudocódigo Algoritmo ILS. . . . . . . . . . . . . . . . . .
Pseudocódigo Algoritmo AG. . . . . . . . . . . . . . . . . .
Pseudocódigo Algoritmo ACO. . . . . . . . . . . . . . . . . .
4.1
4.5
4.6
4.7
4.8
Asyncronous Teams: C1-C5 são agentes construtores; D1-D2 são
agentes destrutores; e M1-M2 são memórias. Fonte: Talukdar e Souza
(1990) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
MAGMA - Arquitetura Multi-Níveis para metaheurísticas. Fonte:
Milano e Roli (2004) . . . . . . . . . . . . . . . . . . . . . . . . . . .
Especialização da arquitetura MAGMA para GRASP. Fonte: Milano
e Roli (2004) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Especialização da arquitetura MAGMA para ACO. Fonte: Milano e
Roli (2004) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Algoritmo Multiagente para o PRVJT. Fonte: Leong e Liu (2006) . .
Interações entre agentes em MAA-VRPTW. Fonte: Leong e Liu (2006)
O Framework Buscador de Vizinhos. Fonte: Andreatta et al. (1998) .
O Framework METHOOD. Fonte: Claro e Sousa (2001) . . . . . . .
38
40
41
42
44
5.1
5.2
5.3
5.4
5.5
5.6
Arquitetura Multiagente AMAM. . . . . . . . . .
Modelo do Ambiente. . . . . . . . . . . . . . . . .
Modelo do ambiente para o Problema da Mochila.
Estrutura Interna dos Agentes de Busca. . . . . .
Algoritmo para um Agente Construtor Básico. . .
Algoritmo para um Agente de Busca Local básico.
48
49
50
53
54
55
4.2
4.3
4.4
xi
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
soluções.
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
20
21
23
24
25
25
26
27
27
27
28
29
31
37
38
5.7
5.8
5.9
5.10
5.11
5.12
5.13
5.14
5.15
5.16
5.17
5.18
5.19
5.20
5.21
5.22
5.23
5.24
5.25
5.26
5.27
6.1
6.2
6.3
6.4
6.5
6.6
6.7
6.8
6.9
6.10
6.11
6.12
6.13
6.14
6.15
6.16
Especialização da Arquitetura AMAM para a metaheurística ACO. .
Algoritmo para uma especialização da Arquitetura AMAM para a
metaheurística ACO. . . . . . . . . . . . . . . . . . . . . . . . . . . .
Especialização da Arquitetura AMAM para a metaheurística AG. . .
metaheurística AG. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Especialização da Arquitetura AMAM para a metaheurística SA. . .
metaheurística SA. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Especialização da Arquitetura AMAM para a metaheurística BT. . .
Especialização da Arquitetura AMAM para a metaheurística BT. . .
Especialização da Arquitetura AMAM para a metaheurística GRASP.
metaheurística GRASP. . . . . . . . . . . . . . . . . . . . . . . . . .
Especialização da Arquitetura AMAM para a metaheurística VNS. .
metaheurística VNS. . . . . . . . . . . . . . . . . . . . . . . . . . . .
Especialização da Arquitetura AMAM para a metaheurística ILS. . .
metaheurística ILS. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Modelagem simplificada da Arquitetura AMAM. . . . . . . . . . . . .
Modelo Detalhado da Arquitetura AMAM. . . . . . . . . . . . . . . .
Interações entre os agentes e o mediador. . . . . . . . . . . . . . . . .
Padrão Estratégia na definição dos Agentes Construtores. . . . . . . .
Padrão Estratégia na definição dos Agentes de Busca. . . . . . . . . .
Padrão Estratégia na definição dos Agentes de Busca. . . . . . . . . .
Padrão Fachada na definição de uma interface para os Agentes. . . .
(A) grafo que representa o PRVJT e (B) grafo que representa uma
solução para o PRVJT. . . . . . . . . . . . . . . . . . . . . . . . . .
Problema de Roteamento de Veículos com Janela de Tempo. . . . .
Instância C101. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Instância R101. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Instância RC101. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Algoritmo da Construção Gulosa baseada em Janela de Tempo. . .
Algoritmo do Método de Descida. . . . . . . . . . . . . . . . . . . .
Algoritmo do Método Iterated Local Search. . . . . . . . . . . . . .
Algoritmo do Método VNS. . . . . . . . . . . . . . . . . . . . . . .
AMAM-ILS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
AMAM-VNS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
AMAM-ILS-ILS. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Gráfico comparativo do desempenho entre as especializações AMAMILS e AMAM-ILS-ILS. . . . . . . . . . . . . . . . . . . . . . . . . .
AMAM-VNS-VNS. . . . . . . . . . . . . . . . . . . . . . . . . . . .
Gráfico comparativo do desempenho entre as especializações AMAMVNS e AMAM-VNS-VNS. . . . . . . . . . . . . . . . . . . . . . . .
AMAM-ILS-VNS. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
xii
.
.
.
.
.
.
.
.
.
.
.
.
55
56
57
57
58
59
59
60
60
61
61
62
63
63
65
66
67
67
68
68
68
71
73
74
75
75
76
77
77
77
79
81
83
. 84
. 86
. 87
. 89
6.17 Gráfico comparativo do desempenho entre as especializações AMAMILS, AMAM-VNS e AMAM-ILS-VNS. . . . . . . . . . . . . . . . . . 89
6.18 Gráfico comparativo do desempenho entre as especializações AMAMILS-ILS, AMAM-VNS-VNS e AMAM-ILS-VNS. . . . . . . . . . . . . 90
xiii
Capítulo 1
Introdução
1.1
Aspectos Gerais
Problemas de otimização combinatória são freqüentemente encontrados em diversas áreas, como aplicações industriais, processos logísticos, dentre outras. Estes
problemas consistem na busca do melhor ajuste do valor de suas variáveis de modo
a atender a um objetivo e satisfazer a um conjunto de restrições pré-definidas. Em
parte dos casos, a solução destes problemas pode ser determinada através de métodos
de programação matemática, como o método Branch-and-Bound (veja Bertsimas e
Tsitsiklis (1997)), capazes de encontrar a solução ótima exata dessa classe de problemas.
Grande parte dos Problemas de Otimização Combinatória é classificada, na literatura, como NP-difícil, para os quais ainda não existem algoritmos que os resolvam
em tempo polinomial. Desta forma, os algoritmos exatos podem precisar de tempo
computacional exponencial ou maior, no pior caso, para solucionar estes problemas,
tornando o uso destes métodos bastante restrito.
Tal dificuldade vem sendo em parte ultrapassada com a aplicação de técnicas
heurísticas e metaheurísticas, que possibilitam a determinação de soluções factíveis
sub-ótimas para uma enorme gama de problemas encontrados na vida prática. A
principal dificuldade a ser vencida pelos métodos baseados em programação matemática reside na necessidade de uma busca exaustiva a ser realizada no espaço
de soluções dos problemas objeto de interesse. Já os procedimentos heurísticos e
metaheurísticos tentam ultrapassar essa questão, guiando a geração de soluções de
modo a proporcionar uma solução de qualidade (avaliada segundo funções expressando os interesses de decisão postos) em um tempo computacional limitado.
As metaheurísticas combinam, em sua ação, diferentes táticas e atuações, no
intuito de buscar o melhor resultado para o problema sob análise. Essa ação pode se
dar, contudo, através de sua formulação como sistemas de diversos agentes, atuando
de forma cooperativa e competitiva.
A evolução das redes de computadores permitiu a utilização de sistemas distribuídos na solução de problemas complexos. Esta complexidade é reduzida por meio
da divisão do problema em subproblemas menores. A demanda por softwares cada
vez mais adaptativos e inteligentes tem conduzido à incorporação de novas tecnologias no tratamento de diversos problemas, como por exemplo, a tecnologia baseada
em agentes inteligentes.
1
1.2
Objetivos
2
Considerando que grande parte dos problemas de otimização combinatória são
complexos e possuem características distribuídas, a abordagem baseada em agente
distingue-se, no tratamento desta classe de problemas, pelo seu poder em modelar
problemas de natureza distribuída e expressar, através das entidades do sistema, a
complexidade das relações envolvidas.
Sistemas multiagentes são sistemas compostos de múltiplos elementos computacionais, em constante interação, chamados agentes (Wooldridge, 2002). Nestes
sistemas, a possibilidade de interação e cooperação entre os diversos agentes permite uma maior exploração do espaço de busca, já que cada agente possui uma
“esfera de influência” diferente e trocam informações sobre elas.
Este trabalho pretende combinar diversas metaheurísticas através da abordagem
multiagente e, desta forma, explorar a atuação cooperativa, existente em um ambiente multiagente, para melhor conhecer as características do espaço de busca e obter
“boas” soluções para o problema.
Adicionalmente, a flexibilidade de uma arquitetura multiagente possibilita que
novos agentes (no caso deste trabalho, as metaheurísticas) sejam facilmente incorporados. Assim, esta abordagem também diminui o esforço empregado no desenvolvimento de metaheurísticas híbridas, que demonstram melhor desempenho na solução
de problemas.
1.2
1.2.1
Objetivos
Objetivo Geral
O objetivo geral deste trabalho é a modelagem de uma arquitetura multiagente
para a solução, via metaheurísticas, de problemas de otimização combinatória. Na
arquitetura, nomeada como AMAM, cada metaheurística é definida como um agente
de busca, que atua na exploração do espaço de busca. O ambiente, no qual os
agentes atuam, é parte integrante da arquitetura e corresponde ao espaço de busca
do problema em questão.
Os agentes possuem capacidade de comunicação entre si e com o seu ambiente.
A partir das possibilidades de comunicação, o comportamento dos agentes tende a
atingir um objetivo comum (solução ótima) de forma cooperativa.
A arquitetura AMAM propõe uma estrutura geral (framework ), onde as diversas metaheurísticas existentes podem ser facilmente adicionadas, como agentes, e
utilizadas na solução dos diferentes tipos de problemas de otimização combinatória.
1.2.2
Objetivos Específicos
Para que este objetivo geral seja alcançado é necessário atingir os seguintes objetivos específicos:
(i) Conhecimento da literatura relevante associada aos principais temas envolvidos no trabalho, qual seja, metodologias multiagentes usadas na solução de
problemas de otimização combinatória; projeto e implementação de sistemas
multiagentes;
1.4
Metodologia de Pesquisa
3
(ii) Estudo e implementação computacional das principais técnicas heurísticas e
metaheurísticas existentes;
(iii) Definição e modelamento dos elementos de uma arquitetura multiagente para
a solução de problemas de otimização combinatória;
(iv) Desenvolvimento de especializações da arquitetura para problemas de otimização combinatória, que serão utilizadas para teste e validação da Arquitetura
proposta.
1.3
Metodologia de Pesquisa
Para o desenvolvimento deste trabalho e a definição da arquitetura AMAM é
preciso, inicialmente, identificar e determinar seus componentes. Neste sentido, as
principais propostas de arquiteturas de software baseadas em agentes devem ser
analisadas para fornecer fundamentos e técnicas adequadas para a elaboração de
sistemas multiagentes. O projeto da arquitetura AMAM deve incluir: as características das partes que irão compor a arquitetura, como elas interagem e onde estas
interações ocorrem.
Uma revisão de literatura, relacionada a metaheurísticas, permitirá a identificação das semelhanças entre os diversos métodos, possibilitando a modelagem dos
agentes de busca que farão parte da arquitetura proposta. Em conjunto com a revisão das principais metaheurísticas, para a modelagem dos agentes serão examinadas
as definições relacionadas à arquitetura de agentes de softwares: classificações de
agentes, mapeamento de percepções e ações, entre outras características que devem
ser consideradas para a correta aplicação do termo agente.
Após a modelagem da arquitetura AMAM, especializações da mesma serão desenvolvidas com o objetivo de analisar seu adequado funcionamento na solução de
diferentes problemas de otimização e a flexibilidade da arquitetura, através da adição
de novos agentes (metaheurísticas) com o mínimo de impacto. Na implementação
destas aplicações, será utilizada a linguagem Java, empregando a plataforma Eclipse.
Por especializações, é entendido neste trabalho como o desenvolvimento de algumas metaheurísticas, ou seja, partes do framework proposto, bem como partes do seu
processo de comunicação. Isso porque, não é escopo deste trabalho a implementação
do framework completo, apenas a sua proposta e modelagem.
A análise dos resultados obtidos nos testes destas especializações permitirá a
avaliação do desempenho da arquitetura e sua possível validação.
1.4
Estrutura da Dissertação
O presente trabalho está organizado da seguinte forma: no capítulo 2, uma
revisão de literatura em relação a sistemas multiagentes é apresentada, buscando
introduzir os principais conceitos envolvidos; o capítulo 3 descreve conceitos importantes ligados à metaheurísticas, assim como as principais metaheurísticas conhecidas e suas formas de classificação; o capítulo 4 discute trabalhos que utilizam as
abordagens multiagente e orientada a objetos no tratamento de metaheurísticas; no
1.4
Estrutura da Dissertação
4
capítulo 5 é apresentada a arquitetura AMAM proposta, assim como os elementos
que a compõem e as formas de interação existentes entre eles; o capítulo 6 apresenta
algumas especializações da arquitetura AMAM para o Problema de Roteamento de
Veículo com Janela de Tempo, com resultados obtidos nos testes destas especializações. Por fim, o capítulo 7 apresenta as conclusões do trabalho e as perspectivas de
trabalhos futuros.
Capítulo 2
Sistemas Multiagentes
2.1
Introdução
A Inteligência Artificial (IA) é uma área de conhecimento que utiliza o comportamento individual humano como modelo para desenvolver sistemas inteligentes.
Na metade da década de 1970, a formulação de Inteligência Artificial Distribuída
(IAD) é apresentada como uma sub-área da Inteligência Artificial. A IAD se baseia
no comportamento social para o desenvolvimento de projeto de sistemas, dando
ênfase em ações e interações sociais. Desde o seu surgimento, a IAD tem evoluído
e se diversificado rapidamente, apresentando aplicações que abrangem diferentes
áreas.
Uma das principais razões para a utilização da Inteligência Artificial Distribuída
no desenvolvimento de sistemas está na possibilidade de se resolver problemas complexos, que envolvam um maior número de variáveis e até mesmo recursos fisicamente
distribuídos. Ao mesmo tempo que a quantidade de informação a ser tratada cresce
continuamente e as aplicações envolvendo tomada de decisão são cada vez mais
necessárias (e.g., sondas, buscadores de internet, robótica).
Neste sentido, para evitar as dificuldades em manter consistência em grandes
projetos de software, existe uma tendência em decompor sistemas em componentes
menores que podem ser compreendidos de forma independentes.
A IAD é dividida em duas áreas: Solução Distribuída de Problemas (SDP) e
Sistemas MultiAgentes (SMA). A SDP busca solucionar um problema específico,
dividindo-o em muitos módulos que cooperam interagindo e trocando conhecimentos
sobre o problema e sua solução. A área de Sistemas MultiAgentes estuda como
coordenar o comportamento de uma sociedade de agentes autônomos para resolver
um determinado problema. Desta forma, contrapondo à SDP, que tem seu foco no
problema, os Sistemas MultiAgentes se concentram nos agentes.
A tecnologia de agentes é um paradigma de software apropriado à exploração
das possibilidades apresentadas em grandes sistemas distribuídos abertos - como,
por exemplo, a Internet.
Assim, o objetivo deste capítulo é introduzir os principais tópicos relacionados
a sistemas de multiagentes que serão úteis no decorrer deste trabalho, assim como,
procurar responder a questões como:
(i) Por que acredita-se que agentes são uma nova e importante forma de concepção
5
2.2
Definições
6
e implementação de sistemas computacionais?
(ii) O que são agentes?
(iii) Quais são as principais abordagens que têm sido utilizadas na implementação
de agente? Quais os méritos e desafios enfrentados?
(iv) Quais são os componentes básicos de um sistema multiagente?
2.2
Definições
Diversas técnicas de solução de problemas têm sido desenvolvidas utilizando os
conceitos de Inteligência Artificial (IA). Dentre estes, pode-se destacar métodos heurísticos e metaheurísticos (Blum e Roli, 2003), algoritmos evolutivos (Bäck, 1996),
redes neurais (Bleale e Jackson, 1990), sistemas fuzzy (Driankov et al., 1990), entre
outros.
Entretanto, com o surgimento das redes de computadores e seu crescimento,
questões relacionadas aos processos de interação e de comunicação entre os sistemas
computacionais foram levantadas. Adicionalmente, a complexidade das tarefas que
são automatizadas e delegadas aos computadores cresce continuamente. Fatores
como estes motivaram o nascimento, ainda na década de 70, da Inteligência Artificial
Distribuída (IAD), que envolve a solução de problemas nos quais as características
distribuídas são inerentes.
É neste contexto que surgem os agentes e sistemas multiagentes e se tornam uma
importante forma de lidar com uma quantidade cada vez maior de informações e
dados.
Nesta seção, alguns conceitos básicos em sistemas multiagentes são apresentados.
2.2.1
Agentes
Como em outros sistemas inspirados na natureza, a IA se baseia no comportamento individual do ser humano para projetar sistemas computacionais que buscam
desempenhar atividades como: pensar, raciocinar, tomar decisões, planejar, perceber, comunicar e aprender. O termo agente é usado para nomear estes tipos de
sistemas.
Há pouca concordância na literatura a respeito do termo agente, isto porque,
para diferentes domínios, existem diferentes níveis de relevância e pertinência em
cada uma das propriedades relacionadas com agentes.
Em Wooldridge (2002) é proposta a seguinte definição para o termo agente:
“Um agente é um sistema de computador que é situado em um ambiente,
e é capaz de ação autônoma neste ambiente para conhecer seus objetivos
de projeto.”
Já segundo Russell e Norvig (1995), o mesmo termo pode ser visto como:
“Um agente é uma entidade que pode perceber seu ambiente através de
sensores (ou sistemas de percepção) e atuar sobre ele por intermédio de
seus mecanismos de atuação (ou sistemas de atuação, atuadores). Para
2.2
Definições
7
isso dispõe de uma representação parcial deste ambiente, podendo, em
um universo multiagente, comunicar-se com outros agentes. O comportamento global do agente ou da comunidade de agentes é conseqüência
de suas percepções e conhecimentos, bem como das iterações realizadas.”
No contexto de métodos metaheurísticos, uma definição, apresentada por Milano
e Roli (2004), que se enquadra aos interesses deste trabalho é apresentada:
“Um agente pode ser entendido como um sistema capaz de construir uma
solução, mover em um espaço de busca, comunicar com outros agentes,
ser ativo e possívelmente adaptativo.”
Adicionalmente, para fins deste trabalho, é importante destacar que o agente
deve ser capaz de perceber os atributos do ambiente em que está situado, como já
apresentado por Russell e Norvig (1995), em sua definição.
A partir das definições apresentadas, é possível identificar propriedades que são
fundamentais na distinção entre agente e outros sistemas computacionais. De acordo
com Wooldridge e Jennings (1995), de uma forma mais geral, as principais propriedades de um agente são:
(i). Autonomia: característica que permite ao agente atingir seu objetivo sem
intervenções ou comandos do ambiente, ou seja, o agente é capaz de agir
sozinho. Assim, o agente possui algum tipo de controle sobre suas ações e seu
estado interno.
(ii). Habilidade social: o agente interage com outros agentes (e possivelmente
humanos) através de algum tipo de linguagem de comunicação.
(iii). Reatividade: é a habilidade que o agente possui de reagir apropriadamente às
influências ou informações de seu ambiente. O agente percebe o ambiente, (que
pode ser o mundo físico, um usuário via uma interface gráfica, uma coleção de
agentes, entre outros), e responde em tempo oportuno às mudanças ocorridas
nele.
(iv). Pro-atividade: o agente não apenas reage a mudanças ambientais, mas toma
iniciativa sobre circunstâncias específicas. Para que esta habilidade seja alcançada, é preciso que o agente seja orientado a metas, ou seja, possua objetivos
bem definidos.
Entretanto, outras características consideradas importantes são destacadas por
vários autores, como Nwana (1996), Lesser (1999), dentre outros. São elas:
(v). Raciocínio/Aprendizado: a inteligência de um agente é formada principalmente por três fatores: (1) base de conhecimento; (2) capacidade de raciocínio
baseado no conteúdo da base de conhecimento; e (3) habilidade de aprender
e/ou adaptar-se a mudanças do ambiente. Entretanto, a presença dos três
fatores em conjunto não é essencial.
(vi). Mobilidade: é a habilidade do agente de se mover e ser executado em outras
plataformas.
2.2
Definições
8
(vii). Cooperação: é a habilidade de comunicação com outros agentes, para atingir
um mesmo objetivo conjuntamente. Um sistema multiagente, assim, é composto por um conjunto de agentes em um ambiente, cada um com uma função
específica, e um conjunto de objetivos a serem alcançados.
(viii). Personalidade: capacidade do agente de personificar-se, utilizando recursos
que emulem aqueles de seres humanos.
(ix). Adaptabilidade: propriedade amplamente relacionado com a autonomia.
Quanto mais autônomo uma agente é, mais adaptável ele será ao contexto
de solução do problema.
A importância dada a cada uma dessas características depende, como já foi
dito, do interesse de cada domínio. Um bom exemplo para esta afirmativa está
na propriedade de mobilidade, que é de extrema relevância no que diz respeito a
sistemas de agentes situados em uma rede e que precisam se mover através dela ou,
até mesmo, um sistema de agentes projetado em um ambiente complexo, que possui,
como característica essencial, o aprendizado.
Lesser (1999) afirma, ainda, que os agentes podem ser caracterizados como sendo
benevolentes (cooperativos) ou auto-interessados. Agentes benevolentes trabalham
para atingir um objetivo comum, enquanto agentes auto-interessados têm objetivos
distintos, embora possam interagir para avançar segundo o seu próprio objetivo.
As propriedades descritas acima podem ser divididas em dois tipos: as propriedades internas e as propriedades externas de um agente. As propriedades internas
são aquelas que formam o estado interno do agente, ou seja, o aprendizado, a reatividade, a autonomia e a orientação a metas. As propriedades externas são aquelas
que afetam a interação entre os diversos agentes (cooperação) ou a comunicação dos
agentes.
O agente possui um conjunto de ações disponíveis, que representam a sua habilidade em atuar e modificar o seu ambiente. Além disso, pré-condições são relacionadas com cada ação, definindo quando elas podem ser usadas. O agente deve
escolher qual a melhor ação a ser executada, ou seja, qual ação o aproxima mais do
seu objetivo.
O agente pode possuir, também, algum tipo de estrutura de dados interna (estado
interno) que armazene informações sobre o estado do ambiente e sua história. Este
estado interno pode ser definido como o conhecimento do agente e é utilizado também
no processo de tomada de decisão. Baseado nas interações com o ambiente e com
os outros agentes do sistema, o agente é capaz de atualizar o seu estado interno,
atualizando o seu conhecimento do ambiente.
2.2.2
Sistemas Multiagentes
A Inteligência Artificial Distribuída é uma subárea da IA que estuda a utilização
de uma sociedade de agentes na solução de um único problema através da divisão
deste em problemas menores. A solução de problemas, a partir da IAD, é baseada
no comportamento do homem em sociedade e suas interações.
Uma definição apropriada para Sistemas MultiAgentes, apresentada em Lesser
(1999), diz que:
2.2
Definições
9
“Sistemas multiagentes são sistemas computacionais em que dois ou mais
agentes interagem ou trabalham juntos para desempenhar um conjunto
de tarefas ou satisfazer um conjunto de objetivos.”
Da mesma forma, Wooldridge (2002) afirma que um conjunto de agentes autônomos em um ambiente caracteriza um sistema multiagente. Assim, ainda segundo
este mesmo autor, um sistema multiagente é composto por agentes em um ambiente,
cada um com uma função específica, e um conjunto de objetivos a serem alcançados.
A soma das habilidades de cada um dos agentes possibilita a solução do problema e
a constante interação entres os agentes define o comportamento global do sistema.
Sistemas complexos, por possuírem componentes heterogêneos com vários tipos
de dependências ou de natureza distribuída, constituem potenciais aplicações para
Sistemas Multiagentes. Algumas das áreas que utilizam tipicamente a abordagem
multiagente são: e-commerce, controle aéreo, gerenciamento de sistemas industriais,
desenvolvimento de jogos, robótica, sistemas de informação, dentre outras.
A educação é uma área em que a tecnologia de agentes tem sido amplamente
usada. Diversos ambientes educacionais e sistemas tutores inteligentes buscam auxiliar no ensino-aprendizagem, oferecendo ambientes dinâmicos e recursos que facilitam a interação do estudante. O MathTutor é um sistema tutor inteligente
proposto em Frigo et al. (2004) e utiliza as técnicas de Sistemas Multiagentes, visando o acompanhamento da aprendizagem do estudante num dado domínio. Este
sistema multiagente modela o conhecimento do estudante sobre um determinado
assunto à medida que ele interage com o sistema, comparando este conhecimento
com o modelo do especialista do domínio.
Sistemas multiagentes são, também, freqüentemente utilizados no desenvolvimento de jogos. Um exemplo da utilização de agentes em jogos é apresentado em
Machado et al. (2004), no qual jogos de RPG (jogos de interpretação de personagem) são desenvolvidos, buscando uma maior interatividade através da abordagem
multiagente.
Vários trabalhos têm utilizado a abordagem de agentes para a solução de problemas de otimização a partir de métodos metaheurísticos, como é o caso do presente
trabalho. Estes trabalhos serão descritos com maiores detalhes no capítulo 4.
Moulin e Chaib-draa (1996) descrevem algumas vantagens significativas dos Sistemas Multiagentes em relação aos solucionadores de problemas monolíticos. Dentre
as citadas nesta referência, destacam-se as seguintes:
- maior rapidez na resolução de problemas através dos aproveitamento do paralelismo;
- diminuição da comunicação por transmitir somente soluções parciais em alto
nível para outros agentes ao invés de dados brutos para um lugar central;
- mais flexibilidade por ter agentes com diferentes habilidades que são dinamicamente agrupados para resolver problemas; e
- aumento da segurança pela possibilidade de agentes assumirem responsabilidades de outros agentes que falham.
2.2
Definições
10
Adicionalmente, em um ambiente multiagente, cada agente possui sua “esfera
de influência”, ou seja, um agente tem visibilidade e acesso a apenas uma região
do ambiente, conforme apresentado na Figura 2.1. Desta forma, um dos principais
objetivos da utilização de sistemas multiagentes na solução de problemas é explorar
a capacidade dos agentes em controlar em diferentes partes do ambiente, obtendo,
assim, um maior conhecimento do mesmo. Isto acontece porque, através da troca
de informações entre os agentes, estes obtêm acesso a dados que, caso estivessem
trabalhando sozinhos, estariam fora do seu alcance.
Um bom exemplo do limite de influência de um agente em seu ambiente pode
ser descrito a partir da utilização da abordagem multiagente no projeto de métodos
metaheurísticos, como apresentado neste trabalho. Cada metaheurística possui sua
função de vizinhança (ou mais de uma, em alguns casos), que define a sua possibilidade de atuação sobre o espaço de busca do problema a ser tratado. Assim, esta
atuação está limitada à parte do espaço de busca a qual a função de vizinhança consegue acessar, ou seja, quais possíveis soluções para o problema podem ser geradas
a partir dela.
Ambiente
Legenda:
esferas de influência
relações organizacionais
interações
agente
Figura 2.1: Sistema Multiagente. Fonte: Wooldridge (2002).
2.2.3
Agentes e Objetos
A tecnologia de agentes provoca uma revolução no desenvolvimento de software.
Desta forma, a Figura 2.2 mostra como a tecnologia agente muda a forma como o
software é estruturado em relação à tecnologia convencional. Na tecnologia convencional, o software é construído como camadas de abstração, enquanto que os sistemas
agentes são formados por muitos programas independentes construídos com base
no modelo de tarefas. O modelo de desenvolvimento da tecnologia convencional
2.3
Definições
11
apresenta alguns problemas, como, principalmente, o crescimento, proporcional ao
número de funcionalidades do sistema e interações de usuários, da complexidade de
construção da interface entre as diferentes camadas (já que cada uma delas representa um nível de abstração diferente).
Sistema de Informação
Aplicações
Linguagem de Alto-Nível
Sistema Operacional
Gerenciamento de Recursos
Modelo
de
Tarefas
Modelo Modelo
de
de
Tarefas Tarefas
Compor- Compor- Comportamento tamento tamento
Modelo
de
Tarefas
Comportamento
Gerenciamento de Recursos
Figura 2.2: Sistemas de software homogêneos são substituídos por uma coleção de
simples agentes com tarefas específicas.
Neste sentido, a tecnologia de agentes possibilita a diminuição da complexidade
de desenvolvimento de grandes sistemas, pois cada cada agente pode ser estruturado
de forma independente e novas funcionalidade podem ser acrescentadas a partir da
adição de novos agentes, sem que a complexidade de cada agente individual ou de
sua interface seja influenciada.
Vários autores, como Wooldridge e Jennings (1995), apresentam questões relacionadas às similaridades e às diferenças entre agentes e objetos, assim como destacam
a importância de se identificar estas diferenças, que são significativas.
Wooldridge e Jennings (1995) apresentam a seguinte definição para objeto:
“Objetos são entidades computacionais que encapsulam algum estado,
são capazes de desempenhar ações, ou métodos sobre este estado, e se
comunicam por meio de transferência de mensagens”.
Estes mesmos autores descrevem três diferenças fundamentais entre agentes e objetos. Estas diferenças são sumarizadas a seguir:
(i). Grau de autonomia existente em agentes e objetos: no caso orientado-aobjetos, a decisão de executar determinado método, quando isto for solicitado
por outro objeto, não é do objeto que possui o método, mas, sim, daquele
que faz a chamada, ou seja, o objeto não possui controle sobre o seu comportamento. No caso de agentes, a decisão de realizar ou não uma certa tarefa
solicitada, está com o agente que recebe a requisição.
(ii). Comportamento autônomo flexível (reatividade, pro-atividade, habilidade social): o modelo de objetos não tem nada a dizer sobre como construir sistemas
que integrem este tipo de comportamento, presente no modelo de agentes.
(iii). Número de threads envolvidas: um sistema multiagente é inerentemente multithreads, já que cada agente é assumido como tendo ao menos uma thread de
controle. No modelo padrão de objetos, existe, em geral, uma simples thread
de controle no sistema.
2.3
2.3
Interações
12
Interações
A interação é um dos elementos mais importantes em um sistema multiagente e
acontece através das trocas de informação que podem ocorrer entre os agentes.
Lesser (1999) apresenta duas situações básicas que determinam como as relações
(interações) surgem naturalmente com a decomposição de um problema em subproblemas. A primeira situação é aquela na qual os subproblemas são os mesmos ou
estão sobrepostos, embora diferentes agentes tenham métodos ou dados alternativos
que podem ser usados para gerar uma solução. A segunda forma de interdependência ocorre quando dois subproblemas são partes de um problema maior, e a solução
para este problema maior requer que certas restrições existam na solução dos seus
subproblemas.
Desta forma, o protocolo de comunicação para o sistema multiagente é o primeiro
passo para que agentes possam trocar e compreender mensagens enviadas por outros
agentes. Através da comunicação, os agentes buscam coordenar suas ações e seus
comportamentos, para melhor atingir seus próprios objetivos ou os objetivos da
sociedade de agentes.
Em um sistema multiagente, é do interesse de cada um dos agentes integrantes que todos sejam capazes de participar de uma conversação. Neste sentido, os
protocolos de comunicação são definidos para permitirem o entendimento de uma
mensagem, considerando três aspectos básicos (Weiss, 2000): (i) sintaxe (ou seja,
como os símbolos de comunicação são estruturados); (ii) semântica (o que os símbolos conotam); e (iii) pragmática (como os símbolos são interpretados). O significado
da mensagem é a combinação de semântica e pragmática.
Um exemplo conhecido de protocolo de comunicação é o Knowledge Query and
Manipulation Language - KQML (Linguagem de manipulação e Consulta ao Conhecimento). O protocolo KQML é um protocolo para a troca de informação e
conhecimento (Weiss, 2000), sendo que sua estratégia é incluir, na própria comunicação, toda a informação necessária para a compreensão do conteúdo da mensagem.
Outra estrutura típica de comunicação, de Quadro-Negro (Blackboard ), é um
exemplo de forma de comunicação em sistemas multiagente. Nesta abordagem, uma
espécie de repositório (Quadro-Negro), no qual os agentes podem ler e escrever mensagens, é usado como meio de interação. Desta forma, este repositório define uma
memória “comunitária” (compartilhada) de dados, soluções parciais, alternativas ou
finais, e informações de controle. Assim, como o repositório normalmente é parte
integrante do ambiente, este pode ser utilizado como mediador de comunicação, já
que, através do repositório, os agentes podem inserir e retirar informações. Uma
revisão de sistemas de quadro-negro é apresentada por Corkill (1991).
Já os protocolos de interação permitem que, através do trabalho em conjunto,
agentes estabeleçam uma conversação. Estes agentes, no entanto, podem possuir objetivos conflitantes ou, até mesmo, compartilharem objetivos comuns. Desta forma,
pode ser necessário a existência de uma coordenação das atividades dos agentes
durante a solução do problema, buscando manter a coesão do sistema.
Segundo Weiss (2000), a cooperação é a coordenação entre agentes aliados, enquanto a negociação é a coordenação entre agentes competitivos e simplesmente
auto-interessados.
Uma das possibilidades de interação é a cooperação entre os agentes, que permite
2.4
Ambiente
13
a realização de alguma ação de troca entre dois ou mais agentes que estejam tentando
atingir conjuntamente um mesmo objetivo.
A organização determina estruturas hierárquicas e diretrizes para que os agentes
possam atingir um objetivo comum. Assim, uma sociedade de agentes pode se organizar de diferentes formas, como, por exemplo, em uma relação Mestre-Escravo,
em que existem gerentes (mestres), que coordenam e distribuem as tarefas, e trabalhadores (escravos), que as realizam, ou ainda, em uma relação de Mecanismos de
Mercado, em que todos os agentes estão em um mesmo nível e conhecem as tarefas
que cada agente é capaz de desempenhar (Ferreira, 2002).
A interação em um sistema multiagente, do ponto de vista das teorias cognitivas contemporâneas, considerando a formulação de Agentes de Software Cognitivos
e Situados (Santos, 2003), é realizada por meio de atuadores e sensores que possibilitam estimular o ambiente e ser estimulado por este. Desta forma, o agente
percebe o mundo dinamicamente, à medida que com ele interagem. Segundo Santos
(2003), os sensores e atuadores são responsáveis pelo comportamento do agente e
por possibilitar a interação com o ambiente e com outros agentes. Estes componentes determinam o domínio das relações e interações do agente. Segundo ainda este
mesmo autor, os componentes sensores e atuadores são específicos para sentirem
determinados tipos de estímulos do ambiente.
2.4
Ambiente
Esta seção tem o objetivo de ressaltar a importância do ambiente para um sistema
multiagente, assim como destacar a relevância que tem sido dada a este elemento em
trabalhos recentes associados a este tema. Assim, Platon et al. (2007), Valckenaers
et al. (2007), Weyns et al. (2007), Henderson-Sellers e P. Giorgini (2005), apresentam
o ambiente como uma parte explícita e essencial aos sistemas multiagente, opondo-se
à idéia do ambiente como externo ao sistema.
Estes mesmos autores consideram o ambiente, no desenvolvimento de sistemas
multiagentes, como uma abstração primária durante as fases de análise e projeto.
Assim, o ambiente deixa de ser o “mundo externo” do sistema multiagente, para
ser um componente ativo dentro deste, possuindo responsabilidades específicas, que
se diferem das responsabilidades dos agentes; mediando interações e o acesso a
recursos; possibilitando percepções; e gerenciando mudanças de estados.
Várias definições de ambiente, no contexto de sistemas multiagente, podem ser
encontradas na literatura, sendo que cada uma destas definições demonstra uma
caráter subjetivo e apresenta papéis diferentes para o ambiente. Cinco destas definições são consideradas mais relevantes à luz dos interesses desse trabalho.
A primeira delas é devida a Russell e Norvig (1995), que define ambiente como
um “programa de ambiente genérico”. Segundo os autores, este programa permite
aos agentes perceberem o ambiente e as respostas deste em relação às suas ações.
Desta forma, a partir das ações do agente, o programa atualiza o estado do ambiente
e possibilita outros processos dinâmicos.
A segunda definição advém de Parunak (1997). Nesse caso, o ambiente é definido
como uma tupla <Estado, Processo>, em que:
2.4
Ambiente
14
- Estado: é o conjunto de valores que define completamente o ambiente, incluindo os agentes e objetos dentro dele.
- Processo: indica que o ambiente por si mesmo é uma entidade ativa, ou seja,
seus próprios processos podem mudar seu estado, independente das ações dos
agentes.
Uma terceira definição é apresentada em Demazeau (2003), propondo que um
sistema de agentes possui quatro blocos de construção essenciais:
(i). os agentes, ou seja, as entidades dos processos;
(ii). as interações, ou melhor, os elementos para estruturar as interações internas
entre as entidades;
(iii). as organizações, representadas pelos elementos para estruturar conjuntos de
entidades dentro do SMA;
(iv). e, finalmente, o ambiente, qual seja, os elementos dependentes do domínio,
que estruturam as interações externas entre as entidades.
Segundo Odell et al. (2003), apresentada aqui como a quarta definição de interesse, “o ambiente fornece as condições sob as quais uma entidade (agente ou objeto)
existe”. Desta forma, estes autores distinguem o ambiente em duas partes: o ambiente físico, que fornece as leis, regras, restrições e políticas que governam e suportam
a existência física das entidades, e o ambiente de comunicação, que fornece os princípios e os processos que governam e suportam as trocas de informação, assim como
as funções e estruturas, que são empregadas na comunicação.
Por fim, a quinta e última é devida a de Weyns et al. (2007). Para eles “o
ambiente é uma abstração de primeira classe que fornece as condições ambientais
para os agentes existirem e que media as interações entre os agentes e o acesso a
recursos”. Assim, segundo Weyns et al. (2007), a afirmação de que o ambiente é
uma abstração primária acentua o fato de que o ambiente é um bloco de construção
independente do restante do SMA, que encapsula suas próprias responsabilidades
definidas. Da mesma forma, esta definição salienta que o ambiente é parte essencial
de todo SMA, atuando ativamente, através da mediação e do gerenciamento de
recursos.
É importante ressaltar que esta última definição é a mais adequada aos objetivos
pretendidos pelo presente trabalho, que tem o ambiente como um dos principais
componentes da arquitetura proposta.
Desse modo, segundo o entendimento aqui adotado, o ambiente inclui todos os
elementos não-agentes do sistema multiagente, tais como, bases de dados, serviços
web, infraestrutura de comunicação e topologia de um domínio espacial (Weyns
et al., 2007).
As interações entre agente e ambiente interferem de forma indireta na atuação
do agente. As percepções do agente dependem de dois fatores: a capacidade dos
sensores de entrada e o tipo de ambiente em que este está inserido. Russell e Norvig
(1995) sugere a seguinte classificação das propriedades do ambiente:
2.4
Ambiente
15
• Acessível × Inacessível: um ambiente acessível é aquele em que o agente
pode obter informações completas, acuradas e atualizadas sobre o estado do
ambiente. A maioria dos ambientes do mundo real (incluindo, por exemplo, o
mundo físico cotidiano e a internet) não é acessível neste sentido.
• Determinístico × Não-Determinístico: um ambiente determinístico é
aquele em que qualquer ação tem um efeito simples garantido - não há nenhuma incerteza sobre qual será o resultado da execução de uma determinada
ação. Por outro lado, o não-determinismo captura o fato de que o agente tem
uma “esfera de influência” limitada e que suas ações podem falhar, não obtendo
o efeito desejado.
• Estático × Dinâmico: um ambiente estático é aquele que permanece inalterado, exceto pela execução de ações do agente. Em contraste, um ambiente
dinâmico é aquele que tem outros processos operando sobre ele, e que, portanto, se altera por si só, independente do controle do agente. O mundo físico
é um ambiente altamente dinâmico, como o é também a internet.
• Discreto × Contínuo: um ambiente é discreto se existe um número fixo e
finito de ações e percepções nele. Em um ambiente contínuo, existem incontáveis estados.
A figura 2.3 apresenta uma visão da relação entre agente e ambiente. O agente
obtém entradas sensórias do ambiente e produz, como saída, ações que afetam o
ambiente.
AGENTE
Sensor de
Entrada
Ação de
Saída
AMBIENTE
Figura 2.3: Relação Agente/Ambiente. Fonte: Wooldridge (2002).
Desta forma, identificar e modelar o ambiente envolve determinar todas as entidades e recursos que o SMA pode explorar, controlar, ou consumir quando está
trabalhando para a realização do objetivo organizacional (Henderson-Sellers e P. Giorgini, 2005). Neste mesmo sentido, ainda segundo Henderson-Sellers e P. Giorgini
(2005), algumas questões fundamentais que devem ser consideradas na fase de modelagem do ambiente são:
(a). Avaliar os recursos ambientais que o agente pode efetivamente acessar;
(b). Avaliar como os agentes devem perceber o ambiente, isto é, que representação
do ambiente é apropriada em uma dada situação;
(c). Avaliar o que deve ser de fato parte do ambiente.
2.5
Arquiteturas de Agentes
16
As responsabilidades centrais do ambiente são relacionadas em Weyns et al.
(2005), e descritas a seguir:
(i). O ambiente estrutura o Sistema Multiagente: o ambiente é um espaço compartilhado pelos agentes, recursos e serviços, os quais estruturam o sistema.
Três formas de estruturação são definidas: estrutura física (espacial, topologia), estrutura de comunicação (protocolos, entre outros) e estrutura social
(organização).
(ii). O ambiente embute recursos e serviços: recursos e serviços são tipicamente
situados em uma estrutura física. O ambiente deve fornecer uma interface
com o nível de recursos e serviços.
(iii). O ambiente pode manter processos dinâmicos: além da atividade do agente, o
ambiente pode manter processos próprios, independentes do agente.
(iv). O ambiente é localmente observável pelo agente: a observação de uma estrutura é tipicamente limitada ao contexto atual no qual o agente se encontra.
Em geral, os agentes deve ser capazes de inspecionar o ambiente de acordo
com suas tarefas correntes.
(v). O ambiente é localmente acessível ao agente: os agentes devem poder acessar as
diferentes estruturas do ambiente, bem como seus recursos, serviços e possíveis
estados externos dos outros agentes. Assim como a observação, o acesso às
estruturas é limitado ao contexto atual no qual o agente se encontra.
(vi). O ambiente pode definir regras para o sistema multiagente: regras podem
refletir as restrições impostas pelo domínio (como, por exemplo, mobilidade
na rede), ou as leis impostas pelo projetista (exemplo, limitações de acessos a
nós da rede). Elas podem restringir, também, o acesso a recursos ou serviços,
ou até determinar o resultado das interações dos agentes.
2.5
Arquiteturas de Agentes
A questão tratada nesta seção envolve a parte prática da construção de sistemas
de computadores que possuem as características de um sistema de agentes. Segundo
Ferreira (2002), uma arquitetura representa o projeto global, ou seja, a solução
computacional ao problema identificado. Desta forma, o objetivo da arquitetura é
mostrar quais as principais propriedades das partes que compõem o sistema e como
estas interagem.
Wooldridge e Jennings (1995) apresentam uma revisão das diversas abordagens
relacionadas às arquiteturas de agentes. Estas abordagem são resumidas a seguir.
2.5.1
Arquitetura Deliberativa
Uma definição para o termo agente deliberativo ou arquitetura agente deliberativa, segundo Wooldridge e Jennings (1995), inclui agentes que possuem uma
representação explícita, um modelo simbólico do mundo, no qual as decisões são
2.6
Considerações Finais
17
tomadas via raciocínio lógico, baseado em combinação de padrões e manipulação
simbólica.
Entretanto, esta abordagem apresenta algumas desvantagens, relacionadas ao
modelo simbólico que a compõe. Este modelo deve ser definido em uma forma na
qual realmente represente as informações e entidades do problema em questão, assim
como definir agentes que consigam inferir sobre estas informações.
Dada a complexidade dos problemas tratados, as desvantagens apresentadas têm
levado alguns pesquisadores a explorarem técnicas alternativas na construção de
agentes. Estas técnicas são descritas na subseções seguintes.
2.5.2
Arquitetura Reativa
Contrapondo-se à abordagem deliberativa, a abordagem reativa não inclui qualquer tipo de modelo simbólico do mundo e não usa raciocínio simbólico complexo.
Neste sentido, esta proposta baseia-se na idéia de que o agente pode desenvolver inteligência a partir de interações com seu ambiente, não necessitando de um modelo
pré-estabelecido.
Assim, segundo Brooks (1991), é possível obter comportamento reativo sem que
seja necessário uma representação e raciocínio explícito.
Considerando-se suas características, a abordagem reativa se tornou uma alternativa no desenvolvimento de agentes, reduzindo os problemas associados com a
complexidade de representação da abordagem deliberativa.
2.5.3
Arquitetura Híbrida
Muitos pesquisadores têm proposto a união das abordagens deliberativa e reativa,
sugerindo que nenhuma destas duas abordagens são adequadas para o desenvolvimento de agentes, quando utilizadas separadamente.
Desta forma, a arquitetura híbrida propõe o desenvolvimento de um subsistema
deliberativo, que possui uma representação simbólica, planeja e toma decisões da
maneira proposta pela Inteligência Artificial simbólica, e, em conjunto, um subsistema reativo, capaz de reagir a eventos que ocorrem no ambiente sem ocupar-se de
raciocínios complexos.
2.6
O foco deste capítulo está na sub-área da Inteligência Artificial Distribuída, que
envolve o desenvolvimento de Sistemas Multiagentes. Assim, alguns conceitos que
serão utilizados no restante deste trabalho são apresentados. Embora não haja
um consenso em relação ao conceito de agente, a capacidade de autonomia no seu
ambiente é considerada de fundamental importância para a definição de um agente.
Adicionalmente, em um sistema multiagente, como cada agente tem sua área de
atuação, a atuação em conjunto permite que o sistema tenha um maior conhecimento
do seu ambiente.
O ambiente e as interações são elementos importantes em um sistema multiagente
e podem exercer influência na forma de atuação dos agentes. Por fim, abordagens
relacionadas à arquiteturas de agentes são apresentadas.
2.6
18
Os conceitos apresentados aqui serão amplamente utilizados na definição da arquitetura proposta.
Capítulo 3
Metaheurísticas para Otimização
Combinatória
3.1
Introdução
A busca por técnicas eficientes para a solução de problemas complexos, não solucionados por metodologias clássicas, motivou a exploração de técnicas da inteligência
computacional. Os métodos metaheurísticos são exemplos destas técnicas utilizadas na resolução de problemas de otimização. Eles oferecem uma solução eficiente,
baseada no não-determinismo e na probabilidade (Milano e Roli, 2004).
Diferentemente dos algoritmos exatos, as metaheurísticas não garantem a solução
ótima do problema objeto de interesse, mas permitem, de outro lado, a determinação
de soluções de boa qualidade em um tempo computacional reduzido. Este fato
é particularmente vantajoso em problemas NP-difíceis, nos quais a aplicação de
métodos exatos pode, no pior caso, necessitar de tempo computacional exponencial
para encontrar a melhor solução.
Neste capítulo, são discutidos conceitos importantes para o estudo de Metaheurísticas, que serão utilizados nas seções seguintes. Ao mesmo tempo, é apresentada
uma descrição das principais metaheurísticas conhecidas, segundo a formulação de
interesse da abordagem aqui adotada.
3.2
Conceitos Importantes
O termo metaheurística foi inicialmente introduzido por Glover (1986) e deriva
de duas palavras gregas: “heuriskein”, que significa “buscar”, e “meta”, que significa
“em um nível superior”.
Uma conceituação de metaheurísticas apropriada aos interesses deste trabalho é
apresentada em Osman e Laporte (1996):
“Uma metaheurística é formalmente definida como um processo de geração iterativo, que guia uma heurística subordinada, pela combinação
de diferentes conceitos inteligentes para explorar e expandir o espaço de
busca. Estratégias de aprendizagem são usadas para estruturar informações com a finalidade de encontrar de forma eficiente soluções próximas
do ótimo.”
19
3.2
Conceitos Importantes
20
Blum e Roli (2003) apresentam propriedades fundamentais associadas às metaheurísticas:
(i). O objetivo é explorar eficientemente o espaço de busca, para encontrar soluções
próximas do ótimo;
(ii). Técnicas que constituem algoritmos de metaheurísticas variam de um simples
procedimento de busca local a processos complexos de aprendizagem;
(iii). As metaheurísticas devem incorporar mecanismos que evitem ficar presas em
áreas limitadas do espaço de busca;
(iv). Metaheurísticas não são voltadas para a solução de problemas específicos;
(v). Metaheurísticas podem utilizar experiências de busca (na forma de algum tipo
de memória, por exemplo) para guiar sua busca.
Assim, de forma objetiva, a principal finalidade das metaheurísticas é guiar a
exploração do espaço de busca utilizando diversas estratégias. Neste sentido, considerando um problema de otimização combinatória definido por um conjunto de
variáveis X = {x1 , x2 , . . . , xn }; o domínio deste conjunto; um conjunto de restrições
sobre as variáveis; e uma função objetivo, o espaço de busca é, então, o conjunto de
todas as soluções factíveis para o problema, ou seja, todas aquelas que satisfazem o
conjunto de restrições.
Adicionalmente, o espaço de busca de um problema de otimização combinatória
pode ser interpretado como um grafo, na forma da figura 3.1, no qual os nós são as
soluções (estados) e os arcos representam a relação de vizinhança entre as soluções
(Milano e Roli, 2004).
s3
s2
s1
s5
s4
Figura 3.1: Grafo que representa o espaço de busca e as relações entre as soluções.
Em seu processo de busca, metaheurísticas usualmente utilizam, como heurística
subordinada, métodos de busca local. Estes métodos buscam soluções através da
troca sistemática da solução corrente por uma melhor solução, dentro da vizinhança
(definida conforme algum critério) da solução corrente.
Uma solução vizinha, nos métodos de busca local, é determinada a partir de
uma função de vizinhança (estrutura de vizinhança). Uma função de vizinhança é
definida como um operador que recebe um estado s1 (figura 3.1) e o transforma em
outro estado s2 , pertencente à vizinhança de s1 (Milano e Roli, 2004).
Métodos de busca local utilizam soluções iniciais para começar seu processo
iterativo. Esta solução inicial é gerada a partir de métodos construtivos. Os métodos
3.3
Classificação
21
Função de Avaliação
construtivos tipicamente começam o seu processo com uma solução inicialmente
vazia e acrescentam elementos, a cada iteração, até que esta se encontre completa.
A principal diferença entre métodos heurísticos (construtivos e busca local) e
as metaheurísticas está na capacidade de escapar de ótimos locais, presente apenas
nas metaheurísticas. Para isto, as metaheurísticas utilizam diferentes estratégias
que permitem uma melhor exploração do espaço a partir de movimentos sobre as
diferentes vizinhanças do espaço de busca e procurando melhores ótimos locais.
Um ótimo local, em relação à vizinhança N , é uma solução s, cuja a função de
avaliação f(s) é menor do que todas as soluções pertencentes a N (s). Da mesma
forma, o ótimo global é uma solução s cuja a função de avaliação f(s) é menor do
que todas as soluções pertencentes ao espaço de busca (veja figura 3.2).
Otimo Local
Otimo Global
Espaco de Busca
Figura 3.2: Ótimo Global e Ótimo Local no espaço de busca.
Várias são as estratégias que permitem escapar de ótimos locais, como, por
exemplo, movimentos de piora da solução, a geração de novas soluções iniciais, o
uso de memória (baseada em decisões tomadas anteriormente ou em experiências de
busca), ou, até mesmo, decisões probabilísticas.
Entretanto, grande parte dos melhores resultados encontrados através de metaheurísticas para diversos problemas foram obtidos a partir de técnicas de hibridismo (Blum e Roli, 2003). O hibridismo é a combinação de uma ou mais metaheurísticas e/ou estratégias com o objetivo de melhorar o desempenho da busca.
A utilização de procedimentos de busca local por métodos como otimização por
colônia de formigas e algoritmos evolucionários é uma forma de hibridismo.
A identificação de elementos comuns nos algoritmos das metaheurísticas permite
um melhor conhecimento destas. Neste sentido, a classificação das metaheurísticas
existentes possibilita sua comparação e, assim, a identificação de suas similaridades
e diferenças. As principais classificações encontradas na literatura são descritas na
seção seguinte.
Uma revisão detalhada dos conceitos básicos envolvidos em metaheurísticas e as
principais classificações pode ser encontrada em Blum e Roli (2003).
3.3
Classificação
Diversas são as formas de classificação de metaheurísticas, cada uma de acordo
com um ponto de vista particular. Elas se diferem por características como funcio-
3.3
Classificação
22
namento, critério de escolha da solução inicial, uso ou não de memória, definição
da vizinhança, critério de parada, dentre outras. As classificações mais citadas nas
bibliografias recentes são descritas a seguir, seguindo a exposição feita por Birattari
et al. (2001) e Blum e Roli (2003).
Uma forma de diferenciar as metaheurísticas é com relação ao modo como percorrem o espaço de busca. Métodos de Trajetória seguem um caminho de busca
simples, correspondendo a um passeio fechado em uma vizinhança. Normalmente,
eles precisam permitir movimentos de piora da solução para escapar de ótimos locais. Alguns exemplos dessa classe de métodos são os métodos Simulated Annealing
e Busca Tabu. Métodos descontínuos permitem grandes saltos no gráfico de vizinhança. Metaheurísticas como Colônia de Formigas, Iterated Local Search (ILS),
GRASP, dentre outros, são exemplos destes métodos.
Uma outra característica que pode ser usada na classificação das metaheurísticas
é o número de soluções envolvidas no processo de busca. Os Métodos Baseados em
População utilizam um grupo de soluções ao mesmo tempo, realizando um processo
de busca que descreve a evolução de um conjunto de pontos do espaço. Colônia de
Formigas e Algoritmos Genéticos utilizam uma população de formigas e indivíduos,
respectivamente, em seu processo de busca. Por outro lado, métodos como Busca
Tabu, Simulated Annealing, Iterated Local Search e GRASP manipulam somente
uma solução em cada iteração do algoritmo.
O uso, ou não, de memória também pode ser usado na diferenciação das metaheurísticas. Memória é explicitamente usada em Busca Tabu; de forma indireta,
no algoritmo Colônia de Formigas, através de um tipo de memória adaptativa (via
feromônio); como também na população de indivíduos do Algoritmo Genético, que
pode ser interpretada como uma forma de experiência de busca recente. Estes são
exemplos de métodos que utilizam algum tipo de memória para evitar ciclagem ou
até mesmo para diversificar e intensificar características. De outro lado, Simulated
Annealing e GRASP são exemplos de métodos que não usam informação na forma de
memória para influenciar a direção da busca: apenas o estado corrente do processo
de busca é usado para determinar a próxima ação.
O número de estruturas de vizinhança usadas no processo de busca é uma característica que também classifica as metaheurísticas. Os métodos baseados em uma
única estrutura de vizinhança definem um único tipo de movimento permitido. Em
outras palavras, o método tem acesso apenas a uma região do espaço de busca durante o curso do algoritmo. A maioria dos algoritmos de busca local utiliza uma
única estrutura de vizinhança. Outras metaheurísticas, como Variable Neighborhood
Search (VNS), usam um conjunto de estruturas de vizinhança que dá a possibilidade
de diversificar a busca pela troca entre diferentes partes do espaço de busca. O método ILS, embora utilize uma segunda vizinhança somente para ejetar a busca para
outro ponto, quando um ótimo local é alcançado, também pode ser interpretado
como operando com várias vizinhanças.
Uma outra classificação de metaheurísticas é de acordo com a forma com que
usam a função objetivo do problema objeto de interesse. Alguns algoritmos modificam a função objetivo durante a busca, tornando-a uma função de avaliação de seu
desempenho ao longo de sua aplicação. Estes métodos introduzem penalidades, tentando incorporar informações coletadas no espaço de busca para escapar de ótimos
locais. O método Guided Local Search (GLS) é um exemplo dessa formulação. A
3.4
Principais Metaheurísticas
23
maioria dos métodos mantém a função objetivo, dada na representação do problema,
durante a busca.
A origem dos algoritmos também é usada como ponto de classificação. Existem
métodos que são inspirados na natureza, como Algoritmos Genéticos, Colônia de
Formigas, Simulated Annealing. Outros, no entanto, não possuem a formulação
associada a fenômenos da natureza, como por exemplo, ILS e Busca Tabu.
Todas estas classificações, contudo, apresentam algumas deficiências, em especial
quando do desenvolvimento de algoritmos híbridos envolvendo formulações e classes
diversas de metaheurísticas.
A classificação mais adequada aos interesses desse trabalho e que será, portanto,
aqui utilizada, é a relacionada ao número de soluções tratadas durante o processo
de busca. Esta escolha se deve à semelhança existente na estrutura dos métodos
baseados em um único ponto, o que facilita a proposição de um framework que os
associe. Já os métodos baseados em população, por outro lado, devem ser abordados com base em suas próprias particularidades e, desta forma, serão incluídos na
arquitetura proposta.
3.4
A descrição das metaheurísticas mais conhecidas e que serão tratadas neste trabalho é apresentada a seguir, sendo separadas segundo a tipologia de classificação
em termos do número de soluções envolvidas no processo de busca.
3.4.1
Métodos baseados em Um Único Ponto
3.4.1.1
Busca Local Básica
O método de Busca Local Básica é normalmente chamado de “melhoramento
iterativo”, visto que cada movimento só é executado se a solução resultante é melhor
que a solução corrente (Blum e Roli, 2003).
O pseudocódigo do Algoritmo de Busca Local é mostrado na figura 3.3. A
função Melhora(s, N (s)) depende da heurística de busca local utilizada, podendo
ser, por exemplo, um procedimento que explora a vizinhança da solução corrente
e seleciona a primeira solução que melhora o valor da função objetivo da solução
corrente (denominado, então, método de busca de Primeiro de Melhora), ou um
procedimento que realiza uma exploração exaustiva na vizinhança, retornando a
solução com o melhor valor da função objetivo (Método de Descida).
Algoritmo BuscaLocal(·)
1 inicio
2
s ← GeraSolucaoInicial(·);
3
repita
4
s ← Melhora(s, N (s));
5
ate nao conseguir melhorar s;
6 fim.
Figura 3.3: Pseudocódigo Algoritmo de Busca Local.
3.4
3.4.1.2
24
Simulated Annealing (SA)
A metaheurística Simulated Annealing (SA) foi originalmente proposta, em 1983,
por Kirkpatrick et al. (1983). A idéia principal se baseia na termodinâmica, simulando o resfriamento (recozimento) de um conjunto de átomos (Dowsland, 1993).
Este método utiliza um mecanismo estatístico, de tal modo que a probabilidade de
que um movimento de piora seja realizado decresce durante a busca.
Iniciando de uma solução inicial qualquer e em um processo iterativo, o método
SA gera, a cada iteração, um único vizinho aleatório da solução corrente s. O
movimento para a solução vizinha s será aceito caso a variação do valor da
função de avaliação utilizada for tal que = f (s ) − f (s) < 0. Caso ≤ 0, a
solução s candidata poderá ser aceita com uma probabilidade p(T ) = e−/T , sendo
o parâmetro T chamado de temperatura corrente, que regula a probabilidade de se
aceitar soluções de pior custo.
O parâmetro T é iniciado com um valor alto, que diminui gradualmente durante o processo de busca, de modo que o algoritmo venha a convergir a um simples
algoritmo de melhoramento iterativo. A figura 3.4 descreve o pseudocódigo da metaheurística Simulated Annealing.
Algoritmo SA(·)
1 inicio
2
s0 ← GeraSolucaoInicial(·);
3
T ← T0 ;
4
enquanto CriterioDeP arada nao for satisfeito
5
s ← GeraV izinho(s);
6
se f (s ) < f (s)
7
s ← s ;
8
senao
9
Aceita s como nova solucao, com probabilidade p(T, s , s);
10
fim se;
11
atualizaT emperatura(T );
12
fim enquanto;
13 fim.
Figura 3.4: Pseudocódigo Algoritmo Simulated Annealing.
3.4.1.3
Busca Tabu
Glover e Laguna (1998) descrevem a metaheurística Busca Tabu, na qual o conceito de histórico de busca é explicitamente usado. Neste método, movimentos de
piora da solução são permitidos (como mostra a figura 3.5) e, desta forma, o método
pode escapar de ótimos locais.
O processo de busca começa com uma solução inicial e, a cada iteração, explora
a vizinhança da solução corrente. O vizinho desta solução que será escolhido é
aquele que possuir o melhor valor de função objetivo, mesmo que este seja pior que
a solução corrente. Desta forma, a busca local é o ingrediente básico deste método.
3.4
25
Movimento
de Piora
Ótimo Local
Espaço de Busca
Figura 3.5: Funcionamento da Metaheurística Busca Tabu.
Para que a busca não entre em ciclagem ao aceitar movimentos de piora, uma
memória de curto prazo é usada para armazenar as últimas soluções visitadas e
as soluções proibidas. Esta memória é chamada de Lista Tabu e, normalmente, é
implementada usando ordem de inserção do tipo FIFO (First In, First Out), ou
seja, quando uma nova solução é adicionada à lista, a mais antiga sai. A figura 3.6
mostra o pseudocódigo de um algoritmo de Busca Tabu básico.
Algoritmo BuscaT abu(·)
1 inicio
2
s0 ← GeraSolucaoInicial(·);
3
InicializaListaBuscaT abu(LT );
4
5
MovimentosP ermitidos ← s pertencente a vizinhança que nao viola LT ;
6
s ← MelhorSolucao(MovimentosP ermitidos);
7
atualizaListaT abu(LT );
8
fim enquanto;
9 fim.
Figura 3.6: Pseudocódigo Algoritmo Busca Tabu.
3.4.1.4
GRASP
A metaheurística GRASP (Greedy Randomized Adaptive Search Procedure) é um
método de busca adaptativa gulosa e aleatória, que combina heurística construtiva
e busca local. Uma descrição detalhada desta metaheurística pode ser encontrada
em Feo e Resende (1995) e Pitsoulis e Resende (2002).
Este método é composto por dois elementos: um procedimento de construção de
solução gulosa aleatória e um procedimento de busca local.
No procedimento de construção, a cada iteração, uma lista de candidatos restrita é gerada com os melhores elementos. Em seguida, cada elemento a ser inserido
na solução é escolhido aleatoriamente, na lista de candidatos restrita. Esta heurística construtiva é chamada dinâmica (Blum e Roli, 2003), já que, a cada iteração,
3.4
26
os valores são atualizados, alterando-se a probabilidade de inserção dos elementos
durante a construção.
A busca local, fase iniciada logo após a construção da solução, tem o objetivo de
melhorar a solução encontrada na fase de construção.
A figura 3.7 apresenta um pseudo-código da metaheurística GRASP.
Algoritmo GRASP (·)
1 inicio
2 enquanto CriterioDeP arada nao for satisfeito
3
Constroi uma solucao s com um procedimento guloso aleatorio;
4
s ← BuscaLocal(s);
5
s∗ ← MelhorSolucao(s, s );
6 fim enquanto;
7 fim.
Figura 3.7: Pseudocódigo Algoritmo GRASP.
3.4.1.5
Variable Neighborhood Search
Proposto em Hasen e Mladenovic (1999) e Hasen e Mladenovic (2001), a metaheurística Variable Neighborhood Search (VNS) se caracteriza pela troca sistemática de vizinhança como estratégia para escapar de ótimos locais.
Esta metaheurística realiza, a cada iteração, uma busca local na solução corrente,
com o objetivo de refinar a solução. Em seguida, compara a solução encontrada na
busca local com a solução corrente; caso não obtenha melhora, faz a troca da função
de vizinhança.
A metodologia VNS não é um método de trajetória, já que, através da troca
de vizinhança, é capaz de explorar diferentes partes do espaço de busca, realizando
saltos durante a exploração. O pseudocódigo da metaheurística VNS é mostrado na
figura 3.8.
3.4.1.6
Iterated Local Search
A metaheurística Iterated Local Search (ILS), proposta por Lourenço et al. (2001),
constrói soluções iterativamente a partir de uma heurística embutida, realizando
modificações nas melhores soluções com o objetivo de escapar de ótimos locais e
diversificar a busca.
Para isso, o algoritmo ILS aplica metaheurísticas de busca local na solução inicial fornecida até que se obtenha um ótimo local; em seguida, perturba a solução
local e reinicia a aplicação da metodologia de busca local na solução perturbada,
como mostra a figura 3.9, para um problema de minimização. Na perturbação, o
método ILS aplica uma função de vizinhança diferente da utilizada na aplicação
da metaheurística de busca local, conseguindo, assim, transferir a busca para outra
região do espaço de busca.
O pseudocódigo da metaheurística ILS é mostrado na figura 3.10. A função
CriterioDeAceitacao(s , s , histrico) faz a escolha entre a solução encontrada na
3.4
27
Algoritmo V NS(·)
1 inicio
2
s ← GeraSolucaoInicial;
3
f uncaovizinhanca ← 1;
4
enquanto CriterioP arada nao for satisfeito
5
s ← GeraV izinho(s, f uncaovizinhanca);
6
s ← BuscaLocal(s );
7
se f (s ) < f (s )
8
s ← s ;
9
senao
10
T rocaF uncaoV izinhanca(f uncaovizinhanca);
11
fim se;
12
fim enquanto;
13 fim.
Figura 3.8: Pseudocódigo Algoritmo VNS.
Pertubação
s1
s
Busca Local
s2
Espaço de Busca
Figura 3.9: Funcionamento da Metaheurística ILS.
metodologia de busca local e a solução corrente, de acordo com o objetivo a ser perseguido (minimização ou maximização), podendo utilizar também, na sua tomada
de decisão, o histórico da busca.
Algoritmo ILS(·)
1 inicio
2
s0 ← GeraSolucaoInicial;
3
s∗ ← BuscaLocal(s0 );
4
repita
5
s ← P ertubao(s∗, historico);
6
s ← BuscaLocal(s );
7
s∗ ← CriterioDeAceitacao(s , s , historico);
8
ate CriterioDeP arada;
9 fim.
Figura 3.10: Pseudocódigo Algoritmo ILS.
3.4
3.4.2
Métodos Populacionais
3.4.2.1
Algoritmos Genéticos
28
A metaheurística Algoritmo Genético (Goldberg, 1989) é inspirada nos processos
naturais de evolução, em que os indivíduos com melhores características genéticas
possuem maiores possibilidades de sobrevivência e, em conseqüência, geram filhos
cada vez mais aptos.
Neste método, as soluções são representadas como cromossomos, que são os
indivíduos da população, e cada componente da solução é associado a um gene do
cromossomo.
O processo inicia com a geração de uma população inicial, obtida geralmente
de forma aleatória, seguida de um processo iterativo, que pode ser resumido em
duas fases principais (veja o pseudocódigo Algoritmo AG, mostrado na figura 3.11):
fase de reprodução, na qual alguns indivíduos são selecionados para operações de
recombinação e/ou mutação; fase de avaliação e definição da população sobrevivente.
Algoritmo AG(·)
1 inicio
2
t ← 0;
3
P (t) ← GeraP opulacaoInicial;
4
Avalia(P (t));
5
enquanto CriterioP arada nao for satisfeito
6
t ← t + 1;
7
P (t) ← GeraP opulacao(P (t − 1));
8
Avalia(P (t));
9
P opulacaoSobrevivente ← P (t);
10
fim enquanto;
11 fim.
Figura 3.11: Pseudocódigo Algoritmo AG.
Os operadores de recombinação realizam a combinação dos genes de dois cromossomos-pais para gerar cromossomos-filhos. Já os operadores de mutação modificam,
de forma aleatória, uma parte dos genes de cada cromossomo.
Através da função Avalia(P (t)), a população sobrevivente é escolhida, com base
em critérios como método da roleta, aleatório ou uma mistura destes dois critérios.
A possibilidade de um indivíduo menos apto ser selecionado é garantido com a
aleatoriedade, o que permite que o método escape de ótimos locais.
3.4.2.2
Ant Colony Optimization
A metaheurística Ant Colony Optimization (ACO) foi proposta em Dorigo (1992),
Dorigo et al. (1996) e Dorigo e Di Caro (1999). O algoritmo desta metodologia foi
inspirado na natureza, sendo baseado no comportamento real das formigas. O princípio utilizado é o de que as formigas, por meio de uma substância química chamada
feromônio, depositada ao longo do caminho, se comunicam indiretamente, para encontrar caminhos menores entre o ninho e uma fonte de alimento.
3.5
29
Inicialmente, as formigas movem-se aleatoriamente, até que encontrem uma fonte
de alimento. Enquanto caminham da fonte de alimento até o ninho, as formigas depositam o feromônio no solo. Quando uma formiga detecta um rastro previamente
deixado pode decidir, com alta probabilidade, segui-lo, reforçando assim o rastro
com seu próprio feromônio. Desta forma, este processo se caracteriza por ser autocatalítico, já que, quanto maior o número de formigas que seguem o rastro, mais
atrativo ele se torna.
No algoritmo ACO, as formigas fazem suas escolhas baseadas no rastro de feromônio do caminho, que depende diretamente do nível de feromônio presente, e na
atratividade, que expressa o quanto o movimento é desejável. Assim, a escolha do
caminho é probabilística, sendo altamente influenciada pela intensidade de feromônio. O método de decisão baseado em feromônio pode, também, permitir o desvio
aleatório da melhor solução corrente, o que possibilita escapar de ótimos locais.
Um pseudocódigo da metaheurística Ant Colony Optimization é apresentado na
figura 3.12:
Algoritmo ACO(·)
1 inicio
2
3
para cada formiga (ate m formigas)
3
s ← ControiSolucao(RastroF eromonio);
4
s ← BuscaLocal(s);
5
Seleciona melhor solucao;
6
Atualiza rastro de feromonio;
7
fim para;
8
fim enquanto;
9fim.
Figura 3.12: Pseudocódigo Algoritmo ACO.
3.5
Este capítulo apresenta conceitos de termos importantes, amplamente utilizados em
metaheurísticas, e que serão utilizados no decorrer deste trabalho. As formas de
classificação aqui apresentadas permitem estabelecer diferenças e semelhanças entre
as principais metaheurísticas, o que será de fundamental importância na proposição
da arquitetura. Desta forma, as metaheurísticas que são tratadas neste trabalho,
são descritas de acordo com a classificação que atende os propósitos deste trabalho.
Capítulo 4
Trabalhos Correlatos
4.1
Introdução
Diversas arquiteturas e frameworks têm sido, recentemente, propostos para o tratamento de métodos de otimização combinatória. Muitos destes trabalhos utilizam
o paradigma orientado a objetos para definir uma estrutura genérica, que permite a
utilização destes métodos na solução de problemas de otimização. Outros trabalhos
utilizam a abordagem multiagente neste mesmo sentido.
Entretanto, o escopo destes trabalhos, normalmente, se limita a uma abordagem
específica, como por exemplo, um framework para algoritmos de busca local (Andreatta et al., 1998) ou uma arquitetura de agentes para a solução do Problema de
Roteamento de Veículos (Thangiah et al., 2001).
Este capítulo se concentra em uma revisão da literatura relacionada à utilização
das abordagens multiagente e orientadas a objeto no tratamento de metaheurísticas.
4.2
Asynchronous Teams
Em Talukdar e Souza (1990), é proposta uma arquitetura multiagente para a
solução de problemas, denominada Asynchronous Teams (A-Teams), na qual os
agentes são autônomos e cooperam entre si, modificando as soluções uns dos outros.
A arquitetura A-Teams tem sido usada na solução de diversos problemas complexos, envolvendo áreas como, por exemplo, projetos, diagnósticos, controle e otimização. Desta forma, vários trabalhos que implementam este formalismo podem
ser citados: Passos e Fonseca (2005) utilizam A-teams na solução de problemas de
seqüenciamento de produção; em Lukin et al. (1997), estes são usados no problema
de tratamento de dados para ressonância da coluna vertebral; em Chen (1992) e
Avila-Abascal e Talukdar (1996) o método é aplicado no diagnóstico de falhas em
redes elétricas; em Gorti et al. (1996), é aplicado a problemas de satisfação de restrições; na solução do Problema do Caixeiro Viajante, em de Souza (1993); Chen
et al. (1993) utiliza-o na programação de horários de trabalho em lojas.
A arquitetura proposta é formada por um conjunto de agentes autônomos e
um conjunto de memórias interconectadas, formando uma rede cíclica, isto é, as
soluções circulam continuamente nas memórias (Talukdar et al., 1998). Um ATeams pode ser representado na forma de um grafo direcionado (veja Figura 4.1),
30
4.3
A-Teams
31
em que cada nó representa uma memória de sobreposição e cada arco representa um
agente autônomo. As memórias acumulam populações de soluções que variam no
tempo, já que novos membros são continuamente adicionados e os membros mais
antigos são apagados.
C1
C3
M1
D1
C4
D2
C2
C5
M2
Figura 4.1: Asyncronous Teams: C1-C5 são agentes construtores; D1-D2 são agentes
destrutores; e M1-M2 são memórias. Fonte: Talukdar e Souza (1990)
Os agentes da arquitetura são divididos em dois tipos:
• Agentes Construtores: adicionam soluções às memórias a partir do processo
de cópia e modificação de soluções mais antigas para, em seguida, incluí-las
como novas soluções;
• Agentes Destruidores: examinam a população e apagam as soluções que não
deveriam estar lá.
Cada agente encapsula um método particular de solução do problema, que age
modificando as soluções existentes (Passos e Fonseca, 2005).
A-Teams cooperam através do compartilhamento das populações de soluções
candidatas armazenadas nas memórias. No entanto, como os agentes são autônomos,
esta cooperação é assíncrona, ou seja, nenhum agente pode ser forçado a esperar
resultados de outro agente.
Passos e Fonseca (2005) relacionam as principais características de um A-Teams:
- Autonomia dos agentes: os agentes são independentes uns dos outros;
- Fluxo de dados cíclico: acontece através da construção e destruição de
soluções e permite a cooperação entre os agentes pelo compartilhamento de
resultados;
- Comunicação Assíncrona: os agentes acessam as memórias sem que exista
uma sincronização entre eles.
Assim, todas as formas de comunicação disponíveis nesta arquitetura são representadas pelo fluxo de dados, ou seja, as possibilidades de interação dos agentes da
proposta se limitam à troca de resultados entre estes, através das memórias. Neste
sentido, a cooperação também se restringe à troca de soluções entre os agentes.
4.3
4.3
AGENT-DOSS
32
AGENT-DOSS
Thangiah et al. (2001) apresentam uma arquiteturas de agentes para a solução de
Problemas de Roteamento de Veículos (PRV). Com o objetivo de reduzir a complexidade do problema a ser solucionado através da divisão deste em problemas menores,
este artigo propõe a solução desta classe de problemas por meio da estratégia de
busca distribuída.
Segundo os autores, os principais objetivos da arquitetura são: (1) resolver o PRV
de maneira distribuída; (2) resolver o problema usando múltiplos computadores em
rede, sem requerer do usuário a tarefa de gerenciar o processo de busca; (3) introduzir
uma arquitetura agente flexível, que tenha a capacidade de integrar Metaheurísticas
para resolver variantes do PRV com o mínimo de mudanças nos algoritmos e no
sistema.
A arquitetura proposta permite, também, resolver variantes complexas do PRV
clássico, com o mínimo de alteração no sistema, assim como a integração de estratégias de busca, como Algoritmos Genéticos, Busca Tabu, Simulated Annealing, entre
outras.
O sistema de agentes implementado neste trabalho foi nomeado pelos autores
como AGENT-DOSS, já que utiliza um método chamado DOSS. Tal método, segundo Thangiah et al. (2001), consiste na habilidade de um sistema conduzir uma
busca usando um ou mais sistemas de computadores heterogêneos em uma rede distribuída, com cada nó sendo capaz de selecionar autonomamente uma estratégia de
busca que maximize seu desempenho local.
Para a solução do PRV, a partir da idéia de agentes trabalhando em conjunto, a
arquitetura apresenta um princípio de negociação e uma estrutura de coordenação
para suporte. O princípio de negociação, através do processo de leilão (auctioning
process), possibilita a interação dos diversos agentes, enquanto a estrutura de coordenação permite aos agentes cooperar e coordenar para resolver o PRV.
Neste sentido, o AGENT-DOSS é formado por dois agentes principais:
(i) Agente Leiloeiro (Auctioneer Agent): responsável por anunciar os clientes disponíveis aos agentes veículos e, assim, receber as ofertas destes. Estas
ofertas são avaliadas, com o objetivo de encontrar o agente veículo com menor
custo, e nomear o cliente para o veículo definido.
(ii) Agente Veículo (Vehicle Agent): são criados até que todos os clientes
submetidos pelo Agente Leiloeiro tenham sido alocados em um Agente Veículo.
Este agente é responsável por avaliar o custo de inserção do novo cliente (que
está sendo ofertado pelo Agente Leiloeiro); enviar este custo para o Agente
Leiloeiro (sua oferta); e, se nomeado por este, aceitar o cliente em sua rota.
O cliente só será aceito pelo Agente Veículo se as restrições de capacidade e
distância não forem violadas. O método Clarke-Wright é usado para avaliar o
custo de inserção do novo cliente na rota do Agente Veículo.
Assim, o processo de leilão consiste da apresentação do novo cliente aos Agentes
Veículos e, conseqüentemente, o retorno, ao Agente Leiloeiro, das ofertas relacionadas à inserção deste cliente nas rotas. Uma vez que esta tarefa está completa,
os Agentes Veículos realizam trocas de mensagens com o objetivo de minimizar
4.4
Coal-VRP
33
a distância viajada por cada um deles. Estas trocas são similares ao movimento
inter-rota, em que um ou dois clientes são trocados entre dois veículos.
O artigo apresenta, para validar sua proposta, aplicações do AGENT-DOSS à
solução do PRV clássico e à solução do PRV multidepósito. É mostrado que a arquitetura proposta não requer nenhuma alteração quando aplicada a cada um destes
problemas, pois os Agentes Veículos trabalham de forma independente e podem,
portanto, iniciar em qualquer depósito.
Adicionalmente, a arquitetura permite a integração de métodos metaheurísticos
no que os autores denominam de nível de agente, isto é, cada Agente Veículo pode
ter um algoritmo de busca que é adequado para resolver o seu subproblema.
Contudo, embora a arquitetura seja capaz de solucionar as diversas variantes
do PRV, ela está restrita a esta classe de problema. Isto porque seus agentes são
altamente especializados, tendo suas habilidades limitadas ao tratamento de clientes
e rotas (veículos), próprios desta classe de problemas.
4.4
Coal-VRP
Em Kefi e Ghedira (2004) é apresentado um modelo multiagente, baseado em
coalizão, para a solução do Problema de Roteamento de Veículos com Janela de
Tempo.
Este artigo foca em um modelo particular, chamado Coal-VRP, que é baseado
em formação de coalizão. O Coal-VRP é um sistema multiagente que consiste na
divisão dos agentes em grupos chamados coalizões. Estes agentes são capazes de
comunicar e negociar uns com os outros.
O objetivo do Coal-VRP é determinar um conjunto final de rotas, dado um
conjunto de pedidos recebidos de clientes distribuídos geograficamente. O sistema
Coal-VRP é formado por dois tipos de agentes:
(i) Agente Interface: responsável pela inicialização do processo de solução, a
ligação dos seus passos e a detecção do seu fim.
(ii) Agente Cliente: corresponde a um dado cliente e seu interesse é ser atendido
em uma rota com o menor custo, enquanto são respeitadas as restrições de
capacidade e janela de tempo.
Uma coalizão, neste modelo, é uma lista ordenada de Agentes Clientes que corresponde a uma rota, começando no depósito, servindo todos os clientes associados
e retornando ao depósito.
O processo de solução do Coal-VRP é dividido em três passos:
(i) Formação distribuída de um grafo acíclico e direto de clientes, chamado de
grafo de relações. A relação entre os Agentes Clientes é baseada em dois
critérios: janela de tempo e heurística de vizinhança espacial.
(ii) Cada Agente Cliente constrói uma coalizão em relação à restrição de capacidade. Ao final deste passo, todos os Agentes Clientes têm uma lista de
coalizões completa e ordenada de acordo com o critério de preferência.
4.6
DyCoal
34
(iii) A coalizão que é a melhor para cada Agente Cliente é determinada. As coalizões escolhidas são armazenadas, e a configuração de coalizões é gradualmente
atingida. Um protocolo de comunicação garante um acordo entre os Agentes Clientes. Ao fim deste passo, as coalizões armazenadas são separadas, de
forma que cada Agente Cliente pertence a exatamente uma coalizão.
Entretanto, este modelo apresenta algumas desvantagens, descritas em Boudali
et al. (2004), e que são mencionadas na seção seguinte.
4.5
DyCoal-VRP
O modelo Coal-VRP expresso na seção 4.4 apresenta algumas desvantagens relacionadas à complexidade espacial e temporal. Neste sentido, Boudali et al. (2004)
propõem uma nova versão do modelo, chamado DyCoal-VRP (Dynamic generation of Coalition for solving a VRP), buscando superar as desvantagens e manter a
qualidade das soluções.
A principal desvantagem do modelo Coal-VRP é encontrada no segundo passo,
já que o tamanho da lista de coalizão é exponencial em relação ao número de clientes
do problema.
O modelo DyCoal-VRP propõe eliminar este passo do processo de solução, correspondente à construção da lista de coalizões, e introduzir uma geração dinâmica
de coalizões.
Desta forma, o novo processo de solução é definido por apenas dois dos passos
descritos acima:
(i) A formação distribuída do grafo de relações, da mesma forma que o ocorrido
no modelo Coal-VRP.
(ii) A determinação da melhor coalizão para cada Cliente (corresponde a união
de dois passos do modelo anterior), sendo que, em lugar de gerar uma lista
com todas as possíveis coalizões para cada agente, no DyCoal-VRP é feita
uma geração dinâmica de coalizões. Como no modelo anterior, em algum
instante, todos os Agentes Clientes têm apenas uma coalizão relacionada. Para
a geração dinâmica de coalizões, o protocolo de negociação foi modificado.
Contudo, deve-se enfatizar que ambos os modelos, Coal-VRP e DyCoal-VRP,
podem ser utilizados apenas na solução do PRVJT, possuindo, assim como na proposta apresentada na seção 4.3, agentes especializados em um tipo específico de
problema específico.
Desta forma, em ambas as propostas, a modificação ou adição de novos métodos
fica restrita, senão impossibilitada, assim como sua aplicação a outros problemas de
otimização combinatória.
4.6
Hiperheurísticas
A metodologia de Hiperheurística pode ser vista como uma heurística que escolhe, dentre diversas heurísticas de baixo nível, qual será aplicada para o auxílio à
4.7
Metaheurísticas Cooperativas
35
solução de um dado problema de otimização. Assim, em cada ponto de decisão, a
hiperheurística deve decidir qual a heurística de baixo nível será aplicada na seqüência do procedimento de solução. A escolha da próxima heurística de baixo nível a ser
aplicada é feita em relação à heurística utilizada previamente e à região do espaço
de busca corrente, tornando esta escolha dinâmica (Gras et al., 2003).
As pesquisas em Hiperheurísticas são voltadas para o desenvolvimento de “heurísticas para escolher heurísticas” em uma tentativa de aumentar o nível de generalidade na solução de problemas de otimização (Burke et al., 2005). Este crescimento
no nível de generalidade pode suportar uma nova geração de sistemas de apoio a
decisão que são aplicáveis a um extenso número de problemas, ao contrário dos
sistemas atuais, que tendem a focar no tratamento de sistemas feitos sob medida.
Pode-se atingir isto pelo uso de um framework com uma construção em um nível
de abstração. Para tal, um conjunto de heurísticas de “baixo nível” é desenvolvido,
interage com uma dada solução para um problema, e explora a vizinhança no espaço
de solução. As hiperheurísticas, então, consistem em métodos de busca de alto
nível, que gerenciam “a escolha de qual heurística de baixo nível deve ser aplicada
em um dado tempo, dependendo das características da região do espaço de solução
em exploração”.
As pesquisas recentes no tema focam na exploração do uso de técnicas e de
metaheurísticas existentes como hiperheurísticas. Neste sentido, alguns trabalhos
são apresentados abaixo, possibilitando uma melhor compreensão do funcionamento
das hiperheurísticas.
Uma hiperheurística Busca Tabu é proposta em Burke et al. (2003), na qual é
mantida uma lista tabu de heurísticas, que impede que certas heurísticas sejam escolhidas em determinados momentos da busca. Nesta proposta, heurísticas competem
usando regras baseadas no princípio de aprendizagem reforçada.
Burke et al. (2005) discutem sobre a utilização do Algoritmo de Otimização por
Colônia de Formigas como uma hiperheurística. Nesta proposta, cada vértice de
uma rede representa uma heurística, enquanto os arcos direcionais, existentes entre
as heurísticas, indicam a possibilidade de se aplicar imediatamente heurísticas sobre
a outra. Em seguida, um certo número de formigas é criado, cada qual representando
um agente hiperheurística (fornecido com uma solução inicial no espaço de solução)
e tem acesso à heurísticas e à funções de avaliação. Estas formigas são espalhadas
uniformemente entre os vértices do grafo.
Desta forma, na hiperheurística proposta, cada formiga deve construir uma
seqüência de heurísticas através do grafo. O próximo vértice a ser visitado é escolhido com base na quantidade de feromônio nos arcos, e a formiga aplica a heurística
representada pelo vértice em sua solução corrente. Após cada formiga visitar certo
número de vértices, elas param e analisam o caminho obtido e depositam uma quantidade de feromônio em cada arco, de acordo com o melhoramento da qualidade da
solução durante o percurso.
4.7
Metaheurísticas Cooperativas
O interesse dessa abordagem consiste em executar diferentes métodos de busca
de forma paralela, de modo tal que estes troquem informações, coletadas em uma
4.8
MAGMA
36
região do espaço de busca previamente explorada. Assim, esta abordagem tem sido
crescentemente utilizada para problemas de otimização de difícil solução e tem se
mostrado, segundo seus proponentes, mais rápida na solução de problemas com
estas características, ao mesmo tempo que melhorado a robustez e a qualidade das
soluções encontradas (Bouthilliera e Crainic, 2005).
O paralelismo é usado em metaheurísticas cooperativas com o objetivo de reduzir o tempo de execução do algoritmo de busca, assim como para melhorar sua
efetividade e robustez. Isso é possível através da cooperação existente entre as metaheurísticas, que realizam a busca paralelamente.
Dentre os trabalhos utilizando esta abordagem, é importante citar os que se
seguem. Em Vallada e Ruiz (2007), a metodologia de metaheurística cooperativa,
na forma de algoritmos genéticos cooperativos, é usada no problema de programação de flowshop. Esta proposta busca resolver o problema, dividindo uma tarefa
em várias partes independentes e resolvendo-as simultaneamente, usando múltiplos
processadores ou computadores.
Uma descrição de metaheurísticas cooperativas, assim como uma classificação
dependente da natureza da cooperação é apresentada em Gras et al. (2003). Os
conceitos apresentados são aplicados a problemas na área de proteômica, incluindo
identificação automática de proteínas, inferência de motivo biológico e alinhamento
de seqüências múltiplas. Várias aplicações são apresentadas utilizando métodos
baseados na cooperação, sendo comparados com abordagem clássicas. Os autores
enfatizam, neste trabalho, a importância da combinação de métodos para maximizar
o ganho de suas características específicas para problemas de estrutura complexa.
4.8
MAGMA (MultiAGent Metaheuristics Architecture)
A Arquitetura MAGMA (MultiAGent Metaheuristics Architecture), apresentada
por Milano e Roli (2004), utiliza a perspectiva multiagente na definição de um
framework, na qual uma metaheurística pode ser vista como o resultado da interação
entre os diversos agentes da arquitetura.
Nesta arquitetura, diferentes agentes atuam em multi-níveis, sendo que cada
um dos níveis corresponde a um grau de abstração e possui um ou mais agentes
especializados.
A arquitetura MAGMA permite a interação dos agentes e a comunicação entre
quaisquer dois níveis. Os níveis da arquitetura MAGMA (figura 4.2) são:
- Nível 0: os agentes deste nível são responsáveis por produzir soluções iniciais
e fornecer uma solução factível para o nível superior; estes agentes podem
explorar estratégias como inicialização aleatória, construção gulosa, construção
probabilística, entre outras.
- Nível 1: estes agentes buscam melhorar a solução fornecida pelo nível 0, a
partir da exploração do espaço de busca com algoritmos de busca local.
- Nível 2: os agentes, neste nível, têm a tarefa de guiar a busca para soluções
mais promissoras, permitindo escapar de ótimos locais.
4.8
MAGMA
37
- Nível 3: os agentes devem coordenar todo o processo de busca, isto é, coordenar o comportamento de todos os agentes dos níveis abaixo deste.
Nível 3
NÍVEL DE COORDENAÇÃO
5
Nível 2
AGENTE DE ESTRATÉGIA
3
Nível 1
6
4
MELHORADORES DE SOLUÇÃO
7
1
Nível 0
2
CONSTRUTORES DE SOLUÇÃO
Figura 4.2: MAGMA - Arquitetura Multi-Níveis para metaheurísticas. Fonte: Milano e Roli (2004)
Cabe ressaltar que a arquitetura MAGMA é uma arquitetura hierárquica, onde
agentes de um nível subordinam as ações dos agentes do nível inferior e, por outro
lado, ficam subordinados às ações dos agentes do nível superior. Assim sendo, os
agentes não são, propriamente autônomos, face à cadeia de subordinação.
Ao contrário dos outros trabalhos aqui apresentados, a arquitetura MAGMA se
mostra uma estrutura mais geral, possibilitando a adição de qualquer metaheurística,
e não se prende a um problema específico.
Em Milano e Roli (2004), algumas especializações da arquitetura MAGMA são
apresentadas, com o objetivo de demonstrar como metaheurísticas conhecidas podem ser representadas pelo framework proposto. Aqui, são apresentadas duas destas
especializações, exemplificando a utilização desta arquitetura.
Primeiro, a arquitetura MAGMA é utilizada para descrever a metaheurística
GRASP (Feo e Resende, 1995), descrita na seção 3.4.1.4. Nesta especialização,
mostrada na figura 4.3, são utilizados os seguintes níveis:
• Nível 0: gera a solução inicial, com uma heurística de construção gulosa aleatória;
• Nível 1: melhora a solução inicial encontrada pelo nível inferior, com um
algoritmo de busca local (a escolha do algoritmo depende do problema a ser
tratado);
• Nível 2: armazena a melhor solução encontrada na busca local.
A segunda especialização da arquitetura utiliza o método ACO (Ant Colony
Optimization) (Dorigo et al., 1996). De acordo com o algoritmo ACO genérico, os
níveis da arquitetura, para esta especialização, são definidos da seguinte forma:
4.9
MAGMA
38
Nível 2
ARMAZENA A MELHOR
SOLUÇÃO
Nível 1
BUSCA LOCAL
Nível 0
CONSTRUÇÃO GULOSA
ALEATÓRIA
Figura 4.3: Especialização da arquitetura MAGMA para GRASP. Fonte: Milano e
Roli (2004)
• Nível 0: constrói a solução inicial, utilizando um procedimento construtivo
probabilístico, baseado no rastro de feromônio;
• Nível 1: implementa algum método de busca local para melhorar a solução;
• Nível 2: armazena a melhor solução e atualiza os níveis de feromônio.
Nível 2
ATUALIZA FEROMÔNIO
Nível 1
BUSCA LOCAL
Nível 0
CONSTRUÇÃO BASEADA
EM FEROMÔNIO
Figura 4.4: Especialização da arquitetura MAGMA para ACO. Fonte: Milano e Roli
(2004)
É importante ressaltar que uma metaheurística, nesta proposta, não é um agente
isolado agindo autonomamente, mas surge da ação cooperada de diferentes agentes
atuando nos vários níveis de abstração da arquitetura.
O ambiente que o agente percebe na arquitetura MAGMA é bem simples, correspondendo apenas ao conjunto de agentes com os quais ele pode se comunicar.
Os agentes são definidos por tuplas T =< M, S >, em que S é a estratégia usada
pelo agente e M é o modelo de problema. Assim, todos os agentes, de todos os
níveis da arquitetura, devem possuir uma definição do modelo do problema. Da
forma como é proposta, então, a arquitetura está fortemente ligada ao problema a
ser tratado, já que, para que dois problemas diferentes sejam solucionados, devem
ser feitas alterações nos agentes, no que diz respeito à definição do problema.
4.10
4.9
FGAS
39
FGAS (Fine-Grained Agents System )
Uma abordagem multiagente para a solução de problemas de otimização que
possuem uma forte estrutura combinatória, em especial o chamado problema de
empacotamento, foi proposta por Lau e Wang (2005).
Neste trabalho, agentes racionais agem de forma colaborativa e competitiva no
projeto do FGAS (Fine-Grained Agents System). O FGAS é definido por uma 4tupla T =< AA, CA, SA, L >, na qual:
(i) AA - Agente de Arbitragem (Arbitration Agent): é um agente que serve
como fornecedor de informações globais do ambiente e controla a concorrência
entre os subagentes;
(ii) CA - Agente Restrição (Constraint Agent ): é um conjunto de agentes
restrições que atuam como consultores, fornecendo informações para a tomada
de decisão dos subagentes;
(iii) SA - SubAgentes (Subagents): é um conjunto de subagentes que pode
ser expresso como {sA1 , sA2 , . . . , sAn }, que adotam uma abordagem de busca
local, através de movimentos (vizinhança), em que o resultado destes movimentos pode mudar o estado interno dos subagentes e melhorar o valor da
função objetivo. Exemplo de um subagente: uma “caixa”, com capacidade
predefinida, no problema de empacotamento; e
(iv) L: é o comportamento local do agente.
A interação entre os agentes ocorre quando os SA’s se encontram com opiniões
diferentes na busca do melhor movimento. Este evento é designado como “conflito”
e, quando ele ocorre, os SA’s começam a negociar uns com os outros. Desta forma,
os agentes resolverão estes conflitos selecionando valores não apenas para satisfazer
a restrição do problema, mas, também, para maximizar a flexibilidade de escolha de
valores do outro agente (Lau e Wang, 2005).
Adicionalmente, os FGAS implementam, para cada movimento, um cálculo de
expectativa futura, sendo que o movimento que tiver a melhor expectativa será
escolhido.
Entretanto, embora esta proposta envolva vários subagentes cooperando na busca
da solução, estes são voltados para métodos de busca local e para a solução de uma
classe de problemas específica.
4.10
MAA-VRPTW
Leong e Liu (2006) propõem um novo algoritmo que combina a abordagem multiagente com heurísticas de busca local, para evitar que, na fase de otimização das
rotas, a solução corrente fique facilmente presa em ótimos locais. Da mesma forma
que outros trabalhos já discutidos aqui, o algoritmo descrito nesta seção também
é especializado na solução do Problema de Roteamento de Veículos com Janela de
Tempo (PRVJT).
Nesta proposta, nomeada como Multi-Agent Algorithm for the VRPTW (MAAVRPTW ) ou Algoritmo Multiagente para o PRVJT, cada entidade no PRVJT é
4.10
MAA-VRPTW
40
tratada como um agente e o PRVJT, como um todo, é representado pelo grupo
de interações destes agentes. Cada agente tem um objetivo local e pode desempenhar um conjunto de operações/movimentos para mudar seu estado; movimentar
para seus objetivos individuais; afetar o ambiente; e modificar os estados de outros
agentes. Desta forma, o algoritmo é composto pelos seguintes agentes:
(i) Agente Cliente: este agente troca informações com os outros Agentes Clientes e tem como objetivo obter o seu atendimento assim que possível e minimizar
seu tempo de espera.
(ii) Agente Rota: cada rota (ou veículo) conhece as informações sobre os clientes
presentes em suas rotas e trocam informações com outras rotas. O objetivo
do Agente Rota é maximizar o uso de sua capacidade e minimizar a distância
viajada.
(iii) Agente Planejador: o planejador global (simbolizado aqui pelo depósito)
está em todas as rotas e conhece todas as informações dos clientes que ele
precisa atender. Este agente tem uma visão geral do estado corrente e é capaz
de coordenar as operações dos clientes e das rotas. O seu objetivo é minimizar
o número de rotas e a distância total viajada em todas as rotas.
Este algoritmo utiliza a heurística PFIH (Push Forward Insertion Heuristic)
(Solomon, 1987) para obter a solução inicial. Esta heurística insere repetidamente o
melhor cliente factível na rota corrente parcial. O melhor cliente factível é definido
por ser aquele com o menor custo calculado pela função de custo do problema.
Após a construção da solução inicial, o algoritmo proposto utiliza a abordagem
multiagente para otimizar as rotas. Neste sentido, cada agente tem um conjunto
de operações que têm o objetivo de melhorar seu próprio objetivo local, enquanto
movem o estado da solução global para soluções globais melhores. Adicionalmente,
o agente planejador também realiza, periodicamente, movimentos globais, que têm
o objetivo de melhorar o estado da solução global
Assim, o MAA-VRPTW trabalha na forma como descrita na Figura 4.5.
Inicializar os
dados usando
solução PFIH
Ambiente
Agente
Agente
Ativar
Agente
Agente
Sistema Multiagente
Principal
Figura 4.5: Algoritmo Multiagente para o PRVJT. Fonte: Leong e Liu (2006)
4.11
Um Framework Orientado a Objeto de Busca Local
41
Nas interações que acontecem no sistema multiagente proposto, o Agente Planejador toma o papel de controlador geral de todo sistema, enquanto os demais
agentes podem se comunicar com ele e com os outros. A Figura 4.6 mostra como
essas interações acontecem.
Interações
entre Agentes
Agente
Cliente
Agente
Planejador
Agente
Cliente
Agente
Rota
Agente
Rota
Figura 4.6: Interações entre agentes em MAA-VRPTW. Fonte: Leong e Liu (2006)
O MAA-VRPTW foi implementado em C++, utilizando um simulador de eventos discreto para simular a característica distribuída. Assim, o sistema não foi implementado usando um sistema multiagente distribuído. Os testes realizados para
validação da proposta foram realizados utilizando o conjunto de dados propostos em
Solomon (1987).
Nesta proposta, a abordagem multiagente é utilizada apenas na definição de
movimentos de vizinhança (entre as rotas), ou seja, somente heurísticas de busca
local podem ser implementadas com este sistema.
4.11
Um Framework Orientado a Objeto para Busca Local
Um framework orientado a objetos para heurísticas de busca local, denominado
Buscador de Vizinho (NeighborSearcher Framework ), é apresentado em Andreatta
et al. (1998). Neste framework, são modelados diferentes aspectos, envolvidos nas
heurísticas de busca local, tais como algoritmos para construção de soluções iniciais;
métodos para geração de vizinhança; e critérios de seleção de movimento.
A estrutura do framework, assim como suas classes e as relações envolvidas, são
apresentadas na figura 4.7 e descritos a seguir:
• Cliente: contém a instância do problema a ser solucionado. Contém também
os dados para criar a Estratégia de Busca que será usada para resolver o
problema.
• Solução: encapsula a representação de uma solução para o problema e define
a interface que permite ao algoritmo construir e modificar soluções.
• Estratégia de Busca: constrói e inicia os algoritmos da Estratégia de Construção e da Busca Local.
4.11
Um Framework Orientado a Objeto de Busca Local
42
Lista_encontrada
Cliente
Estratégia
Lista_construtores
Lista_candidatos
selecionados
Estratégia
de Busca
Lista_buscadores
Lista
Lista_inicial encontada
Estratégia
de Construção
Busca
Local
Incremento
Lista_candidatos
selecionados
Movimento
Solução
Modelo de
Construção
Modelo de
Incremento
Modelo de
Busca
Modelo de
Movimento
Figura 4.7: O Framework Buscador de Vizinhos. Fonte: Andreatta et al. (1998)
• Estratégia de Construção: encapsula os algoritmos construtivos. Faz modificações na solução baseado no Modelo de Incremento.
• Busca Local: encapsula algoritmos de busca local. Faz modificações na solução, baseado no Modelo de Movimento.
• Incremento: grupos de dados necessários para uma modificação da representação interna da solução para os algoritmos construtivos.
• Movimento: grupo de dados necessários para uma modificação da representação interna de uma solução para os algoritmos de busca local.
• Modelo de Incremento: define o modelo de incremento.
• Modelo de Movimento: define o modelo de movimento.
O processo de interação e colaboração deste framework pode ser sintetizado da
seguinte forma: o cliente delega a tarefa de encontrar uma Solução à Estratégia de
4.12
43
Busca. Esta estratégia é composta pelo menos por uma Estratégia de Construção e
uma Busca Local. A Estratégia de Construção produz uma Solução inicial através de
Incrementos e a Busca Local melhora a Solução através de Movimentos sucessivos.
Estes Incrementos e movimentos determinam as relações de vizinhança, que são inicialmente fornecidas pelo Cliente. A implementação destas vizinhanças é delegada
pela Solução a seu Modelo de Incremento (Construção) e ao seu Modelo de Movimento (Busca Local). Estes Modelos, de Incremento e Movimento, podem mudar
em tempo de execução, refletindo o uso de uma vizinhança dinâmica ou Estratégias
de Construção que utilizam vários tipos de incremento.
Assim como a grande maioria dos frameworks propostos para métodos de otimização, o principal objetivo do framework apresentado em Andreatta et al. (1998)
consiste na sua utilização para o desenvolvimento e comparação de diferentes heurísticas para o mesmo problema, por outro lado, também, como é freqüentemente
necessário, deve-se experimentar estes problemas com diferentes estratégias e parâmetros. Entretanto, o framework permite a comparação apenas de métodos de
busca local, não sendo possível utilizá-lo com outras heurísticas.
4.12
Um framework orientado a objetos para busca local multiobjetivo é apresentado
por Claro e Sousa (2001).
Problemas de otimização combinatória com múltiplos objetivos ocorrem em aplicações práticas nas quais o processo de tomada de decisão pode envolver vários objetivos. As metaheurísticas que, normalmente, são as mais adaptadas para o problema
multiobjetivo são Algoritmos Genéticos, Simulated Annealing e Busca Tabu, apesar
de outras metaheurísticas, normalmente implementadas com um simples objetivo,
também têm sido adaptadas para esta formulação de problemas, como GRASP.
Segundo os autores, o paradigma orientado a objetos fornece um bom suporte ao
desenvolvimento da abordagens MOLS (MultiObjective Local Search - em português,
Busca Local Multiobjetivo), particularmente, no controle da dimensão e do nível de
complexidade, que são comuns em problemas e métodos nesta área.
Em Claro e Sousa (2001) é apresentado o desenvolvimento do METHOOD (META- Heuristics Object-Oriented Development, em português, Desenvolvimento Orientado a Objetos de Meta-Heurísticas). METHOOD consiste em um framework
genérico em C++ (Figura 4.8) que fornece as seguintes funções:
- apoio para a definição das variáveis de domínio do problema, soluções, movimentos, incrementos e funções de avaliação;
- apoio para os dados do problema;
- um modelo e uma implementação concreta de um algoritmo construtivo, baseado em Andreatta et al. (1998);
- um modelo MOLS e as derivações PSA e MOTS* deste modelo;
4.13
44
- extensões para uma estratégia de lista de candidatos e uma estratégia de variação de vizinhança;
- um nível solucionador para a articulação de algoritmos construtivos e MOLS,
e a implementação de um nível mais alto, em paralelo, de estratégias de hibridismo.
Suporte de dados do Problema
Estruturas básicas e relações
Algoritmos
Básicos
Resolvedores
Algoritmos
Construtivos
METHOOD
Extensão para algoritmos básicos e
construtivos, e resolvedores
Dados
Avaliações
Movimentos
Soluções
Incrementos
Fornecido pelo Cliente
Figura 4.8: O Framework METHOOD. Fonte: Claro e Sousa (2001)
O funcionamento do algoritmo MOLS pode ser descrito da seguinte maneira:
iterações sobre uma população de soluções, construindo uma aproximação para o
conjunto eficiente do problema considerado; para cada solução, uma vizinhança é
criada, e todos os movimentos são obtidos, para que um deles seja selecionado; a
seleção do movimento sempre envolve os pesos das soluções.
Assim, PSA e MOTS* buscam produzir uma boa aproximação do conjunto eficiente, enquanto trabalham com uma população de soluções, cada um deles mantendo
um vetor de peso para a definição da orientação da busca. Cada solução tem uma
característica de componentes de metaheurística, como vizinhança, em geral, ou lista
tabu, no caso específico de MOTS*. PSA e MOTS* se diferenciam na definição do
modelo de operação primitivo. A formulação de movimento de vizinhança em PSA
é a de um movimento gerado que é selecionado e aceito de acordo com uma probabilidade de aceitação. A definição de movimento em MOTS* considera o status Tabu,
critérios de aceitação e uma comparação de avaliações baseada em uma função de
soma dos pesos.
O framework METHOOD foi aplicado para o problema de escalonamento de
máquinas multiobjetivo, buscando minimizar o número de trabalhos atrasados, o
atraso máximo e o atraso penalizado. Entretanto, não são apresentados resultados
desta aplicação. Deve-se ressaltar que o framework implementa apenas a estratégia de busca local MOLS e as derivações (PSA e MOTS* ), não permitindo que o
problema seja solucionado com outro método.
4.13
4.13
45
Diversos trabalhos têm proposto a utilização das abordagens multiagentes e orientada a objetos para o tratamento de metaheurísticas. Alguns destes trabalhos
apresentados neste capítulo, tais como A-Teams, arquitetura MAGMA, framework
Buscador de Vizinhos, METHOOD definem uma estrutura geral para metaheurísticas. Entretanto, os demais trabalhos, tais como, AGENT-DOSS, DYCoal-VRP,
FGAS, MAA-VRPTW, são desenvolvidos para um problema específico, sendo que
grande parte deles são voltados para o PRV. A descrição destes trabalhos permite
diferenciar a arquitetura AMAM proposta neste trabalho dos demais trabalhos relacionados à utilização de sistemas multiagentes para metaheurísticas.
Capítulo 5
Arquitetura Multiagente para
Metaheurísticas
5.1
Introdução
O objetivo deste capítulo é apresentar a arquitetura AMAM - Arquitetura MultiAgente para Metaheurísticas, para a solução de problemas de otimização combinatória. A arquitetura propõe o acoplamento das diversas metaheurísticas em uma
estrutura geral, visando explorar o trabalho cooperativo, no sentido de encontrar
melhores soluções para os problemas de otimização.
Nesta proposta, cada agente implementa uma certa metaheurística específica e
tem autonomia de ação em sua exploração do espaço de busca do problema. Por
meio desta exploração, os agentes, em conjunto, buscam encontrar a solução ótima,
ou pelo menos, uma solução de “boa” qualidade para o problema tratado.
Na arquitetura proposta, os agentes competem entre si pelo alcance da melhor
solução viável. Entretanto, por outro lado, eles, em sua ação, também colaboram
uns com os outros, trocando e compartilhando informações sobre seu estado e acerca
do ambiente, e.g., regiões promissoras do espaço de busca, regiões não recomendadas
à exploração, soluções guias, soluções iniciais, parâmetros da busca, dentre outras
informações.
A arquitetura AMAM foi modelada de modo a ser flexível o bastante para permitir sua utilização em qualquer classe de problemas de otimização combinatória,
e escalável, considerando que podem ser adicionados novos agentes, que implementam e encapsulam metaheurísticas específicas, com mínimo impacto no restante da
arquitetura, ou seja, trata-se de uma arquitetura de alto nível de abstração.
O ambiente, no qual os agentes metaheurísticos existem e atuam, é parte integrante da arquitetura AMAM, devendo ser modelado para cada problema particular
de otimização. A arquitetura também define e incorpora os mecanismos de comunicação entre os agentes e entre estes e seu ambiente. Assim, o esforço de modelagem
para a criação de uma nova instância da AMAM para tratar diferentes problemas
de otimização é minimizado.
46
5.2
Arquitetura Multiagente para Otimização Combinatória
5.2
47
Aspectos desejáveis numa Arquitetura Multiagente para Otimização Combinatória
A partir da análise dos trabalhos correlatos à proposta de arquitetura multiagente
aqui apresentada, é possível definir alguns aspectos desejáveis a uma arquitetura
multiagente para metaheurísticas. Assim, algumas destas características são listadas
abaixo:
• Os agentes devem ser autônomos;
• O ambiente deve ser considerado, e modelado, como uma abstração primária,
que fornece as condições de existência dos agentes, no sentido de sua autonomia, conforme aponta a seção 2.4 (Russell e Norvig, 1995), (Santos, 2003),
(Santos, 2003), (Weyns et al., 2007);
• Para que seja considerada uma arquitetura, é necessário que seja flexível, permitindo desenvolver aplicações para diferentes problemas de otimização combinatória;
• A interação dos agentes (comunicação) deve ser assíncrona, visando assegurar
a sua autonomia;
• A arquitetura deve se basear em mecanismos de ação individuais e coletivos
dos agentes, contemplando mecanismos de cooperação, ad hoc ou não, e de
competição e seleção dos agentes mais aptos (que estão melhor adaptados ao
ambiente);
• A aplicação da arquitetura deve ser executada em um sistema computacional
distribuído e, eventualmente, heterogêneo. Adicionalmente, esta aplicação, se
utilizando um único processador, deve possuir cada agente definido em uma
thread separada, de modo a assegurar sua autonomia e assincronicidade;
• A adição/remoção de novos agentes deve ser possível em tempo de execução,
conforme a necessidade ou disponibilidade do sistema computacional;
• Deve ser desejável que novas heurísticas e metaheurísticas possam surgir da
cooperação entre os agentes, sem a interferência ou a pré-programação do
projetista/operador do software;
• Os agentes (ou o sistema) devem ter uma memória dinâmica e persistente dos
ambientes, de modo a possibilitar o início de suas atividades a partir de “boas
soluções”;
• A arquitetura deve ser capaz de tratar igualmente agentes ou sociedades de
agentes (grupos), assim como métodos pontuais ou populacionais;
• A arquitetura deve ser projetada em alto nível de abstração, sendo, assim,
robusta, escalável e, além disso, permitir que suas aplicações específicas sejam
desenvolvidas com facilidade.
5.3
Estrutura Geral
48
É importante, no entanto, ressaltar que estas características representam formulações gerais e desejáveis de uma arquitetura multiagente genérica para metaheurísticas, não implicando, portanto, que propostas de cunho semelhante tenham que
satisfazer a todos esses aspectos listados para alcançarem êxito em sua implementação.
5.3
Estrutura Geral
O principal objetivo da arquitetura AMAM é a definição de uma estrutura geral
(framework ), à qual novos agentes (metaheurísticas) possam ser adicionados e na
qual diferentes problemas de otimização possam ser solucionados sem grande esforço
adicional. Desta forma, esta seção descreve a estrutura da arquitetura AMAM (Silva
et al., 2007), que é apresentada na Figura 5.1, definindo seus componentes (agentes
e ambiente), bem como as interações entre os agentes e entre esses e o ambiente.
A estrutura geral da arquitetura define os tipos de agentes que podem ser instanciados para a busca de soluções de problemas de otimização combinatória. Entretanto, não existe uma forma pré-definida de como os agentes atuarão nesta busca,
principalmente em relação ao número de agentes envolvidos. Assim, por se tratar
de um framework, o projetista tem a liberdade de utilizar diferentes agentes em
sua busca. Por exemplo, pode-se optar por instanciar dois agentes de busca, sendo
servidos por soluções iniciais geradas por um único agente construtor. Da mesma
forma, alguns agentes metaheurísticas não utilizam Agentes de Busca Local em seu
processo de busca.
Os principais componentes dessa estrutura são: Ambiente; Agente Construtor;
Agente Busca Local; Agente Metaheurísticas; e no centro de tomada de decisão,
Agente Coordenador e Agente Analisador de Solução.
Ambiente
Agente de
Busca Local
Agente
Coordenador
Agente
Metaheurística
Agente
Construtor
Agente
Analisador
de Solução
Centro de Tomada
de Decisão
Figura 5.1: Arquitetura Multiagente AMAM.
5.3
Estrutura Geral
49
Nas subseções seguintes, cada um dos elementos da arquitetura é descrito de
forma detalhada.
5.3.1
Ambiente de Atuação
O ambiente, como já dito na seção 2.4, é um dos principais elementos da arquitetura AMAM. Esta afirmação se justifica considerando que este elemento é aquele
que proporciona a flexibilidade da arquitetura. Para isto, o ambiente, na presente
proposta, corresponde ao espaço de busca do problema tratado, ou seja, todas as
características próprias do problema, independente da forma como este é modelado,
são definidas no ambiente.
Desta forma, uma das principais contribuições da arquitetura AMAM está na
facilidade apresentada por esta para a solução de diferentes problemas de otimização, considerando que a simples troca do ambiente da arquitetura corresponde à
troca do problema a ser solucionado pelos agentes. Assim, o esforço computacional
para a solução de diferentes problemas é reduzido à modelagem dos seus atributos
específicos.
A forma geral do ambiente, apresentada na Figura 5.2, define o modelo básico
de um problema de otimização combinatória. Esta forma é definida considerandose que, na modelagem de um problema de otimização, é necessário definir a forma
como a solução do problema será representada (estrutura Solução), assim como
todas as informações essenciais para a busca de soluções que precisam ser conhecidas
(estrutura Ambiente).
Problema
Solução
Ambiente
Figura 5.2: Modelo do Ambiente.
Um exemplo da particularização do modelo geral do ambiente é dado a partir de
um problema amplamente conhecido na literatura, qual seja, o Problema da Mochila
(Dowsland e Dowsland, 1992), que é apresentado na Figura 5.3. A representação
da estrutura Solução para este problema é definida considerando uma lista de n
variáveis {s1 , s2 , . . . , sn }, associada a cada um dos objetos, considerando que n é o
total de objetos a serem colocados na mochila e cada variável s é definida como 0
(o objeto não está na mochila) ou 1 (o objeto está na mochila). Da mesma forma,
a estrutura Problema, no modelo, contém os dados necessários para a busca da
solução do problema, que são: os objetos candidatos a entrar na mochila, o peso e
o benefício associado à inserção de cada objeto na mochila.
Na arquitetura AMAM, as possibilidades de interação entre agente e ambiente
são determinadas pela capacidade do agente de perceber as características do problema e de agir através da construção de soluções e da exploração do espaço de
busca. Neste sentido, as funções de vizinhança representam uma das principais formas de ação sobre o ambiente, permitindo a construção de novas soluções a partir da
5.3
Estrutura Geral
50
Problema
Objetos 1 ... n
Peso
P1 ... Pn
Benefício b1 ... bn
s1
Solução
s2 ... sn
Capacidade
Ambiente
Figura 5.3: Modelo do ambiente para o Problema da Mochila.
modificação de soluções já existentes. É através destas funções de vizinhança (neste
trabalho, denominadas como movimentos) que os agentes são capazes de percorrer o
espaço de busca, caminhando, de solução em solução, na busca pela melhor solução
do problema.
Da mesma forma, na construção de soluções iniciais são utilizadas diferentes
formas de adição de elementos, que permitem que soluções vazias sejam incrementadas, a partir de um determinado critério de inserção de elementos, até que estejam
completas e possibilitem o início do processo de busca. Estas formas de adição de
elementos, aqui denominadas como incrementos, capacitam o agente a agir sobre o
ambiente construindo soluções.
Entretanto, estas operações (movimentos e incrementos), que permitem ao agente
atuar sobre a solução (no ambiente), são específicas para cada modelo de problema
e precisam ser definidas dentro do ambiente.
As ações efetuadas por agentes no ambiente são possíveis através de estímulos
enviados, pelos agentes, ao ambiente e que ativam as operações disponíveis neste.
Da mesma forma, o ambiente emite estímulos que podem ser captados pelos agentes,
caracterizando a percepção das características do ambiente.
5.3.2
Agentes
Para uma melhor compreensão da arquitetura AMAM, é importante definir o
papel que cada agente desempenha no processo de solução de um problema de
otimização. Neste sentido, as responsabilidade e objetivos dos agentes que compõem
a estrutura geral da arquitetura são descritos nas seções seguintes.
5.3.2.1
Agente Construtor
O Agente Construtor de Solução é constituído por uma heurística construtiva
(Blum e Roli, 2003) e é responsável pela construção de soluções iniciais. O processo
de construção das heurísticas, como já apresentado no capítulo 3, envolve a soma
de componentes em uma solução - inicialmente vazia - até que esta esteja completa.
As soluções geradas por este agente serão utilizadas pelos Agentes Busca Local
e Agentes Metaheurística na inicialização do seus processos de busca.
5.3
Estrutura Geral
51
O estabelecimento de uma solução inicial para um certo agente é equivalente a
se estabelecer a localização desse agente no ambiente (espaço de busca), a partir da
qual o agente iniciará seus movimentos exploratórios.
Heurísticas construtivas freqüentemente retornam soluções de qualidade inferior
quando comparadas com os algoritmos de busca local (Blum e Roli, 2003). Entretanto, soluções iniciais são necessárias para o início do processo, já que métodos
heurísticos e metaheurísticos mais complexos dependem de um ponto inicial do espaço de busca, para começar sua exploração.
5.3.2.2
Agentes de Busca
Os Agentes Busca Local e Metaheurística são classificados, neste trabalho, como
agentes de busca, por possuírem, como principal função, a exploração do espaço de
busca do problema. Estes agentes são descritos a seguir.
Agente Busca Local. Agentes responsáveis por refinar soluções já encontradas,
a partir de algoritmos de Busca Local (Blum e Roli, 2003). O objetivo do Agente
Busca Local é caminhar, de vizinho a vizinho, a cada iteração, visando melhorar
uma solução já obtida por outro agente. Este agente tem movimentos limitados, o
que o mantém dentro de sua vizinhança.
Agente Metaheurística. Agentes que utilizam algoritmos baseados em metaheurísticas para encontrar “boas” soluções para problemas de otimização combinatória. O objetivo principal destes agentes é realizar uma melhor exploração do
espaço de busca, na tentativa de escapar dos ótimos locais por meio de diferentes
estratégias. Os algoritmos implementados por estes agentes, normalmente, utilizam heurísticas subordinadas (busca local) no seu processo de busca. Algumas das
principais metaheurísticas encontradas na literatura são apresentadas no capítulo 3,
e.g, Algoritmos Genéticos (Koza, 1992), VNS (Hansen et al., 2003), ILS (Lourenço
et al., 2001), ACO (Dorigo e Blum, 2005). Estes agentes tem mais capacidade de se
movimentar no ambiente (espaço de busca) e podem, eventualmente, realizarem um
movimento de “salto” que o leva para outro ponto do espaço, fora de sua vizinhança
corrente. Além disso, estes agentes podem atuar de modo cooperativo, na tentativa
de alcançarem seu objetivo.
A estrutura que define a composição interna dos agentes de busca é discutida na
seção 5.3.2.4.
5.3.2.3
Agentes do Centro de Tomada de Decisão
As várias formas que definem a organização de uma sociedade de agentes permitem determinar estruturas hierárquicas e diretrizes para que os agentes possam
atingir um objetivo comum em cooperação. Nesta proposta, um agente coordenador
central é utilizado para intermediar a cooperação entre os demais agentes, caracterizando uma relação de gerência e reduzindo a complexidade de comunicação.
Agente Coordenador. Agente que tem a função de coordenar as atividades e a comunicação entre os agentes no sistema multiagente. Em seu trabalho de
coordenação, este agente, além de realizar trocas de informações, tem também a
responsabilidade por realizar negociações, acordos e tradução das mensagens entre
os diferentes agentes. A cooperação entre os agentes surge por meio do envio de informações, como regiões promissoras do espaço de busca, regiões não recomendadas
5.3
Estrutura Geral
52
à exploração, soluções guias, soluções iniciais ou parâmetros da busca. A comunicação entre os agentes acontece através da troca de mensagens. Desta forma, o
agente coordenador conhece todos os outros agentes da arquitetura, e é responsável,
quando recebe uma mensagem com alguma solicitação de serviço, por encaminhá-la
para o agente que pode realizar a operação solicitada. Outros tipos de comunicação
também podem ser realizadas através do ambiente.
Agente Analisador de Soluções. Agente responsável pela análise e tomada de
decisão com relação às soluções obtidas pelos Agentes Metaheurísticos, selecionando,
dentre elas, a melhor solução. A análise das soluções realizada por este agente
pode variar de acordo com a estratégia implementada pelo Agente Metaheurística,
podendo ser, por exemplo, probabilística. Uma importante contribuição, obtida a
partir do Agente Analisador, está na possibilidade de utilização de diferentes formas
de escolha da “melhor” solução, baseada em técnicas mais complexas, sem que grande
esforço de implementação seja feito.
5.3.2.4
Estrutura Interna dos Agentes de Busca
Os Agentes Busca Local e Metaheurísticos possuem uma mesma estrutura interna
genérica, diferindo entre si apenas nos métodos implementados. Esta estrutura
genérica é baseada na arquitetura geral de um agente proposta em Resende (2003).
Desta forma, a partir de uma definição geral, torna-se bastante simplificado o projeto
de novos agentes de busca. A figura 5.4 apresenta um diagrama ilustrativo dos
principais componentes internos desta estrutura e que são descritos a seguir:
- Base de Conhecimento: componente que mantém informações acerca do
ambiente, informações necessárias para a comunicação entre os agentes, informações sobre os demais agentes, bem como o histórico de busca do próprio
agente;
- Interface de Comunicação: define os protocolos de comunicação entre os
agentes, permitindo a troca de mensagens entre eles.
- Interface com o Ambiente: envolve os sensores e efetores do agente. Os
sensores possibilitam ao agente perceber o ambiente, enquanto os atuadores
proporcionam ao agente a capacidade de agir e modificar seu ambiente;
- Centro de Tomada de Decisão: componente responsável por tomar decisões com base nos conhecimentos obtidos, nos objetivos e nas estratégias do
agente. Ele deve definir qual o melhor caminho para a busca do agente;
- Agenda de Objetivos: lista de objetivos e de restrições a serem satisfeitas,
obtida a partir do ambiente (ou seja, do problema particular de otimização
combinatória a ser resolvido);
- Estratégias: encapsula a estratégia de busca do agente, ou seja, o algoritmo
da heurística ou metaheurística implementada. Este componente é responsável
por encontrar soluções para o problema representado pelo ambiente. Desta
forma, possibilita o isolamento do problema e do método utilizado em sua
solução e permite que esta estrutura geral possa ser usada na definição de
qualquer agente de busca;
5.4
Algumas Especializações da Arquitetura AMAM
Base de
Conhecimento dados percebidos
53
Estratégias
e comunicados
Centro de
Tomada de
Decisão
dados percebidos
e comunicados
decisão
Controlador
dados
percebidos
conteúdo
da ação
Interface com o Ambiente
Sensores
perceção
Agenda de
Objetivos
conteúdo da
comunicação
Interface de Comunicação
Efetores
(Protocolos de Interação)
ação
mensagens
Ambiente
Agentes
Figura 5.4: Estrutura Interna dos Agentes de Busca.
- Controlador: intermedeia e coordena todo o processo interno do agente, ou
seja, as trocas de informações entre seus componentes internos.
Em linhas gerais, o modus operandi de um certo agente de busca pode ser resumido assim: por meio dos sensores, em sua interface com o ambiente, o agente
captura as características do ambiente (dados necessários para a solução do problema
em questão), enquanto os seus atuadores constroem e modificam as soluções (posicionam ou reposicionam o agente em seu ambiente). Neste processo, o agente pode se
comunicar com outros agentes, via sua interface de comunicação. Assim, pode obter
a colaboração destes, através da troca de informações úteis para a busca. Tanto
os dados percebidos do ambiente quanto aqueles comunicados por outros agentes
são usados para auxiliar a tomada de decisão do agente. Durante todo o processo
de busca, o centro de tomada de decisão realiza escolhas, visando minimizar (ou
maximizar) a função de custo do problema.
5.4
O objetivo desta seção é mostrar como as metaheurísticas, já abordadas neste
trabalho, no capítulo 3, podem ser acomodadas na estrutura geral da arquitetura
AMAM. Neste sentido, a arquitetura é instanciada tanto para os métodos baseados
5.4
54
em um único ponto quanto para os métodos populacionais, demonstrando seu caráter
genérico.
Entretanto, como grande parte das metaheurísticas envolvidas neste trabalho
possui, como métodos subordinados, heurísticas de construção e de busca local, a
particularização da arquitetura para estes métodos é inicialmente apresentada.
Assim, considerando-se heurísticas de construção, que estão fortemente ligadas
ao problema a ser tratado, já que manipulam elemento a elemento na construção da
solução inicial, o algoritmo foi ajustado ao interesses da proposta, como mostra a
figura 5.5.
Algoritmo Construção ( )
1 início
2 Inicializa o conjunto C de elementos candidatos;
3 enquanto (conjunto C não está vazio)
4
Emax = seleciona um elemento no conjunto
C de elementos candidatos;
5
s
s U Emax
Adição de elemento
na solução através
de estímulos enviados
ao ambiente,
ativando um
incremento.
6
Atualiza o conjunto C de elementos candidatos;
7 fim enquanto;
8 fim.
Figura 5.5: Algoritmo para um Agente Construtor Básico.
A forma de adição dos elementos na solução, presente em um algoritmo de construção, é o componente que está diretamente vinculado com o problema. Desta
forma, como uma adaptação da estrutura incremento, proposta por Andreatta et al.
(1998), é definida a possibilidade de interação do agente com o ambiente, que permite que este adicione elementos em uma solução, independente da forma como o
elemento é escolhido.
A figura 5.5 apresenta o algoritmo de uma construção básica, na qual a forma
como o elemento, que será inserido na solução (linha 4), é escolhido depende da
heurística implementada, e.g., heurística gulosa ou aleatória. Assim, um Agente
Construtor define as “coordenadas do ambiente” onde o agente será criado.
As heurísticas de busca local operam sobre a solução por meio de estruturas
de vizinhança. Estas estruturas, por sua vez, também dependem do modelo do
problema. Considerando-se esta afirmação, uma segunda adaptação, relacionada à
estrutura movimento, igualmente proposta por Andreatta et al. (1998), é determinada como forma de atuação do agente sobre uma solução.
A figura 5.6 mostra como, a partir da adaptação para a arquitetura AMAM,
o agente, implementando um algoritmo de busca local, faz movimentos sobre as
soluções, emitindo estímulos para o ambiente (linha 3) e possibilitando, assim, a
modificação das soluções e a conseqüente exploração do espaço de busca.
5.4
55
Algoritmo BuscaLocalBásica ( )
1 início
2 enquanto (Critério de Parada) não for satisfeito
3
GeraVizinho( );
Modificação da
solução através de
estímulos enviados
ao ambiente,
ativando um
movimento.
4
SelecionaMelhorSolução;
5 fim enquanto;
6 fim.
Figura 5.6: Algoritmo para um Agente de Busca Local básico.
5.4.1
Especialização da Arquitetura AMAM para a Metaheurística ACO
A metaheurística ACO (Ant Colony Optimization) pode ser descrita por meio da
arquitetura AMAM, na forma apresentada na figura 5.7. O Agente Metaheurística
ACO utiliza, em seu processo de busca, soluções iniciais geradas por um Agente
Construtor, que escolhe seus elementos baseado em uma matriz de feromônio situada
no ambiente da arquitetura, assim como refina suas soluções utilizando um Agente
Busca Local.
Ambiente
Agente
Busca
Local
Agente
Coordenador
Agente
ACO
Agente
Construtor
(baseado em
feromônio)
Agente
Analisador
de Solução
Figura 5.7: Especialização da Arquitetura AMAM para a metaheurística ACO.
A figura 5.8 demonstra como o algoritmo ACO pode ser adaptado para a arquitetura proposta. Neste sentido, o método de busca local, a ser implementando
pelo Agente Busca Local, será definido pelo projetista e o Agente Analisador é responsável por determinar a melhor solução, de acordo com o critério selecionado. A
atualização do rastro de feromônio (linha 7) é realizada através de estímulos enviados
ao ambiente, já que a matriz de feromônio está definida nele.
5.4
56
Assim, de acordo com a figura 5.8, uma formiga utiliza o Agente Construtor
para construir sua solução inicial, refina esta solução através do Agente Busca Local,
solicita ao Agente Analisador a seleção da melhor solução, dentre a sua solução e
a encontrada por outra formiga e, por fim, emite estímulos ao ambiente, para a
atualização do feromônio baseado na solução obtida.
Algoritmo ACO ( )
1 início
3
para cada formiga (até m formigas)
4
Contrói uma solução inicial
usando o rastro de feromônio;
5
s'
6
Seleciona melhor solução
7
BuscaLocal(si);
Atualiza rastro de feromonio;
fim para;
8
9 fim enquanto;
10 fim.
Agente Construtor
(agente modelado
para construção
de solução baseada
em feromônio).
Agente Busca Local
(o método escolhido
pelo projetista).
Agente Analisador
define qual a
melhor solução.
Estímulo enviado
ao ambiente ativando
a atualização do
feromônio.
Figura 5.8: Algoritmo para uma especialização da Arquitetura AMAM para a metaheurística ACO.
5.4.2
Especialização da Arquitetura AMAM para a Metaheurística Algoritmos Genéticos
A arquitetura AMAM pode ser também utilizada para descrever a metaheurística Algoritmos Genéticos (AG). A figura 5.9 ilustra os agentes necessários para
representar a metaheurística AG na arquitetura. Assim, o Agente Construtor, neste
caso, deve construir uma população de soluções iniciais, ou seja, ele deve ser capaz
de gerar um conjunto de soluções para iniciar o processo de busca do AG. Entretanto, como se observa na figura 5.9, o método AG não utiliza Agente de Busca
Local.
A figura 5.10 mostra a especialização do algoritmo AG para os propósitos da
arquitetura. No processo de solução do método AG, após geradas as soluções iniciais,
as soluções são modificadas a partir de operações genéticas como recombinação,
crossover e mutação. Nesta proposta, estas operações são definidas a partir do
5.4
57
Ambiente
Agente
Coordenador
Agente
Construtor
Agente
AG
(Constrói todas as
soluções da População - tamanho n)
Agente
Analisador
de Solução
Figura 5.9: Especialização da Arquitetura AMAM para a metaheurística AG.
Algoritmo AG ( )
1 início
2 t 0;
3 GeraPopulaçãoInicial P(t);
Agente Construtor
(construção de n
(tamanho da
população)
soluções iniciais)
4
Avalia P(t);
5
6
enquanto (Critério de Parada) não for satisfeito
t t + 1;
7
GeraPopulação P(t) a partir de P(t - 1);
8
Avalia P(t);
9
PopulaçãoSobrevivente
10 fim enquanto;
11 fim.
Modificação da
população P(t)
através de estímulos
enviados ao ambiente,
ativando um
movimento.
Agente Analisador
seleciona a população
sobrevivente.
P(t);
Figura 5.10: Algoritmo para uma especialização da Arquitetura AMAM para a
metaheurística AG.
movimento (estrutura de vizinhança), ou seja, as possibilidades de modificações de
uma solução. Assim, qualquer uma destas operações genéticas pode ser realizada
através do envio de estímulos ao ambiente.
Neste método, todas as populações de soluções geradas passam por uma avaliação, que seleciona qual a população que deve sobreviver, baseado em critérios tais
5.4
58
como roleta, que permite que indivíduos menos aptos sejam selecionados, possibilitando escapar de ótimos locais. A função de avaliar a população de soluções, nesta
especialização, é responsabilidade do Agente Analisador de Solução.
5.4.3
Especialização da Arquitetura AMAM para a Metaheurística Simulated Annealing
A terceira metaheurística a ser descrita através da Arquitetura AMAM, Simulated Annealing, é apresentada na figura 5.11. Considerando suas características, o
algoritmo Simulated Annealing não utiliza Agente Busca Local e seu Agente construtor pode ser implementado utilizando-se qualquer método de construção.
Ambiente
Agente
Coordenador
Agente
Simulated
Annealing
Agente
Construtor
Agente
Analisador
de Solução
Figura 5.11: Especialização da Arquitetura AMAM para a metaheurística SA.
Através de estímulos enviados ao ambiente, o Agente Metaheurística SA gera
um vizinho da solução corrente (linha 5 da figura 5.12). Esta solução vizinha será
analisada pelo Agente Analisador de Soluções, de acordo com um mecanismo probabilístico, baseado na termodinâmica, no qual a probabilidade de que um movimento
seja aceito decresce durante a busca. O cálculo desta probabilidade envolve um
parâmetro T (temperatura) que diminui no decorrer da busca.
5.4.4
Instância da Arquitetura AMAM para a Metaheurística Busca Tabu
A metaheurística Busca Tabu utiliza uma lista de movimentos proibidos, chamada de Lista Tabu, para evitar que seu processo de busca entre em ciclagem. Neste
sentido, a Busca Tabu é especializada na forma da figura 5.13, na qual o Agente
Busca Local é projetado para explorar apenas as soluções que não violam a lista
tabu.
A figura 5.14 mostra como a Busca Tabu pode ser encaixada nos interesses da
arquitetura. A solução inicial pode ser solicitada a qualquer Agente Construtor
disponível. Desta forma, após definidos os movimentos permitidos (que não estão
na lista tabu), a busca local é realizada pelo Agente Busca Local, e a melhor solução
é selecionada pelo Agente Analisador de Solução.
5.4
Algoritmo SA ( )
1 início
Agente Construtor
(construção de n
(tamanho da
população)
soluções iniciais)
2
GeraSoluçãoInicial;
3
4
T T0;
5
s
6
7
8
9
se f(s') < f(s)
s
s;
senão
Aceita s' como nova solução
com probabilidade p(T, s', s);
fim se;
10
59
GeraVizinho(solucaoinicial);
Modificação da
população P(t)
através de estímulos
enviados ao ambiente,
ativando
movimentos.
Agente Analisador
define qual a
melhor solução.
11
AtualizaTemperatura(T);
12 fim enquanto;
13 fim.
metaheurística SA.
Ambiente
Agente
Busca Local
(que melhora a
solução com
movimentos ‘
que não violam
a Lista Tabu)
Agente
Coordenador
Agente
Construtor
Agente
Analisador
de Solução
Agente
Busca
Tabu
Figura 5.13: Especialização da Arquitetura AMAM para a metaheurística BT.
5.4.5
Especialização da Arquitetura AMAM para a Metaheurística GRASP
A metaheurística GRASP tem como elemento chave no seu processo de busca a
construção de soluções iniciais baseada em um método guloso aleatório. Assim, para
a especialização deste método para a arquitetura AMAM, como mostra a figura 5.15,
5.4
60
Algoritmo BT ( )
1 início
Agente Construtor
pelo projetista).
2
GeraSoluçãoInicial;
3
4
5
InicializaListaTabu(LT);
MovimentosPermitidos
s’ pertencente a vizinhança
que não viola a Lista Tabu LT;
6
s
BuscaLocal(MovimentosPermitidos);
7
Seleciona Melhor Solução;
Agente Busca Local
pelo projetista).
Agente Analisador
define qual a
melhor solução.
8
AtualizaListaTabu(LT);
9 fim enquanto;
10 fim.
Figura 5.14: Especialização da Arquitetura AMAM para a metaheurística BT.
um Agente Construtor Guloso Aleatório é definido.
A cada iteração do método
Ambiente
Agente
Busca Local
Agente
Coordenador
Agente
GRASP
Agente
Construtor
Guloso
Aleatório
Agente
Analisador
de Solução
Figura 5.15: Especialização da Arquitetura AMAM para a metaheurística GRASP.
GRASP, uma nova solução é gerada pelo seu Agente Construtor (veja figura 5.16),
permitindo que a busca escape de ótimos locais, através da alternância do ponto de
partida. De acordo com a figura 5.16, o refinamento da solução pode ser realizado
por qualquer Agente de Busca Local, e a seleção da solução é feita pelo Agente
Analisador de Soluções.
5.4
61
Algoritmo GRASP ( )
1 início
3
Constrói uma solução inicial s
com um procedimento guloso aleatório;
4
BuscaLocal(s);
5
Seleciona Melhor Solução;
Agente Construtor
(com um procedimento
guloso aleatório).
Agente Busca Local
pelo projetista).
Agente Analisador
define qual a
melhor solução.
6 fim enquanto;
7 fim.
metaheurística GRASP.
5.4.6
Especialização da Arquitetura AMAM para a Metaheurística VNS
O Agente Construtor e o Agente Busca Local são indispensáveis na definição
da arquitetura AMAM para a metaheurística VNS (figura 5.17), adaptando-se perfeitamente à arquitetura básica. Entretanto, os métodos implementados por estes
agentes não são pré-definidos, como em outros casos. O método VNS utiliza várias
Ambiente
Agente
Busca Local
Agente
Coordenador
Agente
VNS
Agente
Construtor
Agente
Analisador
de Solução
Figura 5.17: Especialização da Arquitetura AMAM para a metaheurística VNS.
estruturas de vizinhança em sua busca por soluções, como estratégia para escapar
de ótimos locais. Neste sentido, como mostra a figura 5.18, uma estrutura função de
vizinhança é definida para enumerar os tipos de movimentos disponíveis no ambiente. O processo se inicia com a geração de uma solução inicial (Agente Construtor),
5.4
62
Algoritmo VNS ( )
1 início
Agente Construtor
pelo projetista).
2
GeraSoluçãoInicial( );
3
4
funçãovizinhança
1;
5
6
7
8
9
10
11
s
GeraVizinho(solução inicial,
funçãovizinhança);
s'
BuscaLocal(s);
Modificação da
estímulos enviados
ao ambiente, ativando
um movimento.
Agente Busca Local
pelo projetista).
se f(s') < f(s)
s
s;
senão
TrocaFunçãoVizinhança(funçãoVizinhança);
fim se;
Agente Analisador
define qual a
melhor solução.
12 fim enquanto;
13 fim.
metaheurística VNS.
seguida pela definição da função de vizinhança corrente, que determina qual movimento será executado quando um estímulo for emitido pelo agente. Esta função de
vizinhança é usada para gerar um vizinho da solução (estímulo enviado ao ambiente),
que será refinado pelo Agente Busca Local. O Agente Analisador de Solução tem
um papel importante na seleção da melhor solução, já que, caso não haja melhora
na solução encontrada pela busca local, uma nova função de vizinhança deve ser
definida. Esta troca de função de vizinhança possibilita ao VNS explorar diferentes
partes do espaço de busca.
5.4.7
Especilização da Arquitetura AMAM para a Metaheurística ILS
A metaheurística ILS, assim como as demais metaheurísticas baseadas em busca
local, é facilmente descrita a partir da arquitetura AMAM. A figura 5.19 mostra
como esta especialização é definida. Assim, levando-se em consideração a forma
geral do algoritmo ILS, uma solução inicial pode ser solicitada a qualquer Agente
Construtor disponível, assim como o refinamento também pode ser realizado por
qualquer Agente Busca Local.
A estratégia usada pelo ILS para escapar de ótimos locais é a execução de saltos
no gráfico de soluções, através da perturbação. Para a perturbação da solução
corrente, é usado uma estrutura de vizinhança que modifica a solução, levando-a
5.4
63
Ambiente
Agente
Busca Local
Agente
Coordenador
Agente
ILS
Agente
Construtor
Agente
Analisador
de Solução
Figura 5.19: Especialização da Arquitetura AMAM para a metaheurística ILS.
Algoritmo ILS ( )
1 início
Agente Construtor
pelo projetista).
2
s0
GeraSoluçãoInicial( );
3
s*
BuscaLocal(s0);
4
5
s’
Pertubação(s*);
6
s’’
BuscaLocal(s’);
7
s*
CritérioDeAceitação(s’’,s*);
Modificação da
estímulos enviados
ao ambiente, ativando
um movimento.
Agente Busca Local
pelo projetista).
Agente Analisador
define qual a
melhor solução.
12 fim enquanto;
13 fim.
metaheurística ILS.
para outra região do espaço de busca. Na arquitetura proposta, isto é possível por
meio dos movimentos disponíveis no ambiente. Assim, a cada iteração, o Agente ILS
emite estímulos ao ambiente, ativando um movimento escolhido para a perturbação
da solução, como mostra a figura 5.20. Em seguida, a solução obtida será refinada
5.5
Modelagem
64
pelo Agente Busca Local. Ao final da iteração, o Agente Analisador seleciona a
melhor solução, de acordo com algum critério de aceitação pré-estabelecido.
5.5
Modelagem UML aplicada à AMAM
A arquitetura AMAM foi modelada utilizando-se a Linguagem de Modelagem
Unificada (UML - Unified Modeling Language), que foi desenvolvida em trabalhos
realizados por Grady Booch, James Rumbaugh e Ivar Jacobson, que resultaram no
estabelecimento de uma única especificação padrão. Uma descrição detalhada da
UML pode ser encontrada em Booch et al. (1998).
A figura 5.21 apresenta o modelo que ilustra as relações entre os agentes e entre
esses e seu ambiente. A partir desse modelo simplificado da arquitetura AMAM, é
possível melhor identificar suas principais classes, que são descritas a seguir.
(i) Problema: contém todas as informações do problema tratado, necessárias
para a solução deste. Freqüentemente, estas informações são obtidas a partir
de problemas-teste;
(ii) Solução: encapsula a representação da solução do problema tratado. Contém
elementos como a função objetivo e penalidades;
(iii) Movimento: encapsula o algoritmo de cada estrutura de vizinhança, ou seja,
os movimentos que podem ser realizados sobre uma solução, gerando uma nova
solução, vizinha ou não.
(iv) Incremento: encapsula o algoritmo de cada forma de incremento, ou seja, a
adição de elementos em uma solução vazia.
(v) Agente Construtor: é composto pela estratégia de construção, um sensor
e um atuador. A estratégia define o método implementado pelo agente. O
sensor e o atuador permitem ao agente interagir com o ambiente e com os
outros agentes.
(vi) Agente de Busca: como o Agente Construtor, este agente também é composto por uma estratégia, um sensor e um atuador. A estratégia define o
método implementado pelo agente. O tipo de Agente de Busca (Agente Busca
Local ou Agente Metaheurística) depende da estratégia utilizada.
(vii) Agente Coordenador: intermedeia a interação entre os agentes. Este agente
também possui um sensor e um atuador, que o possibilita relacionar com os
outros agentes. Apenas a comunicação direta, (i.e., que não é realizada via
alterações no ambiente) entre os agentes é intermediada pelo Agente Coordenador.
(viii) Agente Analisador de Soluções: implementa métodos de seleção de soluções, de acordo com a heurística implementada, possibilitando que formas
mais complexas sejam utilizadas na escolha das soluções. Para perceber soluções e as características necessárias para a seleção destas, este agente utiliza,
assim como todos os outro agentes, um sensor, assim como sua ação é realizada
através de um atuador.
5.5
Modelagem
65
Agente_Analisador
estimula
Analisador
percebe
Ambiente
Incremento
interage
incrementa
Agente_Coordenador
Solução
estimula
Movimento
usa
Problema
modifica
Coordenador
percebe
interage
estimula
Agente_Construção
Agente_Busca Local
interage
interage
Agente_Metaheurística
percebe
estimula
<<interface>>
Construção
Construção1
percebe
<<interface>>
Busca_Local
ConstruçãoN
Busca_Local1
Busca_LocalN
<<interface>>
Metaheurística
Metaheurística1
MetaheurísticaN
Figura 5.21: Modelagem simplificada da Arquitetura AMAM.
Considerando este modelo simplificado, um novo modelo (veja figura 5.22) é
apresentado para descrever, com maiores detalhes, a arquitetura proposta. Neste
modelo, foram utilizados padrões de projeto, com o objetivo de desenvolver uma
arquitetura projetada a partir de encapsulamento, acoplamento fraco e responsabilidades bem definidas. Estes padrões fornecem alternativas de projeto que permitem
que um sistema seja reutilizável, melhorando, também, a documentação e a manutenção deste sistema. Uma discussão detalhada dos padrões de projeto é apresentado
em Gamma et al. (1995), assim como um tutorial utilizando a linguagem Java pode
ser encontrado em Cooper (2000).
Neste sentido, o primeiro padrão utilizado é o Mediador (Mediator ), que define
a implementação do Agente Coordenador para intermediar a comunicação entre os
agentes. Considerando-se que o comportamento de um sistema é dividido entre
classes, o número de classes envolvidas pode crescer até que a comunicação entre
Descida
Agente_Busca
Primeiro_Melhora
Busca_Local
<<interface>>
O Padrão Estratégia
define uma família de algoritmos, encapsula cada um,
e os fazem trocáveos. Este
padrão permite que o algoritmo varie independentemente dos clientes que o usa.
A solução é um conteiner
de soluções, que permite,
no caso de metaheurísticas
populacionais que todas as
soluções sejam tratadas em
uma mesma estrutura.
Busca_Local
Estratégia_Busca
<<interface>>
percebe_infomações
ILS
estímulo
Incremento1
Busca_Tabu
Metaheurística
Sensor
Atuador
O padrão Fachada é usado nas
Interfaces do Agentes para fornecer uma interface unificada para
um conjunto de interfaces em um
subsistema. Estruturar um sistema em subsistemas ajuda a reduzir a complexidade.
interage
IncrementoN
MetaheurísticaN
interage
Interface
<<interface>>
atua_efetuando
MovimentoN
Incremento
Movimento1
<<interface>>
movimenta
Melhor_Solução
Movimento
movimenta
Solução_Corrente
Solução
<<interface>>
usa_informações
Problema
<<interface>>
Operações_Solução
incrementa
Solução_Inicial
Pacote_Solução
Ambiente
Atuador
Sensor
Atuador
interage
estímulo
Analisador_De_Solução
Coordenador
Gulosa
estímulo
percebe_infomações estímulo
Sensor
interage
Interface
Agente_Analisador
atua_efetuando
Atuador
Sensor
Interface
Agente_Coordenador
interage
interage
Interface
Agente_Coordenador
<<interface>>
Aleatória
Estratégia_Construção
Agente Coordenador é
implementado utilizando o
padrão Mediador, que define um objeto que encapsula
a forma como um conjunto
de objetos interage.
ConstruçãoN
5.5
Modelagem
66
Figura 5.22: Modelo Detalhado da Arquitetura AMAM.
estas se torne mais complexa. Para que uma classe se comunique com outra, é
preciso que ela possua uma referência desta outra classe, o que, mais adiante, pode
tornar o sistema difícil de ser alterado. Assim, o padrão mediador simplifica este
5.5
Modelagem
Agente_Construtor
Agente_Busca_Local
Agente_Metaheurística
67
interação
interação
Agente_Coordenador
interação
Agente_Analisador_Soluções
interação
Figura 5.23: Interações entre os agentes e o mediador.
sistema, sendo a única classe que conhece as outras classes. Logo, se houver alguma
mudança, o mediador é o único que precisará ser modificado.
Este padrão permite também o desacoplamento das partes do sistema, definindo
uma interface entre subsistemas. No caso da arquitetura AMAM, como mostra a
figura 5.23, os agentes enviam e recebem requisições do Agente Coordenador, e este
agente implementa o comportamento cooperativo, pelo roteamento das requisições
aos agentes apropriados.
Entretanto, o Agente Coordenador não é a única forma de comunicação entre
agentes, pois estes podem se comunicar através da troca de estímulos com o ambiente. Assim, o ambiente se torna, também, um mediador (indireto) da comunicação
entre os diversos agentes da arquitetura.
<<interface>>
Estratégia_Construção
Gulosa
Aleatória
ConstruçãoN
Figura 5.24: Padrão Estratégia na definição dos Agentes Construtores.
De acordo com Gamma et al. (1995), o Padrão Estratégia (Strategy) define uma
família de algoritmos, encapsula cada um, e os fazem substituíveis, deixando, assim, o algoritmo variar independentemente dos clientes que usam. Desta forma,
este padrão é utilizado, na arquitetura AMAM, na definição do projeto dos métodos implementados pelos agentes. Os Agentes Construtores se diferenciam apenas
pela estratégia de construção implementada, ou seja, agentes semelhantes, com comportamentos diferenciados. Através deste padrão, é possível definir uma família de
Agentes Construtores (veja figura 5.24), permitindo-se que um agente construtor
seja criado sendo necessário apenas a escolha do método de construção. Além disso,
em tempo de execução, os Agentes Construtores podem ser substituídos por outros.
O Padrão Estratégia, através do encapsulamento do método em uma classe separada, permite a variação do método independentemente do contexto em que está
inserido, facilitando possíveis mudanças e a extensão do método.
Da mesma forma, o Padrão Estratégia é usado na definição dos Agentes de
Busca (Busca Local e Metaheurística), por se tratarem de agentes que implementam
métodos de busca e possuem forte semelhança, distinguindo-se apenas pelo método
implementado. Assim, o Padrão Estratégia é utilizado tanto para definir a família
de Agentes de Busca quanto para definir duas subfamílias: Agentes de Busca Local e
Agentes Metaheurísticas, como mostra a figura 5.25. Estas subfamílias, assim como
5.6
Modelagem
68
nos demais casos de estratégia, implementam variantes de algoritmos de busca e
definem agentes que se diferem apenas no comportamento. O Padrão Estratégia é
<<interface>>
Estratégia_Busca
<<interface>>
<<interface>>
Busca_Local
Descida
Metaheurística
Primeiro_Melhora
Busca_Local
ILS
Busca_Tabu
MetaheurísticaN
Figura 5.25: Padrão Estratégia na definição dos Agentes de Busca.
novamente utilizado na definição das famílias de movimentos e de incrementos, que
são os métodos de modificação de uma solução. Movimentos e incrementos também
se diferem no comportamento apresentado. Assim, o padrão estratégia é utilizado
no projeto destes elementos como mostra a figura 5.26.
<<interface>>
<<interface>>
Movimento
Incremento
Movimento1
MovimentoN
Incremento1
IncrementoN
Figura 5.26: Padrão Estratégia na definição dos Agentes de Busca.
Agente
Interface
Sensor
percebe_
informações
Atuador
estímulo
Estratégia
Figura 5.27: Padrão Fachada na definição de uma interface para os Agentes.
Outro padrão de projeto utilizado na modelagem da arquitetura AMAM é o
Padrão Fachada (Facade). O Padrão Fachada fornece uma interface unificada para
um conjunto de objetos, formando um subsistema fácil de usar. Esse estrutura um
sistema em subsistemas e ajuda a reduzir a complexidade (Gamma et al., 1995).
Este padrão foi utilizado na arquitetura proposta, com o objetivo de fornecer uma
interface entre o agente e o restante do sistema (ambiente e demais agentes), como
ilustra a figura 5.27. Assim, cada agente possui uma interface de interação que, por
meio dos sensores e efetores, permite que o agente se relacione no sistema.
5.6
5.6
69
A arquitetura AMAM combina diversas metaheurísticas, sendo que cada uma
delas é definida como um agente autônomo, capaz de realizar a exploração do espaço
de busca de um problema de otimização combinatória. Desta forma, o espaço de
busca do problema é definido como o ambiente da arquitetura multiagente proposta.
Uma estrutura geral da arquitetura AMAM é apresentada, com os principais
elementos que a define. Os agentes presentes nesta estrutura podem ser instanciados
em diferentes configurações para a busca da solução do problema em questão.
A definição de uma estrutura interna para os agentes de busca identifica os principais elementos e possibilidades de interação entre estes agentes e o seu ambiente,
simplificando assim o projeto de novos agentes de busca.
Em seguida, com o objetivo de apresentar cada uma das principais metaheurística
na arquitetura AMAM, algumas especializações dessa arquitetura. A partir destas
especializações, é possível visualizar como metaheurísticas baseadas em um único
ponto e metaheurísticas baseadas em população podem ser facilmente adaptadas à
arquitetura proposta.
O modelo da arquitetura, definido utilizando a linguagem de modelagem UML,
permite a descrição dos detalhes de implementação, assim como padrões de projeto
utilizados.
Capítulo 6
Experimentos Computacionais
6.1
Introdução
A arquitetura AMAM é uma arquitetura de propósito geral, voltada para tratar
problemas de otimização combinatória. Ela pode, em princípio, ser utilizada na
solução de diferentes problemas, pela simples instanciação da arquitetura, com sua
conseqüente especialização, porém, sem requerer mudanças significativas na mesma.
O objetivo central deste capítulo é apresentar especializações da arquitetura
AMAM, buscando: (1) mostrar o correto funcionamento da arquitetura; e (2) mostrar que a adição de novos agentes pode melhorar o desempenho da arquitetura
como um todo.
Cinco especializações da arquitetura AMAM foram utilizadas na realização dos
experimentos computacionais. São:
(1) AMAM-ILS: utiliza apenas um Agente Metaheurística implementando o método ILS;
(2) AMAM-VNS: utiliza apenas um Agente Metaheurística implementando o método VNS;
(3) AMAM-ILS-ILS: utiliza dois Agentes Metaheurísticas, sendo que os dois agentes implementam o método ILS;
(3) AMAM-VNS-VNS: utiliza dois Agentes Metaheurísticas, sendo que os dois
agentes implementam o método VNS; e
(4) AMAM-ILS-VNS: utiliza dois Agentes Metaheurísticas, sendo que um implementa o método ILS e o outro implementa o método VNS.
O problema de otimização utilizado nas especializações apresentadas é o Problema de Roteamento de Veículos com Janela de Tempo, que será melhor discutido
na seção 6.2.
A seção 6.3 descreve as heurísticas e metaheurísticas utilizadas nas especializações desenvolvidas.
É importante ressaltar que não é objetivo deste trabalho superar as melhores
soluções encontradas na literatura para o problema em análise, mas, sim, apontar
as características e benefícios obtidos a partir da perspectiva multiagente, tais como
flexibilidade, escalabilidade e encapsulamento.
70
6.2
Problema de Roteamento de Veículos com Janela de Tempo
6.2
71
Problema de Roteamento de Veículos com Janela de Tempo
O Problema de Roteamento de Veículos (PRV) é um problema de otimização
combinatória bem conhecido e de grande relevância econômica, principalmente em
sistemas logísticos e de transporte. Este problema tem recebido, nas últimas décadas, considerável atenção na literatura, sendo que uma boa referência para sua
revisão é a coletânea de artigos apresentada em Toth e Vigo (2002).
O PRV é um problema de transporte de bens de consumo e produtos que busca
encontrar a melhor rota, partindo de um depósito, para atender clientes espalhados
geograficamente por meio de uma frota de veículos. Esse problema pode gerar
variações para muitos domínios do mundo real, como, por exemplo, serviços de
coleta/entrega e distribuição de petróleo.
O problema pode ser representado como um problema de teoria de grafos, no qual
G = (V, A) é um grafo completo, V é o conjunto de vértices (clientes e o depósito,
normalmente nomeado como vértice zero) e A é o conjunto de arcos (o caminho
que liga todos os clientes e o depósito, representando a distância entre eles). Uma
demanda não negativa qi é associada a cada vértice, e um custo cij é associado com
cada arco em A. A figura 6.1(A) mostra um exemplo de um PRV com 11 clientes.
Como solução para o PRV obtém-se um conjunto de rotas (veja figura 6.1), na
qual, cada rota é representada por uma lista ordenada de clientes que determinam
a seqüência em que devem ser atendidos.
(A)
qi
11
(B)
9
1
6
10
5
4
[ai,bi]
Cliente
9
6
8
2
7
3
ci
1
8
2
Depósito
11
10
7
3
5
4
Figura 6.1: (A) grafo que representa o PRVJT e (B) grafo que representa uma
solução para o PRVJT.
O Problema de Roteamento de Veículos, por ser um problema de otimização,
pode ser formulado como um problema de programação matemática, definido por
uma função objetivo e um conjunto de restrições.
O objetivo mais comum é a minimização do custo de transporte, na forma de
uma função da distância percorrida ou do tempo de viagem; os custos com veículos
e motoristas podem ser considerados fixos e, então, o número de veículos pode
também ser minimizado. A função objetivo também pode ser usada para representar
restrições suaves, que, quando violadas, pagam penalidades (Rizzoli et al., 2004).
Existem muitas variantes do PRV, sendo que estas se diferenciam pelas restrições adicionadas à versão básica do problema. Assim, a versão básica do PRV,
6.2
Modelagem do PRVJT
72
conhecida como PRV com Capacidade (PRVC), é caracterizada pela restrição de
capacidade limitada dos veículos. O objetivo do PRVC é minimizar o custo total da
viagem, expresso como a distância necessária para atender os clientes. Nessa versão,
encontram-se as seguintes restrições para o problema:
(i) as demandas dos clientes são determinísticas e conhecidas com antecedência;
(ii) entregas não podem ser divididas, ou seja, um pedido de um cliente não pode
ser atendido usando dois ou mais veículos;
(iii) a frota de veículos é homogênea, de modo que todos os veículos são iguais em
todas as características;
(iv) existe somente um depósito.
Desta forma, como dito acima, as variações do PRV surgem a partir da adição
de novas restrições, como janelas de tempo, acessibilidade, demandas dinâmicas.
Alguns exemplos de variantes são: o PRV com Janela de Tempo (e sua variante
Dependente de Tempo), o PRV com Coleta e Entrega, e o PRV Dinâmico, entre
outros.
Muitos trabalhos têm dedicado uma atenção especial ao Problema de Roteamento de Veículos com Janela de Tempo (PRVJT), face à grande aplicabilidade da
restrição de janelas de tempo nos casos reais. O PRVJT mantém a restrição de
capacidade e adiciona a restrição de janela de tempo, a qual associa a cada cliente i
um intervalo de tempo [ai , bi ], denominado janela de tempo, e um tempo de serviço
si (atendimento). Assim, caso o veículo chegue ao cliente antes do início da janela
de tempo, um tempo de espera é necessário. Caso o veículo chegue ao cliente após
o instante final da janela de tempo bi , uma penalidade é adicionada.
O PRVJT é um problema da classe NP-difícil, assim, a busca de soluções utilizando métodos exatos pode ser inviável, já que a exploração exaustiva do espaço de
busca requer um longo tempo de processamento impraticável nos casos de elebados
números de clientes. Desta forma, a utilização de metaheurísticas, na solução do
PRVJT, possibilita encontrar “boas” soluções em um espaço de tempo reduzido.
6.2.1
Modelagem do PRVJT
O ambiente da arquitetura possui todos os elementos que são específicos ao problema tratado. Assim, o ambiente foi modelado para o PRVJT na forma apresentada
na Figura 6.2, de modo que a estrutura Problema possui todas as informações dos n
clientes (e.g., localização, janelas de tempo, demanda, dentre outros) e a estrutura
Solução é representada por um conjunto de k rotas, compostas por t clientes.
6.2.1.1
A função de avaliação utilizada é apresentada em (6.1). O principal objetivo
desta função é minimizar o custo associado, dado pela soma das distâncias percorridas nas rotas da solução. Adicionalmente, a função de avaliação é utilizada também
para penalizar a violação das restrições do problema, sendo que, assim, uma solução
que viola as restrições possui um valor ruim da função de avaliação. Desta forma,
6.2
Estruturas de Vizinhança
73
Problema
Cliente 1 ... n
...
... ... ...
Demanda d1 ... dn
Solução
c11
c12
...
c1t
ck1
ck2
...
ckt
Ambiente PRVJT
Figura 6.2: Problema de Roteamento de Veículos com Janela de Tempo.
são penalizadas as violações de capacidade, janela de tempo e número de veículos
(Fraga, 2006).
Através da penalidade sobre o número de veículo, esta função permite minimizar
também o número de veículos necessários e, conseqüentemente, reduzir os custos
com veículos e motoristas. A função de avaliação f (s) é apresentada a seguir, sendo
s uma solução corrente do problema:
f (s) =
dij + αQ(s) + βJ(s) + σK(s)
(6.1)
(i,j)∈A
sendo:
- dij : distância entre os clientes (i, j);
- A : conjunto dos arcos pertencentes à solução;
- Q(s) : soma dos excessos de capacidade de todos os veículos da solução;
- J(s) : soma das violações referentes às restrições de janela de tempo da solução;
- K(s) : total de veículos da solução;
- α, β e σ : fatores de penalidade não negativos, sendo α o fator de penalidade
associado à capacidade dos veículos; β o fator de penalidade associado à maior
janela de tempo do problema teste; e σ o fator de penalidade associado ao
número de veículos utilizados.
6.2.1.2
Estruturas de Vizinhança
Duas estruturas de vizinhança (movimentos) são utilizadas pelos métodos implementados nas especializações que serão descritas nas seções seguintes. São elas:
(i). Troca: o movimento troca realiza a permuta dois clientes, escolhidos aleatoriamente de rotas que também são escolhidas aleatoriamente. Assim, os clientes
escolhidos podem ser de rotas distintas ou até mesmo da mesma rota;
6.2
Descrição dos Problemas Testes
74
(ii). Realocação: o movimento de realocação retira um cliente de uma dada rota e
insere em uma outra posição, que pode ser na mesma rota ou em uma outra
rota. Este movimento foi utilizado de duas formas, sendo que, na primeira
delas, permite que uma nova rota seja criada para a realocação do cliente, e,
na segunda forma, o número de rotas da solução não pode ser aumentado,
ocorrendo a realocação apenas entre as rotas existentes.
6.2.2
Descrição dos Problemas-Teste
Os problemas-teste utilizados em todos os experimentos computacionais descritos
neste capítulo são os introduzidos por Solomon (1987), amplamente utilizados em
trabalhos envolvendo o PRVJT. Estes problemas-teste são formados por três grupos
distintos de clientes:
Instância C101
90
Coordenadas Y
80
70
60
50
40
30
20
10
0
0
10
20
30
40
50
60
70
Coordenadas X
Figura 6.3: Instância C101.
80
90
100
• C: os clientes estão distribuídos geograficamente em grupos de clientes próximos uns dos outros (veja figuras 6.3);
• R: os clientes são distribuídos aleatoriamente e distantes uns dos outros (veja
as figuras 6.4); e
• RC: uma mistura dos dois grupos anteriores (veja as figuras 6.5).
Tabela 6.1: Informações dos problemas-teste de Solomon (Solomon, 1987).
Tipo
R1
R2
C1
C2
RC1
RC2
No
12
11
9
8
8
8
Cap.
200
1000
200
700
200
1000
JTf
230
1000
1236
3390
240
960
ts
Dist.
10 randômica
10 randômica
90 agrupada
90 agrupada
10 misturada
10 misturada
Jan
estreita
larga
estreita
larga
estreita
larga
6.3
Heurísticas e Metaheurísticas Utilizadas
75
Instância R101
Coordenadas Y
80
70
60
50
40
30
20
10
0
0
10
20
30
40
50
60
70
Coordenadas X
Figura 6.4: Instância R101.
Instância RC101
90
Coordenadas Y
80
70
60
50
40
30
20
10
0
0
10
20
30
40
50
60
70
80
90
100
Coordenadas X
Figura 6.5: Instância RC101.
A tabela 6.1 (Ho-Chen e Ting, 2005) resume as características dos problemas
testes de Solomon. A coluna “No ” mostra o número de problemas-teste de cada
tipo; a coluna “Capac.” apresenta a capacidade dos veículos (sendo que a frota é
homogênea); a coluna “JTf” indica a janela de tempo final do depósito, ou seja, o
limite de tempo que o veículo tem para voltar para o depósito; a coluna ts apresenta
o tempo a ser gasto no atendimento ao cliente; a coluna “Distrib.” mostra como os
clientes estão distribuídos geograficamente; e, por fim, a coluna “Jan” apresenta o
tipo de janela de tempo utilizada no problema-teste.
6.3
Heurísticas e Metaheurísticas Utilizadas
Considerando as especializações desenvolvidas, enumeradas acima, esta seção
descreve os métodos utilizados na implementação dos agentes envolvidos. Os Agentes Metaheurísticas utilizados nas especializações, tanto o Agente VNS quanto o
Agente ILS, utilizam o Agente de Busca Local que implementa a heurística de des-
6.3
Heurística Construtiva
76
cida, e o Agente Construtor, que implementa a heurística gulosa.
6.3.1
Heurística Construtiva
A heurística construtiva implementada utiliza uma função gulosa para a seleção
do próximo cliente a ser inserido na rota, baseada na janela de tempo. A seleção do
melhor candidato é feita utilizando-se a funcaoGulosaJT (figura 6.6), a qual escolhe
o cliente que possui a menor diferença entre o início de sua janela de tempo e o
tempo total percorrido até aquele instante. Assim, a solução inicial obtida é sempre
viável em relação à restrição de janelas de tempo, facilitando a busca. A figura 6.6
apresenta o algoritmo da heurística construtiva utilizada.
Algoritmo ConstrucaoGulosaJT (·)
1 inicio
2
Inicializa o conjunto C de elementos candidatos;
3
enquanto C = ∅;
4
candidato ← funcaoGulosaJT (C);
5
s ← s ∪ C;
6
Atualiza C;
7
fim enquanto;
8 fim.
Figura 6.6: Algoritmo da Construção Gulosa baseada em Janela de Tempo.
6.3.2
Heurística de Busca Local
A heurística de refinamento utilizada pelos Agentes Busca é o método de descida.
O método de descida analisa todos os vizinhos de uma dada solução corrente e aceita
apenas as soluções que representem melhora na solução atual. Assim, como este
método explora toda a vizinhança da solução corrente, ele pára quando encontra um
ótimo local. No método implementado, apresentado na figura 6.7, a solução vizinha
é obtida a partir da aplicação do movimento realocação sobre a solução corrente.
Este movimento de realocação não permite que novas rotas sejam geradas, e, assim, é
possível diminuir o número de rotas durante o processo de refinamento da solução. A
aplicação do método de descida com o movimento de realocação permitiu a redução
significativa do número de rotas em relação a outras implementações realizadas.
6.3.3
Metaheurística Iterated Local Search
O método Iterated Local Search, como descrito na seção 3.4.1.6, realiza perturbações na solução, buscando escapar de ótimos locais e, assim, alcançar melhores soluções. Neste sentido, na implementação desse método na forma utilizada pelo Agente
Metaheurística, apresentada na figura 6.8, a perturbação é realizada utilizando-se o
movimento de troca de forma aleatório. A solução inicial é fornecida pelo Agente
Construtor, implementando a construção gulosa baseada na janela de tempo. As soluções são refinadas pelo Agente Busca Local, implementando o método de descida.
6.3
Algoritmo Variable Neighborhood Search
77
Algoritmo Descida(solucaoInicial)
1 inicio
2
solucaoCorrente ← solucaoInicial;
3
para toda vizinhanca da solucaoCorrente;
4
solucaoV izinha ← realocacao(solucaoCorrente);
5
se solucaoV izinha < solucaoCorrente;
6
solucaoCorrente ← solucaoV izinha;
7
fim se;
8
fim para;
9 fim.
Figura 6.7: Algoritmo do Método de Descida.
Algoritmo ILS(·)
1 inicio
2 solucaoInicial ← construcaoGulosaJT (·);
3 solucaoCorrente ← descida(solucaoInicial);
4 melhorSolucao ← solucaoCorrente;
5 enquanto CriteriodeP arada nao for satisfeito;
6 solucaoP erturbada ← T rocaAleatoria(solucaoCorrente);
7 solucaoMelhorada ← descida(solucaoP erturbada);
8 melhorSolucao ← CriteriodeAceitacao(solucaoMelhorada, melhorSolucao);
9 fim enquanto;
10 fim.
Figura 6.8: Algoritmo do Método Iterated Local Search.
Algoritmo V NS(·)
1 inicio
2 solucaoInicial ← construcaoGulosaJT (·);
3 Inicializaf uncaoV izinhanca;
4 solucaoCorrente ← solucaoInicial;
5 enquanto CriteriodeP arada não foi satisfeito;
6 solucaoV izinha ← GeraV izinho(solucaoCorrente, f uncaoV izinhanca);
7 solucaoMelhorada ← descida(solucaoCorrente);
8 se f aval(solucaoMelhorada) < f aval(solucaoCorrente)
9
solucaoCorrente ← solucaoMelhorada;
10 senao
11
T rocaF uncaoV izinhanca(f uncaoV izinhanca);
12 fim se;
13 fim enquanto;
14 fim.
Figura 6.9: Algoritmo do Método VNS.
6.3.4
Algoritmo Variable Neighborhood Search
Assim como o método Iterated Local Search, o método Variable Neighborhood
Search também utiliza as heurísticas de construção gulosa (baseada na janela de
6.4
Experimentos com as instâncias da Arquitetura AMAM
78
tempo) e o método de descida. Como estratégia para escapar de ótimos locais, o método altera a função de vizinhança usada para se gerar soluções vizinhas, utilizando
a função T rocaF uncaoV izinhanca(f uncaoV izinhanca), como mostra a figura 6.9.
As funções de vizinhança intercaladas, caso não haja melhora na solução, são: troca
aleatório e realocação (movimento que permite que novas rotas sejam geradas).
6.4
Experimentos com as especializações da Arquitetura AMAM
As especializações apresentadas nesta seção foram implementadas em linguagem
Java, utilizando a plataforma Eclipse. Na arquitetura, cada agente faz sua busca
em uma thread independente. Threads são fluxos de controle seqüencial, isolados
dentro do programa, permitindo que um programa simples possa executar várias
tarefas diferentes ao mesmo tempo, independentes umas das outras.
Desta forma, a linguagem Java foi escolhida, considerando-se que esta fornece
classes prontas para a implementação de threads, facilitando o desenvolvimento de
sistemas com este recurso, assim como o desenvolvimento de sistemas multiagentes.
Os resultados apresentados nesta seção estão dispostos da seguinte forma nas
respectivas tabelas: a coluna “Média AMAM” mostra a média das soluções obtidas
nas execuções das especializações, sendo que este valor representa apenas a distância total percorrida pelos veículos, considerando-se que foram obtidas soluções sem
violação de restrições (capacidade e janela de tempo). Na coluna “Melhor Solução AMAM” são apresentadas as melhores soluções encontradas pela especialização,
dentre as execuções realizadas. Os melhores resultados obtidos de heurísticas diversas são reportados na mesma tabela, na coluna “Melhor Lit.” e foram obtidos de
Ho-Chen e Ting (2005). A tabela apresenta também o número de rotas (veículos)
da solução entre colchetes ([ ]).
Para todas as especializações da arquitetura AMAM aqui apresentadas, foram
realizadas quinze execuções para cada problema-teste utilizado, com a finalidade de
se obter o comportamento médio.
Foram realizadas as seguintes especializações da Arquitetura AMAM:
• Especialização ILS;
• Especialização VNS;
• Especialização ILS-ILS;
• Especialização VNS-VNS;
• Especialização ILS-VNS.
Cada uma delas encontra-se descrita nas subseções a seguir.
6.4.1
Especialização AMAM-ILS
A especialização derivada do instanciamento da arquitetura AMAM-ILS é composta pelos seguintes elementos: Ambiente (PRVJT), Agente Construtor Guloso
6.4
79
JT, Agente Busca Local Descida, Agente Metaheurística ILS, Agente Coordenador,
Agente Analisador de Soluções, conforme mostra a figura 6.10. O objetivo desta
Ambiente
Agente
Descida
Agente
Coordenador
Agente
ILS
Agente
Construtor
Guloso JT
Agente
Analisador
de Solução
Figura 6.10: AMAM-ILS.
seção é apresentar os resultados relacionados à implementação apenas do método
ILS, que, embora utilizando a arquitetura AMAM, teve um desempenho equivalente
àquele que teria se implementado em sua forma tradicional, já que neste caso não é
empregado o paralelismo (apenas um agente). Assim, é possível comparar os resultados do método ILS com outras especializações da arquitetura que utilizam mais
de um agente na solução de um problema e verificar o provável aprimoramento da
solução obtida.
Os resultados dos testes da especialização AMAM-ILS são mostrados na tabela
6.2. Considerando-se que o método ILS é um método de processo de busca simples,
os resultados obtidos não se comparam com as melhores solução encontradas na
literatura, que foram obtidas, normalmente, por métodos híbridos. Entretanto, para
alguns problemas-teste, as soluções encontradas pela especialização não divergem
muito das melhores soluções, sendo que nos problemas-teste C208 e RC207 foram
obtidas solução bem próximas.
C101
C102
C103
C104
C105
C106
C107
C108
C109
C201
C202
C203
C204
C205
C206
C207
C208
R101
R102
R103
R104
R105
R106
R107
R108
R109
R110
R111
Prob.
Média
Melhor Solução
AMAM-ILS AMAM-ILS
1088,59 [12,5]
1064,0996 [13]
982,34 [10,5]
929,89 [10]
1035,74 [11]
917,59 [11]
1125,74 [11]
1124,59 [11]
1050,59 [12]
1009,69 [12]
1170,64 [12]
1121,39 [11]
1014,34 [11,5]
1003,69 [11]
1068,445 [12,5]
1024,39 [13]
1227,445 [12,5]
1129,5 [12]
639,59 [4]
638,79 [4]
1035,795 [4]
989,09 [4]
730,54 [5]
708,69 [5]
852,14 [4]
832,29 [4]
718,685 [3]
671,38 [3]
1093,045 [5]
1024,49 [5]
995,24 [5]
925,69 [5]
639,79 [3,5]
588,89 [3]
1910,59 [22,5]
1864,69 [22]
1609,645 [19,5]
1601,19 [13]
1358,15 [16]
1355,2 [16]
1100,15 [12,5]
1059,1 [12]
1611,49 [18,5]
1611,29 [18]
1416,945 [16]
1385,19 [15]
1246,45 [13,5]
1194,6 [14]
1067 [11]
1057,6 [11]
1387,045 [15,5]
1355,4 [15]
1236,15 [14]
1227,6 [14]
1215,7 [13]
1173,7 [12]
Melhor
Prob.
Solução Lit.
827,3 [10]
R112
827,3 [10]
R201
828,06 [10]
R202
824,78 [10]
R203
828,94 [10]
R204
827,3 [10]
R205
827,3 [10]
R206
827,30 [10]
R207
828,94 [10]
R208
591,56 [3]
R209
591,56 [3]
R210
591,17 [3]
R211
590,60 [3]
RC101
588,88 [3]
RC102
588,49 [3]
RC103
588,29 [3]
RC104
588,32 [3]
RC105
1607,70 [18] RC106
1434 [17]
RC107
1207 [13]
RC108
982,01 [10] RC201
1311,11 [14] RC202
1252,03 [12] RC203
1120,85 [10] RC204
968,59 [9]
RC205
1013,16 [12] RC206
1080,36 [11] RC207
1099,46 [10] RC208
Média
Melhor Solução
AMAM-ILS AMAM-ILS
1141,15 [12]
1127,6 [12]
1492,49 [6,5]
1394,29 [7]
1227,345 [6]
1186,39 [6]
1141,995 [4]
1132,29 [4]
978,1 [4]
961,7 [4]
1158,84 [5,5]
1109,89 [5]
1144,595 [5,5]
1132,9 [5]
943 [4]
908,6 [4]
834,75 [3]
813,9 [3]
1025,59 [5]
979,79 [5]
1118,995 [5]
1096,5 [5]
944,3 [4,5]
918,6 [4]
1923,29 [18,5]
1917,1 [19]
1636,695 [16,5]
1636,69 [16]
1572,49 [14,5]
1464,49 [14]
1350,945 [13,5]
1294,39 [13]
1910,05 [19,5]
1871,3 [19]
1601,94 [15]
1539,49 [15]
1450,245 [13,5]
1444,6 [13]
1425,095 [13]
1388,5 [13]
1527,04 [7,5]
1519,59 [7]
1435,24 [5,5]
1290,09 [5]
1373,79 [5]
1302,89 [5]
979,445 [4]
930,6 [4]
1490,94 [8,5]
1435,99 [8]
1303,595 [7]
1269,19 [7]
1117,895 [7]
1092,2 [7]
1060,745 [5]
1020,29 [5]
Tabela 6.2: Soluções do AMAM-ILS para o PRVJT.
Melhor
Solução Lit.
953,63 [10]
1252,37 [4]
1198,45 [3]
942,64 [3]
854,88 [2]
1013,47 [3]
833 [3]
814,78 [3]
726,82 [2]
855 [3]
955,39 [3]
910,09 [2]
1642,82 [15]
1540,97 [13]
1110 [11]
1135,83 [10]
1637,15 [13]
1395,37 [12]
1230,54 [11]
1139,82 [10]
1249 [4]
1164,25 [4]
1060,45 [3]
798,46 [3]
1302,42 [4]
1158,81 [3]
1068,86 [3]
833,4 [3]
6.4
80
6.4
Especialização AMAM-VNS
6.4.2
81
A especialização AMAM-VNS utiliza a mesma estrutura da instância anterior,
exceto o Agente Metaheurística que, neste caso, implementa o método Variable
Neighborhood Search. Desta forma, ela é composta pelos seguintes elementos (figura 6.11): Ambiente (PRVJT), Agente Construtor Guloso JT, Agente Busca Local
Descida, Agente Metaheurística VNS, Agente Coordenador, Agente Analisador de
Soluções.
Ambiente
Agente
Descida
Agente
Coordenador
Agente
VNS
Agente
Construtor
Guloso JT
Agente
Analisador
de Solução
Figura 6.11: AMAM-VNS.
Assim como na seção anterior, esta especialização tem o objetivo de apresentar os
resultados obtidos com o método VNS, atuando com um único Agente Metaheurística, e possibilitando sua comparação com as demais especializações desenvolvidas.
Os resultados obtidos pela especialização AMAM-VNS são apresentados na tabela 6.3. Os resultados obtidos nesta versão apresentam melhora significativa em
relação aos resultados apresentados na primeira versão da arquitetura AMAM, apresentada em Silva et al. (2006).
Embora a especialização AMAM-VNS, apresentada nesta seção, tenha encontrado soluções menores do que as melhores soluções da literatura nos casos dos
problemas testes C208 e R211, os resultados encontrados não se comparam as melhores soluções já encontradas. Isto considerando, como já dito aqui, que as melhores
soluções da literatura foram obtidas por métodos mais complexos.
C101
C102
C103
C104
C105
C106
C107
C108
C109
C201
C202
C203
C204
C205
C206
C207
C208
R101
R102
R103
R104
R105
R106
R107
R108
R109
R110
R111
Prob.
Média
AMAM-VNS
1105,89 [13,6]
1074,596667 [12]
1012,05 [11,3]
1091,47 [11]
1051,23 [12,4]
1178,202 [12,6]
1078,101 [12]
984,18 [11,4]
1036,682 [11]
643,33 [4]
1079,872 [4]
1044,79 [5]
813,79 [4]
691,79 [4]
761,99 [4]
771,77 [5]
602,565 [3,8]
1941,69 [22,7]
1625,294 [19,2]
1370,776 [16]
1101,958 [13]
1628,2 [18,8]
1395,014 [15,4]
1218,594 [13,6]
1068,79 [11,16]
1319,434 [15,4]
1213,898 [13,6]
1239,08 [14,8]
Melhor Solução
AMAM-VNS
950,7998 [12]
979,79 [12]
909,59 [11]
970,49 [11]
910,39 [11]
1077,7 [13]
1019,19 [12]
880,19 [10]
873,29 [10]
638,79 [4]
1027,89 [4]
1041,39 [5]
796,09 [4]
618,29 [4]
746,99 [4]
766,29 [5]
585,79 [3]
1863,59 [22]
1599,09 [19]
1345,3 [16]
1086,6 [13]
1578,8 [18]
1366,3 [15]
1194,29 [13]
1048,8 [10]
1292,09 [14]
1187,89 [13]
1186,5 [13]
Melhor
Solução Lit.
827,3 [10]
827,3 [10]
828,06 [10]
824,78 [10]
828,94 [10]
827,3 [10]
827,3 [10]
827,30 [10]
828,94 [10]
591,56 [3]
591,56 [3]
591,17 [3]
590,60 [3]
588,88 [3]
588,49 [3]
588,29 [3]
588,32 [3]
1607,70 [18]
1434 [17]
1207 [13]
982,01 [10]
1311,11 [14]
1252,03 [12]
1120,85 [10]
968,59 [9]
1013,16 [12]
1080,36 [11]
1099,46 [10]
R112
R201
R202
R203
R204
R205
R206
R207
R208
R209
R210
R211
RC101
RC102
RC103
RC104
RC105
RC106
RC107
RC108
RC201
RC202
RC203
RC204
RC205
RC206
RC207
RC208
Prob.
Média
AMAM-VNS
1166 [12]
1372,494 [7]
1372,494 [7]
1089,8 [4]
904,12 [4]
1190,674 [6]
1005,354 [5]
938,2 [4]
862,74 [3]
1107,09 [6]
1095,63 [6]
850,392 [5]
1924,37 [18,2]
1716,514 [16,6]
1497,636 [14,2]
1352,734 [13,4]
1848,254 [18,4]
1602,056 [15,2]
1381,14 [13]
1318,145 [12]
1524,49 [8]
1453,1 [6]
1373,1 [5]
1218,29 [4]
1642,3 [8]
1676,09 [8]
1379,7 [6]
1363,7 [6]
Tabela 6.3: Soluções do AMAM-VNS para o PRVJT.
Melhor Solução
AMAM-VNS
1153,2 [12]
1277,19 [5]
1277,19 [5]
1089,8 [4]
866,8 [4]
1129,09 [6]
962,2 [5]
922,6 [4]
827,3 [3]
1052,89 [6]
1093,59 [6]
840 [5]
1881,79 [19]
1612,89 [16]
1437,79 [14]
1323,09 [13]
1807,5 [18]
1570,2 [15]
1343,79 [13]
1257,29 [12]
1524 [8]
1453,1 [6]
1373,1 [5]
1118,29 [4]
1642,3 [8]
1676,09 [8]
1379,7 [6]
1363,7 [6]
Melhor
Solução Lit.
953,63 [10]
1252,37 [4]
1198,45 [3]
942,64 [3]
854,88 [2]
1013,47 [3]
833 [3]
814,78 [3]
726,82 [2]
855 [3]
955,39 [3]
910,09 [2]
1642,82 [15]
1540,97 [13]
1110 [11]
1135,83 [10]
1637,15 [13]
1395,37 [12]
1230,54 [11]
1139,82 [10]
1249 [4]
1164,25 [4]
1060,45 [3]
798,46 [3]
1302,42 [4]
1158,81 [3]
1068,86 [3]
833,4 [3]
6.4
82
6.4
Especialização AMAM-ILS-ILS
6.4.3
83
Em Talukdar et al. (1998) é introduzido um conceito relacionado ao efeito de
escala de uma organização baseada em computador. Assim, uma organização é considerada escala-efetiva (scale-effective) se seu desempenho melhora com o tamanho,
ou seja, se existem agentes, tais que sua adição melhora a qualidade das soluções
encontradas, e com computadores, cuja adição melhora a velocidade com que esta
solução de qualidade é obtida. Desta forma, em uma organização escala-efetiva,
é minimizado o esforço de adição de novos componentes. Entretanto, em contraponto, uma organização que não possui esta característica enfrenta problemas para
adicionar e modificar suas partes, tornando uma simples alteração uma situação
trabalhosa, com um grande impacto negativo sobre o desempenho global.
A partir deste conceito, três especializações da arquitetura AMAM foram implementadas para discutir esta característica, sendo elas: AMAM-ILS-ILS, AMAMVNS-VNS e AMAM-VNS-ILS.
A especialização da arquitetura AMAM-ILS-ILS acrescenta à especialização
AMAM-ILS um novo agente, implementando o mesmo método. Esta especialização
tem o objetivo de avaliar o desempenho cooperativo entre dois métodos iguais, considerando que, se possuem a mesma estrutura, podem cooperar trocando informações
da mesma região do espaço de busca.
Esta especialização é composta pelos seguintes elementos (figura 6.12): (1) Ambiente (PRVJT), (2) Agente Construtor Guloso JT, (3) Agente Busca Local Descida,
(4) e (5) Agentes Metaheurística ILS, (6) Agente Coordenador, (7) Agente Analisador de Soluções.
Ambiente
Agente
Coordenador
Agente
Descida
Agente
ILS
Lista Tabu
Agente
Construtor
Guloso JT
Agente
Analisador
de Solução
Agente
ILS
Figura 6.12: AMAM-ILS-ILS.
Os testes realizados com dois Agentes Metaheurística ILS buscam verificar se
o comportamento da arquitetura é escalável, ou seja, se a adição de novos agentes trabalhando em conjunto possibilitam um melhor desempenho na busca. Na
arquitetura proposta, novos agentes que implementam e encapsulam metaheurísticas específicas podem ser adicionados com o mínimo de impacto no restante da
arquitetura.
6.4
84
A principal forma de cooperação entre os Agentes Metaheurísticas, nesta especialização, é realizada através do sistema de comunicação quadro-negro. Esta
abordagem utiliza um repositório de dados, no qual os agentes podem ler e inserir
mensagens, como forma de interação. Aqui, este repositório tem a mesma formulação de uma lista tabu (veja figura 6.12), ou seja, soluções não recomendadas à
exploração são colocadas para que possam ser evitadas pelos agentes. Esta lista
foi implementada utilizando um vetor com tamanho igual ao número de clientes do
problema testes, sendo que funciona como uma lista circular, ou seja, quando a lista
está cheia, as novas soluções são inseridas novamente no início.
Os resultados alcançados pela especialização AMAM-ILS-ILS são apresentados
na tabela 6.4. A partir da comparação dos resultados médios obtidos desta especialização em relação às duas especializações anteriores (AMAM-ILS e AMAM-VNS),
a especialização AMAM-ILS-ILS encontrou, em 82% dos casos, soluções melhores.
O gráfico 6.13 apresenta um comparativo entre as especializações AMAM-ILS e
AMAM-ILS-ILS, sendo que os problemas-teste identificados no gráfico correspondem, respectivamente, aos problemas testes C101, C201, R101, R201, RC101 e
RC201 (os demais problemas-teste possuem características semelhantes). Para todos
os problemas presentes no gráfico, a especialização AMAM-ILS-ILS obteve melhor
solução.
2000
1800
1600
1400
1200
1000
AMAM-ILS
800
AMAM-ILS-ILS
600
400
200
0
C101
C201
R101
R201
RC101 RC201
Problemas-Teste
Figura 6.13: Gráfico comparativo do desempenho entre as especializações AMAMILS e AMAM-ILS-ILS.
C101
C102
C103
C104
C105
C106
C107
C108
C109
C201
C202
C203
C204
C205
C206
C207
C208
R101
R102
R103
R104
R105
R106
R107
R108
R109
R110
R111
Prob.
Média AMAMILS-ILS
1010,64 [12]
982,295 [11]
977,74 [12]
1129,295 [11]
1041,29 [12]
1098,99 [12]
1013,19 [11,5]
954,79 [11]
1025,695 [11]
632,89 [4]
737,19 [4]
819,04 [5]
731,49 [4]
586,39 [3]
727,64 [4]
819,04 [5]
601,89 [3,5]
1843,59 [22]
1575,74 [19]
1350,55 [15,5]
1065,795 [13]
1529,495 [18]
1366,495 [15]
1199,395 [13,5]
1049,1 [11]
1274,045 [14,5]
1213,795 [13,5]
1160,3 [14]
Melhor Solução
AMAM-ILS-ILS
999,59 [12]
979,59 [11]
967,49 [12]
1016,99 [11]
1015,79 [12]
1094,59 [12]
913,19 [11]
931,59 [11]
975,69 [11]
626,99 [4]
737,19 [4]
767,49 [5]
717,59 [4]
586,39 [3]
767,49 [4]
767,49 [5]
585,79 [3]
1779,79 [22]
1339,4 [15]
1339,4 [15]
1047,2 [12]
1516,99 [18]
1366,4 [15]
1196,49 [13]
1025,4 [11]
1264,6 [14]
1210,39 [13]
1130,4 [13]
Melhor Solução Lit.
827,3 [10]
827,3 [10]
828,06 [10]
824,78 [10]
828,94 [10]
827,3 [10]
827,3 [10]
827,30 [10]
828,94 [10]
591,56 [3]
591,56 [3]
591,17 [3]
590,60 [3]
588,88 [3]
588,49 [3]
588,29 [3]
588,32 [3]
1607,70 [18]
1434 [17]
1207 [13]
982,01 [10]
1311,11 [14]
1252,03 [12]
1120,85 [10]
968,59 [9]
1013,16 [12]
1080,36 [11]
1099,46 [10]
R112
R201
R202
R203
R204
R205
R206
R207
R208
R209
R210
R211
RC101
RC102
RC103
RC104
RC105
RC106
RC107
RC108
RC201
RC202
RC203
RC204
RC205
RC206
RC207
RC208
Prob.
Média AMAMILS-ILS
1141,595 [12,5]
1329,04 [7]
1274,59 [5]
1057,9 [4]
888,4 [4]
1102,045 [6]
970,94 [5]
916,145 [4]
789,75 [3]
1023,69 [6]
1062,74 [6]
862,19 [5]
1806,15 [17]
1626,095 [16]
1455,34 [13,5]
1289,89 [12,5]
1746,395 [17,5]
1503,995 [14]
1348,09 [13]
1305,795 [13]
1404,14 [8]
1253,195 [6]
1137,845 [5]
1010,49 [4]
1483,44 [8]
1239,745 [7,5]
1150,45 [5,5]
1154,19 [5,5]
Tabela 6.4: Soluções do AMAM-ILS-ILS para o PRVJT.
Melhor Solução
AMAM-ILS-ILS
1113,29 [12]
1309,09 [7]
979,59 [5]
1046 [5]
874,8 [4]
1081,29 [6]
964,09 [5]
907,1 [4]
789,6 [3]
1022,19 [6]
1037,89 [6]
838,49 [5]
1771,89 [17]
1607,59 [16]
1417,89 [13]
1249,39 [12]
1742,39 [17]
1470,99 [14]
1332,09 [13]
1293,2 [13]
1403,49 [8]
1234,3 [6]
1113,2 [5]
1003,79 [4]
1474,39 [8]
1221,69 [7]
1130,2 [5]
1108,79 [5]
953,63 [10]
1252,37 [4]
1198,45 [3]
942,64 [3]
854,88 [2]
1013,47 [3]
833 [3]
814,78 [3]
726,82 [2]
855 [3]
955,39 [3]
910,09 [2]
1642,82 [15]
1540,97 [13]
1110 [11]
1135,83 [10]
1637,15 [13]
1395,37 [12]
1230,54 [11]
1139,82 [10]
1249 [4]
1164,25 [4]
1060,45 [3]
798,46 [3]
1302,42 [4]
1158,81 [3]
1068,86 [3]
833,4 [3]
6.4
85
6.4
Especialização AMAM-VNS-VNS
86
Ambiente
Agente
Descida
Agente
Coordenador
Agente
VNS
Lista Tabu
Agente
Construtor
Guloso JT
Agente
Analisador
de Solução
Agente
VNS
Figura 6.14: AMAM-VNS-VNS.
6.4.4
Já a especialização da arquitetura AMAM-VNS-VNS acrescenta, à especialização
AMAM-VNS, um novo agente, implementando o mesmo método. Esta especialização tem o objetivo de avaliar o desempenho cooperativo entre dois métodos iguais,
agora, no caso, o método Variable Neighborhood Search.
(4) e (5) Agentes Metaheurística VNS, (6) Agente Coordenador, (7) Agente Analisador de Soluções.
6.4
87
2000
1800
1600
1400
1200
1000
AMAM-VNS
800
AMAM-VNS-VNS
600
400
200
0
C101
C201
R101
R201 RC101 RC201
Problemas-Teste
Figura 6.15: Gráfico comparativo do desempenho entre as especializações AMAMVNS e AMAM-VNS-VNS.
A forma de cooperação utilizada nesta especialização é semelhante à descrita
na seção anterior, acontecendo a troca de informações através de um repositório de
dados.
A tabela 6.5 apresenta os resultados obtidos nos testes realizados com a especialização AMAM-VNS-VNS. Em 74 % dos casos, a especilização AMAM-VNS-VNS
consegue atingir soluções melhores que as obtidas pelas especializações AMAM-ILS
e AMAM-VNS. O gráfico 6.15 mostra como a especialização utilizando dois agentes
VNS obtém melhores resultados que a especialização AMAM-VNS, que utiliza apenas um agente VNS. Os problemas-teste correspondem, respectivamente, às instâncias C101, C201, R101, R201, RC101 e RC201 (os demais problemas-teste possuem
características semelhantes).
Média AMAMVNS-VNS
1060,89 [12,5]
994,24 [11,5]
902,33 [11]
1066,89 [11]
1038,09 [12]
1087,39 [12]
976,59 [11,5]
896,09 [11]
999,395 [11]
632,89 [4]
1010,14 [4]
778,39 [5]
733,74 [4]
586,39 [3]
709,145 [4,5]
709,89 [4,5]
585,79 [3]
1813,74 [21,5]
1600,55 [19,5]
1372,445 [15,5]
1083,35 [13]
1521,395 [16]
1377,995 [16]
1199,09 [13]
1049,095 [11,5]
1249,395 [14,5]
1180,095 [13,5]
1220,85 [15]
Prob.
C101
C102
C103
C104
C105
C106
C107
C108
C109
C201
C202
C203
C204
C205
C206
C207
C208
R101
R102
R103
R104
R105
R106
R107
R108
R109
R110
R111
Melhor Solução
AMAM-VNSVNS
1045,39 [12]
972,09 [12]
918,7 [11]
1010,99 [11]
1006,49 [12]
1067,79 [12]
950,09 [11]
891,29 [11]
864,69 [10]
626,99 [4]
1001,2 [4]
753,29 [5]
706,69 [4]
586,39 [3]
707,09 [4]
707,19 [4]
585,79 [3]
1807,39 [22]
1588,1 [19]
1345 [16]
1075,5 [13]
1502,3 [16]
1360,59 [16]
1195,79 [13]
1047,89 [11]
1242,89 [14]
1174,49 [13]
1197,6 [15]
827,3 [10]
827,3 [10]
828,06 [10]
824,78 [10]
828,94 [10]
827,3 [10]
827,3 [10]
827,30 [10]
828,94 [10]
591,56 [3]
591,56 [3]
591,17 [3]
590,60 [3]
588,88 [3]
588,49 [3]
588,29 [3]
588,32 [3]
1607,70 [18]
1434 [17]
1207 [13]
982,01 [10]
1311,11 [14]
1252,03 [12]
1120,85 [10]
968,59 [9]
1013,16 [12]
1080,36 [11]
1099,46 [10]
R112
R201
R202
R203
R204
R205
R206
R207
R208
R209
R210
R211
RC101
RC102
RC103
RC104
RC105
RC106
RC107
RC108
RC201
RC202
RC203
RC204
RC205
RC206
RC207
RC208
Prob.
1064,75 [11,5]
1298,24 [7]
1247,59 [5]
1046 [4]
912,85 [4]
1070,345 [6]
1239,145 [5]
904,55 [4]
801,8 [3]
1027,34 [6]
1057,44 [6]
856,145 [5]
1815 [19,6]
1685,995 [15,5]
1402 [13]
1293,59 [12,5]
1721,1 [16,5]
1557,1 [14,5]
1375,8 [13]
1263,445 [12]
1463 [8]
1248,44 [6]
1147,64 [5]
992,34 [4]
1442,74 [8]
1266,54 [7]
1103,495 [5,5]
1128,945 [6]
Média AMAMVNS-VNS
Melhor Solução
AMAM-VNSVNS
1058,5 [11]
1280,09 [7]
1247,59 [5]
1046 [4]
901,8 [4]
1035 [6]
1229,39 [5]
902,9 [4]
792,7 [3]
996,59 [6]
1050,99 [6]
848,6 [5]
1810,1 [19]
1659,6 [15]
1399,7 [13]
1257,69 [12]
1701,3 [16]
1535,2 [14]
1367,2 [13]
1261,29 [12]
1463 [8]
1240,5 [6]
1121,49 [5]
976,79 [4]
1414,09 [8]
1251,69 [7]
1096,7 [5]
1086,6 [6]
Tabela 6.5: Soluções do AMAM-VNS-VNS para o PRVJT.
953,63 [10]
1252,37 [4]
1198,45 [3]
942,64 [3]
854,88 [2]
1013,47 [3]
833 [3]
814,78 [3]
726,82 [2]
855 [3]
955,39 [3]
910,09 [2]
1642,82 [15]
1540,97 [13]
1110 [11]
1135,83 [10]
1637,15 [13]
1395,37 [12]
1230,54 [11]
1139,82 [10]
1249 [4]
1164,25 [4]
1060,45 [3]
798,46 [3]
1302,42 [4]
1158,81 [3]
1068,86 [3]
833,4 [3]
6.4
88
6.4
Especialização AMAM-ILS-VNS
6.4.5
89
A especialização da arquitetura AMAM-ILS-VNS utiliza dois Agentes Metaheurística diferentes, sendo que um implementa o método ILS e o outro o método VNS.
O objetivo desta seção é verificar o comportamento da arquitetura utilizando agentes diferentes, considerando que estes possivelmente exploram regiões diferentes do
espaço de busca.
(4) Agente Metaheurística ILS, (5) Agente Metaheurística VNS, (6) Agente Coordenador, (7) Agente Analisador de Soluções.
Ambiente
Agente
VNS
Agente
Coordenador
Agente
Descida
Lista Tabu
Agente
Construtor
Guloso JT
Agente
Analisador
de Solução
Agente
ILS
Figura 6.16: AMAM-ILS-VNS.
2000
1800
1600
1400
1200
AMAM-ILS
1000
800
AMAM-VNS
600
AMAM-ILS-VNS
400
200
0
C101
C201
R101
R201 RC101 RC201
Problemas-Teste
Figura 6.17: Gráfico comparativo do desempenho entre as especializações AMAMILS, AMAM-VNS e AMAM-ILS-VNS.
A forma utilizada para cooperação entre os Agentes Metaheurísticas é a mesma
usada nas especializações anteriores.
6.4
90
O Gráfico 6.17 apresenta um comparativo entre as especializações AMAM-ILS
e AMAM-VNS com as especializações utilizando os dois agentes trabalhando em
conjunto, AMAM-ILS-VNS. Na maior parte dos resultados apresentados no gráfico,
a especialização AMAM-ILS-VNS obteve melhores valores para a função de avaliação, sendo que apenas em um caso sua solução ficou acima das soluções das demais
especializações.
Uma comparação entre as especializações que utilizam dois agentes trabalhando
em conjunto (AMAM-ILS-ILS, AMAM-VNS-VNS e AMAM-ILS-VNS) é apresentada no gráfico 6.18. As três especializações apresentaram comportamentos bem
próximos.
2000
1800
1600
1400
1200
AMAM-ILS-ILS
1000
800
AMAM-VNS-VNS
600
AMAM-ILS-VNS
400
200
0
C101
C201
R101
R201
RC101
RC201
Problemas-Teste
Figura 6.18: Gráfico comparativo do desempenho entre as especializações AMAMILS-ILS, AMAM-VNS-VNS e AMAM-ILS-VNS.
Os resultados encontrados pela especialização AMAM-ILS-VNS são apresentados
na tabela 6.6. Em 75% dos casos, a especialização AMAM-ILS-VNS conseguiu
resultados melhores que os obtidos pelas especializações AMAM-ILS e AMAM-VNS.
Média AMAMILS-VNS
995,39 [12,5]
1014,295 [11]
918,295 [11]
1062,11 [11]
906,445 [11]
1090,895 [12]
947,395 [11]
994,945 [11]
895,89 [10]
701,14 [3,5]
732,99 [4]
737,99 [5]
700,795 [4]
600,195 [3]
767,64 [4]
720,89 [5]
633,155 [4]
1859,94 [21,5]
1579,945 [19]
1341,25 [15]
1048,29 [12,3]
1602,4 [18,2]
1380,89 [15,6]
1204,55 [13,6]
1058,43 [11]
1302,29 [11,4]
1193,88 [13,2]
1201,44 [13,8]
Prob.
C101
C102
C103
C104
C105
C106
C107
C108
C109
C201
C202
C203
C204
C205
C206
C207
C208
R101
R102
R103
R104
R105
R106
R107
R108
R109
R110
R111
Melhor Solução
AMAM-ILSVNS
955,39 [12]
1014,295 [11]
918,295 [11]
1062,11 [11]
906,445 [11]
1090,895 [12]
947,395 [11]
994,945 [11]
895,89 [10]
638,79 [4]
732,99 [4]
737,99 [5]
700,795 [4]
600,195 [3]
767,64 [4]
720,89 [5]
633,155 [4]
1859,94 [21]
1579,945 [19]
1341,25 [15]
1021,2 [12]
1590,39 [18]
1360,78 [15]
1187,58 [13]
1033,49 [11]
1264,6 [11]
1185,3 [13]
1160,54 [13]
827,3 [10]
827,3 [10]
828,06 [10]
824,78 [10]
828,94 [10]
827,3 [10]
827,3 [10]
827,30 [10]
828,94 [10]
591,56 [3]
591,56 [3]
591,17 [3]
590,60 [3]
588,88 [3]
588,49 [3]
588,29 [3]
588,32 [3]
1607,70 [18]
1434 [17]
1207 [13]
982,01 [10]
1311,11 [14]
1252,03 [12]
1120,85 [10]
968,59 [9]
1013,16 [12]
1080,36 [11]
1099,46 [10]
R112
R201
R202
R203
R204
R205
R206
R207
R208
R209
R210
R211
RC101
RC102
RC103
RC104
RC105
RC106
RC107
RC108
RC201
RC202
RC203
RC204
RC205
RC206
RC207
RC208
Prob.
1156,4 [12,6]
1268,39 [7]
1271,04 [5]
1046 [4]
870,2 [4]
1094,59 [5,4]
985,39 [5]
926,89 [4]
803,67 [3]
1001,39 [5,8]
1082,3 [6]
878,1 [5]
1820,7 [21]
1642,945 [16]
1387,5 [13,2]
1267,4 [12,4]
1714,99 [17,3]
1560,39 [14,3]
1353,43 [13]
1260,98 [12]
1446,25 [8]
1249,78 [6]
1154,9 [5]
921,59 [4]
1486 [8]
1304,67 [7,3]
1145,33 [5,8]
1056,4 [5,2]
Média AMAMILS-VNS
Melhor Solução
AMAM-ILSVNS
1118,49 [12]
1264,89 [7]
1266,49 [5]
1046 [4]
870,2 [4]
1064,39 [5]
970,59 [5]
813,55 [4]
789,6 [3]
979,79 [5]
1058,4 [6]
838,9 [5]
1820,7 [21]
1589,2 [16]
1365,19 [13]
1224 [12]
1703,55 [17]
1504,43 [14]
1332,09 [13]
1222,99 [12]
1402,79 [8]
1234,3 [6]
1109,45 [5]
913,87 [4]
1474,39 [8]
1243,54 [7]
1126,4 [5]
1020,29 [5]
Tabela 6.6: Soluções do AMAM-ILS-VNS para o PRVJT.
953,63 [10]
1252,37 [4]
1198,45 [3]
942,64 [3]
854,88 [2]
1013,47 [3]
833 [3]
814,78 [3]
726,82 [2]
855 [3]
955,39 [3]
910,09 [2]
1642,82 [15]
1540,97 [13]
1110 [11]
1135,83 [10]
1637,15 [13]
1395,37 [12]
1230,54 [11]
1139,82 [10]
1249 [4]
1164,25 [4]
1060,45 [3]
798,46 [3]
1302,42 [4]
1158,81 [3]
1068,86 [3]
833,4 [3]
6.4
91
6.5
6.5
92
Embora a arquitetura não seja específica para um determinando problema de otimização combinatória, especializações da arquitetura foram desenvolvidas com o
objetivo de mostrar o correto funcionamento da arquitetura e, também, para apontar suas características de escalabilidade, encapsulamento e flexibiliade.
Os experimentos computacionais realizados com as cinco especializações desenvolvidas (AMAM-ILS, AMAM-VNS, AMAM-ILS-ILS, AMAM-VNS-VNS e AMAMILS-VNS) da arquitetura proposta mostram como estas característica estão presentes.
A escalabilidade, que corresponde ao aumento do desempenho a partir da adição
de novos agentes, foi confirmada, considerando a melhora efetiva nos valores das
funções de avaliação, obtida nas especializações com dois agentes metaheurísticas
trabalhando em conjunto, em relação às especializações com apenas um agente.
Capítulo 7
Conclusões Gerais e Trabalhos
Futuros
7.1
Conclusões Gerais
Neste trabalho é introduzida uma arquitetura multiagente para a solução de
problemas de otimização combinatória, através do uso de metaheurísticas. Neste
sentido, uma revisão dos principais conceitos relacionados com Sistemas Multiagentes e Metaheurísticas é apresentada, assim como a discussão de alguns trabalhos
correlatos ao tema tratado.
A partir da análise destes trabalhos similares à arquitetura aqui proposta foram definidos alguns aspectos desejáveis a uma arquitetura multiagente para metaheurísticas. Considerando os aspectos relacionados na seção 5.2, buscou-se, então,
incluí-los na arquitetura.
A classificação das metaheurísticas utilizada como base deste trabalho separa
estas entre metaheurísticas baseadas em um único ponto e metaheurísticas baseadas
em população, buscando, assim, identificar as características particulares à cada
uma delas. Neste sentido, tantos os métodos pontuais quanto populacionais são
facilmente adicionados na arquitetura proposta.
Na arquitetura proposta, nomeada AMAM, as metaheurísticas são definidas
como agentes que atuam na exploração do espaço de busca de forma autônoma.
Assim, diferentes soluções iniciais, formas de refinamento e valores para os parâmetros da busca podem ser usados para cada busca independente, o que resulta
em uma “decomposição” do espaço de busca. Esta decomposição permite que cada
agente explore uma região diferente do ambiente (espaço de busca), obtendo assim,
através da troca de informações, um maior conhecimento do mesmo.
Desta forma, os agentes possuem capacidades de comunicação entre si e com o
seu ambiente, possibilitando um comportamento cooperativo que tende a atingir um
objetivo comum, ou seja, encontrar uma “boa” solução.
A arquitetura AMAM define um framework que permite a comparação do desempenho das diversas metaheurísticas na solução de um determinado problema. Da
mesma forma, a arquitetura AMAM se mostra flexível o bastante para solucionar diferentes problemas de otimização, sem grande impacto no restante da arquitetura. A
adição de novos agentes (metaheurísticas) também é facilitada, já que a arquitetura
define um framework para metaheurísticas híbridas, à qual se somam as vantagens
93
7.2
Trabalhos Futuros
94
da abordagem multiagente, tais como cooperação.
As especializações apresentadas permitem a avaliação experimental da arquitetura proposta, indicando como as características destacadas anteriormente estão
presentes.
Assim, a arquitetura se apresenta de forma escalável, já que as especializações utilizando dois agentes cooperando na busca por soluções obtiveram resultados melhores do que as especializações desenvolvidas com apenas um agente. Adicionalmente,
novos agentes podem ser facilmente adicionados, sem que alterações significativas
sejam necessárias.
A cooperação é a característica determinante no que diz respeito à melhora nos
resultados apresentados na utilização de agentes trabalhando em conjunto e com o
mesmo objetivo.
7.2
Trabalhos Futuros
Algumas perspectivas de continuidade da definição da arquitetura AMAM são:
(i) Implementação da arquitetura com todas as metaheurísticas apresentadas
neste trabalho, assim como as demais metaheurísticas conhecidas;
(ii) Utilização da arquitetura na solução de diferentes problemas de otimização
combinatória;
(iii) Maior exploração da capacidade de busca cooperativa;
(iv) Exploração das possibilidades de inclusão na arquitetura dos métodos de intensificação e diversificação;
(vi) Extensão da arquitetura para a utilização de recursos de computação paralela
e/ou distribuída.
Referências Bibliográficas
Andreatta, A. A.; Carvalho, S. E. R. e Ribeiro, C. C. (1998). An object-oriented
framework for local search heuristics. Proceedings of TOOLS 1998: the 26th International Conference on Technology of Object-Oriented Languages and Systems, p.
33–45, Santa Barbara, CA, USA.
Avila-Abascal, P. e Talukdar, S. N. (1996). Cooperative algorithms and abductive causal networks for the automatic generation of intelligent substation alarm
processors. Proceedings of ISAP’1996 - the International Conference on Intelligent
Systems Applications to Power Systems, Orlando, FL, EUA.
Bäck, T. (1996). Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press,
New York, NY, EUA.
Bertsimas, D. e Tsitsiklis, J. (1997). Introduction to Linear Optimization. Athena
Scientific, Belmont, Massachusetts, EUA.
Birattari, M.; Paquete, L.; Stützle, T. e Varrentrapp, K. (2001). Classification of
metaheuristics and design of experiments for the analysis of components. Relatório Técnico AIDA-01-05, Fachgebiet Intellektik, Fachbereich Informatik, Technische
Universität Darmstadt.
Bleale, R. e Jackson, T. (1990). Neural Computing: An Introduction. Institute of
Physics Publishing, Bristol, Reino Unido.
Blum, Christian e Roli, Andrea. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, v. 35, n. 3,
p. 268–308.
Booch, G.; Rumbaugh, J. e Jacobson, I. (1998). The Unified Modeling Language
User Guide. Addison-Wesley, Reading, Mass, EUA, 1a edição.
Boudali, I.; Fki, W. e Ghedira, K. (2004). How to deal with the vrptw by using multiagent coalitions. HIS 2004: Proceedings of the Fourth International Conference on
Hybrid Intelligent Systems (HIS’04), p. 416–421, Kitakyushu, Japan.
Bouthilliera, Alexandre Le e Crainic, Teodor Gabriel. (2005). A cooperative parallel
meta-heuristic for the vehicle routing problem with time windows. Computers &
Operations Research, v. 32, p. 1685–1708.
95
96
Brooks, R. A. (1991). Intelligence without representation. Artificial Intelligence, v.
47, p. 139–159.
Burke, E. K.; Kendall, G.; Silva, D. L. e Soubeiga, R. O’Brien E. (2005). An ant
algorithm hyperheuristic for the project presentation scheduling problem. The 2005
IEEE Congress on Evolutionary Computation, volume 3, p. 2263–2270, (2005).
Burke, E.K.; Silva, J.D. Landa e Soubeiga, E. (2003). Hyperheuristic approaches
for multi-objective optimisation. Selected Papers from the 2003 Metaheuristics International Conference, Kyoto Japan.
Chen, C. L. Bayesian Nets and A-Teams for Power System Fault Diagnosis. PhD
thesis, Dept. of Electrical and Computer Engineering, Carnegie Mellon University,
Pittsburgh, PA, EUA, (1992).
Chen, S. Y.; Talukdar, S. N. e Sadeh, N. M. (1993). Job-shop-scheduling by a team
of asynchronous agents. Proceedings of IJCAI-93 - Workshop on Knowledge-Based
Production, Scheduling and Control, Chambery, France.
Claro, J. e Sousa, J. P. (2001). An object-oriented framework for multiobjective
local search. Proceedings of MIC’2001 - the Fourth Metaheuristics International
Conference, volume 1, p. 231–236, Porto, Portugal.
Cooper, James W. (2000). Java design patterns: a tutorial. Addison-Wesley, Reading, Mass, EUA.
Corkill, Daniel D. (1991). Blackboard systems. AI Expert, v. 9, n. 6, p. 40–47.
deSouza, P. S. Asynchronous Organizations for Multi-Algorithm Problems. PhD
thesis, Dept. of Electrical and Computer Engineering, Carnegie Mellon University,
Pittsburgh, PA, EUA, (1993).
Demazeau, Y. (2003). Multi-agent systems methodology. ESD2003 - 2a Escuela Franco-Mexicana sobre los Sistemas Distemas Distribuidos Cooperativos,
http://lafmi.lania.mx/escuelas/esd03/ponencias/Demazeau.pdf.
Dorigo, M. Optimization, learning and natural algorithms (in Italian). PhD thesis,
Dipartimento di Elettronica, Politecnico di Milano, Milan, Itália, (1992).
Dorigo, Marco e Blum, Christian. (2005). Ant colony optimization theory: A survey.
Theoretical Computer Science, v. 344, n. 2–3, p. 243–278.
Dorigo, Marco e Di Caro, Gianni. (1999). The Ant Colony Optimization metaheuristic. Corne, David; Dorigo, Marco e Glover, Fred, editors, New Ideas in Optimization, Capítulo 2, p. 11–32. McGraw-Hill, London, Reino Unido.
Dorigo, Marco; Maniezzo, Vittorio e Colorni, A. (1996). Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and
Cybernetics - Part B, v. 26, n. 1, p. 29–41.
97
Dowsland, K. A. (1993). Simulated annealing. Reeves, Colin R., editor, Modern
Heuristic Techniques for Combinatorial Problems, Advanced Topics in Computer
Science, p. 20–69, New York, NY, USA. John Wiley & Sons.
Dowsland, K. A. e Dowsland, W. B. (1992). Packing problems. European Journal
of Operational Research, v. 56, n. 1, p. 2–14.
Driankov, D.; Hellendoorn, H. e Reinfrank, M. (1990). An Introduction to Fuzzy
Control. Springer-Verlag, Berlin, Alemanha, 1a edição.
Feo, T. A. e Resende, M. G. C. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization, v. 6, n. 2, p. 109–133.
Ferreira, S. L. C. Aplicação de Arquiteturas baseadas em Agentes em Sistemas de
Acesso à Informação. Monografia, Ciência da Computação. Universidade Federal
do Maranhão, (2002).
Fraga, Marcelo C. P. Uma metodologia híbrida colônia de formigas-busca tabureconexão por caminhos para resolução do problema de roteamento de veículos com
janelas de tempo. Dissertação de Mestrado, Mestrado em Modelagem Matemática
e Computacional, CEFET-MG, Belo Horizonte, MG, (2006).
Frigo, L. B.; Pozzebon, E. e Bittencourt, G. (2004). O papel dos agentes inteligentes
nos sistemas tutores inteligentes. Brito, C. R. e Ciampi, M. M, editors, Proceedings
of WCETE’2004 - the World Congress on Engineering and Technology Education,
p. 667–671, Guarujá / Santos, SP, Brasil.
Gamma, Erich; Helm, Richard; Johnson, Ralph e Vlissides, John. (1995). Design
Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, Reading,
Mass, EUA, 1a edição.
Glover, F. (1986). Future paths for integer programming and links to artificial
intelligence. Computers & Operations Research, v. 13, n. 5, p. 533–549.
Glover, F. e Laguna, M. (1998). Tabu Search. Springer-Verlag, Berlin, Alemanha.
Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization, and Machine
Learning. Addison Wesley, Reading, MA, EUA.
Gorti, S. R.; Humair, S; Sriram, R. D.; Talukdar, S. e Murthy, S. (1996). Solving
constraint satisfaction problems using a-teams. Artificial Intelligence for Engineering Design, Analysis and Manufacturing, v. 10, n. 1, p. 1–19.
Gras, Robin; Hernandez, David; Hernandez, Patricia; Zangger, Nadine; Mescam, Yoann; Frey, Julien; Martin, Olivier; Nicolas, Jacques e Appel, Ron D. (2003). Cooperative metaheuristics for exploring proteomic data. Artificial Intelligence Review,
volume 20, p. 95–120, (2003).
Hansen, P.; Mladenovic, N. e Moreno, J. A. (2003). Variable neighbourhood search.
Revista Iberoamericana de Inteligencia Artificial, v. 7, n. 19, p. 77–92.
98
Hasen, P. e Mladenovic, N. (1999). An introduction to variable neighborhood search.
Voß, S.; Martello, S.; Osman, I. e Roucairol, C., editors, Metaheuristics: Advances
and trends in local search paradigms for optimization, p. 433–438. Kluwer Academic
Publishers, Norwell, MA, EUA.
Hasen, P. e Mladenovic, N. (2001). Variable neighborhood search: Principles and
applications. European Journal of Operational Research, v. 130, n. 3, p. 449–467.
Henderson-Sellers, B. e P. Giorgini, Editors. (2005). Agent-Oriented Methodologies.
Idea Group Publishing, Hershey, PA, EUA.
Ho-Chen, Chia e Ting, Ching-Jung. (2005). A hybrid ant colony system for vehicle routing problem with time windows. Journal of the Eastern Asia Society for
Transportation Studies, v. 6, p. 2822–2836.
Kefi, M. e Ghedira, K. (2004). A multi-agent model for a vehicle routing problem
with time windows. Proceeding of International Urban Transport’04, Germany.
Kirkpatrick, S.; Gelatt, C. D. e Vecchi, M. P. (1983). Optimization by simulated
annealing. Science, v. 220, p. 671–680.
Koza, J. R. (1992). Genetic Programming: On the Programming of Computers by
Means of Natural Selection. MIT Press, Cambridge, Massachusetts, EUA.
Lau, H.C. e Wang, H. (2005). Multi-agent approach for solving optimization problems involving expensive resources. Proceedings of the 2005 ACM Symposium on
Applied Computing, p. 79–83, Santa Fé, New Mexico, EUA.
Leong, H. W. e Liu, M. (2006). A multi-agent algorithm for vehicle routing problem
with time windows. Proceedings of SAC 2006 - the 21st Annual ACM Symposium
on Applied Computing, p. 23–27, Dijon, France.
Lesser, Victor R. (1999). Cooperative multiagent systems: A personal view of the
state of the art. IEEE Transactions on Knowledge and Data Engineering, v. 11, n.
1, p. 133–142.
Lourenço, H. R.; Martin, O. e Stützle, T. (2001). A beginner’s introduction to
iterated local search. MIC 2001 - Proceedings of the 4th Metaheuristics International
Conference, volume 1, Porto, Portugal.
Lukin, J. A.; Gove, A. P.; Talukdar, S. N. e Ho, C. (1997). Automated probabilistic
method for assigning backbone resonances of (13c, 15n)-labelled proteins. Journal
of Biomolecular NMR, v. 9, p. 151–166.
Machado, M. L. M.; deSouza, D. G.; Souza, J. A.; Dandolini, G. A. e Silveira, R. A.
(2004). Rpg: Uma abordagem empregando sistemas multiagentes. Revista Novas
Tecnologias na Educação, v. 2, n. 1.
Milano, M. e Roli, A. (2004). Magma: a multiagent architecture for metaheuristics.
IEEE Transaction on Systems Man and Cybernetics, v. 34, n. 2.
99
Moulin, B. e Chaib-draa, B. (1996). An overview of distributed artificial intelligence.
O’Hare, G. M. P. e Jennings, N. R., editors, Foundations of distributed artificial
intelligence, Sixth Generation Computer Technology Series, p. 1–56, New York,
NY, EUA. John Wiley & Sons.
Nwana, H.S. (1996). Software agents: An overview. Knowledge Engineering Review,
v. 11, n. 3, p. 205–244.
Odell, J.; Parunak, V.; Fleischer, M. e Breuckner, S. (2003). Modeling agents and
their environment. Giunchiglia, Fausto; Odell, James e Weiß, Gerhard, editors,
Agent-Oriented Software Engineering III, Third International Workshop, AOSE
2002, Bologna, Italy, July 15, 2002, Revised Papers and Invited Contributions, volume 2585 of Lecture Notes in Computer Science, Berlin, Alemanha. Springer.
Osman, I. H. e Laporte, G. (1996). Metaheuristics: A bibliography. Annals of
Operations Research, v. 63, p. 513–628.
Parunak, H. Van Dyke. (1997). “go to the ant”: Engineering principles from natural
multi-agent systems. Annals of Operations Research, v. 75, p. 69–101.
Passos, C. A. S. e Fonseca, S. L. A. (2005). Uma arquitetura multiagente para
a solução de problemas de sequenciamento da produção. INFOCOMP Journal of
Computer Science, v. 4, n. 2, p. 38–45.
Pitsoulis, L. S. e Resende, M. G. C. (2002). Greedy randomized adaptive search
procedures. Pardalos, P.M. e Resende, M.G.C., editors, Handbook of Applied Optimization, p. 168–183. Oxford University Press.
Platon, E.; Mamei, M.; Sabouret, N.; Honiden, S. e Parunak, H. V. D. (2007).
Mechanisms for environments in multi-agent systems: Survey and opportunities.
Autonomous Agents and Multi-Agent Systems, v. 14, n. 1, p. 31–47.
Resende, S. O. (2003). Sistemas Inteligentes - Fundamentos e Aplicações. Manole,
Porto, Portugal.
Rizzoli, A. E.; Oliverio, F.; Montemani, R. e Gambardella, C. M. (2004). Ant
colony optimization fo vehicle routing problem: from theory to application. Relatório
Técnico IDSIA-15-04, IDSIA - University of Lugano.
Russell, S. e Norvig, P. (1995). Artificial Intelligence: a Modern Approach. PrenticeHall, Englewood Cliffs, NJ, EUA.
Santos, Bruno A. Aspectos conceituais e arquiteturais para a criação de linhagens
de agentes de software cognitivos e situados. Dissertação de Mestrado, Mestrado em
Tecnologia, CEFET-MG, Belo Horizonte, MG, (2003).
Silva, M. A. L.; deSouza, S. R.; Borges, H. E.; Oliveira, S. M. e Temponi, E. C. C.
(2007). Amam: Arquitetura multiagente para a solução, via metaheurísticas, de problemas de otimização combinatória. SBAI 2007 - Anais do VII Simpósio Brasileiro
Automação Inteligente, Florianópolis, Brasil.
100
Silva, M. A. L.; deSouza, S. R. e Oliveira, S. M. (2006). Uma proposta de arquitetura multiagente para a solução via metaheurísticas do problema de roteamento de
veículos com janela de tempo. EMC 2006 - Anais do IX Encontro de Modelagem
Computacional, Belo Horizonte, Brasil.
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems
with time window constraints. Operations Research, v. 2, n. 35, p. 254–264.
Talukdar, S.; Baerentzen, L.; Gove, A. e deSouza, P. S. (1998). Asynchronous teams:
Cooperation schemes for autonomous agents. Journal of Heuristics, v. 4, n. 4, p.
295–321.
Talukdar, S. N. e Souza, P. S. (1990). Asynchronous teams. Proceedings of the
Second SIAM Conference on Linear Algebra: Signals, Systems and Control, San
Francisco, CA, EUA.
Thangiah, S.R.; Shmygelska, O. e Mennell, W. (2001). An agente architecture
for vehicle routing problems. Proceedings of the 2001 ACM Symposium on Applied
Computing, p. 517–521, Las Vegas, Nevada, EUA.
Toth, P. e Vigo, D. (2002). The Vehicle Routing Problem. SIAM - Society for
Industrial and Applied Mathematics, Philadelphia.
Valckenaers, P.; Sauter, J.; Sierra, C. e Rodriguez-Aguilar, J. A. (2007). Applications
and environments for multi-agent systems. Autonomous Agents and Multi-Agent
Systems, v. 14, n. 1, p. 61–85.
Vallada, Eva e Ruiz, Rubén. (2007). Cooperative metaheuristics for the permutation
flowshop scheduling problem. Anais do 22nd European conference on operational
research, Praga, Rep. Tcheca.
Weiss, Gerhard. (2000). Multiagente Systems: A Modern Approach to Distributed
Artificial Intelligence. MIT Press, Cambridge, MA, EUA, 1a edição.
Weyns, Danny; Omicini, Andrea e Odell, James. (2007). Environment as a first class
abstraction in multiagent systems. Autonomous Agents and Multi-Agent Systems,
v. 14, n. 1, p. 5–30.
Weyns, Danny; Parunak, H. Van Dyke; Michel, Fabien; Holvoet, Tom e Ferber, Jacques. (2005). Environments for multiagent systems state-of-the-art and research
challenges. E4MAS, volume 3374 of Lecture Notes in Computer Science, p. 1–47.
Springer, (2005).
Wooldridge, M. (2002). An Introduction to Multiagent Systems. John Wiley & Sons,
New York, NY, EUA, 1a edição.
Wooldridge, M. e Jennings, N. R. (1995). Intelligent agents: Theory and practice.
Knowledge Engineering Review, v. 10, n. 2, p. 41–59.

Modelagem de uma Arquitetura Multiagente para a Solução, via

Transcrição

Documentos relacionados

Minimum Spanning Tree Algoritmos de Prim e Kruskal Algoritmo de

Quien sabe, hace... ¿Y quién no sabe? ¿Enseña? Resumo Create

Algoritmo para converter uma temperatura em Fahrenheit para

Problema da Árvore Geradora Mínima

Sistemas de Informação ENADE 2005

o que compreendem? que dificuldades apresentam?

Algoritmo de Prim

ANALISE DE ALGORITMOS

introdução a algoritmos e programação

introdução a algoritmos e programação