TSP GAopt - in progress...

gistfile1.txt

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Threading;
using System.Drawing;

namespace tsp
{
    class Program
    {
        static Random r = new Random();

        static void Main(string[] args)
        {
            List<City> cities = ReadCities();
            List<City> A = Clone(cities); //cities = Shuffle(cities);
            List<City> B = Clone(cities);
            ReadAnswers(ref A, ref B);
            Gene a = new Gene(A);
            Gene b = new Gene(B);
            
            //GeneticsLinear(a, b);
            GeneticsGapSwap(a, b);

            Console.WriteLine("Starting fitness: " + a.fitness + " : " + b.fitness);

        }
        static void GeneticsLinear(Gene A, Gene B)
        {
            bool finished = false; new Thread(new ThreadStart(() => { Console.ReadLine(); finished = true; })).Start();
            while (!finished)
            {
                bool wait_a = true;
                bool wait_b = true;
                LinearFlips(A, (gene) => { A = gene; wait_a = false; });
                LinearFlips(B, (gene) => { B = gene; wait_b = false; });
                while (wait_a || wait_b) Thread.SpinWait(5);
                Diverge(ref A, ref B);
                Save(A, B);
                A.Draw().Save("a.png");
                B.Draw().Save("b.png");
            }
        }
        static void GeneticsGapSwap(Gene A, Gene B)
        {
            bool finished = false; new Thread(new ThreadStart(() => { Console.ReadLine(); finished = true; })).Start();
            while (!finished)
            {
                bool wait_a = true;
                bool wait_b = true;
                GapSwap(A, (gene) => { A = gene; wait_a = false; });
                GapSwap(B, (gene) => { B = gene; wait_b = false; });
                while (wait_a || wait_b) Thread.Sleep(1000);
                Diverge(ref A, ref B);
                Save(A, B);
                A.Draw().Save("a" + DateTime.Now.ToBinary() + ".png");
                B.Draw().Save("b" + DateTime.Now.ToBinary() + ".png");
            }
        }
        static void LinearFlips(Gene gene, Action<Gene> callback)
        {
            new Thread(new ThreadStart(() =>
            {
                for (int e = 0; e < gene.edges.Count; e++)
                {
                    Gene mutant = gene.Mutate(e);
                    if (mutant.fitness < gene.fitness)
                    {
                        gene = mutant;
                        Console.WriteLine(gene.fitness + "(" + e + "/" + gene.edges.Count + ")");
                        //e -= 2;
                        //if (e < -1) e = -1;
                        e = -1;
                    }
                }
                callback(gene);
            })).Start();
        }
        static void GapSwap(Gene gene, Action<Gene> callback)
        {
            int        threads_per_gene = 3;
            List<bool> thread_waits     = new List<bool>();

            for (int t = 0; t < threads_per_gene; t++)
            {
                thread_waits.Add(true);
                int wait_indie = t;
                int lower      = (gene.edges.Count / threads_per_gene) * t;
                int upper      = ((gene.edges.Count / threads_per_gene) * (t + 1)) - 2; // -2 is the safety zone so two edges arent in the same allocation

                if (threads_per_gene == 1) { lower = 0; upper = gene.edges.Count; }

                new Thread(new ThreadStart(() =>
                {
                    for (int rounds = 0; rounds < 10; rounds++)
                    {
                        for (int e = lower; e < upper; e++)
                        {
                            for (int e2 = e + 3; e2 < upper; e2++)
                            {
                                if (gene.Mutate(e, e2))
                                {
                                    Console.WriteLine(gene.fitness + "(" + e + "/" + e2 + ")");
                                    e  = lower;
                                    e2 = e + 3;
                                    break;
                                }
                            }
                        }
                    }
                    thread_waits[wait_indie] = false;
                })).Start();
            }
            for (int w = 0; w < thread_waits.Count; w++)
            {
                if (thread_waits[w])
                {
                    w = -1;
                    Thread.Sleep(1000);
                }
            }
            callback(gene);
        }
        static void Diverge(ref Gene A, ref Gene B)
        {
            bool recheck = true;
            while (recheck)
            {
                recheck = false;
                Console.WriteLine("Diverging");
                Dictionary<String, Edge> hA = ToDictionary(A.edges);
                Dictionary<String, Edge> hB = ToDictionary(B.edges);
                for (int a = 0; a < A.edges.Count; a++)
                {
                    if (a % 1000 == 0) Console.Write("-");
                    if (hB.ContainsKey(A.edges[a].HASH()))
                    {
                        for (int b = 0; b < B.edges.Count; b++)
                        {
                            if (A.edges[a].GetHashCode() == B.edges[b].GetHashCode())
                            {
                                recheck = true;
                                Console.Write("+");
                                if (b < B.edges.Count / 2) B.Mutate(b, r.Next(B.edges.Count / 2, B.edges.Count), true);
                                else B.Mutate(r.Next(0, B.edges.Count / 2), b, true);
                                //if (b + 1 < B.edges.Count) B = B.Mutate(b + 1);
                                //b -= 2;
                                //if (b < -1) 
                                b = -1;
                                hB = ToDictionary(B.edges);
                            }
                        }
                    }
                }
            }
            Console.WriteLine("Done!");
        }
        static Dictionary<String, Edge> ToDictionary(List<Edge> list)
        {
            Dictionary<String, Edge> h = new Dictionary<String, Edge>();
            for (int l = 0; l < list.Count; l++) h.Add(list[l].HASH(), list[l]);
            return h;
        }
        static List<City> ReadCities()
        {
            List<City> cities = new List<City>();
            using (FileStream fs = File.Open("data/santa_cities.csv", FileMode.Open))
            {
                using (StreamReader sr = new StreamReader(fs))
                {
                    sr.ReadLine(); // ignore header
                    while (!sr.EndOfStream) cities.Add(new City(sr.ReadLine()));
                }
            }
            return cities;
        }
        static void ReadAnswers(ref List<City> A, ref List<City> B)
        {
            using (FileStream fs = File.Open("answer.csv", FileMode.Open))
            {
                using (StreamReader sr = new StreamReader(fs))
                {
                    Console.WriteLine("Building answers from file");
                    sr.ReadLine(); // ignore header
                    int true_index = 0;
                    while (!sr.EndOfStream) 
                    {
                        if (true_index % 10000 == 0) Console.Write(true_index + "-");
                        String[] aANDb = sr.ReadLine().Split(',');
                        int a_id = int.Parse(aANDb[0]);
                        int b_id = int.Parse(aANDb[1]);
                        for (int a = 0; a < A.Count; a++)
                        {
                            if (A[a].id == a_id)
                            {
                                City register = A[true_index];
                                A[true_index] = A[a];
                                A[a] = register;
                                break;
                            }
                        }
                        for (int b = 0; b < B.Count; b++)
                        {
                            if (B[b].id == b_id)
                            {
                                City register = B[true_index];
                                B[true_index] = B[b];
                                B[b] = register;
                                break;
                            }
                        }
                        true_index++;
                    }
                    Console.WriteLine("Done!");
                }
            }
        }
        static List<City> Clone(List<City> ToClone) 
        {
            List<City> clone = new List<City>();
            clone.AddRange(ToClone.GetRange(0, ToClone.Count));
            return clone;
        }
        static List<City> Shuffle(List<City> shuff)
        {
            for (int s = 0; s < shuff.Count; s++)
            {
                int random = r.Next(shuff.Count);
                City register = shuff[s];
                shuff[s] = shuff[random];
                shuff[random] = register;
            }
            return shuff;
        }
        static void Save(Gene a, Gene b)
        {
            Console.WriteLine("Building answer");
            if (File.Exists("answer.csv")) File.Delete("answer.csv");
            using (FileStream fs = File.Create("answer.csv"))
            {
                using (StreamWriter sw = new StreamWriter(fs))
                {
                    sw.WriteLine("path1,path2,(fit:" + a.fitness + ":" + b.fitness + ")");
                    sw.WriteLine(a.edges[0].a.id + "," + b.edges[0].a.id);
                    sw.WriteLine(a.edges[0].b.id + "," + b.edges[0].b.id);
                    for (int e = 1; e < a.edges.Count; e++) sw.WriteLine(a.edges[e].b.id + "," + b.edges[e].b.id);
                }
            }
        }
    }

