answersLogoWhite

0

#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();

}

User Avatar

Wiki User

12y ago

What else can I help you with?

Related Questions

What has the author Robert A Luenberger written?

Robert A. Luenberger has written: 'A traveling-salesman-based approach to aircraft scheduling in the terminal area' -- subject(s): Scheduling, Terminal facilities, Traffic control, Algorithms, Traveling salesman problem


A c program to square matrix?

A C program to square matrix is a math problem. In the math problem you write down all the outer boundary values of matrix in a circle, then write down the inner value.


What is solution in c program?

The program itself is the solution. All programs are a solution to a given problem; that's the entire point of writing a program, to solve a problem. The program's algorithm specifies how the problem is solved and it's the programmer's job to convert that algorithm into working code.


Write a program in C programming language that computes the roots of the quadratic equation ax2 plus bx plus c?

Write your program and if you are having a problem post it here with a description of the problem you are having. What you are asking is for someone to do your homework for you.


How do you write the average n numbers program in c language?

Write your program and if you are having a problem post it here with a description of the problem you are having. What you are asking is for someone to do your homework for you. no i am asking to verify my answer


Write a program in c plus plus to compute first of non-terminal?

there is no solution of this problem...........that's it..........


How do you write a c programme for elecricity bill?

Write your program and if you are having a problem post it here with a description of the problem you are having. What you are asking is for someone to do your homework for you.


Arthur Miller felt that Death of a Salesman was a?

C. tragedy.


Features of c program?

the features of a C program


C program was introduced in the year?

c program was introduced in the year 1972 by Dennis RitchieNo, it was the C language, not the C program.


C program for sorting the numbers?

C program for sorting the numbers is very basic, start writing it and if you are having problems, post your program here and a description of the problem and you will be helped. If you are taking a computer course, how do you expect to pass exams if you have plagiarized someone else work for your assignments.


What is programing in c?

C++ is a programming language which gives the user the chance to create working applications through creating source code.