Universidade Federal do Rio Grande do Sul - Instituto de Informática

Têmpera Simulada Aplicada ao Problema de Designação Quadrática

Fábio A. Camargo Corrêa - 141971

faccorrea@inf.ufrgs.br

Porto Alegre, 03 de Dezembro de 2007

Índice

1. Introdução................................................................................................................. 1 2. Definição do Problema............................................................................................. 1 3. Têmpera Simulada.....................................................................................................1

3.1. O Processo Físico............................................................................................... 13.2. Aplicação ao Problema....................................................................................... 2

4. Resultados..................................................................................................................34.1 alfa x T0 ..............................................................................................................44.2 alfa x L ................................................................................................................54.3 L x T0 ..................................................................................................................64.4 Onde foi que eu errei ...........................................................................................7

5. Conclusões.................................................................................................................7 6. Bibliografia................................................................................................................7

1. Introdução

No campo da computação, é freqüente o número de vezes onde nos deparamos com problemas pertencentes a classe dos problemas NP. Ao longo do curso de ciência da computação, até então não tinha sido apresentada nenhuma forma de atacar estes problemas, e quando nos deparávamos com eles, não tínhamos muito que fazer além de constatar que não haveria algoritmo eficiente para resolvê-los. Nesta disciplina, foram apresentadas várias alternativas de tratar estes problemas . Em que pese que as soluções obtidas, quando aplicados estes métodos, não tenham garantia de optimalidade, muitas vezes o resultado obtido é satisfatório.

Este trabalho tem como objetivo aplicar a meta-heurísica da têmpera simulada (simulated annealing) ao problema de designação quadrática e analisar seu desempenho . O foco será analisar a influência dos parâmetros desta heurística, que veremos posteriormente, na qualidade da solução obtida.

2. Definição do problema

O problema de designação quadrática consiste em encontrar uma bijeção f entre os vértices de dois grafos A e B com n vértices, de tal forma que minimize o custo total, dado por:

Uma interpretação para este problema é que cada vértice de A é uma localidade, e o valor da aresta entre uma localidade i e j é a distância entre estas duas. Cada vértice de B é um recurso, que deve ser alocado em alguma localidade. Para cada par x e y de recursos, existe um valor de fluxo associado. Por exemplo, suponha que x seja um cinema e y seja um lugar onde vende-se pipoca. É natural que o fluxo entre estes dois seja grande e, portanto, é razoável alocar x e y em locais de tal forma que ambos não fiquem muito distantes. Este locais são os vértices i e j do grafo A.

3. Têmpera Simulada

A Têmpera Simulada é uma processo físico de resfriamento gradual de determinado sólido, de forma que este possa atingir um estado de baixa energia. Em 1983, Kirkpatrick e seu colaboradores sugeriram que a simulação deste processo poderia ser utilizada para buscar soluções factíveis, com o objetivo de econtrar uma solução ótima. A estratégia é uma variante da técnica de busca local, onde são introduzidos os conceitos do processo físico.

3.1 O processo físico

O processo físico da têmpera (ou recozimento) consiste em duas etapas: elevar a temperatura de um determinado sólido ao valor no qual este se funde. Feito isso, é efetuado o resfriamento do material até que este se solidifique. Este resfriamento deve ser feito de forma lenta e gradual, pois é necessário dar um tempo para os átomos do material, de forma que estes se organizem em uma estrutura cuja configuração é de energia mínima para determinada temperatura. Após este tempo, a temperatura é reduzida novamente e deve-se aguardar mais um tempo para que o material encontre, para esta temperatura, uma configuração de energia mínima. Caso a temperatura seja diminuída de forma muito rápida, o material vai conter várias imperfeições, pois não foi dado tempo suficiente para que os átomos encontrassem essa configuração de energia mínima.

Para exemplificar o quão gradual deve ser este processo, lentes de telescópios científicos

1

∑i , j=0

n

Aij×B f i f j

chegam a ser resfriadas ao longo de cinco anos. A lente do telescópio Hubble levou dois anos para atigir a configuração de energia mínima, isto é, sem imperfeições.

3.2 Aplicação ao problema

As analogias do processo físico com o problema a ser resolvido pela meta-heurística são as seguntes:

a) Uma configuração do material é uma solução;b) A configuração de energia mínima é a solução ótima;c) O nível de energia é a função objetivo;d) A temperatura é um parâmetro de controle;e) O tempo que o material vai permacener em uma dada temperatura é um número de

