Projeto E Analise De Algoritmos 2007 1 Projeto 2 Branch And

Branch and Bound

A abordagem utilizada na resolução do BPP-1 foi a técnica de Branch-and-Bound, que consiste basicamente em um método exato enumerativo que explora apenas regiões do espaço de soluções onde existe a possibilidade de uma solução ótima ser encontrada. A chave para esta técnica é ter um bom critério para decidir se uma região do espaço de soluções pode conter uma solução ótima, o que o critério faz é resolver uma relaxação do problema, considerando o conjunto de decisões tomadas até o momento na construção da solução, obtendo um lower bound (no caso de um problema de minimização) que indica que as soluções daquela região não possuem valor inferior ao mesmo, e então comparar este valor com o valor da função objetivo da melhor solução encontrada até o momento da busca (upper bound). Caso o lower bound seja menor que o upper bound, então o algoritmo continua explorando aquela região em busca da solução ótima (branch), caso contrário o algoritmo não segue na exploração da região considerada (bound). Seguindo este framework é fundamental então trabalhar com boas técnicas de obtenção tanto de lower's quanto de upper's bound. Além disto é preciso decidir de que forma o espaço de soluções é explorado durante o algoritmo, ou seja, como é feito o particionamento do mesmo e em que ordem as regiões são exploradas. As seções seguintes descrevem justamente os elementos adotados no branch and bound para o BPP-1, ou seja, a forma em que o espaço de soluções é explorado, a determinação do upper bound inicial e os lower bound's utilizados no algoritmo.

Exploração do Espaço de Soluções

A estratégia adotada para a exploração do espaço de soluções cosistiu em percorrer a árvore de busca de forma recursiva como uma busca em profundidade, onde o particionamento do espaço consistia em colocar um determinado item em cada bin possível existente e colocá-lo também em um novo bin. Além disto a sequência de análise dos items segue uma ordem não decrescente de peso. O pseudo-código a seguir resume apenas a estratégia de exploração adotada no algoritmo:

// Recebe como parametros a solucao construida atualamente e o item atual considerado
void branch-and-bound(Solucao &s, int itemAtual) {
    ...
    bool criou = false;
    // Percorre cada bin existente para tentar inserir o item atual nele
    for (int i=0; i<=s.nb; i++) {        
        // Se o item nao cabe no bin I, continua
        if (C - s.ocupado[i] < items[itemAtual]) continue;
 
        // Tenta colocar o item atual neste bin e chama recursivo
        s.bins[i].insert(itemAtual);
        s.ocupado[i] += items[itemAtual];
 
        // Cria novo bin
        if (i == s.nb) {
            s.nb += 1;
            criou = true;
        }
 
        // Chama recursivo para o proximo item
        branch-and-bound(s, itemAtual+1);
 
        // Desfaz as operacoes feitas para a chamada recursiva
        if (criou)
            s.nb -= 1;
        s.ocupado[i] -= items[step];
        s.bins[i].pop_back();
    }
    ...
}

Solução viável inicial (Upper Bound Inicial)

Como explicado anteriormente é muito importante para o desempenho do branch and bound trabalhar com um upper bound que tenha valor o mais próximo do valor da função objetivo da solução ótima. Um upper bound, para um problema de minimização, nada mais é que o valor da função objetivo de alguma solução viável conhecida, assim para obtermos um bom upper bound basta gerar uma solução viável de boa qualidade através de qualquer método heurístico. Para o BPP-1 o upper bound inicial foi determinado em duas etapas. A primeira etapa consiste em construir duas soluções utilizando os métodos heurísticos gulosos first fit e best fit, sendo o upper bound atualizado para o menor valor obtido entre as duas soluções. A segunda etapa consiste em tentar encontrar um upper bound melhor através da busca por soluções viáveis para o BPP-1 pela resolução do BPP-2 em instâncias com número de bins entre o lower bound inicial e o upper bound da primeira etapa.

Métodos Gulosos

Os métodos gulosos da primeira etapa trabalham escolhendo a cada iteração em que bin um determinado item será inserido, até que todos os items estejam em algum bin sem estorar as capacidades dos mesmos. Assim a chave dos procedimentos é o critério que determina em que bin o item será inserido, os critérios de cada um são:

  • First-fit - A cada iteração, o item atual é armazenado no bin de menor índice que tenha capacidade residual suficiente para armazena-lo. Se não existe um bin com capacidade residual suficiente, então um novo bin é criado e o item é armazenado no mesmo.
  • Best-fit - A cada iteração, o item atual é armazenado no bin que tenha a menor capacidade residual suficiente para armazena-lo. Se houver empate o bin de menor índice é escolhido. Se não existe um bin com capacidade residual suficiente, então um novo bin é criado e o item é armazenado no mesmo.

Estratégia Dual via Busca Tabu

Para melhorar o upper bound obtido na primeira etapa foi desenvolvida a estratégia descrita em [], que tem como elemento principal a meta-heurística busca tabu. A busca tabu é uma estratégia de busca local que tenta evitar a ciclagem entre soluções e o problema da busca ficar presa em um mínimo local. A descrição completa da busca tabu pode ser encontrada em [].

