Este artigo foi traduzido por máquina.
Execução de teste
Os algoritmos tabu e o número máximo de grupos
Na coluna deste mês, eu vou apresentar uma solução avançada para o problema de camarilha máximo do gráfico. A solução usa o que chamou de um algoritmo de tabu, e eu falarei sobre como projetar e testar estes algoritmos. A idéia do problema camarilha máximo é encontrar o maior grupo de nós em um gráfico que estamos todos conectados um ao outro. Dê uma olhada no gráfico simple na Figura 1. O gráfico tem nove nós e 13 bordas. O gráfico é não ponderado (não há nenhuma prioridade associada com as bordas) e não dirigido (todas as bordas são bidirecional). Nós de 2, 4 e 5 formam um bando de tamanho três. A camarilha máxima é que o conjunto de nós 0, 1, 3 e 4, que forma uma panelinha de tamanho quatro.
Figura 1 gráfico para um algoritmo de Tabu máximo camarilha
O problema de camarilha máximo é interessante por várias razões. Embora não seja aparente do gráfico simple em Figura 1, o problema da camarilha máxima é uma das mais desafiadoras em ciência da computação. Ela surge em muitos problemas práticos importantes, tais como análise de comunicação de redes sociais, onde nós representam pessoas e bordas representam mensagens ou relações. E o problema usa técnicas tais como gananciosos algoritmos e técnicas de programação avançadas de algoritmos de tabu, que são importantes. Ter uma solução para o problema da camarilha máximo em sua biblioteca pessoal pode ser um útil instrumento prático e Noções básicas sobre o algoritmo usado pode adicionar novas técnicas para seu conjunto de habilidades.
Esta é a terceira coluna em uma série que utiliza o problema camarilha máximo para ilustrar avançado de codificação e teste técnicas, mas esta coluna pode ser lido sem referência direta aos dois anteriores. Na minha coluna de outubro, "Gráfico de estruturas e máximo camarilha" (msdn.microsoft.com/magazine/hh456397), descrevi como codificar uma estrutura de dados eficiente para manter uma estrutura de dados do gráfico na memória. Na minha coluna de novembro, "Algoritmos gananciosos e máximo camarilha" (msdn.microsoft.com/magazine/hh547104), descrevi como um algoritmo relativamente simple pode ser usado para encontrar uma solução para o problema difícil camarilha máximo.
Em termos informais, um algoritmo guloso é um algoritmo que começa com uma solução simple e incompleta para um problema difícil e, em seguida, iterativamente procura a melhor maneira de melhorar a solução. O processo é repetido até que alguma condição de parada é atingida. Comonunca, gananciosos algoritmos normalmente têm uma fraqueza: eles repetidamente vão gerar a mesma solução repetidamente. Tabu algoritmos são projetados para lidar com esta fraqueza. O tabu de palavra, por vezes escrito tabu, meio proibido. Em termos simples, tabu algoritmos mantém uma lista de dados proibidos. A parte de processamento do algoritmo não é permitida utilizar tabu dados até que alguns proíbem o tempo passou. Formas simples de uso de algoritmos de tabu um fixo proíbem a tempo. Algoritmos avançados tabu adaptarem o tempo proibir dinamicamente enquanto executa o algoritmo.
Figura 2 ilustra as idéias importantes de um algoritmo de tabu aplicada ao problema de camarilha máximo e mostra-lhe onde eu estou indo nesta coluna.
Figura 2 Tabu máximo Demo Clique Run
Eu tenho um aplicativo de console que começa por carregar na memória o gráfico correspondente ao que foi mostrado na Figura 1. O arquivo usa um formato de arquivo gráfico padrão chamado DIMACS. Criação e a codificação de uma estrutura de dados gráfico eficiente são um problema significativo em si. Eu expliquei o código de estrutura de dados do gráfico na minha coluna de outubro.
O algoritmo começa selecionando um único nó aleatoriamente e inicializando uma panelinha com esse nó. O algoritmo iterativamente tenta encontrar e adicionar o nó melhor que irá aumentar o tamanho da camarilha. Eu vou explicar o que melhor nó significa mais tarde. Se o algoritmo não é possível localizar um nó para adicionar, ele tenta encontrar o melhor nó para descartar da camarilha. Nos bastidores, o algoritmo lembra a última vez que cada nó foi movido para a atual camarilha de solução ou movido da camarilha. O algoritmo usa esta informação para proibir adicionando ou descartando recentemente usado nós para um determinado período de tempo. Esta é a parte do tabu do algoritmo.
O algoritmo reinicia-se de vez em quando, quando nenhum progresso na busca de uma melhor panelinha (maior). O algoritmo silenciosamente armazena as soluções (panelinhas), tem visto anteriormente. O algoritmo usa essas informações de histórico de solução para adaptar-se dinamicamente o tempo de proibir. Se o algoritmo mantém encontrando as mesmas soluções, aumenta o tempo de proibir a desencorajar nós recentemente utilizados sejam utilizados. Se o algoritmo não vê as mesmas soluções, diminui o tempo de proibir para que haja uma maior concentração de nós para escolher. Esta é a parte adaptativa do algoritmo tabu.
Na maioria das situações onde é utilizado um algoritmo guloso, a solução ideal não é conhecida, para que uma ou mais condições de paragem devem ser especificadas. Quando o algoritmo atinge uma condição de parada, a melhor solução encontrada é exibida.
Nas seções a seguem, eu vou levá-lo através do código que produziu a captura de tela na Figura 2. O código-fonte completo está disponível em code.msdn.microsoft.com/mag201112TestRun. Esta coluna supõe que você tem habilidades de programação de nível intermediário com uma linguagem C-família ou o Visual Basic.LÍQUIDO linguagem. Posso usar c#, mas eu escrevi o código para que você será capaz de Refatorar para outro idioma, como F # ou Python sem muita dificuldade se você quiser.
Estrutura geral do programa
A estrutura geral do programa mostrado na Figura 2 é apresentado no Figura 3. Eu decidi colocar todo o código em um aplicativo de console simples usando métodos estáticos para manter a simplicidade, mas você pode querer modularizar partes do código para bibliotecas de classe e usar uma abordagem orientada a objeto. O programa é menos complicado do que você pode suspeitar no olhando Figura 3 porque a maioria dos métodos são métodos auxiliares curto.
Figura 3 global programa estrutura
using System;
using System.Collections.Generic; // List<int>
using System.Text; // StringBuilder
using System.IO; // FileStream
using System.Collections; // Hashtable
namespace TabuMaxClique
{
class TabuMaxCliqueProgram
{
static Random random = null;
static void Main(string[] args) { ...
}
static List<int> FindMaxClique(MyGraph graph, int maxTime,
int targetCliqueSize) { ... }
static List<int> MakePossibleAdd(MyGraph graph,
List<int> clique) { ...
}
static bool FormsALargerClique(MyGraph graph,
List<int> clique, int node) { ...
}
static int GetNodeToAdd(MyGraph graph,
List<int> allowedAdd, List<int> possibleAdd) { ...
}
static int GetNodeToDrop(MyGraph graph, List<int> clique,
List<int> oneMissing) { ...
}
static List<int> MakeOneMissing(MyGraph graph,
List<int> clique) { ...
}
static List<int> SelectAllowedNodes(List<int> listOfNodes,
int time, int prohibitPeriod, int[] lastMoved) { ...
}
static int UpdateProhibitPeriod(MyGraph graph, List<int> clique,
int bestSize, Hashtable history, int time, int prohibitPeriod,
ref int timeProhibitChanged) { ...
}
static string ListAsString(List<int> list) { ...
}
private class CliqueInfo
{
// ...
}
}
public class MyGraph
{
// ...
private class BitMatrix
{
// ...
}
}
} // ns
O programa tem duas classes de alto nível, e cada uma dessas classes tem uma subclasse de auxiliar. TabuMaxCliqueProgram de classe contém o método Main e toda a lógica algoritmo, juntamente com subclasse CliqueInfo, que é usado para manter um histórico das soluções camarilha visto anteriormente. Classe MyGraph encapsula uma representação de gráfico eficiente e contém subclasse BitMatrix, que é usado para armazenar informações de adjacência de nó de forma condensada. Um objeto de Random de escopo de classe chamado aleatório é usado para inicializar a camarilha para um nó aleatório e para quebrar gravatas quando existem vários nós melhores para adicionar ou descartar.
Com algumas declarações WriteLine e try-catch código removido, o método Main é:
Console.WriteLine("\nBegin tabu algorithm maximum clique demo\n");
string graphFile = "..
\\..
\\DimacsGraph.clq";
MyGraph graph = new MyGraph(graphFile, "DIMACS");
int maxTime = 50;
int targetCliqueSize = graph.NumberNodes;
List<int> maxClique = FindMaxClique(graph, maxTime, targetCliqueSize);
Console.WriteLine("\nSize of best clique found = " + maxClique.Count);
Console.WriteLine(ListAsString(maxClique));
O gráfico é representado como um objeto de MyGraph definido pelo programa. O gráfico é carregado a partir de um arquivo de texto externo que usa o formato de arquivo DIMACS. O método de chave de MyGraph é AreAdjacent, que retorna true se dois nós estão conectados. Eu defini maxTime para 50 iterações para estabelecer uma condição de parada absoluto para o algoritmo guloso. Isso é artificialmente pequeno. Em um problema real máximo camarilha, o tempo máximo é tipicamente na faixa de 1.000 a 100.000. Eu definir tamanho de targetClique para estabelecer uma segunda condição de paragem; se uma camarilha é encontrada que tem o mesmo número de nós como existem no gráfico, a camarilha máxima deve foram encontrada. A maior parte do trabalho é feito pelo método FindMaxClique, que usa um algoritmo de tabu gananciosos, adaptável para procurar a camarilha maior possível. O método auxiliar ListAsString simplesmente cria uma representação de seqüência de caracteres de uma lista de <int> objeto.
O método de FindMaxClique.
O método FindMaxClique chama vários métodos auxiliares, que descreverei em breve. Em alto nível pseudocódigo, consta o algoritmo FindMaxClique Figura 4. O pseudocódigo deixa de fora vários detalhes importantes para maior clareza, mas apresenta os principais pontos do algoritmo.
Figura 4 algoritmo adaptável de Tabu máximo camarilha
initialize clique with a single node
get list of candidate nodes to add
loop until stop condition met
if there are nodes which can be added
get list of allowed nodes
if there are allowed nodes to add
find best node to add and add to clique
mark added node as recently used
record current clique
else
get list of allowed nodes to drop
if there are allowed nodes which can be dropped
find best node to drop and drop from clique
mark dropped node as recently used
record current clique
else
select a random node to drop and drop from clique
mark dropped node as recently used
record current clique
if lack of progress
restart algorithm
update list of candidate nodes
update prohibit time
end loop
return largest clique found
The FindMaxClique method definition begins:
static List<int> FindMaxClique(MyGraph graph, int maxTime,
int targetCliqueSize)
{
List<int> clique = new List<int>();
random = new Random(1);
int time = 0;
int timeBestClique = 0;
int timeRestart = 0;
int nodeToAdd = -1;
int nodeToDrop = -1;
...
O objeto camarilha local é o bando de solução atual. O objeto aleatório é instanciado com um valor arbitrário sementes de 1. A variável de tempo é o contador de loop de processamento principal do algoritmo. As variáveis timeBestClique e timeRestart são usadas para determinar se houve uma falta de progresso para que o algoritmo pode reativar a mesmo. Próximo:
int prohibitPeriod = 1;
int timeProhibitChanged = 0;
int[] lastMoved = new int[graph.NumberNodes];
for (int i = 0; i < lastMoved.Length; ++i) {
lastMoved[i] = int.MinValue;
}
Hashtable history = new Hashtable();
...
O período de proibição é inicializado para 1. Isso significa que — inicialmente, pelo menos — depois que um nó tem sido usado pelo algoritmo, não pode ser usado para uma iteração de tempo. Se eu tivesse utilizado um valor de 0, o efeito teria sido ter não proibir em todos os tempo. A maioria dos algoritmos de tabu usar um valor fixo para o tempo de proibir, mas o problema com essa abordagem é que a pesquisa mostrou que o melhor valor para um tempo fixo proibir varia de um problema para o problema. A abordagem adaptável apresento atualizações o tempo proibir enquanto o algoritmo é executado, com base no histórico das soluções anteriores. Eu chamo este tabu adaptável técnica, mas alguns trabalhos de pesquisa chamam a técnica reativa ou dinâmico.
A matriz de lastMoved é usada para determinar se um nó é permitido ou proibido a qualquer momento. O índice da matriz representa um nó, e o correspondente valor da matriz é o tempo que o nó foi movido pela última (adicionado ou descartado). Usando a matriz lastMoved, eu eliminam a necessidade de criar uma lista de nós permitidos explicitamente (ou, equivalentemente, proibida nós). Eu inicializar todas as células de lastMoved para int.MinValue assim que eu mais tarde pode determinar se um nó nunca foi usado.
O objeto Hashtable histórico contém uma coleção de panelinhas solução visto anteriormente. Cada item na tabela de hash é um objeto CliqueInfo, que eu vou descrever em detalhes mais tarde. Poderia ter usado um objeto dicionário genérico em vez do objeto Hashtable não-genérico. FindMaxClique continua:
int randomNode = random.Next(0, graph.NumberNodes);
clique.Add(randomNode);
List<int> bestClique = new List<int>();
bestClique.AddRange(clique);
int bestSize = bestClique.Count;
timeBestClique = time;
...
Eu inicializar a atual camarilha de solução para um nó aleatório do gráfico. Eu instanciar uma lista de bestClique para controlar a melhor solução camarilha (maior) encontrada pelo algoritmo. Em seguida vem:
List<int> possibleAdd = MakePossibleAdd(graph, clique);
List<int> oneMissing = MakeOneMissing(graph, clique);
...
O método MakePossibleAdd cria uma lista de todos os nós que podem ser adicionados para a camarilha atual para aumentar o tamanho da camarilha por 1. Em outras palavras, o método cria uma lista de nós que não estão na camarilha mas estão conectados para cada nó na camarilha. Esta lista de possibleAdd poderia ter uma contagem de 0 ou poderia conter nós proibidos. MakePossibleAdd chama o método auxiliar FormsALargerClique.
O método MakeOneMissing cria uma lista de todos os nós conectados a todos, mas exatamente um de nós no atual camarilha. Não é óbvio, mas acontece que manter essa lista cria uma maneira inteligente para determinar qual nó na atual camarilha é o melhor nó para descartar, como eu vou explicar mais tarde. O loop de processamento principal começa:
while (time < maxTime && bestSize < targetCliqueSize)
{
++time;
bool cliqueChanged = false;
...
O loop de processamento principal será encerrado quando é atingido o número máximo de iterações ou se for encontrada uma solução melhor com o tamanho de camarilha de destino. Eu uso a variável cliqueChanged para controlar a lógica de ramificação entre adicionando e soltando nós, como você verá. A lógica para adicionar um nó permitido é mostrada na Figura 5.
Figura 5 A lógica para adicionar um nó permitido
if (possibleAdd.Count > 0) {
List<int> allowedAdd = SelectAllowedNodes(possibleAdd, time,
prohibitPeriod, lastMoved);
if (allowedAdd.Count > 0) {
nodeToAdd = GetNodeToAdd(graph, allowedAdd, possibleAdd);
clique.Add(nodeToAdd);
lastMoved[nodeToAdd] = time;
clique.Sort(); cliqueChanged = true;
if (clique.Count > bestSize) {
bestSize = clique.Count;
bestClique.Clear();
bestClique.AddRange(clique);
timeBestClique = time;
}
}
}
O algoritmo verifica para ver se há todos os nós que irão aumentar o tamanho da camarilha atual. Se assim, o método SelectAllowedNodes cria uma lista de nós que são permitidos — ou seja, não tabu — da lista de nós que podem ser adicionados.
A linha chave SelectAllowedNodes é:
if (time > lastMoved[currNode] + prohibitPeriod)
result.Add(currNode); // Allowed
O currNode é um de nós na lista possibleAdd. A lógica verifica se tempo suficiente tem decorrido desde que o nó foi usado por último para que o nó é passado o período de proibição. Em caso afirmativo, o nó é adicionado à lista de nós allowedAdd.
Agora, se houver qualquer nós que são permitidos e aumentarão o tamanho da Camarilha, Método GetNodeToAdd determina o melhor nó para adicionar para a camarilha. O nó melhor é o nó na lista de allowedAdd que é mais ligado a nós na lista possibleAdd. A idéia é que você deseja adicionar um nó que lhe dará as maioria das possibilidades de encontrar um nó para adicionar na próxima iteração do algoritmo. Pode haver vários nós na lista allowedAdd que são vinculados como mais ligado a nós em possibleAdd. Em caso afirmativo, um de nós ligada é selecionado ao acaso. Depois de adicionar o nó melhor, a solução atual camarilha é classificada por razões que eu vou explicar mais tarde. O código para soltar um nó é:
if (cliqueChanged == false) {
if (clique.Count > 0) {
List<int> allowedInClique = SelectAllowedNodes(clique, time,
prohibitPeriod, lastMoved);
if (allowedInClique.Count > 0) {
nodeToDrop = GetNodeToDrop(graph, clique, oneMissing);
clique.Remove(nodeToDrop);
lastMoved[nodeToDrop] = time;
clique.Sort(); cliqueChanged = true;
}
}
}
...
Se o algoritmo não é possível adicionar um nó, ele tentará descartar um nó permitido na esperança de que backtracking irá produzir uma solução que permita um novo nó a ser adicionado na próxima iteração. A lista de nós na atual camarilha é filtrada pelo método SelectAllowedNodes para obter nós que não são tabu. O GetNodeToDrop escolhe o melhor de nós cair usando a lista de nós oneMissing.
A idéia é deixar cair o nó permitido em camarilha atual, que resultará em maior aumento na lista de nós possibleAdd. Uma maneira de fazer isso é para testar cada nó na lista de permitidos por realmente removê-la da camarilha atual e, em seguida, o tamanho da lista de possibleAdd resultante de computação. Mas há uma abordagem muito mais eficiente que usa uma lista de nós conectados a todos, mas exatamente um de nós no atual camarilha. Usando a lista de oneMissing de nós, a lista pode ser usada da seguinte maneira. Varredura através de cada nó em nós a camarilha permitidos e contar quantos nós na lista de oneMissing é notconnected para o nó de camarilha. O nó na lista de permitidos camarilha que é menos conectados a nós no oneMissing lista é o nó melhor para soltar. Depois de cair este nó conectado menos, todos os nós na lista oneMissing que não estavam conectados ao nó descartado agora serão totalmente conectados para os nós restantes a camarilha e, portanto, tornar-se novos possibleAdd nós.
Neste momento na lógica, ele não seria possível adicionar um nó permitido ou descartar um nó permitido. Para descolar-se, o algoritmo descarta um nó aleatório da camarilha atual:
if (cliqueChanged == false) {
if (clique.Count > 0) {
nodeToDrop = clique[random.Next(0, clique.Count)];
clique.Remove(nodeToDrop);
lastMoved[nodeToDrop] = time;
clique.Sort();
cliqueChanged = true;
}
}
...
Em seguida, as algoritmo verificações para ver se houve uma falta de progresso e, em caso afirmativo, reinicia-se:
int restart = 100 * bestSize;
if (time - timeBestClique > restart && time - timeRestart > restart) {
timeRestart = time;
prohibitPeriod = 1;
timeProhibitChanged = time;
history.Clear();
...
A variável de reinício é o número de iterações para permitir que exista nenhuma melhoria ou desde a última reinicialização. Aqui eu usar um valor de 100 vezes o tamanho da melhor solução atual. O valor a ser usado para o intervalo de reinício não é bem compreendido, e você pode querer tentar alternativas. (Eu usei um valor fictício de 2 para produzir mais reinicializações para a captura de tela na Figura 2). O valor que eu uso tem funcionado bem para mim na prática, no entanto. Se não houver uma reinicialização, o algoritmo redefine o tempo de proibir e limpa a tabela de hash história segurando panelinhas de solução que tem sido vistas. Observe que o algoritmo ainda não foi atualizada a tabela de hash da história. O código de reinicialização não, no entanto, redefine a matriz de lastVisited, que armazena informações sobre quando nós última foram adicionados ou retirados a camarilha de solução. Em seguida vem:
int seedNode = -1;
List<int> temp = new List<int>();
for (int i = 0; i < lastMoved.Length; ++i) {
if (lastMoved[i] == int.MinValue) temp.Add(i);
}
if (temp.Count > 0)
seedNode = temp[random.Next(0, temp.Count)];
else
seedNode = random.Next(0, graph.NumberNodes);
...
O algoritmo tenta propagar novamente a camarilha de solução com um nó que nunca foi usado antes. Se houver vários nós não utilizados, um é selecionado ao acaso. Se não houver nenhum nós não utilizados, um nó aleatório é selecionado. Em vez de usar um nó aleatório, uma alternativa inexplorada é selecionar o nó que foi menos recentemente movido. O código de reinicialização termina com o seguinte:
...
clique.Clear();
clique.Add(seedNode);
}
O loop de processamento principal e FindMaxClique agasalhar da seguinte forma:
...
possibleAdd = MakePossibleAdd(graph, clique);
oneMissing = MakeOneMissing(graph, clique);
prohibitPeriod = UpdateProhibitPeriod(graph, clique, bestSize,
history, time, prohibitPeriod, ref timeProhibitChanged);
} // Main processing loop
return bestClique;
}
As listas de possibleAdd e oneMissing são regeneradas. Uma alternativa é manter estruturas de dados auxiliares e atualizar essas duas listas em vez de recriá-los do zero. O método UpdateProhibitPeriod é o principal componente da parte adaptativa do algoritmo tabu e descreverei em breve.
Lembrando-se soluções anteriores
Método UpdateProhibitPeriod usa uma tabela de hash de soluções vistas anteriormente para aumentar ou diminuir o tempo de proibir dinamicamente. Lembre-se que uma solução é um bando que é uma lista de <int> de nós que estamos todos conectados um ao outro. Mas eu também preciso armazenar o tempo quando uma solução foi visto pela última vez. Portanto, eu encapsular uma solução camarilha e a última vez foi visto em uma classe de CliqueInfo constantes Figura 6.
Figura 6 A classe CliqueInfo
private class CliqueInfo
{
private List<int> clique;
private int lastSeen;
public CliqueInfo(List<int> clique, int lastSeen)
{
this.clique = new List<int>();
this.clique.AddRange(clique);
this.lastSeen = lastSeen;
}
public int LastSeen
{
get { return this.lastSeen; }
set { this.lastSeen = value; }
}
public override int GetHashCode()
{
StringBuilder sb = new StringBuilder();
for (int i = 0; i < clique.Count; ++i) {
sb.Append(clique[i]);
sb.Append(" ");
}
string s = sb.ToString();
return s.GetHashCode();
}
public override string ToString()
{
string s = "";
for (int i = 0; i < clique.Count; ++i)
s += clique[i] + " ";
return s;
}
}
Porque um item de CliqueInfo será adicionado para o objeto de Hashtable solução história, eu preciso de uma função de hash de GetHashCode personalizada. Escrever funções hash personalizado é surpreendentemente complicado, e uma discussão aprofundada de todas as questões envolvidas exigiria uma coluna inteira. Nessa situação, eu uso o mais simples — mas não o mais eficiente — abordagem. Posso criar uma representação de seqüência de caracteres de nós no campo camarilha, separado por espaços e, em seguida, usar o built-in String.GetHashCode. Por exemplo, se uma panelinha contido nós {3 5 8}, eu gerar "3 5 8" (com um espaço à direita) e, em seguida, gerar um código hash dessa Cadeia de caracteres. Lembre-se que panelinhas sempre são mantidas em uma ordem classificada, assim seria possível ter uma camarilha {3 5 8} e outro camarilha {8 3 5}. Eu coloque espaços entre os nós assim que clique {3 5 8} é distinto da camarilha {3 58}.
Atualizando a proibir o período
Método UpdateProhibitPeriod adaptativamente aumenta ou diminui o tempo de proibir baseado nas soluções camarilha visto anteriormente. O método começa:
static int UpdateProhibitPeriod(MyGraph graph, List<int> clique,
int bestSize, Hashtable history, int time, int prohibitPeriod,
ref int timeProhibitChanged)
{
int result = prohibitPeriod;
CliqueInfo cliqueInfo = new CliqueInfo(clique, time);
.
.
.
O método irá retornar um tempo de proibir que poderia ser o mesmo que o atual tempo de proibir. Um objeto CliqueInfo que contém a camarilha atual e a hora atual são instanciados, como mostrado aqui:
if (history.Contains(cliqueInfo.GetHashCode())) {
CliqueInfo ci = (CliqueInfo)history[cliqueInfo.GetHashCode
int intervalSinceLastVisit = time - ci.LastSeen;
ci.LastSeen = time;
if (intervalSinceLastVisit < 2 * graph.NumberNodes - 1) {
timeProhibitChanged = time;
if (prohibitPeriod + 1 < 2 * bestSize) return prohibitPeriod + 1;
else return 2 * bestSize;
}
}
else history.Add(cliqueInfo.GetHashCode(), cliqueInfo);
...
O código verifica para ver se a atual solução de camarilha, sob a forma de um objeto CliqueInfo, tem sido vista antes — ou seja, é o bando na tabela de hash a história? Se o atual camarilha tem sido vista antes, o algoritmo calcula quanto tempo tem sido desde a camarilha foi vista. Se esse intervalo é curto o suficiente, o tempo de proibir é incrementado (sujeito a um limite superior). A idéia é que, porque não tem sido muito longa desde que o atual camarilha foi vista, o algoritmo está gerando soluções duplicadas. Se aumentar o tempo de proibir, haverá mais nós tabu e, portanto, menos permitido nós, reduzindo as possibilidades de gerar soluções camarilha duplicados. Se a solução atual camarilha não tem sido vista antes, ele é adicionado para a tabela de hash da história.
O intervalo de "curto suficiente" é duas vezes o número de nós no gráfico, menos um. Isso é usado para determinar quando incrementar o tempo proibir. O melhor valor para usar aqui é outra questão em aberto na investigação camarilha máximo. O "limite" para o tempo de proibir é duas vezes o tamanho da solução atual mais conhecido. O melhor valor de limite superior é, como você pode adivinhar provavelmente até agora, outra pergunta de investigação aberta.
Neste momento, tanto a camarilha atual não tem sido vista antes, ou a camarilha tem sido vista antes mas o intervalo necessário para incrementar o tempo proibir não era pequeno o suficiente. Então o algoritmo agora verifica para ver se o período de proibição pode ser diminuído, que irá diminuir o número de nós de tabu e aumentar o número de nós permitidos, que por sua vez dá o algoritmo mais nós para adicionar ou descartar:
...
if (time - timeProhibitChanged > 10 * bestSize) {
timeProhibitChanged = time;
if (prohibitPeriod - 1 > 1)
return prohibitPeriod - 1;
else
return 1;
}
else {
return result; // no change
}
} // UpdateProhibitTime
Em vez de explicitamente a verificação para ver se ele foi "relativamente" tempo desde a camarilha atual foi vista, o algoritmo indirectamente verifica quanto tempo tem sido desde a atual camarilha foi vista, examinando o tempo quando o período de proibição foi alterado pela última vez. Mais uma vez, não é claro o melhor valor para "relativamente longo". Eu uso um valor 10 vezes o tamanho da melhor solução atual. Observe que o tempo de proibir não pode cair abaixo de 1.
Mais pesquisas
Resultados da investigação sobre o problema da camarilha máximo sugerem que uma abordagem gananciosa com um recurso de tabu adaptável oferece os melhores resultados globais ao desempenho e qualidade de solução são tidos em conta. DIMACS é uma organização de pesquisa que criou um conjunto de problemas de difícil gráfico camarilha em referência. Eu corri o código apresentado aqui contra um problema particularmente difícil de DIMACS (C2000.9) e o código rapidamente (em menos de dois segundos) encontraram uma panelinha com tamanho 76 que está dentro de 1,5 por cento do tamanho da solução mais conhecido de 77.
Em vários pontos nesta coluna, eu mencionei resultados da investigação sobre o problema da camarilha máximo. Se você está interessado nesta pesquisa, eu recomendo que você pesquisa na Web para trabalhos acadêmicos, escrito pelo seguinte: r. Battiti et al., w. Pullan et al. e k. Katayama et al. Diversos artigos por esses três autores e seus colegas foram meus referências primárias.
Uma área inexplorada promissora para o algoritmo de camarilha máximo apresentado aqui é incorporar algum formulário do que é chamado de pesquisa do planalto. Lembre-se que o algoritmo de camarilha máximo primeiro tenta adicionar um nó não-tabu para a solução atual camarilha. Então, se isso não for possível, o algoritmo descarta um nó de solução atual camarilha. A idéia da pesquisa do planalto é encontrar um nó na solução atual camarilha que pode ser trocada por um nó não na camarilha. Embora isso não aumentar o tamanho da camarilha atual, ele não diminuir o tamanho da Camarilha, tampouco.
Dr.James McCaffreytrabalha para a Volt Information Sciences Inc., onde gerencia o treinamento técnico para engenheiros de software, trabalhando com a Microsoft Redmond, Wash. campus. Ele trabalhou em vários produtos da Microsoft, incluindo o Internet Explorer e o MSN Busca. Dr. McCaffrey é o autor de ".NET Test Automation Recipes"(Apress, 2006) e pode ser alcançado em jammc@microsoft.com.
Graças aos seguintes especialistas técnicos para revisão deste artigo: Paul Koch, Dan Liebling, Ann Loomis Thompson e Shane Williams