用C#实现蚁群算法解决TSP问题
using System;
using System.Collections.Generic;
using System.Text;
namespace AntSystem
{
public class AA
{
/**////
/// 对信息量的重视程度
///
private int alpha;
/**////
/// 启发式信息的受重视程度
///
private int beta;
/**////
/// 信息素的挥发速度
///
private double lo;
/**////
/// 城市距离矩阵
///
private double[,] City;
/**////
/// 信息素矩阵
///
private double[,] Message;
/**////
/// opneList用于存放下一步可行城市
///
private Queue
/**////
/// closedList用于存放已经访问过的城市
///
private Queue
/**////
/// 储存较好的路径
///
private Queue
private int Pro_time = 0;
/**//////////////////////////////////////////////////////// //
///
/// 构造函数：形成城市距离和信息素矩阵
///
/// 城市距离矩阵
/// 信息素的挥发速度
public AA(double[,] city,double Lo,int Alpha,int Beta)
{
alpha = Alpha;
beta = 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++)
{
City[i, j] = city[i, j];
}
}
//初始化信息素矩阵
for (int i = 0; i < temp; i++)
{
for (int j = 0; j < temp; j++)
{
if (i != j)
{
Message[i, j] = (double)1 / (temp * temp - temp);
}
}
}
}
/**//////////////////////////////////////////////////////// /////
///
/// 改变信息素矩阵，closed_list为较好的路径
///
///
private void Change_Message(Queue
{
lock (this)
{
int[] temp_Array = new int[closed_list.Count];
temp_Array = closed_list.ToArray();
for (int i = 0; i < closed_list.Count - 1; i++)
{
Message[temp_Array[i], temp_Array[i + 1]] = Message[temp_Array[i], temp_Array[i + 1]] + lo / ((1 - lo)
*Convert.ToInt32(Get_Weight(closed_list)+1));
}
Message[temp_Array[temp_Array.Length - 1],
temp_Array[0]] = Message[temp_Array[temp_Array.Length - 1],
temp_Array[0]] + lo / ((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++)
{
Message[i, j] = (1 - lo) * Message[i, j];
}
}
}
}
/**//////////////////////////////////////////////////////// ////////
///
/// 输入一个链表，计算出其对应的总路径
///
///
///
public double Get_Weight(Queue
{
lock (this)
{
double sum = 0;
int[] temp_Array = new int[closed_list.Count];
temp_Array = closed_list.ToArray();
for (int i = 0; i < Convert.ToInt32(temp_Array.Length) - 1; i++)
{
sum = sum + City[temp_Array[i], temp_Array[i + 1]]; }
sum = sum + City[temp_Array[temp_Array.Length - 1], temp_Array[0]];
return sum;
}
}
/**////////////////////////////////////////////////////////
///////
///
/// 产生到i城市后，下一个可走城市的集合。并将城市编号加入到openList中。
/// 产生的城市不可以已经存在closedList中
///
///
private void NextCity()
{
openList.Clear();
int temp_int=Convert.ToInt32(Math.Sqrt(City.Length));
for (int i = 0; i < temp_int; i++)
{
if (closedList.Contains(i) ==false)
{
openList.Enqueue(i);
}
}
}
/**//////////////////////////////////////////////////////// ///////
///
/// 选择应该走那条路，选择完路A后，清空openList，再把A加入到openList中
///
///
private int choiceRoute()
{
int index = 0;//记录选择的城市
Random random = new Random();
double random_value =(double) random.NextDouble();//随机选择的概率
int[] temp_Array=new int [openList.Count];
temp_Array=openList.ToArray();
double sum_Message = 0;//openList所有节点的总信息量
for (int i = 0; i < openList.Count; i++)
{
double eta = 1 / City[Pro_time, temp_Array[i]];
sum_Message = sum_Message +Math.Pow(Message[Pro_time, temp_Array[i]],alpha)*Math.Pow (eta,beta);
}
double temp=0;
for (int j = 0; j < openList.Count; j++)
{
double eta = 1 / City[Pro_time, temp_Array[j]];
temp=temp+Math.Pow(Message[Pro_time,temp_Array[j]], alpha)*Math.Pow(eta,beta)/sum_Message;
if (temp > random_value)
{
index = temp_Array [j];
break;
}
}
openList.Clear();
openList.Enqueue(index);
return index;
}
/**//////////////////////////////////////////////////////// //////
public Queue
{
BestList.Clear();
/**////共循环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.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
int[Convert.ToInt32(Math.Sqrt(City.Length))];
temp_Array = closedList.ToArray(); for (int k = 0; k <
Convert.ToInt32(Math.Sqrt(City.Length)); k++)
{
BestList.Enqueue(temp_Array[k]) ;
}
}
if (Get_Weight(BestList) >
Get_Weight(closedList))
{
BestList.Clear();
int[] temp_Array = new
int[Convert.ToInt32(Math.Sqrt(City.Length))];
temp_Array = closedList.ToArray(); for (int k = 0; k <
Convert.ToInt32(Math.Sqrt(City.Length)); k++)
{
BestList.Enqueue(temp_Array[k]) ;
}
}
}
NextCity();
choiceRoute();
}
}
Change_Message(BestList);//修改信息量
}
return BestList;
}
}
}