iterações L;

Nesta meta-heurística, são possíveis movimentos que aumentem o valor da função objetivo. Tal comportamento inspira-se no processo físico, ende existe uma probabilidade de que o material atinja uma configuração cuja energia é aumentada. Sendo E(S) o nível de energia do material em um estado S; T a temperatura e k uma constante, esta probabilidade é dada pela fórmula:

P E =e−E

kT , sendo E=E −E ' Para o problema de designação quadrática, uma solução é um vetor com n elementos,

onde i = x representa o mapeamento do vértice i de A no vértice x de B. Uma solução vizinha de é o mesmo vetor, permutando-se duas posições r e s.

Para este problema, é a diferença entre a função objetivo obtida com as configurações e ' . Posto isto, o é como segue:

Determinando o que são as soluções vizinhas, que é a parte mais difícil do algoritmo, o pseudo-código para a têmpera simulada é:

2

EE

, r , s =A[r ][r ] .B [ s ][ s ]−B[r ][r ]A[r ] [s ]. B[ s][r ]−B [ r ][s ]A[s ][r ]. B[r ][ s]−B [ s ] [ r ]A[s ][ s ]. B[r ][r ]−B[s ][ s ]

∑k=1 ;k≠r , s

n

A[k ] [r ] .B [k ][ s]−B [ k ][r ]

A[k ] [s ] .B[k ][r ]−B [k ][ s]A[r ][k ] .B[ s][k ]−B [ r ] [ k ]A[s ][k ] .B[r ][k ]−B [ s ] [k ]

4.Resultados

Em contraste com a simplicidade da implementação do algoritmo, verifica-se que é necessário determinar cada parâmetro. A falta de um conhecimento mais profundo sobre o processo físico atrapalha nesta escolha . Posto isso, a implementação teve um maior enfoque em analisar os efeitos de cada parâmetro na qualidade da solução. Sendo assim, os parâmetros testados obedeceram os seguintes limites, com incrementos definidos a seguir:

0.5≤≤0.99250≤L≤1.000

1.000≤T0≤10.000

a) α é a taxa decrescimento da temperatura, com incremento 0.05 caso α < 0.95, incremento 0.1 caso contrário;

b) L é o número de iterações em que será consultada a vizinhança de uma solução em uma determinada temperatura, com incremento 250 a cada passo;

c) T0 é a temperatura inicial, com incremento 1.000 a cada passo;

Os resultados foram obtidos baseados nas instâncias pré-determinadas na definição deste trabalho, extraídas do site QAPLib [3]. Os parâmetros na tabela se referem a primeira combinação de parâmetros em que achou a solução especificada, podendo ter sido encontrada a mesma solução com outros parâmetros, como é o caso da instância els19, que encontrou a solução ótima para uma vasta combinação de parâmetros.

Instância Solução Obtida Solução QPABLib % optimalidade α L T0had12 1690 1652 97,75 0.99 750 200had14 2824 2724 96,45 0.95 1000 3000chr15b 7990 7790 100 0.95 250 6000esc16h 1012 996 98,41 0.8 750 1000els19 17212548 17212548 100 0.5 750 3000chr22a 7792 6156 79 0.9 750 8000bur26c 5426809 5426795 99,99 0.95 250 1000bur26f 3782226 3782044 99,99 0.95 1000 7000kra30b 94050 88900 94,52 0.99 5000 9000kra32 22430 88700 (???) 395,45(??) 0.6 1000 8000esc32a 274 130 47,44 0.99 500 3000sko90 131668 115334 87,59 0.85 750 3000

O desempenho da meta-heurística mostrou-se interessante, posto que achou soluções razoáveis para a maioria dos casos. Agora, serão selecionadas as duas melhores e as duas piores soluções, analisando a relação que existe entre os parâmetros e a solução obtida. Algo que se pode

3

verificar somente olhando esta tabela é que, de fato, a taxa de redução da temperatura é um dos parâmetros mais relevantes, já que para a maioria dos casos o melhor valor encontrado foi sob uma taxa de redução acima de 0.95.

Optou-se por mostrar os gráficos em duas dimensões, sendo cada um dos eixos referentes a um parâmetro. Os gráficos foram gerados com a ferramenta MATLAB, utilizando os arquivos de log gerado para as soluções. Nos gráficos, as área escuras representam proximidade da solução ótima.

