1

Tópicos em Métodos Heurísticos

ANÁLISE EMPÍRICA DE HEURÍSTICAS

ANÁLISE DE DESEMPENHO DE HEURÍSTICAS BASEADA EM RESULTADOS DE

EXPERIMENTOS COMPUTACIONAIS.

Enquanto a análise de pior caso e a análise probabilística de heurísticas são

realizadas de maneira científica, análises empíricas são feitas muitas vezes de forma

subjetiva e sem princípios estabelecidos.

Entretanto...

Existem critérios válidos para comparação de algoritmos heurísticos além da

qualidade da solução os quais não devem ser ignorados (Ball & Magazine, 1981):

TEMPO DE EXECUÇÃO

Geralmente crucial para escolha entre abordagens

FACILIDADE DE IMPLEMENTAÇÃO

Algoritmos difíceis de serem implementados que requerem quantidades

substanciais de tempo computacional podem não valer a pena caso a qualidade

de suas soluções supere apenas de forma marginal um algoritmo fácil de

codificar e extremamente eficiente

FLEXIBILIDADE

Habilidade de um algoritmo lidar com variações de problemas. Uma heurística

que pode resolver apenas certa classe de um problema não é tão flexível quanto

uma heurística que pode resolver duas ou mais classes

SIMPLICIDADE

Algoritmos simples são mais atraentes ao usuário do que um algoritmo

complicado, e se permitem a uma variedade de análises.

2

MÉTODOS ESTATÍSTICOS PARA COMPARAÇÃO DE HEURÍSTICAS

Pressupõem que as instâncias teste formam uma amostragem significativa da

classe de instâncias que as heurísticas se propõem a resolver.

Apesar de impossível de ser validada, esta premissa mostra a importância da

escolha de um conjunto apropriado de instâncias teste (para o TSP, TSPLIB95).

Exemplo: Suponha que três heurísticas (X, Y e Z) foram aplicadas a 15 instâncias

do TSP, para as quais se conhecem limitantes inferiores razoáveis (LB) dos valores das

soluções ótimas. QUAL DAS TRÊS HEURÍSTICAS É A MAIS PRECISA?

Resultados das heurísticas

Instância L B X Y Z

Custo Custo/LB Compr. Custo/LB Compr. Custo/LB

1 310 316 1.02 326 1.05 331 1.07

2 339 367 1.08 367 1.08 418 1.23

3 275 289 1.05 291 1.06 313 1.14

4 274 320 1.17 290 1.06 350 1.28

5 370 417 1.13 383 1.04 475 1.28

6 295 316 1.07 324 1.10 356 1.21

7 312 357 1.14 325 1.04 355 1.14

8 144 171 1.19 164 1.14 186 1.29

9 150 172 1.15 162 1.08 194 1.29

10 258 416 1.61 356 1.40 407 1.58

11 253 355 1.40 339 1.34 364 1.44

12 275 302 1.10 302 1.10 364 1.32

13 395 424 1.07 430 1.09 501 1.27

14 424 560 1.32 564 1.33 655 1.54

15 544 592 1.09 560 1.03 560 1.03

3

Através da compilação de estatísticas, procura-se identificar a heurística que

domina as outras ou aquela que chega mais perto de dominar as outras.

Comparação do desempenho das heurísticas

Medidas de Precisão X Y Z

Número de vezes que a heurística é melhor ou empatada com a

melhor

7 10 1

Porcentagem média acima do limitante

inferior

17,29 12,74 27,41

Classificação média entre as três heurísticas

1,8 1,43 2,77

Pior razão da solução e limitante inferior

1,61 1,40 1,58

Observa-se que:

1. A heurística Y domina as outras duas heurísticas com respeito às quatro medidas

mostradas na tabela.

2. A heurística X supera a heurística Z.

Entretanto,

Pode-se dizer mais sobre a aparente superioridade da heurística Y?

Os resultados são estatisticamente significativos?

Existe um procedimento que mais sistematicamente pode ser seguido de forma a se

chegar a mesma conclusão?

TESTE DE CLASSIFICAÇÃO DE WILCOXON => teste estatístico não-

paramétrico (Pfaffenerger & Patterson, 1981, Mosteller & Rourke, 1973).

4

O teste de Wilcoxon admite as seguintes premissas:

1. Os dados consistem de n pares (xi, Yi) com diferenças di=xi - Yi.

2. Cada di precisa ser uma variável aleatória contínua.

3. A distribuição de cada di precisa ser simétrica.

4. Os pares (xi, yi), i=1, 2,..., n, representam uma amostragem aleatória de uma

distribuição bivariada.

Hipótese nula: E [x] =E [y].

Hipótese alternativa: E [x] E [y], E [x] E [y] ou E [x] E [y].

