作者热门文章
- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
由于模拟退火方法,我正在尝试解决以下问题:
我已经将 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/
我有一个 d3 力布局图可视化效果很好,但它经常过早地“卡住”。例如,节点正朝着一个好的位置摇晃,如果“碰撞”它们(向它们的位置注入(inject)一点随机性并再次 start() ,它们最终会到达那
我是一名优秀的程序员,十分优秀!