Mysterious Changing Values
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,
