Artificial Intelligence - هوش مصنوعی - ارائه الگوريتم تركيبي مورچگان و ژنتيك براي حل مسئله فروشنده دوره گرد

Artificial Intelligence - هوش مصنوعی (http://artificial.ir/intelligence/)

- الگوریتم ژنتیک(Genetic Algorithm) (http://artificial.ir/intelligence/forum24.html)

ارائه الگوريتم تركيبي مورچگان و ژنتيك براي حل مسئله فروشنده دوره گرد

این مقاله یکی از مقالاتی بود که توی کنفرانس بین المللی صنایع ارائه داده شد. و جزء مقالات معتبر شناخته شد. در این مقاله مسئله ی معروف فروشنده با ژنتیک الگوریتم حل شده .

مسئله فروشنده دوره گرد از n شهر تشكيل شده كه بين هر دو شهرآن يك مسير مي تواند وجود داشته باشد . فروشنده دوره گرد مي خواهد از يكي از اين شهرها مسير خود را شروع كرده و سپس به كليه شهرها مسافرت كند و از هر يك از شهرها يكبار فقط بگذرد.

راه حل این مساله رو توی مقاله ببینید.

ارائه الگوريتم تركيبي مورچگان و ژنتيك براي حل مسئله فروشنده دوره گرد

دوست عزيز... در همين انجمن يك Library با نام AForge.net مورد بررسي قرار گرفته كه اگر جستجو كنيد در انجمن پيداش مي كنيد. در اون يكي از مثال هاي بررسي شده در بخش الگوريتم ژنتيك همين مثال فروشنده ي دوره گرد يا TSP‌هست كه با زبان C# پياده سازي شده...
اگر پيداش نكرديد بگيد تا آدرس دقيقتري بدم...

مسئله فروشنده دوره‌گرد ( Travelling salesman problem ،یا TSP ) مسئله‌ای معروفیه که اولین بار مسائل مربوط به اون توسط ویلیام همیلتون و توماس کرکمن مطرح شد و بعد در دهه ۱۹۳۰ شکل عمومی اون به وسیله ریاضیدانانی مثل کارل منگر از دانشگاه هاروارد و هاسلر ویتنی از دانشگاه پرینستون مورد مطالعه قرار گرفت.

در این مسئله تعداد کل راه‌حل‌ها برابر است :

كد:

1/2 (n-1)! n>2

که در واقع n تعداد شهرهاست. و این عدد برابر است با تعداد دورهای همیلتونی در یک گراف کامل با n رأس.

برای اینکه دقیق تر ببینی این مسئله چطور حل میشه میتونی این برنامه که با ژنتیک الگوریتم نوشته شده رو دانلود و نصب کنی. فکر میکنم اینجوری راحت تر به جواب برسی.

دانلود برنامه فروشنده دوره گرد

نسرین جان بقیه اطلاعات رو هم برات میل کردم. اگه بازم سوالی داشتی حتما بپرس.

نقل قول:

نوشته اصلي بوسيله Di4mond_65 (پست 2092)

سلام.
متاسفانه لینکها کار نمیکنند، اگر میشه مجدد آپ کنید.

مرسی.

لينکها؟
مقاله (ارائه الگوريتم تركيبي مورچگان وژنتيك براي حل مسئله فروشنده دوره گرد) که لينکش درسته!

در مورد اون برنامه فروشنده دوره گرد هم بايد بگم که صاحب و نويسنده اصلي برنامه رو از سايتشون پاک کردند و در نتيجه اون لينک هم ديگه کار نميکنه:)
من قبلاً دانلود کرده بودم ;)
در اينجا آپ ميکنم ولي بايد بگم که از اون اول هم سورس رو قرار نداده بودند و فقط فايل اجرايي هست(البته اينم خيلي جذابه):rolleyes:

نقل قول:

نوشته اصلي بوسيله jojo (پست 2548)

من کد میخوام،کمک دارم مشروط میشم سر همین کد مسئله فروشنده دوره گرد بیکار.
email : hmstar2008_13@yahoo.com

اين کد الگوریتم دوره گرد
ولي
بهتره به لينک زير مراجعه نماييد:
حل مسئله فروشنده دوره گرد

كد:



#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

نقل قول:

نوشته اصلي بوسيله یاقوت (پست 2935)

سلام
در صورت امکان حل معمای 8وزیر با الگوریتم ژنتیک را داخل سایت قرار دهید.

اين مسئله به وسيله الگوريتم ژنتيک در لينک زير(پاورپوينت سوم) توضيح داده شده است;)

اسلاید های آموزشی الگوریتم ژنتیک

همچنين با روشهاي ديگر :
حل مسئله 8 وزير با روش هاي مختلف!
:rolleyes:

نقل قول:

نوشته اصلي بوسيله nasrin_darvishi1376 (پست 860)

با سلام
من سوال داشتم در مورد اینکه چه طور الگوریتم فروششنده دوره گرد با الگوریتم ژنتیک ÷یاده سازی کنم یا برنامه را بنویسم

سلام
فکر میکنم این تاپیک بدردتون می خوره :

کد الگوریتم ژنتیک برای حل مساله tsp با نخبه گزینی

خیش خراش مال
بدطور !!!

اینم برای کمک به همه دوستانم.

فروشنده دوره گرد(Travelling Sales Man)

سلام چطوری tsp را با pso در متلب پیاده سازی کنم؟
ممنون می شم اگه راهنمایی کنید

Demo و سورس

سلام

Demo و سورس برنامه TSP و توضیحاتش برای مقایسه بین کارایی اجرای آن به دو روش Genetic و Ant Colony Optimization در این لینک آورده شده:
Genetic and Ant Colony Optimization Algorithms - CodeProject

خیلی جالبه و در عین حال ملموس !