Skynet

        protected override void doBaseInitialization()
        {
            this.genotype = new List<Connection>();
            this.rand = new Random();
        }

        protected override void doRandomInitialization()
        {
            List<Location> locations = World.GetCitiesRandomized();
            for (Int32 i = locations.Count - 1; i > 0; i--)
            {
                this.Genotype.Add(new Connection(locations[i], locations[i - 1]));
            }
            this.Genotype.Add(new Connection(locations[0], locations[locations.Count - 1]));
        }

        /// <summary>Does a crossover operation between to parents to create a new child.</summary>
        protected override void doCrossover(IIndividual m, IIndividual f)
        {
            Route mother = (Route)m;
            Route father = (Route)f;
 
            // To keep track of all cities; they all need to be connected twice.
            Dictionary<Int32, Int32> cityUsage = Route.getUsageDictionary();
 
            // Add the genes both parents agree on to the genotype.
            foreach(Connection connection in mother.Genotype)
            {
                if (father.Genotype.Contains(connection)) 
                {
                    this.Genotype.Add(connection);
                    cityUsage[connection.Location1.Id]++;
                    cityUsage[connection.Location2.Id]++;
                }
            }
 
            Route fittest = mother.Fitness > father.Fitness ? mother : father;
            Route nubbest = mother.Fitness <= father.Fitness ? mother : father;
 
            Int32 nrsToGo = cityUsage.Count / 2;
 
            // Connect up to half of the remaining locations with genes from the fittest parent.
            foreach (Connection connection in fittest.Genotype)
            {
                if (!this.Genotype.Contains(connection))
                {
                    nrsToGo--;
                    this.Genotype.Add(connection);
                    cityUsage[connection.Location1.Id]++;
                    cityUsage[connection.Location2.Id]++;
                    if (nrsToGo <= 0) break;
                }
            }
 
            // Connect up to half of the remaining locations with genes from the nubbest parent. 
            foreach (Connection connection in nubbest.Genotype)
            {
                if (this.getConnectionValidity(connection, cityUsage))
                {
                    this.Genotype.Add(connection);
                    cityUsage[connection.Location1.Id]++;
                    cityUsage[connection.Location2.Id]++;
                }
            }
 
            // Connect the remaining locations with new random connections.
            Int32[] keys = cityUsage.Keys.ToArray();
            foreach (Int32 cityId in keys)
            {
                while (cityUsage[cityId] < 2)
                {
                    Connection connection;
                    Int32 otherCityId;
                    Boolean contains;
                    do
                    {
                        otherCityId = this.rand.Next(cityUsage.Count);
 
                        // Find a city that has not been connected to 2 times yet.
                        while(cityUsage[otherCityId] >= 2 || otherCityId == cityId)
                        {
                            otherCityId++;
                            if (otherCityId >= cityUsage.Count) otherCityId = 0;
                        }
 
                        connection = new Connection(World.Cities[cityId], World.Cities[otherCityId]);
                        contains = this.Genotype.Contains(connection);
                    }
 
                    // Repeat finding a second city for the connection untill it's valid.
                    while (!this.getConnectionValidity(connection, cityUsage));
 
                    this.Genotype.Add(connection);
                    cityUsage[cityId]++;
                    cityUsage[otherCityId]++;
                }
            }
        }

        private Boolean getConnectionValidity(Connection connection, Dictionary<Int32, Int32> cityUsage)
        {
            if (connection.Location1 == connection.Location2 
                || cityUsage[connection.Location1.Id] > 1 || cityUsage[connection.Location2.Id] > 1
                || this.Genotype.Contains(connection)
                )
            {
                return false;
            }
 
            if (cityUsage[connection.Location1.Id] == 0 || cityUsage[connection.Location2.Id] == 0)
            {
                return true;
            }
 
            Int32 directionNr = 0;
            Int32 maxLength = cityUsage.Count;
            do
            {
                Int32 connectionAmount = 0;
 
                Location previouseLoc, currentLoc, endLocation;
                currentLoc = directionNr == 0 ? connection.Location1 : connection.Location2;
                endLocation = directionNr == 0 ? connection.Location2 : connection.Location1;
                previouseLoc = currentLoc;
 
                while (connectionAmount <= maxLength && currentLoc != endLocation) 
                {
                    Location prePreviouse = previouseLoc;
                    previouseLoc = currentLoc;
                    currentLoc = Route.GetNextLocation(currentLoc, prePreviouse, this.genotype);
                    if (currentLoc == previouseLoc) break; // The same gets returned when there is no next connection.
                    connectionAmount++;
                }
 
                // If the cities are connected by going through all cities, the connection is valid.
                if (connectionAmount + 1 >= maxLength)
                {
                    return true;
                }
                // If the cities are connected without going through all cities, the connection is invalid.
                else if (currentLoc == endLocation)
                {
                    return false;
                }
 
                directionNr++;
            } while (directionNr < 2);
 
            // No connection between the cities yet, so it's valid.
            return true;
        }

        protected override Double determineFitness()
        {
            Double distance = 0;
            foreach(Connection connection in this.genotype)
            {
                distance += connection.Length;
            }
            return -distance;
        }

        protected override void doMutation()
        {
            // Get a random connection, which will be the first connection to the location that gets excluded.
            Connection initialConn = this.Genotype[this.rand.Next(this.Genotype.Count)];
            this.Genotype.Remove(initialConn);
 
            // This city will be taken out of the route, and then reintegrated via other connections.
            Location swapLocation = initialConn.Location1; 
 
            Location newConn1, newConn2;
            newConn1 = initialConn.Location2;
            newConn2 = null;
 
            // Determine the second connection to the location that gets excluded.
            foreach(Connection conn in this.Genotype)
            {
                if ((conn.Location1 == swapLocation || conn.Location2 == swapLocation) && conn != initialConn)
                {
                    newConn2 = conn.Location1 == swapLocation ? conn.Location2 : conn.Location1;
                    this.Genotype.Remove(conn);
                    break;
                }
            }
 
            // Add a new connection between the locations previously connected to the excluded location.
            Connection bridgeConnection = new Connection(newConn1, newConn2);
            this.Genotype.Add(bridgeConnection);
 
            // Find a connection to replace by 2 new ones that re-include the excluded location.
            Connection connToReplace;
            do
            {
                connToReplace = this.Genotype[this.rand.Next(this.Genotype.Count)];
            } while(connToReplace == bridgeConnection);
 
            // Remove the connection and add 2 new ones to re-include the excluded location.
            this.Genotype.Remove(connToReplace);
            this.Genotype.Add(new Connection(connToReplace.Location1, swapLocation));
            this.Genotype.Add(new Connection(connToReplace.Location2, swapLocation));
        }

        private void initiateAlgorithm()
        {
            Route.HasUsageDictionary = false;
 
            population = new Population<Route>(
                Math.Max((Int32)numPopulationSize.Value, 10),
                Math.Max(numMaxGenerations.Value, 1),
                Math.Max(numStagnationLimit.Value, 2)
                );
 
            population.MutationRatio = (Int32)sliderMutationRatio.Value;
            population.ElitismPercentage = (Int32)sliderElitismPercantage.Value;
 
            population.GenerationDelay = (Int32)Utilities.getLogaritmicSliderValue(this.slideGenerationDelay);
 
            population.RemoveTwins = (Boolean)this.cbRemoveTwins.IsChecked;
            population.RemoveDuplicates = (Boolean)this.cbRemoveDuplicates.IsChecked;
 
            population.GenerationComplete += new Population<Route>.GenerationCompleteEventHandler(population_GenerationComplete);
            population.EvolutionComplete += new Population<Route>.EvolutionCompleteEventHandler(population_EvolutionComplete);
            population.NewFittest += new Population<Route>.NewFittestEventHandler(population_NewFittest);
 
            this.timer.Start();
 
            String selectionAlgorithm = this.ddSelectionAlgorithm.Text;
 
            switch (selectionAlgorithm)
            {
                case "Rank based":
                    population.DoRankBasedSelection();
                    break;
                case "Truncated rank":
                    population.DoTruncatedRankSelection((Int32)numTruncationSize.Value);
                    break;
                case "Wheel based":
                    population.DoRouletteWheelSelection();
                    break;
                case "Tournament based":
                    population.DoTournamentBasedSelection(numTournamentSize.Value);
                    break;
            }
 
            this.setControlStates();
        }