O teste de Wilcoxon usa classificações com sinal das diferenças para calcular a

diferença em localização de duas populações.

No contexto de comparação de heurísticas, o teste pode ser usado para

comparar duas heurísticas por vez, baseado em um conjunto de n

instâncias de tamanhos e estruturas diferentes.

xi e yi correspondem a porcentagens acima do limitante inferior, geradas

pelas duas heurísticas para a instância i.

A estatística de Wilcoxon W é calculada da seguinte maneira:

1. Obtenha a classificação, ordenando da menor para a maior, as diferenças

absolutas das medidas originais |di|.

2. Se qualquer di=0, elimine o dado e decremente n em uma unidade. Se

empates em diferenças absolutas ocorrerem, calcule a média das

classificações dos itens envolvidos no empate e use a média como

classificação de cada item empatado.

Exemplo:

i |di| Classificação

1 3.6 2½

2 0.9 1

3 3.6 2½

4 4.8 4

5

3. Para classificar a i-ésima diferença absoluta, agregue o sinal de xi – yi e

denote esta classificação com sinal por Ri.

4. Obtenha a soma W das classificações com sinal W= R1 + R2 + ... + Rn.

Heurística X vs. Heurística Y

Instância xi yi xi - yi Classificação de |xi - yi| Classificação com sinal Ri

1 1.94 5.16 -3.22 5 -5

2 8,26 8,26 0

3 5,09 5,82 -0,73 1 -1

4 16,79 5,84 10,95 12 12

5 12,70 3,51 9,19 10 10

6 7,12 9,83 -2,71 4 -4

7 14,42 4,17 10,25 11 11

8 18,75 13,89 4,86 6 6

9 14,67 8 6,67 9 9

10 61,24 37,98 23,26 13 13

11 40,32 33,99 6,33 8 8

12 9,82 9,82 0

13 7,34 8,86 -1,52 3 -3

14 32,08 33,02 -0,94 2 -2

15 8,82 2,94 5,88 7 7

W=61

5. A hipótese nula deve ser rejeitada a um nível de significância se:

W > W1-/2 ou W < W/2, W > W1-, ou W < W

dependendo se a hipótese alternativa é E [x] E [y], E [x] E [y] ou E [x] E [y].

No caso da hipótese adotada ser E [x] E [y], se assumirmos =0,05, então a hipótese nula

será válida se em apenas uma de 20 tentativas (0,05 =1/20), o valor de W seja excedido de

um valor crítico W1-.

6

Valores críticos do teste de Wilcoxon são tabulados em muitos livros de estatística não-

paramétrica. Além disso, para n10, o valor crítico W pode ser aproximado por:

W = Z() (n(n+1) (2n+1) /6))1/2

Onde Z() é o fractil normal padrão tal que uma proporção da área esteja à

esquerda de Z().

Quantis (fractis): pontos estabelecidos em intervalos regulares a partir da função distribuição

acumulada de uma variável aleatória. Dividem os dados ordenados em q subconjuntos de

dados de dimensão essencialmente igual. O k-ésimo q-quantil é o valor x tal que a

probabilidade de um evento da variável aleatória ser inferior a x é no máximo k/q e a

probabilidade da variável aleatória ser superior ou igual a x é pelo menos (q-k)/q.

Dados os resultados computacionais, parece apropriado testar a hipótese alternativa

E [x] > E [y] (ou seja, W > W1-,). Se utilizarmos um nível de significância =0,05 tem-se:

W1- = Z(1-) (n(n+1) (2n+1) /6))1/2

Z(1-) = Z(0,95) = 1, 645

Área da cauda da distribuição normal unitária

z 0.00 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09

0.0 0.50000 0.4960 0.4920 0.4880 0.4840 0.4801 0.4761 0.4721 0.4681 0.4641

0.1 0.4602 0.4562 0.4522 0.4483 0.4443 0.4404 0.4364 0.4325 0.4286 0.4247

…

1.6 0.0548 0.0537 0.0526 0.0516 0.0505 0.0495 0.0485 0.0475 0.0465 0.0455

…

3.9 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000

W1-=1, 645 * (13*14*27/6)1/2

=1, 645*28,62=47,08.

O teste indica que se a hipótese nula for verdadeira (e se as premissas 1-4 forem

válidas) então apenas uma em 20 tentativas (1/20=0,05), W excederá 47,08. Como W=61,

rejeitamos a hipótese nula e inferimos que a heurística Y é melhor que a heurística X.

(Note que como W > W1-·, E [x] > E [y]).

z

7

A seguir, as heurísticas Y e Z poderão ser comparadas. É claro, entretanto, pela

