Java-имитация отжига из псевдокода - PullRequest
Новая
       30

Java-имитация отжига из псевдокода

6 голосов
/ 26 марта 2011

В настоящее время я работаю над проектом (TSP) и пытаюсь преобразовать псевдокод с имитацией отжига в Java. В прошлом я преуспел в преобразовании псевдокода в код Java, однако мне не удалось успешно его преобразовать.

Псевдокод: 

T0(T and a lowercase 0)    Starting temperature
Iter    Number of iterations
λ    The cooling rate

1.  Set T = T0 (T and a lowercase 0)
2.  Let x = a random solution
3.  For i = 0 to Iter-1
4.  Let f = fitness of x
5.  Make a small change to x to make x’
6.  Let f’ = fitness of new point
7.  If f’ is worse than f then
8.      Let p = PR(f’, f, Ti (T with a lowercase i))
9.      If p > UR(0,1) then
10.         Undo change (x and f)
11.     Else
12.         Let x = x’
13.     End if
14.     Let Ti(T with a lowercase i) + 1 = λTi(λ and T with a lowercase i)
15. End for
Output:  The solution x

Если бы кто-то мог показать мне базовую разметку этого в Java, я был бы чрезвычайно благодарен - я просто не могу понять это!

Я работаю в нескольких классах, используя ряд функций (которые я не буду перечислять, поскольку это не имеет отношения к тому, что я спрашиваю). У меня уже есть метод smallChange() и функция fitness - может ли быть шанс, что мне потребуется создать несколько различных версий указанных методов? Например, у меня есть что-то вроде: 

public static ArrayList<Integer> smallChange(ArrayList<Integer> solution){

//Code is here.

}

Может, мне понадобится другая версия этого метода, которая принимает другие параметры? Что-то вроде: 

public static double smallChange(double d){

//Code is here.

}

Все, что мне нужно, - это базовое представление о том, как это будет выглядеть при написании на Java, - я смогу адаптировать его к своему коду, когда узнаю, как оно должно выглядеть в правильном синтаксисе, но, похоже, не могу пройти это конкретное препятствие.

Спасибо.

Mick

Ответы [ 3 ]

5 голосов
/ 26 марта 2011

Вы можете сравнить свой ответ с кодом, предоставленным для учебника
Искусственный интеллект в современном подходе .

5 голосов
/ 26 марта 2011

Основной код должен выглядеть следующим образом: 

public class YourClass {
  public static Solution doYourStuff(double startingTemperature, int numberOfIterations, double coolingRate) {
    double t = startingTemperature;
    Solution x = createRandomSolution();
    double ti = t;

    for (int i = 0; i < numberOfIterations; i ++) {
      double f = calculateFitness(x);
      Solution mutatedX = mutate(x);
      double newF = calculateFitness(mutatedX);
      if (newF < f) {
        double p = PR(); // no idea what you're talking about here
        if (p > UR(0, 1)) { // likewise
          // then do nothing
        } else {
          x = mutatedX;
        }
        ti = t * coolingRate;
      }
    }
    return x;
  }

  static class Solution {
    // no idea what's in here...
  }
}

Теперь, когда вам нужны разные версии метода smallChange () - это вполне выполнимо, но вы должны прочитать о наследовании немного

3 голосов
/ 29 марта 2011

Кроме того, Java-подход к обучению имитации отжига (с примером кода) здесь:

Неллер, Тодд. Обучение стохастическому локальному поиску , в работах И. Рассела и З. Маркова, ред. Материалы 18-й Международной конференции FLAIRS (FLAIRS-2005), Клируотер Бич, Флорида, 15-17 мая 2005 г., AAAI Press, стр. 8-13.

Связанные ресурсы, ссылки и демонстрации находятся здесь: http://cs.gettysburg.edu/~tneller/resources/sls/index.html

...