Имитация отжига: слишком медленный с плохими результатами

Question

Имитация отжига: слишком медленный с плохими результатами

Я пытаюсь решить с помощью метода имитации отжига следующую проблему:

Где я уже получил значения c_i, j, f, хранящиеся в одномерном массиве, так что

c_i,j,f <=> c[i + j * n + f * n * n]

Моя имитированная функция отжига выглядит так:

int annealing(int n, int k_max, int c[]){
// Initial point (verifying the constraints )
int x[n * n * n];
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
for (int f = 0; f < n; f++){
if (i == j && j == f && f == i){
x[i + j * n + f * n * n] = 1;
}else{
x[i + j * n + f * n * n] = 0;
}
}
}
}
// Drawing y in the local neighbourhood of  x : random permutation by keeping the constraints verified
int k = 0;
double T = 0.01; // initial temperature
double beta = 0.9999999999; // cooling factor
int y[n * n * n];
int permutation_i[n];
int permutation_j[n];
while (k <= k_max){ // k_max = maximum number of iterations allowed
Permutation(permutation_i, n);
Permutation(permutation_j, n);
for (int f = 0; f < n; f++){
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
y[i + j * n + f * n * n] = x[permutation_i[i] + permutation_j[j] * n + f * n * n];
}
}
}
if (f(y, c, n) < f(x, c, n) || rand()/(double)(RAND_MAX) <= pow(M_E, -(f(y, c, n)-f(x, c, n))/T)){
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
for (int f = 0; f < n; f++){
x[i + j * n + f * n * n] = y[i + j * n + f * n * n];
}
}
}
}
T *= beta;
++k;
}
return f(x, c, n);
}

Процедура Перестановка (int permutation [], n) заполняет перестановку массива случайной перестановкой [[0, n-1]] (например, она преобразует [0,1,2,3,4] в [ 3,0,4,2,1]).

Проблема в том, что при 1000000 итерациях это занимает слишком много времени, и значения целевой функции колеблются между 78 — 79, в то время как я должен получить 0 в качестве решения.

Я также думал, что смогу добиться большего успеха, когда речь заходит о сложности …
Кто-то может мне помочь, пожалуйста?

Заранее спасибо!

1

c++operations-research simulated-annealing

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

я хотел бы использовать std::vector<int>вместо массивов (и определите пару констант):

#include <vector>
#include <algorithm>
#include <random>

int annealing(int n, int k_max, std::vector<int> c) {

const int N2 = n * n;
const int N3 = N2 * n;

std::vector<int> x(N3);
std::vector<int> y(N3);
std::vector<int> permutation_i(n);
std::vector<int> permutation_j(n);

// ...

Начальные вложенные циклы сводятся к:

for (int i = 0; i < n; i++){
x[(i*N2) + (i + (i * n))] = 1;
}

Это должна быть ваша функция перестановки:

void Permutation(std::vector<int> & x)
{
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(x.begin(), x.end(), g);
}

Инициализируйте векторы перед использованием (от 0 до n-1):

std::iota(permutation_i.begin(), permutation_i.end(), 0);
std::iota(permutation_j.begin(), permutation_j.end(), 0);

Я понятия не имею, что вы f функция есть, но вы должны отредактировать ее, чтобы принять std :: vector в качестве первых двух аргументов.

1