segunda tabela, que a heurística Y supera a heurística Z por uma larga margem e a

heurística Y é a mais precisa das três.

Aplique o teste de Wilcoxon para inferir a qualidade da heurística Y com

relação à heurística Z.

MÚLTIPLAS HEURÍSTICAS BUSCANDO O TÍTULO DE “A MAIS PRECISA”

Se Y é melhor que X a um nível de significância de e Y é melhor que Z a um nível de

significância de , isso não significa que Y é a heurística mais efetiva a um nível de

significância de .

Em geral, se Y é melhor que m heurísticas em níveis de significância individuais i,

então Y é melhor que todas as m heurísticas a um nível de significância de 1- (1-1)( 1-

2)... ( 1-m).

Com qual nível de significância pode-se concluir que a heurística Y supera

tanto a heurística X como a heurística Z, usando apenas o teste de Wilcoxon?

TESTE DE SINAL - VARIAÇÃO COM RELAÇÃO AO TESTE DE WILCOXON

Para ilustrá-lo, vamos comparar as heurísticas X e Z. Será testada a hipótese de que

ambos os procedimentos são igualmente precisos.

Subtraia os valores da solução que resultam da heurística X dos valores

resultantes da heurística Z e guarde o sinal da diferença - 12 números

positivos e três negativos são obtidos.

Se assumirmos que P[zi –xi > 0]=0,5, então a probabilidade de que 12 ou

mais diferenças positivas sejam encontradas é dada pela distribuição

binomial (p: probabilidade de sucesso da hipótese).

8

A inferência seria que a heurística X é superior à heurística Z. O teste de

Wilcoxon é mais poderoso que o teste de sinal, porém requer premissas mais fortes.

TESTE DE FRIEDMAN – COMPARAÇÃO DE TRÊS OU MAIS HEURÍSTICAS

Ao se lidar com três ou mais heurísticas diferentes, é interessante aplicar o teste de

Friedman ao invés de aplicar o teste de Wilcoxon repetidamente.

Características

Testa a hipótese nula Ho: E [x1] = E [x2] ==...=E [xk].

Pressupõe que os dados têm distribuições normais com variância comum.

O teste de Friedman envolve os seguintes passos (onde n=número de instâncias,

k=número de heurísticas):

1. Calcule Rij como a classificação (de 1 a k) designada à heurística j (j=X, Y, Z)

na instância i (a que apresenta o menor valor, recebe a classificação 1). No

caso de empates, a média das classificações é usada.

2. Calcule Rj=i=1 a n Rij para j=1, 2,..., k.

