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

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

Проблема оптимизации

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

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);
}

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

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

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

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


c++ operations-research simulated-annealing
person Mohamed Bouazza    schedule 28.12.2017    source источник
comment
Кто-нибудь, помогите мне, пожалуйста?   -  person Mohamed Bouazza    schedule 28.12.2017
comment
Есть ли какая-то особая причина, по которой вы пишете свою реализацию? Существует обширная поддержка математических функций здесь gnu.org/software/gsl /doc/html/index.html и, в частности, gnu.org/software/gsl/doc/html/siman.html?highlight=annealing   -  person Alessandro Teruzzi    schedule 28.12.2017
comment
Не слишком ли близок этот коэффициент охлаждения к 1,0? Что происходит с чем-то вроде 0,999?   -  person Bob__    schedule 30.12.2017

Ответы (1)


arrow_upward
1
arrow_downward

Я бы использовал 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;
}

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

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 в качестве первых двух аргументов.

person p-a-o-l-o    schedule 28.12.2017
comment
Спасибо за ваше возвращение! Но даже реализуя vector‹int› вместо массивов и определяя константы, это занимает слишком много времени (более 6 часов) для n = 200, мне конечно нужно уменьшить его сложность, но не знаю как? - person Mohamed Bouazza; 29.12.2017
comment
Обратите внимание, что std::mt19937 нужно заполнять только один раз в программе. - person Bob__; 30.12.2017
comment
Знаете ли вы, как я могу уменьшить сложность (когда речь идет о векторе‹int› размером, равным 200*200*200)? - person Mohamed Bouazza; 31.12.2017