This is the program using Genetic Algorithm(GA) to solve the Traveling Salesman Problem(TSP),but unfortunately,there are still some bugs I was unable to handle.Take care!

 

 

 

/*******************coded by Atlantis*******************/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>

 

#define GENE_TOTAL 10  
#define MAX_GEN 5  
#define LOW 3   
#define UP  6
#define INHERIT_RATE 20 
#define HYBRID_RATE 67  
#define RANDOM rand()%GENE_TOTAL 

enum operators
{
 inherit,hybrid,mutation,
}op;

struct individual
{
 int val;
 int gene[GENE_TOTAL];
};

typedef enum operators operators;
typedef struct individual individual;

int Dist[GENE_TOTAL][GENE_TOTAL]={
         0, 1, 4, 6, 8, 1, 3, 7, 2, 9,
         1, 0, 7, 5, 3, 8, 3, 4, 2, 4,
         4, 7, 0, 3, 8, 3, 7, 9, 1, 2,
         6, 5, 3, 0, 3, 1, 5, 2, 9, 1,
         8, 3, 8, 3, 0, 2, 3, 1, 4, 6,
         1, 8, 3, 1, 2, 0, 3, 3, 9, 5,
         3, 3, 7, 5, 3, 3, 0, 7, 5, 9,
         7, 4, 9, 2, 1, 3, 7, 0, 1, 3,
         2, 2, 1, 9, 4, 9, 5, 1, 0, 1,
         9, 4, 2, 1, 6, 5, 9, 3, 1, 0,
         }; 
individual Race[R_AMOUNT];   
int Total,Total_temp;  
void init(void); 
void eval_r(void);  
operators sel_op(void);  
individual* sel_mem(void); 

int main()
{
 int gen=0; 

 int i,j;  
 individual temp[R_AMOUNT];  
 srand((unsigned)time(NULL)); 
 printf("           This Program Is Coded By Atlantis\n");
 printf("************************************************************\n");
 printf("\nRACE AMOUNT:%d TOTAL gene:%d MAX GENERATION:%d\n",R_AMOUNT,GENE_TOTAL,MAX_GEN);
 printf("\nInitialize the race,please wait!\n");
 init(); 
 printf("Initialize finished,press any key to continue...\n");  
 getchar();
 
 for (i=0; i<R_AMOUNT; ++i)   
 {    
  temp[i].val=0;
  for (j=0; j<GENE_TOTAL; ++j) *(temp[i].gene+j)=0;
 }  
 while (gen<MAX_GEN) 
 {
  int i;    
  eval_r();  
  for (i=0; i<R_AMOUNT; ++i)
  {
   op=sel_op(); 
   switch (op)
   {
    case hybrid:
     {
      int j,k,m=0;
      bool flag=false; 
      individual *father,*mother;
      individual son_1,son_2;
      father=sel_mem();
      while(m<100) ++m; 
      m=0;
      mother=sel_mem();
      
      son_1.val=father->val;
      
      son_2.val=mother->val;
      
      for (j=LOW; j<=UP; ++j)  
      {
       *(son_1.gene+j)=*(father->gene+j);
       *(son_2.gene+j)=*(mother->gene+j);

      }
      for (j=0; j<GENE_TOTAL; ++j) 
      {
       for (k=LOW; k<=UP; k++)
       {
        if (!flag && *(mother->gene+j)==*(son_1.gene+k))

        {

         flag=true; 

        }
       }
       if (!flag)
       {
        *(son_1.gene+m)=*(mother->gene+j);
        m++;
        if (m==LOW) m=m+(UP-LOW)+1;
       }
       flag=false; 
      }
      m=0;  
      for (j=0; j<GENE_TOTAL; ++j) 
      {
       for (k=LOW; k<=UP; k++)
       {
        if (!flag && *(father->gene+j) == *(son_2.gene+k) )
        {
         flag=true;
        }
       }
       if (!flag)
       {
        *(son_2.gene+m)=*(father->gene+j);
        m++;
        if (m==LOW) m=m+(UP-LOW)+1;
       }
       flag=false; 
      }
      
      for (j=0; j<GENE_TOTAL; ++j) {
       *(temp[i].gene+j) = *(son_1.gene+j);
       *(son_1.gene+j) = -1; 
       *(son_1.gene+j) = -1;
      }      
      if (i!=R_AMOUNT)
      {
       ++i;
       for (j=0; j<GENE_TOTAL; ++j)
        *(temp[i].gene+j) = *(son_2.gene+j); 
      }
      break;
     }
    case inherit:
     {
      temp[i]=*sel_mem();
      break;
     }
    default:
     {
      int t,rand_t;
      int j=0;  
      temp[i]=*sel_mem();  
      rand_t=RANDOM;   
      t=temp[i].gene[rand_t];  
      
      *(temp[i].gene+rand_t) = RANDOM; 
      while ( j<GENE_TOTAL && *(temp[i].gene+j)!=*(temp[i].gene+rand_t) )
       ++j; 
      *(temp[i].gene+j)=t;      
     }
   }
  }
  for (i=0; i<R_AMOUNT; ++i)  
  {
   int j;
   
   Race[i].val=temp[i].val;
   for (j=0; j<GENE_TOTAL; ++j)
    *(Race[i].gene+j) = *(temp[i].gene+j);
  }
  ++gen; 
  printf("%d  \n",gen); 
 }
 printf("The GA is over,press any key to see the final answer..Wish you good luck!\n");
 getchar();
 {
  int max=Race[0].val,m=0;
  for (i=1; i<R_AMOUNT; ++i)
  {
   if (max<Race[i].val)
   {
    max=Race[i].val;
    m=i;
   }
  }
  printf("%-20s: %d\n","Total generation:",gen);
  printf("%-20s: ","Best gene:");
  for (i=0; i<GENE_TOTAL; ++i)
  {
   printf( "%d ", *(Race[m].gene+i) );
  }
  printf("\n%-15s: %d\n","Largest Value:",Total_temp-Race[m].val);
 }
 getchar();
 return 0;
}