018,05,05,0)!5(!

!155,05,0

15 1515

12

1515

12

kk

k

kk

k kkk

kk

k

ppk

1515

12

115

9

Rij Rij

Heurística j Heurística j

Instància i X Y Z Instància i X Y Z

1 1 2 3 9 2 1 3

2 1.5 1.5 3 10 3 1 2

3 1 2 3 11 2 1 3

4 2 1 3 12 1.5 1.5 3

5 2 1 3 13 1 2 3

6 1 2 3 14 1 2 3

7 3 1 2 15 3 1.5 1.5

8 2 1 3 Rj 27 21.5 41.5

Rij2 56.5 33.75 118.25

3. A estatística do teste é dada por:

Tf=(n-1)(BF – nk(k+1)2/4)/AF - BF

onde AF=i=1 a nj=1 a k(Rij)2 e BF=1/n j=1 a k(Rj)

2.

4. A hipótese nula é rejeitada a um nível de significância se a estatística do

teste exceder a 1- quantil da distribuição F com k-1 e (n-1)(k-1) graus de

liberdade.

Distribuição F (nível de significância 0.95)

v2\v1 1 2 ...

1 161.4 199.5 254.3

...

28 4.20 3.34 ... 1.65

...

3.84 3.00 ... 1.00

10

Usando a tabela temos que:

AF=208,5

BF=194,23

e TF=14{194,23 – (15)(3)(16)/4}/14,27 = 13,96.

Como TF=13,96 > F0.05;2;28=3.34, é rejeitada a hipótese nula de que as

três heurísticas sejam igualmente precisas com =0,05.

Análises posteriores devem ser então realizadas para identificar a “melhor”

das três heurísticas.

O teste de sinal, o teste de Wilcoxon e o teste de Friedman representam

procedimentos razoáveis para comparação de heurísticas.

Entretanto, são todos testes de localização (especificamente, média ou mediana)

e não de forma ou dispersão da distribuição, os resultados podem ser não totalmente

satisfatórios Golden e Stewart (1985): propuseram uma abordagem de utilidade

esperada para comparação de duas ou mais heurísticas, que é ao mesmo tempo simples e

útil apesar de se basear em premissas de alguma forma arbitrárias.

11

PROJETO E REPORTAGEM DE EXPERIMENTOS

COMPUTACIONAIS COM MÉTODOS HEURÍSTICOS (baseado em

Barr, Golden, Kelly, Resende e Stewart, 1985)

EXPERIMENTO: Conjunto de testes executados sob condições controladas para um

propósito específico:

Demonstrar uma verdade conhecida

Ex: BA

B

A ckckdc

dc21 A B (taxa de reação)

Checar a validade de uma hipótese

Ex: O homo sapiens descende do homem Neanderthal?

Examinar o desempenho de algo novo - trazer à tona o conhecimento de um

processo particular e medir o efeito de um ou mais fatores no processo.

Ex: Minha heurística para o TSP provê resultados de maior qualidade para um

conjunto de instâncias do que o reportado no estado-da-arte.

EXPERIMENTOS COMPUTACIONAIS COM HEURÍSTICAS

Resolução de uma série de instâncias de um problema usando uma

implementação específica. Neste contexto, decisões que precisam ser tomadas

incluem:

seleção das instâncias

implementação do algoritmo

ambiente computacional

medidas de desempenho

opções do algoritmo

reportagem dos resultados.

FATOR: qualquer variável controlável do experimento que influencia o resultado do

experimento. A escolha de cada fator pode ter um efeito substancial nos resultados e

na significância do experimento.

12

PASSOS PARA IMPLEMENTAÇÃO DE EXPERIMENTOS

COMPUTACIONAIS

1. Defina os objetivos do experimento.

2. Escolha as medidas de desempenho e fatores a explorar.

3. Projete e execute o experimento.

4. Analise os dados e tire conclusões.

5. Reporte os resultados do experimento.

1. DEFINIÇÃO DOS OBJETIVOS DO EXPERIMENTO

Um experimento computacional deve ter um propósito claramente estipulado e

definido a priori.

O propósito ajuda a identificar os tipos de resultados a serem buscados, as hipóteses

a serem testadas, os testes a serem executados, os fatores a serem explorados, as medidas a

serem usadas, os dados necessários para dar suporte aos itens acima.

Apesar de não haver padrões estabelecidos para pesquisa de algoritmos, em geral

aceita-se que um método heurístico produz contribuição relevante se este é:

Rápido: produz soluções de alta qualidade mais rapidamente que outras abordagens

Preciso: identifica soluções de maior qualidade que outras abordagens

Robusto: menos sensível a diferenças nas caratecrísticas de problemas, dados e

parâmetros de ajuste do que outras abordagens

Simples: fácil de implementar

Alto impacto: resolve um problema novo ou importante mais rapidamente e mais

precisamente que outras abordagens

Generalizável: possui uma faixa larga de aplicações

Inovador: é novo e criativo por si.

Além disso, a reportagem de pesquisa sobre heurísticas é valiosa se ela é:

Reveladora: oferece insight sobre o projeto geral da heurística ou da estrutura do

problema ao estabelecer as razões para o desempenho do algoritmo e explicar seu

comportamento

Teórica: oferece insight teórico, tais como limitantes da qualidade de solução.

13

QUALQUER QUE SEJA A CONTRIBUIÇÃO DA HEURÍSTICA SENDO REPORTADA,

ALGUMA EXPERIMENTAÇÃO COMPUTACIONAL SERÁ NECESSÁRIA PARA

DEMONSTRAR QUE O PROCEDIMENTO FAZ O QUE O(S) AUTOR(ES) CLAMA(M)

FAZER.

TIPOS DE EXPERIMENTOS COMPUTACIONAIS

1. Comparação do desempenho de diferentes algoritmos para a mesma classe de

problemas.

2. Caracterização ou descrição do desempenho isolado de um algoritmo.

a) EXPERIMENTOS COMPARATIVOS (mais comuns)

Visam medir a efetividade relativa em termos das medidas de desempenho adotadas

ao resolver classes específicas de problemas. Geralmente:

Nova abordagem vs. técnicas competitivas existentes.

Nova abordagem vs. heurísticas populares ou publicadas (mesmo que não

representem o estado da arte).

Decisões no estágio inicial do experimento: escolha ou desenvolvimento de

algoritmos e códigos computacionais para estudo, e escolha de classes de problemas.

MÉTODOS DE SOLUÇÃO EFETIVOS PARA CLASSES GERAIS SÃO MAIS

PRESTIGIADOS QUE OS CRIADOS PARA CLASSES ESPECIAIS OU PARA

PROBLEMAS COM ESTRUTURAS ESPECIAIS.

“Comment 7: Moreover, the heuristic takes advantages of the specific pipeline

multiprocessor architecture proposed in the paper. It will be interesting to

