Métodos de busca baseados em otimização local freqüentemente confiam em estratégia de diversificação para aumentar sua efetividade em explorar o espaço de solução definido pelos problemas de otimização combinatorial. Algumas dessas estratégias são desenhadas com o propósito principal de prevenir o processo de busca da ciclagem . Outras estratégias são introduzidas para conceder robustez ou vigor adicionais para a busca. Na BT, a diversificação pode ser criada até certo ponto por funções de memória de curto prazo, como a alternância do valor da permanência ao longo da busca. Mas é particurlarmente reforçada por certas formas
de memória de longo prazo. Estratégias de diversificação em BT, como seu nome sugere, são desenhadas para direcionar a busca para novas regiões, ou seja, redirecionar a busca para regiões ainda não exploradas. Uma forma simples de implementar estratégias de diversificação consiste em modificar a função objetivo de modo a tornar menos atrativos valores próximos e mais atrativos valores afastados da vizinhança. Com esta estratégia é mais difícil encontrar ótimos locais (GLAZAR, 2000). Segundo GLOVER e LAGUNA (1997) as estratégias de intensificação são baseadas na modificação das regras de escolha dos movimentos e por processo de reinicialização. No primeiro caso, são efetuadas modificações nas regras de escolha para encorajar combinações de movimentos e características de soluções historicamente encontradas boas. No segundo caso, um processo de reinicialização propicia um retorno a regiões atrativas para explorar o espaço de soluções mais profundamente.
Segundo GLOVER e LAGUNA (1997), o uso combinado das estratégias de intensificação e diversificação pode tornar a BT ainda mais eficiente. Num horizonte de longo prazo, esta combinação pode permitir a busca alternar entre uma seqüência de passos que intensificam a busca em uma região promissora e passos que diversificam a busca alcançando regiões com características contrastantes. Isto pode ser obtido intensificando a busca numa região, até que um determinado número de iterações seja executado, sem que haja melhora na melhor solução até então encontrada. A partir daí, diversifica-se a busca para outras regiões.
4.5. Lista tabu
A lista tabu é representada por uma matriz onde são armazenadas o status tabu do movimento. Um movimento considerado tabu é proibido de ser gerado por um número de iterações iguais à sua permanência tabu, evitando que a busca retorne a soluções recentemente visitada. Não existe uma regra universal para definição da estrutura da lista tabu e nenhuma estrutura que seja melhor par todas as aplicações. A estrutura dessa lista depende muito mais do problema em questão. Entretanto, algumas regras podem ser levadas em consideração no momento em
que se planeja a estrutura da lista (GLOVER e LAGUNA, 1997). Segundo estes mesmos autores, se o tamanho da vizinhança é pequeno o suficiente para armazenar um item de informação para cada atributo do movimento usado para definir uma restrição tabu, em geral é vantajoso armazenar o número da iteração que identifica quando a restrição tabu será descartada. Isto faz com que o estado tabu de um movimento seja testado em tempo constante.
4.6. Atributos de movimento
Para transformar de uma solução x em outra solução x’ através de um mecanismo de movimento, utiliza-se os atributos de movimento. Segundo Glover e Laguna (1993) citados por GLAZAR (2000), os atributos de movimentos mais comuns são:
• alteração do valor de uma variável xj de 0 para 1;
• alteração do valor de uma variável xj de 1 para 0;
• as alterações de (1) e (2) simultaneamente, para dois diferentes valores de j; • alteração do valor da função objetivo de c(xa) para c(xt);
• alteração do valor de uma função g(xa) para g (xt) onde g pode representar uma função que ocorre naturalmente no problema, ou que é criada estrategicamente. Por exemplo, g pode ser uma medida de distância entre alguma solução dada, e uma solução referência, como a melhor solução até então encontrada.
• alteração no valor da diferença g(xt) - g (xa);
• alterações combinadas dos dois últimos atributos, para mais de uma função g, consideradas simultaneamente.
4.7. Critérios de aspiração
Critérios de aspiração são introduzidos na busca tabu para determinar quando as regras de ativação tabu podem ser anuladas, removendo-se assim a classificação tabu aplicada ao movimento. O domínio do estado tabu dos movimentos através dos critérios de aspiração podem ser muito importantes para capacitar o método de BT a
alcançar seu melhor nível de performance, evitando que soluções não atrativas sejam visitadas.
Os principais critérios de aspiração são (GLOVER e LAGUNA, 1997):
• aspiração default : Em situações onde a vizinhança seja eventualmente pequena, ou quando a permanência tabu seja suficientemente grande é possível que uma iteração possa ocorrer quando todos movimentos disponíveis são classificados como tabu. Este critério permite que, nessas situações onde todos os movimentos possíveis são classificados de tabu e nenhum deles levar a uma melhora da solução, o movimento com a condição tabu mais antiga seja executado;
• aspiração por objetivo: Este critério permite que um movimento tabu seja executado se levar a uma solução melhor que a solução até então encontrada.
4.8. Oscilação estratégica
Oscilação estratégica está intimamente ligada à origem da BT, e produz uma forma de realizar uma interação efetiva entre intensificação e diversificação (GLOVER e LAGUNA, 1997). Segundo GLAZAR (2000), a oscilação estratégica é uma modificação no método das penalidades e representa uma outra forma de diversificação interessante. De acordo com GLOVER e LAGUNA (2000), a idéia desse método é oscilar entre regiões viáveis e inviáveis, manipulando a função objetivo, através de penalidades ou incentivos, ou alterando movimentos construtivos (melhora da função objetivo) e destrutivo ( piora da função objetivo).
Segundo GLAZAR (2000), o uso da oscilação estratégica tem várias vantagens: permite executar movimentos menos complexos; o movimento direcionado para fora da fronteira de viabilidade e seu retorno em diferentes direções abre oportunidades para a melhorar as soluções que não seriam obtidas se a busca ficasse confinada; e finalmente, se o espaço de soluções viáveis é disjunto, então a oscilação estratégica provê um mecanismo de atravessar regiões de inviabilidade.
Gendrau et al., 1994; citados por GLAZAR (2000), propuseram o seguinte método de oscilação estratégica: para cada restrição i relaxada, uma penalidade pi é multiplicada ao excesso da violação desta restrição e adicionada a função objetivo de minimização. Esta penalidade é alterada a cada Lp iterações, utilizando-se pesos (γ) através dos seguintes critérios:
• se todas as Lp soluções anteriores foram viáveis, então pi = pi/γ;
• se todas as Lp soluções anteriores foram inviáveis, então pi = γ pi;
• caso contrário, não altere.
• segundo os mesmos autores, os valores mais usados para Lp e γ são, respectivamente, de 10 e 2.
4.9. Classificação da busca tabu
Os algoritmos baseados na BT são divididos em duas classes, de acordo com a natureza do sistema, determinístico ou estocásticos, que por sua vez são subdivididos de acordo com algumas características de implementação (GLAZAR, 2000). A classificação apresentada no Quadro1 e discutida a seguir foi extraída do trabalho de GLAZAR (2000).
Quadro 1 - Classificação dos algoritmos baseados na Busca Tabu
DETERMINÍSTICO ESTOCÁSTICO
BT estrita (strict TS) BT probabilística BT fixada (fixed TS) BT robusta BT reativa (reactive TS,
RTS)
BT fixada com tie breaking estocástico
BT paralela BT reativa com tie breaking estocástico
BT reativa com amostra da vizinhança (estratégia de lista de candidatos estocásticos)
em que: TS (Tabu Search).
• BT estrita: uma solução da vizinhança é proibida se, e somente se, ela já foi visitada no passado.
• BT fixada: um movimento é considerado tabu durante um intervalo de |T| iterações.
• BT reativa: o tamanho |T| da lista é ajustado automaticamente durante a pesquisa, identificando ciclos de soluções já visitadas.
• BT paralela: são realizados cálculos paralelos para a avaliação de diferentes movimentos.
• BT probabilística: as restrições tabu são substituídas por regras de probabilidade, onde baixas probabilidades proíbem o movimento.
• BT robusta: o tamanho |T| da lista tabu é escolhido aleatoriamente dentre um valor máximo e um valor mínimo durante a pesquisa.
• BT reativa e BT fixada com tie breaking estocástico: desempate entre os melhores movimentos é feito através de regras aleatórias.
• BT reativa com amostra da vizinhança: quando a avaliação de toda a vizinhança é cara, uma amostra estocástica da vizinhança é avaliada através da estratégia de lista de candidatos estocástica.