Csharp實(shí)現(xiàn)蟻群算法解決TSP問(wèn)題

1、C#實(shí)現(xiàn)蟻群算法解決TSP問(wèn)題學(xué)習(xí)了一個(gè)學(xué)期的人工智能，了解到了人工智能的強(qiáng)大力量.很多智能算法真是很令人向往！ 下面是我實(shí)現(xiàn)的蟻群算法.下面介紹一下什么是蟻群算法：主要是一種模擬生物的進(jìn)化：用信息素來(lái)引導(dǎo)螞蟻向比較好的方向前進(jìn).用我們熟悉的魯迅先生的一句話：地上沒(méi)有路，走的人多了也就有了路.（用在蟻群算法身上很好）using System;using System.Collections.Generic;using System.Text;namespace AntSystempublic class AA/*/ <summary>/對(duì)信息量的重視程度/ </summary

2、>private int alpha;/*/ <summary>/啟發(fā)式信息的受重視程度/ </summary>private int beta;/*/ <summary>/信息素的揮發(fā)速度/ </summary>private double lo;/*/ <summary>/城市距離矩陣/ </summary>private double, City;/*/ <summary>/信息素矩陣/ </summary>private double, Message;/*/ <summary&

3、gt;/ opneList用于存放下一步可行城市/ </summary>private Queue<int> openList=new Queue<int> ();/*/ <summary>/ closedList 用于存放已經(jīng)訪問(wèn)過(guò)的城市/ </summary>private Queue<int> closedList=new Queue<int> ();/*/ <summary>/ 儲(chǔ)存較好的路徑/ </summary>private Queue <int> BestLi

4、st=new Queue<int> (); private int Pro_time = 0;/*/ <summary>/ 構(gòu)造函數(shù)：形成城市距離和信息素矩陣/ </summary>/ <param name="city"> 城市距離矩陣 </param>/ <param name="Lo"> 信息素的揮發(fā)速度 </param> public AA(double, city,double Lo,int Alpha,int Beta) alpha = Alpha;beta

5、= Beta;lo=Lo;int temp = Convert.ToInt32( Math.Sqrt(city.Length);City=new double temp,temp;Message=new double temp,temp;for (int i = 0; i < temp; i+)for (int j = 0; j < temp; j+)Cityi, j = cityi, j;/初始化信息素矩陣for (int i = 0; i < temp; i+)for (int j = 0; j < temp; j+)if (i != j)Messagei, j =

6、 (double)1 / (temp * temp - temp);/*/ <summary>/ 改變信息素矩陣， closed_list 為較好的路徑/ </summary>/ <param name="closed_list"></param>private void Change_Message(Queue<int> closed_list)lock (this)int temp_Array = new intclosed_list.Count; temp_Array = closed_list.ToArra

7、y();for (int i = 0; i < closed_list.Count - 1; i+)Messagetemp_Arrayi, temp_Arrayi + 1 = Messagetemp_Arrayi, temp_Arrayi + 1 + lo / (1 - lo) *Convert.ToInt32(Get_Weight(closed_list)+1);Messagetemp_Arraytemp_Array.Length - 1, temp_Array0 = Messagetemp_Arraytemp_Array.Length - 1, temp_Array0 + lo /

8、(1 - lo) *Convert.ToInt32(Get_Weight(closed_list);for (int i = 0; i < closed_list.Count; i+)for (int j = 0; j < closed_list.Count; j+)Messagei, j = (1 - lo) * Messagei, j;/*/ <summary>/ 輸入一個(gè)鏈表，計(jì)算出其對(duì)應(yīng)的總路徑/ </summary>/ <param name="closed_list"></param>/ <ret

9、urns></returns>public double Get_Weight(Queue <int> closed_list)lock (this)double sum = 0;int temp_Array = new intclosed_list.Count;temp_Array = closed_list.ToArray();for (int i = 0; i < Convert.ToInt32(temp_Array.Length) - 1; i+)sum = sum + Citytemp_Arrayi, temp_Arrayi + 1;sum = s

10、um + Citytemp_Arraytemp_Array.Length - 1, temp_Array0;return sum;/*/ <summary>/ 產(chǎn)生到 i 城市后，下一個(gè)可走城市的集合。并將城市編號(hào)加入到 openList 中。/ 產(chǎn)生的城市不可以已經(jīng)存在 closedList 中/ </summary>/ <param name="i"></param>private void NextCity()openList.Clear();int temp_int=Convert.ToInt32(Math.Sqrt(

11、City.Length);for (int i = 0; i < temp_int; i+)if (closedList.Contains(i) =false)openList.Enqueue(i);/*/ <summary>Ill選擇應(yīng)該走那條路，選擇完路A后，清空openList，再把A加入到openList中/ </summary>lll <returns><lreturns>private int choiceRoute()int index = 0;ll 記錄選擇的城市Random random = new Random();do

12、uble random_value =(double) random.NextDouble();ll 隨機(jī)選擇的概率int temp_Array=new int openList.Count;temp_Array=openList.ToArray();double sum_Message = 0;llopenList 所有節(jié)點(diǎn)的總信息量for (int i = 0; i < openList.Count; i+)double eta = 1 l CityPro_time, temp_Arrayi;sum_Message = sum_Message +Math.Pow(MessagePro

13、_time, temp_Arrayi,alpha)*Math.Pow (eta,beta); double temp=0;for (int j = 0; j < openList.Count; j+)double eta = 1 l CityPro_time, temp_Arrayj;temp=temp+Math.Pow(MessagePro_time,temp_Arrayj,alpha)*Math.Pow(eta,beta)/sum_Message; if (temp > random_value)index = temp_Array j;break;openList.Clear

14、();openList.Enqueue(index);return index;/*/public Queue<int> Main_DW()BestList.Clear();/*/ 共循環(huán) 20 次for (int i = 0; i < 4; i+)/*/ 共有 n 只螞蟻 n=City'number Convert.ToInt32(Math.Sqrt(City.Length)for (int j = 0; j < Convert.ToInt32(Math.Sqrt(City.Length); j+)openList.Enqueue(0);closedList.

15、Clear();while (openList.Count != 0 && closedList.Count != Convert.ToInt32(Math.Sqrt(City.Length)int temp = openList.Dequeue();Pro_time = temp;closedList.Enqueue(temp);if (openList.Count = 0 && closedList.Count = Convert.ToInt32(Math.Sqrt(City.Length)if (BestList.Count = 0)int temp_Array = new intConvert.ToInt32(Math.Sqrt(City.Length);temp_Array = closedList.ToArray();for (int k = 0; k < Convert.ToInt32(Math.Sqrt(City.Length); k+)BestList.Enqueue(temp_Arrayk);if (Get_Weight(BestList) > Get_Weight(closedList)BestList.Clear();int temp_Array =