Metaheurísticas

A linguagem de referência é o Julia. Você pode encontrar instruções de instalação e uso neste link.

• Pacote TSPLIB.jl: instâncias da biblioteca TSPLIB (problema do caixeiro viajante) prontas em Julia site. Veja tópico “O problema do caixeiro viajante” para detalhes.
• tspplot.jl: código para plotar instâncias da TSPLIB
• tsp.jl: funções para manipulação de instâncias da TSPLIB e heurística do vizinho mais próximo
• funcoes-teste.jl: funções para teste (para Differential Evolution e Particle Swarm Optimization)

• SLIDES

O problema do problema do caixeiro viajante (em inglês, Travelling Salesman Problem - TSP) serve como “saco de pancadas” para testarmos as implementações. O TSP é simples de entender, portanto não requer conhecimento profundo para começar a testar as metaheurísticas. Além disso, é um problema clássico e de difícil resolução.

• Uma apresentação do TSP
• Slides de M.A.M. Carvalho (UFOP)
• Instâncias para testes - Biblioteca TSPLIB
  • As instâncias que utilizaremos são de “TSP simétrico”, isto é, o custo $c_{ij}$ para ir da cidade $i$ à cidade $j$ é o mesmo que da volta $j$ para $i$. Isso fornece uma matriz de custos simétrica, daí o nome.
  • Na TSPLIB você encontrará outros tipos de instâncias, como as que servem para problemas de roteamento de veículos com capacidade nos arcos. Não as usaremos neste curso!
  • IMPORTANTE: para termos foco, vamos considerar apenas instâncias cujo custo entre cidades é a distância Euclideana entre elas. Para saber se uma instância tsp proveniente do pacote TSPLIB.jl é deste tipo, verifique se tsp.weight_type é “EUC_2D”
  • Lista de todas as instâncias da TSPLIB cujo custo é a distância euclideana
  • Por curiosidade, as referências oficiais da TSPLIB são este artigo e arquivos originais
• Visualização on line do funcionamento de algoritmos para o TSP.

A geração de números randômicos em computador é um tópico pesquisado até hoje. Os principais algoritmos utilizados geram números “pseudo-randômicos”, chamados assim por não serem verdadeiramente randômicos (os números se repetem em ciclos). Este não é um tópico central nessa disciplina, mas vale o comentário. No contexto das metaheurísticas, onde temos que gerar muitos números, é interessante utilizarmos bons geradores.

Cada linguagem adota um gerador como padrão. Por exemplo, o Python 3 adota o Mersenne Twister, um gerador proposto por M. Matsumoto e N. Makoto em 1998. Esse algoritmo é bastante utilizado e gera números com qualidade melhor comparados ao gerador padrão do C. No Julia, Mersenne Twister é implementado no pacote Random.jl.

O Julia (versão 1.8), por sua vez, utiliza como padrão um excelente gerador, mais moderno, conhecido como Xoshiro256++. Esse gerador foi proposto por D. Blackman e S. Vigna em 2018, é rápido e apresenta excelentes resultados em testes de qualidade. Assim, todas as chamadas de funções que retornam valores aleatórios (rand, randperm etc) usam este gerador por padrão (a menos que o usuário diga para usar outro gerador, claro). Os códigos apresentados nessa disciplina utilizam Xoshiro256++.

Para saber mais sobre geradores de número pseudo-aleatórios, consulte este link. Uma lista de diferentes geradores pode ser vista neste link.

• SLIDES
• Tarefa computacional: veja último slide do link acima
• Referência: capítulo 2 de Glover, Kochenberger – Handbook of Metaheuristics. Kluwer, 2003

• SLIDES
• Tarefa computacional: veja último slide do link acima
• Seleção por roleta - SLIDES
• Referência: capítulo 10 de Glover, Kochenberger – Handbook of Metaheuristics. Kluwer, 2003

• SLIDES
• Tarefa computacional: veja último slide do link acima
• Seleção por roleta - SLIDES
• Referências:
  1. Dorigo, Gambardella. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1:53-66, 1997 Link1 (acesso pela universidade) Link2
  2. Dorigo, Caro. Ant colony optimization: a new meta-heuristic. Proceedings of the 1999 Congress on Evolutionary Computation, 2002 Link1 (acesso pela universidade) Link2
  3. Capítulo 9 de Glover, Kochenberger – Handbook of Metaheuristics. Kluwer, 2003

