Simulated annealing

Bom dia pessoal.

Estou implementando o algoritmo simulated annealing para resolver o problema do caixeiro viajante - sim, é trabalho de faculdade

- e, se possível, gostaria de colher opiniões sobre uma questão.

Estou usando double para armazenar o valor da temperatura do sistema, e uma das condições de parada do algoritmo é quando a temperatura chega a (ou se aproxima de) zero. No meu caso estou implementando o laço da seguinte forma:

Porém o algoritmo às vezes não finaliza sua execução por causa da imprecisão do tipo de dados double. Eu tenho duas opções:

1) Usar BigDecimal, que é preciso mas é mais custoso. Tenho dúvidas se seria uma boa opção por causa da performance, uma vez que as instâncias do caixeiro viajante podem possuir dezenas de milhares de cidades;
2) Mudar a comparação para tolerar uma temperatura próxima de zero ao invés de exatamente igual. Nesse caso, qual seria o valor ideal?

Desde já agradeço a atenção de todos. Abraços

GUJ Hacker Membro desde: 26/09/2009 09:18:56 Mensagens: 5750 Offline

Algoritmos de cálculo numérico não devem usar esse tipo de comparação contra um valor exato. (

) .

Pra começar, Double.compare (t1, t2) <= 0 é um desperdício de tempo; use t1 <= t2.

Eles SEMPRE devem usar tolerâncias. Ou seja, o correto é usar, no seu caso,

onde eps é um valor que você deve configurar. Digamos que seja 1E-5, mas não conheço seu algoritmo tão detalhadamente que possa saber se 1E-5 é um valor muito baixo ou alto demais.

JavaEvangelist Membro desde: 21/11/2004 16:40:00 Mensagens: 424 Offline

Isso é um trabalho de faculdade, correto?
Pois bem, existe necessidade de vc se preocupar com performance? Ainda mais que estamos falando de caixeiro-viajante, que é um problema complexo...

Não estou falando que foi ruim vc ter pensado nisso. Muito pelo contrário!!! É ótimo ver que vc se preocupa com esse tipo de coisa. Mostra que vc é/será um bom desenvolvedor, mas talvez o que realmente importa seja a lógica do algoritmo, e não esse tipo de coisa.

Estou te incentivando a manter o foco no problema, e não na solução. Se, para esse trabalho, o professor exigir que o algoritmo rode num tempo y, OK, você deve se preocupar com isso. Com contrário, se preocupe com o objetivo.

E outra coisa: pq vc não transforma esses valores decimais em valores inteiros? Tipo, vc sabe qual o menor valor que será de entrada?
Digamos que seja 0,0001 grau. Bastaria vc multiplicar TODOS os valores de temperatura por 10.000 e vc só precisará trabalhar com inteiros. Dai vc não precisar se preocupar com a aritmética de ponto flutuante do Java.

This message was edited 1 time. Last update was at 13/11/2009 15:29:36

entanglement, obrigado pelas recomendações, ajudaram bastante.
Eu queria realmente saber qual o valor exato pra usar como tolerância; acho que vou ter que descobrir empiricamente.

Olá clone_zealot, obrigado pelos comentários.

clone_zealot wrote:Isso é um trabalho de faculdade, correto?
Pois bem, existe necessidade de vc se preocupar com performance? Ainda mais que estamos falando de caixeiro-viajante, que é um problema complexo...

Não estou falando que foi ruim vc ter pensado nisso. Muito pelo contrário!!! É ótimo ver que vc se preocupa com esse tipo de coisa. Mostra que vc é/será um bom desenvolvedor, mas talvez o que realmente importa seja a lógica do algoritmo, e não esse tipo de coisa.

Estou te incentivando a manter o foco no problema, e não na solução. Se, para esse trabalho, o professor exigir que o algoritmo rode num tempo y, OK, você deve se preocupar com isso. Com contrário, se preocupe com o objetivo.

Preciso me preocupar com performance porque meu trabalho é justamente uma análise de desempenho de diferentes algoritmos de busca na resolução do problema do caixeiro viajante, entre eles simulated annealing. Não é um trabalho qualquer na verdade, trata-se da minha monografia. Além do mais, como já falei antes, terei instâncias do problema que poderão conter dezenas de milhares de cidades - o algoritmo genético, por exemplo, passa umas duas horas rodando - e usar BigDecimal pode influenciar. Queria justamente saber se alguém já implementou o simulated annealing alguma vez pra me responder se essa preocupação é relevante ou não.

clone_zealot wrote:E outra coisa: pq vc não transforma esses valores decimais em valores inteiros? Tipo, vc sabe qual o menor valor que será de entrada?
Digamos que seja 0,0001 grau. Bastaria vc multiplicar TODOS os valores de temperatura por 10.000 e vc só precisará trabalhar com inteiros. Dai vc não precisar se preocupar com a aritmética de ponto flutuante do Java.

Ótima sugestão. No entanto o uso de números de ponto flutuante é mais cômodo de fato pois há uma fórmula do algoritmo que utiliza a constante de Boltzmann, e trabalhar com cálculos inteiros usando essa constante vai render um trabalho extra que eu não quero ter. A performance é importante sim, mas não a esse ponto, creio.

GUJ Hacker Membro desde: 26/09/2009 09:18:56 Mensagens: 5750 Offline

Se você vai usar uma máquina como um Core 2 Duo ou um Phenom ou mesmo um Pentium antigão, usar aritmética de ponto flutuante é muito, muito mais rápido que usar BigDecimal, porque o próprio processador implementa a aritmética de ponto flutuante (ou via "coprocessador", ou via SSE2 ou SSE3).
Se não me engano, é mais rápido fazer uma multiplicação de ponto flutuante em vários desses processadores que fazer uma multiplicação inteira. Mas é questão de testar.
Usar BigDecimal ou BigInteger deve ser relegado a casos especiais.

Notícias, artigos e o maior fórum brasileiro sobre Java