C program to for traveling salesman problem?
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#define N 50
//Travelling sales man problem , travelling between 6
cities.
//initializing the path lengths between cities and the paths to
be included
//in population
void initialize(int pathlen[][6],int path[][6])
{
int i,j,k;
//obtaining pathlengths
for(i=0;i<6;i++)
{
for(j=0;j<6;j++)
{
if(j<i) //path length from a to b will be same as b to a
{
pathlen[i][j]=pathlen[j][i];
}
if(j==i) // path length from a to a will be 0
{
pathlen[i][j]=0;
}
if(j>i) // rest initialized
{
do{
pathlen[i][j]= random(20);
}while(!pathlen[i][j]);
}
}
}
// display the path lengths
printf("\n\tThe PATH LENGTHS ARE: \n" );
for(i=0;i<6;i++)
{
for(j=0;j<6;j++)
{
printf(" %5d ",pathlen[i][j]);
}
printf("\n\n");
}
// generating the population
for(i=0;i<20;i++)
{
for(j=0;j<6;j++)
{
path[i][j]=random(6);
for(k=j-1;k>=0;k--)
{
if(path[i][j]==path[i][k]) //checking to avoid repeatition
{
path[i][j] = random(6);
k=j;
}
}
}
}
}
// evaluating the fitness function or total distance
void evaluate(int pathlen[6][6],int path[20][6],int fx[20])
{
int sum =0,i,j,a,b;
//obtaing the sum of the path taken
for(i=0;i<20;i++)
{
sum=0;
for(j=0;j<5;j++)
{
a=path[i][j];
b=path[i][j+1];
sum=sum+pathlen[a][b];
}
fx[i]=sum;
}
//display the paths generated
printf("\n");
printf("\n\tPATH \t\tf(x) \n\n");
for(i=0;i<20;i++)
{
printf("\t");
for(j=0;j<6;j++)
{
printf(" %d",path[i][j]);
}
printf("\t%d",fx[i]);
printf("\n");
}
}
//selecting the two points for cross over and then performing
partial Crossover
void selection(int fx[20],int pos[2],int posmax[2])
{
int min1=fx[0],min2=fx[0],i,max1=fx[0],max2=fx[0];
pos[0]=0;
pos[1]=0;
posmax[0]=0;
posmax[1]=0;
//calculating the minimum postion
for(i=1;i<20;i++)
{
if(fx[i]<min1)
{
min1=fx[i];
pos[0]=i;
}
}
//calaculating the second minimum position
for(i=1;i<20;i++)
{
if(fx[i]<min2&&i!=pos[0])
{
min2=fx[i];
pos[1]=i;
}
}
//calculating the max position
for(i=1;i<20;i++)
{
if(fx[i]>max1)
{
max1=fx[i];
posmax[0]=i;
}
}
//calculating the second max position
for(i=1;i<20;i++)
{
if(fx[i]>max2&&i!=posmax[0])
{
max2=fx[i];
posmax[1]=i;
}
}
printf("\n\tFIRST MINIMUM=%4d \tPOSITION=%4d\n\tSECOND
MINIMUN=%4d \tPOSITION=%4d\n\tFIRST MAXIMUM=%4d
\tPOSITION=%4d\n\tSECOND MAXIMUM=%4d
\tPOSITION=%4d\n",min1,pos[0],min2,pos[1],max1,posmax[0],max2,posmax[1]);
}
//PERFORMING PARTIAL CROSSOVER
void crossover(int pos[2],int path[][6],int child[2][6])
{
int crosspt1,crosspt2,j,i,temp,temp1[2][6],temp2;
//TAKING 2 CROSS POINTS
do
{
crosspt1=random(5);
}while(crosspt1>2) ;
do
{
crosspt2=random(5);
}while(crosspt2<=3);
clrscr();
printf("\n\n\t The CROSSOVER POINTS ARE : %d , %d
",crosspt1,crosspt2);
printf("\n\n\tTHE PATHS FOR CROSSOVER ARE");
printf("\n\n\t\t");
for(j=0;j<6;j++)
{
child[0][j]=path[pos[0]][j];
printf(" %d",child[0][j]);
}
printf("\n\t\t");
for(j=0;j<6;j++)
{
child[1][j]=path[pos[1]][j];
printf(" %d",child[1][j]);
}
int cnt=0;
//swapping the paths between two crosspoints
for(j=crosspt1+1;j<=crosspt2;j++)
{
temp1[1][cnt]=child[0][j];
temp1[0][cnt]=child[1][j];
temp=child[0][j];
child[0][j]=child[1][j];
child[1][j]=temp;
cnt++;
}
//performing partial crossover
int k,m;
for(m=0;m<2;m++)
{
for(i=0;i<crosspt1+1;i++) //taking the path before
crosspoint
{
for(j=0;j<cnt;j++) //comparing the path within crossover
point
{
if(child[m][i]==temp1[m][j]) //if found then
{
if(m==0) //for child 1
{
temp2=temp1[1][j]; //take the path from child2 crossover
for(k=0;k<6;k++)
{
if(child[m][k]==temp2) //if still the path repeats then repeat
the process again
{ temp2=child[1][k];
k=0;
}
}
child[m][i]=temp2; //finally putting the value in child
}
else //for child 2
{
temp2=temp1[0][j];
for(k=0;k<6;k++)
{
if(child[m][k]==temp2)
{temp2=child[0][k];
k=0;
}
}
child[m][i]=temp2;
}
}
}
}
}
for(m=0;m<2;m++)
{
for(i=crosspt2+1;i<6;i++) //now chehcking the path after the
second cross point
{
for(j=0;j<cnt;j++) //comparing the path within crossover
point
{
if(child[m][i]==temp1[m][j]) //if found then
{
if(m==0) //for child 1
{
temp2=temp1[1][j]; //take the path from child2 crossove
for(k=0;k<6;k++)
{
if(child[m][k]==temp2) //if still the path repeats then repeat
the process again
{temp2=child[1][k];
k=0;
}
}
child[m][i]=temp2; //finally assigning the value
}
else //for child 2
{
temp2=temp1[0][j];
for(k=0;k<cnt;k++)
{
if(child[m][k]==temp2)
{temp2=child[0][k];
k=0;
}
}
child[m][i]=temp2;
}
}
}
}
}
//display AfTER CROSSOVER
printf("\n\tAFTER CROSSOVER\n\t\t");
for(j=0;j<6;j++)
{
printf(" %d",child[0][j]);
}
printf("\n\t\t");
for(j=0;j<6;j++)
{
printf(" %d",child[1][j]);
}
}
//insering the paths in population removing those having maximum
populaiton
void insert(int child[2][6],int posmax[2],int path[20][6])
{
for(int j=0;j<6;j++)
{
path[posmax[0]][j]=child[0][j];
path[posmax[1]][j]=child[1][j];
}
}
// performing mutation
void mutation(int child[2][6])
{
int sel=random(2);
int pos1=random(6);
int pos2=random(6);
int temp=child[sel][pos1];
child[sel][pos1]=child[sel][pos2];
child[sel][pos2]=temp;
}
void main()
{
clrscr();
randomize();
int
pathlen[6][6],path[20][6],fx[20],pos[2],posmax[2],child[2][6];
printf("\n\t\t\t TRAVELLING SALESMAN PROBLEM ");
printf("\n\t\t\t_____________________________");
printf("\n\n\n\t\tTHE TRAVELLING SALES MAN PROBLEM DEALS WITH
THE FACT");
printf("\n\n\t\tTHAT A SALESMAN TRAVELS BETWEEN CITIES TAKING
THE PATH");
printf("\n\n\t\tTHAT IS OF MINIMUN DISTANCE.");
printf("\n\n\n\t\tTO OBTAIN THE MINIMUM DISTANCE WE USE GENETIC
ALGO");
printf("\n\n\t\tWHERE WE TAKE AN INITIAL POPULATION OF 20 PATHS
AND ");
printf("\n\n\t\tAND THEN THROUGH FITNESS FUNCTION WE OBTAIN THE
PATHS ");
printf("\n\n\t\tWITH MINIMUN DISTANCE AND REPLACE THEM WITH THE
CHILDS ");
printf("\n\n\t\tAFTER PARTIAL CROSSOVER WITH MAXIMUM
DISTANCE.");
getch();
clrscr();
initialize(pathlen,path);
evaluate(pathlen,path,fx);
getch();
selection(fx,pos,posmax);
crossover(pos,path,child);
mutation(child);
getch();
insert(child,posmax,path);
for(int i=1;i<N;i++)
{
evaluate(pathlen,path,fx);
selection(fx,pos,posmax);
crossover(pos,path,child);
mutation(child);
insert(child,posmax,path);
}
evaluate(pathlen,path,fx);
selection(fx,pos,posmax);
crossover(pos,path,child);
insert(child,posmax,path);
evaluate(pathlen,path,fx);
getch();
}
