UNIVERSIDADE DO VALE DO ITAJAÍ
CENTRO DE CIÊNCIAS TECNOLÓGICAS DA TERRA E DO MAR
CURSO DE CIÊNCIA DA COMPUTAÇÃO
ESTUDO COMPARATIVO DE METAHEURÍSTICAS APLICADAS AO
PROBLEMA DAS P-MEDIANAS
Pesquisa Operacional
por
Diego Fernando Ribeiro
Edson Tadeu Bez, Dr.
Orientador
São José (SC), dezembro de 2007
UNIVERSIDADE DO VALE DO ITAJAÍ
CENTRO DE CIÊNCIAS TECNOLÓGICAS DA TERRA E DO MAR
CURSO DE CIÊNCIA DA COMPUTAÇÃO
ESTUDO COMPARATIVO DE METAHEURÍSTICAS APLICADAS AO
PROBLEMA DAS P-MEDIANAS
Pesquisa Operacional
por
Diego Fernando Ribeiro
Relatório apresentado à Banca Examinadora do
Trabalho de Conclusão do Curso de Ciência da
Computação para análise e aprovação.
Orientador: Edson Tadeu Bez, Dr.
São José (SC), dezembro de 2007
DEDICATÓRIA
Aos meus pais Antonio Luiz
Ribeiro e Ildegard Angrevski Ribeiro
com amor.
AGRADECIMENTOS
Agradeço a todos que, direta ou indiretamente, colaboraram para a realização deste
trabalho. Em especial:
•
Ao professor Edson Tadeu Bez pelo incentivo, pela orientação constante, dedicação,
amizade e paciência.
•
A professora Anita Maria da Rocha Fernandes pela inestimável colaboração.
•
Aos professores e funcionários da Univali, por todo apoio e estímulo.
•
Aos meus pais que sempre me incentivaram, e por sempre acreditarem na importância do
estudo.
•
Agradeço a Deus, cujas bênçãos possibilitaram a realização deste trabalho.
iii
SUMÁRIO
LISTA DE ABREVIATURAS..................................................................vi
LISTA DE FIGURAS...............................................................................vii
LISTA DE TABELAS .............................................................................viii
LISTA DE EQUAÇÕES ...........................................................................ix
RESUMO..................................................................................................... x
ABSTRACT................................................................................................xi
1 INTRODUÇÃO ...................................................................................... 1
1.1 PROBLEMATIZAÇÃO ..................................................................................... 2
1.1.1 Formulação do Problema ................................................................................. 2
1.1.2 Solução Proposta ............................................................................................... 3
1.2 OBJETIVOS ........................................................................................................ 3
1.2.1 Objetivo Geral ................................................................................................... 3
1.2.2 Objetivos Específicos ........................................................................................ 3
1.3 METODOLOGIA................................................................................................ 4
1.4 ESTRUTURA DO TRABALHO ....................................................................... 5
2 FUNDAMENTAÇÃO TEÓRICA ........................................................ 6
2.1 MODELOS PARA LOCALIZAÇÃO DE FACILIDADES............................ 6
2.1.1 Introdução.......................................................................................................... 6
2.1.2 Definição do problema de p-medianas............................................................ 9
2.2 MÉTODOS EXATOS E ESTOCÁTICOS PARA LOCALIZAÇÃO DE
FACILIDADES ......................................................................................................... 13
2.2.1 Introdução........................................................................................................ 13
2.2.2 Algoritmo de Teitz e Bart............................................................................... 13
2.2.3 Algoritmo Simulated Annealing...................................................................... 14
2.2.4 Algoritmo Genético......................................................................................... 18
2.2.5 Algoritmo Busca Tabu.................................................................................... 26
2.2.6 Algoritmo baseado em colônia de formigas.................................................. 28
3 DESENVOLVIMENTO ...................................................................... 33
3.1 PLANEJAMENTO............................................................................................ 33
3.1.1 Metodologia ..................................................................................................... 33
3.1.2 Problema utilizado nos testes......................................................................... 33
3.1.3 Modelagem dos algoritmos............................................................................. 34
3.2 ENSAIOS NUMÉRICOS.................................................................................. 39
3.2.1 Ensaios realizados com o algoritmo genético ............................................... 40
3.2.2 Ensaios realizados com o algoritmo simulated annealing........................... 44
3.2.3 Ensaios realizados com o algoritmo baseado em colônia de formigas....... 46
3.2.4 Comparativo de resultados ............................................................................ 49
iv
4 CONCLUSÕES .................................................................................... 51
4.1 TRABALHOS FUTUROS................................................................................ 52
REFERÊNCIAS BIBLIOGRÁFICAS ................................................... 53
GLOSSÁRIO............................................................................................. 56
A ENSAIOS NUMÉRICOS .................................................................... 58
A.1.1. Ensaios algoritmo genético............................................................................. 58
A.1.2. Ensaios algoritmo baseado em colônia de formigas .................................... 59
A.1.3. Ensaios Simulated Annealing ......................................................................... 61
v
LISTA DE ABREVIATURAS
GRASP
PLMC
PPMC
SIG
TCC
UNIVALI
Greedy Randomized Search Procedure
Problema de máxima cobertura
Problema das p-medianas capacitado
Sistema de informações geográficas
Trabalho de Conclusão de Curso
Universidade do Vale do Itajaí
LISTA DE FIGURAS
Figura 1. Localização de 3 medianas – capacitado - distâncias euclidianas ........................................7
Figura 2. Localização de 3 medianas – não capacitado – distâncias euclidianas.................................8
Figura 3.Algoritmo de Teitz e Bart ....................................................................................................14
Figura 4. Estado desordenado das moléculas da matéria em fusão. ..................................................15
Figura 5. Estado desordenado das moléculas consecutivo a um resfriamento...................................15
Figura 6. Estado ordenado das moléculas consecutivo a um resfriamento lento...............................16
Figura 7. Algoritmo de Metrópolis ....................................................................................................17
Figura 8. Estrutura do algoritmo Genético.........................................................................................20
Figura 9. Roleta de seleção ................................................................................................................22
Figura 10. Procedimentos de cruzamento com troca de genes randômica.........................................23
Figura 11. Exemplo de cruzamento com 1 ponto de corte.................................................................23
Figura 12. Exemplo de cruzamento com 2 pontos de corte. ..............................................................23
Figura 13. Exemplo de cruzamento com 2 pontos de corte. ..............................................................24
Figura 14. Mutação por troca simples. ...............................................................................................25
Figura 15. Processo de reprodução ....................................................................................................25
Figura 16. Algoritmo Busca Tabu......................................................................................................27
Figura 17. Diferentes caminhos escolhidos pelas formigas, durante um determinado intervalo de
tempo..........................................................................................................................................29
Figura 18. Pseudocódigo da colônia de formigas. .............................................................................30
Figura 19. Código principal algoritmo genético. ...............................................................................36
Figura 20. Código principal Simulated Annealing. ............................................................................37
Figura 21. Código principal algoritmo baseado em colônia de formigas. .........................................39
Figura 22 Ajuste da taxa de cruzamento. ...........................................................................................41
Figura 23 Ajuste da taxa de mutação. ................................................................................................42
Figura 24. Ajuste da quantidade de gerações. ....................................................................................42
Figura 25. Ajuste do tamanho da população. .....................................................................................43
Figura 26. Convergência do algoritmo genético. ...............................................................................43
Figura 27. Ajuste da temperatura inicial ............................................................................................44
Figura 28 Ajuste do decréscimo de temperatura. ...............................................................................45
Figura 29. Ajuste do número de iterações simulated annealing. .......................................................45
Figura 30. Convergência do algoritmo simulated annealing. ............................................................46
Figura 31. Ajuste da quantidade de formigas.....................................................................................47
Figura 32. Ajuste da evaporação de ferômonio..................................................................................47
Figura 33. Ajuste da quantidade de iterações.....................................................................................48
Figura 34. Convergência do algoritmo baseado em colônia de formigas. .........................................48
Figura 35 Comparativo da média e desvio padrão entre os testes. ....................................................49
Figura 36. Comparação em relação aos melhores resultados.............................................................50
LISTA DE TABELAS
Tabela 1. Ensaios algoritmo genético ................................................................................................58
Tabela 2. Ensaios algoritmo baseado em colônia de formigas ..........................................................59
Tabela 3. Ensaios Simulated Annealing .............................................................................................61
viii
LISTA DE EQUAÇÕES
Equação 1 ...........................................................................................................................................10
Equação 2 ...........................................................................................................................................10
Equação 3 ...........................................................................................................................................10
Equação 4 ...........................................................................................................................................10
Equação 5 ...........................................................................................................................................31
Equação 6 ...........................................................................................................................................31
RESUMO
RIBEIRO, Diego Fernando. Metaheurísticas aplicadas ao problema das p-medianas. São José,
2007. 53f. Trabalho de Conclusão de Curso (Graduação em Ciência da Computação)–Centro de
Ciências Tecnológicas da Terra e do Mar, Universidade do Vale do Itajaí, São José, 2007.
O estudo de métodos capazes de resolver problemas considerados de difícil solução tem tido
atenção especial nas últimas décadas. O motivo é que este tipo de problema geralmente está contido
em nosso dia a dia, estando presente em vários setores tais como: transportes, logística, localização
de facilidades, escalonamento de recursos, minimização de desperdiço de matéria-prima entre
outros. As metaheurísticas ou heurísticas modernas são métodos flexíveis que foram ainda pouco
explorados até o momento e têm demonstrado bons resultados aplicados a problemas
combinatórios. Estes métodos podem ser adaptados a diversos tipos de problemas. O que se busca
no momento é torná-los mais robustos com, a finalidade de escapar de mínimos locais. Novas
metaheurísticas tem surgido, buscando tomar proveito das características positivas de cada método,
possibilitando assim um melhor desempenho em relação aos métodos anteriores. O presente estudo
busca avaliar e identificar as melhores soluções para a resolução de problemas de p-medianas, que é
um tipo de problema de localização o qual busca distribuir da melhor forma possível facilidades em
uma determinada área. O trabalho apresentado mostra alguns algoritmos, apresentando a estrutura
de cada um. Para a avaliação e quantificação da melhor solução serão apresentados testes
computacionais a fim de demonstrar as vantagens e desvantagens de cada algoritmo. As
metaheurísticas abordadas neste trabalho foram: Simulated Annealing; algoritmos Genéticos, e
algoritmos baseados em colônia de formigas.
Os resultados obtidos mostram que o algoritmo genético é o melhor apropriado para a resolução do
problema escolhido para o testes sendo que o mesmo demonstra grande vantagem em relação ao
algoritmo Simulated Annealing e o algoritmo baseado em colônia de formigas. Em seguida o
algoritmo de formigas se mostrou superior ao Simulated Annealing convergindo para uma solução
melhor de forma mais rápida.
Palavras-chave: Problemas de localização. Problema de p-medianas, Metaheurísticas.
ABSTRACT
The study of methods adept to solve strenuous solution problems has had special attention in the
last decades. The reason is that this type of problem is in our day to day basis in different sectors
such as: transportation, logistics, facility localization, scheduling of resources, minimization of raw
material waste and others. The modern metaheurístics and heuristics are flexible methods that have
been little explored and have shown positive results when applied to combined results. These
methods can been adapted to a variety of problems. The objective now is to make these methods
more robust and able to escape from the smallest places. New metaheuristics have appeared taking
advantage of the positive characteristics from each method, allowing then a better progress in
relation to the previous methods. The current project tries to evaluate and identify superior
solutions to solve p-medium problems, which is a type of localization problem that intends to find
the best way to distribute facilities in a particular area. The project shown, presents some
algorithms, presenting the structure of each one. In order to evaluate and classify the best solution,
it will be presented computerized tests that will demonstrate the advantages and disadvantages of
each algorithm. The metaheuristics approached in this project were: Simulated Annealing, Genetics
Algorithms and Algorithms based on Ant’s Colonies.
The results show that genetic algorithm is best suited to the resolution of the issue chosen for the
tests is that it shows great advantage in relation to the algorithm Simulated Annealing and
algorithm based on on Ant’s Colonies. The algorithm of ants are shown above the Simulated
Annealing converging towards a better solution more quickly.
Keywords: Localization problems. P-median Problems. Metaheurístics.
1 INTRODUÇÃO
As mudanças ocorridas na revolução industrial, em meados do século XVIII, na Inglaterra,
onde a substituição das ferramentas pelas máquinas, a mão de obra humana pelo trabalho de
máquinas, e o modo de produção que passou a ser um processo automatizado, refletiram de forma
significativa sobre a sociedade (HOBSBAWM, 1982). Observou-se a necessidade de aperfeiçoar
sua maneira de produção e localização de suas facilidades.
Com a manufatura, houve a ampliação do consumo, fato que levou o produtor a aumentar
sua produção. A matéria prima era distribuída aos artesãos que trabalhavam em casa. Como o custo
de operação deste sistema tornava-se alto devido ao custo de transporte e logística na distribuição e
coleta dos produtos, surgiram fábricas com trabalhadores assalariados, com o objetivo de centralizar
a produção. Com esta medida obteve-se o aumento da produtividade, pois cada trabalhador
realizava uma etapa da produção e tornava-se especialista em sua tarefa.
Observou-se que cada fábrica poderia suprir uma demanda limitada, e que a localização
desta fábrica deveria atender a todos os pontos de demanda da melhor maneira, respeitando sua
capacidade.
Da mesma forma para a implantação de uma fábrica em determinada localidade, tornou-se
necessário alguns critérios de localização industrial, tais como, disponibilidade de mão de obra
barata e de matéria prima de qualidade com baixo custo operacional. Respeitando estes ítens, os
custos operacionais da fábrica seriam reduzidos e os riscos do negócio seriam minimizados
possibilitando a fábrica maior competitividade, pois a redução de custos refletiria no produto final e
na sua aceitação no mercado.
Desde então iniciou a busca de locais adequados para servirem de postos de fabricação e
distribuição, buscando um melhor agrupamento dos pontos de demanda atendidos pelas unidades de
produção e distribuição.
Tais problemas podem ser observados no dia a dia, por exemplo: a escolha adequada da
localização de torres de transmissão de sinais de telecomunicação, as quais devem atender a um
número máximo e determinado de usuários, e possibilitar a cobertura de sinal a uma região
específica; a distribuição de produtos perecíveis, os quais devem ser entregues ao consumidor em,
tempo hábil levando em conta os custos operacionais; a localização de unidades de saúde de forma
a atender um número específico de usuários e que a localização seja a melhor possível de acordo
com a população da região a ser atendida; a localização de cooperativas rurais de coleta de leite,
grãos entre outros para que seja possível atender aos produtores de forma eficaz e viável.
Estes problemas são importantes de serem solucionados por serem amplamente encontrados
em diversos sistemas de produção e serviços e terem impacto decisivo na tomada de decisões em
vários setores da economia.
As aplicações de localização, em geral, são divididas para os setores público e privado. No
caso do setor público, as aplicações procuram maximizar a satisfação dos clientes. São
exemplos de aplicações para o setor público, a localização de escolas, postos de saúde,
corpo de bombeiros, centrais de ambulâncias, viaturas de polícia, pontos de ônibus, entre
outros. No caso do setor privado, as aplicações envolvem, em geral, fábricas, depósitos,
torres de Transmissão, lojas de franquias, dentre outras.” Lorena et al., (2002)
Segundo Smiderle, Piva e Tibes (2005), problemas de localização são tratados na literatura
como problemas de p-medianas.
“O problema de p-medianas consiste em localizar p instalações em um espaço considerado
(espaço euclidiano, por exemplo) que devem atender a n pontos de demanda de tal forma que a
soma das distâncias percorridas de cada ponto de demanda até a instalação mais próxima seja
minimizada” (CORRÊA, 2000).
1.1 PROBLEMATIZAÇÃO
1.1.1 Formulação do Problema
Problemas de localização de facilidades pertencem a uma classe de problemas que se
preocupam em estabelecer os locais onde serão sediadas as facilidades (fábricas, centros de saúde,
escolas, etc.). Dependendo da extensão do problema, a solução ideal tem um custo computacional
inviável, pois se caracteriza como um problema combinatório o qual para que se determine a
solução exata, faz-se necessário testar todas as possibilidades. De acordo com Garey e Johnson
(1979), estes problemas são do tipo NP-Hard, ou seja, o tempo para se conseguir uma solução ótima
cresce exponencialmente à medida que aumentam os dados de entrada.
2
1.1.2 Solução Proposta
As metaheurísticas utilizadas neste trabalho são técnicas utilizadas para encontrar uma boa
solução, eventualmente a ótima. Partem de uma solução inicial, têm critérios de parada, e são de uso
geral, podendo ser modeladas de acordo com o problema a ser resolvido, obtendo assim um melhor
desempenho de cada técnica.
Corrêa (2000), salienta que uma heurística conhecida para este tipo de problema é o
algoritmo de Teitz e Bart (1968), o qual é fácil de ser implementado, porém apresenta resultados
aceitáveis apenas quando aplicados a problemas pequenos. Pode-se citar também a Busca tabu
(GLOVER, 1986), e Colônia de Formigas (DORIGO, MANIEZZO & COLORNI, 1991).
Nesta mesma linha, propõe-se, neste trabalho, o estudo do comportamento computacional
destas abordagens, realizando testes comparativos entre os métodos aplicando-o a um problema de
localização.
1.2 OBJETIVOS
1.2.1 Objetivo Geral
Realizar uma análise das metaheurísticas algoritmos genéticos, simulated annealing e
colônia de formigas aplicadas em um problema de localização utilizando p-medianas, levando em
consideração a qualidade da solução (soma das distâncias) e o tempo de processamento.
1.2.2 Objetivos Específicos
Os objetivos específicos deste projeto de pesquisa são:
•
Analisar trabalhos que utilizam os problemas clássicos de p-medianas;
•
Definir o problema a ser utilizado no estudo;
•
Estudar os algoritmos mais utilizados na resolução de problemas de p-medianas;
•
Modelar os algoritmos para resolução do problema escolhido;
•
Implementar computacionalmente os algoritmos; e
•
Realizar os ensaios numéricos.
3
•
Analisar os resultados obtidos; e
•
Documentar os resultados obtidos.
1.3 Metodologia
Para a escolha do problema a ser tratado, foi levado em consideração o tamanho do
problema, para que os testes a serem realizados possam realmente mostrar a diferença entre os
algoritmos escolhidos, pois se os testes forem realizados em problemas pequenos talvez não exista
diferença significativa entre as metaheurísticas.
A seleção dos algoritmos foi feita levando em consideração os mais utilizados para a
resolução de problemas de localização, exceto o algoritmo de formigas que não se tem muitas
aplicações a p-medianas, mas percebeu-se que o mesmo pode ser adaptado para o contexto do
problema.
A modelagem dos algoritmos selecionados foi realizada adaptando cada um, escolhido, de
forma que os mesmos não fossem alterados, e o problema pudesse ser resolvido usando os conceitos
do algoritmo. Foi definido como cada operador será usado para a resolução do problema.
A implementação dos algoritmos foi realizada na segunda parte deste trabalho definida
como TCC II, nesta parte do trabalho foram implementados os algoritmos modelados na etapa
anterior. Foi utilizada para a programação dos algoritmos a linguagem C++, sendo que o objetivo
não é a construção de um software e sim a comparação dos resultados obtidos com os experimentos
realizados.
Os ensaios numéricos foram realizados com os algoritmos já implementados, e todos os
resultados obtidos serão armazenados para a análise comparativa dos resultados, esta etapa foi de
grande importância, pois o resultado de todo o trabalho foram observados nesta etapa.
A documentação dos resultados obtidos será realizada levando em consideração todos os
testes realizados mostrando os resultados encontrados e comparando as soluções encontradas por
cada método..
4
1.4 Estrutura do trabalho
Este documento está estruturado em quatro capítulos. O Capítulo 1, Introdução, apresentou
uma visão geral do trabalho. No Capítulo 2, Fundamentação Teórica, é apresentada uma revisão
bibliográfica sobre problemas de localização, onde são descritos alguns trabalhos já realizados e os
resultados obtidos. Também é descrito o problema de p-medianas. Nesse mesmo capítulo, é
apresentada uma descrição dos algoritmos mais utilizados para a resolução de problemas
combinatórios. O Capítulo 3 apresenta a modelagem dos algoritmos, incluindo sua especificação e a
sua modelagem. O capítulo também discute como foi implementado cada algoritmo, apresentando a
metodologia utilizada no desenvolvimento. Concluindo, no Capítulo 4, apresentam-se as
considerações finais, onde são abordados os resultados, mudanças de algumas estratégias de
desenvolvimento do projeto, dentre outros. O texto ainda inclui dois apêndices e três anexos que
complementam as informações apresentadas no trabalho.
5
2 FUNDAMENTAÇÃO TEÓRICA
2.1 MODELOS PARA LOCALIZAÇÃO DE FACILIDADES
2.1.1 Introdução
Problemas de localização estão presentes no cotidiano das pessoas de diversas maneiras,
sejam na localização de escolas, supermercados, postos de saúde, e possuem várias aplicações seja
na distribuição de energia elétrica, na distribuição de antenas de telecomunicações, distribuição e
transporte de produtos entre outros. Estes problemas tratam da configuração da localização de
facilidades de forma a atender a demanda da população.
Pode-se considerar modelos de avaliação e modelos de otimização. O modelo de avaliação
calcula as medidas de performance como tempo resposta ou proporção de tempo ocupado durante
um período, para várias alternativas de localização, enquanto que os modelos de otimização
determinam a localização ótima das instalações de acordo com uma ou mais medidas de
performance (SOUZA, 1996).
Estes modelos podem ser incluídos dentro de duas categorias:
1. Cobrimento uniforme, que busca minimizar o número de instalações de serviços
(facilidades) requeridas, de modo a assegurar que nenhum ponto da área em estudo
estará mais afastado que uma distância ou tempo resposta prefixado.
2. Modelos com formulação destinada a minimizar o tempo de viagem entre a facilidade e
os pontos da área em estudo. Destacam-se os modelos conhecidos como Minsun e
Minmax.
Segundo Souza (1996), no modelo Minsun, também conhecido como p-mediana, o número
de facilidades (p) é um dado exógeno, ou seja, pré-estabelecido, procurando-se distribuí-las de
modo que o maior número de pessoas tenha acesso às facilidades, dentro de uma distância máxima
estabelecida, com o menor custo do incidente possível (este custo pode ser: tempo de viagem,
tempo resposta, prejuízos decorrentes de um incêndio, etc.) ou, em outras palavras, procura-se
minimizar a soma dos custos de transportes associados com p facilidades.
No Minmax o objetivo não é minimizar o custo total, mas sim minimizar o máximo custo
(por exemplo, a máxima distância) que algum ponto de demanda pode incorrer.
Pode-se levar em consideração a capacidade de atendimento da facilidade. Isto caracteriza
um problema de localização capacitado. Neste tipo de problema é fornecido um conjunto de objetos
como entrada e estes com diferentes pesos, e deseja-se dividir este conjunto de objetos em p
agrupamentos, a intenção é que o peso total dos objetos em cada agrupamento seja menor ou igual a
um dado valor e ainda minimizar a dispersão total dos objetos em relação a uma mediana definida
como centro do agrupamento (LORENA et al., 2002).
A Figura 1 mostra um problema de localização capacitado onde cada mediana representa
uma instalação de serviços de emergência e cada instalação possui uma capacidade máxima de
atendimento.
Figura 1. Localização de 3 medianas – capacitado - distâncias euclidianas
Fonte: Lorena (2003).
“O problema de localização de facilidades (recursos) consiste em localizar um conjunto de
facilidade dentre m possíveis para satisfazer, a um custo mínimo (o menor possível), todas
as demandas de n clientes. Os custos envolvidos seriam a construção de facilidades (escola,
silos, etc.) e também os custos com o transporte (considera-se proporcional à distância).
Leva-se em conta também a capacidade de cada facilidade atender aos clientes.” Lorena et
al., (2002)
7
Quando não são consideradas as restrições de atendimento, o problema passa a ser do tipo
não capacitado, pois admite-se que cada ponto pode atender um número ilimitado de postos de
demanda. A Figura 2 mostra a localização de três medianas as quais são Rádios FM. Usando
distâncias euclidianas em um problema não capacitado, neste caso o número de clientes a ser
atendido por cada rádio não é relevante pois o sinal vai abrangir uma área máxima não importando
o número de ouvintes.
Figura 2. Localização de 3 medianas – não capacitado – distâncias euclidianas
Fonte: Lorena (2003).
Os problemas de localização podem ainda levar em consideração a localização de uma única
mediana, o qual o objetivo deste é localizar a melhor posição de uma facilidade de modo que
minimize a distância média dos usuários à mediana. E a localização de diversas medianas, a qual o
objetivo é minimizar a distância dos usuários até a mediana mais próxima, fato o qual torna o
problema mais difícil de ser resolvido com um tempo aceitável.
8
2.1.2 Definição do problema de p-medianas
O problema de p-medianas consiste em determinar p instalações (facilidades) que deverão
atender a um conjunto existente de demanda. A solução ideal (ótima) do problema é encontrar a
menor soma de todas as distâncias entre as p-instalações e as demandas.
“O modelo de p-medianas é um dos modelos de localização mais populares da literatura.
Foi aplicado várias vezes para localizar centros nos setores públicos e privados.
Conceitualmente, ele é muito simples, entretanto, possui um número muito grande de
soluções, e não é sempre possível resolve-lo de forma ótima”. Lorena (2003).
De acordo com Pereira (2005), o problema de p-medianas tem as seguintes características:
• Um número finito de pontos, com valores conhecidos de demanda, denominados pontos de
demanda;
• Um número finito de locais candidatos para a instalação de facilidades;
• A distância entre cada ponto de demanda e os locais candidatos. Tais distâncias podem ser
calculadas sobre a rede de caminhos que conectam os pontos, ou como distâncias
euclidianas; e
• O número p de facilidades a serem instaladas.
Considerando-se um grafo com um número fixo de vértices a serem nomeados como
facilidades, e os arcos deste grafo sendo os caminhos entre o ponto de demanda (outros vértices mas
não os nomeados como facilidades), e as facilidades, deve-se encontrar a melhor localização destes
vértices de forma que a soma das distâncias de cada vértice até a facilidade seja a mínima possível.
Minieka (1978 apud FLEISCHFRESSER, 2001), fornece definições básicas a respeito do
estudo de medianas. Considerando um grafo, definido por um conjunto de m pontos (ou vértices) e
um conjunto de arcos que ligam todos esses pontos (ou vértices), então mediana é qualquer ponto
(ou vértice), cuja distância total a todos os outros pontos ou vértices seja a menor possível. Para se
obter uma solução ideal as técnicas indicadas para a resolução deste tipo de problemas pertencem à
programação linear inteira.
Hakimi (1964 apud ROSA, 1996) considerou duas categorias de problemas de localização
que fazem parte de um problema de encontrar uma localização ótima para uma facilidade numa
rede que envolve a seleção de uma localização central.
9
Segundo Rosa (1996), estas categorias de problemas são do tipo de problema de localização
"Minmax" e " Minsun". Conforme descrito anteriormente o primeiro problema destes dois consiste
em determinar um vértice u de um dado conjunto de vértices V(G) de um grafo G (finito, conexo,
não-orientado) de maneira que minimize a soma das máximas distâncias de u até todos os vértices
deste grafo, isto é, que minimize a função Minmax dada por:
e(u ) = max{d (u, v ); v ∈ V (G )}.
Equação 1
O Minsun consiste em determinar um vértice u ∈ V(G) de maneira a minimizar a soma das
distâncias de u até todos os vértices do mesmo grafo também conhecido como problema de
localização de soma mínima, onde a localização ótima da facilidade é denominada a mediana do
grafo, isto é, que minimize a função:
D (u ) = {d (u , v); v ∈ V (G )} .
Equação 2
A função e(u ) é chamada de excentricidade de u, e o subconjunto de vértices com mínima
excentricidade é chamado de centro do grafo G. A função D (u ) é a distância de u em G, e o
subconjunto de vértices com mínima distância é chamado de mediana do grafo G. (ROSA, 1996).
De acordo com Lobo (2003), para trabalhar com medianas em geral considera-se um grafo
não direcionado G(N,A) com n nós. Toma-se um inteiro p e escolhe-se um conjunto de p pontos do
grafo, indicado por Xp. Indica-se por d(Xp, j) a distância mínima entre qualquer elemento de Xp e o
nó j do grafo G. Ou seja,
d ( X p , j ) = Minxi ∈X p {d ( xi , j )}
Equação 3
Um conjunto X *p de pontos do grafo G é dito um conjunto de p-medianas de G se para todo
Xp ∈ G tem-se:
J ( X *p ) ≤ J ( X p )
Equação 4
10
onde,
Equação 5
n
J ( X p ) = ∑ h j d ( X p , j)
j =1
A variável
hj
representa um peso atribuído ao nó j e pode representar, por exemplo, a
demanda deste nó (Lobo, 2003).
O problema de p-medianas devido a sua importância econômica é foco de várias aplicações
encontradas na literatura, vários pesquisadores têm desenvolvido heurísticas a fim de melhorar os
resultados já obtidos.
Pereira (2005),descreve o algoritmo branch-and-price para obtenção de soluções viáveis
para problemas de p-medianas, destacando aspectos computacionais referentes à obtenção do
conjunto inicial de colunas, controle do tamanho do problema e critério de ramificação. Apresenta
os resultados de testes computacionais para instâncias de problemas de p-medianas com até 900
vértices. Os algoritmos de geração de colunas e branch-and-price se mostraram mais eficientes que
abordagens de geração de colunas baseadas em relaxação lagrangeana tradicional. Também
concluiu, com base nos resultados apresentados, que o uso combinado de geração de colunas com a
relaxação lagrangeana/surrogate produz resultados superiores aos obtidos pelas heurísticas
lagrangeanas baseadas em otimização de subgradientes, mesmo para instâncias onde a relação entre
o número de vértices e o número de facilidades a serem localizadas não sejam favoráveis às
abordagens baseadas em geração de colunas.
Fleischfresser (2001), implementou heurísticas a fim de melhorar os serviços de entrega de
jornais a seus assinantes na cidade de Curitiba - PR mediante a busca de locais mais adequados para
servirem de postos de distribuição e com um melhor agrupamento dos bairros atendidos pelos
postos. Ele utilizou o algoritmo de Teitz e Bart, Simulated Annealing, Algoritmos Genéticos, e
desenvolve alguns programas fazendo uso do software MATLAB para a resolução do problema.
Os dados iniciais são as coordenadas cartesianas ortogonais dos pontos representativos de cada
bairro e o número de assinantes em cada bairro. Foi levado em consideração a possibilidade de
existirem desde 5 até 10 postos de distribuição, de modo que se pudesse efetuar a comparação entre
os diversos resultados encontrados. Após os testes realizados concluiu que o algoritmo de Teitz e
Bart, e Simulated Annealing, se mostraram mais eficientes para a resolução do problema. Os
resultados obtidos foram melhores que a solução utilizada pela organização jornalística estudada,
11
mas não se pode afirmar que é a melhor solução devido a particularidades da empresa que não
foram consideradas em seu trabalho. Em seu trabalho ele afirma que se a solução proposta for
adotada, haverá importante redução no tempo da entrega, possibilitando o aumentando no período
de redação do jornal, fator de real significação para uma empresa desta natureza, pois permitira a
ampliação de sua competitividade com os outros meios de divulgação.
Rosário (2002), descreve em seu trabalho uma metodologia para a distribuição espacial de
unidades de saúde 24 horas no município de Curitiba PR. Com o objetivo de apresentar uma
sistemática para indicar em que regiões devem ser localizadas as unidades de saúde 24 horas com o
intuito de minimização de distâncias observando os aspectos mais relevantes obtendo assim maior
proximidade entre os usuários e as unidades de saúde, possibilitando assim maior satisfação aos que
mais precisam dos serviços.
Arakaki e Lorena (2006), desenvolvem uma nova heurística de localização-alocação(HLA)
para problemas de localização de facilidades. A heurística foi aplicada a dois problemas: O
problema de máxima cobertura (PLMC) e o Problema das p-medianas capacitado(PPMC) com o
intuito de integração a sistemas de informações Geográficas (SIG).
Corrêa (2000), em seu trabalho apresenta a aplicação do problema de p-medianas capacitado
a um problema real. Ele propôs um algoritmo que otimiza a designação de candidatos ao vestibular
para os locais de prova mais próximos de suas residências. Para resolver tal problema foram
aplicadas duas heurísticas adaptadas ao problema foi adaptado o algoritmo Genético simples que
utiliza os operadores genéticos usuais e um operador heurístico chamado “Hipermutaçao
direcionada”. A segunda heurística proposta é baseada em busca Tabu. O problema abordado por
Corrêa (2000), é do tipo de problema de localização capacitado, pois o conjunto de locais
disponíveis para a realização das provas é limitado, e os locais de provas pode atender a um número
limitado de demanda (é uma restrição de capacidade). Neste trabalho foram exploradas as
características de cada uma das heurísticas utilizadas e observou-se que ambas podem gerar bons
resultados quando bem aplicadas ao problema das p-medianas. Também foi desenvolvido um
algoritmo capaz de otimizar a designação de candidatos ao vestibular aos locais de provas mais
próximos de suas residências. Para validação foram realizados testes computacionais a fim de
verificar a eficiência das heurísticas desenvolvidas. Segundo Corrêa (2000), esta otimização pode
propiciar maior comodidade para os candidatos que terão oportunidade de realizar as provas em
locais próximos as suas residências.
12
2.2 MÉTODOS EXATOS E ESTOCÁTICOS PARA LOCALIZAÇÃO DE
FACILIDADES
2.2.1 Introdução
Métodos estocásticos são métodos probabilísticos o que não garante que a solução
encontrada seja a solução ótima do problema, ao contrário dos métodos determinísticos que
baseados nas características do problema são capazes de determinar a melhor solução. Métodos
estocásticos são caracterizados por explorarem aleatoriamente uma vizinhança em busca de uma
solução melhor do problema. (BEZ, 2005).
Embora não possa ser garantida a melhor solução estes métodos em geral tendem a
aproximar-se da solução ótima, produzindo resultados aceitáveis (dependendo do problema em
questão). Estes métodos têm sido muito utilizados em problemas considerados de difícil solução, os
quais geralmente demandam processamento exaustivo e o tempo para determinar a solução ideal é
inviável. Os métodos estocásticos produzem soluções aceitáveis com um tempo de processamento
baixo se comparados com os métodos determinísticos em geral.
Por essas características eles tem sido muito utilizados para a resolução de problemas reais,
entre eles o problemas das p-medianas. Nesta classe de métodos podem-se citar entre os mais
utilizados os seguintes: Simulated Annealing (KIRKPATRICK; GELLAT; VECCHI, 1983), Tabu
Search (GLOVER, 1986; GLOVER; LAGUNA, 1995, 1997), Ant Colony Optimization Otimização de Colônia de Formigas (DORIGO, MANIEZZO & COLORNI, 1996), GRASP - Greedy
Randomized Adaptive Procedure (FEO e RESENDE, 1995). e os métodos evolucionários
(HOLLAND, 1975).
A seguir serão apresentados algoritmos utilizados para a resolução dete tipo de problema.
2.2.2 Algoritmo de Teitz e Bart
Em 1968 Teitz e Bart propuseram um método baseado na substituição de vértices, para a
resolução de problemas de localização. Neste método é escolhido aleatoriamente um conjunto S de
vértices (medianas), o qual é a solução inicial do problema. A partir da solução inicial busca-se
melhorar o resultado da função objetivo, a cada iteração.
13
De acordo com Corrêa (2000), considerando-se todos os vértices de um grafo como
potenciais medianas o algoritmo de Teitz e Bart para o problema das p-medianas pode ser explicado
como segue:
Seja G = (V , A) um grafo não direcionado onde V são os vértices e A as arestas. Seja v ,
um vértice qualquer pertencente a V . Chama-se número de transmissão à soma das menores
distâncias existentes entre o vértice vi e todos os outros vértices do grafo.
De acordo com Smiderle, Piva e Tibes (2005), o algoritmo de Teitz e Bart segue os
seguintes passos:
Passo 0. Selecione, aleatoriamente, um conjunto V ⊂ V , com
p
solução inicial para o problema;
Passo 1. Rotule todos os vértices
ν i ∈ {V − V p }
para formar uma
como “não analisados”;
Passo 2. Enquanto existirem vértices não analisados em
Selecione um vértice não analisado
Vp = p
v i ∈ {V − V p } ,
{V − V p }
faça o seguinte:
e calcule a redução
transmissão, para todos os vértices vj pertencentes a
Vp ,
∆ ij do
número de
ou seja:
∆ ij = σ (V p ) − σ (V p ∪ {vi } − {v j }), ∀v j ∈V p .
Faça
∆ ij _ max
Faça
V p = (V p U {vi } − {v j })
Rotule
vj
= máximo
[∆ ] para todo
ij
e insira
v j em
∆ ij
calculado anteriormente. Se
∆ ij _ max
> 0 então:
{V − V p } .
como “analisado”.
Caso contrário, continue.
Passo 3. Se, durante a execução do Passo 2, houver alguma modificação no conjunto
Vp ,
então volte ao Passo 1 e continue a execução do algoritmo. Caso contrário, PARE e apresente o
conjunto
Vp
como uma solução aproximada para o problema das p-medianas.
Figura 3.Algoritmo de Teitz e Bart
Fonte: Smiderle, Piva e Tibes (2005)
2.2.3 Algoritmo Simulated Annealing
Também conhecida como cozimento simulado esta é uma técnica heurística moderna muito
utilizada para problemas de otimização combinatória, esta meta heurística foi publicadas por
Metropolis et al., (1953) com o propósito de simular o resfriamento de materiais.
Quando um material sólido é aquecido a uma temperatura elevada chegando ao seu ponto de
fusão e sendo resfriado gradualmente leva o material a estados mínimos de energia. Este é o
principio básico do tratamento térmico que alguns materiais para alterar suas propriedades ou
conferir-lhes determinadas características são submetidos.
14
Segundo Spectru (2007), os principais objetivos do tratamento térmico são:
•
Aumento ou diminuição da dureza;
•
Aumento da resistência mecânica;
•
Melhora da resistência ao desgaste;
•
Melhora das propriedades de corte;
•
Melhora da resistência a corrosão; e
•
Melhora da resistência ao calor.
Baseando-se nestas características a idéia do Simulated Annealing é reproduzir um conjunto
de átomos sendo elevados a uma temperatura e resfriados gradualmente, os mesmos partiram de
uma temperatura pré estabelecida, não necessitando aquecê-los, apenas controlar o resfriamento. As
Figuras 4, 5 e 6 apresentam a configuração das moléculas de acordo com a temperatura.
Figura 4. Estado desordenado das moléculas da matéria em fusão.
Fonte: Noronha, Aloise e Silva (2001)
Figura 5. Estado desordenado das moléculas consecutivo a um resfriamento
rápido.
Fonte: Noronha, Aloise e Silva (2001)
15
Figura 6. Estado ordenado das moléculas consecutivo a um resfriamento lento.
Fonte: Noronha, Aloise e Silva (2001)
O Simulated annealing gera aleatoriamente novas configurações, porém essas novas
soluções são aceitas de acordo com uma taxa de probabilidade de aceitação, isso é utilizado para
que o algoritmo não fique preso a mínimos locais e não encontre a melhor solução. Se a temperatura
for lentamente reduzida os átomos tendem a se arranjar em um estado que minimiza sua energia que
é o estado ideal. (RICH & KNIGHT,1994).
Porém se houver uma queda brusca da temperatura os átomos chegarão a um estado mínimo
muito rapidamente e estes estarão ainda muito desordenados.
Por ser um método estocástico o algoritmo realiza uma busca aleatória porém direcionada de
acordo com o fator de esfriamento e a taxa de aceitação utilizada.(RICH &KNIGHT ,1994).
16
A Figura 7 apresenta o algoritmo de metrópolis.
Figura 7. Algoritmo de Metrópolis
Fonte: Noronha, Aloise e Silva (2001)
De acordo com Noronha, Aloise e Silva (2001), este algoritmo se decompõe em duas
grandes buscas sobrepostas. A busca externa controla o término do processo e é baseado na noção
de estado resfriado. A busca interna contém o processo de otimização. Para uma temperatura fixada,
explora-se a vizinhança aceitando ou não os movimentos são apresentados. Ao fim de L iterações
diminui-se a temperatura.
No decorrer de uma iteração interna, escolhe-se ao acaso um elemento v no centro da
vizinhança da solução corrente s . Se v é um vizinho melhor, ou seja, a quantidade objetivo em v é
inferior aquela em s , então v é aceita como uma nova solução corrente. Ao contrário, se a
passagem de s a v degrada o objetivo, aceita-se o movimento com uma probabilidade ligada a
diferença das quantidades objetivo e a temperatura corrente. Isto é o mecanismo de aceitação
condicional das “ascensões” que permitem ao método de sair dos mínimos locais. (NORONHA,
ALOISE & SILVA, 2001).
“Quando a temperatura se eleva, praticamente todos os movimentos serão autorizados
como no caso da matéria em fusão onde a energia do sistema é muito elevada. Quanto mais
17
a temperatura abaixa, mais as degradações serão penalizadas em função de lucro dos
movimentos melhores, o método vai então convergir para o ótimo local mais próximo”.
Noronha, Aloise e Silva (2001).
Quando se chega a uma solução aceitável e as chances de encontrar soluções melhores são
pequenas aceita-se que o sistema esta resfriado, este critério pode ser estabelecido com um número
estabelecido de iterações do algoritmo, a uma temperatura sem encontrar uma solução melhor.
A alteração da temperatura pode ser realizada de diversas formas, uma delas é aceitar uma
temperatura fixa, este método é chamado de recozimento a temperatura fixa. O resultado pode ser
muito bom dependendo do problema em questão mas as chances de entrar em um local e não
conseguir sair do mesmo são grandes.
Segundo Fleischfresser (2001), as melhores soluções em geral são encontradas utilizando
uma temperatura que decresça lentamente pois a aceitação de configuração de maior energia tornase cada vez mais improvável, até que nos últimos estágios da simulação, somente são aceitas
configurações que representem um decréscimo no valor da função objetivo.
2.2.4 Algoritmo Genético
Os algoritmos genéticos são baseados na teoria de Charles Darwin, que em meados do
século XIX, em viagem pelo mundo teve a oportunidade de perceber as adaptações que aconteciam
de acordo com cada ambiente. Darwin já estava questionando o conceito estático da Terra. Para ele
a Terra evoluía e estava em constante transformação. Darwin percebeu que a origem e proliferação
das espécies em cada ambiente eram processos muito relacionados, pois percebeu que a
sobrevivência dos indivíduos de cada espécie estava relacionado a adaptação do individuo ao meio.
Ele salientou que os indivíduos mais bem adaptados teriam maior chance de sobreviver e
reproduzirem-se. Em sua passagem pelas ilhas Galápagos que hoje pertencente ao Equador ele
registrou as observações sobre a variação de espécies, em que cada ilha apresentava uma espécie
dominante. Sua teoria passou a ser aceita pelo meio científico no século XX, quando Mendel
realizou descobertas acerca da transmissão hereditária de caracteres fato que comprovava a teoria
de Darwin, pois as características de cada indivíduo são repassadas aos seus sucessores
permanecendo sempre os indivíduos mais bem adaptados a cada ambiente. (SANTOS, OLIVEIRA,
& DUTRA, 2006 ).
18
Por vezes, alguns indivíduos apresentam uma nova característica, indivíduos mutantes, que
os distingue do restante de sua espécie. Caso esta nova
característica
apresente
vantagens competitivas em relação aos demais membros
da população, este indivíduo
possui uma probabilidade maior de sobrevivência. Dessa maneira, ele se torna apto a
reproduzir e, assim, perpetuar suas características. (BEZ, 2005).
A idéia inicial de utilizar a teoria de Darwin para a resolução de problemas foi introduzida
por Holland (1975). E em 1989 Goldberg baseado no trabalho Holland publicou Genetic Algorithms
in Search, Optimization and Machine Learning que em seus estudos perceberam que a descoberta
de Darwin poderia ser utilizada para resolução de diversos problemas.
O princípio básico do funcionamento dos algoritmos genéticos é que um critério de seleção
vai fazer com que, depois de muitas gerações, o conjunto inicial de indivíduos gere indivíduos
melhores o que representa soluções melhores do que as iniciais, e depois de varias gerações as
melhores soluções possam ser utilizadas.
Segundo Bez (2005), o princípio básico de um algoritmo genético é manter uma população
de indivíduos que evolui e se modifica por meio de recombinações desses indivíduos e de mutações,
aplicadas a certa parcela dessa população, ocasionadas por pequenas alterações do meio.
Como, de acordo com a teoria Darwiniana, os indivíduos mais aptos sobrevivem, utiliza-se
uma função de aptidão ou avaliação responsável pela classificação dos indivíduos pelo grau de sua
aptidão.
19
A estrutura de um algoritmo genético pode ser vista na Figura 8.
Figura 8. Estrutura do algoritmo Genético
Fonte: Adaptado de Bez (2005).
São componentes do algoritmo genético:
•
População- Representa um conjunto de indivíduos.
•
Geração- Representa uma população em um determinado tempo.
•
Aptidão- Que é utilizada para definir se a solução encontrada é boa ou ruim dependendo
dos resultados encontrados até o momento.
•
Gene- representa os parâmetros e é responsável pela transmissão de características de um
individuo para outro.
•
Genótipo- Representa a constituição genética de cada individuo pela distribuição dos genes
num cromossomo.
•
Fenótipo- É o cromossomo codificado.
•
Cromossomo- Cada cromossomo é formado por um conjunto de genes e representa
possível solução, dependendo da sua aptidão.
20
uma
Operadores genéticos
Os operadores genéticos são os elementos que determinam a evolução dos indivíduos a cada
geração, são parâmetros que dependendo do seu valor podem melhorar os indivíduos subseqüentes,
transformando assim a população através de sucessivas gerações. Eles são necessários para que a
população se diversifique e mantenha características adquiridas por gerações anteriores.
Usando apenas os operadores básicos, problemas de complexidade média podem ser
resolvidos apresentando bons resultados. (CORRÊA, 2002). Os operadores básicos para a utilização
de algoritmos genéticos são: cruzamento, mutação, seleção.
Seleção
A seleção é o mecanismo responsável pela escolha dos indivíduos que irão compor uma
nova geração, pois quando ocorre o cruzamento a população aumenta, e é necessário que seja feita a
escolha de quais indivíduos são mais aptos a permanecerem na população. (COSTA FILHO, 1998).
A seleção é feita levando em consideração a aptidão de cada indivíduo, quanto mais apto ele
for as chances dele continuar na população são maiores. Uma maneira de realizar a seleção é
ordenar todos os indivíduos em ordem decrescente de acordo com a sua aptidão gerando assim uma
lista, conseqüentemente os indivíduos melhores adaptados estarão todos no final da fila, basta
retirar da lista a partir do inicio da mesma a quantidade de elementos necessária para que a
população volte ao tamanho desejado, este método é também conhecido como método elitista.
Outro método também utilizado é o chamado método da roleta, que consiste em colocar os
indivíduos na roleta atribuindo a cada um uma parte proporcional a sua aptidão. (BEZ, 2005).
21
A Figura 9 mostra um exemplo de roleta onde cada parte representa um individuo, as partes
maiores representa os indivíduos mais bem adaptados.
Figura 9. Roleta de seleção
Após a atribuição a roleta é girada, e a fatia onde a agulha parar estará associada a um
individuo e este permanecerá na população. Este método também garante que os indivíduos mais
aptos terão uma chance maior de permanecerem na população. A roleta e acionada quantas vezes
for necessário para atingir o numero desejado de indivíduos na população.
Cruzamento
O cruzamento ou reprodução é a geração de novos indivíduos, para que o cruzamento ocorra
é necessário dois cromossomos os quais darão origem a mais dois cromossomos que terão
características semelhantes aos cromossomos pais. O cruzamento é necessário para que as
características sejam repassadas. O parâmetro de cruzamentos é também conhecido como crossover
por ser um operador predominante ele deve ser maior que a taxa de mutação que é um operador
secundário. (CAZANGI, 2004).
O cruzamento consiste em dividir os dois indivíduos pais em segmentos e promover a troca
destes segmentos, a troca destes dará origem a um novo individuo. O cruzamento pode ser feito
escolhendo os genes os quais serão trocados entre os cromossomos ou definindo um ou mais pontos
de corte.
22
As Figuras 10, 11 e 12 mostram como pode ser realizado o cruzamento.
Figura 10. Procedimentos de cruzamento com troca de genes randômica.
Fonte: Corrêa (2000).
Figura 11. Exemplo de cruzamento com 1 ponto de corte.
Fonte: Corrêa (2000).
Figura 12. Exemplo de cruzamento com 2 pontos de corte.
Fonte: Corrêa (2000).
23
Durante o cruzamento pode ocorrer inconsistências, isso é mais comum quando o algoritmo
genético é representado de forma não binária, pois na hora do cruzamento existe por exemplo um
gene que irá se repetir conforme é mostrado na Figura 13 .
Figura 13. Exemplo de cruzamento com 2 pontos de corte.
Fonte: Boechel (2003).
A Figura 12 também mostra uma técnica utilizada para corrigir o problema de
inconsistência, existem outras maneiras de correção, o objetivo das técnicas de resolução de
inconsistência é que o cruzamento seja realizado e não exista repetição de genes no cromossomo.
Mutação
O operador de mutação é responsável pela diversificação da população, quanto maior o fator
de mutação mais a população sofrerá mutações e se diversificará fato o qual pode ser positivo,
gerando indivíduos melhores adaptados ou negativo piorando se esses indivíduos tiverem a chance
de
se reproduzirem. A mutação geralmente é feita de forma aleatória trocando a ordem de
formação do cromossomo. Com essas alterações genéticas é possível assegura-se que a
probabilidade de sair de mínimos locais é grande pois modifica-se levemente a direção da busca
com as mutações. O operador de mutação geralmente é pequeno pois é um operador genético
secundário. (COSTA FILHO, 1998).
24
A Figura 14 ilustra a mutação de um individuo que neste caso tem seu gene número três
alterado.
Figura 14. Mutação por troca simples.
Fonte: Corrêa (2000).
A Figura 15 mostra como é definido cada população a cada ciclo de reprodução. Onde SP1,
SP2 e SP3 são indivíduos da população.
Figura 15. Processo de reprodução
Fonte: Adaptado de Jungbeck (2001).
Parâmetros Genéticos
Os algoritmos genéticos possuem parâmetros que podem ser ajustados de acordo com a
implementação dos mesmos, os parâmetros que podem ser alterados são a taxa de mutação dos
indivíduos, a taxa de cruzamento da população, e o tamanho da população. O tamanho da população
25
está diretamente ligado ao espaço de busca, quanto menor a população menor será o número de
cruzamentos, e poderá ocorrer a convergência prematura chegando a pontos mínimos com poucas
chances de sair dos mesmos. Usando uma população grande a área de cobertura será maior e as
chances de o algoritmo cair em pontos mínimos e não conseguir sair é menor, porém quanto maior a
população maior será o esforço computacional.
A taxa de mutação é um parâmetro o qual se atribui geralmente um valor pequeno por se
tratar de um operador secundário, se utilizar altas taxas de mutação pode interferir nas
características boas dos indivíduos, podendo descartar um indivíduo bem adaptado muito cedo,
usando taxas de mutação pequenas previne-se a estagnação de uma população, e ao mesmo tempo
permite que todo o espaço de busca seja coberto.
2.2.5 Algoritmo Busca Tabu
De acordo com Gomes (2003) a Busca Tabu é uma das metaheurística mais usadas em
problema de otimização combinatória e foi primeiramente apresentada em sua forma atual por
Glover em 1986 sendo projetada para resolver problemas de otimização combinatória nas áreas de
Pesquisa Operacional, Inteligência Artificial, Computação Paralela, Logística entre outras.
De acordo com Viana (1998 apud GOMES, 2003), este método apresenta as seguintes
características: i - uso de uma estrutura de dados (lista) para “guardar” o histórico da evolução do
processo de busca; iii - uso de um mecanismo de controle para fazer um balanceamento entre a
aceitação, ou não, de uma nova configuração, com base nas informações registradas na “lista tabu”
referentes às restrições e aspirações desejadas e iii - incorporação de procedimentos que alternam as
estratégias de diversificação e intensificação.
É uma metaheurística de melhoramento local que se utiliza de uma lista (tabela), de
movimentos realizados, para garantir que não irá ficar preza em locais ótimos. Quando um local é
visitado através de um arco, por exemplo, este local e este arco vão para a lista tabu, e durante um
número estabelecido de iterações este local não pode ser alcançado utilizando o arco que esta na
lista tabu. (DUCATI, 2003).
De acordo com Araujo (2004), duas regras podem ser definidas como critério de parada para
Pesquisa Tabu: (i) é definido um número máximo de iterações (nbmax) que serão realizadas sem
que ocorra melhora no melhor resultado obtido; (ii) em muitos casos o mínimo global f* é
26
conhecido e a pesquisa pode ser interrompida quando este mínimo for alcançado. Porém, em muitos
casos, o ótimo global não é conhecido. A seguir é na Figura 16 é mostrado o algoritmo geral da
Pesquisa Tabu.
Inicialização
S=solução inicial em x
Niter=0;
Melhiter=0;
Melhsol = s;
Enquanto (f(s) > fmin) e (niter-melhiter < nbmax) faça
niter = niter+1;
Gerar um conjunto V* de soluções si em N(s) que não
seja tabu T ou f(si) < A(f(s));
Escolher a melhor solução s* em V*;
Se f(s*) <f(melhsol) então
melhsol = s*;
melhiter = niter;
fim se;
fim enquanto;
Figura 16. Algoritmo Busca Tabu
Fonte: Adaptado de Araujo (2004).
Segundo Noronha, Aloise e Silva, (2001) a busca Tabu apresenta bons resultados e é fácil
de ser implementada. No entanto é sensível a dois problemas:
•
A aparição de motivos ou de atratores por conseqüência da exploração da
vizinhança, onde não somente se perderá tempo reavaliando várias vezes os mesmos
estados, mas não se ganhará conhecimento suplementar sobre o problema; e
•
Uma propensão a descida muito rápida em direção a um ótimo local: a descida
agressiva, Realmente, o método tem uma tendência a “abrir caminho” em direção
aos mínimos locais, de onde é difícil sair.
De acordo com (Braga et al. 1994 apud GOMES, 2003), é necessário que a Lista Tabu tenha
um comprimento definido, pois poderá haver momentos em que seja necessário voltar para alguma
solução, e a partir dela, buscar outras soluções. O tamanho da vizinhança é outro parâmetro
importante para o uso da Busca Tabu. A escolha do tamanho da vizinhança regula o tempo de
execução do algoritmo. Uma má escolha desse parâmetro pode comprometer a execução do
algoritmo; assim este valor deve ser ajustado, juntamente com o número máximo de iterações, para
se obter bons resultados num tempo aceitável. No caso onde a vizinhança é muito rica, ou seja, para
cada solução, o número de vizinhos é muito grande. Podemos reduzi-los sorteando os elementos a
serem avaliados.
27
“Os métodos de Pesquisa Tabu aparecem como os mais versáteis métodos de pesquisa
local, pois eles se prestam naturalmente as extensões mais diversas. Entretanto, se
desejamos implantar sobre um método Tabu todos os mecanismos de extensão que nós
vimos, choca-se a um problema de coerência na definição do método.Historicamente, é esta
última razão que motiva a pesquisa da formulação genérica e unificada dos métodos de
melhoramento interativo”. Noronha, Aloise e Silva (2001).
Araujo (2004), utilizou Busca Tabu a fim de resolver problemas de p-medianas aplicados a
problemas de corte para projetar um conjunto de Peças em um objeto (Placa), determinando um
Plano de Corte Guilhotina Bidimensional, direcionado a peças regulares com restrições quanto ao
número tipo de peças. O problema estudado por Araujo consiste em descobrir o melhor arranjo de
um conjunto de peças de dimensões diversas que precisa ser projetado em um objeto com
dimensões maiores, com o objetivo de minimizar a perda de matéria prima. Existem diversas
aplicações para o problema estudado como por exemplo aplicações na indústria moveleira, têxtil,
metal mecânica setores da economia em que o arranjo das peças a serem produzidas é um fator
importante para a economia de matéria prima influenciando na competitividade da empresa no
mercado. Diminuindo o custo da produção a empresa pode ter um preço mais competitivo e
aumentar seu lucro.
2.2.6 Algoritmo baseado em colônia de formigas
Esta metaheurística é baseada no comportamento de uma colônia de formigas e foi
introduzida por Dorigo, Maniezzo e Colorni (1991). As formigas naturais saem a procura de
alimento e para chegar a esta fonte de alimento percorrem certa trajetória. Na colônia de formigas
natural percebe-se que após certo tempo todas tendem a percorrer a melhor rota. Isso acontece por
que os melhores caminhos podem ser identificados pela quantidade de uma substância chamada
feromônio.
Os feromônios são odores que transportam informações específicas capazes de promoverem
a comunicação entre os indivíduos da mesma espécie ou colônia. (Birch e Hayanes, 1982 apud
VILELA & DELLA LUCIA, 1987).
A organização da vida das formigas em sociedades somente foi possível com a utilização
dos feromônios, possibilitando o reconhecimento individual e a cooperação na execução das
múltiplas atividades da colônia. (VILELA & DELLA LUCIA, 1987).
Os feromônios conhecidos nas formigas são, principalmente, os de alarme, reconhecimento
individual, da rainha, marcação de trilha, e recrutamento, marcação de folhas e de território. O
28
feromônio responsável pela formação das trilhas e pelo recrutamento de companheiras para os
locais de forrageamento é produzido pelas glândulas de veneno e é depositado sobre as superfícies
(VILELA & DELLA LUCIA, 1987).
No início as formigas saem todas para destinos aleatórios vão a busca de comida e
percorrem praticamente todo o território ao seu redor quando cada formiga sai à procura de
alimento ela deixa pelo caminho o feromônio que é uma substância natural exalada pelas formigas,
a formiga sai de seu ninho vai até a fonte de alimento e retorna.
Conseqüentemente os caminhos mais curtos terão uma quantidade maior de feromônio, com
isso a probabilidade de outras formigas irem pelo mesmo caminho é maior. A Figura 17 ilustra o
funcionamento da busca de comida na natureza.
Figura 17. Diferentes caminhos escolhidos pelas formigas, durante um determinado intervalo de
tempo.
Fonte: Silva et al. (2005).
O feromônio exerce atração sobre as formigas e quanto maior a quantidade de feromônio no
caminho maior a quantidade de formigas será atraída para o mesmo local, e conseqüentemente isso
vai aumentar ainda mais a quantidade da substância no caminho percorrido. Quando uma formiga
encontra um obstáculo que possa impedir sua passagem a mesma tende a deslocar-se para o lado
que mais lhe atrai (que possui uma concentração maior de feromônio). Com o passar do tempo
todas as formigas estarão indo para a fonte de alimento pelo caminho mais próximo.
A versão artificial de colônia de formigas considera um conjunto de agentes que colaboram
para uma solução ideal usando um tipo de comunicação semelhante ao que tem a mesma função do
feromônio na natureza.
29
Quando saem em busca de comida elas escolhem a próxima região a ser visitada de forma
probabilística, entre as regiões que não foram visitadas. A probabilidade de a formiga escolher uma
nó para chegar até a região escolhida é diretamente proporcional a atração que o mesmo exerce
através da quantidade de feromônio que possui. As formigas compartilham uma tabela que contém
todas as regiões já visitadas e a cada região visitada ela acrescenta nesta tabela a região. Ao
retornarem á colônia as formigas põem um rastro de feromônio em todos os nós utilizados. Isso
pode ser feito à medida que a formiga se locomove também para que se assemelhe mais com a
colônia natural. A Figura 18 apresenta o algoritmo em pseudocódigo para esta metaheurística.
Figura 18. Pseudocódigo da colônia de formigas.
Fonte: Bez (2005).
Se não levar em conta o ferômonio a busca se torna probabilística podendo chegar em
soluções ruins e o espaço não seria bem explorado.
A atualização do feromônio pode ser feita de duas maneiras; a cada arco visitado a formiga
atualiza a quantidade de feromônio no mesmo, que representa de forma mais adequada o que ocorre
na natureza, ou pode-se fazer a atualização global que ocorre quando a formiga chega ao final da
sua rota e atualiza todos os arcos que utilizou.
O acréscimo de feromônio pode ser constante ou variável dependendo da abordagem
utilizada, no caso de acréscimo constante, o acréscimo de feromônio é constante para todas as
30
formigas e para todos os arcos, já no caso de acréscimo variável além do acréscimo constante, as
formigas depositam uma quantidade de feromônio que depende da qualidade do caminho
percorrido, pois quanto menor o caminho maior será a quantidade de feromônio depositada. A
escolha do próximo nó a ser visitado, se baseia em uma probabilidade que utiliza o feromônio como
parâmetro conforme a Equação 5:
[ ] [ ]
 τ ij α ⋅ η ij β