see empirically how this heuristic performs on other multiprocessor

architectures. I suggest the authors conduct computational experiments to

verify this issue.”

É preferível obter (ou criar, se necessário) implementações para os métodos

competitivos e fazer comparações com a implementação proposta sob o mesmo

ambiente computacional.

14

Se outros métodos não existem, um método mais geral (por exemplo, baseado

em programação linear ou inteira) ou uma abordagem gulosa simples devem

servir como referência.

b) EXPERIMENTOS DESCRITIVOS

São criados para caracterizar um dado algoritmo, ao invés de compará-los com

outros algoritmos. O objetivo é ganhar compreensão do comportamento da metodologia e

dos fatores que influenciam tal comportamento.

Figure 5 – Distribution of gains provided by WEFB according to instances’ dod

ranges.

Para obter insight do efeito de fatores específicos em um algoritmo, devem-se testar

códigos que são idênticos exceto por um único fator e utilizar técnicas como análise de

variância para testar o efeito do fator nas medidas de desempenho.

2. ESCOLHA DE MEDIDAS DE DESEMPENHO E ESCOLHA DE FATORES

MEDIDAS DE DESEMPENHO

1. Qual a qualidade da melhor solução encontrada?

2. Quanto tempo é requerido para se obter a melhor solução?

3. Quão rapidamente o algoritmo encontra boas soluções? QUALIDADE

4. Quão robusto é o método? ESFORÇO

5. Quão “distante” a melhor solução está daquelas facilmente obtidas? ROBUSTEZ

6. Qual o trade-off entre factiblidade e qualidade das soluções?

0.0

5.0

10.0

15.0

20.0

25.0

30.0

0 (0,0.2] (0.2,0.4] (0.4,0.6] (0.6,0.8] (0.8,0.1]

100-case (lost)

200-case (lost)

15

a) QUALIDADE DAS SOLUÇÕES

Ao testar um algoritmo heurístico, a consideração adicional de quão perto a solução

heurística está de soluções de referência é de grande importância.

Se a solução ótima é conhecida o desvio percentual da solução ótima é

reportado

Se a solução ótima não é conhecida o desvio percentual de um limitante inferior

(superior) “apertado” é reportado. Heurísticas de qualidade podem prover estes

limitantes.

b) ESFORÇO COMPUTACIONAL

A velocidade de obtenção das soluções é um fator chave para análise do

desempenho. É importante reportar:

1. Tempo para obtenção da melhor solução (deve incluir todo o pré-processamento

envolvido e operações de suporte).

2. Tempo total de execução: cuidados com métodos abertos (metaheurísticas).

3. Tempo por fase: determinação do “gargalo” do algoritmo.

Table 2

Total vehicle distance and customer time

Rule Vehicle

distance

Customer

time

% of manual % of manual CPU

time

(miles) (h) distance time (s)

Insertion 6737 442.5 211.8 21.6 9

Improvement 6593 422.7 213.6 26.0 231

TABU-S 6365 410.6 216.6 28.7 623

TABU-A 6338 411.7 217.0 28.5 1357

Manual 7635 449.7 0.0 0.0 NA

Todos os tempos reportados devem ser tomados para um único conjunto de valores

de parâmetros do algoritmo ou para uma regra específica que estabelece os valores

de parâmetros para cada instância.

16

“… from this point on, the best values of t seem to depend on the number of

boxes in the initial pattern provided by the starting block heuristic. Let n0

be the number of boxes in the initial pattern. Regression analysis for the 16

solved instances (with =0.5) resulted in the linear function t’ = 0.3783n0 –

3.2357. The model exhibits high correlation (R2= 0.9875) between t’ and n

0, and

the t’ values provided could be used to determine the range of values to be

tested with other problems. “

Quando a melhor solução é reportada de um conjunto de execuções com diferentes

parâmetros, isso deve ser claramente reportado.

A taxa de convergência para uma solução cujo valor é próximo ao da melhor

solução obtida reflete o trade-off qualidade-tempo e deve ser medida.

A relação qualidade-esforço também pode ser obtida com medidas descritivas.

Exemplo: r0.05= (tempo para obtenção da primeira solução 5% inferior à melhor

solução)/(tempo para melhor solução).

Tempos de execução podem não ser uma boa tradução de um sistema

computacional para outro outras medidas de esforço computacional podem ser

mais apropriadas: contar iterações, operações ou tarefas principais (número de vizinhos

gerados em procedimentos de busca local).

Os benefícios desta abordagem são muitos, pois produzem experimentos nos quais

fatores como habilidades de programação e velocidade do computador são irrelevantes.

17

c) ROBUSTEZ

Geralmente, robustez é baseada na habilidade de uma heurística se portar bem em

