巡回セールスマン問題を解くプログラムを改善する問題です

[学生T]

元のプログラムはランダムな局所的探索法（解の探索はランダムに行うが，解の採用は決定的に行う）で実装されている．
　このプログラムを，Simulated Annealing，遺伝的アルゴリズム，タブーサーチの何れかを用いるように改善し，求まる解が平均的によくなることを確認する．
１改善したプログラムのソース
２　どの手法を用いるように改善したか．
３　改善前と改善後の tsp.c で見つかる解の比較（平均的な解の良さを比較するため，複数回の実行結果を比較すること）
４ 改善した tsp.c で解が平均的に良くなる理由（又は，良くならない理由）

という問題です。元のソース↓

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* 都市の数 */
#define N 20

/* 探索ループの回数 */
#define M 100

/* 一時的に作る解の数 */
#define K 100

/* 都市の位置(X座標，Y座標) */
float X[N];
float Y[N];

/* 都市の位置の初期化. X，Yとも 0～100の間に定める */
void initCities( void ) {
int i;

/* srand(time(NULL)); */
/* ↑このsrandを有効にすると，実行毎に都市の状況が変わります */
for( i = 0; i < N; ++i ) {
X = ((float)rand()/(float)RAND_MAX) * 100.0;
Y = ((float)rand()/(float)RAND_MAX) * 100.0;
printf( "X[%d] = %f, Y[%d] = %f\n", i, X, i, Y );
}
srand(time(NULL));
}

/* 解を評価する */
float evaluateAnswer( const int* answer ) {
int i;
int a, b;
float cost;
for( i = 0, cost = 0.0; i < N-1; ++i ) {
a = answer;
b = answer[i+1];
/* 都市 a と都市 b の距離を求める */
cost += sqrt( (X[a]-X)*(X[a]-X) + (Y[a]-Y) * (Y[a]-Y) );
}
a = answer[N-1];
b = answer[0];
cost += sqrt( (X[a]-X)*(X[a]-X) + (Y[a]-Y) * (Y[a]-Y) );

return cost;
}

/* 解をランダムに生成する */
int* generateRandomAnswer( void ) {
int i,j,k;
int *answer = (int *)malloc( sizeof(int) * N );
for( i = 0; i < N; ++i ) {
answer = -1;
}
for( i = 0; i < N; ++i ) {
while( 1 ) {
j = rand() % N;
for( k = 0; k < i; ++k ) {
if( answer[k] == j ) {
j = -1;
break;
}
}
if( j != -1 ) {
answer = j;
break;
}
}
}
return answer;
}

/* 解のコピーを生成する */
int *cloneAnswer( int *answer ) {
int i;
int* clone = (int *)malloc(sizeof(int)*N);
for( i = 0; i < N; ++i ) {
clone = answer;
}
return clone;
}

/* 解の m 番目と n 番目の都市を入れ替える */
/* 引数として与えた解そのものが変更されるのに注意 */
void swapCities( int *answer, int m, int n ) {
int s;

if( m < 0 || m >= N || n < 0 || n >= N ) {
printf( "inappropriate argument m = %d, n = %d\n", m, n );
return;
}

s = answer[m];
answer[m] = answer[n];
answer[n] = s;

return;
}

/* 解の m 番目の都市と，他にランダムに選んだ都市を入れ替える */
/* 引数として与えた解そのものが変更されるのに注意 */
void swapCitiesRandomOne( int* answer, int m ) {
int n;

if( m < 0 || m >= N ) {
printf( "inappropriate argument m = %d\n", m );
return;
}

while(1) {
n = rand() % N;
if( m != n )
break;
}

swapCities( answer, m, n );

return;
}

/* 解の中でランダムに選ばれた2つの都市を入れ替える */
/* 引数として与えた解そのものが変更されるのに注意 */
void swapCitiesRandomTwo( int *answer ) {
int m;
m = rand() % N;
swapCitiesRandomOne( answer, m );
return;
}

/* 解を標準出力に表示する */
void printAnswer( int* answer ) {
int i ;
for( i = 0; i < N-1; ++i ) {
printf( "%d -> ", answer );
}
printf( "%d\n", answer[N-1] );
}

int main(void) {
int *bestAnswer; /* 最も良い解 */
int **answers; /* 中間的に保持する解の集合 */
float bestCost; /* 最も良い解のコスト */
int i,j,k;

/* 都市の位置を初期化 */
initCities();

/* ランダムに一つの解を生成 */
bestAnswer = generateRandomAnswer();
bestCost = evaluateAnswer( bestAnswer );

/* M回探索を繰り返す */
for( i = 0; i < M; ++i ) {
/* 今の解を基準にして，K個の解を作る */
answers = (int **)malloc(sizeof(int *)*K);
for( j = 0; j < K; ++j ) {
answers[j] = cloneAnswer( bestAnswer );
swapCitiesRandomTwo( answers[j] );
}

/* 生成したK個の解の中で，最もよいもので(bestよりもよければ)解を更新する */
for( j = 0; j < K; ++j ) {
if( evaluateAnswer( answers[j] ) < bestCost ) {
free(bestAnswer);
bestAnswer = cloneAnswer( answers[j] );
bestCost = evaluateAnswer( bestAnswer );
}
}

/* 一時的に保持した解を解放 */
for( j = 0; j < K; ++j ) {
free( answers[j] );
}
free( answers );

/* 表示 */
printf( "at step %d\n", i );
printAnswer( bestAnswer );
printf( "cost: %f\n", bestCost );
}
}


ご解答よろしくお願い致します。

[たいちう]

遺伝的アルゴリズムだったらアドバイスできるけど、それでいい？
それでいいならば、まずソースコードをタグ付きで貼り直すことと、
遺伝的アルゴリズムについてまず自分で調べ、問題点を明らかにして下さい。