Abordagem de Colônia de Formigas aplicada ao
Problema Quadrático de Alocação
Julio Cezar Zanoni
Orientador: Leandro dos Santos Coelho
Co-orientador: Fábio Alessandro Guerra
Curso de Especialização em Inteligência Computacional.
Pontifícia Universidade Católica do Paraná
Curitiba, dezembro de 2005.
Resumo
O Problema Quadrático de Alocação - PQA (Quadratic Assigment Problem - QAP) é
do tipo Não Polinomial-Completo (NP-Completo), o que torna sua resolução bastante
complexa e de alto custo computacional para casos onde o número de variáveis e restrições
seja maior que 20. Vários estudos têm sido desenvolvidos e os que melhor se destacaram
foram aqueles utilizando grafos e programação quadrática. Recentemente, o uso de técnicas
heurísticas e metaheurísticas têm se mostrado eficientes na resolução deste tipo de problema
e até mesmo adotadas em sistemas comerciais. A proposta deste trabalho é o uso da técnica
metaheurística da inteligência de enxames ou inteligência coletiva, mais precisamente de
colônia de formigas na resolução deste tipo de problema.
1
Introdução
O PQA tem recebido a atenção de muitos pesquisadores nas últimas quatro décadas e
diferentes soluções para ele foram apresentadas, sendo a programação quadrática [BRI2001] e
teoria de grafos [FOU1978], as que mais se destacaram. Também se pode citar outra solução
utilizando como estrutura de dados árvores binárias [TAM1991] e que apresenta melhor
capacidade de trabalhar com restrições abrangentes [VAL2002].
Desde a sua primeira formulação, o PQA tem atraído a atenção da comunidade
científica, não apenas pela sua importância prática e teórica, mas principalmente pela sua
complexidade. É um problema de otimização combinatória, considerado como um dos mais
difíceis de ser resolvido. Instâncias de ordem n > 20 não podem ser resolvidas exatamente em
tempo computacional polinomial.
O PQA é um problema do tipo NP-árduo e a menos que P = NP não será possível
encontrar para ele uma solução aproximada por um fator constante da solução ótima. Tais
resultados são válidos mesmo quando fluxos e distâncias aparecem como coeficientes de
matrizes simétricas [ELI2004].
Existem diversos problemas NP-árduos de otimização combinatória, como os
problemas do caixeiro viajante, roteamento de veículos, empacotamento, clique maximal1 e
isomorfismo de grafos, estes podendo ser modelados como PQA’s. A investigação de
problemas de Otimização Combinatória através de instâncias disponibilizadas na Internet é
uma tendência atual, permitindo que sejam utilizados algoritmos exatos, se possível, ou obter
ótimos locais melhores que a melhor solução conhecida para exemplares cujo ponto ótimo
1
Veja: http://www.ime.usp.br/~pf/algoritmos_em_grafos/aulas/cliques.html
ainda não foi comprovado. Anstreicher (2003) registra os recentes avanços na solução de
instâncias do PQA, destacando-se os novos algoritmos e as novas estruturas computacionais
utilizadas para isto. Cabe informar que além dos exemplares disponíveis para testes na
Internet, também existem geradores de instâncias com ótimos conhecidos que são utilizados
para testar os algoritmos criados pela comunidade científica.
Outra tendência atual das pesquisas em Otimização Combinatória é estudar versões
polinomiais de problemas ou procurar instrumentos para análise da dificuldade dos
exemplares.
Na tentativa de identificar novas propriedades estruturais para as instâncias do PQA,
muitas formulações aparecem com base em diferentes enfoques.
A solução apresentada por Foulds e Robinson (1976) é baseada na teoria de grafos.
Nesta abordagem, é formado um grafo, onde cada vértice representa um departamento2 e cada
aresta representa a possibilidade de atribuição de departamentos adjacentes.
Uma modelagem recente foi apresentada por Tam, Kar e Yan (1992), nela é utilizada
uma árvore binária como estrutura de dados e para a busca de soluções utiliza um algoritmo
genético. Esta mesma modelagem também foi usada por Furtado e Lorena (1997), porém,
utilizando o método heurístico de busca Tabu.
Os layouts presentes no meio industrial podem conter vários departamentos sujeitos a
um grande número de restrições [VAL2002], que o projetista deve levar em consideração, por
exemplo:
•
áreas de circulação (corredores de passagem e possíveis desníveis existentes);
•
sistema(s) ou área(s) para a movimentação de materiais;
•
localização das máquinas dentro dos departamentos;
•
localização das áreas de início e fim do processo.
O PQA é um problema bastante interessante para pesquisa, principalmente quando
apresenta grandes dimensões, levando-se em consideração que um PQA com mais de 20
instâncias é considerado intratável, segundo Gambardella, Taillard e Dorigo (1999). Uma das
principais abordagens, a programação quadrática, foi demonstrada ser NP-Completo
[SAH1976] e vários métodos heurísticos têm sido propostos para a obtenção de soluções
satisfatórias.
Do ponto de vista econômico, uma boa distribuição dos departamentos permite a
redução nos custos de produção e melhoria da produtividade. A cada ano o volume de
investimento em novas indústrias e outras instituições incentiva a busca de novas alternativas
para o problema. Além disso, muitas indústrias têm seus layouts modificados anualmente. A
reorganização de layout é uma atividade contínua em qualquer organização que pretenda ser
competitiva e eficiente, devido ao aparecimento de novas máquinas e equipamentos e até
mesmo novas teorias e técnicas que tornam modelos e métodos obsoletos.
Na tentativa de tornar mais eficientes estas contínuas alterações de layout tanto nas
indústrias bem como em outras aplicações, foram criados vários algoritmos de PQA, estes
algoritmos são classificados em: algoritmos construtivos, de melhoramento, híbridos e que
utilizam teoria dos grafos.
•
Algoritmos construtivos
Nos algoritmos construtivos a solução é construída passo a passo. Em outras palavras,
as instalações são alocadas uma de cada vez, até o arranjo físico estar completo.
2
Levando-se em consideração a distribuição dos departamentos de uma indústria.
Existem duas vezes mais algoritmos construtivos que algoritmos de melhoramento e
alguns dos mais conhecidos algoritmos construtivos são:
•
HC66, Hiller e Connors (1966);
•
ALDEP, Seehof e Evans (1967);
•
CORELAP, Lee e Moore (1967);
•
RMA Comp I, Murther e McPherson (1970);
•
MAT, Edwards et al. (1970);
•
PLANET, Deisenroth e Apple (1972);
•
LSP, Zoller e Adendorff (1972);
•
Algoritmo de alocação linear, Neghabat (1974);
•
FATE, Block (1978);
•
INLAYT, O’Brien e Abdel Barr (1980);
•
FLAT, Heragu e Kusiak (1986); e
•
COMLADII, Ziai e Sule (1991).
•
Algoritmos de melhoramento
A característica básica do algoritmo de melhoramento é gerar aleatoriamente uma
solução inicial e com base nesta solução, realizar trocas sistemáticas entre instalações e
avaliar os resultados. As trocas que produzem uma solução melhor são guardadas e o
procedimento continua até que não se obtenha uma solução melhor. Logo, o desempenho e a
qualidade da solução gerada por um algoritmo de melhoramento dependem muito da
qualidade da solução inicial. A seguir são citados alguns algoritmos de melhoramento:
•
CRAFT, Armour e Buffa (1963) e Buffa et al. (1964);
Variações do CRAFT:
•
COFAD, Tompkins e Reed (1976), baseado na técnica, Nugent et al. (1968);
•
COL, Vollman et al., (1968);
•
CRAFT-M, Hicks e Cowan (1976);
•
SPACECRAFT, Johnson (1982);
•
CRAFT-3D, Cinar (1975);
•
SPACECRAFT, Jacobs (1984);
•
MOCRAFT, Svestka (1990); e
•
FACLO, Allenbach e Werner (1990).
Outros algoritmos:
•
H63, Hillier (1963);
•
H63-66, Hillier e Connors (1966);
•
Algoritmos SAMPLING 1º, Nugent et al. (1968) e 2º, Hitchings e Cottam (1976);
•
FRAT, Khalil (1973);
•
COFAD-F, modificado por Shore e Thompkins (1980); e
•
Algoritmo revisado de Hillier, Picone e Wilhelm (1984).
Desenvolveu-se também um modelo para solução de problemas com sistema de
manufatura flexível, que é uma extensão do CRAFT incorporando um modelo,
computacionalmente eficiente de filas em rede. Existe também um outro método conhecido, o
MASL (Multifactor Approach for Selecting from among computer generated Layouts) que faz
a análise em termos de medidas quantitativas tais como: ineficiência de fluxo, distância entre
áreas funcionais e aumento de capacidade. Os softwares utilizados para gerar os arranjos
físicos de teste foram o CRAFT, ALDEP e CORELAP.
•
Algoritmos híbridos
Os algoritmos são classificados como híbridos quando possuem características dos
algoritmos ótimos e sub-ótimos ao mesmo tempo.
Burkard e Stratman (1978) propuseram um algoritmo heurístico que utiliza o método
de branch and bound e um algoritmo de melhoramento. Este obtém uma solução inicial
usando o algoritmo de branch and bound e um limite de tempo. Depois esta solução inicial
passa é usada por um algoritmo de melhoramento denominado VERBES. Este algoritmo
executa trocas em forma de pares (2-opt) e até de triplas (3-opt), alternadamente, e termina
quando a melhor solução encontrada não pode ser melhorada.
Burkard e Stratman (1978) também propuseram um algoritmo similar ao anterior, só
que desta vez utilizando, para encontrar a solução inicial, o algoritmo de Gaschutz e Ahrens
(1968).
Bazara e Kirca (1983) apresentaram um algoritmo heurístico baseado no método de
branch and bound que reduz o tempo de processamento, sem fazer a exploração de vértices
que são uma imagem invertida de um vértice explorado anteriormente. Em outras palavras, se
o vértice A é uma imagem invertida do vértice B o seu limite inferior já foi calculado
anteriormente, então em buscas futuras não precisa fazer trocas no vértice A . Os métodos
heurísticos, utilizando os algoritmos de melhoramento de 2-way e 4-way e uma regra para
selecionar os vértices a serem pesquisados, produzem resultados de boa qualidade.
A seguir são citados alguns algoritmos híbridos:
•
FLAC, Scriabin e Vergin (1985);
•
DISCON, Drezner (1980); e
•
Houshyar e White (1997).
•
Algoritmos que utilizam teoria dos grafos
Os algoritmos que utilizam teoria dos grafos buscam um sub-grafo maximal planar a
partir de um grafo completo que mostra a relação entre as instalações. O dual deste sub-grafo
maximal planar determina o arranjo físico de instalações. Existem algoritmos que podem ser
classificados como algoritmos que utilizam a teoria dos grafos e como algoritmos construtivos
que serão apresentados a seguir.
Seppanen e Moore (1970) propuseram um procedimento utilizando a teoria dos grafos
acima mencionada. Os mesmos autores, em 1975, propuseram um algoritmo heurístico
utilizando a mesma estratégia, que determina a árvore máxima com base no grafo maximal.
Com a ajuda de um processo de adição de eixos, a árvore máxima é então usada para obter o
sub-grafo maximal planar e a partir do dual do sub-grafo maximal planar determina-se o
arranjo físico para as instalações.
Outros algoritmos que utilizam teoria dos grafos são:
•
branch and bound;
•
Deltahedron;
•
Wheel expansion;
•
Métodos heurísticos que transformam o sub-grafo máximal planar em um arranjo
físico de instalações com áreas diferentes;
Também se podem citar vários métodos que têm sido desenvolvidos para solucionar o
problema de PQA, utilizando várias técnicas heurísticas. Dentre estas técnicas pode-se citar:
•
simulated annealing;
busca Tabu;
•
busca híbrida genética-tabu; e
•
recentemente, baseado em busca espalhada.
A proposta para este trabalho é o estudo baseado na maneira como as formigas
procuram por comida e encontram seu caminho de volta ao ninho, ou seja, imitar o
comportamento de uma colônia de formigas. A solução de problemas através da metáfora do
comportamento social de insetos vem se tornando um assunto emergente nos últimos anos.
Como será visto mais adiante, este enfoque enfatiza a distribuição do problema e a interação
direta/indireta entre agentes relativamente simples.
•
1.1
O Problema Quadrático de Alocação
O PQA é um problema que tem sua formulação original dada por Koopmans e
Beckman (1957), em um contexto de determinar a melhor alocação de usinas (plantas
industriais) a localidades. O problema consistia em alocar n usinas indivisíveis a n posições
de forma a maximizar a renda total dessas usinas, através da minimização do custo de
transporte de mercadorias entre elas. Neste problema existem duas matrizes, uma denominada
de matriz de fluxo entre as usinas F = (f ij ) , indicando o número de unidades de uma
determinada mercadoria a ser transportada entre a i-ésima e a j-ésima usina, e a outra
denominada de matriz das distâncias entre as localidades D = (d kl ) , indicando a distância entre
a k-ésima e a l-ésima posições.
Matematicamente este problema pode ser formulado como segue:
Seja uma matriz de custo C = (c ijkl ) , onde c ijkl = custo do par de usinas (i, j ) no par de
posições (k , l ) . Usando as matrizes definidas acima, um elemento seria escrito
como: c ijkl = f ij d kl .
Seja ainda ρ (i ) uma função que para uma determinada planta i retorna sua
localidade. Encontre uma permutação ρ = ( ρ (1), ρ (2),..., ρ (n)) dos inteiros 1,2,..., n que
minimize a quantidade:
n
n
T = ∑∑ cijρ ( i ) ρ ( j )
Equação 1-1
i =1 j =1
onde:
cij ; custo entre as usinas i e j em relação à sua posição;
ρ (i ) ρ ( j ) ; distâncias entre as localidades i e j .
Essa formulação também enfatiza o caráter combinatório desta classe de problemas.
Formulando o problema com programação inteira, ele passa a ser expresso da seguinte
maneira:
Encontre o valor das variáveis x ij , i, j = 1, 2, ... , n , que minimize a quantidade:
n
n
n
n
T = ∑∑∑∑ cijkl xij xkl
Equação 1-2
i =1 j =1 k =1 l =1
onde:
cijkl ; custo entre as usinas i e j com relação à sua localização k, l ;
xij xkl ; distâncias entre as localidades i e j .Sujeito às condições abaixo:
xij ∈ {0,1},
i, j = 1, 2, ... , n
Equação 1-3
n
∑x
i =1
ij
n
∑x
j =1
ij
= 1,
j = 1, 2, ... , n
Equação 1-4
= 1,
i = 1, 2, ... , n
Equação 1-5
Os somatórios, Equação 1-4 e Equação 1-5, impõem que toda usina seja alocada a uma
única localidade e que toda localidade receba uma única usina.
Como se pode verificar, o problema de arranjo físico de instalações é caracterizado
como um problema de minimização combinatória. Tendo uma função objetivo a ser
minimizada que é definida sobre um conjunto discreto, cujos elementos são todas as possíveis
alocações de instalações. O número de elementos do conjunto de configurações cresce
fatorialmente com o aumento do número n de instalações, de modo que a busca não pode ser
feita de forma exaustiva quando n é grande. Também, pelo fato de tal conjunto ser discreto,
impossibilita o uso das noções de continuidade, dificultando nos processos que utilizam o
conceito de direção para caminhar na direção do ótimo.
No caso do projeto de arranjo físico de setores dentro de um prédio, o número de
arranjos físicos é igual a n! , sendo n igual ao número de setores a arranjar, considerando-se
que a área total dos setores é igual à área da edificação.
No caso do arranjo físico de máquinas dentro de um departamento, a complexidade
aumenta, pois, além do espaço das máquinas, deve-se considerar o espaço para circulação e
para operação e manutenção dos equipamentos além de áreas para futuras expansões.
Para que se possa avaliar a complexidade do problema, o número de soluções para o
arranjo físico de um setor com 15 departamentos seria 15! , o que fornece 1.307.674.368.000
soluções possíveis a serem testadas. Tais problemas, denominados de NP-Completos,
apresentam uma complexidade de resolução, por consumirem espaço excessivo de memória e
elevado tempo de processamento.
Desta forma, considerando as duas matrizes, citadas anteriormente, F , matriz de fluxo
entre as localidades e D , matriz de distâncias entre as localidades (ambas com dimensões
nxn , simétricas, com diagonal nula e cujas coordenadas reais são não-negativas), resolver um
exemplar do PQA(F,D), é achar o conjunto de valores que corresponde ao caminho de menor
custo para uma atribuição onde pares de instalações são alocadas a pares de localidades e
reciprocamente, ou seja, o PQA consiste em encontrar uma alocação de custo mínimo dos
objetos aos locais predeterminados.
Outra definição é dada por El-Ghazali, Olivier, Cyril e Denis (1999), onde o PQA
pode ser definido como: um conjunto de n objetos O = {O1 , O 2 , …., O n } , um conjunto de n
locais L = {L1 , L 2 , …., L n } , uma matriz de fluxo F, onde cada elemento cij aparece como um
custo entre os objetos O i e O j , uma matriz de distâncias D , onde cada elemento d kl aparece
como uma distância entre uma localização L k e L l , deve-se encontrar uma localização para o
objeto b ij mapeando M : O → L , que minimiza a função abaixo:
n
n
f = ∑∑ cij d M ( i ) M ( j )
i =1 j =1
onde:
cij ; elemento da matriz de custo;
d M (i ) M ( j ) ; distâncias entre as localizações.
Equação 1-6
O PQA, proposto por Koopmans e Beckman (1957), é um modelo matemático que
está relacionado a atividades econômicas e pode ser encontrado em inúmeras aplicações
práticas, por exemplo:
•
minimização da quantidade de ligações entre componentes de placas de circuitos
eletrônicos;
•
desenvolvimento de um framework de decisões de alocação de uma nova
instalação (postos policiais, supermercados, escolas) que atenda a um dado
conjunto de clientes;
•
problemas de escalonamento de horário;
•
definição de design de teclados e painéis de controle;
•
arqueologia;
•
análise de reações químicas;
•
análise estatística;
•
computação paralela e distribuída; e
•
problema relacionado a parques florestais.
No entanto, é como problema de layout que o PQA vem sendo mais extensivamente
aplicado, no planejamento de hospitais e na modelagem de localização de construções em
campus universitário.
1.2
Colônia de Formigas: inspiração biológica e implementação computacional
A metaheurística Colônia de Formigas (CFs) foi proposta como uma abordagem
multi-agente para a resolução de problemas de otimização combinatória. Nesta estratégia, um
conjunto de agentes, chamados de formigas artificiais, ou simplesmente formigas, buscam em
paralelo encontrar as melhores soluções para o problema [ELI2003]. Esta metaheurística foi
proposta a partir de experimentos e observações de uma colônia de formigas real, baseando-se
no comportamento das mesmas na escolha de qual caminho devem tomar para encontrar
comida. Este comportamento permite às formigas encontrar os trajetos mais curtos entre
fontes de alimento e o seu ninho [DOR1996].
Ao andar do ninho até a fonte de alimento e vice-versa, as formigas depositam uma
substância chamada feromônio pelo caminho por onde passam. Quando se decidem sobre qual
sentido ir, os trajetos mais prováveis são marcados por concentrações mais fortes de
feromônio, este comportamento natural é a base para uma interação cooperativa que conduz
ao trajeto mais curto.
É importante destacar também que as formigas são capazes de se adaptar a mudanças
no ambiente. Como por exemplo, quando o primeiro caminho escolhido já não é o mais curto,
devido a algum obstáculo, a reação imediata das formigas é contornar o obstáculo e decidir
novamente qual o novo caminho mais curto.
Figura 1 - Formigas reais desviando de obstáculos.
Considerando a Figura 1, vemos que em A as formigas têm inicialmente um caminho
direto entre o ninho e a fonte de alimento. Em B a trilha inicial de feromônio foi interrompida
por um obstáculo. Isso obriga as formigas a procurarem um novo caminho. O problema agora
é escolher qual direção tomar para contornar o obstáculo. As formigas então escolhem
aleatoriamente a direção, como mostrado em C. As trilhas de feromônio são então
restabelecidas e o próximo passo é decidir qual dos caminhos é o mais curto, ou seja, qual dos
caminhos possui mais feromônio por unidade de tempo. Após essa análise, as formigas
escolhem o caminho mais curto, como mostrado em D.
As formigas estão divididas em dois grandes grupos:
•
as que trabalham dentro do formigueiro, cuidando da rainha e da prole,
empilhando o alimento armazenado, etc.; e
•
as operárias externas, que se deslocam entre o mundo fora da toca e as câmaras
mais próximas da entrada do formigueiro, sem descerem às partes mais profundas
do mesmo.
As operárias começam seu trabalho logo ao amanhecer e são elas que cuidam da
manutenção, as patrulheiras, as operárias do monturo (lixo e dejetos) e as forrageadoras. As
operárias da manutenção são as primeiras a iniciar o trabalho e limpam a entrada do
formigueiro removendo a terra trazida pela água ou que foi usada para tapar a entrada da
colônia ao final do dia de trabalho.
Logo depois é a vez das patrulheiras, que no início não são tão determinadas quanto as
operárias, que fazem a manutenção, dão uma espiada fora da entrada do formigueiro,
agarrando-se à borda da entrada e, agitando as antenas para todos os lados, verificam a
paisagem química do mundo exterior. De alguma forma, a partir de tal verificação, elas
escolhem as direções a serem tomadas pelas forrageadoras. Então as forrageadoras saem para
realizar seu trabalho, como se já soubessem para onde ir. O período de busca por alimentos
pode durar várias horas e as condições meteorológicas têm influência direta sobre o trabalho
de forragear.
1.2.1 Interação entre as formigas
A interação entre as formigas, nada mais é do que uma resposta aos estímulos
químicos. A maioria das espécies de formigas tem visão muito deficitária, percebendo o
mundo onde estão e às outras formigas através de odores. As formigas têm um grande número
de glândulas, cerca de 14 , e cada uma delas secreta uma substância química diferente. Elas
percebem estas substâncias através de suas antenas. Em algumas espécies, ao encontrarem
uma fonte de alimento, quando no seu retorno para o ninho deixam uma trilha química no
solo para marcar o caminho, possibilitando que outras formigas possam alcançar esta mesma
fonte. Os estímulos químicos podem ter respostas diferentes, dependendo do que a formiga
esteja fazendo, não sendo um padrão fixo, é como, por exemplo, o significado de algumas
palavras, conforme o tom usado para falá-las e/ou o contexto em que são inseridas fazem com
que tenham significados distintos.
1.2.2 Procura por alimento
A procura por alimento realizada pelas formigas leva em conta um aspecto muito
importante de sua organização, ou seja, a resposta rápida a mudanças nos recursos naturais e
do ambiente onde estão.
Por toda parte existem formigas à espreita, as patrulheiras, prontas para mobilizarem
suas companheiras quando se fizer necessário. Por exemplo, quando se deixa qualquer
alimento, principalmente doces, sobre uma mesa em casa ou algo caído no chão as formigas
aparecem numa questão de minutos. Isto porque as patrulheiras ficam mais tempo onde
encontram alimento e as forrageadoras só seguem trilhas que contenham um número mínimo
de patrulheiras, dessa forma, uma trilha forrageadora leva a um local com um nível mínimo de
alimento, fato que faz com que compense às outras forrageadoras seguirem esta trilha.
1.2.3 Ação sem comando
Ninguém diz a uma formiga o que ela deve fazer. O comportamento de cada uma delas
depende da interação local com as outras formigas e com o mundo da maneira como cada
uma o percebe. A experiência de uma formiga está intimamente ligada aos seus sentidos tátil
e químico, desta forma elas se movimentam de um lado para o outro tentando se ajustar ao
ambiente onde estão inseridas, encontram-se com outras formigas e a partir daí, sem que
exista nenhuma explicação, tomam suas decisões e começam seu trabalho. Porém, mesmo
com elas agindo desta forma, o comportamento de uma colônia é previsível, o que significa
que a experiência das formigas deve, de alguma forma, ter alguma regularidade.
1.2.4 Gestão do formigueiro
Quando ocorrem mudanças nas condições do formigueiro, as formigas trocam suas
tarefas, por exemplo: se aparece uma nova fonte de alimento, de forma imprevista, uma
formiga que estava trabalhando no monturo (espécie de lixeira) troca seu turno e se torna uma
forrageadora, coletando o alimento.
As tarefas são atribuídas a cada formiga de modo que elas tenham uma função
específica, de maneira a que existam tantas formigas quantas forem necessárias para realizar
uma determinada tarefa. Este fato faz com que a colônia possa tratar com problemas
dinâmicos, sendo, portanto um processo de ajuste contínuo, processo este que opera sem que
exista nenhum controle central ou hierárquico para designar as tarefas para cada operária.
A rainha não tem nenhuma autoridade sobre as operárias e, portanto, não decide quem
faz o que. As formigas não têm a capacidade de avaliar as necessidades da colônia como um
todo ou mesmo saber quantas operárias estão trabalhando naquele instante, nem mesmo no
que estão trabalhando e decidir quantas deveriam ser remanejadas, cada operária toma
somente decisões simples.
1.2.5 Formigueiro como um sistema complexo
O comportamento das formigas, apesar de simples, gera um comportamento global
complexo. O comportamento de cada unidade “burra”, por assim dizer, está ligado ao sistema
como um todo, de modo que para estudar o funcionamento de uma colônia de formigas, não
podemos desagregá-lo e estudar separadamente cada indivíduo. Também existe outra
consideração a se fazer: nenhuma formiga nasce pré-determinada para exercer uma tarefa
específica, a função de cada uma delas muda juntamente com as condições do meio em que se
encontra inserida, inclusive com relação às atividades que as outras formigas estão realizando.
1.2.6 Formigueiro “cibernético”
Depois de avaliados alguns dos aspectos do funcionamento de uma colônia de
formigas e dos indivíduos que a compõem, pode-se falar sobre sistemas informatizados e
algoritmos que “imitam” parte deste comportamento, a fim de ser aplicado na resolução de
problemas.
A metaheurística CFs foi aplicada ao problema do Caixeiro Viajante e desde então,
pesquisadores têm desenvolvido atividades com o intuito de aprimorar e aplicar a abordagem
aos mais diferentes tipos de problemas de otimização.
A metaheurística CFs é baseada em modelos probabilísticos parametrizados, usados
para modelar o caminho marcado pelo feromônio [DOR1996]. Para isso, as formigas
artificiais executam caminhadas aleatórias em um grafo completamente conexo G = (N, A) ,
cujos vértices são os componentes N e A que representam o conjunto das conexões. Este
grafo é comumente chamado de Grafo de Construção. Quando um problema de otimização
combinatória com restrições é considerado, as restrições do problema são embutidas no
procedimento de construção das formigas artificiais.
Na maioria das aplicações, as formigas são implementadas para construir soluções
viáveis, mas às vezes é desejável também deixar um parâmetro para a trilha de feromônio.
Estes valores de feromônio são usados pelas formigas para tomar decisões probabilísticas
sobre como se mover no Grafo de Construção.
Cada formiga aplica, passo a passo, uma política de decisão para a construção de uma
solução local e, então, construir uma solução do problema como um todo. Em cada
informação local do nó, mantida no próprio nó ou nos arcos que partem deste nó, é usada uma
maneira de decidir o nó seguinte para o qual a formiga irá se mover. A regra de decisão usada
por uma formiga k que se localiza no nó i é a trilha de feromônio t ij usada para computar a
probabilidade da formiga k escolher o nó para o próximo movimento, onde representa o
conjunto de nós vizinhos ao nó i . No início do processo de procura, uma pequena quantidade
de feromônio é associada a todas as arestas e, a cada vez que uma formiga passa por essa
aresta, a quantidade de feromônio é atualizada. Desta forma podemos descrever uma simples
fórmula para calcular na metaheurística de otimização CFs:
pijk =
tij
∑t
j∈Ni
, se j ∈ N i
ij
pijk = 0 , se j ∉ N i
onde:
t ij ; quantidade de feromônio depositado na trilha.
Equação 1-7
Enquanto a solução é construída, as formigas artificiais depositam feromônio nas
arestas em que passam.
Para esta regra, que simula o feromônio das formigas reais, uma formiga que usa o nó
i ligado por uma aresta ao nó j aumenta a probabilidade de outras formigas utilizarem o
mesmo nó no futuro. A Figura 2 abaixo ilustra como uma formiga artificial constrói uma
solução do ninho (início) até a comida (fim). A cada nó percorrido ela deposita uma
quantidade de feromônio. A próxima formiga artificial tenderá a seguir os caminhos que
possuírem mais feromônio, no caso da figura, os nós mais escuros.
Figura 2 - Atualização de feromônio.
Para uma rápida convergência, a trilha de feromônio que não está sendo utilizada
“evapora”, assim como em uma colônia de formigas real, decrementando a quantidade de
feromônio depositado nos nós que não estão sendo percorridos a cada iteração do algoritmo,
isto resulta na criação de um caminho preferencial, o qual será seguido por uma quantidade
maior de formigas a cada iteração.
Em geral, as soluções encontradas por cada formiga, trabalhando isoladamente, são de
baixa qualidade e as melhores soluções são encontradas quando as formigas trabalham de
forma cooperativa. Esta é a base para a inteligência de enxame, que, a partir de indivíduos
simples e de modo cooperativo são capazes de resolver problemas complexos.
As soluções são expressas como um caminho, com custo mínimo, que respeite as
restrições impostas pelo problema. O estado interno da formiga armazena informações sobre o
seu passado histórico, tais como a seqüência de estados que gera a solução, a contribuição de
cada movimento executado e o valor da solução gerada, formando assim sua memória e o seu
conhecimento.
Cada formiga constrói uma solução movendo-se através de uma seqüência finita de
estados sucessivos. Os movimentos são selecionados a partir da regra de transição de estados,
que se baseia na memória da formiga e na quantidade de feromônio acumulada nas trilhas. O
que se observa é que pontos que não foram muito visitados no início serão menos ainda com o
passar do tempo. Uma vez que a formiga realizou sua tarefa, que é a construção de uma
solução e o depósito de feromônio, ela morre, ou seja, é eliminada do sistema, deixando seu
conhecimento para que uma nova formiga venha utilizá-lo.
A cada transição é associada uma quantidade de feromônio no ambiente. Decisões
sobre quando e quanto feromônio depositar, depende das características do problema e do
projeto de implementação. As formigas podem depositar feromônio durante a construção da
solução, assim, cada vez que um novo estado é selecionado, o feromônio associado à
transição pode ser atualizado. Em geral, a quantidade de feromônio depositada é proporcional
à qualidade da solução que foi construída ou que está em construção.
Por fim, o pseudocódigo da metaheurística Colônia de Formigas pode ser descrita da
seguinte forma, segundo Lorenzoni, Ahonen e Alvarenga (2001):
Repita
Crie as formigas e posicione cada uma num estado inicial;
Repita
Para cada formiga faça
Aplique a regra de transição de estado para incrementalmente
construir uma solução;
Aplique a regra de atualização local do feromônio;
Fim para;
Até que todas as formigas tenham construído uma solução completa;
Gere a solução associada a cada uma das formigas;
Aplique a regra de atualização global do feromônio;
Guarde a melhor solução encontrada até o momento;
Até que o critério de parada seja satisfeito.
Em resumo, este tipo de comportamento pode ser valioso quando adaptado
computacionalmente e utilizado na resolução de problemas do tipo Caixeiro Viajante,
escalonamento, roteamento, PQA entre outros de minimização combinatória.
2
Problema
Existem vários tipos de problemas que podem ser tratados com o uso da
metaheurística colônia de formigas. No caso do PQA, que se mostra como um desafio de
otimização combinatória e cada vez mais tem atraído a atenção da comunidade científica na
busca de soluções eficientes, torna-se um bom tema para este trabalho.
No final dos anos 90, Nugent, Vollmann e Ruml, apresentaram um conjunto de
problemas com 5, 6, 7, 8, 12, 15, 20 e 30 instâncias que são notáveis devido à sua dificuldade.
Nestes problemas, a matriz de distâncias teve sua origem de uma grade n1 xn2 e as distâncias
são definidas como distâncias de Manhattan3 entre os pontos. As instâncias PQA resultantes
têm múltiplos ótimos locais, pelo menos quatro se n1 ≠ n 2 e oito se n1 = n 2 como mostrado
por Taillard (1995). Estas soluções globalmente ótimas estão na máxima distância possível de
outras soluções também ótimas. Estes conjuntos receberam a denominação de instâncias de
Nugent e serão tratadas aqui através do uso de um algoritmo simples para CFs.
Por se tratar de um algoritmo simples serão utilizados os problemas de Nugent para
PQA4, com 5, 6, 7 e 8 instâncias e, de agora em diante, serão chamados de Nug5, Nug6, Nug7
e Nug8, respectivamente.
3
Metodologia
A metodologia adotada consiste em realizar testes de desempenho em um algoritmo
simples de CFs aplicado aos problemas de Nugent.
3
A distância entre dois pontos medida ao longo dos eixos em ângulos diretos. Por exemplo: para os pontos n1 com
coordenadas (x1, y1) e n2 com (x2, y2), a distância é calculada por |x1 - x2| + |y1 - y2|.
http://www.nist.gov/dads/HTML/manhattanDistance.html.
4
http://www.seas.upenn.edu/qaplib/inst.html
Para isso, com a ajuda da ferramenta MATLAB e utilizando como base o código “Ant
Algorithm for the Quadratic Assignment Problem”, de Kyriakos Tsourapas da Universidade
de Essex em 20025, foram realizadas rodadas do algoritmo, alterando-se os parâmetros para
algumas das suas varáveis, a saber:
•
números de formigas => ants;
•
número máximo de alocações (quando parar) => max_assigns;
•
valor da solução ótima => optimal;
•
peso para o feromônio => a;
•
peso para a heurística => b;
•
taxa de evaporação do feromônio => lamda; e
•
taxa de atualização do feromônio => Q.
Como primeiro passo, utilizou-se o problema Nug8 por ser o maior de todos os
problemas e o que apresenta o maior grau de dificuldade devido ao maior número de
combinações possíveis. Outro fator levado em consideração é o de tentar encontrar qual
arranjo de parâmetros fornece o melhor resultado e com o menor número de passos para
alcançar o valor ótimo (condição de parada para o algoritmo) para o caso mais difícil, ou seja,
Nug8.
Para cada alteração dos parâmetros, realizou-se 5 rodadas do algoritmo e os resultados
foram armazenados para futura análise e comparação (ver item Resultados abaixo). Em
princípio, foi adotado como critério de parada (valor de solução ótima - optimal), o valor 107.
Depois de analisados os resultados para Nug8, encontrou-se valores de parâmetros,
considerados ótimos, que foram utilizados nos outros problemas de Nug5, Nug6 e Nug7,
cujos resultados também foram armazenados, para posterior análise.
Realizados os passos anteriores, fez-se a redução do valor de solução ótima para
valores menores que 107, dependendo do problema de Nugent utilizado, e novamente foi
aplicado o algoritmo e os resultados armazenados. A seguir podemos ver os resultados
encontrados com o algoritmo de CFs para PAQ, aplicados a Nug5, Nug6, Nug7 e Nug8,
assim como os valores dos parâmetros utilizados.
4
Resultados
As tabelas abaixo mostram quantas alocações foram necessárias para alcançar o custo
ótimo de parada, igual a 107 , e quais foram os valores de parâmetros usados em cada rodada.
Observe que o algoritmo encontrou duas distribuições possíveis para as facilidades,
distribuições que garantem o mesmo custo ótimo de parada e foram classificadas como:
Tabela 1 – Tipos de alocações para custo ótimo de parada igual a 107.
Alocação do tipo 1
1→2
2→1
3→5
4→3
5→4
6→8
7→7
8→6
5
Alocação do tipo 2
1→6
2→5
3→1
4→7
5→8
6→4
7→3
8→2
http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=1663&objectType=file
Tabela 2 – Resultados do algoritmo com os parâmetros a = 3, b = 5, lamda = 0,8 e Q = 10.
Alocações
Tipo
10710
tipo 1
Alocações
Tipo
36786
tipo 1
Alocações
Tipo
14819
tipo 2
Alocações
Tipo
1096
tipo 1
Alocações
Tipo
41580
tipo 1
Alocações
Tipo
20650
tipo 1
Alocações
Tipo
23460
tipo 1
Alocações
Tipo
5220
tipo 1
Alocações
Tipo
17900
tipo 1
Alocações
Tipo
81235
tipo 1
5 formigas
29490
2745
tipo 2
tipo 1
6 formigas
6216
15672
tipo 1
tipo 1
7 formigas
2562
392
tipo 1
tipo 1
8 formigas
41920
3792
tipo 1
tipo 1
9 formigas
12204
4059
tipo 1
tipo 1
10 formigas
17350
15730
tipo 1
tipo 1
15 formigas
70395
20295
tipo 1
tipo 1
20 formigas
76260
13060
tipo 1
tipo 1
25 formigas
8150
29400
tipo 1
tipo 1
35 formigas
350
31045
tipo 1
tipo 1
Média
14448
3105
tipo 2
26190
tipo 2
4290
tipo 1
16692
tipo 1
15931
17535
tipo 1
1897
tipo 1
7441
9480
tipo 2
1360
tipo 1
11530
68337
tipo 1
873
tipo 1
25411
240
tipo 1
15080
tipo 1
13810
6405
tipo 1
18690
tipo 2
27849
60320
tipo 1
1700
tipo 2
31312
9125
tipo 1
38375
tipo 1
20590
29715
tipo 1
15925
tipo 2
31654
Tabela 3 – Resultados do algoritmo com os parâmetros a = 1, b = 5, lamda = 0,8 e Q = 10.
Alocações
Tipo
320
tipo 2
Alocações
Tipo
13236
tipo 1
Alocações
Tipo
38423
tipo 1
Alocações
Tipo
4432
tipo 1
Alocações
Tipo
1872
tipo 1
5 formigas
9055
55985
tipo 1
tipo 1
6 formigas
39186
5622
tipo 1
tipo 1
7 formigas
52654
10192
tipo 1
tipo 1
8 formigas
17824
27728
tipo 1
tipo 1
9 formigas
49140
9864
tipo 1
tipo 1
Média
31539
70340
tipo 1
21995
tipo 1
4704
tipo 1
12750
tipo 1
15100
14546
tipo 1
25396
tipo 1
28242
44176
tipo 1
32336
tipo 1
25299
10017
tipo 1
8667
tipo 1
15912
Alocações
Tipo
8420
tipo 1
Alocações
Tipo
20685
tipo 1
Alocações
Tipo
18060
tipo 1
Alocações
Tipo
20100
tipo 1
Alocações
100030
Não
Alcançado
Tipo
10 formigas
60600
16260
tipo 1
tipo 1
15 formigas
46005
23430
tipo 1
tipo 1
20 formigas
16620
27500
tipo 1
tipo 1
25 formigas
98900
15700
tipo 1
tipo 1
35 formigas
39795
71750
tipo 1
tipo 1
15870
tipo 1
4260
tipo 1
21082
3165
tipo 1
51855
tipo 1
29028
49600
tipo 1
26480
tipo 1
27652
88800
tipo 1
59100
tipo 1
56520
100030
Não
Alcançado
79065
63537
tipo 1
Tabela 4 – Resultados do algoritmo com os parâmetros a = 5, b = 5, lamda = 0,8 e Q = 10.
Alocações
Tipo
22420
tipo 1
Alocações
Tipo
7902
tipo 1
Alocações
Tipo
32228
tipo 1
Alocações
Tipo
8336
tipo 1
Alocações
Tipo
1737
tipo 1
Alocações
Tipo
13560
tipo 1
Alocações
Tipo
7110
tipo 1
Alocações
12800
5 formigas
7740
655
tipo 1
tipo 1
6 formigas
16014
22104
tipo 1
tipo 1
7 formigas
7693
4802
tipo 1
tipo 1
8 formigas
6544
10784
tipo 2
tipo 1
9 formigas
23661
22851
tipo 2
tipo 1
10 formigas
13060
27230
tipo 1
tipo 1
15 formigas
54420
45705
tipo 1
tipo 1
20 formigas
1880
3400
Tipo
tipo 1
tipo 1
Alocações
Tipo
9950
tipo 1
25 formigas
7500
61075
tipo 1
tipo 1
tipo 1
Média
7749
6180
tipo 1
1750
tipo 1
11778
tipo 1
12972
tipo 1
14154
623
tipo 1
58247
tipo 1
20719
56640
tipo 2
50328
tipo 2
26526
10332
tipo 1
4698
tipo 1
12656
11260
tipo 1
5640
tipo 1
14150
19455
tipo 1
38820
tipo 1
33102
100000
Não
Alcançado
880
23792
8175
tipo 1
tipo 1
44875
tipo 1
26315
Alocações
Tipo
59570
tipo 1
35 formigas
79870
35980
tipo 1
tipo 1
7875
tipo 1
8645
tipo 2
38388
Tabela 5 – Resultados do algoritmo com os parâmetros a = 3, b = 3, lamda = 0,8 e Q = 10.
Alocações
Tipo
5620
tipo 1
Alocações
Tipo
150
tipo 1
Alocações
Tipo
14441
tipo 1
Alocações
Tipo
3344
tipo 1
Alocações
Tipo
20583
tipo 1
Alocações
Tipo
16870
tipo 1
Alocações
Tipo
3540
tipo 1
Alocações
Tipo
35560
tipo 1
Alocações
Tipo
10275
tipo 1
Alocações
Tipo
5915
tipo 1
5 formigas
3225
28720
tipo 1
tipo 1
6 formigas
8106
13104
tipo 1
tipo 1
7 formigas
6216
2212
tipo 1
tipo 1
8 formigas
25784
14528
tipo 1
tipo 1
9 formigas
16038
6408
tipo 1
tipo 1
10 formigas
20490
13520
tipo 1
tipo 1
15 formigas
11925
23430
tipo 1
tipo 1
20 formigas
11740
11500
tipo 1
tipo 1
25 formigas
98675
42475
tipo 1
tipo 2
35 formigas
11900
55895
tipo 1
tipo 1
Média
9374
8590
tipo 1
715
tipo 1
6012
tipo 1
18354
tipo 1
9145
11459
tipo 1
18011
tipo 1
10468
4600
tipo 1
16656
tipo 1
12982
8712
tipo 1
68184
tipo 1
23985
44990
tipo 1
18650
tipo 1
22904
14355
tipo 1
48555
tipo 1
20361
48160
tipo 1
40300
tipo 1
29452
47850
tipo 1
12925
tipo 1
42440
18515
tipo 1
3990
tipo 1
19243
Tabela 6 – Resultados do algoritmo com os parâmetros a = 3, b = 8, lamda = 0,8 e Q = 10.
Alocações
Tipo
14640
tipo 1
Alocações
Tipo
7722
tipo 1
Alocações
Tipo
2016
tipo 1
5 formigas
18445
6955
tipo 1
tipo 1
6 formigas
24810
67368
tipo 1
tipo 1
7 formigas
59409
609
tipo 2
tipo 1
Média
13475
14370
tipo 1
12965
tipo 1
4482
tipo 1
3408
tipo 1
21558
8841
tipo 1
41125
tipo 2
22400
Alocações
Tipo
33064
tipo 1
Alocações
Tipo
40122
tipo 1
Alocações
Tipo
15460
tipo 1
Alocações
Tipo
26145
tipo 1
Alocações
Tipo
75400
tipo 1
Alocações
Tipo
58225
tipo 1
Alocações
Tipo
13650
tipo 1
8 formigas
11056
14544
tipo 1
tipo 1
9 formigas
28773
12186
tipo 1
tipo 1
10 formigas
25800
12180
tipo 1
tipo 1
15 formigas
9540
77940
tipo 1
tipo 1
20 formigas
17540
4400
tipo 1
tipo 1
25 formigas
50150
22600
tipo 1
tipo 1
35 formigas
10885
28490
tipo 1
tipo 1
19520
tipo 1
10104
tipo 1
17658
11628
tipo 1
40995
tipo 1
26741
62350
tipo 1
11240
tipo 1
25406
12945
tipo 1
13935
tipo 1
28101
60340
tipo 1
76040
tipo 1
46744
2575
tipo 1
11975
tipo 1
29105
665
tipo 1
15540
tipo 1
13846
Tabela 7 – Resultados do algoritmo com os parâmetros a = 3, b = 5, lamda = 0,3 e Q = 10.
Alocações
Tipo
6080
tipo 1
Alocações
Tipo
28284
tipo 2
Alocações
Tipo
1442
tipo 1
Alocações
Tipo
13152
tipo 1
Alocações
Tipo
1404
tipo 1
Alocações
Tipo
22140
tipo 2
Alocações
Tipo
18495
tipo 1
Alocações
Tipo
10260
tipo 1
5 formigas
5535
3595
tipo 1
tipo 1
6 formigas
13506
3324
tipo 1
tipo 1
7 formigas
2639
8694
tipo 1
tipo 2
8 formigas
952
5072
tipo 1
tipo 1
9 formigas
1350
9018
tipo 2
tipo 1
10 formigas
3670
5840
tipo 1
tipo 2
15 formigas
14355
16635
tipo 2
tipo 1
20 formigas
1620
7260
tipo 1
tipo 1
Média
7688
7420
tipo 2
15810
tipo 1
10998
tipo 1
4434
tipo 1
12109
15764
tipo 2
10304
tipo 1
7769
8200
tipo 1
4536
tipo 1
6382
17937
tipo 2
5040
tipo 1
6950
1720
tipo 1
1610
tipo 1
6996
6705
tipo 1
3420
tipo 1
11922
1500
tipo 1
2620
tipo 1
4652
Alocações
Tipo
450
tipo 1
Alocações
Tipo
3745
tipo 1
25 formigas
1950
475
tipo 1
tipo 2
35 formigas
20090
13440
tipo 1
tipo 1
2300
tipo 1
11425
tipo 1
3320
19355
tipo 1
3745
tipo 1
12075
Tabela 8 – Resultados do algoritmo com os parâmetros a = 3, b = 5, lamda = 1,0 e Q = 10.
Alocações
Tipo
Alocações
Tipo
Alocações
Tipo
5 formigas
4265
64795
100000
100000
100000
Não
Não
Não
tipo 1
tipo 1
Alcançado Alcançado Alcançado
6 formigas
100002
100002
Não
Não
Alcançado Alcançado
35 formigas
22365
100030
100030
46550
100030
Não
Não
Não
tipo 1
tipo 1
Alcançado Alcançado
Alcançado
Média
73812
40001
73801
Tabela 9 – Resultados do algoritmo com os parâmetros a = 3, b = 5, lamda = 0,3 e Q = 5.
Alocações
Tipo
2650
tipo 1
25 formigas
4625
1325
Tipo 1
tipo 1
2950
tipo 1
2050
tipo 1
Média
2720
Tabela 10 – Resultados do algoritmo com os parâmetros a = 3, b = 5, lamda = 0,3 e Q = 5.
Alocações
Tipo
100
tipo 1
25 formigas
825
4675
Tipo 1
tipo 1
6300
tipo 2
750
tipo 1
Média
2530
Pela análise dos resultados obtidos, observa-se que executando o algoritmo com os
parâmetros ajustados para os valores mostrados na Tabela 11 abaixo, a convergência para o
custo ótimo de parada, igual a 107, ocorreu de forma mais rápida e com menos alocações.
Tabela 11 – Parâmetros ótimos para o algoritmo de CFs usando Nug8.
Números de formigas (ants)
Número máximo de alocações (max_assigns)
Valor da solução ótima (optimal)
Peso para o feromônio (a)
Peso para a heurística (b)
Taxa de evaporação do feromônio (lamda)
Taxa de atualização do feromônio (Q)
25
100000
107
3
5
0,3
15
Na Tabela 10, pode-se ver os resultados obtidos com os parâmetros ajustados
conforme os valores ótimos da Tabela 11. Por ser um algoritmo que utiliza metaheurística, a
convergência não acontece com um número de alocações para um valor fixo, mas sim
variando de acordo com a evolução das buscas realizadas pelas “formigas cibernéticas”.
Também se observou que existem tabelas onde não foi alcançada a convergência após
100.000 alocações. Este fato ocorreu por dois motivos:
•
o uso de parâmetros indevidos, ou não ótimos, de configuração; e
•
escolhas ruins na busca do melhor caminho, pelas formigas.
Desta forma, mantendo os valores de parâmetros ótimos, Tabela 11, fizeram-se
rodadas do algoritmo usando os problemas Nug5, Nug6 e Nug7. Os resultados obtidos estão
mostrados nas tabelas abaixo:
Tabela 12 – Resultados do algoritmo para Nug5.
Custo
Alocações
40
25
25 formigas
40
40
25
25
40
25
40
25
Média
40
25
62
25
Média
62
25
98
25
Média
98
25
Tabela 13 – Resultados do algoritmo para Nug6.
Custo
Alocações
62
25
25 formigas
62
62
25
25
62
25
Tabela 14 – Resultados do algoritmo para Nug7.
Custo
Alocações
98
25
25 formigas
98
98
25
25
98
25
Observe que, para um número de instâncias menor, a convergência se dá para um
número de alocações padrão, no caso 25. Porém o valor do custo ótimo de parada para estes
problemas é grande, considerando-se que o número de instâncias e de combinações possíveis
é menor, comparados aos do problema Nug8.
Desta forma, alterou-se o valor ótimo de parada, conforme cada problema e
obtiveram-se os seguintes resultados:
Tabela 15 – Resultados do algoritmo para Nug5 e custo ótimo igual a 30.
Alocações
125
25 formigas
112
100
75
80
Média
98
Tabela 16 – Resultados do algoritmo para Nug5 e custo ótimo igual a 43.
Alocações
150
25 formigas
200
100
250
100
Média
160
Tabela 17 – Resultados do algoritmo para Nug5 e custo ótimo igual a 77.
Alocações
800
25 formigas
500
300
225
625
Média
490
As tabelas 15, 16 e 17, mostram que os valores do número de alocações, aumentaram
com relação aos das tabelas 12, 13 e 14. Isto ocorreu devido ao fato do algoritmo continuar a
busca, na tentativa de encontrar uma solução de menor custo, analisando mais caminhos e
consequentemente aumentando o número de alocações necessárias até atingir a(s)
condição(ões) de parada.
5
Conclusão
Unidades simples, como no caso das formigas, geram um comportamento global
complexo e, como vimos, através dos resultados obtidos, provou-se que a aplicação da
metaheurística de CFs garante bons resultados, principalmente levando em consideração que
se utilizou um algoritmo de CFs simples, sem qualquer mecanismo de otimização.
Pode-se melhorar este desempenho, bastando para isso prover alguns aprimoramentos,
por exemplo: através de ajustes ótimos dos parâmetros de configuração. O uso de outras
heurísticas em conjunto com a CFs, pode melhorar ainda mais a busca realizada pelas
formigas.
Uma boa oportunidade para trabalhos futuros é a implementação deste algoritmo,
promovendo algumas alterações e/ou melhorias no seu código, por exemplo: implementando
a busca local 2-opt que Lin-Kerninghan (1973) aplicou ao problema do caixeiro viajante.
Também convém apontar como uma adição interessante ao algoritmo, a
implementação de um procedimento para a determinação dos parâmetros ótimos, como o
tamanho da população, número de iterações, ponderação do feromônio (a), ponderação da
informação heurística (b) e a constante de projeto (Q).
Referências Bibliograficas
[ALG1999]
[ALL1990]
[ARM1963]
[BAZ1983]
[BRI2001]
[BUR1978]
[CIN1975]
[DEI1972]
[DOR1996]
[DRE1980]
El-Ghazali T., Olivier R., Cyril F., Denis R. (1999), Parallel Ant Colonies for
Combinatorial Optimization Problems, IPPS/SPDP Workshops – Lecture
Notes In Computer Science; Vol. 1586, London, England.
Allenbach, R., Werner, M. (1990), Facility layout program, Computers &
Industrial Engineering, Vol 19, N°. 1-4, pgs. 290-293.
Armour, Buffa (1963), A heuristic algorithm and simulation approach to
relative algoritms.
Bazaraa, Kirca (1983), A Branch-and-Bound-Based Heuristic for Solving the
Quadratic.
N. W. Brixius, K. M. Anstreicher (2001), The Steinberg Wiring Problem, Iowa
City, Iowa.
Burkard, R.E., Stratman, K.H. (1978), Numerical investigations on quadratic
assignment problems.
Cinar U (1975), Facilities planning: a systems analysis and space allocation,
in Spatial Synthesis in Computer-Aided Building Design Eastman CM (ed),
Applied Science Publishers Ltd, London.
Deisenroth, M.P., Apple, J.M. (1972), A computerized plant layout analysis
and evaluation technique (PLANET), Technical Papers, N°. 1962, American
Institute of Industrial Engineers, Norcross, GA.
Dorigo, Maniezzo, Colorni (1996), The Ant System: Optimization by a colony
of cooperating.
Drezner, Z. (1980), DISCON: A new method for the layout problem,
Operations Research. Vol. 25, N°. 6, pgs. 1375-1384.
[ELI2003]
[ELI2004]
[FOU1976]
[FOU1978]
[FUR1997]
[HER1986]
[HIC1976]
[HIL1963]
[HIL1966]
[HIT1976]
[HOU1997]
[HUB1976]
[JAC1984]
[JON1982]
[KHA1973]
[KOO1957]
[LEE1967]
[LIN1973]
[LOR2001]
[LUC1999]
Elizabeth M. K. A. P., Ester M. K., Luiz C. F. J. (2003), A Metaheurística
Colônia de Formigas – Ant Colony, Scientia – Revista do Centro Universitário
Vila Velha, Vila Velha (ES), Vol. 4, N° 1-2.
Eliana M. L., Nair M. M. A., Paulo O. B. N. (2004), Uma Revisão comentada
do Problema Quadrático de Alocação, Coppe, Rio de Janeiro.
Foulds, Robinson (1976), A strategy for solving the plant layout problem.
Foulds, L. R. and Robinson, R. W. (1978), Graph Theoretic Heuristics for the
Plant Layout Problem.
Furtado, J. C., Lorena, L.A.N. (1997), Otimização de Leiaute usando Busca
Tabu.
Heragu, S. S. e Kuslak, A. (1986), Machine layout problem in flexible
manufacturing systems, Working paper 08/86, Department of Mechanical and
Industrial Engineering, University of Manitoba, Winnipeg, Manitoba, Canadá.
Hicks, P.E., e Cowan, T.E. (1976), CRAFT-M for layout rearrangement,
Industrial Engineering.
Hillier, F.S. (1963), Quantitative tools for plant layout analysis, Journal of
Industrial Engineering, Vol. 14, pgs. 33-40.
Hiller, M.R., e Connors, M.M. (1966), Quadratic assignment problem
algorithm and the location of indivisible facilities, Management Science, Vol.
13, N°. 1, pgs. 42-57.
Hitchings, G.G., e Cottam, M. (1976), An efficient heuristic procedure for
solving the layout design problem, Omega, Vol. 4, No. 2, pgs. 205-214.
Houshyar, A., White, B. (1997), Comparison of solution procedures to the
facility location problem, Computers & Insdustrial Engineering, Vol. 32, N°.
1, pgs. 77-87.
Hubert, L.J., Schulz, J. (1976), Quadratic assignment as a general data
analysis strategy, British Journal of Mathematical and Statistical Psychology,
29: pgs. 190-24.
Jacobs, R.F. (1984), A note on SPACECRAFT for multifloor layout planning,
Management Science. Vol. 30, N°. 5, pgs. 648-649.
Jonhson, R.V. (1982), SPACECRAFT for multi-floor layout planning,
Management Science. Vol. 28, N°. 4, pgs. 407-417.
Khalil, T.M. (1973), Facilities relative allocation technique (FRAT),
International Journal of Productions Research. Vol. 12, N°. 2, pgs. 183-194.
Koopmans, T. C., Beckmann, M. J. (1957), Assignment Problems and the
Location of Economic Activities.
Lee, R. C.; Moore, J. M. (1967), CORELAP – computerized relationship
layout planning. Industrial Engineering, Vol. 18, pgs. 195-200.
Lin, s., Kernighan, B. W. (1973), An Effective Heuristic Algorithm for the
Traveling-Salesman Problem, Oper. Res. 21, pgs. 498-516.
Lorenzoni , L. L., Ahonen, H. T., Alvarenga, A. G. de A. (2001), Colônia de
Formigas para o Problema de Escalonamento com Restrição de Recursos,
Anais do XXXIII Simpósio Brasileiro de Pesquisa Operacional, Campos do
Jordão/SP.
Gambardella L. M., E. Taillard e M. Dorigo (1999). Ant Colonies for the
Quadratic Assignment Problem, Journal of the Operational Research Society,
N°. 50, pgs.167-176, Lugano, Switzerland.
[MUR1970]
[NEG1974]
[OBR1980]
[PIC1984]
[SAH1976]
[SCR1985]
[SEE1967]
[SEP1970]
[SHO1980]
[SVE1990]
[TAM1991]
[TAM1992]
[TOM1976]
[VAL2002]
[ZIA1991]
[ZOL1972]
Murther, R., McPherson, K. (1970), Four approaches to computerized layout
planning, Industrial Engineering, February, pgs. 39-42.
Neghabat, F. (1974), An efficient equipment layout algorithm, Operations
Research. Vol. 22, pgs. 622-628.
O’Brien, C., Abdel Barr, S.E.Z. (1980), An interactive approach to computer
aided facility layout, International Journal of Production Research, Vol. 18,
N°. 2, pgs. 201-211.
Picone, C.J., e Wilhelm, W.E. (1984), Perturbation scheme to improve Hiller’s
solution to the facilities layout problem, Management Science. Vol. 30, N°. 10,
pgs. 1238-1249.
Sahni, S.; Gonzalez, T. (1976); P-complete approximation problem, Journal of
Associated Computing Machinery, Vol. 23, N°. 3, pgs. 555-565.
Scriabin, M., e Vergin, R.C. (1985), A cluster-analytic approach to facility
layout, Management Science. Vol. 31, N°. 1, pgs. 33-49.
Seehof, J.M., Evans, W.O. (1967), Automated layout design program, Journal
of Industrial Engineering, Vol. 18 N°.12, pgs. 690-695.
Seppanen, Moore (1970), Facilities planning with graph theory.
Shore, R.H., Tompkins, J. A . (1980), Flexible facilities design, AIIE
Transactions. Vol. 12, N°. 2, pgs. 200-205.
Svestka, J. A. (1990), MOCRAFT: a professional quality microcomputer
implementation of CRAFT with multiple objectives, Copmputers & Industrial
Engineering. Vol. 18, N°. 1, pgs. 13-22.
Tam, Li (1991), A hierarchical approach to the facility layout problem.
Tam, Kar, Yan, (1992), Genetic Algorithms, Function Optimization, and
Facility Layout Design, European Journal of Operational Research, N°. 63,
pgs. 322-346.
Tompkins, J.A ., Reed, R. Jr. (1976), An applied model for the facilities design
problem, International Journal of Productions Research. Vol. 14, N°. 5, pgs.
583-595.
Valdair C. M. (2002), Otimização de layout em Ambientes Industriais
Realistas Usando Busca Tabu, Dissertação apresentada ao Programa de PósGraduação em Informática Aplicada da Pontifícia Universidade Católica do
Paraná como requisito parcial para obtenção do título de Mestre em
Informática Aplicada, PUC-Pr, Curitiba.
Ziai, Sule (1991), Computerized facility layout design.
Zoller, K. e Adendorff, K. (1972), Layout planning by computer simulation,
AIIE, Transactions, N°. 4(2), pgs. 116-125.