Rodrigo de Carvalho


Introdução
◦
Descrição do Problema
Algoritmos
◦
GRASP
◦
S.A
◦
AG
Planejamento Experimental

◦
◦
◦
◦


Objetivo
Instância e métricas
Design experimental
Teste estatístico
Análise Experimental
Conclusões
MANUTENÇÂO:
Sistemas legados
Falta de documentação

Clusterização de grafos direcionados e não ponderados.

Particionar um grafo em subgrafos, de forma que o número de
arestas entre pares de vértices em subgrafos distintos seja
minimizado, bem como, o número de arestas internas a cada
subgrafo seja maximizado.


N = 10  115.975
N = 15  1.382.958.545

GRASP
proc grasp (MAX_ITER, α, s*)
enquanto critério de parada não satisfeito
S = constrói_Solução (α)
S = buscaLocal ()
se (f(s*) < f(S)) entao s* <- S
fim enquanto
retorna (Melhor_Solução)
fim grasp

Simulated Annealing
proc Simulated Annealing
Enquanto T > Tmin
s = gerar um vizinho qualquer s’
se(f(s) > f(s’)) então s’  s
senão s’  s com probabilidade e^-delta/T
T  Atualiza Temperatura
fim para
retorna (Melhor_Solução)
fim grasp

AG
proc AG
Criar população
Avaliar população
enquanto critério de parada não satisfeito
Selecionar indivíduos
Cruzamento e Mutação
Avaliar população
fim enquanto
retorna (Melhor_Solução)
fim grasp

Verificar a existência de diferença significativa no desempenho dos
algoritmos quando aplicados ao problema de clusterização em
grafos (modularização de software).

12 instâncias
◦ 10 a 100 nós
◦ 30 a 1200 arestas

MQ - Qualidade de Modularização (Dovall et
al.,1999)
◦ Esta medida leva em consideração a quantidade de arcos internos
interligando vértices em um mesmo cluster, denominada
intraconectividade, e a quantidade de arcos interligando vértices
entre clusters diferentes, denominada interconectividade (Bi j).
◦ Hipótese:
 H0: os algoritmos não apresentam diferença no desempenho quando aplicados ao
problema estudado;
◦ Fator: Algoritmo
 Níveis: GRASP,Simulated Annealing, AG.
◦ Blocos: por instância;
◦ Replicações: 10.
◦ Região de rejeição: Consiste em todos os valores da estatística do teste
utilizado ,tais que sua probabilidade de ocorrência , sob H0, não supere α
= 0,05 (nível de significância) .

Teste de Friedman
◦ Planejamento em blocos com único fator;
◦ Uma alternativa robusta onde não é possível afirmar/justificar sobre a
normalidade dos dados; (Teste não paramétrico);
◦ Para aplicar o teste calcula-se o valor de uma estatística χ02;
◦ Quando se tem uma amostra relativamente grande é possível mostrar que
χ02 tem uma distribuição aproximadamente qui-quadrada com k-1 gl.

Algoritmos implementados na linguagem C++;

Testes realizados em um computador com:
◦ Intel Core i3 2.3 GHz;
◦ 4 Gb RAM;
◦ Windows 7.

Para cada replicação foi dado um tempo aproximado de 40
segundos de processamento.

Algoritmo x instância x replicação
◦ 3 x 12 x 10 = 360 valores
◦ 60 valores ignorados


Para teste de hipótese realizado foi considerado um nível de
confiança de 95% ( α = 0,05);
O valor crítico: 5,991
procedimento de comparação múltipla


O teste realizado indica a existência de diferença
estatisticamente significativa quanto ao desempenho dos
algoritmos avaliados;
Baseado na média dos ranks e no intervalo de confiança pode
ser perceber que o método GRASP é promissor para resolver
esse problema.



DOVAL, D., MANCORIDIS, S. E MITCHELL, B. S., “Automatic Clustering
of Software System using a Genetic Algorithm”. Proc. Of the Int.
Conf. On Software Tool and Enginnering Practice, pp 73-81,1999.
DIAS, C.R. Desenvolvimento e Análise Experimental de Algoritmos
Evolutivos para o Problema de Clusterização Automática em Grafos
Orientados , Univ. UFF,2004, Dissertação de Mestrado.
D. C. Montgomery e G. C. Runger. Applied statistics and probability
for engineers. John Wiley, 3 edição, 2003.