Heurística Matemática Aplicada ao Problema da Coloração de

Heurística Matemática Aplicada ao Problema da Coloração de Grafos

MARIANE REGINA AFONSO VIEIRA

ORIENTADOR: GEORGE HENRIQUE GODIM DA FONSECA

Sumário1. Introdução

2. Objetivos

3. Metodologia

4. Fundamentação Teórica

5. Revisão Bibliográfica

6. Desenvolvimento

7. Solução Inicial

8. Heurísticas de Refinamento

9. Experimentos Computacionais

10. Conclusão

2

• O que é um grafo?

UNIVERSIDADE FEDERAL DE OURO PRETO

Fonte – (Feofiloff, 2017)

Introdução

3

Mapa do Metrô da cidade de Barcelona

Fonte – (UFSC, 2002)

UNIVERSIDADE FEDERAL DE OURO PRETO 4

• A Teoria dos Grafos

• 1736 – Problema das Pontes de Konigsberg – Prússia XVIII

• Leonard Euler

Fonte – (DALLAQUA, 2016)


Introdução

• Problema da Coloração de Grafos

Fonte – (Meidanis, 2012)

6UNIVERSIDADE FEDERAL DE OURO PRETO 6

Introdução

Introdução

• Francis Guthrie – Problema das quatro cores

• Kempe, 1879 e Peter Guthrie Tait, 1880

• Percy John Heawood, 1890

• Julius Peter Christian Petersen, 1891

• Hapel e Akken, 1976

Qualquer grafo planar é 4-colorível!

7UNIVERSIDADE FEDERAL DE OURO PRETO

• O problema vai mais além...


Fonte – (Zilderlânio, 2015)

Introdução

• Problema NP-Dificil

• Técnicas pensadas para encontrar a melhor solução possível.

• Várias aplicações

• Agendamento de horários educacionais

• Alocações de registradores

• Planejamento de tráfego aéreo


Introdução


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Mat.

Por.

Ingl.

Geog.

Hist.

Física

Química

Biologia

Introdução


Fonte – (Andrade, 2014)

Introdução

Objetivos

• Estudar e desenvolver uma heurística matemática baseada

em decomposição;

• Realizar um levantamento bibliográfico das melhores estratégias

computacionais para solucionar o problema;

• Propor a primeira heurística matemática para a Coloração de Grafos;

• Analisar a viabilidade e o comportamento do algoritmo para grafos

oriundos de várias aplicações.


Metodologia

• Instâncias: DIMACS Implementation Challenge

• Etapas:

• Revisão da Literatura;

• Reprodução do algoritmo D-Satur;

• Desenvolvimento de formulação de programação matemática;

• Implementação da heurística matemática;

• Implementação da meta-heurística;

• Avaliação computacional das técnicas desenvolvidas;

• Análise.


• Programação linear

• Otimizar problemas de decisão;

• Programação Linear Inteira

• Variáveis discretas;


Fundamentação Teórica

• Heurísticas

• Heurísticas construtivas;

• Heurísticas de refinamento;

• Meta-heurísticas

• Heurísticas matemáticas


Fundamentação Teórica

◦ Algoritmos para o problema de coloração de grafos – Rego, M. F.; Santos, H. G.

◦ Solving the graph coloring problem via hybrid genetic algorithms – Douiri, S. M.; Elbernoussi, S.

◦ New approximation algorithms for solving graph coloring problem – An experimental approach –

Marappan, R.; Sethumadhavan, G.; Srihari, R.

◦ Desenvolvimento de meta-heurística baseada em simulated annealing aplicado a coloração de

grafos para otimização de processos – Macedo, H. R; Lima, H. H. d. C.; Tolentino, C. H. C.

◦ New graph coloring algorithms –Al-Omari, H; Sabri, K. E.

◦ Modelagem matemática e aplicações do problema de coloração em grafos – Lozano, D.


Revisão Bibliográfica

• Formulação matemática

