using System;

using System.CodeDom;

using System.Collections.Generic;

using System.IO;

using System.Linq;

using System.Runtime.InteropServices;

using System.Text;

using System.Threading.Tasks;

using System.Threading;

using System.Diagnostics;

​

namespace JilFrühwirt                                   

{       

            public class Point                              //1.) Define class Point & Resulting Tour 

            {                                               // member variables 

                public int ID { get; set; }                 // property

                public int X { get; set; }                  // property

                public int Y {get; set; }                   // property

                public Point ( int id, int x, int y) // Constructor that sets the properties  

                {

                    ID=id;                                  // watch upper and lower case

                    X=x;                                    // watch upper and lower case

                    Y=y;                                    // watch upper and lower case

                }

                public double DistanceToPoint (Point p)     // Method to calculate the Distance between the point 

                {

                var temp1 = Math.Pow((this.X - p.X), 2);    // with .X and .Y we access the property of the class Point

                var temp2 = Math.Pow((this.Y - p.Y), 2);

                var result = Math.Sqrt(temp1+temp2);        

                return result;                  

                } 

            }   

                public class ResultingTour              

                    {

                    public double Distance {get;set;}   

                    public double CumulativeSum {get;set;}

                    public List<Point> Tour {get;set;}                                          

                    public ResultingTour (List <Point> tour, double distanceofthetour) // Constructor that sets the properties 

                    {

                        Distance = distanceofthetour;

                        Tour = tour;

                        CumulativeSum = 0;

                    }

                 }

​

            public class GenericAlgorithm                                                           

            {

                public List<Point> PointList;               // declaration PointList 

                public List<ResultingTour> solutions =  new List<ResultingTour>(); // declaration & initalisation

                public List<ResultingTour> NewSolutions =  new List<ResultingTour>();

                // Adjust parameters

                public double mutation = 5;             // Probability of mutation occurance 

                public int solutionCount = 100;         // Amount of tours in generation

                public int tournamentCount = 20;        // Amount of tournament canidates

                public int stopcrit = 100;              // Amount of past generations

                public int seed = 500;                  // Test with 100, 200, 300, 400, 500

​

                // Do not change

                public double meanDistance = 0;         // declaration

                public List<ResultingTour> child;       // declaration child

                public bool stop = false;               // declaration 

                public int generationCount = 0;         // Amount of tours in new generation

                public Random rand = new Random();      // declaration 

                public static void Main (string [] args)                    

                {

                    // Tournamen Selection

                    GenericAlgorithm ga = new GenericAlgorithm();

                    ga.rand = new Random(ga.seed);              // set seed 

                    Stopwatch sw = new Stopwatch();             // needed for calculation of running time

                    sw.Start();                                 // start timer 

​

                    ga.ReadInAll();

                    ga.solutions = ga.Initialization(ga.solutionCount, ga.PointList);

                    while(ga.stop == false)                     // as long as max. number of generations has not been reached 

                    {

                        if(ga.NewSolutions.Count == ga.solutionCount) // if new generation is full

                        {                           

                            ga.solutions = new List<ResultingTour>(ga.NewSolutions); // overwrite old generation with new generation

                            ga.NewSolutions = new List<ResultingTour>();            // empty new generation

                            ga.generationCount++;                                   // increase generation count 

                        }

                        ga.solutions = ga.FitnessEvaluation(ga.solutions);          // calculate fitness value 

                        List<ResultingTour> Parent =  ga.TournamentSelection(ga.tournamentCount, ga.solutions); // Perform tournament selection

                        ga.SinglePointCrossover(Parent);                            // perform crossover

                        ga.SwapMutation();                                          // perform swap

                        ga.StopCrit();                                              // check for stop criterium 

                    }   

                    double bestFit = 0;                                             

                    foreach(var i in ga.solutions)                                  // Search for the best fitness value in last generation

                    {

                        if(i.Distance > bestFit)

                        {

                            bestFit = i.Distance;

                        }

                    }

                    sw.Stop();                                                      // stop timer 

                                                                                    // Get the elapsed time as a TimeSpan value.

                    TimeSpan ts = sw.Elapsed;

                                                                                    // Format and display the TimeSpan value.

                    string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:00}",

