سورس پروژه TSP با الگوریتم مورچگان Ants
شرح مساله فروشنده دوره گرد بدین شکل است:
یک محیط را در نظر بگیرید که در آن تعدادی شهر داریم و هزینه مستقیم رفتن از شهری به شهر دیگر را میدانیم. حال باید کمهزینهترین مسیری که از یک شهر شروع می شود و از همه شهرها تنها یکبار عبور می کند و به شهر اولی بازمی گردد را پیدا کنیم.
این مساله را میتوان با الگوریتم های مختلفی حل کرد که یکی از این الگوریتم ها الگوریتم مورچگان یا Ant می باشد.
روش کار کلونی مورچگان به این شکل است که مورچه ها وقتی از یک مسیر عبور می کنند در مسیر خود ماده ای بر جای می گزارند که فرومون نام دارد.
هر مسیری که مورچه بیشتری از آن عبور کرده باشد فرومون بیشتری در ان ریخته شده است و احتمال اینکه مورچه های دیگر جذب این مسیر شوند بیشتر است.
از این روش برای حل مساله TSP نیز بهره گرفته ایم. و در نهایت مسیری که فرومون بیشتری در ان ریخته شده است مسیر بهینه اعلام می شود.
در این برنامه از روش تردینگ threading یا همان چند نخی بهره گرفته ایم . در واقع هر مورچه یک Thread جدا ست.ولی محیط برای همه مورچه ها یکی است.
قیمت 3000 تومان
این هم کد برنامه که می توانید در سی شارپ از آن بهره بگیرید
using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms; using System.Threading;
namespace ant_tsp { public partial class Form1 : Form { public Form1() { InitializeComponent(); }
#region publics کلی فضای public const int d= 6;//city counts // public const float tabkhir=0.99 ; int[] city = { 0, 1, 2, 3, 4, 5};
// 0 1 2 3 4 5 int[,] path_main = { { 0, 5, 2, 3, 8, 6 },//0 طول مسیر ، فاصله شهر ها از هم { 5, 0, 2, 3, 4, 5 }, //1 { 2, 2, 0, 3, 4, 5 }, //2 { 3, 3, 3, 0, 8, 6 },//3 { 8, 4, 4, 8, 0, 5 }, //4 { 6, 5, 5, 6, 5, 0} //5 }; int start_place=0; int end_ants = 0,stop_time=0,max_ant=1000; float [,] path_ph = new float [6, 6];// مقدار فرومون ریخته شده توسط مورچه ها اینجا قرار میگیرد
public delegate void endsend(); endsend sh_f; int mm;
#endregion private void ant() { int s_t = stop_time; Thread.Sleep(s_t);//یک وقفه برای اینکه مورچه ها تقریبا با هم کارشون رو شروع کنند //initialize
int place_me = start_place; List city_tomove = new List();// شهرهایی که میشود از مکان فعلی رفت،تکراری نباشد foreach (int i in city) if (i != place_me) city_tomove.Add(i); int c_count = city_tomove.Count+1; for (int c = 0; c < c_count; c++) { if (city_tomove.Count == 0) city_tomove.Add(start_place); //choose(select) city to move //انتخاب مسیر بر حسب فرومون موجود در مسیر // مسیری که فرومون ندارد شانسش 1 است // شانس بقیه 1+فرومون موجود float sum_phromone=0; float [] path_phtemp = new float [d]; for (int i = 0; i < city_tomove.Count; i++) { sum_phromone += path_ph[place_me,city_tomove[i]] + path_ph[city_tomove[i],place_me] + 1;//به دست آوردن مجموع شانس ها path_phtemp[i] = sum_phromone;// شانس هر یک از شهرهای مسیر } Random r = new Random(); int choose_r=0; choose_r = r.Next(Convert.ToInt32( sum_phromone));// انتخاب یک عدد از کل شانسها int choose = 0; for (int i = 0; i < city_tomove.Count; i++) if (choose_r <= path_phtemp[i])//مقایسه اینکه عدد متعلق به کدام شهر است { choose = city_tomove[i]; break; } //move Thread.Sleep(path_main[place_me, choose]);//شبیه سازی زمان پیمایش مسیر ، یعنی مورچه به اندازه طول مسیر زمان برده تا به اینجا رسیده path_ph[place_me, choose] += 2;//(10- path_main[place_me, choose]); place_me = choose; city_tomove.Remove(choose );//نمیتواند به خودش برود
}
} private void send_ant() { for ( mm = 0; mm < max_ant; mm++) { stop_time = max_ant+1000-mm ;//2000 - mm;// یک زمان مکث برای هر مورچه تا کارشان را تقریبا با هم شروع کنند start_place = 5; Thread t = new Thread(new ThreadStart(ant)); t.IsBackground = true; t.Start(); } this.Invoke(sh_f); } private void button1_Click(object sender, EventArgs e) { // مورچه فرستاده میشود end_ants = 0; Thread t = new Thread(new ThreadStart(send_ant)); t.IsBackground = true; t.Start(); timer1.Enabled = true; } private void show_final() { label2.Text = "ants sended ";// +end_ants.ToString(); Application.DoEvents(); Thread.Sleep(max_ant+1000); timer1.Enabled = false; // نمایش میزان فرومون ها در پایان string ss = ""; for (int i = 0; i < d; i++) { for (int j = 0; j < d; j++) ss += Convert.ToInt32(path_ph[i, j]).ToString() + " _ "; listBox1.Items.Add(ss); ss = ""; } listBox1.Items.Add("______________________________"); label1.Text = end_ants.ToString() + " ants ended work";
// محاسبه طول بهترین مسیر یافت شده float sum = 0; int p_me = start_place; listBox2.Items.Add(p_me); List city_tomove = new List(); for (int j = 0; j < d; j++) if (j != p_me) city_tomove.Add(j); for (int i = 0; i < d-1; i++) { float max = path_ph[p_me, 0]; int max2 =city_tomove[0];
for (int k = 1; k < city_tomove.Count; k++) if (max { max = path_ph[p_me, city_tomove[k]]; max2=city_tomove[k]; } sum += path_main[p_me, max2]; p_me = max2; city_tomove.Remove(max2); listBox2.Items.Add(p_me); } listBox2.Items.Add("___"); label5.Text +=" sum: "+ sum.ToString();
sh_f = new endsend(show_final);
} private void timer1_Tick(object sender, EventArgs e) { label2.Text="started ants: "+ mm.ToString(); label1.Text = "ended ants: " + end_ants.ToString();
// تبخیر فرومون for (int i = 0; i < d; i++) for (int j = 0; j < d; j++) if (path_ph[i, j] > 0) path_ph[i, j] *= (float)0.8; }
private void label6_Click(object sender, EventArgs e) { System.Diagnostics.Process.Start("http://www.sourcecodes.ir"); } } }
نشانی ایمیل شما منتشر نخواهد شد. بخشهای موردنیاز علامتگذاری شدهاند *
Current ye@r *
Leave this field empty
Copyright © 2010 Dlbook Team