• Código versão 1

• SLIDES
• Tarefa computacional: veja último slide do link acima
• funcoes-teste.jl: código Julia de funções para teste (descrição nas referências 1 e 2)
• Referências:
  1. Storn, Price. Differential Evolution - A Simple and Efficient Heuristic for global Optimization over Continuous Spaces. Journal of Global Optimization, 11:341-359, 1997 Link (acesso pela universidade)
  2. Feoktistov, Vitaliy. Differential Evolution - In Search of Solutions, Springer, 2006 Link (acesso pela universidade)
  3. Brandão, Saramago. Métodos estocásticos de otimização: algoritmos genéticos e evolução diferencial, SBMAC, 2011 Link

• SLIDES
• Tarefa computacional: veja último slide do link acima
• funcoes-teste.jl: código Julia de funções para teste
• Referências:
  1. Kennedy, Eberhart, Shi. Swarm Intelligence. Morgan Kaufmann, 2001 Link
  2. Shi, Eberhart. A modified particle swarm optimizer. 1998 IEEE International Conference on Evolutionary Computation Proceedings, 1998 Link

• SLIDES
• Tarefa computacional: veja último slide do link acima
• Seleção por roleta - SLIDES
• Referências:
  1. Capítulo 5 de Gendreau, Michel, Potvin, Jean-Yves (Eds.) – Handbook of Metaheuristics. Springer, 2019
  2. Hussain, Muhammad, Sajid, Hussain, Shoukry, Gani. Genetic Algorithm for Traveling Salesman Problem with Modified Cycle Crossover Operator. Computational Intelligence and Neuroscience, 2017 Link
  3. Slides de Estéfane G. M. de Lacerda (UFRN), 2008/2009
  4. Capítulo 2 de Lopes, Rodrigues, Steiner (Eds.) – Meta-heurísticas em Pesquisa Operacional. Omnipax, 2013 Link 1; Link 2

• SLIDES
• Tarefa computacional: veja último slide do link acima
• Seleção por roleta - SLIDES
• Referências:
  1. capítulo 8 de Glover, Kochenberger – Handbook of Metaheuristics. Kluwer, 2003
  2. E.F. Goldbarg, M.C. Goldbarg, J.P.F. Farias. Grasp with Path-Relinking for the TSP. Em: Doerner, Gendreau, Greistorfer, Gutjahr, Hartl, Reimann. (eds) Metaheuristics. Operations Research/Computer Science Interfaces Series, vol 39. Springer, 2007 Link

• Rashedi, Nezamabadi-pour, Saryazdi. GSA: A Gravitational Search Algorithm. Information Sciences, 179(13):2232-2248, 2009
• Para minimização de funções a variáveis contínuas
• Presente no pacote Metaheuristics.jl

• Mejía-de-Dios, Mezura-Montes. A New Evolutionary Optimization Method Based on Center of Mass. In: Deep, K., Jain, M., Salhi, S. (eds) Decision Science in Action. Asset Analytics. Springer, Singapore, 2019
• Para minimização de funções a variáveis contínuas
• Presente no pacote Metaheuristics.jl

ATIVIDADE para a semana entre 27/03 e 31/03, a ser discutida entre todos na aula do dia 06/04

Pesquise metaheurísticas na internet/artigos. Para cada metaheurística encontrada, faça uma descrição contendo:

• A inspiração (fenômeno físico, natural, animal etc)
• Em qual(is) problema(s) foi aplicada, evidenciando se o problema é de otimização contínua (variáveis todas contínuas) ou combinatória
• Uma descrição sucinta do funcionamento do algoritmo
• Não esqueça de indicar a referência da qual retirou as informações!

1. Instale o Julia (caso não instalado)
2. Instale o pacote TSPLIB.jl
3. Carregue a instância berlin52 e teste a função de tspplot obtida neste link
4. Implemente a função de custo (distância euclideana do percurso)
5. Implemente a busca gulosa pelo vizinho mais próximo (Nearest Neighbor search – NN). Veja detalhes neste link
6. Plote soluções obtidas por NN e compare com o valor ótimo (gravado em tsp.optimal)
7. Implementar a heurística 2-OPT. Veja detalhes neste link. Use NN para inicializar. Comparar solução com anteriores.