                        ts.Hours, ts.Minutes, ts.Seconds,

                        ts.Milliseconds / 10);

                    Console.WriteLine("Tournament Selection");

                    Console.WriteLine("Best Fit: " + bestFit);

                    Console.WriteLine("RunTime " + elapsedTime);

                    //Proportional Selection -> Comments analog to tournament selection 

                    ga.rand = new Random(ga.seed);  // Tested with Seed 100, 200 ,300, 400, 500 

                    sw = new Stopwatch();

                    sw.Start();

                    ga = new GenericAlgorithm();

​

                    ga.ReadInAll();

                    ga.solutions = ga.Initialization(ga.solutionCount, ga.PointList);

                    while(ga.stop == false)

                    {

                        if(ga.NewSolutions.Count == ga.solutionCount)

                        {                           

                            ga.solutions = new List<ResultingTour>(ga.NewSolutions);

                            ga.NewSolutions = new List<ResultingTour>();

                            ga.generationCount++;

                        }

                        ga.solutions = ga.FitnessEvaluation(ga.solutions);

                        List<ResultingTour> Parent =  ga.ProportionalSelection(ga.solutions);

                        ga.SinglePointCrossover(Parent);

                        ga.SwapMutation();

                        ga.StopCrit();

                    }

                    bestFit = 0;

                    foreach(var i in ga.solutions)

                    {

                        if(i.Distance > bestFit)

                        {

                            bestFit = i.Distance;

                        }

                    }

                    sw.Stop();

                    // Get the elapsed time as a TimeSpan value.

                    ts = sw.Elapsed;

​

                    // Format and display the TimeSpan value.

