1. ## 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 = 15;
Py = 3 ;

Px = 14;
Py = 10;

Px = 2 ;
Py = 1 ;

Px = 8 ;
Py = 19;

Px = 11;
Py = 6 ;

Px = 18;
Py = 9 ;

Px = 6;
Py = 11;

Px = 9 ;
Py = 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]);
}
}
}
}

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);
}
}

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, 2. The linter tells me you might want to focus here:
Code:
```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; // [Warning 661] Possible access of out-of-bounds pointer (1 beyond end of data) by operator '[' [Reference: file test.c: lines 28, 29, 42]
}
}
}
}``` 3. I just did a logical run through and some debug strings and that var seems to be ok...

Thanks for the idea though, I should have thought of lint. 4. My next guess might be to take a pointed look at the use of global variables. Perhaps parameter passing would not have this issue.

And/or add some debugging lines when assigning to globals.

("Mysterious changing values" usually end up being globals or interrupt related, if not both. If you've got no interrupts, that narrows it a bit.) 5. I know gcc is a good compiler, so globals in general are not bad, is that correct? It's an error on my part somewhere? I've debugged like crazy: it goes in one way, comes out a bit different... And frankly I'm not amazing at C, and parameters will take me quite a while to use efficiently, with pointers and such.

Thanks, 6. Here's an example of what I'm talking about. These two steps occur in this order, with nothing between.
There's definitely something between.

Code:
```  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);
}
}

tableout("Mutation complete.");```
so you call genrand() in between
genrand() changes your global array order[]
order[] is used to calculate your global array fitness[]
tableout() calls testpaths() which updates fintess[] (based on order[] which was just changed)
you then print fitness[] 7. Yes.... but I threw a few more tableouts() in there.... I'll keep working on it. 8. (disregard this... browser issue) Popular pages Recent additions 