uma faixa larga de instâncias teste. É obtida através de medidas de variabilidade.

Estratégias e parâmetros da heurística devem permanecer constantes para o

conjunto de instâncias ou devem ser automaticamente definidos usando

atributos de instâncias individuais.

Exemplo: h= 0.0009*n2 - 0.0552*n + 5.2996 (valor do parâmetro h em função do

tamanho da instância n)

Quando valores de parâmetros são escolhidos, medidas da sensibilidade do

desempenho da heurística a pequenas mudanças nos valores dos parâmetros

indicam a robustez do algoritmo e devem ser incluídas.

0%

2%

4%

6%

8%

10%

12%

14%

Desvio

pe

rce

ntu

al d

o c

usto

da

m

elh

or

so

luçã

o c

on

he

cid

a

Instâncias

Figura 4 - Valores mínimo, médio e máximo da solução com execuções sob

diferentes valores de parâmetros.

Resultados negativos devem ser reportados. Se uma heurística não garante

factibilidade ou tem limitações evidentes, deve-se reportar estes casos e, se

possível, explicitar ou sugerir as razões.

“… On the other hand, the algorithms were unable to find the optimal solutions

of 18 examples of set S2, even for N= (the best 1st-order patterns laid out

one box less than the optimal pattern).”

“…When the RB strategy is included (algorithm WEFB) and compared to WEF,

smaller gains in lost sales are observed up to dod = 0.6. Further examination

of the critical instances indicates that although no buffered request was

18

lost, vehicles were actually necessary in the region of these locations

(according to WEF plans) in order to serve some new requests that arrived at a

later time. This analysis indicates that better results could be attained if

conditions regarding territory coverage (Ichoua et al, 2006) are incorporated

in the decision of whether buffering or not a new request.”

FATORES PARA ESTUDO

Há três categorias de fatores que afetam o desempenho de algoritmos - o problema,

o algoritmo e o ambiente de teste. Para cada categoria, é necessário selecionar dentre os

fatores:

o que estudar (tamanho do problema, método heurístico).

o que fixar em algum nível (classe do problema, regra de parada, ambiente

computacional).

o que ignorar, e esperar que não influenciará os resultados.

a) FATORES DO PROBLEMA

TAMANHO É importante realizar execuções “estressantes” com

instâncias grandes. Muitos fatores não aparecem em instâncias pequenas, e

tais execuções podem não gerar previsões precisas para instâncias maiores e

mais realistas.

CARACTERÍSTICAS DAS INSTÂNCIAS

Exemplos:

Roterização: distribuição uniforme ou agrupada dos nós, com ou sem

janelas de tempo, com ou sem tempo máximo de rota, etc.

Programação de tarefas com precedência em máquinas: estrutura do

grafo (em linha, diamante, etc), grau médio dos nós do grafo, etc.

b) FATORES DO ALGORITMO

SELEÇÃO DAS HEURÍSTICAS E CÓDIGOS EM EXPERIMENTOS

COMPARATIVOS Envolve escolhas específicas do algoritmo sendo

testado: estratégias e valores de parâmetros (construção da solução inicial;

parâmetros da busca heurística regras bem definidas).

19

Heurísticas robustas que funcionam bem com um único conjunto de valores

de parâmetros são geralmente preferíveis a heurísticas que requerem valores

individuais para cada instância, a não ser que a heurística seja auto-ajustável.

O processo para definir estas escolhas é de interesse do leitor e pode

envolver alguma amostragem e análise estatística.

Critério de Parada: é antiético realizar execuções longas para então definir

uma regra apropriada para a heurística.

c) FATORES DO AMBIENTE

Hardware: modelo, memória, velocidade, número de processadores, etc.

Software: sistema operacional, linguagem, compilador, configuração do

compilador, etc.

Idealmente, algoritmos competitivos devem ser codificados pelo mesmo especialista

e serem aplicados às mesmas instâncias na mesma configuração de computador os

resultados em termos de tempo e qualidade de solução são diretamente comparáveis.

Caso contrário é necessário determinar o efeito dos fatores discrepantes.

3. PROJETO E EXECUÇÃO DO EXPERIMENTO

Projeto de experimentos: processo de planejamento de um experimento para

assegurar que os dados apropriados serão coletados. Um bom projeto de experimentos tem

as seguintes características:

Não tendencioso.

Demonstra claramente o desempenho do processo testado.

Apresenta razões para o desempenho.

Tem uma lógica justificável.

Gera conclusões aceitáveis.

É reproduzível.

20

a) SELEÇÃO DE INSTÂNCIAS TESTE

As instâncias tratadas no experimento podem ser de dois tipos:

Extraídas de contextos reais: refletem o propósito último dos métodos

