pheromonetable.cs

ACO.zip是一个蚁群优化算法

using System;
using System.Collections;

namespace ACO
{
	/// <summary>
	///
	/// </summary>
	public class PheromoneTable
	{
		// the possible nodes to chose
		public TableEntry[] tableEntry;
		// the node ID of which this pheromone table belongs to
		public int NodeID;

		// returns the next Node of the path
		public int ProbablePath(ArrayList VisitedNodes)
		{
			// create a random generator
			Random r = new Random(Global.Seed);

			double val=0;
			double count = 0;
			double Lastcount = -1;
	
			ArrayList tempTEVector=new ArrayList();

			// loop through all the connected nodes
			for(int i=0;i<tableEntry.Length;i++)
			{
				// has the node been visitied?
				bool v=false;

				//loop through all the visited nodes
				for(int j=0;j<VisitedNodes.Count;j++)
				{
					// if the ID's match then this node has alrady been visited
					if(tableEntry[i].NodeID==(int)VisitedNodes[j])
						v=true;
				}
				
				// If v is false then the node hasnt been visited.. so Add
				if(!v) 
				{
					// get the node
					Node n = Global.Nodes[tableEntry[i].NodeID];

					// if the node is accepting connections
					if(!n.FullCapacity)
					{
						// add the node as a possible candidate
						tempTEVector.Add(tableEntry[i]);
					}
				}
			}
			
			// if all connections have been visited
			if(tempTEVector.Count==0)
			{
				// loop through all the connected nodes
				for(int i=0;i<tableEntry.Length;i++)
					tempTEVector.Add(tableEntry[i]);
			}

			// get the ceiling amount for probabilities
			for(int i=0;i<tempTEVector.Count;i++)
				val+= ((TableEntry)tempTEVector[i]).Probablilty;

			//create randon value
			val = r.NextDouble()*val;

			// loop through the temp Table Entryies
			for(int i=0;i<tempTEVector.Count;i++)
			{
				// increment the count on each loop
				count += ((TableEntry)tempTEVector[i]).Probablilty;

				// if the random value falls into delegated range then select that path as the next node
				if(val>Lastcount && val < count)
					return ((TableEntry)tempTEVector[i]).NodeID;

				// get the value of the last count
				Lastcount=count;
			}

			// method should never return here
			return -1;
		}

		// updates the probabilities of the pheromone table by multiplying the selected 
		// nodes probability by a radio of  newVal
		public void UpdateProbabilities(double newVal, int EntryTableNodeID)
		{
			TableEntry t;
			double total=0;

			// loop through all the table entries
			// get the total enumeration of probabilities and add the new value.
			// Since this total will be more than 100 a ratio multiplication is
			// applied. Although these values will not equate to exactly 100% floating
			// point calculations will be accurate enough at least 99.99999% which is satisfactory
			for(int j=0;j<tableEntry.Length;j++)
			{
				t = tableEntry[j];

				// enumerate the total probablility
				total += t.Probablilty;
				
				// if the table entry matches the id of the chosen node path
				if(EntryTableNodeID==t.NodeID)
				{
					// add the new value to the total
					total += newVal;
					t = tableEntry[j];
					// add the new value the current value of the selected path
					t.Probablilty += newVal;
				}
			}

			// calculate the ratio for the multiplcation
			double ratio = 100/total;

			// loop through each table entry and multiple the current probability
			// by the new ratio
			for(int j=0;j<tableEntry.Length;j++)
			{
				tableEntry[j].Probablilty *= ratio;
			}

			// this will enumerate all the values to 99.99999%
		}

		// Constructor takes a node to represent and a list of all connected nodes off the
		// calling node
		public PheromoneTable(Node n, int[] conns)
		{
			this.NodeID = n.ID;
		
			// create a tableEntry array the same length as the number of connections
			this.tableEntry = new TableEntry[conns.Length];

			// create a new tableEntry for each connection
			for(int i=0;i<conns.Length;i++)
				tableEntry[i] = new TableEntry(conns[i]);

			// set default equal values
			for(int i=0;i<conns.Length;i++)
				tableEntry[i].Probablilty = (100 / (double)conns.Length);
		}
	}

	// The table entry is a data structure containing a node id and its probablility of
	// being chosen
	public class TableEntry
	{
		// the id of the node
		public int NodeID;
		// the probability of the node being the optimal route
		public double Probablilty;

		// creates a node entry
		public TableEntry(int nodeID)
		{
			this.NodeID = nodeID;
		}
	}
}