I'm working on creating a genetic algorithm solution to the traveling salesman problem in C# and in order to do that I'm trying to create a List of Lists of float arrays, or a List<List<float[]>> if that helps.

I've got a function called RandomInitialPopulation which takes in a List<float[]> xyCoordinates and an int populationSize and outputs a List with a populationSize number of elements, where each element is an object with a random permutation of the List<float[]> xyCoordinates and the total distance involved in traversing the list of xyCoordinates in that order

In order to create the random permutations for each element I've got another function called ShuffleList that takes in List<float[]> arrayToShuffle and outputs a random permutation of that List

ShuffleList is called n times, where n = populationSize. The problem I've noticed is that if I just run my code with no breakpoints, all n outputs from ShuffleList are the exact same. But if I place a breakpoint on the return statement, and repeatedly hit F5 n number of times, ShuffleList produces a different permutation each time, which is the behavior I want it to do.

Here's my code, I can't for the life of me figure out why this code is behaving the way it is.

    private List<PopulationMember> RandomInitialPopulation(List<float[]> xyCoordinates, int populationSize)
    {
        List<PopulationMember> population = new List<PopulationMember>();
        for (int i = 0; i < populationSize; i  )
        {
            PopulationMember populationMember = new PopulationMember();
            populationMember.Path = ShuffleList(xyCoordinates);
            populationMember.TotalDistance = GetPathDistance(populationMember.Path);
            population.Add(populationMember);
        }
        return population;
    }

    private List<float[]> ShuffleList(List<float[]> arrayToShuffle)
    {
        List<float[]> tempCollection = new List<float[]>(arrayToShuffle);
        List<float[]> shuffledXYCoordinatesArray = new List<float[]>();
        Random rnd = new Random();

        while (tempCollection.Count > 0)
        {
            int num = rnd.Next(tempCollection.Count);
            shuffledXYCoordinatesArray.Add(tempCollection.ElementAt(num));
            tempCollection.RemoveAt(num);
        }
        return shuffledXYCoordinatesArray;
    }

Here's the code for the PopulationMember object as well

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

namespace TravelingSalesman
{
    public class PopulationMember
    {
        public List<float[]> Path { get; set; }

        public float TotalDistance { get; set; }
    }
}

Here's some screenshots too:

Here's what I'm seeing if I just run ShuffleList with no breakpoints

You can tell the Path Lists are all the same because the TotalDistance is the same for each one

But here's what I'm seeing if I leave a breakpoint on the return statement on ShuffleList and hit it everytime it runs, pressing F5 each time

This is the behavior I want

Any help would be greatly appreciated!

CodePudding user response：

Have a single static Random object created once.

When you initialise multiple Random objects very close to each other in time then they get the same seed and Next produces the same number.

When you debug, you slow things down and new Random() gets a new different seed so the numbers are different.

CodePudding user response：

As already mentioned, you need a single static Random object to avoid duplication in the random numbers being generated when the instances of Random are created in quick succession.

Here's a better implementation to work from:

private List<PopulationMember> RandomInitialPopulation(List<float[]> xyCoordinates, int populationSize) =>
    Enumerable
        .Range(0, populationSize)
        .Select(i => ShuffleList(xyCoordinates))
        .Select(x => new PopulationMember()
        {
            Path = x,
            TotalDistance = GetPathDistance(x)
        })
        .ToList();

private static readonly ThreadLocal<Random> rnd =
    new ThreadLocal<Random>(() => new Random());

private List<float[]> ShuffleList(List<float[]> arrayToShuffle)
{
    var output = arrayToShuffle.ToList();
    for (var i = 0; i < output.Count; i  )
    {
        var j = rnd.Value.Next(i, output.Count);
        (output[i], output[j]) = (output[j], output[i]);
    }
    return output;
}

And, if you're OK, with a slight loss of efficiency, then you could just do this:

private List<PopulationMember> RandomInitialPopulation(List<float[]> xyCoordinates, int populationSize) =>
    Enumerable
        .Range(0, populationSize)
        .Select(i => xyCoordinates.OrderBy(x => rnd.Value.Next()).ToList())
        .Select(x => new PopulationMember()
        {
            Path = x,
            TotalDistance = GetPathDistance(x)
        })
        .ToList();

private static readonly ThreadLocal<Random> rnd =
    new ThreadLocal<Random>(() => new Random());