相同的代码，不同的性能：模拟退火（Ruby vs Java）
我尝试将[http://www.cleveralgorithms.com/nature-inspired/physical/simulated_annealing.html][1]中给出的Ruby代码转换为使用模拟退火解决旅行商问题的Ruby代码，这两个代码运行时没有任何错误。但是，我发现它们在同一问题实例上的性能不同（来自TSPLIB的berlin52）。Ruby代码通常在9000到10000之间获得最佳解决方案，而Java代码在16000到17000之间获得最佳解决方案。我的Java代码中是否有任何部分没有得到很好的实现？我查过了，但没找到！提前谢谢
Ruby代码：
def euc_2d(c1, c2)
Math.sqrt((c1[0] - c2[0])**2.0 + (c1[1] - c2[1])**2.0).round
end
def cost(permutation, cities)
distance =0
permutation.each_with_index do |c1, i|
c2 = (i==permutation.size-1) ? permutation[0] : permutation[i+1]
distance += euc_2d(cities[c1], cities[c2])
end
return distance
end
def random_permutation(cities)
perm = Array.new(cities.size){|i| i}
perm.each_index do |i|
r = rand(perm.size-i) + i
perm[r], perm[i] = perm[i], perm[r]
end
return perm
end
def stochastic_two_opt!(perm)
c1, c2 = rand(perm.size), rand(perm.size)
exclude = [c1]
exclude << ((c1==0) ? perm.size-1 : c1-1)
exclude << ((c1==perm.size-1) ? 0 : c1+1)
c2 = rand(perm.size) while exclude.include?(c2)
c1, c2 = c2, c1 if c2 < c1
perm[c1...c2] = perm[c1...c2].reverse
return perm
end
def create_neighbor(current, cities)
candidate = {}
candidate[:vector] = Array.new(current[:vector])
stochastic_two_opt!(candidate[:vector])
candidate[:cost] = cost(candidate[:vector], cities)
return candidate
end
def should_accept?(candidate, current, temp)
return true if candidate[:cost] <= current[:cost]
return Math.exp((current[:cost] - candidate[:cost]) / temp) > rand()
end
def search(cities, max_iter, max_temp, temp_change)
current = {:vector=>random_permutation(cities)}
current[:cost] = cost(current[:vector], cities)
temp, best = max_temp, current
max_iter.times do |iter|
candidate = create_neighbor(current, cities)
temp = temp * temp_change
current = candidate if should_accept?(candidate, current, temp)
best = candidate if candidate[:cost] < best[:cost]
if (iter+1).modulo(10) == 0
puts " > iteration #{(iter+1)}, temp=#{temp}, best=#{best[:cost]}"
end
end
return best
end
if __FILE__ == $0
# problem configuration
berlin52 = [[565,575],[25,185],[345,750],[945,685],[845,655],
[880,660],[25,230],[525,1000],[580,1175],[650,1130],[1605,620],
[1220,580],[1465,200],[1530,5],[845,680],[725,370],[145,665],
[415,635],[510,875],[560,365],[300,465],[520,585],[480,415],
[835,625],[975,580],[1215,245],[1320,315],[1250,400],[660,180],
[410,250],[420,555],[575,665],[1150,1160],[700,580],[685,595],
[685,610],[770,610],[795,645],[720,635],[760,650],[475,960],
[95,260],[875,920],[700,500],[555,815],[830,485],[1170,65],
[830,610],[605,625],[595,360],[1340,725],[1740,245]]
# algorithm configuration
max_iterations = 2000
max_temp = 100000.0
temp_change = 0.98
# execute the algorithm
best = search(berlin52, max_iterations, max_temp, temp_change)
puts "Done. Best Solution: c=#{best[:cost]}, v=#{best[:vector].inspect}"
end
Java代码：
package localsearch;
import java.lang.reflect.Array;
import java.util.*;
public class SimulatedAnnealing {
public static Random rand = new Random();
public static double[][] berlin52 = {{565,575},{25,185},{345,750},{945,685},{845,655},
{880,660},{25,230},{525,1000},{580,1175},{650,1130},{1605,620},
{1220,580},{1465,200},{1530,5},{845,680},{725,370},{145,665},
{415,635},{510,875},{560,365},{300,465},{520,585},{480,415},
{835,625},{975,580},{1215,245},{1320,315},{1250,400},{660,180},
{410,250},{420,555},{575,665},{1150,1160},{700,580},{685,595},
{685,610},{770,610},{795,645},{720,635},{760,650},{475,960},
{95,260},{875,920},{700,500},{555,815},{830,485},{1170,65},
{830,610},{605,625},{595,360},{1340,725},{1740,245}};
public static void main (String[] args){
double[][] cities = berlin52;
// Algorithm configuration
int maxIterations = 2000;
double maxTemperature = 100000.0;
double tempChange = 0.98;
// Execute the algorithm
long startTime = System.currentTimeMillis();
Candidate best = search(berlin52, maxIterations, maxTemperature, tempChange);
long endTime = System.currentTimeMillis();
System.out.println("Done. Best Solution: c = " + best.cost + ", v = " + best.vector);
System.out.println("Time taken: " + (endTime - startTime) / 1000.0);
}
public static double euc2d(double[] c1, double[] c2){
return round(Math.sqrt(Math.pow(c1[0] - c2[0], 2.0) + Math.pow(c1[1] - c2[1], 2.0)), 0);
}
public static double cost(List<Integer> permutation, double[][] cities){
double distance = 0;
for (int i = 0; i < permutation.size(); i++) {
int c1 = i;
int c2 = (i == permutation.size()-1)? permutation.get(0) : permutation.get(i+1);
distance += euc2d(cities[c1], cities[c2]);
}
return round(distance, 4);
}
public static ArrayList<Integer> randomPermutation(double[][] cities){
int n = cities.length;
ArrayList<Integer> perm = new ArrayList<>();
for (int i = 0; i < n; i++)
perm.add(i);
for (int i = 0; i < n; i++) {
int r = (rand.nextInt(n) + i) % n;
Collections.swap(perm, i, r);
}
return perm;
}
public static List<Integer> stochasticTwoOpt(List<Integer> perm){
int c1 = rand.nextInt(perm.size());
while (c1 == 0)
c1 = rand.nextInt(perm.size());
int c2 = rand.nextInt(perm.size());
ArrayList<Integer> exclude = new ArrayList<>(Arrays.asList(c1, 0));
exclude.add((c1==0) ? perm.size()-1 : c1-1);
exclude.add((c1 == (perm.size()-1)) ? 0 : c1+1);
while (exclude.contains(c2))
c2 = rand.nextInt(perm.size());
if (c2 < c1){
int temp = c1;
c1 = c2;
c2 = temp;
}
return twoOpt(perm, c1, c2);
}
public static List<Integer> twoOpt(List<Integer> perm, int i, int j){
ArrayList<Integer> newPerm = new ArrayList<>(perm.subList(0, i));
ArrayList<Integer> reversedPortion = new ArrayList<>(perm.subList(i, j + 1));
Collections.reverse(reversedPortion);
newPerm.addAll(reversedPortion);
newPerm.addAll(perm.subList(j + 1, perm.size()));
return newPerm;
}
public static double round(double d, int numbersAfterDecimalPoint) {
double n = Math.pow(10, numbersAfterDecimalPoint);
double d2 = d * n;
long lon = (long) d2;
lon = ((long) (d2 + 0.5) > lon) ? lon + 1 : lon;
return (lon) / n;
}
public static class Candidate {
public double cost;
public List<Integer> vector;
public Candidate(List<Integer> vector, double cost){
this.vector = vector;
this.cost = cost;
}
public Candidate(){
vector = new ArrayList<>();
cost = 0.0;
}
public Candidate(Candidate candidate){
this.vector = new ArrayList<>(candidate.vector);
this.cost = candidate.cost;
}
}
public static Candidate createNeighbor(Candidate current, double[][] cities){
Candidate candidate = new Candidate();
candidate.vector = new ArrayList<>(current.vector);
candidate.vector = stochasticTwoOpt(candidate.vector);
candidate.cost = cost(candidate.vector, cities);
return candidate;
}
public static boolean shouldAccept (Candidate candidate, Candidate current, double temperature){
if(candidate.cost <= current.cost)
return true;
return Math.exp((current.cost - candidate.cost) / temperature) > rand.nextDouble();
}
public static Candidate search(double[][] cities, int maxIterations, double maxTemperature, double tempChange){
ArrayList<Integer> initPerm = randomPermutation(cities);
Candidate current = new Candidate(initPerm, cost(initPerm, cities));
double temp = maxTemperature;
Candidate best = new Candidate(current);
for (int iter = 0; iter < maxIterations; iter++) {
Candidate candidate = createNeighbor(current, cities);
temp *= tempChange;
if(shouldAccept(candidate, current, temp))
current = new Candidate(candidate);
if (candidate.cost < best.cost)
best = new Candidate(candidate);
if ((iter+1) % 10 == 0)
System.out.println("> iteration " + (iter+1) + ", temp = " + temp + ", best = " + best.cost);
}
return best;
}
}
共 (0) 个答案