◦ 𝐺 = 𝑉, 𝐸

◦ 𝑉 = 1,… , 𝑛

◦ 𝐸 = { 𝑣1, 𝑣2 , … }

◦ 𝐶 = 1,… ,𝑚


Desenvolvimento


• Variáveis


Desenvolvimento


• Função objetivo


Desenvolvimento


◦ Restrições


Desenvolvimento

• Algoritmo Guloso


Solução Inicial

2 5

1

3

4

6 7

1 2 3 4 5 6 7 4 cores!

• Algoritmo D-Satur


Solução Inicial

2 5

1

3

4

6 7

1 2 4 5 6 7 3

D = 3

d = 0

D = 2

d = 0

D = 3

d = 0

D = 3

d = 0

D = 3

d = 0

D = 3

d = 0

D = 3

d = 0

D grau

d grau de saturação



Solução Inicial

2 5

1

3

4

6 7

1 2 4 3 5 6 7

D = 2

d = 1

D = 3

d = 1

D = 3

d = 1

D = 3

d = 0

D = 3

d = 0

D = 3

d = 0

D grau




Solução Inicial

2 5

1

3

4

6 7

1 2 3 4 5 6 7

D = 2

d = 2

D = 3

d = 1

D = 3

d = 1

D = 3

d = 0

D = 3

d = 0

D = 3

d = 1

D grau




Solução Inicial

2 5

1

3

4

6 7

1 2 3 4 5 6 7

D = 2

d = 2

D = 3

d = 1

D = 3

d = 1

D = 3

d = 0

D = 3

d = 0

D = 3

d = 1

D grau




Solução Inicial

2 5

1

3

4

6 7

1 2 3 4 5 6 7

D = 2

d = 2

D = 3

d = 1

D = 3

d = 1

D = 3

d = 1

D = 3

d = 1

D = 3

d = 1

D grau




Solução Inicial

2 5

1

3

4

6 7

1 2 3 4 5 6 7

D = 2

d = 2

D = 3

d = 1

D = 3

d = 1

D = 3

d = 2

D = 3

d = 2

D = 3

d = 1

D grau




Solução Inicial

2 5

1

3

4

6 7

1 2 3 4 5 6 7

D = 2

d = 2

D = 3

d = 1

D = 3

d = 1

D = 3

d = 2

D = 3

d = 3

D = 3

d = 1

D grau


4 cores!

• Heurística Simples - recol


Heurísticas de refinamento

2 5

1

3

4

6 7

Vértice 5 recebe cor 1








• Meta-heurística – Simulated Annealing

• Gerar um vizinho qualquer;

• Calcular ;

• Custo simples

• 𝑛𝑢𝑚𝑉𝑒𝑟𝑡𝑖𝑐𝑒𝑠 ∗ 𝑛𝑢𝑚𝐶𝑜𝑟𝑒𝑠𝑆 +𝑚𝑖𝑛

• Probabilidade de aceitar a nova solução

• 𝑥 < 𝑒−Δ

𝑇

• Resfria



2 5

1

3

4

6 7

D

𝑚𝑖𝑛 = frequencia da cor menos utilizada

• Heurística matemática – mipHeuristic

• Sorteia as cores a serem desafixadas;



2 5

1

3

4

6 7

Vértice 2 pode receber a cor 4





2 5

1

3

4

6 7







2 5

1

3

4

6 7








2 5

1

3

4

6 7







• Deixou de utilizar 1 cor

• 3 cores!



2 5

1

3

4

6 7





• Ambiente computacional

• Notebook PC HP ENVY 17 – 64 bits.

• Intel Core™ i7-4710HQ CPU @ 2.50GHZ, 2501 Mhz. 4

cores e 8 processadores lógicos. Memória RAM: 12 GB

• Microsoft Windows 10 Home

• Implementação em Java – NetBeans IDE 8.2

• Gurobi Optimizer


Experimentos Computacionais

36

• Caracterização das Instâncias

