エッジの重みで距離を示すグラフの距離行列 (または隣接リスト) を指定して、2 次元の xy 座標系で頂点の正しい配置を見つけるプログラムを考え出そうとしています。
最初に、ブルートフォース検索を書きました。次に、この問題を解決するために、C++ プログラムを修正して、AB = C 行列方程式を解くことにしました。
INPUT : 距離行列
OUTPUT : 2d-xy 平面内の 2 つの頂点間の距離としてエッジの重みを考慮して、指定された距離行列を満たす頂点の座標。
これは私のプログラムのサンプル実行です:
The original adjacency matrix:
0 1 1.41 1
1 0 1 1.41
1.41 1 0 1
1 1.41 1 0
The coordinates which can satisfy the given input adjacency matrix with edge weight denoting distance are :
[24.327,0.40545]
[25.5472,0.425787]
[25.5306,1.42551]
[24.3103,1.40517]
The calculated adjacency matrix from the solution we got from CrossEntropy Method is :
0 1.10473 1.25607 0.999931
1.10473 0 0.999931 1.25607
1.25607 0.999931 0 1.10473
0.999931 1.25607 1.10473 0
これで、おおよその解が得られていることがわかります。あるいはそうしようとしているとも言えます。しかし、それは満足のいくものではありません。すべての反復の適合度を調べたところ、最初の数ステップの後はほぼ一定でした。それは、フィットネスがあまり改善されていないことを意味します。
前提 1. 私のプログラムはその隣接行列をランダムに生成しました。2. フィットネス変数は、コードでの意味の逆です。適合度の値が高く、解の質が低い
私の質問は >> このプログラムを微調整して、より良い結果が得られるようにする方法です (学習率とサンプル数を変更しようとしましたが、あまり成功しませんでした)。私が間違っていることと、より正確にする方法. これを行うための他の簡単な方法はありますか?隣接行列から座標を取得するという問題全体を意味しますか?
このコードは次のとおりです。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<iostream>
using namespace std;
#define UPPER_LIMIT 20 // this is the upper limit to the distances given in adjacency matrix,
const int SQSZ= UPPER_LIMIT*3; // this is half the size of our finite cartesian coordiante system , which will go from 0 to 2*SQSZ in x as well as y
double SQR(double X ) { return X*X ; }
#define LOWER_BOUND -SQSZ
#define UPPER_BOUND SQSZ
#define num_samples 100 //number of samples we want to generate in every iteration, our population count
#define num_update 5 //number of top members of population we are taking to modify our distribution
#define max_iter 200 //total number of iterations
#define problem_size 4 // number of vertices in graph
#define alpha 0.7 //learning rate
struct sample{
double arr[problem_size];
double cost;
};
typedef struct sample sample;
const int n = problem_size,m = problem_size;
double a[m][n] , b[m];
sample best;
sample samples[num_samples];
sample selected[num_update];
double means[problem_size];
double stdev[problem_size];
/* the following function takes the input adjacency , */
int take_input()
{
srand(time(NULL));
/*
for(int i =0; i< m; i++)
for(int j =0; j<n; j++)
if( i > j ) a[i][j] = a[j][i] = rand()%UPPER_LIMIT;
else a[i][j] = a[j][i] = 0;
*/
cout<<"Input the distance matrix of size "<< problem_size<<"X"<<problem_size<<endl;
for(int i =0 ; i< m ; i++)
for(int j =0; j <n ; j++){
cin >> a[i][j];
}
// for(int i =0; i< m; i++)
// scanf("%lf",&b[i]);
}
void print_matrix()
{
for(int i =0; i<m ; i++,printf("\n"))
for(int j =0 ; j<n; j++)
cout << a[i][j] << " ";
cout<<endl;
}
// what I am doing here is treating each value in a single sample as a creator of x,y corrdinate, by using fmod and division.
double dist(double a,double b)
{
// cout<<"dist("<<a<<" "<<b<<")" << endl;
double ax,ay,bx,by;
ax = fmod(a,SQSZ);
ay = a/SQSZ;
bx = fmod(b,SQSZ);
by = b/SQSZ;
return sqrt(hypot((ax-bx), (ay-by) ));
}
// just to decompose the sample value into x and y coordinate and print it
void decom(double a)
{
double x = fmod(a,SQSZ);
double y = a/SQSZ;
cout <<"["<< x<< "," << y << "]" << endl;
}
/* simple comparision function to compare cost */
bool cmp( sample a , sample b )
{
if( a.cost < b.cost )
return true;
else
return false;
}
/* find average of means of best part of population */
double mean_attr(int x )
{
double sum = 0.0;
for(int i=0; i< num_update; i++)
sum += selected[i].arr[x];
return sum / num_update;
}
/* find the average standard deviation for best part of population */
double stdev_attr(int x,double mean)
{
double sum = 0.0;
for(int i =0; i<num_update; i++)
sum += (selected[i].arr[x] - mean)*(selected[i].arr[x] - mean);
return sqrt( sum / num_update);
}
/* returns a random number between a to b */
double random_variable(double a ,double b){
return a + (( b - a )*((double)rand()/RAND_MAX) );
}
/* returns a value depending on mean and stdev according to gaussian distribution fucntion */
double random_gaussian(double mean , double stdev)
{
double u1,u2,w;
do {
u1 = 2*((double)rand()/RAND_MAX) - 1;
u2 = 2*((double)rand()/RAND_MAX) - 1;
w = u1*u1 + u2 * u2;
} while( w >= 1 );
w = sqrt(( -2.0 * log(w ))/w);
return mean + ( u2* w ) * stdev;
}
/* evaluate our samples , returns the cost of our solution */
double evaluate(int x)
{
double sum = 0.0;
// double delta_array[m];
for(int i =0; i<m ; i++)
for(int j =0; j< n; j++)
{
double y = 0.0;
y = a[i][j] - dist( samples[x].arr[i] +SQSZ, samples[x].arr[j] + SQSZ );
sum += y*y;
// cout << "hii there" << y*y << endl;
// fflush(stdout);
// system("sleep 0.1");
}
/*
for( int i =0; i< m; i++)
{
delta_array[i] = 0.0;
for(int j =0; j<n; j++)
delta_array[i] = ( delta_array[i] + ( (a[i][j]) *samples[x].arr[j] ));
delta_array[i] =delta_array[i] - b[i];
sum += delta_array[i] * delta_array[i];
}
*/
return sum;
}
int main()
{
take_input();
best.cost = -1; // intially we don't have any best , so its initial value is -1
// cout<<"Given random adjacency matrix"<<endl;
// print_matrix();
for(int i =0; i< problem_size; i++){
means[i] = random_variable(LOWER_BOUND,UPPER_BOUND);
stdev[i] = UPPER_BOUND - LOWER_BOUND;
}
for(int iter =0; iter < max_iter ; iter++ )
{
for(int i =0; i< num_samples; i++)
{
for(int j=0; j< problem_size; j++)
{
samples[i].arr[j] = random_gaussian(means[j],stdev[j]);
if( samples[i].arr[j] < LOWER_BOUND ) samples[i].arr[j] = LOWER_BOUND;
if( samples[i].arr[j] > UPPER_BOUND ) samples[i].arr[j] = UPPER_BOUND;
}
samples[i].cost = evaluate(i);
}
sort( samples,samples+num_samples,cmp);
if( best.cost == -1 || best.cost > samples[0].cost )
{
best.cost = samples[0].cost;
for(int i=0; i<problem_size; i++)
best.arr[i] = samples[0].arr[i];
}
for(int j=0; j< num_update;j++){
selected[j].cost = samples[j].cost;
for(int k =0; k< problem_size; k++)
selected[j].arr[k] = samples[j].arr[k];
}
for(int j=0; j< problem_size; j++)
{
means[j] = alpha*means[j] + ( 1.0 - alpha) * mean_attr(j);
stdev[j] = alpha*stdev[j] + ( 1.0 - alpha) * stdev_attr(j,means[j]);
}
// printf(" > iteration = %d , fitness = %lf\n",iter,best.cost );
fflush(stdout);
}
//printf("Solution : f = %lf\n",best.cost );
cout<<"The original adjacency matrix:"<< endl;
print_matrix();
cout << "The coordinates which can satisfy the given input adjacency matrix with edge weight denoting distance are :"<< endl;
for(int i =0; i< problem_size; i++)
decom(best.arr[i] + SQSZ);
cout<<endl;
cout<<"The calculated adjacency matrix from the solution we got from CrossEntropy Method is :"<<endl;
// printing our solutions adjacency matrix
for(int i =0; i<n; i++,printf("\n"))
for(int j =0 ; j<m ;j++)
cout << dist(best.arr[i] +SQSZ, best.arr[j] + SQSZ)<< " ";
cout<<endl;
return 0;
}
前もって感謝します ：）。
アップデート：
入力に単位正方形の単純な距離行列を配置すると、正しい結果が得られます。しかし、そのようなグラフを生成することは、私にとって別の問題であるため、プログラムをテストする方法がよくわかりません。