模拟退火：速度太慢，效果不佳

Question

由于模拟退火方法，我正在尝试解决以下问题：

Optimization problem

我已经将 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);
}

过程 Permutation(int permutation[], n) 用 [[0,n-1]] 的随机排列填充数组排列（例如，它将变换 [0,1,2,3 ,4] 到 [3,0,4,2,1]).

问题是，1000000 次迭代需要太多时间，objective 函数的值在 78 - 79 之间振荡，而我应该得到 0 作为解决方案。

我也在想在复杂性方面我可以做得更好...... 有人可以帮助我吗？

提前致谢！

Answer 1

我会使用 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 作为它的前两个参数。

模拟退火：速度太慢，效果不佳

Simulated annealing: too slow with poor results

c++

simulated-annealing

operations-research