QuarK QuarK - 1 month ago 9
C# Question

Why List<T>.RemoveRange(index, count) changes value before index?

I am implementing a classic genetic algorithm. In the crossover phase I am finding some strange behaviour.

private static void Crossover(ref List<CrossoverPair> pairs)
{
var random = new Random();
//TODO debug this
foreach (var pair in pairs)
{
for (var i = 0; i < pair.First.Chromosomes.Count; i++)
{
var locus = random.Next(1, 12);
var crossoverLength = pair.First.Chromosomes[i].Genes.Count - locus;
var swapFirst = pair.First.Chromosomes[i].Genes.Skip(locus).Take(crossoverLength).ToList();
var swapSecond = pair.Second.Chromosomes[i].Genes.Skip(locus).Take(crossoverLength).ToList();
pair.First.Chromosomes[i].Genes.RemoveRange(locus - 1, crossoverLength);
pair.First.Chromosomes[i].Genes.AddRange(swapSecond);
pair.Second.Chromosomes[i].Genes.RemoveRange(locus - 1, crossoverLength);
pair.Second.Chromosomes[i].Genes.AddRange(swapFirst);
}
}
}


Each chromosome contains 12 genes. It swaps homologous parts starting from a randomly defined locus. For instance, if we have
locus = 8
and
crossoverLength = 4
, we first remove genes from
Genes[8]
to
Genes[11]
using
RemoveRange
, then we add genes from another chromosome using
AddRange
.

Sometimes something strange happens: when we use
RemoveRange
,
Genes[7]
(for this instance) changes its value from 0 to 1 or from 1 to 0. It doesn't happen on each iteration, sometimes everything works fine. I've noticed it happens more often for
locus = 7..11
.

It doesn't hurt algorithm too much (just more mutations :D). But does anyone know why it inverts values?

Strange behaviour proof

Update:

Thanks a lot to BJ Myers for irrefragable answer.
Everyone else, who will read this post later, will may be interested in, why does it happen. It is explained good here.

Answer

RemoveRange is not changing the value before the specified index. The reason it appears to be is because your indexes are off by one.

Take a look at this line:

pair.First.Chromosomes[i].Genes.RemoveRange(locus - 1, crossoverLength);

If we assume (as in your example) locus = 8 and therefore crossoverLength = 4, the desired behavior would be to remove the elements with indexes [8] through [11]. But since you have subtracted one from locus, you are passing in 7 as the first parameter to RemoveRange and therefore removing elements [7] through [10].

The correct code should not include a - 1 offset for either of the calls to RemoveRange:

pair.First.Chromosomes[i].Genes.RemoveRange(locus, crossoverLength);

The behavior that you perceived as element [7] changing was actually the result of elements [7] through [10] being removed, and the element formerly at [11] shifting down into position [7]. If your "genes" are always binary, then there is a 50/50 chance that the value would "change" as a result of the RemoveRange call.