α
β
pijk =  ∑ [τ iu ] ⋅ [η iu ]
 u∈J k
0
se j ∈ J k (i )
Equação 5
caso contrário
onde:
pijk = probabilidade da formiga k, que se encontra em i, escolher o nó j como próximo nó a
ser visitado;
τ ij = quantidade de feromônio existente no arco (i,j). Inicialmente, adota-se um mesmo valor
τ0
para todos os arcos da rede;
ηij = função heurística que representa a atratividade do arco (i,j), dada por 1/dij ;
J k (i ) = conjunto de pontos ainda não visitados pela formiga k;
Βeta e Alfa = parâmetro que controla a importância relativa ao feromônio e a função que representa
a atratividade.
A quantidade de feromônio a ser incrementada em cada rota esta relacionada ao tamanho da
rota percorrida segundo a Equação 6 :
1
L
 k
k
∆τ ij = 


0
se a k ésima formiga usa o
Equação 6
arco (i, j) no seu caminho.
caso contrário.
31
Evaporação
Com o passar do tempo acontece a evaporação do feromônio em todos os arcos a
evaporação é importante para que os caminhos com menos ferômonio, que são as rotas menos
utilizadas possam ser ainda menos utilizadas pois são caminhos que não interessam mais na busca
já que os melhores caminhos sempre terão ferômonio mesmo com a evaporação aumentando assim
as chances das formigas optarem por um caminho melhor.
32
3 DESENVOLVIMENTO
3.1 Planejamento
3.1.1 Metodologia
Para o desenvolvimento deste TCC, foram cumpridos os seguintes objetivos:
•
Analise de trabalhos que utilizam os problemas clássicos de p-medianas;
•
Definição do problema a ser utilizado no estudo;
•
Apresentação dos algoritmos mais utilizados na resolução de problemas de p-medianas;
•
Seleção das metaheurísticas utilizadas nos testes;
•
Modelagem dos algoritmos para resolução do problema escolhido;
•
Implementação computacional dos algoritmos; e
•
Ensaios numéricos e análise dos resultados obtidos;
A seguir é apresentado como foi tratado o problema, a modelagem dos algoritmos os ensaios
numéricos, bem como a análise dos resultados obtidos.
3.1.2 Problema utilizado nos testes
O problemas a ser tratado é do tipo capacitado e é disponibilizado pelo INPE - Instituto
Nacional de Pesquisas Espaciais no site: (http://www.lac.inpe.br/~lorena/instancias.html) o qual
disponibiliza dados do centro da cidade de São José dos Campos. Por ser uma referência na área de
pesquisa de problemas de localização optou-se por utilizar estes dados como base para os testes.
Os dados diponibinilizados incluem: as coordenadas x e y das demandas, a capacidade de
atendimento de cada facilidade e o número desejado de facilidades. Estes dados estão em formato
de arquivo tipo texto, e podem ser facilmente importados para a realização dos testes, e são
suficientes para a elaboração dos mesmos. Os arquivos são disponibilizados no seguinte formato:
100 10
409154
409151
409277
409260
435528
435683
435420
435538
720
720
720
720
50
4
33
15
33
Onde 100 representa o número de pontos de demandas, 10 representa o número de medianas
a serem inseridas. Todos os vertices podem ser usados como demandas ou medianas. Os outros
dados são as coordenadas x e y a capacidade máxima de atendimento daquele ponto e a demanda de
atendimento do ponto.
Neste trabalho não será proposto à resolução de nenhum problema em específico, os dados
serão utilizados apenas para testes não levando em consideração a natureza dos mesmos. O
problema completo pode ser visto no Anexo I.
3.1.3 Modelagem dos algoritmos
Para a resolução de problemas de p-medianas os algoritmos tratados neste trabalho devem
ser adaptados ao contexto do problema, o problema será abordado como um problema capacitado
onde as medianas poderão atender a um número máximo de demandas, nesta parte do trabalho será
apresentado como cada algoritmo será utilizado.
Para todos os algoritmos, será considerado que se tem um conjunto o qual contém todos os
vértices candidatos a medianas, e tem-se também um conjunto com todas as demandas, e as
informações que são as coordenadas cartesianas de cada vértice e de cada demanda para que as
distâncias possam ser calculadas. Neste caso a distância a ser utilizada nos testes será a distância
euclidiana entre os pontos de demanda e as facilidades, ou seja, a distância em linha reta entre
demanda e facilidade que será calculada quando for necessário utilizá-la.
Cada vértice candidato à mediana deverá ter também a capacidade de atendimento que a
facilidade poderá atender, pois o problema será do tipo capacitado.
3.1.3.1
Algoritmo genético
O algoritmo genético foi modelado para o problema da seguinte maneira:
O cromossomo terá o numero de genes igual ao número de medianas desejado e o alelo de
cada gene representa uma mediana. Esta abordagem já foi utilizada por Corrêa (2000). Por
exemplo, suponha-se que se deseja escolher cinco medianas entre 15 instalações possíveis, as quais
são representadas pelos números 1,2,3,.4,5...,15 destas 15 instalações serão montados os
cromossomos com 5 genes cada um exemplo: [1,2,3,4,5], [1,3,15,11,10]. Cada um destes
34
cromossomos representa uma solução para o problema onde cada gene representa uma mediana. A
ordem dos genes não será levada em consideração, pois não vai alterar o resultado.
O tamanho da população é o número de cromossomos que se deseja ter, sabendo- se que
quanto maior a população maior será o esforço computacional.
Após a determinação do tamanho da população foi realizada a geração da população inicial
e foram definidos quais as demandas atendidas por cada uma das medianas, respeitando a
capacidade de atendimento de cada mediana. Após uma demanda ser escolhida para ser atendida
por uma mediana a mesma não pode ser escolhida por outra mediana.
O fitness (função que quantifica a qualidade da solução) de cada cromossomo, se deu pelo
valor da soma das distâncias euclidianas de cada mediana (gene) as suas demandas.
Tendo o fitness de cada indivíduo (cromossomo) os mesmos foram ordenados de forma
decrescente. Os indivíduos que farão parte de cruzamentos foram escolhidos de forma aleatória
buscando assim evitar que o algoritmo estacione em uma solução tida como ótima e não progrida.
A taxa de mutação dos indivíduos também foi definida nos testes e os indivíduos que
sofreram mutação foram escolhidos de forma aleatória, porém todos tiveram a mesma probabilidade
de sofrer mutação.
Caso a mesma mediana apareça duas vezes no mesmo cromossomo então foi realizado o um
processo de tratamento de inconsistências conforme descrito na sub-seção 2.2.4. Neste caso foi
definido outra possível mediana.
A seleção foi realizada feita ordenando as melhores soluções em ordem decrescente e
escolhendo os indivíduos com o melhor fitness.
A condição de término foi um número máximo de iterações do algoritmo, que foi passada
como parâmetro. Onde cada iteração será caracterizada por:
1. Escolha da população;
2. Cálculo do fitness de cada individuo;
3. Ordenação dos indivíduos de acordo com seu fitness;
35
4. Aplicação do cruzamento entre os indivíduos; e
5. Aplicação da mutação entre os indivíduos.
6. Seleção da população.
Após a aplicação da mutação o algoritmo retorna a escolha da população, se o número de
iterações for igual ao número de iterações máximo informado o algoritmo pode ser finalizado e a
solução proposta será o cromossomo com melhor fitness.
A Figura 19 mostra o código principal do algoritmo.
void Geneticos::Run(ImportadorINPE impe)
{
string duracao;
duracao=TimeToStr(Date().CurrentTime()).c_str();
pop.CriarIndividuos(impe.GetNumVertices() ,qtdIndividuos,impe.GetNumMedianas(),impe.vVertices);
for (int i= 1; i<= gerac; i++){
pop.Cruzar(cruz);
pop.Mutar(mutacoes);
pop.Selecionar(qtdIndividuos,impe.vVertices);
}
duracao= TimeToStr(Date().CurrentTime() - StrToTime(duracao.c_str())).c_str();
char tempo[20];
strcpy(tempo,duracao.c_str());
pop.SalvarMelhorIndividuo(tempo);
}
Figura 19. Código principal algoritmo genético.
3.1.3.2
Simulated annealing
Para aplicar o simulated annealing foi definido inicialmente o parâmetro de controle, que se
chama temperatura, em seguida foi escolhido aleatoriamente, uma solução inicial do problema, que
foi um conjunto com as medianas escolhidas. Calculou-se então a menor soma das distâncias de
todos os pontos (demandas) a essas medianas, e este é o valor da solução inicial.
Após ter-se definido uma solução inicial foram geradas aleatoriamente novas soluções e
calculado da mesma forma o valor destas novas soluções. Em seguida é efetuada a redução da
temperatura, utilizando de um valor fixo de redução, (redução linear) onde foi escolhido e testado
juntamente com os testes numéricos. Após ter fixado uma nova temperatura são realizados
movimentos (trocas de medianas), e é calculada a variação de energia ∆Ε proporcionada pelo
movimento realizado. A energia foi entendida como a distância média, da soma das distâncias das
medianas até suas demandas.
36
Quando a energia decresce, significa que a solução encontrada com o deslocamento é
melhor que a solução até então encontrada e deve ser incorporada ao sistema. Porém se o valor
aumentar esta solução será aceita levando em consideração uma estratégia de aceitação
probabilística, isso é importante para que o algoritmo evite ficar preso em mínimos locais. A
estratégia de aceitação levou em consideração o aumento e diminuição da temperatura, pois a
medida que a temperatura aumentar, a probabilidade de aceitar um movimento também aumenta
pois as moléculas estarão em movimento. A medida que a temperatura diminuir a probabilidade de
aceitar uma configuração é diminuída.
Este sistema se repete em todas as temperaturas, até que o sistema se encontre em um estado
que não seja mais possível realizar movimentos que melhorem a solução ou o numero máximo de
iterações seja alcançado.
A Figura 20 mostra o código principal do algoritmo.
void Simulated::Run(std::vector<Vertice*> &vVertices)
{
int i;
Solucao *novaSol;
sol= new Solucao(vVertices.size(),nMedianas);
sol->Fitness(vVertices);
valorMelhorSolucao= sol->GetFitness();
string duracao;
duracao=TimeToStr(Date().CurrentTime()).c_str();
for (i= 1; i<= nSolucoes; i++){
novaSol= new Solucao(vVertices.size(),nMedianas);
novaSol->Fitness(vVertices);
processa(novaSol);
diminuiTemperatura();
//salvaSolucao();
cout<< i<<" "<< valorMelhorSolucao<<endl;
}
duracao= TimeToStr(Date().CurrentTime() - StrToTime(duracao.c_str())).c_str();
char tempo[20];
strcpy(tempo,duracao.c_str());
salvaMelhorSolucao(tempo);
}
Figura 20. Código principal Simulated Annealing.
3.1.3.3
Algoritmo baseado em colônia de formigas
A colônia de formigas foi utilizada de forma adaptada para o contexto do problema, pois nos
trabalhos estudados pouco se falava sobre a aplicação deste método para a resolução de problemas
de p-medianas. O mesmo foi escolhido para ser implementado e testado por ser uma metaheuristica
pouco conhecida e que tem demonstrado ótimos resultados na resolução de problemas
combinatórios.
37
Inicialmente foi escolhida aleatoriamente uma solução inicial para o problema que contém
os vértices onde se instalaram as facilidades. Os demais vértices que podem ser medianas tiveram
uma quantidade de ferômonio igual para todos. O valor exato foi definido em uma unidade, com
isso é garantido que na primeira iteração todos os vértices terão a mesma chance de serem
escolhidos.
O feromônio neste caso deixa de ser uma indicação do melhor caminho e passará a indicar
quais os melhores vértices a serem escolhidos para se tornarem medianas. Cada formiga então
efetua uma escolha, vai escolher uma solução para o problema, e a escolha de cinqüenta por cento
dos vértices candidatos a mediana para a solução foi realizada observando a probabilidade deste ser
escolhido de acordo com a quantidade de ferômonio existente no vértice, pois quanto mais
ferômonio o vértice possuir maior será a chance do mesmo ser escolhido para se tornar parte da
solução.
Após todas as formigas terem escolhido suas medianas, então foi realizado o cálculo para
ver quanto boa é cada solução encontrada. Com base nestas soluções a quantidade de ferômonio foi
depositada de acordo com a qualidade da solução, neste caso o ferômonio foi atualizado após o
ciclo completo de todas as formigas.
Após o ferômonio ser atualizado nos nós utilizados pelas formigas então foi realizada a
evaporação do ferômonio, a taxa de evaporação também foi ajustada e definida durante os testes.
Com isso é finalizada uma iteração. O processo iterativo é interrompido quando for atingido
o número máximo de iterações que é definido como parâmetro na inicialização do algoritmo.
A Figura 21 mostra o código principal do algoritmo.
38
void Formigas::Run(std::vector<Vertice*> &vVertices)
{
int i,j;
Formiga *f;
string duracao;
valorMelhorSolucao= 9999999999999999;
duracao=TimeToStr(Date().CurrentTime()).c_str();
for (i= 1; i<= nIteracoes; i++){
calculaFatia(vVertices);
for (j= 0; j<= lFormigas.NrElementos(); j++){
lFormigas.Enesimo(j,&f);
f->ExecutaBusca(vVertices,fatia);
}
for (j= 0; j<= lFormigas.NrElementos(); j++){
lFormigas.Enesimo(j,&f);
f->AtualizaFeromonio(vVertices);
if (f->GetFitnnes()< valorMelhorSolucao)
valorMelhorSolucao= f->GetFitness();
}
evaporarFeromonio(vVertices);
}
duracao= TimeToStr(Date().CurrentTime() - StrToTime(duracao.c_str())).c_str();
char tempo[20];
strcpy(tempo,duracao.c_str());
salvaMelhorSolucao(tempo);
}
Figura 21. Código principal algoritmo baseado em colônia de formigas.
3.2 Ensaios numéricos
Os ensaios numéricos são testes experimentais e foram conduzidos com base em um
problema fixo, o qual está em anexo (Anexo I). Nesta parte do trabalho buscou-se testar cada
algoritmo com diferentes configurações, pois são características especificas de cada método e os
mesmos devem ser ajustados sendo que todos os parâmetros têm influência direta no resultado dos
testes. A limitação a apenas um problema deu-se devido a grande bateria de testes que teve que ser
feita com cada algoritmo aplicado ao problema, inviabilizando testes com outros problemas.
Os testes foram realizados em massa, ou seja, foi definida uma configuração inicial para
cada algoritmo e foram realizados testes em massa com cada método, cem testes com cada
configuração para cada um foi gravado de forma automática o resultado em um arquivo para análise
posterior. Após os testes com uma determinada configuração os parâmetros foram ajustados
buscando encontrar melhores resultados, nem sempre isso foi possível, pois se percebeu que
encontrar uma configuração ideal para cada problema é uma tarefa difícil, pois pequenas alterações
em alguns parâmetros refletem em resultados ligeiramente diferentes. O grande desafio foi
identificar até que ponto cada parâmetro poderia ser ajustado.
Foi possível extrair um valor médio para a solução, o desvio padrão entre os testes, e
também o melhor resultado obtido dos cem testes realizados.
39
O número total de testes que estão documentados é de treze mil e novecentos. Sendo que
ainda antes do inicio dos mesmos foram realizados inúmeros testes a fim de validar os algoritmos e
encontrar uma configuração inicial para cada método.
A seguir serão apresentados os ensaios numéricos sendo os dados referentes aos gráficos
encontra-se no Apêndice A. Será apresentado como cada método foi testado, ajustado e os
resultados obtidos.
3.2.1
Ensaios realizados com o algoritmo genético
No algoritmo genético foi necessário o ajuste de quatro parâmetros: taxa de cruzamento,
taxa de mutação, e quantidade de gerações e também a população. Para cada configuração foram
realizados cem testes a fim de garantir resultados confiáveis. Os dados utilizados para a construção
dos gráficos estão disponibilizados no apêndice A. 1.1 bem como os tempos gastos na execução de
cada configuração.
Para o ajuste da taxa de cruzamentos foram realizados mil e quinhentos testes sendo que o
tamanho da população foi fixado e definido em testes preliminares e fixado em 164 indivíduos e o
número de mutações foi fixado em 1 mutação por geração a quantidade de iterações também foi
definida inicialmente com cem gerações. Pode-se observar que com uma taxa de cruzamento
pequena os resultados não eram adequados, porém a medida que se aproximou do de 105 (64%) os
resultados foram melhorando e a medida que se afastou deste valor o algoritmo tendeu a ficar mais
aleatório não convergindo para uma solução boa. O resultado do ajuste da taxa de cruzamento pode
ser visto na Figura 22.
40
Ajuste da quantidade de cruzamentos por
geração
Valor da função
23000
22000
21000
20000
19000
18000
20
30
40
50
60
70
80
90 100 103 105 107 110 120 130
Cruzamentos
Figura 22 Ajuste da taxa de cruzamento.
Após a definição da taxa de cruzamento foi realizado a ajuste da taxa de mutação onde
foram fixados os seguintes parâmetros: cem gerações, população de cento e sessenta e quatro
indivíduos, taxa de cruzamento fixa em aproximadamente sessenta e quatro por cento da
população. A Figura 23 mostra o ajuste da taxa de mutação onde é possível observar que a
quantidade de mutações ideal foi de sete mutações que equivale a aproximadamente quatro por
cento da população. É possível observar que taxas de mutação muito pequenas não ajudam o
algoritmo a sair de mínimos locai e que taxas de mutação elevadas tornam o algoritmo muito
aleatório dificultando a convergência do mesmo.
41
Valor da função
Ajuste da quantidade de mutações por
geração
20000
19900
19800
19700
19600
19500
19400
2
3
4
5
6
7
8
9
10
Figura 23 Ajuste da taxa de mutação.
A quantidade de gerações equivale ao número de iterações que o algoritmo terá e foi testada
e ajustada com a seguinte configuração: população de cento e sessenta e quatro indivíduos, taxa de
cruzamento fixa em aproximadamente sessenta e quatro por cento da população, e taxa de mutação
fixa em aproximadamente quatro por cento da população. Na Figura 24 pode-se observar que
quanto maior o número de gerações melhores são os resultados, pois os indivíduos da população
tornam-se melhores adaptados ao meio refletindo em soluções melhores.
Ajuste da quantidade de gerações
Valor da função
25000
24000
23000
22000
21000
20000
19000
18000
17000
16000
10
20
40
80
100
150
Figura 24. Ajuste da quantidade de gerações.
42
200
300
500
750 1000
Geração
Após definidos todos os parâmetros então foi ajustado o tamanho da geração sendo que a
taxa de cruzamentos, taxa de mutação e número de gerações já foi definido. A Figura 25 mostra
como quanto maior a população melhores são os resultados obtidos pois o espaço analisado é maior,
o número de cruzamentos, mutações cresce proporcionalmente de acordo com a população trazendo
assim resultados melhores.
Ajuste da população
Valor da função
20000
19500
19000
18500
18000
17500
17000
16500
16000
50
100
200
300
400
500
1000
População
Figura 25. Ajuste do tamanho da população.
A convergência do algoritmo pode ser observada na Figura 26, onde é possível verificar os
resultados obtidos nas gerações apresentadas.
Convergência do algoritmo
Valor da função
23000
22000
21000
20000
19000
18000
17000
16000
1
5
22
42
65
84
Figura 26. Convergência do algoritmo genético.
43
123
143
600
1000
Iteração
3.2.2 Ensaios realizados com o algoritmo simulated annealing
No algoritmo simulated annealing foi necessário o ajuste de três parâmetros: A temperatura
inicial e o decréscimo da temperatura a cada iteração e o número de iterações. Este algoritmo
mostrou-se bastante instável para o problema em questão, não convergindo para soluções boas. Isso
pode ter ocorrido pelo fato de o mesmo ser muito aleatório e o conjunto de possíveis soluções para
o problema ser extremamente grande. Os dados utilizados para a construção dos gráficos estão
disponibilizados no apêndice A. 1.3 bem como os tempos gastos na execução de cada configuração.
A Figura 27 mostra como foi difícil realizar o ajuste da temperatura num total de mil e
novecentos testes.
Ajuste da temperatura inicial
Valor da função
Resultados
28000
26000
24000
22000
20000
18000
15
00
°
12
00
°
85
0°
70
0°
57
5º
54
0º
50
0°
16000
Figura 27. Ajuste da temperatura inicial
Após o ajuste da temperatura inicial foi necessário o ajuste do resfriamento ou decréscimo
da temperatura. Com base nos testes anteriores a temperatura inicial foi fixada em 1200°. Para
encontrar a melhor configuração foram realizados mil e novecentos testes. A Figura 28 mostra
como foi realizado o ajuste. Percebe-se que o resfriamento que trouxe os melhores resultados foi
fixado em 5.8° sendo que pequenas variações nesta temperatura pioravam os resultados.
44
Ajuste do decréscimo de temperatura
Valor da função
28000
Resultados
27000
26000
25000
24000
23000
22000
21000
6.
5°
6.
0°
5.
8°
5.
0°
3.
5°
2.
0°
0.
5º
20000
Figura 28 Ajuste do decréscimo de temperatura.
Após definidos os parâmetros utilizados então foram realizados testes para ajustar o
número de iterações que os resultados estabilizam, foram feitos testes de dez a cem mil
iterações a Figura 29 mostra o resultado dos testes onde pode-se perceber que os melhores
resultados são obtidos quando o número de iterações é superior a cinqüenta mil iterações.
Ajuste do número de iterações
Valor da função
28000
27000
26000
25000
24000
23000
22000
21000
20000
19000
18000
10
00
25
00
50
00
10
00
0
20
00
0
50
00
0
10
00
00
50
0
30
0
20
0
10
0
40
20
10
Resultados
Figura 29. Ajuste do número de iterações simulated annealing.
45
A Figura 30 mostra com o algoritmo converge para a melhor solução.
Convergência do algoritmo
Valor da função
Resultados
24000
23000
22000
21000
20000
19000
18000
1
797
6483
26859
99673
100000
Iteração
Figura 30. Convergência do algoritmo Simulated Annealing.
3.2.3 Ensaios realizados com o algoritmo baseado em colônia de formigas
Para a utilização do algoritmo baseado em colônia de formigas foi necessário o ajuste de três
parâmetros: Quantidade de formigas, a quantidade de ferômonio a ser evaporada em cada iteração e
o número de iterações. Os dados utilizados para a construção dos gráficos estão disponibilizados no
apêndice A. 1.2 bem como os tempos de processamento gastos para cada configuração.
O ajuste da quantidade de formigas foi realizado com um número fixo de iterações de
duzentas iterações por teste e evaporação de ferômonio de 0.001 a cada iteração. A quantidade de
ferômonio inicial em todos os vértices foi igual a uma unidade. Estes valores iniciais foram
definidos em testes preliminares. A Figura 31 mostra que quanto maior o número de formigas
envolvido as chances de encontrar uma solução melhor aumenta, é importante salientar que quanto
maior o número de formigas utilizadas maior é o esforço computacional envolvido, nos testes foi
fixado um número máximo de cento e vinte formigas.
46
Ajuste da quantidade de formigas
Valor da função
20400
20200
20000
19800
19600
19400
19200
10
15
20
25
30
35
40
45
50
60
70
100 120
Figura 31. Ajuste da quantidade de formigas.
O ajuste da evaporação de ferômonio foi realizado com os seguintes parâmetros: cento e
vinte formigas, número fixo de iterações de duzentas iterações por teste. A quantidade de ferômonio
inicial em todos os vértices foi igual a uma unidade. Na Figura 32 é possível observar que o
decréscimo ideal de ferômonio é em torno de 0.005 unidades por iteração.
Valor da função
Ajuste do decréscimo de ferômonio
0.
5
9
8
7
6
0.
1
0.
0
0.
0
0.
0
0.
0
4
3
2
1
5
0.
0
0.
0
0.
0
0.
0
0.
0
09
07
0.
0
05
0.
0
04
0.
0
03
0.
0
0.
0
0.
0
02
20600
20400
20200
20000
19800
19600
19400
19200
19000
Figura 32. Ajuste da evaporação de ferômonio.
Após a configuração de todos os parâmetros foi testado o número de iterações necessário
para garantir os melhores resultado com a configuração encontrada. Pode-se observar que quanto
maior o número de iterações, melhores são os resultado encontrados sendo que houve uma certa
estabilidade após um número as quinhentas iterações, pois as melhorias encontradas não são
proporcionais ao número de iterações após este limite, e o esforço computacional aumenta a medida
47
que o número de iterações aumenta pois a cada iteração, as formigas realizam uma nova busca a
procura de uma solução. A Figura 33 mostra como o número de iterações influencia no resultado
final.
Ajuste da quantidade de iterações
Valor da
função
23000
22000
21000
20000
19000
18000
17000
10
20
30
40
50
60
70
80
90
100 150 300 600 1000
Figura 33. Ajuste da quantidade de iterações.
A Figura de número 34 mostra como o algoritmo converge utilizando os parâmetros
estabelecidos nos testes anteriores.
Valor da função
Convergência do algoritmo baseado em colônia de
formigas
25000
24000
23000
22000
21000
20000
Número de
19000
1
100
200
300
400
500
650
750
Figura 34. Convergência do algoritmo baseado em colônia de formigas.
48
850
950
iterações
3.2.4 Comparativo de resultados
Após a realização de cem testes com a melhor configuração encontrada em cada algoritmo
foi também feita a média dos testes onde se pode constatar que o algoritmo genético encontrou a
melhor solução, a qual é a menor soma das distancias entre as medianas e suas demandas. A Figura
35 mostra estes resultados. Os dados utilizados para a construção dos gráficos podem ser vistos no
apêndice A.
Analisando o desvio padrão dos testes realizados com a melhor configuração de cada
algoritmo constatou-se que o algoritmo baseado em colônia de formigas demonstrou maior
estabilidade apresentando um desvio médio de duzentos e sete unidades de medida. A Figura 35
mostra o comparativo entre os métodos.
Figura 35 Comparativo da média e desvio padrão entre os testes.
O melhor resultado dos cem testes realizados com a melhor configuração de cada algoritmo
também foi armazenado e se pode perceber que o algoritmo genético também apresentou o melhor
49
resultado para o problema seguido do algoritmo baseado em colônia de formigas, conforme pode
ser observado na Figura 36.
Melhores resultados
Valor da função
Resultados
20000
19000
18000
17000
16000
15000
Simulated
Formigas
Genético
Figura 36. Comparação em relação aos melhores resultados.
Os resultados obtidos neste estudo mostram que o três algoritmos abortados não podem ser
comparados em relação ao número de iterações, pois a complexidade algoritma de cada método é
diferente, a estrutura do algoritmo genético por exemplo é mais complexa que a estrutura do
algoritmo baseado em colônia de formigas que possui uma estrutura mais complexa que o algoritmo
simulated annealing.
Também percebeu-se que para este tipo de problema a melhor forma de analisar e comparar
um algoritmo é analisando os reais resultados que os mesmos oferecem, pois um problema de
localização não é um tipo de problema que necessita de uma resposta imediata.
E o melhor algoritmo realmente será o que trará o melhor resultado, pois o tempo de
processamento não é fator decisivo na escolha do método, pois quanto melhor a solução encontrada
melhor será a economia de recursos, tempo entre outros.
50
4 CONCLUSÕES
O trabalho apresentado é uma pesquisa sobre metaheuristicas utilizadas para a resolução de
problemas de p-medianas, este estudo foi realizado pesquisando em trabalhos anteriores, artigos e
publicações que tratavam da resolução de problemas localização e problemas combinatórios em
geral.
O objetivo deste trabalho foi de abordar apenas três métodos, porém em trabalhos mais
especificos pode-se detalhar e abortar uma única metaheuristica o que possibilitaria um
entendimento melhor da mesma, mas como a intensão é a comparação de três metaheuristicas foi
necessário descrever todas as metaheuristicas a serem utilizadas.
A escolha de aplicar as metaheurísticas a apenas um problema foi realizada porque no
decorrer das pesquisas percebeu-se que muitos dos trabalhos lidos em seus testes utilizavam dados
não reais, e maiores do que problemas reais, o que permite testar as metaheuristicas de uma forma
mais completa. Pois se as mesmas forem testadas com problemas viaveis pequenos a chance de
todas encontrarem o melhor resultado é grande e não seria possível avaliar a real diferênça de
performance entre as mesmas.
A grande bateria de testes realizados com os três métodos foi a parte do trabalho que mais
demorou para ser finalizada, pois para qualquer alteração em uma configuração de um algoritmo
foram realizados cem testes a fim de validar o resultado obtido, como cada algoritmo tem vários
parâmetros a serem ajustados e a medida que se aumentavam alguns parâmetros também o tempo
de processamento aumentava.
Os resultados obtidos nos testes mostram que o algoritmo genético tem grande vantagem em
relação os outros métodos estudados, trazendo as menores distâncias entre as medianas e suas
demandas. O algoritmo baseado em colônia de formigas também obteve bons resultados pois
poucos trabalhos até então aplicam este método a p-medianas, pode-se observar que o método pode
ser aplicado ao problema de p-medianas sem problemas.
O algoritmo simulated annealing em média se mostrou bastante instavel apresentando um
desvio padrão alto entre os testes, isso pode ser explicado devido a sua grande aleatoriedade fato o
qual garante que o mesmo não ficara preso a soluções ruins porém para encontrar bons resultados o
tempo de procesamento deve muito maior que os demais métodos.
4.1 Trabalhos futuros
Com a experiência obtida no desenvolvimento deste trabalho e o interesse despertado por
está área de estudo é importante salientar que bons trabalhos podem ser realizados nesta mesma
linha, porém aplicando um método e tratar um problema com um número maior de restrições o qual
tornaria o problema ainda mais difícil de ser tratado. A possibilidade de desenvolver um algoritmo
hibrido para a resolução de problemas semelhantes, como por exemplo, refinar ainda mais o
algoritmo genético dando a cada indivíduo de uma população um tempo máximo de vida, baseado
em um número fixo de gerações ou número máximo de filhos também pode ser uma ótima
oportunidade de desenvolvimento de trabalhos semelhantes a este. Estas pequenas adaptações
tornariam o algoritmo ainda mais próximo do observado na vida de uma população de indivíduos e
poderia trazer resultados ainda melhores a problemas combinatórios.
52
REFERÊNCIAS BIBLIOGRÁFICAS
ARAKAKI, R. G. I.; LORENA, L. A. N.Uma heurística de localização-alocação (HLA) para
problemas de localização de facilidades. Rev. Produção, São Paulo, v. 16, n. 2, p. 319-328, 2006.
ARAUJO, R. S. Uma Abordagem para o problema de corte guilhotinado bi-dimensional para
peças regulares com a utilização de p-medianas e pesquisa tabu. 2004. 72f. (Monografia,
bacharelado em informática) – Universidade do Vale do rio do Sinos, São Leopoldo, 2004.
BEZ, E.T. Procedimento de representação de soluções em otimização global: Aplicação em
modelos de interação espacial. 2005. 224f. Tese (Doutorado em engenharia de produção) –
Universidade Federal de Santa Catarina, Florianópolis, 2005.
BLUM, C; ROLI, A. Metaheuristics in combinatorial Opitimization: Overview and
Conceptual Comparison. Technical report TR/IRIDIA/2001-13, IRIDIA, Université Libre de
Bruxelles, Belgium, 2001.
BOECHEL, T. Algoritmo de otimização: Uma abordagem hibrida utilizando algoritmo das
formigas e genético.2003. 79f. Dissertação(Mestrado em ciência da computação) - Universidade
Federal de Santa Catarina, Florianópolis, 2003.
CAZANGI, R.R. Uma proposta evolutiva para controle inteligente em navegação autônoma de
robôs. 2004. 151f. Dissertação (Mestrado em engenharia elétrica) – Universidade Estadual de
Campinas – Campinas 2004.
COSTA FILHO, P.A. Algoritmo genético na seleção de variáveis em calibração multivariada
de dados espectroscópicos. 1998. 61f. Dissertação (Mestrado em química) – Universidade
Estadual de Campinas, Campinas 1998.
CORRÊA, D. Algoritmos Genéticos e Elementos Finitos na Síntese de Dispositivos Fotônicos.
2002. 78f. Dissertação (Mestrado em engenharia elétrica) - Universidade Estadual de Campinas –
Campinas, 2002.
CORRÊA, E. S. Algoritmos genéticos e busca tabu aplicados ao problema das p-medianas.
2000. 102f. Dissertação (Mestrado em métodos numéricos) – Universidade Federal do Paraná,
Curitiba, 2000.
DORIGO, M.; MANIEZZO, V.; COLORNI, A. The Ant System: Optimization by a colony of
cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics Part B:
Cybernetics, 26(1):29–41, 1996.
DORIGO, M.; MANIEZZO, V.; COLORNI, A. Positive Feedback as a Search Strategy.
Technical Report No. 91-016, Politecnico di Milano, Italy, 1991b.
DUCATI, E.A. Busca tabu aplicada ao problema de localização de facilidades com restrições
de capacidade. 2003. 71f. Dissertação (Mestrado em engenharia elétrica) - Universidade Estadual
de Campinas – Campinas, 2003.
FEO, T.A. e RESENDE, M. G. C. (1995) Greedy randomized adaptive search procedures. Journal
of GlobalOptimization, 6, 109-133.
FLEISCHFRESSER, S.A. Abordagem de um problema de entrega de jornais a assinantes por
métodos heurísticos e estatísticos. 2001. 96f. Dissertação(Mestrado em métodos numéricos) Universidade Federal do Paraná, Curitiba, 2001.
GAREY, M.R.; JOHNSON, D.S. Computers and intractability: a guide to the theory of
NPcompleteness, W. H. Freeman and Co., San Francisco, 1979.
GLOVER, F. Future paths for integer programming and links to artificial intelligence.Comp.
Operations Research, v.13, p.533-549, 1986.
GLOVER, F.; LAGUNA, M. Tabu search. Boston: Kluwer Academic Publishers, 1997. 408p.
GLOVER, F.; LAGUNA, M. Tabu search. In: COLIN, R. R. Modern heuristic techniques for
combinatorial problems. New York: McGraw-Hill, 1995. p.70-150.
GOMES, H. A. S. Utilização da metaheuristica simulated annealing no problema de alocação
de pessoal em empresas de transporte coletivo por ônibus. 2003.137f. Dissertação (Mestrado em
engenharia de transportes) – Universidade Federal do Ceará, Fortaleza 2003.
HOBSBAWM, E.J. A Era das Revoluções: Europa: 1789-1848. Trad. Port. Rio de Janeiro: Paz e
Terra, 1982.
HOLLAND, J. H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with
Applications to Biology, Control and Artificial Intelligence. Ann Arbor: University of Michigan
Press, 1975.
JUNGBECK, M. Implementação de controladores neurais de Kim-Lewis-Dawson com
parâmetros otimizados por algoritmos genéticos. 2001. 86f. Dissertação ( Mestrado) –
Universidade Estadual de Campinas, Campinas 2001.
KIRKPATRICK, S.; GELLAT JR., C.D.; VECCHI, M.P. Optimization by simulated annealing.
Science, v.220, n.4598, p.671-680, maio/1983.
LOBO D.S. Dimensionamento e Otimização locacional de unidades de educação infantil.2003.
155f. Tese (Doutorado em engenharia de produção) - Universidade Federal de Santa Catarina,
Florianópolis, 2003.
LORENA, L. A. N. Analise espacial de redes com aplicacoes em sistemas de informacoes
geograficas . Revista Produção Online, Florianópolis, v. 3, n. 2, 2003.
LORENA A. N.; ,SENNE E. L. F.; PAIVA J. A. C.; MARCONDES S. P. B. M. Integração de um
modelo de p-medianas a sistemas de informações geográficas - Instituto Nacional de Pesquisas
Espaciais - INPE/LAC Laboratório Associado de Computação e Matemática Aplicada São José dos
Campos, SP - Universidade Estadual Paulista - UNESP/FEG Faculdade de Engenharia,
Departamento de Matemática Guaratinguetá, SP.2002.
54
METROPOLIS, W.; ROSENBLUTH, A.; ROSENBLUTH, M.; TELLER, A.; TELLER,
E.Equation of state calculations by fast computing machines. Journal of chemical physics. v. 21,
n. 6, p. 1087-1092, Jun. 1953.
NORONHA, T. F. ; ALOISE,D. J. ; SILVA, M. M.Uma Abordagem sobre estratégias
metaheurísticas. REIC. Revista eletrônica de iniciação científica, http://www.sbc.org.br/reic, v. 1,
2001.
PEREIRA M.A. Um método Branch-and-Price para problemas de localização de p-medianas.
2005. 90f. Tese(Doutorado em computação aplicada) Instituto Nacional de Pesquisas Espaciais, São
José dos Campos, 2005
RICH, Elaine; KNIGHT, Kevin Inteligência Artificial. Makron Books. 2ª. Edição. São Paulo,
1994. 722p.
ROSA, A. A. Dimensionamento e localização de centro de distribuição de correios numa
cidade de médio porte. 1996. Dissertação ( Mestrado) - Universidade Federal de Santa Catarina,
Florianópolis, 1996.
ROSÁRIO,R.R.L.Proposta de Solução para o Problema das p-medianas na Localização de
Unidades de Saúde 24 horas. 2002. Dissertação (Mestrado) no Programa de Pós-Graduação em
Métodos Numéricos em Engenharia, UFPR,
2002.
SANTOS, J.C.; OLIVEIRA,J.R.F;DUTRA V.L. Uso de algoritmos Genéticos na seleção de
atributos para classificação de regiões. Instituto Nacional de Pesquisas Espaciais, São José dos
Campos,2006.
SILVA, E. O. A.; BENTES, C.; BAHIENSE, L.; CASTRO, C. S. Uma Abordagem Paralela
Baseada em Colônia de Formigas para o Problema do Caixeiro Viajante. Caderno do IME Vol.
18 : Julho de 2005.
SMIDERLE A., PIVA A.R., TIBES E. Estudo de caso da distribuição geográfica das unidades
farmacêuticas do município de Pato Branco. 2005. Artigo XXV Encontro Nac. de Eng. de
Produção – Porto Alegre, RS, Brasil, 29 out a 01 de Nov de 2005.
SOUZA, J.C. Dimensionamento, localização e escalonamento de serviços de atendimento
emergencial. 1996. 112f. Tese (Doutorado em engenharia de produção) – Universidade Federal de
Santa Catarina, Florianópolis, 1996.
TEITZ, M. B.; BART, P. Heuristics methods for estimating the generalized vertex median of a
weighted graph. Operations Research, v.16, p.955-961. 1968
SPECTRU Instrumental científico LTDA. Tratamento dos metais. Disponível em:
http://www.spectru.com.br/Metalurgia/diversos/tratamento.pdf . Acesso em: 26 abr. 2007.
VILELA, E. F. & DELLA LUCIA, T. M. C. Feromônios de insetos: biologia, química e emprego
no manejo de pragas. Viçosa, Imprensa Universitária. 155 p. 1987
55
GLOSSÁRIO
Branch-and-price
Uma abordagem de geração de colunas
Distância euclidiana
Distância em linha reta Distância em linha reta
Grafo conexo
) UmUm grafo G(V,A) é dito ser conexo se há pelo menos uma cadeia
ligando cada par de vértices deste grafo G.
Grafo não Orientado
Não existe orientação no grafo ou seja qualquer ligação é permitida
entre os vértices.
Heurisken
Encontrar
NP-Hard
Problema de difícil solução
Relaxação lagrangeana
Uma abordagem de geração de colunas
Simulated Annealing
Recozimento simulado
APÊNDICES
57
A ENSAIOS NUMÉRICOS
Nas tabelas que contém os resultados dos ensaios numéricos, cada linha da tabela representa
uma configuração diferente do algoritmo, e para cada linha foram realizados cem testes.
Os tempos contidos nas tabelas foram contabilizados utilizando um computador com CPU
AMD athlon 1.19 Mhz com 720 Mb de memória RAM.
A.1.1. Ensaios algoritmo genético
Tabela 1. Ensaios algoritmo genético
N° de
gerações
por teste
Tempo
por
teste
População
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
03 seg.
03 seg.
04 seg.
06 seg.
06 seg.
07 seg.
08 seg.
10 seg.
13 seg.
13 seg.
13 seg.
13 seg.
13 seg.
14 seg.
15 seg.
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
100
100
100
100
100
100
100
100
100
10
20
40
13 seg.
13 seg.
13 seg.
13 seg.
14 seg.
14 seg.
14 seg.
14 seg.
14 seg.
01 seg.
01 seg.
02 seg.
164
164
164
164
164
164
164
164
164
164
164
164
N° de
mutações
Nº de
cruzamentos
Média
Ajuste da quantidade de cruzamentos
1
20
22309.8419
1
30
21647.7525
1
40
20395.0728
1
50
20861.9511
1
60
20235.3891
1
70
19999.5123
1
80
20497.2412
1
90
19886.8288
1
100
19813.8345
1
103
20082.5578
1
105
19730.8260
1
107
19814.3248
1
110
19586.4116
1
120
19704.3226
1
130
19746.9677
Ajuste da quantidade de mutações
2
105
19852.7000
3
105
19719.5613
4
105
19729.1311
5
105
19774.5612
6
105
19656.1383
7
105
19629.9574
8
105
19805.1811
9
105
19806.7743
10
105
19897.7594
7
105
23458.9971
7
105
23248.0179
7
105
22319.4194
58
Desvio
padrão
Melhor
Resultado
1877.7938
1607.7124
1024.5244
1518.5277
1118.9061
912.8852
1242.5682
960.8411
1144.5075
969.5374
924.4588
748.4394
926.6385
1069.6165
847.7363
19339.7059
18936.0926
18274.3802
18020.9898
18039.9567
17999.2122
18302.5327
17835.8050
18010.8579
17931.2749
17856.0108
18008.4389
17817.7354
17658.6161
18141.5489
765.1864
1014.7997
1180.5076
921.5302
976.0942
935.1174
931.1480
1005.1184
963.7844
2623.6615
2523.7017
2145.9259
18376.8152
17920.5836
17925.6876
17872.5983
18124.7947
17925.3972
17895.7696
17927.6465
18036.2058
20569.7591
18693.7527
19311.8203
80
100
150
200
300
500
05 seg.
14 seg.
19 seg.
22 seg.
28 seg.
80 seg.
164
164
164
164
164
164
750
1000
100
100
100
100
100
100
100
123 seg.
157 seg.
5 seg.
23 seg.
45 seg.
78 seg.
103 seg.
120 seg.
185 seg.
164
164
50
100
200
300
400
500
1000
7
7
7
7
7
7
105
105
105
105
105
105
Ajuste da população
7
105
7
105
2
32
4
64
8
128
12
192
16
256
20
320
40
640
21216.8212
19629.9574
20064.2675
19671.1177
18973.2860
18393.3572
1370.9739
935.1174
1115.9105
938.0492
852.1851
505.1404
18224.3507
17925.3972
17859.0013
17898.3636
17406.5484
17240.9331
18073.7102
18211.7142
19438.3353
18121.9081
17915.2938
17680.8547
17609.3072
17619.3913
17405.0410
487.3739
508.8953
802.0742
418.0721
402.9325
385.8191
380.9521
351.8316
269.0747
16807.3589
17270.9677
17624.5961
17164.4059
17106.1404
16837.2113
16943.4384
16793.0419
16776.1689
A.1.2. Ensaios algoritmo baseado em colônia de formigas
Tabela 2. Ensaios algoritmo baseado em colônia de formigas
Número
de
iterações
por teste
Tempo
médio
200
200
200
200
200
200
200
200
200
200
200
200
200
01 seg.
01 seg.
02 seg.
02 seg.
03 seg.
03 seg.
04 seg.
04 seg.
05 seg.
05 seg.
06 seg.
07 seg.
09 seg.
200
200
200
200
200
200
09 seg.
09 seg.
09 seg.
09 seg.
09 seg.
09 seg.
Número de
formigas
utilizadas
Decrésci Média
mo do
ferômoni
o
Ajuste da quantidade de formigas
10
0.001
20007.8521
15
0.001
20331.9499
20
0.001
20142.9048
25
0.001
20011.8929
30
0.001
20148.3691
35
0.001
20003.2772
40
0.001
20322.0257
45
0.001
20161.7619
50
0.001
20210.1457
60
0.001
20241.3847
70
0.001
19980.6335
100
0.001
19961.2144
120
0.001
19591.9797
Ajuste da evaporação de ferômonio
120
0.002
19808.7932
120
0.003
19829.9162
120
0.004
19755.6158
120
0.005
19558.4858
120
0.007
19998.3358
120
0.009
20218.5159
59
Desvio
padrão
Melhor
Resultado em
Unidades de
medida
661.8263
533.0776
745.1365
592.6856
571.6717
591.8941
555.3209
496.3890
690.7933
551.7180
462.5873
385.7286
392.2400
18227.3223
19225.2188
18539.1992
18448.9883
18497.8926
18557.5234
18749.3203
18845.2070
18406.4141
18793.1797
19101.8535
19020.6758
17902.5645
438.9792
512.2212
382.6776
655.8785
670.2304
579.0480
18759.8887
18785.6230
18358.7305
18671.3809
18493.2793
18819.7812
200
200
200
200
200
200
200
200
200
200
200
09 seg.
09 seg.
09 seg.
09 seg.
09 seg.
09 seg.
09 seg.
09 seg.
09 seg.
09 seg.
09 seg.
10
20
30
40
50
60
70
80
90
100
150
300
600
1000
01 seg.
01 seg.
02 seg.
02 seg.
02 seg.
02 seg.
03 seg.
03 seg.
03 seg.
04 seg.
07 seg.
12 seg.
50 seg.
184 seg.
120
0.01
20421.0777
120
0.02
20227.5787
120
0.03
19937.1588
120
0.04
20111.3207
120
0.05
19636.1951
120
0.06
19742.4078
120
0.07
19801.2142
120
0.08
19792.7342
120
0.09
19856.6911
120
0.1
19868.6582
120
0.5
20000.5461
Ajuste do número de iterações
120
0.005
22240.7508
120
0.005
21654.6631
120
0.005
20744.4151
120
0.005
20909.0768
120
0.005
20704.4288
120
0.005
20621.7936
120
0.005
20609.8833
120
0.005
20751.1275
120
0.005
20727.2917
120
0.005
20787.3798
120
0.005
19967.1996
120
0.005
19233.6042
120
0.005
18893.5689
120
0.005
18874.8951
60
575.1043
575.1332
618.7731
575.8106
612.1550
417.4454
419.3741
448.0632
520.6373
499.9751
421.1158
19022.9609
18562.5762
18899.8281
18984.1191
18296.4844
18850.2461
18839.3301
18166.1875
18454.9883
18650.9141
18629.9297
2200.168
1058.040
1011.501
924.9336
903.3046
824.3889
873.4453
709.1773
651.1356
749.3440
532.1497
434.4622
462.4419
207.6702
17776.1699
19536.1699
18985.8965
18541.6621
18349.4102
18631.5723
18591.5391
19196.8477
18719.4180
18417.7617
18919.9688
18420.6719
18345.3398
18069.7012
A.1.3. Ensaios Simulated Annealing
Tabela 3. Ensaios Simulated Annealing
Tempo por
teste
Numero
de
iterações
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
Tempera
tura
inicial
Decréscimo
Média
da
temperatura
Ajuste da temperatura
500°
0.10°
23140.9739
550°
0.10°
22065.7792
525º
0.10°
24374.4277
540º
0.10°
25680.9279
550º
0.10°
24088.1433
560º
0.10°
23187.8361
575º
0.10°
22531.6872
600°
0.10°
24593.2798
650°
0.10°
24660.8431
700°
0.10°
27740.8965
750°
0.10°
23767.7706
800°
0.10°
26582.9399
850°
0.10°
24034.5084
900°
0.10°
24693.0104
1000º
0.10°
22169.5471
1200°
0.10°
21752.8718
1300°
0.10°
25742.3709
1400º
0.10°
23543.3392
1500°
0.10°
24950.4882
Ajuste do decréscimo da temperatura
1200°
0.5º
24533.2717
1200°
1.0°
23257.7797
1200°
1.5°
23687.5019
1200°
2.0°
23361.5361
1200°
2.5°
23198.3190
1200°
3.0°
24116.0943
1200°
3.5°
23206.0870
1200°
4.0°
23559.7201
1200°
4.5º
25987.3753
1200°
5.0°
22425.3501
1200°
5.5°
23859.1664
1200°
5.7°
24408.3620
1200°
5.8°
21762.3928
1200°
5.85°
23378.4535
1200°
5.9°
22012.3135
1200°
6.0°
21938.8980
1200°
6.1°
23950.5035
61
Desvio
padrão
Melhor
Resultado
1955.1086
1254.6620
1619.9444
1120.3050
3079.0881
2123.5084
3488.5840
3101.0286
1692.6208
4985.8013
1194.1690
10120.3119
3446.0982
916.3339
3838.6736
1220.8686
3499.4612
1037.9880
3449.6570
20092.9902
21264.3047
21264.0879
24378.9258
20871.5508
21550.9609
20113.9297
20889.7754
22030.5742
23803.3711
22134.4668
21878.3105
21324.4766
20829.3281
18641.8926
20584.5449
21165.1699
22173.0156
21698.2598
1077.6918
2630.0986
1734.1858
2434.0117
2437.5653
985.2717
2236.4972
2599.4609
2678.2675
1021.3644
2533.4996
2383.6503
2008.2425
2806.6895
2391.2368
1174.0602
2062.1990
23966.3379
20953.2988
22314.5312
20413.4824
19455.1172
23521.0273
21330.5215
21421.4258
22878.9844
21234.6660
21576.0195
20825.4062
20940.8770
20674.8711
19994.7969
20959.0957
21158.4902
01 seg.
01 seg.
200
200
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
01 seg.
02 seg.
4 seg.
11 seg.
21 seg
42 seg.
83 seg
184 seg.
10
20
40
100
200
300
500
1000
2500
5000
10000
20000
50000
100000
1200°
6.2°
23688.7464
1200°
6.5°
26572.2528
Ajuste do número de iterações
1200°
5.8°
23951.8111
1200°
5.8°
23491.4889
1200°
5.8°
27689.4667
1200°
5.8°
26223.3092
1200°
5.8°
21762.3928
1200°
5.8°
22312.3332
1200°
5.8°
21169.0770
1200°
5.8°
24815.1882
1200°
5.8°
24834.3158
1200°
5.8°
23160.0990
1200°
5.8°
21236.6997
1200°
5.8°
20419.3480
1200°
5.8°
19675.4514
1200°
5.8°
19496.3630
62
2876.7417
2179.3412
21571.9473
24456.6777
1711.14299
301.25388
8729.7592
1706.2199
2008.2425
1093.4948
350.93580
3053.5965
2172.9371
2248.4803
1219.1719
731.5850
615.7628
381.5908
21283.2910
23173.7480
21275.771
24514.1973
20940.8770
20414.1328
21061.6230
20294.7090
21826.0996
20313.6895
19500.4727
19506.9277
18690.0801
19078.4824
ANEXOS
63
I PROBLEMA
No problema utilizado nos testes cem representa o número de pontos de demandas, dez
representa o número de medianas a serem inseridas. Todos os pontos podem ser usados como
demandas ou medianas. Os outros dados são as coordenadas x e y a capacidade máxima de
atendimento daquele ponto e a demanda de atendimento do ponto.
100 10
409154
409151
409277
409260
409240
409213
409199
409178
409174
409147
409469
409378
409378
409351
409328
409275
409289
409272
409208
409754
409609
409565
409577
409515
409478
409442
409442
409408
409344
409398
409638
409683
409670
409620
409688
409624
409570
409541
409512
409216
435528
435683
435420
435538
435695
435897
435982
436078
436171
436256
435389
435463
435563
435734
435891
435982
436065
436188
436263
435326
435201
435307
435510
435614
435707
435810
435913
436075
436201
436213
435143
435349
435514
435615
435618
435752
435942
436090
436236
435826
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
50
4
33
15
1
5
87
91
45
1
41
23
26
301
53
1
80
118
1
1
15
12
60
35
138
1
173
61
1
21
8
18
35
17
22
60
65
54
39
1
64
409158
408777
408731
408808
408840
408932
408897
409050
409033
408906
409262
409090
409020
409262
409210
409109
409192
409298
409302
409264
409372
409426
409452
409553
409434
409479
409517
409539
409038
409167
408778
409411
409822
409811
409765
409812
409792
409837
409711
409969
409944
410041
409946
410015
410067
410073
410113
410204
409645
435820
434870
434657
434639
435022
434976
434650
434674
434769
434723
434873
434982
435056
435017
435093
435153
435244
435127
435225
435295
434355
434622
434831
435074
435030
434592
434818
434954
435235
435416
434739
434362
435466
435545
435617
435857
435978
436155
436281
435509
435714
435866
436015
436193
435592
436039
436329
436314
436119
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
1
5
115
30
98
61
79
8
193
4
654
63
22
283
150
153
20
10
13
3
19
444
54
25
21
13
19
26
90
105
73
3
1
46
28
160
1
65
152
1
61
102
49
43
1
48
27
6
49
65
410120
409875
410180
410244
410224
410435
409573
409575
409553
409546
409701
436189
435755
436398
436276
436222
436784
436533
436677
436813
436882
436391
720
720
720
720
720
720
720
720
720
720
720
27
19
33
1
1
37
49
54
30
12
34
66