Uma Comparação entre Operadores Geométricos e
Path-Relinking: Estudo de Caso dos Problemas DCMST,
OCST e QMST
Rodrigo Leite Durães
rodrigold@[Link]
Orientador: Oriane Magela Neto
Co-Orientador: Eduardo Gontijo Carrano
PPGEE
UFMG
30 de março de 2019
1 / 76
Sumário
1 Introdução
2 Problemas de Redes Utilizados
3 Controle Dimensional nos Problemas de Redes
4 Métrica T-norm
5 Desenvolvimento do Trabalho
6 Resultados
7 Conclusão
2 / 76
Sumário
1 Introdução
2 Problemas de Redes Utilizados
3 Controle Dimensional nos Problemas de Redes
4 Métrica T-norm
5 Desenvolvimento do Trabalho
6 Resultados
7 Conclusão
3 / 76
Introdução
A teoria dos grafos é um ramo da matemática que estuda as relações entre
os objetos de um determinado conjunto. Para tal são empregadas estruturas
chamadas de grafos, G(V,A), onde V é um conjunto não vazio de objetos
denominados vértices e A é um conjunto de pares não ordenados de V,
chamado arestas.
Estruturas que podem ser representadas por grafos estão em toda parte e
muitos problemas de interesse prático podem ser formulados como questões
sobre certos grafos.
Neste trabalho foi estudado problemas de redes que são representados como
árvores. Uma árvore é um grafo simples acı́clico e conexo.
4 / 76
Motivação
A idéia deste estudo é devido a Moraglio (2007) que formalizou o conceito
de operador geométrico. De acordo com Moraglio (2007), operadores
geométricos têm fortes conexões com a metaheurı́stica Path-Relinking.
No entanto, existem diferenças importantes entre o Path-Relinking e os
operadores geométricos.
5 / 76
Motivação
O Path-Relinking utiliza os valores da função objetivo para percorrer
a vizinhança, enquanto os operadores geométricos utilizam uma norma
associando o espaço de busca à geometria da vizinhança.
6 / 76
Motivação
Neste contexto, a hipótese que este trabalho pretende comprovar é a
seguinte:
É plausı́vel que o fato dos operadores geométricos utilizarem uma
norma para percorrer a vizinhança, produza melhores soluções que o
Path-Relinking, que utiliza os valores da função objetivo para
percorrer a vizinhança.
7 / 76
Objetivo
Este trabalho tem como objetivo comparar quantitativa e qualitativamente
os operadores geométricos e o Path-Relinking na resolução de problemas
combinatórios.
8 / 76
Justificativa
Para a comparação entre operadores geométricos e Path-Relinking, faz-se
necessário:
Escolher os problemas a serem utilizados: DCMST, OCST e QMST.
Definir o espaço de busca a ser utilizado: espaço completo e
Controlled-Greedy Encoding.
Definir a norma a ser utilizada: T-norm.
Definir os algoritmos utilizados: GRASP e algoritmo genético.
9 / 76
Etapas Concluı́das do Trabalho
Para alcançar o objetivo proposto, foram percorridos os seguintes passos:
Revisão da literatura: Foi feita uma revisão bibliográfica sobre
DCMST, OCST, QMST, GRASP, algoritmo genético, Path-Relinking,
operadores geométricos e Controlled-Greedy Encoding.
Estado da Arte: Realização de um estudo abrangente à respeito dos
trabalhos de otimização de redes que se assemelham a este trabalho.
Definição das redes e os algoritmos utilizados: Escolha das redes
e os algoritmos utilizados neste estudo.
Resultados: Apresentação das tabelas e gráficos dos resultados
encontrados para as instâncias estudadas e o seu respectivo problema.
Análise dos Resultados da Pesquisa e Discussão: Análise e
avaliação dos resultados obtidos.
10 / 76
Sumário
1 Introdução
2 Problemas de Redes Utilizados
3 Controle Dimensional nos Problemas de Redes
4 Métrica T-norm
5 Desenvolvimento do Trabalho
6 Resultados
7 Conclusão
11 / 76
Degree-Constrained Minimum Spanning Tree (DCMST)
Seja G (V , E ) um grafo conexo com |V | vértices e |E | arestas, e ci,j é o
custo associado a cada aresta (i, j ). A solução do DCMST sobre G é o
subgrafo árvore geradora de custo mı́nimo de tal modo que para cada nó i,
o grau di está entre um limite inferior Li e um limite superior Ui .
12 / 76
Degree-Constrained Minimum Spanning Tree (DCMST)
X ∗ = arg minx ∑ xi,j · ci,j (1)
i,j∈V
sujeito a:
X ⊆E
∑j∈V xi,j = |V | − 1 , ∀i ∈ V
xi,j ∈ {0, 1} , ∀i, j ∈ V
∑j∈V xi,j ≤ Ui , ∀i ∈ V
em que X é o conjunto de arcos ativos ((i, j ) ∈ X se xi,j = 1).
13 / 76
Degree-Constrained Minimum Spanning Tree (DCMST)
C = ωa é o custo da aresta a entre os vértices (i, j ).
sendo ωi,j ∈ W o peso associado à aresta que conecta o par de vértices
(i, j ).
14 / 76
Optimal Communication Spanning Tree (OCST)
O problema de encontrar a OCST consiste na busca da árvore geradora
de custo mı́nimo que satisfaz os requisitos de comunicação conhecidos
anteriormente entre os pares de vértices do grafo. O problema tem a seguinte
formulação:
x é o peso acumulado do
Ri é a demanda por comunicação entre (i, j ) e Ci,j
caminho (i, j ) em T .
T ∗ = arg minT ∑ X
Ri,j · Ci,j (2)
i,j∈V
15 / 76
Optimal Communication Spanning Tree (OCST)
C = R1,2 ωa é o custo da aresta a entre os vértices (1, 2).
16 / 76
Quadratic Minimum Spanning Tree (QMST)
O problema de encontrar a árvore mı́nima quadrática, consiste na busca
de árvore geradora que minimiza uma função quadrática, que depende dos
pesos das arestas e a interação entre eles. O problema apresenta a seguinte
formulação:
k,l
ωi,j é o peso induzido na aresta (i, j ) pela aresta (k, l ).
!
T ∗ = arg minT ∑ ∑ k,l
ωi,j · ti,j · tk,l + ωi,j · ti,j (3)
i,j∈V k,l∈V
no qual:
ta,b é 1 se a aresta (i, j ) está presente na rede ou 0 caso contrário.
17 / 76
Quadratic Minimum Spanning Tree (QMST)
C = ωa é o custo da aresta a entre os vértices (i, j ).
18 / 76
Sumário
1 Introdução
2 Problemas de Redes Utilizados
3 Controle Dimensional nos Problemas de Redes
4 Métrica T-norm
5 Desenvolvimento do Trabalho
6 Resultados
7 Conclusão
19 / 76
Espaço Completo
No espaço completo o número de conexões possı́veis em um problema de
rede (ou codificação) cresce de forma quadrática com o número de nós.
Este comportamento faz com que a solução direta de problemas de médio e
grande porte apresente alto custo computacional, devido ao elevado número
de variáveis a considerar, ainda que um conhecimento a priori do problema a
ser tratado possa ser aplicado para reduzir o número de conexões possı́veis.
20 / 76
Controlled-Greedy Encoding
Para contornar a dificuldade de fazer a codificação do problema de rede,
tornando este processo automático, foi utilizada a técnica Controlled-Greedy
Enconding de redução dimensional da codificação do problema. O resultado
da aplicação desta técnica é um número muito menor de variáveis do que o
obtido para a codificação completa.
21 / 76
Controlled-Greedy Encoding
A construção do Controlled-Greedy Enconding foi inspirado em algoritmos
gulosos, cuja idéia básica é conectar cada nó ao nó mais próximo, o que
geralmente leva a ótimos locais. Para evitar isso, tentou-se controlar a gula
do algoritmo usando dois parâmetros:
mnv: número mı́nimo de nós em que cada nó pode se conectar;
mxv: número máximo de nós em que cada nó pode se conectar.
22 / 76
Controlled-Greedy Encoding
Para determinar o número de conexões de cada nó é determinado primeiro
a distância média de cada nó i (di ) usando:
1 n
di = dist (i, j ) (4)
n j∑
=1
23 / 76
Controlled-Greedy Encoding
Assim, o número de conexões permissı́veis para cada nó i (nci ) pode ser
determinado usando:
mnv − mxv
nci = · (di + dmin ) + mxv (5)
dmax − dmin
no qual:
dmin = min(d )
dmax = max (d )
24 / 76
Controlled-Greedy Encoding
Figura: Número de conexões vs. distância média.
25 / 76
Sumário
1 Introdução
2 Problemas de Redes Utilizados
3 Controle Dimensional nos Problemas de Redes
4 Métrica T-norm
5 Desenvolvimento do Trabalho
6 Resultados
7 Conclusão
26 / 76
O Conceito de Distância no Espaço de Redes
N é qualquer rede que pode ser representada em um grafo G (V , A) sendo
|V | = n e |A| = m, com tc tipos de conexões. N pode ser representado
→
−
como um vetor N no espaço Rm :
m
→
−
N = ∑ (ωiN · pn1 + Ni · ωiN · pn2 ) · →
−
ei (6)
i =1
27 / 76
O Conceito de Distância no Espaço de Redes
no qual:
ωiN é o peso da conexão i na rede N;
Ni é o tipo de ramo da conexão i na rede N;
Pn1 é o fator de penalidade 1;
Pn2 é o fator de penalidade 2;
→
−
ei é i-ésimo vetor da base canônica do espaço Rm .
28 / 76
O Conceito de Distância no Espaço de Redes
Sejam as redes NA e NB . O vetor posição relativa entre NA e NB é uma
consequência direta desta representação vetorial de redes, como mostrado
em:
m
−−→
NAB = ∑ [(ωiA − ωiB ) · pn1 + (Ai · ωiA − Bi · ωiB ) · pn2 ] · →
−
ei (7)
i =1
29 / 76
Sumário
1 Introdução
2 Problemas de Redes Utilizados
3 Controle Dimensional nos Problemas de Redes
4 Métrica T-norm
5 Desenvolvimento do Trabalho
6 Resultados
7 Conclusão
30 / 76
Questões centrais
Como representar os indivı́duos?
Como definir a função objetivo?
Como construir a vizinhança?
Quais são os critérios de seleção?
Como aplicar/definir os operadores?
31 / 76
Algoritmo Genético
Executar a inicialização:
1 Gerar a população inicial com o procedimento usando Kruskal,
algoritmo para pesos aleatórios. Todos são garantidos para ser viável;
2 Avaliar a função objetivo de cada indivı́duo;
3 Atribuir o valor de avaliação para cada indivı́duo, com um ranking
linear.
32 / 76
Algoritmo Genético
Enquanto não atingir critério de parada
Executar as operações binárias:
1 Ordenar aos pares a população (de forma aleatória, com distribuição
uniforme de probabilidade)
2 Para cada par de indivı́duos:
a) Se rbin ≤ pbin então
Executar o cruzamento escolhido: Path-Relinking, Golden Section ou
Quadratically-Biased.
Executar as operações unárias:
3 Para cada indivı́duo:
a) Se run ≤ pun então
Escolher entre a mutação 1 e mutação 2, com distribuição uniforme
de probabilidade, e executar a operação escolhida.
33 / 76
Algoritmo Genético
Realizar a avaliação da função e a seleção:
4 Avaliar a função objetivo para cada novo indivı́duo gerado;
5 Atribuir o valor de avaliação para cada indivı́duo da população, com
um ranking linear;
6 Realizar a seleção usando a amostragem universal estocástica;
fim enquanto
1 Executar a busca local ao redor do melhor indivı́duo encontrado pelo
algoritmo genético, procurando uma melhor solução.
34 / 76
GRASP
1 Construir a solução;
2 Enquanto critério de parada não satisfeito faça
a) Executar a busca local;
b) Executar o operador escolhido: Path-Relinking, Golden Section ou
Quadratically-Biased;
c) Avaliar a função objetivo para cada novo indivı́duo gerado;
d) Se a nova rede tem um melhor valor de função objetivo do que a
anterior, então redefinir o centro da vizinhança para esta rede.
35 / 76
GRASP
A etapa de construção do algoritmo pode ser de dois tipos: construção
gulosa e construção semi-gulosa. A função de construção gulosa segue os
seguintes passos:
1 Definir elementos candidatos;
2 Aplicar uma função de avaliação a cada elemento candidato;
3 Ordenar elementos de acordo com a função de avaliação;
4 Adicionar melhor elemento;
36 / 76
GRASP
A função de construção semi-gulosa do algoritmo segue os seguintes passos:
1 Definir elementos candidatos;
2 Aplicar uma função de avaliação a cada elemento candidato;
3 Ordenar elementos de acordo com a função de avaliação;
4 Colocar elementos melhor classificados em uma LRC;
5 Adicionar um elemento da LRC escolhido aleatoriamente à solução.
37 / 76
GRASP
A construção da LRC tem as seguintes caracterı́sticas:
Cardinalidade: incluir os k melhores elementos na LRC;
Valor da função de avaliação: incluir todos os elementos que possuem
valor de função de avaliação abaixo de um limiar:
e ∈ C : g (e ) ≤ g (emin ) + α [g (emax ) − g (emin )]
α = 0: a LRC é formada apenas por emin (melhor elemento de cada
iteração) e a construção torna-se determinı́stica e puramente gulosa;
α = 1: a LRC é formada por todos os elementos de C e a construção
é totalmente aleatória;
α 6= 0 e α 6= 1: a construção é semi-gulosa.
38 / 76
Path-Relinking
1 Considera-se um par de soluções (xs , xt ), sendo uma delas
considerada a solução de partida, chamada solução corrente, e a outra
a solução guia.
2 Enquanto xs 6= xt faça
a) Realizar um movimento que torne a solução x mais próxima de xt . No
qual, x é a solução corrente;
b) Atribuir a x ∗ a melhor solução obtida aplicando o melhor movimento.
No qual, x ∗ é a melhor solução obtida;
c) Excluir o movimento aplicado;
d) Avaliar a função objetivo do novo indivı́duo gerado;
e) Se a nova rede tem um melhor valor de função objetivo do que a
anterior, então redefinir o centro da vizinhança para esta rede;
3 Executar a busca local sobre x ∗ .
39 / 76
Método Golden Section
1 Entradas: as redes P1 e P2 , são escolhidas aleatoriamente com uma
distribuição uniforme de probabilidade.
→
− −
→ −−−→
2 Uma rede resultante é gerada S1 = P1 + r · (P1 , P2 ) usando o
procedimento de interpolação de linha.
3 Uma segunda rede resultante S2 é gerada no segmento (P1 , P2 ),
usando o seguinte procedimento de busca:
40 / 76
Método Golden Section
1 Criar duas redes Ax e Bx que são idênticas a P1 e P2 ,
respectivamente.
2 Usar o procedimento de interpolação de linha para encontrar uma
−
→ − → −−−→
rede PA tal que PA ≈ Ax + α · (Ax , Bx ).
3 Usar o procedimento para encontrar um rede PB tal que
−
→ − → −−−→
PB ≈ Ax + (1 − α ) · (Ax , Bx ).
4 Avaliar o valor da função objetivo nas redes f (PA ) e f (PB ).
41 / 76
Método Golden Section
−−−−→ −−→
5 Enquanto k(PA , PB )k/ k (A, B ) k≥ ε faça
a) Se f (PA ) > f (PB ) então:
42 / 76
Método Golden Section
b) Caso contrário:
43 / 76
Método Golden Section
Depois de um número de avaliações de função sem melhoria, o método
Golden Section é usado para melhorar as soluções encontradas, neste caso,
o mesmo é executado da seguinte maneira:
1 Entradas: uma rede pai P, escolhida aleatoriamente com distribuição
uniforme de probabilidade, e uma rede viável P ∗ que tem o melhor
valor de avaliação.
2 A busca de linha com o procedimento de busca descrito acima é
−−−→
empregado para encontrar a melhor rede dentro do segmento (P, P ∗ ).
Se a melhor rede é diferente de P ∗ , é entregue como uma prole da
operação de cruzamento.
44 / 76
Operador Quadratically-Biased
1 Entradas: as redes P1 e P2 , são escolhidas aleatoriamente com uma
distribuição uniforme de probabilidade. Admitindo (sem perda de
generalidade) que f (P1 ) < f (P2 ).
→
− −→ −−−→
2 Duas redes descendentes são geradas como S1 = P1 + r1 · r2 · (P1 , P2 )
→
− −
→ −−−→
e S2 = P1 + r3 · (P1 , P2 ), usando o procedimento de interpolação de
→
−
linha. Observa-se que a prole S1 tem uma distribuição quadrática de
probabilidade que é tendenciosa para a melhor rede P1 .
45 / 76
Prova de Teste
46 / 76
Prova de Teste
47 / 76
Prova de Teste
48 / 76
Prova de Teste
49 / 76
Sumário
1 Introdução
2 Problemas de Redes Utilizados
3 Controle Dimensional nos Problemas de Redes
4 Métrica T-norm
5 Desenvolvimento do Trabalho
6 Resultados
7 Conclusão
50 / 76
Resultados
Foram realizados testes para redes de 50 nós para os problemas OCST,
QMST e DCMST; e 100 nós para o DCMST, para as redes com 50 nós
o total de avaliações de função é 50000, e para as redes de 100 nós o
total é 100000 avaliações de função, o número de execuções é 10 para cada
algoritmo, a população é inicial é de 10 indivı́duos para cada algoritmo.
51 / 76
Resultados
As redes de 50 nós possuem 1225 variáveis no espaço completo e 249
variáveis no Controlled-Greedy Enconding para o DCMST e 247 variáveis
no Controlled-Greedy Enconding para o OCST e QMST, as rede de
100 nós possuem 4950 variáveis no espaço completo e 497 variáveis no
Controlled-Greedy Enconding.
52 / 76
Resultados
Tabela: Mı́nimo encontrado utilizando GRASP e espaço completo.
53 / 76
Resultados
Tabela: Mı́nimo encontrado utilizando GRASP e CGE.
54 / 76
Resultados
Tabela: Mı́nimo encontrado utilizando algoritmo genético e espaço completo.
55 / 76
Resultados
Tabela: Mı́nimo encontrado utilizando algoritmo genético e CGE.
56 / 76
Resultados
Tabela: Operadores que encontraram o melhor mı́nimo.
57 / 76
Resultados
De posse de todos estes resultados apresentados nas tabelas acima, nota-se
que a variação entre os algoritmos e os seus métodos é pequena, e uma vez
que em vários casos houveram empates, é necessário outros mecanismos
que mostrem o comportamento de cada método em cada algoritmo. Desta
forma, o gráfico de comportamento médio da curva foi escolhido para esta
tarefa.
58 / 76
Resultados
7 OCST50
x 10
Path Relinking
2.2
Quadratically−Biased
Golden Section
1.8
Best
1.6
1.4
1.2
0 5000 10000 15000
Evals
Figura: OCST50 utilizando GRASP e espaço completo.
59 / 76
Resultados
7 OCST50
x 10
1.5
Path Relinking
Quadratically−Biased
1.45
Golden Section
1.4
1.35
1.3
Best
1.25
1.2
1.15
1.1
1.05
0 2000 4000 6000 8000 10000 12000
Evals
Figura: OCST50 utilizando GRASP e CGE.
60 / 76
Resultados
É interessante saber qual espaço apresentou o melhor desempenho, portanto,
a figura abaixo mostra o comportamento médio do GRASP com o método
Quadratically-Biased para os dois espaços utilizados.
61 / 76
Resultados
7 OCST50
x 10
1.7
full
cgreedy
1.6
1.5
Best
1.4
1.3
1.2
1.1
0 1000 2000 3000 4000 5000 6000
Evals
Figura: OCST50 utilizando GRASP.
62 / 76
Resultados
7 OCST50
x 10
5
Path Relinking
Quadratically−Biased
4.5
Golden Section
3.5
Best
2.5
1.5
1
0 1 2 3 4 5 6
Evals x 10
4
Figura: OCST50 utilizando algoritmo genético e espaço completo.
63 / 76
Resultados
7 OCST50
x 10
2.4
Path Relinking
Quadratically−Biased
2.2 Golden Section
1.8
Best
1.6
1.4
1.2
1
0 1 2 3 4 5
Evals x 10
4
Figura: OCST50 utilizando algoritmo genético e CGE.
64 / 76
Resultados
7 OCST50
x 10
5
full
cgreedy
4.5
3.5
Best
2.5
1.5
1
0 1 2 3 4 5
Evals x 10
4
Figura: OCST50 utilizando algoritmo genético.
65 / 76
Resultados
Os resultados das tabelas e figuras mostram que os operadores geométricos
convergem mais rápido que o Path-Relinking, para o mı́nimo da função
de custo na maioria das instâncias utilizadas nos problemas estudados.
Assim sendo, os operadores geométricos propostos mostraram-se eficientes,
eficazes e efetivos.
66 / 76
Sumário
1 Introdução
2 Problemas de Redes Utilizados
3 Controle Dimensional nos Problemas de Redes
4 Métrica T-norm
5 Desenvolvimento do Trabalho
6 Resultados
7 Conclusão
67 / 76
Conclusão
Este estudo comparou quantitativa e qualitativamente os operadores
geométricos e o Path-Relinking na resolução dos problemas combinatórios
propostos.
68 / 76
Conclusão
Os resultados observados para as instâncias consideradas sugerem que os
operadores propostos para o GRASP e o algoritmo genético são adequados
para lidar com os problemas DCMST, OCST e QMST, e ainda podem ser
aplicados em instâncias maiores destes problemas.
69 / 76
Conclusão
Os resultados encontrados mostram que os operadores geométricos são mais
velozes que o Path-Relinking, na convergência para o mı́nimo da função de
custo na maioria das instâncias utilizadas nos problemas estudados. Este
fato leva à conclusão, que é plausı́vel que nos problemas estudados, o uso da
norma pelos operadores geométricos para percorrer a vizinhança, produza
melhores soluções que o Path-Relinking, que utiliza os valores da função
objetivo para percorrer a vizinhança. Como neste trabalho foram utilizadas
as instâncias com 50 e 100 nós, resta saber como é o comportamento destes
operadores para instâncias maiores.
70 / 76
Trabalhos Futuros
Aplicação dos algoritmos em instâncias maiores dos problemas
estudados.
Neste trabalho foram utilizadas instâncias com 50 e 100 nós, há a
possibilidade de se utilizar instâncias de 200 a 1000 nós no problema
DCMST.
71 / 76
Trabalhos Futuros
Aplicação dos algoritmos ILS e VNS.
As soluções podem convergir prematuramente devido à variação da
dimensão do espaço, assim sendo, os algoritmos ILS (Iterated Local Search)
e VNS (Variable Neighborhood Search) podem ser utilizados a fim de
explorar a vizinhança.
72 / 76
Trabalhos Futuros
Utilização de técnicas estatı́sticas para fundamentar a comparação
entre o Path-Relinking e os operadores geométricos.
Aqui será utilizado um planejamento e análise de experimentos.
73 / 76
Trabalhos Futuros
Migração dos códigos fontes para outra linguagem de programação.
Atualmente a linguagem utilizada é o Matlab, entretanto, o mesmo despende
muita memória RAM e tempo de processamento. Para sanar esse problema
foi escolhida a linguagem C # (C Sharp).
74 / 76
Referências I
Eduardo Gontijo Carrano.
Algoritmos Evolucionários Eficientes para Otimização de Redes.
Tese, PPGEE - UFMG, Belo Horizonte, Minas Gerais, Brazil, Agosto
2007.
Eduardo Gontijo Carrano, Ricardo Hiroshi Caldeira Takahashi, Carlos M.
Fonseca, and Oriane Magela Neto.
Nonlinear network optimization - an embedding vector space
approach.
IEEE Transactions on Evolutionary Computation, 14(2), April 2010.
Alberto Moraglio.
Towards a Geometric Unification of Evolutionary Algorithms.
PhD thesis, University of Essex, November 2007.
75 / 76
Referências II
Tiago L. Pereira, Eduardo Gontijo Carrano, Ricardo Hiroshi Caldeira
Takahashi, Elizabeth Fialho Wanner, and Oriane Magela Neto.
Continuous-space embedding genetic algorithm applied to the degree
constrained minimum spanning tree problem.
IEEE Congress on Evolutionary Computation (CEC 2009), 2009.
76 / 76
Agradecimentos
Ao Conselho Nacional de Desenvolvimento Cientı́fico (CNPq) pelo apoio
financeiro.
Ao Laboratório de Otimização e Pesquisa Assistido por Computador
(LOPAC) pelo apoio e infra-estrutura fornecidos.
Aos professores e colegas do Grupo de Otimizao e Pesquisa Assistido por
Computador - GOPAC.
Agradeço direção, coordenação e funcionários do Programa de
Pós-Graduação em Engenharia Elétrica (PPGEE).
À Universidade Federal de Minas Gerais (UFMG) por participar, da minha
formação acadêmica e pessoal.
77 / 76