    class Gene
    {
        static Random     r     = new Random();
        public List<Edge> edges = new List<Edge>();
        public double     fitness;
        private Gene(){}
        public Gene(List<City> Cities)
        {
            fitness = 0;
            edges   = GetEdges(Cities);
            for (int e = 0; e < edges.Count; e++) fitness += edges[e].distance;
        }
        public Gene Mutate()
        {
            return Mutate(r.Next(0, edges.Count));
        }
        public Gene Mutate(int Mutation_Point)
        {
            Gene mutant         = Clone(this);
            Edge left           = (Mutation_Point - 1 >= 0 ? mutant.edges[Mutation_Point - 1] : null);
            Edge apex           = mutant.edges[Mutation_Point];
            Edge right          = (Mutation_Point + 1 < mutant.edges.Count ? mutant.edges[Mutation_Point + 1] : null);

            if (left != null)  mutant.fitness -= left.distance;
                               mutant.fitness -= apex.distance;
            if (right != null) mutant.fitness -= right.distance;

            if (left != null)  left  = new Edge(left.a, apex.b);
                               apex  = new Edge(apex.b, apex.a);
            if (right != null) right = new Edge(apex.b, right.b);

            if (left != null)  mutant.edges[Mutation_Point - 1] = left;
                               mutant.edges[Mutation_Point]     = apex;
            if (right != null) mutant.edges[Mutation_Point + 1] = right;

            if (left != null)  mutant.fitness += left.distance;
                               mutant.fitness += apex.distance;
            if (right != null) mutant.fitness += right.distance;

            return mutant;
        }
 