heurísticos e devem ser representativos das instâncias para as quais a heurística

será aplicada na prática.

Criados com um software de geração de instâncias: dá ao usuário controle

sobre características do problema, permitindo a criação de instâncias com

uma configuração específica de fatores do projeto do experimento. Alguns

geradores fornecem a solução ótima ou seu valor.

Se as instâncias são criadas pelo usuário, o processo de geração deve ser

claramente descrito e as novas instâncias geradas devem ser armazenadas (ou

o processo de geração reproduzível) para serem utilizados por outros.

Em geral, quanto mais instâncias avaliadas, mais informativo é o estudo.

As instâncias mais interessantes são aquelas que estressam ou testam os limites

do software ou causam sua falha.

4. ANÁLISE DOS RESULTADOS E CONCLUSÕES

Análise de dados consiste na avaliação dos dados empíricos obtidos com técnicas

estatísticas ou não com respeito ao propósito e objetivos do experimento.

Ex.: Taxa de crescimento do tempo computacional com o tamanho da instância

útil para determinar como a heurística se comportará em instâncias grandes. Um

modelo de regressão que relaciona tempos de execução com o tamanho do problema

pode ser usado para caracterizar o crescimento empírico do tempo.

Ferramentas de análise de dados incluem:

Pacotes estatísticos gerais (matlab, mathematika, etc).

Softwares para visualização de dados: gráficos fornecem uma forma de

visualizar todos os dados. Uma maior compreensão do processo pode ser

atingida com o exame do total de dados do que somente com um sumário

das estatísticas.

21

Figura 2: Desempenho nos testes de [10] (Gráfico Dolan e Moré).

20000

22000

24000

26000

28000

30000

32000

34000

36000

38000

40000

1 501 1001 1501Iteration

Cost

HHTA

NA

Figura 5: Custo da solução vs Iteração dos algoritmos HTA e NA.

Métodos estatísticos devem ser empregados sempre que possível para

indicar a força das relações entre fatores diferentes e medidas de

desempenho não provam casualidade, mas podem indicar a

confiabilidade e validade dos resultados.

Uma vez que os dados tenham sido analisados, os resultados são interpretados como

uma série de conclusões e inferências deduzidas da evidência coletada. A significância

estatística e prática destas conclusões devem ser endereçadas, suas implicações

avaliadas e recomendações realizadas.

22

A EXPERIMENTAÇÃO TENDE A SER UM PROCESSO ITERATIVO, ONDE CADA ETAPA

NÃO SÓ EXPANDE O CONHECIMENTO DO ALGORITMO, MAS TAMBÉM TRAZ NOVAS

QUESTÕES, E ALGUMAS VEZES, A NECESSIDADE DE NOVAS MEDIDAS DE

DESEMPENHO.

ORIENTAÇÕES PARA REPORTAGEM DE EXPERIMENTOS

COMPUTACIONAIS

1. Reprodutibilidade é essencial: faça documentação para permitir a reprodução

substancial dos resultados.

2. Especifique todos os fatores de influência em detalhe: heurística, código, parâmetros,

números pseudo-aletórios, dados de entrada, estruturas de dados não triviais, e ambiente

computacional.

3. Seja preciso quanto a medidas de tempo.

4. Mostre como alguns parâmetros do algoritmo são definidos.

5. Use técnicas estatísticas de projeto de experimentos.

6. Compare a heurística com outros métodos.

7. Produza uma reportagem que abranja os resultados obtidos.

ROTEIRO DE EXPERIMENTAÇÃO PARA O TRABALHO DE AVALIAÇÃO

1. Defina as análises que vc deseja realizar em seu experimento.

Exemplos:

Como o desempenho de uma heurística de busca local é afetado se são utilizadas

soluções aleatórias ou soluções geradas por uma heurística construtiva?

Qual o efeito da temperatura inicial no desempenho de SA

Para um dado valor de temperatura inicial selecionado, como o desempenho de

SA é afetado conforme se aumenta o tamanho da instância?

2. Selecione um conjunto de instâncias interessantes do problema (geradas aleatoriamente,

obtidas em uma biblioteca, etc.).

3. Selecione um subconjunto de instâncias teste do total de instâncias (cerca de 30%). As

instâncias teste devem ser representativas do conjunto total, ou seja, devem contemplar

23

características que devem estar alinhadas com o tipo de análise definida no passo 1. Por

exemplo:

Diferentes tamanhos.

Outras características que implicam em uma maior ou menor dificuldade de

resolução.

Por exemplo, no problema da mochila, se os objetos têm pesos relativamente grandes à

capacidade da mochila e valores aleatórios, então esta instância deve envolver um

conjunto maior de opções de seleção de itens. Por outro lado, se os objetos têm pesos