                    elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:00}",

                        ts.Hours, ts.Minutes, ts.Seconds,

                        ts.Milliseconds / 10);

                    Console.WriteLine(" ");

                    Console.WriteLine("Proportional Selection");

                    Console.WriteLine("Best Fit: " + bestFit);

                    Console.WriteLine("RunTime " + elapsedTime);            

                }

                public void ReadInAll()         

                {

                    string [] Givendata =  {"NAME : att48","COMMENT : 48 capitals of the US (Padberg/Rinaldi)","TYPE : TSP","DIMENSION : 48",

                                        "EDGE_WEIGHT_TYPE : ATT","NODE_COORD_SECTION","1 6734 1453","2 2233 10","3 5530 1424","4 401 841","5 3082 1644","6 7608 4458","7 7573 3716","8 7265 1268","9 6898 1885","10 1112 2049","11 5468 2606","12 5989 2873",

                                        "13 4706 2674","14 4612 2035","15 6347 2683","16 6107 669","17 7611 5184","18 7462 3590","19 7732 4723","20 5900 3561",

                                        "21 4483 3369","22 6101 1110","23 5199 2182","24 1633 2809","25 4307 2322","26 675 1006","27 7555 4819","28 7541 3981",

                                        "29 3177 756","30 7352 4506","31 7545 2801","32 3245 3305","33 6426 3173","34 4608 1198","35 23 2216","36 7248 3779",

                                        "37 7762 4595","38 7392 2244","39 3484 2829","40 6271 2135","41 4985 140","42 1916 1569","43 7280 4899","44 7509 3239",

                                        "45 10 2676","46 6807 2993","47 5185 3258","48 3023 1942"};

                            PointList = new List<Point>();                                                                              // initialisation of list Point????

                            for(int i=0; i< Givendata.Length; i++)                                                                      // for loop: you go through each position in the string 

                            {

                                string firstPosition = Givendata[i].Split(new char[0],StringSplitOptions.RemoveEmptyEntries)[0];        // you filter for the first position in the position 

                                int j = 0;

                                if (int.TryParse(firstPosition, out j) == true)                                                         // if cou can convert the first position in the position into a number (int) you continue 

                                {                                                                                                       //...with the if function and add the number to points. If cou cannot convert it into int, the system skipps that position s

                                    int id = Int32.Parse(Givendata[i].Split(new char[0],StringSplitOptions.RemoveEmptyEntries)[0]);     // ID = first Position 

                                    int X = Int32.Parse(Givendata[i].Split(new char[0],StringSplitOptions.RemoveEmptyEntries)[1]);      // x-coordinate = second position 

                                    int Y = Int32.Parse(Givendata[i].Split(new char[0],StringSplitOptions.RemoveEmptyEntries)[2]);      // y-coordinate = third position                        

                                    PointList.Add(new Point(id,X,Y));                                                               // Add point to list

                                }

                            }                                                                           

                }

                public double calculateDistance(List<Point> Tour){                          // total distance of the final tour 

                    double distance = 0;

                    for(int i = 0; i < Tour.Count-1; i++){                                  //For each point in the tour we calculate distance to next point 

                                                                                            //...-1 because the last distance we calcualte is the distance from the (vorletzten) point back to the Startpoint

                        distance = distance + Tour[i].DistanceToPoint(Tour[i+1]);

                    }

                    return distance;

                }

                static public List<Point> RandomTour(List <Point> Points, Random rand)      // Generation random tour

                {               

                        var temp = new List<Point>(Points);                                 // copy PointList

                        List<Point> Tour = new List<Point> ();                              // declaration 

                        while(temp.Count > 0)                                               // while temp still has nodes in it 

                        {

                            int remainingCount = temp.Count-1;                              // get highest index of remaining list

                            int randomID = rand.Next(remainingCount);                       // generat random number between random numb. and highest index

                            Tour.Add(temp[randomID]);                                       // add node with random ID to tour

                            temp.RemoveAt(randomID);                                        // remove ID from remaining list 

                        }       

                    return Tour;    

                }

                public List<ResultingTour> Initialization(int numberSolution, List<Point> Points){  // Creation of first/initial generation 

                    solutions = new List<ResultingTour>();

                    double sum = 0;

                    for(int i = 0; i < numberSolution; i++){            //  As long as max number of solutions has not been reached             

                        List<Point> Tour = RandomTour(Points, rand);    // create random tour 

                        double Distance = calculateDistance(Tour);      // calculate distance of tour

                        sum += Distance;                                // Add distance to overall distance 

                        solutions.Add(new ResultingTour(Tour, 0));      // Add tour to solutions

                    }

                    meanDistance = sum / numberSolution;                // Average distance of initial generation

                    return solutions;

                }

                public List<ResultingTour> FitnessEvaluation(List<ResultingTour> solutions){    // Calculate fitness 

                    foreach(var i in solutions){                                                // for each tour 

                        i.Distance = meanDistance/calculateDistance(i.Tour);                    // calculate fitness value 

                    }

                    return solutions;

                }

                public List<ResultingTour> TournamentSelection(int tournamentSize, List<ResultingTour> solutions){  

                    //Tournament Selection for 2 Parents

                    List<ResultingTour> candidates = new List<ResultingTour>(solutions.OrderBy(x => rand.Next()).Take(tournamentSize));// Select k-random tours

                    List<ResultingTour> chosen = new List<ResultingTour>();     // list for parents 

                    int parentsFree = 2;                                        // amount of parents available 

                    while(parentsFree > 0){                                     // As long as there is still place available 

                        double totalCandidatesDistance = 0;                     // declaration & initialization

                        foreach(var i in candidates)

                        {

                            totalCandidatesDistance = totalCandidatesDistance + i.Distance; // total distance of all candidates 

                            i.CumulativeSum = totalCandidatesDistance;                      // cumulated sum until candidate i

                        }

​

                        double sepPoint = rand.NextDouble() * totalCandidatesDistance;      // calculate random cutpoint of number 

                        ResultingTour parent = candidates.FirstOrDefault(i => i.CumulativeSum >= sepPoint); // select first candidate who's cum.sum exceeds cutpoint

                        chosen.Add(parent);                 // Add parent

                        candidates.Remove(parent);          // Remove point from Candidate list!

                        parentsFree--;                      // Reduce free slot 

                    }

                    return chosen;

                }

                public List<ResultingTour> ProportionalSelection(List<ResultingTour> solutions){

                    //Proportional Selection for 2 Parents

                    List<ResultingTour> candidates = new List<ResultingTour>(solutions); // Select all 

                    List<ResultingTour> chosen = new List<ResultingTour>();             // list for parents

                    int parentsFree = 2;                                                // amount of parents available 

                    while(parentsFree > 0){                                             // same as with tournament selection 

                        double totalCandidatesDistance = 0;                 

                        foreach(var i in candidates)

                        {

                            totalCandidatesDistance = totalCandidatesDistance + i.Distance;

                            i.CumulativeSum = totalCandidatesDistance;

                        }

​

                        double sepPoint = rand.NextDouble() * totalCandidatesDistance;

                        ResultingTour parent = candidates.FirstOrDefault(i => i.CumulativeSum >= sepPoint);

                        chosen.Add(parent);

                        candidates.Remove(parent);

                        parentsFree--;

                    }

                    return chosen;

                }

                public void SinglePointCrossover(List<ResultingTour> chosen){       // Perform crossover!

                    int cutPoint = rand.Next(chosen[0].Tour.Count-1);               // get random cutpoint between zero and highest index

                    child = new List<ResultingTour>();                              // declaration & initialization of child list

                    List<Point> childTourOne = new List<Point>();                   // declaration & initialization

                    List<Point> childTourTwo = new List<Point>();                   // declaration & initialization

                    for(int i = 0; i < chosen[0].Tour.Count; i++){                  // as long as there are remaining nodes in the parents list 

                        if(i <= cutPoint){                                          // if i is smaller/ equal to cutpoint index

                            childTourOne.Add(chosen[0].Tour[i]);                    // Add left side of parent 1 to first child

                            childTourTwo.Add(chosen[1].Tour[i]);                    // Add left side of parent 2 to second child 

                        }else if(i > cutPoint){

                            childTourOne.Add(chosen[1].Tour[i]);                    // Add right side of second parent to first child 

                            childTourTwo.Add(chosen[0].Tour[i]);                    // Add right side of first parent to second child 

                        }

                    }

                    double childDistanceOne = meanDistance / calculateDistance(childTourOne);   // calculate fitness value of child one 

                    double childDistanceTwo = meanDistance / calculateDistance(childTourTwo);   // calculate fitness value of child two 

                    child.Add(new ResultingTour(childTourOne,childDistanceOne));                // Add children to list 

                    child.Add(new ResultingTour(childTourTwo,childDistanceTwo));                // Add children to list 

                }       

                public void SwapMutation(){                                         // Perfrom Mutation

                    ResultingTour childTourOne = child[0];                          

                    ResultingTour childTourTwo = child[1];

                    if(rand.Next(0,100) <= mutation){                               // generate random number between 0 and 100 

                        // Swap Child One

                        int positionOne = rand.Next(childTourOne.Tour.Count-1);     // generate two random index

                        int positionTwo = rand.Next(childTourOne.Tour.Count-1);

                        Point temp = childTourOne.Tour[positionOne];                // swap nodes at two indexes 

                        childTourOne.Tour[positionOne] = childTourOne.Tour[positionTwo];

                        childTourOne.Tour[positionTwo] = temp;

                        // Swap Child Two                                           // analog to first child

                        positionOne = rand.Next(childTourOne.Tour.Count-1);

                        positionTwo = rand.Next(childTourOne.Tour.Count-1);

                        temp = childTourTwo.Tour[positionOne];

                        childTourTwo.Tour[positionOne] = childTourOne.Tour[positionTwo];

                        childTourTwo.Tour[positionTwo] = temp;

                    }

                    NewSolutions.Add(childTourOne);                                 // add children to new generation 

                    NewSolutions.Add(childTourTwo);

                }   

                public void StopCrit(){                             // Stop criterium 

                    if(generationCount == stopcrit)                 // if enough generations have been created

                    {               

                        stop = true;                                // set stop criterium to true! 

                    }

                }

            }

}

​