        public bool Mutate(int Left, int Right, bool force = false)
        {
            if (Right - Left <= 1) throw new Exception("Attemping to switch an edge with itself, or left > right");
            double old_fitness  = 0;
            old_fitness += edges[Right    ].distance;
            old_fitness += edges[Left     ].distance;
            old_fitness += edges[Left  + 1].distance;
            old_fitness += edges[Right - 1].distance;
            
            Edge new_right           = new Edge(edges[Left     ].b, edges[Right   ].b);
            Edge new_left            = new Edge(edges[Left     ].a, edges[Right   ].a);
            Edge new_left_plus_one   = new Edge(edges[Right    ].a, edges[Left + 1].b);
            Edge new_right_minus_one = new Edge(edges[Right - 1].a, edges[Left    ].b);

            double new_fitness  = 0;
            new_fitness += new_right.distance;
            new_fitness += new_left.distance;
            new_fitness += new_left_plus_one.distance;
            new_fitness += new_right_minus_one.distance;

            if (new_fitness < old_fitness || force)
            {
                edges[Right    ] = new_right;
                edges[Left     ] = new_left;
                edges[Left  + 1] = new_left_plus_one;
                edges[Right - 1] = new_right_minus_one;
                fitness -= old_fitness;
                fitness += new_fitness;
                return true;
            }
            return false;
        }
        public List<Edge> GetEdges(List<City> path)
        {
            List<Edge> e = new List<Edge>();
            for (int p = 0; p < path.Count - 1; p++) e.Add(new Edge(path[p], path[p + 1]));
            return e;
        }
        private static Gene Clone(Gene ToClone)
        {
            Gene clone    = new Gene();
            clone.fitness = ToClone.fitness;
            clone.edges.AddRange(ToClone.edges.GetRange(0, ToClone.edges.Count));
            return clone;
        }
        public Bitmap Draw()
        {
            Console.WriteLine("Drawing...");
            float width = 0; float height = 0;
            for (int e = 0; e < edges.Count; e++)
            {
                float widest   = (edges[e].a.x > edges[e].b.x ? edges[e].a.x : edges[e].b.x);
                float heighest = (edges[e].a.y > edges[e].b.y ? edges[e].a.y : edges[e].b.y);
                width          = (width > widest ? width : widest);
                height         = (height > heighest ? height : heighest);
            }
            Bitmap b = new Bitmap((int)width / 10, (int)height / 10);
            using (Graphics g = Graphics.FromImage(b))
            {
                g.Clear(Color.White);
                Pen p = new Pen(Color.FromArgb(50, Color.Black));
                for (int e = 0; e < edges.Count; e++) g.DrawLine(Pens.Black, edges[e].a.x / 10, edges[e].a.y / 10, edges[e].b.x / 10, edges[e].b.y / 10);
            }
            return b;
        }
    }

    class City
    {
        public int   id;
        public float x;
        public float y;
        public City(String Line)
        {
            String[] split = Line.Split(',');
            id = int.Parse(split[0]);
            x  = float.Parse(split[1]);
            y  = float.Parse(split[2]);
        }
        public override bool Equals(object obj)
        {
            return id == ((City)obj).id;
        }
    }
    class Edge
    {
        public City   a;
        public City   b;
        public double distance;
        public Edge(City A, City B)
        {
            a        = A;
            b        = B;
            distance = Math.Sqrt(Math.Pow(a.x - b.x, 2) + Math.Pow(a.y - b.y, 2));
        }
        public override int GetHashCode()
        {
            if (a.id > b.id) return (a.id + "-" + b.id).GetHashCode();
            else             return (b.id + "-" + a.id).GetHashCode();
        }
        public override string ToString()
        {
            return a.id + "-" + b.id;
        }
        public string HASH()
        {
            if (a.id > b.id) return (a.id + "-" + b.id);
            else             return (b.id + "-" + a.id);
        }
    }
}