ارائه الگوريتم تركيبي مورچگان و ژنتيك براي حل مسئله فروشنده دوره گرد
این مقاله یکی از مقالاتی بود که توی کنفرانس بین المللی صنایع ارائه داده شد. و جزء مقالات معتبر شناخته شد. در این مقاله مسئله ی معروف فروشنده با ژنتیک الگوریتم حل شده .
مسئله فروشنده دوره گرد از n شهر تشكيل شده كه بين هر دو شهرآن يك مسير مي تواند وجود داشته باشد . فروشنده دوره گرد مي خواهد از يكي از اين شهرها مسير خود را شروع كرده و سپس به كليه شهرها مسافرت كند و از هر يك از شهرها يكبار فقط بگذرد.
راه حل این مساله رو توی مقاله ببینید.
ارائه الگوريتم تركيبي مورچگان و ژنتيك براي حل مسئله فروشنده دوره گرد
دوست عزيز... در همين انجمن يك Library با نام AForge.net مورد بررسي قرار گرفته كه اگر جستجو كنيد در انجمن پيداش مي كنيد. در اون يكي از مثال هاي بررسي شده در بخش الگوريتم ژنتيك همين مثال فروشنده ي دوره گرد يا TSPهست كه با زبان C# پياده سازي شده...
اگر پيداش نكرديد بگيد تا آدرس دقيقتري بدم...
مسئله فروشنده دورهگرد ( Travelling salesman problem ،یا TSP ) مسئلهای معروفیه که اولین بار مسائل مربوط به اون توسط ویلیام همیلتون و توماس کرکمن مطرح شد و بعد در دهه ۱۹۳۰ شکل عمومی اون به وسیله ریاضیدانانی مثل کارل منگر از دانشگاه هاروارد و هاسلر ویتنی از دانشگاه پرینستون مورد مطالعه قرار گرفت.
در این مسئله تعداد کل راهحلها برابر است :
كد:
1/2 (n-1)! n>2
که در واقع n تعداد شهرهاست. و این عدد برابر است با تعداد دورهای همیلتونی در یک گراف کامل با n رأس.
برای اینکه دقیق تر ببینی این مسئله چطور حل میشه میتونی این برنامه که با ژنتیک الگوریتم نوشته شده رو دانلود و نصب کنی. فکر میکنم اینجوری راحت تر به جواب برسی.
سلام.
متاسفانه لینکها کار نمیکنند، اگر میشه مجدد آپ کنید.
مرسی.
لينکها؟
مقاله (ارائه الگوريتم تركيبي مورچگان وژنتيك براي حل مسئله فروشنده دوره گرد) که لينکش درسته!
در مورد اون برنامه فروشنده دوره گرد هم بايد بگم که صاحب و نويسنده اصلي برنامه رو از سايتشون پاک کردند و در نتيجه اون لينک هم ديگه کار نميکنه
من قبلاً دانلود کرده بودم
در اينجا آپ ميکنم ولي بايد بگم که از اون اول هم سورس رو قرار نداده بودند و فقط فايل اجرايي هست(البته اينم خيلي جذابه)
#include<stdio.h>
#include<conio.h>
#define ALL -1
#define MAXCITIES 10
enum BOOL{FALSE,TRUE};
lنودهای پیمایش شده اینجا علامتگذاری میشوند//long*visited;
long*min_circuit;//min inner circuit for given node as start node at position indexed 0
long*ham_circuit;//optimal circuit with length stored at position indexed 0
long min_circuit_length;//min circuit lenth for given start node
int n;//city count
long matrix[MAXCITIES][MAXCITIES];//nondirectional nXn symmetric matrix
//to store path distances as sourceXdestination
long INFI;// INFINITY value to be defined by user
// function resets minimum circuit for a given start node
//with setting its id at index 0 and setting furthr node ids to -1
void reset_min_circuit(int s_v_id)
{
min_circuit[0]=s_v_id;
for(int i=1;i<n;i++) min_circuit[i]=-1;
}
// marks given node id with given flag
// if id==ALL it marks all nodes with given flag
void set_visited(int v_id,BOOL flag)
{
if(v_id==ALL) for(int i=0;i<n;i++) visited[i]=flag;
else visited[v_id]=flag;
}
// function sets hamiltonion circuit for a given path length
void SET_HAM_CKT(long pl)
{
ham_circuit[0]=pl;
for(int i=0;i<n;i++) ham_circuit[i+1]=min_circuit[i];
ham_circuit[n+1]=min_circuit[0];
}
//function sets a valid circuit by finiding min inner path for a given
//combination start vertex and next vertex to start vertex such that
// the 2nd vertex of circuits is always s_n_v and start and dest node is
//always s_v for all possible values of s_n_v, and then returns the
// valid circuit length for this combination
long get_valid_circuit(int s_v,int s_n_v)
{
int next_v,min,v_count=1;
long path_length=0;
min_circuit[0]=s_v;
min_circuit[1]=s_n_v;
set_visited(s_n_v,TRUE);
path_length+=matrix[s_v][s_n_v];
for(int V=s_n_v;v_count<n-1;v_count++)
{ min=INFI;
for(int i=0;i<n;i++)
if( matrix[V][i]<INFI && !visited[i]
&& matrix[V][i]<=min
)
min=matrix[V][next_v=i];
set_visited(next_v,TRUE);
V=min_circuit[v_count+1]=next_v;
path_length+=min;
}
path_length+=matrix[min_circuit[n-1]][s_v];
return(path_length);
}
void main()
{
clrscr();
printf("Make sure that infinity value < sum of all path distances\nSet Infinity at (signed long):";
scanf("%ld",&INFI);
int pathcount,i,j,source,dest;
long dist=0;
long new_circuit_length=INFI;
printf("Enter no. of cities(MAX:%d):",MAXCITIES);
scanf("%d",&n);
printf("Enter path count:";
scanf("%d",&pathcount);
printf("Enter paths:< source_id destination_id distance >\n ids varying from 0 to %d\n",n-1);
//init all matrix distances to infinity
for(i=0;i<n;i++)
for(j=0;j<n;j++)
matrix[i][j]=INFI;
//populate the matrix
for(i=0;i<pathcount;i++)
{
printf("[path %d]:",i);
scanf("%d %d %ld",&source,&dest,&dist);
if(source!=dest)
matrix[source][dest]=matrix[dest][source]=dist;
}
visited=new long[n];
min_circuit=new long[n];
ham_circuit=new long[n+2];
min_circuit_length=INFI;
// algorithm
//for each vertex, S_V as a staring node
for(int S_V_id=0;S_V_id<n;S_V_id++)
{ //for each and non start vertex as i
for(i=0;i<n;i++)
{ //set all to unvisited
set_visited(ALL,FALSE);
// set staring vertex as visited
set_visited(S_V_id,TRUE);
//reset/init minimum circuit
reset_min_circuit(S_V_id);
// obtain circuit for combination of S_V and i
new_circuit_length=get_valid_circuit(S_V_id,i);
// if newer length is less than the previously
//calculated min then set it as min and set the
//current circuit in hamiltonion circuit
if(new_circuit_length<=min_circuit_length)
SET_HAM_CKT(min_circuit_length=new_circuit_length);
}
}
// if any circuit found
if(min_circuit_length<INFI)
{
printf("\n\nMinimum circuit length is: %ld\nCircuit is:\n",min_circuit_length);
for(i=1;i<n+2;i++) printf("<%ld> ",ham_circuit[i]);
}
else printf(&q