gpt4 book ai didi

c++ - 模拟退火 : too slow with poor results

转载 作者:行者123 更新时间:2023-11-30 05:06:14 26 4
gpt4 key购买 nike

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

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 次迭代需要太多时间,目标函数的值在 78 - 79 之间波动,而我应该得到 0 作为解决方案。

我还认为在复杂性方面我可以做得更好......有人可以帮帮我吗?

提前致谢!

最佳答案

我会使用 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);
}

使用前初始化 vector (0 到 n-1):

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

我不知道你的 f函数是,但你应该编辑它以接受 std::vector 作为它的前两个参数。

关于c++ - 模拟退火 : too slow with poor results,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48007145/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com