annealingsimulation.cs

//dianthus simulation
class SimulatedAnnealingProgram
{
  static Random random;
	//static void Main(string[] args)
	public SimulatedAnnealingProgram()
	{
		try
		{
			// Set up problem data.
			random = new Random(0);
			int numWorkers = 4;
			int numTasks = 5;
			double[][] problemData = MakeProblemData(numWorkers, numTasks);
			// Create random state.
			int[] state = RandomState(problemData);
			double energy = Energy(state, problemData);
			int[] bestState = state;
			double bestEnergy = energy;
			int[] adjState;
			double adjEnergy;
			// Set up SA variables for temperature and cooling rate.
			int iteration = 0;
			int maxIteration = 1000000;
			double currTemp = 10000.0;
			double alpha = 0.995;
			while (iteration < maxIteration && currTemp > 0.0001)
			{
				// Create adjacent state.
				adjState = AdjacentState(state, problemData);
				// Compute energy of adjacent state.
				adjEnergy = Energy(adjState, problemData);
				// Check if adjacent state is new best.
				if (adjEnergy < bestEnergy)
				{
					bestState = adjState;
					bestEnergy = adjEnergy;
					Console.WriteLine("New best state found:");
					Display(bestState);
					Console.WriteLine("Energy = " + bestEnergy.ToString("F2") + "\n");
				}
				// If adjacent state better, accept state with varying probability.
				double p = random.NextDouble();
				if (AcceptanceProb(energy, adjEnergy, currTemp) > p)
				{
					state = adjState;
					energy = adjEnergy;
				}
				// Decrease temperature and increase iteration counter.
				currTemp = currTemp * alpha;
				++iteration;
			}
			// Display best state found.
		}
		catch (Exception ex)
		{
			Console.WriteLine(ex.Message);
			Console.ReadLine();
		}
	}
	
	static double[][] MakeProblemData(int numWorkers, int numTasks)
	{
		double[][] result = new double[numWorkers][];
		for (int w = 0; w < result.Length; ++w)
			result[w] = new double[numTasks];
		
		//worker -> task
		//result[0][0] = 7.5; result[0][1] = 3.5; result[0][2] = 2.5;
		//result[1][1] = 1.5; result[1][2] = 4.5; result[1][3] = 3.5;
		//result[2][2] = 3.5; result[2][3] = 5.5; result[2][4] = 3.5;
		//result[3][3] = 6.5; result[3][4] = 1.5; result[3][5] = 4.5;
		//result[4][0] = 2.5; result[4][4] = 2.5; result[4][5] = 2.5;
		
		//vertex - > vertex
		result[0][0] = 2; result[0][1] = 2;
		result[1][2] = 5;
		result[2][3] = 10;
		result[3][4] = 1;
		
		return result;
	}
	
	static int[] RandomState(double[][] problemData) 
	{ 
		int numWorkers = problemData.Length;
		int numTasks = problemData[0].Length;
		int[] state = new int[numTasks];
		for (int t = 0; t < numTasks; ++t) 
		{
			int w = random.Next(0, numWorkers);
			while (problemData[w][t] == 0.0) 
			{
				++w; 
				if (w > numWorkers - 1) w = 0;
			}
			state[t] = w;
		}
		return state;
	}
	
	static int[] AdjacentState(int[] currState,
	double[][] problemData) 
	{ 
		int numWorkers = problemData.Length;
		int numTasks = problemData[0].Length;
		int[] state = new int[numTasks];
		int task = random.Next(0, numTasks);
		int worker = random.Next(0, numWorkers);
		while (problemData[worker][task] == 0.0) 
		{
			++worker; 
			if (worker > numWorkers - 1) worker = 0;
		}
		currState.CopyTo(state, 0);
		state[task] = worker;
		return state;
	}
	
	static double Energy(int[] state, double[][] problemData) 
	{ 
		double result = 0.0;
		for (int t = 0; t < state.Length; ++t) 
		{
			int worker = state[t];
			double time = problemData[worker][t];
			result += time;
		}
		int numWorkers = problemData.Length;
		int[] numJobs = new int[numWorkers];
		for (int t = 0; t < state.Length; ++t) 
		{
			int worker = state[t];
			++numJobs[worker];
			if (numJobs[worker] > 1) result += 3.50;
		}
		return result;
	}
	
	static double AcceptanceProb(double energy, double adjEnergy,
	double currTemp) 
	{ 
		if (adjEnergy < energy)
			return 1.0;
		else
			return Math.Exp((energy - adjEnergy) / currTemp);
	}
	
	static void Display(double[][] matrix) 
	{ 
		for (int i = 0; i < matrix.Length; ++i) 
		{
			for (int j = 0; j < matrix[i].Length; ++j)
				Console.Write(matrix[i][j].ToString("F2") + " ");
			Console.WriteLine("");
		}
	}
	
	static void Display(int[] vector)
	{
		for (int i = 0; i < vector.Length; ++i)
			Console.Write(vector[i] + " ");
		Console.WriteLine("");
	}
	
	static void Interpret(int[] state, double[][] problemData)
	{
		for (int t = 0; t < state.Length; ++t) 
		{ // task
			int w = state[t]; // worker
			Console.Write("Task [" + t + "] assigned to worker ");
			Console.WriteLine(w + ", " + problemData[w][t].ToString("F2"));
		}
	}
}

void Main()
{
	new SimulatedAnnealingProgram();
}

// Define other methods and classes here