Serão avaliadas as implementações de todas as metaheurísticas apresentadas durante a disciplina. Cada aluno será “entrevistado” individualmente, onde mostrará ao professor o que fez, executará testes e responderá à eventuais perguntas. Não é necessário fazer slides para uma apresentação, a conversa será feita em frente ao computador. No entanto, o(a) estudante deverá organizar o roteiro de sua fala, testes que apresentará, dificuldades enfrentadas etc.

• Nota máxima: 10,0 pontos
• Período das avaliações: 15 e 16 de junho

Critérios considerados na avaliação:

• Profundidade, clareza e organização da apresentação;
• Domínio do assunto;
• Coerência dos testes numéricos.

Apresentação de um artigo selecionado. Cada estaudante escolherá um artigo e fará uma apresentação explicando:

• o problema estudado, sua aplicação;
• a metodologia de resolução (metaheurística usada/adaptada pelo(s) autore(s));
• detalhes da representação dos dados;
• detalhes do funcionamento do algoritmo;
• discussão dos testes numéricos apresentados.

O(A) estudante pode escolher um artigo da lista sugerida abaixo ou um artigo de sua preferência. No último caso, o artigo dependerá do aval do professor.

Critérios de pontuação da apresentação:

• Qualidade da apresentação (slides, material digital ou impresso…)
• Organização das ideias e sequência lógica do assunto
• Domínio do assunto
• Postura, naturalidade, dinamismo e interação diante da plateia
• Uso de linguagem apropriada; uso correto da língua portuguesa
• Clareza e dicção
• Adequação ao tempo pré-determinado

Critérios de avaliação:

• Cada apresentação receberá nota de 0 a 10, seguindo os pontos elencados acima;
• O trabalho pode ser individual ou em dupla;
• As apresentações deverão ser em dia e horário das aulas;
• O tempo máximo de cada apresentação é de 1h;
• Período das apresentações: duas últimas semanas de 2023/1

Artigos sugeridos:

A Hybrid Grouping Genetic Algorithm for the Multiple-Type Access Node Location Problem
O. Alonso-Garrido, S. Salcedo-Sanz, L.E. Agustín-Blas, E.G. Ortiz-García, A.M. Pérez-Bellido, J.A. Portilla-Figueras.

A simple and robust Simulated Annealing algorithm for scheduling workover rigs on onshore oil fields
G.M. Ribeiro, G.R. Mauri, L.A.N. Lorena

A simple and effective genetic algorithm for the two-stage capacitated facility location problem
D.R.M. Fernandes, C. Rocha, D. Aloise, G.M. Ribeiro, E.M. Santos, A. Silva

A greedy randomized adaptive search procedure for the point-feature cartographic label placement
G.L. Cravo, G.M. Ribeiro, L.A.N. Lorena

Simulated annealing and tabu search approaches for the Corridor Allocation Problem
H. Ahonen, A.G.de Alvarenga, A.R.S. Amaral

A Biased Random-Key Genetic Algorithm for the Traffic Counting Location Problem
G. Clímaco, P.H. Gonzalez, G.M. Ribeiro, G.R. Mauri, L. Simonetti

Four-bar Mechanism Synthesis for n Desired Path Points Using Simulated Annealing
H. Martínez-Alfaro

Dynamic Load Balancing Using an Ant Colony Approach in Micro-cellular Mobile Communications Systems
S.-S. Kim, A.E. Smith, S.-J. Hong

Tabu Search Heuristic for Point-Feature Cartographic Label Placement
M. Yamamoto, G. Camara, L.A.N. Lorena

A GRASP algorithm for solving large-scale single row facility layout problems
G.L. Cravo, A.R.S. Amaral

Single row facility layout problem using a permutation-based genetic algorithm
D. Datta, A.R.S. Amaral, J.R. Figueira

Coevolutionary Genetic Algorithm to Solve Economic Dispatch
M.M.A. Samed, M.A.S.S. Ravagnani

GSA: A Gravitational Search Algorithm
Rashedi, Nezamabadi-pour, Saryazdi

A New Evolutionary Optimization Method Based on Center of Mass
Mejía-de-Dios, Mezura-Montes