simulatedannealing.cs

using System;
using System.Collections;

public class City
{
    public int x, y;

    public City(int p1, int p2)
    {
        x = p1;
        y = p2;
    }

    public City(int mapRange)
    {
        x = new Random().Next(1, mapRange);
        y = new Random().Next(1, mapRange);
    }

    public override string ToString()
    {
        return x.ToString() + "," +  y.ToString();
    }
}

public class Solution
{
    // find a way to specify ax cities so u dont run out of index
    private ArrayList cities = new ArrayList();
    private double tourLength;

    public City GetCityByIndex(short index)
    {
        return (City)cities[index];
    }

    public double TourLength()
    {
        return tourLength;
    }

    public void SetTourLength(double computedTourLength)
    {
        tourLength = computedTourLength;
    }

    public void SwapCities(short indexOne, short indexTwo)
    {
        City temp = (City)cities[indexOne];
        cities[indexOne] = cities[indexTwo];
        cities[indexTwo] = temp;
    }

    public String ToString(String separator = " --> ")
    {
        String tourString = "|";
        for (int i = 0; i < cities.Count; i++)
        {
            tourString += ((City)cities[i]) + separator; 
        }

        return tourString;
    }

    public Solution(City[] map)
    {
        for (short index = 0; index < map.Length; index++)
        {
            cities.Add(map[index]);
        }
    }

    public Solution(ArrayList citiesMap)
    {

        cities.AddRange(citiesMap);
    }

    public static Solution copySolution(Solution aSolution)
    {
        return new Solution(aSolution.cities)
        {
            tourLength = aSolution.tourLength
        };
    }
}

namespace SimulatedAnnealing
{
    public class Algr1
    {
        private double Temperature = 10000; // initial temp
        private readonly short MAXCITIES = 10;
        private readonly double ALPHA = 0.03; // cooling schedule
        private readonly City[] map = {
            new City(60, 200), new City(180, 200), new City(80, 180),
            new City(140, 180), new City(20, 160), new City(100, 160),
            new City(200), new City(200), new City(200),
            new City(200)
        };


        public Algr1()
        {

        }

        public void Start()
        {
            // get a random current solution
            // also u need initial temperature
            // solution is a list of cities with associated tour_length
            // so a tour is a list 
            double deltaE;
            Solution curSolution = new Solution(map);
            Solution tempSolution;
            short MONTECARLOITERATIONS = 10;
            ComputeTour(ref curSolution);
            System.Console.WriteLine("Initial solution tour length: {0}: ", curSolution.TourLength());
            System.Console.WriteLine(curSolution.ToString());

            while (this.Temperature > 0.001)
            {
                // copy curr solution to temp
                tempSolution = Solution.copySolution(curSolution);
                for (short iterationCount = 0; iterationCount < MONTECARLOITERATIONS; iterationCount++)
                {
                    PerturbSolution(ref tempSolution);
                    ComputeTour(ref tempSolution);
                    deltaE = tempSolution.TourLength() - curSolution.TourLength();
                    // new solution better than current
                    // i.e smaller
                    if (deltaE < 0.0)
                    {
                        // accept new solution
                        curSolution = Solution.copySolution(tempSolution);
                    }
                    else
                    {
                        // probabilistically accept worse soliution
                        if (AcceptWorseSolution(deltaE))
                        {
                            curSolution = Solution.copySolution(tempSolution);
                        }
                    }
                }
                // decrease temp
                Temperature *= ALPHA;

            }

            System.Console.WriteLine("Best solution: {0}", curSolution.TourLength());
            System.Console.WriteLine(curSolution.ToString());
        }

        private void PerturbSolution(ref Solution aSolution)
        {
            short indexOne, indexTwo;
            do
            {
                indexOne = (short)new Random().Next(0, MAXCITIES - 1);
                indexTwo = (short)new Random().Next(0, MAXCITIES - 1);
            } while (indexOne == indexTwo);
            aSolution.SwapCities(indexOne, indexTwo);
        }

        private void ComputeTour(ref Solution aSolution)
        {
            // get the tour length of a tour
            double tourLength = 0.0;
            short i;
            for (i = 0; i < MAXCITIES - 1; i++)
            {
                tourLength += EuclideanDistance(aSolution.GetCityByIndex(i), aSolution.GetCityByIndex((short)(i + 1)));
            }

            tourLength += EuclideanDistance(aSolution.GetCityByIndex((short)(MAXCITIES - 1)), aSolution.GetCityByIndex(0));
            aSolution.SetTourLength(tourLength);
        }

        private double EuclideanDistance(City a, City b)
        {
            return System.Math.Sqrt(System.Math.Pow((a.x - b.x), 2) + System.Math.Pow((a.y - b.y), 2));
        }

        private bool AcceptWorseSolution(double deltaEnergy)
        {
            return System.Math.Exp(-deltaEnergy / Temperature) > new Random().NextDouble();
        }
    }
}