UNIVERSIDADE ANHEMBI MORUMBI
MÁRIO CÉSAR MANCINELLI DE ARAÚJO
RAFAEL CLARET DE BARROS
ANÁLISE E IMPLEMENTAÇÃO DE UMA SOLUÇÃO SEQUENCIAL E DISTRIBUÍDA
PARA A RESOLUÇÃO DO PROBLEMA DA COBERTURA DE CONJUNTOS
UTILIZANDO O ALGORITMO ANT SYSTEM
São Paulo
2009
MÁRIO CÉSAR MANCINELLI DE ARAÚJO
RAFAEL CLARET DE BARROS
ANÁLISE E IMPLEMENTAÇÃO DE UMA SOLUÇÃO SEQUENCIAL E
DISTRIBUÍDA PARA A RESOLUÇÃO DO PROBLEMA DA COBERTURA DE
CONJUNTOS UTILIZANDO O ALGORITMO ANT SYSTEM
Trabalho de conclusão de curso apresentada como exigência
parcial para obtenção do título de Bacharel em Ciência da
Computação da Universidade Anhembi Morumbi.
Orientador: Augusto Mendes Gomes Junior
São Paulo
2009
A69
Araújo, Mário César Mancinelli de
Análise e implementação de uma solução seqüencial
distribuída para a resolução do problema da cobertura de
conjuntos utilizando o algoritmo Ant System / Mário César
Macinelli de Araújo, Rafael Claret de Barros. – 2009.
64f.: il; 30 cm.
Orientador: Prof. Augusto Mendes Gomes Junior.
Trabalho de Conclusão de Curso (Graduação em
Ciência da Computação) – Universidade Anhembi Morumbi,
São Paulo, 2009.
Bibliografia: f. 50-52.
1. Ciência da Computação. 2. Cobertura de Conjuntos. 3.
Ant System. I. Título.
CDD 004
MÁRIO CÉSAR MANCINELLI DE ARAÚJO
RAFAEL CLARET DE BARROS
ANÁLISE E IMPLEMENTAÇÃO DE UMA SOLUÇÃO SEQUENCIAL E
DISTRIBUÍDA PARA A RESOLUÇÃO DO PROBLEMA DA COBERTURA DE
CONJUNTOS UTILIZANDO O ALGORITMO ANT SYSTEM
Trabalho de conclusão de curso apresentada como exigência
parcial para obtenção do título de Bacharel em Ciência da
Computação da Universidade Anhembi Morumbi.
Aprovado em
____________________________________________________
Prof. Msc. AUGUSTO MENDES GOMES
Universidade Anhembi Morumbi
____________________________________________________
Prof. MARCELO ALEXANDRE COUTO DE JESUS
Universidade Anhembi Morumbi
____________________________________________________
Prof. LUIS FERNANDO AIRES BRANCO
Universidade Anhembi Morumbi
RESUMO
Por representar problemas comuns, o Problema de Cobertura de Conjuntos é de
grande uso, além de existir um grande esforço para encontrar algoritmos que resolvam
problemas como este em um tempo que seja polinomial em relação ao tamanho da entrada.
Por este motivo, o Problema de Cobertura de Conjuntos é o objeto de estudo desse trabalho,
que também objetiva a implementação de uma solução sequencial e outra distribuída,
utilizando a heurística Ant System. Por pertencer à classe de complexidade NP-Completo, o
Problema de Cobertura de Conjuntos tem a característica de que, à medida que o tamanho da
entrada aumenta, o tempo para a sua resolução cresce exponencialmente. Devido a isso, a
utilização de algoritmos heurísticos tem se tornado algo cada vez mais interessante, pois
permitem obter boas soluções (porém não ótimas) em um curto tempo e espaço de busca. A
estratégia deste trabalho é inicialmente implementar a solução sequencial e, posteriormente,
distribuída. O benefício desta estratégia é que, implementando primeiro a versão sequencial
do algoritmo, testes podem ser realizados, visando melhorar seu desempenho e heurística
para, a partir dela, implementar a versão distribuída. Finalmente, são realizados testes e
comparações, de forma a avaliar tanto a qualidade dos resultados quanto o desempenho da
solução.
Palavras-chave: Problema de Cobertura de Conjuntos, Heurística, Ant System, Distribuição.
ABSTRACT
Because it represents common problems, the Set Covering Problem is of great use,
and there is a large effort to find algorithms that could solve problems like this in a time that
is polynomial in the input size. Because of that, the Set Covering Problem is the main subject
of this project, which also aims to implement a distributed solution and another sequential,
using the Ant System heuristic. To belong to the complexity class NP-Complete, the Set
Covering Problem has the feature that as the size of the problem grows, time required to solve
the problem grows exponentially. Because of this, the use of heuristic algorithms has become
something more interesting; they can obtain good solutions (but not great) in a short space of
time and search. The strategy of this project is initially developing the sequential solution, and
subsequently distributed. The benefit of this strategy is that by developing the sequential
version of the algorithm first, tests can be done to improve it’s performance and heuristic to,
based on that version, develop the distributed version. Finally, tests and comparisons are
made in order to measure the quality of results and the performance of the solution.
Keywords: Set Covering Problem, Heuristic, Ant System, Distribution.
LISTA DE FIGURAS
Figura 1: Função exponencial genérica associada ao SCP ....................................................... 15
Figura 2: Representação do Problema de Cobertura de Conjuntos .......................................... 16
Figura 3: SCP associado a rotas e pontos de ônibus ................................................................ 17
Figura 4: Instancia (X, F) do SCP ............................................................................................ 19
Figura 5: Algoritmo Greedy ..................................................................................................... 19
Figura 6: Otimização de Colônia de Formigas ......................................................................... 21
Figura 7: Esquema das Experiências adaptado de Goss (1989) ............................................... 24
Figura 8: Ant System no problema de cobertura de conjuntos................................................. 26
Figura 9: Exemplo de representação do TSP ............................................................................ 28
Figura 10: Representação de SCP por matriz ........................................................................... 31
Figura 11: Fluxograma do Modelo da Solução ........................................................................ 33
Figura 12: Estratégia de distribuição da solução ...................................................................... 38
LISTA DE GRÁFICOS
Gráfico 1: Comparações dos Custos: Ótimo vs. Sequencial vs. Distribuído ........................... 45
Gráfico 2: Comparação dos Tempos de Execução: Sequencial vs. Distribuído ...................... 46
Gráfico 3: Speedup da Versão Distribuída ............................................................................... 46
LISTA DE TABELAS
Tabela 1: Arquivos fonte utilizados no teste ............................................................................ 36
Tabela 2: Testes preliminares de variações de depósito de feromônio .................................... 36
Tabela 3: Resultados dos testes de valores do parâmetro de evaporação ................................. 37
Tabela 4: Arquivos fonte dos problemas utilizados ................................................................. 42
Tabela 5: Resultados dos testes do parâmetro de influência do feromônio (α) ........................ 43
Tabela 6: Resultados dos testes do parâmetro de influência da função custo (β) .................... 44
Tabela 7: Valores adotados para os parâmetros do algoritmo Ant Sysytem ............................. 44
Tabela 8: Resultados Testes - dos Custos: Ótimo vs. Sequencial vs. Distribuído ................... 44
Tabela 9: Resultados dos Testes - Tempos de Execução: Sequencial vs. Distribuído ............. 45
LISTA DE SIGLAS
ACO
Ant Colony Optimization: Otimização por Colônias de Formigas
AG
Algoritmo Genético
AG-SCP
Algoritmo Genético aplicado ao Problema de Cobertura de Conjuntos
AS
Ant System: Sistema de Formigas
AS-JSP
Heurística Ant System aplicada ao Problema de Escalonamento de Job-Shop
AS-SCP
Heurística Ant System aplicada ao Problema de Cobertura de Conjuntos
HAS-SOP
Heurística Ant System aplicada ao Problema de Ordenação Sequencial
JSP
Job-Shop Scheduling Problem: Problema de Escalonamento de Job-Shop
MPI
Message Passing Interface: Interface de Passagem de Mensagens
PGA
Problema Generalizado de Atribuição
SCP
Set Covering Problem: Problema de Cobertura de Conjuntos
SD
Sistema Distribuído
SOP
Sequential Ordering Problem: Problema de Ordenação Sequencial
TSP
Traveling Salesman Problem: Problema do Caixeiro Viajante
SUMÁRIO
1
INTRODUÇÃO ............................................................................................................. 11
1.1
OBJETIVOS ................................................................................................................... 12
1.2
JUSTIFICATIVA............................................................................................................ 12
1.3
ABRANGÊNCIA............................................................................................................ 13
1.4
ESTRUTURA DO TRABALHO .................................................................................... 14
2
COBERTURA DE CONJUNTOS ............................................................................... 15
2.1
DEFINIÇÃO ................................................................................................................... 15
2.2
APLICAÇÕES ................................................................................................................ 17
2.2.1 Problema da transversal mínima ................................................................................. 17
2.2.2 Problema de localização de máxima disponibilidade ................................................ 18
2.2.3 Problema Generalizado de Atribuição ........................................................................ 18
2.2.4 Detecção de Vírus .......................................................................................................... 18
2.3
TRABALHOS RELACIONADOS ................................................................................. 19
2.3.1 Solução usando o Algoritmo Guloso de Aproximação .............................................. 19
2.3.2 Solução usando o Algoritmo Genético ........................................................................ 20
2.3.3 Solução usando o Ant System Colony ......................................................................... 21
3
ANT SYSTEM ............................................................................................................... 23
3.1
DEFINIÇÃO ................................................................................................................... 23
3.2
FUNCIONAMENTO NO SCP ....................................................................................... 25
3.3
FEROMÔNIO ................................................................................................................. 26
3.4
EVAPORAÇÃO ............................................................................................................. 27
3.5
TRABALHOS RELACIONADOS ................................................................................. 28
3.5.1 Ant System e o Problema do Caixeiro Viajante ......................................................... 28
3.5.2 Problema de Escalonamento de Job-Shop .................................................................. 29
3.5.3 Problema da Ordenação Sequencial............................................................................ 30
4
MODELAGEM E IMPLEMENTAÇÃO SEQUENCIAL DO SCP......................... 31
4.1
MODELO DA SOLUÇÃO ............................................................................................. 32
4.2
FUNÇÃO CUSTO .......................................................................................................... 33
4.3
GERAÇÃO DAS SOLUÇÕES ....................................................................................... 34
4.4
FEROMÔNIO ................................................................................................................. 35
4.5
EVAPORAÇÃO ............................................................................................................. 37
5
MODELAGEM E IMPLEMENTAÇÃO DISTRIBUÍDA DO SCP ........................ 38
5.1
ESTRATÉGIA DE RESOLUÇÃO ................................................................................. 38
5.2
IMPLEMENTAÇÃO COM MPI .................................................................................... 39
5.2.1 Funcionamento do Mestre ............................................................................................ 40
5.2.2 Funcionamento do Escravo .......................................................................................... 41
6
TESTES E ANÁLISE DOS RESULTADOS .............................................................. 42
6.1
AMBIENTE DE TESTE ................................................................................................. 43
6.2
TESTES .......................................................................................................................... 43
6.3
ANÁLISE DOS RESULTADOS.................................................................................... 47
7
CONCLUSÃO ............................................................................................................... 48
7.1
TRABALHOS FUTUROS ............................................................................................. 48
REFERÊNCIAS BIBLIOGRÁFICAS ...............................................................................50
APÊNDICE A – CÓDIGO FONTE DA VERSÃO SEQUENCIAL ...........................53
APÊNDICE B – CÓDIGO FONTE DA VERSÃO DISTRIBUÍDA ...........................58
11
1
INTRODUÇÃO
Problemas pertencentes à categoria NP-Completos (GAREY; JOHNSON, 1979) são
problemas em que à medida que o tamanho da entrada aumenta o tempo para a sua resolução
cresce exponencialmente.
Na teoria da complexidade computacional, a classe de complexidade NP-completo é o
subconjunto dos problemas de decisão em NP de tal modo que todo problema em NP pode ser
reduzido a um dos problemas NP-completo (CORMEN, 2002).
A importância desta classe de problemas é que ela contém muitos problemas de busca
e otimização, nos quais se deseja saber se existe uma solução possível. Dentre os problemas,
pode-se destacar:
a) Escalonamento: de operações de manufatura, de vôos, de aulas;
b) Encaminhamento: veículos, chamadas telefônicas, bits, petróleo;
c) Isomorfismo de grafos: verificar se dois grafos têm correspondência entre seus
vértices e arestas, de tal maneira que a relação de incidência seja preservada (ou
seja, se podem ser desenhados de forma idêntica);
d) Caminho Hamiltoniano: verificar se determinado grafo possui um caminho que
permita passar por todos os vértices sem que haja repetições, ou seja, sem que seja
necessário visitar o mesmo vértice mais de uma vez;
e) Cobertura de conjuntos: definir o conjunto mínimo que consiga cobrir todas as
localidades do problema.
Segundo Cormen (2002, p. 815):
O problema de cobertura de conjuntos é um problema de otimização que modela
muitos problemas de seleção de recursos. Seu problema de decisão correspondente
generaliza o problema de cobertura de vértices NP-completo e, por tanto, também
NP-difícil.
Por representar problemas comuns, o problema de cobertura de conjuntos é de grande
uso. E por precisar processar um grande número de entrada de dados em tempo razoável, uma
solução que seja próxima do ótimo é aceitável.
Uma abordagem possível na busca dessas soluções é utilizar um algoritmo heurístico
associado ao problema, em que dado um tempo suficiente, pode encontrar não a solução
ótima, mas sim uma muito boa que esteja bem próxima da ótima, com baixo tempo
computacional (LOPES, 1995).
Algoritmos heurísticos (RUSSELL, 2004) são algoritmos não-determinísticos que
resolvem determinado problema, encontrando uma solução aproximada, ao deduzir os
melhores passos através de estimativas sob forma de heurísticas. Algoritmos heurísticos
12
aplicados a esse tipo de problema têm tornado-se cada vez mais atraentes e utilizados, pois
permitem obter boas soluções (porém não ótimas) para problemas de combinação em um
curto tempo e espaço de busca.
Em comparação com as técnicas exatas, os algoritmos heurísticos (RUSSELL, 2004)
não garantem encontrar uma solução ótima após atingirem um critério de parada; mas estes
têm demonstrado alta eficiência em problemas de larga combinação para casos práticos, além
de poderem ser modificados facilmente, adaptando-se ao problema analisado (GOLDBARG,
2000).
Hoje é muito fácil construir sistemas computacionais compostos por um grande
número de computadores ligados através de redes de alta velocidade. Tais sistemas são
chamados SDs, em contraste com os Sistemas Centralizados, compostos por um único
processador, memória e periféricos (TANENBAUM, 2007).
O ponto forte da descentralização é a questão econômica. Porque por pouco dinheiro,
pode-se comprar um computador cujo microprocessador que execute mais instruções/segundo
que os maiores mainframes da década de 80. Portanto, a melhor solução em termos de custo
atualmente é juntar um grande número de computadores baratos em um único sistema, afinal,
estes sistemas têm melhor relação preço/performance do que os sistemas centralizados
(TANENBAUM, 2007).
1.1
OBJETIVOS
O objetivo é a modelagem e implementação de uma solução sequencial e distribuída
utilizando um algoritmo heurístico, para solucionar um problema pertencente à classe NPcompleto. O problema abordado é o Problema da Cobertura de Conjuntos e o algoritmo
utilizado é o Ant System. Este trabalho aborda e estuda algoritmos heurísticos e sua aplicação
em problemas de NP-Completo.
1.2
JUSTIFICATIVA
Os problemas pertencentes à classe NP possuem a característica de demandar grande
tempo computacional para sua resolução de forma ótima (polinomial ou super-polinomial),
pois à medida que o tamanho da entrada de dados aumenta, o tempo de processamento cresce
exponencialmente.
13
Devido ao fato de existirem muitos problemas importantes nesta classe, existe um
grande esforço para encontrar algoritmos que resolvam problemas NP em um tempo que seja
polinomial em relação ao tamanho da entrada. Contudo, existe um grande número de
problemas NP que resiste a tais tentativas, parecendo requerer um tempo super-polinomial. Se
estes problemas realmente não podem ser resolvidos em tempo polinomial é um das grandes
questões abertas na ciência da computação.
Devido a isso, é interessante a utilização de um algoritmo heurístico que visa encontrar
uma boa solução, e não a ótima, em um tempo computacional muito menor. A paralelização e
distribuição de processamento entre diferentes processadores/computadores também pode
diminuir o tempo de execução do algoritmo.
Esta área de Otimização combinada com Processamento de Alto Desempenho está
crescendo bastante nos últimos anos, pois o hardware evoluiu para multicore, porém as
aplicações não se adaptaram a isto. O método para esta adaptação é a utilização de recursos
computacionais, como threads e mecanismos de sincronização (TANENBAUM, 2007).
1.3
ABRANGÊNCIA
O projeto abrange o estudo do problema de cobertura de conjuntos, assim como a
modelagem e implementação de uma solução sequencial e de uma solução distribuída
utilizando um algoritmo Ant System para solucioná-lo.
O projeto não abrange o estudo da complexidade dos problemas de cobertura de
conjunto ou de nenhum outro problema de NP-completo. Também não estuda a complexidade
do algoritmo Ant System, o qual foi escolhido para servir de base para implementação.
As comparações são realizadas entre os resultados obtidos com a versão sequencial e a
versão distribuída, com os resultados obtidos pelo trabalho Implementação De Uma Solução
Paralela Para A Resolução Do Problema De Cobertura De Conjuntos Utilizando Algoritmo
Genético de CARDOSO et al. (2008), assim como com os resultados das soluções ótimas dos
problemas, que são conhecidas.
A implementação distribuída será concebida a partir da versão seqüencial, visando
otimizar o processo de busca de soluções.
Os testes foram realizados em um computador Intel (R) Core(TM) 2 Duo CPU de
2.20GHz, 2,00GB de memória RAM, com o sistema operacional Microsoft Windows XP
Professional Service Pack 3.
14
1.4
ESTRUTURA DO TRABALHO
O trabalho está dividido da seguinte maneira:
a) Capítulo 2: Este capítulo aborda o problema de cobertura de conjuntos, sua
definição, aplicações do mesmo e trabalhos relacionados a este problema;
b) Capítulo 3: Este capítulo aborda o algoritmo Ant System, sua definição, o que
seria o feromônio e a evaporação, além de trabalhos que utilizaram uma
abordagem com este algoritmo;
c) Capítulo 4: Este capítulo aborda a modelagem e implementação de uma solução
sequencial para o problema de cobertura de conjuntos. Explora o modelo da
solução, a função custo, a geração das soluções, o feromônio e a evaporação;
d) Capítulo 5: Este capítulo aborda a modelagem e implementação de uma solução
distribuída para o problema de cobertura de conjuntos. Explora a estratégia de
resolução, uma implementação que utiliza de sockets para a comunicação e de
outra que utiliza MPI para a comunicação;
e) Capítulo 6: Este capítulo aborda os testes e a análise dos resultados. Explora o
ambiente de testes, os testes em si e faz a análise dos resultados;
f) Capítulo 7: Este capítulo conclui do trabalho, assim como lista possíveis trabalhos
futuros.
15
2
COBERTURA DE CONJUNTOS
CONJUNT
O problema de cobertura de conjuntos (Set Covering Problem - SCP) é motivo de
grande interesse devido a sua complexidade e principalmente aplicabilidade. Em outras
palavras, ele facilita a representação de problemas práticos e comuns do nosso cotidiano tais
tai
como planejamento de construções, alocações de equipamentos ou serviços criados para um
determinado propósito (CAMBRIDGE, 1995).
Porém, o SCP é um problema pertencente à classe NP-Completo,
NP Completo, o que quer dizer que
o tempo computacional gasto para a resolução
resoluçã do problema aumenta exponencialmente à
medida que os dados de entrada crescem.
crescem
Para contextualizar a discussão sobre o significado do fato de um algoritmo levar
tempo exponencial para obter a solução de um problema, considere um algoritmo que execute
em tempo proporcional a 2ⁿ,
2 como visto na Figura 1. Isso significa que não é garantido que o
algoritmo possa obter a resposta para todos os problemas de tamanho n = 100 ou maior,
porque o tempo computacional seria excessivo,
excessivo que seria de 2¹ºº passos para terminar
term
sua
tarefa, independente da velocidade do computador. (ZINVIANI, 2007).
2007)
NP
NP-Completo
(Função Exponencial)
1200
Tempo
1000
800
600
400
200
0
1
2
3
4
5
6
7
8
9
10
Entrada de Dados
Figura 1: Função exponencial genérica associada ao SCP. Fonte: O Autor, 2009.
2.1
DEFINIÇÃO
O SCP é um problema de otimização que modela muitos problemas de seleção de
recursos (CORMEN, 2002).
2002)
Este problema pode ser definido através de um conjunto de localidades e facilidades,
facilidades
as quais são representadas respectivamente por ● e círculos na Figura 2. Com
Co isso pode-se
supor que uma determinada quantidade (conjunto) de localidades é coberta por uma facilidade
16
a um determinado custo (CARDOSO
CARDOSO et al., 2008, p.13).
). A Figura 2 mostra várias localidades
sendo cobertas por círculos de facilidades.
Figura 2: Representação do Problema de Cobertura de Conjuntos. Fonte: O Autor, 2009.
Por
or pertencer a classe NP-completo,
NP completo, tem seu tempo computacional gasto crescendo
exponencialmente a medida que crescem os dados de entrada, assim tornando-se
tornando inviável em
uma situação com grande massa de dados. Portanto, é aceitável uma solução aproximada (não
uma ótima), desde que tenha tempo computacional razoável.
Com a definição de facilidades, podem ser feitas analogias ao conceito de hospitais
para atender uma região (TOREGAS, 1971), bem como supermercados, fábricas, escolas,
bibliotecas, bombeiros (WALKER, 1974), componentes de um circuito integrado (FRANCIS,
1974).
Matematicamente, uma instância (X, F) do SCP é um conjunto finito de X e uma
família F de subconjuntos
ubconjuntos de X, de forma que todo elemento X pertence a pelo menos um
subconjunto em F,, como vemos na Equação 1.
1
(1)
Diz-se
se que um subconjunto S pertencente a F cobre seus elementos. O problema então
é encontrar um subconjunto de tamanho mínimo L ⊆ F cujos conjuntos membros cubram todo
o X,, conforme a Equação 2.
(2)
815)
Finalmente, qualquer L que satisfaz à Equação 2 cobre X (CORMEN, 2002, p. 815).
17
Um problema clássico do SCP é o problema de rotas de ônibus (facilidades) para
atender os pontos (localidades) de uma cidade. O custo para se fazer essa cobertura poderia
ser o tempo gasto, a distância percorrida, etc. Na Figura 3(a), os pontos de ônibus são
representados pelos pontos e na Figura 3(b) as rotas de ônibus que cobrem esses pontos são
representadas pelas linhas, como um exemplo de pontos que são cobertos (CARDOSO et al.,
2008, p.14).
(a)
(b)
Figura 3: SCP associado a rotas e pontos de ônibus. Fonte: CARDOSO et al., 2008.
2.2
APLICAÇÕES
O SCP pode ser utilizado para a modelagem de diversos problemas que visam otimizar
combinações de possibilidades de cobertura. E devido a sua grande aplicabilidade e
possibilidade de obter bons resultados com baixo tempo de processamento utilizando técnicas
heurísticas (CALVI, 2005), várias soluções são geradas a partir de seu uso.
2.2.1
Problema da transversal mínima
O problema da transversal mínima consiste em encontrar a menor transversal em um
grafo orientado. O grafo orientado é um conjunto de arcos (ou vértices) que corta todos os
circuitos orientados do grafo. Ou seja, uma transversal em um grafo orientado G é um
conjunto T de arcos (ou vértices) tal que G-T é acíclico.
Este problema é NP-difícil, é equivalente ao conhecido problema da cobertura de
conjuntos (Set Covering Problem) (HOCHBAUM, 1997). Devido a essa equivalência,
resultados para o problema da cobertura de conjuntos podem ser transformados em resultados
para o problema da transversal mínima (RUCHKYS; SONG, 2002).
18
2.2.2
Problema de localização de máxima disponibilidade
Os primeiros modelos desenvolvidos para a localização de serviços de emergência
foram determinísticos. O mais simples dos modelos matemáticos existentes para problemas de
localização com restrições de cobertura determinísticos é correspondente ao Problema de
Localização para a Cobertura de Conjuntos, que consiste na determinação do número mínimo
de facilidades e de sua localização, de tal forma que cada área de demanda esteja a uma
distância menor do que a crítica, de pelo menos uma das facilidades localizadas (GALVÃO et
al., 2002).
2.2.3
Problema Generalizado de Atribuição
O Problema Generalizado de Atribuição (PGA) é um problema de otimização
combinatória NP-completo (SAHNI; GONZALEZ, 1976). Sua importância decorre não
apenas de sua aplicabilidade direta, mas também do fato de aparecer como um subproblema
de muitos outros problemas práticos mais complexos. O problema pode ser estabelecido como
o de determinar uma atribuição de custo mínimo de n tarefas a m máquinas de forma que cada
tarefa é atribuída a apenas uma máquina cuja capacidade deve ser respeitada. Aplicações do
PGA aparecem em problemas como roteamento de veículos (FISHER; JAIKUMAR, 1981),
localização de facilidades (ROSS; SOLAND, 1977), escalonamento de recursos (MAZOLLA
et al., 1989), dentre outros.
2.2.4
Detecção de Vírus
Em um trabalho realizado na IBM foi aplicado o SCP para procurar por vírus de
computador. Para isso, foram usados os seguintes parâmetros:
a) Elementos: vírus conhecidos (cerca de 5000);
b) Conjuntos: sequências de 20 ou mais bytes consecutivos dos vírus, não
encontradas em código comum (cerca de 9000 no total).
Um conjunto de cerca de 180 foi descoberto, o que significa que procurar por essas
180 sequências é suficiente para verificar a existência dos vírus de computador conhecidos.
Finalmente, usando o algoritmo Greedy, uma solução de 190 sequências foi
encontrada. O valor de relaxamento da programação linear era 185, então a solução ótima
tinha ao menos 185 sequências. Deste modo, a solução Greedy ficou bastante próxima da
ótima (WILLIAMSON, 1999).
19
2.3
TRABALHOS RELACIONADOS
RELACIONAD
Pelo SCP pertencer à classe NP-completo
NP
(com tempo computacional exponencial em
relação
ação à quantidade de dados de entrada) e por ser utilizado para modelar diversos problemas
de otimização combinatória, é aceitável uma solução aproximada (não uma ótima), desde que
tenha tempo computacional razoável. Portanto, o desenvolvimento de algoritmos
algoritm heurísticos
que produzam boas soluções em um tempo computacional aceitável é necessário.
necessário
O problema de decisão ao qual o SCP corresponde é o problema de cobertura de
vértices. Porém, os algoritmos de aproximação desenvolvidos para tratar o problema de
cobertura
obertura de vértices não se aplica ao SCP, assim outras abordagens precisam ser tentadas
(CORMEN, 2002). Alguns algoritmos já foram desenvolvidos e oss principais são descritos
nos itens a seguir.
2.3.1
Solução usando o Algoritmo Guloso de Aproximação
O funcionamento do método guloso é simples. Em cada fase ele escolhe um conjunto
S,, o qual cobre o maior número de elementos ainda descobertos (CORMEN, 2002).
2002)
Na Figura 4, os 12 (doze)
(do
pontos formam o X e os S’s
’s formam o F, portanto F = (S1,
S2, S3, S4, S5, S6).. Uma cobertura mínima seria L = (S3, S4, S5).. O algoritmo guloso produz
uma cobertura de tamanho 4 (quatro), ficando C = (S1, S4, S5 e S3) (CORMEN, 2002).
Figura 4: Instancia (X, F) do SCP. Fonte: CORMEN, 2002.
O algoritmo usado para isto é o Greedy, exibido na Figura 5.
Figura 5: Algoritmo Greedy. Fonte: O Autor, 2009.
20
O algoritmo Greedy não retorna um resultado muito maior que uma cobertura ótima
neste caso e é executada em um tempo polinominal (CORMEN, 2002). Contudo, para
problemas maiores e mais complexos, esse tipo de algoritmo acaba se mostrando pouco
eficiente, pois sua solução passa a se distanciar da ótima.
2.3.2
Solução usando o Algoritmo Genético
O Algoritmo Genético (AG) foi desenvolvido com o objetivo de solucionar problemas
relacionados à Inteligência Artificial (HOLLAND, 1975), baseado no conceito de Seleção
Natural proposto por Charles Darwin.
Um AG é um algoritmo no qual os estados sucessores são gerados pela combinação de
dois estados pais, em vez de serem gerados pela modificação de um só estado. Portanto,
estamos lidando com “reprodução sexuada”, não com “reprodução assexuada” (RUSSELL,
2004).
Beasley (1987) propôs um algoritmo exato para o SCP, o qual combina testes de
redução com subida dual (dual ascent), otimização de subgradiente e programação linear.
Neste artigo são exibidos resultados para problemas envolvendo até 400 linhas e 4000
colunas.
Beasley e Chu (1996) apresentaram um novo algoritmo genético para resolver o SCP,
chamado GA-SCP. Os autores fizeram várias modificações no AG básico adicionando um
novo operador crossover chamado fusão, o qual foi baseado no fitness dos pais. Também
introduziram uma taxa de mutação variável e um operador heurístico desenhado
especialmente para o SCP. Os testes foram realizados sobre 65 problemas de diversos
tamanhos com até 1000 linhas e 10000 colunas.
O GA-SCP desenvolvido por Beasley e Chu possui os seguintes passos:
1°. Gera a população inicial com N soluções aleatórias. Então, inicializa o índice de
iteração como t ← 0;
2°. Seleciona duas soluções P1 e P2 pertencentes à população, usando o processo de
seleção por torneio;
3°. Combina P1 e P2 para formar uma nova solução C, através do operador de
reprodução por fusão;
4°. Faz mutação de k facilidades da solução C, escolhidas aleatoriamente;
5°. Torna C viável e, caso exista, remove suas facilidades redundantes. Incrementar t
← t +1;
21
6°. Escolhe uma solução com capacidade de adaptação menor à capacidade média da
população e a substitui
substitu por C.
Se a solução ótima não foi encontrada, e o tempo de execução atual for menor que o
tempo máximo (pré-estabelecido),
estabelecido), então retornar ao 2° passo. Caso contrário, parar e retornar
a melhor solução obtida.
Essee processo de seleção, cruzamento e mutação é repetido sucessivamente
sucessiva
até que
uma solução satisfatória seja desenvolvida ou tempo limite de parada seja alcançado. Pelo
fato de serem escolhidos os indivíduos mais aptos a cada nova geração,
geração são eliminados
aqueles
ueles que não teriam chances de sobreviver e gerar descendentes, ou seja, não gerariam
soluções adequadas (CARDOSO et al., 2008, p.19).
p.1
2.3.3
Solução usando o Ant System Colony
O método de otimização por colônias de formigas (ACO), fundamentado por Marco
Dorigo (1996), foi baseado no
n comportamento de colônias de formigas reais, conforme
exemplifica a Figura 6.. O método consiste em um processo probabilístico em que,
que
inicialmente, se tem um conjunto N de formigas dispersas de forma aleat
eatória, como visto na
Figura 6 quadro A. E estas começam a mover-se, escolhendo qualquer um dos possíveis
caminhos, como visto na Figura 6 quadro B, pois neste momento todos os caminhos têm a
mesma quantidade de feromônio,
feromônio que é uma substância química utilizada
lizada pelas formigas no
processo de comunicação. Conforme passa o tempo, acontece o processo de depósito e
evaporação do feromônio,, como visto na Figura 6 quadro C, as formigas começam a escolher
o melhor caminho (que tem mais feromônio) entre todos os vistos,
stos, o qual será considerado a
melhor solução,, como visto na Figura 6 quadro D (CARDOSO et al., 2008, p.17).
Figura 6: Otimização de Colônia de Formigas. Fonte: CARDOSO et al., 2008.
22
O processo de escolha da melhor solução para o SCP, utilizando ACO, consiste no
depósito de feromônio nos caminhos (facilidades) em que, segundo um critério probabilístico
pré-estabelecido, foram considerados mais otimizados do que os outros existentes. Assim, um
maior número de formigas acaba utilizando estes caminhos, não repondo feromônio nos
demais (considerados desfavoráveis). Este processo é repetido N vezes com outros caminhos,
até que as formigas comecem a tender para o mesmo caminho, ou seja, a melhor solução
dentre todas as pesquisadas/possíveis (SILVA, 2006).
23
3
ANT SYSTEM
O presente capítulo apresenta uma série de processos oriundos da meta-heurística de
otimização para funções reais, que simulam o comportamento de uma espécie de formiga à
procura de alimentos, processo conhecido como Ant Colony Optimization (ACO) ou Ant
System (AS) (DORIGO; CARO, 1999a; DORIGO; CARO, 1999b), sob a inspiração das
experiências com formigas reais realizadas por Goss, Aron, Deneuborg, e Pasteels (GOSS et
al., 1989).
Esta espécie de formiga é caracterizada por uma estratégia de caça onde cada
indivíduo demarca pequenas regiões de busca em torno da colônia, de modo a cobrir todo o
espaço em torno da mesma. Além disso, a colônia é mudada periodicamente de lugar à
medida que o alimento se torna escasso, o que significa que a pesquisa é feita tanto local
quanto globalmente na região que cerca tal colônia. Em experimentos realizados com algumas
funções reais clássicas utilizadas para testes o algoritmo mostrou um excelente desempenho
fornecendo sempre uma solução idêntica ou melhor do que a solução obtida por outros
algoritmos similares.
3.1
DEFINIÇÃO
As formigas são insetos sociais que possuem um complexo sistema de organização e
divisão de tarefas, tendo como função principal a garantia de sobrevivência do formigueiro. O
método de otimização de formigas (ACO) fundamentado por Marco Dorigo (1996) partiu do
estudo do comportamento de formigas reais.
O método se baseia na capacidade de grupos de formigas de apresentar
comportamento coletivo muito mais inteligente que o que uma formiga sozinha seria capaz de
fazer. Inicialmente um número de formigas percorre as proximidades do formigueiro em
busca do alimento. Cada formiga, ao percorrer o seu caminho, deposita uma substância
chamada feromônio, formando um caminho ou rastro de feromônio. Posteriormente as
formigas subseqüentes seguem o caminho com maior concentração de feromônio, ou seja,
onde há a maior passagem de formigas (DORIGO; CARO, 1999c).
A experiência realizada com formigas reais por GOSS, ARON, DENEUBOURG e
PASTEELS (GOSS et al., 1989), serviu de inspiração à criação do método de otimização de
colônia de formigas. Esta experiência consistia na submissão de uma colônia de formigas
24
Iridomyrex humilis a uma fonte de alimento através de dois caminhos distintos,
distintos conforme a
Figura 7.
Figura 7: Esquema das Experiências adaptado de Goss (1989). Fonte: GOSS et al., 1989.
O planejamento do experimento foi feito de maneira que as formigas, ao percorrerem
ambas as direções, tivessem
vessem sempre que optar por um ou outro caminho (Figura 7a). Após
uma fase transitória, a maioria das formigas acabava escolhendo
escolhe
um mesmo caminho.
caminho Assim
a probabilidade de selecionar o menor caminho aumentava, à medida que a diferença de
tamanho entre os caminhos
os aumentava (SILVA, 2006).
Tal
al comportamento é devido a uma substância chamada feromônio,
feromônio a qual é
depositada pelas formigas durante sua locomoção. Quando as formigas chegam a um ponto de
decisão, como a bifurcação entre dois caminhos, elas fazem uma escolha
esco
probabilística
baseada na quantidade de feromônio presente em cada uma das opções.. Ou seja, quanto maior
a quantidade de feromônio em um caminho, maior a probabilidade deste ser escolhido
(SILVA, 2006).
Inicialmente, não existe feromônio nos caminhos, portanto a probabilidade de escolha
é a mesma para ambos. Entretanto, quando os caminhos têm a mesma distância, a maior
concentração de feromônio naquele caminho com um pouco mais de formiga, estimulará mais
formigas a segui-lo;
lo; e assim cada vez mais, até que a grande maioria das formigas acabe
optando pelo mesmo,, como mostrado na Figura 7b (SILVA, 2006).
Quando os caminhos têm distâncias diferentes,, a taxa de formigas que chegam à fonte
de alimentos pelo menor caminho é maior do que a taxa de formigas que chegam pelo maior
caminho. Da mesma forma,
forma no retorno ao ninho as formigas encontrarão
encontrar mais feromônio
sobre o menor caminho, o que estimulará
estimula mais formigas a segui-lo, fazendo com que cada vez
mais formigas acabem optando pelo mesmo (SILVA, 2006).
25
Recentemente, algoritmos baseados no AS têm sido aplicados em problemas de
cobertura, como o problema de roteamento de veículos, coloração de grafos, roteamento de
comunicação de rede, e assim por diante (DORIGO; CARO, 1999c).
3.2
FUNCIONAMENTO NO SCP
Segundo SILVA (2006), quando aplicado ao SCP, o AS inicia com h formigas, as
quais são distribuídas pelas facilidades (colunas ou componentes do problema) segundo
algum critério pré-estabelecido, e todas as facilidades j ∈ J são iniciadas com a mesma
quantidade τj(1) > 0 j de feromônio (Figura 8, linha 1).
Em seguida, cada formiga k (k = 1,..., h) seleciona as próximas facilidades a serem
visitadas (Figura 8, linhas 5-6), através da regra de decisão probabilística da Equação 3
(SILVA, 2006).
(3)
Onde, segundo SILVA (2006):
a) t: iteração atual da heurística AS-SCP;
b) pkij(t): probabilidade da facilidade j ser escolhida pela formiga k, atualmente
situada na facilidade i, durante a t-ésima iteração da heurística AS-SCP;
c) τj(t): quantidade de feromônio sobre a facilidade j ∈ J na t-ésima iteração;
d) α: parâmetro que regula a influência de τj(t);
e) ηj =
: visibilidade da facilidade j com relação à facilidade i;
f) cj: custo da facilidade j;
g) U: conjunto de localidades atualmente descobertas;
h) Ij: conjunto de localidades cobertas pela facilidade j ∈ J;
i) |⋅|: operador de cardinalidade de conjuntos;
j) β: parâmetro que regula a influência de ηj;
k) Nki(t): conjunto de facilidades ainda não visitadas pela formiga k, atualmente
situada na facilidade i, nesta t-ésima iteração de AS-SCP.
A Equação 3 determina que a chance da facilidade j ser escolhida é diretamente
proporcional ao valor do feromônio de j multiplicado pelo valor da função custo de j; e é
inversamente proporcional ao valor da somatória da probabilidade de todas as facilidades
26
ainda não visitadas. Outro detalhe é que o valor do feromônio é elevado a α (parâmetro que
regula a influência do feromônio) e o valor da função custo é elevado a β (parâmetro que
regula a influência da função custo).
custo)
Este processo de seleção da próxima facilidade a ser visitada é repetido até que todas
as formigas tenham encontrado uma solução viável ψ para SCP (Figura 8, linha 4) (SILVA,
2006).
Todos os procedimentos
procedimentos citados são repetidos a cada iteração da heurística AS.
Contudo, quando o número máximo de iterações previamente estabelecido é alcançado
(Figura 8, linha 2), a heurística Ant System retorna a melhor solução ψ* encontrada até então
(Figura 8, linha 14)
4) (SILVA, 2006).
Figura 8: Ant System no problema de cobertura de conjuntos. Fonte: SILVA (2006).
3.3
FEROMÔNIO
A comunicação
ção entre formigas é feita por meio
eio do resíduo de feromônio,
feromônio o qual elas
depositam por onde passam.
passam Nesse contexto, que é base para o AS, o mecanismo que surge
dessa comunicação é a formação de caminhos que, em
e um determinado momento, a maioria
das formigas passa a utilizar.
ilizar. Vale notar que,
que à medida que o tempo passa, o feromônio
depositado vai evaporando,
ando, necessitando
nec
sempre que a comunicação se mantenha ativa
(COLORNI et al., 1991) ou, em outras palavras, que o feromônio continue sendo depositado.
depositado
Os resíduos de feromônio são associados com os componentes do problema, desta
forma o feromônio τj associado,
associado por exemplo, com um vértice, mede o quanto é desejável a
27
inclusão do vértice j na solução. A forma de cálculo dos valores de τj são dados pelos
algoritmos heurísticos ACO específicos. Assim, a probabilidade de escolha é dada pelo
resultado da multiplicação do fator feromônio pelo fator informação heurística (MULATI,
2009).
A atualização de feromônio é feita basicamente pela evaporação e pelo depósito de
mais feromônio por uma ou mais formigas, sendo definida pelo algoritmo heurístico ACO em
utilização (MULATI, 2009).
O depósito do feromônio pode ser descrito, de forma genérica, pela Equação 4.
(4)
Onde ∆τk pode ser até mesmo um valor constante, ou conforme a heurística definida.
3.4
EVAPORAÇÃO
Há duas ações relacionadas ao feromônio: depósito e evaporação. A evaporação
provoca uma diminuição do valor do feromônio em todos os arcos ij através de um fator ρ. Já
o depósito adiciona feromônio em todos arcos il que pertençam aos caminhos construídos por
cada formiga.
A evaporação do feromônio, que poderia favorecer a exploração de novos caminhos, é
demasiadamente lenta: a vida do feromônio é comparável com a duração de um julgamento
(GOSS et al., 1989). Isto significa que o feromônio evapora lentamente para permitir que a
colônia de formigas "esqueça" o caminho sub-ótimo para onde as formigas convergiram, de
forma que um caminho novo e menor possa ser descoberto e "aprendido" (DORIGO;
STÜTZLE, 2004).
O modelo pressupõe que a quantidade de feromônio em um dado caminho é
proporcional ao número de formigas que o utilizaram no passado. Em outras palavras, a
evaporação do feromônio não é considerada pelo do modelo (DORIGO; STÜTZLE, 2004).
Isto está de acordo com a observação experimental, na qual o tempo necessário para as
formigas a convergirem para o caminho mais curto tem a mesma ordem de grandeza que o
tempo de vida do feromônio (GOSS et al., 1989; BECKERS, DENEUBOURG, GOSS, 1993).
A evaporação pode ser descrita, de forma genérica, pela Equação 5.
(5)
28
3.5
TRABALHOS RELACIONADOS
A meta-heurística
heurística ACO tem sido aplicada em vários problemas discretos de
otimização, tais como, o problema do caixeiro viajante, a atribuição quadrática, o roteamento
em redes de telecomunicações, o roteamento de veículos, etc. Entretanto, o algoritmo AS
(COLORNI et al., 1991) ainda continua servindo de base à criação da maioria dos algoritmos
ACO.
Algumas
mas das aplicações da meta-heurística ACO já foram desenvolvidas.
desenvolvid As principais
são descritas nos itens a seguir.
seguir
3.5.1
Ant System e o Problema do Caixeiro Viajante
Intuitivamente, o Problema do Caixeiro Viajante (Traveling
(Traveling Salesman Problem - TSP)
é um problema encontrado por um caixeiro viajante que, iniciando de sua cidade natal, quer
encontrar o menor caminho possível através de um conjunto de cidades
cidades clientes dadas, de
forma que ele possa visitar cada cidade uma única vez, para depois retornar à sua cidade natal
(DORIGO; STÜTZLE, 2004).
2004)
O TSP pode ser definido da seguinte forma: dado um conjunto de n cidades e a
distância (ou custo da viagem) entre
ent elas, deve-se
se determinar uma rota que percorra cada uma
das n cidades uma única vez e retorne à cidade de origem, de tal forma que a distância total
percorrida seja mínima (SILVA, 2006).
Este problema pode ser representado por um grafo completo G = (N, A), onde N é o
conjunto de n = |N| cidades (nós) e A é o conjunto de arcos que conectam cada um dos nós a
todos os demais. Para cada arco (i, j) є A é dado um peso dij que representa a distancia (tempo,
custo, o que for) entre as cidades i e j (DORIGO; STÜTZLE, 2004),, conforme visto na Figura
9.
Figura 9:: Exemplo de representação do TSP.. Fonte: MACIEL, 2005.
29
Uma solução para uma instância do TSP pode ser representado como uma permutação
de índices de cidades; esta permutação é cíclica, ou seja, a posição de uma cidade em um
caminho não é importante, mas apenas a ordem relativa é importante (em outras palavras,
existem n permutações do mapa para a mesma solução) (DORIGO; STÜTZLE, 2004).
Aplicando o ACO para o TSP, cada formiga é inicialmente colocada em uma cidade
escolhida randomicamente e a cada etapa iterativa acrescenta uma cidade ainda não visitada
em seu caminho parcial. A construção da solução termina quando todas as cidades foram
visitadas (DORIGO; STÜTZLE, 2004).
3.5.2
Problema de Escalonamento de Job-Shop
Este problema foi aplicado em primeira mão por Colorni, Dorigo e Maniezzo (1994).
Eles aplicaram ao problema de escalonamento de Job-Shop (Job-Shop Scheduling Problem JSP) que é formulado da seguinte forma: definimos a variável M para o número de maquinas
disponíveis para processamento e a variável J para o número de trabalhos (jobs) que
desejamos processar. Montamos desta forma uma sequência ordenada de operações para
serem executadas/distribuídas nessas maquinas (DORIGO; CARO, 1999c).
O intuito do JSP é atribuir tarefas para as maquinas, de modo que o valor máximo da
conclusão de todas as tarefas seja minimizado e não serem processadas duas tarefas na mesma
maquina. O JSP é considerado um problema NP-Completo (GAREY; JOHNSON, 1979).
O algoritmo básico aplicado por eles foi idêntico ao AS, onde o valor heurístico foi
computado usando o valor da heurística de maior tempo de processamento restante. Devido a
uma natureza diferente de limitações em relação ao TSP, foi definida por eles uma nova
forma de construir a lista tabu das formigas. O AS-JSP é aplicado a problemas de dimensão
superior a 15 maquinas e 15 tarefas, sempre procurando soluções relacionadas diretamente
aos 10% do valor ótimo estimado (DORIGO; CARO, 1999c).
São resultados excepcionais, porém são muito encorajadores e sugestivos comparados
ao trabalho que um sistema operacional casual teria para processar esta demanda. Além disto,
uma comparação com outras abordagens é sempre necessária e válida (DORIGO; CARO,
1999c).
30
3.5.3
Problema da Ordenação Sequencial
O problema de ordenação sequencial (Sequential Ordering Problem - SOP) consiste
em achar o menor peso em um caminho hamiltoniano sobre um grafo direcionado com
valores nos arcos e nos vértices. Ele é bem similar ao TSP assimétrico, onde a cidade destino
não é conectada diretamente a cidade de partida. O SOP, que é um problema NP-Completo,
pode modelar problemas do mundo real, como o problema onde um único veículo necessita
realizar entregas e recolher encomendas; o planejamento da produção e problemas de
transporte em um sistemas manufatureiro flexível. Portanto o SOP é um problema importante
no ponto de vista das aplicações (DORIGO; CARO, 1999c).
Gambardella e Dorigo (1997) enfrentaram o SOP com o HAS-SOP, uma extensão do
ACS (Ant Colony System). HAS-SOP é o mesmo que o ACS, com exceção do conjunto de
vértices viáveis, que é criado levando em consideração a precedência de limitações adicionais,
e para o otimizador local, que foi uma variante especificamente concebida para o famoso
procedimento 3-opt (DORIGO; CARO, 1999c).
Resultados obtidos com a HAS-SOP são excelentes. Foram feitos testes em um grande
número de problemas básicos e comparações foram feitas com os melhores métodos
heurísticos disponíveis. Em todos os casos HAS-SOP foi o método que apresentou melhores
resultados em termos de qualidade das soluções e de tempo de computação (DORIGO;
CARO, 1999c).
31
4
MODELAGEM E IMPLEMENTAÇÃO SEQUENCIAL DO SCP
Ant Colony Optimization (ACO) é uma construção heurística probabilística que gera
soluções de forma iterativa, levando em conta experiências de pesquisas anteriores
acumuladas: rastros de feromônio e informação heurística (LESSING et al., 2004).
Segundo SILVA (2006), entre todas as heurísticas AS analisadas, aquela que
apresentou melhores resultados foi a AS-SCP. Portanto, esta é a heurística na qual este
trabalho se baseia. O método de otimização para SCP AS-SCP pode ser definido conforme a
Figura 8 (Seção 3.2).
Beasley e Chu (1996) modelaram o SCP através de uma matriz binária de M linhas por
N colunas, em que N é o número de facilidades e M é o número de localidades existentes (e
que devem ser atendidas). Conforme Figura 10, a facilidade F2 atende as localidades L1 e L4.
Assim, é definido que uma localidade é atendida por uma facilidade quando o cruzamento
linha x coluna de ambas contiver o número 1, caso contrário (se contiver 0), esta não é coberta
(CARDOSO et al., 2008, p.24).
Figura 10: Representação de SCP por matriz. Fonte: CARDOSO et al., 2008.
Existe também um vetor custo N-dimensional, o qual contém valores dos custos de
cada facilidade existente (CARDOSO et al., 2008, p.24).
Contudo, por este trabalho usar a heurística ACO, o problema deve ser modelado na
forma de um grafo, chamado “grafo de construção”, que tem a forma G = (J, L,W), o qual é
normalmente um grafo completo. J é o conjunto de facilidades (colunas da tabela da Figura
10) com a adição de um nó inicial, no qual todas as formigas são colocadas no primeiro passo
da construção das soluções (DORIGO; STÜTZLE, 2004). L é o conjunto finito de possíveis
conexões entre os elementos de C. Finalmente, W é o conjunto de custos associados a cada
elemento de C (SILVA, 2006). Assim, as soluções são subconjuntos do conjunto C
(DORIGO; STÜTZLE, 2004).
32
A implementação da solução de software proposta neste trabalho é feita utilizando a
linguagem de programação C.
As demais seções deste capítulo definem:
a) O modelo de solução de software utilizada (seção 4.1);
b) A implementação da função custo (seção 4.2);
c) A implementação da geração das soluções (seção 4.3);
d) O funcionamento do depósito de feromônio (seção 4.4);
e) O funcionamento da evaporação (seção 4.5).
4.1
MODELO DA SOLUÇÃO
O modelo da solução é apresentado, por meio de um fluxograma, na Figura 11. Seu
funcionamento segue os seguintes passos:
1°. O processo é iniciado: todas as facilidades são iniciadas com a mesma quantidade
τj(1) > 0 de feromônio;
2°. É iniciado um laço que conta o número de iterações já executadas da heurística
AS-SCP. Caso o número total de iterações tenha sido alcançado, vai para o passo
10, caso contrário para o passo 3;
3°. É iniciado um laço que seleciona cada formiga k para executar os passos 4 e 5.
Quando isto é concluído, vai para o passo 6;
4°. É iniciado um laço que é executado até que a formiga K selecionada encontre
uma solução viável. Quando isso acontece volta ao passo 3, caso contrário vai
para o passo 5;
5°. A formiga K seleciona uma próxima facilidade;
6°. O feromônio das facilidades é atualizado (depósito e evaporação);
7°. O custo da nova solução é calculado;
8°. É feita a verificação para checar se o custo da nova solução é menor do que o da
solução anterior. Caso positivo, o passo 9 é executado, caso contrário volta para o
passo 2;
9°. A solução anterior é substituída pela nova solução (de custo mais baixo) e volta
ao passo 2;
10°. É retornada a melhor solução encontrada.
33
Figura 11:: Fluxograma do Modelo da Solução. Fonte: O Autor (2009).
O código fonte da versão sequencial está no Apêndice A.
4.2
FUNÇÃO CUSTO
A função custo é uma informação heurística,
h
a qual é computada em função da
solução parcial da formiga atual. Ela é diretamente proporcional ao custo da coluna e
inversamente proporcional ao número de linhas que essa coluna cobre.
cobre Esta função é
calculada através da Equação 6.
(6)
Onde:
a) ej: o número de linhas adicionais cobertas quando a coluna j é adicionada à solução
parcial;
b) bj: o valor do custo da coluna, que não pode ser negativo.
34
Assim, a Equação 6 representa o custo por linha adicional coberta quando a coluna j é
adicionada para a solução em construção.
4.3
GERAÇÃO DAS SOLUÇÕES
A geração das soluções é feita da seguinte forma: cada formiga inicia com uma
solução vazia e a constrói de forma iterativa, adicionando componentes (colunas), até que
todas as linhas sejam cobertas. Cada componente deve ser visitado por uma formiga pelo
menos uma vez e uma solução tem que cobrir todas as linhas (DORIGO; STÜTZLE, 2004).
Contudo o primeiro componente adicionado por cada formiga é selecionado de forma
randômica, de modo a proporcionar uma maior variedade de soluções. A seleção destes
componentes, para cada formiga, é feita antes do início das iterações para que cada formiga
inicie a construção de sua solução adicionando sempre o mesmo componente. Além disto o
algoritmo utilizado garante que não hajam repetições do primeiro componente entre formigas
diferentes.
A regra para a seleção do próximo componente é feita através da regra de decisão
probabilística da Equação 3 (seção 3.2), repetida aqui.
(3)
Onde, adaptando a partir de SILVA (2006):
a) t: iteração atual da heurística AS-SCP;
b) pkij(t): probabilidade da facilidade j ser escolhida pela formiga k, atualmente
situada na facilidade i, durante a t-ésima iteração da heurística AS-SCP;
c) τj(t): quantidade de feromônio sobre a facilidade j ∈ J na t-ésima iteração;
d) α: parâmetro que regula a influência de τj(t);
e) ηj =
: visibilidade da facilidade j com relação à facilidade i (custo);
f) β: parâmetro que regula a influência de ηj;
g) Nki(t): conjunto de facilidades ainda não visitadas pela formiga k, atualmente
situada na facilidade i, nesta t-ésima iteração de AS-SCP.
A Equação 3 determina que a chance da facilidade j ser escolhida é diretamente
proporcional ao valor do feromônio de j multiplicado pelo valor da função custo de j; e é
35
inversamente proporcional ao valor da somatória da probabilidade de todas as facilidades
ainda não visitadas. Outro detalhe é que o valor do feromônio é elevado a α (parâmetro que
regula a influência do feromônio) e o valor da função custo é elevado a β (parâmetro que
regula a influência da função custo).
Após feito o calculo da chance de cada facilidade ser escolhida e do valor da
somatória de probabilidades de todas as facilidades ainda não visitadas, é utilizado um
componente randômico para que a escolha em si seja feita. O valor deste componente
randômico fica entre 0 (zero) e o valor da somatória. Ele é utilizado num laço, onde o valor da
probabilidade de cada facilidade é somado, até que esse valor seja maior ou igual ao valor do
componente randômico. Então a facilidade escolhida é a última utilizada nesse laço.
4.4
FEROMÔNIO
Os resíduos de feromônio são associados com os componentes do problema, de forma
que o resíduo de feromônio τj associado ao vértice j, mede o quanto é desejável a inclusão do
vértice j na solução.
Cada formiga inicia seu processo com uma solução vazia, porém não livre de
feromônio. Como visto na seção 4.1, todas as facilidades são iniciadas com um valor τj(1) > 0
de feromônio. Esse valor pode ser definido pela Equação 7.
(7)
Onde J é o conjunto de facilidades.
Posteriormente o feromônio é depositado durante a atualização (quando também
ocorre a evaporação). A atualização do feromônio é feita a cada iteração, após todas as
formigas terem sido chamadas. Este processo ocorre conforme a Equação 8.
(8)
O valor da atualização é dado por
, o qual valerá
se o componente i tiver sido
k
visitado e 0 caso contrário. C é a soma do custo de todas as colunas adicionadas à solução da
formiga k.
Normalmente o feromônio é depositado nos componentes pertencentes às soluções de
todas as formigas, contudo isto poderia fazer com que o feromônio fosse depositado em
36
soluções ruins, o que acaba facilitando a construção de uma solução final também ruim. Por
este motivo foram feitos testes preliminares para avaliar qual é a melhor forma de se depositar
feromônio.
Foram desenvolvidas 4 versões para a realização dos testes:
a) Uma em que o depósito é feito apenas na melhor solução encontrada na iteração;
b) Uma em que o depósito é feito nas 5 melhores soluções encontradas na iteração;
c) Uma em que o depósito é feito nas 10 melhores soluções encontradas na iteração;
d) Uma em que o depósito é feito nas soluções de todas as formigas da iteração.
Os arquivos fonte utilizados nos testes foram selecionados da OR-Library
(BEASLEY,1990), que é uma “biblioteca” constituída por arquivos fontes (problemas) em
formato texto, e são aqueles apresentados na Tabela 1.
Tabela 1: Arquivos fonte utilizados no teste. Fonte: O Autor (2009).
Nome do Arquivo
Facilidades (Colunas)
Localidades (Linhas)
200
511
300
400
1023
1000
210
3000
4000
330
scp48.txt
scpclr10.txt
scpa2.txt
scpc4.txt
scpclr11.txt
Os resultados destes testes estão na Tabela 2.
Tabela 2: Testes preliminares de variações de depósito de feromônio. Fonte: O Autor (2009).
Arquivos
Melhor
Solução
Média Custos
5 Melhores
Soluções
Média Custos
10 Melhores
Soluções
Média Custos
Todas as
Soluções
Média Custos
scp48.txt
scpclr10.txt
scpa2.txt
scpc4.txt
scpclr11.txt
587
29,6
316,4
283
30
588,2
31,8
306,4
275,4
32
593,8
28,8
309,2
269,6
31,8
573,8
33,6
287,6
257,4
35,6
Geral:
249,2
246,76
246,64
237,6
Cada arquivo foi processado 5 vezes com cada uma das versões desenvolvidas. Assim,
a opção adotada neste trabalho foi a de fazer o depósito de feromônio em todas as soluções da
iteração, pois foi aquela que se apresentou a melhor média geral de custos.
Ainda há espaço para discussão, afinal o resultado de cada versão depende mais do
arquivo de entrada do que do algoritmo em si, pois nem sempre uma versão apresenta
obrigatoriamente os melhores resultados.
37
4.5
EVAPORAÇÃO
Durante a atualização de feromônio o primeiro passo consiste na evaporação do
feromônio, para que então ocorra o depósito do mesmo. A evaporação é dada pela Equação 9.
(9)
Assim, ρ é o parâmetro que indica a taxa de evaporação do feromônio. Seu valor
normalmente é configurado como 10%. Contudo, para estabelecer o melhor valor para este
parâmetro, foram feitos testes com 3 valores diferentes, sendo eles 10%, 20% e 30%. Os
testes foram feitos com o arquivo fonte de nome “scp48.txt”, utilizando a versão sequencial
que faz o depósito de feromônio em todas as soluções da iteração (que foi aquela que
apresentou a melhor média de custos, conforme a seção 4.4) e os resultados destes testes estão
na Tabela 3.
Tabela 3: Resultados dos testes de valores do parâmetro de evaporação. Fonte: O Autor (2009).
10%
Custo
Execução
1
2
3
4
5
574
569
575
574
577
Média: 573,8
20%
Custo
30%
Custo
582
590
584
586
593
598
588
593
595
591
587
593
O valor adotado neste trabalho foi de 10%, pois foi o valor do parâmetro de
evaporação que apresentou a melhor média de custos.
38
5
MODELAGEM E IMPLEMENTAÇÃO
IMPLEMEN
DISTRIBUÍDA DO SCP
A modelagem da versão
vers distribuída é baseada na versão sequencial, apresentada no
Capítulo 4. Assim, com
om base nos resultados obtidos nos
os testes preliminares realizados para
comparar as formas de depósito de feromônio (seção 4.4) e os valores do parâmetro de
evaporação (seção 4.5),, a versão que faz o depósito em todas as soluções de cada iteração e
usa o valor do parâmetro de evaporação de 10% foi a melhor opção e serviu
serv de base da versão
distribuída.
A implementação da solução
soluç distribuída proposta neste trabalho é feita utilizando a
linguagem de programação C e utiliza o padrão MPI (SNIR; GROPP, 1998).
1998)
As seções destee capítulo definem:
a) A estratégia utilizada para realizar a distribuição do software (seção 5.1);
b) A forma de implementação do software utilizando o padrão MPI (seção 5.2).
5.1
ESTRATÉGIA DE RESOLUÇÃO
RESOLU
A estratégia de resolução da distribuição da solução definida neste trabalho é
apresentada na Figura 12.
Figura 12:: Estratégia de distribuição da solução. Fonte: O Autor (2009).
39
Cada escravo executa uma colônia de formigas, contudo o número total de iterações é
dividido entre os escravos. O cálculo do número de iterações de cada colônia é o número total
de iterações dividido pelo número de escravos, conforme a Equação 10.
(10)
Onde:
a) ni : número de iterações do escravo;
b) ti : número total de iterações da solução;
c) st : número de escravos sendo utilizados.
Cada colônia trabalha no arquivo de entrada inteiro. Ou seja, o arquivo de entrada não
é dividido em partes para que cada escravo processe apenas uma pequena parte, como é
normalmente feito.
O primeiro componente adicionado a cada formiga continua sendo selecionado de
forma randômica, da mesma forma que acontece na versão sequencial. Quanto à atualização
do feromônio, ela é feita separadamente em cada escravo da mesma forma que acontece na
versão sequencial. Contudo, logo após este processo, cada escravo comunica aos demais onde
e quanto feromônio ele depositou. Desta forma, apesar do processamento ter sido distribuído,
o contexto em que as soluções são criadas continua sendo um só.
Ainda assim a granularidade é alta, pois a comunicação entre os escravos ocorre
apenas uma vez a cada iteração e tudo o que é comunicado é um vetor do tipo double com
tamanho igual ao número de facilidades (colunas ou componentes) do problema.
Quando cada escravo é chamado é passando a ele apenas o nome do arquivo de
entrada a ser utilizado. Ao final do processamento o mestre recebe o resultado de cada
escravo, avalia qual das soluções é melhor, exibe este resultado e finaliza.
5.2
IMPLEMENTAÇÃO COM MPI
MPI (Message Passing Interface) é um padrão especificado pelo MPI-Forum para o
desenvolvimento
de
uma
interface
de
passagem
de
mensagens
entre
sistemas
multiprocessadores e multicomputadores. A passagem de mensagens engloba tanto a
transmissão da mensagem, quanto as sincronização e ordenação das mensagens
(MASSETTO, 2007).
40
A principal característica da plataforma MPI é que ela permite que programas possam
ser executados de forma distribuída (em vários computadores de forma simultânea), com
suporte a primitivas de comunicação comuns entre seus componentes (MULATI, 2009).
O projeto do MPI teve início em 1992 com um grupo de pesquisadores de várias
nacionalidades e fabricantes de computadores do mundo todo. Ele é uma tentativa de
padronizar a troca de mensagem entre equipamentos (TAMAE et al., 2006).
Neste trabalho é utilizado o MPICH2 (MCS, 2009), que é uma implementação do
padrão MPI. As letras “CH” do final do nome vem de Chameleon (ou Camaleão em
português), animal símbolo da adaptabilidade e, portanto, da portabilidade.
Em soluções de software desenvolvidos utilizando MPI, este fica responsável por todo
o processo de comunicação. Assim deixa de ser necessário o desenvolvimento de toda a parte
específica de protocolos, formatos de mensagens, etc., permitindo que o desenvolvedor se
concentre no problema a ser solucionado.
O MPI permite dois tipos de comunicação: ponto a ponto (entre dois processos
específicos) e coletivas.
a) Comunicação coletiva: aquela que parte de um processo (do mestre, por exemplo)
para os demais (escravos);
b) Comunicação ponto a ponto: na comunicação que parte de um processo específico
para um outro também específico.
Neste trabalho o tipo de comunicação utilizado é apenas o ponto a ponto.
Além disto, o MPI ainda fica responsável por informações como o número de
processadores utilizados em uma solução (através da primitiva MPI_Comm_size), o
identificador ou número do processo (através da primitiva MPI_Comm_rank), etc. Assim,
basta que o escravo tenha acesso ao arquivo fonte do problema e que faça chamadas a estas
primitivas para poder calcular todas as equações apontadas na seção 5.1.
A própria execução da solução é facilitada, pois todos os processos são disparados
remotamente nas máquinas determinadas.
O código fonte da versão distribuída está no Apêndice B.
5.2.1
Funcionamento do Mestre
O funcionamento do mestre é, na verdade, bastante simples. Tudo o que ele faz é
esperar que os escravos lhe enviem as soluções encontradas durante o processamento do
41
arquivo do problema. Depois disto o mestre verifica qual destas soluções é a melhor e
apresenta o resultado.
5.2.2
Funcionamento do Escravo
Cada escravo recebe seu número de escravo e o número total de escravos sendo
utilizados através de chamadas a primitivas MPI. É com base nestes dois números que cada
escravo define quantas iterações ele deve utilizar e para quais processos ele deve enviar
mensagens.
O funcionamento do escravo é basicamente o mesmo da versão sequencial,
apresentada no Capítulo 4. A diferença básica é que, antes de realizar o processamento em si,
ele deve realizar os cálculos apresentados na seção 5.1, assim como notificar (através do
envio de mensagens) aos demais escravos onde e quanto feromônio ele depositou em cada
iteração.
Tendo feito isto e processado o problema em si, o escravo envia a melhor solução
encontrada ao mestre.
42
6
TESTES E ANÁLISE DOS RESULTADOS
Para testar e analisar a eficiência dos algoritmos desenvolvidos, foram realizados
testes utilizando como base a OR-Library (BEASLEY,1990), que é uma “biblioteca”
constituída por arquivos fontes (problemas) em formato texto, os quais têm tamanhos
variados e a solução ótima é conhecida.
Em cada execução é informado o nome do arquivo fonte e cada um deles (arquivos
fontes – problemas) é processado dez vezes para ambas as versões do algoritmo, tanto
sequencial quanto distribuído. Os resultados são copiados em um arquivo de saída, que são
compostos pelas soluções finais (contendo custo total da solução, número de
componentes/colunas adicionadas à solução e em que iteração e formiga ela foi encontrada) e
tempos de execução.
Ao término das dez execuções de cada versão, uma média ponderada é calculada tanto
dos custos das soluções obtidas, quanto dos tempos de execução, os quais são relevantes a
demonstração dos objetivos do trabalho. A média ponderada citada é calculada consideradas
as médias aritméticas dos valores, desprezando os valores anômalos extremos (o menor e o
maior).
Os arquivos fonte utilizados nos testes são aqueles listados na Tabela 4:
Tabela 4: Arquivos fonte dos problemas utilizados. Fonte: O Autor (2009).
Nome do Arquivo
Facilidades (Colunas)
Localidades (Linhas)
scp63
scp55
scpa5
scpb2
scpd3
scpnre1
scpnre2
scpnre5
200
200
300
300
400
500
500
500
1000
2000
3000
3000
4000
5000
5000
5000
Estes arquivos fontes foram selecionados por terem dimensões variadas, além de
serem 8 dos 10 arquivos fonte usados por CARDOSO et al. (2008), no trabalho
Implementação De Uma Solução Paralela Para A Resolução Do Problema De Cobertura De
Conjuntos Utilizando Algoritmo Genético, o que permite que os resultados de ambos os
trabalhos possam ser comparados. Além disto, com estes arquivos fonte o algoritmo será
submetido a diferentes tamanhos de entrada de dados.
43
O motivo pelo qual não foram usados todos os 10 arquivos fonte usados por
CARDOSO et al. (2008) foi o tempo. Os 2 arquivos que não foram utilizados nos testes deste
trabalho são muito grandes e, por isso mesmo, demoram muito para serem processados.
6.1
AMBIENTE DE TESTE
Os testes foram realizados num computador com a seguinte configuração: Intel (R)
Core(TM) 2 Duo CPU de 2.20GHz, 2,00GB de memória RAM, com o sistema operacional
Microsoft Windows XP Professional Service Pack 3, MPICH2 versão 1.2.
6.2
TESTES
Dentre os parâmetros utilizados pelo Ant System em seu processamento, os parâmetros
α (parâmetro que regula a influência do feromônio) e β (parâmetro que regula a influência da
função custo) têm extrema relevância para a qualidade dos resultados obtidos, portanto
precisam ser configurados de forma bastante cuidadosa e precisa. Para tanto foram feitos
testes preliminares para avaliar quais são os melhores valores para estes dois parâmetros.
Os testes do parâmetro α foram feitos com os arquivos fonte “scpd3.txt” e
“scpnre2.txt”, utilizando a versão sequencial adotada para este trabalho (citada na seção 4.4) e
fixando o valor do parâmetro β em 2.0. Os resultados destes testes estão na Tabela 5.
Tabela 5: Resultados dos testes do parâmetro de influência do feromônio (α). Fonte: O Autor (2009).
Arquivos Fonte
(Problema)
1.0
Custo
2.0
Custo
3.0
Custo
scpd3.txt
scpnre2.txt
80,5
34
79
35,5
79
36
57,25
57,25
57,5
Média:
Os testes do parâmetro β foram feitos da mesma forma: com os arquivos fonte
“scpd3.txt” e “scpnre2.txt”, utilizando a versão sequencial adotada para este trabalho (citada
na seção 4.4), mas fixando o valor do parâmetro α em 1.0. O valor 1.0 não foi o melhor
resultado obtido no teste do parâmetro de influência do feromônio, mas foi um dos dois
melhores. Além disto, este é o valor indicado para esse parâmetro por DORIGO e STÜTZLE
(2004). Os resultados destes testes estão na Tabela 6.
44
Tabela 6: Resultados dos testes do parâmetro de influência da função custo (β). Fonte: O Autor (2009).
1.0
Custo
82,5
37,5
60
Arquivo Fonte
scpd3.txt
scpnre2.txt
Média:
2.0
Custo
80
34
57
3.0
Custo
81
33,5
57,25
4.0
Custo
81
35
58
Desta forma, os valores adotados neste trabalho para os parâmetros α e β foram de 1.0
e 2.0 respectivamente, pois foram os valores que apresentaram as melhores médias de custos.
A Tabela 7 apresenta os valores de todos os parâmetros do Ant System adotados neste
trabalho.
Tabela 7: Valores adotados para os parâmetros do algoritmo Ant Sysytem. Fonte: O Autor (2009).
Parâmetros
Valores Adotados
Número de iterações
Quantidade de formigas
Taxa de evaporação do feromônio (ρ)
Valor inicial do feromônio
Influência do feromônio (α)
Influência da função custo (β)
100
100
10%
1.0
1.0
2.0
A seguir são apresentadas as tabelas dos resultados obtidos através do processamento
dos arquivos fonte pelos algoritmos sequencial e distribuído, assim como gráficos gerados a
partir destas tabelas. Para cada gráfico é feita uma breve descrição, com a finalidade de tornar
mais clara e objetiva sua apresentação, assim como a de facilitar a análise dos resultados,
presente na sessão 6.3.
Tabela 8: Resultados Testes - dos Custos: Ótimo vs. Sequencial vs. Distribuído. Fonte: O Autor (2009).
Arquivos Fonte
(Problemas)
Solução
Ótima
Algoritmo Genético
Solução
Sequencial
Solução Distribuída
(3 Processos)
scp63
scp55
scpa5
scpb2
scpd3
scpnre1
scpnre2
scpnre5
145
211
236
76
72
29
30
28
148
212
237
76
73
29
30
28
166,625
236
254,75
84,75
80,625
30,125
33,875
30,25
163,5
232,375
254,5
83,875
81,125
30,375
35
29,75
A Tabela 8 apresenta os resultados obtidos através dos testes realizados com os
arquivos fonte adotados no trabalho, assim como o valor da solução ótima destes arquivos e
45
dos melhores resultados do Algoritmo Genético apresentados pelo no trabalho Implementação
De Uma Solução Paralela Para A Resolução Do Problema De Cobertura De Conjuntos
Utilizando Algoritmo Genético de CARDOSO et al., 2008.
O Gráfico 1, o qual foi criado a partir da Tabela 8, apresenta a comparação entre os
resultados (soluções) obtidos pelas duas versões do algoritmo Ant System, sequencial e
distribuída, desenvolvidas neste trabalho, com a solução ótima já conhecida para cada
problema e com os resultados apresentados por CARDOSO et al., 2008.
Custos Obtidos - Ótimo vs. Sequencial vs. Distribuído
Custo das Soluções
300
250
200
150
Solução Ótima
100
Algoritmo Genético
50
Solução Sequencial
0
Solução Distribuída (3 Processos)
Arquivos Fonte
Gráfico 1: Comparações dos Custos: Ótimo vs. Sequencial vs. Distribuído. Fonte: O Autor (2009).
A Tabela 9 apresenta os tempos de execução obtidos através dos testes realizados com
as versões sequencial e distribuída, com o processamento dos arquivos fonte adotados neste
trabalho.
Tabela 9: Resultados dos Testes - Tempos de Execução: Sequencial vs. Distribuído. Fonte: O Autor (2009).
Arquivos Fonte
(Problemas)
scp63
scp55
scpa5
scpb2
scpd3
scpnre1
scpnre2
scpnre5
Solução Sequencial
387,625
1031,25
2650,5
1928,625
3594,375
4064,5
4219,5
4002,5
Solução Distribuída
(3 Processos)
192,375
515,25
1324,75
968
1822,625
2084,625
2169
2038
46
O Gráfico 2, o qual foi criado a partir da Tabela 9, apresenta comparação entre os
resultados dos tempos de execução.
Tempos de Execução - Sequencial vs. Distribuído
4500
4000
3500
3000
2500
2000
1500
1000
500
0
Solução Sequencial
Solução Distribuída (3
Processos)
Arquivos Fonte
Gráfico 2: Comparação dos Tempos de Execução: Sequencial vs. Distribuído. Fonte: O Autor (2009).
O Gráfico 3 apresenta o speedup (relação entre os tempos de execução das versões
sequencial e distribuída). Este grafo também foi criado a partir da Tabela 9, contudo os
valores são os resultados da divisão do tempo de execução da versão sequencial pelo tempo
de execução da versão distribuída.
Speedup da Versão Distribuída
2,04
2,02
Speedyp
2
1,98
1,96
1,94
Speedup da Versão
Distribuída (3 Processos)
1,92
1,9
Arquivos Fonte
Gráfico 3: Speedup da Versão Distribuída. Fonte: O Autor (2009).
47
6.3
ANÁLISE DOS RESULTADOS
Como pode ser observado nos gráficos 1 e 2, os resultados obtidos tanto com a versão
sequencial, quanto com a versão distribuída, foram satisfatórios. As soluções encontradas com
o Ant System se aproximaram da solução ótima, com um tempo computacional muito menor
se comparado a uma estratégia sem a aplicação de heurística, demonstrando a eficiência deste
tipo de algoritmo.
A versão distribuída apresentou resultados ainda mais interessantes, pois com a
utilização da arquitetura multi-processada, pôde obter soluções tão boas quanto as soluções
obtidas na versão sequencial, porém com tempos de execução muito menores. Afinal, a
vantagem em tempo de execução da versão distribuída em relação à versão sequencial é dada,
na maioria dos casos, quase pela divisão do tempo da versão sequencial pelo número de
escravos utilizados na execução, que é exatamente o número de processos usados menos um
(que executa a aplicação mestre). Isto fica ainda mais claro ao se observar o Gráfico 3.
A vantagem apresentada pela versão distribuída não se resume ao tempo de execução:
ela apresentou os melhores resultados em 5 (cinco) dos 8 (oito) arquivos fontes utilizados
neste trabalho. Assim, quanto à versão distribuída, tanto o desempenho, medido através do
tempo de execução, como os resultados apresentados, a tornam extremamente vantajosa.
Esta vantagem da versão distribuída pode diminuir quando o número de máquinas
envolvidas no trabalho (número de escravos) começa a crescer demais. Isto devido ao fato dos
processos (escravos e mestre) começarem a gastar mais tempo com a comunicação, do que
com o processamento em si. Contudo, devido à estratégia de distribuição adotada neste
trabalho, o número de máquinas terá de ser muito grande para isto poder ser observado, pois a
comunicação entre os processos é bastante restrita.
48
7
CONCLUSÃO
O objetivo traçado no início deste trabalho era o de implementar em uma solução,
tanto seqüencial quanto distribuída, para o Problema de Cobertura de Conjuntos através do
uso de técnicas heurísticas, abordagem a qual não visa descobrir exatamente a solução ótima,
mas sim uma solução boa (em alguns casos podendo chegar à solução ótima). Assim, o
algoritmo heurístico escolhido foi o Ant System. Tal objetivo foi atingido e, comparando-se as
soluções ótimas com os testes realizados, assim como com as soluções geradas pelo
Algoritmo Genético, apresentadas pelo trabalho de CARDOSO et al. (2008), a utilização do
algoritmo Ant System se mostrou bastante satisfatória.
Mais do que isto, apesar do Algoritmo Genético apresentar resultados melhores, seu
tempo de execução é muito superior, devido a diferenças quanto ao critério de parada do
algoritmo: enquanto o Ant System executa um número pré-estabelecido de vezes, o Algoritmo
Genético tem seu critério de parada no tempo de execução, assim como na qualidade da
melhor solução encontrada. Isto acaba fazendo com que o Algoritmo Genético seja bem mais
lento.
A partir dos resultados obtidos nos testes realizados, conforme apresentado na seção
6.2, assim como da análise desses resultados, apresentada na seção 6.3, pôde-se chegar a
algumas conclusões: no que diz respeito à versão seqüencial, foram obtidos resultados
bastante satisfatórios, contudo seu desempenho não foi tão bom quanto o da versão
distribuída. Já no que diz respeito à versão distribuída, os resultados obtidos foram não só
satisfatórios, como chegaram a ser melhores que os resultados da versão seqüencial,
apresentando um placar de 5 (cinco) a 3 (três) para a versão distribuída. Além disso, o
desempenho apresentado (tempo de execução) por esta versão foi ainda mais satisfatório.
Vale também ressaltar, que a principal dificuldade encontrada durante todo este
trabalho foi quanto à falta de documentação que detalhasse de forma mais precisa como
implementar o algoritmo Ant System, o que inclusive impediu que a busca local fosse
implementada.
7.1
TRABALHOS FUTUROS
A partir do que foi apresentado neste trabalho, várias são as possibilidades para
trabalhos futuros:
49
a) Alterar o critério de parada do algoritmo de um número de iterações fixo para
utilizar dois outros critérios: um por tempo de execução e outro por porcentagem
da qualidade da solução até então encontrada. Essa porcentagem seria de 0%
quando a solução encontrada fosse igual à ótima, de 50% quando a solução
encontrada fosse igual à ótima vezes 1.5 e assim por diante;
b) Uso de threads para paralelizar o processamento das formigas, tanto na versão
distribuída como na versão sequencial (transformando-a numa versão “local”, pois
esta tecnicamente deixaria de ser “sequencial”), de forma a aproveitar as vantagens
dos novos processadores multi-core;
c) Implementação da busca local, a qual seria realizada nas melhores soluções de
cada iteração, para tentar eliminar as distorções dos resultados apresentados na
seção 4.4;
d) Implementação de outras variantes do algoritmo Ant System, de forma a verificar
qual seria mais efetivo ao SCP;
e) Implementação de outras técnicas heurísticas como Greedy (CORMEN, 2002) ou
Simulate Annealing (JACOBS; BRUSCO, 1995) para comparar os resultados com
aqueles obtidos neste trabalho, de forma a verificar qual seria mais efetivo ao SCP.
50
REFERÊNCIAS BIBLIOGRÁFICAS
BEASLEY, J. E. An algorithm for set covering problem. European Journal of Operational
Research, v. 31, n. 1, p. 85-93, jul. 1987.
BEASLEY, J. OR-Library: distributing test problems by electronic mail, Journal of the
Operational Research Society 41 : 1069-1072, 1990.
BEASLEY J. E, CHU P. C. A Genetic Algorithm for the Set Covering Problem, European
Journal of Operational Research, 1996.
BECKERS, R., DENEUBOURG, J.L., GOSS, S. Modulation of trail laying in the ant Lasius
niger (hymenoptera: Formicidae) and its role in the collective selection of a food source.
Journal of Insect Behavior, 6(6), 751–759, 1993.
CALVI R., Um algoritmo para o problema de escalonamento de tripulação em empresas de
ônibus, 2005.
CAMBRIDGE International Dictionary of English, Cambridge University Press, 1995.
CARDOSO, A.; GUEDES, J.; SOUZA, P.; FARIA, R.; FERRO, W., Implementação De Uma
Solução Paralela Para A Resolução Do Problema De Cobertura De Conjuntos Utilizando
Algoritmo Genético. 2008. Monografia (Bacharelado em Ciência da Computação) Universidade Anhembi Morumbi, São Paulo.
COLORNI A.; DORIGO M.; MANIEZZO V., Positive Feedback as a Search Strategy.
Relatório Técnico 91-016, Departamento de Eletrônica, Politécnico de Milão, Itália, 1991.
COLORNI A.; DORIGO M.; MANIEZZO V., The Ant System Applied to the Quadratic
Assignment Problem. Relatório Técnico IRIDIA/94-28, Univesité Libre de Bruxelles,
Bélgica, 1994.
COLORNI A.; DORIGO M.; MANIEZZO V., Ant System: Optimization by a Colony of
Cooperating Agents, IEEE Transactions On Systems, Man, And Cybernetics-Part B
Cybernetics, Vol 26, N.o 1, 1996.
CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L., Algoritmos: Teoria e Prática. 2° ed.
Rio de Janeiro: Campus, 2002.
DORIGO M. Ant System: Optimization by a Colony of Cooperating Agents, 1996.
DORIGO M., GAMBARDELLA L. M. Ant Colony System: a Cooperative Learning
Approach to the Travelling Salesman Problem. IEEE Trans. Evol. Comput. 1 (1):53-66, 1997.
DORIGO M.; CARO G., The Ant Colony Optimization Meta-Heuristic. New Ideas in
Optimization, McGraw-Hill, Londres, Reino Unido, 1999a.
DORIGO M.; CARO G.; GAMBARDELLA L. M., Ant Algorithms for Discrete
Optimization. Artificial Life 5(2), 1999b.
51
DORIGO M.; CARO G., Ant Algorithms for Discrete Optimization. Artificial Life 5: 137–
172, Bruxelas, Bélgica, 1999c.
DORIGO M.; STÜTZLE T., Ant Colony Optimization. Cambridge: The MIT Press, 2004.
FISHER, M.; JAIKUMAR, R., A generalized assignment heuristic for vehicle routing.
Networks, 11, 109-124, 1981.
FRANCIS, L. R.; White J. A., Facility Layout and Location. Prentice-Hall, 1974.
GALVÃO R. D.; CHIYOSHI F. Y.; ESPEJO L. C. A.; RIVAS M. P. A., Solução do
Problema de Localização de Máxima Disponibilidade Utilizando o Modelo Hipercubo. 2002.
COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro
GAMBARDELLA L. M., DORIGO M. HAS-SOP: An Hybrid Ant System for the Sequential
Ordering Problem. Relatório Técnico IDSIA-11-97, Lugano, Suíça, 1997.
GAREY M. R.; JOHNSON, D. S., Computers and Intractability: A Guide to the Theory of
NP-Completeness, 1979.
GOLDBARG, M. C.; LUNA, H. P. L. Otimização Combinatória e Programação Linear. Rio
de Janeiro: Campus. 2000. 649 p.
GOSS S., ARON S., DENEUBOURG J. L., PASTEELS, J. M. Self-organized shortcuts in the
Argentine ant. Naturwissenschaften, 76:579-581, 1989.
HOCHBAUM D.S., editor. Aproximation Algorithms for NP-Hard Problems. PWS
Publishing Company, 1997.
HOLLAND, J., Adaptation In Natural And Articial Systems, University of Michigan Press,
Ann Arbor (1975).
JACOBS, L. W.; BRUSCO, M. J., Note: A Local-Search Heuristic for Large Set-Covering
Problems, Naval Research Logistics, Vol. 42, pp. 1129-1140, 1995.
LESSING, L.; DUMITRESCU, I.; STUTZLE, T., “A comparison between ACO algorithms
for the set covering problem”, ANTS 2004, LNCS 3172, 2004, pp. 1-12
LOPES, L. S., Uma Heurística Baseada em Algoritmos Genéticos Aplicada ao Problema de
Cobertura de Conjuntos, 1995.
MASSETTO, S. I., Hybrid MPI – Uma Implementação MPI para Ambientes Distribuídos
Híbridos. 2007. Tese (Doutorado em Engenharia Elétrica) - Escola Politécnica, Universidade
de São Paulo, São Paulo.
MAZZOLA, J.; NEEBE, A.; DUNN, C., Production planning of flexible manufacturing
system in material requirements planning environment. Internat. J. Flexible Manufacturing
Systems, 1/2, 115-142, 1989.
MCS.
MPICH2.
Argonne
National
Laboratory.
2009.
Disponível
http://www.mcs.anl.gov/research/projects/mpich2/. Acessado em: 22 de 10 do 2009.
em
52
MULATI M. H. Investigação da meta-heurística de otimização por colônia de formigas
artificiais aplicada ao problema de cobertura de conjunto. 2009. Dissertação (Mestrado em
Ciência da Computação) - Departamento de Informática, Universidade Estadual de Maringá,
Maringá.
ROSS, G.T.; SOLAND, R.M., Modeling facility location problems as generalized assignment
problems. Management Sci., 24, 345-357, 1977.
RUCHKYS D.P.; SONG S.W., Processamento Paralelo para Análise da Expressão Gênica.,
2002.
RUSSELL, S.; NORVIG, P. Inteligência Artificial. Rio de Janeiro: Campus, 2004.
SAHNI, S.; GONZALEZ, T., P-complete approximation problems. J. ACM, 23, 555-565,
1976.
SILVA R.M.A., Otimização baseada em colônia de formigas aplicada ao Problema de
cobertura de conjuntos, 2006.
SNIR M., GROPP W., MPI the Complete Reference. The MIT Press (1998).
TAMAE, R. Y.; ROSA, A. J.; MUZZI, F. A. G.; PRIMO, A. L. G.; MUCHERONI, M. L.,
Performance em Ambientes Distribuídos Usando MPI para Processamento de Imagens
Médicas. Revista Científica Eletrônica de Sistemas de Informação, Garça: Publicação
Científica da Faculdade de Ciências Jurídicas e Gerenciais de GARÇA/FAEG, ano 2, número
4, Fevereiro de 2006.
TANENBAUM, A. S. Sistemas Operacionais Modernos. Rio de Janeiro: LTC, 2007.
TOREGAS C.; SWAIN R.; REVELLE C.; BERGMAN L. The Location of Emergency
Service Facilities, Operations Research, 19, 1363-1373, 1971.
WALKER W. E. Using the Set Covering Problem to Assign Fire Companies to Fire Houses,
Operations Research, 22, 275-277, 1974.
WILLIAMSON, D. P. Lecture notes on approximation algorithms. Tech. rep. RC 21409,
IBM T. J. Watson Research Center, 1999.
ZIVIANI, N., Projeto de Algoritmos com Implementações em Java e C++, São Paulo, Brazil,
Thomson Learning, ISBN 85-221-0525-1, 2007, 641 pages.
53
APÊNDICE A – CÓDIGO FONTE DA VERSÃO SEQUENCIAL
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//Definições...
#define FALSE 0
#define TRUE 1
#define QTD_ITERACOES 100
#define QTD_FORMIGAS 100
//Variáveis globáis
double alfa
=
double beta
=
double evaporacao =
double feromonio =
long *vet;
(em sua maioria parâmetros)...
1.0; //Parâmetro que regula a influência do feromônio...
2.0; //Parâmetro que regula a influência da função custo...
0.1; //Parâmetro que determina a evaporação...
1.0; //Parâmetro que determina o depósito de feromônio...
//Definição de estruturas...
typedef struct vertices {
long colID; //Número da coluna...
double feromonio; //Valor do feromônio depositado no vértice...
int custo; //Custo da coluna...
long numLinhas; //Número de linhas cobertas pela coluna...
long *linhas; //Linhas cobertas pela coluna...
double funcCusto; //Valor da função custo calculado (em dada seleção de coluna) para a
coluna...
int visited; //Se a formiga K já visitou o vértice ou não...
} Vertice;
typedef struct solucao {
Vertice **conjSolucao; //Vértices selecionados na solução...
long *linhas; //Linhas cobertas pela solução...
long numLinhas; //Número de linhas cobertas pela solução...
int iteracao; //Em que interação esta solução foi encontrada...
int formiga; //Que formiga encontrou esta solução...
long costTotal; //Custo total da solução...
long numColunas; //Número de colunas selecionadas na solução...
} Solucao;
//Declaração de funções...
Solucao * colonia(long colunas, long linhas, Vertice *grafo);
long geraPosInicial(long pos, long colunas);
Vertice * selecionaPrimeiraColuna(long colunas, long pos, Vertice *grafo);
Vertice * escolheColuna(long colunas, long linhas, Vertice *grafo, long *linhasSelecionadas);
void adicionaColuna(long linhas, Solucao *sol, Vertice *coluna, long posicao);
int main(int argc, char *argv[]) {
Vertice *grafo = NULL, *p = NULL;
Solucao *resultado = NULL;
Vertice **conjSolucao = NULL;
long *linhasCobertas = NULL;
long linhas, colunas, i, j, l;
long start, end;
//Entra do número de linhas e colunas...
scanf("%ld", &linhas); //Linhas...
scanf("%ld", &colunas); //Colunas..
//Cria o grafo...
grafo = (Vertice *) malloc((colunas) * sizeof(Vertice));
if(grafo == NULL) {
printf("ERRO: falta de memoria!!!\n");
fflush(stdout);
exit(0);
}
p = grafo;
//Preenche o grafo...
for (i = 0; i < colunas; i++) {
p->colID = i;
p->feromonio = feromonio;
//Entra o custo das colunas...
scanf("%d", &p->custo);
//Entra o número de linhas do grafo...
scanf("%ld", &p->numLinhas);
//Cria e limpa as linhas...
linhasCobertas = (long *) malloc(linhas * sizeof(long));
if(linhasCobertas == NULL) {
printf("ERRO: falta de memoria!!!\n");
fflush(stdout);
exit(0);
}
for (j = 0; j < linhas; j++) {
linhasCobertas[j] = 0;
54
}
//Entra as linhas...
for (j = 0; j < p->numLinhas; j++) {
scanf("%ld", &l);
linhasCobertas[l - 1] = 1;
}
p->linhas = linhasCobertas;
//Entra o valor da função custo...
p->funcCusto = 0.0;
//Seta o vértice como não visitado...
p->visited = FALSE;
p++;
}
//Marca o tempo inicial...
start = time(NULL);
//Processa...
resultado = colonia(colunas, linhas, grafo);
//Marca o tempo final...
end = time(NULL);
//Exibe o resultado...
printf("\n\n*** Resultado da melhor solucao encontrada ***\n\n");
printf("Numero de colunas: %ld\n", resultado->numColunas);
printf("Colunas: ");
conjSolucao = resultado->conjSolucao;
for (i = 0; i < resultado->numColunas; i++) {
p = *conjSolucao;
printf("%ld ", p->colID);
conjSolucao++;
}
printf("\nCusto total: %ld\n", resultado->costTotal);
printf("Solucao encontrada na %d iteracao pela formiga %d.\n", resultado->iteracao,
resultado->formiga);
printf("Tempo total de processamento: %ld.\n", (end - start));
printf("Implementacao: SEQUENCIAL\n");
fflush(stdout);
//Libera tudo...
free(resultado->linhas);
free(resultado->conjSolucao);
free(resultado);
p = grafo;
for (i = 0; i < colunas; i++) {
free(p->linhas);
p++;
}
free(grafo);
//Finaliza...
//system("PAUSE");
return 0;
}
Solucao * colonia(long colunas, long linhas, Vertice *grafo) {
long *linhasCobertas = NULL;
int i, k, m, indSelecionado;
long j, menorCusto;
Solucao *melhor = NULL, **iteracao = NULL;
Solucao *atual = NULL;
Vertice *coluna = NULL;
Vertice **conjSolucao = NULL;
Vertice *p = NULL;
long posInicial[QTD_FORMIGAS];
int primeira;
//Preenche a posição inicial das formigas...
for (k = 0; k < QTD_FORMIGAS; k++) {
posInicial[k] = geraPosInicial(k, colunas);
}
free(vet);
//Processa...
for (i = 0; i < QTD_ITERACOES; i++) { //Iterações...
//printf("Iteracao: %d\n", i);
//fflush(stdout);
//Cria o vetor iteracao...
iteracao = (Solucao **) malloc(QTD_FORMIGAS * sizeof(Solucao *));
for (m = 0; m < QTD_FORMIGAS; m++) {
iteracao[m] = NULL;
}
for (k = 0; k < QTD_FORMIGAS; k++) { //Formigas
//printf("Formiga: %d\n", k);
//fflush(stdout);
//Cria uma nova solução a ser preenchida...
linhasCobertas = (long *) malloc(linhas * sizeof(int));
conjSolucao = (Vertice **) malloc((colunas) * sizeof(Vertice *));
iteracao[k] = (Solucao *) malloc(sizeof(Solucao));
if(linhasCobertas == NULL || conjSolucao == NULL || iteracao[k] == NULL) {
printf("ERRO: falta de memoria!!!\n");
fflush(stdout);
exit(0);
}
55
iteracao[k]->iteracao = i;
iteracao[k]->formiga = k;
iteracao[k]->numColunas = 0;
iteracao[k]->numLinhas = 0;
iteracao[k]->costTotal = 0;
iteracao[k]->linhas = linhasCobertas;
iteracao[k]->conjSolucao = conjSolucao;
//Limpa todas as linhas...
for (j = 0; j < linhas; j++) {
linhasCobertas[j] = 0;
}
//Seta primeira para TRUE para que a formiga possa adicionar a
//primeira posição (coluna) sorteada...
primeira = TRUE;
do {
//Atividade da formiga k...
if (primeira == TRUE) {
//Seleciona a primeira coluna a ser adicionada...
coluna = selecionaPrimeiraColuna(colunas, posInicial[k], grafo);
//Adiciona a nova coluna...
adicionaColuna(linhas, iteracao[k], coluna, iteracao[k]->numColunas);
primeira = FALSE;
} else {
//Escolhe uma nova coluna a ser adicionada...
coluna = escolheColuna(colunas, linhas, grafo, linhasCobertas);
//Adiciona a nova coluna...
adicionaColuna(linhas, iteracao[k], coluna, iteracao[k]->numColunas);
}
iteracao[k]->numColunas++;
} while (iteracao[k]->numLinhas < linhas) ;
//Seta todos os vértice do grafo como não visitados...
p = grafo;
for (j = 0; j < colunas; j++) {
p->visited = FALSE;
p++;
}
}
//Atualiza o feromônio...
//Evaporação...
p = grafo;
for (j = 0; j < colunas; j++) {
p->feromonio = (1 - evaporacao) * p->feromonio;
p++;
}
//Depósito...
for (m = 0; m < QTD_FORMIGAS; m++) {
conjSolucao = iteracao[m]->conjSolucao;
for (j = 0; j < iteracao[m]->numColunas; j++) {
conjSolucao[j]->feromonio += feromonio / iteracao[m]->costTotal;
}
}
//Guarda a melhor solução gerada até agora...
//Verifica qual a melhor solução da iteração...
menorCusto = iteracao[0]->costTotal;
indSelecionado = 0;
for (m = 1; m < QTD_FORMIGAS; m++) {
if (iteracao[m]->costTotal < menorCusto) {
menorCusto = iteracao[m]->costTotal;
indSelecionado = m;
}
}
//Verifica se a melhor solução da iteração é melhor que a
// melhor até o momento...
if (i == 0 || iteracao[indSelecionado]->costTotal < melhor->costTotal) {
//Ou esta é a primeira iteração, portanto a melhor solução ainda
// está vazia, ou o custo da melhor solução da iteração é menor que
// o da melhor até o momento...
melhor = iteracao[indSelecionado];
}
//Libera a iteracao inteira...
for (m = 0; m < QTD_FORMIGAS; m++) {
if (m != indSelecionado) {
free(iteracao[m]->linhas);
free(iteracao[m]->conjSolucao);
free(iteracao[m]);
}
}
}
return melhor;
}
long geraPosInicial(long pos, long colunas) {
static int primeira = TRUE;
long i, outro, temp;
if (primeira == TRUE) {
//Cria o vetor...
56
vet = (long *) malloc(colunas * sizeof(int));
if(vet == NULL) {
printf("ERRO: falta de memoria!!!\n");
fflush(stdout);
exit(0);
}
//Preenche o vetor...
for (i = 0; i < colunas; i++) {
vet[i] = i;
}
//Embaralha o vetor...
for (i = 0; i < colunas; i++) {
outro = rand() % (colunas);
temp = vet[i];
vet[i] = vet[outro];
vet[outro] = temp;
}
primeira = FALSE;
}
//Retorna a posição...
if (pos >= colunas) {
pos -= colunas;
}
return vet[pos];
}
Vertice * selecionaPrimeiraColuna(long colunas, long pos, Vertice *grafo) {
Vertice *p = NULL;
long i;
p = grafo;
for (i = 0; i < pos; i++) {
p++;
}
return p;
}
Vertice * escolheColuna(long colunas, long linhas, Vertice *grafo, long *linhasCobertas) {
Vertice *p = NULL;
long *lin = NULL, i, j;
long totLinhas, colsAcessiveis = 0, random;
double custoTotal = 0.0, custo, prob;
//Calcula a função custo total e de cada vértice...
p = grafo;
for (i = 0; i < colunas; i++) {
if (p->visited == TRUE) {
p->funcCusto = 0.0;
} else {
lin = p->linhas;
totLinhas = 0;
if (lin == NULL) {
printf("ERRO: o vetor de linhas do vertice eh nulo!!!\n");
fflush(stdout);
exit(0);
}
if (linhasCobertas == NULL) {
printf("ERRO: o vetor de linhas da solucao atual eh nulo!!!\n");
fflush(stdout);
exit(0);
}
for (j = 0; j < linhas; j++) {
//Conta as linhas cobertas ainda não adicionadas...
if (lin[j] == 1 && linhasCobertas[j] == 0) {
totLinhas++;
}
}
if (totLinhas > 0) {
colsAcessiveis++;
//Calcula a função custo de cada vértice...
custo = (double)((double)totLinhas / (double)p->custo);
p->funcCusto = pow(p->feromonio, alfa) * pow(custo, beta);
//Calcula a função custo total...
custoTotal += p->funcCusto;
} else {
//Todas as linhas cobertas pelo vértice já foram cobertas pela solução
atual...
p->funcCusto = 0.0;
p->visited = TRUE;
}
}
p++;
}
//Calcula a probabilidade de cada coluna ser escolhida...
if (custoTotal < 1) {
random = 0;
} else {
srand(time(NULL));
random = rand() % (int)custoTotal;
57
}
p = grafo;
while (p->visited == TRUE) {
p++;
}
prob = p->funcCusto;
while ((int)prob < random) {
p++;
prob += p->funcCusto;
}
return p;
}
void adicionaColuna(long linhas, Solucao *sol, Vertice *coluna, long posicao) {
long *linhasCobertas = NULL;
long *novasLinhas = NULL;
long i;
//Adiciona a coluna à solunção...
sol->conjSolucao[posicao] = coluna;
//Soma o custo da coluna no custo total da solunção...
sol->costTotal += coluna->custo;
//Atualiza as linhas cobertas pela solução...
linhasCobertas = sol->linhas;
novasLinhas = coluna->linhas;
for (i = 0; i < linhas; i++) {
if (novasLinhas[i] == 1 && linhasCobertas[i] != novasLinhas[i]) {
linhasCobertas[i] = 1;
sol->numLinhas++;
}
}
coluna->visited = TRUE;
return;
}
58
APÊNDICE B – CÓDIGO FONTE DA VERSÃO DISTRIBUÍDA
#include
#include
#include
#include
#include
#include
<stdio.h>
<stdlib.h>
<math.h>
<time.h>
<string.h>
"mpi.h"
//Definições...
#define FALSE 0
#define TRUE 1
#define QTD_ITERACOES 100
#define QTD_FORMIGAS 100
//Variáveis globáis
double alfa
=
double beta
=
double evaporacao =
double feromonio =
long *vet;
(em sua maioria parâmetros)...
1.0; //Parâmetro que regula a influência do feromônio...
2.0; //Parâmetro que regula a influência da função custo...
0.1; //Parâmetro que determina a evaporação...
1.0; //Parâmetro que determina o depósito de feromônio...
//Definição de estruturas...
typedef struct vertices {
long colID; //Número da coluna...
double feromonio; //Valor do feromônio depositado no vértice...
int custo; //Custo da coluna...
long numLinhas; //Número de linhas cobertas pela coluna...
long *linhas; //Linhas cobertas pela coluna...
double funcCusto; //Valor da função custo calculado (em dada seleção de coluna) para a
coluna...
int visited; //Se a formiga K já visitou o vértice ou não...
} Vertice;
typedef struct solucao {
Vertice **conjSolucao; //Vértices selecionados na solução...
long *linhas; //Linhas cobertas pela solução...
long numLinhas; //Número de linhas cobertas pela solução...
int iteracao; //Em que interação esta solução foi encontrada...
int formiga; //Que formiga encontrou esta solução...
long costTotal; //Custo total da solução...
long numColunas; //Número de colunas selecionadas na solução...
} Solucao;
//Declaração de funções...
void mestre();
void escravo(char *arquivo);
Solucao * colonia(long colunas, long linhas, Vertice *grafo);
long geraPosInicial(long pos, long colunas);
Vertice * selecionaPrimeiraColuna(long colunas, long pos, Vertice *grafo);
Vertice * escolheColuna(long colunas, long linhas, Vertice *grafo, long *linhasSelecionadas);
void adicionaColuna(long linhas, Solucao *sol, Vertice *coluna, long posicao);
int main(int argc, char *argv[]) {
int numProcs, rank;
char arquivo[256] = "fontes/";
if (argc < 2) {
printf("ERRO!!!\n\nNumero incorreto de parametros.\nA forma correta para utilizar o
soft eh:");
printf("%s <arquivo de entrada>\n\n", argv[0]);
fflush(stdout);
return 1;
}
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &numProcs);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
if (rank == 0) {
//É o processo mestre...
mestre();
} else {
//É um dos processos escravos...
strcat(arquivo, argv[1]);
escravo(arquivo);
}
MPI_Finalize();
}
void mestre() {
int numProcs, rank, rankSender, indSelecionado, i;
int *processos;
long menorCusto;
long start, end;
MPI_Status status;
59
Solucao **resultado = NULL;
//Pega o rank do processo e o número de processos da solução...
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &numProcs);
//Cria o vetor de resultados...
resultado = (Solucao **) malloc((numProcs - 1) * sizeof(Solucao *));
processos = (int *) malloc((numProcs - 1) * sizeof(int));
if(resultado == NULL) {
printf("ERRO: falta de memoria!!!\n");
fflush(stdout);
exit(1);
}
for (i = 0; i < (numProcs - 1); i++) {
resultado[i] = NULL;
}
//Marca o tempo inicial...
start = time(NULL);
//Recebe as soluções de cada escravo...
for (i = 0; i < (numProcs - 1); i++) {
resultado[i] = (Solucao *) malloc(sizeof(Solucao));
MPI_Recv(&resultado[i]->iteracao, 1, MPI_INT, MPI_ANY_SOURCE, 1, MPI_COMM_WORLD,
&status);
rankSender = status.MPI_SOURCE;
MPI_Recv(&resultado[i]->formiga, 1, MPI_INT, rankSender, 2, MPI_COMM_WORLD, &status);
MPI_Recv(&resultado[i]->costTotal,
1,
MPI_LONG,
rankSender,
3,
MPI_COMM_WORLD,
&status);
MPI_Recv(&resultado[i]->numColunas, 1, MPI_LONG, rankSender, 4, MPI_COMM_WORLD,
&status);
processos[i] = rankSender;
}
//Verifica qual a melhor...
menorCusto = resultado[0]->costTotal;
indSelecionado = 0;
for (i = 0; i < (numProcs - 1); i++) {
if (resultado[i]->costTotal < menorCusto) {
menorCusto = resultado[i]->costTotal;
indSelecionado = i;
}
}
//Marca o tempo final...
end = time(NULL);
//Exibe a melhor delas...
printf("\n\n*** Resultado da melhor solucao encontrada ***\n\n");
printf("Numero de colunas: %ld\n", resultado[indSelecionado]->numColunas);
/*printf("Colunas: ");
conjSolucao = resultado[indSelecionado]->conjSolucao;
for (i = 0; i < resultado[indSelecionado]->numColunas; i++) {
p = *conjSolucao;
printf("%ld ", p->colID);
conjSolucao++;
}*/
printf("\nCusto total: %ld\n", resultado[indSelecionado]->costTotal);
printf("Solucao encontrada na %d iteracao pela formiga %d.\n", resultado[indSelecionado]>iteracao, resultado[indSelecionado]->formiga);
printf("Solucao encontrada no escravo de rank %d.\n", processos[indSelecionado]);
printf("Tempo total de processamento: %ld.\n", (end - start));
printf("Implementacao: DISTRIBUIDA\n");
fflush(stdout);
//Libera tudo...
for (i = 0; i < (numProcs - 1); i++) {
free(resultado[i]);
}
free(resultado);
//Finaliza...
return;
}
void escravo(char *arquivo) {
MPI_Status status;
FILE *arqFonte;
Vertice *grafo = NULL, *p = NULL;
Solucao *resultado = NULL;
Vertice **conjSolucao = NULL;
long *linhasCobertas = NULL;
long linhas, colunas, i, j, l;
//Abre o arquivo de entrada...
if ((arqFonte = fopen(arquivo, "r")) == NULL) {
printf("ERRO: nao foi possivel abrir o arquivo %s!!!\n", arquivo);
fflush(stdout);
exit(2);
}
//Entra do número de linhas e colunas...
fscanf(arqFonte, "%ld", &linhas); //Linhas...
fscanf(arqFonte, "%ld", &colunas); //Colunas..
//Cria o grafo...
grafo = (Vertice *) malloc((colunas) * sizeof(Vertice));
if(grafo == NULL) {
60
printf("ERRO: falta de memoria!!!\n");
fflush(stdout);
exit(1);
}
p = grafo;
//Preenche o grafo...
for (i = 0; i < colunas; i++) {
p->colID = i;
p->feromonio = feromonio;
//Entra o custo das colunas...
fscanf(arqFonte, "%d", &p->custo);
//Entra o número de linhas do grafo...
fscanf(arqFonte, "%ld", &p->numLinhas);
//Cria e limpa as linhas...
linhasCobertas = (long *) malloc(linhas * sizeof(int));
if(linhasCobertas == NULL) {
printf("ERRO: falta de memoria!!!\n");
fflush(stdout);
exit(1);
}
for (j = 0; j < linhas; j++) {
linhasCobertas[j] = 0;
}
//Entra as linhas...
for (j = 0; j < p->numLinhas; j++) {
fscanf(arqFonte, "%ld", &l);
linhasCobertas[l - 1] = 1;
}
p->linhas = linhasCobertas;
//Entra o valor da função custo...
p->funcCusto = 0.0;
//Seta o vértice como não visitado...
p->visited = FALSE;
p++;
}
//Fecha o arquivo...
fclose(arqFonte);
//Processa...
resultado = colonia(colunas, linhas, grafo);
//Retorna o resultado pro mestre...
MPI_Send(&resultado->iteracao, 1, MPI_INT, 0, 1, MPI_COMM_WORLD);
MPI_Send(&resultado->formiga, 1, MPI_INT, 0, 2, MPI_COMM_WORLD);
MPI_Send(&resultado->costTotal, 1, MPI_LONG, 0, 3, MPI_COMM_WORLD);
MPI_Send(&resultado->numColunas, 1, MPI_LONG, 0, 4, MPI_COMM_WORLD);
//Libera tudo...
free(resultado->linhas);
free(resultado->conjSolucao);
free(resultado);
p = grafo;
for (i = 0; i < colunas; i++) {
free(p->linhas);
p++;
}
free(grafo);
//Finaliza...
return;
}
Solucao * colonia(long colunas, long linhas, Vertice *grafo) {
int i, k, m, indSelecionado, qtdIntrEscravo, numProcs, rank;
int primeira;
long *linhasCobertas = NULL;
long j, menorCusto;
long *posInicial;
double *feromDeposito;
MPI_Status status;
Solucao *melhor = NULL, **iteracao = NULL;
Solucao *atual = NULL;
Vertice *coluna = NULL;
Vertice **conjSolucao = NULL;
Vertice *p = NULL;
//Pega o rank do processo e o número de processos da solução...
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &numProcs);
//Define a quantidade de iterações do escravo...
qtdIntrEscravo = (int)QTD_ITERACOES / (numProcs - 1);
if (rank == numProcs - 1) {
if (qtdIntrEscravo * numProcs < QTD_ITERACOES) {
qtdIntrEscravo += QTD_ITERACOES - qtdIntrEscravo * numProcs;
}
}
//Cria o vetor de posições iniciais...
posInicial = (long *) malloc(QTD_FORMIGAS * sizeof(long));
if(posInicial == NULL) {
printf("ERRO: falta de memoria!!!\n");
fflush(stdout);
exit(1);
61
}
//Preenche a posição inicial das formigas...
for (k = 0; k < QTD_FORMIGAS; k++) {
posInicial[k] = geraPosInicial(k, colunas);
}
free(vet);
//Processa...
for (i = 0; i < qtdIntrEscravo; i++) { //Iterações...
//printf("Iteracao: %d\n", i);
//fflush(stdout);
//Cria o vetor iteracao...
iteracao = (Solucao **) malloc(QTD_FORMIGAS * sizeof(Solucao *));
for (m = 0; m < QTD_FORMIGAS; m++) {
iteracao[m] = NULL;
}
for (k = 0; k < QTD_FORMIGAS; k++) { //Formigas
//printf("Formiga: %d\n", k);
//Cria uma nova solução a ser preenchida...
linhasCobertas = (long *) malloc(linhas * sizeof(int));
conjSolucao = (Vertice **) malloc((colunas) * sizeof(Vertice *));
iteracao[k] = (Solucao *) malloc(sizeof(Solucao));
if(linhasCobertas == NULL || conjSolucao == NULL || iteracao[k] == NULL) {
printf("ERRO: falta de memoria!!!\n");
fflush(stdout);
exit(1);
}
iteracao[k]->iteracao = i;
iteracao[k]->formiga = k;
iteracao[k]->numColunas = 0;
iteracao[k]->numLinhas = 0;
iteracao[k]->costTotal = 0;
iteracao[k]->linhas = linhasCobertas;
iteracao[k]->conjSolucao = conjSolucao;
//Limpa todas as linhas...
for (j = 0; j < linhas; j++) {
linhasCobertas[j] = 0;
}
//Seta primeira para TRUE para que a formiga possa adicionar a
//primeira posição (coluna) sorteada...
primeira = TRUE;
do {
//Atividade da formiga k...
if (primeira == TRUE) {
//Seleciona a primeira coluna a ser adicionada...
coluna = selecionaPrimeiraColuna(colunas, posInicial[k], grafo);
//Adiciona a nova coluna...
adicionaColuna(linhas, iteracao[k], coluna, iteracao[k]->numColunas);
primeira = FALSE;
} else {
//Escolhe uma nova coluna a ser adicionada...
coluna = escolheColuna(colunas, linhas, grafo, linhasCobertas);
//Adiciona a nova coluna...
adicionaColuna(linhas, iteracao[k], coluna, iteracao[k]->numColunas);
}
iteracao[k]->numColunas++;
} while (iteracao[k]->numLinhas < linhas) ;
//Seta todos os vértice do grafo como não visitados...
p = grafo;
for (j = 0; j < colunas; j++) {
p->visited = FALSE;
p++;
}
}
//Atualiza o feromônio...
//Evaporação...
p = grafo;
for (j = 0; j < colunas; j++) {
p->feromonio = (1 - evaporacao) * p->feromonio;
p++;
}
//Depósito...
feromDeposito = (double *) malloc((colunas) * sizeof(double));
for (m = 0; m < colunas; m++) {
feromDeposito[m] = 0;
}
for (m = 0; m < QTD_FORMIGAS; m++) {
conjSolucao = iteracao[m]->conjSolucao;
for (j = 0; j < iteracao[m]->numColunas; j++) {
conjSolucao[j]->feromonio += feromonio / iteracao[m]->costTotal;
feromDeposito[conjSolucao[j]->colID] += feromonio / iteracao[m]->costTotal;
}
}
//Comunica aos demais escravos o depósito feito...
for (m = 1; m < numProcs; m++) {
//Pula o rank 0 (zero), pois este é o mestre...
if (m != rank) {
62
//Pula também o rank do escravo atual...
MPI_Send(feromDeposito, colunas, MPI_DOUBLE, m, 10, MPI_COMM_WORLD);
}
}
//Recebe dos demais escravos o depósito feito por eles...
for (m = 1; m < numProcs; m++) {
//Pula o rank 0 (zero), pois este é o mestre...
if (m != rank) {
//Pula também o rank do escravo atual...
MPI_Recv(feromDeposito,
colunas,
MPI_DOUBLE,
MPI_ANY_SOURCE,
MPI_COMM_WORLD, &status);
p = grafo;
for (j = 0; j < colunas; j++) {
//Faz o depósito...
if (feromDeposito[j] != 0) {
p->feromonio += feromDeposito[j];
}
p++;
}
}
}
//Libera o feromDeposito...
free(feromDeposito);
//Guarda a melhor solução gerada até agora...
//Verifica qual a melhor solução da iteração...
menorCusto = iteracao[0]->costTotal;
indSelecionado = 0;
for (m = 1; m < QTD_FORMIGAS; m++) {
if (iteracao[m]->costTotal < menorCusto) {
menorCusto = iteracao[m]->costTotal;
indSelecionado = m;
}
}
//Verifica se a melhor solução da iteração é melhor que a
// melhor até o momento...
if (i == 0 || iteracao[indSelecionado]->costTotal < melhor->costTotal) {
//Ou esta é a primeira iteração, portanto a melhor solução ainda
// está vazia, ou o custo da melhor solução da iteração é menor que
// o da melhor até o momento...
melhor = iteracao[indSelecionado];
}
//Libera a iteracao inteira...
for (m = 0; m < QTD_FORMIGAS; m++) {
if (m != indSelecionado) {
free(iteracao[m]->linhas);
free(iteracao[m]->conjSolucao);
free(iteracao[m]);
}
}
}
return melhor;
}
long geraPosInicial(long pos, long colunas) {
static int primeira = TRUE;
long i, outro, temp;
if (primeira == TRUE) {
//Cria o vetor...
vet = (long *) malloc(colunas * sizeof(int));
if(vet == NULL) {
printf("ERRO: falta de memoria!!!\n");
fflush(stdout);
exit(1);
}
//Preenche o vetor...
for (i = 0; i < colunas; i++) {
vet[i] = i;
}
//Embaralha o vetor...
for (i = 0; i < colunas; i++) {
outro = rand() % (colunas);
temp = vet[i];
vet[i] = vet[outro];
vet[outro] = temp;
}
primeira = FALSE;
}
//Retorna a posição...
if (pos >= colunas) {
pos -= colunas;
}
return vet[pos];
}
Vertice * selecionaPrimeiraColuna(long colunas, long pos, Vertice *grafo) {
Vertice *p = NULL;
long i;
10,
63
p = grafo;
for (i = 0; i < pos; i++) {
p++;
}
return p;
}
Vertice * escolheColuna(long colunas, long linhas, Vertice *grafo, long *linhasCobertas) {
Vertice *p = NULL;
long *lin = NULL, i, j;
long totLinhas, colsAcessiveis = 0, random;
double custoTotal = 0.0, custo, prob;
//Calcula a função custo total e de cada vértice...
p = grafo;
for (i = 0; i < colunas; i++) {
if (p->visited == TRUE) {
p->funcCusto = 0.0;
} else {
lin = p->linhas;
totLinhas = 0;
if (lin == NULL) {
printf("ERRO: o vetor de linhas do vertice eh nulo!!!\n");
fflush(stdout);
exit(3);
}
if (linhasCobertas == NULL) {
printf("ERRO: o vetor de linhas da solucao atual eh nulo!!!\n");
fflush(stdout);
exit(4);
}
for (j = 0; j < linhas; j++) {
//Conta as linhas cobertas ainda não adicionadas...
if (lin[j] == 1 && linhasCobertas[j] == 0) {
totLinhas++;
}
}
if (totLinhas > 0) {
colsAcessiveis++;
//Calcula a função custo de cada vértice...
custo = (double)((double)totLinhas / (double)p->custo);
p->funcCusto = pow(p->feromonio, alfa) * pow(custo, beta);
//Calcula a função custo total...
custoTotal += p->funcCusto;
} else {
//Todas as linhas cobertas pelo vértice já foram cobertas pela solução
atual...
p->funcCusto = 0.0;
p->visited = TRUE;
}
}
p++;
}
//Calcula a probabilidade de cada coluna ser escolhida...
if (custoTotal < 1) {
random = 0;
} else {
srand(time(NULL));
random = rand() % (int)custoTotal;
}
p = grafo;
while (p->visited == TRUE) {
p++;
}
prob = p->funcCusto;
while ((int)prob < random) {
p++;
prob += p->funcCusto;
}
return p;
}
void adicionaColuna(long linhas, Solucao *sol, Vertice *coluna, long posicao) {
long *linhasCobertas = NULL;
long *novasLinhas = NULL;
long i;
//Adiciona a coluna à solunção...
sol->conjSolucao[posicao] = coluna;
//Soma o custo da coluna no custo total da solunção...
sol->costTotal += coluna->custo;
//Atualiza as linhas cobertas pela solução...
linhasCobertas = sol->linhas;
novasLinhas = coluna->linhas;
for (i = 0; i < linhas; i++) {
if (novasLinhas[i] == 1 && linhasCobertas[i] != novasLinhas[i]) {
linhasCobertas[i] = 1;
sol->numLinhas++;
}
64
}
coluna->visited = TRUE;
return;
}