QAP: Metodos construtivos, 2-opt, Busca tabu

Problema quadrático de alocação (QAP)

Métodos construtivosBusca local 2-optBusca tabu

Daniel Lemes [email protected]

18 de dezembro de 2013

mailto:[email protected]

mailto:[email protected]

Métodos construtivos

Foram elaborados dois métodos construtivos gulosos, ambos orientados a construir uma solução de tal forma que o custo total seja mínimo.1. FIA (Facilidade inicial arbitrária)2. NFI (N facilidades iniciais)


Método 1: FIA (Facilidade inicial arbitrária)Algoritmo guloso que consiste em obter o menor custo total a cada atribuição de facilidade a um local, sendo que a atribuição da primeira facilidade a um local é arbitrária. 1. A facilidade 0 é alocada ao local 0. 2. Verifica-se dentre as facilidades disponíveis qual facilidade deveria ser escolhida para ser alocada ao próximo local i, de tal forma que o custo total seja mínimo.3. Executa-se o passo 2 até a n-ésima facilidade, gerando uma permutação que corresponde à solução final.


Método 1: FIA (Facilidade inicial arbitrária)1. (n-1) iterações

2. (n-2) iterações




…n-1.(n-(n-1)) iterações

Complexidade:O((n² - n)/2) ⇒ O(n²)


Método 2: NFI (N facilidades iniciais)Este método é um aprimoramento da construção FIA. Ele consiste em n execuções do algoritmo FIA, atribuindo cada uma das n facilidades à facilidade inicial.

1. Executa-se o algoritmo FIA (com a facilidade i alocada ao local 0).

2. Armazena-se o custo da permutação pi

3. Repete-se os passos 1 e 2 atribuindo a facilidade i+1 ao local 0 até que todas as n facilidades sejam testadas como sendo a facilidade inicial no algoritmo FIA.

4. A iteração que gerar o menor custo é sempre armazenada e a solução final é então escolhida.


Método 2: NFI (N facilidades iniciais)1. (n-1) iterações





…n-1.(n-(n-1)) iterações

Complexidade:O(n × (n² - n)/2) ⇒ O(n³)

n vezes


Método 2: NFI (N facilidades iniciais)def initial_solution(distance, flow):

n = int(math.sqrt(len(distance)))

best_cost_final = 0

m_x = []

for q in range(0, n):

m = [q]

m2 = [q]

j = 0

Métodos construtivos# here FIA starts

while j < n-1:

k = get_minor(m, n)

m.append(k)

m2 = copy(m)

best_cost = cost(m, distance, flow)

if j == 0:

best_cost_final = best_cost

for i in range(0, n):

if i not in m:

m2[len(m2)-1] = i

c = cost(m2, distance, flow)

if c < best_cost:

m[len(m)-1] = i

best_cost = c

j = j + 1

# here FIA ends

if best_cost < best_cost_final:

best_cost_final = best_cost

m_final = copy(m)

Busca local

2-optNesse método, as facilidades são transpostas durante a execução do algoritmo. Se o número de facilidades e locais for n, então o número de transposições em cada iteração do algoritmo será (n²-n)/2. Inicialmente, o algoritmo considera a transposição das facilidades alocadas nos locais 0 e 1. Se o valor da função objetivo resultante para a solução for menor que o valor da solução inicial, então esta solução é armazenada como uma solução candidata para o futuro. Caso contrário, ela é descartada. O procedimento de transposições continua até que todas as trocas de pares sejam consideradas.

def iteration_2opt(p, dist, flow):

best_solution = []

best_solution = copy(p)

best_cost = cost(p, dist, flow)

size = len(p)

i = 0

for i in range(0, size-1):

for j in range(i+1, size):

posI = p.index(i)

posJ = p.index(j)

p[posI] = j

p[posJ] = i

current_cost = cost(p, dist, flow)

if(current_cost < best_cost):

best_solution = copy(p)

best_cost = current_cost

Busca local

2-opt

Effective heuristics and meta-heuristics for the quadratic assignment problem with tuned parameters and analytical comparisons. Mahdi Bashiri, Hossein Karimi

Busca TabuA origem da palavra tabu remonta ao Tongan, um idioma da Polinésia. A palavra era utilizada pelos nativos da ilha Tonga para indicar objetos que não podiam ser tocados por serem sagrados.O nome deste método vem das listas tabu, que consistem em listas com soluções (movimentos) não permitidas. Na sua forma mais básica, contém os últimos elementos visitados. Outras listas podem conter soluções proibidas devido a, por exemplo, certos atributos da solução ou movimentos ilegais no contexto do problema.