A construção de uma busca tabu efetiva para o BPP-1 tem o problema de que as restições de capacidade restringem muito a busca e a definição usual de movimentos (mudar um item de bin ou trocar dois items entre bins diferentes) dificilmente afeta o valor da função objetivo. Como consequência, todos os movimentos possíveis em uma dada iteração tem muitas vezes o mesmo valor de função objetivo, não ficando claro qual movimento deve ser escolhido. Para lidar com este problema a estratégia proposta em [] utiliza a relação próxima entre o BPP-1 e o BPP-2. Esta estratégia é chamada de dual, e pode ser descrita da seguinte forma: iniciando com o melhor valor de lower bound encontrado, tenta-se encontrar uma solução do BPP-2 para a instância tendo o número de bins igual ao do lower bound onde valor de sua função objetivo seja inferior a capacidade dos bins da instância original do BPP-1. Caso esta solução tenha sido encontrada ela o upper bound é então atualizado e o algoritmo termina. Caso contrário, aumenta-se o número de bins da instância do BPP-2 e novamente o resolve na busca de uma solução viável para o BPP-1. Este procedimento continua até que o número de bins da instância do BPP-2 se torna igual ao melhor upper bound já encontrado, se for este o caso o algoritmo para. A vantagem desta estratégia é que é mais natural se desenvolver um método heurístico de busca local como a busca tabu para resolver o BPP-2, já que o problema de similaridade da função objetivo entre soluções vizinhas é mínimo.

A estratégia para resolver as instâncias descritas do BPP-2 foi inicialmente gerar uma solução gulosa e em seguida aplicar a busca tabu. A solução gulosa simplesmente escolhia a cada iteração o bin que o item considerado seria armazenado como sendo o bin com o menor peso já armazenado, até que todos os items estivessem em algum bin. A busca tabu desenvolvida tem as seguintes características:

  • Vizinhança - De uma solução atual x, soluções vizinhas x' são obtidas através de dois tipos de movimentos simples. Ou um item $j$ é movido de seu bin atual $h$ para um novo bin $i$ (shift), ou dois items $j$ e $k$ são trocados de seus bins atuais $h$ e $i$ (swap).
  • Lista tabu - A lista tabu consiste de uma matriz de dimensões número de bins X número de items onde uma determinada posição $t[i][j]$ indica o status tabu do movimento que deseja armazenar o item $j$ no bin $i$. Quando é realizado um shift, o movimento de armazenar o item deslocado para a seu bin de origem é tornado tabu por um determinado número de iterações. Quando um swap é realizado os movimentos de retornar cada item para seu bin original são tornados também tabu. Um shift só é permitido se a mudança de bin do item não tem status tabu, já no swap as duas mudanças de bins não podem ter status tabu para que o mesmo seja permitido.
  • Seleção de movimento - O movimento escolhido em uma determinada iteração da busca é aquele que não tem status tabu e o que leva ao menor valor da função objetivo.
  • Critério de parada - O algoritmo para se um determinado número de iterações é atingido ou se a viabilidade da solução para o BPP-1 é alcançada.

O número de iterações em que o movimento fica tabu foi fixado em metade do número de items e limite de iterações do algoritmo foi fixado em dez vezes o número de items. O pseudo-código a seguir descreve em linhas gerais a estratégia dual:

// Procedimento principal da estrategia dual
int hybridUB(){
    // Itera sobre os valores que podem representar melhorias no Upper Bound
    for(int i=bestLower; i<bestUpper; i++){
        Solucao s;
        // Cria a solucao gulosa para o BPP-2
        int maxBin = criarDualWorstFit(s,i);
        // Se o bin mais pesado da solucao eh menor que a capacidade retorne o novo upper bound
        if(maxBin <= C) 
            return i;
        // Aplica a busca tabu na solucao gulosa
        maxBin = tabuSearch(s,i,N*10,N/2);
        // Se o bin mais pesado da solucao eh menor que a capacidade retorne o novo upper bound
        if(maxBin <= C) 
            return i;
    }
}
 
// Procedimento de busca tabu para o BPP-2
int tabuSearch(Solucao & s, int nb, int numIter, int tabuTenure){
    Inicializa a tabuList;
    bool viavel = false;
    for(int iter=0; iter<numIter && !viavel; iter++){
        move = escolhe o melhor movimento nao tabu;
        if(move.moveType == SHIFT){
            realiza o shift entre do item a do bin h para o bin k;
            torna o movimento de armazenar a em h como tabu pelas proximas tabuTenure iteracoes;
        }
        else if(moveType == SWAP){
            realiza o swap entre item a do bin h e o item b do bin k;
            torna o movimento de armazenar o item a no bin h como tabu pelas proximas tabuTenure iteracoes;
            torna o movimento de armazenar o item b no bin k como tabu pelas proximas tabuTenure iteracoes;
        }
        // Se o maior peso total armazenado em um bin eh menor que a capacidade do mesmo a soucao eh viavel para o BPP-1
        if(atual.ocupado[atual.heaviestBin] <= C)
            viavel = true;
    }
    return s.ocupado[s.heaviestBin];
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.