Este artigo foi traduzido por máquina.
Execução de teste
Otimização de colônia de formigas
Na coluna deste mês apresento o código c# que implementa um algoritmo de Ant Colony Optimization (ACO) para resolver o problema do caixeiro (TSP). Um algoritmo ACO é uma técnica de inteligência artificial baseada no comportamento do pheromone-imposição de formigas; Ele pode ser usado para encontrar soluções para problemas extremamente complexos que procuram o caminho ideal através de um gráfico. A melhor maneira de ver onde eu estou cabeças é ter um olhar para a captura de tela na Figura 1. Neste caso, a demonstração é resolver uma instância do TSP, com o objetivo de encontrar o caminho mais curto que visita cada uma das 60 cidades exatamente uma vez. O programa de demonstração usa quatro formigas; cada formiga representa uma potencial solução. ACO requer a especificação de vários parâmetros, como o factor de influência do pheromone (alfa) e o coeficiente de evaporação do pheromone (rho), que explicarei mais tarde. As quatro formigas são inicializadas para trilhas aleatórias por 60 cidades; após a inicialização, a formiga melhor tem um comprimento de trilha mais curto de 245.0 unidades. A idéia chave de ACO é o uso de pheromones simulados, que atraem as formigas a melhores trilhas por meio do gráfico. O loop de processamento principal alterna entre as trilhas de formigas com base nos valores do pheromone atual de atualização e a atualização os pheromones com base em novas trilhas de formigas. Depois que o número máximo de vezes (1.000) através do loop de processamento principal, o programa exibe a melhor trilha encontrada e seu comprimento correspondente (61.0 unidades).
O gráfico de 60-cidade é artificialmente construído para que cada cidade está ligada a todas as outras cidades, e a distância entre as duas cidades é um valor aleatório entre 1,0 e 8.0 unidades arbitrárias (km, km e assim por diante). Não há nenhuma maneira fácil de resolver o TSP. Com 60 cidades, supondo que você pode começar em qualquer cidade e ir em frente ou para trás, e que todas as cidades estão ligadas, há um total de (60 - 1)! / 2 = 69,341,559,272,844,917,868,969,509,860,194,703,172,951,438,386,343,716,270,410,647,470,080,000,000,000,000 possíveis soluções. Mesmo que você poderia avaliar possíveis mil soluções por segundo, levaria cerca de 2.2 * 1063 anos para vê-los todos, que é muitas vezes maior do que a idade estimada do universo.
ACO é um aproximados, significando que é um quadro geral que pode ser usado para criar um algoritmo específico para resolver um problema de caminho do gráfico específico. Embora ACO foi proposto em uma tese de doutoramento de 1991 por M. Dorigo, a primeira descrição detalhada do algoritmo é geralmente atribuído a um documento de acompanhamento de 1996 por M. Dorigo, V. Maniezzo e a. Colorni. Desde então, ACO tem sido amplamente estudado e modificado, mas, um tanto curiosamente, muito poucas implementações completas e correctas estão disponíveis online.
Esta coluna supõe que você tenha habilidades de programação intermediário a avançado. Implementar o programa ACO usando c#, mas você não deve ter muita dificuldade refatoração meu código para um idioma diferente, como JavaScript. Eu decidi evitar todo o uso da programação orientada a objeto (OOP) para manter as ideias do algoritmo tão claro quanto possível. Por causa das limitações de espaço, eu não pode apresentar todo o código mostrado em execução Figura 1. Eu vou passar sobre as partes mais complicadas e você pode baixar o código completo do archive.msdn.microsoft.com/mag201202TestRun. Embora você pode nunca usar ACO código diretamente, muitas das suas técnicas, tais como seleção de roda Roleta, podem ser interessantes e útil adições à sua habilidade técnica definida.
.png)
Figura 1 Ant Colony Optimization em ação**
Estrutura do programa
Implementei o programa de demonstração ACO como um único aplicativo do console c#. A estrutura geral do programa, com a maioria das declarações de WriteLine removido, é mostrada na Figura 2. Embora algumas partes são complicados, o programa não é tão complicado quanto Figure2 sugere porque muitos dos métodos são métodos auxiliares curto.
Figura 2 Ant Colony Optimization programa estrutura
using System;
namespace AntColony
{
class AntColonyProgram
{
static Random random = new Random(0);
static int alpha = 3;
static int beta = 2;
static double rho = 0.01;
static double Q = 2.0;
static void Main(string[] args)
{
try
{
Console.WriteLine("\nBegin Ant Colony Optimization demo\n");
int numCities = 60;
int numAnts = 4;
int maxTime = 1000;
int[][] dists = MakeGraphDistances(numCities);
int[][] ants = InitAnts(numAnts, numCities);
int[] bestTrail = BestTrail(ants, dists);
double bestLength = Length(bestTrail, dists);
double[][] pheromones = InitPheromones(numCities);
int time = 0;
while (time < maxTime)
{
UpdateAnts(ants, pheromones, dists);
UpdatePheromones(pheromones, ants, dists);
int[] currBestTrail = BestTrail(ants, dists);
double currBestLength = Length(currBestTrail, dists);
if (currBestLength < bestLength)
{
bestLength = currBestLength;
bestTrail = currBestTrail;
}
++time;
}
Console.WriteLine("\nBest trail found:");
Display(bestTrail);
Console.WriteLine("\nLength of best trail found: " +
bestLength.ToString("F1"));
Console.WriteLine("\nEnd Ant Colony Optimization demo\n");
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}
} // Main
static int[][] InitAnts(int numAnts, int numCities) { .
.
}
static int[] RandomTrail(int start, int numCities) { .
.
}
static int IndexOfTarget(int[] trail, int target) { .
.
}
static double Length(int[] trail, int[][] dists) { .
.
}
static int[] BestTrail(int[][] ants, int[][] dists) { .
.
}
static double[][] InitPheromones(int numCities) { .
.
}
static void UpdateAnts(int[][] ants, double[][] pheromones,
int[][] dists) { .
.
}
static int[] BuildTrail(int k, int start, double[][] pheromones,
int[][] dists) { .
.
}
static int NextCity(int k, int cityX, bool[] visited, double[][] pheromones,
int[][] dists) { .
.
}
static double[] MoveProbs(int k, int cityX, bool[] visited,
double[][] pheromones, int[][] dists) { .
.
}
static void UpdatePheromones(double[][] pheromones, int[][] ants,
int[][] dists) { .
.
}
static bool EdgeInTrail(int nodeX, int nodeY, int[] trail) { .
.
}
static int[][] MakeGraphDistances(int numCities) { .
.
}
static double Distance(int cityX, int cityY, int[][] dists) { .
.
}
static void Display(int[] trail) { .
.
}
static void ShowAnts(int[][] ants, int[][] dists) { .
.
}
static void Display(double[][] pheromones) { .
.
}
}
}
Eu usei o Visual Studio para criar um programa de aplicativo de console chamado AntColony. Na janela Solution Explorer eu renomeado o arquivo padrão de Program. CS para AntColonyProgram.cs, que autoforma renomeada a única classe no projeto. Eliminei todos os modelo-gerado usando instruções exceto para o namespace de sistema — ACO normalmente não precisa de muito apoio de biblioteca. Os dois métodos principais são UpdateAnts e UpdatePheromones. Método UpdateAnts chama auxiliar BuildTrail, que chama NextCity, que chama MoveProbs. Método UpdatePheromones chama auxiliar EdgeInTrail, que chama IndexOfTarget.
Declarei um escopo de classe Random objeto chamado aleatório. Algoritmos ACO são probabilísticos, como você verá em breve. O alfa de variáveis de escopo de classe, beta, rho e q controlam o comportamento do algoritmo ACO. Eu uso esses nomes de variáveis, porque eles foram usados na descrição original de ACO.
Como configurar o problema
Eu usei o método MakeGraphDistances para definir um gráfico artificial:
static int[][] MakeGraphDistances(int numCities)
{
int[][] dists = new int[numCities][];
for (int i = 0; i < dists.Length; ++i)
dists[i] = new int[numCities];
for (int i = 0; i < numCities; ++i)
for (int j = i + 1; j < numCities; ++j) {
int d = random.Next(1, 9); // [1,8]
dists[i][j] = d; dists[j][i] = d;
}
return dists;
}
Para um problema gráfico do mundo real, você provavelmente teria ler gráfico -adjacência e distância entre nó dados de um arquivo de texto em algum tipo de estrutura de dados. Aqui eu simulado um gráfico, criando uma matriz de matrizes, onde o índice da linha que representa o índice de coluna j e da cidade representa a cidade. Observe que todas as cidades estão conectadas, distâncias são simétricas e a distância entre uma cidade e si é 0.
Assim que eu tiver uma estrutura de dados de distâncias que pode usá-lo para um método de distância:
static double Distance(int cityX, int cityY, int[][] dists)
{
return dists[cityX][cityY];
}
Para minimizar a quantidade de código apresentado, eu omiti normal erro verificando, tais como certificando-se de que os parâmetros cityY e cityX são válidos.
Iniciando as formigas e os Pheromones
Esta implementação não OOP, uma formiga é simplesmente uma matriz de valores de int que representa a trilha ou caminho, de uma cidade inicial através de todas as outras cidades. Uma coleção de formigas é uma matriz de matrizes em que o primeiro índice indica a formiga:
static int[][] InitAnts(int numAnts, int numCities)
{
int[][] ants = new int[numAnts][];
for (int k = 0; k < numAnts; ++k) {
int start = random.Next(0, numCities);
ants[k] = RandomTrail(start, numCities);
}
return ants;
}
O método de inicialização aloca uma linha para a trilha para cada formiga, escolhe uma cidade aleatória iniciar e, em seguida, chama um método auxiliar RandomTrail:
static int[] RandomTrail(int start, int numCities)
{
int[] trail = new int[numCities];
for (int i = 0; i < numCities; ++i) { trail[i] = i; }
for (int i = 0; i < numCities; ++i) {
int r = random.Next(i, numCities);
int tmp = trail[r]; trail[r] = trail[i]; trail[i] = tmp;
}
int idx = IndexOfTarget(trail, start);
int temp = trail[0]; trail[0] = trail[idx]; trail[idx] = temp;
return trail;
}
O auxiliar de RandomTrail aloca uma trilha e a inicializa para 0, 1, 2,... numCities-1. Em seguida, o método usa o algoritmo de shuffle do Fisher-Yates para randomizar a ordem das cidades da trilha. A cidade de início especificada é então localizada e trocada em trilha de posição [0].
Os Pheromones são lugar de formigas de produtos químicos em suas trilhas; eles atraem outras formigas. Formigas mais vão viajar em uma trilha mais curta para uma fonte de alimento — e depositar mais pheromones — do que em trilhas mais longo. Os pheromones evaporar lentamente ao longo do tempo. Aqui está o método InitPheromones:
static double[][] InitPheromones(int numCities)
{
double[][] pheromones = new double[numCities][];
for (int i = 0; i < numCities; ++i)
pheromones[i] = new double[numCities];
for (int i = 0; i < pheromones.Length; ++i)
for (int j = 0; j < pheromones[i].Length; ++j)
pheromones[i][j] = 0.01;
return pheromones;
}
Informações do pheromone são armazenadas em uma matriz simétrica de matriz de matrizes estilo onde a linha índice i é de cidade e o índice de coluna j é a cidade. Todos os valores são inicialmente definidos como um valor arbitrário pequeno (0,01) para ir começar o ciclo de UpdateAnts-UpdatePheromones.
Atualizando as formigas
A chave para o algoritmo ACO é o processo que atualiza cada formiga e trilha com a construção de um novo — esperamos melhor — trilha com base nas informações do pheromone e distância. Dê uma olhada Figura 3. Suponha que temos um gráfico pequeno com apenas cinco cidades. Em Figura 3 a trilha de nova para uma formiga está em construção. A trilha começa na cidade 1 e, em seguida, vai para a cidade 3, e o algoritmo de atualização é determinar a próxima cidade. Agora suponha que o feromônio e distância informações são como mostrado na imagem. O primeiro passo para determinar a próxima cidade é construir uma matriz eu chamado "taueta" (porque o papel de pesquisa original usado as letras gregas tau e eta). O valor de taueta é o valor do pheromone na borda elevado à potência alfa, vezes um sobre o valor de distance elevado à potência de beta. Lembre-se de que a alfa e beta são constantes globais que devem ser especificados. Aqui vou supor que alfa é 3 e beta é 2. Os valores de taueta para cidade 1 e 3 não são computados porque eles já estão na trilha atual. Observe que valores maiores do pheromone aumentam taueta, mas taueta diminuem a distâncias maiores.
.png)
Figura 3 Atualização Ant informações
Depois de tem sido computados todos os valores de taueta, o próximo passo é converter esses valores em probabilidades e colocá-las em uma matriz eu rotulados probs. O algoritmo de soma os valores de taueta, ficando 82.26 neste exemplo e, em seguida, divide cada valor de taueta pela soma. Neste ponto, cidade 0 tem uma probabilidade de 0,09 de sendo selecionado e assim por diante. Em seguida, o algoritmo deve selecionar a próxima cidade com base em probabilidades computadas. Como mencionado anteriormente, o algoritmo ACO que apresento neste artigo usa uma técnica de pura chamada seleção de roda de roleta. I construiu uma matriz aumentada chamada cumul, que detém cumulativas probabilidades. O tamanho da matriz aumentada é maior do que a matriz de probs e célula [0] é propagada com 0,0. Cada célula cumul é a soma cumulativa das probabilidades. Após a matriz cumul construída, é gerado um número p aleatório entre 0,0 e 1,0. Suponha que p = 0.538 conforme mostrado. Esse valor de p cai entre os valores em [2] e [3] na matriz cumul, que significa que [2], ou cidade 2, é selecionada como a próxima cidade.
O método de nível superior para a atualização é chamado UpdateAnts:
static void UpdateAnts(int[][] ants, double[][] pheromones, int[][] dists)
{
int numCities = pheromones.Length;
for (int k = 0; k < ants.Length; ++k) {
int start = random.Next(0, numCities);
int[] newTrail = BuildTrail(k, start, pheromones, dists);
ants[k] = newTrail;
}
}
Observe que cada formiga é atribuída a uma cidade de partida nova e aleatória em vez de preservar os antigos começar a cidade. A maioria do trabalho real é executada pelo método auxiliar BuildTrail, como mostrado na Figura 4.
Figura 4 O método de BuildTrail
static int[] BuildTrail(int k, int start, double[][] pheromones,
int[][] dists)
{
int numCities = pheromones.Length;
int[] trail = new int[numCities];
bool[] visited = new bool[numCities];
trail[0] = start;
visited[start] = true;
for (int i = 0; i < numCities - 1; ++i) {
int cityX = trail[i];
int next = NextCity(k, cityX, visited, pheromones, dists);
trail[i + 1] = next;
visited[next] = true;
}
return trail;
}
BuildTrail mantém uma matriz de Boolean visitou, para que a trilha criada não contém cidades duplicadas. O valor em trail [0] é inoculado com uma cidade de início e, em seguida, cada cidade é adicionada, por sua vez pelo método auxiliar NextCity, mostrado na Figura 5.
Figura 5 O método de NextCity
static int NextCity(int k, int cityX, bool[] visited,
double[][] pheromones, int[][] dists)
{
double[] probs = MoveProbs(k, cityX, visited, pheromones, dists);
double[] cumul = new double[probs.Length + 1];
for (int i = 0; i < probs.Length; ++i)
cumul[i + 1] = cumul[i] + probs[i];
double p = random.NextDouble();
for (int i = 0; i < cumul.Length - 1; ++i)
if (p >= cumul[i] && p < cumul[i + 1])
return i;
throw new Exception("Failure to return valid city in NextCity");
}
O método NextCity implementa o algoritmo de seleção de roda de roleta.Observe que o algoritmo irá falhar se o último valor na matriz cumul for maior que 1,00 (possivelmente devido a erros de arredondamento), e então você pode querer adicionar lógica para definir sempre cumul [cumul.Length-1] 1.00. NextCity requer uma matriz de probabilidades produzido pelo método auxiliar MoveProbs, mostrado na Figura 6.
Figura 6 O método de MoveProbs
static double[] MoveProbs(int k, int cityX, bool[] visited,
double[][] pheromones, int[][] dists)
{
int numCities = pheromones.Length;
double[] taueta = new double[numCities];
double sum = 0.0;
for (int i = 0; i < taueta.Length; ++i) {
if (i == cityX)
taueta[i] = 0.0; // Prob of moving to self is zero
else if (visited[i] == true)
taueta[i] = 0.0; // Prob of moving to a visited node is zero
else {
taueta[i] = Math.Pow(pheromones[cityX][i], alpha) *
Math.Pow((1.0 / Distance(cityX, i, dists)), beta);
if (taueta[i] < 0.0001)
taueta[i] = 0.0001;
else if (taueta[i] > (double.MaxValue / (numCities * 100)))
taueta[i] = double.MaxValue / (numCities * 100);
}
sum += taueta[i];
}
double[] probs = new double[numCities];
for (int i = 0; i < probs.Length; ++i)
probs[i] = taueta[i] / sum;
return probs;
}
Os valores de taueta podem ser muito pequenos (se o valor de distância é muito grande) ou muito grandes (se o valor do pheromone é grande), que pode produzir dificuldades para o algoritmo. Para lidar com isso, eu verificar os valores de taueta e impor valores max e min arbitrário.
Atualizando os Pheromones
Atualizando informações do pheromone é muito mais fácil do que atualizar as informações de trilha de formiga. As principais linhas de código no método UpdatePhermones são:
double length = Length(ants[k], dists);
double decrease = (1.0 - rho) * pheromones[i][j];
double increase = 0.0;
if (EdgeInTrail(i, j, ants[k]) == true)
increase = (Q / length);
pheromones[i][j] = decrease + increase;
Cada valor do pheromone é diminuída, simulando a evaporação e aumentado, simulando o depósito dos pheromones por formigas na trilha.O efeito de diminuição é produzido multiplicando o valor atual do pheromone por um factor inferior a 1.0 que depende de rho parâmetro global.O maior rho é, quanto maior for a diminuição do valor do pheromone.O efeito de aumento é produzido pela adição de uma percentagem do comprimento total da trilha de ant atual, onde a proporção é determinada pelo parâmetro global Q.Valores maiores do q aumentam a quantidade de feromônio adicionado.Auxiliar de chamadas de método UpdatePheromones EdgeInTrail, que determina se um segmento entre duas cidades é na trilha atual de ant.Você pode verificar o download do código deste artigo para obter os detalhes (archive.msdn.microsoft.com/mag201202TestRun).
Resumindo
Deixe-me enfatizar que existem muitas variações de ACO; a versão que apresentei aqui é apenas uma das muitas abordagens possíveis.Defensores ACO tem aplicado o algoritmo para uma ampla gama de problemas de otimização combinatória.Outro combinatória optimization algoritmos baseados no comportamento dos sistemas naturais incluem Simulated Annealing (SA), que abordei no mês passado (msdn.microsoft.com/magazine/hh708758) e simulados de abelha colônia (SBC), as quais abordei na minha coluna de abril de 2011 (msdn.microsoft.com/magazine/gg983491).Cada abordagem tem pontos fortes e fracos.Na minha opinião, a ACO é softwre para problemas muito semelhantes, o problema do caixeiro, enquanto SA e SBC são melhores para problemas de otimização combinatória mais gerais, como o agendamento.
ACO, em comum com outro meta-heurística baseada em sistemas naturais, é bastante sensível à sua escolha de parâmetros globais livre — alfa, beta e assim por diante.Embora tenha havido um pouco de pesquisa sobre parâmetros ACO, o consenso geral é que você deve experimentar um pouco com parâmetros grátis para obter a melhor combinação de desempenho e solução de qualidade.
Dr.James McCaffrey trabalha para a Volt Information Sciences Inc., onde gerencia o treinamento técnico para engenheiros de software que trabalham no Microsoft Redmond, Wash., campus. Ele trabalhou em vários produtos Microsoft, incluindo o Internet Explorer e o MSN Busca. McCaffrey é autor de ".NET Test Automation Recipes"(Apress, 2006) e pode ser contatado pelo email jmccaffrey@volt.com ou jammc@microsoft.com.
Graças aos seguintes especialistas técnicos da Microsoft para revisão deste artigo: Dan Liebling e Anne Loomis Thompson