시뮬레이션 어닐링 : 시뮬레이션 어닐링 방법, 다음과 같은 문제에 가난한 내가 해결하기 위해 노력하고있어 결과

Question

, 덕분에 너무 느린 :

나는 이미 C_I, J있어

Optimization problem

, F 값이 저장 1 차원 배열되므로

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을 얻어야한다는 것입니다.

복잡성과 관련하여 더 잘할 수 있다고 생각했습니다. 누군가 제발 나를 도와 줄 수 있습니까?

미리 감사드립니다.

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를 처음 두 인수로 받아들이도록 편집해야합니다.