Simulated Recozimento TSP
Eu estou olhando para implementar o algoritmo de recozimento simulado em Java para encontrar uma rota ideal para oProblema do vendedor em viagem, até agora eu implementei força bruta e estou olhando para modificar esse código, a fim de usar o recozimento simulado. Obviamente, a força bruta e o recozimento simulado são muito diferentes e usam funções muito diferentes.
Eu entendo que o recozimento simulado usa uma variável conhecida como a temperatura que então esfria enquanto o algoritmo é executado; com a temperatura começando alta e gradualmente esfriando por toda parte. Embora a temperatura seja alta, é mais provável que o algoritmo escolha soluções que sejam piores do que a corrente, eliminando os máximos locais como se encontraria no algoritmo de subida de morros similar. À medida que esfria, é mais improvável que o algoritmo aceite soluções piores e, assim, ele pode se concentrar em uma área específica e uma rota ideal é encontrada rapidamente.
Eu acredito que eu entendo como o algoritmo funciona, mas estou tendo problemas para colocar isso em Java, eu tenho duas classes; uma cidade chamada que contém apenas métodos para elaborar detalhes de cada cidade, comogetIndex
, getDistance
, etc. A classe de algoritmo lê de um arquivo de entrada e armazena-o em uma matriz (int [][]
)
O código abaixo é o algoritmo para força bruta, que é o que eu quero modificar para fazer simulated annealing, se alguém puder me ajudar, eu apreciaria massivamente.
public static void doBF()
{
int random1 = generateRand();
if (towns2.size() > random1)
{
Town town = towns2.get(random1);
visitedTowns[i] = town;
towns2.remove(town);
i++;
if (lastTown != 1000)
{
journey += town.getDistance(lastTown);
}
lastTown = town.getIndex();
}
else
{
doBF();
}
}