void init(void)  
{
 int i,j;
 struct node   
 {
  int code;
  struct node *next;
 }NODE;
 typedef struct node node;
 node *head,*p,*t;
 int k; 
 int offset;

 for (i=0; i<R_AMOUNT; ++i)   
 {
  Race[i].val=0;
  for (j=0; j<GENE_TOTAL; ++j)
   *(Race[i].gene+j)=0;
 }

 for (i=0; i<R_AMOUNT; ++i)
 {  
  Race[i].val=0; 
  head=(node *)malloc(sizeof(NODE));
  if (!head) {printf("memory allocation error!\n");exit(1);}
  head->code=0;
  head->next=head;
  k=GENE_TOTAL-1;
  do{
   p=(node *)malloc(sizeof(NODE));
   if (!p) {printf("memory allocation error!\n");exit(1);}
   p->code=k;
   p->next=head->next;
   head->next=p;
   k--;
  }while(k>0);
  
  j=0;
  do{
   t=head;
   offset=rand()%(GENE_TOTAL-j);  
   
   for (k=0; k<=offset; k++) 
   {
    p=t;
    t=t->next;
   }
   
   *(Race[i].gene+j)=t->code; 
   
   p->next=t->next;
   head=p->next; 
   if( head->code != p->next->code )
    free(t);
   ++j;
  }while(j<GENE_TOTAL);
  free(t);
  printf("i: %d gene:",i);
  for (j=0; j<GENE_TOTAL; ++j) printf(" %d",Race[i].gene[j]);
  printf("\n");
 }
}

void eval_r(void)  
{
 int i,j;
 Total=0;
 Total_temp=0;
 for (i=0; i<R_AMOUNT; ++i)
 {
  Race[i].val=0;
  for (j=0; j<GENE_TOTAL; ++j)
  {
   Race[i].val +=Dist[ *(Race[i].gene+j) ][ *(Race[i].gene+(j+1)%GENE_TOTAL) ];
  }  
  Total_temp += Race[i].val;
 }
 
 for (i=0; i<R_AMOUNT; ++i)
 {   
  Race[i].val =Total_temp-Race[i].val; 
  Total += Race[i].val;
 } 
}

operators sel_op(void) 
{
 int rand_no;
 rand_no=rand()%100;
 if (rand_no<=HYBRID_RATE) return hybrid;
 if (rand_no<=INHERIT_RATE+HYBRID_RATE) return inherit;
 return mutation;
}

individual* sel_mem(void)
{
 int i=0;
 int base=0;  
 individual *p;
 int rand_no=rand()%Total; 
 do
 {
  base +=Race[i].val;
  if (rand_no<=base && rand_no>base-Race[i].val)
  {
   break;
  }
  ++i;
 }while(i<R_AMOUNT);
 if (i==R_AMOUNT) i--;  
 p=Race;
 
return p+i;
}

 

For more details,contact me by Caesar1106@163.com