Metaheurísticas

Horários das aulas

Ementa

Consulte Projeto Pedagógico do Curso.

Objetivos da disciplina

Estudar as principais (meta)heurísticas usadas para resolver problemas de otimização contínua e combinatória
Aplicar as técnicas em problemas conhecidos da literatura e encontrados na indústria
Na medida do possível, estudar e reproduzir testes computacionais de artigos científicos sobre o tema, publicados em periódicos

Conteúdo

Principais metaheurísticas usadas na literatura recente (algoritmos genéticos, simulated annealing, busca tabu, colônia de formigas, outras metaheurísticas bio-inspiradas, GRASP, dentre outras).

Referências principais

Obs: outras referências são descritas em cada tópico

Formas de avaliação

Serão aplicadas no mínimo duas avaliações, dentre testes dissertativos, apresentações de seminários e/ou desenvolvimento de projetos.

Cálculo da média parcial (2023/1)

(1,0(atividade avaliativa 1) + 6,0(atividade avaliativa 2) + 3,0(atividade avaliativa 3)) / 10,0

Critérios para aprovação

Faltas acima de 25% da carga horária —> reprovado(a) por falta
Média parcial >= 7,0 —> aprovado(a) (desde que não reprovado(a) por falta)
Média parcial < 7,0 —> Avaliação final (desde que não reprovado(a) por falta). Neste caso, média final >= 5,0 —> aprovado(a)

MATERIAIS PARA AS AULAS

Linguagem de programação

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

Para auxiliá-lo na instalação do Julia pré-compilado + pré-requisitos + pacotes utilizados, baixe ESTE SCRIPT e siga as instruções contidas nele (testado no Ubuntu 22.04)

Pacotes e códigos em Julia

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)

Apresentação

SLIDES

O problema do caixeiro viajante (Travelling Salesman Problem - TSP)

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.

Sobre geradores de números randômicos

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.

METAHEURÍSTICA 1: Busca Tabu (Tabu Search - TS)

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

METAHEURÍSTICA 2: Simulated Annealing (SA)

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

METAHEURÍSTICA 3: Colônia de formigas (Ant Colony Optimization - ACO)

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

DICAS PARA CALIBRAÇÃO DE PARÂMETROS

Código versão 1

METAHEURÍSTICA 4: Evolução Diferencial (Differential Evolution - DE)

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

METAHEURÍSTICA 5: Nuvem de partículas (Particle Swarm Optimization - PSO)

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

METAHEURÍSTICA 6: Algoritmo Genético (Genetic Algorithm - GA)

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

METAHEURÍSTICA 7: GRASP (Greedy Randomized Adaptive Search Procedure)

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

Pacotes de terceiros

Pacote Metaheuristics.jl: implementação em Julia de várias metaheurísticas. Site.

OUTRAS METAHEURÍSTICAS

Gravitational Search Algorithm

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

Evolutionary Centers Algorithm

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

Leitura(s) recomendada(s)

Análise de Sörensen sobre a profusão de artigos nos últimos anos e seu rigor científico
Uma versão com acesso aberto está disponível neste link.

Materiais de terceiros

ATIVIDADES PROPOSTAS (2023/1)

Atividade 1

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!

Atividade 2

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

Atividade 3

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.

Atividade 4

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: