Thread: Mysterious Changing Values

  1. #1
    Registered User crepincdotcom's Avatar
    Join Date
    Oct 2003
    Posts
    94

    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,
    -Jack C
    jack {at} crepinc.com
    http://www.crepinc.com

  2. #2
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    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]
          }
        }
      }
    }
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  3. #3
    Registered User crepincdotcom's Avatar
    Join Date
    Oct 2003
    Posts
    94
    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.
    -Jack C
    jack {at} crepinc.com
    http://www.crepinc.com

  4. #4
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    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.)
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  5. #5
    Registered User crepincdotcom's Avatar
    Join Date
    Oct 2003
    Posts
    94
    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,
    -Jack C
    jack {at} crepinc.com
    http://www.crepinc.com

  6. #6
    Registered User
    Join Date
    Mar 2005
    Posts
    140
    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);
          }
        }
      } //add other methods here
    
      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[]
    Last edited by spydoor; 12-02-2005 at 09:30 AM.

  7. #7
    Registered User crepincdotcom's Avatar
    Join Date
    Oct 2003
    Posts
    94
    Yes.... but I threw a few more tableouts() in there.... I'll keep working on it.
    -Jack C
    jack {at} crepinc.com
    http://www.crepinc.com

  8. #8
    Registered User crepincdotcom's Avatar
    Join Date
    Oct 2003
    Posts
    94
    (disregard this... browser issue)
    Last edited by crepincdotcom; 12-02-2005 at 11:07 AM.
    -Jack C
    jack {at} crepinc.com
    http://www.crepinc.com

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. disposing error
    By dropper166 in forum C# Programming
    Replies: 2
    Last Post: 03-30-2009, 11:53 PM
  2. Pointer changing values
    By belkins in forum C Programming
    Replies: 9
    Last Post: 12-02-2008, 09:55 AM
  3. Replies: 2
    Last Post: 11-19-2008, 02:36 PM
  4. Checking ascii values of char input
    By yank in forum C Programming
    Replies: 2
    Last Post: 04-29-2003, 07:49 AM
  5. unsigned char vs signed char and range of values
    By Silvercord in forum C++ Programming
    Replies: 5
    Last Post: 01-22-2003, 01:30 PM