• DIMACS Implementation Challenge

• Grafos divididos em 2 tabelas

• Vértices, arestas e densidade do grafo



37

• Planejamento Experimental

• Tempo de execução das heurísticas de refinamento

• Fatores e níveis

• 𝐺𝐴𝑃 =𝑠′−𝑠∗

𝑠′

• Simulated Aneealing: α = 0.4 / 𝑇0 = 50 / 𝑆𝐴𝑚𝑎𝑥 = 50

• mipHeuristic: color_percent = 0.2



38

• Resultados

• Geração da solução inicial



39

Grafo greedycol 𝑻𝒈𝒓𝒆𝒆𝒅𝒚𝒄𝒐𝒍 D-Satur 𝑻𝑫−𝑺𝒂𝒕𝒖𝒓

queen5_5 8 0 5 28

queen6_6 11 6 9 54

queen7_7 10 10 11 56

queen8_8 13 24 12 61

queen9_9 16 17 13 67

• Resultados

• mipHeuristic



40

Grafo s* Exp1 Exp2 Exp3 Exp4 Exp5 𝒔𝒎𝒊𝒏 𝒔𝒎𝒂𝒙 𝒔𝒎é𝒅𝒊𝒐 GAP

queen5_5 5* 5 5 5 5 5 5 5 5,00 0,00

queen6_6 7* 7 7 7 7 7 7 7 7,00 0,00

queen7_7 7* 7 7 7 7 7 7 7 7,00 0,00

queen8_8 9* 10 9 9 9 10 9 10 9,40 0,00

queen9_9 10* 11 11 11 11 10 10 11 10,80 0,00

• Resultados

• Comparação com a literatura – Douiri e Elbernoussi



41

Grafo s* 𝒔𝑫&𝑬 𝑮𝑨𝑷𝑫&𝑬 𝒔𝒎𝒊𝒑𝑯𝒆𝒖𝒓𝒊𝒔𝒕𝒊𝒄 𝐆𝐀𝐏𝐦𝐢𝐩𝐇𝐞𝐮𝐫𝐢𝐬𝐭𝐢𝐜

queen5_5 5* 5 0,00 5 0,00

queen6_6 7* 7 0,00 7 0,00

queen7_7 7* 7 0,00 9 0,00

queen8_8 9* 9 0,00 10 0,00

queen9_9 10* 10 0,00 11 0,00

• Análise dos resultados

• Trabalhos futuros

• Conclusão


Conclusão

42

• DOUIRI, S. M.; ELBERNOUSSI, S. Solving the graph coloring problem viahybrid genetic algorithms. Journal of King Saud University-Engineering Sciences,Elsevier, v. 27, n. 1, p. 114–118, 2015.

• DALLAQUA, C. Origem da Teoria dos Grafos – As 7 Pontes de Konigsberg. 2016. Disponível em: <https://universoracionalista.org/ origem-da-teoria-dos-grafos-as-7-pontes-de-konigsberg/>.

• Feofiloff, P. Componentes aresta-biconexas. 2017. Disponível em: <https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/edge-biconnected.html >.

• UFSC. Problema do metrô. 2002. Disponível em: <http://www.inf.ufsc.br/grafos/problemas/metro/metro.htm>.

• Meidanis, J. MC558 – Prova P2. 2012. Disponível em: <http://www.ic.unicamp.br/~meidanis/courses/mc558/2012s2/P2/>.


Referências

43

• Zilderlânio. Contribuição dos Grafos. 2015. Disponível em:

<http://integradorp3.wixsite.com/arquitetura/single-

post/2015/10/20/CONTRIBUI%C3%87%C3%83O-DOS-GRAFOS-

Zilderl%C3%A2nio >.

• Andrade, Ana. Coloração. 2014. Disponível em:

<https://slideplayer.com.br/slide/292978/#>.


Referências

44

Documents

Heurística Matemática Aplicada ao Problema da Coloração de