4.1 alfa x T0

A interação entre estes dois parâmetros parece não afetar muito a qualidade da solução, posto que ao longo do eixo que representa alfa, a variação é praticamente imperceptível. Note que estes gráficos são tri-dimensionais, logo uma pequena variação do resultado em relação ao alfa pode ter sido perdida por conta da intperpolação dos pontos. Mas os gráficos são consistentes, já que a melhor solução encontrada está justamente com a temperatura inicial determinado pela região mais escura do gráfico

Els19 Chr15b

Chr22a Esc32a

4

4.2 Alfa x L

A interação entre alfa e L também parece não afetar a solução. Estes gráficos indicam que, selecionando um L adequado, é provável que encontremos uma solução boa. O único caso, destes gráficos apresentados, que verificou-se uma forte ligação entre L e alfa foi a instância chr22a, já que a solução ótima só poderia ser encontrada em uma região delimitada no canto superior direito, do gráfico, isto é, o L entre 250 e 500 e com alfa valendo acima de 0.95.

Els9 Chr15b

Chr22a Esc32a

5

4.3 L x T0

Estes dois parâmetros tem um comportamento que, verificou-se, depende dos valores que a função objetivo assume. Quanto mais próximo são os valores da função objetivo e da temperatura inicial, menor é a chance de se encontrar a solução ótima, que está representado nos gráficos como sendo a distribuição de regiões claras e escuras. Para a instância Els19, cuja função objetivo assume valores bastante elevados, as soluções ótimas se distribuem ao longo de praticamente todo valor de L e T0, onde o T0 é maior que 3000 . Tal falha de raciocínio é detalhada a seguir, e sua correção não fez parte da implementação por ter sido detectada após o prazo estipulado da apresentação. Em que pese que para a instância chr15b, os valores ótimos (região escura) não sejam tão abundantes quanto a outra instância, a solução ótima foi encontrada com um alfa valendo 0.95. Se a temperatura reduzisse de forma mais rápida, não chegaríamos a um resultado tão bom. Para os casos de teste onde os valores assumidos para a função objetivo são bem pequenos, são abuntantes as regiões claras no gráfico, isto é, existem poucas combinações adequadas para se encontrar uma solução boa.

Els9 Chr15b

Chr22a Esc32a

6

4.4 Onde foi que eu errei

Analisando os resultados obtidos, claramente havia alguma coisa errada na minha implementação. O padrão para as melhores soluções encontradas era que o valor da função objetivo assumia valores muito altos (comparados a temperatura inicial), enquanto as piores soluções ocorria o contrário. Ora, não deve ser correto a qualidade da heurística estar subjugada a estrutura da instância do problema. A falha proveio do fato de T0 não ter sido dimensionado de forma correta. Recapitulando , a probabilidade da função objetivo ter seu valor aumentado é:

Isto significa que, quanto menor for EkT , maior será a probabilidade de se realizar um

movimento aleatório. Para as instâncias cujo valor de E é muito baixo, impostos os limites determinados para a temperatura inicial, a heurística se assemelha-se a um randon walk, posto que a cada passo se efetua uma transição sem saber se esta irá aumentar ou diminuir o valor da função objetivo.

A correção necessária seria estimar os valores máximo e mínimo de e somente então, determinar um valor adequado para T0.

5. Conclusões

A têmpera simulada é uma heurística que alcança resultados bastante satisfatórios. Além de ser de fácil implementação, há garantia de convergência, dado tempo suficiente para encontrar-se uma configuração de energia mínima. As desvantagens são :

a) O número de parâmetros envolvidos;b) A velocidade da redução da temperatura implica visitar um número exponencial de

vizinhosc) Um processo lento de redução da temperatura leva a tempos de processamento elevados

Quando trata-se de heurísticas, conhecimento prático é valoso, já que através dele eu pudecompreender a falha da minha implementação sem conhecimento profundo sobre o processo físico.

6. Bibliografia

[1] KIRKPATRICJ, S.; GELATT, C. D.; VECCHI M.P. Optimization by Simulated Annealing, Science v.220, n.4598, 1983 [2] STÜTZLE, T.; DORIGO; M.; Local Search and Metaheuristics for the Quadratic Assignment Problem [3] BURKARD R.E. ; KARISCH S.E. ; RENDLL F., QAPLib Home Page http://www.opt.math.tu-graz.ac.at/qaplib/

7

P E =e−E

kT

E