Hello all,

I'm writting (have written...) a program that uses genetic algorithms to solve the Travelling Salesman Problem. (Search google if the idea of the interests you). I hate to post a whole 200 lines here, but I'm at a loss for the reason of these issues. It seems that values in one of my arrays simply increments by some random value each time that function is run. I know this is an error of mine, but I cannot for the life of me find it.

Here's an example of what I'm talking about. These two steps occur in this order, with nothing between. For debugging, the values of fitness[] for each index is in parenthises. Note how they get bigger in the second output! What is that!!!!

Code:
!!!!--------Sort complete, mutating.
0:104.45:  3 5 4 2 6 0 1 7 (52.46)
1:87.36:  5 6 2 4 1 0 3 7 (69.12)
2:85.31:  6 2 7 3 4 1 5 0 (77.89)
3:77.89:  3 2 6 0 7 4 5 1 (79.86)
4:52.46:  6 5 2 7 1 0 4 3 (85.31)
5:69.12:  3 4 5 6 0 7 2 1 (87.36)
6:79.86:  2 5 4 7 3 6 1 0 (90.70)
7:90.70:  4 0 3 7 1 5 6 2 (104.45)

!!!!--------Mutation complete.
0:109.32:  3 5 4 2 6 0 1 7 (63.93)
1:73.57:  5 6 2 4 1 0 3 7 (75.77)
2:97.50:  6 2 7 3 4 1 5 0 (67.16)
3:67.16:  3 2 6 0 7 4 5 1 (71.45)
4:63.93:  3 0 7 5 1 6 2 4 (97.50)
5:75.77:  4 2 3 0 1 7 5 6 (73.57)
6:71.45:  4 5 1 2 0 7 6 3 (95.09)
7:95.09:  2 5 4 6 7 3 1 0 (109.32)
*sigh*

The code looks like crap at the moment because I've been tearing it apart with various debugs to try to find the problem, to no avail. Here it is:

Code:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define N     8 //number of points for salesman to hit
#define S     8 //number of genetic "strands"
#define DEBUG 1
#define M     1 //method to use:
                //  1) top half saved, other rand
                //  2) top quarter saved, 2nd splits, 3-4 rand

double Px[N],Py[N];
double fitness[N],fitnesst[N];
int order[S][N+1],ordert[S][N+1];
unsigned int itz=0; //iterations
int index[N];

void genrand( int inx, int start, int num ) {
  int used[N];
  int i,j,t,o;

  i=inx;

  for (j=0;j<N;j++) {
    used[j]=0;
  }

  if (start != 0) {
    for (i=0;i<N;i++) {
      used[order[inx][i]]++;
    }
  }
  
  for (j=start;j<num;j++) {
    o=0; //funny looking line
    
    while (o==0) {
      t = rand() % N;
      if (used[t]==0) {
        used[t]++;
        o++;
        order[i][j]=t;
      }
    }
  }
}

void init( void ) {
  Px[0] = 15;
  Py[0] = 3 ;

  Px[1] = 14;
  Py[1] = 10;

  Px[2] = 2 ;
  Py[2] = 1 ;

  Px[3] = 8 ; 
  Py[3] = 19;

  Px[4] = 11;
  Py[4] = 6 ;

  Px[5] = 18;
  Py[5] = 9 ;

  Px[6] = 6;
  Py[6] = 11;

  Px[7] = 9 ;
  Py[7] = 4 ;

  int i,j;

  for (i=0;i<S;i++) {
    genrand(i,0,N);
  }
}

double distance( int p1, int p2 ) {
  double D; //funny line...

  //if (DEBUG) printf("[+] distance(%d,%d) called.\n",p1,p2);

  D = ((Px[p2]-Px[p1])*(Px[p2]-Px[p1])) + 
    ((Py[p2]-Py[p1])*(Py[p2]-Py[p1]));

  //if (DEBUG) printf("[+] distance() returning val of %f.\n",sqrt(D));

  return sqrt(D);
}

void testpaths( void ) {
  int i,j;

  for (j=0;j<N;j++) fitness[j]=0;

  for (i=0;i<S;i++) {
    for (j=0;j<N;j++) {
      if (j!=(N-1)) {
        fitness[j] += distance(order[i][j],order[i][j+1]); 
      } else {
        fitness[j] += distance(order[i][j],order[i][0]);
      }
    }
  }
}

void tableout( char *msg ) {
  int i,j;

  testpaths(); //!!!!!

  printf("\n!!!!--------%s\n",msg);
  for (i=0;i<S;i++) { //show table
    printf("%d:%.2f: ",i,fitness[i]);
    for (j=0;j<N;j++) {
      printf(" %d",order[i][j]);
    }
    printf(" (%.2f)\n",fitness[index[i]]);
  }

}

/*
fitness[N] holds the distance traveled for the order
  of index N.

Sort fitness[] with lowest being best. Then, the order of the indicies
  of that list gives the indecies of order[][] from best to worst.
*/
void evolve( void ) { //tried to come up with a cooler name but failed
  int i,j,t;
  //int index[N];

  printf("[+]  New evolve().\n");
  tableout("Beginning evole(), testpaths()");
 
  testpaths();

  tableout("testpaths() done, sorting.");

  for (i=0;i<S;i++) { //make index have nums
    index[i]=i;
  }

  // bubble sort
  for (i=0;i<S;i++) {
    for (j=(i+1);j<N;j++) {
      if( fitness[index[i]] > fitness[index[j]]) {
        t = index[i];
        index[i] = index[j];
        index[j] = t;
      }
    }
  }

  /* printf("fitness[] sorted\n"); */ 
/*   for (j=0;j<N;j++) fitnesst[j]=fitness[index[j]]; */
/*   for (j=0;j<N;j++) fitness[j]=fitnesst[j]; */
 
  for (i=0;i<S;i++) { //put order in temp in correct way
    for (j=0;j<N;j++) {
     ordert[i][j]=order[index[i]][j];
    }
  } 
  
  for (i=0;i<S;i++) { //copy to original
    for (j=0;j<N;j++) {
      order[i][j]=ordert[i][j];
    }
  }

  tableout("Sort complete, mutating.");
 
  if (M==1) {
    //leave top half, rand the rest
    
    int k=(int)(S/2);
    //printf("k=%d\n",k);
    for (i=k;i<S;i++) {
      for (j=0;j<N;j++) {
        genrand(i,0,N);
      }
    }
  } //add other methods here

  tableout("Mutation complete.");
}

int main( int argc, char *argv[] ) {

  int iterations=2;
  
  srand(getpid()*time(0));

  init();

  int i;
  for (i=0;i<iterations;i++) {
    evolve();
  }
  
  //system("Pause"); //tested on win, needed this
  return 0;
}
I will be forever indebted to anyone who finds the/an issue.

Thanks a great deal,