Simulated annealing

13 de novembro de 2009 5 respostas

tnaires 13 de novembro de 2009

Bom dia pessoal.

Estou implementando o algoritmo simulated annealing para resolver o problema do caixeiro viajante - sim, é trabalho de faculdade :P - 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:

while (Double.compare(system.temperature(), 0) &lt;= 0) {

}

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

5 Respostas

entanglement 13 de nov. de 2009

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

while (Double.compare(system.temperature(), 0) <= 0) {   
  
}

) .

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,

while (Math.abs (system.temperature()) <= eps) {
}

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.

clone_zealot 13 de nov. de 2009

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.

tnaires 13 de nov. de 2009

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.

tnaires 13 de nov. de 2009

Olá clone_zealot, obrigado pelos comentários.

clone_zealot:
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:
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.

entanglement 24 de nov. de 2009

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.

Criado 13 de novembro de 2009

Ultima resposta 24 de nov. de 2009

Respostas 5

Participantes 3

5 Respostas

Topicos relacionados