relativamente pequenos à capacidade da mochila e valores aleatórios, então é possível

incluir grande parte dos objetos na solução da mochila, o que leva à redução do número

de opções de seleção. No caso extremo, pode ser resolvida de forma trivial (seleção de

todos os objetos).

4. Em um primeiro conjunto de experimentos, resolva as instâncias teste no sentido de

investigar o efeito que valores de parâmetros e estratégias definidos no passo 4 têm

sobre a performance do algoritmo. Os resultados devem indicar os melhores valores de

parâmetros e estratégias. Outros parâmetros são mantidos fixos.

5. Aplique os valores de parâmetros e estratégias nas instâncias restantes. Analise

qualidade de solução e tempo computacional e compile os resultados, obtendo medidas

de performance médias para o conjunto de instâncias. Esses resultados podem implicar

na discriminação de grupos de instâncias.

Para as metaheurísticas:

SIMULATED ANNEALING

Parâmetros: Temperatura inicial, número de iterações em cada temperatura,

velocidade de resfriamento, temperatura final.

Utilize a velocidade de resfriamento geométrica, fixe a temperatura final e o

número de iterações em cada temperatura, e investigue com as instâncias teste:

i. O impacto de três temperaturas iniciais na qualidade da solução.

ii. O impacto de três valores de r (velocidade de resfriamento) na qualidade

da solução.

iii. O impacto de reaquecimento após certo número de resfriamentos da

24

temperatura sem melhoria.

Plote a trajetória de busca de algumas das instâncias teste (para uma dada

temperatura inicial, e os três valores de r) que sejam interessantes tanto

positivamente como negativamente.

Aplique os melhores valores de r e T para as demais instâncias.

BUSCA TABU

Definições requeridas: movimento, atributos do movimento, status tabu do

atributo, regra de ativação tabu do movimento.

Parâmetros: Estrutura da lista tabu, tamanho de lista tabu, critérios de parada.

Utilize, se possível, estruturas matriciais para armazenagem da informação

sobre o status tabu dos atributos, e períodos tabu dinâmicos aleatórios (os quais

devem crescer com o tamanho da instância). Utilize como um dos critérios de

parada, 2000 iterações sem melhoria.

Verifique com as instâncias teste:

i. O impacto de duas regras de ativação tabu (uma mais restritiva e outra

menos restritiva).

ii. O impacto de cinco faixas de período tabu na qualidade da solução.

Determine períodos mais adequados e aqueles que provocam ciclagem

ou restritividade excessiva, através dos resultados numéricos e pela

análise de gráficos função objetivo vs. iteração.

Plote a trajetória de busca de algumas das instâncias teste que sejam interessantes.

Aplique os melhores valores de período tabu e regras de ativação tabu às demais

instâncias.

ALGORITMOS GENÉTICOS

Definições requeridas: representação do cromossoma, operadores de cruzamento

e mutação, procedimento de factibilização de soluções infactíveis (se

necessário), geração da população inicial (aleatoriamente).

Parâmetros: Tamanho da população, probabilidades de cruzamento e mutação,

número de gerações.

Utilize o operador de cruzamento de um ponto. Fixe o tamanho da população

25

em 20 cromossomas e gere a população inicial (factível) aleatoriamente.

Verifique com as instâncias teste:

i. O impacto de quatro probabilidades de mutação (0.01, 0.05, 0.1 e 0.2).

ii. O impacto de quatro probabilidades de cruzamento (0.1, 0.3, 0.5 e 0.7).

Determine os valores mais adequados destas probabilidades.

Plote a trajetória de busca de algumas das instâncias teste que possam ser

interessantes.

Aplique os melhores valores de pm e pc às demais instâncias.

GRASP

Definições requeridas: procedimento de geração de soluções (factíveis).

Modifique a heurística de construção utilizada nas outras metaheurísticas

incorporando os conceitos probabilísticos da técnica GRASP. Use esta nova

heurística de construção em cada uma das implementações das metaheurísticas

anteriores. No caso de algoritmos genéticos, como as soluções iniciais foram

geradas aleatoriamente, as 20 soluções iniciais com GRASP devem ser obtidas

baseando-se na heurística de construção das outras metaheurísticas.

Verifique com as instâncias teste:

i. O impacto do uso da heurística de construção sobre as SA, BT e AG.

Houve melhoria na qualidade das soluções? Qual a metaheurística mais

beneficiada?

Aplique a heurística de construção às demais instâncias com cada metaheurística.

RESULTADOS GERAIS: Calcule o desempenho médio em termos de qualidade de

solução e tempo computacional. Qual das implementações de metaheurísticas foi a mais

efetiva? Qual a mais rápida?