Busca Tabu

Movimentos Tabu: Ro-TSExemplo

Metaheuristics for Hard Optimization: Methods and Case Studies. Pag. 64. Johann Dréo, Alain Pétrowski, Patrick Siarry, Eric Taillard.

Busca Tabu

Parâmetrosvoid tabu_search(long n, // problem size

type_matrix & a, // flows matrix

type_matrix & b, // distance matrix

type_vector & best_sol, // best solution found

long & best_cost, // cost of best solution

long min_size, // parameter 1: 0.9n

long max_size, // parameter 2: 1.1n

long aspiration, // parameter 3: 2n²

long 1000000) // number of iterations

Robust taboo search procedure for the quadratic assignment problem (c++ program). Eric Taillard

Busca Tabu

Movimentos Tabu★ Pequeno número de movimentos tabu ⇒ descoberta de ótimos locais★ Pequeno número de movimentos tabu ⇒ repetição de soluções★ Grande número de movimentos tabu ⇒ diminui possibilidade de

repetições (confinamento) ⇒ aumenta possibilidade de visitar boas soluções

★ Grande número de movimentos tabu ⇒ diminui probabilidade de encontrar bons ótimos locais

Busca Tabu

Pequeno número de movimentos tabu

Busca Tabu

Grande número de movimentos tabu

Busca Tabu

Duração tabu aleatóriaPara se obter o benefício simultâneo das vantagens oferecidas por um pequeno número de movimentos tabu (permite a exploração profunda de um vale) e por um grande número de movimentos tabu (permite pular de um vale para outro), uma possibilidade é modificar essa duração durante o processo de busca.Por exemplo, pode ser usado um valor aleatório entre um limite inferior e superior a cada iteração ou a cada n iterações.Estes limites podem ser identificados, inclusive podem ser aumentados ou diminuídos com base em certas características observadas durante a busca.

Busca Tabu

Duração tabu aleatória// forbid reverse move for a fixed number of iterations

if(min_size == max_size) {

tabu_list[i_retained][p[j_retained]] = current_iteration + min_size;

tabu_list[j_retained][p[i_retained]] = current_iteration + min_size;

}

// forbid reverse move for a random number of iterations

else {

tabu_list[i_retained][p[j_retained]] = current_iteration + unif(min_size,max_size);

tabu_list[j_retained][p[i_retained]] = current_iteration + unif(min_size,max_size);

}

Robust taboo search procedure for the quadratic assignment problem (c++ program). Eric Taillard

Resultados

Ajuste de parâmetrosDuração da condição tabu

Busca Tabu

Critério de aspiraçãoUm movimento vai passar no critério de aspiração se:★ for um movimento que leve à maior redução no

custo da solução atual★ o movimento levar as facilidades à locais em que

ambos não tenham ocupado nas últimas t iterações

Busca Tabu

Critério de aspiraçãoExemplop = {3, 4, 2, 1, 5, 6}

m = (2, 5): 4 → 5, 5 → 2

last_assignment(4, 5) = i2; last_assignment(5, 2) = i

8

current_i = 22

2 < 22 - a ?

8 < 22 - a ?

Qual valor atribuir ao parâmetro a?

a grande ⇒ maior possibilidade de “libertar” movimento ⇒ aspiração aceita!

a pequeno ⇒ menor possibilidade de “libertar” movimento (mais rígido) ⇒ aspiração negada!

Resultados

Ajuste de parâmetrosCritério de aspiração

Resultados

Resultados

Resultados

NFI, 2-opt + Ro-TS

Referências

QAPLIB - A Quadratic Assignment Problem Library. R .E. Burkard, E. Çela, S. E. Karisch, F. Rendl. http://www.seas.upenn.edu/qaplib/

Robust taboo search for the quadratic assignment problem. E. Taillard.

Metaheuristics for Hard Optimization: Methods and Case Studies. Johann Dréo, Alain Pétrowski, Patrick Siarry, Eric Taillard.

Robust taboo search procedure for the quadratic assignment problem (c++ program). http://mistic.heig-vd.ch/taillard/codes.dir/tabou_qap.cpp

http://www.seas.upenn.edu/qaplib/

http://mistic.heig-vd.ch/taillard/codes.dir/tabou_qap.cpp

Obrigado.https://github.com/danielgribel/qap

https://github.com/danielgribel/qap

https://github.com/danielgribel/qap

Technology

QAP: Metodos construtivos, 2-opt, Busca tabu